Index: CMakeLists.txt
===================================================================
--- CMakeLists.txt (revision 1185)
+++ CMakeLists.txt (revision 1230)
@@ -63,5 +63,5 @@
FIND_PACKAGE(Ghostscript)
FIND_PACKAGE(GLPK 4.33)
-FIND_PACKAGE(CPLEX)
+FIND_PACKAGE(ILOG)
FIND_PACKAGE(COIN)
Index: INSTALL
===================================================================
--- INSTALL (revision 1208)
+++ INSTALL (revision 1230)
@@ -107,35 +107,7 @@
really want to use this option.
--DLEMON_DOC_SOURCE_BROWSER=YES
-
- Include the browsable cross referenced LEMON source code into the
- doc. It makes the doc quite bloated, but may be useful for
- developing LEMON itself.
-
--DLEMON_DOC_USE_MATHJAX=YES
-
- Use MathJax (http://mathjax.org) for rendering the math formulae in
- the doc. It of much higher quality compared to the default LaTeX
- generated static images and it allows copy&paste of the formulae to
- LaTeX, Open Office, MS Word etc. documents.
-
- On the other hand, it needs either Internet access or a locally
- installed version of MathJax to properly render the doc.
-
--DLEMON_DOC_MATHJAX_RELPATH=DIRECTORY
-
- The location of the MathJax library. It defaults to
- http://www.mathjax.org/mathjax, which necessitates Internet access
- for proper rendering. The easiest way to make it usable offline is
- to set this parameter to 'mathjax' and copy all files of the MathJax
- library into the 'doc/html/mathjax' subdirectory of the build
- location.
-
- See http://docs.mathjax.org/en/latest/installation.html for more details.
-
-
-DGLPK_ROOT_DIR=DIRECTORY
-DCOIN_ROOT_DIR=DIRECTORY
--DCPLEX_ROOT_DIR=DIRECTORY
+-DILOG_ROOT_DIR=DIRECTORY
Install root directory prefixes of optional third party libraries.
Index: ake/FindCPLEX.cmake
===================================================================
--- cmake/FindCPLEX.cmake (revision 1119)
+++ (revision )
@@ -1,40 +1,0 @@
-SET(CPLEX_ROOT_DIR "" CACHE PATH "CPLEX root directory")
-
-FIND_PATH(CPLEX_INCLUDE_DIR
- ilcplex/cplex.h
- PATHS "C:/ILOG/CPLEX/include"
- PATHS "/opt/ilog/cplex/include"
- HINTS ${CPLEX_ROOT_DIR}/include
-)
-FIND_LIBRARY(CPLEX_LIBRARY
- cplex
- PATHS "C:/ILOG/CPLEX/lib/msvc7/stat_mda"
- PATHS "/opt/ilog/cplex/bin"
- HINTS ${CPLEX_ROOT_DIR}/bin
- HINTS ${CPLEX_ROOT_DIR}/lib
-)
-
-INCLUDE(FindPackageHandleStandardArgs)
-FIND_PACKAGE_HANDLE_STANDARD_ARGS(CPLEX DEFAULT_MSG CPLEX_LIBRARY CPLEX_INCLUDE_DIR)
-
-FIND_PATH(CPLEX_BIN_DIR
- cplex.dll
- PATHS "C:/ILOG/CPLEX/bin/x86_win32"
- HINTS ${CPLEX_ROOT_DIR}/bin
-)
-
-IF(CPLEX_FOUND)
- SET(CPLEX_INCLUDE_DIRS ${CPLEX_INCLUDE_DIR})
- SET(CPLEX_LIBRARIES ${CPLEX_LIBRARY})
- IF(CMAKE_SYSTEM_NAME STREQUAL "Linux")
- SET(CPLEX_LIBRARIES "${CPLEX_LIBRARIES};m;pthread")
- ENDIF(CMAKE_SYSTEM_NAME STREQUAL "Linux")
-ENDIF(CPLEX_FOUND)
-
-MARK_AS_ADVANCED(CPLEX_LIBRARY CPLEX_INCLUDE_DIR CPLEX_BIN_DIR)
-
-IF(CPLEX_FOUND)
- SET(LEMON_HAVE_LP TRUE)
- SET(LEMON_HAVE_MIP TRUE)
- SET(LEMON_HAVE_CPLEX TRUE)
-ENDIF(CPLEX_FOUND)
Index: cmake/FindGLPK.cmake
===================================================================
--- cmake/FindGLPK.cmake (revision 685)
+++ cmake/FindGLPK.cmake (revision 1230)
@@ -60,2 +60,3 @@
SET(LEMON_HAVE_GLPK TRUE)
ENDIF(GLPK_FOUND)
+
Index: cmake/FindILOG.cmake
===================================================================
--- cmake/FindILOG.cmake (revision 1230)
+++ cmake/FindILOG.cmake (revision 1230)
@@ -0,0 +1,108 @@
+FIND_PATH(ILOG_ROOT_DIR
+ NAMES cplex
+ DOC "CPLEX STUDIO root directory"
+ PATHS /opt/ibm/ILOG /usr/local/ibm/ILOG /usr/local/ILOG /usr/local/ilog
+ PATHS "$ENV{HOME}/ILOG" "$ENV{HOME}/.local/ILOG"
+ PATHS "$ENV{HOME}/ibm/ILOG" "$ENV{HOME}/.local/ibm/ILOG"
+ PATHS "C:/Program Files/IBM/ILOG"
+ PATH_SUFFIXES "CPLEX_Studio126" "CPLEX_Studio125"
+ "CPLEX_Studio124" "CPLEX_Studio123" "CPLEX_Studio122"
+ NO_DEFAULT_PATH
+)
+
+IF(WIN32)
+ IF(MSVC_VERSION STREQUAL "1400")
+ SET(ILOG_WIN_COMPILER "windows_vs2005")
+ ELSEIF(MSVC_VERSION STREQUAL "1500")
+ SET(ILOG_WIN_COMPILER "windows_vs2008")
+ ELSEIF(MSVC_VERSION STREQUAL "1600")
+ SET(ILOG_WIN_COMPILER "windows_vs2010")
+ ELSE()
+ SET(ILOG_WIN_COMPILER "windows_vs2008")
+ ENDIF()
+ IF(CMAKE_CL_64)
+ SET(ILOG_WIN_COMPILER "x64_${ILOG_WIN_COMPILER}")
+ SET(ILOG_WIN_PLATFORM "x64_win32")
+ ELSE()
+ SET(ILOG_WIN_COMPILER "x86_${ILOG_WIN_COMPILER}")
+ SET(ILOG_WIN_PLATFORM "x86_win32")
+ ENDIF()
+ENDIF()
+
+FIND_PATH(ILOG_CPLEX_ROOT_DIR
+ NAMES include/ilcplex
+ HINTS ${ILOG_ROOT_DIR}/cplex ${ILOG_ROOT_DIR}/cplex121
+ ${ILOG_ROOT_DIR}/cplex122 ${ILOG_ROOT_DIR}/cplex123
+ DOC "CPLEX root directory"
+ NO_DEFAULT_PATH
+)
+
+FIND_PATH(ILOG_CONCERT_ROOT_DIR
+ NAMES include/ilconcert
+ HINTS ${ILOG_ROOT_DIR}/concert ${ILOG_ROOT_DIR}/concert29
+ DOC "CONCERT root directory"
+ NO_DEFAULT_PATH
+)
+
+FIND_PATH(ILOG_CPLEX_INCLUDE_DIR
+ ilcplex/cplex.h
+ HINTS ${ILOG_CPLEX_ROOT_DIR}/include
+ NO_DEFAULT_PATH
+)
+
+FIND_PATH(ILOG_CONCERT_INCLUDE_DIR
+ ilconcert/ilobasic.h
+ HINTS ${ILOG_CONCERT_ROOT_DIR}/include
+ NO_DEFAULT_PATH
+)
+
+FIND_LIBRARY(ILOG_CPLEX_LIBRARY
+ cplex cplex121 cplex122 cplex123 cplex124
+ HINTS ${ILOG_CPLEX_ROOT_DIR}/lib/x86_sles10_4.1/static_pic
+ ${ILOG_CPLEX_ROOT_DIR}/lib/x86-64_sles10_4.1/static_pic
+ ${ILOG_CPLEX_ROOT_DIR}/lib/x86_debian4.0_4.1/static_pic
+ ${ILOG_CPLEX_ROOT_DIR}/lib/x86-64_debian4.0_4.1/static_pic
+ ${ILOG_CPLEX_ROOT_DIR}/lib/${ILOG_WIN_COMPILER}/stat_mda
+ NO_DEFAULT_PATH
+ )
+
+FIND_LIBRARY(ILOG_CONCERT_LIBRARY
+ concert
+ HINTS ${ILOG_CONCERT_ROOT_DIR}/lib/x86_sles10_4.1/static_pic
+ ${ILOG_CONCERT_ROOT_DIR}/lib/x86-64_sles10_4.1/static_pic
+ ${ILOG_CONCERT_ROOT_DIR}/lib/x86_debian4.0_4.1/static_pic
+ ${ILOG_CONCERT_ROOT_DIR}/lib/x86-64_debian4.0_4.1/static_pic
+ ${ILOG_CONCERT_ROOT_DIR}/lib/${ILOG_WIN_COMPILER}/stat_mda
+ NO_DEFAULT_PATH
+ )
+
+FIND_FILE(ILOG_CPLEX_DLL
+ cplex121.dll cplex122.dll cplex123.dll cplex124.dll
+ HINTS ${ILOG_CPLEX_ROOT_DIR}/bin/${ILOG_WIN_PLATFORM}
+ NO_DEFAULT_PATH
+ )
+
+INCLUDE(FindPackageHandleStandardArgs)
+FIND_PACKAGE_HANDLE_STANDARD_ARGS(ILOG
+ DEFAULT_MSG ILOG_CPLEX_LIBRARY ILOG_CPLEX_INCLUDE_DIR
+ )
+
+IF(ILOG_FOUND)
+ SET(ILOG_INCLUDE_DIRS ${ILOG_CPLEX_INCLUDE_DIR} ${ILOG_CONCERT_INCLUDE_DIR})
+ SET(ILOG_LIBRARIES ${ILOG_CPLEX_LIBRARY} ${ILOG_CONCERT_LIBRARY})
+ IF(CMAKE_SYSTEM_NAME STREQUAL "Linux")
+ # SET(CPLEX_LIBRARIES "${CPLEX_LIBRARIES};m;pthread")
+ SET(ILOG_LIBRARIES ${ILOG_LIBRARIES} "m" "pthread")
+ ENDIF(CMAKE_SYSTEM_NAME STREQUAL "Linux")
+ENDIF(ILOG_FOUND)
+
+MARK_AS_ADVANCED(
+ ILOG_CPLEX_LIBRARY ILOG_CPLEX_INCLUDE_DIR ILOG_CPLEX_DLL
+ ILOG_CONCERT_LIBRARY ILOG_CONCERT_INCLUDE_DIR ILOG_CONCERT_DLL
+ )
+
+IF(ILOG_FOUND)
+ SET(LEMON_HAVE_LP TRUE)
+ SET(LEMON_HAVE_MIP TRUE)
+ SET(LEMON_HAVE_CPLEX TRUE)
+ENDIF(ILOG_FOUND)
Index: doc/CMakeLists.txt
===================================================================
--- doc/CMakeLists.txt (revision 1221)
+++ doc/CMakeLists.txt (revision 1135)
@@ -5,6 +5,4 @@
SET(LEMON_DOC_SOURCE_BROWSER "NO" CACHE STRING "Include source into the doc (YES/NO).")
-SET(LEMON_DOC_USE_MATHJAX "NO" CACHE STRING "Use MathJax to display math formulae (YES/NO).")
-SET(LEMON_DOC_MATHJAX_RELPATH "http://www.mathjax.org/mathjax" CACHE STRING "MathJax library location.")
CONFIGURE_FILE(
@@ -35,21 +33,20 @@
COMMAND ${CMAKE_COMMAND} -E remove_directory gen-images
COMMAND ${CMAKE_COMMAND} -E make_directory gen-images
- COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r20 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
- COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/adaptors2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/adaptors2.eps
- COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
- COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
- COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
- COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
- COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps
- COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r24 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps
- COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r24 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps
- COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r40 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
- COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r24 -sOutputFile=gen-images/tsp.png ${CMAKE_CURRENT_SOURCE_DIR}/images/tsp.eps
- COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
- COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
- COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
- COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
- COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
COMMAND ${CMAKE_COMMAND} -E remove_directory html
+ COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
@@ -76,5 +73,10 @@
IF(WGET_FOUND)
ADD_CUSTOM_TARGET(update-external-tags
- COMMAND ${WGET_EXECUTABLE} -N http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag
+ COMMAND ${CMAKE_COMMAND} -E make_directory dl
+ # COMMAND ${CMAKE_COMMAND} -E copy libstdc++.tag dl
+ COMMAND ${WGET_EXECUTABLE} wget -P dl -N libstdc++.tag.tmp http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag
+ COMMAND ${CMAKE_COMMAND} -E rename dl/libstdc++.tag libstdc++.tag
+ COMMAND ${CMAKE_COMMAND} -E remove dl/libstdc++.tag
+ COMMAND ${CMAKE_COMMAND} -E remove_directory dl
WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
)
Index: doc/Doxyfile.in
===================================================================
--- doc/Doxyfile.in (revision 1221)
+++ doc/Doxyfile.in (revision 1111)
@@ -78,5 +78,4 @@
FILE_VERSION_FILTER =
LAYOUT_FILE = "@abs_top_srcdir@/doc/DoxygenLayout.xml"
-CITE_BIB_FILES = "@abs_top_srcdir@/doc/references.bib"
#---------------------------------------------------------------------------
# configuration options related to warning and progress messages
@@ -184,6 +183,6 @@
FORMULA_FONTSIZE = 10
FORMULA_TRANSPARENT = YES
-USE_MATHJAX = @LEMON_DOC_USE_MATHJAX@
-MATHJAX_RELPATH = @LEMON_DOC_MATHJAX_RELPATH@
+USE_MATHJAX = NO
+MATHJAX_RELPATH = http://www.mathjax.org/mathjax
SEARCHENGINE = YES
SERVER_BASED_SEARCH = NO
Index: doc/groups.dox
===================================================================
--- doc/groups.dox (revision 1221)
+++ doc/groups.dox (revision 1165)
@@ -113,12 +113,4 @@
detailed documentation of particular adaptors.
-Since the adaptor classes conform to the \ref graph_concepts "graph concepts",
-an adaptor can even be applied to another one.
-The following image illustrates a situation when a \ref SubDigraph adaptor
-is applied on a digraph and \ref Undirector is applied on the subgraph.
-
-\image html adaptors2.png
-\image latex adaptors2.eps "Using graph adaptors" width=\textwidth
-
The behavior of graph adaptors can be very different. Some of them keep
capabilities of the original graph while in other cases this would be
@@ -318,5 +310,5 @@
This group contains the common graph search algorithms, namely
\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
-\cite clrs01algorithms.
+\ref clrs01algorithms.
*/
@@ -327,5 +319,5 @@
This group contains the algorithms for finding shortest paths in digraphs
-\cite clrs01algorithms.
+\ref clrs01algorithms.
- \ref Dijkstra algorithm for finding shortest paths from a source node
@@ -349,5 +341,5 @@
This group contains the algorithms for finding minimum cost spanning
-trees and arborescences \cite clrs01algorithms.
+trees and arborescences \ref clrs01algorithms.
*/
@@ -358,5 +350,5 @@
This group contains the algorithms for finding maximum flows and
-feasible circulations \cite clrs01algorithms, \cite amo93networkflows.
+feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
The \e maximum \e flow \e problem is to find a flow of maximum value between
@@ -374,11 +366,11 @@
LEMON contains several algorithms for solving maximum flow problems:
- \ref EdmondsKarp Edmonds-Karp algorithm
- \cite edmondskarp72theoretical.
+ \ref edmondskarp72theoretical.
- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
- \cite goldberg88newapproach.
+ \ref goldberg88newapproach.
- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
- \cite dinic70algorithm, \cite sleator83dynamic.
+ \ref dinic70algorithm, \ref sleator83dynamic.
- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
- \cite goldberg88newapproach, \cite sleator83dynamic.
+ \ref goldberg88newapproach, \ref sleator83dynamic.
In most cases the \ref Preflow algorithm provides the
@@ -400,18 +392,18 @@
This group contains the algorithms for finding minimum cost flows and
-circulations \cite amo93networkflows. For more information about this
-problem and its dual solution, see: \ref min_cost_flow
+circulations \ref amo93networkflows. For more information about this
+problem and its dual solution, see \ref min_cost_flow
"Minimum Cost Flow Problem".
LEMON contains several algorithms for this problem.
- \ref NetworkSimplex Primal Network Simplex algorithm with various
- pivot strategies \cite dantzig63linearprog, \cite kellyoneill91netsimplex.
+ pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
- \ref CostScaling Cost Scaling algorithm based on push/augment and
- relabel operations \cite goldberg90approximation, \cite goldberg97efficient,
- \cite bunnagel98efficient.
+ relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
+ \ref bunnagel98efficient.
- \ref CapacityScaling Capacity Scaling algorithm based on the successive
- shortest path method \cite edmondskarp72theoretical.
+ shortest path method \ref edmondskarp72theoretical.
- \ref CycleCanceling Cycle-Canceling algorithms, two of which are
- strongly polynomial \cite klein67primal, \cite goldberg89cyclecanceling.
+ strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
@@ -429,9 +421,4 @@
which is capable of handling real-valued arc costs (other numerical
data are required to be integer).
-
-For more details about these implementations and for a comprehensive
-experimental study, see the paper \cite KiralyKovacs12MCF.
-It also compares these codes to other publicly available
-minimum cost flow solvers.
*/
@@ -472,5 +459,5 @@
This group contains the algorithms for finding minimum mean cycles
-\cite amo93networkflows, \cite karp78characterization.
+\ref amo93networkflows, \ref karp78characterization.
The \e minimum \e mean \e cycle \e problem is to find a directed cycle
@@ -488,9 +475,9 @@
LEMON contains three algorithms for solving the minimum mean cycle problem:
-- \ref KarpMmc Karp's original algorithm \cite karp78characterization.
+- \ref KarpMmc Karp's original algorithm \ref karp78characterization.
- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
- version of Karp's algorithm \cite hartmann93finding.
+ version of Karp's algorithm \ref hartmann93finding.
- \ref HowardMmc Howard's policy iteration algorithm
- \cite dasdan98minmeancycle, \cite dasdan04experimental.
+ \ref dasdan98minmeancycle, \ref dasdan04experimental.
In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
@@ -498,5 +485,6 @@
time is exponential.
Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
-run in time O(ne) and use space O(n2+e).
+run in time O(ne) and use space O(n2+e), but the latter one is
+typically faster due to the applied early termination scheme.
*/
@@ -571,40 +559,4 @@
\image latex planar.eps "Plane graph" width=\textwidth
*/
-
-/**
-@defgroup tsp Traveling Salesman Problem
-@ingroup algs
-\brief Algorithms for the symmetric traveling salesman problem
-
-This group contains basic heuristic algorithms for the the symmetric
-\e traveling \e salesman \e problem (TSP).
-Given an \ref FullGraph "undirected full graph" with a cost map on its edges,
-the problem is to find a shortest possible tour that visits each node exactly
-once (i.e. the minimum cost Hamiltonian cycle).
-
-These TSP algorithms are intended to be used with a \e metric \e cost
-\e function, i.e. the edge costs should satisfy the triangle inequality.
-Otherwise the algorithms could yield worse results.
-
-LEMON provides five well-known heuristics for solving symmetric TSP:
- - \ref NearestNeighborTsp Neareast neighbor algorithm
- - \ref GreedyTsp Greedy algorithm
- - \ref InsertionTsp Insertion heuristic (with four selection methods)
- - \ref ChristofidesTsp Christofides algorithm
- - \ref Opt2Tsp 2-opt algorithm
-
-\ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest
-solution methods. Furthermore, \ref InsertionTsp is usually quite effective.
-
-\ref ChristofidesTsp is somewhat slower, but it has the best guaranteed
-approximation factor: 3/2.
-
-\ref Opt2Tsp usually provides the best results in practice, but
-it is the slowest method. It can also be used to improve given tours,
-for example, the results of other algorithms.
-
-\image html tsp.png
-\image latex tsp.eps "Traveling salesman problem" width=\textwidth
-*/
/**
@@ -648,6 +600,6 @@
high-level interface.
-The currently supported solvers are \cite glpk, \cite clp, \cite cbc,
-\cite cplex, \cite soplex.
+The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
+\ref cplex, \ref soplex.
*/
@@ -736,6 +688,4 @@
This group contains general \c EPS drawing methods and special
graph exporting tools.
-
-\image html graph_to_eps.png
*/
Index: c/images/adaptors1.eps
===================================================================
--- doc/images/adaptors1.eps (revision 1218)
+++ (revision )
@@ -1,303 +1,0 @@
-%!PS-Adobe-2.0 EPSF-2.0
-%%Title: adaptors1.fig
-%%Creator: fig2dev Version 3.2 Patchlevel 5
-%%CreationDate: Sun Feb 21 18:51:21 2010
-%%For: Peter@KOVACSPETER (Péter,U-KOVACSPETER\Peter,S-1-5-21-1774138250-1299389707-1938712334-1001)
-%%BoundingBox: 0 0 787 372
-%Magnification: 1.0000
-%%EndComments
-/$F2psDict 200 dict def
-$F2psDict begin
-$F2psDict /mtrx matrix put
-/col-1 {0 setgray} bind def
-/col0 {0.000 0.000 0.000 srgb} bind def
-/col1 {0.000 0.000 1.000 srgb} bind def
-/col2 {0.000 1.000 0.000 srgb} bind def
-/col3 {0.000 1.000 1.000 srgb} bind def
-/col4 {1.000 0.000 0.000 srgb} bind def
-/col5 {1.000 0.000 1.000 srgb} bind def
-/col6 {1.000 1.000 0.000 srgb} bind def
-/col7 {1.000 1.000 1.000 srgb} bind def
-/col8 {0.000 0.000 0.560 srgb} bind def
-/col9 {0.000 0.000 0.690 srgb} bind def
-/col10 {0.000 0.000 0.820 srgb} bind def
-/col11 {0.530 0.810 1.000 srgb} bind def
-/col12 {0.000 0.560 0.000 srgb} bind def
-/col13 {0.000 0.690 0.000 srgb} bind def
-/col14 {0.000 0.820 0.000 srgb} bind def
-/col15 {0.000 0.560 0.560 srgb} bind def
-/col16 {0.000 0.690 0.690 srgb} bind def
-/col17 {0.000 0.820 0.820 srgb} bind def
-/col18 {0.560 0.000 0.000 srgb} bind def
-/col19 {0.690 0.000 0.000 srgb} bind def
-/col20 {0.820 0.000 0.000 srgb} bind def
-/col21 {0.560 0.000 0.560 srgb} bind def
-/col22 {0.690 0.000 0.690 srgb} bind def
-/col23 {0.820 0.000 0.820 srgb} bind def
-/col24 {0.500 0.190 0.000 srgb} bind def
-/col25 {0.630 0.250 0.000 srgb} bind def
-/col26 {0.750 0.380 0.000 srgb} bind def
-/col27 {1.000 0.500 0.500 srgb} bind def
-/col28 {1.000 0.630 0.630 srgb} bind def
-/col29 {1.000 0.750 0.750 srgb} bind def
-/col30 {1.000 0.880 0.880 srgb} bind def
-/col31 {1.000 0.840 0.000 srgb} bind def
-
-end
-save
-newpath 0 372 moveto 0 0 lineto 787 0 lineto 787 372 lineto closepath clip newpath
--14.2 385.4 translate
-1 -1 scale
-
-/cp {closepath} bind def
-/ef {eofill} bind def
-/gr {grestore} bind def
-/gs {gsave} bind def
-/sa {save} bind def
-/rs {restore} bind def
-/l {lineto} bind def
-/m {moveto} bind def
-/rm {rmoveto} bind def
-/n {newpath} bind def
-/s {stroke} bind def
-/sh {show} bind def
-/slc {setlinecap} bind def
-/slj {setlinejoin} bind def
-/slw {setlinewidth} bind def
-/srgb {setrgbcolor} bind def
-/rot {rotate} bind def
-/sc {scale} bind def
-/sd {setdash} bind def
-/ff {findfont} bind def
-/sf {setfont} bind def
-/scf {scalefont} bind def
-/sw {stringwidth} bind def
-/tr {translate} bind def
-/tnt {dup dup currentrgbcolor
- 4 -2 roll dup 1 exch sub 3 -1 roll mul add
- 4 -2 roll dup 1 exch sub 3 -1 roll mul add
- 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb}
- bind def
-/shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul
- 4 -2 roll mul srgb} bind def
- /DrawEllipse {
- /endangle exch def
- /startangle exch def
- /yrad exch def
- /xrad exch def
- /y exch def
- /x exch def
- /savematrix mtrx currentmatrix def
- x y tr xrad yrad sc 0 0 1 startangle endangle arc
- closepath
- savematrix setmatrix
- } def
-
-/$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def
-/$F2psEnd {$F2psEnteredState restore end} def
-
-$F2psBegin
-10 setmiterlimit
-0 slj 0 slc
- 0.06299 0.06299 sc
-%
-% Fig objects follow
-%
-%
-% here starts figure with depth 60
-% Polyline
-0 slj
-0 slc
-15.000 slw
-gs clippath
-6319 5229 m 6442 5564 l 6527 5533 l 6403 5198 l 6403 5198 l 6424 5383 l 6319 5229 l cp
-eoclip
-n 5850 3825 m
- 6480 5535 l gs col0 s gr gr
-
-% arrowhead
-75.000 slw
-n 6319 5229 m 6424 5383 l 6403 5198 l 6319 5229 l cp gs 0.00 setgray ef gr col0 s
-% Polyline
-15.000 slw
-gs clippath
-5417 4044 m 5746 3905 l 5711 3822 l 5382 3961 l 5382 3961 l 5566 3933 l 5417 4044 l cp
-eoclip
-n 1575 5625 m
- 5715 3870 l gs col0 s gr gr
-
-% arrowhead
-75.000 slw
-n 5417 4044 m 5566 3933 l 5382 3961 l 5417 4044 l cp gs 0.00 setgray ef gr col0 s
-% Polyline
-15.000 slw
-gs clippath
-3897 3780 m 3540 3780 l 3540 3870 l 3897 3870 l 3897 3870 l 3717 3825 l 3897 3780 l cp
-eoclip
-n 5625 3825 m
- 3555 3825 l gs col0 s gr gr
-
-% arrowhead
-75.000 slw
-n 3897 3780 m 3717 3825 l 3897 3870 l 3897 3780 l cp gs 0.00 setgray ef gr col0 s
-% Polyline
-15.000 slw
-gs clippath
-3075 4188 m 3327 3936 l 3263 3872 l 3011 4124 l 3011 4124 l 3171 4029 l 3075 4188 l cp
-eoclip
-n 1575 5625 m
- 3285 3915 l gs col0 s gr gr
-
-% arrowhead
-75.000 slw
-n 3075 4188 m 3171 4029 l 3011 4124 l 3075 4188 l cp gs 0.00 setgray ef gr col0 s
-% Polyline
-15.000 slw
-gs clippath
-3528 2520 m 3885 2520 l 3885 2430 l 3528 2430 l 3528 2430 l 3708 2475 l 3528 2520 l cp
-eoclip
-n 1800 2475 m
- 3870 2475 l gs col0 s gr gr
-
-% arrowhead
-75.000 slw
-n 3528 2520 m 3708 2475 l 3528 2430 l 3528 2520 l cp gs 0.00 setgray ef gr col0 s
-% Polyline
-15.000 slw
-gs clippath
-4304 2156 m 4052 2408 l 4116 2472 l 4368 2220 l 4368 2220 l 4209 2316 l 4304 2156 l cp
-eoclip
-n 5850 675 m
- 4095 2430 l gs col0 s gr gr
-
-% arrowhead
-75.000 slw
-n 4304 2156 m 4209 2316 l 4368 2220 l 4304 2156 l cp gs 0.00 setgray ef gr col0 s
-% Polyline
-15.000 slw
-gs clippath
-6319 2079 m 6442 2414 l 6527 2383 l 6403 2048 l 6403 2048 l 6424 2233 l 6319 2079 l cp
-eoclip
-n 5850 675 m
- 6480 2385 l gs col0 s gr gr
-
-% arrowhead
-75.000 slw
-n 6319 2079 m 6424 2233 l 6403 2048 l 6319 2079 l cp gs 0.00 setgray ef gr col0 s
-% Polyline
-15.000 slw
-gs clippath
-5417 894 m 5746 755 l 5711 672 l 5382 811 l 5382 811 l 5566 783 l 5417 894 l cp
-eoclip
-n 1575 2475 m
- 5715 720 l gs col0 s gr gr
-
-% arrowhead
-75.000 slw
-n 5417 894 m 5566 783 l 5382 811 l 5417 894 l cp gs 0.00 setgray ef gr col0 s
-% Polyline
-15.000 slw
-gs clippath
-3528 5670 m 3885 5670 l 3885 5580 l 3528 5580 l 3528 5580 l 3708 5625 l 3528 5670 l cp
-eoclip
-n 1800 5625 m
- 3870 5625 l gs col0 s gr gr
-
-% arrowhead
-75.000 slw
-n 3528 5670 m 3708 5625 l 3528 5580 l 3528 5670 l cp gs 0.00 setgray ef gr col0 s
-% Polyline
-15.000 slw
-gs clippath
-4572 5580 m 4215 5580 l 4215 5670 l 4572 5670 l 4572 5670 l 4392 5625 l 4572 5580 l cp
-eoclip
-n 6300 5625 m
- 4230 5625 l gs col0 s gr gr
-
-% arrowhead
-75.000 slw
-n 4572 5580 m 4392 5625 l 4572 5670 l 4572 5580 l cp gs 0.00 setgray ef gr col0 s
-% Polyline
-15.000 slw
-gs clippath
-4304 5306 m 4052 5558 l 4116 5622 l 4368 5370 l 4368 5370 l 4209 5466 l 4304 5306 l cp
-eoclip
-n 5850 3825 m
- 4095 5580 l gs col0 s gr gr
-
-% arrowhead
-75.000 slw
-n 4304 5306 m 4209 5466 l 4368 5370 l 4304 5306 l cp gs 0.00 setgray ef gr col0 s
-% here ends figure;
-%
-% here starts figure with depth 50
-% Ellipse
-15.000 slw
-n 3375 3825 225 112 0 360 DrawEllipse gs 1.00 setgray ef gr gs col0 s gr
-
-% Ellipse
-n 5850 3825 225 112 0 360 DrawEllipse gs 1.00 setgray ef gr gs col0 s gr
-
-% Polyline
-0 slj
-0 slc
-n 247 2947 m 2947 247 l 9697 247 l 6997 2947 l
- 247 2947 l cp gs col0 s gr
-% Polyline
-n 247 6097 m 2947 3397 l 9697 3397 l 6997 6097 l
- 247 6097 l cp gs col0 s gr
-% Ellipse
-n 1575 2475 225 112 0 360 DrawEllipse gs 1.00 setgray ef gr gs col0 s gr
-
-% Ellipse
-n 4050 2475 225 112 0 360 DrawEllipse gs 1.00 setgray ef gr gs col0 s gr
-
-% Ellipse
-n 6525 2475 225 112 0 360 DrawEllipse gs 1.00 setgray ef gr gs col0 s gr
-
-% Ellipse
-n 5850 675 225 112 0 360 DrawEllipse gs 1.00 setgray ef gr gs col0 s gr
-
-% Ellipse
-n 1575 5625 225 112 0 360 DrawEllipse gs 1.00 setgray ef gr gs col0 s gr
-
-% Ellipse
-n 4050 5625 225 112 0 360 DrawEllipse gs 1.00 setgray ef gr gs col0 s gr
-
-% Ellipse
-n 6525 5625 225 112 0 360 DrawEllipse gs 1.00 setgray ef gr gs col0 s gr
-
-% here ends figure;
-%
-% here starts figure with depth 40
-/Helvetica ff 480.00 scf sf
-8280 2610 m
-gs 1 -1 sc (SubDigraph adaptor) col0 sh gr
-% Polyline
-0 slj
-0 slc
-7.500 slw
- [15 45] 45 sd
-n 4050 2610 m
- 4050 5625 l gs col0 s gr [] 0 sd
-% Polyline
- [15 45] 45 sd
-n 5850 810 m
- 5850 3825 l gs col0 s gr [] 0 sd
-% Polyline
- [15 45] 45 sd
-n 6525 2610 m
- 6525 5625 l gs col0 s gr [] 0 sd
-/Helvetica ff 480.00 scf sf
-8280 5760 m
-gs 1 -1 sc (Original digraph) col0 sh gr
-% Polyline
- [15 45] 45 sd
-n 1575 2610 m
- 1575 5625 l gs col0 s gr [] 0 sd
-% here ends figure;
-$F2psEnd
-rs
-showpage
-%%Trailer
-%EOF
Index: c/images/adaptors2.eps
===================================================================
--- doc/images/adaptors2.eps (revision 1218)
+++ (revision )
@@ -1,349 +1,0 @@
-%!PS-Adobe-2.0 EPSF-2.0
-%%Title: adaptors2.fig
-%%Creator: fig2dev Version 3.2 Patchlevel 5
-%%CreationDate: Sun Feb 21 18:51:31 2010
-%%For: Peter@KOVACSPETER (Péter,U-KOVACSPETER\Peter,S-1-5-21-1774138250-1299389707-1938712334-1001)
-%%BoundingBox: 0 0 787 570
-%Magnification: 1.0000
-%%EndComments
-/$F2psDict 200 dict def
-$F2psDict begin
-$F2psDict /mtrx matrix put
-/col-1 {0 setgray} bind def
-/col0 {0.000 0.000 0.000 srgb} bind def
-/col1 {0.000 0.000 1.000 srgb} bind def
-/col2 {0.000 1.000 0.000 srgb} bind def
-/col3 {0.000 1.000 1.000 srgb} bind def
-/col4 {1.000 0.000 0.000 srgb} bind def
-/col5 {1.000 0.000 1.000 srgb} bind def
-/col6 {1.000 1.000 0.000 srgb} bind def
-/col7 {1.000 1.000 1.000 srgb} bind def
-/col8 {0.000 0.000 0.560 srgb} bind def
-/col9 {0.000 0.000 0.690 srgb} bind def
-/col10 {0.000 0.000 0.820 srgb} bind def
-/col11 {0.530 0.810 1.000 srgb} bind def
-/col12 {0.000 0.560 0.000 srgb} bind def
-/col13 {0.000 0.690 0.000 srgb} bind def
-/col14 {0.000 0.820 0.000 srgb} bind def
-/col15 {0.000 0.560 0.560 srgb} bind def
-/col16 {0.000 0.690 0.690 srgb} bind def
-/col17 {0.000 0.820 0.820 srgb} bind def
-/col18 {0.560 0.000 0.000 srgb} bind def
-/col19 {0.690 0.000 0.000 srgb} bind def
-/col20 {0.820 0.000 0.000 srgb} bind def
-/col21 {0.560 0.000 0.560 srgb} bind def
-/col22 {0.690 0.000 0.690 srgb} bind def
-/col23 {0.820 0.000 0.820 srgb} bind def
-/col24 {0.500 0.190 0.000 srgb} bind def
-/col25 {0.630 0.250 0.000 srgb} bind def
-/col26 {0.750 0.380 0.000 srgb} bind def
-/col27 {1.000 0.500 0.500 srgb} bind def
-/col28 {1.000 0.630 0.630 srgb} bind def
-/col29 {1.000 0.750 0.750 srgb} bind def
-/col30 {1.000 0.880 0.880 srgb} bind def
-/col31 {1.000 0.840 0.000 srgb} bind def
-
-end
-save
-newpath 0 570 moveto 0 0 lineto 787 0 lineto 787 570 lineto closepath clip newpath
--14.2 583.9 translate
-1 -1 scale
-
-/cp {closepath} bind def
-/ef {eofill} bind def
-/gr {grestore} bind def
-/gs {gsave} bind def
-/sa {save} bind def
-/rs {restore} bind def
-/l {lineto} bind def
-/m {moveto} bind def
-/rm {rmoveto} bind def
-/n {newpath} bind def
-/s {stroke} bind def
-/sh {show} bind def
-/slc {setlinecap} bind def
-/slj {setlinejoin} bind def
-/slw {setlinewidth} bind def
-/srgb {setrgbcolor} bind def
-/rot {rotate} bind def
-/sc {scale} bind def
-/sd {setdash} bind def
-/ff {findfont} bind def
-/sf {setfont} bind def
-/scf {scalefont} bind def
-/sw {stringwidth} bind def
-/tr {translate} bind def
-/tnt {dup dup currentrgbcolor
- 4 -2 roll dup 1 exch sub 3 -1 roll mul add
- 4 -2 roll dup 1 exch sub 3 -1 roll mul add
- 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb}
- bind def
-/shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul
- 4 -2 roll mul srgb} bind def
- /DrawEllipse {
- /endangle exch def
- /startangle exch def
- /yrad exch def
- /xrad exch def
- /y exch def
- /x exch def
- /savematrix mtrx currentmatrix def
- x y tr xrad yrad sc 0 0 1 startangle endangle arc
- closepath
- savematrix setmatrix
- } def
-
-/$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def
-/$F2psEnd {$F2psEnteredState restore end} def
-
-$F2psBegin
-10 setmiterlimit
-0 slj 0 slc
- 0.06299 0.06299 sc
-%
-% Fig objects follow
-%
-%
-% here starts figure with depth 60
-% Polyline
-0 slj
-0 slc
-15.000 slw
-gs clippath
-5417 4044 m 5746 3905 l 5711 3822 l 5382 3961 l 5382 3961 l 5566 3933 l 5417 4044 l cp
-eoclip
-n 1575 5625 m
- 5715 3870 l gs col0 s gr gr
-
-% arrowhead
-75.000 slw
-n 5417 4044 m 5566 3933 l 5382 3961 l 5417 4044 l cp gs 0.00 setgray ef gr col0 s
-% Polyline
-15.000 slw
-gs clippath
-5417 7194 m 5746 7055 l 5711 6972 l 5382 7111 l 5382 7111 l 5566 7083 l 5417 7194 l cp
-eoclip
-n 1575 8775 m
- 5715 7020 l gs col0 s gr gr
-
-% arrowhead
-75.000 slw
-n 5417 7194 m 5566 7083 l 5382 7111 l 5417 7194 l cp gs 0.00 setgray ef gr col0 s
-% Polyline
-15.000 slw
-gs clippath
-6319 8379 m 6442 8714 l 6527 8683 l 6403 8348 l 6403 8348 l 6424 8533 l 6319 8379 l cp
-eoclip
-n 5850 6975 m
- 6480 8685 l gs col0 s gr gr
-
-% arrowhead
-75.000 slw
-n 6319 8379 m 6424 8533 l 6403 8348 l 6319 8379 l cp gs 0.00 setgray ef gr col0 s
-% Polyline
-15.000 slw
-gs clippath
-4304 8456 m 4052 8708 l 4116 8772 l 4368 8520 l 4368 8520 l 4209 8616 l 4304 8456 l cp
-eoclip
-n 5850 6975 m
- 4095 8730 l gs col0 s gr gr
-
-% arrowhead
-75.000 slw
-n 4304 8456 m 4209 8616 l 4368 8520 l 4304 8456 l cp gs 0.00 setgray ef gr col0 s
-% Polyline
-15.000 slw
-gs clippath
-4572 8730 m 4215 8730 l 4215 8820 l 4572 8820 l 4572 8820 l 4392 8775 l 4572 8730 l cp
-eoclip
-n 6300 8775 m
- 4230 8775 l gs col0 s gr gr
-
-% arrowhead
-75.000 slw
-n 4572 8730 m 4392 8775 l 4572 8820 l 4572 8730 l cp gs 0.00 setgray ef gr col0 s
-% Polyline
-15.000 slw
-gs clippath
-3528 8820 m 3885 8820 l 3885 8730 l 3528 8730 l 3528 8730 l 3708 8775 l 3528 8820 l cp
-eoclip
-n 1800 8775 m
- 3870 8775 l gs col0 s gr gr
-
-% arrowhead
-75.000 slw
-n 3528 8820 m 3708 8775 l 3528 8730 l 3528 8820 l cp gs 0.00 setgray ef gr col0 s
-% Polyline
-15.000 slw
-n 1800 2475 m
- 3870 2475 l gs col0 s gr
-% Polyline
-n 1575 2475 m
- 5715 720 l gs col0 s gr
-% Polyline
-n 5850 675 m
- 4095 2430 l gs col0 s gr
-% Polyline
-n 5850 675 m
- 6480 2385 l gs col0 s gr
-% Polyline
-gs clippath
-3075 7338 m 3327 7086 l 3263 7022 l 3011 7274 l 3011 7274 l 3171 7179 l 3075 7338 l cp
-eoclip
-n 1575 8775 m
- 3285 7065 l gs col0 s gr gr
-
-% arrowhead
-75.000 slw
-n 3075 7338 m 3171 7179 l 3011 7274 l 3075 7338 l cp gs 0.00 setgray ef gr col0 s
-% Polyline
-15.000 slw
-gs clippath
-3528 5670 m 3885 5670 l 3885 5580 l 3528 5580 l 3528 5580 l 3708 5625 l 3528 5670 l cp
-eoclip
-n 1800 5625 m
- 3870 5625 l gs col0 s gr gr
-
-% arrowhead
-75.000 slw
-n 3528 5670 m 3708 5625 l 3528 5580 l 3528 5670 l cp gs 0.00 setgray ef gr col0 s
-% Polyline
-15.000 slw
-gs clippath
-4304 5306 m 4052 5558 l 4116 5622 l 4368 5370 l 4368 5370 l 4209 5466 l 4304 5306 l cp
-eoclip
-n 5850 3825 m
- 4095 5580 l gs col0 s gr gr
-
-% arrowhead
-75.000 slw
-n 4304 5306 m 4209 5466 l 4368 5370 l 4304 5306 l cp gs 0.00 setgray ef gr col0 s
-% Polyline
-15.000 slw
-gs clippath
-6319 5229 m 6442 5564 l 6527 5533 l 6403 5198 l 6403 5198 l 6424 5383 l 6319 5229 l cp
-eoclip
-n 5850 3825 m
- 6480 5535 l gs col0 s gr gr
-
-% arrowhead
-75.000 slw
-n 6319 5229 m 6424 5383 l 6403 5198 l 6319 5229 l cp gs 0.00 setgray ef gr col0 s
-% Polyline
-15.000 slw
-gs clippath
-3897 6930 m 3540 6930 l 3540 7020 l 3897 7020 l 3897 7020 l 3717 6975 l 3897 6930 l cp
-eoclip
-n 5625 6975 m
- 3555 6975 l gs col0 s gr gr
-
-% arrowhead
-75.000 slw
-n 3897 6930 m 3717 6975 l 3897 7020 l 3897 6930 l cp gs 0.00 setgray ef gr col0 s
-% here ends figure;
-%
-% here starts figure with depth 50
-% Polyline
-0 slj
-0 slc
-15.000 slw
-n 247 6097 m 2947 3397 l 9697 3397 l 6997 6097 l
- 247 6097 l cp gs col0 s gr
-% Polyline
-n 247 9247 m 2947 6547 l 9697 6547 l 6997 9247 l
- 247 9247 l cp gs col0 s gr
-% Ellipse
-n 4050 2475 225 112 0 360 DrawEllipse gs 1.00 setgray ef gr gs col0 s gr
-
-% Ellipse
-n 6525 2475 225 112 0 360 DrawEllipse gs 1.00 setgray ef gr gs col0 s gr
-
-% Ellipse
-n 1575 2475 225 112 0 360 DrawEllipse gs 1.00 setgray ef gr gs col0 s gr
-
-% Ellipse
-n 5850 675 225 112 0 360 DrawEllipse gs 1.00 setgray ef gr gs col0 s gr
-
-% Ellipse
-n 1575 5625 225 112 0 360 DrawEllipse gs 1.00 setgray ef gr gs col0 s gr
-
-% Ellipse
-n 4050 5625 225 112 0 360 DrawEllipse gs 1.00 setgray ef gr gs col0 s gr
-
-% Ellipse
-n 6525 5625 225 112 0 360 DrawEllipse gs 1.00 setgray ef gr gs col0 s gr
-
-% Ellipse
-n 5850 3825 225 112 0 360 DrawEllipse gs 1.00 setgray ef gr gs col0 s gr
-
-% Ellipse
-n 1575 8775 225 112 0 360 DrawEllipse gs 1.00 setgray ef gr gs col0 s gr
-
-% Ellipse
-n 4050 8775 225 112 0 360 DrawEllipse gs 1.00 setgray ef gr gs col0 s gr
-
-% Ellipse
-n 3375 6975 225 112 0 360 DrawEllipse gs 1.00 setgray ef gr gs col0 s gr
-
-% Ellipse
-n 6525 8775 225 112 0 360 DrawEllipse gs 1.00 setgray ef gr gs col0 s gr
-
-% Ellipse
-n 5850 6975 225 112 0 360 DrawEllipse gs 1.00 setgray ef gr gs col0 s gr
-
-% Polyline
-n 247 2947 m 2947 247 l 9697 247 l 6997 2947 l
- 247 2947 l cp gs col0 s gr
-% here ends figure;
-%
-% here starts figure with depth 40
-/Helvetica ff 480.00 scf sf
-8280 8910 m
-gs 1 -1 sc (Original digraph) col0 sh gr
-% Polyline
-0 slj
-0 slc
-7.500 slw
- [15 45] 45 sd
-n 5850 810 m
- 5850 3825 l gs col0 s gr [] 0 sd
-% Polyline
- [15 45] 45 sd
-n 6525 2610 m
- 6525 5625 l gs col0 s gr [] 0 sd
-% Polyline
- [15 45] 45 sd
-n 4050 2610 m
- 4050 5625 l gs col0 s gr [] 0 sd
-% Polyline
- [15 45] 45 sd
-n 1575 2610 m
- 1575 5625 l gs col0 s gr [] 0 sd
-% Polyline
- [15 45] 45 sd
-n 5850 3960 m
- 5850 6975 l gs col0 s gr [] 0 sd
-% Polyline
- [15 45] 45 sd
-n 6525 5760 m
- 6525 8775 l gs col0 s gr [] 0 sd
-% Polyline
- [15 45] 45 sd
-n 4050 5760 m
- 4050 8775 l gs col0 s gr [] 0 sd
-/Helvetica ff 480.00 scf sf
-8280 2610 m
-gs 1 -1 sc (Undirector adaptor) col0 sh gr
-/Helvetica ff 480.00 scf sf
-8280 5760 m
-gs 1 -1 sc (SubDigraph adaptor) col0 sh gr
-% Polyline
- [15 45] 45 sd
-n 1575 5760 m
- 1575 8775 l gs col0 s gr [] 0 sd
-% here ends figure;
-$F2psEnd
-rs
-showpage
-%%Trailer
-%EOF
Index: doc/images/bipartite_partitions.eps
===================================================================
--- doc/images/bipartite_partitions.eps (revision 1213)
+++ doc/images/bipartite_partitions.eps (revision 634)
@@ -1,5 +1,5 @@
%!PS-Adobe-2.0 EPSF-2.0
%%Creator: LEMON, graphToEps()
-%%CreationDate: Fri Mar 8 00:18:43 2013
+%%CreationDate: Tue Nov 15 16:51:43 2005
%%BoundingBox: 0 0 842 596
%%EndComments
@@ -54,60 +54,60 @@
%Edges:
gsave
-513.857 -446.322 296.569 -487.43 79.2808 -528.539 0 0 0 7.00153 lb
-513.857 -446.322 575.52 -315.656 637.183 -184.989 0 0 0 7.00153 lb
-393.468 566.711 494.771 434.577 596.074 302.442 0 0 0 7.00153 lb
-393.468 566.711 155.625 579.925 -82.2171 593.138 0 0 0 7.00153 lb
-393.468 566.711 251.056 450.726 108.644 334.741 0 0 0 7.00153 lb
-869.153 52.8539 732.613 177.648 596.074 302.442 0 0 0 7.00153 lb
-869.153 52.8539 753.168 -66.0676 637.183 -184.989 0 0 0 7.00153 lb
--82.2171 593.138 -91.0261 346.487 -99.8351 99.8351 0 0 0 7.00153 lb
--663.61 546.157 -753.168 394.936 -842.726 243.715 0 0 0 7.00153 lb
--663.61 546.157 -574.052 437.513 -484.494 328.869 0 0 0 7.00153 lb
--1077.63 161.498 -960.178 202.606 -842.726 243.715 0 0 0 7.00153 lb
--1077.63 161.498 -968.987 66.0674 -860.344 -29.3633 0 0 0 7.00153 lb
--1177.47 -234.906 -1029.18 -381.722 -880.898 -528.539 0 0 0 7.00153 lb
--1177.47 -234.906 -1018.91 -132.135 -860.344 -29.3633 0 0 0 7.00153 lb
--880.898 -528.539 -744.359 -387.595 -607.82 -246.651 0 0 0 7.00153 lb
--499.175 -499.175 -355.295 -475.685 -211.415 -452.194 0 0 0 7.00153 lb
--499.175 -499.175 -553.498 -372.913 -607.82 -246.651 0 0 0 7.00153 lb
--499.175 -499.175 -386.587 -315.087 -274 -131 0 0 0 7.00153 lb
-79.2808 -528.539 -66.0671 -490.366 -211.415 -452.194 0 0 0 7.00153 lb
-637.183 -184.989 421.363 -253.993 205.543 -322.996 0 0 0 7.00153 lb
-205.543 -322.996 162.966 -226.097 120.389 -129.198 0 0 0 7.00153 lb
-399.34 88.0898 259.865 -20.5541 120.389 -129.198 0 0 0 7.00153 lb
-399.34 88.0898 253.992 211.415 108.644 334.741 0 0 0 7.00153 lb
--842.726 243.715 -471.281 171.775 -99.8351 99.8351 0 0 0 7.00153 lb
--842.726 243.715 -558.363 56.3575 -274 -131 0 0 0 7.00153 lb
--860.344 -29.3633 -734.082 -138.007 -607.82 -246.651 0 0 0 7.00153 lb
--211.415 -452.194 -45.513 -290.696 120.389 -129.198 0 0 0 7.00153 lb
--99.8351 99.8351 4.40445 217.288 108.644 334.741 0 0 0 7.00153 lb
--99.8351 99.8351 -292.165 214.352 -484.494 328.869 0 0 0 7.00153 lb
-120.389 -129.198 -76.8055 -130.099 -274 -131 0 0 0 7.00153 lb
+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 23.3384 1 0 0 nc
--607.82 -246.651 23.3384 1 0 0 nc
--484.494 328.869 23.3384 0 0 1 nc
-108.644 334.741 23.3384 0 0 1 nc
-120.389 -129.198 23.3384 0 0 1 nc
--99.8351 99.8351 23.3384 1 0 0 nc
--211.415 -452.194 23.3384 1 0 0 nc
--860.344 -29.3633 23.3384 0 0 1 nc
--842.726 243.715 23.3384 0 0 1 nc
-399.34 88.0898 23.3384 1 0 0 nc
-205.543 -322.996 23.3384 1 0 0 nc
-637.183 -184.989 23.3384 0 0 1 nc
-79.2808 -528.539 23.3384 0 0 1 nc
--499.175 -499.175 23.3384 0 0 1 nc
--880.898 -528.539 23.3384 0 0 1 nc
--1177.47 -234.906 23.3384 1 0 0 nc
--1077.63 161.498 23.3384 1 0 0 nc
--663.61 546.157 23.3384 1 0 0 nc
--82.2171 593.138 23.3384 0 0 1 nc
-596.074 302.442 23.3384 0 0 1 nc
-869.153 52.8539 23.3384 1 0 0 nc
-393.468 566.711 23.3384 1 0 0 nc
-513.857 -446.322 23.3384 1 0 0 nc
+-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
Index: doc/images/connected_components.eps
===================================================================
--- doc/images/connected_components.eps (revision 1213)
+++ doc/images/connected_components.eps (revision 634)
@@ -1,5 +1,5 @@
%!PS-Adobe-2.0 EPSF-2.0
%%Creator: LEMON, graphToEps()
-%%CreationDate: Fri Mar 8 00:18:43 2013
+%%CreationDate: Fri Nov 4 13:47:12 2005
%%BoundingBox: 0 0 842 596
%%EndComments
@@ -54,105 +54,105 @@
%Edges:
gsave
-574.035 177.301 622.149 225.748 670.264 274.195 0 0 0 6.25356 lb
-694.579 115.483 682.421 194.839 670.264 274.195 0 0 0 6.25356 lb
-280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 0 6.25356 lb
-280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 0 6.25356 lb
-212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 0 6.25356 lb
-286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 0 6.25356 lb
-286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 0 6.25356 lb
-438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 0 6.25356 lb
-438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 0 6.25356 lb
-397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 0 6.25356 lb
-366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 0 6.25356 lb
-271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 0 6.25356 lb
-271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 0 6.25356 lb
-277.311 -252.33 241.766 -229.149 206.221 -205.967 0 0 0 6.25356 lb
--840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0 0 6.25356 lb
--579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0 6.25356 lb
--579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0 6.25356 lb
--767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0 6.25356 lb
-906.312 201.403 946.592 42.798 986.873 -115.807 0 0 0 6.25356 lb
-906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 0 6.25356 lb
-986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 0 6.25356 lb
--470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0 0 0 6.25356 lb
-422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 0 6.25356 lb
-422.945 521.129 376.371 417.911 329.797 314.692 0 0 0 6.25356 lb
-422.945 521.129 474.554 276.928 526.164 32.7279 0 0 0 6.25356 lb
--5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 0 6.25356 lb
-329.797 314.692 130.912 317.209 -67.9734 319.727 0 0 0 6.25356 lb
--67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 0 6.25356 lb
-762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 0 6.25356 lb
-762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 0 6.25356 lb
-526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 0 6.25356 lb
-730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 0 6.25356 lb
-415.393 -289.516 173.71 -318.468 -67.9734 -347.42 0 0 0 6.25356 lb
--67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 0 6.25356 lb
--67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 0 6.25356 lb
--309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 0 6.25356 lb
--323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 0 6.25356 lb
--26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 0 6.25356 lb
--26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 0 6.25356 lb
--26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 0 6.25356 lb
--26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 0 6.25356 lb
-116.407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 0 6.25356 lb
--262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 0 6.25356 lb
--262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 0 6.25356 lb
--13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 0 6.25356 lb
--180.397 245.045 -113.509 338.465 -132.697 451.748 0 0 0 6.25356 lb
--180.397 245.045 -199.585 358.328 -132.697 451.748 0 0 0 6.25356 lb
--416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 0 6.25356 lb
--416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 0 6.25356 lb
--132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 0 6.25356 lb
-670.264 274.195 629.188 409.347 588.113 544.499 0 0 0 6.25356 lb
-670.264 274.195 797.466 341.771 924.667 409.347 0 0 0 6.25356 lb
-588.113 544.499 756.39 476.923 924.667 409.347 0 0 0 6.25356 lb
--689.204 -237.261 -587.735 -114.393 -567.302 43.6423 0 0 0 6.25356 lb
--689.204 -237.261 -668.771 -79.2259 -567.302 43.6423 0 0 0 6.25356 lb
+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.8452 0 0 0 nc
--689.204 -237.261 20.8452 0 0 0 nc
-924.667 409.347 20.8452 1 0 0 nc
-588.113 544.499 20.8452 1 0 0 nc
-670.264 274.195 20.8452 1 0 0 nc
--371.2 568.349 20.8452 0 1 0 nc
--132.697 451.748 20.8452 0 1 0 nc
--416.25 345.746 20.8452 0 1 0 nc
--180.397 245.045 20.8452 0 1 0 nc
--13.4452 133.743 20.8452 0 1 0 nc
--262.548 107.243 20.8452 0 1 0 nc
-201.208 38.3422 20.8452 0 1 0 nc
-116.407 -173.66 20.8452 0 1 0 nc
--26.6953 -19.9585 20.8452 0 1 0 nc
--539.894 -262.64 20.8452 0 0 1 nc
--323.543 -433.964 20.8452 0 0 1 nc
--309.657 -57.9033 20.8452 0 0 1 nc
--67.9734 -347.42 20.8452 0 0 1 nc
-415.393 -289.516 20.8452 0 0 1 nc
-730.084 -307.139 20.8452 0 0 1 nc
-526.164 32.7279 20.8452 0 0 1 nc
-762.812 -17.6227 20.8452 0 0 1 nc
--67.9734 319.727 20.8452 0 0 1 nc
-329.797 314.692 20.8452 0 0 1 nc
--5.03507 561.41 20.8452 0 0 1 nc
-422.945 521.129 20.8452 0 0 1 nc
--470.779 158.605 20.8452 0 0 1 nc
-986.873 -115.807 20.8452 0 0 1 nc
-906.312 201.403 20.8452 0 0 1 nc
--767.847 113.289 20.8452 0 0 1 nc
--579.033 445.603 20.8452 0 0 1 nc
--840.856 -246.718 20.8452 0 0 1 nc
-206.221 -205.967 20.8452 1 1 0 nc
-277.311 -252.33 20.8452 1 1 0 nc
-271.13 -175.058 20.8452 1 1 0 nc
-366.947 -110.15 20.8452 1 1 0 nc
-397.855 -196.694 20.8452 1 1 0 nc
-438.037 -88.514 20.8452 1 1 0 nc
-286.584 -48.3327 20.8452 1 1 0 nc
-212.403 -23.6057 20.8452 1 1 0 nc
-280.402 10.3938 20.8452 1 1 0 nc
-694.579 115.483 20.8452 1 0 0 nc
-574.035 177.301 20.8452 1 0 0 nc
+-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
Index: doc/images/edge_biconnected_components.eps
===================================================================
--- doc/images/edge_biconnected_components.eps (revision 1213)
+++ doc/images/edge_biconnected_components.eps (revision 634)
@@ -1,5 +1,5 @@
%!PS-Adobe-2.0 EPSF-2.0
%%Creator: LEMON, graphToEps()
-%%CreationDate: Fri Mar 8 00:18:43 2013
+%%CreationDate: Fri Nov 4 13:47:12 2005
%%BoundingBox: 0 0 842 596
%%EndComments
@@ -54,105 +54,105 @@
%Edges:
gsave
-574.035 177.301 622.149 225.748 670.264 274.195 1 0 0 6.25356 lb
-694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 6.25356 lb
-280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 1 6.25356 lb
-280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 1 6.25356 lb
-212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 1 6.25356 lb
-286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 1 6.25356 lb
-286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 1 6.25356 lb
-438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 1 6.25356 lb
-438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 1 6.25356 lb
-397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 1 6.25356 lb
-366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 1 6.25356 lb
-271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 1 6.25356 lb
-271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 1 6.25356 lb
-277.311 -252.33 241.766 -229.149 206.221 -205.967 0 0 1 6.25356 lb
--840.856 -246.718 -804.351 -66.7145 -767.847 113.289 1 0 0 6.25356 lb
--579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 1 6.25356 lb
--579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 1 6.25356 lb
--767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 1 6.25356 lb
-906.312 201.403 946.592 42.798 986.873 -115.807 0 0 1 6.25356 lb
-906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 1 6.25356 lb
-986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 1 6.25356 lb
--470.779 158.605 -390.218 50.3508 -309.657 -57.9033 1 0 0 6.25356 lb
-422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 1 6.25356 lb
-422.945 521.129 376.371 417.911 329.797 314.692 0 0 1 6.25356 lb
-422.945 521.129 474.554 276.928 526.164 32.7279 0 0 1 6.25356 lb
--5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 1 6.25356 lb
-329.797 314.692 130.912 317.209 -67.9734 319.727 0 0 1 6.25356 lb
--67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 1 6.25356 lb
-762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 1 6.25356 lb
-762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 1 6.25356 lb
-526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 1 6.25356 lb
-730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 1 6.25356 lb
-415.393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0 0 6.25356 lb
--67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 1 6.25356 lb
--67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 1 6.25356 lb
--309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 1 6.25356 lb
--323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 1 6.25356 lb
--26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 1 6.25356 lb
--26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 1 6.25356 lb
--26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 1 6.25356 lb
--26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 1 6.25356 lb
-116.407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 1 6.25356 lb
--262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 1 6.25356 lb
--262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 1 6.25356 lb
--13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 1 6.25356 lb
--180.397 245.045 -113.509 338.465 -132.697 451.748 0 0 1 6.25356 lb
--180.397 245.045 -199.585 358.328 -132.697 451.748 0 0 1 6.25356 lb
--416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 1 6.25356 lb
--416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 1 6.25356 lb
--132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 1 6.25356 lb
-670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 6.25356 lb
-670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 6.25356 lb
-588.113 544.499 756.39 476.923 924.667 409.347 0 0 1 6.25356 lb
--689.204 -237.261 -587.735 -114.393 -567.302 43.6423 0 0 1 6.25356 lb
--689.204 -237.261 -668.771 -79.2259 -567.302 43.6423 0 0 1 6.25356 lb
+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.8452 0 0 0 nc
--689.204 -237.261 20.8452 0 0 0 nc
-924.667 409.347 20.8452 0 0 1 nc
-588.113 544.499 20.8452 0 0 1 nc
-670.264 274.195 20.8452 0 0 1 nc
--371.2 568.349 20.8452 1 1 0 nc
--132.697 451.748 20.8452 1 1 0 nc
--416.25 345.746 20.8452 1 1 0 nc
--180.397 245.045 20.8452 1 1 0 nc
--13.4452 133.743 20.8452 1 1 0 nc
--262.548 107.243 20.8452 1 1 0 nc
-201.208 38.3422 20.8452 1 1 0 nc
-116.407 -173.66 20.8452 1 1 0 nc
--26.6953 -19.9585 20.8452 1 1 0 nc
--539.894 -262.64 20.8452 0 0.5 0 nc
--323.543 -433.964 20.8452 0 0.5 0 nc
--309.657 -57.9033 20.8452 0 0.5 0 nc
--67.9734 -347.42 20.8452 0 0.5 0 nc
-415.393 -289.516 20.8452 0.5 0 0 nc
-730.084 -307.139 20.8452 0.5 0 0 nc
-526.164 32.7279 20.8452 0.5 0 0 nc
-762.812 -17.6227 20.8452 0.5 0 0 nc
--67.9734 319.727 20.8452 0.5 0 0 nc
-329.797 314.692 20.8452 0.5 0 0 nc
--5.03507 561.41 20.8452 0.5 0 0 nc
-422.945 521.129 20.8452 0.5 0 0 nc
--470.779 158.605 20.8452 0 1 1 nc
-986.873 -115.807 20.8452 0.5 0 0 nc
-906.312 201.403 20.8452 0.5 0 0 nc
--767.847 113.289 20.8452 0 1 1 nc
--579.033 445.603 20.8452 0 1 1 nc
--840.856 -246.718 20.8452 1 0 1 nc
-206.221 -205.967 20.8452 0 0 0.5 nc
-277.311 -252.33 20.8452 0 0 0.5 nc
-271.13 -175.058 20.8452 0 0 0.5 nc
-366.947 -110.15 20.8452 0 0 0.5 nc
-397.855 -196.694 20.8452 0 0 0.5 nc
-438.037 -88.514 20.8452 0 0 0.5 nc
-286.584 -48.3327 20.8452 0 0 0.5 nc
-212.403 -23.6057 20.8452 0 0 0.5 nc
-280.402 10.3938 20.8452 0 0 0.5 nc
-694.579 115.483 20.8452 1 0 0 nc
-574.035 177.301 20.8452 0 1 0 nc
+-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
Index: doc/images/node_biconnected_components.eps
===================================================================
--- doc/images/node_biconnected_components.eps (revision 1213)
+++ doc/images/node_biconnected_components.eps (revision 634)
@@ -1,5 +1,5 @@
%!PS-Adobe-2.0 EPSF-2.0
%%Creator: LEMON, graphToEps()
-%%CreationDate: Fri Mar 8 00:18:43 2013
+%%CreationDate: Fri Nov 4 13:47:12 2005
%%BoundingBox: 0 0 842 596
%%EndComments
@@ -54,105 +54,105 @@
%Edges:
gsave
-574.035 177.301 622.149 225.748 670.264 274.195 0 1 0 6.25356 lb
-694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 6.25356 lb
-280.402 10.3938 246.402 -6.60595 212.403 -23.6057 1 1 0.5 6.25356 lb
-280.402 10.3938 283.493 -18.9695 286.584 -48.3327 1 1 0.5 6.25356 lb
-212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 1 1 0.5 6.25356 lb
-286.584 -48.3327 326.765 -79.2414 366.947 -110.15 1 0.5 1 6.25356 lb
-286.584 -48.3327 278.857 -111.695 271.13 -175.058 1 0.5 1 6.25356 lb
-438.037 -88.514 417.946 -142.604 397.855 -196.694 0.5 0.5 1 6.25356 lb
-438.037 -88.514 402.492 -99.332 366.947 -110.15 0.5 0.5 1 6.25356 lb
-397.855 -196.694 382.401 -153.422 366.947 -110.15 0.5 0.5 1 6.25356 lb
-366.947 -110.15 319.038 -142.604 271.13 -175.058 1 0.5 1 6.25356 lb
-271.13 -175.058 274.221 -213.694 277.311 -252.33 0.5 1 1 6.25356 lb
-271.13 -175.058 238.675 -190.512 206.221 -205.967 0.5 1 1 6.25356 lb
-277.311 -252.33 241.766 -229.149 206.221 -205.967 0.5 1 1 6.25356 lb
--840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0.5 0 6.25356 lb
--579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0.5 6.25356 lb
--579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0.5 6.25356 lb
--767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0.5 6.25356 lb
-906.312 201.403 946.592 42.798 986.873 -115.807 0 0.5 0.5 6.25356 lb
-906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0.5 0.5 6.25356 lb
-986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0.5 0.5 6.25356 lb
--470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0.5 0.5 0 6.25356 lb
-422.945 521.129 208.955 541.269 -5.03507 561.41 0.5 0 0.5 6.25356 lb
-422.945 521.129 376.371 417.911 329.797 314.692 0.5 0 0.5 6.25356 lb
-422.945 521.129 474.554 276.928 526.164 32.7279 0.5 0 0.5 6.25356 lb
--5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0.5 0 0.5 6.25356 lb
-329.797 314.692 130.912 317.209 -67.9734 319.727 0.5 0 0.5 6.25356 lb
--67.9734 319.727 229.095 176.227 526.164 32.7279 0.5 0 0.5 6.25356 lb
-762.812 -17.6227 644.488 7.5526 526.164 32.7279 0.5 0.5 0.5 6.25356 lb
-762.812 -17.6227 746.448 -162.381 730.084 -307.139 0.5 0.5 0.5 6.25356 lb
-526.164 32.7279 470.779 -128.394 415.393 -289.516 0.5 0.5 0.5 6.25356 lb
-730.084 -307.139 572.738 -298.327 415.393 -289.516 0.5 0.5 0.5 6.25356 lb
-415.393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0.5 0.5 6.25356 lb
--67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0.5 1 0.5 6.25356 lb
--67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0.5 1 0.5 6.25356 lb
--309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0.5 1 0.5 6.25356 lb
--323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0.5 1 0.5 6.25356 lb
--26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 1 1 0 6.25356 lb
--26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 1 1 0 6.25356 lb
--26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 1 0 1 6.25356 lb
--26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 1 0 1 6.25356 lb
-116.407 -173.66 158.808 -67.6589 201.208 38.3422 1 1 0 6.25356 lb
--262.548 107.243 -137.997 120.493 -13.4452 133.743 1 0 1 6.25356 lb
--262.548 107.243 -221.472 176.144 -180.397 245.045 1 0 1 6.25356 lb
--13.4452 133.743 -96.9211 189.394 -180.397 245.045 1 0 1 6.25356 lb
--180.397 245.045 -113.509 338.465 -132.697 451.748 0 1 1 6.25356 lb
--180.397 245.045 -199.585 358.328 -132.697 451.748 0 1 1 6.25356 lb
--416.25 345.746 -274.474 398.747 -132.697 451.748 0.5 0 0 6.25356 lb
--416.25 345.746 -393.725 457.048 -371.2 568.349 0.5 0 0 6.25356 lb
--132.697 451.748 -251.948 510.048 -371.2 568.349 0.5 0 0 6.25356 lb
-670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 6.25356 lb
-670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 6.25356 lb
-588.113 544.499 756.39 476.923 924.667 409.347 0 0 1 6.25356 lb
--689.204 -237.261 -587.735 -114.393 -567.302 43.6423 0 0 0 6.25356 lb
--689.204 -237.261 -668.771 -79.2259 -567.302 43.6423 0 0 0 6.25356 lb
+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.8452 0 0 1 nc
--689.204 -237.261 20.8452 0 0 1 nc
-924.667 409.347 20.8452 0 0 1 nc
-588.113 544.499 20.8452 0 0 1 nc
-670.264 274.195 20.8452 1 0 0 nc
--371.2 568.349 20.8452 0 0 1 nc
--132.697 451.748 20.8452 1 0 0 nc
--416.25 345.746 20.8452 0 0 1 nc
--180.397 245.045 20.8452 1 0 0 nc
--13.4452 133.743 20.8452 0 0 1 nc
--262.548 107.243 20.8452 0 0 1 nc
-201.208 38.3422 20.8452 0 0 1 nc
-116.407 -173.66 20.8452 0 0 1 nc
--26.6953 -19.9585 20.8452 1 0 0 nc
--539.894 -262.64 20.8452 0 0 1 nc
--323.543 -433.964 20.8452 0 0 1 nc
--309.657 -57.9033 20.8452 1 0 0 nc
--67.9734 -347.42 20.8452 1 0 0 nc
-415.393 -289.516 20.8452 1 0 0 nc
-730.084 -307.139 20.8452 0 0 1 nc
-526.164 32.7279 20.8452 1 0 0 nc
-762.812 -17.6227 20.8452 1 0 0 nc
--67.9734 319.727 20.8452 0 0 1 nc
-329.797 314.692 20.8452 0 0 1 nc
--5.03507 561.41 20.8452 0 0 1 nc
-422.945 521.129 20.8452 0 0 1 nc
--470.779 158.605 20.8452 1 0 0 nc
-986.873 -115.807 20.8452 0 0 1 nc
-906.312 201.403 20.8452 0 0 1 nc
--767.847 113.289 20.8452 1 0 0 nc
--579.033 445.603 20.8452 0 0 1 nc
--840.856 -246.718 20.8452 0 0 1 nc
-206.221 -205.967 20.8452 0 0 1 nc
-277.311 -252.33 20.8452 0 0 1 nc
-271.13 -175.058 20.8452 1 0 0 nc
-366.947 -110.15 20.8452 1 0 0 nc
-397.855 -196.694 20.8452 0 0 1 nc
-438.037 -88.514 20.8452 0 0 1 nc
-286.584 -48.3327 20.8452 1 0 0 nc
-212.403 -23.6057 20.8452 0 0 1 nc
-280.402 10.3938 20.8452 0 0 1 nc
-694.579 115.483 20.8452 0 0 1 nc
-574.035 177.301 20.8452 0 0 1 nc
+-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
Index: doc/images/strongly_connected_components.eps
===================================================================
--- doc/images/strongly_connected_components.eps (revision 1213)
+++ doc/images/strongly_connected_components.eps (revision 634)
@@ -1,5 +1,5 @@
%!PS-Adobe-2.0 EPSF-2.0
%%Creator: LEMON, graphToEps()
-%%CreationDate: Fri Mar 8 00:22:15 2013
+%%CreationDate: Fri Nov 4 13:47:12 2005
%%BoundingBox: 0 0 842 596
%%EndComments
@@ -54,126 +54,126 @@
%Edges:
gsave
-4.56973 setlinewidth 0 0 1 setrgbcolor newpath
+2 setlinewidth 0 0 1 setrgbcolor newpath
218.178 27.2723 moveto
-195.849 -31.0725 190.033 -46.2697 176.306 -82.1369 curveto stroke
-newpath 163.235 -116.291 moveto 165.206 -77.8889 lineto 187.405 -86.3849 lineto closepath fill
-4.56973 setlinewidth 0 0 1 setrgbcolor newpath
+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
-109.705 19.9594 126.016 21.0591 166.493 23.7879 curveto stroke
-newpath 202.98 26.2477 moveto 167.292 11.9299 lineto 165.694 35.6458 lineto closepath fill
-4.56973 setlinewidth 1 0 0 setrgbcolor newpath
+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
-281.264 -80.3935 289.87 -95.0808 338.092 -177.379 curveto stroke
-newpath 356.579 -208.932 moveto 327.837 -183.388 lineto 348.346 -171.371 lineto closepath fill
-4.56973 setlinewidth 0 0 1 setrgbcolor newpath
+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
-114.446 -74.4692 104.358 -61.4239 76.4943 -25.394 curveto stroke
-newpath 54.1228 3.53455 moveto 85.8959 -18.1234 lineto 67.0928 -32.6646 lineto closepath fill
-4.56973 setlinewidth 1 0 0 setrgbcolor newpath
+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
--39.4801 -139.85 -31.344 -124.846 20.1113 -29.9539 curveto stroke
-newpath 37.5434 2.19358 moveto 30.559 -35.6192 lineto 9.66361 -24.2886 lineto closepath fill
-4.56973 setlinewidth 0 0 1 setrgbcolor newpath
+-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
--550.335 -27.1603 -566.8 -24.1113 -625.027 -13.3286 curveto stroke
-newpath -660.985 -6.66971 moveto -622.863 -1.64245 lineto -627.191 -25.0148 lineto closepath fill
-4.56973 setlinewidth 0 0 1 setrgbcolor newpath
+-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
--535.911 -114.447 -524.692 -103.027 -501.88 -79.8085 curveto stroke
-newpath -476.251 -53.7222 moveto -493.402 -88.1377 lineto -510.358 -71.4793 lineto closepath fill
-4.56973 setlinewidth 1 0 0 setrgbcolor newpath
+-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
--481.623 60.8277 -479.143 44.8049 -473.499 8.33636 curveto stroke
-newpath -467.906 -27.8032 moveto -485.244 6.51862 lineto -461.754 10.1541 lineto closepath fill
-4.56973 setlinewidth 0 0 1 setrgbcolor newpath
+-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
--637.405 -60.9909 -628.201 -74.6206 -603.658 -110.963 curveto stroke
-newpath -583.191 -141.27 moveto -613.507 -117.615 lineto -593.808 -104.312 lineto closepath fill
-4.56973 setlinewidth 0 0 1 setrgbcolor newpath
+-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
--439.75 208.465 -431.238 223.057 -394.278 286.417 curveto stroke
-newpath -375.851 318.006 moveto -384.012 280.429 lineto -404.543 292.406 lineto closepath fill
-4.56973 setlinewidth 0 0 1 setrgbcolor newpath
+-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
--358.311 117.318 -375.109 117.756 -439.117 119.426 curveto stroke
-newpath -475.674 120.38 moveto -438.807 131.307 lineto -439.426 107.545 lineto closepath fill
-4.56973 setlinewidth 0 0 1 setrgbcolor newpath
+-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
--326.156 241.466 -318.997 226.186 -288.855 161.843 curveto stroke
-newpath -273.341 128.727 moveto -299.617 156.801 lineto -278.092 166.885 lineto closepath fill
-4.56973 setlinewidth 1 0 0 setrgbcolor newpath
+-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
--226.764 227.755 -221.069 243.774 -190.728 329.107 curveto stroke
-newpath -178.477 363.564 moveto -179.53 325.126 lineto -201.926 333.089 lineto closepath fill
-4.56973 setlinewidth 0 0 1 setrgbcolor newpath
+-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
--198.044 -308.079 -183.61 -300.766 -151.402 -284.448 curveto stroke
-newpath -118.781 -267.92 moveto -146.031 -295.049 lineto -156.774 -273.846 lineto closepath fill
-4.56973 setlinewidth 0 0 1 setrgbcolor newpath
+-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
--332.039 -219.059 -322.392 -232.919 -280.889 -292.543 curveto stroke
-newpath -259.996 -322.557 moveto -290.643 -299.333 lineto -271.134 -285.753 lineto closepath fill
-4.56973 setlinewidth 1 0 0 setrgbcolor newpath
+-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
--70.5724 261.706 -81.8227 274.423 -139.051 339.116 curveto stroke
-newpath -163.281 366.507 moveto -130.149 346.991 lineto -147.953 331.242 lineto closepath fill
-4.56973 setlinewidth 0 0 1 setrgbcolor newpath
+-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
-103.641 256.819 90.7821 246.103 45.6398 208.485 curveto stroke
-newpath 17.546 185.074 moveto 38.0313 217.615 lineto 53.2483 199.355 lineto closepath fill
-4.56973 setlinewidth 0 0 1 setrgbcolor newpath
+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
-269.224 196.246 258.132 209.083 203.347 272.486 curveto stroke
-newpath 179.437 300.157 moveto 212.34 280.257 lineto 194.354 264.716 lineto closepath fill
-4.56973 setlinewidth 0 0 1 setrgbcolor newpath
+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
-155.419 146.79 172.221 143.585 291.966 120.743 curveto stroke
-newpath 327.888 113.891 moveto 289.739 109.069 lineto 294.193 132.418 lineto closepath fill
-4.56973 setlinewidth 0 0 1 setrgbcolor newpath
+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
-490.978 6.99574 505.015 -2.86383 627.727 -89.0547 curveto stroke
-newpath 657.653 -110.074 moveto 620.896 -98.7802 lineto 634.558 -79.3291 lineto closepath fill
-4.56973 setlinewidth 0 0 1 setrgbcolor newpath
+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.807 -74.8128 353.709 -57.7536 346.177 59.3416 curveto stroke
-newpath 343.829 95.836 moveto 358.037 60.1045 lineto 334.316 58.5786 lineto closepath fill
-4.56973 setlinewidth 0 0 1 setrgbcolor newpath
+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
-535.595 -164.241 519.412 -169.704 413.361 -205.505 curveto stroke
-newpath 378.712 -217.202 moveto 409.559 -194.245 lineto 417.162 -216.766 lineto closepath fill
-4.56973 setlinewidth 1 0 0 setrgbcolor newpath
+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
-110.939 -243.099 128.069 -241.677 312.655 -226.358 curveto stroke
-newpath 349.1 -223.334 moveto 313.638 -238.202 lineto 311.672 -214.514 lineto closepath fill
-4.56973 setlinewidth 0 0 1 setrgbcolor newpath
+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
--156.746 -168.566 -164.987 -153.784 -202.693 -86.1539 curveto stroke
-newpath -220.5 -54.2129 moveto -192.312 -80.3665 lineto -213.073 -91.9413 lineto closepath fill
-4.56973 setlinewidth 0 0 1 setrgbcolor newpath
+-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
--290.327 -77.7521 -304.558 -86.1532 -344.995 -110.026 curveto stroke
-newpath -376.487 -128.617 moveto -351.037 -99.7914 lineto -338.953 -120.26 lineto closepath fill
+-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 15.2324 0 1 0 nc
--227.918 -40.9084 15.2324 0 1 0 nc
--105.193 -261.035 15.2324 0 1 0 nc
-364.28 -222.074 15.2324 1 1 0 nc
-670.118 -118.829 15.2324 1 1 0 nc
-342.851 111.037 15.2324 1 1 0 nc
-5.84406 175.322 15.2324 1 1 0 nc
-169.478 311.683 15.2324 1 1 0 nc
--173.374 377.916 15.2324 1 0 1 nc
--251.294 -335.059 15.2324 0 1 0 nc
--266.879 114.933 15.2324 0 0 0 nc
--368.176 331.163 15.2324 0 0 0 nc
--490.901 120.777 15.2324 0 0 0 nc
--574.666 -153.893 15.2324 1 0 0 nc
--675.963 -3.89604 15.2324 1 0 0 nc
--465.576 -42.8564 15.2324 1 0 0 nc
-44.8044 15.5841 15.2324 0 0 1 nc
-157.79 -130.517 15.2324 0 0 1 nc
-218.178 27.2723 15.2324 0 0 1 nc
+-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
Index: c/images/tsp.eps
===================================================================
--- doc/images/tsp.eps (revision 1200)
+++ (revision )
@@ -1,229 +1,0 @@
-%!PS-Adobe-2.0 EPSF-2.0
-%%Creator: LEMON, graphToEps()
-%%CreationDate: Tue Jun 15 00:58:57 2010
-%%BoundingBox: 31 41 649 709
-%%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
-/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
- newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
- lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
- 5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
- 5 index 5 index 5 index c fill
- setrgbcolor 1.1 div c fill
- } bind def
-/nmale {
- 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
- newpath 5 index 5 index moveto
- 5 index 4 index 1 mul 1.5 mul add
- 5 index 5 index 3 sqrt 1.5 mul mul add
- 1 index 1 index lineto
- 1 index 1 index 7 index sub moveto
- 1 index 1 index lineto
- exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
- stroke
- 5 index 5 index 5 index c fill
- setrgbcolor 1.1 div c fill
- } bind def
-/arrl 1 def
-/arrw 0.3 def
-/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
-/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
- /w exch def /len exch def
- newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
- len w sub arrl sub dx dy lrl
- arrw dy dx neg lrl
- dx arrl w add mul dy w 2 div arrw add mul sub
- dy arrl w add mul dx w 2 div arrw add mul add rlineto
- dx arrl w add mul neg dy w 2 div arrw add mul sub
- dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
- arrw dy dx neg lrl
- len w sub arrl sub neg dx dy lrl
- closepath fill } bind def
-/cshow { 2 index 2 index moveto dup stringwidth pop
- neg 2 div fosi .35 mul neg rmoveto show pop pop} def
-
-gsave
-10 dup scale
-%Arcs:
-gsave
-27 68 37 69 0 0 1 0.513798 l
-37 69 27 68 0 0 1 0.513798 l
-8 52 5 64 0 0 1 0.513798 l
-5 64 8 52 0 0 1 0.513798 l
-16 57 25 55 0 0 1 0.513798 l
-25 55 16 57 0 0 1 0.513798 l
-43 67 37 69 0 0 1 0.513798 l
-37 69 43 67 0 0 1 0.513798 l
-42 57 43 67 0 0 1 0.513798 l
-43 67 42 57 0 0 1 0.513798 l
-62 42 61 33 0 0 1 0.513798 l
-61 33 62 42 0 0 1 0.513798 l
-62 42 58 48 0 0 1 0.513798 l
-58 48 62 42 0 0 1 0.513798 l
-58 27 61 33 0 0 1 0.513798 l
-61 33 58 27 0 0 1 0.513798 l
-57 58 62 63 0 0 1 0.513798 l
-62 63 57 58 0 0 1 0.513798 l
-13 13 21 10 0 0 1 0.513798 l
-21 10 13 13 0 0 1 0.513798 l
-13 13 5 6 0 0 1 0.513798 l
-5 6 13 13 0 0 1 0.513798 l
-17 33 7 38 0 0 1 0.513798 l
-7 38 17 33 0 0 1 0.513798 l
-46 10 59 15 0 0 1 0.513798 l
-59 15 46 10 0 0 1 0.513798 l
-46 10 39 10 0 0 1 0.513798 l
-39 10 46 10 0 0 1 0.513798 l
-27 23 21 10 0 0 1 0.513798 l
-21 10 27 23 0 0 1 0.513798 l
-52 41 56 37 0 0 1 0.513798 l
-56 37 52 41 0 0 1 0.513798 l
-62 63 63 69 0 0 1 0.513798 l
-63 69 62 63 0 0 1 0.513798 l
-36 16 39 10 0 0 1 0.513798 l
-39 10 36 16 0 0 1 0.513798 l
-36 16 30 15 0 0 1 0.513798 l
-30 15 36 16 0 0 1 0.513798 l
-12 42 7 38 0 0 1 0.513798 l
-7 38 12 42 0 0 1 0.513798 l
-12 42 8 52 0 0 1 0.513798 l
-8 52 12 42 0 0 1 0.513798 l
-32 22 30 15 0 0 1 0.513798 l
-30 15 32 22 0 0 1 0.513798 l
-5 25 10 17 0 0 1 0.513798 l
-10 17 5 25 0 0 1 0.513798 l
-5 25 17 33 0 0 1 0.513798 l
-17 33 5 25 0 0 1 0.513798 l
-45 35 48 28 0 0 1 0.513798 l
-48 28 45 35 0 0 1 0.513798 l
-31 32 25 32 0 0 1 0.513798 l
-25 32 31 32 0 0 1 0.513798 l
-31 32 32 39 0 0 1 0.513798 l
-32 39 31 32 0 0 1 0.513798 l
-42 41 38 46 0 0 1 0.513798 l
-38 46 42 41 0 0 1 0.513798 l
-42 41 52 41 0 0 1 0.513798 l
-52 41 42 41 0 0 1 0.513798 l
-5 6 10 17 0 0 1 0.513798 l
-10 17 5 6 0 0 1 0.513798 l
-51 21 59 15 0 0 1 0.513798 l
-59 15 51 21 0 0 1 0.513798 l
-51 21 58 27 0 0 1 0.513798 l
-58 27 51 21 0 0 1 0.513798 l
-52 33 56 37 0 0 1 0.513798 l
-56 37 52 33 0 0 1 0.513798 l
-52 33 48 28 0 0 1 0.513798 l
-48 28 52 33 0 0 1 0.513798 l
-31 62 25 55 0 0 1 0.513798 l
-25 55 31 62 0 0 1 0.513798 l
-31 62 27 68 0 0 1 0.513798 l
-27 68 31 62 0 0 1 0.513798 l
-17 63 5 64 0 0 1 0.513798 l
-5 64 17 63 0 0 1 0.513798 l
-17 63 16 57 0 0 1 0.513798 l
-16 57 17 63 0 0 1 0.513798 l
-21 47 30 40 0 0 1 0.513798 l
-30 40 21 47 0 0 1 0.513798 l
-21 47 30 48 0 0 1 0.513798 l
-30 48 21 47 0 0 1 0.513798 l
-40 30 45 35 0 0 1 0.513798 l
-45 35 40 30 0 0 1 0.513798 l
-40 30 32 22 0 0 1 0.513798 l
-32 22 40 30 0 0 1 0.513798 l
-32 39 30 40 0 0 1 0.513798 l
-30 40 32 39 0 0 1 0.513798 l
-20 26 25 32 0 0 1 0.513798 l
-25 32 20 26 0 0 1 0.513798 l
-20 26 27 23 0 0 1 0.513798 l
-27 23 20 26 0 0 1 0.513798 l
-52 64 63 69 0 0 1 0.513798 l
-63 69 52 64 0 0 1 0.513798 l
-52 64 42 57 0 0 1 0.513798 l
-42 57 52 64 0 0 1 0.513798 l
-49 49 58 48 0 0 1 0.513798 l
-58 48 49 49 0 0 1 0.513798 l
-49 49 57 58 0 0 1 0.513798 l
-57 58 49 49 0 0 1 0.513798 l
-37 52 38 46 0 0 1 0.513798 l
-38 46 37 52 0 0 1 0.513798 l
-37 52 30 48 0 0 1 0.513798 l
-30 48 37 52 0 0 1 0.513798 l
-grestore
-%Nodes:
-gsave
-30 40 0.856329 1 1 1 nc
-56 37 0.856329 1 1 1 nc
-48 28 0.856329 1 1 1 nc
-25 55 0.856329 1 1 1 nc
-25 32 0.856329 1 1 1 nc
-32 39 0.856329 1 1 1 nc
-39 10 0.856329 1 1 1 nc
-30 15 0.856329 1 1 1 nc
-5 64 0.856329 1 1 1 nc
-21 10 0.856329 1 1 1 nc
-10 17 0.856329 1 1 1 nc
-5 6 0.856329 1 1 1 nc
-59 15 0.856329 1 1 1 nc
-45 35 0.856329 1 1 1 nc
-32 22 0.856329 1 1 1 nc
-63 69 0.856329 1 1 1 nc
-62 63 0.856329 1 1 1 nc
-61 33 0.856329 1 1 1 nc
-46 10 0.856329 1 1 1 nc
-38 46 0.856329 1 1 1 nc
-37 69 0.856329 1 1 1 nc
-58 27 0.856329 1 1 1 nc
-58 48 0.856329 1 1 1 nc
-43 67 0.856329 1 1 1 nc
-30 48 0.856329 1 1 1 nc
-27 68 0.856329 1 1 1 nc
-7 38 0.856329 1 1 1 nc
-8 52 0.856329 1 1 1 nc
-16 57 0.856329 1 1 1 nc
-42 57 0.856329 1 1 1 nc
-62 42 0.856329 1 1 1 nc
-57 58 0.856329 1 1 1 nc
-13 13 0.856329 1 1 1 nc
-17 33 0.856329 1 1 1 nc
-27 23 0.856329 1 1 1 nc
-52 41 0.856329 1 1 1 nc
-36 16 0.856329 1 1 1 nc
-12 42 0.856329 1 1 1 nc
-5 25 0.856329 1 1 1 nc
-31 32 0.856329 1 1 1 nc
-42 41 0.856329 1 1 1 nc
-51 21 0.856329 1 1 1 nc
-52 33 0.856329 1 1 1 nc
-31 62 0.856329 1 1 1 nc
-17 63 0.856329 1 1 1 nc
-21 47 0.856329 1 1 1 nc
-40 30 0.856329 1 1 1 nc
-20 26 0.856329 1 1 1 nc
-52 64 0.856329 1 1 1 nc
-49 49 0.856329 1 1 1 nc
-37 52 0.856329 1 1 1 nc
-grestore
-grestore
-showpage
Index: doc/lgf.dox
===================================================================
--- doc/lgf.dox (revision 1192)
+++ doc/lgf.dox (revision 1069)
@@ -64,26 +64,9 @@
\endcode
-The \e LGF files can also contain bipartite graphs, in this case a
-\c @red_nodes and a \c @blue_nodes sections describe the node set of the
-graph. If a map is in both of these sections, then it can be used as a
-regular node map.
-
-\code
- @red_nodes
- label only_red_map name
- 1 "cherry" "John"
- 2 "Santa Claus" "Jack"
- 3 "blood" "Jason"
- @blue_nodes
- label name
- 4 "Elisabeth"
- 5 "Eve"
-\endcode
-
-The \c \@arcs section is very similar to the \c \@nodes section,
-it again starts with a header line describing the names of the maps,
-but the \c "label" map is not obligatory here. The following lines
-describe the arcs. The first two tokens of each line are
-the source and the target node of the arc, respectively, then come the map
+The \c \@arcs section is very similar to the \c \@nodes section, it
+again starts with a header line describing the names of the maps, but
+the \c "label" map is not obligatory here. The following lines
+describe the arcs. The first two tokens of each line are the source
+and the target node of the arc, respectively, then come the map
values. The source and target tokens must be node labels.
Index: doc/mainpage.dox.in
===================================================================
--- doc/mainpage.dox.in (revision 1221)
+++ doc/mainpage.dox.in (revision 1039)
@@ -26,5 +26,5 @@
It is a C++ template library providing efficient implementations of common
data structures and algorithms with focus on combinatorial optimization
-tasks connected mainly with graphs and networks \cite DezsoJuttnerKovacs11Lemon.
+tasks connected mainly with graphs and networks.
@@ -38,10 +38,10 @@
The project is maintained by the
Egerváry Research Group on
-Combinatorial Optimization \cite egres
+Combinatorial Optimization \ref egres
at the Operations Research Department of the
Eötvös Loránd University,
Budapest, Hungary.
LEMON is also a member of the COIN-OR
-initiative \cite coinor.
+initiative \ref coinor.
\section howtoread How to Read the Documentation
Index: doc/min_cost_flow.dox
===================================================================
--- doc/min_cost_flow.dox (revision 1221)
+++ doc/min_cost_flow.dox (revision 1164)
@@ -27,5 +27,5 @@
minimum total cost from a set of supply nodes to a set of demand nodes
in a network with capacity constraints (lower and upper bounds)
-and arc costs \cite amo93networkflows.
+and arc costs \ref amo93networkflows.
Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
Index: doc/references.bib
===================================================================
--- doc/references.bib (revision 1219)
+++ doc/references.bib (revision 1164)
@@ -20,26 +20,4 @@
{O}perations {R}esearch},
url = {http://www.coin-or.org/}
-}
-
-
-%%%%% Papers related to LEMON %%%%%
-
-@article{DezsoJuttnerKovacs11Lemon,
- author = {B. Dezs{\H o} and A. J\"uttner and P. Kov\'acs},
- title = {{LEMON} -- an open source {C++} graph template library},
- journal = {Electronic Notes in Theoretical Computer Science},
- volume = {264},
- pages = {23--45},
- year = {2011},
- note = {Proc. 2nd Workshop on Generative Technologies}
-}
-
-@article{KiralyKovacs12MCF,
- author = {Z. Kir\'aly and P. Kov\'acs},
- title = {Efficient implementations of minimum-cost flow algorithms},
- journal = {Acta Universitatis Sapientiae, Informatica},
- year = {2012},
- volume = {4},
- pages = {67--118}
}
Index: lemon/CMakeLists.txt
===================================================================
--- lemon/CMakeLists.txt (revision 1133)
+++ lemon/CMakeLists.txt (revision 1230)
@@ -37,5 +37,5 @@
IF(LEMON_HAVE_CPLEX)
SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc)
- INCLUDE_DIRECTORIES(${CPLEX_INCLUDE_DIRS})
+ INCLUDE_DIRECTORIES(${ILOG_INCLUDE_DIRS})
ENDIF()
Index: lemon/base.cc
===================================================================
--- lemon/base.cc (revision 1222)
+++ lemon/base.cc (revision 554)
@@ -22,5 +22,4 @@
#include
#include
-#include
namespace lemon {
@@ -33,5 +32,3 @@
#endif
- TimeStamp::Format TimeStamp::_format = TimeStamp::NORMAL;
-
} //namespace lemon
Index: lemon/bits/graph_extender.h
===================================================================
--- lemon/bits/graph_extender.h (revision 1195)
+++ lemon/bits/graph_extender.h (revision 1159)
@@ -747,585 +747,4 @@
};
- // \ingroup _graphbits
- //
- // \brief Extender for the BpGraphs
- template
- class BpGraphExtender : public Base {
- typedef Base Parent;
-
- public:
-
- typedef BpGraphExtender BpGraph;
-
- typedef True UndirectedTag;
-
- typedef typename Parent::Node Node;
- typedef typename Parent::RedNode RedNode;
- typedef typename Parent::BlueNode BlueNode;
- typedef typename Parent::Arc Arc;
- typedef typename Parent::Edge Edge;
-
- // BpGraph extension
-
- using Parent::first;
- using Parent::next;
- using Parent::id;
-
- int maxId(Node) const {
- return Parent::maxNodeId();
- }
-
- int maxId(RedNode) const {
- return Parent::maxRedId();
- }
-
- int maxId(BlueNode) const {
- return Parent::maxBlueId();
- }
-
- int maxId(Arc) const {
- return Parent::maxArcId();
- }
-
- int maxId(Edge) const {
- return Parent::maxEdgeId();
- }
-
- static Node fromId(int id, Node) {
- return Parent::nodeFromId(id);
- }
-
- static Arc fromId(int id, Arc) {
- return Parent::arcFromId(id);
- }
-
- static Edge fromId(int id, Edge) {
- return Parent::edgeFromId(id);
- }
-
- Node u(Edge e) const { return this->redNode(e); }
- Node v(Edge e) const { return this->blueNode(e); }
-
- Node oppositeNode(const Node &n, const Edge &e) const {
- if( n == u(e))
- return v(e);
- else if( n == v(e))
- return u(e);
- else
- return INVALID;
- }
-
- Arc oppositeArc(const Arc &arc) const {
- return Parent::direct(arc, !Parent::direction(arc));
- }
-
- using Parent::direct;
- Arc direct(const Edge &edge, const Node &node) const {
- return Parent::direct(edge, Parent::redNode(edge) == node);
- }
-
- RedNode asRedNode(const Node& node) const {
- if (node == INVALID || Parent::blue(node)) {
- return INVALID;
- } else {
- return Parent::asRedNodeUnsafe(node);
- }
- }
-
- BlueNode asBlueNode(const Node& node) const {
- if (node == INVALID || Parent::red(node)) {
- return INVALID;
- } else {
- return Parent::asBlueNodeUnsafe(node);
- }
- }
-
- // Alterable extension
-
- typedef AlterationNotifier NodeNotifier;
- typedef AlterationNotifier RedNodeNotifier;
- typedef AlterationNotifier BlueNodeNotifier;
- typedef AlterationNotifier ArcNotifier;
- typedef AlterationNotifier EdgeNotifier;
-
-
- protected:
-
- mutable NodeNotifier node_notifier;
- mutable RedNodeNotifier red_node_notifier;
- mutable BlueNodeNotifier blue_node_notifier;
- mutable ArcNotifier arc_notifier;
- mutable EdgeNotifier edge_notifier;
-
- public:
-
- NodeNotifier& notifier(Node) const {
- return node_notifier;
- }
-
- RedNodeNotifier& notifier(RedNode) const {
- return red_node_notifier;
- }
-
- BlueNodeNotifier& notifier(BlueNode) const {
- return blue_node_notifier;
- }
-
- ArcNotifier& notifier(Arc) const {
- return arc_notifier;
- }
-
- EdgeNotifier& notifier(Edge) const {
- return edge_notifier;
- }
-
-
-
- class NodeIt : public Node {
- const BpGraph* _graph;
- public:
-
- NodeIt() {}
-
- NodeIt(Invalid i) : Node(i) { }
-
- explicit NodeIt(const BpGraph& graph) : _graph(&graph) {
- _graph->first(static_cast(*this));
- }
-
- NodeIt(const BpGraph& graph, const Node& node)
- : Node(node), _graph(&graph) {}
-
- NodeIt& operator++() {
- _graph->next(*this);
- return *this;
- }
-
- };
-
- class RedNodeIt : public RedNode {
- const BpGraph* _graph;
- public:
-
- RedNodeIt() {}
-
- RedNodeIt(Invalid i) : RedNode(i) { }
-
- explicit RedNodeIt(const BpGraph& graph) : _graph(&graph) {
- _graph->first(static_cast(*this));
- }
-
- RedNodeIt(const BpGraph& graph, const RedNode& node)
- : RedNode(node), _graph(&graph) {}
-
- RedNodeIt& operator++() {
- _graph->next(static_cast(*this));
- return *this;
- }
-
- };
-
- class BlueNodeIt : public BlueNode {
- const BpGraph* _graph;
- public:
-
- BlueNodeIt() {}
-
- BlueNodeIt(Invalid i) : BlueNode(i) { }
-
- explicit BlueNodeIt(const BpGraph& graph) : _graph(&graph) {
- _graph->first(static_cast(*this));
- }
-
- BlueNodeIt(const BpGraph& graph, const BlueNode& node)
- : BlueNode(node), _graph(&graph) {}
-
- BlueNodeIt& operator++() {
- _graph->next(static_cast(*this));
- return *this;
- }
-
- };
-
-
- class ArcIt : public Arc {
- const BpGraph* _graph;
- public:
-
- ArcIt() { }
-
- ArcIt(Invalid i) : Arc(i) { }
-
- explicit ArcIt(const BpGraph& graph) : _graph(&graph) {
- _graph->first(static_cast(*this));
- }
-
- ArcIt(const BpGraph& graph, const Arc& arc) :
- Arc(arc), _graph(&graph) { }
-
- ArcIt& operator++() {
- _graph->next(*this);
- return *this;
- }
-
- };
-
-
- class OutArcIt : public Arc {
- const BpGraph* _graph;
- public:
-
- OutArcIt() { }
-
- OutArcIt(Invalid i) : Arc(i) { }
-
- OutArcIt(const BpGraph& graph, const Node& node)
- : _graph(&graph) {
- _graph->firstOut(*this, node);
- }
-
- OutArcIt(const BpGraph& graph, const Arc& arc)
- : Arc(arc), _graph(&graph) {}
-
- OutArcIt& operator++() {
- _graph->nextOut(*this);
- return *this;
- }
-
- };
-
-
- class InArcIt : public Arc {
- const BpGraph* _graph;
- public:
-
- InArcIt() { }
-
- InArcIt(Invalid i) : Arc(i) { }
-
- InArcIt(const BpGraph& graph, const Node& node)
- : _graph(&graph) {
- _graph->firstIn(*this, node);
- }
-
- InArcIt(const BpGraph& graph, const Arc& arc) :
- Arc(arc), _graph(&graph) {}
-
- InArcIt& operator++() {
- _graph->nextIn(*this);
- return *this;
- }
-
- };
-
-
- class EdgeIt : public Parent::Edge {
- const BpGraph* _graph;
- public:
-
- EdgeIt() { }
-
- EdgeIt(Invalid i) : Edge(i) { }
-
- explicit EdgeIt(const BpGraph& graph) : _graph(&graph) {
- _graph->first(static_cast(*this));
- }
-
- EdgeIt(const BpGraph& graph, const Edge& edge) :
- Edge(edge), _graph(&graph) { }
-
- EdgeIt& operator++() {
- _graph->next(*this);
- return *this;
- }
-
- };
-
- class IncEdgeIt : public Parent::Edge {
- friend class BpGraphExtender;
- const BpGraph* _graph;
- bool _direction;
- public:
-
- IncEdgeIt() { }
-
- IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
-
- IncEdgeIt(const BpGraph& graph, const Node &node) : _graph(&graph) {
- _graph->firstInc(*this, _direction, node);
- }
-
- IncEdgeIt(const BpGraph& graph, const Edge &edge, const Node &node)
- : _graph(&graph), Edge(edge) {
- _direction = (_graph->source(edge) == node);
- }
-
- IncEdgeIt& operator++() {
- _graph->nextInc(*this, _direction);
- return *this;
- }
- };
-
- // \brief Base node of the iterator
- //
- // Returns the base node (ie. the source in this case) of the iterator
- Node baseNode(const OutArcIt &arc) const {
- return Parent::source(static_cast(arc));
- }
- // \brief Running node of the iterator
- //
- // Returns the running node (ie. the target in this case) of the
- // iterator
- Node runningNode(const OutArcIt &arc) const {
- return Parent::target(static_cast(arc));
- }
-
- // \brief Base node of the iterator
- //
- // Returns the base node (ie. the target in this case) of the iterator
- Node baseNode(const InArcIt &arc) const {
- return Parent::target(static_cast(arc));
- }
- // \brief Running node of the iterator
- //
- // Returns the running node (ie. the source in this case) of the
- // iterator
- Node runningNode(const InArcIt &arc) const {
- return Parent::source(static_cast(arc));
- }
-
- // Base node of the iterator
- //
- // Returns the base node of the iterator
- Node baseNode(const IncEdgeIt &edge) const {
- return edge._direction ? this->u(edge) : this->v(edge);
- }
- // Running node of the iterator
- //
- // Returns the running node of the iterator
- Node runningNode(const IncEdgeIt &edge) const {
- return edge._direction ? this->v(edge) : this->u(edge);
- }
-
- // Mappable extension
-
- template
- class NodeMap
- : public MapExtender > {
- typedef MapExtender > Parent;
-
- public:
- explicit NodeMap(const BpGraph& bpgraph)
- : Parent(bpgraph) {}
- NodeMap(const BpGraph& bpgraph, const _Value& value)
- : Parent(bpgraph, value) {}
-
- private:
- NodeMap& operator=(const NodeMap& cmap) {
- return operator=(cmap);
- }
-
- template
- NodeMap& operator=(const CMap& cmap) {
- Parent::operator=(cmap);
- return *this;
- }
-
- };
-
- template
- class RedNodeMap
- : public MapExtender > {
- typedef MapExtender > Parent;
-
- public:
- explicit RedNodeMap(const BpGraph& bpgraph)
- : Parent(bpgraph) {}
- RedNodeMap(const BpGraph& bpgraph, const _Value& value)
- : Parent(bpgraph, value) {}
-
- private:
- RedNodeMap& operator=(const RedNodeMap& cmap) {
- return operator=(cmap);
- }
-
- template
- RedNodeMap& operator=(const CMap& cmap) {
- Parent::operator=(cmap);
- return *this;
- }
-
- };
-
- template
- class BlueNodeMap
- : public MapExtender > {
- typedef MapExtender > Parent;
-
- public:
- explicit BlueNodeMap(const BpGraph& bpgraph)
- : Parent(bpgraph) {}
- BlueNodeMap(const BpGraph& bpgraph, const _Value& value)
- : Parent(bpgraph, value) {}
-
- private:
- BlueNodeMap& operator=(const BlueNodeMap& cmap) {
- return operator=(cmap);
- }
-
- template
- BlueNodeMap& operator=(const CMap& cmap) {
- Parent::operator=(cmap);
- return *this;
- }
-
- };
-
- template
- class ArcMap
- : public MapExtender > {
- typedef MapExtender > Parent;
-
- public:
- explicit ArcMap(const BpGraph& graph)
- : Parent(graph) {}
- ArcMap(const BpGraph& graph, const _Value& value)
- : Parent(graph, value) {}
-
- private:
- ArcMap& operator=(const ArcMap& cmap) {
- return operator=(cmap);
- }
-
- template
- ArcMap& operator=(const CMap& cmap) {
- Parent::operator=(cmap);
- return *this;
- }
- };
-
-
- template
- class EdgeMap
- : public MapExtender > {
- typedef MapExtender > Parent;
-
- public:
- explicit EdgeMap(const BpGraph& graph)
- : Parent(graph) {}
-
- EdgeMap(const BpGraph& graph, const _Value& value)
- : Parent(graph, value) {}
-
- private:
- EdgeMap& operator=(const EdgeMap& cmap) {
- return operator=(cmap);
- }
-
- template
- EdgeMap& operator=(const CMap& cmap) {
- Parent::operator=(cmap);
- return *this;
- }
-
- };
-
- // Alteration extension
-
- RedNode addRedNode() {
- RedNode node = Parent::addRedNode();
- notifier(RedNode()).add(node);
- notifier(Node()).add(node);
- return node;
- }
-
- BlueNode addBlueNode() {
- BlueNode node = Parent::addBlueNode();
- notifier(BlueNode()).add(node);
- notifier(Node()).add(node);
- return node;
- }
-
- Edge addEdge(const RedNode& from, const BlueNode& to) {
- Edge edge = Parent::addEdge(from, to);
- notifier(Edge()).add(edge);
- std::vector av;
- av.push_back(Parent::direct(edge, true));
- av.push_back(Parent::direct(edge, false));
- notifier(Arc()).add(av);
- return edge;
- }
-
- void clear() {
- notifier(Arc()).clear();
- notifier(Edge()).clear();
- notifier(Node()).clear();
- notifier(BlueNode()).clear();
- notifier(RedNode()).clear();
- Parent::clear();
- }
-
- template
- void build(const BpGraph& graph, NodeRefMap& nodeRef,
- EdgeRefMap& edgeRef) {
- Parent::build(graph, nodeRef, edgeRef);
- notifier(RedNode()).build();
- notifier(BlueNode()).build();
- notifier(Node()).build();
- notifier(Edge()).build();
- notifier(Arc()).build();
- }
-
- void erase(const Node& node) {
- Arc arc;
- Parent::firstOut(arc, node);
- while (arc != INVALID ) {
- erase(arc);
- Parent::firstOut(arc, node);
- }
-
- Parent::firstIn(arc, node);
- while (arc != INVALID ) {
- erase(arc);
- Parent::firstIn(arc, node);
- }
-
- if (Parent::red(node)) {
- notifier(RedNode()).erase(this->asRedNodeUnsafe(node));
- } else {
- notifier(BlueNode()).erase(this->asBlueNodeUnsafe(node));
- }
-
- notifier(Node()).erase(node);
- Parent::erase(node);
- }
-
- void erase(const Edge& edge) {
- std::vector av;
- av.push_back(Parent::direct(edge, true));
- av.push_back(Parent::direct(edge, false));
- notifier(Arc()).erase(av);
- notifier(Edge()).erase(edge);
- Parent::erase(edge);
- }
-
- BpGraphExtender() {
- red_node_notifier.setContainer(*this);
- blue_node_notifier.setContainer(*this);
- node_notifier.setContainer(*this);
- arc_notifier.setContainer(*this);
- edge_notifier.setContainer(*this);
- }
-
- ~BpGraphExtender() {
- edge_notifier.clear();
- arc_notifier.clear();
- node_notifier.clear();
- blue_node_notifier.clear();
- red_node_notifier.clear();
- }
-
- };
-
}
Index: lemon/bits/traits.h
===================================================================
--- lemon/bits/traits.h (revision 1194)
+++ lemon/bits/traits.h (revision 663)
@@ -149,86 +149,4 @@
: Parent(_digraph, _value) {}
};
-
- };
-
- template
- struct RedNodeNotifierIndicator {
- typedef InvalidType Type;
- };
- template
- struct RedNodeNotifierIndicator<
- GR,
- typename enable_if::type
- > {
- typedef typename GR::RedNodeNotifier Type;
- };
-
- template
- class ItemSetTraits {
- public:
-
- typedef GR BpGraph;
- typedef GR Graph;
- typedef GR Digraph;
-
- typedef typename GR::RedNode Item;
- typedef typename GR::RedNodeIt ItemIt;
-
- typedef typename RedNodeNotifierIndicator::Type ItemNotifier;
-
- template
- class Map : public GR::template RedNodeMap {
- typedef typename GR::template RedNodeMap Parent;
-
- public:
- typedef typename GR::template RedNodeMap Type;
- typedef typename Parent::Value Value;
-
- Map(const GR& _bpgraph) : Parent(_bpgraph) {}
- Map(const GR& _bpgraph, const Value& _value)
- : Parent(_bpgraph, _value) {}
-
- };
-
- };
-
- template
- struct BlueNodeNotifierIndicator {
- typedef InvalidType Type;
- };
- template
- struct BlueNodeNotifierIndicator<
- GR,
- typename enable_if::type
- > {
- typedef typename GR::BlueNodeNotifier Type;
- };
-
- template
- class ItemSetTraits {
- public:
-
- typedef GR BpGraph;
- typedef GR Graph;
- typedef GR Digraph;
-
- typedef typename GR::BlueNode Item;
- typedef typename GR::BlueNodeIt ItemIt;
-
- typedef typename BlueNodeNotifierIndicator::Type ItemNotifier;
-
- template
- class Map : public GR::template BlueNodeMap {
- typedef typename GR::template BlueNodeMap Parent;
-
- public:
- typedef typename GR::template BlueNodeMap Type;
- typedef typename Parent::Value Value;
-
- Map(const GR& _bpgraph) : Parent(_bpgraph) {}
- Map(const GR& _bpgraph, const Value& _value)
- : Parent(_bpgraph, _value) {}
-
- };
};
Index: lemon/capacity_scaling.h
===================================================================
--- lemon/capacity_scaling.h (revision 1221)
+++ lemon/capacity_scaling.h (revision 1166)
@@ -67,9 +67,7 @@
/// \ref CapacityScaling implements the capacity scaling version
/// of the successive shortest path algorithm for finding a
- /// \ref min_cost_flow "minimum cost flow" \cite amo93networkflows,
- /// \cite edmondskarp72theoretical. It is an efficient dual
- /// solution method, which runs in polynomial time
- /// \f$O(e\log U (n+e)\log n)\f$, where U denotes the maximum
- /// of node supply and arc capacity values.
+ /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,
+ /// \ref edmondskarp72theoretical. It is an efficient dual
+ /// solution method.
///
/// This algorithm is typically slower than \ref CostScaling and
Index: mon/christofides_tsp.h
===================================================================
--- lemon/christofides_tsp.h (revision 1205)
+++ (revision )
@@ -1,254 +1,0 @@
-/* -*- mode: C++; indent-tabs-mode: nil; -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library.
- *
- * Copyright (C) 2003-2010
- * 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.
- *
- */
-
-#ifndef LEMON_CHRISTOFIDES_TSP_H
-#define LEMON_CHRISTOFIDES_TSP_H
-
-/// \ingroup tsp
-/// \file
-/// \brief Christofides algorithm for symmetric TSP
-
-#include
-#include
-#include
-#include
-#include
-
-namespace lemon {
-
- /// \ingroup tsp
- ///
- /// \brief Christofides algorithm for symmetric TSP.
- ///
- /// ChristofidesTsp implements Christofides' heuristic for solving
- /// symmetric \ref tsp "TSP".
- ///
- /// This a well-known approximation method for the TSP problem with
- /// metric cost function.
- /// It has a guaranteed approximation factor of 3/2 (i.e. it finds a tour
- /// whose total cost is at most 3/2 of the optimum), but it usually
- /// provides better solutions in practice.
- /// This implementation runs in O(n3log(n)) time.
- ///
- /// The algorithm starts with a \ref spantree "minimum cost spanning tree" and
- /// finds a \ref MaxWeightedPerfectMatching "minimum cost perfect matching"
- /// in the subgraph induced by the nodes that have odd degree in the
- /// spanning tree.
- /// Finally, it constructs the tour from the \ref EulerIt "Euler traversal"
- /// of the union of the spanning tree and the matching.
- /// During this last step, the algorithm simply skips the visited nodes
- /// (i.e. creates shortcuts) assuming that the triangle inequality holds
- /// for the cost function.
- ///
- /// \tparam CM Type of the cost map.
- ///
- /// \warning CM::Value must be a signed number type.
- template
- class ChristofidesTsp
- {
- public:
-
- /// Type of the cost map
- typedef CM CostMap;
- /// Type of the edge costs
- typedef typename CM::Value Cost;
-
- private:
-
- GRAPH_TYPEDEFS(FullGraph);
-
- const FullGraph &_gr;
- const CostMap &_cost;
- std::vector _path;
- Cost _sum;
-
- public:
-
- /// \brief Constructor
- ///
- /// Constructor.
- /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
- /// \param cost The cost map.
- ChristofidesTsp(const FullGraph &gr, const CostMap &cost)
- : _gr(gr), _cost(cost) {}
-
- /// \name Execution Control
- /// @{
-
- /// \brief Runs the algorithm.
- ///
- /// This function runs the algorithm.
- ///
- /// \return The total cost of the found tour.
- Cost run() {
- _path.clear();
-
- if (_gr.nodeNum() == 0) return _sum = 0;
- else if (_gr.nodeNum() == 1) {
- _path.push_back(_gr(0));
- return _sum = 0;
- }
- else if (_gr.nodeNum() == 2) {
- _path.push_back(_gr(0));
- _path.push_back(_gr(1));
- return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
- }
-
- // Compute min. cost spanning tree
- std::vector tree;
- kruskal(_gr, _cost, std::back_inserter(tree));
-
- FullGraph::NodeMap deg(_gr, 0);
- for (int i = 0; i != int(tree.size()); ++i) {
- Edge e = tree[i];
- ++deg[_gr.u(e)];
- ++deg[_gr.v(e)];
- }
-
- // Copy the induced subgraph of odd nodes
- std::vector odd_nodes;
- for (NodeIt u(_gr); u != INVALID; ++u) {
- if (deg[u] % 2 == 1) odd_nodes.push_back(u);
- }
-
- SmartGraph sgr;
- SmartGraph::EdgeMap scost(sgr);
- for (int i = 0; i != int(odd_nodes.size()); ++i) {
- sgr.addNode();
- }
- for (int i = 0; i != int(odd_nodes.size()); ++i) {
- for (int j = 0; j != int(odd_nodes.size()); ++j) {
- if (j == i) continue;
- SmartGraph::Edge e =
- sgr.addEdge(sgr.nodeFromId(i), sgr.nodeFromId(j));
- scost[e] = -_cost[_gr.edge(odd_nodes[i], odd_nodes[j])];
- }
- }
-
- // Compute min. cost perfect matching
- MaxWeightedPerfectMatching >
- mwpm(sgr, scost);
- mwpm.run();
-
- for (SmartGraph::EdgeIt e(sgr); e != INVALID; ++e) {
- if (mwpm.matching(e)) {
- tree.push_back( _gr.edge(odd_nodes[sgr.id(sgr.u(e))],
- odd_nodes[sgr.id(sgr.v(e))]) );
- }
- }
-
- // Join the spanning tree and the matching
- sgr.clear();
- for (int i = 0; i != _gr.nodeNum(); ++i) {
- sgr.addNode();
- }
- for (int i = 0; i != int(tree.size()); ++i) {
- int ui = _gr.id(_gr.u(tree[i])),
- vi = _gr.id(_gr.v(tree[i]));
- sgr.addEdge(sgr.nodeFromId(ui), sgr.nodeFromId(vi));
- }
-
- // Compute the tour from the Euler traversal
- SmartGraph::NodeMap visited(sgr, false);
- for (EulerIt e(sgr); e != INVALID; ++e) {
- SmartGraph::Node n = sgr.target(e);
- if (!visited[n]) {
- _path.push_back(_gr(sgr.id(n)));
- visited[n] = true;
- }
- }
-
- _sum = _cost[_gr.edge(_path.back(), _path.front())];
- for (int i = 0; i < int(_path.size())-1; ++i) {
- _sum += _cost[_gr.edge(_path[i], _path[i+1])];
- }
-
- return _sum;
- }
-
- /// @}
-
- /// \name Query Functions
- /// @{
-
- /// \brief The total cost of the found tour.
- ///
- /// This function returns the total cost of the found tour.
- ///
- /// \pre run() must be called before using this function.
- Cost tourCost() const {
- return _sum;
- }
-
- /// \brief Returns a const reference to the node sequence of the
- /// found tour.
- ///
- /// This function returns a const reference to a vector
- /// that stores the node sequence of the found tour.
- ///
- /// \pre run() must be called before using this function.
- const std::vector& tourNodes() const {
- return _path;
- }
-
- /// \brief Gives back the node sequence of the found tour.
- ///
- /// This function copies the node sequence of the found tour into
- /// an STL container through the given output iterator. The
- /// value_type of the container must be FullGraph::Node.
- /// For example,
- /// \code
- /// std::vector nodes(countNodes(graph));
- /// tsp.tourNodes(nodes.begin());
- /// \endcode
- /// or
- /// \code
- /// std::list nodes;
- /// tsp.tourNodes(std::back_inserter(nodes));
- /// \endcode
- ///
- /// \pre run() must be called before using this function.
- template
- void tourNodes(Iterator out) const {
- std::copy(_path.begin(), _path.end(), out);
- }
-
- /// \brief Gives back the found tour as a path.
- ///
- /// This function copies the found tour as a list of arcs/edges into
- /// the given \ref concept::Path "path structure".
- ///
- /// \pre run() must be called before using this function.
- template
- void tour(Path &path) const {
- path.clear();
- for (int i = 0; i < int(_path.size()) - 1; ++i) {
- path.addBack(_gr.arc(_path[i], _path[i+1]));
- }
- if (int(_path.size()) >= 2) {
- path.addBack(_gr.arc(_path.back(), _path.front()));
- }
- }
-
- /// @}
-
- };
-
-}; // namespace lemon
-
-#endif
Index: mon/concepts/bpgraph.h
===================================================================
--- lemon/concepts/bpgraph.h (revision 1217)
+++ (revision )
@@ -1,1026 +1,0 @@
-/* -*- mode: C++; indent-tabs-mode: nil; -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library.
- *
- * Copyright (C) 2003-2010
- * 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.
- *
- */
-
-///\ingroup graph_concepts
-///\file
-///\brief The concept of undirected graphs.
-
-#ifndef LEMON_CONCEPTS_BPGRAPH_H
-#define LEMON_CONCEPTS_BPGRAPH_H
-
-#include
-#include
-#include
-#include
-
-namespace lemon {
- namespace concepts {
-
- /// \ingroup graph_concepts
- ///
- /// \brief Class describing the concept of undirected bipartite graphs.
- ///
- /// This class describes the common interface of all undirected
- /// bipartite graphs.
- ///
- /// Like all concept classes, it only provides an interface
- /// without any sensible implementation. So any general algorithm for
- /// undirected bipartite graphs should compile with this class,
- /// but it will not run properly, of course.
- /// An actual graph implementation like \ref ListBpGraph or
- /// \ref SmartBpGraph may have additional functionality.
- ///
- /// The bipartite graphs also fulfill the concept of \ref Graph
- /// "undirected graphs". Bipartite graphs provide a bipartition of
- /// the node set, namely a red and blue set of the nodes. The
- /// nodes can be iterated with the RedNodeIt and BlueNodeIt in the
- /// two node sets. With RedNodeMap and BlueNodeMap values can be
- /// assigned to the nodes in the two sets.
- ///
- /// The edges of the graph cannot connect two nodes of the same
- /// set. The edges inherent orientation is from the red nodes to
- /// the blue nodes.
- ///
- /// \sa Graph
- class BpGraph {
- private:
- /// BpGraphs are \e not copy constructible. Use bpGraphCopy instead.
- BpGraph(const BpGraph&) {}
- /// \brief Assignment of a graph to another one is \e not allowed.
- /// Use bpGraphCopy instead.
- void operator=(const BpGraph&) {}
-
- public:
- /// Default constructor.
- BpGraph() {}
-
- /// \brief Undirected graphs should be tagged with \c UndirectedTag.
- ///
- /// Undirected graphs should be tagged with \c UndirectedTag.
- ///
- /// This tag helps the \c enable_if technics to make compile time
- /// specializations for undirected graphs.
- typedef True UndirectedTag;
-
- /// The node type of the graph
-
- /// This class identifies a node of the graph. It also serves
- /// as a base class of the node iterators,
- /// thus they convert to this type.
- class Node {
- public:
- /// Default constructor
-
- /// Default constructor.
- /// \warning It sets the object to an undefined value.
- Node() { }
- /// Copy constructor.
-
- /// Copy constructor.
- ///
- Node(const Node&) { }
-
- /// %Invalid constructor \& conversion.
-
- /// Initializes the object to be invalid.
- /// \sa Invalid for more details.
- Node(Invalid) { }
- /// Equality operator
-
- /// Equality operator.
- ///
- /// Two iterators are equal if and only if they point to the
- /// same object or both are \c INVALID.
- bool operator==(Node) const { return true; }
-
- /// Inequality operator
-
- /// Inequality operator.
- bool operator!=(Node) const { return true; }
-
- /// Artificial ordering operator.
-
- /// Artificial ordering operator.
- ///
- /// \note This operator only has to define some strict ordering of
- /// the items; this order has nothing to do with the iteration
- /// ordering of the items.
- bool operator<(Node) const { return false; }
-
- };
-
- /// Class to represent red nodes.
-
- /// This class represents the red nodes of the graph. It does
- /// not supposed to be used directly, because the nodes can be
- /// represented as Node instances. This class can be used as
- /// template parameter for special map classes.
- class RedNode : public Node {
- public:
- /// Default constructor
-
- /// Default constructor.
- /// \warning It sets the object to an undefined value.
- RedNode() { }
- /// Copy constructor.
-
- /// Copy constructor.
- ///
- RedNode(const RedNode&) : Node() { }
-
- /// %Invalid constructor \& conversion.
-
- /// Initializes the object to be invalid.
- /// \sa Invalid for more details.
- RedNode(Invalid) { }
-
- };
-
- /// Class to represent blue nodes.
-
- /// This class represents the blue nodes of the graph. It does
- /// not supposed to be used directly, because the nodes can be
- /// represented as Node instances. This class can be used as
- /// template parameter for special map classes.
- class BlueNode : public Node {
- public:
- /// Default constructor
-
- /// Default constructor.
- /// \warning It sets the object to an undefined value.
- BlueNode() { }
- /// Copy constructor.
-
- /// Copy constructor.
- ///
- BlueNode(const BlueNode&) : Node() { }
-
- /// %Invalid constructor \& conversion.
-
- /// Initializes the object to be invalid.
- /// \sa Invalid for more details.
- BlueNode(Invalid) { }
-
- };
-
- /// Iterator class for the red nodes.
-
- /// This iterator goes through each red node of the graph.
- /// Its usage is quite simple, for example, you can count the number
- /// of red nodes in a graph \c g of type \c %BpGraph like this:
- ///\code
- /// int count=0;
- /// for (BpGraph::RedNodeIt n(g); n!=INVALID; ++n) ++count;
- ///\endcode
- class RedNodeIt : public RedNode {
- public:
- /// Default constructor
-
- /// Default constructor.
- /// \warning It sets the iterator to an undefined value.
- RedNodeIt() { }
- /// Copy constructor.
-
- /// Copy constructor.
- ///
- RedNodeIt(const RedNodeIt& n) : RedNode(n) { }
- /// %Invalid constructor \& conversion.
-
- /// Initializes the iterator to be invalid.
- /// \sa Invalid for more details.
- RedNodeIt(Invalid) { }
- /// Sets the iterator to the first red node.
-
- /// Sets the iterator to the first red node of the given
- /// digraph.
- explicit RedNodeIt(const BpGraph&) { }
- /// Sets the iterator to the given red node.
-
- /// Sets the iterator to the given red node of the given
- /// digraph.
- RedNodeIt(const BpGraph&, const RedNode&) { }
- /// Next node.
-
- /// Assign the iterator to the next red node.
- ///
- RedNodeIt& operator++() { return *this; }
- };
-
- /// Iterator class for the blue nodes.
-
- /// This iterator goes through each blue node of the graph.
- /// Its usage is quite simple, for example, you can count the number
- /// of blue nodes in a graph \c g of type \c %BpGraph like this:
- ///\code
- /// int count=0;
- /// for (BpGraph::BlueNodeIt n(g); n!=INVALID; ++n) ++count;
- ///\endcode
- class BlueNodeIt : public BlueNode {
- public:
- /// Default constructor
-
- /// Default constructor.
- /// \warning It sets the iterator to an undefined value.
- BlueNodeIt() { }
- /// Copy constructor.
-
- /// Copy constructor.
- ///
- BlueNodeIt(const BlueNodeIt& n) : BlueNode(n) { }
- /// %Invalid constructor \& conversion.
-
- /// Initializes the iterator to be invalid.
- /// \sa Invalid for more details.
- BlueNodeIt(Invalid) { }
- /// Sets the iterator to the first blue node.
-
- /// Sets the iterator to the first blue node of the given
- /// digraph.
- explicit BlueNodeIt(const BpGraph&) { }
- /// Sets the iterator to the given blue node.
-
- /// Sets the iterator to the given blue node of the given
- /// digraph.
- BlueNodeIt(const BpGraph&, const BlueNode&) { }
- /// Next node.
-
- /// Assign the iterator to the next blue node.
- ///
- BlueNodeIt& operator++() { return *this; }
- };
-
- /// Iterator class for the nodes.
-
- /// This iterator goes through each node of the graph.
- /// Its usage is quite simple, for example, you can count the number
- /// of nodes in a graph \c g of type \c %BpGraph like this:
- ///\code
- /// int count=0;
- /// for (BpGraph::NodeIt n(g); n!=INVALID; ++n) ++count;
- ///\endcode
- class NodeIt : public Node {
- public:
- /// Default constructor
-
- /// Default constructor.
- /// \warning It sets the iterator to an undefined value.
- NodeIt() { }
- /// Copy constructor.
-
- /// Copy constructor.
- ///
- NodeIt(const NodeIt& n) : Node(n) { }
- /// %Invalid constructor \& conversion.
-
- /// Initializes the iterator to be invalid.
- /// \sa Invalid for more details.
- NodeIt(Invalid) { }
- /// Sets the iterator to the first node.
-
- /// Sets the iterator to the first node of the given digraph.
- ///
- explicit NodeIt(const BpGraph&) { }
- /// Sets the iterator to the given node.
-
- /// Sets the iterator to the given node of the given digraph.
- ///
- NodeIt(const BpGraph&, const Node&) { }
- /// Next node.
-
- /// Assign the iterator to the next node.
- ///
- NodeIt& operator++() { return *this; }
- };
-
-
- /// The edge type of the graph
-
- /// This class identifies an edge of the graph. It also serves
- /// as a base class of the edge iterators,
- /// thus they will convert to this type.
- class Edge {
- public:
- /// Default constructor
-
- /// Default constructor.
- /// \warning It sets the object to an undefined value.
- Edge() { }
- /// Copy constructor.
-
- /// Copy constructor.
- ///
- Edge(const Edge&) { }
- /// %Invalid constructor \& conversion.
-
- /// Initializes the object to be invalid.
- /// \sa Invalid for more details.
- Edge(Invalid) { }
- /// Equality operator
-
- /// Equality operator.
- ///
- /// Two iterators are equal if and only if they point to the
- /// same object or both are \c INVALID.
- bool operator==(Edge) const { return true; }
- /// Inequality operator
-
- /// Inequality operator.
- bool operator!=(Edge) const { return true; }
-
- /// Artificial ordering operator.
-
- /// Artificial ordering operator.
- ///
- /// \note This operator only has to define some strict ordering of
- /// the edges; this order has nothing to do with the iteration
- /// ordering of the edges.
- bool operator<(Edge) const { return false; }
- };
-
- /// Iterator class for the edges.
-
- /// This iterator goes through each edge of the graph.
- /// Its usage is quite simple, for example, you can count the number
- /// of edges in a graph \c g of type \c %BpGraph as follows:
- ///\code
- /// int count=0;
- /// for(BpGraph::EdgeIt e(g); e!=INVALID; ++e) ++count;
- ///\endcode
- class EdgeIt : public Edge {
- public:
- /// Default constructor
-
- /// Default constructor.
- /// \warning It sets the iterator to an undefined value.
- EdgeIt() { }
- /// Copy constructor.
-
- /// Copy constructor.
- ///
- EdgeIt(const EdgeIt& e) : Edge(e) { }
- /// %Invalid constructor \& conversion.
-
- /// Initializes the iterator to be invalid.
- /// \sa Invalid for more details.
- EdgeIt(Invalid) { }
- /// Sets the iterator to the first edge.
-
- /// Sets the iterator to the first edge of the given graph.
- ///
- explicit EdgeIt(const BpGraph&) { }
- /// Sets the iterator to the given edge.
-
- /// Sets the iterator to the given edge of the given graph.
- ///
- EdgeIt(const BpGraph&, const Edge&) { }
- /// Next edge
-
- /// Assign the iterator to the next edge.
- ///
- EdgeIt& operator++() { return *this; }
- };
-
- /// Iterator class for the incident edges of a node.
-
- /// This iterator goes trough the incident undirected edges
- /// of a certain node of a graph.
- /// Its usage is quite simple, for example, you can compute the
- /// degree (i.e. the number of incident edges) of a node \c n
- /// in a graph \c g of type \c %BpGraph as follows.
- ///
- ///\code
- /// int count=0;
- /// for(BpGraph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
- ///\endcode
- ///
- /// \warning Loop edges will be iterated twice.
- class IncEdgeIt : public Edge {
- public:
- /// Default constructor
-
- /// Default constructor.
- /// \warning It sets the iterator to an undefined value.
- IncEdgeIt() { }
- /// Copy constructor.
-
- /// Copy constructor.
- ///
- IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
- /// %Invalid constructor \& conversion.
-
- /// Initializes the iterator to be invalid.
- /// \sa Invalid for more details.
- IncEdgeIt(Invalid) { }
- /// Sets the iterator to the first incident edge.
-
- /// Sets the iterator to the first incident edge of the given node.
- ///
- IncEdgeIt(const BpGraph&, const Node&) { }
- /// Sets the iterator to the given edge.
-
- /// Sets the iterator to the given edge of the given graph.
- ///
- IncEdgeIt(const BpGraph&, const Edge&) { }
- /// Next incident edge
-
- /// Assign the iterator to the next incident edge
- /// of the corresponding node.
- IncEdgeIt& operator++() { return *this; }
- };
-
- /// The arc type of the graph
-
- /// This class identifies a directed arc of the graph. It also serves
- /// as a base class of the arc iterators,
- /// thus they will convert to this type.
- class Arc {
- public:
- /// Default constructor
-
- /// Default constructor.
- /// \warning It sets the object to an undefined value.
- Arc() { }
- /// Copy constructor.
-
- /// Copy constructor.
- ///
- Arc(const Arc&) { }
- /// %Invalid constructor \& conversion.
-
- /// Initializes the object to be invalid.
- /// \sa Invalid for more details.
- Arc(Invalid) { }
- /// Equality operator
-
- /// Equality operator.
- ///
- /// Two iterators are equal if and only if they point to the
- /// same object or both are \c INVALID.
- bool operator==(Arc) const { return true; }
- /// Inequality operator
-
- /// Inequality operator.
- bool operator!=(Arc) const { return true; }
-
- /// Artificial ordering operator.
-
- /// Artificial ordering operator.
- ///
- /// \note This operator only has to define some strict ordering of
- /// the arcs; this order has nothing to do with the iteration
- /// ordering of the arcs.
- bool operator<(Arc) const { return false; }
-
- /// Converison to \c Edge
-
- /// Converison to \c Edge.
- ///
- operator Edge() const { return Edge(); }
- };
-
- /// Iterator class for the arcs.
-
- /// This iterator goes through each directed arc of the graph.
- /// Its usage is quite simple, for example, you can count the number
- /// of arcs in a graph \c g of type \c %BpGraph as follows:
- ///\code
- /// int count=0;
- /// for(BpGraph::ArcIt a(g); a!=INVALID; ++a) ++count;
- ///\endcode
- class ArcIt : public Arc {
- public:
- /// Default constructor
-
- /// Default constructor.
- /// \warning It sets the iterator to an undefined value.
- ArcIt() { }
- /// Copy constructor.
-
- /// Copy constructor.
- ///
- ArcIt(const ArcIt& e) : Arc(e) { }
- /// %Invalid constructor \& conversion.
-
- /// Initializes the iterator to be invalid.
- /// \sa Invalid for more details.
- ArcIt(Invalid) { }
- /// Sets the iterator to the first arc.
-
- /// Sets the iterator to the first arc of the given graph.
- ///
- explicit ArcIt(const BpGraph &g) { ignore_unused_variable_warning(g); }
- /// Sets the iterator to the given arc.
-
- /// Sets the iterator to the given arc of the given graph.
- ///
- ArcIt(const BpGraph&, const Arc&) { }
- /// Next arc
-
- /// Assign the iterator to the next arc.
- ///
- ArcIt& operator++() { return *this; }
- };
-
- /// Iterator class for the outgoing arcs of a node.
-
- /// This iterator goes trough the \e outgoing directed arcs of a
- /// certain node of a graph.
- /// Its usage is quite simple, for example, you can count the number
- /// of outgoing arcs of a node \c n
- /// in a graph \c g of type \c %BpGraph as follows.
- ///\code
- /// int count=0;
- /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
- ///\endcode
- class OutArcIt : public Arc {
- public:
- /// Default constructor
-
- /// Default constructor.
- /// \warning It sets the iterator to an undefined value.
- OutArcIt() { }
- /// Copy constructor.
-
- /// Copy constructor.
- ///
- OutArcIt(const OutArcIt& e) : Arc(e) { }
- /// %Invalid constructor \& conversion.
-
- /// Initializes the iterator to be invalid.
- /// \sa Invalid for more details.
- OutArcIt(Invalid) { }
- /// Sets the iterator to the first outgoing arc.
-
- /// Sets the iterator to the first outgoing arc of the given node.
- ///
- OutArcIt(const BpGraph& n, const Node& g) {
- ignore_unused_variable_warning(n);
- ignore_unused_variable_warning(g);
- }
- /// Sets the iterator to the given arc.
-
- /// Sets the iterator to the given arc of the given graph.
- ///
- OutArcIt(const BpGraph&, const Arc&) { }
- /// Next outgoing arc
-
- /// Assign the iterator to the next
- /// outgoing arc of the corresponding node.
- OutArcIt& operator++() { return *this; }
- };
-
- /// Iterator class for the incoming arcs of a node.
-
- /// This iterator goes trough the \e incoming directed arcs of a
- /// certain node of a graph.
- /// Its usage is quite simple, for example, you can count the number
- /// of incoming arcs of a node \c n
- /// in a graph \c g of type \c %BpGraph as follows.
- ///\code
- /// int count=0;
- /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
- ///\endcode
- class InArcIt : public Arc {
- public:
- /// Default constructor
-
- /// Default constructor.
- /// \warning It sets the iterator to an undefined value.
- InArcIt() { }
- /// Copy constructor.
-
- /// Copy constructor.
- ///
- InArcIt(const InArcIt& e) : Arc(e) { }
- /// %Invalid constructor \& conversion.
-
- /// Initializes the iterator to be invalid.
- /// \sa Invalid for more details.
- InArcIt(Invalid) { }
- /// Sets the iterator to the first incoming arc.
-
- /// Sets the iterator to the first incoming arc of the given node.
- ///
- InArcIt(const BpGraph& g, const Node& n) {
- ignore_unused_variable_warning(n);
- ignore_unused_variable_warning(g);
- }
- /// Sets the iterator to the given arc.
-
- /// Sets the iterator to the given arc of the given graph.
- ///
- InArcIt(const BpGraph&, const Arc&) { }
- /// Next incoming arc
-
- /// Assign the iterator to the next
- /// incoming arc of the corresponding node.
- InArcIt& operator++() { return *this; }
- };
-
- /// \brief Standard graph map type for the nodes.
- ///
- /// Standard graph map type for the nodes.
- /// It conforms to the ReferenceMap concept.
- template
- class NodeMap : public ReferenceMap
- {
- public:
-
- /// Constructor
- explicit NodeMap(const BpGraph&) { }
- /// Constructor with given initial value
- NodeMap(const BpGraph&, T) { }
-
- private:
- ///Copy constructor
- NodeMap(const NodeMap& nm) :
- ReferenceMap(nm) { }
- ///Assignment operator
- template
- NodeMap& operator=(const CMap&) {
- checkConcept, CMap>();
- return *this;
- }
- };
-
- /// \brief Standard graph map type for the red nodes.
- ///
- /// Standard graph map type for the red nodes.
- /// It conforms to the ReferenceMap concept.
- template
- class RedNodeMap : public ReferenceMap
- {
- public:
-
- /// Constructor
- explicit RedNodeMap(const BpGraph&) { }
- /// Constructor with given initial value
- RedNodeMap(const BpGraph&, T) { }
-
- private:
- ///Copy constructor
- RedNodeMap(const RedNodeMap& nm) :
- ReferenceMap(nm) { }
- ///Assignment operator
- template
- RedNodeMap& operator=(const CMap&) {
- checkConcept, CMap>();
- return *this;
- }
- };
-
- /// \brief Standard graph map type for the blue nodes.
- ///
- /// Standard graph map type for the blue nodes.
- /// It conforms to the ReferenceMap concept.
- template
- class BlueNodeMap : public ReferenceMap
- {
- public:
-
- /// Constructor
- explicit BlueNodeMap(const BpGraph&) { }
- /// Constructor with given initial value
- BlueNodeMap(const BpGraph&, T) { }
-
- private:
- ///Copy constructor
- BlueNodeMap(const BlueNodeMap& nm) :
- ReferenceMap(nm) { }
- ///Assignment operator
- template
- BlueNodeMap& operator=(const CMap&) {
- checkConcept, CMap>();
- return *this;
- }
- };
-
- /// \brief Standard graph map type for the arcs.
- ///
- /// Standard graph map type for the arcs.
- /// It conforms to the ReferenceMap concept.
- template
- class ArcMap : public ReferenceMap
- {
- public:
-
- /// Constructor
- explicit ArcMap(const BpGraph&) { }
- /// Constructor with given initial value
- ArcMap(const BpGraph&, T) { }
-
- private:
- ///Copy constructor
- ArcMap(const ArcMap& em) :
- ReferenceMap(em) { }
- ///Assignment operator
- template
- ArcMap& operator=(const CMap&) {
- checkConcept, CMap>();
- return *this;
- }
- };
-
- /// \brief Standard graph map type for the edges.
- ///
- /// Standard graph map type for the edges.
- /// It conforms to the ReferenceMap concept.
- template
- class EdgeMap : public ReferenceMap
- {
- public:
-
- /// Constructor
- explicit EdgeMap(const BpGraph&) { }
- /// Constructor with given initial value
- EdgeMap(const BpGraph&, T) { }
-
- private:
- ///Copy constructor
- EdgeMap(const EdgeMap& em) :
- ReferenceMap(em) {}
- ///Assignment operator
- template
- EdgeMap& operator=(const CMap&) {
- checkConcept, CMap>();
- return *this;
- }
- };
-
- /// \brief Gives back %true for red nodes.
- ///
- /// Gives back %true for red nodes.
- bool red(const Node&) const { return true; }
-
- /// \brief Gives back %true for blue nodes.
- ///
- /// Gives back %true for blue nodes.
- bool blue(const Node&) const { return true; }
-
- /// \brief Converts the node to red node object.
- ///
- /// This function converts unsafely the node to red node
- /// object. It should be called only if the node is from the red
- /// partition or INVALID.
- RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); }
-
- /// \brief Converts the node to blue node object.
- ///
- /// This function converts unsafely the node to blue node
- /// object. It should be called only if the node is from the red
- /// partition or INVALID.
- BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); }
-
- /// \brief Converts the node to red node object.
- ///
- /// This function converts safely the node to red node
- /// object. If the node is not from the red partition, then it
- /// returns INVALID.
- RedNode asRedNode(const Node&) const { return RedNode(); }
-
- /// \brief Converts the node to blue node object.
- ///
- /// This function converts unsafely the node to blue node
- /// object. If the node is not from the blue partition, then it
- /// returns INVALID.
- BlueNode asBlueNode(const Node&) const { return BlueNode(); }
-
- /// \brief Gives back the red end node of the edge.
- ///
- /// Gives back the red end node of the edge.
- RedNode redNode(const Edge&) const { return RedNode(); }
-
- /// \brief Gives back the blue end node of the edge.
- ///
- /// Gives back the blue end node of the edge.
- BlueNode blueNode(const Edge&) const { return BlueNode(); }
-
- /// \brief The first node of the edge.
- ///
- /// It is a synonim for the \c redNode().
- Node u(Edge) const { return INVALID; }
-
- /// \brief The second node of the edge.
- ///
- /// It is a synonim for the \c blueNode().
- Node v(Edge) const { return INVALID; }
-
- /// \brief The source node of the arc.
- ///
- /// Returns the source node of the given arc.
- Node source(Arc) const { return INVALID; }
-
- /// \brief The target node of the arc.
- ///
- /// Returns the target node of the given arc.
- Node target(Arc) const { return INVALID; }
-
- /// \brief The ID of the node.
- ///
- /// Returns the ID of the given node.
- int id(Node) const { return -1; }
-
- /// \brief The red ID of the node.
- ///
- /// Returns the red ID of the given node.
- int id(RedNode) const { return -1; }
-
- /// \brief The blue ID of the node.
- ///
- /// Returns the blue ID of the given node.
- int id(BlueNode) const { return -1; }
-
- /// \brief The ID of the edge.
- ///
- /// Returns the ID of the given edge.
- int id(Edge) const { return -1; }
-
- /// \brief The ID of the arc.
- ///
- /// Returns the ID of the given arc.
- int id(Arc) const { return -1; }
-
- /// \brief The node with the given ID.
- ///
- /// Returns the node with the given ID.
- /// \pre The argument should be a valid node ID in the graph.
- Node nodeFromId(int) const { return INVALID; }
-
- /// \brief The edge with the given ID.
- ///
- /// Returns the edge with the given ID.
- /// \pre The argument should be a valid edge ID in the graph.
- Edge edgeFromId(int) const { return INVALID; }
-
- /// \brief The arc with the given ID.
- ///
- /// Returns the arc with the given ID.
- /// \pre The argument should be a valid arc ID in the graph.
- Arc arcFromId(int) const { return INVALID; }
-
- /// \brief An upper bound on the node IDs.
- ///
- /// Returns an upper bound on the node IDs.
- int maxNodeId() const { return -1; }
-
- /// \brief An upper bound on the red IDs.
- ///
- /// Returns an upper bound on the red IDs.
- int maxRedId() const { return -1; }
-
- /// \brief An upper bound on the blue IDs.
- ///
- /// Returns an upper bound on the blue IDs.
- int maxBlueId() const { return -1; }
-
- /// \brief An upper bound on the edge IDs.
- ///
- /// Returns an upper bound on the edge IDs.
- int maxEdgeId() const { return -1; }
-
- /// \brief An upper bound on the arc IDs.
- ///
- /// Returns an upper bound on the arc IDs.
- int maxArcId() const { return -1; }
-
- /// \brief The direction of the arc.
- ///
- /// Returns \c true if the given arc goes from a red node to a blue node.
- bool direction(Arc) const { return true; }
-
- /// \brief Direct the edge.
- ///
- /// Direct the given edge. The returned arc
- /// represents the given edge and its direction comes
- /// from the bool parameter. If it is \c true, then the source of the node
- /// will be a red node.
- Arc direct(Edge, bool) const {
- return INVALID;
- }
-
- /// \brief Direct the edge.
- ///
- /// Direct the given edge. The returned arc represents the given
- /// edge and its source node is the given node.
- Arc direct(Edge, Node) const {
- return INVALID;
- }
-
- /// \brief The oppositely directed arc.
- ///
- /// Returns the oppositely directed arc representing the same edge.
- Arc oppositeArc(Arc) const { return INVALID; }
-
- /// \brief The opposite node on the edge.
- ///
- /// Returns the opposite node on the given edge.
- Node oppositeNode(Node, Edge) const { return INVALID; }
-
- void first(Node&) const {}
- void next(Node&) const {}
-
- void firstRed(RedNode&) const {}
- void nextRed(RedNode&) const {}
-
- void firstBlue(BlueNode&) const {}
- void nextBlue(BlueNode&) const {}
-
- void first(Edge&) const {}
- void next(Edge&) const {}
-
- void first(Arc&) const {}
- void next(Arc&) const {}
-
- void firstOut(Arc&, Node) const {}
- void nextOut(Arc&) const {}
-
- void firstIn(Arc&, Node) const {}
- void nextIn(Arc&) const {}
-
- void firstInc(Edge &, bool &, const Node &) const {}
- void nextInc(Edge &, bool &) const {}
-
- // The second parameter is dummy.
- Node fromId(int, Node) const { return INVALID; }
- // The second parameter is dummy.
- Edge fromId(int, Edge) const { return INVALID; }
- // The second parameter is dummy.
- Arc fromId(int, Arc) const { return INVALID; }
-
- // Dummy parameter.
- int maxId(Node) const { return -1; }
- // Dummy parameter.
- int maxId(RedNode) const { return -1; }
- // Dummy parameter.
- int maxId(BlueNode) const { return -1; }
- // Dummy parameter.
- int maxId(Edge) const { return -1; }
- // Dummy parameter.
- int maxId(Arc) const { return -1; }
-
- /// \brief The base node of the iterator.
- ///
- /// Returns the base node of the given incident edge iterator.
- Node baseNode(IncEdgeIt) const { return INVALID; }
-
- /// \brief The running node of the iterator.
- ///
- /// Returns the running node of the given incident edge iterator.
- Node runningNode(IncEdgeIt) const { return INVALID; }
-
- /// \brief The base node of the iterator.
- ///
- /// Returns the base node of the given outgoing arc iterator
- /// (i.e. the source node of the corresponding arc).
- Node baseNode(OutArcIt) const { return INVALID; }
-
- /// \brief The running node of the iterator.
- ///
- /// Returns the running node of the given outgoing arc iterator
- /// (i.e. the target node of the corresponding arc).
- Node runningNode(OutArcIt) const { return INVALID; }
-
- /// \brief The base node of the iterator.
- ///
- /// Returns the base node of the given incoming arc iterator
- /// (i.e. the target node of the corresponding arc).
- Node baseNode(InArcIt) const { return INVALID; }
-
- /// \brief The running node of the iterator.
- ///
- /// Returns the running node of the given incoming arc iterator
- /// (i.e. the source node of the corresponding arc).
- Node runningNode(InArcIt) const { return INVALID; }
-
- template
- struct Constraints {
- void constraints() {
- checkConcept();
- checkConcept, _BpGraph>();
- checkConcept, _BpGraph>();
- checkConcept, _BpGraph>();
- }
- };
-
- };
-
- }
-
-}
-
-#endif
Index: lemon/concepts/digraph.h
===================================================================
--- lemon/concepts/digraph.h (revision 1217)
+++ lemon/concepts/digraph.h (revision 956)
@@ -410,5 +410,5 @@
/// \brief The base node of the iterator.
///
- /// Returns the base node of the given incoming arc iterator
+ /// Returns the base node of the given incomming arc iterator
/// (i.e. the target node of the corresponding arc).
Node baseNode(InArcIt) const { return INVALID; }
@@ -416,5 +416,5 @@
/// \brief The running node of the iterator.
///
- /// Returns the running node of the given incoming arc iterator
+ /// Returns the running node of the given incomming arc iterator
/// (i.e. the source node of the corresponding arc).
Node runningNode(InArcIt) const { return INVALID; }
Index: lemon/concepts/graph.h
===================================================================
--- lemon/concepts/graph.h (revision 1217)
+++ lemon/concepts/graph.h (revision 956)
@@ -73,8 +73,8 @@
class Graph {
private:
- /// Graphs are \e not copy constructible. Use GraphCopy instead.
+ /// Graphs are \e not copy constructible. Use DigraphCopy instead.
Graph(const Graph&) {}
/// \brief Assignment of a graph to another one is \e not allowed.
- /// Use GraphCopy instead.
+ /// Use DigraphCopy instead.
void operator=(const Graph&) {}
@@ -758,5 +758,5 @@
/// \brief The base node of the iterator.
///
- /// Returns the base node of the given incoming arc iterator
+ /// Returns the base node of the given incomming arc iterator
/// (i.e. the target node of the corresponding arc).
Node baseNode(InArcIt) const { return INVALID; }
@@ -764,5 +764,5 @@
/// \brief The running node of the iterator.
///
- /// Returns the running node of the given incoming arc iterator
+ /// Returns the running node of the given incomming arc iterator
/// (i.e. the source node of the corresponding arc).
Node runningNode(InArcIt) const { return INVALID; }
Index: lemon/concepts/graph_components.h
===================================================================
--- lemon/concepts/graph_components.h (revision 1217)
+++ lemon/concepts/graph_components.h (revision 1175)
@@ -300,170 +300,4 @@
};
- /// \brief Base skeleton class for undirected bipartite graphs.
- ///
- /// This class describes the base interface of undirected
- /// bipartite graph types. All bipartite graph %concepts have to
- /// conform to this class. It extends the interface of \ref
- /// BaseGraphComponent 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 BaseBpGraphComponent : public BaseGraphComponent {
- public:
-
- typedef BaseBpGraphComponent BpGraph;
-
- typedef BaseDigraphComponent::Node Node;
- typedef BaseDigraphComponent::Arc Arc;
-
- /// \brief Class to represent red nodes.
- ///
- /// This class represents the red nodes of the graph. The red
- /// nodes can also be used as normal nodes.
- class RedNode : public Node {
- typedef Node Parent;
-
- public:
- /// \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.
- RedNode() {}
-
- /// \brief Copy constructor.
- ///
- /// Copy constructor.
- RedNode(const RedNode &) : Parent() {}
-
- /// \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.
- RedNode(Invalid) {}
- };
-
- /// \brief Class to represent blue nodes.
- ///
- /// This class represents the blue nodes of the graph. The blue
- /// nodes can also be used as normal nodes.
- class BlueNode : public Node {
- typedef Node Parent;
-
- public:
- /// \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.
- BlueNode() {}
-
- /// \brief Copy constructor.
- ///
- /// Copy constructor.
- BlueNode(const BlueNode &) : Parent() {}
-
- /// \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.
- BlueNode(Invalid) {}
-
- /// \brief Constructor for conversion from a node.
- ///
- /// Constructor for conversion from a node. The conversion can
- /// be invalid, since the Node can be member of the red
- /// set.
- BlueNode(const Node&) {}
- };
-
- /// \brief Gives back %true for red nodes.
- ///
- /// Gives back %true for red nodes.
- bool red(const Node&) const { return true; }
-
- /// \brief Gives back %true for blue nodes.
- ///
- /// Gives back %true for blue nodes.
- bool blue(const Node&) const { return true; }
-
- /// \brief Gives back the red end node of the edge.
- ///
- /// Gives back the red end node of the edge.
- RedNode redNode(const Edge&) const { return RedNode(); }
-
- /// \brief Gives back the blue end node of the edge.
- ///
- /// Gives back the blue end node of the edge.
- BlueNode blueNode(const Edge&) const { return BlueNode(); }
-
- /// \brief Converts the node to red node object.
- ///
- /// This function converts unsafely the node to red node
- /// object. It should be called only if the node is from the red
- /// partition or INVALID.
- RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); }
-
- /// \brief Converts the node to blue node object.
- ///
- /// This function converts unsafely the node to blue node
- /// object. It should be called only if the node is from the red
- /// partition or INVALID.
- BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); }
-
- /// \brief Converts the node to red node object.
- ///
- /// This function converts safely the node to red node
- /// object. If the node is not from the red partition, then it
- /// returns INVALID.
- RedNode asRedNode(const Node&) const { return RedNode(); }
-
- /// \brief Converts the node to blue node object.
- ///
- /// This function converts unsafely the node to blue node
- /// object. If the node is not from the blue partition, then it
- /// returns INVALID.
- BlueNode asBlueNode(const Node&) const { return BlueNode(); }
-
- template
- struct Constraints {
- typedef typename _BpGraph::Node Node;
- typedef typename _BpGraph::RedNode RedNode;
- typedef typename _BpGraph::BlueNode BlueNode;
- typedef typename _BpGraph::Arc Arc;
- typedef typename _BpGraph::Edge Edge;
-
- void constraints() {
- checkConcept();
- checkConcept, RedNode>();
- checkConcept, BlueNode>();
- {
- Node n;
- RedNode rn;
- BlueNode bn;
- Node rnan = rn;
- Node bnan = bn;
- Edge e;
- bool b;
- b = bpgraph.red(rnan);
- b = bpgraph.blue(bnan);
- rn = bpgraph.redNode(e);
- bn = bpgraph.blueNode(e);
- rn = bpgraph.asRedNodeUnsafe(rnan);
- bn = bpgraph.asBlueNodeUnsafe(bnan);
- rn = bpgraph.asRedNode(rnan);
- bn = bpgraph.asBlueNode(bnan);
- ignore_unused_variable_warning(b);
- }
- }
-
- const _BpGraph& bpgraph;
- };
-
- };
-
/// \brief Skeleton class for \e idable directed graphs.
///
@@ -598,68 +432,4 @@
};
- /// \brief Skeleton class for \e idable undirected bipartite graphs.
- ///
- /// This class describes the interface of \e idable undirected
- /// bipartite graphs. It extends \ref IDableGraphComponent with
- /// the core ID functions of undirected bipartite graphs. Beside
- /// the regular node ids, this class also provides ids within the
- /// the red and blue sets of the nodes. This concept is part of
- /// the BpGraph concept.
- template
- class IDableBpGraphComponent : public IDableGraphComponent {
- public:
-
- typedef BAS Base;
- typedef IDableGraphComponent Parent;
- typedef typename Base::Node Node;
- typedef typename Base::RedNode RedNode;
- typedef typename Base::BlueNode BlueNode;
-
- using Parent::id;
-
- /// \brief Return a unique integer id for the given node in the red set.
- ///
- /// Return a unique integer id for the given node in the red set.
- int id(const RedNode&) const { return -1; }
-
- /// \brief Return a unique integer id for the given node in the blue set.
- ///
- /// Return a unique integer id for the given node in the blue set.
- int id(const BlueNode&) const { return -1; }
-
- /// \brief Return an integer greater or equal to the maximum
- /// node id in the red set.
- ///
- /// Return an integer greater or equal to the maximum
- /// node id in the red set.
- int maxRedId() const { return -1; }
-
- /// \brief Return an integer greater or equal to the maximum
- /// node id in the blue set.
- ///
- /// Return an integer greater or equal to the maximum
- /// node id in the blue set.
- int maxBlueId() const { return -1; }
-
- template
- struct Constraints {
-
- void constraints() {
- checkConcept, _BpGraph>();
- typename _BpGraph::Node node;
- typename _BpGraph::RedNode red;
- typename _BpGraph::BlueNode blue;
- int rid = bpgraph.id(red);
- int bid = bpgraph.id(blue);
- rid = bpgraph.maxRedId();
- bid = bpgraph.maxBlueId();
- ignore_unused_variable_warning(rid);
- ignore_unused_variable_warning(bid);
- }
-
- const _BpGraph& bpgraph;
- };
- };
-
/// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
///
@@ -876,13 +646,13 @@
void next(Arc&) const {}
- /// \brief Return the first arc incoming to the given node.
- ///
- /// This function gives back the first arc incoming to the
+ /// \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 Return the next arc incoming to the given node.
- ///
- /// This function gives back the next arc incoming to the
+ /// \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 {}
@@ -1135,95 +905,4 @@
};
- /// \brief Skeleton class for iterable undirected bipartite graphs.
- ///
- /// This class describes the interface of iterable undirected
- /// bipartite graphs. It extends \ref IterableGraphComponent with
- /// the core iterable interface of undirected bipartite graphs.
- /// This concept is part of the BpGraph concept.
- template
- class IterableBpGraphComponent : public IterableGraphComponent {
- public:
-
- typedef BAS Base;
- typedef typename Base::Node Node;
- typedef typename Base::RedNode RedNode;
- typedef typename Base::BlueNode BlueNode;
- typedef typename Base::Arc Arc;
- typedef typename Base::Edge Edge;
-
- typedef IterableBpGraphComponent BpGraph;
-
- using IterableGraphComponent::first;
- using IterableGraphComponent::next;
-
- /// \name Base Iteration
- ///
- /// This interface provides functions for iteration on red and blue nodes.
- ///
- /// @{
-
- /// \brief Return the first red node.
- ///
- /// This function gives back the first red node in the iteration order.
- void first(RedNode&) const {}
-
- /// \brief Return the next red node.
- ///
- /// This function gives back the next red node in the iteration order.
- void next(RedNode&) const {}
-
- /// \brief Return the first blue node.
- ///
- /// This function gives back the first blue node in the iteration order.
- void first(BlueNode&) const {}
-
- /// \brief Return the next blue node.
- ///
- /// This function gives back the next blue node in the iteration order.
- void next(BlueNode&) const {}
-
-
- /// @}
-
- /// \name Class Based Iteration
- ///
- /// This interface provides iterator classes for red and blue nodes.
- ///
- /// @{
-
- /// \brief This iterator goes through each red node.
- ///
- /// This iterator goes through each red node.
- typedef GraphItemIt RedNodeIt;
-
- /// \brief This iterator goes through each blue node.
- ///
- /// This iterator goes through each blue node.
- typedef GraphItemIt BlueNodeIt;
-
- /// @}
-
- template
- struct Constraints {
- void constraints() {
- checkConcept, _BpGraph>();
-
- typename _BpGraph::RedNode rn(INVALID);
- bpgraph.first(rn);
- bpgraph.next(rn);
- typename _BpGraph::BlueNode bn(INVALID);
- bpgraph.first(bn);
- bpgraph.next(bn);
-
- checkConcept,
- typename _BpGraph::RedNodeIt>();
- checkConcept,
- typename _BpGraph::BlueNodeIt>();
- }
-
- const _BpGraph& bpgraph;
- };
- };
-
/// \brief Skeleton class for alterable directed graphs.
///
@@ -1251,12 +930,9 @@
ArcNotifier;
- mutable NodeNotifier node_notifier;
- mutable ArcNotifier arc_notifier;
-
/// \brief Return the node alteration notifier.
///
/// This function gives back the node alteration notifier.
NodeNotifier& notifier(Node) const {
- return node_notifier;
+ return NodeNotifier();
}
@@ -1265,5 +941,5 @@
/// This function gives back the arc alteration notifier.
ArcNotifier& notifier(Arc) const {
- return arc_notifier;
+ return ArcNotifier();
}
@@ -1301,5 +977,4 @@
typedef BAS Base;
- typedef AlterableDigraphComponent Parent;
typedef typename Base::Edge Edge;
@@ -1309,13 +984,9 @@
EdgeNotifier;
- mutable EdgeNotifier edge_notifier;
-
- using Parent::notifier;
-
/// \brief Return the edge alteration notifier.
///
/// This function gives back the edge alteration notifier.
EdgeNotifier& notifier(Edge) const {
- return edge_notifier;
+ return EdgeNotifier();
}
@@ -1331,66 +1002,4 @@
const _Graph& graph;
Constraints() {}
- };
- };
-
- /// \brief Skeleton class for alterable undirected bipartite graphs.
- ///
- /// This class describes the interface of alterable undirected
- /// bipartite graphs. It extends \ref AlterableGraphComponent with
- /// the alteration notifier interface of bipartite graphs. It
- /// implements an observer-notifier pattern for the red and blue
- /// nodes. More obsevers can be registered into the notifier and
- /// whenever an alteration occured in the graph all the observers
- /// will be notified about it.
- template
- class AlterableBpGraphComponent : public AlterableGraphComponent {
- public:
-
- typedef BAS Base;
- typedef AlterableGraphComponent Parent;
- typedef typename Base::RedNode RedNode;
- typedef typename Base::BlueNode BlueNode;
-
-
- /// Red node alteration notifier class.
- typedef AlterationNotifier
- RedNodeNotifier;
-
- /// Blue node alteration notifier class.
- typedef AlterationNotifier
- BlueNodeNotifier;
-
- mutable RedNodeNotifier red_node_notifier;
- mutable BlueNodeNotifier blue_node_notifier;
-
- using Parent::notifier;
-
- /// \brief Return the red node alteration notifier.
- ///
- /// This function gives back the red node alteration notifier.
- RedNodeNotifier& notifier(RedNode) const {
- return red_node_notifier;
- }
-
- /// \brief Return the blue node alteration notifier.
- ///
- /// This function gives back the blue node alteration notifier.
- BlueNodeNotifier& notifier(BlueNode) const {
- return blue_node_notifier;
- }
-
- template
- struct Constraints {
- void constraints() {
- checkConcept, _BpGraph>();
- typename _BpGraph::RedNodeNotifier& rnn
- = bpgraph.notifier(typename _BpGraph::RedNode());
- typename _BpGraph::BlueNodeNotifier& bnn
- = bpgraph.notifier(typename _BpGraph::BlueNode());
- ignore_unused_variable_warning(rnn);
- ignore_unused_variable_warning(bnn);
- }
-
- const _BpGraph& bpgraph;
};
};
@@ -1699,148 +1308,4 @@
};
- /// \brief Skeleton class for mappable undirected bipartite graphs.
- ///
- /// This class describes the interface of mappable undirected
- /// bipartite graphs. It extends \ref MappableGraphComponent with
- /// the standard graph map class for red and blue nodes (\c
- /// RedNodeMap and BlueNodeMap). This concept is part of the
- /// BpGraph concept.
- template
- class MappableBpGraphComponent : public MappableGraphComponent {
- public:
-
- typedef BAS Base;
- typedef typename Base::Node Node;
-
- typedef MappableBpGraphComponent BpGraph;
-
- /// \brief Standard graph map for the red nodes.
- ///
- /// Standard graph map for the red nodes.
- /// It conforms to the ReferenceMap concept.
- template
- class RedNodeMap : public GraphMap {
- typedef GraphMap Parent;
-
- public:
- /// \brief Construct a new map.
- ///
- /// Construct a new map for the graph.
- explicit RedNodeMap(const MappableBpGraphComponent& graph)
- : Parent(graph) {}
-
- /// \brief Construct a new map with default value.
- ///
- /// Construct a new map for the graph and initalize the values.
- RedNodeMap(const MappableBpGraphComponent& graph, const V& value)
- : Parent(graph, value) {}
-
- private:
- /// \brief Copy constructor.
- ///
- /// Copy Constructor.
- RedNodeMap(const RedNodeMap& nm) : Parent(nm) {}
-
- /// \brief Assignment operator.
- ///
- /// Assignment operator.
- template
- RedNodeMap& operator=(const CMap&) {
- checkConcept, CMap>();
- return *this;
- }
-
- };
-
- /// \brief Standard graph map for the blue nodes.
- ///
- /// Standard graph map for the blue nodes.
- /// It conforms to the ReferenceMap concept.
- template
- class BlueNodeMap : public GraphMap {
- typedef GraphMap Parent;
-
- public:
- /// \brief Construct a new map.
- ///
- /// Construct a new map for the graph.
- explicit BlueNodeMap(const MappableBpGraphComponent& graph)
- : Parent(graph) {}
-
- /// \brief Construct a new map with default value.
- ///
- /// Construct a new map for the graph and initalize the values.
- BlueNodeMap(const MappableBpGraphComponent& graph, const V& value)
- : Parent(graph, value) {}
-
- private:
- /// \brief Copy constructor.
- ///
- /// Copy Constructor.
- BlueNodeMap(const BlueNodeMap& nm) : Parent(nm) {}
-
- /// \brief Assignment operator.
- ///
- /// Assignment operator.
- template
- BlueNodeMap& operator=(const CMap&) {
- checkConcept, CMap>();
- return *this;
- }
-
- };
-
-
- template
- struct Constraints {
-
- struct Dummy {
- int value;
- Dummy() : value(0) {}
- Dummy(int _v) : value(_v) {}
- };
-
- void constraints() {
- checkConcept, _BpGraph>();
-
- { // int map test
- typedef typename _BpGraph::template RedNodeMap
- IntRedNodeMap;
- checkConcept,
- IntRedNodeMap >();
- } { // bool map test
- typedef typename _BpGraph::template RedNodeMap
- BoolRedNodeMap;
- checkConcept,
- BoolRedNodeMap >();
- } { // Dummy map test
- typedef typename _BpGraph::template RedNodeMap
- DummyRedNodeMap;
- checkConcept,
- DummyRedNodeMap >();
- }
-
- { // int map test
- typedef typename _BpGraph::template BlueNodeMap
- IntBlueNodeMap;
- checkConcept,
- IntBlueNodeMap >();
- } { // bool map test
- typedef typename _BpGraph::template BlueNodeMap
- BoolBlueNodeMap;
- checkConcept,
- BoolBlueNodeMap >();
- } { // Dummy map test
- typedef typename _BpGraph::template BlueNodeMap
- DummyBlueNodeMap;
- checkConcept,
- DummyBlueNodeMap >();
- }
- }
-
- const _BpGraph& bpgraph;
- };
- };
-
/// \brief Skeleton class for extendable directed graphs.
///
@@ -1933,63 +1398,4 @@
};
- /// \brief Skeleton class for extendable undirected bipartite graphs.
- ///
- /// This class describes the interface of extendable undirected
- /// bipartite graphs. It extends \ref BaseGraphComponent with
- /// functions for adding nodes and edges to the graph. This
- /// concept requires \ref AlterableBpGraphComponent.
- template
- class ExtendableBpGraphComponent : public BAS {
- public:
-
- typedef BAS Base;
- typedef typename Base::Node Node;
- typedef typename Base::RedNode RedNode;
- typedef typename Base::BlueNode BlueNode;
- typedef typename Base::Edge Edge;
-
- /// \brief Add a new red node to the digraph.
- ///
- /// This function adds a red new node to the digraph.
- RedNode addRedNode() {
- return INVALID;
- }
-
- /// \brief Add a new blue node to the digraph.
- ///
- /// This function adds a blue new node to the digraph.
- BlueNode addBlueNode() {
- return INVALID;
- }
-
- /// \brief Add a new edge connecting the given two nodes.
- ///
- /// This function adds a new edge connecting the given two nodes
- /// of the graph. The first node has to be a red node, and the
- /// second one a blue node.
- Edge addEdge(const RedNode&, const BlueNode&) {
- return INVALID;
- }
- Edge addEdge(const BlueNode&, const RedNode&) {
- return INVALID;
- }
-
- template
- struct Constraints {
- void constraints() {
- checkConcept();
- typename _BpGraph::RedNode red_node;
- typename _BpGraph::BlueNode blue_node;
- red_node = bpgraph.addRedNode();
- blue_node = bpgraph.addBlueNode();
- typename _BpGraph::Edge edge;
- edge = bpgraph.addEdge(red_node, blue_node);
- edge = bpgraph.addEdge(blue_node, red_node);
- }
-
- _BpGraph& bpgraph;
- };
- };
-
/// \brief Skeleton class for erasable directed graphs.
///
@@ -2072,13 +1478,4 @@
};
- /// \brief Skeleton class for erasable undirected graphs.
- ///
- /// This class describes the interface of erasable undirected
- /// bipartite graphs. It extends \ref BaseBpGraphComponent with
- /// functions for removing nodes and edges from the graph. This
- /// concept requires \ref AlterableBpGraphComponent.
- template
- class ErasableBpGraphComponent : public ErasableGraphComponent {};
-
/// \brief Skeleton class for clearable directed graphs.
///
@@ -2117,14 +1514,25 @@
/// This concept requires \ref AlterableGraphComponent.
template
- class ClearableGraphComponent : public ClearableDigraphComponent {};
-
- /// \brief Skeleton class for clearable undirected biparite graphs.
- ///
- /// This class describes the interface of clearable undirected
- /// bipartite graphs. It extends \ref BaseBpGraphComponent with a
- /// function for clearing the graph. This concept requires \ref
- /// AlterableBpGraphComponent.
- template
- class ClearableBpGraphComponent : public ClearableGraphComponent {};
+ class ClearableGraphComponent : public ClearableDigraphComponent {
+ public:
+
+ typedef BAS Base;
+
+ /// \brief Erase all nodes and edges from the graph.
+ ///
+ /// This function erases all nodes and edges from the graph.
+ void clear() {}
+
+ template
+ struct Constraints {
+ void constraints() {
+ checkConcept();
+ graph.clear();
+ }
+
+ _Graph& graph;
+ Constraints() {}
+ };
+ };
}
Index: lemon/core.h
===================================================================
--- lemon/core.h (revision 1195)
+++ lemon/core.h (revision 1162)
@@ -149,47 +149,4 @@
typedef typename Graph::template EdgeMap DoubleEdgeMap
- ///Create convenience typedefs for the bipartite graph types and iterators
-
- ///This \c \#define creates the same convenient type definitions as
- ///defined by \ref GRAPH_TYPEDEFS(BpGraph) and ten more, namely it
- ///creates \c RedNode, \c RedNodeIt, \c BoolRedNodeMap,
- ///\c IntRedNodeMap, \c DoubleRedNodeMap, \c BlueNode, \c BlueNodeIt,
- ///\c BoolBlueNodeMap, \c IntBlueNodeMap, \c DoubleBlueNodeMap.
- ///
- ///\note If the graph type is a dependent type, ie. the graph type depend
- ///on a template parameter, then use \c TEMPLATE_BPGRAPH_TYPEDEFS()
- ///macro.
-#define BPGRAPH_TYPEDEFS(BpGraph) \
- GRAPH_TYPEDEFS(BpGraph); \
- typedef BpGraph::RedNode RedNode; \
- typedef BpGraph::RedNodeIt RedNodeIt; \
- typedef BpGraph::RedNodeMap BoolRedNodeMap; \
- typedef BpGraph::RedNodeMap IntRedNodeMap; \
- typedef BpGraph::RedNodeMap DoubleRedNodeMap; \
- typedef BpGraph::BlueNode BlueNode; \
- typedef BpGraph::BlueNodeIt BlueNodeIt; \
- typedef BpGraph::BlueNodeMap BoolBlueNodeMap; \
- typedef BpGraph::BlueNodeMap IntBlueNodeMap; \
- typedef BpGraph::BlueNodeMap DoubleBlueNodeMap
-
- ///Create convenience typedefs for the bipartite graph types and iterators
-
- ///\see BPGRAPH_TYPEDEFS
- ///
- ///\note Use this macro, if the graph type is a dependent type,
- ///ie. the graph type depend on a template parameter.
-#define TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph) \
- TEMPLATE_GRAPH_TYPEDEFS(BpGraph); \
- typedef typename BpGraph::RedNode RedNode; \
- typedef typename BpGraph::RedNodeIt RedNodeIt; \
- typedef typename BpGraph::template RedNodeMap BoolRedNodeMap; \
- typedef typename BpGraph::template RedNodeMap IntRedNodeMap; \
- typedef typename BpGraph::template RedNodeMap DoubleRedNodeMap; \
- typedef typename BpGraph::BlueNode BlueNode; \
- typedef typename BpGraph::BlueNodeIt BlueNodeIt; \
- typedef typename BpGraph::template BlueNodeMap BoolBlueNodeMap; \
- typedef typename BpGraph::template BlueNodeMap IntBlueNodeMap; \
- typedef typename BpGraph::template BlueNodeMap DoubleBlueNodeMap
-
/// \brief Function to count the items in a graph.
///
@@ -243,72 +200,4 @@
}
- namespace _graph_utils_bits {
-
- template
- struct CountRedNodesSelector {
- static int count(const Graph &g) {
- return countItems(g);
- }
- };
-
- template
- struct CountRedNodesSelector<
- Graph, typename
- enable_if::type>
- {
- static int count(const Graph &g) {
- return g.redNum();
- }
- };
- }
-
- /// \brief Function to count the red nodes in the graph.
- ///
- /// This function counts the red nodes in the graph.
- /// The complexity of the function is O(n) but for some
- /// graph structures it is specialized to run in O(1).
- ///
- /// If the graph contains a \e redNum() member function and a
- /// \e NodeNumTag tag then this function calls directly the member
- /// function to query the cardinality of the node set.
- template
- inline int countRedNodes(const Graph& g) {
- return _graph_utils_bits::CountRedNodesSelector::count(g);
- }
-
- namespace _graph_utils_bits {
-
- template
- struct CountBlueNodesSelector {
- static int count(const Graph &g) {
- return countItems(g);
- }
- };
-
- template
- struct CountBlueNodesSelector<
- Graph, typename
- enable_if::type>
- {
- static int count(const Graph &g) {
- return g.blueNum();
- }
- };
- }
-
- /// \brief Function to count the blue nodes in the graph.
- ///
- /// This function counts the blue nodes in the graph.
- /// The complexity of the function is O(n) but for some
- /// graph structures it is specialized to run in O(1).
- ///
- /// If the graph contains a \e blueNum() member function and a
- /// \e NodeNumTag tag then this function calls directly the member
- /// function to query the cardinality of the node set.
- template
- inline int countBlueNodes(const Graph& g) {
- return _graph_utils_bits::CountBlueNodesSelector::count(g);
- }
-
// Arc counting:
@@ -552,44 +441,6 @@
template
static void copy(const From& from, Graph &to,
- NodeRefMap& nodeRefMap,
- EdgeRefMap& edgeRefMap) {
+ NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
to.build(from, nodeRefMap, edgeRefMap);
- }
- };
-
- template
- struct BpGraphCopySelector {
- template
- static void copy(const From& from, BpGraph &to,
- RedNodeRefMap& redNodeRefMap,
- BlueNodeRefMap& blueNodeRefMap,
- EdgeRefMap& edgeRefMap) {
- to.clear();
- for (typename From::RedNodeIt it(from); it != INVALID; ++it) {
- redNodeRefMap[it] = to.addRedNode();
- }
- for (typename From::BlueNodeIt it(from); it != INVALID; ++it) {
- blueNodeRefMap[it] = to.addBlueNode();
- }
- for (typename From::EdgeIt it(from); it != INVALID; ++it) {
- edgeRefMap[it] = to.addEdge(redNodeRefMap[from.redNode(it)],
- blueNodeRefMap[from.blueNode(it)]);
- }
- }
- };
-
- template
- struct BpGraphCopySelector<
- BpGraph,
- typename enable_if::type>
- {
- template
- static void copy(const From& from, BpGraph &to,
- RedNodeRefMap& redNodeRefMap,
- BlueNodeRefMap& blueNodeRefMap,
- EdgeRefMap& edgeRefMap) {
- to.build(from, redNodeRefMap, blueNodeRefMap, edgeRefMap);
}
};
@@ -1139,452 +990,4 @@
graphCopy(const From& from, To& to) {
return GraphCopy(from, to);
- }
-
- /// \brief Class to copy a bipartite graph.
- ///
- /// Class to copy a bipartite graph to another graph (duplicate a
- /// graph). The simplest way of using it is through the
- /// \c bpGraphCopy() function.
- ///
- /// This class not only make a copy of a bipartite graph, but it can
- /// create references and cross references between the nodes, edges
- /// and arcs of the two graphs, and it can copy maps for using with
- /// the newly created graph.
- ///
- /// To make a copy from a graph, first an instance of BpGraphCopy
- /// should be created, then the data belongs to the graph should
- /// assigned to copy. In the end, the \c run() member should be
- /// called.
- ///
- /// The next code copies a graph with several data:
- ///\code
- /// BpGraphCopy cg(orig_graph, new_graph);
- /// // Create references for the nodes
- /// OrigBpGraph::NodeMap nr(orig_graph);
- /// cg.nodeRef(nr);
- /// // Create cross references (inverse) for the edges
- /// NewBpGraph::EdgeMap ecr(new_graph);
- /// cg.edgeCrossRef(ecr);
- /// // Copy a red node map
- /// OrigBpGraph::RedNodeMap ormap(orig_graph);
- /// NewBpGraph::RedNodeMap nrmap(new_graph);
- /// cg.redNodeMap(ormap, nrmap);
- /// // Copy a node
- /// OrigBpGraph::Node on;
- /// NewBpGraph::Node nn;
- /// cg.node(on, nn);
- /// // Execute copying
- /// cg.run();
- ///\endcode
- template
- class BpGraphCopy {
- private:
-
- typedef typename From::Node Node;
- typedef typename From::RedNode RedNode;
- typedef typename From::BlueNode BlueNode;
- typedef typename From::NodeIt NodeIt;
- typedef typename From::Arc Arc;
- typedef typename From::ArcIt ArcIt;
- typedef typename From::Edge Edge;
- typedef typename From::EdgeIt EdgeIt;
-
- typedef typename To::Node TNode;
- typedef typename To::RedNode TRedNode;
- typedef typename To::BlueNode TBlueNode;
- typedef typename To::Arc TArc;
- typedef typename To::Edge TEdge;
-
- typedef typename From::template RedNodeMap RedNodeRefMap;
- typedef typename From::template BlueNodeMap BlueNodeRefMap;
- typedef typename From::template EdgeMap EdgeRefMap;
-
- struct NodeRefMap {
- NodeRefMap(const From& from, const RedNodeRefMap& red_node_ref,
- const BlueNodeRefMap& blue_node_ref)
- : _from(from), _red_node_ref(red_node_ref),
- _blue_node_ref(blue_node_ref) {}
-
- typedef typename From::Node Key;
- typedef typename To::Node Value;
-
- Value operator[](const Key& key) const {
- if (_from.red(key)) {
- return _red_node_ref[_from.asRedNodeUnsafe(key)];
- } else {
- return _blue_node_ref[_from.asBlueNodeUnsafe(key)];
- }
- }
-
- const From& _from;
- const RedNodeRefMap& _red_node_ref;
- const BlueNodeRefMap& _blue_node_ref;
- };
-
- struct ArcRefMap {
- ArcRefMap(const From& from, const To& to, const EdgeRefMap& edge_ref)
- : _from(from), _to(to), _edge_ref(edge_ref) {}
-
- typedef typename From::Arc Key;
- typedef typename To::Arc Value;
-
- Value operator[](const Key& key) const {
- return _to.direct(_edge_ref[key], _from.direction(key));
- }
-
- const From& _from;
- const To& _to;
- const EdgeRefMap& _edge_ref;
- };
-
- public:
-
- /// \brief Constructor of BpGraphCopy.
- ///
- /// Constructor of BpGraphCopy for copying the content of the
- /// \c from graph into the \c to graph.
- BpGraphCopy(const From& from, To& to)
- : _from(from), _to(to) {}
-
- /// \brief Destructor of BpGraphCopy
- ///
- /// Destructor of BpGraphCopy.
- ~BpGraphCopy() {
- for (int i = 0; i < int(_node_maps.size()); ++i) {
- delete _node_maps[i];
- }
- for (int i = 0; i < int(_red_maps.size()); ++i) {
- delete _red_maps[i];
- }
- for (int i = 0; i < int(_blue_maps.size()); ++i) {
- delete _blue_maps[i];
- }
- for (int i = 0; i < int(_arc_maps.size()); ++i) {
- delete _arc_maps[i];
- }
- for (int i = 0; i < int(_edge_maps.size()); ++i) {
- delete _edge_maps[i];
- }
- }
-
- /// \brief Copy the node references into the given map.
- ///
- /// This function copies the node references into the given map.
- /// The parameter should be a map, whose key type is the Node type of
- /// the source graph, while the value type is the Node type of the
- /// destination graph.
- template
- BpGraphCopy& nodeRef(NodeRef& map) {
- _node_maps.push_back(new _core_bits::RefCopy(map));
- return *this;
- }
-
- /// \brief Copy the node cross references into the given map.
- ///
- /// This function copies the node cross references (reverse references)
- /// into the given map. The parameter should be a map, whose key type
- /// is the Node type of the destination graph, while the value type is
- /// the Node type of the source graph.
- template
- BpGraphCopy& nodeCrossRef(NodeCrossRef& map) {
- _node_maps.push_back(new _core_bits::CrossRefCopy(map));
- return *this;
- }
-
- /// \brief Make a copy of the given node map.
- ///
- /// This function makes a copy of the given node map for the newly
- /// created graph.
- /// The key type of the new map \c tmap should be the Node type of the
- /// destination graph, and the key type of the original map \c map
- /// should be the Node type of the source graph.
- template
- BpGraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
- _node_maps.push_back(new _core_bits::MapCopy(map, tmap));
- return *this;
- }
-
- /// \brief Make a copy of the given node.
- ///
- /// This function makes a copy of the given node.
- BpGraphCopy& node(const Node& node, TNode& tnode) {
- _node_maps.push_back(new _core_bits::ItemCopy(node, tnode));
- return *this;
- }
-
- /// \brief Copy the red node references into the given map.
- ///
- /// This function copies the red node references into the given
- /// map. The parameter should be a map, whose key type is the
- /// Node type of the source graph with the red item set, while the
- /// value type is the Node type of the destination graph.
- template
- BpGraphCopy& redRef(RedRef& map) {
- _red_maps.push_back(new _core_bits::RefCopy(map));
- return *this;
- }
-
- /// \brief Copy the red node cross references into the given map.
- ///
- /// This function copies the red node cross references (reverse
- /// references) into the given map. The parameter should be a map,
- /// whose key type is the Node type of the destination graph with
- /// the red item set, while the value type is the Node type of the
- /// source graph.
- template
- BpGraphCopy& redCrossRef(RedCrossRef& map) {
- _red_maps.push_back(new _core_bits::CrossRefCopy(map));
- return *this;
- }
-
- /// \brief Make a copy of the given red node map.
- ///
- /// This function makes a copy of the given red node map for the newly
- /// created graph.
- /// The key type of the new map \c tmap should be the Node type of
- /// the destination graph with the red items, and the key type of
- /// the original map \c map should be the Node type of the source
- /// graph.
- template
- BpGraphCopy& redNodeMap(const FromMap& map, ToMap& tmap) {
- _red_maps.push_back(new _core_bits::MapCopy(map, tmap));
- return *this;
- }
-
- /// \brief Make a copy of the given red node.
- ///
- /// This function makes a copy of the given red node.
- BpGraphCopy& redNode(const RedNode& node, TRedNode& tnode) {
- _red_maps.push_back(new _core_bits::ItemCopy(node, tnode));
- return *this;
- }
-
- /// \brief Copy the blue node references into the given map.
- ///
- /// This function copies the blue node references into the given
- /// map. The parameter should be a map, whose key type is the
- /// Node type of the source graph with the blue item set, while the
- /// value type is the Node type of the destination graph.
- template
- BpGraphCopy& blueRef(BlueRef& map) {
- _blue_maps.push_back(new _core_bits::RefCopy(map));
- return *this;
- }
-
- /// \brief Copy the blue node cross references into the given map.
- ///
- /// This function copies the blue node cross references (reverse
- /// references) into the given map. The parameter should be a map,
- /// whose key type is the Node type of the destination graph with
- /// the blue item set, while the value type is the Node type of the
- /// source graph.
- template
- BpGraphCopy& blueCrossRef(BlueCrossRef& map) {
- _blue_maps.push_back(new _core_bits::CrossRefCopy(map));
- return *this;
- }
-
- /// \brief Make a copy of the given blue node map.
- ///
- /// This function makes a copy of the given blue node map for the newly
- /// created graph.
- /// The key type of the new map \c tmap should be the Node type of
- /// the destination graph with the blue items, and the key type of
- /// the original map \c map should be the Node type of the source
- /// graph.
- template
- BpGraphCopy& blueNodeMap(const FromMap& map, ToMap& tmap) {
- _blue_maps.push_back(new _core_bits::MapCopy(map, tmap));
- return *this;
- }
-
- /// \brief Make a copy of the given blue node.
- ///
- /// This function makes a copy of the given blue node.
- BpGraphCopy& blueNode(const BlueNode& node, TBlueNode& tnode) {
- _blue_maps.push_back(new _core_bits::ItemCopy(node, tnode));
- return *this;
- }
-
- /// \brief Copy the arc references into the given map.
- ///
- /// This function copies the arc references into the given map.
- /// The parameter should be a map, whose key type is the Arc type of
- /// the source graph, while the value type is the Arc type of the
- /// destination graph.
- template
- BpGraphCopy& arcRef(ArcRef& map) {
- _arc_maps.push_back(new _core_bits::RefCopy(map));
- return *this;
- }
-
- /// \brief Copy the arc cross references into the given map.
- ///
- /// This function copies the arc cross references (reverse references)
- /// into the given map. The parameter should be a map, whose key type
- /// is the Arc type of the destination graph, while the value type is
- /// the Arc type of the source graph.
- template
- BpGraphCopy& arcCrossRef(ArcCrossRef& map) {
- _arc_maps.push_back(new _core_bits::CrossRefCopy(map));
- return *this;
- }
-
- /// \brief Make a copy of the given arc map.
- ///
- /// This function makes a copy of the given arc map for the newly
- /// created graph.
- /// The key type of the new map \c tmap should be the Arc type of the
- /// destination graph, and the key type of the original map \c map
- /// should be the Arc type of the source graph.
- template
- BpGraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
- _arc_maps.push_back(new _core_bits::MapCopy(map, tmap));
- return *this;
- }
-
- /// \brief Make a copy of the given arc.
- ///
- /// This function makes a copy of the given arc.
- BpGraphCopy& arc(const Arc& arc, TArc& tarc) {
- _arc_maps.push_back(new _core_bits::ItemCopy(arc, tarc));
- return *this;
- }
-
- /// \brief Copy the edge references into the given map.
- ///
- /// This function copies the edge references into the given map.
- /// The parameter should be a map, whose key type is the Edge type of
- /// the source graph, while the value type is the Edge type of the
- /// destination graph.
- template
- BpGraphCopy& edgeRef(EdgeRef& map) {
- _edge_maps.push_back(new _core_bits::RefCopy(map));
- return *this;
- }
-
- /// \brief Copy the edge cross references into the given map.
- ///
- /// This function copies the edge cross references (reverse references)
- /// into the given map. The parameter should be a map, whose key type
- /// is the Edge type of the destination graph, while the value type is
- /// the Edge type of the source graph.
- template