home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / graph_al / _mcb_mat.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  3.0 KB  |  122 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _mcb_matching.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. *                                                                              *
  19. *  MAX_CARD_BIPARTITE_MATCHING  (maximum cardinality bipartite matching)       *
  20. *                                                                              *
  21. *******************************************************************************/
  22.  
  23.  
  24.  
  25. #include <LEDA/graph_alg.h>
  26.  
  27. edge find_next_augmenting_path(graph&,node, node, node_array(edge)&, node_array(int)&);
  28. /* defined later */
  29.  
  30. list(edge) MAX_CARD_BIPARTITE_MATCHING(graph& G, const list(node)& A, 
  31.                                                  const list(node)& B )
  32. { // G is a bipartite graph with sides A and B, all edges must be directed 
  33.   // from A to B. We compute a matching of maximum cardinality using the 
  34.   // algorithm of Hopcroft and Karp. The running time is O(sqrt(n)*m).
  35.  
  36. node v;
  37. edge e;
  38.  
  39. forall(v,B) 
  40.    forall_adj_edges(e,v) 
  41.       { error_handler(0,"mcb_matching: edge from B to A (deleted).");
  42.         G.del_edge(e);  
  43.        }
  44.  
  45. node s = G.new_node("s");
  46. node t = G.new_node("t");
  47.  
  48. forall(v,A) G.new_edge(s,v);
  49. forall(v,B) G.new_edge(v,t);
  50.  
  51. node_array(edge) pred(G,0); 
  52. node_array(int)  layer(G,0);
  53. list(edge) EL;
  54. list(node) L;
  55.  
  56. G.reset();
  57.  
  58. for(;;)
  59. { forall_nodes(v,G) { layer[v] = -1; pred[v] = 0; }
  60.  
  61.   L = BFS(G,s,layer);
  62.  
  63.   if (layer[t]>=0)  // there is at least one augmenting path
  64.    { while (e = find_next_augmenting_path(G,s,t,pred,layer)) EL.append(e); 
  65.  
  66.      G.reset();
  67.      while (e=EL.pop())
  68.        { edge x = pred[source(e)];
  69.          while (source(x) != s)
  70.            { G.rev_edge(x);
  71.              x=pred[target(x)];
  72.             }
  73.          G.del_edge(e);  // edge into t
  74.          G.del_edge(x);  // edge out of s
  75.         } 
  76.     }
  77.   else break;
  78. } 
  79.  
  80. list(edge) result;
  81.  
  82. forall(v,B) 
  83.    forall_adj_edges(e,v) 
  84.       if (target(e) != t) 
  85.         result.append(e);
  86.       else
  87.         EL.append(e);
  88.  
  89. //restore graph:
  90. forall(e,EL) G.del_edge(e);
  91. forall(e,result) G.rev_edge(e);
  92. G.del_node(s);
  93. G.del_node(t);
  94.  
  95. return result;
  96. }
  97.  
  98.  
  99. // edges in the layered network are called eligible:
  100. #define ELIGIBLE(e)\
  101. (layer[target(e)]==layer[source(e)]+1) && (layer[target(e)]<=layer[t])
  102.  
  103.  
  104. edge find_next_augmenting_path(graph& G, node s, node t, node_array(edge)& pred, 
  105.                                          node_array(int)&  layer)
  106. { node w;
  107.   edge e;
  108.   edge f=0;
  109.  
  110.   while (f==0 && G.next_adj_edge(e,s))
  111.     if (ELIGIBLE(e))
  112.       if ((w=target(e))==t) f=e;              // t is reached
  113.       else  if (pred[w]==0)                   // w not reached before 
  114.             { pred[w] = e;
  115.               f = find_next_augmenting_path(G,w,t,pred,layer);
  116.              }
  117.   return f;
  118. } 
  119.  
  120.  
  121.  
  122.