Changeset 2424:95cd24940d00 in lemon-0.x for test

Timestamp:

04/19/07 17:11:58 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Redesigned Kruskal algorithm

The interface of function type implementation is not changed
Additional class type implementation

File:

• test/kruskal_test.cc (modified) (7 diffs)

test/kruskal_test.cc

@@ -24 +24 @@
 #include <lemon/kruskal.h>
 #include <lemon/list_graph.h>
+
 #include <lemon/concepts/maps.h>
 #include <lemon/concepts/graph.h>
+#include <lemon/concepts/ugraph.h>
 
 
@@ -34 +36 @@
 {
   concepts::WriteMap<concepts::Graph::Edge,bool> w;
+  concepts::WriteMap<concepts::UGraph::UEdge,bool> uw;
+
+  concepts::ReadMap<concepts::Graph::Edge,int> r;
+  concepts::ReadMap<concepts::UGraph::UEdge,int> ur;
 
   concepts::Graph g;
-  kruskal(g,
-          concepts::ReadMap<concepts::Graph::Edge,int>(),
-          w);
+  concepts::UGraph ug;
+
+  kruskal(g, r, w);
+  kruskal(ug, ur, uw);
+
+  std::vector<std::pair<concepts::Graph::Edge, int> > rs;
+  std::vector<std::pair<concepts::UGraph::UEdge, int> > urs;
+
+  kruskal(g, rs, w);
+  kruskal(ug, urs, uw);
+
+  std::vector<concepts::Graph::Edge> ws;
+  std::vector<concepts::UGraph::UEdge> uws;
+
+  kruskal(g, r, ws.begin());
+  kruskal(ug, ur, uws.begin());
+
+  Kruskal<concepts::UGraph,concepts::ReadMap<concepts::UGraph::UEdge,int> >
+    alg(ug, ur);
+
+  alg.init();
+  alg.initPresorted(uws.begin(), uws.end());
+  alg.reinit();
+  
+  alg.emptyQueue();
+  
+  alg.nextEdge();
+  alg.processNextEdge();
+  alg.processEdge(concepts::UGraph::UEdge());
+
+  alg.run();
+  
+  alg.treeMap();
+  alg.tree(concepts::UGraph::UEdge());
 }
 
 int main() {
 
-  typedef ListGraph::Node Node;
-  typedef ListGraph::Edge Edge;
-  typedef ListGraph::NodeIt NodeIt;
-  typedef ListGraph::EdgeIt EdgeIt;
+  typedef ListUGraph::Node Node;
+  typedef ListUGraph::UEdge UEdge;
+  typedef ListUGraph::NodeIt NodeIt;
+  typedef ListUGraph::EdgeIt EdgeIt;
 
-  ListGraph G;
+  ListUGraph G;
 
   Node s=G.addNode();
@@ -57 +94 @@
   Node t=G.addNode();
   
-  Edge e1 = G.addEdge(s, v1);
-  Edge e2 = G.addEdge(s, v2);
-  Edge e3 = G.addEdge(v1, v2);
-  Edge e4 = G.addEdge(v2, v1);
-  Edge e5 = G.addEdge(v1, v3);
-  Edge e6 = G.addEdge(v3, v2);
-  Edge e7 = G.addEdge(v2, v4);
-  Edge e8 = G.addEdge(v4, v3);
-  Edge e9 = G.addEdge(v3, t);
-  Edge e10 = G.addEdge(v4, t);
+  UEdge e1 = G.addEdge(s, v1);
+  UEdge e2 = G.addEdge(s, v2);
+  UEdge e3 = G.addEdge(v1, v2);
+  UEdge e4 = G.addEdge(v2, v1);
+  UEdge e5 = G.addEdge(v1, v3);
+  UEdge e6 = G.addEdge(v3, v2);
+  UEdge e7 = G.addEdge(v2, v4);
+  UEdge e8 = G.addEdge(v4, v3);
+  UEdge e9 = G.addEdge(v3, t);
+  UEdge e10 = G.addEdge(v4, t);
 
-  typedef ListGraph::EdgeMap<int> ECostMap;
-  typedef ListGraph::EdgeMap<bool> EBoolMap;
+  typedef ListUGraph::UEdgeMap<int> ECostMap;
+  typedef ListUGraph::UEdgeMap<bool> EBoolMap;
 
   ECostMap edge_cost_map(G, 2);
@@ -76 +113 @@
 
   //Test with const map.
-  check(kruskal(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
+  check(kruskal(G, ConstMap<ListUGraph::UEdge,int>(2), tree_map)==10,
         "Total cost should be 10");
   //Test with a edge map (filled with uniform costs).
@@ -93 +130 @@
   edge_cost_map.set(e10, -1);
 
-  vector<Edge> tree_edge_vec(5);
+  vector<UEdge> tree_edge_vec(5);
 
   //Test with a edge map and inserter.
@@ -108 +145 @@
         "Total cost should be -31.");
   
-  tree_edge_vec.clear();
+//   tree_edge_vec.clear();
   
-  //The above test could also be coded like this:
-  check(kruskal(G,
-                makeKruskalMapInput(G, edge_cost_map),
-                makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
-        ==-31,
-        "Total cost should be -31.");
+//   //The above test could also be coded like this:
+//   check(kruskal(G,
+//              makeKruskalMapInput(G, edge_cost_map),
+//              makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
+//      ==-31,
+//      "Total cost should be -31.");
 
   check(tree_edge_vec.size()==5,"The tree should have 5 edges.");
@@ -126 +163 @@
         "Wrong tree.");
 
+  Kruskal<ListUGraph, ECostMap> ka(G, edge_cost_map);
+  
+  ka.run();
+  
+  check(ka.tree(e1) && 
+        ka.tree(e2) &&
+        ka.tree(e5) &&
+        ka.tree(e7) &&
+        ka.tree(e9),
+        "Wrong tree.");
+
+  check(ka.treeValue() == -31,
+        "Total cost should be -31.");
+
   return 0;
 }