Guest User

Untitled

a guest
Feb 6th, 2011
2,056
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.   Edmonds's maximum matching algorithm
  3.   Complexity: O(v^3)
  4.   Written by Felipe Lopes de Freitas
  5. */
  6. #include <stdio.h>
  7. #define MAX 100
  8. #define undef -2
  9. #define empty -1
  10. #define noEdge 0
  11. #define unmatched 1
  12. #define matched 2
  13. #define forward 0
  14. #define reverse 0
  15.  
  16.                     //Labels are the key to this implementation of the algorithm.
  17. struct Label {      //An even label in a vertex means there's an alternating path
  18.        int even;    //of even length starting from the root node that ends on the
  19.        int odd[2];  //vertex. To find this path, the backtrace() function is called,
  20. };                  //constructing the path by following the content of the labels.
  21.                     //Odd labels are similar, the only difference is that base nodes
  22.                     //of blossoms inside other blossoms may have two. More on this later.
  23.  
  24.  
  25. struct elem {            //This is the element of the queue of labels to be analyzed by
  26.        int vertex,type;  //the augmentMatching() procedure. Each element contains the vertex
  27. };                       //where the label is and its type, odd or even.
  28.  
  29.  
  30. int g[MAX][MAX];         //The graph, as an adjacency matrix.
  31.  
  32.                          //blossom[i] contains the base node of the blossom the vertex i
  33. int blossom[MAX];        //is in. This, together with labels eliminates the need to
  34.                          //contract the graph.
  35.  
  36.                               //The path arrays are where the backtrace() routine will
  37. int path[2][MAX],endPath[2];  //store the paths it finds. Only two paths need to be
  38.                               //stored. endPath[p] denotes the end of path[p].
  39.  
  40. bool match[MAX];  //An array of flags. match[i] stores if vertex i is in the matching.
  41.  
  42.                   //label[i] contains the label assigned to vertex i. It may be undefined,
  43. Label label[MAX]; //empty (meaning the node is a root) and a node might have even and odd
  44.                   //labels at the same time, which is the case for nonbase nodes of blossoms
  45.  
  46. elem queue[2*MAX];         //The queue is necessary for efficiently scanning all labels.
  47. int queueFront,queueBack;  //A label is enqueued when assigned and dequeued after scanned.
  48.  
  49. void initGraph(int n){
  50.      for (int i=0; i<n; i++)
  51.          for (int j=0; j<n; j++) g[i][j]=noEdge;
  52. }
  53.  
  54. int readGraph(){
  55.      int n,e,a,b;
  56.      scanf(" %d %d",&n,&e);      //The graph is read and its edges are unmatched by default.
  57.      initGraph(n);               //Since C++ arrays are 0..n-1 and input 1..n , subtractions
  58.      for (int i=0; i<e; i++){    //are made for better memory usage.
  59.          scanf(" %d %d",&a,&b);
  60.          if (a!=b)
  61.             g[a-1][b-1]=g[b-1][a-1]=unmatched;
  62.      }
  63.      return n;
  64. }
  65.  
  66. void initAlg(int n){             //Initializes all data structures for the augmentMatching()
  67.      queueFront=queueBack=0;     //function begin. At the start, all labels are undefined,
  68.      for (int i=0; i<n; i++){    //the queue is empty and a node alone is its own blossom.
  69.          blossom[i]=i;
  70.          label[i].even=label[i].odd[0]=label[i].odd[1]=undef;
  71.      }
  72. }
  73.  
  74. void backtrace (int vert, int pathNum, int stop, int parity, int direction){
  75.      if (vert==stop) return;           //pathNum is the number of the path to store
  76.      else if (parity==0){              //vert and parity determine the label to be read.
  77.         if (direction==reverse){
  78.            backtrace(label[vert].even,pathNum,stop,(parity+1)%2,reverse);
  79.            path[pathNum][endPath[pathNum]++]=vert;
  80.         }                             //forward means the vertices called first enter
  81.         else if (direction==forward){ //the path first, reverse is the opposite.
  82.              path[pathNum][endPath[pathNum]++]=vert;
  83.              backtrace(label[vert].even,pathNum,stop,(parity+1)%2,forward);
  84.         }
  85.      }
  86.      /*
  87.        stop is the stopping condition for the recursion.
  88.        Recursion is necessary because of the possible dual odd labels.
  89.        having empty at stop means the recursion will only stop after
  90.        the whole tree has been climbed. If assigned to a vertex, it'll stop
  91.        once it's reached.
  92.      */
  93.      else if (parity==1 && label[vert].odd[1]==undef){
  94.         if (direction==reverse){
  95.            backtrace(label[vert].odd[0],pathNum,stop,(parity+1)%2,reverse);
  96.            path[pathNum][endPath[pathNum]++]=vert;
  97.         }
  98.         else if (direction==forward){
  99.              path[pathNum][endPath[pathNum]++]=vert;
  100.              backtrace(label[vert].odd[0],pathNum,stop,(parity+1)%2,forward);
  101.         }
  102.      }
  103.      /*
  104.        Dual odd labels are interpreted as follows:
  105.        There exists an odd length alternating path starting from the root to this
  106.        vertex. To find this path, backtrace from odd[0] to the top of the tree and
  107.        from odd[1] to the vertex itself. This, put in the right order, will
  108.        constitute said path.
  109.      */
  110.      else if (parity==1 && label[vert].odd[1]!=undef){
  111.           if (direction==reverse){
  112.              backtrace(label[vert].odd[0],pathNum,empty,(parity+1)%2,reverse);
  113.              backtrace(label[vert].odd[1],pathNum,vert,(parity+1)%2,forward);
  114.              path[pathNum][endPath[pathNum]++]=vert;
  115.           }
  116.           else if (direction==forward){
  117.                backtrace(label[vert].odd[1],pathNum,vert,(parity+1)%2,reverse);
  118.                backtrace(label[vert].odd[0],pathNum,empty,(parity+1)%2,forward);
  119.                path[pathNum][endPath[pathNum]++]=vert;
  120.           }
  121.      }
  122. }
  123.  
  124. void enqueue (int vert, int t){
  125.      elem tmp;               //Enqueues labels for scanning.
  126.      tmp.vertex=vert;        //No label that's dequeued during the execution
  127.      tmp.type=t;             //of augmentMatching() goes back to the queue.
  128.      queue[queueBack++]=tmp; //Thus, circular arrays are unnecessary.
  129. }
  130.  
  131. void newBlossom (int a, int b){     //newBlossom() will be called after the paths are evaluated.
  132.      int i,base,innerBlossom,innerBase;
  133.      for (i=0; path[0][i]==path[1][i]; i++);   //Find the lowest common ancestor of a and b
  134.      i--;                                      //it will be used to represent the blossom.
  135.      base=blossom[path[0][i]];                 //Unless it's already contained in another...
  136.                                                //In this case, all will be put in the older one.
  137.      for (int j=i; j<endPath[0]; j++) blossom[path[0][j]]=base;
  138.      for (int j=i+1; j<endPath[1]; j++) blossom[path[1][j]]=base; //Set all nodes to this
  139.      for (int p=0; p<2; p++){                                     //new blossom.
  140.         for (int j=i+1; j<endPath[p]-1; j++){
  141.             if (label[path[p][j]].even==undef){        //Now, new labels will be applied
  142.                label[path[p][j]].even=path[p][j+1];    //to indicate the existence of even
  143.                enqueue(path[p][j],0);                  //and odd length paths.
  144.             }
  145.             else if (label[path[p][j]].odd[0]==undef && label[path[p][j+1]].even==undef){
  146.                  label[path[p][j]].odd[0]=path[p][j+1];
  147.                  enqueue(path[p][j],1);                 //Labels will only be put if the vertex
  148.             }                                           //doesn't have one.
  149.            
  150.             else if (label[path[p][j]].odd[0]==undef && label[path[p][j+1]].even!=undef){
  151.                  /*
  152.                    If a vertex doesn't have an odd label, but the next one in the path
  153.                    has an even label, it means that the current vertex is the base node
  154.                    of a previous blossom and the next one is contained within it.
  155.                    The standard labeling procedure will fail in this case. This is fixed
  156.                    by going to the last node in the path inside this inner blossom and using
  157.                    it to apply the dual label.
  158.                    Refer to backtrace() to know how the path will be built.
  159.                  */
  160.                  innerBlossom=blossom[path[p][j]];
  161.                  innerBase=j;
  162.                  for (; blossom[j]==innerBlossom && j<endPath[p]-1; j++);
  163.                  j--;
  164.                  label[path[p][innerBase]].odd[0]=path[p][j+1];
  165.                  label[path[p][innerBase]].odd[1]=path[p][j];
  166.                  enqueue(path[p][innerBase],1);
  167.             }
  168.         }
  169.      }
  170.      if (g[a][b]==unmatched){           //All nodes have received labels, except
  171.         if (label[a].odd[0]==undef){    //the ones that called the function in
  172.            label[a].odd[0]=b;           //the first place. It's possible to
  173.            enqueue(a,1);                //find out how to label them by
  174.         }                               //analyzing if they're in the matching.
  175.         if (label[b].odd[0]==undef){
  176.            label[b].odd[0]=a;
  177.            enqueue(b,1);
  178.         }                              
  179.      }
  180.      else if (g[a][b]==matched){
  181.           if (label[a].even==undef){
  182.              label[a].even=b;
  183.              enqueue(a,0);
  184.           }
  185.           if (label[b].even==undef){
  186.              label[b].even=a;
  187.              enqueue(b,0);
  188.           }
  189.      }
  190. }
  191.  
  192. void augmentPath (){           //An augmenting path has been found in the matching
  193.      int a,b;                  //and is contained in the path arrays.
  194.      for (int p=0; p<2; p++){
  195.          for (int i=0; i<endPath[p]-1; i++){
  196.              a=path[p][i];             //Because of labeling, this path is already
  197.              b=path[p][i+1];           //lifted and can be augmented by simple
  198.              if (g[a][b]==unmatched)   //changing of the matching status.
  199.                 g[a][b]=g[b][a]=matched;
  200.              else if (g[a][b]==matched)
  201.                   g[a][b]=g[b][a]=unmatched;
  202.          }
  203.      }
  204.      a=path[0][endPath[0]-1];
  205.      b=path[1][endPath[1]-1];
  206.      if (g[a][b]==unmatched) g[a][b]=g[b][a]=matched;
  207.      else if (g[a][b]==matched) g[a][b]=g[b][a]=unmatched;
  208.      //After this, a and b are included in the matching.
  209.      match[path[0][0]]=match[path[1][0]]=true;
  210. }
  211.  
  212. bool augmentMatching (int n){  //The main analyzing function, with the
  213.      int node,nodeLabel;       //goal of finding augmenting paths or
  214.      initAlg(n);               //concluding that the matching is maximum.
  215.      for (int i=0; i<n; i++) if (!match[i]){
  216.          label[i].even=empty;
  217.          enqueue(i,0);          //Initialize the queue with the exposed vertices,
  218.      }                          //making them the roots in the forest.
  219.      
  220.      while (queueFront<queueBack){
  221.          node=queue[queueFront].vertex;
  222.          nodeLabel=queue[queueFront].type;
  223.          if (nodeLabel==0){
  224.             for (int i=0; i<n; i++) if (g[node][i]==unmatched){
  225.                 if (blossom[node]==blossom[i]);
  226.                 //Do nothing. Edges inside the same blossom have no meaning.
  227.                 else if (label[i].even!=undef){
  228.                      /*
  229.                        The tree has reached a vertex with a label.
  230.                        The parity of this label indicates that an odd length
  231.                        alternating path has been found. If this path is between
  232.                        roots, we have an augmenting path, else there's an
  233.                        alternating cycle, a blossom.
  234.                      */
  235.                      endPath[0]=endPath[1]=0;
  236.                      backtrace(node,0,empty,0,reverse);
  237.                      backtrace(i,1,empty,0,reverse);
  238.                      //Call the backtracing function to find out.
  239.                      if (path[0][0]==path[1][0]) newBlossom(node,i);
  240.                      /*
  241.                        If the same root node is reached, a blossom was found.
  242.                        Start the labelling procedure to create pseudo-contraction.
  243.                      */
  244.                      else {
  245.                           augmentPath();
  246.                           return true;
  247.                           /*
  248.                             If the roots are different, we have an augmenting path.
  249.                             Improve the matching by augmenting this path.
  250.                             Now some labels might make no sense, stop the function,
  251.                             returning that it was successful in improving.
  252.                           */
  253.                      }
  254.                 }
  255.                 else if (label[i].even==undef && label[i].odd[0]==undef){
  256.                      //If an unseen vertex is found, report the existing path
  257.                      //by labeling it accordingly.
  258.                      label[i].odd[0]=node;
  259.                      enqueue(i,1);
  260.                 }
  261.             }
  262.          }
  263.          else if (nodeLabel==1){ //Similar to above.
  264.             for (int i=0; i<n; i++) if (g[node][i]==matched){
  265.                 if (blossom[node]==blossom[i]);
  266.                 else if (label[i].odd[0]!=undef){
  267.                      endPath[0]=endPath[1]=0;
  268.                      backtrace(node,0,empty,1,reverse);
  269.                      backtrace(i,1,empty,1,reverse);
  270.                      if (path[0][0]==path[1][0]) newBlossom(node,i);
  271.                      else {
  272.                           augmentPath();
  273.                           return true;
  274.                      }
  275.                 }
  276.                 else if (label[i].even==undef && label[i].odd[0]==undef){
  277.                      label[i].even=node;
  278.                      enqueue(i,0);
  279.                 }
  280.             }
  281.          }
  282.          /*
  283.            The scanning of this label is complete, dequeue it and
  284.            keep going to the next one.
  285.          */
  286.          queueFront++;
  287.      }
  288.      /*
  289.        If the function reaches this point, the queue is empty, all
  290.        labels have been scanned. The algorithm couldn't find an augmenting
  291.        path. Therefore, it concludes the matching is maximum.
  292.      */
  293.      return false;
  294. }
  295.  
  296. void findMaximumMatching (int n){
  297.      //Initialize it with the empty matching.
  298.      for (int i=0; i<n; i++) match[i]=false;
  299.      //Run augmentMatching(), it'll keep improving the matching.
  300.      //Eventually, it will no longer find a path and break the loop,
  301.      //at this point, the current matching is maximum.
  302.      while (augmentMatching(n));
  303. }
  304.  
  305. int main(){
  306.     int n;
  307.     n=readGraph();
  308.     findMaximumMatching(n);
  309.     for (int i=0; i<n; i++){
  310.         for (int j=i+1; j<n; j++) if (g[i][j]==matched)
  311.             printf("%d %d\n",i+1,j+1);
  312.     }
  313.     return 0;
  314. }
RAW Paste Data