Changes in / [843:189760a7cdd0:844:c01a98ce01fd] in lemon
- Files:
-
- 2 added
- 1 deleted
- 21 edited
Legend:
- Unmodified
- Added
- Removed
-
CMakeLists.txt
r678 r705 45 45 SET(CPACK_PACKAGE_VENDOR "EGRES") 46 46 SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY 47 "LEMON - Library of Efficient Modelsand Optimization in Networks")47 "LEMON - Library for Efficient Modeling and Optimization in Networks") 48 48 SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE") 49 49 -
NEWS
r534 r712 1 2009-05-13 Version 1.1 released 2 3 This is the second stable release of the 1.x series. It 4 features a better coverage of the tools available in the 0.x 5 series, a thoroughly reworked LP/MIP interface plus various 6 improvements in the existing tools. 7 8 * Much improved M$ Windows support 9 * Various improvements in the CMAKE build system 10 * Compilation warnings are fixed/suppressed 11 * Support IBM xlC compiler 12 * New algorithms 13 * Connectivity related algorithms (#61) 14 * Euler walks (#65) 15 * Preflow push-relabel max. flow algorithm (#176) 16 * Circulation algorithm (push-relabel based) (#175) 17 * Suurballe algorithm (#47) 18 * Gomory-Hu algorithm (#66) 19 * Hao-Orlin algorithm (#58) 20 * Edmond's maximum cardinality and weighted matching algorithms 21 in general graphs (#48,#265) 22 * Minimum cost arborescence/branching (#60) 23 * Network Simplex min. cost flow algorithm (#234) 24 * New data structures 25 * Full graph structure (#57) 26 * Grid graph structure (#57) 27 * Hypercube graph structure (#57) 28 * Graph adaptors (#67) 29 * ArcSet and EdgeSet classes (#67) 30 * Elevator class (#174) 31 * Other new tools 32 * LP/MIP interface (#44) 33 * Support for GLPK, CPLEX, Soplex, COIN-OR CLP and CBC 34 * Reader for the Nauty file format (#55) 35 * DIMACS readers (#167) 36 * Radix sort algorithms (#72) 37 * RangeIdMap and CrossRefMap (#160) 38 * New command line tools 39 * DIMACS to LGF converter (#182) 40 * lgf-gen - a graph generator (#45) 41 * DIMACS solver utility (#226) 42 * Other code improvements 43 * Lognormal distribution added to Random (#102) 44 * Better (i.e. O(1) time) item counting in SmartGraph (#3) 45 * The standard maps of graphs are guaranteed to be 46 reference maps (#190) 47 * Miscellaneous 48 * Various doc improvements 49 * Improved 0.x -> 1.x converter script 50 51 * Several bugfixes (compared to release 1.0): 52 #170: Bugfix SmartDigraph::split() 53 #171: Bugfix in SmartGraph::restoreSnapshot() 54 #172: Extended test cases for graphs and digraphs 55 #173: Bugfix in Random 56 * operator()s always return a double now 57 * the faulty real<Num>(Num) and real<Num>(Num,Num) 58 have been removed 59 #187: Remove DijkstraWidestPathOperationTraits 60 #61: Bugfix in DfsVisit 61 #193: Bugfix in GraphReader::skipSection() 62 #195: Bugfix in ConEdgeIt() 63 #197: Bugfix in heap unionfind 64 * This bug affects Edmond's general matching algorithms 65 #207: Fix 'make install' without 'make html' using CMAKE 66 #208: Suppress or fix VS2008 compilation warnings 67 ----: Update the LEMON icon 68 ----: Enable the component-based installer 69 (in installers made by CPACK) 70 ----: Set the proper version for CMAKE in the tarballs 71 (made by autotools) 72 ----: Minor clarification in the LICENSE file 73 ----: Add missing unistd.h include to time_measure.h 74 #204: Compilation bug fixed in graph_to_eps.h with VS2005 75 #214,#215: windows.h should never be included by lemon headers 76 #230: Build systems check the availability of 'long long' type 77 #229: Default implementation of Tolerance<> is used for integer types 78 #211,#212: Various fixes for compiling on AIX 79 ----: Improvements in CMAKE config 80 - docs is installed in share/doc/ 81 - detects newer versions of Ghostscript 82 #239: Fix missing 'inline' specifier in time_measure.h 83 #274,#280: Install lemon/config.h 84 #275: Prefix macro names with LEMON_ in lemon/config.h 85 ----: Small script for making the release tarballs added 86 ----: Minor improvement in unify-sources.sh (a76f55d7d397) 87 1 88 2009-03-27 LEMON joins to the COIN-OR initiative 2 89 -
README
r318 r705 1 ================================================================== 2 LEMON - a Library of Efficient Modelsand Optimization in Networks3 ================================================================== 1 ===================================================================== 2 LEMON - a Library for Efficient Modeling and Optimization in Networks 3 ===================================================================== 4 4 5 5 LEMON is an open source library written in C++. It provides -
doc/Makefile.am
r634 r710 9 9 doc/mainpage.dox \ 10 10 doc/migration.dox \ 11 doc/min_cost_flow.dox \ 11 12 doc/named-param.dox \ 12 13 doc/namespaces.dox \ -
doc/groups.dox
r843 r844 139 139 140 140 /** 141 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs142 @ingroup graphs143 \brief Graph types between real graphs and graph adaptors.144 145 This group contains some graph types between real graphs and graph adaptors.146 These classes wrap graphs to give new functionality as the adaptors do it.147 On the other hand they are not light-weight structures as the adaptors.148 */149 150 /**151 141 @defgroup maps Maps 152 142 @ingroup datas … … 316 306 minimum cut, which is the dual problem of maximum flow. 317 307 308 318 309 \ref Circulation is a preflow push-relabel algorithm implemented directly 319 310 for finding feasible circulations, which is a somewhat different problem, … … 323 314 324 315 /** 325 @defgroup min_cost_flow Minimum Cost Flow Algorithms316 @defgroup min_cost_flow_algs Minimum Cost Flow Algorithms 326 317 @ingroup algs 327 318 … … 329 320 330 321 This group contains the algorithms for finding minimum cost flows and 331 circulations. 332 333 The \e minimum \e cost \e flow \e problem is to find a feasible flow of 334 minimum total cost from a set of supply nodes to a set of demand nodes 335 in a network with capacity constraints (lower and upper bounds) 336 and arc costs. 337 Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{Z}\f$, 338 \f$upper: A\rightarrow\mathbf{Z}\cup\{+\infty\}\f$ denote the lower and 339 upper bounds for the flow values on the arcs, for which 340 \f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$, 341 \f$cost: A\rightarrow\mathbf{Z}\f$ denotes the cost per unit flow 342 on the arcs and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the 343 signed supply values of the nodes. 344 If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$ 345 supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with 346 \f$-sup(u)\f$ demand. 347 A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution 348 of the following optimization problem. 349 350 \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f] 351 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq 352 sup(u) \quad \forall u\in V \f] 353 \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f] 354 355 The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be 356 zero or negative in order to have a feasible solution (since the sum 357 of the expressions on the left-hand side of the inequalities is zero). 358 It means that the total demand must be greater or equal to the total 359 supply and all the supplies have to be carried out from the supply nodes, 360 but there could be demands that are not satisfied. 361 If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand 362 constraints have to be satisfied with equality, i.e. all demands 363 have to be satisfied and all supplies have to be used. 364 365 If you need the opposite inequalities in the supply/demand constraints 366 (i.e. the total demand is less than the total supply and all the demands 367 have to be satisfied while there could be supplies that are not used), 368 then you could easily transform the problem to the above form by reversing 369 the direction of the arcs and taking the negative of the supply values 370 (e.g. using \ref ReverseDigraph and \ref NegMap adaptors). 371 However \ref NetworkSimplex algorithm also supports this form directly 372 for the sake of convenience. 373 374 A feasible solution for this problem can be found using \ref Circulation. 375 376 Note that the above formulation is actually more general than the usual 377 definition of the minimum cost flow problem, in which strict equalities 378 are required in the supply/demand contraints, i.e. 379 380 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) = 381 sup(u) \quad \forall u\in V. \f] 382 383 However if the sum of the supply values is zero, then these two problems 384 are equivalent. So if you need the equality form, you have to ensure this 385 additional contraint for the algorithms. 386 387 The dual solution of the minimum cost flow problem is represented by node 388 potentials \f$\pi: V\rightarrow\mathbf{Z}\f$. 389 An \f$f: A\rightarrow\mathbf{Z}\f$ feasible solution of the problem 390 is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$ 391 node potentials the following \e complementary \e slackness optimality 392 conditions hold. 393 394 - For all \f$uv\in A\f$ arcs: 395 - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$; 396 - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$; 397 - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$. 398 - For all \f$u\in V\f$ nodes: 399 - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$, 400 then \f$\pi(u)=0\f$. 401 402 Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc 403 \f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e. 404 \f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f] 322 circulations. For more information about this problem and its dual 323 solution see \ref min_cost_flow "Minimum Cost Flow Problem". 405 324 406 325 \ref NetworkSimplex is an efficient implementation of the primal Network … … 480 399 @defgroup spantree Minimum Spanning Tree Algorithms 481 400 @ingroup algs 482 \brief Algorithms for finding a minimum cost spanning tree in a graph.483 484 This group contains the algorithms for finding aminimum cost spanning485 tree in a graph.401 \brief Algorithms for finding minimum cost spanning trees and arborescences. 402 403 This group contains the algorithms for finding minimum cost spanning 404 trees and arborescences. 486 405 */ 487 406 -
doc/mainpage.dox
r606 r705 24 24 \subsection whatis What is LEMON 25 25 26 LEMON stands for 27 <b>L</b>ibrary of <b>E</b>fficient <b>M</b>odels 26 LEMON stands for <b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling 28 27 and <b>O</b>ptimization in <b>N</b>etworks. 29 28 It is a C++ template … … 42 41 \subsection howtoread How to read the documentation 43 42 44 If you want to get a quick start and see the most important features then 45 take a look at our \ref quicktour 46 "Quick Tour to LEMON" which will guide you along. 47 48 If you already feel like using our library, see the 43 If you would like to get to know the library, see 49 44 <a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>. 50 45 51 If you know what you are looking for then try to find it under the46 If you know what you are looking for, then try to find it under the 52 47 <a class="el" href="modules.html">Modules</a> section. 53 48 -
lemon/Makefile.am
r686 r708 112 112 lemon/bits/alteration_notifier.h \ 113 113 lemon/bits/array_map.h \ 114 lemon/bits/base_extender.h \115 114 lemon/bits/bezier.h \ 116 115 lemon/bits/default_map.h \ -
lemon/adaptors.h
r664 r703 1840 1840 typedef typename Digraph::Node Node; 1841 1841 1842 class Arc : public Edge{1842 class Arc { 1843 1843 friend class UndirectorBase; 1844 1844 protected: 1845 Edge _edge; 1845 1846 bool _forward; 1846 1847 1847 Arc(const Edge& edge, bool forward) :1848 Edge(edge), _forward(forward) {}1848 Arc(const Edge& edge, bool forward) 1849 : _edge(edge), _forward(forward) {} 1849 1850 1850 1851 public: 1851 1852 Arc() {} 1852 1853 1853 Arc(Invalid) : Edge(INVALID), _forward(true) {} 1854 Arc(Invalid) : _edge(INVALID), _forward(true) {} 1855 1856 operator const Edge&() const { return _edge; } 1854 1857 1855 1858 bool operator==(const Arc &other) const { 1856 return _forward == other._forward && 1857 static_cast<const Edge&>(*this) == static_cast<const Edge&>(other); 1859 return _forward == other._forward && _edge == other._edge; 1858 1860 } 1859 1861 bool operator!=(const Arc &other) const { 1860 return _forward != other._forward || 1861 static_cast<const Edge&>(*this) != static_cast<const Edge&>(other); 1862 return _forward != other._forward || _edge != other._edge; 1862 1863 } 1863 1864 bool operator<(const Arc &other) const { 1864 1865 return _forward < other._forward || 1865 (_forward == other._forward && 1866 static_cast<const Edge&>(*this) < static_cast<const Edge&>(other)); 1866 (_forward == other._forward && _edge < other._edge); 1867 1867 } 1868 1868 }; … … 1877 1877 1878 1878 void first(Arc& a) const { 1879 _digraph->first(a );1879 _digraph->first(a._edge); 1880 1880 a._forward = true; 1881 1881 } … … 1885 1885 a._forward = false; 1886 1886 } else { 1887 _digraph->next(a );1887 _digraph->next(a._edge); 1888 1888 a._forward = true; 1889 1889 } … … 1899 1899 1900 1900 void firstOut(Arc& a, const Node& n) const { 1901 _digraph->firstIn(a , n);1902 if ( static_cast<const Edge&>(a)!= INVALID ) {1901 _digraph->firstIn(a._edge, n); 1902 if (a._edge != INVALID ) { 1903 1903 a._forward = false; 1904 1904 } else { 1905 _digraph->firstOut(a , n);1905 _digraph->firstOut(a._edge, n); 1906 1906 a._forward = true; 1907 1907 } … … 1909 1909 void nextOut(Arc &a) const { 1910 1910 if (!a._forward) { 1911 Node n = _digraph->target(a );1912 _digraph->nextIn(a );1913 if ( static_cast<const Edge&>(a) == INVALID) {1914 _digraph->firstOut(a , n);1911 Node n = _digraph->target(a._edge); 1912 _digraph->nextIn(a._edge); 1913 if (a._edge == INVALID) { 1914 _digraph->firstOut(a._edge, n); 1915 1915 a._forward = true; 1916 1916 } 1917 1917 } 1918 1918 else { 1919 _digraph->nextOut(a );1919 _digraph->nextOut(a._edge); 1920 1920 } 1921 1921 } 1922 1922 1923 1923 void firstIn(Arc &a, const Node &n) const { 1924 _digraph->firstOut(a , n);1925 if ( static_cast<const Edge&>(a)!= INVALID ) {1924 _digraph->firstOut(a._edge, n); 1925 if (a._edge != INVALID ) { 1926 1926 a._forward = false; 1927 1927 } else { 1928 _digraph->firstIn(a , n);1928 _digraph->firstIn(a._edge, n); 1929 1929 a._forward = true; 1930 1930 } … … 1932 1932 void nextIn(Arc &a) const { 1933 1933 if (!a._forward) { 1934 Node n = _digraph->source(a );1935 _digraph->nextOut(a );1936 if ( static_cast<const Edge&>(a)== INVALID ) {1937 _digraph->firstIn(a , n);1934 Node n = _digraph->source(a._edge); 1935 _digraph->nextOut(a._edge); 1936 if (a._edge == INVALID ) { 1937 _digraph->firstIn(a._edge, n); 1938 1938 a._forward = true; 1939 1939 } 1940 1940 } 1941 1941 else { 1942 _digraph->nextIn(a );1942 _digraph->nextIn(a._edge); 1943 1943 } 1944 1944 } … … 1973 1973 1974 1974 Node source(const Arc &a) const { 1975 return a._forward ? _digraph->source(a ) : _digraph->target(a);1975 return a._forward ? _digraph->source(a._edge) : _digraph->target(a._edge); 1976 1976 } 1977 1977 1978 1978 Node target(const Arc &a) const { 1979 return a._forward ? _digraph->target(a ) : _digraph->source(a);1979 return a._forward ? _digraph->target(a._edge) : _digraph->source(a._edge); 1980 1980 } 1981 1981 1982 1982 static Arc direct(const Edge &e, bool d) { 1983 1983 return Arc(e, d); 1984 }1985 Arc direct(const Edge &e, const Node& n) const {1986 return Arc(e, _digraph->source(e) == n);1987 1984 } 1988 1985 -
lemon/concepts/graph.h
r627 r704 311 311 /// The directed arc type. It can be converted to the 312 312 /// edge or it should be inherited from the undirected 313 /// arc.314 class Arc : public Edge{313 /// edge. 314 class Arc { 315 315 public: 316 316 /// Default constructor … … 323 323 /// Copy constructor. 324 324 /// 325 Arc(const Arc& e) : Edge(e) { }325 Arc(const Arc&) { } 326 326 /// Initialize the iterator to be invalid. 327 327 … … 350 350 bool operator<(Arc) const { return false; } 351 351 352 /// Converison to Edge 353 operator Edge() const { return Edge(); } 352 354 }; 353 355 /// This iterator goes through each directed arc. -
lemon/connectivity.h
r633 r695 43 43 /// \ingroup graph_properties 44 44 /// 45 /// \brief Check whether the given undirected graph is connected. 46 /// 47 /// Check whether the given undirected graph is connected. 48 /// \param graph The undirected graph. 49 /// \return \c true when there is path between any two nodes in the graph. 45 /// \brief Check whether an undirected graph is connected. 46 /// 47 /// This function checks whether the given undirected graph is connected, 48 /// i.e. there is a path between any two nodes in the graph. 49 /// 50 /// \return \c true if the graph is connected. 50 51 /// \note By definition, the empty graph is connected. 52 /// 53 /// \see countConnectedComponents(), connectedComponents() 54 /// \see stronglyConnected() 51 55 template <typename Graph> 52 56 bool connected(const Graph& graph) { … … 68 72 /// \brief Count the number of connected components of an undirected graph 69 73 /// 70 /// Count the number of connected components of an undirected graph 71 /// 72 /// \param graph The graph. It must be undirected. 73 /// \return The number of components 74 /// This function counts the number of connected components of the given 75 /// undirected graph. 76 /// 77 /// The connected components are the classes of an equivalence relation 78 /// on the nodes of an undirected graph. Two nodes are in the same class 79 /// if they are connected with a path. 80 /// 81 /// \return The number of connected components. 74 82 /// \note By definition, the empty graph consists 75 83 /// of zero connected components. 84 /// 85 /// \see connected(), connectedComponents() 76 86 template <typename Graph> 77 87 int countConnectedComponents(const Graph &graph) { … … 110 120 /// \brief Find the connected components of an undirected graph 111 121 /// 112 /// Find the connected components of an undirected graph. 122 /// This function finds the connected components of the given undirected 123 /// graph. 124 /// 125 /// The connected components are the classes of an equivalence relation 126 /// on the nodes of an undirected graph. Two nodes are in the same class 127 /// if they are connected with a path. 113 128 /// 114 129 /// \image html connected_components.png 115 130 /// \image latex connected_components.eps "Connected components" width=\textwidth 116 131 /// 117 /// \param graph The graph. It must be undirected.132 /// \param graph The undirected graph. 118 133 /// \retval compMap A writable node map. The values will be set from 0 to 119 /// the number of the connected components minus one. Each value sof the map120 /// will be set exactly once, the values of a certain component will be134 /// the number of the connected components minus one. Each value of the map 135 /// will be set exactly once, and the values of a certain component will be 121 136 /// set continuously. 122 /// \return The number of components 137 /// \return The number of connected components. 138 /// \note By definition, the empty graph consists 139 /// of zero connected components. 140 /// 141 /// \see connected(), countConnectedComponents() 123 142 template <class Graph, class NodeMap> 124 143 int connectedComponents(const Graph &graph, NodeMap &compMap) { … … 232 251 /// \ingroup graph_properties 233 252 /// 234 /// \brief Check whether the givendirected graph is strongly connected.235 /// 236 /// Check whether the given directed graph is strongly connected. The237 /// graph is strongly connected when any two nodes of thegraph are253 /// \brief Check whether a directed graph is strongly connected. 254 /// 255 /// This function checks whether the given directed graph is strongly 256 /// connected, i.e. any two nodes of the digraph are 238 257 /// connected with directed paths in both direction. 239 /// \return \c false when the graph is not strongly connected. 240 /// \see connected 241 /// 242 /// \note By definition, the empty graph is strongly connected. 258 /// 259 /// \return \c true if the digraph is strongly connected. 260 /// \note By definition, the empty digraph is strongly connected. 261 /// 262 /// \see countStronglyConnectedComponents(), stronglyConnectedComponents() 263 /// \see connected() 243 264 template <typename Digraph> 244 265 bool stronglyConnected(const Digraph& digraph) { … … 271 292 RDigraph rdigraph(digraph); 272 293 273 typedef DfsVisitor< Digraph> RVisitor;294 typedef DfsVisitor<RDigraph> RVisitor; 274 295 RVisitor rvisitor; 275 296 … … 290 311 /// \ingroup graph_properties 291 312 /// 292 /// \brief Count the strongly connected components of a directed graph 293 /// 294 /// Count the strongly connected components of a directed graph. 313 /// \brief Count the number of strongly connected components of a 314 /// directed graph 315 /// 316 /// This function counts the number of strongly connected components of 317 /// the given directed graph. 318 /// 295 319 /// The strongly connected components are the classes of an 296 /// equivalence relation on the nodes of thegraph. Two nodes are in320 /// equivalence relation on the nodes of a digraph. Two nodes are in 297 321 /// the same class if they are connected with directed paths in both 298 322 /// direction. 299 323 /// 300 /// \param digraph The graph. 301 /// \return The number of components 302 /// \note By definition, the empty graph has zero 324 /// \return The number of strongly connected components. 325 /// \note By definition, the empty digraph has zero 303 326 /// strongly connected components. 327 /// 328 /// \see stronglyConnected(), stronglyConnectedComponents() 304 329 template <typename Digraph> 305 330 int countStronglyConnectedComponents(const Digraph& digraph) { … … 356 381 /// \brief Find the strongly connected components of a directed graph 357 382 /// 358 /// Find the strongly connected components of a directed graph. The 359 /// strongly connected components are the classes of an equivalence 360 /// relation on the nodes of the graph. Two nodes are in 361 /// relationship when there are directed paths between them in both 362 /// direction. In addition, the numbering of components will satisfy 363 /// that there is no arc going from a higher numbered component to 364 /// a lower. 383 /// This function finds the strongly connected components of the given 384 /// directed graph. In addition, the numbering of the components will 385 /// satisfy that there is no arc going from a higher numbered component 386 /// to a lower one (i.e. it provides a topological order of the components). 387 /// 388 /// The strongly connected components are the classes of an 389 /// equivalence relation on the nodes of a digraph. Two nodes are in 390 /// the same class if they are connected with directed paths in both 391 /// direction. 365 392 /// 366 393 /// \image html strongly_connected_components.png … … 370 397 /// \retval compMap A writable node map. The values will be set from 0 to 371 398 /// the number of the strongly connected components minus one. Each value 372 /// of the map will be set exactly once, the values of a certain component 373 /// will be set continuously. 374 /// \return The number of components 399 /// of the map will be set exactly once, and the values of a certain 400 /// component will be set continuously. 401 /// \return The number of strongly connected components. 402 /// \note By definition, the empty digraph has zero 403 /// strongly connected components. 404 /// 405 /// \see stronglyConnected(), countStronglyConnectedComponents() 375 406 template <typename Digraph, typename NodeMap> 376 407 int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) { … … 425 456 /// \brief Find the cut arcs of the strongly connected components. 426 457 /// 427 /// Find the cut arcs of the strongly connected components. 428 /// The strongly connected components are the classes of an equivalence 429 /// relation on the nodes of the graph. Two nodes are in relationship 430 /// when there are directed paths between them in both direction. 458 /// This function finds the cut arcs of the strongly connected components 459 /// of the given digraph. 460 /// 461 /// The strongly connected components are the classes of an 462 /// equivalence relation on the nodes of a digraph. Two nodes are in 463 /// the same class if they are connected with directed paths in both 464 /// direction. 431 465 /// The strongly connected components are separated by the cut arcs. 432 466 /// 433 /// \param graph The graph. 434 /// \retval cutMap A writable node map. The values will be set true when the 435 /// arc is a cut arc. 436 /// 437 /// \return The number of cut arcs 467 /// \param digraph The digraph. 468 /// \retval cutMap A writable arc map. The values will be set to \c true 469 /// for the cut arcs (exactly once for each cut arc), and will not be 470 /// changed for other arcs. 471 /// \return The number of cut arcs. 472 /// 473 /// \see stronglyConnected(), stronglyConnectedComponents() 438 474 template <typename Digraph, typename ArcMap> 439 int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) {475 int stronglyConnectedCutArcs(const Digraph& digraph, ArcMap& cutMap) { 440 476 checkConcept<concepts::Digraph, Digraph>(); 441 477 typedef typename Digraph::Node Node; … … 449 485 typedef typename Container::iterator Iterator; 450 486 451 Container nodes(countNodes( graph));487 Container nodes(countNodes(digraph)); 452 488 typedef LeaveOrderVisitor<Digraph, Iterator> Visitor; 453 489 Visitor visitor(nodes.begin()); 454 490 455 DfsVisit<Digraph, Visitor> dfs( graph, visitor);491 DfsVisit<Digraph, Visitor> dfs(digraph, visitor); 456 492 dfs.init(); 457 for (NodeIt it( graph); it != INVALID; ++it) {493 for (NodeIt it(digraph); it != INVALID; ++it) { 458 494 if (!dfs.reached(it)) { 459 495 dfs.addSource(it); … … 465 501 typedef ReverseDigraph<const Digraph> RDigraph; 466 502 467 RDigraph r graph(graph);503 RDigraph rdigraph(digraph); 468 504 469 505 int cutNum = 0; 470 506 471 507 typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor; 472 RVisitor rvisitor(r graph, cutMap, cutNum);473 474 DfsVisit<RDigraph, RVisitor> rdfs(r graph, rvisitor);508 RVisitor rvisitor(rdigraph, cutMap, cutNum); 509 510 DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor); 475 511 476 512 rdfs.init(); … … 707 743 /// \ingroup graph_properties 708 744 /// 709 /// \brief Checks the graph is bi-node-connected. 710 /// 711 /// This function checks that the undirected graph is bi-node-connected 712 /// graph. The graph is bi-node-connected if any two undirected edge is 713 /// on same circle. 714 /// 715 /// \param graph The graph. 716 /// \return \c true when the graph bi-node-connected. 745 /// \brief Check whether an undirected graph is bi-node-connected. 746 /// 747 /// This function checks whether the given undirected graph is 748 /// bi-node-connected, i.e. any two edges are on same circle. 749 /// 750 /// \return \c true if the graph bi-node-connected. 751 /// \note By definition, the empty graph is bi-node-connected. 752 /// 753 /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents() 717 754 template <typename Graph> 718 755 bool biNodeConnected(const Graph& graph) { … … 722 759 /// \ingroup graph_properties 723 760 /// 724 /// \brief Count the biconnected components. 725 /// 726 /// This function finds the bi-node-connected components in an undirected 727 /// graph. The biconnected components are the classes of an equivalence 728 /// relation on the undirected edges. Two undirected edge is in relationship 729 /// when they are on same circle. 730 /// 731 /// \param graph The graph. 732 /// \return The number of components. 761 /// \brief Count the number of bi-node-connected components of an 762 /// undirected graph. 763 /// 764 /// This function counts the number of bi-node-connected components of 765 /// the given undirected graph. 766 /// 767 /// The bi-node-connected components are the classes of an equivalence 768 /// relation on the edges of a undirected graph. Two edges are in the 769 /// same class if they are on same circle. 770 /// 771 /// \return The number of bi-node-connected components. 772 /// 773 /// \see biNodeConnected(), biNodeConnectedComponents() 733 774 template <typename Graph> 734 775 int countBiNodeConnectedComponents(const Graph& graph) { … … 757 798 /// \ingroup graph_properties 758 799 /// 759 /// \brief Find the bi-node-connected components. 760 /// 761 /// This function finds the bi-node-connected components in an undirected 762 /// graph. The bi-node-connected components are the classes of an equivalence 763 /// relation on the undirected edges. Two undirected edge are in relationship 764 /// when they are on same circle. 800 /// \brief Find the bi-node-connected components of an undirected graph. 801 /// 802 /// This function finds the bi-node-connected components of the given 803 /// undirected graph. 804 /// 805 /// The bi-node-connected components are the classes of an equivalence 806 /// relation on the edges of a undirected graph. Two edges are in the 807 /// same class if they are on same circle. 765 808 /// 766 809 /// \image html node_biconnected_components.png 767 810 /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth 768 811 /// 769 /// \param graph The graph. 770 /// \retval compMap A writable uedge map. The values will be set from 0 771 /// to the number of the biconnected components minus one. Each values 772 /// of the map will be set exactly once, the values of a certain component 773 /// will be set continuously. 774 /// \return The number of components. 812 /// \param graph The undirected graph. 813 /// \retval compMap A writable edge map. The values will be set from 0 814 /// to the number of the bi-node-connected components minus one. Each 815 /// value of the map will be set exactly once, and the values of a 816 /// certain component will be set continuously. 817 /// \return The number of bi-node-connected components. 818 /// 819 /// \see biNodeConnected(), countBiNodeConnectedComponents() 775 820 template <typename Graph, typename EdgeMap> 776 821 int biNodeConnectedComponents(const Graph& graph, … … 802 847 /// \ingroup graph_properties 803 848 /// 804 /// \brief Find the bi-node-connected cut nodes. 805 /// 806 /// This function finds the bi-node-connected cut nodes in an undirected 807 /// graph. The bi-node-connected components are the classes of an equivalence 808 /// relation on the undirected edges. Two undirected edges are in 809 /// relationship when they are on same circle. The biconnected components 810 /// are separted by nodes which are the cut nodes of the components. 811 /// 812 /// \param graph The graph. 813 /// \retval cutMap A writable edge map. The values will be set true when 814 /// the node separate two or more components. 849 /// \brief Find the bi-node-connected cut nodes in an undirected graph. 850 /// 851 /// This function finds the bi-node-connected cut nodes in the given 852 /// undirected graph. 853 /// 854 /// The bi-node-connected components are the classes of an equivalence 855 /// relation on the edges of a undirected graph. Two edges are in the 856 /// same class if they are on same circle. 857 /// The bi-node-connected components are separted by the cut nodes of 858 /// the components. 859 /// 860 /// \param graph The undirected graph. 861 /// \retval cutMap A writable node map. The values will be set to 862 /// \c true for the nodes that separate two or more components 863 /// (exactly once for each cut node), and will not be changed for 864 /// other nodes. 815 865 /// \return The number of the cut nodes. 866 /// 867 /// \see biNodeConnected(), biNodeConnectedComponents() 816 868 template <typename Graph, typename NodeMap> 817 869 int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) { … … 1032 1084 /// \ingroup graph_properties 1033 1085 /// 1034 /// \brief Checks that the graph is bi-edge-connected. 1035 /// 1036 /// This function checks that the graph is bi-edge-connected. The undirected 1037 /// graph is bi-edge-connected when any two nodes are connected with two 1038 /// edge-disjoint paths. 1039 /// 1040 /// \param graph The undirected graph. 1041 /// \return The number of components. 1086 /// \brief Check whether an undirected graph is bi-edge-connected. 1087 /// 1088 /// This function checks whether the given undirected graph is 1089 /// bi-edge-connected, i.e. any two nodes are connected with at least 1090 /// two edge-disjoint paths. 1091 /// 1092 /// \return \c true if the graph is bi-edge-connected. 1093 /// \note By definition, the empty graph is bi-edge-connected. 1094 /// 1095 /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents() 1042 1096 template <typename Graph> 1043 1097 bool biEdgeConnected(const Graph& graph) { … … 1047 1101 /// \ingroup graph_properties 1048 1102 /// 1049 /// \brief Count the bi-edge-connected components. 1050 /// 1051 /// This function count the bi-edge-connected components in an undirected 1052 /// graph. The bi-edge-connected components are the classes of an equivalence 1053 /// relation on the nodes. Two nodes are in relationship when they are 1054 /// connected with at least two edge-disjoint paths. 1055 /// 1056 /// \param graph The undirected graph. 1057 /// \return The number of components. 1103 /// \brief Count the number of bi-edge-connected components of an 1104 /// undirected graph. 1105 /// 1106 /// This function counts the number of bi-edge-connected components of 1107 /// the given undirected graph. 1108 /// 1109 /// The bi-edge-connected components are the classes of an equivalence 1110 /// relation on the nodes of an undirected graph. Two nodes are in the 1111 /// same class if they are connected with at least two edge-disjoint 1112 /// paths. 1113 /// 1114 /// \return The number of bi-edge-connected components. 1115 /// 1116 /// \see biEdgeConnected(), biEdgeConnectedComponents() 1058 1117 template <typename Graph> 1059 1118 int countBiEdgeConnectedComponents(const Graph& graph) { … … 1082 1141 /// \ingroup graph_properties 1083 1142 /// 1084 /// \brief Find the bi-edge-connected components. 1085 /// 1086 /// This function finds the bi-edge-connected components in an undirected 1087 /// graph. The bi-edge-connected components are the classes of an equivalence 1088 /// relation on the nodes. Two nodes are in relationship when they are 1089 /// connected at least two edge-disjoint paths. 1143 /// \brief Find the bi-edge-connected components of an undirected graph. 1144 /// 1145 /// This function finds the bi-edge-connected components of the given 1146 /// undirected graph. 1147 /// 1148 /// The bi-edge-connected components are the classes of an equivalence 1149 /// relation on the nodes of an undirected graph. Two nodes are in the 1150 /// same class if they are connected with at least two edge-disjoint 1151 /// paths. 1090 1152 /// 1091 1153 /// \image html edge_biconnected_components.png 1092 1154 /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth 1093 1155 /// 1094 /// \param graph The graph.1156 /// \param graph The undirected graph. 1095 1157 /// \retval compMap A writable node map. The values will be set from 0 to 1096 /// the number of the biconnected components minus one. Each values 1097 /// of the map will be set exactly once, the values of a certain component 1098 /// will be set continuously. 1099 /// \return The number of components. 1158 /// the number of the bi-edge-connected components minus one. Each value 1159 /// of the map will be set exactly once, and the values of a certain 1160 /// component will be set continuously. 1161 /// \return The number of bi-edge-connected components. 1162 /// 1163 /// \see biEdgeConnected(), countBiEdgeConnectedComponents() 1100 1164 template <typename Graph, typename NodeMap> 1101 1165 int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) { … … 1126 1190 /// \ingroup graph_properties 1127 1191 /// 1128 /// \brief Find the bi-edge-connected cut edges. 1129 /// 1130 /// This function finds the bi-edge-connected components in an undirected 1131 /// graph. The bi-edge-connected components are the classes of an equivalence 1132 /// relation on the nodes. Two nodes are in relationship when they are 1133 /// connected with at least two edge-disjoint paths. The bi-edge-connected 1134 /// components are separted by edges which are the cut edges of the 1135 /// components. 1136 /// 1137 /// \param graph The graph. 1138 /// \retval cutMap A writable node map. The values will be set true when the 1139 /// edge is a cut edge. 1192 /// \brief Find the bi-edge-connected cut edges in an undirected graph. 1193 /// 1194 /// This function finds the bi-edge-connected cut edges in the given 1195 /// undirected graph. 1196 /// 1197 /// The bi-edge-connected components are the classes of an equivalence 1198 /// relation on the nodes of an undirected graph. Two nodes are in the 1199 /// same class if they are connected with at least two edge-disjoint 1200 /// paths. 1201 /// The bi-edge-connected components are separted by the cut edges of 1202 /// the components. 1203 /// 1204 /// \param graph The undirected graph. 1205 /// \retval cutMap A writable edge map. The values will be set to \c true 1206 /// for the cut edges (exactly once for each cut edge), and will not be 1207 /// changed for other edges. 1140 1208 /// \return The number of cut edges. 1209 /// 1210 /// \see biEdgeConnected(), biEdgeConnectedComponents() 1141 1211 template <typename Graph, typename EdgeMap> 1142 1212 int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) { … … 1190 1260 /// \ingroup graph_properties 1191 1261 /// 1192 /// \brief Sort the nodes of a DAG into topolgical order. 1193 /// 1194 /// Sort the nodes of a DAG into topolgical order. 1195 /// 1196 /// \param graph The graph. It must be directed and acyclic. 1197 /// \retval order A writable node map. The values will be set from 0 to 1198 /// the number of the nodes in the graph minus one. Each values of the map 1199 /// will be set exactly once, the values will be set descending order. 1200 /// 1201 /// \see checkedTopologicalSort 1202 /// \see dag 1203 template <typename Digraph, typename NodeMap> 1204 void topologicalSort(const Digraph& graph, NodeMap& order) { 1205 using namespace _connectivity_bits; 1262 /// \brief Check whether a digraph is DAG. 1263 /// 1264 /// This function checks whether the given digraph is DAG, i.e. 1265 /// \e Directed \e Acyclic \e Graph. 1266 /// \return \c true if there is no directed cycle in the digraph. 1267 /// \see acyclic() 1268 template <typename Digraph> 1269 bool dag(const Digraph& digraph) { 1206 1270 1207 1271 checkConcept<concepts::Digraph, Digraph>(); 1208 checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();1209 1272 1210 1273 typedef typename Digraph::Node Node; … … 1212 1275 typedef typename Digraph::Arc Arc; 1213 1276 1277 typedef typename Digraph::template NodeMap<bool> ProcessedMap; 1278 1279 typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>:: 1280 Create dfs(digraph); 1281 1282 ProcessedMap processed(digraph); 1283 dfs.processedMap(processed); 1284 1285 dfs.init(); 1286 for (NodeIt it(digraph); it != INVALID; ++it) { 1287 if (!dfs.reached(it)) { 1288 dfs.addSource(it); 1289 while (!dfs.emptyQueue()) { 1290 Arc arc = dfs.nextArc(); 1291 Node target = digraph.target(arc); 1292 if (dfs.reached(target) && !processed[target]) { 1293 return false; 1294 } 1295 dfs.processNextArc(); 1296 } 1297 } 1298 } 1299 return true; 1300 } 1301 1302 /// \ingroup graph_properties 1303 /// 1304 /// \brief Sort the nodes of a DAG into topolgical order. 1305 /// 1306 /// This function sorts the nodes of the given acyclic digraph (DAG) 1307 /// into topolgical order. 1308 /// 1309 /// \param digraph The digraph, which must be DAG. 1310 /// \retval order A writable node map. The values will be set from 0 to 1311 /// the number of the nodes in the digraph minus one. Each value of the 1312 /// map will be set exactly once, and the values will be set descending 1313 /// order. 1314 /// 1315 /// \see dag(), checkedTopologicalSort() 1316 template <typename Digraph, typename NodeMap> 1317 void topologicalSort(const Digraph& digraph, NodeMap& order) { 1318 using namespace _connectivity_bits; 1319 1320 checkConcept<concepts::Digraph, Digraph>(); 1321 checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>(); 1322 1323 typedef typename Digraph::Node Node; 1324 typedef typename Digraph::NodeIt NodeIt; 1325 typedef typename Digraph::Arc Arc; 1326 1214 1327 TopologicalSortVisitor<Digraph, NodeMap> 1215 visitor(order, countNodes( graph));1328 visitor(order, countNodes(digraph)); 1216 1329 1217 1330 DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> > 1218 dfs( graph, visitor);1331 dfs(digraph, visitor); 1219 1332 1220 1333 dfs.init(); 1221 for (NodeIt it( graph); it != INVALID; ++it) {1334 for (NodeIt it(digraph); it != INVALID; ++it) { 1222 1335 if (!dfs.reached(it)) { 1223 1336 dfs.addSource(it); … … 1231 1344 /// \brief Sort the nodes of a DAG into topolgical order. 1232 1345 /// 1233 /// Sort the nodes of a DAG into topolgical order. It also checks1234 /// that the given graph is DAG.1235 /// 1236 /// \param digraph The graph. It must be directed and acyclic.1237 /// \ retval order A readable - writable node map. The values will be set1238 /// from 0 to the number of the nodes in the graph minus one. Each values1239 /// of the map will be set exactly once, the values will be set descending1240 /// order.1241 /// \return \c false when the graph is not DAG.1242 /// 1243 /// \see topologicalSort1244 /// \see dag 1346 /// This function sorts the nodes of the given acyclic digraph (DAG) 1347 /// into topolgical order and also checks whether the given digraph 1348 /// is DAG. 1349 /// 1350 /// \param digraph The digraph. 1351 /// \retval order A readable and writable node map. The values will be 1352 /// set from 0 to the number of the nodes in the digraph minus one. 1353 /// Each value of the map will be set exactly once, and the values will 1354 /// be set descending order. 1355 /// \return \c false if the digraph is not DAG. 1356 /// 1357 /// \see dag(), topologicalSort() 1245 1358 template <typename Digraph, typename NodeMap> 1246 1359 bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) { … … 1284 1397 /// \ingroup graph_properties 1285 1398 /// 1286 /// \brief Check that the given directed graph is a DAG. 1287 /// 1288 /// Check that the given directed graph is a DAG. The DAG is 1289 /// an Directed Acyclic Digraph. 1290 /// \return \c false when the graph is not DAG. 1291 /// \see acyclic 1292 template <typename Digraph> 1293 bool dag(const Digraph& digraph) { 1294 1295 checkConcept<concepts::Digraph, Digraph>(); 1296 1297 typedef typename Digraph::Node Node; 1298 typedef typename Digraph::NodeIt NodeIt; 1299 typedef typename Digraph::Arc Arc; 1300 1301 typedef typename Digraph::template NodeMap<bool> ProcessedMap; 1302 1303 typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>:: 1304 Create dfs(digraph); 1305 1306 ProcessedMap processed(digraph); 1307 dfs.processedMap(processed); 1308 1309 dfs.init(); 1310 for (NodeIt it(digraph); it != INVALID; ++it) { 1311 if (!dfs.reached(it)) { 1312 dfs.addSource(it); 1313 while (!dfs.emptyQueue()) { 1314 Arc edge = dfs.nextArc(); 1315 Node target = digraph.target(edge); 1316 if (dfs.reached(target) && !processed[target]) { 1317 return false; 1318 } 1319 dfs.processNextArc(); 1320 } 1321 } 1322 } 1323 return true; 1324 } 1325 1326 /// \ingroup graph_properties 1327 /// 1328 /// \brief Check that the given undirected graph is acyclic. 1329 /// 1330 /// Check that the given undirected graph acyclic. 1331 /// \param graph The undirected graph. 1332 /// \return \c true when there is no circle in the graph. 1333 /// \see dag 1399 /// \brief Check whether an undirected graph is acyclic. 1400 /// 1401 /// This function checks whether the given undirected graph is acyclic. 1402 /// \return \c true if there is no cycle in the graph. 1403 /// \see dag() 1334 1404 template <typename Graph> 1335 1405 bool acyclic(const Graph& graph) { … … 1344 1414 dfs.addSource(it); 1345 1415 while (!dfs.emptyQueue()) { 1346 Arc edge= dfs.nextArc();1347 Node source = graph.source( edge);1348 Node target = graph.target( edge);1416 Arc arc = dfs.nextArc(); 1417 Node source = graph.source(arc); 1418 Node target = graph.target(arc); 1349 1419 if (dfs.reached(target) && 1350 dfs.predArc(source) != graph.oppositeArc( edge)) {1420 dfs.predArc(source) != graph.oppositeArc(arc)) { 1351 1421 return false; 1352 1422 } … … 1360 1430 /// \ingroup graph_properties 1361 1431 /// 1362 /// \brief Check that the given undirected graph is tree.1363 /// 1364 /// Check thatthe given undirected graph is tree.1365 /// \ param graph The undirected graph.1366 /// \ return \c true when the graph is acyclic and connected.1432 /// \brief Check whether an undirected graph is tree. 1433 /// 1434 /// This function checks whether the given undirected graph is tree. 1435 /// \return \c true if the graph is acyclic and connected. 1436 /// \see acyclic(), connected() 1367 1437 template <typename Graph> 1368 1438 bool tree(const Graph& graph) { … … 1371 1441 typedef typename Graph::NodeIt NodeIt; 1372 1442 typedef typename Graph::Arc Arc; 1443 if (NodeIt(graph) == INVALID) return true; 1373 1444 Dfs<Graph> dfs(graph); 1374 1445 dfs.init(); 1375 1446 dfs.addSource(NodeIt(graph)); 1376 1447 while (!dfs.emptyQueue()) { 1377 Arc edge= dfs.nextArc();1378 Node source = graph.source( edge);1379 Node target = graph.target( edge);1448 Arc arc = dfs.nextArc(); 1449 Node source = graph.source(arc); 1450 Node target = graph.target(arc); 1380 1451 if (dfs.reached(target) && 1381 dfs.predArc(source) != graph.oppositeArc( edge)) {1452 dfs.predArc(source) != graph.oppositeArc(arc)) { 1382 1453 return false; 1383 1454 } … … 1452 1523 /// \ingroup graph_properties 1453 1524 /// 1454 /// \brief Check if the given undirected graph is bipartite or not 1455 /// 1456 /// The function checks if the given undirected \c graph graph is bipartite 1457 /// or not. The \ref Bfs algorithm is used to calculate the result. 1458 /// \param graph The undirected graph. 1459 /// \return \c true if \c graph is bipartite, \c false otherwise. 1460 /// \sa bipartitePartitions 1525 /// \brief Check whether an undirected graph is bipartite. 1526 /// 1527 /// The function checks whether the given undirected graph is bipartite. 1528 /// \return \c true if the graph is bipartite. 1529 /// 1530 /// \see bipartitePartitions() 1461 1531 template<typename Graph> 1462 inlinebool bipartite(const Graph &graph){1532 bool bipartite(const Graph &graph){ 1463 1533 using namespace _connectivity_bits; 1464 1534 … … 1489 1559 /// \ingroup graph_properties 1490 1560 /// 1491 /// \brief Check if the given undirected graph is bipartite or not 1492 /// 1493 /// The function checks if the given undirected graph is bipartite 1494 /// or not. The \ref Bfs algorithm is used to calculate the result. 1495 /// During the execution, the \c partMap will be set as the two 1496 /// partitions of the graph. 1561 /// \brief Find the bipartite partitions of an undirected graph. 1562 /// 1563 /// This function checks whether the given undirected graph is bipartite 1564 /// and gives back the bipartite partitions. 1497 1565 /// 1498 1566 /// \image html bipartite_partitions.png … … 1500 1568 /// 1501 1569 /// \param graph The undirected graph. 1502 /// \retval partMap A writable bool map of nodes. It will be set as the 1503 /// two partitions of the graph. 1504 /// \return \c true if \c graph is bipartite, \c false otherwise. 1570 /// \retval partMap A writable node map of \c bool (or convertible) value 1571 /// type. The values will be set to \c true for one component and 1572 /// \c false for the other one. 1573 /// \return \c true if the graph is bipartite, \c false otherwise. 1574 /// 1575 /// \see bipartite() 1505 1576 template<typename Graph, typename NodeMap> 1506 inlinebool bipartitePartitions(const Graph &graph, NodeMap &partMap){1577 bool bipartitePartitions(const Graph &graph, NodeMap &partMap){ 1507 1578 using namespace _connectivity_bits; 1508 1579 1509 1580 checkConcept<concepts::Graph, Graph>(); 1581 checkConcept<concepts::WriteMap<typename Graph::Node, bool>, NodeMap>(); 1510 1582 1511 1583 typedef typename Graph::Node Node; … … 1532 1604 } 1533 1605 1534 /// \brief Returns true when there are not loop edges in the graph. 1535 /// 1536 /// Returns true when there are not loop edges in the graph. 1537 template <typename Digraph> 1538 bool loopFree(const Digraph& digraph) { 1539 for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) { 1540 if (digraph.source(it) == digraph.target(it)) return false; 1606 /// \ingroup graph_properties 1607 /// 1608 /// \brief Check whether the given graph contains no loop arcs/edges. 1609 /// 1610 /// This function returns \c true if there are no loop arcs/edges in 1611 /// the given graph. It works for both directed and undirected graphs. 1612 template <typename Graph> 1613 bool loopFree(const Graph& graph) { 1614 for (typename Graph::ArcIt it(graph); it != INVALID; ++it) { 1615 if (graph.source(it) == graph.target(it)) return false; 1541 1616 } 1542 1617 return true; 1543 1618 } 1544 1619 1545 /// \brief Returns true when there are not parallel edges in the graph. 1546 /// 1547 /// Returns true when there are not parallel edges in the graph. 1548 template <typename Digraph> 1549 bool parallelFree(const Digraph& digraph) { 1550 typename Digraph::template NodeMap<bool> reached(digraph, false); 1551 for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) { 1552 for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { 1553 if (reached[digraph.target(a)]) return false; 1554 reached.set(digraph.target(a), true); 1555 } 1556 for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { 1557 reached.set(digraph.target(a), false); 1558 } 1620 /// \ingroup graph_properties 1621 /// 1622 /// \brief Check whether the given graph contains no parallel arcs/edges. 1623 /// 1624 /// This function returns \c true if there are no parallel arcs/edges in 1625 /// the given graph. It works for both directed and undirected graphs. 1626 template <typename Graph> 1627 bool parallelFree(const Graph& graph) { 1628 typename Graph::template NodeMap<int> reached(graph, 0); 1629 int cnt = 1; 1630 for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { 1631 for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) { 1632 if (reached[graph.target(a)] == cnt) return false; 1633 reached[graph.target(a)] = cnt; 1634 } 1635 ++cnt; 1559 1636 } 1560 1637 return true; 1561 1638 } 1562 1639 1563 /// \brief Returns true when there are not loop edges and parallel 1564 /// edges in the graph. 1565 /// 1566 /// Returns true when there are not loop edges and parallel edges in 1567 /// the graph. 1568 template <typename Digraph> 1569 bool simpleDigraph(const Digraph& digraph) { 1570 typename Digraph::template NodeMap<bool> reached(digraph, false); 1571 for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) { 1572 reached.set(n, true); 1573 for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { 1574 if (reached[digraph.target(a)]) return false; 1575 reached.set(digraph.target(a), true); 1576 } 1577 for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { 1578 reached.set(digraph.target(a), false); 1579 } 1580 reached.set(n, false); 1640 /// \ingroup graph_properties 1641 /// 1642 /// \brief Check whether the given graph is simple. 1643 /// 1644 /// This function returns \c true if the given graph is simple, i.e. 1645 /// it contains no loop arcs/edges and no parallel arcs/edges. 1646 /// The function works for both directed and undirected graphs. 1647 /// \see loopFree(), parallelFree() 1648 template <typename Graph> 1649 bool simpleGraph(const Graph& graph) { 1650 typename Graph::template NodeMap<int> reached(graph, 0); 1651 int cnt = 1; 1652 for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { 1653 reached[n] = cnt; 1654 for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) { 1655 if (reached[graph.target(a)] == cnt) return false; 1656 reached[graph.target(a)] = cnt; 1657 } 1658 ++cnt; 1581 1659 } 1582 1660 return true; -
lemon/edge_set.h
r664 r707 23 23 #include <lemon/bits/edge_set_extender.h> 24 24 25 /// \ingroup semi_adaptors25 /// \ingroup graphs 26 26 /// \file 27 27 /// \brief ArcSet and EdgeSet classes. … … 231 231 }; 232 232 233 /// \ingroup semi_adaptors233 /// \ingroup graphs 234 234 /// 235 235 /// \brief Digraph using a node set of another digraph or graph and … … 655 655 }; 656 656 657 /// \ingroup semi_adaptors657 /// \ingroup graphs 658 658 /// 659 659 /// \brief Graph using a node set of another digraph or graph and an … … 914 914 915 915 916 /// \ingroup semi_adaptors916 /// \ingroup graphs 917 917 /// 918 918 /// \brief Digraph using a node set of another digraph or graph and … … 1258 1258 }; 1259 1259 1260 /// \ingroup semi_adaptors1260 /// \ingroup graphs 1261 1261 /// 1262 1262 /// \brief Graph using a node set of another digraph or graph and an -
lemon/euler.h
r639 r695 245 245 246 246 247 ///Check if the given graph is \eEulerian247 ///Check if the given graph is Eulerian 248 248 249 249 /// \ingroup graph_properties 250 ///This function checks if the given graph is \eEulerian.250 ///This function checks if the given graph is Eulerian. 251 251 ///It works for both directed and undirected graphs. 252 252 /// -
lemon/glpk.h
r623 r697 27 27 28 28 // forward declaration 29 #if ndef _GLP_PROB29 #if !defined _GLP_PROB && !defined GLP_PROB 30 30 #define _GLP_PROB 31 typedef struct { double _prob; } glp_prob; 31 #define GLP_PROB 32 typedef struct { double _opaque_prob; } glp_prob; 32 33 /* LP/MIP problem object */ 33 34 #endif -
lemon/lemon.pc.in
r692 r705 5 5 6 6 Name: @PACKAGE_NAME@ 7 Description: Library of Efficient Modelsand Optimization in Networks7 Description: Library for Efficient Modeling and Optimization in Networks 8 8 Version: @PACKAGE_VERSION@ 9 9 Libs: -L${libdir} -lemon @GLPK_LIBS@ @CPLEX_LIBS@ @SOPLEX_LIBS@ @CLP_LIBS@ @CBC_LIBS@ -
lemon/matching.h
r641 r698 500 500 /// This function runs the original Edmonds' algorithm. 501 501 /// 502 /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be502 /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be 503 503 /// called before using this function. 504 504 void startSparse() { … … 519 519 /// shrinks, therefore resulting in a faster algorithm for dense graphs. 520 520 /// 521 /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be521 /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be 522 522 /// called before using this function. 523 523 void startDense() { -
lemon/network_simplex.h
r690 r710 20 20 #define LEMON_NETWORK_SIMPLEX_H 21 21 22 /// \ingroup min_cost_flow 22 /// \ingroup min_cost_flow_algs 23 23 /// 24 24 /// \file … … 34 34 namespace lemon { 35 35 36 /// \addtogroup min_cost_flow 36 /// \addtogroup min_cost_flow_algs 37 37 /// @{ 38 38 … … 103 103 /// constraints of the \ref min_cost_flow "minimum cost flow problem". 104 104 /// 105 /// The default supply type is \c GEQ, since this form is supported 106 /// by other minimum cost flow algorithms and the \ref Circulation 107 /// algorithm, as well. 108 /// The \c LEQ problem type can be selected using the \ref supplyType() 109 /// function. 110 /// 111 /// Note that the equality form is a special case of both supply types. 105 /// The default supply type is \c GEQ, the \c LEQ type can be 106 /// selected using \ref supplyType(). 107 /// The equality form is a special case of both supply types. 112 108 enum SupplyType { 113 114 109 /// This option means that there are <em>"greater or equal"</em> 115 /// supply/demand constraints in the definition, i.e. the exact 116 /// formulation of the problem is the following. 117 /** 118 \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f] 119 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq 120 sup(u) \quad \forall u\in V \f] 121 \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f] 122 */ 123 /// It means that the total demand must be greater or equal to the 124 /// total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or 125 /// negative) and all the supplies have to be carried out from 126 /// the supply nodes, but there could be demands that are not 127 /// satisfied. 110 /// supply/demand constraints in the definition of the problem. 128 111 GEQ, 129 /// It is just an alias for the \c GEQ option.130 CARRY_SUPPLIES = GEQ,131 132 112 /// This option means that there are <em>"less or equal"</em> 133 /// supply/demand constraints in the definition, i.e. the exact 134 /// formulation of the problem is the following. 135 /** 136 \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f] 137 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq 138 sup(u) \quad \forall u\in V \f] 139 \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f] 140 */ 141 /// It means that the total demand must be less or equal to the 142 /// total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or 143 /// positive) and all the demands have to be satisfied, but there 144 /// could be supplies that are not carried out from the supply 145 /// nodes. 146 LEQ, 147 /// It is just an alias for the \c LEQ option. 148 SATISFY_DEMANDS = LEQ 113 /// supply/demand constraints in the definition of the problem. 114 LEQ 149 115 }; 150 116 … … 216 182 int _node_num; 217 183 int _arc_num; 184 int _all_arc_num; 185 int _search_arc_num; 218 186 219 187 // Parameters of the problem … … 278 246 const CostVector &_pi; 279 247 int &_in_arc; 280 int _ arc_num;248 int _search_arc_num; 281 249 282 250 // Pivot rule data … … 289 257 _source(ns._source), _target(ns._target), 290 258 _cost(ns._cost), _state(ns._state), _pi(ns._pi), 291 _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0) 259 _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num), 260 _next_arc(0) 292 261 {} 293 262 … … 295 264 bool findEnteringArc() { 296 265 Cost c; 297 for (int e = _next_arc; e < _ arc_num; ++e) {266 for (int e = _next_arc; e < _search_arc_num; ++e) { 298 267 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 299 268 if (c < 0) { … … 329 298 const CostVector &_pi; 330 299 int &_in_arc; 331 int _ arc_num;300 int _search_arc_num; 332 301 333 302 public: … … 337 306 _source(ns._source), _target(ns._target), 338 307 _cost(ns._cost), _state(ns._state), _pi(ns._pi), 339 _in_arc(ns.in_arc), _ arc_num(ns._arc_num)308 _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num) 340 309 {} 341 310 … … 343 312 bool findEnteringArc() { 344 313 Cost c, min = 0; 345 for (int e = 0; e < _ arc_num; ++e) {314 for (int e = 0; e < _search_arc_num; ++e) { 346 315 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 347 316 if (c < min) { … … 368 337 const CostVector &_pi; 369 338 int &_in_arc; 370 int _ arc_num;339 int _search_arc_num; 371 340 372 341 // Pivot rule data … … 380 349 _source(ns._source), _target(ns._target), 381 350 _cost(ns._cost), _state(ns._state), _pi(ns._pi), 382 _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0) 351 _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num), 352 _next_arc(0) 383 353 { 384 354 // The main parameters of the pivot rule 385 const double BLOCK_SIZE_FACTOR = 2.0;355 const double BLOCK_SIZE_FACTOR = 0.5; 386 356 const int MIN_BLOCK_SIZE = 10; 387 357 388 358 _block_size = std::max( int(BLOCK_SIZE_FACTOR * 389 std::sqrt(double(_ arc_num))),359 std::sqrt(double(_search_arc_num))), 390 360 MIN_BLOCK_SIZE ); 391 361 } … … 396 366 int cnt = _block_size; 397 367 int e, min_arc = _next_arc; 398 for (e = _next_arc; e < _ arc_num; ++e) {368 for (e = _next_arc; e < _search_arc_num; ++e) { 399 369 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 400 370 if (c < min) { … … 441 411 const CostVector &_pi; 442 412 int &_in_arc; 443 int _ arc_num;413 int _search_arc_num; 444 414 445 415 // Pivot rule data … … 455 425 _source(ns._source), _target(ns._target), 456 426 _cost(ns._cost), _state(ns._state), _pi(ns._pi), 457 _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0) 427 _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num), 428 _next_arc(0) 458 429 { 459 430 // The main parameters of the pivot rule … … 464 435 465 436 _list_length = std::max( int(LIST_LENGTH_FACTOR * 466 std::sqrt(double(_ arc_num))),437 std::sqrt(double(_search_arc_num))), 467 438 MIN_LIST_LENGTH ); 468 439 _minor_limit = std::max( int(MINOR_LIMIT_FACTOR * _list_length), … … 501 472 min = 0; 502 473 _curr_length = 0; 503 for (e = _next_arc; e < _ arc_num; ++e) {474 for (e = _next_arc; e < _search_arc_num; ++e) { 504 475 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 505 476 if (c < 0) { … … 547 518 const CostVector &_pi; 548 519 int &_in_arc; 549 int _ arc_num;520 int _search_arc_num; 550 521 551 522 // Pivot rule data … … 575 546 _source(ns._source), _target(ns._target), 576 547 _cost(ns._cost), _state(ns._state), _pi(ns._pi), 577 _in_arc(ns.in_arc), _ arc_num(ns._arc_num),578 _next_arc(0), _cand_cost(ns._ arc_num), _sort_func(_cand_cost)548 _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num), 549 _next_arc(0), _cand_cost(ns._search_arc_num), _sort_func(_cand_cost) 579 550 { 580 551 // The main parameters of the pivot rule … … 585 556 586 557 _block_size = std::max( int(BLOCK_SIZE_FACTOR * 587 std::sqrt(double(_ arc_num))),558 std::sqrt(double(_search_arc_num))), 588 559 MIN_BLOCK_SIZE ); 589 560 _head_length = std::max( int(HEAD_LENGTH_FACTOR * _block_size), … … 611 582 int limit = _head_length; 612 583 613 for (int e = _next_arc; e < _ arc_num; ++e) {584 for (int e = _next_arc; e < _search_arc_num; ++e) { 614 585 _cand_cost[e] = _state[e] * 615 586 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); … … 679 650 _arc_num = countArcs(_graph); 680 651 int all_node_num = _node_num + 1; 681 int all_arc_num = _arc_num +_node_num;682 683 _source.resize( all_arc_num);684 _target.resize( all_arc_num);685 686 _lower.resize( all_arc_num);687 _upper.resize( all_arc_num);688 _cap.resize( all_arc_num);689 _cost.resize( all_arc_num);652 int max_arc_num = _arc_num + 2 * _node_num; 653 654 _source.resize(max_arc_num); 655 _target.resize(max_arc_num); 656 657 _lower.resize(_arc_num); 658 _upper.resize(_arc_num); 659 _cap.resize(max_arc_num); 660 _cost.resize(max_arc_num); 690 661 _supply.resize(all_node_num); 691 _flow.resize( all_arc_num);662 _flow.resize(max_arc_num); 692 663 _pi.resize(all_node_num); 693 664 … … 699 670 _succ_num.resize(all_node_num); 700 671 _last_succ.resize(all_node_num); 701 _state.resize( all_arc_num);672 _state.resize(max_arc_num); 702 673 703 674 // Copy the graph (store the arcs in a mixed order) … … 1070 1041 Cost ART_COST; 1071 1042 if (std::numeric_limits<Cost>::is_exact) { 1072 ART_COST = std::numeric_limits<Cost>::max() / 4+ 1;1043 ART_COST = std::numeric_limits<Cost>::max() / 2 + 1; 1073 1044 } else { 1074 1045 ART_COST = std::numeric_limits<Cost>::min(); … … 1094 1065 _last_succ[_root] = _root - 1; 1095 1066 _supply[_root] = -_sum_supply; 1096 _pi[_root] = _sum_supply < 0 ? -ART_COST : ART_COST;1067 _pi[_root] = 0; 1097 1068 1098 1069 // Add artificial arcs and initialize the spanning tree data structure 1099 for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) { 1100 _parent[u] = _root; 1101 _pred[u] = e; 1102 _thread[u] = u + 1; 1103 _rev_thread[u + 1] = u; 1104 _succ_num[u] = 1; 1105 _last_succ[u] = u; 1106 _cost[e] = ART_COST; 1107 _cap[e] = INF; 1108 _state[e] = STATE_TREE; 1109 if (_supply[u] > 0 || (_supply[u] == 0 && _sum_supply <= 0)) { 1110 _flow[e] = _supply[u]; 1111 _forward[u] = true; 1112 _pi[u] = -ART_COST + _pi[_root]; 1113 } else { 1114 _flow[e] = -_supply[u]; 1115 _forward[u] = false; 1116 _pi[u] = ART_COST + _pi[_root]; 1117 } 1070 if (_sum_supply == 0) { 1071 // EQ supply constraints 1072 _search_arc_num = _arc_num; 1073 _all_arc_num = _arc_num + _node_num; 1074 for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) { 1075 _parent[u] = _root; 1076 _pred[u] = e; 1077 _thread[u] = u + 1; 1078 _rev_thread[u + 1] = u; 1079 _succ_num[u] = 1; 1080 _last_succ[u] = u; 1081 _cap[e] = INF; 1082 _state[e] = STATE_TREE; 1083 if (_supply[u] >= 0) { 1084 _forward[u] = true; 1085 _pi[u] = 0; 1086 _source[e] = u; 1087 _target[e] = _root; 1088 _flow[e] = _supply[u]; 1089 _cost[e] = 0; 1090 } else { 1091 _forward[u] = false; 1092 _pi[u] = ART_COST; 1093 _source[e] = _root; 1094 _target[e] = u; 1095 _flow[e] = -_supply[u]; 1096 _cost[e] = ART_COST; 1097 } 1098 } 1099 } 1100 else if (_sum_supply > 0) { 1101 // LEQ supply constraints 1102 _search_arc_num = _arc_num + _node_num; 1103 int f = _arc_num + _node_num; 1104 for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) { 1105 _parent[u] = _root; 1106 _thread[u] = u + 1; 1107 _rev_thread[u + 1] = u; 1108 _succ_num[u] = 1; 1109 _last_succ[u] = u; 1110 if (_supply[u] >= 0) { 1111 _forward[u] = true; 1112 _pi[u] = 0; 1113 _pred[u] = e; 1114 _source[e] = u; 1115 _target[e] = _root; 1116 _cap[e] = INF; 1117 _flow[e] = _supply[u]; 1118 _cost[e] = 0; 1119 _state[e] = STATE_TREE; 1120 } else { 1121 _forward[u] = false; 1122 _pi[u] = ART_COST; 1123 _pred[u] = f; 1124 _source[f] = _root; 1125 _target[f] = u; 1126 _cap[f] = INF; 1127 _flow[f] = -_supply[u]; 1128 _cost[f] = ART_COST; 1129 _state[f] = STATE_TREE; 1130 _source[e] = u; 1131 _target[e] = _root; 1132 _cap[e] = INF; 1133 _flow[e] = 0; 1134 _cost[e] = 0; 1135 _state[e] = STATE_LOWER; 1136 ++f; 1137 } 1138 } 1139 _all_arc_num = f; 1140 } 1141 else { 1142 // GEQ supply constraints 1143 _search_arc_num = _arc_num + _node_num; 1144 int f = _arc_num + _node_num; 1145 for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) { 1146 _parent[u] = _root; 1147 _thread[u] = u + 1; 1148 _rev_thread[u + 1] = u; 1149 _succ_num[u] = 1; 1150 _last_succ[u] = u; 1151 if (_supply[u] <= 0) { 1152 _forward[u] = false; 1153 _pi[u] = 0; 1154 _pred[u] = e; 1155 _source[e] = _root; 1156 _target[e] = u; 1157 _cap[e] = INF; 1158 _flow[e] = -_supply[u]; 1159 _cost[e] = 0; 1160 _state[e] = STATE_TREE; 1161 } else { 1162 _forward[u] = true; 1163 _pi[u] = -ART_COST; 1164 _pred[u] = f; 1165 _source[f] = u; 1166 _target[f] = _root; 1167 _cap[f] = INF; 1168 _flow[f] = _supply[u]; 1169 _state[f] = STATE_TREE; 1170 _cost[f] = ART_COST; 1171 _source[e] = _root; 1172 _target[e] = u; 1173 _cap[e] = INF; 1174 _flow[e] = 0; 1175 _cost[e] = 0; 1176 _state[e] = STATE_LOWER; 1177 ++f; 1178 } 1179 } 1180 _all_arc_num = f; 1118 1181 } 1119 1182 … … 1375 1438 1376 1439 // Check feasibility 1377 if (_sum_supply < 0) { 1378 for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) { 1379 if (_supply[u] >= 0 && _flow[e] != 0) return INFEASIBLE; 1380 } 1381 } 1382 else if (_sum_supply > 0) { 1383 for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) { 1384 if (_supply[u] <= 0 && _flow[e] != 0) return INFEASIBLE; 1385 } 1386 } 1387 else { 1388 for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) { 1389 if (_flow[e] != 0) return INFEASIBLE; 1390 } 1440 for (int e = _search_arc_num; e != _all_arc_num; ++e) { 1441 if (_flow[e] != 0) return INFEASIBLE; 1391 1442 } 1392 1443 … … 1402 1453 } 1403 1454 } 1455 1456 // Shift potentials to meet the requirements of the GEQ/LEQ type 1457 // optimality conditions 1458 if (_sum_supply == 0) { 1459 if (_stype == GEQ) { 1460 Cost max_pot = std::numeric_limits<Cost>::min(); 1461 for (int i = 0; i != _node_num; ++i) { 1462 if (_pi[i] > max_pot) max_pot = _pi[i]; 1463 } 1464 if (max_pot > 0) { 1465 for (int i = 0; i != _node_num; ++i) 1466 _pi[i] -= max_pot; 1467 } 1468 } else { 1469 Cost min_pot = std::numeric_limits<Cost>::max(); 1470 for (int i = 0; i != _node_num; ++i) { 1471 if (_pi[i] < min_pot) min_pot = _pi[i]; 1472 } 1473 if (min_pot < 0) { 1474 for (int i = 0; i != _node_num; ++i) 1475 _pi[i] -= min_pot; 1476 } 1477 } 1478 } 1404 1479 1405 1480 return OPTIMAL; -
scripts/unify-sources.sh
r675 r702 7 7 if [ -n "$(hg st $1)" ]; then 8 8 echo $YEAR 9 else 10 hg log -l 1 --template='{date|isodate}\n' $1 | 11 cut -d '-' -f 1 12 fi 9 13 } 10 14 -
test/CMakeLists.txt
r674 r696 10 10 bfs_test 11 11 circulation_test 12 connectivity_test 12 13 counter_test 13 14 dfs_test -
test/Makefile.am
r658 r696 10 10 test/bfs_test \ 11 11 test/circulation_test \ 12 test/connectivity_test \ 12 13 test/counter_test \ 13 14 test/dfs_test \ … … 55 56 test_circulation_test_SOURCES = test/circulation_test.cc 56 57 test_counter_test_SOURCES = test/counter_test.cc 58 test_connectivity_test_SOURCES = test/connectivity_test.cc 57 59 test_dfs_test_SOURCES = test/dfs_test.cc 58 60 test_digraph_test_SOURCES = test/digraph_test.cc -
test/min_cost_flow_test.cc
r689 r711 175 175 bool checkPotential( const GR& gr, const LM& lower, const UM& upper, 176 176 const CM& cost, const SM& supply, const FM& flow, 177 const PM& pi )177 const PM& pi, SupplyType type ) 178 178 { 179 179 TEMPLATE_DIGRAPH_TYPEDEFS(GR); … … 194 194 for (InArcIt e(gr, n); e != INVALID; ++e) 195 195 sum -= flow[e]; 196 opt = (sum == supply[n]) || (pi[n] == 0); 196 if (type != LEQ) { 197 opt = (pi[n] <= 0) && (sum == supply[n] || pi[n] == 0); 198 } else { 199 opt = (pi[n] >= 0) && (sum == supply[n] || pi[n] == 0); 200 } 197 201 } 198 202 199 203 return opt; 204 } 205 206 // Check whether the dual cost is equal to the primal cost 207 template < typename GR, typename LM, typename UM, 208 typename CM, typename SM, typename PM > 209 bool checkDualCost( const GR& gr, const LM& lower, const UM& upper, 210 const CM& cost, const SM& supply, const PM& pi, 211 typename CM::Value total ) 212 { 213 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 214 215 typename CM::Value dual_cost = 0; 216 SM red_supply(gr); 217 for (NodeIt n(gr); n != INVALID; ++n) { 218 red_supply[n] = supply[n]; 219 } 220 for (ArcIt a(gr); a != INVALID; ++a) { 221 if (lower[a] != 0) { 222 dual_cost += lower[a] * cost[a]; 223 red_supply[gr.source(a)] -= lower[a]; 224 red_supply[gr.target(a)] += lower[a]; 225 } 226 } 227 228 for (NodeIt n(gr); n != INVALID; ++n) { 229 dual_cost -= red_supply[n] * pi[n]; 230 } 231 for (ArcIt a(gr); a != INVALID; ++a) { 232 typename CM::Value red_cost = 233 cost[a] + pi[gr.source(a)] - pi[gr.target(a)]; 234 dual_cost -= (upper[a] - lower[a]) * std::max(-red_cost, 0); 235 } 236 237 return dual_cost == total; 200 238 } 201 239 … … 221 259 "The flow is not feasible " + test_id); 222 260 check(mcf.totalCost() == total, "The flow is not optimal " + test_id); 223 check(checkPotential(gr, lower, upper, cost, supply, flow, pi ),261 check(checkPotential(gr, lower, upper, cost, supply, flow, pi, type), 224 262 "Wrong potentials " + test_id); 263 check(checkDualCost(gr, lower, upper, cost, supply, pi, total), 264 "Wrong dual cost " + test_id); 225 265 } 226 266 } … … 267 307 .run(); 268 308 269 // Build a test digraph for testing negative costs 270 Digraph ngr; 271 Node n1 = ngr.addNode(); 272 Node n2 = ngr.addNode(); 273 Node n3 = ngr.addNode(); 274 Node n4 = ngr.addNode(); 275 Node n5 = ngr.addNode(); 276 Node n6 = ngr.addNode(); 277 Node n7 = ngr.addNode(); 278 279 Arc a1 = ngr.addArc(n1, n2); 280 Arc a2 = ngr.addArc(n1, n3); 281 Arc a3 = ngr.addArc(n2, n4); 282 Arc a4 = ngr.addArc(n3, n4); 283 Arc a5 = ngr.addArc(n3, n2); 284 Arc a6 = ngr.addArc(n5, n3); 285 Arc a7 = ngr.addArc(n5, n6); 286 Arc a8 = ngr.addArc(n6, n7); 287 Arc a9 = ngr.addArc(n7, n5); 288 289 Digraph::ArcMap<int> nc(ngr), nl1(ngr, 0), nl2(ngr, 0); 290 ConstMap<Arc, int> nu1(std::numeric_limits<int>::max()), nu2(5000); 291 Digraph::NodeMap<int> ns(ngr, 0); 292 293 nl2[a7] = 1000; 294 nl2[a8] = -1000; 295 296 ns[n1] = 100; 297 ns[n4] = -100; 298 299 nc[a1] = 100; 300 nc[a2] = 30; 301 nc[a3] = 20; 302 nc[a4] = 80; 303 nc[a5] = 50; 304 nc[a6] = 10; 305 nc[a7] = 80; 306 nc[a8] = 30; 307 nc[a9] = -120; 309 // Build test digraphs with negative costs 310 Digraph neg_gr; 311 Node n1 = neg_gr.addNode(); 312 Node n2 = neg_gr.addNode(); 313 Node n3 = neg_gr.addNode(); 314 Node n4 = neg_gr.addNode(); 315 Node n5 = neg_gr.addNode(); 316 Node n6 = neg_gr.addNode(); 317 Node n7 = neg_gr.addNode(); 318 319 Arc a1 = neg_gr.addArc(n1, n2); 320 Arc a2 = neg_gr.addArc(n1, n3); 321 Arc a3 = neg_gr.addArc(n2, n4); 322 Arc a4 = neg_gr.addArc(n3, n4); 323 Arc a5 = neg_gr.addArc(n3, n2); 324 Arc a6 = neg_gr.addArc(n5, n3); 325 Arc a7 = neg_gr.addArc(n5, n6); 326 Arc a8 = neg_gr.addArc(n6, n7); 327 Arc a9 = neg_gr.addArc(n7, n5); 328 329 Digraph::ArcMap<int> neg_c(neg_gr), neg_l1(neg_gr, 0), neg_l2(neg_gr, 0); 330 ConstMap<Arc, int> neg_u1(std::numeric_limits<int>::max()), neg_u2(5000); 331 Digraph::NodeMap<int> neg_s(neg_gr, 0); 332 333 neg_l2[a7] = 1000; 334 neg_l2[a8] = -1000; 335 336 neg_s[n1] = 100; 337 neg_s[n4] = -100; 338 339 neg_c[a1] = 100; 340 neg_c[a2] = 30; 341 neg_c[a3] = 20; 342 neg_c[a4] = 80; 343 neg_c[a5] = 50; 344 neg_c[a6] = 10; 345 neg_c[a7] = 80; 346 neg_c[a8] = 30; 347 neg_c[a9] = -120; 348 349 Digraph negs_gr; 350 Digraph::NodeMap<int> negs_s(negs_gr); 351 Digraph::ArcMap<int> negs_c(negs_gr); 352 ConstMap<Arc, int> negs_l(0), negs_u(1000); 353 n1 = negs_gr.addNode(); 354 n2 = negs_gr.addNode(); 355 negs_s[n1] = 100; 356 negs_s[n2] = -300; 357 negs_c[negs_gr.addArc(n1, n2)] = -1; 358 308 359 309 360 // A. Test NetworkSimplex with the default pivot rule … … 343 394 checkMcf(mcf, mcf.lowerMap(l2).run(), 344 395 gr, l2, u, c, s5, mcf.OPTIMAL, true, 4540, "#A11", GEQ); 345 mcf.supply Type(mcf.CARRY_SUPPLIES).supplyMap(s6);396 mcf.supplyMap(s6); 346 397 checkMcf(mcf, mcf.run(), 347 398 gr, l2, u, c, s6, mcf.INFEASIBLE, false, 0, "#A12", GEQ); … … 354 405 checkMcf(mcf, mcf.lowerMap(l2).run(), 355 406 gr, l2, u, c, s6, mcf.OPTIMAL, true, 5930, "#A14", LEQ); 356 mcf.supply Type(mcf.SATISFY_DEMANDS).supplyMap(s5);407 mcf.supplyMap(s5); 357 408 checkMcf(mcf, mcf.run(), 358 409 gr, l2, u, c, s5, mcf.INFEASIBLE, false, 0, "#A15", LEQ); 359 410 360 411 // Check negative costs 361 NetworkSimplex<Digraph> nmcf(ngr); 362 nmcf.lowerMap(nl1).costMap(nc).supplyMap(ns); 363 checkMcf(nmcf, nmcf.run(), 364 ngr, nl1, nu1, nc, ns, nmcf.UNBOUNDED, false, 0, "#A16"); 365 checkMcf(nmcf, nmcf.upperMap(nu2).run(), 366 ngr, nl1, nu2, nc, ns, nmcf.OPTIMAL, true, -40000, "#A17"); 367 nmcf.reset().lowerMap(nl2).costMap(nc).supplyMap(ns); 368 checkMcf(nmcf, nmcf.run(), 369 ngr, nl2, nu1, nc, ns, nmcf.UNBOUNDED, false, 0, "#A18"); 412 NetworkSimplex<Digraph> neg_mcf(neg_gr); 413 neg_mcf.lowerMap(neg_l1).costMap(neg_c).supplyMap(neg_s); 414 checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u1, 415 neg_c, neg_s, neg_mcf.UNBOUNDED, false, 0, "#A16"); 416 neg_mcf.upperMap(neg_u2); 417 checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u2, 418 neg_c, neg_s, neg_mcf.OPTIMAL, true, -40000, "#A17"); 419 neg_mcf.reset().lowerMap(neg_l2).costMap(neg_c).supplyMap(neg_s); 420 checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l2, neg_u1, 421 neg_c, neg_s, neg_mcf.UNBOUNDED, false, 0, "#A18"); 422 423 NetworkSimplex<Digraph> negs_mcf(negs_gr); 424 negs_mcf.costMap(negs_c).supplyMap(negs_s); 425 checkMcf(negs_mcf, negs_mcf.run(), negs_gr, negs_l, negs_u, 426 negs_c, negs_s, negs_mcf.OPTIMAL, true, -300, "#A19", GEQ); 370 427 } 371 428 -
tools/lgf-gen.cc
r670 r701 19 19 /// \ingroup tools 20 20 /// \file 21 /// \brief Special plane digraph generator.21 /// \brief Special plane graph generator. 22 22 /// 23 23 /// Graph generator application for various types of plane graphs. … … 27 27 /// lgf-gen --help 28 28 /// \endcode 29 /// for more info on the usage.29 /// for more information on the usage. 30 30 31 31 #include <algorithm> … … 687 687 .refOption("cities", "Number of cities (default is 1)", num_of_cities) 688 688 .refOption("area", "Full relative area of the cities (default is 1)", area) 689 .refOption("disc", "Nodes are evenly distributed on a unit disc (default)",disc_d) 689 .refOption("disc", "Nodes are evenly distributed on a unit disc (default)", 690 disc_d) 690 691 .optionGroup("dist", "disc") 691 .refOption("square", "Nodes are evenly distributed on a unit square", square_d) 692 .refOption("square", "Nodes are evenly distributed on a unit square", 693 square_d) 692 694 .optionGroup("dist", "square") 693 .refOption("gauss", 694 "Nodes are located according to a two-dim gauss distribution", 695 gauss_d) 695 .refOption("gauss", "Nodes are located according to a two-dim Gauss " 696 "distribution", gauss_d) 696 697 .optionGroup("dist", "gauss") 697 // .mandatoryGroup("dist")698 698 .onlyOneGroup("dist") 699 .boolOption("eps", "Also generate .eps output (prefix.eps)") 700 .boolOption("nonodes", "Draw the edges only in the generated .eps") 701 .boolOption("dir", "Directed digraph is generated (each arcs are replaced by two directed ones)") 702 .boolOption("2con", "Create a two connected planar digraph") 699 .boolOption("eps", "Also generate .eps output (<prefix>.eps)") 700 .boolOption("nonodes", "Draw only the edges in the generated .eps output") 701 .boolOption("dir", "Directed graph is generated (each edge is replaced by " 702 "two directed arcs)") 703 .boolOption("2con", "Create a two connected planar graph") 703 704 .optionGroup("alg","2con") 704 705 .boolOption("tree", "Create a min. cost spanning tree") … … 708 709 .boolOption("tsp2", "Create a TSP tour (tree based)") 709 710 .optionGroup("alg","tsp2") 710 .boolOption("dela", "Delaunay triangulation digraph")711 .boolOption("dela", "Delaunay triangulation graph") 711 712 .optionGroup("alg","dela") 712 713 .onlyOneGroup("alg")
Note: See TracChangeset
for help on using the changeset viewer.