1.1 --- a/src/work/marci_graph_demo.cc Sat Apr 03 14:22:33 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,270 +0,0 @@
1.4 -#include <iostream>
1.5 -#include <vector>
1.6 -#include <string>
1.7 -
1.8 -#include <list_graph.h>
1.9 -#include <bfs_iterator.h>
1.10 -#include <edmonds_karp.h>
1.11 -
1.12 -using namespace hugo;
1.13 -
1.14 -int main (int, char*[])
1.15 -{
1.16 - typedef ListGraph::Node Node;
1.17 - typedef ListGraph::Edge Edge;
1.18 - typedef ListGraph::NodeIt NodeIt;
1.19 - typedef ListGraph::EdgeIt EdgeIt;
1.20 - typedef ListGraph::OutEdgeIt OutEdgeIt;
1.21 - typedef ListGraph::InEdgeIt InEdgeIt;
1.22 - typedef ListGraph::SymEdgeIt SymEdgeIt;
1.23 - ListGraph G;
1.24 - std::vector<Node> vector_of_Nodes;
1.25 - for(int i=0; i!=8; ++i) vector_of_Nodes.push_back(G.addNode());
1.26 - for(int i=0; i!=8; ++i)
1.27 - for(int j=0; j!=8; ++j)
1.28 - if ((i<j)&&(i+j)%3) G.addEdge(vector_of_Nodes[i], vector_of_Nodes[j]);
1.29 -
1.30 - 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.31 - std::cout << "number of nodes: " << count(G.first<NodeIt>()) << std::endl;
1.32 -
1.33 - for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
1.34 - std::cout << "node " << G.id(i) << std::endl;
1.35 - std::cout << " outdegree (OutEdgeIt): " << count(G.first<OutEdgeIt>(i)) << " ";
1.36 - for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) {
1.37 - std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") ";
1.38 - }
1.39 - std::cout << std::endl;
1.40 -
1.41 - std::cout<< " ";
1.42 - for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) {
1.43 - std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }
1.44 - std::cout<<std::endl;
1.45 -
1.46 - std::cout << " indegree: (InEdgeIt) " << count(G.first<InEdgeIt>(i)) << " ";
1.47 - for(InEdgeIt j=G.first<InEdgeIt>(i); G.valid(j); G.next(j)) {
1.48 - std::cout << j << " "; }
1.49 - std::cout << std::endl;
1.50 -
1.51 - std::cout<< " ";
1.52 - for(InEdgeIt j=G.first<InEdgeIt>(i); G.valid(j); G.next(j)) {
1.53 - std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }
1.54 - std::cout<<std::endl;
1.55 -
1.56 - std::cout << " degree: (SymEdgeIt) " << count(G.first<SymEdgeIt>(i)) << " ";
1.57 - for(SymEdgeIt j=G.first<SymEdgeIt>(i); G.valid(j); G.next(j)) {
1.58 - std::cout << j << " "; }
1.59 - std::cout<<std::endl;
1.60 -
1.61 - std::cout<< " ";
1.62 - for(SymEdgeIt j=G.first<SymEdgeIt>(i); G.valid(j); G.next(j)) {
1.63 - std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }
1.64 - std::cout<<std::endl;
1.65 - }
1.66 -
1.67 - std::cout << "all edges: ";
1.68 - for(EdgeIt i=G.first<EdgeIt>(); G.valid(i); G.next(i)) {
1.69 - std::cout << i << " ";
1.70 - }
1.71 - std::cout << std::endl;
1.72 -
1.73 - std::cout << "node property array test" << std::endl;
1.74 - ListGraph::NodeMap<int> my_property_vector(G);
1.75 - NodeIt v;
1.76 - G.first(v);
1.77 - my_property_vector.set(v, 42);
1.78 - my_property_vector.set(G.next(G.first<NodeIt>()), 314);
1.79 - my_property_vector.set(G.next(G.next(G.first<NodeIt>())), 1956);
1.80 - my_property_vector.set(vector_of_Nodes[3], 1989);
1.81 - my_property_vector.set(vector_of_Nodes[4], 2003);
1.82 - my_property_vector.set(vector_of_Nodes[7], 1978);
1.83 - std::cout << "some node property values..." << std::endl;
1.84 - for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
1.85 - std::cout << my_property_vector.get(i) << std::endl;
1.86 - }
1.87 - int _i=1;
1.88 - int _ii=1;
1.89 - ListGraph::EdgeMap<int> my_edge_property(G);
1.90 - for(EdgeIt i=G.first<EdgeIt>(); G.valid(i); G.next(i)) {
1.91 - my_edge_property.set(i, _i);
1.92 - _i*=_ii; ++_ii;
1.93 - }
1.94 -
1.95 - std::cout << "node and edge property values on the tails and heads of edges..." << std::endl;
1.96 - for(EdgeIt j=G.first<EdgeIt>(); G.valid(j); G.next(j)) {
1.97 - std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " ";
1.98 - }
1.99 - std::cout << std::endl;
1.100 -/*
1.101 - std::cout << "bfs from the first node" << std::endl;
1.102 - bfs<ListGraph> bfs_test(G, G.first<NodeIt>());
1.103 - bfs_test.run();
1.104 - std::cout << "reached: ";
1.105 - for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
1.106 - std::cout << bfs_test.reached.get(i) << " ";
1.107 - }
1.108 - std::cout<<std::endl;
1.109 - std::cout << "dist: ";
1.110 - for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
1.111 - std::cout << bfs_test.dist.get(i) << " ";
1.112 - }
1.113 - std::cout<<std::endl;
1.114 -*/
1.115 -
1.116 - std::cout << "augmenting path flow algorithm test..." << std::endl;
1.117 - ListGraph flowG;
1.118 -
1.119 - Node s=flowG.addNode();
1.120 - Node v1=flowG.addNode();
1.121 - Node v2=flowG.addNode();
1.122 - Node v3=flowG.addNode();
1.123 - Node v4=flowG.addNode();
1.124 - Node t=flowG.addNode();
1.125 -
1.126 - ListGraph::NodeMap<std::string> node_name(flowG);
1.127 - node_name.set(s, "s");
1.128 - node_name.set(v1, "v1");
1.129 - node_name.set(v2, "v2");
1.130 - node_name.set(v3, "v3");
1.131 - node_name.set(v4, "v4");
1.132 - node_name.set(t, "t");
1.133 -
1.134 - Edge s_v1=flowG.addEdge(s, v1);
1.135 - Edge s_v2=flowG.addEdge(s, v2);
1.136 - Edge v1_v2=flowG.addEdge(v1, v2);
1.137 - Edge v2_v1=flowG.addEdge(v2, v1);
1.138 - Edge v1_v3=flowG.addEdge(v1, v3);
1.139 - Edge v3_v2=flowG.addEdge(v3, v2);
1.140 - Edge v2_v4=flowG.addEdge(v2, v4);
1.141 - Edge v4_v3=flowG.addEdge(v4, v3);
1.142 - Edge v3_t=flowG.addEdge(v3, t);
1.143 - Edge v4_t=flowG.addEdge(v4, t);
1.144 -
1.145 - ListGraph::EdgeMap<int> cap(flowG);
1.146 -
1.147 - cap.set(s_v1, 16);
1.148 - cap.set(s_v2, 13);
1.149 - cap.set(v1_v2, 10);
1.150 - cap.set(v2_v1, 4);
1.151 - cap.set(v1_v3, 12);
1.152 - cap.set(v3_v2, 9);
1.153 - cap.set(v2_v4, 14);
1.154 - cap.set(v4_v3, 7);
1.155 - cap.set(v3_t, 20);
1.156 - cap.set(v4_t, 4);
1.157 -
1.158 - std::cout << "on directed graph graph" << std::endl; //<< flowG;
1.159 - std::cout << "names and capacity values" << std::endl;
1.160 - for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) {
1.161 - std::cout << node_name.get(i) << ": ";
1.162 - std::cout << "out edges: ";
1.163 - for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j))
1.164 - std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
1.165 - std::cout << "in edges: ";
1.166 - for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j))
1.167 - std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
1.168 - std::cout << std::endl;
1.169 - }
1.170 -
1.171 - //flowG.deleteEdge(s_v1);
1.172 - //flowG.deleteEdge(s_v2);
1.173 - //flowG.deleteEdge(v1_v2);
1.174 - //flowG.deleteEdge(v1_v3);
1.175 -
1.176 -
1.177 - //flowG.setTail(v3_t, v2);
1.178 - //flowG.setHead(v3_t, s);
1.179 -/*
1.180 - for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) {
1.181 - std::cout << node_name.get(i) << ": ";
1.182 - std::cout << "out edges: ";
1.183 - for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j))
1.184 - std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
1.185 - std::cout << "in edges: ";
1.186 - for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j))
1.187 - std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
1.188 - std::cout << std::endl;
1.189 - }
1.190 -
1.191 - for(EdgeIt e=flowG.first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
1.192 - std::cout << node_name.get(flowG.tail(e)) << "-"<< cap.get(e) << "->" << node_name.get(flowG.head(e)) << " ";
1.193 - }
1.194 -*/
1.195 - /*
1.196 - while (flowG.valid(flowG.first<EdgeIt>())) {
1.197 - flowG.deleteEdge(flowG.first<EdgeIt>());
1.198 - for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) {
1.199 - std::cout << node_name.get(i) << ": ";
1.200 - std::cout << "out edges: ";
1.201 - for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j))
1.202 - std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
1.203 - std::cout << "in edges: ";
1.204 - for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j))
1.205 - std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
1.206 - std::cout << std::endl;
1.207 - }
1.208 - }
1.209 -
1.210 - while (flowG.valid(flowG.first<NodeIt>())) {
1.211 - flowG.deleteNode(flowG.first<NodeIt>());
1.212 - for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) {
1.213 - std::cout << node_name.get(i) << ": ";
1.214 - std::cout << "out edges: ";
1.215 - for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j))
1.216 - std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
1.217 - std::cout << "in edges: ";
1.218 - for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j))
1.219 - std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
1.220 - std::cout << std::endl;
1.221 - }
1.222 - }
1.223 - */
1.224 -
1.225 - //std::cout << std::endl;
1.226 -
1.227 -
1.228 - {
1.229 - ListGraph::EdgeMap<int> flow(flowG, 0);
1.230 - MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, s, t, flow, cap);
1.231 - /*
1.232 - max_flow_test.augmentOnBlockingFlow<ListGraph>();
1.233 - for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
1.234 - std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
1.235 - }
1.236 - std::cout<<std::endl;
1.237 - max_flow_test.augmentOnBlockingFlow<ListGraph>();
1.238 - for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
1.239 - std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
1.240 - }
1.241 - std::cout<<std::endl;*/
1.242 - //max_flow_test.run();
1.243 -
1.244 - //std::cout << "maximum flow: "<< std::endl;
1.245 - while (max_flow_test.augmentOnShortestPath()) {
1.246 - for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
1.247 - std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
1.248 - }
1.249 - std::cout<<std::endl;
1.250 - }
1.251 - std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.252 - }
1.253 -/*
1.254 - {
1.255 - std::list<Node> S;
1.256 - S.push_back(s); S.push_back(v3);
1.257 - std::list<Node> T;
1.258 - T.push_back(t);
1.259 -
1.260 - ListGraph::EdgeMap<int> flow(flowG, 0);
1.261 - MaxFlow2<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, S, T, flow, cap);
1.262 - max_flow_test.run();
1.263 -
1.264 - std::cout << "maximum flow: "<< std::endl;
1.265 - for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
1.266 - std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
1.267 - }
1.268 - std::cout<<std::endl;
1.269 - std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.270 - }
1.271 -*/
1.272 - return 0;
1.273 -}