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