marci@9: #include marci@9: #include marci@9: #include marci@9: marci@49: #include marci@49: #include marci@49: #include 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 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 ((ij is arc iff i()) << std::endl; marci@9: marci@49: for(EachNodeIt i=G.first(); i.valid(); ++i) { marci@9: std::cout << "node " << G.id(i) << std::endl; marci@49: std::cout << " outdegree (OutEdgeIt): " << count(G.first(i)) << " "; marci@49: for(OutEdgeIt j=G.first(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(i); j.valid(); ++j) { marci@49: std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } marci@12: std::cout<(i)) << " "; marci@49: for(InEdgeIt j=G.first(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(i); j.valid(); ++j) { marci@49: std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } marci@12: std::cout<(i)) << " "; marci@49: for(SymEdgeIt j=G.first(i); j.valid(); ++j) { marci@9: std::cout << j << " "; } marci@9: std::cout<(i); j.valid(); ++j) { marci@49: std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } marci@12: std::cout<(); 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 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(), 314); marci@49: my_property_vector.set(++++G.first(), 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(); 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 my_edge_property(G); marci@49: for(EachEdgeIt i=G.first(); 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(); 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 bfs_test(G, G.first()); marci@9: bfs_test.run(); marci@9: std::cout << "reached: "; marci@49: for(EachNodeIt i=G.first(); i.valid(); ++i) { marci@9: std::cout << bfs_test.reached.get(i) << " "; marci@9: } marci@9: std::cout<(); i.valid(); ++i) { marci@9: std::cout << bfs_test.dist.get(i) << " "; marci@9: } marci@9: std::cout< 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 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(); i.valid(); ++i) { marci@9: std::cout << node_name.get(i) << ": "; marci@9: std::cout << "out edges: "; marci@49: for(OutEdgeIt j=flowG.first(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(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(); i.valid(); ++i) { marci@49: std::cout << node_name.get(i) << ": "; marci@49: std::cout << "out edges: "; marci@49: for(OutEdgeIt j=flowG.first(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(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(); 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().valid()) { marci@49: flowG.deleteEdge(flowG.first()); marci@49: for(EachNodeIt i=flowG.first(); i.valid(); ++i) { marci@49: std::cout << node_name.get(i) << ": "; marci@49: std::cout << "out edges: "; marci@49: for(OutEdgeIt j=flowG.first(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(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().valid()) { marci@49: flowG.deleteNode(flowG.first()); marci@49: for(EachNodeIt i=flowG.first(); i.valid(); ++i) { marci@49: std::cout << node_name.get(i) << ": "; marci@49: std::cout << "out edges: "; marci@49: for(OutEdgeIt j=flowG.first(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(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 flow(flowG, 0); marci@75: MaxFlow, ListGraph::EdgeMap > 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(); e.valid(); ++e) { marci@75: std::cout<<"("<"< S; marci@75: S.push_back(s); S.push_back(v3); marci@75: std::list T; marci@75: T.push_back(t); marci@75: marci@75: ListGraph::EdgeMap flow(flowG, 0); marci@75: MaxFlow2, ListGraph::EdgeMap > 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(); e.valid(); ++e) { marci@75: std::cout<<"("<"<