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