23 operator[](s) = i; |
23 operator[](s) = i; |
24 } |
24 } |
25 }; |
25 }; |
26 |
26 |
27 |
27 |
|
28 // Egy olyan "map", ami nem tud semmit, csak a typedef-eket. |
|
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 int main() { |
38 int main() { |
29 |
39 |
|
40 typedef ListGraph::Node Node; |
|
41 typedef ListGraph::Edge Edge; |
30 typedef ListGraph::NodeIt NodeIt; |
42 typedef ListGraph::NodeIt NodeIt; |
31 typedef ListGraph::EdgeIt EdgeIt; |
43 typedef ListGraph::EdgeIt EdgeIt; |
32 typedef ListGraph::EachNodeIt EachNodeIt; |
|
33 typedef ListGraph::EachEdgeIt EachEdgeIt; |
|
34 |
44 |
35 ListGraph G; |
45 ListGraph G; |
36 |
46 |
37 NodeIt s=G.addNode(); |
47 Node s=G.addNode(); |
38 NodeIt v1=G.addNode(); |
48 Node v1=G.addNode(); |
39 NodeIt v2=G.addNode(); |
49 Node v2=G.addNode(); |
40 NodeIt v3=G.addNode(); |
50 Node v3=G.addNode(); |
41 NodeIt v4=G.addNode(); |
51 Node v4=G.addNode(); |
42 NodeIt t=G.addNode(); |
52 Node t=G.addNode(); |
43 |
53 |
44 G.addEdge(s, v1); |
54 Edge e1 = G.addEdge(s, v1); |
45 G.addEdge(s, v2); |
55 Edge e2 = G.addEdge(s, v2); |
46 G.addEdge(v1, v2); |
56 Edge e3 = G.addEdge(v1, v2); |
47 G.addEdge(v2, v1); |
57 Edge e4 = G.addEdge(v2, v1); |
48 G.addEdge(v1, v3); |
58 Edge e5 = G.addEdge(v1, v3); |
49 G.addEdge(v3, v2); |
59 Edge e6 = G.addEdge(v3, v2); |
50 G.addEdge(v2, v4); |
60 Edge e7 = G.addEdge(v2, v4); |
51 G.addEdge(v4, v3); |
61 Edge e8 = G.addEdge(v4, v3); |
52 G.addEdge(v3, t); |
62 Edge e9 = G.addEdge(v3, t); |
53 G.addEdge(v4, t); |
63 Edge e10 = G.addEdge(v4, t); |
54 |
64 |
55 ListGraph::EdgeMap<double> edge_cost_map(G, 2); |
65 typedef ListGraph::EdgeMap<double> ECostMap; |
56 ListGraph::EdgeMap<bool> tree_map(G); |
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 2-es 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 return 0; |
98 return 0; |
63 } |
99 } |