src/work/marci_graph_demo.cc
changeset 92 a7f9e2fda93a
parent 69 24c2c2989e0f
child 107 8d62f0072ff0
equal deleted inserted replaced
5:8f347d0f0839 6:fd4701b3d474
    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(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)) << " ";
    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<EachNodeIt>());
   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(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
   106   std::cout << "dist: ";
   106   std::cout << "dist: ";
   107   for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
   107   for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++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   NodeIt s=flowG.addNode();
   171   //flowG.deleteEdge(v1_v3);
   171   //flowG.deleteEdge(v1_v3);
   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(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++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); j.valid(); ++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)) << " ";
   186   }
   186   }
   187   
   187   
   188   for(EachEdgeIt e=flowG.first<EachEdgeIt>(); e.valid(); ++e) {
   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)) << " ";
   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.first<EachEdgeIt>().valid()) {
   194     flowG.deleteEdge(flowG.first<EachEdgeIt>());
   194     flowG.deleteEdge(flowG.first<EachEdgeIt>());
   195     for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { 
   195     for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { 
   196       std::cout << node_name.get(i) << ": ";
   196       std::cout << node_name.get(i) << ": ";
   217       std::cout << std::endl;
   217       std::cout << std::endl;
   218     }
   218     }
   219   }
   219   }
   220   */
   220   */
   221 
   221 
   222   std::cout << std::endl;
   222   //std::cout << std::endl;
   223   //std::cout << "meg jo" << std::flush;
   223 
   224 
   224 
   225   ListGraph::EdgeMap<int> flow(flowG, 0);
   225   {
   226   MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, s, t, flow, cap);
   226     ListGraph::EdgeMap<int> flow(flowG, 0);
   227   max_flow_test.run();
   227     MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, s, t, flow, cap);
   228 
   228     max_flow_test.run();
   229   std::cout << "maximum flow: "<< std::endl;
   229     
   230   for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) { 
   230     std::cout << "maximum flow: "<< std::endl;
   231     std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
   231     for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) { 
   232   }
   232       std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
   233   std::cout<<std::endl;
   233     }
   234   std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   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   }
   235 
   255 
   236   return 0;
   256   return 0;
   237 }
   257 }