/* -*- 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.cc
#include
#include
#include
#include
#include
#include
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.lgf file" << endl;
typedef SmartGraph Graph;
Graph graph;
Graph::NodeMap > coords(graph);
Graph::Node source, target;
GraphReader("disjoint_paths.lgf", graph).
readNodeMap("coords", coords).
readNode("source", source).readNode("target", target).run();
typedef ConstMap Capacity;
Capacity capacity(1);
Graph::EdgeMap flow(graph);
Preflow preflow(graph, source, target, capacity, flow);
preflow.run();
cout << "Number of edge disjoint paths: " << preflow.flowValue() << endl;
graphToEps(graph, "edge_disjoint.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.eps" << endl;
typedef SplitGraphAdaptor SGraph;
SGraph sgraph(graph);
typedef ConstMap SCapacity;
SCapacity scapacity(1);
SGraph::EdgeMap sflow(sgraph);
Preflow 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.eps").
title("node disjoint path").copyright("(C) 2006 LEMON Project").drawArrows().
edgeColors(composeMap(functorMap(color), sflow)).
coords(SGraph::combinedNodeMap(coords, shiftMap(coords, xy(5, 0)))).
autoNodeScale().run();
cout << "The paths are written into node_disjoint.eps" << endl;
return 0;
}