COIN-OR::LEMON - Graph Library

Ignore:
Files:
3 added
33 deleted
121 edited

Legend:

Unmodified
Added
Removed
  • .hgignore

    r564 r400  
    2323lemon/stamp-h2
    2424doc/Doxyfile
    25 cmake/cmake.version
    2625.dirstamp
    2726.libs/*
    2827.deps/*
    2928demo/*.eps
    30 m4/libtool.m4
    31 m4/ltoptions.m4
    32 m4/ltsugar.m4
    33 m4/ltversion.m4
    34 m4/lt~obsolete.m4
    3529
    3630syntax: regexp
     
    4135^autom4te.cache/.*
    4236^build-aux/.*
    43 ^.*objs.*/.*
     37^objs.*/.*
    4438^test/[a-z_]*$
    4539^tools/[a-z-_]*$
    4640^demo/.*_demo$
    47 ^.*build.*/.*
     41^build/.*
    4842^doc/gen-images/.*
    4943CMakeFiles
  • CMakeLists.txt

    r574 r274  
    11CMAKE_MINIMUM_REQUIRED(VERSION 2.6)
    22
    3 IF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
    4   INCLUDE(${CMAKE_SOURCE_DIR}/cmake/version.cmake)
    5 ELSE(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
    6   SET(PROJECT_NAME "LEMON")
    7   SET(PROJECT_VERSION "hg-tip" CACHE STRING "LEMON version string.")
    8 ENDIF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
     3SET(PROJECT_NAME "LEMON")
     4SET(PROJECT_VERSION "hg-tip" CACHE STRING "The version string.")
    95
    106PROJECT(${PROJECT_NAME})
     
    1410INCLUDE(FindDoxygen)
    1511INCLUDE(FindGhostscript)
    16 FIND_PACKAGE(GLPK 4.33)
    17 
    18 ADD_DEFINITIONS(-DHAVE_CONFIG_H)
    19 
    20 IF(MSVC)
    21   SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} /wd4250 /wd4355 /wd4800 /wd4996")
    22 # Suppressed warnings:
    23 # C4250: 'class1' : inherits 'class2::member' via dominance
    24 # C4355: 'this' : used in base member initializer list
    25 # C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning)
    26 # C4996: 'function': was declared deprecated
    27 ENDIF(MSVC)
    28 
    29 IF(GLPK_FOUND)
    30   SET(HAVE_LP TRUE)
    31   SET(HAVE_MIP TRUE)
    32   SET(HAVE_GLPK TRUE)
    33 ENDIF(GLPK_FOUND)
    34 
    35 INCLUDE(CheckTypeSize)
    36 CHECK_TYPE_SIZE("long long" LONG_LONG)
    3712
    3813ENABLE_TESTING()
     
    4015ADD_SUBDIRECTORY(lemon)
    4116ADD_SUBDIRECTORY(demo)
    42 ADD_SUBDIRECTORY(tools)
    4317ADD_SUBDIRECTORY(doc)
    4418ADD_SUBDIRECTORY(test)
    4519
    4620IF(WIN32)
     21  INSTALL(FILES ${CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico
     22    DESTINATION bin)
     23ENDIF(WIN32)
     24
     25IF(WIN32)
    4726  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
    48   SET(CPACK_PACKAGE_VENDOR "EGRES")
     27  SET(CPACK_PACKAGE_VENDOR
     28    "EGRES - Egervary Research Group on Combinatorial Optimization")
    4929  SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
    5030    "LEMON - Library of Efficient Models and Optimization in Networks")
     
    5838    "${PROJECT_NAME} ${PROJECT_VERSION}")
    5939
    60   SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
     40  # Variables to generate a component-based installer.
     41  #SET(CPACK_COMPONENTS_ALL headers library html_documentation)
    6142
    62   SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
    63   SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
    64   SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities")
    65   SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
     43  #SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
     44  #SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Static library")
     45  #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
    6646
    67   SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
    68     "C++ header files")
    69   SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
    70     "DLL and import library")
    71   SET(CPACK_COMPONENT_BIN_DESCRIPTION
    72     "Command line utilities")
    73   SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
    74     "Doxygen generated documentation")
     47  #SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
     48  #  "C++ header files for use with the LEMON library")
     49  #SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
     50  #  "Static library used to build programs with LEMON")
     51  #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
     52  #  "Doxygen generated documentation")
    7553
    76   SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
     54  #SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
    7755
    78   SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
    79   SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
    80   SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
     56  #SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
     57  #SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
     58  #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
    8159
    82   SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
    83     "Components needed to develop software using LEMON")
    84   SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
    85     "Documentation of LEMON")
     60  #SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
     61  #  "Components needed to develop software using LEMON")
     62  #SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
     63  #  "Documentation of LEMON")
    8664
    87   SET(CPACK_ALL_INSTALL_TYPES Full Developer)
     65  #SET(CPACK_ALL_INSTALL_TYPES Full Developer)
    8866
    89   SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
    90   SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
    91   SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
     67  #SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
     68  #SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
     69  #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
    9270
    9371  SET(CPACK_GENERATOR "NSIS")
     
    10179  SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")
    10280  SET(CPACK_NSIS_CREATE_ICONS_EXTRA "
    103     CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\share\\\\doc\\\\index.html\\\"
     81    CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\doc\\\\index.html\\\"
    10482    ")
    10583  SET(CPACK_NSIS_DELETE_ICONS_EXTRA "
  • LICENSE

    r463 r107  
    22copyright/license.
    33
    4 Copyright (C) 2003-2009 Egervary Jeno Kombinatorikus Optimalizalasi
     4Copyright (C) 2003-2008 Egervary Jeno Kombinatorikus Optimalizalasi
    55Kutatocsoport (Egervary Combinatorial Optimization Research Group,
    66EGRES).
  • Makefile.am

    r555 r375  
    1313        m4/lx_check_soplex.m4 \
    1414        CMakeLists.txt \
    15         cmake/FindGhostscript.cmake \
    16         cmake/FindGLPK.cmake \
    17         cmake/version.cmake.in \
    18         cmake/version.cmake \
    19         cmake/nsis/lemon.ico \
    20         cmake/nsis/uninstall.ico
     15        cmake
    2116
    2217pkgconfigdir = $(libdir)/pkgconfig
  • cmake/FindGhostscript.cmake

    r520 r225  
    44  NAMES gs gswin32c
    55  PATHS "$ENV{ProgramFiles}/gs"
    6   PATH_SUFFIXES gs8.61/bin gs8.62/bin gs8.63/bin gs8.64/bin gs8.65/bin
     6  PATH_SUFFIXES gs8.61/bin gs8.62/bin
    77  DOC "Ghostscript: PostScript and PDF language interpreter and previewer."
    88)
  • configure.ac

    r564 r375  
    2222dnl Do compilation tests using the C++ compiler.
    2323AC_LANG([C++])
    24 
    25 dnl Check the existence of long long type.
    26 AC_CHECK_TYPE(long long, [long_long_found=yes], [long_long_found=no])
    27 if test x"$long_long_found" = x"yes"; then
    28   AC_DEFINE([HAVE_LONG_LONG], [1], [Define to 1 if you have long long.])
    29 fi
    3024
    3125dnl Checks for programs.
     
    5751
    5852dnl Checks for libraries.
    59 LX_CHECK_GLPK
    60 LX_CHECK_CPLEX
    61 LX_CHECK_SOPLEX
    62 LX_CHECK_CLP
    63 
    64 AM_CONDITIONAL([HAVE_LP], [test x"$lx_lp_found" = x"yes"])
    65 AM_CONDITIONAL([HAVE_MIP], [test x"$lx_mip_found" = x"yes"])
     53#LX_CHECK_GLPK
     54#LX_CHECK_CPLEX
     55#LX_CHECK_SOPLEX
    6656
    6757dnl Disable/enable building the demo programs.
     
    10797dnl Add dependencies on files generated by configure.
    10898AC_SUBST([CONFIG_STATUS_DEPENDENCIES],
    109   ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in'])
     99  ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/lemon/lemon.pc.in'])
    110100
    111101AC_CONFIG_FILES([
    112102Makefile
    113 cmake/version.cmake
    114103doc/Doxyfile
    115104lemon/lemon.pc
     
    126115echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
    127116echo
    128 echo Compiler supports long long... : $long_long_found
    129 echo
    130 echo GLPK support.................. : $lx_glpk_found
    131 echo CPLEX support................. : $lx_cplex_found
    132 echo SOPLEX support................ : $lx_soplex_found
    133 echo CLP support................... : $lx_clp_found
    134 echo
     117#echo GLPK support.................. : $lx_glpk_found
     118#echo CPLEX support................. : $lx_cplex_found
     119#echo SOPLEX support................ : $lx_soplex_found
     120#echo
    135121echo Build demo programs........... : $enable_demo
    136122echo Build additional tools........ : $enable_tools
  • demo/CMakeLists.txt

    r498 r225  
    1 INCLUDE_DIRECTORIES(
    2   ${CMAKE_SOURCE_DIR}
    3   ${CMAKE_BINARY_DIR}
    4 )
     1INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})
    52
    63LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
  • demo/arg_parser_demo.cc

    r463 r311  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • demo/graph_to_eps_demo.cc

    r463 r313  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8686    coords(coords).
    8787    title("Sample .eps figure").
    88     copyright("(C) 2003-2009 LEMON Project").
     88    copyright("(C) 2003-2008 LEMON Project").
    8989    run();
    9090
     
    9393    coords(coords).
    9494    title("Sample .eps figure").
    95     copyright("(C) 2003-2009 LEMON Project").
     95    copyright("(C) 2003-2008 LEMON Project").
    9696    absoluteNodeSizes().absoluteArcWidths().
    9797    nodeScale(2).nodeSizes(sizes).
     
    106106  graphToEps(g,"graph_to_eps_demo_out_3_arr.eps").
    107107    title("Sample .eps figure (with arrowheads)").
    108     copyright("(C) 2003-2009 LEMON Project").
     108    copyright("(C) 2003-2008 LEMON Project").
    109109    absoluteNodeSizes().absoluteArcWidths().
    110110    nodeColors(composeMap(palette,colors)).
     
    133133  graphToEps(g,"graph_to_eps_demo_out_4_par.eps").
    134134    title("Sample .eps figure (parallel arcs)").
    135     copyright("(C) 2003-2009 LEMON Project").
     135    copyright("(C) 2003-2008 LEMON Project").
    136136    absoluteNodeSizes().absoluteArcWidths().
    137137    nodeShapes(shapes).
     
    148148  graphToEps(g,"graph_to_eps_demo_out_5_par_arr.eps").
    149149    title("Sample .eps figure (parallel arcs and arrowheads)").
    150     copyright("(C) 2003-2009 LEMON Project").
     150    copyright("(C) 2003-2008 LEMON Project").
    151151    absoluteNodeSizes().absoluteArcWidths().
    152152    nodeScale(2).nodeSizes(sizes).
     
    164164  graphToEps(g,"graph_to_eps_demo_out_6_par_arr_a4.eps").
    165165    title("Sample .eps figure (fits to A4)").
    166     copyright("(C) 2003-2009 LEMON Project").
     166    copyright("(C) 2003-2008 LEMON Project").
    167167    scaleToA4().
    168168    absoluteNodeSizes().absoluteArcWidths().
     
    194194    scale(60).
    195195    title("Sample .eps figure (Palette demo)").
    196     copyright("(C) 2003-2009 LEMON Project").
     196    copyright("(C) 2003-2008 LEMON Project").
    197197    coords(hcoords).
    198198    absoluteNodeSizes().absoluteArcWidths().
  • demo/lgf_demo.cc

    r463 r294  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • doc/CMakeLists.txt

    r565 r347  
    1010
    1111IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
    12   FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)
    1312  IF(UNIX)
    1413    ADD_CUSTOM_TARGET(html
     
    3736      WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR})
    3837  ENDIF(UNIX)
    39   INSTALL(
    40     DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
    41     DESTINATION share/doc
    42     COMPONENT html_documentation)
    4338ENDIF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
     39
     40INSTALL(
     41  DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
     42  DESTINATION doc
     43  COMPONENT html_documentation)
  • doc/coding_style.dox

    r463 r210  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • doc/dirs.dox

    r463 r318  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    7272\brief Auxiliary tools for implementation.
    7373
    74 This directory contains some auxiliary classes for implementing graphs,
     74This directory contains some auxiliary classes for implementing graphs, 
    7575maps and some other classes.
    7676As a user you typically don't have to deal with these files.
  • doc/groups.dox

    r478 r434  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6363
    6464/**
    65 @defgroup graph_adaptors Adaptor Classes for Graphs
     65@defgroup graph_adaptors Adaptor Classes for graphs
    6666@ingroup graphs
    67 \brief Adaptor classes for digraphs and graphs
    68 
    69 This group contains several useful adaptor classes for digraphs and graphs.
     67\brief This group contains several adaptor classes for digraphs and graphs
    7068
    7169The main parts of LEMON are the different graph structures, generic
    72 graph algorithms, graph concepts, which couple them, and graph
     70graph algorithms, graph concepts which couple these, and graph
    7371adaptors. While the previous notions are more or less clear, the
    7472latter one needs further explanation. Graph adaptors are graph classes
     
    7674
    7775A short example makes this much clearer.  Suppose that we have an
    78 instance \c g of a directed graph type, say ListDigraph and an algorithm
     76instance \c g of a directed graph type say ListDigraph and an algorithm
    7977\code
    8078template <typename Digraph>
     
    8482(in time or in memory usage) to copy \c g with the reversed
    8583arcs.  In this case, an adaptor class is used, which (according
    86 to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
    87 The adaptor uses the original digraph structure and digraph operations when
    88 methods of the reversed oriented graph are called.  This means that the adaptor
    89 have minor memory usage, and do not perform sophisticated algorithmic
     84to LEMON digraph concepts) works as a digraph.  The adaptor uses the
     85original digraph structure and digraph operations when methods of the
     86reversed oriented graph are called.  This means that the adaptor have
     87minor memory usage, and do not perform sophisticated algorithmic
    9088actions.  The purpose of it is to give a tool for the cases when a
    9189graph have to be used in a specific alteration.  If this alteration is
    92 obtained by a usual construction like filtering the node or the arc set or
     90obtained by a usual construction like filtering the arc-set or
    9391considering a new orientation, then an adaptor is worthwhile to use.
    9492To come back to the reverse oriented graph, in this situation
     
    9997\code
    10098ListDigraph g;
    101 ReverseDigraph<ListDigraph> rg(g);
     99ReverseDigraph<ListGraph> rg(g);
    102100int result = algorithm(rg);
    103101\endcode
    104 During running the algorithm, the original digraph \c g is untouched.
    105 This techniques give rise to an elegant code, and based on stable
     102After running the algorithm, the original graph \c g is untouched.
     103This techniques gives rise to an elegant code, and based on stable
    106104graph adaptors, complex algorithms can be implemented easily.
    107105
    108 In flow, circulation and matching problems, the residual
     106In flow, circulation and bipartite matching problems, the residual
    109107graph is of particular importance. Combining an adaptor implementing
    110 this with shortest path algorithms or minimum mean cycle algorithms,
     108this, shortest path algorithms and minimum mean cycle algorithms,
    111109a range of weighted and cardinality optimization algorithms can be
    112110obtained. For other examples, the interested user is referred to the
     
    115113The behavior of graph adaptors can be very different. Some of them keep
    116114capabilities of the original graph while in other cases this would be
    117 meaningless. This means that the concepts that they meet depend
    118 on the graph adaptor, and the wrapped graph.
    119 For example, if an arc of a reversed digraph is deleted, this is carried
    120 out by deleting the corresponding arc of the original digraph, thus the
    121 adaptor modifies the original digraph.
    122 However in case of a residual digraph, this operation has no sense.
    123 
     115meaningless. This means that the concepts that they are models of depend
     116on the graph adaptor, and the wrapped graph(s).
     117If an arc of \c rg is deleted, this is carried out by deleting the
     118corresponding arc of \c g, thus the adaptor modifies the original graph.
     119
     120But for a residual graph, this operation has no sense.
    124121Let us stand one more example here to simplify your work.
    125 ReverseDigraph has constructor
     122RevGraphAdaptor has constructor
    126123\code
    127124ReverseDigraph(Digraph& digraph);
    128125\endcode
    129 This means that in a situation, when a <tt>const %ListDigraph&</tt>
     126This means that in a situation, when a <tt>const ListDigraph&</tt>
    130127reference to a graph is given, then it have to be instantiated with
    131 <tt>Digraph=const %ListDigraph</tt>.
     128<tt>Digraph=const ListDigraph</tt>.
    132129\code
    133130int algorithm1(const ListDigraph& g) {
    134   ReverseDigraph<const ListDigraph> rg(g);
     131  RevGraphAdaptor<const ListDigraph> rg(g);
    135132  return algorithm2(rg);
    136133}
  • doc/lgf.dox

    r463 r313  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • doc/license.dox

    r463 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • doc/mainpage.dox

    r463 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • doc/migration.dox

    r463 r355  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • doc/named-param.dox

    r463 r269  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • doc/namespaces.dox

    r463 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • doc/template.h

    r463 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/CMakeLists.txt

    r562 r225  
    1 INCLUDE_DIRECTORIES(
    2   ${CMAKE_SOURCE_DIR}
    3   ${CMAKE_BINARY_DIR}
    4 )
     1INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})
    52
    6 CONFIGURE_FILE(
    7   ${CMAKE_CURRENT_SOURCE_DIR}/config.h.cmake
    8   ${CMAKE_CURRENT_BINARY_DIR}/config.h
    9 )
    10 
    11 SET(LEMON_SOURCES
     3ADD_LIBRARY(lemon
    124  arg_parser.cc
    135  base.cc
    146  color.cc
    15   lp_base.cc
    16   lp_skeleton.cc
    17   random.cc
    18   bits/windows.cc
    19 )
    20 
    21 IF(HAVE_GLPK)
    22   SET(LEMON_SOURCES ${LEMON_SOURCES} glpk.cc)
    23   INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIR})
    24   IF(WIN32)
    25     INSTALL(FILES ${GLPK_BIN_DIR}/glpk.dll DESTINATION bin)
    26     INSTALL(FILES ${GLPK_BIN_DIR}/libltdl3.dll DESTINATION bin)
    27     INSTALL(FILES ${GLPK_BIN_DIR}/zlib1.dll DESTINATION bin)
    28   ENDIF(WIN32)
    29 ENDIF(HAVE_GLPK)
    30 
    31 ADD_LIBRARY(lemon ${LEMON_SOURCES})
     7  random.cc)
    328
    339INSTALL(
  • lemon/Makefile.am

    r575 r522  
    88
    99lemon_libemon_la_SOURCES = \
    10         lemon/arg_parser.cc \
    11         lemon/base.cc \
    12         lemon/color.cc \
    13         lemon/lp_base.cc \
    14         lemon/lp_skeleton.cc \
    15         lemon/random.cc \
    16         lemon/bits/windows.cc
     10        lemon/arg_parser.cc \
     11        lemon/base.cc \
     12        lemon/color.cc \
     13        lemon/random.cc
    1714
    18 
    19 lemon_libemon_la_CXXFLAGS = \
    20         $(GLPK_CFLAGS) \
    21         $(CPLEX_CFLAGS) \
    22         $(SOPLEX_CXXFLAGS) \
    23         $(CLP_CXXFLAGS)
    24 
    25 lemon_libemon_la_LDFLAGS = \
    26         $(GLPK_LIBS) \
    27         $(CPLEX_LIBS) \
    28         $(SOPLEX_LIBS) \
    29         $(CLP_LIBS)
    30 
    31 if HAVE_GLPK
    32 lemon_libemon_la_SOURCES += lemon/glpk.cc
    33 endif
    34 
    35 if HAVE_CPLEX
    36 lemon_libemon_la_SOURCES += lemon/cplex.cc
    37 endif
    38 
    39 if HAVE_SOPLEX
    40 lemon_libemon_la_SOURCES += lemon/soplex.cc
    41 endif
    42 
    43 if HAVE_CLP
    44 lemon_libemon_la_SOURCES += lemon/clp.cc
    45 endif
     15#lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS) $(AM_CXXFLAGS)
     16#lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
    4617
    4718lemon_HEADERS += \
    4819        lemon/adaptors.h \
    49         lemon/arg_parser.h \
     20        lemon/arg_parser.h \
    5021        lemon/assert.h \
    51         lemon/bfs.h \
    52         lemon/bin_heap.h \
    53         lemon/circulation.h \
    54         lemon/clp.h \
    55         lemon/color.h \
     22        lemon/bfs.h \
     23        lemon/bin_heap.h \
     24        lemon/circulation.h \
     25        lemon/color.h \
    5626        lemon/concept_check.h \
    57         lemon/connectivity.h \
    58         lemon/counter.h \
     27        lemon/counter.h \
    5928        lemon/core.h \
    60         lemon/cplex.h \
    61         lemon/dfs.h \
    62         lemon/dijkstra.h \
    63         lemon/dim2.h \
    64         lemon/dimacs.h \
    65         lemon/edge_set.h \
     29        lemon/dfs.h \
     30        lemon/dijkstra.h \
     31        lemon/dim2.h \
     32        lemon/dimacs.h \
    6633        lemon/elevator.h \
    6734        lemon/error.h \
    68         lemon/euler.h \
    6935        lemon/full_graph.h \
    70         lemon/glpk.h \
    71         lemon/graph_to_eps.h \
    72         lemon/grid_graph.h \
     36        lemon/graph_to_eps.h \
     37        lemon/grid_graph.h \
    7338        lemon/hypercube_graph.h \
    7439        lemon/kruskal.h \
     
    7641        lemon/lgf_reader.h \
    7742        lemon/lgf_writer.h \
    78         lemon/list_graph.h \
    79         lemon/lp.h \
    80         lemon/lp_base.h \
    81         lemon/lp_skeleton.h \
    8243        lemon/list_graph.h \
    8344        lemon/maps.h \
     
    8849        lemon/path.h \
    8950        lemon/preflow.h \
    90         lemon/radix_sort.h \
    91         lemon/random.h \
     51        lemon/random.h \
    9252        lemon/smart_graph.h \
    93         lemon/soplex.h \
    9453        lemon/suurballe.h \
    95         lemon/time_measure.h \
    96         lemon/tolerance.h \
    97         lemon/unionfind.h \
    98         lemon/bits/windows.h
     54        lemon/time_measure.h \
     55        lemon/tolerance.h \
     56        lemon/unionfind.h
    9957
    10058bits_HEADERS += \
     
    10260        lemon/bits/array_map.h \
    10361        lemon/bits/base_extender.h \
    104         lemon/bits/bezier.h \
     62        lemon/bits/bezier.h \
    10563        lemon/bits/default_map.h \
    106         lemon/bits/edge_set_extender.h \
    107         lemon/bits/enable_if.h \
     64        lemon/bits/enable_if.h \
    10865        lemon/bits/graph_adaptor_extender.h \
    10966        lemon/bits/graph_extender.h \
    11067        lemon/bits/map_extender.h \
    11168        lemon/bits/path_dump.h \
    112         lemon/bits/solver_bits.h \
    11369        lemon/bits/traits.h \
    11470        lemon/bits/variant.h \
  • lemon/adaptors.h

    r566 r432  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2222/// \ingroup graph_adaptors
    2323/// \file
    24 /// \brief Adaptor classes for digraphs and graphs
     24/// \brief Several graph adaptors
    2525///
    2626/// This file contains several useful adaptors for digraphs and graphs.
     
    3131
    3232#include <lemon/bits/graph_adaptor_extender.h>
    33 #include <lemon/bits/map_extender.h>
    3433#include <lemon/tolerance.h>
    3534
     
    3837namespace lemon {
    3938
    40 #ifdef _MSC_VER
    41 #define LEMON_SCOPE_FIX(OUTER, NESTED) OUTER::NESTED
    42 #else
    43 #define LEMON_SCOPE_FIX(OUTER, NESTED) typename OUTER::template NESTED
    44 #endif
    45 
    46   template<typename DGR>
     39  template<typename _Digraph>
    4740  class DigraphAdaptorBase {
    4841  public:
    49     typedef DGR Digraph;
     42    typedef _Digraph Digraph;
    5043    typedef DigraphAdaptorBase Adaptor;
     44    typedef Digraph ParentDigraph;
    5145
    5246  protected:
    53     DGR* _digraph;
     47    Digraph* _digraph;
    5448    DigraphAdaptorBase() : _digraph(0) { }
    55     void initialize(DGR& digraph) { _digraph = &digraph; }
    56 
    57   public:
    58     DigraphAdaptorBase(DGR& digraph) : _digraph(&digraph) { }
    59 
    60     typedef typename DGR::Node Node;
    61     typedef typename DGR::Arc Arc;
     49    void setDigraph(Digraph& digraph) { _digraph = &digraph; }
     50
     51  public:
     52    DigraphAdaptorBase(Digraph& digraph) : _digraph(&digraph) { }
     53
     54    typedef typename Digraph::Node Node;
     55    typedef typename Digraph::Arc Arc;
    6256
    6357    void first(Node& i) const { _digraph->first(i); }
     
    7468    Node target(const Arc& a) const { return _digraph->target(a); }
    7569
    76     typedef NodeNumTagIndicator<DGR> NodeNumTag;
     70    typedef NodeNumTagIndicator<Digraph> NodeNumTag;
    7771    int nodeNum() const { return _digraph->nodeNum(); }
    7872
    79     typedef ArcNumTagIndicator<DGR> ArcNumTag;
     73    typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
    8074    int arcNum() const { return _digraph->arcNum(); }
    8175
    82     typedef FindArcTagIndicator<DGR> FindArcTag;
    83     Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const {
     76    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
     77    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
    8478      return _digraph->findArc(u, v, prev);
    8579    }
     
    8882    Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
    8983
    90     void erase(const Node& n) { _digraph->erase(n); }
    91     void erase(const Arc& a) { _digraph->erase(a); }
    92 
    93     void clear() { _digraph->clear(); }
     84    void erase(const Node& n) const { _digraph->erase(n); }
     85    void erase(const Arc& a) const { _digraph->erase(a); }
     86
     87    void clear() const { _digraph->clear(); }
    9488
    9589    int id(const Node& n) const { return _digraph->id(n); }
     
    10296    int maxArcId() const { return _digraph->maxArcId(); }
    10397
    104     typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
     98    typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
    10599    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
    106100
    107     typedef typename ItemSetTraits<DGR, Arc>::ItemNotifier ArcNotifier;
     101    typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier;
    108102    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
    109103
    110     template <typename V>
    111     class NodeMap : public DGR::template NodeMap<V> {
    112     public:
    113 
    114       typedef typename DGR::template NodeMap<V> Parent;
     104    template <typename _Value>
     105    class NodeMap : public Digraph::template NodeMap<_Value> {
     106    public:
     107
     108      typedef typename Digraph::template NodeMap<_Value> Parent;
    115109
    116110      explicit NodeMap(const Adaptor& adaptor)
    117111        : Parent(*adaptor._digraph) {}
    118112
    119       NodeMap(const Adaptor& adaptor, const V& value)
     113      NodeMap(const Adaptor& adaptor, const _Value& value)
    120114        : Parent(*adaptor._digraph, value) { }
    121115
     
    133127    };
    134128
    135     template <typename V>
    136     class ArcMap : public DGR::template ArcMap<V> {
    137     public:
    138 
    139       typedef typename DGR::template ArcMap<V> Parent;
    140 
    141       explicit ArcMap(const DigraphAdaptorBase<DGR>& adaptor)
     129    template <typename _Value>
     130    class ArcMap : public Digraph::template ArcMap<_Value> {
     131    public:
     132
     133      typedef typename Digraph::template ArcMap<_Value> Parent;
     134
     135      explicit ArcMap(const Adaptor& adaptor)
    142136        : Parent(*adaptor._digraph) {}
    143137
    144       ArcMap(const DigraphAdaptorBase<DGR>& adaptor, const V& value)
     138      ArcMap(const Adaptor& adaptor, const _Value& value)
    145139        : Parent(*adaptor._digraph, value) {}
    146140
     
    160154  };
    161155
    162   template<typename GR>
     156  template<typename _Graph>
    163157  class GraphAdaptorBase {
    164158  public:
    165     typedef GR Graph;
     159    typedef _Graph Graph;
     160    typedef Graph ParentGraph;
    166161
    167162  protected:
    168     GR* _graph;
     163    Graph* _graph;
    169164
    170165    GraphAdaptorBase() : _graph(0) {}
    171166
    172     void initialize(GR& graph) { _graph = &graph; }
    173 
    174   public:
    175     GraphAdaptorBase(GR& graph) : _graph(&graph) {}
    176 
    177     typedef typename GR::Node Node;
    178     typedef typename GR::Arc Arc;
    179     typedef typename GR::Edge Edge;
     167    void setGraph(Graph& graph) { _graph = &graph; }
     168
     169  public:
     170    GraphAdaptorBase(Graph& graph) : _graph(&graph) {}
     171
     172    typedef typename Graph::Node Node;
     173    typedef typename Graph::Arc Arc;
     174    typedef typename Graph::Edge Edge;
    180175
    181176    void first(Node& i) const { _graph->first(i); }
     
    204199    int nodeNum() const { return _graph->nodeNum(); }
    205200
    206     typedef ArcNumTagIndicator<Graph> ArcNumTag;
     201    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
    207202    int arcNum() const { return _graph->arcNum(); }
    208 
    209     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
    210203    int edgeNum() const { return _graph->edgeNum(); }
    211204
    212     typedef FindArcTagIndicator<Graph> FindArcTag;
    213     Arc findArc(const Node& u, const Node& v,
    214                 const Arc& prev = INVALID) const {
     205    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
     206    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
    215207      return _graph->findArc(u, v, prev);
    216208    }
    217 
    218     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
    219     Edge findEdge(const Node& u, const Node& v,
    220                   const Edge& prev = INVALID) const {
     209    Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) {
    221210      return _graph->findEdge(u, v, prev);
    222211    }
     
    245234    int maxEdgeId() const { return _graph->maxEdgeId(); }
    246235
    247     typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
     236    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
    248237    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
    249238
    250     typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;
     239    typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
    251240    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
    252241
    253     typedef typename ItemSetTraits<GR, Edge>::ItemNotifier EdgeNotifier;
     242    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
    254243    EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
    255244
    256     template <typename V>
    257     class NodeMap : public GR::template NodeMap<V> {
    258     public:
    259       typedef typename GR::template NodeMap<V> Parent;
    260       explicit NodeMap(const GraphAdaptorBase<GR>& adapter)
     245    template <typename _Value>
     246    class NodeMap : public Graph::template NodeMap<_Value> {
     247    public:
     248      typedef typename Graph::template NodeMap<_Value> Parent;
     249      explicit NodeMap(const GraphAdaptorBase<Graph>& adapter)
    261250        : Parent(*adapter._graph) {}
    262       NodeMap(const GraphAdaptorBase<GR>& adapter, const V& value)
     251      NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
    263252        : Parent(*adapter._graph, value) {}
    264253
     
    276265    };
    277266
    278     template <typename V>
    279     class ArcMap : public GR::template ArcMap<V> {
    280     public:
    281       typedef typename GR::template ArcMap<V> Parent;
    282       explicit ArcMap(const GraphAdaptorBase<GR>& adapter)
     267    template <typename _Value>
     268    class ArcMap : public Graph::template ArcMap<_Value> {
     269    public:
     270      typedef typename Graph::template ArcMap<_Value> Parent;
     271      explicit ArcMap(const GraphAdaptorBase<Graph>& adapter)
    283272        : Parent(*adapter._graph) {}
    284       ArcMap(const GraphAdaptorBase<GR>& adapter, const V& value)
     273      ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
    285274        : Parent(*adapter._graph, value) {}
    286275
     
    297286    };
    298287
    299     template <typename V>
    300     class EdgeMap : public GR::template EdgeMap<V> {
    301     public:
    302       typedef typename GR::template EdgeMap<V> Parent;
    303       explicit EdgeMap(const GraphAdaptorBase<GR>& adapter)
     288    template <typename _Value>
     289    class EdgeMap : public Graph::template EdgeMap<_Value> {
     290    public:
     291      typedef typename Graph::template EdgeMap<_Value> Parent;
     292      explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)
    304293        : Parent(*adapter._graph) {}
    305       EdgeMap(const GraphAdaptorBase<GR>& adapter, const V& value)
     294      EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
    306295        : Parent(*adapter._graph, value) {}
    307296
     
    320309  };
    321310
    322   template <typename DGR>
    323   class ReverseDigraphBase : public DigraphAdaptorBase<DGR> {
    324   public:
    325     typedef DGR Digraph;
    326     typedef DigraphAdaptorBase<DGR> Parent;
     311  template <typename _Digraph>
     312  class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> {
     313  public:
     314    typedef _Digraph Digraph;
     315    typedef DigraphAdaptorBase<_Digraph> Parent;
    327316  protected:
    328317    ReverseDigraphBase() : Parent() { }
     
    342331    Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
    343332
    344     typedef FindArcTagIndicator<DGR> FindArcTag;
     333    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
    345334    Arc findArc(const Node& u, const Node& v,
    346                 const Arc& prev = INVALID) const {
     335                const Arc& prev = INVALID) {
    347336      return Parent::findArc(v, u, prev);
    348337    }
     
    352341  /// \ingroup graph_adaptors
    353342  ///
    354   /// \brief Adaptor class for reversing the orientation of the arcs in
    355   /// a digraph.
    356   ///
    357   /// ReverseDigraph can be used for reversing the arcs in a digraph.
    358   /// It conforms to the \ref concepts::Digraph "Digraph" concept.
    359   ///
    360   /// The adapted digraph can also be modified through this adaptor
    361   /// by adding or removing nodes or arcs, unless the \c GR template
    362   /// parameter is set to be \c const.
    363   ///
    364   /// \tparam DGR The type of the adapted digraph.
    365   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    366   /// It can also be specified to be \c const.
    367   ///
    368   /// \note The \c Node and \c Arc types of this adaptor and the adapted
    369   /// digraph are convertible to each other.
    370   template<typename DGR>
    371 #ifdef DOXYGEN
    372   class ReverseDigraph {
    373 #else
     343  /// \brief A digraph adaptor which reverses the orientation of the arcs.
     344  ///
     345  /// ReverseDigraph reverses the arcs in the adapted digraph. The
     346  /// SubDigraph is conform to the \ref concepts::Digraph
     347  /// "Digraph concept".
     348  ///
     349  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
     350  /// "Digraph concept". The type can be specified to be const.
     351  template<typename _Digraph>
    374352  class ReverseDigraph :
    375     public DigraphAdaptorExtender<ReverseDigraphBase<DGR> > {
    376 #endif
    377   public:
    378     /// The type of the adapted digraph.
    379     typedef DGR Digraph;
    380     typedef DigraphAdaptorExtender<ReverseDigraphBase<DGR> > Parent;
     353    public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > {
     354  public:
     355    typedef _Digraph Digraph;
     356    typedef DigraphAdaptorExtender<
     357      ReverseDigraphBase<_Digraph> > Parent;
    381358  protected:
    382359    ReverseDigraph() { }
     
    385362    /// \brief Constructor
    386363    ///
    387     /// Creates a reverse digraph adaptor for the given digraph.
    388     explicit ReverseDigraph(DGR& digraph) {
    389       Parent::initialize(digraph);
     364    /// Creates a reverse digraph adaptor for the given digraph
     365    explicit ReverseDigraph(Digraph& digraph) {
     366      Parent::setDigraph(digraph);
    390367    }
    391368  };
    392369
    393   /// \brief Returns a read-only ReverseDigraph adaptor
    394   ///
    395   /// This function just returns a read-only \ref ReverseDigraph adaptor.
    396   /// \ingroup graph_adaptors
    397   /// \relates ReverseDigraph
    398   template<typename DGR>
    399   ReverseDigraph<const DGR> reverseDigraph(const DGR& digraph) {
    400     return ReverseDigraph<const DGR>(digraph);
     370  /// \brief Just gives back a reverse digraph adaptor
     371  ///
     372  /// Just gives back a reverse digraph adaptor
     373  template<typename Digraph>
     374  ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) {
     375    return ReverseDigraph<const Digraph>(digraph);
    401376  }
    402377
    403 
    404   template <typename DGR, typename NF, typename AF, bool ch = true>
    405   class SubDigraphBase : public DigraphAdaptorBase<DGR> {
    406   public:
    407     typedef DGR Digraph;
    408     typedef NF NodeFilterMap;
    409     typedef AF ArcFilterMap;
     378  template <typename _Digraph, typename _NodeFilterMap,
     379            typename _ArcFilterMap, bool _checked = true>
     380  class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {
     381  public:
     382    typedef _Digraph Digraph;
     383    typedef _NodeFilterMap NodeFilterMap;
     384    typedef _ArcFilterMap ArcFilterMap;
    410385
    411386    typedef SubDigraphBase Adaptor;
    412     typedef DigraphAdaptorBase<DGR> Parent;
     387    typedef DigraphAdaptorBase<_Digraph> Parent;
    413388  protected:
    414     NF* _node_filter;
    415     AF* _arc_filter;
     389    NodeFilterMap* _node_filter;
     390    ArcFilterMap* _arc_filter;
    416391    SubDigraphBase()
    417392      : Parent(), _node_filter(0), _arc_filter(0) { }
    418393
    419     void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
    420       Parent::initialize(digraph);
     394    void setNodeFilterMap(NodeFilterMap& node_filter) {
    421395      _node_filter = &node_filter;
    422       _arc_filter = &arc_filter;     
     396    }
     397    void setArcFilterMap(ArcFilterMap& arc_filter) {
     398      _arc_filter = &arc_filter;
    423399    }
    424400
     
    482458    }
    483459
    484     void status(const Node& n, bool v) const { _node_filter->set(n, v); }
    485     void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
    486 
    487     bool status(const Node& n) const { return (*_node_filter)[n]; }
    488     bool status(const Arc& a) const { return (*_arc_filter)[a]; }
     460    void hide(const Node& n) const { _node_filter->set(n, false); }
     461    void hide(const Arc& a) const { _arc_filter->set(a, false); }
     462
     463    void unHide(const Node& n) const { _node_filter->set(n, true); }
     464    void unHide(const Arc& a) const { _arc_filter->set(a, true); }
     465
     466    bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
     467    bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }
    489468
    490469    typedef False NodeNumTag;
    491     typedef False ArcNumTag;
    492 
    493     typedef FindArcTagIndicator<DGR> FindArcTag;
     470    typedef False EdgeNumTag;
     471
     472    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
    494473    Arc findArc(const Node& source, const Node& target,
    495                 const Arc& prev = INVALID) const {
     474                const Arc& prev = INVALID) {
    496475      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
    497476        return INVALID;
     
    504483    }
    505484
    506   public:
    507 
    508     template <typename V>
    509     class NodeMap
    510       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    511               LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
    512     public:
    513       typedef V Value;
    514       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    515             LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
    516 
    517       NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
    518         : Parent(adaptor) {}
    519       NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
    520         : Parent(adaptor, value) {}
     485    template <typename _Value>
     486    class NodeMap : public SubMapExtender<Adaptor,
     487      typename Parent::template NodeMap<_Value> > {
     488    public:
     489      typedef _Value Value;
     490      typedef SubMapExtender<Adaptor, typename Parent::
     491                             template NodeMap<Value> > MapParent;
     492
     493      NodeMap(const Adaptor& adaptor)
     494        : MapParent(adaptor) {}
     495      NodeMap(const Adaptor& adaptor, const Value& value)
     496        : MapParent(adaptor, value) {}
    521497
    522498    private:
     
    527503      template <typename CMap>
    528504      NodeMap& operator=(const CMap& cmap) {
    529         Parent::operator=(cmap);
     505        MapParent::operator=(cmap);
    530506        return *this;
    531507      }
    532508    };
    533509
    534     template <typename V>
    535     class ArcMap
    536       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    537               LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
    538     public:
    539       typedef V Value;
    540       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    541         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
    542 
    543       ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
    544         : Parent(adaptor) {}
    545       ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
    546         : Parent(adaptor, value) {}
     510    template <typename _Value>
     511    class ArcMap : public SubMapExtender<Adaptor,
     512      typename Parent::template ArcMap<_Value> > {
     513    public:
     514      typedef _Value Value;
     515      typedef SubMapExtender<Adaptor, typename Parent::
     516                             template ArcMap<Value> > MapParent;
     517
     518      ArcMap(const Adaptor& adaptor)
     519        : MapParent(adaptor) {}
     520      ArcMap(const Adaptor& adaptor, const Value& value)
     521        : MapParent(adaptor, value) {}
    547522
    548523    private:
     
    553528      template <typename CMap>
    554529      ArcMap& operator=(const CMap& cmap) {
    555         Parent::operator=(cmap);
     530        MapParent::operator=(cmap);
    556531        return *this;
    557532      }
     
    560535  };
    561536
    562   template <typename DGR, typename NF, typename AF>
    563   class SubDigraphBase<DGR, NF, AF, false>
    564     : public DigraphAdaptorBase<DGR> {
    565   public:
    566     typedef DGR Digraph;
    567     typedef NF NodeFilterMap;
    568     typedef AF ArcFilterMap;
     537  template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>
     538  class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>
     539    : public DigraphAdaptorBase<_Digraph> {
     540  public:
     541    typedef _Digraph Digraph;
     542    typedef _NodeFilterMap NodeFilterMap;
     543    typedef _ArcFilterMap ArcFilterMap;
    569544
    570545    typedef SubDigraphBase Adaptor;
    571546    typedef DigraphAdaptorBase<Digraph> Parent;
    572547  protected:
    573     NF* _node_filter;
    574     AF* _arc_filter;
     548    NodeFilterMap* _node_filter;
     549    ArcFilterMap* _arc_filter;
    575550    SubDigraphBase()
    576551      : Parent(), _node_filter(0), _arc_filter(0) { }
    577552
    578     void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
    579       Parent::initialize(digraph);
     553    void setNodeFilterMap(NodeFilterMap& node_filter) {
    580554      _node_filter = &node_filter;
    581       _arc_filter = &arc_filter;     
     555    }
     556    void setArcFilterMap(ArcFilterMap& arc_filter) {
     557      _arc_filter = &arc_filter;
    582558    }
    583559
     
    625601    }
    626602
    627     void status(const Node& n, bool v) const { _node_filter->set(n, v); }
    628     void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
    629 
    630     bool status(const Node& n) const { return (*_node_filter)[n]; }
    631     bool status(const Arc& a) const { return (*_arc_filter)[a]; }
     603    void hide(const Node& n) const { _node_filter->set(n, false); }
     604    void hide(const Arc& e) const { _arc_filter->set(e, false); }
     605
     606    void unHide(const Node& n) const { _node_filter->set(n, true); }
     607    void unHide(const Arc& e) const { _arc_filter->set(e, true); }
     608
     609    bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
     610    bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }
    632611
    633612    typedef False NodeNumTag;
    634     typedef False ArcNumTag;
    635 
    636     typedef FindArcTagIndicator<DGR> FindArcTag;
     613    typedef False EdgeNumTag;
     614
     615    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
    637616    Arc findArc(const Node& source, const Node& target,
    638                 const Arc& prev = INVALID) const {
     617                const Arc& prev = INVALID) {
    639618      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
    640619        return INVALID;
     
    647626    }
    648627
    649     template <typename V>
    650     class NodeMap
    651       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    652           LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
    653     public:
    654       typedef V Value;
    655       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    656         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
    657 
    658       NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
    659         : Parent(adaptor) {}
    660       NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
    661         : Parent(adaptor, value) {}
     628    template <typename _Value>
     629    class NodeMap : public SubMapExtender<Adaptor,
     630      typename Parent::template NodeMap<_Value> > {
     631    public:
     632      typedef _Value Value;
     633      typedef SubMapExtender<Adaptor, typename Parent::
     634                             template NodeMap<Value> > MapParent;
     635
     636      NodeMap(const Adaptor& adaptor)
     637        : MapParent(adaptor) {}
     638      NodeMap(const Adaptor& adaptor, const Value& value)
     639        : MapParent(adaptor, value) {}
    662640
    663641    private:
     
    668646      template <typename CMap>
    669647      NodeMap& operator=(const CMap& cmap) {
    670         Parent::operator=(cmap);
     648        MapParent::operator=(cmap);
    671649        return *this;
    672650      }
    673651    };
    674652
    675     template <typename V>
    676     class ArcMap
    677       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    678           LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
    679     public:
    680       typedef V Value;
    681       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    682           LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
    683 
    684       ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
    685         : Parent(adaptor) {}
    686       ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
    687         : Parent(adaptor, value) {}
     653    template <typename _Value>
     654    class ArcMap : public SubMapExtender<Adaptor,
     655      typename Parent::template ArcMap<_Value> > {
     656    public:
     657      typedef _Value Value;
     658      typedef SubMapExtender<Adaptor, typename Parent::
     659                             template ArcMap<Value> > MapParent;
     660
     661      ArcMap(const Adaptor& adaptor)
     662        : MapParent(adaptor) {}
     663      ArcMap(const Adaptor& adaptor, const Value& value)
     664        : MapParent(adaptor, value) {}
    688665
    689666    private:
     
    694671      template <typename CMap>
    695672      ArcMap& operator=(const CMap& cmap) {
    696         Parent::operator=(cmap);
     673        MapParent::operator=(cmap);
    697674        return *this;
    698675      }
     
    703680  /// \ingroup graph_adaptors
    704681  ///
    705   /// \brief Adaptor class for hiding nodes and arcs in a digraph
    706   ///
    707   /// SubDigraph can be used for hiding nodes and arcs in a digraph.
    708   /// A \c bool node map and a \c bool arc map must be specified, which
    709   /// define the filters for nodes and arcs.
    710   /// Only the nodes and arcs with \c true filter value are
    711   /// shown in the subdigraph. The arcs that are incident to hidden
    712   /// nodes are also filtered out.
    713   /// This adaptor conforms to the \ref concepts::Digraph "Digraph" concept.
    714   ///
    715   /// The adapted digraph can also be modified through this adaptor
    716   /// by adding or removing nodes or arcs, unless the \c GR template
    717   /// parameter is set to be \c const.
    718   ///
    719   /// \tparam DGR The type of the adapted digraph.
    720   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    721   /// It can also be specified to be \c const.
    722   /// \tparam NF The type of the node filter map.
    723   /// It must be a \c bool (or convertible) node map of the
    724   /// adapted digraph. The default type is
    725   /// \ref concepts::Digraph::NodeMap "DGR::NodeMap<bool>".
    726   /// \tparam AF The type of the arc filter map.
    727   /// It must be \c bool (or convertible) arc map of the
    728   /// adapted digraph. The default type is
    729   /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>".
    730   ///
    731   /// \note The \c Node and \c Arc types of this adaptor and the adapted
    732   /// digraph are convertible to each other.
     682  /// \brief An adaptor for hiding nodes and arcs in a digraph
     683  ///
     684  /// SubDigraph hides nodes and arcs in a digraph. A bool node map
     685  /// and a bool arc map must be specified, which define the filters
     686  /// for nodes and arcs. Just the nodes and arcs with true value are
     687  /// shown in the subdigraph. The SubDigraph is conform to the \ref
     688  /// concepts::Digraph "Digraph concept". If the \c _checked parameter
     689  /// is true, then the arcs incident to filtered nodes are also
     690  /// filtered out.
     691  ///
     692  /// \tparam _Digraph It must be conform to the \ref
     693  /// concepts::Digraph "Digraph concept". The type can be specified
     694  /// to const.
     695  /// \tparam _NodeFilterMap A bool valued node map of the the adapted digraph.
     696  /// \tparam _ArcFilterMap A bool valued arc map of the the adapted digraph.
     697  /// \tparam _checked If the parameter is false then the arc filtering
     698  /// is not checked with respect to node filter. Otherwise, each arc
     699  /// is automatically filtered, which is incident to a filtered node.
    733700  ///
    734701  /// \see FilterNodes
    735702  /// \see FilterArcs
    736 #ifdef DOXYGEN
    737   template<typename DGR, typename NF, typename AF>
    738   class SubDigraph {
    739 #else
    740   template<typename DGR,
    741            typename NF = typename DGR::template NodeMap<bool>,
    742            typename AF = typename DGR::template ArcMap<bool> >
    743   class SubDigraph :
    744     public DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> > {
    745 #endif
    746   public:
    747     /// The type of the adapted digraph.
    748     typedef DGR Digraph;
    749     /// The type of the node filter map.
    750     typedef NF NodeFilterMap;
    751     /// The type of the arc filter map.
    752     typedef AF ArcFilterMap;
    753 
    754     typedef DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> >
    755       Parent;
     703  template<typename _Digraph,
     704           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
     705           typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,
     706           bool _checked = true>
     707  class SubDigraph
     708    : public DigraphAdaptorExtender<
     709      SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > {
     710  public:
     711    typedef _Digraph Digraph;
     712    typedef _NodeFilterMap NodeFilterMap;
     713    typedef _ArcFilterMap ArcFilterMap;
     714
     715    typedef DigraphAdaptorExtender<
     716      SubDigraphBase<Digraph, NodeFilterMap, ArcFilterMap, _checked> >
     717    Parent;
    756718
    757719    typedef typename Parent::Node Node;
     
    764726    /// \brief Constructor
    765727    ///
    766     /// Creates a subdigraph for the given digraph with the
    767     /// given node and arc filter maps.
    768     SubDigraph(DGR& digraph, NF& node_filter, AF& arc_filter) {
    769       Parent::initialize(digraph, node_filter, arc_filter);
    770     }
    771 
    772     /// \brief Sets the status of the given node
    773     ///
    774     /// This function sets the status of the given node.
    775     /// It is done by simply setting the assigned value of \c n
    776     /// to \c v in the node filter map.
    777     void status(const Node& n, bool v) const { Parent::status(n, v); }
    778 
    779     /// \brief Sets the status of the given arc
    780     ///
    781     /// This function sets the status of the given arc.
    782     /// It is done by simply setting the assigned value of \c a
    783     /// to \c v in the arc filter map.
    784     void status(const Arc& a, bool v) const { Parent::status(a, v); }
    785 
    786     /// \brief Returns the status of the given node
    787     ///
    788     /// This function returns the status of the given node.
    789     /// It is \c true if the given node is enabled (i.e. not hidden).
    790     bool status(const Node& n) const { return Parent::status(n); }
    791 
    792     /// \brief Returns the status of the given arc
    793     ///
    794     /// This function returns the status of the given arc.
    795     /// It is \c true if the given arc is enabled (i.e. not hidden).
    796     bool status(const Arc& a) const { return Parent::status(a); }
    797 
    798     /// \brief Disables the given node
    799     ///
    800     /// This function disables the given node in the subdigraph,
    801     /// so the iteration jumps over it.
    802     /// It is the same as \ref status() "status(n, false)".
    803     void disable(const Node& n) const { Parent::status(n, false); }
    804 
    805     /// \brief Disables the given arc
    806     ///
    807     /// This function disables the given arc in the subdigraph,
    808     /// so the iteration jumps over it.
    809     /// It is the same as \ref status() "status(a, false)".
    810     void disable(const Arc& a) const { Parent::status(a, false); }
    811 
    812     /// \brief Enables the given node
    813     ///
    814     /// This function enables the given node in the subdigraph.
    815     /// It is the same as \ref status() "status(n, true)".
    816     void enable(const Node& n) const { Parent::status(n, true); }
    817 
    818     /// \brief Enables the given arc
    819     ///
    820     /// This function enables the given arc in the subdigraph.
    821     /// It is the same as \ref status() "status(a, true)".
    822     void enable(const Arc& a) const { Parent::status(a, true); }
     728    /// Creates a subdigraph for the given digraph with
     729    /// given node and arc map filters.
     730    SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,
     731               ArcFilterMap& arc_filter) {
     732      setDigraph(digraph);
     733      setNodeFilterMap(node_filter);
     734      setArcFilterMap(arc_filter);
     735    }
     736
     737    /// \brief Hides the node of the graph
     738    ///
     739    /// This function hides \c n in the digraph, i.e. the iteration
     740    /// jumps over it. This is done by simply setting the value of \c n
     741    /// to be false in the corresponding node-map.
     742    void hide(const Node& n) const { Parent::hide(n); }
     743
     744    /// \brief Hides the arc of the graph
     745    ///
     746    /// This function hides \c a in the digraph, i.e. the iteration
     747    /// jumps over it. This is done by simply setting the value of \c a
     748    /// to be false in the corresponding arc-map.
     749    void hide(const Arc& a) const { Parent::hide(a); }
     750
     751    /// \brief Unhides the node of the graph
     752    ///
     753    /// The value of \c n is set to be true in the node-map which stores
     754    /// hide information. If \c n was hidden previuosly, then it is shown
     755    /// again
     756    void unHide(const Node& n) const { Parent::unHide(n); }
     757
     758    /// \brief Unhides the arc of the graph
     759    ///
     760    /// The value of \c a is set to be true in the arc-map which stores
     761    /// hide information. If \c a was hidden previuosly, then it is shown
     762    /// again
     763    void unHide(const Arc& a) const { Parent::unHide(a); }
     764
     765    /// \brief Returns true if \c n is hidden.
     766    ///
     767    /// Returns true if \c n is hidden.
     768    ///
     769    bool hidden(const Node& n) const { return Parent::hidden(n); }
     770
     771    /// \brief Returns true if \c a is hidden.
     772    ///
     773    /// Returns true if \c a is hidden.
     774    ///
     775    bool hidden(const Arc& a) const { return Parent::hidden(a); }
    823776
    824777  };
    825778
    826   /// \brief Returns a read-only SubDigraph adaptor
    827   ///
    828   /// This function just returns a read-only \ref SubDigraph adaptor.
    829   /// \ingroup graph_adaptors
    830   /// \relates SubDigraph
    831   template<typename DGR, typename NF, typename AF>
    832   SubDigraph<const DGR, NF, AF>
    833   subDigraph(const DGR& digraph,
    834              NF& node_filter, AF& arc_filter) {
    835     return SubDigraph<const DGR, NF, AF>
    836       (digraph, node_filter, arc_filter);
     779  /// \brief Just gives back a subdigraph
     780  ///
     781  /// Just gives back a subdigraph
     782  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
     783  SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
     784  subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) {
     785    return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
     786      (digraph, nfm, afm);
    837787  }
    838788
    839   template<typename DGR, typename NF, typename AF>
    840   SubDigraph<const DGR, const NF, AF>
    841   subDigraph(const DGR& digraph,
    842              const NF& node_filter, AF& arc_filter) {
    843     return SubDigraph<const DGR, const NF, AF>
    844       (digraph, node_filter, arc_filter);
     789  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
     790  SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
     791  subDigraph(const Digraph& digraph,
     792             const NodeFilterMap& nfm, ArcFilterMap& afm) {
     793    return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
     794      (digraph, nfm, afm);
    845795  }
    846796
    847   template<typename DGR, typename NF, typename AF>
    848   SubDigraph<const DGR, NF, const AF>
    849   subDigraph(const DGR& digraph,
    850              NF& node_filter, const AF& arc_filter) {
    851     return SubDigraph<const DGR, NF, const AF>
    852       (digraph, node_filter, arc_filter);
     797  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
     798  SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
     799  subDigraph(const Digraph& digraph,
     800             NodeFilterMap& nfm, const ArcFilterMap& afm) {
     801    return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
     802      (digraph, nfm, afm);
    853803  }
    854804
    855   template<typename DGR, typename NF, typename AF>
    856   SubDigraph<const DGR, const NF, const AF>
    857   subDigraph(const DGR& digraph,
    858              const NF& node_filter, const AF& arc_filter) {
    859     return SubDigraph<const DGR, const NF, const AF>
    860       (digraph, node_filter, arc_filter);
     805  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
     806  SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap>
     807  subDigraph(const Digraph& digraph,
     808             const NodeFilterMap& nfm, const ArcFilterMap& afm) {
     809    return SubDigraph<const Digraph, const NodeFilterMap,
     810      const ArcFilterMap>(digraph, nfm, afm);
    861811  }
    862812
    863813
    864   template <typename GR, typename NF, typename EF, bool ch = true>
    865   class SubGraphBase : public GraphAdaptorBase<GR> {
    866   public:
    867     typedef GR Graph;
    868     typedef NF NodeFilterMap;
    869     typedef EF EdgeFilterMap;
    870 
     814  template <typename _Graph, typename NodeFilterMap,
     815            typename EdgeFilterMap, bool _checked = true>
     816  class SubGraphBase : public GraphAdaptorBase<_Graph> {
     817  public:
     818    typedef _Graph Graph;
    871819    typedef SubGraphBase Adaptor;
    872     typedef GraphAdaptorBase<GR> Parent;
     820    typedef GraphAdaptorBase<_Graph> Parent;
    873821  protected:
    874822
    875     NF* _node_filter;
    876     EF* _edge_filter;
     823    NodeFilterMap* _node_filter_map;
     824    EdgeFilterMap* _edge_filter_map;
    877825
    878826    SubGraphBase()
    879       : Parent(), _node_filter(0), _edge_filter(0) { }
    880 
    881     void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
    882       Parent::initialize(graph);
    883       _node_filter = &node_filter;
    884       _edge_filter = &edge_filter;
     827      : Parent(), _node_filter_map(0), _edge_filter_map(0) { }
     828
     829    void setNodeFilterMap(NodeFilterMap& node_filter_map) {
     830      _node_filter_map=&node_filter_map;
     831    }
     832    void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
     833      _edge_filter_map=&edge_filter_map;
    885834    }
    886835
     
    893842    void first(Node& i) const {
    894843      Parent::first(i);
    895       while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
     844      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
    896845    }
    897846
    898847    void first(Arc& i) const {
    899848      Parent::first(i);
    900       while (i!=INVALID && (!(*_edge_filter)[i]
    901                             || !(*_node_filter)[Parent::source(i)]
    902                             || !(*_node_filter)[Parent::target(i)]))
     849      while (i!=INVALID && (!(*_edge_filter_map)[i]
     850                            || !(*_node_filter_map)[Parent::source(i)]
     851                            || !(*_node_filter_map)[Parent::target(i)]))
    903852        Parent::next(i);
    904853    }
     
    906855    void first(Edge& i) const {
    907856      Parent::first(i);
    908       while (i!=INVALID && (!(*_edge_filter)[i]
    909                             || !(*_node_filter)[Parent::u(i)]
    910                             || !(*_node_filter)[Parent::v(i)]))
     857      while (i!=INVALID && (!(*_edge_filter_map)[i]
     858                            || !(*_node_filter_map)[Parent::u(i)]
     859                            || !(*_node_filter_map)[Parent::v(i)]))
    911860        Parent::next(i);
    912861    }
     
    914863    void firstIn(Arc& i, const Node& n) const {
    915864      Parent::firstIn(i, n);
    916       while (i!=INVALID && (!(*_edge_filter)[i]
    917                             || !(*_node_filter)[Parent::source(i)]))
     865      while (i!=INVALID && (!(*_edge_filter_map)[i]
     866                            || !(*_node_filter_map)[Parent::source(i)]))
    918867        Parent::nextIn(i);
    919868    }
     
    921870    void firstOut(Arc& i, const Node& n) const {
    922871      Parent::firstOut(i, n);
    923       while (i!=INVALID && (!(*_edge_filter)[i]
    924                             || !(*_node_filter)[Parent::target(i)]))
     872      while (i!=INVALID && (!(*_edge_filter_map)[i]
     873                            || !(*_node_filter_map)[Parent::target(i)]))
    925874        Parent::nextOut(i);
    926875    }
     
    928877    void firstInc(Edge& i, bool& d, const Node& n) const {
    929878      Parent::firstInc(i, d, n);
    930       while (i!=INVALID && (!(*_edge_filter)[i]
    931                             || !(*_node_filter)[Parent::u(i)]
    932                             || !(*_node_filter)[Parent::v(i)]))
     879      while (i!=INVALID && (!(*_edge_filter_map)[i]
     880                            || !(*_node_filter_map)[Parent::u(i)]
     881                            || !(*_node_filter_map)[Parent::v(i)]))
    933882        Parent::nextInc(i, d);
    934883    }
     
    936885    void next(Node& i) const {
    937886      Parent::next(i);
    938       while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
     887      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
    939888    }
    940889
    941890    void next(Arc& i) const {
    942891      Parent::next(i);
    943       while (i!=INVALID && (!(*_edge_filter)[i]
    944                             || !(*_node_filter)[Parent::source(i)]
    945                             || !(*_node_filter)[Parent::target(i)]))
     892      while (i!=INVALID && (!(*_edge_filter_map)[i]
     893                            || !(*_node_filter_map)[Parent::source(i)]
     894                            || !(*_node_filter_map)[Parent::target(i)]))
    946895        Parent::next(i);
    947896    }
     
    949898    void next(Edge& i) const {
    950899      Parent::next(i);
    951       while (i!=INVALID && (!(*_edge_filter)[i]
    952                             || !(*_node_filter)[Parent::u(i)]
    953                             || !(*_node_filter)[Parent::v(i)]))
     900      while (i!=INVALID && (!(*_edge_filter_map)[i]
     901                            || !(*_node_filter_map)[Parent::u(i)]
     902                            || !(*_node_filter_map)[Parent::v(i)]))
    954903        Parent::next(i);
    955904    }
     
    957906    void nextIn(Arc& i) const {
    958907      Parent::nextIn(i);
    959       while (i!=INVALID && (!(*_edge_filter)[i]
    960                             || !(*_node_filter)[Parent::source(i)]))
     908      while (i!=INVALID && (!(*_edge_filter_map)[i]
     909                            || !(*_node_filter_map)[Parent::source(i)]))
    961910        Parent::nextIn(i);
    962911    }
     
    964913    void nextOut(Arc& i) const {
    965914      Parent::nextOut(i);
    966       while (i!=INVALID && (!(*_edge_filter)[i]
    967                             || !(*_node_filter)[Parent::target(i)]))
     915      while (i!=INVALID && (!(*_edge_filter_map)[i]
     916                            || !(*_node_filter_map)[Parent::target(i)]))
    968917        Parent::nextOut(i);
    969918    }
     
    971920    void nextInc(Edge& i, bool& d) const {
    972921      Parent::nextInc(i, d);
    973       while (i!=INVALID && (!(*_edge_filter)[i]
    974                             || !(*_node_filter)[Parent::u(i)]
    975                             || !(*_node_filter)[Parent::v(i)]))
     922      while (i!=INVALID && (!(*_edge_filter_map)[i]
     923                            || !(*_node_filter_map)[Parent::u(i)]
     924                            || !(*_node_filter_map)[Parent::v(i)]))
    976925        Parent::nextInc(i, d);
    977926    }
    978927
    979     void status(const Node& n, bool v) const { _node_filter->set(n, v); }
    980     void status(const Edge& e, bool v) const { _edge_filter->set(e, v); }
    981 
    982     bool status(const Node& n) const { return (*_node_filter)[n]; }
    983     bool status(const Edge& e) const { return (*_edge_filter)[e]; }
     928    void hide(const Node& n) const { _node_filter_map->set(n, false); }
     929    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
     930
     931    void unHide(const Node& n) const { _node_filter_map->set(n, true); }
     932    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
     933
     934    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
     935    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
    984936
    985937    typedef False NodeNumTag;
    986     typedef False ArcNumTag;
    987938    typedef False EdgeNumTag;
    988939
    989     typedef FindArcTagIndicator<Graph> FindArcTag;
     940    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
    990941    Arc findArc(const Node& u, const Node& v,
    991                 const Arc& prev = INVALID) const {
    992       if (!(*_node_filter)[u] || !(*_node_filter)[v]) {
     942                const Arc& prev = INVALID) {
     943      if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
    993944        return INVALID;
    994945      }
    995946      Arc arc = Parent::findArc(u, v, prev);
    996       while (arc != INVALID && !(*_edge_filter)[arc]) {
     947      while (arc != INVALID && !(*_edge_filter_map)[arc]) {
    997948        arc = Parent::findArc(u, v, arc);
    998949      }
    999950      return arc;
    1000951    }
    1001 
    1002     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
    1003952    Edge findEdge(const Node& u, const Node& v,
    1004                   const Edge& prev = INVALID) const {
    1005       if (!(*_node_filter)[u] || !(*_node_filter)[v]) {
     953                  const Edge& prev = INVALID) {
     954      if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
    1006955        return INVALID;
    1007956      }
    1008957      Edge edge = Parent::findEdge(u, v, prev);
    1009       while (edge != INVALID && !(*_edge_filter)[edge]) {
     958      while (edge != INVALID && !(*_edge_filter_map)[edge]) {
    1010959        edge = Parent::findEdge(u, v, edge);
    1011960      }
     
    1013962    }
    1014963
    1015     template <typename V>
    1016     class NodeMap
    1017       : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    1018           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
    1019     public:
    1020       typedef V Value;
    1021       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    1022         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
    1023 
    1024       NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
    1025         : Parent(adaptor) {}
    1026       NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
    1027         : Parent(adaptor, value) {}
     964    template <typename _Value>
     965    class NodeMap : public SubMapExtender<Adaptor,
     966      typename Parent::template NodeMap<_Value> > {
     967    public:
     968      typedef _Value Value;
     969      typedef SubMapExtender<Adaptor, typename Parent::
     970                             template NodeMap<Value> > MapParent;
     971
     972      NodeMap(const Adaptor& adaptor)
     973        : MapParent(adaptor) {}
     974      NodeMap(const Adaptor& adaptor, const Value& value)
     975        : MapParent(adaptor, value) {}
    1028976
    1029977    private:
     
    1034982      template <typename CMap>
    1035983      NodeMap& operator=(const CMap& cmap) {
    1036         Parent::operator=(cmap);
     984        MapParent::operator=(cmap);
    1037985        return *this;
    1038986      }
    1039987    };
    1040988
    1041     template <typename V>
    1042     class ArcMap
    1043       : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    1044           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
    1045     public:
    1046       typedef V Value;
    1047       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    1048         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
    1049 
    1050       ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
    1051         : Parent(adaptor) {}
    1052       ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
    1053         : Parent(adaptor, value) {}
     989    template <typename _Value>
     990    class ArcMap : public SubMapExtender<Adaptor,
     991      typename Parent::template ArcMap<_Value> > {
     992    public:
     993      typedef _Value Value;
     994      typedef SubMapExtender<Adaptor, typename Parent::
     995                             template ArcMap<Value> > MapParent;
     996
     997      ArcMap(const Adaptor& adaptor)
     998        : MapParent(adaptor) {}
     999      ArcMap(const Adaptor& adaptor, const Value& value)
     1000        : MapParent(adaptor, value) {}
    10541001
    10551002    private:
     
    10601007      template <typename CMap>
    10611008      ArcMap& operator=(const CMap& cmap) {
    1062         Parent::operator=(cmap);
     1009        MapParent::operator=(cmap);
    10631010        return *this;
    10641011      }
    10651012    };
    10661013
    1067     template <typename V>
    1068     class EdgeMap
    1069       : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    1070         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
    1071     public:
    1072       typedef V Value;
    1073       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    1074         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
    1075 
    1076       EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
    1077         : Parent(adaptor) {}
    1078 
    1079       EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
    1080         : Parent(adaptor, value) {}
     1014    template <typename _Value>
     1015    class EdgeMap : public SubMapExtender<Adaptor,
     1016      typename Parent::template EdgeMap<_Value> > {
     1017    public:
     1018      typedef _Value Value;
     1019      typedef SubMapExtender<Adaptor, typename Parent::
     1020                             template EdgeMap<Value> > MapParent;
     1021
     1022      EdgeMap(const Adaptor& adaptor)
     1023        : MapParent(adaptor) {}
     1024
     1025      EdgeMap(const Adaptor& adaptor, const Value& value)
     1026        : MapParent(adaptor, value) {}
    10811027
    10821028    private:
     
    10871033      template <typename CMap>
    10881034      EdgeMap& operator=(const CMap& cmap) {
    1089         Parent::operator=(cmap);
     1035        MapParent::operator=(cmap);
    10901036        return *this;
    10911037      }
     
    10941040  };
    10951041
    1096   template <typename GR, typename NF, typename EF>
    1097   class SubGraphBase<GR, NF, EF, false>
    1098     : public GraphAdaptorBase<GR> {
    1099   public:
    1100     typedef GR Graph;
    1101     typedef NF NodeFilterMap;
    1102     typedef EF EdgeFilterMap;
    1103 
     1042  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
     1043  class SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
     1044    : public GraphAdaptorBase<_Graph> {
     1045  public:
     1046    typedef _Graph Graph;
    11041047    typedef SubGraphBase Adaptor;
    1105     typedef GraphAdaptorBase<GR> Parent;
     1048    typedef GraphAdaptorBase<_Graph> Parent;
    11061049  protected:
    1107     NF* _node_filter;
    1108     EF* _edge_filter;
    1109     SubGraphBase()
    1110           : Parent(), _node_filter(0), _edge_filter(0) { }
    1111 
    1112     void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
    1113       Parent::initialize(graph);
    1114       _node_filter = &node_filter;
    1115       _edge_filter = &edge_filter;
     1050    NodeFilterMap* _node_filter_map;
     1051    EdgeFilterMap* _edge_filter_map;
     1052    SubGraphBase() : Parent(),
     1053                     _node_filter_map(0), _edge_filter_map(0) { }
     1054
     1055    void setNodeFilterMap(NodeFilterMap& node_filter_map) {
     1056      _node_filter_map=&node_filter_map;
     1057    }
     1058    void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
     1059      _edge_filter_map=&edge_filter_map;
    11161060    }
    11171061
     
    11241068    void first(Node& i) const {
    11251069      Parent::first(i);
    1126       while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
     1070      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
    11271071    }
    11281072
    11291073    void first(Arc& i) const {
    11301074      Parent::first(i);
    1131       while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
     1075      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
    11321076    }
    11331077
    11341078    void first(Edge& i) const {
    11351079      Parent::first(i);
    1136       while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
     1080      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
    11371081    }
    11381082
    11391083    void firstIn(Arc& i, const Node& n) const {
    11401084      Parent::firstIn(i, n);
    1141       while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i);
     1085      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
    11421086    }
    11431087
    11441088    void firstOut(Arc& i, const Node& n) const {
    11451089      Parent::firstOut(i, n);
    1146       while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i);
     1090      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
    11471091    }
    11481092
    11491093    void firstInc(Edge& i, bool& d, const Node& n) const {
    11501094      Parent::firstInc(i, d, n);
    1151       while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d);
     1095      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
    11521096    }
    11531097
    11541098    void next(Node& i) const {
    11551099      Parent::next(i);
    1156       while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
     1100      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
    11571101    }
    11581102    void next(Arc& i) const {
    11591103      Parent::next(i);
    1160       while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
     1104      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
    11611105    }
    11621106    void next(Edge& i) const {
    11631107      Parent::next(i);
    1164       while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
     1108      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
    11651109    }
    11661110    void nextIn(Arc& i) const {
    11671111      Parent::nextIn(i);
    1168       while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i);
     1112      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
    11691113    }
    11701114
    11711115    void nextOut(Arc& i) const {
    11721116      Parent::nextOut(i);
    1173       while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i);
     1117      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
    11741118    }
    11751119    void nextInc(Edge& i, bool& d) const {
    11761120      Parent::nextInc(i, d);
    1177       while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d);
    1178     }
    1179 
    1180     void status(const Node& n, bool v) const { _node_filter->set(n, v); }
    1181     void status(const Edge& e, bool v) const { _edge_filter->set(e, v); }
    1182 
    1183     bool status(const Node& n) const { return (*_node_filter)[n]; }
    1184     bool status(const Edge& e) const { return (*_edge_filter)[e]; }
     1121      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
     1122    }
     1123
     1124    void hide(const Node& n) const { _node_filter_map->set(n, false); }
     1125    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
     1126
     1127    void unHide(const Node& n) const { _node_filter_map->set(n, true); }
     1128    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
     1129
     1130    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
     1131    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
    11851132
    11861133    typedef False NodeNumTag;
    1187     typedef False ArcNumTag;
    11881134    typedef False EdgeNumTag;
    11891135
    1190     typedef FindArcTagIndicator<Graph> FindArcTag;
     1136    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
    11911137    Arc findArc(const Node& u, const Node& v,
    1192                 const Arc& prev = INVALID) const {
     1138                const Arc& prev = INVALID) {
    11931139      Arc arc = Parent::findArc(u, v, prev);
    1194       while (arc != INVALID && !(*_edge_filter)[arc]) {
     1140      while (arc != INVALID && !(*_edge_filter_map)[arc]) {
    11951141        arc = Parent::findArc(u, v, arc);
    11961142      }
    11971143      return arc;
    11981144    }
    1199 
    1200     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
    12011145    Edge findEdge(const Node& u, const Node& v,
    1202                   const Edge& prev = INVALID) const {
     1146                  const Edge& prev = INVALID) {
    12031147      Edge edge = Parent::findEdge(u, v, prev);
    1204       while (edge != INVALID && !(*_edge_filter)[edge]) {
     1148      while (edge != INVALID && !(*_edge_filter_map)[edge]) {
    12051149        edge = Parent::findEdge(u, v, edge);
    12061150      }
     
    12081152    }
    12091153
    1210     template <typename V>
    1211     class NodeMap
    1212       : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    1213           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
    1214     public:
    1215       typedef V Value;
    1216       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    1217         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
    1218 
    1219       NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
    1220         : Parent(adaptor) {}
    1221       NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
    1222         : Parent(adaptor, value) {}
     1154    template <typename _Value>
     1155    class NodeMap : public SubMapExtender<Adaptor,
     1156      typename Parent::template NodeMap<_Value> > {
     1157    public:
     1158      typedef _Value Value;
     1159      typedef SubMapExtender<Adaptor, typename Parent::
     1160                             template NodeMap<Value> > MapParent;
     1161
     1162      NodeMap(const Adaptor& adaptor)
     1163        : MapParent(adaptor) {}
     1164      NodeMap(const Adaptor& adaptor, const Value& value)
     1165        : MapParent(adaptor, value) {}
    12231166
    12241167    private:
     
    12291172      template <typename CMap>
    12301173      NodeMap& operator=(const CMap& cmap) {
    1231         Parent::operator=(cmap);
     1174        MapParent::operator=(cmap);
    12321175        return *this;
    12331176      }
    12341177    };
    12351178
    1236     template <typename V>
    1237     class ArcMap
    1238       : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    1239           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
    1240     public:
    1241       typedef V Value;
    1242       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    1243         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
    1244 
    1245       ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
    1246         : Parent(adaptor) {}
    1247       ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
    1248         : Parent(adaptor, value) {}
     1179    template <typename _Value>
     1180    class ArcMap : public SubMapExtender<Adaptor,
     1181      typename Parent::template ArcMap<_Value> > {
     1182    public:
     1183      typedef _Value Value;
     1184      typedef SubMapExtender<Adaptor, typename Parent::
     1185                             template ArcMap<Value> > MapParent;
     1186
     1187      ArcMap(const Adaptor& adaptor)
     1188        : MapParent(adaptor) {}
     1189      ArcMap(const Adaptor& adaptor, const Value& value)
     1190        : MapParent(adaptor, value) {}
    12491191
    12501192    private:
     
    12551197      template <typename CMap>
    12561198      ArcMap& operator=(const CMap& cmap) {
    1257         Parent::operator=(cmap);
     1199        MapParent::operator=(cmap);
    12581200        return *this;
    12591201      }
    12601202    };
    12611203
    1262     template <typename V>
    1263     class EdgeMap
    1264       : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    1265         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
    1266     public:
    1267       typedef V Value;
    1268       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    1269                   LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
    1270 
    1271       EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
    1272         : Parent(adaptor) {}
    1273 
    1274       EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
    1275         : Parent(adaptor, value) {}
     1204    template <typename _Value>
     1205    class EdgeMap : public SubMapExtender<Adaptor,
     1206      typename Parent::template EdgeMap<_Value> > {
     1207    public:
     1208      typedef _Value Value;
     1209      typedef SubMapExtender<Adaptor, typename Parent::
     1210                             template EdgeMap<Value> > MapParent;
     1211
     1212      EdgeMap(const Adaptor& adaptor)
     1213        : MapParent(adaptor) {}
     1214
     1215      EdgeMap(const Adaptor& adaptor, const _Value& value)
     1216        : MapParent(adaptor, value) {}
    12761217
    12771218    private:
     
    12821223      template <typename CMap>
    12831224      EdgeMap& operator=(const CMap& cmap) {
    1284         Parent::operator=(cmap);
     1225        MapParent::operator=(cmap);
    12851226        return *this;
    12861227      }
     
    12911232  /// \ingroup graph_adaptors
    12921233  ///
    1293   /// \brief Adaptor class for hiding nodes and edges in an undirected
    1294   /// graph.
    1295   ///
    1296   /// SubGraph can be used for hiding nodes and edges in a graph.
    1297   /// A \c bool node map and a \c bool edge map must be specified, which
    1298   /// define the filters for nodes and edges.
    1299   /// Only the nodes and edges with \c true filter value are
    1300   /// shown in the subgraph. The edges that are incident to hidden
    1301   /// nodes are also filtered out.
    1302   /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
    1303   ///
    1304   /// The adapted graph can also be modified through this adaptor
    1305   /// by adding or removing nodes or edges, unless the \c GR template
    1306   /// parameter is set to be \c const.
    1307   ///
    1308   /// \tparam GR The type of the adapted graph.
    1309   /// It must conform to the \ref concepts::Graph "Graph" concept.
    1310   /// It can also be specified to be \c const.
    1311   /// \tparam NF The type of the node filter map.
    1312   /// It must be a \c bool (or convertible) node map of the
    1313   /// adapted graph. The default type is
    1314   /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".
    1315   /// \tparam EF The type of the edge filter map.
    1316   /// It must be a \c bool (or convertible) edge map of the
    1317   /// adapted graph. The default type is
    1318   /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
    1319   ///
    1320   /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the
    1321   /// adapted graph are convertible to each other.
     1234  /// \brief A graph adaptor for hiding nodes and edges in an
     1235  /// undirected graph.
     1236  ///
     1237  /// SubGraph hides nodes and edges in a graph. A bool node map and a
     1238  /// bool edge map must be specified, which define the filters for
     1239  /// nodes and edges. Just the nodes and edges with true value are
     1240  /// shown in the subgraph. The SubGraph is conform to the \ref
     1241  /// concepts::Graph "Graph concept". If the \c _checked parameter is
     1242  /// true, then the edges incident to filtered nodes are also
     1243  /// filtered out.
     1244  ///
     1245  /// \tparam _Graph It must be conform to the \ref
     1246  /// concepts::Graph "Graph concept". The type can be specified
     1247  /// to const.
     1248  /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
     1249  /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted graph.
     1250  /// \tparam _checked If the parameter is false then the edge filtering
     1251  /// is not checked with respect to node filter. Otherwise, each edge
     1252  /// is automatically filtered, which is incident to a filtered node.
    13221253  ///
    13231254  /// \see FilterNodes
    13241255  /// \see FilterEdges
    1325 #ifdef DOXYGEN
    1326   template<typename GR, typename NF, typename EF>
    1327   class SubGraph {
    1328 #else
    1329   template<typename GR,
    1330            typename NF = typename GR::template NodeMap<bool>,
    1331            typename EF = typename GR::template EdgeMap<bool> >
    1332   class SubGraph :
    1333     public GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> > {
    1334 #endif
    1335   public:
    1336     /// The type of the adapted graph.
    1337     typedef GR Graph;
    1338     /// The type of the node filter map.
    1339     typedef NF NodeFilterMap;
    1340     /// The type of the edge filter map.
    1341     typedef EF EdgeFilterMap;
    1342 
    1343     typedef GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> >
    1344       Parent;
     1256  template<typename _Graph, typename NodeFilterMap,
     1257           typename EdgeFilterMap, bool _checked = true>
     1258  class SubGraph
     1259    : public GraphAdaptorExtender<
     1260      SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, _checked> > {
     1261  public:
     1262    typedef _Graph Graph;
     1263    typedef GraphAdaptorExtender<
     1264      SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
    13451265
    13461266    typedef typename Parent::Node Node;
     
    13531273    /// \brief Constructor
    13541274    ///
    1355     /// Creates a subgraph for the given graph with the given node
    1356     /// and edge filter maps.
    1357     SubGraph(GR& graph, NF& node_filter, EF& edge_filter) {
    1358       initialize(graph, node_filter, edge_filter);
    1359     }
    1360 
    1361     /// \brief Sets the status of the given node
    1362     ///
    1363     /// This function sets the status of the given node.
    1364     /// It is done by simply setting the assigned value of \c n
    1365     /// to \c v in the node filter map.
    1366     void status(const Node& n, bool v) const { Parent::status(n, v); }
    1367 
    1368     /// \brief Sets the status of the given edge
    1369     ///
    1370     /// This function sets the status of the given edge.
    1371     /// It is done by simply setting the assigned value of \c e
    1372     /// to \c v in the edge filter map.
    1373     void status(const Edge& e, bool v) const { Parent::status(e, v); }
    1374 
    1375     /// \brief Returns the status of the given node
    1376     ///
    1377     /// This function returns the status of the given node.
    1378     /// It is \c true if the given node is enabled (i.e. not hidden).
    1379     bool status(const Node& n) const { return Parent::status(n); }
    1380 
    1381     /// \brief Returns the status of the given edge
    1382     ///
    1383     /// This function returns the status of the given edge.
    1384     /// It is \c true if the given edge is enabled (i.e. not hidden).
    1385     bool status(const Edge& e) const { return Parent::status(e); }
    1386 
    1387     /// \brief Disables the given node
    1388     ///
    1389     /// This function disables the given node in the subdigraph,
    1390     /// so the iteration jumps over it.
    1391     /// It is the same as \ref status() "status(n, false)".
    1392     void disable(const Node& n) const { Parent::status(n, false); }
    1393 
    1394     /// \brief Disables the given edge
    1395     ///
    1396     /// This function disables the given edge in the subgraph,
    1397     /// so the iteration jumps over it.
    1398     /// It is the same as \ref status() "status(e, false)".
    1399     void disable(const Edge& e) const { Parent::status(e, false); }
    1400 
    1401     /// \brief Enables the given node
    1402     ///
    1403     /// This function enables the given node in the subdigraph.
    1404     /// It is the same as \ref status() "status(n, true)".
    1405     void enable(const Node& n) const { Parent::status(n, true); }
    1406 
    1407     /// \brief Enables the given edge
    1408     ///
    1409     /// This function enables the given edge in the subgraph.
    1410     /// It is the same as \ref status() "status(e, true)".
    1411     void enable(const Edge& e) const { Parent::status(e, true); }
    1412 
     1275    /// Creates a subgraph for the given graph with given node and
     1276    /// edge map filters.
     1277    SubGraph(Graph& _graph, NodeFilterMap& node_filter_map,
     1278             EdgeFilterMap& edge_filter_map) {
     1279      setGraph(_graph);
     1280      setNodeFilterMap(node_filter_map);
     1281      setEdgeFilterMap(edge_filter_map);
     1282    }
     1283
     1284    /// \brief Hides the node of the graph
     1285    ///
     1286    /// This function hides \c n in the graph, i.e. the iteration
     1287    /// jumps over it. This is done by simply setting the value of \c n
     1288    /// to be false in the corresponding node-map.
     1289    void hide(const Node& n) const { Parent::hide(n); }
     1290
     1291    /// \brief Hides the edge of the graph
     1292    ///
     1293    /// This function hides \c e in the graph, i.e. the iteration
     1294    /// jumps over it. This is done by simply setting the value of \c e
     1295    /// to be false in the corresponding edge-map.
     1296    void hide(const Edge& e) const { Parent::hide(e); }
     1297
     1298    /// \brief Unhides the node of the graph
     1299    ///
     1300    /// The value of \c n is set to be true in the node-map which stores
     1301    /// hide information. If \c n was hidden previuosly, then it is shown
     1302    /// again
     1303    void unHide(const Node& n) const { Parent::unHide(n); }
     1304
     1305    /// \brief Unhides the edge of the graph
     1306    ///
     1307    /// The value of \c e is set to be true in the edge-map which stores
     1308    /// hide information. If \c e was hidden previuosly, then it is shown
     1309    /// again
     1310    void unHide(const Edge& e) const { Parent::unHide(e); }
     1311
     1312    /// \brief Returns true if \c n is hidden.
     1313    ///
     1314    /// Returns true if \c n is hidden.
     1315    ///
     1316    bool hidden(const Node& n) const { return Parent::hidden(n); }
     1317
     1318    /// \brief Returns true if \c e is hidden.
     1319    ///
     1320    /// Returns true if \c e is hidden.
     1321    ///
     1322    bool hidden(const Edge& e) const { return Parent::hidden(e); }
    14131323  };
    14141324
    1415   /// \brief Returns a read-only SubGraph adaptor
    1416   ///
    1417   /// This function just returns a read-only \ref SubGraph adaptor.
     1325  /// \brief Just gives back a subgraph
     1326  ///
     1327  /// Just gives back a subgraph
     1328  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
     1329  SubGraph<const Graph, NodeFilterMap, ArcFilterMap>
     1330  subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) {
     1331    return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm);
     1332  }
     1333
     1334  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
     1335  SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
     1336  subGraph(const Graph& graph,
     1337           const NodeFilterMap& nfm, ArcFilterMap& efm) {
     1338    return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
     1339      (graph, nfm, efm);
     1340  }
     1341
     1342  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
     1343  SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
     1344  subGraph(const Graph& graph,
     1345           NodeFilterMap& nfm, const ArcFilterMap& efm) {
     1346    return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
     1347      (graph, nfm, efm);
     1348  }
     1349
     1350  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
     1351  SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
     1352  subGraph(const Graph& graph,
     1353           const NodeFilterMap& nfm, const ArcFilterMap& efm) {
     1354    return SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
     1355      (graph, nfm, efm);
     1356  }
     1357
    14181358  /// \ingroup graph_adaptors
    1419   /// \relates SubGraph
    1420   template<typename GR, typename NF, typename EF>
    1421   SubGraph<const GR, NF, EF>
    1422   subGraph(const GR& graph, NF& node_filter, EF& edge_filter) {
    1423     return SubGraph<const GR, NF, EF>
    1424       (graph, node_filter, edge_filter);
    1425   }
    1426 
    1427   template<typename GR, typename NF, typename EF>
    1428   SubGraph<const GR, const NF, EF>
    1429   subGraph(const GR& graph, const NF& node_filter, EF& edge_filter) {
    1430     return SubGraph<const GR, const NF, EF>
    1431       (graph, node_filter, edge_filter);
    1432   }
    1433 
    1434   template<typename GR, typename NF, typename EF>
    1435   SubGraph<const GR, NF, const EF>
    1436   subGraph(const GR& graph, NF& node_filter, const EF& edge_filter) {
    1437     return SubGraph<const GR, NF, const EF>
    1438       (graph, node_filter, edge_filter);
    1439   }
    1440 
    1441   template<typename GR, typename NF, typename EF>
    1442   SubGraph<const GR, const NF, const EF>
    1443   subGraph(const GR& graph, const NF& node_filter, const EF& edge_filter) {
    1444     return SubGraph<const GR, const NF, const EF>
    1445       (graph, node_filter, edge_filter);
    1446   }
    1447 
    1448 
    1449   /// \ingroup graph_adaptors
    1450   ///
    1451   /// \brief Adaptor class for hiding nodes in a digraph or a graph.
    1452   ///
    1453   /// FilterNodes adaptor can be used for hiding nodes in a digraph or a
    1454   /// graph. A \c bool node map must be specified, which defines the filter
    1455   /// for the nodes. Only the nodes with \c true filter value and the
    1456   /// arcs/edges incident to nodes both with \c true filter value are shown
    1457   /// in the subgraph. This adaptor conforms to the \ref concepts::Digraph
    1458   /// "Digraph" concept or the \ref concepts::Graph "Graph" concept
    1459   /// depending on the \c GR template parameter.
    1460   ///
    1461   /// The adapted (di)graph can also be modified through this adaptor
    1462   /// by adding or removing nodes or arcs/edges, unless the \c GR template
    1463   /// parameter is set to be \c const.
    1464   ///
    1465   /// \tparam GR The type of the adapted digraph or graph.
    1466   /// It must conform to the \ref concepts::Digraph "Digraph" concept
    1467   /// or the \ref concepts::Graph "Graph" concept.
    1468   /// It can also be specified to be \c const.
    1469   /// \tparam NF The type of the node filter map.
    1470   /// It must be a \c bool (or convertible) node map of the
    1471   /// adapted (di)graph. The default type is
    1472   /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".
    1473   ///
    1474   /// \note The \c Node and <tt>Arc/Edge</tt> types of this adaptor and the
    1475   /// adapted (di)graph are convertible to each other.
     1359  ///
     1360  /// \brief An adaptor for hiding nodes from a digraph or a graph.
     1361  ///
     1362  /// FilterNodes adaptor hides nodes in a graph or a digraph. A bool
     1363  /// node map must be specified, which defines the filters for
     1364  /// nodes. Just the unfiltered nodes and the arcs or edges incident
     1365  /// to unfiltered nodes are shown in the subdigraph or subgraph. The
     1366  /// FilterNodes is conform to the \ref concepts::Digraph
     1367  /// "Digraph concept" or \ref concepts::Graph "Graph concept" depending
     1368  /// on the \c _Digraph template parameter. If the \c _checked
     1369  /// parameter is true, then the arc or edges incident to filtered nodes
     1370  /// are also filtered out.
     1371  ///
     1372  /// \tparam _Digraph It must be conform to the \ref
     1373  /// concepts::Digraph "Digraph concept" or \ref concepts::Graph
     1374  /// "Graph concept". The type can be specified to be const.
     1375  /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
     1376  /// \tparam _checked If the parameter is false then the arc or edge
     1377  /// filtering is not checked with respect to node filter. In this
     1378  /// case just isolated nodes can be filtered out from the
     1379  /// graph.
    14761380#ifdef DOXYGEN
    1477   template<typename GR, typename NF>
    1478   class FilterNodes {
     1381  template<typename _Digraph,
     1382           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
     1383           bool _checked = true>
    14791384#else
    1480   template<typename GR,
    1481            typename NF = typename GR::template NodeMap<bool>,
     1385  template<typename _Digraph,
     1386           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
     1387           bool _checked = true,
    14821388           typename Enable = void>
    1483   class FilterNodes :
    1484     public DigraphAdaptorExtender<
    1485       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
    1486                      true> > {
    14871389#endif
    1488   public:
    1489 
    1490     typedef GR Digraph;
    1491     typedef NF NodeFilterMap;
    1492 
    1493     typedef DigraphAdaptorExtender<
    1494       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
    1495                      true> > Parent;
     1390  class FilterNodes
     1391    : public SubDigraph<_Digraph, _NodeFilterMap,
     1392                        ConstMap<typename _Digraph::Arc, bool>, _checked> {
     1393  public:
     1394
     1395    typedef _Digraph Digraph;
     1396    typedef _NodeFilterMap NodeFilterMap;
     1397
     1398    typedef SubDigraph<Digraph, NodeFilterMap,
     1399                       ConstMap<typename Digraph::Arc, bool>, _checked>
     1400    Parent;
    14961401
    14971402    typedef typename Parent::Node Node;
    14981403
    14991404  protected:
    1500     ConstMap<typename Digraph::Arc, Const<bool, true> > const_true_map;
    1501 
    1502     FilterNodes() : const_true_map() {}
     1405    ConstMap<typename Digraph::Arc, bool> const_true_map;
     1406
     1407    FilterNodes() : const_true_map(true) {
     1408      Parent::setArcFilterMap(const_true_map);
     1409    }
    15031410
    15041411  public:
     
    15061413    /// \brief Constructor
    15071414    ///
    1508     /// Creates a subgraph for the given digraph or graph with the
     1415    /// Creates an adaptor for the given digraph or graph with
    15091416    /// given node filter map.
    1510     FilterNodes(GR& graph, NF& node_filter)
    1511       : Parent(), const_true_map()
    1512     {
    1513       Parent::initialize(graph, node_filter, const_true_map);
    1514     }
    1515 
    1516     /// \brief Sets the status of the given node
    1517     ///
    1518     /// This function sets the status of the given node.
    1519     /// It is done by simply setting the assigned value of \c n
    1520     /// to \c v in the node filter map.
    1521     void status(const Node& n, bool v) const { Parent::status(n, v); }
    1522 
    1523     /// \brief Returns the status of the given node
    1524     ///
    1525     /// This function returns the status of the given node.
    1526     /// It is \c true if the given node is enabled (i.e. not hidden).
    1527     bool status(const Node& n) const { return Parent::status(n); }
    1528 
    1529     /// \brief Disables the given node
    1530     ///
    1531     /// This function disables the given node, so the iteration
    1532     /// jumps over it.
    1533     /// It is the same as \ref status() "status(n, false)".
    1534     void disable(const Node& n) const { Parent::status(n, false); }
    1535 
    1536     /// \brief Enables the given node
    1537     ///
    1538     /// This function enables the given node.
    1539     /// It is the same as \ref status() "status(n, true)".
    1540     void enable(const Node& n) const { Parent::status(n, true); }
     1417    FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) :
     1418      Parent(), const_true_map(true) {
     1419      Parent::setDigraph(_digraph);
     1420      Parent::setNodeFilterMap(node_filter);
     1421      Parent::setArcFilterMap(const_true_map);
     1422    }
     1423
     1424    /// \brief Hides the node of the graph
     1425    ///
     1426    /// This function hides \c n in the digraph or graph, i.e. the iteration
     1427    /// jumps over it. This is done by simply setting the value of \c n
     1428    /// to be false in the corresponding node map.
     1429    void hide(const Node& n) const { Parent::hide(n); }
     1430
     1431    /// \brief Unhides the node of the graph
     1432    ///
     1433    /// The value of \c n is set to be true in the node-map which stores
     1434    /// hide information. If \c n was hidden previuosly, then it is shown
     1435    /// again
     1436    void unHide(const Node& n) const { Parent::unHide(n); }
     1437
     1438    /// \brief Returns true if \c n is hidden.
     1439    ///
     1440    /// Returns true if \c n is hidden.
     1441    ///
     1442    bool hidden(const Node& n) const { return Parent::hidden(n); }
    15411443
    15421444  };
    15431445
    1544   template<typename GR, typename NF>
    1545   class FilterNodes<GR, NF,
    1546                     typename enable_if<UndirectedTagIndicator<GR> >::type> :
    1547     public GraphAdaptorExtender<
    1548       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
    1549                    true> > {
    1550 
    1551   public:
    1552     typedef GR Graph;
    1553     typedef NF NodeFilterMap;
    1554     typedef GraphAdaptorExtender<
    1555       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
    1556                    true> > Parent;
     1446  template<typename _Graph, typename _NodeFilterMap, bool _checked>
     1447  class FilterNodes<_Graph, _NodeFilterMap, _checked,
     1448                    typename enable_if<UndirectedTagIndicator<_Graph> >::type>
     1449    : public SubGraph<_Graph, _NodeFilterMap,
     1450                      ConstMap<typename _Graph::Edge, bool>, _checked> {
     1451  public:
     1452    typedef _Graph Graph;
     1453    typedef _NodeFilterMap NodeFilterMap;
     1454    typedef SubGraph<Graph, NodeFilterMap,
     1455                     ConstMap<typename Graph::Edge, bool> > Parent;
    15571456
    15581457    typedef typename Parent::Node Node;
    15591458  protected:
    1560     ConstMap<typename GR::Edge, Const<bool, true> > const_true_map;
    1561 
    1562     FilterNodes() : const_true_map() {}
    1563 
    1564   public:
    1565 
    1566     FilterNodes(GR& graph, NodeFilterMap& node_filter) :
    1567       Parent(), const_true_map() {
    1568       Parent::initialize(graph, node_filter, const_true_map);
    1569     }
    1570 
    1571     void status(const Node& n, bool v) const { Parent::status(n, v); }
    1572     bool status(const Node& n) const { return Parent::status(n); }
    1573     void disable(const Node& n) const { Parent::status(n, false); }
    1574     void enable(const Node& n) const { Parent::status(n, true); }
     1459    ConstMap<typename Graph::Edge, bool> const_true_map;
     1460
     1461    FilterNodes() : const_true_map(true) {
     1462      Parent::setEdgeFilterMap(const_true_map);
     1463    }
     1464
     1465  public:
     1466
     1467    FilterNodes(Graph& _graph, NodeFilterMap& node_filter_map) :
     1468      Parent(), const_true_map(true) {
     1469      Parent::setGraph(_graph);
     1470      Parent::setNodeFilterMap(node_filter_map);
     1471      Parent::setEdgeFilterMap(const_true_map);
     1472    }
     1473
     1474    void hide(const Node& n) const { Parent::hide(n); }
     1475    void unHide(const Node& n) const { Parent::unHide(n); }
     1476    bool hidden(const Node& n) const { return Parent::hidden(n); }
    15751477
    15761478  };
    15771479
    15781480
    1579   /// \brief Returns a read-only FilterNodes adaptor
    1580   ///
    1581   /// This function just returns a read-only \ref FilterNodes adaptor.
     1481  /// \brief Just gives back a FilterNodes adaptor
     1482  ///
     1483  /// Just gives back a FilterNodes adaptor
     1484  template<typename Digraph, typename NodeFilterMap>
     1485  FilterNodes<const Digraph, NodeFilterMap>
     1486  filterNodes(const Digraph& digraph, NodeFilterMap& nfm) {
     1487    return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm);
     1488  }
     1489
     1490  template<typename Digraph, typename NodeFilterMap>
     1491  FilterNodes<const Digraph, const NodeFilterMap>
     1492  filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) {
     1493    return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm);
     1494  }
     1495
    15821496  /// \ingroup graph_adaptors
    1583   /// \relates FilterNodes
    1584   template<typename GR, typename NF>
    1585   FilterNodes<const GR, NF>
    1586   filterNodes(const GR& graph, NF& node_filter) {
    1587     return FilterNodes<const GR, NF>(graph, node_filter);
     1497  ///
     1498  /// \brief An adaptor for hiding arcs from a digraph.
     1499  ///
     1500  /// FilterArcs adaptor hides arcs in a digraph. A bool arc map must
     1501  /// be specified, which defines the filters for arcs. Just the
     1502  /// unfiltered arcs are shown in the subdigraph. The FilterArcs is
     1503  /// conform to the \ref concepts::Digraph "Digraph concept".
     1504  ///
     1505  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
     1506  /// "Digraph concept". The type can be specified to be const.
     1507  /// \tparam _ArcFilterMap A bool valued arc map of the the adapted
     1508  /// graph.
     1509  template<typename _Digraph, typename _ArcFilterMap>
     1510  class FilterArcs :
     1511    public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>,
     1512                      _ArcFilterMap, false> {
     1513  public:
     1514    typedef _Digraph Digraph;
     1515    typedef _ArcFilterMap ArcFilterMap;
     1516
     1517    typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>,
     1518                       ArcFilterMap, false> Parent;
     1519
     1520    typedef typename Parent::Arc Arc;
     1521
     1522  protected:
     1523    ConstMap<typename Digraph::Node, bool> const_true_map;
     1524
     1525    FilterArcs() : const_true_map(true) {
     1526      Parent::setNodeFilterMap(const_true_map);
     1527    }
     1528
     1529  public:
     1530
     1531    /// \brief Constructor
     1532    ///
     1533    /// Creates a FilterArcs adaptor for the given graph with
     1534    /// given arc map filter.
     1535    FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
     1536      : Parent(), const_true_map(true) {
     1537      Parent::setDigraph(digraph);
     1538      Parent::setNodeFilterMap(const_true_map);
     1539      Parent::setArcFilterMap(arc_filter);
     1540    }
     1541
     1542    /// \brief Hides the arc of the graph
     1543    ///
     1544    /// This function hides \c a in the graph, i.e. the iteration
     1545    /// jumps over it. This is done by simply setting the value of \c a
     1546    /// to be false in the corresponding arc map.
     1547    void hide(const Arc& a) const { Parent::hide(a); }
     1548
     1549    /// \brief Unhides the arc of the graph
     1550    ///
     1551    /// The value of \c a is set to be true in the arc-map which stores
     1552    /// hide information. If \c a was hidden previuosly, then it is shown
     1553    /// again
     1554    void unHide(const Arc& a) const { Parent::unHide(a); }
     1555
     1556    /// \brief Returns true if \c a is hidden.
     1557    ///
     1558    /// Returns true if \c a is hidden.
     1559    ///
     1560    bool hidden(const Arc& a) const { return Parent::hidden(a); }
     1561
     1562  };
     1563
     1564  /// \brief Just gives back an FilterArcs adaptor
     1565  ///
     1566  /// Just gives back an FilterArcs adaptor
     1567  template<typename Digraph, typename ArcFilterMap>
     1568  FilterArcs<const Digraph, ArcFilterMap>
     1569  filterArcs(const Digraph& digraph, ArcFilterMap& afm) {
     1570    return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm);
    15881571  }
    15891572
    1590   template<typename GR, typename NF>
    1591   FilterNodes<const GR, const NF>
    1592   filterNodes(const GR& graph, const NF& node_filter) {
    1593     return FilterNodes<const GR, const NF>(graph, node_filter);
     1573  template<typename Digraph, typename ArcFilterMap>
     1574  FilterArcs<const Digraph, const ArcFilterMap>
     1575  filterArcs(const Digraph& digraph, const ArcFilterMap& afm) {
     1576    return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm);
    15941577  }
    15951578
    15961579  /// \ingroup graph_adaptors
    15971580  ///
    1598   /// \brief Adaptor class for hiding arcs in a digraph.
    1599   ///
    1600   /// FilterArcs adaptor can be used for hiding arcs in a digraph.
    1601   /// A \c bool arc map must be specified, which defines the filter for
    1602   /// the arcs. Only the arcs with \c true filter value are shown in the
    1603   /// subdigraph. This adaptor conforms to the \ref concepts::Digraph
    1604   /// "Digraph" concept.
    1605   ///
    1606   /// The adapted digraph can also be modified through this adaptor
    1607   /// by adding or removing nodes or arcs, unless the \c GR template
    1608   /// parameter is set to be \c const.
    1609   ///
    1610   /// \tparam DGR The type of the adapted digraph.
    1611   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    1612   /// It can also be specified to be \c const.
    1613   /// \tparam AF The type of the arc filter map.
    1614   /// It must be a \c bool (or convertible) arc map of the
    1615   /// adapted digraph. The default type is
    1616   /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>".
    1617   ///
    1618   /// \note The \c Node and \c Arc types of this adaptor and the adapted
    1619   /// digraph are convertible to each other.
    1620 #ifdef DOXYGEN
    1621   template<typename DGR,
    1622            typename AF>
    1623   class FilterArcs {
    1624 #else
    1625   template<typename DGR,
    1626            typename AF = typename DGR::template ArcMap<bool> >
    1627   class FilterArcs :
    1628     public DigraphAdaptorExtender<
    1629       SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
    1630                      AF, false> > {
    1631 #endif
    1632   public:
    1633     /// The type of the adapted digraph.
    1634     typedef DGR Digraph;
    1635     /// The type of the arc filter map.
    1636     typedef AF ArcFilterMap;
    1637 
    1638     typedef DigraphAdaptorExtender<
    1639       SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
    1640                      AF, false> > Parent;
    1641 
    1642     typedef typename Parent::Arc Arc;
    1643 
     1581  /// \brief An adaptor for hiding edges from a graph.
     1582  ///
     1583  /// FilterEdges adaptor hides edges in a digraph. A bool edge map must
     1584  /// be specified, which defines the filters for edges. Just the
     1585  /// unfiltered edges are shown in the subdigraph. The FilterEdges is
     1586  /// conform to the \ref concepts::Graph "Graph concept".
     1587  ///
     1588  /// \tparam _Graph It must be conform to the \ref concepts::Graph
     1589  /// "Graph concept". The type can be specified to be const.
     1590  /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted
     1591  /// graph.
     1592  template<typename _Graph, typename _EdgeFilterMap>
     1593  class FilterEdges :
     1594    public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>,
     1595                    _EdgeFilterMap, false> {
     1596  public:
     1597    typedef _Graph Graph;
     1598    typedef _EdgeFilterMap EdgeFilterMap;
     1599    typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>,
     1600                     EdgeFilterMap, false> Parent;
     1601    typedef typename Parent::Edge Edge;
    16441602  protected:
    1645     ConstMap<typename DGR::Node, Const<bool, true> > const_true_map;
    1646 
    1647     FilterArcs() : const_true_map() {}
    1648 
    1649   public:
    1650 
    1651     /// \brief Constructor
    1652     ///
    1653     /// Creates a subdigraph for the given digraph with the given arc
    1654     /// filter map.
    1655     FilterArcs(DGR& digraph, ArcFilterMap& arc_filter)
    1656       : Parent(), const_true_map() {
    1657       Parent::initialize(digraph, const_true_map, arc_filter);
    1658     }
    1659 
    1660     /// \brief Sets the status of the given arc
    1661     ///
    1662     /// This function sets the status of the given arc.
    1663     /// It is done by simply setting the assigned value of \c a
    1664     /// to \c v in the arc filter map.
    1665     void status(const Arc& a, bool v) const { Parent::status(a, v); }
    1666 
    1667     /// \brief Returns the status of the given arc
    1668     ///
    1669     /// This function returns the status of the given arc.
    1670     /// It is \c true if the given arc is enabled (i.e. not hidden).
    1671     bool status(const Arc& a) const { return Parent::status(a); }
    1672 
    1673     /// \brief Disables the given arc
    1674     ///
    1675     /// This function disables the given arc in the subdigraph,
    1676     /// so the iteration jumps over it.
    1677     /// It is the same as \ref status() "status(a, false)".
    1678     void disable(const Arc& a) const { Parent::status(a, false); }
    1679 
    1680     /// \brief Enables the given arc
    1681     ///
    1682     /// This function enables the given arc in the subdigraph.
    1683     /// It is the same as \ref status() "status(a, true)".
    1684     void enable(const Arc& a) const { Parent::status(a, true); }
    1685 
    1686   };
    1687 
    1688   /// \brief Returns a read-only FilterArcs adaptor
    1689   ///
    1690   /// This function just returns a read-only \ref FilterArcs adaptor.
    1691   /// \ingroup graph_adaptors
    1692   /// \relates FilterArcs
    1693   template<typename DGR, typename AF>
    1694   FilterArcs<const DGR, AF>
    1695   filterArcs(const DGR& digraph, AF& arc_filter) {
    1696     return FilterArcs<const DGR, AF>(digraph, arc_filter);
    1697   }
    1698 
    1699   template<typename DGR, typename AF>
    1700   FilterArcs<const DGR, const AF>
    1701   filterArcs(const DGR& digraph, const AF& arc_filter) {
    1702     return FilterArcs<const DGR, const AF>(digraph, arc_filter);
    1703   }
    1704 
    1705   /// \ingroup graph_adaptors
    1706   ///
    1707   /// \brief Adaptor class for hiding edges in a graph.
    1708   ///
    1709   /// FilterEdges adaptor can be used for hiding edges in a graph.
    1710   /// A \c bool edge map must be specified, which defines the filter for
    1711   /// the edges. Only the edges with \c true filter value are shown in the
    1712   /// subgraph. This adaptor conforms to the \ref concepts::Graph
    1713   /// "Graph" concept.
    1714   ///
    1715   /// The adapted graph can also be modified through this adaptor
    1716   /// by adding or removing nodes or edges, unless the \c GR template
    1717   /// parameter is set to be \c const.
    1718   ///
    1719   /// \tparam GR The type of the adapted graph.
    1720   /// It must conform to the \ref concepts::Graph "Graph" concept.
    1721   /// It can also be specified to be \c const.
    1722   /// \tparam EF The type of the edge filter map.
    1723   /// It must be a \c bool (or convertible) edge map of the
    1724   /// adapted graph. The default type is
    1725   /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
    1726   ///
    1727   /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the
    1728   /// adapted graph are convertible to each other.
    1729 #ifdef DOXYGEN
    1730   template<typename GR,
    1731            typename EF>
    1732   class FilterEdges {
    1733 #else
    1734   template<typename GR,
    1735            typename EF = typename GR::template EdgeMap<bool> >
    1736   class FilterEdges :
    1737     public GraphAdaptorExtender<
    1738       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,
    1739                    EF, false> > {
    1740 #endif
    1741   public:
    1742     /// The type of the adapted graph.
    1743     typedef GR Graph;
    1744     /// The type of the edge filter map.
    1745     typedef EF EdgeFilterMap;
    1746 
    1747     typedef GraphAdaptorExtender<
    1748       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
    1749                    EF, false> > Parent;
    1750 
    1751     typedef typename Parent::Edge Edge;
    1752 
    1753   protected:
    1754     ConstMap<typename GR::Node, Const<bool, true> > const_true_map;
     1603    ConstMap<typename Graph::Node, bool> const_true_map;
    17551604
    17561605    FilterEdges() : const_true_map(true) {
     
    17621611    /// \brief Constructor
    17631612    ///
    1764     /// Creates a subgraph for the given graph with the given edge
    1765     /// filter map.
    1766     FilterEdges(GR& graph, EF& edge_filter)
    1767       : Parent(), const_true_map() {
    1768       Parent::initialize(graph, const_true_map, edge_filter);
    1769     }
    1770 
    1771     /// \brief Sets the status of the given edge
    1772     ///
    1773     /// This function sets the status of the given edge.
    1774     /// It is done by simply setting the assigned value of \c e
    1775     /// to \c v in the edge filter map.
    1776     void status(const Edge& e, bool v) const { Parent::status(e, v); }
    1777 
    1778     /// \brief Returns the status of the given edge
    1779     ///
    1780     /// This function returns the status of the given edge.
    1781     /// It is \c true if the given edge is enabled (i.e. not hidden).
    1782     bool status(const Edge& e) const { return Parent::status(e); }
    1783 
    1784     /// \brief Disables the given edge
    1785     ///
    1786     /// This function disables the given edge in the subgraph,
    1787     /// so the iteration jumps over it.
    1788     /// It is the same as \ref status() "status(e, false)".
    1789     void disable(const Edge& e) const { Parent::status(e, false); }
    1790 
    1791     /// \brief Enables the given edge
    1792     ///
    1793     /// This function enables the given edge in the subgraph.
    1794     /// It is the same as \ref status() "status(e, true)".
    1795     void enable(const Edge& e) const { Parent::status(e, true); }
     1613    /// Creates a FilterEdges adaptor for the given graph with
     1614    /// given edge map filters.
     1615    FilterEdges(Graph& _graph, EdgeFilterMap& edge_filter_map) :
     1616      Parent(), const_true_map(true) {
     1617      Parent::setGraph(_graph);
     1618      Parent::setNodeFilterMap(const_true_map);
     1619      Parent::setEdgeFilterMap(edge_filter_map);
     1620    }
     1621
     1622    /// \brief Hides the edge of the graph
     1623    ///
     1624    /// This function hides \c e in the graph, i.e. the iteration
     1625    /// jumps over it. This is done by simply setting the value of \c e
     1626    /// to be false in the corresponding edge-map.
     1627    void hide(const Edge& e) const { Parent::hide(e); }
     1628
     1629    /// \brief Unhides the edge of the graph
     1630    ///
     1631    /// The value of \c e is set to be true in the edge-map which stores
     1632    /// hide information. If \c e was hidden previuosly, then it is shown
     1633    /// again
     1634    void unHide(const Edge& e) const { Parent::unHide(e); }
     1635
     1636    /// \brief Returns true if \c e is hidden.
     1637    ///
     1638    /// Returns true if \c e is hidden.
     1639    ///
     1640    bool hidden(const Edge& e) const { return Parent::hidden(e); }
    17961641
    17971642  };
    17981643
    1799   /// \brief Returns a read-only FilterEdges adaptor
    1800   ///
    1801   /// This function just returns a read-only \ref FilterEdges adaptor.
    1802   /// \ingroup graph_adaptors
    1803   /// \relates FilterEdges
    1804   template<typename GR, typename EF>
    1805   FilterEdges<const GR, EF>
    1806   filterEdges(const GR& graph, EF& edge_filter) {
    1807     return FilterEdges<const GR, EF>(graph, edge_filter);
     1644  /// \brief Just gives back a FilterEdges adaptor
     1645  ///
     1646  /// Just gives back a FilterEdges adaptor
     1647  template<typename Graph, typename EdgeFilterMap>
     1648  FilterEdges<const Graph, EdgeFilterMap>
     1649  filterEdges(const Graph& graph, EdgeFilterMap& efm) {
     1650    return FilterEdges<const Graph, EdgeFilterMap>(graph, efm);
    18081651  }
    18091652
    1810   template<typename GR, typename EF>
    1811   FilterEdges<const GR, const EF>
    1812   filterEdges(const GR& graph, const EF& edge_filter) {
    1813     return FilterEdges<const GR, const EF>(graph, edge_filter);
     1653  template<typename Graph, typename EdgeFilterMap>
     1654  FilterEdges<const Graph, const EdgeFilterMap>
     1655  filterEdges(const Graph& graph, const EdgeFilterMap& efm) {
     1656    return FilterEdges<const Graph, const EdgeFilterMap>(graph, efm);
    18141657  }
    18151658
    1816 
    1817   template <typename DGR>
     1659  template <typename _Digraph>
    18181660  class UndirectorBase {
    18191661  public:
    1820     typedef DGR Digraph;
     1662    typedef _Digraph Digraph;
    18211663    typedef UndirectorBase Adaptor;
    18221664
     
    18531695      }
    18541696    };
     1697
     1698
    18551699
    18561700    void first(Node& n) const {
     
    20021846
    20031847    typedef NodeNumTagIndicator<Digraph> NodeNumTag;
    2004     int nodeNum() const { return _digraph->nodeNum(); }
    2005 
    2006     typedef ArcNumTagIndicator<Digraph> ArcNumTag;
     1848    int nodeNum() const { return 2 * _digraph->arcNum(); }
     1849    typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
    20071850    int arcNum() const { return 2 * _digraph->arcNum(); }
    2008 
    2009     typedef ArcNumTag EdgeNumTag;
    20101851    int edgeNum() const { return _digraph->arcNum(); }
    20111852
    2012     typedef FindArcTagIndicator<Digraph> FindArcTag;
     1853    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
    20131854    Arc findArc(Node s, Node t, Arc p = INVALID) const {
    20141855      if (p == INVALID) {
     
    20291870    }
    20301871
    2031     typedef FindArcTag FindEdgeTag;
    20321872    Edge findEdge(Node s, Node t, Edge p = INVALID) const {
    20331873      if (s != t) {
     
    20371877          arc = _digraph->findArc(t, s);
    20381878          if (arc != INVALID) return arc;
    2039         } else if (_digraph->source(p) == s) {
     1879        } else if (_digraph->s(p) == s) {
    20401880          Edge arc = _digraph->findArc(s, t, p);
    20411881          if (arc != INVALID) return arc;
     
    20541894  private:
    20551895
    2056     template <typename V>
     1896    template <typename _Value>
    20571897    class ArcMapBase {
    20581898    private:
    20591899
    2060       typedef typename DGR::template ArcMap<V> MapImpl;
     1900      typedef typename Digraph::template ArcMap<_Value> MapImpl;
    20611901
    20621902    public:
     
    20641904      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
    20651905
    2066       typedef V Value;
     1906      typedef _Value Value;
    20671907      typedef Arc Key;
    2068       typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue;
    2069       typedef typename MapTraits<MapImpl>::ReturnValue ReturnValue;
    2070       typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReference;
    2071       typedef typename MapTraits<MapImpl>::ReturnValue Reference;
    2072 
    2073       ArcMapBase(const UndirectorBase<DGR>& adaptor) :
     1908
     1909      ArcMapBase(const Adaptor& adaptor) :
    20741910        _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
    20751911
    2076       ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)
    2077         : _forward(*adaptor._digraph, value),
    2078           _backward(*adaptor._digraph, value) {}
    2079 
    2080       void set(const Arc& a, const V& value) {
     1912      ArcMapBase(const Adaptor& adaptor, const Value& v)
     1913        : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}
     1914
     1915      void set(const Arc& a, const Value& v) {
    20811916        if (direction(a)) {
    2082           _forward.set(a, value);
     1917          _forward.set(a, v);
    20831918        } else {
    2084           _backward.set(a, value);
     1919          _backward.set(a, v);
    20851920        }
    20861921      }
    20871922
    2088       ConstReturnValue operator[](const Arc& a) const {
     1923      typename MapTraits<MapImpl>::ConstReturnValue
     1924      operator[](const Arc& a) const {
    20891925        if (direction(a)) {
    20901926          return _forward[a];
     
    20941930      }
    20951931
    2096       ReturnValue operator[](const Arc& a) {
     1932      typename MapTraits<MapImpl>::ReturnValue
     1933      operator[](const Arc& a) {
    20971934        if (direction(a)) {
    20981935          return _forward[a];
     
    21101947  public:
    21111948
    2112     template <typename V>
    2113     class NodeMap : public DGR::template NodeMap<V> {
    2114     public:
    2115 
    2116       typedef V Value;
    2117       typedef typename DGR::template NodeMap<Value> Parent;
    2118 
    2119       explicit NodeMap(const UndirectorBase<DGR>& adaptor)
     1949    template <typename _Value>
     1950    class NodeMap : public Digraph::template NodeMap<_Value> {
     1951    public:
     1952
     1953      typedef _Value Value;
     1954      typedef typename Digraph::template NodeMap<Value> Parent;
     1955
     1956      explicit NodeMap(const Adaptor& adaptor)
    21201957        : Parent(*adaptor._digraph) {}
    21211958
    2122       NodeMap(const UndirectorBase<DGR>& adaptor, const V& value)
     1959      NodeMap(const Adaptor& adaptor, const _Value& value)
    21231960        : Parent(*adaptor._digraph, value) { }
    21241961
     
    21361973    };
    21371974
    2138     template <typename V>
     1975    template <typename _Value>
    21391976    class ArcMap
    2140       : public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> >
     1977      : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
    21411978    {
    21421979    public:
    2143       typedef V Value;
    2144       typedef SubMapExtender<Adaptor, ArcMapBase<V> > Parent;
    2145 
    2146       explicit ArcMap(const UndirectorBase<DGR>& adaptor)
     1980      typedef _Value Value;
     1981      typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
     1982
     1983      ArcMap(const Adaptor& adaptor)
    21471984        : Parent(adaptor) {}
    21481985
    2149       ArcMap(const UndirectorBase<DGR>& adaptor, const V& value)
     1986      ArcMap(const Adaptor& adaptor, const Value& value)
    21501987        : Parent(adaptor, value) {}
    21511988
     
    21621999    };
    21632000
    2164     template <typename V>
    2165     class EdgeMap : public Digraph::template ArcMap<V> {
    2166     public:
    2167 
    2168       typedef V Value;
    2169       typedef typename Digraph::template ArcMap<V> Parent;
    2170 
    2171       explicit EdgeMap(const UndirectorBase<DGR>& adaptor)
     2001    template <typename _Value>
     2002    class EdgeMap : public Digraph::template ArcMap<_Value> {
     2003    public:
     2004
     2005      typedef _Value Value;
     2006      typedef typename Digraph::template ArcMap<Value> Parent;
     2007
     2008      explicit EdgeMap(const Adaptor& adaptor)
    21722009        : Parent(*adaptor._digraph) {}
    21732010
    2174       EdgeMap(const UndirectorBase<DGR>& adaptor, const V& value)
     2011      EdgeMap(const Adaptor& adaptor, const Value& value)
    21752012        : Parent(*adaptor._digraph, value) {}
    21762013
     
    21882025    };
    21892026
    2190     typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
     2027    typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
    21912028    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
    21922029
    2193     typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
    2194     EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
    2195 
    21962030  protected:
    21972031
    21982032    UndirectorBase() : _digraph(0) {}
    21992033
    2200     DGR* _digraph;
    2201 
    2202     void initialize(DGR& digraph) {
     2034    Digraph* _digraph;
     2035
     2036    void setDigraph(Digraph& digraph) {
    22032037      _digraph = &digraph;
    22042038    }
     
    22082042  /// \ingroup graph_adaptors
    22092043  ///
    2210   /// \brief Adaptor class for viewing a digraph as an undirected graph.
    2211   ///
    2212   /// Undirector adaptor can be used for viewing a digraph as an undirected
    2213   /// graph. All arcs of the underlying digraph are showed in the
    2214   /// adaptor as an edge (and also as a pair of arcs, of course).
    2215   /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
    2216   ///
    2217   /// The adapted digraph can also be modified through this adaptor
    2218   /// by adding or removing nodes or edges, unless the \c GR template
    2219   /// parameter is set to be \c const.
    2220   ///
    2221   /// \tparam DGR The type of the adapted digraph.
    2222   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    2223   /// It can also be specified to be \c const.
    2224   ///
    2225   /// \note The \c Node type of this adaptor and the adapted digraph are
    2226   /// convertible to each other, moreover the \c Edge type of the adaptor
    2227   /// and the \c Arc type of the adapted digraph are also convertible to
    2228   /// each other.
    2229   /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type
    2230   /// of the adapted digraph.)
    2231   template<typename DGR>
    2232 #ifdef DOXYGEN
    2233   class Undirector {
    2234 #else
    2235   class Undirector :
    2236     public GraphAdaptorExtender<UndirectorBase<DGR> > {
    2237 #endif
    2238   public:
    2239     /// The type of the adapted digraph.
    2240     typedef DGR Digraph;
    2241     typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent;
     2044  /// \brief Undirect the graph
     2045  ///
     2046  /// This adaptor makes an undirected graph from a directed
     2047  /// graph. All arcs of the underlying digraph will be showed in the
     2048  /// adaptor as an edge. The Orienter adaptor is conform to the \ref
     2049  /// concepts::Graph "Graph concept".
     2050  ///
     2051  /// \tparam _Digraph It must be conform to the \ref
     2052  /// concepts::Digraph "Digraph concept". The type can be specified
     2053  /// to const.
     2054  template<typename _Digraph>
     2055  class Undirector
     2056    : public GraphAdaptorExtender<UndirectorBase<_Digraph> > {
     2057  public:
     2058    typedef _Digraph Digraph;
     2059    typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent;
    22422060  protected:
    22432061    Undirector() { }
     
    22462064    /// \brief Constructor
    22472065    ///
    2248     /// Creates an undirected graph from the given digraph.
    2249     Undirector(DGR& digraph) {
    2250       initialize(digraph);
    2251     }
    2252 
    2253     /// \brief Arc map combined from two original arc maps
    2254     ///
    2255     /// This map adaptor class adapts two arc maps of the underlying
    2256     /// digraph to get an arc map of the undirected graph.
    2257     /// Its value type is inherited from the first arc map type
    2258     /// (\c %ForwardMap).
    2259     template <typename ForwardMap, typename BackwardMap>
     2066    /// Creates a undirected graph from the given digraph
     2067    Undirector(_Digraph& digraph) {
     2068      setDigraph(digraph);
     2069    }
     2070
     2071    /// \brief ArcMap combined from two original ArcMap
     2072    ///
     2073    /// This class adapts two original digraph ArcMap to
     2074    /// get an arc map on the undirected graph.
     2075    template <typename _ForwardMap, typename _BackwardMap>
    22602076    class CombinedArcMap {
    22612077    public:
    22622078
    2263       /// The key type of the map
     2079      typedef _ForwardMap ForwardMap;
     2080      typedef _BackwardMap BackwardMap;
     2081
     2082      typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
     2083
     2084      typedef typename ForwardMap::Value Value;
    22642085      typedef typename Parent::Arc Key;
    2265       /// The value type of the map
    2266       typedef typename ForwardMap::Value Value;
    2267 
    2268       typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
    2269 
    2270       typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue;
    2271       typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReturnValue;
    2272       typedef typename MapTraits<ForwardMap>::ReturnValue Reference;
    2273       typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference;
    2274 
     2086
     2087      /// \brief Constructor
     2088      ///
    22752089      /// Constructor
    22762090      CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
    22772091        : _forward(&forward), _backward(&backward) {}
    22782092
    2279       /// Sets the value associated with the given key.
     2093
     2094      /// \brief Sets the value associated with a key.
     2095      ///
     2096      /// Sets the value associated with a key.
    22802097      void set(const Key& e, const Value& a) {
    22812098        if (Parent::direction(e)) {
     
    22862103      }
    22872104
    2288       /// Returns the value associated with the given key.
    2289       ConstReturnValue operator[](const Key& e) const {
     2105      /// \brief Returns the value associated with a key.
     2106      ///
     2107      /// Returns the value associated with a key.
     2108      typename MapTraits<ForwardMap>::ConstReturnValue
     2109      operator[](const Key& e) const {
    22902110        if (Parent::direction(e)) {
    22912111          return (*_forward)[e];
     
    22952115      }
    22962116
    2297       /// Returns a reference to the value associated with the given key.
    2298       ReturnValue operator[](const Key& e) {
     2117      /// \brief Returns the value associated with a key.
     2118      ///
     2119      /// Returns the value associated with a key.
     2120      typename MapTraits<ForwardMap>::ReturnValue
     2121      operator[](const Key& e) {
    22992122        if (Parent::direction(e)) {
    23002123          return (*_forward)[e];
     
    23112134    };
    23122135
    2313     /// \brief Returns a combined arc map
    2314     ///
    2315     /// This function just returns a combined arc map.
     2136    /// \brief Just gives back a combined arc map
     2137    ///
     2138    /// Just gives back a combined arc map
    23162139    template <typename ForwardMap, typename BackwardMap>
    23172140    static CombinedArcMap<ForwardMap, BackwardMap>
     
    23432166  };
    23442167
    2345   /// \brief Returns a read-only Undirector adaptor
    2346   ///
    2347   /// This function just returns a read-only \ref Undirector adaptor.
    2348   /// \ingroup graph_adaptors
    2349   /// \relates Undirector
    2350   template<typename DGR>
    2351   Undirector<const DGR> undirector(const DGR& digraph) {
    2352     return Undirector<const DGR>(digraph);
     2168  /// \brief Just gives back an undirected view of the given digraph
     2169  ///
     2170  /// Just gives back an undirected view of the given digraph
     2171  template<typename Digraph>
     2172  Undirector<const Digraph>
     2173  undirector(const Digraph& digraph) {
     2174    return Undirector<const Digraph>(digraph);
    23532175  }
    23542176
    2355 
    2356   template <typename GR, typename DM>
     2177  template <typename _Graph, typename _DirectionMap>
    23572178  class OrienterBase {
    23582179  public:
    23592180
    2360     typedef GR Graph;
    2361     typedef DM DirectionMap;
    2362 
    2363     typedef typename GR::Node Node;
    2364     typedef typename GR::Edge Arc;
     2181    typedef _Graph Graph;
     2182    typedef _DirectionMap DirectionMap;
     2183
     2184    typedef typename Graph::Node Node;
     2185    typedef typename Graph::Edge Arc;
    23652186
    23662187    void reverseArc(const Arc& arc) {
     
    23712192    void first(Arc& i) const { _graph->first(i); }
    23722193    void firstIn(Arc& i, const Node& n) const {
    2373       bool d = true;
     2194      bool d;
    23742195      _graph->firstInc(i, d, n);
    23752196      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
    23762197    }
    23772198    void firstOut(Arc& i, const Node& n ) const {
    2378       bool d = true;
     2199      bool d;
    23792200      _graph->firstInc(i, d, n);
    23802201      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
     
    24042225    int nodeNum() const { return _graph->nodeNum(); }
    24052226
    2406     typedef EdgeNumTagIndicator<Graph> ArcNumTag;
     2227    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
    24072228    int arcNum() const { return _graph->edgeNum(); }
    24082229
    2409     typedef FindEdgeTagIndicator<Graph> FindArcTag;
     2230    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
    24102231    Arc findArc(const Node& u, const Node& v,
    2411                 const Arc& prev = INVALID) const {
    2412       Arc arc = _graph->findEdge(u, v, prev);
    2413       while (arc != INVALID && source(arc) != u) {
     2232                const Arc& prev = INVALID) {
     2233      Arc arc = prev;
     2234      bool d = arc == INVALID ? true : (*_direction)[arc];
     2235      if (d) {
    24142236        arc = _graph->findEdge(u, v, arc);
     2237        while (arc != INVALID && !(*_direction)[arc]) {
     2238          _graph->findEdge(u, v, arc);
     2239        }
     2240        if (arc != INVALID) return arc;
     2241      }
     2242      _graph->findEdge(v, u, arc);
     2243      while (arc != INVALID && (*_direction)[arc]) {
     2244        _graph->findEdge(u, v, arc);
    24152245      }
    24162246      return arc;
     
    24222252
    24232253    Arc addArc(const Node& u, const Node& v) {
    2424       Arc arc = _graph->addEdge(u, v);
    2425       _direction->set(arc, _graph->u(arc) == u);
     2254      Arc arc = _graph->addArc(u, v);
     2255      _direction->set(arc, _graph->source(arc) == u);
    24262256      return arc;
    24272257    }
     
    24412271    int maxArcId() const { return _graph->maxEdgeId(); }
    24422272
    2443     typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
     2273    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
    24442274    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
    24452275
    2446     typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;
     2276    typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
    24472277    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
    24482278
    2449     template <typename V>
    2450     class NodeMap : public GR::template NodeMap<V> {
    2451     public:
    2452 
    2453       typedef typename GR::template NodeMap<V> Parent;
    2454 
    2455       explicit NodeMap(const OrienterBase<GR, DM>& adapter)
     2279    template <typename _Value>
     2280    class NodeMap : public _Graph::template NodeMap<_Value> {
     2281    public:
     2282
     2283      typedef typename _Graph::template NodeMap<_Value> Parent;
     2284
     2285      explicit NodeMap(const OrienterBase& adapter)
    24562286        : Parent(*adapter._graph) {}
    24572287
    2458       NodeMap(const OrienterBase<GR, DM>& adapter, const V& value)
     2288      NodeMap(const OrienterBase& adapter, const _Value& value)
    24592289        : Parent(*adapter._graph, value) {}
    24602290
     
    24722302    };
    24732303
    2474     template <typename V>
    2475     class ArcMap : public GR::template EdgeMap<V> {
    2476     public:
    2477 
    2478       typedef typename Graph::template EdgeMap<V> Parent;
    2479 
    2480       explicit ArcMap(const OrienterBase<GR, DM>& adapter)
     2304    template <typename _Value>
     2305    class ArcMap : public _Graph::template EdgeMap<_Value> {
     2306    public:
     2307
     2308      typedef typename Graph::template EdgeMap<_Value> Parent;
     2309
     2310      explicit ArcMap(const OrienterBase& adapter)
    24812311        : Parent(*adapter._graph) { }
    24822312
    2483       ArcMap(const OrienterBase<GR, DM>& adapter, const V& value)
     2313      ArcMap(const OrienterBase& adapter, const _Value& value)
    24842314        : Parent(*adapter._graph, value) { }
    24852315
     
    25002330  protected:
    25012331    Graph* _graph;
    2502     DM* _direction;
    2503 
    2504     void initialize(GR& graph, DM& direction) {
     2332    DirectionMap* _direction;
     2333
     2334    void setDirectionMap(DirectionMap& direction) {
     2335      _direction = &direction;
     2336    }
     2337
     2338    void setGraph(Graph& graph) {
    25052339      _graph = &graph;
    2506       _direction = &direction;
    25072340    }
    25082341
     
    25112344  /// \ingroup graph_adaptors
    25122345  ///
    2513   /// \brief Adaptor class for orienting the edges of a graph to get a digraph
    2514   ///
    2515   /// Orienter adaptor can be used for orienting the edges of a graph to
    2516   /// get a digraph. A \c bool edge map of the underlying graph must be
    2517   /// specified, which define the direction of the arcs in the adaptor.
    2518   /// The arcs can be easily reversed by the \c reverseArc() member function
    2519   /// of the adaptor.
    2520   /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
    2521   ///
    2522   /// The adapted graph can also be modified through this adaptor
    2523   /// by adding or removing nodes or arcs, unless the \c GR template
    2524   /// parameter is set to be \c const.
    2525   ///
    2526   /// \tparam GR The type of the adapted graph.
    2527   /// It must conform to the \ref concepts::Graph "Graph" concept.
    2528   /// It can also be specified to be \c const.
    2529   /// \tparam DM The type of the direction map.
    2530   /// It must be a \c bool (or convertible) edge map of the
    2531   /// adapted graph. The default type is
    2532   /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
    2533   ///
    2534   /// \note The \c Node type of this adaptor and the adapted graph are
    2535   /// convertible to each other, moreover the \c Arc type of the adaptor
    2536   /// and the \c Edge type of the adapted graph are also convertible to
    2537   /// each other.
    2538 #ifdef DOXYGEN
    2539   template<typename GR,
    2540            typename DM>
    2541   class Orienter {
    2542 #else
    2543   template<typename GR,
    2544            typename DM = typename GR::template EdgeMap<bool> >
     2346  /// \brief Orients the edges of the graph to get a digraph
     2347  ///
     2348  /// This adaptor orients each edge in the undirected graph. The
     2349  /// direction of the arcs stored in an edge node map.  The arcs can
     2350  /// be easily reverted by the \c reverseArc() member function in the
     2351  /// adaptor. The Orienter adaptor is conform to the \ref
     2352  /// concepts::Digraph "Digraph concept".
     2353  ///
     2354  /// \tparam _Graph It must be conform to the \ref concepts::Graph
     2355  /// "Graph concept". The type can be specified to be const.
     2356  /// \tparam _DirectionMap A bool valued edge map of the the adapted
     2357  /// graph.
     2358  ///
     2359  /// \sa orienter
     2360  template<typename _Graph,
     2361           typename DirectionMap = typename _Graph::template EdgeMap<bool> >
    25452362  class Orienter :
    2546     public DigraphAdaptorExtender<OrienterBase<GR, DM> > {
    2547 #endif
    2548   public:
    2549 
    2550     /// The type of the adapted graph.
    2551     typedef GR Graph;
    2552     /// The type of the direction edge map.
    2553     typedef DM DirectionMap;
    2554 
    2555     typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
     2363    public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > {
     2364  public:
     2365    typedef _Graph Graph;
     2366    typedef DigraphAdaptorExtender<
     2367      OrienterBase<_Graph, DirectionMap> > Parent;
    25562368    typedef typename Parent::Arc Arc;
    25572369  protected:
     
    25592371  public:
    25602372
    2561     /// \brief Constructor
    2562     ///
    2563     /// Constructor of the adaptor.
    2564     Orienter(GR& graph, DM& direction) {
    2565       Parent::initialize(graph, direction);
    2566     }
    2567 
    2568     /// \brief Reverses the given arc
    2569     ///
    2570     /// This function reverses the given arc.
    2571     /// It is done by simply negate the assigned value of \c a
    2572     /// in the direction map.
     2373    /// \brief Constructor of the adaptor
     2374    ///
     2375    /// Constructor of the adaptor
     2376    Orienter(Graph& graph, DirectionMap& direction) {
     2377      setGraph(graph);
     2378      setDirectionMap(direction);
     2379    }
     2380
     2381    /// \brief Reverse arc
     2382    ///
     2383    /// It reverse the given arc. It simply negate the direction in the map.
    25732384    void reverseArc(const Arc& a) {
    25742385      Parent::reverseArc(a);
     
    25762387  };
    25772388
    2578   /// \brief Returns a read-only Orienter adaptor
    2579   ///
    2580   /// This function just returns a read-only \ref Orienter adaptor.
     2389  /// \brief Just gives back a Orienter
     2390  ///
     2391  /// Just gives back a Orienter
     2392  template<typename Graph, typename DirectionMap>
     2393  Orienter<const Graph, DirectionMap>
     2394  orienter(const Graph& graph, DirectionMap& dm) {
     2395    return Orienter<const Graph, DirectionMap>(graph, dm);
     2396  }
     2397
     2398  template<typename Graph, typename DirectionMap>
     2399  Orienter<const Graph, const DirectionMap>
     2400  orienter(const Graph& graph, const DirectionMap& dm) {
     2401    return Orienter<const Graph, const DirectionMap>(graph, dm);
     2402  }
     2403
     2404  namespace _adaptor_bits {
     2405
     2406    template<typename _Digraph,
     2407             typename _CapacityMap = typename _Digraph::template ArcMap<int>,
     2408             typename _FlowMap = _CapacityMap,
     2409             typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
     2410    class ResForwardFilter {
     2411    public:
     2412
     2413      typedef _Digraph Digraph;
     2414      typedef _CapacityMap CapacityMap;
     2415      typedef _FlowMap FlowMap;
     2416      typedef _Tolerance Tolerance;
     2417
     2418      typedef typename Digraph::Arc Key;
     2419      typedef bool Value;
     2420
     2421    private:
     2422
     2423      const CapacityMap* _capacity;
     2424      const FlowMap* _flow;
     2425      Tolerance _tolerance;
     2426    public:
     2427
     2428      ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,
     2429                       const Tolerance& tolerance = Tolerance())
     2430        : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
     2431
     2432      bool operator[](const typename Digraph::Arc& a) const {
     2433        return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
     2434      }
     2435    };
     2436
     2437    template<typename _Digraph,
     2438             typename _CapacityMap = typename _Digraph::template ArcMap<int>,
     2439             typename _FlowMap = _CapacityMap,
     2440             typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
     2441    class ResBackwardFilter {
     2442    public:
     2443
     2444      typedef _Digraph Digraph;
     2445      typedef _CapacityMap CapacityMap;
     2446      typedef _FlowMap FlowMap;
     2447      typedef _Tolerance Tolerance;
     2448
     2449      typedef typename Digraph::Arc Key;
     2450      typedef bool Value;
     2451
     2452    private:
     2453
     2454      const CapacityMap* _capacity;
     2455      const FlowMap* _flow;
     2456      Tolerance _tolerance;
     2457
     2458    public:
     2459
     2460      ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,
     2461                        const Tolerance& tolerance = Tolerance())
     2462        : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
     2463
     2464      bool operator[](const typename Digraph::Arc& a) const {
     2465        return _tolerance.positive((*_flow)[a]);
     2466      }
     2467    };
     2468
     2469  }
     2470
    25812471  /// \ingroup graph_adaptors
    2582   /// \relates Orienter
    2583   template<typename GR, typename DM>
    2584   Orienter<const GR, DM>
    2585   orienter(const GR& graph, DM& direction) {
    2586     return Orienter<const GR, DM>(graph, direction);
    2587   }
    2588 
    2589   template<typename GR, typename DM>
    2590   Orienter<const GR, const DM>
    2591   orienter(const GR& graph, const DM& direction) {
    2592     return Orienter<const GR, const DM>(graph, direction);
    2593   }
    2594 
    2595   namespace _adaptor_bits {
    2596 
    2597     template <typename DGR, typename CM, typename FM, typename TL>
    2598     class ResForwardFilter {
    2599     public:
    2600 
    2601       typedef typename DGR::Arc Key;
    2602       typedef bool Value;
    2603 
    2604     private:
    2605 
    2606       const CM* _capacity;
    2607       const FM* _flow;
    2608       TL _tolerance;
    2609 
    2610     public:
    2611 
    2612       ResForwardFilter(const CM& capacity, const FM& flow,
    2613                        const TL& tolerance = TL())
    2614         : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
    2615 
    2616       bool operator[](const typename DGR::Arc& a) const {
    2617         return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
    2618       }
    2619     };
    2620 
    2621     template<typename DGR,typename CM, typename FM, typename TL>
    2622     class ResBackwardFilter {
    2623     public:
    2624 
    2625       typedef typename DGR::Arc Key;
    2626       typedef bool Value;
    2627 
    2628     private:
    2629 
    2630       const CM* _capacity;
    2631       const FM* _flow;
    2632       TL _tolerance;
    2633 
    2634     public:
    2635 
    2636       ResBackwardFilter(const CM& capacity, const FM& flow,
    2637                         const TL& tolerance = TL())
    2638         : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
    2639 
    2640       bool operator[](const typename DGR::Arc& a) const {
    2641         return _tolerance.positive((*_flow)[a]);
    2642       }
    2643     };
    2644 
    2645   }
    2646 
    2647   /// \ingroup graph_adaptors
    2648   ///
    2649   /// \brief Adaptor class for composing the residual digraph for directed
     2472  ///
     2473  /// \brief An adaptor for composing the residual graph for directed
    26502474  /// flow and circulation problems.
    26512475  ///
    2652   /// ResidualDigraph can be used for composing the \e residual digraph
    2653   /// for directed flow and circulation problems. Let \f$ G=(V, A) \f$
    2654   /// be a directed graph and let \f$ F \f$ be a number type.
    2655   /// Let \f$ flow, cap: A\to F \f$ be functions on the arcs.
    2656   /// This adaptor implements a digraph structure with node set \f$ V \f$
    2657   /// and arc set \f$ A_{forward}\cup A_{backward} \f$,
    2658   /// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)<cap(uv)\} \f$ and
    2659   /// \f$ A_{backward}=\{vu : uv\in A, flow(uv)>0\} \f$, i.e. the so
    2660   /// called residual digraph.
    2661   /// When the union \f$ A_{forward}\cup A_{backward} \f$ is taken,
    2662   /// multiplicities are counted, i.e. the adaptor has exactly
    2663   /// \f$ |A_{forward}| + |A_{backward}|\f$ arcs (it may have parallel
    2664   /// arcs).
    2665   /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
    2666   ///
    2667   /// \tparam DGR The type of the adapted digraph.
    2668   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    2669   /// It is implicitly \c const.
    2670   /// \tparam CM The type of the capacity map.
    2671   /// It must be an arc map of some numerical type, which defines
    2672   /// the capacities in the flow problem. It is implicitly \c const.
    2673   /// The default type is
    2674   /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    2675   /// \tparam FM The type of the flow map.
    2676   /// It must be an arc map of some numerical type, which defines
    2677   /// the flow values in the flow problem. The default type is \c CM.
    2678   /// \tparam TL The tolerance type for handling inexact computation.
    2679   /// The default tolerance type depends on the value type of the
    2680   /// capacity map.
    2681   ///
    2682   /// \note This adaptor is implemented using Undirector and FilterArcs
    2683   /// adaptors.
    2684   ///
    2685   /// \note The \c Node type of this adaptor and the adapted digraph are
    2686   /// convertible to each other, moreover the \c Arc type of the adaptor
    2687   /// is convertible to the \c Arc type of the adapted digraph.
    2688 #ifdef DOXYGEN
    2689   template<typename DGR, typename CM, typename FM, typename TL>
    2690   class ResidualDigraph
    2691 #else
    2692   template<typename DGR,
    2693            typename CM = typename DGR::template ArcMap<int>,
    2694            typename FM = CM,
    2695            typename TL = Tolerance<typename CM::Value> >
    2696   class ResidualDigraph
    2697     : public SubDigraph<
    2698         Undirector<const DGR>,
    2699         ConstMap<typename DGR::Node, Const<bool, true> >,
    2700         typename Undirector<const DGR>::template CombinedArcMap<
    2701           _adaptor_bits::ResForwardFilter<const DGR, CM, FM, TL>,
    2702           _adaptor_bits::ResBackwardFilter<const DGR, CM, FM, TL> > >
    2703 #endif
     2476  /// An adaptor for composing the residual graph for directed flow and
     2477  /// circulation problems.  Let \f$ G=(V, A) \f$ be a directed graph
     2478  /// and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
     2479  /// be functions on the arc-set.
     2480  ///
     2481  /// Then Residual implements the digraph structure with
     2482  /// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward} \f$,
     2483  /// where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
     2484  /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so
     2485  /// called residual graph.  When we take the union
     2486  /// \f$ A_{forward}\cup A_{backward} \f$, multiplicities are counted,
     2487  /// i.e.  if an arc is in both \f$ A_{forward} \f$ and
     2488  /// \f$ A_{backward} \f$, then in the adaptor it appears in both
     2489  /// orientation.
     2490  ///
     2491  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
     2492  /// "Digraph concept". The type is implicitly const.
     2493  /// \tparam _CapacityMap An arc map of some numeric type, it defines
     2494  /// the capacities in the flow problem. The map is implicitly const.
     2495  /// \tparam _FlowMap An arc map of some numeric type, it defines
     2496  /// the capacities in the flow problem.
     2497  /// \tparam _Tolerance Handler for inexact computation.
     2498  template<typename _Digraph,
     2499           typename _CapacityMap = typename _Digraph::template ArcMap<int>,
     2500           typename _FlowMap = _CapacityMap,
     2501           typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
     2502  class Residual :
     2503    public FilterArcs<
     2504    Undirector<const _Digraph>,
     2505    typename Undirector<const _Digraph>::template CombinedArcMap<
     2506      _adaptor_bits::ResForwardFilter<const _Digraph, _CapacityMap,
     2507                                      _FlowMap, _Tolerance>,
     2508      _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap,
     2509                                       _FlowMap, _Tolerance> > >
    27042510  {
    27052511  public:
    27062512
    2707     /// The type of the underlying digraph.
    2708     typedef DGR Digraph;
    2709     /// The type of the capacity map.
    2710     typedef CM CapacityMap;
    2711     /// The type of the flow map.
    2712     typedef FM FlowMap;
    2713     /// The tolerance type.
    2714     typedef TL Tolerance;
     2513    typedef _Digraph Digraph;
     2514    typedef _CapacityMap CapacityMap;
     2515    typedef _FlowMap FlowMap;
     2516    typedef _Tolerance Tolerance;
    27152517
    27162518    typedef typename CapacityMap::Value Value;
    2717     typedef ResidualDigraph Adaptor;
     2519    typedef Residual Adaptor;
    27182520
    27192521  protected:
     
    27212523    typedef Undirector<const Digraph> Undirected;
    27222524
    2723     typedef ConstMap<typename DGR::Node, Const<bool, true> > NodeFilter;
    2724 
    2725     typedef _adaptor_bits::ResForwardFilter<const DGR, CM,
    2726                                             FM, TL> ForwardFilter;
    2727 
    2728     typedef _adaptor_bits::ResBackwardFilter<const DGR, CM,
    2729                                              FM, TL> BackwardFilter;
     2525    typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap,
     2526                                            FlowMap, Tolerance> ForwardFilter;
     2527
     2528    typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap,
     2529                                             FlowMap, Tolerance> BackwardFilter;
    27302530
    27312531    typedef typename Undirected::
    2732       template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
    2733 
    2734     typedef SubDigraph<Undirected, NodeFilter, ArcFilter> Parent;
     2532    template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
     2533
     2534    typedef FilterArcs<Undirected, ArcFilter> Parent;
    27352535
    27362536    const CapacityMap* _capacity;
     
    27382538
    27392539    Undirected _graph;
    2740     NodeFilter _node_filter;
    27412540    ForwardFilter _forward_filter;
    27422541    BackwardFilter _backward_filter;
     
    27452544  public:
    27462545
    2747     /// \brief Constructor
    2748     ///
    2749     /// Constructor of the residual digraph adaptor. The parameters are the
    2750     /// digraph, the capacity map, the flow map, and a tolerance object.
    2751     ResidualDigraph(const DGR& digraph, const CM& capacity,
    2752                     FM& flow, const TL& tolerance = Tolerance())
    2753       : Parent(), _capacity(&capacity), _flow(&flow),
    2754         _graph(digraph), _node_filter(),
     2546    /// \brief Constructor of the residual digraph.
     2547    ///
     2548    /// Constructor of the residual graph. The parameters are the digraph,
     2549    /// the flow map, the capacity map and a tolerance object.
     2550    Residual(const Digraph& digraph, const CapacityMap& capacity,
     2551             FlowMap& flow, const Tolerance& tolerance = Tolerance())
     2552      : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
    27552553        _forward_filter(capacity, flow, tolerance),
    27562554        _backward_filter(capacity, flow, tolerance),
    27572555        _arc_filter(_forward_filter, _backward_filter)
    27582556    {
    2759       Parent::initialize(_graph, _node_filter, _arc_filter);
     2557      Parent::setDigraph(_graph);
     2558      Parent::setArcFilterMap(_arc_filter);
    27602559    }
    27612560
    27622561    typedef typename Parent::Arc Arc;
    27632562
    2764     /// \brief Returns the residual capacity of the given arc.
    2765     ///
    2766     /// Returns the residual capacity of the given arc.
     2563    /// \brief Gives back the residual capacity of the arc.
     2564    ///
     2565    /// Gives back the residual capacity of the arc.
    27672566    Value residualCapacity(const Arc& a) const {
    27682567      if (Undirected::direction(a)) {
     
    27732572    }
    27742573
    2775     /// \brief Augments on the given arc in the residual digraph.
    2776     ///
    2777     /// Augments on the given arc in the residual digraph. It increases
    2778     /// or decreases the flow value on the original arc according to the
    2779     /// direction of the residual arc.
     2574    /// \brief Augment on the given arc in the residual graph.
     2575    ///
     2576    /// Augment on the given arc in the residual graph. It increase
     2577    /// or decrease the flow on the original arc depend on the direction
     2578    /// of the residual arc.
    27802579    void augment(const Arc& a, const Value& v) const {
    27812580      if (Undirected::direction(a)) {
     
    27862585    }
    27872586
    2788     /// \brief Returns \c true if the given residual arc is a forward arc.
    2789     ///
    2790     /// Returns \c true if the given residual arc has the same orientation
    2791     /// as the original arc, i.e. it is a so called forward arc.
     2587    /// \brief Returns the direction of the arc.
     2588    ///
     2589    /// Returns true when the arc is same oriented as the original arc.
    27922590    static bool forward(const Arc& a) {
    27932591      return Undirected::direction(a);
    27942592    }
    27952593
    2796     /// \brief Returns \c true if the given residual arc is a backward arc.
    2797     ///
    2798     /// Returns \c true if the given residual arc has the opposite orientation
    2799     /// than the original arc, i.e. it is a so called backward arc.
     2594    /// \brief Returns the direction of the arc.
     2595    ///
     2596    /// Returns true when the arc is opposite oriented as the original arc.
    28002597    static bool backward(const Arc& a) {
    28012598      return !Undirected::direction(a);
    28022599    }
    28032600
    2804     /// \brief Returns the forward oriented residual arc.
    2805     ///
    2806     /// Returns the forward oriented residual arc related to the given
    2807     /// arc of the underlying digraph.
     2601    /// \brief Gives back the forward oriented residual arc.
     2602    ///
     2603    /// Gives back the forward oriented residual arc.
    28082604    static Arc forward(const typename Digraph::Arc& a) {
    28092605      return Undirected::direct(a, true);
    28102606    }
    28112607
    2812     /// \brief Returns the backward oriented residual arc.
    2813     ///
    2814     /// Returns the backward oriented residual arc related to the given
    2815     /// arc of the underlying digraph.
     2608    /// \brief Gives back the backward oriented residual arc.
     2609    ///
     2610    /// Gives back the backward oriented residual arc.
    28162611    static Arc backward(const typename Digraph::Arc& a) {
    28172612      return Undirected::direct(a, false);
     
    28202615    /// \brief Residual capacity map.
    28212616    ///
    2822     /// This map adaptor class can be used for obtaining the residual
    2823     /// capacities as an arc map of the residual digraph.
    2824     /// Its value type is inherited from the capacity map.
     2617    /// In generic residual graph the residual capacity can be obtained
     2618    /// as a map.
    28252619    class ResidualCapacity {
    28262620    protected:
    28272621      const Adaptor* _adaptor;
    28282622    public:
    2829       /// The key type of the map
     2623      /// The Key type
    28302624      typedef Arc Key;
    2831       /// The value type of the map
    2832       typedef typename CapacityMap::Value Value;
     2625      /// The Value type
     2626      typedef typename _CapacityMap::Value Value;
    28332627
    28342628      /// Constructor
    2835       ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)
    2836         : _adaptor(&adaptor) {}
    2837 
    2838       /// Returns the value associated with the given residual arc
     2629      ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}
     2630
     2631      /// \e
    28392632      Value operator[](const Arc& a) const {
    28402633        return _adaptor->residualCapacity(a);
     
    28432636    };
    28442637
    2845     /// \brief Returns a residual capacity map
    2846     ///
    2847     /// This function just returns a residual capacity map.
    2848     ResidualCapacity residualCapacity() const {
    2849       return ResidualCapacity(*this);
    2850     }
    2851 
    28522638  };
    28532639
    2854   /// \brief Returns a (read-only) Residual adaptor
    2855   ///
    2856   /// This function just returns a (read-only) \ref ResidualDigraph adaptor.
    2857   /// \ingroup graph_adaptors
    2858   /// \relates ResidualDigraph
    2859     template<typename DGR, typename CM, typename FM>
    2860   ResidualDigraph<DGR, CM, FM>
    2861   residualDigraph(const DGR& digraph, const CM& capacity_map, FM& flow_map) {
    2862     return ResidualDigraph<DGR, CM, FM> (digraph, capacity_map, flow_map);
    2863   }
    2864 
    2865 
    2866   template <typename DGR>
     2640  template <typename _Digraph>
    28672641  class SplitNodesBase {
    28682642  public:
    28692643
    2870     typedef DGR Digraph;
    2871     typedef DigraphAdaptorBase<const DGR> Parent;
     2644    typedef _Digraph Digraph;
     2645    typedef DigraphAdaptorBase<const _Digraph> Parent;
    28722646    typedef SplitNodesBase Adaptor;
    28732647
    2874     typedef typename DGR::Node DigraphNode;
    2875     typedef typename DGR::Arc DigraphArc;
     2648    typedef typename Digraph::Node DigraphNode;
     2649    typedef typename Digraph::Arc DigraphArc;
    28762650
    28772651    class Node;
     
    31112885
    31122886    typedef True NodeNumTag;
     2887
    31132888    int nodeNum() const {
    31142889      return  2 * countNodes(*_digraph);
    31152890    }
    31162891
    3117     typedef True ArcNumTag;
     2892    typedef True EdgeNumTag;
    31182893    int arcNum() const {
    31192894      return countArcs(*_digraph) + countNodes(*_digraph);
    31202895    }
    31212896
    3122     typedef True FindArcTag;
     2897    typedef True FindEdgeTag;
    31232898    Arc findArc(const Node& u, const Node& v,
    31242899                const Arc& prev = INVALID) const {
    3125       if (inNode(u) && outNode(v)) {
    3126         if (static_cast<const DigraphNode&>(u) ==
    3127             static_cast<const DigraphNode&>(v) && prev == INVALID) {
    3128           return Arc(u);
     2900      if (inNode(u)) {
     2901        if (outNode(v)) {
     2902          if (static_cast<const DigraphNode&>(u) ==
     2903              static_cast<const DigraphNode&>(v) && prev == INVALID) {
     2904            return Arc(u);
     2905          }
    31292906        }
    3130       }
    3131       else if (outNode(u) && inNode(v)) {
    3132         return Arc(::lemon::findArc(*_digraph, u, v, prev));
     2907      } else {
     2908        if (inNode(v)) {
     2909          return Arc(::lemon::findArc(*_digraph, u, v, prev));
     2910        }
    31332911      }
    31342912      return INVALID;
     
    31372915  private:
    31382916
    3139     template <typename V>
     2917    template <typename _Value>
    31402918    class NodeMapBase
    3141       : public MapTraits<typename Parent::template NodeMap<V> > {
    3142       typedef typename Parent::template NodeMap<V> NodeImpl;
     2919      : public MapTraits<typename Parent::template NodeMap<_Value> > {
     2920      typedef typename Parent::template NodeMap<_Value> NodeImpl;
    31432921    public:
    31442922      typedef Node Key;
    3145       typedef V Value;
    3146       typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag;
    3147       typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue;
    3148       typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReturnValue;
    3149       typedef typename MapTraits<NodeImpl>::ReturnValue Reference;
    3150       typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference;
    3151 
    3152       NodeMapBase(const SplitNodesBase<DGR>& adaptor)
     2923      typedef _Value Value;
     2924
     2925      NodeMapBase(const Adaptor& adaptor)
    31532926        : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
    3154       NodeMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)
     2927      NodeMapBase(const Adaptor& adaptor, const Value& value)
    31552928        : _in_map(*adaptor._digraph, value),
    31562929          _out_map(*adaptor._digraph, value) {}
    31572930
    3158       void set(const Node& key, const V& val) {
    3159         if (SplitNodesBase<DGR>::inNode(key)) { _in_map.set(key, val); }
     2931      void set(const Node& key, const Value& val) {
     2932        if (Adaptor::inNode(key)) { _in_map.set(key, val); }
    31602933        else {_out_map.set(key, val); }
    31612934      }
    31622935
    3163       ReturnValue operator[](const Node& key) {
    3164         if (SplitNodesBase<DGR>::inNode(key)) { return _in_map[key]; }
     2936      typename MapTraits<NodeImpl>::ReturnValue
     2937      operator[](const Node& key) {
     2938        if (Adaptor::inNode(key)) { return _in_map[key]; }
    31652939        else { return _out_map[key]; }
    31662940      }
    31672941
    3168       ConstReturnValue operator[](const Node& key) const {
     2942      typename MapTraits<NodeImpl>::ConstReturnValue
     2943      operator[](const Node& key) const {
    31692944        if (Adaptor::inNode(key)) { return _in_map[key]; }
    31702945        else { return _out_map[key]; }
     
    31752950    };
    31762951
    3177     template <typename V>
     2952    template <typename _Value>
    31782953    class ArcMapBase
    3179       : public MapTraits<typename Parent::template ArcMap<V> > {
    3180       typedef typename Parent::template ArcMap<V> ArcImpl;
    3181       typedef typename Parent::template NodeMap<V> NodeImpl;
     2954      : public MapTraits<typename Parent::template ArcMap<_Value> > {
     2955      typedef typename Parent::template ArcMap<_Value> ArcImpl;
     2956      typedef typename Parent::template NodeMap<_Value> NodeImpl;
    31822957    public:
    31832958      typedef Arc Key;
    3184       typedef V Value;
    3185       typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag;
    3186       typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue;
    3187       typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReturnValue;
    3188       typedef typename MapTraits<ArcImpl>::ReturnValue Reference;
    3189       typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference;
    3190 
    3191       ArcMapBase(const SplitNodesBase<DGR>& adaptor)
     2959      typedef _Value Value;
     2960
     2961      ArcMapBase(const Adaptor& adaptor)
    31922962        : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
    3193       ArcMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)
     2963      ArcMapBase(const Adaptor& adaptor, const Value& value)
    31942964        : _arc_map(*adaptor._digraph, value),
    31952965          _node_map(*adaptor._digraph, value) {}
    31962966
    3197       void set(const Arc& key, const V& val) {
    3198         if (SplitNodesBase<DGR>::origArc(key)) {
    3199           _arc_map.set(static_cast<const DigraphArc&>(key), val);
     2967      void set(const Arc& key, const Value& val) {
     2968        if (Adaptor::origArc(key)) {
     2969          _arc_map.set(key._item.first(), val);
    32002970        } else {
    3201           _node_map.set(static_cast<const DigraphNode&>(key), val);
     2971          _node_map.set(key._item.second(), val);
    32022972        }
    32032973      }
    32042974
    3205       ReturnValue operator[](const Arc& key) {
    3206         if (SplitNodesBase<DGR>::origArc(key)) {
    3207           return _arc_map[static_cast<const DigraphArc&>(key)];
     2975      typename MapTraits<ArcImpl>::ReturnValue
     2976      operator[](const Arc& key) {
     2977        if (Adaptor::origArc(key)) {
     2978          return _arc_map[key._item.first()];
    32082979        } else {
    3209           return _node_map[static_cast<const DigraphNode&>(key)];
     2980          return _node_map[key._item.second()];
    32102981        }
    32112982      }
    32122983
    3213       ConstReturnValue operator[](const Arc& key) const {
    3214         if (SplitNodesBase<DGR>::origArc(key)) {
    3215           return _arc_map[static_cast<const DigraphArc&>(key)];
     2984      typename MapTraits<ArcImpl>::ConstReturnValue
     2985      operator[](const Arc& key) const {
     2986        if (Adaptor::origArc(key)) {
     2987          return _arc_map[key._item.first()];
    32162988        } else {
    3217           return _node_map[static_cast<const DigraphNode&>(key)];
     2989          return _node_map[key._item.second()];
    32182990        }
    32192991      }
     
    32262998  public:
    32272999
    3228     template <typename V>
     3000    template <typename _Value>
    32293001    class NodeMap
    3230       : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> >
     3002      : public SubMapExtender<Adaptor, NodeMapBase<_Value> >
    32313003    {
    32323004    public:
    3233       typedef V Value;
    3234       typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<Value> > Parent;
    3235 
    3236       NodeMap(const SplitNodesBase<DGR>& adaptor)
     3005      typedef _Value Value;
     3006      typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent;
     3007
     3008      NodeMap(const Adaptor& adaptor)
    32373009        : Parent(adaptor) {}
    32383010
    3239       NodeMap(const SplitNodesBase<DGR>& adaptor, const V& value)
     3011      NodeMap(const Adaptor& adaptor, const Value& value)
    32403012        : Parent(adaptor, value) {}
    32413013
     
    32523024    };
    32533025
    3254     template <typename V>
     3026    template <typename _Value>
    32553027    class ArcMap
    3256       : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> >
     3028      : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
    32573029    {
    32583030    public:
    3259       typedef V Value;
    3260       typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<Value> > Parent;
    3261 
    3262       ArcMap(const SplitNodesBase<DGR>& adaptor)
     3031      typedef _Value Value;
     3032      typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
     3033
     3034      ArcMap(const Adaptor& adaptor)
    32633035        : Parent(adaptor) {}
    32643036
    3265       ArcMap(const SplitNodesBase<DGR>& adaptor, const V& value)
     3037      ArcMap(const Adaptor& adaptor, const Value& value)
    32663038        : Parent(adaptor, value) {}
    32673039
     
    32823054    SplitNodesBase() : _digraph(0) {}
    32833055
    3284     DGR* _digraph;
    3285 
    3286     void initialize(Digraph& digraph) {
     3056    Digraph* _digraph;
     3057
     3058    void setDigraph(Digraph& digraph) {
    32873059      _digraph = &digraph;
    32883060    }
     
    32923064  /// \ingroup graph_adaptors
    32933065  ///
    3294   /// \brief Adaptor class for splitting the nodes of a digraph.
    3295   ///
    3296   /// SplitNodes adaptor can be used for splitting each node into an
    3297   /// \e in-node and an \e out-node in a digraph. Formaly, the adaptor
    3298   /// replaces each node \f$ u \f$ in the digraph with two nodes,
    3299   /// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$.
    3300   /// If there is a \f$ (v, u) \f$ arc in the original digraph, then the
    3301   /// new target of the arc will be \f$ u_{in} \f$ and similarly the
    3302   /// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$.
    3303   /// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$
    3304   /// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph.
    3305   ///
    3306   /// The aim of this class is running an algorithm with respect to node
    3307   /// costs or capacities if the algorithm considers only arc costs or
    3308   /// capacities directly.
    3309   /// In this case you can use \c SplitNodes adaptor, and set the node
    3310   /// costs/capacities of the original digraph to the \e bind \e arcs
    3311   /// in the adaptor.
    3312   ///
    3313   /// \tparam DGR The type of the adapted digraph.
    3314   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    3315   /// It is implicitly \c const.
    3316   ///
    3317   /// \note The \c Node type of this adaptor is converible to the \c Node
    3318   /// type of the adapted digraph.
    3319   template <typename DGR>
    3320 #ifdef DOXYGEN
    3321   class SplitNodes {
    3322 #else
     3066  /// \brief Split the nodes of a directed graph
     3067  ///
     3068  /// The SplitNodes adaptor splits each node into an in-node and an
     3069  /// out-node. Formaly, the adaptor replaces each \f$ u \f$ node in
     3070  /// the digraph with two nodes(namely node \f$ u_{in} \f$ and node
     3071  /// \f$ u_{out} \f$). If there is a \f$ (v, u) \f$ arc in the
     3072  /// original digraph the new target of the arc will be \f$ u_{in} \f$
     3073  /// and similarly the source of the original \f$ (u, v) \f$ arc
     3074  /// will be \f$ u_{out} \f$.  The adaptor will add for each node in
     3075  /// the original digraph an additional arc which connects
     3076  /// \f$ (u_{in}, u_{out}) \f$.
     3077  ///
     3078  /// The aim of this class is to run algorithm with node costs if the
     3079  /// algorithm can use directly just arc costs. In this case we should use
     3080  /// a \c SplitNodes and set the node cost of the graph to the
     3081  /// bind arc in the adapted graph.
     3082  ///
     3083  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
     3084  /// "Digraph concept". The type can be specified to be const.
     3085  template <typename _Digraph>
    33233086  class SplitNodes
    3324     : public DigraphAdaptorExtender<SplitNodesBase<const DGR> > {
    3325 #endif
    3326   public:
    3327     typedef DGR Digraph;
    3328     typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent;
    3329 
    3330     typedef typename DGR::Node DigraphNode;
    3331     typedef typename DGR::Arc DigraphArc;
     3087    : public DigraphAdaptorExtender<SplitNodesBase<_Digraph> > {
     3088  public:
     3089    typedef _Digraph Digraph;
     3090    typedef DigraphAdaptorExtender<SplitNodesBase<Digraph> > Parent;
     3091
     3092    typedef typename Digraph::Node DigraphNode;
     3093    typedef typename Digraph::Arc DigraphArc;
    33323094
    33333095    typedef typename Parent::Node Node;
    33343096    typedef typename Parent::Arc Arc;
    33353097
    3336     /// \brief Constructor
     3098    /// \brief Constructor of the adaptor.
    33373099    ///
    33383100    /// Constructor of the adaptor.
    3339     SplitNodes(const DGR& g) {
    3340       Parent::initialize(g);
    3341     }
    3342 
    3343     /// \brief Returns \c true if the given node is an in-node.
    3344     ///
    3345     /// Returns \c true if the given node is an in-node.
     3101    SplitNodes(Digraph& g) {
     3102      Parent::setDigraph(g);
     3103    }
     3104
     3105    /// \brief Returns true when the node is in-node.
     3106    ///
     3107    /// Returns true when the node is in-node.
    33463108    static bool inNode(const Node& n) {
    33473109      return Parent::inNode(n);
    33483110    }
    33493111
    3350     /// \brief Returns \c true if the given node is an out-node.
    3351     ///
    3352     /// Returns \c true if the given node is an out-node.
     3112    /// \brief Returns true when the node is out-node.
     3113    ///
     3114    /// Returns true when the node is out-node.
    33533115    static bool outNode(const Node& n) {
    33543116      return Parent::outNode(n);
    33553117    }
    33563118
    3357     /// \brief Returns \c true if the given arc is an original arc.
    3358     ///
    3359     /// Returns \c true if the given arc is one of the arcs in the
    3360     /// original digraph.
     3119    /// \brief Returns true when the arc is arc in the original digraph.
     3120    ///
     3121    /// Returns true when the arc is arc in the original digraph.
    33613122    static bool origArc(const Arc& a) {
    33623123      return Parent::origArc(a);
    33633124    }
    33643125
    3365     /// \brief Returns \c true if the given arc is a bind arc.
    3366     ///
    3367     /// Returns \c true if the given arc is a bind arc, i.e. it connects
    3368     /// an in-node and an out-node.
     3126    /// \brief Returns true when the arc binds an in-node and an out-node.
     3127    ///
     3128    /// Returns true when the arc binds an in-node and an out-node.
    33693129    static bool bindArc(const Arc& a) {
    33703130      return Parent::bindArc(a);
    33713131    }
    33723132
    3373     /// \brief Returns the in-node created from the given original node.
    3374     ///
    3375     /// Returns the in-node created from the given original node.
     3133    /// \brief Gives back the in-node created from the \c node.
     3134    ///
     3135    /// Gives back the in-node created from the \c node.
    33763136    static Node inNode(const DigraphNode& n) {
    33773137      return Parent::inNode(n);
    33783138    }
    33793139
    3380     /// \brief Returns the out-node created from the given original node.
    3381     ///
    3382     /// Returns the out-node created from the given original node.
     3140    /// \brief Gives back the out-node created from the \c node.
     3141    ///
     3142    /// Gives back the out-node created from the \c node.
    33833143    static Node outNode(const DigraphNode& n) {
    33843144      return Parent::outNode(n);
    33853145    }
    33863146
    3387     /// \brief Returns the bind arc that corresponds to the given
    3388     /// original node.
    3389     ///
    3390     /// Returns the bind arc in the adaptor that corresponds to the given
    3391     /// original node, i.e. the arc connecting the in-node and out-node
    3392     /// of \c n.
     3147    /// \brief Gives back the arc binds the two part of the node.
     3148    ///
     3149    /// Gives back the arc binds the two part of the node.
    33933150    static Arc arc(const DigraphNode& n) {
    33943151      return Parent::arc(n);
    33953152    }
    33963153
    3397     /// \brief Returns the arc that corresponds to the given original arc.
    3398     ///
    3399     /// Returns the arc in the adaptor that corresponds to the given
    3400     /// original arc.
     3154    /// \brief Gives back the arc of the original arc.
     3155    ///
     3156    /// Gives back the arc of the original arc.
    34013157    static Arc arc(const DigraphArc& a) {
    34023158      return Parent::arc(a);
    34033159    }
    34043160
    3405     /// \brief Node map combined from two original node maps
    3406     ///
    3407     /// This map adaptor class adapts two node maps of the original digraph
    3408     /// to get a node map of the split digraph.
    3409     /// Its value type is inherited from the first node map type
    3410     /// (\c InNodeMap).
     3161    /// \brief NodeMap combined from two original NodeMap
     3162    ///
     3163    /// This class adapt two of the original digraph NodeMap to
     3164    /// get a node map on the adapted digraph.
    34113165    template <typename InNodeMap, typename OutNodeMap>
    34123166    class CombinedNodeMap {
    34133167    public:
    34143168
    3415       /// The key type of the map
    34163169      typedef Node Key;
    3417       /// The value type of the map
    34183170      typedef typename InNodeMap::Value Value;
    34193171
    3420       typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag;
    3421       typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue;
    3422       typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReturnValue;
    3423       typedef typename MapTraits<InNodeMap>::ReturnValue Reference;
    3424       typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference;
    3425 
    3426       /// Constructor
     3172      /// \brief Constructor
     3173      ///
     3174      /// Constructor.
    34273175      CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
    34283176        : _in_map(in_map), _out_map(out_map) {}
    34293177
    3430       /// Returns the value associated with the given key.
    3431       Value operator[](const Key& key) const {
    3432         if (SplitNodesBase<const DGR>::inNode(key)) {
     3178      /// \brief The subscript operator.
     3179      ///
     3180      /// The subscript operator.
     3181      Value& operator[](const Key& key) {
     3182        if (Parent::inNode(key)) {
    34333183          return _in_map[key];
    34343184        } else {
     
    34373187      }
    34383188
    3439       /// Returns a reference to the value associated with the given key.
    3440       Value& operator[](const Key& key) {
    3441         if (SplitNodesBase<const DGR>::inNode(key)) {
     3189      /// \brief The const subscript operator.
     3190      ///
     3191      /// The const subscript operator.
     3192      Value operator[](const Key& key) const {
     3193        if (Parent::inNode(key)) {
    34423194          return _in_map[key];
    34433195        } else {
     
    34463198      }
    34473199
    3448       /// Sets the value associated with the given key.
     3200      /// \brief The setter function of the map.
     3201      ///
     3202      /// The setter function of the map.
    34493203      void set(const Key& key, const Value& value) {
    3450         if (SplitNodesBase<const DGR>::inNode(key)) {
     3204        if (Parent::inNode(key)) {
    34513205          _in_map.set(key, value);
    34523206        } else {
     
    34633217
    34643218
    3465     /// \brief Returns a combined node map
    3466     ///
    3467     /// This function just returns a combined node map.
     3219    /// \brief Just gives back a combined node map
     3220    ///
     3221    /// Just gives back a combined node map
    34683222    template <typename InNodeMap, typename OutNodeMap>
    34693223    static CombinedNodeMap<InNodeMap, OutNodeMap>
     
    34913245    }
    34923246
    3493     /// \brief Arc map combined from an arc map and a node map of the
    3494     /// original digraph.
    3495     ///
    3496     /// This map adaptor class adapts an arc map and a node map of the
    3497     /// original digraph to get an arc map of the split digraph.
    3498     /// Its value type is inherited from the original arc map type
    3499     /// (\c ArcMap).
    3500     template <typename ArcMap, typename NodeMap>
     3247    /// \brief ArcMap combined from an original ArcMap and a NodeMap
     3248    ///
     3249    /// This class adapt an original ArcMap and a NodeMap to get an
     3250    /// arc map on the adapted digraph
     3251    template <typename DigraphArcMap, typename DigraphNodeMap>
    35013252    class CombinedArcMap {
    35023253    public:
    35033254
    3504       /// The key type of the map
    35053255      typedef Arc Key;
    3506       /// The value type of the map
    3507       typedef typename ArcMap::Value Value;
    3508 
    3509       typedef typename MapTraits<ArcMap>::ReferenceMapTag ReferenceMapTag;
    3510       typedef typename MapTraits<ArcMap>::ReturnValue ReturnValue;
    3511       typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReturnValue;
    3512       typedef typename MapTraits<ArcMap>::ReturnValue Reference;
    3513       typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReference;
    3514 
    3515       /// Constructor
    3516       CombinedArcMap(ArcMap& arc_map, NodeMap& node_map)
     3256      typedef typename DigraphArcMap::Value Value;
     3257
     3258      /// \brief Constructor
     3259      ///
     3260      /// Constructor.
     3261      CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)
    35173262        : _arc_map(arc_map), _node_map(node_map) {}
    35183263
    3519       /// Returns the value associated with the given key.
     3264      /// \brief The subscript operator.
     3265      ///
     3266      /// The subscript operator.
     3267      void set(const Arc& arc, const Value& val) {
     3268        if (Parent::origArc(arc)) {
     3269          _arc_map.set(arc, val);
     3270        } else {
     3271          _node_map.set(arc, val);
     3272        }
     3273      }
     3274
     3275      /// \brief The const subscript operator.
     3276      ///
     3277      /// The const subscript operator.
    35203278      Value operator[](const Key& arc) const {
    3521         if (SplitNodesBase<const DGR>::origArc(arc)) {
     3279        if (Parent::origArc(arc)) {
    35223280          return _arc_map[arc];
    35233281        } else {
     
    35263284      }
    35273285
    3528       /// Returns a reference to the value associated with the given key.
     3286      /// \brief The const subscript operator.
     3287      ///
     3288      /// The const subscript operator.
    35293289      Value& operator[](const Key& arc) {
    3530         if (SplitNodesBase<const DGR>::origArc(arc)) {
     3290        if (Parent::origArc(arc)) {
    35313291          return _arc_map[arc];
    35323292        } else {
     
    35353295      }
    35363296
    3537       /// Sets the value associated with the given key.
    3538       void set(const Arc& arc, const Value& val) {
    3539         if (SplitNodesBase<const DGR>::origArc(arc)) {
    3540           _arc_map.set(arc, val);
    3541         } else {
    3542           _node_map.set(arc, val);
    3543         }
    3544       }
    3545 
    35463297    private:
    3547       ArcMap& _arc_map;
    3548       NodeMap& _node_map;
     3298      DigraphArcMap& _arc_map;
     3299      DigraphNodeMap& _node_map;
    35493300    };
    35503301
    3551     /// \brief Returns a combined arc map
    3552     ///
    3553     /// This function just returns a combined arc map.
    3554     template <typename ArcMap, typename NodeMap>
    3555     static CombinedArcMap<ArcMap, NodeMap>
    3556     combinedArcMap(ArcMap& arc_map, NodeMap& node_map) {
    3557       return CombinedArcMap<ArcMap, NodeMap>(arc_map, node_map);
    3558     }
    3559 
    3560     template <typename ArcMap, typename NodeMap>
    3561     static CombinedArcMap<const ArcMap, NodeMap>
    3562     combinedArcMap(const ArcMap& arc_map, NodeMap& node_map) {
    3563       return CombinedArcMap<const ArcMap, NodeMap>(arc_map, node_map);
    3564     }
    3565 
    3566     template <typename ArcMap, typename NodeMap>
    3567     static CombinedArcMap<ArcMap, const NodeMap>
    3568     combinedArcMap(ArcMap& arc_map, const NodeMap& node_map) {
    3569       return CombinedArcMap<ArcMap, const NodeMap>(arc_map, node_map);
    3570     }
    3571 
    3572     template <typename ArcMap, typename NodeMap>
    3573     static CombinedArcMap<const ArcMap, const NodeMap>
    3574     combinedArcMap(const ArcMap& arc_map, const NodeMap& node_map) {
    3575       return CombinedArcMap<const ArcMap, const NodeMap>(arc_map, node_map);
     3302    /// \brief Just gives back a combined arc map
     3303    ///
     3304    /// Just gives back a combined arc map
     3305    template <typename DigraphArcMap, typename DigraphNodeMap>
     3306    static CombinedArcMap<DigraphArcMap, DigraphNodeMap>
     3307    combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
     3308      return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map);
     3309    }
     3310
     3311    template <typename DigraphArcMap, typename DigraphNodeMap>
     3312    static CombinedArcMap<const DigraphArcMap, DigraphNodeMap>
     3313    combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
     3314      return CombinedArcMap<const DigraphArcMap,
     3315        DigraphNodeMap>(arc_map, node_map);
     3316    }
     3317
     3318    template <typename DigraphArcMap, typename DigraphNodeMap>
     3319    static CombinedArcMap<DigraphArcMap, const DigraphNodeMap>
     3320    combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) {
     3321      return CombinedArcMap<DigraphArcMap,
     3322        const DigraphNodeMap>(arc_map, node_map);
     3323    }
     3324
     3325    template <typename DigraphArcMap, typename DigraphNodeMap>
     3326    static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap>
     3327    combinedArcMap(const DigraphArcMap& arc_map,
     3328                   const DigraphNodeMap& node_map) {
     3329      return CombinedArcMap<const DigraphArcMap,
     3330        const DigraphNodeMap>(arc_map, node_map);
    35763331    }
    35773332
    35783333  };
    35793334
    3580   /// \brief Returns a (read-only) SplitNodes adaptor
    3581   ///
    3582   /// This function just returns a (read-only) \ref SplitNodes adaptor.
    3583   /// \ingroup graph_adaptors
    3584   /// \relates SplitNodes
    3585   template<typename DGR>
    3586   SplitNodes<DGR>
    3587   splitNodes(const DGR& digraph) {
    3588     return SplitNodes<DGR>(digraph);
     3335  /// \brief Just gives back a node splitter
     3336  ///
     3337  /// Just gives back a node splitter
     3338  template<typename Digraph>
     3339  SplitNodes<Digraph>
     3340  splitNodes(const Digraph& digraph) {
     3341    return SplitNodes<Digraph>(digraph);
    35893342  }
    35903343
    3591 #undef LEMON_SCOPE_FIX
    35923344
    35933345} //namespace lemon
  • lemon/arg_parser.cc

    r463 r311  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/arg_parser.h

    r463 r311  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/assert.h

    r463 r290  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/base.cc

    r554 r220  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2424namespace lemon {
    2525
    26   float Tolerance<float>::def_epsilon = static_cast<float>(1e-4);
     26  float Tolerance<float>::def_epsilon = 1e-4;
    2727  double Tolerance<double>::def_epsilon = 1e-10;
    2828  long double Tolerance<long double>::def_epsilon = 1e-14;
  • lemon/bfs.h

    r463 r421  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    17421742    /// \pre Either \ref run(Node) "run()" or \ref init()
    17431743    /// must be called before using this function.
    1744     bool reached(Node v) const { return (*_reached)[v]; }
     1744    bool reached(Node v) { return (*_reached)[v]; }
    17451745
    17461746    ///@}
  • lemon/bin_heap.h

    r463 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/alteration_notifier.h

    r463 r373  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/array_map.h

    r463 r373  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/base_extender.h

    r463 r373  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/bezier.h

    r463 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/default_map.h

    r564 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    9797
    9898
    99 #if defined HAVE_LONG_LONG
     99#if defined __GNUC__ && !defined __STRICT_ANSI__
    100100
    101101  // long long
  • lemon/bits/enable_if.h

    r463 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/graph_adaptor_extender.h

    r478 r432  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    174174  };
    175175
     176
     177  /// \ingroup digraphbits
     178  ///
     179  /// \brief Extender for the GraphAdaptors
    176180  template <typename _Graph>
    177181  class GraphAdaptorExtender : public _Graph {
  • lemon/bits/graph_extender.h

    r463 r373  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/map_extender.h

    r463 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/path_dump.h

    r566 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    1919#ifndef LEMON_BITS_PRED_MAP_PATH_H
    2020#define LEMON_BITS_PRED_MAP_PATH_H
    21 
    22 #include <lemon/core.h>
    23 #include <lemon/concept_check.h>
    2421
    2522namespace lemon {
  • lemon/bits/traits.h

    r463 r372  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/variant.h

    r463 r432  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2222#include <lemon/assert.h>
    2323
    24 // \file
    25 // \brief Variant types
     24/// \file
     25/// \brief Variant types
    2626
    2727namespace lemon {
     
    3737
    3838
    39   // \brief Simple Variant type for two types
    40   //
    41   // Simple Variant type for two types. The Variant type is a type-safe
    42   // union. C++ has strong limitations for using unions, for
    43   // example you cannot store a type with non-default constructor or
    44   // destructor in a union. This class always knowns the current
    45   // state of the variant and it cares for the proper construction
    46   // and destruction.
     39  /// \brief Simple Variant type for two types
     40  ///
     41  /// Simple Variant type for two types. The Variant type is a type
     42  /// safe union. The C++ has strong limitations for using unions, by
     43  /// example we can not store type with non default constructor or
     44  /// destructor in an union. This class always knowns the current
     45  /// state of the variant and it cares for the proper construction
     46  /// and destruction.
    4747  template <typename _First, typename _Second>
    4848  class BiVariant {
    4949  public:
    5050
    51     // \brief The \c First type.
     51    /// \brief The \c First type.
    5252    typedef _First First;
    53     // \brief The \c Second type.
     53    /// \brief The \c Second type.
    5454    typedef _Second Second;
    5555
    56     // \brief Constructor
    57     //
    58     // This constructor initalizes to the default value of the \c First
    59     // type.
     56    /// \brief Constructor
     57    ///
     58    /// This constructor initalizes to the default value of the \c First
     59    /// type.
    6060    BiVariant() {
    6161      flag = true;
     
    6363    }
    6464
    65     // \brief Constructor
    66     //
    67     // This constructor initalizes to the given value of the \c First
    68     // type.
     65    /// \brief Constructor
     66    ///
     67    /// This constructor initalizes to the given value of the \c First
     68    /// type.
    6969    BiVariant(const First& f) {
    7070      flag = true;
     
    7272    }
    7373
    74     // \brief Constructor
    75     //
    76     // This constructor initalizes to the given value of the \c
    77     // Second type.
     74    /// \brief Constructor
     75    ///
     76    /// This constructor initalizes to the given value of the \c
     77    /// Second type.
    7878    BiVariant(const Second& s) {
    7979      flag = false;
     
    8181    }
    8282
    83     // \brief Copy constructor
    84     //
    85     // Copy constructor
     83    /// \brief Copy constructor
     84    ///
     85    /// Copy constructor
    8686    BiVariant(const BiVariant& bivariant) {
    8787      flag = bivariant.flag;
     
    9393    }
    9494
    95     // \brief Destrcutor
    96     //
    97     // Destructor
     95    /// \brief Destrcutor
     96    ///
     97    /// Destructor
    9898    ~BiVariant() {
    9999      destroy();
    100100    }
    101101
    102     // \brief Set to the default value of the \c First type.
    103     //
    104     // This function sets the variant to the default value of the \c
    105     // First type.
     102    /// \brief Set to the default value of the \c First type.
     103    ///
     104    /// This function sets the variant to the default value of the \c
     105    /// First type.
    106106    BiVariant& setFirst() {
    107107      destroy();
     
    111111    }
    112112
    113     // \brief Set to the given value of the \c First type.
    114     //
    115     // This function sets the variant to the given value of the \c
    116     // First type.
     113    /// \brief Set to the given value of the \c First type.
     114    ///
     115    /// This function sets the variant to the given value of the \c
     116    /// First type.
    117117    BiVariant& setFirst(const First& f) {
    118118      destroy();
     
    122122    }
    123123
    124     // \brief Set to the default value of the \c Second type.
    125     //
    126     // This function sets the variant to the default value of the \c
    127     // Second type.
     124    /// \brief Set to the default value of the \c Second type.
     125    ///
     126    /// This function sets the variant to the default value of the \c
     127    /// Second type.
    128128    BiVariant& setSecond() {
    129129      destroy();
     
    133133    }
    134134
    135     // \brief Set to the given value of the \c Second type.
    136     //
    137     // This function sets the variant to the given value of the \c
    138     // Second type.
     135    /// \brief Set to the given value of the \c Second type.
     136    ///
     137    /// This function sets the variant to the given value of the \c
     138    /// Second type.
    139139    BiVariant& setSecond(const Second& s) {
    140140      destroy();
     
    144144    }
    145145
    146     // \brief Operator form of the \c setFirst()
     146    /// \brief Operator form of the \c setFirst()
    147147    BiVariant& operator=(const First& f) {
    148148      return setFirst(f);
    149149    }
    150150
    151     // \brief Operator form of the \c setSecond()
     151    /// \brief Operator form of the \c setSecond()
    152152    BiVariant& operator=(const Second& s) {
    153153      return setSecond(s);
    154154    }
    155155
    156     // \brief Assign operator
     156    /// \brief Assign operator
    157157    BiVariant& operator=(const BiVariant& bivariant) {
    158158      if (this == &bivariant) return *this;
     
    167167    }
    168168
    169     // \brief Reference to the value
    170     //
    171     // Reference to the value of the \c First type.
    172     // \pre The BiVariant should store value of \c First type.
     169    /// \brief Reference to the value
     170    ///
     171    /// Reference to the value of the \c First type.
     172    /// \pre The BiVariant should store value of \c First type.
    173173    First& first() {
    174174      LEMON_DEBUG(flag, "Variant wrong state");
    175       return *reinterpret_cast<First*>(data);
    176     }
    177 
    178     // \brief Const reference to the value
    179     //
    180     // Const reference to the value of the \c First type.
    181     // \pre The BiVariant should store value of \c First type.
    182     const First& first() const {
     175      return *reinterpret_cast<First*>(data); 
     176    }
     177
     178    /// \brief Const reference to the value
     179    ///
     180    /// Const reference to the value of the \c First type.
     181    /// \pre The BiVariant should store value of \c First type.
     182    const First& first() const { 
    183183      LEMON_DEBUG(flag, "Variant wrong state");
    184       return *reinterpret_cast<const First*>(data);
    185     }
    186 
    187     // \brief Operator form of the \c first()
     184      return *reinterpret_cast<const First*>(data); 
     185    }
     186
     187    /// \brief Operator form of the \c first()
    188188    operator First&() { return first(); }
    189     // \brief Operator form of the const \c first()
     189    /// \brief Operator form of the const \c first()
    190190    operator const First&() const { return first(); }
    191191
    192     // \brief Reference to the value
    193     //
    194     // Reference to the value of the \c Second type.
    195     // \pre The BiVariant should store value of \c Second type.
    196     Second& second() {
     192    /// \brief Reference to the value
     193    ///
     194    /// Reference to the value of the \c Second type.
     195    /// \pre The BiVariant should store value of \c Second type.
     196    Second& second() { 
    197197      LEMON_DEBUG(!flag, "Variant wrong state");
    198       return *reinterpret_cast<Second*>(data);
    199     }
    200 
    201     // \brief Const reference to the value
    202     //
    203     // Const reference to the value of the \c Second type.
    204     // \pre The BiVariant should store value of \c Second type.
    205     const Second& second() const {
     198      return *reinterpret_cast<Second*>(data); 
     199    }
     200
     201    /// \brief Const reference to the value
     202    ///
     203    /// Const reference to the value of the \c Second type.
     204    /// \pre The BiVariant should store value of \c Second type.
     205    const Second& second() const { 
    206206      LEMON_DEBUG(!flag, "Variant wrong state");
    207       return *reinterpret_cast<const Second*>(data);
    208     }
    209 
    210     // \brief Operator form of the \c second()
     207      return *reinterpret_cast<const Second*>(data); 
     208    }
     209
     210    /// \brief Operator form of the \c second()
    211211    operator Second&() { return second(); }
    212     // \brief Operator form of the const \c second()
     212    /// \brief Operator form of the const \c second()
    213213    operator const Second&() const { return second(); }
    214214
    215     // \brief %True when the variant is in the first state
    216     //
    217     // %True when the variant stores value of the \c First type.
     215    /// \brief %True when the variant is in the first state
     216    ///
     217    /// %True when the variant stores value of the \c First type.
    218218    bool firstState() const { return flag; }
    219219
    220     // \brief %True when the variant is in the second state
    221     //
    222     // %True when the variant stores value of the \c Second type.
     220    /// \brief %True when the variant is in the second state
     221    ///
     222    /// %True when the variant stores value of the \c Second type.
    223223    bool secondState() const { return !flag; }
    224224
     
    290290  }
    291291
    292   // \brief Variant type
    293   //
    294   // Simple Variant type. The Variant type is a type-safe union.
    295   // C++ has strong limitations for using unions, for example you
    296   // cannot store type with non-default constructor or destructor in
    297   // a union. This class always knowns the current state of the
    298   // variant and it cares for the proper construction and
    299   // destruction.
    300   //
    301   // \param _num The number of the types which can be stored in the
    302   // variant type.
    303   // \param _TypeMap This class describes the types of the Variant. The
    304   // _TypeMap::Map<index>::Type should be a valid type for each index
    305   // in the range {0, 1, ..., _num - 1}. The \c VariantTypeMap is helper
    306   // class to define such type mappings up to 10 types.
    307   //
    308   // And the usage of the class:
    309   //\code
    310   // typedef Variant<3, VariantTypeMap<int, std::string, double> > MyVariant;
    311   // MyVariant var;
    312   // var.set<0>(12);
    313   // std::cout << var.get<0>() << std::endl;
    314   // var.set<1>("alpha");
    315   // std::cout << var.get<1>() << std::endl;
    316   // var.set<2>(0.75);
    317   // std::cout << var.get<2>() << std::endl;
    318   //\endcode
    319   //