Changeset 218:5964f1c64ca1 in lemon-0.x for src/work/johanna/kruskal_test.cc

Timestamp:

03/20/04 18:01:45 (20 years ago)

Author:

beckerjc

Branch:

default

Phase:

public

Convert:

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

Message:

unionfind: componentSize tagfv

kruskal: osztalyositva; lehet beadni sajat elorendezett el-koltseg vektort

nem tul elegans megoldas...

File:

• src/work/johanna/kruskal_test.cc (modified) (2 diffs)

src/work/johanna/kruskal_test.cc

@@ -4 +4 @@
 
 #include <kruskal.h>
-#include <list_graph.hh>
+#include <list_graph.h>
 
 
@@ -26 +26 @@
 
 
+// Egy olyan "map", ami nem tud semmit, csak a typedef-eket.
+// Valami elegansabb megoldas kene a Kruskalban...
+
+template <typename K, typename V>
+class DummyMap {
+public:
+  typedef K KeyType;
+  typedef V ValueType;
+};
+
 int main() {
 
+  typedef ListGraph::Node Node;
+  typedef ListGraph::Edge Edge;
   typedef ListGraph::NodeIt NodeIt;
   typedef ListGraph::EdgeIt EdgeIt;
-  typedef ListGraph::EachNodeIt EachNodeIt;
-  typedef ListGraph::EachEdgeIt EachEdgeIt;
 
   ListGraph G;
 
-  NodeIt s=G.addNode();
-  NodeIt v1=G.addNode();
-  NodeIt v2=G.addNode();
-  NodeIt v3=G.addNode();
-  NodeIt v4=G.addNode();
-  NodeIt t=G.addNode();
+  Node s=G.addNode();
+  Node v1=G.addNode();
+  Node v2=G.addNode();
+  Node v3=G.addNode();
+  Node v4=G.addNode();
+  Node t=G.addNode();
   
-  G.addEdge(s, v1);
-  G.addEdge(s, v2);
-  G.addEdge(v1, v2);
-  G.addEdge(v2, v1);
-  G.addEdge(v1, v3);
-  G.addEdge(v3, v2);
-  G.addEdge(v2, v4);
-  G.addEdge(v4, v3);
-  G.addEdge(v3, t);
-  G.addEdge(v4, t);
+  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);
 
-  ListGraph::EdgeMap<double> edge_cost_map(G, 2);
-  ListGraph::EdgeMap<bool> tree_map(G);
+  typedef ListGraph::EdgeMap<double> ECostMap;
+  typedef ListGraph::EdgeMap<bool> EBoolMap;
+
+  ECostMap edge_cost_map(G, 2);
+  EBoolMap tree_map(G);
   
-  double k0lts = MinCostTreeKruskal(G, edge_cost_map, tree_map);
+  typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK;
 
-  cout << k0lts << endl;
+  MCTK mctk(G, edge_cost_map, tree_map);
+  double k0lts = mctk.run();
+
+  cout << "Uniform 2-es koltseggel: " << k0lts << endl;
+
+  // Max koltsegu fa szamitasa elore megrendezett koltseg vektorbol:
+  typedef MinCostTreeKruskal<ListGraph, DummyMap<Edge,int>, EBoolMap> MCTK2;
+  MCTK2 mctk2(G, DummyMap<Edge,int>(), tree_map);
+  MCTK2::EdgeCostVector ecv;
+  ecv.push_back(make_pair(e1, 10));
+  ecv.push_back(make_pair(e2, 9));
+  ecv.push_back(make_pair(e3, 8));
+  ecv.push_back(make_pair(e4, 7));
+  ecv.push_back(make_pair(e5, 6));
+  ecv.push_back(make_pair(e6, 5));
+  ecv.push_back(make_pair(e7, 4));
+  ecv.push_back(make_pair(e8, 3));
+  ecv.push_back(make_pair(e9, 2));
+  ecv.push_back(make_pair(e10, 1));
+
+  k0lts = mctk2.run(ecv);
+  cout << "Max koltsegu fa elore megrendezett koltseg vektorbol: 31 = "
+       << k0lts << endl;
+
 
   return 0;