1 #include <iostream> |
1 #include <iostream> |
2 #include <vector> |
2 #include <vector> |
3 #include <string> |
3 #include <string> |
4 |
4 |
5 #include <marci_list_graph.hh> |
5 #include <list_graph.hh> |
6 #include <marci_property_vector.hh> |
6 #include <bfs_iterator.hh> |
7 #include <marci_bfs.hh> |
7 #include <edmonds_karp.hh> |
8 #include <marci_max_flow.hh> |
|
9 |
8 |
10 using namespace marci; |
9 using namespace marci; |
11 |
10 |
12 int main (int, char*[]) |
11 int main (int, char*[]) |
13 { |
12 { |
14 typedef list_graph::node_iterator node_iterator; |
13 typedef ListGraph::NodeIt NodeIt; |
15 typedef list_graph::edge_iterator edge_iterator; |
14 typedef ListGraph::EdgeIt EdgeIt; |
16 typedef list_graph::each_node_iterator each_node_iterator; |
15 typedef ListGraph::EachNodeIt EachNodeIt; |
17 typedef list_graph::each_edge_iterator each_edge_iterator; |
16 typedef ListGraph::EachEdgeIt EachEdgeIt; |
18 typedef list_graph::out_edge_iterator out_edge_iterator; |
17 typedef ListGraph::OutEdgeIt OutEdgeIt; |
19 typedef list_graph::in_edge_iterator in_edge_iterator; |
18 typedef ListGraph::InEdgeIt InEdgeIt; |
20 typedef list_graph::sym_edge_iterator sym_edge_iterator; |
19 typedef ListGraph::SymEdgeIt SymEdgeIt; |
21 list_graph G; |
20 ListGraph G; |
22 std::vector<node_iterator> vector_of_node_iterators; |
21 std::vector<NodeIt> vector_of_NodeIts; |
23 for(int i=0; i!=8; ++i) vector_of_node_iterators.push_back(G.add_node()); |
22 for(int i=0; i!=8; ++i) vector_of_NodeIts.push_back(G.addNode()); |
24 for(int i=0; i!=8; ++i) |
23 for(int i=0; i!=8; ++i) |
25 for(int j=0; j!=8; ++j) { |
24 for(int j=0; j!=8; ++j) |
26 if ((i<j)&&(i+j)%3) G.add_edge(vector_of_node_iterators[i], vector_of_node_iterators[j]); |
25 if ((i<j)&&(i+j)%3) G.addEdge(vector_of_NodeIts[i], vector_of_NodeIts[j]); |
27 } |
|
28 |
26 |
29 std::cout << "We construct a directed graph on the node set {0,1,2,...,7}," <<std::endl << "i-->j is arc iff i<j and (i+j)%3." << std::endl; |
27 std::cout << "We construct a directed graph on the node set {0,1,2,...,7}," <<std::endl << "i-->j is arc iff i<j and (i+j)%3." << std::endl; |
30 std::cout << "number of nodes: " << number_of(G.first_node()) << std::endl; |
28 std::cout << "number of nodes: " << count(G.first<EachNodeIt>()) << std::endl; |
31 |
29 |
32 for(each_node_iterator i=G.first_node(); i.valid(); ++i) { |
30 for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) { |
33 std::cout << "node " << G.id(i) << std::endl; |
31 std::cout << "node " << G.id(i) << std::endl; |
34 std::cout << " outdegree (out_edge_iterator): " << number_of(G.first_out_edge(i)) << " "; |
32 std::cout << " outdegree (OutEdgeIt): " << count(G.first<OutEdgeIt>(i)) << " "; |
35 for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) { |
33 for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) { |
36 std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") "; |
34 std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") "; |
37 } |
35 } |
38 std::cout << std::endl; |
36 std::cout << std::endl; |
39 |
37 |
40 std::cout<< " "; |
38 std::cout<< " "; |
41 for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) { |
39 for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) { |
42 std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; } |
40 std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } |
43 std::cout<<std::endl; |
41 std::cout<<std::endl; |
44 |
42 |
45 std::cout << " indegree: (in_edge_oterator) " << number_of(G.first_in_edge(i)) << " "; |
43 std::cout << " indegree: (InEdgeIt) " << count(G.first<InEdgeIt>(i)) << " "; |
46 for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) { |
44 for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) { |
47 std::cout << j << " "; } |
45 std::cout << j << " "; } |
48 std::cout << std::endl; |
46 std::cout << std::endl; |
49 |
47 |
50 std::cout<< " "; |
48 std::cout<< " "; |
51 for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) { |
49 for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) { |
52 std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; } |
50 std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } |
53 std::cout<<std::endl; |
51 std::cout<<std::endl; |
54 |
52 |
55 std::cout << " degree: (sym_edge_iterator) " << number_of(G.first_sym_edge(i)) << " "; |
53 std::cout << " degree: (SymEdgeIt) " << count(G.first<SymEdgeIt>(i)) << " "; |
56 for(sym_edge_iterator j=G.first_sym_edge(i); j.valid(); ++j) { |
54 for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) { |
57 std::cout << j << " "; } |
55 std::cout << j << " "; } |
58 std::cout<<std::endl; |
56 std::cout<<std::endl; |
59 |
57 |
60 std::cout<< " "; |
58 std::cout<< " "; |
61 for(sym_edge_iterator j=G.first_sym_edge(i); j.valid(); ++j) { |
59 for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) { |
62 std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; } |
60 std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } |
63 std::cout<<std::endl; |
61 std::cout<<std::endl; |
64 } |
62 } |
65 |
63 |
66 std::cout << "all edges: "; |
64 std::cout << "all edges: "; |
67 for(each_edge_iterator i=G.first_edge(); i.valid(); ++i) { |
65 for(EachEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) { |
68 std::cout << i << " "; |
66 std::cout << i << " "; |
69 } |
67 } |
70 std::cout << std::endl; |
68 std::cout << std::endl; |
71 |
69 |
72 std::cout << "node property array test" << std::endl; |
70 std::cout << "node property array test" << std::endl; |
73 node_property_vector<list_graph, int> my_property_vector(G); |
71 ListGraph::NodeMap<int> my_property_vector(G); |
74 each_node_iterator v; |
72 EachNodeIt v; |
75 G.get_first(v); |
73 G.getFirst(v); |
76 my_property_vector.put(v, 42); |
74 my_property_vector.set(v, 42); |
77 my_property_vector.put(++G.first_node(), 314); |
75 my_property_vector.set(++G.first<EachNodeIt>(), 314); |
78 my_property_vector.put(++++G.first_node(), 1956); |
76 my_property_vector.set(++++G.first<EachNodeIt>(), 1956); |
79 my_property_vector.put(vector_of_node_iterators[3], 1989); |
77 my_property_vector.set(vector_of_NodeIts[3], 1989); |
80 my_property_vector.put(vector_of_node_iterators[4], 2003); |
78 my_property_vector.set(vector_of_NodeIts[4], 2003); |
81 my_property_vector.put(vector_of_node_iterators[7], 1978); |
79 my_property_vector.set(vector_of_NodeIts[7], 1978); |
82 std::cout << "some node property values..." << std::endl; |
80 std::cout << "some node property values..." << std::endl; |
83 for(each_node_iterator i=G.first_node(); i.valid(); ++i) { |
81 for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) { |
84 std::cout << my_property_vector.get(i) << std::endl; |
82 std::cout << my_property_vector.get(i) << std::endl; |
85 } |
83 } |
86 int _i=1; |
84 int _i=1; |
87 int _ii=1; |
85 int _ii=1; |
88 edge_property_vector<list_graph, int> my_edge_property(G); |
86 ListGraph::EdgeMap<int> my_edge_property(G); |
89 for(each_edge_iterator i=G.first_edge(); i.valid(); ++i) { |
87 for(EachEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) { |
90 my_edge_property.put(i, _i); |
88 my_edge_property.set(i, _i); |
91 _i*=_ii; ++_ii; |
89 _i*=_ii; ++_ii; |
92 } |
90 } |
93 |
91 |
94 std::cout << "node and edge property values on the tails and heads of edges..." << std::endl; |
92 std::cout << "node and edge property values on the tails and heads of edges..." << std::endl; |
95 for(each_edge_iterator j=G.first_edge(); j.valid(); ++j) { |
93 for(EachEdgeIt j=G.first<EachEdgeIt>(); j.valid(); ++j) { |
96 std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " "; |
94 std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " "; |
97 } |
95 } |
98 std::cout << std::endl; |
96 std::cout << std::endl; |
99 |
97 |
100 //std::cout << "the same for inedges of the nodes..." << std::endl; |
|
101 //k=0; |
|
102 //for(each_node_iterator i=G.first_node(); i.valid(); ++i) { |
|
103 // for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) { |
|
104 // std::cout << my_property_vector.get(G.tail(j)) << "-->" << my_property_vector.get(G.head(j)) << " "; |
|
105 // } |
|
106 // std::cout << std::endl; |
|
107 //} |
|
108 |
|
109 std::cout << "bfs from the first node" << std::endl; |
98 std::cout << "bfs from the first node" << std::endl; |
110 bfs<list_graph> bfs_test(G, G.first_node()); |
99 bfs<ListGraph> bfs_test(G, G.first<EachNodeIt>()); |
111 bfs_test.run(); |
100 bfs_test.run(); |
112 std::cout << "reached: "; |
101 std::cout << "reached: "; |
113 for(each_node_iterator i=G.first_node(); i.valid(); ++i) { |
102 for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) { |
114 std::cout << bfs_test.reached.get(i) << " "; |
103 std::cout << bfs_test.reached.get(i) << " "; |
115 } |
104 } |
116 std::cout<<std::endl; |
105 std::cout<<std::endl; |
117 std::cout << "dist: "; |
106 std::cout << "dist: "; |
118 for(each_node_iterator i=G.first_node(); i.valid(); ++i) { |
107 for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) { |
119 std::cout << bfs_test.dist.get(i) << " "; |
108 std::cout << bfs_test.dist.get(i) << " "; |
120 } |
109 } |
121 std::cout<<std::endl; |
110 std::cout<<std::endl; |
122 |
111 |
123 |
112 |
124 std::cout << "augmenting path flow algorithm test..." << std::endl; |
113 std::cout << "augmenting path flow algorithm test..." << std::endl; |
125 list_graph flow_test; |
114 ListGraph flowG; |
126 |
115 |
127 node_iterator s=flow_test.add_node(); |
116 NodeIt s=flowG.addNode(); |
128 node_iterator v1=flow_test.add_node(); |
117 NodeIt v1=flowG.addNode(); |
129 node_iterator v2=flow_test.add_node(); |
118 NodeIt v2=flowG.addNode(); |
130 node_iterator v3=flow_test.add_node(); |
119 NodeIt v3=flowG.addNode(); |
131 node_iterator v4=flow_test.add_node(); |
120 NodeIt v4=flowG.addNode(); |
132 node_iterator t=flow_test.add_node(); |
121 NodeIt t=flowG.addNode(); |
133 |
122 |
134 node_property_vector<list_graph, std::string> node_name(flow_test); |
123 ListGraph::NodeMap<std::string> node_name(flowG); |
135 node_name.put(s, "s"); |
124 node_name.set(s, "s"); |
136 node_name.put(v1, "v1"); |
125 node_name.set(v1, "v1"); |
137 node_name.put(v2, "v2"); |
126 node_name.set(v2, "v2"); |
138 node_name.put(v3, "v3"); |
127 node_name.set(v3, "v3"); |
139 node_name.put(v4, "v4"); |
128 node_name.set(v4, "v4"); |
140 node_name.put(t, "t"); |
129 node_name.set(t, "t"); |
141 |
130 |
142 edge_iterator s_v1=flow_test.add_edge(s, v1); |
131 EdgeIt s_v1=flowG.addEdge(s, v1); |
143 edge_iterator s_v2=flow_test.add_edge(s, v2); |
132 EdgeIt s_v2=flowG.addEdge(s, v2); |
144 edge_iterator v1_v2=flow_test.add_edge(v1, v2); |
133 EdgeIt v1_v2=flowG.addEdge(v1, v2); |
145 edge_iterator v2_v1=flow_test.add_edge(v2, v1); |
134 EdgeIt v2_v1=flowG.addEdge(v2, v1); |
146 edge_iterator v1_v3=flow_test.add_edge(v1, v3); |
135 EdgeIt v1_v3=flowG.addEdge(v1, v3); |
147 edge_iterator v3_v2=flow_test.add_edge(v3, v2); |
136 EdgeIt v3_v2=flowG.addEdge(v3, v2); |
148 edge_iterator v2_v4=flow_test.add_edge(v2, v4); |
137 EdgeIt v2_v4=flowG.addEdge(v2, v4); |
149 edge_iterator v4_v3=flow_test.add_edge(v4, v3); |
138 EdgeIt v4_v3=flowG.addEdge(v4, v3); |
150 edge_iterator v3_t=flow_test.add_edge(v3, t); |
139 EdgeIt v3_t=flowG.addEdge(v3, t); |
151 edge_iterator v4_t=flow_test.add_edge(v4, t); |
140 EdgeIt v4_t=flowG.addEdge(v4, t); |
152 |
141 |
153 edge_property_vector<list_graph, int> cap(flow_test); |
142 ListGraph::EdgeMap<int> cap(flowG); |
154 |
143 |
155 cap.put(s_v1, 16); |
144 cap.set(s_v1, 16); |
156 cap.put(s_v2, 13); |
145 cap.set(s_v2, 13); |
157 cap.put(v1_v2, 10); |
146 cap.set(v1_v2, 10); |
158 cap.put(v2_v1, 4); |
147 cap.set(v2_v1, 4); |
159 cap.put(v1_v3, 12); |
148 cap.set(v1_v3, 12); |
160 cap.put(v3_v2, 9); |
149 cap.set(v3_v2, 9); |
161 cap.put(v2_v4, 14); |
150 cap.set(v2_v4, 14); |
162 cap.put(v4_v3, 7); |
151 cap.set(v4_v3, 7); |
163 cap.put(v3_t, 20); |
152 cap.set(v3_t, 20); |
164 cap.put(v4_t, 4); |
153 cap.set(v4_t, 4); |
165 |
154 |
166 std::cout << "on directed graph graph" << std::endl; //<< flow_test; |
155 std::cout << "on directed graph graph" << std::endl; //<< flowG; |
167 std::cout << "names and capacity values" << std::endl; |
156 std::cout << "names and capacity values" << std::endl; |
168 for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) { |
157 for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { |
169 std::cout << node_name.get(i) << ": "; |
158 std::cout << node_name.get(i) << ": "; |
170 std::cout << "out edges: "; |
159 std::cout << "out edges: "; |
171 for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j) |
160 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j) |
172 std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " "; |
161 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " "; |
173 std::cout << "in edges: "; |
162 std::cout << "in edges: "; |
174 for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j) |
163 for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j) |
175 std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " "; |
164 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " "; |
176 std::cout << std::endl; |
165 std::cout << std::endl; |
177 } |
166 } |
178 |
167 |
|
168 //flowG.setTail(v3_t, v2); |
|
169 //flowG.setHead(v3_t, s); |
|
170 |
|
171 for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { |
|
172 std::cout << node_name.get(i) << ": "; |
|
173 std::cout << "out edges: "; |
|
174 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j) |
|
175 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " "; |
|
176 std::cout << "in edges: "; |
|
177 for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j) |
|
178 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " "; |
|
179 std::cout << std::endl; |
|
180 } |
179 |
181 |
180 //for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) { |
182 |
181 // std::cout << i << " "; |
183 /* |
182 //} |
184 while (flowG.first<EachEdgeIt>().valid()) { |
|
185 flowG.deleteEdge(flowG.first<EachEdgeIt>()); |
|
186 for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { |
|
187 std::cout << node_name.get(i) << ": "; |
|
188 std::cout << "out edges: "; |
|
189 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j) |
|
190 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " "; |
|
191 std::cout << "in edges: "; |
|
192 for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j) |
|
193 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " "; |
|
194 std::cout << std::endl; |
|
195 } |
|
196 } |
183 |
197 |
184 max_flow_type<list_graph, int> max_flow_test(flow_test, s, t, cap); |
198 while (flowG.first<EachNodeIt>().valid()) { |
|
199 flowG.deleteNode(flowG.first<EachNodeIt>()); |
|
200 for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { |
|
201 std::cout << node_name.get(i) << ": "; |
|
202 std::cout << "out edges: "; |
|
203 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j) |
|
204 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " "; |
|
205 std::cout << "in edges: "; |
|
206 for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j) |
|
207 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " "; |
|
208 std::cout << std::endl; |
|
209 } |
|
210 } |
|
211 */ |
|
212 |
|
213 //ListGraph::EdgeMap<int> flow(flowG, 0); |
|
214 //ResGraph<ListGraph, int> res_graph(flowG, cap, flow); |
|
215 max_flow_type<ListGraph, int> max_flow_test(flowG, s, t, cap); |
185 max_flow_test.run(); |
216 max_flow_test.run(); |
186 |
217 |
187 return 0; |
218 return 0; |
188 } |
219 } |