COIN-OR::LEMON - Graph Library

Ignore:
Files:
35 added
1 deleted
42 edited

Legend:

Unmodified
Added
Removed
  • .hgignore

    r400 r564  
    2323lemon/stamp-h2
    2424doc/Doxyfile
     25cmake/cmake.version
    2526.dirstamp
    2627.libs/*
    2728.deps/*
    2829demo/*.eps
     30m4/libtool.m4
     31m4/ltoptions.m4
     32m4/ltsugar.m4
     33m4/ltversion.m4
     34m4/lt~obsolete.m4
    2935
    3036syntax: regexp
     
    3541^autom4te.cache/.*
    3642^build-aux/.*
    37 ^objs.*/.*
     43^.*objs.*/.*
    3844^test/[a-z_]*$
    3945^tools/[a-z-_]*$
    4046^demo/.*_demo$
    41 ^build/.*
     47^.*build.*/.*
    4248^doc/gen-images/.*
    4349CMakeFiles
  • CMakeLists.txt

    r274 r574  
    11CMAKE_MINIMUM_REQUIRED(VERSION 2.6)
    22
    3 SET(PROJECT_NAME "LEMON")
    4 SET(PROJECT_VERSION "hg-tip" CACHE STRING "The version string.")
     3IF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
     4  INCLUDE(${CMAKE_SOURCE_DIR}/cmake/version.cmake)
     5ELSE(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
     6  SET(PROJECT_NAME "LEMON")
     7  SET(PROJECT_VERSION "hg-tip" CACHE STRING "LEMON version string.")
     8ENDIF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
    59
    610PROJECT(${PROJECT_NAME})
     
    1014INCLUDE(FindDoxygen)
    1115INCLUDE(FindGhostscript)
     16FIND_PACKAGE(GLPK 4.33)
     17
     18ADD_DEFINITIONS(-DHAVE_CONFIG_H)
     19
     20IF(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
     27ENDIF(MSVC)
     28
     29IF(GLPK_FOUND)
     30  SET(HAVE_LP TRUE)
     31  SET(HAVE_MIP TRUE)
     32  SET(HAVE_GLPK TRUE)
     33ENDIF(GLPK_FOUND)
     34
     35INCLUDE(CheckTypeSize)
     36CHECK_TYPE_SIZE("long long" LONG_LONG)
    1237
    1338ENABLE_TESTING()
     
    1540ADD_SUBDIRECTORY(lemon)
    1641ADD_SUBDIRECTORY(demo)
     42ADD_SUBDIRECTORY(tools)
    1743ADD_SUBDIRECTORY(doc)
    1844ADD_SUBDIRECTORY(test)
    1945
    2046IF(WIN32)
    21   INSTALL(FILES ${CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico
    22     DESTINATION bin)
    23 ENDIF(WIN32)
    24 
    25 IF(WIN32)
    2647  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
    27   SET(CPACK_PACKAGE_VENDOR
    28     "EGRES - Egervary Research Group on Combinatorial Optimization")
     48  SET(CPACK_PACKAGE_VENDOR "EGRES")
    2949  SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
    3050    "LEMON - Library of Efficient Models and Optimization in Networks")
     
    3858    "${PROJECT_NAME} ${PROJECT_VERSION}")
    3959
    40   # Variables to generate a component-based installer.
    41   #SET(CPACK_COMPONENTS_ALL headers library html_documentation)
     60  SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
    4261
    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")
     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")
    4666
    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")
     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")
    5375
    54   #SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
     76  SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
    5577
    56   #SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
    57   #SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
    58   #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
     78  SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
     79  SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
     80  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
    5981
    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")
     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")
    6486
    65   #SET(CPACK_ALL_INSTALL_TYPES Full Developer)
     87  SET(CPACK_ALL_INSTALL_TYPES Full Developer)
    6688
    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)
     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)
    7092
    7193  SET(CPACK_GENERATOR "NSIS")
     
    79101  SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")
    80102  SET(CPACK_NSIS_CREATE_ICONS_EXTRA "
    81     CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\doc\\\\index.html\\\"
     103    CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\share\\\\doc\\\\index.html\\\"
    82104    ")
    83105  SET(CPACK_NSIS_DELETE_ICONS_EXTRA "
  • Makefile.am

    r375 r555  
    1313        m4/lx_check_soplex.m4 \
    1414        CMakeLists.txt \
    15         cmake
     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
    1621
    1722pkgconfigdir = $(libdir)/pkgconfig
  • cmake/FindGhostscript.cmake

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

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

    r225 r498  
    1 INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})
     1INCLUDE_DIRECTORIES(
     2  ${CMAKE_SOURCE_DIR}
     3  ${CMAKE_BINARY_DIR}
     4)
    25
    36LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
  • doc/CMakeLists.txt

    r347 r565  
    1010
    1111IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
     12  FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)
    1213  IF(UNIX)
    1314    ADD_CUSTOM_TARGET(html
     
    3637      WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR})
    3738  ENDIF(UNIX)
     39  INSTALL(
     40    DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
     41    DESTINATION share/doc
     42    COMPONENT html_documentation)
    3843ENDIF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
    39 
    40 INSTALL(
    41   DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
    42   DESTINATION doc
    43   COMPONENT html_documentation)
  • doc/groups.dox

    r463 r478  
    6363
    6464/**
    65 @defgroup graph_adaptors Adaptor Classes for graphs
     65@defgroup graph_adaptors Adaptor Classes for Graphs
    6666@ingroup graphs
    67 \brief This group contains several adaptor classes for digraphs and graphs
     67\brief Adaptor classes for digraphs and graphs
     68
     69This group contains several useful adaptor classes for digraphs and graphs.
    6870
    6971The main parts of LEMON are the different graph structures, generic
    70 graph algorithms, graph concepts which couple these, and graph
     72graph algorithms, graph concepts, which couple them, and graph
    7173adaptors. While the previous notions are more or less clear, the
    7274latter one needs further explanation. Graph adaptors are graph classes
     
    7476
    7577A short example makes this much clearer.  Suppose that we have an
    76 instance \c g of a directed graph type say ListDigraph and an algorithm
     78instance \c g of a directed graph type, say ListDigraph and an algorithm
    7779\code
    7880template <typename Digraph>
     
    8284(in time or in memory usage) to copy \c g with the reversed
    8385arcs.  In this case, an adaptor class is used, which (according
    84 to LEMON digraph concepts) works as a digraph.  The adaptor uses the
    85 original digraph structure and digraph operations when methods of the
    86 reversed oriented graph are called.  This means that the adaptor have
    87 minor memory usage, and do not perform sophisticated algorithmic
     86to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
     87The adaptor uses the original digraph structure and digraph operations when
     88methods of the reversed oriented graph are called.  This means that the adaptor
     89have minor memory usage, and do not perform sophisticated algorithmic
    8890actions.  The purpose of it is to give a tool for the cases when a
    8991graph have to be used in a specific alteration.  If this alteration is
    90 obtained by a usual construction like filtering the arc-set or
     92obtained by a usual construction like filtering the node or the arc set or
    9193considering a new orientation, then an adaptor is worthwhile to use.
    9294To come back to the reverse oriented graph, in this situation
     
    9799\code
    98100ListDigraph g;
    99 ReverseDigraph<ListGraph> rg(g);
     101ReverseDigraph<ListDigraph> rg(g);
    100102int result = algorithm(rg);
    101103\endcode
    102 After running the algorithm, the original graph \c g is untouched.
    103 This techniques gives rise to an elegant code, and based on stable
     104During running the algorithm, the original digraph \c g is untouched.
     105This techniques give rise to an elegant code, and based on stable
    104106graph adaptors, complex algorithms can be implemented easily.
    105107
    106 In flow, circulation and bipartite matching problems, the residual
     108In flow, circulation and matching problems, the residual
    107109graph is of particular importance. Combining an adaptor implementing
    108 this, shortest path algorithms and minimum mean cycle algorithms,
     110this with shortest path algorithms or minimum mean cycle algorithms,
    109111a range of weighted and cardinality optimization algorithms can be
    110112obtained. For other examples, the interested user is referred to the
     
    113115The behavior of graph adaptors can be very different. Some of them keep
    114116capabilities of the original graph while in other cases this would be
    115 meaningless. This means that the concepts that they are models of depend
    116 on the graph adaptor, and the wrapped graph(s).
    117 If an arc of \c rg is deleted, this is carried out by deleting the
    118 corresponding arc of \c g, thus the adaptor modifies the original graph.
    119 
    120 But for a residual graph, this operation has no sense.
     117meaningless. This means that the concepts that they meet depend
     118on the graph adaptor, and the wrapped graph.
     119For example, if an arc of a reversed digraph is deleted, this is carried
     120out by deleting the corresponding arc of the original digraph, thus the
     121adaptor modifies the original digraph.
     122However in case of a residual digraph, this operation has no sense.
     123
    121124Let us stand one more example here to simplify your work.
    122 RevGraphAdaptor has constructor
     125ReverseDigraph has constructor
    123126\code
    124127ReverseDigraph(Digraph& digraph);
    125128\endcode
    126 This means that in a situation, when a <tt>const ListDigraph&</tt>
     129This means that in a situation, when a <tt>const %ListDigraph&</tt>
    127130reference to a graph is given, then it have to be instantiated with
    128 <tt>Digraph=const ListDigraph</tt>.
     131<tt>Digraph=const %ListDigraph</tt>.
    129132\code
    130133int algorithm1(const ListDigraph& g) {
    131   RevGraphAdaptor<const ListDigraph> rg(g);
     134  ReverseDigraph<const ListDigraph> rg(g);
    132135  return algorithm2(rg);
    133136}
  • lemon/CMakeLists.txt

    r225 r562  
    1 INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})
     1INCLUDE_DIRECTORIES(
     2  ${CMAKE_SOURCE_DIR}
     3  ${CMAKE_BINARY_DIR}
     4)
    25
    3 ADD_LIBRARY(lemon
     6CONFIGURE_FILE(
     7  ${CMAKE_CURRENT_SOURCE_DIR}/config.h.cmake
     8  ${CMAKE_CURRENT_BINARY_DIR}/config.h
     9)
     10
     11SET(LEMON_SOURCES
    412  arg_parser.cc
    513  base.cc
    614  color.cc
    7   random.cc)
     15  lp_base.cc
     16  lp_skeleton.cc
     17  random.cc
     18  bits/windows.cc
     19)
     20
     21IF(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)
     29ENDIF(HAVE_GLPK)
     30
     31ADD_LIBRARY(lemon ${LEMON_SOURCES})
    832
    933INSTALL(
  • lemon/Makefile.am

    r463 r575  
    1111        lemon/base.cc \
    1212        lemon/color.cc \
    13         lemon/random.cc
     13        lemon/lp_base.cc \
     14        lemon/lp_skeleton.cc \
     15        lemon/random.cc \
     16        lemon/bits/windows.cc
    1417
    15 #lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS) $(AM_CXXFLAGS)
    16 #lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
     18
     19lemon_libemon_la_CXXFLAGS = \
     20        $(GLPK_CFLAGS) \
     21        $(CPLEX_CFLAGS) \
     22        $(SOPLEX_CXXFLAGS) \
     23        $(CLP_CXXFLAGS)
     24
     25lemon_libemon_la_LDFLAGS = \
     26        $(GLPK_LIBS) \
     27        $(CPLEX_LIBS) \
     28        $(SOPLEX_LIBS) \
     29        $(CLP_LIBS)
     30
     31if HAVE_GLPK
     32lemon_libemon_la_SOURCES += lemon/glpk.cc
     33endif
     34
     35if HAVE_CPLEX
     36lemon_libemon_la_SOURCES += lemon/cplex.cc
     37endif
     38
     39if HAVE_SOPLEX
     40lemon_libemon_la_SOURCES += lemon/soplex.cc
     41endif
     42
     43if HAVE_CLP
     44lemon_libemon_la_SOURCES += lemon/clp.cc
     45endif
    1746
    1847lemon_HEADERS += \
     
    2352        lemon/bin_heap.h \
    2453        lemon/circulation.h \
     54        lemon/clp.h \
    2555        lemon/color.h \
    2656        lemon/concept_check.h \
     57        lemon/connectivity.h \
    2758        lemon/counter.h \
    2859        lemon/core.h \
     60        lemon/cplex.h \
    2961        lemon/dfs.h \
    3062        lemon/dijkstra.h \
    3163        lemon/dim2.h \
    3264        lemon/dimacs.h \
     65        lemon/edge_set.h \
    3366        lemon/elevator.h \
    3467        lemon/error.h \
     68        lemon/euler.h \
    3569        lemon/full_graph.h \
     70        lemon/glpk.h \
    3671        lemon/graph_to_eps.h \
    3772        lemon/grid_graph.h \
     
    4277        lemon/lgf_writer.h \
    4378        lemon/list_graph.h \
     79        lemon/lp.h \
     80        lemon/lp_base.h \
     81        lemon/lp_skeleton.h \
     82        lemon/list_graph.h \
    4483        lemon/maps.h \
    4584        lemon/math.h \
    4685        lemon/max_matching.h \
     86        lemon/min_cost_arborescence.h \
    4787        lemon/nauty_reader.h \
    4888        lemon/path.h \
    4989        lemon/preflow.h \
     90        lemon/radix_sort.h \
    5091        lemon/random.h \
    5192        lemon/smart_graph.h \
     93        lemon/soplex.h \
    5294        lemon/suurballe.h \
    5395        lemon/time_measure.h \
    5496        lemon/tolerance.h \
    55         lemon/unionfind.h
     97        lemon/unionfind.h \
     98        lemon/bits/windows.h
    5699
    57100bits_HEADERS += \
     
    61104        lemon/bits/bezier.h \
    62105        lemon/bits/default_map.h \
     106        lemon/bits/edge_set_extender.h \
    63107        lemon/bits/enable_if.h \
    64108        lemon/bits/graph_adaptor_extender.h \
     
    66110        lemon/bits/map_extender.h \
    67111        lemon/bits/path_dump.h \
     112        lemon/bits/solver_bits.h \
    68113        lemon/bits/traits.h \
    69114        lemon/bits/variant.h \
  • lemon/adaptors.h

    r463 r566  
    2222/// \ingroup graph_adaptors
    2323/// \file
    24 /// \brief Several graph adaptors
     24/// \brief Adaptor classes for digraphs and graphs
    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>
    3334#include <lemon/tolerance.h>
    3435
     
    3738namespace lemon {
    3839
    39   template<typename _Digraph>
     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>
    4047  class DigraphAdaptorBase {
    4148  public:
    42     typedef _Digraph Digraph;
     49    typedef DGR Digraph;
    4350    typedef DigraphAdaptorBase Adaptor;
    44     typedef Digraph ParentDigraph;
    4551
    4652  protected:
    47     Digraph* _digraph;
     53    DGR* _digraph;
    4854    DigraphAdaptorBase() : _digraph(0) { }
    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;
     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;
    5662
    5763    void first(Node& i) const { _digraph->first(i); }
     
    6874    Node target(const Arc& a) const { return _digraph->target(a); }
    6975
    70     typedef NodeNumTagIndicator<Digraph> NodeNumTag;
     76    typedef NodeNumTagIndicator<DGR> NodeNumTag;
    7177    int nodeNum() const { return _digraph->nodeNum(); }
    7278
    73     typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
     79    typedef ArcNumTagIndicator<DGR> ArcNumTag;
    7480    int arcNum() const { return _digraph->arcNum(); }
    7581
    76     typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
    77     Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
     82    typedef FindArcTagIndicator<DGR> FindArcTag;
     83    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const {
    7884      return _digraph->findArc(u, v, prev);
    7985    }
     
    8288    Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
    8389
    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(); }
     90    void erase(const Node& n) { _digraph->erase(n); }
     91    void erase(const Arc& a) { _digraph->erase(a); }
     92
     93    void clear() { _digraph->clear(); }
    8894
    8995    int id(const Node& n) const { return _digraph->id(n); }
     
    96102    int maxArcId() const { return _digraph->maxArcId(); }
    97103
    98     typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
     104    typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
    99105    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
    100106
    101     typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier;
     107    typedef typename ItemSetTraits<DGR, Arc>::ItemNotifier ArcNotifier;
    102108    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
    103109
    104     template <typename _Value>
    105     class NodeMap : public Digraph::template NodeMap<_Value> {
     110    template <typename V>
     111    class NodeMap : public DGR::template NodeMap<V> {
    106112    public:
    107113
    108       typedef typename Digraph::template NodeMap<_Value> Parent;
     114      typedef typename DGR::template NodeMap<V> Parent;
    109115
    110116      explicit NodeMap(const Adaptor& adaptor)
    111117        : Parent(*adaptor._digraph) {}
    112118
    113       NodeMap(const Adaptor& adaptor, const _Value& value)
     119      NodeMap(const Adaptor& adaptor, const V& value)
    114120        : Parent(*adaptor._digraph, value) { }
    115121
     
    127133    };
    128134
    129     template <typename _Value>
    130     class ArcMap : public Digraph::template ArcMap<_Value> {
     135    template <typename V>
     136    class ArcMap : public DGR::template ArcMap<V> {
    131137    public:
    132138
    133       typedef typename Digraph::template ArcMap<_Value> Parent;
    134 
    135       explicit ArcMap(const Adaptor& adaptor)
     139      typedef typename DGR::template ArcMap<V> Parent;
     140
     141      explicit ArcMap(const DigraphAdaptorBase<DGR>& adaptor)
    136142        : Parent(*adaptor._digraph) {}
    137143
    138       ArcMap(const Adaptor& adaptor, const _Value& value)
     144      ArcMap(const DigraphAdaptorBase<DGR>& adaptor, const V& value)
    139145        : Parent(*adaptor._digraph, value) {}
    140146
     
    154160  };
    155161
    156   template<typename _Graph>
     162  template<typename GR>
    157163  class GraphAdaptorBase {
    158164  public:
    159     typedef _Graph Graph;
    160     typedef Graph ParentGraph;
     165    typedef GR Graph;
    161166
    162167  protected:
    163     Graph* _graph;
     168    GR* _graph;
    164169
    165170    GraphAdaptorBase() : _graph(0) {}
    166171
    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;
     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;
    175180
    176181    void first(Node& i) const { _graph->first(i); }
     
    199204    int nodeNum() const { return _graph->nodeNum(); }
    200205
     206    typedef ArcNumTagIndicator<Graph> ArcNumTag;
     207    int arcNum() const { return _graph->arcNum(); }
     208
    201209    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
    202     int arcNum() const { return _graph->arcNum(); }
    203210    int edgeNum() const { return _graph->edgeNum(); }
    204211
     212    typedef FindArcTagIndicator<Graph> FindArcTag;
     213    Arc findArc(const Node& u, const Node& v,
     214                const Arc& prev = INVALID) const {
     215      return _graph->findArc(u, v, prev);
     216    }
     217
    205218    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
    206     Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
    207       return _graph->findArc(u, v, prev);
    208     }
    209     Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) {
     219    Edge findEdge(const Node& u, const Node& v,
     220                  const Edge& prev = INVALID) const {
    210221      return _graph->findEdge(u, v, prev);
    211222    }
     
    234245    int maxEdgeId() const { return _graph->maxEdgeId(); }
    235246
    236     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
     247    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
    237248    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
    238249
    239     typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
     250    typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;
    240251    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
    241252
    242     typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
     253    typedef typename ItemSetTraits<GR, Edge>::ItemNotifier EdgeNotifier;
    243254    EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
    244255
    245     template <typename _Value>
    246     class NodeMap : public Graph::template NodeMap<_Value> {
     256    template <typename V>
     257    class NodeMap : public GR::template NodeMap<V> {
    247258    public:
    248       typedef typename Graph::template NodeMap<_Value> Parent;
    249       explicit NodeMap(const GraphAdaptorBase<Graph>& adapter)
     259      typedef typename GR::template NodeMap<V> Parent;
     260      explicit NodeMap(const GraphAdaptorBase<GR>& adapter)
    250261        : Parent(*adapter._graph) {}
    251       NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
     262      NodeMap(const GraphAdaptorBase<GR>& adapter, const V& value)
    252263        : Parent(*adapter._graph, value) {}
    253264
     
    265276    };
    266277
    267     template <typename _Value>
    268     class ArcMap : public Graph::template ArcMap<_Value> {
     278    template <typename V>
     279    class ArcMap : public GR::template ArcMap<V> {
    269280    public:
    270       typedef typename Graph::template ArcMap<_Value> Parent;
    271       explicit ArcMap(const GraphAdaptorBase<Graph>& adapter)
     281      typedef typename GR::template ArcMap<V> Parent;
     282      explicit ArcMap(const GraphAdaptorBase<GR>& adapter)
    272283        : Parent(*adapter._graph) {}
    273       ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
     284      ArcMap(const GraphAdaptorBase<GR>& adapter, const V& value)
    274285        : Parent(*adapter._graph, value) {}
    275286
     
    286297    };
    287298
    288     template <typename _Value>
    289     class EdgeMap : public Graph::template EdgeMap<_Value> {
     299    template <typename V>
     300    class EdgeMap : public GR::template EdgeMap<V> {
    290301    public:
    291       typedef typename Graph::template EdgeMap<_Value> Parent;
    292       explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)
     302      typedef typename GR::template EdgeMap<V> Parent;
     303      explicit EdgeMap(const GraphAdaptorBase<GR>& adapter)
    293304        : Parent(*adapter._graph) {}
    294       EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
     305      EdgeMap(const GraphAdaptorBase<GR>& adapter, const V& value)
    295306        : Parent(*adapter._graph, value) {}
    296307
     
    309320  };
    310321
    311   template <typename _Digraph>
    312   class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> {
    313   public:
    314     typedef _Digraph Digraph;
    315     typedef DigraphAdaptorBase<_Digraph> Parent;
     322  template <typename DGR>
     323  class ReverseDigraphBase : public DigraphAdaptorBase<DGR> {
     324  public:
     325    typedef DGR Digraph;
     326    typedef DigraphAdaptorBase<DGR> Parent;
    316327  protected:
    317328    ReverseDigraphBase() : Parent() { }
     
    331342    Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
    332343
    333     typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
     344    typedef FindArcTagIndicator<DGR> FindArcTag;
    334345    Arc findArc(const Node& u, const Node& v,
    335                 const Arc& prev = INVALID) {
     346                const Arc& prev = INVALID) const {
    336347      return Parent::findArc(v, u, prev);
    337348    }
     
    341352  /// \ingroup graph_adaptors
    342353  ///
    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>
     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
    352374  class ReverseDigraph :
    353     public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > {
    354   public:
    355     typedef _Digraph Digraph;
    356     typedef DigraphAdaptorExtender<
    357       ReverseDigraphBase<_Digraph> > Parent;
     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;
    358381  protected:
    359382    ReverseDigraph() { }
     
    362385    /// \brief Constructor
    363386    ///
    364     /// Creates a reverse digraph adaptor for the given digraph
    365     explicit ReverseDigraph(Digraph& digraph) {
    366       Parent::setDigraph(digraph);
     387    /// Creates a reverse digraph adaptor for the given digraph.
     388    explicit ReverseDigraph(DGR& digraph) {
     389      Parent::initialize(digraph);
    367390    }
    368391  };
    369392
    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);
     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);
    376401  }
    377402
    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;
     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;
    385410
    386411    typedef SubDigraphBase Adaptor;
    387     typedef DigraphAdaptorBase<_Digraph> Parent;
     412    typedef DigraphAdaptorBase<DGR> Parent;
    388413  protected:
    389     NodeFilterMap* _node_filter;
    390     ArcFilterMap* _arc_filter;
     414    NF* _node_filter;
     415    AF* _arc_filter;
    391416    SubDigraphBase()
    392417      : Parent(), _node_filter(0), _arc_filter(0) { }
    393418
    394     void setNodeFilterMap(NodeFilterMap& node_filter) {
     419    void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
     420      Parent::initialize(digraph);
    395421      _node_filter = &node_filter;
    396     }
    397     void setArcFilterMap(ArcFilterMap& arc_filter) {
    398       _arc_filter = &arc_filter;
     422      _arc_filter = &arc_filter;     
    399423    }
    400424
     
    458482    }
    459483
    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]; }
     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]; }
    468489
    469490    typedef False NodeNumTag;
    470     typedef False EdgeNumTag;
    471 
    472     typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
     491    typedef False ArcNumTag;
     492
     493    typedef FindArcTagIndicator<DGR> FindArcTag;
    473494    Arc findArc(const Node& source, const Node& target,
    474                 const Arc& prev = INVALID) {
     495                const Arc& prev = INVALID) const {
    475496      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
    476497        return INVALID;
     
    483504    }
    484505
    485     template <typename _Value>
    486     class NodeMap : public SubMapExtender<Adaptor,
    487       typename Parent::template NodeMap<_Value> > {
     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>)> {
    488512    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) {}
     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) {}
    497521
    498522    private:
     
    503527      template <typename CMap>
    504528      NodeMap& operator=(const CMap& cmap) {
    505         MapParent::operator=(cmap);
     529        Parent::operator=(cmap);
    506530        return *this;
    507531      }
    508532    };
    509533
    510     template <typename _Value>
    511     class ArcMap : public SubMapExtender<Adaptor,
    512       typename Parent::template ArcMap<_Value> > {
     534    template <typename V>
     535    class ArcMap
     536      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
     537              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
    513538    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) {}
     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) {}
    522547
    523548    private:
     
    528553      template <typename CMap>
    529554      ArcMap& operator=(const CMap& cmap) {
    530         MapParent::operator=(cmap);
     555        Parent::operator=(cmap);
    531556        return *this;
    532557      }
     
    535560  };
    536561
    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;
     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;
    544569
    545570    typedef SubDigraphBase Adaptor;
    546571    typedef DigraphAdaptorBase<Digraph> Parent;
    547572  protected:
    548     NodeFilterMap* _node_filter;
    549     ArcFilterMap* _arc_filter;
     573    NF* _node_filter;
     574    AF* _arc_filter;
    550575    SubDigraphBase()
    551576      : Parent(), _node_filter(0), _arc_filter(0) { }
    552577
    553     void setNodeFilterMap(NodeFilterMap& node_filter) {
     578    void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
     579      Parent::initialize(digraph);
    554580      _node_filter = &node_filter;
    555     }
    556     void setArcFilterMap(ArcFilterMap& arc_filter) {
    557       _arc_filter = &arc_filter;
     581      _arc_filter = &arc_filter;     
    558582    }
    559583
     
    601625    }
    602626
    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]; }
     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]; }
    611632
    612633    typedef False NodeNumTag;
    613     typedef False EdgeNumTag;
    614 
    615     typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
     634    typedef False ArcNumTag;
     635
     636    typedef FindArcTagIndicator<DGR> FindArcTag;
    616637    Arc findArc(const Node& source, const Node& target,
    617                 const Arc& prev = INVALID) {
     638                const Arc& prev = INVALID) const {
    618639      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
    619640        return INVALID;
     
    626647    }
    627648
    628     template <typename _Value>
    629     class NodeMap : public SubMapExtender<Adaptor,
    630       typename Parent::template NodeMap<_Value> > {
     649    template <typename V>
     650    class NodeMap
     651      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
     652          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
    631653    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) {}
     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) {}
    640662
    641663    private:
     
    646668      template <typename CMap>
    647669      NodeMap& operator=(const CMap& cmap) {
    648         MapParent::operator=(cmap);
     670        Parent::operator=(cmap);
    649671        return *this;
    650672      }
    651673    };
    652674
    653     template <typename _Value>
    654     class ArcMap : public SubMapExtender<Adaptor,
    655       typename Parent::template ArcMap<_Value> > {
     675    template <typename V>
     676    class ArcMap
     677      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
     678          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
    656679    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) {}
     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) {}
    665688
    666689    private:
     
    671694      template <typename CMap>
    672695      ArcMap& operator=(const CMap& cmap) {
    673         MapParent::operator=(cmap);
     696        Parent::operator=(cmap);
    674697        return *this;
    675698      }
     
    680703  /// \ingroup graph_adaptors
    681704  ///
    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.
     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.
    700733  ///
    701734  /// \see FilterNodes
    702735  /// \see FilterArcs
    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;
     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;
    718756
    719757    typedef typename Parent::Node Node;
     
    726764    /// \brief Constructor
    727765    ///
    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); }
     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); }
    776823
    777824  };
    778825
    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);
     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);
    787837  }
    788838
    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);
     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);
    795845  }
    796846
    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);
     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);
    803853  }
    804854
    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);
     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);
    811861  }
    812862
    813863
    814   template <typename _Graph, typename NodeFilterMap,
    815             typename EdgeFilterMap, bool _checked = true>
    816   class SubGraphBase : public GraphAdaptorBase<_Graph> {
    817   public:
    818     typedef _Graph Graph;
     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
    819871    typedef SubGraphBase Adaptor;
    820     typedef GraphAdaptorBase<_Graph> Parent;
     872    typedef GraphAdaptorBase<GR> Parent;
    821873  protected:
    822874
    823     NodeFilterMap* _node_filter_map;
    824     EdgeFilterMap* _edge_filter_map;
     875    NF* _node_filter;
     876    EF* _edge_filter;
    825877
    826878    SubGraphBase()
    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;
     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;
    834885    }
    835886
     
    842893    void first(Node& i) const {
    843894      Parent::first(i);
    844       while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
     895      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
    845896    }
    846897
    847898    void first(Arc& i) const {
    848899      Parent::first(i);
    849       while (i!=INVALID && (!(*_edge_filter_map)[i]
    850                             || !(*_node_filter_map)[Parent::source(i)]
    851                             || !(*_node_filter_map)[Parent::target(i)]))
     900      while (i!=INVALID && (!(*_edge_filter)[i]
     901                            || !(*_node_filter)[Parent::source(i)]
     902                            || !(*_node_filter)[Parent::target(i)]))
    852903        Parent::next(i);
    853904    }
     
    855906    void first(Edge& i) const {
    856907      Parent::first(i);
    857       while (i!=INVALID && (!(*_edge_filter_map)[i]
    858                             || !(*_node_filter_map)[Parent::u(i)]
    859                             || !(*_node_filter_map)[Parent::v(i)]))
     908      while (i!=INVALID && (!(*_edge_filter)[i]
     909                            || !(*_node_filter)[Parent::u(i)]
     910                            || !(*_node_filter)[Parent::v(i)]))
    860911        Parent::next(i);
    861912    }
     
    863914    void firstIn(Arc& i, const Node& n) const {
    864915      Parent::firstIn(i, n);
    865       while (i!=INVALID && (!(*_edge_filter_map)[i]
    866                             || !(*_node_filter_map)[Parent::source(i)]))
     916      while (i!=INVALID && (!(*_edge_filter)[i]
     917                            || !(*_node_filter)[Parent::source(i)]))
    867918        Parent::nextIn(i);
    868919    }
     
    870921    void firstOut(Arc& i, const Node& n) const {
    871922      Parent::firstOut(i, n);
    872       while (i!=INVALID && (!(*_edge_filter_map)[i]
    873                             || !(*_node_filter_map)[Parent::target(i)]))
     923      while (i!=INVALID && (!(*_edge_filter)[i]
     924                            || !(*_node_filter)[Parent::target(i)]))
    874925        Parent::nextOut(i);
    875926    }
     
    877928    void firstInc(Edge& i, bool& d, const Node& n) const {
    878929      Parent::firstInc(i, d, n);
    879       while (i!=INVALID && (!(*_edge_filter_map)[i]
    880                             || !(*_node_filter_map)[Parent::u(i)]
    881                             || !(*_node_filter_map)[Parent::v(i)]))
     930      while (i!=INVALID && (!(*_edge_filter)[i]
     931                            || !(*_node_filter)[Parent::u(i)]
     932                            || !(*_node_filter)[Parent::v(i)]))
    882933        Parent::nextInc(i, d);
    883934    }
     
    885936    void next(Node& i) const {
    886937      Parent::next(i);
    887       while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
     938      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
    888939    }
    889940
    890941    void next(Arc& i) const {
    891942      Parent::next(i);
    892       while (i!=INVALID && (!(*_edge_filter_map)[i]
    893                             || !(*_node_filter_map)[Parent::source(i)]
    894                             || !(*_node_filter_map)[Parent::target(i)]))
     943      while (i!=INVALID && (!(*_edge_filter)[i]
     944                            || !(*_node_filter)[Parent::source(i)]
     945                            || !(*_node_filter)[Parent::target(i)]))
    895946        Parent::next(i);
    896947    }
     
    898949    void next(Edge& i) const {
    899950      Parent::next(i);
    900       while (i!=INVALID && (!(*_edge_filter_map)[i]
    901                             || !(*_node_filter_map)[Parent::u(i)]
    902                             || !(*_node_filter_map)[Parent::v(i)]))
     951      while (i!=INVALID && (!(*_edge_filter)[i]
     952                            || !(*_node_filter)[Parent::u(i)]
     953                            || !(*_node_filter)[Parent::v(i)]))
    903954        Parent::next(i);
    904955    }
     
    906957    void nextIn(Arc& i) const {
    907958      Parent::nextIn(i);
    908       while (i!=INVALID && (!(*_edge_filter_map)[i]
    909                             || !(*_node_filter_map)[Parent::source(i)]))
     959      while (i!=INVALID && (!(*_edge_filter)[i]
     960                            || !(*_node_filter)[Parent::source(i)]))
    910961        Parent::nextIn(i);
    911962    }
     
    913964    void nextOut(Arc& i) const {
    914965      Parent::nextOut(i);
    915       while (i!=INVALID && (!(*_edge_filter_map)[i]
    916                             || !(*_node_filter_map)[Parent::target(i)]))
     966      while (i!=INVALID && (!(*_edge_filter)[i]
     967                            || !(*_node_filter)[Parent::target(i)]))
    917968        Parent::nextOut(i);
    918969    }
     
    920971    void nextInc(Edge& i, bool& d) const {
    921972      Parent::nextInc(i, d);
    922       while (i!=INVALID && (!(*_edge_filter_map)[i]
    923                             || !(*_node_filter_map)[Parent::u(i)]
    924                             || !(*_node_filter_map)[Parent::v(i)]))
     973      while (i!=INVALID && (!(*_edge_filter)[i]
     974                            || !(*_node_filter)[Parent::u(i)]
     975                            || !(*_node_filter)[Parent::v(i)]))
    925976        Parent::nextInc(i, d);
    926977    }
    927978
    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]; }
     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]; }
    936984
    937985    typedef False NodeNumTag;
     986    typedef False ArcNumTag;
    938987    typedef False EdgeNumTag;
    939988
     989    typedef FindArcTagIndicator<Graph> FindArcTag;
     990    Arc findArc(const Node& u, const Node& v,
     991                const Arc& prev = INVALID) const {
     992      if (!(*_node_filter)[u] || !(*_node_filter)[v]) {
     993        return INVALID;
     994      }
     995      Arc arc = Parent::findArc(u, v, prev);
     996      while (arc != INVALID && !(*_edge_filter)[arc]) {
     997        arc = Parent::findArc(u, v, arc);
     998      }
     999      return arc;
     1000    }
     1001
    9401002    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
    941     Arc findArc(const Node& u, const Node& v,
    942                 const Arc& prev = INVALID) {
    943       if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
     1003    Edge findEdge(const Node& u, const Node& v,
     1004                  const Edge& prev = INVALID) const {
     1005      if (!(*_node_filter)[u] || !(*_node_filter)[v]) {
    9441006        return INVALID;
    9451007      }
    946       Arc arc = Parent::findArc(u, v, prev);
    947       while (arc != INVALID && !(*_edge_filter_map)[arc]) {
    948         arc = Parent::findArc(u, v, arc);
    949       }
    950       return arc;
    951     }
    952     Edge findEdge(const Node& u, const Node& v,
    953                   const Edge& prev = INVALID) {
    954       if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
    955         return INVALID;
    956       }
    9571008      Edge edge = Parent::findEdge(u, v, prev);
    958       while (edge != INVALID && !(*_edge_filter_map)[edge]) {
     1009      while (edge != INVALID && !(*_edge_filter)[edge]) {
    9591010        edge = Parent::findEdge(u, v, edge);
    9601011      }
     
    9621013    }
    9631014
    964     template <typename _Value>
    965     class NodeMap : public SubMapExtender<Adaptor,
    966       typename Parent::template NodeMap<_Value> > {
     1015    template <typename V>
     1016    class NodeMap
     1017      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1018          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
    9671019    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) {}
     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) {}
    9761028
    9771029    private:
     
    9821034      template <typename CMap>
    9831035      NodeMap& operator=(const CMap& cmap) {
    984         MapParent::operator=(cmap);
     1036        Parent::operator=(cmap);
    9851037        return *this;
    9861038      }
    9871039    };
    9881040
    989     template <typename _Value>
    990     class ArcMap : public SubMapExtender<Adaptor,
    991       typename Parent::template ArcMap<_Value> > {
     1041    template <typename V>
     1042    class ArcMap
     1043      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1044          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
    9921045    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) {}
     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) {}
    10011054
    10021055    private:
     
    10071060      template <typename CMap>
    10081061      ArcMap& operator=(const CMap& cmap) {
    1009         MapParent::operator=(cmap);
     1062        Parent::operator=(cmap);
    10101063        return *this;
    10111064      }
    10121065    };
    10131066
    1014     template <typename _Value>
    1015     class EdgeMap : public SubMapExtender<Adaptor,
    1016       typename Parent::template EdgeMap<_Value> > {
     1067    template <typename V>
     1068    class EdgeMap
     1069      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1070        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
    10171071    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) {}
     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) {}
    10271081
    10281082    private:
     
    10331087      template <typename CMap>
    10341088      EdgeMap& operator=(const CMap& cmap) {
    1035         MapParent::operator=(cmap);
     1089        Parent::operator=(cmap);
    10361090        return *this;
    10371091      }
     
    10401094  };
    10411095
    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;
     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
    10471104    typedef SubGraphBase Adaptor;
    1048     typedef GraphAdaptorBase<_Graph> Parent;
     1105    typedef GraphAdaptorBase<GR> Parent;
    10491106  protected:
    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;
     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;
    10601116    }
    10611117
     
    10681124    void first(Node& i) const {
    10691125      Parent::first(i);
    1070       while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
     1126      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
    10711127    }
    10721128
    10731129    void first(Arc& i) const {
    10741130      Parent::first(i);
    1075       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
     1131      while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
    10761132    }
    10771133
    10781134    void first(Edge& i) const {
    10791135      Parent::first(i);
    1080       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
     1136      while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
    10811137    }
    10821138
    10831139    void firstIn(Arc& i, const Node& n) const {
    10841140      Parent::firstIn(i, n);
    1085       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
     1141      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i);
    10861142    }
    10871143
    10881144    void firstOut(Arc& i, const Node& n) const {
    10891145      Parent::firstOut(i, n);
    1090       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
     1146      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i);
    10911147    }
    10921148
    10931149    void firstInc(Edge& i, bool& d, const Node& n) const {
    10941150      Parent::firstInc(i, d, n);
    1095       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
     1151      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d);
    10961152    }
    10971153
    10981154    void next(Node& i) const {
    10991155      Parent::next(i);
    1100       while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
     1156      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
    11011157    }
    11021158    void next(Arc& i) const {
    11031159      Parent::next(i);
    1104       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
     1160      while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
    11051161    }
    11061162    void next(Edge& i) const {
    11071163      Parent::next(i);
    1108       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
     1164      while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
    11091165    }
    11101166    void nextIn(Arc& i) const {
    11111167      Parent::nextIn(i);
    1112       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
     1168      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i);
    11131169    }
    11141170
    11151171    void nextOut(Arc& i) const {
    11161172      Parent::nextOut(i);
    1117       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
     1173      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i);
    11181174    }
    11191175    void nextInc(Edge& i, bool& d) const {
    11201176      Parent::nextInc(i, d);
    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]; }
     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]; }
    11321185
    11331186    typedef False NodeNumTag;
     1187    typedef False ArcNumTag;
    11341188    typedef False EdgeNumTag;
    11351189
     1190    typedef FindArcTagIndicator<Graph> FindArcTag;
     1191    Arc findArc(const Node& u, const Node& v,
     1192                const Arc& prev = INVALID) const {
     1193      Arc arc = Parent::findArc(u, v, prev);
     1194      while (arc != INVALID && !(*_edge_filter)[arc]) {
     1195        arc = Parent::findArc(u, v, arc);
     1196      }
     1197      return arc;
     1198    }
     1199
    11361200    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
    1137     Arc findArc(const Node& u, const Node& v,
    1138                 const Arc& prev = INVALID) {
    1139       Arc arc = Parent::findArc(u, v, prev);
    1140       while (arc != INVALID && !(*_edge_filter_map)[arc]) {
    1141         arc = Parent::findArc(u, v, arc);
    1142       }
    1143       return arc;
    1144     }
    11451201    Edge findEdge(const Node& u, const Node& v,
    1146                   const Edge& prev = INVALID) {
     1202                  const Edge& prev = INVALID) const {
    11471203      Edge edge = Parent::findEdge(u, v, prev);
    1148       while (edge != INVALID && !(*_edge_filter_map)[edge]) {
     1204      while (edge != INVALID && !(*_edge_filter)[edge]) {
    11491205        edge = Parent::findEdge(u, v, edge);
    11501206      }
     
    11521208    }
    11531209
    1154     template <typename _Value>
    1155     class NodeMap : public SubMapExtender<Adaptor,
    1156       typename Parent::template NodeMap<_Value> > {
     1210    template <typename V>
     1211    class NodeMap
     1212      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1213          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
    11571214    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) {}
     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) {}
    11661223
    11671224    private:
     
    11721229      template <typename CMap>
    11731230      NodeMap& operator=(const CMap& cmap) {
    1174         MapParent::operator=(cmap);
     1231        Parent::operator=(cmap);
    11751232        return *this;
    11761233      }
    11771234    };
    11781235
    1179     template <typename _Value>
    1180     class ArcMap : public SubMapExtender<Adaptor,
    1181       typename Parent::template ArcMap<_Value> > {
     1236    template <typename V>
     1237    class ArcMap
     1238      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1239          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
    11821240    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) {}
     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) {}
    11911249
    11921250    private:
     
    11971255      template <typename CMap>
    11981256      ArcMap& operator=(const CMap& cmap) {
    1199         MapParent::operator=(cmap);
     1257        Parent::operator=(cmap);
    12001258        return *this;
    12011259      }
    12021260    };
    12031261
    1204     template <typename _Value>
    1205     class EdgeMap : public SubMapExtender<Adaptor,
    1206       typename Parent::template EdgeMap<_Value> > {
     1262    template <typename V>
     1263    class EdgeMap
     1264      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1265        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
    12071266    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) {}
     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) {}
    12171276
    12181277    private:
     
    12231282      template <typename CMap>
    12241283      EdgeMap& operator=(const CMap& cmap) {
    1225         MapParent::operator=(cmap);
     1284        Parent::operator=(cmap);
    12261285        return *this;
    12271286      }
     
    12321291  /// \ingroup graph_adaptors
    12331292  ///
    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.
     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.
    12531322  ///
    12541323  /// \see FilterNodes
    12551324  /// \see FilterEdges
    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;
     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;
    12651345
    12661346    typedef typename Parent::Node Node;
     
    12731353    /// \brief Constructor
    12741354    ///
    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); }
     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
    13231413  };
    13241414
    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);
     1415  /// \brief Returns a read-only SubGraph adaptor
     1416  ///
     1417  /// This function just returns a read-only \ref SubGraph adaptor.
     1418  /// \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);
    13321425  }
    13331426
    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);
     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);
    13401432  }
    13411433
    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);
     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);
    13481439  }
    13491440
    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);
     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);
    13561446  }
    13571447
     1448
    13581449  /// \ingroup graph_adaptors
    13591450  ///
    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.
     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.
    13801476#ifdef DOXYGEN
    1381   template<typename _Digraph,
    1382            typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
    1383            bool _checked = true>
     1477  template<typename GR, typename NF>
     1478  class FilterNodes {
    13841479#else
    1385   template<typename _Digraph,
    1386            typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
    1387            bool _checked = true,
     1480  template<typename GR,
     1481           typename NF = typename GR::template NodeMap<bool>,
    13881482           typename Enable = void>
     1483  class FilterNodes :
     1484    public DigraphAdaptorExtender<
     1485      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
     1486                     true> > {
    13891487#endif
    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;
     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;
    14011496
    14021497    typedef typename Parent::Node Node;
    14031498
    14041499  protected:
    1405     ConstMap<typename Digraph::Arc, bool> const_true_map;
    1406 
    1407     FilterNodes() : const_true_map(true) {
    1408       Parent::setArcFilterMap(const_true_map);
    1409     }
     1500    ConstMap<typename Digraph::Arc, Const<bool, true> > const_true_map;
     1501
     1502    FilterNodes() : const_true_map() {}
    14101503
    14111504  public:
     
    14131506    /// \brief Constructor
    14141507    ///
    1415     /// Creates an adaptor for the given digraph or graph with
     1508    /// Creates a subgraph for the given digraph or graph with the
    14161509    /// given node filter map.
    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); }
     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); }
    14431541
    14441542  };
    14451543
    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;
     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;
    14561557
    14571558    typedef typename Parent::Node Node;
    14581559  protected:
    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); }
     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); }
    14771575
    14781576  };
    14791577
    14801578
    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);
     1579  /// \brief Returns a read-only FilterNodes adaptor
     1580  ///
     1581  /// This function just returns a read-only \ref FilterNodes adaptor.
     1582  /// \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);
    14881588  }
    14891589
    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);
     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);
    14941594  }
    14951595
    14961596  /// \ingroup graph_adaptors
    14971597  ///
    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>
     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> >
    15101627  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;
     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;
    15191641
    15201642    typedef typename Parent::Arc Arc;
    15211643
    15221644  protected:
    1523     ConstMap<typename Digraph::Node, bool> const_true_map;
    1524 
    1525     FilterArcs() : const_true_map(true) {
    1526       Parent::setNodeFilterMap(const_true_map);
    1527     }
     1645    ConstMap<typename DGR::Node, Const<bool, true> > const_true_map;
     1646
     1647    FilterArcs() : const_true_map() {}
    15281648
    15291649  public:
     
    15311651    /// \brief Constructor
    15321652    ///
    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); }
     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); }
    15611685
    15621686  };
    15631687
    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);
     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);
    15711697  }
    15721698
    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);
     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);
    15771703  }
    15781704
    15791705  /// \ingroup graph_adaptors
    15801706  ///
    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>
     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> >
    15931736  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;
     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
    16011751    typedef typename Parent::Edge Edge;
     1752
    16021753  protected:
    1603     ConstMap<typename Graph::Node, bool> const_true_map;
     1754    ConstMap<typename GR::Node, Const<bool, true> > const_true_map;
    16041755
    16051756    FilterEdges() : const_true_map(true) {
     
    16111762    /// \brief Constructor
    16121763    ///
    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); }
     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); }
    16411796
    16421797  };
    16431798
    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);
     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);
    16511808  }
    16521809
    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);
     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);
    16571814  }
    16581815
    1659   template <typename _Digraph>
     1816
     1817  template <typename DGR>
    16601818  class UndirectorBase {
    16611819  public:
    1662     typedef _Digraph Digraph;
     1820    typedef DGR Digraph;
    16631821    typedef UndirectorBase Adaptor;
    16641822
     
    16951853      }
    16961854    };
    1697 
    1698 
    16991855
    17001856    void first(Node& n) const {
     
    18462002
    18472003    typedef NodeNumTagIndicator<Digraph> NodeNumTag;
    1848     int nodeNum() const { return 2 * _digraph->arcNum(); }
    1849     typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
     2004    int nodeNum() const { return _digraph->nodeNum(); }
     2005
     2006    typedef ArcNumTagIndicator<Digraph> ArcNumTag;
    18502007    int arcNum() const { return 2 * _digraph->arcNum(); }
     2008
     2009    typedef ArcNumTag EdgeNumTag;
    18512010    int edgeNum() const { return _digraph->arcNum(); }
    18522011
    1853     typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
     2012    typedef FindArcTagIndicator<Digraph> FindArcTag;
    18542013    Arc findArc(Node s, Node t, Arc p = INVALID) const {
    18552014      if (p == INVALID) {
     
    18702029    }
    18712030
     2031    typedef FindArcTag FindEdgeTag;
    18722032    Edge findEdge(Node s, Node t, Edge p = INVALID) const {
    18732033      if (s != t) {
     
    18772037          arc = _digraph->findArc(t, s);
    18782038          if (arc != INVALID) return arc;
    1879         } else if (_digraph->s(p) == s) {
     2039        } else if (_digraph->source(p) == s) {
    18802040          Edge arc = _digraph->findArc(s, t, p);
    18812041          if (arc != INVALID) return arc;
     
    18942054  private:
    18952055
    1896     template <typename _Value>
     2056    template <typename V>
    18972057    class ArcMapBase {
    18982058    private:
    18992059
    1900       typedef typename Digraph::template ArcMap<_Value> MapImpl;
     2060      typedef typename DGR::template ArcMap<V> MapImpl;
    19012061
    19022062    public:
     
    19042064      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
    19052065
    1906       typedef _Value Value;
     2066      typedef V Value;
    19072067      typedef Arc Key;
    1908 
    1909       ArcMapBase(const Adaptor& adaptor) :
     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) :
    19102074        _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
    19112075
    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) {
     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) {
    19162081        if (direction(a)) {
    1917           _forward.set(a, v);
     2082          _forward.set(a, value);
    19182083        } else {
    1919           _backward.set(a, v);
     2084          _backward.set(a, value);
    19202085        }
    19212086      }
    19222087
    1923       typename MapTraits<MapImpl>::ConstReturnValue
    1924       operator[](const Arc& a) const {
     2088      ConstReturnValue operator[](const Arc& a) const {
    19252089        if (direction(a)) {
    19262090          return _forward[a];
     
    19302094      }
    19312095
    1932       typename MapTraits<MapImpl>::ReturnValue
    1933       operator[](const Arc& a) {
     2096      ReturnValue operator[](const Arc& a) {
    19342097        if (direction(a)) {
    19352098          return _forward[a];
     
    19472110  public:
    19482111
    1949     template <typename _Value>
    1950     class NodeMap : public Digraph::template NodeMap<_Value> {
     2112    template <typename V>
     2113    class NodeMap : public DGR::template NodeMap<V> {
    19512114    public:
    19522115
    1953       typedef _Value Value;
    1954       typedef typename Digraph::template NodeMap<Value> Parent;
    1955 
    1956       explicit NodeMap(const Adaptor& adaptor)
     2116      typedef V Value;
     2117      typedef typename DGR::template NodeMap<Value> Parent;
     2118
     2119      explicit NodeMap(const UndirectorBase<DGR>& adaptor)
    19572120        : Parent(*adaptor._digraph) {}
    19582121
    1959       NodeMap(const Adaptor& adaptor, const _Value& value)
     2122      NodeMap(const UndirectorBase<DGR>& adaptor, const V& value)
    19602123        : Parent(*adaptor._digraph, value) { }
    19612124
     
    19732136    };
    19742137
    1975     template <typename _Value>
     2138    template <typename V>
    19762139    class ArcMap
    1977       : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
     2140      : public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> >
    19782141    {
    19792142    public:
    1980       typedef _Value Value;
    1981       typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
    1982 
    1983       ArcMap(const Adaptor& adaptor)
     2143      typedef V Value;
     2144      typedef SubMapExtender<Adaptor, ArcMapBase<V> > Parent;
     2145
     2146      explicit ArcMap(const UndirectorBase<DGR>& adaptor)
    19842147        : Parent(adaptor) {}
    19852148
    1986       ArcMap(const Adaptor& adaptor, const Value& value)
     2149      ArcMap(const UndirectorBase<DGR>& adaptor, const V& value)
    19872150        : Parent(adaptor, value) {}
    19882151
     
    19992162    };
    20002163
    2001     template <typename _Value>
    2002     class EdgeMap : public Digraph::template ArcMap<_Value> {
     2164    template <typename V>
     2165    class EdgeMap : public Digraph::template ArcMap<V> {
    20032166    public:
    20042167
    2005       typedef _Value Value;
    2006       typedef typename Digraph::template ArcMap<Value> Parent;
    2007 
    2008       explicit EdgeMap(const Adaptor& adaptor)
     2168      typedef V Value;
     2169      typedef typename Digraph::template ArcMap<V> Parent;
     2170
     2171      explicit EdgeMap(const UndirectorBase<DGR>& adaptor)
    20092172        : Parent(*adaptor._digraph) {}
    20102173
    2011       EdgeMap(const Adaptor& adaptor, const Value& value)
     2174      EdgeMap(const UndirectorBase<DGR>& adaptor, const V& value)
    20122175        : Parent(*adaptor._digraph, value) {}
    20132176
     
    20252188    };
    20262189
    2027     typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
     2190    typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
    20282191    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
    20292192
     2193    typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
     2194    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
     2195
    20302196  protected:
    20312197
    20322198    UndirectorBase() : _digraph(0) {}
    20332199
    2034     Digraph* _digraph;
    2035 
    2036     void setDigraph(Digraph& digraph) {
     2200    DGR* _digraph;
     2201
     2202    void initialize(DGR& digraph) {
    20372203      _digraph = &digraph;
    20382204    }
     
    20422208  /// \ingroup graph_adaptors
    20432209  ///
    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;
     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;
    20602242  protected:
    20612243    Undirector() { }
     
    20642246    /// \brief Constructor
    20652247    ///
    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>
     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>
    20762260    class CombinedArcMap {
    20772261    public:
    20782262
    2079       typedef _ForwardMap ForwardMap;
    2080       typedef _BackwardMap BackwardMap;
     2263      /// The key type of the map
     2264      typedef typename Parent::Arc Key;
     2265      /// The value type of the map
     2266      typedef typename ForwardMap::Value Value;
    20812267
    20822268      typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
    20832269
    2084       typedef typename ForwardMap::Value Value;
    2085       typedef typename Parent::Arc Key;
    2086 
    2087       /// \brief Constructor
    2088       ///
     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
    20892275      /// Constructor
    20902276      CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
    20912277        : _forward(&forward), _backward(&backward) {}
    20922278
    2093 
    2094       /// \brief Sets the value associated with a key.
    2095       ///
    2096       /// Sets the value associated with a key.
     2279      /// Sets the value associated with the given key.
    20972280      void set(const Key& e, const Value& a) {
    20982281        if (Parent::direction(e)) {
     
    21032286      }
    21042287
    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 {
     2288      /// Returns the value associated with the given key.
     2289      ConstReturnValue operator[](const Key& e) const {
    21102290        if (Parent::direction(e)) {
    21112291          return (*_forward)[e];
     
    21152295      }
    21162296
    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) {
     2297      /// Returns a reference to the value associated with the given key.
     2298      ReturnValue operator[](const Key& e) {
    21222299        if (Parent::direction(e)) {
    21232300          return (*_forward)[e];
     
    21342311    };
    21352312
    2136     /// \brief Just gives back a combined arc map
    2137     ///
    2138     /// Just gives back a combined arc map
     2313    /// \brief Returns a combined arc map
     2314    ///
     2315    /// This function just returns a combined arc map.
    21392316    template <typename ForwardMap, typename BackwardMap>
    21402317    static CombinedArcMap<ForwardMap, BackwardMap>
     
    21662343  };
    21672344
    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);
     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);
    21752353  }
    21762354
    2177   template <typename _Graph, typename _DirectionMap>
     2355
     2356  template <typename GR, typename DM>
    21782357  class OrienterBase {
    21792358  public:
    21802359
    2181     typedef _Graph Graph;
    2182     typedef _DirectionMap DirectionMap;
    2183 
    2184     typedef typename Graph::Node Node;
    2185     typedef typename Graph::Edge Arc;
     2360    typedef GR Graph;
     2361    typedef DM DirectionMap;
     2362
     2363    typedef typename GR::Node Node;
     2364    typedef typename GR::Edge Arc;
    21862365
    21872366    void reverseArc(const Arc& arc) {
     
    21922371    void first(Arc& i) const { _graph->first(i); }
    21932372    void firstIn(Arc& i, const Node& n) const {
    2194       bool d;
     2373      bool d = true;
    21952374      _graph->firstInc(i, d, n);
    21962375      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
    21972376    }
    21982377    void firstOut(Arc& i, const Node& n ) const {
    2199       bool d;
     2378      bool d = true;
    22002379      _graph->firstInc(i, d, n);
    22012380      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
     
    22252404    int nodeNum() const { return _graph->nodeNum(); }
    22262405
    2227     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
     2406    typedef EdgeNumTagIndicator<Graph> ArcNumTag;
    22282407    int arcNum() const { return _graph->edgeNum(); }
    22292408
    2230     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
     2409    typedef FindEdgeTagIndicator<Graph> FindArcTag;
    22312410    Arc findArc(const Node& u, const Node& v,
    2232                 const Arc& prev = INVALID) {
    2233       Arc arc = prev;
    2234       bool d = arc == INVALID ? true : (*_direction)[arc];
    2235       if (d) {
     2411                const Arc& prev = INVALID) const {
     2412      Arc arc = _graph->findEdge(u, v, prev);
     2413      while (arc != INVALID && source(arc) != u) {
    22362414        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);
    22452415      }
    22462416      return arc;
     
    22522422
    22532423    Arc addArc(const Node& u, const Node& v) {
    2254       Arc arc = _graph->addArc(u, v);
    2255       _direction->set(arc, _graph->source(arc) == u);
     2424      Arc arc = _graph->addEdge(u, v);
     2425      _direction->set(arc, _graph->u(arc) == u);
    22562426      return arc;
    22572427    }
     
    22712441    int maxArcId() const { return _graph->maxEdgeId(); }
    22722442
    2273     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
     2443    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
    22742444    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
    22752445
    2276     typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
     2446    typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;
    22772447    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
    22782448
    2279     template <typename _Value>
    2280     class NodeMap : public _Graph::template NodeMap<_Value> {
     2449    template <typename V>
     2450    class NodeMap : public GR::template NodeMap<V> {
    22812451    public:
    22822452
    2283       typedef typename _Graph::template NodeMap<_Value> Parent;
    2284 
    2285       explicit NodeMap(const OrienterBase& adapter)
     2453      typedef typename GR::template NodeMap<V> Parent;
     2454
     2455      explicit NodeMap(const OrienterBase<GR, DM>& adapter)
    22862456        : Parent(*adapter._graph) {}
    22872457
    2288       NodeMap(const OrienterBase& adapter, const _Value& value)
     2458      NodeMap(const OrienterBase<GR, DM>& adapter, const V& value)
    22892459        : Parent(*adapter._graph, value) {}
    22902460
     
    23022472    };
    23032473
    2304     template <typename _Value>
    2305     class ArcMap : public _Graph::template EdgeMap<_Value> {
     2474    template <typename V>
     2475    class ArcMap : public GR::template EdgeMap<V> {
    23062476    public:
    23072477
    2308       typedef typename Graph::template EdgeMap<_Value> Parent;
    2309 
    2310       explicit ArcMap(const OrienterBase& adapter)
     2478      typedef typename Graph::template EdgeMap<V> Parent;
     2479
     2480      explicit ArcMap(const OrienterBase<GR, DM>& adapter)
    23112481        : Parent(*adapter._graph) { }
    23122482
    2313       ArcMap(const OrienterBase& adapter, const _Value& value)
     2483      ArcMap(const OrienterBase<GR, DM>& adapter, const V& value)
    23142484        : Parent(*adapter._graph, value) { }
    23152485
     
    23302500  protected:
    23312501    Graph* _graph;
    2332     DirectionMap* _direction;
    2333 
    2334     void setDirectionMap(DirectionMap& direction) {
     2502    DM* _direction;
     2503
     2504    void initialize(GR& graph, DM& direction) {
     2505      _graph = &graph;
    23352506      _direction = &direction;
    23362507    }
    23372508
    2338     void setGraph(Graph& graph) {
    2339       _graph = &graph;
    2340     }
    2341 
    23422509  };
    23432510
    23442511  /// \ingroup graph_adaptors
    23452512  ///
    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> >
     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> >
    23622545  class Orienter :
    2363     public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > {
    2364   public:
    2365     typedef _Graph Graph;
    2366     typedef DigraphAdaptorExtender<
    2367       OrienterBase<_Graph, DirectionMap> > Parent;
     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;
    23682556    typedef typename Parent::Arc Arc;
    23692557  protected:
     
    23712559  public:
    23722560
    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.
     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.
    23842573    void reverseArc(const Arc& a) {
    23852574      Parent::reverseArc(a);
     
    23872576  };
    23882577
    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);
     2578  /// \brief Returns a read-only Orienter adaptor
     2579  ///
     2580  /// This function just returns a read-only \ref Orienter adaptor.
     2581  /// \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);
    23962587  }
    23972588
    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);
     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);
    24022593  }
    24032594
    24042595  namespace _adaptor_bits {
    24052596
    2406     template<typename _Digraph,
    2407              typename _CapacityMap = typename _Digraph::template ArcMap<int>,
    2408              typename _FlowMap = _CapacityMap,
    2409              typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
     2597    template <typename DGR, typename CM, typename FM, typename TL>
    24102598    class ResForwardFilter {
    24112599    public:
    24122600
    2413       typedef _Digraph Digraph;
    2414       typedef _CapacityMap CapacityMap;
    2415       typedef _FlowMap FlowMap;
    2416       typedef _Tolerance Tolerance;
    2417 
    2418       typedef typename Digraph::Arc Key;
     2601      typedef typename DGR::Arc Key;
    24192602      typedef bool Value;
    24202603
    24212604    private:
    24222605
    2423       const CapacityMap* _capacity;
    2424       const FlowMap* _flow;
    2425       Tolerance _tolerance;
     2606      const CM* _capacity;
     2607      const FM* _flow;
     2608      TL _tolerance;
     2609
    24262610    public:
    24272611
    2428       ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,
    2429                        const Tolerance& tolerance = Tolerance())
     2612      ResForwardFilter(const CM& capacity, const FM& flow,
     2613                       const TL& tolerance = TL())
    24302614        : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
    24312615
    2432       bool operator[](const typename Digraph::Arc& a) const {
     2616      bool operator[](const typename DGR::Arc& a) const {
    24332617        return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
    24342618      }
    24352619    };
    24362620
    2437     template<typename _Digraph,
    2438              typename _CapacityMap = typename _Digraph::template ArcMap<int>,
    2439              typename _FlowMap = _CapacityMap,
    2440              typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
     2621    template<typename DGR,typename CM, typename FM, typename TL>
    24412622    class ResBackwardFilter {
    24422623    public:
    24432624
    2444       typedef _Digraph Digraph;
    2445       typedef _CapacityMap CapacityMap;
    2446       typedef _FlowMap FlowMap;
    2447       typedef _Tolerance Tolerance;
    2448 
    2449       typedef typename Digraph::Arc Key;
     2625      typedef typename DGR::Arc Key;
    24502626      typedef bool Value;
    24512627
    24522628    private:
    24532629
    2454       const CapacityMap* _capacity;
    2455       const FlowMap* _flow;
    2456       Tolerance _tolerance;
     2630      const CM* _capacity;
     2631      const FM* _flow;
     2632      TL _tolerance;
    24572633
    24582634    public:
    24592635
    2460       ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,
    2461                         const Tolerance& tolerance = Tolerance())
     2636      ResBackwardFilter(const CM& capacity, const FM& flow,
     2637                        const TL& tolerance = TL())
    24622638        : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
    24632639
    2464       bool operator[](const typename Digraph::Arc& a) const {
     2640      bool operator[](const typename DGR::Arc& a) const {
    24652641        return _tolerance.positive((*_flow)[a]);
    24662642      }
     
    24712647  /// \ingroup graph_adaptors
    24722648  ///
    2473   /// \brief An adaptor for composing the residual graph for directed
     2649  /// \brief Adaptor class for composing the residual digraph for directed
    24742650  /// flow and circulation problems.
    24752651  ///
    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> > >
     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
    25102704  {
    25112705  public:
    25122706
    2513     typedef _Digraph Digraph;
    2514     typedef _CapacityMap CapacityMap;
    2515     typedef _FlowMap FlowMap;
    2516     typedef _Tolerance Tolerance;
     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;
    25172715
    25182716    typedef typename CapacityMap::Value Value;
    2519     typedef Residual Adaptor;
     2717    typedef ResidualDigraph Adaptor;
    25202718
    25212719  protected:
     
    25232721    typedef Undirector<const Digraph> Undirected;
    25242722
    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;
     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;
    25302730
    25312731    typedef typename Undirected::
    2532     template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
    2533 
    2534     typedef FilterArcs<Undirected, ArcFilter> Parent;
     2732      template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
     2733
     2734    typedef SubDigraph<Undirected, NodeFilter, ArcFilter> Parent;
    25352735
    25362736    const CapacityMap* _capacity;
     
    25382738
    25392739    Undirected _graph;
     2740    NodeFilter _node_filter;
    25402741    ForwardFilter _forward_filter;
    25412742    BackwardFilter _backward_filter;
     
    25442745  public:
    25452746
    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),
     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(),
    25532755        _forward_filter(capacity, flow, tolerance),
    25542756        _backward_filter(capacity, flow, tolerance),
    25552757        _arc_filter(_forward_filter, _backward_filter)
    25562758    {
    2557       Parent::setDigraph(_graph);
    2558       Parent::setArcFilterMap(_arc_filter);
     2759      Parent::initialize(_graph, _node_filter, _arc_filter);
    25592760    }
    25602761
    25612762    typedef typename Parent::Arc Arc;
    25622763
    2563     /// \brief Gives back the residual capacity of the arc.
    2564     ///
    2565     /// Gives back the residual capacity of the arc.
     2764    /// \brief Returns the residual capacity of the given arc.
     2765    ///
     2766    /// Returns the residual capacity of the given arc.
    25662767    Value residualCapacity(const Arc& a) const {
    25672768      if (Undirected::direction(a)) {
     
    25722773    }
    25732774
    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.
     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.
    25792780    void augment(const Arc& a, const Value& v) const {
    25802781      if (Undirected::direction(a)) {
     
    25852786    }
    25862787
    2587     /// \brief Returns the direction of the arc.
    2588     ///
    2589     /// Returns true when the arc is same oriented as the original arc.
     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.
    25902792    static bool forward(const Arc& a) {
    25912793      return Undirected::direction(a);
    25922794    }
    25932795
    2594     /// \brief Returns the direction of the arc.
    2595     ///
    2596     /// Returns true when the arc is opposite oriented as the original arc.
     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.
    25972800    static bool backward(const Arc& a) {
    25982801      return !Undirected::direction(a);
    25992802    }
    26002803
    2601     /// \brief Gives back the forward oriented residual arc.
    2602     ///
    2603     /// Gives back the forward oriented residual arc.
     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.
    26042808    static Arc forward(const typename Digraph::Arc& a) {
    26052809      return Undirected::direct(a, true);
    26062810    }
    26072811
    2608     /// \brief Gives back the backward oriented residual arc.
    2609     ///
    2610     /// Gives back the backward oriented residual arc.
     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.
    26112816    static Arc backward(const typename Digraph::Arc& a) {
    26122817      return Undirected::direct(a, false);
     
    26152820    /// \brief Residual capacity map.
    26162821    ///
    2617     /// In generic residual graph the residual capacity can be obtained
    2618     /// as a map.
     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.
    26192825    class ResidualCapacity {
    26202826    protected:
    26212827      const Adaptor* _adaptor;
    26222828    public:
    2623       /// The Key type
     2829      /// The key type of the map
    26242830      typedef Arc Key;
    2625       /// The Value type
    2626       typedef typename _CapacityMap::Value Value;
     2831      /// The value type of the map
     2832      typedef typename CapacityMap::Value Value;
    26272833
    26282834      /// Constructor
    2629       ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}
    2630 
    2631       /// \e
     2835      ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)
     2836        : _adaptor(&adaptor) {}
     2837
     2838      /// Returns the value associated with the given residual arc
    26322839      Value operator[](const Arc& a) const {
    26332840        return _adaptor->residualCapacity(a);
     
    26362843    };
    26372844
     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
    26382852  };
    26392853
    2640   template <typename _Digraph>
     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>
    26412867  class SplitNodesBase {
    26422868  public:
    26432869
    2644     typedef _Digraph Digraph;
    2645     typedef DigraphAdaptorBase<const _Digraph> Parent;
     2870    typedef DGR Digraph;
     2871    typedef DigraphAdaptorBase<const DGR> Parent;
    26462872    typedef SplitNodesBase Adaptor;
    26472873
    2648     typedef typename Digraph::Node DigraphNode;
    2649     typedef typename Digraph::Arc DigraphArc;
     2874    typedef typename DGR::Node DigraphNode;
     2875    typedef typename DGR::Arc DigraphArc;
    26502876
    26512877    class Node;
     
    28853111
    28863112    typedef True NodeNumTag;
    2887 
    28883113    int nodeNum() const {
    28893114      return  2 * countNodes(*_digraph);
    28903115    }
    28913116
    2892     typedef True EdgeNumTag;
     3117    typedef True ArcNumTag;
    28933118    int arcNum() const {
    28943119      return countArcs(*_digraph) + countNodes(*_digraph);
    28953120    }
    28963121
    2897     typedef True FindEdgeTag;
     3122    typedef True FindArcTag;
    28983123    Arc findArc(const Node& u, const Node& v,
    28993124                const Arc& prev = INVALID) const {
    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           }
     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);
    29063129        }
    2907       } else {
    2908         if (inNode(v)) {
    2909           return Arc(::lemon::findArc(*_digraph, u, v, prev));
    2910         }
     3130      }
     3131      else if (outNode(u) && inNode(v)) {
     3132        return Arc(::lemon::findArc(*_digraph, u, v, prev));
    29113133      }
    29123134      return INVALID;
     
    29153137  private:
    29163138
    2917     template <typename _Value>
     3139    template <typename V>
    29183140    class NodeMapBase
    2919       : public MapTraits<typename Parent::template NodeMap<_Value> > {
    2920       typedef typename Parent::template NodeMap<_Value> NodeImpl;
     3141      : public MapTraits<typename Parent::template NodeMap<V> > {
     3142      typedef typename Parent::template NodeMap<V> NodeImpl;
    29213143    public:
    29223144      typedef Node Key;
    2923       typedef _Value Value;
    2924 
    2925       NodeMapBase(const Adaptor& adaptor)
     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)
    29263153        : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
    2927       NodeMapBase(const Adaptor& adaptor, const Value& value)
     3154      NodeMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)
    29283155        : _in_map(*adaptor._digraph, value),
    29293156          _out_map(*adaptor._digraph, value) {}
    29303157
    2931       void set(const Node& key, const Value& val) {
    2932         if (Adaptor::inNode(key)) { _in_map.set(key, val); }
     3158      void set(const Node& key, const V& val) {
     3159        if (SplitNodesBase<DGR>::inNode(key)) { _in_map.set(key, val); }
    29333160        else {_out_map.set(key, val); }
    29343161      }
    29353162
    2936       typename MapTraits<NodeImpl>::ReturnValue
    2937       operator[](const Node& key) {
    2938         if (Adaptor::inNode(key)) { return _in_map[key]; }
     3163      ReturnValue operator[](const Node& key) {
     3164        if (SplitNodesBase<DGR>::inNode(key)) { return _in_map[key]; }
    29393165        else { return _out_map[key]; }
    29403166      }
    29413167
    2942       typename MapTraits<NodeImpl>::ConstReturnValue
    2943       operator[](const Node& key) const {
     3168      ConstReturnValue operator[](const Node& key) const {
    29443169        if (Adaptor::inNode(key)) { return _in_map[key]; }
    29453170        else { return _out_map[key]; }
     
    29503175    };
    29513176
    2952     template <typename _Value>
     3177    template <typename V>
    29533178    class ArcMapBase
    2954       : public MapTraits<typename Parent::template ArcMap<_Value> > {
    2955       typedef typename Parent::template ArcMap<_Value> ArcImpl;
    2956       typedef typename Parent::template NodeMap<_Value> NodeImpl;
     3179      : public MapTraits<typename Parent::template ArcMap<V> > {
     3180      typedef typename Parent::template ArcMap<V> ArcImpl;
     3181      typedef typename Parent::template NodeMap<V> NodeImpl;
    29573182    public:
    29583183      typedef Arc Key;
    2959       typedef _Value Value;
    2960 
    2961       ArcMapBase(const Adaptor& adaptor)
     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)
    29623192        : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
    2963       ArcMapBase(const Adaptor& adaptor, const Value& value)
     3193      ArcMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)
    29643194        : _arc_map(*adaptor._digraph, value),
    29653195          _node_map(*adaptor._digraph, value) {}
    29663196
    2967       void set(const Arc& key, const Value& val) {
    2968         if (Adaptor::origArc(key)) {
    2969           _arc_map.set(key._item.first(), val);
     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);
    29703200        } else {
    2971           _node_map.set(key._item.second(), val);
     3201          _node_map.set(static_cast<const DigraphNode&>(key), val);
    29723202        }
    29733203      }
    29743204
    2975       typename MapTraits<ArcImpl>::ReturnValue
    2976       operator[](const Arc& key) {
    2977         if (Adaptor::origArc(key)) {
    2978           return _arc_map[key._item.first()];
     3205      ReturnValue operator[](const Arc& key) {
     3206        if (SplitNodesBase<DGR>::origArc(key)) {
     3207          return _arc_map[static_cast<const DigraphArc&>(key)];
    29793208        } else {
    2980           return _node_map[key._item.second()];
     3209          return _node_map[static_cast<const DigraphNode&>(key)];
    29813210        }
    29823211      }
    29833212
    2984       typename MapTraits<ArcImpl>::ConstReturnValue
    2985       operator[](const Arc& key) const {
    2986         if (Adaptor::origArc(key)) {
    2987           return _arc_map[key._item.first()];
     3213      ConstReturnValue operator[](const Arc& key) const {
     3214        if (SplitNodesBase<DGR>::origArc(key)) {
     3215          return _arc_map[static_cast<const DigraphArc&>(key)];
    29883216        } else {
    2989           return _node_map[key._item.second()];
     3217          return _node_map[static_cast<const DigraphNode&>(key)];
    29903218        }
    29913219      }
     
    29983226  public:
    29993227
    3000     template <typename _Value>
     3228    template <typename V>
    30013229    class NodeMap
    3002       : public SubMapExtender<Adaptor, NodeMapBase<_Value> >
     3230      : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> >
    30033231    {
    30043232    public:
    3005       typedef _Value Value;
    3006       typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent;
    3007 
    3008       NodeMap(const Adaptor& adaptor)
     3233      typedef V Value;
     3234      typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<Value> > Parent;
     3235
     3236      NodeMap(const SplitNodesBase<DGR>& adaptor)
    30093237        : Parent(adaptor) {}
    30103238
    3011       NodeMap(const Adaptor& adaptor, const Value& value)
     3239      NodeMap(const SplitNodesBase<DGR>& adaptor, const V& value)
    30123240        : Parent(adaptor, value) {}
    30133241
     
    30243252    };
    30253253
    3026     template <typename _Value>
     3254    template <typename V>
    30273255    class ArcMap
    3028       : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
     3256      : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> >
    30293257    {
    30303258    public:
    3031       typedef _Value Value;
    3032       typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
    3033 
    3034       ArcMap(const Adaptor& adaptor)
     3259      typedef V Value;
     3260      typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<Value> > Parent;
     3261
     3262      ArcMap(const SplitNodesBase<DGR>& adaptor)
    30353263        : Parent(adaptor) {}
    30363264
    3037       ArcMap(const Adaptor& adaptor, const Value& value)
     3265      ArcMap(const SplitNodesBase<DGR>& adaptor, const V& value)
    30383266        : Parent(adaptor, value) {}
    30393267
     
    30543282    SplitNodesBase() : _digraph(0) {}
    30553283
    3056     Digraph* _digraph;
    3057 
    3058     void setDigraph(Digraph& digraph) {
     3284    DGR* _digraph;
     3285
     3286    void initialize(Digraph& digraph) {
    30593287      _digraph = &digraph;
    30603288    }
     
    30643292  /// \ingroup graph_adaptors
    30653293  ///
    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>
     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
    30863323  class SplitNodes
    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;
     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;
    30943332
    30953333    typedef typename Parent::Node Node;
    30963334    typedef typename Parent::Arc Arc;
    30973335
    3098     /// \brief Constructor of the adaptor.
     3336    /// \brief Constructor
    30993337    ///
    31003338    /// Constructor of the adaptor.
    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.
     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.
    31083346    static bool inNode(const Node& n) {
    31093347      return Parent::inNode(n);
    31103348    }
    31113349
    3112     /// \brief Returns true when the node is out-node.
    3113     ///
    3114     /// Returns true when the node is out-node.
     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.
    31153353    static bool outNode(const Node& n) {
    31163354      return Parent::outNode(n);
    31173355    }
    31183356
    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.
     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.
    31223361    static bool origArc(const Arc& a) {
    31233362      return Parent::origArc(a);
    31243363    }
    31253364
    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.
     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.
    31293369    static bool bindArc(const Arc& a) {
    31303370      return Parent::bindArc(a);
    31313371    }
    31323372
    3133     /// \brief Gives back the in-node created from the \c node.
    3134     ///
    3135     /// Gives back the in-node created from the \c node.
     3373    /// \brief Returns the in-node created from the given original node.
     3374    ///
     3375    /// Returns the in-node created from the given original node.
    31363376    static Node inNode(const DigraphNode& n) {
    31373377      return Parent::inNode(n);
    31383378    }
    31393379
    3140     /// \brief Gives back the out-node created from the \c node.
    3141     ///
    3142     /// Gives back the out-node created from the \c node.
     3380    /// \brief Returns the out-node created from the given original node.
     3381    ///
     3382    /// Returns the out-node created from the given original node.
    31433383    static Node outNode(const DigraphNode& n) {
    31443384      return Parent::outNode(n);
    31453385    }
    31463386
    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.
     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.
    31503393    static Arc arc(const DigraphNode& n) {
    31513394      return Parent::arc(n);
    31523395    }
    31533396
    3154     /// \brief Gives back the arc of the original arc.
    3155     ///
    3156     /// Gives back the arc of the original arc.
     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.
    31573401    static Arc arc(const DigraphArc& a) {
    31583402      return Parent::arc(a);
    31593403    }
    31603404
    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.
     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).
    31653411    template <typename InNodeMap, typename OutNodeMap>
    31663412    class CombinedNodeMap {
    31673413    public:
    31683414
     3415      /// The key type of the map
    31693416      typedef Node Key;
     3417      /// The value type of the map
    31703418      typedef typename InNodeMap::Value Value;
    31713419
    3172       /// \brief Constructor
    3173       ///
    3174       /// Constructor.
     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
    31753427      CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
    31763428        : _in_map(in_map), _out_map(out_map) {}
    31773429
    3178       /// \brief The subscript operator.
    3179       ///
    3180       /// The subscript operator.
    3181       Value& operator[](const Key& key) {
    3182         if (Parent::inNode(key)) {
     3430      /// Returns the value associated with the given key.
     3431      Value operator[](const Key& key) const {
     3432        if (SplitNodesBase<const DGR>::inNode(key)) {
    31833433          return _in_map[key];
    31843434        } else {
     
    31873437      }
    31883438
    3189       /// \brief The const subscript operator.
    3190       ///
    3191       /// The const subscript operator.
    3192       Value operator[](const Key& key) const {
    3193         if (Parent::inNode(key)) {
     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)) {
    31943442          return _in_map[key];
    31953443        } else {
     
    31983446      }
    31993447
    3200       /// \brief The setter function of the map.
    3201       ///
    3202       /// The setter function of the map.
     3448      /// Sets the value associated with the given key.
    32033449      void set(const Key& key, const Value& value) {
    3204         if (Parent::inNode(key)) {
     3450        if (SplitNodesBase<const DGR>::inNode(key)) {
    32053451          _in_map.set(key, value);
    32063452        } else {
     
    32173463
    32183464
    3219     /// \brief Just gives back a combined node map
    3220     ///
    3221     /// Just gives back a combined node map
     3465    /// \brief Returns a combined node map
     3466    ///
     3467    /// This function just returns a combined node map.
    32223468    template <typename InNodeMap, typename OutNodeMap>
    32233469    static CombinedNodeMap<InNodeMap, OutNodeMap>
     
    32453491    }
    32463492
    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>
     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>
    32523501    class CombinedArcMap {
    32533502    public:
    32543503
     3504      /// The key type of the map
    32553505      typedef Arc Key;
    3256       typedef typename DigraphArcMap::Value Value;
    3257 
    3258       /// \brief Constructor
    3259       ///
    3260       /// Constructor.
    3261       CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)
     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)
    32623517        : _arc_map(arc_map), _node_map(node_map) {}
    32633518
    3264       /// \brief The subscript operator.
    3265       ///
    3266       /// The subscript operator.
     3519      /// Returns the value associated with the given key.
     3520      Value operator[](const Key& arc) const {
     3521        if (SplitNodesBase<const DGR>::origArc(arc)) {
     3522          return _arc_map[arc];
     3523        } else {
     3524          return _node_map[arc];
     3525        }
     3526      }
     3527
     3528      /// Returns a reference to the value associated with the given key.
     3529      Value& operator[](const Key& arc) {
     3530        if (SplitNodesBase<const DGR>::origArc(arc)) {
     3531          return _arc_map[arc];
     3532        } else {
     3533          return _node_map[arc];
     3534        }
     3535      }
     3536
     3537      /// Sets the value associated with the given key.
    32673538      void set(const Arc& arc, const Value& val) {
    3268         if (Parent::origArc(arc)) {
     3539        if (SplitNodesBase<const DGR>::origArc(arc)) {
    32693540          _arc_map.set(arc, val);
    32703541        } else {
     
    32733544      }
    32743545
    3275       /// \brief The const subscript operator.
    3276       ///
    3277       /// The const subscript operator.
    3278       Value operator[](const Key& arc) const {
    3279         if (Parent::origArc(arc)) {
    3280           return _arc_map[arc];
    3281         } else {
    3282           return _node_map[arc];
    3283         }
    3284       }
    3285 
    3286       /// \brief The const subscript operator.
    3287       ///
    3288       /// The const subscript operator.
    3289       Value& operator[](const Key& arc) {
    3290         if (Parent::origArc(arc)) {
    3291           return _arc_map[arc];
    3292         } else {
    3293           return _node_map[arc];
    3294         }
    3295       }
    3296 
    32973546    private:
    3298       DigraphArcMap& _arc_map;
    3299       DigraphNodeMap& _node_map;
     3547      ArcMap& _arc_map;
     3548      NodeMap& _node_map;
    33003549    };
    33013550
    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);
     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);
    33313576    }
    33323577
    33333578  };
    33343579
    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);
     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);
    33423589  }
    33433590
     3591#undef LEMON_SCOPE_FIX
    33443592
    33453593} //namespace lemon
  • lemon/base.cc

    r463 r554  
    2424namespace lemon {
    2525
    26   float Tolerance<float>::def_epsilon = 1e-4;
     26  float Tolerance<float>::def_epsilon = static_cast<float>(1e-4);
    2727  double Tolerance<double>::def_epsilon = 1e-10;
    2828  long double Tolerance<long double>::def_epsilon = 1e-14;
  • lemon/bits/default_map.h

    r463 r564  
    9797
    9898
    99 #if defined __GNUC__ && !defined __STRICT_ANSI__
     99#if defined HAVE_LONG_LONG
    100100
    101101  // long long
  • lemon/bits/graph_adaptor_extender.h

    r463 r478  
    174174  };
    175175
    176 
    177   /// \ingroup digraphbits
    178   ///
    179   /// \brief Extender for the GraphAdaptors
    180176  template <typename _Graph>
    181177  class GraphAdaptorExtender : public _Graph {
  • lemon/bits/path_dump.h

    r463 r576  
    1717 */
    1818
    19 #ifndef LEMON_BITS_PRED_MAP_PATH_H
    20 #define LEMON_BITS_PRED_MAP_PATH_H
     19#ifndef LEMON_BITS_PATH_DUMP_H
     20#define LEMON_BITS_PATH_DUMP_H
     21
     22#include <lemon/core.h>
     23#include <lemon/concept_check.h>
    2124
    2225namespace lemon {
  • lemon/concepts/digraph.h

    r463 r576  
    1717 */
    1818
    19 #ifndef LEMON_CONCEPT_DIGRAPH_H
    20 #define LEMON_CONCEPT_DIGRAPH_H
     19#ifndef LEMON_CONCEPTS_DIGRAPH_H
     20#define LEMON_CONCEPTS_DIGRAPH_H
    2121
    2222///\ingroup graph_concepts
     
    485485
    486486
    487 #endif // LEMON_CONCEPT_DIGRAPH_H
     487#endif
  • lemon/concepts/graph.h

    r463 r576  
    2121///\brief The concept of Undirected Graphs.
    2222
    23 #ifndef LEMON_CONCEPT_GRAPH_H
    24 #define LEMON_CONCEPT_GRAPH_H
     23#ifndef LEMON_CONCEPTS_GRAPH_H
     24#define LEMON_CONCEPTS_GRAPH_H
    2525
    2626#include <lemon/concepts/graph_components.h>
    27 #include <lemon/concepts/graph.h>
    2827#include <lemon/core.h>
    2928
  • lemon/concepts/graph_components.h

    r525 r581  
    2222
    2323
    24 #ifndef LEMON_CONCEPT_GRAPH_COMPONENTS_H
    25 #define LEMON_CONCEPT_GRAPH_COMPONENTS_H
     24#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
     25#define LEMON_CONCEPTS_GRAPH_COMPONENTS_H
    2626
    2727#include <lemon/core.h>
  • lemon/concepts/heap.h

    r463 r576  
    2121///\brief The concept of heaps.
    2222
    23 #ifndef LEMON_CONCEPT_HEAP_H
    24 #define LEMON_CONCEPT_HEAP_H
     23#ifndef LEMON_CONCEPTS_HEAP_H
     24#define LEMON_CONCEPTS_HEAP_H
    2525
    2626#include <lemon/core.h>
     27#include <lemon/concept_check.h>
    2728
    2829namespace lemon {
     
    243244  } // namespace lemon
    244245}
    245 #endif // LEMON_CONCEPT_PATH_H
     246#endif
  • lemon/concepts/maps.h

    r463 r576  
    1717 */
    1818
    19 #ifndef LEMON_CONCEPT_MAPS_H
    20 #define LEMON_CONCEPT_MAPS_H
     19#ifndef LEMON_CONCEPTS_MAPS_H
     20#define LEMON_CONCEPTS_MAPS_H
    2121
    2222#include <lemon/core.h>
     
    214214} //namespace lemon
    215215
    216 #endif // LEMON_CONCEPT_MAPS_H
     216#endif
  • lemon/concepts/path.h

    r463 r576  
    2222///
    2323
    24 #ifndef LEMON_CONCEPT_PATH_H
    25 #define LEMON_CONCEPT_PATH_H
     24#ifndef LEMON_CONCEPTS_PATH_H
     25#define LEMON_CONCEPTS_PATH_H
    2626
    2727#include <lemon/core.h>
     
    306306} // namespace lemon
    307307
    308 #endif // LEMON_CONCEPT_PATH_H
     308#endif
  • lemon/config.h.in

    r1 r564  
     1/* Define to 1 if you have long long */
     2#undef HAVE_LONG_LONG
     3
     4/* Define to 1 if you have any LP solver. */
     5#undef HAVE_LP
     6
     7/* Define to 1 if you have any MIP solver. */
     8#undef HAVE_MIP
     9
    110/* Define to 1 if you have CPLEX. */
    211#undef HAVE_CPLEX
     
    413/* Define to 1 if you have GLPK. */
    514#undef HAVE_GLPK
     15
     16/* Define to 1 if you have SOPLEX */
     17#undef HAVE_SOPLEX
     18
     19/* Define to 1 if you have CLP */
     20#undef HAVE_CLP
  • lemon/dimacs.h

    r463 r572  
    296296  }
    297297
    298   /// DIMACS plain digraph reader function.
    299   ///
    300   /// This function reads a digraph without any designated nodes and
     298  template<typename Graph>
     299  typename enable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
     300  _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
     301              dummy<0> = 0)
     302  {
     303    g.addEdge(s,t);
     304  }
     305  template<typename Graph>
     306  typename disable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
     307  _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
     308              dummy<1> = 1)
     309  {
     310    g.addArc(s,t);
     311  }
     312 
     313  /// DIMACS plain (di)graph reader function.
     314  ///
     315  /// This function reads a (di)graph without any designated nodes and
    301316  /// maps from DIMACS format, i.e. from DIMACS files having a line
    302317  /// starting with
     
    308323  /// If the file type was previously evaluated by dimacsType(), then
    309324  /// the descriptor struct should be given by the \c dest parameter.
    310   template<typename Digraph>
    311   void readDimacsMat(std::istream& is, Digraph &g,
    312                      DimacsDescriptor desc=DimacsDescriptor()) {
    313     typename Digraph::Node u,v;
    314     NullMap<typename Digraph::Arc, int> n;
     325  template<typename Graph>
     326  void readDimacsMat(std::istream& is, Graph &g,
     327                     DimacsDescriptor desc=DimacsDescriptor())
     328  {
    315329    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
    316330    if(desc.type!=DimacsDescriptor::MAT)
    317331      throw FormatError("Problem type mismatch");
    318     _readDimacs(is, g, n, u, v, desc);
     332
     333    g.clear();
     334    std::vector<typename Graph::Node> nodes;
     335    char c;
     336    int i, j;
     337    std::string str;
     338    nodes.resize(desc.nodeNum + 1);
     339    for (int k = 1; k <= desc.nodeNum; ++k) {
     340      nodes[k] = g.addNode();
     341    }
     342   
     343    while (is >> c) {
     344      switch (c) {
     345      case 'c': // comment line
     346        getline(is, str);
     347        break;
     348      case 'n': // node definition line
     349        break;
     350      case 'a': // arc (arc) definition line
     351        is >> i >> j;
     352        getline(is, str);
     353        _addArcEdge(g,nodes[i], nodes[j]);
     354        break;
     355      }
     356    }
    319357  }
    320358
  • lemon/elevator.h

    r463 r566  
    2828///
    2929
     30#include <lemon/core.h>
    3031#include <lemon/bits/traits.h>
    3132
  • lemon/graph_to_eps.h

    r463 r562  
    3030#include<ctime>
    3131#else
    32 #define WIN32_LEAN_AND_MEAN
    33 #define NOMINMAX
    34 #include<windows.h>
     32#include<lemon/bits/windows.h>
    3533#endif
    3634
     
    680678
    681679    {
     680      os << "%%CreationDate: ";
    682681#ifndef WIN32
    683682      timeval tv;
     
    686685      char cbuf[26];
    687686      ctime_r(&tv.tv_sec,cbuf);
    688       os << "%%CreationDate: " << cbuf;
     687      os << cbuf;
    689688#else
    690       SYSTEMTIME time;
    691       char buf1[11], buf2[9], buf3[5];
    692 
    693       GetSystemTime(&time);
    694       if (GetDateFormat(LOCALE_USER_DEFAULT, 0, &time,
    695                         "ddd MMM dd", buf1, 11) &&
    696           GetTimeFormat(LOCALE_USER_DEFAULT, 0, &time,
    697                         "HH':'mm':'ss", buf2, 9) &&
    698           GetDateFormat(LOCALE_USER_DEFAULT, 0, &time,
    699                                 "yyyy", buf3, 5)) {
    700         os << "%%CreationDate: " << buf1 << ' '
    701            << buf2 << ' ' << buf3 << std::endl;
    702       }
     689      os << bits::getWinFormattedDate();
    703690#endif
    704691    }
     692    os << std::endl;
    705693
    706694    if (_autoArcWidthScale) {
  • lemon/lgf_reader.h

    r463 r564  
    391391  class DigraphReader;
    392392
    393   /// \brief Return a \ref DigraphReader class
    394   ///
    395   /// This function just returns a \ref DigraphReader class.
    396   /// \relates DigraphReader
    397393  template <typename Digraph>
    398   DigraphReader<Digraph> digraphReader(Digraph& digraph,
    399                                        std::istream& is = std::cin) {
    400     DigraphReader<Digraph> tmp(digraph, is);
    401     return tmp;
    402   }
    403 
    404   /// \brief Return a \ref DigraphReader class
    405   ///
    406   /// This function just returns a \ref DigraphReader class.
    407   /// \relates DigraphReader
     394  DigraphReader<Digraph> digraphReader(Digraph& digraph,
     395                                       std::istream& is = std::cin);
    408396  template <typename Digraph>
    409   DigraphReader<Digraph> digraphReader(Digraph& digraph,
    410                                        const std::string& fn) {
    411     DigraphReader<Digraph> tmp(digraph, fn);
    412     return tmp;
    413   }
    414 
    415   /// \brief Return a \ref DigraphReader class
    416   ///
    417   /// This function just returns a \ref DigraphReader class.
    418   /// \relates DigraphReader
     397  DigraphReader<Digraph> digraphReader(Digraph& digraph, const std::string& fn);
    419398  template <typename Digraph>
    420   DigraphReader<Digraph> digraphReader(Digraph& digraph, const char* fn) {
    421     DigraphReader<Digraph> tmp(digraph, fn);
    422     return tmp;
    423   }
     399  DigraphReader<Digraph> digraphReader(Digraph& digraph, const char *fn);
    424400
    425401  /// \ingroup lemon_io
     
    585561  private:
    586562
    587     friend DigraphReader<Digraph> digraphReader<>(Digraph& digraph,
    588                                                   std::istream& is);
    589     friend DigraphReader<Digraph> digraphReader<>(Digraph& digraph,
    590                                                   const std::string& fn);
    591     friend DigraphReader<Digraph> digraphReader<>(Digraph& digraph,
    592                                                   const char *fn);
     563    template <typename DGR>
     564    friend DigraphReader<DGR> digraphReader(DGR& digraph, std::istream& is);
     565    template <typename DGR>
     566    friend DigraphReader<DGR> digraphReader(DGR& digraph,
     567                                            const std::string& fn);
     568    template <typename DGR>
     569    friend DigraphReader<DGR> digraphReader(DGR& digraph, const char *fn);
    593570
    594571    DigraphReader(DigraphReader& other)
     
    12131190  };
    12141191
     1192  /// \brief Return a \ref DigraphReader class
     1193  ///
     1194  /// This function just returns a \ref DigraphReader class.
     1195  /// \relates DigraphReader
     1196  template <typename Digraph>
     1197  DigraphReader<Digraph> digraphReader(Digraph& digraph, std::istream& is) {
     1198    DigraphReader<Digraph> tmp(digraph, is);
     1199    return tmp;
     1200  }
     1201
     1202  /// \brief Return a \ref DigraphReader class
     1203  ///
     1204  /// This function just returns a \ref DigraphReader class.
     1205  /// \relates DigraphReader
     1206  template <typename Digraph>
     1207  DigraphReader<Digraph> digraphReader(Digraph& digraph,
     1208                                       const std::string& fn) {
     1209    DigraphReader<Digraph> tmp(digraph, fn);
     1210    return tmp;
     1211  }
     1212
     1213  /// \brief Return a \ref DigraphReader class
     1214  ///
     1215  /// This function just returns a \ref DigraphReader class.
     1216  /// \relates DigraphReader
     1217  template <typename Digraph>
     1218  DigraphReader<Digraph> digraphReader(Digraph& digraph, const char* fn) {
     1219    DigraphReader<Digraph> tmp(digraph, fn);
     1220    return tmp;
     1221  }
     1222
    12151223  template <typename Graph>
    12161224  class GraphReader;
    1217 
    1218   /// \brief Return a \ref GraphReader class
    1219   ///
    1220   /// This function just returns a \ref GraphReader class.
    1221   /// \relates GraphReader
     1225 
    12221226  template <typename Graph>
    1223   GraphReader<Graph> graphReader(Graph& graph, std::istream& is = std::cin) {
    1224     GraphReader<Graph> tmp(graph, is);
    1225     return tmp;
    1226   }
    1227 
    1228   /// \brief Return a \ref GraphReader class
    1229   ///
    1230   /// This function just returns a \ref GraphReader class.
    1231   /// \relates GraphReader
     1227  GraphReader<Graph> graphReader(Graph& graph,
     1228                                 std::istream& is = std::cin);
    12321229  template <typename Graph>
    1233   GraphReader<Graph> graphReader(Graph& graph, const std::string& fn) {
    1234     GraphReader<Graph> tmp(graph, fn);
    1235     return tmp;
    1236   }
    1237 
    1238   /// \brief Return a \ref GraphReader class
    1239   ///
    1240   /// This function just returns a \ref GraphReader class.
    1241   /// \relates GraphReader
     1230  GraphReader<Graph> graphReader(Graph& graph, const std::string& fn);
    12421231  template <typename Graph>
    1243   GraphReader<Graph> graphReader(Graph& graph, const char* fn) {
    1244     GraphReader<Graph> tmp(graph, fn);
    1245     return tmp;
    1246   }
     1232  GraphReader<Graph> graphReader(Graph& graph, const char *fn);
    12471233
    12481234  /// \ingroup lemon_io
     
    13711357
    13721358  private:
    1373     friend GraphReader<Graph> graphReader<>(Graph& graph, std::istream& is);
    1374     friend GraphReader<Graph> graphReader<>(Graph& graph,
    1375                                             const std::string& fn);
    1376     friend GraphReader<Graph> graphReader<>(Graph& graph, const char *fn);
     1359    template <typename GR>
     1360    friend GraphReader<GR> graphReader(GR& graph, std::istream& is);
     1361    template <typename GR>
     1362    friend GraphReader<GR> graphReader(GR& graph, const std::string& fn);
     1363    template <typename GR>
     1364    friend GraphReader<GR> graphReader(GR& graph, const char *fn);
    13771365
    13781366    GraphReader(GraphReader& other)
     
    20442032
    20452033  };
     2034
     2035  /// \brief Return a \ref GraphReader class
     2036  ///
     2037  /// This function just returns a \ref GraphReader class.
     2038  /// \relates GraphReader
     2039  template <typename Graph>
     2040  GraphReader<Graph> graphReader(Graph& graph, std::istream& is) {
     2041    GraphReader<Graph> tmp(graph, is);
     2042    return tmp;
     2043  }
     2044
     2045  /// \brief Return a \ref GraphReader class
     2046  ///
     2047  /// This function just returns a \ref GraphReader class.
     2048  /// \relates GraphReader
     2049  template <typename Graph>
     2050  GraphReader<Graph> graphReader(Graph& graph, const std::string& fn) {
     2051    GraphReader<Graph> tmp(graph, fn);
     2052    return tmp;
     2053  }
     2054
     2055  /// \brief Return a \ref GraphReader class
     2056  ///
     2057  /// This function just returns a \ref GraphReader class.
     2058  /// \relates GraphReader
     2059  template <typename Graph>
     2060  GraphReader<Graph> graphReader(Graph& graph, const char* fn) {
     2061    GraphReader<Graph> tmp(graph, fn);
     2062    return tmp;
     2063  }
    20462064
    20472065  class SectionReader;
  • lemon/lgf_writer.h

    r463 r564  
    351351  class DigraphWriter;
    352352
    353   /// \brief Return a \ref DigraphWriter class
    354   ///
    355   /// This function just returns a \ref DigraphWriter class.
    356   /// \relates DigraphWriter
    357353  template <typename Digraph>
    358354  DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,
    359                                        std::ostream& os = std::cout) {
    360     DigraphWriter<Digraph> tmp(digraph, os);
    361     return tmp;
    362   }
    363 
    364   /// \brief Return a \ref DigraphWriter class
    365   ///
    366   /// This function just returns a \ref DigraphWriter class.
    367   /// \relates DigraphWriter
     355                                       std::ostream& os = std::cout);
    368356  template <typename Digraph>
    369357  DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,
    370                                        const std::string& fn) {
    371     DigraphWriter<Digraph> tmp(digraph, fn);
    372     return tmp;
    373   }
    374 
    375   /// \brief Return a \ref DigraphWriter class
    376   ///
    377   /// This function just returns a \ref DigraphWriter class.
    378   /// \relates DigraphWriter
     358                                       const std::string& fn);
     359
    379360  template <typename Digraph>
    380361  DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,
    381                                        const char* fn) {
    382     DigraphWriter<Digraph> tmp(digraph, fn);
    383     return tmp;
    384   }
     362                                       const char* fn);
     363
    385364
    386365  /// \ingroup lemon_io
     
    527506  private:
    528507
    529     friend DigraphWriter<Digraph> digraphWriter<>(const Digraph& digraph,
    530                                                   std::ostream& os);
    531     friend DigraphWriter<Digraph> digraphWriter<>(const Digraph& digraph,
    532                                                   const std::string& fn);
    533     friend DigraphWriter<Digraph> digraphWriter<>(const Digraph& digraph,
    534                                                   const char *fn);
     508    template <typename DGR>
     509    friend DigraphWriter<DGR> digraphWriter(const DGR& digraph,
     510                                            std::ostream& os);
     511    template <typename DGR>
     512    friend DigraphWriter<DGR> digraphWriter(const DGR& digraph,
     513                                            const std::string& fn);
     514    template <typename DGR>
     515    friend DigraphWriter<DGR> digraphWriter(const DGR& digraph,
     516                                            const char *fn);
    535517
    536518    DigraphWriter(DigraphWriter& other)
     
    934916  };
    935917
     918  /// \brief Return a \ref DigraphWriter class
     919  ///
     920  /// This function just returns a \ref DigraphWriter class.
     921  /// \relates DigraphWriter
     922  template <typename Digraph>
     923  DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,
     924                                       std::ostream& os) {
     925    DigraphWriter<Digraph> tmp(digraph, os);
     926    return tmp;
     927  }
     928
     929  /// \brief Return a \ref DigraphWriter class
     930  ///
     931  /// This function just returns a \ref DigraphWriter class.
     932  /// \relates DigraphWriter
     933  template <typename Digraph>
     934  DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,
     935                                       const std::string& fn) {
     936    DigraphWriter<Digraph> tmp(digraph, fn);
     937    return tmp;
     938  }
     939
     940  /// \brief Return a \ref DigraphWriter class
     941  ///
     942  /// This function just returns a \ref DigraphWriter class.
     943  /// \relates DigraphWriter
     944  template <typename Digraph>
     945  DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,
     946                                       const char* fn) {
     947    DigraphWriter<Digraph> tmp(digraph, fn);
     948    return tmp;
     949  }
     950
    936951  template <typename Graph>
    937952  class GraphWriter;
    938953
    939   /// \brief Return a \ref GraphWriter class
    940   ///
    941   /// This function just returns a \ref GraphWriter class.
    942   /// \relates GraphWriter
    943954  template <typename Graph>
    944955  GraphWriter<Graph> graphWriter(const Graph& graph,
    945                                  std::ostream& os = std::cout) {
    946     GraphWriter<Graph> tmp(graph, os);
    947     return tmp;
    948   }
    949 
    950   /// \brief Return a \ref GraphWriter class
    951   ///
    952   /// This function just returns a \ref GraphWriter class.
    953   /// \relates GraphWriter
     956                                 std::ostream& os = std::cout);
    954957  template <typename Graph>
    955   GraphWriter<Graph> graphWriter(const Graph& graph, const std::string& fn) {
    956     GraphWriter<Graph> tmp(graph, fn);
    957     return tmp;
    958   }
    959 
    960   /// \brief Return a \ref GraphWriter class
    961   ///
    962   /// This function just returns a \ref GraphWriter class.
    963   /// \relates GraphWriter
     958  GraphWriter<Graph> graphWriter(const Graph& graph, const std::string& fn);
    964959  template <typename Graph>
    965   GraphWriter<Graph> graphWriter(const Graph& graph, const char* fn) {
    966     GraphWriter<Graph> tmp(graph, fn);
    967     return tmp;
    968   }
     960  GraphWriter<Graph> graphWriter(const Graph& graph, const char* fn);
    969961
    970962  /// \ingroup lemon_io
     
    10821074  private:
    10831075
    1084     friend GraphWriter<Graph> graphWriter<>(const Graph& graph,
    1085                                             std::ostream& os);
    1086     friend GraphWriter<Graph> graphWriter<>(const Graph& graph,
    1087                                             const std::string& fn);
    1088     friend GraphWriter<Graph> graphWriter<>(const Graph& graph,
    1089                                             const char *fn);
    1090 
     1076    template <typename GR>
     1077    friend GraphWriter<GR> graphWriter(const GR& graph,
     1078                                       std::ostream& os);
     1079    template <typename GR>
     1080    friend GraphWriter<GR> graphWriter(const GR& graph,
     1081                                       const std::string& fn);
     1082    template <typename GR>
     1083    friend GraphWriter<GR> graphWriter(const GR& graph,
     1084                                       const char *fn);
     1085   
    10911086    GraphWriter(GraphWriter& other)
    10921087      : _os(other._os), local_os(other.local_os), _graph(other._graph),
     
    15341529    /// @}
    15351530  };
     1531
     1532  /// \brief Return a \ref GraphWriter class
     1533  ///
     1534  /// This function just returns a \ref GraphWriter class.
     1535  /// \relates GraphWriter
     1536  template <typename Graph>
     1537  GraphWriter<Graph> graphWriter(const Graph& graph,
     1538                                 std::ostream& os) {
     1539    GraphWriter<Graph> tmp(graph, os);
     1540    return tmp;
     1541  }
     1542
     1543  /// \brief Return a \ref GraphWriter class
     1544  ///
     1545  /// This function just returns a \ref GraphWriter class.
     1546  /// \relates GraphWriter
     1547  template <typename Graph>
     1548  GraphWriter<Graph> graphWriter(const Graph& graph, const std::string& fn) {
     1549    GraphWriter<Graph> tmp(graph, fn);
     1550    return tmp;
     1551  }
     1552
     1553  /// \brief Return a \ref GraphWriter class
     1554  ///
     1555  /// This function just returns a \ref GraphWriter class.
     1556  /// \relates GraphWriter
     1557  template <typename Graph>
     1558  GraphWriter<Graph> graphWriter(const Graph& graph, const char* fn) {
     1559    GraphWriter<Graph> tmp(graph, fn);
     1560    return tmp;
     1561  }
    15361562
    15371563  class SectionWriter;
  • lemon/math.h

    r463 r558  
    5656  const long double SQRT1_2 = 0.7071067811865475244008443621048490L;
    5757
     58  ///Check whether the parameter is NaN or not
     59 
     60  ///This function checks whether the parameter is NaN or not.
     61  ///Is should be equivalent with std::isnan(), but it is not
     62  ///provided by all compilers.
     63  inline bool isNaN(double v)
     64    {
     65      return v!=v;
     66    }
    5867
    5968  /// @}
  • lemon/path.h

    r463 r564  
    930930
    931931    template <typename Target, typename Source,
    932               bool buildEnable = BuildTagIndicator<Target>::value,
    933               bool revEnable = RevPathTagIndicator<Source>::value>
    934     struct PathCopySelector {
     932              bool buildEnable = BuildTagIndicator<Target>::value>
     933    struct PathCopySelectorForward {
    935934      static void copy(Target& target, const Source& source) {
    936935        target.clear();
     
    942941
    943942    template <typename Target, typename Source>
    944     struct PathCopySelector<Target, Source, false, true> {
     943    struct PathCopySelectorForward<Target, Source, true> {
     944      static void copy(Target& target, const Source& source) {
     945        target.clear();
     946        target.build(source);
     947      }
     948    };
     949
     950    template <typename Target, typename Source,
     951              bool buildEnable = BuildTagIndicator<Target>::value>
     952    struct PathCopySelectorBackward {
    945953      static void copy(Target& target, const Source& source) {
    946954        target.clear();
     
    952960
    953961    template <typename Target, typename Source>
    954     struct PathCopySelector<Target, Source, true, false> {
    955       static void copy(Target& target, const Source& source) {
    956         target.clear();
    957         target.build(source);
    958       }
    959     };
    960 
    961     template <typename Target, typename Source>
    962     struct PathCopySelector<Target, Source, true, true> {
     962    struct PathCopySelectorBackward<Target, Source, true> {
    963963      static void copy(Target& target, const Source& source) {
    964964        target.clear();
    965965        target.buildRev(source);
    966966      }
     967    };
     968
     969   
     970    template <typename Target, typename Source,
     971              bool revEnable = RevPathTagIndicator<Source>::value>
     972    struct PathCopySelector {
     973      static void copy(Target& target, const Source& source) {
     974        PathCopySelectorForward<Target, Source>::copy(target, source);
     975      }     
     976    };
     977
     978    template <typename Target, typename Source>
     979    struct PathCopySelector<Target, Source, true> {
     980      static void copy(Target& target, const Source& source) {
     981        PathCopySelectorBackward<Target, Source>::copy(target, source);
     982      }     
    967983    };
    968984
  • lemon/random.h

    r463 r564  
    7878#include <unistd.h>
    7979#else
    80 #include <windows.h>
     80#include <lemon/bits/windows.h>
    8181#endif
    8282
     
    345345    };
    346346
    347     template <typename Result, int exp, bool pos = (exp >= 0)>
     347    template <typename Result, int exp>
    348348    struct ShiftMultiplier {
    349       static const Result multiplier() {
    350         Result res = ShiftMultiplier<Result, exp / 2>::multiplier();
    351         res *= res;
    352         if ((exp & 1) == 1) res *= static_cast<Result>(2.0);
    353         return res;
    354       }
    355     };
    356 
    357     template <typename Result, int exp>
    358     struct ShiftMultiplier<Result, exp, false> {
    359349      static const Result multiplier() {
    360350        Result res = ShiftMultiplier<Result, exp / 2>::multiplier();
     
    366356
    367357    template <typename Result>
    368     struct ShiftMultiplier<Result, 0, true> {
     358    struct ShiftMultiplier<Result, 0> {
    369359      static const Result multiplier() {
    370360        return static_cast<Result>(1.0);
     
    373363
    374364    template <typename Result>
    375     struct ShiftMultiplier<Result, -20, true> {
     365    struct ShiftMultiplier<Result, 20> {
    376366      static const Result multiplier() {
    377367        return static_cast<Result>(1.0/1048576.0);
     
    380370
    381371    template <typename Result>
    382     struct ShiftMultiplier<Result, -32, true> {
     372    struct ShiftMultiplier<Result, 32> {
    383373      static const Result multiplier() {
    384         return static_cast<Result>(1.0/424967296.0);
     374        return static_cast<Result>(1.0/4294967296.0);
    385375      }
    386376    };
    387377
    388378    template <typename Result>
    389     struct ShiftMultiplier<Result, -53, true> {
     379    struct ShiftMultiplier<Result, 53> {
    390380      static const Result multiplier() {
    391381        return static_cast<Result>(1.0/9007199254740992.0);
     
    394384
    395385    template <typename Result>
    396     struct ShiftMultiplier<Result, -64, true> {
     386    struct ShiftMultiplier<Result, 64> {
    397387      static const Result multiplier() {
    398388        return static_cast<Result>(1.0/18446744073709551616.0);
     
    414404
    415405      static Result convert(RandomCore<Word>& rnd) {
    416         return Shifting<Result, - shift - rest>::
     406        return Shifting<Result, shift + rest>::
    417407          shift(static_cast<Result>(rnd() >> (bits - rest)));
    418408      }
     
    424414
    425415      static Result convert(RandomCore<Word>& rnd) {
    426         return Shifting<Result, - shift - bits>::
     416        return Shifting<Result, shift + bits>::
    427417          shift(static_cast<Result>(rnd())) +
    428418          RealConversion<Result, Word, rest-bits, shift + bits>::
     
    663653      seed(getpid() + tv.tv_sec + tv.tv_usec);
    664654#else
    665       FILETIME time;
    666       GetSystemTimeAsFileTime(&time);
    667       seed(GetCurrentProcessId() + time.dwHighDateTime + time.dwLowDateTime);
     655      seed(bits::getWinRndSeed());
    668656#endif
    669657      return true;
  • lemon/suurballe.h

    r463 r566  
    2828#include <lemon/bin_heap.h>
    2929#include <lemon/path.h>
     30#include <lemon/list_graph.h>
     31#include <lemon/maps.h>
    3032
    3133namespace lemon {
  • lemon/time_measure.h

    r463 r562  
    2525
    2626#ifdef WIN32
    27 #define WIN32_LEAN_AND_MEAN
    28 #define NOMINMAX
    29 #include <windows.h>
    30 #include <cmath>
     27#include <lemon/bits/windows.h>
    3128#else
     29#include <unistd.h>
    3230#include <sys/times.h>
    3331#include <sys/time.h>
     
    8886      cstime=ts.tms_cstime/tck;
    8987#else
    90       static const double ch = 4294967296.0e-7;
    91       static const double cl = 1.0e-7;
    92 
    93       FILETIME system;
    94       GetSystemTimeAsFileTime(&system);
    95       rtime = ch * system.dwHighDateTime + cl * system.dwLowDateTime;
    96 
    97       FILETIME create, exit, kernel, user;
    98       if (GetProcessTimes(GetCurrentProcess(),&create, &exit, &kernel, &user)) {
    99         utime = ch * user.dwHighDateTime + cl * user.dwLowDateTime;
    100         stime = ch * kernel.dwHighDateTime + cl * kernel.dwLowDateTime;
    101         cutime = 0;
    102         cstime = 0;
    103       } else {
    104         rtime = 0;
    105         utime = 0;
    106         stime = 0;
    107         cutime = 0;
    108         cstime = 0;
    109       }
     88      bits::getWinProcTimes(rtime, utime, stime, cutime, cstime);
    11089#endif
    11190    }
  • lemon/tolerance.h

    r463 r564  
    3939  ///as a result of a probably inexact computation.
    4040  ///
    41   ///This is an abstract class, it should be specialized for all
    42   ///numerical data types. These specialized classes like
     41  ///The general implementation is suitable only if the data type is exact,
     42  ///like the integer types, otherwise a specialized version must be
     43  ///implemented. These specialized classes like
    4344  ///Tolerance<double> may offer additional tuning parameters.
    4445  ///
     
    4647  ///\sa Tolerance<double>
    4748  ///\sa Tolerance<long double>
    48   ///\sa Tolerance<int>
    49   ///\sa Tolerance<long long int>
    50   ///\sa Tolerance<unsigned int>
    51   ///\sa Tolerance<unsigned long long int>
    5249
    5350  template<class T>
     
    6562
    6663    ///Returns \c true if \c a is \e surely strictly less than \c b
    67     static bool less(Value a,Value b) {return false;}
    68     ///Returns \c true if \c a is \e surely different from \c b
    69     static bool different(Value a,Value b) {return false;}
    70     ///Returns \c true if \c a is \e surely positive
    71     static bool positive(Value a) {return false;}
    72     ///Returns \c true if \c a is \e surely negative
    73     static bool negative(Value a) {return false;}
    74     ///Returns \c true if \c a is \e surely non-zero
    75     static bool nonZero(Value a) {return false;}
     64    static bool less(Value a,Value b) {return a<b;}
     65    ///Returns \c true if \c a is \e surely different from \c b
     66    static bool different(Value a,Value b) {return a!=b;}
     67    ///Returns \c true if \c a is \e surely positive
     68    static bool positive(Value a) {return static_cast<Value>(0) < a;}
     69    ///Returns \c true if \c a is \e surely negative
     70    static bool negative(Value a) {return a < static_cast<Value>(0);}
     71    ///Returns \c true if \c a is \e surely non-zero
     72    static bool nonZero(Value a) {return a != static_cast<Value>(0);}
    7673
    7774    ///@}
    7875
    7976    ///Returns the zero value.
    80     static Value zero() {return T();}
     77    static Value zero() {return static_cast<Value>(0);}
    8178
    8279    //   static bool finite(Value a) {}
     
    239236  };
    240237
    241   ///Integer specialization of Tolerance.
    242 
    243   ///Integer specialization of Tolerance.
    244   ///\sa Tolerance
    245   template<>
    246   class Tolerance<int>
    247   {
    248   public:
    249     ///\e
    250     typedef int Value;
    251 
    252     ///\name Comparisons
    253     ///See \ref lemon::Tolerance "Tolerance" for more details.
    254 
    255     ///@{
    256 
    257     ///Returns \c true if \c a is \e surely strictly less than \c b
    258     static bool less(Value a,Value b) { return a<b;}
    259     ///Returns \c true if \c a is \e surely different from \c b
    260     static bool different(Value a,Value b) { return a!=b; }
    261     ///Returns \c true if \c a is \e surely positive
    262     static bool positive(Value a) { return 0<a; }
    263     ///Returns \c true if \c a is \e surely negative
    264     static bool negative(Value a) { return 0>a; }
    265     ///Returns \c true if \c a is \e surely non-zero
    266     static bool nonZero(Value a) { return a!=0; }
    267 
    268     ///@}
    269 </