Changeset 218:5964f1c64ca1 in lemon0.x for src/work/johanna/kruskal_test.cc
 Timestamp:
 03/20/04 18:01:45 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@314
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/johanna/kruskal_test.cc
r150 r218 4 4 5 5 #include <kruskal.h> 6 #include <list_graph.h h>6 #include <list_graph.h> 7 7 8 8 … … 26 26 27 27 28 // Egy olyan "map", ami nem tud semmit, csak a typedefeket. 29 // Valami elegansabb megoldas kene a Kruskalban... 30 31 template <typename K, typename V> 32 class DummyMap { 33 public: 34 typedef K KeyType; 35 typedef V ValueType; 36 }; 37 28 38 int main() { 29 39 40 typedef ListGraph::Node Node; 41 typedef ListGraph::Edge Edge; 30 42 typedef ListGraph::NodeIt NodeIt; 31 43 typedef ListGraph::EdgeIt EdgeIt; 32 typedef ListGraph::EachNodeIt EachNodeIt;33 typedef ListGraph::EachEdgeIt EachEdgeIt;34 44 35 45 ListGraph G; 36 46 37 Node Its=G.addNode();38 Node Itv1=G.addNode();39 Node Itv2=G.addNode();40 Node Itv3=G.addNode();41 Node Itv4=G.addNode();42 Node Itt=G.addNode();47 Node s=G.addNode(); 48 Node v1=G.addNode(); 49 Node v2=G.addNode(); 50 Node v3=G.addNode(); 51 Node v4=G.addNode(); 52 Node t=G.addNode(); 43 53 44 G.addEdge(s, v1);45 G.addEdge(s, v2);46 G.addEdge(v1, v2);47 G.addEdge(v2, v1);48 G.addEdge(v1, v3);49 G.addEdge(v3, v2);50 G.addEdge(v2, v4);51 G.addEdge(v4, v3);52 G.addEdge(v3, t);53 G.addEdge(v4, t);54 Edge e1 = G.addEdge(s, v1); 55 Edge e2 = G.addEdge(s, v2); 56 Edge e3 = G.addEdge(v1, v2); 57 Edge e4 = G.addEdge(v2, v1); 58 Edge e5 = G.addEdge(v1, v3); 59 Edge e6 = G.addEdge(v3, v2); 60 Edge e7 = G.addEdge(v2, v4); 61 Edge e8 = G.addEdge(v4, v3); 62 Edge e9 = G.addEdge(v3, t); 63 Edge e10 = G.addEdge(v4, t); 54 64 55 ListGraph::EdgeMap<double> edge_cost_map(G, 2); 56 ListGraph::EdgeMap<bool> tree_map(G); 65 typedef ListGraph::EdgeMap<double> ECostMap; 66 typedef ListGraph::EdgeMap<bool> EBoolMap; 67 68 ECostMap edge_cost_map(G, 2); 69 EBoolMap tree_map(G); 57 70 58 double k0lts = MinCostTreeKruskal(G, edge_cost_map, tree_map);71 typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK; 59 72 60 cout << k0lts << endl; 73 MCTK mctk(G, edge_cost_map, tree_map); 74 double k0lts = mctk.run(); 75 76 cout << "Uniform 2es koltseggel: " << k0lts << endl; 77 78 // Max koltsegu fa szamitasa elore megrendezett koltseg vektorbol: 79 typedef MinCostTreeKruskal<ListGraph, DummyMap<Edge,int>, EBoolMap> MCTK2; 80 MCTK2 mctk2(G, DummyMap<Edge,int>(), tree_map); 81 MCTK2::EdgeCostVector ecv; 82 ecv.push_back(make_pair(e1, 10)); 83 ecv.push_back(make_pair(e2, 9)); 84 ecv.push_back(make_pair(e3, 8)); 85 ecv.push_back(make_pair(e4, 7)); 86 ecv.push_back(make_pair(e5, 6)); 87 ecv.push_back(make_pair(e6, 5)); 88 ecv.push_back(make_pair(e7, 4)); 89 ecv.push_back(make_pair(e8, 3)); 90 ecv.push_back(make_pair(e9, 2)); 91 ecv.push_back(make_pair(e10, 1)); 92 93 k0lts = mctk2.run(ecv); 94 cout << "Max koltsegu fa elore megrendezett koltseg vektorbol: 31 = " 95 << k0lts << endl; 96 61 97 62 98 return 0;
Note: See TracChangeset
for help on using the changeset viewer.