Changes in / [1071:879fcb781086:1070:ee9bac10f58e] in lemon-main
- Files:
-
- 3 added
- 6 deleted
- 49 edited
Legend:
- Unmodified
- Added
- Removed
-
CMakeLists.txt
r1066 r1017 62 62 FIND_PACKAGE(Doxygen) 63 63 FIND_PACKAGE(Ghostscript) 64 65 SET(LEMON_ENABLE_GLPK YES CACHE STRING "Enable GLPK solver backend.") 66 SET(LEMON_ENABLE_ILOG YES CACHE STRING "Enable ILOG (CPLEX) solver backend.") 67 SET(LEMON_ENABLE_COIN YES CACHE STRING "Enable COIN solver backend.") 68 69 IF(LEMON_ENABLE_GLPK) 70 FIND_PACKAGE(GLPK 4.33) 71 ENDIF(LEMON_ENABLE_GLPK) 72 IF(LEMON_ENABLE_ILOG) 73 FIND_PACKAGE(ILOG) 74 ENDIF(LEMON_ENABLE_ILOG) 75 IF(LEMON_ENABLE_COIN) 76 FIND_PACKAGE(COIN) 77 ENDIF(LEMON_ENABLE_COIN) 78 79 IF(GLPK_FOUND) 80 SET(LEMON_HAVE_LP TRUE) 81 SET(LEMON_HAVE_MIP TRUE) 82 SET(LEMON_HAVE_GLPK TRUE) 83 ENDIF(GLPK_FOUND) 84 IF(ILOG_FOUND) 85 SET(LEMON_HAVE_LP TRUE) 86 SET(LEMON_HAVE_MIP TRUE) 87 SET(LEMON_HAVE_CPLEX TRUE) 88 ENDIF(ILOG_FOUND) 89 IF(COIN_FOUND) 90 SET(LEMON_HAVE_LP TRUE) 91 SET(LEMON_HAVE_MIP TRUE) 92 SET(LEMON_HAVE_CLP TRUE) 93 SET(LEMON_HAVE_CBC TRUE) 94 ENDIF(COIN_FOUND) 95 96 IF(ILOG_FOUND) 97 SET(DEFAULT_LP "CPLEX") 98 SET(DEFAULT_MIP "CPLEX") 99 ELSEIF(COIN_FOUND) 100 SET(DEFAULT_LP "CLP") 101 SET(DEFAULT_MIP "CBC") 102 ELSEIF(GLPK_FOUND) 103 SET(DEFAULT_LP "GLPK") 104 SET(DEFAULT_MIP "GLPK") 105 ENDIF() 106 107 IF(NOT LEMON_DEFAULT_LP OR 108 (NOT ILOG_FOUND AND (LEMON_DEFAULT_LP STREQUAL "CPLEX")) OR 109 (NOT COIN_FOUND AND (LEMON_DEFAULT_LP STREQUAL "CLP")) OR 110 (NOT GLPK_FOUND AND (LEMON_DEFAULT_LP STREQUAL "GLPK"))) 111 SET(LEMON_DEFAULT_LP ${DEFAULT_LP} CACHE STRING 112 "Default LP solver backend (GLPK, CPLEX or CLP)" FORCE) 113 ENDIF() 114 IF(NOT LEMON_DEFAULT_MIP OR 115 (NOT ILOG_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "CPLEX")) OR 116 (NOT COIN_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "CBC")) OR 117 (NOT GLPK_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "GLPK"))) 118 SET(LEMON_DEFAULT_MIP ${DEFAULT_MIP} CACHE STRING 119 "Default MIP solver backend (GLPK, CPLEX or CBC)" FORCE) 120 ENDIF() 121 64 FIND_PACKAGE(GLPK 4.33) 65 FIND_PACKAGE(CPLEX) 66 FIND_PACKAGE(COIN) 122 67 123 68 IF(DEFINED ENV{LEMON_CXX_WARNING}) -
INSTALL
r1065 r1040 135 135 136 136 137 -DLEMON_ENABLE_GLPK=NO138 -DLEMON_ENABLE_COIN=NO139 -DLEMON_ENABLE_ILOG=NO140 141 Enable optional third party libraries. They are all enabled by default.142 143 -DLEMON_DEFAULT_LP=GLPK144 145 Sets the default LP solver backend. The supported values are146 CPLEX, CLP and GLPK. By default, it is set to the first one which147 is enabled and succesfully discovered.148 149 -DLEMON_DEFAULT_MIP=GLPK150 151 Sets the default MIP solver backend. The supported values are152 CPLEX, CBC and GLPK. By default, it is set to the first one which153 is enabled and succesfully discovered.154 155 137 -DGLPK_ROOT_DIR=DIRECTORY 156 138 -DCOIN_ROOT_DIR=DIRECTORY 157 -D ILOG_ROOT_DIR=DIRECTORY139 -DCPLEX_ROOT_DIR=DIRECTORY 158 140 159 Root directory prefixes of optional third party libraries.141 Install root directory prefixes of optional third party libraries. 160 142 161 143 Makefile Variables -
cmake/FindCOIN.cmake
r1064 r973 109 109 COIN_BZ2_LIBRARY 110 110 ) 111 112 IF(COIN_FOUND) 113 SET(LEMON_HAVE_LP TRUE) 114 SET(LEMON_HAVE_MIP TRUE) 115 SET(LEMON_HAVE_CLP TRUE) 116 SET(LEMON_HAVE_CBC TRUE) 117 ENDIF(COIN_FOUND) -
cmake/FindGLPK.cmake
r1064 r638 54 54 55 55 MARK_AS_ADVANCED(GLPK_LIBRARY GLPK_INCLUDE_DIR GLPK_BIN_DIR) 56 57 IF(GLPK_FOUND) 58 SET(LEMON_HAVE_LP TRUE) 59 SET(LEMON_HAVE_MIP TRUE) 60 SET(LEMON_HAVE_GLPK TRUE) 61 ENDIF(GLPK_FOUND) -
doc/CMakeLists.txt
r1053 r1041 35 35 COMMAND ${CMAKE_COMMAND} -E remove_directory gen-images 36 36 COMMAND ${CMAKE_COMMAND} -E make_directory gen-images 37 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r20 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps 38 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/adaptors2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/adaptors2.eps 39 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps 40 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps 41 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps 42 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps 43 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps 44 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r24 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps 45 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r24 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps 46 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r40 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps 47 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r24 -sOutputFile=gen-images/tsp.png ${CMAKE_CURRENT_SOURCE_DIR}/images/tsp.eps 48 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps 49 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps 50 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps 51 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps 52 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps 37 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps 38 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps 39 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps 40 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps 41 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps 42 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps 43 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps 44 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps 45 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps 46 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps 47 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps 48 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps 49 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps 50 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps 51 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/tsp.png ${CMAKE_CURRENT_SOURCE_DIR}/images/tsp.eps 53 52 COMMAND ${CMAKE_COMMAND} -E remove_directory html 53 COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox 54 54 COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile 55 55 WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR} -
doc/Doxyfile.in
r1053 r1040 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"81 80 #--------------------------------------------------------------------------- 82 81 # configuration options related to warning and progress messages -
doc/groups.dox
r1053 r1038 113 113 detailed documentation of particular adaptors. 114 114 115 Since the adaptor classes conform to the \ref graph_concepts "graph concepts",116 an adaptor can even be applied to another one.117 The following image illustrates a situation when a \ref SubDigraph adaptor118 is applied on a digraph and \ref Undirector is applied on the subgraph.119 120 \image html adaptors2.png121 \image latex adaptors2.eps "Using graph adaptors" width=\textwidth122 123 115 The behavior of graph adaptors can be very different. Some of them keep 124 116 capabilities of the original graph while in other cases this would be … … 318 310 This group contains the common graph search algorithms, namely 319 311 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS) 320 \ citeclrs01algorithms.312 \ref clrs01algorithms. 321 313 */ 322 314 … … 327 319 328 320 This group contains the algorithms for finding shortest paths in digraphs 329 \ citeclrs01algorithms.321 \ref clrs01algorithms. 330 322 331 323 - \ref Dijkstra algorithm for finding shortest paths from a source node … … 349 341 350 342 This group contains the algorithms for finding minimum cost spanning 351 trees and arborescences \ citeclrs01algorithms.343 trees and arborescences \ref clrs01algorithms. 352 344 */ 353 345 … … 358 350 359 351 This group contains the algorithms for finding maximum flows and 360 feasible circulations \ cite clrs01algorithms, \citeamo93networkflows.352 feasible circulations \ref clrs01algorithms, \ref amo93networkflows. 361 353 362 354 The \e maximum \e flow \e problem is to find a flow of maximum value between … … 374 366 LEMON contains several algorithms for solving maximum flow problems: 375 367 - \ref EdmondsKarp Edmonds-Karp algorithm 376 \ citeedmondskarp72theoretical.368 \ref edmondskarp72theoretical. 377 369 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm 378 \ citegoldberg88newapproach.370 \ref goldberg88newapproach. 379 371 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees 380 \ cite dinic70algorithm, \citesleator83dynamic.372 \ref dinic70algorithm, \ref sleator83dynamic. 381 373 - \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees 382 \ cite goldberg88newapproach, \citesleator83dynamic.374 \ref goldberg88newapproach, \ref sleator83dynamic. 383 375 384 376 In most cases the \ref Preflow algorithm provides the … … 400 392 401 393 This group contains the algorithms for finding minimum cost flows and 402 circulations \ citeamo93networkflows. For more information about this403 problem and its dual solution, see :\ref min_cost_flow394 circulations \ref amo93networkflows. For more information about this 395 problem and its dual solution, see \ref min_cost_flow 404 396 "Minimum Cost Flow Problem". 405 397 406 398 LEMON contains several algorithms for this problem. 407 399 - \ref NetworkSimplex Primal Network Simplex algorithm with various 408 pivot strategies \ cite dantzig63linearprog, \citekellyoneill91netsimplex.400 pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex. 409 401 - \ref CostScaling Cost Scaling algorithm based on push/augment and 410 relabel operations \ cite goldberg90approximation, \citegoldberg97efficient,411 \ citebunnagel98efficient.402 relabel operations \ref goldberg90approximation, \ref goldberg97efficient, 403 \ref bunnagel98efficient. 412 404 - \ref CapacityScaling Capacity Scaling algorithm based on the successive 413 shortest path method \ citeedmondskarp72theoretical.405 shortest path method \ref edmondskarp72theoretical. 414 406 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are 415 strongly polynomial \ cite klein67primal, \citegoldberg89cyclecanceling.407 strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling. 416 408 417 409 In general, \ref NetworkSimplex and \ref CostScaling are the most efficient … … 429 421 which is capable of handling real-valued arc costs (other numerical 430 422 data are required to be integer). 431 432 For more details about these implementations and for a comprehensive433 experimental study, see the paper \cite KiralyKovacs12MCF.434 It also compares these codes to other publicly available435 minimum cost flow solvers.436 423 */ 437 424 … … 472 459 473 460 This group contains the algorithms for finding minimum mean cycles 474 \ cite amo93networkflows, \citekarp78characterization.461 \ref amo93networkflows, \ref karp78characterization. 475 462 476 463 The \e minimum \e mean \e cycle \e problem is to find a directed cycle … … 488 475 489 476 LEMON contains three algorithms for solving the minimum mean cycle problem: 490 - \ref KarpMmc Karp's original algorithm \ citekarp78characterization.477 - \ref KarpMmc Karp's original algorithm \ref karp78characterization. 491 478 - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved 492 version of Karp's algorithm \ citehartmann93finding.479 version of Karp's algorithm \ref hartmann93finding. 493 480 - \ref HowardMmc Howard's policy iteration algorithm 494 \ cite dasdan98minmeancycle, \citedasdan04experimental.481 \ref dasdan98minmeancycle, \ref dasdan04experimental. 495 482 496 483 In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the … … 498 485 time is exponential. 499 486 Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms 500 run in time O(ne) and use space O(n<sup>2</sup>+e). 487 run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is 488 typically faster due to the applied early termination scheme. 501 489 */ 502 490 … … 648 636 high-level interface. 649 637 650 The currently supported solvers are \ cite glpk, \cite clp, \citecbc,651 \ cite cplex, \citesoplex.638 The currently supported solvers are \ref glpk, \ref clp, \ref cbc, 639 \ref cplex, \ref soplex. 652 640 */ 653 641 … … 736 724 This group contains general \c EPS drawing methods and special 737 725 graph exporting tools. 738 739 \image html graph_to_eps.png740 726 */ 741 727 -
doc/images/bipartite_partitions.eps
r1045 r587 1 1 %!PS-Adobe-2.0 EPSF-2.0 2 2 %%Creator: LEMON, graphToEps() 3 %%CreationDate: Fri Mar 8 00:18:43 20133 %%CreationDate: Tue Nov 15 16:51:43 2005 4 4 %%BoundingBox: 0 0 842 596 5 5 %%EndComments … … 54 54 %Edges: 55 55 gsave 56 513.857 -446.322 296.569 -487.43 79.2808 -528.539 0 0 0 7.00153lb57 513.857 -446.322 575.52 -315.65 6 637.183 -184.989 0 0 0 7.00153lb58 393.468 566.711 494.771 434.577 596.074 302.442 0 0 0 7.00153lb59 393.468 566.711 155.625 579.925 -82.2171 593.138 0 0 0 7.00153lb60 393.468 566.711 251.056 450.726 108.644 334.741 0 0 0 7.00153lb61 869.153 52.8539 732.613 177.648 596.074 302.442 0 0 0 7.00153lb62 869.153 52.8539 753.168 -66.0676 637.183 -184.989 0 0 0 7.00153lb63 -82.2171 593.138 -91.0261 346.487 -99.8351 99.8351 0 0 0 7.00153lb64 -663.61 546.157 -753.168 394.936 -842.726 243.715 0 0 0 7.00153lb65 -663.61 546.157 -574.052 437.513 -484.494 328.869 0 0 0 7.00153lb66 -1077.63 161.498 -960.178 202.606 -842.726 243.715 0 0 0 7.00153lb67 -1077.63 161.498 -968.987 66.0674 -860.344 -29.3633 0 0 0 7.00153lb68 -1177.47 -234.906 -1029.18 -381.722 -880.898 -528.539 0 0 0 7.00153lb69 -1177.47 -234.906 -1018.91 -132.135 -860.344 -29.3633 0 0 0 7.00153lb70 -880.898 -528.539 -744.359 -387.595 -607.82 -246.651 0 0 0 7.00153lb71 -499.175 -499.175 -355.295 -475.685 -211.415 -452.194 0 0 0 7.00153lb72 -499.175 -499.175 -553.498 -372.913 -607.82 -246.651 0 0 0 7.00153lb73 -499.175 -499.175 -386.587 -315.087 -274 -131 0 0 0 7.00153lb74 79.2808 -528.539 -66.0671 -490.366 -211.415 -452.194 0 0 0 7.00153lb75 637.183 -184.989 421.363 -253.993 205.543 -322.996 0 0 0 7.00153lb76 205.543 -322.996 162.966 -226.097 120.389 -129.198 0 0 0 7.00153lb77 399.34 88.0898 259.865 -20.5541 120.389 -129.198 0 0 0 7.00153lb78 399.34 88.0898 253.992 211.415 108.644 334.741 0 0 0 7.00153lb79 -842.726 243.715 -471.281 171.775 -99.8351 99.8351 0 0 0 7.00153lb80 -842.726 243.715 -558.363 56.3575 -274 -131 0 0 0 7.00153lb81 -860.344 -29.3633 -734.082 -138.007 -607.82 -246.651 0 0 0 7.00153lb82 -211.415 -452.194 -45.513 -290.696 120.389 -129.198 0 0 0 7.00153lb83 -99.8351 99.8351 4.40445 217.288 108.644 334.741 0 0 0 7.00153lb84 -99.8351 99.8351 -292.165 214.352 -484.494 328.869 0 0 0 7.00153lb85 120.389 -129.198 -76.8055 -130.099 -274 -131 0 0 0 7.00153lb56 513.857 -446.322 296.569 -487.43 79.2808 -528.539 0 0 0 2 lb 57 513.857 -446.322 575.52 -315.655 637.183 -184.989 0 0 0 2 lb 58 393.468 566.711 494.771 434.577 596.074 302.442 0 0 0 2 lb 59 393.468 566.711 155.625 579.925 -82.2171 593.138 0 0 0 2 lb 60 393.468 566.711 251.056 450.726 108.644 334.741 0 0 0 2 lb 61 869.153 52.8539 732.613 177.648 596.074 302.442 0 0 0 2 lb 62 869.153 52.8539 753.168 -66.0676 637.183 -184.989 0 0 0 2 lb 63 -82.2171 593.138 -91.0261 346.487 -99.8351 99.8351 0 0 0 2 lb 64 -663.61 546.157 -753.168 394.936 -842.726 243.715 0 0 0 2 lb 65 -663.61 546.157 -574.052 437.513 -484.494 328.869 0 0 0 2 lb 66 -1077.63 161.498 -960.178 202.606 -842.726 243.715 0 0 0 2 lb 67 -1077.63 161.498 -968.987 66.0674 -860.344 -29.3633 0 0 0 2 lb 68 -1177.47 -234.906 -1029.18 -381.722 -880.898 -528.539 0 0 0 2 lb 69 -1177.47 -234.906 -1018.91 -132.135 -860.344 -29.3633 0 0 0 2 lb 70 -880.898 -528.539 -744.359 -387.595 -607.82 -246.651 0 0 0 2 lb 71 -499.175 -499.175 -355.295 -475.685 -211.415 -452.194 0 0 0 2 lb 72 -499.175 -499.175 -553.498 -372.913 -607.82 -246.651 0 0 0 2 lb 73 -499.175 -499.175 -386.587 -315.087 -274 -131 0 0 0 2 lb 74 79.2808 -528.539 -66.0671 -490.366 -211.415 -452.194 0 0 0 2 lb 75 637.183 -184.989 421.363 -253.993 205.543 -322.996 0 0 0 2 lb 76 205.543 -322.996 162.966 -226.097 120.389 -129.198 0 0 0 2 lb 77 399.34 88.0898 259.865 -20.5541 120.389 -129.198 0 0 0 2 lb 78 399.34 88.0898 253.992 211.415 108.644 334.741 0 0 0 2 lb 79 -842.726 243.715 -471.281 171.775 -99.8351 99.8351 0 0 0 2 lb 80 -842.726 243.715 -558.363 56.3575 -274 -131 0 0 0 2 lb 81 -860.344 -29.3633 -734.082 -138.007 -607.82 -246.651 0 0 0 2 lb 82 -211.415 -452.194 -45.513 -290.696 120.389 -129.198 0 0 0 2 lb 83 -99.8351 99.8351 4.40445 217.288 108.644 334.741 0 0 0 2 lb 84 -99.8351 99.8351 -292.165 214.352 -484.494 328.869 0 0 0 2 lb 85 120.389 -129.198 -76.8055 -130.099 -274 -131 0 0 0 2 lb 86 86 grestore 87 87 %Nodes: 88 88 gsave 89 -274 -131 2 3.33841 0 0 nc90 -607.82 -246.651 2 3.33841 0 0 nc91 -484.494 328.869 2 3.33840 0 1 nc92 108.644 334.741 2 3.33840 0 1 nc93 120.389 -129.198 2 3.33840 0 1 nc94 -99.8351 99.8351 2 3.33841 0 0 nc95 -211.415 -452.194 2 3.33841 0 0 nc96 -860.344 -29.3633 2 3.33840 0 1 nc97 -842.726 243.715 2 3.33840 0 1 nc98 399.34 88.0898 2 3.33841 0 0 nc99 205.543 -322.996 2 3.33841 0 0 nc100 637.183 -184.989 2 3.33840 0 1 nc101 79.2808 -528.539 2 3.33840 0 1 nc102 -499.175 -499.175 2 3.33840 0 1 nc103 -880.898 -528.539 2 3.33840 0 1 nc104 -1177.47 -234.906 2 3.33841 0 0 nc105 -1077.63 161.498 2 3.33841 0 0 nc106 -663.61 546.157 2 3.33841 0 0 nc107 -82.2171 593.138 2 3.33840 0 1 nc108 596.074 302.442 2 3.33840 0 1 nc109 869.153 52.8539 2 3.33841 0 0 nc110 393.468 566.711 2 3.33841 0 0 nc111 513.857 -446.322 2 3.33841 0 0 nc89 -274 -131 20 1 0 0 nc 90 -607.82 -246.651 20 1 0 0 nc 91 -484.494 328.869 20 0 0 1 nc 92 108.644 334.741 20 0 0 1 nc 93 120.389 -129.198 20 0 0 1 nc 94 -99.8351 99.8351 20 1 0 0 nc 95 -211.415 -452.194 20 1 0 0 nc 96 -860.344 -29.3633 20 0 0 1 nc 97 -842.726 243.715 20 0 0 1 nc 98 399.34 88.0898 20 1 0 0 nc 99 205.543 -322.996 20 1 0 0 nc 100 637.183 -184.989 20 0 0 1 nc 101 79.2808 -528.539 20 0 0 1 nc 102 -499.175 -499.175 20 0 0 1 nc 103 -880.898 -528.539 20 0 0 1 nc 104 -1177.47 -234.906 20 1 0 0 nc 105 -1077.63 161.498 20 1 0 0 nc 106 -663.61 546.157 20 1 0 0 nc 107 -82.2171 593.138 20 0 0 1 nc 108 596.074 302.442 20 0 0 1 nc 109 869.153 52.8539 20 1 0 0 nc 110 393.468 566.711 20 1 0 0 nc 111 513.857 -446.322 20 1 0 0 nc 112 112 grestore 113 113 grestore -
doc/images/connected_components.eps
r1045 r587 1 1 %!PS-Adobe-2.0 EPSF-2.0 2 2 %%Creator: LEMON, graphToEps() 3 %%CreationDate: Fri Mar 8 00:18:43 20133 %%CreationDate: Fri Nov 4 13:47:12 2005 4 4 %%BoundingBox: 0 0 842 596 5 5 %%EndComments … … 54 54 %Edges: 55 55 gsave 56 574.035 177.301 622.149 225.748 670.264 274.195 0 0 0 6.25356lb57 694.579 115.483 682.421 194.839 670.264 274.195 0 0 0 6.25356lb58 280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 0 6.25356lb59 280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 0 6.25356lb60 212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 0 6.25356lb61 286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 0 6.25356lb62 286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 0 6.25356lb63 438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 0 6.25356lb64 438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 0 6.25356lb65 397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 0 6.25356lb66 366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 0 6.25356lb67 271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 0 6.25356lb68 271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 0 6.25356lb69 277.311 -252.33 241.766 -229.149 206.221 -205.967 0 0 0 6.25356lb70 -840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0 0 6.25356lb71 -579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0 6.25356lb72 -579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0 6.25356lb73 -767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0 6.25356lb74 906.312 201.403 946.592 42.798 986.873 -115.807 0 0 0 6.25356lb75 906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 0 6.25356lb76 986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 0 6.25356lb77 -470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0 0 0 6.25356lb78 422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 0 6.25356lb79 422.945 521.129 376.371 417.911 329.797 314.692 0 0 0 6.25356lb80 422.945 521.129 474.554 276.928 526.164 32.7279 0 0 0 6.25356lb81 -5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 0 6.25356lb82 329.797 314.692 130.912 317.209 -67.9734 319.727 0 0 0 6.25356lb83 -67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 0 6.25356lb84 762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 0 6.25356lb85 762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 0 6.25356lb86 526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 0 6.25356lb87 730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 0 6.25356lb88 415.393 -289.516 173.71 -318.468 -67.9734 -347.42 0 0 0 6.25356lb89 -67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 0 6.25356lb90 -67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 0 6.25356lb91 -309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 0 6.25356lb92 -323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 0 6.25356lb93 -26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 0 6.25356lb94 -26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 0 6.25356lb95 -26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 0 6.25356lb96 -26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 0 6.25356lb97 116.407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 0 6.25356lb98 -262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 0 6.25356lb99 -262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 0 6.25356lb100 -13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 0 6.25356lb101 -180.397 245.045 -1 13.509 338.465 -132.697 451.748 0 0 0 6.25356lb102 -180.397 245.045 -1 99.585 358.328 -132.697 451.748 0 0 0 6.25356lb103 -416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 0 6.25356lb104 -416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 0 6.25356lb105 -132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 0 6.25356lb106 670.264 274.195 629.188 409.347 588.113 544.499 0 0 0 6.25356lb107 670.264 274.195 797.466 341.771 924.667 409.347 0 0 0 6.25356lb108 588.113 544.499 756.39 476.923 924.667 409.347 0 0 0 6.25356lb109 -689.204 -237.261 - 587.735 -114.393 -567.302 43.6423 0 0 0 6.25356lb110 -689.204 -237.261 -6 68.771 -79.2259 -567.302 43.6423 0 0 0 6.25356lb56 574.035 177.301 622.149 225.748 670.264 274.195 0 0 0 2 lb 57 694.579 115.483 682.421 194.839 670.264 274.195 0 0 0 2 lb 58 280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 0 2 lb 59 280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 0 2 lb 60 212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 0 2 lb 61 286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 0 2 lb 62 286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 0 2 lb 63 438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 0 2 lb 64 438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 0 2 lb 65 397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 0 2 lb 66 366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 0 2 lb 67 271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 0 2 lb 68 271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 0 2 lb 69 277.311 -252.33 241.766 -229.149 206.221 -205.967 0 0 0 2 lb 70 -840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0 0 2 lb 71 -579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0 2 lb 72 -579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0 2 lb 73 -767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0 2 lb 74 906.312 201.403 946.592 42.798 986.873 -115.807 0 0 0 2 lb 75 906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 0 2 lb 76 986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 0 2 lb 77 -470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0 0 0 2 lb 78 422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 0 2 lb 79 422.945 521.129 376.371 417.911 329.797 314.692 0 0 0 2 lb 80 422.945 521.129 474.554 276.928 526.164 32.7279 0 0 0 2 lb 81 -5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 0 2 lb 82 329.797 314.692 130.912 317.209 -67.9734 319.727 0 0 0 2 lb 83 -67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 0 2 lb 84 762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 0 2 lb 85 762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 0 2 lb 86 526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 0 2 lb 87 730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 0 2 lb 88 415.393 -289.516 173.71 -318.468 -67.9734 -347.42 0 0 0 2 lb 89 -67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 0 2 lb 90 -67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 0 2 lb 91 -309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 0 2 lb 92 -323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 0 2 lb 93 -26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 0 2 lb 94 -26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 0 2 lb 95 -26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 0 2 lb 96 -26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 0 2 lb 97 116.407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 0 2 lb 98 -262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 0 2 lb 99 -262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 0 2 lb 100 -13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 0 2 lb 101 -180.397 245.045 -142.256 345.099 -132.697 451.748 0 0 0 2 lb 102 -180.397 245.045 -170.838 351.694 -132.697 451.748 0 0 0 2 lb 103 -416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 0 2 lb 104 -416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 0 2 lb 105 -132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 0 2 lb 106 670.264 274.195 629.188 409.347 588.113 544.499 0 0 0 2 lb 107 670.264 274.195 797.466 341.771 924.667 409.347 0 0 0 2 lb 108 588.113 544.499 756.39 476.923 924.667 409.347 0 0 0 2 lb 109 -689.204 -237.261 -614.799 -102.648 -567.302 43.6423 0 0 0 2 lb 110 -689.204 -237.261 -641.707 -90.9706 -567.302 43.6423 0 0 0 2 lb 111 111 grestore 112 112 %Nodes: 113 113 gsave 114 -567.302 43.6423 20 .84520 0 0 nc115 -689.204 -237.261 20 .84520 0 0 nc116 924.667 409.347 20 .84521 0 0 nc117 588.113 544.499 20 .84521 0 0 nc118 670.264 274.195 20 .84521 0 0 nc119 -371.2 568.349 20 .84520 1 0 nc120 -132.697 451.748 20 .84520 1 0 nc121 -416.25 345.746 20 .84520 1 0 nc122 -180.397 245.045 20 .84520 1 0 nc123 -13.4452 133.743 20 .84520 1 0 nc124 -262.548 107.243 20 .84520 1 0 nc125 201.208 38.3422 20 .84520 1 0 nc126 116.407 -173.66 20 .84520 1 0 nc127 -26.6953 -19.9585 20 .84520 1 0 nc128 -539.894 -262.64 20 .84520 0 1 nc129 -323.543 -433.964 20 .84520 0 1 nc130 -309.657 -57.9033 20 .84520 0 1 nc131 -67.9734 -347.42 20 .84520 0 1 nc132 415.393 -289.516 20 .84520 0 1 nc133 730.084 -307.139 20 .84520 0 1 nc134 526.164 32.7279 20 .84520 0 1 nc135 762.812 -17.6227 20 .84520 0 1 nc136 -67.9734 319.727 20 .84520 0 1 nc137 329.797 314.692 20 .84520 0 1 nc138 -5.03507 561.41 20 .84520 0 1 nc139 422.945 521.129 20 .84520 0 1 nc140 -470.779 158.605 20 .84520 0 1 nc141 986.873 -115.807 20 .84520 0 1 nc142 906.312 201.403 20 .84520 0 1 nc143 -767.847 113.289 20 .84520 0 1 nc144 -579.033 445.603 20 .84520 0 1 nc145 -840.856 -246.718 20 .84520 0 1 nc146 206.221 -205.967 20 .84521 1 0 nc147 277.311 -252.33 20 .84521 1 0 nc148 271.13 -175.058 20 .84521 1 0 nc149 366.947 -110.15 20 .84521 1 0 nc150 397.855 -196.694 20 .84521 1 0 nc151 438.037 -88.514 20 .84521 1 0 nc152 286.584 -48.3327 20 .84521 1 0 nc153 212.403 -23.6057 20 .84521 1 0 nc154 280.402 10.3938 20 .84521 1 0 nc155 694.579 115.483 20 .84521 0 0 nc156 574.035 177.301 20 .84521 0 0 nc114 -567.302 43.6423 20 0 0 0 nc 115 -689.204 -237.261 20 0 0 0 nc 116 924.667 409.347 20 1 0 0 nc 117 588.113 544.499 20 1 0 0 nc 118 670.264 274.195 20 1 0 0 nc 119 -371.2 568.349 20 0 1 0 nc 120 -132.697 451.748 20 0 1 0 nc 121 -416.25 345.746 20 0 1 0 nc 122 -180.397 245.045 20 0 1 0 nc 123 -13.4452 133.743 20 0 1 0 nc 124 -262.548 107.243 20 0 1 0 nc 125 201.208 38.3422 20 0 1 0 nc 126 116.407 -173.66 20 0 1 0 nc 127 -26.6953 -19.9585 20 0 1 0 nc 128 -539.894 -262.64 20 0 0 1 nc 129 -323.543 -433.964 20 0 0 1 nc 130 -309.657 -57.9033 20 0 0 1 nc 131 -67.9734 -347.42 20 0 0 1 nc 132 415.393 -289.516 20 0 0 1 nc 133 730.084 -307.139 20 0 0 1 nc 134 526.164 32.7279 20 0 0 1 nc 135 762.812 -17.6227 20 0 0 1 nc 136 -67.9734 319.727 20 0 0 1 nc 137 329.797 314.692 20 0 0 1 nc 138 -5.03507 561.41 20 0 0 1 nc 139 422.945 521.129 20 0 0 1 nc 140 -470.779 158.605 20 0 0 1 nc 141 986.873 -115.807 20 0 0 1 nc 142 906.312 201.403 20 0 0 1 nc 143 -767.847 113.289 20 0 0 1 nc 144 -579.033 445.603 20 0 0 1 nc 145 -840.856 -246.718 20 0 0 1 nc 146 206.221 -205.967 20 1 1 0 nc 147 277.311 -252.33 20 1 1 0 nc 148 271.13 -175.058 20 1 1 0 nc 149 366.947 -110.15 20 1 1 0 nc 150 397.855 -196.694 20 1 1 0 nc 151 438.037 -88.514 20 1 1 0 nc 152 286.584 -48.3327 20 1 1 0 nc 153 212.403 -23.6057 20 1 1 0 nc 154 280.402 10.3938 20 1 1 0 nc 155 694.579 115.483 20 1 0 0 nc 156 574.035 177.301 20 1 0 0 nc 157 157 grestore 158 158 grestore -
doc/images/edge_biconnected_components.eps
r1045 r587 1 1 %!PS-Adobe-2.0 EPSF-2.0 2 2 %%Creator: LEMON, graphToEps() 3 %%CreationDate: Fri Mar 8 00:18:43 20133 %%CreationDate: Fri Nov 4 13:47:12 2005 4 4 %%BoundingBox: 0 0 842 596 5 5 %%EndComments … … 54 54 %Edges: 55 55 gsave 56 574.035 177.301 622.149 225.748 670.264 274.195 1 0 0 6.25356lb57 694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 6.25356lb58 280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 1 6.25356lb59 280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 1 6.25356lb60 212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 1 6.25356lb61 286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 1 6.25356lb62 286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 1 6.25356lb63 438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 1 6.25356lb64 438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 1 6.25356lb65 397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 1 6.25356lb66 366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 1 6.25356lb67 271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 1 6.25356lb68 271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 1 6.25356lb69 277.311 -252.33 241.766 -229.149 206.221 -205.967 0 0 1 6.25356lb70 -840.856 -246.718 -804.351 -66.7145 -767.847 113.289 1 0 0 6.25356lb71 -579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 1 6.25356lb72 -579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 1 6.25356lb73 -767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 1 6.25356lb74 906.312 201.403 946.592 42.798 986.873 -115.807 0 0 1 6.25356lb75 906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 1 6.25356lb76 986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 1 6.25356lb77 -470.779 158.605 -390.218 50.3508 -309.657 -57.9033 1 0 0 6.25356lb78 422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 1 6.25356lb79 422.945 521.129 376.371 417.911 329.797 314.692 0 0 1 6.25356lb80 422.945 521.129 474.554 276.928 526.164 32.7279 0 0 1 6.25356lb81 -5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 1 6.25356lb82 329.797 314.692 130.912 317.209 -67.9734 319.727 0 0 1 6.25356lb83 -67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 1 6.25356lb84 762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 1 6.25356lb85 762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 1 6.25356lb86 526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 1 6.25356lb87 730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 1 6.25356lb88 415.393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0 0 6.25356lb89 -67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 1 6.25356lb90 -67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 1 6.25356lb91 -309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 1 6.25356lb92 -323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 1 6.25356lb93 -26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 1 6.25356lb94 -26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 1 6.25356lb95 -26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 1 6.25356lb96 -26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 1 6.25356lb97 116.407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 1 6.25356lb98 -262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 1 6.25356lb99 -262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 1 6.25356lb100 -13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 1 6.25356lb101 -180.397 245.045 -1 13.509 338.465 -132.697 451.748 0 0 1 6.25356lb102 -180.397 245.045 -1 99.585 358.328 -132.697 451.748 0 0 1 6.25356lb103 -416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 1 6.25356lb104 -416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 1 6.25356lb105 -132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 1 6.25356lb106 670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 6.25356lb107 670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 6.25356lb108 588.113 544.499 756.39 476.923 924.667 409.347 0 0 1 6.25356lb109 -689.204 -237.261 - 587.735 -114.393 -567.302 43.6423 0 0 1 6.25356lb110 -689.204 -237.261 -6 68.771 -79.2259 -567.302 43.6423 0 0 1 6.25356lb56 574.035 177.301 622.149 225.748 670.264 274.195 1 0 0 2 lb 57 694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 2 lb 58 280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 1 2 lb 59 280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 1 2 lb 60 212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 1 2 lb 61 286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 1 2 lb 62 286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 1 2 lb 63 438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 1 2 lb 64 438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 1 2 lb 65 397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 1 2 lb 66 366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 1 2 lb 67 271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 1 2 lb 68 271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 1 2 lb 69 277.311 -252.33 241.766 -229.149 206.221 -205.967 0 0 1 2 lb 70 -840.856 -246.718 -804.351 -66.7145 -767.847 113.289 1 0 0 2 lb 71 -579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 1 2 lb 72 -579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 1 2 lb 73 -767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 1 2 lb 74 906.312 201.403 946.592 42.798 986.873 -115.807 0 0 1 2 lb 75 906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 1 2 lb 76 986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 1 2 lb 77 -470.779 158.605 -390.218 50.3508 -309.657 -57.9033 1 0 0 2 lb 78 422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 1 2 lb 79 422.945 521.129 376.371 417.911 329.797 314.692 0 0 1 2 lb 80 422.945 521.129 474.554 276.928 526.164 32.7279 0 0 1 2 lb 81 -5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 1 2 lb 82 329.797 314.692 130.912 317.209 -67.9734 319.727 0 0 1 2 lb 83 -67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 1 2 lb 84 762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 1 2 lb 85 762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 1 2 lb 86 526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 1 2 lb 87 730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 1 2 lb 88 415.393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0 0 2 lb 89 -67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 1 2 lb 90 -67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 1 2 lb 91 -309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 1 2 lb 92 -323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 1 2 lb 93 -26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 1 2 lb 94 -26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 1 2 lb 95 -26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 1 2 lb 96 -26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 1 2 lb 97 116.407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 1 2 lb 98 -262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 1 2 lb 99 -262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 1 2 lb 100 -13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 1 2 lb 101 -180.397 245.045 -142.256 345.099 -132.697 451.748 0 0 1 2 lb 102 -180.397 245.045 -170.838 351.694 -132.697 451.748 0 0 1 2 lb 103 -416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 1 2 lb 104 -416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 1 2 lb 105 -132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 1 2 lb 106 670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 2 lb 107 670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 2 lb 108 588.113 544.499 756.39 476.923 924.667 409.347 0 0 1 2 lb 109 -689.204 -237.261 -614.799 -102.648 -567.302 43.6423 0 0 1 2 lb 110 -689.204 -237.261 -641.707 -90.9706 -567.302 43.6423 0 0 1 2 lb 111 111 grestore 112 112 %Nodes: 113 113 gsave 114 -567.302 43.6423 20 .84520 0 0 nc115 -689.204 -237.261 20 .84520 0 0 nc116 924.667 409.347 20 .84520 0 1 nc117 588.113 544.499 20 .84520 0 1 nc118 670.264 274.195 20 .84520 0 1 nc119 -371.2 568.349 20 .84521 1 0 nc120 -132.697 451.748 20 .84521 1 0 nc121 -416.25 345.746 20 .84521 1 0 nc122 -180.397 245.045 20 .84521 1 0 nc123 -13.4452 133.743 20 .84521 1 0 nc124 -262.548 107.243 20 .84521 1 0 nc125 201.208 38.3422 20 .84521 1 0 nc126 116.407 -173.66 20 .84521 1 0 nc127 -26.6953 -19.9585 20 .84521 1 0 nc128 -539.894 -262.64 20 .84520 0.5 0 nc129 -323.543 -433.964 20 .84520 0.5 0 nc130 -309.657 -57.9033 20 .84520 0.5 0 nc131 -67.9734 -347.42 20 .84520 0.5 0 nc132 415.393 -289.516 20 .84520.5 0 0 nc133 730.084 -307.139 20 .84520.5 0 0 nc134 526.164 32.7279 20 .84520.5 0 0 nc135 762.812 -17.6227 20 .84520.5 0 0 nc136 -67.9734 319.727 20 .84520.5 0 0 nc137 329.797 314.692 20 .84520.5 0 0 nc138 -5.03507 561.41 20 .84520.5 0 0 nc139 422.945 521.129 20 .84520.5 0 0 nc140 -470.779 158.605 20 .84520 1 1 nc141 986.873 -115.807 20 .84520.5 0 0 nc142 906.312 201.403 20 .84520.5 0 0 nc143 -767.847 113.289 20 .84520 1 1 nc144 -579.033 445.603 20 .84520 1 1 nc145 -840.856 -246.718 20 .84521 0 1 nc146 206.221 -205.967 20 .84520 0 0.5 nc147 277.311 -252.33 20 .84520 0 0.5 nc148 271.13 -175.058 20 .84520 0 0.5 nc149 366.947 -110.15 20 .84520 0 0.5 nc150 397.855 -196.694 20 .84520 0 0.5 nc151 438.037 -88.514 20 .84520 0 0.5 nc152 286.584 -48.3327 20 .84520 0 0.5 nc153 212.403 -23.6057 20 .84520 0 0.5 nc154 280.402 10.3938 20 .84520 0 0.5 nc155 694.579 115.483 20 .84521 0 0 nc156 574.035 177.301 20 .84520 1 0 nc114 -567.302 43.6423 20 0 0 0 nc 115 -689.204 -237.261 20 0 0 0 nc 116 924.667 409.347 20 0 0 1 nc 117 588.113 544.499 20 0 0 1 nc 118 670.264 274.195 20 0 0 1 nc 119 -371.2 568.349 20 1 1 0 nc 120 -132.697 451.748 20 1 1 0 nc 121 -416.25 345.746 20 1 1 0 nc 122 -180.397 245.045 20 1 1 0 nc 123 -13.4452 133.743 20 1 1 0 nc 124 -262.548 107.243 20 1 1 0 nc 125 201.208 38.3422 20 1 1 0 nc 126 116.407 -173.66 20 1 1 0 nc 127 -26.6953 -19.9585 20 1 1 0 nc 128 -539.894 -262.64 20 0 0.5 0 nc 129 -323.543 -433.964 20 0 0.5 0 nc 130 -309.657 -57.9033 20 0 0.5 0 nc 131 -67.9734 -347.42 20 0 0.5 0 nc 132 415.393 -289.516 20 0.5 0 0 nc 133 730.084 -307.139 20 0.5 0 0 nc 134 526.164 32.7279 20 0.5 0 0 nc 135 762.812 -17.6227 20 0.5 0 0 nc 136 -67.9734 319.727 20 0.5 0 0 nc 137 329.797 314.692 20 0.5 0 0 nc 138 -5.03507 561.41 20 0.5 0 0 nc 139 422.945 521.129 20 0.5 0 0 nc 140 -470.779 158.605 20 0 1 1 nc 141 986.873 -115.807 20 0.5 0 0 nc 142 906.312 201.403 20 0.5 0 0 nc 143 -767.847 113.289 20 0 1 1 nc 144 -579.033 445.603 20 0 1 1 nc 145 -840.856 -246.718 20 1 0 1 nc 146 206.221 -205.967 20 0 0 0.5 nc 147 277.311 -252.33 20 0 0 0.5 nc 148 271.13 -175.058 20 0 0 0.5 nc 149 366.947 -110.15 20 0 0 0.5 nc 150 397.855 -196.694 20 0 0 0.5 nc 151 438.037 -88.514 20 0 0 0.5 nc 152 286.584 -48.3327 20 0 0 0.5 nc 153 212.403 -23.6057 20 0 0 0.5 nc 154 280.402 10.3938 20 0 0 0.5 nc 155 694.579 115.483 20 1 0 0 nc 156 574.035 177.301 20 0 1 0 nc 157 157 grestore 158 158 grestore -
doc/images/node_biconnected_components.eps
r1045 r587 1 1 %!PS-Adobe-2.0 EPSF-2.0 2 2 %%Creator: LEMON, graphToEps() 3 %%CreationDate: Fri Mar 8 00:18:43 20133 %%CreationDate: Fri Nov 4 13:47:12 2005 4 4 %%BoundingBox: 0 0 842 596 5 5 %%EndComments … … 54 54 %Edges: 55 55 gsave 56 574.035 177.301 622.149 225.748 670.264 274.195 0 1 0 6.25356lb57 694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 6.25356lb58 280.402 10.3938 246.402 -6.60595 212.403 -23.6057 1 1 0.5 6.25356lb59 280.402 10.3938 283.493 -18.9695 286.584 -48.3327 1 1 0.5 6.25356lb60 212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 1 1 0.5 6.25356lb61 286.584 -48.3327 326.765 -79.2414 366.947 -110.15 1 0.5 1 6.25356lb62 286.584 -48.3327 278.857 -111.695 271.13 -175.058 1 0.5 1 6.25356lb63 438.037 -88.514 417.946 -142.604 397.855 -196.694 0.5 0.5 1 6.25356lb64 438.037 -88.514 402.492 -99.332 366.947 -110.15 0.5 0.5 1 6.25356lb65 397.855 -196.694 382.401 -153.422 366.947 -110.15 0.5 0.5 1 6.25356lb66 366.947 -110.15 319.038 -142.604 271.13 -175.058 1 0.5 1 6.25356lb67 271.13 -175.058 274.221 -213.694 277.311 -252.33 0.5 1 1 6.25356lb68 271.13 -175.058 238.675 -190.512 206.221 -205.967 0.5 1 1 6.25356lb69 277.311 -252.33 241.766 -229.149 206.221 -205.967 0.5 1 1 6.25356lb70 -840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0.5 0 6.25356lb71 -579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0.5 6.25356lb72 -579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0.5 6.25356lb73 -767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0.5 6.25356lb74 906.312 201.403 946.592 42.798 986.873 -115.807 0 0.5 0.5 6.25356lb75 906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0.5 0.5 6.25356lb76 986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0.5 0.5 6.25356lb77 -470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0.5 0.5 0 6.25356lb78 422.945 521.129 208.955 541.269 -5.03507 561.41 0.5 0 0.5 6.25356lb79 422.945 521.129 376.371 417.911 329.797 314.692 0.5 0 0.5 6.25356lb80 422.945 521.129 474.554 276.928 526.164 32.7279 0.5 0 0.5 6.25356lb81 -5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0.5 0 0.5 6.25356lb82 329.797 314.692 130.912 317.209 -67.9734 319.727 0.5 0 0.5 6.25356lb83 -67.9734 319.727 229.095 176.227 526.164 32.7279 0.5 0 0.5 6.25356lb84 762.812 -17.6227 644.488 7.5526 526.164 32.7279 0.5 0.5 0.5 6.25356lb85 762.812 -17.6227 746.448 -162.381 730.084 -307.139 0.5 0.5 0.5 6.25356lb86 526.164 32.7279 470.779 -128.394 415.393 -289.516 0.5 0.5 0.5 6.25356lb87 730.084 -307.139 572.738 -298.327 415.393 -289.516 0.5 0.5 0.5 6.25356lb88 415.393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0.5 0.5 6.25356lb89 -67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0.5 1 0.5 6.25356lb90 -67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0.5 1 0.5 6.25356lb91 -309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0.5 1 0.5 6.25356lb92 -323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0.5 1 0.5 6.25356lb93 -26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 1 1 0 6.25356lb94 -26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 1 1 0 6.25356lb95 -26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 1 0 1 6.25356lb96 -26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 1 0 1 6.25356lb97 116.407 -173.66 158.808 -67.6589 201.208 38.3422 1 1 0 6.25356lb98 -262.548 107.243 -137.997 120.493 -13.4452 133.743 1 0 1 6.25356lb99 -262.548 107.243 -221.472 176.144 -180.397 245.045 1 0 1 6.25356lb100 -13.4452 133.743 -96.9211 189.394 -180.397 245.045 1 0 1 6.25356lb101 -180.397 245.045 -1 13.509 338.465 -132.697 451.748 0 1 1 6.25356lb102 -180.397 245.045 -1 99.585 358.328 -132.697 451.748 0 1 1 6.25356lb103 -416.25 345.746 -274.474 398.747 -132.697 451.748 0.5 0 0 6.25356lb104 -416.25 345.746 -393.725 457.048 -371.2 568.349 0.5 0 0 6.25356lb105 -132.697 451.748 -251.948 510.048 -371.2 568.349 0.5 0 0 6.25356lb106 670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 6.25356lb107 670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 6.25356lb108 588.113 544.499 756.39 476.923 924.667 409.347 0 0 1 6.25356lb109 -689.204 -237.261 - 587.735 -114.393 -567.302 43.6423 0 0 0 6.25356lb110 -689.204 -237.261 -6 68.771 -79.2259 -567.302 43.6423 0 0 0 6.25356lb56 574.035 177.301 622.149 225.748 670.264 274.195 0 1 0 5 lb 57 694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 5 lb 58 280.402 10.3938 246.402 -6.60595 212.403 -23.6057 1 1 0.5 5 lb 59 280.402 10.3938 283.493 -18.9695 286.584 -48.3327 1 1 0.5 5 lb 60 212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 1 1 0.5 5 lb 61 286.584 -48.3327 326.765 -79.2414 366.947 -110.15 1 0.5 1 5 lb 62 286.584 -48.3327 278.857 -111.695 271.13 -175.058 1 0.5 1 5 lb 63 438.037 -88.514 417.946 -142.604 397.855 -196.694 0.5 0.5 1 5 lb 64 438.037 -88.514 402.492 -99.332 366.947 -110.15 0.5 0.5 1 5 lb 65 397.855 -196.694 382.401 -153.422 366.947 -110.15 0.5 0.5 1 5 lb 66 366.947 -110.15 319.038 -142.604 271.13 -175.058 1 0.5 1 5 lb 67 271.13 -175.058 274.221 -213.694 277.311 -252.33 0.5 1 1 5 lb 68 271.13 -175.058 238.675 -190.512 206.221 -205.967 0.5 1 1 5 lb 69 277.311 -252.33 241.766 -229.149 206.221 -205.967 0.5 1 1 5 lb 70 -840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0.5 0 5 lb 71 -579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0.5 5 lb 72 -579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0.5 5 lb 73 -767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0.5 5 lb 74 906.312 201.403 946.592 42.798 986.873 -115.807 0 0.5 0.5 5 lb 75 906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0.5 0.5 5 lb 76 986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0.5 0.5 5 lb 77 -470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0.5 0.5 0 5 lb 78 422.945 521.129 208.955 541.269 -5.03507 561.41 0.5 0 0.5 5 lb 79 422.945 521.129 376.371 417.911 329.797 314.692 0.5 0 0.5 5 lb 80 422.945 521.129 474.554 276.928 526.164 32.7279 0.5 0 0.5 5 lb 81 -5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0.5 0 0.5 5 lb 82 329.797 314.692 130.912 317.209 -67.9734 319.727 0.5 0 0.5 5 lb 83 -67.9734 319.727 229.095 176.227 526.164 32.7279 0.5 0 0.5 5 lb 84 762.812 -17.6227 644.488 7.5526 526.164 32.7279 0.5 0.5 0.5 5 lb 85 762.812 -17.6227 746.448 -162.381 730.084 -307.139 0.5 0.5 0.5 5 lb 86 526.164 32.7279 470.779 -128.394 415.393 -289.516 0.5 0.5 0.5 5 lb 87 730.084 -307.139 572.738 -298.327 415.393 -289.516 0.5 0.5 0.5 5 lb 88 415.393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0.5 0.5 5 lb 89 -67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0.5 1 0.5 5 lb 90 -67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0.5 1 0.5 5 lb 91 -309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0.5 1 0.5 5 lb 92 -323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0.5 1 0.5 5 lb 93 -26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 1 1 0 5 lb 94 -26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 1 1 0 5 lb 95 -26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 1 0 1 5 lb 96 -26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 1 0 1 5 lb 97 116.407 -173.66 158.808 -67.6589 201.208 38.3422 1 1 0 5 lb 98 -262.548 107.243 -137.997 120.493 -13.4452 133.743 1 0 1 5 lb 99 -262.548 107.243 -221.472 176.144 -180.397 245.045 1 0 1 5 lb 100 -13.4452 133.743 -96.9211 189.394 -180.397 245.045 1 0 1 5 lb 101 -180.397 245.045 -140.307 344.649 -132.697 451.748 0 1 1 5 lb 102 -180.397 245.045 -172.787 352.144 -132.697 451.748 0 1 1 5 lb 103 -416.25 345.746 -274.474 398.747 -132.697 451.748 0.5 0 0 5 lb 104 -416.25 345.746 -393.725 457.048 -371.2 568.349 0.5 0 0 5 lb 105 -132.697 451.748 -251.948 510.048 -371.2 568.349 0.5 0 0 5 lb 106 670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 5 lb 107 670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 5 lb 108 588.113 544.499 756.39 476.923 924.667 409.347 0 0 1 5 lb 109 -689.204 -237.261 -612.964 -103.444 -567.302 43.6423 0 0 0 5 lb 110 -689.204 -237.261 -643.542 -90.1744 -567.302 43.6423 0 0 0 5 lb 111 111 grestore 112 112 %Nodes: 113 113 gsave 114 -567.302 43.6423 20 .84520 0 1 nc115 -689.204 -237.261 20 .84520 0 1 nc116 924.667 409.347 20 .84520 0 1 nc117 588.113 544.499 20 .84520 0 1 nc118 670.264 274.195 20 .84521 0 0 nc119 -371.2 568.349 20 .84520 0 1 nc120 -132.697 451.748 20 .84521 0 0 nc121 -416.25 345.746 20 .84520 0 1 nc122 -180.397 245.045 20 .84521 0 0 nc123 -13.4452 133.743 20 .84520 0 1 nc124 -262.548 107.243 20 .84520 0 1 nc125 201.208 38.3422 20 .84520 0 1 nc126 116.407 -173.66 20 .84520 0 1 nc127 -26.6953 -19.9585 20 .84521 0 0 nc128 -539.894 -262.64 20 .84520 0 1 nc129 -323.543 -433.964 20 .84520 0 1 nc130 -309.657 -57.9033 20 .84521 0 0 nc131 -67.9734 -347.42 20 .84521 0 0 nc132 415.393 -289.516 20 .84521 0 0 nc133 730.084 -307.139 20 .84520 0 1 nc134 526.164 32.7279 20 .84521 0 0 nc135 762.812 -17.6227 20 .84521 0 0 nc136 -67.9734 319.727 20 .84520 0 1 nc137 329.797 314.692 20 .84520 0 1 nc138 -5.03507 561.41 20 .84520 0 1 nc139 422.945 521.129 20 .84520 0 1 nc140 -470.779 158.605 20 .84521 0 0 nc141 986.873 -115.807 20 .84520 0 1 nc142 906.312 201.403 20 .84520 0 1 nc143 -767.847 113.289 20 .84521 0 0 nc144 -579.033 445.603 20 .84520 0 1 nc145 -840.856 -246.718 20 .84520 0 1 nc146 206.221 -205.967 20 .84520 0 1 nc147 277.311 -252.33 20 .84520 0 1 nc148 271.13 -175.058 20 .84521 0 0 nc149 366.947 -110.15 20 .84521 0 0 nc150 397.855 -196.694 20 .84520 0 1 nc151 438.037 -88.514 20 .84520 0 1 nc152 286.584 -48.3327 20 .84521 0 0 nc153 212.403 -23.6057 20 .84520 0 1 nc154 280.402 10.3938 20 .84520 0 1 nc155 694.579 115.483 20 .84520 0 1 nc156 574.035 177.301 20 .84520 0 1 nc114 -567.302 43.6423 20 0 0 1 nc 115 -689.204 -237.261 20 0 0 1 nc 116 924.667 409.347 20 0 0 1 nc 117 588.113 544.499 20 0 0 1 nc 118 670.264 274.195 20 1 0 0 nc 119 -371.2 568.349 20 0 0 1 nc 120 -132.697 451.748 20 1 0 0 nc 121 -416.25 345.746 20 0 0 1 nc 122 -180.397 245.045 20 1 0 0 nc 123 -13.4452 133.743 20 0 0 1 nc 124 -262.548 107.243 20 0 0 1 nc 125 201.208 38.3422 20 0 0 1 nc 126 116.407 -173.66 20 0 0 1 nc 127 -26.6953 -19.9585 20 1 0 0 nc 128 -539.894 -262.64 20 0 0 1 nc 129 -323.543 -433.964 20 0 0 1 nc 130 -309.657 -57.9033 20 1 0 0 nc 131 -67.9734 -347.42 20 1 0 0 nc 132 415.393 -289.516 20 1 0 0 nc 133 730.084 -307.139 20 0 0 1 nc 134 526.164 32.7279 20 1 0 0 nc 135 762.812 -17.6227 20 1 0 0 nc 136 -67.9734 319.727 20 0 0 1 nc 137 329.797 314.692 20 0 0 1 nc 138 -5.03507 561.41 20 0 0 1 nc 139 422.945 521.129 20 0 0 1 nc 140 -470.779 158.605 20 1 0 0 nc 141 986.873 -115.807 20 0 0 1 nc 142 906.312 201.403 20 0 0 1 nc 143 -767.847 113.289 20 1 0 0 nc 144 -579.033 445.603 20 0 0 1 nc 145 -840.856 -246.718 20 0 0 1 nc 146 206.221 -205.967 20 0 0 1 nc 147 277.311 -252.33 20 0 0 1 nc 148 271.13 -175.058 20 1 0 0 nc 149 366.947 -110.15 20 1 0 0 nc 150 397.855 -196.694 20 0 0 1 nc 151 438.037 -88.514 20 0 0 1 nc 152 286.584 -48.3327 20 1 0 0 nc 153 212.403 -23.6057 20 0 0 1 nc 154 280.402 10.3938 20 0 0 1 nc 155 694.579 115.483 20 0 0 1 nc 156 574.035 177.301 20 0 0 1 nc 157 157 grestore 158 158 grestore -
doc/images/strongly_connected_components.eps
r1045 r587 1 1 %!PS-Adobe-2.0 EPSF-2.0 2 2 %%Creator: LEMON, graphToEps() 3 %%CreationDate: Fri Mar 8 00:22:15 20133 %%CreationDate: Fri Nov 4 13:47:12 2005 4 4 %%BoundingBox: 0 0 842 596 5 5 %%EndComments … … 54 54 %Edges: 55 55 gsave 56 4.56973setlinewidth 0 0 1 setrgbcolor newpath56 2 setlinewidth 0 0 1 setrgbcolor newpath 57 57 218.178 27.2723 moveto 58 19 5.849 -31.0725 190.033 -46.2697 176.306 -82.1369curveto stroke59 newpath 16 3.235 -116.291 moveto 165.206 -77.8889 lineto 187.405 -86.3849lineto closepath fill60 4.56973setlinewidth 0 0 1 setrgbcolor newpath58 192.373 -40.1551 188.622 -49.9556 169.228 -100.631 curveto stroke 59 newpath 164.939 -111.838 moveto 165.492 -99.2013 lineto 172.964 -102.061 lineto closepath fill 60 2 setlinewidth 0 0 1 setrgbcolor newpath 61 61 44.8044 15.5841 moveto 62 1 09.705 19.9594 126.016 21.0591 166.493 23.7879 curveto stroke63 newpath 202.98 26.2477 moveto 167.292 11.9299 lineto 165.694 35.6458 lineto closepath fill64 4.56973setlinewidth 1 0 0 setrgbcolor newpath62 119.293 20.6059 129.775 21.3125 186.25 25.1199 curveto stroke 63 newpath 198.223 25.927 moveto 186.519 21.1289 lineto 185.981 29.1108 lineto closepath fill 64 2 setlinewidth 1 0 0 setrgbcolor newpath 65 65 218.178 27.2723 moveto 66 28 1.264 -80.3935 289.87 -95.0808 338.092 -177.379curveto stroke67 newpath 35 6.579 -208.932 moveto 327.837 -183.388 lineto 348.346 -171.371lineto closepath fill68 4.56973setlinewidth 0 0 1 setrgbcolor newpath66 285.395 -87.4449 290.763 -96.6058 348.102 -194.464 curveto stroke 67 newpath 354.169 -204.818 moveto 344.651 -196.487 lineto 351.554 -192.442 lineto closepath fill 68 2 setlinewidth 0 0 1 setrgbcolor newpath 69 69 157.79 -130.517 moveto 70 1 14.446 -74.4692 104.358 -61.4239 76.4943 -25.394 curveto stroke71 newpath 5 4.1228 3.53455 moveto 85.8959 -18.1234 lineto 67.0928 -32.6646lineto closepath fill72 4.56973setlinewidth 1 0 0 setrgbcolor newpath70 108.71 -67.0521 102.27 -58.7243 64.3804 -9.72954 curveto stroke 71 newpath 57.0394 -0.236898 moveto 67.5446 -7.28254 lineto 61.2162 -12.1765 lineto closepath fill 72 2 setlinewidth 1 0 0 setrgbcolor newpath 73 73 -105.193 -261.035 moveto 74 -3 9.4801 -139.85 -31.344 -124.846 20.1113 -29.9539curveto stroke75 newpath 3 7.5434 2.19358 moveto 30.559 -35.6192 lineto 9.66361 -24.2886lineto closepath fill76 4.56973setlinewidth 0 0 1 setrgbcolor newpath74 -35.6576 -132.801 -30.5923 -123.459 29.5506 -12.5464 curveto stroke 75 newpath 35.2708 -1.99743 moveto 33.0669 -14.4531 lineto 26.0343 -10.6397 lineto closepath fill 76 2 setlinewidth 0 0 1 setrgbcolor newpath 77 77 -465.576 -42.8564 moveto 78 -55 0.335 -27.1603 -566.8 -24.1113 -625.027 -13.3286 curveto stroke79 newpath -6 60.985 -6.66971 moveto -622.863 -1.64245 lineto -627.191 -25.0148lineto closepath fill80 4.56973setlinewidth 0 0 1 setrgbcolor newpath78 -559.078 -25.5413 -569.47 -23.6169 -644.498 -9.72286 curveto stroke 79 newpath -656.297 -7.5378 moveto -643.77 -5.78973 lineto -645.226 -13.656 lineto closepath fill 80 2 setlinewidth 0 0 1 setrgbcolor newpath 81 81 -574.666 -153.893 moveto 82 -5 35.911 -114.447 -524.692 -103.027 -501.88 -79.8085curveto stroke83 newpath -47 6.251 -53.7222 moveto -493.402 -88.1377 lineto -510.358 -71.4793lineto closepath fill84 4.56973setlinewidth 1 0 0 setrgbcolor newpath82 -528.842 -107.252 -521.515 -99.794 -488.002 -65.683 curveto stroke 83 newpath -479.592 -57.123 moveto -485.149 -68.4863 lineto -490.856 -62.8797 lineto closepath fill 84 2 setlinewidth 1 0 0 setrgbcolor newpath 85 85 -490.901 120.777 moveto 86 -48 1.623 60.8277 -479.143 44.8049 -473.499 8.33636curveto stroke87 newpath -46 7.906 -27.8032 moveto -485.244 6.51862 lineto -461.754 10.1541lineto closepath fill88 4.56973setlinewidth 0 0 1 setrgbcolor newpath86 -480.122 51.1328 -478.519 40.7713 -470.47 -11.2329 curveto stroke 87 newpath -468.635 -23.0917 moveto -474.423 -11.8447 lineto -466.517 -10.6212 lineto closepath fill 88 2 setlinewidth 0 0 1 setrgbcolor newpath 89 89 -675.963 -3.89604 moveto 90 -63 7.405 -60.9909 -628.201 -74.6206 -603.658 -110.963curveto stroke91 newpath -58 3.191 -141.27 moveto -613.507 -117.615 lineto -593.808 -104.312lineto closepath fill92 4.56973setlinewidth 0 0 1 setrgbcolor newpath90 -632.116 -68.8235 -626.228 -77.5422 -592.575 -127.374 curveto stroke 91 newpath -585.859 -137.319 moveto -595.89 -129.612 lineto -589.26 -125.135 lineto closepath fill 92 2 setlinewidth 0 0 1 setrgbcolor newpath 93 93 -490.901 120.777 moveto 94 -43 9.75 208.465 -431.238 223.057 -394.278 286.417curveto stroke95 newpath -37 5.851 318.006 moveto -384.012 280.429 lineto -404.543 292.406lineto closepath fill96 4.56973setlinewidth 0 0 1 setrgbcolor newpath94 -435.445 215.844 -430.107 224.995 -384.3 303.522 curveto stroke 95 newpath -378.253 313.887 moveto -380.845 301.507 lineto -387.755 305.537 lineto closepath fill 96 2 setlinewidth 0 0 1 setrgbcolor newpath 97 97 -266.879 114.933 moveto 98 -3 58.311 117.318 -375.109 117.756 -439.117 119.426curveto stroke99 newpath -47 5.674 120.38 moveto -438.807 131.307 lineto -439.426 107.545lineto closepath fill100 4.56973setlinewidth 0 0 1 setrgbcolor newpath98 -367.067 117.547 -377.642 117.822 -458.912 119.943 curveto stroke 99 newpath -470.908 120.255 moveto -458.807 123.941 lineto -459.016 115.944 lineto closepath fill 100 2 setlinewidth 0 0 1 setrgbcolor newpath 101 101 -368.176 331.163 moveto 102 -32 6.156 241.466 -318.997 226.186 -288.855 161.843curveto stroke103 newpath -27 3.341 128.727 moveto -299.617 156.801 lineto -278.092 166.885lineto closepath fill104 4.56973setlinewidth 1 0 0 setrgbcolor newpath102 -322.511 233.685 -318.018 224.095 -280.454 143.911 curveto stroke 103 newpath -275.364 133.044 moveto -284.076 142.214 lineto -276.832 145.608 lineto closepath fill 104 2 setlinewidth 1 0 0 setrgbcolor newpath 105 105 -266.879 114.933 moveto 106 -22 6.764 227.755 -221.069 243.774 -190.728 329.107curveto stroke107 newpath -1 78.477 363.564 moveto -179.53 325.126 lineto -201.926 333.089lineto closepath fill108 4.56973setlinewidth 0 0 1 setrgbcolor newpath106 -224.004 235.52 -220.448 245.52 -184.094 347.765 curveto stroke 107 newpath -180.074 359.072 moveto -180.325 346.425 lineto -187.863 349.105 lineto closepath fill 108 2 setlinewidth 0 0 1 setrgbcolor newpath 109 109 -251.294 -335.059 moveto 110 -1 98.044 -308.079 -183.61 -300.766 -151.402 -284.448 curveto stroke111 newpath -1 18.781 -267.92 moveto -146.031 -295.049 lineto -156.774 -273.846lineto closepath fill112 4.56973setlinewidth 0 0 1 setrgbcolor newpath110 -189.25 -303.624 -179.902 -298.887 -133.738 -275.498 curveto stroke 111 newpath -123.034 -270.074 moveto -131.93 -279.066 lineto -135.546 -271.93 lineto closepath fill 112 2 setlinewidth 0 0 1 setrgbcolor newpath 113 113 -389.604 -136.361 moveto 114 -3 32.039 -219.059 -322.392 -232.919 -280.889 -292.543curveto stroke115 newpath -2 59.996 -322.557 moveto -290.643 -299.333 lineto -271.134 -285.753lineto closepath fill116 4.56973setlinewidth 1 0 0 setrgbcolor newpath114 -327.15 -226.083 -321.098 -234.777 -269.576 -308.795 curveto stroke 115 newpath -262.72 -318.644 moveto -272.859 -311.081 lineto -266.293 -306.51 lineto closepath fill 116 2 setlinewidth 1 0 0 setrgbcolor newpath 117 117 5.84406 175.322 moveto 118 -7 0.5724 261.706 -81.8227 274.423 -139.051 339.116curveto stroke119 newpath -16 3.281 366.507 moveto -130.149 346.991 lineto -147.953 331.242lineto closepath fill120 4.56973setlinewidth 0 0 1 setrgbcolor newpath118 -76.0754 267.926 -83.1051 275.873 -152.172 353.948 curveto stroke 119 newpath -160.122 362.936 moveto -149.176 356.598 lineto -155.168 351.298 lineto closepath fill 120 2 setlinewidth 0 0 1 setrgbcolor newpath 121 121 169.478 311.683 moveto 122 103.641 256.819 90.7821 246.103 45.6398 208.485curveto stroke123 newpath 17.546 185.074 moveto 38.0313 217.615 lineto 53.2483 199.355 lineto closepath fill124 4.56973setlinewidth 0 0 1 setrgbcolor newpath122 96.8003 251.119 88.6819 244.353 30.4273 195.808 curveto stroke 123 newpath 21.2086 188.126 moveto 27.8666 198.881 lineto 32.988 192.735 lineto closepath fill 124 2 setlinewidth 0 0 1 setrgbcolor newpath 125 125 342.851 111.037 moveto 126 26 9.224 196.246 258.132 209.083 203.347 272.486curveto stroke127 newpath 1 79.437 300.157 moveto 212.34 280.257 lineto 194.354 264.716lineto closepath fill128 4.56973setlinewidth 0 0 1 setrgbcolor newpath126 263.766 202.563 256.831 210.589 190.4 287.47 curveto stroke 127 newpath 182.554 296.55 moveto 193.427 290.085 lineto 187.373 284.855 lineto closepath fill 128 2 setlinewidth 0 0 1 setrgbcolor newpath 129 129 5.84406 175.322 moveto 130 1 55.419 146.79 172.221 143.585 291.966 120.743 curveto stroke131 newpath 32 7.888 113.891 moveto 289.739 109.069 lineto 294.193 132.418lineto closepath fill132 4.56973setlinewidth 0 0 1 setrgbcolor newpath130 163.16 145.314 173.605 143.321 311.418 117.033 curveto stroke 131 newpath 323.205 114.784 moveto 310.668 113.104 lineto 312.167 120.962 lineto closepath fill 132 2 setlinewidth 0 0 1 setrgbcolor newpath 133 133 342.851 111.037 moveto 134 49 0.978 6.99574 505.015 -2.86383 627.727 -89.0547curveto stroke135 newpath 65 7.653 -110.074 moveto 620.896 -98.7802 lineto 634.558 -79.3291lineto closepath fill136 4.56973setlinewidth 0 0 1 setrgbcolor newpath134 497.255 2.58683 505.964 -3.53033 643.932 -100.436 curveto stroke 135 newpath 653.752 -107.334 moveto 641.633 -103.71 lineto 646.231 -97.163 lineto closepath fill 136 2 setlinewidth 0 0 1 setrgbcolor newpath 137 137 364.28 -222.074 moveto 138 354. 807 -74.8128 353.709 -57.7536 346.177 59.3416curveto stroke139 newpath 34 3.829 95.836 moveto 358.037 60.1045 lineto 334.316 58.5786lineto closepath fill140 4.56973setlinewidth 0 0 1 setrgbcolor newpath138 354.298 -66.9063 353.616 -56.2971 344.905 79.1029 curveto stroke 139 newpath 344.135 91.0781 moveto 348.897 79.3597 lineto 340.914 78.8461 lineto closepath fill 140 2 setlinewidth 0 0 1 setrgbcolor newpath 141 141 670.118 -118.829 moveto 142 5 35.595 -164.241 519.412 -169.704 413.361 -205.505curveto stroke143 newpath 3 78.712 -217.202 moveto 409.559 -194.245 lineto 417.162 -216.766lineto closepath fill144 4.56973setlinewidth 1 0 0 setrgbcolor newpath142 528.037 -166.793 517.967 -170.192 394.599 -211.839 curveto stroke 143 newpath 383.229 -215.677 moveto 393.32 -208.049 lineto 395.878 -215.629 lineto closepath fill 144 2 setlinewidth 1 0 0 setrgbcolor newpath 145 145 -105.193 -261.035 moveto 146 11 0.939 -243.099 128.069 -241.677 312.655 -226.358curveto stroke147 newpath 34 9.1 -223.334 moveto 313.638 -238.202 lineto 311.672 -214.514 lineto closepath fill148 4.56973setlinewidth 0 0 1 setrgbcolor newpath146 118.401 -242.479 129.015 -241.598 332.39 -224.721 curveto stroke 147 newpath 344.348 -223.728 moveto 332.72 -228.707 lineto 332.059 -220.734 lineto closepath fill 148 2 setlinewidth 0 0 1 setrgbcolor newpath 149 149 -105.193 -261.035 moveto 150 -1 56.746 -168.566 -164.987 -153.784 -202.693 -86.1539curveto stroke151 newpath -2 20.5 -54.2129 moveto -192.312 -80.3665 lineto -213.073 -91.9413lineto closepath fill152 4.56973setlinewidth 0 0 1 setrgbcolor newpath150 -160.867 -161.176 -166.028 -151.918 -212.336 -68.858 curveto stroke 151 newpath -218.179 -58.3769 moveto -208.842 -66.9102 lineto -215.829 -70.8058 lineto closepath fill 152 2 setlinewidth 0 0 1 setrgbcolor newpath 153 153 -227.918 -40.9084 moveto 154 -29 0.327 -77.7521 -304.558 -86.1532 -344.995 -110.026curveto stroke155 newpath -37 6.487 -128.617 moveto -351.037 -99.7914 lineto -338.953 -120.26lineto closepath fill154 -298.35 -82.4884 -307.42 -87.8432 -362.048 -120.093 curveto stroke 155 newpath -372.381 -126.193 moveto -364.081 -116.648 lineto -360.014 -123.537 lineto closepath fill 156 156 grestore 157 157 %Nodes: 158 158 gsave 159 -389.604 -136.361 15.23240 1 0 nc160 -227.918 -40.9084 15.23240 1 0 nc161 -105.193 -261.035 15.23240 1 0 nc162 364.28 -222.074 15.23241 1 0 nc163 670.118 -118.829 15.23241 1 0 nc164 342.851 111.037 15.23241 1 0 nc165 5.84406 175.322 15.23241 1 0 nc166 169.478 311.683 15.23241 1 0 nc167 -173.374 377.916 15.23241 0 1 nc168 -251.294 -335.059 15.23240 1 0 nc169 -266.879 114.933 15.23240 0 0 nc170 -368.176 331.163 15.23240 0 0 nc171 -490.901 120.777 15.23240 0 0 nc172 -574.666 -153.893 15.23241 0 0 nc173 -675.963 -3.89604 15.23241 0 0 nc174 -465.576 -42.8564 15.23241 0 0 nc175 44.8044 15.5841 15.23240 0 1 nc176 157.79 -130.517 15.23240 0 1 nc177 218.178 27.2723 15.23240 0 1 nc159 -389.604 -136.361 20 0 1 0 nc 160 -227.918 -40.9084 20 0 1 0 nc 161 -105.193 -261.035 20 0 1 0 nc 162 364.28 -222.074 20 1 1 0 nc 163 670.118 -118.829 20 1 1 0 nc 164 342.851 111.037 20 1 1 0 nc 165 5.84406 175.322 20 1 1 0 nc 166 169.478 311.683 20 1 1 0 nc 167 -173.374 377.916 20 1 0 1 nc 168 -251.294 -335.059 20 0 1 0 nc 169 -266.879 114.933 20 0 0 0 nc 170 -368.176 331.163 20 0 0 0 nc 171 -490.901 120.777 20 0 0 0 nc 172 -574.666 -153.893 20 1 0 0 nc 173 -675.963 -3.89604 20 1 0 0 nc 174 -465.576 -42.8564 20 1 0 0 nc 175 44.8044 15.5841 20 0 0 1 nc 176 157.79 -130.517 20 0 0 1 nc 177 218.178 27.2723 20 0 0 1 nc 178 178 grestore 179 179 grestore -
doc/mainpage.dox.in
r1053 r930 26 26 It is a C++ template library providing efficient implementations of common 27 27 data structures and algorithms with focus on combinatorial optimization 28 tasks connected mainly with graphs and networks \cite DezsoJuttnerKovacs11Lemon.28 tasks connected mainly with graphs and networks. 29 29 30 30 <b> … … 38 38 The project is maintained by the 39 39 <a href="http://www.cs.elte.hu/egres/">Egerváry Research Group on 40 Combinatorial Optimization</a> \ citeegres40 Combinatorial Optimization</a> \ref egres 41 41 at the Operations Research Department of the 42 42 <a href="http://www.elte.hu/en/">Eötvös Loránd University</a>, 43 43 Budapest, Hungary. 44 44 LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a> 45 initiative \ citecoinor.45 initiative \ref coinor. 46 46 47 47 \section howtoread How to Read the Documentation -
doc/min_cost_flow.dox
r1053 r1002 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 \ citeamo93networkflows.29 and arc costs \ref 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
r1051 r1002 20 20 {O}perations {R}esearch}, 21 21 url = {http://www.coin-or.org/} 22 }23 24 25 %%%%% Papers related to LEMON %%%%%26 27 @article{DezsoJuttnerKovacs11Lemon,28 author = {B. Dezs{\H o} and A. J\"uttner and P. Kov\'acs},29 title = {{LEMON} -- an open source {C++} graph template library},30 journal = {Electronic Notes in Theoretical Computer Science},31 volume = {264},32 pages = {23--45},33 year = {2011},34 note = {Proc. 2nd Workshop on Generative Technologies}35 }36 37 @article{KiralyKovacs12MCF,38 author = {Z. Kir\'aly and P. Kov\'acs},39 title = {Efficient implementations of minimum-cost flow algorithms},40 journal = {Acta Universitatis Sapientiae, Informatica},41 year = {2012},42 volume = {4},43 pages = {67--118}44 22 } 45 23 -
lemon/CMakeLists.txt
r1062 r981 37 37 IF(LEMON_HAVE_CPLEX) 38 38 SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc) 39 INCLUDE_DIRECTORIES(${ ILOG_INCLUDE_DIRS})39 INCLUDE_DIRECTORIES(${CPLEX_INCLUDE_DIRS}) 40 40 ENDIF() 41 41 -
lemon/base.cc
r1054 r477 22 22 #include<lemon/tolerance.h> 23 23 #include<lemon/core.h> 24 #include<lemon/time_measure.h>25 24 namespace lemon { 26 25 … … 33 32 #endif 34 33 35 TimeStamp::Format TimeStamp::_format = TimeStamp::NORMAL;36 37 34 } //namespace lemon -
lemon/capacity_scaling.h
r1071 r1070 67 67 /// \ref CapacityScaling implements the capacity scaling version 68 68 /// of the successive shortest path algorithm for finding a 69 /// \ref min_cost_flow "minimum cost flow" \cite amo93networkflows, 70 /// \cite edmondskarp72theoretical. It is an efficient dual 71 /// solution method, which runs in polynomial time 72 /// \f$O(e\log U (n+e)\log n)\f$, where <i>U</i> denotes the maximum 73 /// of node supply and arc capacity values. 69 /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows, 70 /// \ref edmondskarp72theoretical. It is an efficient dual 71 /// solution method. 74 72 /// 75 73 /// This algorithm is typically slower than \ref CostScaling and -
lemon/cbc.h
r1064 r877 17 17 */ 18 18 19 // -*- C++ -*- 19 20 #ifndef LEMON_CBC_H 20 21 #define LEMON_CBC_H -
lemon/concepts/bpgraph.h
r1049 r1028 998 998 /// \brief The base node of the iterator. 999 999 /// 1000 /// Returns the base node of the given incom ing arc iterator1000 /// Returns the base node of the given incomming arc iterator 1001 1001 /// (i.e. the target node of the corresponding arc). 1002 1002 Node baseNode(InArcIt) const { return INVALID; } … … 1004 1004 /// \brief The running node of the iterator. 1005 1005 /// 1006 /// Returns the running node of the given incom ing arc iterator1006 /// Returns the running node of the given incomming arc iterator 1007 1007 /// (i.e. the source node of the corresponding arc). 1008 1008 Node runningNode(InArcIt) const { return INVALID; } -
lemon/concepts/digraph.h
r1049 r877 410 410 /// \brief The base node of the iterator. 411 411 /// 412 /// Returns the base node of the given incom ing arc iterator412 /// Returns the base node of the given incomming arc iterator 413 413 /// (i.e. the target node of the corresponding arc). 414 414 Node baseNode(InArcIt) const { return INVALID; } … … 416 416 /// \brief The running node of the iterator. 417 417 /// 418 /// Returns the running node of the given incom ing arc iterator418 /// Returns the running node of the given incomming arc iterator 419 419 /// (i.e. the source node of the corresponding arc). 420 420 Node runningNode(InArcIt) const { return INVALID; } -
lemon/concepts/graph.h
r1049 r1018 758 758 /// \brief The base node of the iterator. 759 759 /// 760 /// Returns the base node of the given incom ing arc iterator760 /// Returns the base node of the given incomming arc iterator 761 761 /// (i.e. the target node of the corresponding arc). 762 762 Node baseNode(InArcIt) const { return INVALID; } … … 764 764 /// \brief The running node of the iterator. 765 765 /// 766 /// Returns the running node of the given incom ing arc iterator766 /// Returns the running node of the given incomming arc iterator 767 767 /// (i.e. the source node of the corresponding arc). 768 768 Node runningNode(InArcIt) const { return INVALID; } -
lemon/concepts/graph_components.h
r1049 r1028 876 876 void next(Arc&) const {} 877 877 878 /// \brief Return the first arc incom ing to the given node.879 /// 880 /// This function gives back the first arc incom ing to the878 /// \brief Return the first arc incomming to the given node. 879 /// 880 /// This function gives back the first arc incomming to the 881 881 /// given node. 882 882 void firstIn(Arc&, const Node&) const {} 883 883 884 /// \brief Return the next arc incom ing to the given node.885 /// 886 /// This function gives back the next arc incom ing to the884 /// \brief Return the next arc incomming to the given node. 885 /// 886 /// This function gives back the next arc incomming to the 887 887 /// given node. 888 888 void nextIn(Arc&) const {} -
lemon/config.h.in
r1064 r981 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@11 9 #cmakedefine LEMON_USE_PTHREAD 1 12 10 #cmakedefine LEMON_USE_WIN32_THREADS 1 -
lemon/core.h
r1069 r1027 36 36 #ifdef _MSC_VER 37 37 #pragma warning( disable : 4250 4355 4503 4800 4996 ) 38 #endif39 40 #ifdef __GNUC__41 // Needed by the [DI]GRAPH_TYPEDEFS marcos for gcc 4.842 #pragma GCC diagnostic ignored "-Wunused-local-typedefs"43 38 #endif 44 39 -
lemon/cost_scaling.h
r1071 r1070 92 92 /// \ref CostScaling implements a cost scaling algorithm that performs 93 93 /// push/augment and relabel operations for finding a \ref min_cost_flow 94 /// "minimum cost flow" \ cite amo93networkflows, \citegoldberg90approximation,95 /// \ cite goldberg97efficient, \citebunnagel98efficient.94 /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation, 95 /// \ref goldberg97efficient, \ref bunnagel98efficient. 96 96 /// It is a highly efficient primal-dual solution method, which 97 97 /// can be viewed as the generalization of the \ref Preflow 98 98 /// "preflow push-relabel" algorithm for the maximum flow problem. 99 /// It is a polynomial algorithm, its running time complexity is100 /// \f$O(n^2e\log(nK))\f$, where <i>K</i> denotes the maximum arc cost.101 99 /// 102 100 /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest … … 1285 1283 _buckets[r] = _bucket_next[u]; 1286 1284 1287 // Search the incom ing arcs of u1285 // Search the incomming arcs of u 1288 1286 LargeCost pi_u = _pi[u]; 1289 1287 int last_out = _first_out[u+1]; -
lemon/cplex.cc
r1063 r1016 492 492 _message_enabled ? CPX_ON : CPX_OFF); 493 493 } 494 495 void CplexBase::_write(std::string file, std::string format) const496 {497 if(format == "MPS" || format == "LP")498 CPXwriteprob(cplexEnv(), cplexLp(), file.c_str(), format.c_str());499 else if(format == "SOL")500 CPXsolwrite(cplexEnv(), cplexLp(), file.c_str());501 else throw UnsupportedFormatError(format);502 }503 504 505 494 506 495 // CplexLp members -
lemon/cplex.h
r1063 r746 151 151 bool _message_enabled; 152 152 153 void _write(std::string file, std::string format) const;154 155 153 public: 156 154 … … 173 171 const cpxlp* cplexLp() const { return _prob; } 174 172 175 #ifdef DOXYGEN176 /// Write the problem or the solution to a file in the given format177 178 /// This function writes the problem or the solution179 /// to a file in the given format.180 /// Trying to write in an unsupported format will trigger181 /// \ref UnsupportedFormatError.182 /// \param file The file path183 /// \param format The output file format.184 /// Supportted formats are "MPS", "LP" and "SOL".185 void write(std::string file, std::string format = "MPS") const {}186 #endif187 188 173 }; 189 174 -
lemon/cycle_canceling.h
r1071 r1070 48 48 /// \ref CycleCanceling implements three different cycle-canceling 49 49 /// algorithms for finding a \ref min_cost_flow "minimum cost flow" 50 /// \ cite amo93networkflows, \citeklein67primal,51 /// \ citegoldberg89cyclecanceling.50 /// \ref amo93networkflows, \ref klein67primal, 51 /// \ref goldberg89cyclecanceling. 52 52 /// The most efficent one is the \ref CANCEL_AND_TIGHTEN 53 53 /// "Cancel-and-Tighten" algorithm, thus it is the default method. 54 /// It runs in strongly polynomial time O(n<sup>2</sup>e<sup>2</sup>log(n)),55 /// but in practice, it is typically orders of magnitude slower than56 /// the scaling algorithms and\ref NetworkSimplex.54 /// It runs in strongly polynomial time, but in practice, it is typically 55 /// orders of magnitude slower than the scaling algorithms and 56 /// \ref NetworkSimplex. 57 57 /// (For more information, see \ref min_cost_flow_algs "the module page".) 58 58 /// … … 132 132 /// The "Minimum Mean Cycle-Canceling" algorithm, which is a 133 133 /// well-known strongly polynomial method 134 /// \ citegoldberg89cyclecanceling. It improves along a134 /// \ref goldberg89cyclecanceling. It improves along a 135 135 /// \ref min_mean_cycle "minimum mean cycle" in each iteration. 136 136 /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)). … … 138 138 /// The "Cancel-and-Tighten" algorithm, which can be viewed as an 139 139 /// improved version of the previous method 140 /// \ citegoldberg89cyclecanceling.140 /// \ref goldberg89cyclecanceling. 141 141 /// It is faster both in theory and in practice, its running time 142 142 /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)). -
lemon/glpk.cc
r1063 r989 581 581 break; 582 582 } 583 }584 585 void GlpkBase::_write(std::string file, std::string format) const586 {587 if(format == "MPS")588 glp_write_mps(lp, GLP_MPS_FILE, 0, file.c_str());589 else if(format == "LP")590 glp_write_lp(lp, 0, file.c_str());591 else throw UnsupportedFormatError(format);592 583 } 593 584 … … 1008 999 const char* GlpkMip::_solverName() const { return "GlpkMip"; } 1009 1000 1010 1011 1012 1001 } //END OF NAMESPACE LEMON -
lemon/glpk.h
r1063 r877 116 116 virtual void _messageLevel(MessageLevel level); 117 117 118 virtual void _write(std::string file, std::string format) const;119 120 118 private: 121 119 … … 147 145 int lpxCol(Col c) const { return cols(id(c)); } 148 146 149 #ifdef DOXYGEN150 /// Write the problem or the solution to a file in the given format151 152 /// This function writes the problem or the solution153 /// to a file in the given format.154 /// Trying to write in an unsupported format will trigger155 /// \ref UnsupportedFormatError.156 /// \param file The file path157 /// \param format The output file format.158 /// Supportted formats are "MPS" and "LP".159 void write(std::string file, std::string format = "MPS") const {}160 #endif161 162 147 }; 163 148 -
lemon/grosso_locatelli_pullan_mc.h
r1053 r918 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 \ citegrosso08maxclique.43 /// \e clique \e problem \ref 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
r1053 r1002 99 99 /// This class implements the Hartmann-Orlin algorithm for finding 100 100 /// a directed cycle of minimum mean cost in a digraph 101 /// \cite hartmann93finding, \cite dasdan98minmeancycle. 102 /// This method is based on \ref KarpMmc "Karp"'s original algorithm, but 103 /// applies an early termination scheme. It makes the algorithm 104 /// significantly faster for some problem instances, but slower for others. 105 /// The algorithm runs in time O(ne) and uses space O(n<sup>2</sup>+e). 101 /// \ref hartmann93finding, \ref dasdan98minmeancycle. 102 /// It is an improved version of \ref KarpMmc "Karp"'s original algorithm, 103 /// it applies an efficient early termination scheme. 104 /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e). 106 105 /// 107 106 /// \tparam GR The type of the digraph the algorithm runs on. … … 276 275 /// 277 276 /// If you don't call this function before calling \ref run() or 278 /// \ref findCycleMean(), a local \ref Path "path" structure279 /// will be allocated. The destuctor deallocates this automatically277 /// \ref findCycleMean(), it will allocate a local \ref Path "path" 278 /// structure. The destuctor deallocates this automatically 280 279 /// allocated object, of course. 281 280 /// -
lemon/howard_mmc.h
r1053 r1012 99 99 /// This class implements Howard's policy iteration algorithm for finding 100 100 /// a directed cycle of minimum mean cost in a digraph 101 /// \ cite dasdan98minmeancycle, \citedasdan04experimental.101 /// \ref dasdan98minmeancycle, \ref dasdan04experimental. 102 102 /// This class provides the most efficient algorithm for the 103 103 /// minimum mean cycle problem, though the best known theoretical … … 283 283 /// 284 284 /// If you don't call this function before calling \ref run() or 285 /// \ref findCycleMean(), a local \ref Path "path" structure286 /// will be allocated. The destuctor deallocates this automatically285 /// \ref findCycleMean(), it will allocate a local \ref Path "path" 286 /// structure. The destuctor deallocates this automatically 287 287 /// allocated object, of course. 288 288 /// -
lemon/karp_mmc.h
r1053 r1002 99 99 /// This class implements Karp's algorithm for finding a directed 100 100 /// cycle of minimum mean cost in a digraph 101 /// \ cite karp78characterization, \citedasdan98minmeancycle.101 /// \ref karp78characterization, \ref dasdan98minmeancycle. 102 102 /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e). 103 103 /// … … 271 271 /// 272 272 /// If you don't call this function before calling \ref run() or 273 /// \ref findCycleMean(), a local \ref Path "path" structure274 /// will be allocated. The destuctor deallocates this automatically273 /// \ref findCycleMean(), it will allocate a local \ref Path "path" 274 /// structure. The destuctor deallocates this automatically 275 275 /// allocated object, of course. 276 276 /// -
lemon/list_graph.h
r1049 r1025 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 incom ing arcs of \c v.448 ///iterators are invalidated for the incomming 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
r1064 r877 60 60 ///\ingroup lp_group 61 61 /// 62 ///Currently, the possible values are \c GLPK , \c CPLEX or \c CBC62 ///Currently, the possible values are \c GLPK or \c CPLEX 63 63 #define LEMON_DEFAULT_MIP SOLVER 64 64 ///The default MIP solver. … … 67 67 ///\ingroup lp_group 68 68 /// 69 ///Currently, it is either \c GlpkMip , \c CplexMip , \c CbcMip69 ///Currently, it is either \c GlpkMip or \c CplexMip 70 70 typedef GlpkMip Mip; 71 71 #else 72 #if LEMON_DEFAULT_LP == GLPK 72 #ifdef LEMON_HAVE_GLPK 73 # define LEMON_DEFAULT_LP GLPK 73 74 typedef GlpkLp Lp; 74 #elif LEMON_DEFAULT_LP == CPLEX 75 # define LEMON_DEFAULT_MIP GLPK 76 typedef GlpkMip Mip; 77 #elif LEMON_HAVE_CPLEX 78 # define LEMON_DEFAULT_LP CPLEX 75 79 typedef CplexLp Lp; 76 #elif LEMON_DEFAULT_LP == SOPLEX 80 # define LEMON_DEFAULT_MIP CPLEX 81 typedef CplexMip Mip; 82 #elif LEMON_HAVE_SOPLEX 83 # define DEFAULT_LP SOPLEX 77 84 typedef SoplexLp Lp; 78 #elif LEMON_DEFAULT_LP == CLP 85 #elif LEMON_HAVE_CLP 86 # define DEFAULT_LP CLP 79 87 typedef ClpLp Lp; 80 #endif81 #if LEMON_DEFAULT_MIP == GLPK82 typedef GlpkLp Mip;83 #elif LEMON_DEFAULT_MIP == CPLEX84 typedef CplexMip Mip;85 #elif LEMON_DEFAULT_MIP == CBC86 typedef CbcMip Mip;87 88 #endif 88 89 #endif -
lemon/lp_base.h
r1063 r989 1008 1008 public: 1009 1009 1010 ///\e1011 class UnsupportedFormatError : public Exception1012 {1013 std::string _format;1014 mutable std::string _what;1015 public:1016 explicit UnsupportedFormatError(std::string format) throw()1017 : _format(format) { }1018 virtual ~UnsupportedFormatError() throw() {}1019 virtual const char* what() const throw() {1020 try {1021 _what.clear();1022 std::ostringstream oss;1023 oss << "lemon::UnsupportedFormatError: " << _format;1024 _what = oss.str();1025 }1026 catch (...) {}1027 if (!_what.empty()) return _what.c_str();1028 else return "lemon::UnsupportedFormatError";1029 }1030 };1031 1032 protected:1033 virtual void _write(std::string, std::string format) const1034 {1035 throw UnsupportedFormatError(format);1036 }1037 1038 public:1039 1040 1010 /// Virtual destructor 1041 1011 virtual ~LpBase() {} … … 1586 1556 void min() { _setSense(MIN); } 1587 1557 1588 ///Clear the problem1558 ///Clears the problem 1589 1559 void clear() { _clear(); rows.clear(); cols.clear(); } 1590 1560 1591 /// Set the message level of the solver1561 /// Sets the message level of the solver 1592 1562 void messageLevel(MessageLevel level) { _messageLevel(level); } 1593 1594 /// Write the problem to a file in the given format1595 1596 /// This function writes the problem to a file in the given format.1597 /// Different solver backends may support different formats.1598 /// Trying to write in an unsupported format will trigger1599 /// \ref UnsupportedFormatError. For the supported formats,1600 /// visit the documentation of the base class of the related backends1601 /// (\ref CplexBase, \ref GlpkBase etc.)1602 /// \param file The file path1603 /// \param format The output file format.1604 void write(std::string file, std::string format = "MPS") const1605 {1606 _write(file.c_str(),format.c_str());1607 }1608 1563 1609 1564 ///@} -
lemon/lp_skeleton.cc
r1063 r877 92 92 void SkeletonSolverBase::_messageLevel(MessageLevel) {} 93 93 94 void SkeletonSolverBase::_write(std::string, std::string) const {}95 96 94 LpSkeleton::SolveExitStatus LpSkeleton::_solve() { return SOLVED; } 97 95 -
lemon/lp_skeleton.h
r1063 r877 145 145 ///\e 146 146 virtual void _messageLevel(MessageLevel); 147 148 ///\e149 virtual void _write(std::string file, std::string format) const;150 151 147 }; 152 148 … … 227 223 ///\e 228 224 virtual const char* _solverName() const; 229 230 225 }; 231 226 -
lemon/math.h
r1054 r877 66 66 } 67 67 68 ///Round a value to its closest integer69 inline double round(double r) {70 return (r > 0.0) ? floor(r + 0.5) : ceil(r - 0.5);71 }72 73 68 /// @} 74 69 75 70 } //namespace lemon 76 71 77 #endif //LEMON_ MATH_H72 #endif //LEMON_TOLERANCE_H -
lemon/network_simplex.h
r1071 r1070 42 42 /// \ref NetworkSimplex implements the primal Network Simplex algorithm 43 43 /// for finding a \ref min_cost_flow "minimum cost flow" 44 /// \ cite amo93networkflows, \citedantzig63linearprog,45 /// \ citekellyoneill91netsimplex.44 /// \ref amo93networkflows, \ref dantzig63linearprog, 45 /// \ref kellyoneill91netsimplex. 46 46 /// This algorithm is a highly efficient specialized version of the 47 47 /// linear programming simplex method directly for the minimum cost … … 1517 1517 } 1518 1518 } else { 1519 // Find the min. cost incom ing arc for each demand node1519 // Find the min. cost incomming arc for each demand node 1520 1520 for (int i = 0; i != int(demand_nodes.size()); ++i) { 1521 1521 Node v = demand_nodes[i]; -
lemon/path.h
r1044 r1000 318 318 /// Constructor with starting point 319 319 ArcIt(const SimplePath &_path, int _idx) 320 : path(&_path), idx(_idx) {}320 : idx(_idx), path(&_path) {} 321 321 322 322 public: -
lemon/preflow.h
r1053 r966 103 103 /// This class provides an implementation of Goldberg-Tarjan's \e preflow 104 104 /// \e push-relabel algorithm producing a \ref max_flow 105 /// "flow of maximum value" in a digraph \ citeclrs01algorithms,106 /// \ cite amo93networkflows, \citegoldberg88newapproach.105 /// "flow of maximum value" in a digraph \ref clrs01algorithms, 106 /// \ref amo93networkflows, \ref goldberg88newapproach. 107 107 /// The preflow algorithms are the fastest known maximum 108 108 /// flow algorithms. The current implementation uses a mixture of the -
lemon/time_measure.h
r1054 r786 35 35 #include <fstream> 36 36 #include <iostream> 37 #include <lemon/math.h>38 37 39 38 namespace lemon { … … 65 64 double rtime; 66 65 67 public:68 ///Display format specifier69 70 ///\e71 ///72 enum Format {73 /// Reports all measured values74 NORMAL = 0,75 /// Only real time and an error indicator is displayed76 SHORT = 177 };78 79 private:80 static Format _format;81 82 66 void _reset() { 83 67 utime = stime = cutime = cstime = rtime = 0; … … 86 70 public: 87 71 88 ///Set output format89 90 ///Set output format.91 ///92 ///The output format is global for all timestamp instances.93 static void format(Format f) { _format = f; }94 ///Retrieve the current output format95 96 ///Retrieve the current output format97 ///98 ///The output format is global for all timestamp instances.99 static Format format() { return _format; }100 101 102 72 ///Read the current time values of the process 103 73 void stamp() … … 255 225 inline std::ostream& operator<<(std::ostream& os,const TimeStamp &t) 256 226 { 257 switch(t._format) 258 { 259 case TimeStamp::NORMAL: 260 os << "u: " << t.userTime() << 261 "s, s: " << t.systemTime() << 262 "s, cu: " << t.cUserTime() << 263 "s, cs: " << t.cSystemTime() << 264 "s, real: " << t.realTime() << "s"; 265 break; 266 case TimeStamp::SHORT: 267 double total = t.userTime()+t.systemTime()+ 268 t.cUserTime()+t.cSystemTime(); 269 os << t.realTime() 270 << "s (err: " << round((t.realTime()-total)/ 271 t.realTime()*10000)/100 272 << "%)"; 273 break; 274 } 227 os << "u: " << t.userTime() << 228 "s, s: " << t.systemTime() << 229 "s, cu: " << t.cUserTime() << 230 "s, cs: " << t.cSystemTime() << 231 "s, real: " << t.realTime() << "s"; 275 232 return os; 276 233 } … … 512 469 std::string _title; 513 470 std::ostream &_os; 514 bool _active;515 471 public: 516 472 ///Constructor … … 520 476 ///\param os The stream to print the report to. 521 477 ///\param run Sets whether the timer should start immediately. 522 ///\param active Sets whether the report should actually be printed 523 /// on destruction. 524 TimeReport(std::string title,std::ostream &os=std::cerr,bool run=true, 525 bool active=true) 526 : Timer(run), _title(title), _os(os), _active(active) {} 478 TimeReport(std::string title,std::ostream &os=std::cerr,bool run=true) 479 : Timer(run), _title(title), _os(os){} 527 480 ///Destructor that prints the ellapsed time 528 481 ~TimeReport() 529 482 { 530 if(_active) _os << _title << *this << std::endl; 531 } 532 533 ///Retrieve the activity status 534 535 ///\e 536 /// 537 bool active() const { return _active; } 538 ///Set the activity status 539 540 /// This function set whether the time report should actually be printed 541 /// on destruction. 542 void active(bool a) { _active=a; } 483 _os << _title << *this << std::endl; 484 } 543 485 }; 544 486 -
test/CMakeLists.txt
r1065 r1038 42 42 max_cardinality_search_test 43 43 max_clique_test 44 max_flow_test45 44 min_cost_arborescence_test 46 45 min_cost_flow_test … … 49 48 path_test 50 49 planarity_test 50 preflow_test 51 51 radix_sort_test 52 52 random_test … … 70 70 ENDIF() 71 71 IF(LEMON_HAVE_CPLEX) 72 SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${ ILOG_LIBRARIES})72 SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${CPLEX_LIBRARIES}) 73 73 ENDIF() 74 74 IF(LEMON_HAVE_CLP) … … 94 94 GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH) 95 95 ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD 96 COMMAND ${CMAKE_COMMAND} -E copy ${ ILOG_CPLEX_DLL}${TARGET_PATH}96 COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex.dll ${TARGET_PATH} 97 97 ) 98 98 ENDIF() … … 112 112 ENDIF() 113 113 IF(LEMON_HAVE_CPLEX) 114 SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${ ILOG_LIBRARIES})114 SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${CPLEX_LIBRARIES}) 115 115 ENDIF() 116 116 IF(LEMON_HAVE_CBC) … … 136 136 GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH) 137 137 ADD_CUSTOM_COMMAND(TARGET mip_test POST_BUILD 138 COMMAND ${CMAKE_COMMAND} -E copy ${ ILOG_CPLEX_DLL}${TARGET_PATH}138 COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex.dll ${TARGET_PATH} 139 139 ) 140 140 ENDIF() -
test/lp_test.cc
r1064 r988 241 241 { 242 242 LP::DualExpr e,f,g; 243 LP::Row p1 = INVALID, p2 = INVALID; 243 LP::Row p1 = INVALID, p2 = INVALID, p3 = INVALID, 244 p4 = INVALID, p5 = INVALID; 244 245 245 246 e[p1]=2; -
test/maps_test.cc
r1067 r998 536 536 537 537 typedef Orienter<Graph, const ConstMap<Edge, bool> > Digraph; 538 ConstMap<Edge, bool> true_edge_map(true); 539 Digraph dgr(gr, true_edge_map); 538 Digraph dgr(gr, constMap<Edge, bool>(true)); 540 539 OutDegMap<Digraph> odm(dgr); 541 540 InDegMap<Digraph> idm(dgr); -
test/path_test.cc
r1044 r990 22 22 #include <lemon/concepts/path.h> 23 23 #include <lemon/concepts/digraph.h> 24 #include <lemon/concept_check.h>25 24 26 25 #include <lemon/path.h> … … 32 31 using namespace lemon; 33 32 34 template <typename GR> 35 void checkConcepts() { 36 checkConcept<concepts::Path<GR>, concepts::Path<GR> >(); 37 checkConcept<concepts::Path<GR>, Path<GR> >(); 38 checkConcept<concepts::Path<GR>, SimplePath<GR> >(); 39 checkConcept<concepts::Path<GR>, StaticPath<GR> >(); 40 checkConcept<concepts::Path<GR>, ListPath<GR> >(); 41 } 42 43 // Conecpt checking for path structures 44 void checkPathConcepts() { 45 checkConcepts<concepts::Digraph>(); 46 checkConcepts<ListDigraph>(); 33 void check_concepts() { 34 checkConcept<concepts::Path<ListDigraph>, concepts::Path<ListDigraph> >(); 35 checkConcept<concepts::Path<ListDigraph>, Path<ListDigraph> >(); 36 checkConcept<concepts::Path<ListDigraph>, SimplePath<ListDigraph> >(); 37 checkConcept<concepts::Path<ListDigraph>, StaticPath<ListDigraph> >(); 38 checkConcept<concepts::Path<ListDigraph>, ListPath<ListDigraph> >(); 47 39 } 48 40 49 41 // Check if proper copy consructor is called (use valgrind for testing) 50 template <typename GR, typename P1, typename P2> 51 void checkCopy(typename GR::Arc a) { 52 P1 p; 42 template<class _Path> 43 void checkCopy() 44 { 45 ListDigraph g; 46 ListDigraph::Arc a = g.addArc(g.addNode(), g.addNode()); 47 48 _Path p,q; 53 49 p.addBack(a); 54 P1 q; 55 q = p; 56 P1 r(p); 57 P2 q2; 58 q2 = p; 59 P2 r2(p); 50 q=p; 51 _Path r(p); 52 StaticPath<ListDigraph> s(r); 60 53 } 54 55 int main() { 56 check_concepts(); 61 57 62 // Tests for copy constructors and assignment operators of paths 63 void checkPathCopy() { 58 checkCopy<Path<ListDigraph> >(); 59 checkCopy<SimplePath<ListDigraph> >(); 60 checkCopy<ListPath<ListDigraph> >(); 61 64 62 ListDigraph g; 65 ListDigraph::Arc a = g.addArc(g.addNode(), g.addNode()); 66 67 typedef Path<ListDigraph> Path1; 68 typedef SimplePath<ListDigraph> Path2; 69 typedef ListPath<ListDigraph> Path3; 70 typedef StaticPath<ListDigraph> Path4; 71 checkCopy<ListDigraph, Path1, Path2>(a); 72 checkCopy<ListDigraph, Path1, Path3>(a); 73 checkCopy<ListDigraph, Path1, Path4>(a); 74 checkCopy<ListDigraph, Path2, Path1>(a); 75 checkCopy<ListDigraph, Path2, Path3>(a); 76 checkCopy<ListDigraph, Path2, Path4>(a); 77 checkCopy<ListDigraph, Path3, Path1>(a); 78 checkCopy<ListDigraph, Path3, Path2>(a); 79 checkCopy<ListDigraph, Path3, Path4>(a); 80 } 81 82 // Class for testing path functions 83 class CheckPathFunctions { 84 typedef ListDigraph GR; 85 DIGRAPH_TYPEDEFS(GR); 86 GR gr; 87 const GR& cgr; 88 Node n1, n2, n3, n4; 89 Node tmp_n; 90 Arc a1, a2, a3, a4; 91 Arc tmp_a; 92 93 public: 94 95 CheckPathFunctions() : cgr(gr) { 96 n1 = gr.addNode(); 97 n2 = gr.addNode(); 98 n3 = gr.addNode(); 99 n4 = gr.addNode(); 100 a1 = gr.addArc(n1, n2); 101 a2 = gr.addArc(n2, n3); 102 a3 = gr.addArc(n3, n4); 103 a4 = gr.addArc(n4, n1); 104 } 105 106 void run() { 107 checkBackAndFrontInsertablePath<Path<GR> >(); 108 checkBackAndFrontInsertablePath<ListPath<GR> >(); 109 checkBackInsertablePath<SimplePath<GR> >(); 110 111 checkListPathSplitAndSplice(); 112 } 113 114 private: 115 116 template <typename P> 117 void checkBackInsertablePath() { 118 119 // Create and check empty path 120 P p; 121 const P& cp = p; 122 check(cp.empty(), "The path is not empty"); 123 check(cp.length() == 0, "The path is not empty"); 124 // check(cp.front() == INVALID, "Wrong front()"); 125 // check(cp.back() == INVALID, "Wrong back()"); 126 typename P::ArcIt ai(cp); 127 check(ai == INVALID, "Wrong ArcIt"); 128 check(pathSource(cgr, cp) == INVALID, "Wrong pathSource()"); 129 check(pathTarget(cgr, cp) == INVALID, "Wrong pathTarget()"); 130 check(checkPath(cgr, cp), "Wrong checkPath()"); 131 PathNodeIt<P> ni(cgr, cp); 132 check(ni == INVALID, "Wrong PathNodeIt"); 133 134 // Check single-arc path 135 p.addBack(a1); 136 check(!cp.empty(), "Wrong empty()"); 137 check(cp.length() == 1, "Wrong length"); 138 check(cp.front() == a1, "Wrong front()"); 139 check(cp.back() == a1, "Wrong back()"); 140 check(cp.nth(0) == a1, "Wrong nth()"); 141 ai = cp.nthIt(0); 142 check((tmp_a = ai) == a1, "Wrong nthIt()"); 143 check(++ai == INVALID, "Wrong nthIt()"); 144 typename P::ArcIt ai2(cp); 145 check((tmp_a = ai2) == a1, "Wrong ArcIt"); 146 check(++ai2 == INVALID, "Wrong ArcIt"); 147 check(pathSource(cgr, cp) == n1, "Wrong pathSource()"); 148 check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()"); 149 check(checkPath(cgr, cp), "Wrong checkPath()"); 150 PathNodeIt<P> ni2(cgr, cp); 151 check((tmp_n = ni2) == n1, "Wrong PathNodeIt"); 152 check((tmp_n = ++ni2) == n2, "Wrong PathNodeIt"); 153 check(++ni2 == INVALID, "Wrong PathNodeIt"); 154 155 // Check adding more arcs 156 p.addBack(a2); 157 p.addBack(a3); 158 check(!cp.empty(), "Wrong empty()"); 159 check(cp.length() == 3, "Wrong length"); 160 check(cp.front() == a1, "Wrong front()"); 161 check(cp.back() == a3, "Wrong back()"); 162 check(cp.nth(0) == a1, "Wrong nth()"); 163 check(cp.nth(1) == a2, "Wrong nth()"); 164 check(cp.nth(2) == a3, "Wrong nth()"); 165 typename P::ArcIt ai3(cp); 166 check((tmp_a = ai3) == a1, "Wrong ArcIt"); 167 check((tmp_a = ++ai3) == a2, "Wrong nthIt()"); 168 check((tmp_a = ++ai3) == a3, "Wrong nthIt()"); 169 check(++ai3 == INVALID, "Wrong nthIt()"); 170 ai = cp.nthIt(0); 171 check((tmp_a = ai) == a1, "Wrong nthIt()"); 172 check((tmp_a = ++ai) == a2, "Wrong nthIt()"); 173 ai = cp.nthIt(2); 174 check((tmp_a = ai) == a3, "Wrong nthIt()"); 175 check(++ai == INVALID, "Wrong nthIt()"); 176 check(pathSource(cgr, cp) == n1, "Wrong pathSource()"); 177 check(pathTarget(cgr, cp) == n4, "Wrong pathTarget()"); 178 check(checkPath(cgr, cp), "Wrong checkPath()"); 179 PathNodeIt<P> ni3(cgr, cp); 180 check((tmp_n = ni3) == n1, "Wrong PathNodeIt"); 181 check((tmp_n = ++ni3) == n2, "Wrong PathNodeIt"); 182 check((tmp_n = ++ni3) == n3, "Wrong PathNodeIt"); 183 check((tmp_n = ++ni3) == n4, "Wrong PathNodeIt"); 184 check(++ni3 == INVALID, "Wrong PathNodeIt"); 185 186 // Check arc removal and addition 187 p.eraseBack(); 188 p.eraseBack(); 189 p.addBack(a2); 190 check(!cp.empty(), "Wrong empty()"); 191 check(cp.length() == 2, "Wrong length"); 192 check(cp.front() == a1, "Wrong front()"); 193 check(cp.back() == a2, "Wrong back()"); 194 check(pathSource(cgr, cp) == n1, "Wrong pathSource()"); 195 check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()"); 196 check(checkPath(cgr, cp), "Wrong checkPath()"); 197 198 // Check clear() 199 p.clear(); 200 check(cp.empty(), "The path is not empty"); 201 check(cp.length() == 0, "The path is not empty"); 202 203 // Check inconsistent path 204 p.addBack(a4); 205 p.addBack(a2); 206 p.addBack(a1); 207 check(!cp.empty(), "Wrong empty()"); 208 check(cp.length() == 3, "Wrong length"); 209 check(cp.front() == a4, "Wrong front()"); 210 check(cp.back() == a1, "Wrong back()"); 211 check(pathSource(cgr, cp) == n4, "Wrong pathSource()"); 212 check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()"); 213 check(!checkPath(cgr, cp), "Wrong checkPath()"); 214 } 215 216 template <typename P> 217 void checkBackAndFrontInsertablePath() { 218 219 // Include back insertable test cases 220 checkBackInsertablePath<P>(); 221 222 // Check front and back insertion 223 P p; 224 const P& cp = p; 225 p.addFront(a4); 226 p.addBack(a1); 227 p.addFront(a3); 228 check(!cp.empty(), "Wrong empty()"); 229 check(cp.length() == 3, "Wrong length"); 230 check(cp.front() == a3, "Wrong front()"); 231 check(cp.back() == a1, "Wrong back()"); 232 check(cp.nth(0) == a3, "Wrong nth()"); 233 check(cp.nth(1) == a4, "Wrong nth()"); 234 check(cp.nth(2) == a1, "Wrong nth()"); 235 typename P::ArcIt ai(cp); 236 check((tmp_a = ai) == a3, "Wrong ArcIt"); 237 check((tmp_a = ++ai) == a4, "Wrong nthIt()"); 238 check((tmp_a = ++ai) == a1, "Wrong nthIt()"); 239 check(++ai == INVALID, "Wrong nthIt()"); 240 ai = cp.nthIt(0); 241 check((tmp_a = ai) == a3, "Wrong nthIt()"); 242 check((tmp_a = ++ai) == a4, "Wrong nthIt()"); 243 ai = cp.nthIt(2); 244 check((tmp_a = ai) == a1, "Wrong nthIt()"); 245 check(++ai == INVALID, "Wrong nthIt()"); 246 check(pathSource(cgr, cp) == n3, "Wrong pathSource()"); 247 check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()"); 248 check(checkPath(cgr, cp), "Wrong checkPath()"); 249 250 // Check eraseFront() 251 p.eraseFront(); 252 p.addBack(a2); 253 check(!cp.empty(), "Wrong empty()"); 254 check(cp.length() == 3, "Wrong length"); 255 check(cp.front() == a4, "Wrong front()"); 256 check(cp.back() == a2, "Wrong back()"); 257 check(cp.nth(0) == a4, "Wrong nth()"); 258 check(cp.nth(1) == a1, "Wrong nth()"); 259 check(cp.nth(2) == a2, "Wrong nth()"); 260 typename P::ArcIt ai2(cp); 261 check((tmp_a = ai2) == a4, "Wrong ArcIt"); 262 check((tmp_a = ++ai2) == a1, "Wrong nthIt()"); 263 check((tmp_a = ++ai2) == a2, "Wrong nthIt()"); 264 check(++ai2 == INVALID, "Wrong nthIt()"); 265 ai = cp.nthIt(0); 266 check((tmp_a = ai) == a4, "Wrong nthIt()"); 267 check((tmp_a = ++ai) == a1, "Wrong nthIt()"); 268 ai = cp.nthIt(2); 269 check((tmp_a = ai) == a2, "Wrong nthIt()"); 270 check(++ai == INVALID, "Wrong nthIt()"); 271 check(pathSource(cgr, cp) == n4, "Wrong pathSource()"); 272 check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()"); 273 check(checkPath(cgr, cp), "Wrong checkPath()"); 274 } 275 276 void checkListPathSplitAndSplice() { 277 278 // Build a path with spliceFront() and spliceBack() 279 ListPath<GR> p1, p2, p3, p4; 280 p1.addBack(a3); 281 p1.addFront(a2); 282 p2.addBack(a1); 283 p1.spliceFront(p2); 284 p3.addFront(a4); 285 p1.spliceBack(p3); 286 check(p1.length() == 4, "Wrong length"); 287 check(p1.front() == a1, "Wrong front()"); 288 check(p1.back() == a4, "Wrong back()"); 289 ListPath<GR>::ArcIt ai(p1); 290 check((tmp_a = ai) == a1, "Wrong ArcIt"); 291 check((tmp_a = ++ai) == a2, "Wrong nthIt()"); 292 check((tmp_a = ++ai) == a3, "Wrong nthIt()"); 293 check((tmp_a = ++ai) == a4, "Wrong nthIt()"); 294 check(++ai == INVALID, "Wrong nthIt()"); 295 check(checkPath(cgr, p1), "Wrong checkPath()"); 296 297 // Check split() 298 p1.split(p1.nthIt(2), p2); 299 check(p1.length() == 2, "Wrong length"); 300 ai = p1.nthIt(0); 301 check((tmp_a = ai) == a1, "Wrong ArcIt"); 302 check((tmp_a = ++ai) == a2, "Wrong nthIt()"); 303 check(++ai == INVALID, "Wrong nthIt()"); 304 check(checkPath(cgr, p1), "Wrong checkPath()"); 305 check(p2.length() == 2, "Wrong length"); 306 ai = p2.nthIt(0); 307 check((tmp_a = ai) == a3, "Wrong ArcIt"); 308 check((tmp_a = ++ai) == a4, "Wrong nthIt()"); 309 check(++ai == INVALID, "Wrong nthIt()"); 310 check(checkPath(cgr, p2), "Wrong checkPath()"); 311 312 // Check split() and splice() 313 p1.spliceFront(p2); 314 p1.split(p1.nthIt(2), p2); 315 p2.split(p2.nthIt(1), p3); 316 p2.spliceBack(p1); 317 p2.splice(p2.nthIt(1), p3); 318 check(p2.length() == 4, "Wrong length"); 319 check(p2.front() == a1, "Wrong front()"); 320 check(p2.back() == a4, "Wrong back()"); 321 ai = p2.nthIt(0); 322 check((tmp_a = ai) == a1, "Wrong ArcIt"); 323 check((tmp_a = ++ai) == a2, "Wrong nthIt()"); 324 check((tmp_a = ++ai) == a3, "Wrong nthIt()"); 325 check((tmp_a = ++ai) == a4, "Wrong nthIt()"); 326 check(++ai == INVALID, "Wrong nthIt()"); 327 check(checkPath(cgr, p2), "Wrong checkPath()"); 328 } 329 330 }; 331 332 int main() { 333 checkPathConcepts(); 334 checkPathCopy(); 335 CheckPathFunctions cpf; 336 cpf.run(); 63 ListDigraph::Arc a = g.addArc(g.addNode(), g.addNode()); 64 65 Path<ListDigraph> p; 66 StaticPath<ListDigraph> q,r; 67 p.addBack(a); 68 q=p; 69 r=q; 70 StaticPath<ListDigraph> s(q); 337 71 338 72 return 0;
Note: See TracChangeset
for help on using the changeset viewer.