home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / graph_al / _mc_matc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  7.9 KB  |  347 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _mc_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. *  MAX_CARD_MATCHING  (maximum cardinality matching)                           *
  19. *                                                                              *
  20. *  Edmond's Algorithm (running time O(n*m*alpha(n)) )                          *
  21. *                                                                              *
  22. *  S. Naeher (October 1991)                                                    *
  23. *                                                                              *
  24. *******************************************************************************/
  25.  
  26.  
  27. #include <LEDA/graph_alg.h>
  28. #include <LEDA/node_partition.h>
  29.  
  30. declare(node_array,node)
  31.  
  32. static void find_path(list(node)& L, node_array(int)&   label,
  33.                                      node_array(node)&  pred,
  34.                                      node_array(node)&  mate,
  35.                                      node_array(edge)&  bridge,
  36.                                      node x, node y);
  37.  
  38. enum LABEL {ODD, EVEN, UNREACHED};
  39.  
  40. static graph* GP;
  41.  
  42. static int cmp_degree(node& v,node& w) { return GP->indeg(v) - GP->indeg(w); }
  43.  
  44.  
  45. list(edge) MAX_CARD_MATCHING(graph& G, bool report_blossoms)
  46. { 
  47.  
  48.   // input: directed graph G, we make it undirected (symmetric) by inserting
  49.   //        reversal edges
  50.  
  51.  
  52.   list(edge) R;
  53.  
  54.   int    strue = 0;
  55.   bool   done  = false;
  56.  
  57.   node_array(int)  label(G,UNREACHED);
  58.   node_array(node) pred(G,nil);
  59.   node_array(node) mate(G,nil);
  60.   node_array(int)  path1(G,0);
  61.   node_array(int)  path2(G,0);
  62.   node_array(edge) bridge(G,nil);
  63.   edge_array(edge) rev(G,nil);
  64.  
  65.   GP = &G;
  66.  
  67.  
  68.   // make graph symmetric
  69.  
  70.   compute_correspondence(G,rev);
  71.  
  72.   edge e;
  73.  
  74.   list(edge) E = G.all_edges();
  75.  
  76.   forall(e,E) 
  77.     if (rev[e] == nil)
  78.       { rev[e] = G.new_edge(target(e),source(e));
  79.         R.append(rev[e]);
  80.        }
  81.  
  82.   edge_array(edge) reversal(G);
  83.  
  84.   forall(e,E)
  85.   { reversal[e] = rev[e];
  86.     reversal[rev[e]] = e;
  87.    }
  88.  
  89.   G.sort_nodes(cmp_degree);  // sort nodes by degree
  90.  
  91.  
  92.   forall_edges(e,G)          // greedy
  93.   { node v = source(e);
  94.     node w = target(e);
  95.  
  96.     if (v != w && mate[v] == nil && mate[w] == nil) 
  97.     { mate[v] = w;
  98.       mate[w] = v;
  99.      }
  100.    }
  101.  
  102.   while (! done)  /* main loop */
  103.   {
  104.     list(node) Q;
  105.     node v;
  106.  
  107.     node_partition base(G);    // now base(v) = v for all nodes v
  108.  
  109.     done = true;
  110.    
  111.     forall_nodes(v,G)
  112.     { pred[v] = nil;
  113.   
  114.       if (mate[v] == nil)
  115.       { label[v] = EVEN; 
  116.         Q.append(v); 
  117.        }
  118.       else label[v] = UNREACHED;
  119.     }
  120.   
  121.     while (!Q.empty())    // search for augmenting path
  122.     {
  123.       node v = Q.pop();
  124.       edge e;
  125.  
  126.       forall_adj_edges(e,v)
  127.       {
  128.         node w = G.target(e);
  129.  
  130.         if (v == w) continue;    // ignore loops
  131.  
  132.         if (base(v) == base(w) || (label[w] == ODD && base(w) == w)) 
  133.         continue;   // do nothing
  134.  
  135.         if (label[w] == UNREACHED)
  136.         { label[w] = ODD;
  137.           pred[w] = v;
  138.           label[mate[w]] = EVEN;
  139.           Q.append(mate[w]);
  140.          }
  141.         else  // base(v) != base(w) && (label[w] == EVEN || base(w) !=w)
  142.         { 
  143.           node hv = base(v);
  144.           node hw = base(w);
  145.   
  146.           strue++;
  147.           path1[hv] = path2[hw] = strue;
  148.   
  149.           while ((path1[hw] != strue && path2[hv] != strue) &&
  150.                  (mate[hv] != nil || mate[hw] != nil) )
  151.           {
  152.             if (mate[hv] != nil)
  153.             { hv = base(pred[mate[hv]]);
  154.               path1[hv] = strue;
  155.              }
  156.   
  157.             if (mate[hw] != nil)
  158.             { hw = base(pred[mate[hw]]);
  159.               path2[hw] = strue;
  160.              }
  161.            }
  162.   
  163.           if (path1[hw] == strue || path2[hv] == strue)  // Shrink Blossom
  164.           { node x;
  165.             node y;
  166.             node b = (path1[hw] == strue) ? hw : hv;    // Base
  167.  
  168. if (report_blossoms)
  169. { cout << "SHRINK BLOSSOM\n";
  170.   cout << "bridge = "; 
  171.   G.print_edge(e);
  172.   newline;
  173.   cout << "base   = "; 
  174.   G.print_node(b);
  175.   newline;
  176.   cout << "path1  = ";
  177. }
  178.  
  179.             x = base(v);
  180.             while (x != b)
  181.             { 
  182.  
  183. if (report_blossoms)
  184. { G.print_node(x); 
  185.   cout << " ";
  186.  }
  187.               base.union_blocks(x,b);
  188.               base.set_inf(b,b);
  189.  
  190.               x = mate[x];
  191.  
  192. if (report_blossoms)
  193. { G.print_node(x); 
  194.   cout << " ";
  195.  }
  196.               y = base(pred[x]);
  197.               base.union_blocks(x,b);
  198.               base.set_inf(b,b);
  199.  
  200.               Q.append(x);
  201.  
  202.               bridge[x] = e;
  203.               x = y;
  204.              }
  205.  
  206. if (report_blossoms)
  207. { G.print_node(b);
  208.   newline;
  209.   cout << "path2  = ";
  210.  }
  211.  
  212.             x = base(w);
  213.             while (x != b)
  214.             { 
  215.  
  216. if (report_blossoms)
  217. { G.print_node(x); 
  218.   cout << " ";
  219.  }
  220.               base.union_blocks(x,b);
  221.               base.set_inf(b,b);
  222.  
  223.               x = mate[x];
  224.  
  225. if (report_blossoms)
  226. { G.print_node(x); 
  227.   cout << " ";
  228.  }
  229.               y = base(pred[x]);
  230.  
  231.               base.union_blocks(x,b);
  232.               base.set_inf(b,b);
  233.  
  234.               Q.append(x);
  235.  
  236.               bridge[x] = reversal[e];
  237.  
  238.               x = y;
  239.              }
  240.  
  241. if (report_blossoms)
  242. { G.print_node(b);
  243.   newline;
  244.   newline;
  245.  }
  246.           }
  247.           else  // augment path
  248.           {
  249.             list(node) P[2];
  250.  
  251.             find_path(P[0],label,pred,mate,bridge,v,hv);
  252.             P[0].push(w);
  253.             find_path(P[1],label,pred,mate,bridge,w,hw);
  254.             P[1].pop();
  255.  
  256. //cout << "augment path: ";
  257.  
  258.             for(int i=0; i<2; i++)
  259.               while(! P[i].empty())
  260.                { node a = P[i].pop();
  261.                  node b = P[i].pop();
  262.                  mate[a] = b;
  263.                  mate[b] = a;
  264. //G.print_node(a); 
  265. //cout << " "; 
  266. //G.print_node(b); 
  267. //cout << " ";
  268.                 }
  269. //newline;
  270. //newline;
  271.              Q.clear();                /* stop search (while Q not empty) */
  272.              done = false;             /* continue main loop              */
  273.              G.init_adj_iterator(v);
  274.              break;                    /* forall_adj_edges(e,v) ...       */
  275.            }
  276.  
  277.         } // base(v) != base(w) && (label[w] == EVEN || base(w) !=w)
  278.   
  279.       } // for all adjacent edges
  280.   
  281.     } // while Q not empty
  282.  
  283.   } // while not done
  284.  
  285.  
  286.  forall(e,R) G.del_edge(e);  // restore graph (only original edges in result!)
  287.  
  288.  list(edge) result;
  289.  
  290.  forall_edges(e,G) 
  291.  { node v = source(e);
  292.    node w = target(e);
  293.    if ( v != w  &&  mate[v] == w ) 
  294.    { result.append(e);
  295.      mate[v] = v;
  296.      mate[w] = w;
  297.    }
  298.  }
  299.  
  300.  
  301.  return result;
  302.  
  303. }
  304.  
  305.  
  306.  
  307. void find_path(list(node)& L, node_array(int)&  label,
  308.                               node_array(node)& pred,
  309.                               node_array(node)& mate,
  310.                               node_array(edge)& bridge,
  311.                               node x, node y)
  312. {
  313.   /* computes an even length alternating path from x to y begining with a 
  314.      matching edge (Tarjan: Data Structures and Network Algorithms, page 122)
  315.      Preconditions: 
  316.      a) x and y are even or shrinked
  317.      b) when x was made part of a blossom for the first time, y was a base 
  318.         and predecessor of the base of that blossom
  319.    */
  320.  
  321.  if (x==y) 
  322.  { // [ x ]
  323.    L.append(x);
  324.    return;
  325.   }
  326.  
  327.  if (label[x] == EVEN) 
  328.  { // [ x --> mate[x] --> path(pred[mate[x]],y) ]
  329.    find_path(L,label,pred,mate,bridge,pred[mate[x]],y);
  330.    L.push(mate[x]);
  331.    L.push(x);
  332.    return;
  333.  }
  334.  
  335.  if (label[x] == ODD) 
  336.  { // [ x --> REV(path(source(bridge),mate[x])) --> path(target(bridge),y)) ]
  337.    node v;
  338.    list(node) L1;
  339.    find_path(L,label,pred,mate,bridge,target(bridge[x]),y);
  340.    find_path(L1,label,pred,mate,bridge,source(bridge[x]),mate[x]);
  341.    forall(v,L1) L.push(v);
  342.    L.push(x);
  343.    return;
  344.   }
  345. }
  346.  
  347.