3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
21 /// \brief Node and edge disjoint paths in directed graph.
23 /// This demo program calculates how many edge disjoint and node disjoint
24 /// paths are in a directed graph between a source and a target node.
25 /// The edge disjoint paths can be computed with a flow algorithm,
26 /// in this example we use the Preflow algorithm class. To get the node
27 /// disjoint paths we should first adapt the graph with the SplitGraphAdaptor
28 /// and just then calculate the flow.
30 /// \include disjoint_paths_demo.cc
34 #include <lemon/smart_graph.h>
35 #include <lemon/graph_adaptor.h>
36 #include <lemon/graph_reader.h>
37 #include <lemon/preflow.h>
38 #include <lemon/graph_to_eps.h>
40 using namespace lemon;
44 return b ? RED : BLACK;
48 cout << "This program calculates the number " <<
49 "of disjoint paths in a graph" << endl;
50 cout << "The graph is read from the disjoint_paths_demo.lgf file" << endl;
51 typedef SmartGraph Graph;
55 Graph::NodeMap<dim2::Point<double> > coords(graph);
56 Graph::Node source, target;
57 GraphReader<Graph>("disjoint_paths_demo.lgf", graph).
58 readNodeMap("coords", coords).
59 readNode("source", source).readNode("target", target).run();
61 typedef ConstMap<Graph::Edge, int> Capacity;
64 Graph::EdgeMap<int> flow(graph);
66 Preflow<Graph, int, Capacity> preflow(graph, source, target, capacity, flow);
70 cout << "Number of edge disjoint paths: " << preflow.flowValue() << endl;
72 graphToEps(graph, "edge_disjoint_paths.eps").
73 title("edge disjoint path").copyright("(C) 2006 LEMON Project").drawArrows().
74 edgeColors(composeMap(functorMap(color), flow)).
75 coords(coords).autoNodeScale().run();
78 cout << "The paths are written into edge_disjoint_paths.eps" << endl;
80 typedef SplitGraphAdaptor<SmartGraph> SGraph;
84 typedef ConstMap<SGraph::Edge, int> SCapacity;
85 SCapacity scapacity(1);
87 SGraph::EdgeMap<int> sflow(sgraph);
89 Preflow<SGraph, int, SCapacity> spreflow(sgraph, SGraph::outNode(source),
90 SGraph::inNode(target),
95 cout << "Number of node disjoint paths: " << spreflow.flowValue() << endl;
98 graphToEps(sgraph, "node_disjoint_paths.eps").
99 title("node disjoint path").copyright("(C) 2006 LEMON Project").drawArrows().
100 edgeColors(composeMap(functorMap(color), sflow)).
101 coords(SGraph::combinedNodeMap(coords,
103 dim2::Point<double>(5, 0)))).
104 autoNodeScale().run();
106 cout << "The paths are written into node_disjoint_paths.eps" << endl;