Diff [ee9bac10f58e04dfc86f266cae4a1ad968cd8d20:879fcb781086c50dc6bb528f28ce99a7bfe17bdc] for / – LEMON

CMakeLists.txt

-                      r1017
+                      r1066
 FIND_PACKAGE(Doxygen)
 FIND_PACKAGE(Ghostscript)
+FIND_PACKAGE(GLPK 4.33)
+FIND_PACKAGE(CPLEX)
+FIND_PACKAGE(COIN)
+SET(LEMON_ENABLE_GLPK YES CACHE STRING "Enable GLPK solver backend.")
+SET(LEMON_ENABLE_ILOG YES CACHE STRING "Enable ILOG (CPLEX) solver backend.")
+SET(LEMON_ENABLE_COIN YES CACHE STRING "Enable COIN solver backend.")
+IF(LEMON_ENABLE_GLPK)
+  FIND_PACKAGE(GLPK 4.33)
+ENDIF(LEMON_ENABLE_GLPK)
+IF(LEMON_ENABLE_ILOG)
+  FIND_PACKAGE(ILOG)
+ENDIF(LEMON_ENABLE_ILOG)
+IF(LEMON_ENABLE_COIN)
+  FIND_PACKAGE(COIN)
+ENDIF(LEMON_ENABLE_COIN)
+IF(GLPK_FOUND)
+  SET(LEMON_HAVE_LP TRUE)
+  SET(LEMON_HAVE_MIP TRUE)
+  SET(LEMON_HAVE_GLPK TRUE)
+ENDIF(GLPK_FOUND)
+IF(ILOG_FOUND)
+  SET(LEMON_HAVE_LP TRUE)
+  SET(LEMON_HAVE_MIP TRUE)
+  SET(LEMON_HAVE_CPLEX TRUE)
+ENDIF(ILOG_FOUND)
+IF(COIN_FOUND)
+  SET(LEMON_HAVE_LP TRUE)
+  SET(LEMON_HAVE_MIP TRUE)
+  SET(LEMON_HAVE_CLP TRUE)
+  SET(LEMON_HAVE_CBC TRUE)
+ENDIF(COIN_FOUND)
+IF(ILOG_FOUND)
+  SET(DEFAULT_LP "CPLEX")
+  SET(DEFAULT_MIP "CPLEX")
+ELSEIF(COIN_FOUND)
+  SET(DEFAULT_LP "CLP")
+  SET(DEFAULT_MIP "CBC")
+ELSEIF(GLPK_FOUND)
+  SET(DEFAULT_LP "GLPK")
+  SET(DEFAULT_MIP "GLPK")
+ENDIF()
+IF(NOT LEMON_DEFAULT_LP OR
+    (NOT ILOG_FOUND AND (LEMON_DEFAULT_LP STREQUAL "CPLEX")) OR
+    (NOT COIN_FOUND AND (LEMON_DEFAULT_LP STREQUAL "CLP")) OR
+    (NOT GLPK_FOUND AND (LEMON_DEFAULT_LP STREQUAL "GLPK")))
+  SET(LEMON_DEFAULT_LP ${DEFAULT_LP} CACHE STRING
+    "Default LP solver backend (GLPK, CPLEX or CLP)" FORCE)
+ENDIF()
+IF(NOT LEMON_DEFAULT_MIP OR
+    (NOT ILOG_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "CPLEX")) OR
+    (NOT COIN_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "CBC")) OR
+    (NOT GLPK_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "GLPK")))
+  SET(LEMON_DEFAULT_MIP ${DEFAULT_MIP} CACHE STRING
+    "Default MIP solver backend (GLPK, CPLEX or CBC)" FORCE)
+ENDIF()
 IF(DEFINED ENV{LEMON_CXX_WARNING})

INSTALL

-                      r1040
+                      r1065
+-DLEMON_ENABLE_GLPK=NO
+-DLEMON_ENABLE_COIN=NO
+-DLEMON_ENABLE_ILOG=NO
+  Enable optional third party libraries. They are all enabled by default.
+-DLEMON_DEFAULT_LP=GLPK
+  Sets the default LP solver backend. The supported values are
+  CPLEX, CLP and GLPK. By default, it is set to the first one which
+  is enabled and succesfully discovered.
+-DLEMON_DEFAULT_MIP=GLPK
+  Sets the default MIP solver backend. The supported values are
+  CPLEX, CBC and GLPK. By default, it is set to the first one which
+  is enabled and succesfully discovered.
 -DGLPK_ROOT_DIR=DIRECTORY
 -DCOIN_ROOT_DIR=DIRECTORY
 -DCPLEX_ROOT_DIR=DIRECTORY
+-DILOG_ROOT_DIR=DIRECTORY
   Install root directory prefixes of optional third party libraries.
+  Root directory prefixes of optional third party libraries.
 Makefile Variables

cmake/FindCOIN.cmake

-                      r973
+                      r1064
   COIN_BZ2_LIBRARY
+)
-IF(COIN_FOUND)
-  SET(LEMON_HAVE_LP TRUE)
-  SET(LEMON_HAVE_MIP TRUE)
-  SET(LEMON_HAVE_CLP TRUE)
-  SET(LEMON_HAVE_CBC TRUE)
-ENDIF(COIN_FOUND)

cmake/FindGLPK.cmake

-                      r638
+                      r1064
 MARK_AS_ADVANCED(GLPK_LIBRARY GLPK_INCLUDE_DIR GLPK_BIN_DIR)
-IF(GLPK_FOUND)
-  SET(LEMON_HAVE_LP TRUE)
-  SET(LEMON_HAVE_MIP TRUE)
-  SET(LEMON_HAVE_GLPK TRUE)
-ENDIF(GLPK_FOUND)

doc/CMakeLists.txt

-                      r1041
+                      r1053
     COMMAND ${CMAKE_COMMAND} -E remove_directory gen-images
     COMMAND ${CMAKE_COMMAND} -E make_directory gen-images
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/tsp.png ${CMAKE_CURRENT_SOURCE_DIR}/images/tsp.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r20 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/adaptors2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/adaptors2.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r24 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r24 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r40 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r24 -sOutputFile=gen-images/tsp.png ${CMAKE_CURRENT_SOURCE_DIR}/images/tsp.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
     COMMAND ${CMAKE_COMMAND} -E remove_directory html
-    COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
     COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
     WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}

doc/Doxyfile.in

r1040	r1053
78	78	FILE_VERSION_FILTER =
79	79	LAYOUT_FILE = "@abs_top_srcdir@/doc/DoxygenLayout.xml"
	80	CITE_BIB_FILES = "@abs_top_srcdir@/doc/references.bib"
80	81	#---------------------------------------------------------------------------
81	82	# configuration options related to warning and progress messages

doc/groups.dox

-                      r1038
+                      r1053
 detailed documentation of particular adaptors.
+Since the adaptor classes conform to the \ref graph_concepts "graph concepts",
+an adaptor can even be applied to another one.
+The following image illustrates a situation when a \ref SubDigraph adaptor
+is applied on a digraph and \ref Undirector is applied on the subgraph.
+\image html adaptors2.png
+\image latex adaptors2.eps "Using graph adaptors" width=\textwidth
 The behavior of graph adaptors can be very different. Some of them keep
 capabilities of the original graph while in other cases this would be
 …
 This group contains the common graph search algorithms, namely
 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
 \ref clrs01algorithms.
+\cite clrs01algorithms.
 */
 …
 This group contains the algorithms for finding shortest paths in digraphs
 \ref clrs01algorithms.
+\cite clrs01algorithms.
  - \ref Dijkstra algorithm for finding shortest paths from a source node
 …
 This group contains the algorithms for finding minimum cost spanning
 trees and arborescences \ref clrs01algorithms.
+trees and arborescences \cite clrs01algorithms.
 */
 …
 This group contains the algorithms for finding maximum flows and
 feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
+feasible circulations \cite clrs01algorithms, \cite amo93networkflows.
 The \e maximum \e flow \e problem is to find a flow of maximum value between
 …
 LEMON contains several algorithms for solving maximum flow problems:
 - \ref EdmondsKarp Edmonds-Karp algorithm
   \ref edmondskarp72theoretical.
+  \cite edmondskarp72theoretical.
 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
   \ref goldberg88newapproach.
+  \cite goldberg88newapproach.
 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
   \ref dinic70algorithm, \ref sleator83dynamic.
+  \cite dinic70algorithm, \cite sleator83dynamic.
 - \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
   \ref goldberg88newapproach, \ref sleator83dynamic.
+  \cite goldberg88newapproach, \cite sleator83dynamic.
 In most cases the \ref Preflow algorithm provides the
 …
 This group contains the algorithms for finding minimum cost flows and
 circulations \ref amo93networkflows. For more information about this
 problem and its dual solution, see \ref min_cost_flow
+circulations \cite amo93networkflows. For more information about this
+problem and its dual solution, see: \ref min_cost_flow
 "Minimum Cost Flow Problem".
 LEMON contains several algorithms for this problem.
  - \ref NetworkSimplex Primal Network Simplex algorithm with various
    pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
+   pivot strategies \cite dantzig63linearprog, \cite kellyoneill91netsimplex.
  - \ref CostScaling Cost Scaling algorithm based on push/augment and
    relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
    \ref bunnagel98efficient.
+   relabel operations \cite goldberg90approximation, \cite goldberg97efficient,
+   \cite bunnagel98efficient.
  - \ref CapacityScaling Capacity Scaling algorithm based on the successive
    shortest path method \ref edmondskarp72theoretical.
+   shortest path method \cite edmondskarp72theoretical.
  - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
    strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
+   strongly polynomial \cite klein67primal, \cite goldberg89cyclecanceling.
 In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
 …
 which is capable of handling real-valued arc costs (other numerical
 data are required to be integer).
+For more details about these implementations and for a comprehensive
+experimental study, see the paper \cite KiralyKovacs12MCF.
+It also compares these codes to other publicly available
+minimum cost flow solvers.
 */
 …
 This group contains the algorithms for finding minimum mean cycles
 \ref amo93networkflows, \ref karp78characterization.
+\cite amo93networkflows, \cite karp78characterization.
 The \e minimum \e mean \e cycle \e problem is to find a directed cycle
 …
 LEMON contains three algorithms for solving the minimum mean cycle problem:
 - \ref KarpMmc Karp's original algorithm \ref karp78characterization.
+- \ref KarpMmc Karp's original algorithm \cite karp78characterization.
 - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
   version of Karp's algorithm \ref hartmann93finding.
+  version of Karp's algorithm \cite hartmann93finding.
 - \ref HowardMmc Howard's policy iteration algorithm
   \ref dasdan98minmeancycle, \ref dasdan04experimental.
+  \cite dasdan98minmeancycle, \cite dasdan04experimental.
 In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
 …
 time is exponential.
 Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
+run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
+typically faster due to the applied early termination scheme.
+run in time O(ne) and use space O(n<sup>2</sup>+e).
 */
 …
 high-level interface.
 The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
 \ref cplex, \ref soplex.
+The currently supported solvers are \cite glpk, \cite clp, \cite cbc,
+\cite cplex, \cite soplex.
 */
 …
 This group contains general \c EPS drawing methods and special
 graph exporting tools.
+\image html graph_to_eps.png
 */

doc/images/bipartite_partitions.eps

-                      r587
+                      r1045
 %!PS-Adobe-2.0 EPSF-2.0
 %%Creator: LEMON, graphToEps()
 %%CreationDate: Tue Nov 15 16:51:43 2005
+%%CreationDate: Fri Mar  8 00:18:43 2013
 %%BoundingBox: 0 0 842 596
 %%EndComments
 …
 %Edges:
 gsave
 .857 -446.322 296.569 -487.43 79.2808 -528.539 0 0 0 2 lb
 .857 -446.322 575.52 -315.655 637.183 -184.989 0 0 0 2 lb
 .468 566.711 494.771 434.577 596.074 302.442 0 0 0 2 lb
 .468 566.711 155.625 579.925 -82.2171 593.138 0 0 0 2 lb
 .468 566.711 251.056 450.726 108.644 334.741 0 0 0 2 lb
 .153 52.8539 732.613 177.648 596.074 302.442 0 0 0 2 lb
 .153 52.8539 753.168 -66.0676 637.183 -184.989 0 0 0 2 lb
 -82.2171 593.138 -91.0261 346.487 -99.8351 99.8351 0 0 0 2 lb
 -663.61 546.157 -753.168 394.936 -842.726 243.715 0 0 0 2 lb
 -663.61 546.157 -574.052 437.513 -484.494 328.869 0 0 0 2 lb
 -1077.63 161.498 -960.178 202.606 -842.726 243.715 0 0 0 2 lb
 -1077.63 161.498 -968.987 66.0674 -860.344 -29.3633 0 0 0 2 lb
 -1177.47 -234.906 -1029.18 -381.722 -880.898 -528.539 0 0 0 2 lb
 -1177.47 -234.906 -1018.91 -132.135 -860.344 -29.3633 0 0 0 2 lb
 -880.898 -528.539 -744.359 -387.595 -607.82 -246.651 0 0 0 2 lb
 -499.175 -499.175 -355.295 -475.685 -211.415 -452.194 0 0 0 2 lb
 -499.175 -499.175 -553.498 -372.913 -607.82 -246.651 0 0 0 2 lb
 -499.175 -499.175 -386.587 -315.087 -274 -131 0 0 0 2 lb
 .2808 -528.539 -66.0671 -490.366 -211.415 -452.194 0 0 0 2 lb
 .183 -184.989 421.363 -253.993 205.543 -322.996 0 0 0 2 lb
 .543 -322.996 162.966 -226.097 120.389 -129.198 0 0 0 2 lb
 .34 88.0898 259.865 -20.5541 120.389 -129.198 0 0 0 2 lb
 .34 88.0898 253.992 211.415 108.644 334.741 0 0 0 2 lb
 -842.726 243.715 -471.281 171.775 -99.8351 99.8351 0 0 0 2 lb
 -842.726 243.715 -558.363 56.3575 -274 -131 0 0 0 2 lb
 -860.344 -29.3633 -734.082 -138.007 -607.82 -246.651 0 0 0 2 lb
 -211.415 -452.194 -45.513 -290.696 120.389 -129.198 0 0 0 2 lb
 -99.8351 99.8351 4.40445 217.288 108.644 334.741 0 0 0 2 lb
 -99.8351 99.8351 -292.165 214.352 -484.494 328.869 0 0 0 2 lb
 .389 -129.198 -76.8055 -130.099 -274 -131 0 0 0 2 lb
+.857 -446.322 296.569 -487.43 79.2808 -528.539 0 0 0 7.00153 lb
+.857 -446.322 575.52 -315.656 637.183 -184.989 0 0 0 7.00153 lb
+.468 566.711 494.771 434.577 596.074 302.442 0 0 0 7.00153 lb
+.468 566.711 155.625 579.925 -82.2171 593.138 0 0 0 7.00153 lb
+.468 566.711 251.056 450.726 108.644 334.741 0 0 0 7.00153 lb
+.153 52.8539 732.613 177.648 596.074 302.442 0 0 0 7.00153 lb
+.153 52.8539 753.168 -66.0676 637.183 -184.989 0 0 0 7.00153 lb
+-82.2171 593.138 -91.0261 346.487 -99.8351 99.8351 0 0 0 7.00153 lb
+-663.61 546.157 -753.168 394.936 -842.726 243.715 0 0 0 7.00153 lb
+-663.61 546.157 -574.052 437.513 -484.494 328.869 0 0 0 7.00153 lb
+-1077.63 161.498 -960.178 202.606 -842.726 243.715 0 0 0 7.00153 lb
+-1077.63 161.498 -968.987 66.0674 -860.344 -29.3633 0 0 0 7.00153 lb
+-1177.47 -234.906 -1029.18 -381.722 -880.898 -528.539 0 0 0 7.00153 lb
+-1177.47 -234.906 -1018.91 -132.135 -860.344 -29.3633 0 0 0 7.00153 lb
+-880.898 -528.539 -744.359 -387.595 -607.82 -246.651 0 0 0 7.00153 lb
+-499.175 -499.175 -355.295 -475.685 -211.415 -452.194 0 0 0 7.00153 lb
+-499.175 -499.175 -553.498 -372.913 -607.82 -246.651 0 0 0 7.00153 lb
+-499.175 -499.175 -386.587 -315.087 -274 -131 0 0 0 7.00153 lb
+.2808 -528.539 -66.0671 -490.366 -211.415 -452.194 0 0 0 7.00153 lb
+.183 -184.989 421.363 -253.993 205.543 -322.996 0 0 0 7.00153 lb
+.543 -322.996 162.966 -226.097 120.389 -129.198 0 0 0 7.00153 lb
+.34 88.0898 259.865 -20.5541 120.389 -129.198 0 0 0 7.00153 lb
+.34 88.0898 253.992 211.415 108.644 334.741 0 0 0 7.00153 lb
+-842.726 243.715 -471.281 171.775 -99.8351 99.8351 0 0 0 7.00153 lb
+-842.726 243.715 -558.363 56.3575 -274 -131 0 0 0 7.00153 lb
+-860.344 -29.3633 -734.082 -138.007 -607.82 -246.651 0 0 0 7.00153 lb
+-211.415 -452.194 -45.513 -290.696 120.389 -129.198 0 0 0 7.00153 lb
+-99.8351 99.8351 4.40445 217.288 108.644 334.741 0 0 0 7.00153 lb
+-99.8351 99.8351 -292.165 214.352 -484.494 328.869 0 0 0 7.00153 lb
+.389 -129.198 -76.8055 -130.099 -274 -131 0 0 0 7.00153 lb
 grestore
 %Nodes:
 gsave
 -274 -131 20 1 0 0 nc
 -607.82 -246.651 20 1 0 0 nc
 -484.494 328.869 20 0 0 1 nc
 .644 334.741 20 0 0 1 nc
 .389 -129.198 20 0 0 1 nc
 -99.8351 99.8351 20 1 0 0 nc
 -211.415 -452.194 20 1 0 0 nc
 -860.344 -29.3633 20 0 0 1 nc
 -842.726 243.715 20 0 0 1 nc
 .34 88.0898 20 1 0 0 nc
 .543 -322.996 20 1 0 0 nc
 .183 -184.989 20 0 0 1 nc
 .2808 -528.539 20 0 0 1 nc
 -499.175 -499.175 20 0 0 1 nc
 -880.898 -528.539 20 0 0 1 nc
 -1177.47 -234.906 20 1 0 0 nc
 -1077.63 161.498 20 1 0 0 nc
 -663.61 546.157 20 1 0 0 nc
 -82.2171 593.138 20 0 0 1 nc
 .074 302.442 20 0 0 1 nc
 .153 52.8539 20 1 0 0 nc
 .468 566.711 20 1 0 0 nc
 .857 -446.322 20 1 0 0 nc
+-274 -131 23.3384 1 0 0 nc
+-607.82 -246.651 23.3384 1 0 0 nc
+-484.494 328.869 23.3384 0 0 1 nc
+.644 334.741 23.3384 0 0 1 nc
+.389 -129.198 23.3384 0 0 1 nc
+-99.8351 99.8351 23.3384 1 0 0 nc
+-211.415 -452.194 23.3384 1 0 0 nc
+-860.344 -29.3633 23.3384 0 0 1 nc
+-842.726 243.715 23.3384 0 0 1 nc
+.34 88.0898 23.3384 1 0 0 nc
+.543 -322.996 23.3384 1 0 0 nc
+.183 -184.989 23.3384 0 0 1 nc
+.2808 -528.539 23.3384 0 0 1 nc
+-499.175 -499.175 23.3384 0 0 1 nc
+-880.898 -528.539 23.3384 0 0 1 nc
+-1177.47 -234.906 23.3384 1 0 0 nc
+-1077.63 161.498 23.3384 1 0 0 nc
+-663.61 546.157 23.3384 1 0 0 nc
+-82.2171 593.138 23.3384 0 0 1 nc
+.074 302.442 23.3384 0 0 1 nc
+.153 52.8539 23.3384 1 0 0 nc
+.468 566.711 23.3384 1 0 0 nc
+.857 -446.322 23.3384 1 0 0 nc
 grestore
 grestore

doc/images/connected_components.eps

-                      r587
+                      r1045
 %!PS-Adobe-2.0 EPSF-2.0
 %%Creator: LEMON, graphToEps()
 %%CreationDate: Fri Nov  4 13:47:12 2005
+%%CreationDate: Fri Mar  8 00:18:43 2013
 %%BoundingBox: 0 0 842 596
 %%EndComments
 …
 %Edges:
 gsave
 .035 177.301 622.149 225.748 670.264 274.195 0 0 0 2 lb
 .579 115.483 682.421 194.839 670.264 274.195 0 0 0 2 lb
 .402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 0 2 lb
 .402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 0 2 lb
 .403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 0 2 lb
 .584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 0 2 lb
 .584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 0 2 lb
 .037 -88.514 417.946 -142.604 397.855 -196.694 0 0 0 2 lb
 .037 -88.514 402.492 -99.332 366.947 -110.15 0 0 0 2 lb
 .855 -196.694 382.401 -153.422 366.947 -110.15 0 0 0 2 lb
 .947 -110.15 319.038 -142.604 271.13 -175.058 0 0 0 2 lb
 .13 -175.058 274.221 -213.694 277.311 -252.33 0 0 0 2 lb
 .13 -175.058 238.675 -190.512 206.221 -205.967 0 0 0 2 lb
 .311 -252.33 241.766 -229.149 206.221 -205.967 0 0 0 2 lb
 -840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0 0 2 lb
 -579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0 2 lb
 -579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0 2 lb
 -767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0 2 lb
 .312 201.403 946.592 42.798 986.873 -115.807 0 0 0 2 lb
 .312 201.403 834.562 91.8901 762.812 -17.6227 0 0 0 2 lb
 .873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 0 2 lb
 -470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0 0 0 2 lb
 .945 521.129 208.955 541.269 -5.03507 561.41 0 0 0 2 lb
 .945 521.129 376.371 417.911 329.797 314.692 0 0 0 2 lb
 .945 521.129 474.554 276.928 526.164 32.7279 0 0 0 2 lb
 -5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 0 2 lb
 .797 314.692 130.912 317.209 -67.9734 319.727 0 0 0 2 lb
 -67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 0 2 lb
 .812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 0 2 lb
 .812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 0 2 lb
 .164 32.7279 470.779 -128.394 415.393 -289.516 0 0 0 2 lb
 .084 -307.139 572.738 -298.327 415.393 -289.516 0 0 0 2 lb
 .393 -289.516 173.71 -318.468 -67.9734 -347.42 0 0 0 2 lb
 -67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 0 2 lb
 -67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 0 2 lb
 -309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 0 2 lb
 -323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 0 2 lb
 -26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 0 2 lb
 -26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 0 2 lb
 -26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 0 2 lb
 -26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 0 2 lb
 .407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 0 2 lb
 -262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 0 2 lb
 -262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 0 2 lb
 -13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 0 2 lb
 -180.397 245.045 -142.256 345.099 -132.697 451.748 0 0 0 2 lb
 -180.397 245.045 -170.838 351.694 -132.697 451.748 0 0 0 2 lb
 -416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 0 2 lb
 -416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 0 2 lb
 -132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 0 2 lb
 .264 274.195 629.188 409.347 588.113 544.499 0 0 0 2 lb
 .264 274.195 797.466 341.771 924.667 409.347 0 0 0 2 lb
 .113 544.499 756.39 476.923 924.667 409.347 0 0 0 2 lb
 -689.204 -237.261 -614.799 -102.648 -567.302 43.6423 0 0 0 2 lb
 -689.204 -237.261 -641.707 -90.9706 -567.302 43.6423 0 0 0 2 lb
+.035 177.301 622.149 225.748 670.264 274.195 0 0 0 6.25356 lb
+.579 115.483 682.421 194.839 670.264 274.195 0 0 0 6.25356 lb
+.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 0 6.25356 lb
+.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 0 6.25356 lb
+.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 0 6.25356 lb
+.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 0 6.25356 lb
+.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 0 6.25356 lb
+.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 0 6.25356 lb
+.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 0 6.25356 lb
+.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 0 6.25356 lb
+.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 0 6.25356 lb
+.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 0 6.25356 lb
+.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 0 6.25356 lb
+.311 -252.33 241.766 -229.149 206.221 -205.967 0 0 0 6.25356 lb
+-840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0 0 6.25356 lb
+-579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0 6.25356 lb
+-579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0 6.25356 lb
+-767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0 6.25356 lb
+.312 201.403 946.592 42.798 986.873 -115.807 0 0 0 6.25356 lb
+.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 0 6.25356 lb
+.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 0 6.25356 lb
+-470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0 0 0 6.25356 lb
+.945 521.129 208.955 541.269 -5.03507 561.41 0 0 0 6.25356 lb
+.945 521.129 376.371 417.911 329.797 314.692 0 0 0 6.25356 lb
+.945 521.129 474.554 276.928 526.164 32.7279 0 0 0 6.25356 lb
+-5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 0 6.25356 lb
+.797 314.692 130.912 317.209 -67.9734 319.727 0 0 0 6.25356 lb
+-67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 0 6.25356 lb
+.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 0 6.25356 lb
+.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 0 6.25356 lb
+.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 0 6.25356 lb
+.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 0 6.25356 lb
+.393 -289.516 173.71 -318.468 -67.9734 -347.42 0 0 0 6.25356 lb
+-67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 0 6.25356 lb
+-67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 0 6.25356 lb
+-309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 0 6.25356 lb
+-323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 0 6.25356 lb
+-26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 0 6.25356 lb
+-26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 0 6.25356 lb
+-26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 0 6.25356 lb
+-26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 0 6.25356 lb
+.407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 0 6.25356 lb
+-262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 0 6.25356 lb
+-262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 0 6.25356 lb
+-13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 0 6.25356 lb
+-180.397 245.045 -113.509 338.465 -132.697 451.748 0 0 0 6.25356 lb
+-180.397 245.045 -199.585 358.328 -132.697 451.748 0 0 0 6.25356 lb
+-416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 0 6.25356 lb
+-416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 0 6.25356 lb
+-132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 0 6.25356 lb
+.264 274.195 629.188 409.347 588.113 544.499 0 0 0 6.25356 lb
+.264 274.195 797.466 341.771 924.667 409.347 0 0 0 6.25356 lb
+.113 544.499 756.39 476.923 924.667 409.347 0 0 0 6.25356 lb
+-689.204 -237.261 -587.735 -114.393 -567.302 43.6423 0 0 0 6.25356 lb
+-689.204 -237.261 -668.771 -79.2259 -567.302 43.6423 0 0 0 6.25356 lb
 grestore
 %Nodes:
 gsave
 -567.302 43.6423 20 0 0 0 nc
 -689.204 -237.261 20 0 0 0 nc
 .667 409.347 20 1 0 0 nc
 .113 544.499 20 1 0 0 nc
 .264 274.195 20 1 0 0 nc
 -371.2 568.349 20 0 1 0 nc
 -132.697 451.748 20 0 1 0 nc
 -416.25 345.746 20 0 1 0 nc
 -180.397 245.045 20 0 1 0 nc
 -13.4452 133.743 20 0 1 0 nc
 -262.548 107.243 20 0 1 0 nc
 .208 38.3422 20 0 1 0 nc
 .407 -173.66 20 0 1 0 nc
 -26.6953 -19.9585 20 0 1 0 nc
 -539.894 -262.64 20 0 0 1 nc
 -323.543 -433.964 20 0 0 1 nc
 -309.657 -57.9033 20 0 0 1 nc
 -67.9734 -347.42 20 0 0 1 nc
 .393 -289.516 20 0 0 1 nc
 .084 -307.139 20 0 0 1 nc
 .164 32.7279 20 0 0 1 nc
 .812 -17.6227 20 0 0 1 nc
 -67.9734 319.727 20 0 0 1 nc
 .797 314.692 20 0 0 1 nc
 -5.03507 561.41 20 0 0 1 nc
 .945 521.129 20 0 0 1 nc
 -470.779 158.605 20 0 0 1 nc
 .873 -115.807 20 0 0 1 nc
 .312 201.403 20 0 0 1 nc
 -767.847 113.289 20 0 0 1 nc
 -579.033 445.603 20 0 0 1 nc
 -840.856 -246.718 20 0 0 1 nc
 .221 -205.967 20 1 1 0 nc
 .311 -252.33 20 1 1 0 nc
 .13 -175.058 20 1 1 0 nc
 .947 -110.15 20 1 1 0 nc
 .855 -196.694 20 1 1 0 nc
 .037 -88.514 20 1 1 0 nc
 .584 -48.3327 20 1 1 0 nc
 .403 -23.6057 20 1 1 0 nc
 .402 10.3938 20 1 1 0 nc
 .579 115.483 20 1 0 0 nc
 .035 177.301 20 1 0 0 nc
+-567.302 43.6423 20.8452 0 0 0 nc
+-689.204 -237.261 20.8452 0 0 0 nc
+.667 409.347 20.8452 1 0 0 nc
+.113 544.499 20.8452 1 0 0 nc
+.264 274.195 20.8452 1 0 0 nc
+-371.2 568.349 20.8452 0 1 0 nc
+-132.697 451.748 20.8452 0 1 0 nc
+-416.25 345.746 20.8452 0 1 0 nc
+-180.397 245.045 20.8452 0 1 0 nc
+-13.4452 133.743 20.8452 0 1 0 nc
+-262.548 107.243 20.8452 0 1 0 nc
+.208 38.3422 20.8452 0 1 0 nc
+.407 -173.66 20.8452 0 1 0 nc
+-26.6953 -19.9585 20.8452 0 1 0 nc
+-539.894 -262.64 20.8452 0 0 1 nc
+-323.543 -433.964 20.8452 0 0 1 nc
+-309.657 -57.9033 20.8452 0 0 1 nc
+-67.9734 -347.42 20.8452 0 0 1 nc
+.393 -289.516 20.8452 0 0 1 nc
+.084 -307.139 20.8452 0 0 1 nc
+.164 32.7279 20.8452 0 0 1 nc
+.812 -17.6227 20.8452 0 0 1 nc
+-67.9734 319.727 20.8452 0 0 1 nc
+.797 314.692 20.8452 0 0 1 nc
+-5.03507 561.41 20.8452 0 0 1 nc
+.945 521.129 20.8452 0 0 1 nc
+-470.779 158.605 20.8452 0 0 1 nc
+.873 -115.807 20.8452 0 0 1 nc
+.312 201.403 20.8452 0 0 1 nc
+-767.847 113.289 20.8452 0 0 1 nc
+-579.033 445.603 20.8452 0 0 1 nc
+-840.856 -246.718 20.8452 0 0 1 nc
+.221 -205.967 20.8452 1 1 0 nc
+.311 -252.33 20.8452 1 1 0 nc
+.13 -175.058 20.8452 1 1 0 nc
+.947 -110.15 20.8452 1 1 0 nc
+.855 -196.694 20.8452 1 1 0 nc
+.037 -88.514 20.8452 1 1 0 nc
+.584 -48.3327 20.8452 1 1 0 nc
+.403 -23.6057 20.8452 1 1 0 nc
+.402 10.3938 20.8452 1 1 0 nc
+.579 115.483 20.8452 1 0 0 nc
+.035 177.301 20.8452 1 0 0 nc
 grestore
 grestore

doc/images/edge_biconnected_components.eps

-                      r587
+                      r1045
 %!PS-Adobe-2.0 EPSF-2.0
 %%Creator: LEMON, graphToEps()
 %%CreationDate: Fri Nov  4 13:47:12 2005
+%%CreationDate: Fri Mar  8 00:18:43 2013
 %%BoundingBox: 0 0 842 596
 %%EndComments
 …
 %Edges:
 gsave
 .035 177.301 622.149 225.748 670.264 274.195 1 0 0 2 lb
 .579 115.483 682.421 194.839 670.264 274.195 1 0 0 2 lb
 .402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 1 2 lb
 .402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 1 2 lb
 .403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 1 2 lb
 .584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 1 2 lb
 .584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 1 2 lb
 .037 -88.514 417.946 -142.604 397.855 -196.694 0 0 1 2 lb
 .037 -88.514 402.492 -99.332 366.947 -110.15 0 0 1 2 lb
 .855 -196.694 382.401 -153.422 366.947 -110.15 0 0 1 2 lb
 .947 -110.15 319.038 -142.604 271.13 -175.058 0 0 1 2 lb
 .13 -175.058 274.221 -213.694 277.311 -252.33 0 0 1 2 lb
 .13 -175.058 238.675 -190.512 206.221 -205.967 0 0 1 2 lb
 .311 -252.33 241.766 -229.149 206.221 -205.967 0 0 1 2 lb
 -840.856 -246.718 -804.351 -66.7145 -767.847 113.289 1 0 0 2 lb
 -579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 1 2 lb
 -579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 1 2 lb
 -767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 1 2 lb
 .312 201.403 946.592 42.798 986.873 -115.807 0 0 1 2 lb
 .312 201.403 834.562 91.8901 762.812 -17.6227 0 0 1 2 lb
 .873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 1 2 lb
 -470.779 158.605 -390.218 50.3508 -309.657 -57.9033 1 0 0 2 lb
 .945 521.129 208.955 541.269 -5.03507 561.41 0 0 1 2 lb
 .945 521.129 376.371 417.911 329.797 314.692 0 0 1 2 lb
 .945 521.129 474.554 276.928 526.164 32.7279 0 0 1 2 lb
 -5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 1 2 lb
 .797 314.692 130.912 317.209 -67.9734 319.727 0 0 1 2 lb
 -67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 1 2 lb
 .812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 1 2 lb
 .812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 1 2 lb
 .164 32.7279 470.779 -128.394 415.393 -289.516 0 0 1 2 lb
 .084 -307.139 572.738 -298.327 415.393 -289.516 0 0 1 2 lb
 .393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0 0 2 lb
 -67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 1 2 lb
 -67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 1 2 lb
 -309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 1 2 lb
 -323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 1 2 lb
 -26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 1 2 lb
 -26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 1 2 lb
 -26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 1 2 lb
 -26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 1 2 lb
 .407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 1 2 lb
 -262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 1 2 lb
 -262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 1 2 lb
 -13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 1 2 lb
 -180.397 245.045 -142.256 345.099 -132.697 451.748 0 0 1 2 lb
 -180.397 245.045 -170.838 351.694 -132.697 451.748 0 0 1 2 lb
 -416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 1 2 lb
 -416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 1 2 lb
 -132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 1 2 lb
 .264 274.195 629.188 409.347 588.113 544.499 0 0 1 2 lb
 .264 274.195 797.466 341.771 924.667 409.347 0 0 1 2 lb
 .113 544.499 756.39 476.923 924.667 409.347 0 0 1 2 lb
 -689.204 -237.261 -614.799 -102.648 -567.302 43.6423 0 0 1 2 lb
 -689.204 -237.261 -641.707 -90.9706 -567.302 43.6423 0 0 1 2 lb
+.035 177.301 622.149 225.748 670.264 274.195 1 0 0 6.25356 lb
+.579 115.483 682.421 194.839 670.264 274.195 1 0 0 6.25356 lb
+.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 1 6.25356 lb
+.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 1 6.25356 lb
+.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 1 6.25356 lb
+.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 1 6.25356 lb
+.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 1 6.25356 lb
+.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 1 6.25356 lb
+.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 1 6.25356 lb
+.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 1 6.25356 lb
+.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 1 6.25356 lb
+.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 1 6.25356 lb
+.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 1 6.25356 lb
+.311 -252.33 241.766 -229.149 206.221 -205.967 0 0 1 6.25356 lb
+-840.856 -246.718 -804.351 -66.7145 -767.847 113.289 1 0 0 6.25356 lb
+-579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 1 6.25356 lb
+-579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 1 6.25356 lb
+-767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 1 6.25356 lb
+.312 201.403 946.592 42.798 986.873 -115.807 0 0 1 6.25356 lb
+.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 1 6.25356 lb
+.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 1 6.25356 lb
+-470.779 158.605 -390.218 50.3508 -309.657 -57.9033 1 0 0 6.25356 lb
+.945 521.129 208.955 541.269 -5.03507 561.41 0 0 1 6.25356 lb
+.945 521.129 376.371 417.911 329.797 314.692 0 0 1 6.25356 lb
+.945 521.129 474.554 276.928 526.164 32.7279 0 0 1 6.25356 lb
+-5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 1 6.25356 lb
+.797 314.692 130.912 317.209 -67.9734 319.727 0 0 1 6.25356 lb
+-67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 1 6.25356 lb
+.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 1 6.25356 lb
+.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 1 6.25356 lb
+.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 1 6.25356 lb
+.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 1 6.25356 lb
+.393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0 0 6.25356 lb
+-67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 1 6.25356 lb
+-67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 1 6.25356 lb
+-309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 1 6.25356 lb
+-323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 1 6.25356 lb
+-26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 1 6.25356 lb
+-26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 1 6.25356 lb
+-26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 1 6.25356 lb
+-26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 1 6.25356 lb
+.407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 1 6.25356 lb
+-262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 1 6.25356 lb
+-262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 1 6.25356 lb
+-13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 1 6.25356 lb
+-180.397 245.045 -113.509 338.465 -132.697 451.748 0 0 1 6.25356 lb
+-180.397 245.045 -199.585 358.328 -132.697 451.748 0 0 1 6.25356 lb
+-416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 1 6.25356 lb
+-416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 1 6.25356 lb
+-132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 1 6.25356 lb
+.264 274.195 629.188 409.347 588.113 544.499 0 0 1 6.25356 lb
+.264 274.195 797.466 341.771 924.667 409.347 0 0 1 6.25356 lb
+.113 544.499 756.39 476.923 924.667 409.347 0 0 1 6.25356 lb
+-689.204 -237.261 -587.735 -114.393 -567.302 43.6423 0 0 1 6.25356 lb
+-689.204 -237.261 -668.771 -79.2259 -567.302 43.6423 0 0 1 6.25356 lb
 grestore
 %Nodes:
 gsave
 -567.302 43.6423 20 0 0 0 nc
 -689.204 -237.261 20 0 0 0 nc
 .667 409.347 20 0 0 1 nc
 .113 544.499 20 0 0 1 nc
 .264 274.195 20 0 0 1 nc
 -371.2 568.349 20 1 1 0 nc
 -132.697 451.748 20 1 1 0 nc
 -416.25 345.746 20 1 1 0 nc
 -180.397 245.045 20 1 1 0 nc
 -13.4452 133.743 20 1 1 0 nc
 -262.548 107.243 20 1 1 0 nc
 .208 38.3422 20 1 1 0 nc
 .407 -173.66 20 1 1 0 nc
 -26.6953 -19.9585 20 1 1 0 nc
 -539.894 -262.64 20 0 0.5 0 nc
 -323.543 -433.964 20 0 0.5 0 nc
 -309.657 -57.9033 20 0 0.5 0 nc
 -67.9734 -347.42 20 0 0.5 0 nc
 .393 -289.516 20 0.5 0 0 nc
 .084 -307.139 20 0.5 0 0 nc
 .164 32.7279 20 0.5 0 0 nc
 .812 -17.6227 20 0.5 0 0 nc
 -67.9734 319.727 20 0.5 0 0 nc
 .797 314.692 20 0.5 0 0 nc
 -5.03507 561.41 20 0.5 0 0 nc
 .945 521.129 20 0.5 0 0 nc
 -470.779 158.605 20 0 1 1 nc
 .873 -115.807 20 0.5 0 0 nc
 .312 201.403 20 0.5 0 0 nc
 -767.847 113.289 20 0 1 1 nc
 -579.033 445.603 20 0 1 1 nc
 -840.856 -246.718 20 1 0 1 nc
 .221 -205.967 20 0 0 0.5 nc
 .311 -252.33 20 0 0 0.5 nc
 .13 -175.058 20 0 0 0.5 nc
 .947 -110.15 20 0 0 0.5 nc
 .855 -196.694 20 0 0 0.5 nc
 .037 -88.514 20 0 0 0.5 nc
 .584 -48.3327 20 0 0 0.5 nc
 .403 -23.6057 20 0 0 0.5 nc
 .402 10.3938 20 0 0 0.5 nc
 .579 115.483 20 1 0 0 nc
 .035 177.301 20 0 1 0 nc
+-567.302 43.6423 20.8452 0 0 0 nc
+-689.204 -237.261 20.8452 0 0 0 nc
+.667 409.347 20.8452 0 0 1 nc
+.113 544.499 20.8452 0 0 1 nc
+.264 274.195 20.8452 0 0 1 nc
+-371.2 568.349 20.8452 1 1 0 nc
+-132.697 451.748 20.8452 1 1 0 nc
+-416.25 345.746 20.8452 1 1 0 nc
+-180.397 245.045 20.8452 1 1 0 nc
+-13.4452 133.743 20.8452 1 1 0 nc
+-262.548 107.243 20.8452 1 1 0 nc
+.208 38.3422 20.8452 1 1 0 nc
+.407 -173.66 20.8452 1 1 0 nc
+-26.6953 -19.9585 20.8452 1 1 0 nc
+-539.894 -262.64 20.8452 0 0.5 0 nc
+-323.543 -433.964 20.8452 0 0.5 0 nc
+-309.657 -57.9033 20.8452 0 0.5 0 nc
+-67.9734 -347.42 20.8452 0 0.5 0 nc
+.393 -289.516 20.8452 0.5 0 0 nc
+.084 -307.139 20.8452 0.5 0 0 nc
+.164 32.7279 20.8452 0.5 0 0 nc
+.812 -17.6227 20.8452 0.5 0 0 nc
+-67.9734 319.727 20.8452 0.5 0 0 nc
+.797 314.692 20.8452 0.5 0 0 nc
+-5.03507 561.41 20.8452 0.5 0 0 nc
+.945 521.129 20.8452 0.5 0 0 nc
+-470.779 158.605 20.8452 0 1 1 nc
+.873 -115.807 20.8452 0.5 0 0 nc
+.312 201.403 20.8452 0.5 0 0 nc
+-767.847 113.289 20.8452 0 1 1 nc
+-579.033 445.603 20.8452 0 1 1 nc
+-840.856 -246.718 20.8452 1 0 1 nc
+.221 -205.967 20.8452 0 0 0.5 nc
+.311 -252.33 20.8452 0 0 0.5 nc
+.13 -175.058 20.8452 0 0 0.5 nc
+.947 -110.15 20.8452 0 0 0.5 nc
+.855 -196.694 20.8452 0 0 0.5 nc
+.037 -88.514 20.8452 0 0 0.5 nc
+.584 -48.3327 20.8452 0 0 0.5 nc
+.403 -23.6057 20.8452 0 0 0.5 nc
+.402 10.3938 20.8452 0 0 0.5 nc
+.579 115.483 20.8452 1 0 0 nc
+.035 177.301 20.8452 0 1 0 nc
 grestore
 grestore

doc/images/node_biconnected_components.eps

-                      r587
+                      r1045
 %!PS-Adobe-2.0 EPSF-2.0
 %%Creator: LEMON, graphToEps()
 %%CreationDate: Fri Nov  4 13:47:12 2005
+%%CreationDate: Fri Mar  8 00:18:43 2013
 %%BoundingBox: 0 0 842 596
 %%EndComments
 …
 %Edges:
 gsave
 .035 177.301 622.149 225.748 670.264 274.195 0 1 0 5 lb
 .579 115.483 682.421 194.839 670.264 274.195 1 0 0 5 lb
 .402 10.3938 246.402 -6.60595 212.403 -23.6057 1 1 0.5 5 lb
 .402 10.3938 283.493 -18.9695 286.584 -48.3327 1 1 0.5 5 lb
 .403 -23.6057 249.493 -35.9692 286.584 -48.3327 1 1 0.5 5 lb
 .584 -48.3327 326.765 -79.2414 366.947 -110.15 1 0.5 1 5 lb
 .584 -48.3327 278.857 -111.695 271.13 -175.058 1 0.5 1 5 lb
 .037 -88.514 417.946 -142.604 397.855 -196.694 0.5 0.5 1 5 lb
 .037 -88.514 402.492 -99.332 366.947 -110.15 0.5 0.5 1 5 lb
 .855 -196.694 382.401 -153.422 366.947 -110.15 0.5 0.5 1 5 lb
 .947 -110.15 319.038 -142.604 271.13 -175.058 1 0.5 1 5 lb
 .13 -175.058 274.221 -213.694 277.311 -252.33 0.5 1 1 5 lb
 .13 -175.058 238.675 -190.512 206.221 -205.967 0.5 1 1 5 lb
 .311 -252.33 241.766 -229.149 206.221 -205.967 0.5 1 1 5 lb
 -840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0.5 0 5 lb
 -579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0.5 5 lb
 -579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0.5 5 lb
 -767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0.5 5 lb
 .312 201.403 946.592 42.798 986.873 -115.807 0 0.5 0.5 5 lb
 .312 201.403 834.562 91.8901 762.812 -17.6227 0 0.5 0.5 5 lb
 .873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0.5 0.5 5 lb
 -470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0.5 0.5 0 5 lb
 .945 521.129 208.955 541.269 -5.03507 561.41 0.5 0 0.5 5 lb
 .945 521.129 376.371 417.911 329.797 314.692 0.5 0 0.5 5 lb
 .945 521.129 474.554 276.928 526.164 32.7279 0.5 0 0.5 5 lb
 -5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0.5 0 0.5 5 lb
 .797 314.692 130.912 317.209 -67.9734 319.727 0.5 0 0.5 5 lb
 -67.9734 319.727 229.095 176.227 526.164 32.7279 0.5 0 0.5 5 lb
 .812 -17.6227 644.488 7.5526 526.164 32.7279 0.5 0.5 0.5 5 lb
 .812 -17.6227 746.448 -162.381 730.084 -307.139 0.5 0.5 0.5 5 lb
 .164 32.7279 470.779 -128.394 415.393 -289.516 0.5 0.5 0.5 5 lb
 .084 -307.139 572.738 -298.327 415.393 -289.516 0.5 0.5 0.5 5 lb
 .393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0.5 0.5 5 lb
 -67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0.5 1 0.5 5 lb
 -67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0.5 1 0.5 5 lb
 -309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0.5 1 0.5 5 lb
 -323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0.5 1 0.5 5 lb
 -26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 1 1 0 5 lb
 -26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 1 1 0 5 lb
 -26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 1 0 1 5 lb
 -26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 1 0 1 5 lb
 .407 -173.66 158.808 -67.6589 201.208 38.3422 1 1 0 5 lb
 -262.548 107.243 -137.997 120.493 -13.4452 133.743 1 0 1 5 lb
 -262.548 107.243 -221.472 176.144 -180.397 245.045 1 0 1 5 lb
 -13.4452 133.743 -96.9211 189.394 -180.397 245.045 1 0 1 5 lb
 -180.397 245.045 -140.307 344.649 -132.697 451.748 0 1 1 5 lb
 -180.397 245.045 -172.787 352.144 -132.697 451.748 0 1 1 5 lb
 -416.25 345.746 -274.474 398.747 -132.697 451.748 0.5 0 0 5 lb
 -416.25 345.746 -393.725 457.048 -371.2 568.349 0.5 0 0 5 lb
 -132.697 451.748 -251.948 510.048 -371.2 568.349 0.5 0 0 5 lb
 .264 274.195 629.188 409.347 588.113 544.499 0 0 1 5 lb
 .264 274.195 797.466 341.771 924.667 409.347 0 0 1 5 lb
 .113 544.499 756.39 476.923 924.667 409.347 0 0 1 5 lb
 -689.204 -237.261 -612.964 -103.444 -567.302 43.6423 0 0 0 5 lb
 -689.204 -237.261 -643.542 -90.1744 -567.302 43.6423 0 0 0 5 lb
+.035 177.301 622.149 225.748 670.264 274.195 0 1 0 6.25356 lb
+.579 115.483 682.421 194.839 670.264 274.195 1 0 0 6.25356 lb
+.402 10.3938 246.402 -6.60595 212.403 -23.6057 1 1 0.5 6.25356 lb
+.402 10.3938 283.493 -18.9695 286.584 -48.3327 1 1 0.5 6.25356 lb
+.403 -23.6057 249.493 -35.9692 286.584 -48.3327 1 1 0.5 6.25356 lb
+.584 -48.3327 326.765 -79.2414 366.947 -110.15 1 0.5 1 6.25356 lb
+.584 -48.3327 278.857 -111.695 271.13 -175.058 1 0.5 1 6.25356 lb
+.037 -88.514 417.946 -142.604 397.855 -196.694 0.5 0.5 1 6.25356 lb
+.037 -88.514 402.492 -99.332 366.947 -110.15 0.5 0.5 1 6.25356 lb
+.855 -196.694 382.401 -153.422 366.947 -110.15 0.5 0.5 1 6.25356 lb
+.947 -110.15 319.038 -142.604 271.13 -175.058 1 0.5 1 6.25356 lb
+.13 -175.058 274.221 -213.694 277.311 -252.33 0.5 1 1 6.25356 lb
+.13 -175.058 238.675 -190.512 206.221 -205.967 0.5 1 1 6.25356 lb
+.311 -252.33 241.766 -229.149 206.221 -205.967 0.5 1 1 6.25356 lb
+-840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0.5 0 6.25356 lb
+-579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0.5 6.25356 lb
+-579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0.5 6.25356 lb
+-767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0.5 6.25356 lb
+.312 201.403 946.592 42.798 986.873 -115.807 0 0.5 0.5 6.25356 lb
+.312 201.403 834.562 91.8901 762.812 -17.6227 0 0.5 0.5 6.25356 lb
+.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0.5 0.5 6.25356 lb
+-470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0.5 0.5 0 6.25356 lb
+.945 521.129 208.955 541.269 -5.03507 561.41 0.5 0 0.5 6.25356 lb
+.945 521.129 376.371 417.911 329.797 314.692 0.5 0 0.5 6.25356 lb
+.945 521.129 474.554 276.928 526.164 32.7279 0.5 0 0.5 6.25356 lb
+-5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0.5 0 0.5 6.25356 lb
+.797 314.692 130.912 317.209 -67.9734 319.727 0.5 0 0.5 6.25356 lb
+-67.9734 319.727 229.095 176.227 526.164 32.7279 0.5 0 0.5 6.25356 lb
+.812 -17.6227 644.488 7.5526 526.164 32.7279 0.5 0.5 0.5 6.25356 lb
+.812 -17.6227 746.448 -162.381 730.084 -307.139 0.5 0.5 0.5 6.25356 lb
+.164 32.7279 470.779 -128.394 415.393 -289.516 0.5 0.5 0.5 6.25356 lb
+.084 -307.139 572.738 -298.327 415.393 -289.516 0.5 0.5 0.5 6.25356 lb
+.393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0.5 0.5 6.25356 lb
+-67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0.5 1 0.5 6.25356 lb
+-67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0.5 1 0.5 6.25356 lb
+-309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0.5 1 0.5 6.25356 lb
+-323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0.5 1 0.5 6.25356 lb
+-26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 1 1 0 6.25356 lb
+-26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 1 1 0 6.25356 lb
+-26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 1 0 1 6.25356 lb
+-26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 1 0 1 6.25356 lb
+.407 -173.66 158.808 -67.6589 201.208 38.3422 1 1 0 6.25356 lb
+-262.548 107.243 -137.997 120.493 -13.4452 133.743 1 0 1 6.25356 lb
+-262.548 107.243 -221.472 176.144 -180.397 245.045 1 0 1 6.25356 lb
+-13.4452 133.743 -96.9211 189.394 -180.397 245.045 1 0 1 6.25356 lb
+-180.397 245.045 -113.509 338.465 -132.697 451.748 0 1 1 6.25356 lb
+-180.397 245.045 -199.585 358.328 -132.697 451.748 0 1 1 6.25356 lb
+-416.25 345.746 -274.474 398.747 -132.697 451.748 0.5 0 0 6.25356 lb
+-416.25 345.746 -393.725 457.048 -371.2 568.349 0.5 0 0 6.25356 lb
+-132.697 451.748 -251.948 510.048 -371.2 568.349 0.5 0 0 6.25356 lb
+.264 274.195 629.188 409.347 588.113 544.499 0 0 1 6.25356 lb
+.264 274.195 797.466 341.771 924.667 409.347 0 0 1 6.25356 lb
+.113 544.499 756.39 476.923 924.667 409.347 0 0 1 6.25356 lb
+-689.204 -237.261 -587.735 -114.393 -567.302 43.6423 0 0 0 6.25356 lb
+-689.204 -237.261 -668.771 -79.2259 -567.302 43.6423 0 0 0 6.25356 lb
 grestore
 %Nodes:
 gsave
 -567.302 43.6423 20 0 0 1 nc
 -689.204 -237.261 20 0 0 1 nc
 .667 409.347 20 0 0 1 nc
 .113 544.499 20 0 0 1 nc
 .264 274.195 20 1 0 0 nc
 -371.2 568.349 20 0 0 1 nc
 -132.697 451.748 20 1 0 0 nc
 -416.25 345.746 20 0 0 1 nc
 -180.397 245.045 20 1 0 0 nc
 -13.4452 133.743 20 0 0 1 nc
 -262.548 107.243 20 0 0 1 nc
 .208 38.3422 20 0 0 1 nc
 .407 -173.66 20 0 0 1 nc
 -26.6953 -19.9585 20 1 0 0 nc
 -539.894 -262.64 20 0 0 1 nc
 -323.543 -433.964 20 0 0 1 nc
 -309.657 -57.9033 20 1 0 0 nc
 -67.9734 -347.42 20 1 0 0 nc
 .393 -289.516 20 1 0 0 nc
 .084 -307.139 20 0 0 1 nc
 .164 32.7279 20 1 0 0 nc
 .812 -17.6227 20 1 0 0 nc
 -67.9734 319.727 20 0 0 1 nc
 .797 314.692 20 0 0 1 nc
 -5.03507 561.41 20 0 0 1 nc
 .945 521.129 20 0 0 1 nc
 -470.779 158.605 20 1 0 0 nc
 .873 -115.807 20 0 0 1 nc
 .312 201.403 20 0 0 1 nc
 -767.847 113.289 20 1 0 0 nc
 -579.033 445.603 20 0 0 1 nc
 -840.856 -246.718 20 0 0 1 nc
 .221 -205.967 20 0 0 1 nc
 .311 -252.33 20 0 0 1 nc
 .13 -175.058 20 1 0 0 nc
 .947 -110.15 20 1 0 0 nc
 .855 -196.694 20 0 0 1 nc
 .037 -88.514 20 0 0 1 nc
 .584 -48.3327 20 1 0 0 nc
 .403 -23.6057 20 0 0 1 nc
 .402 10.3938 20 0 0 1 nc
 .579 115.483 20 0 0 1 nc
 .035 177.301 20 0 0 1 nc
+-567.302 43.6423 20.8452 0 0 1 nc
+-689.204 -237.261 20.8452 0 0 1 nc
+.667 409.347 20.8452 0 0 1 nc
+.113 544.499 20.8452 0 0 1 nc
+.264 274.195 20.8452 1 0 0 nc
+-371.2 568.349 20.8452 0 0 1 nc
+-132.697 451.748 20.8452 1 0 0 nc
+-416.25 345.746 20.8452 0 0 1 nc
+-180.397 245.045 20.8452 1 0 0 nc
+-13.4452 133.743 20.8452 0 0 1 nc
+-262.548 107.243 20.8452 0 0 1 nc
+.208 38.3422 20.8452 0 0 1 nc
+.407 -173.66 20.8452 0 0 1 nc
+-26.6953 -19.9585 20.8452 1 0 0 nc
+-539.894 -262.64 20.8452 0 0 1 nc
+-323.543 -433.964 20.8452 0 0 1 nc
+-309.657 -57.9033 20.8452 1 0 0 nc
+-67.9734 -347.42 20.8452 1 0 0 nc
+.393 -289.516 20.8452 1 0 0 nc
+.084 -307.139 20.8452 0 0 1 nc
+.164 32.7279 20.8452 1 0 0 nc
+.812 -17.6227 20.8452 1 0 0 nc
+-67.9734 319.727 20.8452 0 0 1 nc
+.797 314.692 20.8452 0 0 1 nc
+-5.03507 561.41 20.8452 0 0 1 nc
+.945 521.129 20.8452 0 0 1 nc
+-470.779 158.605 20.8452 1 0 0 nc
+.873 -115.807 20.8452 0 0 1 nc
+.312 201.403 20.8452 0 0 1 nc
+-767.847 113.289 20.8452 1 0 0 nc
+-579.033 445.603 20.8452 0 0 1 nc
+-840.856 -246.718 20.8452 0 0 1 nc
+.221 -205.967 20.8452 0 0 1 nc
+.311 -252.33 20.8452 0 0 1 nc
+.13 -175.058 20.8452 1 0 0 nc
+.947 -110.15 20.8452 1 0 0 nc
+.855 -196.694 20.8452 0 0 1 nc
+.037 -88.514 20.8452 0 0 1 nc
+.584 -48.3327 20.8452 1 0 0 nc
+.403 -23.6057 20.8452 0 0 1 nc
+.402 10.3938 20.8452 0 0 1 nc
+.579 115.483 20.8452 0 0 1 nc
+.035 177.301 20.8452 0 0 1 nc
 grestore
 grestore

doc/images/strongly_connected_components.eps

-                      r587
+                      r1045
 %!PS-Adobe-2.0 EPSF-2.0
 %%Creator: LEMON, graphToEps()
 %%CreationDate: Fri Nov  4 13:47:12 2005
+%%CreationDate: Fri Mar  8 00:22:15 2013
 %%BoundingBox: 0 0 842 596
 %%EndComments
 …
 %Edges:
 gsave
 setlinewidth 0 0 1 setrgbcolor newpath
+.56973 setlinewidth 0 0 1 setrgbcolor newpath
 .178 27.2723 moveto
 .373 -40.1551 188.622 -49.9556 169.228 -100.631 curveto stroke
 newpath 164.939 -111.838 moveto 165.492 -99.2013 lineto 172.964 -102.061 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
+.849 -31.0725 190.033 -46.2697 176.306 -82.1369 curveto stroke
+newpath 163.235 -116.291 moveto 165.206 -77.8889 lineto 187.405 -86.3849 lineto closepath fill
+.56973 setlinewidth 0 0 1 setrgbcolor newpath
 .8044 15.5841 moveto
 .293 20.6059 129.775 21.3125 186.25 25.1199 curveto stroke
 newpath 198.223 25.927 moveto 186.519 21.1289 lineto 185.981 29.1108 lineto closepath fill
 setlinewidth 1 0 0 setrgbcolor newpath
+.705 19.9594 126.016 21.0591 166.493 23.7879 curveto stroke
+newpath 202.98 26.2477 moveto 167.292 11.9299 lineto 165.694 35.6458 lineto closepath fill
+.56973 setlinewidth 1 0 0 setrgbcolor newpath
 .178 27.2723 moveto
 .395 -87.4449 290.763 -96.6058 348.102 -194.464 curveto stroke
 newpath 354.169 -204.818 moveto 344.651 -196.487 lineto 351.554 -192.442 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
+.264 -80.3935 289.87 -95.0808 338.092 -177.379 curveto stroke
+newpath 356.579 -208.932 moveto 327.837 -183.388 lineto 348.346 -171.371 lineto closepath fill
+.56973 setlinewidth 0 0 1 setrgbcolor newpath
 .79 -130.517 moveto
 .71 -67.0521 102.27 -58.7243 64.3804 -9.72954 curveto stroke
 newpath 57.0394 -0.236898 moveto 67.5446 -7.28254 lineto 61.2162 -12.1765 lineto closepath fill
 setlinewidth 1 0 0 setrgbcolor newpath
+.446 -74.4692 104.358 -61.4239 76.4943 -25.394 curveto stroke
+newpath 54.1228 3.53455 moveto 85.8959 -18.1234 lineto 67.0928 -32.6646 lineto closepath fill
+.56973 setlinewidth 1 0 0 setrgbcolor newpath
 -105.193 -261.035 moveto
 -35.6576 -132.801 -30.5923 -123.459 29.5506 -12.5464 curveto stroke
 newpath 35.2708 -1.99743 moveto 33.0669 -14.4531 lineto 26.0343 -10.6397 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
+-39.4801 -139.85 -31.344 -124.846 20.1113 -29.9539 curveto stroke
+newpath 37.5434 2.19358 moveto 30.559 -35.6192 lineto 9.66361 -24.2886 lineto closepath fill
+.56973 setlinewidth 0 0 1 setrgbcolor newpath
 -465.576 -42.8564 moveto
 -559.078 -25.5413 -569.47 -23.6169 -644.498 -9.72286 curveto stroke
 newpath -656.297 -7.5378 moveto -643.77 -5.78973 lineto -645.226 -13.656 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
+-550.335 -27.1603 -566.8 -24.1113 -625.027 -13.3286 curveto stroke
+newpath -660.985 -6.66971 moveto -622.863 -1.64245 lineto -627.191 -25.0148 lineto closepath fill
+.56973 setlinewidth 0 0 1 setrgbcolor newpath
 -574.666 -153.893 moveto
 -528.842 -107.252 -521.515 -99.794 -488.002 -65.683 curveto stroke
 newpath -479.592 -57.123 moveto -485.149 -68.4863 lineto -490.856 -62.8797 lineto closepath fill
 setlinewidth 1 0 0 setrgbcolor newpath
+-535.911 -114.447 -524.692 -103.027 -501.88 -79.8085 curveto stroke
+newpath -476.251 -53.7222 moveto -493.402 -88.1377 lineto -510.358 -71.4793 lineto closepath fill
+.56973 setlinewidth 1 0 0 setrgbcolor newpath
 -490.901 120.777 moveto
 -480.122 51.1328 -478.519 40.7713 -470.47 -11.2329 curveto stroke
 newpath -468.635 -23.0917 moveto -474.423 -11.8447 lineto -466.517 -10.6212 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
+-481.623 60.8277 -479.143 44.8049 -473.499 8.33636 curveto stroke
+newpath -467.906 -27.8032 moveto -485.244 6.51862 lineto -461.754 10.1541 lineto closepath fill
+.56973 setlinewidth 0 0 1 setrgbcolor newpath
 -675.963 -3.89604 moveto
 -632.116 -68.8235 -626.228 -77.5422 -592.575 -127.374 curveto stroke
 newpath -585.859 -137.319 moveto -595.89 -129.612 lineto -589.26 -125.135 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
+-637.405 -60.9909 -628.201 -74.6206 -603.658 -110.963 curveto stroke
+newpath -583.191 -141.27 moveto -613.507 -117.615 lineto -593.808 -104.312 lineto closepath fill
+.56973 setlinewidth 0 0 1 setrgbcolor newpath
 -490.901 120.777 moveto
 -435.445 215.844 -430.107 224.995 -384.3 303.522 curveto stroke
 newpath -378.253 313.887 moveto -380.845 301.507 lineto -387.755 305.537 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
+-439.75 208.465 -431.238 223.057 -394.278 286.417 curveto stroke
+newpath -375.851 318.006 moveto -384.012 280.429 lineto -404.543 292.406 lineto closepath fill
+.56973 setlinewidth 0 0 1 setrgbcolor newpath
 -266.879 114.933 moveto
 -367.067 117.547 -377.642 117.822 -458.912 119.943 curveto stroke
 newpath -470.908 120.255 moveto -458.807 123.941 lineto -459.016 115.944 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
+-358.311 117.318 -375.109 117.756 -439.117 119.426 curveto stroke
+newpath -475.674 120.38 moveto -438.807 131.307 lineto -439.426 107.545 lineto closepath fill
+.56973 setlinewidth 0 0 1 setrgbcolor newpath
 -368.176 331.163 moveto
 -322.511 233.685 -318.018 224.095 -280.454 143.911 curveto stroke
 newpath -275.364 133.044 moveto -284.076 142.214 lineto -276.832 145.608 lineto closepath fill
 setlinewidth 1 0 0 setrgbcolor newpath
+-326.156 241.466 -318.997 226.186 -288.855 161.843 curveto stroke
+newpath -273.341 128.727 moveto -299.617 156.801 lineto -278.092 166.885 lineto closepath fill
+.56973 setlinewidth 1 0 0 setrgbcolor newpath
 -266.879 114.933 moveto
 -224.004 235.52 -220.448 245.52 -184.094 347.765 curveto stroke
 newpath -180.074 359.072 moveto -180.325 346.425 lineto -187.863 349.105 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
+-226.764 227.755 -221.069 243.774 -190.728 329.107 curveto stroke
+newpath -178.477 363.564 moveto -179.53 325.126 lineto -201.926 333.089 lineto closepath fill
+.56973 setlinewidth 0 0 1 setrgbcolor newpath
 -251.294 -335.059 moveto
 -189.25 -303.624 -179.902 -298.887 -133.738 -275.498 curveto stroke
 newpath -123.034 -270.074 moveto -131.93 -279.066 lineto -135.546 -271.93 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
+-198.044 -308.079 -183.61 -300.766 -151.402 -284.448 curveto stroke
+newpath -118.781 -267.92 moveto -146.031 -295.049 lineto -156.774 -273.846 lineto closepath fill
+.56973 setlinewidth 0 0 1 setrgbcolor newpath
 -389.604 -136.361 moveto
 -327.15 -226.083 -321.098 -234.777 -269.576 -308.795 curveto stroke
 newpath -262.72 -318.644 moveto -272.859 -311.081 lineto -266.293 -306.51 lineto closepath fill
 setlinewidth 1 0 0 setrgbcolor newpath
+-332.039 -219.059 -322.392 -232.919 -280.889 -292.543 curveto stroke
+newpath -259.996 -322.557 moveto -290.643 -299.333 lineto -271.134 -285.753 lineto closepath fill
+.56973 setlinewidth 1 0 0 setrgbcolor newpath
 .84406 175.322 moveto
 -76.0754 267.926 -83.1051 275.873 -152.172 353.948 curveto stroke
 newpath -160.122 362.936 moveto -149.176 356.598 lineto -155.168 351.298 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
+-70.5724 261.706 -81.8227 274.423 -139.051 339.116 curveto stroke
+newpath -163.281 366.507 moveto -130.149 346.991 lineto -147.953 331.242 lineto closepath fill
+.56973 setlinewidth 0 0 1 setrgbcolor newpath
 .478 311.683 moveto
 .8003 251.119 88.6819 244.353 30.4273 195.808 curveto stroke
 newpath 21.2086 188.126 moveto 27.8666 198.881 lineto 32.988 192.735 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
+.641 256.819 90.7821 246.103 45.6398 208.485 curveto stroke
+newpath 17.546 185.074 moveto 38.0313 217.615 lineto 53.2483 199.355 lineto closepath fill
+.56973 setlinewidth 0 0 1 setrgbcolor newpath
 .851 111.037 moveto
 .766 202.563 256.831 210.589 190.4 287.47 curveto stroke
 newpath 182.554 296.55 moveto 193.427 290.085 lineto 187.373 284.855 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
+.224 196.246 258.132 209.083 203.347 272.486 curveto stroke
+newpath 179.437 300.157 moveto 212.34 280.257 lineto 194.354 264.716 lineto closepath fill
+.56973 setlinewidth 0 0 1 setrgbcolor newpath
 .84406 175.322 moveto
 .16 145.314 173.605 143.321 311.418 117.033 curveto stroke
 newpath 323.205 114.784 moveto 310.668 113.104 lineto 312.167 120.962 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
+.419 146.79 172.221 143.585 291.966 120.743 curveto stroke
+newpath 327.888 113.891 moveto 289.739 109.069 lineto 294.193 132.418 lineto closepath fill
+.56973 setlinewidth 0 0 1 setrgbcolor newpath
 .851 111.037 moveto
 .255 2.58683 505.964 -3.53033 643.932 -100.436 curveto stroke
 newpath 653.752 -107.334 moveto 641.633 -103.71 lineto 646.231 -97.163 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
+.978 6.99574 505.015 -2.86383 627.727 -89.0547 curveto stroke
+newpath 657.653 -110.074 moveto 620.896 -98.7802 lineto 634.558 -79.3291 lineto closepath fill
+.56973 setlinewidth 0 0 1 setrgbcolor newpath
 .28 -222.074 moveto
 .298 -66.9063 353.616 -56.2971 344.905 79.1029 curveto stroke
 newpath 344.135 91.0781 moveto 348.897 79.3597 lineto 340.914 78.8461 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
+.807 -74.8128 353.709 -57.7536 346.177 59.3416 curveto stroke
+newpath 343.829 95.836 moveto 358.037 60.1045 lineto 334.316 58.5786 lineto closepath fill
+.56973 setlinewidth 0 0 1 setrgbcolor newpath
 .118 -118.829 moveto
 .037 -166.793 517.967 -170.192 394.599 -211.839 curveto stroke
 newpath 383.229 -215.677 moveto 393.32 -208.049 lineto 395.878 -215.629 lineto closepath fill
 setlinewidth 1 0 0 setrgbcolor newpath
+.595 -164.241 519.412 -169.704 413.361 -205.505 curveto stroke
+newpath 378.712 -217.202 moveto 409.559 -194.245 lineto 417.162 -216.766 lineto closepath fill
+.56973 setlinewidth 1 0 0 setrgbcolor newpath
 -105.193 -261.035 moveto
 .401 -242.479 129.015 -241.598 332.39 -224.721 curveto stroke
 newpath 344.348 -223.728 moveto 332.72 -228.707 lineto 332.059 -220.734 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
+.939 -243.099 128.069 -241.677 312.655 -226.358 curveto stroke
+newpath 349.1 -223.334 moveto 313.638 -238.202 lineto 311.672 -214.514 lineto closepath fill
+.56973 setlinewidth 0 0 1 setrgbcolor newpath
 -105.193 -261.035 moveto
 -160.867 -161.176 -166.028 -151.918 -212.336 -68.858 curveto stroke
 newpath -218.179 -58.3769 moveto -208.842 -66.9102 lineto -215.829 -70.8058 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
+-156.746 -168.566 -164.987 -153.784 -202.693 -86.1539 curveto stroke
+newpath -220.5 -54.2129 moveto -192.312 -80.3665 lineto -213.073 -91.9413 lineto closepath fill
+.56973 setlinewidth 0 0 1 setrgbcolor newpath
 -227.918 -40.9084 moveto
 -298.35 -82.4884 -307.42 -87.8432 -362.048 -120.093 curveto stroke
 newpath -372.381 -126.193 moveto -364.081 -116.648 lineto -360.014 -123.537 lineto closepath fill
+-290.327 -77.7521 -304.558 -86.1532 -344.995 -110.026 curveto stroke
+newpath -376.487 -128.617 moveto -351.037 -99.7914 lineto -338.953 -120.26 lineto closepath fill
 grestore
 %Nodes:
 gsave
 -389.604 -136.361 20 0 1 0 nc
 -227.918 -40.9084 20 0 1 0 nc
 -105.193 -261.035 20 0 1 0 nc
 .28 -222.074 20 1 1 0 nc
 .118 -118.829 20 1 1 0 nc
 .851 111.037 20 1 1 0 nc
 .84406 175.322 20 1 1 0 nc
 .478 311.683 20 1 1 0 nc
 -173.374 377.916 20 1 0 1 nc
 -251.294 -335.059 20 0 1 0 nc
 -266.879 114.933 20 0 0 0 nc
 -368.176 331.163 20 0 0 0 nc
 -490.901 120.777 20 0 0 0 nc
 -574.666 -153.893 20 1 0 0 nc
 -675.963 -3.89604 20 1 0 0 nc
 -465.576 -42.8564 20 1 0 0 nc
 .8044 15.5841 20 0 0 1 nc
 .79 -130.517 20 0 0 1 nc
 .178 27.2723 20 0 0 1 nc
+-389.604 -136.361 15.2324 0 1 0 nc
+-227.918 -40.9084 15.2324 0 1 0 nc
+-105.193 -261.035 15.2324 0 1 0 nc
+.28 -222.074 15.2324 1 1 0 nc
+.118 -118.829 15.2324 1 1 0 nc
+.851 111.037 15.2324 1 1 0 nc
+.84406 175.322 15.2324 1 1 0 nc
+.478 311.683 15.2324 1 1 0 nc
+-173.374 377.916 15.2324 1 0 1 nc
+-251.294 -335.059 15.2324 0 1 0 nc
+-266.879 114.933 15.2324 0 0 0 nc
+-368.176 331.163 15.2324 0 0 0 nc
+-490.901 120.777 15.2324 0 0 0 nc
+-574.666 -153.893 15.2324 1 0 0 nc
+-675.963 -3.89604 15.2324 1 0 0 nc
+-465.576 -42.8564 15.2324 1 0 0 nc
+.8044 15.5841 15.2324 0 0 1 nc
+.79 -130.517 15.2324 0 0 1 nc
+.178 27.2723 15.2324 0 0 1 nc
 grestore
 grestore

doc/mainpage.dox.in

-                      r930
+                      r1053
 It is a C++ template library providing efficient implementations of common
 data structures and algorithms with focus on combinatorial optimization
 tasks connected mainly with graphs and networks.
+tasks connected mainly with graphs and networks \cite DezsoJuttnerKovacs11Lemon.
 <b>
 …
 The project is maintained by the
 <a href="http://www.cs.elte.hu/egres/">Egerv&aacute;ry Research Group on
 Combinatorial Optimization</a> \ref egres
+Combinatorial Optimization</a> \cite egres
 at the Operations Research Department of the
 <a href="http://www.elte.hu/en/">E&ouml;tv&ouml;s Lor&aacute;nd University</a>,
 Budapest, Hungary.
 LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a>
 initiative \ref coinor.
+initiative \cite coinor.
 \section howtoread How to Read the Documentation

doc/min_cost_flow.dox

r1002	r1053
27	27	minimum total cost from a set of supply nodes to a set of demand nodes
28	28	in a network with capacity constraints (lower and upper bounds)
29		and arc costs \~~ref~~ amo93networkflows.
	29	and arc costs \cite amo93networkflows.
30	30
31	31	Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,

doc/references.bib

-                      r1002
+                      r1051
                   {O}perations {R}esearch},
   url =          {http://www.coin-or.org/}
+}
+%%%%% Papers related to LEMON %%%%%
+@article{DezsoJuttnerKovacs11Lemon,
+  author =       {B. Dezs{\H o} and A. J\"uttner and P. Kov\'acs},
+  title =        {{LEMON} -- an open source {C++} graph template library},
+  journal =      {Electronic Notes in Theoretical Computer Science},
+  volume =       {264},
+  pages =        {23--45},
+  year =         {2011},
+  note =         {Proc. 2nd Workshop on Generative Technologies}
+}
+@article{KiralyKovacs12MCF,
+  author =       {Z. Kir\'aly and P. Kov\'acs},
+  title =        {Efficient implementations of minimum-cost flow algorithms},
+  journal =      {Acta Universitatis Sapientiae, Informatica},
+  year =         {2012},
+  volume =       {4},
+  pages =        {67--118}
+}

lemon/CMakeLists.txt

r981	r1062
37	37	IF(LEMON_HAVE_CPLEX)
38	38	SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc)
39		INCLUDE_DIRECTORIES(${~~CPLEX~~_INCLUDE_DIRS})
	39	INCLUDE_DIRECTORIES(${ILOG_INCLUDE_DIRS})
40	40	ENDIF()
41	41

lemon/base.cc

-                      r477
+                      r1054
 #include<lemon/tolerance.h>
 #include<lemon/core.h>
+#include<lemon/time_measure.h>
 namespace lemon {
 …
 #endif
+  TimeStamp::Format TimeStamp::_format = TimeStamp::NORMAL;
 } //namespace lemon

lemon/capacity_scaling.h

-                      r1070
+                      r1071
   /// \ref CapacityScaling implements the capacity scaling version
   /// of the successive shortest path algorithm for finding a
+  /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,
+  /// \ref edmondskarp72theoretical. It is an efficient dual
+  /// solution method.
+  /// \ref min_cost_flow "minimum cost flow" \cite amo93networkflows,
+  /// \cite edmondskarp72theoretical. It is an efficient dual
+  /// solution method, which runs in polynomial time
+  /// \f$O(e\log U (n+e)\log n)\f$, where <i>U</i> denotes the maximum
+  /// of node supply and arc capacity values.
   ///
   /// This algorithm is typically slower than \ref CostScaling and

lemon/cbc.h

r877	r1064
17	17	*/
18	18
19		~~// -- C++ --~~
20	19	#ifndef LEMON_CBC_H
21	20	#define LEMON_CBC_H

lemon/concepts/bpgraph.h

-                      r1028
+                      r1049
       /// \brief The base node of the iterator.
       ///
       /// Returns the base node of the given incomming arc iterator
+      /// Returns the base node of the given incoming arc iterator
       /// (i.e. the target node of the corresponding arc).
       Node baseNode(InArcIt) const { return INVALID; }
 …
       /// \brief The running node of the iterator.
       ///
       /// Returns the running node of the given incomming arc iterator
+      /// Returns the running node of the given incoming arc iterator
       /// (i.e. the source node of the corresponding arc).
       Node runningNode(InArcIt) const { return INVALID; }

lemon/concepts/digraph.h

-                      r877
+                      r1049
       /// \brief The base node of the iterator.
       ///
       /// Returns the base node of the given incomming arc iterator
+      /// Returns the base node of the given incoming arc iterator
       /// (i.e. the target node of the corresponding arc).
       Node baseNode(InArcIt) const { return INVALID; }
 …
       /// \brief The running node of the iterator.
       ///
       /// Returns the running node of the given incomming arc iterator
+      /// Returns the running node of the given incoming arc iterator
       /// (i.e. the source node of the corresponding arc).
       Node runningNode(InArcIt) const { return INVALID; }

lemon/concepts/graph.h

-                      r1018
+                      r1049
       /// \brief The base node of the iterator.
       ///
       /// Returns the base node of the given incomming arc iterator
+      /// Returns the base node of the given incoming arc iterator
       /// (i.e. the target node of the corresponding arc).
       Node baseNode(InArcIt) const { return INVALID; }
 …
       /// \brief The running node of the iterator.
       ///
       /// Returns the running node of the given incomming arc iterator
+      /// Returns the running node of the given incoming arc iterator
       /// (i.e. the source node of the corresponding arc).
       Node runningNode(InArcIt) const { return INVALID; }

lemon/concepts/graph_components.h

-                      r1028
+                      r1049
       void next(Arc&) const {}
       /// \brief Return the first arc incomming to the given node.
       ///
       /// This function gives back the first arc incomming to the
+      /// \brief Return the first arc incoming to the given node.
+      ///
+      /// This function gives back the first arc incoming to the
       /// given node.
       void firstIn(Arc&, const Node&) const {}
       /// \brief Return the next arc incomming to the given node.
       ///
       /// This function gives back the next arc incomming to the
+      /// \brief Return the next arc incoming to the given node.
+      ///
+      /// This function gives back the next arc incoming to the
       /// given node.
       void nextIn(Arc&) const {}

lemon/config.h.in

r981	r1064
7	7	#cmakedefine LEMON_HAVE_CLP 1
8	8	#cmakedefine LEMON_HAVE_CBC 1
	9	#cmakedefine LEMON_DEFAULT_LP @LEMON_DEFAULT_LP@
	10	#cmakedefine LEMON_DEFAULT_MIP @LEMON_DEFAULT_MIP@
9	11	#cmakedefine LEMON_USE_PTHREAD 1
10	12	#cmakedefine LEMON_USE_WIN32_THREADS 1

lemon/core.h

-                      r1027
+                      r1069
 #ifdef _MSC_VER
 #pragma warning( disable : 4250 4355 4503 4800 4996 )
+#endif
+#ifdef __GNUC__
+// Needed by the [DI]GRAPH_TYPEDEFS marcos for gcc 4.8
+#pragma GCC diagnostic ignored "-Wunused-local-typedefs"
 #endif

lemon/cost_scaling.h

-                      r1070
+                      r1071
   /// \ref CostScaling implements a cost scaling algorithm that performs
   /// push/augment and relabel operations for finding a \ref min_cost_flow
   /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,
   /// \ref goldberg97efficient, \ref bunnagel98efficient.
+  /// "minimum cost flow" \cite amo93networkflows, \cite goldberg90approximation,
+  /// \cite goldberg97efficient, \cite bunnagel98efficient.
   /// It is a highly efficient primal-dual solution method, which
   /// can be viewed as the generalization of the \ref Preflow
   /// "preflow push-relabel" algorithm for the maximum flow problem.
+  /// It is a polynomial algorithm, its running time complexity is
+  /// \f$O(n^2e\log(nK))\f$, where <i>K</i> denotes the maximum arc cost.
   ///
   /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
 …
           _buckets[r] = _bucket_next[u];
           // Search the incomming arcs of u
+          // Search the incoming arcs of u
           LargeCost pi_u = _pi[u];
           int last_out = _first_out[u+1];

lemon/cplex.cc

-                      r1016
+                      r1063
                    _message_enabled ? CPX_ON : CPX_OFF);
+  }
+  void CplexBase::_write(std::string file, std::string format) const
+  {
+    if(format == "MPS" || format == "LP")
+      CPXwriteprob(cplexEnv(), cplexLp(), file.c_str(), format.c_str());
+    else if(format == "SOL")
+      CPXsolwrite(cplexEnv(), cplexLp(), file.c_str());
+    else throw UnsupportedFormatError(format);
+  }
   // CplexLp members

lemon/cplex.h

-                      r746
+                      r1063
     bool _message_enabled;
+    void _write(std::string file, std::string format) const;
   public:
 …
     const cpxlp* cplexLp() const { return _prob; }
+#ifdef DOXYGEN
+    /// Write the problem or the solution to a file in the given format
+    /// This function writes the problem or the solution
+    /// to a file in the given format.
+    /// Trying to write in an unsupported format will trigger
+    /// \ref UnsupportedFormatError.
+    /// \param file The file path
+    /// \param format The output file format.
+    /// Supportted formats are "MPS", "LP" and "SOL".
+    void write(std::string file, std::string format = "MPS") const {}
+#endif
   };

lemon/cycle_canceling.h

-                      r1070
+                      r1071
   /// \ref CycleCanceling implements three different cycle-canceling
   /// algorithms for finding a \ref min_cost_flow "minimum cost flow"
   /// \ref amo93networkflows, \ref klein67primal,
   /// \ref goldberg89cyclecanceling.
+  /// \cite amo93networkflows, \cite klein67primal,
+  /// \cite goldberg89cyclecanceling.
   /// The most efficent one is the \ref CANCEL_AND_TIGHTEN
   /// "Cancel-and-Tighten" algorithm, thus it is the default method.
   /// It runs in strongly polynomial time, but in practice, it is typically
   /// orders of magnitude slower than the scaling algorithms and
   /// \ref NetworkSimplex.
+  /// It runs in strongly polynomial time O(n<sup>2</sup>e<sup>2</sup>log(n)),
+  /// but in practice, it is typically orders of magnitude slower than
+  /// the scaling algorithms and \ref NetworkSimplex.
   /// (For more information, see \ref min_cost_flow_algs "the module page".)
   ///
 …
       /// The "Minimum Mean Cycle-Canceling" algorithm, which is a
       /// well-known strongly polynomial method
       /// \ref goldberg89cyclecanceling. It improves along a
+      /// \cite goldberg89cyclecanceling. It improves along a
       /// \ref min_mean_cycle "minimum mean cycle" in each iteration.
       /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)).
 …
       /// The "Cancel-and-Tighten" algorithm, which can be viewed as an
       /// improved version of the previous method
       /// \ref goldberg89cyclecanceling.
+      /// \cite goldberg89cyclecanceling.
       /// It is faster both in theory and in practice, its running time
       /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)).

lemon/glpk.cc

-                      r989
+                      r1063
       break;
+    }
+  }
+  void GlpkBase::_write(std::string file, std::string format) const
+  {
+    if(format == "MPS")
+      glp_write_mps(lp, GLP_MPS_FILE, 0, file.c_str());
+    else if(format == "LP")
+      glp_write_lp(lp, 0, file.c_str());
+    else throw UnsupportedFormatError(format);
+  }
 …
   const char* GlpkMip::_solverName() const { return "GlpkMip"; }
 } //END OF NAMESPACE LEMON

lemon/glpk.h

-                      r877
+                      r1063
     virtual void _messageLevel(MessageLevel level);
+    virtual void _write(std::string file, std::string format) const;
   private:
 …
     int lpxCol(Col c) const { return cols(id(c)); }
+#ifdef DOXYGEN
+    /// Write the problem or the solution to a file in the given format
+    /// This function writes the problem or the solution
+    /// to a file in the given format.
+    /// Trying to write in an unsupported format will trigger
+    /// \ref UnsupportedFormatError.
+    /// \param file The file path
+    /// \param format The output file format.
+    /// Supportted formats are "MPS" and "LP".
+    void write(std::string file, std::string format = "MPS") const {}
+#endif
   };

lemon/grosso_locatelli_pullan_mc.h

r918	r1053
41	41	/// \ref GrossoLocatelliPullanMc implements the iterated local search
42	42	/// algorithm of Grosso, Locatelli, and Pullan for solving the \e maximum
43		/// \e clique \e problem \~~ref~~ grosso08maxclique.
	43	/// \e clique \e problem \cite grosso08maxclique.
44	44	/// It is to find the largest complete subgraph (\e clique) in an
45	45	/// undirected graph, i.e., the largest set of nodes where each

lemon/hartmann_orlin_mmc.h

-                      r1002
+                      r1053
   /// This class implements the Hartmann-Orlin algorithm for finding
   /// a directed cycle of minimum mean cost in a digraph
+  /// \ref hartmann93finding, \ref dasdan98minmeancycle.
+  /// It is an improved version of \ref KarpMmc "Karp"'s original algorithm,
+  /// it applies an efficient early termination scheme.
+  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
+  /// \cite hartmann93finding, \cite dasdan98minmeancycle.
+  /// This method is based on \ref KarpMmc "Karp"'s original algorithm, but
+  /// applies an early termination scheme. It makes the algorithm
+  /// significantly faster for some problem instances, but slower for others.
+  /// The algorithm runs in time O(ne) and uses space O(n<sup>2</sup>+e).
   ///
   /// \tparam GR The type of the digraph the algorithm runs on.
 …
     ///
     /// If you don't call this function before calling \ref run() or
     /// \ref findCycleMean(), it will allocate a local \ref Path "path"
     /// structure. The destuctor deallocates this automatically
+    /// \ref findCycleMean(), a local \ref Path "path" structure
+    /// will be allocated. The destuctor deallocates this automatically
     /// allocated object, of course.
     ///

lemon/howard_mmc.h

-                      r1012
+                      r1053
   /// This class implements Howard's policy iteration algorithm for finding
   /// a directed cycle of minimum mean cost in a digraph
   /// \ref dasdan98minmeancycle, \ref dasdan04experimental.
+  /// \cite dasdan98minmeancycle, \cite dasdan04experimental.
   /// This class provides the most efficient algorithm for the
   /// minimum mean cycle problem, though the best known theoretical
 …
     ///
     /// If you don't call this function before calling \ref run() or
     /// \ref findCycleMean(), it will allocate a local \ref Path "path"
     /// structure. The destuctor deallocates this automatically
+    /// \ref findCycleMean(), a local \ref Path "path" structure
+    /// will be allocated. The destuctor deallocates this automatically
     /// allocated object, of course.
     ///

lemon/karp_mmc.h

-                      r1002
+                      r1053
   /// This class implements Karp's algorithm for finding a directed
   /// cycle of minimum mean cost in a digraph
   /// \ref karp78characterization, \ref dasdan98minmeancycle.
+  /// \cite karp78characterization, \cite dasdan98minmeancycle.
   /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
   ///
 …
     ///
     /// If you don't call this function before calling \ref run() or
     /// \ref findCycleMean(), it will allocate a local \ref Path "path"
     /// structure. The destuctor deallocates this automatically
+    /// \ref findCycleMean(), a local \ref Path "path" structure
+    /// will be allocated. The destuctor deallocates this automatically
     /// allocated object, of course.
     ///

lemon/list_graph.h

r1025	r1049
446	446	///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are
447	447	///invalidated for the outgoing arcs of node \c v and \c InArcIt
448		///iterators are invalidated for the incomming arcs of \c v.
	448	///iterators are invalidated for the incoming arcs of \c v.
449	449	///Moreover all iterators referencing node \c v or the removed
450	450	///loops are also invalidated. Other iterators remain valid.

lemon/lp.h

-                      r877
+                      r1064
   ///\ingroup lp_group
   ///
   ///Currently, the possible values are \c GLPK or \c CPLEX
+  ///Currently, the possible values are \c GLPK, \c CPLEX or \c CBC
 #define LEMON_DEFAULT_MIP SOLVER
   ///The default MIP solver.
 …
   ///\ingroup lp_group
   ///
   ///Currently, it is either \c GlpkMip or \c CplexMip
+  ///Currently, it is either \c GlpkMip, \c CplexMip , \c CbcMip
   typedef GlpkMip Mip;
 #else
+#ifdef LEMON_HAVE_GLPK
+# define LEMON_DEFAULT_LP GLPK
+#if LEMON_DEFAULT_LP == GLPK
   typedef GlpkLp Lp;
+# define LEMON_DEFAULT_MIP GLPK
+  typedef GlpkMip Mip;
+#elif LEMON_HAVE_CPLEX
+# define LEMON_DEFAULT_LP CPLEX
+#elif LEMON_DEFAULT_LP == CPLEX
   typedef CplexLp Lp;
+# define LEMON_DEFAULT_MIP CPLEX
+#elif LEMON_DEFAULT_LP == SOPLEX
+  typedef SoplexLp Lp;
+#elif LEMON_DEFAULT_LP == CLP
+  typedef ClpLp Lp;
+#endif
+#if LEMON_DEFAULT_MIP == GLPK
+  typedef GlpkLp Mip;
+#elif LEMON_DEFAULT_MIP == CPLEX
   typedef CplexMip Mip;
+#elif LEMON_HAVE_SOPLEX
+# define DEFAULT_LP SOPLEX
+  typedef SoplexLp Lp;
+#elif LEMON_HAVE_CLP
+# define DEFAULT_LP CLP
+  typedef ClpLp Lp;
+#elif LEMON_DEFAULT_MIP == CBC
+  typedef CbcMip Mip;
 #endif
 #endif

lemon/lp_base.h

-                      r989
+                      r1063
   public:
+    ///\e
+    class UnsupportedFormatError : public Exception
+    {
+      std::string _format;
+      mutable std::string _what;
+    public:
+      explicit UnsupportedFormatError(std::string format) throw()
+        : _format(format) { }
+      virtual ~UnsupportedFormatError() throw() {}
+      virtual const char* what() const throw() {
+        try {
+          _what.clear();
+          std::ostringstream oss;
+          oss << "lemon::UnsupportedFormatError: " << _format;
+          _what = oss.str();
+        }
+        catch (...) {}
+        if (!_what.empty()) return _what.c_str();
+        else return "lemon::UnsupportedFormatError";
+      }
+    };
+  protected:
+    virtual void _write(std::string, std::string format) const
+    {
+      throw UnsupportedFormatError(format);
+    }
+  public:
     /// Virtual destructor
     virtual ~LpBase() {}
 …
     void min() { _setSense(MIN); }
     ///Clears the problem
+    ///Clear the problem
     void clear() { _clear(); rows.clear(); cols.clear(); }
     /// Sets the message level of the solver
+    /// Set the message level of the solver
     void messageLevel(MessageLevel level) { _messageLevel(level); }
+    /// Write the problem to a file in the given format
+    /// This function writes the problem to a file in the given format.
+    /// Different solver backends may support different formats.
+    /// Trying to write in an unsupported format will trigger
+    /// \ref UnsupportedFormatError. For the supported formats,
+    /// visit the documentation of the base class of the related backends
+    /// (\ref CplexBase, \ref GlpkBase etc.)
+    /// \param file The file path
+    /// \param format The output file format.
+    void write(std::string file, std::string format = "MPS") const
+    {
+      _write(file.c_str(),format.c_str());
+    }
     ///@}

lemon/lp_skeleton.cc

r877	r1063
92	92	void SkeletonSolverBase::_messageLevel(MessageLevel) {}
93	93
	94	void SkeletonSolverBase::_write(std::string, std::string) const {}
	95
94	96	LpSkeleton::SolveExitStatus LpSkeleton::_solve() { return SOLVED; }
95	97

lemon/lp_skeleton.h

-                      r877
+                      r1063
     ///\e
     virtual void _messageLevel(MessageLevel);
+    ///\e
+    virtual void _write(std::string file, std::string format) const;
   };
 …
     ///\e
     virtual const char* _solverName() const;
   };

lemon/math.h

-                      r877
+                      r1054
+    }
+  ///Round a value to its closest integer
+  inline double round(double r) {
+    return (r > 0.0) ? floor(r + 0.5) : ceil(r - 0.5);
+  }
   /// @}
 } //namespace lemon
 #endif //LEMON_TOLERANCE_H
+#endif //LEMON_MATH_H

lemon/network_simplex.h

-                      r1070
+                      r1071
   /// \ref NetworkSimplex implements the primal Network Simplex algorithm
   /// for finding a \ref min_cost_flow "minimum cost flow"
   /// \ref amo93networkflows, \ref dantzig63linearprog,
   /// \ref kellyoneill91netsimplex.
+  /// \cite amo93networkflows, \cite dantzig63linearprog,
+  /// \cite kellyoneill91netsimplex.
   /// This algorithm is a highly efficient specialized version of the
   /// linear programming simplex method directly for the minimum cost
 …
+          }
         } else {
           // Find the min. cost incomming arc for each demand node
+          // Find the min. cost incoming arc for each demand node
           for (int i = 0; i != int(demand_nodes.size()); ++i) {
             Node v = demand_nodes[i];

lemon/path.h

r1000	r1044
318	318	/// Constructor with starting point
319	319	ArcIt(const SimplePath &_path, int _idx)
320		: ~~idx(_idx), path(&_path~~) {}
	320	: path(&_path), idx(_idx) {}
321	321
322	322	public:

lemon/preflow.h

-                      r966
+                      r1053
   /// This class provides an implementation of Goldberg-Tarjan's \e preflow
   /// \e push-relabel algorithm producing a \ref max_flow
   /// "flow of maximum value" in a digraph \ref clrs01algorithms,
   /// \ref amo93networkflows, \ref goldberg88newapproach.
+  /// "flow of maximum value" in a digraph \cite clrs01algorithms,
+  /// \cite amo93networkflows, \cite goldberg88newapproach.
   /// The preflow algorithms are the fastest known maximum
   /// flow algorithms. The current implementation uses a mixture of the

lemon/time_measure.h

-                      r786
+                      r1054
 #include <fstream>
 #include <iostream>
+#include <lemon/math.h>
 namespace lemon {
 …
     double rtime;
+  public:
+    ///Display format specifier
+    ///\e
+    ///
+    enum Format {
+      /// Reports all measured values
+      NORMAL = 0,
+      /// Only real time and an error indicator is displayed
+      SHORT = 1
+    };
+  private:
+    static Format _format;
     void _reset() {
       utime = stime = cutime = cstime = rtime = 0;
 …
   public:
+    ///Set output format
+    ///Set output format.
+    ///
+    ///The output format is global for all timestamp instances.
+    static void format(Format f) { _format = f; }
+    ///Retrieve the current output format
+    ///Retrieve the current output format
+    ///
+    ///The output format is global for all timestamp instances.
+    static Format format() { return _format; }
     ///Read the current time values of the process
     void stamp()
 …
   inline std::ostream& operator<<(std::ostream& os,const TimeStamp &t)
+  {
+    os << "u: " << t.userTime() <<
+      "s, s: " << t.systemTime() <<
+      "s, cu: " << t.cUserTime() <<
+      "s, cs: " << t.cSystemTime() <<
+      "s, real: " << t.realTime() << "s";
+    switch(t._format)
+      {
+      case TimeStamp::NORMAL:
+        os << "u: " << t.userTime() <<
+          "s, s: " << t.systemTime() <<
+          "s, cu: " << t.cUserTime() <<
+          "s, cs: " << t.cSystemTime() <<
+          "s, real: " << t.realTime() << "s";
+        break;
+      case TimeStamp::SHORT:
+        double total = t.userTime()+t.systemTime()+
+          t.cUserTime()+t.cSystemTime();
+        os << t.realTime()
+           << "s (err: " << round((t.realTime()-total)/
+                                  t.realTime()*10000)/100
+           << "%)";
+        break;
+      }
     return os;
+  }
 …
     std::string _title;
     std::ostream &_os;
+    bool _active;
   public:
     ///Constructor
 …
     ///\param os The stream to print the report to.
     ///\param run Sets whether the timer should start immediately.
+    TimeReport(std::string title,std::ostream &os=std::cerr,bool run=true)
+      : Timer(run), _title(title), _os(os){}
+    ///\param active Sets whether the report should actually be printed
+    ///       on destruction.
+    TimeReport(std::string title,std::ostream &os=std::cerr,bool run=true,
+               bool active=true)
+      : Timer(run), _title(title), _os(os), _active(active) {}
     ///Destructor that prints the ellapsed time
     ~TimeReport()
+    {
+      _os << _title << *this << std::endl;
+    }
+      if(_active) _os << _title << *this << std::endl;
+    }
+    ///Retrieve the activity status
+    ///\e
+    ///
+    bool active() const { return _active; }
+    ///Set the activity status
+    /// This function set whether the time report should actually be printed
+    /// on destruction.
+    void active(bool a) { _active=a; }
   };

test/CMakeLists.txt

-                      r1038
+                      r1065
   max_cardinality_search_test
   max_clique_test
+  max_flow_test
   min_cost_arborescence_test
   min_cost_flow_test
 …
   path_test
   planarity_test
-  preflow_test
   radix_sort_test
   random_test
 …
   ENDIF()
   IF(LEMON_HAVE_CPLEX)
     SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${CPLEX_LIBRARIES})
+    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${ILOG_LIBRARIES})
   ENDIF()
   IF(LEMON_HAVE_CLP)
 …
     GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
     ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD
       COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex.dll ${TARGET_PATH}
+      COMMAND ${CMAKE_COMMAND} -E copy ${ILOG_CPLEX_DLL} ${TARGET_PATH}
+    )
   ENDIF()
 …
   ENDIF()
   IF(LEMON_HAVE_CPLEX)
     SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${CPLEX_LIBRARIES})
+    SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${ILOG_LIBRARIES})
   ENDIF()
   IF(LEMON_HAVE_CBC)
 …
     GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
     ADD_CUSTOM_COMMAND(TARGET mip_test POST_BUILD
       COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex.dll ${TARGET_PATH}
+      COMMAND ${CMAKE_COMMAND} -E copy ${ILOG_CPLEX_DLL} ${TARGET_PATH}
+    )
   ENDIF()

test/lp_test.cc

-                      r988
+                      r1064
+  {
     LP::DualExpr e,f,g;
+    LP::Row p1 = INVALID, p2 = INVALID, p3 = INVALID,
+      p4 = INVALID, p5 = INVALID;
+    LP::Row p1 = INVALID, p2 = INVALID;
     e[p1]=2;

test/maps_test.cc

-                      r998
+                      r1067
     typedef Orienter<Graph, const ConstMap<Edge, bool> > Digraph;
+    Digraph dgr(gr, constMap<Edge, bool>(true));
+    ConstMap<Edge, bool> true_edge_map(true);
+    Digraph dgr(gr, true_edge_map);
     OutDegMap<Digraph> odm(dgr);
     InDegMap<Digraph> idm(dgr);

test/path_test.cc

-                      r990
+                      r1044
 #include <lemon/concepts/path.h>
 #include <lemon/concepts/digraph.h>
+#include <lemon/concept_check.h>
 #include <lemon/path.h>
 …
 using namespace lemon;
+void check_concepts() {
+  checkConcept<concepts::Path<ListDigraph>, concepts::Path<ListDigraph> >();
+  checkConcept<concepts::Path<ListDigraph>, Path<ListDigraph> >();
+  checkConcept<concepts::Path<ListDigraph>, SimplePath<ListDigraph> >();
+  checkConcept<concepts::Path<ListDigraph>, StaticPath<ListDigraph> >();
+  checkConcept<concepts::Path<ListDigraph>, ListPath<ListDigraph> >();
+template <typename GR>
+void checkConcepts() {
+  checkConcept<concepts::Path<GR>, concepts::Path<GR> >();
+  checkConcept<concepts::Path<GR>, Path<GR> >();
+  checkConcept<concepts::Path<GR>, SimplePath<GR> >();
+  checkConcept<concepts::Path<GR>, StaticPath<GR> >();
+  checkConcept<concepts::Path<GR>, ListPath<GR> >();
+}
+// Conecpt checking for path structures
+void checkPathConcepts() {
+  checkConcepts<concepts::Digraph>();
+  checkConcepts<ListDigraph>();
+}
 // Check if proper copy consructor is called (use valgrind for testing)
+template<class _Path>
+void checkCopy()
+{
+template <typename GR, typename P1, typename P2>
+void checkCopy(typename GR::Arc a) {
+  P1 p;
+  p.addBack(a);
+  P1 q;
+  q = p;
+  P1 r(p);
+  P2 q2;
+  q2 = p;
+  P2 r2(p);
+}
+// Tests for copy constructors and assignment operators of paths
+void checkPathCopy() {
   ListDigraph g;
+  ListDigraph::Arc a  = g.addArc(g.addNode(), g.addNode());
+  _Path p,q;
+  p.addBack(a);
+  q=p;
+  _Path r(p);
+  StaticPath<ListDigraph> s(r);
+}
+  ListDigraph::Arc a = g.addArc(g.addNode(), g.addNode());
+  typedef Path<ListDigraph> Path1;
+  typedef SimplePath<ListDigraph> Path2;
+  typedef ListPath<ListDigraph> Path3;
+  typedef StaticPath<ListDigraph> Path4;
+  checkCopy<ListDigraph, Path1, Path2>(a);
+  checkCopy<ListDigraph, Path1, Path3>(a);
+  checkCopy<ListDigraph, Path1, Path4>(a);
+  checkCopy<ListDigraph, Path2, Path1>(a);
+  checkCopy<ListDigraph, Path2, Path3>(a);
+  checkCopy<ListDigraph, Path2, Path4>(a);
+  checkCopy<ListDigraph, Path3, Path1>(a);
+  checkCopy<ListDigraph, Path3, Path2>(a);
+  checkCopy<ListDigraph, Path3, Path4>(a);
+}
+// Class for testing path functions
+class CheckPathFunctions {
+  typedef ListDigraph GR;
+  DIGRAPH_TYPEDEFS(GR);
+  GR gr;
+  const GR& cgr;
+  Node n1, n2, n3, n4;
+  Node tmp_n;
+  Arc a1, a2, a3, a4;
+  Arc tmp_a;
+public:
+  CheckPathFunctions() : cgr(gr) {
+    n1 = gr.addNode();
+    n2 = gr.addNode();
+    n3 = gr.addNode();
+    n4 = gr.addNode();
+    a1 = gr.addArc(n1, n2);
+    a2 = gr.addArc(n2, n3);
+    a3 = gr.addArc(n3, n4);
+    a4 = gr.addArc(n4, n1);
+  }
+  void run() {
+    checkBackAndFrontInsertablePath<Path<GR> >();
+    checkBackAndFrontInsertablePath<ListPath<GR> >();
+    checkBackInsertablePath<SimplePath<GR> >();
+    checkListPathSplitAndSplice();
+  }
+private:
+  template <typename P>
+  void checkBackInsertablePath() {
+    // Create and check empty path
+    P p;
+    const P& cp = p;
+    check(cp.empty(), "The path is not empty");
+    check(cp.length() == 0, "The path is not empty");
+//    check(cp.front() == INVALID, "Wrong front()");
+//    check(cp.back() == INVALID, "Wrong back()");
+    typename P::ArcIt ai(cp);
+    check(ai == INVALID, "Wrong ArcIt");
+    check(pathSource(cgr, cp) == INVALID, "Wrong pathSource()");
+    check(pathTarget(cgr, cp) == INVALID, "Wrong pathTarget()");
+    check(checkPath(cgr, cp), "Wrong checkPath()");
+    PathNodeIt<P> ni(cgr, cp);
+    check(ni == INVALID, "Wrong PathNodeIt");
+    // Check single-arc path
+    p.addBack(a1);
+    check(!cp.empty(), "Wrong empty()");
+    check(cp.length() == 1, "Wrong length");
+    check(cp.front() == a1, "Wrong front()");
+    check(cp.back() == a1, "Wrong back()");
+    check(cp.nth(0) == a1, "Wrong nth()");
+    ai = cp.nthIt(0);
+    check((tmp_a = ai) == a1, "Wrong nthIt()");
+    check(++ai == INVALID, "Wrong nthIt()");
+    typename P::ArcIt ai2(cp);
+    check((tmp_a = ai2) == a1, "Wrong ArcIt");
+    check(++ai2 == INVALID, "Wrong ArcIt");
+    check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
+    check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
+    check(checkPath(cgr, cp), "Wrong checkPath()");
+    PathNodeIt<P> ni2(cgr, cp);
+    check((tmp_n = ni2) == n1, "Wrong PathNodeIt");
+    check((tmp_n = ++ni2) == n2, "Wrong PathNodeIt");
+    check(++ni2 == INVALID, "Wrong PathNodeIt");
+    // Check adding more arcs
+    p.addBack(a2);
+    p.addBack(a3);
+    check(!cp.empty(), "Wrong empty()");
+    check(cp.length() == 3, "Wrong length");
+    check(cp.front() == a1, "Wrong front()");
+    check(cp.back() == a3, "Wrong back()");
+    check(cp.nth(0) == a1, "Wrong nth()");
+    check(cp.nth(1) == a2, "Wrong nth()");
+    check(cp.nth(2) == a3, "Wrong nth()");
+    typename P::ArcIt ai3(cp);
+    check((tmp_a = ai3) == a1, "Wrong ArcIt");
+    check((tmp_a = ++ai3) == a2, "Wrong nthIt()");
+    check((tmp_a = ++ai3) == a3, "Wrong nthIt()");
+    check(++ai3 == INVALID, "Wrong nthIt()");
+    ai = cp.nthIt(0);
+    check((tmp_a = ai) == a1, "Wrong nthIt()");
+    check((tmp_a = ++ai) == a2, "Wrong nthIt()");
+    ai = cp.nthIt(2);
+    check((tmp_a = ai) == a3, "Wrong nthIt()");
+    check(++ai == INVALID, "Wrong nthIt()");
+    check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
+    check(pathTarget(cgr, cp) == n4, "Wrong pathTarget()");
+    check(checkPath(cgr, cp), "Wrong checkPath()");
+    PathNodeIt<P> ni3(cgr, cp);
+    check((tmp_n = ni3) == n1, "Wrong PathNodeIt");
+    check((tmp_n = ++ni3) == n2, "Wrong PathNodeIt");
+    check((tmp_n = ++ni3) == n3, "Wrong PathNodeIt");
+    check((tmp_n = ++ni3) == n4, "Wrong PathNodeIt");
+    check(++ni3 == INVALID, "Wrong PathNodeIt");
+    // Check arc removal and addition
+    p.eraseBack();
+    p.eraseBack();
+    p.addBack(a2);
+    check(!cp.empty(), "Wrong empty()");
+    check(cp.length() == 2, "Wrong length");
+    check(cp.front() == a1, "Wrong front()");
+    check(cp.back() == a2, "Wrong back()");
+    check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
+    check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()");
+    check(checkPath(cgr, cp), "Wrong checkPath()");
+    // Check clear()
+    p.clear();
+    check(cp.empty(), "The path is not empty");
+    check(cp.length() == 0, "The path is not empty");
+    // Check inconsistent path
+    p.addBack(a4);
+    p.addBack(a2);
+    p.addBack(a1);
+    check(!cp.empty(), "Wrong empty()");
+    check(cp.length() == 3, "Wrong length");
+    check(cp.front() == a4, "Wrong front()");
+    check(cp.back() == a1, "Wrong back()");
+    check(pathSource(cgr, cp) == n4, "Wrong pathSource()");
+    check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
+    check(!checkPath(cgr, cp), "Wrong checkPath()");
+  }
+  template <typename P>
+  void checkBackAndFrontInsertablePath() {
+    // Include back insertable test cases
+    checkBackInsertablePath<P>();
+    // Check front and back insertion
+    P p;
+    const P& cp = p;
+    p.addFront(a4);
+    p.addBack(a1);
+    p.addFront(a3);
+    check(!cp.empty(), "Wrong empty()");
+    check(cp.length() == 3, "Wrong length");
+    check(cp.front() == a3, "Wrong front()");
+    check(cp.back() == a1, "Wrong back()");
+    check(cp.nth(0) == a3, "Wrong nth()");
+    check(cp.nth(1) == a4, "Wrong nth()");
+    check(cp.nth(2) == a1, "Wrong nth()");
+    typename P::ArcIt ai(cp);
+    check((tmp_a = ai) == a3, "Wrong ArcIt");
+    check((tmp_a = ++ai) == a4, "Wrong nthIt()");
+    check((tmp_a = ++ai) == a1, "Wrong nthIt()");
+    check(++ai == INVALID, "Wrong nthIt()");
+    ai = cp.nthIt(0);
+    check((tmp_a = ai) == a3, "Wrong nthIt()");
+    check((tmp_a = ++ai) == a4, "Wrong nthIt()");
+    ai = cp.nthIt(2);
+    check((tmp_a = ai) == a1, "Wrong nthIt()");
+    check(++ai == INVALID, "Wrong nthIt()");
+    check(pathSource(cgr, cp) == n3, "Wrong pathSource()");
+    check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
+    check(checkPath(cgr, cp), "Wrong checkPath()");
+    // Check eraseFront()
+    p.eraseFront();
+    p.addBack(a2);
+    check(!cp.empty(), "Wrong empty()");
+    check(cp.length() == 3, "Wrong length");
+    check(cp.front() == a4, "Wrong front()");
+    check(cp.back() == a2, "Wrong back()");
+    check(cp.nth(0) == a4, "Wrong nth()");
+    check(cp.nth(1) == a1, "Wrong nth()");
+    check(cp.nth(2) == a2, "Wrong nth()");
+    typename P::ArcIt ai2(cp);
+    check((tmp_a = ai2) == a4, "Wrong ArcIt");
+    check((tmp_a = ++ai2) == a1, "Wrong nthIt()");
+    check((tmp_a = ++ai2) == a2, "Wrong nthIt()");
+    check(++ai2 == INVALID, "Wrong nthIt()");
+    ai = cp.nthIt(0);
+    check((tmp_a = ai) == a4, "Wrong nthIt()");
+    check((tmp_a = ++ai) == a1, "Wrong nthIt()");
+    ai = cp.nthIt(2);
+    check((tmp_a = ai) == a2, "Wrong nthIt()");
+    check(++ai == INVALID, "Wrong nthIt()");
+    check(pathSource(cgr, cp) == n4, "Wrong pathSource()");
+    check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()");
+    check(checkPath(cgr, cp), "Wrong checkPath()");
+  }
+  void checkListPathSplitAndSplice() {
+    // Build a path with spliceFront() and spliceBack()
+    ListPath<GR> p1, p2, p3, p4;
+    p1.addBack(a3);
+    p1.addFront(a2);
+    p2.addBack(a1);
+    p1.spliceFront(p2);
+    p3.addFront(a4);
+    p1.spliceBack(p3);
+    check(p1.length() == 4, "Wrong length");
+    check(p1.front() == a1, "Wrong front()");
+    check(p1.back() == a4, "Wrong back()");
+    ListPath<GR>::ArcIt ai(p1);
+    check((tmp_a = ai) == a1, "Wrong ArcIt");
+    check((tmp_a = ++ai) == a2, "Wrong nthIt()");
+    check((tmp_a = ++ai) == a3, "Wrong nthIt()");
+    check((tmp_a = ++ai) == a4, "Wrong nthIt()");
+    check(++ai == INVALID, "Wrong nthIt()");
+    check(checkPath(cgr, p1), "Wrong checkPath()");
+    // Check split()
+    p1.split(p1.nthIt(2), p2);
+    check(p1.length() == 2, "Wrong length");
+    ai = p1.nthIt(0);
+    check((tmp_a = ai) == a1, "Wrong ArcIt");
+    check((tmp_a = ++ai) == a2, "Wrong nthIt()");
+    check(++ai == INVALID, "Wrong nthIt()");
+    check(checkPath(cgr, p1), "Wrong checkPath()");
+    check(p2.length() == 2, "Wrong length");
+    ai = p2.nthIt(0);
+    check((tmp_a = ai) == a3, "Wrong ArcIt");
+    check((tmp_a = ++ai) == a4, "Wrong nthIt()");
+    check(++ai == INVALID, "Wrong nthIt()");
+    check(checkPath(cgr, p2), "Wrong checkPath()");
+    // Check split() and splice()
+    p1.spliceFront(p2);
+    p1.split(p1.nthIt(2), p2);
+    p2.split(p2.nthIt(1), p3);
+    p2.spliceBack(p1);
+    p2.splice(p2.nthIt(1), p3);
+    check(p2.length() == 4, "Wrong length");
+    check(p2.front() == a1, "Wrong front()");
+    check(p2.back() == a4, "Wrong back()");
+    ai = p2.nthIt(0);
+    check((tmp_a = ai) == a1, "Wrong ArcIt");
+    check((tmp_a = ++ai) == a2, "Wrong nthIt()");
+    check((tmp_a = ++ai) == a3, "Wrong nthIt()");
+    check((tmp_a = ++ai) == a4, "Wrong nthIt()");
+    check(++ai == INVALID, "Wrong nthIt()");
+    check(checkPath(cgr, p2), "Wrong checkPath()");
+  }
+};
 int main() {
+  check_concepts();
+  checkCopy<Path<ListDigraph> >();
+  checkCopy<SimplePath<ListDigraph> >();
+  checkCopy<ListPath<ListDigraph> >();
+  ListDigraph g;
+  ListDigraph::Arc a  = g.addArc(g.addNode(), g.addNode());
+  Path<ListDigraph> p;
+  StaticPath<ListDigraph> q,r;
+  p.addBack(a);
+  q=p;
+  r=q;
+  StaticPath<ListDigraph> s(q);
+  checkPathConcepts();
+  checkPathCopy();
+  CheckPathFunctions cpf;
+  cpf.run();
   return 0;

Context Navigation

Changes in / [1070:ee9bac10f58e:1071:879fcb781086] in lemon-main

Legend:

Download in other formats: