home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / graph_al / _mwb_mat.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  4.4 KB  |  222 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _mwb_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_WEIGHT_BIPARTITE_MATCHING  (maximum weight bipartite matching)          *
  20. *                                                                              *
  21. *******************************************************************************/
  22.  
  23.  
  24.  
  25. #include <LEDA/graph_alg.h>
  26.  
  27.  
  28. // for integer edge weights:
  29.  
  30. list(edge) MAX_WEIGHT_BIPARTITE_MATCHING (graph& G, 
  31.                                           const list(node)& A, 
  32.                                           const list(node)& B, 
  33.                                           const edge_array(int)& weight )
  34.  
  35. { 
  36.  
  37. node v;
  38. edge e;
  39.  
  40. forall(v,B) 
  41.   forall_adj_edges(e,v)
  42.    { error_handler(0,"mwb_matching: edge from B to A (deleted)");
  43.      G.del_edge(e);
  44.     }
  45.  
  46. node s = G.new_node();
  47.  
  48. node_array(int)  dist(G);
  49. node_array(int)  u(G,0);
  50. node_array(edge) pred(G);
  51.  
  52.  
  53. forall(v,A) 
  54.   { int m = 0;
  55.     forall_adj_edges(e,v) if (weight[e] > m) m = weight[e];
  56.     if (m > 0)  G.new_edge(s,v);
  57.     u[v] = m;
  58.    }
  59.  
  60. edge_array(int)  p(G,0);
  61.  
  62.  
  63. while (outdeg(s) > 0)
  64. { 
  65.   forall_edges(e,G) 
  66.   { p[e] = u[source(e)] + u[target(e)]; 
  67.     if (source(e) != s) p[e] -= weight[e];
  68.    }
  69.  
  70.   DIJKSTRA(G,s,p,dist,pred);
  71.  
  72.   node j0,i0;
  73.   int min_A = Infinity; 
  74.   int min_B = Infinity;
  75.  
  76.   forall(v,B) 
  77.    { int x = dist[v];
  78.  
  79.      if ( outdeg(v)==0 && x < min_A ) 
  80.       { j0 = v; 
  81.         min_A = x;
  82.        }
  83.  
  84.     }
  85.  
  86.   forall(v,A) 
  87.    { int x = dist[v];
  88.      int y = x+u[v];
  89.  
  90.      if ( x < Infinity && y < min_B ) 
  91.       { i0 = v; 
  92.         min_B = y;
  93.        }
  94.  
  95.     }
  96.  
  97.   node k0 = j0; 
  98.   int d = min_A;
  99.   if (min_A > min_B) { k0 = i0; d = min_B; }
  100.  
  101.   forall(v,A) if (d > dist[v]) u[v] -= d-dist[v];
  102.   forall(v,B) if (d > dist[v]) u[v] += d-dist[v];
  103.  
  104.   if (e = pred[k0])
  105.    { while (source(e) != s)
  106.        { G.rev_edge(e);      /* "source(e) heisst jetzt target(e)" */
  107.          e=pred[target(e)];
  108.         }
  109.      G.del_edge(e);
  110.     }
  111. }
  112.  
  113. edgelist result;
  114. forall(v,B) forall_adj_edges(e,v) result.append(e);
  115.  
  116. // restore graph
  117. G.del_node(s);
  118. forall(e,result) G.rev_edge(e);
  119.  
  120. return result;
  121. }
  122.  
  123.  
  124.  
  125.  
  126. #ifndef NO_REAL_GRAPH_ALG
  127.  
  128. // for real edge weights:
  129.  
  130. list(edge) MAX_WEIGHT_BIPARTITE_MATCHING (graph& G, 
  131.                                           const list(node)& A, 
  132.                                           const list(node)& B, 
  133.                                           const edge_array(real)& weight )
  134.  
  135. { 
  136.  
  137. node v;
  138. edge e;
  139.  
  140. forall(v,B) 
  141.   forall_adj_edges(e,v)
  142.    { error_handler(0,"mwb_matching: edge from B to A (deleted)");
  143.      G.del_edge(e);
  144.     }
  145.  
  146. node s = G.new_node();
  147.  
  148. node_array(real)  dist(G);
  149. node_array(real)  u(G,0);
  150. node_array(edge) pred(G);
  151.  
  152.  
  153. forall(v,A) 
  154.   { real m = 0;
  155.     forall_adj_edges(e,v) if (weight[e] > m) m = weight[e];
  156.     if (m > 0)  G.new_edge(s,v);
  157.     u[v] = m;
  158.    }
  159.  
  160. edge_array(real)  p(G,0);
  161.  
  162. // edge_array(real)  w(G,0);
  163. // forall_edges(e,G) if (source(e)!=s) w[e] = weight[e];
  164.  
  165.  
  166. while (outdeg(s) > 0)
  167. { 
  168.  
  169.   /* forall_edges(e,G) p[e] = u[source(e)] + u[target(e)] - w[e]; */ 
  170.  
  171.   forall_edges(e,G) 
  172.   { p[e] = u[source(e)] + u[target(e)]; 
  173.     if (source(e) != s) p[e] -= weight[e];
  174.    }
  175.  
  176.   DIJKSTRA(G,s,p,dist,pred);
  177.  
  178.   node j0,i0;
  179.   real min_A = Infinity; 
  180.   real min_B = Infinity;
  181.  
  182.   forall(v,B) 
  183.     if ((outdeg(v)==0)&&(dist[v] < min_A)) 
  184.      { j0 = v; 
  185.        min_A = dist[v];
  186.       }
  187.  
  188.   forall(v,A) 
  189.     if (dist[v] < Infinity && (dist[v]+u[v]) < min_B) 
  190.      { i0 = v; 
  191.        min_B = dist[v] + u[v]; 
  192.       }
  193.  
  194.   node k0 = j0; 
  195.   real d = min_A;
  196.   if (min_A > min_B) { k0 = i0; d = min_B; }
  197.  
  198.   forall(v,A) if (d > dist[v]) u[v] -= d-dist[v];
  199.   forall(v,B) if (d > dist[v]) u[v] += d-dist[v];
  200.  
  201.   if (e = pred[k0])
  202.    { while (source(e) != s)
  203.        { G.rev_edge(e);      /* "source(e) heisst jetzt target(e)" */
  204.          e=pred[target(e)];
  205.         }
  206.      G.del_edge(e);
  207.     }
  208. }
  209.  
  210. edgelist result;
  211. forall(v,B) forall_adj_edges(e,v) result.append(e);
  212.  
  213. // restore graph
  214. G.del_node(s);
  215. forall(e,result) G.rev_edge(e);
  216.  
  217. return result;
  218. }
  219.  
  220.  
  221. #endif
  222.