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