lemon-0.x: src/work/marci/oldies/marci_graph

     1 #include <iostream>

     2 #include <vector>

     3 #include <string>

     5 #include <list_graph.h>

     6 #include <bfs_iterator.h>

     7 #include <edmonds_karp.h>

     9 using namespace hugo;

    11 int main (int, char*[])

    12 {

    13   typedef ListGraph::Node Node;

    14   typedef ListGraph::Edge Edge;

    15   typedef ListGraph::NodeIt NodeIt;

    16   typedef ListGraph::EdgeIt EdgeIt;

    17   typedef ListGraph::OutEdgeIt OutEdgeIt;

    18   typedef ListGraph::InEdgeIt InEdgeIt;

    19   typedef ListGraph::SymEdgeIt SymEdgeIt;

    20   ListGraph G;

    21   std::vector<Node> vector_of_Nodes;

    22   for(int i=0; i!=8; ++i) vector_of_Nodes.push_back(G.addNode());

    23   for(int i=0; i!=8; ++i)

    24     for(int j=0; j!=8; ++j)

    25       if ((i<j)&&(i+j)%3) G.addEdge(vector_of_Nodes[i], vector_of_Nodes[j]);

    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;

    28   std::cout << "number of nodes: " << count(G.first<NodeIt>()) << std::endl;

    30   for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {

    31     std::cout << "node " << G.id(i) << std::endl;

    32     std::cout << " outdegree (OutEdgeIt): " << count(G.first<OutEdgeIt>(i)) << " ";

    33     for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) {

    34       std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") ";

    35     }

    36     std::cout << std::endl;

    38     std::cout<< " ";

    39     for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) {

    40       std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }

    41     std::cout<<std::endl;

    43     std::cout << " indegree: (InEdgeIt) " << count(G.first<InEdgeIt>(i)) << " ";

    44     for(InEdgeIt j=G.first<InEdgeIt>(i); G.valid(j); G.next(j)) {

    45       std::cout << j << " "; }

    46     std::cout << std::endl;

    48     std::cout<< " ";

    49     for(InEdgeIt j=G.first<InEdgeIt>(i); G.valid(j); G.next(j)) {

    50       std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }

    51     std::cout<<std::endl;

    53     std::cout << " degree: (SymEdgeIt) " << count(G.first<SymEdgeIt>(i)) << " ";

    54     for(SymEdgeIt j=G.first<SymEdgeIt>(i); G.valid(j); G.next(j)) {

    55       std::cout << j << " "; }

    56     std::cout<<std::endl;

    58     std::cout<< " ";

    59     for(SymEdgeIt j=G.first<SymEdgeIt>(i); G.valid(j); G.next(j)) {

    60       std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }

    61     std::cout<<std::endl;

    62   }

    64   std::cout << "all edges: ";

    65   for(EdgeIt i=G.first<EdgeIt>(); G.valid(i); G.next(i)) {

    66     std::cout << i << " ";

    67   }

    68   std::cout << std::endl;

    70   std::cout << "node property array test" << std::endl;

    71   ListGraph::NodeMap<int> my_property_vector(G);

    72   NodeIt v;

    73   G.first(v);

    74   my_property_vector.set(v, 42);

    75   my_property_vector.set(G.next(G.first<NodeIt>()), 314);

    76   my_property_vector.set(G.next(G.next(G.first<NodeIt>())), 1956);

    77   my_property_vector.set(vector_of_Nodes[3], 1989);

    78   my_property_vector.set(vector_of_Nodes[4], 2003);

    79   my_property_vector.set(vector_of_Nodes[7], 1978);

    80   std::cout << "some node property values..." << std::endl;

    81   for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {

    82     std::cout << my_property_vector.get(i) << std::endl;

    83   }

    84   int _i=1;

    85   int _ii=1;

    86   ListGraph::EdgeMap<int> my_edge_property(G);

    87   for(EdgeIt i=G.first<EdgeIt>(); G.valid(i); G.next(i)) {

    88     my_edge_property.set(i, _i);

    89     _i*=_ii; ++_ii;

    90   }

    92   std::cout << "node and edge property values on the tails and heads of edges..." << std::endl;

    93   for(EdgeIt j=G.first<EdgeIt>(); G.valid(j); G.next(j)) {

    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;

    99   bfs<ListGraph> bfs_test(G, G.first<NodeIt>());

   100   bfs_test.run();

   101   std::cout << "reached: ";

   102   for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {

   103     std::cout << bfs_test.reached.get(i) << " ";

   104   }

   105   std::cout<<std::endl;

   106   std::cout << "dist: ";

   107   for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {

   108     std::cout << bfs_test.dist.get(i) << " ";

   109   }

   110   std::cout<<std::endl;

   111 */

   113   std::cout << "augmenting path flow algorithm test..." << std::endl;

   114   ListGraph flowG;

   116   Node s=flowG.addNode();

   117   Node v1=flowG.addNode();

   118   Node v2=flowG.addNode();

   119   Node v3=flowG.addNode();

   120   Node v4=flowG.addNode();

   121   Node t=flowG.addNode();

   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");

   131   Edge s_v1=flowG.addEdge(s, v1);

   132   Edge s_v2=flowG.addEdge(s, v2);

   133   Edge v1_v2=flowG.addEdge(v1, v2);

   134   Edge v2_v1=flowG.addEdge(v2, v1);

   135   Edge v1_v3=flowG.addEdge(v1, v3);

   136   Edge v3_v2=flowG.addEdge(v3, v2);

   137   Edge v2_v4=flowG.addEdge(v2, v4);

   138   Edge v4_v3=flowG.addEdge(v4, v3);

   139   Edge v3_t=flowG.addEdge(v3, t);

   140   Edge v4_t=flowG.addEdge(v4, t);

   142   ListGraph::EdgeMap<int> cap(flowG);

   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);

   155   std::cout << "on directed graph graph" << std::endl; //<< flowG;

   156   std::cout << "names and capacity values" << std::endl;

   157   for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) {

   158     std::cout << node_name.get(i) << ": ";

   159     std::cout << "out edges: ";

   160     for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j))

   161       std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";

   162     std::cout << "in edges: ";

   163     for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j))

   164       std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";

   165     std::cout << std::endl;

   166   }

   168   //flowG.deleteEdge(s_v1);

   169   //flowG.deleteEdge(s_v2);

   170   //flowG.deleteEdge(v1_v2);

   171   //flowG.deleteEdge(v1_v3);

   174   //flowG.setTail(v3_t, v2);

   175   //flowG.setHead(v3_t, s);

   176 /*

   177   for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) {

   178     std::cout << node_name.get(i) << ": ";

   179     std::cout << "out edges: ";

   180     for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(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); flowG.valid(j); flowG.next(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   }

   188   for(EdgeIt e=flowG.first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {

   189     std::cout << node_name.get(flowG.tail(e)) << "-"<< cap.get(e) << "->" << node_name.get(flowG.head(e)) << " ";

   190   }

   191 */

   192   /*

   193   while (flowG.valid(flowG.first<EdgeIt>())) {

   194     flowG.deleteEdge(flowG.first<EdgeIt>());

   195     for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) {

   196       std::cout << node_name.get(i) << ": ";

   197       std::cout << "out edges: ";

   198       for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(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); flowG.valid(j); flowG.next(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   }

   207   while (flowG.valid(flowG.first<NodeIt>())) {

   208     flowG.deleteNode(flowG.first<NodeIt>());

   209     for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) {

   210       std::cout << node_name.get(i) << ": ";

   211       std::cout << "out edges: ";

   212       for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(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); flowG.valid(j); flowG.next(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   */

   222   //std::cout << std::endl;

   225   {

   226     ListGraph::EdgeMap<int> flow(flowG, 0);

   227     MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, s, t, flow, cap);

   228     /*

   229     max_flow_test.augmentOnBlockingFlow<ListGraph>();

   230     for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {

   231       std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";

   232     }

   233     std::cout<<std::endl;

   234     max_flow_test.augmentOnBlockingFlow<ListGraph>();

   235     for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {

   236       std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";

   237     }

   238     std::cout<<std::endl;*/

   239     //max_flow_test.run();

   241     //std::cout << "maximum flow: "<< std::endl;

   242     while (max_flow_test.augmentOnShortestPath()) {

   243       for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {

   244 	std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";

   245       }

   246       std::cout<<std::endl;

   247     }

   248     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;

   249   }

   250 /*

   251   {

   252     std::list<Node> S;

   253     S.push_back(s); S.push_back(v3);

   254     std::list<Node> T;

   255     T.push_back(t);

   257     ListGraph::EdgeMap<int> flow(flowG, 0);

   258     MaxFlow2<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, S, T, flow, cap);

   259     max_flow_test.run();

   261     std::cout << "maximum flow: "<< std::endl;

   262     for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {

   263       std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";

   264     }

   265     std::cout<<std::endl;

   266     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;

   267   }

   268 */

   269   return 0;

   270 }

author	athos
	Tue, 11 May 2004 16:38:17 +0000
changeset 611	83530dad618a
child 921	818510fa3d99
permissions	-rw-r--r--