/* -*- 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 ? RED : BLACK;

 }

 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;

 }