deba@2084: /* -*- C++ -*- deba@2084: * deba@2084: * This file is a part of LEMON, a generic C++ optimization library deba@2084: * alpar@2553: * Copyright (C) 2003-2008 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) { alpar@2174: return b ? RED : BLACK; deba@2084: } deba@2084: deba@2084: int main() { deba@2392: cout << "This program calculates the number " deba@2392: "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: alpar@2207: 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@2514: Preflow preflow(graph, capacity, source, target); 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@2392: title("edge disjoint paths").scaleToA4(). deba@2392: copyright("(C) 2003-2007 LEMON Project").drawArrows(). deba@2514: edgeColors(composeMap(functorMap(color), preflow.flowMap())). deba@2392: coords(coords).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@2514: Preflow spreflow(sgraph, scapacity, deba@2514: SGraph::outNode(source), deba@2514: SGraph::inNode(target)); 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@2392: title("node disjoint paths").scaleToA4(). deba@2392: copyright("(C) 2003-2007 LEMON Project").drawArrows(). deba@2514: edgeColors(composeMap(functorMap(color), spreflow.flowMap())). alpar@2207: coords(SGraph::combinedNodeMap(coords, alpar@2207: shiftMap(coords, alpar@2207: dim2::Point(5, 0)))). deba@2392: run(); deba@2084: deba@2084: cout << "The paths are written into node_disjoint_paths.eps" << endl; deba@2084: deba@2084: return 0; deba@2084: }