/* -*- 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;

}