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