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 <marci_list_graph.hh> |
6 #include <marci_graph_traits.hh> |
|
7 #include <marci_property_vector.hh> |
6 #include <marci_property_vector.hh> |
8 #include <marci_bfs.hh> |
7 #include <marci_bfs.hh> |
9 #include <marci_max_flow.hh> |
8 #include <marci_max_flow.hh> |
10 |
9 |
11 using namespace marci; |
10 using namespace marci; |
12 |
11 |
13 int main (int, char*[]) |
12 int main (int, char*[]) |
14 { |
13 { |
15 typedef graph_traits<list_graph>::node_iterator node_iterator; |
14 typedef list_graph::node_iterator node_iterator; |
16 typedef graph_traits<list_graph>::edge_iterator edge_iterator; |
15 typedef list_graph::edge_iterator edge_iterator; |
17 typedef graph_traits<list_graph>::each_node_iterator each_node_iterator; |
16 typedef list_graph::each_node_iterator each_node_iterator; |
18 typedef graph_traits<list_graph>::each_edge_iterator each_edge_iterator; |
17 typedef list_graph::each_edge_iterator each_edge_iterator; |
19 typedef graph_traits<list_graph>::out_edge_iterator out_edge_iterator; |
18 typedef list_graph::out_edge_iterator out_edge_iterator; |
20 typedef graph_traits<list_graph>::in_edge_iterator in_edge_iterator; |
19 typedef list_graph::in_edge_iterator in_edge_iterator; |
21 typedef graph_traits<list_graph>::sym_edge_iterator sym_edge_iterator; |
20 typedef list_graph::sym_edge_iterator sym_edge_iterator; |
22 |
|
23 list_graph G; |
21 list_graph G; |
24 std::vector<node_iterator> vector_of_node_iterators; |
22 std::vector<node_iterator> vector_of_node_iterators; |
25 for(int i=0; i!=8; ++i) vector_of_node_iterators.push_back(G.add_node()); |
23 for(int i=0; i!=8; ++i) vector_of_node_iterators.push_back(G.add_node()); |
26 for(int i=0; i!=8; ++i) |
24 for(int i=0; i!=8; ++i) |
27 for(int j=0; j!=8; ++j) { |
25 for(int j=0; j!=8; ++j) { |
29 } |
27 } |
30 |
28 |
31 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; |
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; |
32 std::cout << "number of nodes: " << number_of(G.first_node()) << std::endl; |
30 std::cout << "number of nodes: " << number_of(G.first_node()) << std::endl; |
33 |
31 |
34 for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) { |
32 for(each_node_iterator i=G.first_node(); i.valid(); ++i) { |
35 std::cout << "node " << G.id(i) << std::endl; |
33 std::cout << "node " << G.id(i) << std::endl; |
36 std::cout << " outdegree (out_edge_iterator): " << number_of(G.first_out_edge(i)) << " "; |
34 std::cout << " outdegree (out_edge_iterator): " << number_of(G.first_out_edge(i)) << " "; |
37 for(out_edge_iterator j=G.first_out_edge(i); j.is_valid(); ++j) { |
35 for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) { |
38 std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") "; |
36 std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") "; |
39 } |
37 } |
40 std::cout << std::endl; |
38 std::cout << std::endl; |
41 |
39 |
42 std::cout<< " "; |
40 std::cout<< " "; |
43 for(out_edge_iterator j=G.first_out_edge(i); j.is_valid(); ++j) { |
41 for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) { |
44 std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; } |
42 std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; } |
45 std::cout<<std::endl; |
43 std::cout<<std::endl; |
46 |
44 |
47 std::cout << " indegree: (in_edge_oterator) " << number_of(G.first_in_edge(i)) << " "; |
45 std::cout << " indegree: (in_edge_oterator) " << number_of(G.first_in_edge(i)) << " "; |
48 for(in_edge_iterator j=G.first_in_edge(i); j.is_valid(); ++j) { |
46 for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) { |
49 std::cout << j << " "; } |
47 std::cout << j << " "; } |
50 std::cout << std::endl; |
48 std::cout << std::endl; |
51 |
49 |
52 std::cout<< " "; |
50 std::cout<< " "; |
53 for(in_edge_iterator j=G.first_in_edge(i); j.is_valid(); ++j) { |
51 for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) { |
54 std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; } |
52 std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; } |
55 std::cout<<std::endl; |
53 std::cout<<std::endl; |
56 |
54 |
57 std::cout << " degree: (sym_edge_iterator) " << number_of(G.first_sym_edge(i)) << " "; |
55 std::cout << " degree: (sym_edge_iterator) " << number_of(G.first_sym_edge(i)) << " "; |
58 for(sym_edge_iterator j=G.first_sym_edge(i); j.is_valid(); ++j) { |
56 for(sym_edge_iterator j=G.first_sym_edge(i); j.valid(); ++j) { |
59 std::cout << j << " "; } |
57 std::cout << j << " "; } |
60 std::cout<<std::endl; |
58 std::cout<<std::endl; |
61 |
59 |
62 std::cout<< " "; |
60 std::cout<< " "; |
63 for(sym_edge_iterator j=G.first_sym_edge(i); j.is_valid(); ++j) { |
61 for(sym_edge_iterator j=G.first_sym_edge(i); j.valid(); ++j) { |
64 std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; } |
62 std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; } |
65 std::cout<<std::endl; |
63 std::cout<<std::endl; |
66 } |
64 } |
67 |
65 |
68 std::cout << "all edges: "; |
66 std::cout << "all edges: "; |
69 for(each_edge_iterator i=G.first_edge(); i.is_valid(); ++i) { |
67 for(each_edge_iterator i=G.first_edge(); i.valid(); ++i) { |
70 std::cout << i << " "; |
68 std::cout << i << " "; |
71 } |
69 } |
72 std::cout << std::endl; |
70 std::cout << std::endl; |
73 |
71 |
74 std::cout << "node property array test" << std::endl; |
72 std::cout << "node property array test" << std::endl; |
80 my_property_vector.put(++++G.first_node(), 1956); |
78 my_property_vector.put(++++G.first_node(), 1956); |
81 my_property_vector.put(vector_of_node_iterators[3], 1989); |
79 my_property_vector.put(vector_of_node_iterators[3], 1989); |
82 my_property_vector.put(vector_of_node_iterators[4], 2003); |
80 my_property_vector.put(vector_of_node_iterators[4], 2003); |
83 my_property_vector.put(vector_of_node_iterators[7], 1978); |
81 my_property_vector.put(vector_of_node_iterators[7], 1978); |
84 std::cout << "some node property values..." << std::endl; |
82 std::cout << "some node property values..." << std::endl; |
85 for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) { |
83 for(each_node_iterator i=G.first_node(); i.valid(); ++i) { |
86 std::cout << my_property_vector.get(i) << std::endl; |
84 std::cout << my_property_vector.get(i) << std::endl; |
87 } |
85 } |
88 int _i=1; |
86 int _i=1; |
89 int _ii=1; |
87 int _ii=1; |
90 edge_property_vector<list_graph, int> my_edge_property(G); |
88 edge_property_vector<list_graph, int> my_edge_property(G); |
91 for(each_edge_iterator i=G.first_edge(); i.is_valid(); ++i) { |
89 for(each_edge_iterator i=G.first_edge(); i.valid(); ++i) { |
92 my_edge_property.put(i, _i); |
90 my_edge_property.put(i, _i); |
93 _i*=_ii; ++_ii; |
91 _i*=_ii; ++_ii; |
94 } |
92 } |
95 |
93 |
96 std::cout << "node and edge property values on the tails and heads of edges..." << std::endl; |
94 std::cout << "node and edge property values on the tails and heads of edges..." << std::endl; |
97 for(each_edge_iterator j=G.first_edge(); j.is_valid(); ++j) { |
95 for(each_edge_iterator j=G.first_edge(); j.valid(); ++j) { |
98 std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " "; |
96 std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " "; |
99 } |
97 } |
100 std::cout << std::endl; |
98 std::cout << std::endl; |
101 |
99 |
102 //std::cout << "the same for inedges of the nodes..." << std::endl; |
100 //std::cout << "the same for inedges of the nodes..." << std::endl; |
103 //k=0; |
101 //k=0; |
104 //for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) { |
102 //for(each_node_iterator i=G.first_node(); i.valid(); ++i) { |
105 // for(in_edge_iterator j=G.first_in_edge(i); j.is_valid(); ++j) { |
103 // for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) { |
106 // std::cout << my_property_vector.get(G.tail(j)) << "-->" << my_property_vector.get(G.head(j)) << " "; |
104 // std::cout << my_property_vector.get(G.tail(j)) << "-->" << my_property_vector.get(G.head(j)) << " "; |
107 // } |
105 // } |
108 // std::cout << std::endl; |
106 // std::cout << std::endl; |
109 //} |
107 //} |
110 |
108 |
111 std::cout << "bfs from the first node" << std::endl; |
109 std::cout << "bfs from the first node" << std::endl; |
112 bfs<list_graph> bfs_test(G, G.first_node()); |
110 bfs<list_graph> bfs_test(G, G.first_node()); |
113 bfs_test.run(); |
111 bfs_test.run(); |
114 std::cout << "reached: "; |
112 std::cout << "reached: "; |
115 for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) { |
113 for(each_node_iterator i=G.first_node(); i.valid(); ++i) { |
116 std::cout << bfs_test.reached.get(i) << " "; |
114 std::cout << bfs_test.reached.get(i) << " "; |
117 } |
115 } |
118 std::cout<<std::endl; |
116 std::cout<<std::endl; |
119 std::cout << "dist: "; |
117 std::cout << "dist: "; |
120 for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) { |
118 for(each_node_iterator i=G.first_node(); i.valid(); ++i) { |
121 std::cout << bfs_test.dist.get(i) << " "; |
119 std::cout << bfs_test.dist.get(i) << " "; |
122 } |
120 } |
123 std::cout<<std::endl; |
121 std::cout<<std::endl; |
124 |
122 |
125 |
123 |
165 cap.put(v3_t, 20); |
163 cap.put(v3_t, 20); |
166 cap.put(v4_t, 4); |
164 cap.put(v4_t, 4); |
167 |
165 |
168 std::cout << "on directed graph graph" << std::endl; //<< flow_test; |
166 std::cout << "on directed graph graph" << std::endl; //<< flow_test; |
169 std::cout << "names and capacity values" << std::endl; |
167 std::cout << "names and capacity values" << std::endl; |
170 for(each_node_iterator i=flow_test.first_node(); i.is_valid(); ++i) { |
168 for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) { |
171 std::cout << node_name.get(i) << ": "; |
169 std::cout << node_name.get(i) << ": "; |
172 std::cout << "out edges: "; |
170 std::cout << "out edges: "; |
173 for(out_edge_iterator j=flow_test.first_out_edge(i); j.is_valid(); ++j) |
171 for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j) |
174 std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " "; |
172 std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " "; |
175 std::cout << "in edges: "; |
173 std::cout << "in edges: "; |
176 for(in_edge_iterator j=flow_test.first_in_edge(i); j.is_valid(); ++j) |
174 for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j) |
177 std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " "; |
175 std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " "; |
178 std::cout << std::endl; |
176 std::cout << std::endl; |
179 } |
177 } |
180 |
178 |
181 |
179 |
182 //for(each_node_iterator i=flow_test.first_node(); i.is_valid(); ++i) { |
180 //for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) { |
183 // std::cout << i << " "; |
181 // std::cout << i << " "; |
184 //} |
182 //} |
185 |
183 |
186 max_flow_type<list_graph, int> max_flow_test(flow_test, s, t, cap); |
184 max_flow_type<list_graph, int> max_flow_test(flow_test, s, t, cap); |
187 max_flow_test.run(); |
185 max_flow_test.run(); |