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