LEMON/LEMON-main Changeset - r784:1a7fe3bef514

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r784:1a7fe3bef514

« 783:ef88c0
« 516:c6acc3

789:8ddb7d »
787:c22306 »

r784:1a7fe3bef514

Thu, 05 Nov 2009 15:50:01

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Merge #321

1 109 87

merge default

2 files changed:

cmake/FindCOIN.cmake

cmake/FindCPLEX.cmake

cmake/FindGLPK.cmake

cmake/LEMONConfig.cmake.in

doc/images/bipartite_matching.eps

586

doc/images/bipartite_partitions.eps

114

doc/images/connected_components.eps

159

doc/images/edge_biconnected_components.eps

159

doc/images/grid_graph.eps

286

doc/images/node_biconnected_components.eps

159

doc/images/strongly_connected_components.eps

180

doc/min_cost_flow.dox

153

doc/references.bib

301

.hgignore

CMakeLists.txt

INSTALL

LICENSE

Makefile.am

NEWS

README

cmake/version.cmake.in

configure.ac

demo/CMakeLists.txt

demo/Makefile.am

demo/arg_parser_demo.cc

demo/graph_to_eps_demo.cc

demo/lgf_demo.cc

doc/CMakeLists.txt

doc/Doxyfile.in

doc/Makefile.am

doc/coding_style.dox

doc/dirs.dox

doc/groups.dox

373

158

doc/lgf.dox

doc/license.dox

doc/mainpage.dox

doc/migration.dox

doc/named-param.dox

doc/namespaces.dox

doc/template.h

lemon/CMakeLists.txt

lemon/Makefile.am

100

Changeset was too big and was cut off... Show full diff

↑ Collapse diff ↑

cmake/FindCOIN.cmake

Show inline comments

 		SET(COIN_ROOT_DIR "" CACHE PATH "COIN root directory")
 		FIND_PATH(COIN_INCLUDE_DIR coin/CoinUtilsConfig.h
 		  HINTS ${COIN_ROOT_DIR}/include
+		)
 		FIND_LIBRARY(COIN_CBC_LIBRARY
 		  NAMES Cbc libCbc
 		  HINTS ${COIN_ROOT_DIR}/lib
+		)
 		FIND_LIBRARY(COIN_CBC_SOLVER_LIBRARY
 		  NAMES CbcSolver libCbcSolver
 		  HINTS ${COIN_ROOT_DIR}/lib
+		)
 		FIND_LIBRARY(COIN_CGL_LIBRARY
 		  NAMES Cgl libCgl
 		  HINTS ${COIN_ROOT_DIR}/lib
+		)
 		FIND_LIBRARY(COIN_CLP_LIBRARY
 		  NAMES Clp libClp
 		  HINTS ${COIN_ROOT_DIR}/lib
+		)
 		FIND_LIBRARY(COIN_COIN_UTILS_LIBRARY
 		  NAMES CoinUtils libCoinUtils
 		  HINTS ${COIN_ROOT_DIR}/lib
+		)
 		FIND_LIBRARY(COIN_OSI_LIBRARY
 		  NAMES Osi libOsi
 		  HINTS ${COIN_ROOT_DIR}/lib
+		)
 		FIND_LIBRARY(COIN_OSI_CBC_LIBRARY
 		  NAMES OsiCbc libOsiCbc
 		  HINTS ${COIN_ROOT_DIR}/lib
+		)
 		FIND_LIBRARY(COIN_OSI_CLP_LIBRARY
 		  NAMES OsiClp libOsiClp
 		  HINTS ${COIN_ROOT_DIR}/lib
+		)
 		FIND_LIBRARY(COIN_OSI_VOL_LIBRARY
 		  NAMES OsiVol libOsiVol
 		  HINTS ${COIN_ROOT_DIR}/lib
+		)
 		FIND_LIBRARY(COIN_VOL_LIBRARY
 		  NAMES Vol libVol
 		  HINTS ${COIN_ROOT_DIR}/lib
+		)
 		INCLUDE(FindPackageHandleStandardArgs)
 		FIND_PACKAGE_HANDLE_STANDARD_ARGS(COIN DEFAULT_MSG
 		  COIN_INCLUDE_DIR
 		  COIN_CBC_LIBRARY
 		  COIN_CBC_SOLVER_LIBRARY
 		  COIN_CGL_LIBRARY
 		  COIN_CLP_LIBRARY
 		  COIN_COIN_UTILS_LIBRARY
 		  COIN_OSI_LIBRARY
 		  COIN_OSI_CBC_LIBRARY
 		  COIN_OSI_CLP_LIBRARY
 		  COIN_OSI_VOL_LIBRARY
 		  COIN_VOL_LIBRARY
+		)
 		IF(COIN_FOUND)
 		  SET(COIN_INCLUDE_DIRS ${COIN_INCLUDE_DIR})
 		  SET(COIN_LIBRARIES "${COIN_CBC_LIBRARY};${COIN_CBC_SOLVER_LIBRARY};${COIN_CGL_LIBRARY};${COIN_CLP_LIBRARY};${COIN_COIN_UTILS_LIBRARY};${COIN_OSI_LIBRARY};${COIN_OSI_CBC_LIBRARY};${COIN_OSI_CLP_LIBRARY};${COIN_OSI_VOL_LIBRARY};${COIN_VOL_LIBRARY}")
 		  SET(COIN_CLP_LIBRARIES "${COIN_CLP_LIBRARY};${COIN_COIN_UTILS_LIBRARY}")
 		  SET(COIN_CBC_LIBRARIES ${COIN_LIBRARIES})
 		ENDIF(COIN_FOUND)
 		MARK_AS_ADVANCED(
 		  COIN_INCLUDE_DIR
 		  COIN_CBC_LIBRARY
 		  COIN_CBC_SOLVER_LIBRARY
 		  COIN_CGL_LIBRARY
 		  COIN_CLP_LIBRARY
 		  COIN_COIN_UTILS_LIBRARY
 		  COIN_OSI_LIBRARY
 		  COIN_OSI_CBC_LIBRARY
 		  COIN_OSI_CLP_LIBRARY
 		  COIN_OSI_VOL_LIBRARY
 		  COIN_VOL_LIBRARY
+		)
 		IF(COIN_FOUND)
 		  SET(LEMON_HAVE_LP TRUE)
 		  SET(LEMON_HAVE_MIP TRUE)
 		  SET(LEMON_HAVE_CLP TRUE)
 		  SET(LEMON_HAVE_CBC TRUE)
 		ENDIF(COIN_FOUND)

cmake/FindCPLEX.cmake

Show inline comments

 		SET(CPLEX_ROOT_DIR "" CACHE PATH "CPLEX root directory")
 		FIND_PATH(CPLEX_INCLUDE_DIR
 		  ilcplex/cplex.h
 		  PATHS "C:/ILOG/CPLEX91/include"
 		  PATHS "/opt/ilog/cplex91/include"
 		  HINTS ${CPLEX_ROOT_DIR}/include
+		)
 		FIND_LIBRARY(CPLEX_LIBRARY
 		  cplex91
 		  PATHS "C:/ILOG/CPLEX91/lib/msvc7/stat_mda"
 		  PATHS "/opt/ilog/cplex91/bin"
 		  HINTS ${CPLEX_ROOT_DIR}/bin
+		)
 		INCLUDE(FindPackageHandleStandardArgs)
 		FIND_PACKAGE_HANDLE_STANDARD_ARGS(CPLEX DEFAULT_MSG CPLEX_LIBRARY CPLEX_INCLUDE_DIR)
 		FIND_PATH(CPLEX_BIN_DIR
 		  cplex91.dll
 		  PATHS "C:/ILOG/CPLEX91/bin/x86_win32"
+		)
 		IF(CPLEX_FOUND)
 		  SET(CPLEX_INCLUDE_DIRS ${CPLEX_INCLUDE_DIR})
 		  SET(CPLEX_LIBRARIES ${CPLEX_LIBRARY})
 		  IF(CMAKE_SYSTEM_NAME STREQUAL "Linux")
 		    SET(CPLEX_LIBRARIES "${CPLEX_LIBRARIES};m;pthread")
 		  ENDIF(CMAKE_SYSTEM_NAME STREQUAL "Linux")
 		ENDIF(CPLEX_FOUND)
 		MARK_AS_ADVANCED(CPLEX_LIBRARY CPLEX_INCLUDE_DIR CPLEX_BIN_DIR)
 		IF(CPLEX_FOUND)
 		  SET(LEMON_HAVE_LP TRUE)
 		  SET(LEMON_HAVE_MIP TRUE)
 		  SET(LEMON_HAVE_CPLEX TRUE)
 		ENDIF(CPLEX_FOUND)

cmake/FindGLPK.cmake

Show inline comments

 		SET(GLPK_ROOT_DIR "" CACHE PATH "GLPK root directory")
 		SET(GLPK_REGKEY "[HKEY_LOCAL_MACHINE\\SOFTWARE\\GnuWin32\\Glpk;InstallPath]")
 		GET_FILENAME_COMPONENT(GLPK_ROOT_PATH ${GLPK_REGKEY} ABSOLUTE)
 		FIND_PATH(GLPK_INCLUDE_DIR
 		  glpk.h
 		  PATHS ${GLPK_REGKEY}/include
 		  HINTS ${GLPK_ROOT_DIR}/include
+		)
 		FIND_LIBRARY(GLPK_LIBRARY
 		  glpk
 		  PATHS ${GLPK_REGKEY}/lib
 		  HINTS ${GLPK_ROOT_DIR}/lib
+		)
 		IF(GLPK_INCLUDE_DIR AND GLPK_LIBRARY)
 		  FILE(READ ${GLPK_INCLUDE_DIR}/glpk.h GLPK_GLPK_H)
 		  STRING(REGEX MATCH "define[ ]+GLP_MAJOR_VERSION[ ]+[0-9]+" GLPK_MAJOR_VERSION_LINE "${GLPK_GLPK_H}")
 		  STRING(REGEX REPLACE "define[ ]+GLP_MAJOR_VERSION[ ]+([0-9]+)" "\\1" GLPK_VERSION_MAJOR "${GLPK_MAJOR_VERSION_LINE}")
 		  STRING(REGEX MATCH "define[ ]+GLP_MINOR_VERSION[ ]+[0-9]+" GLPK_MINOR_VERSION_LINE "${GLPK_GLPK_H}")
 		  STRING(REGEX REPLACE "define[ ]+GLP_MINOR_VERSION[ ]+([0-9]+)" "\\1" GLPK_VERSION_MINOR "${GLPK_MINOR_VERSION_LINE}")
 		  SET(GLPK_VERSION_STRING "${GLPK_VERSION_MAJOR}.${GLPK_VERSION_MINOR}")
 		  IF(GLPK_FIND_VERSION)
 		    IF(GLPK_FIND_VERSION_COUNT GREATER 2)
 		      MESSAGE(SEND_ERROR "unexpected version string")
 		    ENDIF(GLPK_FIND_VERSION_COUNT GREATER 2)
 		    MATH(EXPR GLPK_REQUESTED_VERSION "${GLPK_FIND_VERSION_MAJOR}*100 + ${GLPK_FIND_VERSION_MINOR}")
 		    MATH(EXPR GLPK_FOUND_VERSION "${GLPK_VERSION_MAJOR}*100 + ${GLPK_VERSION_MINOR}")
 		    IF(GLPK_FOUND_VERSION LESS GLPK_REQUESTED_VERSION)
 		      SET(GLPK_PROPER_VERSION_FOUND FALSE)
 		    ELSE(GLPK_FOUND_VERSION LESS GLPK_REQUESTED_VERSION)
 		      SET(GLPK_PROPER_VERSION_FOUND TRUE)
 		    ENDIF(GLPK_FOUND_VERSION LESS GLPK_REQUESTED_VERSION)
 		  ELSE(GLPK_FIND_VERSION)
 		    SET(GLPK_PROPER_VERSION_FOUND TRUE)
 		  ENDIF(GLPK_FIND_VERSION)
 		ENDIF(GLPK_INCLUDE_DIR AND GLPK_LIBRARY)
 		INCLUDE(FindPackageHandleStandardArgs)
 		FIND_PACKAGE_HANDLE_STANDARD_ARGS(GLPK DEFAULT_MSG GLPK_LIBRARY GLPK_INCLUDE_DIR GLPK_PROPER_VERSION_FOUND)
 		IF(GLPK_FOUND)
 		  SET(GLPK_INCLUDE_DIRS ${GLPK_INCLUDE_DIR})
 		  SET(GLPK_LIBRARIES ${GLPK_LIBRARY})
 		  SET(GLPK_BIN_DIR ${GLPK_ROOT_PATH}/bin)
 		ENDIF(GLPK_FOUND)
 		MARK_AS_ADVANCED(GLPK_LIBRARY GLPK_INCLUDE_DIR GLPK_BIN_DIR)
 		IF(GLPK_FOUND)
 		  SET(LEMON_HAVE_LP TRUE)
 		  SET(LEMON_HAVE_MIP TRUE)
 		  SET(LEMON_HAVE_GLPK TRUE)
 		ENDIF(GLPK_FOUND)

cmake/LEMONConfig.cmake.in

Show inline comments

 		SET(LEMON_INCLUDE_DIR "@CMAKE_INSTALL_PREFIX@/include" CACHE PATH "LEMON include directory")
 		SET(LEMON_INCLUDE_DIRS "${LEMON_INCLUDE_DIR}")
 		IF(UNIX)
 		  SET(LEMON_LIB_NAME "libemon.a")
 		ELSEIF(WIN32)
 		  SET(LEMON_LIB_NAME "lemon.lib")
 		ENDIF(UNIX)
 		SET(LEMON_LIBRARY "@CMAKE_INSTALL_PREFIX@/lib/${LEMON_LIB_NAME}" CACHE FILEPATH "LEMON library")
 		SET(LEMON_LIBRARIES "${LEMON_LIBRARY}")
 		MARK_AS_ADVANCED(LEMON_LIBRARY LEMON_INCLUDE_DIR)

doc/images/bipartite_matching.eps

Show inline comments

 		%!PS-Adobe-3.0 EPSF-3.0
 		%%BoundingBox: 15 18 829 570
 		%%HiResBoundingBox: 15.1913 18.4493 828.078 569.438
 		%%Creator: Karbon14 EPS Exportfilter 0.5
 		%%CreationDate: (04/15/06 15:20:26)
 		%%For: (Balazs Dezso) ()
 		%%Title: ()
 		/N {newpath} def
 		/C {closepath} def
 		/m {moveto} def
 		/c {curveto} def
 		/l {lineto} def
 		/s {stroke} def
 		/f {fill} def
 		/w {setlinewidth} def
 		/d {setdash} def
 		/r {setrgbcolor} def
 		/S {gsave} def
 		/R {grestore} def
+		N
 .402 32.047 m
 .945 293.946 814.484 555.844 814.484 555.844 c
 		[] 0 d 1 0 0 r 3.92814 w s
+		N
 .012 32.047 m
 .465 293.946 735.918 555.844 735.918 555.844 c
 		[] 0 d 0 0 0 r 1.96407 w s
+		N
 .492 32.047 m
 .703 293.946 735.918 555.844 735.918 555.844 c
 		[] 0 d 0 0 0 r 1.96407 w s
+		N
 .832 32.047 m
 .375 293.946 735.918 555.844 735.918 555.844 c
 		[] 0 d 0 0 0 r 1.96407 w s
+		N
 .355 32.047 m
 .637 293.946 735.918 555.844 735.918 555.844 c
 		[] 0 d 1 0 0 r 3.92814 w s
+		N
 .25 555.844 m
 .633 293.946 749.012 32.047 749.012 32.047 c
 		[] 0 d 0 0 0 r 1.96407 w s
+		N
 .016 555.844 m
 .516 293.946 749.012 32.047 749.012 32.047 c
 		[] 0 d 1 0 0 r 3.92814 w s
+		N
 .535 32.047 m
 .894 293.946 644.25 555.844 644.25 555.844 c
 		[] 0 d 0 0 0 r 1.96407 w s
+		N
 .453 555.844 m
 .992 293.946 683.535 32.047 683.535 32.047 c
 		[] 0 d 0 0 0 r 1.96407 w s
+		N
 .7853 555.844 m
 .16 293.946 683.535 32.047 683.535 32.047 c
 		[] 0 d 1 0 0 r 3.92814 w s
+		N
 .492 32.047 m
 .039 293.946 552.586 555.844 552.586 555.844 c
 		[] 0 d 1 0 0 r 3.92814 w s
+		N
 .875 32.047 m
 .613 293.946 382.351 555.844 382.351 555.844 c
 		[] 0 d 1 0 0 r 3.92814 w s
+		N
 .355 32.047 m
 .855 293.946 382.351 555.844 382.351 555.844 c
 		[] 0 d 0 0 0 r 1.96407 w s
+		N
 .687 555.844 m
 .805 293.946 460.922 32.047 460.922 32.047 c
 		[] 0 d 1 0 0 r 3.92814 w s
+		N
 .453 555.844 m
 .687 293.946 460.922 32.047 460.922 32.047 c
 		[] 0 d 0 0 0 r 1.96407 w s
+		N
 .832 32.047 m
 .64 293.946 120.453 555.844 120.453 555.844 c
 		[] 0 d 1 0 0 r 3.92814 w s
+		N
 .6913 555.844 m
 .6913 555.844 l
 .6913 548.614 21.5553 542.75 28.7853 542.75 c
 .0163 542.75 41.8833 548.614 41.8833 555.844 c
 .8833 563.075 36.0163 568.938 28.7853 568.938 c
 .5553 568.938 15.6913 563.075 15.6913 555.844 c
 .6913 555.844 l
+		C
 		S 0 0 0 r f R
+		N
 .8833 555.844 m
 .8833 555.844 l
 .8833 549.27 22.2113 543.942 28.7853 543.942 c
 .3593 543.942 40.6913 549.27 40.6913 555.844 c
 .6913 562.418 35.3593 567.747 28.7853 567.747 c
 .2113 567.747 16.8833 562.418 16.8833 555.844 c
 .8833 555.844 l
+		C
 		S 1 0.5 1 r f R
+		N
 .355 555.844 m
 .355 555.844 l
 .355 548.614 113.223 542.75 120.453 542.75 c
 .683 542.75 133.547 548.614 133.547 555.844 c
 .547 563.075 127.683 568.938 120.453 568.938 c
 .223 568.938 107.355 563.075 107.355 555.844 c
 .355 555.844 l
+		C
 		S 0 0 0 r f R
+		N
 .547 555.844 m
 .547 555.844 l
 .547 549.27 113.879 543.942 120.453 543.942 c
 .027 543.942 132.355 549.27 132.355 555.844 c
 .355 562.418 127.027 567.747 120.453 567.747 c
 .879 567.747 108.547 562.418 108.547 555.844 c
 .547 555.844 l
+		C
 		S 1 0 1 r f R
+		N
 .019 555.844 m
 .019 555.844 l
 .019 548.614 204.887 542.75 212.117 542.75 c
 .348 542.75 225.211 548.614 225.211 555.844 c
 .211 563.075 219.348 568.938 212.117 568.938 c
 .887 568.938 199.019 563.075 199.019 555.844 c
 .019 555.844 l
+		C
 		S 0 0 0 r f R
+		N
 .211 555.844 m
 .211 555.844 l
 .211 549.27 205.543 543.942 212.117 543.942 c
 .691 543.942 224.019 549.27 224.019 555.844 c
 .019 562.418 218.691 567.747 212.117 567.747 c
 .543 567.747 200.211 562.418 200.211 555.844 c
 .211 555.844 l
+		C
 		S 1 0.5 1 r f R
+		N
 .59 555.844 m
 .59 555.844 l
 .59 548.614 283.457 542.75 290.687 542.75 c
 .918 542.75 303.781 548.614 303.781 555.844 c
 .781 563.075 297.918 568.938 290.687 568.938 c
 .457 568.938 277.59 563.075 277.59 555.844 c
 .59 555.844 l
+		C
 		S 0 0 0 r f R
+		N
 .781 555.844 m
 .781 555.844 l
 .781 549.27 284.113 543.942 290.687 543.942 c
 .262 543.942 302.59 549.27 302.59 555.844 c
 .59 562.418 297.262 567.747 290.687 567.747 c
 .113 567.747 278.781 562.418 278.781 555.844 c
 .781 555.844 l
+		C
 		S 1 0 1 r f R
+		N
 .258 555.844 m
 .258 555.844 l
 .258 548.614 375.121 542.75 382.351 542.75 c
 .582 542.75 395.445 548.614 395.445 555.844 c
 .445 563.075 389.582 568.938 382.351 568.938 c
 .121 568.938 369.258 563.075 369.258 555.844 c
 .258 555.844 l
+		C
 		S 0 0 0 r f R
+		N
 .445 555.844 m
 .445 555.844 l
 .445 549.27 375.777 543.942 382.351 543.942 c
 .926 543.942 394.258 549.27 394.258 555.844 c
 .258 562.418 388.926 567.747 382.351 567.747 c
 .777 567.747 370.445 562.418 370.445 555.844 c
 .445 555.844 l
+		C
 		S 1 0 1 r f R
+		N
 .922 555.844 m
 .922 555.844 l
 .922 548.614 466.785 542.75 474.016 542.75 c
 .246 542.75 487.109 548.614 487.109 555.844 c
 .109 563.075 481.246 568.938 474.016 568.938 c
 .785 568.938 460.922 563.075 460.922 555.844 c
 .922 555.844 l
+		C
 		S 0 0 0 r f R
+		N
 .113 555.844 m
 .113 555.844 l
 .113 549.27 467.441 543.942 474.016 543.942 c
 .59 543.942 485.922 549.27 485.922 555.844 c
 .922 562.418 480.59 567.747 474.016 567.747 c
 .441 567.747 462.113 562.418 462.113 555.844 c
 .113 555.844 l
+		C
 		S 1 0.5 1 r f R
+		N
 .492 555.844 m
 .492 555.844 l
 .492 548.614 545.355 542.75 552.586 542.75 c
 .816 542.75 565.68 548.614 565.68 555.844 c
 .68 563.075 559.816 568.938 552.586 568.938 c
 .355 568.938 539.492 563.075 539.492 555.844 c
 .492 555.844 l
+		C
 		S 0 0 0 r f R
+		N
 .683 555.844 m
 .683 555.844 l
 .683 549.27 546.012 543.942 552.586 543.942 c
 .16 543.942 564.492 549.27 564.492 555.844 c
 .492 562.418 559.16 567.747 552.586 567.747 c
 .012 567.747 540.683 562.418 540.683 555.844 c
 .683 555.844 l
+		C
 		S 1 0 1 r f R
+		N
 .156 555.844 m
 .156 555.844 l
 .156 548.614 637.019 542.75 644.25 542.75 c
 .48 542.75 657.348 548.614 657.348 555.844 c
 .348 563.075 651.48 568.938 644.25 568.938 c
 .019 568.938 631.156 563.075 631.156 555.844 c
 .156 555.844 l
+		C
 		S 0 0 0 r f R
+		N
 .348 555.844 m
 .348 555.844 l
 .348 549.27 637.676 543.942 644.25 543.942 c
 .824 543.942 656.156 549.27 656.156 555.844 c
 .156 562.418 650.824 567.747 644.25 567.747 c
 .676 567.747 632.348 562.418 632.348 555.844 c
 .348 555.844 l
+		C
 		S 1 0.5 1 r f R
+		N
 .82 555.844 m
 .82 555.844 l
 .82 548.614 728.687 542.75 735.918 542.75 c
 .149 542.75 749.012 548.614 749.012 555.844 c
 .012 563.075 743.149 568.938 735.918 568.938 c
 .687 568.938 722.82 563.075 722.82 555.844 c
 .82 555.844 l
+		C
 		S 0 0 0 r f R
+		N
 .012 555.844 m
 .012 555.844 l
 .012 549.27 729.344 543.942 735.918 543.942 c
 .492 543.942 747.82 549.27 747.82 555.844 c
 .82 562.418 742.492 567.747 735.918 567.747 c
 .344 567.747 724.012 562.418 724.012 555.844 c
 .012 555.844 l
+		C
 		S 1 0 1 r f R
+		N
 .391 555.844 m
 .391 555.844 l
 .391 548.614 807.254 542.75 814.484 542.75 c
 .715 542.75 827.578 548.614 827.578 555.844 c
 .578 563.075 821.715 568.938 814.484 568.938 c
 .254 568.938 801.391 563.075 801.391 555.844 c
 .391 555.844 l
+		C
 		S 0 0 0 r f R
+		N
 .582 555.844 m
 .582 555.844 l
 .582 549.27 807.91 543.942 814.484 543.942 c
 .059 543.942 826.387 549.27 826.387 555.844 c
 .387 562.418 821.059 567.747 814.484 567.747 c
 .91 567.747 802.582 562.418 802.582 555.844 c
 .582 555.844 l
+		C
 		S 1 0 1 r f R
+		N
 .6913 32.047 m
 .6913 32.047 l
 .6913 24.8165 21.5553 18.9493 28.7853 18.9493 c
 .0163 18.9493 41.8833 24.8165 41.8833 32.047 c
 .8833 39.2775 36.0163 45.1407 28.7853 45.1407 c
 .5553 45.1407 15.6913 39.2775 15.6913 32.047 c
 .6913 32.047 l
+		C
 		S 0 0 0 r f R
+		N
 .8833 32.047 m
 .8833 32.047 l
 .8833 25.4728 22.2113 20.1407 28.7853 20.1407 c
 .3593 20.1407 40.6913 25.4728 40.6913 32.047 c
 .6913 38.6212 35.3593 43.9493 28.7853 43.9493 c
 .2113 43.9493 16.8833 38.6212 16.8833 32.047 c
 .8833 32.047 l
+		C
 		S 0.5 0.5 1 r f R
+		N
 .2623 32.047 m
 .2623 32.047 l
 .2623 24.8165 100.125 18.9493 107.355 18.9493 c
 .586 18.9493 120.453 24.8165 120.453 32.047 c
 .453 39.2775 114.586 45.1407 107.355 45.1407 c
 .125 45.1407 94.2623 39.2775 94.2623 32.047 c
 .2623 32.047 l
+		C
 		S 0 0 0 r f R
+		N
 .4533 32.047 m
 .4533 32.047 l
 .4533 25.4728 100.781 20.1407 107.355 20.1407 c
 .93 20.1407 119.262 25.4728 119.262 32.047 c
 .262 38.6212 113.93 43.9493 107.355 43.9493 c
 .781 43.9493 95.4533 38.6212 95.4533 32.047 c
 .4533 32.047 l
+		C
 		S 0.5 0.5 1 r f R
+		N
 .734 32.047 m
 .734 32.047 l
 .734 24.8165 165.601 18.9493 172.832 18.9493 c
 .062 18.9493 185.926 24.8165 185.926 32.047 c
 .926 39.2775 180.062 45.1407 172.832 45.1407 c
 .601 45.1407 159.734 39.2775 159.734 32.047 c
 .734 32.047 l
+		C
 		S 0 0 0 r f R
+		N
 .926 32.047 m
 .926 32.047 l
 .926 25.4728 166.258 20.1407 172.832 20.1407 c
 .406 20.1407 184.734 25.4728 184.734 32.047 c
 .734 38.6212 179.406 43.9493 172.832 43.9493 c
 .258 43.9493 160.926 38.6212 160.926 32.047 c
 .926 32.047 l
+		C
 		S 0.5 0.5 1 r f R
+		N
 .305 32.047 m
 .305 32.047 l
 .305 24.8165 244.172 18.9493 251.402 18.9493 c
 .633 18.9493 264.496 24.8165 264.496 32.047 c
 .496 39.2775 258.633 45.1407 251.402 45.1407 c
 .172 45.1407 238.305 39.2775 238.305 32.047 c
 .305 32.047 l
+		C
 		S 0 0 0 r f R
+		N
 .496 32.047 m
 .496 32.047 l
 .496 25.4728 244.828 20.1407 251.402 20.1407 c
 .976 20.1407 263.305 25.4728 263.305 32.047 c
 .305 38.6212 257.976 43.9493 251.402 43.9493 c
 .828 43.9493 239.496 38.6212 239.496 32.047 c
 .496 32.047 l
+		C
 		S 0.5 0.5 1 r f R
+		N
 .781 32.047 m
 .781 32.047 l
 .781 24.8165 309.644 18.9493 316.875 18.9493 c
 .105 18.9493 329.973 24.8165 329.973 32.047 c
 .973 39.2775 324.105 45.1407 316.875 45.1407 c
 .644 45.1407 303.781 39.2775 303.781 32.047 c
 .781 32.047 l
+		C
 		S 0 0 0 r f R
+		N
 .973 32.047 m
 .973 32.047 l
 .973 25.4728 310.301 20.1407 316.875 20.1407 c
 .449 20.1407 328.781 25.4728 328.781 32.047 c
 .781 38.6212 323.449 43.9493 316.875 43.9493 c
 .301 43.9493 304.973 38.6212 304.973 32.047 c
 .973 32.047 l
+		C
 		S 0.5 0.5 1 r f R
+		N
 .351 32.047 m
 .351 32.047 l
 .351 24.8165 388.215 18.9493 395.445 18.9493 c
 .676 18.9493 408.543 24.8165 408.543 32.047 c
 .543 39.2775 402.676 45.1407 395.445 45.1407 c
 .215 45.1407 382.351 39.2775 382.351 32.047 c
 .351 32.047 l
+		C
 		S 0 0 0 r f R
+		N
 .543 32.047 m
 .543 32.047 l
 .543 25.4728 388.871 20.1407 395.445 20.1407 c
 .019 20.1407 407.351 25.4728 407.351 32.047 c
 .351 38.6212 402.019 43.9493 395.445 43.9493 c
 .871 43.9493 383.543 38.6212 383.543 32.047 c
 .543 32.047 l
+		C
 		S 0.5 0.5 1 r f R
+		N
 .828 32.047 m
 .828 32.047 l
 .828 24.8165 453.691 18.9493 460.922 18.9493 c
 .152 18.9493 474.016 24.8165 474.016 32.047 c
 .016 39.2775 468.152 45.1407 460.922 45.1407 c
 .691 45.1407 447.828 39.2775 447.828 32.047 c
 .828 32.047 l
+		C
 		S 0 0 0 r f R
+		N
 .016 32.047 m
 .016 32.047 l
 .016 25.4728 454.348 20.1407 460.922 20.1407 c
 .496 20.1407 472.824 25.4728 472.824 32.047 c
 .824 38.6212 467.496 43.9493 460.922 43.9493 c
 .348 43.9493 449.016 38.6212 449.016 32.047 c
 .016 32.047 l
+		C
 		S 0.5 0.5 1 r f R
+		N
 .394 32.047 m
 .394 32.047 l
 .394 24.8165 532.262 18.9493 539.492 18.9493 c
 .723 18.9493 552.586 24.8165 552.586 32.047 c
 .586 39.2775 546.723 45.1407 539.492 45.1407 c
 .262 45.1407 526.394 39.2775 526.394 32.047 c
 .394 32.047 l
+		C
 		S 0 0 0 r f R
+		N
 .586 32.047 m
 .586 32.047 l
 .586 25.4728 532.918 20.1407 539.492 20.1407 c
 .066 20.1407 551.394 25.4728 551.394 32.047 c
 .394 38.6212 546.066 43.9493 539.492 43.9493 c
 .918 43.9493 527.586 38.6212 527.586 32.047 c
 .586 32.047 l
+		C
 		S 0.5 0.5 1 r f R
+		N
 .871 32.047 m
 .871 32.047 l
 .871 24.8165 597.734 18.9493 604.965 18.9493 c
 .195 18.9493 618.062 24.8165 618.062 32.047 c
 .062 39.2775 612.195 45.1407 604.965 45.1407 c
 .734 45.1407 591.871 39.2775 591.871 32.047 c
 .871 32.047 l
+		C
 		S 0 0 0 r f R
+		N
 .062 32.047 m
 .062 32.047 l
 .062 25.4728 598.39 20.1407 604.965 20.1407 c
 .539 20.1407 616.871 25.4728 616.871 32.047 c
 .871 38.6212 611.539 43.9493 604.965 43.9493 c
 .39 43.9493 593.062 38.6212 593.062 32.047 c
 .062 32.047 l
+		C
 		S 0.5 0.5 1 r f R
+		N
 .441 32.047 m
 .441 32.047 l
 .441 24.8165 676.305 18.9493 683.535 18.9493 c
 .766 18.9493 696.633 24.8165 696.633 32.047 c
 .633 39.2775 690.766 45.1407 683.535 45.1407 c
 .305 45.1407 670.441 39.2775 670.441 32.047 c
 .441 32.047 l
+		C
 		S 0 0 0 r f R
+		N
 .633 32.047 m
 .633 32.047 l
 .633 25.4728 676.961 20.1407 683.535 20.1407 c
 .109 20.1407 695.441 25.4728 695.441 32.047 c
 .441 38.6212 690.109 43.9493 683.535 43.9493 c
 .961 43.9493 671.633 38.6212 671.633 32.047 c
 .633 32.047 l
+		C
 		S 0 0 1 r f R
+		N
 .918 32.047 m
 .918 32.047 l
 .918 24.8165 741.781 18.9493 749.012 18.9493 c
 .242 18.9493 762.106 24.8165 762.106 32.047 c
 .106 39.2775 756.242 45.1407 749.012 45.1407 c
 .781 45.1407 735.918 39.2775 735.918 32.047 c
 .918 32.047 l
+		C
 		S 0 0 0 r f R
+		N
 .105 32.047 m
 .105 32.047 l
 .105 25.4728 742.437 20.1407 749.012 20.1407 c
 .586 20.1407 760.914 25.4728 760.914 32.047 c
 .914 38.6212 755.586 43.9493 749.012 43.9493 c
 .437 43.9493 737.105 38.6212 737.105 32.047 c
 .105 32.047 l
+		C
 		S 0 0 1 r f R
+		N
 .391 32.047 m
 .391 32.047 l
 .391 24.8165 807.254 18.9493 814.484 18.9493 c
 .715 18.9493 827.578 24.8165 827.578 32.047 c
 .578 39.2775 821.715 45.1407 814.484 45.1407 c
 .254 45.1407 801.391 39.2775 801.391 32.047 c
 .391 32.047 l
+		C
 		S 0 0 0 r f R
+		N
 .582 32.047 m
 .582 32.047 l
 .582 25.4728 807.91 20.1407 814.484 20.1407 c
 .059 20.1407 826.387 25.4728 826.387 32.047 c
 .387 38.6212 821.059 43.9493 814.484 43.9493 c
 .91 43.9493 802.582 38.6212 802.582 32.047 c
 .582 32.047 l
+		C
 		S 0.5 0.5 1 r f R
 		%%EOF

doc/images/bipartite_partitions.eps

Show inline comments

 		%!PS-Adobe-2.0 EPSF-2.0
 		%%Creator: LEMON, graphToEps()
 		%%CreationDate: Tue Nov 15 16:51:43 2005
 		%%BoundingBox: 0 0 842 596
 		%%EndComments
 		/lb { setlinewidth setrgbcolor newpath moveto
 2 roll 1 index 1 index curveto stroke } bind def
 		/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
 		/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
 		/sq { newpath 2 index 1 index add 2 index 2 index add moveto
 index 1 index sub 2 index 2 index add lineto
 index 1 index sub 2 index 2 index sub lineto
 index 1 index add 2 index 2 index sub lineto
 		      closepath pop pop pop} bind def
 		/di { newpath 2 index 1 index add 2 index moveto
 index             2 index 2 index add lineto
 index 1 index sub 2 index             lineto
 index             2 index 2 index sub lineto
 		      closepath pop pop pop} bind def
 		/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
 		     setrgbcolor 1.1 div c fill
 		   } bind def
 		/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
 		     setrgbcolor 1.1 div sq fill
 		   } bind def
 		/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
 		     setrgbcolor 1.1 div di fill
 		   } bind def
 		/arrl 1 def
 		/arrw 0.3 def
 		/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
 		/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
 		       /w exch def /len exch def
 		       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
 		       len w sub arrl sub dx dy lrl
 		       arrw dy dx neg lrl
 		       dx arrl w add mul dy w 2 div arrw add mul sub
 		       dy arrl w add mul dx w 2 div arrw add mul add rlineto
 		       dx arrl w add mul neg dy w 2 div arrw add mul sub
 		       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
 		       arrw dy dx neg lrl
 		       len w sub arrl sub neg dx dy lrl
 		       closepath fill } bind def
 		/cshow { 2 index 2 index moveto dup stringwidth pop
 		         neg 2 div fosi .35 mul neg rmoveto show pop pop} def
 		gsave
 rotate
 -842 translate
 .6378 15 translate
 .389093 dup scale
 rotate
 .47 -613.138 translate
 		%Edges:
 		gsave
 .857 -446.322 296.569 -487.43 79.2808 -528.539 0 0 0 2 lb
 .857 -446.322 575.52 -315.655 637.183 -184.989 0 0 0 2 lb
 .468 566.711 494.771 434.577 596.074 302.442 0 0 0 2 lb
 .468 566.711 155.625 579.925 -82.2171 593.138 0 0 0 2 lb
 .468 566.711 251.056 450.726 108.644 334.741 0 0 0 2 lb
 .153 52.8539 732.613 177.648 596.074 302.442 0 0 0 2 lb
 .153 52.8539 753.168 -66.0676 637.183 -184.989 0 0 0 2 lb
 		-82.2171 593.138 -91.0261 346.487 -99.8351 99.8351 0 0 0 2 lb
 		-663.61 546.157 -753.168 394.936 -842.726 243.715 0 0 0 2 lb
 		-663.61 546.157 -574.052 437.513 -484.494 328.869 0 0 0 2 lb
 		-1077.63 161.498 -960.178 202.606 -842.726 243.715 0 0 0 2 lb
 		-1077.63 161.498 -968.987 66.0674 -860.344 -29.3633 0 0 0 2 lb
 		-1177.47 -234.906 -1029.18 -381.722 -880.898 -528.539 0 0 0 2 lb
 		-1177.47 -234.906 -1018.91 -132.135 -860.344 -29.3633 0 0 0 2 lb
 		-880.898 -528.539 -744.359 -387.595 -607.82 -246.651 0 0 0 2 lb
 		-499.175 -499.175 -355.295 -475.685 -211.415 -452.194 0 0 0 2 lb
 		-499.175 -499.175 -553.498 -372.913 -607.82 -246.651 0 0 0 2 lb
 		-499.175 -499.175 -386.587 -315.087 -274 -131 0 0 0 2 lb
 .2808 -528.539 -66.0671 -490.366 -211.415 -452.194 0 0 0 2 lb
 .183 -184.989 421.363 -253.993 205.543 -322.996 0 0 0 2 lb
 .543 -322.996 162.966 -226.097 120.389 -129.198 0 0 0 2 lb
 .34 88.0898 259.865 -20.5541 120.389 -129.198 0 0 0 2 lb
 .34 88.0898 253.992 211.415 108.644 334.741 0 0 0 2 lb
 		-842.726 243.715 -471.281 171.775 -99.8351 99.8351 0 0 0 2 lb
 		-842.726 243.715 -558.363 56.3575 -274 -131 0 0 0 2 lb
 		-860.344 -29.3633 -734.082 -138.007 -607.82 -246.651 0 0 0 2 lb
 		-211.415 -452.194 -45.513 -290.696 120.389 -129.198 0 0 0 2 lb
 		-99.8351 99.8351 4.40445 217.288 108.644 334.741 0 0 0 2 lb
 		-99.8351 99.8351 -292.165 214.352 -484.494 328.869 0 0 0 2 lb
 .389 -129.198 -76.8055 -130.099 -274 -131 0 0 0 2 lb
 		grestore
 		%Nodes:
 		gsave
 		-274 -131 20 1 0 0 nc
 		-607.82 -246.651 20 1 0 0 nc
 		-484.494 328.869 20 0 0 1 nc
 .644 334.741 20 0 0 1 nc
 .389 -129.198 20 0 0 1 nc
 		-99.8351 99.8351 20 1 0 0 nc
 		-211.415 -452.194 20 1 0 0 nc
 		-860.344 -29.3633 20 0 0 1 nc
 		-842.726 243.715 20 0 0 1 nc
 .34 88.0898 20 1 0 0 nc
 .543 -322.996 20 1 0 0 nc
 .183 -184.989 20 0 0 1 nc
 .2808 -528.539 20 0 0 1 nc
 		-499.175 -499.175 20 0 0 1 nc
 		-880.898 -528.539 20 0 0 1 nc
 		-1177.47 -234.906 20 1 0 0 nc
 		-1077.63 161.498 20 1 0 0 nc
 		-663.61 546.157 20 1 0 0 nc
 		-82.2171 593.138 20 0 0 1 nc
 .074 302.442 20 0 0 1 nc
 .153 52.8539 20 1 0 0 nc
 .468 566.711 20 1 0 0 nc
 .857 -446.322 20 1 0 0 nc
 		grestore
 		grestore
 		showpage

doc/images/connected_components.eps

Show inline comments

 		%!PS-Adobe-2.0 EPSF-2.0
 		%%Creator: LEMON, graphToEps()
 		%%CreationDate: Fri Nov  4 13:47:12 2005
 		%%BoundingBox: 0 0 842 596
 		%%EndComments
 		/lb { setlinewidth setrgbcolor newpath moveto
 2 roll 1 index 1 index curveto stroke } bind def
 		/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
 		/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
 		/sq { newpath 2 index 1 index add 2 index 2 index add moveto
 index 1 index sub 2 index 2 index add lineto
 index 1 index sub 2 index 2 index sub lineto
 index 1 index add 2 index 2 index sub lineto
 		      closepath pop pop pop} bind def
 		/di { newpath 2 index 1 index add 2 index moveto
 index             2 index 2 index add lineto
 index 1 index sub 2 index             lineto
 index             2 index 2 index sub lineto
 		      closepath pop pop pop} bind def
 		/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
 		     setrgbcolor 1.1 div c fill
 		   } bind def
 		/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
 		     setrgbcolor 1.1 div sq fill
 		   } bind def
 		/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
 		     setrgbcolor 1.1 div di fill
 		   } bind def
 		/arrl 1 def
 		/arrw 0.3 def
 		/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
 		/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
 		       /w exch def /len exch def
 		       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
 		       len w sub arrl sub dx dy lrl
 		       arrw dy dx neg lrl
 		       dx arrl w add mul dy w 2 div arrw add mul sub
 		       dy arrl w add mul dx w 2 div arrw add mul add rlineto
 		       dx arrl w add mul neg dy w 2 div arrw add mul sub
 		       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
 		       arrw dy dx neg lrl
 		       len w sub arrl sub neg dx dy lrl
 		       closepath fill } bind def
 		/cshow { 2 index 2 index moveto dup stringwidth pop
 		         neg 2 div fosi .35 mul neg rmoveto show pop pop} def
 		gsave
 rotate
 -842 translate
 .0944 15 translate
 .434694 dup scale
 rotate
 .856 -588.349 translate
 		%Edges:
 		gsave
 .035 177.301 622.149 225.748 670.264 274.195 0 0 0 2 lb
 .579 115.483 682.421 194.839 670.264 274.195 0 0 0 2 lb
 .402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 0 2 lb
 .402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 0 2 lb
 .403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 0 2 lb
 .584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 0 2 lb
 .584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 0 2 lb
 .037 -88.514 417.946 -142.604 397.855 -196.694 0 0 0 2 lb
 .037 -88.514 402.492 -99.332 366.947 -110.15 0 0 0 2 lb
 .855 -196.694 382.401 -153.422 366.947 -110.15 0 0 0 2 lb
 .947 -110.15 319.038 -142.604 271.13 -175.058 0 0 0 2 lb
 .13 -175.058 274.221 -213.694 277.311 -252.33 0 0 0 2 lb
 .13 -175.058 238.675 -190.512 206.221 -205.967 0 0 0 2 lb
 .311 -252.33 241.766 -229.149 206.221 -205.967 0 0 0 2 lb
 		-840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0 0 2 lb
 		-579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0 2 lb
 		-579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0 2 lb
 		-767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0 2 lb
 .312 201.403 946.592 42.798 986.873 -115.807 0 0 0 2 lb
 .312 201.403 834.562 91.8901 762.812 -17.6227 0 0 0 2 lb
 .873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 0 2 lb
 		-470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0 0 0 2 lb
 .945 521.129 208.955 541.269 -5.03507 561.41 0 0 0 2 lb
 .945 521.129 376.371 417.911 329.797 314.692 0 0 0 2 lb
 .945 521.129 474.554 276.928 526.164 32.7279 0 0 0 2 lb
 		-5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 0 2 lb
 .797 314.692 130.912 317.209 -67.9734 319.727 0 0 0 2 lb
 		-67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 0 2 lb
 .812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 0 2 lb
 .812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 0 2 lb
 .164 32.7279 470.779 -128.394 415.393 -289.516 0 0 0 2 lb
 .084 -307.139 572.738 -298.327 415.393 -289.516 0 0 0 2 lb
 .393 -289.516 173.71 -318.468 -67.9734 -347.42 0 0 0 2 lb
 		-67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 0 2 lb
 		-67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 0 2 lb
 		-309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 0 2 lb
 		-323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 0 2 lb
 		-26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 0 2 lb
 		-26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 0 2 lb
 		-26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 0 2 lb
 		-26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 0 2 lb
 .407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 0 2 lb
 		-262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 0 2 lb
 		-262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 0 2 lb
 		-13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 0 2 lb
 		-180.397 245.045 -142.256 345.099 -132.697 451.748 0 0 0 2 lb
 		-180.397 245.045 -170.838 351.694 -132.697 451.748 0 0 0 2 lb
 		-416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 0 2 lb
 		-416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 0 2 lb
 		-132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 0 2 lb
 .264 274.195 629.188 409.347 588.113 544.499 0 0 0 2 lb
 .264 274.195 797.466 341.771 924.667 409.347 0 0 0 2 lb
 .113 544.499 756.39 476.923 924.667 409.347 0 0 0 2 lb
 		-689.204 -237.261 -614.799 -102.648 -567.302 43.6423 0 0 0 2 lb
 		-689.204 -237.261 -641.707 -90.9706 -567.302 43.6423 0 0 0 2 lb
 		grestore
 		%Nodes:
 		gsave
 		-567.302 43.6423 20 0 0 0 nc
 		-689.204 -237.261 20 0 0 0 nc
 .667 409.347 20 1 0 0 nc
 .113 544.499 20 1 0 0 nc
 .264 274.195 20 1 0 0 nc
 		-371.2 568.349 20 0 1 0 nc
 		-132.697 451.748 20 0 1 0 nc
 		-416.25 345.746 20 0 1 0 nc
 		-180.397 245.045 20 0 1 0 nc
 		-13.4452 133.743 20 0 1 0 nc
 		-262.548 107.243 20 0 1 0 nc
 .208 38.3422 20 0 1 0 nc
 .407 -173.66 20 0 1 0 nc
 		-26.6953 -19.9585 20 0 1 0 nc
 		-539.894 -262.64 20 0 0 1 nc
 		-323.543 -433.964 20 0 0 1 nc
 		-309.657 -57.9033 20 0 0 1 nc
 		-67.9734 -347.42 20 0 0 1 nc
 .393 -289.516 20 0 0 1 nc
 .084 -307.139 20 0 0 1 nc
 .164 32.7279 20 0 0 1 nc
 .812 -17.6227 20 0 0 1 nc
 		-67.9734 319.727 20 0 0 1 nc
 .797 314.692 20 0 0 1 nc
 		-5.03507 561.41 20 0 0 1 nc
 .945 521.129 20 0 0 1 nc
 		-470.779 158.605 20 0 0 1 nc
 .873 -115.807 20 0 0 1 nc
 .312 201.403 20 0 0 1 nc
 		-767.847 113.289 20 0 0 1 nc
 		-579.033 445.603 20 0 0 1 nc
 		-840.856 -246.718 20 0 0 1 nc
 .221 -205.967 20 1 1 0 nc
 .311 -252.33 20 1 1 0 nc
 .13 -175.058 20 1 1 0 nc
 .947 -110.15 20 1 1 0 nc
 .855 -196.694 20 1 1 0 nc
 .037 -88.514 20 1 1 0 nc
 .584 -48.3327 20 1 1 0 nc
 .403 -23.6057 20 1 1 0 nc
 .402 10.3938 20 1 1 0 nc
 .579 115.483 20 1 0 0 nc
 .035 177.301 20 1 0 0 nc
 		grestore
 		grestore
 		showpage

doc/images/edge_biconnected_components.eps

Show inline comments

 		%!PS-Adobe-2.0 EPSF-2.0
 		%%Creator: LEMON, graphToEps()
 		%%CreationDate: Fri Nov  4 13:47:12 2005
 		%%BoundingBox: 0 0 842 596
 		%%EndComments
 		/lb { setlinewidth setrgbcolor newpath moveto
 2 roll 1 index 1 index curveto stroke } bind def
 		/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
 		/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
 		/sq { newpath 2 index 1 index add 2 index 2 index add moveto
 index 1 index sub 2 index 2 index add lineto
 index 1 index sub 2 index 2 index sub lineto
 index 1 index add 2 index 2 index sub lineto
 		      closepath pop pop pop} bind def
 		/di { newpath 2 index 1 index add 2 index moveto
 index             2 index 2 index add lineto
 index 1 index sub 2 index             lineto
 index             2 index 2 index sub lineto
 		      closepath pop pop pop} bind def
 		/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
 		     setrgbcolor 1.1 div c fill
 		   } bind def
 		/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
 		     setrgbcolor 1.1 div sq fill
 		   } bind def
 		/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
 		     setrgbcolor 1.1 div di fill
 		   } bind def
 		/arrl 1 def
 		/arrw 0.3 def
 		/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
 		/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
 		       /w exch def /len exch def
 		       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
 		       len w sub arrl sub dx dy lrl
 		       arrw dy dx neg lrl
 		       dx arrl w add mul dy w 2 div arrw add mul sub
 		       dy arrl w add mul dx w 2 div arrw add mul add rlineto
 		       dx arrl w add mul neg dy w 2 div arrw add mul sub
 		       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
 		       arrw dy dx neg lrl
 		       len w sub arrl sub neg dx dy lrl
 		       closepath fill } bind def
 		/cshow { 2 index 2 index moveto dup stringwidth pop
 		         neg 2 div fosi .35 mul neg rmoveto show pop pop} def
 		gsave
 rotate
 -842 translate
 .0944 15 translate
 .434694 dup scale
 rotate
 .856 -588.349 translate
 		%Edges:
 		gsave
 .035 177.301 622.149 225.748 670.264 274.195 1 0 0 2 lb
 .579 115.483 682.421 194.839 670.264 274.195 1 0 0 2 lb
 .402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 1 2 lb
 .402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 1 2 lb
 .403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 1 2 lb
 .584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 1 2 lb
 .584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 1 2 lb
 .037 -88.514 417.946 -142.604 397.855 -196.694 0 0 1 2 lb
 .037 -88.514 402.492 -99.332 366.947 -110.15 0 0 1 2 lb
 .855 -196.694 382.401 -153.422 366.947 -110.15 0 0 1 2 lb
 .947 -110.15 319.038 -142.604 271.13 -175.058 0 0 1 2 lb
 .13 -175.058 274.221 -213.694 277.311 -252.33 0 0 1 2 lb
 .13 -175.058 238.675 -190.512 206.221 -205.967 0 0 1 2 lb
 .311 -252.33 241.766 -229.149 206.221 -205.967 0 0 1 2 lb
 		-840.856 -246.718 -804.351 -66.7145 -767.847 113.289 1 0 0 2 lb
 		-579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 1 2 lb
 		-579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 1 2 lb
 		-767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 1 2 lb
 .312 201.403 946.592 42.798 986.873 -115.807 0 0 1 2 lb
 .312 201.403 834.562 91.8901 762.812 -17.6227 0 0 1 2 lb
 .873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 1 2 lb
 		-470.779 158.605 -390.218 50.3508 -309.657 -57.9033 1 0 0 2 lb
 .945 521.129 208.955 541.269 -5.03507 561.41 0 0 1 2 lb
 .945 521.129 376.371 417.911 329.797 314.692 0 0 1 2 lb
 .945 521.129 474.554 276.928 526.164 32.7279 0 0 1 2 lb
 		-5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 1 2 lb
 .797 314.692 130.912 317.209 -67.9734 319.727 0 0 1 2 lb
 		-67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 1 2 lb
 .812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 1 2 lb
 .812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 1 2 lb
 .164 32.7279 470.779 -128.394 415.393 -289.516 0 0 1 2 lb
 .084 -307.139 572.738 -298.327 415.393 -289.516 0 0 1 2 lb
 .393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0 0 2 lb
 		-67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 1 2 lb
 		-67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 1 2 lb
 		-309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 1 2 lb
 		-323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 1 2 lb
 		-26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 1 2 lb
 		-26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 1 2 lb
 		-26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 1 2 lb
 		-26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 1 2 lb
 .407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 1 2 lb
 		-262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 1 2 lb
 		-262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 1 2 lb
 		-13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 1 2 lb
 		-180.397 245.045 -142.256 345.099 -132.697 451.748 0 0 1 2 lb
 		-180.397 245.045 -170.838 351.694 -132.697 451.748 0 0 1 2 lb
 		-416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 1 2 lb
 		-416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 1 2 lb
 		-132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 1 2 lb
 .264 274.195 629.188 409.347 588.113 544.499 0 0 1 2 lb
 .264 274.195 797.466 341.771 924.667 409.347 0 0 1 2 lb
 .113 544.499 756.39 476.923 924.667 409.347 0 0 1 2 lb
 		-689.204 -237.261 -614.799 -102.648 -567.302 43.6423 0 0 1 2 lb
 		-689.204 -237.261 -641.707 -90.9706 -567.302 43.6423 0 0 1 2 lb
 		grestore
 		%Nodes:
 		gsave
 		-567.302 43.6423 20 0 0 0 nc
 		-689.204 -237.261 20 0 0 0 nc
 .667 409.347 20 0 0 1 nc
 .113 544.499 20 0 0 1 nc
 .264 274.195 20 0 0 1 nc
 		-371.2 568.349 20 1 1 0 nc
 		-132.697 451.748 20 1 1 0 nc
 		-416.25 345.746 20 1 1 0 nc
 		-180.397 245.045 20 1 1 0 nc
 		-13.4452 133.743 20 1 1 0 nc
 		-262.548 107.243 20 1 1 0 nc
 .208 38.3422 20 1 1 0 nc
 .407 -173.66 20 1 1 0 nc
 		-26.6953 -19.9585 20 1 1 0 nc
 		-539.894 -262.64 20 0 0.5 0 nc
 		-323.543 -433.964 20 0 0.5 0 nc
 		-309.657 -57.9033 20 0 0.5 0 nc
 		-67.9734 -347.42 20 0 0.5 0 nc
 .393 -289.516 20 0.5 0 0 nc
 .084 -307.139 20 0.5 0 0 nc
 .164 32.7279 20 0.5 0 0 nc
 .812 -17.6227 20 0.5 0 0 nc
 		-67.9734 319.727 20 0.5 0 0 nc
 .797 314.692 20 0.5 0 0 nc
 		-5.03507 561.41 20 0.5 0 0 nc
 .945 521.129 20 0.5 0 0 nc
 		-470.779 158.605 20 0 1 1 nc
 .873 -115.807 20 0.5 0 0 nc
 .312 201.403 20 0.5 0 0 nc
 		-767.847 113.289 20 0 1 1 nc
 		-579.033 445.603 20 0 1 1 nc
 		-840.856 -246.718 20 1 0 1 nc
 .221 -205.967 20 0 0 0.5 nc
 .311 -252.33 20 0 0 0.5 nc
 .13 -175.058 20 0 0 0.5 nc
 .947 -110.15 20 0 0 0.5 nc
 .855 -196.694 20 0 0 0.5 nc
 .037 -88.514 20 0 0 0.5 nc
 .584 -48.3327 20 0 0 0.5 nc
 .403 -23.6057 20 0 0 0.5 nc
 .402 10.3938 20 0 0 0.5 nc
 .579 115.483 20 1 0 0 nc
 .035 177.301 20 0 1 0 nc
 		grestore
 		grestore
 		showpage

doc/images/grid_graph.eps

Show inline comments

 		%!PS-Adobe-2.0 EPSF-2.0
 		%%Title: Grid undirected graph
 		%%Copyright: (C) 2006 LEMON Project
 		%%Creator: LEMON, graphToEps()
 		%%CreationDate: Fri Sep 29 11:55:56 2006
 		%%BoundingBox: 0 0 985 1144
 		%%EndComments
 		/lb { setlinewidth setrgbcolor newpath moveto
 2 roll 1 index 1 index curveto stroke } bind def
 		/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
 		/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
 		/sq { newpath 2 index 1 index add 2 index 2 index add moveto
 index 1 index sub 2 index 2 index add lineto
 index 1 index sub 2 index 2 index sub lineto
 index 1 index add 2 index 2 index sub lineto
 		      closepath pop pop pop} bind def
 		/di { newpath 2 index 1 index add 2 index moveto
 index             2 index 2 index add lineto
 index 1 index sub 2 index             lineto
 index             2 index 2 index sub lineto
 		      closepath pop pop pop} bind def
 		/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
 		     setrgbcolor 1.1 div c fill
 		   } bind def
 		/arrl 1 def
 		/arrw 0.3 def
 		/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
 		/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
 		       /w exch def /len exch def
 		       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
 		       len w sub arrl sub dx dy lrl
 		       arrw dy dx neg lrl
 		       dx arrl w add mul dy w 2 div arrw add mul sub
 		       dy arrl w add mul dx w 2 div arrw add mul add rlineto
 		       dx arrl w add mul neg dy w 2 div arrw add mul sub
 		       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
 		       arrw dy dx neg lrl
 		       len w sub arrl sub neg dx dy lrl
 		       closepath fill } bind def
 		/cshow { 2 index 2 index moveto dup stringwidth pop
 		         neg 2 div fosi .35 mul neg rmoveto show pop pop} def
 		gsave
 2 scale
 40 translate
 .5000 5.5000 scale
 		% 1.14018 1.14018 translate
 		%Edges:
 		gsave
 80 70 90 0 0 0 0.5000 l
 70 70 80 0 0 0 0.5000 l
 60 70 70 0 0 0 0.5000 l
 50 70 60 0 0 0 0.5000 l
 40 70 50 0 0 0 0.5000 l
 30 70 40 0 0 0 0.5000 l
 20 70 30 0 0 0 0.5000 l
 10 70 20 0 0 0 0.5000 l
 0 70 10 0 0 0 0.5000 l
 80 60 90 0 0 0 0.5000 l
 70 60 80 0 0 0 0.5000 l
 60 60 70 0 0 0 0.5000 l
 50 60 60 0 0 0 0.5000 l
 40 60 50 0 0 0 0.5000 l
 30 60 40 0 0 0 0.5000 l
 20 60 30 0 0 0 0.5000 l
 10 60 20 0 0 0 0.5000 l
 0 60 10 0 0 0 0.5000 l
 80 50 90 0 0 0 0.5000 l
 70 50 80 0 0 0 0.5000 l
 60 50 70 0 0 0 0.5000 l
 50 50 60 0 0 0 0.5000 l
 40 50 50 0 0 0 0.5000 l
 30 50 40 0 0 0 0.5000 l
 20 50 30 0 0 0 0.5000 l
 10 50 20 0 0 0 0.5000 l
 0 50 10 0 0 0 0.5000 l
 80 40 90 0 0 0 0.5000 l
 70 40 80 0 0 0 0.5000 l
 60 40 70 0 0 0 0.5000 l
 50 40 60 0 0 0 0.5000 l
 40 40 50 0 0 0 0.5000 l
 30 40 40 0 0 0 0.5000 l
 20 40 30 0 0 0 0.5000 l
 10 40 20 0 0 0 0.5000 l
 0 40 10 0 0 0 0.5000 l
 80 30 90 0 0 0 0.5000 l
 70 30 80 0 0 0 0.5000 l
 60 30 70 0 0 0 0.5000 l
 50 30 60 0 0 0 0.5000 l
 40 30 50 0 0 0 0.5000 l
 30 30 40 0 0 0 0.5000 l
 20 30 30 0 0 0 0.5000 l
 10 30 20 0 0 0 0.5000 l
 0 30 10 0 0 0 0.5000 l
 80 20 90 0 0 0 0.5000 l
 70 20 80 0 0 0 0.5000 l
 60 20 70 0 0 0 0.5000 l
 50 20 60 0 0 0 0.5000 l
 40 20 50 0 0 0 0.5000 l
 30 20 40 0 0 0 0.5000 l
 20 20 30 0 0 0 0.5000 l
 10 20 20 0 0 0 0.5000 l
 0 20 10 0 0 0 0.5000 l
 80 10 90 0 0 0 0.5000 l
 70 10 80 0 0 0 0.5000 l
 60 10 70 0 0 0 0.5000 l
 50 10 60 0 0 0 0.5000 l
 40 10 50 0 0 0 0.5000 l
 30 10 40 0 0 0 0.5000 l
 20 10 30 0 0 0 0.5000 l
 10 10 20 0 0 0 0.5000 l
 0 10 10 0 0 0 0.5000 l
 80 0 90 0 0 0 0.5000 l
 70 0 80 0 0 0 0.5000 l
 60 0 70 0 0 0 0.5000 l
 50 0 60 0 0 0 0.5000 l
 40 0 50 0 0 0 0.5000 l
 30 0 40 0 0 0 0.5000 l
 20 0 30 0 0 0 0.5000 l
 10 0 20 0 0 0 0.5000 l
 0 0 10 0 0 0 0.5000 l
 90 70 90 0 0 0 0.5000 l
 80 70 80 0 0 0 0.5000 l
 70 70 70 0 0 0 0.5000 l
 60 70 60 0 0 0 0.5000 l
 50 70 50 0 0 0 0.5000 l
 40 70 40 0 0 0 0.5000 l
 30 70 30 0 0 0 0.5000 l
 20 70 20 0 0 0 0.5000 l
 10 70 10 0 0 0 0.5000 l
 0 70 0 0 0 0 0.5000 l
 90 60 90 0 0 0 0.5000 l
 80 60 80 0 0 0 0.5000 l
 70 60 70 0 0 0 0.5000 l
 60 60 60 0 0 0 0.5000 l
 50 60 50 0 0 0 0.5000 l
 40 60 40 0 0 0 0.5000 l
 30 60 30 0 0 0 0.5000 l
 20 60 20 0 0 0 0.5000 l
 10 60 10 0 0 0 0.5000 l
 0 60 0 0 0 0 0.5000 l
 90 50 90 0 0 0 0.5000 l
 80 50 80 0 0 0 0.5000 l
 70 50 70 0 0 0 0.5000 l
 60 50 60 0 0 0 0.5000 l
 50 50 50 0 0 0 0.5000 l
 40 50 40 0 0 0 0.5000 l
 30 50 30 0 0 0 0.5000 l
 20 50 20 0 0 0 0.5000 l
 10 50 10 0 0 0 0.5000 l
 0 50 0 0 0 0 0.5000 l
 90 40 90 0 0 0 0.5000 l
 80 40 80 0 0 0 0.5000 l
 70 40 70 0 0 0 0.5000 l
 60 40 60 0 0 0 0.5000 l
 50 40 50 0 0 0 0.5000 l
 40 40 40 0 0 0 0.5000 l
 30 40 30 0 0 0 0.5000 l
 20 40 20 0 0 0 0.5000 l
 10 40 10 0 0 0 0.5000 l
 0 40 0 0 0 0 0.5000 l
 90 30 90 0 0 0 0.5000 l
 80 30 80 0 0 0 0.5000 l
 70 30 70 0 0 0 0.5000 l
 60 30 60 0 0 0 0.5000 l
 50 30 50 0 0 0 0.5000 l
 40 30 40 0 0 0 0.5000 l
 30 30 30 0 0 0 0.5000 l
 20 30 20 0 0 0 0.5000 l
 10 30 10 0 0 0 0.5000 l
 0 30 0 0 0 0 0.5000 l
 90 20 90 0 0 0 0.5000 l
 80 20 80 0 0 0 0.5000 l
 70 20 70 0 0 0 0.5000 l
 60 20 60 0 0 0 0.5000 l
 50 20 50 0 0 0 0.5000 l
 40 20 40 0 0 0 0.5000 l
 30 20 30 0 0 0 0.5000 l
 20 20 20 0 0 0 0.5000 l
 10 20 10 0 0 0 0.5000 l
 0 20 0 0 0 0 0.5000 l
 90 10 90 0 0 0 0.5000 l
 80 10 80 0 0 0 0.5000 l
 70 10 70 0 0 0 0.5000 l
 60 10 60 0 0 0 0.5000 l
 50 10 50 0 0 0 0.5000 l
 40 10 40 0 0 0 0.5000 l
 30 10 30 0 0 0 0.5000 l
 20 10 20 0 0 0 0.5000 l
 10 10 10 0 0 0 0.5000 l
 0 10 0 0 0 0 0.5000 l
 		grestore
 		%Nodes:
 		gsave
 90 1.4000 0 0 0 nc
 80 1.4000 1 1 1 nc
 70 1.4000 1 1 1 nc
 60 1.4000 1 1 1 nc
 50 1.4000 1 1 1 nc
 40 1.4000 1 1 1 nc
 30 1.4000 1 1 1 nc
 20 1.4000 1 1 1 nc
 10 1.4000 1 1 1 nc
 0 1.4000 0 0 0 nc
 90 1.4000 1 1 1 nc
 80 1.4000 1 1 1 nc
 70 1.4000 1 1 1 nc
 60 1.4000 1 1 1 nc
 50 1.4000 1 1 1 nc
 40 1.4000 1 1 1 nc
 30 1.4000 1 1 1 nc
 20 1.4000 1 1 1 nc
 10 1.4000 1 1 1 nc
 0 1.4000 1 1 1 nc
 90 1.4000 1 1 1 nc
 80 1.4000 1 1 1 nc
 70 1.4000 1 1 1 nc
 60 1.4000 1 1 1 nc
 50 1.4000 1 1 1 nc
 40 1.4000 1 1 1 nc
 30 1.4000 1 1 1 nc
 20 1.4000 1 1 1 nc
 10 1.4000 1 1 1 nc
 0 1.4000 1 1 1 nc
 90 1.4000 1 1 1 nc
 80 1.4000 1 1 1 nc
 70 1.4000 1 1 1 nc
 60 1.4000 1 1 1 nc
 50 1.4000 1 1 1 nc
 40 1.4000 1 1 1 nc
 30 1.4000 1 1 1 nc
 20 1.4000 1 1 1 nc
 10 1.4000 1 1 1 nc
 0 1.4000 1 1 1 nc
 90 1.4000 1 1 1 nc
 80 1.4000 1 1 1 nc
 70 1.4000 1 1 1 nc
 60 1.4000 1 1 1 nc
 50 1.4000 1 1 1 nc
 40 1.4000 1 1 1 nc
 30 1.4000 1 1 1 nc
 20 1.4000 1 1 1 nc
 10 1.4000 1 1 1 nc
 0 1.4000 1 1 1 nc
 90 1.4000 1 1 1 nc
 80 1.4000 1 1 1 nc
 70 1.4000 1 1 1 nc
 60 1.4000 1 1 1 nc
 50 1.4000 1 1 1 nc
 40 1.4000 1 1 1 nc
 30 1.4000 1 1 1 nc
 20 1.4000 1 1 1 nc
 10 1.4000 1 1 1 nc
 0 1.4000 1 1 1 nc
 90 1.4000 1 1 1 nc
 80 1.4000 1 1 1 nc
 70 1.4000 1 1 1 nc
 60 1.4000 1 1 1 nc
 50 1.4000 1 1 1 nc
 40 1.4000 1 1 1 nc
 30 1.4000 1 1 1 nc
 20 1.4000 1 1 1 nc
 10 1.4000 1 1 1 nc
 0 1.4000 1 1 1 nc
 90 1.4000 0 0 0 nc
 80 1.4000 1 1 1 nc
 70 1.4000 1 1 1 nc
 60 1.4000 1 1 1 nc
 50 1.4000 1 1 1 nc
 40 1.4000 1 1 1 nc
 30 1.4000 1 1 1 nc
 20 1.4000 1 1 1 nc
 10 1.4000 1 1 1 nc
 0 1.4000 0 0 0 nc
 		grestore
 		gsave
 		/fosi 3.5 def
 		(Helvetica) findfont fosi scalefont setfont
 0 0 setrgbcolor
 95 ((0,height-1)) cshow
 95 ((width-1,height-1)) cshow
 -5 ((0,0)) cshow
 -5 ((width-1,0)) cshow
 		grestore
 		grestore
 		showpage

doc/images/node_biconnected_components.eps

Show inline comments

 		%!PS-Adobe-2.0 EPSF-2.0
 		%%Creator: LEMON, graphToEps()
 		%%CreationDate: Fri Nov  4 13:47:12 2005
 		%%BoundingBox: 0 0 842 596
 		%%EndComments
 		/lb { setlinewidth setrgbcolor newpath moveto
 2 roll 1 index 1 index curveto stroke } bind def
 		/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
 		/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
 		/sq { newpath 2 index 1 index add 2 index 2 index add moveto
 index 1 index sub 2 index 2 index add lineto
 index 1 index sub 2 index 2 index sub lineto
 index 1 index add 2 index 2 index sub lineto
 		      closepath pop pop pop} bind def
 		/di { newpath 2 index 1 index add 2 index moveto
 index             2 index 2 index add lineto
 index 1 index sub 2 index             lineto
 index             2 index 2 index sub lineto
 		      closepath pop pop pop} bind def
 		/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
 		     setrgbcolor 1.1 div c fill
 		   } bind def
 		/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
 		     setrgbcolor 1.1 div sq fill
 		   } bind def
 		/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
 		     setrgbcolor 1.1 div di fill
 		   } bind def
 		/arrl 1 def
 		/arrw 0.3 def
 		/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
 		/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
 		       /w exch def /len exch def
 		       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
 		       len w sub arrl sub dx dy lrl
 		       arrw dy dx neg lrl
 		       dx arrl w add mul dy w 2 div arrw add mul sub
 		       dy arrl w add mul dx w 2 div arrw add mul add rlineto
 		       dx arrl w add mul neg dy w 2 div arrw add mul sub
 		       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
 		       arrw dy dx neg lrl
 		       len w sub arrl sub neg dx dy lrl
 		       closepath fill } bind def
 		/cshow { 2 index 2 index moveto dup stringwidth pop
 		         neg 2 div fosi .35 mul neg rmoveto show pop pop} def
 		gsave
 rotate
 -842 translate
 .0944 15 translate
 .434694 dup scale
 rotate
 .856 -588.349 translate
 		%Edges:
 		gsave
 .035 177.301 622.149 225.748 670.264 274.195 0 1 0 5 lb
 .579 115.483 682.421 194.839 670.264 274.195 1 0 0 5 lb
 .402 10.3938 246.402 -6.60595 212.403 -23.6057 1 1 0.5 5 lb
 .402 10.3938 283.493 -18.9695 286.584 -48.3327 1 1 0.5 5 lb
 .403 -23.6057 249.493 -35.9692 286.584 -48.3327 1 1 0.5 5 lb
 .584 -48.3327 326.765 -79.2414 366.947 -110.15 1 0.5 1 5 lb
 .584 -48.3327 278.857 -111.695 271.13 -175.058 1 0.5 1 5 lb
 .037 -88.514 417.946 -142.604 397.855 -196.694 0.5 0.5 1 5 lb
 .037 -88.514 402.492 -99.332 366.947 -110.15 0.5 0.5 1 5 lb
 .855 -196.694 382.401 -153.422 366.947 -110.15 0.5 0.5 1 5 lb
 .947 -110.15 319.038 -142.604 271.13 -175.058 1 0.5 1 5 lb
 .13 -175.058 274.221 -213.694 277.311 -252.33 0.5 1 1 5 lb
 .13 -175.058 238.675 -190.512 206.221 -205.967 0.5 1 1 5 lb
 .311 -252.33 241.766 -229.149 206.221 -205.967 0.5 1 1 5 lb
 		-840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0.5 0 5 lb
 		-579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0.5 5 lb
 		-579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0.5 5 lb
 		-767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0.5 5 lb
 .312 201.403 946.592 42.798 986.873 -115.807 0 0.5 0.5 5 lb
 .312 201.403 834.562 91.8901 762.812 -17.6227 0 0.5 0.5 5 lb
 .873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0.5 0.5 5 lb
 		-470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0.5 0.5 0 5 lb
 .945 521.129 208.955 541.269 -5.03507 561.41 0.5 0 0.5 5 lb
 .945 521.129 376.371 417.911 329.797 314.692 0.5 0 0.5 5 lb
 .945 521.129 474.554 276.928 526.164 32.7279 0.5 0 0.5 5 lb
 		-5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0.5 0 0.5 5 lb
 .797 314.692 130.912 317.209 -67.9734 319.727 0.5 0 0.5 5 lb
 		-67.9734 319.727 229.095 176.227 526.164 32.7279 0.5 0 0.5 5 lb
 .812 -17.6227 644.488 7.5526 526.164 32.7279 0.5 0.5 0.5 5 lb
 .812 -17.6227 746.448 -162.381 730.084 -307.139 0.5 0.5 0.5 5 lb
 .164 32.7279 470.779 -128.394 415.393 -289.516 0.5 0.5 0.5 5 lb
 .084 -307.139 572.738 -298.327 415.393 -289.516 0.5 0.5 0.5 5 lb
 .393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0.5 0.5 5 lb
 		-67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0.5 1 0.5 5 lb
 		-67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0.5 1 0.5 5 lb
 		-309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0.5 1 0.5 5 lb
 		-323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0.5 1 0.5 5 lb
 		-26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 1 1 0 5 lb
 		-26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 1 1 0 5 lb
 		-26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 1 0 1 5 lb
 		-26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 1 0 1 5 lb
 .407 -173.66 158.808 -67.6589 201.208 38.3422 1 1 0 5 lb
 		-262.548 107.243 -137.997 120.493 -13.4452 133.743 1 0 1 5 lb
 		-262.548 107.243 -221.472 176.144 -180.397 245.045 1 0 1 5 lb
 		-13.4452 133.743 -96.9211 189.394 -180.397 245.045 1 0 1 5 lb
 		-180.397 245.045 -140.307 344.649 -132.697 451.748 0 1 1 5 lb
 		-180.397 245.045 -172.787 352.144 -132.697 451.748 0 1 1 5 lb
 		-416.25 345.746 -274.474 398.747 -132.697 451.748 0.5 0 0 5 lb
 		-416.25 345.746 -393.725 457.048 -371.2 568.349 0.5 0 0 5 lb
 		-132.697 451.748 -251.948 510.048 -371.2 568.349 0.5 0 0 5 lb
 .264 274.195 629.188 409.347 588.113 544.499 0 0 1 5 lb
 .264 274.195 797.466 341.771 924.667 409.347 0 0 1 5 lb
 .113 544.499 756.39 476.923 924.667 409.347 0 0 1 5 lb
 		-689.204 -237.261 -612.964 -103.444 -567.302 43.6423 0 0 0 5 lb
 		-689.204 -237.261 -643.542 -90.1744 -567.302 43.6423 0 0 0 5 lb
 		grestore
 		%Nodes:
 		gsave
 		-567.302 43.6423 20 0 0 1 nc
 		-689.204 -237.261 20 0 0 1 nc
 .667 409.347 20 0 0 1 nc
 .113 544.499 20 0 0 1 nc
 .264 274.195 20 1 0 0 nc
 		-371.2 568.349 20 0 0 1 nc
 		-132.697 451.748 20 1 0 0 nc
 		-416.25 345.746 20 0 0 1 nc
 		-180.397 245.045 20 1 0 0 nc
 		-13.4452 133.743 20 0 0 1 nc
 		-262.548 107.243 20 0 0 1 nc
 .208 38.3422 20 0 0 1 nc
 .407 -173.66 20 0 0 1 nc
 		-26.6953 -19.9585 20 1 0 0 nc
 		-539.894 -262.64 20 0 0 1 nc
 		-323.543 -433.964 20 0 0 1 nc
 		-309.657 -57.9033 20 1 0 0 nc
 		-67.9734 -347.42 20 1 0 0 nc
 .393 -289.516 20 1 0 0 nc
 .084 -307.139 20 0 0 1 nc
 .164 32.7279 20 1 0 0 nc
 .812 -17.6227 20 1 0 0 nc
 		-67.9734 319.727 20 0 0 1 nc
 .797 314.692 20 0 0 1 nc
 		-5.03507 561.41 20 0 0 1 nc
 .945 521.129 20 0 0 1 nc
 		-470.779 158.605 20 1 0 0 nc
 .873 -115.807 20 0 0 1 nc
 .312 201.403 20 0 0 1 nc
 		-767.847 113.289 20 1 0 0 nc
 		-579.033 445.603 20 0 0 1 nc
 		-840.856 -246.718 20 0 0 1 nc
 .221 -205.967 20 0 0 1 nc
 .311 -252.33 20 0 0 1 nc
 .13 -175.058 20 1 0 0 nc
 .947 -110.15 20 1 0 0 nc
 .855 -196.694 20 0 0 1 nc
 .037 -88.514 20 0 0 1 nc
 .584 -48.3327 20 1 0 0 nc
 .403 -23.6057 20 0 0 1 nc
 .402 10.3938 20 0 0 1 nc
 .579 115.483 20 0 0 1 nc
 .035 177.301 20 0 0 1 nc
 		grestore
 		grestore
 		showpage

doc/images/strongly_connected_components.eps

Show inline comments

 		%!PS-Adobe-2.0 EPSF-2.0
 		%%Creator: LEMON, graphToEps()
 		%%CreationDate: Fri Nov  4 13:47:12 2005
 		%%BoundingBox: 0 0 842 596
 		%%EndComments
 		/lb { setlinewidth setrgbcolor newpath moveto
 2 roll 1 index 1 index curveto stroke } bind def
 		/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
 		/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
 		/sq { newpath 2 index 1 index add 2 index 2 index add moveto
 index 1 index sub 2 index 2 index add lineto
 index 1 index sub 2 index 2 index sub lineto
 index 1 index add 2 index 2 index sub lineto
 		      closepath pop pop pop} bind def
 		/di { newpath 2 index 1 index add 2 index moveto
 index             2 index 2 index add lineto
 index 1 index sub 2 index             lineto
 index             2 index 2 index sub lineto
 		      closepath pop pop pop} bind def
 		/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
 		     setrgbcolor 1.1 div c fill
 		   } bind def
 		/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
 		     setrgbcolor 1.1 div sq fill
 		   } bind def
 		/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
 		     setrgbcolor 1.1 div di fill
 		   } bind def
 		/arrl 10 def
 		/arrw 3 def
 		/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
 		/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
 		       /w exch def /len exch def
 		       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
 		       len w sub arrl sub dx dy lrl
 		       arrw dy dx neg lrl
 		       dx arrl w add mul dy w 2 div arrw add mul sub
 		       dy arrl w add mul dx w 2 div arrw add mul add rlineto
 		       dx arrl w add mul neg dy w 2 div arrw add mul sub
 		       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
 		       arrw dy dx neg lrl
 		       len w sub arrl sub neg dx dy lrl
 		       closepath fill } bind def
 		/cshow { 2 index 2 index moveto dup stringwidth pop
 		         neg 2 div fosi .35 mul neg rmoveto show pop pop} def
 		gsave
 rotate
 -842 translate
 .1122 15 translate
 .585745 dup scale
 rotate
 .963 -397.916 translate
 		%Edges:
 		gsave
 setlinewidth 0 0 1 setrgbcolor newpath
 .178 27.2723 moveto
 .373 -40.1551 188.622 -49.9556 169.228 -100.631 curveto stroke
 		newpath 164.939 -111.838 moveto 165.492 -99.2013 lineto 172.964 -102.061 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
 .8044 15.5841 moveto
 .293 20.6059 129.775 21.3125 186.25 25.1199 curveto stroke
 		newpath 198.223 25.927 moveto 186.519 21.1289 lineto 185.981 29.1108 lineto closepath fill
 setlinewidth 1 0 0 setrgbcolor newpath
 .178 27.2723 moveto
 .395 -87.4449 290.763 -96.6058 348.102 -194.464 curveto stroke
 		newpath 354.169 -204.818 moveto 344.651 -196.487 lineto 351.554 -192.442 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
 .79 -130.517 moveto
 .71 -67.0521 102.27 -58.7243 64.3804 -9.72954 curveto stroke
 		newpath 57.0394 -0.236898 moveto 67.5446 -7.28254 lineto 61.2162 -12.1765 lineto closepath fill
 setlinewidth 1 0 0 setrgbcolor newpath
 		-105.193 -261.035 moveto
 		-35.6576 -132.801 -30.5923 -123.459 29.5506 -12.5464 curveto stroke
 		newpath 35.2708 -1.99743 moveto 33.0669 -14.4531 lineto 26.0343 -10.6397 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
 		-465.576 -42.8564 moveto
 		-559.078 -25.5413 -569.47 -23.6169 -644.498 -9.72286 curveto stroke
 		newpath -656.297 -7.5378 moveto -643.77 -5.78973 lineto -645.226 -13.656 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
 		-574.666 -153.893 moveto
 		-528.842 -107.252 -521.515 -99.794 -488.002 -65.683 curveto stroke
 		newpath -479.592 -57.123 moveto -485.149 -68.4863 lineto -490.856 -62.8797 lineto closepath fill
 setlinewidth 1 0 0 setrgbcolor newpath
 		-490.901 120.777 moveto
 		-480.122 51.1328 -478.519 40.7713 -470.47 -11.2329 curveto stroke
 		newpath -468.635 -23.0917 moveto -474.423 -11.8447 lineto -466.517 -10.6212 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
 		-675.963 -3.89604 moveto
 		-632.116 -68.8235 -626.228 -77.5422 -592.575 -127.374 curveto stroke
 		newpath -585.859 -137.319 moveto -595.89 -129.612 lineto -589.26 -125.135 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
 		-490.901 120.777 moveto
 		-435.445 215.844 -430.107 224.995 -384.3 303.522 curveto stroke
 		newpath -378.253 313.887 moveto -380.845 301.507 lineto -387.755 305.537 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
 		-266.879 114.933 moveto
 		-367.067 117.547 -377.642 117.822 -458.912 119.943 curveto stroke
 		newpath -470.908 120.255 moveto -458.807 123.941 lineto -459.016 115.944 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
 		-368.176 331.163 moveto
 		-322.511 233.685 -318.018 224.095 -280.454 143.911 curveto stroke
 		newpath -275.364 133.044 moveto -284.076 142.214 lineto -276.832 145.608 lineto closepath fill
 setlinewidth 1 0 0 setrgbcolor newpath
 		-266.879 114.933 moveto
 		-224.004 235.52 -220.448 245.52 -184.094 347.765 curveto stroke
 		newpath -180.074 359.072 moveto -180.325 346.425 lineto -187.863 349.105 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
 		-251.294 -335.059 moveto
 		-189.25 -303.624 -179.902 -298.887 -133.738 -275.498 curveto stroke
 		newpath -123.034 -270.074 moveto -131.93 -279.066 lineto -135.546 -271.93 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
 		-389.604 -136.361 moveto
 		-327.15 -226.083 -321.098 -234.777 -269.576 -308.795 curveto stroke
 		newpath -262.72 -318.644 moveto -272.859 -311.081 lineto -266.293 -306.51 lineto closepath fill
 setlinewidth 1 0 0 setrgbcolor newpath
 .84406 175.322 moveto
 		-76.0754 267.926 -83.1051 275.873 -152.172 353.948 curveto stroke
 		newpath -160.122 362.936 moveto -149.176 356.598 lineto -155.168 351.298 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
 .478 311.683 moveto
 .8003 251.119 88.6819 244.353 30.4273 195.808 curveto stroke
 		newpath 21.2086 188.126 moveto 27.8666 198.881 lineto 32.988 192.735 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
 .851 111.037 moveto
 .766 202.563 256.831 210.589 190.4 287.47 curveto stroke
 		newpath 182.554 296.55 moveto 193.427 290.085 lineto 187.373 284.855 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
 .84406 175.322 moveto
 .16 145.314 173.605 143.321 311.418 117.033 curveto stroke
 		newpath 323.205 114.784 moveto 310.668 113.104 lineto 312.167 120.962 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
 .851 111.037 moveto
 .255 2.58683 505.964 -3.53033 643.932 -100.436 curveto stroke
 		newpath 653.752 -107.334 moveto 641.633 -103.71 lineto 646.231 -97.163 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
 .28 -222.074 moveto
 .298 -66.9063 353.616 -56.2971 344.905 79.1029 curveto stroke
 		newpath 344.135 91.0781 moveto 348.897 79.3597 lineto 340.914 78.8461 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
 .118 -118.829 moveto
 .037 -166.793 517.967 -170.192 394.599 -211.839 curveto stroke
 		newpath 383.229 -215.677 moveto 393.32 -208.049 lineto 395.878 -215.629 lineto closepath fill
 setlinewidth 1 0 0 setrgbcolor newpath
 		-105.193 -261.035 moveto
 .401 -242.479 129.015 -241.598 332.39 -224.721 curveto stroke
 		newpath 344.348 -223.728 moveto 332.72 -228.707 lineto 332.059 -220.734 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
 		-105.193 -261.035 moveto
 		-160.867 -161.176 -166.028 -151.918 -212.336 -68.858 curveto stroke
 		newpath -218.179 -58.3769 moveto -208.842 -66.9102 lineto -215.829 -70.8058 lineto closepath fill
 setlinewidth 0 0 1 setrgbcolor newpath
 		-227.918 -40.9084 moveto
 		-298.35 -82.4884 -307.42 -87.8432 -362.048 -120.093 curveto stroke
 		newpath -372.381 -126.193 moveto -364.081 -116.648 lineto -360.014 -123.537 lineto closepath fill
 		grestore
 		%Nodes:
 		gsave
 		-389.604 -136.361 20 0 1 0 nc
 		-227.918 -40.9084 20 0 1 0 nc
 		-105.193 -261.035 20 0 1 0 nc
 .28 -222.074 20 1 1 0 nc
 .118 -118.829 20 1 1 0 nc
 .851 111.037 20 1 1 0 nc
 .84406 175.322 20 1 1 0 nc
 .478 311.683 20 1 1 0 nc
 		-173.374 377.916 20 1 0 1 nc
 		-251.294 -335.059 20 0 1 0 nc
 		-266.879 114.933 20 0 0 0 nc
 		-368.176 331.163 20 0 0 0 nc
 		-490.901 120.777 20 0 0 0 nc
 		-574.666 -153.893 20 1 0 0 nc
 		-675.963 -3.89604 20 1 0 0 nc
 		-465.576 -42.8564 20 1 0 0 nc
 .8044 15.5841 20 0 0 1 nc
 .79 -130.517 20 0 0 1 nc
 .178 27.2723 20 0 0 1 nc
 		grestore
 		grestore
 		showpage

doc/min_cost_flow.dox

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		namespace lemon {
 		/**
 		\page min_cost_flow Minimum Cost Flow Problem
 		\section mcf_def Definition (GEQ form)
 		The \e minimum \e cost \e flow \e problem is to find a feasible flow of
 		minimum total cost from a set of supply nodes to a set of demand nodes
 		in a network with capacity constraints (lower and upper bounds)
 		and arc costs \ref amo93networkflows.
 		Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
 		\f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and
 		upper bounds for the flow values on the arcs, for which
 		\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
 		\f$cost: A\rightarrow\mathbf{R}\f$ denotes the cost per unit flow
 		on the arcs and \f$sup: V\rightarrow\mathbf{R}\f$ denotes the
 		signed supply values of the nodes.
 		If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
 		supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
 		\f$-sup(u)\f$ demand.
 		A minimum cost flow is an \f$f: A\rightarrow\mathbf{R}\f$ solution
 		of the following optimization problem.
 		\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
 		\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
 		    sup(u) \quad \forall u\in V \f]
 		\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
 		The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
 		zero or negative in order to have a feasible solution (since the sum
 		of the expressions on the left-hand side of the inequalities is zero).
 		It means that the total demand must be greater or equal to the total
 		supply and all the supplies have to be carried out from the supply nodes,
 		but there could be demands that are not satisfied.
 		If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
 		constraints have to be satisfied with equality, i.e. all demands
 		have to be satisfied and all supplies have to be used.
 		\section mcf_algs Algorithms
 		LEMON contains several algorithms for solving this problem, for more
 		information see \ref min_cost_flow_algs "Minimum Cost Flow Algorithms".
 		A feasible solution for this problem can be found using \ref Circulation.
 		\section mcf_dual Dual Solution
 		The dual solution of the minimum cost flow problem is represented by
 		node potentials \f$\pi: V\rightarrow\mathbf{R}\f$.
 		An \f$f: A\rightarrow\mathbf{R}\f$ primal feasible solution is optimal
 		if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$ node potentials
 		the following \e complementary \e slackness optimality conditions hold.
 		 - For all \f$uv\in A\f$ arcs:
 		   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
 		   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
 		   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
 		 - For all \f$u\in V\f$ nodes:
 		   - \f$\pi(u)<=0\f$;
 		   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
 		     then \f$\pi(u)=0\f$.
 		Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
 		\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
 		\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
 		All algorithms provide dual solution (node potentials), as well,
 		if an optimal flow is found.
 		\section mcf_eq Equality Form
 		The above \ref mcf_def "definition" is actually more general than the
 		usual formulation of the minimum cost flow problem, in which strict
 		equalities are required in the supply/demand contraints.
 		\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
 		\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
 		    sup(u) \quad \forall u\in V \f]
 		\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
 		However if the sum of the supply values is zero, then these two problems
 		are equivalent.
 		The \ref min_cost_flow_algs "algorithms" in LEMON support the general
 		form, so if you need the equality form, you have to ensure this additional
 		contraint manually.
 		\section mcf_leq Opposite Inequalites (LEQ Form)
 		Another possible definition of the minimum cost flow problem is
 		when there are <em>"less or equal"</em> (LEQ) supply/demand constraints,
 		instead of the <em>"greater or equal"</em> (GEQ) constraints.
 		\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
 		\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq
 		    sup(u) \quad \forall u\in V \f]
 		\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
 		It means that the total demand must be less or equal to the
 		total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
 		positive) and all the demands have to be satisfied, but there
 		could be supplies that are not carried out from the supply
 		nodes.
 		The equality form is also a special case of this form, of course.
 		You could easily transform this case to the \ref mcf_def "GEQ form"
 		of the problem by reversing the direction of the arcs and taking the
 		negative of the supply values (e.g. using \ref ReverseDigraph and
 		\ref NegMap adaptors).
 		However \ref NetworkSimplex algorithm also supports this form directly
 		for the sake of convenience.
 		Note that the optimality conditions for this supply constraint type are
 		slightly differ from the conditions that are discussed for the GEQ form,
 		namely the potentials have to be non-negative instead of non-positive.
 		An \f$f: A\rightarrow\mathbf{R}\f$ feasible solution of this problem
 		is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$
 		node potentials the following conditions hold.
 		 - For all \f$uv\in A\f$ arcs:
 		   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
 		   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
 		   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
 		 - For all \f$u\in V\f$ nodes:
 		   - \f$\pi(u)>=0\f$;
 		   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
 		     then \f$\pi(u)=0\f$.
 		*/
+		}

doc/references.bib

Show inline comments

 		%%%%% Defining LEMON %%%%%
 		@misc{lemon,
 		  key =          {LEMON},
 		  title =        {{LEMON} -- {L}ibrary for {E}fficient {M}odeling and
 		                  {O}ptimization in {N}etworks},
 		  howpublished = {\url{http://lemon.cs.elte.hu/}},
 		  year =         2009
+		}
 		@misc{egres,
 		  key =          {EGRES},
 		  title =        {{EGRES} -- {E}gerv{\'a}ry {R}esearch {G}roup on
 		                  {C}ombinatorial {O}ptimization},
 		  url =          {http://www.cs.elte.hu/egres/}
+		}
 		@misc{coinor,
 		  key =          {COIN-OR},
 		  title =        {{COIN-OR} -- {C}omputational {I}nfrastructure for
 		                  {O}perations {R}esearch},
 		  url =          {http://www.coin-or.org/}
+		}
 		%%%%% Other libraries %%%%%%
 		@misc{boost,
 		  key =          {Boost},
 		  title =        {{B}oost {C++} {L}ibraries},
 		  url =          {http://www.boost.org/}
+		}
 		@book{bglbook,
 		  author =       {Jeremy G. Siek and Lee-Quan Lee and Andrew
 		                  Lumsdaine},
 		  title =        {The Boost Graph Library: User Guide and Reference
 		                  Manual},
 		  publisher =    {Addison-Wesley},
 		  year =         2002
+		}
 		@misc{leda,
 		  key =          {LEDA},
 		  title =        {{LEDA} -- {L}ibrary of {E}fficient {D}ata {T}ypes and
 		                  {A}lgorithms},
 		  url =          {http://www.algorithmic-solutions.com/}
+		}
 		@book{ledabook,
 		  author =       {Kurt Mehlhorn and Stefan N{\"a}her},
 		  title =        {{LEDA}: {A} platform for combinatorial and geometric
 		                  computing},
 		  isbn =         {0-521-56329-1},
 		  publisher =    {Cambridge University Press},
 		  address =      {New York, NY, USA},
 		  year =         1999
+		}
 		%%%%% Tools that LEMON depends on %%%%%
 		@misc{cmake,
 		  key =          {CMake},
 		  title =        {{CMake} -- {C}ross {P}latform {M}ake},
 		  url =          {http://www.cmake.org/}
+		}
 		@misc{doxygen,
 		  key =          {Doxygen},
 		  title =        {{Doxygen} -- {S}ource code documentation generator
 		                  tool},
 		  url =          {http://www.doxygen.org/}
+		}
 		%%%%% LP/MIP libraries %%%%%
 		@misc{glpk,
 		  key =          {GLPK},
 		  title =        {{GLPK} -- {GNU} {L}inear {P}rogramming {K}it},
 		  url =          {http://www.gnu.org/software/glpk/}
+		}
 		@misc{clp,
 		  key =          {Clp},
 		  title =        {{Clp} -- {Coin-Or} {L}inear {P}rogramming},
 		  url =          {http://projects.coin-or.org/Clp/}
+		}
 		@misc{cbc,
 		  key =          {Cbc},
 		  title =        {{Cbc} -- {Coin-Or} {B}ranch and {C}ut},
 		  url =          {http://projects.coin-or.org/Cbc/}
+		}
 		@misc{cplex,
 		  key =          {CPLEX},
 		  title =        {{ILOG} {CPLEX}},
 		  url =          {http://www.ilog.com/}
+		}
 		@misc{soplex,
 		  key =          {SoPlex},
 		  title =        {{SoPlex} -- {T}he {S}equential {O}bject-{O}riented
 		                  {S}implex},
 		  url =          {http://soplex.zib.de/}
+		}
 		%%%%% General books %%%%%
 		@book{amo93networkflows,
 		  author =       {Ravindra K. Ahuja and Thomas L. Magnanti and James
 		                  B. Orlin},
 		  title =        {Network Flows: Theory, Algorithms, and Applications},
 		  publisher =    {Prentice-Hall, Inc.},
 		  year =         1993,
 		  month =        feb,
 		  isbn =         {978-0136175490}
+		}
 		@book{schrijver03combinatorial,
 		  author =       {Alexander Schrijver},
 		  title =        {Combinatorial Optimization: Polyhedra and Efficiency},
 		  publisher =    {Springer-Verlag},
 		  year =         2003,
 		  isbn =         {978-3540443896}
+		}
 		@book{clrs01algorithms,
 		  author =       {Thomas H. Cormen and Charles E. Leiserson and Ronald
 		                  L. Rivest and Clifford Stein},
 		  title =        {Introduction to Algorithms},
 		  publisher =    {The MIT Press},
 		  year =         2001,
 		  edition =      {2nd}
+		}
 		@book{stroustrup00cpp,
 		  author =       {Bjarne Stroustrup},
 		  title =        {The C++ Programming Language},
 		  edition =      {3rd},
 		  publisher =    {Addison-Wesley Professional},
 		  isbn =         0201700735,
 		  month =        {February},
 		  year =         2000
+		}
 		%%%%% Maximum flow algorithms %%%%%
 		@article{edmondskarp72theoretical,
 		  author =       {Jack Edmonds and Richard M. Karp},
 		  title =        {Theoretical improvements in algorithmic efficiency
 		                  for network flow problems},
 		  journal =      {Journal of the ACM},
 		  year =         1972,
 		  volume =       19,
 		  number =       2,
 		  pages =        {248-264}
+		}
 		@article{goldberg88newapproach,
 		  author =       {Andrew V. Goldberg and Robert E. Tarjan},
 		  title =        {A new approach to the maximum flow problem},
 		  journal =      {Journal of the ACM},
 		  year =         1988,
 		  volume =       35,
 		  number =       4,
 		  pages =        {921-940}
+		}
 		@article{dinic70algorithm,
 		  author =       {E. A. Dinic},
 		  title =        {Algorithm for solution of a problem of maximum flow
 		                  in a network with power estimation},
 		  journal =      {Soviet Math. Doklady},
 		  year =         1970,
 		  volume =       11,
 		  pages =        {1277-1280}
+		}
 		@article{goldberg08partial,
 		  author =       {Andrew V. Goldberg},
 		  title =        {The Partial Augment-Relabel Algorithm for the
 		                  Maximum Flow Problem},
 		  journal =      {16th Annual European Symposium on Algorithms},
 		  year =         2008,
 		  pages =        {466-477}
+		}
 		@article{sleator83dynamic,
 		  author =       {Daniel D. Sleator and Robert E. Tarjan},
 		  title =        {A data structure for dynamic trees},
 		  journal =      {Journal of Computer and System Sciences},
 		  year =         1983,
 		  volume =       26,
 		  number =       3,
 		  pages =        {362-391}
+		}
 		%%%%% Minimum mean cycle algorithms %%%%%
 		@article{karp78characterization,
 		  author =       {Richard M. Karp},
 		  title =        {A characterization of the minimum cycle mean in a
 		                  digraph},
 		  journal =      {Discrete Math.},
 		  year =         1978,
 		  volume =       23,
 		  pages =        {309-311}
+		}
 		@article{dasdan98minmeancycle,
 		  author =       {Ali Dasdan and Rajesh K. Gupta},
 		  title =        {Faster Maximum and Minimum Mean Cycle Alogrithms for
 		                  System Performance Analysis},
 		  journal =      {IEEE Transactions on Computer-Aided Design of
 		                  Integrated Circuits and Systems},
 		  year =         1998,
 		  volume =       17,
 		  number =       10,
 		  pages =        {889-899}
+		}
 		%%%%% Minimum cost flow algorithms %%%%%
 		@article{klein67primal,
 		  author =       {Morton Klein},
 		  title =        {A primal method for minimal cost flows with
 		                  applications to the assignment and transportation
 		                  problems},
 		  journal =      {Management Science},
 		  year =         1967,
 		  volume =       14,
 		  pages =        {205-220}
+		}
 		@article{goldberg89cyclecanceling,
 		  author =       {Andrew V. Goldberg and Robert E. Tarjan},
 		  title =        {Finding minimum-cost circulations by canceling
 		                  negative cycles},
 		  journal =      {Journal of the ACM},
 		  year =         1989,
 		  volume =       36,
 		  number =       4,
 		  pages =        {873-886}
+		}
 		@article{goldberg90approximation,
 		  author =       {Andrew V. Goldberg and Robert E. Tarjan},
 		  title =        {Finding Minimum-Cost Circulations by Successive
 		                  Approximation},
 		  journal =      {Mathematics of Operations Research},
 		  year =         1990,
 		  volume =       15,
 		  number =       3,
 		  pages =        {430-466}
+		}
 		@article{goldberg97efficient,
 		  author =       {Andrew V. Goldberg},
 		  title =        {An Efficient Implementation of a Scaling
 		                  Minimum-Cost Flow Algorithm},
 		  journal =      {Journal of Algorithms},
 		  year =         1997,
 		  volume =       22,
 		  number =       1,
 		  pages =        {1-29}
+		}
 		@article{bunnagel98efficient,
 		  author =       {Ursula B{\"u}nnagel and Bernhard Korte and Jens
 		                  Vygen},
 		  title =        {Efficient implementation of the {G}oldberg-{T}arjan
 		                  minimum-cost flow algorithm},
 		  journal =      {Optimization Methods and Software},
 		  year =         1998,
 		  volume =       10,
 		  pages =        {157-174}
+		}
 		@book{dantzig63linearprog,
 		  author =       {George B. Dantzig},
 		  title =        {Linear Programming and Extensions},
 		  publisher =    {Princeton University Press},
 		  year =         1963
+		}
 		@mastersthesis{kellyoneill91netsimplex,
 		  author =       {Damian J. Kelly and Garrett M. O'Neill},
 		  title =        {The Minimum Cost Flow Problem and The Network
 		                  Simplex Method},
 		  school =       {University College},
 		  address =      {Dublin, Ireland},
 		  year =         1991,
 		  month =        sep,
+		}

.hgignore

Show inline comments

@@ -24,3 +24,3 @@
 		doc/Doxyfile
-		cmake/cmake.version
+		cmake/version.cmake
 		.dirstamp
@@ -29,2 +29,7 @@
 		demo/*.eps
 		m4/libtool.m4
 		m4/ltoptions.m4
 		m4/ltsugar.m4
 		m4/ltversion.m4
 		m4/lt~obsolete.m4
@@ -37,6 +42,7 @@
 		^build-aux/.*
 		^objs.*/.*
+		^.*objs.*/.*
 		^test/[a-z_]*$
 		^tools/[a-z-_]*$
 		^demo/.*_demo$
 		^build/.*
+		^.*build.*/.*
 		^doc/gen-images/.*

CMakeLists.txt

Show inline comments

@@ -2,20 +2,38 @@
 		IF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
 		  INCLUDE(${CMAKE_SOURCE_DIR}/cmake/version.cmake)
 		ELSE(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
 		  SET(PROJECT_NAME "LEMON")
 		  SET(PROJECT_VERSION "hg-tip" CACHE STRING "LEMON version string.")
 		ENDIF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
+		SET(PROJECT_NAME "LEMON")
 		PROJECT(${PROJECT_NAME})
-		SET(CMAKE_MODULE_PATH ${CMAKE_SOURCE_DIR}/cmake)
+		IF(EXISTS ${PROJECT_SOURCE_DIR}/cmake/version.cmake)
 		  INCLUDE(${PROJECT_SOURCE_DIR}/cmake/version.cmake)
 		ELSEIF(DEFINED ENV{LEMON_VERSION})
 		  SET(LEMON_VERSION $ENV{LEMON_VERSION} CACHE STRING "LEMON version string.")
 		ELSE()
 		  EXECUTE_PROCESS(
 		    COMMAND hg id -i
 		    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
 		    OUTPUT_VARIABLE HG_REVISION
 		    ERROR_QUIET
 		    OUTPUT_STRIP_TRAILING_WHITESPACE
+		  )
 		  IF(HG_REVISION STREQUAL "")
 		    SET(HG_REVISION "hg-tip")
 		  ENDIF()
 		  SET(LEMON_VERSION ${HG_REVISION} CACHE STRING "LEMON version string.")
 		ENDIF()
 		INCLUDE(FindDoxygen)
 		INCLUDE(FindGhostscript)
 		SET(PROJECT_VERSION ${LEMON_VERSION})
-		ADD_DEFINITIONS(-DHAVE_CONFIG_H)
+		SET(CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR}/cmake)
 		FIND_PACKAGE(Doxygen)
 		FIND_PACKAGE(Ghostscript)
 		FIND_PACKAGE(GLPK 4.33)
 		FIND_PACKAGE(CPLEX)
 		FIND_PACKAGE(COIN)
 		INCLUDE(CheckTypeSize)
-		CHECK_TYPE_SIZE("long long" LEMON_LONG_LONG)
+		CHECK_TYPE_SIZE("long long" LONG_LONG)
 		SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
 		INCLUDE(FindPythonInterp)
@@ -24,7 +42,27 @@
 		ADD_SUBDIRECTORY(lemon)
 		ADD_SUBDIRECTORY(demo)
 		ADD_SUBDIRECTORY(doc)
-		ADD_SUBDIRECTORY(test)
+		IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
 		  ADD_SUBDIRECTORY(demo)
 		  ADD_SUBDIRECTORY(tools)
 		  ADD_SUBDIRECTORY(doc)
 		  ADD_SUBDIRECTORY(test)
 		ENDIF()
-		IF(WIN32)
+		CONFIGURE_FILE(
 		  ${PROJECT_SOURCE_DIR}/cmake/LEMONConfig.cmake.in
 		  ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
 		  @ONLY
+		)
 		IF(UNIX)
 		  INSTALL(
 		    FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
 		    DESTINATION share/lemon/cmake
+		  )
 		ELSEIF(WIN32)
 		  INSTALL(
 		    FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
 		    DESTINATION cmake
+		  )
 		ENDIF()
 		IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR} AND WIN32)
 		  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
@@ -32,4 +70,4 @@
 		  SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
 		    "LEMON - Library of Efficient Models and Optimization in Networks")
 		  SET(CPACK_RESOURCE_FILE_LICENSE "${CMAKE_SOURCE_DIR}/LICENSE")
 		    "LEMON - Library for Efficient Modeling and Optimization in Networks")
 		  SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")
@@ -42,3 +80,3 @@
 		  SET(CPACK_COMPONENTS_ALL headers library html_documentation)
+		  SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
@@ -46,2 +84,3 @@
 		  SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
 		  SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities")
 		  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
@@ -52,2 +91,4 @@
 		    "DLL and import library")
 		  SET(CPACK_COMPONENT_BIN_DESCRIPTION
 		    "Command line utilities")
 		  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
@@ -73,5 +114,5 @@
 		  SET(CPACK_GENERATOR "NSIS")
 		  SET(CPACK_NSIS_MUI_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico")
 		  SET(CPACK_NSIS_MUI_UNIICON "${CMAKE_SOURCE_DIR}/cmake/nsis/uninstall.ico")
-		  #SET(CPACK_PACKAGE_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
+		  SET(CPACK_NSIS_MUI_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis/lemon.ico")
 		  SET(CPACK_NSIS_MUI_UNIICON "${PROJECT_SOURCE_DIR}/cmake/nsis/uninstall.ico")
 		  #SET(CPACK_PACKAGE_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
 		  SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
@@ -90,2 +131,2 @@
 		  INCLUDE(CPack)
-		ENDIF(WIN32)
 		ENDIF()

INSTALL

Show inline comments

@@ -29,4 +29,4 @@
 		      This command compiles the non-template part of LEMON into libemon.a
 		      file. It also compiles the programs in the tools and demo subdirectories
 		      when enabled.
 		      file. It also compiles the programs in the tools subdirectory by
 		      default.
@@ -77,10 +77,2 @@
 		--enable-demo
 		   Build the examples in the demo subdirectory.
 		--disable-demo
 		   Do not build the examples in the demo subdirectory (default).
 		--enable-tools
@@ -160,1 +152,24 @@
 		   Disable SoPlex support.
 		--with-coin[=PREFIX]
 		   Enable support for COIN-OR solvers (CLP and CBC). You should
 		   specify the prefix too. (by default, COIN-OR tools install
 		   themselves to the source code directory). This command enables the
 		   solvers that are actually found.
 		--with-coin-includedir=DIR
 		   The directory where the COIN-OR header files are located. This is
 		   only useful when the COIN-OR headers and libraries are not under
 		   the same prefix (which is unlikely).
 		--with-coin-libdir=DIR
 		   The directory where the COIN-OR libraries are located. This is only
 		   useful when the COIN-OR headers and libraries are not under the
 		   same prefix (which is unlikely).
 		--without-coin
 		   Disable COIN-OR support.

LICENSE

Show inline comments

@@ -3,3 +3,3 @@
-		Copyright (C) 2003-2008 Egervary Jeno Kombinatorikus Optimalizalasi
+		Copyright (C) 2003-2009 Egervary Jeno Kombinatorikus Optimalizalasi
 		Kutatocsoport (Egervary Combinatorial Optimization Research Group,

Makefile.am

Show inline comments

@@ -2,2 +2,4 @@
 		AM_CXXFLAGS = $(WARNINGCXXFLAGS)
 		AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir)
@@ -11,4 +13,9 @@
 			m4/lx_check_soplex.m4 \
 			m4/lx_check_coin.m4 \
 			CMakeLists.txt \
 			cmake/FindGhostscript.cmake \
 			cmake/FindCPLEX.cmake \
 			cmake/FindGLPK.cmake \
 			cmake/FindCOIN.cmake \
 			cmake/LEMONConfig.cmake.in \
 			cmake/version.cmake.in \
@@ -38,5 +45,9 @@
 		include doc/Makefile.am
 		include demo/Makefile.am
 		include tools/Makefile.am
 		DIST_SUBDIRS = demo
 		demo:
 			$(MAKE) $(AM_MAKEFLAGS) -C demo
 		MRPROPERFILES = \
@@ -67,2 +78,2 @@
-		.PHONY: mrproper dist-bz2 distcheck-bz2
+		.PHONY: demo mrproper dist-bz2 distcheck-bz2

NEWS

Show inline comments

 -05-13 Version 1.1 released
 		        This is the second stable release of the 1.x series. It
 		        features a better coverage of the tools available in the 0.x
 		        series, a thoroughly reworked LP/MIP interface plus various
 		        improvements in the existing tools.
 		        * Much improved M$ Windows support
 		          * Various improvements in the CMAKE build system
 		          * Compilation warnings are fixed/suppressed
 		        * Support IBM xlC compiler
 		        * New algorithms
 		          * Connectivity related algorithms (#61)
 		          * Euler walks (#65)
 		          * Preflow push-relabel max. flow algorithm (#176)
 		          * Circulation algorithm (push-relabel based) (#175)
 		          * Suurballe algorithm (#47)
 		          * Gomory-Hu algorithm (#66)
 		          * Hao-Orlin algorithm (#58)
 		          * Edmond's maximum cardinality and weighted matching algorithms
 		            in general graphs (#48,#265)
 		          * Minimum cost arborescence/branching (#60)
 		          * Network Simplex min. cost flow algorithm (#234)
 		        * New data structures
 		          * Full graph structure (#57)
 		          * Grid graph structure (#57)
 		          * Hypercube graph structure (#57)
 		          * Graph adaptors (#67)
 		          * ArcSet and EdgeSet classes (#67)
 		          * Elevator class (#174)
 		        * Other new tools
 		          * LP/MIP interface (#44)
 		            * Support for GLPK, CPLEX, Soplex, COIN-OR CLP and CBC
 		          * Reader for the Nauty file format (#55)
 		          * DIMACS readers (#167)
 		          * Radix sort algorithms (#72)
 		          * RangeIdMap and CrossRefMap (#160)
 		        * New command line tools
 		          * DIMACS to LGF converter (#182)
 		          * lgf-gen - a graph generator (#45)
 		          * DIMACS solver utility (#226)
 		        * Other code improvements
 		          * Lognormal distribution added to Random (#102)
 		          * Better (i.e. O(1) time) item counting in SmartGraph (#3)
 		          * The standard maps of graphs are guaranteed to be
 		            reference maps (#190)
 		        * Miscellaneous
 		          * Various doc improvements
 		          * Improved 0.x -> 1.x converter script
 		        * Several bugfixes (compared to release 1.0):
 		          #170: Bugfix SmartDigraph::split()
 		          #171: Bugfix in SmartGraph::restoreSnapshot()
 		          #172: Extended test cases for graphs and digraphs
 		          #173: Bugfix in Random
 		                * operator()s always return a double now
 		                * the faulty real<Num>(Num) and real<Num>(Num,Num)
 		                  have been removed
 		          #187: Remove DijkstraWidestPathOperationTraits
 		          #61:  Bugfix in DfsVisit
 		          #193: Bugfix in GraphReader::skipSection()
 		          #195: Bugfix in ConEdgeIt()
 		          #197: Bugfix in heap unionfind
 		                * This bug affects Edmond's general matching algorithms
 		          #207: Fix 'make install' without 'make html' using CMAKE
 		          #208: Suppress or fix VS2008 compilation warnings
 		          ----: Update the LEMON icon
 		          ----: Enable the component-based installer
 		                (in installers made by CPACK)
 		          ----: Set the proper version for CMAKE in the tarballs
 		                (made by autotools)
 		          ----: Minor clarification in the LICENSE file
 		          ----: Add missing unistd.h include to time_measure.h
 		          #204: Compilation bug fixed in graph_to_eps.h with VS2005
 		          #214,#215: windows.h should never be included by lemon headers
 		          #230: Build systems check the availability of 'long long' type
 		          #229: Default implementation of Tolerance<> is used for integer types
 		          #211,#212: Various fixes for compiling on AIX
 		          ----: Improvements in CMAKE config
 		                - docs is installed in share/doc/
 		                - detects newer versions of Ghostscript
 		          #239: Fix missing 'inline' specifier in time_measure.h
 		          #274,#280: Install lemon/config.h
 		          #275: Prefix macro names with LEMON_ in lemon/config.h
 		          ----: Small script for making the release tarballs added
 		          ----: Minor improvement in unify-sources.sh (a76f55d7d397)
 -03-27 LEMON joins to the COIN-OR initiative

README

Show inline comments

 		==================================================================
 		LEMON - a Library of Efficient Models and Optimization in Networks
 		==================================================================
+		=====================================================================
 		LEMON - a Library for Efficient Modeling and Optimization in Networks
 		=====================================================================

cmake/version.cmake.in

Show inline comments

 		SET(PROJECT_NAME "@PACKAGE_NAME@")
 		SET(PROJECT_VERSION "@PACKAGE_VERSION@" CACHE STRING "LEMON version string.")
 		SET(LEMON_VERSION "@PACKAGE_VERSION@" CACHE STRING "LEMON version string.")

configure.ac

Show inline comments

@@ -4,10 +4,13 @@
 		m4_define([lemon_version_number],
-			[m4_normalize(esyscmd([echo ${LEMON_VERSION}]))])
+		          [m4_normalize(esyscmd([echo ${LEMON_VERSION}]))])
 		dnl m4_define([lemon_version_number], [])
 		m4_define([lemon_hg_path], [m4_normalize(esyscmd([./scripts/chg-len.py]))])
 		m4_define([lemon_hg_revision], [m4_normalize(esyscmd([hg id -i]))])
+		m4_define([lemon_hg_revision], [m4_normalize(esyscmd([hg id -i 2> /dev/null]))])
 		m4_define([lemon_version], [ifelse(lemon_version_number(),
 					   [],
 					   [lemon_hg_path().lemon_hg_revision()],
-					   [lemon_version_number()])])
+		                           [],
 		                           [ifelse(lemon_hg_revision(),
 		                           [],
 		                           [hg-tip],
 		                           [lemon_hg_path().lemon_hg_revision()])],
 		                           [lemon_version_number()])])
@@ -21,3 +24,3 @@
-		lx_cmdline_cxxflags_set=${CXXFLAGS+set}
+		AC_DEFINE([LEMON_VERSION], [lemon_version()], [The version string])
@@ -40,2 +43,3 @@
 		AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
 		AC_CHECK_PROG([python_found],[python],[yes],[no])
 		AC_CHECK_PROG([gs_found],[gs],[yes],[no])
@@ -54,23 +58,15 @@
 		dnl Set custom compiler flags when using g++.
 		if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes -a "$ICC" = no; then
 		  CXXFLAGS="$CXXFLAGS -Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas"
 		if test "$GXX" = yes -a "$ICC" = no; then
 		  WARNINGCXXFLAGS="-Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas"
 		fi
 		AC_SUBST([WARNINGCXXFLAGS])
 		dnl Checks for libraries.
 		#LX_CHECK_GLPK
 		#LX_CHECK_CPLEX
-		#LX_CHECK_SOPLEX
+		LX_CHECK_GLPK
 		LX_CHECK_CPLEX
 		LX_CHECK_SOPLEX
 		LX_CHECK_COIN
 		dnl Disable/enable building the demo programs.
 		AC_ARG_ENABLE([demo],
 		AS_HELP_STRING([--enable-demo], [build the demo programs])
 		AS_HELP_STRING([--disable-demo], [do not build the demo programs @<:@default@:>@]),
 		              [], [enable_demo=no])
 		AC_MSG_CHECKING([whether to build the demo programs])
 		if test x"$enable_demo" != x"no"; then
 		  AC_MSG_RESULT([yes])
 		else
 		  AC_MSG_RESULT([no])
 		fi
 		AM_CONDITIONAL([WANT_DEMO], [test x"$enable_demo" != x"no"])
 		AM_CONDITIONAL([HAVE_LP], [test x"$lx_lp_found" = x"yes"])
 		AM_CONDITIONAL([HAVE_MIP], [test x"$lx_mip_found" = x"yes"])
@@ -109,2 +105,3 @@
 		Makefile
 		demo/Makefile
 		cmake/version.cmake
@@ -122,3 +119,3 @@
 		echo C++ compiler.................. : $CXX
 		echo C++ compiles flags............ : $CXXFLAGS
+		echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
 		echo
@@ -126,7 +123,8 @@
 		echo
 		#echo GLPK support.................. : $lx_glpk_found
 		#echo CPLEX support................. : $lx_cplex_found
 		#echo SOPLEX support................ : $lx_soplex_found
 		#echo
-		echo Build demo programs........... : $enable_demo
+		echo GLPK support.................. : $lx_glpk_found
 		echo CPLEX support................. : $lx_cplex_found
 		echo SOPLEX support................ : $lx_soplex_found
 		echo CLP support................... : $lx_clp_found
 		echo CBC support................... : $lx_cbc_found
 		echo
 		echo Build additional tools........ : $enable_tools

demo/CMakeLists.txt

Show inline comments

 		INCLUDE_DIRECTORIES(
-		  ${CMAKE_SOURCE_DIR}
+		  ${PROJECT_SOURCE_DIR}
 		  ${PROJECT_BINARY_DIR}
@@ -5,3 +5,5 @@
-		LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
 		LINK_DIRECTORIES(
 		  ${PROJECT_BINARY_DIR}/lemon
+		)
@@ -10,3 +12,4 @@
 		  graph_to_eps_demo
-		  lgf_demo)
 		  lgf_demo
+		)
@@ -15,2 +18,2 @@
 		  TARGET_LINK_LIBRARIES(${DEMO_NAME} lemon)
-		ENDFOREACH(DEMO_NAME)
 		ENDFOREACH()

demo/Makefile.am

Show inline comments

 		EXTRA_DIST += \
 			demo/CMakeLists.txt \
-			demo/digraph.lgf
+		AM_CXXFLAGS = $(WARNINGCXXFLAGS)
-		if WANT_DEMO
+		AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir)
 		LDADD = $(top_builddir)/lemon/libemon.la
 		noinst_PROGRAMS += \
 			demo/arg_parser_demo \
 			demo/graph_to_eps_demo \
 			demo/lgf_demo
 		EXTRA_DIST = \
 			CMakeLists.txt \
 			digraph.lgf
-		endif WANT_DEMO
+		noinst_PROGRAMS = \
 			arg_parser_demo \
 			graph_to_eps_demo \
 			lgf_demo
 		demo_arg_parser_demo_SOURCES = demo/arg_parser_demo.cc
 		demo_graph_to_eps_demo_SOURCES = demo/graph_to_eps_demo.cc
-		demo_lgf_demo_SOURCES = demo/lgf_demo.cc
+		arg_parser_demo_SOURCES = arg_parser_demo.cc
 		graph_to_eps_demo_SOURCES = graph_to_eps_demo.cc
 		lgf_demo_SOURCES = lgf_demo.cc

demo/arg_parser_demo.cc

Show inline comments

@@ -4,3 +4,3 @@
+		 *
-		 * Copyright (C) 2003-2008
+		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

demo/graph_to_eps_demo.cc

Show inline comments

@@ -4,3 +4,3 @@
+		 *
-		 * Copyright (C) 2003-2008
+		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
@@ -87,3 +87,3 @@
 		    title("Sample .eps figure").
-		    copyright("(C) 2003-2008 LEMON Project").
+		    copyright("(C) 2003-2009 LEMON Project").
 		    run();
@@ -94,3 +94,3 @@
 		    title("Sample .eps figure").
-		    copyright("(C) 2003-2008 LEMON Project").
+		    copyright("(C) 2003-2009 LEMON Project").
 		    absoluteNodeSizes().absoluteArcWidths().
@@ -107,3 +107,3 @@
 		    title("Sample .eps figure (with arrowheads)").
-		    copyright("(C) 2003-2008 LEMON Project").
+		    copyright("(C) 2003-2009 LEMON Project").
 		    absoluteNodeSizes().absoluteArcWidths().
@@ -134,3 +134,3 @@
 		    title("Sample .eps figure (parallel arcs)").
-		    copyright("(C) 2003-2008 LEMON Project").
+		    copyright("(C) 2003-2009 LEMON Project").
 		    absoluteNodeSizes().absoluteArcWidths().
@@ -149,3 +149,3 @@
 		    title("Sample .eps figure (parallel arcs and arrowheads)").
-		    copyright("(C) 2003-2008 LEMON Project").
+		    copyright("(C) 2003-2009 LEMON Project").
 		    absoluteNodeSizes().absoluteArcWidths().
@@ -165,3 +165,3 @@
 		    title("Sample .eps figure (fits to A4)").
-		    copyright("(C) 2003-2008 LEMON Project").
+		    copyright("(C) 2003-2009 LEMON Project").
 		    scaleToA4().
@@ -184,3 +184,3 @@
 		  int cols=int(sqrt(double(palette.size())));
+		  int cols=int(std::sqrt(double(palette.size())));
 		  for(int i=0;i<int(paletteW.size());i++) {
@@ -195,3 +195,3 @@
 		    title("Sample .eps figure (Palette demo)").
-		    copyright("(C) 2003-2008 LEMON Project").
+		    copyright("(C) 2003-2009 LEMON Project").
 		    coords(hcoords).

demo/lgf_demo.cc

Show inline comments

@@ -4,3 +4,3 @@
+		 *
-		 * Copyright (C) 2003-2008
+		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

doc/CMakeLists.txt

Show inline comments

@@ -2,41 +2,51 @@
 		SET(PACKAGE_VERSION ${PROJECT_VERSION})
 		SET(abs_top_srcdir ${CMAKE_SOURCE_DIR})
 		SET(abs_top_builddir ${CMAKE_BINARY_DIR})
 		SET(abs_top_srcdir ${PROJECT_SOURCE_DIR})
 		SET(abs_top_builddir ${PROJECT_BINARY_DIR})
 		CONFIGURE_FILE(
 		  ${CMAKE_SOURCE_DIR}/doc/Doxyfile.in
 		  ${CMAKE_BINARY_DIR}/doc/Doxyfile
-		  @ONLY)
+		  ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in
 		  ${PROJECT_BINARY_DIR}/doc/Doxyfile
 		  @ONLY
+		)
 		IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
+		IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE)
 		  FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)
 		  SET(GHOSTSCRIPT_OPTIONS -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha)
 		  ADD_CUSTOM_TARGET(html
 		    COMMAND ${CMAKE_COMMAND} -E remove_directory gen-images
 		    COMMAND ${CMAKE_COMMAND} -E make_directory gen-images
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
 		    COMMAND ${CMAKE_COMMAND} -E remove_directory html
 		    COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
 		    COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
 		    WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
+		  )
 		  SET_TARGET_PROPERTIES(html PROPERTIES PROJECT_LABEL BUILD_DOC)
 		  IF(UNIX)
 		    ADD_CUSTOM_TARGET(html
 		      COMMAND rm -rf gen-images
 		      COMMAND mkdir gen-images
 		      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
 		      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
 		      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
 		      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
 		      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
 		      COMMAND rm -rf html
 		      COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
-		      WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR})
+		    INSTALL(
 		      DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
 		      DESTINATION share/doc/lemon/html
 		      COMPONENT html_documentation
+		    )
 		  ELSEIF(WIN32)
 		    ADD_CUSTOM_TARGET(html
 		      COMMAND if exist gen-images rmdir /s /q gen-images
 		      COMMAND mkdir gen-images
 		      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
 		      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
 		      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
 		      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
 		      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
 		      COMMAND if exist html rmdir /s /q html
 		      COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
 		      WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR})
 		  ENDIF(UNIX)
 		  INSTALL(
 		    DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
 		    DESTINATION share/doc
 		    COMPONENT html_documentation)
-		ENDIF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
+		    INSTALL(
 		      DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
 		      DESTINATION doc
 		      COMPONENT html_documentation
+		    )
 		  ENDIF()
 		ENDIF()

doc/Doxyfile.in

Show inline comments

-		# Doxyfile 1.5.7.1
+		# Doxyfile 1.5.9
@@ -23,3 +23,2 @@
 		MULTILINE_CPP_IS_BRIEF = NO
 		DETAILS_AT_TOP         = YES
 		INHERIT_DOCS           = NO
@@ -68,3 +67,3 @@
 		MAX_INITIALIZER_LINES  = 5
-		SHOW_USED_FILES        = YES
+		SHOW_USED_FILES        = NO
 		SHOW_DIRECTORIES       = YES
@@ -93,3 +92,4 @@
 		                         "@abs_top_srcdir@/tools" \
 		                         "@abs_top_srcdir@/test/test_tools.h"
+		                         "@abs_top_srcdir@/test/test_tools.h" \
 		                         "@abs_top_builddir@/doc/references.dox"
 		INPUT_ENCODING         = UTF-8
@@ -225,3 +225,3 @@
 		#---------------------------------------------------------------------------
-		# Configuration::additions related to external references
+		# Options related to the search engine
 		#---------------------------------------------------------------------------

doc/Makefile.am

Show inline comments

@@ -10,2 +10,3 @@
 			doc/migration.dox \
 			doc/min_cost_flow.dox \
 			doc/named-param.dox \
@@ -16,2 +17,3 @@
 		DOC_EPS_IMAGES18 = \
 			grid_graph.eps \
 			nodeshape_0.eps \
@@ -22,4 +24,13 @@
 		DOC_EPS_IMAGES27 = \
 			bipartite_matching.eps \
 			bipartite_partitions.eps \
 			connected_components.eps \
 			edge_biconnected_components.eps \
 			node_biconnected_components.eps \
 			strongly_connected_components.eps
 		DOC_EPS_IMAGES = \
 			$(DOC_EPS_IMAGES18)
+			$(DOC_EPS_IMAGES18) \
 			$(DOC_EPS_IMAGES27)
@@ -46,3 +57,26 @@
-		html-local: $(DOC_PNG_IMAGES)
+		$(DOC_EPS_IMAGES27:%.eps=doc/gen-images/%.png): doc/gen-images/%.png: doc/images/%.eps
 			-mkdir doc/gen-images
 			if test ${gs_found} = yes; then \
 			  $(GS_COMMAND) -sDEVICE=pngalpha -r27 -sOutputFile=$@ $<; \
 			else \
 			  echo; \
 			  echo "Ghostscript not found."; \
 			  echo; \
 			  exit 1; \
 			fi
 		references.dox: doc/references.bib
 			if test ${python_found} = yes; then \
 			  cd doc; \
 			  python @abs_top_srcdir@/scripts/bib2dox.py @abs_top_builddir@/$< >$@; \
 			  cd ..; \
 			else \
 			  echo; \
 			  echo "Python not found."; \
 			  echo; \
 			  exit 1; \
 			fi
 		html-local: $(DOC_PNG_IMAGES) references.dox
 			if test ${doxygen_found} = yes; then \
@@ -71,7 +105,7 @@
 			@$(NORMAL_INSTALL)
-			$(mkinstalldirs) $(DESTDIR)$(htmldir)/docs
+			$(mkinstalldirs) $(DESTDIR)$(htmldir)/html
 			for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
 			  f="`echo $$p | sed -e 's|^.*/||'`"; \
 			  echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f"; \
 			  $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f; \
 			  echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f"; \
 			  $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f; \
 			done
@@ -82,4 +116,4 @@
 			  f="`echo $$p | sed -e 's|^.*/||'`"; \
 			  echo " rm -f $(DESTDIR)$(htmldir)/docs/$$f"; \
 			  rm -f $(DESTDIR)$(htmldir)/docs/$$f; \
 			  echo " rm -f $(DESTDIR)$(htmldir)/html/$$f"; \
 			  rm -f $(DESTDIR)$(htmldir)/html/$$f; \
 			done

doc/coding_style.dox

Show inline comments

@@ -4,3 +4,3 @@
+		 *
-		 * Copyright (C) 2003-2008
+		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

doc/dirs.dox

Show inline comments

@@ -4,3 +4,3 @@
+		 *
-		 * Copyright (C) 2003-2008
+		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
@@ -73,3 +73,3 @@
-		This directory contains some auxiliary classes for implementing graphs,
 		This directory contains some auxiliary classes for implementing graphs,
 		maps and some other classes.

doc/groups.dox

Show inline comments

@@ -4,3 +4,3 @@
+		 *
-		 * Copyright (C) 2003-2008
+		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
@@ -18,5 +18,7 @@
 		namespace lemon {
 		/**
 		@defgroup datas Data Structures
-		This group describes the several data structures implemented in LEMON.
+		This group contains the several data structures implemented in LEMON.
 		*/
@@ -62,9 +64,75 @@
 		/**
-		@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
+		@defgroup graph_adaptors Adaptor Classes for Graphs
 		@ingroup graphs
-		\brief Graph types between real graphs and graph adaptors.
+		\brief Adaptor classes for digraphs and graphs
 		This group describes some graph types between real graphs and graph adaptors.
 		These classes wrap graphs to give new functionality as the adaptors do it.
-		On the other hand they are not light-weight structures as the adaptors.
+		This group contains several useful adaptor classes for digraphs and graphs.
 		The main parts of LEMON are the different graph structures, generic
 		graph algorithms, graph concepts, which couple them, and graph
 		adaptors. While the previous notions are more or less clear, the
 		latter one needs further explanation. Graph adaptors are graph classes
 		which serve for considering graph structures in different ways.
 		A short example makes this much clearer.  Suppose that we have an
 		instance \c g of a directed graph type, say ListDigraph and an algorithm
 		\code
 		template <typename Digraph>
 		int algorithm(const Digraph&);
 		\endcode
 		is needed to run on the reverse oriented graph.  It may be expensive
 		(in time or in memory usage) to copy \c g with the reversed
 		arcs.  In this case, an adaptor class is used, which (according
 		to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
 		The adaptor uses the original digraph structure and digraph operations when
 		methods of the reversed oriented graph are called.  This means that the adaptor
 		have minor memory usage, and do not perform sophisticated algorithmic
 		actions.  The purpose of it is to give a tool for the cases when a
 		graph have to be used in a specific alteration.  If this alteration is
 		obtained by a usual construction like filtering the node or the arc set or
 		considering a new orientation, then an adaptor is worthwhile to use.
 		To come back to the reverse oriented graph, in this situation
 		\code
 		template<typename Digraph> class ReverseDigraph;
 		\endcode
 		template class can be used. The code looks as follows
 		\code
 		ListDigraph g;
 		ReverseDigraph<ListDigraph> rg(g);
 		int result = algorithm(rg);
 		\endcode
 		During running the algorithm, the original digraph \c g is untouched.
 		This techniques give rise to an elegant code, and based on stable
 		graph adaptors, complex algorithms can be implemented easily.
 		In flow, circulation and matching problems, the residual
 		graph is of particular importance. Combining an adaptor implementing
 		this with shortest path algorithms or minimum mean cycle algorithms,
 		a range of weighted and cardinality optimization algorithms can be
 		obtained. For other examples, the interested user is referred to the
 		detailed documentation of particular adaptors.
 		The behavior of graph adaptors can be very different. Some of them keep
 		capabilities of the original graph while in other cases this would be
 		meaningless. This means that the concepts that they meet depend
 		on the graph adaptor, and the wrapped graph.
 		For example, if an arc of a reversed digraph is deleted, this is carried
 		out by deleting the corresponding arc of the original digraph, thus the
 		adaptor modifies the original digraph.
 		However in case of a residual digraph, this operation has no sense.
 		Let us stand one more example here to simplify your work.
 		ReverseDigraph has constructor
 		\code
 		ReverseDigraph(Digraph& digraph);
 		\endcode
 		This means that in a situation, when a <tt>const %ListDigraph&</tt>
 		reference to a graph is given, then it have to be instantiated with
 		<tt>Digraph=const %ListDigraph</tt>.
 		\code
 		int algorithm1(const ListDigraph& g) {
 		  ReverseDigraph<const ListDigraph> rg(g);
 		  return algorithm2(rg);
+		}
 		\endcode
 		*/
@@ -76,3 +144,3 @@
-		This group describes the map structures implemented in LEMON.
+		This group contains the map structures implemented in LEMON.
@@ -89,4 +157,7 @@
 		This group describes maps that are specifically designed to assign
 		values to the nodes and arcs of graphs.
 		This group contains maps that are specifically designed to assign
 		values to the nodes and arcs/edges of graphs.
 		If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
 		\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
 		*/
@@ -98,6 +169,6 @@
-		This group describes map adaptors that are used to create "implicit"
+		This group contains map adaptors that are used to create "implicit"
 		maps from other maps.
-		Most of them are \ref lemon::concepts::ReadMap "read-only maps".
 		Most of them are \ref concepts::ReadMap "read-only maps".
 		They can make arithmetic and logical operations between one or two maps
@@ -157,10 +228,2 @@
 		/**
 		@defgroup matrices Matrices
 		@ingroup datas
 		\brief Two dimensional data storages implemented in LEMON.
 		This group describes two dimensional data storages implemented in LEMON.
 		*/
 		/**
 		@defgroup paths Path Structures
@@ -169,3 +232,3 @@
-		This group describes the path structures implemented in LEMON.
+		This group contains the path structures implemented in LEMON.
@@ -177,3 +240,32 @@
-		\sa lemon::concepts::Path
+		\sa \ref concepts::Path "Path concept"
 		*/
 		/**
 		@defgroup heaps Heap Structures
 		@ingroup datas
 		\brief %Heap structures implemented in LEMON.
 		This group contains the heap structures implemented in LEMON.
 		LEMON provides several heap classes. They are efficient implementations
 		of the abstract data type \e priority \e queue. They store items with
 		specified values called \e priorities in such a way that finding and
 		removing the item with minimum priority are efficient.
 		The basic operations are adding and erasing items, changing the priority
 		of an item, etc.
 		Heaps are crucial in several algorithms, such as Dijkstra and Prim.
 		The heap implementations have the same interface, thus any of them can be
 		used easily in such algorithms.
 		\sa \ref concepts::Heap "Heap concept"
 		*/
 		/**
 		@defgroup matrices Matrices
 		@ingroup datas
 		\brief Two dimensional data storages implemented in LEMON.
 		This group contains two dimensional data storages implemented in LEMON.
 		*/
@@ -185,3 +277,3 @@
-		This group describes some data structures implemented in LEMON in
+		This group contains some data structures implemented in LEMON in
 		order to make it easier to implement combinatorial algorithms.
@@ -190,7 +282,29 @@
 		/**
 		@defgroup geomdat Geometric Data Structures
 		@ingroup auxdat
 		\brief Geometric data structures implemented in LEMON.
 		This group contains geometric data structures implemented in LEMON.
 		 - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
 		   vector with the usual operations.
 		 - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
 		   rectangular bounding box of a set of \ref lemon::dim2::Point
 		   "dim2::Point"'s.
 		*/
 		/**
 		@defgroup matrices Matrices
 		@ingroup auxdat
 		\brief Two dimensional data storages implemented in LEMON.
 		This group contains two dimensional data storages implemented in LEMON.
 		*/
 		/**
 		@defgroup algs Algorithms
-		\brief This group describes the several algorithms
+		\brief This group contains the several algorithms
 		implemented in LEMON.
-		This group describes the several algorithms
+		This group contains the several algorithms
 		implemented in LEMON.
@@ -203,4 +317,5 @@
 		This group describes the common graph search algorithms like
 		Breadth-First Search (BFS) and Depth-First Search (DFS).
 		This group contains the common graph search algorithms, namely
 		\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
 		\ref clrs01algorithms.
 		*/
@@ -212,3 +327,26 @@
-		This group describes the algorithms for finding shortest paths in graphs.
+		This group contains the algorithms for finding shortest paths in digraphs
 		\ref clrs01algorithms.
 		 - \ref Dijkstra algorithm for finding shortest paths from a source node
 		   when all arc lengths are non-negative.
 		 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
 		   from a source node when arc lenghts can be either positive or negative,
 		   but the digraph should not contain directed cycles with negative total
 		   length.
 		 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
 		   for solving the \e all-pairs \e shortest \e paths \e problem when arc
 		   lenghts can be either positive or negative, but the digraph should
 		   not contain directed cycles with negative total length.
 		 - \ref Suurballe A successive shortest path algorithm for finding
 		   arc-disjoint paths between two nodes having minimum total length.
 		*/
 		/**
 		@defgroup spantree Minimum Spanning Tree Algorithms
 		@ingroup algs
 		\brief Algorithms for finding minimum cost spanning trees and arborescences.
 		This group contains the algorithms for finding minimum cost spanning
 		trees and arborescences \ref clrs01algorithms.
 		*/
@@ -220,26 +358,36 @@
 		This group describes the algorithms for finding maximum flows and
 		feasible circulations.
 		This group contains the algorithms for finding maximum flows and
 		feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
 		The maximum flow problem is to find a flow between a single source and
 		a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
 		directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
 		function and given \f$s, t \in V\f$ source and target node. The
-		maximum flow is the \f$f_a\f$ solution of the next optimization problem:
+		The \e maximum \e flow \e problem is to find a flow of maximum value between
 		a single source and a single target. Formally, there is a \f$G=(V,A)\f$
 		digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
 		\f$s, t \in V\f$ source and target nodes.
 		A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
 		following optimization problem.
 		\f[ 0 \le f_a \le c_a \f]
 		\f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
 		\qquad \forall u \in V \setminus \{s,t\}\f]
 		\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
 		\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
 		\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
 		    \quad \forall u\in V\setminus\{s,t\} \f]
 		\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
 		LEMON contains several algorithms for solving maximum flow problems:
 		- \ref lemon::EdmondsKarp "Edmonds-Karp"
 		- \ref lemon::Preflow "Goldberg's Preflow algorithm"
 		- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
 		- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
 		- \ref EdmondsKarp Edmonds-Karp algorithm
 		  \ref edmondskarp72theoretical.
 		- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
 		  \ref goldberg88newapproach.
 		- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
 		  \ref dinic70algorithm, \ref sleator83dynamic.
 		- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
 		  \ref goldberg88newapproach, \ref sleator83dynamic.
 		In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
 		fastest method to compute the maximum flow. All impelementations
 		provides functions to query the minimum cut, which is the dual linear
 		programming problem of the maximum flow.
 		In most cases the \ref Preflow algorithm provides the
 		fastest method for computing a maximum flow. All implementations
 		also provide functions to query the minimum cut, which is the dual
 		problem of maximum flow.
 		\ref Circulation is a preflow push-relabel algorithm implemented directly
 		for finding feasible circulations, which is a somewhat different problem,
 		but it is strongly related to maximum flow.
 		For more information, see \ref Circulation.
 		*/
@@ -247,3 +395,3 @@
 		/**
-		@defgroup min_cost_flow Minimum Cost Flow Algorithms
+		@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
 		@ingroup algs
@@ -252,4 +400,24 @@
 		This group describes the algorithms for finding minimum cost flows and
 		circulations.
 		This group contains the algorithms for finding minimum cost flows and
 		circulations \ref amo93networkflows. For more information about this
 		problem and its dual solution, see \ref min_cost_flow
 		"Minimum Cost Flow Problem".
 		LEMON contains several algorithms for this problem.
 		 - \ref NetworkSimplex Primal Network Simplex algorithm with various
 		   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
 		 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
 		   cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
 		   \ref bunnagel98efficient.
 		 - \ref CapacityScaling Successive Shortest %Path algorithm with optional
 		   capacity scaling \ref edmondskarp72theoretical.
 		 - \ref CancelAndTighten The Cancel and Tighten algorithm
 		   \ref goldberg89cyclecanceling.
 		 - \ref CycleCanceling Cycle-Canceling algorithms
 		   \ref klein67primal, \ref goldberg89cyclecanceling.
 		In general NetworkSimplex is the most efficient implementation,
 		but in special cases other algorithms could be faster.
 		For example, if the total supply and/or capacities are rather small,
 		CapacityScaling is usually the fastest algorithm (without effective scaling).
 		*/
@@ -262,8 +430,8 @@
-		This group describes the algorithms for finding minimum cut in graphs.
+		This group contains the algorithms for finding minimum cut in graphs.
 		The minimum cut problem is to find a non-empty and non-complete
 		\f$X\f$ subset of the vertices with minimum overall capacity on
 		outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
 		\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
 		The \e minimum \e cut \e problem is to find a non-empty and non-complete
 		\f$X\f$ subset of the nodes with minimum overall capacity on
 		outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
 		\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
 		cut is the \f$X\f$ solution of the next optimization problem:
@@ -271,3 +439,3 @@
 		\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
-		\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
+		    \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
@@ -275,11 +443,11 @@
 		- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
 		  in directed graphs
 		- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
 		  calculate minimum cut in undirected graphs
 		- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
 		  pairs minimum cut in undirected graphs
 		- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
 		  in directed graphs.
 		- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
 		  calculating minimum cut in undirected graphs.
 		- \ref GomoryHu "Gomory-Hu tree computation" for calculating
 		  all-pairs minimum cut in undirected graphs.
 		If you want to find minimum cut just between two distinict nodes,
-		please see the \ref max_flow "Maximum Flow page".
+		see the \ref max_flow "maximum flow problem".
 		*/
@@ -287,3 +455,80 @@
 		/**
-		@defgroup graph_prop Connectivity and Other Graph Properties
+		@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
 		@ingroup algs
 		\brief Algorithms for finding minimum mean cycles.
 		This group contains the algorithms for finding minimum mean cycles
 		\ref clrs01algorithms, \ref amo93networkflows.
 		The \e minimum \e mean \e cycle \e problem is to find a directed cycle
 		of minimum mean length (cost) in a digraph.
 		The mean length of a cycle is the average length of its arcs, i.e. the
 		ratio between the total length of the cycle and the number of arcs on it.
 		This problem has an important connection to \e conservative \e length
 		\e functions, too. A length function on the arcs of a digraph is called
 		conservative if and only if there is no directed cycle of negative total
 		length. For an arbitrary length function, the negative of the minimum
 		cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
 		arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
 		function.
 		LEMON contains three algorithms for solving the minimum mean cycle problem:
 		- \ref Karp "Karp"'s original algorithm \ref amo93networkflows,
 		  \ref dasdan98minmeancycle.
 		- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
 		  version of Karp's algorithm \ref dasdan98minmeancycle.
 		- \ref Howard "Howard"'s policy iteration algorithm
 		  \ref dasdan98minmeancycle.
 		In practice, the Howard algorithm proved to be by far the most efficient
 		one, though the best known theoretical bound on its running time is
 		exponential.
 		Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
 		O(n<sup>2</sup>+e), but the latter one is typically faster due to the
 		applied early termination scheme.
 		*/
 		/**
 		@defgroup matching Matching Algorithms
 		@ingroup algs
 		\brief Algorithms for finding matchings in graphs and bipartite graphs.
 		This group contains the algorithms for calculating
 		matchings in graphs and bipartite graphs. The general matching problem is
 		finding a subset of the edges for which each node has at most one incident
 		edge.
 		There are several different algorithms for calculate matchings in
 		graphs.  The matching problems in bipartite graphs are generally
 		easier than in general graphs. The goal of the matching optimization
 		can be finding maximum cardinality, maximum weight or minimum cost
 		matching. The search can be constrained to find perfect or
 		maximum cardinality matching.
 		The matching algorithms implemented in LEMON:
 		- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
 		  for calculating maximum cardinality matching in bipartite graphs.
 		- \ref PrBipartiteMatching Push-relabel algorithm
 		  for calculating maximum cardinality matching in bipartite graphs.
 		- \ref MaxWeightedBipartiteMatching
 		  Successive shortest path algorithm for calculating maximum weighted
 		  matching and maximum weighted bipartite matching in bipartite graphs.
 		- \ref MinCostMaxBipartiteMatching
 		  Successive shortest path algorithm for calculating minimum cost maximum
 		  matching in bipartite graphs.
 		- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
 		  maximum cardinality matching in general graphs.
 		- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
 		  maximum weighted matching in general graphs.
 		- \ref MaxWeightedPerfectMatching
 		  Edmond's blossom shrinking algorithm for calculating maximum weighted
 		  perfect matching in general graphs.
 		\image html bipartite_matching.png
 		\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
 		*/
 		/**
 		@defgroup graph_properties Connectivity and Other Graph Properties
 		@ingroup algs
@@ -291,7 +536,7 @@
-		This group describes the algorithms for discovering the graph properties
+		This group contains the algorithms for discovering the graph properties
 		like connectivity, bipartiteness, euler property, simplicity etc.
 		\image html edge_biconnected_components.png
 		\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
 		\image html connected_components.png
 		\image latex connected_components.eps "Connected components" width=\textwidth
 		*/
@@ -303,3 +548,3 @@
-		This group describes the algorithms for planarity checking,
+		This group contains the algorithms for planarity checking,
 		embedding and drawing.
@@ -311,49 +556,8 @@
 		/**
-		@defgroup matching Matching Algorithms
+		@defgroup approx Approximation Algorithms
 		@ingroup algs
-		\brief Algorithms for finding matchings in graphs and bipartite graphs.
+		\brief Approximation algorithms.
 		This group contains algorithm objects and functions to calculate
 		matchings in graphs and bipartite graphs. The general matching problem is
 		finding a subset of the arcs which does not shares common endpoints.
 		There are several different algorithms for calculate matchings in
 		graphs.  The matching problems in bipartite graphs are generally
 		easier than in general graphs. The goal of the matching optimization
 		can be the finding maximum cardinality, maximum weight or minimum cost
 		matching. The search can be constrained to find perfect or
 		maximum cardinality matching.
 		LEMON contains the next algorithms:
 		- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
 		  augmenting path algorithm for calculate maximum cardinality matching in
 		  bipartite graphs
 		- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
 		  algorithm for calculate maximum cardinality matching in bipartite graphs
 		- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
 		  Successive shortest path algorithm for calculate maximum weighted matching
 		  and maximum weighted bipartite matching in bipartite graph
 		- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
 		  Successive shortest path algorithm for calculate minimum cost maximum
 		  matching in bipartite graph
 		- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
 		  for calculate maximum cardinality matching in general graph
 		- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
 		  shrinking algorithm for calculate maximum weighted matching in general
 		  graph
 		- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
 		  Edmond's blossom shrinking algorithm for calculate maximum weighted
 		  perfect matching in general graph
 		\image html bipartite_matching.png
 		\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
 		*/
 		/**
 		@defgroup spantree Minimum Spanning Tree Algorithms
 		@ingroup algs
 		\brief Algorithms for finding a minimum cost spanning tree in a graph.
 		This group describes the algorithms for finding a minimum cost spanning
-		tree in a graph
+		This group contains the approximation and heuristic algorithms
 		implemented in LEMON.
 		*/
@@ -365,3 +569,3 @@
-		This group describes some algorithms implemented in LEMON
+		This group contains some algorithms implemented in LEMON
 		in order to make it easier to implement complex algorithms.
@@ -370,7 +574,7 @@
 		/**
 		@defgroup approx Approximation Algorithms
 		@ingroup algs
-		\brief Approximation algorithms.
+		@defgroup gen_opt_group General Optimization Tools
 		\brief This group contains some general optimization frameworks
 		implemented in LEMON.
-		This group describes the approximation and heuristic algorithms
+		This group contains some general optimization frameworks
 		implemented in LEMON.
@@ -379,18 +583,12 @@
 		/**
 		@defgroup gen_opt_group General Optimization Tools
 		\brief This group describes some general optimization frameworks
-		implemented in LEMON.
+		@defgroup lp_group LP and MIP Solvers
 		@ingroup gen_opt_group
 		\brief LP and MIP solver interfaces for LEMON.
 		This group describes some general optimization frameworks
 		implemented in LEMON.
-		*/
+		This group contains LP and MIP solver interfaces for LEMON.
 		Various LP solvers could be used in the same manner with this
 		high-level interface.
 		/**
 		@defgroup lp_group Lp and Mip Solvers
 		@ingroup gen_opt_group
 		\brief Lp and Mip solver interfaces for LEMON.
 		This group describes Lp and Mip solver interfaces for LEMON. The
 		various LP solvers could be used in the same manner with this
 		interface.
 		The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
 		\ref cplex, \ref soplex.
 		*/
@@ -411,3 +609,3 @@
-		This group describes some metaheuristic optimization tools.
+		This group contains some metaheuristic optimization tools.
 		*/
@@ -426,3 +624,3 @@
-		This group describes some simple basic graph utilities.
+		This group contains some simple basic graph utilities.
 		*/
@@ -434,3 +632,3 @@
-		This group describes several useful tools for development,
+		This group contains several useful tools for development,
 		debugging and testing.
@@ -443,3 +641,3 @@
-		This group describes simple tools for measuring the performance
+		This group contains simple tools for measuring the performance
 		of algorithms.
@@ -452,3 +650,3 @@
-		This group describes the exceptions defined in LEMON.
+		This group contains the exceptions defined in LEMON.
 		*/
@@ -459,3 +657,3 @@
-		This group describes the tools for importing and exporting graphs
+		This group contains the tools for importing and exporting graphs
 		and graph related data. Now it supports the \ref lgf-format
@@ -466,3 +664,3 @@
 		/**
-		@defgroup lemon_io LEMON Input-Output
+		@defgroup lemon_io LEMON Graph Format
 		@ingroup io_group
@@ -470,3 +668,3 @@
-		This group describes methods for reading and writing
+		This group contains methods for reading and writing
 		\ref lgf-format "LEMON Graph Format".
@@ -479,3 +677,3 @@
-		This group describes general \c EPS drawing methods and special
+		This group contains general \c EPS drawing methods and special
 		graph exporting tools.
@@ -484,2 +682,18 @@
 		/**
 		@defgroup dimacs_group DIMACS Format
 		@ingroup io_group
 		\brief Read and write files in DIMACS format
 		Tools to read a digraph from or write it to a file in DIMACS format data.
 		*/
 		/**
 		@defgroup nauty_group NAUTY Format
 		@ingroup io_group
 		\brief Read \e Nauty format
 		Tool to read graphs from \e Nauty format data.
 		*/
 		/**
 		@defgroup concept Concepts
@@ -487,3 +701,3 @@
-		This group describes the data/algorithm skeletons and concept checking
+		This group contains the data/algorithm skeletons and concept checking
 		classes implemented in LEMON.
@@ -517,4 +731,4 @@
 		This group describes the skeletons and concept checking classes of LEMON's
 		graph structures and helper classes used to implement these.
 		This group contains the skeletons and concept checking classes of
 		graph structures.
 		*/
@@ -526,3 +740,3 @@
-		This group describes the skeletons and concept checking classes of maps.
+		This group contains the skeletons and concept checking classes of maps.
 		*/
@@ -530,15 +744,3 @@
 		/**
 		\anchor demoprograms
 		@defgroup demos Demo programs
 		Some demo programs are listed here. Their full source codes can be found in
 		the \c demo subdirectory of the source tree.
 		It order to compile them, use <tt>--enable-demo</tt> configure option when
 		build the library.
 		*/
 		/**
-		@defgroup tools Standalone utility applications
+		@defgroup tools Standalone Utility Applications
@@ -550,1 +752,14 @@
 		/**
 		\anchor demoprograms
 		@defgroup demos Demo Programs
 		Some demo programs are listed here. Their full source codes can be found in
 		the \c demo subdirectory of the source tree.
 		In order to compile them, use the <tt>make demo</tt> or the
 		<tt>make check</tt> commands.
 		*/
+		}

doc/lgf.dox

Show inline comments

@@ -4,3 +4,3 @@
+		 *
-		 * Copyright (C) 2003-2008
+		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

doc/license.dox

Show inline comments

@@ -4,3 +4,3 @@
+		 *
-		 * Copyright (C) 2003-2008
+		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

doc/mainpage.dox

Show inline comments

@@ -4,3 +4,3 @@
+		 *
-		 * Copyright (C) 2003-2008
+		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
@@ -23,11 +23,7 @@
 		\subsection whatis What is LEMON
 		LEMON stands for
 		<b>L</b>ibrary of <b>E</b>fficient <b>M</b>odels
 		and <b>O</b>ptimization in <b>N</b>etworks.
 		It is a C++ template
 		library aimed at combinatorial optimization tasks which
 		often involve in working
-		with graphs.
+		<b>LEMON</b> stands for <i><b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
 		and <b>O</b>ptimization in <b>N</b>etworks</i>.
 		It is a C++ template library providing efficient implementation of common
 		data structures and algorithms with focus on combinatorial optimization
 		problems in graphs and networks.
@@ -41,18 +37,18 @@
-		\subsection howtoread How to read the documentation
+		The project is maintained by the
 		<a href="http://www.cs.elte.hu/egres/">Egerv&aacute;ry Research Group on
 		Combinatorial Optimization</a> \ref egres
 		at the Operations Research Department of the
 		<a href="http://www.elte.hu/">E&ouml;tv&ouml;s Lor&aacute;nd University,
 		Budapest</a>, Hungary.
 		LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a>
 		initiative \ref coinor.
 		If you want to get a quick start and see the most important features then
 		take a look at our \ref quicktour
-		"Quick Tour to LEMON" which will guide you along.
+		\section howtoread How to Read the Documentation
 		If you already feel like using our library, see the page that tells you
 		\ref getstart "How to start using LEMON".
 		If you would like to get to know the library, see
 		<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
 		If you
 		want to see how LEMON works, see
 		some \ref demoprograms "demo programs".
 		If you know what you are looking for then try to find it under the
 		<a class="el" href="modules.html">Modules</a>
-		section.
+		If you know what you are looking for, then try to find it under the
 		<a class="el" href="modules.html">Modules</a> section.

doc/migration.dox

Show inline comments

@@ -4,3 +4,3 @@
+		 *
-		 * Copyright (C) 2003-2008
+		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
@@ -27,3 +27,3 @@
 		Many of these changes adjusted automatically by the
-		<tt>script/lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual
 		<tt>lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual
 		update are typeset <b>boldface</b>.
@@ -55,5 +55,7 @@
 		\warning
 		<b>The <tt>script/lemon-0.x-to-1.x.sh</tt> tool replaces all instances of
 		the words \c graph, \c digraph, \c edge and \c arc, so it replaces them
-		in strings, comments etc. as well as in all identifiers.</b>
+		<b>The <tt>lemon-0.x-to-1.x.sh</tt> script replaces the words \c graph,
 		\c ugraph, \c edge and \c uedge in your own identifiers and in
 		strings, comments etc. as well as in all LEMON specific identifiers.
 		So use the script carefully and make a backup copy of your source files
 		before applying the script to them.</b>

doc/named-param.dox

Show inline comments

@@ -4,3 +4,3 @@
+		 *
-		 * Copyright (C) 2003-2008
+		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

doc/namespaces.dox

Show inline comments

@@ -4,3 +4,3 @@
+		 *
-		 * Copyright (C) 2003-2008
+		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

doc/template.h

Show inline comments

@@ -4,3 +4,3 @@
+		 *
-		 * Copyright (C) 2003-2008
+		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

lemon/CMakeLists.txt

Show inline comments

 		INCLUDE_DIRECTORIES(
-		  ${CMAKE_SOURCE_DIR}
+		  ${PROJECT_SOURCE_DIR}
 		  ${PROJECT_BINARY_DIR}
@@ -10,3 +10,3 @@
-		ADD_LIBRARY(lemon
+		SET(LEMON_SOURCES
 		  arg_parser.cc
@@ -14,2 +14,4 @@
 		  color.cc
 		  lp_base.cc
 		  lp_skeleton.cc
 		  random.cc
@@ -18,2 +20,32 @@
 		IF(LEMON_HAVE_GLPK)
 		  SET(LEMON_SOURCES ${LEMON_SOURCES} glpk.cc)
 		  INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIRS})
 		  IF(WIN32)
 		    INSTALL(FILES ${GLPK_BIN_DIR}/glpk.dll DESTINATION bin)
 		    INSTALL(FILES ${GLPK_BIN_DIR}/libltdl3.dll DESTINATION bin)
 		    INSTALL(FILES ${GLPK_BIN_DIR}/zlib1.dll DESTINATION bin)
 		  ENDIF()
 		ENDIF()
 		IF(LEMON_HAVE_CPLEX)
 		  SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc)
 		  INCLUDE_DIRECTORIES(${CPLEX_INCLUDE_DIRS})
 		ENDIF()
 		IF(LEMON_HAVE_CLP)
 		  SET(LEMON_SOURCES ${LEMON_SOURCES} clp.cc)
 		  INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
 		ENDIF()
 		IF(LEMON_HAVE_CBC)
 		  SET(LEMON_SOURCES ${LEMON_SOURCES} cbc.cc)
 		  INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
 		ENDIF()
 		ADD_LIBRARY(lemon ${LEMON_SOURCES})
 		IF(UNIX)
 		  SET_TARGET_PROPERTIES(lemon PROPERTIES OUTPUT_NAME emon)
 		ENDIF()
 		INSTALL(
@@ -21,3 +53,4 @@
 		  ARCHIVE DESTINATION lib
-		  COMPONENT library)
 		  COMPONENT library
+		)
@@ -27,3 +60,4 @@
 		  COMPONENT headers
-		  FILES_MATCHING PATTERN "*.h")
 		  FILES_MATCHING PATTERN "*.h"
+		)
@@ -32,2 +66,3 @@
 		  DESTINATION include/lemon
-		  COMPONENT headers)
 		  COMPONENT headers
+		)

lemon/Makefile.am

Show inline comments

@@ -2,3 +2,4 @@
 			lemon/lemon.pc.in \
 			lemon/CMakeLists.txt
+			lemon/CMakeLists.txt \
 			lemon/config.h.cmake
@@ -9,28 +10,87 @@
 		lemon_libemon_la_SOURCES = \
 		        lemon/arg_parser.cc \
 		        lemon/base.cc \
 		        lemon/color.cc \
 		        lemon/random.cc \
 			lemon/arg_parser.cc \
 			lemon/base.cc \
 			lemon/color.cc \
 			lemon/lp_base.cc \
 			lemon/lp_skeleton.cc \
 			lemon/random.cc \
 			lemon/bits/windows.cc
 		#lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
 		#lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
 		nodist_lemon_HEADERS = lemon/config.h
-		nodist_lemon_HEADERS = lemon/config.h
+		lemon_libemon_la_CXXFLAGS = \
 			$(AM_CXXFLAGS) \
 			$(GLPK_CFLAGS) \
 			$(CPLEX_CFLAGS) \
 			$(SOPLEX_CXXFLAGS) \
 			$(CLP_CXXFLAGS) \
 			$(CBC_CXXFLAGS)
 		lemon_libemon_la_LDFLAGS = \
 			$(GLPK_LIBS) \
 			$(CPLEX_LIBS) \
 			$(SOPLEX_LIBS) \
 			$(CLP_LIBS) \
 			$(CBC_LIBS)
 		if HAVE_GLPK
 		lemon_libemon_la_SOURCES += lemon/glpk.cc
 		endif
 		if HAVE_CPLEX
 		lemon_libemon_la_SOURCES += lemon/cplex.cc
 		endif
 		if HAVE_SOPLEX
 		lemon_libemon_la_SOURCES += lemon/soplex.cc
 		endif
 		if HAVE_CLP
 		lemon_libemon_la_SOURCES += lemon/clp.cc
 		endif
 		if HAVE_CBC
 		lemon_libemon_la_SOURCES += lemon/cbc.cc
 		endif
 		lemon_HEADERS += \
-		        lemon/arg_parser.h \
+			lemon/adaptors.h \
 			lemon/arg_parser.h \
 			lemon/assert.h \
 		        lemon/bfs.h \
 		        lemon/bin_heap.h \
-		        lemon/color.h \
+			lemon/bellman_ford.h \
 			lemon/bfs.h \
 			lemon/bin_heap.h \
 			lemon/binom_heap.h \
 			lemon/bucket_heap.h \
 			lemon/cbc.h \
 			lemon/circulation.h \
 			lemon/clp.h \
 			lemon/color.h \
 			lemon/concept_check.h \
-		        lemon/counter.h \
+			lemon/connectivity.h \
 			lemon/counter.h \
 			lemon/core.h \
 		        lemon/dfs.h \
 		        lemon/dijkstra.h \
-		        lemon/dim2.h \
+			lemon/cplex.h \
 			lemon/dfs.h \
 			lemon/dijkstra.h \
 			lemon/dim2.h \
 			lemon/dimacs.h \
 			lemon/edge_set.h \
 			lemon/elevator.h \
 			lemon/error.h \
-		        lemon/graph_to_eps.h \
+			lemon/euler.h \
 			lemon/fib_heap.h \
 			lemon/fourary_heap.h \
 			lemon/full_graph.h \
 			lemon/glpk.h \
 			lemon/gomory_hu.h \
 			lemon/graph_to_eps.h \
 			lemon/grid_graph.h \
 			lemon/hartmann_orlin.h \
 			lemon/howard.h \
 			lemon/hypercube_graph.h \
 			lemon/karp.h \
 			lemon/kary_heap.h \
 			lemon/kruskal.h \
 			lemon/hao_orlin.h \
 			lemon/lgf_reader.h \
@@ -38,9 +98,23 @@
 			lemon/list_graph.h \
 			lemon/lp.h \
 			lemon/lp_base.h \
 			lemon/lp_skeleton.h \
 			lemon/maps.h \
 			lemon/matching.h \
 			lemon/math.h \
 			lemon/min_cost_arborescence.h \
 			lemon/nauty_reader.h \
 			lemon/network_simplex.h \
 			lemon/pairing_heap.h \
 			lemon/path.h \
-		        lemon/random.h \
+			lemon/preflow.h \
 			lemon/radix_heap.h \
 			lemon/radix_sort.h \
 			lemon/random.h \
 			lemon/smart_graph.h \
 		        lemon/time_measure.h \
 		        lemon/tolerance.h \
 			lemon/soplex.h \
 			lemon/static_graph.h \
 			lemon/suurballe.h \
 			lemon/time_measure.h \
 			lemon/tolerance.h \
 			lemon/unionfind.h \
@@ -51,6 +125,7 @@
 			lemon/bits/array_map.h \
 			lemon/bits/base_extender.h \
 		        lemon/bits/bezier.h \
 			lemon/bits/bezier.h \
 			lemon/bits/default_map.h \
-		        lemon/bits/enable_if.h \
+			lemon/bits/edge_set_extender.h \
 			lemon/bits/enable_if.h \
 			lemon/bits/graph_adaptor_extender.h \
 			lemon/bits/graph_extender.h \
@@ -58,3 +133,5 @@
 			lemon/bits/path_dump.h \
 			lemon/bits/solver_bits.h \
 			lemon/bits/traits.h \
 			lemon/bits/variant.h \
 			lemon/bits/vector_map.h

Changeset was too big and was cut off... Show full diff

0 comments (0 inline)

RhodeCode

Login to your account

Changeset was too big and was cut off... Show full diff

Changeset was too big and was cut off... Show full diff