demo/disjoint_paths_demo.cc
author alpar
Tue, 18 Jul 2006 17:00:24 +0000
changeset 2155 c712e66532d8
child 2174 f9e43b5cc617
permissions -rw-r--r--
Minor doc changes.
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2006
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 /// \ingroup demos
    20 /// \file
    21 /// \brief Node and edge disjoint paths in directed graph.
    22 ///
    23 /// This demo program calculates how many edge disjoint and node disjoint
    24 /// paths are in a directed graph between a source and a target node.
    25 /// The edge disjoint paths can be computed with a flow algorithm,
    26 /// in this example we use the Preflow algorithm class. To get the node
    27 /// disjoint paths we should first adapt the graph with the SplitGraphAdaptor
    28 /// and just then calculate the flow.  
    29 ///
    30 /// \include disjoint_paths_demo.cc
    31 
    32 #include <iostream>
    33 
    34 #include <lemon/smart_graph.h>
    35 #include <lemon/graph_adaptor.h>
    36 #include <lemon/graph_reader.h>
    37 #include <lemon/preflow.h>
    38 #include <lemon/graph_to_eps.h>
    39 
    40 using namespace lemon;
    41 using namespace std;
    42 
    43 Color color(bool b) {
    44   return b ? Color(1.0, 0.0, 0.0) : Color(0.0, 0.0, 0.0);
    45 }
    46 
    47 int main() {
    48   cout << "This program calculates the number " <<
    49     "of disjoint paths in a graph" << endl;
    50   cout << "The graph is read from the disjoint_paths_demo.lgf file" << endl;
    51   typedef SmartGraph Graph;
    52 
    53   Graph graph;
    54 
    55   Graph::NodeMap<xy<double> > coords(graph);
    56   Graph::Node source, target;
    57   GraphReader<Graph>("disjoint_paths_demo.lgf", graph).
    58     readNodeMap("coords", coords).
    59     readNode("source", source).readNode("target", target).run();
    60 
    61   typedef ConstMap<Graph::Edge, int> Capacity;
    62   Capacity capacity(1);
    63 
    64   Graph::EdgeMap<int> flow(graph);
    65 
    66   Preflow<Graph, int, Capacity> preflow(graph, source, target, capacity, flow); 
    67   
    68   preflow.run();
    69 
    70   cout << "Number of edge disjoint paths: " << preflow.flowValue() << endl;
    71 
    72   graphToEps(graph, "edge_disjoint_paths.eps").
    73     title("edge disjoint path").copyright("(C) 2006 LEMON Project").drawArrows().
    74     edgeColors(composeMap(functorMap(color), flow)).
    75     coords(coords).autoNodeScale().run();
    76 
    77 
    78   cout << "The paths are written into edge_disjoint_paths.eps" << endl;
    79 
    80   typedef SplitGraphAdaptor<SmartGraph> SGraph;
    81 
    82   SGraph sgraph(graph);
    83 
    84   typedef ConstMap<SGraph::Edge, int> SCapacity;
    85   SCapacity scapacity(1);
    86 
    87   SGraph::EdgeMap<int> sflow(sgraph);
    88 
    89   Preflow<SGraph, int, SCapacity> spreflow(sgraph, SGraph::outNode(source), 
    90                                            SGraph::inNode(target), 
    91                                            scapacity, sflow);
    92 
    93   spreflow.run();
    94 
    95   cout << "Number of node disjoint paths: " << spreflow.flowValue() << endl;
    96 
    97 
    98   graphToEps(sgraph, "node_disjoint_paths.eps").
    99     title("node disjoint path").copyright("(C) 2006 LEMON Project").drawArrows().
   100     edgeColors(composeMap(functorMap(color), sflow)).
   101     coords(SGraph::combinedNodeMap(coords, shiftMap(coords, xy<double>(5, 0)))).
   102     autoNodeScale().run();
   103 
   104   cout << "The paths are written into node_disjoint_paths.eps" << endl;
   105   
   106   return 0;
   107 }