1.1 --- a/demo/Makefile.am Fri May 12 09:57:03 2006 +0000
1.2 +++ b/demo/Makefile.am Fri May 12 15:29:42 2006 +0000
1.3 @@ -18,7 +18,8 @@
1.4 coloring \
1.5 grid_ugraph_demo \
1.6 topology_demo \
1.7 - simann_maxcut_demo
1.8 + simann_maxcut_demo \
1.9 + disjoint_paths_demo
1.10
1.11 if HAVE_GLPK
1.12 noinst_PROGRAMS += lp_demo lp_maxflow_demo
1.13 @@ -66,3 +67,5 @@
1.14 topology_demo_SOURCES = topology_demo.cc
1.15
1.16 simann_maxcut_demo_SOURCES = simann_maxcut_demo.cc
1.17 +
1.18 +disjoint_paths_demo_SOURCES = disjoint_paths.cc
2.1 --- a/demo/descriptor_map_demo.cc Fri May 12 09:57:03 2006 +0000
2.2 +++ b/demo/descriptor_map_demo.cc Fri May 12 15:29:42 2006 +0000
2.3 @@ -16,6 +16,16 @@
2.4 *
2.5 */
2.6
2.7 +/// \ingroup demos
2.8 +/// \file
2.9 +/// \brief Using descriptor map and own special map types.
2.10 +///
2.11 +/// This demo shows how can be used the DescriptorMap class
2.12 +/// which helps to use unique label for each node or edge.
2.13 +/// And it gives an example how easy is creating own map types.
2.14 +///
2.15 +/// \include descriptor_map_demo.cc
2.16 +
2.17 #include <lemon/list_graph.h>
2.18 #include <lemon/graph_utils.h>
2.19 #include <lemon/graph_writer.h>
2.20 @@ -30,12 +40,13 @@
2.21
2.22 using namespace lemon;
2.23
2.24 -// Special map type
2.25 -// It gives back a position for each node. The position of the nodes
2.26 +// Special xy<double> map type
2.27 +//
2.28 +// It gives back a position for each node. The position of the nodes
2.29 // are on the circle with the given center and radius.
2.30 //
2.31 -// Because we use the descriptor map it will hold the proprty described above
2.32 -// even if a node added or deleted.
2.33 +// Because we use the descriptor map it will hold the proprty
2.34 +// described above even if a node added or deleted.
2.35 template <typename Graph>
2.36 class CircleMap {
2.37 public:
3.1 --- a/demo/dim_to_dot.cc Fri May 12 09:57:03 2006 +0000
3.2 +++ b/demo/dim_to_dot.cc Fri May 12 15:29:42 2006 +0000
3.3 @@ -16,21 +16,20 @@
3.4 *
3.5 */
3.6
3.7 -// Use a DIMACS max flow file as stdin.
3.8 -// dim_to_dot < dimacs_max_flow_file > dot_output_file
3.9 -// This program makes a dot file from a dimacs max flow file.
3.10 -// This program can be an aid in making up to date visualized documantation
3.11 -// of demo programs.
3.12 -
3.13 -// For later documentation (if marci does not do it)
3.14 -// Az a graphviz csomag egy egyszeru formatuma, ami egy graphrajzolo csomag.
3.15 -// Az EdgeSubGraphAdaptor doksijaban szerepel egy kirajzolt graf. Azt nem
3.16 -// kezzel csinaltam, hanem a megfelelo dim file-bol ezzel a progival. A
3.17 -// doxygen ugyanis ilyet eszik, igy a juzer vizualisan is latja a grafot a
3.18 -// doksiban, es sajat maga is le tudja futtatni az algoritmust, mert ott van
3.19 -// a kezeben a dim file is. Es mivel ez egy generalt file, ezert ha vmit
3.20 -// valtoztatunk a dim-en, ezt is konnyu bemasolni. Uff.
3.21 -
3.22 +///\file
3.23 +///\brief Dim (Dimacs) to Dot (Graphviz) converter
3.24 +///
3.25 +/// This program can convert the dimacs format to graphviz dot format.
3.26 +///
3.27 +/// Use a DIMACS max flow file as stdin.
3.28 +///
3.29 +/// <tt>dim_to_dot < dimacs_max_flow_file > dot_output_file</tt>
3.30 +///
3.31 +/// This program makes a dot file from a dimacs max flow file.
3.32 +/// This program can be an aid in making up to date visualized documantation
3.33 +/// of demo programs.
3.34 +///
3.35 +/// \include dim_to_dot.cc
3.36
3.37 #include <iostream>
3.38 #include <fstream>
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/demo/disjoint_paths.cc Fri May 12 15:29:42 2006 +0000
4.3 @@ -0,0 +1,107 @@
4.4 +/* -*- C++ -*-
4.5 + *
4.6 + * This file is a part of LEMON, a generic C++ optimization library
4.7 + *
4.8 + * Copyright (C) 2003-2006
4.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.11 + *
4.12 + * Permission to use, modify and distribute this software is granted
4.13 + * provided that this copyright notice appears in all copies. For
4.14 + * precise terms see the accompanying LICENSE file.
4.15 + *
4.16 + * This software is provided "AS IS" with no warranty of any kind,
4.17 + * express or implied, and with no claim as to its suitability for any
4.18 + * purpose.
4.19 + *
4.20 + */
4.21 +
4.22 +/// \ingroup demos
4.23 +/// \file
4.24 +/// \brief Node and edge disjoint paths in directed graph.
4.25 +///
4.26 +/// This demo program calculates how many edge disjoint and node disjoint
4.27 +/// paths are in a directed graph between a source and a target node.
4.28 +/// The edge disjoint paths can be computed with a flow algorithm,
4.29 +/// in this example we use the Preflow algorithm class. To get the node
4.30 +/// disjoint paths we should first adapt the graph with the SplitGraphAdaptor
4.31 +/// and just then calculate the flow.
4.32 +///
4.33 +/// \include disjoint_paths.cc
4.34 +
4.35 +#include <iostream>
4.36 +
4.37 +#include <lemon/smart_graph.h>
4.38 +#include <lemon/graph_adaptor.h>
4.39 +#include <lemon/graph_reader.h>
4.40 +#include <lemon/preflow.h>
4.41 +#include <lemon/graph_to_eps.h>
4.42 +
4.43 +using namespace lemon;
4.44 +using namespace std;
4.45 +
4.46 +Color color(bool b) {
4.47 + return b ? Color(1.0, 0.0, 0.0) : Color(0.0, 0.0, 0.0);
4.48 +}
4.49 +
4.50 +int main() {
4.51 + cout << "This program calculates the number " <<
4.52 + "of disjoint paths in a graph" << endl;
4.53 + cout << "The graph is read from the disjoint_paths.lgf file" << endl;
4.54 + typedef SmartGraph Graph;
4.55 +
4.56 + Graph graph;
4.57 +
4.58 + Graph::NodeMap<xy<double> > coords(graph);
4.59 + Graph::Node source, target;
4.60 + GraphReader<Graph>("disjoint_paths.lgf", graph).
4.61 + readNodeMap("coords", coords).
4.62 + readNode("source", source).readNode("target", target).run();
4.63 +
4.64 + typedef ConstMap<Graph::Edge, int> Capacity;
4.65 + Capacity capacity(1);
4.66 +
4.67 + Graph::EdgeMap<int> flow(graph);
4.68 +
4.69 + Preflow<Graph, int, Capacity> preflow(graph, source, target, capacity, flow);
4.70 +
4.71 + preflow.run();
4.72 +
4.73 + cout << "Number of edge disjoint paths: " << preflow.flowValue() << endl;
4.74 +
4.75 + graphToEps(graph, "edge_disjoint.eps").
4.76 + title("edge disjoint path").copyright("(C) 2006 LEMON Project").drawArrows().
4.77 + edgeColors(composeMap(functorMap(color), flow)).
4.78 + coords(coords).autoNodeScale().run();
4.79 +
4.80 +
4.81 + cout << "The paths are written into edge_disjoint.eps" << endl;
4.82 +
4.83 + typedef SplitGraphAdaptor<SmartGraph> SGraph;
4.84 +
4.85 + SGraph sgraph(graph);
4.86 +
4.87 + typedef ConstMap<SGraph::Edge, int> SCapacity;
4.88 + SCapacity scapacity(1);
4.89 +
4.90 + SGraph::EdgeMap<int> sflow(sgraph);
4.91 +
4.92 + Preflow<SGraph, int, SCapacity> spreflow(sgraph, SGraph::outNode(source),
4.93 + SGraph::inNode(target),
4.94 + scapacity, sflow);
4.95 +
4.96 + spreflow.run();
4.97 +
4.98 + cout << "Number of node disjoint paths: " << spreflow.flowValue() << endl;
4.99 +
4.100 +
4.101 + graphToEps(sgraph, "node_disjoint.eps").
4.102 + title("node disjoint path").copyright("(C) 2006 LEMON Project").drawArrows().
4.103 + edgeColors(composeMap(functorMap(color), sflow)).
4.104 + coords(SGraph::combinedNodeMap(coords, shiftMap(coords, xy<double>(5, 0)))).
4.105 + autoNodeScale().run();
4.106 +
4.107 + cout << "The paths are written into node_disjoint.eps" << endl;
4.108 +
4.109 + return 0;
4.110 +}
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/demo/disjoint_paths.lgf Fri May 12 15:29:42 2006 +0000
5.3 @@ -0,0 +1,46 @@
5.4 +@nodeset
5.5 +coords label
5.6 +(-20,17) 15
5.7 +(39,13) 14
5.8 +(39,-11) 13
5.9 +(-12,7) 12
5.10 +(25,-15) 11
5.11 +(-18,-14) 10
5.12 +(45,3) 9
5.13 +(28,13) 8
5.14 +(25,-5) 7
5.15 +(1,21) 6
5.16 +(3,3) 5
5.17 +(3,-9) 4
5.18 +(-9,15) 3
5.19 +(-13,-4) 2
5.20 +(-27,5) 1
5.21 +@edgeset
5.22 + label
5.23 +1 15 22
5.24 +8 14 20
5.25 +11 13 18
5.26 +1 12 8
5.27 +4 11 14
5.28 +1 10 1
5.29 +14 9 21
5.30 +13 9 19
5.31 +8 9 17
5.32 +7 9 16
5.33 +11 9 15
5.34 +5 8 12
5.35 +6 8 11
5.36 +5 7 13
5.37 +3 6 4
5.38 +12 5 9
5.39 +2 5 6
5.40 +3 5 5
5.41 +2 4 10
5.42 +10 4 7
5.43 +15 3 23
5.44 +1 3 3
5.45 +1 2 2
5.46 +@nodes
5.47 +source 1
5.48 +target 9
5.49 +@end
6.1 --- a/demo/tight_edge_filter_map.h Fri May 12 09:57:03 2006 +0000
6.2 +++ b/demo/tight_edge_filter_map.h Fri May 12 15:29:42 2006 +0000
6.3 @@ -16,36 +16,39 @@
6.4 *
6.5 */
6.6
6.7 -#ifndef LEMON_TIGHT_EDGE_FILTER_MAP_H
6.8 -#define LEMON_TIGHT_EDGE_FILTER_MAP_H
6.9 +#ifndef DEMO_TIGHT_EDGE_FILTER_MAP_H
6.10 +#define DEMO_TIGHT_EDGE_FILTER_MAP_H
6.11
6.12 #include <lemon/maps.h>
6.13
6.14 -// /// \file
6.15 -// /// \brief Maximum flow algorithms.
6.16 -// /// \ingroup galgs
6.17 +/// \file
6.18 +/// \brief Tight edge filter map.
6.19 +///
6.20 +/// Tight edge filter map is bool map on the edges of the graph
6.21 +/// which filters the edges which are not tight for a node-potential.
6.22 +/// It is used in the \ref sub_graph_adaptor_demo.cc file.
6.23 +///
6.24 +/// \include tight_edge_filter_map.h
6.25
6.26 namespace lemon {
6.27
6.28 - /*!
6.29 - \brief A map for filtering the edge-set to those edges
6.30 - which are tight w.r.t. a node-potential and
6.31 - edge-distance.
6.32 -
6.33 - Let \f$ G=(V,A) \f$ be a directed graph (graph for short) and
6.34 - let \f$ \mathbb{F} \f$ be a number type.
6.35 - Given a distance function
6.36 - \f$ d:E\to\mathbb{F} \f$,
6.37 - \f$ \pi:V\to\mathbb{F} \f$ is said to be a potetial
6.38 - w.r.t. \f$ d \f$
6.39 - if and only if
6.40 - \f$ \pi(v)\le d(uv)+\pi(u) \f$ holds for each edge \f$ uv\in E \f$
6.41 - (or the reverse inequality holds for each edge).
6.42 - An edge is said to be tight if this inequality holds with equality,
6.43 - and the map returns \c true exactly for those edges.
6.44 - To avoid rounding errors, it is recommended to use this class with exact
6.45 - number types, e.g. with \c int.
6.46 - */
6.47 + /// \brief A map for filtering the edge-set to those edges
6.48 + /// which are tight w.r.t. a node-potential and
6.49 + /// edge-distance.
6.50 + ///
6.51 + /// Let \f$ G=(V,A) \f$ be a directed graph (graph for short) and
6.52 + /// let \f$ \mathbb{F} \f$ be a number type.
6.53 + /// Given a distance function
6.54 + /// \f$ d:E\to\mathbb{F} \f$,
6.55 + /// \f$ \pi:V\to\mathbb{F} \f$ is said to be a potetial
6.56 + /// w.r.t. \f$ d \f$
6.57 + /// if and only if
6.58 + /// \f$ \pi(v)\le d(uv)+\pi(u) \f$ holds for each edge \f$ uv\in E \f$
6.59 + /// (or the reverse inequality holds for each edge).
6.60 + /// An edge is said to be tight if this inequality holds with equality,
6.61 + /// and the map returns \c true exactly for those edges.
6.62 + /// To avoid rounding errors, it is recommended to use this class with exact
6.63 + /// number types, e.g. with \c int.
6.64 template<typename Graph,
6.65 typename NodePotentialMap, typename EdgeDistanceMap>
6.66 class TightEdgeFilterMap : public MapBase<typename Graph::Edge, bool> {
6.67 @@ -66,4 +69,4 @@
6.68
6.69 } //namespace lemon
6.70
6.71 -#endif //LEMON_TIGHT_EDGE_FILTER_MAP_H
6.72 +#endif //DEMO_TIGHT_EDGE_FILTER_MAP_H
7.1 --- a/lemon/graph_adaptor.h Fri May 12 09:57:03 2006 +0000
7.2 +++ b/lemon/graph_adaptor.h Fri May 12 15:29:42 2006 +0000
7.3 @@ -41,7 +41,6 @@
7.4 namespace lemon {
7.5
7.6 ///\brief Base type for the Graph Adaptors
7.7 - ///\ingroup graph_adaptors
7.8 ///
7.9 ///Base type for the Graph Adaptors
7.10 ///
7.11 @@ -192,6 +191,12 @@
7.12
7.13 };
7.14
7.15 + ///\ingroup graph_adaptors
7.16 + ///
7.17 + ///\brief Trivial Graph Adaptor
7.18 + ///
7.19 + /// This class is an adaptor which does not change the adapted graph.
7.20 + /// It can be used only to test the graph adaptors.
7.21 template <typename _Graph>
7.22 class GraphAdaptor :
7.23 public GraphAdaptorExtender<GraphAdaptorBase<_Graph> > {
7.24 @@ -245,8 +250,9 @@
7.25 };
7.26
7.27
7.28 + ///\ingroup graph_adaptors
7.29 + ///
7.30 ///\brief A graph adaptor which reverses the orientation of the edges.
7.31 - ///\ingroup graph_adaptors
7.32 ///
7.33 /// If \c g is defined as
7.34 ///\code
7.35 @@ -636,8 +642,9 @@
7.36
7.37 };
7.38
7.39 + /// \ingroup graph_adaptors
7.40 + ///
7.41 /// \brief A graph adaptor for hiding nodes and edges from a graph.
7.42 - /// \ingroup graph_adaptors
7.43 ///
7.44 /// SubGraphAdaptor shows the graph with filtered node-set and
7.45 /// edge-set. If the \c checked parameter is true then it filters the edgeset
7.46 @@ -755,8 +762,9 @@
7.47
7.48
7.49
7.50 + ///\ingroup graph_adaptors
7.51 + ///
7.52 ///\brief An adaptor for hiding nodes from a graph.
7.53 - ///\ingroup graph_adaptors
7.54 ///
7.55 ///An adaptor for hiding nodes from a graph.
7.56 ///This adaptor specializes SubGraphAdaptor in the way that only
7.57 @@ -809,6 +817,8 @@
7.58 return NodeSubGraphAdaptor<const Graph, const NodeFilterMap>(graph, nfm);
7.59 }
7.60
7.61 + ///\ingroup graph_adaptors
7.62 + ///
7.63 ///\brief An adaptor for hiding edges from a graph.
7.64 ///
7.65 ///An adaptor for hiding edges from a graph.
7.66 @@ -1227,8 +1237,9 @@
7.67 };
7.68
7.69
7.70 + ///\ingroup graph_adaptors
7.71 + ///
7.72 /// \brief An undirected graph is made from a directed graph by an adaptor
7.73 - /// \ingroup graph_adaptors
7.74 ///
7.75 /// Undocumented, untested!!!
7.76 /// If somebody knows nice demo application, let's polulate it.
7.77 @@ -1365,11 +1376,11 @@
7.78 };
7.79
7.80
7.81 + ///\ingroup graph_adaptors
7.82 + ///
7.83 ///\brief An adaptor for composing the residual
7.84 ///graph for directed flow and circulation problems.
7.85 ///
7.86 - ///\ingroup graph_adaptors
7.87 - ///
7.88 ///An adaptor for composing the residual graph for directed flow and
7.89 ///circulation problems. Let \f$ G=(V, A) \f$ be a directed graph
7.90 ///and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
7.91 @@ -1574,8 +1585,9 @@
7.92 };
7.93
7.94
7.95 + ///\ingroup graph_adaptors
7.96 + ///
7.97 ///\brief For blocking flows.
7.98 - ///\ingroup graph_adaptors
7.99 ///
7.100 ///This graph adaptor is used for on-the-fly
7.101 ///Dinits blocking flow computations.
7.102 @@ -2319,7 +2331,7 @@
7.103
7.104 /// \ingroup graph_adaptors
7.105 ///
7.106 - /// \brief SplitGraphAdaptor class
7.107 + /// \brief Split graph adaptor class
7.108 ///
7.109 /// This is an graph adaptor which splits all node into an in-node
7.110 /// and an out-node. Formaly, the adaptor replaces each \f$ u \f$
7.111 @@ -2375,6 +2387,7 @@
7.112 /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth
7.113 ///
7.114 /// The second solution contains just 3 disjoint paths while the first 4.
7.115 + /// The full code can be found in the \ref disjoint_paths.cc demo file.
7.116 ///
7.117 /// This graph adaptor is fully conform to the
7.118 /// \ref concept::StaticGraph "StaticGraph" concept and