home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / graph_al / matching.heu < prev   
Encoding:
Text File  |  1991-11-15  |  1.6 KB  |  67 lines
  1. From markus@mpii01002.cs.uni-sb.de Mon Oct 28 11:08:16 1991
  2. From: markus@mpii01002.cs.uni-sb.de
  3. To: stefan
  4. Subject: Gen. Matching
  5.  
  6. ' Morgen.
  7.  
  8. Ich schicke Dir mal die Heuristik, die (fast) alle Pfade der 
  9. Laenge <= 3 findet. Sie ist kaum langsamer als die "Greedy"-Methode,
  10. aber wesentlich besser. Die Laufzeit des nachfolgenden Algorithmus
  11. reduziert sich auf ca. 1/5 (je nach Dichte).
  12.  
  13.                     Markus
  14.  
  15.  
  16.  
  17.  
  18.  
  19. /*
  20.  * finds almost all augmenting paths of length <=3 with two passes over
  21.  * the adjacency lists
  22.  * ("almost": discovery of a blossom {v,w,x,v} leads to a skip of the
  23.  * edge (x,v), even if the base v stays unmatched - it's not worth while
  24.  * to fix this problem)
  25.  * if all adjacent nodes w of v are matched, try to find an other 
  26.  * partner for mate[x], and match v and w on success
  27.  */
  28. int heuristic( graph &G, node_array(node)& mate )
  29. {
  30.   node u, v, w, x ;
  31.   int card = 0 ;
  32.   bool found ;
  33.   node_array(bool) all_matched( G, false ) ;
  34.  
  35.   G.reset() ;
  36.   forall_nodes( v, G ) {        
  37.     if( mate[v]==nil ) {            // first pass
  38.       while( (found=G.next_adj_node( w, v )) && (mate[w]!=nil) ) ;
  39.       if( found ) {
  40.         mate[v] = w ;  mate[w] = v ;  
  41.     card++ ;    
  42.       }
  43.       else {        
  44.     all_matched[v] = true ;
  45.     G.init_adj_iterator( v ) ;        // second pass
  46.         while( G.next_adj_node( w, v ) ) {
  47.       if( ! all_matched[ ( x = mate[w] ) ] ) {
  48.             while( (found=G.next_adj_node( u, x )) && ( (u==v) || (mate[u]!=nil) ) ) ;
  49.             if( found ) {
  50.               mate[u] = x ;  mate[x] = u ;
  51.               mate[v] = w ;  mate[w] = v ;
  52.           card++ ;
  53.           break ;
  54.         }
  55.         else
  56.           all_matched[x] = true ;
  57.       }
  58.     }
  59.       }
  60.     } 
  61.   } ;
  62.   G.reset() ;
  63.  
  64.   return( card ) ;
  65. }
  66.  
  67.