Changeset 2205:c20b0eb92a33 in lemon-0.x for lemon/max_matching.h

Timestamp:

09/06/06 13:17:12 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2930

Message:

UnionFind?
Changing the representation of the union-find
it has the same running time but it takes just 2/3 space
! does not auto insert items /performance/

UnionFindEnum?
Changing the interface - more convenient to UnionFind?
Does not based on the stl data structures /it could be disadvantage/

=> does not use singular iterator assignment /not stl conform, but always work/

Just new iterator interface

MaxMatching? + UnionFindTest?
Using new iterator interface instead of the old

File:

• lemon/max_matching.h (modified) (3 diffs)

lemon/max_matching.h

@@ -66 +66 @@
     typedef typename Graph::IncEdgeIt IncEdgeIt;
 
-    typedef UnionFindEnum<Node, Graph::template NodeMap> UFE;
+    typedef typename Graph::template NodeMap<int> UFECrossRef;
+    typedef UnionFindEnum<Node, UFECrossRef> UFE;
 
   public:
@@ -122 +123 @@
       //representative elements of UFE blossom) and for the nodes in C 
       
-      typename UFE::MapType blossom_base(g);
+      UFECrossRef blossom_base(g);
       UFE blossom(blossom_base);
-      typename UFE::MapType tree_base(g);
+
+      UFECrossRef tree_base(g);
       UFE tree(tree_base);
+
       //If these UFE's would be members of the class then also
       //blossom_base and tree_base should be a member.
@@ -550 +553 @@
     }
     Node y=blossom.find(x);
-    typename UFE::ItemIt it;
-    for (tree.first(it,blossom.find(x)); tree.valid(it); tree.next(it)) {   
-      if ( position[it] == D ) {
-        typename UFE::ItemIt b_it;
-        for (blossom.first(b_it,it); blossom.valid(b_it); blossom.next(b_it)) {  
-          position.set( b_it ,C);
+    for (typename UFE::ItemIt tit(tree, y); tit != INVALID; ++tit) {   
+      if ( position[tit] == D ) {
+        for (typename UFE::ItemIt bit(blossom, tit); bit != INVALID; ++bit) {  
+          position.set( bit ,C);
         }
-        blossom.eraseClass(it);
-      } else position.set( it ,C);
+        blossom.eraseClass(tit);
+      } else position.set( tit ,C);
     }
     tree.eraseClass(y);