1.1 --- a/src/work/marci_graph_demo.cc Fri Jan 30 14:54:32 2004 +0000
1.2 +++ b/src/work/marci_graph_demo.cc Fri Jan 30 14:55:10 2004 +0000
1.3 @@ -2,186 +2,217 @@
1.4 #include <vector>
1.5 #include <string>
1.6
1.7 -#include <marci_list_graph.hh>
1.8 -#include <marci_property_vector.hh>
1.9 -#include <marci_bfs.hh>
1.10 -#include <marci_max_flow.hh>
1.11 +#include <list_graph.hh>
1.12 +#include <bfs_iterator.hh>
1.13 +#include <edmonds_karp.hh>
1.14
1.15 using namespace marci;
1.16
1.17 int main (int, char*[])
1.18 {
1.19 - typedef list_graph::node_iterator node_iterator;
1.20 - typedef list_graph::edge_iterator edge_iterator;
1.21 - typedef list_graph::each_node_iterator each_node_iterator;
1.22 - typedef list_graph::each_edge_iterator each_edge_iterator;
1.23 - typedef list_graph::out_edge_iterator out_edge_iterator;
1.24 - typedef list_graph::in_edge_iterator in_edge_iterator;
1.25 - typedef list_graph::sym_edge_iterator sym_edge_iterator;
1.26 - list_graph G;
1.27 - std::vector<node_iterator> vector_of_node_iterators;
1.28 - for(int i=0; i!=8; ++i) vector_of_node_iterators.push_back(G.add_node());
1.29 + typedef ListGraph::NodeIt NodeIt;
1.30 + typedef ListGraph::EdgeIt EdgeIt;
1.31 + typedef ListGraph::EachNodeIt EachNodeIt;
1.32 + typedef ListGraph::EachEdgeIt EachEdgeIt;
1.33 + typedef ListGraph::OutEdgeIt OutEdgeIt;
1.34 + typedef ListGraph::InEdgeIt InEdgeIt;
1.35 + typedef ListGraph::SymEdgeIt SymEdgeIt;
1.36 + ListGraph G;
1.37 + std::vector<NodeIt> vector_of_NodeIts;
1.38 + for(int i=0; i!=8; ++i) vector_of_NodeIts.push_back(G.addNode());
1.39 for(int i=0; i!=8; ++i)
1.40 - for(int j=0; j!=8; ++j) {
1.41 - if ((i<j)&&(i+j)%3) G.add_edge(vector_of_node_iterators[i], vector_of_node_iterators[j]);
1.42 - }
1.43 + for(int j=0; j!=8; ++j)
1.44 + if ((i<j)&&(i+j)%3) G.addEdge(vector_of_NodeIts[i], vector_of_NodeIts[j]);
1.45
1.46 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;
1.47 - std::cout << "number of nodes: " << number_of(G.first_node()) << std::endl;
1.48 + std::cout << "number of nodes: " << count(G.first<EachNodeIt>()) << std::endl;
1.49
1.50 - for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
1.51 + for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
1.52 std::cout << "node " << G.id(i) << std::endl;
1.53 - std::cout << " outdegree (out_edge_iterator): " << number_of(G.first_out_edge(i)) << " ";
1.54 - for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) {
1.55 + std::cout << " outdegree (OutEdgeIt): " << count(G.first<OutEdgeIt>(i)) << " ";
1.56 + for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) {
1.57 std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") ";
1.58 }
1.59 std::cout << std::endl;
1.60
1.61 std::cout<< " ";
1.62 - for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) {
1.63 - std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; }
1.64 + for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) {
1.65 + std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }
1.66 std::cout<<std::endl;
1.67
1.68 - std::cout << " indegree: (in_edge_oterator) " << number_of(G.first_in_edge(i)) << " ";
1.69 - for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) {
1.70 + std::cout << " indegree: (InEdgeIt) " << count(G.first<InEdgeIt>(i)) << " ";
1.71 + for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) {
1.72 std::cout << j << " "; }
1.73 std::cout << std::endl;
1.74
1.75 std::cout<< " ";
1.76 - for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) {
1.77 - std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; }
1.78 + for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) {
1.79 + std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }
1.80 std::cout<<std::endl;
1.81
1.82 - std::cout << " degree: (sym_edge_iterator) " << number_of(G.first_sym_edge(i)) << " ";
1.83 - for(sym_edge_iterator j=G.first_sym_edge(i); j.valid(); ++j) {
1.84 + std::cout << " degree: (SymEdgeIt) " << count(G.first<SymEdgeIt>(i)) << " ";
1.85 + for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) {
1.86 std::cout << j << " "; }
1.87 std::cout<<std::endl;
1.88
1.89 std::cout<< " ";
1.90 - for(sym_edge_iterator j=G.first_sym_edge(i); j.valid(); ++j) {
1.91 - std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; }
1.92 + for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) {
1.93 + std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }
1.94 std::cout<<std::endl;
1.95 }
1.96
1.97 std::cout << "all edges: ";
1.98 - for(each_edge_iterator i=G.first_edge(); i.valid(); ++i) {
1.99 + for(EachEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) {
1.100 std::cout << i << " ";
1.101 }
1.102 std::cout << std::endl;
1.103
1.104 std::cout << "node property array test" << std::endl;
1.105 - node_property_vector<list_graph, int> my_property_vector(G);
1.106 - each_node_iterator v;
1.107 - G.get_first(v);
1.108 - my_property_vector.put(v, 42);
1.109 - my_property_vector.put(++G.first_node(), 314);
1.110 - my_property_vector.put(++++G.first_node(), 1956);
1.111 - my_property_vector.put(vector_of_node_iterators[3], 1989);
1.112 - my_property_vector.put(vector_of_node_iterators[4], 2003);
1.113 - my_property_vector.put(vector_of_node_iterators[7], 1978);
1.114 + ListGraph::NodeMap<int> my_property_vector(G);
1.115 + EachNodeIt v;
1.116 + G.getFirst(v);
1.117 + my_property_vector.set(v, 42);
1.118 + my_property_vector.set(++G.first<EachNodeIt>(), 314);
1.119 + my_property_vector.set(++++G.first<EachNodeIt>(), 1956);
1.120 + my_property_vector.set(vector_of_NodeIts[3], 1989);
1.121 + my_property_vector.set(vector_of_NodeIts[4], 2003);
1.122 + my_property_vector.set(vector_of_NodeIts[7], 1978);
1.123 std::cout << "some node property values..." << std::endl;
1.124 - for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
1.125 + for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
1.126 std::cout << my_property_vector.get(i) << std::endl;
1.127 }
1.128 int _i=1;
1.129 int _ii=1;
1.130 - edge_property_vector<list_graph, int> my_edge_property(G);
1.131 - for(each_edge_iterator i=G.first_edge(); i.valid(); ++i) {
1.132 - my_edge_property.put(i, _i);
1.133 + ListGraph::EdgeMap<int> my_edge_property(G);
1.134 + for(EachEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) {
1.135 + my_edge_property.set(i, _i);
1.136 _i*=_ii; ++_ii;
1.137 }
1.138
1.139 std::cout << "node and edge property values on the tails and heads of edges..." << std::endl;
1.140 - for(each_edge_iterator j=G.first_edge(); j.valid(); ++j) {
1.141 + for(EachEdgeIt j=G.first<EachEdgeIt>(); j.valid(); ++j) {
1.142 std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " ";
1.143 }
1.144 std::cout << std::endl;
1.145
1.146 - //std::cout << "the same for inedges of the nodes..." << std::endl;
1.147 - //k=0;
1.148 - //for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
1.149 - // for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) {
1.150 - // std::cout << my_property_vector.get(G.tail(j)) << "-->" << my_property_vector.get(G.head(j)) << " ";
1.151 - // }
1.152 - // std::cout << std::endl;
1.153 - //}
1.154 -
1.155 std::cout << "bfs from the first node" << std::endl;
1.156 - bfs<list_graph> bfs_test(G, G.first_node());
1.157 + bfs<ListGraph> bfs_test(G, G.first<EachNodeIt>());
1.158 bfs_test.run();
1.159 std::cout << "reached: ";
1.160 - for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
1.161 + for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
1.162 std::cout << bfs_test.reached.get(i) << " ";
1.163 }
1.164 std::cout<<std::endl;
1.165 std::cout << "dist: ";
1.166 - for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
1.167 + for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
1.168 std::cout << bfs_test.dist.get(i) << " ";
1.169 }
1.170 std::cout<<std::endl;
1.171
1.172
1.173 std::cout << "augmenting path flow algorithm test..." << std::endl;
1.174 - list_graph flow_test;
1.175 + ListGraph flowG;
1.176
1.177 - node_iterator s=flow_test.add_node();
1.178 - node_iterator v1=flow_test.add_node();
1.179 - node_iterator v2=flow_test.add_node();
1.180 - node_iterator v3=flow_test.add_node();
1.181 - node_iterator v4=flow_test.add_node();
1.182 - node_iterator t=flow_test.add_node();
1.183 + NodeIt s=flowG.addNode();
1.184 + NodeIt v1=flowG.addNode();
1.185 + NodeIt v2=flowG.addNode();
1.186 + NodeIt v3=flowG.addNode();
1.187 + NodeIt v4=flowG.addNode();
1.188 + NodeIt t=flowG.addNode();
1.189
1.190 - node_property_vector<list_graph, std::string> node_name(flow_test);
1.191 - node_name.put(s, "s");
1.192 - node_name.put(v1, "v1");
1.193 - node_name.put(v2, "v2");
1.194 - node_name.put(v3, "v3");
1.195 - node_name.put(v4, "v4");
1.196 - node_name.put(t, "t");
1.197 + ListGraph::NodeMap<std::string> node_name(flowG);
1.198 + node_name.set(s, "s");
1.199 + node_name.set(v1, "v1");
1.200 + node_name.set(v2, "v2");
1.201 + node_name.set(v3, "v3");
1.202 + node_name.set(v4, "v4");
1.203 + node_name.set(t, "t");
1.204
1.205 - edge_iterator s_v1=flow_test.add_edge(s, v1);
1.206 - edge_iterator s_v2=flow_test.add_edge(s, v2);
1.207 - edge_iterator v1_v2=flow_test.add_edge(v1, v2);
1.208 - edge_iterator v2_v1=flow_test.add_edge(v2, v1);
1.209 - edge_iterator v1_v3=flow_test.add_edge(v1, v3);
1.210 - edge_iterator v3_v2=flow_test.add_edge(v3, v2);
1.211 - edge_iterator v2_v4=flow_test.add_edge(v2, v4);
1.212 - edge_iterator v4_v3=flow_test.add_edge(v4, v3);
1.213 - edge_iterator v3_t=flow_test.add_edge(v3, t);
1.214 - edge_iterator v4_t=flow_test.add_edge(v4, t);
1.215 + EdgeIt s_v1=flowG.addEdge(s, v1);
1.216 + EdgeIt s_v2=flowG.addEdge(s, v2);
1.217 + EdgeIt v1_v2=flowG.addEdge(v1, v2);
1.218 + EdgeIt v2_v1=flowG.addEdge(v2, v1);
1.219 + EdgeIt v1_v3=flowG.addEdge(v1, v3);
1.220 + EdgeIt v3_v2=flowG.addEdge(v3, v2);
1.221 + EdgeIt v2_v4=flowG.addEdge(v2, v4);
1.222 + EdgeIt v4_v3=flowG.addEdge(v4, v3);
1.223 + EdgeIt v3_t=flowG.addEdge(v3, t);
1.224 + EdgeIt v4_t=flowG.addEdge(v4, t);
1.225
1.226 - edge_property_vector<list_graph, int> cap(flow_test);
1.227 + ListGraph::EdgeMap<int> cap(flowG);
1.228
1.229 - cap.put(s_v1, 16);
1.230 - cap.put(s_v2, 13);
1.231 - cap.put(v1_v2, 10);
1.232 - cap.put(v2_v1, 4);
1.233 - cap.put(v1_v3, 12);
1.234 - cap.put(v3_v2, 9);
1.235 - cap.put(v2_v4, 14);
1.236 - cap.put(v4_v3, 7);
1.237 - cap.put(v3_t, 20);
1.238 - cap.put(v4_t, 4);
1.239 + cap.set(s_v1, 16);
1.240 + cap.set(s_v2, 13);
1.241 + cap.set(v1_v2, 10);
1.242 + cap.set(v2_v1, 4);
1.243 + cap.set(v1_v3, 12);
1.244 + cap.set(v3_v2, 9);
1.245 + cap.set(v2_v4, 14);
1.246 + cap.set(v4_v3, 7);
1.247 + cap.set(v3_t, 20);
1.248 + cap.set(v4_t, 4);
1.249
1.250 - std::cout << "on directed graph graph" << std::endl; //<< flow_test;
1.251 + std::cout << "on directed graph graph" << std::endl; //<< flowG;
1.252 std::cout << "names and capacity values" << std::endl;
1.253 - for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) {
1.254 + for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {
1.255 std::cout << node_name.get(i) << ": ";
1.256 std::cout << "out edges: ";
1.257 - for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j)
1.258 - std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
1.259 + for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)
1.260 + std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
1.261 std::cout << "in edges: ";
1.262 - for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j)
1.263 - std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
1.264 + for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)
1.265 + std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
1.266 std::cout << std::endl;
1.267 }
1.268
1.269 + //flowG.setTail(v3_t, v2);
1.270 + //flowG.setHead(v3_t, s);
1.271 +
1.272 + for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {
1.273 + std::cout << node_name.get(i) << ": ";
1.274 + std::cout << "out edges: ";
1.275 + for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)
1.276 + std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
1.277 + std::cout << "in edges: ";
1.278 + for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)
1.279 + std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
1.280 + std::cout << std::endl;
1.281 + }
1.282
1.283 - //for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) {
1.284 - // std::cout << i << " ";
1.285 - //}
1.286 +
1.287 + /*
1.288 + while (flowG.first<EachEdgeIt>().valid()) {
1.289 + flowG.deleteEdge(flowG.first<EachEdgeIt>());
1.290 + for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {
1.291 + std::cout << node_name.get(i) << ": ";
1.292 + std::cout << "out edges: ";
1.293 + for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)
1.294 + std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
1.295 + std::cout << "in edges: ";
1.296 + for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)
1.297 + std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
1.298 + std::cout << std::endl;
1.299 + }
1.300 + }
1.301
1.302 - max_flow_type<list_graph, int> max_flow_test(flow_test, s, t, cap);
1.303 + while (flowG.first<EachNodeIt>().valid()) {
1.304 + flowG.deleteNode(flowG.first<EachNodeIt>());
1.305 + for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {
1.306 + std::cout << node_name.get(i) << ": ";
1.307 + std::cout << "out edges: ";
1.308 + for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)
1.309 + std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
1.310 + std::cout << "in edges: ";
1.311 + for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)
1.312 + std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
1.313 + std::cout << std::endl;
1.314 + }
1.315 + }
1.316 + */
1.317 +
1.318 + //ListGraph::EdgeMap<int> flow(flowG, 0);
1.319 + //ResGraph<ListGraph, int> res_graph(flowG, cap, flow);
1.320 + max_flow_type<ListGraph, int> max_flow_test(flowG, s, t, cap);
1.321 max_flow_test.run();
1.322
1.323 return 0;