1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/marci/oldies/marci_graph_demo.cc Sat Apr 03 14:41:31 2004 +0000
1.3 @@ -0,0 +1,270 @@
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 +}