athos@1583: /* -*- C++ -*- athos@1583: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@1956: * Copyright (C) 2003-2006 alpar@1956: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport athos@1583: * (Egervary Research Group on Combinatorial Optimization, EGRES). athos@1583: * athos@1583: * Permission to use, modify and distribute this software is granted athos@1583: * provided that this copyright notice appears in all copies. For athos@1583: * precise terms see the accompanying LICENSE file. athos@1583: * athos@1583: * This software is provided "AS IS" with no warranty of any kind, athos@1583: * express or implied, and with no claim as to its suitability for any athos@1583: * purpose. athos@1583: * athos@1583: */ athos@1583: athos@1583: ///\ingroup demos athos@1583: ///\file athos@1583: ///\brief Computing maximum number of edge-disjoint shortest paths athos@1583: /// athos@1583: /// This program computes a maximum number of edge-disjoint shortest paths athos@1583: /// between nodes \c s and \c t. alpar@1641: /// alpar@1641: /// \include sub_graph_adaptor_demo.cc marci@866: athos@1560: // Use a DIMACS max flow file as input. alpar@1401: // sub_graph_adaptor_demo < dimacs_max_flow_file athos@1583: // Modified to eat lemon graph format! athos@1583: 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 ladanyi@2013: #include "tight_edge_filter_map.h" marci@866: athos@1583: #include athos@1577: athos@1577: alpar@921: using namespace lemon; marci@866: marci@866: using std::cout; marci@866: using std::endl; marci@866: athos@1560: int main(int argc, char *argv[]) athos@1560: { athos@1560: if(argc<2) athos@1560: { athos@1583: std::cerr << "USAGE: sub_graph_adaptor_demo input_file.lgf" << std::endl; athos@1583: std::cerr << "The file 'input_file.lgf' has to contain a max flow " athos@1583: << "instance in \n LEMON format " athos@1583: << "(e.g. sub_gad_input.lgf is such a file)." athos@1583: << std::endl; athos@1560: return 0; athos@1560: } athos@1560: athos@1560: athos@1560: //input stream to read the graph from athos@1560: std::ifstream is(argv[1]); athos@1560: 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: athos@1583: //readDimacs(is, g, length, s, t); marci@866: athos@1577: athos@1583: GraphReader reader(is,g); athos@1583: reader.readNode("source",s).readNode("target",t) athos@1583: .readEdgeMap("length",length).run(); athos@1577: 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: }