home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / graph_al / _maxflow.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  14.1 KB  |  530 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _maxflow.c
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. /******************************************************************************\
  17. *                                                                              *
  18. *  MAX_FLOW                                                                    *
  19. *                                                                              *
  20. *  Max Flow Algorithm, using the Goldberg-Tarjan algorithm, Journal ACM 35,    *
  21. *  Oct 1988, p921-940 .                                                        *
  22. *                                                                              *
  23. *  Applies push steps to vertices with positive preflow, based on              *
  24. *  distance labels.  Uses FIFO rule (implemented by FIFO queue)                *
  25. *  for selecting a vertex with +ve preflow. )                                  *
  26. *                                                                              *
  27. *                                                                              *
  28. *  Implemented by                                                              *
  29. *                                                                              *
  30. *  Joseph Cheriyan & Stefan Naeher                                             *
  31. *                                                                              *
  32. *  Fachbereich Informatik                                                      *
  33. *  Universitaet des Saarlandes                                                 *
  34. *  6600 Saarbruecken                                                           *
  35. *                                                                              *
  36. \******************************************************************************/
  37.  
  38. #include <LEDA/graph_alg.h>
  39.  
  40. static
  41. void gt_bfs2(node s_vert, int dist_s_vert, 
  42.              const graph& G, node s, const edge_array(int)& cap,
  43.              edge_array(int)& flow, node_array(int)& dist);
  44.  
  45.  
  46. int MAX_FLOW(graph& G, node s, node t, const edge_array(int)& cap, 
  47.                                              edge_array(int)& flow) 
  48. {
  49.  
  50. /* Computes a maximum flow from source s to sink t, using
  51.    Goldberg-Tarjan algorithm [Journal ACM 35 (Oct 1988) p921-940].
  52.    ( Applies push steps to vertices with positive preflow, based on 
  53.      distance labels.  Uses FIFO rule (implemented by FIFO queue) 
  54.      for selecting a vertex with +ve preflow. )
  55.  
  56.    input:   cap[e]  gives capacity of edge e 
  57.  
  58.    output:  flow[e] flow on edge e
  59.             returns total flow into sink
  60.  
  61.    node_arrays used by the algorithm:
  62.    dist[v]   = lower bound on shortest distance from v to t
  63.    excess[v] = (total incoming preflow[v]) - (total outgoing preflow[v])
  64.  
  65.    Implemented by  Joseph Cheriyan & Stefan Naeher.
  66. */
  67.  
  68.  
  69. int heuristic = 1;
  70.  
  71.   /*
  72.             heuristic == parameter for heuristic suggested by Goldberg
  73.              to speed up algorithm 
  74.             0 == no heuristic
  75.             1 == compute exact distance labels after every N relabel steps
  76.            +i == compute exact distance labels after every N*i relabel steps
  77.            -i == compute exact distance labels after every N/i relabel steps
  78.  
  79.   */
  80.  
  81. node_array(int)       dist(G,0);
  82. node_array(int)       excess(G,0);
  83.  
  84. list(node) U;     // FIFO Queue used for selecting vertex with +ve preflow
  85. node     v,w;
  86. edge     e;
  87.  
  88. G.make_undirected();
  89.  
  90. int N = G.number_of_nodes();
  91.  
  92. int num_relabels = 0;
  93.  
  94. if (heuristic < -N || heuristic > N) 
  95.     heuristic = 0;
  96. else
  97.     heuristic = ((heuristic >= 0) ? N*heuristic : N/(-heuristic));
  98.  
  99. int  limit_heur = heuristic;
  100.  
  101. if (s == t) error_handler(1,"gt_max_flow: source == sink");
  102.  
  103. forall_edges(e,G)  flow[e] = 0;
  104.  
  105. forall_adj_edges(e,s)
  106. if (source(e) == s)
  107.   { v = target(e);
  108.     flow[e] = cap[e];
  109.     excess[v] += flow[e];
  110.     if (v!=s && v!=t) U.append(v);
  111.   }
  112.  
  113. dist[s] = N;
  114.  
  115. while (! U.empty() )      /* main loop */
  116. { 
  117.   v = U.pop();
  118.  
  119.   int delta;
  120.  
  121.   while ((excess[v] > 0) && G.next_adj_edge(e,v))
  122.     { // push flow along each edge e = (v,w) in the residual graph with
  123.       // dist[v] == dist[w] + 1
  124.   
  125.       if (v == source(e))
  126.       { w = target(e);
  127.  
  128.         if ((dist[v]==dist[w]+1) 
  129.         && (delta = Min(cap[e]-flow[e],excess[v])) 
  130.         && (dist[v] < N))
  131.         // pushes towards s that increase flow[e] are not allowed
  132.  
  133.         { if ((excess[w] == 0) && (w != t)) U.append(w);
  134.           flow[e] += delta;
  135.           excess[w] += delta;
  136.           excess[v] -= delta;
  137.          }
  138.        }
  139.       else
  140.       { w = source(e);
  141.         if ((dist[v] == dist[w]+1) && (delta = Min(flow[e],excess[v])))
  142.         { if ((excess[w] == 0) && (w != t) && (w != s)) U.append(w);
  143.           flow[e] -= delta;
  144.           excess[w] += delta;
  145.           excess[v] -= delta;
  146.          }
  147.        }
  148.   
  149.     }  // while ( (excess[v] > 0) && ...)
  150.   
  151.   
  152.   if (excess[v] > 0)
  153.   {
  154.     // relabel vertex v (i.e. update dist[v]) because all
  155.     // admissible edges in the residual graph have been saturated 
  156.  
  157.     num_relabels++;
  158.   
  159.     if ( heuristic 
  160.         && (num_relabels == limit_heur))
  161.     {
  162.       limit_heur += heuristic;
  163.  
  164.       // heuristic suggested by Goldberg to reduce number of relabels:
  165.       // periodically compute exact dist[] labels by two backward bfs 
  166.       // one starting at t and another starting at s
  167.  
  168.      node x;
  169.  
  170.      forall_nodes(x,G)
  171.      dist[x] = Infinity;
  172.  
  173.      gt_bfs2(t,0,G,s,cap,flow,dist);
  174.      gt_bfs2(s,N,G,s,cap,flow,dist);
  175.  
  176.     }
  177.                   
  178.     else
  179.    
  180.     {
  181.      int min_dist = Infinity;
  182.      forall_adj_edges(e,v)
  183.        {
  184.          if ((source(e) == v) && ((cap[e] - flow[e]) > 0) && (dist[v] < N))
  185.            //pushes towards s that increase flow[e] are not allowed
  186.            min_dist = Min(min_dist,dist[target(e)]);
  187.  
  188.          if ((target(e) == v) && (flow[e] > 0))
  189.            min_dist = Min(min_dist,dist[source(e)]);
  190.         }
  191.       if (min_dist != Infinity) min_dist++;
  192.       dist[v] = min_dist;
  193.  
  194.      } // else
  195.          
  196.       U.push(v);
  197.       G.init_adj_iterator(v);
  198.      
  199.     } // if (excess[v] > 0)
  200.  
  201.  }  // while (!U.empty())  
  202.        
  203.    
  204.  
  205. //code to verify that flow is legal
  206.  
  207.  
  208. /*
  209. int tot_s_flow = 0;
  210. forall_adj_edges(e,s)  
  211.    if (source(e) == s)   tot_s_flow += cap[e];
  212. if (tot_s_flow != (excess[s] + excess[t]))
  213.  { cout << "gt_max_flow: total out cap s != excess[s] + excess[t]\n";
  214.    forall_nodes(v,G)
  215.      if ((excess[v] != 0) && (v != t) && (v != s))
  216.       cout << "gt_max_flow: v!=s,t has excess[v]=" << excess[v] << "\n";
  217.   }
  218. */
  219.  
  220.  
  221. G.make_directed();
  222.  
  223. heuristic = num_relabels;
  224.  
  225. int result = excess[t];  //returns value of maximum flow from s to t
  226.  
  227. return result; 
  228.   
  229. } // procedure gt_max_flow
  230.  
  231.  
  232. //procedure to perform backward bfs starting at vertex s_vert with 
  233. //distance label dist_s_vert
  234.  
  235. static
  236. void gt_bfs2(node s_vert, int dist_s_vert,
  237.              const graph& G, node s, const edge_array(int)& cap,
  238.              edge_array(int)& flow, node_array(int)& dist)
  239. {
  240.   node x,y;
  241.   edge e;
  242.   list(node) bfs_Q;
  243.   int c;
  244.  
  245.   dist[s_vert] = dist_s_vert;
  246.   bfs_Q.append(s_vert);
  247.   while (x = bfs_Q.pop())
  248.     {
  249.       forall_adj_edges(e,x)
  250.         {
  251.           if (x == source(e)) 
  252.         { y = target(e); 
  253.                   c = flow[e]; }
  254.           else 
  255.         { y = source(e); 
  256.                   c = cap[e] - flow[e]; }
  257.  
  258.           if ( c > 0  && dist[y] == Infinity
  259.                       && !(x == target(e) && (s_vert == s)) )
  260.           // while doing bfs with s_vert==s, 
  261.           // only edges with flow[e]>0 are reachable from s
  262.  
  263.           { dist[y] = dist[x] + 1;
  264.             bfs_Q.append(y);
  265.             G.init_adj_iterator(y);
  266.  
  267.         //next statement is not really needed, but is added for
  268.         //protection, to ensure that s does not get relabelled by
  269.         //bfs starting at t; this may lead to decrease in d[v]!
  270.         if (y == s) dist[y] = G.number_of_nodes();
  271.            }
  272.  
  273.          }  //forall (e,...)
  274.  
  275.      }  //while (x == bfs_Q.pop())
  276.  
  277. }  //end gt_bfs2
  278.  
  279.  
  280.  
  281.  
  282.  
  283.  
  284. #ifndef NO_REAL_GRAPH_ALG
  285.  
  286.  
  287. static
  288. void gt_bfs1(node s_vert, int dist_s_vert, 
  289.              const graph& G, node s, const edge_array(real)& cap,
  290.              edge_array(real)& flow, node_array(int)& dist);
  291.  
  292.  
  293.  
  294. real MAX_FLOW(graph& G, node s, node t, const edge_array(real)& cap, 
  295.                                               edge_array(real)& flow) 
  296. {
  297. int heuristic = 1;
  298.  
  299. /* Computes a maximum flow from source s to sink t, using
  300.    Goldberg-Tarjan algorithm [Journal ACM 35 (Oct 1988) p921-940].
  301.    ( Applies push steps to vertices with positive preflow, based on 
  302.      distance labels.  Uses FIFO rule (implemented by FIFO queue) 
  303.      for selecting a vertex with +ve preflow. )
  304.  
  305.    input:   cap[e]  gives capacity of edge e 
  306.  
  307.             heuristic == parameter for heuristic suggested by Goldberg
  308.              to speed up algorithm 
  309.             0 == no heuristic
  310.             1 == compute exact distance labels after every N relabel steps
  311.            +i == compute exact distance labels after every N*i relabel steps
  312.            -i == compute exact distance labels after every N/i relabel steps
  313.  
  314.    output:  flow[e] flow on edge e
  315.         heuristic = number of relabels
  316.  
  317.             returns total flow into sink
  318.  
  319.    node_arrays used by the algorithm:
  320.    dist[v]   = lower bound on shortest distance from v to t
  321.    excess[v] = (total incoming preflow[v]) - (total outgoing preflow[v])
  322.  
  323.    Implemented by  Joseph Cheriyan & Stefan Naeher.
  324. */
  325.  
  326.  
  327.  
  328. node_array(int)       dist(G,0);
  329. node_array(real)      excess(G,0);
  330.  
  331. list(node) U;     // FIFO Queue used for selecting vertex with +ve preflow
  332. node     v,w;
  333. edge     e;
  334.  
  335. G.make_undirected();
  336.  
  337. int N = G.number_of_nodes();
  338.  
  339. int num_relabels = 0;
  340.  
  341. if (heuristic < -N || heuristic > N) 
  342.     heuristic = 0;
  343. else
  344.     heuristic = ((heuristic >= 0) ? N*heuristic : N/(-heuristic));
  345.  
  346. int  limit_heur = heuristic;
  347.  
  348. if (s == t) error_handler(1,"gt_max_flow: source == sink");
  349.  
  350. forall_edges(e,G)  flow[e] = 0;
  351.  
  352. forall_adj_edges(e,s)
  353. if (source(e) == s)
  354.   { v = target(e);
  355.     flow[e] = cap[e];
  356.     excess[v] += flow[e];
  357.     if (v!=s && v!=t) U.append(v);
  358.   }
  359.  
  360. dist[s] = N;
  361.  
  362. while (! U.empty() )      /* main loop */
  363. { 
  364.   v = U.pop();
  365.  
  366.   real delta;
  367.  
  368.   while ((excess[v] > 0) && G.next_adj_edge(e,v))
  369.     { // push flow along each edge e = (v,w) in the residual graph with
  370.       // dist[v] == dist[w] + 1
  371.   
  372.       if (v == source(e))
  373.       { w = target(e);
  374.         real d = cap[e] - flow[e];
  375.         delta = Min(d,excess[v]);
  376.         if ((dist[v]==dist[w]+1) && (delta > 0) && (dist[v] < N))
  377.         // pushes towards s that increase flow[e] are not allowed
  378.         { if ((excess[w] == 0) && (w != t)) U.append(w);
  379.           flow[e] += delta;
  380.           excess[w] += delta;
  381.           excess[v] -= delta;
  382.          }
  383.        }
  384.       else
  385.       { w = source(e);
  386.         delta = Min(flow[e],excess[v]);
  387.         if ((dist[v] == dist[w]+1) && (delta > 0))
  388.         { if ((excess[w] == 0) && (w != t) && (w != s)) U.append(w);
  389.           flow[e] -= delta;
  390.           excess[w] += delta;
  391.           excess[v] -= delta;
  392.          }
  393.        }
  394.   
  395.     }  // while ( (excess[v] > 0) && ...)
  396.   
  397.   
  398.   if (excess[v] > 0)
  399.   {
  400.     // relabel vertex v (i.e. update dist[v]) because all
  401.     // admissible edges in the residual graph have been saturated 
  402.  
  403.     num_relabels++;
  404.   
  405.     if ( heuristic 
  406.         && (num_relabels == limit_heur))
  407.     {
  408.       limit_heur += heuristic;
  409.  
  410.       // heuristic suggested by Goldberg to reduce number of relabels:
  411.       // periodically compute exact dist[] labels by two backward bfs 
  412.       // one starting at t and another starting at s
  413.  
  414.      node x;
  415.  
  416.      forall_nodes(x,G)
  417.      dist[x] = Infinity;
  418.  
  419.      gt_bfs1(t,0,G,s,cap,flow,dist);
  420.      gt_bfs1(s,N,G,s,cap,flow,dist);
  421.  
  422.     }
  423.                   
  424.     else
  425.    
  426.     {
  427.      int min_dist = Infinity;
  428.      forall_adj_edges(e,v)
  429.        {
  430.          real r = cap[e] - flow[e];
  431.  
  432.          if ((source(e) == v) && (r > 0) && (dist[v] < N))
  433.            //pushes towards s that increase flow[e] are not allowed
  434.            min_dist = Min(min_dist,dist[target(e)]);
  435.  
  436.  
  437.          if ((target(e) == v) && (flow[e] > 0))
  438.            min_dist = Min(min_dist,dist[source(e)]);
  439.         }
  440.       if (min_dist != Infinity) min_dist++;
  441.       dist[v] = min_dist;
  442.  
  443.      } // else
  444.          
  445.       U.push(v);
  446.       G.init_adj_iterator(v);
  447.      
  448.     } // if (excess[v] > 0)
  449.  
  450.  }  // while (!U.empty())  
  451.        
  452.    
  453.  
  454. //code to verify that flow is legal
  455.  
  456. /*
  457.  
  458. real tot_s_flow = 0;
  459. forall_adj_edges(e,s)  
  460.    if (source(e) == s)   tot_s_flow += cap[e];
  461. if (tot_s_flow != (excess[s] + excess[t]))
  462.  { cout << "gt_max_flow: total out cap s != excess[s] + excess[t]\n";
  463.    forall_nodes(v,G)
  464.      if ((excess[v] != 0) && (v != t) && (v != s))
  465.       cout << "gt_max_flow: v!=s,t has excess[v]=" << excess[v] << "\n";
  466.   }
  467.  
  468. */
  469.  
  470. G.make_directed();
  471.  
  472. heuristic = num_relabels;
  473.  
  474. real result = excess[t];  //returns value of maximum flow from s to t
  475.  
  476. return result; 
  477.   
  478. } // procedure gt_max_flow
  479.  
  480.  
  481. //procedure to perform backward bfs starting at vertex s_vert with 
  482. //distance label dist_s_vert
  483.  
  484. static
  485. void gt_bfs1(node s_vert, int dist_s_vert,
  486.             const graph& G, node s, const edge_array(real)& cap,
  487.             edge_array(real)& flow, node_array(int)& dist)
  488. {
  489.   node x,y;
  490.   edge e;
  491.   list(node) bfs_Q;
  492.   real c;
  493.  
  494.   dist[s_vert] = dist_s_vert;
  495.   bfs_Q.append(s_vert);
  496.   while (x = bfs_Q.pop())
  497.     {
  498.       forall_adj_edges(e,x)
  499.         {
  500.           if (x == source(e)) 
  501.         { y = target(e); 
  502.                   c = flow[e]; }
  503.           else 
  504.         { y = source(e); 
  505.                   c = cap[e] - flow[e]; }
  506.  
  507.           if ( c > 0  && dist[y] == Infinity
  508.                       && !(x == target(e) && (s_vert == s)) )
  509.           // while doing bfs with s_vert==s, 
  510.           // only edges with flow[e]>0 are reachable from s
  511.  
  512.           { dist[y] = dist[x] + 1;
  513.             bfs_Q.append(y);
  514.             G.init_adj_iterator(y);
  515.  
  516.         //next statement is not really needed, but is added for
  517.         //protection, to ensure that s does not get relabelled by
  518.         //bfs starting at t; this may lead to decrease in d[v]!
  519.         if (y == s) dist[y] = G.number_of_nodes();
  520.            }
  521.  
  522.          }  //forall(e,...)
  523.  
  524.      }  //while(x == bfs_Q.pop())
  525.  
  526. }  //end procedure gt_bfs1
  527.  
  528.  
  529. #endif
  530.