1.1 --- a/CMakeLists.txt Thu May 07 02:05:12 2009 +0200
1.2 +++ b/CMakeLists.txt Tue May 12 12:09:55 2009 +0100
1.3 @@ -44,7 +44,7 @@
1.4 SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
1.5 SET(CPACK_PACKAGE_VENDOR "EGRES")
1.6 SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
1.7 - "LEMON - Library of Efficient Models and Optimization in Networks")
1.8 + "LEMON - Library for Efficient Modeling and Optimization in Networks")
1.9 SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")
1.10
1.11 SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
2.1 --- a/NEWS Thu May 07 02:05:12 2009 +0200
2.2 +++ b/NEWS Tue May 12 12:09:55 2009 +0100
2.3 @@ -1,3 +1,90 @@
2.4 +2009-05-13 Version 1.1 released
2.5 +
2.6 + This is the second stable release of the 1.x series. It
2.7 + features a better coverage of the tools available in the 0.x
2.8 + series, a thoroughly reworked LP/MIP interface plus various
2.9 + improvements in the existing tools.
2.10 +
2.11 + * Much improved M$ Windows support
2.12 + * Various improvements in the CMAKE build system
2.13 + * Compilation warnings are fixed/suppressed
2.14 + * Support IBM xlC compiler
2.15 + * New algorithms
2.16 + * Connectivity related algorithms (#61)
2.17 + * Euler walks (#65)
2.18 + * Preflow push-relabel max. flow algorithm (#176)
2.19 + * Circulation algorithm (push-relabel based) (#175)
2.20 + * Suurballe algorithm (#47)
2.21 + * Gomory-Hu algorithm (#66)
2.22 + * Hao-Orlin algorithm (#58)
2.23 + * Edmond's maximum cardinality and weighted matching algorithms
2.24 + in general graphs (#48,#265)
2.25 + * Minimum cost arborescence/branching (#60)
2.26 + * Network Simplex min. cost flow algorithm (#234)
2.27 + * New data structures
2.28 + * Full graph structure (#57)
2.29 + * Grid graph structure (#57)
2.30 + * Hypercube graph structure (#57)
2.31 + * Graph adaptors (#67)
2.32 + * ArcSet and EdgeSet classes (#67)
2.33 + * Elevator class (#174)
2.34 + * Other new tools
2.35 + * LP/MIP interface (#44)
2.36 + * Support for GLPK, CPLEX, Soplex, COIN-OR CLP and CBC
2.37 + * Reader for the Nauty file format (#55)
2.38 + * DIMACS readers (#167)
2.39 + * Radix sort algorithms (#72)
2.40 + * RangeIdMap and CrossRefMap (#160)
2.41 + * New command line tools
2.42 + * DIMACS to LGF converter (#182)
2.43 + * lgf-gen - a graph generator (#45)
2.44 + * DIMACS solver utility (#226)
2.45 + * Other code improvements
2.46 + * Lognormal distribution added to Random (#102)
2.47 + * Better (i.e. O(1) time) item counting in SmartGraph (#3)
2.48 + * The standard maps of graphs are guaranteed to be
2.49 + reference maps (#190)
2.50 + * Miscellaneous
2.51 + * Various doc improvements
2.52 + * Improved 0.x -> 1.x converter script
2.53 +
2.54 + * Several bugfixes (compared to release 1.0):
2.55 + #170: Bugfix SmartDigraph::split()
2.56 + #171: Bugfix in SmartGraph::restoreSnapshot()
2.57 + #172: Extended test cases for graphs and digraphs
2.58 + #173: Bugfix in Random
2.59 + * operator()s always return a double now
2.60 + * the faulty real<Num>(Num) and real<Num>(Num,Num)
2.61 + have been removed
2.62 + #187: Remove DijkstraWidestPathOperationTraits
2.63 + #61: Bugfix in DfsVisit
2.64 + #193: Bugfix in GraphReader::skipSection()
2.65 + #195: Bugfix in ConEdgeIt()
2.66 + #197: Bugfix in heap unionfind
2.67 + * This bug affects Edmond's general matching algorithms
2.68 + #207: Fix 'make install' without 'make html' using CMAKE
2.69 + #208: Suppress or fix VS2008 compilation warnings
2.70 + ----: Update the LEMON icon
2.71 + ----: Enable the component-based installer
2.72 + (in installers made by CPACK)
2.73 + ----: Set the proper version for CMAKE in the tarballs
2.74 + (made by autotools)
2.75 + ----: Minor clarification in the LICENSE file
2.76 + ----: Add missing unistd.h include to time_measure.h
2.77 + #204: Compilation bug fixed in graph_to_eps.h with VS2005
2.78 + #214,#215: windows.h should never be included by lemon headers
2.79 + #230: Build systems check the availability of 'long long' type
2.80 + #229: Default implementation of Tolerance<> is used for integer types
2.81 + #211,#212: Various fixes for compiling on AIX
2.82 + ----: Improvements in CMAKE config
2.83 + - docs is installed in share/doc/
2.84 + - detects newer versions of Ghostscript
2.85 + #239: Fix missing 'inline' specifier in time_measure.h
2.86 + #274,#280: Install lemon/config.h
2.87 + #275: Prefix macro names with LEMON_ in lemon/config.h
2.88 + ----: Small script for making the release tarballs added
2.89 + ----: Minor improvement in unify-sources.sh (a76f55d7d397)
2.90 +
2.91 2009-03-27 LEMON joins to the COIN-OR initiative
2.92
2.93 COIN-OR (Computational Infrastructure for Operations Research,
3.1 --- a/README Thu May 07 02:05:12 2009 +0200
3.2 +++ b/README Tue May 12 12:09:55 2009 +0100
3.3 @@ -1,6 +1,6 @@
3.4 -==================================================================
3.5 -LEMON - a Library of Efficient Models and Optimization in Networks
3.6 -==================================================================
3.7 +=====================================================================
3.8 +LEMON - a Library for Efficient Modeling and Optimization in Networks
3.9 +=====================================================================
3.10
3.11 LEMON is an open source library written in C++. It provides
3.12 easy-to-use implementations of common data structures and algorithms
4.1 --- a/doc/Makefile.am Thu May 07 02:05:12 2009 +0200
4.2 +++ b/doc/Makefile.am Tue May 12 12:09:55 2009 +0100
4.3 @@ -8,6 +8,7 @@
4.4 doc/license.dox \
4.5 doc/mainpage.dox \
4.6 doc/migration.dox \
4.7 + doc/min_cost_flow.dox \
4.8 doc/named-param.dox \
4.9 doc/namespaces.dox \
4.10 doc/html \
5.1 --- a/doc/groups.dox Thu May 07 02:05:12 2009 +0200
5.2 +++ b/doc/groups.dox Tue May 12 12:09:55 2009 +0100
5.3 @@ -138,16 +138,6 @@
5.4 */
5.5
5.6 /**
5.7 -@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
5.8 -@ingroup graphs
5.9 -\brief Graph types between real graphs and graph adaptors.
5.10 -
5.11 -This group contains some graph types between real graphs and graph adaptors.
5.12 -These classes wrap graphs to give new functionality as the adaptors do it.
5.13 -On the other hand they are not light-weight structures as the adaptors.
5.14 -*/
5.15 -
5.16 -/**
5.17 @defgroup maps Maps
5.18 @ingroup datas
5.19 \brief Map structures implemented in LEMON.
5.20 @@ -315,6 +305,7 @@
5.21 Tarjan for solving this problem. It also provides functions to query the
5.22 minimum cut, which is the dual problem of maximum flow.
5.23
5.24 +
5.25 \ref Circulation is a preflow push-relabel algorithm implemented directly
5.26 for finding feasible circulations, which is a somewhat different problem,
5.27 but it is strongly related to maximum flow.
5.28 @@ -322,86 +313,14 @@
5.29 */
5.30
5.31 /**
5.32 -@defgroup min_cost_flow Minimum Cost Flow Algorithms
5.33 +@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
5.34 @ingroup algs
5.35
5.36 \brief Algorithms for finding minimum cost flows and circulations.
5.37
5.38 This group contains the algorithms for finding minimum cost flows and
5.39 -circulations.
5.40 -
5.41 -The \e minimum \e cost \e flow \e problem is to find a feasible flow of
5.42 -minimum total cost from a set of supply nodes to a set of demand nodes
5.43 -in a network with capacity constraints (lower and upper bounds)
5.44 -and arc costs.
5.45 -Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{Z}\f$,
5.46 -\f$upper: A\rightarrow\mathbf{Z}\cup\{+\infty\}\f$ denote the lower and
5.47 -upper bounds for the flow values on the arcs, for which
5.48 -\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
5.49 -\f$cost: A\rightarrow\mathbf{Z}\f$ denotes the cost per unit flow
5.50 -on the arcs and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
5.51 -signed supply values of the nodes.
5.52 -If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
5.53 -supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
5.54 -\f$-sup(u)\f$ demand.
5.55 -A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution
5.56 -of the following optimization problem.
5.57 -
5.58 -\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
5.59 -\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
5.60 - sup(u) \quad \forall u\in V \f]
5.61 -\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
5.62 -
5.63 -The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
5.64 -zero or negative in order to have a feasible solution (since the sum
5.65 -of the expressions on the left-hand side of the inequalities is zero).
5.66 -It means that the total demand must be greater or equal to the total
5.67 -supply and all the supplies have to be carried out from the supply nodes,
5.68 -but there could be demands that are not satisfied.
5.69 -If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
5.70 -constraints have to be satisfied with equality, i.e. all demands
5.71 -have to be satisfied and all supplies have to be used.
5.72 -
5.73 -If you need the opposite inequalities in the supply/demand constraints
5.74 -(i.e. the total demand is less than the total supply and all the demands
5.75 -have to be satisfied while there could be supplies that are not used),
5.76 -then you could easily transform the problem to the above form by reversing
5.77 -the direction of the arcs and taking the negative of the supply values
5.78 -(e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
5.79 -However \ref NetworkSimplex algorithm also supports this form directly
5.80 -for the sake of convenience.
5.81 -
5.82 -A feasible solution for this problem can be found using \ref Circulation.
5.83 -
5.84 -Note that the above formulation is actually more general than the usual
5.85 -definition of the minimum cost flow problem, in which strict equalities
5.86 -are required in the supply/demand contraints, i.e.
5.87 -
5.88 -\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
5.89 - sup(u) \quad \forall u\in V. \f]
5.90 -
5.91 -However if the sum of the supply values is zero, then these two problems
5.92 -are equivalent. So if you need the equality form, you have to ensure this
5.93 -additional contraint for the algorithms.
5.94 -
5.95 -The dual solution of the minimum cost flow problem is represented by node
5.96 -potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
5.97 -An \f$f: A\rightarrow\mathbf{Z}\f$ feasible solution of the problem
5.98 -is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
5.99 -node potentials the following \e complementary \e slackness optimality
5.100 -conditions hold.
5.101 -
5.102 - - For all \f$uv\in A\f$ arcs:
5.103 - - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
5.104 - - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
5.105 - - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
5.106 - - For all \f$u\in V\f$ nodes:
5.107 - - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
5.108 - then \f$\pi(u)=0\f$.
5.109 -
5.110 -Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
5.111 -\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
5.112 -\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
5.113 +circulations. For more information about this problem and its dual
5.114 +solution see \ref min_cost_flow "Minimum Cost Flow Problem".
5.115
5.116 \ref NetworkSimplex is an efficient implementation of the primal Network
5.117 Simplex algorithm for finding minimum cost flows. It also provides dual
5.118 @@ -479,10 +398,10 @@
5.119 /**
5.120 @defgroup spantree Minimum Spanning Tree Algorithms
5.121 @ingroup algs
5.122 -\brief Algorithms for finding a minimum cost spanning tree in a graph.
5.123 +\brief Algorithms for finding minimum cost spanning trees and arborescences.
5.124
5.125 -This group contains the algorithms for finding a minimum cost spanning
5.126 -tree in a graph.
5.127 +This group contains the algorithms for finding minimum cost spanning
5.128 +trees and arborescences.
5.129 */
5.130
5.131 /**
6.1 --- a/doc/mainpage.dox Thu May 07 02:05:12 2009 +0200
6.2 +++ b/doc/mainpage.dox Tue May 12 12:09:55 2009 +0100
6.3 @@ -23,8 +23,7 @@
6.4
6.5 \subsection whatis What is LEMON
6.6
6.7 -LEMON stands for
6.8 -<b>L</b>ibrary of <b>E</b>fficient <b>M</b>odels
6.9 +LEMON stands for <b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
6.10 and <b>O</b>ptimization in <b>N</b>etworks.
6.11 It is a C++ template
6.12 library aimed at combinatorial optimization tasks which
6.13 @@ -41,14 +40,10 @@
6.14
6.15 \subsection howtoread How to read the documentation
6.16
6.17 -If you want to get a quick start and see the most important features then
6.18 -take a look at our \ref quicktour
6.19 -"Quick Tour to LEMON" which will guide you along.
6.20 -
6.21 -If you already feel like using our library, see the
6.22 +If you would like to get to know the library, see
6.23 <a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
6.24
6.25 -If you know what you are looking for then try to find it under the
6.26 +If you know what you are looking for, then try to find it under the
6.27 <a class="el" href="modules.html">Modules</a> section.
6.28
6.29 If you are a user of the old (0.x) series of LEMON, please check out the
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/doc/min_cost_flow.dox Tue May 12 12:09:55 2009 +0100
7.3 @@ -0,0 +1,153 @@
7.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
7.5 + *
7.6 + * This file is a part of LEMON, a generic C++ optimization library.
7.7 + *
7.8 + * Copyright (C) 2003-2009
7.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
7.11 + *
7.12 + * Permission to use, modify and distribute this software is granted
7.13 + * provided that this copyright notice appears in all copies. For
7.14 + * precise terms see the accompanying LICENSE file.
7.15 + *
7.16 + * This software is provided "AS IS" with no warranty of any kind,
7.17 + * express or implied, and with no claim as to its suitability for any
7.18 + * purpose.
7.19 + *
7.20 + */
7.21 +
7.22 +namespace lemon {
7.23 +
7.24 +/**
7.25 +\page min_cost_flow Minimum Cost Flow Problem
7.26 +
7.27 +\section mcf_def Definition (GEQ form)
7.28 +
7.29 +The \e minimum \e cost \e flow \e problem is to find a feasible flow of
7.30 +minimum total cost from a set of supply nodes to a set of demand nodes
7.31 +in a network with capacity constraints (lower and upper bounds)
7.32 +and arc costs.
7.33 +
7.34 +Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
7.35 +\f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and
7.36 +upper bounds for the flow values on the arcs, for which
7.37 +\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
7.38 +\f$cost: A\rightarrow\mathbf{R}\f$ denotes the cost per unit flow
7.39 +on the arcs and \f$sup: V\rightarrow\mathbf{R}\f$ denotes the
7.40 +signed supply values of the nodes.
7.41 +If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
7.42 +supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
7.43 +\f$-sup(u)\f$ demand.
7.44 +A minimum cost flow is an \f$f: A\rightarrow\mathbf{R}\f$ solution
7.45 +of the following optimization problem.
7.46 +
7.47 +\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
7.48 +\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
7.49 + sup(u) \quad \forall u\in V \f]
7.50 +\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
7.51 +
7.52 +The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
7.53 +zero or negative in order to have a feasible solution (since the sum
7.54 +of the expressions on the left-hand side of the inequalities is zero).
7.55 +It means that the total demand must be greater or equal to the total
7.56 +supply and all the supplies have to be carried out from the supply nodes,
7.57 +but there could be demands that are not satisfied.
7.58 +If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
7.59 +constraints have to be satisfied with equality, i.e. all demands
7.60 +have to be satisfied and all supplies have to be used.
7.61 +
7.62 +
7.63 +\section mcf_algs Algorithms
7.64 +
7.65 +LEMON contains several algorithms for solving this problem, for more
7.66 +information see \ref min_cost_flow_algs "Minimum Cost Flow Algorithms".
7.67 +
7.68 +A feasible solution for this problem can be found using \ref Circulation.
7.69 +
7.70 +
7.71 +\section mcf_dual Dual Solution
7.72 +
7.73 +The dual solution of the minimum cost flow problem is represented by
7.74 +node potentials \f$\pi: V\rightarrow\mathbf{R}\f$.
7.75 +An \f$f: A\rightarrow\mathbf{R}\f$ primal feasible solution is optimal
7.76 +if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$ node potentials
7.77 +the following \e complementary \e slackness optimality conditions hold.
7.78 +
7.79 + - For all \f$uv\in A\f$ arcs:
7.80 + - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
7.81 + - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
7.82 + - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
7.83 + - For all \f$u\in V\f$ nodes:
7.84 + - \f$\pi(u)<=0\f$;
7.85 + - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
7.86 + then \f$\pi(u)=0\f$.
7.87 +
7.88 +Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
7.89 +\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
7.90 +\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
7.91 +
7.92 +All algorithms provide dual solution (node potentials), as well,
7.93 +if an optimal flow is found.
7.94 +
7.95 +
7.96 +\section mcf_eq Equality Form
7.97 +
7.98 +The above \ref mcf_def "definition" is actually more general than the
7.99 +usual formulation of the minimum cost flow problem, in which strict
7.100 +equalities are required in the supply/demand contraints.
7.101 +
7.102 +\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
7.103 +\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
7.104 + sup(u) \quad \forall u\in V \f]
7.105 +\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
7.106 +
7.107 +However if the sum of the supply values is zero, then these two problems
7.108 +are equivalent.
7.109 +The \ref min_cost_flow_algs "algorithms" in LEMON support the general
7.110 +form, so if you need the equality form, you have to ensure this additional
7.111 +contraint manually.
7.112 +
7.113 +
7.114 +\section mcf_leq Opposite Inequalites (LEQ Form)
7.115 +
7.116 +Another possible definition of the minimum cost flow problem is
7.117 +when there are <em>"less or equal"</em> (LEQ) supply/demand constraints,
7.118 +instead of the <em>"greater or equal"</em> (GEQ) constraints.
7.119 +
7.120 +\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
7.121 +\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq
7.122 + sup(u) \quad \forall u\in V \f]
7.123 +\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
7.124 +
7.125 +It means that the total demand must be less or equal to the
7.126 +total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
7.127 +positive) and all the demands have to be satisfied, but there
7.128 +could be supplies that are not carried out from the supply
7.129 +nodes.
7.130 +The equality form is also a special case of this form, of course.
7.131 +
7.132 +You could easily transform this case to the \ref mcf_def "GEQ form"
7.133 +of the problem by reversing the direction of the arcs and taking the
7.134 +negative of the supply values (e.g. using \ref ReverseDigraph and
7.135 +\ref NegMap adaptors).
7.136 +However \ref NetworkSimplex algorithm also supports this form directly
7.137 +for the sake of convenience.
7.138 +
7.139 +Note that the optimality conditions for this supply constraint type are
7.140 +slightly differ from the conditions that are discussed for the GEQ form,
7.141 +namely the potentials have to be non-negative instead of non-positive.
7.142 +An \f$f: A\rightarrow\mathbf{R}\f$ feasible solution of this problem
7.143 +is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$
7.144 +node potentials the following conditions hold.
7.145 +
7.146 + - For all \f$uv\in A\f$ arcs:
7.147 + - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
7.148 + - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
7.149 + - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
7.150 + - For all \f$u\in V\f$ nodes:
7.151 + - \f$\pi(u)>=0\f$;
7.152 + - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
7.153 + then \f$\pi(u)=0\f$.
7.154 +
7.155 +*/
7.156 +}
8.1 --- a/lemon/Makefile.am Thu May 07 02:05:12 2009 +0200
8.2 +++ b/lemon/Makefile.am Tue May 12 12:09:55 2009 +0100
8.3 @@ -111,7 +111,6 @@
8.4 bits_HEADERS += \
8.5 lemon/bits/alteration_notifier.h \
8.6 lemon/bits/array_map.h \
8.7 - lemon/bits/base_extender.h \
8.8 lemon/bits/bezier.h \
8.9 lemon/bits/default_map.h \
8.10 lemon/bits/edge_set_extender.h \
9.1 --- a/lemon/adaptors.h Thu May 07 02:05:12 2009 +0200
9.2 +++ b/lemon/adaptors.h Tue May 12 12:09:55 2009 +0100
9.3 @@ -1839,31 +1839,31 @@
9.4 typedef typename Digraph::Arc Edge;
9.5 typedef typename Digraph::Node Node;
9.6
9.7 - class Arc : public Edge {
9.8 + class Arc {
9.9 friend class UndirectorBase;
9.10 protected:
9.11 + Edge _edge;
9.12 bool _forward;
9.13
9.14 - Arc(const Edge& edge, bool forward) :
9.15 - Edge(edge), _forward(forward) {}
9.16 + Arc(const Edge& edge, bool forward)
9.17 + : _edge(edge), _forward(forward) {}
9.18
9.19 public:
9.20 Arc() {}
9.21
9.22 - Arc(Invalid) : Edge(INVALID), _forward(true) {}
9.23 + Arc(Invalid) : _edge(INVALID), _forward(true) {}
9.24 +
9.25 + operator const Edge&() const { return _edge; }
9.26
9.27 bool operator==(const Arc &other) const {
9.28 - return _forward == other._forward &&
9.29 - static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
9.30 + return _forward == other._forward && _edge == other._edge;
9.31 }
9.32 bool operator!=(const Arc &other) const {
9.33 - return _forward != other._forward ||
9.34 - static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
9.35 + return _forward != other._forward || _edge != other._edge;
9.36 }
9.37 bool operator<(const Arc &other) const {
9.38 return _forward < other._forward ||
9.39 - (_forward == other._forward &&
9.40 - static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
9.41 + (_forward == other._forward && _edge < other._edge);
9.42 }
9.43 };
9.44
9.45 @@ -1876,7 +1876,7 @@
9.46 }
9.47
9.48 void first(Arc& a) const {
9.49 - _digraph->first(a);
9.50 + _digraph->first(a._edge);
9.51 a._forward = true;
9.52 }
9.53
9.54 @@ -1884,7 +1884,7 @@
9.55 if (a._forward) {
9.56 a._forward = false;
9.57 } else {
9.58 - _digraph->next(a);
9.59 + _digraph->next(a._edge);
9.60 a._forward = true;
9.61 }
9.62 }
9.63 @@ -1898,48 +1898,48 @@
9.64 }
9.65
9.66 void firstOut(Arc& a, const Node& n) const {
9.67 - _digraph->firstIn(a, n);
9.68 - if( static_cast<const Edge&>(a) != INVALID ) {
9.69 + _digraph->firstIn(a._edge, n);
9.70 + if (a._edge != INVALID ) {
9.71 a._forward = false;
9.72 } else {
9.73 - _digraph->firstOut(a, n);
9.74 + _digraph->firstOut(a._edge, n);
9.75 a._forward = true;
9.76 }
9.77 }
9.78 void nextOut(Arc &a) const {
9.79 if (!a._forward) {
9.80 - Node n = _digraph->target(a);
9.81 - _digraph->nextIn(a);
9.82 - if (static_cast<const Edge&>(a) == INVALID ) {
9.83 - _digraph->firstOut(a, n);
9.84 + Node n = _digraph->target(a._edge);
9.85 + _digraph->nextIn(a._edge);
9.86 + if (a._edge == INVALID) {
9.87 + _digraph->firstOut(a._edge, n);
9.88 a._forward = true;
9.89 }
9.90 }
9.91 else {
9.92 - _digraph->nextOut(a);
9.93 + _digraph->nextOut(a._edge);
9.94 }
9.95 }
9.96
9.97 void firstIn(Arc &a, const Node &n) const {
9.98 - _digraph->firstOut(a, n);
9.99 - if (static_cast<const Edge&>(a) != INVALID ) {
9.100 + _digraph->firstOut(a._edge, n);
9.101 + if (a._edge != INVALID ) {
9.102 a._forward = false;
9.103 } else {
9.104 - _digraph->firstIn(a, n);
9.105 + _digraph->firstIn(a._edge, n);
9.106 a._forward = true;
9.107 }
9.108 }
9.109 void nextIn(Arc &a) const {
9.110 if (!a._forward) {
9.111 - Node n = _digraph->source(a);
9.112 - _digraph->nextOut(a);
9.113 - if( static_cast<const Edge&>(a) == INVALID ) {
9.114 - _digraph->firstIn(a, n);
9.115 + Node n = _digraph->source(a._edge);
9.116 + _digraph->nextOut(a._edge);
9.117 + if (a._edge == INVALID ) {
9.118 + _digraph->firstIn(a._edge, n);
9.119 a._forward = true;
9.120 }
9.121 }
9.122 else {
9.123 - _digraph->nextIn(a);
9.124 + _digraph->nextIn(a._edge);
9.125 }
9.126 }
9.127
9.128 @@ -1972,19 +1972,16 @@
9.129 }
9.130
9.131 Node source(const Arc &a) const {
9.132 - return a._forward ? _digraph->source(a) : _digraph->target(a);
9.133 + return a._forward ? _digraph->source(a._edge) : _digraph->target(a._edge);
9.134 }
9.135
9.136 Node target(const Arc &a) const {
9.137 - return a._forward ? _digraph->target(a) : _digraph->source(a);
9.138 + return a._forward ? _digraph->target(a._edge) : _digraph->source(a._edge);
9.139 }
9.140
9.141 static Arc direct(const Edge &e, bool d) {
9.142 return Arc(e, d);
9.143 }
9.144 - Arc direct(const Edge &e, const Node& n) const {
9.145 - return Arc(e, _digraph->source(e) == n);
9.146 - }
9.147
9.148 static bool direction(const Arc &a) { return a._forward; }
9.149
10.1 --- a/lemon/bits/base_extender.h Thu May 07 02:05:12 2009 +0200
10.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
10.3 @@ -1,495 +0,0 @@
10.4 -/* -*- mode: C++; indent-tabs-mode: nil; -*-
10.5 - *
10.6 - * This file is a part of LEMON, a generic C++ optimization library.
10.7 - *
10.8 - * Copyright (C) 2003-2009
10.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
10.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
10.11 - *
10.12 - * Permission to use, modify and distribute this software is granted
10.13 - * provided that this copyright notice appears in all copies. For
10.14 - * precise terms see the accompanying LICENSE file.
10.15 - *
10.16 - * This software is provided "AS IS" with no warranty of any kind,
10.17 - * express or implied, and with no claim as to its suitability for any
10.18 - * purpose.
10.19 - *
10.20 - */
10.21 -
10.22 -#ifndef LEMON_BITS_BASE_EXTENDER_H
10.23 -#define LEMON_BITS_BASE_EXTENDER_H
10.24 -
10.25 -#include <lemon/core.h>
10.26 -#include <lemon/error.h>
10.27 -
10.28 -#include <lemon/bits/map_extender.h>
10.29 -#include <lemon/bits/default_map.h>
10.30 -
10.31 -#include <lemon/concept_check.h>
10.32 -#include <lemon/concepts/maps.h>
10.33 -
10.34 -//\ingroup digraphbits
10.35 -//\file
10.36 -//\brief Extenders for the graph types
10.37 -namespace lemon {
10.38 -
10.39 - // \ingroup digraphbits
10.40 - //
10.41 - // \brief BaseDigraph to BaseGraph extender
10.42 - template <typename Base>
10.43 - class UndirDigraphExtender : public Base {
10.44 - typedef Base Parent;
10.45 -
10.46 - public:
10.47 -
10.48 - typedef typename Parent::Arc Edge;
10.49 - typedef typename Parent::Node Node;
10.50 -
10.51 - typedef True UndirectedTag;
10.52 -
10.53 - class Arc : public Edge {
10.54 - friend class UndirDigraphExtender;
10.55 -
10.56 - protected:
10.57 - bool forward;
10.58 -
10.59 - Arc(const Edge &ue, bool _forward) :
10.60 - Edge(ue), forward(_forward) {}
10.61 -
10.62 - public:
10.63 - Arc() {}
10.64 -
10.65 - // Invalid arc constructor
10.66 - Arc(Invalid i) : Edge(i), forward(true) {}
10.67 -
10.68 - bool operator==(const Arc &that) const {
10.69 - return forward==that.forward && Edge(*this)==Edge(that);
10.70 - }
10.71 - bool operator!=(const Arc &that) const {
10.72 - return forward!=that.forward || Edge(*this)!=Edge(that);
10.73 - }
10.74 - bool operator<(const Arc &that) const {
10.75 - return forward<that.forward ||
10.76 - (!(that.forward<forward) && Edge(*this)<Edge(that));
10.77 - }
10.78 - };
10.79 -
10.80 - // First node of the edge
10.81 - Node u(const Edge &e) const {
10.82 - return Parent::source(e);
10.83 - }
10.84 -
10.85 - // Source of the given arc
10.86 - Node source(const Arc &e) const {
10.87 - return e.forward ? Parent::source(e) : Parent::target(e);
10.88 - }
10.89 -
10.90 - // Second node of the edge
10.91 - Node v(const Edge &e) const {
10.92 - return Parent::target(e);
10.93 - }
10.94 -
10.95 - // Target of the given arc
10.96 - Node target(const Arc &e) const {
10.97 - return e.forward ? Parent::target(e) : Parent::source(e);
10.98 - }
10.99 -
10.100 - // \brief Directed arc from an edge.
10.101 - //
10.102 - // Returns a directed arc corresponding to the specified edge.
10.103 - // If the given bool is true, the first node of the given edge and
10.104 - // the source node of the returned arc are the same.
10.105 - static Arc direct(const Edge &e, bool d) {
10.106 - return Arc(e, d);
10.107 - }
10.108 -
10.109 - // Returns whether the given directed arc has the same orientation
10.110 - // as the corresponding edge.
10.111 - static bool direction(const Arc &a) { return a.forward; }
10.112 -
10.113 - using Parent::first;
10.114 - using Parent::next;
10.115 -
10.116 - void first(Arc &e) const {
10.117 - Parent::first(e);
10.118 - e.forward=true;
10.119 - }
10.120 -
10.121 - void next(Arc &e) const {
10.122 - if( e.forward ) {
10.123 - e.forward = false;
10.124 - }
10.125 - else {
10.126 - Parent::next(e);
10.127 - e.forward = true;
10.128 - }
10.129 - }
10.130 -
10.131 - void firstOut(Arc &e, const Node &n) const {
10.132 - Parent::firstIn(e,n);
10.133 - if( Edge(e) != INVALID ) {
10.134 - e.forward = false;
10.135 - }
10.136 - else {
10.137 - Parent::firstOut(e,n);
10.138 - e.forward = true;
10.139 - }
10.140 - }
10.141 - void nextOut(Arc &e) const {
10.142 - if( ! e.forward ) {
10.143 - Node n = Parent::target(e);
10.144 - Parent::nextIn(e);
10.145 - if( Edge(e) == INVALID ) {
10.146 - Parent::firstOut(e, n);
10.147 - e.forward = true;
10.148 - }
10.149 - }
10.150 - else {
10.151 - Parent::nextOut(e);
10.152 - }
10.153 - }
10.154 -
10.155 - void firstIn(Arc &e, const Node &n) const {
10.156 - Parent::firstOut(e,n);
10.157 - if( Edge(e) != INVALID ) {
10.158 - e.forward = false;
10.159 - }
10.160 - else {
10.161 - Parent::firstIn(e,n);
10.162 - e.forward = true;
10.163 - }
10.164 - }
10.165 - void nextIn(Arc &e) const {
10.166 - if( ! e.forward ) {
10.167 - Node n = Parent::source(e);
10.168 - Parent::nextOut(e);
10.169 - if( Edge(e) == INVALID ) {
10.170 - Parent::firstIn(e, n);
10.171 - e.forward = true;
10.172 - }
10.173 - }
10.174 - else {
10.175 - Parent::nextIn(e);
10.176 - }
10.177 - }
10.178 -
10.179 - void firstInc(Edge &e, bool &d, const Node &n) const {
10.180 - d = true;
10.181 - Parent::firstOut(e, n);
10.182 - if (e != INVALID) return;
10.183 - d = false;
10.184 - Parent::firstIn(e, n);
10.185 - }
10.186 -
10.187 - void nextInc(Edge &e, bool &d) const {
10.188 - if (d) {
10.189 - Node s = Parent::source(e);
10.190 - Parent::nextOut(e);
10.191 - if (e != INVALID) return;
10.192 - d = false;
10.193 - Parent::firstIn(e, s);
10.194 - } else {
10.195 - Parent::nextIn(e);
10.196 - }
10.197 - }
10.198 -
10.199 - Node nodeFromId(int ix) const {
10.200 - return Parent::nodeFromId(ix);
10.201 - }
10.202 -
10.203 - Arc arcFromId(int ix) const {
10.204 - return direct(Parent::arcFromId(ix >> 1), bool(ix & 1));
10.205 - }
10.206 -
10.207 - Edge edgeFromId(int ix) const {
10.208 - return Parent::arcFromId(ix);
10.209 - }
10.210 -
10.211 - int id(const Node &n) const {
10.212 - return Parent::id(n);
10.213 - }
10.214 -
10.215 - int id(const Edge &e) const {
10.216 - return Parent::id(e);
10.217 - }
10.218 -
10.219 - int id(const Arc &e) const {
10.220 - return 2 * Parent::id(e) + int(e.forward);
10.221 - }
10.222 -
10.223 - int maxNodeId() const {
10.224 - return Parent::maxNodeId();
10.225 - }
10.226 -
10.227 - int maxArcId() const {
10.228 - return 2 * Parent::maxArcId() + 1;
10.229 - }
10.230 -
10.231 - int maxEdgeId() const {
10.232 - return Parent::maxArcId();
10.233 - }
10.234 -
10.235 - int arcNum() const {
10.236 - return 2 * Parent::arcNum();
10.237 - }
10.238 -
10.239 - int edgeNum() const {
10.240 - return Parent::arcNum();
10.241 - }
10.242 -
10.243 - Arc findArc(Node s, Node t, Arc p = INVALID) const {
10.244 - if (p == INVALID) {
10.245 - Edge arc = Parent::findArc(s, t);
10.246 - if (arc != INVALID) return direct(arc, true);
10.247 - arc = Parent::findArc(t, s);
10.248 - if (arc != INVALID) return direct(arc, false);
10.249 - } else if (direction(p)) {
10.250 - Edge arc = Parent::findArc(s, t, p);
10.251 - if (arc != INVALID) return direct(arc, true);
10.252 - arc = Parent::findArc(t, s);
10.253 - if (arc != INVALID) return direct(arc, false);
10.254 - } else {
10.255 - Edge arc = Parent::findArc(t, s, p);
10.256 - if (arc != INVALID) return direct(arc, false);
10.257 - }
10.258 - return INVALID;
10.259 - }
10.260 -
10.261 - Edge findEdge(Node s, Node t, Edge p = INVALID) const {
10.262 - if (s != t) {
10.263 - if (p == INVALID) {
10.264 - Edge arc = Parent::findArc(s, t);
10.265 - if (arc != INVALID) return arc;
10.266 - arc = Parent::findArc(t, s);
10.267 - if (arc != INVALID) return arc;
10.268 - } else if (Parent::s(p) == s) {
10.269 - Edge arc = Parent::findArc(s, t, p);
10.270 - if (arc != INVALID) return arc;
10.271 - arc = Parent::findArc(t, s);
10.272 - if (arc != INVALID) return arc;
10.273 - } else {
10.274 - Edge arc = Parent::findArc(t, s, p);
10.275 - if (arc != INVALID) return arc;
10.276 - }
10.277 - } else {
10.278 - return Parent::findArc(s, t, p);
10.279 - }
10.280 - return INVALID;
10.281 - }
10.282 - };
10.283 -
10.284 - template <typename Base>
10.285 - class BidirBpGraphExtender : public Base {
10.286 - typedef Base Parent;
10.287 -
10.288 - public:
10.289 - typedef BidirBpGraphExtender Digraph;
10.290 -
10.291 - typedef typename Parent::Node Node;
10.292 - typedef typename Parent::Edge Edge;
10.293 -
10.294 -
10.295 - using Parent::first;
10.296 - using Parent::next;
10.297 -
10.298 - using Parent::id;
10.299 -
10.300 - class Red : public Node {
10.301 - friend class BidirBpGraphExtender;
10.302 - public:
10.303 - Red() {}
10.304 - Red(const Node& node) : Node(node) {
10.305 - LEMON_DEBUG(Parent::red(node) || node == INVALID,
10.306 - typename Parent::NodeSetError());
10.307 - }
10.308 - Red& operator=(const Node& node) {
10.309 - LEMON_DEBUG(Parent::red(node) || node == INVALID,
10.310 - typename Parent::NodeSetError());
10.311 - Node::operator=(node);
10.312 - return *this;
10.313 - }
10.314 - Red(Invalid) : Node(INVALID) {}
10.315 - Red& operator=(Invalid) {
10.316 - Node::operator=(INVALID);
10.317 - return *this;
10.318 - }
10.319 - };
10.320 -
10.321 - void first(Red& node) const {
10.322 - Parent::firstRed(static_cast<Node&>(node));
10.323 - }
10.324 - void next(Red& node) const {
10.325 - Parent::nextRed(static_cast<Node&>(node));
10.326 - }
10.327 -
10.328 - int id(const Red& node) const {
10.329 - return Parent::redId(node);
10.330 - }
10.331 -
10.332 - class Blue : public Node {
10.333 - friend class BidirBpGraphExtender;
10.334 - public:
10.335 - Blue() {}
10.336 - Blue(const Node& node) : Node(node) {
10.337 - LEMON_DEBUG(Parent::blue(node) || node == INVALID,
10.338 - typename Parent::NodeSetError());
10.339 - }
10.340 - Blue& operator=(const Node& node) {
10.341 - LEMON_DEBUG(Parent::blue(node) || node == INVALID,
10.342 - typename Parent::NodeSetError());
10.343 - Node::operator=(node);
10.344 - return *this;
10.345 - }
10.346 - Blue(Invalid) : Node(INVALID) {}
10.347 - Blue& operator=(Invalid) {
10.348 - Node::operator=(INVALID);
10.349 - return *this;
10.350 - }
10.351 - };
10.352 -
10.353 - void first(Blue& node) const {
10.354 - Parent::firstBlue(static_cast<Node&>(node));
10.355 - }
10.356 - void next(Blue& node) const {
10.357 - Parent::nextBlue(static_cast<Node&>(node));
10.358 - }
10.359 -
10.360 - int id(const Blue& node) const {
10.361 - return Parent::redId(node);
10.362 - }
10.363 -
10.364 - Node source(const Edge& arc) const {
10.365 - return red(arc);
10.366 - }
10.367 - Node target(const Edge& arc) const {
10.368 - return blue(arc);
10.369 - }
10.370 -
10.371 - void firstInc(Edge& arc, bool& dir, const Node& node) const {
10.372 - if (Parent::red(node)) {
10.373 - Parent::firstFromRed(arc, node);
10.374 - dir = true;
10.375 - } else {
10.376 - Parent::firstFromBlue(arc, node);
10.377 - dir = static_cast<Edge&>(arc) == INVALID;
10.378 - }
10.379 - }
10.380 - void nextInc(Edge& arc, bool& dir) const {
10.381 - if (dir) {
10.382 - Parent::nextFromRed(arc);
10.383 - } else {
10.384 - Parent::nextFromBlue(arc);
10.385 - if (arc == INVALID) dir = true;
10.386 - }
10.387 - }
10.388 -
10.389 - class Arc : public Edge {
10.390 - friend class BidirBpGraphExtender;
10.391 - protected:
10.392 - bool forward;
10.393 -
10.394 - Arc(const Edge& arc, bool _forward)
10.395 - : Edge(arc), forward(_forward) {}
10.396 -
10.397 - public:
10.398 - Arc() {}
10.399 - Arc (Invalid) : Edge(INVALID), forward(true) {}
10.400 - bool operator==(const Arc& i) const {
10.401 - return Edge::operator==(i) && forward == i.forward;
10.402 - }
10.403 - bool operator!=(const Arc& i) const {
10.404 - return Edge::operator!=(i) || forward != i.forward;
10.405 - }
10.406 - bool operator<(const Arc& i) const {
10.407 - return Edge::operator<(i) ||
10.408 - (!(i.forward<forward) && Edge(*this)<Edge(i));
10.409 - }
10.410 - };
10.411 -
10.412 - void first(Arc& arc) const {
10.413 - Parent::first(static_cast<Edge&>(arc));
10.414 - arc.forward = true;
10.415 - }
10.416 -
10.417 - void next(Arc& arc) const {
10.418 - if (!arc.forward) {
10.419 - Parent::next(static_cast<Edge&>(arc));
10.420 - }
10.421 - arc.forward = !arc.forward;
10.422 - }
10.423 -
10.424 - void firstOut(Arc& arc, const Node& node) const {
10.425 - if (Parent::red(node)) {
10.426 - Parent::firstFromRed(arc, node);
10.427 - arc.forward = true;
10.428 - } else {
10.429 - Parent::firstFromBlue(arc, node);
10.430 - arc.forward = static_cast<Edge&>(arc) == INVALID;
10.431 - }
10.432 - }
10.433 - void nextOut(Arc& arc) const {
10.434 - if (arc.forward) {
10.435 - Parent::nextFromRed(arc);
10.436 - } else {
10.437 - Parent::nextFromBlue(arc);
10.438 - arc.forward = static_cast<Edge&>(arc) == INVALID;
10.439 - }
10.440 - }
10.441 -
10.442 - void firstIn(Arc& arc, const Node& node) const {
10.443 - if (Parent::blue(node)) {
10.444 - Parent::firstFromBlue(arc, node);
10.445 - arc.forward = true;
10.446 - } else {
10.447 - Parent::firstFromRed(arc, node);
10.448 - arc.forward = static_cast<Edge&>(arc) == INVALID;
10.449 - }
10.450 - }
10.451 - void nextIn(Arc& arc) const {
10.452 - if (arc.forward) {
10.453 - Parent::nextFromBlue(arc);
10.454 - } else {
10.455 - Parent::nextFromRed(arc);
10.456 - arc.forward = static_cast<Edge&>(arc) == INVALID;
10.457 - }
10.458 - }
10.459 -
10.460 - Node source(const Arc& arc) const {
10.461 - return arc.forward ? Parent::red(arc) : Parent::blue(arc);
10.462 - }
10.463 - Node target(const Arc& arc) const {
10.464 - return arc.forward ? Parent::blue(arc) : Parent::red(arc);
10.465 - }
10.466 -
10.467 - int id(const Arc& arc) const {
10.468 - return (Parent::id(static_cast<const Edge&>(arc)) << 1) +
10.469 - (arc.forward ? 0 : 1);
10.470 - }
10.471 - Arc arcFromId(int ix) const {
10.472 - return Arc(Parent::fromEdgeId(ix >> 1), (ix & 1) == 0);
10.473 - }
10.474 - int maxArcId() const {
10.475 - return (Parent::maxEdgeId() << 1) + 1;
10.476 - }
10.477 -
10.478 - bool direction(const Arc& arc) const {
10.479 - return arc.forward;
10.480 - }
10.481 -
10.482 - Arc direct(const Edge& arc, bool dir) const {
10.483 - return Arc(arc, dir);
10.484 - }
10.485 -
10.486 - int arcNum() const {
10.487 - return 2 * Parent::edgeNum();
10.488 - }
10.489 -
10.490 - int edgeNum() const {
10.491 - return Parent::edgeNum();
10.492 - }
10.493 -
10.494 -
10.495 - };
10.496 -}
10.497 -
10.498 -#endif
11.1 --- a/lemon/concepts/graph.h Thu May 07 02:05:12 2009 +0200
11.2 +++ b/lemon/concepts/graph.h Tue May 12 12:09:55 2009 +0100
11.3 @@ -310,8 +310,8 @@
11.4
11.5 /// The directed arc type. It can be converted to the
11.6 /// edge or it should be inherited from the undirected
11.7 - /// arc.
11.8 - class Arc : public Edge {
11.9 + /// edge.
11.10 + class Arc {
11.11 public:
11.12 /// Default constructor
11.13
11.14 @@ -322,7 +322,7 @@
11.15
11.16 /// Copy constructor.
11.17 ///
11.18 - Arc(const Arc& e) : Edge(e) { }
11.19 + Arc(const Arc&) { }
11.20 /// Initialize the iterator to be invalid.
11.21
11.22 /// Initialize the iterator to be invalid.
11.23 @@ -349,6 +349,8 @@
11.24 /// ordering of the items.
11.25 bool operator<(Arc) const { return false; }
11.26
11.27 + /// Converison to Edge
11.28 + operator Edge() const { return Edge(); }
11.29 };
11.30 /// This iterator goes through each directed arc.
11.31
12.1 --- a/lemon/connectivity.h Thu May 07 02:05:12 2009 +0200
12.2 +++ b/lemon/connectivity.h Tue May 12 12:09:55 2009 +0100
12.3 @@ -42,12 +42,16 @@
12.4
12.5 /// \ingroup graph_properties
12.6 ///
12.7 - /// \brief Check whether the given undirected graph is connected.
12.8 + /// \brief Check whether an undirected graph is connected.
12.9 ///
12.10 - /// Check whether the given undirected graph is connected.
12.11 - /// \param graph The undirected graph.
12.12 - /// \return \c true when there is path between any two nodes in the graph.
12.13 + /// This function checks whether the given undirected graph is connected,
12.14 + /// i.e. there is a path between any two nodes in the graph.
12.15 + ///
12.16 + /// \return \c true if the graph is connected.
12.17 /// \note By definition, the empty graph is connected.
12.18 + ///
12.19 + /// \see countConnectedComponents(), connectedComponents()
12.20 + /// \see stronglyConnected()
12.21 template <typename Graph>
12.22 bool connected(const Graph& graph) {
12.23 checkConcept<concepts::Graph, Graph>();
12.24 @@ -67,12 +71,18 @@
12.25 ///
12.26 /// \brief Count the number of connected components of an undirected graph
12.27 ///
12.28 - /// Count the number of connected components of an undirected graph
12.29 + /// This function counts the number of connected components of the given
12.30 + /// undirected graph.
12.31 ///
12.32 - /// \param graph The graph. It must be undirected.
12.33 - /// \return The number of components
12.34 + /// The connected components are the classes of an equivalence relation
12.35 + /// on the nodes of an undirected graph. Two nodes are in the same class
12.36 + /// if they are connected with a path.
12.37 + ///
12.38 + /// \return The number of connected components.
12.39 /// \note By definition, the empty graph consists
12.40 /// of zero connected components.
12.41 + ///
12.42 + /// \see connected(), connectedComponents()
12.43 template <typename Graph>
12.44 int countConnectedComponents(const Graph &graph) {
12.45 checkConcept<concepts::Graph, Graph>();
12.46 @@ -109,17 +119,26 @@
12.47 ///
12.48 /// \brief Find the connected components of an undirected graph
12.49 ///
12.50 - /// Find the connected components of an undirected graph.
12.51 + /// This function finds the connected components of the given undirected
12.52 + /// graph.
12.53 + ///
12.54 + /// The connected components are the classes of an equivalence relation
12.55 + /// on the nodes of an undirected graph. Two nodes are in the same class
12.56 + /// if they are connected with a path.
12.57 ///
12.58 /// \image html connected_components.png
12.59 /// \image latex connected_components.eps "Connected components" width=\textwidth
12.60 ///
12.61 - /// \param graph The graph. It must be undirected.
12.62 + /// \param graph The undirected graph.
12.63 /// \retval compMap A writable node map. The values will be set from 0 to
12.64 - /// the number of the connected components minus one. Each values of the map
12.65 - /// will be set exactly once, the values of a certain component will be
12.66 + /// the number of the connected components minus one. Each value of the map
12.67 + /// will be set exactly once, and the values of a certain component will be
12.68 /// set continuously.
12.69 - /// \return The number of components
12.70 + /// \return The number of connected components.
12.71 + /// \note By definition, the empty graph consists
12.72 + /// of zero connected components.
12.73 + ///
12.74 + /// \see connected(), countConnectedComponents()
12.75 template <class Graph, class NodeMap>
12.76 int connectedComponents(const Graph &graph, NodeMap &compMap) {
12.77 checkConcept<concepts::Graph, Graph>();
12.78 @@ -231,15 +250,17 @@
12.79
12.80 /// \ingroup graph_properties
12.81 ///
12.82 - /// \brief Check whether the given directed graph is strongly connected.
12.83 + /// \brief Check whether a directed graph is strongly connected.
12.84 ///
12.85 - /// Check whether the given directed graph is strongly connected. The
12.86 - /// graph is strongly connected when any two nodes of the graph are
12.87 + /// This function checks whether the given directed graph is strongly
12.88 + /// connected, i.e. any two nodes of the digraph are
12.89 /// connected with directed paths in both direction.
12.90 - /// \return \c false when the graph is not strongly connected.
12.91 - /// \see connected
12.92 ///
12.93 - /// \note By definition, the empty graph is strongly connected.
12.94 + /// \return \c true if the digraph is strongly connected.
12.95 + /// \note By definition, the empty digraph is strongly connected.
12.96 + ///
12.97 + /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()
12.98 + /// \see connected()
12.99 template <typename Digraph>
12.100 bool stronglyConnected(const Digraph& digraph) {
12.101 checkConcept<concepts::Digraph, Digraph>();
12.102 @@ -270,7 +291,7 @@
12.103 typedef typename RDigraph::NodeIt RNodeIt;
12.104 RDigraph rdigraph(digraph);
12.105
12.106 - typedef DfsVisitor<Digraph> RVisitor;
12.107 + typedef DfsVisitor<RDigraph> RVisitor;
12.108 RVisitor rvisitor;
12.109
12.110 DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
12.111 @@ -289,18 +310,22 @@
12.112
12.113 /// \ingroup graph_properties
12.114 ///
12.115 - /// \brief Count the strongly connected components of a directed graph
12.116 + /// \brief Count the number of strongly connected components of a
12.117 + /// directed graph
12.118 ///
12.119 - /// Count the strongly connected components of a directed graph.
12.120 + /// This function counts the number of strongly connected components of
12.121 + /// the given directed graph.
12.122 + ///
12.123 /// The strongly connected components are the classes of an
12.124 - /// equivalence relation on the nodes of the graph. Two nodes are in
12.125 + /// equivalence relation on the nodes of a digraph. Two nodes are in
12.126 /// the same class if they are connected with directed paths in both
12.127 /// direction.
12.128 ///
12.129 - /// \param digraph The graph.
12.130 - /// \return The number of components
12.131 - /// \note By definition, the empty graph has zero
12.132 + /// \return The number of strongly connected components.
12.133 + /// \note By definition, the empty digraph has zero
12.134 /// strongly connected components.
12.135 + ///
12.136 + /// \see stronglyConnected(), stronglyConnectedComponents()
12.137 template <typename Digraph>
12.138 int countStronglyConnectedComponents(const Digraph& digraph) {
12.139 checkConcept<concepts::Digraph, Digraph>();
12.140 @@ -355,13 +380,15 @@
12.141 ///
12.142 /// \brief Find the strongly connected components of a directed graph
12.143 ///
12.144 - /// Find the strongly connected components of a directed graph. The
12.145 - /// strongly connected components are the classes of an equivalence
12.146 - /// relation on the nodes of the graph. Two nodes are in
12.147 - /// relationship when there are directed paths between them in both
12.148 - /// direction. In addition, the numbering of components will satisfy
12.149 - /// that there is no arc going from a higher numbered component to
12.150 - /// a lower.
12.151 + /// This function finds the strongly connected components of the given
12.152 + /// directed graph. In addition, the numbering of the components will
12.153 + /// satisfy that there is no arc going from a higher numbered component
12.154 + /// to a lower one (i.e. it provides a topological order of the components).
12.155 + ///
12.156 + /// The strongly connected components are the classes of an
12.157 + /// equivalence relation on the nodes of a digraph. Two nodes are in
12.158 + /// the same class if they are connected with directed paths in both
12.159 + /// direction.
12.160 ///
12.161 /// \image html strongly_connected_components.png
12.162 /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
12.163 @@ -369,9 +396,13 @@
12.164 /// \param digraph The digraph.
12.165 /// \retval compMap A writable node map. The values will be set from 0 to
12.166 /// the number of the strongly connected components minus one. Each value
12.167 - /// of the map will be set exactly once, the values of a certain component
12.168 - /// will be set continuously.
12.169 - /// \return The number of components
12.170 + /// of the map will be set exactly once, and the values of a certain
12.171 + /// component will be set continuously.
12.172 + /// \return The number of strongly connected components.
12.173 + /// \note By definition, the empty digraph has zero
12.174 + /// strongly connected components.
12.175 + ///
12.176 + /// \see stronglyConnected(), countStronglyConnectedComponents()
12.177 template <typename Digraph, typename NodeMap>
12.178 int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
12.179 checkConcept<concepts::Digraph, Digraph>();
12.180 @@ -424,19 +455,24 @@
12.181 ///
12.182 /// \brief Find the cut arcs of the strongly connected components.
12.183 ///
12.184 - /// Find the cut arcs of the strongly connected components.
12.185 - /// The strongly connected components are the classes of an equivalence
12.186 - /// relation on the nodes of the graph. Two nodes are in relationship
12.187 - /// when there are directed paths between them in both direction.
12.188 + /// This function finds the cut arcs of the strongly connected components
12.189 + /// of the given digraph.
12.190 + ///
12.191 + /// The strongly connected components are the classes of an
12.192 + /// equivalence relation on the nodes of a digraph. Two nodes are in
12.193 + /// the same class if they are connected with directed paths in both
12.194 + /// direction.
12.195 /// The strongly connected components are separated by the cut arcs.
12.196 ///
12.197 - /// \param graph The graph.
12.198 - /// \retval cutMap A writable node map. The values will be set true when the
12.199 - /// arc is a cut arc.
12.200 + /// \param digraph The digraph.
12.201 + /// \retval cutMap A writable arc map. The values will be set to \c true
12.202 + /// for the cut arcs (exactly once for each cut arc), and will not be
12.203 + /// changed for other arcs.
12.204 + /// \return The number of cut arcs.
12.205 ///
12.206 - /// \return The number of cut arcs
12.207 + /// \see stronglyConnected(), stronglyConnectedComponents()
12.208 template <typename Digraph, typename ArcMap>
12.209 - int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) {
12.210 + int stronglyConnectedCutArcs(const Digraph& digraph, ArcMap& cutMap) {
12.211 checkConcept<concepts::Digraph, Digraph>();
12.212 typedef typename Digraph::Node Node;
12.213 typedef typename Digraph::Arc Arc;
12.214 @@ -448,13 +484,13 @@
12.215 typedef std::vector<Node> Container;
12.216 typedef typename Container::iterator Iterator;
12.217
12.218 - Container nodes(countNodes(graph));
12.219 + Container nodes(countNodes(digraph));
12.220 typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
12.221 Visitor visitor(nodes.begin());
12.222
12.223 - DfsVisit<Digraph, Visitor> dfs(graph, visitor);
12.224 + DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
12.225 dfs.init();
12.226 - for (NodeIt it(graph); it != INVALID; ++it) {
12.227 + for (NodeIt it(digraph); it != INVALID; ++it) {
12.228 if (!dfs.reached(it)) {
12.229 dfs.addSource(it);
12.230 dfs.start();
12.231 @@ -464,14 +500,14 @@
12.232 typedef typename Container::reverse_iterator RIterator;
12.233 typedef ReverseDigraph<const Digraph> RDigraph;
12.234
12.235 - RDigraph rgraph(graph);
12.236 + RDigraph rdigraph(digraph);
12.237
12.238 int cutNum = 0;
12.239
12.240 typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
12.241 - RVisitor rvisitor(rgraph, cutMap, cutNum);
12.242 + RVisitor rvisitor(rdigraph, cutMap, cutNum);
12.243
12.244 - DfsVisit<RDigraph, RVisitor> rdfs(rgraph, rvisitor);
12.245 + DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
12.246
12.247 rdfs.init();
12.248 for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
12.249 @@ -706,14 +742,15 @@
12.250
12.251 /// \ingroup graph_properties
12.252 ///
12.253 - /// \brief Checks the graph is bi-node-connected.
12.254 + /// \brief Check whether an undirected graph is bi-node-connected.
12.255 ///
12.256 - /// This function checks that the undirected graph is bi-node-connected
12.257 - /// graph. The graph is bi-node-connected if any two undirected edge is
12.258 - /// on same circle.
12.259 + /// This function checks whether the given undirected graph is
12.260 + /// bi-node-connected, i.e. any two edges are on same circle.
12.261 ///
12.262 - /// \param graph The graph.
12.263 - /// \return \c true when the graph bi-node-connected.
12.264 + /// \return \c true if the graph bi-node-connected.
12.265 + /// \note By definition, the empty graph is bi-node-connected.
12.266 + ///
12.267 + /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()
12.268 template <typename Graph>
12.269 bool biNodeConnected(const Graph& graph) {
12.270 return countBiNodeConnectedComponents(graph) <= 1;
12.271 @@ -721,15 +758,19 @@
12.272
12.273 /// \ingroup graph_properties
12.274 ///
12.275 - /// \brief Count the biconnected components.
12.276 + /// \brief Count the number of bi-node-connected components of an
12.277 + /// undirected graph.
12.278 ///
12.279 - /// This function finds the bi-node-connected components in an undirected
12.280 - /// graph. The biconnected components are the classes of an equivalence
12.281 - /// relation on the undirected edges. Two undirected edge is in relationship
12.282 - /// when they are on same circle.
12.283 + /// This function counts the number of bi-node-connected components of
12.284 + /// the given undirected graph.
12.285 ///
12.286 - /// \param graph The graph.
12.287 - /// \return The number of components.
12.288 + /// The bi-node-connected components are the classes of an equivalence
12.289 + /// relation on the edges of a undirected graph. Two edges are in the
12.290 + /// same class if they are on same circle.
12.291 + ///
12.292 + /// \return The number of bi-node-connected components.
12.293 + ///
12.294 + /// \see biNodeConnected(), biNodeConnectedComponents()
12.295 template <typename Graph>
12.296 int countBiNodeConnectedComponents(const Graph& graph) {
12.297 checkConcept<concepts::Graph, Graph>();
12.298 @@ -756,22 +797,26 @@
12.299
12.300 /// \ingroup graph_properties
12.301 ///
12.302 - /// \brief Find the bi-node-connected components.
12.303 + /// \brief Find the bi-node-connected components of an undirected graph.
12.304 ///
12.305 - /// This function finds the bi-node-connected components in an undirected
12.306 - /// graph. The bi-node-connected components are the classes of an equivalence
12.307 - /// relation on the undirected edges. Two undirected edge are in relationship
12.308 - /// when they are on same circle.
12.309 + /// This function finds the bi-node-connected components of the given
12.310 + /// undirected graph.
12.311 + ///
12.312 + /// The bi-node-connected components are the classes of an equivalence
12.313 + /// relation on the edges of a undirected graph. Two edges are in the
12.314 + /// same class if they are on same circle.
12.315 ///
12.316 /// \image html node_biconnected_components.png
12.317 /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
12.318 ///
12.319 - /// \param graph The graph.
12.320 - /// \retval compMap A writable uedge map. The values will be set from 0
12.321 - /// to the number of the biconnected components minus one. Each values
12.322 - /// of the map will be set exactly once, the values of a certain component
12.323 - /// will be set continuously.
12.324 - /// \return The number of components.
12.325 + /// \param graph The undirected graph.
12.326 + /// \retval compMap A writable edge map. The values will be set from 0
12.327 + /// to the number of the bi-node-connected components minus one. Each
12.328 + /// value of the map will be set exactly once, and the values of a
12.329 + /// certain component will be set continuously.
12.330 + /// \return The number of bi-node-connected components.
12.331 + ///
12.332 + /// \see biNodeConnected(), countBiNodeConnectedComponents()
12.333 template <typename Graph, typename EdgeMap>
12.334 int biNodeConnectedComponents(const Graph& graph,
12.335 EdgeMap& compMap) {
12.336 @@ -801,18 +846,25 @@
12.337
12.338 /// \ingroup graph_properties
12.339 ///
12.340 - /// \brief Find the bi-node-connected cut nodes.
12.341 + /// \brief Find the bi-node-connected cut nodes in an undirected graph.
12.342 ///
12.343 - /// This function finds the bi-node-connected cut nodes in an undirected
12.344 - /// graph. The bi-node-connected components are the classes of an equivalence
12.345 - /// relation on the undirected edges. Two undirected edges are in
12.346 - /// relationship when they are on same circle. The biconnected components
12.347 - /// are separted by nodes which are the cut nodes of the components.
12.348 + /// This function finds the bi-node-connected cut nodes in the given
12.349 + /// undirected graph.
12.350 ///
12.351 - /// \param graph The graph.
12.352 - /// \retval cutMap A writable edge map. The values will be set true when
12.353 - /// the node separate two or more components.
12.354 + /// The bi-node-connected components are the classes of an equivalence
12.355 + /// relation on the edges of a undirected graph. Two edges are in the
12.356 + /// same class if they are on same circle.
12.357 + /// The bi-node-connected components are separted by the cut nodes of
12.358 + /// the components.
12.359 + ///
12.360 + /// \param graph The undirected graph.
12.361 + /// \retval cutMap A writable node map. The values will be set to
12.362 + /// \c true for the nodes that separate two or more components
12.363 + /// (exactly once for each cut node), and will not be changed for
12.364 + /// other nodes.
12.365 /// \return The number of the cut nodes.
12.366 + ///
12.367 + /// \see biNodeConnected(), biNodeConnectedComponents()
12.368 template <typename Graph, typename NodeMap>
12.369 int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {
12.370 checkConcept<concepts::Graph, Graph>();
12.371 @@ -1031,14 +1083,16 @@
12.372
12.373 /// \ingroup graph_properties
12.374 ///
12.375 - /// \brief Checks that the graph is bi-edge-connected.
12.376 + /// \brief Check whether an undirected graph is bi-edge-connected.
12.377 ///
12.378 - /// This function checks that the graph is bi-edge-connected. The undirected
12.379 - /// graph is bi-edge-connected when any two nodes are connected with two
12.380 - /// edge-disjoint paths.
12.381 + /// This function checks whether the given undirected graph is
12.382 + /// bi-edge-connected, i.e. any two nodes are connected with at least
12.383 + /// two edge-disjoint paths.
12.384 ///
12.385 - /// \param graph The undirected graph.
12.386 - /// \return The number of components.
12.387 + /// \return \c true if the graph is bi-edge-connected.
12.388 + /// \note By definition, the empty graph is bi-edge-connected.
12.389 + ///
12.390 + /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents()
12.391 template <typename Graph>
12.392 bool biEdgeConnected(const Graph& graph) {
12.393 return countBiEdgeConnectedComponents(graph) <= 1;
12.394 @@ -1046,15 +1100,20 @@
12.395
12.396 /// \ingroup graph_properties
12.397 ///
12.398 - /// \brief Count the bi-edge-connected components.
12.399 + /// \brief Count the number of bi-edge-connected components of an
12.400 + /// undirected graph.
12.401 ///
12.402 - /// This function count the bi-edge-connected components in an undirected
12.403 - /// graph. The bi-edge-connected components are the classes of an equivalence
12.404 - /// relation on the nodes. Two nodes are in relationship when they are
12.405 - /// connected with at least two edge-disjoint paths.
12.406 + /// This function counts the number of bi-edge-connected components of
12.407 + /// the given undirected graph.
12.408 ///
12.409 - /// \param graph The undirected graph.
12.410 - /// \return The number of components.
12.411 + /// The bi-edge-connected components are the classes of an equivalence
12.412 + /// relation on the nodes of an undirected graph. Two nodes are in the
12.413 + /// same class if they are connected with at least two edge-disjoint
12.414 + /// paths.
12.415 + ///
12.416 + /// \return The number of bi-edge-connected components.
12.417 + ///
12.418 + /// \see biEdgeConnected(), biEdgeConnectedComponents()
12.419 template <typename Graph>
12.420 int countBiEdgeConnectedComponents(const Graph& graph) {
12.421 checkConcept<concepts::Graph, Graph>();
12.422 @@ -1081,22 +1140,27 @@
12.423
12.424 /// \ingroup graph_properties
12.425 ///
12.426 - /// \brief Find the bi-edge-connected components.
12.427 + /// \brief Find the bi-edge-connected components of an undirected graph.
12.428 ///
12.429 - /// This function finds the bi-edge-connected components in an undirected
12.430 - /// graph. The bi-edge-connected components are the classes of an equivalence
12.431 - /// relation on the nodes. Two nodes are in relationship when they are
12.432 - /// connected at least two edge-disjoint paths.
12.433 + /// This function finds the bi-edge-connected components of the given
12.434 + /// undirected graph.
12.435 + ///
12.436 + /// The bi-edge-connected components are the classes of an equivalence
12.437 + /// relation on the nodes of an undirected graph. Two nodes are in the
12.438 + /// same class if they are connected with at least two edge-disjoint
12.439 + /// paths.
12.440 ///
12.441 /// \image html edge_biconnected_components.png
12.442 /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
12.443 ///
12.444 - /// \param graph The graph.
12.445 + /// \param graph The undirected graph.
12.446 /// \retval compMap A writable node map. The values will be set from 0 to
12.447 - /// the number of the biconnected components minus one. Each values
12.448 - /// of the map will be set exactly once, the values of a certain component
12.449 - /// will be set continuously.
12.450 - /// \return The number of components.
12.451 + /// the number of the bi-edge-connected components minus one. Each value
12.452 + /// of the map will be set exactly once, and the values of a certain
12.453 + /// component will be set continuously.
12.454 + /// \return The number of bi-edge-connected components.
12.455 + ///
12.456 + /// \see biEdgeConnected(), countBiEdgeConnectedComponents()
12.457 template <typename Graph, typename NodeMap>
12.458 int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
12.459 checkConcept<concepts::Graph, Graph>();
12.460 @@ -1125,19 +1189,25 @@
12.461
12.462 /// \ingroup graph_properties
12.463 ///
12.464 - /// \brief Find the bi-edge-connected cut edges.
12.465 + /// \brief Find the bi-edge-connected cut edges in an undirected graph.
12.466 ///
12.467 - /// This function finds the bi-edge-connected components in an undirected
12.468 - /// graph. The bi-edge-connected components are the classes of an equivalence
12.469 - /// relation on the nodes. Two nodes are in relationship when they are
12.470 - /// connected with at least two edge-disjoint paths. The bi-edge-connected
12.471 - /// components are separted by edges which are the cut edges of the
12.472 - /// components.
12.473 + /// This function finds the bi-edge-connected cut edges in the given
12.474 + /// undirected graph.
12.475 ///
12.476 - /// \param graph The graph.
12.477 - /// \retval cutMap A writable node map. The values will be set true when the
12.478 - /// edge is a cut edge.
12.479 + /// The bi-edge-connected components are the classes of an equivalence
12.480 + /// relation on the nodes of an undirected graph. Two nodes are in the
12.481 + /// same class if they are connected with at least two edge-disjoint
12.482 + /// paths.
12.483 + /// The bi-edge-connected components are separted by the cut edges of
12.484 + /// the components.
12.485 + ///
12.486 + /// \param graph The undirected graph.
12.487 + /// \retval cutMap A writable edge map. The values will be set to \c true
12.488 + /// for the cut edges (exactly once for each cut edge), and will not be
12.489 + /// changed for other edges.
12.490 /// \return The number of cut edges.
12.491 + ///
12.492 + /// \see biEdgeConnected(), biEdgeConnectedComponents()
12.493 template <typename Graph, typename EdgeMap>
12.494 int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
12.495 checkConcept<concepts::Graph, Graph>();
12.496 @@ -1189,19 +1259,62 @@
12.497
12.498 /// \ingroup graph_properties
12.499 ///
12.500 + /// \brief Check whether a digraph is DAG.
12.501 + ///
12.502 + /// This function checks whether the given digraph is DAG, i.e.
12.503 + /// \e Directed \e Acyclic \e Graph.
12.504 + /// \return \c true if there is no directed cycle in the digraph.
12.505 + /// \see acyclic()
12.506 + template <typename Digraph>
12.507 + bool dag(const Digraph& digraph) {
12.508 +
12.509 + checkConcept<concepts::Digraph, Digraph>();
12.510 +
12.511 + typedef typename Digraph::Node Node;
12.512 + typedef typename Digraph::NodeIt NodeIt;
12.513 + typedef typename Digraph::Arc Arc;
12.514 +
12.515 + typedef typename Digraph::template NodeMap<bool> ProcessedMap;
12.516 +
12.517 + typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
12.518 + Create dfs(digraph);
12.519 +
12.520 + ProcessedMap processed(digraph);
12.521 + dfs.processedMap(processed);
12.522 +
12.523 + dfs.init();
12.524 + for (NodeIt it(digraph); it != INVALID; ++it) {
12.525 + if (!dfs.reached(it)) {
12.526 + dfs.addSource(it);
12.527 + while (!dfs.emptyQueue()) {
12.528 + Arc arc = dfs.nextArc();
12.529 + Node target = digraph.target(arc);
12.530 + if (dfs.reached(target) && !processed[target]) {
12.531 + return false;
12.532 + }
12.533 + dfs.processNextArc();
12.534 + }
12.535 + }
12.536 + }
12.537 + return true;
12.538 + }
12.539 +
12.540 + /// \ingroup graph_properties
12.541 + ///
12.542 /// \brief Sort the nodes of a DAG into topolgical order.
12.543 ///
12.544 - /// Sort the nodes of a DAG into topolgical order.
12.545 + /// This function sorts the nodes of the given acyclic digraph (DAG)
12.546 + /// into topolgical order.
12.547 ///
12.548 - /// \param graph The graph. It must be directed and acyclic.
12.549 + /// \param digraph The digraph, which must be DAG.
12.550 /// \retval order A writable node map. The values will be set from 0 to
12.551 - /// the number of the nodes in the graph minus one. Each values of the map
12.552 - /// will be set exactly once, the values will be set descending order.
12.553 + /// the number of the nodes in the digraph minus one. Each value of the
12.554 + /// map will be set exactly once, and the values will be set descending
12.555 + /// order.
12.556 ///
12.557 - /// \see checkedTopologicalSort
12.558 - /// \see dag
12.559 + /// \see dag(), checkedTopologicalSort()
12.560 template <typename Digraph, typename NodeMap>
12.561 - void topologicalSort(const Digraph& graph, NodeMap& order) {
12.562 + void topologicalSort(const Digraph& digraph, NodeMap& order) {
12.563 using namespace _connectivity_bits;
12.564
12.565 checkConcept<concepts::Digraph, Digraph>();
12.566 @@ -1212,13 +1325,13 @@
12.567 typedef typename Digraph::Arc Arc;
12.568
12.569 TopologicalSortVisitor<Digraph, NodeMap>
12.570 - visitor(order, countNodes(graph));
12.571 + visitor(order, countNodes(digraph));
12.572
12.573 DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
12.574 - dfs(graph, visitor);
12.575 + dfs(digraph, visitor);
12.576
12.577 dfs.init();
12.578 - for (NodeIt it(graph); it != INVALID; ++it) {
12.579 + for (NodeIt it(digraph); it != INVALID; ++it) {
12.580 if (!dfs.reached(it)) {
12.581 dfs.addSource(it);
12.582 dfs.start();
12.583 @@ -1230,18 +1343,18 @@
12.584 ///
12.585 /// \brief Sort the nodes of a DAG into topolgical order.
12.586 ///
12.587 - /// Sort the nodes of a DAG into topolgical order. It also checks
12.588 - /// that the given graph is DAG.
12.589 + /// This function sorts the nodes of the given acyclic digraph (DAG)
12.590 + /// into topolgical order and also checks whether the given digraph
12.591 + /// is DAG.
12.592 ///
12.593 - /// \param digraph The graph. It must be directed and acyclic.
12.594 - /// \retval order A readable - writable node map. The values will be set
12.595 - /// from 0 to the number of the nodes in the graph minus one. Each values
12.596 - /// of the map will be set exactly once, the values will be set descending
12.597 - /// order.
12.598 - /// \return \c false when the graph is not DAG.
12.599 + /// \param digraph The digraph.
12.600 + /// \retval order A readable and writable node map. The values will be
12.601 + /// set from 0 to the number of the nodes in the digraph minus one.
12.602 + /// Each value of the map will be set exactly once, and the values will
12.603 + /// be set descending order.
12.604 + /// \return \c false if the digraph is not DAG.
12.605 ///
12.606 - /// \see topologicalSort
12.607 - /// \see dag
12.608 + /// \see dag(), topologicalSort()
12.609 template <typename Digraph, typename NodeMap>
12.610 bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
12.611 using namespace _connectivity_bits;
12.612 @@ -1283,54 +1396,11 @@
12.613
12.614 /// \ingroup graph_properties
12.615 ///
12.616 - /// \brief Check that the given directed graph is a DAG.
12.617 + /// \brief Check whether an undirected graph is acyclic.
12.618 ///
12.619 - /// Check that the given directed graph is a DAG. The DAG is
12.620 - /// an Directed Acyclic Digraph.
12.621 - /// \return \c false when the graph is not DAG.
12.622 - /// \see acyclic
12.623 - template <typename Digraph>
12.624 - bool dag(const Digraph& digraph) {
12.625 -
12.626 - checkConcept<concepts::Digraph, Digraph>();
12.627 -
12.628 - typedef typename Digraph::Node Node;
12.629 - typedef typename Digraph::NodeIt NodeIt;
12.630 - typedef typename Digraph::Arc Arc;
12.631 -
12.632 - typedef typename Digraph::template NodeMap<bool> ProcessedMap;
12.633 -
12.634 - typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
12.635 - Create dfs(digraph);
12.636 -
12.637 - ProcessedMap processed(digraph);
12.638 - dfs.processedMap(processed);
12.639 -
12.640 - dfs.init();
12.641 - for (NodeIt it(digraph); it != INVALID; ++it) {
12.642 - if (!dfs.reached(it)) {
12.643 - dfs.addSource(it);
12.644 - while (!dfs.emptyQueue()) {
12.645 - Arc edge = dfs.nextArc();
12.646 - Node target = digraph.target(edge);
12.647 - if (dfs.reached(target) && !processed[target]) {
12.648 - return false;
12.649 - }
12.650 - dfs.processNextArc();
12.651 - }
12.652 - }
12.653 - }
12.654 - return true;
12.655 - }
12.656 -
12.657 - /// \ingroup graph_properties
12.658 - ///
12.659 - /// \brief Check that the given undirected graph is acyclic.
12.660 - ///
12.661 - /// Check that the given undirected graph acyclic.
12.662 - /// \param graph The undirected graph.
12.663 - /// \return \c true when there is no circle in the graph.
12.664 - /// \see dag
12.665 + /// This function checks whether the given undirected graph is acyclic.
12.666 + /// \return \c true if there is no cycle in the graph.
12.667 + /// \see dag()
12.668 template <typename Graph>
12.669 bool acyclic(const Graph& graph) {
12.670 checkConcept<concepts::Graph, Graph>();
12.671 @@ -1343,11 +1413,11 @@
12.672 if (!dfs.reached(it)) {
12.673 dfs.addSource(it);
12.674 while (!dfs.emptyQueue()) {
12.675 - Arc edge = dfs.nextArc();
12.676 - Node source = graph.source(edge);
12.677 - Node target = graph.target(edge);
12.678 + Arc arc = dfs.nextArc();
12.679 + Node source = graph.source(arc);
12.680 + Node target = graph.target(arc);
12.681 if (dfs.reached(target) &&
12.682 - dfs.predArc(source) != graph.oppositeArc(edge)) {
12.683 + dfs.predArc(source) != graph.oppositeArc(arc)) {
12.684 return false;
12.685 }
12.686 dfs.processNextArc();
12.687 @@ -1359,26 +1429,27 @@
12.688
12.689 /// \ingroup graph_properties
12.690 ///
12.691 - /// \brief Check that the given undirected graph is tree.
12.692 + /// \brief Check whether an undirected graph is tree.
12.693 ///
12.694 - /// Check that the given undirected graph is tree.
12.695 - /// \param graph The undirected graph.
12.696 - /// \return \c true when the graph is acyclic and connected.
12.697 + /// This function checks whether the given undirected graph is tree.
12.698 + /// \return \c true if the graph is acyclic and connected.
12.699 + /// \see acyclic(), connected()
12.700 template <typename Graph>
12.701 bool tree(const Graph& graph) {
12.702 checkConcept<concepts::Graph, Graph>();
12.703 typedef typename Graph::Node Node;
12.704 typedef typename Graph::NodeIt NodeIt;
12.705 typedef typename Graph::Arc Arc;
12.706 + if (NodeIt(graph) == INVALID) return true;
12.707 Dfs<Graph> dfs(graph);
12.708 dfs.init();
12.709 dfs.addSource(NodeIt(graph));
12.710 while (!dfs.emptyQueue()) {
12.711 - Arc edge = dfs.nextArc();
12.712 - Node source = graph.source(edge);
12.713 - Node target = graph.target(edge);
12.714 + Arc arc = dfs.nextArc();
12.715 + Node source = graph.source(arc);
12.716 + Node target = graph.target(arc);
12.717 if (dfs.reached(target) &&
12.718 - dfs.predArc(source) != graph.oppositeArc(edge)) {
12.719 + dfs.predArc(source) != graph.oppositeArc(arc)) {
12.720 return false;
12.721 }
12.722 dfs.processNextArc();
12.723 @@ -1451,15 +1522,14 @@
12.724
12.725 /// \ingroup graph_properties
12.726 ///
12.727 - /// \brief Check if the given undirected graph is bipartite or not
12.728 + /// \brief Check whether an undirected graph is bipartite.
12.729 ///
12.730 - /// The function checks if the given undirected \c graph graph is bipartite
12.731 - /// or not. The \ref Bfs algorithm is used to calculate the result.
12.732 - /// \param graph The undirected graph.
12.733 - /// \return \c true if \c graph is bipartite, \c false otherwise.
12.734 - /// \sa bipartitePartitions
12.735 + /// The function checks whether the given undirected graph is bipartite.
12.736 + /// \return \c true if the graph is bipartite.
12.737 + ///
12.738 + /// \see bipartitePartitions()
12.739 template<typename Graph>
12.740 - inline bool bipartite(const Graph &graph){
12.741 + bool bipartite(const Graph &graph){
12.742 using namespace _connectivity_bits;
12.743
12.744 checkConcept<concepts::Graph, Graph>();
12.745 @@ -1488,25 +1558,27 @@
12.746
12.747 /// \ingroup graph_properties
12.748 ///
12.749 - /// \brief Check if the given undirected graph is bipartite or not
12.750 + /// \brief Find the bipartite partitions of an undirected graph.
12.751 ///
12.752 - /// The function checks if the given undirected graph is bipartite
12.753 - /// or not. The \ref Bfs algorithm is used to calculate the result.
12.754 - /// During the execution, the \c partMap will be set as the two
12.755 - /// partitions of the graph.
12.756 + /// This function checks whether the given undirected graph is bipartite
12.757 + /// and gives back the bipartite partitions.
12.758 ///
12.759 /// \image html bipartite_partitions.png
12.760 /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
12.761 ///
12.762 /// \param graph The undirected graph.
12.763 - /// \retval partMap A writable bool map of nodes. It will be set as the
12.764 - /// two partitions of the graph.
12.765 - /// \return \c true if \c graph is bipartite, \c false otherwise.
12.766 + /// \retval partMap A writable node map of \c bool (or convertible) value
12.767 + /// type. The values will be set to \c true for one component and
12.768 + /// \c false for the other one.
12.769 + /// \return \c true if the graph is bipartite, \c false otherwise.
12.770 + ///
12.771 + /// \see bipartite()
12.772 template<typename Graph, typename NodeMap>
12.773 - inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
12.774 + bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
12.775 using namespace _connectivity_bits;
12.776
12.777 checkConcept<concepts::Graph, Graph>();
12.778 + checkConcept<concepts::WriteMap<typename Graph::Node, bool>, NodeMap>();
12.779
12.780 typedef typename Graph::Node Node;
12.781 typedef typename Graph::NodeIt NodeIt;
12.782 @@ -1531,53 +1603,59 @@
12.783 return true;
12.784 }
12.785
12.786 - /// \brief Returns true when there are not loop edges in the graph.
12.787 + /// \ingroup graph_properties
12.788 ///
12.789 - /// Returns true when there are not loop edges in the graph.
12.790 - template <typename Digraph>
12.791 - bool loopFree(const Digraph& digraph) {
12.792 - for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) {
12.793 - if (digraph.source(it) == digraph.target(it)) return false;
12.794 + /// \brief Check whether the given graph contains no loop arcs/edges.
12.795 + ///
12.796 + /// This function returns \c true if there are no loop arcs/edges in
12.797 + /// the given graph. It works for both directed and undirected graphs.
12.798 + template <typename Graph>
12.799 + bool loopFree(const Graph& graph) {
12.800 + for (typename Graph::ArcIt it(graph); it != INVALID; ++it) {
12.801 + if (graph.source(it) == graph.target(it)) return false;
12.802 }
12.803 return true;
12.804 }
12.805
12.806 - /// \brief Returns true when there are not parallel edges in the graph.
12.807 + /// \ingroup graph_properties
12.808 ///
12.809 - /// Returns true when there are not parallel edges in the graph.
12.810 - template <typename Digraph>
12.811 - bool parallelFree(const Digraph& digraph) {
12.812 - typename Digraph::template NodeMap<bool> reached(digraph, false);
12.813 - for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
12.814 - for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
12.815 - if (reached[digraph.target(a)]) return false;
12.816 - reached.set(digraph.target(a), true);
12.817 + /// \brief Check whether the given graph contains no parallel arcs/edges.
12.818 + ///
12.819 + /// This function returns \c true if there are no parallel arcs/edges in
12.820 + /// the given graph. It works for both directed and undirected graphs.
12.821 + template <typename Graph>
12.822 + bool parallelFree(const Graph& graph) {
12.823 + typename Graph::template NodeMap<int> reached(graph, 0);
12.824 + int cnt = 1;
12.825 + for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
12.826 + for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
12.827 + if (reached[graph.target(a)] == cnt) return false;
12.828 + reached[graph.target(a)] = cnt;
12.829 }
12.830 - for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
12.831 - reached.set(digraph.target(a), false);
12.832 - }
12.833 + ++cnt;
12.834 }
12.835 return true;
12.836 }
12.837
12.838 - /// \brief Returns true when there are not loop edges and parallel
12.839 - /// edges in the graph.
12.840 + /// \ingroup graph_properties
12.841 ///
12.842 - /// Returns true when there are not loop edges and parallel edges in
12.843 - /// the graph.
12.844 - template <typename Digraph>
12.845 - bool simpleDigraph(const Digraph& digraph) {
12.846 - typename Digraph::template NodeMap<bool> reached(digraph, false);
12.847 - for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
12.848 - reached.set(n, true);
12.849 - for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
12.850 - if (reached[digraph.target(a)]) return false;
12.851 - reached.set(digraph.target(a), true);
12.852 + /// \brief Check whether the given graph is simple.
12.853 + ///
12.854 + /// This function returns \c true if the given graph is simple, i.e.
12.855 + /// it contains no loop arcs/edges and no parallel arcs/edges.
12.856 + /// The function works for both directed and undirected graphs.
12.857 + /// \see loopFree(), parallelFree()
12.858 + template <typename Graph>
12.859 + bool simpleGraph(const Graph& graph) {
12.860 + typename Graph::template NodeMap<int> reached(graph, 0);
12.861 + int cnt = 1;
12.862 + for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
12.863 + reached[n] = cnt;
12.864 + for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
12.865 + if (reached[graph.target(a)] == cnt) return false;
12.866 + reached[graph.target(a)] = cnt;
12.867 }
12.868 - for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
12.869 - reached.set(digraph.target(a), false);
12.870 - }
12.871 - reached.set(n, false);
12.872 + ++cnt;
12.873 }
12.874 return true;
12.875 }
13.1 --- a/lemon/edge_set.h Thu May 07 02:05:12 2009 +0200
13.2 +++ b/lemon/edge_set.h Tue May 12 12:09:55 2009 +0100
13.3 @@ -22,7 +22,7 @@
13.4 #include <lemon/core.h>
13.5 #include <lemon/bits/edge_set_extender.h>
13.6
13.7 -/// \ingroup semi_adaptors
13.8 +/// \ingroup graphs
13.9 /// \file
13.10 /// \brief ArcSet and EdgeSet classes.
13.11 ///
13.12 @@ -230,7 +230,7 @@
13.13
13.14 };
13.15
13.16 - /// \ingroup semi_adaptors
13.17 + /// \ingroup graphs
13.18 ///
13.19 /// \brief Digraph using a node set of another digraph or graph and
13.20 /// an own arc set.
13.21 @@ -654,7 +654,7 @@
13.22
13.23 };
13.24
13.25 - /// \ingroup semi_adaptors
13.26 + /// \ingroup graphs
13.27 ///
13.28 /// \brief Graph using a node set of another digraph or graph and an
13.29 /// own edge set.
13.30 @@ -913,7 +913,7 @@
13.31 };
13.32
13.33
13.34 - /// \ingroup semi_adaptors
13.35 + /// \ingroup graphs
13.36 ///
13.37 /// \brief Digraph using a node set of another digraph or graph and
13.38 /// an own arc set.
13.39 @@ -1257,7 +1257,7 @@
13.40
13.41 };
13.42
13.43 - /// \ingroup semi_adaptors
13.44 + /// \ingroup graphs
13.45 ///
13.46 /// \brief Graph using a node set of another digraph or graph and an
13.47 /// own edge set.
14.1 --- a/lemon/euler.h Thu May 07 02:05:12 2009 +0200
14.2 +++ b/lemon/euler.h Tue May 12 12:09:55 2009 +0100
14.3 @@ -244,10 +244,10 @@
14.4 };
14.5
14.6
14.7 - ///Check if the given graph is \e Eulerian
14.8 + ///Check if the given graph is Eulerian
14.9
14.10 /// \ingroup graph_properties
14.11 - ///This function checks if the given graph is \e Eulerian.
14.12 + ///This function checks if the given graph is Eulerian.
14.13 ///It works for both directed and undirected graphs.
14.14 ///
14.15 ///By definition, a digraph is called \e Eulerian if
15.1 --- a/lemon/glpk.h Thu May 07 02:05:12 2009 +0200
15.2 +++ b/lemon/glpk.h Tue May 12 12:09:55 2009 +0100
15.3 @@ -26,9 +26,10 @@
15.4 #include <lemon/lp_base.h>
15.5
15.6 // forward declaration
15.7 -#ifndef _GLP_PROB
15.8 +#if !defined _GLP_PROB && !defined GLP_PROB
15.9 #define _GLP_PROB
15.10 -typedef struct { double _prob; } glp_prob;
15.11 +#define GLP_PROB
15.12 +typedef struct { double _opaque_prob; } glp_prob;
15.13 /* LP/MIP problem object */
15.14 #endif
15.15
16.1 --- a/lemon/lemon.pc.in Thu May 07 02:05:12 2009 +0200
16.2 +++ b/lemon/lemon.pc.in Tue May 12 12:09:55 2009 +0100
16.3 @@ -4,7 +4,7 @@
16.4 includedir=@includedir@
16.5
16.6 Name: @PACKAGE_NAME@
16.7 -Description: Library of Efficient Models and Optimization in Networks
16.8 +Description: Library for Efficient Modeling and Optimization in Networks
16.9 Version: @PACKAGE_VERSION@
16.10 Libs: -L${libdir} -lemon @GLPK_LIBS@ @CPLEX_LIBS@ @SOPLEX_LIBS@ @CLP_LIBS@ @CBC_LIBS@
16.11 Cflags: -I${includedir}
17.1 --- a/lemon/matching.h Thu May 07 02:05:12 2009 +0200
17.2 +++ b/lemon/matching.h Tue May 12 12:09:55 2009 +0100
17.3 @@ -499,7 +499,7 @@
17.4 ///
17.5 /// This function runs the original Edmonds' algorithm.
17.6 ///
17.7 - /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be
17.8 + /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be
17.9 /// called before using this function.
17.10 void startSparse() {
17.11 for(NodeIt n(_graph); n != INVALID; ++n) {
17.12 @@ -518,7 +518,7 @@
17.13 /// This function runs Edmonds' algorithm with a heuristic of postponing
17.14 /// shrinks, therefore resulting in a faster algorithm for dense graphs.
17.15 ///
17.16 - /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be
17.17 + /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be
17.18 /// called before using this function.
17.19 void startDense() {
17.20 for(NodeIt n(_graph); n != INVALID; ++n) {
18.1 --- a/lemon/network_simplex.h Thu May 07 02:05:12 2009 +0200
18.2 +++ b/lemon/network_simplex.h Tue May 12 12:09:55 2009 +0100
18.3 @@ -19,7 +19,7 @@
18.4 #ifndef LEMON_NETWORK_SIMPLEX_H
18.5 #define LEMON_NETWORK_SIMPLEX_H
18.6
18.7 -/// \ingroup min_cost_flow
18.8 +/// \ingroup min_cost_flow_algs
18.9 ///
18.10 /// \file
18.11 /// \brief Network Simplex algorithm for finding a minimum cost flow.
18.12 @@ -33,7 +33,7 @@
18.13
18.14 namespace lemon {
18.15
18.16 - /// \addtogroup min_cost_flow
18.17 + /// \addtogroup min_cost_flow_algs
18.18 /// @{
18.19
18.20 /// \brief Implementation of the primal Network Simplex algorithm
18.21 @@ -102,50 +102,16 @@
18.22 /// i.e. the direction of the inequalities in the supply/demand
18.23 /// constraints of the \ref min_cost_flow "minimum cost flow problem".
18.24 ///
18.25 - /// The default supply type is \c GEQ, since this form is supported
18.26 - /// by other minimum cost flow algorithms and the \ref Circulation
18.27 - /// algorithm, as well.
18.28 - /// The \c LEQ problem type can be selected using the \ref supplyType()
18.29 - /// function.
18.30 - ///
18.31 - /// Note that the equality form is a special case of both supply types.
18.32 + /// The default supply type is \c GEQ, the \c LEQ type can be
18.33 + /// selected using \ref supplyType().
18.34 + /// The equality form is a special case of both supply types.
18.35 enum SupplyType {
18.36 -
18.37 /// This option means that there are <em>"greater or equal"</em>
18.38 - /// supply/demand constraints in the definition, i.e. the exact
18.39 - /// formulation of the problem is the following.
18.40 - /**
18.41 - \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
18.42 - \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
18.43 - sup(u) \quad \forall u\in V \f]
18.44 - \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
18.45 - */
18.46 - /// It means that the total demand must be greater or equal to the
18.47 - /// total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
18.48 - /// negative) and all the supplies have to be carried out from
18.49 - /// the supply nodes, but there could be demands that are not
18.50 - /// satisfied.
18.51 + /// supply/demand constraints in the definition of the problem.
18.52 GEQ,
18.53 - /// It is just an alias for the \c GEQ option.
18.54 - CARRY_SUPPLIES = GEQ,
18.55 -
18.56 /// This option means that there are <em>"less or equal"</em>
18.57 - /// supply/demand constraints in the definition, i.e. the exact
18.58 - /// formulation of the problem is the following.
18.59 - /**
18.60 - \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
18.61 - \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq
18.62 - sup(u) \quad \forall u\in V \f]
18.63 - \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
18.64 - */
18.65 - /// It means that the total demand must be less or equal to the
18.66 - /// total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
18.67 - /// positive) and all the demands have to be satisfied, but there
18.68 - /// could be supplies that are not carried out from the supply
18.69 - /// nodes.
18.70 - LEQ,
18.71 - /// It is just an alias for the \c LEQ option.
18.72 - SATISFY_DEMANDS = LEQ
18.73 + /// supply/demand constraints in the definition of the problem.
18.74 + LEQ
18.75 };
18.76
18.77 /// \brief Constants for selecting the pivot rule.
18.78 @@ -215,6 +181,8 @@
18.79 const GR &_graph;
18.80 int _node_num;
18.81 int _arc_num;
18.82 + int _all_arc_num;
18.83 + int _search_arc_num;
18.84
18.85 // Parameters of the problem
18.86 bool _have_lower;
18.87 @@ -277,7 +245,7 @@
18.88 const IntVector &_state;
18.89 const CostVector &_pi;
18.90 int &_in_arc;
18.91 - int _arc_num;
18.92 + int _search_arc_num;
18.93
18.94 // Pivot rule data
18.95 int _next_arc;
18.96 @@ -288,13 +256,14 @@
18.97 FirstEligiblePivotRule(NetworkSimplex &ns) :
18.98 _source(ns._source), _target(ns._target),
18.99 _cost(ns._cost), _state(ns._state), _pi(ns._pi),
18.100 - _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0)
18.101 + _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),
18.102 + _next_arc(0)
18.103 {}
18.104
18.105 // Find next entering arc
18.106 bool findEnteringArc() {
18.107 Cost c;
18.108 - for (int e = _next_arc; e < _arc_num; ++e) {
18.109 + for (int e = _next_arc; e < _search_arc_num; ++e) {
18.110 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
18.111 if (c < 0) {
18.112 _in_arc = e;
18.113 @@ -328,7 +297,7 @@
18.114 const IntVector &_state;
18.115 const CostVector &_pi;
18.116 int &_in_arc;
18.117 - int _arc_num;
18.118 + int _search_arc_num;
18.119
18.120 public:
18.121
18.122 @@ -336,13 +305,13 @@
18.123 BestEligiblePivotRule(NetworkSimplex &ns) :
18.124 _source(ns._source), _target(ns._target),
18.125 _cost(ns._cost), _state(ns._state), _pi(ns._pi),
18.126 - _in_arc(ns.in_arc), _arc_num(ns._arc_num)
18.127 + _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num)
18.128 {}
18.129
18.130 // Find next entering arc
18.131 bool findEnteringArc() {
18.132 Cost c, min = 0;
18.133 - for (int e = 0; e < _arc_num; ++e) {
18.134 + for (int e = 0; e < _search_arc_num; ++e) {
18.135 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
18.136 if (c < min) {
18.137 min = c;
18.138 @@ -367,7 +336,7 @@
18.139 const IntVector &_state;
18.140 const CostVector &_pi;
18.141 int &_in_arc;
18.142 - int _arc_num;
18.143 + int _search_arc_num;
18.144
18.145 // Pivot rule data
18.146 int _block_size;
18.147 @@ -379,14 +348,15 @@
18.148 BlockSearchPivotRule(NetworkSimplex &ns) :
18.149 _source(ns._source), _target(ns._target),
18.150 _cost(ns._cost), _state(ns._state), _pi(ns._pi),
18.151 - _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0)
18.152 + _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),
18.153 + _next_arc(0)
18.154 {
18.155 // The main parameters of the pivot rule
18.156 - const double BLOCK_SIZE_FACTOR = 2.0;
18.157 + const double BLOCK_SIZE_FACTOR = 0.5;
18.158 const int MIN_BLOCK_SIZE = 10;
18.159
18.160 _block_size = std::max( int(BLOCK_SIZE_FACTOR *
18.161 - std::sqrt(double(_arc_num))),
18.162 + std::sqrt(double(_search_arc_num))),
18.163 MIN_BLOCK_SIZE );
18.164 }
18.165
18.166 @@ -395,7 +365,7 @@
18.167 Cost c, min = 0;
18.168 int cnt = _block_size;
18.169 int e, min_arc = _next_arc;
18.170 - for (e = _next_arc; e < _arc_num; ++e) {
18.171 + for (e = _next_arc; e < _search_arc_num; ++e) {
18.172 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
18.173 if (c < min) {
18.174 min = c;
18.175 @@ -440,7 +410,7 @@
18.176 const IntVector &_state;
18.177 const CostVector &_pi;
18.178 int &_in_arc;
18.179 - int _arc_num;
18.180 + int _search_arc_num;
18.181
18.182 // Pivot rule data
18.183 IntVector _candidates;
18.184 @@ -454,7 +424,8 @@
18.185 CandidateListPivotRule(NetworkSimplex &ns) :
18.186 _source(ns._source), _target(ns._target),
18.187 _cost(ns._cost), _state(ns._state), _pi(ns._pi),
18.188 - _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0)
18.189 + _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),
18.190 + _next_arc(0)
18.191 {
18.192 // The main parameters of the pivot rule
18.193 const double LIST_LENGTH_FACTOR = 1.0;
18.194 @@ -463,7 +434,7 @@
18.195 const int MIN_MINOR_LIMIT = 3;
18.196
18.197 _list_length = std::max( int(LIST_LENGTH_FACTOR *
18.198 - std::sqrt(double(_arc_num))),
18.199 + std::sqrt(double(_search_arc_num))),
18.200 MIN_LIST_LENGTH );
18.201 _minor_limit = std::max( int(MINOR_LIMIT_FACTOR * _list_length),
18.202 MIN_MINOR_LIMIT );
18.203 @@ -500,7 +471,7 @@
18.204 // Major iteration: build a new candidate list
18.205 min = 0;
18.206 _curr_length = 0;
18.207 - for (e = _next_arc; e < _arc_num; ++e) {
18.208 + for (e = _next_arc; e < _search_arc_num; ++e) {
18.209 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
18.210 if (c < 0) {
18.211 _candidates[_curr_length++] = e;
18.212 @@ -546,7 +517,7 @@
18.213 const IntVector &_state;
18.214 const CostVector &_pi;
18.215 int &_in_arc;
18.216 - int _arc_num;
18.217 + int _search_arc_num;
18.218
18.219 // Pivot rule data
18.220 int _block_size, _head_length, _curr_length;
18.221 @@ -574,8 +545,8 @@
18.222 AlteringListPivotRule(NetworkSimplex &ns) :
18.223 _source(ns._source), _target(ns._target),
18.224 _cost(ns._cost), _state(ns._state), _pi(ns._pi),
18.225 - _in_arc(ns.in_arc), _arc_num(ns._arc_num),
18.226 - _next_arc(0), _cand_cost(ns._arc_num), _sort_func(_cand_cost)
18.227 + _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),
18.228 + _next_arc(0), _cand_cost(ns._search_arc_num), _sort_func(_cand_cost)
18.229 {
18.230 // The main parameters of the pivot rule
18.231 const double BLOCK_SIZE_FACTOR = 1.5;
18.232 @@ -584,7 +555,7 @@
18.233 const int MIN_HEAD_LENGTH = 3;
18.234
18.235 _block_size = std::max( int(BLOCK_SIZE_FACTOR *
18.236 - std::sqrt(double(_arc_num))),
18.237 + std::sqrt(double(_search_arc_num))),
18.238 MIN_BLOCK_SIZE );
18.239 _head_length = std::max( int(HEAD_LENGTH_FACTOR * _block_size),
18.240 MIN_HEAD_LENGTH );
18.241 @@ -610,7 +581,7 @@
18.242 int last_arc = 0;
18.243 int limit = _head_length;
18.244
18.245 - for (int e = _next_arc; e < _arc_num; ++e) {
18.246 + for (int e = _next_arc; e < _search_arc_num; ++e) {
18.247 _cand_cost[e] = _state[e] *
18.248 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
18.249 if (_cand_cost[e] < 0) {
18.250 @@ -678,17 +649,17 @@
18.251 _node_num = countNodes(_graph);
18.252 _arc_num = countArcs(_graph);
18.253 int all_node_num = _node_num + 1;
18.254 - int all_arc_num = _arc_num + _node_num;
18.255 + int max_arc_num = _arc_num + 2 * _node_num;
18.256
18.257 - _source.resize(all_arc_num);
18.258 - _target.resize(all_arc_num);
18.259 + _source.resize(max_arc_num);
18.260 + _target.resize(max_arc_num);
18.261
18.262 - _lower.resize(all_arc_num);
18.263 - _upper.resize(all_arc_num);
18.264 - _cap.resize(all_arc_num);
18.265 - _cost.resize(all_arc_num);
18.266 + _lower.resize(_arc_num);
18.267 + _upper.resize(_arc_num);
18.268 + _cap.resize(max_arc_num);
18.269 + _cost.resize(max_arc_num);
18.270 _supply.resize(all_node_num);
18.271 - _flow.resize(all_arc_num);
18.272 + _flow.resize(max_arc_num);
18.273 _pi.resize(all_node_num);
18.274
18.275 _parent.resize(all_node_num);
18.276 @@ -698,7 +669,7 @@
18.277 _rev_thread.resize(all_node_num);
18.278 _succ_num.resize(all_node_num);
18.279 _last_succ.resize(all_node_num);
18.280 - _state.resize(all_arc_num);
18.281 + _state.resize(max_arc_num);
18.282
18.283 // Copy the graph (store the arcs in a mixed order)
18.284 int i = 0;
18.285 @@ -1069,7 +1040,7 @@
18.286 // Initialize artifical cost
18.287 Cost ART_COST;
18.288 if (std::numeric_limits<Cost>::is_exact) {
18.289 - ART_COST = std::numeric_limits<Cost>::max() / 4 + 1;
18.290 + ART_COST = std::numeric_limits<Cost>::max() / 2 + 1;
18.291 } else {
18.292 ART_COST = std::numeric_limits<Cost>::min();
18.293 for (int i = 0; i != _arc_num; ++i) {
18.294 @@ -1093,29 +1064,121 @@
18.295 _succ_num[_root] = _node_num + 1;
18.296 _last_succ[_root] = _root - 1;
18.297 _supply[_root] = -_sum_supply;
18.298 - _pi[_root] = _sum_supply < 0 ? -ART_COST : ART_COST;
18.299 + _pi[_root] = 0;
18.300
18.301 // Add artificial arcs and initialize the spanning tree data structure
18.302 - for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
18.303 - _parent[u] = _root;
18.304 - _pred[u] = e;
18.305 - _thread[u] = u + 1;
18.306 - _rev_thread[u + 1] = u;
18.307 - _succ_num[u] = 1;
18.308 - _last_succ[u] = u;
18.309 - _cost[e] = ART_COST;
18.310 - _cap[e] = INF;
18.311 - _state[e] = STATE_TREE;
18.312 - if (_supply[u] > 0 || (_supply[u] == 0 && _sum_supply <= 0)) {
18.313 - _flow[e] = _supply[u];
18.314 - _forward[u] = true;
18.315 - _pi[u] = -ART_COST + _pi[_root];
18.316 - } else {
18.317 - _flow[e] = -_supply[u];
18.318 - _forward[u] = false;
18.319 - _pi[u] = ART_COST + _pi[_root];
18.320 + if (_sum_supply == 0) {
18.321 + // EQ supply constraints
18.322 + _search_arc_num = _arc_num;
18.323 + _all_arc_num = _arc_num + _node_num;
18.324 + for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
18.325 + _parent[u] = _root;
18.326 + _pred[u] = e;
18.327 + _thread[u] = u + 1;
18.328 + _rev_thread[u + 1] = u;
18.329 + _succ_num[u] = 1;
18.330 + _last_succ[u] = u;
18.331 + _cap[e] = INF;
18.332 + _state[e] = STATE_TREE;
18.333 + if (_supply[u] >= 0) {
18.334 + _forward[u] = true;
18.335 + _pi[u] = 0;
18.336 + _source[e] = u;
18.337 + _target[e] = _root;
18.338 + _flow[e] = _supply[u];
18.339 + _cost[e] = 0;
18.340 + } else {
18.341 + _forward[u] = false;
18.342 + _pi[u] = ART_COST;
18.343 + _source[e] = _root;
18.344 + _target[e] = u;
18.345 + _flow[e] = -_supply[u];
18.346 + _cost[e] = ART_COST;
18.347 + }
18.348 }
18.349 }
18.350 + else if (_sum_supply > 0) {
18.351 + // LEQ supply constraints
18.352 + _search_arc_num = _arc_num + _node_num;
18.353 + int f = _arc_num + _node_num;
18.354 + for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
18.355 + _parent[u] = _root;
18.356 + _thread[u] = u + 1;
18.357 + _rev_thread[u + 1] = u;
18.358 + _succ_num[u] = 1;
18.359 + _last_succ[u] = u;
18.360 + if (_supply[u] >= 0) {
18.361 + _forward[u] = true;
18.362 + _pi[u] = 0;
18.363 + _pred[u] = e;
18.364 + _source[e] = u;
18.365 + _target[e] = _root;
18.366 + _cap[e] = INF;
18.367 + _flow[e] = _supply[u];
18.368 + _cost[e] = 0;
18.369 + _state[e] = STATE_TREE;
18.370 + } else {
18.371 + _forward[u] = false;
18.372 + _pi[u] = ART_COST;
18.373 + _pred[u] = f;
18.374 + _source[f] = _root;
18.375 + _target[f] = u;
18.376 + _cap[f] = INF;
18.377 + _flow[f] = -_supply[u];
18.378 + _cost[f] = ART_COST;
18.379 + _state[f] = STATE_TREE;
18.380 + _source[e] = u;
18.381 + _target[e] = _root;
18.382 + _cap[e] = INF;
18.383 + _flow[e] = 0;
18.384 + _cost[e] = 0;
18.385 + _state[e] = STATE_LOWER;
18.386 + ++f;
18.387 + }
18.388 + }
18.389 + _all_arc_num = f;
18.390 + }
18.391 + else {
18.392 + // GEQ supply constraints
18.393 + _search_arc_num = _arc_num + _node_num;
18.394 + int f = _arc_num + _node_num;
18.395 + for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
18.396 + _parent[u] = _root;
18.397 + _thread[u] = u + 1;
18.398 + _rev_thread[u + 1] = u;
18.399 + _succ_num[u] = 1;
18.400 + _last_succ[u] = u;
18.401 + if (_supply[u] <= 0) {
18.402 + _forward[u] = false;
18.403 + _pi[u] = 0;
18.404 + _pred[u] = e;
18.405 + _source[e] = _root;
18.406 + _target[e] = u;
18.407 + _cap[e] = INF;
18.408 + _flow[e] = -_supply[u];
18.409 + _cost[e] = 0;
18.410 + _state[e] = STATE_TREE;
18.411 + } else {
18.412 + _forward[u] = true;
18.413 + _pi[u] = -ART_COST;
18.414 + _pred[u] = f;
18.415 + _source[f] = u;
18.416 + _target[f] = _root;
18.417 + _cap[f] = INF;
18.418 + _flow[f] = _supply[u];
18.419 + _state[f] = STATE_TREE;
18.420 + _cost[f] = ART_COST;
18.421 + _source[e] = _root;
18.422 + _target[e] = u;
18.423 + _cap[e] = INF;
18.424 + _flow[e] = 0;
18.425 + _cost[e] = 0;
18.426 + _state[e] = STATE_LOWER;
18.427 + ++f;
18.428 + }
18.429 + }
18.430 + _all_arc_num = f;
18.431 + }
18.432
18.433 return true;
18.434 }
18.435 @@ -1374,20 +1437,8 @@
18.436 }
18.437
18.438 // Check feasibility
18.439 - if (_sum_supply < 0) {
18.440 - for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
18.441 - if (_supply[u] >= 0 && _flow[e] != 0) return INFEASIBLE;
18.442 - }
18.443 - }
18.444 - else if (_sum_supply > 0) {
18.445 - for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
18.446 - if (_supply[u] <= 0 && _flow[e] != 0) return INFEASIBLE;
18.447 - }
18.448 - }
18.449 - else {
18.450 - for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
18.451 - if (_flow[e] != 0) return INFEASIBLE;
18.452 - }
18.453 + for (int e = _search_arc_num; e != _all_arc_num; ++e) {
18.454 + if (_flow[e] != 0) return INFEASIBLE;
18.455 }
18.456
18.457 // Transform the solution and the supply map to the original form
18.458 @@ -1401,6 +1452,30 @@
18.459 }
18.460 }
18.461 }
18.462 +
18.463 + // Shift potentials to meet the requirements of the GEQ/LEQ type
18.464 + // optimality conditions
18.465 + if (_sum_supply == 0) {
18.466 + if (_stype == GEQ) {
18.467 + Cost max_pot = std::numeric_limits<Cost>::min();
18.468 + for (int i = 0; i != _node_num; ++i) {
18.469 + if (_pi[i] > max_pot) max_pot = _pi[i];
18.470 + }
18.471 + if (max_pot > 0) {
18.472 + for (int i = 0; i != _node_num; ++i)
18.473 + _pi[i] -= max_pot;
18.474 + }
18.475 + } else {
18.476 + Cost min_pot = std::numeric_limits<Cost>::max();
18.477 + for (int i = 0; i != _node_num; ++i) {
18.478 + if (_pi[i] < min_pot) min_pot = _pi[i];
18.479 + }
18.480 + if (min_pot < 0) {
18.481 + for (int i = 0; i != _node_num; ++i)
18.482 + _pi[i] -= min_pot;
18.483 + }
18.484 + }
18.485 + }
18.486
18.487 return OPTIMAL;
18.488 }
19.1 --- a/scripts/unify-sources.sh Thu May 07 02:05:12 2009 +0200
19.2 +++ b/scripts/unify-sources.sh Tue May 12 12:09:55 2009 +0100
19.3 @@ -6,6 +6,10 @@
19.4 function hg_year() {
19.5 if [ -n "$(hg st $1)" ]; then
19.6 echo $YEAR
19.7 + else
19.8 + hg log -l 1 --template='{date|isodate}\n' $1 |
19.9 + cut -d '-' -f 1
19.10 + fi
19.11 }
19.12
19.13 # file enumaration modes
20.1 --- a/test/CMakeLists.txt Thu May 07 02:05:12 2009 +0200
20.2 +++ b/test/CMakeLists.txt Tue May 12 12:09:55 2009 +0100
20.3 @@ -9,6 +9,7 @@
20.4 adaptors_test
20.5 bfs_test
20.6 circulation_test
20.7 + connectivity_test
20.8 counter_test
20.9 dfs_test
20.10 digraph_test
21.1 --- a/test/Makefile.am Thu May 07 02:05:12 2009 +0200
21.2 +++ b/test/Makefile.am Tue May 12 12:09:55 2009 +0100
21.3 @@ -9,6 +9,7 @@
21.4 test/adaptors_test \
21.5 test/bfs_test \
21.6 test/circulation_test \
21.7 + test/connectivity_test \
21.8 test/counter_test \
21.9 test/dfs_test \
21.10 test/digraph_test \
21.11 @@ -54,6 +55,7 @@
21.12 test_bfs_test_SOURCES = test/bfs_test.cc
21.13 test_circulation_test_SOURCES = test/circulation_test.cc
21.14 test_counter_test_SOURCES = test/counter_test.cc
21.15 +test_connectivity_test_SOURCES = test/connectivity_test.cc
21.16 test_dfs_test_SOURCES = test/dfs_test.cc
21.17 test_digraph_test_SOURCES = test/digraph_test.cc
21.18 test_dijkstra_test_SOURCES = test/dijkstra_test.cc
22.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
22.2 +++ b/test/connectivity_test.cc Tue May 12 12:09:55 2009 +0100
22.3 @@ -0,0 +1,297 @@
22.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
22.5 + *
22.6 + * This file is a part of LEMON, a generic C++ optimization library.
22.7 + *
22.8 + * Copyright (C) 2003-2009
22.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
22.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
22.11 + *
22.12 + * Permission to use, modify and distribute this software is granted
22.13 + * provided that this copyright notice appears in all copies. For
22.14 + * precise terms see the accompanying LICENSE file.
22.15 + *
22.16 + * This software is provided "AS IS" with no warranty of any kind,
22.17 + * express or implied, and with no claim as to its suitability for any
22.18 + * purpose.
22.19 + *
22.20 + */
22.21 +
22.22 +#include <lemon/connectivity.h>
22.23 +#include <lemon/list_graph.h>
22.24 +#include <lemon/adaptors.h>
22.25 +
22.26 +#include "test_tools.h"
22.27 +
22.28 +using namespace lemon;
22.29 +
22.30 +
22.31 +int main()
22.32 +{
22.33 + typedef ListDigraph Digraph;
22.34 + typedef Undirector<Digraph> Graph;
22.35 +
22.36 + {
22.37 + Digraph d;
22.38 + Digraph::NodeMap<int> order(d);
22.39 + Graph g(d);
22.40 +
22.41 + check(stronglyConnected(d), "The empty digraph is strongly connected");
22.42 + check(countStronglyConnectedComponents(d) == 0,
22.43 + "The empty digraph has 0 strongly connected component");
22.44 + check(connected(g), "The empty graph is connected");
22.45 + check(countConnectedComponents(g) == 0,
22.46 + "The empty graph has 0 connected component");
22.47 +
22.48 + check(biNodeConnected(g), "The empty graph is bi-node-connected");
22.49 + check(countBiNodeConnectedComponents(g) == 0,
22.50 + "The empty graph has 0 bi-node-connected component");
22.51 + check(biEdgeConnected(g), "The empty graph is bi-edge-connected");
22.52 + check(countBiEdgeConnectedComponents(g) == 0,
22.53 + "The empty graph has 0 bi-edge-connected component");
22.54 +
22.55 + check(dag(d), "The empty digraph is DAG.");
22.56 + check(checkedTopologicalSort(d, order), "The empty digraph is DAG.");
22.57 + check(loopFree(d), "The empty digraph is loop-free.");
22.58 + check(parallelFree(d), "The empty digraph is parallel-free.");
22.59 + check(simpleGraph(d), "The empty digraph is simple.");
22.60 +
22.61 + check(acyclic(g), "The empty graph is acyclic.");
22.62 + check(tree(g), "The empty graph is tree.");
22.63 + check(bipartite(g), "The empty graph is bipartite.");
22.64 + check(loopFree(g), "The empty graph is loop-free.");
22.65 + check(parallelFree(g), "The empty graph is parallel-free.");
22.66 + check(simpleGraph(g), "The empty graph is simple.");
22.67 + }
22.68 +
22.69 + {
22.70 + Digraph d;
22.71 + Digraph::NodeMap<int> order(d);
22.72 + Graph g(d);
22.73 + Digraph::Node n = d.addNode();
22.74 +
22.75 + check(stronglyConnected(d), "This digraph is strongly connected");
22.76 + check(countStronglyConnectedComponents(d) == 1,
22.77 + "This digraph has 1 strongly connected component");
22.78 + check(connected(g), "This graph is connected");
22.79 + check(countConnectedComponents(g) == 1,
22.80 + "This graph has 1 connected component");
22.81 +
22.82 + check(biNodeConnected(g), "This graph is bi-node-connected");
22.83 + check(countBiNodeConnectedComponents(g) == 0,
22.84 + "This graph has 0 bi-node-connected component");
22.85 + check(biEdgeConnected(g), "This graph is bi-edge-connected");
22.86 + check(countBiEdgeConnectedComponents(g) == 1,
22.87 + "This graph has 1 bi-edge-connected component");
22.88 +
22.89 + check(dag(d), "This digraph is DAG.");
22.90 + check(checkedTopologicalSort(d, order), "This digraph is DAG.");
22.91 + check(loopFree(d), "This digraph is loop-free.");
22.92 + check(parallelFree(d), "This digraph is parallel-free.");
22.93 + check(simpleGraph(d), "This digraph is simple.");
22.94 +
22.95 + check(acyclic(g), "This graph is acyclic.");
22.96 + check(tree(g), "This graph is tree.");
22.97 + check(bipartite(g), "This graph is bipartite.");
22.98 + check(loopFree(g), "This graph is loop-free.");
22.99 + check(parallelFree(g), "This graph is parallel-free.");
22.100 + check(simpleGraph(g), "This graph is simple.");
22.101 + }
22.102 +
22.103 + {
22.104 + Digraph d;
22.105 + Digraph::NodeMap<int> order(d);
22.106 + Graph g(d);
22.107 +
22.108 + Digraph::Node n1 = d.addNode();
22.109 + Digraph::Node n2 = d.addNode();
22.110 + Digraph::Node n3 = d.addNode();
22.111 + Digraph::Node n4 = d.addNode();
22.112 + Digraph::Node n5 = d.addNode();
22.113 + Digraph::Node n6 = d.addNode();
22.114 +
22.115 + d.addArc(n1, n3);
22.116 + d.addArc(n3, n2);
22.117 + d.addArc(n2, n1);
22.118 + d.addArc(n4, n2);
22.119 + d.addArc(n4, n3);
22.120 + d.addArc(n5, n6);
22.121 + d.addArc(n6, n5);
22.122 +
22.123 + check(!stronglyConnected(d), "This digraph is not strongly connected");
22.124 + check(countStronglyConnectedComponents(d) == 3,
22.125 + "This digraph has 3 strongly connected components");
22.126 + check(!connected(g), "This graph is not connected");
22.127 + check(countConnectedComponents(g) == 2,
22.128 + "This graph has 2 connected components");
22.129 +
22.130 + check(!dag(d), "This digraph is not DAG.");
22.131 + check(!checkedTopologicalSort(d, order), "This digraph is not DAG.");
22.132 + check(loopFree(d), "This digraph is loop-free.");
22.133 + check(parallelFree(d), "This digraph is parallel-free.");
22.134 + check(simpleGraph(d), "This digraph is simple.");
22.135 +
22.136 + check(!acyclic(g), "This graph is not acyclic.");
22.137 + check(!tree(g), "This graph is not tree.");
22.138 + check(!bipartite(g), "This graph is not bipartite.");
22.139 + check(loopFree(g), "This graph is loop-free.");
22.140 + check(!parallelFree(g), "This graph is not parallel-free.");
22.141 + check(!simpleGraph(g), "This graph is not simple.");
22.142 +
22.143 + d.addArc(n3, n3);
22.144 +
22.145 + check(!loopFree(d), "This digraph is not loop-free.");
22.146 + check(!loopFree(g), "This graph is not loop-free.");
22.147 + check(!simpleGraph(d), "This digraph is not simple.");
22.148 +
22.149 + d.addArc(n3, n2);
22.150 +
22.151 + check(!parallelFree(d), "This digraph is not parallel-free.");
22.152 + }
22.153 +
22.154 + {
22.155 + Digraph d;
22.156 + Digraph::ArcMap<bool> cutarcs(d, false);
22.157 + Graph g(d);
22.158 +
22.159 + Digraph::Node n1 = d.addNode();
22.160 + Digraph::Node n2 = d.addNode();
22.161 + Digraph::Node n3 = d.addNode();
22.162 + Digraph::Node n4 = d.addNode();
22.163 + Digraph::Node n5 = d.addNode();
22.164 + Digraph::Node n6 = d.addNode();
22.165 + Digraph::Node n7 = d.addNode();
22.166 + Digraph::Node n8 = d.addNode();
22.167 +
22.168 + d.addArc(n1, n2);
22.169 + d.addArc(n5, n1);
22.170 + d.addArc(n2, n8);
22.171 + d.addArc(n8, n5);
22.172 + d.addArc(n6, n4);
22.173 + d.addArc(n4, n6);
22.174 + d.addArc(n2, n5);
22.175 + d.addArc(n1, n8);
22.176 + d.addArc(n6, n7);
22.177 + d.addArc(n7, n6);
22.178 +
22.179 + check(!stronglyConnected(d), "This digraph is not strongly connected");
22.180 + check(countStronglyConnectedComponents(d) == 3,
22.181 + "This digraph has 3 strongly connected components");
22.182 + Digraph::NodeMap<int> scomp1(d);
22.183 + check(stronglyConnectedComponents(d, scomp1) == 3,
22.184 + "This digraph has 3 strongly connected components");
22.185 + check(scomp1[n1] != scomp1[n3] && scomp1[n1] != scomp1[n4] &&
22.186 + scomp1[n3] != scomp1[n4], "Wrong stronglyConnectedComponents()");
22.187 + check(scomp1[n1] == scomp1[n2] && scomp1[n1] == scomp1[n5] &&
22.188 + scomp1[n1] == scomp1[n8], "Wrong stronglyConnectedComponents()");
22.189 + check(scomp1[n4] == scomp1[n6] && scomp1[n4] == scomp1[n7],
22.190 + "Wrong stronglyConnectedComponents()");
22.191 + Digraph::ArcMap<bool> scut1(d, false);
22.192 + check(stronglyConnectedCutArcs(d, scut1) == 0,
22.193 + "This digraph has 0 strongly connected cut arc.");
22.194 + for (Digraph::ArcIt a(d); a != INVALID; ++a) {
22.195 + check(!scut1[a], "Wrong stronglyConnectedCutArcs()");
22.196 + }
22.197 +
22.198 + check(!connected(g), "This graph is not connected");
22.199 + check(countConnectedComponents(g) == 3,
22.200 + "This graph has 3 connected components");
22.201 + Graph::NodeMap<int> comp(g);
22.202 + check(connectedComponents(g, comp) == 3,
22.203 + "This graph has 3 connected components");
22.204 + check(comp[n1] != comp[n3] && comp[n1] != comp[n4] &&
22.205 + comp[n3] != comp[n4], "Wrong connectedComponents()");
22.206 + check(comp[n1] == comp[n2] && comp[n1] == comp[n5] &&
22.207 + comp[n1] == comp[n8], "Wrong connectedComponents()");
22.208 + check(comp[n4] == comp[n6] && comp[n4] == comp[n7],
22.209 + "Wrong connectedComponents()");
22.210 +
22.211 + cutarcs[d.addArc(n3, n1)] = true;
22.212 + cutarcs[d.addArc(n3, n5)] = true;
22.213 + cutarcs[d.addArc(n3, n8)] = true;
22.214 + cutarcs[d.addArc(n8, n6)] = true;
22.215 + cutarcs[d.addArc(n8, n7)] = true;
22.216 +
22.217 + check(!stronglyConnected(d), "This digraph is not strongly connected");
22.218 + check(countStronglyConnectedComponents(d) == 3,
22.219 + "This digraph has 3 strongly connected components");
22.220 + Digraph::NodeMap<int> scomp2(d);
22.221 + check(stronglyConnectedComponents(d, scomp2) == 3,
22.222 + "This digraph has 3 strongly connected components");
22.223 + check(scomp2[n3] == 0, "Wrong stronglyConnectedComponents()");
22.224 + check(scomp2[n1] == 1 && scomp2[n2] == 1 && scomp2[n5] == 1 &&
22.225 + scomp2[n8] == 1, "Wrong stronglyConnectedComponents()");
22.226 + check(scomp2[n4] == 2 && scomp2[n6] == 2 && scomp2[n7] == 2,
22.227 + "Wrong stronglyConnectedComponents()");
22.228 + Digraph::ArcMap<bool> scut2(d, false);
22.229 + check(stronglyConnectedCutArcs(d, scut2) == 5,
22.230 + "This digraph has 5 strongly connected cut arcs.");
22.231 + for (Digraph::ArcIt a(d); a != INVALID; ++a) {
22.232 + check(scut2[a] == cutarcs[a], "Wrong stronglyConnectedCutArcs()");
22.233 + }
22.234 + }
22.235 +
22.236 + {
22.237 + // DAG example for topological sort from the book New Algorithms
22.238 + // (T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein)
22.239 + Digraph d;
22.240 + Digraph::NodeMap<int> order(d);
22.241 +
22.242 + Digraph::Node belt = d.addNode();
22.243 + Digraph::Node trousers = d.addNode();
22.244 + Digraph::Node necktie = d.addNode();
22.245 + Digraph::Node coat = d.addNode();
22.246 + Digraph::Node socks = d.addNode();
22.247 + Digraph::Node shirt = d.addNode();
22.248 + Digraph::Node shoe = d.addNode();
22.249 + Digraph::Node watch = d.addNode();
22.250 + Digraph::Node pants = d.addNode();
22.251 +
22.252 + d.addArc(socks, shoe);
22.253 + d.addArc(pants, shoe);
22.254 + d.addArc(pants, trousers);
22.255 + d.addArc(trousers, shoe);
22.256 + d.addArc(trousers, belt);
22.257 + d.addArc(belt, coat);
22.258 + d.addArc(shirt, belt);
22.259 + d.addArc(shirt, necktie);
22.260 + d.addArc(necktie, coat);
22.261 +
22.262 + check(dag(d), "This digraph is DAG.");
22.263 + topologicalSort(d, order);
22.264 + for (Digraph::ArcIt a(d); a != INVALID; ++a) {
22.265 + check(order[d.source(a)] < order[d.target(a)],
22.266 + "Wrong topologicalSort()");
22.267 + }
22.268 + }
22.269 +
22.270 + {
22.271 + ListGraph g;
22.272 + ListGraph::NodeMap<bool> map(g);
22.273 +
22.274 + ListGraph::Node n1 = g.addNode();
22.275 + ListGraph::Node n2 = g.addNode();
22.276 + ListGraph::Node n3 = g.addNode();
22.277 + ListGraph::Node n4 = g.addNode();
22.278 + ListGraph::Node n5 = g.addNode();
22.279 + ListGraph::Node n6 = g.addNode();
22.280 + ListGraph::Node n7 = g.addNode();
22.281 +
22.282 + g.addEdge(n1, n3);
22.283 + g.addEdge(n1, n4);
22.284 + g.addEdge(n2, n5);
22.285 + g.addEdge(n3, n6);
22.286 + g.addEdge(n4, n6);
22.287 + g.addEdge(n4, n7);
22.288 + g.addEdge(n5, n7);
22.289 +
22.290 + check(bipartite(g), "This graph is bipartite");
22.291 + check(bipartitePartitions(g, map), "This graph is bipartite");
22.292 +
22.293 + check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7],
22.294 + "Wrong bipartitePartitions()");
22.295 + check(map[n3] == map[n4] && map[n3] == map[n5],
22.296 + "Wrong bipartitePartitions()");
22.297 + }
22.298 +
22.299 + return 0;
22.300 +}
23.1 --- a/test/min_cost_flow_test.cc Thu May 07 02:05:12 2009 +0200
23.2 +++ b/test/min_cost_flow_test.cc Tue May 12 12:09:55 2009 +0100
23.3 @@ -174,7 +174,7 @@
23.4 typename CM, typename SM, typename FM, typename PM >
23.5 bool checkPotential( const GR& gr, const LM& lower, const UM& upper,
23.6 const CM& cost, const SM& supply, const FM& flow,
23.7 - const PM& pi )
23.8 + const PM& pi, SupplyType type )
23.9 {
23.10 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
23.11
23.12 @@ -193,12 +193,50 @@
23.13 sum += flow[e];
23.14 for (InArcIt e(gr, n); e != INVALID; ++e)
23.15 sum -= flow[e];
23.16 - opt = (sum == supply[n]) || (pi[n] == 0);
23.17 + if (type != LEQ) {
23.18 + opt = (pi[n] <= 0) && (sum == supply[n] || pi[n] == 0);
23.19 + } else {
23.20 + opt = (pi[n] >= 0) && (sum == supply[n] || pi[n] == 0);
23.21 + }
23.22 }
23.23
23.24 return opt;
23.25 }
23.26
23.27 +// Check whether the dual cost is equal to the primal cost
23.28 +template < typename GR, typename LM, typename UM,
23.29 + typename CM, typename SM, typename PM >
23.30 +bool checkDualCost( const GR& gr, const LM& lower, const UM& upper,
23.31 + const CM& cost, const SM& supply, const PM& pi,
23.32 + typename CM::Value total )
23.33 +{
23.34 + TEMPLATE_DIGRAPH_TYPEDEFS(GR);
23.35 +
23.36 + typename CM::Value dual_cost = 0;
23.37 + SM red_supply(gr);
23.38 + for (NodeIt n(gr); n != INVALID; ++n) {
23.39 + red_supply[n] = supply[n];
23.40 + }
23.41 + for (ArcIt a(gr); a != INVALID; ++a) {
23.42 + if (lower[a] != 0) {
23.43 + dual_cost += lower[a] * cost[a];
23.44 + red_supply[gr.source(a)] -= lower[a];
23.45 + red_supply[gr.target(a)] += lower[a];
23.46 + }
23.47 + }
23.48 +
23.49 + for (NodeIt n(gr); n != INVALID; ++n) {
23.50 + dual_cost -= red_supply[n] * pi[n];
23.51 + }
23.52 + for (ArcIt a(gr); a != INVALID; ++a) {
23.53 + typename CM::Value red_cost =
23.54 + cost[a] + pi[gr.source(a)] - pi[gr.target(a)];
23.55 + dual_cost -= (upper[a] - lower[a]) * std::max(-red_cost, 0);
23.56 + }
23.57 +
23.58 + return dual_cost == total;
23.59 +}
23.60 +
23.61 // Run a minimum cost flow algorithm and check the results
23.62 template < typename MCF, typename GR,
23.63 typename LM, typename UM,
23.64 @@ -220,8 +258,10 @@
23.65 check(checkFlow(gr, lower, upper, supply, flow, type),
23.66 "The flow is not feasible " + test_id);
23.67 check(mcf.totalCost() == total, "The flow is not optimal " + test_id);
23.68 - check(checkPotential(gr, lower, upper, cost, supply, flow, pi),
23.69 + check(checkPotential(gr, lower, upper, cost, supply, flow, pi, type),
23.70 "Wrong potentials " + test_id);
23.71 + check(checkDualCost(gr, lower, upper, cost, supply, pi, total),
23.72 + "Wrong dual cost " + test_id);
23.73 }
23.74 }
23.75
23.76 @@ -266,45 +306,56 @@
23.77 .node("target", w)
23.78 .run();
23.79
23.80 - // Build a test digraph for testing negative costs
23.81 - Digraph ngr;
23.82 - Node n1 = ngr.addNode();
23.83 - Node n2 = ngr.addNode();
23.84 - Node n3 = ngr.addNode();
23.85 - Node n4 = ngr.addNode();
23.86 - Node n5 = ngr.addNode();
23.87 - Node n6 = ngr.addNode();
23.88 - Node n7 = ngr.addNode();
23.89 + // Build test digraphs with negative costs
23.90 + Digraph neg_gr;
23.91 + Node n1 = neg_gr.addNode();
23.92 + Node n2 = neg_gr.addNode();
23.93 + Node n3 = neg_gr.addNode();
23.94 + Node n4 = neg_gr.addNode();
23.95 + Node n5 = neg_gr.addNode();
23.96 + Node n6 = neg_gr.addNode();
23.97 + Node n7 = neg_gr.addNode();
23.98
23.99 - Arc a1 = ngr.addArc(n1, n2);
23.100 - Arc a2 = ngr.addArc(n1, n3);
23.101 - Arc a3 = ngr.addArc(n2, n4);
23.102 - Arc a4 = ngr.addArc(n3, n4);
23.103 - Arc a5 = ngr.addArc(n3, n2);
23.104 - Arc a6 = ngr.addArc(n5, n3);
23.105 - Arc a7 = ngr.addArc(n5, n6);
23.106 - Arc a8 = ngr.addArc(n6, n7);
23.107 - Arc a9 = ngr.addArc(n7, n5);
23.108 + Arc a1 = neg_gr.addArc(n1, n2);
23.109 + Arc a2 = neg_gr.addArc(n1, n3);
23.110 + Arc a3 = neg_gr.addArc(n2, n4);
23.111 + Arc a4 = neg_gr.addArc(n3, n4);
23.112 + Arc a5 = neg_gr.addArc(n3, n2);
23.113 + Arc a6 = neg_gr.addArc(n5, n3);
23.114 + Arc a7 = neg_gr.addArc(n5, n6);
23.115 + Arc a8 = neg_gr.addArc(n6, n7);
23.116 + Arc a9 = neg_gr.addArc(n7, n5);
23.117
23.118 - Digraph::ArcMap<int> nc(ngr), nl1(ngr, 0), nl2(ngr, 0);
23.119 - ConstMap<Arc, int> nu1(std::numeric_limits<int>::max()), nu2(5000);
23.120 - Digraph::NodeMap<int> ns(ngr, 0);
23.121 + Digraph::ArcMap<int> neg_c(neg_gr), neg_l1(neg_gr, 0), neg_l2(neg_gr, 0);
23.122 + ConstMap<Arc, int> neg_u1(std::numeric_limits<int>::max()), neg_u2(5000);
23.123 + Digraph::NodeMap<int> neg_s(neg_gr, 0);
23.124
23.125 - nl2[a7] = 1000;
23.126 - nl2[a8] = -1000;
23.127 + neg_l2[a7] = 1000;
23.128 + neg_l2[a8] = -1000;
23.129
23.130 - ns[n1] = 100;
23.131 - ns[n4] = -100;
23.132 + neg_s[n1] = 100;
23.133 + neg_s[n4] = -100;
23.134
23.135 - nc[a1] = 100;
23.136 - nc[a2] = 30;
23.137 - nc[a3] = 20;
23.138 - nc[a4] = 80;
23.139 - nc[a5] = 50;
23.140 - nc[a6] = 10;
23.141 - nc[a7] = 80;
23.142 - nc[a8] = 30;
23.143 - nc[a9] = -120;
23.144 + neg_c[a1] = 100;
23.145 + neg_c[a2] = 30;
23.146 + neg_c[a3] = 20;
23.147 + neg_c[a4] = 80;
23.148 + neg_c[a5] = 50;
23.149 + neg_c[a6] = 10;
23.150 + neg_c[a7] = 80;
23.151 + neg_c[a8] = 30;
23.152 + neg_c[a9] = -120;
23.153 +
23.154 + Digraph negs_gr;
23.155 + Digraph::NodeMap<int> negs_s(negs_gr);
23.156 + Digraph::ArcMap<int> negs_c(negs_gr);
23.157 + ConstMap<Arc, int> negs_l(0), negs_u(1000);
23.158 + n1 = negs_gr.addNode();
23.159 + n2 = negs_gr.addNode();
23.160 + negs_s[n1] = 100;
23.161 + negs_s[n2] = -300;
23.162 + negs_c[negs_gr.addArc(n1, n2)] = -1;
23.163 +
23.164
23.165 // A. Test NetworkSimplex with the default pivot rule
23.166 {
23.167 @@ -342,7 +393,7 @@
23.168 mcf.supplyType(mcf.GEQ);
23.169 checkMcf(mcf, mcf.lowerMap(l2).run(),
23.170 gr, l2, u, c, s5, mcf.OPTIMAL, true, 4540, "#A11", GEQ);
23.171 - mcf.supplyType(mcf.CARRY_SUPPLIES).supplyMap(s6);
23.172 + mcf.supplyMap(s6);
23.173 checkMcf(mcf, mcf.run(),
23.174 gr, l2, u, c, s6, mcf.INFEASIBLE, false, 0, "#A12", GEQ);
23.175
23.176 @@ -353,20 +404,26 @@
23.177 gr, l1, u, c, s6, mcf.OPTIMAL, true, 5080, "#A13", LEQ);
23.178 checkMcf(mcf, mcf.lowerMap(l2).run(),
23.179 gr, l2, u, c, s6, mcf.OPTIMAL, true, 5930, "#A14", LEQ);
23.180 - mcf.supplyType(mcf.SATISFY_DEMANDS).supplyMap(s5);
23.181 + mcf.supplyMap(s5);
23.182 checkMcf(mcf, mcf.run(),
23.183 gr, l2, u, c, s5, mcf.INFEASIBLE, false, 0, "#A15", LEQ);
23.184
23.185 // Check negative costs
23.186 - NetworkSimplex<Digraph> nmcf(ngr);
23.187 - nmcf.lowerMap(nl1).costMap(nc).supplyMap(ns);
23.188 - checkMcf(nmcf, nmcf.run(),
23.189 - ngr, nl1, nu1, nc, ns, nmcf.UNBOUNDED, false, 0, "#A16");
23.190 - checkMcf(nmcf, nmcf.upperMap(nu2).run(),
23.191 - ngr, nl1, nu2, nc, ns, nmcf.OPTIMAL, true, -40000, "#A17");
23.192 - nmcf.reset().lowerMap(nl2).costMap(nc).supplyMap(ns);
23.193 - checkMcf(nmcf, nmcf.run(),
23.194 - ngr, nl2, nu1, nc, ns, nmcf.UNBOUNDED, false, 0, "#A18");
23.195 + NetworkSimplex<Digraph> neg_mcf(neg_gr);
23.196 + neg_mcf.lowerMap(neg_l1).costMap(neg_c).supplyMap(neg_s);
23.197 + checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u1,
23.198 + neg_c, neg_s, neg_mcf.UNBOUNDED, false, 0, "#A16");
23.199 + neg_mcf.upperMap(neg_u2);
23.200 + checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u2,
23.201 + neg_c, neg_s, neg_mcf.OPTIMAL, true, -40000, "#A17");
23.202 + neg_mcf.reset().lowerMap(neg_l2).costMap(neg_c).supplyMap(neg_s);
23.203 + checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l2, neg_u1,
23.204 + neg_c, neg_s, neg_mcf.UNBOUNDED, false, 0, "#A18");
23.205 +
23.206 + NetworkSimplex<Digraph> negs_mcf(negs_gr);
23.207 + negs_mcf.costMap(negs_c).supplyMap(negs_s);
23.208 + checkMcf(negs_mcf, negs_mcf.run(), negs_gr, negs_l, negs_u,
23.209 + negs_c, negs_s, negs_mcf.OPTIMAL, true, -300, "#A19", GEQ);
23.210 }
23.211
23.212 // B. Test NetworkSimplex with each pivot rule
24.1 --- a/tools/lgf-gen.cc Thu May 07 02:05:12 2009 +0200
24.2 +++ b/tools/lgf-gen.cc Tue May 12 12:09:55 2009 +0100
24.3 @@ -18,7 +18,7 @@
24.4
24.5 /// \ingroup tools
24.6 /// \file
24.7 -/// \brief Special plane digraph generator.
24.8 +/// \brief Special plane graph generator.
24.9 ///
24.10 /// Graph generator application for various types of plane graphs.
24.11 ///
24.12 @@ -26,7 +26,7 @@
24.13 /// \code
24.14 /// lgf-gen --help
24.15 /// \endcode
24.16 -/// for more info on the usage.
24.17 +/// for more information on the usage.
24.18
24.19 #include <algorithm>
24.20 #include <set>
24.21 @@ -686,20 +686,21 @@
24.22 .intOption("g", "Girth parameter (default is 10)", 10)
24.23 .refOption("cities", "Number of cities (default is 1)", num_of_cities)
24.24 .refOption("area", "Full relative area of the cities (default is 1)", area)
24.25 - .refOption("disc", "Nodes are evenly distributed on a unit disc (default)",disc_d)
24.26 + .refOption("disc", "Nodes are evenly distributed on a unit disc (default)",
24.27 + disc_d)
24.28 .optionGroup("dist", "disc")
24.29 - .refOption("square", "Nodes are evenly distributed on a unit square", square_d)
24.30 + .refOption("square", "Nodes are evenly distributed on a unit square",
24.31 + square_d)
24.32 .optionGroup("dist", "square")
24.33 - .refOption("gauss",
24.34 - "Nodes are located according to a two-dim gauss distribution",
24.35 - gauss_d)
24.36 + .refOption("gauss", "Nodes are located according to a two-dim Gauss "
24.37 + "distribution", gauss_d)
24.38 .optionGroup("dist", "gauss")
24.39 -// .mandatoryGroup("dist")
24.40 .onlyOneGroup("dist")
24.41 - .boolOption("eps", "Also generate .eps output (prefix.eps)")
24.42 - .boolOption("nonodes", "Draw the edges only in the generated .eps")
24.43 - .boolOption("dir", "Directed digraph is generated (each arcs are replaced by two directed ones)")
24.44 - .boolOption("2con", "Create a two connected planar digraph")
24.45 + .boolOption("eps", "Also generate .eps output (<prefix>.eps)")
24.46 + .boolOption("nonodes", "Draw only the edges in the generated .eps output")
24.47 + .boolOption("dir", "Directed graph is generated (each edge is replaced by "
24.48 + "two directed arcs)")
24.49 + .boolOption("2con", "Create a two connected planar graph")
24.50 .optionGroup("alg","2con")
24.51 .boolOption("tree", "Create a min. cost spanning tree")
24.52 .optionGroup("alg","tree")
24.53 @@ -707,7 +708,7 @@
24.54 .optionGroup("alg","tsp")
24.55 .boolOption("tsp2", "Create a TSP tour (tree based)")
24.56 .optionGroup("alg","tsp2")
24.57 - .boolOption("dela", "Delaunay triangulation digraph")
24.58 + .boolOption("dela", "Delaunay triangulation graph")
24.59 .optionGroup("alg","dela")
24.60 .onlyOneGroup("alg")
24.61 .boolOption("rand", "Use time seed for random number generator")