max_flow_stef.t

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

            { fe -= ev; 
              ew += ev;
              ev = 0;   // excess[v] exhausted
              break;
             }
            else
            { ew += fe;
              ev -= fe;
              fe = 0;
             }
           }
         else
           if (dw < dmin) dmin = dw;
       } 
     }
   
     
     excess[v] = ev;
   
     if (ev > 0)  
     { 
       // remaining excess at v
       // relabel vertex v (i.e. update dist[v]) because all
       // admissible edges in the residual graph have been saturated 
   
       if (num_relabels <= limit_heur)
         { num_relabels++;
           if (dv < n) //(phase == 1)
           { node vsucc = levels.succ(v);
             levels.del(v);
             if (level_head[dv] == v) 
             { level_head[dv] = vsucc;
               if (dmin < n && (vsucc == nil || dist[vsucc] != dv)) //gap
               { //num_gaps++;
                 num_gap_nodes++;
                 dmin = n-1; //dist[v] = n
                 for(node u = vsucc; u!=nil; u = levels.succ(u))
                 { dist[u] =  n;
                   num_gap_nodes++;
                  }
                 if (vsucc) levels.del(vsucc,levels.last());
                }
              }
            }

           dv = dmin+1;
           dist[v] = dv;

           if (dv < n) 
           { if (dv > dist[levels.last()])
               { levels.append(v);
                 level_head[dv] = v;
                }
             else
               { node u = level_head[dv];
                 levels.insert(v,u);
                }
            }
           if (dv <= max_level) U.insert(v,dv);
          }
       else
         { // heuristic suggested by Goldberg to reduce number of relabels:
           // periodically compute exact dist[] labels by a backward bfs 
           // starting at t
           limit_heur += heuristic;
           if (phase == 1) 
           { //dist.use_node_data(G,max_level+1);
             forall(v,levels) dist[v] = max_level+1;
             compute_dist1(G,t,flow,cap,dist,levels,level_head);
            }
           if (phase == 2)
           { dist.use_node_data(G,max_level+1);
             compute_dist2(G,s,flow,dist);
            }
           init_level_queue(G,excess,dist,U,min_level,max_level);
           num_updates++;
         }
      }
  } // end of main loop

  delete[] level_head;

  return excess[t];  // value of maximum flow from s to t
}



template<class NT>
inline
void compute_dist11(const graph& G, node t, const edge_array<NT>& flow, 
                                            const edge_array<NT>& cap, 
                                            node_array<int>& dist, 
                                            int* count)
{ 
  // compute exact distance values by a "backward" bfs in the
  // residual network starting at t

  int n = G.number_of_nodes();

  for(int i=0; i<n; i++) count[i] = 0;

  b_queue<node> Q(n);
  Q.append(t);

  dist[t] = 0;

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

    count[d]++;

    d = d+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);
       }
     }

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



template<class NT>
inline
void compute_dist22(const graph& G, node s, const edge_array<NT>& flow, 
                                           node_array<int>& dist)
{ // forward bfs starting in s
  // (when excess flows back to s) 

  int n = G.number_of_nodes();

  b_queue<node> Q(n);
  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); 
      if (dist[u] >= 2*n)
      { dist[u] = d;
        Q.append(u);
       }
     }
   } 
}





template<class NT>
__temp_func_inline
NT MAX_FLOW_S_T(const graph& G, node s, node t, const edge_array<NT>& cap, 
                                                edge_array<NT>& flow,
                                                int& num_pushes,
                                                int& edge_inspections,
                                                int& num_relabels,
                                                int& num_updates,
                                                int& num_gap_nodes, float h)
{ 
  int n = G.number_of_nodes();
  
  flow.init(G,0);
  
  // use free data slots for node_arrays if available
  
  node_array<int> dist;
  dist.use_node_data(G,n);
  
  node_array<NT> excess;
  excess.use_node_data(G,0);
  
  
  // parameter for heuristic suggested by Goldberg to speed up algorithm 
  // compute exact distance labels after every "heuristic" relabel steps
  
  int heuristic = (int)(h*n);

  int limit_heur = heuristic;
  
  num_pushes   = 0;
  num_relabels = 0;
  num_updates  = 0;
  num_gap_nodes= 0;

  edge_inspections = 0;
  
  
  if (s == t) error_handler(1,"MAXFLOW: source == sink");

  // saturate all edges leaving from s and init level queue
  
  level_queue1  U(G,n);
  
  edge e;
  forall_out_edges(e,s) 
  { NT c = cap[e];
    flow[e] = c;
    excess[s] -= c;
    excess[target(e)] += c;
   }

  int* count = new int[n];

  int phase = 1;

  int min_level = 0;
  int max_level = n-1;

  dist.use_node_data(G,max_level+1);
  compute_dist11(G,t,flow,cap,dist,count);

  init_level_queue(G,excess,dist,U,min_level,max_level);

  //cout << string("initialization: %.2f",used_time(T)) << endl;

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

    if (v == nil) 
    { if (phase == 2) break;
      phase = 2;
      min_level = n;
      max_level = 2*n-1;
      dist.use_node_data(G,max_level+1);
      compute_dist22(G,s,flow,dist);
      init_level_queue(G,excess,dist,U,min_level,max_level);
      continue;
     }
   
    if (v == t) continue;

   
    NT  ev = excess[v]; // temporary excess of v 
    int dv = dist[v];   // level of v

   
    int dmin = MAXINT;  // will contain minimum level of nodes adjacent
                        // in residual network if ev > 0 after push step

    // push excess ev out of v (invariant: ev > 0)
   
    if (dv < n) // do not use outgoing arcs in phase 2 (excess flows back to s)
    { edge e;
      for (e = G.first_adj_edge(v); e; e = G.adj_succ(e))
      { NT& fe = flow[e];
        NT  rc = cap[e] - fe;
        if (rc == 0) continue;
        node w = target(e);
        int dw = dist[w];
        if (dw == dv-1)
         { num_pushes++;
           NT& ew = excess[w];
           if (ew == 0) U.insert(w,dw);
           if (ev <= rc) 
           { ew += ev;
             fe += ev;
             ev = 0;   // excess[v] exhausted (stop)
             break;
            }
           else
           { ew += rc;
             fe += rc;
             ev -= rc;
            }
          }
        else
          if (dw < dmin) dmin = dw;
       }
     }
   
   
     if (ev > 0)  // stop if excess[v] == 0
     { edge e;
       for (e = G.first_in_edge(v); e; e = G.in_succ(e))
       { NT& fe = flow[e];
         if (fe == 0) continue;
         node w = source(e);
         int dw = dist[w];
         if (dw == dv-1)
          { num_pushes++;
            NT& ew = excess[w];
            if (ew == 0) U.insert(w,dw);
            if (ev <= fe) 
            { fe -= ev; 
              ew += ev;
              ev = 0;   // excess[v] exhausted
              break;
             }
            else
            { ew += fe;
              ev -= fe;
              fe = 0;
             }
           }
         else
           if (dw < dmin) dmin = dw;
       } 
     }
   
     
     excess[v] = ev;
   
   
     if (ev > 0)
     { 
       // remaining excess at v
       // relabel vertex v (i.e. update dist[v]) because all
       // admissible edges in the residual graph have been saturated 
   
       if (num_relabels <= limit_heur)
         { num_relabels++;
           if (dv < n && --count[dv] == 0 ) // gap (phase == 1)
           { //num_gaps++;
             b_queue<node> Q(n);
             Q.append(v);
             dist[v] = n;
             while ( !Q.empty() )
             { edge e;
               node w = Q.pop(); 
               num_gap_nodes++;
               forall_out_edges(e,w)
               { node z = G.target(e);
                 int& dz = dist[z];
                 if (dz < n && flow[e] < cap[e])
                 { Q.append(z);
                   count[dz]--; 
                   dz = n;
                 }
               }
               forall_in_edges(e,w)
               { node z = G.source(e);
                 int& dz = dist[z];
                 if (dz < n && flow[e] > 0)
                 { Q.append(z);
                   count[dz]--; 
                   dz = n;
                 }
               }
             }

            if (dmin < n) dmin = n-1; // dist[v] = n
           }

           dv = dmin+1;
           dist[v] = dv;

           if (dv < n) count[dv]++;
           if (dv <= max_level) U.insert(v,dv);
          }
       else
         { // heuristic suggested by Goldberg to reduce number of relabels:
           // periodically compute exact dist[] labels by a backward bfs 
           // starting at t
           limit_heur += heuristic;
           if (phase == 1) 
           { dist.use_node_data(G,max_level+1);
             compute_dist11(G,t,flow,cap,dist,count);
            }
           if (phase == 2)
           { dist.use_node_data(G,max_level+1);
             compute_dist22(G,s,flow,dist);
            }
           init_level_queue(G,excess,dist,U,min_level,max_level);
           num_updates++;
         }
      }
  } // end of main loop

  delete[] count;

  return excess[t];  // value of maximum flow from s to t
}


LEDA_END_NAMESPACE

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