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 <iostream>
deba@2084: 
deba@2084: #include <lemon/smart_graph.h>
deba@2084: #include <lemon/graph_adaptor.h>
deba@2084: #include <lemon/graph_reader.h>
deba@2084: #include <lemon/preflow.h>
deba@2084: #include <lemon/graph_to_eps.h>
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<dim2::Point<double> > coords(graph);
deba@2084:   Graph::Node source, target;
deba@2084:   GraphReader<Graph>("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<Graph::Edge, int> Capacity;
deba@2084:   Capacity capacity(1);
deba@2084: 
deba@2084:   Graph::EdgeMap<int> flow(graph);
deba@2084: 
deba@2514:   Preflow<Graph, Capacity> 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<SmartGraph> SGraph;
deba@2084: 
deba@2084:   SGraph sgraph(graph);
deba@2084: 
deba@2084:   typedef ConstMap<SGraph::Edge, int> SCapacity;
deba@2084:   SCapacity scapacity(1);
deba@2084: 
deba@2084:   SGraph::EdgeMap<int> sflow(sgraph);
deba@2084: 
deba@2514:   Preflow<SGraph, SCapacity> 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<double>(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: }