max_flow_book.t

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

    if (v == t) continue;

    NT  ev   = excess[v]; // excess of v 
    int dv   = dist[v];   // level of v
    int dmin = MAXINT;     // for local relabeling heuristic
    edge e;

    if (dv < 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) 
    { dist[v] = 1 + dmin; 
      num_relabels++;
      U.insert(v,dist[v]);
    }
  } 


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

  return excess[t];
}




template<class NT, class SET>
inline void compute_dist_t(const graph& G, node t, const edge_array<NT>& flow, 
                           const edge_array<NT>& cap, 
                           const node_array<NT>& excess, node_array<int>& dist, 
                           SET& U, b_queue<node>& Q, array<int>& count)
{ 
  int n = G.number_of_nodes();
  Q.append(t);

  dist[t] = 0; 

  count.init(0);
  count[0] = 1;

  while ( !Q.empty() )
  { node v = Q.pop();
    int  d = dist[v] + 1;
    edge e;

    for(e = G.first_adj_edge(v); e; e = G.adj_succ(e))
    { if ( flow[e] == 0 ) continue;
      node u = target(e); 
      int& du = dist[u];
      if ( du >= n ) 
      { du = d;
        Q.append(u); count[d]++; 
        if ( excess[u] > 0 ) U.insert(u,d); 
       }
     }

    for(e = G.first_in_edge(v); e; e = G.in_succ(e))
    { if ( cap[e] == flow[e] ) continue;
      node u = source(e); 
      int& du = dist[u];
      if ( du >= n )  
      { du = d;  
        Q.append(u); count[d]++;
       if (excess[u] > 0) U.insert(u,d); 
      }
    }
  }
}


template<class NT, class SET>
inline void compute_dist_s(const graph& G, node s, const edge_array<NT>& flow,
                           const node_array<NT>& excess, node_array<int>& dist, 
                           SET& U, b_queue<node>& Q)
{ 
  int n = G.number_of_nodes();
  int max_level = 2*n - 1;

  Q.append(s);
  dist[s] = n;

  while ( !Q.empty() )
  { node v = Q.pop();
    int  d = dist[v] + 1;
    edge e;
    for(e = G.first_adj_edge(v); e; e = G.adj_succ(e))
    { if ( flow[e] == 0 ) continue;
      node u = target(e); 
      int& du = dist[u];
      if ( du == max_level )
      { du  = d;  
        if (excess[u] > 0) U.insert(u,d);
        Q.append(u);
       }
     }
   } 
}



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

  
  
  flow.init(G,0);
  //if (G.outdeg(s) == 0) return 0;
  if (G.first_adj_edge(s) == nil) return 0;

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

  node_array<NT>  excess(G,0);

  // saturate all edges leaving s

  edge e;
  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;
   } 


  
  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);

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

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



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

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

      dist.init(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;


    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)
        { 
          dmin++; num_relabels++;
          if ( phase_number == 1 && dmin >= n) dist[v] = n;
          else { 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];
}


template<class NT, class SET>
__temp_func_inline
NT MAX_FLOW_GAP_T(const graph& G, node s, node t, 
                  const edge_array<NT>& cap, edge_array<NT>& flow,
                  SET& U, 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");

  
  
  flow.init(G,0);
  //if (G.outdeg(s) == 0) return 0;
  if (G.first_adj_edge(s) == nil) return 0;

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

  node_array<NT>  excess(G,0);

  // saturate all edges leaving s

  edge e;
  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;
   } 


  
  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);

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

  
  num_relabels = num_pushes = 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);
      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; }