marci@866: // -*- c++ -*- marci@866: marci@866: // Use a DIMACS max flow file as stdin. alpar@1401: // sub_graph_adaptor_demo < dimacs_max_flow_file marci@871: // This program computes a maximum number of edge-disjoint shortest paths marci@869: // between s and t. marci@866: marci@866: #include marci@866: #include marci@866: alpar@921: #include alpar@921: #include alpar@921: #include alpar@1401: #include alpar@921: #include alpar@921: #include marci@931: #include marci@866: alpar@921: using namespace lemon; marci@866: marci@866: using std::cout; marci@866: using std::endl; marci@866: marci@866: int main() marci@866: { marci@866: typedef SmartGraph Graph; marci@866: marci@866: typedef Graph::Edge Edge; marci@866: typedef Graph::Node Node; marci@866: typedef Graph::EdgeIt EdgeIt; marci@866: typedef Graph::NodeIt NodeIt; marci@866: typedef Graph::EdgeMap LengthMap; marci@866: marci@866: Graph g; marci@866: Node s, t; marci@866: LengthMap length(g); marci@866: marci@866: readDimacs(std::cin, g, length, s, t); marci@866: alpar@986: cout << "edges with lengths (of form id, source--length->target): " << endl; marci@866: for(EdgeIt e(g); e!=INVALID; ++e) alpar@986: cout << " " << g.id(e) << ", " << g.id(g.source(e)) << "--" alpar@986: << length[e] << "->" << g.id(g.target(e)) << endl; marci@866: marci@866: cout << "s: " << g.id(s) << " t: " << g.id(t) << endl; marci@866: marci@866: typedef Dijkstra Dijkstra; marci@866: Dijkstra dijkstra(g, length); marci@866: dijkstra.run(s); marci@866: marci@869: // This map returns true exactly for those edges which are marci@869: // tight w.r.t the length funcion and the potential marci@869: // given by the dijkstra algorithm. marci@866: typedef TightEdgeFilterMap marci@866: TightEdgeFilter; marci@866: TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length); marci@866: marci@932: // ConstMap const_true_map(true); marci@869: // This graph contains exaclty the tight edges. alpar@1401: // typedef SubGraphAdaptor, TightEdgeFilter> SubGW; alpar@1401: typedef EdgeSubGraphAdaptor SubGW; marci@932: SubGW gw(g, tight_edge_filter); marci@866: marci@866: ConstMap const_1_map(1); marci@866: Graph::EdgeMap flow(g, 0); marci@869: // Max flow between s and t in the graph of tight edges. marci@866: Preflow, Graph::EdgeMap > marci@866: preflow(gw, s, t, const_1_map, flow); marci@866: preflow.run(); marci@866: athos@1544: cout << "maximum number of edge-disjoint shortest paths: " marci@931: << preflow.flowValue() << endl; marci@866: cout << "edges of the maximum number of edge-disjoint shortest s-t paths: " marci@866: << endl; marci@866: for(EdgeIt e(g); e!=INVALID; ++e) marci@866: if (flow[e]) marci@931: cout << " " << g.id(e) << ", " alpar@986: << g.id(g.source(e)) << "--" alpar@986: << length[e] << "->" << g.id(g.target(e)) << endl; marci@866: }