marci@9: #include <iostream>
marci@9: #include <vector>
marci@9: #include <string>
marci@9: 
marci@49: #include <list_graph.hh>
marci@49: #include <bfs_iterator.hh>
marci@49: #include <edmonds_karp.hh>
marci@9: 
marci@9: using namespace marci;
marci@9: 
marci@9: int main (int, char*[])
marci@9: {
marci@49:   typedef ListGraph::NodeIt NodeIt;
marci@49:   typedef ListGraph::EdgeIt EdgeIt;
marci@49:   typedef ListGraph::EachNodeIt EachNodeIt;
marci@49:   typedef ListGraph::EachEdgeIt EachEdgeIt;
marci@49:   typedef ListGraph::OutEdgeIt OutEdgeIt;
marci@49:   typedef ListGraph::InEdgeIt InEdgeIt;
marci@49:   typedef ListGraph::SymEdgeIt SymEdgeIt;
marci@49:   ListGraph G;
marci@49:   std::vector<NodeIt> vector_of_NodeIts;
marci@49:   for(int i=0; i!=8; ++i) vector_of_NodeIts.push_back(G.addNode());
marci@9:   for(int i=0; i!=8; ++i)
marci@49:     for(int j=0; j!=8; ++j) 
marci@49:       if ((i<j)&&(i+j)%3) G.addEdge(vector_of_NodeIts[i], vector_of_NodeIts[j]);
marci@9: 
marci@9:   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;
marci@49:   std::cout << "number of nodes: " << count(G.first<EachNodeIt>()) << std::endl;
marci@9: 
marci@49:   for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
marci@9:     std::cout << "node " << G.id(i) << std::endl;
marci@49:     std::cout << " outdegree (OutEdgeIt): " << count(G.first<OutEdgeIt>(i)) << " "; 
marci@49:     for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) { 
marci@9:       std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") ";
marci@9:     }
marci@9:     std::cout << std::endl; 
marci@12: 
marci@12:     std::cout<< " ";
marci@49:     for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) { 
marci@49:       std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } 
marci@12:     std::cout<<std::endl;
marci@12: 
marci@49:     std::cout << " indegree: (InEdgeIt) " << count(G.first<InEdgeIt>(i)) << " ";
marci@49:     for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) { 
marci@9:       std::cout << j << " "; } 
marci@9:     std::cout << std::endl;
marci@12: 
marci@12:     std::cout<< " ";
marci@49:     for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) { 
marci@49:       std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } 
marci@12:     std::cout<<std::endl;
marci@12: 
marci@49:     std::cout << " degree: (SymEdgeIt) " << count(G.first<SymEdgeIt>(i)) << " ";
marci@49:     for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) { 
marci@9:       std::cout << j << " "; } 
marci@9:     std::cout<<std::endl;
marci@12: 
marci@12:     std::cout<< " ";
marci@49:     for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) { 
marci@49:       std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } 
marci@12:     std::cout<<std::endl;
marci@9:   }
marci@9: 
marci@9:   std::cout << "all edges: ";
marci@49:   for(EachEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) {
marci@9:     std::cout << i << " ";
marci@9:   }
marci@9:   std::cout << std::endl;
marci@9: 
marci@9:   std::cout << "node property array test" << std::endl;
marci@49:   ListGraph::NodeMap<int> my_property_vector(G);
marci@49:   EachNodeIt v;
marci@49:   G.getFirst(v);
marci@49:   my_property_vector.set(v, 42);
marci@49:   my_property_vector.set(++G.first<EachNodeIt>(), 314);
marci@49:   my_property_vector.set(++++G.first<EachNodeIt>(), 1956);
marci@49:   my_property_vector.set(vector_of_NodeIts[3], 1989);
marci@49:   my_property_vector.set(vector_of_NodeIts[4], 2003);
marci@49:   my_property_vector.set(vector_of_NodeIts[7], 1978);
marci@9:   std::cout << "some node property values..." << std::endl;
marci@49:   for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
marci@9:     std::cout << my_property_vector.get(i) << std::endl;
marci@9:   }
marci@9:   int _i=1;
marci@9:   int _ii=1;
marci@49:   ListGraph::EdgeMap<int> my_edge_property(G);
marci@49:   for(EachEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) {
marci@49:     my_edge_property.set(i, _i);
marci@9:     _i*=_ii; ++_ii;
marci@9:   }
marci@9: 
marci@9:   std::cout << "node and edge property values on the tails and heads of edges..." << std::endl;
marci@49:   for(EachEdgeIt j=G.first<EachEdgeIt>(); j.valid(); ++j) {
marci@9:     std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " ";
marci@9:   }
marci@9:   std::cout << std::endl;
marci@75: /*
marci@9:   std::cout << "bfs from the first node" << std::endl;
marci@49:   bfs<ListGraph> bfs_test(G, G.first<EachNodeIt>());
marci@9:   bfs_test.run();
marci@9:   std::cout << "reached: ";
marci@49:   for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
marci@9:     std::cout << bfs_test.reached.get(i) << " ";
marci@9:   }
marci@9:   std::cout<<std::endl;
marci@9:   std::cout << "dist: ";
marci@49:   for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
marci@9:     std::cout << bfs_test.dist.get(i) << " ";
marci@9:   }
marci@9:   std::cout<<std::endl;
marci@75: */
marci@9: 
marci@9:   std::cout << "augmenting path flow algorithm test..." << std::endl;
marci@49:   ListGraph flowG;
marci@9: 
marci@49:   NodeIt s=flowG.addNode();
marci@49:   NodeIt v1=flowG.addNode();
marci@49:   NodeIt v2=flowG.addNode();
marci@49:   NodeIt v3=flowG.addNode();
marci@49:   NodeIt v4=flowG.addNode();
marci@49:   NodeIt t=flowG.addNode();
marci@9:   
marci@49:   ListGraph::NodeMap<std::string> node_name(flowG);
marci@49:   node_name.set(s, "s");
marci@49:   node_name.set(v1, "v1");
marci@49:   node_name.set(v2, "v2");
marci@49:   node_name.set(v3, "v3");
marci@49:   node_name.set(v4, "v4");
marci@49:   node_name.set(t, "t");
marci@9: 
marci@49:   EdgeIt s_v1=flowG.addEdge(s, v1);
marci@49:   EdgeIt s_v2=flowG.addEdge(s, v2);
marci@49:   EdgeIt v1_v2=flowG.addEdge(v1, v2);
marci@49:   EdgeIt v2_v1=flowG.addEdge(v2, v1);
marci@49:   EdgeIt v1_v3=flowG.addEdge(v1, v3);
marci@49:   EdgeIt v3_v2=flowG.addEdge(v3, v2);
marci@49:   EdgeIt v2_v4=flowG.addEdge(v2, v4);
marci@49:   EdgeIt v4_v3=flowG.addEdge(v4, v3);
marci@49:   EdgeIt v3_t=flowG.addEdge(v3, t);
marci@49:   EdgeIt v4_t=flowG.addEdge(v4, t);
marci@9: 
marci@49:   ListGraph::EdgeMap<int> cap(flowG);
marci@9: 
marci@49:   cap.set(s_v1, 16);
marci@49:   cap.set(s_v2, 13);
marci@49:   cap.set(v1_v2, 10);
marci@49:   cap.set(v2_v1, 4);
marci@49:   cap.set(v1_v3, 12);
marci@49:   cap.set(v3_v2, 9);
marci@49:   cap.set(v2_v4, 14);
marci@49:   cap.set(v4_v3, 7);
marci@49:   cap.set(v3_t, 20);
marci@49:   cap.set(v4_t, 4);
marci@9: 
marci@49:   std::cout << "on directed graph graph" << std::endl; //<< flowG;
marci@9:   std::cout << "names and capacity values" << std::endl; 
marci@49:   for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { 
marci@9:     std::cout << node_name.get(i) << ": ";
marci@9:     std::cout << "out edges: ";
marci@49:     for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j) 
marci@49:       std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
marci@9:     std::cout << "in edges: ";
marci@49:     for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j) 
marci@49:       std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
marci@9:     std::cout << std::endl;
marci@9:   }
marci@9: 
marci@60:   //flowG.deleteEdge(s_v1);
marci@60:   //flowG.deleteEdge(s_v2);
marci@60:   //flowG.deleteEdge(v1_v2);
marci@60:   //flowG.deleteEdge(v1_v3);
marci@60:   
marci@60: 
marci@49:   //flowG.setTail(v3_t, v2);
marci@49:   //flowG.setHead(v3_t, s);
marci@75: /*
marci@49:   for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { 
marci@49:     std::cout << node_name.get(i) << ": ";
marci@49:     std::cout << "out edges: ";
marci@49:     for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j) 
marci@49:       std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
marci@49:     std::cout << "in edges: ";
marci@49:     for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j) 
marci@49:       std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
marci@49:     std::cout << std::endl;
marci@49:   }
marci@9:   
marci@60:   for(EachEdgeIt e=flowG.first<EachEdgeIt>(); e.valid(); ++e) {
marci@60:     std::cout << node_name.get(flowG.tail(e)) << "-"<< cap.get(e) << "->" << node_name.get(flowG.head(e)) << " ";
marci@60:   }
marci@75: */
marci@49:   /*
marci@49:   while (flowG.first<EachEdgeIt>().valid()) {
marci@49:     flowG.deleteEdge(flowG.first<EachEdgeIt>());
marci@49:     for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { 
marci@49:       std::cout << node_name.get(i) << ": ";
marci@49:       std::cout << "out edges: ";
marci@49:       for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j) 
marci@49: 	std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
marci@49:       std::cout << "in edges: ";
marci@49:       for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j) 
marci@49: 	std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
marci@49:       std::cout << std::endl;
marci@49:     }
marci@49:   }
marci@9:   
marci@49:   while (flowG.first<EachNodeIt>().valid()) {
marci@49:     flowG.deleteNode(flowG.first<EachNodeIt>());
marci@49:     for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { 
marci@49:       std::cout << node_name.get(i) << ": ";
marci@49:       std::cout << "out edges: ";
marci@49:       for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j) 
marci@49: 	std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
marci@49:       std::cout << "in edges: ";
marci@49:       for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j) 
marci@49: 	std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
marci@49:       std::cout << std::endl;
marci@49:     }
marci@49:   }
marci@49:   */
marci@49: 
marci@75:   //std::cout << std::endl;
marci@60: 
marci@9: 
marci@75:   {
marci@75:     ListGraph::EdgeMap<int> flow(flowG, 0);
marci@75:     MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, s, t, flow, cap);
marci@75:     max_flow_test.run();
marci@75:     
marci@75:     std::cout << "maximum flow: "<< std::endl;
marci@75:     for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) { 
marci@75:       std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
marci@75:     }
marci@75:     std::cout<<std::endl;
marci@75:     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@60:   }
marci@75: 
marci@75:   {
marci@75:     std::list<NodeIt> S;
marci@75:     S.push_back(s); S.push_back(v3);
marci@75:     std::list<NodeIt> T;
marci@75:     T.push_back(t);
marci@75: 
marci@75:     ListGraph::EdgeMap<int> flow(flowG, 0);
marci@75:     MaxFlow2<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, S, T, flow, cap);
marci@75:     max_flow_test.run();
marci@75:     
marci@75:     std::cout << "maximum flow: "<< std::endl;
marci@75:     for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) { 
marci@75:       std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
marci@75:     }
marci@75:     std::cout<<std::endl;
marci@75:     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@75:   }
marci@60: 
marci@9:   return 0;
marci@9: }