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

Timestamp:

09/06/06 13:17:12 (18 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/kruskal.h (modified) (3 diffs)

lemon/kruskal.h

@@ -25 +25 @@
 #include <lemon/bits/utility.h>
 #include <lemon/bits/traits.h>
+#include <lemon/time_measure.h>
+#include <iostream>
 
 ///\ingroup spantree
@@ -118 +120 @@
     typedef typename GR::Node Node;
 
-    NodeIntMap comp(g, -1);
-    UnionFind<Node,NodeIntMap> uf(comp); 
+    Timer timer;
+    NodeIntMap comp(g);
+    UnionFind<Node,NodeIntMap> uf(comp);
+    for (typename GR::NodeIt it(g); it != INVALID; ++it) {
+      uf.insert(it);
+    }
       
     EdgeCost tot_cost = 0;
@@ -133 +139 @@
       }
     }
+    std::cout << timer << std::endl;
     return tot_cost;
   }