Mercuriallemon-0.x / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/marci_graph_demo.cc
author marci
Mon, 16 Feb 2004 11:29:48 +0000
changeset 75 87623302a68f
parent 69 24c2c2989e0f
child 107 8d62f0072ff0
permissions -rw-r--r--
. 
     1 #include <iostream>

     2 #include <vector>

     3 #include <string>

     4 

     5 #include <list_graph.hh>

     6 #include <bfs_iterator.hh>

     7 #include <edmonds_karp.hh>

     8 

     9 using namespace marci;

    10 

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

    26 

    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;

    29 

    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; 

    37 

    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;

    42 

    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;

    47 

    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;

    52 

    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;

    57 

    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   }

    63 

    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;

    69 

    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   }

    91 

    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 */

   112 

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

   114   ListGraph flowG;

   115 

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

   122   

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

   130 

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

   141 

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

   143 

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

   154 

   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   }

   167 

   168   //flowG.deleteEdge(s_v1);

   169   //flowG.deleteEdge(s_v2);

   170   //flowG.deleteEdge(v1_v2);

   171   //flowG.deleteEdge(v1_v3);

   172   

   173 

   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   }

   187   

   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   }

   206   

   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   */

   221 

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

   223 

   224 

   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     max_flow_test.run();

   229     

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

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

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

   233     }

   234     std::cout<<std::endl;

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

   236   }

   237 

   238   {

   239     std::list<NodeIt> S;

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

   241     std::list<NodeIt> T;

   242     T.push_back(t);

   243 

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

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

   246     max_flow_test.run();

   247     

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

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

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

   251     }

   252     std::cout<<std::endl;

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

   254   }

   255 

   256   return 0;

   257 }
lemon-0.x