max_flow_book.t

A Library of Efficient Data Types and Algorithms,封装了常用的ADT及其相关算法的软件包

                         }
 }
    
    if ( ev > 0 ) { 
                    for (e = G.first_in_edge(v); e; e = G.in_succ(e))
                    { num_edge_inspections++;
                      NT& fe = flow[e];
                      if (fe == 0) continue;
                      node w = source(e);
                      int dw = dist[w];
                      if ( dw < dv ) // equivalent to ( dw == dv - 1 )
                      { num_pushes++;
                        NT& ew = excess[w];
                        if (ew == 0) U.insert0(w,dw); 
                        if (ev <= fe) 
                        { fe -= ev; ew += ev;
                          ev = 0;   // stop: excess[v] exhausted
                          break;
                        }
                        else
                        { ew += fe; ev -= fe;
                          fe = 0;
                        }
                      }
                      else { if ( dw < dmin ) dmin = dw; }
                    }
 }

    excess[v] = ev;

    if (ev > 0) { 
                  if (num_edge_inspections <= limit_heur)
                    {   
                      num_relabels++;
                      if (phase_number == 1)
                      { if ( --count[dv] == 0 || dmin >= n - 1)
                        { // v cannot reach t anymore 
                          
                          dist[v] = n; 
                          if ( dmin < n )
                          { Q.append(v); 
                            node w,z;
                            while ( !Q.empty() )
                            { edge e; 
                              w = Q.pop(); num_gaps++;
                              forall_out_edges(e,w)
                              { if ( flow[e] < cap[e] && dist[z = G.target(e)] < n)
                                { Q.append(z);  
                                  count[dist[z]]--; dist[z] = n;
                                }
                              }
                              forall_in_edges(e,w)
                              { if ( flow[e] > 0 && dist[z = G.source(e)] < n)
                                { Q.append(z); 
                                  count[dist[z]]--; dist[z] = n;
                                }
                              }
                            }
                          }

                        }
                        else 
                        { dist[v] = ++dmin; count[dmin]++;
                          U.insert(v,dmin); 
                        }
                      }
                      else // phase_number == 2
                      { dist[v] = ++dmin; 
                        U.insert(v,dmin); 
                      }
 }
                  else
                    { limit_heur += heuristic;
                      num_global_relabels++;
                      
                      U.clear();

                      if (phase_number == 1)
                      { dist.init(G,n);
                        compute_dist_t(G,t,flow,cap,excess,dist,U,Q,count);
                        if ( U.empty() ) 
                        { node u;
                          forall_nodes(u,G) 
                          { if (dist[u] == n) 
                            { S.append(u);
                              dist[u] = max_level;
                            }
                          }
                          phase_number = 2;
                          compute_dist_s(G,s,flow,excess,dist,U,Q);
                        }
                      }
                      else
                      { node u; 
                        forall(u,S) dist[u] = max_level;
                        compute_dist_s(G,s,flow,excess,dist,U,Q);
                      }
 
                    }
 }
  }


#ifdef TEST
  assert(CHECK_MAX_FLOW_T(G,s,t,cap,flow));
#endif

  return excess[t];
}



// static graph for (mis)using node-info fields
static GRAPH<node,edge> NEXT;

class level_queue {

const graph* gr;

node*  head;
node*  stop;
node*  max;



// array for saving and restoring original node infos
node* save;

public:


level_queue(const graph& G, int sz)
{ gr = &G;
  head = new node[sz];
  save = new node[G.number_of_nodes()];
  max  = head;
  stop = head + sz;
  node* p = head;
  while(p < stop) *p++ = nil; 
  node  v;
  p = save;
  forall_nodes(v,G) *p++ = NEXT[v];
 }

~level_queue() 
 { node  v;
   node* p = save;
   forall_nodes(v,*gr) NEXT[v] = *p++;
   delete[] save;
   delete[] head; 
  }


void insert0(node v, int i)
{ // insert without updating max pointer
   node* h = head + i;
  NEXT[v] = *h;
  *h = v;
 }

void insert(node v, int i)
{ // insert and update max pointer
  node* h = head + i;
  if (h > max) max = h;
  NEXT[v] = *h;
  *h = v;
 }

node del_max()
{ // remove and return maximum (nil if list is empty) 
  while (*max == nil && max > head) max--; 
  node v = *max;
  if (v != nil) *max = NEXT[v];
  return v;
}

node find_max()
{ // return maximum (nil if list is empty) 
  while (*max == nil && max > head) max--; 
  return *max;
}

node del() { return del_max(); }

bool empty() { return find_max() == nil; }

void clear() 
{ *head = nil;
  while (max > head) *max-- =  nil; 
 }

void clear(int i)
{ // erase everything on and above level i
  node* p = head + i;
  while (max >= p) *max-- =  nil;
  if (max < head) max = head;
}

};



template<class NT>
__temp_func_inline
NT MAX_FLOW_T(const graph& G, node s, node t, 
                 const edge_array<NT>& cap, 
                 edge_array<NT>& flow, 
                 int& num_pushes, 
                 int& num_edge_inspections,
                 int& num_relabels,
                 int& num_global_relabels,
                 int& num_gaps,
                 float h)
{  if (s == t) error_handler(1,"MAXFLOW: source == sink");


  int n = G.number_of_nodes(); int max_level = 2*n - 1;
  int m = G.number_of_edges(); 

/*
  node_array<int> dist(G,0);
  node_array<NT>  excess(G,0);
*/

// use free data slots for node_arrays if available

  node_array<NT> excess;
  excess.use_node_data(G,0);

  //flow.init(G,0);
  edge e;
  forall_edges(e,G) flow[e] = 0;

  forall_out_edges(e,s) 
  { NT c = cap[e];
    if (c == 0) continue;
    node v = target(e);
    flow[e] = c;
    excess[s] -= c;
    excess[v] += c;
  } 

  level_queue  U(G,2*n);
  b_queue<node> Q(n);
  int phase_number = 1;
  array<int> count(n);
  list<node> S;
  int heuristic  = (int) (h*m);
  int limit_heur = heuristic;

  //node_array<int> dist(G);
  //dist.init(G,n);
  node_array<int> dist;
  dist.use_node_data(G,n);

  compute_dist_t(G,t,flow,cap,excess,dist,U,Q,count);

  num_relabels         = 0;
  num_pushes           = 0;
  num_edge_inspections = 0;
  num_global_relabels  = 0;
  num_gaps = 0;

  
  for(;;) 
  {
    
    node v = U.del();

    if (v == nil)
    { 
      if ( phase_number == 2 ) break; // done

      //dist.init(G,n);
      dist.use_node_data(G,n);
      compute_dist_t(G,t,flow,cap,excess,dist,U,Q,count);

      node u;
      forall_nodes(u,G) 
      { if (dist[u] == n) 
        { S.append(u);
          dist[u] = max_level;
        }
      }
      phase_number = 2;
      compute_dist_s(G,s,flow,excess,dist,U,Q);
      continue;
    }
      
    if (v == t) continue;

    if (dist[v] == n && phase_number == 1) continue;
   
    NT  ev   = excess[v]; // excess of v 
    int dv   = dist[v];   // level of v
    int dmin = MAXINT;
    edge e;

    if ( dist[v] < n )
    { 
      for (e = G.first_adj_edge(v); e; e = G.adj_succ(e))
      { num_edge_inspections++;
        NT& fe = flow[e];
        NT  rc = cap[e] - fe;
        if (rc == 0) continue;
        node w = target(e);
        int dw = dist[w];
        if ( dw < dv ) // equivalent to ( dw == dv - 1 )
        { num_pushes++;
          NT& ew = excess[w];
          if (ew == 0) U.insert0(w,dw); 
          if (ev <= rc) 
          { ew += ev; fe += ev;
            ev = 0;   // stop: excess[v] exhausted
            break;
          }
          else
          { ew += rc; fe += rc;
            ev -= rc;
          }
        }
        else { if ( dw < dmin ) dmin = dw; }
      }
 }
    if ( ev > 0 )
    { 
      for (e = G.first_in_edge(v); e; e = G.in_succ(e))
      { num_edge_inspections++;
        NT& fe = flow[e];
        if (fe == 0) continue;
        node w = source(e);
        int dw = dist[w];
        if ( dw < dv ) // equivalent to ( dw == dv - 1 )
        { num_pushes++;
          NT& ew = excess[w];
          if (ew == 0) U.insert0(w,dw); 
          if (ev <= fe) 
          { fe -= ev; ew += ev;
            ev = 0;   // stop: excess[v] exhausted
            break;
          }
          else
          { ew += fe; ev -= fe;
            fe = 0;
          }
        }
        else { if ( dw < dmin ) dmin = dw; }
      }
 }

    excess[v] = ev;

    if (ev > 0) 
    { 
      if (num_edge_inspections <= limit_heur)
        {   
          num_relabels++;
          if (phase_number == 1)
          { if ( --count[dv] == 0 || dmin >= n - 1)
            { // v cannot reach t anymore 
              
              dist[v] = n; 
              if ( dmin < n )
              { Q.append(v); 
                node w,z;
                while ( !Q.empty() )
                { edge e; 
                  w = Q.pop(); num_gaps++;
                  forall_out_edges(e,w)
                  { if ( flow[e] < cap[e] && dist[z = G.target(e)] < n)
                    { Q.append(z);  
                      count[dist[z]]--; dist[z] = n;
                    }
                  }
                  forall_in_edges(e,w)
                  { if ( flow[e] > 0 && dist[z = G.source(e)] < n)
                    { Q.append(z); 
                      count[dist[z]]--; dist[z] = n;
                    }
                  }
                }
              }

            }
            else 
            { dist[v] = ++dmin; count[dmin]++;
              U.insert(v,dmin); 
            }
          }
          else // phase_number == 2
          { dist[v] = ++dmin; 
            U.insert(v,dmin); 
          }
 }
      else
        { limit_heur += heuristic;
          num_global_relabels++;
          
          U.clear();

          if (phase_number == 1)
          { //dist.init(G,n);
            dist.use_node_data(G,n);
            compute_dist_t(G,t,flow,cap,excess,dist,U,Q,count);
            if ( U.empty() ) // U is empty
            { node u;
              forall_nodes(u,G) 
              { if (dist[u] == n) 
                { S.append(u);
                  dist[u] = max_level;
                }
              }
              phase_number = 2;
              compute_dist_s(G,s,flow,excess,dist,U,Q);
            }
          }
          else
          { node u; 
            forall(u,S) dist[u] = max_level;
            compute_dist_s(G,s,flow,excess,dist,U,Q);
          }

                   
        }
 }
  }


#ifdef TEST
  assert(CHECK_MAX_FLOW_T(G,s,t,cap,flow));
#endif

  return excess[t];
}


template <class NT>
__temp_func_inline
NT MAX_FLOW_T(const graph& G, node s, node t, 
                 const edge_array<NT>& cap, 
                 edge_array<NT>& flow)
{ int num_pushes, num_edge_inspections, num_relabels, num_global_relabels,
      num_gaps;
  float h = 5.0;
  return MAX_FLOW_T(G,s,t,cap,flow,num_pushes,num_edge_inspections,
        num_relabels,num_global_relabels,num_gaps,h);
}




#if LEDA_ROOT_INCL_ID == 450451
#undef LEDA_ROOT_INCL_ID
#include <LEDA/POSTAMBLE.h>
#endif


LEDA_END_NAMESPACE