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