Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/marci_graph_demo.cc
changeset 277 044f5898b769
parent 168 27fbd1559fb7
equal deleted inserted replaced
10:e1511a48d30b 11:5241d2c28aa2 
     1 #include <iostream>
 
     1 #include <iostream>
 
     2 #include <vector>
 
     2 #include <vector>
 
     3 #include <string>
 
     3 #include <string>
 
     4 
     4 
     5 #include <list_graph.hh>
 
     5 #include <list_graph.h>
 
     6 #include <bfs_iterator.hh>
 
     6 #include <bfs_iterator.h>
 
     7 #include <edmonds_karp.hh>
 
     7 #include <edmonds_karp.h>
 
     8 
     8 
     9 using namespace hugo;
 
     9 using namespace hugo;
 
    10 
    10 
    11 int main (int, char*[])
 
    11 int main (int, char*[])
 
    12 {
 
    12 {
 
       
    13   typedef ListGraph::Node Node;
 
       
    14   typedef ListGraph::Edge Edge;
 
    13   typedef ListGraph::NodeIt NodeIt;
 
    15   typedef ListGraph::NodeIt NodeIt;
 
    14   typedef ListGraph::EdgeIt EdgeIt;
 
    16   typedef ListGraph::EdgeIt EdgeIt;
 
    15   typedef ListGraph::EachNodeIt EachNodeIt;
 
       
    16   typedef ListGraph::EachEdgeIt EachEdgeIt;
 
       
    17   typedef ListGraph::OutEdgeIt OutEdgeIt;
 
    17   typedef ListGraph::OutEdgeIt OutEdgeIt;
 
    18   typedef ListGraph::InEdgeIt InEdgeIt;
 
    18   typedef ListGraph::InEdgeIt InEdgeIt;
 
    19   typedef ListGraph::SymEdgeIt SymEdgeIt;
 
    19   typedef ListGraph::SymEdgeIt SymEdgeIt;
 
    20   ListGraph G;
 
    20   ListGraph G;
 
    21   std::vector<NodeIt> vector_of_NodeIts;
 
    21   std::vector<Node> vector_of_Nodes;
 
    22   for(int i=0; i!=8; ++i) vector_of_NodeIts.push_back(G.addNode());
 
    22   for(int i=0; i!=8; ++i) vector_of_Nodes.push_back(G.addNode());
 
    23   for(int i=0; i!=8; ++i)
 
    23   for(int i=0; i!=8; ++i)
 
    24     for(int j=0; j!=8; ++j) 
    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]);
 
    25       if ((i<j)&&(i+j)%3) G.addEdge(vector_of_Nodes[i], vector_of_Nodes[j]);
 
    26 
    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;
 
    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;
 
    28   std::cout << "number of nodes: " << count(G.first<NodeIt>()) << std::endl;
 
    29 
    29 
    30   for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
 
    30   for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
 
    31     std::cout << "node " << G.id(i) << std::endl;
 
    31     std::cout << "node " << G.id(i) << std::endl;
 
    32     std::cout << " outdegree (OutEdgeIt): " << count(G.first<OutEdgeIt>(i)) << " "; 
    32     std::cout << " outdegree (OutEdgeIt): " << count(G.first<OutEdgeIt>(i)) << " "; 
    33     for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) { 
    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)) << ") ";
 
    34       std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") ";
 
    35     }
 
    35     }
 
    36     std::cout << std::endl; 
    36     std::cout << std::endl; 
    37 
    37 
    38     std::cout<< " ";
 
    38     std::cout<< " ";
 
    39     for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) { 
    39     for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) { 
    40       std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } 
    40       std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } 
    41     std::cout<<std::endl;
 
    41     std::cout<<std::endl;
 
    42 
    42 
    43     std::cout << " indegree: (InEdgeIt) " << count(G.first<InEdgeIt>(i)) << " ";
 
    43     std::cout << " indegree: (InEdgeIt) " << count(G.first<InEdgeIt>(i)) << " ";
 
    44     for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) { 
    44     for(InEdgeIt j=G.first<InEdgeIt>(i); G.valid(j); G.next(j)) { 
    45       std::cout << j << " "; } 
    45       std::cout << j << " "; } 
    46     std::cout << std::endl;
 
    46     std::cout << std::endl;
 
    47 
    47 
    48     std::cout<< " ";
 
    48     std::cout<< " ";
 
    49     for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) { 
    49     for(InEdgeIt j=G.first<InEdgeIt>(i); G.valid(j); G.next(j)) { 
    50       std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } 
    50       std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } 
    51     std::cout<<std::endl;
 
    51     std::cout<<std::endl;
 
    52 
    52 
    53     std::cout << " degree: (SymEdgeIt) " << count(G.first<SymEdgeIt>(i)) << " ";
 
    53     std::cout << " degree: (SymEdgeIt) " << count(G.first<SymEdgeIt>(i)) << " ";
 
    54     for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) { 
    54     for(SymEdgeIt j=G.first<SymEdgeIt>(i); G.valid(j); G.next(j)) { 
    55       std::cout << j << " "; } 
    55       std::cout << j << " "; } 
    56     std::cout<<std::endl;
 
    56     std::cout<<std::endl;
 
    57 
    57 
    58     std::cout<< " ";
 
    58     std::cout<< " ";
 
    59     for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) { 
    59     for(SymEdgeIt j=G.first<SymEdgeIt>(i); G.valid(j); G.next(j)) { 
    60       std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } 
    60       std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } 
    61     std::cout<<std::endl;
 
    61     std::cout<<std::endl;
 
    62   }
 
    62   }
 
    63 
    63 
    64   std::cout << "all edges: ";
 
    64   std::cout << "all edges: ";
 
    65   for(EachEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) {
 
    65   for(EdgeIt i=G.first<EdgeIt>(); G.valid(i); G.next(i)) {
 
    66     std::cout << i << " ";
 
    66     std::cout << i << " ";
 
    67   }
 
    67   }
 
    68   std::cout << std::endl;
 
    68   std::cout << std::endl;
 
    69 
    69 
    70   std::cout << "node property array test" << std::endl;
 
    70   std::cout << "node property array test" << std::endl;
 
    71   ListGraph::NodeMap<int> my_property_vector(G);
 
    71   ListGraph::NodeMap<int> my_property_vector(G);
 
    72   EachNodeIt v;
 
    72   NodeIt v;
 
    73   G.getFirst(v);
 
    73   G.first(v);
 
    74   my_property_vector.set(v, 42);
 
    74   my_property_vector.set(v, 42);
 
    75   my_property_vector.set(++G.first<EachNodeIt>(), 314);
 
    75   my_property_vector.set(G.next(G.first<NodeIt>()), 314);
 
    76   my_property_vector.set(++++G.first<EachNodeIt>(), 1956);
 
    76   my_property_vector.set(G.next(G.next(G.first<NodeIt>())), 1956);
 
    77   my_property_vector.set(vector_of_NodeIts[3], 1989);
 
    77   my_property_vector.set(vector_of_Nodes[3], 1989);
 
    78   my_property_vector.set(vector_of_NodeIts[4], 2003);
 
    78   my_property_vector.set(vector_of_Nodes[4], 2003);
 
    79   my_property_vector.set(vector_of_NodeIts[7], 1978);
 
    79   my_property_vector.set(vector_of_Nodes[7], 1978);
 
    80   std::cout << "some node property values..." << std::endl;
 
    80   std::cout << "some node property values..." << std::endl;
 
    81   for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
 
    81   for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
 
    82     std::cout << my_property_vector.get(i) << std::endl;
 
    82     std::cout << my_property_vector.get(i) << std::endl;
 
    83   }
 
    83   }
 
    84   int _i=1;
 
    84   int _i=1;
 
    85   int _ii=1;
 
    85   int _ii=1;
 
    86   ListGraph::EdgeMap<int> my_edge_property(G);
 
    86   ListGraph::EdgeMap<int> my_edge_property(G);
 
    87   for(EachEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) {
 
    87   for(EdgeIt i=G.first<EdgeIt>(); G.valid(i); G.next(i)) {
 
    88     my_edge_property.set(i, _i);
 
    88     my_edge_property.set(i, _i);
 
    89     _i*=_ii; ++_ii;
 
    89     _i*=_ii; ++_ii;
 
    90   }
 
    90   }
 
    91 
    91 
    92   std::cout << "node and edge property values on the tails and heads of edges..." << std::endl;
 
    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) {
 
    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)) << " ";
 
    94     std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " ";
 
    95   }
 
    95   }
 
    96   std::cout << std::endl;
 
    96   std::cout << std::endl;
 
    97 /*
 
    97 /*
 
    98   std::cout << "bfs from the first node" << std::endl;
 
    98   std::cout << "bfs from the first node" << std::endl;
 
    99   bfs<ListGraph> bfs_test(G, G.first<EachNodeIt>());
 
    99   bfs<ListGraph> bfs_test(G, G.first<NodeIt>());
 
   100   bfs_test.run();
 
   100   bfs_test.run();
 
   101   std::cout << "reached: ";
 
   101   std::cout << "reached: ";
 
   102   for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
 
   102   for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
 
   103     std::cout << bfs_test.reached.get(i) << " ";
 
   103     std::cout << bfs_test.reached.get(i) << " ";
 
   104   }
 
   104   }
 
   105   std::cout<<std::endl;
 
   105   std::cout<<std::endl;
 
   106   std::cout << "dist: ";
 
   106   std::cout << "dist: ";
 
   107   for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
 
   107   for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
 
   108     std::cout << bfs_test.dist.get(i) << " ";
 
   108     std::cout << bfs_test.dist.get(i) << " ";
 
   109   }
 
   109   }
 
   110   std::cout<<std::endl;
 
   110   std::cout<<std::endl;
 
   111 */
 
   111 */
 
   112 
   112 
   113   std::cout << "augmenting path flow algorithm test..." << std::endl;
 
   113   std::cout << "augmenting path flow algorithm test..." << std::endl;
 
   114   ListGraph flowG;
 
   114   ListGraph flowG;
 
   115 
   115 
   116   NodeIt s=flowG.addNode();
 
   116   Node s=flowG.addNode();
 
   117   NodeIt v1=flowG.addNode();
 
   117   Node v1=flowG.addNode();
 
   118   NodeIt v2=flowG.addNode();
 
   118   Node v2=flowG.addNode();
 
   119   NodeIt v3=flowG.addNode();
 
   119   Node v3=flowG.addNode();
 
   120   NodeIt v4=flowG.addNode();
 
   120   Node v4=flowG.addNode();
 
   121   NodeIt t=flowG.addNode();
 
   121   Node t=flowG.addNode();
 
   122   
   122   
   123   ListGraph::NodeMap<std::string> node_name(flowG);
 
   123   ListGraph::NodeMap<std::string> node_name(flowG);
 
   124   node_name.set(s, "s");
 
   124   node_name.set(s, "s");
 
   125   node_name.set(v1, "v1");
 
   125   node_name.set(v1, "v1");
 
   126   node_name.set(v2, "v2");
 
   126   node_name.set(v2, "v2");
 
   127   node_name.set(v3, "v3");
 
   127   node_name.set(v3, "v3");
 
   128   node_name.set(v4, "v4");
 
   128   node_name.set(v4, "v4");
 
   129   node_name.set(t, "t");
 
   129   node_name.set(t, "t");
 
   130 
   130 
   131   EdgeIt s_v1=flowG.addEdge(s, v1);
 
   131   Edge s_v1=flowG.addEdge(s, v1);
 
   132   EdgeIt s_v2=flowG.addEdge(s, v2);
 
   132   Edge s_v2=flowG.addEdge(s, v2);
 
   133   EdgeIt v1_v2=flowG.addEdge(v1, v2);
 
   133   Edge v1_v2=flowG.addEdge(v1, v2);
 
   134   EdgeIt v2_v1=flowG.addEdge(v2, v1);
 
   134   Edge v2_v1=flowG.addEdge(v2, v1);
 
   135   EdgeIt v1_v3=flowG.addEdge(v1, v3);
 
   135   Edge v1_v3=flowG.addEdge(v1, v3);
 
   136   EdgeIt v3_v2=flowG.addEdge(v3, v2);
 
   136   Edge v3_v2=flowG.addEdge(v3, v2);
 
   137   EdgeIt v2_v4=flowG.addEdge(v2, v4);
 
   137   Edge v2_v4=flowG.addEdge(v2, v4);
 
   138   EdgeIt v4_v3=flowG.addEdge(v4, v3);
 
   138   Edge v4_v3=flowG.addEdge(v4, v3);
 
   139   EdgeIt v3_t=flowG.addEdge(v3, t);
 
   139   Edge v3_t=flowG.addEdge(v3, t);
 
   140   EdgeIt v4_t=flowG.addEdge(v4, t);
 
   140   Edge v4_t=flowG.addEdge(v4, t);
 
   141 
   141 
   142   ListGraph::EdgeMap<int> cap(flowG);
 
   142   ListGraph::EdgeMap<int> cap(flowG);
 
   143 
   143 
   144   cap.set(s_v1, 16);
 
   144   cap.set(s_v1, 16);
 
   145   cap.set(s_v2, 13);
 
   145   cap.set(s_v2, 13);
 
   152   cap.set(v3_t, 20);
 
   152   cap.set(v3_t, 20);
 
   153   cap.set(v4_t, 4);
 
   153   cap.set(v4_t, 4);
 
   154 
   154 
   155   std::cout << "on directed graph graph" << std::endl; //<< flowG;
 
   155   std::cout << "on directed graph graph" << std::endl; //<< flowG;
 
   156   std::cout << "names and capacity values" << std::endl; 
   156   std::cout << "names and capacity values" << std::endl; 
   157   for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { 
   157   for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 
   158     std::cout << node_name.get(i) << ": ";
 
   158     std::cout << node_name.get(i) << ": ";
 
   159     std::cout << "out edges: ";
 
   159     std::cout << "out edges: ";
 
   160     for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j) 
   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)) << " ";
 
   161       std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
 
   162     std::cout << "in edges: ";
 
   162     std::cout << "in edges: ";
 
   163     for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j) 
   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)) << " ";
 
   164       std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
 
   165     std::cout << std::endl;
 
   165     std::cout << std::endl;
 
   166   }
 
   166   }
 
   167 
   167 
   168   //flowG.deleteEdge(s_v1);
 
   168   //flowG.deleteEdge(s_v1);
 
   172   
   172   
   173 
   173 
   174   //flowG.setTail(v3_t, v2);
 
   174   //flowG.setTail(v3_t, v2);
 
   175   //flowG.setHead(v3_t, s);
 
   175   //flowG.setHead(v3_t, s);
 
   176 /*
 
   176 /*
 
   177   for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { 
   177   for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 
   178     std::cout << node_name.get(i) << ": ";
 
   178     std::cout << node_name.get(i) << ": ";
 
   179     std::cout << "out edges: ";
 
   179     std::cout << "out edges: ";
 
   180     for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j) 
   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)) << " ";
 
   181       std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
 
   182     std::cout << "in edges: ";
 
   182     std::cout << "in edges: ";
 
   183     for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j) 
   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)) << " ";
 
   184       std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
 
   185     std::cout << std::endl;
 
   185     std::cout << std::endl;
 
   186   }
 
   186   }
 
   187   
   187   
   188   for(EachEdgeIt e=flowG.first<EachEdgeIt>(); e.valid(); ++e) {
 
   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)) << " ";
 
   189     std::cout << node_name.get(flowG.tail(e)) << "-"<< cap.get(e) << "->" << node_name.get(flowG.head(e)) << " ";
 
   190   }
 
   190   }
 
   191 */
 
   191 */
 
   192   /*
 
   192   /*
 
   193   while (flowG.first<EachEdgeIt>().valid()) {
 
   193   while (flowG.valid(flowG.first<EdgeIt>())) {
 
   194     flowG.deleteEdge(flowG.first<EachEdgeIt>());
 
   194     flowG.deleteEdge(flowG.first<EdgeIt>());
 
   195     for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { 
   195     for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 
   196       std::cout << node_name.get(i) << ": ";
 
   196       std::cout << node_name.get(i) << ": ";
 
   197       std::cout << "out edges: ";
 
   197       std::cout << "out edges: ";
 
   198       for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j) 
   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)) << " ";
 
   199 	std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
 
   200       std::cout << "in edges: ";
 
   200       std::cout << "in edges: ";
 
   201       for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j) 
   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)) << " ";
 
   202 	std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
 
   203       std::cout << std::endl;
 
   203       std::cout << std::endl;
 
   204     }
 
   204     }
 
   205   }
 
   205   }
 
   206   
   206   
   207   while (flowG.first<EachNodeIt>().valid()) {
 
   207   while (flowG.valid(flowG.first<NodeIt>())) {
 
   208     flowG.deleteNode(flowG.first<EachNodeIt>());
 
   208     flowG.deleteNode(flowG.first<NodeIt>());
 
   209     for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { 
   209     for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 
   210       std::cout << node_name.get(i) << ": ";
 
   210       std::cout << node_name.get(i) << ": ";
 
   211       std::cout << "out edges: ";
 
   211       std::cout << "out edges: ";
 
   212       for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j) 
   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)) << " ";
 
   213 	std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
 
   214       std::cout << "in edges: ";
 
   214       std::cout << "in edges: ";
 
   215       for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j) 
   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)) << " ";
 
   216 	std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
 
   217       std::cout << std::endl;
 
   217       std::cout << std::endl;
 
   218     }
 
   218     }
 
   219   }
 
   219   }
 
   220   */
 
   220   */
 
   225   {
 
   225   {
 
   226     ListGraph::EdgeMap<int> flow(flowG, 0);
 
   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);
 
   227     MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, s, t, flow, cap);
 
   228     /*
 
   228     /*
 
   229     max_flow_test.augmentOnBlockingFlow<ListGraph>();
 
   229     max_flow_test.augmentOnBlockingFlow<ListGraph>();
 
   230     for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) { 
   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)<<") ";
 
   231       std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
 
   232     }
 
   232     }
 
   233     std::cout<<std::endl;
 
   233     std::cout<<std::endl;
 
   234     max_flow_test.augmentOnBlockingFlow<ListGraph>();
 
   234     max_flow_test.augmentOnBlockingFlow<ListGraph>();
 
   235     for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) { 
   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)<<") ";
 
   236       std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
 
   237     }
 
   237     }
 
   238     std::cout<<std::endl;*/
 
   238     std::cout<<std::endl;*/
 
   239     //max_flow_test.run();
 
   239     //max_flow_test.run();
 
   240     
   240     
   241     //std::cout << "maximum flow: "<< std::endl;
 
   241     //std::cout << "maximum flow: "<< std::endl;
 
   242     while (max_flow_test.augmentOnShortestPath()) {
 
   242     while (max_flow_test.augmentOnShortestPath()) {
 
   243       for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) { 
   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)<<") ";
 
   244 	std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
 
   245       }
 
   245       }
 
   246       std::cout<<std::endl;
 
   246       std::cout<<std::endl;
 
   247     }
 
   247     }
 
   248     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   248     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   249   }
 
   249   }
 
   250 /*
 
   250 /*
 
   251   {
 
   251   {
 
   252     std::list<NodeIt> S;
 
   252     std::list<Node> S;
 
   253     S.push_back(s); S.push_back(v3);
 
   253     S.push_back(s); S.push_back(v3);
 
   254     std::list<NodeIt> T;
 
   254     std::list<Node> T;
 
   255     T.push_back(t);
 
   255     T.push_back(t);
 
   256 
   256 
   257     ListGraph::EdgeMap<int> flow(flowG, 0);
 
   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);
 
   258     MaxFlow2<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, S, T, flow, cap);
 
   259     max_flow_test.run();
 
   259     max_flow_test.run();
 
   260     
   260     
   261     std::cout << "maximum flow: "<< std::endl;
 
   261     std::cout << "maximum flow: "<< std::endl;
 
   262     for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) { 
   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)<<") ";
 
   263       std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
 
   264     }
 
   264     }
 
   265     std::cout<<std::endl;
 
   265     std::cout<<std::endl;
 
   266     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   266     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   267   }
 
   267   }
lemon-0.x