athos@36: #include athos@36: #include athos@36: #include athos@36: athos@77: #include "list_graph.hh" athos@36: #include "marci_graph_traits.hh" athos@77: //#include "marci_property_vector.hh" athos@36: #include "preflow_push.hh" athos@36: alpar@105: using namespace hugo; athos@36: athos@36: athos@36: int main (int, char*[]) athos@36: { athos@36: athos@36: athos@77: typedef ListGraph::NodeIt NodeIt; athos@77: typedef ListGraph::EdgeIt EdgeIt; athos@77: /* athos@77: typedef ListGraph::EachNodeIt EachNodeIt; athos@77: typedef ListGraph::EachEdgeIt EachEdgeIt; athos@77: typedef ListGraph::OutEdgeIt OutEdgeIt; athos@77: typedef ListGraph::InEdgeIt InEdgeIt; athos@77: typedef ListGraph::SymEdgeIt SymEdgeIt; athos@77: */ athos@77: athos@77: //Marci példája athos@77: ListGraph flowG; athos@77: athos@77: NodeIt s=flowG.addNode(); athos@77: NodeIt v1=flowG.addNode(); athos@77: NodeIt v2=flowG.addNode(); athos@77: NodeIt v3=flowG.addNode(); athos@77: NodeIt v4=flowG.addNode(); athos@77: NodeIt t=flowG.addNode(); athos@77: athos@77: athos@77: EdgeIt s_v1=flowG.addEdge(s, v1); athos@77: EdgeIt s_v2=flowG.addEdge(s, v2); athos@77: EdgeIt v1_v2=flowG.addEdge(v1, v2); athos@77: EdgeIt v2_v1=flowG.addEdge(v2, v1); athos@77: EdgeIt v1_v3=flowG.addEdge(v1, v3); athos@77: EdgeIt v3_v2=flowG.addEdge(v3, v2); athos@77: EdgeIt v2_v4=flowG.addEdge(v2, v4); athos@77: EdgeIt v4_v3=flowG.addEdge(v4, v3); athos@77: EdgeIt v3_t=flowG.addEdge(v3, t); athos@77: EdgeIt v4_t=flowG.addEdge(v4, t); athos@77: athos@77: ListGraph::EdgeMap cap(flowG); athos@77: athos@77: cap.set(s_v1, 16); athos@77: cap.set(s_v2, 13); athos@77: cap.set(v1_v2, 10); athos@77: cap.set(v2_v1, 4); athos@77: cap.set(v1_v3, 12); athos@77: cap.set(v3_v2, 9); athos@77: cap.set(v2_v4, 14); athos@77: cap.set(v4_v3, 7); athos@77: cap.set(v3_t, 20); athos@77: cap.set(v4_t, 4); athos@77: athos@77: athos@77: athos@77: athos@77: athos@77: athos@77: athos@77: /* athos@36: //Ahuja könyv példája athos@36: node_iterator s=flow_test.add_node(); athos@77: NodeIt v2=flow_test.add_node(); athos@77: NodeIt v3=flow_test.add_node(); athos@77: NodeIt v4=flow_test.add_node(); athos@77: NodeIt v5=flow_test.add_node(); athos@77: NodeIt t=flow_test.add_node(); athos@36: athos@36: node_property_vector node_name(flow_test); athos@36: node_name.put(s, "s"); athos@36: node_name.put(v2, "v2"); athos@36: node_name.put(v3, "v3"); athos@36: node_name.put(v4, "v4"); athos@36: node_name.put(v5, "v5"); athos@36: node_name.put(t, "t"); athos@36: athos@36: athos@36: edge_iterator s_v2=flow_test.add_edge(s, v2); athos@36: edge_iterator s_v3=flow_test.add_edge(s, v3); athos@36: athos@36: edge_iterator v2_v4=flow_test.add_edge(v2, v4); athos@36: edge_iterator v2_v5=flow_test.add_edge(v2, v5); athos@36: athos@36: edge_iterator v3_v5=flow_test.add_edge(v3, v5); athos@36: athos@36: edge_iterator v4_t=flow_test.add_edge(v4, t); athos@36: edge_iterator v5_t=flow_test.add_edge(v5, t); athos@36: athos@36: //Kis modositas athos@36: edge_iterator v2_s=flow_test.add_edge(v2, s); athos@36: athos@36: edge_property_vector cap(flow_test); athos@36: cap.put(s_v2, 10); athos@36: cap.put(s_v3, 10); athos@36: cap.put(v2_v4, 5); athos@36: cap.put(v2_v5, 8); athos@36: cap.put(v3_v5, 5); athos@36: cap.put(v4_t, 8); athos@36: cap.put(v5_t, 8); athos@36: athos@36: //Kis modositas athos@36: cap.put(v2_s, 100); athos@36: athos@36: //Kis modositas athos@36: //edge_iterator t_s=flow_test.add_edge(t, s); athos@36: //cap.put(t_s, 20); athos@36: athos@77: */ athos@36: athos@77: athos@77: athos@36: /*Egyszerű példa athos@77: NodeIt s=flow_test.add_node(); athos@77: NodeIt v1=flow_test.add_node(); athos@77: NodeIt v2=flow_test.add_node(); athos@77: NodeIt t=flow_test.add_node(); athos@36: athos@36: node_property_vector node_name(flow_test); athos@36: node_name.put(s, "s"); athos@36: node_name.put(v1, "v1"); athos@36: node_name.put(v2, "v2"); athos@36: node_name.put(t, "t"); athos@36: athos@36: edge_iterator s_v1=flow_test.add_edge(s, v1); athos@36: edge_iterator v1_v2=flow_test.add_edge(v1, v2); athos@36: edge_iterator v2_t=flow_test.add_edge(v2, t); athos@36: athos@36: edge_property_vector cap(flow_test); athos@36: athos@36: cap.put(s_v1, 16); athos@36: cap.put(v1_v2, 10); athos@36: cap.put(v2_t, 4); athos@36: */ athos@36: athos@36: std::cout << "preflow-push algorithm test..." << std::endl; athos@77: athos@77: /* athos@36: std::cout << "on directed graph graph" << std::endl; //<< flow_test; athos@36: std::cout << "names and capacity values" << std::endl; athos@77: for(EachNodeIt i=flow_test.first_node(); i.valid(); ++i) { athos@36: std::cout << node_name.get(i) << ": "; athos@36: std::cout << "out edges: "; athos@36: for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j) athos@36: std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " "; athos@36: std::cout << "in edges: "; athos@36: for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j) athos@36: std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " "; athos@36: std::cout << std::endl; athos@36: } athos@77: */ athos@36: athos@77: //for(each_NodeIt i=flow_test.first_node(); i.valid(); ++i) { athos@36: // std::cout << i << " "; athos@36: //} athos@36: athos@77: preflow_push preflow_push_test(flowG, s, t, cap); athos@36: cout << preflow_push_test.run()<