Index: .hgignore
===================================================================
--- .hgignore (revision 517)
+++ .hgignore (revision 563)
@@ -23,5 +23,5 @@
lemon/stamp-h2
doc/Doxyfile
-cmake/cmake.version
+cmake/version.cmake
.dirstamp
.libs/*
Index: CMakeLists.txt
===================================================================
--- CMakeLists.txt (revision 527)
+++ CMakeLists.txt (revision 552)
@@ -10,5 +10,5 @@
PROJECT(${PROJECT_NAME})
-SET(CMAKE_MODULE_PATH ${CMAKE_SOURCE_DIR}/cmake)
+SET(CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR}/cmake)
INCLUDE(FindDoxygen)
@@ -39,73 +39,77 @@
ADD_SUBDIRECTORY(lemon)
-ADD_SUBDIRECTORY(demo)
-ADD_SUBDIRECTORY(tools)
-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(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
-IF(WIN32)
- SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
- SET(CPACK_PACKAGE_VENDOR "EGRES")
- SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
- "LEMON - Library of Efficient Models and Optimization in Networks")
- SET(CPACK_RESOURCE_FILE_LICENSE "${CMAKE_SOURCE_DIR}/LICENSE")
+IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
+ IF(WIN32)
+ SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
+ SET(CPACK_PACKAGE_VENDOR "EGRES")
+ SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
+ "LEMON - Library of Efficient Models and Optimization in Networks")
+ SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")
- SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
+ SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
- SET(CPACK_PACKAGE_INSTALL_DIRECTORY
- "${PROJECT_NAME} ${PROJECT_VERSION}")
- SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY
- "${PROJECT_NAME} ${PROJECT_VERSION}")
+ SET(CPACK_PACKAGE_INSTALL_DIRECTORY
+ "${PROJECT_NAME} ${PROJECT_VERSION}")
+ SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY
+ "${PROJECT_NAME} ${PROJECT_VERSION}")
- SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
+ SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
- SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
- 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")
+ SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
+ 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")
- SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
- "C++ header files")
- SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
- "DLL and import library")
- SET(CPACK_COMPONENT_BIN_DESCRIPTION
- "Command line utilities")
- SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
- "Doxygen generated documentation")
+ SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
+ "C++ header files")
+ SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
+ "DLL and import library")
+ SET(CPACK_COMPONENT_BIN_DESCRIPTION
+ "Command line utilities")
+ SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
+ "Doxygen generated documentation")
- SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
+ SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
- SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
- SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
- SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
+ SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
+ SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
+ SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
- SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
- "Components needed to develop software using LEMON")
- SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
- "Documentation of LEMON")
+ SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
+ "Components needed to develop software using LEMON")
+ SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
+ "Documentation of LEMON")
- SET(CPACK_ALL_INSTALL_TYPES Full Developer)
+ SET(CPACK_ALL_INSTALL_TYPES Full Developer)
- SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
- SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
- SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
+ SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
+ SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
+ SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
- 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_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
- SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
- SET(CPACK_NSIS_HELP_LINK "http:\\\\\\\\lemon.cs.elte.hu")
- SET(CPACK_NSIS_URL_INFO_ABOUT "http:\\\\\\\\lemon.cs.elte.hu")
- SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")
- SET(CPACK_NSIS_CREATE_ICONS_EXTRA "
- CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\share\\\\doc\\\\index.html\\\"
- ")
- SET(CPACK_NSIS_DELETE_ICONS_EXTRA "
- !insertmacro MUI_STARTMENU_GETFOLDER Application $MUI_TEMP
- Delete \\\"$SMPROGRAMS\\\\$MUI_TEMP\\\\Documentation.lnk\\\"
- ")
+ SET(CPACK_GENERATOR "NSIS")
+ 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")
+ SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
+ SET(CPACK_NSIS_HELP_LINK "http:\\\\\\\\lemon.cs.elte.hu")
+ SET(CPACK_NSIS_URL_INFO_ABOUT "http:\\\\\\\\lemon.cs.elte.hu")
+ SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")
+ SET(CPACK_NSIS_CREATE_ICONS_EXTRA "
+ CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\share\\\\doc\\\\index.html\\\"
+ ")
+ SET(CPACK_NSIS_DELETE_ICONS_EXTRA "
+ !insertmacro MUI_STARTMENU_GETFOLDER Application $MUI_TEMP
+ Delete \\\"$SMPROGRAMS\\\\$MUI_TEMP\\\\Documentation.lnk\\\"
+ ")
- INCLUDE(CPack)
-ENDIF(WIN32)
+ INCLUDE(CPack)
+ ENDIF(WIN32)
+ENDIF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
Index: INSTALL
===================================================================
--- INSTALL (revision 318)
+++ INSTALL (revision 568)
@@ -5,4 +5,10 @@
tarballs and successfully extracted it. The latest version of LEMON is
available at our web page (http://lemon.cs.elte.hu/).
+
+LEMON provides two different build environments, one is based on "autotool",
+while the other is based on "cmake". This file contains instructions only for
+the former one, which is the recommended build environment on Linux, Mac OSX
+and other unices or if you use Cygwin on Windows. For cmake installation
+instructions visit http://lemon.cs.elte.hu.
In order to install LEMON from the extracted source tarball you have to
@@ -22,6 +28,6 @@
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.
4. `make check'
@@ -69,12 +75,4 @@
Set the installation prefix to PREFIX. By default it is /usr/local.
-
---enable-demo
-
- Build the examples in the demo subdirectory.
-
---disable-demo
-
- Do not build the examples in the demo subdirectory (default).
--enable-tools
@@ -153,2 +151,25 @@
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.
Index: LICENSE
===================================================================
--- LICENSE (revision 440)
+++ LICENSE (revision 553)
@@ -1,3 +1,3 @@
-LEMON code without an explicit copyright is covered by the following
+LEMON code without an explicit copyright notice is covered by the following
copyright/license.
@@ -5,4 +5,8 @@
Kutatocsoport (Egervary Combinatorial Optimization Research Group,
EGRES).
+
+===========================================================================
+Boost Software License, Version 1.0
+===========================================================================
Permission is hereby granted, free of charge, to any person or organization
@@ -27,7 +31,2 @@
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.
-
-===========================================================================
-This license is a verbatim copy of the Boost Software License, Version 1.0.
-
-
Index: Makefile.am
===================================================================
--- Makefile.am (revision 508)
+++ Makefile.am (revision 567)
@@ -12,4 +12,6 @@
m4/lx_check_glpk.m4 \
m4/lx_check_soplex.m4 \
+ m4/lx_check_clp.m4 \
+ m4/lx_check_cbc.m4 \
CMakeLists.txt \
cmake/FindGhostscript.cmake \
@@ -40,6 +42,10 @@
include test/Makefile.am
include doc/Makefile.am
-include demo/Makefile.am
include tools/Makefile.am
+
+DIST_SUBDIRS = demo
+
+demo:
+ $(MAKE) $(AM_MAKEFLAGS) -C demo
MRPROPERFILES = \
@@ -69,3 +75,3 @@
bzip2 --best -c > $(PACKAGE)-$(VERSION).tar.bz2
-.PHONY: mrproper dist-bz2 distcheck-bz2
+.PHONY: demo mrproper dist-bz2 distcheck-bz2
Index: NEWS
===================================================================
--- NEWS (revision 322)
+++ NEWS (revision 496)
@@ -1,2 +1,9 @@
+2009-03-27 LEMON joins to the COIN-OR initiative
+
+ COIN-OR (Computational Infrastructure for Operations Research,
+ http://www.coin-or.org) project is an initiative to spur the
+ development of open-source software for the operations research
+ community.
+
2008-10-13 Version 1.0 released
Index: configure.ac
===================================================================
--- configure.ac (revision 517)
+++ configure.ac (revision 568)
@@ -60,21 +60,8 @@
LX_CHECK_CPLEX
LX_CHECK_SOPLEX
-LX_CHECK_CLP
+LX_CHECK_COIN
AM_CONDITIONAL([HAVE_LP], [test x"$lx_lp_found" = x"yes"])
AM_CONDITIONAL([HAVE_MIP], [test x"$lx_mip_found" = x"yes"])
-
-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"])
dnl Disable/enable building the binary tools.
@@ -111,4 +98,5 @@
AC_CONFIG_FILES([
Makefile
+demo/Makefile
cmake/version.cmake
doc/Doxyfile
@@ -132,6 +120,6 @@
echo SOPLEX support................ : $lx_soplex_found
echo CLP support................... : $lx_clp_found
+echo CBC support................... : $lx_cbc_found
echo
-echo Build demo programs........... : $enable_demo
echo Build additional tools........ : $enable_tools
echo
Index: demo/CMakeLists.txt
===================================================================
--- demo/CMakeLists.txt (revision 475)
+++ demo/CMakeLists.txt (revision 549)
@@ -1,8 +1,8 @@
INCLUDE_DIRECTORIES(
- ${CMAKE_SOURCE_DIR}
- ${CMAKE_BINARY_DIR}
+ ${PROJECT_SOURCE_DIR}
+ ${PROJECT_BINARY_DIR}
)
-LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
+LINK_DIRECTORIES(${PROJECT_BINARY_DIR}/lemon)
SET(DEMOS
Index: demo/Makefile.am
===================================================================
--- demo/Makefile.am (revision 400)
+++ demo/Makefile.am (revision 564)
@@ -1,16 +1,17 @@
-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
Index: doc/CMakeLists.txt
===================================================================
--- doc/CMakeLists.txt (revision 518)
+++ doc/CMakeLists.txt (revision 586)
@@ -1,10 +1,10 @@
SET(PACKAGE_NAME ${PROJECT_NAME})
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
+ ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in
+ ${PROJECT_BINARY_DIR}/doc/Doxyfile
@ONLY)
@@ -15,5 +15,10 @@
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/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
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
@@ -21,4 +26,5 @@
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 ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
COMMAND rm -rf html
COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
@@ -28,4 +34,10 @@
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/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
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
@@ -33,4 +45,5 @@
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 ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
COMMAND if exist html rmdir /s /q html
COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
Index: doc/Makefile.am
===================================================================
--- doc/Makefile.am (revision 337)
+++ doc/Makefile.am (revision 587)
@@ -22,6 +22,15 @@
nodeshape_4.eps
+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)
DOC_PNG_IMAGES = \
@@ -39,4 +48,15 @@
if test ${gs_found} = yes; then \
$(GS_COMMAND) -sDEVICE=pngalpha -r18 -sOutputFile=$@ $<; \
+ else \
+ echo; \
+ echo "Ghostscript not found."; \
+ echo; \
+ exit 1; \
+ fi
+
+$(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; \
Index: doc/groups.dox
===================================================================
--- doc/groups.dox (revision 609)
+++ doc/groups.dox (revision 611)
@@ -21,5 +21,5 @@
/**
@defgroup datas Data Structures
-This group describes the several data structures implemented in LEMON.
+This group contains the several data structures implemented in LEMON.
*/
@@ -143,5 +143,5 @@
\brief Graph types between real graphs and graph adaptors.
-This group describes some graph types between real graphs and graph adaptors.
+This group contains some graph types between real graphs and graph adaptors.
These classes wrap graphs to give new functionality as the adaptors do it.
On the other hand they are not light-weight structures as the adaptors.
@@ -153,5 +153,5 @@
\brief Map structures implemented in LEMON.
-This group describes the map structures implemented in LEMON.
+This group contains the map structures implemented in LEMON.
LEMON provides several special purpose maps and map adaptors that e.g. combine
@@ -166,5 +166,5 @@
\brief Special graph-related maps.
-This group describes maps that are specifically designed to assign
+This group contains maps that are specifically designed to assign
values to the nodes and arcs/edges of graphs.
@@ -178,5 +178,5 @@
\brief Tools to create new maps from existing ones
-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.
@@ -241,5 +241,5 @@
\brief Two dimensional data storages implemented in LEMON.
-This group describes two dimensional data storages implemented in LEMON.
+This group contains two dimensional data storages implemented in LEMON.
*/
@@ -249,5 +249,5 @@
\brief %Path structures implemented in LEMON.
-This group describes the path structures implemented in LEMON.
+This group contains the path structures implemented in LEMON.
LEMON provides flexible data structures to work with paths.
@@ -265,5 +265,5 @@
\brief Auxiliary data structures implemented in LEMON.
-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.
*/
@@ -271,8 +271,8 @@
/**
@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.
*/
@@ -283,5 +283,5 @@
\brief Common graph search algorithms.
-This group describes the common graph search algorithms, namely
+This group contains the common graph search algorithms, namely
\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
*/
@@ -292,5 +292,5 @@
\brief Algorithms for finding shortest paths.
-This group describes the algorithms for finding shortest paths in digraphs.
+This group contains the algorithms for finding shortest paths in digraphs.
- \ref Dijkstra algorithm for finding shortest paths from a source node
@@ -313,5 +313,5 @@
\brief Algorithms for finding maximum flows.
-This group describes the algorithms for finding maximum flows and
+This group contains the algorithms for finding maximum flows and
feasible circulations.
@@ -451,5 +451,5 @@
\brief Algorithms for finding minimum cut in graphs.
-This group describes the algorithms for finding minimum cut in graphs.
+This group contains the algorithms for finding minimum cut in graphs.
The \e minimum \e cut \e problem is to find a non-empty and non-complete
@@ -468,5 +468,5 @@
- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
calculating minimum cut in undirected graphs.
-- \ref GomoryHuTree "Gomory-Hu tree computation" for calculating
+- \ref GomoryHu "Gomory-Hu tree computation" for calculating
all-pairs minimum cut in undirected graphs.
@@ -476,9 +476,9 @@
/**
-@defgroup graph_prop Connectivity and Other Graph Properties
+@defgroup graph_properties Connectivity and Other Graph Properties
@ingroup algs
\brief Algorithms for discovering the graph properties
-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.
@@ -492,5 +492,5 @@
\brief Algorithms for planarity checking, embedding and drawing
-This group describes the algorithms for planarity checking,
+This group contains the algorithms for planarity checking,
embedding and drawing.
@@ -504,7 +504,8 @@
\brief Algorithms for finding matchings in graphs and bipartite graphs.
-This group contains algorithm objects and functions to calculate
+This group contains the algorithms for calculating
matchings in graphs and bipartite graphs. The general matching problem is
-finding a subset of the arcs which does not shares common endpoints.
+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
@@ -543,5 +544,5 @@
\brief Algorithms for finding a minimum cost spanning tree in a graph.
-This group describes the algorithms for finding a minimum cost spanning
+This group contains the algorithms for finding a minimum cost spanning
tree in a graph.
*/
@@ -552,5 +553,5 @@
\brief Auxiliary algorithms implemented in LEMON.
-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.
*/
@@ -561,5 +562,5 @@
\brief Approximation algorithms.
-This group describes the approximation and heuristic algorithms
+This group contains the approximation and heuristic algorithms
implemented in LEMON.
*/
@@ -567,8 +568,8 @@
/**
@defgroup gen_opt_group General Optimization Tools
-\brief This group describes some general optimization frameworks
+\brief This group contains some general optimization frameworks
implemented in LEMON.
-This group describes some general optimization frameworks
+This group contains some general optimization frameworks
implemented in LEMON.
*/
@@ -579,5 +580,5 @@
\brief Lp and Mip solver interfaces for LEMON.
-This group describes Lp and Mip solver interfaces for LEMON. The
+This group contains Lp and Mip solver interfaces for LEMON. The
various LP solvers could be used in the same manner with this
interface.
@@ -598,5 +599,5 @@
\brief Metaheuristics for LEMON library.
-This group describes some metaheuristic optimization tools.
+This group contains some metaheuristic optimization tools.
*/
@@ -613,5 +614,5 @@
\brief Simple basic graph utilities.
-This group describes some simple basic graph utilities.
+This group contains some simple basic graph utilities.
*/
@@ -621,5 +622,5 @@
\brief Tools for development, debugging and testing.
-This group describes several useful tools for development,
+This group contains several useful tools for development,
debugging and testing.
*/
@@ -630,5 +631,5 @@
\brief Simple tools for measuring the performance of algorithms.
-This group describes simple tools for measuring the performance
+This group contains simple tools for measuring the performance
of algorithms.
*/
@@ -639,5 +640,5 @@
\brief Exceptions defined in LEMON.
-This group describes the exceptions defined in LEMON.
+This group contains the exceptions defined in LEMON.
*/
@@ -646,5 +647,5 @@
\brief Graph Input-Output methods
-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
"LEMON Graph Format", the \c DIMACS format and the encapsulated
@@ -657,5 +658,5 @@
\brief Reading and writing LEMON Graph Format.
-This group describes methods for reading and writing
+This group contains methods for reading and writing
\ref lgf-format "LEMON Graph Format".
*/
@@ -666,5 +667,5 @@
\brief General \c EPS drawer and graph exporter
-This group describes general \c EPS drawing methods and special
+This group contains general \c EPS drawing methods and special
graph exporting tools.
*/
@@ -690,5 +691,5 @@
\brief Skeleton classes and concept checking classes
-This group describes the data/algorithm skeletons and concept checking
+This group contains the data/algorithm skeletons and concept checking
classes implemented in LEMON.
@@ -720,5 +721,5 @@
\brief Skeleton and concept checking classes for graph structures
-This group describes the skeletons and concept checking classes of LEMON's
+This group contains the skeletons and concept checking classes of LEMON's
graph structures and helper classes used to implement these.
*/
@@ -729,5 +730,5 @@
\brief Skeleton and concept checking classes for maps
-This group describes the skeletons and concept checking classes of maps.
+This group contains the skeletons and concept checking classes of maps.
*/
@@ -740,6 +741,6 @@
the \c demo subdirectory of the source tree.
-It order to compile them, use --enable-demo configure option when
-build the library.
+In order to compile them, use the make demo or the
+make check commands.
*/
Index: doc/images/bipartite_matching.eps
===================================================================
--- doc/images/bipartite_matching.eps (revision 586)
+++ doc/images/bipartite_matching.eps (revision 586)
@@ -0,0 +1,586 @@
+%!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
+251.402 32.047 m
+532.945 293.946 814.484 555.844 814.484 555.844 c
+[] 0 d 1 0 0 r 3.92814 w s
+
+N
+749.012 32.047 m
+742.465 293.946 735.918 555.844 735.918 555.844 c
+[] 0 d 0 0 0 r 1.96407 w s
+
+N
+539.492 32.047 m
+637.703 293.946 735.918 555.844 735.918 555.844 c
+[] 0 d 0 0 0 r 1.96407 w s
+
+N
+172.832 32.047 m
+454.375 293.946 735.918 555.844 735.918 555.844 c
+[] 0 d 0 0 0 r 1.96407 w s
+
+N
+107.355 32.047 m
+421.637 293.946 735.918 555.844 735.918 555.844 c
+[] 0 d 1 0 0 r 3.92814 w s
+
+N
+644.25 555.844 m
+696.633 293.946 749.012 32.047 749.012 32.047 c
+[] 0 d 0 0 0 r 1.96407 w s
+
+N
+474.016 555.844 m
+611.516 293.946 749.012 32.047 749.012 32.047 c
+[] 0 d 1 0 0 r 3.92814 w s
+
+N
+683.535 32.047 m
+663.894 293.946 644.25 555.844 644.25 555.844 c
+[] 0 d 0 0 0 r 1.96407 w s
+
+N
+120.453 555.844 m
+401.992 293.946 683.535 32.047 683.535 32.047 c
+[] 0 d 0 0 0 r 1.96407 w s
+
+N
+28.7853 555.844 m
+356.16 293.946 683.535 32.047 683.535 32.047 c
+[] 0 d 1 0 0 r 3.92814 w s
+
+N
+539.492 32.047 m
+546.039 293.946 552.586 555.844 552.586 555.844 c
+[] 0 d 1 0 0 r 3.92814 w s
+
+N
+316.875 32.047 m
+349.613 293.946 382.351 555.844 382.351 555.844 c
+[] 0 d 1 0 0 r 3.92814 w s
+
+N
+107.355 32.047 m
+244.855 293.946 382.351 555.844 382.351 555.844 c
+[] 0 d 0 0 0 r 1.96407 w s
+
+N
+290.687 555.844 m
+375.805 293.946 460.922 32.047 460.922 32.047 c
+[] 0 d 1 0 0 r 3.92814 w s
+
+N
+120.453 555.844 m
+290.687 293.946 460.922 32.047 460.922 32.047 c
+[] 0 d 0 0 0 r 1.96407 w s
+
+N
+172.832 32.047 m
+146.64 293.946 120.453 555.844 120.453 555.844 c
+[] 0 d 1 0 0 r 3.92814 w s
+
+N
+15.6913 555.844 m
+15.6913 555.844 l
+15.6913 548.614 21.5553 542.75 28.7853 542.75 c
+36.0163 542.75 41.8833 548.614 41.8833 555.844 c
+41.8833 563.075 36.0163 568.938 28.7853 568.938 c
+21.5553 568.938 15.6913 563.075 15.6913 555.844 c
+15.6913 555.844 l
+C
+S 0 0 0 r f R
+
+N
+16.8833 555.844 m
+16.8833 555.844 l
+16.8833 549.27 22.2113 543.942 28.7853 543.942 c
+35.3593 543.942 40.6913 549.27 40.6913 555.844 c
+40.6913 562.418 35.3593 567.747 28.7853 567.747 c
+22.2113 567.747 16.8833 562.418 16.8833 555.844 c
+16.8833 555.844 l
+C
+S 1 0.5 1 r f R
+
+N
+107.355 555.844 m
+107.355 555.844 l
+107.355 548.614 113.223 542.75 120.453 542.75 c
+127.683 542.75 133.547 548.614 133.547 555.844 c
+133.547 563.075 127.683 568.938 120.453 568.938 c
+113.223 568.938 107.355 563.075 107.355 555.844 c
+107.355 555.844 l
+C
+S 0 0 0 r f R
+
+N
+108.547 555.844 m
+108.547 555.844 l
+108.547 549.27 113.879 543.942 120.453 543.942 c
+127.027 543.942 132.355 549.27 132.355 555.844 c
+132.355 562.418 127.027 567.747 120.453 567.747 c
+113.879 567.747 108.547 562.418 108.547 555.844 c
+108.547 555.844 l
+C
+S 1 0 1 r f R
+
+N
+199.019 555.844 m
+199.019 555.844 l
+199.019 548.614 204.887 542.75 212.117 542.75 c
+219.348 542.75 225.211 548.614 225.211 555.844 c
+225.211 563.075 219.348 568.938 212.117 568.938 c
+204.887 568.938 199.019 563.075 199.019 555.844 c
+199.019 555.844 l
+C
+S 0 0 0 r f R
+
+N
+200.211 555.844 m
+200.211 555.844 l
+200.211 549.27 205.543 543.942 212.117 543.942 c
+218.691 543.942 224.019 549.27 224.019 555.844 c
+224.019 562.418 218.691 567.747 212.117 567.747 c
+205.543 567.747 200.211 562.418 200.211 555.844 c
+200.211 555.844 l
+C
+S 1 0.5 1 r f R
+
+N
+277.59 555.844 m
+277.59 555.844 l
+277.59 548.614 283.457 542.75 290.687 542.75 c
+297.918 542.75 303.781 548.614 303.781 555.844 c
+303.781 563.075 297.918 568.938 290.687 568.938 c
+283.457 568.938 277.59 563.075 277.59 555.844 c
+277.59 555.844 l
+C
+S 0 0 0 r f R
+
+N
+278.781 555.844 m
+278.781 555.844 l
+278.781 549.27 284.113 543.942 290.687 543.942 c
+297.262 543.942 302.59 549.27 302.59 555.844 c
+302.59 562.418 297.262 567.747 290.687 567.747 c
+284.113 567.747 278.781 562.418 278.781 555.844 c
+278.781 555.844 l
+C
+S 1 0 1 r f R
+
+N
+369.258 555.844 m
+369.258 555.844 l
+369.258 548.614 375.121 542.75 382.351 542.75 c
+389.582 542.75 395.445 548.614 395.445 555.844 c
+395.445 563.075 389.582 568.938 382.351 568.938 c
+375.121 568.938 369.258 563.075 369.258 555.844 c
+369.258 555.844 l
+C
+S 0 0 0 r f R
+
+N
+370.445 555.844 m
+370.445 555.844 l
+370.445 549.27 375.777 543.942 382.351 543.942 c
+388.926 543.942 394.258 549.27 394.258 555.844 c
+394.258 562.418 388.926 567.747 382.351 567.747 c
+375.777 567.747 370.445 562.418 370.445 555.844 c
+370.445 555.844 l
+C
+S 1 0 1 r f R
+
+N
+460.922 555.844 m
+460.922 555.844 l
+460.922 548.614 466.785 542.75 474.016 542.75 c
+481.246 542.75 487.109 548.614 487.109 555.844 c
+487.109 563.075 481.246 568.938 474.016 568.938 c
+466.785 568.938 460.922 563.075 460.922 555.844 c
+460.922 555.844 l
+C
+S 0 0 0 r f R
+
+N
+462.113 555.844 m
+462.113 555.844 l
+462.113 549.27 467.441 543.942 474.016 543.942 c
+480.59 543.942 485.922 549.27 485.922 555.844 c
+485.922 562.418 480.59 567.747 474.016 567.747 c
+467.441 567.747 462.113 562.418 462.113 555.844 c
+462.113 555.844 l
+C
+S 1 0.5 1 r f R
+
+N
+539.492 555.844 m
+539.492 555.844 l
+539.492 548.614 545.355 542.75 552.586 542.75 c
+559.816 542.75 565.68 548.614 565.68 555.844 c
+565.68 563.075 559.816 568.938 552.586 568.938 c
+545.355 568.938 539.492 563.075 539.492 555.844 c
+539.492 555.844 l
+C
+S 0 0 0 r f R
+
+N
+540.683 555.844 m
+540.683 555.844 l
+540.683 549.27 546.012 543.942 552.586 543.942 c
+559.16 543.942 564.492 549.27 564.492 555.844 c
+564.492 562.418 559.16 567.747 552.586 567.747 c
+546.012 567.747 540.683 562.418 540.683 555.844 c
+540.683 555.844 l
+C
+S 1 0 1 r f R
+
+N
+631.156 555.844 m
+631.156 555.844 l
+631.156 548.614 637.019 542.75 644.25 542.75 c
+651.48 542.75 657.348 548.614 657.348 555.844 c
+657.348 563.075 651.48 568.938 644.25 568.938 c
+637.019 568.938 631.156 563.075 631.156 555.844 c
+631.156 555.844 l
+C
+S 0 0 0 r f R
+
+N
+632.348 555.844 m
+632.348 555.844 l
+632.348 549.27 637.676 543.942 644.25 543.942 c
+650.824 543.942 656.156 549.27 656.156 555.844 c
+656.156 562.418 650.824 567.747 644.25 567.747 c
+637.676 567.747 632.348 562.418 632.348 555.844 c
+632.348 555.844 l
+C
+S 1 0.5 1 r f R
+
+N
+722.82 555.844 m
+722.82 555.844 l
+722.82 548.614 728.687 542.75 735.918 542.75 c
+743.149 542.75 749.012 548.614 749.012 555.844 c
+749.012 563.075 743.149 568.938 735.918 568.938 c
+728.687 568.938 722.82 563.075 722.82 555.844 c
+722.82 555.844 l
+C
+S 0 0 0 r f R
+
+N
+724.012 555.844 m
+724.012 555.844 l
+724.012 549.27 729.344 543.942 735.918 543.942 c
+742.492 543.942 747.82 549.27 747.82 555.844 c
+747.82 562.418 742.492 567.747 735.918 567.747 c
+729.344 567.747 724.012 562.418 724.012 555.844 c
+724.012 555.844 l
+C
+S 1 0 1 r f R
+
+N
+801.391 555.844 m
+801.391 555.844 l
+801.391 548.614 807.254 542.75 814.484 542.75 c
+821.715 542.75 827.578 548.614 827.578 555.844 c
+827.578 563.075 821.715 568.938 814.484 568.938 c
+807.254 568.938 801.391 563.075 801.391 555.844 c
+801.391 555.844 l
+C
+S 0 0 0 r f R
+
+N
+802.582 555.844 m
+802.582 555.844 l
+802.582 549.27 807.91 543.942 814.484 543.942 c
+821.059 543.942 826.387 549.27 826.387 555.844 c
+826.387 562.418 821.059 567.747 814.484 567.747 c
+807.91 567.747 802.582 562.418 802.582 555.844 c
+802.582 555.844 l
+C
+S 1 0 1 r f R
+
+N
+15.6913 32.047 m
+15.6913 32.047 l
+15.6913 24.8165 21.5553 18.9493 28.7853 18.9493 c
+36.0163 18.9493 41.8833 24.8165 41.8833 32.047 c
+41.8833 39.2775 36.0163 45.1407 28.7853 45.1407 c
+21.5553 45.1407 15.6913 39.2775 15.6913 32.047 c
+15.6913 32.047 l
+C
+S 0 0 0 r f R
+
+N
+16.8833 32.047 m
+16.8833 32.047 l
+16.8833 25.4728 22.2113 20.1407 28.7853 20.1407 c
+35.3593 20.1407 40.6913 25.4728 40.6913 32.047 c
+40.6913 38.6212 35.3593 43.9493 28.7853 43.9493 c
+22.2113 43.9493 16.8833 38.6212 16.8833 32.047 c
+16.8833 32.047 l
+C
+S 0.5 0.5 1 r f R
+
+N
+94.2623 32.047 m
+94.2623 32.047 l
+94.2623 24.8165 100.125 18.9493 107.355 18.9493 c
+114.586 18.9493 120.453 24.8165 120.453 32.047 c
+120.453 39.2775 114.586 45.1407 107.355 45.1407 c
+100.125 45.1407 94.2623 39.2775 94.2623 32.047 c
+94.2623 32.047 l
+C
+S 0 0 0 r f R
+
+N
+95.4533 32.047 m
+95.4533 32.047 l
+95.4533 25.4728 100.781 20.1407 107.355 20.1407 c
+113.93 20.1407 119.262 25.4728 119.262 32.047 c
+119.262 38.6212 113.93 43.9493 107.355 43.9493 c
+100.781 43.9493 95.4533 38.6212 95.4533 32.047 c
+95.4533 32.047 l
+C
+S 0.5 0.5 1 r f R
+
+N
+159.734 32.047 m
+159.734 32.047 l
+159.734 24.8165 165.601 18.9493 172.832 18.9493 c
+180.062 18.9493 185.926 24.8165 185.926 32.047 c
+185.926 39.2775 180.062 45.1407 172.832 45.1407 c
+165.601 45.1407 159.734 39.2775 159.734 32.047 c
+159.734 32.047 l
+C
+S 0 0 0 r f R
+
+N
+160.926 32.047 m
+160.926 32.047 l
+160.926 25.4728 166.258 20.1407 172.832 20.1407 c
+179.406 20.1407 184.734 25.4728 184.734 32.047 c
+184.734 38.6212 179.406 43.9493 172.832 43.9493 c
+166.258 43.9493 160.926 38.6212 160.926 32.047 c
+160.926 32.047 l
+C
+S 0.5 0.5 1 r f R
+
+N
+238.305 32.047 m
+238.305 32.047 l
+238.305 24.8165 244.172 18.9493 251.402 18.9493 c
+258.633 18.9493 264.496 24.8165 264.496 32.047 c
+264.496 39.2775 258.633 45.1407 251.402 45.1407 c
+244.172 45.1407 238.305 39.2775 238.305 32.047 c
+238.305 32.047 l
+C
+S 0 0 0 r f R
+
+N
+239.496 32.047 m
+239.496 32.047 l
+239.496 25.4728 244.828 20.1407 251.402 20.1407 c
+257.976 20.1407 263.305 25.4728 263.305 32.047 c
+263.305 38.6212 257.976 43.9493 251.402 43.9493 c
+244.828 43.9493 239.496 38.6212 239.496 32.047 c
+239.496 32.047 l
+C
+S 0.5 0.5 1 r f R
+
+N
+303.781 32.047 m
+303.781 32.047 l
+303.781 24.8165 309.644 18.9493 316.875 18.9493 c
+324.105 18.9493 329.973 24.8165 329.973 32.047 c
+329.973 39.2775 324.105 45.1407 316.875 45.1407 c
+309.644 45.1407 303.781 39.2775 303.781 32.047 c
+303.781 32.047 l
+C
+S 0 0 0 r f R
+
+N
+304.973 32.047 m
+304.973 32.047 l
+304.973 25.4728 310.301 20.1407 316.875 20.1407 c
+323.449 20.1407 328.781 25.4728 328.781 32.047 c
+328.781 38.6212 323.449 43.9493 316.875 43.9493 c
+310.301 43.9493 304.973 38.6212 304.973 32.047 c
+304.973 32.047 l
+C
+S 0.5 0.5 1 r f R
+
+N
+382.351 32.047 m
+382.351 32.047 l
+382.351 24.8165 388.215 18.9493 395.445 18.9493 c
+402.676 18.9493 408.543 24.8165 408.543 32.047 c
+408.543 39.2775 402.676 45.1407 395.445 45.1407 c
+388.215 45.1407 382.351 39.2775 382.351 32.047 c
+382.351 32.047 l
+C
+S 0 0 0 r f R
+
+N
+383.543 32.047 m
+383.543 32.047 l
+383.543 25.4728 388.871 20.1407 395.445 20.1407 c
+402.019 20.1407 407.351 25.4728 407.351 32.047 c
+407.351 38.6212 402.019 43.9493 395.445 43.9493 c
+388.871 43.9493 383.543 38.6212 383.543 32.047 c
+383.543 32.047 l
+C
+S 0.5 0.5 1 r f R
+
+N
+447.828 32.047 m
+447.828 32.047 l
+447.828 24.8165 453.691 18.9493 460.922 18.9493 c
+468.152 18.9493 474.016 24.8165 474.016 32.047 c
+474.016 39.2775 468.152 45.1407 460.922 45.1407 c
+453.691 45.1407 447.828 39.2775 447.828 32.047 c
+447.828 32.047 l
+C
+S 0 0 0 r f R
+
+N
+449.016 32.047 m
+449.016 32.047 l
+449.016 25.4728 454.348 20.1407 460.922 20.1407 c
+467.496 20.1407 472.824 25.4728 472.824 32.047 c
+472.824 38.6212 467.496 43.9493 460.922 43.9493 c
+454.348 43.9493 449.016 38.6212 449.016 32.047 c
+449.016 32.047 l
+C
+S 0.5 0.5 1 r f R
+
+N
+526.394 32.047 m
+526.394 32.047 l
+526.394 24.8165 532.262 18.9493 539.492 18.9493 c
+546.723 18.9493 552.586 24.8165 552.586 32.047 c
+552.586 39.2775 546.723 45.1407 539.492 45.1407 c
+532.262 45.1407 526.394 39.2775 526.394 32.047 c
+526.394 32.047 l
+C
+S 0 0 0 r f R
+
+N
+527.586 32.047 m
+527.586 32.047 l
+527.586 25.4728 532.918 20.1407 539.492 20.1407 c
+546.066 20.1407 551.394 25.4728 551.394 32.047 c
+551.394 38.6212 546.066 43.9493 539.492 43.9493 c
+532.918 43.9493 527.586 38.6212 527.586 32.047 c
+527.586 32.047 l
+C
+S 0.5 0.5 1 r f R
+
+N
+591.871 32.047 m
+591.871 32.047 l
+591.871 24.8165 597.734 18.9493 604.965 18.9493 c
+612.195 18.9493 618.062 24.8165 618.062 32.047 c
+618.062 39.2775 612.195 45.1407 604.965 45.1407 c
+597.734 45.1407 591.871 39.2775 591.871 32.047 c
+591.871 32.047 l
+C
+S 0 0 0 r f R
+
+N
+593.062 32.047 m
+593.062 32.047 l
+593.062 25.4728 598.39 20.1407 604.965 20.1407 c
+611.539 20.1407 616.871 25.4728 616.871 32.047 c
+616.871 38.6212 611.539 43.9493 604.965 43.9493 c
+598.39 43.9493 593.062 38.6212 593.062 32.047 c
+593.062 32.047 l
+C
+S 0.5 0.5 1 r f R
+
+N
+670.441 32.047 m
+670.441 32.047 l
+670.441 24.8165 676.305 18.9493 683.535 18.9493 c
+690.766 18.9493 696.633 24.8165 696.633 32.047 c
+696.633 39.2775 690.766 45.1407 683.535 45.1407 c
+676.305 45.1407 670.441 39.2775 670.441 32.047 c
+670.441 32.047 l
+C
+S 0 0 0 r f R
+
+N
+671.633 32.047 m
+671.633 32.047 l
+671.633 25.4728 676.961 20.1407 683.535 20.1407 c
+690.109 20.1407 695.441 25.4728 695.441 32.047 c
+695.441 38.6212 690.109 43.9493 683.535 43.9493 c
+676.961 43.9493 671.633 38.6212 671.633 32.047 c
+671.633 32.047 l
+C
+S 0 0 1 r f R
+
+N
+735.918 32.047 m
+735.918 32.047 l
+735.918 24.8165 741.781 18.9493 749.012 18.9493 c
+756.242 18.9493 762.106 24.8165 762.106 32.047 c
+762.106 39.2775 756.242 45.1407 749.012 45.1407 c
+741.781 45.1407 735.918 39.2775 735.918 32.047 c
+735.918 32.047 l
+C
+S 0 0 0 r f R
+
+N
+737.105 32.047 m
+737.105 32.047 l
+737.105 25.4728 742.437 20.1407 749.012 20.1407 c
+755.586 20.1407 760.914 25.4728 760.914 32.047 c
+760.914 38.6212 755.586 43.9493 749.012 43.9493 c
+742.437 43.9493 737.105 38.6212 737.105 32.047 c
+737.105 32.047 l
+C
+S 0 0 1 r f R
+
+N
+801.391 32.047 m
+801.391 32.047 l
+801.391 24.8165 807.254 18.9493 814.484 18.9493 c
+821.715 18.9493 827.578 24.8165 827.578 32.047 c
+827.578 39.2775 821.715 45.1407 814.484 45.1407 c
+807.254 45.1407 801.391 39.2775 801.391 32.047 c
+801.391 32.047 l
+C
+S 0 0 0 r f R
+
+N
+802.582 32.047 m
+802.582 32.047 l
+802.582 25.4728 807.91 20.1407 814.484 20.1407 c
+821.059 20.1407 826.387 25.4728 826.387 32.047 c
+826.387 38.6212 821.059 43.9493 814.484 43.9493 c
+807.91 43.9493 802.582 38.6212 802.582 32.047 c
+802.582 32.047 l
+C
+S 0.5 0.5 1 r f R
+
+%%EOF
Index: doc/images/bipartite_partitions.eps
===================================================================
--- doc/images/bipartite_partitions.eps (revision 587)
+++ doc/images/bipartite_partitions.eps (revision 587)
@@ -0,0 +1,114 @@
+%!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
+ 4 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
+ 2 index 1 index sub 2 index 2 index add lineto
+ 2 index 1 index sub 2 index 2 index sub lineto
+ 2 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
+ 2 index 2 index 2 index add lineto
+ 2 index 1 index sub 2 index lineto
+ 2 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
+90 rotate
+0 -842 translate
+71.6378 15 translate
+0.389093 dup scale
+90 rotate
+1197.47 -613.138 translate
+%Edges:
+gsave
+513.857 -446.322 296.569 -487.43 79.2808 -528.539 0 0 0 2 lb
+513.857 -446.322 575.52 -315.655 637.183 -184.989 0 0 0 2 lb
+393.468 566.711 494.771 434.577 596.074 302.442 0 0 0 2 lb
+393.468 566.711 155.625 579.925 -82.2171 593.138 0 0 0 2 lb
+393.468 566.711 251.056 450.726 108.644 334.741 0 0 0 2 lb
+869.153 52.8539 732.613 177.648 596.074 302.442 0 0 0 2 lb
+869.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
+79.2808 -528.539 -66.0671 -490.366 -211.415 -452.194 0 0 0 2 lb
+637.183 -184.989 421.363 -253.993 205.543 -322.996 0 0 0 2 lb
+205.543 -322.996 162.966 -226.097 120.389 -129.198 0 0 0 2 lb
+399.34 88.0898 259.865 -20.5541 120.389 -129.198 0 0 0 2 lb
+399.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
+120.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
+108.644 334.741 20 0 0 1 nc
+120.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
+399.34 88.0898 20 1 0 0 nc
+205.543 -322.996 20 1 0 0 nc
+637.183 -184.989 20 0 0 1 nc
+79.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
+596.074 302.442 20 0 0 1 nc
+869.153 52.8539 20 1 0 0 nc
+393.468 566.711 20 1 0 0 nc
+513.857 -446.322 20 1 0 0 nc
+grestore
+grestore
+showpage
Index: doc/images/connected_components.eps
===================================================================
--- doc/images/connected_components.eps (revision 587)
+++ doc/images/connected_components.eps (revision 587)
@@ -0,0 +1,159 @@
+%!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
+ 4 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
+ 2 index 1 index sub 2 index 2 index add lineto
+ 2 index 1 index sub 2 index 2 index sub lineto
+ 2 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
+ 2 index 2 index 2 index add lineto
+ 2 index 1 index sub 2 index lineto
+ 2 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
+90 rotate
+0 -842 translate
+71.0944 15 translate
+0.434694 dup scale
+90 rotate
+860.856 -588.349 translate
+%Edges:
+gsave
+574.035 177.301 622.149 225.748 670.264 274.195 0 0 0 2 lb
+694.579 115.483 682.421 194.839 670.264 274.195 0 0 0 2 lb
+280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 0 2 lb
+280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 0 2 lb
+212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 0 2 lb
+286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 0 2 lb
+286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 0 2 lb
+438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 0 2 lb
+438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 0 2 lb
+397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 0 2 lb
+366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 0 2 lb
+271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 0 2 lb
+271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 0 2 lb
+277.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
+906.312 201.403 946.592 42.798 986.873 -115.807 0 0 0 2 lb
+906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 0 2 lb
+986.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
+422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 0 2 lb
+422.945 521.129 376.371 417.911 329.797 314.692 0 0 0 2 lb
+422.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
+329.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
+762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 0 2 lb
+762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 0 2 lb
+526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 0 2 lb
+730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 0 2 lb
+415.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
+116.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
+670.264 274.195 629.188 409.347 588.113 544.499 0 0 0 2 lb
+670.264 274.195 797.466 341.771 924.667 409.347 0 0 0 2 lb
+588.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
+924.667 409.347 20 1 0 0 nc
+588.113 544.499 20 1 0 0 nc
+670.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
+201.208 38.3422 20 0 1 0 nc
+116.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
+415.393 -289.516 20 0 0 1 nc
+730.084 -307.139 20 0 0 1 nc
+526.164 32.7279 20 0 0 1 nc
+762.812 -17.6227 20 0 0 1 nc
+-67.9734 319.727 20 0 0 1 nc
+329.797 314.692 20 0 0 1 nc
+-5.03507 561.41 20 0 0 1 nc
+422.945 521.129 20 0 0 1 nc
+-470.779 158.605 20 0 0 1 nc
+986.873 -115.807 20 0 0 1 nc
+906.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
+206.221 -205.967 20 1 1 0 nc
+277.311 -252.33 20 1 1 0 nc
+271.13 -175.058 20 1 1 0 nc
+366.947 -110.15 20 1 1 0 nc
+397.855 -196.694 20 1 1 0 nc
+438.037 -88.514 20 1 1 0 nc
+286.584 -48.3327 20 1 1 0 nc
+212.403 -23.6057 20 1 1 0 nc
+280.402 10.3938 20 1 1 0 nc
+694.579 115.483 20 1 0 0 nc
+574.035 177.301 20 1 0 0 nc
+grestore
+grestore
+showpage
Index: doc/images/edge_biconnected_components.eps
===================================================================
--- doc/images/edge_biconnected_components.eps (revision 587)
+++ doc/images/edge_biconnected_components.eps (revision 587)
@@ -0,0 +1,159 @@
+%!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
+ 4 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
+ 2 index 1 index sub 2 index 2 index add lineto
+ 2 index 1 index sub 2 index 2 index sub lineto
+ 2 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
+ 2 index 2 index 2 index add lineto
+ 2 index 1 index sub 2 index lineto
+ 2 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
+90 rotate
+0 -842 translate
+71.0944 15 translate
+0.434694 dup scale
+90 rotate
+860.856 -588.349 translate
+%Edges:
+gsave
+574.035 177.301 622.149 225.748 670.264 274.195 1 0 0 2 lb
+694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 2 lb
+280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 1 2 lb
+280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 1 2 lb
+212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 1 2 lb
+286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 1 2 lb
+286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 1 2 lb
+438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 1 2 lb
+438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 1 2 lb
+397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 1 2 lb
+366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 1 2 lb
+271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 1 2 lb
+271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 1 2 lb
+277.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
+906.312 201.403 946.592 42.798 986.873 -115.807 0 0 1 2 lb
+906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 1 2 lb
+986.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
+422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 1 2 lb
+422.945 521.129 376.371 417.911 329.797 314.692 0 0 1 2 lb
+422.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
+329.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
+762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 1 2 lb
+762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 1 2 lb
+526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 1 2 lb
+730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 1 2 lb
+415.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
+116.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
+670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 2 lb
+670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 2 lb
+588.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
+924.667 409.347 20 0 0 1 nc
+588.113 544.499 20 0 0 1 nc
+670.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
+201.208 38.3422 20 1 1 0 nc
+116.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
+415.393 -289.516 20 0.5 0 0 nc
+730.084 -307.139 20 0.5 0 0 nc
+526.164 32.7279 20 0.5 0 0 nc
+762.812 -17.6227 20 0.5 0 0 nc
+-67.9734 319.727 20 0.5 0 0 nc
+329.797 314.692 20 0.5 0 0 nc
+-5.03507 561.41 20 0.5 0 0 nc
+422.945 521.129 20 0.5 0 0 nc
+-470.779 158.605 20 0 1 1 nc
+986.873 -115.807 20 0.5 0 0 nc
+906.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
+206.221 -205.967 20 0 0 0.5 nc
+277.311 -252.33 20 0 0 0.5 nc
+271.13 -175.058 20 0 0 0.5 nc
+366.947 -110.15 20 0 0 0.5 nc
+397.855 -196.694 20 0 0 0.5 nc
+438.037 -88.514 20 0 0 0.5 nc
+286.584 -48.3327 20 0 0 0.5 nc
+212.403 -23.6057 20 0 0 0.5 nc
+280.402 10.3938 20 0 0 0.5 nc
+694.579 115.483 20 1 0 0 nc
+574.035 177.301 20 0 1 0 nc
+grestore
+grestore
+showpage
Index: doc/images/node_biconnected_components.eps
===================================================================
--- doc/images/node_biconnected_components.eps (revision 587)
+++ doc/images/node_biconnected_components.eps (revision 587)
@@ -0,0 +1,159 @@
+%!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
+ 4 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
+ 2 index 1 index sub 2 index 2 index add lineto
+ 2 index 1 index sub 2 index 2 index sub lineto
+ 2 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
+ 2 index 2 index 2 index add lineto
+ 2 index 1 index sub 2 index lineto
+ 2 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
+90 rotate
+0 -842 translate
+71.0944 15 translate
+0.434694 dup scale
+90 rotate
+860.856 -588.349 translate
+%Edges:
+gsave
+574.035 177.301 622.149 225.748 670.264 274.195 0 1 0 5 lb
+694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 5 lb
+280.402 10.3938 246.402 -6.60595 212.403 -23.6057 1 1 0.5 5 lb
+280.402 10.3938 283.493 -18.9695 286.584 -48.3327 1 1 0.5 5 lb
+212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 1 1 0.5 5 lb
+286.584 -48.3327 326.765 -79.2414 366.947 -110.15 1 0.5 1 5 lb
+286.584 -48.3327 278.857 -111.695 271.13 -175.058 1 0.5 1 5 lb
+438.037 -88.514 417.946 -142.604 397.855 -196.694 0.5 0.5 1 5 lb
+438.037 -88.514 402.492 -99.332 366.947 -110.15 0.5 0.5 1 5 lb
+397.855 -196.694 382.401 -153.422 366.947 -110.15 0.5 0.5 1 5 lb
+366.947 -110.15 319.038 -142.604 271.13 -175.058 1 0.5 1 5 lb
+271.13 -175.058 274.221 -213.694 277.311 -252.33 0.5 1 1 5 lb
+271.13 -175.058 238.675 -190.512 206.221 -205.967 0.5 1 1 5 lb
+277.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
+906.312 201.403 946.592 42.798 986.873 -115.807 0 0.5 0.5 5 lb
+906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0.5 0.5 5 lb
+986.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
+422.945 521.129 208.955 541.269 -5.03507 561.41 0.5 0 0.5 5 lb
+422.945 521.129 376.371 417.911 329.797 314.692 0.5 0 0.5 5 lb
+422.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
+329.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
+762.812 -17.6227 644.488 7.5526 526.164 32.7279 0.5 0.5 0.5 5 lb
+762.812 -17.6227 746.448 -162.381 730.084 -307.139 0.5 0.5 0.5 5 lb
+526.164 32.7279 470.779 -128.394 415.393 -289.516 0.5 0.5 0.5 5 lb
+730.084 -307.139 572.738 -298.327 415.393 -289.516 0.5 0.5 0.5 5 lb
+415.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
+116.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
+670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 5 lb
+670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 5 lb
+588.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
+924.667 409.347 20 0 0 1 nc
+588.113 544.499 20 0 0 1 nc
+670.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
+201.208 38.3422 20 0 0 1 nc
+116.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
+415.393 -289.516 20 1 0 0 nc
+730.084 -307.139 20 0 0 1 nc
+526.164 32.7279 20 1 0 0 nc
+762.812 -17.6227 20 1 0 0 nc
+-67.9734 319.727 20 0 0 1 nc
+329.797 314.692 20 0 0 1 nc
+-5.03507 561.41 20 0 0 1 nc
+422.945 521.129 20 0 0 1 nc
+-470.779 158.605 20 1 0 0 nc
+986.873 -115.807 20 0 0 1 nc
+906.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
+206.221 -205.967 20 0 0 1 nc
+277.311 -252.33 20 0 0 1 nc
+271.13 -175.058 20 1 0 0 nc
+366.947 -110.15 20 1 0 0 nc
+397.855 -196.694 20 0 0 1 nc
+438.037 -88.514 20 0 0 1 nc
+286.584 -48.3327 20 1 0 0 nc
+212.403 -23.6057 20 0 0 1 nc
+280.402 10.3938 20 0 0 1 nc
+694.579 115.483 20 0 0 1 nc
+574.035 177.301 20 0 0 1 nc
+grestore
+grestore
+showpage
Index: doc/images/strongly_connected_components.eps
===================================================================
--- doc/images/strongly_connected_components.eps (revision 587)
+++ doc/images/strongly_connected_components.eps (revision 587)
@@ -0,0 +1,180 @@
+%!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
+ 4 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
+ 2 index 1 index sub 2 index 2 index add lineto
+ 2 index 1 index sub 2 index 2 index sub lineto
+ 2 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
+ 2 index 2 index 2 index add lineto
+ 2 index 1 index sub 2 index lineto
+ 2 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
+90 rotate
+0 -842 translate
+77.1122 15 translate
+0.585745 dup scale
+90 rotate
+695.963 -397.916 translate
+%Edges:
+gsave
+2 setlinewidth 0 0 1 setrgbcolor newpath
+218.178 27.2723 moveto
+192.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
+2 setlinewidth 0 0 1 setrgbcolor newpath
+44.8044 15.5841 moveto
+119.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
+2 setlinewidth 1 0 0 setrgbcolor newpath
+218.178 27.2723 moveto
+285.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
+2 setlinewidth 0 0 1 setrgbcolor newpath
+157.79 -130.517 moveto
+108.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
+2 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
+2 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
+2 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
+2 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
+2 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
+2 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
+2 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
+2 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
+2 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
+2 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
+2 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
+2 setlinewidth 1 0 0 setrgbcolor newpath
+5.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
+2 setlinewidth 0 0 1 setrgbcolor newpath
+169.478 311.683 moveto
+96.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
+2 setlinewidth 0 0 1 setrgbcolor newpath
+342.851 111.037 moveto
+263.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
+2 setlinewidth 0 0 1 setrgbcolor newpath
+5.84406 175.322 moveto
+163.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
+2 setlinewidth 0 0 1 setrgbcolor newpath
+342.851 111.037 moveto
+497.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
+2 setlinewidth 0 0 1 setrgbcolor newpath
+364.28 -222.074 moveto
+354.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
+2 setlinewidth 0 0 1 setrgbcolor newpath
+670.118 -118.829 moveto
+528.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
+2 setlinewidth 1 0 0 setrgbcolor newpath
+-105.193 -261.035 moveto
+118.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
+2 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
+2 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
+364.28 -222.074 20 1 1 0 nc
+670.118 -118.829 20 1 1 0 nc
+342.851 111.037 20 1 1 0 nc
+5.84406 175.322 20 1 1 0 nc
+169.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
+44.8044 15.5841 20 0 0 1 nc
+157.79 -130.517 20 0 0 1 nc
+218.178 27.2723 20 0 0 1 nc
+grestore
+grestore
+showpage
Index: doc/mainpage.dox
===================================================================
--- doc/mainpage.dox (revision 440)
+++ doc/mainpage.dox (revision 559)
@@ -46,14 +46,9 @@
"Quick Tour to LEMON" which will guide you along.
-If you already feel like using our library, see the page that tells you
-\ref getstart "How to start using LEMON".
-
-If you
-want to see how LEMON works, see
-some \ref demoprograms "demo programs".
+If you already feel like using our library, see the
+LEMON Tutorial.
If you know what you are looking for then try to find it under the
-Modules
-section.
+Modules section.
If you are a user of the old (0.x) series of LEMON, please check out the
Index: lemon/CMakeLists.txt
===================================================================
--- lemon/CMakeLists.txt (revision 515)
+++ lemon/CMakeLists.txt (revision 549)
@@ -1,5 +1,5 @@
INCLUDE_DIRECTORIES(
- ${CMAKE_SOURCE_DIR}
- ${CMAKE_BINARY_DIR}
+ ${PROJECT_SOURCE_DIR}
+ ${PROJECT_BINARY_DIR}
)
Index: lemon/Makefile.am
===================================================================
--- lemon/Makefile.am (revision 601)
+++ lemon/Makefile.am (revision 611)
@@ -13,13 +13,15 @@
lemon/lp_base.cc \
lemon/lp_skeleton.cc \
- lemon/random.cc \
+ lemon/random.cc \
lemon/bits/windows.cc
lemon_libemon_la_CXXFLAGS = \
+ $(AM_CXXFLAGS) \
$(GLPK_CFLAGS) \
$(CPLEX_CFLAGS) \
$(SOPLEX_CXXFLAGS) \
- $(CLP_CXXFLAGS)
+ $(CLP_CXXFLAGS) \
+ $(CBC_CXXFLAGS)
lemon_libemon_la_LDFLAGS = \
@@ -27,5 +29,6 @@
$(CPLEX_LIBS) \
$(SOPLEX_LIBS) \
- $(CLP_LIBS)
+ $(CLP_LIBS) \
+ $(CBC_LIBS)
if HAVE_GLPK
@@ -43,4 +46,8 @@
if HAVE_CLP
lemon_libemon_la_SOURCES += lemon/clp.cc
+endif
+
+if HAVE_CBC
+lemon_libemon_la_SOURCES += lemon/cbc.cc
endif
@@ -69,4 +76,5 @@
lemon/full_graph.h \
lemon/glpk.h \
+ lemon/gomory_hu.h \
lemon/graph_to_eps.h \
lemon/grid_graph.h \
@@ -82,6 +90,6 @@
lemon/list_graph.h \
lemon/maps.h \
+ lemon/matching.h \
lemon/math.h \
- lemon/max_matching.h \
lemon/min_cost_arborescence.h \
lemon/nauty_reader.h \
Index: lemon/adaptors.h
===================================================================
--- lemon/adaptors.h (revision 519)
+++ lemon/adaptors.h (revision 579)
@@ -2193,4 +2193,7 @@
typedef typename ItemSetTraits::ItemNotifier EdgeNotifier;
EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
+
+ typedef EdgeNotifier ArcNotifier;
+ ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
protected:
@@ -2255,7 +2258,8 @@
/// This map adaptor class adapts two arc maps of the underlying
/// digraph to get an arc map of the undirected graph.
- /// Its value type is inherited from the first arc map type
- /// (\c %ForwardMap).
- template
+ /// Its value type is inherited from the first arc map type (\c FW).
+ /// \tparam FW The type of the "foward" arc map.
+ /// \tparam BK The type of the "backward" arc map.
+ template
class CombinedArcMap {
public:
@@ -2264,15 +2268,15 @@
typedef typename Parent::Arc Key;
/// The value type of the map
- typedef typename ForwardMap::Value Value;
-
- typedef typename MapTraits::ReferenceMapTag ReferenceMapTag;
-
- typedef typename MapTraits::ReturnValue ReturnValue;
- typedef typename MapTraits::ConstReturnValue ConstReturnValue;
- typedef typename MapTraits::ReturnValue Reference;
- typedef typename MapTraits::ConstReturnValue ConstReference;
+ typedef typename FW::Value Value;
+
+ typedef typename MapTraits::ReferenceMapTag ReferenceMapTag;
+
+ typedef typename MapTraits::ReturnValue ReturnValue;
+ typedef typename MapTraits::ConstReturnValue ConstReturnValue;
+ typedef typename MapTraits::ReturnValue Reference;
+ typedef typename MapTraits::ConstReturnValue ConstReference;
/// Constructor
- CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
+ CombinedArcMap(FW& forward, BK& backward)
: _forward(&forward), _backward(&backward) {}
@@ -2306,6 +2310,6 @@
protected:
- ForwardMap* _forward;
- BackwardMap* _backward;
+ FW* _forward;
+ BK* _backward;
};
@@ -2314,29 +2318,26 @@
///
/// This function just returns a combined arc map.
- template
- static CombinedArcMap
- combinedArcMap(ForwardMap& forward, BackwardMap& backward) {
- return CombinedArcMap(forward, backward);
- }
-
- template
- static CombinedArcMap
- combinedArcMap(const ForwardMap& forward, BackwardMap& backward) {
- return CombinedArcMap(forward, backward);
- }
-
- template
- static CombinedArcMap
- combinedArcMap(ForwardMap& forward, const BackwardMap& backward) {
- return CombinedArcMap(forward, backward);
- }
-
- template
- static CombinedArcMap
- combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) {
- return CombinedArcMap(forward, backward);
+ template
+ static CombinedArcMap
+ combinedArcMap(FW& forward, BK& backward) {
+ return CombinedArcMap(forward, backward);
+ }
+
+ template
+ static CombinedArcMap
+ combinedArcMap(const FW& forward, BK& backward) {
+ return CombinedArcMap(forward, backward);
+ }
+
+ template
+ static CombinedArcMap
+ combinedArcMap(FW& forward, const BK& backward) {
+ return CombinedArcMap(forward, backward);
+ }
+
+ template
+ static CombinedArcMap
+ combinedArcMap(const FW& forward, const BK& backward) {
+ return CombinedArcMap(forward, backward);
}
@@ -3407,7 +3408,8 @@
/// This map adaptor class adapts two node maps of the original digraph
/// to get a node map of the split digraph.
- /// Its value type is inherited from the first node map type
- /// (\c InNodeMap).
- template
+ /// Its value type is inherited from the first node map type (\c IN).
+ /// \tparam IN The type of the node map for the in-nodes.
+ /// \tparam OUT The type of the node map for the out-nodes.
+ template
class CombinedNodeMap {
public:
@@ -3416,14 +3418,14 @@
typedef Node Key;
/// The value type of the map
- typedef typename InNodeMap::Value Value;
-
- typedef typename MapTraits::ReferenceMapTag ReferenceMapTag;
- typedef typename MapTraits::ReturnValue ReturnValue;
- typedef typename MapTraits::ConstReturnValue ConstReturnValue;
- typedef typename MapTraits::ReturnValue Reference;
- typedef typename MapTraits::ConstReturnValue ConstReference;
+ typedef typename IN::Value Value;
+
+ typedef typename MapTraits::ReferenceMapTag ReferenceMapTag;
+ typedef typename MapTraits::ReturnValue ReturnValue;
+ typedef typename MapTraits::ConstReturnValue ConstReturnValue;
+ typedef typename MapTraits::ReturnValue Reference;
+ typedef typename MapTraits::ConstReturnValue ConstReference;
/// Constructor
- CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
+ CombinedNodeMap(IN& in_map, OUT& out_map)
: _in_map(in_map), _out_map(out_map) {}
@@ -3457,6 +3459,6 @@
private:
- InNodeMap& _in_map;
- OutNodeMap& _out_map;
+ IN& _in_map;
+ OUT& _out_map;
};
@@ -3466,27 +3468,26 @@
///
/// This function just returns a combined node map.
- template
- static CombinedNodeMap
- combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
- return CombinedNodeMap(in_map, out_map);
- }
-
- template
- static CombinedNodeMap
- combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
- return CombinedNodeMap(in_map, out_map);
- }
-
- template
- static CombinedNodeMap
- combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
- return CombinedNodeMap(in_map, out_map);
- }
-
- template
- static CombinedNodeMap
- combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
- return CombinedNodeMap(in_map, out_map);
+ template
+ static CombinedNodeMap
+ combinedNodeMap(IN& in_map, OUT& out_map) {
+ return CombinedNodeMap(in_map, out_map);
+ }
+
+ template
+ static CombinedNodeMap
+ combinedNodeMap(const IN& in_map, OUT& out_map) {
+ return CombinedNodeMap(in_map, out_map);
+ }
+
+ template
+ static CombinedNodeMap
+ combinedNodeMap(IN& in_map, const OUT& out_map) {
+ return CombinedNodeMap(in_map, out_map);
+ }
+
+ template
+ static CombinedNodeMap
+ combinedNodeMap(const IN& in_map, const OUT& out_map) {
+ return CombinedNodeMap(in_map, out_map);
}
@@ -3496,7 +3497,8 @@
/// This map adaptor class adapts an arc map and a node map of the
/// original digraph to get an arc map of the split digraph.
- /// Its value type is inherited from the original arc map type
- /// (\c ArcMap).
- template
+ /// Its value type is inherited from the original arc map type (\c AM).
+ /// \tparam AM The type of the arc map.
+ /// \tparam NM the type of the node map.
+ template
class CombinedArcMap {
public:
@@ -3505,14 +3507,14 @@
typedef Arc Key;
/// The value type of the map
- typedef typename ArcMap::Value Value;
-
- typedef typename MapTraits::ReferenceMapTag ReferenceMapTag;
- typedef typename MapTraits::ReturnValue ReturnValue;
- typedef typename MapTraits::ConstReturnValue ConstReturnValue;
- typedef typename MapTraits::ReturnValue Reference;
- typedef typename MapTraits::ConstReturnValue ConstReference;
+ typedef typename AM::Value Value;
+
+ typedef typename MapTraits::ReferenceMapTag ReferenceMapTag;
+ typedef typename MapTraits::ReturnValue ReturnValue;
+ typedef typename MapTraits::ConstReturnValue ConstReturnValue;
+ typedef typename MapTraits::ReturnValue Reference;
+ typedef typename MapTraits::ConstReturnValue ConstReference;
/// Constructor
- CombinedArcMap(ArcMap& arc_map, NodeMap& node_map)
+ CombinedArcMap(AM& arc_map, NM& node_map)
: _arc_map(arc_map), _node_map(node_map) {}
@@ -3545,6 +3547,8 @@
private:
- ArcMap& _arc_map;
- NodeMap& _node_map;
+
+ AM& _arc_map;
+ NM& _node_map;
+
};
Index: lemon/bin_heap.h
===================================================================
--- lemon/bin_heap.h (revision 440)
+++ lemon/bin_heap.h (revision 584)
@@ -34,27 +34,28 @@
///\brief A Binary Heap implementation.
///
- ///This class implements the \e binary \e heap data structure. A \e heap
- ///is a data structure for storing items with specified values called \e
- ///priorities in such a way that finding the item with minimum priority is
- ///efficient. \c Compare specifies the ordering of the priorities. In a heap
- ///one can change the priority of an item, add or erase an item, etc.
+ ///This class implements the \e binary \e heap data structure.
+ ///
+ ///A \e heap is a data structure for storing items with specified values
+ ///called \e priorities in such a way that finding the item with minimum
+ ///priority is efficient. \c Comp specifies the ordering of the priorities.
+ ///In a heap one can change the priority of an item, add or erase an
+ ///item, etc.
///
- ///\tparam _Prio Type of the priority of the items.
- ///\tparam _ItemIntMap A read and writable Item int map, used internally
+ ///\tparam PR Type of the priority of the items.
+ ///\tparam IM A read and writable item map with int values, used internally
///to handle the cross references.
- ///\tparam _Compare A class for the ordering of the priorities. The
- ///default is \c std::less<_Prio>.
+ ///\tparam Comp A functor class for the ordering of the priorities.
+ ///The default is \c std::less.
///
///\sa FibHeap
///\sa Dijkstra
- template >
+ template >
class BinHeap {
public:
///\e
- typedef _ItemIntMap ItemIntMap;
- ///\e
- typedef _Prio Prio;
+ typedef IM ItemIntMap;
+ ///\e
+ typedef PR Prio;
///\e
typedef typename ItemIntMap::Key Item;
@@ -62,5 +63,5 @@
typedef std::pair- Pair;
///\e
- typedef _Compare Compare;
+ typedef Comp Compare;
/// \brief Type to represent the items states.
@@ -70,16 +71,16 @@
/// heap's point of view, but may be useful to the user.
///
- /// The ItemIntMap \e should be initialized in such way that it maps
- /// PRE_HEAP (-1) to any element to be put in the heap...
+ /// The item-int map must be initialized in such way that it assigns
+ /// \c PRE_HEAP (-1) to any element to be put in the heap.
enum State {
- IN_HEAP = 0,
- PRE_HEAP = -1,
- POST_HEAP = -2
+ IN_HEAP = 0, ///< = 0.
+ PRE_HEAP = -1, ///< = -1.
+ POST_HEAP = -2 ///< = -2.
};
private:
- std::vector data;
- Compare comp;
- ItemIntMap &iim;
+ std::vector _data;
+ Compare _comp;
+ ItemIntMap &_iim;
public:
@@ -87,19 +88,19 @@
///
/// The constructor.
- /// \param _iim should be given to the constructor, since it is used
+ /// \param map should be given to the constructor, since it is used
+ /// internally to handle the cross references. The value of the map
+ /// must be \c PRE_HEAP (-1) for every item.
+ explicit BinHeap(ItemIntMap &map) : _iim(map) {}
+
+ /// \brief The constructor.
+ ///
+ /// The constructor.
+ /// \param map should be given to the constructor, since it is used
/// internally to handle the cross references. The value of the map
/// should be PRE_HEAP (-1) for each element.
- explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
-
- /// \brief The constructor.
- ///
- /// The constructor.
- /// \param _iim should be given to the constructor, since it is used
- /// internally to handle the cross references. The value of the map
- /// should be PRE_HEAP (-1) for each element.
- ///
- /// \param _comp The comparator function object.
- BinHeap(ItemIntMap &_iim, const Compare &_comp)
- : iim(_iim), comp(_comp) {}
+ ///
+ /// \param comp The comparator function object.
+ BinHeap(ItemIntMap &map, const Compare &comp)
+ : _iim(map), _comp(comp) {}
@@ -107,10 +108,10 @@
///
/// \brief Returns the number of items stored in the heap.
- int size() const { return data.size(); }
+ int size() const { return _data.size(); }
/// \brief Checks if the heap stores no items.
///
/// Returns \c true if and only if the heap stores no items.
- bool empty() const { return data.empty(); }
+ bool empty() const { return _data.empty(); }
/// \brief Make empty this heap.
@@ -121,5 +122,5 @@
/// each item to \c PRE_HEAP.
void clear() {
- data.clear();
+ _data.clear();
}
@@ -129,11 +130,11 @@
static int second_child(int i) { return 2*i+2; }
bool less(const Pair &p1, const Pair &p2) const {
- return comp(p1.second, p2.second);
+ return _comp(p1.second, p2.second);
}
int bubble_up(int hole, Pair p) {
int par = parent(hole);
- while( hole>0 && less(p,data[par]) ) {
- move(data[par],hole);
+ while( hole>0 && less(p,_data[par]) ) {
+ move(_data[par],hole);
hole = par;
par = parent(hole);
@@ -146,16 +147,16 @@
int child = second_child(hole);
while(child < length) {
- if( less(data[child-1], data[child]) ) {
+ if( less(_data[child-1], _data[child]) ) {
--child;
}
- if( !less(data[child], p) )
+ if( !less(_data[child], p) )
goto ok;
- move(data[child], hole);
+ move(_data[child], hole);
hole = child;
child = second_child(hole);
}
child--;
- if( child 0) {
- bubble_down(0, data[n], n);
- }
- data.pop_back();
+ bubble_down(0, _data[n], n);
+ }
+ _data.pop_back();
}
@@ -225,13 +226,13 @@
/// \pre The item should be in the heap.
void erase(const Item &i) {
- int h = iim[i];
- int n = data.size()-1;
- iim.set(data[h].first, POST_HEAP);
+ int h = _iim[i];
+ int n = _data.size()-1;
+ _iim.set(_data[h].first, POST_HEAP);
if( h < n ) {
- if ( bubble_up(h, data[n]) == h) {
- bubble_down(h, data[n], n);
+ if ( bubble_up(h, _data[n]) == h) {
+ bubble_down(h, _data[n], n);
}
}
- data.pop_back();
+ _data.pop_back();
}
@@ -240,9 +241,9 @@
///
/// This function returns the priority of item \c i.
+ /// \param i The item.
/// \pre \c i must be in the heap.
- /// \param i The item.
Prio operator[](const Item &i) const {
- int idx = iim[i];
- return data[idx].second;
+ int idx = _iim[i];
+ return _data[idx].second;
}
@@ -255,13 +256,13 @@
/// \param p The priority.
void set(const Item &i, const Prio &p) {
- int idx = iim[i];
+ int idx = _iim[i];
if( idx < 0 ) {
push(i,p);
}
- else if( comp(p, data[idx].second) ) {
+ else if( _comp(p, _data[idx].second) ) {
bubble_up(idx, Pair(i,p));
}
else {
- bubble_down(idx, Pair(i,p), data.size());
+ bubble_down(idx, Pair(i,p), _data.size());
}
}
@@ -270,23 +271,23 @@
///
/// This method decreases the priority of item \c i to \c p.
+ /// \param i The item.
+ /// \param p The priority.
/// \pre \c i must be stored in the heap with priority at least \c
/// p relative to \c Compare.
+ void decrease(const Item &i, const Prio &p) {
+ int idx = _iim[i];
+ bubble_up(idx, Pair(i,p));
+ }
+
+ /// \brief Increases the priority of \c i to \c p.
+ ///
+ /// This method sets the priority of item \c i to \c p.
/// \param i The item.
/// \param p The priority.
- void decrease(const Item &i, const Prio &p) {
- int idx = iim[i];
- bubble_up(idx, Pair(i,p));
- }
-
- /// \brief Increases the priority of \c i to \c p.
- ///
- /// This method sets the priority of item \c i to \c p.
/// \pre \c i must be stored in the heap with priority at most \c
/// p relative to \c Compare.
- /// \param i The item.
- /// \param p The priority.
void increase(const Item &i, const Prio &p) {
- int idx = iim[i];
- bubble_down(idx, Pair(i,p), data.size());
+ int idx = _iim[i];
+ bubble_down(idx, Pair(i,p), _data.size());
}
@@ -300,5 +301,5 @@
/// \param i The item.
State state(const Item &i) const {
- int s = iim[i];
+ int s = _iim[i];
if( s>=0 )
s=0;
@@ -320,5 +321,5 @@
erase(i);
}
- iim[i] = st;
+ _iim[i] = st;
break;
case IN_HEAP:
@@ -334,8 +335,8 @@
/// with the same prioriority as prevoiusly the \c i item.
void replace(const Item& i, const Item& j) {
- int idx = iim[i];
- iim.set(i, iim[j]);
- iim.set(j, idx);
- data[idx].first = j;
+ int idx = _iim[i];
+ _iim.set(i, _iim[j]);
+ _iim.set(j, idx);
+ _data[idx].first = j;
}
Index: lemon/bits/edge_set_extender.h
===================================================================
--- lemon/bits/edge_set_extender.h (revision 519)
+++ lemon/bits/edge_set_extender.h (revision 559)
@@ -25,12 +25,12 @@
#include
-///\ingroup digraphbits
-///\file
-///\brief Extenders for the arc set types
+//\ingroup digraphbits
+//\file
+//\brief Extenders for the arc set types
namespace lemon {
- /// \ingroup digraphbits
- ///
- /// \brief Extender for the ArcSets
+ // \ingroup digraphbits
+ //
+ // \brief Extender for the ArcSets
template
class ArcSetExtender : public Base {
@@ -73,5 +73,5 @@
// Alteration notifier extensions
- /// The arc observer registry.
+ // The arc observer registry.
typedef AlterationNotifier ArcNotifier;
@@ -84,7 +84,5 @@
using Parent::notifier;
- /// \brief Gives back the arc alteration notifier.
- ///
- /// Gives back the arc alteration notifier.
+ // Gives back the arc alteration notifier.
ArcNotifier& notifier(Arc) const {
return arc_notifier;
@@ -186,28 +184,28 @@
};
- /// \brief Base node of the iterator
- ///
- /// Returns the base node (ie. the source in this case) of the iterator
+ // \brief Base node of the iterator
+ //
+ // Returns the base node (ie. the source in this case) of the iterator
Node baseNode(const OutArcIt &e) const {
return Parent::source(static_cast(e));
}
- /// \brief Running node of the iterator
- ///
- /// Returns the running node (ie. the target in this case) of the
- /// iterator
+ // \brief Running node of the iterator
+ //
+ // Returns the running node (ie. the target in this case) of the
+ // iterator
Node runningNode(const OutArcIt &e) const {
return Parent::target(static_cast(e));
}
- /// \brief Base node of the iterator
- ///
- /// Returns the base node (ie. the target in this case) of the iterator
+ // \brief Base node of the iterator
+ //
+ // Returns the base node (ie. the target in this case) of the iterator
Node baseNode(const InArcIt &e) const {
return Parent::target(static_cast(e));
}
- /// \brief Running node of the iterator
- ///
- /// Returns the running node (ie. the source in this case) of the
- /// iterator
+ // \brief Running node of the iterator
+ //
+ // Returns the running node (ie. the source in this case) of the
+ // iterator
Node runningNode(const InArcIt &e) const {
return Parent::source(static_cast(e));
@@ -272,7 +270,7 @@
- /// \ingroup digraphbits
- ///
- /// \brief Extender for the EdgeSets
+ // \ingroup digraphbits
+ //
+ // \brief Extender for the EdgeSets
template
class EdgeSetExtender : public Base {
@@ -493,41 +491,41 @@
};
- /// \brief Base node of the iterator
- ///
- /// Returns the base node (ie. the source in this case) of the iterator
+ // \brief Base node of the iterator
+ //
+ // Returns the base node (ie. the source in this case) of the iterator
Node baseNode(const OutArcIt &e) const {
return Parent::source(static_cast(e));
}
- /// \brief Running node of the iterator
- ///
- /// Returns the running node (ie. the target in this case) of the
- /// iterator
+ // \brief Running node of the iterator
+ //
+ // Returns the running node (ie. the target in this case) of the
+ // iterator
Node runningNode(const OutArcIt &e) const {
return Parent::target(static_cast(e));
}
- /// \brief Base node of the iterator
- ///
- /// Returns the base node (ie. the target in this case) of the iterator
+ // \brief Base node of the iterator
+ //
+ // Returns the base node (ie. the target in this case) of the iterator
Node baseNode(const InArcIt &e) const {
return Parent::target(static_cast(e));
}
- /// \brief Running node of the iterator
- ///
- /// Returns the running node (ie. the source in this case) of the
- /// iterator
+ // \brief Running node of the iterator
+ //
+ // Returns the running node (ie. the source in this case) of the
+ // iterator
Node runningNode(const InArcIt &e) const {
return Parent::source(static_cast(e));
}
- /// Base node of the iterator
- ///
- /// Returns the base node of the iterator
+ // Base node of the iterator
+ //
+ // Returns the base node of the iterator
Node baseNode(const IncEdgeIt &e) const {
return e.direction ? u(e) : v(e);
}
- /// Running node of the iterator
- ///
- /// Returns the running node of the iterator
+ // Running node of the iterator
+ //
+ // Returns the running node of the iterator
Node runningNode(const IncEdgeIt &e) const {
return e.direction ? v(e) : u(e);
Index: lemon/bits/graph_adaptor_extender.h
===================================================================
--- lemon/bits/graph_adaptor_extender.h (revision 455)
+++ lemon/bits/graph_adaptor_extender.h (revision 580)
@@ -22,6 +22,4 @@
#include
#include
-
-#include
namespace lemon {
Index: lemon/bits/map_extender.h
===================================================================
--- lemon/bits/map_extender.h (revision 440)
+++ lemon/bits/map_extender.h (revision 580)
@@ -48,4 +48,6 @@
typedef typename Parent::Key Key;
typedef typename Parent::Value Value;
+ typedef typename Parent::Reference Reference;
+ typedef typename Parent::ConstReference ConstReference;
class MapIt;
@@ -188,4 +190,6 @@
typedef typename Parent::Key Key;
typedef typename Parent::Value Value;
+ typedef typename Parent::Reference Reference;
+ typedef typename Parent::ConstReference ConstReference;
class MapIt;
Index: lemon/cbc.cc
===================================================================
--- lemon/cbc.cc (revision 576)
+++ lemon/cbc.cc (revision 576)
@@ -0,0 +1,463 @@
+/* -*- 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.
+ *
+ */
+
+///\file
+///\brief Implementation of the CBC MIP solver interface.
+
+#include "cbc.h"
+
+#include
+#include
+#include
+
+#ifdef COIN_HAS_CLP
+#include "coin/OsiClpSolverInterface.hpp"
+#endif
+#ifdef COIN_HAS_OSL
+#include "coin/OsiOslSolverInterface.hpp"
+#endif
+
+#include "coin/CbcCutGenerator.hpp"
+#include "coin/CbcHeuristicLocal.hpp"
+#include "coin/CbcHeuristicGreedy.hpp"
+#include "coin/CbcHeuristicFPump.hpp"
+#include "coin/CbcHeuristicRINS.hpp"
+
+#include "coin/CglGomory.hpp"
+#include "coin/CglProbing.hpp"
+#include "coin/CglKnapsackCover.hpp"
+#include "coin/CglOddHole.hpp"
+#include "coin/CglClique.hpp"
+#include "coin/CglFlowCover.hpp"
+#include "coin/CglMixedIntegerRounding.hpp"
+
+#include "coin/CbcHeuristic.hpp"
+
+namespace lemon {
+
+ CbcMip::CbcMip() {
+ _prob = new CoinModel();
+ _prob->setProblemName("LEMON");
+ _osi_solver = 0;
+ _cbc_model = 0;
+ messageLevel(MESSAGE_NOTHING);
+ }
+
+ CbcMip::CbcMip(const CbcMip& other) {
+ _prob = new CoinModel(*other._prob);
+ _prob->setProblemName("LEMON");
+ _osi_solver = 0;
+ _cbc_model = 0;
+ messageLevel(MESSAGE_NOTHING);
+ }
+
+ CbcMip::~CbcMip() {
+ delete _prob;
+ if (_osi_solver) delete _osi_solver;
+ if (_cbc_model) delete _cbc_model;
+ }
+
+ const char* CbcMip::_solverName() const { return "CbcMip"; }
+
+ int CbcMip::_addCol() {
+ _prob->addColumn(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX, 0.0, 0, false);
+ return _prob->numberColumns() - 1;
+ }
+
+ CbcMip* CbcMip::newSolver() const {
+ CbcMip* newlp = new CbcMip;
+ return newlp;
+ }
+
+ CbcMip* CbcMip::cloneSolver() const {
+ CbcMip* copylp = new CbcMip(*this);
+ return copylp;
+ }
+
+ int CbcMip::_addRow() {
+ _prob->addRow(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX);
+ return _prob->numberRows() - 1;
+ }
+
+
+ void CbcMip::_eraseCol(int i) {
+ _prob->deleteColumn(i);
+ }
+
+ void CbcMip::_eraseRow(int i) {
+ _prob->deleteRow(i);
+ }
+
+ void CbcMip::_eraseColId(int i) {
+ cols.eraseIndex(i);
+ }
+
+ void CbcMip::_eraseRowId(int i) {
+ rows.eraseIndex(i);
+ }
+
+ void CbcMip::_getColName(int c, std::string& name) const {
+ name = _prob->getColumnName(c);
+ }
+
+ void CbcMip::_setColName(int c, const std::string& name) {
+ _prob->setColumnName(c, name.c_str());
+ }
+
+ int CbcMip::_colByName(const std::string& name) const {
+ return _prob->column(name.c_str());
+ }
+
+ void CbcMip::_getRowName(int r, std::string& name) const {
+ name = _prob->getRowName(r);
+ }
+
+ void CbcMip::_setRowName(int r, const std::string& name) {
+ _prob->setRowName(r, name.c_str());
+ }
+
+ int CbcMip::_rowByName(const std::string& name) const {
+ return _prob->row(name.c_str());
+ }
+
+ void CbcMip::_setRowCoeffs(int i, ExprIterator b, ExprIterator e) {
+ for (ExprIterator it = b; it != e; ++it) {
+ _prob->setElement(i, it->first, it->second);
+ }
+ }
+
+ void CbcMip::_getRowCoeffs(int ix, InsertIterator b) const {
+ int length = _prob->numberRows();
+
+ std::vector indices(length);
+ std::vector values(length);
+
+ length = _prob->getRow(ix, &indices[0], &values[0]);
+
+ for (int i = 0; i < length; ++i) {
+ *b = std::make_pair(indices[i], values[i]);
+ ++b;
+ }
+ }
+
+ void CbcMip::_setColCoeffs(int ix, ExprIterator b, ExprIterator e) {
+ for (ExprIterator it = b; it != e; ++it) {
+ _prob->setElement(it->first, ix, it->second);
+ }
+ }
+
+ void CbcMip::_getColCoeffs(int ix, InsertIterator b) const {
+ int length = _prob->numberColumns();
+
+ std::vector indices(length);
+ std::vector values(length);
+
+ length = _prob->getColumn(ix, &indices[0], &values[0]);
+
+ for (int i = 0; i < length; ++i) {
+ *b = std::make_pair(indices[i], values[i]);
+ ++b;
+ }
+ }
+
+ void CbcMip::_setCoeff(int ix, int jx, Value value) {
+ _prob->setElement(ix, jx, value);
+ }
+
+ CbcMip::Value CbcMip::_getCoeff(int ix, int jx) const {
+ return _prob->getElement(ix, jx);
+ }
+
+
+ void CbcMip::_setColLowerBound(int i, Value lo) {
+ LEMON_ASSERT(lo != INF, "Invalid bound");
+ _prob->setColumnLower(i, lo == - INF ? - COIN_DBL_MAX : lo);
+ }
+
+ CbcMip::Value CbcMip::_getColLowerBound(int i) const {
+ double val = _prob->getColumnLower(i);
+ return val == - COIN_DBL_MAX ? - INF : val;
+ }
+
+ void CbcMip::_setColUpperBound(int i, Value up) {
+ LEMON_ASSERT(up != -INF, "Invalid bound");
+ _prob->setColumnUpper(i, up == INF ? COIN_DBL_MAX : up);
+ }
+
+ CbcMip::Value CbcMip::_getColUpperBound(int i) const {
+ double val = _prob->getColumnUpper(i);
+ return val == COIN_DBL_MAX ? INF : val;
+ }
+
+ void CbcMip::_setRowLowerBound(int i, Value lo) {
+ LEMON_ASSERT(lo != INF, "Invalid bound");
+ _prob->setRowLower(i, lo == - INF ? - COIN_DBL_MAX : lo);
+ }
+
+ CbcMip::Value CbcMip::_getRowLowerBound(int i) const {
+ double val = _prob->getRowLower(i);
+ return val == - COIN_DBL_MAX ? - INF : val;
+ }
+
+ void CbcMip::_setRowUpperBound(int i, Value up) {
+ LEMON_ASSERT(up != -INF, "Invalid bound");
+ _prob->setRowUpper(i, up == INF ? COIN_DBL_MAX : up);
+ }
+
+ CbcMip::Value CbcMip::_getRowUpperBound(int i) const {
+ double val = _prob->getRowUpper(i);
+ return val == COIN_DBL_MAX ? INF : val;
+ }
+
+ void CbcMip::_setObjCoeffs(ExprIterator b, ExprIterator e) {
+ int num = _prob->numberColumns();
+ for (int i = 0; i < num; ++i) {
+ _prob->setColumnObjective(i, 0.0);
+ }
+ for (ExprIterator it = b; it != e; ++it) {
+ _prob->setColumnObjective(it->first, it->second);
+ }
+ }
+
+ void CbcMip::_getObjCoeffs(InsertIterator b) const {
+ int num = _prob->numberColumns();
+ for (int i = 0; i < num; ++i) {
+ Value coef = _prob->getColumnObjective(i);
+ if (coef != 0.0) {
+ *b = std::make_pair(i, coef);
+ ++b;
+ }
+ }
+ }
+
+ void CbcMip::_setObjCoeff(int i, Value obj_coef) {
+ _prob->setColumnObjective(i, obj_coef);
+ }
+
+ CbcMip::Value CbcMip::_getObjCoeff(int i) const {
+ return _prob->getColumnObjective(i);
+ }
+
+ CbcMip::SolveExitStatus CbcMip::_solve() {
+
+ if (_osi_solver) {
+ delete _osi_solver;
+ }
+#ifdef COIN_HAS_CLP
+ _osi_solver = new OsiClpSolverInterface();
+#elif COIN_HAS_OSL
+ _osi_solver = new OsiOslSolverInterface();
+#else
+#error Cannot instantiate Osi solver
+#endif
+
+ _osi_solver->loadFromCoinModel(*_prob);
+
+ if (_cbc_model) {
+ delete _cbc_model;
+ }
+ _cbc_model= new CbcModel(*_osi_solver);
+
+ _osi_solver->messageHandler()->setLogLevel(_message_level);
+ _cbc_model->setLogLevel(_message_level);
+
+ _cbc_model->initialSolve();
+ _cbc_model->solver()->setHintParam(OsiDoReducePrint, true, OsiHintTry);
+
+ if (!_cbc_model->isInitialSolveAbandoned() &&
+ _cbc_model->isInitialSolveProvenOptimal() &&
+ !_cbc_model->isInitialSolveProvenPrimalInfeasible() &&
+ !_cbc_model->isInitialSolveProvenDualInfeasible()) {
+
+ CglProbing generator1;
+ generator1.setUsingObjective(true);
+ generator1.setMaxPass(3);
+ generator1.setMaxProbe(100);
+ generator1.setMaxLook(50);
+ generator1.setRowCuts(3);
+ _cbc_model->addCutGenerator(&generator1, -1, "Probing");
+
+ CglGomory generator2;
+ generator2.setLimit(300);
+ _cbc_model->addCutGenerator(&generator2, -1, "Gomory");
+
+ CglKnapsackCover generator3;
+ _cbc_model->addCutGenerator(&generator3, -1, "Knapsack");
+
+ CglOddHole generator4;
+ generator4.setMinimumViolation(0.005);
+ generator4.setMinimumViolationPer(0.00002);
+ generator4.setMaximumEntries(200);
+ _cbc_model->addCutGenerator(&generator4, -1, "OddHole");
+
+ CglClique generator5;
+ generator5.setStarCliqueReport(false);
+ generator5.setRowCliqueReport(false);
+ _cbc_model->addCutGenerator(&generator5, -1, "Clique");
+
+ CglMixedIntegerRounding mixedGen;
+ _cbc_model->addCutGenerator(&mixedGen, -1, "MixedIntegerRounding");
+
+ CglFlowCover flowGen;
+ _cbc_model->addCutGenerator(&flowGen, -1, "FlowCover");
+
+#ifdef COIN_HAS_CLP
+ OsiClpSolverInterface* osiclp =
+ dynamic_cast(_cbc_model->solver());
+ if (osiclp->getNumRows() < 300 && osiclp->getNumCols() < 500) {
+ osiclp->setupForRepeatedUse(2, 0);
+ }
+#endif
+
+ CbcRounding heuristic1(*_cbc_model);
+ heuristic1.setWhen(3);
+ _cbc_model->addHeuristic(&heuristic1);
+
+ CbcHeuristicLocal heuristic2(*_cbc_model);
+ heuristic2.setWhen(3);
+ _cbc_model->addHeuristic(&heuristic2);
+
+ CbcHeuristicGreedyCover heuristic3(*_cbc_model);
+ heuristic3.setAlgorithm(11);
+ heuristic3.setWhen(3);
+ _cbc_model->addHeuristic(&heuristic3);
+
+ CbcHeuristicFPump heuristic4(*_cbc_model);
+ heuristic4.setWhen(3);
+ _cbc_model->addHeuristic(&heuristic4);
+
+ CbcHeuristicRINS heuristic5(*_cbc_model);
+ heuristic5.setWhen(3);
+ _cbc_model->addHeuristic(&heuristic5);
+
+ if (_cbc_model->getNumCols() < 500) {
+ _cbc_model->setMaximumCutPassesAtRoot(-100);
+ } else if (_cbc_model->getNumCols() < 5000) {
+ _cbc_model->setMaximumCutPassesAtRoot(100);
+ } else {
+ _cbc_model->setMaximumCutPassesAtRoot(20);
+ }
+
+ if (_cbc_model->getNumCols() < 5000) {
+ _cbc_model->setNumberStrong(10);
+ }
+
+ _cbc_model->solver()->setIntParam(OsiMaxNumIterationHotStart, 100);
+ _cbc_model->branchAndBound();
+ }
+
+ if (_cbc_model->isAbandoned()) {
+ return UNSOLVED;
+ } else {
+ return SOLVED;
+ }
+ }
+
+ CbcMip::Value CbcMip::_getSol(int i) const {
+ return _cbc_model->getColSolution()[i];
+ }
+
+ CbcMip::Value CbcMip::_getSolValue() const {
+ return _cbc_model->getObjValue();
+ }
+
+ CbcMip::ProblemType CbcMip::_getType() const {
+ if (_cbc_model->isProvenOptimal()) {
+ return OPTIMAL;
+ } else if (_cbc_model->isContinuousUnbounded()) {
+ return UNBOUNDED;
+ }
+ return FEASIBLE;
+ }
+
+ void CbcMip::_setSense(Sense sense) {
+ switch (sense) {
+ case MIN:
+ _prob->setOptimizationDirection(1.0);
+ break;
+ case MAX:
+ _prob->setOptimizationDirection(- 1.0);
+ break;
+ }
+ }
+
+ CbcMip::Sense CbcMip::_getSense() const {
+ if (_prob->optimizationDirection() > 0.0) {
+ return MIN;
+ } else if (_prob->optimizationDirection() < 0.0) {
+ return MAX;
+ } else {
+ LEMON_ASSERT(false, "Wrong sense");
+ return CbcMip::Sense();
+ }
+ }
+
+ void CbcMip::_setColType(int i, CbcMip::ColTypes col_type) {
+ switch (col_type){
+ case INTEGER:
+ _prob->setInteger(i);
+ break;
+ case REAL:
+ _prob->setContinuous(i);
+ break;
+ default:;
+ LEMON_ASSERT(false, "Wrong sense");
+ }
+ }
+
+ CbcMip::ColTypes CbcMip::_getColType(int i) const {
+ return _prob->getColumnIsInteger(i) ? INTEGER : REAL;
+ }
+
+ void CbcMip::_clear() {
+ delete _prob;
+ if (_osi_solver) {
+ delete _osi_solver;
+ _osi_solver = 0;
+ }
+ if (_cbc_model) {
+ delete _cbc_model;
+ _cbc_model = 0;
+ }
+
+ _prob = new CoinModel();
+ rows.clear();
+ cols.clear();
+ }
+
+ void CbcMip::_messageLevel(MessageLevel level) {
+ switch (level) {
+ case MESSAGE_NOTHING:
+ _message_level = 0;
+ break;
+ case MESSAGE_ERROR:
+ _message_level = 1;
+ break;
+ case MESSAGE_WARNING:
+ _message_level = 1;
+ break;
+ case MESSAGE_NORMAL:
+ _message_level = 2;
+ break;
+ case MESSAGE_VERBOSE:
+ _message_level = 3;
+ break;
+ }
+ }
+
+} //END OF NAMESPACE LEMON
Index: lemon/cbc.h
===================================================================
--- lemon/cbc.h (revision 576)
+++ lemon/cbc.h (revision 576)
@@ -0,0 +1,129 @@
+/* -*- 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.
+ *
+ */
+
+// -*- C++ -*-
+#ifndef LEMON_CBC_H
+#define LEMON_CBC_H
+
+///\file
+///\brief Header of the LEMON-CBC mip solver interface.
+///\ingroup lp_group
+
+#include
+
+class CoinModel;
+class OsiSolverInterface;
+class CbcModel;
+
+namespace lemon {
+
+ /// \brief Interface for the CBC MIP solver
+ ///
+ /// This class implements an interface for the CBC MIP solver.
+ ///\ingroup lp_group
+ class CbcMip : public MipSolver {
+ protected:
+
+ CoinModel *_prob;
+ OsiSolverInterface *_osi_solver;
+ CbcModel *_cbc_model;
+
+ public:
+
+ /// \e
+ CbcMip();
+ /// \e
+ CbcMip(const CbcMip&);
+ /// \e
+ ~CbcMip();
+ /// \e
+ virtual CbcMip* newSolver() const;
+ /// \e
+ virtual CbcMip* cloneSolver() const;
+
+ protected:
+
+ virtual const char* _solverName() const;
+
+ virtual int _addCol();
+ virtual int _addRow();
+
+ virtual void _eraseCol(int i);
+ virtual void _eraseRow(int i);
+
+ virtual void _eraseColId(int i);
+ virtual void _eraseRowId(int i);
+
+ virtual void _getColName(int col, std::string& name) const;
+ virtual void _setColName(int col, const std::string& name);
+ virtual int _colByName(const std::string& name) const;
+
+ virtual void _getRowName(int row, std::string& name) const;
+ virtual void _setRowName(int row, const std::string& name);
+ virtual int _rowByName(const std::string& name) const;
+
+ virtual void _setRowCoeffs(int i, ExprIterator b, ExprIterator e);
+ virtual void _getRowCoeffs(int i, InsertIterator b) const;
+
+ virtual void _setColCoeffs(int i, ExprIterator b, ExprIterator e);
+ virtual void _getColCoeffs(int i, InsertIterator b) const;
+
+ virtual void _setCoeff(int row, int col, Value value);
+ virtual Value _getCoeff(int row, int col) const;
+
+ virtual void _setColLowerBound(int i, Value value);
+ virtual Value _getColLowerBound(int i) const;
+ virtual void _setColUpperBound(int i, Value value);
+ virtual Value _getColUpperBound(int i) const;
+
+ virtual void _setRowLowerBound(int i, Value value);
+ virtual Value _getRowLowerBound(int i) const;
+ virtual void _setRowUpperBound(int i, Value value);
+ virtual Value _getRowUpperBound(int i) const;
+
+ virtual void _setObjCoeffs(ExprIterator b, ExprIterator e);
+ virtual void _getObjCoeffs(InsertIterator b) const;
+
+ virtual void _setObjCoeff(int i, Value obj_coef);
+ virtual Value _getObjCoeff(int i) const;
+
+ virtual void _setSense(Sense sense);
+ virtual Sense _getSense() const;
+
+ virtual ColTypes _getColType(int col) const;
+ virtual void _setColType(int col, ColTypes col_type);
+
+ virtual SolveExitStatus _solve();
+ virtual ProblemType _getType() const;
+ virtual Value _getSol(int i) const;
+ virtual Value _getSolValue() const;
+
+ virtual void _clear();
+
+ virtual void _messageLevel(MessageLevel level);
+ void _applyMessageLevel();
+
+ int _message_level;
+
+
+
+ };
+
+}
+
+#endif
Index: lemon/circulation.h
===================================================================
--- lemon/circulation.h (revision 610)
+++ lemon/circulation.h (revision 611)
@@ -231,7 +231,7 @@
///@{
- template
+ template
struct SetFlowMapTraits : public Traits {
- typedef _FlowMap FlowMap;
+ typedef T FlowMap;
static FlowMap *createFlowMap(const Digraph&) {
LEMON_ASSERT(false, "FlowMap is not initialized");
@@ -245,15 +245,15 @@
/// \ref named-templ-param "Named parameter" for setting FlowMap
/// type.
- template
+ template
struct SetFlowMap
: public Circulation > {
+ SetFlowMapTraits > {
typedef Circulation > Create;
+ SetFlowMapTraits > Create;
};
- template
+ template
struct SetElevatorTraits : public Traits {
- typedef _Elevator Elevator;
+ typedef T Elevator;
static Elevator *createElevator(const Digraph&, int) {
LEMON_ASSERT(false, "Elevator is not initialized");
@@ -271,15 +271,15 @@
/// \ref run() or \ref init().
/// \sa SetStandardElevator
- template
+ template
struct SetElevator
: public Circulation > {
+ SetElevatorTraits > {
typedef Circulation > Create;
+ SetElevatorTraits > Create;
};
- template
+ template
struct SetStandardElevatorTraits : public Traits {
- typedef _Elevator Elevator;
+ typedef T Elevator;
static Elevator *createElevator(const Digraph& digraph, int max_level) {
return new Elevator(digraph, max_level);
@@ -299,10 +299,10 @@
/// before calling \ref run() or \ref init().
/// \sa SetElevator
- template
+ template
struct SetStandardElevator
: public Circulation > {
+ SetStandardElevatorTraits > {
typedef Circulation > Create;
+ SetStandardElevatorTraits > Create;
};
@@ -471,11 +471,11 @@
for(NodeIt n(_g);n!=INVALID;++n) {
- _excess->set(n, (*_supply)[n]);
+ (*_excess)[n] = (*_supply)[n];
}
for (ArcIt e(_g);e!=INVALID;++e) {
_flow->set(e, (*_lo)[e]);
- _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_flow)[e]);
- _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_flow)[e]);
+ (*_excess)[_g.target(e)] += (*_flow)[e];
+ (*_excess)[_g.source(e)] -= (*_flow)[e];
}
@@ -500,5 +500,5 @@
for(NodeIt n(_g);n!=INVALID;++n) {
- _excess->set(n, (*_supply)[n]);
+ (*_excess)[n] = (*_supply)[n];
}
@@ -506,15 +506,15 @@
if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) {
_flow->set(e, (*_up)[e]);
- _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_up)[e]);
- _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_up)[e]);
+ (*_excess)[_g.target(e)] += (*_up)[e];
+ (*_excess)[_g.source(e)] -= (*_up)[e];
} else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) {
_flow->set(e, (*_lo)[e]);
- _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_lo)[e]);
- _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_lo)[e]);
+ (*_excess)[_g.target(e)] += (*_lo)[e];
+ (*_excess)[_g.source(e)] -= (*_lo)[e];
} else {
Flow fc = -(*_excess)[_g.target(e)];
_flow->set(e, fc);
- _excess->set(_g.target(e), 0);
- _excess->set(_g.source(e), (*_excess)[_g.source(e)] - fc);
+ (*_excess)[_g.target(e)] = 0;
+ (*_excess)[_g.source(e)] -= fc;
}
}
@@ -555,8 +555,8 @@
if(!_tol.less(fc, exc)) {
_flow->set(e, (*_flow)[e] + exc);
- _excess->set(v, (*_excess)[v] + exc);
+ (*_excess)[v] += exc;
if(!_level->active(v) && _tol.positive((*_excess)[v]))
_level->activate(v);
- _excess->set(act,0);
+ (*_excess)[act] = 0;
_level->deactivate(act);
goto next_l;
@@ -564,5 +564,5 @@
else {
_flow->set(e, (*_up)[e]);
- _excess->set(v, (*_excess)[v] + fc);
+ (*_excess)[v] += fc;
if(!_level->active(v) && _tol.positive((*_excess)[v]))
_level->activate(v);
@@ -579,8 +579,8 @@
if(!_tol.less(fc, exc)) {
_flow->set(e, (*_flow)[e] - exc);
- _excess->set(v, (*_excess)[v] + exc);
+ (*_excess)[v] += exc;
if(!_level->active(v) && _tol.positive((*_excess)[v]))
_level->activate(v);
- _excess->set(act,0);
+ (*_excess)[act] = 0;
_level->deactivate(act);
goto next_l;
@@ -588,5 +588,5 @@
else {
_flow->set(e, (*_lo)[e]);
- _excess->set(v, (*_excess)[v] + fc);
+ (*_excess)[v] += fc;
if(!_level->active(v) && _tol.positive((*_excess)[v]))
_level->activate(v);
@@ -597,5 +597,5 @@
}
- _excess->set(act, exc);
+ (*_excess)[act] = exc;
if(!_tol.positive(exc)) _level->deactivate(act);
else if(mlevel==_node_num) {
@@ -700,5 +700,5 @@
///
/// \note This function calls \ref barrier() for each node,
- /// so it runs in \f$O(n)\f$ time.
+ /// so it runs in O(n) time.
///
/// \pre Either \ref run() or \ref init() must be called before
Index: lemon/clp.cc
===================================================================
--- lemon/clp.cc (revision 462)
+++ lemon/clp.cc (revision 576)
@@ -25,5 +25,5 @@
_prob = new ClpSimplex();
_init_temporals();
- messageLevel(MESSAGE_NO_OUTPUT);
+ messageLevel(MESSAGE_NOTHING);
}
@@ -33,5 +33,5 @@
cols = other.cols;
_init_temporals();
- messageLevel(MESSAGE_NO_OUTPUT);
+ messageLevel(MESSAGE_NOTHING);
}
@@ -57,10 +57,10 @@
}
- ClpLp* ClpLp::_newSolver() const {
+ ClpLp* ClpLp::newSolver() const {
ClpLp* newlp = new ClpLp;
return newlp;
}
- ClpLp* ClpLp::_cloneSolver() const {
+ ClpLp* ClpLp::cloneSolver() const {
ClpLp* copylp = new ClpLp(*this);
return copylp;
@@ -431,6 +431,22 @@
}
- void ClpLp::messageLevel(MessageLevel m) {
- _prob->setLogLevel(static_cast(m));
+ void ClpLp::_messageLevel(MessageLevel level) {
+ switch (level) {
+ case MESSAGE_NOTHING:
+ _prob->setLogLevel(0);
+ break;
+ case MESSAGE_ERROR:
+ _prob->setLogLevel(1);
+ break;
+ case MESSAGE_WARNING:
+ _prob->setLogLevel(2);
+ break;
+ case MESSAGE_NORMAL:
+ _prob->setLogLevel(3);
+ break;
+ case MESSAGE_VERBOSE:
+ _prob->setLogLevel(4);
+ break;
+ }
}
Index: lemon/clp.h
===================================================================
--- lemon/clp.h (revision 462)
+++ lemon/clp.h (revision 576)
@@ -57,4 +57,9 @@
~ClpLp();
+ /// \e
+ virtual ClpLp* newSolver() const;
+ /// \e
+ virtual ClpLp* cloneSolver() const;
+
protected:
@@ -66,7 +71,4 @@
protected:
-
- virtual ClpLp* _newSolver() const;
- virtual ClpLp* _cloneSolver() const;
virtual const char* _solverName() const;
@@ -135,4 +137,6 @@
virtual void _clear();
+ virtual void _messageLevel(MessageLevel);
+
public:
@@ -152,24 +156,4 @@
int clpCol(Col c) const { return cols(id(c)); }
- ///Enum for \c messageLevel() parameter
- enum MessageLevel {
- /// no output (default value)
- MESSAGE_NO_OUTPUT = 0,
- /// print final solution
- MESSAGE_FINAL_SOLUTION = 1,
- /// print factorization
- MESSAGE_FACTORIZATION = 2,
- /// normal output
- MESSAGE_NORMAL_OUTPUT = 3,
- /// verbose output
- MESSAGE_VERBOSE_OUTPUT = 4
- };
- ///Set the verbosity of the messages
-
- ///Set the verbosity of the messages
- ///
- ///\param m is the level of the messages output by the solver routines.
- void messageLevel(MessageLevel m);
-
};
Index: lemon/concepts/digraph.h
===================================================================
--- lemon/concepts/digraph.h (revision 529)
+++ lemon/concepts/digraph.h (revision 580)
@@ -422,10 +422,9 @@
Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
- /// \brief Read write map of the nodes to type \c T.
- ///
- /// ReadWrite map of the nodes to type \c T.
- /// \sa Reference
+ /// \brief Reference map of the nodes to type \c T.
+ ///
+ /// Reference map of the nodes to type \c T.
template
- class NodeMap : public ReadWriteMap< Node, T > {
+ class NodeMap : public ReferenceMap {
public:
@@ -437,5 +436,6 @@
private:
///Copy constructor
- NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
+ NodeMap(const NodeMap& nm) :
+ ReferenceMap(nm) { }
///Assignment operator
template
@@ -446,10 +446,9 @@
};
- /// \brief Read write map of the arcs to type \c T.
+ /// \brief Reference map of the arcs to type \c T.
///
/// Reference map of the arcs to type \c T.
- /// \sa Reference
template
- class ArcMap : public ReadWriteMap {
+ class ArcMap : public ReferenceMap {
public:
@@ -460,5 +459,6 @@
private:
///Copy constructor
- ArcMap(const ArcMap& em) : ReadWriteMap(em) { }
+ ArcMap(const ArcMap& em) :
+ ReferenceMap(em) { }
///Assignment operator
template
@@ -472,4 +472,5 @@
struct Constraints {
void constraints() {
+ checkConcept();
checkConcept, _Digraph>();
checkConcept, _Digraph>();
Index: lemon/concepts/graph.h
===================================================================
--- lemon/concepts/graph.h (revision 529)
+++ lemon/concepts/graph.h (revision 580)
@@ -498,10 +498,9 @@
};
- /// \brief Read write map of the nodes to type \c T.
- ///
- /// ReadWrite map of the nodes to type \c T.
- /// \sa Reference
+ /// \brief Reference map of the nodes to type \c T.
+ ///
+ /// Reference map of the nodes to type \c T.
template
- class NodeMap : public ReadWriteMap< Node, T >
+ class NodeMap : public ReferenceMap
{
public:
@@ -514,5 +513,6 @@
private:
///Copy constructor
- NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
+ NodeMap(const NodeMap& nm) :
+ ReferenceMap(nm) { }
///Assignment operator
template
@@ -523,10 +523,9 @@
};
- /// \brief Read write map of the directed arcs to type \c T.
- ///
- /// Reference map of the directed arcs to type \c T.
- /// \sa Reference
+ /// \brief Reference map of the arcs to type \c T.
+ ///
+ /// Reference map of the arcs to type \c T.
template
- class ArcMap : public ReadWriteMap
+ class ArcMap : public ReferenceMap
{
public:
@@ -538,5 +537,6 @@
private:
///Copy constructor
- ArcMap(const ArcMap& em) : ReadWriteMap(em) { }
+ ArcMap(const ArcMap& em) :
+ ReferenceMap(em) { }
///Assignment operator
template
@@ -547,10 +547,9 @@
};
- /// Read write map of the edges to type \c T.
-
- /// Reference map of the arcs to type \c T.
- /// \sa Reference
+ /// Reference map of the edges to type \c T.
+
+ /// Reference map of the edges to type \c T.
template
- class EdgeMap : public ReadWriteMap
+ class EdgeMap : public ReferenceMap
{
public:
@@ -562,5 +561,6 @@
private:
///Copy constructor
- EdgeMap(const EdgeMap& em) : ReadWriteMap(em) {}
+ EdgeMap(const EdgeMap& em) :
+ ReferenceMap(em) {}
///Assignment operator
template
@@ -602,21 +602,33 @@
/// \brief Opposite node on an arc
///
- /// \return the opposite of the given Node on the given Edge
+ /// \return The opposite of the given node on the given edge.
Node oppositeNode(Node, Edge) const { return INVALID; }
/// \brief First node of the edge.
///
- /// \return the first node of the given Edge.
+ /// \return The first node of the given edge.
///
/// Naturally edges don't have direction and thus
- /// don't have source and target node. But we use these two methods
- /// to query the two nodes of the arc. The direction of the arc
- /// which arises this way is called the inherent direction of the
+ /// don't have source and target node. However we use \c u() and \c v()
+ /// methods to query the two nodes of the arc. The direction of the
+ /// arc which arises this way is called the inherent direction of the
/// edge, and is used to define the "default" direction
/// of the directed versions of the arcs.
- /// \sa direction
+ /// \sa v()
+ /// \sa direction()
Node u(Edge) const { return INVALID; }
/// \brief Second node of the edge.
+ ///
+ /// \return The second node of the given edge.
+ ///
+ /// Naturally edges don't have direction and thus
+ /// don't have source and target node. However we use \c u() and \c v()
+ /// methods to query the two nodes of the arc. The direction of the
+ /// arc which arises this way is called the inherent direction of the
+ /// edge, and is used to define the "default" direction
+ /// of the directed versions of the arcs.
+ /// \sa u()
+ /// \sa direction()
Node v(Edge) const { return INVALID; }
@@ -737,4 +749,5 @@
struct Constraints {
void constraints() {
+ checkConcept();
checkConcept, _Graph>();
checkConcept, _Graph>();
Index: lemon/concepts/graph_components.h
===================================================================
--- lemon/concepts/graph_components.h (revision 534)
+++ lemon/concepts/graph_components.h (revision 584)
@@ -21,5 +21,4 @@
///\brief The concept of graph components.
-
#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
#define LEMON_CONCEPTS_GRAPH_COMPONENTS_H
@@ -33,17 +32,16 @@
namespace concepts {
- /// \brief Skeleton class for graph Node and Arc types
- ///
- /// This class describes the interface of Node and Arc (and Edge
- /// in undirected graphs) subtypes of graph types.
+ /// \brief Concept class for \c Node, \c Arc and \c Edge types.
+ ///
+ /// This class describes the concept of \c Node, \c Arc and \c Edge
+ /// subtypes of digraph and graph types.
///
/// \note This class is a template class so that we can use it to
- /// create graph skeleton classes. The reason for this is than Node
- /// and Arc types should \em not derive from the same base class.
- /// For Node you should instantiate it with character 'n' and for Arc
- /// with 'a'.
-
+ /// create graph skeleton classes. The reason for this is that \c Node
+ /// and \c Arc (or \c Edge) types should \e not derive from the same
+ /// base class. For \c Node you should instantiate it with character
+ /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'.
#ifndef DOXYGEN
- template
+ template
#endif
class GraphItem {
@@ -51,43 +49,47 @@
/// \brief Default constructor.
///
+ /// Default constructor.
/// \warning The default constructor is not required to set
/// the item to some well-defined value. So you should consider it
/// as uninitialized.
GraphItem() {}
+
/// \brief Copy constructor.
///
/// Copy constructor.
- ///
GraphItem(const GraphItem &) {}
- /// \brief Invalid constructor \& conversion.
- ///
- /// This constructor initializes the item to be invalid.
+
+ /// \brief Constructor for conversion from \c INVALID.
+ ///
+ /// Constructor for conversion from \c INVALID.
+ /// It initializes the item to be invalid.
/// \sa Invalid for more details.
GraphItem(Invalid) {}
- /// \brief Assign operator for nodes.
- ///
- /// The nodes are assignable.
- ///
- GraphItem& operator=(GraphItem const&) { return *this; }
+
+ /// \brief Assignment operator.
+ ///
+ /// Assignment operator for the item.
+ GraphItem& operator=(const GraphItem&) { return *this; }
+
/// \brief Equality operator.
///
- /// Two iterators are equal if and only if they represents the
- /// same node in the graph or both are invalid.
- bool operator==(GraphItem) const { return false; }
+ /// Equality operator.
+ bool operator==(const GraphItem&) const { return false; }
+
/// \brief Inequality operator.
///
- /// \sa operator==(const Node& n)
- ///
- bool operator!=(GraphItem) const { return false; }
-
- /// \brief Artificial ordering operator.
- ///
- /// To allow the use of graph descriptors as key type in std::map or
- /// similar associative container we require this.
+ /// Inequality operator.
+ bool operator!=(const GraphItem&) const { return false; }
+
+ /// \brief Ordering operator.
+ ///
+ /// This operator defines an ordering of the items.
+ /// It makes possible to use graph item types as key types in
+ /// associative containers (e.g. \c std::map).
///
/// \note This operator only have to define some strict ordering of
/// the items; this order has nothing to do with the iteration
/// ordering of the items.
- bool operator<(GraphItem) const { return false; }
+ bool operator<(const GraphItem&) const { return false; }
template
@@ -101,5 +103,4 @@
bool b;
- // b = (ia == ib) && (ia != ib) && (ia < ib);
b = (ia == ib) && (ia != ib);
b = (ia == INVALID) && (ib != INVALID);
@@ -112,11 +113,10 @@
};
- /// \brief An empty base directed graph class.
- ///
- /// This class provides the minimal set of features needed for a
- /// directed graph structure. All digraph concepts have to
- /// conform to this base directed graph. It just provides types
- /// for nodes and arcs and functions to get the source and the
- /// target of the arcs.
+ /// \brief Base skeleton class for directed graphs.
+ ///
+ /// This class describes the base interface of directed graph types.
+ /// All digraph %concepts have to conform to this class.
+ /// It just provides types for nodes and arcs and functions
+ /// to get the source and the target nodes of arcs.
class BaseDigraphComponent {
public:
@@ -126,29 +126,25 @@
/// \brief Node class of the digraph.
///
- /// This class represents the Nodes of the digraph.
- ///
+ /// This class represents the nodes of the digraph.
typedef GraphItem<'n'> Node;
/// \brief Arc class of the digraph.
///
- /// This class represents the Arcs of the digraph.
- ///
- typedef GraphItem<'e'> Arc;
-
- /// \brief Gives back the target node of an arc.
- ///
- /// Gives back the target node of an arc.
- ///
- Node target(const Arc&) const { return INVALID;}
-
- /// \brief Gives back the source node of an arc.
- ///
- /// Gives back the source node of an arc.
- ///
- Node source(const Arc&) const { return INVALID;}
-
- /// \brief Gives back the opposite node on the given arc.
- ///
- /// Gives back the opposite node on the given arc.
+ /// This class represents the arcs of the digraph.
+ typedef GraphItem<'a'> Arc;
+
+ /// \brief Return the source node of an arc.
+ ///
+ /// This function returns the source node of an arc.
+ Node source(const Arc&) const { return INVALID; }
+
+ /// \brief Return the target node of an arc.
+ ///
+ /// This function returns the target node of an arc.
+ Node target(const Arc&) const { return INVALID; }
+
+ /// \brief Return the opposite node on the given arc.
+ ///
+ /// This function returns the opposite node on the given arc.
Node oppositeNode(const Node&, const Arc&) const {
return INVALID;
@@ -176,50 +172,55 @@
};
- /// \brief An empty base undirected graph class.
- ///
- /// This class provides the minimal set of features needed for an
- /// undirected graph structure. All undirected graph concepts have
- /// to conform to this base graph. It just provides types for
- /// nodes, arcs and edges and functions to get the
- /// source and the target of the arcs and edges,
- /// conversion from arcs to edges and function to get
- /// both direction of the edges.
+ /// \brief Base skeleton class for undirected graphs.
+ ///
+ /// This class describes the base interface of undirected graph types.
+ /// All graph %concepts have to conform to this class.
+ /// It extends the interface of \ref BaseDigraphComponent with an
+ /// \c Edge type and functions to get the end nodes of edges,
+ /// to convert from arcs to edges and to get both direction of edges.
class BaseGraphComponent : public BaseDigraphComponent {
public:
typedef BaseDigraphComponent::Node Node;
typedef BaseDigraphComponent::Arc Arc;
- /// \brief Undirected arc class of the graph.
- ///
- /// This class represents the edges of the graph.
- /// The undirected graphs can be used as a directed graph which
- /// for each arc contains the opposite arc too so the graph is
- /// bidirected. The edge represents two opposite
- /// directed arcs.
- class Edge : public GraphItem<'u'> {
+
+ /// \brief Undirected edge class of the graph.
+ ///
+ /// This class represents the undirected edges of the graph.
+ /// Undirected graphs can be used as directed graphs, each edge is
+ /// represented by two opposite directed arcs.
+ class Edge : public GraphItem<'e'> {
public:
- typedef GraphItem<'u'> Parent;
+ typedef GraphItem<'e'> Parent;
+
/// \brief Default constructor.
///
+ /// Default constructor.
/// \warning The default constructor is not required to set
/// the item to some well-defined value. So you should consider it
/// as uninitialized.
Edge() {}
+
/// \brief Copy constructor.
///
/// Copy constructor.
- ///
Edge(const Edge &) : Parent() {}
- /// \brief Invalid constructor \& conversion.
- ///
- /// This constructor initializes the item to be invalid.
+
+ /// \brief Constructor for conversion from \c INVALID.
+ ///
+ /// Constructor for conversion from \c INVALID.
+ /// It initializes the item to be invalid.
/// \sa Invalid for more details.
Edge(Invalid) {}
- /// \brief Converter from arc to edge.
- ///
+
+ /// \brief Constructor for conversion from an arc.
+ ///
+ /// Constructor for conversion from an arc.
/// Besides the core graph item functionality each arc should
/// be convertible to the represented edge.
Edge(const Arc&) {}
- /// \brief Assign arc to edge.
- ///
+
+ /// \brief Assign an arc to an edge.
+ ///
+ /// This function assigns an arc to an edge.
/// Besides the core graph item functionality each arc should
/// be convertible to the represented edge.
@@ -227,5 +228,27 @@
};
- /// \brief Returns the direction of the arc.
+ /// \brief Return one end node of an edge.
+ ///
+ /// This function returns one end node of an edge.
+ Node u(const Edge&) const { return INVALID; }
+
+ /// \brief Return the other end node of an edge.
+ ///
+ /// This function returns the other end node of an edge.
+ Node v(const Edge&) const { return INVALID; }
+
+ /// \brief Return a directed arc related to an edge.
+ ///
+ /// This function returns a directed arc from its direction and the
+ /// represented edge.
+ Arc direct(const Edge&, bool) const { return INVALID; }
+
+ /// \brief Return a directed arc related to an edge.
+ ///
+ /// This function returns a directed arc from its source node and the
+ /// represented edge.
+ Arc direct(const Edge&, const Node&) const { return INVALID; }
+
+ /// \brief Return the direction of the arc.
///
/// Returns the direction of the arc. Each arc represents an
@@ -234,31 +257,9 @@
bool direction(const Arc&) const { return true; }
- /// \brief Returns the directed arc.
- ///
- /// Returns the directed arc from its direction and the
- /// represented edge.
- Arc direct(const Edge&, bool) const { return INVALID;}
-
- /// \brief Returns the directed arc.
- ///
- /// Returns the directed arc from its source and the
- /// represented edge.
- Arc direct(const Edge&, const Node&) const { return INVALID;}
-
- /// \brief Returns the opposite arc.
- ///
- /// Returns the opposite arc. It is the arc representing the
- /// same edge and has opposite direction.
- Arc oppositeArc(const Arc&) const { return INVALID;}
-
- /// \brief Gives back one ending of an edge.
- ///
- /// Gives back one ending of an edge.
- Node u(const Edge&) const { return INVALID;}
-
- /// \brief Gives back the other ending of an edge.
- ///
- /// Gives back the other ending of an edge.
- Node v(const Edge&) const { return INVALID;}
+ /// \brief Return the opposite arc.
+ ///
+ /// This function returns the opposite arc, i.e. the arc representing
+ /// the same edge and has opposite direction.
+ Arc oppositeArc(const Arc&) const { return INVALID; }
template
@@ -270,5 +271,5 @@
void constraints() {
checkConcept();
- checkConcept, Edge>();
+ checkConcept, Edge>();
{
Node n;
@@ -278,4 +279,5 @@
n = graph.v(ue);
e = graph.direct(ue, true);
+ e = graph.direct(ue, false);
e = graph.direct(ue, n);
e = graph.oppositeArc(e);
@@ -291,57 +293,55 @@
};
- /// \brief An empty idable base digraph class.
- ///
- /// This class provides beside the core digraph features
- /// core id functions for the digraph structure.
- /// The most of the base digraphs should conform to this concept.
- /// The id's are unique and immutable.
- template
- class IDableDigraphComponent : public _Base {
- public:
-
- typedef _Base Base;
+ /// \brief Skeleton class for \e idable directed graphs.
+ ///
+ /// This class describes the interface of \e idable directed graphs.
+ /// It extends \ref BaseDigraphComponent with the core ID functions.
+ /// The ids of the items must be unique and immutable.
+ /// This concept is part of the Digraph concept.
+ template
+ class IDableDigraphComponent : public BAS {
+ public:
+
+ typedef BAS Base;
typedef typename Base::Node Node;
typedef typename Base::Arc Arc;
- /// \brief Gives back an unique integer id for the Node.
- ///
- /// Gives back an unique integer id for the Node.
- ///
- int id(const Node&) const { return -1;}
-
- /// \brief Gives back the node by the unique id.
- ///
- /// Gives back the node by the unique id.
- /// If the digraph does not contain node with the given id
- /// then the result of the function is undetermined.
- Node nodeFromId(int) const { return INVALID;}
-
- /// \brief Gives back an unique integer id for the Arc.
- ///
- /// Gives back an unique integer id for the Arc.
- ///
- int id(const Arc&) const { return -1;}
-
- /// \brief Gives back the arc by the unique id.
- ///
- /// Gives back the arc by the unique id.
- /// If the digraph does not contain arc with the given id
- /// then the result of the function is undetermined.
- Arc arcFromId(int) const { return INVALID;}
-
- /// \brief Gives back an integer greater or equal to the maximum
- /// Node id.
- ///
- /// Gives back an integer greater or equal to the maximum Node
- /// id.
- int maxNodeId() const { return -1;}
-
- /// \brief Gives back an integer greater or equal to the maximum
- /// Arc id.
- ///
- /// Gives back an integer greater or equal to the maximum Arc
- /// id.
- int maxArcId() const { return -1;}
+ /// \brief Return a unique integer id for the given node.
+ ///
+ /// This function returns a unique integer id for the given node.
+ int id(const Node&) const { return -1; }
+
+ /// \brief Return the node by its unique id.
+ ///
+ /// This function returns the node by its unique id.
+ /// If the digraph does not contain a node with the given id,
+ /// then the result of the function is undefined.
+ Node nodeFromId(int) const { return INVALID; }
+
+ /// \brief Return a unique integer id for the given arc.
+ ///
+ /// This function returns a unique integer id for the given arc.
+ int id(const Arc&) const { return -1; }
+
+ /// \brief Return the arc by its unique id.
+ ///
+ /// This function returns the arc by its unique id.
+ /// If the digraph does not contain an arc with the given id,
+ /// then the result of the function is undefined.
+ Arc arcFromId(int) const { return INVALID; }
+
+ /// \brief Return an integer greater or equal to the maximum
+ /// node id.
+ ///
+ /// This function returns an integer greater or equal to the
+ /// maximum node id.
+ int maxNodeId() const { return -1; }
+
+ /// \brief Return an integer greater or equal to the maximum
+ /// arc id.
+ ///
+ /// This function returns an integer greater or equal to the
+ /// maximum arc id.
+ int maxArcId() const { return -1; }
template
@@ -369,38 +369,38 @@
};
- /// \brief An empty idable base undirected graph class.
- ///
- /// This class provides beside the core undirected graph features
- /// core id functions for the undirected graph structure. The
- /// most of the base undirected graphs should conform to this
- /// concept. The id's are unique and immutable.
- template
- class IDableGraphComponent : public IDableDigraphComponent<_Base> {
- public:
-
- typedef _Base Base;
+ /// \brief Skeleton class for \e idable undirected graphs.
+ ///
+ /// This class describes the interface of \e idable undirected
+ /// graphs. It extends \ref IDableDigraphComponent with the core ID
+ /// functions of undirected graphs.
+ /// The ids of the items must be unique and immutable.
+ /// This concept is part of the Graph concept.
+ template
+ class IDableGraphComponent : public IDableDigraphComponent {
+ public:
+
+ typedef BAS Base;
typedef typename Base::Edge Edge;
- using IDableDigraphComponent<_Base>::id;
-
- /// \brief Gives back an unique integer id for the Edge.
- ///
- /// Gives back an unique integer id for the Edge.
- ///
- int id(const Edge&) const { return -1;}
-
- /// \brief Gives back the edge by the unique id.
- ///
- /// Gives back the edge by the unique id. If the
- /// graph does not contain arc with the given id then the
- /// result of the function is undetermined.
- Edge edgeFromId(int) const { return INVALID;}
-
- /// \brief Gives back an integer greater or equal to the maximum
- /// Edge id.
- ///
- /// Gives back an integer greater or equal to the maximum Edge
- /// id.
- int maxEdgeId() const { return -1;}
+ using IDableDigraphComponent::id;
+
+ /// \brief Return a unique integer id for the given edge.
+ ///
+ /// This function returns a unique integer id for the given edge.
+ int id(const Edge&) const { return -1; }
+
+ /// \brief Return the edge by its unique id.
+ ///
+ /// This function returns the edge by its unique id.
+ /// If the graph does not contain an edge with the given id,
+ /// then the result of the function is undefined.
+ Edge edgeFromId(int) const { return INVALID; }
+
+ /// \brief Return an integer greater or equal to the maximum
+ /// edge id.
+ ///
+ /// This function returns an integer greater or equal to the
+ /// maximum edge id.
+ int maxEdgeId() const { return -1; }
template
@@ -408,5 +408,4 @@
void constraints() {
- checkConcept();
checkConcept, _Graph >();
typename _Graph::Edge edge;
@@ -422,50 +421,59 @@
};
- /// \brief Skeleton class for graph NodeIt and ArcIt
- ///
- /// Skeleton class for graph NodeIt and ArcIt.
- ///
- template
- class GraphItemIt : public _Item {
+ /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
+ ///
+ /// This class describes the concept of \c NodeIt, \c ArcIt and
+ /// \c EdgeIt subtypes of digraph and graph types.
+ template
+ class GraphItemIt : public Item {
public:
/// \brief Default constructor.
///
- /// @warning The default constructor sets the iterator
- /// to an undefined value.
+ /// Default constructor.
+ /// \warning The default constructor is not required to set
+ /// the iterator to some well-defined value. So you should consider it
+ /// as uninitialized.
GraphItemIt() {}
+
/// \brief Copy constructor.
///
/// Copy constructor.
- ///
- GraphItemIt(const GraphItemIt& ) {}
- /// \brief Sets the iterator to the first item.
- ///
- /// Sets the iterator to the first item of \c the graph.
- ///
- explicit GraphItemIt(const _Graph&) {}
- /// \brief Invalid constructor \& conversion.
- ///
- /// This constructor initializes the item to be invalid.
+ GraphItemIt(const GraphItemIt& it) : Item(it) {}
+
+ /// \brief Constructor that sets the iterator to the first item.
+ ///
+ /// Constructor that sets the iterator to the first item.
+ explicit GraphItemIt(const GR&) {}
+
+ /// \brief Constructor for conversion from \c INVALID.
+ ///
+ /// Constructor for conversion from \c INVALID.
+ /// It initializes the iterator to be invalid.
/// \sa Invalid for more details.
GraphItemIt(Invalid) {}
- /// \brief Assign operator for items.
- ///
- /// The items are assignable.
- ///
+
+ /// \brief Assignment operator.
+ ///
+ /// Assignment operator for the iterator.
GraphItemIt& operator=(const GraphItemIt&) { return *this; }
- /// \brief Next item.
- ///
- /// Assign the iterator to the next item.
- ///
+
+ /// \brief Increment the iterator.
+ ///
+ /// This operator increments the iterator, i.e. assigns it to the
+ /// next item.
GraphItemIt& operator++() { return *this; }
+
/// \brief Equality operator
///
+ /// Equality operator.
/// Two iterators are equal if and only if they point to the
/// same object or both are invalid.
bool operator==(const GraphItemIt&) const { return true;}
+
/// \brief Inequality operator
///
- /// \sa operator==(Node n)
- ///
+ /// Inequality operator.
+ /// Two iterators are equal if and only if they point to the
+ /// same object or both are invalid.
bool operator!=(const GraphItemIt&) const { return true;}
@@ -473,6 +481,9 @@
struct Constraints {
void constraints() {
+ checkConcept, _GraphItemIt>();
_GraphItemIt it1(g);
_GraphItemIt it2;
+ _GraphItemIt it3 = it1;
+ _GraphItemIt it4 = INVALID;
it2 = ++it1;
@@ -480,58 +491,68 @@
++(++it1);
- _Item bi = it1;
+ Item bi = it1;
bi = it2;
}
- _Graph& g;
- };
- };
-
- /// \brief Skeleton class for graph InArcIt and OutArcIt
- ///
- /// \note Because InArcIt and OutArcIt may not inherit from the same
- /// base class, the _selector is a additional template parameter. For
- /// InArcIt you should instantiate it with character 'i' and for
- /// OutArcIt with 'o'.
- template
- class GraphIncIt : public _Item {
+ const GR& g;
+ };
+ };
+
+ /// \brief Concept class for \c InArcIt, \c OutArcIt and
+ /// \c IncEdgeIt types.
+ ///
+ /// This class describes the concept of \c InArcIt, \c OutArcIt
+ /// and \c IncEdgeIt subtypes of digraph and graph types.
+ ///
+ /// \note Since these iterator classes do not inherit from the same
+ /// base class, there is an additional template parameter (selector)
+ /// \c sel. For \c InArcIt you should instantiate it with character
+ /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
+ template
+ class GraphIncIt : public Item {
public:
/// \brief Default constructor.
///
- /// @warning The default constructor sets the iterator
- /// to an undefined value.
+ /// Default constructor.
+ /// \warning The default constructor is not required to set
+ /// the iterator to some well-defined value. So you should consider it
+ /// as uninitialized.
GraphIncIt() {}
+
/// \brief Copy constructor.
///
/// Copy constructor.
- ///
- GraphIncIt(GraphIncIt const& gi) : _Item(gi) {}
- /// \brief Sets the iterator to the first arc incoming into or outgoing
- /// from the node.
- ///
- /// Sets the iterator to the first arc incoming into or outgoing
- /// from the node.
- ///
- explicit GraphIncIt(const _Graph&, const _Base&) {}
- /// \brief Invalid constructor \& conversion.
- ///
- /// This constructor initializes the item to be invalid.
+ GraphIncIt(const GraphIncIt& it) : Item(it) {}
+
+ /// \brief Constructor that sets the iterator to the first
+ /// incoming or outgoing arc.
+ ///
+ /// Constructor that sets the iterator to the first arc
+ /// incoming to or outgoing from the given node.
+ explicit GraphIncIt(const GR&, const Base&) {}
+
+ /// \brief Constructor for conversion from \c INVALID.
+ ///
+ /// Constructor for conversion from \c INVALID.
+ /// It initializes the iterator to be invalid.
/// \sa Invalid for more details.
GraphIncIt(Invalid) {}
- /// \brief Assign operator for iterators.
- ///
- /// The iterators are assignable.
- ///
- GraphIncIt& operator=(GraphIncIt const&) { return *this; }
- /// \brief Next item.
- ///
- /// Assign the iterator to the next item.
- ///
+
+ /// \brief Assignment operator.
+ ///
+ /// Assignment operator for the iterator.
+ GraphIncIt& operator=(const GraphIncIt&) { return *this; }
+
+ /// \brief Increment the iterator.
+ ///
+ /// This operator increments the iterator, i.e. assigns it to the
+ /// next arc incoming to or outgoing from the given node.
GraphIncIt& operator++() { return *this; }
/// \brief Equality operator
///
+ /// Equality operator.
/// Two iterators are equal if and only if they point to the
/// same object or both are invalid.
@@ -540,6 +561,7 @@
/// \brief Inequality operator
///
- /// \sa operator==(Node n)
- ///
+ /// Inequality operator.
+ /// Two iterators are equal if and only if they point to the
+ /// same object or both are invalid.
bool operator!=(const GraphIncIt&) const { return true;}
@@ -547,35 +569,33 @@
struct Constraints {
void constraints() {
- checkConcept, _GraphIncIt>();
+ checkConcept, _GraphIncIt>();
_GraphIncIt it1(graph, node);
_GraphIncIt it2;
+ _GraphIncIt it3 = it1;
+ _GraphIncIt it4 = INVALID;
it2 = ++it1;
++it2 = it1;
++(++it1);
- _Item e = it1;
+ Item e = it1;
e = it2;
-
- }
-
- _Item arc;
- _Base node;
- _Graph graph;
- _GraphIncIt it;
- };
- };
-
-
- /// \brief An empty iterable digraph class.
- ///
- /// This class provides beside the core digraph features
- /// iterator based iterable interface for the digraph structure.
+ }
+ const Base& node;
+ const GR& graph;
+ };
+ };
+
+ /// \brief Skeleton class for iterable directed graphs.
+ ///
+ /// This class describes the interface of iterable directed
+ /// graphs. It extends \ref BaseDigraphComponent with the core
+ /// iterable interface.
/// This concept is part of the Digraph concept.
- template
- class IterableDigraphComponent : public _Base {
-
- public:
-
- typedef _Base Base;
+ template
+ class IterableDigraphComponent : public BAS {
+
+ public:
+
+ typedef BAS Base;
typedef typename Base::Node Node;
typedef typename Base::Arc Arc;
@@ -583,68 +603,59 @@
typedef IterableDigraphComponent Digraph;
- /// \name Base iteration
- ///
- /// This interface provides functions for iteration on digraph items
+ /// \name Base Iteration
+ ///
+ /// This interface provides functions for iteration on digraph items.
///
/// @{
- /// \brief Gives back the first node in the iterating order.
- ///
- /// Gives back the first node in the iterating order.
- ///
+ /// \brief Return the first node.
+ ///
+ /// This function gives back the first node in the iteration order.
void first(Node&) const {}
- /// \brief Gives back the next node in the iterating order.
- ///
- /// Gives back the next node in the iterating order.
- ///
+ /// \brief Return the next node.
+ ///
+ /// This function gives back the next node in the iteration order.
void next(Node&) const {}
- /// \brief Gives back the first arc in the iterating order.
- ///
- /// Gives back the first arc in the iterating order.
- ///
+ /// \brief Return the first arc.
+ ///
+ /// This function gives back the first arc in the iteration order.
void first(Arc&) const {}
- /// \brief Gives back the next arc in the iterating order.
- ///
- /// Gives back the next arc in the iterating order.
- ///
+ /// \brief Return the next arc.
+ ///
+ /// This function gives back the next arc in the iteration order.
void next(Arc&) const {}
-
- /// \brief Gives back the first of the arcs point to the given
- /// node.
- ///
- /// Gives back the first of the arcs point to the given node.
- ///
+ /// \brief Return the first arc incomming to the given node.
+ ///
+ /// This function gives back the first arc incomming to the
+ /// given node.
void firstIn(Arc&, const Node&) const {}
- /// \brief Gives back the next of the arcs points to the given
- /// node.
- ///
- /// Gives back the next of the arcs points to the given node.
- ///
+ /// \brief Return the next arc incomming to the given node.
+ ///
+ /// This function gives back the next arc incomming to the
+ /// given node.
void nextIn(Arc&) const {}
- /// \brief Gives back the first of the arcs start from the
+ /// \brief Return the first arc outgoing form the given node.
+ ///
+ /// This function gives back the first arc outgoing form the
/// given node.
- ///
- /// Gives back the first of the arcs start from the given node.
- ///
void firstOut(Arc&, const Node&) const {}
- /// \brief Gives back the next of the arcs start from the given
- /// node.
- ///
- /// Gives back the next of the arcs start from the given node.
- ///
+ /// \brief Return the next arc outgoing form the given node.
+ ///
+ /// This function gives back the next arc outgoing form the
+ /// given node.
void nextOut(Arc&) const {}
/// @}
- /// \name Class based iteration
- ///
- /// This interface provides functions for iteration on digraph items
+ /// \name Class Based Iteration
+ ///
+ /// This interface provides iterator classes for digraph items.
///
/// @{
@@ -656,7 +667,7 @@
typedef GraphItemIt NodeIt;
- /// \brief This iterator goes through each node.
- ///
- /// This iterator goes through each node.
+ /// \brief This iterator goes through each arc.
+ ///
+ /// This iterator goes through each arc.
///
typedef GraphItemIt ArcIt;
@@ -664,5 +675,5 @@
/// \brief This iterator goes trough the incoming arcs of a node.
///
- /// This iterator goes trough the \e inccoming arcs of a certain node
+ /// This iterator goes trough the \e incoming arcs of a certain node
/// of a digraph.
typedef GraphIncIt InArcIt;
@@ -676,24 +687,24 @@
/// \brief The base node of the iterator.
///
- /// Gives back the base node of the iterator.
- /// It is always the target of the pointed arc.
+ /// This function gives back the base node of the iterator.
+ /// It is always the target node of the pointed arc.
Node baseNode(const InArcIt&) const { return INVALID; }
/// \brief The running node of the iterator.
///
- /// Gives back the running node of the iterator.
- /// It is always the source of the pointed arc.
+ /// This function gives back the running node of the iterator.
+ /// It is always the source node of the pointed arc.
Node runningNode(const InArcIt&) const { return INVALID; }
/// \brief The base node of the iterator.
///
- /// Gives back the base node of the iterator.
- /// It is always the source of the pointed arc.
+ /// This function gives back the base node of the iterator.
+ /// It is always the source node of the pointed arc.
Node baseNode(const OutArcIt&) const { return INVALID; }
/// \brief The running node of the iterator.
///
- /// Gives back the running node of the iterator.
- /// It is always the target of the pointed arc.
+ /// This function gives back the running node of the iterator.
+ /// It is always the target node of the pointed arc.
Node runningNode(const OutArcIt&) const { return INVALID; }
@@ -737,10 +748,10 @@
typename _Digraph::Node n;
- typename _Digraph::InArcIt ieit(INVALID);
- typename _Digraph::OutArcIt oeit(INVALID);
- n = digraph.baseNode(ieit);
- n = digraph.runningNode(ieit);
- n = digraph.baseNode(oeit);
- n = digraph.runningNode(oeit);
+ const typename _Digraph::InArcIt iait(INVALID);
+ const typename _Digraph::OutArcIt oait(INVALID);
+ n = digraph.baseNode(iait);
+ n = digraph.runningNode(iait);
+ n = digraph.baseNode(oait);
+ n = digraph.runningNode(oait);
ignore_unused_variable_warning(n);
}
@@ -748,18 +759,18 @@
const _Digraph& digraph;
-
- };
- };
-
- /// \brief An empty iterable undirected graph class.
- ///
- /// This class provides beside the core graph features iterator
- /// based iterable interface for the undirected graph structure.
+ };
+ };
+
+ /// \brief Skeleton class for iterable undirected graphs.
+ ///
+ /// This class describes the interface of iterable undirected
+ /// graphs. It extends \ref IterableDigraphComponent with the core
+ /// iterable interface of undirected graphs.
/// This concept is part of the Graph concept.
- template
- class IterableGraphComponent : public IterableDigraphComponent<_Base> {
- public:
-
- typedef _Base Base;
+ template
+ class IterableGraphComponent : public IterableDigraphComponent {
+ public:
+
+ typedef BAS Base;
typedef typename Base::Node Node;
typedef typename Base::Arc Arc;
@@ -769,34 +780,29 @@
typedef IterableGraphComponent Graph;
- /// \name Base iteration
- ///
- /// This interface provides functions for iteration on graph items
+ /// \name Base Iteration
+ ///
+ /// This interface provides functions for iteration on edges.
+ ///
/// @{
- using IterableDigraphComponent<_Base>::first;
- using IterableDigraphComponent<_Base>::next;
-
- /// \brief Gives back the first edge in the iterating
- /// order.
- ///
- /// Gives back the first edge in the iterating order.
- ///
+ using IterableDigraphComponent::first;
+ using IterableDigraphComponent::next;
+
+ /// \brief Return the first edge.
+ ///
+ /// This function gives back the first edge in the iteration order.
void first(Edge&) const {}
- /// \brief Gives back the next edge in the iterating
- /// order.
- ///
- /// Gives back the next edge in the iterating order.
- ///
+ /// \brief Return the next edge.
+ ///
+ /// This function gives back the next edge in the iteration order.
void next(Edge&) const {}
-
- /// \brief Gives back the first of the edges from the
+ /// \brief Return the first edge incident to the given node.
+ ///
+ /// This function gives back the first edge incident to the given
+ /// node. The bool parameter gives back the direction for which the
+ /// source node of the directed arc representing the edge is the
/// given node.
- ///
- /// Gives back the first of the edges from the given
- /// node. The bool parameter gives back that direction which
- /// gives a good direction of the edge so the source of the
- /// directed arc is the given node.
void firstInc(Edge&, bool&, const Node&) const {}
@@ -804,38 +810,39 @@
/// given node.
///
- /// Gives back the next of the edges from the given
- /// node. The bool parameter should be used as the \c firstInc()
- /// use it.
+ /// This function gives back the next edge incident to the given
+ /// node. The bool parameter should be used as \c firstInc() use it.
void nextInc(Edge&, bool&) const {}
- using IterableDigraphComponent<_Base>::baseNode;
- using IterableDigraphComponent<_Base>::runningNode;
+ using IterableDigraphComponent::baseNode;
+ using IterableDigraphComponent::runningNode;
/// @}
- /// \name Class based iteration
- ///
- /// This interface provides functions for iteration on graph items
+ /// \name Class Based Iteration
+ ///
+ /// This interface provides iterator classes for edges.
///
/// @{
- /// \brief This iterator goes through each node.
- ///
- /// This iterator goes through each node.
+ /// \brief This iterator goes through each edge.
+ ///
+ /// This iterator goes through each edge.
typedef GraphItemIt EdgeIt;
- /// \brief This iterator goes trough the incident arcs of a
+
+ /// \brief This iterator goes trough the incident edges of a
/// node.
///
- /// This iterator goes trough the incident arcs of a certain
+ /// This iterator goes trough the incident edges of a certain
/// node of a graph.
- typedef GraphIncIt IncEdgeIt;
+ typedef GraphIncIt IncEdgeIt;
+
/// \brief The base node of the iterator.
///
- /// Gives back the base node of the iterator.
+ /// This function gives back the base node of the iterator.
Node baseNode(const IncEdgeIt&) const { return INVALID; }
/// \brief The running node of the iterator.
///
- /// Gives back the running node of the iterator.
+ /// This function gives back the running node of the iterator.
Node runningNode(const IncEdgeIt&) const { return INVALID; }
@@ -866,52 +873,52 @@
typename _Graph::EdgeIt >();
checkConcept, typename _Graph::IncEdgeIt>();
+ typename _Graph::Node, 'e'>, typename _Graph::IncEdgeIt>();
typename _Graph::Node n;
- typename _Graph::IncEdgeIt ueit(INVALID);
- n = graph.baseNode(ueit);
- n = graph.runningNode(ueit);
+ const typename _Graph::IncEdgeIt ieit(INVALID);
+ n = graph.baseNode(ieit);
+ n = graph.runningNode(ieit);
}
}
const _Graph& graph;
-
- };
- };
-
- /// \brief An empty alteration notifier digraph class.
- ///
- /// This class provides beside the core digraph features alteration
- /// notifier interface for the digraph structure. This implements
+ };
+ };
+
+ /// \brief Skeleton class for alterable directed graphs.
+ ///
+ /// This class describes the interface of alterable directed
+ /// graphs. It extends \ref BaseDigraphComponent with the alteration
+ /// notifier interface. It implements
/// an observer-notifier pattern for each digraph item. More
/// obsevers can be registered into the notifier and whenever an
- /// alteration occured in the digraph all the observers will
+ /// alteration occured in the digraph all the observers will be
/// notified about it.
- template
- class AlterableDigraphComponent : public _Base {
- public:
-
- typedef _Base Base;
+ template
+ class AlterableDigraphComponent : public BAS {
+ public:
+
+ typedef BAS Base;
typedef typename Base::Node Node;
typedef typename Base::Arc Arc;
- /// The node observer registry.
+ /// Node alteration notifier class.
typedef AlterationNotifier
NodeNotifier;
- /// The arc observer registry.
+ /// Arc alteration notifier class.
typedef AlterationNotifier
ArcNotifier;
- /// \brief Gives back the node alteration notifier.
- ///
- /// Gives back the node alteration notifier.
+ /// \brief Return the node alteration notifier.
+ ///
+ /// This function gives back the node alteration notifier.
NodeNotifier& notifier(Node) const {
- return NodeNotifier();
+ return NodeNotifier();
}
- /// \brief Gives back the arc alteration notifier.
- ///
- /// Gives back the arc alteration notifier.
+ /// \brief Return the arc alteration notifier.
+ ///
+ /// This function gives back the arc alteration notifier.
ArcNotifier& notifier(Arc) const {
return ArcNotifier();
@@ -933,32 +940,31 @@
const _Digraph& digraph;
-
- };
-
- };
-
- /// \brief An empty alteration notifier undirected graph class.
- ///
- /// This class provides beside the core graph features alteration
- /// notifier interface for the graph structure. This implements
- /// an observer-notifier pattern for each graph item. More
+ };
+ };
+
+ /// \brief Skeleton class for alterable undirected graphs.
+ ///
+ /// This class describes the interface of alterable undirected
+ /// graphs. It extends \ref AlterableDigraphComponent with the alteration
+ /// notifier interface of undirected graphs. It implements
+ /// an observer-notifier pattern for the edges. More
/// obsevers can be registered into the notifier and whenever an
- /// alteration occured in the graph all the observers will
+ /// alteration occured in the graph all the observers will be
/// notified about it.
- template
- class AlterableGraphComponent : public AlterableDigraphComponent<_Base> {
- public:
-
- typedef _Base Base;
+ template
+ class AlterableGraphComponent : public AlterableDigraphComponent {
+ public:
+
+ typedef BAS Base;
typedef typename Base::Edge Edge;
- /// The arc observer registry.
+ /// Edge alteration notifier class.
typedef AlterationNotifier
EdgeNotifier;
- /// \brief Gives back the arc alteration notifier.
- ///
- /// Gives back the arc alteration notifier.
+ /// \brief Return the edge alteration notifier.
+ ///
+ /// This function gives back the edge alteration notifier.
EdgeNotifier& notifier(Edge) const {
return EdgeNotifier();
@@ -968,5 +974,5 @@
struct Constraints {
void constraints() {
- checkConcept, _Graph>();
+ checkConcept, _Graph>();
typename _Graph::EdgeNotifier& uen
= graph.notifier(typename _Graph::Edge());
@@ -975,26 +981,32 @@
const _Graph& graph;
-
- };
-
- };
-
- /// \brief Class describing the concept of graph maps
- ///
- /// This class describes the common interface of the graph maps
- /// (NodeMap, ArcMap), that is maps that can be used to
- /// associate data to graph descriptors (nodes or arcs).
- template
- class GraphMap : public ReadWriteMap<_Item, _Value> {
- public:
-
- typedef ReadWriteMap<_Item, _Value> Parent;
+ };
+ };
+
+ /// \brief Concept class for standard graph maps.
+ ///
+ /// This class describes the concept of standard graph maps, i.e.
+ /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
+ /// graph types, which can be used for associating data to graph items.
+ /// The standard graph maps must conform to the ReferenceMap concept.
+ template
+ class GraphMap : public ReferenceMap {
+ public:
+
+ typedef ReadWriteMap Parent;
/// The graph type of the map.
- typedef _Graph Graph;
+ typedef GR Graph;
/// The key type of the map.
- typedef _Item Key;
+ typedef K Key;
/// The value type of the map.
- typedef _Value Value;
+ typedef V Value;
+ /// The reference type of the map.
+ typedef Value& Reference;
+ /// The const reference type of the map.
+ typedef const Value& ConstReference;
+
+ // The reference map tag.
+ typedef True ReferenceMapTag;
/// \brief Construct a new map.
@@ -1004,5 +1016,5 @@
/// \brief Construct a new map with default value.
///
- /// Construct a new map for the graph and initalise the values.
+ /// Construct a new map for the graph and initalize the values.
GraphMap(const Graph&, const Value&) {}
@@ -1013,7 +1025,7 @@
GraphMap(const GraphMap&) : Parent() {}
- /// \brief Assign operator.
- ///
- /// Assign operator. It does not mofify the underlying graph,
+ /// \brief Assignment operator.
+ ///
+ /// Assignment operator. It does not mofify the underlying graph,
/// it just iterates on the current item set and set the map
/// with the value returned by the assigned map.
@@ -1028,21 +1040,22 @@
struct Constraints {
void constraints() {
- checkConcept, _Map >();
- // Construction with a graph parameter
- _Map a(g);
- // Constructor with a graph and a default value parameter
- _Map a2(g,t);
- // Copy constructor.
- // _Map b(c);
-
+ checkConcept
+ , _Map>();
+ _Map m1(g);
+ _Map m2(g,t);
+
+ // Copy constructor
+ // _Map m3(m);
+
+ // Assignment operator
// ReadMap cmap;
- // b = cmap;
-
- ignore_unused_variable_warning(a);
- ignore_unused_variable_warning(a2);
- // ignore_unused_variable_warning(b);
- }
-
- const _Map &c;
+ // m3 = cmap;
+
+ ignore_unused_variable_warning(m1);
+ ignore_unused_variable_warning(m2);
+ // ignore_unused_variable_warning(m3);
+ }
+
+ const _Map &m;
const Graph &g;
const typename GraphMap::Value &t;
@@ -1051,14 +1064,15 @@
};
- /// \brief An empty mappable digraph class.
- ///
- /// This class provides beside the core digraph features
- /// map interface for the digraph structure.
+ /// \brief Skeleton class for mappable directed graphs.
+ ///
+ /// This class describes the interface of mappable directed graphs.
+ /// It extends \ref BaseDigraphComponent with the standard digraph
+ /// map classes, namely \c NodeMap and \c ArcMap.
/// This concept is part of the Digraph concept.
- template
- class MappableDigraphComponent : public _Base {
- public:
-
- typedef _Base Base;
+ template
+ class MappableDigraphComponent : public BAS {
+ public:
+
+ typedef BAS Base;
typedef typename Base::Node Node;
typedef typename Base::Arc Arc;
@@ -1066,12 +1080,12 @@
typedef MappableDigraphComponent Digraph;
- /// \brief ReadWrite map of the nodes.
- ///
- /// ReadWrite map of the nodes.
- ///
- template
- class NodeMap : public GraphMap {
+ /// \brief Standard graph map for the nodes.
+ ///
+ /// Standard graph map for the nodes.
+ /// It conforms to the ReferenceMap concept.
+ template
+ class NodeMap : public GraphMap {
public:
- typedef GraphMap Parent;
+ typedef GraphMap Parent;
/// \brief Construct a new map.
@@ -1083,6 +1097,6 @@
/// \brief Construct a new map with default value.
///
- /// Construct a new map for the digraph and initalise the values.
- NodeMap(const MappableDigraphComponent& digraph, const _Value& value)
+ /// Construct a new map for the digraph and initalize the values.
+ NodeMap(const MappableDigraphComponent& digraph, const V& value)
: Parent(digraph, value) {}
@@ -1093,10 +1107,10 @@
NodeMap(const NodeMap& nm) : Parent(nm) {}
- /// \brief Assign operator.
- ///
- /// Assign operator.
+ /// \brief Assignment operator.
+ ///
+ /// Assignment operator.
template
NodeMap& operator=(const CMap&) {
- checkConcept, CMap>();
+ checkConcept, CMap>();
return *this;
}
@@ -1104,12 +1118,12 @@
};
- /// \brief ReadWrite map of the arcs.
- ///
- /// ReadWrite map of the arcs.
- ///
- template
- class ArcMap : public GraphMap {
+ /// \brief Standard graph map for the arcs.
+ ///
+ /// Standard graph map for the arcs.
+ /// It conforms to the ReferenceMap concept.
+ template
+ class ArcMap : public GraphMap {
public:
- typedef GraphMap Parent;
+ typedef GraphMap Parent;
/// \brief Construct a new map.
@@ -1121,6 +1135,6 @@
/// \brief Construct a new map with default value.
///
- /// Construct a new map for the digraph and initalise the values.
- ArcMap(const MappableDigraphComponent& digraph, const _Value& value)
+ /// Construct a new map for the digraph and initalize the values.
+ ArcMap(const MappableDigraphComponent& digraph, const V& value)
: Parent(digraph, value) {}
@@ -1131,10 +1145,10 @@
ArcMap(const ArcMap& nm) : Parent(nm) {}
- /// \brief Assign operator.
- ///
- /// Assign operator.
+ /// \brief Assignment operator.
+ ///
+ /// Assignment operator.
template
ArcMap& operator=(const CMap&) {
- checkConcept, CMap>();
+ checkConcept, CMap>();
return *this;
}
@@ -1183,30 +1197,31 @@
}
- _Digraph& digraph;
- };
- };
-
- /// \brief An empty mappable base bipartite graph class.
- ///
- /// This class provides beside the core graph features
- /// map interface for the graph structure.
+ const _Digraph& digraph;
+ };
+ };
+
+ /// \brief Skeleton class for mappable undirected graphs.
+ ///
+ /// This class describes the interface of mappable undirected graphs.
+ /// It extends \ref MappableDigraphComponent with the standard graph
+ /// map class for edges (\c EdgeMap).
/// This concept is part of the Graph concept.
- template
- class MappableGraphComponent : public MappableDigraphComponent<_Base> {
- public:
-
- typedef _Base Base;
+ template
+ class MappableGraphComponent : public MappableDigraphComponent {
+ public:
+
+ typedef BAS Base;
typedef typename Base::Edge Edge;
typedef MappableGraphComponent Graph;
- /// \brief ReadWrite map of the edges.
- ///
- /// ReadWrite map of the edges.
- ///
- template
- class EdgeMap : public GraphMap {
+ /// \brief Standard graph map for the edges.
+ ///
+ /// Standard graph map for the edges.
+ /// It conforms to the ReferenceMap concept.
+ template
+ class EdgeMap : public GraphMap {
public:
- typedef GraphMap Parent;
+ typedef GraphMap Parent;
/// \brief Construct a new map.
@@ -1218,6 +1233,6 @@
/// \brief Construct a new map with default value.
///
- /// Construct a new map for the graph and initalise the values.
- EdgeMap(const MappableGraphComponent& graph, const _Value& value)
+ /// Construct a new map for the graph and initalize the values.
+ EdgeMap(const MappableGraphComponent& graph, const V& value)
: Parent(graph, value) {}
@@ -1228,10 +1243,10 @@
EdgeMap(const EdgeMap& nm) : Parent(nm) {}
- /// \brief Assign operator.
- ///
- /// Assign operator.
+ /// \brief Assignment operator.
+ ///
+ /// Assignment operator.
template
EdgeMap& operator=(const CMap&) {
- checkConcept