disjoint_paths_demo.cc File Reference

---

Detailed Description

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.

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2008
 * 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.
 *
 */


#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 ? RED : BLACK;
}

int main() {
  cout << "This program calculates the number " 
    "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<dim2::Point<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, Capacity> preflow(graph, capacity, source, target); 
  
  preflow.run();

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

  graphToEps(graph, "edge_disjoint_paths.eps").
    title("edge disjoint paths").scaleToA4().
    copyright("(C) 2003-2007 LEMON Project").drawArrows().
    edgeColors(composeMap(functorMap(color), preflow.flowMap())).
    coords(coords).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, SCapacity> spreflow(sgraph, scapacity, 
                                      SGraph::outNode(source), 
                                      SGraph::inNode(target));

  spreflow.run();

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


  graphToEps(sgraph, "node_disjoint_paths.eps").
    title("node disjoint paths").scaleToA4().
    copyright("(C) 2003-2007 LEMON Project").drawArrows().
    edgeColors(composeMap(functorMap(color), spreflow.flowMap())).
    coords(SGraph::combinedNodeMap(coords,
                                   shiftMap(coords,
                                            dim2::Point<double>(5, 0)))).
    run();

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

#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>