lemon-0.x: src/work/marci_graph_demo.cc@6364b07f8cd4

     1 #include <iostream>

     2 #include <vector>

     3 #include <string>

     5 #include <list_graph.hh>

     6 #include <bfs_iterator.hh>

     7 #include <edmonds_karp.hh>

     9 using namespace hugo;

    11 int main (int, char*[])

    12 {

    13   typedef ListGraph::NodeIt NodeIt;

    14   typedef ListGraph::EdgeIt EdgeIt;

    15   typedef ListGraph::EachNodeIt EachNodeIt;

    16   typedef ListGraph::EachEdgeIt EachEdgeIt;

    17   typedef ListGraph::OutEdgeIt OutEdgeIt;

    18   typedef ListGraph::InEdgeIt InEdgeIt;

    19   typedef ListGraph::SymEdgeIt SymEdgeIt;

    20   ListGraph G;

    21   std::vector<NodeIt> vector_of_NodeIts;

    22   for(int i=0; i!=8; ++i) vector_of_NodeIts.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_NodeIts[i], vector_of_NodeIts[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<EachNodeIt>()) << std::endl;

    30   for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++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); j.valid(); ++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); j.valid(); ++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); j.valid(); ++j) {

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

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

    48     std::cout<< " ";

    49     for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++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); j.valid(); ++j) {

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

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

    58     std::cout<< " ";

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

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

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

    62   }

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

    65   for(EachEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++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   EachNodeIt v;

    73   G.getFirst(v);

    74   my_property_vector.set(v, 42);

    75   my_property_vector.set(++G.first<EachNodeIt>(), 314);

    76   my_property_vector.set(++++G.first<EachNodeIt>(), 1956);

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

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

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

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

    81   for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++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(EachEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++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(EachEdgeIt j=G.first<EachEdgeIt>(); j.valid(); ++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<EachNodeIt>());

   100   bfs_test.run();

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

   102   for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {

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

   104   }

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

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

   107   for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++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   NodeIt s=flowG.addNode();

   117   NodeIt v1=flowG.addNode();

   118   NodeIt v2=flowG.addNode();

   119   NodeIt v3=flowG.addNode();

   120   NodeIt v4=flowG.addNode();

   121   NodeIt 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   EdgeIt s_v1=flowG.addEdge(s, v1);

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

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

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

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

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

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

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

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

   140   EdgeIt 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(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {

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

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

   160     for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++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); j.valid(); ++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(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {

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

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

   180     for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++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); j.valid(); ++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(EachEdgeIt e=flowG.first<EachEdgeIt>(); e.valid(); ++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.first<EachEdgeIt>().valid()) {

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

   195     for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {

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

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

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

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

   209     for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {

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

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

   212       for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++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); j.valid(); ++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(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++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(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++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     for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {

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

   244     }

   245     std::cout<<std::endl;

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

   247   }

   249   {

   250     std::list<NodeIt> S;

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

   252     std::list<NodeIt> T;

   253     T.push_back(t);

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

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

   257     max_flow_test.run();

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

   260     for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {

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

   262     }

   263     std::cout<<std::endl;

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

   265   }

   267   return 0;

   268 }

author	marci
	Mon, 01 Mar 2004 11:33:10 +0000
changeset 137	6364b07f8cd4
parent 107	8d62f0072ff0
child 155	8c6292ec54c6
permissions	-rw-r--r--