# HG changeset patch
# User Alpar Juttner <alpar@cs.elte.hu>
# Date 1242126595 -3600
# Node ID c01a98ce01fd88fb40ab5e4b1e2c0c5be2ad93b5
# Parent 189760a7cdd0d71c2d3ae8727ab5d589944f374d# Parent e652b6f9a29f6654b2a48148cd5243587baf0b6d
Merge
diff -r 189760a7cdd0 -r c01a98ce01fd CMakeLists.txt
--- a/CMakeLists.txt Thu May 07 02:05:12 2009 +0200
+++ b/CMakeLists.txt Tue May 12 12:09:55 2009 +0100
@@ -44,7 +44,7 @@
SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
SET(CPACK_PACKAGE_VENDOR "EGRES")
SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
- "LEMON - Library of Efficient Models and Optimization in Networks")
+ "LEMON - Library for Efficient Modeling and Optimization in Networks")
SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")
SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
diff -r 189760a7cdd0 -r c01a98ce01fd NEWS
--- a/NEWS Thu May 07 02:05:12 2009 +0200
+++ b/NEWS Tue May 12 12:09:55 2009 +0100
@@ -1,3 +1,90 @@
+2009-05-13 Version 1.1 released
+
+ This is the second stable release of the 1.x series. It
+ features a better coverage of the tools available in the 0.x
+ series, a thoroughly reworked LP/MIP interface plus various
+ improvements in the existing tools.
+
+ * Much improved M$ Windows support
+ * Various improvements in the CMAKE build system
+ * Compilation warnings are fixed/suppressed
+ * Support IBM xlC compiler
+ * New algorithms
+ * Connectivity related algorithms (#61)
+ * Euler walks (#65)
+ * Preflow push-relabel max. flow algorithm (#176)
+ * Circulation algorithm (push-relabel based) (#175)
+ * Suurballe algorithm (#47)
+ * Gomory-Hu algorithm (#66)
+ * Hao-Orlin algorithm (#58)
+ * Edmond's maximum cardinality and weighted matching algorithms
+ in general graphs (#48,#265)
+ * Minimum cost arborescence/branching (#60)
+ * Network Simplex min. cost flow algorithm (#234)
+ * New data structures
+ * Full graph structure (#57)
+ * Grid graph structure (#57)
+ * Hypercube graph structure (#57)
+ * Graph adaptors (#67)
+ * ArcSet and EdgeSet classes (#67)
+ * Elevator class (#174)
+ * Other new tools
+ * LP/MIP interface (#44)
+ * Support for GLPK, CPLEX, Soplex, COIN-OR CLP and CBC
+ * Reader for the Nauty file format (#55)
+ * DIMACS readers (#167)
+ * Radix sort algorithms (#72)
+ * RangeIdMap and CrossRefMap (#160)
+ * New command line tools
+ * DIMACS to LGF converter (#182)
+ * lgf-gen - a graph generator (#45)
+ * DIMACS solver utility (#226)
+ * Other code improvements
+ * Lognormal distribution added to Random (#102)
+ * Better (i.e. O(1) time) item counting in SmartGraph (#3)
+ * The standard maps of graphs are guaranteed to be
+ reference maps (#190)
+ * Miscellaneous
+ * Various doc improvements
+ * Improved 0.x -> 1.x converter script
+
+ * Several bugfixes (compared to release 1.0):
+ #170: Bugfix SmartDigraph::split()
+ #171: Bugfix in SmartGraph::restoreSnapshot()
+ #172: Extended test cases for graphs and digraphs
+ #173: Bugfix in Random
+ * operator()s always return a double now
+ * the faulty real<Num>(Num) and real<Num>(Num,Num)
+ have been removed
+ #187: Remove DijkstraWidestPathOperationTraits
+ #61: Bugfix in DfsVisit
+ #193: Bugfix in GraphReader::skipSection()
+ #195: Bugfix in ConEdgeIt()
+ #197: Bugfix in heap unionfind
+ * This bug affects Edmond's general matching algorithms
+ #207: Fix 'make install' without 'make html' using CMAKE
+ #208: Suppress or fix VS2008 compilation warnings
+ ----: Update the LEMON icon
+ ----: Enable the component-based installer
+ (in installers made by CPACK)
+ ----: Set the proper version for CMAKE in the tarballs
+ (made by autotools)
+ ----: Minor clarification in the LICENSE file
+ ----: Add missing unistd.h include to time_measure.h
+ #204: Compilation bug fixed in graph_to_eps.h with VS2005
+ #214,#215: windows.h should never be included by lemon headers
+ #230: Build systems check the availability of 'long long' type
+ #229: Default implementation of Tolerance<> is used for integer types
+ #211,#212: Various fixes for compiling on AIX
+ ----: Improvements in CMAKE config
+ - docs is installed in share/doc/
+ - detects newer versions of Ghostscript
+ #239: Fix missing 'inline' specifier in time_measure.h
+ #274,#280: Install lemon/config.h
+ #275: Prefix macro names with LEMON_ in lemon/config.h
+ ----: Small script for making the release tarballs added
+ ----: Minor improvement in unify-sources.sh (a76f55d7d397)
+
2009-03-27 LEMON joins to the COIN-OR initiative
COIN-OR (Computational Infrastructure for Operations Research,
diff -r 189760a7cdd0 -r c01a98ce01fd README
--- a/README Thu May 07 02:05:12 2009 +0200
+++ b/README Tue May 12 12:09:55 2009 +0100
@@ -1,6 +1,6 @@
-==================================================================
-LEMON - a Library of Efficient Models and Optimization in Networks
-==================================================================
+=====================================================================
+LEMON - a Library for Efficient Modeling and Optimization in Networks
+=====================================================================
LEMON is an open source library written in C++. It provides
easy-to-use implementations of common data structures and algorithms
diff -r 189760a7cdd0 -r c01a98ce01fd doc/Makefile.am
--- a/doc/Makefile.am Thu May 07 02:05:12 2009 +0200
+++ b/doc/Makefile.am Tue May 12 12:09:55 2009 +0100
@@ -8,6 +8,7 @@
doc/license.dox \
doc/mainpage.dox \
doc/migration.dox \
+ doc/min_cost_flow.dox \
doc/named-param.dox \
doc/namespaces.dox \
doc/html \
diff -r 189760a7cdd0 -r c01a98ce01fd doc/groups.dox
--- a/doc/groups.dox Thu May 07 02:05:12 2009 +0200
+++ b/doc/groups.dox Tue May 12 12:09:55 2009 +0100
@@ -138,16 +138,6 @@
*/
/**
-@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
-@ingroup graphs
-\brief Graph types between real graphs and graph adaptors.
-
-This group contains some graph types between real graphs and graph adaptors.
-These classes wrap graphs to give new functionality as the adaptors do it.
-On the other hand they are not light-weight structures as the adaptors.
-*/
-
-/**
@defgroup maps Maps
@ingroup datas
\brief Map structures implemented in LEMON.
@@ -315,6 +305,7 @@
Tarjan for solving this problem. It also provides functions to query the
minimum cut, which is the dual problem of maximum flow.
+
\ref Circulation is a preflow push-relabel algorithm implemented directly
for finding feasible circulations, which is a somewhat different problem,
but it is strongly related to maximum flow.
@@ -322,86 +313,14 @@
*/
/**
-@defgroup min_cost_flow Minimum Cost Flow Algorithms
+@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
@ingroup algs
\brief Algorithms for finding minimum cost flows and circulations.
This group contains the algorithms for finding minimum cost flows and
-circulations.
-
-The \e minimum \e cost \e flow \e problem is to find a feasible flow of
-minimum total cost from a set of supply nodes to a set of demand nodes
-in a network with capacity constraints (lower and upper bounds)
-and arc costs.
-Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{Z}\f$,
-\f$upper: A\rightarrow\mathbf{Z}\cup\{+\infty\}\f$ denote the lower and
-upper bounds for the flow values on the arcs, for which
-\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
-\f$cost: A\rightarrow\mathbf{Z}\f$ denotes the cost per unit flow
-on the arcs and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
-signed supply values of the nodes.
-If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
-supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
-\f$-sup(u)\f$ demand.
-A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution
-of the following optimization problem.
-
-\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
-\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
- sup(u) \quad \forall u\in V \f]
-\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
-
-The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
-zero or negative in order to have a feasible solution (since the sum
-of the expressions on the left-hand side of the inequalities is zero).
-It means that the total demand must be greater or equal to the total
-supply and all the supplies have to be carried out from the supply nodes,
-but there could be demands that are not satisfied.
-If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
-constraints have to be satisfied with equality, i.e. all demands
-have to be satisfied and all supplies have to be used.
-
-If you need the opposite inequalities in the supply/demand constraints
-(i.e. the total demand is less than the total supply and all the demands
-have to be satisfied while there could be supplies that are not used),
-then you could easily transform the problem to the above form by reversing
-the direction of the arcs and taking the negative of the supply values
-(e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
-However \ref NetworkSimplex algorithm also supports this form directly
-for the sake of convenience.
-
-A feasible solution for this problem can be found using \ref Circulation.
-
-Note that the above formulation is actually more general than the usual
-definition of the minimum cost flow problem, in which strict equalities
-are required in the supply/demand contraints, i.e.
-
-\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
- sup(u) \quad \forall u\in V. \f]
-
-However if the sum of the supply values is zero, then these two problems
-are equivalent. So if you need the equality form, you have to ensure this
-additional contraint for the algorithms.
-
-The dual solution of the minimum cost flow problem is represented by node
-potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
-An \f$f: A\rightarrow\mathbf{Z}\f$ feasible solution of the problem
-is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
-node potentials the following \e complementary \e slackness optimality
-conditions hold.
-
- - For all \f$uv\in A\f$ arcs:
- - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
- - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
- - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
- - For all \f$u\in V\f$ nodes:
- - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
- then \f$\pi(u)=0\f$.
-
-Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
-\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
-\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
+circulations. For more information about this problem and its dual
+solution see \ref min_cost_flow "Minimum Cost Flow Problem".
\ref NetworkSimplex is an efficient implementation of the primal Network
Simplex algorithm for finding minimum cost flows. It also provides dual
@@ -479,10 +398,10 @@
/**
@defgroup spantree Minimum Spanning Tree Algorithms
@ingroup algs
-\brief Algorithms for finding a minimum cost spanning tree in a graph.
+\brief Algorithms for finding minimum cost spanning trees and arborescences.
-This group contains the algorithms for finding a minimum cost spanning
-tree in a graph.
+This group contains the algorithms for finding minimum cost spanning
+trees and arborescences.
*/
/**
diff -r 189760a7cdd0 -r c01a98ce01fd doc/mainpage.dox
--- a/doc/mainpage.dox Thu May 07 02:05:12 2009 +0200
+++ b/doc/mainpage.dox Tue May 12 12:09:55 2009 +0100
@@ -23,8 +23,7 @@
\subsection whatis What is LEMON
-LEMON stands for
-<b>L</b>ibrary of <b>E</b>fficient <b>M</b>odels
+LEMON stands for <b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
and <b>O</b>ptimization in <b>N</b>etworks.
It is a C++ template
library aimed at combinatorial optimization tasks which
@@ -41,14 +40,10 @@
\subsection howtoread How to read the documentation
-If you want to get a quick start and see the most important features then
-take a look at our \ref quicktour
-"Quick Tour to LEMON" which will guide you along.
-
-If you already feel like using our library, see the
+If you would like to get to know the library, see
<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
-If you know what you are looking for then try to find it under the
+If you know what you are looking for, then try to find it under the
<a class="el" href="modules.html">Modules</a> section.
If you are a user of the old (0.x) series of LEMON, please check out the
diff -r 189760a7cdd0 -r c01a98ce01fd doc/min_cost_flow.dox
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/doc/min_cost_flow.dox Tue May 12 12:09:55 2009 +0100
@@ -0,0 +1,153 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2009
+ * 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.
+ *
+ */
+
+namespace lemon {
+
+/**
+\page min_cost_flow Minimum Cost Flow Problem
+
+\section mcf_def Definition (GEQ form)
+
+The \e minimum \e cost \e flow \e problem is to find a feasible flow of
+minimum total cost from a set of supply nodes to a set of demand nodes
+in a network with capacity constraints (lower and upper bounds)
+and arc costs.
+
+Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
+\f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and
+upper bounds for the flow values on the arcs, for which
+\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
+\f$cost: A\rightarrow\mathbf{R}\f$ denotes the cost per unit flow
+on the arcs and \f$sup: V\rightarrow\mathbf{R}\f$ denotes the
+signed supply values of the nodes.
+If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
+supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
+\f$-sup(u)\f$ demand.
+A minimum cost flow is an \f$f: A\rightarrow\mathbf{R}\f$ solution
+of the following optimization problem.
+
+\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
+\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
+ sup(u) \quad \forall u\in V \f]
+\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
+
+The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
+zero or negative in order to have a feasible solution (since the sum
+of the expressions on the left-hand side of the inequalities is zero).
+It means that the total demand must be greater or equal to the total
+supply and all the supplies have to be carried out from the supply nodes,
+but there could be demands that are not satisfied.
+If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
+constraints have to be satisfied with equality, i.e. all demands
+have to be satisfied and all supplies have to be used.
+
+
+\section mcf_algs Algorithms
+
+LEMON contains several algorithms for solving this problem, for more
+information see \ref min_cost_flow_algs "Minimum Cost Flow Algorithms".
+
+A feasible solution for this problem can be found using \ref Circulation.
+
+
+\section mcf_dual Dual Solution
+
+The dual solution of the minimum cost flow problem is represented by
+node potentials \f$\pi: V\rightarrow\mathbf{R}\f$.
+An \f$f: A\rightarrow\mathbf{R}\f$ primal feasible solution is optimal
+if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$ node potentials
+the following \e complementary \e slackness optimality conditions hold.
+
+ - For all \f$uv\in A\f$ arcs:
+ - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
+ - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
+ - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
+ - For all \f$u\in V\f$ nodes:
+ - \f$\pi(u)<=0\f$;
+ - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
+ then \f$\pi(u)=0\f$.
+
+Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
+\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
+\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
+
+All algorithms provide dual solution (node potentials), as well,
+if an optimal flow is found.
+
+
+\section mcf_eq Equality Form
+
+The above \ref mcf_def "definition" is actually more general than the
+usual formulation of the minimum cost flow problem, in which strict
+equalities are required in the supply/demand contraints.
+
+\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
+\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
+ sup(u) \quad \forall u\in V \f]
+\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
+
+However if the sum of the supply values is zero, then these two problems
+are equivalent.
+The \ref min_cost_flow_algs "algorithms" in LEMON support the general
+form, so if you need the equality form, you have to ensure this additional
+contraint manually.
+
+
+\section mcf_leq Opposite Inequalites (LEQ Form)
+
+Another possible definition of the minimum cost flow problem is
+when there are <em>"less or equal"</em> (LEQ) supply/demand constraints,
+instead of the <em>"greater or equal"</em> (GEQ) constraints.
+
+\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
+\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq
+ sup(u) \quad \forall u\in V \f]
+\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
+
+It means that the total demand must be less or equal to the
+total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
+positive) and all the demands have to be satisfied, but there
+could be supplies that are not carried out from the supply
+nodes.
+The equality form is also a special case of this form, of course.
+
+You could easily transform this case to the \ref mcf_def "GEQ form"
+of the problem by reversing the direction of the arcs and taking the
+negative of the supply values (e.g. using \ref ReverseDigraph and
+\ref NegMap adaptors).
+However \ref NetworkSimplex algorithm also supports this form directly
+for the sake of convenience.
+
+Note that the optimality conditions for this supply constraint type are
+slightly differ from the conditions that are discussed for the GEQ form,
+namely the potentials have to be non-negative instead of non-positive.
+An \f$f: A\rightarrow\mathbf{R}\f$ feasible solution of this problem
+is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$
+node potentials the following conditions hold.
+
+ - For all \f$uv\in A\f$ arcs:
+ - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
+ - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
+ - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
+ - For all \f$u\in V\f$ nodes:
+ - \f$\pi(u)>=0\f$;
+ - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
+ then \f$\pi(u)=0\f$.
+
+*/
+}
diff -r 189760a7cdd0 -r c01a98ce01fd lemon/Makefile.am
--- a/lemon/Makefile.am Thu May 07 02:05:12 2009 +0200
+++ b/lemon/Makefile.am Tue May 12 12:09:55 2009 +0100
@@ -111,7 +111,6 @@
bits_HEADERS += \
lemon/bits/alteration_notifier.h \
lemon/bits/array_map.h \
- lemon/bits/base_extender.h \
lemon/bits/bezier.h \
lemon/bits/default_map.h \
lemon/bits/edge_set_extender.h \
diff -r 189760a7cdd0 -r c01a98ce01fd lemon/adaptors.h
--- a/lemon/adaptors.h Thu May 07 02:05:12 2009 +0200
+++ b/lemon/adaptors.h Tue May 12 12:09:55 2009 +0100
@@ -1839,31 +1839,31 @@
typedef typename Digraph::Arc Edge;
typedef typename Digraph::Node Node;
- class Arc : public Edge {
+ class Arc {
friend class UndirectorBase;
protected:
+ Edge _edge;
bool _forward;
- Arc(const Edge& edge, bool forward) :
- Edge(edge), _forward(forward) {}
+ Arc(const Edge& edge, bool forward)
+ : _edge(edge), _forward(forward) {}
public:
Arc() {}
- Arc(Invalid) : Edge(INVALID), _forward(true) {}
+ Arc(Invalid) : _edge(INVALID), _forward(true) {}
+
+ operator const Edge&() const { return _edge; }
bool operator==(const Arc &other) const {
- return _forward == other._forward &&
- static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
+ return _forward == other._forward && _edge == other._edge;
}
bool operator!=(const Arc &other) const {
- return _forward != other._forward ||
- static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
+ return _forward != other._forward || _edge != other._edge;
}
bool operator<(const Arc &other) const {
return _forward < other._forward ||
- (_forward == other._forward &&
- static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
+ (_forward == other._forward && _edge < other._edge);
}
};
@@ -1876,7 +1876,7 @@
}
void first(Arc& a) const {
- _digraph->first(a);
+ _digraph->first(a._edge);
a._forward = true;
}
@@ -1884,7 +1884,7 @@
if (a._forward) {
a._forward = false;
} else {
- _digraph->next(a);
+ _digraph->next(a._edge);
a._forward = true;
}
}
@@ -1898,48 +1898,48 @@
}
void firstOut(Arc& a, const Node& n) const {
- _digraph->firstIn(a, n);
- if( static_cast<const Edge&>(a) != INVALID ) {
+ _digraph->firstIn(a._edge, n);
+ if (a._edge != INVALID ) {
a._forward = false;
} else {
- _digraph->firstOut(a, n);
+ _digraph->firstOut(a._edge, n);
a._forward = true;
}
}
void nextOut(Arc &a) const {
if (!a._forward) {
- Node n = _digraph->target(a);
- _digraph->nextIn(a);
- if (static_cast<const Edge&>(a) == INVALID ) {
- _digraph->firstOut(a, n);
+ Node n = _digraph->target(a._edge);
+ _digraph->nextIn(a._edge);
+ if (a._edge == INVALID) {
+ _digraph->firstOut(a._edge, n);
a._forward = true;
}
}
else {
- _digraph->nextOut(a);
+ _digraph->nextOut(a._edge);
}
}
void firstIn(Arc &a, const Node &n) const {
- _digraph->firstOut(a, n);
- if (static_cast<const Edge&>(a) != INVALID ) {
+ _digraph->firstOut(a._edge, n);
+ if (a._edge != INVALID ) {
a._forward = false;
} else {
- _digraph->firstIn(a, n);
+ _digraph->firstIn(a._edge, n);
a._forward = true;
}
}
void nextIn(Arc &a) const {
if (!a._forward) {
- Node n = _digraph->source(a);
- _digraph->nextOut(a);
- if( static_cast<const Edge&>(a) == INVALID ) {
- _digraph->firstIn(a, n);
+ Node n = _digraph->source(a._edge);
+ _digraph->nextOut(a._edge);
+ if (a._edge == INVALID ) {
+ _digraph->firstIn(a._edge, n);
a._forward = true;
}
}
else {
- _digraph->nextIn(a);
+ _digraph->nextIn(a._edge);
}
}
@@ -1972,19 +1972,16 @@
}
Node source(const Arc &a) const {
- return a._forward ? _digraph->source(a) : _digraph->target(a);
+ return a._forward ? _digraph->source(a._edge) : _digraph->target(a._edge);
}
Node target(const Arc &a) const {
- return a._forward ? _digraph->target(a) : _digraph->source(a);
+ return a._forward ? _digraph->target(a._edge) : _digraph->source(a._edge);
}
static Arc direct(const Edge &e, bool d) {
return Arc(e, d);
}
- Arc direct(const Edge &e, const Node& n) const {
- return Arc(e, _digraph->source(e) == n);
- }
static bool direction(const Arc &a) { return a._forward; }
diff -r 189760a7cdd0 -r c01a98ce01fd lemon/bits/base_extender.h
--- a/lemon/bits/base_extender.h Thu May 07 02:05:12 2009 +0200
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,495 +0,0 @@
-/* -*- mode: C++; indent-tabs-mode: nil; -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library.
- *
- * Copyright (C) 2003-2009
- * 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.
- *
- */
-
-#ifndef LEMON_BITS_BASE_EXTENDER_H
-#define LEMON_BITS_BASE_EXTENDER_H
-
-#include <lemon/core.h>
-#include <lemon/error.h>
-
-#include <lemon/bits/map_extender.h>
-#include <lemon/bits/default_map.h>
-
-#include <lemon/concept_check.h>
-#include <lemon/concepts/maps.h>
-
-//\ingroup digraphbits
-//\file
-//\brief Extenders for the graph types
-namespace lemon {
-
- // \ingroup digraphbits
- //
- // \brief BaseDigraph to BaseGraph extender
- template <typename Base>
- class UndirDigraphExtender : public Base {
- typedef Base Parent;
-
- public:
-
- typedef typename Parent::Arc Edge;
- typedef typename Parent::Node Node;
-
- typedef True UndirectedTag;
-
- class Arc : public Edge {
- friend class UndirDigraphExtender;
-
- protected:
- bool forward;
-
- Arc(const Edge &ue, bool _forward) :
- Edge(ue), forward(_forward) {}
-
- public:
- Arc() {}
-
- // Invalid arc constructor
- Arc(Invalid i) : Edge(i), forward(true) {}
-
- bool operator==(const Arc &that) const {
- return forward==that.forward && Edge(*this)==Edge(that);
- }
- bool operator!=(const Arc &that) const {
- return forward!=that.forward || Edge(*this)!=Edge(that);
- }
- bool operator<(const Arc &that) const {
- return forward<that.forward ||
- (!(that.forward<forward) && Edge(*this)<Edge(that));
- }
- };
-
- // First node of the edge
- Node u(const Edge &e) const {
- return Parent::source(e);
- }
-
- // Source of the given arc
- Node source(const Arc &e) const {
- return e.forward ? Parent::source(e) : Parent::target(e);
- }
-
- // Second node of the edge
- Node v(const Edge &e) const {
- return Parent::target(e);
- }
-
- // Target of the given arc
- Node target(const Arc &e) const {
- return e.forward ? Parent::target(e) : Parent::source(e);
- }
-
- // \brief Directed arc from an edge.
- //
- // Returns a directed arc corresponding to the specified edge.
- // If the given bool is true, the first node of the given edge and
- // the source node of the returned arc are the same.
- static Arc direct(const Edge &e, bool d) {
- return Arc(e, d);
- }
-
- // Returns whether the given directed arc has the same orientation
- // as the corresponding edge.
- static bool direction(const Arc &a) { return a.forward; }
-
- using Parent::first;
- using Parent::next;
-
- void first(Arc &e) const {
- Parent::first(e);
- e.forward=true;
- }
-
- void next(Arc &e) const {
- if( e.forward ) {
- e.forward = false;
- }
- else {
- Parent::next(e);
- e.forward = true;
- }
- }
-
- void firstOut(Arc &e, const Node &n) const {
- Parent::firstIn(e,n);
- if( Edge(e) != INVALID ) {
- e.forward = false;
- }
- else {
- Parent::firstOut(e,n);
- e.forward = true;
- }
- }
- void nextOut(Arc &e) const {
- if( ! e.forward ) {
- Node n = Parent::target(e);
- Parent::nextIn(e);
- if( Edge(e) == INVALID ) {
- Parent::firstOut(e, n);
- e.forward = true;
- }
- }
- else {
- Parent::nextOut(e);
- }
- }
-
- void firstIn(Arc &e, const Node &n) const {
- Parent::firstOut(e,n);
- if( Edge(e) != INVALID ) {
- e.forward = false;
- }
- else {
- Parent::firstIn(e,n);
- e.forward = true;
- }
- }
- void nextIn(Arc &e) const {
- if( ! e.forward ) {
- Node n = Parent::source(e);
- Parent::nextOut(e);
- if( Edge(e) == INVALID ) {
- Parent::firstIn(e, n);
- e.forward = true;
- }
- }
- else {
- Parent::nextIn(e);
- }
- }
-
- void firstInc(Edge &e, bool &d, const Node &n) const {
- d = true;
- Parent::firstOut(e, n);
- if (e != INVALID) return;
- d = false;
- Parent::firstIn(e, n);
- }
-
- void nextInc(Edge &e, bool &d) const {
- if (d) {
- Node s = Parent::source(e);
- Parent::nextOut(e);
- if (e != INVALID) return;
- d = false;
- Parent::firstIn(e, s);
- } else {
- Parent::nextIn(e);
- }
- }
-
- Node nodeFromId(int ix) const {
- return Parent::nodeFromId(ix);
- }
-
- Arc arcFromId(int ix) const {
- return direct(Parent::arcFromId(ix >> 1), bool(ix & 1));
- }
-
- Edge edgeFromId(int ix) const {
- return Parent::arcFromId(ix);
- }
-
- int id(const Node &n) const {
- return Parent::id(n);
- }
-
- int id(const Edge &e) const {
- return Parent::id(e);
- }
-
- int id(const Arc &e) const {
- return 2 * Parent::id(e) + int(e.forward);
- }
-
- int maxNodeId() const {
- return Parent::maxNodeId();
- }
-
- int maxArcId() const {
- return 2 * Parent::maxArcId() + 1;
- }
-
- int maxEdgeId() const {
- return Parent::maxArcId();
- }
-
- int arcNum() const {
- return 2 * Parent::arcNum();
- }
-
- int edgeNum() const {
- return Parent::arcNum();
- }
-
- Arc findArc(Node s, Node t, Arc p = INVALID) const {
- if (p == INVALID) {
- Edge arc = Parent::findArc(s, t);
- if (arc != INVALID) return direct(arc, true);
- arc = Parent::findArc(t, s);
- if (arc != INVALID) return direct(arc, false);
- } else if (direction(p)) {
- Edge arc = Parent::findArc(s, t, p);
- if (arc != INVALID) return direct(arc, true);
- arc = Parent::findArc(t, s);
- if (arc != INVALID) return direct(arc, false);
- } else {
- Edge arc = Parent::findArc(t, s, p);
- if (arc != INVALID) return direct(arc, false);
- }
- return INVALID;
- }
-
- Edge findEdge(Node s, Node t, Edge p = INVALID) const {
- if (s != t) {
- if (p == INVALID) {
- Edge arc = Parent::findArc(s, t);
- if (arc != INVALID) return arc;
- arc = Parent::findArc(t, s);
- if (arc != INVALID) return arc;
- } else if (Parent::s(p) == s) {
- Edge arc = Parent::findArc(s, t, p);
- if (arc != INVALID) return arc;
- arc = Parent::findArc(t, s);
- if (arc != INVALID) return arc;
- } else {
- Edge arc = Parent::findArc(t, s, p);
- if (arc != INVALID) return arc;
- }
- } else {
- return Parent::findArc(s, t, p);
- }
- return INVALID;
- }
- };
-
- template <typename Base>
- class BidirBpGraphExtender : public Base {
- typedef Base Parent;
-
- public:
- typedef BidirBpGraphExtender Digraph;
-
- typedef typename Parent::Node Node;
- typedef typename Parent::Edge Edge;
-
-
- using Parent::first;
- using Parent::next;
-
- using Parent::id;
-
- class Red : public Node {
- friend class BidirBpGraphExtender;
- public:
- Red() {}
- Red(const Node& node) : Node(node) {
- LEMON_DEBUG(Parent::red(node) || node == INVALID,
- typename Parent::NodeSetError());
- }
- Red& operator=(const Node& node) {
- LEMON_DEBUG(Parent::red(node) || node == INVALID,
- typename Parent::NodeSetError());
- Node::operator=(node);
- return *this;
- }
- Red(Invalid) : Node(INVALID) {}
- Red& operator=(Invalid) {
- Node::operator=(INVALID);
- return *this;
- }
- };
-
- void first(Red& node) const {
- Parent::firstRed(static_cast<Node&>(node));
- }
- void next(Red& node) const {
- Parent::nextRed(static_cast<Node&>(node));
- }
-
- int id(const Red& node) const {
- return Parent::redId(node);
- }
-
- class Blue : public Node {
- friend class BidirBpGraphExtender;
- public:
- Blue() {}
- Blue(const Node& node) : Node(node) {
- LEMON_DEBUG(Parent::blue(node) || node == INVALID,
- typename Parent::NodeSetError());
- }
- Blue& operator=(const Node& node) {
- LEMON_DEBUG(Parent::blue(node) || node == INVALID,
- typename Parent::NodeSetError());
- Node::operator=(node);
- return *this;
- }
- Blue(Invalid) : Node(INVALID) {}
- Blue& operator=(Invalid) {
- Node::operator=(INVALID);
- return *this;
- }
- };
-
- void first(Blue& node) const {
- Parent::firstBlue(static_cast<Node&>(node));
- }
- void next(Blue& node) const {
- Parent::nextBlue(static_cast<Node&>(node));
- }
-
- int id(const Blue& node) const {
- return Parent::redId(node);
- }
-
- Node source(const Edge& arc) const {
- return red(arc);
- }
- Node target(const Edge& arc) const {
- return blue(arc);
- }
-
- void firstInc(Edge& arc, bool& dir, const Node& node) const {
- if (Parent::red(node)) {
- Parent::firstFromRed(arc, node);
- dir = true;
- } else {
- Parent::firstFromBlue(arc, node);
- dir = static_cast<Edge&>(arc) == INVALID;
- }
- }
- void nextInc(Edge& arc, bool& dir) const {
- if (dir) {
- Parent::nextFromRed(arc);
- } else {
- Parent::nextFromBlue(arc);
- if (arc == INVALID) dir = true;
- }
- }
-
- class Arc : public Edge {
- friend class BidirBpGraphExtender;
- protected:
- bool forward;
-
- Arc(const Edge& arc, bool _forward)
- : Edge(arc), forward(_forward) {}
-
- public:
- Arc() {}
- Arc (Invalid) : Edge(INVALID), forward(true) {}
- bool operator==(const Arc& i) const {
- return Edge::operator==(i) && forward == i.forward;
- }
- bool operator!=(const Arc& i) const {
- return Edge::operator!=(i) || forward != i.forward;
- }
- bool operator<(const Arc& i) const {
- return Edge::operator<(i) ||
- (!(i.forward<forward) && Edge(*this)<Edge(i));
- }
- };
-
- void first(Arc& arc) const {
- Parent::first(static_cast<Edge&>(arc));
- arc.forward = true;
- }
-
- void next(Arc& arc) const {
- if (!arc.forward) {
- Parent::next(static_cast<Edge&>(arc));
- }
- arc.forward = !arc.forward;
- }
-
- void firstOut(Arc& arc, const Node& node) const {
- if (Parent::red(node)) {
- Parent::firstFromRed(arc, node);
- arc.forward = true;
- } else {
- Parent::firstFromBlue(arc, node);
- arc.forward = static_cast<Edge&>(arc) == INVALID;
- }
- }
- void nextOut(Arc& arc) const {
- if (arc.forward) {
- Parent::nextFromRed(arc);
- } else {
- Parent::nextFromBlue(arc);
- arc.forward = static_cast<Edge&>(arc) == INVALID;
- }
- }
-
- void firstIn(Arc& arc, const Node& node) const {
- if (Parent::blue(node)) {
- Parent::firstFromBlue(arc, node);
- arc.forward = true;
- } else {
- Parent::firstFromRed(arc, node);
- arc.forward = static_cast<Edge&>(arc) == INVALID;
- }
- }
- void nextIn(Arc& arc) const {
- if (arc.forward) {
- Parent::nextFromBlue(arc);
- } else {
- Parent::nextFromRed(arc);
- arc.forward = static_cast<Edge&>(arc) == INVALID;
- }
- }
-
- Node source(const Arc& arc) const {
- return arc.forward ? Parent::red(arc) : Parent::blue(arc);
- }
- Node target(const Arc& arc) const {
- return arc.forward ? Parent::blue(arc) : Parent::red(arc);
- }
-
- int id(const Arc& arc) const {
- return (Parent::id(static_cast<const Edge&>(arc)) << 1) +
- (arc.forward ? 0 : 1);
- }
- Arc arcFromId(int ix) const {
- return Arc(Parent::fromEdgeId(ix >> 1), (ix & 1) == 0);
- }
- int maxArcId() const {
- return (Parent::maxEdgeId() << 1) + 1;
- }
-
- bool direction(const Arc& arc) const {
- return arc.forward;
- }
-
- Arc direct(const Edge& arc, bool dir) const {
- return Arc(arc, dir);
- }
-
- int arcNum() const {
- return 2 * Parent::edgeNum();
- }
-
- int edgeNum() const {
- return Parent::edgeNum();
- }
-
-
- };
-}
-
-#endif
diff -r 189760a7cdd0 -r c01a98ce01fd lemon/concepts/graph.h
--- a/lemon/concepts/graph.h Thu May 07 02:05:12 2009 +0200
+++ b/lemon/concepts/graph.h Tue May 12 12:09:55 2009 +0100
@@ -310,8 +310,8 @@
/// The directed arc type. It can be converted to the
/// edge or it should be inherited from the undirected
- /// arc.
- class Arc : public Edge {
+ /// edge.
+ class Arc {
public:
/// Default constructor
@@ -322,7 +322,7 @@
/// Copy constructor.
///
- Arc(const Arc& e) : Edge(e) { }
+ Arc(const Arc&) { }
/// Initialize the iterator to be invalid.
/// Initialize the iterator to be invalid.
@@ -349,6 +349,8 @@
/// ordering of the items.
bool operator<(Arc) const { return false; }
+ /// Converison to Edge
+ operator Edge() const { return Edge(); }
};
/// This iterator goes through each directed arc.
diff -r 189760a7cdd0 -r c01a98ce01fd lemon/connectivity.h
--- a/lemon/connectivity.h Thu May 07 02:05:12 2009 +0200
+++ b/lemon/connectivity.h Tue May 12 12:09:55 2009 +0100
@@ -42,12 +42,16 @@
/// \ingroup graph_properties
///
- /// \brief Check whether the given undirected graph is connected.
+ /// \brief Check whether an undirected graph is connected.
///
- /// Check whether the given undirected graph is connected.
- /// \param graph The undirected graph.
- /// \return \c true when there is path between any two nodes in the graph.
+ /// This function checks whether the given undirected graph is connected,
+ /// i.e. there is a path between any two nodes in the graph.
+ ///
+ /// \return \c true if the graph is connected.
/// \note By definition, the empty graph is connected.
+ ///
+ /// \see countConnectedComponents(), connectedComponents()
+ /// \see stronglyConnected()
template <typename Graph>
bool connected(const Graph& graph) {
checkConcept<concepts::Graph, Graph>();
@@ -67,12 +71,18 @@
///
/// \brief Count the number of connected components of an undirected graph
///
- /// Count the number of connected components of an undirected graph
+ /// This function counts the number of connected components of the given
+ /// undirected graph.
///
- /// \param graph The graph. It must be undirected.
- /// \return The number of components
+ /// The connected components are the classes of an equivalence relation
+ /// on the nodes of an undirected graph. Two nodes are in the same class
+ /// if they are connected with a path.
+ ///
+ /// \return The number of connected components.
/// \note By definition, the empty graph consists
/// of zero connected components.
+ ///
+ /// \see connected(), connectedComponents()
template <typename Graph>
int countConnectedComponents(const Graph &graph) {
checkConcept<concepts::Graph, Graph>();
@@ -109,17 +119,26 @@
///
/// \brief Find the connected components of an undirected graph
///
- /// Find the connected components of an undirected graph.
+ /// This function finds the connected components of the given undirected
+ /// graph.
+ ///
+ /// The connected components are the classes of an equivalence relation
+ /// on the nodes of an undirected graph. Two nodes are in the same class
+ /// if they are connected with a path.
///
/// \image html connected_components.png
/// \image latex connected_components.eps "Connected components" width=\textwidth
///
- /// \param graph The graph. It must be undirected.
+ /// \param graph The undirected graph.
/// \retval compMap A writable node map. The values will be set from 0 to
- /// the number of the connected components minus one. Each values of the map
- /// will be set exactly once, the values of a certain component will be
+ /// the number of the connected components minus one. Each value of the map
+ /// will be set exactly once, and the values of a certain component will be
/// set continuously.
- /// \return The number of components
+ /// \return The number of connected components.
+ /// \note By definition, the empty graph consists
+ /// of zero connected components.
+ ///
+ /// \see connected(), countConnectedComponents()
template <class Graph, class NodeMap>
int connectedComponents(const Graph &graph, NodeMap &compMap) {
checkConcept<concepts::Graph, Graph>();
@@ -231,15 +250,17 @@
/// \ingroup graph_properties
///
- /// \brief Check whether the given directed graph is strongly connected.
+ /// \brief Check whether a directed graph is strongly connected.
///
- /// Check whether the given directed graph is strongly connected. The
- /// graph is strongly connected when any two nodes of the graph are
+ /// This function checks whether the given directed graph is strongly
+ /// connected, i.e. any two nodes of the digraph are
/// connected with directed paths in both direction.
- /// \return \c false when the graph is not strongly connected.
- /// \see connected
///
- /// \note By definition, the empty graph is strongly connected.
+ /// \return \c true if the digraph is strongly connected.
+ /// \note By definition, the empty digraph is strongly connected.
+ ///
+ /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()
+ /// \see connected()
template <typename Digraph>
bool stronglyConnected(const Digraph& digraph) {
checkConcept<concepts::Digraph, Digraph>();
@@ -270,7 +291,7 @@
typedef typename RDigraph::NodeIt RNodeIt;
RDigraph rdigraph(digraph);
- typedef DfsVisitor<Digraph> RVisitor;
+ typedef DfsVisitor<RDigraph> RVisitor;
RVisitor rvisitor;
DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
@@ -289,18 +310,22 @@
/// \ingroup graph_properties
///
- /// \brief Count the strongly connected components of a directed graph
+ /// \brief Count the number of strongly connected components of a
+ /// directed graph
///
- /// Count the strongly connected components of a directed graph.
+ /// This function counts the number of strongly connected components of
+ /// the given directed graph.
+ ///
/// The strongly connected components are the classes of an
- /// equivalence relation on the nodes of the graph. Two nodes are in
+ /// equivalence relation on the nodes of a digraph. Two nodes are in
/// the same class if they are connected with directed paths in both
/// direction.
///
- /// \param digraph The graph.
- /// \return The number of components
- /// \note By definition, the empty graph has zero
+ /// \return The number of strongly connected components.
+ /// \note By definition, the empty digraph has zero
/// strongly connected components.
+ ///
+ /// \see stronglyConnected(), stronglyConnectedComponents()
template <typename Digraph>
int countStronglyConnectedComponents(const Digraph& digraph) {
checkConcept<concepts::Digraph, Digraph>();
@@ -355,13 +380,15 @@
///
/// \brief Find the strongly connected components of a directed graph
///
- /// Find the strongly connected components of a directed graph. The
- /// strongly connected components are the classes of an equivalence
- /// relation on the nodes of the graph. Two nodes are in
- /// relationship when there are directed paths between them in both
- /// direction. In addition, the numbering of components will satisfy
- /// that there is no arc going from a higher numbered component to
- /// a lower.
+ /// This function finds the strongly connected components of the given
+ /// directed graph. In addition, the numbering of the components will
+ /// satisfy that there is no arc going from a higher numbered component
+ /// to a lower one (i.e. it provides a topological order of the components).
+ ///
+ /// The strongly connected components are the classes of an
+ /// equivalence relation on the nodes of a digraph. Two nodes are in
+ /// the same class if they are connected with directed paths in both
+ /// direction.
///
/// \image html strongly_connected_components.png
/// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
@@ -369,9 +396,13 @@
/// \param digraph The digraph.
/// \retval compMap A writable node map. The values will be set from 0 to
/// the number of the strongly connected components minus one. Each value
- /// of the map will be set exactly once, the values of a certain component
- /// will be set continuously.
- /// \return The number of components
+ /// of the map will be set exactly once, and the values of a certain
+ /// component will be set continuously.
+ /// \return The number of strongly connected components.
+ /// \note By definition, the empty digraph has zero
+ /// strongly connected components.
+ ///
+ /// \see stronglyConnected(), countStronglyConnectedComponents()
template <typename Digraph, typename NodeMap>
int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
checkConcept<concepts::Digraph, Digraph>();
@@ -424,19 +455,24 @@
///
/// \brief Find the cut arcs of the strongly connected components.
///
- /// Find the cut arcs of the strongly connected components.
- /// The strongly connected components are the classes of an equivalence
- /// relation on the nodes of the graph. Two nodes are in relationship
- /// when there are directed paths between them in both direction.
+ /// This function finds the cut arcs of the strongly connected components
+ /// of the given digraph.
+ ///
+ /// The strongly connected components are the classes of an
+ /// equivalence relation on the nodes of a digraph. Two nodes are in
+ /// the same class if they are connected with directed paths in both
+ /// direction.
/// The strongly connected components are separated by the cut arcs.
///
- /// \param graph The graph.
- /// \retval cutMap A writable node map. The values will be set true when the
- /// arc is a cut arc.
+ /// \param digraph The digraph.
+ /// \retval cutMap A writable arc map. The values will be set to \c true
+ /// for the cut arcs (exactly once for each cut arc), and will not be
+ /// changed for other arcs.
+ /// \return The number of cut arcs.
///
- /// \return The number of cut arcs
+ /// \see stronglyConnected(), stronglyConnectedComponents()
template <typename Digraph, typename ArcMap>
- int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) {
+ int stronglyConnectedCutArcs(const Digraph& digraph, ArcMap& cutMap) {
checkConcept<concepts::Digraph, Digraph>();
typedef typename Digraph::Node Node;
typedef typename Digraph::Arc Arc;
@@ -448,13 +484,13 @@
typedef std::vector<Node> Container;
typedef typename Container::iterator Iterator;
- Container nodes(countNodes(graph));
+ Container nodes(countNodes(digraph));
typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
Visitor visitor(nodes.begin());
- DfsVisit<Digraph, Visitor> dfs(graph, visitor);
+ DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
dfs.init();
- for (NodeIt it(graph); it != INVALID; ++it) {
+ for (NodeIt it(digraph); it != INVALID; ++it) {
if (!dfs.reached(it)) {
dfs.addSource(it);
dfs.start();
@@ -464,14 +500,14 @@
typedef typename Container::reverse_iterator RIterator;
typedef ReverseDigraph<const Digraph> RDigraph;
- RDigraph rgraph(graph);
+ RDigraph rdigraph(digraph);
int cutNum = 0;
typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
- RVisitor rvisitor(rgraph, cutMap, cutNum);
+ RVisitor rvisitor(rdigraph, cutMap, cutNum);
- DfsVisit<RDigraph, RVisitor> rdfs(rgraph, rvisitor);
+ DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
rdfs.init();
for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
@@ -706,14 +742,15 @@
/// \ingroup graph_properties
///
- /// \brief Checks the graph is bi-node-connected.
+ /// \brief Check whether an undirected graph is bi-node-connected.
///
- /// This function checks that the undirected graph is bi-node-connected
- /// graph. The graph is bi-node-connected if any two undirected edge is
- /// on same circle.
+ /// This function checks whether the given undirected graph is
+ /// bi-node-connected, i.e. any two edges are on same circle.
///
- /// \param graph The graph.
- /// \return \c true when the graph bi-node-connected.
+ /// \return \c true if the graph bi-node-connected.
+ /// \note By definition, the empty graph is bi-node-connected.
+ ///
+ /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()
template <typename Graph>
bool biNodeConnected(const Graph& graph) {
return countBiNodeConnectedComponents(graph) <= 1;
@@ -721,15 +758,19 @@
/// \ingroup graph_properties
///
- /// \brief Count the biconnected components.
+ /// \brief Count the number of bi-node-connected components of an
+ /// undirected graph.
///
- /// This function finds the bi-node-connected components in an undirected
- /// graph. The biconnected components are the classes of an equivalence
- /// relation on the undirected edges. Two undirected edge is in relationship
- /// when they are on same circle.
+ /// This function counts the number of bi-node-connected components of
+ /// the given undirected graph.
///
- /// \param graph The graph.
- /// \return The number of components.
+ /// The bi-node-connected components are the classes of an equivalence
+ /// relation on the edges of a undirected graph. Two edges are in the
+ /// same class if they are on same circle.
+ ///
+ /// \return The number of bi-node-connected components.
+ ///
+ /// \see biNodeConnected(), biNodeConnectedComponents()
template <typename Graph>
int countBiNodeConnectedComponents(const Graph& graph) {
checkConcept<concepts::Graph, Graph>();
@@ -756,22 +797,26 @@
/// \ingroup graph_properties
///
- /// \brief Find the bi-node-connected components.
+ /// \brief Find the bi-node-connected components of an undirected graph.
///
- /// This function finds the bi-node-connected components in an undirected
- /// graph. The bi-node-connected components are the classes of an equivalence
- /// relation on the undirected edges. Two undirected edge are in relationship
- /// when they are on same circle.
+ /// This function finds the bi-node-connected components of the given
+ /// undirected graph.
+ ///
+ /// The bi-node-connected components are the classes of an equivalence
+ /// relation on the edges of a undirected graph. Two edges are in the
+ /// same class if they are on same circle.
///
/// \image html node_biconnected_components.png
/// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
///
- /// \param graph The graph.
- /// \retval compMap A writable uedge map. The values will be set from 0
- /// to the number of the biconnected components minus one. Each values
- /// of the map will be set exactly once, the values of a certain component
- /// will be set continuously.
- /// \return The number of components.
+ /// \param graph The undirected graph.
+ /// \retval compMap A writable edge map. The values will be set from 0
+ /// to the number of the bi-node-connected components minus one. Each
+ /// value of the map will be set exactly once, and the values of a
+ /// certain component will be set continuously.
+ /// \return The number of bi-node-connected components.
+ ///
+ /// \see biNodeConnected(), countBiNodeConnectedComponents()
template <typename Graph, typename EdgeMap>
int biNodeConnectedComponents(const Graph& graph,
EdgeMap& compMap) {
@@ -801,18 +846,25 @@
/// \ingroup graph_properties
///
- /// \brief Find the bi-node-connected cut nodes.
+ /// \brief Find the bi-node-connected cut nodes in an undirected graph.
///
- /// This function finds the bi-node-connected cut nodes in an undirected
- /// graph. The bi-node-connected components are the classes of an equivalence
- /// relation on the undirected edges. Two undirected edges are in
- /// relationship when they are on same circle. The biconnected components
- /// are separted by nodes which are the cut nodes of the components.
+ /// This function finds the bi-node-connected cut nodes in the given
+ /// undirected graph.
///
- /// \param graph The graph.
- /// \retval cutMap A writable edge map. The values will be set true when
- /// the node separate two or more components.
+ /// The bi-node-connected components are the classes of an equivalence
+ /// relation on the edges of a undirected graph. Two edges are in the
+ /// same class if they are on same circle.
+ /// The bi-node-connected components are separted by the cut nodes of
+ /// the components.
+ ///
+ /// \param graph The undirected graph.
+ /// \retval cutMap A writable node map. The values will be set to
+ /// \c true for the nodes that separate two or more components
+ /// (exactly once for each cut node), and will not be changed for
+ /// other nodes.
/// \return The number of the cut nodes.
+ ///
+ /// \see biNodeConnected(), biNodeConnectedComponents()
template <typename Graph, typename NodeMap>
int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {
checkConcept<concepts::Graph, Graph>();
@@ -1031,14 +1083,16 @@
/// \ingroup graph_properties
///
- /// \brief Checks that the graph is bi-edge-connected.
+ /// \brief Check whether an undirected graph is bi-edge-connected.
///
- /// This function checks that the graph is bi-edge-connected. The undirected
- /// graph is bi-edge-connected when any two nodes are connected with two
- /// edge-disjoint paths.
+ /// This function checks whether the given undirected graph is
+ /// bi-edge-connected, i.e. any two nodes are connected with at least
+ /// two edge-disjoint paths.
///
- /// \param graph The undirected graph.
- /// \return The number of components.
+ /// \return \c true if the graph is bi-edge-connected.
+ /// \note By definition, the empty graph is bi-edge-connected.
+ ///
+ /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents()
template <typename Graph>
bool biEdgeConnected(const Graph& graph) {
return countBiEdgeConnectedComponents(graph) <= 1;
@@ -1046,15 +1100,20 @@
/// \ingroup graph_properties
///
- /// \brief Count the bi-edge-connected components.
+ /// \brief Count the number of bi-edge-connected components of an
+ /// undirected graph.
///
- /// This function count the bi-edge-connected components in an undirected
- /// graph. The bi-edge-connected components are the classes of an equivalence
- /// relation on the nodes. Two nodes are in relationship when they are
- /// connected with at least two edge-disjoint paths.
+ /// This function counts the number of bi-edge-connected components of
+ /// the given undirected graph.
///
- /// \param graph The undirected graph.
- /// \return The number of components.
+ /// The bi-edge-connected components are the classes of an equivalence
+ /// relation on the nodes of an undirected graph. Two nodes are in the
+ /// same class if they are connected with at least two edge-disjoint
+ /// paths.
+ ///
+ /// \return The number of bi-edge-connected components.
+ ///
+ /// \see biEdgeConnected(), biEdgeConnectedComponents()
template <typename Graph>
int countBiEdgeConnectedComponents(const Graph& graph) {
checkConcept<concepts::Graph, Graph>();
@@ -1081,22 +1140,27 @@
/// \ingroup graph_properties
///
- /// \brief Find the bi-edge-connected components.
+ /// \brief Find the bi-edge-connected components of an undirected graph.
///
- /// This function finds the bi-edge-connected components in an undirected
- /// graph. The bi-edge-connected components are the classes of an equivalence
- /// relation on the nodes. Two nodes are in relationship when they are
- /// connected at least two edge-disjoint paths.
+ /// This function finds the bi-edge-connected components of the given
+ /// undirected graph.
+ ///
+ /// The bi-edge-connected components are the classes of an equivalence
+ /// relation on the nodes of an undirected graph. Two nodes are in the
+ /// same class if they are connected with at least two edge-disjoint
+ /// paths.
///
/// \image html edge_biconnected_components.png
/// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
///
- /// \param graph The graph.
+ /// \param graph The undirected graph.
/// \retval compMap A writable node map. The values will be set from 0 to
- /// the number of the biconnected components minus one. Each values
- /// of the map will be set exactly once, the values of a certain component
- /// will be set continuously.
- /// \return The number of components.
+ /// the number of the bi-edge-connected components minus one. Each value
+ /// of the map will be set exactly once, and the values of a certain
+ /// component will be set continuously.
+ /// \return The number of bi-edge-connected components.
+ ///
+ /// \see biEdgeConnected(), countBiEdgeConnectedComponents()
template <typename Graph, typename NodeMap>
int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
checkConcept<concepts::Graph, Graph>();
@@ -1125,19 +1189,25 @@
/// \ingroup graph_properties
///
- /// \brief Find the bi-edge-connected cut edges.
+ /// \brief Find the bi-edge-connected cut edges in an undirected graph.
///
- /// This function finds the bi-edge-connected components in an undirected
- /// graph. The bi-edge-connected components are the classes of an equivalence
- /// relation on the nodes. Two nodes are in relationship when they are
- /// connected with at least two edge-disjoint paths. The bi-edge-connected
- /// components are separted by edges which are the cut edges of the
- /// components.
+ /// This function finds the bi-edge-connected cut edges in the given
+ /// undirected graph.
///
- /// \param graph The graph.
- /// \retval cutMap A writable node map. The values will be set true when the
- /// edge is a cut edge.
+ /// The bi-edge-connected components are the classes of an equivalence
+ /// relation on the nodes of an undirected graph. Two nodes are in the
+ /// same class if they are connected with at least two edge-disjoint
+ /// paths.
+ /// The bi-edge-connected components are separted by the cut edges of
+ /// the components.
+ ///
+ /// \param graph The undirected graph.
+ /// \retval cutMap A writable edge map. The values will be set to \c true
+ /// for the cut edges (exactly once for each cut edge), and will not be
+ /// changed for other edges.
/// \return The number of cut edges.
+ ///
+ /// \see biEdgeConnected(), biEdgeConnectedComponents()
template <typename Graph, typename EdgeMap>
int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
checkConcept<concepts::Graph, Graph>();
@@ -1189,19 +1259,62 @@
/// \ingroup graph_properties
///
+ /// \brief Check whether a digraph is DAG.
+ ///
+ /// This function checks whether the given digraph is DAG, i.e.
+ /// \e Directed \e Acyclic \e Graph.
+ /// \return \c true if there is no directed cycle in the digraph.
+ /// \see acyclic()
+ template <typename Digraph>
+ bool dag(const Digraph& digraph) {
+
+ checkConcept<concepts::Digraph, Digraph>();
+
+ typedef typename Digraph::Node Node;
+ typedef typename Digraph::NodeIt NodeIt;
+ typedef typename Digraph::Arc Arc;
+
+ typedef typename Digraph::template NodeMap<bool> ProcessedMap;
+
+ typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
+ Create dfs(digraph);
+
+ ProcessedMap processed(digraph);
+ dfs.processedMap(processed);
+
+ dfs.init();
+ for (NodeIt it(digraph); it != INVALID; ++it) {
+ if (!dfs.reached(it)) {
+ dfs.addSource(it);
+ while (!dfs.emptyQueue()) {
+ Arc arc = dfs.nextArc();
+ Node target = digraph.target(arc);
+ if (dfs.reached(target) && !processed[target]) {
+ return false;
+ }
+ dfs.processNextArc();
+ }
+ }
+ }
+ return true;
+ }
+
+ /// \ingroup graph_properties
+ ///
/// \brief Sort the nodes of a DAG into topolgical order.
///
- /// Sort the nodes of a DAG into topolgical order.
+ /// This function sorts the nodes of the given acyclic digraph (DAG)
+ /// into topolgical order.
///
- /// \param graph The graph. It must be directed and acyclic.
+ /// \param digraph The digraph, which must be DAG.
/// \retval order A writable node map. The values will be set from 0 to
- /// the number of the nodes in the graph minus one. Each values of the map
- /// will be set exactly once, the values will be set descending order.
+ /// the number of the nodes in the digraph minus one. Each value of the
+ /// map will be set exactly once, and the values will be set descending
+ /// order.
///
- /// \see checkedTopologicalSort
- /// \see dag
+ /// \see dag(), checkedTopologicalSort()
template <typename Digraph, typename NodeMap>
- void topologicalSort(const Digraph& graph, NodeMap& order) {
+ void topologicalSort(const Digraph& digraph, NodeMap& order) {
using namespace _connectivity_bits;
checkConcept<concepts::Digraph, Digraph>();
@@ -1212,13 +1325,13 @@
typedef typename Digraph::Arc Arc;
TopologicalSortVisitor<Digraph, NodeMap>
- visitor(order, countNodes(graph));
+ visitor(order, countNodes(digraph));
DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
- dfs(graph, visitor);
+ dfs(digraph, visitor);
dfs.init();
- for (NodeIt it(graph); it != INVALID; ++it) {
+ for (NodeIt it(digraph); it != INVALID; ++it) {
if (!dfs.reached(it)) {
dfs.addSource(it);
dfs.start();
@@ -1230,18 +1343,18 @@
///
/// \brief Sort the nodes of a DAG into topolgical order.
///
- /// Sort the nodes of a DAG into topolgical order. It also checks
- /// that the given graph is DAG.
+ /// This function sorts the nodes of the given acyclic digraph (DAG)
+ /// into topolgical order and also checks whether the given digraph
+ /// is DAG.
///
- /// \param digraph The graph. It must be directed and acyclic.
- /// \retval order A readable - writable node map. The values will be set
- /// from 0 to the number of the nodes in the graph minus one. Each values
- /// of the map will be set exactly once, the values will be set descending
- /// order.
- /// \return \c false when the graph is not DAG.
+ /// \param digraph The digraph.
+ /// \retval order A readable and writable node map. The values will be
+ /// set from 0 to the number of the nodes in the digraph minus one.
+ /// Each value of the map will be set exactly once, and the values will
+ /// be set descending order.
+ /// \return \c false if the digraph is not DAG.
///
- /// \see topologicalSort
- /// \see dag
+ /// \see dag(), topologicalSort()
template <typename Digraph, typename NodeMap>
bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
using namespace _connectivity_bits;
@@ -1283,54 +1396,11 @@
/// \ingroup graph_properties
///
- /// \brief Check that the given directed graph is a DAG.
+ /// \brief Check whether an undirected graph is acyclic.
///
- /// Check that the given directed graph is a DAG. The DAG is
- /// an Directed Acyclic Digraph.
- /// \return \c false when the graph is not DAG.
- /// \see acyclic
- template <typename Digraph>
- bool dag(const Digraph& digraph) {
-
- checkConcept<concepts::Digraph, Digraph>();
-
- typedef typename Digraph::Node Node;
- typedef typename Digraph::NodeIt NodeIt;
- typedef typename Digraph::Arc Arc;
-
- typedef typename Digraph::template NodeMap<bool> ProcessedMap;
-
- typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
- Create dfs(digraph);
-
- ProcessedMap processed(digraph);
- dfs.processedMap(processed);
-
- dfs.init();
- for (NodeIt it(digraph); it != INVALID; ++it) {
- if (!dfs.reached(it)) {
- dfs.addSource(it);
- while (!dfs.emptyQueue()) {
- Arc edge = dfs.nextArc();
- Node target = digraph.target(edge);
- if (dfs.reached(target) && !processed[target]) {
- return false;
- }
- dfs.processNextArc();
- }
- }
- }
- return true;
- }
-
- /// \ingroup graph_properties
- ///
- /// \brief Check that the given undirected graph is acyclic.
- ///
- /// Check that the given undirected graph acyclic.
- /// \param graph The undirected graph.
- /// \return \c true when there is no circle in the graph.
- /// \see dag
+ /// This function checks whether the given undirected graph is acyclic.
+ /// \return \c true if there is no cycle in the graph.
+ /// \see dag()
template <typename Graph>
bool acyclic(const Graph& graph) {
checkConcept<concepts::Graph, Graph>();
@@ -1343,11 +1413,11 @@
if (!dfs.reached(it)) {
dfs.addSource(it);
while (!dfs.emptyQueue()) {
- Arc edge = dfs.nextArc();
- Node source = graph.source(edge);
- Node target = graph.target(edge);
+ Arc arc = dfs.nextArc();
+ Node source = graph.source(arc);
+ Node target = graph.target(arc);
if (dfs.reached(target) &&
- dfs.predArc(source) != graph.oppositeArc(edge)) {
+ dfs.predArc(source) != graph.oppositeArc(arc)) {
return false;
}
dfs.processNextArc();
@@ -1359,26 +1429,27 @@
/// \ingroup graph_properties
///
- /// \brief Check that the given undirected graph is tree.
+ /// \brief Check whether an undirected graph is tree.
///
- /// Check that the given undirected graph is tree.
- /// \param graph The undirected graph.
- /// \return \c true when the graph is acyclic and connected.
+ /// This function checks whether the given undirected graph is tree.
+ /// \return \c true if the graph is acyclic and connected.
+ /// \see acyclic(), connected()
template <typename Graph>
bool tree(const Graph& graph) {
checkConcept<concepts::Graph, Graph>();
typedef typename Graph::Node Node;
typedef typename Graph::NodeIt NodeIt;
typedef typename Graph::Arc Arc;
+ if (NodeIt(graph) == INVALID) return true;
Dfs<Graph> dfs(graph);
dfs.init();
dfs.addSource(NodeIt(graph));
while (!dfs.emptyQueue()) {
- Arc edge = dfs.nextArc();
- Node source = graph.source(edge);
- Node target = graph.target(edge);
+ Arc arc = dfs.nextArc();
+ Node source = graph.source(arc);
+ Node target = graph.target(arc);
if (dfs.reached(target) &&
- dfs.predArc(source) != graph.oppositeArc(edge)) {
+ dfs.predArc(source) != graph.oppositeArc(arc)) {
return false;
}
dfs.processNextArc();
@@ -1451,15 +1522,14 @@
/// \ingroup graph_properties
///
- /// \brief Check if the given undirected graph is bipartite or not
+ /// \brief Check whether an undirected graph is bipartite.
///
- /// The function checks if the given undirected \c graph graph is bipartite
- /// or not. The \ref Bfs algorithm is used to calculate the result.
- /// \param graph The undirected graph.
- /// \return \c true if \c graph is bipartite, \c false otherwise.
- /// \sa bipartitePartitions
+ /// The function checks whether the given undirected graph is bipartite.
+ /// \return \c true if the graph is bipartite.
+ ///
+ /// \see bipartitePartitions()
template<typename Graph>
- inline bool bipartite(const Graph &graph){
+ bool bipartite(const Graph &graph){
using namespace _connectivity_bits;
checkConcept<concepts::Graph, Graph>();
@@ -1488,25 +1558,27 @@
/// \ingroup graph_properties
///
- /// \brief Check if the given undirected graph is bipartite or not
+ /// \brief Find the bipartite partitions of an undirected graph.
///
- /// The function checks if the given undirected graph is bipartite
- /// or not. The \ref Bfs algorithm is used to calculate the result.
- /// During the execution, the \c partMap will be set as the two
- /// partitions of the graph.
+ /// This function checks whether the given undirected graph is bipartite
+ /// and gives back the bipartite partitions.
///
/// \image html bipartite_partitions.png
/// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
///
/// \param graph The undirected graph.
- /// \retval partMap A writable bool map of nodes. It will be set as the
- /// two partitions of the graph.
- /// \return \c true if \c graph is bipartite, \c false otherwise.
+ /// \retval partMap A writable node map of \c bool (or convertible) value
+ /// type. The values will be set to \c true for one component and
+ /// \c false for the other one.
+ /// \return \c true if the graph is bipartite, \c false otherwise.
+ ///
+ /// \see bipartite()
template<typename Graph, typename NodeMap>
- inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
+ bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
using namespace _connectivity_bits;
checkConcept<concepts::Graph, Graph>();
+ checkConcept<concepts::WriteMap<typename Graph::Node, bool>, NodeMap>();
typedef typename Graph::Node Node;
typedef typename Graph::NodeIt NodeIt;
@@ -1531,53 +1603,59 @@
return true;
}
- /// \brief Returns true when there are not loop edges in the graph.
+ /// \ingroup graph_properties
///
- /// Returns true when there are not loop edges in the graph.
- template <typename Digraph>
- bool loopFree(const Digraph& digraph) {
- for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) {
- if (digraph.source(it) == digraph.target(it)) return false;
+ /// \brief Check whether the given graph contains no loop arcs/edges.
+ ///
+ /// This function returns \c true if there are no loop arcs/edges in
+ /// the given graph. It works for both directed and undirected graphs.
+ template <typename Graph>
+ bool loopFree(const Graph& graph) {
+ for (typename Graph::ArcIt it(graph); it != INVALID; ++it) {
+ if (graph.source(it) == graph.target(it)) return false;
}
return true;
}
- /// \brief Returns true when there are not parallel edges in the graph.
+ /// \ingroup graph_properties
///
- /// Returns true when there are not parallel edges in the graph.
- template <typename Digraph>
- bool parallelFree(const Digraph& digraph) {
- typename Digraph::template NodeMap<bool> reached(digraph, false);
- for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
- for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
- if (reached[digraph.target(a)]) return false;
- reached.set(digraph.target(a), true);
+ /// \brief Check whether the given graph contains no parallel arcs/edges.
+ ///
+ /// This function returns \c true if there are no parallel arcs/edges in
+ /// the given graph. It works for both directed and undirected graphs.
+ template <typename Graph>
+ bool parallelFree(const Graph& graph) {
+ typename Graph::template NodeMap<int> reached(graph, 0);
+ int cnt = 1;
+ for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
+ for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
+ if (reached[graph.target(a)] == cnt) return false;
+ reached[graph.target(a)] = cnt;
}
- for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
- reached.set(digraph.target(a), false);
- }
+ ++cnt;
}
return true;
}
- /// \brief Returns true when there are not loop edges and parallel
- /// edges in the graph.
+ /// \ingroup graph_properties
///
- /// Returns true when there are not loop edges and parallel edges in
- /// the graph.
- template <typename Digraph>
- bool simpleDigraph(const Digraph& digraph) {
- typename Digraph::template NodeMap<bool> reached(digraph, false);
- for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
- reached.set(n, true);
- for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
- if (reached[digraph.target(a)]) return false;
- reached.set(digraph.target(a), true);
+ /// \brief Check whether the given graph is simple.
+ ///
+ /// This function returns \c true if the given graph is simple, i.e.
+ /// it contains no loop arcs/edges and no parallel arcs/edges.
+ /// The function works for both directed and undirected graphs.
+ /// \see loopFree(), parallelFree()
+ template <typename Graph>
+ bool simpleGraph(const Graph& graph) {
+ typename Graph::template NodeMap<int> reached(graph, 0);
+ int cnt = 1;
+ for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
+ reached[n] = cnt;
+ for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
+ if (reached[graph.target(a)] == cnt) return false;
+ reached[graph.target(a)] = cnt;
}
- for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
- reached.set(digraph.target(a), false);
- }
- reached.set(n, false);
+ ++cnt;
}
return true;
}
diff -r 189760a7cdd0 -r c01a98ce01fd lemon/edge_set.h
--- a/lemon/edge_set.h Thu May 07 02:05:12 2009 +0200
+++ b/lemon/edge_set.h Tue May 12 12:09:55 2009 +0100
@@ -22,7 +22,7 @@
#include <lemon/core.h>
#include <lemon/bits/edge_set_extender.h>
-/// \ingroup semi_adaptors
+/// \ingroup graphs
/// \file
/// \brief ArcSet and EdgeSet classes.
///
@@ -230,7 +230,7 @@
};
- /// \ingroup semi_adaptors
+ /// \ingroup graphs
///
/// \brief Digraph using a node set of another digraph or graph and
/// an own arc set.
@@ -654,7 +654,7 @@
};
- /// \ingroup semi_adaptors
+ /// \ingroup graphs
///
/// \brief Graph using a node set of another digraph or graph and an
/// own edge set.
@@ -913,7 +913,7 @@
};
- /// \ingroup semi_adaptors
+ /// \ingroup graphs
///
/// \brief Digraph using a node set of another digraph or graph and
/// an own arc set.
@@ -1257,7 +1257,7 @@
};
- /// \ingroup semi_adaptors
+ /// \ingroup graphs
///
/// \brief Graph using a node set of another digraph or graph and an
/// own edge set.
diff -r 189760a7cdd0 -r c01a98ce01fd lemon/euler.h
--- a/lemon/euler.h Thu May 07 02:05:12 2009 +0200
+++ b/lemon/euler.h Tue May 12 12:09:55 2009 +0100
@@ -244,10 +244,10 @@
};
- ///Check if the given graph is \e Eulerian
+ ///Check if the given graph is Eulerian
/// \ingroup graph_properties
- ///This function checks if the given graph is \e Eulerian.
+ ///This function checks if the given graph is Eulerian.
///It works for both directed and undirected graphs.
///
///By definition, a digraph is called \e Eulerian if
diff -r 189760a7cdd0 -r c01a98ce01fd lemon/glpk.h
--- a/lemon/glpk.h Thu May 07 02:05:12 2009 +0200
+++ b/lemon/glpk.h Tue May 12 12:09:55 2009 +0100
@@ -26,9 +26,10 @@
#include <lemon/lp_base.h>
// forward declaration
-#ifndef _GLP_PROB
+#if !defined _GLP_PROB && !defined GLP_PROB
#define _GLP_PROB
-typedef struct { double _prob; } glp_prob;
+#define GLP_PROB
+typedef struct { double _opaque_prob; } glp_prob;
/* LP/MIP problem object */
#endif
diff -r 189760a7cdd0 -r c01a98ce01fd lemon/lemon.pc.in
--- a/lemon/lemon.pc.in Thu May 07 02:05:12 2009 +0200
+++ b/lemon/lemon.pc.in Tue May 12 12:09:55 2009 +0100
@@ -4,7 +4,7 @@
includedir=@includedir@
Name: @PACKAGE_NAME@
-Description: Library of Efficient Models and Optimization in Networks
+Description: Library for Efficient Modeling and Optimization in Networks
Version: @PACKAGE_VERSION@
Libs: -L${libdir} -lemon @GLPK_LIBS@ @CPLEX_LIBS@ @SOPLEX_LIBS@ @CLP_LIBS@ @CBC_LIBS@
Cflags: -I${includedir}
diff -r 189760a7cdd0 -r c01a98ce01fd lemon/matching.h
--- a/lemon/matching.h Thu May 07 02:05:12 2009 +0200
+++ b/lemon/matching.h Tue May 12 12:09:55 2009 +0100
@@ -499,7 +499,7 @@
///
/// This function runs the original Edmonds' algorithm.
///
- /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be
+ /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be
/// called before using this function.
void startSparse() {
for(NodeIt n(_graph); n != INVALID; ++n) {
@@ -518,7 +518,7 @@
/// This function runs Edmonds' algorithm with a heuristic of postponing
/// shrinks, therefore resulting in a faster algorithm for dense graphs.
///
- /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be
+ /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be
/// called before using this function.
void startDense() {
for(NodeIt n(_graph); n != INVALID; ++n) {
diff -r 189760a7cdd0 -r c01a98ce01fd lemon/network_simplex.h
--- a/lemon/network_simplex.h Thu May 07 02:05:12 2009 +0200
+++ b/lemon/network_simplex.h Tue May 12 12:09:55 2009 +0100
@@ -19,7 +19,7 @@
#ifndef LEMON_NETWORK_SIMPLEX_H
#define LEMON_NETWORK_SIMPLEX_H
-/// \ingroup min_cost_flow
+/// \ingroup min_cost_flow_algs
///
/// \file
/// \brief Network Simplex algorithm for finding a minimum cost flow.
@@ -33,7 +33,7 @@
namespace lemon {
- /// \addtogroup min_cost_flow
+ /// \addtogroup min_cost_flow_algs
/// @{
/// \brief Implementation of the primal Network Simplex algorithm
@@ -102,50 +102,16 @@
/// i.e. the direction of the inequalities in the supply/demand
/// constraints of the \ref min_cost_flow "minimum cost flow problem".
///
- /// The default supply type is \c GEQ, since this form is supported
- /// by other minimum cost flow algorithms and the \ref Circulation
- /// algorithm, as well.
- /// The \c LEQ problem type can be selected using the \ref supplyType()
- /// function.
- ///
- /// Note that the equality form is a special case of both supply types.
+ /// The default supply type is \c GEQ, the \c LEQ type can be
+ /// selected using \ref supplyType().
+ /// The equality form is a special case of both supply types.
enum SupplyType {
-
/// This option means that there are <em>"greater or equal"</em>
- /// supply/demand constraints in the definition, i.e. the exact
- /// formulation of the problem is the following.
- /**
- \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
- \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
- sup(u) \quad \forall u\in V \f]
- \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
- */
- /// It means that the total demand must be greater or equal to the
- /// total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
- /// negative) and all the supplies have to be carried out from
- /// the supply nodes, but there could be demands that are not
- /// satisfied.
+ /// supply/demand constraints in the definition of the problem.
GEQ,
- /// It is just an alias for the \c GEQ option.
- CARRY_SUPPLIES = GEQ,
-
/// This option means that there are <em>"less or equal"</em>
- /// supply/demand constraints in the definition, i.e. the exact
- /// formulation of the problem is the following.
- /**
- \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
- \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq
- sup(u) \quad \forall u\in V \f]
- \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
- */
- /// It means that the total demand must be less or equal to the
- /// total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
- /// positive) and all the demands have to be satisfied, but there
- /// could be supplies that are not carried out from the supply
- /// nodes.
- LEQ,
- /// It is just an alias for the \c LEQ option.
- SATISFY_DEMANDS = LEQ
+ /// supply/demand constraints in the definition of the problem.
+ LEQ
};
/// \brief Constants for selecting the pivot rule.
@@ -215,6 +181,8 @@
const GR &_graph;
int _node_num;
int _arc_num;
+ int _all_arc_num;
+ int _search_arc_num;
// Parameters of the problem
bool _have_lower;
@@ -277,7 +245,7 @@
const IntVector &_state;
const CostVector &_pi;
int &_in_arc;
- int _arc_num;
+ int _search_arc_num;
// Pivot rule data
int _next_arc;
@@ -288,13 +256,14 @@
FirstEligiblePivotRule(NetworkSimplex &ns) :
_source(ns._source), _target(ns._target),
_cost(ns._cost), _state(ns._state), _pi(ns._pi),
- _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0)
+ _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),
+ _next_arc(0)
{}
// Find next entering arc
bool findEnteringArc() {
Cost c;
- for (int e = _next_arc; e < _arc_num; ++e) {
+ for (int e = _next_arc; e < _search_arc_num; ++e) {
c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
if (c < 0) {
_in_arc = e;
@@ -328,7 +297,7 @@
const IntVector &_state;
const CostVector &_pi;
int &_in_arc;
- int _arc_num;
+ int _search_arc_num;
public:
@@ -336,13 +305,13 @@
BestEligiblePivotRule(NetworkSimplex &ns) :
_source(ns._source), _target(ns._target),
_cost(ns._cost), _state(ns._state), _pi(ns._pi),
- _in_arc(ns.in_arc), _arc_num(ns._arc_num)
+ _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num)
{}
// Find next entering arc
bool findEnteringArc() {
Cost c, min = 0;
- for (int e = 0; e < _arc_num; ++e) {
+ for (int e = 0; e < _search_arc_num; ++e) {
c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
if (c < min) {
min = c;
@@ -367,7 +336,7 @@
const IntVector &_state;
const CostVector &_pi;
int &_in_arc;
- int _arc_num;
+ int _search_arc_num;
// Pivot rule data
int _block_size;
@@ -379,14 +348,15 @@
BlockSearchPivotRule(NetworkSimplex &ns) :
_source(ns._source), _target(ns._target),
_cost(ns._cost), _state(ns._state), _pi(ns._pi),
- _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0)
+ _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),
+ _next_arc(0)
{
// The main parameters of the pivot rule
- const double BLOCK_SIZE_FACTOR = 2.0;
+ const double BLOCK_SIZE_FACTOR = 0.5;
const int MIN_BLOCK_SIZE = 10;
_block_size = std::max( int(BLOCK_SIZE_FACTOR *
- std::sqrt(double(_arc_num))),
+ std::sqrt(double(_search_arc_num))),
MIN_BLOCK_SIZE );
}
@@ -395,7 +365,7 @@
Cost c, min = 0;
int cnt = _block_size;
int e, min_arc = _next_arc;
- for (e = _next_arc; e < _arc_num; ++e) {
+ for (e = _next_arc; e < _search_arc_num; ++e) {
c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
if (c < min) {
min = c;
@@ -440,7 +410,7 @@
const IntVector &_state;
const CostVector &_pi;
int &_in_arc;
- int _arc_num;
+ int _search_arc_num;
// Pivot rule data
IntVector _candidates;
@@ -454,7 +424,8 @@
CandidateListPivotRule(NetworkSimplex &ns) :
_source(ns._source), _target(ns._target),
_cost(ns._cost), _state(ns._state), _pi(ns._pi),
- _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0)
+ _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),
+ _next_arc(0)
{
// The main parameters of the pivot rule
const double LIST_LENGTH_FACTOR = 1.0;
@@ -463,7 +434,7 @@
const int MIN_MINOR_LIMIT = 3;
_list_length = std::max( int(LIST_LENGTH_FACTOR *
- std::sqrt(double(_arc_num))),
+ std::sqrt(double(_search_arc_num))),
MIN_LIST_LENGTH );
_minor_limit = std::max( int(MINOR_LIMIT_FACTOR * _list_length),
MIN_MINOR_LIMIT );
@@ -500,7 +471,7 @@
// Major iteration: build a new candidate list
min = 0;
_curr_length = 0;
- for (e = _next_arc; e < _arc_num; ++e) {
+ for (e = _next_arc; e < _search_arc_num; ++e) {
c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
if (c < 0) {
_candidates[_curr_length++] = e;
@@ -546,7 +517,7 @@
const IntVector &_state;
const CostVector &_pi;
int &_in_arc;
- int _arc_num;
+ int _search_arc_num;
// Pivot rule data
int _block_size, _head_length, _curr_length;
@@ -574,8 +545,8 @@
AlteringListPivotRule(NetworkSimplex &ns) :
_source(ns._source), _target(ns._target),
_cost(ns._cost), _state(ns._state), _pi(ns._pi),
- _in_arc(ns.in_arc), _arc_num(ns._arc_num),
- _next_arc(0), _cand_cost(ns._arc_num), _sort_func(_cand_cost)
+ _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),
+ _next_arc(0), _cand_cost(ns._search_arc_num), _sort_func(_cand_cost)
{
// The main parameters of the pivot rule
const double BLOCK_SIZE_FACTOR = 1.5;
@@ -584,7 +555,7 @@
const int MIN_HEAD_LENGTH = 3;
_block_size = std::max( int(BLOCK_SIZE_FACTOR *
- std::sqrt(double(_arc_num))),
+ std::sqrt(double(_search_arc_num))),
MIN_BLOCK_SIZE );
_head_length = std::max( int(HEAD_LENGTH_FACTOR * _block_size),
MIN_HEAD_LENGTH );
@@ -610,7 +581,7 @@
int last_arc = 0;
int limit = _head_length;
- for (int e = _next_arc; e < _arc_num; ++e) {
+ for (int e = _next_arc; e < _search_arc_num; ++e) {
_cand_cost[e] = _state[e] *
(_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
if (_cand_cost[e] < 0) {
@@ -678,17 +649,17 @@
_node_num = countNodes(_graph);
_arc_num = countArcs(_graph);
int all_node_num = _node_num + 1;
- int all_arc_num = _arc_num + _node_num;
+ int max_arc_num = _arc_num + 2 * _node_num;
- _source.resize(all_arc_num);
- _target.resize(all_arc_num);
+ _source.resize(max_arc_num);
+ _target.resize(max_arc_num);
- _lower.resize(all_arc_num);
- _upper.resize(all_arc_num);
- _cap.resize(all_arc_num);
- _cost.resize(all_arc_num);
+ _lower.resize(_arc_num);
+ _upper.resize(_arc_num);
+ _cap.resize(max_arc_num);
+ _cost.resize(max_arc_num);
_supply.resize(all_node_num);
- _flow.resize(all_arc_num);
+ _flow.resize(max_arc_num);
_pi.resize(all_node_num);
_parent.resize(all_node_num);
@@ -698,7 +669,7 @@
_rev_thread.resize(all_node_num);
_succ_num.resize(all_node_num);
_last_succ.resize(all_node_num);
- _state.resize(all_arc_num);
+ _state.resize(max_arc_num);
// Copy the graph (store the arcs in a mixed order)
int i = 0;
@@ -1069,7 +1040,7 @@
// Initialize artifical cost
Cost ART_COST;
if (std::numeric_limits<Cost>::is_exact) {
- ART_COST = std::numeric_limits<Cost>::max() / 4 + 1;
+ ART_COST = std::numeric_limits<Cost>::max() / 2 + 1;
} else {
ART_COST = std::numeric_limits<Cost>::min();
for (int i = 0; i != _arc_num; ++i) {
@@ -1093,29 +1064,121 @@
_succ_num[_root] = _node_num + 1;
_last_succ[_root] = _root - 1;
_supply[_root] = -_sum_supply;
- _pi[_root] = _sum_supply < 0 ? -ART_COST : ART_COST;
+ _pi[_root] = 0;
// Add artificial arcs and initialize the spanning tree data structure
- for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
- _parent[u] = _root;
- _pred[u] = e;
- _thread[u] = u + 1;
- _rev_thread[u + 1] = u;
- _succ_num[u] = 1;
- _last_succ[u] = u;
- _cost[e] = ART_COST;
- _cap[e] = INF;
- _state[e] = STATE_TREE;
- if (_supply[u] > 0 || (_supply[u] == 0 && _sum_supply <= 0)) {
- _flow[e] = _supply[u];
- _forward[u] = true;
- _pi[u] = -ART_COST + _pi[_root];
- } else {
- _flow[e] = -_supply[u];
- _forward[u] = false;
- _pi[u] = ART_COST + _pi[_root];
+ if (_sum_supply == 0) {
+ // EQ supply constraints
+ _search_arc_num = _arc_num;
+ _all_arc_num = _arc_num + _node_num;
+ for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
+ _parent[u] = _root;
+ _pred[u] = e;
+ _thread[u] = u + 1;
+ _rev_thread[u + 1] = u;
+ _succ_num[u] = 1;
+ _last_succ[u] = u;
+ _cap[e] = INF;
+ _state[e] = STATE_TREE;
+ if (_supply[u] >= 0) {
+ _forward[u] = true;
+ _pi[u] = 0;
+ _source[e] = u;
+ _target[e] = _root;
+ _flow[e] = _supply[u];
+ _cost[e] = 0;
+ } else {
+ _forward[u] = false;
+ _pi[u] = ART_COST;
+ _source[e] = _root;
+ _target[e] = u;
+ _flow[e] = -_supply[u];
+ _cost[e] = ART_COST;
+ }
}
}
+ else if (_sum_supply > 0) {
+ // LEQ supply constraints
+ _search_arc_num = _arc_num + _node_num;
+ int f = _arc_num + _node_num;
+ for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
+ _parent[u] = _root;
+ _thread[u] = u + 1;
+ _rev_thread[u + 1] = u;
+ _succ_num[u] = 1;
+ _last_succ[u] = u;
+ if (_supply[u] >= 0) {
+ _forward[u] = true;
+ _pi[u] = 0;
+ _pred[u] = e;
+ _source[e] = u;
+ _target[e] = _root;
+ _cap[e] = INF;
+ _flow[e] = _supply[u];
+ _cost[e] = 0;
+ _state[e] = STATE_TREE;
+ } else {
+ _forward[u] = false;
+ _pi[u] = ART_COST;
+ _pred[u] = f;
+ _source[f] = _root;
+ _target[f] = u;
+ _cap[f] = INF;
+ _flow[f] = -_supply[u];
+ _cost[f] = ART_COST;
+ _state[f] = STATE_TREE;
+ _source[e] = u;
+ _target[e] = _root;
+ _cap[e] = INF;
+ _flow[e] = 0;
+ _cost[e] = 0;
+ _state[e] = STATE_LOWER;
+ ++f;
+ }
+ }
+ _all_arc_num = f;
+ }
+ else {
+ // GEQ supply constraints
+ _search_arc_num = _arc_num + _node_num;
+ int f = _arc_num + _node_num;
+ for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
+ _parent[u] = _root;
+ _thread[u] = u + 1;
+ _rev_thread[u + 1] = u;
+ _succ_num[u] = 1;
+ _last_succ[u] = u;
+ if (_supply[u] <= 0) {
+ _forward[u] = false;
+ _pi[u] = 0;
+ _pred[u] = e;
+ _source[e] = _root;
+ _target[e] = u;
+ _cap[e] = INF;
+ _flow[e] = -_supply[u];
+ _cost[e] = 0;
+ _state[e] = STATE_TREE;
+ } else {
+ _forward[u] = true;
+ _pi[u] = -ART_COST;
+ _pred[u] = f;
+ _source[f] = u;
+ _target[f] = _root;
+ _cap[f] = INF;
+ _flow[f] = _supply[u];
+ _state[f] = STATE_TREE;
+ _cost[f] = ART_COST;
+ _source[e] = _root;
+ _target[e] = u;
+ _cap[e] = INF;
+ _flow[e] = 0;
+ _cost[e] = 0;
+ _state[e] = STATE_LOWER;
+ ++f;
+ }
+ }
+ _all_arc_num = f;
+ }
return true;
}
@@ -1374,20 +1437,8 @@
}
// Check feasibility
- if (_sum_supply < 0) {
- for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
- if (_supply[u] >= 0 && _flow[e] != 0) return INFEASIBLE;
- }
- }
- else if (_sum_supply > 0) {
- for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
- if (_supply[u] <= 0 && _flow[e] != 0) return INFEASIBLE;
- }
- }
- else {
- for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
- if (_flow[e] != 0) return INFEASIBLE;
- }
+ for (int e = _search_arc_num; e != _all_arc_num; ++e) {
+ if (_flow[e] != 0) return INFEASIBLE;
}
// Transform the solution and the supply map to the original form
@@ -1401,6 +1452,30 @@
}
}
}
+
+ // Shift potentials to meet the requirements of the GEQ/LEQ type
+ // optimality conditions
+ if (_sum_supply == 0) {
+ if (_stype == GEQ) {
+ Cost max_pot = std::numeric_limits<Cost>::min();
+ for (int i = 0; i != _node_num; ++i) {
+ if (_pi[i] > max_pot) max_pot = _pi[i];
+ }
+ if (max_pot > 0) {
+ for (int i = 0; i != _node_num; ++i)
+ _pi[i] -= max_pot;
+ }
+ } else {
+ Cost min_pot = std::numeric_limits<Cost>::max();
+ for (int i = 0; i != _node_num; ++i) {
+ if (_pi[i] < min_pot) min_pot = _pi[i];
+ }
+ if (min_pot < 0) {
+ for (int i = 0; i != _node_num; ++i)
+ _pi[i] -= min_pot;
+ }
+ }
+ }
return OPTIMAL;
}
diff -r 189760a7cdd0 -r c01a98ce01fd scripts/unify-sources.sh
--- a/scripts/unify-sources.sh Thu May 07 02:05:12 2009 +0200
+++ b/scripts/unify-sources.sh Tue May 12 12:09:55 2009 +0100
@@ -6,6 +6,10 @@
function hg_year() {
if [ -n "$(hg st $1)" ]; then
echo $YEAR
+ else
+ hg log -l 1 --template='{date|isodate}\n' $1 |
+ cut -d '-' -f 1
+ fi
}
# file enumaration modes
diff -r 189760a7cdd0 -r c01a98ce01fd test/CMakeLists.txt
--- a/test/CMakeLists.txt Thu May 07 02:05:12 2009 +0200
+++ b/test/CMakeLists.txt Tue May 12 12:09:55 2009 +0100
@@ -9,6 +9,7 @@
adaptors_test
bfs_test
circulation_test
+ connectivity_test
counter_test
dfs_test
digraph_test
diff -r 189760a7cdd0 -r c01a98ce01fd test/Makefile.am
--- a/test/Makefile.am Thu May 07 02:05:12 2009 +0200
+++ b/test/Makefile.am Tue May 12 12:09:55 2009 +0100
@@ -9,6 +9,7 @@
test/adaptors_test \
test/bfs_test \
test/circulation_test \
+ test/connectivity_test \
test/counter_test \
test/dfs_test \
test/digraph_test \
@@ -54,6 +55,7 @@
test_bfs_test_SOURCES = test/bfs_test.cc
test_circulation_test_SOURCES = test/circulation_test.cc
test_counter_test_SOURCES = test/counter_test.cc
+test_connectivity_test_SOURCES = test/connectivity_test.cc
test_dfs_test_SOURCES = test/dfs_test.cc
test_digraph_test_SOURCES = test/digraph_test.cc
test_dijkstra_test_SOURCES = test/dijkstra_test.cc
diff -r 189760a7cdd0 -r c01a98ce01fd test/connectivity_test.cc
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/test/connectivity_test.cc Tue May 12 12:09:55 2009 +0100
@@ -0,0 +1,297 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2009
+ * 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.
+ *
+ */
+
+#include <lemon/connectivity.h>
+#include <lemon/list_graph.h>
+#include <lemon/adaptors.h>
+
+#include "test_tools.h"
+
+using namespace lemon;
+
+
+int main()
+{
+ typedef ListDigraph Digraph;
+ typedef Undirector<Digraph> Graph;
+
+ {
+ Digraph d;
+ Digraph::NodeMap<int> order(d);
+ Graph g(d);
+
+ check(stronglyConnected(d), "The empty digraph is strongly connected");
+ check(countStronglyConnectedComponents(d) == 0,
+ "The empty digraph has 0 strongly connected component");
+ check(connected(g), "The empty graph is connected");
+ check(countConnectedComponents(g) == 0,
+ "The empty graph has 0 connected component");
+
+ check(biNodeConnected(g), "The empty graph is bi-node-connected");
+ check(countBiNodeConnectedComponents(g) == 0,
+ "The empty graph has 0 bi-node-connected component");
+ check(biEdgeConnected(g), "The empty graph is bi-edge-connected");
+ check(countBiEdgeConnectedComponents(g) == 0,
+ "The empty graph has 0 bi-edge-connected component");
+
+ check(dag(d), "The empty digraph is DAG.");
+ check(checkedTopologicalSort(d, order), "The empty digraph is DAG.");
+ check(loopFree(d), "The empty digraph is loop-free.");
+ check(parallelFree(d), "The empty digraph is parallel-free.");
+ check(simpleGraph(d), "The empty digraph is simple.");
+
+ check(acyclic(g), "The empty graph is acyclic.");
+ check(tree(g), "The empty graph is tree.");
+ check(bipartite(g), "The empty graph is bipartite.");
+ check(loopFree(g), "The empty graph is loop-free.");
+ check(parallelFree(g), "The empty graph is parallel-free.");
+ check(simpleGraph(g), "The empty graph is simple.");
+ }
+
+ {
+ Digraph d;
+ Digraph::NodeMap<int> order(d);
+ Graph g(d);
+ Digraph::Node n = d.addNode();
+
+ check(stronglyConnected(d), "This digraph is strongly connected");
+ check(countStronglyConnectedComponents(d) == 1,
+ "This digraph has 1 strongly connected component");
+ check(connected(g), "This graph is connected");
+ check(countConnectedComponents(g) == 1,
+ "This graph has 1 connected component");
+
+ check(biNodeConnected(g), "This graph is bi-node-connected");
+ check(countBiNodeConnectedComponents(g) == 0,
+ "This graph has 0 bi-node-connected component");
+ check(biEdgeConnected(g), "This graph is bi-edge-connected");
+ check(countBiEdgeConnectedComponents(g) == 1,
+ "This graph has 1 bi-edge-connected component");
+
+ check(dag(d), "This digraph is DAG.");
+ check(checkedTopologicalSort(d, order), "This digraph is DAG.");
+ check(loopFree(d), "This digraph is loop-free.");
+ check(parallelFree(d), "This digraph is parallel-free.");
+ check(simpleGraph(d), "This digraph is simple.");
+
+ check(acyclic(g), "This graph is acyclic.");
+ check(tree(g), "This graph is tree.");
+ check(bipartite(g), "This graph is bipartite.");
+ check(loopFree(g), "This graph is loop-free.");
+ check(parallelFree(g), "This graph is parallel-free.");
+ check(simpleGraph(g), "This graph is simple.");
+ }
+
+ {
+ Digraph d;
+ Digraph::NodeMap<int> order(d);
+ Graph g(d);
+
+ Digraph::Node n1 = d.addNode();
+ Digraph::Node n2 = d.addNode();
+ Digraph::Node n3 = d.addNode();
+ Digraph::Node n4 = d.addNode();
+ Digraph::Node n5 = d.addNode();
+ Digraph::Node n6 = d.addNode();
+
+ d.addArc(n1, n3);
+ d.addArc(n3, n2);
+ d.addArc(n2, n1);
+ d.addArc(n4, n2);
+ d.addArc(n4, n3);
+ d.addArc(n5, n6);
+ d.addArc(n6, n5);
+
+ check(!stronglyConnected(d), "This digraph is not strongly connected");
+ check(countStronglyConnectedComponents(d) == 3,
+ "This digraph has 3 strongly connected components");
+ check(!connected(g), "This graph is not connected");
+ check(countConnectedComponents(g) == 2,
+ "This graph has 2 connected components");
+
+ check(!dag(d), "This digraph is not DAG.");
+ check(!checkedTopologicalSort(d, order), "This digraph is not DAG.");
+ check(loopFree(d), "This digraph is loop-free.");
+ check(parallelFree(d), "This digraph is parallel-free.");
+ check(simpleGraph(d), "This digraph is simple.");
+
+ check(!acyclic(g), "This graph is not acyclic.");
+ check(!tree(g), "This graph is not tree.");
+ check(!bipartite(g), "This graph is not bipartite.");
+ check(loopFree(g), "This graph is loop-free.");
+ check(!parallelFree(g), "This graph is not parallel-free.");
+ check(!simpleGraph(g), "This graph is not simple.");
+
+ d.addArc(n3, n3);
+
+ check(!loopFree(d), "This digraph is not loop-free.");
+ check(!loopFree(g), "This graph is not loop-free.");
+ check(!simpleGraph(d), "This digraph is not simple.");
+
+ d.addArc(n3, n2);
+
+ check(!parallelFree(d), "This digraph is not parallel-free.");
+ }
+
+ {
+ Digraph d;
+ Digraph::ArcMap<bool> cutarcs(d, false);
+ Graph g(d);
+
+ Digraph::Node n1 = d.addNode();
+ Digraph::Node n2 = d.addNode();
+ Digraph::Node n3 = d.addNode();
+ Digraph::Node n4 = d.addNode();
+ Digraph::Node n5 = d.addNode();
+ Digraph::Node n6 = d.addNode();
+ Digraph::Node n7 = d.addNode();
+ Digraph::Node n8 = d.addNode();
+
+ d.addArc(n1, n2);
+ d.addArc(n5, n1);
+ d.addArc(n2, n8);
+ d.addArc(n8, n5);
+ d.addArc(n6, n4);
+ d.addArc(n4, n6);
+ d.addArc(n2, n5);
+ d.addArc(n1, n8);
+ d.addArc(n6, n7);
+ d.addArc(n7, n6);
+
+ check(!stronglyConnected(d), "This digraph is not strongly connected");
+ check(countStronglyConnectedComponents(d) == 3,
+ "This digraph has 3 strongly connected components");
+ Digraph::NodeMap<int> scomp1(d);
+ check(stronglyConnectedComponents(d, scomp1) == 3,
+ "This digraph has 3 strongly connected components");
+ check(scomp1[n1] != scomp1[n3] && scomp1[n1] != scomp1[n4] &&
+ scomp1[n3] != scomp1[n4], "Wrong stronglyConnectedComponents()");
+ check(scomp1[n1] == scomp1[n2] && scomp1[n1] == scomp1[n5] &&
+ scomp1[n1] == scomp1[n8], "Wrong stronglyConnectedComponents()");
+ check(scomp1[n4] == scomp1[n6] && scomp1[n4] == scomp1[n7],
+ "Wrong stronglyConnectedComponents()");
+ Digraph::ArcMap<bool> scut1(d, false);
+ check(stronglyConnectedCutArcs(d, scut1) == 0,
+ "This digraph has 0 strongly connected cut arc.");
+ for (Digraph::ArcIt a(d); a != INVALID; ++a) {
+ check(!scut1[a], "Wrong stronglyConnectedCutArcs()");
+ }
+
+ check(!connected(g), "This graph is not connected");
+ check(countConnectedComponents(g) == 3,
+ "This graph has 3 connected components");
+ Graph::NodeMap<int> comp(g);
+ check(connectedComponents(g, comp) == 3,
+ "This graph has 3 connected components");
+ check(comp[n1] != comp[n3] && comp[n1] != comp[n4] &&
+ comp[n3] != comp[n4], "Wrong connectedComponents()");
+ check(comp[n1] == comp[n2] && comp[n1] == comp[n5] &&
+ comp[n1] == comp[n8], "Wrong connectedComponents()");
+ check(comp[n4] == comp[n6] && comp[n4] == comp[n7],
+ "Wrong connectedComponents()");
+
+ cutarcs[d.addArc(n3, n1)] = true;
+ cutarcs[d.addArc(n3, n5)] = true;
+ cutarcs[d.addArc(n3, n8)] = true;
+ cutarcs[d.addArc(n8, n6)] = true;
+ cutarcs[d.addArc(n8, n7)] = true;
+
+ check(!stronglyConnected(d), "This digraph is not strongly connected");
+ check(countStronglyConnectedComponents(d) == 3,
+ "This digraph has 3 strongly connected components");
+ Digraph::NodeMap<int> scomp2(d);
+ check(stronglyConnectedComponents(d, scomp2) == 3,
+ "This digraph has 3 strongly connected components");
+ check(scomp2[n3] == 0, "Wrong stronglyConnectedComponents()");
+ check(scomp2[n1] == 1 && scomp2[n2] == 1 && scomp2[n5] == 1 &&
+ scomp2[n8] == 1, "Wrong stronglyConnectedComponents()");
+ check(scomp2[n4] == 2 && scomp2[n6] == 2 && scomp2[n7] == 2,
+ "Wrong stronglyConnectedComponents()");
+ Digraph::ArcMap<bool> scut2(d, false);
+ check(stronglyConnectedCutArcs(d, scut2) == 5,
+ "This digraph has 5 strongly connected cut arcs.");
+ for (Digraph::ArcIt a(d); a != INVALID; ++a) {
+ check(scut2[a] == cutarcs[a], "Wrong stronglyConnectedCutArcs()");
+ }
+ }
+
+ {
+ // DAG example for topological sort from the book New Algorithms
+ // (T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein)
+ Digraph d;
+ Digraph::NodeMap<int> order(d);
+
+ Digraph::Node belt = d.addNode();
+ Digraph::Node trousers = d.addNode();
+ Digraph::Node necktie = d.addNode();
+ Digraph::Node coat = d.addNode();
+ Digraph::Node socks = d.addNode();
+ Digraph::Node shirt = d.addNode();
+ Digraph::Node shoe = d.addNode();
+ Digraph::Node watch = d.addNode();
+ Digraph::Node pants = d.addNode();
+
+ d.addArc(socks, shoe);
+ d.addArc(pants, shoe);
+ d.addArc(pants, trousers);
+ d.addArc(trousers, shoe);
+ d.addArc(trousers, belt);
+ d.addArc(belt, coat);
+ d.addArc(shirt, belt);
+ d.addArc(shirt, necktie);
+ d.addArc(necktie, coat);
+
+ check(dag(d), "This digraph is DAG.");
+ topologicalSort(d, order);
+ for (Digraph::ArcIt a(d); a != INVALID; ++a) {
+ check(order[d.source(a)] < order[d.target(a)],
+ "Wrong topologicalSort()");
+ }
+ }
+
+ {
+ ListGraph g;
+ ListGraph::NodeMap<bool> map(g);
+
+ ListGraph::Node n1 = g.addNode();
+ ListGraph::Node n2 = g.addNode();
+ ListGraph::Node n3 = g.addNode();
+ ListGraph::Node n4 = g.addNode();
+ ListGraph::Node n5 = g.addNode();
+ ListGraph::Node n6 = g.addNode();
+ ListGraph::Node n7 = g.addNode();
+
+ g.addEdge(n1, n3);
+ g.addEdge(n1, n4);
+ g.addEdge(n2, n5);
+ g.addEdge(n3, n6);
+ g.addEdge(n4, n6);
+ g.addEdge(n4, n7);
+ g.addEdge(n5, n7);
+
+ check(bipartite(g), "This graph is bipartite");
+ check(bipartitePartitions(g, map), "This graph is bipartite");
+
+ check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7],
+ "Wrong bipartitePartitions()");
+ check(map[n3] == map[n4] && map[n3] == map[n5],
+ "Wrong bipartitePartitions()");
+ }
+
+ return 0;
+}
diff -r 189760a7cdd0 -r c01a98ce01fd test/min_cost_flow_test.cc
--- a/test/min_cost_flow_test.cc Thu May 07 02:05:12 2009 +0200
+++ b/test/min_cost_flow_test.cc Tue May 12 12:09:55 2009 +0100
@@ -174,7 +174,7 @@
typename CM, typename SM, typename FM, typename PM >
bool checkPotential( const GR& gr, const LM& lower, const UM& upper,
const CM& cost, const SM& supply, const FM& flow,
- const PM& pi )
+ const PM& pi, SupplyType type )
{
TEMPLATE_DIGRAPH_TYPEDEFS(GR);
@@ -193,12 +193,50 @@
sum += flow[e];
for (InArcIt e(gr, n); e != INVALID; ++e)
sum -= flow[e];
- opt = (sum == supply[n]) || (pi[n] == 0);
+ if (type != LEQ) {
+ opt = (pi[n] <= 0) && (sum == supply[n] || pi[n] == 0);
+ } else {
+ opt = (pi[n] >= 0) && (sum == supply[n] || pi[n] == 0);
+ }
}
return opt;
}
+// Check whether the dual cost is equal to the primal cost
+template < typename GR, typename LM, typename UM,
+ typename CM, typename SM, typename PM >
+bool checkDualCost( const GR& gr, const LM& lower, const UM& upper,
+ const CM& cost, const SM& supply, const PM& pi,
+ typename CM::Value total )
+{
+ TEMPLATE_DIGRAPH_TYPEDEFS(GR);
+
+ typename CM::Value dual_cost = 0;
+ SM red_supply(gr);
+ for (NodeIt n(gr); n != INVALID; ++n) {
+ red_supply[n] = supply[n];
+ }
+ for (ArcIt a(gr); a != INVALID; ++a) {
+ if (lower[a] != 0) {
+ dual_cost += lower[a] * cost[a];
+ red_supply[gr.source(a)] -= lower[a];
+ red_supply[gr.target(a)] += lower[a];
+ }
+ }
+
+ for (NodeIt n(gr); n != INVALID; ++n) {
+ dual_cost -= red_supply[n] * pi[n];
+ }
+ for (ArcIt a(gr); a != INVALID; ++a) {
+ typename CM::Value red_cost =
+ cost[a] + pi[gr.source(a)] - pi[gr.target(a)];
+ dual_cost -= (upper[a] - lower[a]) * std::max(-red_cost, 0);
+ }
+
+ return dual_cost == total;
+}
+
// Run a minimum cost flow algorithm and check the results
template < typename MCF, typename GR,
typename LM, typename UM,
@@ -220,8 +258,10 @@
check(checkFlow(gr, lower, upper, supply, flow, type),
"The flow is not feasible " + test_id);
check(mcf.totalCost() == total, "The flow is not optimal " + test_id);
- check(checkPotential(gr, lower, upper, cost, supply, flow, pi),
+ check(checkPotential(gr, lower, upper, cost, supply, flow, pi, type),
"Wrong potentials " + test_id);
+ check(checkDualCost(gr, lower, upper, cost, supply, pi, total),
+ "Wrong dual cost " + test_id);
}
}
@@ -266,45 +306,56 @@
.node("target", w)
.run();
- // Build a test digraph for testing negative costs
- Digraph ngr;
- Node n1 = ngr.addNode();
- Node n2 = ngr.addNode();
- Node n3 = ngr.addNode();
- Node n4 = ngr.addNode();
- Node n5 = ngr.addNode();
- Node n6 = ngr.addNode();
- Node n7 = ngr.addNode();
+ // Build test digraphs with negative costs
+ Digraph neg_gr;
+ Node n1 = neg_gr.addNode();
+ Node n2 = neg_gr.addNode();
+ Node n3 = neg_gr.addNode();
+ Node n4 = neg_gr.addNode();
+ Node n5 = neg_gr.addNode();
+ Node n6 = neg_gr.addNode();
+ Node n7 = neg_gr.addNode();
- Arc a1 = ngr.addArc(n1, n2);
- Arc a2 = ngr.addArc(n1, n3);
- Arc a3 = ngr.addArc(n2, n4);
- Arc a4 = ngr.addArc(n3, n4);
- Arc a5 = ngr.addArc(n3, n2);
- Arc a6 = ngr.addArc(n5, n3);
- Arc a7 = ngr.addArc(n5, n6);
- Arc a8 = ngr.addArc(n6, n7);
- Arc a9 = ngr.addArc(n7, n5);
+ Arc a1 = neg_gr.addArc(n1, n2);
+ Arc a2 = neg_gr.addArc(n1, n3);
+ Arc a3 = neg_gr.addArc(n2, n4);
+ Arc a4 = neg_gr.addArc(n3, n4);
+ Arc a5 = neg_gr.addArc(n3, n2);
+ Arc a6 = neg_gr.addArc(n5, n3);
+ Arc a7 = neg_gr.addArc(n5, n6);
+ Arc a8 = neg_gr.addArc(n6, n7);
+ Arc a9 = neg_gr.addArc(n7, n5);
- Digraph::ArcMap<int> nc(ngr), nl1(ngr, 0), nl2(ngr, 0);
- ConstMap<Arc, int> nu1(std::numeric_limits<int>::max()), nu2(5000);
- Digraph::NodeMap<int> ns(ngr, 0);
+ Digraph::ArcMap<int> neg_c(neg_gr), neg_l1(neg_gr, 0), neg_l2(neg_gr, 0);
+ ConstMap<Arc, int> neg_u1(std::numeric_limits<int>::max()), neg_u2(5000);
+ Digraph::NodeMap<int> neg_s(neg_gr, 0);
- nl2[a7] = 1000;
- nl2[a8] = -1000;
+ neg_l2[a7] = 1000;
+ neg_l2[a8] = -1000;
- ns[n1] = 100;
- ns[n4] = -100;
+ neg_s[n1] = 100;
+ neg_s[n4] = -100;
- nc[a1] = 100;
- nc[a2] = 30;
- nc[a3] = 20;
- nc[a4] = 80;
- nc[a5] = 50;
- nc[a6] = 10;
- nc[a7] = 80;
- nc[a8] = 30;
- nc[a9] = -120;
+ neg_c[a1] = 100;
+ neg_c[a2] = 30;
+ neg_c[a3] = 20;
+ neg_c[a4] = 80;
+ neg_c[a5] = 50;
+ neg_c[a6] = 10;
+ neg_c[a7] = 80;
+ neg_c[a8] = 30;
+ neg_c[a9] = -120;
+
+ Digraph negs_gr;
+ Digraph::NodeMap<int> negs_s(negs_gr);
+ Digraph::ArcMap<int> negs_c(negs_gr);
+ ConstMap<Arc, int> negs_l(0), negs_u(1000);
+ n1 = negs_gr.addNode();
+ n2 = negs_gr.addNode();
+ negs_s[n1] = 100;
+ negs_s[n2] = -300;
+ negs_c[negs_gr.addArc(n1, n2)] = -1;
+
// A. Test NetworkSimplex with the default pivot rule
{
@@ -342,7 +393,7 @@
mcf.supplyType(mcf.GEQ);
checkMcf(mcf, mcf.lowerMap(l2).run(),
gr, l2, u, c, s5, mcf.OPTIMAL, true, 4540, "#A11", GEQ);
- mcf.supplyType(mcf.CARRY_SUPPLIES).supplyMap(s6);
+ mcf.supplyMap(s6);
checkMcf(mcf, mcf.run(),
gr, l2, u, c, s6, mcf.INFEASIBLE, false, 0, "#A12", GEQ);
@@ -353,20 +404,26 @@
gr, l1, u, c, s6, mcf.OPTIMAL, true, 5080, "#A13", LEQ);
checkMcf(mcf, mcf.lowerMap(l2).run(),
gr, l2, u, c, s6, mcf.OPTIMAL, true, 5930, "#A14", LEQ);
- mcf.supplyType(mcf.SATISFY_DEMANDS).supplyMap(s5);
+ mcf.supplyMap(s5);
checkMcf(mcf, mcf.run(),
gr, l2, u, c, s5, mcf.INFEASIBLE, false, 0, "#A15", LEQ);
// Check negative costs
- NetworkSimplex<Digraph> nmcf(ngr);
- nmcf.lowerMap(nl1).costMap(nc).supplyMap(ns);
- checkMcf(nmcf, nmcf.run(),
- ngr, nl1, nu1, nc, ns, nmcf.UNBOUNDED, false, 0, "#A16");
- checkMcf(nmcf, nmcf.upperMap(nu2).run(),
- ngr, nl1, nu2, nc, ns, nmcf.OPTIMAL, true, -40000, "#A17");
- nmcf.reset().lowerMap(nl2).costMap(nc).supplyMap(ns);
- checkMcf(nmcf, nmcf.run(),
- ngr, nl2, nu1, nc, ns, nmcf.UNBOUNDED, false, 0, "#A18");
+ NetworkSimplex<Digraph> neg_mcf(neg_gr);
+ neg_mcf.lowerMap(neg_l1).costMap(neg_c).supplyMap(neg_s);
+ checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u1,
+ neg_c, neg_s, neg_mcf.UNBOUNDED, false, 0, "#A16");
+ neg_mcf.upperMap(neg_u2);
+ checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u2,
+ neg_c, neg_s, neg_mcf.OPTIMAL, true, -40000, "#A17");
+ neg_mcf.reset().lowerMap(neg_l2).costMap(neg_c).supplyMap(neg_s);
+ checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l2, neg_u1,
+ neg_c, neg_s, neg_mcf.UNBOUNDED, false, 0, "#A18");
+
+ NetworkSimplex<Digraph> negs_mcf(negs_gr);
+ negs_mcf.costMap(negs_c).supplyMap(negs_s);
+ checkMcf(negs_mcf, negs_mcf.run(), negs_gr, negs_l, negs_u,
+ negs_c, negs_s, negs_mcf.OPTIMAL, true, -300, "#A19", GEQ);
}
// B. Test NetworkSimplex with each pivot rule
diff -r 189760a7cdd0 -r c01a98ce01fd tools/lgf-gen.cc
--- a/tools/lgf-gen.cc Thu May 07 02:05:12 2009 +0200
+++ b/tools/lgf-gen.cc Tue May 12 12:09:55 2009 +0100
@@ -18,7 +18,7 @@
/// \ingroup tools
/// \file
-/// \brief Special plane digraph generator.
+/// \brief Special plane graph generator.
///
/// Graph generator application for various types of plane graphs.
///
@@ -26,7 +26,7 @@
/// \code
/// lgf-gen --help
/// \endcode
-/// for more info on the usage.
+/// for more information on the usage.
#include <algorithm>
#include <set>
@@ -686,20 +686,21 @@
.intOption("g", "Girth parameter (default is 10)", 10)
.refOption("cities", "Number of cities (default is 1)", num_of_cities)
.refOption("area", "Full relative area of the cities (default is 1)", area)
- .refOption("disc", "Nodes are evenly distributed on a unit disc (default)",disc_d)
+ .refOption("disc", "Nodes are evenly distributed on a unit disc (default)",
+ disc_d)
.optionGroup("dist", "disc")
- .refOption("square", "Nodes are evenly distributed on a unit square", square_d)
+ .refOption("square", "Nodes are evenly distributed on a unit square",
+ square_d)
.optionGroup("dist", "square")
- .refOption("gauss",
- "Nodes are located according to a two-dim gauss distribution",
- gauss_d)
+ .refOption("gauss", "Nodes are located according to a two-dim Gauss "
+ "distribution", gauss_d)
.optionGroup("dist", "gauss")
-// .mandatoryGroup("dist")
.onlyOneGroup("dist")
- .boolOption("eps", "Also generate .eps output (prefix.eps)")
- .boolOption("nonodes", "Draw the edges only in the generated .eps")
- .boolOption("dir", "Directed digraph is generated (each arcs are replaced by two directed ones)")
- .boolOption("2con", "Create a two connected planar digraph")
+ .boolOption("eps", "Also generate .eps output (<prefix>.eps)")
+ .boolOption("nonodes", "Draw only the edges in the generated .eps output")
+ .boolOption("dir", "Directed graph is generated (each edge is replaced by "
+ "two directed arcs)")
+ .boolOption("2con", "Create a two connected planar graph")
.optionGroup("alg","2con")
.boolOption("tree", "Create a min. cost spanning tree")
.optionGroup("alg","tree")
@@ -707,7 +708,7 @@
.optionGroup("alg","tsp")
.boolOption("tsp2", "Create a TSP tour (tree based)")
.optionGroup("alg","tsp2")
- .boolOption("dela", "Delaunay triangulation digraph")
+ .boolOption("dela", "Delaunay triangulation graph")
.optionGroup("alg","dela")
.onlyOneGroup("alg")
.boolOption("rand", "Use time seed for random number generator")