[9] | 1 | #include <iostream> |
---|
| 2 | #include <vector> |
---|
| 3 | #include <string> |
---|
| 4 | |
---|
| 5 | #include <marci_list_graph.hh> |
---|
| 6 | #include <marci_property_vector.hh> |
---|
| 7 | #include <marci_bfs.hh> |
---|
| 8 | #include <marci_max_flow.hh> |
---|
| 9 | |
---|
| 10 | using namespace marci; |
---|
| 11 | |
---|
| 12 | int main (int, char*[]) |
---|
| 13 | { |
---|
[19] | 14 | typedef list_graph::node_iterator node_iterator; |
---|
| 15 | typedef list_graph::edge_iterator edge_iterator; |
---|
| 16 | typedef list_graph::each_node_iterator each_node_iterator; |
---|
| 17 | typedef list_graph::each_edge_iterator each_edge_iterator; |
---|
| 18 | typedef list_graph::out_edge_iterator out_edge_iterator; |
---|
| 19 | typedef list_graph::in_edge_iterator in_edge_iterator; |
---|
| 20 | typedef list_graph::sym_edge_iterator sym_edge_iterator; |
---|
[9] | 21 | list_graph G; |
---|
| 22 | std::vector<node_iterator> vector_of_node_iterators; |
---|
| 23 | for(int i=0; i!=8; ++i) vector_of_node_iterators.push_back(G.add_node()); |
---|
| 24 | for(int i=0; i!=8; ++i) |
---|
| 25 | 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]); |
---|
| 27 | } |
---|
| 28 | |
---|
| 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; |
---|
[12] | 30 | std::cout << "number of nodes: " << number_of(G.first_node()) << std::endl; |
---|
[9] | 31 | |
---|
[19] | 32 | for(each_node_iterator i=G.first_node(); i.valid(); ++i) { |
---|
[9] | 33 | std::cout << "node " << G.id(i) << std::endl; |
---|
| 34 | std::cout << " outdegree (out_edge_iterator): " << number_of(G.first_out_edge(i)) << " "; |
---|
[19] | 35 | for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) { |
---|
[9] | 36 | std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") "; |
---|
| 37 | } |
---|
| 38 | std::cout << std::endl; |
---|
[12] | 39 | |
---|
| 40 | std::cout<< " "; |
---|
[19] | 41 | for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) { |
---|
[12] | 42 | std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; } |
---|
| 43 | std::cout<<std::endl; |
---|
| 44 | |
---|
[9] | 45 | std::cout << " indegree: (in_edge_oterator) " << number_of(G.first_in_edge(i)) << " "; |
---|
[19] | 46 | for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) { |
---|
[9] | 47 | std::cout << j << " "; } |
---|
| 48 | std::cout << std::endl; |
---|
[12] | 49 | |
---|
| 50 | std::cout<< " "; |
---|
[19] | 51 | for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) { |
---|
[12] | 52 | std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; } |
---|
| 53 | std::cout<<std::endl; |
---|
| 54 | |
---|
[9] | 55 | std::cout << " degree: (sym_edge_iterator) " << number_of(G.first_sym_edge(i)) << " "; |
---|
[19] | 56 | for(sym_edge_iterator j=G.first_sym_edge(i); j.valid(); ++j) { |
---|
[9] | 57 | std::cout << j << " "; } |
---|
| 58 | std::cout<<std::endl; |
---|
[12] | 59 | |
---|
| 60 | std::cout<< " "; |
---|
[19] | 61 | for(sym_edge_iterator j=G.first_sym_edge(i); j.valid(); ++j) { |
---|
[12] | 62 | std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; } |
---|
| 63 | std::cout<<std::endl; |
---|
[9] | 64 | } |
---|
| 65 | |
---|
| 66 | std::cout << "all edges: "; |
---|
[19] | 67 | for(each_edge_iterator i=G.first_edge(); i.valid(); ++i) { |
---|
[9] | 68 | std::cout << i << " "; |
---|
| 69 | } |
---|
| 70 | std::cout << std::endl; |
---|
| 71 | |
---|
| 72 | std::cout << "node property array test" << std::endl; |
---|
| 73 | node_property_vector<list_graph, int> my_property_vector(G); |
---|
| 74 | each_node_iterator v; |
---|
| 75 | G.get_first(v); |
---|
| 76 | my_property_vector.put(v, 42); |
---|
| 77 | my_property_vector.put(++G.first_node(), 314); |
---|
| 78 | my_property_vector.put(++++G.first_node(), 1956); |
---|
| 79 | my_property_vector.put(vector_of_node_iterators[3], 1989); |
---|
| 80 | my_property_vector.put(vector_of_node_iterators[4], 2003); |
---|
| 81 | my_property_vector.put(vector_of_node_iterators[7], 1978); |
---|
| 82 | std::cout << "some node property values..." << std::endl; |
---|
[19] | 83 | for(each_node_iterator i=G.first_node(); i.valid(); ++i) { |
---|
[9] | 84 | std::cout << my_property_vector.get(i) << std::endl; |
---|
| 85 | } |
---|
| 86 | int _i=1; |
---|
| 87 | int _ii=1; |
---|
| 88 | edge_property_vector<list_graph, int> my_edge_property(G); |
---|
[19] | 89 | for(each_edge_iterator i=G.first_edge(); i.valid(); ++i) { |
---|
[9] | 90 | my_edge_property.put(i, _i); |
---|
| 91 | _i*=_ii; ++_ii; |
---|
| 92 | } |
---|
| 93 | |
---|
| 94 | std::cout << "node and edge property values on the tails and heads of edges..." << std::endl; |
---|
[19] | 95 | for(each_edge_iterator j=G.first_edge(); j.valid(); ++j) { |
---|
[9] | 96 | std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " "; |
---|
| 97 | } |
---|
| 98 | std::cout << std::endl; |
---|
| 99 | |
---|
| 100 | //std::cout << "the same for inedges of the nodes..." << std::endl; |
---|
| 101 | //k=0; |
---|
[19] | 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) { |
---|
[9] | 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; |
---|
| 110 | bfs<list_graph> bfs_test(G, G.first_node()); |
---|
| 111 | bfs_test.run(); |
---|
| 112 | std::cout << "reached: "; |
---|
[19] | 113 | for(each_node_iterator i=G.first_node(); i.valid(); ++i) { |
---|
[9] | 114 | std::cout << bfs_test.reached.get(i) << " "; |
---|
| 115 | } |
---|
| 116 | std::cout<<std::endl; |
---|
| 117 | std::cout << "dist: "; |
---|
[19] | 118 | for(each_node_iterator i=G.first_node(); i.valid(); ++i) { |
---|
[9] | 119 | std::cout << bfs_test.dist.get(i) << " "; |
---|
| 120 | } |
---|
| 121 | std::cout<<std::endl; |
---|
| 122 | |
---|
| 123 | |
---|
| 124 | std::cout << "augmenting path flow algorithm test..." << std::endl; |
---|
| 125 | list_graph flow_test; |
---|
| 126 | |
---|
| 127 | node_iterator s=flow_test.add_node(); |
---|
| 128 | node_iterator v1=flow_test.add_node(); |
---|
| 129 | node_iterator v2=flow_test.add_node(); |
---|
| 130 | node_iterator v3=flow_test.add_node(); |
---|
| 131 | node_iterator v4=flow_test.add_node(); |
---|
| 132 | node_iterator t=flow_test.add_node(); |
---|
| 133 | |
---|
| 134 | node_property_vector<list_graph, std::string> node_name(flow_test); |
---|
| 135 | node_name.put(s, "s"); |
---|
| 136 | node_name.put(v1, "v1"); |
---|
| 137 | node_name.put(v2, "v2"); |
---|
| 138 | node_name.put(v3, "v3"); |
---|
| 139 | node_name.put(v4, "v4"); |
---|
| 140 | node_name.put(t, "t"); |
---|
| 141 | |
---|
| 142 | edge_iterator s_v1=flow_test.add_edge(s, v1); |
---|
| 143 | edge_iterator s_v2=flow_test.add_edge(s, v2); |
---|
| 144 | edge_iterator v1_v2=flow_test.add_edge(v1, v2); |
---|
| 145 | edge_iterator v2_v1=flow_test.add_edge(v2, v1); |
---|
| 146 | edge_iterator v1_v3=flow_test.add_edge(v1, v3); |
---|
| 147 | edge_iterator v3_v2=flow_test.add_edge(v3, v2); |
---|
| 148 | edge_iterator v2_v4=flow_test.add_edge(v2, v4); |
---|
| 149 | edge_iterator v4_v3=flow_test.add_edge(v4, v3); |
---|
| 150 | edge_iterator v3_t=flow_test.add_edge(v3, t); |
---|
| 151 | edge_iterator v4_t=flow_test.add_edge(v4, t); |
---|
| 152 | |
---|
| 153 | edge_property_vector<list_graph, int> cap(flow_test); |
---|
| 154 | |
---|
| 155 | cap.put(s_v1, 16); |
---|
| 156 | cap.put(s_v2, 13); |
---|
| 157 | cap.put(v1_v2, 10); |
---|
| 158 | cap.put(v2_v1, 4); |
---|
| 159 | cap.put(v1_v3, 12); |
---|
| 160 | cap.put(v3_v2, 9); |
---|
| 161 | cap.put(v2_v4, 14); |
---|
| 162 | cap.put(v4_v3, 7); |
---|
| 163 | cap.put(v3_t, 20); |
---|
| 164 | cap.put(v4_t, 4); |
---|
| 165 | |
---|
| 166 | std::cout << "on directed graph graph" << std::endl; //<< flow_test; |
---|
| 167 | std::cout << "names and capacity values" << std::endl; |
---|
[19] | 168 | for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) { |
---|
[9] | 169 | std::cout << node_name.get(i) << ": "; |
---|
| 170 | std::cout << "out edges: "; |
---|
[19] | 171 | for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j) |
---|
[9] | 172 | std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " "; |
---|
| 173 | std::cout << "in edges: "; |
---|
[19] | 174 | for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j) |
---|
[9] | 175 | std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " "; |
---|
| 176 | std::cout << std::endl; |
---|
| 177 | } |
---|
| 178 | |
---|
| 179 | |
---|
[19] | 180 | //for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) { |
---|
[9] | 181 | // std::cout << i << " "; |
---|
| 182 | //} |
---|
| 183 | |
---|
| 184 | max_flow_type<list_graph, int> max_flow_test(flow_test, s, t, cap); |
---|
| 185 | max_flow_test.run(); |
---|
| 186 | |
---|
| 187 | return 0; |
---|
| 188 | } |
---|