deba@2084: /* -*- C++ -*- deba@2084: * deba@2084: * This file is a part of LEMON, a generic C++ optimization library deba@2084: * deba@2084: * Copyright (C) 2003-2006 deba@2084: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@2084: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@2084: * deba@2084: * Permission to use, modify and distribute this software is granted deba@2084: * provided that this copyright notice appears in all copies. For deba@2084: * precise terms see the accompanying LICENSE file. deba@2084: * deba@2084: * This software is provided "AS IS" with no warranty of any kind, deba@2084: * express or implied, and with no claim as to its suitability for any deba@2084: * purpose. deba@2084: * deba@2084: */ deba@2084: deba@2084: /// \ingroup demos deba@2084: /// \file deba@2084: /// \brief Node and edge disjoint paths in directed graph. deba@2084: /// deba@2084: /// This demo program calculates how many edge disjoint and node disjoint deba@2084: /// paths are in a directed graph between a source and a target node. deba@2084: /// The edge disjoint paths can be computed with a flow algorithm, deba@2084: /// in this example we use the Preflow algorithm class. To get the node deba@2084: /// disjoint paths we should first adapt the graph with the SplitGraphAdaptor deba@2084: /// and just then calculate the flow. deba@2084: /// deba@2084: /// \include disjoint_paths_demo.cc deba@2084: deba@2084: #include deba@2084: deba@2084: #include deba@2084: #include deba@2084: #include deba@2084: #include deba@2084: #include deba@2084: deba@2084: using namespace lemon; deba@2084: using namespace std; deba@2084: deba@2084: Color color(bool b) { deba@2084: return b ? Color(1.0, 0.0, 0.0) : Color(0.0, 0.0, 0.0); deba@2084: } deba@2084: deba@2084: int main() { deba@2084: cout << "This program calculates the number " << deba@2084: "of disjoint paths in a graph" << endl; deba@2084: cout << "The graph is read from the disjoint_paths_demo.lgf file" << endl; deba@2084: typedef SmartGraph Graph; deba@2084: deba@2084: Graph graph; deba@2084: deba@2084: Graph::NodeMap > coords(graph); deba@2084: Graph::Node source, target; deba@2084: GraphReader("disjoint_paths_demo.lgf", graph). deba@2084: readNodeMap("coords", coords). deba@2084: readNode("source", source).readNode("target", target).run(); deba@2084: deba@2084: typedef ConstMap Capacity; deba@2084: Capacity capacity(1); deba@2084: deba@2084: Graph::EdgeMap flow(graph); deba@2084: deba@2084: Preflow preflow(graph, source, target, capacity, flow); deba@2084: deba@2084: preflow.run(); deba@2084: deba@2084: cout << "Number of edge disjoint paths: " << preflow.flowValue() << endl; deba@2084: deba@2084: graphToEps(graph, "edge_disjoint_paths.eps"). deba@2084: title("edge disjoint path").copyright("(C) 2006 LEMON Project").drawArrows(). deba@2084: edgeColors(composeMap(functorMap(color), flow)). deba@2084: coords(coords).autoNodeScale().run(); deba@2084: deba@2084: deba@2084: cout << "The paths are written into edge_disjoint_paths.eps" << endl; deba@2084: deba@2084: typedef SplitGraphAdaptor SGraph; deba@2084: deba@2084: SGraph sgraph(graph); deba@2084: deba@2084: typedef ConstMap SCapacity; deba@2084: SCapacity scapacity(1); deba@2084: deba@2084: SGraph::EdgeMap sflow(sgraph); deba@2084: deba@2084: Preflow spreflow(sgraph, SGraph::outNode(source), deba@2084: SGraph::inNode(target), deba@2084: scapacity, sflow); deba@2084: deba@2084: spreflow.run(); deba@2084: deba@2084: cout << "Number of node disjoint paths: " << spreflow.flowValue() << endl; deba@2084: deba@2084: deba@2084: graphToEps(sgraph, "node_disjoint_paths.eps"). deba@2084: title("node disjoint path").copyright("(C) 2006 LEMON Project").drawArrows(). deba@2084: edgeColors(composeMap(functorMap(color), sflow)). deba@2084: coords(SGraph::combinedNodeMap(coords, shiftMap(coords, xy(5, 0)))). deba@2084: autoNodeScale().run(); deba@2084: deba@2084: cout << "The paths are written into node_disjoint_paths.eps" << endl; deba@2084: deba@2084: return 0; deba@2084: }