1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/demo/disjoint_paths_demo.cc Mon May 15 09:49:51 2006 +0000
1.3 @@ -0,0 +1,107 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2006
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +/// \ingroup demos
1.23 +/// \file
1.24 +/// \brief Node and edge disjoint paths in directed graph.
1.25 +///
1.26 +/// This demo program calculates how many edge disjoint and node disjoint
1.27 +/// paths are in a directed graph between a source and a target node.
1.28 +/// The edge disjoint paths can be computed with a flow algorithm,
1.29 +/// in this example we use the Preflow algorithm class. To get the node
1.30 +/// disjoint paths we should first adapt the graph with the SplitGraphAdaptor
1.31 +/// and just then calculate the flow.
1.32 +///
1.33 +/// \include disjoint_paths_demo.cc
1.34 +
1.35 +#include <iostream>
1.36 +
1.37 +#include <lemon/smart_graph.h>
1.38 +#include <lemon/graph_adaptor.h>
1.39 +#include <lemon/graph_reader.h>
1.40 +#include <lemon/preflow.h>
1.41 +#include <lemon/graph_to_eps.h>
1.42 +
1.43 +using namespace lemon;
1.44 +using namespace std;
1.45 +
1.46 +Color color(bool b) {
1.47 + return b ? Color(1.0, 0.0, 0.0) : Color(0.0, 0.0, 0.0);
1.48 +}
1.49 +
1.50 +int main() {
1.51 + cout << "This program calculates the number " <<
1.52 + "of disjoint paths in a graph" << endl;
1.53 + cout << "The graph is read from the disjoint_paths_demo.lgf file" << endl;
1.54 + typedef SmartGraph Graph;
1.55 +
1.56 + Graph graph;
1.57 +
1.58 + Graph::NodeMap<xy<double> > coords(graph);
1.59 + Graph::Node source, target;
1.60 + GraphReader<Graph>("disjoint_paths_demo.lgf", graph).
1.61 + readNodeMap("coords", coords).
1.62 + readNode("source", source).readNode("target", target).run();
1.63 +
1.64 + typedef ConstMap<Graph::Edge, int> Capacity;
1.65 + Capacity capacity(1);
1.66 +
1.67 + Graph::EdgeMap<int> flow(graph);
1.68 +
1.69 + Preflow<Graph, int, Capacity> preflow(graph, source, target, capacity, flow);
1.70 +
1.71 + preflow.run();
1.72 +
1.73 + cout << "Number of edge disjoint paths: " << preflow.flowValue() << endl;
1.74 +
1.75 + graphToEps(graph, "edge_disjoint_paths.eps").
1.76 + title("edge disjoint path").copyright("(C) 2006 LEMON Project").drawArrows().
1.77 + edgeColors(composeMap(functorMap(color), flow)).
1.78 + coords(coords).autoNodeScale().run();
1.79 +
1.80 +
1.81 + cout << "The paths are written into edge_disjoint_paths.eps" << endl;
1.82 +
1.83 + typedef SplitGraphAdaptor<SmartGraph> SGraph;
1.84 +
1.85 + SGraph sgraph(graph);
1.86 +
1.87 + typedef ConstMap<SGraph::Edge, int> SCapacity;
1.88 + SCapacity scapacity(1);
1.89 +
1.90 + SGraph::EdgeMap<int> sflow(sgraph);
1.91 +
1.92 + Preflow<SGraph, int, SCapacity> spreflow(sgraph, SGraph::outNode(source),
1.93 + SGraph::inNode(target),
1.94 + scapacity, sflow);
1.95 +
1.96 + spreflow.run();
1.97 +
1.98 + cout << "Number of node disjoint paths: " << spreflow.flowValue() << endl;
1.99 +
1.100 +
1.101 + graphToEps(sgraph, "node_disjoint_paths.eps").
1.102 + title("node disjoint path").copyright("(C) 2006 LEMON Project").drawArrows().
1.103 + edgeColors(composeMap(functorMap(color), sflow)).
1.104 + coords(SGraph::combinedNodeMap(coords, shiftMap(coords, xy<double>(5, 0)))).
1.105 + autoNodeScale().run();
1.106 +
1.107 + cout << "The paths are written into node_disjoint_paths.eps" << endl;
1.108 +
1.109 + return 0;
1.110 +}