diff options
Diffstat (limited to 'lemon/doc')
30 files changed, 4858 insertions, 0 deletions
diff --git a/lemon/doc/CMakeLists.txt b/lemon/doc/CMakeLists.txt new file mode 100644 index 0000000..68a690e --- /dev/null +++ b/lemon/doc/CMakeLists.txt @@ -0,0 +1,74 @@ +SET(PACKAGE_NAME ${PROJECT_NAME}) +SET(PACKAGE_VERSION ${PROJECT_VERSION}) +SET(abs_top_srcdir ${PROJECT_SOURCE_DIR}) +SET(abs_top_builddir ${PROJECT_BINARY_DIR}) + +SET(LEMON_DOC_SOURCE_BROWSER "NO" CACHE STRING "Include source into the doc (YES/NO).") + +CONFIGURE_FILE( + ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in + ${PROJECT_BINARY_DIR}/doc/Doxyfile + @ONLY +) + +CONFIGURE_FILE( + ${PROJECT_SOURCE_DIR}/doc/mainpage.dox.in + ${PROJECT_BINARY_DIR}/doc/mainpage.dox + @ONLY +) + +IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE) + FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/) + SET(GHOSTSCRIPT_OPTIONS -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha) + ADD_CUSTOM_TARGET(html + COMMAND ${CMAKE_COMMAND} -E remove_directory gen-images + COMMAND ${CMAKE_COMMAND} -E make_directory gen-images + COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps + COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps + COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps + COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps + COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps + COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/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} + ) + + SET_TARGET_PROPERTIES(html PROPERTIES PROJECT_LABEL BUILD_DOC) + + IF(UNIX) + INSTALL( + DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/ + DESTINATION share/doc/lemon/html + COMPONENT html_documentation + ) + ELSEIF(WIN32) + INSTALL( + DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/ + DESTINATION doc + COMPONENT html_documentation + ) + ENDIF() + +ENDIF() + +IF(WGET_FOUND) +ADD_CUSTOM_TARGET(update-external-tags + 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} + ) +ENDIF() diff --git a/lemon/doc/Doxyfile b/lemon/doc/Doxyfile new file mode 100644 index 0000000..a53c7a4 --- /dev/null +++ b/lemon/doc/Doxyfile @@ -0,0 +1,291 @@ +# Doxyfile 1.7.3 + +#--------------------------------------------------------------------------- +# Project related configuration options +#--------------------------------------------------------------------------- +DOXYFILE_ENCODING = UTF-8 +PROJECT_NAME = +PROJECT_NUMBER = +PROJECT_BRIEF = +PROJECT_LOGO = +OUTPUT_DIRECTORY = +CREATE_SUBDIRS = NO +OUTPUT_LANGUAGE = English +BRIEF_MEMBER_DESC = YES +REPEAT_BRIEF = NO +ABBREVIATE_BRIEF = +ALWAYS_DETAILED_SEC = NO +INLINE_INHERITED_MEMB = NO +FULL_PATH_NAMES = YES +STRIP_FROM_PATH = "/home/carlo/honours/lemon" +STRIP_FROM_INC_PATH = "/home/carlo/honours/lemon" +SHORT_NAMES = YES +JAVADOC_AUTOBRIEF = NO +QT_AUTOBRIEF = NO +MULTILINE_CPP_IS_BRIEF = NO +INHERIT_DOCS = NO +SEPARATE_MEMBER_PAGES = NO +TAB_SIZE = 8 +ALIASES = +OPTIMIZE_OUTPUT_FOR_C = NO +OPTIMIZE_OUTPUT_JAVA = NO +OPTIMIZE_FOR_FORTRAN = NO +OPTIMIZE_OUTPUT_VHDL = NO +EXTENSION_MAPPING = +BUILTIN_STL_SUPPORT = YES +CPP_CLI_SUPPORT = NO +SIP_SUPPORT = NO +IDL_PROPERTY_SUPPORT = YES +DISTRIBUTE_GROUP_DOC = NO +SUBGROUPING = YES +TYPEDEF_HIDES_STRUCT = NO +SYMBOL_CACHE_SIZE = 0 +#--------------------------------------------------------------------------- +# Build related configuration options +#--------------------------------------------------------------------------- +EXTRACT_ALL = NO +EXTRACT_PRIVATE = YES +EXTRACT_STATIC = YES +EXTRACT_LOCAL_CLASSES = NO +EXTRACT_LOCAL_METHODS = NO +EXTRACT_ANON_NSPACES = NO +HIDE_UNDOC_MEMBERS = YES +HIDE_UNDOC_CLASSES = YES +HIDE_FRIEND_COMPOUNDS = NO +HIDE_IN_BODY_DOCS = NO +INTERNAL_DOCS = NO +CASE_SENSE_NAMES = YES +HIDE_SCOPE_NAMES = YES +SHOW_INCLUDE_FILES = YES +FORCE_LOCAL_INCLUDES = NO +INLINE_INFO = YES +SORT_MEMBER_DOCS = NO +SORT_BRIEF_DOCS = NO +SORT_MEMBERS_CTORS_1ST = NO +SORT_GROUP_NAMES = NO +SORT_BY_SCOPE_NAME = NO +STRICT_PROTO_MATCHING = NO +GENERATE_TODOLIST = YES +GENERATE_TESTLIST = YES +GENERATE_BUGLIST = YES +GENERATE_DEPRECATEDLIST= YES +ENABLED_SECTIONS = +MAX_INITIALIZER_LINES = 5 +SHOW_USED_FILES = NO +SHOW_DIRECTORIES = YES +SHOW_FILES = YES +SHOW_NAMESPACES = YES +FILE_VERSION_FILTER = +LAYOUT_FILE = "/home/carlo/honours/lemon/doc/DoxygenLayout.xml" +#--------------------------------------------------------------------------- +# configuration options related to warning and progress messages +#--------------------------------------------------------------------------- +QUIET = NO +WARNINGS = YES +WARN_IF_UNDOCUMENTED = YES +WARN_IF_DOC_ERROR = YES +WARN_NO_PARAMDOC = NO +WARN_FORMAT = "$file:$line: $text" +WARN_LOGFILE = doxygen.log +#--------------------------------------------------------------------------- +# configuration options related to the input files +#--------------------------------------------------------------------------- +INPUT = "/home/carlo/honours/lemon/doc" \ + "/home/carlo/honours/lemon/lemon" \ + "/home/carlo/honours/lemon/lemon/bits" \ + "/home/carlo/honours/lemon/lemon/concepts" \ + "/home/carlo/honours/lemon/demo" \ + "/home/carlo/honours/lemon/tools" \ + "/home/carlo/honours/lemon/test/test_tools.h" \ + "/home/carlo/honours/lemon/doc/mainpage.dox" \ + "/home/carlo/honours/lemon/doc/references.dox" +INPUT_ENCODING = UTF-8 +FILE_PATTERNS = *.h \ + *.cc \ + *.dox +RECURSIVE = NO +EXCLUDE = +EXCLUDE_SYMLINKS = NO +EXCLUDE_PATTERNS = +EXCLUDE_SYMBOLS = +EXAMPLE_PATH = "/home/carlo/honours/lemon/demo" \ + "/home/carlo/honours/lemon/LICENSE" \ + "/home/carlo/honours/lemon/doc" +EXAMPLE_PATTERNS = +EXAMPLE_RECURSIVE = NO +IMAGE_PATH = "/home/carlo/honours/lemon/doc/images" \ + "/home/carlo/honours/lemon/doc/gen-images" +INPUT_FILTER = +FILTER_PATTERNS = +FILTER_SOURCE_FILES = NO +FILTER_SOURCE_PATTERNS = +#--------------------------------------------------------------------------- +# configuration options related to source browsing +#--------------------------------------------------------------------------- +SOURCE_BROWSER = @LEMON_DOC_SOURCE_BROWSER@ +INLINE_SOURCES = NO +STRIP_CODE_COMMENTS = YES +REFERENCED_BY_RELATION = NO +REFERENCES_RELATION = NO +REFERENCES_LINK_SOURCE = YES +USE_HTAGS = NO +VERBATIM_HEADERS = NO +#--------------------------------------------------------------------------- +# configuration options related to the alphabetical class index +#--------------------------------------------------------------------------- +ALPHABETICAL_INDEX = YES +COLS_IN_ALPHA_INDEX = 2 +IGNORE_PREFIX = +#--------------------------------------------------------------------------- +# configuration options related to the HTML output +#--------------------------------------------------------------------------- +GENERATE_HTML = YES +HTML_OUTPUT = html +HTML_FILE_EXTENSION = .html +HTML_HEADER = +HTML_FOOTER = +HTML_STYLESHEET = +HTML_COLORSTYLE_HUE = 220 +HTML_COLORSTYLE_SAT = 100 +HTML_COLORSTYLE_GAMMA = 80 +HTML_TIMESTAMP = YES +HTML_ALIGN_MEMBERS = YES +HTML_DYNAMIC_SECTIONS = YES +GENERATE_DOCSET = NO +DOCSET_FEEDNAME = "Doxygen generated docs" +DOCSET_BUNDLE_ID = org.doxygen.Project +DOCSET_PUBLISHER_ID = org.doxygen.Publisher +DOCSET_PUBLISHER_NAME = Publisher +GENERATE_HTMLHELP = NO +CHM_FILE = +HHC_LOCATION = +GENERATE_CHI = NO +CHM_INDEX_ENCODING = +BINARY_TOC = NO +TOC_EXPAND = NO +GENERATE_QHP = NO +QCH_FILE = +QHP_NAMESPACE = org.doxygen.Project +QHP_VIRTUAL_FOLDER = doc +QHP_CUST_FILTER_NAME = +QHP_CUST_FILTER_ATTRS = +QHP_SECT_FILTER_ATTRS = +QHG_LOCATION = +GENERATE_ECLIPSEHELP = NO +ECLIPSE_DOC_ID = org.doxygen.Project +DISABLE_INDEX = NO +ENUM_VALUES_PER_LINE = 4 +GENERATE_TREEVIEW = NO +USE_INLINE_TREES = NO +TREEVIEW_WIDTH = 250 +EXT_LINKS_IN_WINDOW = NO +FORMULA_FONTSIZE = 10 +FORMULA_TRANSPARENT = YES +USE_MATHJAX = NO +MATHJAX_RELPATH = http://www.mathjax.org/mathjax +SEARCHENGINE = YES +SERVER_BASED_SEARCH = NO +#--------------------------------------------------------------------------- +# configuration options related to the LaTeX output +#--------------------------------------------------------------------------- +GENERATE_LATEX = NO +LATEX_OUTPUT = latex +LATEX_CMD_NAME = latex +MAKEINDEX_CMD_NAME = makeindex +COMPACT_LATEX = YES +PAPER_TYPE = a4wide +EXTRA_PACKAGES = amsmath \ + amssymb +LATEX_HEADER = +PDF_HYPERLINKS = YES +USE_PDFLATEX = YES +LATEX_BATCHMODE = NO +LATEX_HIDE_INDICES = NO +LATEX_SOURCE_CODE = NO +#--------------------------------------------------------------------------- +# configuration options related to the RTF output +#--------------------------------------------------------------------------- +GENERATE_RTF = NO +RTF_OUTPUT = rtf +COMPACT_RTF = NO +RTF_HYPERLINKS = NO +RTF_STYLESHEET_FILE = +RTF_EXTENSIONS_FILE = +#--------------------------------------------------------------------------- +# configuration options related to the man page output +#--------------------------------------------------------------------------- +GENERATE_MAN = NO +MAN_OUTPUT = man +MAN_EXTENSION = .3 +MAN_LINKS = NO +#--------------------------------------------------------------------------- +# configuration options related to the XML output +#--------------------------------------------------------------------------- +GENERATE_XML = NO +XML_OUTPUT = xml +XML_SCHEMA = +XML_DTD = +XML_PROGRAMLISTING = YES +#--------------------------------------------------------------------------- +# configuration options for the AutoGen Definitions output +#--------------------------------------------------------------------------- +GENERATE_AUTOGEN_DEF = NO +#--------------------------------------------------------------------------- +# configuration options related to the Perl module output +#--------------------------------------------------------------------------- +GENERATE_PERLMOD = NO +PERLMOD_LATEX = NO +PERLMOD_PRETTY = YES +PERLMOD_MAKEVAR_PREFIX = +#--------------------------------------------------------------------------- +# Configuration options related to the preprocessor +#--------------------------------------------------------------------------- +ENABLE_PREPROCESSING = YES +MACRO_EXPANSION = NO +EXPAND_ONLY_PREDEF = NO +SEARCH_INCLUDES = YES +INCLUDE_PATH = +INCLUDE_FILE_PATTERNS = +PREDEFINED = DOXYGEN +EXPAND_AS_DEFINED = +SKIP_FUNCTION_MACROS = YES +#--------------------------------------------------------------------------- +# Configuration::additions related to external references +#--------------------------------------------------------------------------- +TAGFILES = "/home/carlo/honours/lemon/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/ " +GENERATE_TAGFILE = html/lemon.tag +ALLEXTERNALS = NO +EXTERNAL_GROUPS = NO +PERL_PATH = /usr/bin/perl +#--------------------------------------------------------------------------- +# Configuration options related to the dot tool +#--------------------------------------------------------------------------- +CLASS_DIAGRAMS = YES +MSCGEN_PATH = +HIDE_UNDOC_RELATIONS = YES +HAVE_DOT = YES +DOT_NUM_THREADS = 0 +DOT_FONTNAME = FreeSans +DOT_FONTSIZE = 10 +DOT_FONTPATH = +CLASS_GRAPH = YES +COLLABORATION_GRAPH = NO +GROUP_GRAPHS = NO +UML_LOOK = NO +TEMPLATE_RELATIONS = NO +INCLUDE_GRAPH = NO +INCLUDED_BY_GRAPH = NO +CALL_GRAPH = NO +CALLER_GRAPH = NO +GRAPHICAL_HIERARCHY = NO +DIRECTORY_GRAPH = NO +DOT_IMAGE_FORMAT = png +DOT_PATH = +DOTFILE_DIRS = +MSCFILE_DIRS = +DOT_GRAPH_MAX_NODES = 50 +MAX_DOT_GRAPH_DEPTH = 0 +DOT_TRANSPARENT = NO +DOT_MULTI_TARGETS = NO +GENERATE_LEGEND = YES +DOT_CLEANUP = YES diff --git a/lemon/doc/Doxyfile.in b/lemon/doc/Doxyfile.in new file mode 100644 index 0000000..e4dcaf8 --- /dev/null +++ b/lemon/doc/Doxyfile.in @@ -0,0 +1,291 @@ +# Doxyfile 1.7.3 + +#--------------------------------------------------------------------------- +# Project related configuration options +#--------------------------------------------------------------------------- +DOXYFILE_ENCODING = UTF-8 +PROJECT_NAME = +PROJECT_NUMBER = +PROJECT_BRIEF = +PROJECT_LOGO = +OUTPUT_DIRECTORY = +CREATE_SUBDIRS = NO +OUTPUT_LANGUAGE = English +BRIEF_MEMBER_DESC = YES +REPEAT_BRIEF = NO +ABBREVIATE_BRIEF = +ALWAYS_DETAILED_SEC = NO +INLINE_INHERITED_MEMB = NO +FULL_PATH_NAMES = YES +STRIP_FROM_PATH = "@abs_top_srcdir@" +STRIP_FROM_INC_PATH = "@abs_top_srcdir@" +SHORT_NAMES = YES +JAVADOC_AUTOBRIEF = NO +QT_AUTOBRIEF = NO +MULTILINE_CPP_IS_BRIEF = NO +INHERIT_DOCS = NO +SEPARATE_MEMBER_PAGES = NO +TAB_SIZE = 8 +ALIASES = +OPTIMIZE_OUTPUT_FOR_C = NO +OPTIMIZE_OUTPUT_JAVA = NO +OPTIMIZE_FOR_FORTRAN = NO +OPTIMIZE_OUTPUT_VHDL = NO +EXTENSION_MAPPING = +BUILTIN_STL_SUPPORT = YES +CPP_CLI_SUPPORT = NO +SIP_SUPPORT = NO +IDL_PROPERTY_SUPPORT = YES +DISTRIBUTE_GROUP_DOC = NO +SUBGROUPING = YES +TYPEDEF_HIDES_STRUCT = NO +SYMBOL_CACHE_SIZE = 0 +#--------------------------------------------------------------------------- +# Build related configuration options +#--------------------------------------------------------------------------- +EXTRACT_ALL = NO +EXTRACT_PRIVATE = YES +EXTRACT_STATIC = YES +EXTRACT_LOCAL_CLASSES = NO +EXTRACT_LOCAL_METHODS = NO +EXTRACT_ANON_NSPACES = NO +HIDE_UNDOC_MEMBERS = YES +HIDE_UNDOC_CLASSES = YES +HIDE_FRIEND_COMPOUNDS = NO +HIDE_IN_BODY_DOCS = NO +INTERNAL_DOCS = NO +CASE_SENSE_NAMES = YES +HIDE_SCOPE_NAMES = YES +SHOW_INCLUDE_FILES = YES +FORCE_LOCAL_INCLUDES = NO +INLINE_INFO = YES +SORT_MEMBER_DOCS = NO +SORT_BRIEF_DOCS = NO +SORT_MEMBERS_CTORS_1ST = NO +SORT_GROUP_NAMES = NO +SORT_BY_SCOPE_NAME = NO +STRICT_PROTO_MATCHING = NO +GENERATE_TODOLIST = YES +GENERATE_TESTLIST = YES +GENERATE_BUGLIST = YES +GENERATE_DEPRECATEDLIST= YES +ENABLED_SECTIONS = +MAX_INITIALIZER_LINES = 5 +SHOW_USED_FILES = NO +SHOW_DIRECTORIES = YES +SHOW_FILES = YES +SHOW_NAMESPACES = YES +FILE_VERSION_FILTER = +LAYOUT_FILE = "@abs_top_srcdir@/doc/DoxygenLayout.xml" +#--------------------------------------------------------------------------- +# configuration options related to warning and progress messages +#--------------------------------------------------------------------------- +QUIET = NO +WARNINGS = YES +WARN_IF_UNDOCUMENTED = YES +WARN_IF_DOC_ERROR = YES +WARN_NO_PARAMDOC = NO +WARN_FORMAT = "$file:$line: $text" +WARN_LOGFILE = doxygen.log +#--------------------------------------------------------------------------- +# configuration options related to the input files +#--------------------------------------------------------------------------- +INPUT = "@abs_top_srcdir@/doc" \ + "@abs_top_srcdir@/lemon" \ + "@abs_top_srcdir@/lemon/bits" \ + "@abs_top_srcdir@/lemon/concepts" \ + "@abs_top_srcdir@/demo" \ + "@abs_top_srcdir@/tools" \ + "@abs_top_srcdir@/test/test_tools.h" \ + "@abs_top_builddir@/doc/mainpage.dox" \ + "@abs_top_builddir@/doc/references.dox" +INPUT_ENCODING = UTF-8 +FILE_PATTERNS = *.h \ + *.cc \ + *.dox +RECURSIVE = NO +EXCLUDE = +EXCLUDE_SYMLINKS = NO +EXCLUDE_PATTERNS = +EXCLUDE_SYMBOLS = +EXAMPLE_PATH = "@abs_top_srcdir@/demo" \ + "@abs_top_srcdir@/LICENSE" \ + "@abs_top_srcdir@/doc" +EXAMPLE_PATTERNS = +EXAMPLE_RECURSIVE = NO +IMAGE_PATH = "@abs_top_srcdir@/doc/images" \ + "@abs_top_builddir@/doc/gen-images" +INPUT_FILTER = +FILTER_PATTERNS = +FILTER_SOURCE_FILES = NO +FILTER_SOURCE_PATTERNS = +#--------------------------------------------------------------------------- +# configuration options related to source browsing +#--------------------------------------------------------------------------- +SOURCE_BROWSER = @LEMON_DOC_SOURCE_BROWSER@ +INLINE_SOURCES = NO +STRIP_CODE_COMMENTS = YES +REFERENCED_BY_RELATION = NO +REFERENCES_RELATION = NO +REFERENCES_LINK_SOURCE = YES +USE_HTAGS = NO +VERBATIM_HEADERS = NO +#--------------------------------------------------------------------------- +# configuration options related to the alphabetical class index +#--------------------------------------------------------------------------- +ALPHABETICAL_INDEX = YES +COLS_IN_ALPHA_INDEX = 2 +IGNORE_PREFIX = +#--------------------------------------------------------------------------- +# configuration options related to the HTML output +#--------------------------------------------------------------------------- +GENERATE_HTML = YES +HTML_OUTPUT = html +HTML_FILE_EXTENSION = .html +HTML_HEADER = +HTML_FOOTER = +HTML_STYLESHEET = +HTML_COLORSTYLE_HUE = 220 +HTML_COLORSTYLE_SAT = 100 +HTML_COLORSTYLE_GAMMA = 80 +HTML_TIMESTAMP = YES +HTML_ALIGN_MEMBERS = YES +HTML_DYNAMIC_SECTIONS = YES +GENERATE_DOCSET = NO +DOCSET_FEEDNAME = "Doxygen generated docs" +DOCSET_BUNDLE_ID = org.doxygen.Project +DOCSET_PUBLISHER_ID = org.doxygen.Publisher +DOCSET_PUBLISHER_NAME = Publisher +GENERATE_HTMLHELP = NO +CHM_FILE = +HHC_LOCATION = +GENERATE_CHI = NO +CHM_INDEX_ENCODING = +BINARY_TOC = NO +TOC_EXPAND = NO +GENERATE_QHP = NO +QCH_FILE = +QHP_NAMESPACE = org.doxygen.Project +QHP_VIRTUAL_FOLDER = doc +QHP_CUST_FILTER_NAME = +QHP_CUST_FILTER_ATTRS = +QHP_SECT_FILTER_ATTRS = +QHG_LOCATION = +GENERATE_ECLIPSEHELP = NO +ECLIPSE_DOC_ID = org.doxygen.Project +DISABLE_INDEX = NO +ENUM_VALUES_PER_LINE = 4 +GENERATE_TREEVIEW = NO +USE_INLINE_TREES = NO +TREEVIEW_WIDTH = 250 +EXT_LINKS_IN_WINDOW = NO +FORMULA_FONTSIZE = 10 +FORMULA_TRANSPARENT = YES +USE_MATHJAX = NO +MATHJAX_RELPATH = http://www.mathjax.org/mathjax +SEARCHENGINE = YES +SERVER_BASED_SEARCH = NO +#--------------------------------------------------------------------------- +# configuration options related to the LaTeX output +#--------------------------------------------------------------------------- +GENERATE_LATEX = NO +LATEX_OUTPUT = latex +LATEX_CMD_NAME = latex +MAKEINDEX_CMD_NAME = makeindex +COMPACT_LATEX = YES +PAPER_TYPE = a4wide +EXTRA_PACKAGES = amsmath \ + amssymb +LATEX_HEADER = +PDF_HYPERLINKS = YES +USE_PDFLATEX = YES +LATEX_BATCHMODE = NO +LATEX_HIDE_INDICES = NO +LATEX_SOURCE_CODE = NO +#--------------------------------------------------------------------------- +# configuration options related to the RTF output +#--------------------------------------------------------------------------- +GENERATE_RTF = NO +RTF_OUTPUT = rtf +COMPACT_RTF = NO +RTF_HYPERLINKS = NO +RTF_STYLESHEET_FILE = +RTF_EXTENSIONS_FILE = +#--------------------------------------------------------------------------- +# configuration options related to the man page output +#--------------------------------------------------------------------------- +GENERATE_MAN = NO +MAN_OUTPUT = man +MAN_EXTENSION = .3 +MAN_LINKS = NO +#--------------------------------------------------------------------------- +# configuration options related to the XML output +#--------------------------------------------------------------------------- +GENERATE_XML = NO +XML_OUTPUT = xml +XML_SCHEMA = +XML_DTD = +XML_PROGRAMLISTING = YES +#--------------------------------------------------------------------------- +# configuration options for the AutoGen Definitions output +#--------------------------------------------------------------------------- +GENERATE_AUTOGEN_DEF = NO +#--------------------------------------------------------------------------- +# configuration options related to the Perl module output +#--------------------------------------------------------------------------- +GENERATE_PERLMOD = NO +PERLMOD_LATEX = NO +PERLMOD_PRETTY = YES +PERLMOD_MAKEVAR_PREFIX = +#--------------------------------------------------------------------------- +# Configuration options related to the preprocessor +#--------------------------------------------------------------------------- +ENABLE_PREPROCESSING = YES +MACRO_EXPANSION = NO +EXPAND_ONLY_PREDEF = NO +SEARCH_INCLUDES = YES +INCLUDE_PATH = +INCLUDE_FILE_PATTERNS = +PREDEFINED = DOXYGEN +EXPAND_AS_DEFINED = +SKIP_FUNCTION_MACROS = YES +#--------------------------------------------------------------------------- +# Configuration::additions related to external references +#--------------------------------------------------------------------------- +TAGFILES = "@abs_top_builddir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/ " +GENERATE_TAGFILE = html/lemon.tag +ALLEXTERNALS = NO +EXTERNAL_GROUPS = NO +PERL_PATH = /usr/bin/perl +#--------------------------------------------------------------------------- +# Configuration options related to the dot tool +#--------------------------------------------------------------------------- +CLASS_DIAGRAMS = YES +MSCGEN_PATH = +HIDE_UNDOC_RELATIONS = YES +HAVE_DOT = YES +DOT_NUM_THREADS = 0 +DOT_FONTNAME = FreeSans +DOT_FONTSIZE = 10 +DOT_FONTPATH = +CLASS_GRAPH = YES +COLLABORATION_GRAPH = NO +GROUP_GRAPHS = NO +UML_LOOK = NO +TEMPLATE_RELATIONS = NO +INCLUDE_GRAPH = NO +INCLUDED_BY_GRAPH = NO +CALL_GRAPH = NO +CALLER_GRAPH = NO +GRAPHICAL_HIERARCHY = NO +DIRECTORY_GRAPH = NO +DOT_IMAGE_FORMAT = png +DOT_PATH = +DOTFILE_DIRS = +MSCFILE_DIRS = +DOT_GRAPH_MAX_NODES = 50 +MAX_DOT_GRAPH_DEPTH = 0 +DOT_TRANSPARENT = NO +DOT_MULTI_TARGETS = NO +GENERATE_LEGEND = YES +DOT_CLEANUP = YES diff --git a/lemon/doc/DoxygenLayout.xml b/lemon/doc/DoxygenLayout.xml new file mode 100644 index 0000000..7085f8a --- /dev/null +++ b/lemon/doc/DoxygenLayout.xml @@ -0,0 +1,182 @@ +<doxygenlayout version="1.0"> + <!-- Navigation index tabs for HTML output --> + <navindex> + <tab type="mainpage" visible="yes" title=""/> + <tab type="modules" visible="yes" title="" intro=""/> + <tab type="classes" visible="yes" title=""> + <tab type="classes" visible="yes" title="" intro=""/> + <tab type="classindex" visible="$ALPHABETICAL_INDEX" title=""/> + <tab type="hierarchy" visible="yes" title="" intro=""/> + <tab type="classmembers" visible="yes" title="" intro=""/> + </tab> + <tab type="namespaces" visible="yes" title=""> + <tab type="namespaces" visible="yes" title="" intro=""/> + <tab type="namespacemembers" visible="yes" title="" intro=""/> + </tab> + <tab type="files" visible="yes" title=""> + <tab type="files" visible="yes" title="" intro=""/> + <tab type="globals" visible="yes" title="" intro=""/> + </tab> + <tab type="dirs" visible="yes" title="" intro=""/> + <tab type="examples" visible="yes" title="" intro=""/> + <tab type="pages" visible="yes" title="" intro=""/> + </navindex> + + <!-- Layout definition for a class page --> + <class> + <briefdescription visible="no"/> + <detaileddescription title=""/> + <includes visible="$SHOW_INCLUDE_FILES"/> + <inheritancegraph visible="$CLASS_GRAPH"/> + <collaborationgraph visible="$COLLABORATION_GRAPH"/> + <allmemberslink visible="yes"/> + <memberdecl> + <membergroups visible="yes"/> + <nestedclasses visible="yes" title=""/> + <publictypes title=""/> + <publicslots title=""/> + <signals title=""/> + <publicmethods title=""/> + <publicstaticmethods title=""/> + <publicattributes title=""/> + <publicstaticattributes title=""/> + <protectedtypes title=""/> + <protectedslots title=""/> + <protectedmethods title=""/> + <protectedstaticmethods title=""/> + <protectedattributes title=""/> + <protectedstaticattributes title=""/> + <packagetypes title=""/> + <packagemethods title=""/> + <packagestaticmethods title=""/> + <packageattributes title=""/> + <packagestaticattributes title=""/> + <properties title=""/> + <events title=""/> + <privatetypes title=""/> + <privateslots title=""/> + <privatemethods title=""/> + <privatestaticmethods title=""/> + <privateattributes title=""/> + <privatestaticattributes title=""/> + <friends title=""/> + <related title="" subtitle=""/> + </memberdecl> + <memberdef> + <typedefs title=""/> + <enums title=""/> + <constructors title=""/> + <functions title=""/> + <related title=""/> + <variables title=""/> + <properties title=""/> + <events title=""/> + </memberdef> + <usedfiles visible="$SHOW_USED_FILES"/> + <authorsection visible="yes"/> + </class> + + <!-- Layout definition for a namespace page --> + <namespace> + <briefdescription visible="no"/> + <detaileddescription title=""/> + <memberdecl> + <nestednamespaces visible="yes" title=""/> + <classes visible="yes" title=""/> + <membergroups visible="yes"/> + <typedefs title=""/> + <enums title=""/> + <functions title=""/> + <variables title=""/> + </memberdecl> + <memberdef> + <typedefs title=""/> + <enums title=""/> + <functions title=""/> + <variables title=""/> + </memberdef> + <authorsection visible="yes"/> + </namespace> + + <!-- Layout definition for a file page --> + <file> + <briefdescription visible="no"/> + <detaileddescription title=""/> + <includes visible="$SHOW_INCLUDE_FILES"/> + <includegraph visible="$INCLUDE_GRAPH"/> + <includedbygraph visible="$INCLUDED_BY_GRAPH"/> + <sourcelink visible="yes"/> + <memberdecl> + <classes visible="yes" title=""/> + <namespaces visible="yes" title=""/> + <defines title=""/> + <typedefs title=""/> + <enums title=""/> + <functions title=""/> + <variables title=""/> + </memberdecl> + <memberdef> + <defines title=""/> + <typedefs title=""/> + <enums title=""/> + <functions title=""/> + <variables title=""/> + </memberdef> + <authorsection/> + </file> + + <!-- Layout definition for a group page --> + <group> + <briefdescription visible="no"/> + <detaileddescription title=""/> + <groupgraph visible="$GROUP_GRAPHS"/> + <memberdecl> + <classes visible="yes" title=""/> + <namespaces visible="yes" title=""/> + <dirs visible="yes" title=""/> + <nestedgroups visible="yes" title=""/> + <files visible="yes" title=""/> + <defines title=""/> + <typedefs title=""/> + <enums title=""/> + <enumvalues title=""/> + <functions title=""/> + <variables title=""/> + <signals title=""/> + <publicslots title=""/> + <protectedslots title=""/> + <privateslots title=""/> + <events title=""/> + <properties title=""/> + <friends title=""/> + </memberdecl> + <memberdef> + <pagedocs/> + <defines title=""/> + <typedefs title=""/> + <enums title=""/> + <enumvalues title=""/> + <functions title=""/> + <variables title=""/> + <signals title=""/> + <publicslots title=""/> + <protectedslots title=""/> + <privateslots title=""/> + <events title=""/> + <properties title=""/> + <friends title=""/> + </memberdef> + <authorsection visible="yes"/> + </group> + + <!-- Layout definition for a directory page --> + <directory> + <briefdescription visible="no"/> + <detaileddescription title=""/> + <directorygraph visible="yes"/> + <memberdecl> + <dirs visible="yes"/> + <files visible="yes"/> + </memberdecl> + </directory> +</doxygenlayout> diff --git a/lemon/doc/Makefile.am b/lemon/doc/Makefile.am new file mode 100644 index 0000000..ee02e50 --- /dev/null +++ b/lemon/doc/Makefile.am @@ -0,0 +1,123 @@ +EXTRA_DIST += \ + doc/Doxyfile.in \ + doc/DoxygenLayout.xml \ + doc/coding_style.dox \ + doc/dirs.dox \ + doc/groups.dox \ + doc/lgf.dox \ + doc/license.dox \ + doc/mainpage.dox \ + doc/migration.dox \ + doc/min_cost_flow.dox \ + doc/named-param.dox \ + doc/namespaces.dox \ + doc/html \ + doc/CMakeLists.txt + +DOC_EPS_IMAGES18 = \ + grid_graph.eps \ + nodeshape_0.eps \ + nodeshape_1.eps \ + nodeshape_2.eps \ + nodeshape_3.eps \ + nodeshape_4.eps + +DOC_EPS_IMAGES27 = \ + bipartite_matching.eps \ + bipartite_partitions.eps \ + connected_components.eps \ + edge_biconnected_components.eps \ + matching.eps \ + node_biconnected_components.eps \ + planar.eps \ + strongly_connected_components.eps + +DOC_EPS_IMAGES = \ + $(DOC_EPS_IMAGES18) \ + $(DOC_EPS_IMAGES27) + +DOC_PNG_IMAGES = \ + $(DOC_EPS_IMAGES:%.eps=doc/gen-images/%.png) + +EXTRA_DIST += $(DOC_EPS_IMAGES:%=doc/images/%) + +doc/html: + $(MAKE) $(AM_MAKEFLAGS) html + +GS_COMMAND=gs -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 + +$(DOC_EPS_IMAGES18:%.eps=doc/gen-images/%.png): doc/gen-images/%.png: doc/images/%.eps + -mkdir doc/gen-images + if test ${gs_found} = yes; then \ + $(GS_COMMAND) -sDEVICE=pngalpha -r18 -sOutputFile=$@ $<; \ + else \ + echo; \ + echo "Ghostscript not found."; \ + echo; \ + exit 1; \ + fi + +$(DOC_EPS_IMAGES27:%.eps=doc/gen-images/%.png): doc/gen-images/%.png: doc/images/%.eps + -mkdir doc/gen-images + if test ${gs_found} = yes; then \ + $(GS_COMMAND) -sDEVICE=pngalpha -r27 -sOutputFile=$@ $<; \ + else \ + echo; \ + echo "Ghostscript not found."; \ + echo; \ + exit 1; \ + fi + +references.dox: doc/references.bib + if test ${python_found} = yes; then \ + cd doc; \ + python @abs_top_srcdir@/scripts/bib2dox.py @abs_top_builddir@/$< >$@; \ + cd ..; \ + else \ + echo; \ + echo "Python not found."; \ + echo; \ + exit 1; \ + fi + +html-local: $(DOC_PNG_IMAGES) references.dox + if test ${doxygen_found} = yes; then \ + cd doc; \ + doxygen Doxyfile; \ + cd ..; \ + else \ + echo; \ + echo "Doxygen not found."; \ + echo; \ + exit 1; \ + fi + +clean-local: + -rm -rf doc/html + -rm -f doc/doxygen.log + -rm -f $(DOC_PNG_IMAGES) + -rm -rf doc/gen-images + +update-external-tags: + wget -O doc/libstdc++.tag.tmp http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag && \ + mv doc/libstdc++.tag.tmp doc/libstdc++.tag || \ + rm doc/libstdc++.tag.tmp + +install-html-local: doc/html + @$(NORMAL_INSTALL) + $(mkinstalldirs) $(DESTDIR)$(htmldir)/html + for p in doc/html/*.{html,css,png,map,gif,tag} ; do \ + f="`echo $$p | sed -e 's|^.*/||'`"; \ + echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f"; \ + $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f; \ + done + +uninstall-local: + @$(NORMAL_UNINSTALL) + for p in doc/html/*.{html,css,png,map,gif,tag} ; do \ + f="`echo $$p | sed -e 's|^.*/||'`"; \ + echo " rm -f $(DESTDIR)$(htmldir)/html/$$f"; \ + rm -f $(DESTDIR)$(htmldir)/html/$$f; \ + done + +.PHONY: update-external-tags diff --git a/lemon/doc/coding_style.dox b/lemon/doc/coding_style.dox new file mode 100644 index 0000000..5c6af26 --- /dev/null +++ b/lemon/doc/coding_style.dox @@ -0,0 +1,127 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2009 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +/*! + +\page coding_style LEMON Coding Style + +\section naming_conv Naming Conventions + +In order to make development easier we have made some conventions +according to coding style. These include names of types, classes, +functions, variables, constants and exceptions. If these conventions +are met in one's code then it is easier to read and maintain +it. Please comply with these conventions if you want to contribute +developing LEMON library. + +\note When the coding style requires the capitalization of an abbreviation, +only the first letter should be upper case. + +\code +XmlReader +\endcode + + +\warning In some cases we diverge from these rules. +This is primary done because STL uses different naming convention and +in certain cases +it is beneficial to provide STL compatible interface. + +\subsection cs-files File Names + +The header file names should look like the following. + +\code +header_file.h +\endcode + +Note that all standard LEMON headers are located in the \c lemon subdirectory, +so you should include them from C++ source like this: + +\code +#include <lemon/header_file.h> +\endcode + +The source code files use the same style and they have '.cc' extension. + +\code +source_code.cc +\endcode + +\subsection cs-class Classes and other types + +The name of a class or any type should look like the following. + +\code +AllWordsCapitalizedWithoutUnderscores +\endcode + +\subsection cs-func Methods and other functions + +The name of a function should look like the following. + +\code +firstWordLowerCaseRestCapitalizedWithoutUnderscores +\endcode + +\subsection cs-funcs Constants, Macros + +The names of constants and macros should look like the following. + +\code +ALL_UPPER_CASE_WITH_UNDERSCORES +\endcode + +\subsection cs-loc-var Class and instance member variables, auto variables + +The names of class and instance member variables and auto variables +(=variables used locally in methods) should look like the following. + +\code +all_lower_case_with_underscores +\endcode + +\subsection pri-loc-var Private member variables + +Private member variables should start with underscore + +\code +_start_with_underscores +\endcode + +\subsection cs-excep Exceptions + +When writing exceptions please comply the following naming conventions. + +\code +ClassNameEndsWithException +\endcode + +or + +\code +ClassNameEndsWithError +\endcode + +\section header-template Template Header File + +Each LEMON header file should look like this: + +\include template.h + +*/ diff --git a/lemon/doc/dirs.dox b/lemon/doc/dirs.dox new file mode 100644 index 0000000..c242fb2 --- /dev/null +++ b/lemon/doc/dirs.dox @@ -0,0 +1,77 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2009 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +/** +\dir demo +\brief A collection of demo applications. + +This directory contains several simple demo applications, mainly +for educational purposes. +*/ + +/** +\dir doc +\brief Auxiliary (and the whole generated) documentation. + +This directory contains some auxiliary pages and the whole generated +documentation. +*/ + +/** +\dir test +\brief Test programs. + +This directory contains several test programs that check the consistency +of the code. +*/ + +/** +\dir tools +\brief Some useful executables. + +This directory contains the sources of some useful complete executables. +*/ + +/** +\dir lemon +\brief Base include directory of LEMON. + +This is the base directory of LEMON includes, so each include file must be +prefixed with this, e.g. +\code +#include<lemon/list_graph.h> +#include<lemon/dijkstra.h> +\endcode +*/ + +/** +\dir concepts +\brief Concept descriptors and checking classes. + +This directory contains the concept descriptors and concept checking tools. +For more information see the \ref concept "Concepts" module. +*/ + +/** +\dir bits +\brief Auxiliary tools for implementation. + +This directory contains some auxiliary classes for implementing graphs, +maps and some other classes. +As a user you typically don't have to deal with these files. +*/ diff --git a/lemon/doc/groups.dox b/lemon/doc/groups.dox new file mode 100644 index 0000000..7400979 --- /dev/null +++ b/lemon/doc/groups.dox @@ -0,0 +1,702 @@ +/* -*- 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. + * + */ + +namespace lemon { + +/** +@defgroup datas Data Structures +This group contains the several data structures implemented in LEMON. +*/ + +/** +@defgroup graphs Graph Structures +@ingroup datas +\brief Graph structures implemented in LEMON. + +The implementation of combinatorial algorithms heavily relies on +efficient graph implementations. LEMON offers data structures which are +planned to be easily used in an experimental phase of implementation studies, +and thereafter the program code can be made efficient by small modifications. + +The most efficient implementation of diverse applications require the +usage of different physical graph implementations. These differences +appear in the size of graph we require to handle, memory or time usage +limitations or in the set of operations through which the graph can be +accessed. LEMON provides several physical graph structures to meet +the diverging requirements of the possible users. In order to save on +running time or on memory usage, some structures may fail to provide +some graph features like arc/edge or node deletion. + +Alteration of standard containers need a very limited number of +operations, these together satisfy the everyday requirements. +In the case of graph structures, different operations are needed which do +not alter the physical graph, but gives another view. If some nodes or +arcs have to be hidden or the reverse oriented graph have to be used, then +this is the case. It also may happen that in a flow implementation +the residual graph can be accessed by another algorithm, or a node-set +is to be shrunk for another algorithm. +LEMON also provides a variety of graphs for these requirements called +\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only +in conjunction with other graph representations. + +You are free to use the graph structure that fit your requirements +the best, most graph algorithms and auxiliary data structures can be used +with any graph structure. + +<b>See also:</b> \ref graph_concepts "Graph Structure Concepts". +*/ + +/** +@defgroup graph_adaptors Adaptor Classes for Graphs +@ingroup graphs +\brief Adaptor classes for digraphs and graphs + +This group contains several useful adaptor classes for digraphs and graphs. + +The main parts of LEMON are the different graph structures, generic +graph algorithms, graph concepts, which couple them, and graph +adaptors. While the previous notions are more or less clear, the +latter one needs further explanation. Graph adaptors are graph classes +which serve for considering graph structures in different ways. + +A short example makes this much clearer. Suppose that we have an +instance \c g of a directed graph type, say ListDigraph and an algorithm +\code +template <typename Digraph> +int algorithm(const Digraph&); +\endcode +is needed to run on the reverse oriented graph. It may be expensive +(in time or in memory usage) to copy \c g with the reversed +arcs. In this case, an adaptor class is used, which (according +to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph. +The adaptor uses the original digraph structure and digraph operations when +methods of the reversed oriented graph are called. This means that the adaptor +have minor memory usage, and do not perform sophisticated algorithmic +actions. The purpose of it is to give a tool for the cases when a +graph have to be used in a specific alteration. If this alteration is +obtained by a usual construction like filtering the node or the arc set or +considering a new orientation, then an adaptor is worthwhile to use. +To come back to the reverse oriented graph, in this situation +\code +template<typename Digraph> class ReverseDigraph; +\endcode +template class can be used. The code looks as follows +\code +ListDigraph g; +ReverseDigraph<ListDigraph> rg(g); +int result = algorithm(rg); +\endcode +During running the algorithm, the original digraph \c g is untouched. +This techniques give rise to an elegant code, and based on stable +graph adaptors, complex algorithms can be implemented easily. + +In flow, circulation and matching problems, the residual +graph is of particular importance. Combining an adaptor implementing +this with shortest path algorithms or minimum mean cycle algorithms, +a range of weighted and cardinality optimization algorithms can be +obtained. For other examples, the interested user is referred to the +detailed documentation of particular adaptors. + +The behavior of graph adaptors can be very different. Some of them keep +capabilities of the original graph while in other cases this would be +meaningless. This means that the concepts that they meet depend +on the graph adaptor, and the wrapped graph. +For example, if an arc of a reversed digraph is deleted, this is carried +out by deleting the corresponding arc of the original digraph, thus the +adaptor modifies the original digraph. +However in case of a residual digraph, this operation has no sense. + +Let us stand one more example here to simplify your work. +ReverseDigraph has constructor +\code +ReverseDigraph(Digraph& digraph); +\endcode +This means that in a situation, when a <tt>const %ListDigraph&</tt> +reference to a graph is given, then it have to be instantiated with +<tt>Digraph=const %ListDigraph</tt>. +\code +int algorithm1(const ListDigraph& g) { + ReverseDigraph<const ListDigraph> rg(g); + return algorithm2(rg); +} +\endcode +*/ + +/** +@defgroup maps Maps +@ingroup datas +\brief Map structures implemented in LEMON. + +This group contains the map structures implemented in LEMON. + +LEMON provides several special purpose maps and map adaptors that e.g. combine +new maps from existing ones. + +<b>See also:</b> \ref map_concepts "Map Concepts". +*/ + +/** +@defgroup graph_maps Graph Maps +@ingroup maps +\brief Special graph-related maps. + +This group contains maps that are specifically designed to assign +values to the nodes and arcs/edges of graphs. + +If you are looking for the standard graph maps (\c NodeMap, \c ArcMap, +\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts". +*/ + +/** +\defgroup map_adaptors Map Adaptors +\ingroup maps +\brief Tools to create new maps from existing ones + +This group contains map adaptors that are used to create "implicit" +maps from other maps. + +Most of them are \ref concepts::ReadMap "read-only maps". +They can make arithmetic and logical operations between one or two maps +(negation, shifting, addition, multiplication, logical 'and', 'or', +'not' etc.) or e.g. convert a map to another one of different Value type. + +The typical usage of this classes is passing implicit maps to +algorithms. If a function type algorithm is called then the function +type map adaptors can be used comfortable. For example let's see the +usage of map adaptors with the \c graphToEps() function. +\code + Color nodeColor(int deg) { + if (deg >= 2) { + return Color(0.5, 0.0, 0.5); + } else if (deg == 1) { + return Color(1.0, 0.5, 1.0); + } else { + return Color(0.0, 0.0, 0.0); + } + } + + Digraph::NodeMap<int> degree_map(graph); + + graphToEps(graph, "graph.eps") + .coords(coords).scaleToA4().undirected() + .nodeColors(composeMap(functorToMap(nodeColor), degree_map)) + .run(); +\endcode +The \c functorToMap() function makes an \c int to \c Color map from the +\c nodeColor() function. The \c composeMap() compose the \c degree_map +and the previously created map. The composed map is a proper function to +get the color of each node. + +The usage with class type algorithms is little bit harder. In this +case the function type map adaptors can not be used, because the +function map adaptors give back temporary objects. +\code + Digraph graph; + + typedef Digraph::ArcMap<double> DoubleArcMap; + DoubleArcMap length(graph); + DoubleArcMap speed(graph); + + typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap; + TimeMap time(length, speed); + + Dijkstra<Digraph, TimeMap> dijkstra(graph, time); + dijkstra.run(source, target); +\endcode +We have a length map and a maximum speed map on the arcs of a digraph. +The minimum time to pass the arc can be calculated as the division of +the two maps which can be done implicitly with the \c DivMap template +class. We use the implicit minimum time map as the length map of the +\c Dijkstra algorithm. +*/ + +/** +@defgroup paths Path Structures +@ingroup datas +\brief %Path structures implemented in LEMON. + +This group contains the path structures implemented in LEMON. + +LEMON provides flexible data structures to work with paths. +All of them have similar interfaces and they can be copied easily with +assignment operators and copy constructors. This makes it easy and +efficient to have e.g. the Dijkstra algorithm to store its result in +any kind of path structure. + +\sa \ref concepts::Path "Path concept" +*/ + +/** +@defgroup heaps Heap Structures +@ingroup datas +\brief %Heap structures implemented in LEMON. + +This group contains the heap structures implemented in LEMON. + +LEMON provides several heap classes. They are efficient implementations +of the abstract data type \e priority \e queue. They store items with +specified values called \e priorities in such a way that finding and +removing the item with minimum priority are efficient. +The basic operations are adding and erasing items, changing the priority +of an item, etc. + +Heaps are crucial in several algorithms, such as Dijkstra and Prim. +The heap implementations have the same interface, thus any of them can be +used easily in such algorithms. + +\sa \ref concepts::Heap "Heap concept" +*/ + +/** +@defgroup auxdat Auxiliary Data Structures +@ingroup datas +\brief Auxiliary data structures implemented in LEMON. + +This group contains some data structures implemented in LEMON in +order to make it easier to implement combinatorial algorithms. +*/ + +/** +@defgroup geomdat Geometric Data Structures +@ingroup auxdat +\brief Geometric data structures implemented in LEMON. + +This group contains geometric data structures implemented in LEMON. + + - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional + vector with the usual operations. + - \ref lemon::dim2::Box "dim2::Box" can be used to determine the + rectangular bounding box of a set of \ref lemon::dim2::Point + "dim2::Point"'s. +*/ + +/** +@defgroup algs Algorithms +\brief This group contains the several algorithms +implemented in LEMON. + +This group contains the several algorithms +implemented in LEMON. +*/ + +/** +@defgroup search Graph Search +@ingroup algs +\brief Common graph search algorithms. + +This group contains the common graph search algorithms, namely +\e breadth-first \e search (BFS) and \e depth-first \e search (DFS) +\ref clrs01algorithms. +*/ + +/** +@defgroup shortest_path Shortest Path Algorithms +@ingroup algs +\brief Algorithms for finding shortest paths. + +This group contains the algorithms for finding shortest paths in digraphs +\ref clrs01algorithms. + + - \ref Dijkstra algorithm for finding shortest paths from a source node + when all arc lengths are non-negative. + - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths + from a source node when arc lenghts can be either positive or negative, + but the digraph should not contain directed cycles with negative total + length. + - \ref Suurballe A successive shortest path algorithm for finding + arc-disjoint paths between two nodes having minimum total length. +*/ + +/** +@defgroup spantree Minimum Spanning Tree Algorithms +@ingroup algs +\brief Algorithms for finding minimum cost spanning trees and arborescences. + +This group contains the algorithms for finding minimum cost spanning +trees and arborescences \ref clrs01algorithms. +*/ + +/** +@defgroup max_flow Maximum Flow Algorithms +@ingroup algs +\brief Algorithms for finding maximum flows. + +This group contains the algorithms for finding maximum flows and +feasible circulations \ref clrs01algorithms, \ref amo93networkflows. + +The \e maximum \e flow \e problem is to find a flow of maximum value between +a single source and a single target. Formally, there is a \f$G=(V,A)\f$ +digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and +\f$s, t \in V\f$ source and target nodes. +A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the +following optimization problem. + +\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f] +\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu) + \quad \forall u\in V\setminus\{s,t\} \f] +\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] + +\ref Preflow is an efficient implementation of Goldberg-Tarjan's +preflow push-relabel algorithm \ref goldberg88newapproach for finding +maximum flows. It also provides functions to query the minimum cut, +which is the dual problem of maximum flow. + +\ref Circulation is a preflow push-relabel algorithm implemented directly +for finding feasible circulations, which is a somewhat different problem, +but it is strongly related to maximum flow. +For more information, see \ref Circulation. +*/ + +/** +@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms +@ingroup algs + +\brief Algorithms for finding minimum cost flows and circulations. + +This group contains the algorithms for finding minimum cost flows and +circulations \ref amo93networkflows. For more information about this +problem and its dual solution, see \ref min_cost_flow +"Minimum Cost Flow Problem". + +LEMON contains several algorithms for this problem. + - \ref NetworkSimplex Primal Network Simplex algorithm with various + pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex. + - \ref CostScaling Cost Scaling algorithm based on push/augment and + relabel operations \ref goldberg90approximation, \ref goldberg97efficient, + \ref bunnagel98efficient. + - \ref CapacityScaling Capacity Scaling algorithm based on the successive + shortest path method \ref edmondskarp72theoretical. + - \ref CycleCanceling Cycle-Canceling algorithms, two of which are + strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling. + +In general NetworkSimplex is the most efficient implementation, +but in special cases other algorithms could be faster. +For example, if the total supply and/or capacities are rather small, +CapacityScaling is usually the fastest algorithm (without effective scaling). +*/ + +/** +@defgroup min_cut Minimum Cut Algorithms +@ingroup algs + +\brief Algorithms for finding minimum cut in graphs. + +This group contains the algorithms for finding minimum cut in graphs. + +The \e minimum \e cut \e problem is to find a non-empty and non-complete +\f$X\f$ subset of the nodes with minimum overall capacity on +outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a +\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum +cut is the \f$X\f$ solution of the next optimization problem: + +\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}} + \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f] + +LEMON contains several algorithms related to minimum cut problems: + +- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut + in directed graphs. +- \ref GomoryHu "Gomory-Hu tree computation" for calculating + all-pairs minimum cut in undirected graphs. + +If you want to find minimum cut just between two distinict nodes, +see the \ref max_flow "maximum flow problem". +*/ + +/** +@defgroup min_mean_cycle Minimum Mean Cycle Algorithms +@ingroup algs +\brief Algorithms for finding minimum mean cycles. + +This group contains the algorithms for finding minimum mean cycles +\ref clrs01algorithms, \ref amo93networkflows. + +The \e minimum \e mean \e cycle \e problem is to find a directed cycle +of minimum mean length (cost) in a digraph. +The mean length of a cycle is the average length of its arcs, i.e. the +ratio between the total length of the cycle and the number of arcs on it. + +This problem has an important connection to \e conservative \e length +\e functions, too. A length function on the arcs of a digraph is called +conservative if and only if there is no directed cycle of negative total +length. For an arbitrary length function, the negative of the minimum +cycle mean is the smallest \f$\epsilon\f$ value so that increasing the +arc lengths uniformly by \f$\epsilon\f$ results in a conservative length +function. + +LEMON contains three algorithms for solving the minimum mean cycle problem: +- \ref KarpMmc Karp's original algorithm \ref amo93networkflows, + \ref dasdan98minmeancycle. +- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved + version of Karp's algorithm \ref dasdan98minmeancycle. +- \ref HowardMmc Howard's policy iteration algorithm + \ref dasdan98minmeancycle. + +In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the +most efficient one, though the best known theoretical bound on its running +time is exponential. +Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms +run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is +typically faster due to the applied early termination scheme. +*/ + +/** +@defgroup matching Matching Algorithms +@ingroup algs +\brief Algorithms for finding matchings in graphs and bipartite graphs. + +This group contains the algorithms for calculating +matchings in graphs and bipartite graphs. The general matching problem is +finding a subset of the edges for which each node has at most one incident +edge. + +There are several different algorithms for calculate matchings in +graphs. The matching problems in bipartite graphs are generally +easier than in general graphs. The goal of the matching optimization +can be finding maximum cardinality, maximum weight or minimum cost +matching. The search can be constrained to find perfect or +maximum cardinality matching. + +The matching algorithms implemented in LEMON: +- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating + maximum cardinality matching in general graphs. +- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating + maximum weighted matching in general graphs. +- \ref MaxWeightedPerfectMatching + Edmond's blossom shrinking algorithm for calculating maximum weighted + perfect matching in general graphs. +- \ref MaxFractionalMatching Push-relabel algorithm for calculating + maximum cardinality fractional matching in general graphs. +- \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating + maximum weighted fractional matching in general graphs. +- \ref MaxWeightedPerfectFractionalMatching + Augmenting path algorithm for calculating maximum weighted + perfect fractional matching in general graphs. + +\image html matching.png +\image latex matching.eps "Min Cost Perfect Matching" width=\textwidth +*/ + +/** +@defgroup graph_properties Connectivity and Other Graph Properties +@ingroup algs +\brief Algorithms for discovering the graph properties + +This group contains the algorithms for discovering the graph properties +like connectivity, bipartiteness, euler property, simplicity etc. + +\image html connected_components.png +\image latex connected_components.eps "Connected components" width=\textwidth +*/ + +/** +@defgroup planar Planarity Embedding and Drawing +@ingroup algs +\brief Algorithms for planarity checking, embedding and drawing + +This group contains the algorithms for planarity checking, +embedding and drawing. + +\image html planar.png +\image latex planar.eps "Plane graph" width=\textwidth +*/ + +/** +@defgroup auxalg Auxiliary Algorithms +@ingroup algs +\brief Auxiliary algorithms implemented in LEMON. + +This group contains some algorithms implemented in LEMON +in order to make it easier to implement complex algorithms. +*/ + +/** +@defgroup gen_opt_group General Optimization Tools +\brief This group contains some general optimization frameworks +implemented in LEMON. + +This group contains some general optimization frameworks +implemented in LEMON. +*/ + +/** +@defgroup lp_group LP and MIP Solvers +@ingroup gen_opt_group +\brief LP and MIP solver interfaces for LEMON. + +This group contains LP and MIP solver interfaces for LEMON. +Various LP solvers could be used in the same manner with this +high-level interface. + +The currently supported solvers are \ref glpk, \ref clp, \ref cbc, +\ref cplex, \ref soplex. +*/ + +/** +@defgroup utils Tools and Utilities +\brief Tools and utilities for programming in LEMON + +Tools and utilities for programming in LEMON. +*/ + +/** +@defgroup gutils Basic Graph Utilities +@ingroup utils +\brief Simple basic graph utilities. + +This group contains some simple basic graph utilities. +*/ + +/** +@defgroup misc Miscellaneous Tools +@ingroup utils +\brief Tools for development, debugging and testing. + +This group contains several useful tools for development, +debugging and testing. +*/ + +/** +@defgroup timecount Time Measuring and Counting +@ingroup misc +\brief Simple tools for measuring the performance of algorithms. + +This group contains simple tools for measuring the performance +of algorithms. +*/ + +/** +@defgroup exceptions Exceptions +@ingroup utils +\brief Exceptions defined in LEMON. + +This group contains the exceptions defined in LEMON. +*/ + +/** +@defgroup io_group Input-Output +\brief Graph Input-Output methods + +This group contains the tools for importing and exporting graphs +and graph related data. Now it supports the \ref lgf-format +"LEMON Graph Format", the \c DIMACS format and the encapsulated +postscript (EPS) format. +*/ + +/** +@defgroup lemon_io LEMON Graph Format +@ingroup io_group +\brief Reading and writing LEMON Graph Format. + +This group contains methods for reading and writing +\ref lgf-format "LEMON Graph Format". +*/ + +/** +@defgroup eps_io Postscript Exporting +@ingroup io_group +\brief General \c EPS drawer and graph exporter + +This group contains general \c EPS drawing methods and special +graph exporting tools. +*/ + +/** +@defgroup dimacs_group DIMACS Format +@ingroup io_group +\brief Read and write files in DIMACS format + +Tools to read a digraph from or write it to a file in DIMACS format data. +*/ + +/** +@defgroup nauty_group NAUTY Format +@ingroup io_group +\brief Read \e Nauty format + +Tool to read graphs from \e Nauty format data. +*/ + +/** +@defgroup concept Concepts +\brief Skeleton classes and concept checking classes + +This group contains the data/algorithm skeletons and concept checking +classes implemented in LEMON. + +The purpose of the classes in this group is fourfold. + +- These classes contain the documentations of the %concepts. In order + to avoid document multiplications, an implementation of a concept + simply refers to the corresponding concept class. + +- These classes declare every functions, <tt>typedef</tt>s etc. an + implementation of the %concepts should provide, however completely + without implementations and real data structures behind the + interface. On the other hand they should provide nothing else. All + the algorithms working on a data structure meeting a certain concept + should compile with these classes. (Though it will not run properly, + of course.) In this way it is easily to check if an algorithm + doesn't use any extra feature of a certain implementation. + +- The concept descriptor classes also provide a <em>checker class</em> + that makes it possible to check whether a certain implementation of a + concept indeed provides all the required features. + +- Finally, They can serve as a skeleton of a new implementation of a concept. +*/ + +/** +@defgroup graph_concepts Graph Structure Concepts +@ingroup concept +\brief Skeleton and concept checking classes for graph structures + +This group contains the skeletons and concept checking classes of +graph structures. +*/ + +/** +@defgroup map_concepts Map Concepts +@ingroup concept +\brief Skeleton and concept checking classes for maps + +This group contains the skeletons and concept checking classes of maps. +*/ + +/** +@defgroup tools Standalone Utility Applications + +Some utility applications are listed here. + +The standard compilation procedure (<tt>./configure;make</tt>) will compile +them, as well. +*/ + +/** +\anchor demoprograms + +@defgroup demos Demo Programs + +Some demo programs are listed here. Their full source codes can be found in +the \c demo subdirectory of the source tree. + +In order to compile them, use the <tt>make demo</tt> or the +<tt>make check</tt> commands. +*/ + +} diff --git a/lemon/doc/images/bipartite_matching.eps b/lemon/doc/images/bipartite_matching.eps new file mode 100644 index 0000000..b5683cb --- /dev/null +++ b/lemon/doc/images/bipartite_matching.eps @@ -0,0 +1,586 @@ +%!PS-Adobe-3.0 EPSF-3.0 +%%BoundingBox: 15 18 829 570 +%%HiResBoundingBox: 15.1913 18.4493 828.078 569.438 +%%Creator: Karbon14 EPS Exportfilter 0.5 +%%CreationDate: (04/15/06 15:20:26) +%%For: (Balazs Dezso) () +%%Title: () + +/N {newpath} def +/C {closepath} def +/m {moveto} def +/c {curveto} def +/l {lineto} def +/s {stroke} def +/f {fill} def +/w {setlinewidth} def +/d {setdash} def +/r {setrgbcolor} def +/S {gsave} def +/R {grestore} def + +N +251.402 32.047 m +532.945 293.946 814.484 555.844 814.484 555.844 c +[] 0 d 1 0 0 r 3.92814 w s + +N +749.012 32.047 m +742.465 293.946 735.918 555.844 735.918 555.844 c +[] 0 d 0 0 0 r 1.96407 w s + +N +539.492 32.047 m +637.703 293.946 735.918 555.844 735.918 555.844 c +[] 0 d 0 0 0 r 1.96407 w s + +N +172.832 32.047 m +454.375 293.946 735.918 555.844 735.918 555.844 c +[] 0 d 0 0 0 r 1.96407 w s + +N +107.355 32.047 m +421.637 293.946 735.918 555.844 735.918 555.844 c +[] 0 d 1 0 0 r 3.92814 w s + +N +644.25 555.844 m +696.633 293.946 749.012 32.047 749.012 32.047 c +[] 0 d 0 0 0 r 1.96407 w s + +N +474.016 555.844 m +611.516 293.946 749.012 32.047 749.012 32.047 c +[] 0 d 1 0 0 r 3.92814 w s + +N +683.535 32.047 m +663.894 293.946 644.25 555.844 644.25 555.844 c +[] 0 d 0 0 0 r 1.96407 w s + +N +120.453 555.844 m +401.992 293.946 683.535 32.047 683.535 32.047 c +[] 0 d 0 0 0 r 1.96407 w s + +N +28.7853 555.844 m +356.16 293.946 683.535 32.047 683.535 32.047 c +[] 0 d 1 0 0 r 3.92814 w s + +N +539.492 32.047 m +546.039 293.946 552.586 555.844 552.586 555.844 c +[] 0 d 1 0 0 r 3.92814 w s + +N +316.875 32.047 m +349.613 293.946 382.351 555.844 382.351 555.844 c +[] 0 d 1 0 0 r 3.92814 w s + +N +107.355 32.047 m +244.855 293.946 382.351 555.844 382.351 555.844 c +[] 0 d 0 0 0 r 1.96407 w s + +N +290.687 555.844 m +375.805 293.946 460.922 32.047 460.922 32.047 c +[] 0 d 1 0 0 r 3.92814 w s + +N +120.453 555.844 m +290.687 293.946 460.922 32.047 460.922 32.047 c +[] 0 d 0 0 0 r 1.96407 w s + +N +172.832 32.047 m +146.64 293.946 120.453 555.844 120.453 555.844 c +[] 0 d 1 0 0 r 3.92814 w s + +N +15.6913 555.844 m +15.6913 555.844 l +15.6913 548.614 21.5553 542.75 28.7853 542.75 c +36.0163 542.75 41.8833 548.614 41.8833 555.844 c +41.8833 563.075 36.0163 568.938 28.7853 568.938 c +21.5553 568.938 15.6913 563.075 15.6913 555.844 c +15.6913 555.844 l +C +S 0 0 0 r f R + +N +16.8833 555.844 m +16.8833 555.844 l +16.8833 549.27 22.2113 543.942 28.7853 543.942 c +35.3593 543.942 40.6913 549.27 40.6913 555.844 c +40.6913 562.418 35.3593 567.747 28.7853 567.747 c +22.2113 567.747 16.8833 562.418 16.8833 555.844 c +16.8833 555.844 l +C +S 1 0.5 1 r f R + +N +107.355 555.844 m +107.355 555.844 l +107.355 548.614 113.223 542.75 120.453 542.75 c +127.683 542.75 133.547 548.614 133.547 555.844 c +133.547 563.075 127.683 568.938 120.453 568.938 c +113.223 568.938 107.355 563.075 107.355 555.844 c +107.355 555.844 l +C +S 0 0 0 r f R + +N +108.547 555.844 m +108.547 555.844 l +108.547 549.27 113.879 543.942 120.453 543.942 c +127.027 543.942 132.355 549.27 132.355 555.844 c +132.355 562.418 127.027 567.747 120.453 567.747 c +113.879 567.747 108.547 562.418 108.547 555.844 c +108.547 555.844 l +C +S 1 0 1 r f R + +N +199.019 555.844 m +199.019 555.844 l +199.019 548.614 204.887 542.75 212.117 542.75 c +219.348 542.75 225.211 548.614 225.211 555.844 c +225.211 563.075 219.348 568.938 212.117 568.938 c +204.887 568.938 199.019 563.075 199.019 555.844 c +199.019 555.844 l +C +S 0 0 0 r f R + +N +200.211 555.844 m +200.211 555.844 l +200.211 549.27 205.543 543.942 212.117 543.942 c +218.691 543.942 224.019 549.27 224.019 555.844 c +224.019 562.418 218.691 567.747 212.117 567.747 c +205.543 567.747 200.211 562.418 200.211 555.844 c +200.211 555.844 l +C +S 1 0.5 1 r f R + +N +277.59 555.844 m +277.59 555.844 l +277.59 548.614 283.457 542.75 290.687 542.75 c +297.918 542.75 303.781 548.614 303.781 555.844 c +303.781 563.075 297.918 568.938 290.687 568.938 c +283.457 568.938 277.59 563.075 277.59 555.844 c +277.59 555.844 l +C +S 0 0 0 r f R + +N +278.781 555.844 m +278.781 555.844 l +278.781 549.27 284.113 543.942 290.687 543.942 c +297.262 543.942 302.59 549.27 302.59 555.844 c +302.59 562.418 297.262 567.747 290.687 567.747 c +284.113 567.747 278.781 562.418 278.781 555.844 c +278.781 555.844 l +C +S 1 0 1 r f R + +N +369.258 555.844 m +369.258 555.844 l +369.258 548.614 375.121 542.75 382.351 542.75 c +389.582 542.75 395.445 548.614 395.445 555.844 c +395.445 563.075 389.582 568.938 382.351 568.938 c +375.121 568.938 369.258 563.075 369.258 555.844 c +369.258 555.844 l +C +S 0 0 0 r f R + +N +370.445 555.844 m +370.445 555.844 l +370.445 549.27 375.777 543.942 382.351 543.942 c +388.926 543.942 394.258 549.27 394.258 555.844 c +394.258 562.418 388.926 567.747 382.351 567.747 c +375.777 567.747 370.445 562.418 370.445 555.844 c +370.445 555.844 l +C +S 1 0 1 r f R + +N +460.922 555.844 m +460.922 555.844 l +460.922 548.614 466.785 542.75 474.016 542.75 c +481.246 542.75 487.109 548.614 487.109 555.844 c +487.109 563.075 481.246 568.938 474.016 568.938 c +466.785 568.938 460.922 563.075 460.922 555.844 c +460.922 555.844 l +C +S 0 0 0 r f R + +N +462.113 555.844 m +462.113 555.844 l +462.113 549.27 467.441 543.942 474.016 543.942 c +480.59 543.942 485.922 549.27 485.922 555.844 c +485.922 562.418 480.59 567.747 474.016 567.747 c +467.441 567.747 462.113 562.418 462.113 555.844 c +462.113 555.844 l +C +S 1 0.5 1 r f R + +N +539.492 555.844 m +539.492 555.844 l +539.492 548.614 545.355 542.75 552.586 542.75 c +559.816 542.75 565.68 548.614 565.68 555.844 c +565.68 563.075 559.816 568.938 552.586 568.938 c +545.355 568.938 539.492 563.075 539.492 555.844 c +539.492 555.844 l +C +S 0 0 0 r f R + +N +540.683 555.844 m +540.683 555.844 l +540.683 549.27 546.012 543.942 552.586 543.942 c +559.16 543.942 564.492 549.27 564.492 555.844 c +564.492 562.418 559.16 567.747 552.586 567.747 c +546.012 567.747 540.683 562.418 540.683 555.844 c +540.683 555.844 l +C +S 1 0 1 r f R + +N +631.156 555.844 m +631.156 555.844 l +631.156 548.614 637.019 542.75 644.25 542.75 c +651.48 542.75 657.348 548.614 657.348 555.844 c +657.348 563.075 651.48 568.938 644.25 568.938 c +637.019 568.938 631.156 563.075 631.156 555.844 c +631.156 555.844 l +C +S 0 0 0 r f R + +N +632.348 555.844 m +632.348 555.844 l +632.348 549.27 637.676 543.942 644.25 543.942 c +650.824 543.942 656.156 549.27 656.156 555.844 c +656.156 562.418 650.824 567.747 644.25 567.747 c +637.676 567.747 632.348 562.418 632.348 555.844 c +632.348 555.844 l +C +S 1 0.5 1 r f R + +N +722.82 555.844 m +722.82 555.844 l +722.82 548.614 728.687 542.75 735.918 542.75 c +743.149 542.75 749.012 548.614 749.012 555.844 c +749.012 563.075 743.149 568.938 735.918 568.938 c +728.687 568.938 722.82 563.075 722.82 555.844 c +722.82 555.844 l +C +S 0 0 0 r f R + +N +724.012 555.844 m +724.012 555.844 l +724.012 549.27 729.344 543.942 735.918 543.942 c +742.492 543.942 747.82 549.27 747.82 555.844 c +747.82 562.418 742.492 567.747 735.918 567.747 c +729.344 567.747 724.012 562.418 724.012 555.844 c +724.012 555.844 l +C +S 1 0 1 r f R + +N +801.391 555.844 m +801.391 555.844 l +801.391 548.614 807.254 542.75 814.484 542.75 c +821.715 542.75 827.578 548.614 827.578 555.844 c +827.578 563.075 821.715 568.938 814.484 568.938 c +807.254 568.938 801.391 563.075 801.391 555.844 c +801.391 555.844 l +C +S 0 0 0 r f R + +N +802.582 555.844 m +802.582 555.844 l +802.582 549.27 807.91 543.942 814.484 543.942 c +821.059 543.942 826.387 549.27 826.387 555.844 c +826.387 562.418 821.059 567.747 814.484 567.747 c +807.91 567.747 802.582 562.418 802.582 555.844 c +802.582 555.844 l +C +S 1 0 1 r f R + +N +15.6913 32.047 m +15.6913 32.047 l +15.6913 24.8165 21.5553 18.9493 28.7853 18.9493 c +36.0163 18.9493 41.8833 24.8165 41.8833 32.047 c +41.8833 39.2775 36.0163 45.1407 28.7853 45.1407 c +21.5553 45.1407 15.6913 39.2775 15.6913 32.047 c +15.6913 32.047 l +C +S 0 0 0 r f R + +N +16.8833 32.047 m +16.8833 32.047 l +16.8833 25.4728 22.2113 20.1407 28.7853 20.1407 c +35.3593 20.1407 40.6913 25.4728 40.6913 32.047 c +40.6913 38.6212 35.3593 43.9493 28.7853 43.9493 c +22.2113 43.9493 16.8833 38.6212 16.8833 32.047 c +16.8833 32.047 l +C +S 0.5 0.5 1 r f R + +N +94.2623 32.047 m +94.2623 32.047 l +94.2623 24.8165 100.125 18.9493 107.355 18.9493 c +114.586 18.9493 120.453 24.8165 120.453 32.047 c +120.453 39.2775 114.586 45.1407 107.355 45.1407 c +100.125 45.1407 94.2623 39.2775 94.2623 32.047 c +94.2623 32.047 l +C +S 0 0 0 r f R + +N +95.4533 32.047 m +95.4533 32.047 l +95.4533 25.4728 100.781 20.1407 107.355 20.1407 c +113.93 20.1407 119.262 25.4728 119.262 32.047 c +119.262 38.6212 113.93 43.9493 107.355 43.9493 c +100.781 43.9493 95.4533 38.6212 95.4533 32.047 c +95.4533 32.047 l +C +S 0.5 0.5 1 r f R + +N +159.734 32.047 m +159.734 32.047 l +159.734 24.8165 165.601 18.9493 172.832 18.9493 c +180.062 18.9493 185.926 24.8165 185.926 32.047 c +185.926 39.2775 180.062 45.1407 172.832 45.1407 c +165.601 45.1407 159.734 39.2775 159.734 32.047 c +159.734 32.047 l +C +S 0 0 0 r f R + +N +160.926 32.047 m +160.926 32.047 l +160.926 25.4728 166.258 20.1407 172.832 20.1407 c +179.406 20.1407 184.734 25.4728 184.734 32.047 c +184.734 38.6212 179.406 43.9493 172.832 43.9493 c +166.258 43.9493 160.926 38.6212 160.926 32.047 c +160.926 32.047 l +C +S 0.5 0.5 1 r f R + +N +238.305 32.047 m +238.305 32.047 l +238.305 24.8165 244.172 18.9493 251.402 18.9493 c +258.633 18.9493 264.496 24.8165 264.496 32.047 c +264.496 39.2775 258.633 45.1407 251.402 45.1407 c +244.172 45.1407 238.305 39.2775 238.305 32.047 c +238.305 32.047 l +C +S 0 0 0 r f R + +N +239.496 32.047 m +239.496 32.047 l +239.496 25.4728 244.828 20.1407 251.402 20.1407 c +257.976 20.1407 263.305 25.4728 263.305 32.047 c +263.305 38.6212 257.976 43.9493 251.402 43.9493 c +244.828 43.9493 239.496 38.6212 239.496 32.047 c +239.496 32.047 l +C +S 0.5 0.5 1 r f R + +N +303.781 32.047 m +303.781 32.047 l +303.781 24.8165 309.644 18.9493 316.875 18.9493 c +324.105 18.9493 329.973 24.8165 329.973 32.047 c +329.973 39.2775 324.105 45.1407 316.875 45.1407 c +309.644 45.1407 303.781 39.2775 303.781 32.047 c +303.781 32.047 l +C +S 0 0 0 r f R + +N +304.973 32.047 m +304.973 32.047 l +304.973 25.4728 310.301 20.1407 316.875 20.1407 c +323.449 20.1407 328.781 25.4728 328.781 32.047 c +328.781 38.6212 323.449 43.9493 316.875 43.9493 c +310.301 43.9493 304.973 38.6212 304.973 32.047 c +304.973 32.047 l +C +S 0.5 0.5 1 r f R + +N +382.351 32.047 m +382.351 32.047 l +382.351 24.8165 388.215 18.9493 395.445 18.9493 c +402.676 18.9493 408.543 24.8165 408.543 32.047 c +408.543 39.2775 402.676 45.1407 395.445 45.1407 c +388.215 45.1407 382.351 39.2775 382.351 32.047 c +382.351 32.047 l +C +S 0 0 0 r f R + +N +383.543 32.047 m +383.543 32.047 l +383.543 25.4728 388.871 20.1407 395.445 20.1407 c +402.019 20.1407 407.351 25.4728 407.351 32.047 c +407.351 38.6212 402.019 43.9493 395.445 43.9493 c +388.871 43.9493 383.543 38.6212 383.543 32.047 c +383.543 32.047 l +C +S 0.5 0.5 1 r f R + +N +447.828 32.047 m +447.828 32.047 l +447.828 24.8165 453.691 18.9493 460.922 18.9493 c +468.152 18.9493 474.016 24.8165 474.016 32.047 c +474.016 39.2775 468.152 45.1407 460.922 45.1407 c +453.691 45.1407 447.828 39.2775 447.828 32.047 c +447.828 32.047 l +C +S 0 0 0 r f R + +N +449.016 32.047 m +449.016 32.047 l +449.016 25.4728 454.348 20.1407 460.922 20.1407 c +467.496 20.1407 472.824 25.4728 472.824 32.047 c +472.824 38.6212 467.496 43.9493 460.922 43.9493 c +454.348 43.9493 449.016 38.6212 449.016 32.047 c +449.016 32.047 l +C +S 0.5 0.5 1 r f R + +N +526.394 32.047 m +526.394 32.047 l +526.394 24.8165 532.262 18.9493 539.492 18.9493 c +546.723 18.9493 552.586 24.8165 552.586 32.047 c +552.586 39.2775 546.723 45.1407 539.492 45.1407 c +532.262 45.1407 526.394 39.2775 526.394 32.047 c +526.394 32.047 l +C +S 0 0 0 r f R + +N +527.586 32.047 m +527.586 32.047 l +527.586 25.4728 532.918 20.1407 539.492 20.1407 c +546.066 20.1407 551.394 25.4728 551.394 32.047 c +551.394 38.6212 546.066 43.9493 539.492 43.9493 c +532.918 43.9493 527.586 38.6212 527.586 32.047 c +527.586 32.047 l +C +S 0.5 0.5 1 r f R + +N +591.871 32.047 m +591.871 32.047 l +591.871 24.8165 597.734 18.9493 604.965 18.9493 c +612.195 18.9493 618.062 24.8165 618.062 32.047 c +618.062 39.2775 612.195 45.1407 604.965 45.1407 c +597.734 45.1407 591.871 39.2775 591.871 32.047 c +591.871 32.047 l +C +S 0 0 0 r f R + +N +593.062 32.047 m +593.062 32.047 l +593.062 25.4728 598.39 20.1407 604.965 20.1407 c +611.539 20.1407 616.871 25.4728 616.871 32.047 c +616.871 38.6212 611.539 43.9493 604.965 43.9493 c +598.39 43.9493 593.062 38.6212 593.062 32.047 c +593.062 32.047 l +C +S 0.5 0.5 1 r f R + +N +670.441 32.047 m +670.441 32.047 l +670.441 24.8165 676.305 18.9493 683.535 18.9493 c +690.766 18.9493 696.633 24.8165 696.633 32.047 c +696.633 39.2775 690.766 45.1407 683.535 45.1407 c +676.305 45.1407 670.441 39.2775 670.441 32.047 c +670.441 32.047 l +C +S 0 0 0 r f R + +N +671.633 32.047 m +671.633 32.047 l +671.633 25.4728 676.961 20.1407 683.535 20.1407 c +690.109 20.1407 695.441 25.4728 695.441 32.047 c +695.441 38.6212 690.109 43.9493 683.535 43.9493 c +676.961 43.9493 671.633 38.6212 671.633 32.047 c +671.633 32.047 l +C +S 0 0 1 r f R + +N +735.918 32.047 m +735.918 32.047 l +735.918 24.8165 741.781 18.9493 749.012 18.9493 c +756.242 18.9493 762.106 24.8165 762.106 32.047 c +762.106 39.2775 756.242 45.1407 749.012 45.1407 c +741.781 45.1407 735.918 39.2775 735.918 32.047 c +735.918 32.047 l +C +S 0 0 0 r f R + +N +737.105 32.047 m +737.105 32.047 l +737.105 25.4728 742.437 20.1407 749.012 20.1407 c +755.586 20.1407 760.914 25.4728 760.914 32.047 c +760.914 38.6212 755.586 43.9493 749.012 43.9493 c +742.437 43.9493 737.105 38.6212 737.105 32.047 c +737.105 32.047 l +C +S 0 0 1 r f R + +N +801.391 32.047 m +801.391 32.047 l +801.391 24.8165 807.254 18.9493 814.484 18.9493 c +821.715 18.9493 827.578 24.8165 827.578 32.047 c +827.578 39.2775 821.715 45.1407 814.484 45.1407 c +807.254 45.1407 801.391 39.2775 801.391 32.047 c +801.391 32.047 l +C +S 0 0 0 r f R + +N +802.582 32.047 m +802.582 32.047 l +802.582 25.4728 807.91 20.1407 814.484 20.1407 c +821.059 20.1407 826.387 25.4728 826.387 32.047 c +826.387 38.6212 821.059 43.9493 814.484 43.9493 c +807.91 43.9493 802.582 38.6212 802.582 32.047 c +802.582 32.047 l +C +S 0.5 0.5 1 r f R + +%%EOF diff --git a/lemon/doc/images/bipartite_partitions.eps b/lemon/doc/images/bipartite_partitions.eps new file mode 100644 index 0000000..5ff348d --- /dev/null +++ b/lemon/doc/images/bipartite_partitions.eps @@ -0,0 +1,114 @@ +%!PS-Adobe-2.0 EPSF-2.0 +%%Creator: LEMON, graphToEps() +%%CreationDate: Tue Nov 15 16:51:43 2005 +%%BoundingBox: 0 0 842 596 +%%EndComments +/lb { setlinewidth setrgbcolor newpath moveto + 4 2 roll 1 index 1 index curveto stroke } bind def +/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def +/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def +/sq { newpath 2 index 1 index add 2 index 2 index add moveto + 2 index 1 index sub 2 index 2 index add lineto + 2 index 1 index sub 2 index 2 index sub lineto + 2 index 1 index add 2 index 2 index sub lineto + closepath pop pop pop} bind def +/di { newpath 2 index 1 index add 2 index moveto + 2 index 2 index 2 index add lineto + 2 index 1 index sub 2 index lineto + 2 index 2 index 2 index sub lineto + closepath pop pop pop} bind def +/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill + setrgbcolor 1.1 div c fill + } bind def +/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill + setrgbcolor 1.1 div sq fill + } bind def +/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill + setrgbcolor 1.1 div di fill + } bind def +/arrl 1 def +/arrw 0.3 def +/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def +/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def + /w exch def /len exch def + newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto + len w sub arrl sub dx dy lrl + arrw dy dx neg lrl + dx arrl w add mul dy w 2 div arrw add mul sub + dy arrl w add mul dx w 2 div arrw add mul add rlineto + dx arrl w add mul neg dy w 2 div arrw add mul sub + dy arrl w add mul neg dx w 2 div arrw add mul add rlineto + arrw dy dx neg lrl + len w sub arrl sub neg dx dy lrl + closepath fill } bind def +/cshow { 2 index 2 index moveto dup stringwidth pop + neg 2 div fosi .35 mul neg rmoveto show pop pop} def + +gsave +90 rotate +0 -842 translate +71.6378 15 translate +0.389093 dup scale +90 rotate +1197.47 -613.138 translate +%Edges: +gsave +513.857 -446.322 296.569 -487.43 79.2808 -528.539 0 0 0 2 lb +513.857 -446.322 575.52 -315.655 637.183 -184.989 0 0 0 2 lb +393.468 566.711 494.771 434.577 596.074 302.442 0 0 0 2 lb +393.468 566.711 155.625 579.925 -82.2171 593.138 0 0 0 2 lb +393.468 566.711 251.056 450.726 108.644 334.741 0 0 0 2 lb +869.153 52.8539 732.613 177.648 596.074 302.442 0 0 0 2 lb +869.153 52.8539 753.168 -66.0676 637.183 -184.989 0 0 0 2 lb +-82.2171 593.138 -91.0261 346.487 -99.8351 99.8351 0 0 0 2 lb +-663.61 546.157 -753.168 394.936 -842.726 243.715 0 0 0 2 lb +-663.61 546.157 -574.052 437.513 -484.494 328.869 0 0 0 2 lb +-1077.63 161.498 -960.178 202.606 -842.726 243.715 0 0 0 2 lb +-1077.63 161.498 -968.987 66.0674 -860.344 -29.3633 0 0 0 2 lb +-1177.47 -234.906 -1029.18 -381.722 -880.898 -528.539 0 0 0 2 lb +-1177.47 -234.906 -1018.91 -132.135 -860.344 -29.3633 0 0 0 2 lb +-880.898 -528.539 -744.359 -387.595 -607.82 -246.651 0 0 0 2 lb +-499.175 -499.175 -355.295 -475.685 -211.415 -452.194 0 0 0 2 lb +-499.175 -499.175 -553.498 -372.913 -607.82 -246.651 0 0 0 2 lb +-499.175 -499.175 -386.587 -315.087 -274 -131 0 0 0 2 lb +79.2808 -528.539 -66.0671 -490.366 -211.415 -452.194 0 0 0 2 lb +637.183 -184.989 421.363 -253.993 205.543 -322.996 0 0 0 2 lb +205.543 -322.996 162.966 -226.097 120.389 -129.198 0 0 0 2 lb +399.34 88.0898 259.865 -20.5541 120.389 -129.198 0 0 0 2 lb +399.34 88.0898 253.992 211.415 108.644 334.741 0 0 0 2 lb +-842.726 243.715 -471.281 171.775 -99.8351 99.8351 0 0 0 2 lb +-842.726 243.715 -558.363 56.3575 -274 -131 0 0 0 2 lb +-860.344 -29.3633 -734.082 -138.007 -607.82 -246.651 0 0 0 2 lb +-211.415 -452.194 -45.513 -290.696 120.389 -129.198 0 0 0 2 lb +-99.8351 99.8351 4.40445 217.288 108.644 334.741 0 0 0 2 lb +-99.8351 99.8351 -292.165 214.352 -484.494 328.869 0 0 0 2 lb +120.389 -129.198 -76.8055 -130.099 -274 -131 0 0 0 2 lb +grestore +%Nodes: +gsave +-274 -131 20 1 0 0 nc +-607.82 -246.651 20 1 0 0 nc +-484.494 328.869 20 0 0 1 nc +108.644 334.741 20 0 0 1 nc +120.389 -129.198 20 0 0 1 nc +-99.8351 99.8351 20 1 0 0 nc +-211.415 -452.194 20 1 0 0 nc +-860.344 -29.3633 20 0 0 1 nc +-842.726 243.715 20 0 0 1 nc +399.34 88.0898 20 1 0 0 nc +205.543 -322.996 20 1 0 0 nc +637.183 -184.989 20 0 0 1 nc +79.2808 -528.539 20 0 0 1 nc +-499.175 -499.175 20 0 0 1 nc +-880.898 -528.539 20 0 0 1 nc +-1177.47 -234.906 20 1 0 0 nc +-1077.63 161.498 20 1 0 0 nc +-663.61 546.157 20 1 0 0 nc +-82.2171 593.138 20 0 0 1 nc +596.074 302.442 20 0 0 1 nc +869.153 52.8539 20 1 0 0 nc +393.468 566.711 20 1 0 0 nc +513.857 -446.322 20 1 0 0 nc +grestore +grestore +showpage diff --git a/lemon/doc/images/connected_components.eps b/lemon/doc/images/connected_components.eps new file mode 100644 index 0000000..6690733 --- /dev/null +++ b/lemon/doc/images/connected_components.eps @@ -0,0 +1,159 @@ +%!PS-Adobe-2.0 EPSF-2.0 +%%Creator: LEMON, graphToEps() +%%CreationDate: Fri Nov 4 13:47:12 2005 +%%BoundingBox: 0 0 842 596 +%%EndComments +/lb { setlinewidth setrgbcolor newpath moveto + 4 2 roll 1 index 1 index curveto stroke } bind def +/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def +/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def +/sq { newpath 2 index 1 index add 2 index 2 index add moveto + 2 index 1 index sub 2 index 2 index add lineto + 2 index 1 index sub 2 index 2 index sub lineto + 2 index 1 index add 2 index 2 index sub lineto + closepath pop pop pop} bind def +/di { newpath 2 index 1 index add 2 index moveto + 2 index 2 index 2 index add lineto + 2 index 1 index sub 2 index lineto + 2 index 2 index 2 index sub lineto + closepath pop pop pop} bind def +/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill + setrgbcolor 1.1 div c fill + } bind def +/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill + setrgbcolor 1.1 div sq fill + } bind def +/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill + setrgbcolor 1.1 div di fill + } bind def +/arrl 1 def +/arrw 0.3 def +/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def +/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def + /w exch def /len exch def + newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto + len w sub arrl sub dx dy lrl + arrw dy dx neg lrl + dx arrl w add mul dy w 2 div arrw add mul sub + dy arrl w add mul dx w 2 div arrw add mul add rlineto + dx arrl w add mul neg dy w 2 div arrw add mul sub + dy arrl w add mul neg dx w 2 div arrw add mul add rlineto + arrw dy dx neg lrl + len w sub arrl sub neg dx dy lrl + closepath fill } bind def +/cshow { 2 index 2 index moveto dup stringwidth pop + neg 2 div fosi .35 mul neg rmoveto show pop pop} def + +gsave +90 rotate +0 -842 translate +71.0944 15 translate +0.434694 dup scale +90 rotate +860.856 -588.349 translate +%Edges: +gsave +574.035 177.301 622.149 225.748 670.264 274.195 0 0 0 2 lb +694.579 115.483 682.421 194.839 670.264 274.195 0 0 0 2 lb +280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 0 2 lb +280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 0 2 lb +212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 0 2 lb +286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 0 2 lb +286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 0 2 lb +438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 0 2 lb +438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 0 2 lb +397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 0 2 lb +366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 0 2 lb +271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 0 2 lb +271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 0 2 lb +277.311 -252.33 241.766 -229.149 206.221 -205.967 0 0 0 2 lb +-840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0 0 2 lb +-579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0 2 lb +-579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0 2 lb +-767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0 2 lb +906.312 201.403 946.592 42.798 986.873 -115.807 0 0 0 2 lb +906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 0 2 lb +986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 0 2 lb +-470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0 0 0 2 lb +422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 0 2 lb +422.945 521.129 376.371 417.911 329.797 314.692 0 0 0 2 lb +422.945 521.129 474.554 276.928 526.164 32.7279 0 0 0 2 lb +-5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 0 2 lb +329.797 314.692 130.912 317.209 -67.9734 319.727 0 0 0 2 lb +-67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 0 2 lb +762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 0 2 lb +762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 0 2 lb +526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 0 2 lb +730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 0 2 lb +415.393 -289.516 173.71 -318.468 -67.9734 -347.42 0 0 0 2 lb +-67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 0 2 lb +-67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 0 2 lb +-309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 0 2 lb +-323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 0 2 lb +-26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 0 2 lb +-26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 0 2 lb +-26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 0 2 lb +-26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 0 2 lb +116.407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 0 2 lb +-262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 0 2 lb +-262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 0 2 lb +-13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 0 2 lb +-180.397 245.045 -142.256 345.099 -132.697 451.748 0 0 0 2 lb +-180.397 245.045 -170.838 351.694 -132.697 451.748 0 0 0 2 lb +-416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 0 2 lb +-416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 0 2 lb +-132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 0 2 lb +670.264 274.195 629.188 409.347 588.113 544.499 0 0 0 2 lb +670.264 274.195 797.466 341.771 924.667 409.347 0 0 0 2 lb +588.113 544.499 756.39 476.923 924.667 409.347 0 0 0 2 lb +-689.204 -237.261 -614.799 -102.648 -567.302 43.6423 0 0 0 2 lb +-689.204 -237.261 -641.707 -90.9706 -567.302 43.6423 0 0 0 2 lb +grestore +%Nodes: +gsave +-567.302 43.6423 20 0 0 0 nc +-689.204 -237.261 20 0 0 0 nc +924.667 409.347 20 1 0 0 nc +588.113 544.499 20 1 0 0 nc +670.264 274.195 20 1 0 0 nc +-371.2 568.349 20 0 1 0 nc +-132.697 451.748 20 0 1 0 nc +-416.25 345.746 20 0 1 0 nc +-180.397 245.045 20 0 1 0 nc +-13.4452 133.743 20 0 1 0 nc +-262.548 107.243 20 0 1 0 nc +201.208 38.3422 20 0 1 0 nc +116.407 -173.66 20 0 1 0 nc +-26.6953 -19.9585 20 0 1 0 nc +-539.894 -262.64 20 0 0 1 nc +-323.543 -433.964 20 0 0 1 nc +-309.657 -57.9033 20 0 0 1 nc +-67.9734 -347.42 20 0 0 1 nc +415.393 -289.516 20 0 0 1 nc +730.084 -307.139 20 0 0 1 nc +526.164 32.7279 20 0 0 1 nc +762.812 -17.6227 20 0 0 1 nc +-67.9734 319.727 20 0 0 1 nc +329.797 314.692 20 0 0 1 nc +-5.03507 561.41 20 0 0 1 nc +422.945 521.129 20 0 0 1 nc +-470.779 158.605 20 0 0 1 nc +986.873 -115.807 20 0 0 1 nc +906.312 201.403 20 0 0 1 nc +-767.847 113.289 20 0 0 1 nc +-579.033 445.603 20 0 0 1 nc +-840.856 -246.718 20 0 0 1 nc +206.221 -205.967 20 1 1 0 nc +277.311 -252.33 20 1 1 0 nc +271.13 -175.058 20 1 1 0 nc +366.947 -110.15 20 1 1 0 nc +397.855 -196.694 20 1 1 0 nc +438.037 -88.514 20 1 1 0 nc +286.584 -48.3327 20 1 1 0 nc +212.403 -23.6057 20 1 1 0 nc +280.402 10.3938 20 1 1 0 nc +694.579 115.483 20 1 0 0 nc +574.035 177.301 20 1 0 0 nc +grestore +grestore +showpage diff --git a/lemon/doc/images/edge_biconnected_components.eps b/lemon/doc/images/edge_biconnected_components.eps new file mode 100644 index 0000000..a42d352 --- /dev/null +++ b/lemon/doc/images/edge_biconnected_components.eps @@ -0,0 +1,159 @@ +%!PS-Adobe-2.0 EPSF-2.0 +%%Creator: LEMON, graphToEps() +%%CreationDate: Fri Nov 4 13:47:12 2005 +%%BoundingBox: 0 0 842 596 +%%EndComments +/lb { setlinewidth setrgbcolor newpath moveto + 4 2 roll 1 index 1 index curveto stroke } bind def +/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def +/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def +/sq { newpath 2 index 1 index add 2 index 2 index add moveto + 2 index 1 index sub 2 index 2 index add lineto + 2 index 1 index sub 2 index 2 index sub lineto + 2 index 1 index add 2 index 2 index sub lineto + closepath pop pop pop} bind def +/di { newpath 2 index 1 index add 2 index moveto + 2 index 2 index 2 index add lineto + 2 index 1 index sub 2 index lineto + 2 index 2 index 2 index sub lineto + closepath pop pop pop} bind def +/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill + setrgbcolor 1.1 div c fill + } bind def +/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill + setrgbcolor 1.1 div sq fill + } bind def +/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill + setrgbcolor 1.1 div di fill + } bind def +/arrl 1 def +/arrw 0.3 def +/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def +/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def + /w exch def /len exch def + newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto + len w sub arrl sub dx dy lrl + arrw dy dx neg lrl + dx arrl w add mul dy w 2 div arrw add mul sub + dy arrl w add mul dx w 2 div arrw add mul add rlineto + dx arrl w add mul neg dy w 2 div arrw add mul sub + dy arrl w add mul neg dx w 2 div arrw add mul add rlineto + arrw dy dx neg lrl + len w sub arrl sub neg dx dy lrl + closepath fill } bind def +/cshow { 2 index 2 index moveto dup stringwidth pop + neg 2 div fosi .35 mul neg rmoveto show pop pop} def + +gsave +90 rotate +0 -842 translate +71.0944 15 translate +0.434694 dup scale +90 rotate +860.856 -588.349 translate +%Edges: +gsave +574.035 177.301 622.149 225.748 670.264 274.195 1 0 0 2 lb +694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 2 lb +280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 1 2 lb +280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 1 2 lb +212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 1 2 lb +286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 1 2 lb +286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 1 2 lb +438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 1 2 lb +438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 1 2 lb +397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 1 2 lb +366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 1 2 lb +271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 1 2 lb +271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 1 2 lb +277.311 -252.33 241.766 -229.149 206.221 -205.967 0 0 1 2 lb +-840.856 -246.718 -804.351 -66.7145 -767.847 113.289 1 0 0 2 lb +-579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 1 2 lb +-579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 1 2 lb +-767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 1 2 lb +906.312 201.403 946.592 42.798 986.873 -115.807 0 0 1 2 lb +906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 1 2 lb +986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 1 2 lb +-470.779 158.605 -390.218 50.3508 -309.657 -57.9033 1 0 0 2 lb +422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 1 2 lb +422.945 521.129 376.371 417.911 329.797 314.692 0 0 1 2 lb +422.945 521.129 474.554 276.928 526.164 32.7279 0 0 1 2 lb +-5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 1 2 lb +329.797 314.692 130.912 317.209 -67.9734 319.727 0 0 1 2 lb +-67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 1 2 lb +762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 1 2 lb +762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 1 2 lb +526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 1 2 lb +730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 1 2 lb +415.393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0 0 2 lb +-67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 1 2 lb +-67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 1 2 lb +-309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 1 2 lb +-323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 1 2 lb +-26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 1 2 lb +-26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 1 2 lb +-26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 1 2 lb +-26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 1 2 lb +116.407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 1 2 lb +-262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 1 2 lb +-262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 1 2 lb +-13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 1 2 lb +-180.397 245.045 -142.256 345.099 -132.697 451.748 0 0 1 2 lb +-180.397 245.045 -170.838 351.694 -132.697 451.748 0 0 1 2 lb +-416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 1 2 lb +-416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 1 2 lb +-132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 1 2 lb +670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 2 lb +670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 2 lb +588.113 544.499 756.39 476.923 924.667 409.347 0 0 1 2 lb +-689.204 -237.261 -614.799 -102.648 -567.302 43.6423 0 0 1 2 lb +-689.204 -237.261 -641.707 -90.9706 -567.302 43.6423 0 0 1 2 lb +grestore +%Nodes: +gsave +-567.302 43.6423 20 0 0 0 nc +-689.204 -237.261 20 0 0 0 nc +924.667 409.347 20 0 0 1 nc +588.113 544.499 20 0 0 1 nc +670.264 274.195 20 0 0 1 nc +-371.2 568.349 20 1 1 0 nc +-132.697 451.748 20 1 1 0 nc +-416.25 345.746 20 1 1 0 nc +-180.397 245.045 20 1 1 0 nc +-13.4452 133.743 20 1 1 0 nc +-262.548 107.243 20 1 1 0 nc +201.208 38.3422 20 1 1 0 nc +116.407 -173.66 20 1 1 0 nc +-26.6953 -19.9585 20 1 1 0 nc +-539.894 -262.64 20 0 0.5 0 nc +-323.543 -433.964 20 0 0.5 0 nc +-309.657 -57.9033 20 0 0.5 0 nc +-67.9734 -347.42 20 0 0.5 0 nc +415.393 -289.516 20 0.5 0 0 nc +730.084 -307.139 20 0.5 0 0 nc +526.164 32.7279 20 0.5 0 0 nc +762.812 -17.6227 20 0.5 0 0 nc +-67.9734 319.727 20 0.5 0 0 nc +329.797 314.692 20 0.5 0 0 nc +-5.03507 561.41 20 0.5 0 0 nc +422.945 521.129 20 0.5 0 0 nc +-470.779 158.605 20 0 1 1 nc +986.873 -115.807 20 0.5 0 0 nc +906.312 201.403 20 0.5 0 0 nc +-767.847 113.289 20 0 1 1 nc +-579.033 445.603 20 0 1 1 nc +-840.856 -246.718 20 1 0 1 nc +206.221 -205.967 20 0 0 0.5 nc +277.311 -252.33 20 0 0 0.5 nc +271.13 -175.058 20 0 0 0.5 nc +366.947 -110.15 20 0 0 0.5 nc +397.855 -196.694 20 0 0 0.5 nc +438.037 -88.514 20 0 0 0.5 nc +286.584 -48.3327 20 0 0 0.5 nc +212.403 -23.6057 20 0 0 0.5 nc +280.402 10.3938 20 0 0 0.5 nc +694.579 115.483 20 1 0 0 nc +574.035 177.301 20 0 1 0 nc +grestore +grestore +showpage diff --git a/lemon/doc/images/grid_graph.eps b/lemon/doc/images/grid_graph.eps new file mode 100644 index 0000000..6dbf477 --- /dev/null +++ b/lemon/doc/images/grid_graph.eps @@ -0,0 +1,286 @@ +%!PS-Adobe-2.0 EPSF-2.0 +%%Title: Grid undirected graph +%%Copyright: (C) 2006 LEMON Project +%%Creator: LEMON, graphToEps() +%%CreationDate: Fri Sep 29 11:55:56 2006 +%%BoundingBox: 0 0 985 1144 +%%EndComments +/lb { setlinewidth setrgbcolor newpath moveto + 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 +/arrl 1 def +/arrw 0.3 def +/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def +/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def + /w exch def /len exch def + newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto + len w sub arrl sub dx dy lrl + arrw dy dx neg lrl + dx arrl w add mul dy w 2 div arrw add mul sub + dy arrl w add mul dx w 2 div arrw add mul add rlineto + dx arrl w add mul neg dy w 2 div arrw add mul sub + dy arrl w add mul neg dx w 2 div arrw add mul add rlineto + arrw dy dx neg lrl + len w sub arrl sub neg dx dy lrl + closepath fill } bind def +/cshow { 2 index 2 index moveto dup stringwidth pop + neg 2 div fosi .35 mul neg rmoveto show pop pop} def + +gsave +2 2 scale +50 40 translate +5.5000 5.5000 scale +% 1.14018 1.14018 translate +%Edges: +gsave +70 80 70 90 0 0 0 0.5000 l +70 70 70 80 0 0 0 0.5000 l +70 60 70 70 0 0 0 0.5000 l +70 50 70 60 0 0 0 0.5000 l +70 40 70 50 0 0 0 0.5000 l +70 30 70 40 0 0 0 0.5000 l +70 20 70 30 0 0 0 0.5000 l +70 10 70 20 0 0 0 0.5000 l +70 0 70 10 0 0 0 0.5000 l +60 80 60 90 0 0 0 0.5000 l +60 70 60 80 0 0 0 0.5000 l +60 60 60 70 0 0 0 0.5000 l +60 50 60 60 0 0 0 0.5000 l +60 40 60 50 0 0 0 0.5000 l +60 30 60 40 0 0 0 0.5000 l +60 20 60 30 0 0 0 0.5000 l +60 10 60 20 0 0 0 0.5000 l +60 0 60 10 0 0 0 0.5000 l +50 80 50 90 0 0 0 0.5000 l +50 70 50 80 0 0 0 0.5000 l +50 60 50 70 0 0 0 0.5000 l +50 50 50 60 0 0 0 0.5000 l +50 40 50 50 0 0 0 0.5000 l +50 30 50 40 0 0 0 0.5000 l +50 20 50 30 0 0 0 0.5000 l +50 10 50 20 0 0 0 0.5000 l +50 0 50 10 0 0 0 0.5000 l +40 80 40 90 0 0 0 0.5000 l +40 70 40 80 0 0 0 0.5000 l +40 60 40 70 0 0 0 0.5000 l +40 50 40 60 0 0 0 0.5000 l +40 40 40 50 0 0 0 0.5000 l +40 30 40 40 0 0 0 0.5000 l +40 20 40 30 0 0 0 0.5000 l +40 10 40 20 0 0 0 0.5000 l +40 0 40 10 0 0 0 0.5000 l +30 80 30 90 0 0 0 0.5000 l +30 70 30 80 0 0 0 0.5000 l +30 60 30 70 0 0 0 0.5000 l +30 50 30 60 0 0 0 0.5000 l +30 40 30 50 0 0 0 0.5000 l +30 30 30 40 0 0 0 0.5000 l +30 20 30 30 0 0 0 0.5000 l +30 10 30 20 0 0 0 0.5000 l +30 0 30 10 0 0 0 0.5000 l +20 80 20 90 0 0 0 0.5000 l +20 70 20 80 0 0 0 0.5000 l +20 60 20 70 0 0 0 0.5000 l +20 50 20 60 0 0 0 0.5000 l +20 40 20 50 0 0 0 0.5000 l +20 30 20 40 0 0 0 0.5000 l +20 20 20 30 0 0 0 0.5000 l +20 10 20 20 0 0 0 0.5000 l +20 0 20 10 0 0 0 0.5000 l +10 80 10 90 0 0 0 0.5000 l +10 70 10 80 0 0 0 0.5000 l +10 60 10 70 0 0 0 0.5000 l +10 50 10 60 0 0 0 0.5000 l +10 40 10 50 0 0 0 0.5000 l +10 30 10 40 0 0 0 0.5000 l +10 20 10 30 0 0 0 0.5000 l +10 10 10 20 0 0 0 0.5000 l +10 0 10 10 0 0 0 0.5000 l +0 80 0 90 0 0 0 0.5000 l +0 70 0 80 0 0 0 0.5000 l +0 60 0 70 0 0 0 0.5000 l +0 50 0 60 0 0 0 0.5000 l +0 40 0 50 0 0 0 0.5000 l +0 30 0 40 0 0 0 0.5000 l +0 20 0 30 0 0 0 0.5000 l +0 10 0 20 0 0 0 0.5000 l +0 0 0 10 0 0 0 0.5000 l +60 90 70 90 0 0 0 0.5000 l +60 80 70 80 0 0 0 0.5000 l +60 70 70 70 0 0 0 0.5000 l +60 60 70 60 0 0 0 0.5000 l +60 50 70 50 0 0 0 0.5000 l +60 40 70 40 0 0 0 0.5000 l +60 30 70 30 0 0 0 0.5000 l +60 20 70 20 0 0 0 0.5000 l +60 10 70 10 0 0 0 0.5000 l +60 0 70 0 0 0 0 0.5000 l +50 90 60 90 0 0 0 0.5000 l +50 80 60 80 0 0 0 0.5000 l +50 70 60 70 0 0 0 0.5000 l +50 60 60 60 0 0 0 0.5000 l +50 50 60 50 0 0 0 0.5000 l +50 40 60 40 0 0 0 0.5000 l +50 30 60 30 0 0 0 0.5000 l +50 20 60 20 0 0 0 0.5000 l +50 10 60 10 0 0 0 0.5000 l +50 0 60 0 0 0 0 0.5000 l +40 90 50 90 0 0 0 0.5000 l +40 80 50 80 0 0 0 0.5000 l +40 70 50 70 0 0 0 0.5000 l +40 60 50 60 0 0 0 0.5000 l +40 50 50 50 0 0 0 0.5000 l +40 40 50 40 0 0 0 0.5000 l +40 30 50 30 0 0 0 0.5000 l +40 20 50 20 0 0 0 0.5000 l +40 10 50 10 0 0 0 0.5000 l +40 0 50 0 0 0 0 0.5000 l +30 90 40 90 0 0 0 0.5000 l +30 80 40 80 0 0 0 0.5000 l +30 70 40 70 0 0 0 0.5000 l +30 60 40 60 0 0 0 0.5000 l +30 50 40 50 0 0 0 0.5000 l +30 40 40 40 0 0 0 0.5000 l +30 30 40 30 0 0 0 0.5000 l +30 20 40 20 0 0 0 0.5000 l +30 10 40 10 0 0 0 0.5000 l +30 0 40 0 0 0 0 0.5000 l +20 90 30 90 0 0 0 0.5000 l +20 80 30 80 0 0 0 0.5000 l +20 70 30 70 0 0 0 0.5000 l +20 60 30 60 0 0 0 0.5000 l +20 50 30 50 0 0 0 0.5000 l +20 40 30 40 0 0 0 0.5000 l +20 30 30 30 0 0 0 0.5000 l +20 20 30 20 0 0 0 0.5000 l +20 10 30 10 0 0 0 0.5000 l +20 0 30 0 0 0 0 0.5000 l +10 90 20 90 0 0 0 0.5000 l +10 80 20 80 0 0 0 0.5000 l +10 70 20 70 0 0 0 0.5000 l +10 60 20 60 0 0 0 0.5000 l +10 50 20 50 0 0 0 0.5000 l +10 40 20 40 0 0 0 0.5000 l +10 30 20 30 0 0 0 0.5000 l +10 20 20 20 0 0 0 0.5000 l +10 10 20 10 0 0 0 0.5000 l +10 0 20 0 0 0 0 0.5000 l +0 90 10 90 0 0 0 0.5000 l +0 80 10 80 0 0 0 0.5000 l +0 70 10 70 0 0 0 0.5000 l +0 60 10 60 0 0 0 0.5000 l +0 50 10 50 0 0 0 0.5000 l +0 40 10 40 0 0 0 0.5000 l +0 30 10 30 0 0 0 0.5000 l +0 20 10 20 0 0 0 0.5000 l +0 10 10 10 0 0 0 0.5000 l +0 0 10 0 0 0 0 0.5000 l +grestore +%Nodes: +gsave +70 90 1.4000 0 0 0 nc +70 80 1.4000 1 1 1 nc +70 70 1.4000 1 1 1 nc +70 60 1.4000 1 1 1 nc +70 50 1.4000 1 1 1 nc +70 40 1.4000 1 1 1 nc +70 30 1.4000 1 1 1 nc +70 20 1.4000 1 1 1 nc +70 10 1.4000 1 1 1 nc +70 0 1.4000 0 0 0 nc +60 90 1.4000 1 1 1 nc +60 80 1.4000 1 1 1 nc +60 70 1.4000 1 1 1 nc +60 60 1.4000 1 1 1 nc +60 50 1.4000 1 1 1 nc +60 40 1.4000 1 1 1 nc +60 30 1.4000 1 1 1 nc +60 20 1.4000 1 1 1 nc +60 10 1.4000 1 1 1 nc +60 0 1.4000 1 1 1 nc +50 90 1.4000 1 1 1 nc +50 80 1.4000 1 1 1 nc +50 70 1.4000 1 1 1 nc +50 60 1.4000 1 1 1 nc +50 50 1.4000 1 1 1 nc +50 40 1.4000 1 1 1 nc +50 30 1.4000 1 1 1 nc +50 20 1.4000 1 1 1 nc +50 10 1.4000 1 1 1 nc +50 0 1.4000 1 1 1 nc +40 90 1.4000 1 1 1 nc +40 80 1.4000 1 1 1 nc +40 70 1.4000 1 1 1 nc +40 60 1.4000 1 1 1 nc +40 50 1.4000 1 1 1 nc +40 40 1.4000 1 1 1 nc +40 30 1.4000 1 1 1 nc +40 20 1.4000 1 1 1 nc +40 10 1.4000 1 1 1 nc +40 0 1.4000 1 1 1 nc +30 90 1.4000 1 1 1 nc +30 80 1.4000 1 1 1 nc +30 70 1.4000 1 1 1 nc +30 60 1.4000 1 1 1 nc +30 50 1.4000 1 1 1 nc +30 40 1.4000 1 1 1 nc +30 30 1.4000 1 1 1 nc +30 20 1.4000 1 1 1 nc +30 10 1.4000 1 1 1 nc +30 0 1.4000 1 1 1 nc +20 90 1.4000 1 1 1 nc +20 80 1.4000 1 1 1 nc +20 70 1.4000 1 1 1 nc +20 60 1.4000 1 1 1 nc +20 50 1.4000 1 1 1 nc +20 40 1.4000 1 1 1 nc +20 30 1.4000 1 1 1 nc +20 20 1.4000 1 1 1 nc +20 10 1.4000 1 1 1 nc +20 0 1.4000 1 1 1 nc +10 90 1.4000 1 1 1 nc +10 80 1.4000 1 1 1 nc +10 70 1.4000 1 1 1 nc +10 60 1.4000 1 1 1 nc +10 50 1.4000 1 1 1 nc +10 40 1.4000 1 1 1 nc +10 30 1.4000 1 1 1 nc +10 20 1.4000 1 1 1 nc +10 10 1.4000 1 1 1 nc +10 0 1.4000 1 1 1 nc +0 90 1.4000 0 0 0 nc +0 80 1.4000 1 1 1 nc +0 70 1.4000 1 1 1 nc +0 60 1.4000 1 1 1 nc +0 50 1.4000 1 1 1 nc +0 40 1.4000 1 1 1 nc +0 30 1.4000 1 1 1 nc +0 20 1.4000 1 1 1 nc +0 10 1.4000 1 1 1 nc +0 0 1.4000 0 0 0 nc +grestore +gsave +/fosi 3.5 def +(Helvetica) findfont fosi scalefont setfont +0 0 0 setrgbcolor +0 95 ((0,height-1)) cshow +67 95 ((width-1,height-1)) cshow +0 -5 ((0,0)) cshow +70 -5 ((width-1,0)) cshow +grestore +grestore +showpage diff --git a/lemon/doc/images/matching.eps b/lemon/doc/images/matching.eps new file mode 100644 index 0000000..2f418bd --- /dev/null +++ b/lemon/doc/images/matching.eps @@ -0,0 +1,130 @@ +%!PS-Adobe-2.0 EPSF-2.0 +%%Creator: LEMON, graphToEps() +%%CreationDate: Sun Mar 14 09:08:34 2010 +%%BoundingBox: -353 -264 559 292 +%%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 +%Arcs: +gsave +140.321 266.249 -327.729 150.06 0 0 0 4.99223 l +82.1207 -238.726 -245.288 -110.743 0 0 0 4.99223 l +336.635 -229.036 533.603 13.109 0 0 0 4.99223 l +53.8598 -45.8071 -245.288 -110.743 0 0 0 4.99223 l +-75.5617 118.579 -327.729 150.06 0 0 0 4.99223 l +-327.729 150.06 -245.288 -110.743 1 0 0 11.9813 l +533.603 13.109 218.184 -84.2955 0 0 0 4.99223 l +39.87 175.035 141.163 67.2575 0 0 0 4.99223 l +53.8598 -45.8071 -75.5617 118.579 0 0 0 4.99223 l +-102.406 -141.267 82.1207 -238.726 0 0 0 4.99223 l +399.144 166.894 533.603 13.109 1 0 0 11.9813 l +39.87 175.035 140.321 266.249 1 0 0 11.9813 l +399.144 166.894 140.321 266.249 0 0 0 4.99223 l +399.144 166.894 141.163 67.2575 0 0 0 4.99223 l +53.8598 -45.8071 204.765 -173.77 0 0 0 4.99223 l +82.1207 -238.726 204.765 -173.77 0 0 0 4.99223 l +258.227 61.658 399.144 166.894 0 0 0 4.99223 l +53.8598 -45.8071 -102.406 -141.267 1 0 0 11.9813 l +175.073 -37.4477 141.163 67.2575 0 0 0 4.99223 l +258.227 61.658 380 0 0 0 0 4.99223 l +34.6739 40.8267 -75.5617 118.579 1 0 0 11.9813 l +380 0 533.603 13.109 0 0 0 4.99223 l +175.073 -37.4477 380 0 0 0 0 4.99223 l +218.184 -84.2955 204.765 -173.77 0 0 0 4.99223 l +53.8598 -45.8071 34.6739 40.8267 0 0 0 4.99223 l +167.905 -213.988 82.1207 -238.726 1 0 0 11.9813 l +336.635 -229.036 204.765 -173.77 1 0 0 11.9813 l +336.635 -229.036 167.905 -213.988 0 0 0 4.99223 l +329.08 -26.3098 218.184 -84.2955 0 0 0 4.99223 l +39.87 175.035 -75.5617 118.579 0 0 0 4.99223 l +53.8598 -45.8071 175.073 -37.4477 0 0 0 4.99223 l +34.6739 40.8267 141.163 67.2575 0 0 0 4.99223 l +258.227 61.658 141.163 67.2575 1 0 0 11.9813 l +175.073 -37.4477 218.184 -84.2955 1 0 0 11.9813 l +380 0 329.08 -26.3098 1 0 0 11.9813 l +grestore +%Nodes: +gsave +-245.288 -110.743 14.9767 1 1 1 nc +204.765 -173.77 14.9767 1 1 1 nc +-327.729 150.06 14.9767 1 1 1 nc +-75.5617 118.579 14.9767 1 1 1 nc +218.184 -84.2955 14.9767 1 1 1 nc +140.321 266.249 14.9767 1 1 1 nc +141.163 67.2575 14.9767 1 1 1 nc +82.1207 -238.726 14.9767 1 1 1 nc +329.08 -26.3098 14.9767 1 1 1 nc +-102.406 -141.267 14.9767 1 1 1 nc +533.603 13.109 14.9767 1 1 1 nc +167.905 -213.988 14.9767 1 1 1 nc +336.635 -229.036 14.9767 1 1 1 nc +380 0 14.9767 1 1 1 nc +399.144 166.894 14.9767 1 1 1 nc +34.6739 40.8267 14.9767 1 1 1 nc +39.87 175.035 14.9767 1 1 1 nc +175.073 -37.4477 14.9767 1 1 1 nc +53.8598 -45.8071 14.9767 1 1 1 nc +258.227 61.658 14.9767 1 1 1 nc +grestore +grestore +showpage diff --git a/lemon/doc/images/node_biconnected_components.eps b/lemon/doc/images/node_biconnected_components.eps new file mode 100644 index 0000000..a6839c0 --- /dev/null +++ b/lemon/doc/images/node_biconnected_components.eps @@ -0,0 +1,159 @@ +%!PS-Adobe-2.0 EPSF-2.0 +%%Creator: LEMON, graphToEps() +%%CreationDate: Fri Nov 4 13:47:12 2005 +%%BoundingBox: 0 0 842 596 +%%EndComments +/lb { setlinewidth setrgbcolor newpath moveto + 4 2 roll 1 index 1 index curveto stroke } bind def +/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def +/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def +/sq { newpath 2 index 1 index add 2 index 2 index add moveto + 2 index 1 index sub 2 index 2 index add lineto + 2 index 1 index sub 2 index 2 index sub lineto + 2 index 1 index add 2 index 2 index sub lineto + closepath pop pop pop} bind def +/di { newpath 2 index 1 index add 2 index moveto + 2 index 2 index 2 index add lineto + 2 index 1 index sub 2 index lineto + 2 index 2 index 2 index sub lineto + closepath pop pop pop} bind def +/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill + setrgbcolor 1.1 div c fill + } bind def +/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill + setrgbcolor 1.1 div sq fill + } bind def +/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill + setrgbcolor 1.1 div di fill + } bind def +/arrl 1 def +/arrw 0.3 def +/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def +/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def + /w exch def /len exch def + newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto + len w sub arrl sub dx dy lrl + arrw dy dx neg lrl + dx arrl w add mul dy w 2 div arrw add mul sub + dy arrl w add mul dx w 2 div arrw add mul add rlineto + dx arrl w add mul neg dy w 2 div arrw add mul sub + dy arrl w add mul neg dx w 2 div arrw add mul add rlineto + arrw dy dx neg lrl + len w sub arrl sub neg dx dy lrl + closepath fill } bind def +/cshow { 2 index 2 index moveto dup stringwidth pop + neg 2 div fosi .35 mul neg rmoveto show pop pop} def + +gsave +90 rotate +0 -842 translate +71.0944 15 translate +0.434694 dup scale +90 rotate +860.856 -588.349 translate +%Edges: +gsave +574.035 177.301 622.149 225.748 670.264 274.195 0 1 0 5 lb +694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 5 lb +280.402 10.3938 246.402 -6.60595 212.403 -23.6057 1 1 0.5 5 lb +280.402 10.3938 283.493 -18.9695 286.584 -48.3327 1 1 0.5 5 lb +212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 1 1 0.5 5 lb +286.584 -48.3327 326.765 -79.2414 366.947 -110.15 1 0.5 1 5 lb +286.584 -48.3327 278.857 -111.695 271.13 -175.058 1 0.5 1 5 lb +438.037 -88.514 417.946 -142.604 397.855 -196.694 0.5 0.5 1 5 lb +438.037 -88.514 402.492 -99.332 366.947 -110.15 0.5 0.5 1 5 lb +397.855 -196.694 382.401 -153.422 366.947 -110.15 0.5 0.5 1 5 lb +366.947 -110.15 319.038 -142.604 271.13 -175.058 1 0.5 1 5 lb +271.13 -175.058 274.221 -213.694 277.311 -252.33 0.5 1 1 5 lb +271.13 -175.058 238.675 -190.512 206.221 -205.967 0.5 1 1 5 lb +277.311 -252.33 241.766 -229.149 206.221 -205.967 0.5 1 1 5 lb +-840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0.5 0 5 lb +-579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0.5 5 lb +-579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0.5 5 lb +-767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0.5 5 lb +906.312 201.403 946.592 42.798 986.873 -115.807 0 0.5 0.5 5 lb +906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0.5 0.5 5 lb +986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0.5 0.5 5 lb +-470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0.5 0.5 0 5 lb +422.945 521.129 208.955 541.269 -5.03507 561.41 0.5 0 0.5 5 lb +422.945 521.129 376.371 417.911 329.797 314.692 0.5 0 0.5 5 lb +422.945 521.129 474.554 276.928 526.164 32.7279 0.5 0 0.5 5 lb +-5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0.5 0 0.5 5 lb +329.797 314.692 130.912 317.209 -67.9734 319.727 0.5 0 0.5 5 lb +-67.9734 319.727 229.095 176.227 526.164 32.7279 0.5 0 0.5 5 lb +762.812 -17.6227 644.488 7.5526 526.164 32.7279 0.5 0.5 0.5 5 lb +762.812 -17.6227 746.448 -162.381 730.084 -307.139 0.5 0.5 0.5 5 lb +526.164 32.7279 470.779 -128.394 415.393 -289.516 0.5 0.5 0.5 5 lb +730.084 -307.139 572.738 -298.327 415.393 -289.516 0.5 0.5 0.5 5 lb +415.393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0.5 0.5 5 lb +-67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0.5 1 0.5 5 lb +-67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0.5 1 0.5 5 lb +-309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0.5 1 0.5 5 lb +-323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0.5 1 0.5 5 lb +-26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 1 1 0 5 lb +-26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 1 1 0 5 lb +-26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 1 0 1 5 lb +-26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 1 0 1 5 lb +116.407 -173.66 158.808 -67.6589 201.208 38.3422 1 1 0 5 lb +-262.548 107.243 -137.997 120.493 -13.4452 133.743 1 0 1 5 lb +-262.548 107.243 -221.472 176.144 -180.397 245.045 1 0 1 5 lb +-13.4452 133.743 -96.9211 189.394 -180.397 245.045 1 0 1 5 lb +-180.397 245.045 -140.307 344.649 -132.697 451.748 0 1 1 5 lb +-180.397 245.045 -172.787 352.144 -132.697 451.748 0 1 1 5 lb +-416.25 345.746 -274.474 398.747 -132.697 451.748 0.5 0 0 5 lb +-416.25 345.746 -393.725 457.048 -371.2 568.349 0.5 0 0 5 lb +-132.697 451.748 -251.948 510.048 -371.2 568.349 0.5 0 0 5 lb +670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 5 lb +670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 5 lb +588.113 544.499 756.39 476.923 924.667 409.347 0 0 1 5 lb +-689.204 -237.261 -612.964 -103.444 -567.302 43.6423 0 0 0 5 lb +-689.204 -237.261 -643.542 -90.1744 -567.302 43.6423 0 0 0 5 lb +grestore +%Nodes: +gsave +-567.302 43.6423 20 0 0 1 nc +-689.204 -237.261 20 0 0 1 nc +924.667 409.347 20 0 0 1 nc +588.113 544.499 20 0 0 1 nc +670.264 274.195 20 1 0 0 nc +-371.2 568.349 20 0 0 1 nc +-132.697 451.748 20 1 0 0 nc +-416.25 345.746 20 0 0 1 nc +-180.397 245.045 20 1 0 0 nc +-13.4452 133.743 20 0 0 1 nc +-262.548 107.243 20 0 0 1 nc +201.208 38.3422 20 0 0 1 nc +116.407 -173.66 20 0 0 1 nc +-26.6953 -19.9585 20 1 0 0 nc +-539.894 -262.64 20 0 0 1 nc +-323.543 -433.964 20 0 0 1 nc +-309.657 -57.9033 20 1 0 0 nc +-67.9734 -347.42 20 1 0 0 nc +415.393 -289.516 20 1 0 0 nc +730.084 -307.139 20 0 0 1 nc +526.164 32.7279 20 1 0 0 nc +762.812 -17.6227 20 1 0 0 nc +-67.9734 319.727 20 0 0 1 nc +329.797 314.692 20 0 0 1 nc +-5.03507 561.41 20 0 0 1 nc +422.945 521.129 20 0 0 1 nc +-470.779 158.605 20 1 0 0 nc +986.873 -115.807 20 0 0 1 nc +906.312 201.403 20 0 0 1 nc +-767.847 113.289 20 1 0 0 nc +-579.033 445.603 20 0 0 1 nc +-840.856 -246.718 20 0 0 1 nc +206.221 -205.967 20 0 0 1 nc +277.311 -252.33 20 0 0 1 nc +271.13 -175.058 20 1 0 0 nc +366.947 -110.15 20 1 0 0 nc +397.855 -196.694 20 0 0 1 nc +438.037 -88.514 20 0 0 1 nc +286.584 -48.3327 20 1 0 0 nc +212.403 -23.6057 20 0 0 1 nc +280.402 10.3938 20 0 0 1 nc +694.579 115.483 20 0 0 1 nc +574.035 177.301 20 0 0 1 nc +grestore +grestore +showpage diff --git a/lemon/doc/images/nodeshape_0.eps b/lemon/doc/images/nodeshape_0.eps new file mode 100644 index 0000000..5f2f4a8 --- /dev/null +++ b/lemon/doc/images/nodeshape_0.eps @@ -0,0 +1,57 @@ +%!PS-Adobe-2.0 EPSF-2.0 +%%Title: LEMON GraphToEps figure +%%Creator: LEMON GraphToEps function +%%BoundingBox: 0 0 200 200 +%%EndComments +/lb { setlinewidth setrgbcolor newpath moveto + 4 2 roll 1 index 1 index curveto stroke } bind def +/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def +/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def +/sq { newpath 2 index 1 index add 2 index 2 index add moveto + 2 index 1 index sub 2 index 2 index add lineto + 2 index 1 index sub 2 index 2 index sub lineto + 2 index 1 index add 2 index 2 index sub lineto + closepath pop pop pop} bind def +/di { newpath 2 index 1 index add 2 index moveto + 2 index 2 index 2 index add lineto + 2 index 1 index sub 2 index lineto + 2 index 2 index 2 index sub lineto + closepath pop pop pop} bind def +/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill + setrgbcolor 1.1 div c fill + } bind def +/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill + setrgbcolor 1.1 div sq fill + } bind def +/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill + setrgbcolor 1.1 div di fill + } bind def +/arrl 1 def +/arrw 0.3 def +/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def +/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def + /w exch def /len exch def + newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto + len w sub arrl sub dx dy lrl + arrw dy dx neg lrl + dx arrl w add mul dy w 2 div arrw add mul sub + dy arrl w add mul dx w 2 div arrw add mul add rlineto + dx arrl w add mul neg dy w 2 div arrw add mul sub + dy arrl w add mul neg dx w 2 div arrw add mul add rlineto + arrw dy dx neg lrl + len w sub arrl sub neg dx dy lrl + closepath fill } bind def +/cshow { 2 index 2 index moveto dup stringwidth pop + neg 2 div fosi .35 mul neg rmoveto show pop pop} def + +gsave +100 dup scale +%Edges: +gsave +grestore +%Nodes: +gsave +1 1 1 0.2 1 0.2 nc +grestore +grestore +showpage diff --git a/lemon/doc/images/nodeshape_1.eps b/lemon/doc/images/nodeshape_1.eps new file mode 100644 index 0000000..e8b1104 --- /dev/null +++ b/lemon/doc/images/nodeshape_1.eps @@ -0,0 +1,57 @@ +%!PS-Adobe-2.0 EPSF-2.0 +%%Title: LEMON GraphToEps figure +%%Creator: LEMON GraphToEps function +%%BoundingBox: 0 0 200 200 +%%EndComments +/lb { setlinewidth setrgbcolor newpath moveto + 4 2 roll 1 index 1 index curveto stroke } bind def +/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def +/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def +/sq { newpath 2 index 1 index add 2 index 2 index add moveto + 2 index 1 index sub 2 index 2 index add lineto + 2 index 1 index sub 2 index 2 index sub lineto + 2 index 1 index add 2 index 2 index sub lineto + closepath pop pop pop} bind def +/di { newpath 2 index 1 index add 2 index moveto + 2 index 2 index 2 index add lineto + 2 index 1 index sub 2 index lineto + 2 index 2 index 2 index sub lineto + closepath pop pop pop} bind def +/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill + setrgbcolor 1.1 div c fill + } bind def +/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill + setrgbcolor 1.1 div sq fill + } bind def +/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill + setrgbcolor 1.1 div di fill + } bind def +/arrl 1 def +/arrw 0.3 def +/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def +/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def + /w exch def /len exch def + newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto + len w sub arrl sub dx dy lrl + arrw dy dx neg lrl + dx arrl w add mul dy w 2 div arrw add mul sub + dy arrl w add mul dx w 2 div arrw add mul add rlineto + dx arrl w add mul neg dy w 2 div arrw add mul sub + dy arrl w add mul neg dx w 2 div arrw add mul add rlineto + arrw dy dx neg lrl + len w sub arrl sub neg dx dy lrl + closepath fill } bind def +/cshow { 2 index 2 index moveto dup stringwidth pop + neg 2 div fosi .35 mul neg rmoveto show pop pop} def + +gsave +100 dup scale +%Edges: +gsave +grestore +%Nodes: +gsave +1 1 1 0.2 1 0.2 nsq +grestore +grestore +showpage diff --git a/lemon/doc/images/nodeshape_2.eps b/lemon/doc/images/nodeshape_2.eps new file mode 100644 index 0000000..5dcc4aa --- /dev/null +++ b/lemon/doc/images/nodeshape_2.eps @@ -0,0 +1,57 @@ +%!PS-Adobe-2.0 EPSF-2.0 +%%Title: LEMON GraphToEps figure +%%Creator: LEMON GraphToEps function +%%BoundingBox: 0 0 200 200 +%%EndComments +/lb { setlinewidth setrgbcolor newpath moveto + 4 2 roll 1 index 1 index curveto stroke } bind def +/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def +/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def +/sq { newpath 2 index 1 index add 2 index 2 index add moveto + 2 index 1 index sub 2 index 2 index add lineto + 2 index 1 index sub 2 index 2 index sub lineto + 2 index 1 index add 2 index 2 index sub lineto + closepath pop pop pop} bind def +/di { newpath 2 index 1 index add 2 index moveto + 2 index 2 index 2 index add lineto + 2 index 1 index sub 2 index lineto + 2 index 2 index 2 index sub lineto + closepath pop pop pop} bind def +/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill + setrgbcolor 1.1 div c fill + } bind def +/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill + setrgbcolor 1.1 div sq fill + } bind def +/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill + setrgbcolor 1.1 div di fill + } bind def +/arrl 1 def +/arrw 0.3 def +/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def +/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def + /w exch def /len exch def + newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto + len w sub arrl sub dx dy lrl + arrw dy dx neg lrl + dx arrl w add mul dy w 2 div arrw add mul sub + dy arrl w add mul dx w 2 div arrw add mul add rlineto + dx arrl w add mul neg dy w 2 div arrw add mul sub + dy arrl w add mul neg dx w 2 div arrw add mul add rlineto + arrw dy dx neg lrl + len w sub arrl sub neg dx dy lrl + closepath fill } bind def +/cshow { 2 index 2 index moveto dup stringwidth pop + neg 2 div fosi .35 mul neg rmoveto show pop pop} def + +gsave +100 dup scale +%Edges: +gsave +grestore +%Nodes: +gsave +1 1 1 0.2 1 0.2 ndi +grestore +grestore +showpage diff --git a/lemon/doc/images/nodeshape_3.eps b/lemon/doc/images/nodeshape_3.eps new file mode 100644 index 0000000..bc736af --- /dev/null +++ b/lemon/doc/images/nodeshape_3.eps @@ -0,0 +1,77 @@ +%!PS-Adobe-2.0 EPSF-2.0 +%%Title: LEMON GraphToEps figure +%%Creator: LEMON GraphToEps function +%%BoundingBox: 0 0 256 372 +%%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 +100 dup scale +%Edges: +gsave +grestore +%Nodes: +gsave +1 1 1 0.2 1 0.2 nmale +grestore +grestore +showpage diff --git a/lemon/doc/images/nodeshape_4.eps b/lemon/doc/images/nodeshape_4.eps new file mode 100644 index 0000000..e9fa575 --- /dev/null +++ b/lemon/doc/images/nodeshape_4.eps @@ -0,0 +1,77 @@ +%!PS-Adobe-2.0 EPSF-2.0 +%%Title: LEMON GraphToEps figure +%%Creator: LEMON GraphToEps function +%%BoundingBox: 0 -199 200 200 +%%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 +100 dup scale +%Edges: +gsave +grestore +%Nodes: +gsave +1 1 1 0.2 1 0.2 nfemale +grestore +grestore +showpage diff --git a/lemon/doc/images/planar.eps b/lemon/doc/images/planar.eps new file mode 100644 index 0000000..97d0aaf --- /dev/null +++ b/lemon/doc/images/planar.eps @@ -0,0 +1,181 @@ +%!PS-Adobe-2.0 EPSF-2.0 +%%Creator: LEMON, graphToEps() +%%CreationDate: Fri Oct 19 18:32:32 2007 +%%BoundingBox: 0 0 596 842 +%%DocumentPaperSizes: a4 +%%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 +15 138.307 translate +12.7843 dup scale +90 rotate +0.608112 -43.6081 translate +%Edges: +gsave +9 31 9.5 30.5 10 30 0 0 0 0.091217 lb +9 31 5.5 34.5 2 38 0 0 0 0.091217 lb +9 31 25.5 16 42 1 0 0 0 0.091217 lb +3 40 23 20.5 43 1 0 0 0 0.091217 lb +3 40 22.5 20.5 42 1 0 0 0 0.091217 lb +3 40 2.5 40.5 2 41 0 0 0 0.091217 lb +13 25 10.5 24.5 8 24 0 0 0 0.091217 lb +13 25 12 27 11 29 0 0 0 0.091217 lb +3 4 2.5 3 2 2 0 0 0 0.091217 lb +3 4 4.5 3 6 2 0 0 0 0.091217 lb +6 25 7 24.5 8 24 0 0 0 0.091217 lb +6 25 6 24.5 6 24 0 0 0 0.091217 lb +34 2 33.5 2 33 2 0 0 0 0.091217 lb +34 2 35 2 36 2 0 0 0 0.091217 lb +6 8 16 9 26 10 0 0 0 0.091217 lb +6 8 6 10.5 6 13 0 0 0 0.091217 lb +6 8 6 7.5 6 7 0 0 0 0.091217 lb +26 10 27.5 8.5 29 7 0 0 0 0.091217 lb +26 10 27.5 9 29 8 0 0 0 0.091217 lb +10 30 10.5 29.5 11 29 0 0 0 0.091217 lb +8 24 7 23.5 6 23 0 0 0 0.091217 lb +8 24 8 24.5 8 25 0 0 0 0.091217 lb +33 2 32.5 2 32 2 0 0 0 0.091217 lb +29 7 17.5 7 6 7 0 0 0 0.091217 lb +2 2 1.5 22 1 42 0 0 0 0.091217 lb +2 2 3.5 2 5 2 0 0 0 0.091217 lb +21 15 13.5 14.5 6 14 0 0 0 0.091217 lb +21 15 21 15.5 21 16 0 0 0 0.091217 lb +1 42 0.5 42.5 0 43 0 0 0 0.091217 lb +1 42 1.5 41.5 2 41 0 0 0 0.091217 lb +6 15 6 15.5 6 16 0 0 0 0.091217 lb +6 15 6 14.5 6 14 0 0 0 0.091217 lb +43 1 22 0.5 1 0 0 0 0 0.091217 lb +31 2 18.5 2 6 2 0 0 0 0.091217 lb +31 2 31.5 2 32 2 0 0 0 0.091217 lb +6 24 6 23.5 6 23 0 0 0 0.091217 lb +6 16 6 16.5 6 17 0 0 0 0.091217 lb +6 23 6 20 6 17 0 0 0 0.091217 lb +6 2 5.5 2 5 2 0 0 0 0.091217 lb +6 2 6 4.5 6 7 0 0 0 0.091217 lb +0 43 0.5 21.5 1 0 0 0 0 0.091217 lb +1 1 19.5 1.5 38 2 0 0 0 0.091217 lb +1 1 1 0.5 1 0 0 0 0 0.091217 lb +2 38 5.5 31.5 9 25 0 0 0 0.091217 lb +25 13 15.5 13 6 13 0 0 0 0.091217 lb +25 13 15.5 13.5 6 14 0 0 0 0.091217 lb +8 25 8.5 25 9 25 0 0 0 0.091217 lb +11 29 24.5 15.5 38 2 0 0 0 0.091217 lb +6 17 11.5 18 17 19 0 0 0 0.091217 lb +16 23 26.5 12.5 37 2 0 0 0 0.091217 lb +16 23 18.5 19.5 21 16 0 0 0 0.091217 lb +36 2 36.5 2 37 2 0 0 0 0.091217 lb +36 2 32.5 5 29 8 0 0 0 0.091217 lb +6 13 6 13.5 6 14 0 0 0 0.091217 lb +37 2 37.5 2 38 2 0 0 0 0.091217 lb +21 16 19 17.5 17 19 0 0 0 0.091217 lb +grestore +%Nodes: +gsave +29 8 0.304556 1 1 1 nc +2 41 0.304556 1 1 1 nc +6 7 0.304556 1 1 1 nc +5 2 0.304556 1 1 1 nc +17 19 0.304556 1 1 1 nc +21 16 0.304556 1 1 1 nc +1 0 0.304556 1 1 1 nc +9 25 0.304556 1 1 1 nc +6 14 0.304556 1 1 1 nc +42 1 0.304556 1 1 1 nc +38 2 0.304556 1 1 1 nc +37 2 0.304556 1 1 1 nc +6 13 0.304556 1 1 1 nc +36 2 0.304556 1 1 1 nc +16 23 0.304556 1 1 1 nc +6 17 0.304556 1 1 1 nc +11 29 0.304556 1 1 1 nc +8 25 0.304556 1 1 1 nc +32 2 0.304556 1 1 1 nc +25 13 0.304556 1 1 1 nc +2 38 0.304556 1 1 1 nc +1 1 0.304556 1 1 1 nc +0 43 0.304556 1 1 1 nc +6 2 0.304556 1 1 1 nc +6 23 0.304556 1 1 1 nc +6 16 0.304556 1 1 1 nc +6 24 0.304556 1 1 1 nc +31 2 0.304556 1 1 1 nc +43 1 0.304556 1 1 1 nc +6 15 0.304556 1 1 1 nc +1 42 0.304556 1 1 1 nc +21 15 0.304556 1 1 1 nc +2 2 0.304556 1 1 1 nc +29 7 0.304556 1 1 1 nc +33 2 0.304556 1 1 1 nc +8 24 0.304556 1 1 1 nc +10 30 0.304556 1 1 1 nc +26 10 0.304556 1 1 1 nc +6 8 0.304556 1 1 1 nc +34 2 0.304556 1 1 1 nc +6 25 0.304556 1 1 1 nc +3 4 0.304556 1 1 1 nc +13 25 0.304556 1 1 1 nc +3 40 0.304556 1 1 1 nc +9 31 0.304556 1 1 1 nc +grestore +grestore +showpage diff --git a/lemon/doc/images/strongly_connected_components.eps b/lemon/doc/images/strongly_connected_components.eps new file mode 100644 index 0000000..0f0d8fe --- /dev/null +++ b/lemon/doc/images/strongly_connected_components.eps @@ -0,0 +1,180 @@ +%!PS-Adobe-2.0 EPSF-2.0 +%%Creator: LEMON, graphToEps() +%%CreationDate: Fri Nov 4 13:47:12 2005 +%%BoundingBox: 0 0 842 596 +%%EndComments +/lb { setlinewidth setrgbcolor newpath moveto + 4 2 roll 1 index 1 index curveto stroke } bind def +/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def +/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def +/sq { newpath 2 index 1 index add 2 index 2 index add moveto + 2 index 1 index sub 2 index 2 index add lineto + 2 index 1 index sub 2 index 2 index sub lineto + 2 index 1 index add 2 index 2 index sub lineto + closepath pop pop pop} bind def +/di { newpath 2 index 1 index add 2 index moveto + 2 index 2 index 2 index add lineto + 2 index 1 index sub 2 index lineto + 2 index 2 index 2 index sub lineto + closepath pop pop pop} bind def +/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill + setrgbcolor 1.1 div c fill + } bind def +/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill + setrgbcolor 1.1 div sq fill + } bind def +/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill + setrgbcolor 1.1 div di fill + } bind def +/arrl 10 def +/arrw 3 def +/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def +/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def + /w exch def /len exch def + newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto + len w sub arrl sub dx dy lrl + arrw dy dx neg lrl + dx arrl w add mul dy w 2 div arrw add mul sub + dy arrl w add mul dx w 2 div arrw add mul add rlineto + dx arrl w add mul neg dy w 2 div arrw add mul sub + dy arrl w add mul neg dx w 2 div arrw add mul add rlineto + arrw dy dx neg lrl + len w sub arrl sub neg dx dy lrl + closepath fill } bind def +/cshow { 2 index 2 index moveto dup stringwidth pop + neg 2 div fosi .35 mul neg rmoveto show pop pop} def + +gsave +90 rotate +0 -842 translate +77.1122 15 translate +0.585745 dup scale +90 rotate +695.963 -397.916 translate +%Edges: +gsave +2 setlinewidth 0 0 1 setrgbcolor newpath +218.178 27.2723 moveto +192.373 -40.1551 188.622 -49.9556 169.228 -100.631 curveto stroke +newpath 164.939 -111.838 moveto 165.492 -99.2013 lineto 172.964 -102.061 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +44.8044 15.5841 moveto +119.293 20.6059 129.775 21.3125 186.25 25.1199 curveto stroke +newpath 198.223 25.927 moveto 186.519 21.1289 lineto 185.981 29.1108 lineto closepath fill +2 setlinewidth 1 0 0 setrgbcolor newpath +218.178 27.2723 moveto +285.395 -87.4449 290.763 -96.6058 348.102 -194.464 curveto stroke +newpath 354.169 -204.818 moveto 344.651 -196.487 lineto 351.554 -192.442 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +157.79 -130.517 moveto +108.71 -67.0521 102.27 -58.7243 64.3804 -9.72954 curveto stroke +newpath 57.0394 -0.236898 moveto 67.5446 -7.28254 lineto 61.2162 -12.1765 lineto closepath fill +2 setlinewidth 1 0 0 setrgbcolor newpath +-105.193 -261.035 moveto +-35.6576 -132.801 -30.5923 -123.459 29.5506 -12.5464 curveto stroke +newpath 35.2708 -1.99743 moveto 33.0669 -14.4531 lineto 26.0343 -10.6397 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +-465.576 -42.8564 moveto +-559.078 -25.5413 -569.47 -23.6169 -644.498 -9.72286 curveto stroke +newpath -656.297 -7.5378 moveto -643.77 -5.78973 lineto -645.226 -13.656 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +-574.666 -153.893 moveto +-528.842 -107.252 -521.515 -99.794 -488.002 -65.683 curveto stroke +newpath -479.592 -57.123 moveto -485.149 -68.4863 lineto -490.856 -62.8797 lineto closepath fill +2 setlinewidth 1 0 0 setrgbcolor newpath +-490.901 120.777 moveto +-480.122 51.1328 -478.519 40.7713 -470.47 -11.2329 curveto stroke +newpath -468.635 -23.0917 moveto -474.423 -11.8447 lineto -466.517 -10.6212 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +-675.963 -3.89604 moveto +-632.116 -68.8235 -626.228 -77.5422 -592.575 -127.374 curveto stroke +newpath -585.859 -137.319 moveto -595.89 -129.612 lineto -589.26 -125.135 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +-490.901 120.777 moveto +-435.445 215.844 -430.107 224.995 -384.3 303.522 curveto stroke +newpath -378.253 313.887 moveto -380.845 301.507 lineto -387.755 305.537 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +-266.879 114.933 moveto +-367.067 117.547 -377.642 117.822 -458.912 119.943 curveto stroke +newpath -470.908 120.255 moveto -458.807 123.941 lineto -459.016 115.944 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +-368.176 331.163 moveto +-322.511 233.685 -318.018 224.095 -280.454 143.911 curveto stroke +newpath -275.364 133.044 moveto -284.076 142.214 lineto -276.832 145.608 lineto closepath fill +2 setlinewidth 1 0 0 setrgbcolor newpath +-266.879 114.933 moveto +-224.004 235.52 -220.448 245.52 -184.094 347.765 curveto stroke +newpath -180.074 359.072 moveto -180.325 346.425 lineto -187.863 349.105 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +-251.294 -335.059 moveto +-189.25 -303.624 -179.902 -298.887 -133.738 -275.498 curveto stroke +newpath -123.034 -270.074 moveto -131.93 -279.066 lineto -135.546 -271.93 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +-389.604 -136.361 moveto +-327.15 -226.083 -321.098 -234.777 -269.576 -308.795 curveto stroke +newpath -262.72 -318.644 moveto -272.859 -311.081 lineto -266.293 -306.51 lineto closepath fill +2 setlinewidth 1 0 0 setrgbcolor newpath +5.84406 175.322 moveto +-76.0754 267.926 -83.1051 275.873 -152.172 353.948 curveto stroke +newpath -160.122 362.936 moveto -149.176 356.598 lineto -155.168 351.298 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +169.478 311.683 moveto +96.8003 251.119 88.6819 244.353 30.4273 195.808 curveto stroke +newpath 21.2086 188.126 moveto 27.8666 198.881 lineto 32.988 192.735 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +342.851 111.037 moveto +263.766 202.563 256.831 210.589 190.4 287.47 curveto stroke +newpath 182.554 296.55 moveto 193.427 290.085 lineto 187.373 284.855 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +5.84406 175.322 moveto +163.16 145.314 173.605 143.321 311.418 117.033 curveto stroke +newpath 323.205 114.784 moveto 310.668 113.104 lineto 312.167 120.962 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +342.851 111.037 moveto +497.255 2.58683 505.964 -3.53033 643.932 -100.436 curveto stroke +newpath 653.752 -107.334 moveto 641.633 -103.71 lineto 646.231 -97.163 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +364.28 -222.074 moveto +354.298 -66.9063 353.616 -56.2971 344.905 79.1029 curveto stroke +newpath 344.135 91.0781 moveto 348.897 79.3597 lineto 340.914 78.8461 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +670.118 -118.829 moveto +528.037 -166.793 517.967 -170.192 394.599 -211.839 curveto stroke +newpath 383.229 -215.677 moveto 393.32 -208.049 lineto 395.878 -215.629 lineto closepath fill +2 setlinewidth 1 0 0 setrgbcolor newpath +-105.193 -261.035 moveto +118.401 -242.479 129.015 -241.598 332.39 -224.721 curveto stroke +newpath 344.348 -223.728 moveto 332.72 -228.707 lineto 332.059 -220.734 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +-105.193 -261.035 moveto +-160.867 -161.176 -166.028 -151.918 -212.336 -68.858 curveto stroke +newpath -218.179 -58.3769 moveto -208.842 -66.9102 lineto -215.829 -70.8058 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +-227.918 -40.9084 moveto +-298.35 -82.4884 -307.42 -87.8432 -362.048 -120.093 curveto stroke +newpath -372.381 -126.193 moveto -364.081 -116.648 lineto -360.014 -123.537 lineto closepath fill +grestore +%Nodes: +gsave +-389.604 -136.361 20 0 1 0 nc +-227.918 -40.9084 20 0 1 0 nc +-105.193 -261.035 20 0 1 0 nc +364.28 -222.074 20 1 1 0 nc +670.118 -118.829 20 1 1 0 nc +342.851 111.037 20 1 1 0 nc +5.84406 175.322 20 1 1 0 nc +169.478 311.683 20 1 1 0 nc +-173.374 377.916 20 1 0 1 nc +-251.294 -335.059 20 0 1 0 nc +-266.879 114.933 20 0 0 0 nc +-368.176 331.163 20 0 0 0 nc +-490.901 120.777 20 0 0 0 nc +-574.666 -153.893 20 1 0 0 nc +-675.963 -3.89604 20 1 0 0 nc +-465.576 -42.8564 20 1 0 0 nc +44.8044 15.5841 20 0 0 1 nc +157.79 -130.517 20 0 0 1 nc +218.178 27.2723 20 0 0 1 nc +grestore +grestore +showpage diff --git a/lemon/doc/lgf.dox b/lemon/doc/lgf.dox new file mode 100644 index 0000000..b5bf2f5 --- /dev/null +++ b/lemon/doc/lgf.dox @@ -0,0 +1,118 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2011 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +namespace lemon { +/*! + + + +\page lgf-format LEMON Graph Format (LGF) + +The \e LGF is a <em>column oriented</em> +file format for storing graphs and associated data like +node and edge maps. + +Each line with \c '#' first non-whitespace +character is considered as a comment line. + +Otherwise the file consists of sections starting with +a header line. The header lines starts with an \c '@' character followed by the +type of section. The standard section types are \c \@nodes, \c +\@arcs and \c \@edges +and \@attributes. Each header line may also have an optional +\e name, which can be use to distinguish the sections of the same +type. + +The standard sections are column oriented, each line consists of +<em>token</em>s separated by whitespaces. A token can be \e plain or +\e quoted. A plain token is just a sequence of non-whitespace characters, +while a quoted token is a +character sequence surrounded by double quotes, and it can also +contain whitespaces and escape sequences. + +The \c \@nodes section describes a set of nodes and associated +maps. The first is a header line, its columns are the names of the +maps appearing in the following lines. +One of the maps must be called \c +"label", which plays special role in the file. +The following +non-empty lines until the next section describes nodes of the +graph. Each line contains the values of the node maps +associated to the current node. + +\code + @nodes + label coordinates size title + 1 (10,20) 10 "First node" + 2 (80,80) 8 "Second node" + 3 (40,10) 10 "Third node" +\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 +values. The source and target tokens must be node labels. + +\code + @arcs + capacity + 1 2 16 + 1 3 12 + 2 3 18 +\endcode + +If there is no map in the \c \@arcs section at all, then it must be +indicated by a sole '-' sign in the first line. + +\code + @arcs + - + 1 2 + 1 3 + 2 3 +\endcode + +The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can +also store the edge set of an undirected graph. In such case there is +a conventional method for store arc maps in the file, if two columns +have the same caption with \c '+' and \c '-' prefix, then these columns +can be regarded as the values of an arc map. + +The \c \@attributes section contains key-value pairs, each line +consists of two tokens, an attribute name, and then an attribute +value. The value of the attribute could be also a label value of a +node or an edge, or even an edge label prefixed with \c '+' or \c '-', +which regards to the forward or backward directed arc of the +corresponding edge. + +\code + @attributes + source 1 + target 3 + caption "LEMON test digraph" +\endcode + +The \e LGF can contain extra sections, but there is no restriction on +the format of such sections. + +*/ +} + +// LocalWords: whitespace whitespaces diff --git a/lemon/doc/license.dox b/lemon/doc/license.dox new file mode 100644 index 0000000..a40939b --- /dev/null +++ b/lemon/doc/license.dox @@ -0,0 +1,25 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2009 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +/** + +\page license License Terms + +\verbinclude LICENSE + +*/ diff --git a/lemon/doc/mainpage.dox b/lemon/doc/mainpage.dox new file mode 100644 index 0000000..b947bae --- /dev/null +++ b/lemon/doc/mainpage.dox @@ -0,0 +1,61 @@ +/* -*- 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. + * + */ + +/** +\mainpage LEMON 1.2.3 Documentation + +\section intro Introduction + +<b>LEMON</b> stands for <i><b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling +and <b>O</b>ptimization in <b>N</b>etworks</i>. +It is a C++ template library providing efficient implementations of common +data structures and algorithms with focus on combinatorial optimization +tasks connected mainly with graphs and networks. + +<b> +LEMON is an <a class="el" href="http://opensource.org/">open source</a> +project. +You are free to use it in your commercial or +non-commercial applications under very permissive +\ref license "license terms". +</b> + +The project is maintained by the +<a href="http://www.cs.elte.hu/egres/">Egerváry Research Group on +Combinatorial Optimization</a> \ref egres +at the Operations Research Department of the +<a href="http://www.elte.hu/en/">Eötvös Loránd University</a>, +Budapest, Hungary. +LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a> +initiative \ref coinor. + +\section howtoread How to Read the Documentation + +If you would like to get to know the library, see +<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>. + +If you are interested in starting to use the library, see the <a class="el" +href="http://lemon.cs.elte.hu/trac/lemon/wiki/InstallGuide/">Installation +Guide</a>. + +If you know what you are looking for, then try to find it under the +<a class="el" href="modules.html">Modules</a> section. + +If you are a user of the old (0.x) series of LEMON, please check out the +\ref migration "Migration Guide" for the backward incompatibilities. +*/ diff --git a/lemon/doc/mainpage.dox.in b/lemon/doc/mainpage.dox.in new file mode 100644 index 0000000..86f124d --- /dev/null +++ b/lemon/doc/mainpage.dox.in @@ -0,0 +1,61 @@ +/* -*- 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. + * + */ + +/** +\mainpage @PACKAGE_NAME@ @PACKAGE_VERSION@ Documentation + +\section intro Introduction + +<b>LEMON</b> stands for <i><b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling +and <b>O</b>ptimization in <b>N</b>etworks</i>. +It is a C++ template library providing efficient implementations of common +data structures and algorithms with focus on combinatorial optimization +tasks connected mainly with graphs and networks. + +<b> +LEMON is an <a class="el" href="http://opensource.org/">open source</a> +project. +You are free to use it in your commercial or +non-commercial applications under very permissive +\ref license "license terms". +</b> + +The project is maintained by the +<a href="http://www.cs.elte.hu/egres/">Egerváry Research Group on +Combinatorial Optimization</a> \ref egres +at the Operations Research Department of the +<a href="http://www.elte.hu/en/">Eötvös Loránd University</a>, +Budapest, Hungary. +LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a> +initiative \ref coinor. + +\section howtoread How to Read the Documentation + +If you would like to get to know the library, see +<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>. + +If you are interested in starting to use the library, see the <a class="el" +href="http://lemon.cs.elte.hu/trac/lemon/wiki/InstallGuide/">Installation +Guide</a>. + +If you know what you are looking for, then try to find it under the +<a class="el" href="modules.html">Modules</a> section. + +If you are a user of the old (0.x) series of LEMON, please check out the +\ref migration "Migration Guide" for the backward incompatibilities. +*/ diff --git a/lemon/doc/migration.dox b/lemon/doc/migration.dox new file mode 100644 index 0000000..3117aa3 --- /dev/null +++ b/lemon/doc/migration.dox @@ -0,0 +1,145 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2009 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +namespace lemon { +/*! + +\page migration Migration from the 0.x Series + +This guide gives an in depth description on what has changed compared +to the 0.x release series. + +Many of these changes adjusted automatically by the +<tt>lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual +update are typeset <b>boldface</b>. + +\section migration-graph Graph Related Name Changes + +- \ref concepts::Digraph "Directed graphs" are called \c Digraph and + they have <tt>Arc</tt>s (instead of <tt>Edge</tt>s), while + \ref concepts::Graph "undirected graphs" are called \c Graph + (instead of \c UGraph) and they have <tt>Edge</tt>s (instead of + <tt>UEdge</tt>s). These changes reflected thoroughly everywhere in + the library. Namely, + - \c Graph -> \c Digraph + - \c %ListGraph -> \c ListDigraph, \c %SmartGraph -> \c SmartDigraph etc. + - \c UGraph -> \c Graph + - \c ListUGraph -> \c ListGraph, \c SmartUGraph -> \c SmartGraph etc. + - \c Edge -> \c Arc, \c UEdge -> \c Edge + - \c EdgeMap -> \c ArcMap, \c UEdgeMap -> \c EdgeMap + - \c EdgeIt -> \c ArcIt, \c UEdgeIt -> \c EdgeIt + - Class names and function names containing the words \c graph, + \c ugraph, \e edge or \e arc should also be updated. +- <b>The two endpoints of an (\e undirected) \c Edge can be obtained by the + <tt>u()</tt> and <tt>v()</tt> member function of the graph + (instead of <tt>source()</tt> and <tt>target()</tt>). This change + must be done by hand.</b> + \n Of course, you can still use <tt>source()</tt> and <tt>target()</tt> + for <tt>Arc</tt>s (directed edges). + +\warning +<b>The <tt>lemon-0.x-to-1.x.sh</tt> script replaces the words \c graph, +\c ugraph, \c edge and \c uedge in your own identifiers and in +strings, comments etc. as well as in all LEMON specific identifiers. +So use the script carefully and make a backup copy of your source files +before applying the script to them.</b> + +\section migration-lgf LGF tools + - The \ref lgf-format "LGF file format" has changed, + <tt>\@nodeset</tt> has changed to <tt>\@nodes</tt>, + <tt>\@edgeset</tt> and <tt>\@uedgeset</tt> to <tt>\@arcs</tt> or + <tt>\@edges</tt>, which become completely equivalents. The + <tt>\@nodes</tt>, <tt>\@edges</tt> and <tt>\@uedges</tt> sections are + removed from the format, the content of them should be + the part of <tt>\@attributes</tt> section. The data fields in + the sections must follow a strict format, they must be either character + sequences without whitespaces or quoted strings. + - The <tt>LemonReader</tt> and <tt>LemonWriter</tt> core interfaces + are no longer available. + - The implementation of the general section readers and writers has changed + they are simple functors now. Beside the old + stream based section handling, currently line oriented section + reading and writing are also supported. In the + section readers the lines must be counted manually. The sections + should be read and written with the SectionWriter and SectionReader + classes. + - Instead of the item readers and writers, item converters should be + used. The converters are functors, which map the type to + std::string or std::string to the type. The converters for standard + containers hasn't yet been implemented in the new LEMON. The converters + can return strings in any format, because if it is necessary, the LGF + writer and reader will quote and unquote the given value. + - The DigraphReader and DigraphWriter can used similarly to the + 0.x series, however the <tt>read</tt> or <tt>write</tt> prefix of + the member functions are removed. + - The new LEMON supports the function like interface, the \c + digraphReader and \c digraphWriter functions are more convenient than + using the classes directly. + +\section migration-search BFS, DFS and Dijkstra +- <b>Using the function interface of BFS, DFS and %Dijkstra both source and + target nodes can be given as parameters of the <tt>run()</tt> function + (instead of \c bfs(), \c dfs() or \c dijkstra() itself).</b> +- \ref named-templ-param "Named class template parameters" of \c Bfs, + \c Dfs, \c Dijkstra, \c BfsVisit, \c DfsVisit are renamed to start + with "Set" instead of "Def". Namely, + - \c DefPredMap -> \c SetPredMap + - \c DefDistMap -> \c SetDistMap + - \c DefReachedMap -> \c SetReachedMap + - \c DefProcessedMap -> \c SetProcessedMap + - \c DefHeap -> \c SetHeap + - \c DefStandardHeap -> \c SetStandardHeap + - \c DefOperationTraits -> \c SetOperationTraits + - \c DefProcessedMapToBeDefaultMap -> \c SetStandardProcessedMap + +\section migration-error Exceptions and Debug tools + +<b>The class hierarchy of exceptions has largely been simplified. Now, +only the i/o related tools may throw exceptions. All other exceptions +have been replaced with either the \c LEMON_ASSERT or the \c LEMON_DEBUG +macros.</b> + +<b>On the other hand, the parameter order of constructors of the +exceptions has been changed. See \ref IoError and \ref FormatError for +more details.</b> + +\section migration-other Others +- <b>The contents of <tt>graph_utils.h</tt> are moved to <tt>core.h</tt> + and <tt>maps.h</tt>. <tt>core.h</tt> is included by all graph types, + therefore it usually do not have to be included directly.</b> +- <b><tt>path_utils.h</tt> is merged to \c path.h.</b> +- <b>The semantic of the assignment operations and copy constructors of maps + are still under discussion. So, you must copy them by hand (i.e. copy + each entry one-by-one)</b> +- <b>The parameters of the graph copying tools (i.e. \c GraphCopy, + \c DigraphCopy) have to be given in the from-to order.</b> +- \c copyDigraph() and \c copyGraph() are renamed to \c digraphCopy() + and \c graphCopy(), respectively. +- <b>The interface of \ref DynArcLookUp has changed. It is now the same as + of \ref ArcLookUp and \ref AllArcLookUp</b> +- Some map types should also been renamed. Namely, + - \c IntegerMap -> \c RangeMap + - \c StdMap -> \c SparseMap + - \c FunctorMap -> \c FunctorToMap + - \c MapFunctor -> \c MapToFunctor + - \c ForkWriteMap -> \c ForkMap + - \c StoreBoolMap -> \c LoggerBoolMap +- \c dim2::BoundingBox -> \c dim2::Box + +*/ +} diff --git a/lemon/doc/min_cost_flow.dox b/lemon/doc/min_cost_flow.dox new file mode 100644 index 0000000..ae8f044 --- /dev/null +++ b/lemon/doc/min_cost_flow.dox @@ -0,0 +1,153 @@ +/* -*- 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. + * + */ + +namespace lemon { + +/** +\page min_cost_flow Minimum Cost Flow Problem + +\section mcf_def Definition (GEQ form) + +The \e minimum \e cost \e flow \e problem is to find a feasible flow of +minimum total cost from a set of supply nodes to a set of demand nodes +in a network with capacity constraints (lower and upper bounds) +and arc costs \ref amo93networkflows. + +Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$, +\f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and +upper bounds for the flow values on the arcs, for which +\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$, +\f$cost: A\rightarrow\mathbf{R}\f$ denotes the cost per unit flow +on the arcs and \f$sup: V\rightarrow\mathbf{R}\f$ denotes the +signed supply values of the nodes. +If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$ +supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with +\f$-sup(u)\f$ demand. +A minimum cost flow is an \f$f: A\rightarrow\mathbf{R}\f$ solution +of the following optimization problem. + +\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f] +\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq + sup(u) \quad \forall u\in V \f] +\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f] + +The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be +zero or negative in order to have a feasible solution (since the sum +of the expressions on the left-hand side of the inequalities is zero). +It means that the total demand must be greater or equal to the total +supply and all the supplies have to be carried out from the supply nodes, +but there could be demands that are not satisfied. +If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand +constraints have to be satisfied with equality, i.e. all demands +have to be satisfied and all supplies have to be used. + + +\section mcf_algs Algorithms + +LEMON contains several algorithms for solving this problem, for more +information see \ref min_cost_flow_algs "Minimum Cost Flow Algorithms". + +A feasible solution for this problem can be found using \ref Circulation. + + +\section mcf_dual Dual Solution + +The dual solution of the minimum cost flow problem is represented by +node potentials \f$\pi: V\rightarrow\mathbf{R}\f$. +An \f$f: A\rightarrow\mathbf{R}\f$ primal feasible solution is optimal +if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$ node potentials +the following \e complementary \e slackness optimality conditions hold. + + - For all \f$uv\in A\f$ arcs: + - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$; + - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$; + - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$. + - For all \f$u\in V\f$ nodes: + - \f$\pi(u)\leq 0\f$; + - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$, + then \f$\pi(u)=0\f$. + +Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc +\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e. +\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f] + +All algorithms provide dual solution (node potentials), as well, +if an optimal flow is found. + + +\section mcf_eq Equality Form + +The above \ref mcf_def "definition" is actually more general than the +usual formulation of the minimum cost flow problem, in which strict +equalities are required in the supply/demand contraints. + +\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f] +\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) = + sup(u) \quad \forall u\in V \f] +\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f] + +However if the sum of the supply values is zero, then these two problems +are equivalent. +The \ref min_cost_flow_algs "algorithms" in LEMON support the general +form, so if you need the equality form, you have to ensure this additional +contraint manually. + + +\section mcf_leq Opposite Inequalites (LEQ Form) + +Another possible definition of the minimum cost flow problem is +when there are <em>"less or equal"</em> (LEQ) supply/demand constraints, +instead of the <em>"greater or equal"</em> (GEQ) constraints. + +\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f] +\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq + sup(u) \quad \forall u\in V \f] +\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f] + +It means that the total demand must be less or equal to the +total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or +positive) and all the demands have to be satisfied, but there +could be supplies that are not carried out from the supply +nodes. +The equality form is also a special case of this form, of course. + +You could easily transform this case to the \ref mcf_def "GEQ form" +of the problem by reversing the direction of the arcs and taking the +negative of the supply values (e.g. using \ref ReverseDigraph and +\ref NegMap adaptors). +However \ref NetworkSimplex algorithm also supports this form directly +for the sake of convenience. + +Note that the optimality conditions for this supply constraint type are +slightly differ from the conditions that are discussed for the GEQ form, +namely the potentials have to be non-negative instead of non-positive. +An \f$f: A\rightarrow\mathbf{R}\f$ feasible solution of this problem +is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$ +node potentials the following conditions hold. + + - For all \f$uv\in A\f$ arcs: + - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$; + - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$; + - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$. + - For all \f$u\in V\f$ nodes: + - \f$\pi(u)\geq 0\f$; + - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$, + then \f$\pi(u)=0\f$. + +*/ +} diff --git a/lemon/doc/named-param.dox b/lemon/doc/named-param.dox new file mode 100644 index 0000000..2a981f7 --- /dev/null +++ b/lemon/doc/named-param.dox @@ -0,0 +1,119 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2009 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +/*! + +\page named-param Named Parameters + +\section named-func-param Named Function Parameters + +Several modern languages provide a convenient way to refer the +function parameters by name also when you call the function. It is +especially comfortable in case of a function having tons of parameters +with natural default values. Sadly, C++ lack this amenity. + +However, with a crafty trick and with some little +inconvenience, it is possible to emulate is. +The example below shows how to do it. + +\code +class namedFn +{ + int _id; + double _val; + int _dim; + + public: + namedFn() : _id(0), _val(1), _dim(2) {} + namedFn& id(int p) { _id = p ; return *this; } + namedFn& val(double p) { _val = p ; return *this; } + namedFn& dim(int p) { _dim = p ; return *this; } + + run() { + std::cout << "Here comes the function itself\n" << + << "With parameters " + << _id << ", " << _val << ", " << _dim << std::endl; + } +}; +\endcode + +Then you can use it like this. + +\code +namedFn().id(3).val(2).run(); +\endcode + +The trick is obvious, each "named parameter" changes one component of +the underlying class, then gives back a reference to it. Finally, +<tt>run()</tt> executes the algorithm itself. + +\note Although it is a class, namedFn is used pretty much like as it were +a function. That it why we called it namedFn instead of \c NamedFn. + +\note In fact, the final <tt>.run()</tt> could be made unnecessary, +because the algorithm could also be implemented in the destructor of +\c namedFn instead. This however would make it impossible to implement +functions with return values, and would also cause serious problems when +implementing \ref named-templ-func-param "named template parameters". +<b>Therefore, by convention, <tt>.run()</tt> must be used +explicitly to execute a function having named parameters +everywhere in LEMON.</b> + +\section named-templ-func-param Named Function Template Parameters + +A named parameter can also be a template function. The usage is +exactly the same, but the implementation behind is a kind of black +magic and they are the dirtiest part of the LEMON code. + +You will probably never need to know how it works, but if you really +committed, have a look at \ref lemon/graph_to_eps.h for an example. + +\section traits-classes Traits Classes + +A similar game can also be played when defining classes. In this case +the type of the class attributes can be changed. Initially we have to +define a special class called <em>Traits Class</em> defining the +default type of the attributes. Then the types of these attributes can +be changed in the same way as described in the next section. + +See \ref lemon::DijkstraDefaultTraits for an +example how a traits class implementation looks like. + +\section named-templ-param Named Class Template Parameters + +If we would like to change the type of an attribute in a class that +was instantiated by using a traits class as a template parameter, and +the class contains named parameters, we do not have to instantiate again +the class with new traits class, but instead adaptor classes can +be used as shown in the following example. + +\code +Dijkstra<>::SetPredMap<NullMap<Node,Arc> >::Create +\endcode + +It can also be used in conjunction with other named template +parameters in arbitrary order. + +\code +Dijkstra<>::SetDistMap<MyMap>::SetPredMap<NullMap<Node,Arc> >::Create +\endcode + +The result will be an instantiated Dijkstra class, in which the +DistMap and the PredMap is modified. + +*/ diff --git a/lemon/doc/namespaces.dox b/lemon/doc/namespaces.dox new file mode 100644 index 0000000..248ca20 --- /dev/null +++ b/lemon/doc/namespaces.dox @@ -0,0 +1,30 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2009 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +/// The namespace of LEMON + +/// The namespace of LEMON +/// +namespace lemon { + + /// The namespace of LEMON concepts and concept checking classes + + /// The namespace of LEMON concepts and concept checking classes + /// + namespace concepts {} +} |