1 | #include <string> |
---|
2 | #include <iostream> |
---|
3 | #include <map> |
---|
4 | #include <vector> |
---|
5 | |
---|
6 | #include <kruskal.h> |
---|
7 | #include <list_graph.h> |
---|
8 | |
---|
9 | |
---|
10 | using namespace std; |
---|
11 | using namespace hugo; |
---|
12 | |
---|
13 | class string_int_map : public map<string,int> { |
---|
14 | public: |
---|
15 | int get(const string &s) { |
---|
16 | // Bocs, ez igy gaaaany, de nem volt kedvem utananezni, hogy |
---|
17 | // hogy is mukodik ez a map :) |
---|
18 | if( count(s) == 0 ) { |
---|
19 | operator[](s) = -1; |
---|
20 | } |
---|
21 | return operator[](s); |
---|
22 | } |
---|
23 | void set(const string &s, int i) { |
---|
24 | operator[](s) = i; |
---|
25 | } |
---|
26 | }; |
---|
27 | |
---|
28 | |
---|
29 | // Egy olyan "map", ami nem tud semmit, csak a typedef-eket. |
---|
30 | // Valami elegansabb megoldas kene a Kruskalban... |
---|
31 | |
---|
32 | template <typename K, typename V> |
---|
33 | class DummyMap { |
---|
34 | public: |
---|
35 | typedef K KeyType; |
---|
36 | typedef V ValueType; |
---|
37 | }; |
---|
38 | |
---|
39 | int main() { |
---|
40 | |
---|
41 | typedef ListGraph::Node Node; |
---|
42 | typedef ListGraph::Edge Edge; |
---|
43 | typedef ListGraph::NodeIt NodeIt; |
---|
44 | typedef ListGraph::EdgeIt EdgeIt; |
---|
45 | |
---|
46 | ListGraph G; |
---|
47 | |
---|
48 | Node s=G.addNode(); |
---|
49 | Node v1=G.addNode(); |
---|
50 | Node v2=G.addNode(); |
---|
51 | Node v3=G.addNode(); |
---|
52 | Node v4=G.addNode(); |
---|
53 | Node t=G.addNode(); |
---|
54 | |
---|
55 | Edge e1 = G.addEdge(s, v1); |
---|
56 | Edge e2 = G.addEdge(s, v2); |
---|
57 | Edge e3 = G.addEdge(v1, v2); |
---|
58 | Edge e4 = G.addEdge(v2, v1); |
---|
59 | Edge e5 = G.addEdge(v1, v3); |
---|
60 | Edge e6 = G.addEdge(v3, v2); |
---|
61 | Edge e7 = G.addEdge(v2, v4); |
---|
62 | Edge e8 = G.addEdge(v4, v3); |
---|
63 | Edge e9 = G.addEdge(v3, t); |
---|
64 | Edge e10 = G.addEdge(v4, t); |
---|
65 | |
---|
66 | typedef ListGraph::EdgeMap<double> ECostMap; |
---|
67 | typedef ListGraph::EdgeMap<bool> EBoolMap; |
---|
68 | |
---|
69 | ECostMap edge_cost_map(G, 2); |
---|
70 | EBoolMap tree_map(G); |
---|
71 | |
---|
72 | |
---|
73 | cout << "Uniform 2-es koltseggel: " |
---|
74 | << kruskal1(G, edge_cost_map, tree_map) |
---|
75 | << endl; |
---|
76 | |
---|
77 | |
---|
78 | edge_cost_map.set(e1, -10); |
---|
79 | edge_cost_map.set(e2, -9); |
---|
80 | edge_cost_map.set(e3, -8); |
---|
81 | edge_cost_map.set(e4, -7); |
---|
82 | edge_cost_map.set(e5, -6); |
---|
83 | edge_cost_map.set(e6, -5); |
---|
84 | edge_cost_map.set(e7, -4); |
---|
85 | edge_cost_map.set(e8, -3); |
---|
86 | edge_cost_map.set(e9, -2); |
---|
87 | edge_cost_map.set(e10, -1); |
---|
88 | |
---|
89 | vector<Edge> tree_edge_vec; |
---|
90 | |
---|
91 | cout << "Nemkonst koltseggel (-31): " |
---|
92 | << kruskal2(G, edge_cost_map, back_inserter(tree_edge_vec)) |
---|
93 | << endl; |
---|
94 | |
---|
95 | int i = 1; |
---|
96 | for(vector<Edge>::iterator e = tree_edge_vec.begin(); |
---|
97 | e != tree_edge_vec.end(); ++e, ++i) { |
---|
98 | cout << i << ". el: " << *e << endl; |
---|
99 | } |
---|
100 | |
---|
101 | |
---|
102 | // typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK; |
---|
103 | |
---|
104 | // MCTK mctk(G, edge_cost_map, tree_map); |
---|
105 | // double k0lts = mctk.run(); |
---|
106 | |
---|
107 | // cout << "Uniform 2-es koltseggel: " << k0lts << endl; |
---|
108 | |
---|
109 | // // Max koltsegu fa szamitasa elore megrendezett koltseg vektorbol: |
---|
110 | // typedef MinCostTreeKruskal<ListGraph, DummyMap<Edge,int>, EBoolMap> MCTK2; |
---|
111 | // MCTK2 mctk2(G, DummyMap<Edge,int>(), tree_map); |
---|
112 | // MCTK2::EdgeCostVector ecv; |
---|
113 | // ecv.push_back(make_pair(e1, 10)); |
---|
114 | // ecv.push_back(make_pair(e2, 9)); |
---|
115 | // ecv.push_back(make_pair(e3, 8)); |
---|
116 | // ecv.push_back(make_pair(e4, 7)); |
---|
117 | // ecv.push_back(make_pair(e5, 6)); |
---|
118 | // ecv.push_back(make_pair(e6, 5)); |
---|
119 | // ecv.push_back(make_pair(e7, 4)); |
---|
120 | // ecv.push_back(make_pair(e8, 3)); |
---|
121 | // ecv.push_back(make_pair(e9, 2)); |
---|
122 | // ecv.push_back(make_pair(e10, 1)); |
---|
123 | |
---|
124 | // k0lts = mctk2.run(ecv); |
---|
125 | // cout << "Max koltsegu fa elore megrendezett koltseg vektorbol: 31 = " |
---|
126 | // << k0lts << endl; |
---|
127 | |
---|
128 | |
---|
129 | return 0; |
---|
130 | } |
---|