1 #include <string> |
|
2 #include <iostream> |
|
3 #include <map> |
|
4 #include <vector> |
|
5 |
|
6 #include <kruskal.h> |
|
7 #include <hugo/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 << kruskalEdgeMap(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 << kruskalEdgeMap_IteratorOut(G, edge_cost_map, |
|
93 back_inserter(tree_edge_vec)) |
|
94 << endl; |
|
95 |
|
96 int i = 1; |
|
97 for(vector<Edge>::iterator e = tree_edge_vec.begin(); |
|
98 e != tree_edge_vec.end(); ++e, ++i) { |
|
99 cout << i << ". el: " << G.id(*e) << endl; |
|
100 } |
|
101 |
|
102 tree_edge_vec.clear(); |
|
103 // SequenceOutput< back_insert_iterator< vector<Edge> > > |
|
104 // vec_filler(back_inserter(tree_edge_vec)); |
|
105 // cout << "Nemkonst koltseggel tarhatekonyabban: " |
|
106 // << Kruskal(G, |
|
107 // KruskalMapVec<ECostMap>(G, edge_cost_map), |
|
108 // vec_filler) |
|
109 // << endl; |
|
110 |
|
111 // cout << "Nemkonst koltseggel tarhatekonyabban: " |
|
112 // << kruskal(G, |
|
113 // KruskalMapVec<ECostMap>(G, edge_cost_map), |
|
114 // makeSequenceOutput(back_inserter(tree_edge_vec)) |
|
115 // ) |
|
116 // << endl; |
|
117 |
|
118 // i = 1; |
|
119 // for(vector<Edge>::iterator e = tree_edge_vec.begin(); |
|
120 // e != tree_edge_vec.end(); ++e, ++i) { |
|
121 // cout << i << ". el: " << *e << endl; |
|
122 // } |
|
123 |
|
124 // ********************************************************************** |
|
125 |
|
126 // typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK; |
|
127 |
|
128 // MCTK mctk(G, edge_cost_map, tree_map); |
|
129 // double k0lts = mctk.run(); |
|
130 |
|
131 // cout << "Uniform 2-es koltseggel: " << k0lts << endl; |
|
132 |
|
133 // // Max koltsegu fa szamitasa elore megrendezett koltseg vektorbol: |
|
134 // typedef MinCostTreeKruskal<ListGraph, DummyMap<Edge,int>, EBoolMap> MCTK2; |
|
135 // MCTK2 mctk2(G, DummyMap<Edge,int>(), tree_map); |
|
136 // MCTK2::EdgeCostVector ecv; |
|
137 // ecv.push_back(make_pair(e1, 10)); |
|
138 // ecv.push_back(make_pair(e2, 9)); |
|
139 // ecv.push_back(make_pair(e3, 8)); |
|
140 // ecv.push_back(make_pair(e4, 7)); |
|
141 // ecv.push_back(make_pair(e5, 6)); |
|
142 // ecv.push_back(make_pair(e6, 5)); |
|
143 // ecv.push_back(make_pair(e7, 4)); |
|
144 // ecv.push_back(make_pair(e8, 3)); |
|
145 // ecv.push_back(make_pair(e9, 2)); |
|
146 // ecv.push_back(make_pair(e10, 1)); |
|
147 |
|
148 // k0lts = mctk2.run(ecv); |
|
149 // cout << "Max koltsegu fa elore megrendezett koltseg vektorbol: 31 = " |
|
150 // << k0lts << endl; |
|
151 |
|
152 |
|
153 return 0; |
|
154 } |
|