source: lemon-0.x/demo/disjoint_paths_demo.cc @ 2125:2f2cbe4e78a8

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2006
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

/// \ingroup demos
/// \file
/// \brief Node and edge disjoint paths in directed graph.
///
/// This demo program calculates how many edge disjoint and node disjoint
/// paths are in a directed graph between a source and a target node.
/// The edge disjoint paths can be computed with a flow algorithm,
/// in this example we use the Preflow algorithm class. To get the node
/// disjoint paths we should first adapt the graph with the SplitGraphAdaptor
/// and just then calculate the flow.  
///
/// \include disjoint_paths_demo.cc

#include <iostream>

#include <lemon/smart_graph.h>
#include <lemon/graph_adaptor.h>
#include <lemon/graph_reader.h>
#include <lemon/preflow.h>
#include <lemon/graph_to_eps.h>

using namespace lemon;
using namespace std;

Color color(bool b) {
  return b ? Color(1.0, 0.0, 0.0) : Color(0.0, 0.0, 0.0);
}

int main() {
  cout << "This program calculates the number " <<
    "of disjoint paths in a graph" << endl;
  cout << "The graph is read from the disjoint_paths_demo.lgf file" << endl;
  typedef SmartGraph Graph;

  Graph graph;

  Graph::NodeMap<xy<double> > coords(graph);
  Graph::Node source, target;
  GraphReader<Graph>("disjoint_paths_demo.lgf", graph).
    readNodeMap("coords", coords).
    readNode("source", source).readNode("target", target).run();

  typedef ConstMap<Graph::Edge, int> Capacity;
  Capacity capacity(1);

  Graph::EdgeMap<int> flow(graph);

  Preflow<Graph, int, Capacity> preflow(graph, source, target, capacity, flow); 
  
  preflow.run();

  cout << "Number of edge disjoint paths: " << preflow.flowValue() << endl;

  graphToEps(graph, "edge_disjoint_paths.eps").
    title("edge disjoint path").copyright("(C) 2006 LEMON Project").drawArrows().
    edgeColors(composeMap(functorMap(color), flow)).
    coords(coords).autoNodeScale().run();


  cout << "The paths are written into edge_disjoint_paths.eps" << endl;

  typedef SplitGraphAdaptor<SmartGraph> SGraph;

  SGraph sgraph(graph);

  typedef ConstMap<SGraph::Edge, int> SCapacity;
  SCapacity scapacity(1);

  SGraph::EdgeMap<int> sflow(sgraph);

  Preflow<SGraph, int, SCapacity> spreflow(sgraph, SGraph::outNode(source), 
                                           SGraph::inNode(target), 
                                           scapacity, sflow);

  spreflow.run();

  cout << "Number of node disjoint paths: " << spreflow.flowValue() << endl;


  graphToEps(sgraph, "node_disjoint_paths.eps").
    title("node disjoint path").copyright("(C) 2006 LEMON Project").drawArrows().
    edgeColors(composeMap(functorMap(color), sflow)).
    coords(SGraph::combinedNodeMap(coords, shiftMap(coords, xy<double>(5, 0)))).
    autoNodeScale().run();

  cout << "The paths are written into node_disjoint_paths.eps" << endl;
  
  return 0;
}