gravatar
alpar (Alpar Juttner)
alpar@cs.elte.hu
Merge
1 21 2
merge 1.1
2 files changed:
↑ Collapse diff ↑
Ignore white space 6 line context
1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2
 *
3
 * This file is a part of LEMON, a generic C++ optimization library.
4
 *
5
 * Copyright (C) 2003-2009
6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8
 *
9
 * Permission to use, modify and distribute this software is granted
10
 * provided that this copyright notice appears in all copies. For
11
 * precise terms see the accompanying LICENSE file.
12
 *
13
 * This software is provided "AS IS" with no warranty of any kind,
14
 * express or implied, and with no claim as to its suitability for any
15
 * purpose.
16
 *
17
 */
18

	
19
namespace lemon {
20

	
21
/**
22
\page min_cost_flow Minimum Cost Flow Problem
23

	
24
\section mcf_def Definition (GEQ form)
25

	
26
The \e minimum \e cost \e flow \e problem is to find a feasible flow of
27
minimum total cost from a set of supply nodes to a set of demand nodes
28
in a network with capacity constraints (lower and upper bounds)
29
and arc costs.
30

	
31
Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
32
\f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and
33
upper bounds for the flow values on the arcs, for which
34
\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
35
\f$cost: A\rightarrow\mathbf{R}\f$ denotes the cost per unit flow
36
on the arcs and \f$sup: V\rightarrow\mathbf{R}\f$ denotes the
37
signed supply values of the nodes.
38
If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
39
supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
40
\f$-sup(u)\f$ demand.
41
A minimum cost flow is an \f$f: A\rightarrow\mathbf{R}\f$ solution
42
of the following optimization problem.
43

	
44
\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
45
\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
46
    sup(u) \quad \forall u\in V \f]
47
\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
48

	
49
The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
50
zero or negative in order to have a feasible solution (since the sum
51
of the expressions on the left-hand side of the inequalities is zero).
52
It means that the total demand must be greater or equal to the total
53
supply and all the supplies have to be carried out from the supply nodes,
54
but there could be demands that are not satisfied.
55
If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
56
constraints have to be satisfied with equality, i.e. all demands
57
have to be satisfied and all supplies have to be used.
58

	
59

	
60
\section mcf_algs Algorithms
61

	
62
LEMON contains several algorithms for solving this problem, for more
63
information see \ref min_cost_flow_algs "Minimum Cost Flow Algorithms".
64

	
65
A feasible solution for this problem can be found using \ref Circulation.
66

	
67

	
68
\section mcf_dual Dual Solution
69

	
70
The dual solution of the minimum cost flow problem is represented by
71
node potentials \f$\pi: V\rightarrow\mathbf{R}\f$.
72
An \f$f: A\rightarrow\mathbf{R}\f$ primal feasible solution is optimal
73
if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$ node potentials
74
the following \e complementary \e slackness optimality conditions hold.
75

	
76
 - For all \f$uv\in A\f$ arcs:
77
   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
78
   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
79
   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
80
 - For all \f$u\in V\f$ nodes:
81
   - \f$\pi(u)<=0\f$;
82
   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
83
     then \f$\pi(u)=0\f$.
84
 
85
Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
86
\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
87
\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
88

	
89
All algorithms provide dual solution (node potentials), as well,
90
if an optimal flow is found.
91

	
92

	
93
\section mcf_eq Equality Form
94

	
95
The above \ref mcf_def "definition" is actually more general than the
96
usual formulation of the minimum cost flow problem, in which strict
97
equalities are required in the supply/demand contraints.
98

	
99
\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
100
\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
101
    sup(u) \quad \forall u\in V \f]
102
\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
103

	
104
However if the sum of the supply values is zero, then these two problems
105
are equivalent.
106
The \ref min_cost_flow_algs "algorithms" in LEMON support the general
107
form, so if you need the equality form, you have to ensure this additional
108
contraint manually.
109

	
110

	
111
\section mcf_leq Opposite Inequalites (LEQ Form)
112

	
113
Another possible definition of the minimum cost flow problem is
114
when there are <em>"less or equal"</em> (LEQ) supply/demand constraints,
115
instead of the <em>"greater or equal"</em> (GEQ) constraints.
116

	
117
\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
118
\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq
119
    sup(u) \quad \forall u\in V \f]
120
\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
121

	
122
It means that the total demand must be less or equal to the 
123
total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
124
positive) and all the demands have to be satisfied, but there
125
could be supplies that are not carried out from the supply
126
nodes.
127
The equality form is also a special case of this form, of course.
128

	
129
You could easily transform this case to the \ref mcf_def "GEQ form"
130
of the problem by reversing the direction of the arcs and taking the
131
negative of the supply values (e.g. using \ref ReverseDigraph and
132
\ref NegMap adaptors).
133
However \ref NetworkSimplex algorithm also supports this form directly
134
for the sake of convenience.
135

	
136
Note that the optimality conditions for this supply constraint type are
137
slightly differ from the conditions that are discussed for the GEQ form,
138
namely the potentials have to be non-negative instead of non-positive.
139
An \f$f: A\rightarrow\mathbf{R}\f$ feasible solution of this problem
140
is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$
141
node potentials the following conditions hold.
142

	
143
 - For all \f$uv\in A\f$ arcs:
144
   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
145
   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
146
   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
147
 - For all \f$u\in V\f$ nodes:
148
   - \f$\pi(u)>=0\f$;
149
   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
150
     then \f$\pi(u)=0\f$.
151

	
152
*/
153
}
Ignore white space 6 line context
1 1
CMAKE_MINIMUM_REQUIRED(VERSION 2.6)
2 2

	
3 3
IF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
4 4
  INCLUDE(${CMAKE_SOURCE_DIR}/cmake/version.cmake)
5 5
ELSE(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
6 6
  SET(PROJECT_NAME "LEMON")
7 7
  SET(PROJECT_VERSION "hg-tip" CACHE STRING "LEMON version string.")
8 8
ENDIF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
9 9

	
10 10
PROJECT(${PROJECT_NAME})
11 11

	
12 12
SET(CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR}/cmake)
13 13

	
14 14
INCLUDE(FindDoxygen)
15 15
INCLUDE(FindGhostscript)
16 16
FIND_PACKAGE(GLPK 4.33)
17 17
FIND_PACKAGE(CPLEX)
18 18
FIND_PACKAGE(COIN)
19 19

	
20 20
IF(MSVC)
21 21
  SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} /wd4250 /wd4355 /wd4800 /wd4996")
22 22
# Suppressed warnings:
23 23
# C4250: 'class1' : inherits 'class2::member' via dominance
24 24
# C4355: 'this' : used in base member initializer list
25 25
# C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning)
26 26
# C4996: 'function': was declared deprecated
27 27
ENDIF(MSVC)
28 28

	
29 29
INCLUDE(CheckTypeSize)
30 30
CHECK_TYPE_SIZE("long long" LEMON_LONG_LONG)
31 31

	
32 32
ENABLE_TESTING()
33 33

	
34 34
ADD_SUBDIRECTORY(lemon)
35 35
IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
36 36
  ADD_SUBDIRECTORY(demo)
37 37
  ADD_SUBDIRECTORY(tools)
38 38
  ADD_SUBDIRECTORY(doc)
39 39
  ADD_SUBDIRECTORY(test)
40 40
ENDIF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
41 41

	
42 42
IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
43 43
  IF(WIN32)
44 44
    SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
45 45
    SET(CPACK_PACKAGE_VENDOR "EGRES")
46 46
    SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
47
      "LEMON - Library of Efficient Models and Optimization in Networks")
47
      "LEMON - Library for Efficient Modeling and Optimization in Networks")
48 48
    SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")
49 49

	
50 50
    SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
51 51

	
52 52
    SET(CPACK_PACKAGE_INSTALL_DIRECTORY
53 53
      "${PROJECT_NAME} ${PROJECT_VERSION}")
54 54
    SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY
55 55
      "${PROJECT_NAME} ${PROJECT_VERSION}")
56 56

	
57 57
    SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
58 58

	
59 59
    SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
60 60
    SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
61 61
    SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities")
62 62
    SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
63 63

	
64 64
    SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
65 65
      "C++ header files")
66 66
    SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
67 67
      "DLL and import library")
68 68
    SET(CPACK_COMPONENT_BIN_DESCRIPTION
69 69
      "Command line utilities")
70 70
    SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
71 71
      "Doxygen generated documentation")
72 72

	
73 73
    SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
74 74

	
75 75
    SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
76 76
    SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
77 77
    SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
78 78

	
79 79
    SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
80 80
      "Components needed to develop software using LEMON")
81 81
    SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
82 82
      "Documentation of LEMON")
83 83

	
84 84
    SET(CPACK_ALL_INSTALL_TYPES Full Developer)
85 85

	
86 86
    SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
87 87
    SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
88 88
    SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
89 89

	
90 90
    SET(CPACK_GENERATOR "NSIS")
91 91
    SET(CPACK_NSIS_MUI_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis/lemon.ico")
92 92
    SET(CPACK_NSIS_MUI_UNIICON "${PROJECT_SOURCE_DIR}/cmake/nsis/uninstall.ico")
93 93
    #SET(CPACK_PACKAGE_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
94 94
    SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
95 95
    SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
96 96
    SET(CPACK_NSIS_HELP_LINK "http:\\\\\\\\lemon.cs.elte.hu")
97 97
    SET(CPACK_NSIS_URL_INFO_ABOUT "http:\\\\\\\\lemon.cs.elte.hu")
98 98
    SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")
99 99
    SET(CPACK_NSIS_CREATE_ICONS_EXTRA "
100 100
      CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\share\\\\doc\\\\index.html\\\"
101 101
      ")
102 102
    SET(CPACK_NSIS_DELETE_ICONS_EXTRA "
103 103
      !insertmacro MUI_STARTMENU_GETFOLDER Application $MUI_TEMP
104 104
      Delete \\\"$SMPROGRAMS\\\\$MUI_TEMP\\\\Documentation.lnk\\\"
105 105
      ")
106 106

	
107 107
    INCLUDE(CPack)
108 108
  ENDIF(WIN32)
109 109
ENDIF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
Ignore white space 6 line context
1
2009-05-13 Version 1.1 released
2

	
3
        This is the second stable release of the 1.x series. It
4
        features a better coverage of the tools available in the 0.x
5
        series, a thoroughly reworked LP/MIP interface plus various
6
        improvements in the existing tools.
7

	
8
        * Much improved M$ Windows support
9
          * Various improvements in the CMAKE build system
10
          * Compilation warnings are fixed/suppressed
11
        * Support IBM xlC compiler
12
        * New algorithms
13
          * Connectivity related algorithms (#61)
14
          * Euler walks (#65)
15
          * Preflow push-relabel max. flow algorithm (#176)
16
          * Circulation algorithm (push-relabel based) (#175)
17
          * Suurballe algorithm (#47)
18
          * Gomory-Hu algorithm (#66)
19
          * Hao-Orlin algorithm (#58)
20
          * Edmond's maximum cardinality and weighted matching algorithms
21
            in general graphs (#48,#265)
22
          * Minimum cost arborescence/branching (#60)
23
          * Network Simplex min. cost flow algorithm (#234)
24
        * New data structures
25
          * Full graph structure (#57)
26
          * Grid graph structure (#57)
27
          * Hypercube graph structure (#57)
28
          * Graph adaptors (#67)
29
          * ArcSet and EdgeSet classes (#67)
30
          * Elevator class (#174)
31
        * Other new tools
32
          * LP/MIP interface (#44)
33
            * Support for GLPK, CPLEX, Soplex, COIN-OR CLP and CBC
34
          * Reader for the Nauty file format (#55)
35
          * DIMACS readers (#167)
36
          * Radix sort algorithms (#72)
37
          * RangeIdMap and CrossRefMap (#160)
38
        * New command line tools
39
          * DIMACS to LGF converter (#182)
40
          * lgf-gen - a graph generator (#45)
41
          * DIMACS solver utility (#226)
42
        * Other code improvements
43
          * Lognormal distribution added to Random (#102)
44
          * Better (i.e. O(1) time) item counting in SmartGraph (#3)
45
          * The standard maps of graphs are guaranteed to be
46
            reference maps (#190)
47
        * Miscellaneous
48
          * Various doc improvements
49
          * Improved 0.x -> 1.x converter script
50

	
51
        * Several bugfixes (compared to release 1.0):
52
          #170: Bugfix SmartDigraph::split()
53
          #171: Bugfix in SmartGraph::restoreSnapshot()
54
          #172: Extended test cases for graphs and digraphs
55
          #173: Bugfix in Random
56
                * operator()s always return a double now
57
                * the faulty real<Num>(Num) and real<Num>(Num,Num)
58
                  have been removed
59
          #187: Remove DijkstraWidestPathOperationTraits
60
          #61:  Bugfix in DfsVisit
61
          #193: Bugfix in GraphReader::skipSection()
62
          #195: Bugfix in ConEdgeIt()
63
          #197: Bugfix in heap unionfind
64
                * This bug affects Edmond's general matching algorithms
65
          #207: Fix 'make install' without 'make html' using CMAKE
66
          #208: Suppress or fix VS2008 compilation warnings
67
          ----: Update the LEMON icon
68
          ----: Enable the component-based installer
69
                (in installers made by CPACK)
70
          ----: Set the proper version for CMAKE in the tarballs
71
                (made by autotools)
72
          ----: Minor clarification in the LICENSE file
73
          ----: Add missing unistd.h include to time_measure.h
74
          #204: Compilation bug fixed in graph_to_eps.h with VS2005
75
          #214,#215: windows.h should never be included by lemon headers
76
          #230: Build systems check the availability of 'long long' type
77
          #229: Default implementation of Tolerance<> is used for integer types
78
          #211,#212: Various fixes for compiling on AIX
79
          ----: Improvements in CMAKE config
80
                - docs is installed in share/doc/
81
                - detects newer versions of Ghostscript
82
          #239: Fix missing 'inline' specifier in time_measure.h
83
          #274,#280: Install lemon/config.h
84
          #275: Prefix macro names with LEMON_ in lemon/config.h
85
          ----: Small script for making the release tarballs added
86
          ----: Minor improvement in unify-sources.sh (a76f55d7d397)
87

	
1 88
2009-03-27 LEMON joins to the COIN-OR initiative
2 89

	
3 90
        COIN-OR (Computational Infrastructure for Operations Research,
4 91
        http://www.coin-or.org) project is an initiative to spur the
5 92
        development of open-source software for the operations research
6 93
        community.
7 94

	
8 95
2008-10-13 Version 1.0 released
9 96

	
10 97
	This is the first stable release of LEMON. Compared to the 0.x
11 98
	release series, it features a considerably smaller but more
12 99
	matured set of tools. The API has also completely revised and
13 100
	changed in several places.
14 101

	
15 102
	* The major name changes compared to the 0.x series (see the
16 103
          Migration Guide in the doc for more details)
17 104
          * Graph -> Digraph, UGraph -> Graph
18 105
          * Edge -> Arc, UEdge -> Edge
19 106
	  * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
20 107
	* Other improvements
21 108
	  * Better documentation
22 109
	  * Reviewed and cleaned up codebase
23 110
	  * CMake based build system (along with the autotools based one)
24 111
	* Contents of the library (ported from 0.x)
25 112
	  * Algorithms
26 113
       	    * breadth-first search (bfs.h)
27 114
       	    * depth-first search (dfs.h)
28 115
       	    * Dijkstra's algorithm (dijkstra.h)
29 116
       	    * Kruskal's algorithm (kruskal.h)
30 117
    	  * Data structures
31 118
       	    * graph data structures (list_graph.h, smart_graph.h)
32 119
       	    * path data structures (path.h)
33 120
       	    * binary heap data structure (bin_heap.h)
34 121
       	    * union-find data structures (unionfind.h)
35 122
       	    * miscellaneous property maps (maps.h)
36 123
       	    * two dimensional vector and bounding box (dim2.h)
37 124
          * Concepts
38 125
       	    * graph structure concepts (concepts/digraph.h, concepts/graph.h,
39 126
              concepts/graph_components.h)
40 127
       	    * concepts for other structures (concepts/heap.h, concepts/maps.h,
41 128
	      concepts/path.h)
42 129
    	  * Tools
43 130
       	    * Mersenne twister random number generator (random.h)
44 131
       	    * tools for measuring cpu and wall clock time (time_measure.h)
45 132
       	    * tools for counting steps and events (counter.h)
46 133
       	    * tool for parsing command line arguments (arg_parser.h)
47 134
       	    * tool for visualizing graphs (graph_to_eps.h)
48 135
       	    * tools for reading and writing data in LEMON Graph Format
49 136
              (lgf_reader.h, lgf_writer.h)
50 137
            * tools to handle the anomalies of calculations with
51 138
	      floating point numbers (tolerance.h)
52 139
            * tools to manage RGB colors (color.h)
53 140
    	  * Infrastructure
54 141
       	    * extended assertion handling (assert.h)
55 142
       	    * exception classes and error handling (error.h)
56 143
      	    * concept checking (concept_check.h)
57 144
       	    * commonly used mathematical constants (math.h)
Ignore white space 6 line context
1
==================================================================
2
LEMON - a Library of Efficient Models and Optimization in Networks
3
==================================================================
1
=====================================================================
2
LEMON - a Library for Efficient Modeling and Optimization in Networks
3
=====================================================================
4 4

	
5 5
LEMON is an open source library written in C++. It provides
6 6
easy-to-use implementations of common data structures and algorithms
7 7
in the area of optimization and helps implementing new ones. The main
8 8
focus is on graphs and graph algorithms, thus it is especially
9 9
suitable for solving design and optimization problems of
10 10
telecommunication networks. To achieve wide usability its data
11 11
structures and algorithms provide generic interfaces.
12 12

	
13 13
Contents
14 14
========
15 15

	
16 16
LICENSE
17 17

	
18 18
   Copying, distribution and modification conditions and terms.
19 19

	
20 20
INSTALL
21 21

	
22 22
   General building and installation instructions.
23 23

	
24 24
lemon/
25 25

	
26 26
   Source code of LEMON library.
27 27

	
28 28
doc/
29 29

	
30 30
   Documentation of LEMON. The starting page is doc/html/index.html.
31 31

	
32 32
demo/
33 33

	
34 34
   Some example programs to make you easier to get familiar with LEMON.
35 35

	
36 36
test/
37 37

	
38 38
   Programs to check the integrity and correctness of LEMON.
39 39

	
40 40
tools/
41 41

	
42 42
   Various utilities related to LEMON.
Ignore white space 6 line context
1 1
EXTRA_DIST += \
2 2
	doc/Doxyfile.in \
3 3
	doc/DoxygenLayout.xml \
4 4
	doc/coding_style.dox \
5 5
	doc/dirs.dox \
6 6
	doc/groups.dox \
7 7
	doc/lgf.dox \
8 8
	doc/license.dox \
9 9
	doc/mainpage.dox \
10 10
	doc/migration.dox \
11
	doc/min_cost_flow.dox \
11 12
	doc/named-param.dox \
12 13
	doc/namespaces.dox \
13 14
	doc/html \
14 15
	doc/CMakeLists.txt
15 16

	
16 17
DOC_EPS_IMAGES18 = \
17 18
	grid_graph.eps \
18 19
	nodeshape_0.eps \
19 20
	nodeshape_1.eps \
20 21
	nodeshape_2.eps \
21 22
	nodeshape_3.eps \
22 23
	nodeshape_4.eps
23 24

	
24 25
DOC_EPS_IMAGES27 = \
25 26
	bipartite_matching.eps \
26 27
	bipartite_partitions.eps \
27 28
	connected_components.eps \
28 29
	edge_biconnected_components.eps \
29 30
	node_biconnected_components.eps \
30 31
	strongly_connected_components.eps
31 32

	
32 33
DOC_EPS_IMAGES = \
33 34
	$(DOC_EPS_IMAGES18) \
34 35
	$(DOC_EPS_IMAGES27)
35 36

	
36 37
DOC_PNG_IMAGES = \
37 38
	$(DOC_EPS_IMAGES:%.eps=doc/gen-images/%.png)
38 39

	
39 40
EXTRA_DIST += $(DOC_EPS_IMAGES:%=doc/images/%)
40 41

	
41 42
doc/html:
42 43
	$(MAKE) $(AM_MAKEFLAGS) html
43 44

	
44 45
GS_COMMAND=gs -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4
45 46

	
46 47
$(DOC_EPS_IMAGES18:%.eps=doc/gen-images/%.png): doc/gen-images/%.png: doc/images/%.eps
47 48
	-mkdir doc/gen-images
48 49
	if test ${gs_found} = yes; then \
49 50
	  $(GS_COMMAND) -sDEVICE=pngalpha -r18 -sOutputFile=$@ $<; \
50 51
	else \
51 52
	  echo; \
52 53
	  echo "Ghostscript not found."; \
53 54
	  echo; \
54 55
	  exit 1; \
55 56
	fi
56 57

	
57 58
$(DOC_EPS_IMAGES27:%.eps=doc/gen-images/%.png): doc/gen-images/%.png: doc/images/%.eps
58 59
	-mkdir doc/gen-images
59 60
	if test ${gs_found} = yes; then \
60 61
	  $(GS_COMMAND) -sDEVICE=pngalpha -r27 -sOutputFile=$@ $<; \
61 62
	else \
62 63
	  echo; \
63 64
	  echo "Ghostscript not found."; \
64 65
	  echo; \
65 66
	  exit 1; \
66 67
	fi
67 68

	
68 69
html-local: $(DOC_PNG_IMAGES)
69 70
	if test ${doxygen_found} = yes; then \
70 71
	  cd doc; \
71 72
	  doxygen Doxyfile; \
72 73
	  cd ..; \
73 74
	else \
74 75
	  echo; \
75 76
	  echo "Doxygen not found."; \
76 77
	  echo; \
77 78
	  exit 1; \
78 79
	fi
79 80

	
80 81
clean-local:
81 82
	-rm -rf doc/html
82 83
	-rm -f doc/doxygen.log
83 84
	-rm -f $(DOC_PNG_IMAGES)
84 85
	-rm -rf doc/gen-images
85 86

	
86 87
update-external-tags:
87 88
	wget -O doc/libstdc++.tag.tmp http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag && \
88 89
	mv doc/libstdc++.tag.tmp doc/libstdc++.tag || \
89 90
	rm doc/libstdc++.tag.tmp
90 91

	
91 92
install-html-local: doc/html
92 93
	@$(NORMAL_INSTALL)
93 94
	$(mkinstalldirs) $(DESTDIR)$(htmldir)/docs
94 95
	for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
95 96
	  f="`echo $$p | sed -e 's|^.*/||'`"; \
96 97
	  echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f"; \
97 98
	  $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f; \
98 99
	done
99 100

	
100 101
uninstall-local:
101 102
	@$(NORMAL_UNINSTALL)
102 103
	for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
103 104
	  f="`echo $$p | sed -e 's|^.*/||'`"; \
104 105
	  echo " rm -f $(DESTDIR)$(htmldir)/docs/$$f"; \
105 106
	  rm -f $(DESTDIR)$(htmldir)/docs/$$f; \
106 107
	done
107 108

	
108 109
.PHONY: update-external-tags
Ignore white space 6 line context
1 1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 2
 *
3 3
 * This file is a part of LEMON, a generic C++ optimization library.
4 4
 *
5 5
 * Copyright (C) 2003-2009
6 6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 8
 *
9 9
 * Permission to use, modify and distribute this software is granted
10 10
 * provided that this copyright notice appears in all copies. For
11 11
 * precise terms see the accompanying LICENSE file.
12 12
 *
13 13
 * This software is provided "AS IS" with no warranty of any kind,
14 14
 * express or implied, and with no claim as to its suitability for any
15 15
 * purpose.
16 16
 *
17 17
 */
18 18

	
19 19
namespace lemon {
20 20

	
21 21
/**
22 22
@defgroup datas Data Structures
23 23
This group contains the several data structures implemented in LEMON.
24 24
*/
25 25

	
26 26
/**
27 27
@defgroup graphs Graph Structures
28 28
@ingroup datas
29 29
\brief Graph structures implemented in LEMON.
30 30

	
31 31
The implementation of combinatorial algorithms heavily relies on
32 32
efficient graph implementations. LEMON offers data structures which are
33 33
planned to be easily used in an experimental phase of implementation studies,
34 34
and thereafter the program code can be made efficient by small modifications.
35 35

	
36 36
The most efficient implementation of diverse applications require the
37 37
usage of different physical graph implementations. These differences
38 38
appear in the size of graph we require to handle, memory or time usage
39 39
limitations or in the set of operations through which the graph can be
40 40
accessed.  LEMON provides several physical graph structures to meet
41 41
the diverging requirements of the possible users.  In order to save on
42 42
running time or on memory usage, some structures may fail to provide
43 43
some graph features like arc/edge or node deletion.
44 44

	
45 45
Alteration of standard containers need a very limited number of
46 46
operations, these together satisfy the everyday requirements.
47 47
In the case of graph structures, different operations are needed which do
48 48
not alter the physical graph, but gives another view. If some nodes or
49 49
arcs have to be hidden or the reverse oriented graph have to be used, then
50 50
this is the case. It also may happen that in a flow implementation
51 51
the residual graph can be accessed by another algorithm, or a node-set
52 52
is to be shrunk for another algorithm.
53 53
LEMON also provides a variety of graphs for these requirements called
54 54
\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
55 55
in conjunction with other graph representations.
56 56

	
57 57
You are free to use the graph structure that fit your requirements
58 58
the best, most graph algorithms and auxiliary data structures can be used
59 59
with any graph structure.
60 60

	
61 61
<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
62 62
*/
63 63

	
64 64
/**
65 65
@defgroup graph_adaptors Adaptor Classes for Graphs
66 66
@ingroup graphs
67 67
\brief Adaptor classes for digraphs and graphs
68 68

	
69 69
This group contains several useful adaptor classes for digraphs and graphs.
70 70

	
71 71
The main parts of LEMON are the different graph structures, generic
72 72
graph algorithms, graph concepts, which couple them, and graph
73 73
adaptors. While the previous notions are more or less clear, the
74 74
latter one needs further explanation. Graph adaptors are graph classes
75 75
which serve for considering graph structures in different ways.
76 76

	
77 77
A short example makes this much clearer.  Suppose that we have an
78 78
instance \c g of a directed graph type, say ListDigraph and an algorithm
79 79
\code
80 80
template <typename Digraph>
81 81
int algorithm(const Digraph&);
82 82
\endcode
83 83
is needed to run on the reverse oriented graph.  It may be expensive
84 84
(in time or in memory usage) to copy \c g with the reversed
85 85
arcs.  In this case, an adaptor class is used, which (according
86 86
to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
87 87
The adaptor uses the original digraph structure and digraph operations when
88 88
methods of the reversed oriented graph are called.  This means that the adaptor
89 89
have minor memory usage, and do not perform sophisticated algorithmic
90 90
actions.  The purpose of it is to give a tool for the cases when a
91 91
graph have to be used in a specific alteration.  If this alteration is
92 92
obtained by a usual construction like filtering the node or the arc set or
93 93
considering a new orientation, then an adaptor is worthwhile to use.
94 94
To come back to the reverse oriented graph, in this situation
95 95
\code
96 96
template<typename Digraph> class ReverseDigraph;
97 97
\endcode
98 98
template class can be used. The code looks as follows
99 99
\code
100 100
ListDigraph g;
101 101
ReverseDigraph<ListDigraph> rg(g);
102 102
int result = algorithm(rg);
103 103
\endcode
104 104
During running the algorithm, the original digraph \c g is untouched.
105 105
This techniques give rise to an elegant code, and based on stable
106 106
graph adaptors, complex algorithms can be implemented easily.
107 107

	
108 108
In flow, circulation and matching problems, the residual
109 109
graph is of particular importance. Combining an adaptor implementing
110 110
this with shortest path algorithms or minimum mean cycle algorithms,
111 111
a range of weighted and cardinality optimization algorithms can be
112 112
obtained. For other examples, the interested user is referred to the
113 113
detailed documentation of particular adaptors.
114 114

	
115 115
The behavior of graph adaptors can be very different. Some of them keep
116 116
capabilities of the original graph while in other cases this would be
117 117
meaningless. This means that the concepts that they meet depend
118 118
on the graph adaptor, and the wrapped graph.
119 119
For example, if an arc of a reversed digraph is deleted, this is carried
120 120
out by deleting the corresponding arc of the original digraph, thus the
121 121
adaptor modifies the original digraph.
122 122
However in case of a residual digraph, this operation has no sense.
123 123

	
124 124
Let us stand one more example here to simplify your work.
125 125
ReverseDigraph has constructor
126 126
\code
127 127
ReverseDigraph(Digraph& digraph);
128 128
\endcode
129 129
This means that in a situation, when a <tt>const %ListDigraph&</tt>
130 130
reference to a graph is given, then it have to be instantiated with
131 131
<tt>Digraph=const %ListDigraph</tt>.
132 132
\code
133 133
int algorithm1(const ListDigraph& g) {
134 134
  ReverseDigraph<const ListDigraph> rg(g);
135 135
  return algorithm2(rg);
136 136
}
137 137
\endcode
138 138
*/
139 139

	
140 140
/**
141
@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
142
@ingroup graphs
143
\brief Graph types between real graphs and graph adaptors.
144

	
145
This group contains some graph types between real graphs and graph adaptors.
146
These classes wrap graphs to give new functionality as the adaptors do it.
147
On the other hand they are not light-weight structures as the adaptors.
148
*/
149

	
150
/**
151 141
@defgroup maps Maps
152 142
@ingroup datas
153 143
\brief Map structures implemented in LEMON.
154 144

	
155 145
This group contains the map structures implemented in LEMON.
156 146

	
157 147
LEMON provides several special purpose maps and map adaptors that e.g. combine
158 148
new maps from existing ones.
159 149

	
160 150
<b>See also:</b> \ref map_concepts "Map Concepts".
161 151
*/
162 152

	
163 153
/**
164 154
@defgroup graph_maps Graph Maps
165 155
@ingroup maps
166 156
\brief Special graph-related maps.
167 157

	
168 158
This group contains maps that are specifically designed to assign
169 159
values to the nodes and arcs/edges of graphs.
170 160

	
171 161
If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
172 162
\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
173 163
*/
174 164

	
175 165
/**
176 166
\defgroup map_adaptors Map Adaptors
177 167
\ingroup maps
178 168
\brief Tools to create new maps from existing ones
179 169

	
180 170
This group contains map adaptors that are used to create "implicit"
181 171
maps from other maps.
182 172

	
183 173
Most of them are \ref concepts::ReadMap "read-only maps".
184 174
They can make arithmetic and logical operations between one or two maps
185 175
(negation, shifting, addition, multiplication, logical 'and', 'or',
186 176
'not' etc.) or e.g. convert a map to another one of different Value type.
187 177

	
188 178
The typical usage of this classes is passing implicit maps to
189 179
algorithms.  If a function type algorithm is called then the function
190 180
type map adaptors can be used comfortable. For example let's see the
191 181
usage of map adaptors with the \c graphToEps() function.
192 182
\code
193 183
  Color nodeColor(int deg) {
194 184
    if (deg >= 2) {
195 185
      return Color(0.5, 0.0, 0.5);
196 186
    } else if (deg == 1) {
197 187
      return Color(1.0, 0.5, 1.0);
198 188
    } else {
199 189
      return Color(0.0, 0.0, 0.0);
200 190
    }
201 191
  }
202 192

	
203 193
  Digraph::NodeMap<int> degree_map(graph);
204 194

	
205 195
  graphToEps(graph, "graph.eps")
206 196
    .coords(coords).scaleToA4().undirected()
207 197
    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
208 198
    .run();
209 199
\endcode
210 200
The \c functorToMap() function makes an \c int to \c Color map from the
211 201
\c nodeColor() function. The \c composeMap() compose the \c degree_map
212 202
and the previously created map. The composed map is a proper function to
213 203
get the color of each node.
214 204

	
215 205
The usage with class type algorithms is little bit harder. In this
216 206
case the function type map adaptors can not be used, because the
217 207
function map adaptors give back temporary objects.
218 208
\code
219 209
  Digraph graph;
220 210

	
221 211
  typedef Digraph::ArcMap<double> DoubleArcMap;
222 212
  DoubleArcMap length(graph);
223 213
  DoubleArcMap speed(graph);
224 214

	
225 215
  typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
226 216
  TimeMap time(length, speed);
227 217

	
228 218
  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
229 219
  dijkstra.run(source, target);
230 220
\endcode
231 221
We have a length map and a maximum speed map on the arcs of a digraph.
232 222
The minimum time to pass the arc can be calculated as the division of
233 223
the two maps which can be done implicitly with the \c DivMap template
234 224
class. We use the implicit minimum time map as the length map of the
235 225
\c Dijkstra algorithm.
236 226
*/
237 227

	
238 228
/**
239 229
@defgroup paths Path Structures
240 230
@ingroup datas
241 231
\brief %Path structures implemented in LEMON.
242 232

	
243 233
This group contains the path structures implemented in LEMON.
244 234

	
245 235
LEMON provides flexible data structures to work with paths.
246 236
All of them have similar interfaces and they can be copied easily with
247 237
assignment operators and copy constructors. This makes it easy and
248 238
efficient to have e.g. the Dijkstra algorithm to store its result in
249 239
any kind of path structure.
250 240

	
251 241
\sa lemon::concepts::Path
252 242
*/
253 243

	
254 244
/**
255 245
@defgroup auxdat Auxiliary Data Structures
256 246
@ingroup datas
257 247
\brief Auxiliary data structures implemented in LEMON.
258 248

	
259 249
This group contains some data structures implemented in LEMON in
260 250
order to make it easier to implement combinatorial algorithms.
261 251
*/
262 252

	
263 253
/**
264 254
@defgroup algs Algorithms
265 255
\brief This group contains the several algorithms
266 256
implemented in LEMON.
267 257

	
268 258
This group contains the several algorithms
269 259
implemented in LEMON.
270 260
*/
271 261

	
272 262
/**
273 263
@defgroup search Graph Search
274 264
@ingroup algs
275 265
\brief Common graph search algorithms.
276 266

	
277 267
This group contains the common graph search algorithms, namely
278 268
\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
279 269
*/
280 270

	
281 271
/**
282 272
@defgroup shortest_path Shortest Path Algorithms
283 273
@ingroup algs
284 274
\brief Algorithms for finding shortest paths.
285 275

	
286 276
This group contains the algorithms for finding shortest paths in digraphs.
287 277

	
288 278
 - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a 
289 279
   source node when all arc lengths are non-negative.
290 280
 - \ref Suurballe A successive shortest path algorithm for finding
291 281
   arc-disjoint paths between two nodes having minimum total length.
292 282
*/
293 283

	
294 284
/**
295 285
@defgroup max_flow Maximum Flow Algorithms
296 286
@ingroup algs
297 287
\brief Algorithms for finding maximum flows.
298 288

	
299 289
This group contains the algorithms for finding maximum flows and
300 290
feasible circulations.
301 291

	
302 292
The \e maximum \e flow \e problem is to find a flow of maximum value between
303 293
a single source and a single target. Formally, there is a \f$G=(V,A)\f$
304 294
digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
305 295
\f$s, t \in V\f$ source and target nodes.
306 296
A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
307 297
following optimization problem.
308 298

	
309 299
\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
310 300
\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
311 301
    \quad \forall u\in V\setminus\{s,t\} \f]
312 302
\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
313 303

	
314 304
\ref Preflow implements the preflow push-relabel algorithm of Goldberg and
315 305
Tarjan for solving this problem. It also provides functions to query the
316 306
minimum cut, which is the dual problem of maximum flow.
317 307

	
308

	
318 309
\ref Circulation is a preflow push-relabel algorithm implemented directly 
319 310
for finding feasible circulations, which is a somewhat different problem,
320 311
but it is strongly related to maximum flow.
321 312
For more information, see \ref Circulation.
322 313
*/
323 314

	
324 315
/**
325
@defgroup min_cost_flow Minimum Cost Flow Algorithms
316
@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
326 317
@ingroup algs
327 318

	
328 319
\brief Algorithms for finding minimum cost flows and circulations.
329 320

	
330 321
This group contains the algorithms for finding minimum cost flows and
331
circulations.
332

	
333
The \e minimum \e cost \e flow \e problem is to find a feasible flow of
334
minimum total cost from a set of supply nodes to a set of demand nodes
335
in a network with capacity constraints (lower and upper bounds)
336
and arc costs.
337
Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{Z}\f$,
338
\f$upper: A\rightarrow\mathbf{Z}\cup\{+\infty\}\f$ denote the lower and
339
upper bounds for the flow values on the arcs, for which
340
\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
341
\f$cost: A\rightarrow\mathbf{Z}\f$ denotes the cost per unit flow
342
on the arcs and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
343
signed supply values of the nodes.
344
If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
345
supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
346
\f$-sup(u)\f$ demand.
347
A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution
348
of the following optimization problem.
349

	
350
\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
351
\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
352
    sup(u) \quad \forall u\in V \f]
353
\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
354

	
355
The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
356
zero or negative in order to have a feasible solution (since the sum
357
of the expressions on the left-hand side of the inequalities is zero).
358
It means that the total demand must be greater or equal to the total
359
supply and all the supplies have to be carried out from the supply nodes,
360
but there could be demands that are not satisfied.
361
If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
362
constraints have to be satisfied with equality, i.e. all demands
363
have to be satisfied and all supplies have to be used.
364

	
365
If you need the opposite inequalities in the supply/demand constraints
366
(i.e. the total demand is less than the total supply and all the demands
367
have to be satisfied while there could be supplies that are not used),
368
then you could easily transform the problem to the above form by reversing
369
the direction of the arcs and taking the negative of the supply values
370
(e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
371
However \ref NetworkSimplex algorithm also supports this form directly
372
for the sake of convenience.
373

	
374
A feasible solution for this problem can be found using \ref Circulation.
375

	
376
Note that the above formulation is actually more general than the usual
377
definition of the minimum cost flow problem, in which strict equalities
378
are required in the supply/demand contraints, i.e.
379

	
380
\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
381
    sup(u) \quad \forall u\in V. \f]
382

	
383
However if the sum of the supply values is zero, then these two problems
384
are equivalent. So if you need the equality form, you have to ensure this
385
additional contraint for the algorithms.
386

	
387
The dual solution of the minimum cost flow problem is represented by node 
388
potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
389
An \f$f: A\rightarrow\mathbf{Z}\f$ feasible solution of the problem
390
is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
391
node potentials the following \e complementary \e slackness optimality
392
conditions hold.
393

	
394
 - For all \f$uv\in A\f$ arcs:
395
   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
396
   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
397
   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
398
 - For all \f$u\in V\f$ nodes:
399
   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
400
     then \f$\pi(u)=0\f$.
401
 
402
Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
403
\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
404
\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
322
circulations. For more information about this problem and its dual
323
solution see \ref min_cost_flow "Minimum Cost Flow Problem".
405 324

	
406 325
\ref NetworkSimplex is an efficient implementation of the primal Network
407 326
Simplex algorithm for finding minimum cost flows. It also provides dual
408 327
solution (node potentials), if an optimal flow is found.
409 328
*/
410 329

	
411 330
/**
412 331
@defgroup min_cut Minimum Cut Algorithms
413 332
@ingroup algs
414 333

	
415 334
\brief Algorithms for finding minimum cut in graphs.
416 335

	
417 336
This group contains the algorithms for finding minimum cut in graphs.
418 337

	
419 338
The \e minimum \e cut \e problem is to find a non-empty and non-complete
420 339
\f$X\f$ subset of the nodes with minimum overall capacity on
421 340
outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
422 341
\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
423 342
cut is the \f$X\f$ solution of the next optimization problem:
424 343

	
425 344
\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
426 345
    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
427 346

	
428 347
LEMON contains several algorithms related to minimum cut problems:
429 348

	
430 349
- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
431 350
  in directed graphs.
432 351
- \ref GomoryHu "Gomory-Hu tree computation" for calculating
433 352
  all-pairs minimum cut in undirected graphs.
434 353

	
435 354
If you want to find minimum cut just between two distinict nodes,
436 355
see the \ref max_flow "maximum flow problem".
437 356
*/
438 357

	
439 358
/**
440 359
@defgroup graph_properties Connectivity and Other Graph Properties
441 360
@ingroup algs
442 361
\brief Algorithms for discovering the graph properties
443 362

	
444 363
This group contains the algorithms for discovering the graph properties
445 364
like connectivity, bipartiteness, euler property, simplicity etc.
446 365

	
447 366
\image html edge_biconnected_components.png
448 367
\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
449 368
*/
450 369

	
451 370
/**
452 371
@defgroup matching Matching Algorithms
453 372
@ingroup algs
454 373
\brief Algorithms for finding matchings in graphs and bipartite graphs.
455 374

	
456 375
This group contains the algorithms for calculating matchings in graphs.
457 376
The general matching problem is finding a subset of the edges for which
458 377
each node has at most one incident edge.
459 378

	
460 379
There are several different algorithms for calculate matchings in
461 380
graphs. The goal of the matching optimization
462 381
can be finding maximum cardinality, maximum weight or minimum cost
463 382
matching. The search can be constrained to find perfect or
464 383
maximum cardinality matching.
465 384

	
466 385
The matching algorithms implemented in LEMON:
467 386
- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
468 387
  maximum cardinality matching in general graphs.
469 388
- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
470 389
  maximum weighted matching in general graphs.
471 390
- \ref MaxWeightedPerfectMatching
472 391
  Edmond's blossom shrinking algorithm for calculating maximum weighted
473 392
  perfect matching in general graphs.
474 393

	
475 394
\image html bipartite_matching.png
476 395
\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
477 396
*/
478 397

	
479 398
/**
480 399
@defgroup spantree Minimum Spanning Tree Algorithms
481 400
@ingroup algs
482
\brief Algorithms for finding a minimum cost spanning tree in a graph.
401
\brief Algorithms for finding minimum cost spanning trees and arborescences.
483 402

	
484
This group contains the algorithms for finding a minimum cost spanning
485
tree in a graph.
403
This group contains the algorithms for finding minimum cost spanning
404
trees and arborescences.
486 405
*/
487 406

	
488 407
/**
489 408
@defgroup auxalg Auxiliary Algorithms
490 409
@ingroup algs
491 410
\brief Auxiliary algorithms implemented in LEMON.
492 411

	
493 412
This group contains some algorithms implemented in LEMON
494 413
in order to make it easier to implement complex algorithms.
495 414
*/
496 415

	
497 416
/**
498 417
@defgroup gen_opt_group General Optimization Tools
499 418
\brief This group contains some general optimization frameworks
500 419
implemented in LEMON.
501 420

	
502 421
This group contains some general optimization frameworks
503 422
implemented in LEMON.
504 423
*/
505 424

	
506 425
/**
507 426
@defgroup lp_group Lp and Mip Solvers
508 427
@ingroup gen_opt_group
509 428
\brief Lp and Mip solver interfaces for LEMON.
510 429

	
511 430
This group contains Lp and Mip solver interfaces for LEMON. The
512 431
various LP solvers could be used in the same manner with this
513 432
interface.
514 433
*/
515 434

	
516 435
/**
517 436
@defgroup utils Tools and Utilities
518 437
\brief Tools and utilities for programming in LEMON
519 438

	
520 439
Tools and utilities for programming in LEMON.
521 440
*/
522 441

	
523 442
/**
524 443
@defgroup gutils Basic Graph Utilities
525 444
@ingroup utils
526 445
\brief Simple basic graph utilities.
527 446

	
528 447
This group contains some simple basic graph utilities.
529 448
*/
530 449

	
531 450
/**
532 451
@defgroup misc Miscellaneous Tools
533 452
@ingroup utils
534 453
\brief Tools for development, debugging and testing.
535 454

	
536 455
This group contains several useful tools for development,
537 456
debugging and testing.
538 457
*/
539 458

	
540 459
/**
541 460
@defgroup timecount Time Measuring and Counting
542 461
@ingroup misc
543 462
\brief Simple tools for measuring the performance of algorithms.
544 463

	
545 464
This group contains simple tools for measuring the performance
546 465
of algorithms.
547 466
*/
548 467

	
549 468
/**
550 469
@defgroup exceptions Exceptions
551 470
@ingroup utils
552 471
\brief Exceptions defined in LEMON.
553 472

	
554 473
This group contains the exceptions defined in LEMON.
555 474
*/
556 475

	
557 476
/**
558 477
@defgroup io_group Input-Output
559 478
\brief Graph Input-Output methods
560 479

	
561 480
This group contains the tools for importing and exporting graphs
562 481
and graph related data. Now it supports the \ref lgf-format
563 482
"LEMON Graph Format", the \c DIMACS format and the encapsulated
564 483
postscript (EPS) format.
565 484
*/
566 485

	
567 486
/**
568 487
@defgroup lemon_io LEMON Graph Format
569 488
@ingroup io_group
570 489
\brief Reading and writing LEMON Graph Format.
571 490

	
572 491
This group contains methods for reading and writing
573 492
\ref lgf-format "LEMON Graph Format".
574 493
*/
575 494

	
576 495
/**
577 496
@defgroup eps_io Postscript Exporting
578 497
@ingroup io_group
579 498
\brief General \c EPS drawer and graph exporter
580 499

	
581 500
This group contains general \c EPS drawing methods and special
582 501
graph exporting tools.
583 502
*/
584 503

	
585 504
/**
586 505
@defgroup dimacs_group DIMACS format
587 506
@ingroup io_group
588 507
\brief Read and write files in DIMACS format
589 508

	
590 509
Tools to read a digraph from or write it to a file in DIMACS format data.
591 510
*/
592 511

	
593 512
/**
594 513
@defgroup nauty_group NAUTY Format
595 514
@ingroup io_group
596 515
\brief Read \e Nauty format
597 516

	
598 517
Tool to read graphs from \e Nauty format data.
599 518
*/
600 519

	
601 520
/**
602 521
@defgroup concept Concepts
603 522
\brief Skeleton classes and concept checking classes
604 523

	
605 524
This group contains the data/algorithm skeletons and concept checking
606 525
classes implemented in LEMON.
607 526

	
608 527
The purpose of the classes in this group is fourfold.
609 528

	
610 529
- These classes contain the documentations of the %concepts. In order
611 530
  to avoid document multiplications, an implementation of a concept
612 531
  simply refers to the corresponding concept class.
613 532

	
614 533
- These classes declare every functions, <tt>typedef</tt>s etc. an
615 534
  implementation of the %concepts should provide, however completely
616 535
  without implementations and real data structures behind the
617 536
  interface. On the other hand they should provide nothing else. All
618 537
  the algorithms working on a data structure meeting a certain concept
619 538
  should compile with these classes. (Though it will not run properly,
620 539
  of course.) In this way it is easily to check if an algorithm
621 540
  doesn't use any extra feature of a certain implementation.
622 541

	
623 542
- The concept descriptor classes also provide a <em>checker class</em>
624 543
  that makes it possible to check whether a certain implementation of a
625 544
  concept indeed provides all the required features.
626 545

	
627 546
- Finally, They can serve as a skeleton of a new implementation of a concept.
628 547
*/
629 548

	
630 549
/**
631 550
@defgroup graph_concepts Graph Structure Concepts
632 551
@ingroup concept
633 552
\brief Skeleton and concept checking classes for graph structures
634 553

	
635 554
This group contains the skeletons and concept checking classes of LEMON's
636 555
graph structures and helper classes used to implement these.
637 556
*/
638 557

	
639 558
/**
640 559
@defgroup map_concepts Map Concepts
641 560
@ingroup concept
642 561
\brief Skeleton and concept checking classes for maps
643 562

	
644 563
This group contains the skeletons and concept checking classes of maps.
645 564
*/
646 565

	
647 566
/**
648 567
\anchor demoprograms
649 568

	
650 569
@defgroup demos Demo Programs
651 570

	
652 571
Some demo programs are listed here. Their full source codes can be found in
653 572
the \c demo subdirectory of the source tree.
654 573

	
655 574
In order to compile them, use the <tt>make demo</tt> or the
656 575
<tt>make check</tt> commands.
657 576
*/
658 577

	
659 578
/**
660 579
@defgroup tools Standalone Utility Applications
661 580

	
662 581
Some utility applications are listed here.
663 582

	
664 583
The standard compilation procedure (<tt>./configure;make</tt>) will compile
665 584
them, as well.
666 585
*/
667 586

	
668 587
}
Ignore white space 6 line context
1 1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 2
 *
3 3
 * This file is a part of LEMON, a generic C++ optimization library.
4 4
 *
5 5
 * Copyright (C) 2003-2009
6 6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 8
 *
9 9
 * Permission to use, modify and distribute this software is granted
10 10
 * provided that this copyright notice appears in all copies. For
11 11
 * precise terms see the accompanying LICENSE file.
12 12
 *
13 13
 * This software is provided "AS IS" with no warranty of any kind,
14 14
 * express or implied, and with no claim as to its suitability for any
15 15
 * purpose.
16 16
 *
17 17
 */
18 18

	
19 19
/**
20 20
\mainpage LEMON Documentation
21 21

	
22 22
\section intro Introduction
23 23

	
24 24
\subsection whatis What is LEMON
25 25

	
26
LEMON stands for
27
<b>L</b>ibrary of <b>E</b>fficient <b>M</b>odels
26
LEMON stands for <b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
28 27
and <b>O</b>ptimization in <b>N</b>etworks.
29 28
It is a C++ template
30 29
library aimed at combinatorial optimization tasks which
31 30
often involve in working
32 31
with graphs.
33 32

	
34 33
<b>
35 34
LEMON is an <a class="el" href="http://opensource.org/">open&nbsp;source</a>
36 35
project.
37 36
You are free to use it in your commercial or
38 37
non-commercial applications under very permissive
39 38
\ref license "license terms".
40 39
</b>
41 40

	
42 41
\subsection howtoread How to read the documentation
43 42

	
44
If you want to get a quick start and see the most important features then
45
take a look at our \ref quicktour
46
"Quick Tour to LEMON" which will guide you along.
47

	
48
If you already feel like using our library, see the
43
If you would like to get to know the library, see
49 44
<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
50 45

	
51
If you know what you are looking for then try to find it under the
46
If you know what you are looking for, then try to find it under the
52 47
<a class="el" href="modules.html">Modules</a> section.
53 48

	
54 49
If you are a user of the old (0.x) series of LEMON, please check out the
55 50
\ref migration "Migration Guide" for the backward incompatibilities.
56 51
*/
Ignore white space 12288 line context
1 1
EXTRA_DIST += \
2 2
	lemon/lemon.pc.in \
3 3
	lemon/CMakeLists.txt
4 4

	
5 5
pkgconfig_DATA += lemon/lemon.pc
6 6

	
7 7
lib_LTLIBRARIES += lemon/libemon.la
8 8

	
9 9
lemon_libemon_la_SOURCES = \
10 10
	lemon/arg_parser.cc \
11 11
	lemon/base.cc \
12 12
	lemon/color.cc \
13 13
	lemon/lp_base.cc \
14 14
	lemon/lp_skeleton.cc \
15 15
	lemon/random.cc \
16 16
	lemon/bits/windows.cc
17 17

	
18 18
nodist_lemon_HEADERS = lemon/config.h	
19 19
	
20 20
lemon_libemon_la_CXXFLAGS = \
21 21
	$(AM_CXXFLAGS) \
22 22
	$(GLPK_CFLAGS) \
23 23
	$(CPLEX_CFLAGS) \
24 24
	$(SOPLEX_CXXFLAGS) \
25 25
	$(CLP_CXXFLAGS) \
26 26
	$(CBC_CXXFLAGS)
27 27

	
28 28
lemon_libemon_la_LDFLAGS = \
29 29
	$(GLPK_LIBS) \
30 30
	$(CPLEX_LIBS) \
31 31
	$(SOPLEX_LIBS) \
32 32
	$(CLP_LIBS) \
33 33
	$(CBC_LIBS)
34 34

	
35 35
if HAVE_GLPK
36 36
lemon_libemon_la_SOURCES += lemon/glpk.cc
37 37
endif
38 38

	
39 39
if HAVE_CPLEX
40 40
lemon_libemon_la_SOURCES += lemon/cplex.cc
41 41
endif
42 42

	
43 43
if HAVE_SOPLEX
44 44
lemon_libemon_la_SOURCES += lemon/soplex.cc
45 45
endif
46 46

	
47 47
if HAVE_CLP
48 48
lemon_libemon_la_SOURCES += lemon/clp.cc
49 49
endif
50 50

	
51 51
if HAVE_CBC
52 52
lemon_libemon_la_SOURCES += lemon/cbc.cc
53 53
endif
54 54

	
55 55
lemon_HEADERS += \
56 56
	lemon/adaptors.h \
57 57
	lemon/arg_parser.h \
58 58
	lemon/assert.h \
59 59
	lemon/bfs.h \
60 60
	lemon/bin_heap.h \
61 61
	lemon/cbc.h \
62 62
	lemon/circulation.h \
63 63
	lemon/clp.h \
64 64
	lemon/color.h \
65 65
	lemon/concept_check.h \
66 66
	lemon/connectivity.h \
67 67
	lemon/counter.h \
68 68
	lemon/core.h \
69 69
	lemon/cplex.h \
70 70
	lemon/dfs.h \
71 71
	lemon/dijkstra.h \
72 72
	lemon/dim2.h \
73 73
	lemon/dimacs.h \
74 74
	lemon/edge_set.h \
75 75
	lemon/elevator.h \
76 76
	lemon/error.h \
77 77
	lemon/euler.h \
78 78
	lemon/full_graph.h \
79 79
	lemon/glpk.h \
80 80
	lemon/gomory_hu.h \
81 81
	lemon/graph_to_eps.h \
82 82
	lemon/grid_graph.h \
83 83
	lemon/hypercube_graph.h \
84 84
	lemon/kruskal.h \
85 85
	lemon/hao_orlin.h \
86 86
	lemon/lgf_reader.h \
87 87
	lemon/lgf_writer.h \
88 88
	lemon/list_graph.h \
89 89
	lemon/lp.h \
90 90
	lemon/lp_base.h \
91 91
	lemon/lp_skeleton.h \
92 92
	lemon/list_graph.h \
93 93
	lemon/maps.h \
94 94
	lemon/matching.h \
95 95
	lemon/math.h \
96 96
	lemon/min_cost_arborescence.h \
97 97
	lemon/nauty_reader.h \
98 98
	lemon/network_simplex.h \
99 99
	lemon/path.h \
100 100
	lemon/preflow.h \
101 101
	lemon/radix_sort.h \
102 102
	lemon/random.h \
103 103
	lemon/smart_graph.h \
104 104
	lemon/soplex.h \
105 105
	lemon/suurballe.h \
106 106
	lemon/time_measure.h \
107 107
	lemon/tolerance.h \
108 108
	lemon/unionfind.h \
109 109
	lemon/bits/windows.h
110 110

	
111 111
bits_HEADERS += \
112 112
	lemon/bits/alteration_notifier.h \
113 113
	lemon/bits/array_map.h \
114
	lemon/bits/base_extender.h \
115 114
	lemon/bits/bezier.h \
116 115
	lemon/bits/default_map.h \
117 116
	lemon/bits/edge_set_extender.h \
118 117
	lemon/bits/enable_if.h \
119 118
	lemon/bits/graph_adaptor_extender.h \
120 119
	lemon/bits/graph_extender.h \
121 120
	lemon/bits/map_extender.h \
122 121
	lemon/bits/path_dump.h \
123 122
	lemon/bits/solver_bits.h \
124 123
	lemon/bits/traits.h \
125 124
	lemon/bits/variant.h \
126 125
	lemon/bits/vector_map.h
127 126

	
128 127
concept_HEADERS += \
129 128
	lemon/concepts/digraph.h \
130 129
	lemon/concepts/graph.h \
131 130
	lemon/concepts/graph_components.h \
132 131
	lemon/concepts/heap.h \
133 132
	lemon/concepts/maps.h \
134 133
	lemon/concepts/path.h
Ignore white space 6 line context
1 1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 2
 *
3 3
 * This file is a part of LEMON, a generic C++ optimization library.
4 4
 *
5 5
 * Copyright (C) 2003-2009
6 6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 8
 *
9 9
 * Permission to use, modify and distribute this software is granted
10 10
 * provided that this copyright notice appears in all copies. For
11 11
 * precise terms see the accompanying LICENSE file.
12 12
 *
13 13
 * This software is provided "AS IS" with no warranty of any kind,
14 14
 * express or implied, and with no claim as to its suitability for any
15 15
 * purpose.
16 16
 *
17 17
 */
18 18

	
19 19
#ifndef LEMON_ADAPTORS_H
20 20
#define LEMON_ADAPTORS_H
21 21

	
22 22
/// \ingroup graph_adaptors
23 23
/// \file
24 24
/// \brief Adaptor classes for digraphs and graphs
25 25
///
26 26
/// This file contains several useful adaptors for digraphs and graphs.
27 27

	
28 28
#include <lemon/core.h>
29 29
#include <lemon/maps.h>
30 30
#include <lemon/bits/variant.h>
31 31

	
32 32
#include <lemon/bits/graph_adaptor_extender.h>
33 33
#include <lemon/bits/map_extender.h>
34 34
#include <lemon/tolerance.h>
35 35

	
36 36
#include <algorithm>
37 37

	
38 38
namespace lemon {
39 39

	
40 40
#ifdef _MSC_VER
41 41
#define LEMON_SCOPE_FIX(OUTER, NESTED) OUTER::NESTED
42 42
#else
43 43
#define LEMON_SCOPE_FIX(OUTER, NESTED) typename OUTER::template NESTED
44 44
#endif
45 45

	
46 46
  template<typename DGR>
47 47
  class DigraphAdaptorBase {
48 48
  public:
49 49
    typedef DGR Digraph;
50 50
    typedef DigraphAdaptorBase Adaptor;
51 51

	
52 52
  protected:
53 53
    DGR* _digraph;
54 54
    DigraphAdaptorBase() : _digraph(0) { }
55 55
    void initialize(DGR& digraph) { _digraph = &digraph; }
56 56

	
57 57
  public:
58 58
    DigraphAdaptorBase(DGR& digraph) : _digraph(&digraph) { }
59 59

	
60 60
    typedef typename DGR::Node Node;
61 61
    typedef typename DGR::Arc Arc;
62 62

	
63 63
    void first(Node& i) const { _digraph->first(i); }
64 64
    void first(Arc& i) const { _digraph->first(i); }
65 65
    void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); }
66 66
    void firstOut(Arc& i, const Node& n ) const { _digraph->firstOut(i, n); }
67 67

	
68 68
    void next(Node& i) const { _digraph->next(i); }
69 69
    void next(Arc& i) const { _digraph->next(i); }
70 70
    void nextIn(Arc& i) const { _digraph->nextIn(i); }
71 71
    void nextOut(Arc& i) const { _digraph->nextOut(i); }
72 72

	
73 73
    Node source(const Arc& a) const { return _digraph->source(a); }
74 74
    Node target(const Arc& a) const { return _digraph->target(a); }
75 75

	
76 76
    typedef NodeNumTagIndicator<DGR> NodeNumTag;
77 77
    int nodeNum() const { return _digraph->nodeNum(); }
78 78

	
79 79
    typedef ArcNumTagIndicator<DGR> ArcNumTag;
80 80
    int arcNum() const { return _digraph->arcNum(); }
81 81

	
82 82
    typedef FindArcTagIndicator<DGR> FindArcTag;
83 83
    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const {
84 84
      return _digraph->findArc(u, v, prev);
85 85
    }
86 86

	
87 87
    Node addNode() { return _digraph->addNode(); }
88 88
    Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
89 89

	
90 90
    void erase(const Node& n) { _digraph->erase(n); }
91 91
    void erase(const Arc& a) { _digraph->erase(a); }
92 92

	
93 93
    void clear() { _digraph->clear(); }
94 94

	
95 95
    int id(const Node& n) const { return _digraph->id(n); }
96 96
    int id(const Arc& a) const { return _digraph->id(a); }
97 97

	
98 98
    Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
99 99
    Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); }
100 100

	
101 101
    int maxNodeId() const { return _digraph->maxNodeId(); }
102 102
    int maxArcId() const { return _digraph->maxArcId(); }
103 103

	
104 104
    typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
105 105
    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
106 106

	
107 107
    typedef typename ItemSetTraits<DGR, Arc>::ItemNotifier ArcNotifier;
108 108
    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
109 109

	
110 110
    template <typename V>
111 111
    class NodeMap : public DGR::template NodeMap<V> {
112 112
      typedef typename DGR::template NodeMap<V> Parent;
113 113

	
114 114
    public:
115 115
      explicit NodeMap(const Adaptor& adaptor)
116 116
        : Parent(*adaptor._digraph) {}
117 117
      NodeMap(const Adaptor& adaptor, const V& value)
118 118
        : Parent(*adaptor._digraph, value) { }
119 119

	
120 120
    private:
121 121
      NodeMap& operator=(const NodeMap& cmap) {
122 122
        return operator=<NodeMap>(cmap);
123 123
      }
124 124

	
125 125
      template <typename CMap>
126 126
      NodeMap& operator=(const CMap& cmap) {
127 127
        Parent::operator=(cmap);
128 128
        return *this;
129 129
      }
130 130

	
131 131
    };
132 132

	
133 133
    template <typename V>
134 134
    class ArcMap : public DGR::template ArcMap<V> {
135 135
      typedef typename DGR::template ArcMap<V> Parent;
136 136

	
137 137
    public:
138 138
      explicit ArcMap(const DigraphAdaptorBase<DGR>& adaptor)
139 139
        : Parent(*adaptor._digraph) {}
140 140
      ArcMap(const DigraphAdaptorBase<DGR>& adaptor, const V& value)
141 141
        : Parent(*adaptor._digraph, value) {}
142 142

	
143 143
    private:
144 144
      ArcMap& operator=(const ArcMap& cmap) {
145 145
        return operator=<ArcMap>(cmap);
146 146
      }
147 147

	
148 148
      template <typename CMap>
149 149
      ArcMap& operator=(const CMap& cmap) {
150 150
        Parent::operator=(cmap);
151 151
        return *this;
152 152
      }
153 153

	
154 154
    };
155 155

	
156 156
  };
157 157

	
158 158
  template<typename GR>
159 159
  class GraphAdaptorBase {
160 160
  public:
161 161
    typedef GR Graph;
162 162

	
163 163
  protected:
164 164
    GR* _graph;
165 165

	
166 166
    GraphAdaptorBase() : _graph(0) {}
167 167

	
168 168
    void initialize(GR& graph) { _graph = &graph; }
169 169

	
170 170
  public:
171 171
    GraphAdaptorBase(GR& graph) : _graph(&graph) {}
172 172

	
173 173
    typedef typename GR::Node Node;
174 174
    typedef typename GR::Arc Arc;
175 175
    typedef typename GR::Edge Edge;
176 176

	
177 177
    void first(Node& i) const { _graph->first(i); }
178 178
    void first(Arc& i) const { _graph->first(i); }
179 179
    void first(Edge& i) const { _graph->first(i); }
180 180
    void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); }
181 181
    void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); }
182 182
    void firstInc(Edge &i, bool &d, const Node &n) const {
183 183
      _graph->firstInc(i, d, n);
184 184
    }
185 185

	
186 186
    void next(Node& i) const { _graph->next(i); }
187 187
    void next(Arc& i) const { _graph->next(i); }
188 188
    void next(Edge& i) const { _graph->next(i); }
189 189
    void nextIn(Arc& i) const { _graph->nextIn(i); }
190 190
    void nextOut(Arc& i) const { _graph->nextOut(i); }
191 191
    void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); }
192 192

	
193 193
    Node u(const Edge& e) const { return _graph->u(e); }
194 194
    Node v(const Edge& e) const { return _graph->v(e); }
195 195

	
196 196
    Node source(const Arc& a) const { return _graph->source(a); }
197 197
    Node target(const Arc& a) const { return _graph->target(a); }
198 198

	
199 199
    typedef NodeNumTagIndicator<Graph> NodeNumTag;
200 200
    int nodeNum() const { return _graph->nodeNum(); }
201 201

	
202 202
    typedef ArcNumTagIndicator<Graph> ArcNumTag;
203 203
    int arcNum() const { return _graph->arcNum(); }
204 204

	
205 205
    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
206 206
    int edgeNum() const { return _graph->edgeNum(); }
207 207

	
208 208
    typedef FindArcTagIndicator<Graph> FindArcTag;
209 209
    Arc findArc(const Node& u, const Node& v,
210 210
                const Arc& prev = INVALID) const {
211 211
      return _graph->findArc(u, v, prev);
212 212
    }
213 213

	
214 214
    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
215 215
    Edge findEdge(const Node& u, const Node& v,
216 216
                  const Edge& prev = INVALID) const {
217 217
      return _graph->findEdge(u, v, prev);
218 218
    }
219 219

	
220 220
    Node addNode() { return _graph->addNode(); }
221 221
    Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }
222 222

	
223 223
    void erase(const Node& i) { _graph->erase(i); }
224 224
    void erase(const Edge& i) { _graph->erase(i); }
225 225

	
226 226
    void clear() { _graph->clear(); }
227 227

	
228 228
    bool direction(const Arc& a) const { return _graph->direction(a); }
229 229
    Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); }
230 230

	
231 231
    int id(const Node& v) const { return _graph->id(v); }
232 232
    int id(const Arc& a) const { return _graph->id(a); }
233 233
    int id(const Edge& e) const { return _graph->id(e); }
234 234

	
235 235
    Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
236 236
    Arc arcFromId(int ix) const { return _graph->arcFromId(ix); }
237 237
    Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); }
238 238

	
239 239
    int maxNodeId() const { return _graph->maxNodeId(); }
240 240
    int maxArcId() const { return _graph->maxArcId(); }
241 241
    int maxEdgeId() const { return _graph->maxEdgeId(); }
242 242

	
243 243
    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
244 244
    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
245 245

	
246 246
    typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;
247 247
    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
248 248

	
249 249
    typedef typename ItemSetTraits<GR, Edge>::ItemNotifier EdgeNotifier;
250 250
    EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
251 251

	
252 252
    template <typename V>
253 253
    class NodeMap : public GR::template NodeMap<V> {
254 254
      typedef typename GR::template NodeMap<V> Parent;
255 255

	
256 256
    public:
257 257
      explicit NodeMap(const GraphAdaptorBase<GR>& adapter)
258 258
        : Parent(*adapter._graph) {}
259 259
      NodeMap(const GraphAdaptorBase<GR>& adapter, const V& value)
260 260
        : Parent(*adapter._graph, value) {}
261 261

	
262 262
    private:
263 263
      NodeMap& operator=(const NodeMap& cmap) {
264 264
        return operator=<NodeMap>(cmap);
265 265
      }
266 266

	
267 267
      template <typename CMap>
268 268
      NodeMap& operator=(const CMap& cmap) {
269 269
        Parent::operator=(cmap);
270 270
        return *this;
271 271
      }
272 272

	
273 273
    };
274 274

	
275 275
    template <typename V>
276 276
    class ArcMap : public GR::template ArcMap<V> {
277 277
      typedef typename GR::template ArcMap<V> Parent;
278 278

	
279 279
    public:
280 280
      explicit ArcMap(const GraphAdaptorBase<GR>& adapter)
281 281
        : Parent(*adapter._graph) {}
282 282
      ArcMap(const GraphAdaptorBase<GR>& adapter, const V& value)
283 283
        : Parent(*adapter._graph, value) {}
284 284

	
285 285
    private:
286 286
      ArcMap& operator=(const ArcMap& cmap) {
287 287
        return operator=<ArcMap>(cmap);
288 288
      }
289 289

	
290 290
      template <typename CMap>
291 291
      ArcMap& operator=(const CMap& cmap) {
292 292
        Parent::operator=(cmap);
293 293
        return *this;
294 294
      }
295 295
    };
296 296

	
297 297
    template <typename V>
298 298
    class EdgeMap : public GR::template EdgeMap<V> {
299 299
      typedef typename GR::template EdgeMap<V> Parent;
300 300

	
301 301
    public:
302 302
      explicit EdgeMap(const GraphAdaptorBase<GR>& adapter)
303 303
        : Parent(*adapter._graph) {}
304 304
      EdgeMap(const GraphAdaptorBase<GR>& adapter, const V& value)
305 305
        : Parent(*adapter._graph, value) {}
306 306

	
307 307
    private:
308 308
      EdgeMap& operator=(const EdgeMap& cmap) {
309 309
        return operator=<EdgeMap>(cmap);
310 310
      }
311 311

	
312 312
      template <typename CMap>
313 313
      EdgeMap& operator=(const CMap& cmap) {
314 314
        Parent::operator=(cmap);
315 315
        return *this;
316 316
      }
317 317
    };
318 318

	
319 319
  };
320 320

	
321 321
  template <typename DGR>
322 322
  class ReverseDigraphBase : public DigraphAdaptorBase<DGR> {
323 323
    typedef DigraphAdaptorBase<DGR> Parent;
324 324
  public:
325 325
    typedef DGR Digraph;
326 326
  protected:
327 327
    ReverseDigraphBase() : Parent() { }
328 328
  public:
329 329
    typedef typename Parent::Node Node;
330 330
    typedef typename Parent::Arc Arc;
331 331

	
332 332
    void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }
333 333
    void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); }
334 334

	
335 335
    void nextIn(Arc& a) const { Parent::nextOut(a); }
336 336
    void nextOut(Arc& a) const { Parent::nextIn(a); }
337 337

	
338 338
    Node source(const Arc& a) const { return Parent::target(a); }
339 339
    Node target(const Arc& a) const { return Parent::source(a); }
340 340

	
341 341
    Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
342 342

	
343 343
    typedef FindArcTagIndicator<DGR> FindArcTag;
344 344
    Arc findArc(const Node& u, const Node& v,
345 345
                const Arc& prev = INVALID) const {
346 346
      return Parent::findArc(v, u, prev);
347 347
    }
348 348

	
349 349
  };
350 350

	
351 351
  /// \ingroup graph_adaptors
352 352
  ///
353 353
  /// \brief Adaptor class for reversing the orientation of the arcs in
354 354
  /// a digraph.
355 355
  ///
356 356
  /// ReverseDigraph can be used for reversing the arcs in a digraph.
357 357
  /// It conforms to the \ref concepts::Digraph "Digraph" concept.
358 358
  ///
359 359
  /// The adapted digraph can also be modified through this adaptor
360 360
  /// by adding or removing nodes or arcs, unless the \c GR template
361 361
  /// parameter is set to be \c const.
362 362
  ///
363 363
  /// \tparam DGR The type of the adapted digraph.
364 364
  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
365 365
  /// It can also be specified to be \c const.
366 366
  ///
367 367
  /// \note The \c Node and \c Arc types of this adaptor and the adapted
368 368
  /// digraph are convertible to each other.
369 369
  template<typename DGR>
370 370
#ifdef DOXYGEN
371 371
  class ReverseDigraph {
372 372
#else
373 373
  class ReverseDigraph :
374 374
    public DigraphAdaptorExtender<ReverseDigraphBase<DGR> > {
375 375
#endif
376 376
    typedef DigraphAdaptorExtender<ReverseDigraphBase<DGR> > Parent;
377 377
  public:
378 378
    /// The type of the adapted digraph.
379 379
    typedef DGR Digraph;
380 380
  protected:
381 381
    ReverseDigraph() { }
382 382
  public:
383 383

	
384 384
    /// \brief Constructor
385 385
    ///
386 386
    /// Creates a reverse digraph adaptor for the given digraph.
387 387
    explicit ReverseDigraph(DGR& digraph) {
388 388
      Parent::initialize(digraph);
389 389
    }
390 390
  };
391 391

	
392 392
  /// \brief Returns a read-only ReverseDigraph adaptor
393 393
  ///
394 394
  /// This function just returns a read-only \ref ReverseDigraph adaptor.
395 395
  /// \ingroup graph_adaptors
396 396
  /// \relates ReverseDigraph
397 397
  template<typename DGR>
398 398
  ReverseDigraph<const DGR> reverseDigraph(const DGR& digraph) {
399 399
    return ReverseDigraph<const DGR>(digraph);
400 400
  }
401 401

	
402 402

	
403 403
  template <typename DGR, typename NF, typename AF, bool ch = true>
404 404
  class SubDigraphBase : public DigraphAdaptorBase<DGR> {
405 405
    typedef DigraphAdaptorBase<DGR> Parent;
406 406
  public:
407 407
    typedef DGR Digraph;
408 408
    typedef NF NodeFilterMap;
409 409
    typedef AF ArcFilterMap;
410 410

	
411 411
    typedef SubDigraphBase Adaptor;
412 412
  protected:
413 413
    NF* _node_filter;
414 414
    AF* _arc_filter;
415 415
    SubDigraphBase()
416 416
      : Parent(), _node_filter(0), _arc_filter(0) { }
417 417

	
418 418
    void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
419 419
      Parent::initialize(digraph);
420 420
      _node_filter = &node_filter;
421 421
      _arc_filter = &arc_filter;      
422 422
    }
423 423

	
424 424
  public:
425 425

	
426 426
    typedef typename Parent::Node Node;
427 427
    typedef typename Parent::Arc Arc;
428 428

	
429 429
    void first(Node& i) const {
430 430
      Parent::first(i);
431 431
      while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
432 432
    }
433 433

	
434 434
    void first(Arc& i) const {
435 435
      Parent::first(i);
436 436
      while (i != INVALID && (!(*_arc_filter)[i]
437 437
                              || !(*_node_filter)[Parent::source(i)]
438 438
                              || !(*_node_filter)[Parent::target(i)]))
439 439
        Parent::next(i);
440 440
    }
441 441

	
442 442
    void firstIn(Arc& i, const Node& n) const {
443 443
      Parent::firstIn(i, n);
444 444
      while (i != INVALID && (!(*_arc_filter)[i]
445 445
                              || !(*_node_filter)[Parent::source(i)]))
446 446
        Parent::nextIn(i);
447 447
    }
448 448

	
449 449
    void firstOut(Arc& i, const Node& n) const {
450 450
      Parent::firstOut(i, n);
451 451
      while (i != INVALID && (!(*_arc_filter)[i]
452 452
                              || !(*_node_filter)[Parent::target(i)]))
453 453
        Parent::nextOut(i);
454 454
    }
455 455

	
456 456
    void next(Node& i) const {
457 457
      Parent::next(i);
458 458
      while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
459 459
    }
460 460

	
461 461
    void next(Arc& i) const {
462 462
      Parent::next(i);
463 463
      while (i != INVALID && (!(*_arc_filter)[i]
464 464
                              || !(*_node_filter)[Parent::source(i)]
465 465
                              || !(*_node_filter)[Parent::target(i)]))
466 466
        Parent::next(i);
467 467
    }
468 468

	
469 469
    void nextIn(Arc& i) const {
470 470
      Parent::nextIn(i);
471 471
      while (i != INVALID && (!(*_arc_filter)[i]
472 472
                              || !(*_node_filter)[Parent::source(i)]))
473 473
        Parent::nextIn(i);
474 474
    }
475 475

	
476 476
    void nextOut(Arc& i) const {
477 477
      Parent::nextOut(i);
478 478
      while (i != INVALID && (!(*_arc_filter)[i]
479 479
                              || !(*_node_filter)[Parent::target(i)]))
480 480
        Parent::nextOut(i);
481 481
    }
482 482

	
483 483
    void status(const Node& n, bool v) const { _node_filter->set(n, v); }
484 484
    void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
485 485

	
486 486
    bool status(const Node& n) const { return (*_node_filter)[n]; }
487 487
    bool status(const Arc& a) const { return (*_arc_filter)[a]; }
488 488

	
489 489
    typedef False NodeNumTag;
490 490
    typedef False ArcNumTag;
491 491

	
492 492
    typedef FindArcTagIndicator<DGR> FindArcTag;
493 493
    Arc findArc(const Node& source, const Node& target,
494 494
                const Arc& prev = INVALID) const {
495 495
      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
496 496
        return INVALID;
497 497
      }
498 498
      Arc arc = Parent::findArc(source, target, prev);
499 499
      while (arc != INVALID && !(*_arc_filter)[arc]) {
500 500
        arc = Parent::findArc(source, target, arc);
501 501
      }
502 502
      return arc;
503 503
    }
504 504

	
505 505
  public:
506 506

	
507 507
    template <typename V>
508 508
    class NodeMap 
509 509
      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 
510 510
	      LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
511 511
      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
512 512
	LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
513 513

	
514 514
    public:
515 515
      typedef V Value;
516 516

	
517 517
      NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
518 518
        : Parent(adaptor) {}
519 519
      NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
520 520
        : Parent(adaptor, value) {}
521 521

	
522 522
    private:
523 523
      NodeMap& operator=(const NodeMap& cmap) {
524 524
        return operator=<NodeMap>(cmap);
525 525
      }
526 526

	
527 527
      template <typename CMap>
528 528
      NodeMap& operator=(const CMap& cmap) {
529 529
        Parent::operator=(cmap);
530 530
        return *this;
531 531
      }
532 532
    };
533 533

	
534 534
    template <typename V>
535 535
    class ArcMap 
536 536
      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
537 537
	      LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
538 538
      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
539 539
        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
540 540

	
541 541
    public:
542 542
      typedef V Value;
543 543

	
544 544
      ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
545 545
        : Parent(adaptor) {}
546 546
      ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
547 547
        : Parent(adaptor, value) {}
548 548

	
549 549
    private:
550 550
      ArcMap& operator=(const ArcMap& cmap) {
551 551
        return operator=<ArcMap>(cmap);
552 552
      }
553 553

	
554 554
      template <typename CMap>
555 555
      ArcMap& operator=(const CMap& cmap) {
556 556
        Parent::operator=(cmap);
557 557
        return *this;
558 558
      }
559 559
    };
560 560

	
561 561
  };
562 562

	
563 563
  template <typename DGR, typename NF, typename AF>
564 564
  class SubDigraphBase<DGR, NF, AF, false>
565 565
    : public DigraphAdaptorBase<DGR> {
566 566
    typedef DigraphAdaptorBase<DGR> Parent;
567 567
  public:
568 568
    typedef DGR Digraph;
569 569
    typedef NF NodeFilterMap;
570 570
    typedef AF ArcFilterMap;
571 571

	
572 572
    typedef SubDigraphBase Adaptor;
573 573
  protected:
574 574
    NF* _node_filter;
575 575
    AF* _arc_filter;
576 576
    SubDigraphBase()
577 577
      : Parent(), _node_filter(0), _arc_filter(0) { }
578 578

	
579 579
    void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
580 580
      Parent::initialize(digraph);
581 581
      _node_filter = &node_filter;
582 582
      _arc_filter = &arc_filter;      
583 583
    }
584 584

	
585 585
  public:
586 586

	
587 587
    typedef typename Parent::Node Node;
588 588
    typedef typename Parent::Arc Arc;
589 589

	
590 590
    void first(Node& i) const {
591 591
      Parent::first(i);
592 592
      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
593 593
    }
594 594

	
595 595
    void first(Arc& i) const {
596 596
      Parent::first(i);
597 597
      while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
598 598
    }
599 599

	
600 600
    void firstIn(Arc& i, const Node& n) const {
601 601
      Parent::firstIn(i, n);
602 602
      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
603 603
    }
604 604

	
605 605
    void firstOut(Arc& i, const Node& n) const {
606 606
      Parent::firstOut(i, n);
607 607
      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
608 608
    }
609 609

	
610 610
    void next(Node& i) const {
611 611
      Parent::next(i);
612 612
      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
613 613
    }
614 614
    void next(Arc& i) const {
615 615
      Parent::next(i);
616 616
      while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
617 617
    }
618 618
    void nextIn(Arc& i) const {
619 619
      Parent::nextIn(i);
620 620
      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
621 621
    }
622 622

	
623 623
    void nextOut(Arc& i) const {
624 624
      Parent::nextOut(i);
625 625
      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
626 626
    }
627 627

	
628 628
    void status(const Node& n, bool v) const { _node_filter->set(n, v); }
629 629
    void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
630 630

	
631 631
    bool status(const Node& n) const { return (*_node_filter)[n]; }
632 632
    bool status(const Arc& a) const { return (*_arc_filter)[a]; }
633 633

	
634 634
    typedef False NodeNumTag;
635 635
    typedef False ArcNumTag;
636 636

	
637 637
    typedef FindArcTagIndicator<DGR> FindArcTag;
638 638
    Arc findArc(const Node& source, const Node& target,
639 639
                const Arc& prev = INVALID) const {
640 640
      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
641 641
        return INVALID;
642 642
      }
643 643
      Arc arc = Parent::findArc(source, target, prev);
644 644
      while (arc != INVALID && !(*_arc_filter)[arc]) {
645 645
        arc = Parent::findArc(source, target, arc);
646 646
      }
647 647
      return arc;
648 648
    }
649 649

	
650 650
    template <typename V>
651 651
    class NodeMap 
652 652
      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
653 653
          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
654 654
      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 
655 655
        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
656 656

	
657 657
    public:
658 658
      typedef V Value;
659 659

	
660 660
      NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
661 661
        : Parent(adaptor) {}
662 662
      NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
663 663
        : Parent(adaptor, value) {}
664 664

	
665 665
    private:
666 666
      NodeMap& operator=(const NodeMap& cmap) {
667 667
        return operator=<NodeMap>(cmap);
668 668
      }
669 669

	
670 670
      template <typename CMap>
671 671
      NodeMap& operator=(const CMap& cmap) {
672 672
        Parent::operator=(cmap);
673 673
        return *this;
674 674
      }
675 675
    };
676 676

	
677 677
    template <typename V>
678 678
    class ArcMap 
679 679
      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
680 680
          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
681 681
      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
682 682
        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
683 683

	
684 684
    public:
685 685
      typedef V Value;
686 686

	
687 687
      ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
688 688
        : Parent(adaptor) {}
689 689
      ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
690 690
        : Parent(adaptor, value) {}
691 691

	
692 692
    private:
693 693
      ArcMap& operator=(const ArcMap& cmap) {
694 694
        return operator=<ArcMap>(cmap);
695 695
      }
696 696

	
697 697
      template <typename CMap>
698 698
      ArcMap& operator=(const CMap& cmap) {
699 699
        Parent::operator=(cmap);
700 700
        return *this;
701 701
      }
702 702
    };
703 703

	
704 704
  };
705 705

	
706 706
  /// \ingroup graph_adaptors
707 707
  ///
708 708
  /// \brief Adaptor class for hiding nodes and arcs in a digraph
709 709
  ///
710 710
  /// SubDigraph can be used for hiding nodes and arcs in a digraph.
711 711
  /// A \c bool node map and a \c bool arc map must be specified, which
712 712
  /// define the filters for nodes and arcs.
713 713
  /// Only the nodes and arcs with \c true filter value are
714 714
  /// shown in the subdigraph. The arcs that are incident to hidden
715 715
  /// nodes are also filtered out.
716 716
  /// This adaptor conforms to the \ref concepts::Digraph "Digraph" concept.
717 717
  ///
718 718
  /// The adapted digraph can also be modified through this adaptor
719 719
  /// by adding or removing nodes or arcs, unless the \c GR template
720 720
  /// parameter is set to be \c const.
721 721
  ///
722 722
  /// \tparam DGR The type of the adapted digraph.
723 723
  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
724 724
  /// It can also be specified to be \c const.
725 725
  /// \tparam NF The type of the node filter map.
726 726
  /// It must be a \c bool (or convertible) node map of the
727 727
  /// adapted digraph. The default type is
728 728
  /// \ref concepts::Digraph::NodeMap "DGR::NodeMap<bool>".
729 729
  /// \tparam AF The type of the arc filter map.
730 730
  /// It must be \c bool (or convertible) arc map of the
731 731
  /// adapted digraph. The default type is
732 732
  /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>".
733 733
  ///
734 734
  /// \note The \c Node and \c Arc types of this adaptor and the adapted
735 735
  /// digraph are convertible to each other.
736 736
  ///
737 737
  /// \see FilterNodes
738 738
  /// \see FilterArcs
739 739
#ifdef DOXYGEN
740 740
  template<typename DGR, typename NF, typename AF>
741 741
  class SubDigraph {
742 742
#else
743 743
  template<typename DGR,
744 744
           typename NF = typename DGR::template NodeMap<bool>,
745 745
           typename AF = typename DGR::template ArcMap<bool> >
746 746
  class SubDigraph :
747 747
    public DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> > {
748 748
#endif
749 749
  public:
750 750
    /// The type of the adapted digraph.
751 751
    typedef DGR Digraph;
752 752
    /// The type of the node filter map.
753 753
    typedef NF NodeFilterMap;
754 754
    /// The type of the arc filter map.
755 755
    typedef AF ArcFilterMap;
756 756

	
757 757
    typedef DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> >
758 758
      Parent;
759 759

	
760 760
    typedef typename Parent::Node Node;
761 761
    typedef typename Parent::Arc Arc;
762 762

	
763 763
  protected:
764 764
    SubDigraph() { }
765 765
  public:
766 766

	
767 767
    /// \brief Constructor
768 768
    ///
769 769
    /// Creates a subdigraph for the given digraph with the
770 770
    /// given node and arc filter maps.
771 771
    SubDigraph(DGR& digraph, NF& node_filter, AF& arc_filter) {
772 772
      Parent::initialize(digraph, node_filter, arc_filter);
773 773
    }
774 774

	
775 775
    /// \brief Sets the status of the given node
776 776
    ///
777 777
    /// This function sets the status of the given node.
778 778
    /// It is done by simply setting the assigned value of \c n
779 779
    /// to \c v in the node filter map.
780 780
    void status(const Node& n, bool v) const { Parent::status(n, v); }
781 781

	
782 782
    /// \brief Sets the status of the given arc
783 783
    ///
784 784
    /// This function sets the status of the given arc.
785 785
    /// It is done by simply setting the assigned value of \c a
786 786
    /// to \c v in the arc filter map.
787 787
    void status(const Arc& a, bool v) const { Parent::status(a, v); }
788 788

	
789 789
    /// \brief Returns the status of the given node
790 790
    ///
791 791
    /// This function returns the status of the given node.
792 792
    /// It is \c true if the given node is enabled (i.e. not hidden).
793 793
    bool status(const Node& n) const { return Parent::status(n); }
794 794

	
795 795
    /// \brief Returns the status of the given arc
796 796
    ///
797 797
    /// This function returns the status of the given arc.
798 798
    /// It is \c true if the given arc is enabled (i.e. not hidden).
799 799
    bool status(const Arc& a) const { return Parent::status(a); }
800 800

	
801 801
    /// \brief Disables the given node
802 802
    ///
803 803
    /// This function disables the given node in the subdigraph,
804 804
    /// so the iteration jumps over it.
805 805
    /// It is the same as \ref status() "status(n, false)".
806 806
    void disable(const Node& n) const { Parent::status(n, false); }
807 807

	
808 808
    /// \brief Disables the given arc
809 809
    ///
810 810
    /// This function disables the given arc in the subdigraph,
811 811
    /// so the iteration jumps over it.
812 812
    /// It is the same as \ref status() "status(a, false)".
813 813
    void disable(const Arc& a) const { Parent::status(a, false); }
814 814

	
815 815
    /// \brief Enables the given node
816 816
    ///
817 817
    /// This function enables the given node in the subdigraph.
818 818
    /// It is the same as \ref status() "status(n, true)".
819 819
    void enable(const Node& n) const { Parent::status(n, true); }
820 820

	
821 821
    /// \brief Enables the given arc
822 822
    ///
823 823
    /// This function enables the given arc in the subdigraph.
824 824
    /// It is the same as \ref status() "status(a, true)".
825 825
    void enable(const Arc& a) const { Parent::status(a, true); }
826 826

	
827 827
  };
828 828

	
829 829
  /// \brief Returns a read-only SubDigraph adaptor
830 830
  ///
831 831
  /// This function just returns a read-only \ref SubDigraph adaptor.
832 832
  /// \ingroup graph_adaptors
833 833
  /// \relates SubDigraph
834 834
  template<typename DGR, typename NF, typename AF>
835 835
  SubDigraph<const DGR, NF, AF>
836 836
  subDigraph(const DGR& digraph,
837 837
             NF& node_filter, AF& arc_filter) {
838 838
    return SubDigraph<const DGR, NF, AF>
839 839
      (digraph, node_filter, arc_filter);
840 840
  }
841 841

	
842 842
  template<typename DGR, typename NF, typename AF>
843 843
  SubDigraph<const DGR, const NF, AF>
844 844
  subDigraph(const DGR& digraph,
845 845
             const NF& node_filter, AF& arc_filter) {
846 846
    return SubDigraph<const DGR, const NF, AF>
847 847
      (digraph, node_filter, arc_filter);
848 848
  }
849 849

	
850 850
  template<typename DGR, typename NF, typename AF>
851 851
  SubDigraph<const DGR, NF, const AF>
852 852
  subDigraph(const DGR& digraph,
853 853
             NF& node_filter, const AF& arc_filter) {
854 854
    return SubDigraph<const DGR, NF, const AF>
855 855
      (digraph, node_filter, arc_filter);
856 856
  }
857 857

	
858 858
  template<typename DGR, typename NF, typename AF>
859 859
  SubDigraph<const DGR, const NF, const AF>
860 860
  subDigraph(const DGR& digraph,
861 861
             const NF& node_filter, const AF& arc_filter) {
862 862
    return SubDigraph<const DGR, const NF, const AF>
863 863
      (digraph, node_filter, arc_filter);
864 864
  }
865 865

	
866 866

	
867 867
  template <typename GR, typename NF, typename EF, bool ch = true>
868 868
  class SubGraphBase : public GraphAdaptorBase<GR> {
869 869
    typedef GraphAdaptorBase<GR> Parent;
870 870
  public:
871 871
    typedef GR Graph;
872 872
    typedef NF NodeFilterMap;
873 873
    typedef EF EdgeFilterMap;
874 874

	
875 875
    typedef SubGraphBase Adaptor;
876 876
  protected:
877 877

	
878 878
    NF* _node_filter;
879 879
    EF* _edge_filter;
880 880

	
881 881
    SubGraphBase()
882 882
      : Parent(), _node_filter(0), _edge_filter(0) { }
883 883

	
884 884
    void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
885 885
      Parent::initialize(graph);
886 886
      _node_filter = &node_filter;
887 887
      _edge_filter = &edge_filter;
888 888
    }
889 889

	
890 890
  public:
891 891

	
892 892
    typedef typename Parent::Node Node;
893 893
    typedef typename Parent::Arc Arc;
894 894
    typedef typename Parent::Edge Edge;
895 895

	
896 896
    void first(Node& i) const {
897 897
      Parent::first(i);
898 898
      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
899 899
    }
900 900

	
901 901
    void first(Arc& i) const {
902 902
      Parent::first(i);
903 903
      while (i!=INVALID && (!(*_edge_filter)[i]
904 904
                            || !(*_node_filter)[Parent::source(i)]
905 905
                            || !(*_node_filter)[Parent::target(i)]))
906 906
        Parent::next(i);
907 907
    }
908 908

	
909 909
    void first(Edge& i) const {
910 910
      Parent::first(i);
911 911
      while (i!=INVALID && (!(*_edge_filter)[i]
912 912
                            || !(*_node_filter)[Parent::u(i)]
913 913
                            || !(*_node_filter)[Parent::v(i)]))
914 914
        Parent::next(i);
915 915
    }
916 916

	
917 917
    void firstIn(Arc& i, const Node& n) const {
918 918
      Parent::firstIn(i, n);
919 919
      while (i!=INVALID && (!(*_edge_filter)[i]
920 920
                            || !(*_node_filter)[Parent::source(i)]))
921 921
        Parent::nextIn(i);
922 922
    }
923 923

	
924 924
    void firstOut(Arc& i, const Node& n) const {
925 925
      Parent::firstOut(i, n);
926 926
      while (i!=INVALID && (!(*_edge_filter)[i]
927 927
                            || !(*_node_filter)[Parent::target(i)]))
928 928
        Parent::nextOut(i);
929 929
    }
930 930

	
931 931
    void firstInc(Edge& i, bool& d, const Node& n) const {
932 932
      Parent::firstInc(i, d, n);
933 933
      while (i!=INVALID && (!(*_edge_filter)[i]
934 934
                            || !(*_node_filter)[Parent::u(i)]
935 935
                            || !(*_node_filter)[Parent::v(i)]))
936 936
        Parent::nextInc(i, d);
937 937
    }
938 938

	
939 939
    void next(Node& i) const {
940 940
      Parent::next(i);
941 941
      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
942 942
    }
943 943

	
944 944
    void next(Arc& i) const {
945 945
      Parent::next(i);
946 946
      while (i!=INVALID && (!(*_edge_filter)[i]
947 947
                            || !(*_node_filter)[Parent::source(i)]
948 948
                            || !(*_node_filter)[Parent::target(i)]))
949 949
        Parent::next(i);
950 950
    }
951 951

	
952 952
    void next(Edge& i) const {
953 953
      Parent::next(i);
954 954
      while (i!=INVALID && (!(*_edge_filter)[i]
955 955
                            || !(*_node_filter)[Parent::u(i)]
956 956
                            || !(*_node_filter)[Parent::v(i)]))
957 957
        Parent::next(i);
958 958
    }
959 959

	
960 960
    void nextIn(Arc& i) const {
961 961
      Parent::nextIn(i);
962 962
      while (i!=INVALID && (!(*_edge_filter)[i]
963 963
                            || !(*_node_filter)[Parent::source(i)]))
964 964
        Parent::nextIn(i);
965 965
    }
966 966

	
967 967
    void nextOut(Arc& i) const {
968 968
      Parent::nextOut(i);
969 969
      while (i!=INVALID && (!(*_edge_filter)[i]
970 970
                            || !(*_node_filter)[Parent::target(i)]))
971 971
        Parent::nextOut(i);
972 972
    }
973 973

	
974 974
    void nextInc(Edge& i, bool& d) const {
975 975
      Parent::nextInc(i, d);
976 976
      while (i!=INVALID && (!(*_edge_filter)[i]
977 977
                            || !(*_node_filter)[Parent::u(i)]
978 978
                            || !(*_node_filter)[Parent::v(i)]))
979 979
        Parent::nextInc(i, d);
980 980
    }
981 981

	
982 982
    void status(const Node& n, bool v) const { _node_filter->set(n, v); }
983 983
    void status(const Edge& e, bool v) const { _edge_filter->set(e, v); }
984 984

	
985 985
    bool status(const Node& n) const { return (*_node_filter)[n]; }
986 986
    bool status(const Edge& e) const { return (*_edge_filter)[e]; }
987 987

	
988 988
    typedef False NodeNumTag;
989 989
    typedef False ArcNumTag;
990 990
    typedef False EdgeNumTag;
991 991

	
992 992
    typedef FindArcTagIndicator<Graph> FindArcTag;
993 993
    Arc findArc(const Node& u, const Node& v,
994 994
                const Arc& prev = INVALID) const {
995 995
      if (!(*_node_filter)[u] || !(*_node_filter)[v]) {
996 996
        return INVALID;
997 997
      }
998 998
      Arc arc = Parent::findArc(u, v, prev);
999 999
      while (arc != INVALID && !(*_edge_filter)[arc]) {
1000 1000
        arc = Parent::findArc(u, v, arc);
1001 1001
      }
1002 1002
      return arc;
1003 1003
    }
1004 1004

	
1005 1005
    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1006 1006
    Edge findEdge(const Node& u, const Node& v,
1007 1007
                  const Edge& prev = INVALID) const {
1008 1008
      if (!(*_node_filter)[u] || !(*_node_filter)[v]) {
1009 1009
        return INVALID;
1010 1010
      }
1011 1011
      Edge edge = Parent::findEdge(u, v, prev);
1012 1012
      while (edge != INVALID && !(*_edge_filter)[edge]) {
1013 1013
        edge = Parent::findEdge(u, v, edge);
1014 1014
      }
1015 1015
      return edge;
1016 1016
    }
1017 1017

	
1018 1018
    template <typename V>
1019 1019
    class NodeMap 
1020 1020
      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
1021 1021
          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
1022 1022
      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
1023 1023
        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
1024 1024

	
1025 1025
    public:
1026 1026
      typedef V Value;
1027 1027

	
1028 1028
      NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
1029 1029
        : Parent(adaptor) {}
1030 1030
      NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
1031 1031
        : Parent(adaptor, value) {}
1032 1032

	
1033 1033
    private:
1034 1034
      NodeMap& operator=(const NodeMap& cmap) {
1035 1035
        return operator=<NodeMap>(cmap);
1036 1036
      }
1037 1037

	
1038 1038
      template <typename CMap>
1039 1039
      NodeMap& operator=(const CMap& cmap) {
1040 1040
        Parent::operator=(cmap);
1041 1041
        return *this;
1042 1042
      }
1043 1043
    };
1044 1044

	
1045 1045
    template <typename V>
1046 1046
    class ArcMap 
1047 1047
      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
1048 1048
          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
1049 1049
      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
1050 1050
        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
1051 1051

	
1052 1052
    public:
1053 1053
      typedef V Value;
1054 1054

	
1055 1055
      ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
1056 1056
        : Parent(adaptor) {}
1057 1057
      ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
1058 1058
        : Parent(adaptor, value) {}
1059 1059

	
1060 1060
    private:
1061 1061
      ArcMap& operator=(const ArcMap& cmap) {
1062 1062
        return operator=<ArcMap>(cmap);
1063 1063
      }
1064 1064

	
1065 1065
      template <typename CMap>
1066 1066
      ArcMap& operator=(const CMap& cmap) {
1067 1067
        Parent::operator=(cmap);
1068 1068
        return *this;
1069 1069
      }
1070 1070
    };
1071 1071

	
1072 1072
    template <typename V>
1073 1073
    class EdgeMap 
1074 1074
      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
1075 1075
        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
1076 1076
      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
1077 1077
        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
1078 1078

	
1079 1079
    public:
1080 1080
      typedef V Value;
1081 1081

	
1082 1082
      EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
1083 1083
        : Parent(adaptor) {}
1084 1084

	
1085 1085
      EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
1086 1086
        : Parent(adaptor, value) {}
1087 1087

	
1088 1088
    private:
1089 1089
      EdgeMap& operator=(const EdgeMap& cmap) {
1090 1090
        return operator=<EdgeMap>(cmap);
1091 1091
      }
1092 1092

	
1093 1093
      template <typename CMap>
1094 1094
      EdgeMap& operator=(const CMap& cmap) {
1095 1095
        Parent::operator=(cmap);
1096 1096
        return *this;
1097 1097
      }
1098 1098
    };
1099 1099

	
1100 1100
  };
1101 1101

	
1102 1102
  template <typename GR, typename NF, typename EF>
1103 1103
  class SubGraphBase<GR, NF, EF, false>
1104 1104
    : public GraphAdaptorBase<GR> {
1105 1105
    typedef GraphAdaptorBase<GR> Parent;
1106 1106
  public:
1107 1107
    typedef GR Graph;
1108 1108
    typedef NF NodeFilterMap;
1109 1109
    typedef EF EdgeFilterMap;
1110 1110

	
1111 1111
    typedef SubGraphBase Adaptor;
1112 1112
  protected:
1113 1113
    NF* _node_filter;
1114 1114
    EF* _edge_filter;
1115 1115
    SubGraphBase() 
1116 1116
	  : Parent(), _node_filter(0), _edge_filter(0) { }
1117 1117

	
1118 1118
    void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
1119 1119
      Parent::initialize(graph);
1120 1120
      _node_filter = &node_filter;
1121 1121
      _edge_filter = &edge_filter;
1122 1122
    }
1123 1123

	
1124 1124
  public:
1125 1125

	
1126 1126
    typedef typename Parent::Node Node;
1127 1127
    typedef typename Parent::Arc Arc;
1128 1128
    typedef typename Parent::Edge Edge;
1129 1129

	
1130 1130
    void first(Node& i) const {
1131 1131
      Parent::first(i);
1132 1132
      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
1133 1133
    }
1134 1134

	
1135 1135
    void first(Arc& i) const {
1136 1136
      Parent::first(i);
1137 1137
      while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
1138 1138
    }
1139 1139

	
1140 1140
    void first(Edge& i) const {
1141 1141
      Parent::first(i);
1142 1142
      while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
1143 1143
    }
1144 1144

	
1145 1145
    void firstIn(Arc& i, const Node& n) const {
1146 1146
      Parent::firstIn(i, n);
1147 1147
      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i);
1148 1148
    }
1149 1149

	
1150 1150
    void firstOut(Arc& i, const Node& n) const {
1151 1151
      Parent::firstOut(i, n);
1152 1152
      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i);
1153 1153
    }
1154 1154

	
1155 1155
    void firstInc(Edge& i, bool& d, const Node& n) const {
1156 1156
      Parent::firstInc(i, d, n);
1157 1157
      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d);
1158 1158
    }
1159 1159

	
1160 1160
    void next(Node& i) const {
1161 1161
      Parent::next(i);
1162 1162
      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
1163 1163
    }
1164 1164
    void next(Arc& i) const {
1165 1165
      Parent::next(i);
1166 1166
      while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
1167 1167
    }
1168 1168
    void next(Edge& i) const {
1169 1169
      Parent::next(i);
1170 1170
      while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
1171 1171
    }
1172 1172
    void nextIn(Arc& i) const {
1173 1173
      Parent::nextIn(i);
1174 1174
      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i);
1175 1175
    }
1176 1176

	
1177 1177
    void nextOut(Arc& i) const {
1178 1178
      Parent::nextOut(i);
1179 1179
      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i);
1180 1180
    }
1181 1181
    void nextInc(Edge& i, bool& d) const {
1182 1182
      Parent::nextInc(i, d);
1183 1183
      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d);
1184 1184
    }
1185 1185

	
1186 1186
    void status(const Node& n, bool v) const { _node_filter->set(n, v); }
1187 1187
    void status(const Edge& e, bool v) const { _edge_filter->set(e, v); }
1188 1188

	
1189 1189
    bool status(const Node& n) const { return (*_node_filter)[n]; }
1190 1190
    bool status(const Edge& e) const { return (*_edge_filter)[e]; }
1191 1191

	
1192 1192
    typedef False NodeNumTag;
1193 1193
    typedef False ArcNumTag;
1194 1194
    typedef False EdgeNumTag;
1195 1195

	
1196 1196
    typedef FindArcTagIndicator<Graph> FindArcTag;
1197 1197
    Arc findArc(const Node& u, const Node& v,
1198 1198
                const Arc& prev = INVALID) const {
1199 1199
      Arc arc = Parent::findArc(u, v, prev);
1200 1200
      while (arc != INVALID && !(*_edge_filter)[arc]) {
1201 1201
        arc = Parent::findArc(u, v, arc);
1202 1202
      }
1203 1203
      return arc;
1204 1204
    }
1205 1205

	
1206 1206
    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1207 1207
    Edge findEdge(const Node& u, const Node& v,
1208 1208
                  const Edge& prev = INVALID) const {
1209 1209
      Edge edge = Parent::findEdge(u, v, prev);
1210 1210
      while (edge != INVALID && !(*_edge_filter)[edge]) {
1211 1211
        edge = Parent::findEdge(u, v, edge);
1212 1212
      }
1213 1213
      return edge;
1214 1214
    }
1215 1215

	
1216 1216
    template <typename V>
1217 1217
    class NodeMap 
1218 1218
      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
1219 1219
          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
1220 1220
      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
1221 1221
        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
1222 1222

	
1223 1223
    public:
1224 1224
      typedef V Value;
1225 1225

	
1226 1226
      NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
1227 1227
        : Parent(adaptor) {}
1228 1228
      NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
1229 1229
        : Parent(adaptor, value) {}
1230 1230

	
1231 1231
    private:
1232 1232
      NodeMap& operator=(const NodeMap& cmap) {
1233 1233
        return operator=<NodeMap>(cmap);
1234 1234
      }
1235 1235

	
1236 1236
      template <typename CMap>
1237 1237
      NodeMap& operator=(const CMap& cmap) {
1238 1238
        Parent::operator=(cmap);
1239 1239
        return *this;
1240 1240
      }
1241 1241
    };
1242 1242

	
1243 1243
    template <typename V>
1244 1244
    class ArcMap 
1245 1245
      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
1246 1246
          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
1247 1247
      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
1248 1248
        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
1249 1249

	
1250 1250
    public:
1251 1251
      typedef V Value;
1252 1252

	
1253 1253
      ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
1254 1254
        : Parent(adaptor) {}
1255 1255
      ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
1256 1256
        : Parent(adaptor, value) {}
1257 1257

	
1258 1258
    private:
1259 1259
      ArcMap& operator=(const ArcMap& cmap) {
1260 1260
        return operator=<ArcMap>(cmap);
1261 1261
      }
1262 1262

	
1263 1263
      template <typename CMap>
1264 1264
      ArcMap& operator=(const CMap& cmap) {
1265 1265
        Parent::operator=(cmap);
1266 1266
        return *this;
1267 1267
      }
1268 1268
    };
1269 1269

	
1270 1270
    template <typename V>
1271 1271
    class EdgeMap 
1272 1272
      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
1273 1273
        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
1274 1274
      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
1275 1275
	LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
1276 1276

	
1277 1277
    public:
1278 1278
      typedef V Value;
1279 1279

	
1280 1280
      EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
1281 1281
        : Parent(adaptor) {}
1282 1282

	
1283 1283
      EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
1284 1284
        : Parent(adaptor, value) {}
1285 1285

	
1286 1286
    private:
1287 1287
      EdgeMap& operator=(const EdgeMap& cmap) {
1288 1288
        return operator=<EdgeMap>(cmap);
1289 1289
      }
1290 1290

	
1291 1291
      template <typename CMap>
1292 1292
      EdgeMap& operator=(const CMap& cmap) {
1293 1293
        Parent::operator=(cmap);
1294 1294
        return *this;
1295 1295
      }
1296 1296
    };
1297 1297

	
1298 1298
  };
1299 1299

	
1300 1300
  /// \ingroup graph_adaptors
1301 1301
  ///
1302 1302
  /// \brief Adaptor class for hiding nodes and edges in an undirected
1303 1303
  /// graph.
1304 1304
  ///
1305 1305
  /// SubGraph can be used for hiding nodes and edges in a graph.
1306 1306
  /// A \c bool node map and a \c bool edge map must be specified, which
1307 1307
  /// define the filters for nodes and edges.
1308 1308
  /// Only the nodes and edges with \c true filter value are
1309 1309
  /// shown in the subgraph. The edges that are incident to hidden
1310 1310
  /// nodes are also filtered out.
1311 1311
  /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
1312 1312
  ///
1313 1313
  /// The adapted graph can also be modified through this adaptor
1314 1314
  /// by adding or removing nodes or edges, unless the \c GR template
1315 1315
  /// parameter is set to be \c const.
1316 1316
  ///
1317 1317
  /// \tparam GR The type of the adapted graph.
1318 1318
  /// It must conform to the \ref concepts::Graph "Graph" concept.
1319 1319
  /// It can also be specified to be \c const.
1320 1320
  /// \tparam NF The type of the node filter map.
1321 1321
  /// It must be a \c bool (or convertible) node map of the
1322 1322
  /// adapted graph. The default type is
1323 1323
  /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".
1324 1324
  /// \tparam EF The type of the edge filter map.
1325 1325
  /// It must be a \c bool (or convertible) edge map of the
1326 1326
  /// adapted graph. The default type is
1327 1327
  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
1328 1328
  ///
1329 1329
  /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the
1330 1330
  /// adapted graph are convertible to each other.
1331 1331
  ///
1332 1332
  /// \see FilterNodes
1333 1333
  /// \see FilterEdges
1334 1334
#ifdef DOXYGEN
1335 1335
  template<typename GR, typename NF, typename EF>
1336 1336
  class SubGraph {
1337 1337
#else
1338 1338
  template<typename GR,
1339 1339
           typename NF = typename GR::template NodeMap<bool>,
1340 1340
           typename EF = typename GR::template EdgeMap<bool> >
1341 1341
  class SubGraph :
1342 1342
    public GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> > {
1343 1343
#endif
1344 1344
  public:
1345 1345
    /// The type of the adapted graph.
1346 1346
    typedef GR Graph;
1347 1347
    /// The type of the node filter map.
1348 1348
    typedef NF NodeFilterMap;
1349 1349
    /// The type of the edge filter map.
1350 1350
    typedef EF EdgeFilterMap;
1351 1351

	
1352 1352
    typedef GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> >
1353 1353
      Parent;
1354 1354

	
1355 1355
    typedef typename Parent::Node Node;
1356 1356
    typedef typename Parent::Edge Edge;
1357 1357

	
1358 1358
  protected:
1359 1359
    SubGraph() { }
1360 1360
  public:
1361 1361

	
1362 1362
    /// \brief Constructor
1363 1363
    ///
1364 1364
    /// Creates a subgraph for the given graph with the given node
1365 1365
    /// and edge filter maps.
1366 1366
    SubGraph(GR& graph, NF& node_filter, EF& edge_filter) {
1367 1367
      initialize(graph, node_filter, edge_filter);
1368 1368
    }
1369 1369

	
1370 1370
    /// \brief Sets the status of the given node
1371 1371
    ///
1372 1372
    /// This function sets the status of the given node.
1373 1373
    /// It is done by simply setting the assigned value of \c n
1374 1374
    /// to \c v in the node filter map.
1375 1375
    void status(const Node& n, bool v) const { Parent::status(n, v); }
1376 1376

	
1377 1377
    /// \brief Sets the status of the given edge
1378 1378
    ///
1379 1379
    /// This function sets the status of the given edge.
1380 1380
    /// It is done by simply setting the assigned value of \c e
1381 1381
    /// to \c v in the edge filter map.
1382 1382
    void status(const Edge& e, bool v) const { Parent::status(e, v); }
1383 1383

	
1384 1384
    /// \brief Returns the status of the given node
1385 1385
    ///
1386 1386
    /// This function returns the status of the given node.
1387 1387
    /// It is \c true if the given node is enabled (i.e. not hidden).
1388 1388
    bool status(const Node& n) const { return Parent::status(n); }
1389 1389

	
1390 1390
    /// \brief Returns the status of the given edge
1391 1391
    ///
1392 1392
    /// This function returns the status of the given edge.
1393 1393
    /// It is \c true if the given edge is enabled (i.e. not hidden).
1394 1394
    bool status(const Edge& e) const { return Parent::status(e); }
1395 1395

	
1396 1396
    /// \brief Disables the given node
1397 1397
    ///
1398 1398
    /// This function disables the given node in the subdigraph,
1399 1399
    /// so the iteration jumps over it.
1400 1400
    /// It is the same as \ref status() "status(n, false)".
1401 1401
    void disable(const Node& n) const { Parent::status(n, false); }
1402 1402

	
1403 1403
    /// \brief Disables the given edge
1404 1404
    ///
1405 1405
    /// This function disables the given edge in the subgraph,
1406 1406
    /// so the iteration jumps over it.
1407 1407
    /// It is the same as \ref status() "status(e, false)".
1408 1408
    void disable(const Edge& e) const { Parent::status(e, false); }
1409 1409

	
1410 1410
    /// \brief Enables the given node
1411 1411
    ///
1412 1412
    /// This function enables the given node in the subdigraph.
1413 1413
    /// It is the same as \ref status() "status(n, true)".
1414 1414
    void enable(const Node& n) const { Parent::status(n, true); }
1415 1415

	
1416 1416
    /// \brief Enables the given edge
1417 1417
    ///
1418 1418
    /// This function enables the given edge in the subgraph.
1419 1419
    /// It is the same as \ref status() "status(e, true)".
1420 1420
    void enable(const Edge& e) const { Parent::status(e, true); }
1421 1421

	
1422 1422
  };
1423 1423

	
1424 1424
  /// \brief Returns a read-only SubGraph adaptor
1425 1425
  ///
1426 1426
  /// This function just returns a read-only \ref SubGraph adaptor.
1427 1427
  /// \ingroup graph_adaptors
1428 1428
  /// \relates SubGraph
1429 1429
  template<typename GR, typename NF, typename EF>
1430 1430
  SubGraph<const GR, NF, EF>
1431 1431
  subGraph(const GR& graph, NF& node_filter, EF& edge_filter) {
1432 1432
    return SubGraph<const GR, NF, EF>
1433 1433
      (graph, node_filter, edge_filter);
1434 1434
  }
1435 1435

	
1436 1436
  template<typename GR, typename NF, typename EF>
1437 1437
  SubGraph<const GR, const NF, EF>
1438 1438
  subGraph(const GR& graph, const NF& node_filter, EF& edge_filter) {
1439 1439
    return SubGraph<const GR, const NF, EF>
1440 1440
      (graph, node_filter, edge_filter);
1441 1441
  }
1442 1442

	
1443 1443
  template<typename GR, typename NF, typename EF>
1444 1444
  SubGraph<const GR, NF, const EF>
1445 1445
  subGraph(const GR& graph, NF& node_filter, const EF& edge_filter) {
1446 1446
    return SubGraph<const GR, NF, const EF>
1447 1447
      (graph, node_filter, edge_filter);
1448 1448
  }
1449 1449

	
1450 1450
  template<typename GR, typename NF, typename EF>
1451 1451
  SubGraph<const GR, const NF, const EF>
1452 1452
  subGraph(const GR& graph, const NF& node_filter, const EF& edge_filter) {
1453 1453
    return SubGraph<const GR, const NF, const EF>
1454 1454
      (graph, node_filter, edge_filter);
1455 1455
  }
1456 1456

	
1457 1457

	
1458 1458
  /// \ingroup graph_adaptors
1459 1459
  ///
1460 1460
  /// \brief Adaptor class for hiding nodes in a digraph or a graph.
1461 1461
  ///
1462 1462
  /// FilterNodes adaptor can be used for hiding nodes in a digraph or a
1463 1463
  /// graph. A \c bool node map must be specified, which defines the filter
1464 1464
  /// for the nodes. Only the nodes with \c true filter value and the
1465 1465
  /// arcs/edges incident to nodes both with \c true filter value are shown
1466 1466
  /// in the subgraph. This adaptor conforms to the \ref concepts::Digraph
1467 1467
  /// "Digraph" concept or the \ref concepts::Graph "Graph" concept
1468 1468
  /// depending on the \c GR template parameter.
1469 1469
  ///
1470 1470
  /// The adapted (di)graph can also be modified through this adaptor
1471 1471
  /// by adding or removing nodes or arcs/edges, unless the \c GR template
1472 1472
  /// parameter is set to be \c const.
1473 1473
  ///
1474 1474
  /// \tparam GR The type of the adapted digraph or graph.
1475 1475
  /// It must conform to the \ref concepts::Digraph "Digraph" concept
1476 1476
  /// or the \ref concepts::Graph "Graph" concept.
1477 1477
  /// It can also be specified to be \c const.
1478 1478
  /// \tparam NF The type of the node filter map.
1479 1479
  /// It must be a \c bool (or convertible) node map of the
1480 1480
  /// adapted (di)graph. The default type is
1481 1481
  /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".
1482 1482
  ///
1483 1483
  /// \note The \c Node and <tt>Arc/Edge</tt> types of this adaptor and the
1484 1484
  /// adapted (di)graph are convertible to each other.
1485 1485
#ifdef DOXYGEN
1486 1486
  template<typename GR, typename NF>
1487 1487
  class FilterNodes {
1488 1488
#else
1489 1489
  template<typename GR,
1490 1490
           typename NF = typename GR::template NodeMap<bool>,
1491 1491
           typename Enable = void>
1492 1492
  class FilterNodes :
1493 1493
    public DigraphAdaptorExtender<
1494 1494
      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
1495 1495
                     true> > {
1496 1496
#endif
1497 1497
    typedef DigraphAdaptorExtender<
1498 1498
      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >, 
1499 1499
                     true> > Parent;
1500 1500

	
1501 1501
  public:
1502 1502

	
1503 1503
    typedef GR Digraph;
1504 1504
    typedef NF NodeFilterMap;
1505 1505

	
1506 1506
    typedef typename Parent::Node Node;
1507 1507

	
1508 1508
  protected:
1509 1509
    ConstMap<typename Digraph::Arc, Const<bool, true> > const_true_map;
1510 1510

	
1511 1511
    FilterNodes() : const_true_map() {}
1512 1512

	
1513 1513
  public:
1514 1514

	
1515 1515
    /// \brief Constructor
1516 1516
    ///
1517 1517
    /// Creates a subgraph for the given digraph or graph with the
1518 1518
    /// given node filter map.
1519 1519
    FilterNodes(GR& graph, NF& node_filter) 
1520 1520
      : Parent(), const_true_map()
1521 1521
    {
1522 1522
      Parent::initialize(graph, node_filter, const_true_map);
1523 1523
    }
1524 1524

	
1525 1525
    /// \brief Sets the status of the given node
1526 1526
    ///
1527 1527
    /// This function sets the status of the given node.
1528 1528
    /// It is done by simply setting the assigned value of \c n
1529 1529
    /// to \c v in the node filter map.
1530 1530
    void status(const Node& n, bool v) const { Parent::status(n, v); }
1531 1531

	
1532 1532
    /// \brief Returns the status of the given node
1533 1533
    ///
1534 1534
    /// This function returns the status of the given node.
1535 1535
    /// It is \c true if the given node is enabled (i.e. not hidden).
1536 1536
    bool status(const Node& n) const { return Parent::status(n); }
1537 1537

	
1538 1538
    /// \brief Disables the given node
1539 1539
    ///
1540 1540
    /// This function disables the given node, so the iteration
1541 1541
    /// jumps over it.
1542 1542
    /// It is the same as \ref status() "status(n, false)".
1543 1543
    void disable(const Node& n) const { Parent::status(n, false); }
1544 1544

	
1545 1545
    /// \brief Enables the given node
1546 1546
    ///
1547 1547
    /// This function enables the given node.
1548 1548
    /// It is the same as \ref status() "status(n, true)".
1549 1549
    void enable(const Node& n) const { Parent::status(n, true); }
1550 1550

	
1551 1551
  };
1552 1552

	
1553 1553
  template<typename GR, typename NF>
1554 1554
  class FilterNodes<GR, NF,
1555 1555
                    typename enable_if<UndirectedTagIndicator<GR> >::type> :
1556 1556
    public GraphAdaptorExtender<
1557 1557
      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
1558 1558
                   true> > {
1559 1559

	
1560 1560
    typedef GraphAdaptorExtender<
1561 1561
      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
1562 1562
                   true> > Parent;
1563 1563

	
1564 1564
  public:
1565 1565

	
1566 1566
    typedef GR Graph;
1567 1567
    typedef NF NodeFilterMap;
1568 1568

	
1569 1569
    typedef typename Parent::Node Node;
1570 1570

	
1571 1571
  protected:
1572 1572
    ConstMap<typename GR::Edge, Const<bool, true> > const_true_map;
1573 1573

	
1574 1574
    FilterNodes() : const_true_map() {}
1575 1575

	
1576 1576
  public:
1577 1577

	
1578 1578
    FilterNodes(GR& graph, NodeFilterMap& node_filter) :
1579 1579
      Parent(), const_true_map() {
1580 1580
      Parent::initialize(graph, node_filter, const_true_map);
1581 1581
    }
1582 1582

	
1583 1583
    void status(const Node& n, bool v) const { Parent::status(n, v); }
1584 1584
    bool status(const Node& n) const { return Parent::status(n); }
1585 1585
    void disable(const Node& n) const { Parent::status(n, false); }
1586 1586
    void enable(const Node& n) const { Parent::status(n, true); }
1587 1587

	
1588 1588
  };
1589 1589

	
1590 1590

	
1591 1591
  /// \brief Returns a read-only FilterNodes adaptor
1592 1592
  ///
1593 1593
  /// This function just returns a read-only \ref FilterNodes adaptor.
1594 1594
  /// \ingroup graph_adaptors
1595 1595
  /// \relates FilterNodes
1596 1596
  template<typename GR, typename NF>
1597 1597
  FilterNodes<const GR, NF>
1598 1598
  filterNodes(const GR& graph, NF& node_filter) {
1599 1599
    return FilterNodes<const GR, NF>(graph, node_filter);
1600 1600
  }
1601 1601

	
1602 1602
  template<typename GR, typename NF>
1603 1603
  FilterNodes<const GR, const NF>
1604 1604
  filterNodes(const GR& graph, const NF& node_filter) {
1605 1605
    return FilterNodes<const GR, const NF>(graph, node_filter);
1606 1606
  }
1607 1607

	
1608 1608
  /// \ingroup graph_adaptors
1609 1609
  ///
1610 1610
  /// \brief Adaptor class for hiding arcs in a digraph.
1611 1611
  ///
1612 1612
  /// FilterArcs adaptor can be used for hiding arcs in a digraph.
1613 1613
  /// A \c bool arc map must be specified, which defines the filter for
1614 1614
  /// the arcs. Only the arcs with \c true filter value are shown in the
1615 1615
  /// subdigraph. This adaptor conforms to the \ref concepts::Digraph
1616 1616
  /// "Digraph" concept.
1617 1617
  ///
1618 1618
  /// The adapted digraph can also be modified through this adaptor
1619 1619
  /// by adding or removing nodes or arcs, unless the \c GR template
1620 1620
  /// parameter is set to be \c const.
1621 1621
  ///
1622 1622
  /// \tparam DGR The type of the adapted digraph.
1623 1623
  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
1624 1624
  /// It can also be specified to be \c const.
1625 1625
  /// \tparam AF The type of the arc filter map.
1626 1626
  /// It must be a \c bool (or convertible) arc map of the
1627 1627
  /// adapted digraph. The default type is
1628 1628
  /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>".
1629 1629
  ///
1630 1630
  /// \note The \c Node and \c Arc types of this adaptor and the adapted
1631 1631
  /// digraph are convertible to each other.
1632 1632
#ifdef DOXYGEN
1633 1633
  template<typename DGR,
1634 1634
           typename AF>
1635 1635
  class FilterArcs {
1636 1636
#else
1637 1637
  template<typename DGR,
1638 1638
           typename AF = typename DGR::template ArcMap<bool> >
1639 1639
  class FilterArcs :
1640 1640
    public DigraphAdaptorExtender<
1641 1641
      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
1642 1642
                     AF, false> > {
1643 1643
#endif
1644 1644
    typedef DigraphAdaptorExtender<
1645 1645
      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >, 
1646 1646
                     AF, false> > Parent;
1647 1647

	
1648 1648
  public:
1649 1649

	
1650 1650
    /// The type of the adapted digraph.
1651 1651
    typedef DGR Digraph;
1652 1652
    /// The type of the arc filter map.
1653 1653
    typedef AF ArcFilterMap;
1654 1654

	
1655 1655
    typedef typename Parent::Arc Arc;
1656 1656

	
1657 1657
  protected:
1658 1658
    ConstMap<typename DGR::Node, Const<bool, true> > const_true_map;
1659 1659

	
1660 1660
    FilterArcs() : const_true_map() {}
1661 1661

	
1662 1662
  public:
1663 1663

	
1664 1664
    /// \brief Constructor
1665 1665
    ///
1666 1666
    /// Creates a subdigraph for the given digraph with the given arc
1667 1667
    /// filter map.
1668 1668
    FilterArcs(DGR& digraph, ArcFilterMap& arc_filter)
1669 1669
      : Parent(), const_true_map() {
1670 1670
      Parent::initialize(digraph, const_true_map, arc_filter);
1671 1671
    }
1672 1672

	
1673 1673
    /// \brief Sets the status of the given arc
1674 1674
    ///
1675 1675
    /// This function sets the status of the given arc.
1676 1676
    /// It is done by simply setting the assigned value of \c a
1677 1677
    /// to \c v in the arc filter map.
1678 1678
    void status(const Arc& a, bool v) const { Parent::status(a, v); }
1679 1679

	
1680 1680
    /// \brief Returns the status of the given arc
1681 1681
    ///
1682 1682
    /// This function returns the status of the given arc.
1683 1683
    /// It is \c true if the given arc is enabled (i.e. not hidden).
1684 1684
    bool status(const Arc& a) const { return Parent::status(a); }
1685 1685

	
1686 1686
    /// \brief Disables the given arc
1687 1687
    ///
1688 1688
    /// This function disables the given arc in the subdigraph,
1689 1689
    /// so the iteration jumps over it.
1690 1690
    /// It is the same as \ref status() "status(a, false)".
1691 1691
    void disable(const Arc& a) const { Parent::status(a, false); }
1692 1692

	
1693 1693
    /// \brief Enables the given arc
1694 1694
    ///
1695 1695
    /// This function enables the given arc in the subdigraph.
1696 1696
    /// It is the same as \ref status() "status(a, true)".
1697 1697
    void enable(const Arc& a) const { Parent::status(a, true); }
1698 1698

	
1699 1699
  };
1700 1700

	
1701 1701
  /// \brief Returns a read-only FilterArcs adaptor
1702 1702
  ///
1703 1703
  /// This function just returns a read-only \ref FilterArcs adaptor.
1704 1704
  /// \ingroup graph_adaptors
1705 1705
  /// \relates FilterArcs
1706 1706
  template<typename DGR, typename AF>
1707 1707
  FilterArcs<const DGR, AF>
1708 1708
  filterArcs(const DGR& digraph, AF& arc_filter) {
1709 1709
    return FilterArcs<const DGR, AF>(digraph, arc_filter);
1710 1710
  }
1711 1711

	
1712 1712
  template<typename DGR, typename AF>
1713 1713
  FilterArcs<const DGR, const AF>
1714 1714
  filterArcs(const DGR& digraph, const AF& arc_filter) {
1715 1715
    return FilterArcs<const DGR, const AF>(digraph, arc_filter);
1716 1716
  }
1717 1717

	
1718 1718
  /// \ingroup graph_adaptors
1719 1719
  ///
1720 1720
  /// \brief Adaptor class for hiding edges in a graph.
1721 1721
  ///
1722 1722
  /// FilterEdges adaptor can be used for hiding edges in a graph.
1723 1723
  /// A \c bool edge map must be specified, which defines the filter for
1724 1724
  /// the edges. Only the edges with \c true filter value are shown in the
1725 1725
  /// subgraph. This adaptor conforms to the \ref concepts::Graph
1726 1726
  /// "Graph" concept.
1727 1727
  ///
1728 1728
  /// The adapted graph can also be modified through this adaptor
1729 1729
  /// by adding or removing nodes or edges, unless the \c GR template
1730 1730
  /// parameter is set to be \c const.
1731 1731
  ///
1732 1732
  /// \tparam GR The type of the adapted graph.
1733 1733
  /// It must conform to the \ref concepts::Graph "Graph" concept.
1734 1734
  /// It can also be specified to be \c const.
1735 1735
  /// \tparam EF The type of the edge filter map.
1736 1736
  /// It must be a \c bool (or convertible) edge map of the
1737 1737
  /// adapted graph. The default type is
1738 1738
  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
1739 1739
  ///
1740 1740
  /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the
1741 1741
  /// adapted graph are convertible to each other.
1742 1742
#ifdef DOXYGEN
1743 1743
  template<typename GR,
1744 1744
           typename EF>
1745 1745
  class FilterEdges {
1746 1746
#else
1747 1747
  template<typename GR,
1748 1748
           typename EF = typename GR::template EdgeMap<bool> >
1749 1749
  class FilterEdges :
1750 1750
    public GraphAdaptorExtender<
1751 1751
      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >, 
1752 1752
                   EF, false> > {
1753 1753
#endif
1754 1754
    typedef GraphAdaptorExtender<
1755 1755
      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >, 
1756 1756
                   EF, false> > Parent;
1757 1757

	
1758 1758
  public:
1759 1759

	
1760 1760
    /// The type of the adapted graph.
1761 1761
    typedef GR Graph;
1762 1762
    /// The type of the edge filter map.
1763 1763
    typedef EF EdgeFilterMap;
1764 1764

	
1765 1765
    typedef typename Parent::Edge Edge;
1766 1766

	
1767 1767
  protected:
1768 1768
    ConstMap<typename GR::Node, Const<bool, true> > const_true_map;
1769 1769

	
1770 1770
    FilterEdges() : const_true_map(true) {
1771 1771
      Parent::setNodeFilterMap(const_true_map);
1772 1772
    }
1773 1773

	
1774 1774
  public:
1775 1775

	
1776 1776
    /// \brief Constructor
1777 1777
    ///
1778 1778
    /// Creates a subgraph for the given graph with the given edge
1779 1779
    /// filter map.
1780 1780
    FilterEdges(GR& graph, EF& edge_filter) 
1781 1781
      : Parent(), const_true_map() {
1782 1782
      Parent::initialize(graph, const_true_map, edge_filter);
1783 1783
    }
1784 1784

	
1785 1785
    /// \brief Sets the status of the given edge
1786 1786
    ///
1787 1787
    /// This function sets the status of the given edge.
1788 1788
    /// It is done by simply setting the assigned value of \c e
1789 1789
    /// to \c v in the edge filter map.
1790 1790
    void status(const Edge& e, bool v) const { Parent::status(e, v); }
1791 1791

	
1792 1792
    /// \brief Returns the status of the given edge
1793 1793
    ///
1794 1794
    /// This function returns the status of the given edge.
1795 1795
    /// It is \c true if the given edge is enabled (i.e. not hidden).
1796 1796
    bool status(const Edge& e) const { return Parent::status(e); }
1797 1797

	
1798 1798
    /// \brief Disables the given edge
1799 1799
    ///
1800 1800
    /// This function disables the given edge in the subgraph,
1801 1801
    /// so the iteration jumps over it.
1802 1802
    /// It is the same as \ref status() "status(e, false)".
1803 1803
    void disable(const Edge& e) const { Parent::status(e, false); }
1804 1804

	
1805 1805
    /// \brief Enables the given edge
1806 1806
    ///
1807 1807
    /// This function enables the given edge in the subgraph.
1808 1808
    /// It is the same as \ref status() "status(e, true)".
1809 1809
    void enable(const Edge& e) const { Parent::status(e, true); }
1810 1810

	
1811 1811
  };
1812 1812

	
1813 1813
  /// \brief Returns a read-only FilterEdges adaptor
1814 1814
  ///
1815 1815
  /// This function just returns a read-only \ref FilterEdges adaptor.
1816 1816
  /// \ingroup graph_adaptors
1817 1817
  /// \relates FilterEdges
1818 1818
  template<typename GR, typename EF>
1819 1819
  FilterEdges<const GR, EF>
1820 1820
  filterEdges(const GR& graph, EF& edge_filter) {
1821 1821
    return FilterEdges<const GR, EF>(graph, edge_filter);
1822 1822
  }
1823 1823

	
1824 1824
  template<typename GR, typename EF>
1825 1825
  FilterEdges<const GR, const EF>
1826 1826
  filterEdges(const GR& graph, const EF& edge_filter) {
1827 1827
    return FilterEdges<const GR, const EF>(graph, edge_filter);
1828 1828
  }
1829 1829

	
1830 1830

	
1831 1831
  template <typename DGR>
1832 1832
  class UndirectorBase {
1833 1833
  public:
1834 1834
    typedef DGR Digraph;
1835 1835
    typedef UndirectorBase Adaptor;
1836 1836

	
1837 1837
    typedef True UndirectedTag;
1838 1838

	
1839 1839
    typedef typename Digraph::Arc Edge;
1840 1840
    typedef typename Digraph::Node Node;
1841 1841

	
1842
    class Arc : public Edge {
1842
    class Arc {
1843 1843
      friend class UndirectorBase;
1844 1844
    protected:
1845
      Edge _edge;
1845 1846
      bool _forward;
1846 1847

	
1847
      Arc(const Edge& edge, bool forward) :
1848
        Edge(edge), _forward(forward) {}
1848
      Arc(const Edge& edge, bool forward) 
1849
        : _edge(edge), _forward(forward) {}
1849 1850

	
1850 1851
    public:
1851 1852
      Arc() {}
1852 1853

	
1853
      Arc(Invalid) : Edge(INVALID), _forward(true) {}
1854
      Arc(Invalid) : _edge(INVALID), _forward(true) {}
1855

	
1856
      operator const Edge&() const { return _edge; }
1854 1857

	
1855 1858
      bool operator==(const Arc &other) const {
1856
        return _forward == other._forward &&
1857
          static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
1859
        return _forward == other._forward && _edge == other._edge;
1858 1860
      }
1859 1861
      bool operator!=(const Arc &other) const {
1860
        return _forward != other._forward ||
1861
          static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
1862
        return _forward != other._forward || _edge != other._edge;
1862 1863
      }
1863 1864
      bool operator<(const Arc &other) const {
1864 1865
        return _forward < other._forward ||
1865
          (_forward == other._forward &&
1866
           static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
1866
          (_forward == other._forward && _edge < other._edge);
1867 1867
      }
1868 1868
    };
1869 1869

	
1870 1870
    void first(Node& n) const {
1871 1871
      _digraph->first(n);
1872 1872
    }
1873 1873

	
1874 1874
    void next(Node& n) const {
1875 1875
      _digraph->next(n);
1876 1876
    }
1877 1877

	
1878 1878
    void first(Arc& a) const {
1879
      _digraph->first(a);
1879
      _digraph->first(a._edge);
1880 1880
      a._forward = true;
1881 1881
    }
1882 1882

	
1883 1883
    void next(Arc& a) const {
1884 1884
      if (a._forward) {
1885 1885
        a._forward = false;
1886 1886
      } else {
1887
        _digraph->next(a);
1887
        _digraph->next(a._edge);
1888 1888
        a._forward = true;
1889 1889
      }
1890 1890
    }
1891 1891

	
1892 1892
    void first(Edge& e) const {
1893 1893
      _digraph->first(e);
1894 1894
    }
1895 1895

	
1896 1896
    void next(Edge& e) const {
1897 1897
      _digraph->next(e);
1898 1898
    }
1899 1899

	
1900 1900
    void firstOut(Arc& a, const Node& n) const {
1901
      _digraph->firstIn(a, n);
1902
      if( static_cast<const Edge&>(a) != INVALID ) {
1901
      _digraph->firstIn(a._edge, n);
1902
      if (a._edge != INVALID ) {
1903 1903
        a._forward = false;
1904 1904
      } else {
1905
        _digraph->firstOut(a, n);
1905
        _digraph->firstOut(a._edge, n);
1906 1906
        a._forward = true;
1907 1907
      }
1908 1908
    }
1909 1909
    void nextOut(Arc &a) const {
1910 1910
      if (!a._forward) {
1911
        Node n = _digraph->target(a);
1912
        _digraph->nextIn(a);
1913
        if (static_cast<const Edge&>(a) == INVALID ) {
1914
          _digraph->firstOut(a, n);
1911
        Node n = _digraph->target(a._edge);
1912
        _digraph->nextIn(a._edge);
1913
        if (a._edge == INVALID) {
1914
          _digraph->firstOut(a._edge, n);
1915 1915
          a._forward = true;
1916 1916
        }
1917 1917
      }
1918 1918
      else {
1919
        _digraph->nextOut(a);
1919
        _digraph->nextOut(a._edge);
1920 1920
      }
1921 1921
    }
1922 1922

	
1923 1923
    void firstIn(Arc &a, const Node &n) const {
1924
      _digraph->firstOut(a, n);
1925
      if (static_cast<const Edge&>(a) != INVALID ) {
1924
      _digraph->firstOut(a._edge, n);
1925
      if (a._edge != INVALID ) {
1926 1926
        a._forward = false;
1927 1927
      } else {
1928
        _digraph->firstIn(a, n);
1928
        _digraph->firstIn(a._edge, n);
1929 1929
        a._forward = true;
1930 1930
      }
1931 1931
    }
1932 1932
    void nextIn(Arc &a) const {
1933 1933
      if (!a._forward) {
1934
        Node n = _digraph->source(a);
1935
        _digraph->nextOut(a);
1936
        if( static_cast<const Edge&>(a) == INVALID ) {
1937
          _digraph->firstIn(a, n);
1934
        Node n = _digraph->source(a._edge);
1935
        _digraph->nextOut(a._edge);
1936
        if (a._edge == INVALID ) {
1937
          _digraph->firstIn(a._edge, n);
1938 1938
          a._forward = true;
1939 1939
        }
1940 1940
      }
1941 1941
      else {
1942
        _digraph->nextIn(a);
1942
        _digraph->nextIn(a._edge);
1943 1943
      }
1944 1944
    }
1945 1945

	
1946 1946
    void firstInc(Edge &e, bool &d, const Node &n) const {
1947 1947
      d = true;
1948 1948
      _digraph->firstOut(e, n);
1949 1949
      if (e != INVALID) return;
1950 1950
      d = false;
1951 1951
      _digraph->firstIn(e, n);
1952 1952
    }
1953 1953

	
1954 1954
    void nextInc(Edge &e, bool &d) const {
1955 1955
      if (d) {
1956 1956
        Node s = _digraph->source(e);
1957 1957
        _digraph->nextOut(e);
1958 1958
        if (e != INVALID) return;
1959 1959
        d = false;
1960 1960
        _digraph->firstIn(e, s);
1961 1961
      } else {
1962 1962
        _digraph->nextIn(e);
1963 1963
      }
1964 1964
    }
1965 1965

	
1966 1966
    Node u(const Edge& e) const {
1967 1967
      return _digraph->source(e);
1968 1968
    }
1969 1969

	
1970 1970
    Node v(const Edge& e) const {
1971 1971
      return _digraph->target(e);
1972 1972
    }
1973 1973

	
1974 1974
    Node source(const Arc &a) const {
1975
      return a._forward ? _digraph->source(a) : _digraph->target(a);
1975
      return a._forward ? _digraph->source(a._edge) : _digraph->target(a._edge);
1976 1976
    }
1977 1977

	
1978 1978
    Node target(const Arc &a) const {
1979
      return a._forward ? _digraph->target(a) : _digraph->source(a);
1979
      return a._forward ? _digraph->target(a._edge) : _digraph->source(a._edge);
1980 1980
    }
1981 1981

	
1982 1982
    static Arc direct(const Edge &e, bool d) {
1983 1983
      return Arc(e, d);
1984 1984
    }
1985
    Arc direct(const Edge &e, const Node& n) const {
1986
      return Arc(e, _digraph->source(e) == n);
1987
    }
1988 1985

	
1989 1986
    static bool direction(const Arc &a) { return a._forward; }
1990 1987

	
1991 1988
    Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
1992 1989
    Arc arcFromId(int ix) const {
1993 1990
      return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1));
1994 1991
    }
1995 1992
    Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); }
1996 1993

	
1997 1994
    int id(const Node &n) const { return _digraph->id(n); }
1998 1995
    int id(const Arc &a) const {
1999 1996
      return  (_digraph->id(a) << 1) | (a._forward ? 1 : 0);
2000 1997
    }
2001 1998
    int id(const Edge &e) const { return _digraph->id(e); }
2002 1999

	
2003 2000
    int maxNodeId() const { return _digraph->maxNodeId(); }
2004 2001
    int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; }
2005 2002
    int maxEdgeId() const { return _digraph->maxArcId(); }
2006 2003

	
2007 2004
    Node addNode() { return _digraph->addNode(); }
2008 2005
    Edge addEdge(const Node& u, const Node& v) {
2009 2006
      return _digraph->addArc(u, v);
2010 2007
    }
2011 2008

	
2012 2009
    void erase(const Node& i) { _digraph->erase(i); }
2013 2010
    void erase(const Edge& i) { _digraph->erase(i); }
2014 2011

	
2015 2012
    void clear() { _digraph->clear(); }
2016 2013

	
2017 2014
    typedef NodeNumTagIndicator<Digraph> NodeNumTag;
2018 2015
    int nodeNum() const { return _digraph->nodeNum(); }
2019 2016

	
2020 2017
    typedef ArcNumTagIndicator<Digraph> ArcNumTag;
2021 2018
    int arcNum() const { return 2 * _digraph->arcNum(); }
2022 2019

	
2023 2020
    typedef ArcNumTag EdgeNumTag;
2024 2021
    int edgeNum() const { return _digraph->arcNum(); }
2025 2022

	
2026 2023
    typedef FindArcTagIndicator<Digraph> FindArcTag;
2027 2024
    Arc findArc(Node s, Node t, Arc p = INVALID) const {
2028 2025
      if (p == INVALID) {
2029 2026
        Edge arc = _digraph->findArc(s, t);
2030 2027
        if (arc != INVALID) return direct(arc, true);
2031 2028
        arc = _digraph->findArc(t, s);
2032 2029
        if (arc != INVALID) return direct(arc, false);
2033 2030
      } else if (direction(p)) {
2034 2031
        Edge arc = _digraph->findArc(s, t, p);
2035 2032
        if (arc != INVALID) return direct(arc, true);
2036 2033
        arc = _digraph->findArc(t, s);
2037 2034
        if (arc != INVALID) return direct(arc, false);
2038 2035
      } else {
2039 2036
        Edge arc = _digraph->findArc(t, s, p);
2040 2037
        if (arc != INVALID) return direct(arc, false);
2041 2038
      }
2042 2039
      return INVALID;
2043 2040
    }
2044 2041

	
2045 2042
    typedef FindArcTag FindEdgeTag;
2046 2043
    Edge findEdge(Node s, Node t, Edge p = INVALID) const {
2047 2044
      if (s != t) {
2048 2045
        if (p == INVALID) {
2049 2046
          Edge arc = _digraph->findArc(s, t);
2050 2047
          if (arc != INVALID) return arc;
2051 2048
          arc = _digraph->findArc(t, s);
2052 2049
          if (arc != INVALID) return arc;
2053 2050
        } else if (_digraph->source(p) == s) {
2054 2051
          Edge arc = _digraph->findArc(s, t, p);
2055 2052
          if (arc != INVALID) return arc;
2056 2053
          arc = _digraph->findArc(t, s);
2057 2054
          if (arc != INVALID) return arc;
2058 2055
        } else {
2059 2056
          Edge arc = _digraph->findArc(t, s, p);
2060 2057
          if (arc != INVALID) return arc;
2061 2058
        }
2062 2059
      } else {
2063 2060
        return _digraph->findArc(s, t, p);
2064 2061
      }
2065 2062
      return INVALID;
2066 2063
    }
2067 2064

	
2068 2065
  private:
2069 2066

	
2070 2067
    template <typename V>
2071 2068
    class ArcMapBase {
2072 2069
    private:
2073 2070

	
2074 2071
      typedef typename DGR::template ArcMap<V> MapImpl;
2075 2072

	
2076 2073
    public:
2077 2074

	
2078 2075
      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
2079 2076

	
2080 2077
      typedef V Value;
2081 2078
      typedef Arc Key;
2082 2079
      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue;
2083 2080
      typedef typename MapTraits<MapImpl>::ReturnValue ReturnValue;
2084 2081
      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReference;
2085 2082
      typedef typename MapTraits<MapImpl>::ReturnValue Reference;
2086 2083

	
2087 2084
      ArcMapBase(const UndirectorBase<DGR>& adaptor) :
2088 2085
        _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
2089 2086

	
2090 2087
      ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)
2091 2088
        : _forward(*adaptor._digraph, value), 
2092 2089
          _backward(*adaptor._digraph, value) {}
2093 2090

	
2094 2091
      void set(const Arc& a, const V& value) {
2095 2092
        if (direction(a)) {
2096 2093
          _forward.set(a, value);
2097 2094
        } else {
2098 2095
          _backward.set(a, value);
2099 2096
        }
2100 2097
      }
2101 2098

	
2102 2099
      ConstReturnValue operator[](const Arc& a) const {
2103 2100
        if (direction(a)) {
2104 2101
          return _forward[a];
2105 2102
        } else {
2106 2103
          return _backward[a];
2107 2104
        }
2108 2105
      }
2109 2106

	
2110 2107
      ReturnValue operator[](const Arc& a) {
2111 2108
        if (direction(a)) {
2112 2109
          return _forward[a];
2113 2110
        } else {
2114 2111
          return _backward[a];
2115 2112
        }
2116 2113
      }
2117 2114

	
2118 2115
    protected:
2119 2116

	
2120 2117
      MapImpl _forward, _backward;
2121 2118

	
2122 2119
    };
2123 2120

	
2124 2121
  public:
2125 2122

	
2126 2123
    template <typename V>
2127 2124
    class NodeMap : public DGR::template NodeMap<V> {
2128 2125
      typedef typename DGR::template NodeMap<V> Parent;
2129 2126

	
2130 2127
    public:
2131 2128
      typedef V Value;
2132 2129

	
2133 2130
      explicit NodeMap(const UndirectorBase<DGR>& adaptor)
2134 2131
        : Parent(*adaptor._digraph) {}
2135 2132

	
2136 2133
      NodeMap(const UndirectorBase<DGR>& adaptor, const V& value)
2137 2134
        : Parent(*adaptor._digraph, value) { }
2138 2135

	
2139 2136
    private:
2140 2137
      NodeMap& operator=(const NodeMap& cmap) {
2141 2138
        return operator=<NodeMap>(cmap);
2142 2139
      }
2143 2140

	
2144 2141
      template <typename CMap>
2145 2142
      NodeMap& operator=(const CMap& cmap) {
2146 2143
        Parent::operator=(cmap);
2147 2144
        return *this;
2148 2145
      }
2149 2146

	
2150 2147
    };
2151 2148

	
2152 2149
    template <typename V>
2153 2150
    class ArcMap
2154 2151
      : public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > {
2155 2152
      typedef SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > Parent;
2156 2153

	
2157 2154
    public:
2158 2155
      typedef V Value;
2159 2156

	
2160 2157
      explicit ArcMap(const UndirectorBase<DGR>& adaptor)
2161 2158
        : Parent(adaptor) {}
2162 2159

	
2163 2160
      ArcMap(const UndirectorBase<DGR>& adaptor, const V& value)
2164 2161
        : Parent(adaptor, value) {}
2165 2162

	
2166 2163
    private:
2167 2164
      ArcMap& operator=(const ArcMap& cmap) {
2168 2165
        return operator=<ArcMap>(cmap);
2169 2166
      }
2170 2167

	
2171 2168
      template <typename CMap>
2172 2169
      ArcMap& operator=(const CMap& cmap) {
2173 2170
        Parent::operator=(cmap);
2174 2171
        return *this;
2175 2172
      }
2176 2173
    };
2177 2174

	
2178 2175
    template <typename V>
2179 2176
    class EdgeMap : public Digraph::template ArcMap<V> {
2180 2177
      typedef typename Digraph::template ArcMap<V> Parent;
2181 2178

	
2182 2179
    public:
2183 2180
      typedef V Value;
2184 2181

	
2185 2182
      explicit EdgeMap(const UndirectorBase<DGR>& adaptor)
2186 2183
        : Parent(*adaptor._digraph) {}
2187 2184

	
2188 2185
      EdgeMap(const UndirectorBase<DGR>& adaptor, const V& value)
2189 2186
        : Parent(*adaptor._digraph, value) {}
2190 2187

	
2191 2188
    private:
2192 2189
      EdgeMap& operator=(const EdgeMap& cmap) {
2193 2190
        return operator=<EdgeMap>(cmap);
2194 2191
      }
2195 2192

	
2196 2193
      template <typename CMap>
2197 2194
      EdgeMap& operator=(const CMap& cmap) {
2198 2195
        Parent::operator=(cmap);
2199 2196
        return *this;
2200 2197
      }
2201 2198

	
2202 2199
    };
2203 2200

	
2204 2201
    typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
2205 2202
    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
2206 2203

	
2207 2204
    typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
2208 2205
    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
2209 2206
    
2210 2207
    typedef EdgeNotifier ArcNotifier;
2211 2208
    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
2212 2209

	
2213 2210
  protected:
2214 2211

	
2215 2212
    UndirectorBase() : _digraph(0) {}
2216 2213

	
2217 2214
    DGR* _digraph;
2218 2215

	
2219 2216
    void initialize(DGR& digraph) {
2220 2217
      _digraph = &digraph;
2221 2218
    }
2222 2219

	
2223 2220
  };
2224 2221

	
2225 2222
  /// \ingroup graph_adaptors
2226 2223
  ///
2227 2224
  /// \brief Adaptor class for viewing a digraph as an undirected graph.
2228 2225
  ///
2229 2226
  /// Undirector adaptor can be used for viewing a digraph as an undirected
2230 2227
  /// graph. All arcs of the underlying digraph are showed in the
2231 2228
  /// adaptor as an edge (and also as a pair of arcs, of course).
2232 2229
  /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
2233 2230
  ///
2234 2231
  /// The adapted digraph can also be modified through this adaptor
2235 2232
  /// by adding or removing nodes or edges, unless the \c GR template
2236 2233
  /// parameter is set to be \c const.
2237 2234
  ///
2238 2235
  /// \tparam DGR The type of the adapted digraph.
2239 2236
  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
2240 2237
  /// It can also be specified to be \c const.
2241 2238
  ///
2242 2239
  /// \note The \c Node type of this adaptor and the adapted digraph are
2243 2240
  /// convertible to each other, moreover the \c Edge type of the adaptor
2244 2241
  /// and the \c Arc type of the adapted digraph are also convertible to
2245 2242
  /// each other.
2246 2243
  /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type
2247 2244
  /// of the adapted digraph.)
2248 2245
  template<typename DGR>
2249 2246
#ifdef DOXYGEN
2250 2247
  class Undirector {
2251 2248
#else
2252 2249
  class Undirector :
2253 2250
    public GraphAdaptorExtender<UndirectorBase<DGR> > {
2254 2251
#endif
2255 2252
    typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent;
2256 2253
  public:
2257 2254
    /// The type of the adapted digraph.
2258 2255
    typedef DGR Digraph;
2259 2256
  protected:
2260 2257
    Undirector() { }
2261 2258
  public:
2262 2259

	
2263 2260
    /// \brief Constructor
2264 2261
    ///
2265 2262
    /// Creates an undirected graph from the given digraph.
2266 2263
    Undirector(DGR& digraph) {
2267 2264
      initialize(digraph);
2268 2265
    }
2269 2266

	
2270 2267
    /// \brief Arc map combined from two original arc maps
2271 2268
    ///
2272 2269
    /// This map adaptor class adapts two arc maps of the underlying
2273 2270
    /// digraph to get an arc map of the undirected graph.
2274 2271
    /// Its value type is inherited from the first arc map type (\c FW).
2275 2272
    /// \tparam FW The type of the "foward" arc map.
2276 2273
    /// \tparam BK The type of the "backward" arc map.
2277 2274
    template <typename FW, typename BK>
2278 2275
    class CombinedArcMap {
2279 2276
    public:
2280 2277

	
2281 2278
      /// The key type of the map
2282 2279
      typedef typename Parent::Arc Key;
2283 2280
      /// The value type of the map
2284 2281
      typedef typename FW::Value Value;
2285 2282

	
2286 2283
      typedef typename MapTraits<FW>::ReferenceMapTag ReferenceMapTag;
2287 2284

	
2288 2285
      typedef typename MapTraits<FW>::ReturnValue ReturnValue;
2289 2286
      typedef typename MapTraits<FW>::ConstReturnValue ConstReturnValue;
2290 2287
      typedef typename MapTraits<FW>::ReturnValue Reference;
2291 2288
      typedef typename MapTraits<FW>::ConstReturnValue ConstReference;
2292 2289

	
2293 2290
      /// Constructor
2294 2291
      CombinedArcMap(FW& forward, BK& backward)
2295 2292
        : _forward(&forward), _backward(&backward) {}
2296 2293

	
2297 2294
      /// Sets the value associated with the given key.
2298 2295
      void set(const Key& e, const Value& a) {
2299 2296
        if (Parent::direction(e)) {
2300 2297
          _forward->set(e, a);
2301 2298
        } else {
2302 2299
          _backward->set(e, a);
2303 2300
        }
2304 2301
      }
2305 2302

	
2306 2303
      /// Returns the value associated with the given key.
2307 2304
      ConstReturnValue operator[](const Key& e) const {
2308 2305
        if (Parent::direction(e)) {
2309 2306
          return (*_forward)[e];
2310 2307
        } else {
2311 2308
          return (*_backward)[e];
2312 2309
        }
2313 2310
      }
2314 2311

	
2315 2312
      /// Returns a reference to the value associated with the given key.
2316 2313
      ReturnValue operator[](const Key& e) {
2317 2314
        if (Parent::direction(e)) {
2318 2315
          return (*_forward)[e];
2319 2316
        } else {
2320 2317
          return (*_backward)[e];
2321 2318
        }
2322 2319
      }
2323 2320

	
2324 2321
    protected:
2325 2322

	
2326 2323
      FW* _forward;
2327 2324
      BK* _backward;
2328 2325

	
2329 2326
    };
2330 2327

	
2331 2328
    /// \brief Returns a combined arc map
2332 2329
    ///
2333 2330
    /// This function just returns a combined arc map.
2334 2331
    template <typename FW, typename BK>
2335 2332
    static CombinedArcMap<FW, BK>
2336 2333
    combinedArcMap(FW& forward, BK& backward) {
2337 2334
      return CombinedArcMap<FW, BK>(forward, backward);
2338 2335
    }
2339 2336

	
2340 2337
    template <typename FW, typename BK>
2341 2338
    static CombinedArcMap<const FW, BK>
2342 2339
    combinedArcMap(const FW& forward, BK& backward) {
2343 2340
      return CombinedArcMap<const FW, BK>(forward, backward);
2344 2341
    }
2345 2342

	
2346 2343
    template <typename FW, typename BK>
2347 2344
    static CombinedArcMap<FW, const BK>
2348 2345
    combinedArcMap(FW& forward, const BK& backward) {
2349 2346
      return CombinedArcMap<FW, const BK>(forward, backward);
2350 2347
    }
2351 2348

	
2352 2349
    template <typename FW, typename BK>
2353 2350
    static CombinedArcMap<const FW, const BK>
2354 2351
    combinedArcMap(const FW& forward, const BK& backward) {
2355 2352
      return CombinedArcMap<const FW, const BK>(forward, backward);
2356 2353
    }
2357 2354

	
2358 2355
  };
2359 2356

	
2360 2357
  /// \brief Returns a read-only Undirector adaptor
2361 2358
  ///
2362 2359
  /// This function just returns a read-only \ref Undirector adaptor.
2363 2360
  /// \ingroup graph_adaptors
2364 2361
  /// \relates Undirector
2365 2362
  template<typename DGR>
2366 2363
  Undirector<const DGR> undirector(const DGR& digraph) {
2367 2364
    return Undirector<const DGR>(digraph);
2368 2365
  }
2369 2366

	
2370 2367

	
2371 2368
  template <typename GR, typename DM>
2372 2369
  class OrienterBase {
2373 2370
  public:
2374 2371

	
2375 2372
    typedef GR Graph;
2376 2373
    typedef DM DirectionMap;
2377 2374

	
2378 2375
    typedef typename GR::Node Node;
2379 2376
    typedef typename GR::Edge Arc;
2380 2377

	
2381 2378
    void reverseArc(const Arc& arc) {
2382 2379
      _direction->set(arc, !(*_direction)[arc]);
2383 2380
    }
2384 2381

	
2385 2382
    void first(Node& i) const { _graph->first(i); }
2386 2383
    void first(Arc& i) const { _graph->first(i); }
2387 2384
    void firstIn(Arc& i, const Node& n) const {
2388 2385
      bool d = true;
2389 2386
      _graph->firstInc(i, d, n);
2390 2387
      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
2391 2388
    }
2392 2389
    void firstOut(Arc& i, const Node& n ) const {
2393 2390
      bool d = true;
2394 2391
      _graph->firstInc(i, d, n);
2395 2392
      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
2396 2393
    }
2397 2394

	
2398 2395
    void next(Node& i) const { _graph->next(i); }
2399 2396
    void next(Arc& i) const { _graph->next(i); }
2400 2397
    void nextIn(Arc& i) const {
2401 2398
      bool d = !(*_direction)[i];
2402 2399
      _graph->nextInc(i, d);
2403 2400
      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
2404 2401
    }
2405 2402
    void nextOut(Arc& i) const {
2406 2403
      bool d = (*_direction)[i];
2407 2404
      _graph->nextInc(i, d);
2408 2405
      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
2409 2406
    }
2410 2407

	
2411 2408
    Node source(const Arc& e) const {
2412 2409
      return (*_direction)[e] ? _graph->u(e) : _graph->v(e);
2413 2410
    }
2414 2411
    Node target(const Arc& e) const {
2415 2412
      return (*_direction)[e] ? _graph->v(e) : _graph->u(e);
2416 2413
    }
2417 2414

	
2418 2415
    typedef NodeNumTagIndicator<Graph> NodeNumTag;
2419 2416
    int nodeNum() const { return _graph->nodeNum(); }
2420 2417

	
2421 2418
    typedef EdgeNumTagIndicator<Graph> ArcNumTag;
2422 2419
    int arcNum() const { return _graph->edgeNum(); }
2423 2420

	
2424 2421
    typedef FindEdgeTagIndicator<Graph> FindArcTag;
2425 2422
    Arc findArc(const Node& u, const Node& v,
2426 2423
                const Arc& prev = INVALID) const {
2427 2424
      Arc arc = _graph->findEdge(u, v, prev);
2428 2425
      while (arc != INVALID && source(arc) != u) {
2429 2426
        arc = _graph->findEdge(u, v, arc);
2430 2427
      }
2431 2428
      return arc;
2432 2429
    }
2433 2430

	
2434 2431
    Node addNode() {
2435 2432
      return Node(_graph->addNode());
2436 2433
    }
2437 2434

	
2438 2435
    Arc addArc(const Node& u, const Node& v) {
2439 2436
      Arc arc = _graph->addEdge(u, v);
2440 2437
      _direction->set(arc, _graph->u(arc) == u);
2441 2438
      return arc;
2442 2439
    }
2443 2440

	
2444 2441
    void erase(const Node& i) { _graph->erase(i); }
2445 2442
    void erase(const Arc& i) { _graph->erase(i); }
2446 2443

	
2447 2444
    void clear() { _graph->clear(); }
2448 2445

	
2449 2446
    int id(const Node& v) const { return _graph->id(v); }
2450 2447
    int id(const Arc& e) const { return _graph->id(e); }
2451 2448

	
2452 2449
    Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
2453 2450
    Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
2454 2451

	
2455 2452
    int maxNodeId() const { return _graph->maxNodeId(); }
2456 2453
    int maxArcId() const { return _graph->maxEdgeId(); }
2457 2454

	
2458 2455
    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
2459 2456
    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
2460 2457

	
2461 2458
    typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;
2462 2459
    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
2463 2460

	
2464 2461
    template <typename V>
2465 2462
    class NodeMap : public GR::template NodeMap<V> {
2466 2463
      typedef typename GR::template NodeMap<V> Parent;
2467 2464

	
2468 2465
    public:
2469 2466

	
2470 2467
      explicit NodeMap(const OrienterBase<GR, DM>& adapter)
2471 2468
        : Parent(*adapter._graph) {}
2472 2469

	
2473 2470
      NodeMap(const OrienterBase<GR, DM>& adapter, const V& value)
2474 2471
        : Parent(*adapter._graph, value) {}
2475 2472

	
2476 2473
    private:
2477 2474
      NodeMap& operator=(const NodeMap& cmap) {
2478 2475
        return operator=<NodeMap>(cmap);
2479 2476
      }
2480 2477

	
2481 2478
      template <typename CMap>
2482 2479
      NodeMap& operator=(const CMap& cmap) {
2483 2480
        Parent::operator=(cmap);
2484 2481
        return *this;
2485 2482
      }
2486 2483

	
2487 2484
    };
2488 2485

	
2489 2486
    template <typename V>
2490 2487
    class ArcMap : public GR::template EdgeMap<V> {
2491 2488
      typedef typename Graph::template EdgeMap<V> Parent;
2492 2489

	
2493 2490
    public:
2494 2491

	
2495 2492
      explicit ArcMap(const OrienterBase<GR, DM>& adapter)
2496 2493
        : Parent(*adapter._graph) { }
2497 2494

	
2498 2495
      ArcMap(const OrienterBase<GR, DM>& adapter, const V& value)
2499 2496
        : Parent(*adapter._graph, value) { }
2500 2497

	
2501 2498
    private:
2502 2499
      ArcMap& operator=(const ArcMap& cmap) {
2503 2500
        return operator=<ArcMap>(cmap);
2504 2501
      }
2505 2502

	
2506 2503
      template <typename CMap>
2507 2504
      ArcMap& operator=(const CMap& cmap) {
2508 2505
        Parent::operator=(cmap);
2509 2506
        return *this;
2510 2507
      }
2511 2508
    };
2512 2509

	
2513 2510

	
2514 2511

	
2515 2512
  protected:
2516 2513
    Graph* _graph;
2517 2514
    DM* _direction;
2518 2515

	
2519 2516
    void initialize(GR& graph, DM& direction) {
2520 2517
      _graph = &graph;
2521 2518
      _direction = &direction;
2522 2519
    }
2523 2520

	
2524 2521
  };
2525 2522

	
2526 2523
  /// \ingroup graph_adaptors
2527 2524
  ///
2528 2525
  /// \brief Adaptor class for orienting the edges of a graph to get a digraph
2529 2526
  ///
2530 2527
  /// Orienter adaptor can be used for orienting the edges of a graph to
2531 2528
  /// get a digraph. A \c bool edge map of the underlying graph must be
2532 2529
  /// specified, which define the direction of the arcs in the adaptor.
2533 2530
  /// The arcs can be easily reversed by the \c reverseArc() member function
2534 2531
  /// of the adaptor.
2535 2532
  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
2536 2533
  ///
2537 2534
  /// The adapted graph can also be modified through this adaptor
2538 2535
  /// by adding or removing nodes or arcs, unless the \c GR template
2539 2536
  /// parameter is set to be \c const.
2540 2537
  ///
2541 2538
  /// \tparam GR The type of the adapted graph.
2542 2539
  /// It must conform to the \ref concepts::Graph "Graph" concept.
2543 2540
  /// It can also be specified to be \c const.
2544 2541
  /// \tparam DM The type of the direction map.
2545 2542
  /// It must be a \c bool (or convertible) edge map of the
2546 2543
  /// adapted graph. The default type is
2547 2544
  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
2548 2545
  ///
2549 2546
  /// \note The \c Node type of this adaptor and the adapted graph are
2550 2547
  /// convertible to each other, moreover the \c Arc type of the adaptor
2551 2548
  /// and the \c Edge type of the adapted graph are also convertible to
2552 2549
  /// each other.
2553 2550
#ifdef DOXYGEN
2554 2551
  template<typename GR,
2555 2552
           typename DM>
2556 2553
  class Orienter {
2557 2554
#else
2558 2555
  template<typename GR,
2559 2556
           typename DM = typename GR::template EdgeMap<bool> >
2560 2557
  class Orienter :
2561 2558
    public DigraphAdaptorExtender<OrienterBase<GR, DM> > {
2562 2559
#endif
2563 2560
    typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
2564 2561
  public:
2565 2562

	
2566 2563
    /// The type of the adapted graph.
2567 2564
    typedef GR Graph;
2568 2565
    /// The type of the direction edge map.
2569 2566
    typedef DM DirectionMap;
2570 2567

	
2571 2568
    typedef typename Parent::Arc Arc;
2572 2569

	
2573 2570
  protected:
2574 2571
    Orienter() { }
2575 2572

	
2576 2573
  public:
2577 2574

	
2578 2575
    /// \brief Constructor
2579 2576
    ///
2580 2577
    /// Constructor of the adaptor.
2581 2578
    Orienter(GR& graph, DM& direction) {
2582 2579
      Parent::initialize(graph, direction);
2583 2580
    }
2584 2581

	
2585 2582
    /// \brief Reverses the given arc
2586 2583
    ///
2587 2584
    /// This function reverses the given arc.
2588 2585
    /// It is done by simply negate the assigned value of \c a
2589 2586
    /// in the direction map.
2590 2587
    void reverseArc(const Arc& a) {
2591 2588
      Parent::reverseArc(a);
2592 2589
    }
2593 2590
  };
2594 2591

	
2595 2592
  /// \brief Returns a read-only Orienter adaptor
2596 2593
  ///
2597 2594
  /// This function just returns a read-only \ref Orienter adaptor.
2598 2595
  /// \ingroup graph_adaptors
2599 2596
  /// \relates Orienter
2600 2597
  template<typename GR, typename DM>
2601 2598
  Orienter<const GR, DM>
2602 2599
  orienter(const GR& graph, DM& direction) {
2603 2600
    return Orienter<const GR, DM>(graph, direction);
2604 2601
  }
2605 2602

	
2606 2603
  template<typename GR, typename DM>
2607 2604
  Orienter<const GR, const DM>
2608 2605
  orienter(const GR& graph, const DM& direction) {
2609 2606
    return Orienter<const GR, const DM>(graph, direction);
2610 2607
  }
2611 2608

	
2612 2609
  namespace _adaptor_bits {
2613 2610

	
2614 2611
    template <typename DGR, typename CM, typename FM, typename TL>
2615 2612
    class ResForwardFilter {
2616 2613
    public:
2617 2614

	
2618 2615
      typedef typename DGR::Arc Key;
2619 2616
      typedef bool Value;
2620 2617

	
2621 2618
    private:
2622 2619

	
2623 2620
      const CM* _capacity;
2624 2621
      const FM* _flow;
2625 2622
      TL _tolerance;
2626 2623

	
2627 2624
    public:
2628 2625

	
2629 2626
      ResForwardFilter(const CM& capacity, const FM& flow,
2630 2627
                       const TL& tolerance = TL())
2631 2628
        : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
2632 2629

	
2633 2630
      bool operator[](const typename DGR::Arc& a) const {
2634 2631
        return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
2635 2632
      }
2636 2633
    };
2637 2634

	
2638 2635
    template<typename DGR,typename CM, typename FM, typename TL>
2639 2636
    class ResBackwardFilter {
2640 2637
    public:
2641 2638

	
2642 2639
      typedef typename DGR::Arc Key;
2643 2640
      typedef bool Value;
2644 2641

	
2645 2642
    private:
2646 2643

	
2647 2644
      const CM* _capacity;
2648 2645
      const FM* _flow;
2649 2646
      TL _tolerance;
2650 2647

	
2651 2648
    public:
2652 2649

	
2653 2650
      ResBackwardFilter(const CM& capacity, const FM& flow,
2654 2651
                        const TL& tolerance = TL())
2655 2652
        : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
2656 2653

	
2657 2654
      bool operator[](const typename DGR::Arc& a) const {
2658 2655
        return _tolerance.positive((*_flow)[a]);
2659 2656
      }
2660 2657
    };
2661 2658

	
2662 2659
  }
2663 2660

	
2664 2661
  /// \ingroup graph_adaptors
2665 2662
  ///
2666 2663
  /// \brief Adaptor class for composing the residual digraph for directed
2667 2664
  /// flow and circulation problems.
2668 2665
  ///
2669 2666
  /// ResidualDigraph can be used for composing the \e residual digraph
2670 2667
  /// for directed flow and circulation problems. Let \f$ G=(V, A) \f$
2671 2668
  /// be a directed graph and let \f$ F \f$ be a number type.
2672 2669
  /// Let \f$ flow, cap: A\to F \f$ be functions on the arcs.
2673 2670
  /// This adaptor implements a digraph structure with node set \f$ V \f$
2674 2671
  /// and arc set \f$ A_{forward}\cup A_{backward} \f$,
2675 2672
  /// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)<cap(uv)\} \f$ and
2676 2673
  /// \f$ A_{backward}=\{vu : uv\in A, flow(uv)>0\} \f$, i.e. the so
2677 2674
  /// called residual digraph.
2678 2675
  /// When the union \f$ A_{forward}\cup A_{backward} \f$ is taken,
2679 2676
  /// multiplicities are counted, i.e. the adaptor has exactly
2680 2677
  /// \f$ |A_{forward}| + |A_{backward}|\f$ arcs (it may have parallel
2681 2678
  /// arcs).
2682 2679
  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
2683 2680
  ///
2684 2681
  /// \tparam DGR The type of the adapted digraph.
2685 2682
  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
2686 2683
  /// It is implicitly \c const.
2687 2684
  /// \tparam CM The type of the capacity map.
2688 2685
  /// It must be an arc map of some numerical type, which defines
2689 2686
  /// the capacities in the flow problem. It is implicitly \c const.
2690 2687
  /// The default type is
2691 2688
  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
2692 2689
  /// \tparam FM The type of the flow map.
2693 2690
  /// It must be an arc map of some numerical type, which defines
2694 2691
  /// the flow values in the flow problem. The default type is \c CM.
2695 2692
  /// \tparam TL The tolerance type for handling inexact computation.
2696 2693
  /// The default tolerance type depends on the value type of the
2697 2694
  /// capacity map.
2698 2695
  ///
2699 2696
  /// \note This adaptor is implemented using Undirector and FilterArcs
2700 2697
  /// adaptors.
2701 2698
  ///
2702 2699
  /// \note The \c Node type of this adaptor and the adapted digraph are
2703 2700
  /// convertible to each other, moreover the \c Arc type of the adaptor
2704 2701
  /// is convertible to the \c Arc type of the adapted digraph.
2705 2702
#ifdef DOXYGEN
2706 2703
  template<typename DGR, typename CM, typename FM, typename TL>
2707 2704
  class ResidualDigraph
2708 2705
#else
2709 2706
  template<typename DGR,
2710 2707
           typename CM = typename DGR::template ArcMap<int>,
2711 2708
           typename FM = CM,
2712 2709
           typename TL = Tolerance<typename CM::Value> >
2713 2710
  class ResidualDigraph 
2714 2711
    : public SubDigraph<
2715 2712
        Undirector<const DGR>,
2716 2713
        ConstMap<typename DGR::Node, Const<bool, true> >,
2717 2714
        typename Undirector<const DGR>::template CombinedArcMap<
2718 2715
          _adaptor_bits::ResForwardFilter<const DGR, CM, FM, TL>,
2719 2716
          _adaptor_bits::ResBackwardFilter<const DGR, CM, FM, TL> > >
2720 2717
#endif
2721 2718
  {
2722 2719
  public:
2723 2720

	
2724 2721
    /// The type of the underlying digraph.
2725 2722
    typedef DGR Digraph;
2726 2723
    /// The type of the capacity map.
2727 2724
    typedef CM CapacityMap;
2728 2725
    /// The type of the flow map.
2729 2726
    typedef FM FlowMap;
2730 2727
    /// The tolerance type.
2731 2728
    typedef TL Tolerance;
2732 2729

	
2733 2730
    typedef typename CapacityMap::Value Value;
2734 2731
    typedef ResidualDigraph Adaptor;
2735 2732

	
2736 2733
  protected:
2737 2734

	
2738 2735
    typedef Undirector<const Digraph> Undirected;
2739 2736

	
2740 2737
    typedef ConstMap<typename DGR::Node, Const<bool, true> > NodeFilter;
2741 2738

	
2742 2739
    typedef _adaptor_bits::ResForwardFilter<const DGR, CM,
2743 2740
                                            FM, TL> ForwardFilter;
2744 2741

	
2745 2742
    typedef _adaptor_bits::ResBackwardFilter<const DGR, CM,
2746 2743
                                             FM, TL> BackwardFilter;
2747 2744

	
2748 2745
    typedef typename Undirected::
2749 2746
      template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
2750 2747

	
2751 2748
    typedef SubDigraph<Undirected, NodeFilter, ArcFilter> Parent;
2752 2749

	
2753 2750
    const CapacityMap* _capacity;
2754 2751
    FlowMap* _flow;
2755 2752

	
2756 2753
    Undirected _graph;
2757 2754
    NodeFilter _node_filter;
2758 2755
    ForwardFilter _forward_filter;
2759 2756
    BackwardFilter _backward_filter;
2760 2757
    ArcFilter _arc_filter;
2761 2758

	
2762 2759
  public:
2763 2760

	
2764 2761
    /// \brief Constructor
2765 2762
    ///
2766 2763
    /// Constructor of the residual digraph adaptor. The parameters are the
2767 2764
    /// digraph, the capacity map, the flow map, and a tolerance object.
2768 2765
    ResidualDigraph(const DGR& digraph, const CM& capacity,
2769 2766
                    FM& flow, const TL& tolerance = Tolerance())
2770 2767
      : Parent(), _capacity(&capacity), _flow(&flow), 
2771 2768
        _graph(digraph), _node_filter(),
2772 2769
        _forward_filter(capacity, flow, tolerance),
2773 2770
        _backward_filter(capacity, flow, tolerance),
2774 2771
        _arc_filter(_forward_filter, _backward_filter)
2775 2772
    {
2776 2773
      Parent::initialize(_graph, _node_filter, _arc_filter);
2777 2774
    }
2778 2775

	
2779 2776
    typedef typename Parent::Arc Arc;
2780 2777

	
2781 2778
    /// \brief Returns the residual capacity of the given arc.
2782 2779
    ///
2783 2780
    /// Returns the residual capacity of the given arc.
2784 2781
    Value residualCapacity(const Arc& a) const {
2785 2782
      if (Undirected::direction(a)) {
2786 2783
        return (*_capacity)[a] - (*_flow)[a];
2787 2784
      } else {
2788 2785
        return (*_flow)[a];
2789 2786
      }
2790 2787
    }
2791 2788

	
2792 2789
    /// \brief Augments on the given arc in the residual digraph.
2793 2790
    ///
2794 2791
    /// Augments on the given arc in the residual digraph. It increases
2795 2792
    /// or decreases the flow value on the original arc according to the
2796 2793
    /// direction of the residual arc.
2797 2794
    void augment(const Arc& a, const Value& v) const {
2798 2795
      if (Undirected::direction(a)) {
2799 2796
        _flow->set(a, (*_flow)[a] + v);
2800 2797
      } else {
2801 2798
        _flow->set(a, (*_flow)[a] - v);
2802 2799
      }
2803 2800
    }
2804 2801

	
2805 2802
    /// \brief Returns \c true if the given residual arc is a forward arc.
2806 2803
    ///
2807 2804
    /// Returns \c true if the given residual arc has the same orientation
2808 2805
    /// as the original arc, i.e. it is a so called forward arc.
2809 2806
    static bool forward(const Arc& a) {
2810 2807
      return Undirected::direction(a);
2811 2808
    }
2812 2809

	
2813 2810
    /// \brief Returns \c true if the given residual arc is a backward arc.
2814 2811
    ///
2815 2812
    /// Returns \c true if the given residual arc has the opposite orientation
2816 2813
    /// than the original arc, i.e. it is a so called backward arc.
2817 2814
    static bool backward(const Arc& a) {
2818 2815
      return !Undirected::direction(a);
2819 2816
    }
2820 2817

	
2821 2818
    /// \brief Returns the forward oriented residual arc.
2822 2819
    ///
2823 2820
    /// Returns the forward oriented residual arc related to the given
2824 2821
    /// arc of the underlying digraph.
2825 2822
    static Arc forward(const typename Digraph::Arc& a) {
2826 2823
      return Undirected::direct(a, true);
2827 2824
    }
2828 2825

	
2829 2826
    /// \brief Returns the backward oriented residual arc.
2830 2827
    ///
2831 2828
    /// Returns the backward oriented residual arc related to the given
2832 2829
    /// arc of the underlying digraph.
2833 2830
    static Arc backward(const typename Digraph::Arc& a) {
2834 2831
      return Undirected::direct(a, false);
2835 2832
    }
2836 2833

	
2837 2834
    /// \brief Residual capacity map.
2838 2835
    ///
2839 2836
    /// This map adaptor class can be used for obtaining the residual
2840 2837
    /// capacities as an arc map of the residual digraph.
2841 2838
    /// Its value type is inherited from the capacity map.
2842 2839
    class ResidualCapacity {
2843 2840
    protected:
2844 2841
      const Adaptor* _adaptor;
2845 2842
    public:
2846 2843
      /// The key type of the map
2847 2844
      typedef Arc Key;
2848 2845
      /// The value type of the map
2849 2846
      typedef typename CapacityMap::Value Value;
2850 2847

	
2851 2848
      /// Constructor
2852 2849
      ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor) 
2853 2850
        : _adaptor(&adaptor) {}
2854 2851

	
2855 2852
      /// Returns the value associated with the given residual arc
2856 2853
      Value operator[](const Arc& a) const {
2857 2854
        return _adaptor->residualCapacity(a);
2858 2855
      }
2859 2856

	
2860 2857
    };
2861 2858

	
2862 2859
    /// \brief Returns a residual capacity map
2863 2860
    ///
2864 2861
    /// This function just returns a residual capacity map.
2865 2862
    ResidualCapacity residualCapacity() const {
2866 2863
      return ResidualCapacity(*this);
2867 2864
    }
2868 2865

	
2869 2866
  };
2870 2867

	
2871 2868
  /// \brief Returns a (read-only) Residual adaptor
2872 2869
  ///
2873 2870
  /// This function just returns a (read-only) \ref ResidualDigraph adaptor.
2874 2871
  /// \ingroup graph_adaptors
2875 2872
  /// \relates ResidualDigraph
2876 2873
    template<typename DGR, typename CM, typename FM>
2877 2874
  ResidualDigraph<DGR, CM, FM>
2878 2875
  residualDigraph(const DGR& digraph, const CM& capacity_map, FM& flow_map) {
2879 2876
    return ResidualDigraph<DGR, CM, FM> (digraph, capacity_map, flow_map);
2880 2877
  }
2881 2878

	
2882 2879

	
2883 2880
  template <typename DGR>
2884 2881
  class SplitNodesBase {
2885 2882
    typedef DigraphAdaptorBase<const DGR> Parent;
2886 2883

	
2887 2884
  public:
2888 2885

	
2889 2886
    typedef DGR Digraph;
2890 2887
    typedef SplitNodesBase Adaptor;
2891 2888

	
2892 2889
    typedef typename DGR::Node DigraphNode;
2893 2890
    typedef typename DGR::Arc DigraphArc;
2894 2891

	
2895 2892
    class Node;
2896 2893
    class Arc;
2897 2894

	
2898 2895
  private:
2899 2896

	
2900 2897
    template <typename T> class NodeMapBase;
2901 2898
    template <typename T> class ArcMapBase;
2902 2899

	
2903 2900
  public:
2904 2901

	
2905 2902
    class Node : public DigraphNode {
2906 2903
      friend class SplitNodesBase;
2907 2904
      template <typename T> friend class NodeMapBase;
2908 2905
    private:
2909 2906

	
2910 2907
      bool _in;
2911 2908
      Node(DigraphNode node, bool in)
2912 2909
        : DigraphNode(node), _in(in) {}
2913 2910

	
2914 2911
    public:
2915 2912

	
2916 2913
      Node() {}
2917 2914
      Node(Invalid) : DigraphNode(INVALID), _in(true) {}
2918 2915

	
2919 2916
      bool operator==(const Node& node) const {
2920 2917
        return DigraphNode::operator==(node) && _in == node._in;
2921 2918
      }
2922 2919

	
2923 2920
      bool operator!=(const Node& node) const {
2924 2921
        return !(*this == node);
2925 2922
      }
2926 2923

	
2927 2924
      bool operator<(const Node& node) const {
2928 2925
        return DigraphNode::operator<(node) ||
2929 2926
          (DigraphNode::operator==(node) && _in < node._in);
2930 2927
      }
2931 2928
    };
2932 2929

	
2933 2930
    class Arc {
2934 2931
      friend class SplitNodesBase;
2935 2932
      template <typename T> friend class ArcMapBase;
2936 2933
    private:
2937 2934
      typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;
2938 2935

	
2939 2936
      explicit Arc(const DigraphArc& arc) : _item(arc) {}
2940 2937
      explicit Arc(const DigraphNode& node) : _item(node) {}
2941 2938

	
2942 2939
      ArcImpl _item;
2943 2940

	
2944 2941
    public:
2945 2942
      Arc() {}
2946 2943
      Arc(Invalid) : _item(DigraphArc(INVALID)) {}
2947 2944

	
2948 2945
      bool operator==(const Arc& arc) const {
2949 2946
        if (_item.firstState()) {
2950 2947
          if (arc._item.firstState()) {
2951 2948
            return _item.first() == arc._item.first();
2952 2949
          }
2953 2950
        } else {
2954 2951
          if (arc._item.secondState()) {
2955 2952
            return _item.second() == arc._item.second();
2956 2953
          }
2957 2954
        }
2958 2955
        return false;
2959 2956
      }
2960 2957

	
2961 2958
      bool operator!=(const Arc& arc) const {
2962 2959
        return !(*this == arc);
2963 2960
      }
2964 2961

	
2965 2962
      bool operator<(const Arc& arc) const {
2966 2963
        if (_item.firstState()) {
2967 2964
          if (arc._item.firstState()) {
2968 2965
            return _item.first() < arc._item.first();
2969 2966
          }
2970 2967
          return false;
2971 2968
        } else {
2972 2969
          if (arc._item.secondState()) {
2973 2970
            return _item.second() < arc._item.second();
2974 2971
          }
2975 2972
          return true;
2976 2973
        }
2977 2974
      }
2978 2975

	
2979 2976
      operator DigraphArc() const { return _item.first(); }
2980 2977
      operator DigraphNode() const { return _item.second(); }
2981 2978

	
2982 2979
    };
2983 2980

	
2984 2981
    void first(Node& n) const {
2985 2982
      _digraph->first(n);
2986 2983
      n._in = true;
2987 2984
    }
2988 2985

	
2989 2986
    void next(Node& n) const {
2990 2987
      if (n._in) {
2991 2988
        n._in = false;
2992 2989
      } else {
2993 2990
        n._in = true;
2994 2991
        _digraph->next(n);
2995 2992
      }
2996 2993
    }
2997 2994

	
2998 2995
    void first(Arc& e) const {
2999 2996
      e._item.setSecond();
3000 2997
      _digraph->first(e._item.second());
3001 2998
      if (e._item.second() == INVALID) {
3002 2999
        e._item.setFirst();
3003 3000
        _digraph->first(e._item.first());
3004 3001
      }
3005 3002
    }
3006 3003

	
3007 3004
    void next(Arc& e) const {
3008 3005
      if (e._item.secondState()) {
3009 3006
        _digraph->next(e._item.second());
3010 3007
        if (e._item.second() == INVALID) {
3011 3008
          e._item.setFirst();
3012 3009
          _digraph->first(e._item.first());
3013 3010
        }
3014 3011
      } else {
3015 3012
        _digraph->next(e._item.first());
3016 3013
      }
3017 3014
    }
3018 3015

	
3019 3016
    void firstOut(Arc& e, const Node& n) const {
3020 3017
      if (n._in) {
3021 3018
        e._item.setSecond(n);
3022 3019
      } else {
3023 3020
        e._item.setFirst();
3024 3021
        _digraph->firstOut(e._item.first(), n);
3025 3022
      }
3026 3023
    }
3027 3024

	
3028 3025
    void nextOut(Arc& e) const {
3029 3026
      if (!e._item.firstState()) {
3030 3027
        e._item.setFirst(INVALID);
3031 3028
      } else {
3032 3029
        _digraph->nextOut(e._item.first());
3033 3030
      }
3034 3031
    }
3035 3032

	
3036 3033
    void firstIn(Arc& e, const Node& n) const {
3037 3034
      if (!n._in) {
3038 3035
        e._item.setSecond(n);
3039 3036
      } else {
3040 3037
        e._item.setFirst();
3041 3038
        _digraph->firstIn(e._item.first(), n);
3042 3039
      }
3043 3040
    }
3044 3041

	
3045 3042
    void nextIn(Arc& e) const {
3046 3043
      if (!e._item.firstState()) {
3047 3044
        e._item.setFirst(INVALID);
3048 3045
      } else {
3049 3046
        _digraph->nextIn(e._item.first());
3050 3047
      }
3051 3048
    }
3052 3049

	
3053 3050
    Node source(const Arc& e) const {
3054 3051
      if (e._item.firstState()) {
3055 3052
        return Node(_digraph->source(e._item.first()), false);
3056 3053
      } else {
3057 3054
        return Node(e._item.second(), true);
3058 3055
      }
3059 3056
    }
3060 3057

	
3061 3058
    Node target(const Arc& e) const {
3062 3059
      if (e._item.firstState()) {
3063 3060
        return Node(_digraph->target(e._item.first()), true);
3064 3061
      } else {
3065 3062
        return Node(e._item.second(), false);
3066 3063
      }
3067 3064
    }
3068 3065

	
3069 3066
    int id(const Node& n) const {
3070 3067
      return (_digraph->id(n) << 1) | (n._in ? 0 : 1);
3071 3068
    }
3072 3069
    Node nodeFromId(int ix) const {
3073 3070
      return Node(_digraph->nodeFromId(ix >> 1), (ix & 1) == 0);
3074 3071
    }
3075 3072
    int maxNodeId() const {
3076 3073
      return 2 * _digraph->maxNodeId() + 1;
3077 3074
    }
3078 3075

	
3079 3076
    int id(const Arc& e) const {
3080 3077
      if (e._item.firstState()) {
3081 3078
        return _digraph->id(e._item.first()) << 1;
3082 3079
      } else {
3083 3080
        return (_digraph->id(e._item.second()) << 1) | 1;
3084 3081
      }
3085 3082
    }
3086 3083
    Arc arcFromId(int ix) const {
3087 3084
      if ((ix & 1) == 0) {
3088 3085
        return Arc(_digraph->arcFromId(ix >> 1));
3089 3086
      } else {
3090 3087
        return Arc(_digraph->nodeFromId(ix >> 1));
3091 3088
      }
3092 3089
    }
3093 3090
    int maxArcId() const {
3094 3091
      return std::max(_digraph->maxNodeId() << 1,
3095 3092
                      (_digraph->maxArcId() << 1) | 1);
3096 3093
    }
3097 3094

	
3098 3095
    static bool inNode(const Node& n) {
3099 3096
      return n._in;
3100 3097
    }
3101 3098

	
3102 3099
    static bool outNode(const Node& n) {
3103 3100
      return !n._in;
3104 3101
    }
3105 3102

	
3106 3103
    static bool origArc(const Arc& e) {
3107 3104
      return e._item.firstState();
3108 3105
    }
3109 3106

	
3110 3107
    static bool bindArc(const Arc& e) {
3111 3108
      return e._item.secondState();
3112 3109
    }
3113 3110

	
3114 3111
    static Node inNode(const DigraphNode& n) {
3115 3112
      return Node(n, true);
3116 3113
    }
3117 3114

	
3118 3115
    static Node outNode(const DigraphNode& n) {
3119 3116
      return Node(n, false);
3120 3117
    }
3121 3118

	
3122 3119
    static Arc arc(const DigraphNode& n) {
3123 3120
      return Arc(n);
3124 3121
    }
3125 3122

	
3126 3123
    static Arc arc(const DigraphArc& e) {
3127 3124
      return Arc(e);
3128 3125
    }
3129 3126

	
3130 3127
    typedef True NodeNumTag;
3131 3128
    int nodeNum() const {
3132 3129
      return  2 * countNodes(*_digraph);
3133 3130
    }
3134 3131

	
3135 3132
    typedef True ArcNumTag;
3136 3133
    int arcNum() const {
3137 3134
      return countArcs(*_digraph) + countNodes(*_digraph);
3138 3135
    }
3139 3136

	
3140 3137
    typedef True FindArcTag;
3141 3138
    Arc findArc(const Node& u, const Node& v,
3142 3139
                const Arc& prev = INVALID) const {
3143 3140
      if (inNode(u) && outNode(v)) {
3144 3141
        if (static_cast<const DigraphNode&>(u) ==
3145 3142
            static_cast<const DigraphNode&>(v) && prev == INVALID) {
3146 3143
          return Arc(u);
3147 3144
        }
3148 3145
      }
3149 3146
      else if (outNode(u) && inNode(v)) {
3150 3147
        return Arc(::lemon::findArc(*_digraph, u, v, prev));
3151 3148
      }
3152 3149
      return INVALID;
3153 3150
    }
3154 3151

	
3155 3152
  private:
3156 3153

	
3157 3154
    template <typename V>
3158 3155
    class NodeMapBase
3159 3156
      : public MapTraits<typename Parent::template NodeMap<V> > {
3160 3157
      typedef typename Parent::template NodeMap<V> NodeImpl;
3161 3158
    public:
3162 3159
      typedef Node Key;
3163 3160
      typedef V Value;
3164 3161
      typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag;
3165 3162
      typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue;
3166 3163
      typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReturnValue;
3167 3164
      typedef typename MapTraits<NodeImpl>::ReturnValue Reference;
3168 3165
      typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference;
3169 3166

	
3170 3167
      NodeMapBase(const SplitNodesBase<DGR>& adaptor)
3171 3168
        : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
3172 3169
      NodeMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)
3173 3170
        : _in_map(*adaptor._digraph, value),
3174 3171
          _out_map(*adaptor._digraph, value) {}
3175 3172

	
3176 3173
      void set(const Node& key, const V& val) {
3177 3174
        if (SplitNodesBase<DGR>::inNode(key)) { _in_map.set(key, val); }
3178 3175
        else {_out_map.set(key, val); }
3179 3176
      }
3180 3177

	
3181 3178
      ReturnValue operator[](const Node& key) {
3182 3179
        if (SplitNodesBase<DGR>::inNode(key)) { return _in_map[key]; }
3183 3180
        else { return _out_map[key]; }
3184 3181
      }
3185 3182

	
3186 3183
      ConstReturnValue operator[](const Node& key) const {
3187 3184
        if (Adaptor::inNode(key)) { return _in_map[key]; }
3188 3185
        else { return _out_map[key]; }
3189 3186
      }
3190 3187

	
3191 3188
    private:
3192 3189
      NodeImpl _in_map, _out_map;
3193 3190
    };
3194 3191

	
3195 3192
    template <typename V>
3196 3193
    class ArcMapBase
3197 3194
      : public MapTraits<typename Parent::template ArcMap<V> > {
3198 3195
      typedef typename Parent::template ArcMap<V> ArcImpl;
3199 3196
      typedef typename Parent::template NodeMap<V> NodeImpl;
3200 3197
    public:
3201 3198
      typedef Arc Key;
3202 3199
      typedef V Value;
3203 3200
      typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag;
3204 3201
      typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue;
3205 3202
      typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReturnValue;
3206 3203
      typedef typename MapTraits<ArcImpl>::ReturnValue Reference;
3207 3204
      typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference;
3208 3205

	
3209 3206
      ArcMapBase(const SplitNodesBase<DGR>& adaptor)
3210 3207
        : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
3211 3208
      ArcMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)
3212 3209
        : _arc_map(*adaptor._digraph, value),
3213 3210
          _node_map(*adaptor._digraph, value) {}
3214 3211

	
3215 3212
      void set(const Arc& key, const V& val) {
3216 3213
        if (SplitNodesBase<DGR>::origArc(key)) {
3217 3214
          _arc_map.set(static_cast<const DigraphArc&>(key), val);
3218 3215
        } else {
3219 3216
          _node_map.set(static_cast<const DigraphNode&>(key), val);
3220 3217
        }
3221 3218
      }
3222 3219

	
3223 3220
      ReturnValue operator[](const Arc& key) {
3224 3221
        if (SplitNodesBase<DGR>::origArc(key)) {
3225 3222
          return _arc_map[static_cast<const DigraphArc&>(key)];
3226 3223
        } else {
3227 3224
          return _node_map[static_cast<const DigraphNode&>(key)];
3228 3225
        }
3229 3226
      }
3230 3227

	
3231 3228
      ConstReturnValue operator[](const Arc& key) const {
3232 3229
        if (SplitNodesBase<DGR>::origArc(key)) {
3233 3230
          return _arc_map[static_cast<const DigraphArc&>(key)];
3234 3231
        } else {
3235 3232
          return _node_map[static_cast<const DigraphNode&>(key)];
3236 3233
        }
3237 3234
      }
3238 3235

	
3239 3236
    private:
3240 3237
      ArcImpl _arc_map;
3241 3238
      NodeImpl _node_map;
3242 3239
    };
3243 3240

	
3244 3241
  public:
3245 3242

	
3246 3243
    template <typename V>
3247 3244
    class NodeMap
3248 3245
      : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > {
3249 3246
      typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > Parent;
3250 3247

	
3251 3248
    public:
3252 3249
      typedef V Value;
3253 3250

	
3254 3251
      NodeMap(const SplitNodesBase<DGR>& adaptor)
3255 3252
        : Parent(adaptor) {}
3256 3253

	
3257 3254
      NodeMap(const SplitNodesBase<DGR>& adaptor, const V& value)
3258 3255
        : Parent(adaptor, value) {}
3259 3256

	
3260 3257
    private:
3261 3258
      NodeMap& operator=(const NodeMap& cmap) {
3262 3259
        return operator=<NodeMap>(cmap);
3263 3260
      }
3264 3261

	
3265 3262
      template <typename CMap>
3266 3263
      NodeMap& operator=(const CMap& cmap) {
3267 3264
        Parent::operator=(cmap);
3268 3265
        return *this;
3269 3266
      }
3270 3267
    };
3271 3268

	
3272 3269
    template <typename V>
3273 3270
    class ArcMap
3274 3271
      : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > {
3275 3272
      typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > Parent;
3276 3273

	
3277 3274
    public:
3278 3275
      typedef V Value;
3279 3276

	
3280 3277
      ArcMap(const SplitNodesBase<DGR>& adaptor)
3281 3278
        : Parent(adaptor) {}
3282 3279

	
3283 3280
      ArcMap(const SplitNodesBase<DGR>& adaptor, const V& value)
3284 3281
        : Parent(adaptor, value) {}
3285 3282

	
3286 3283
    private:
3287 3284
      ArcMap& operator=(const ArcMap& cmap) {
3288 3285
        return operator=<ArcMap>(cmap);
3289 3286
      }
3290 3287

	
3291 3288
      template <typename CMap>
3292 3289
      ArcMap& operator=(const CMap& cmap) {
3293 3290
        Parent::operator=(cmap);
3294 3291
        return *this;
3295 3292
      }
3296 3293
    };
3297 3294

	
3298 3295
  protected:
3299 3296

	
3300 3297
    SplitNodesBase() : _digraph(0) {}
3301 3298

	
3302 3299
    DGR* _digraph;
3303 3300

	
3304 3301
    void initialize(Digraph& digraph) {
3305 3302
      _digraph = &digraph;
3306 3303
    }
3307 3304

	
3308 3305
  };
3309 3306

	
3310 3307
  /// \ingroup graph_adaptors
3311 3308
  ///
3312 3309
  /// \brief Adaptor class for splitting the nodes of a digraph.
3313 3310
  ///
3314 3311
  /// SplitNodes adaptor can be used for splitting each node into an
3315 3312
  /// \e in-node and an \e out-node in a digraph. Formaly, the adaptor
3316 3313
  /// replaces each node \f$ u \f$ in the digraph with two nodes,
3317 3314
  /// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$.
3318 3315
  /// If there is a \f$ (v, u) \f$ arc in the original digraph, then the
3319 3316
  /// new target of the arc will be \f$ u_{in} \f$ and similarly the
3320 3317
  /// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$.
3321 3318
  /// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$
3322 3319
  /// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph.
3323 3320
  ///
3324 3321
  /// The aim of this class is running an algorithm with respect to node
3325 3322
  /// costs or capacities if the algorithm considers only arc costs or
3326 3323
  /// capacities directly.
3327 3324
  /// In this case you can use \c SplitNodes adaptor, and set the node
3328 3325
  /// costs/capacities of the original digraph to the \e bind \e arcs
3329 3326
  /// in the adaptor.
3330 3327
  ///
3331 3328
  /// \tparam DGR The type of the adapted digraph.
3332 3329
  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
3333 3330
  /// It is implicitly \c const.
3334 3331
  ///
3335 3332
  /// \note The \c Node type of this adaptor is converible to the \c Node
3336 3333
  /// type of the adapted digraph.
3337 3334
  template <typename DGR>
3338 3335
#ifdef DOXYGEN
3339 3336
  class SplitNodes {
3340 3337
#else
3341 3338
  class SplitNodes
3342 3339
    : public DigraphAdaptorExtender<SplitNodesBase<const DGR> > {
3343 3340
#endif
3344 3341
    typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent;
3345 3342

	
3346 3343
  public:
3347 3344
    typedef DGR Digraph;
3348 3345

	
3349 3346
    typedef typename DGR::Node DigraphNode;
3350 3347
    typedef typename DGR::Arc DigraphArc;
3351 3348

	
3352 3349
    typedef typename Parent::Node Node;
3353 3350
    typedef typename Parent::Arc Arc;
3354 3351

	
3355 3352
    /// \brief Constructor
3356 3353
    ///
3357 3354
    /// Constructor of the adaptor.
3358 3355
    SplitNodes(const DGR& g) {
3359 3356
      Parent::initialize(g);
3360 3357
    }
3361 3358

	
3362 3359
    /// \brief Returns \c true if the given node is an in-node.
3363 3360
    ///
3364 3361
    /// Returns \c true if the given node is an in-node.
3365 3362
    static bool inNode(const Node& n) {
3366 3363
      return Parent::inNode(n);
3367 3364
    }
3368 3365

	
3369 3366
    /// \brief Returns \c true if the given node is an out-node.
3370 3367
    ///
3371 3368
    /// Returns \c true if the given node is an out-node.
3372 3369
    static bool outNode(const Node& n) {
3373 3370
      return Parent::outNode(n);
3374 3371
    }
3375 3372

	
3376 3373
    /// \brief Returns \c true if the given arc is an original arc.
3377 3374
    ///
3378 3375
    /// Returns \c true if the given arc is one of the arcs in the
3379 3376
    /// original digraph.
3380 3377
    static bool origArc(const Arc& a) {
3381 3378
      return Parent::origArc(a);
3382 3379
    }
3383 3380

	
3384 3381
    /// \brief Returns \c true if the given arc is a bind arc.
3385 3382
    ///
3386 3383
    /// Returns \c true if the given arc is a bind arc, i.e. it connects
3387 3384
    /// an in-node and an out-node.
3388 3385
    static bool bindArc(const Arc& a) {
3389 3386
      return Parent::bindArc(a);
3390 3387
    }
3391 3388

	
3392 3389
    /// \brief Returns the in-node created from the given original node.
3393 3390
    ///
3394 3391
    /// Returns the in-node created from the given original node.
3395 3392
    static Node inNode(const DigraphNode& n) {
3396 3393
      return Parent::inNode(n);
3397 3394
    }
3398 3395

	
3399 3396
    /// \brief Returns the out-node created from the given original node.
3400 3397
    ///
3401 3398
    /// Returns the out-node created from the given original node.
3402 3399
    static Node outNode(const DigraphNode& n) {
3403 3400
      return Parent::outNode(n);
3404 3401
    }
3405 3402

	
3406 3403
    /// \brief Returns the bind arc that corresponds to the given
3407 3404
    /// original node.
3408 3405
    ///
3409 3406
    /// Returns the bind arc in the adaptor that corresponds to the given
3410 3407
    /// original node, i.e. the arc connecting the in-node and out-node
3411 3408
    /// of \c n.
3412 3409
    static Arc arc(const DigraphNode& n) {
3413 3410
      return Parent::arc(n);
3414 3411
    }
3415 3412

	
3416 3413
    /// \brief Returns the arc that corresponds to the given original arc.
3417 3414
    ///
3418 3415
    /// Returns the arc in the adaptor that corresponds to the given
3419 3416
    /// original arc.
3420 3417
    static Arc arc(const DigraphArc& a) {
3421 3418
      return Parent::arc(a);
3422 3419
    }
3423 3420

	
3424 3421
    /// \brief Node map combined from two original node maps
3425 3422
    ///
3426 3423
    /// This map adaptor class adapts two node maps of the original digraph
3427 3424
    /// to get a node map of the split digraph.
3428 3425
    /// Its value type is inherited from the first node map type (\c IN).
3429 3426
    /// \tparam IN The type of the node map for the in-nodes. 
3430 3427
    /// \tparam OUT The type of the node map for the out-nodes.
3431 3428
    template <typename IN, typename OUT>
3432 3429
    class CombinedNodeMap {
3433 3430
    public:
3434 3431

	
3435 3432
      /// The key type of the map
3436 3433
      typedef Node Key;
3437 3434
      /// The value type of the map
3438 3435
      typedef typename IN::Value Value;
3439 3436

	
3440 3437
      typedef typename MapTraits<IN>::ReferenceMapTag ReferenceMapTag;
3441 3438
      typedef typename MapTraits<IN>::ReturnValue ReturnValue;
3442 3439
      typedef typename MapTraits<IN>::ConstReturnValue ConstReturnValue;
3443 3440
      typedef typename MapTraits<IN>::ReturnValue Reference;
3444 3441
      typedef typename MapTraits<IN>::ConstReturnValue ConstReference;
3445 3442

	
3446 3443
      /// Constructor
3447 3444
      CombinedNodeMap(IN& in_map, OUT& out_map)
3448 3445
        : _in_map(in_map), _out_map(out_map) {}
3449 3446

	
3450 3447
      /// Returns the value associated with the given key.
3451 3448
      Value operator[](const Key& key) const {
3452 3449
        if (SplitNodesBase<const DGR>::inNode(key)) {
3453 3450
          return _in_map[key];
3454 3451
        } else {
3455 3452
          return _out_map[key];
3456 3453
        }
3457 3454
      }
3458 3455

	
3459 3456
      /// Returns a reference to the value associated with the given key.
3460 3457
      Value& operator[](const Key& key) {
3461 3458
        if (SplitNodesBase<const DGR>::inNode(key)) {
3462 3459
          return _in_map[key];
3463 3460
        } else {
3464 3461
          return _out_map[key];
3465 3462
        }
3466 3463
      }
3467 3464

	
3468 3465
      /// Sets the value associated with the given key.
3469 3466
      void set(const Key& key, const Value& value) {
3470 3467
        if (SplitNodesBase<const DGR>::inNode(key)) {
3471 3468
          _in_map.set(key, value);
3472 3469
        } else {
3473 3470
          _out_map.set(key, value);
3474 3471
        }
3475 3472
      }
3476 3473

	
3477 3474
    private:
3478 3475

	
3479 3476
      IN& _in_map;
3480 3477
      OUT& _out_map;
3481 3478

	
3482 3479
    };
3483 3480

	
3484 3481

	
3485 3482
    /// \brief Returns a combined node map
3486 3483
    ///
3487 3484
    /// This function just returns a combined node map.
3488 3485
    template <typename IN, typename OUT>
3489 3486
    static CombinedNodeMap<IN, OUT>
3490 3487
    combinedNodeMap(IN& in_map, OUT& out_map) {
3491 3488
      return CombinedNodeMap<IN, OUT>(in_map, out_map);
3492 3489
    }
3493 3490

	
3494 3491
    template <typename IN, typename OUT>
3495 3492
    static CombinedNodeMap<const IN, OUT>
3496 3493
    combinedNodeMap(const IN& in_map, OUT& out_map) {
3497 3494
      return CombinedNodeMap<const IN, OUT>(in_map, out_map);
3498 3495
    }
3499 3496

	
3500 3497
    template <typename IN, typename OUT>
3501 3498
    static CombinedNodeMap<IN, const OUT>
3502 3499
    combinedNodeMap(IN& in_map, const OUT& out_map) {
3503 3500
      return CombinedNodeMap<IN, const OUT>(in_map, out_map);
3504 3501
    }
3505 3502

	
3506 3503
    template <typename IN, typename OUT>
3507 3504
    static CombinedNodeMap<const IN, const OUT>
3508 3505
    combinedNodeMap(const IN& in_map, const OUT& out_map) {
3509 3506
      return CombinedNodeMap<const IN, const OUT>(in_map, out_map);
3510 3507
    }
3511 3508

	
3512 3509
    /// \brief Arc map combined from an arc map and a node map of the
3513 3510
    /// original digraph.
3514 3511
    ///
3515 3512
    /// This map adaptor class adapts an arc map and a node map of the
3516 3513
    /// original digraph to get an arc map of the split digraph.
3517 3514
    /// Its value type is inherited from the original arc map type (\c AM).
3518 3515
    /// \tparam AM The type of the arc map.
3519 3516
    /// \tparam NM the type of the node map.
3520 3517
    template <typename AM, typename NM>
3521 3518
    class CombinedArcMap {
3522 3519
    public:
3523 3520

	
3524 3521
      /// The key type of the map
3525 3522
      typedef Arc Key;
3526 3523
      /// The value type of the map
3527 3524
      typedef typename AM::Value Value;
3528 3525

	
3529 3526
      typedef typename MapTraits<AM>::ReferenceMapTag ReferenceMapTag;
3530 3527
      typedef typename MapTraits<AM>::ReturnValue ReturnValue;
3531 3528
      typedef typename MapTraits<AM>::ConstReturnValue ConstReturnValue;
3532 3529
      typedef typename MapTraits<AM>::ReturnValue Reference;
3533 3530
      typedef typename MapTraits<AM>::ConstReturnValue ConstReference;
3534 3531

	
3535 3532
      /// Constructor
3536 3533
      CombinedArcMap(AM& arc_map, NM& node_map)
3537 3534
        : _arc_map(arc_map), _node_map(node_map) {}
3538 3535

	
3539 3536
      /// Returns the value associated with the given key.
3540 3537
      Value operator[](const Key& arc) const {
3541 3538
        if (SplitNodesBase<const DGR>::origArc(arc)) {
3542 3539
          return _arc_map[arc];
3543 3540
        } else {
3544 3541
          return _node_map[arc];
3545 3542
        }
3546 3543
      }
3547 3544

	
3548 3545
      /// Returns a reference to the value associated with the given key.
3549 3546
      Value& operator[](const Key& arc) {
3550 3547
        if (SplitNodesBase<const DGR>::origArc(arc)) {
3551 3548
          return _arc_map[arc];
3552 3549
        } else {
3553 3550
          return _node_map[arc];
3554 3551
        }
3555 3552
      }
3556 3553

	
3557 3554
      /// Sets the value associated with the given key.
3558 3555
      void set(const Arc& arc, const Value& val) {
3559 3556
        if (SplitNodesBase<const DGR>::origArc(arc)) {
3560 3557
          _arc_map.set(arc, val);
3561 3558
        } else {
3562 3559
          _node_map.set(arc, val);
3563 3560
        }
3564 3561
      }
3565 3562

	
3566 3563
    private:
3567 3564

	
3568 3565
      AM& _arc_map;
3569 3566
      NM& _node_map;
3570 3567

	
3571 3568
    };
3572 3569

	
3573 3570
    /// \brief Returns a combined arc map
3574 3571
    ///
3575 3572
    /// This function just returns a combined arc map.
3576 3573
    template <typename ArcMap, typename NodeMap>
3577 3574
    static CombinedArcMap<ArcMap, NodeMap>
3578 3575
    combinedArcMap(ArcMap& arc_map, NodeMap& node_map) {
3579 3576
      return CombinedArcMap<ArcMap, NodeMap>(arc_map, node_map);
3580 3577
    }
3581 3578

	
3582 3579
    template <typename ArcMap, typename NodeMap>
3583 3580
    static CombinedArcMap<const ArcMap, NodeMap>
3584 3581
    combinedArcMap(const ArcMap& arc_map, NodeMap& node_map) {
3585 3582
      return CombinedArcMap<const ArcMap, NodeMap>(arc_map, node_map);
3586 3583
    }
3587 3584

	
3588 3585
    template <typename ArcMap, typename NodeMap>
3589 3586
    static CombinedArcMap<ArcMap, const NodeMap>
3590 3587
    combinedArcMap(ArcMap& arc_map, const NodeMap& node_map) {
3591 3588
      return CombinedArcMap<ArcMap, const NodeMap>(arc_map, node_map);
3592 3589
    }
3593 3590

	
3594 3591
    template <typename ArcMap, typename NodeMap>
3595 3592
    static CombinedArcMap<const ArcMap, const NodeMap>
3596 3593
    combinedArcMap(const ArcMap& arc_map, const NodeMap& node_map) {
3597 3594
      return CombinedArcMap<const ArcMap, const NodeMap>(arc_map, node_map);
3598 3595
    }
3599 3596

	
3600 3597
  };
3601 3598

	
3602 3599
  /// \brief Returns a (read-only) SplitNodes adaptor
3603 3600
  ///
3604 3601
  /// This function just returns a (read-only) \ref SplitNodes adaptor.
3605 3602
  /// \ingroup graph_adaptors
3606 3603
  /// \relates SplitNodes
3607 3604
  template<typename DGR>
3608 3605
  SplitNodes<DGR>
3609 3606
  splitNodes(const DGR& digraph) {
3610 3607
    return SplitNodes<DGR>(digraph);
3611 3608
  }
3612 3609

	
3613 3610
#undef LEMON_SCOPE_FIX
3614 3611

	
3615 3612
} //namespace lemon
3616 3613

	
3617 3614
#endif //LEMON_ADAPTORS_H
Ignore white space 6 line context
1 1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 2
 *
3 3
 * This file is a part of LEMON, a generic C++ optimization library.
4 4
 *
5 5
 * Copyright (C) 2003-2009
6 6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 8
 *
9 9
 * Permission to use, modify and distribute this software is granted
10 10
 * provided that this copyright notice appears in all copies. For
11 11
 * precise terms see the accompanying LICENSE file.
12 12
 *
13 13
 * This software is provided "AS IS" with no warranty of any kind,
14 14
 * express or implied, and with no claim as to its suitability for any
15 15
 * purpose.
16 16
 *
17 17
 */
18 18

	
19 19
///\ingroup graph_concepts
20 20
///\file
21 21
///\brief The concept of Undirected Graphs.
22 22

	
23 23
#ifndef LEMON_CONCEPTS_GRAPH_H
24 24
#define LEMON_CONCEPTS_GRAPH_H
25 25

	
26 26
#include <lemon/concepts/graph_components.h>
27 27
#include <lemon/core.h>
28 28

	
29 29
namespace lemon {
30 30
  namespace concepts {
31 31

	
32 32
    /// \ingroup graph_concepts
33 33
    ///
34 34
    /// \brief Class describing the concept of Undirected Graphs.
35 35
    ///
36 36
    /// This class describes the common interface of all Undirected
37 37
    /// Graphs.
38 38
    ///
39 39
    /// As all concept describing classes it provides only interface
40 40
    /// without any sensible implementation. So any algorithm for
41 41
    /// undirected graph should compile with this class, but it will not
42 42
    /// run properly, of course.
43 43
    ///
44 44
    /// The LEMON undirected graphs also fulfill the concept of
45 45
    /// directed graphs (\ref lemon::concepts::Digraph "Digraph
46 46
    /// Concept"). Each edges can be seen as two opposite
47 47
    /// directed arc and consequently the undirected graph can be
48 48
    /// seen as the direceted graph of these directed arcs. The
49 49
    /// Graph has the Edge inner class for the edges and
50 50
    /// the Arc type for the directed arcs. The Arc type is
51 51
    /// convertible to Edge or inherited from it so from a directed
52 52
    /// arc we can get the represented edge.
53 53
    ///
54 54
    /// In the sense of the LEMON each edge has a default
55 55
    /// direction (it should be in every computer implementation,
56 56
    /// because the order of edge's nodes defines an
57 57
    /// orientation). With the default orientation we can define that
58 58
    /// the directed arc is forward or backward directed. With the \c
59 59
    /// direction() and \c direct() function we can get the direction
60 60
    /// of the directed arc and we can direct an edge.
61 61
    ///
62 62
    /// The EdgeIt is an iterator for the edges. We can use
63 63
    /// the EdgeMap to map values for the edges. The InArcIt and
64 64
    /// OutArcIt iterates on the same edges but with opposite
65 65
    /// direction. The IncEdgeIt iterates also on the same edges
66 66
    /// as the OutArcIt and InArcIt but it is not convertible to Arc just
67 67
    /// to Edge.
68 68
    class Graph {
69 69
    public:
70 70
      /// \brief The undirected graph should be tagged by the
71 71
      /// UndirectedTag.
72 72
      ///
73 73
      /// The undirected graph should be tagged by the UndirectedTag. This
74 74
      /// tag helps the enable_if technics to make compile time
75 75
      /// specializations for undirected graphs.
76 76
      typedef True UndirectedTag;
77 77

	
78 78
      /// \brief The base type of node iterators,
79 79
      /// or in other words, the trivial node iterator.
80 80
      ///
81 81
      /// This is the base type of each node iterator,
82 82
      /// thus each kind of node iterator converts to this.
83 83
      /// More precisely each kind of node iterator should be inherited
84 84
      /// from the trivial node iterator.
85 85
      class Node {
86 86
      public:
87 87
        /// Default constructor
88 88

	
89 89
        /// @warning The default constructor sets the iterator
90 90
        /// to an undefined value.
91 91
        Node() { }
92 92
        /// Copy constructor.
93 93

	
94 94
        /// Copy constructor.
95 95
        ///
96 96
        Node(const Node&) { }
97 97

	
98 98
        /// Invalid constructor \& conversion.
99 99

	
100 100
        /// This constructor initializes the iterator to be invalid.
101 101
        /// \sa Invalid for more details.
102 102
        Node(Invalid) { }
103 103
        /// Equality operator
104 104

	
105 105
        /// Two iterators are equal if and only if they point to the
106 106
        /// same object or both are invalid.
107 107
        bool operator==(Node) const { return true; }
108 108

	
109 109
        /// Inequality operator
110 110

	
111 111
        /// \sa operator==(Node n)
112 112
        ///
113 113
        bool operator!=(Node) const { return true; }
114 114

	
115 115
        /// Artificial ordering operator.
116 116

	
117 117
        /// To allow the use of graph descriptors as key type in std::map or
118 118
        /// similar associative container we require this.
119 119
        ///
120 120
        /// \note This operator only have to define some strict ordering of
121 121
        /// the items; this order has nothing to do with the iteration
122 122
        /// ordering of the items.
123 123
        bool operator<(Node) const { return false; }
124 124

	
125 125
      };
126 126

	
127 127
      /// This iterator goes through each node.
128 128

	
129 129
      /// This iterator goes through each node.
130 130
      /// Its usage is quite simple, for example you can count the number
131 131
      /// of nodes in graph \c g of type \c Graph like this:
132 132
      ///\code
133 133
      /// int count=0;
134 134
      /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
135 135
      ///\endcode
136 136
      class NodeIt : public Node {
137 137
      public:
138 138
        /// Default constructor
139 139

	
140 140
        /// @warning The default constructor sets the iterator
141 141
        /// to an undefined value.
142 142
        NodeIt() { }
143 143
        /// Copy constructor.
144 144

	
145 145
        /// Copy constructor.
146 146
        ///
147 147
        NodeIt(const NodeIt& n) : Node(n) { }
148 148
        /// Invalid constructor \& conversion.
149 149

	
150 150
        /// Initialize the iterator to be invalid.
151 151
        /// \sa Invalid for more details.
152 152
        NodeIt(Invalid) { }
153 153
        /// Sets the iterator to the first node.
154 154

	
155 155
        /// Sets the iterator to the first node of \c g.
156 156
        ///
157 157
        NodeIt(const Graph&) { }
158 158
        /// Node -> NodeIt conversion.
159 159

	
160 160
        /// Sets the iterator to the node of \c the graph pointed by
161 161
        /// the trivial iterator.
162 162
        /// This feature necessitates that each time we
163 163
        /// iterate the arc-set, the iteration order is the same.
164 164
        NodeIt(const Graph&, const Node&) { }
165 165
        /// Next node.
166 166

	
167 167
        /// Assign the iterator to the next node.
168 168
        ///
169 169
        NodeIt& operator++() { return *this; }
170 170
      };
171 171

	
172 172

	
173 173
      /// The base type of the edge iterators.
174 174

	
175 175
      /// The base type of the edge iterators.
176 176
      ///
177 177
      class Edge {
178 178
      public:
179 179
        /// Default constructor
180 180

	
181 181
        /// @warning The default constructor sets the iterator
182 182
        /// to an undefined value.
183 183
        Edge() { }
184 184
        /// Copy constructor.
185 185

	
186 186
        /// Copy constructor.
187 187
        ///
188 188
        Edge(const Edge&) { }
189 189
        /// Initialize the iterator to be invalid.
190 190

	
191 191
        /// Initialize the iterator to be invalid.
192 192
        ///
193 193
        Edge(Invalid) { }
194 194
        /// Equality operator
195 195

	
196 196
        /// Two iterators are equal if and only if they point to the
197 197
        /// same object or both are invalid.
198 198
        bool operator==(Edge) const { return true; }
199 199
        /// Inequality operator
200 200

	
201 201
        /// \sa operator==(Edge n)
202 202
        ///
203 203
        bool operator!=(Edge) const { return true; }
204 204

	
205 205
        /// Artificial ordering operator.
206 206

	
207 207
        /// To allow the use of graph descriptors as key type in std::map or
208 208
        /// similar associative container we require this.
209 209
        ///
210 210
        /// \note This operator only have to define some strict ordering of
211 211
        /// the items; this order has nothing to do with the iteration
212 212
        /// ordering of the items.
213 213
        bool operator<(Edge) const { return false; }
214 214
      };
215 215

	
216 216
      /// This iterator goes through each edge.
217 217

	
218 218
      /// This iterator goes through each edge of a graph.
219 219
      /// Its usage is quite simple, for example you can count the number
220 220
      /// of edges in a graph \c g of type \c Graph as follows:
221 221
      ///\code
222 222
      /// int count=0;
223 223
      /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
224 224
      ///\endcode
225 225
      class EdgeIt : public Edge {
226 226
      public:
227 227
        /// Default constructor
228 228

	
229 229
        /// @warning The default constructor sets the iterator
230 230
        /// to an undefined value.
231 231
        EdgeIt() { }
232 232
        /// Copy constructor.
233 233

	
234 234
        /// Copy constructor.
235 235
        ///
236 236
        EdgeIt(const EdgeIt& e) : Edge(e) { }
237 237
        /// Initialize the iterator to be invalid.
238 238

	
239 239
        /// Initialize the iterator to be invalid.
240 240
        ///
241 241
        EdgeIt(Invalid) { }
242 242
        /// This constructor sets the iterator to the first edge.
243 243

	
244 244
        /// This constructor sets the iterator to the first edge.
245 245
        EdgeIt(const Graph&) { }
246 246
        /// Edge -> EdgeIt conversion
247 247

	
248 248
        /// Sets the iterator to the value of the trivial iterator.
249 249
        /// This feature necessitates that each time we
250 250
        /// iterate the edge-set, the iteration order is the
251 251
        /// same.
252 252
        EdgeIt(const Graph&, const Edge&) { }
253 253
        /// Next edge
254 254

	
255 255
        /// Assign the iterator to the next edge.
256 256
        EdgeIt& operator++() { return *this; }
257 257
      };
258 258

	
259 259
      /// \brief This iterator goes trough the incident undirected
260 260
      /// arcs of a node.
261 261
      ///
262 262
      /// This iterator goes trough the incident edges
263 263
      /// of a certain node of a graph. You should assume that the
264 264
      /// loop arcs will be iterated twice.
265 265
      ///
266 266
      /// Its usage is quite simple, for example you can compute the
267 267
      /// degree (i.e. count the number of incident arcs of a node \c n
268 268
      /// in graph \c g of type \c Graph as follows.
269 269
      ///
270 270
      ///\code
271 271
      /// int count=0;
272 272
      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
273 273
      ///\endcode
274 274
      class IncEdgeIt : public Edge {
275 275
      public:
276 276
        /// Default constructor
277 277

	
278 278
        /// @warning The default constructor sets the iterator
279 279
        /// to an undefined value.
280 280
        IncEdgeIt() { }
281 281
        /// Copy constructor.
282 282

	
283 283
        /// Copy constructor.
284 284
        ///
285 285
        IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
286 286
        /// Initialize the iterator to be invalid.
287 287

	
288 288
        /// Initialize the iterator to be invalid.
289 289
        ///
290 290
        IncEdgeIt(Invalid) { }
291 291
        /// This constructor sets the iterator to first incident arc.
292 292

	
293 293
        /// This constructor set the iterator to the first incident arc of
294 294
        /// the node.
295 295
        IncEdgeIt(const Graph&, const Node&) { }
296 296
        /// Edge -> IncEdgeIt conversion
297 297

	
298 298
        /// Sets the iterator to the value of the trivial iterator \c e.
299 299
        /// This feature necessitates that each time we
300 300
        /// iterate the arc-set, the iteration order is the same.
301 301
        IncEdgeIt(const Graph&, const Edge&) { }
302 302
        /// Next incident arc
303 303

	
304 304
        /// Assign the iterator to the next incident arc
305 305
        /// of the corresponding node.
306 306
        IncEdgeIt& operator++() { return *this; }
307 307
      };
308 308

	
309 309
      /// The directed arc type.
310 310

	
311 311
      /// The directed arc type. It can be converted to the
312 312
      /// edge or it should be inherited from the undirected
313
      /// arc.
314
      class Arc : public Edge {
313
      /// edge.
314
      class Arc {
315 315
      public:
316 316
        /// Default constructor
317 317

	
318 318
        /// @warning The default constructor sets the iterator
319 319
        /// to an undefined value.
320 320
        Arc() { }
321 321
        /// Copy constructor.
322 322

	
323 323
        /// Copy constructor.
324 324
        ///
325
        Arc(const Arc& e) : Edge(e) { }
325
        Arc(const Arc&) { }
326 326
        /// Initialize the iterator to be invalid.
327 327

	
328 328
        /// Initialize the iterator to be invalid.
329 329
        ///
330 330
        Arc(Invalid) { }
331 331
        /// Equality operator
332 332

	
333 333
        /// Two iterators are equal if and only if they point to the
334 334
        /// same object or both are invalid.
335 335
        bool operator==(Arc) const { return true; }
336 336
        /// Inequality operator
337 337

	
338 338
        /// \sa operator==(Arc n)
339 339
        ///
340 340
        bool operator!=(Arc) const { return true; }
341 341

	
342 342
        /// Artificial ordering operator.
343 343

	
344 344
        /// To allow the use of graph descriptors as key type in std::map or
345 345
        /// similar associative container we require this.
346 346
        ///
347 347
        /// \note This operator only have to define some strict ordering of
348 348
        /// the items; this order has nothing to do with the iteration
349 349
        /// ordering of the items.
350 350
        bool operator<(Arc) const { return false; }
351 351

	
352
        /// Converison to Edge
353
        operator Edge() const { return Edge(); }
352 354
      };
353 355
      /// This iterator goes through each directed arc.
354 356

	
355 357
      /// This iterator goes through each arc of a graph.
356 358
      /// Its usage is quite simple, for example you can count the number
357 359
      /// of arcs in a graph \c g of type \c Graph as follows:
358 360
      ///\code
359 361
      /// int count=0;
360 362
      /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;
361 363
      ///\endcode
362 364
      class ArcIt : public Arc {
363 365
      public:
364 366
        /// Default constructor
365 367

	
366 368
        /// @warning The default constructor sets the iterator
367 369
        /// to an undefined value.
368 370
        ArcIt() { }
369 371
        /// Copy constructor.
370 372

	
371 373
        /// Copy constructor.
372 374
        ///
373 375
        ArcIt(const ArcIt& e) : Arc(e) { }
374 376
        /// Initialize the iterator to be invalid.
375 377

	
376 378
        /// Initialize the iterator to be invalid.
377 379
        ///
378 380
        ArcIt(Invalid) { }
379 381
        /// This constructor sets the iterator to the first arc.
380 382

	
381 383
        /// This constructor sets the iterator to the first arc of \c g.
382 384
        ///@param g the graph
383 385
        ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
384 386
        /// Arc -> ArcIt conversion
385 387

	
386 388
        /// Sets the iterator to the value of the trivial iterator \c e.
387 389
        /// This feature necessitates that each time we
388 390
        /// iterate the arc-set, the iteration order is the same.
389 391
        ArcIt(const Graph&, const Arc&) { }
390 392
        ///Next arc
391 393

	
392 394
        /// Assign the iterator to the next arc.
393 395
        ArcIt& operator++() { return *this; }
394 396
      };
395 397

	
396 398
      /// This iterator goes trough the outgoing directed arcs of a node.
397 399

	
398 400
      /// This iterator goes trough the \e outgoing arcs of a certain node
399 401
      /// of a graph.
400 402
      /// Its usage is quite simple, for example you can count the number
401 403
      /// of outgoing arcs of a node \c n
402 404
      /// in graph \c g of type \c Graph as follows.
403 405
      ///\code
404 406
      /// int count=0;
405 407
      /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
406 408
      ///\endcode
407 409

	
408 410
      class OutArcIt : public Arc {
409 411
      public:
410 412
        /// Default constructor
411 413

	
412 414
        /// @warning The default constructor sets the iterator
413 415
        /// to an undefined value.
414 416
        OutArcIt() { }
415 417
        /// Copy constructor.
416 418

	
417 419
        /// Copy constructor.
418 420
        ///
419 421
        OutArcIt(const OutArcIt& e) : Arc(e) { }
420 422
        /// Initialize the iterator to be invalid.
421 423

	
422 424
        /// Initialize the iterator to be invalid.
423 425
        ///
424 426
        OutArcIt(Invalid) { }
425 427
        /// This constructor sets the iterator to the first outgoing arc.
426 428

	
427 429
        /// This constructor sets the iterator to the first outgoing arc of
428 430
        /// the node.
429 431
        ///@param n the node
430 432
        ///@param g the graph
431 433
        OutArcIt(const Graph& n, const Node& g) {
432 434
          ignore_unused_variable_warning(n);
433 435
          ignore_unused_variable_warning(g);
434 436
        }
435 437
        /// Arc -> OutArcIt conversion
436 438

	
437 439
        /// Sets the iterator to the value of the trivial iterator.
438 440
        /// This feature necessitates that each time we
439 441
        /// iterate the arc-set, the iteration order is the same.
440 442
        OutArcIt(const Graph&, const Arc&) { }
441 443
        ///Next outgoing arc
442 444

	
443 445
        /// Assign the iterator to the next
444 446
        /// outgoing arc of the corresponding node.
445 447
        OutArcIt& operator++() { return *this; }
446 448
      };
447 449

	
448 450
      /// This iterator goes trough the incoming directed arcs of a node.
449 451

	
450 452
      /// This iterator goes trough the \e incoming arcs of a certain node
451 453
      /// of a graph.
452 454
      /// Its usage is quite simple, for example you can count the number
453 455
      /// of outgoing arcs of a node \c n
454 456
      /// in graph \c g of type \c Graph as follows.
455 457
      ///\code
456 458
      /// int count=0;
457 459
      /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
458 460
      ///\endcode
459 461

	
460 462
      class InArcIt : public Arc {
461 463
      public:
462 464
        /// Default constructor
463 465

	
464 466
        /// @warning The default constructor sets the iterator
465 467
        /// to an undefined value.
466 468
        InArcIt() { }
467 469
        /// Copy constructor.
468 470

	
469 471
        /// Copy constructor.
470 472
        ///
471 473
        InArcIt(const InArcIt& e) : Arc(e) { }
472 474
        /// Initialize the iterator to be invalid.
473 475

	
474 476
        /// Initialize the iterator to be invalid.
475 477
        ///
476 478
        InArcIt(Invalid) { }
477 479
        /// This constructor sets the iterator to first incoming arc.
478 480

	
479 481
        /// This constructor set the iterator to the first incoming arc of
480 482
        /// the node.
481 483
        ///@param n the node
482 484
        ///@param g the graph
483 485
        InArcIt(const Graph& g, const Node& n) {
484 486
          ignore_unused_variable_warning(n);
485 487
          ignore_unused_variable_warning(g);
486 488
        }
487 489
        /// Arc -> InArcIt conversion
488 490

	
489 491
        /// Sets the iterator to the value of the trivial iterator \c e.
490 492
        /// This feature necessitates that each time we
491 493
        /// iterate the arc-set, the iteration order is the same.
492 494
        InArcIt(const Graph&, const Arc&) { }
493 495
        /// Next incoming arc
494 496

	
495 497
        /// Assign the iterator to the next inarc of the corresponding node.
496 498
        ///
497 499
        InArcIt& operator++() { return *this; }
498 500
      };
499 501

	
500 502
      /// \brief Reference map of the nodes to type \c T.
501 503
      ///
502 504
      /// Reference map of the nodes to type \c T.
503 505
      template<class T>
504 506
      class NodeMap : public ReferenceMap<Node, T, T&, const T&>
505 507
      {
506 508
      public:
507 509

	
508 510
        ///\e
509 511
        NodeMap(const Graph&) { }
510 512
        ///\e
511 513
        NodeMap(const Graph&, T) { }
512 514

	
513 515
      private:
514 516
        ///Copy constructor
515 517
        NodeMap(const NodeMap& nm) :
516 518
          ReferenceMap<Node, T, T&, const T&>(nm) { }
517 519
        ///Assignment operator
518 520
        template <typename CMap>
519 521
        NodeMap& operator=(const CMap&) {
520 522
          checkConcept<ReadMap<Node, T>, CMap>();
521 523
          return *this;
522 524
        }
523 525
      };
524 526

	
525 527
      /// \brief Reference map of the arcs to type \c T.
526 528
      ///
527 529
      /// Reference map of the arcs to type \c T.
528 530
      template<class T>
529 531
      class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
530 532
      {
531 533
      public:
532 534

	
533 535
        ///\e
534 536
        ArcMap(const Graph&) { }
535 537
        ///\e
536 538
        ArcMap(const Graph&, T) { }
537 539
      private:
538 540
        ///Copy constructor
539 541
        ArcMap(const ArcMap& em) :
540 542
          ReferenceMap<Arc, T, T&, const T&>(em) { }
541 543
        ///Assignment operator
542 544
        template <typename CMap>
543 545
        ArcMap& operator=(const CMap&) {
544 546
          checkConcept<ReadMap<Arc, T>, CMap>();
545 547
          return *this;
546 548
        }
547 549
      };
548 550

	
549 551
      /// Reference map of the edges to type \c T.
550 552

	
551 553
      /// Reference map of the edges to type \c T.
552 554
      template<class T>
553 555
      class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
554 556
      {
555 557
      public:
556 558

	
557 559
        ///\e
558 560
        EdgeMap(const Graph&) { }
559 561
        ///\e
560 562
        EdgeMap(const Graph&, T) { }
561 563
      private:
562 564
        ///Copy constructor
563 565
        EdgeMap(const EdgeMap& em) :
564 566
          ReferenceMap<Edge, T, T&, const T&>(em) {}
565 567
        ///Assignment operator
566 568
        template <typename CMap>
567 569
        EdgeMap& operator=(const CMap&) {
568 570
          checkConcept<ReadMap<Edge, T>, CMap>();
569 571
          return *this;
570 572
        }
571 573
      };
572 574

	
573 575
      /// \brief Direct the given edge.
574 576
      ///
575 577
      /// Direct the given edge. The returned arc source
576 578
      /// will be the given node.
577 579
      Arc direct(const Edge&, const Node&) const {
578 580
        return INVALID;
579 581
      }
580 582

	
581 583
      /// \brief Direct the given edge.
582 584
      ///
583 585
      /// Direct the given edge. The returned arc
584 586
      /// represents the given edge and the direction comes
585 587
      /// from the bool parameter. The source of the edge and
586 588
      /// the directed arc is the same when the given bool is true.
587 589
      Arc direct(const Edge&, bool) const {
588 590
        return INVALID;
589 591
      }
590 592

	
591 593
      /// \brief Returns true if the arc has default orientation.
592 594
      ///
593 595
      /// Returns whether the given directed arc is same orientation as
594 596
      /// the corresponding edge's default orientation.
595 597
      bool direction(Arc) const { return true; }
596 598

	
597 599
      /// \brief Returns the opposite directed arc.
598 600
      ///
599 601
      /// Returns the opposite directed arc.
600 602
      Arc oppositeArc(Arc) const { return INVALID; }
601 603

	
602 604
      /// \brief Opposite node on an arc
603 605
      ///
604 606
      /// \return The opposite of the given node on the given edge.
605 607
      Node oppositeNode(Node, Edge) const { return INVALID; }
606 608

	
607 609
      /// \brief First node of the edge.
608 610
      ///
609 611
      /// \return The first node of the given edge.
610 612
      ///
611 613
      /// Naturally edges don't have direction and thus
612 614
      /// don't have source and target node. However we use \c u() and \c v()
613 615
      /// methods to query the two nodes of the arc. The direction of the
614 616
      /// arc which arises this way is called the inherent direction of the
615 617
      /// edge, and is used to define the "default" direction
616 618
      /// of the directed versions of the arcs.
617 619
      /// \sa v()
618 620
      /// \sa direction()
619 621
      Node u(Edge) const { return INVALID; }
620 622

	
621 623
      /// \brief Second node of the edge.
622 624
      ///
623 625
      /// \return The second node of the given edge.
624 626
      ///
625 627
      /// Naturally edges don't have direction and thus
626 628
      /// don't have source and target node. However we use \c u() and \c v()
627 629
      /// methods to query the two nodes of the arc. The direction of the
628 630
      /// arc which arises this way is called the inherent direction of the
629 631
      /// edge, and is used to define the "default" direction
630 632
      /// of the directed versions of the arcs.
631 633
      /// \sa u()
632 634
      /// \sa direction()
633 635
      Node v(Edge) const { return INVALID; }
634 636

	
635 637
      /// \brief Source node of the directed arc.
636 638
      Node source(Arc) const { return INVALID; }
637 639

	
638 640
      /// \brief Target node of the directed arc.
639 641
      Node target(Arc) const { return INVALID; }
640 642

	
641 643
      /// \brief Returns the id of the node.
642 644
      int id(Node) const { return -1; }
643 645

	
644 646
      /// \brief Returns the id of the edge.
645 647
      int id(Edge) const { return -1; }
646 648

	
647 649
      /// \brief Returns the id of the arc.
648 650
      int id(Arc) const { return -1; }
649 651

	
650 652
      /// \brief Returns the node with the given id.
651 653
      ///
652 654
      /// \pre The argument should be a valid node id in the graph.
653 655
      Node nodeFromId(int) const { return INVALID; }
654 656

	
655 657
      /// \brief Returns the edge with the given id.
656 658
      ///
657 659
      /// \pre The argument should be a valid edge id in the graph.
658 660
      Edge edgeFromId(int) const { return INVALID; }
659 661

	
660 662
      /// \brief Returns the arc with the given id.
661 663
      ///
662 664
      /// \pre The argument should be a valid arc id in the graph.
663 665
      Arc arcFromId(int) const { return INVALID; }
664 666

	
665 667
      /// \brief Returns an upper bound on the node IDs.
666 668
      int maxNodeId() const { return -1; }
667 669

	
668 670
      /// \brief Returns an upper bound on the edge IDs.
669 671
      int maxEdgeId() const { return -1; }
670 672

	
671 673
      /// \brief Returns an upper bound on the arc IDs.
672 674
      int maxArcId() const { return -1; }
673 675

	
674 676
      void first(Node&) const {}
675 677
      void next(Node&) const {}
676 678

	
677 679
      void first(Edge&) const {}
678 680
      void next(Edge&) const {}
679 681

	
680 682
      void first(Arc&) const {}
681 683
      void next(Arc&) const {}
682 684

	
683 685
      void firstOut(Arc&, Node) const {}
684 686
      void nextOut(Arc&) const {}
685 687

	
686 688
      void firstIn(Arc&, Node) const {}
687 689
      void nextIn(Arc&) const {}
688 690

	
689 691
      void firstInc(Edge &, bool &, const Node &) const {}
690 692
      void nextInc(Edge &, bool &) const {}
691 693

	
692 694
      // The second parameter is dummy.
693 695
      Node fromId(int, Node) const { return INVALID; }
694 696
      // The second parameter is dummy.
695 697
      Edge fromId(int, Edge) const { return INVALID; }
696 698
      // The second parameter is dummy.
697 699
      Arc fromId(int, Arc) const { return INVALID; }
698 700

	
699 701
      // Dummy parameter.
700 702
      int maxId(Node) const { return -1; }
701 703
      // Dummy parameter.
702 704
      int maxId(Edge) const { return -1; }
703 705
      // Dummy parameter.
704 706
      int maxId(Arc) const { return -1; }
705 707

	
706 708
      /// \brief Base node of the iterator
707 709
      ///
708 710
      /// Returns the base node (the source in this case) of the iterator
709 711
      Node baseNode(OutArcIt e) const {
710 712
        return source(e);
711 713
      }
712 714
      /// \brief Running node of the iterator
713 715
      ///
714 716
      /// Returns the running node (the target in this case) of the
715 717
      /// iterator
716 718
      Node runningNode(OutArcIt e) const {
717 719
        return target(e);
718 720
      }
719 721

	
720 722
      /// \brief Base node of the iterator
721 723
      ///
722 724
      /// Returns the base node (the target in this case) of the iterator
723 725
      Node baseNode(InArcIt e) const {
724 726
        return target(e);
725 727
      }
726 728
      /// \brief Running node of the iterator
727 729
      ///
728 730
      /// Returns the running node (the source in this case) of the
729 731
      /// iterator
730 732
      Node runningNode(InArcIt e) const {
731 733
        return source(e);
732 734
      }
733 735

	
734 736
      /// \brief Base node of the iterator
735 737
      ///
736 738
      /// Returns the base node of the iterator
737 739
      Node baseNode(IncEdgeIt) const {
738 740
        return INVALID;
739 741
      }
740 742

	
741 743
      /// \brief Running node of the iterator
742 744
      ///
743 745
      /// Returns the running node of the iterator
744 746
      Node runningNode(IncEdgeIt) const {
745 747
        return INVALID;
746 748
      }
747 749

	
748 750
      template <typename _Graph>
749 751
      struct Constraints {
750 752
        void constraints() {
751 753
          checkConcept<BaseGraphComponent, _Graph>();
752 754
          checkConcept<IterableGraphComponent<>, _Graph>();
753 755
          checkConcept<IDableGraphComponent<>, _Graph>();
754 756
          checkConcept<MappableGraphComponent<>, _Graph>();
755 757
        }
756 758
      };
757 759

	
758 760
    };
759 761

	
760 762
  }
761 763

	
762 764
}
763 765

	
764 766
#endif
Ignore white space 6 line context
1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2
 *
3
 * This file is a part of LEMON, a generic C++ optimization library.
4
 *
5
 * Copyright (C) 2003-2009
6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8
 *
9
 * Permission to use, modify and distribute this software is granted
10
 * provided that this copyright notice appears in all copies. For
11
 * precise terms see the accompanying LICENSE file.
12
 *
13
 * This software is provided "AS IS" with no warranty of any kind,
14
 * express or implied, and with no claim as to its suitability for any
15
 * purpose.
16
 *
17
 */
18

	
19
#ifndef LEMON_BITS_BASE_EXTENDER_H
20
#define LEMON_BITS_BASE_EXTENDER_H
21

	
22
#include <lemon/core.h>
23
#include <lemon/error.h>
24

	
25
#include <lemon/bits/map_extender.h>
26
#include <lemon/bits/default_map.h>
27

	
28
#include <lemon/concept_check.h>
29
#include <lemon/concepts/maps.h>
30

	
31
//\ingroup digraphbits
32
//\file
33
//\brief Extenders for the graph types
34
namespace lemon {
35

	
36
  // \ingroup digraphbits
37
  //
38
  // \brief BaseDigraph to BaseGraph extender
39
  template <typename Base>
40
  class UndirDigraphExtender : public Base {
41
    typedef Base Parent;
42

	
43
  public:
44

	
45
    typedef typename Parent::Arc Edge;
46
    typedef typename Parent::Node Node;
47

	
48
    typedef True UndirectedTag;
49

	
50
    class Arc : public Edge {
51
      friend class UndirDigraphExtender;
52

	
53
    protected:
54
      bool forward;
55

	
56
      Arc(const Edge &ue, bool _forward) :
57
        Edge(ue), forward(_forward) {}
58

	
59
    public:
60
      Arc() {}
61

	
62
      // Invalid arc constructor
63
      Arc(Invalid i) : Edge(i), forward(true) {}
64

	
65
      bool operator==(const Arc &that) const {
66
        return forward==that.forward && Edge(*this)==Edge(that);
67
      }
68
      bool operator!=(const Arc &that) const {
69
        return forward!=that.forward || Edge(*this)!=Edge(that);
70
      }
71
      bool operator<(const Arc &that) const {
72
        return forward<that.forward ||
73
          (!(that.forward<forward) && Edge(*this)<Edge(that));
74
      }
75
    };
76

	
77
    // First node of the edge
78
    Node u(const Edge &e) const {
79
      return Parent::source(e);
80
    }
81

	
82
    // Source of the given arc
83
    Node source(const Arc &e) const {
84
      return e.forward ? Parent::source(e) : Parent::target(e);
85
    }
86

	
87
    // Second node of the edge
88
    Node v(const Edge &e) const {
89
      return Parent::target(e);
90
    }
91

	
92
    // Target of the given arc
93
    Node target(const Arc &e) const {
94
      return e.forward ? Parent::target(e) : Parent::source(e);
95
    }
96

	
97
    // \brief Directed arc from an edge.
98
    //
99
    // Returns a directed arc corresponding to the specified edge.
100
    // If the given bool is true, the first node of the given edge and
101
    // the source node of the returned arc are the same.
102
    static Arc direct(const Edge &e, bool d) {
103
      return Arc(e, d);
104
    }
105

	
106
    // Returns whether the given directed arc has the same orientation
107
    // as the corresponding edge.
108
    static bool direction(const Arc &a) { return a.forward; }
109

	
110
    using Parent::first;
111
    using Parent::next;
112

	
113
    void first(Arc &e) const {
114
      Parent::first(e);
115
      e.forward=true;
116
    }
117

	
118
    void next(Arc &e) const {
119
      if( e.forward ) {
120
        e.forward = false;
121
      }
122
      else {
123
        Parent::next(e);
124
        e.forward = true;
125
      }
126
    }
127

	
128
    void firstOut(Arc &e, const Node &n) const {
129
      Parent::firstIn(e,n);
130
      if( Edge(e) != INVALID ) {
131
        e.forward = false;
132
      }
133
      else {
134
        Parent::firstOut(e,n);
135
        e.forward = true;
136
      }
137
    }
138
    void nextOut(Arc &e) const {
139
      if( ! e.forward ) {
140
        Node n = Parent::target(e);
141
        Parent::nextIn(e);
142
        if( Edge(e) == INVALID ) {
143
          Parent::firstOut(e, n);
144
          e.forward = true;
145
        }
146
      }
147
      else {
148
        Parent::nextOut(e);
149
      }
150
    }
151

	
152
    void firstIn(Arc &e, const Node &n) const {
153
      Parent::firstOut(e,n);
154
      if( Edge(e) != INVALID ) {
155
        e.forward = false;
156
      }
157
      else {
158
        Parent::firstIn(e,n);
159
        e.forward = true;
160
      }
161
    }
162
    void nextIn(Arc &e) const {
163
      if( ! e.forward ) {
164
        Node n = Parent::source(e);
165
        Parent::nextOut(e);
166
        if( Edge(e) == INVALID ) {
167
          Parent::firstIn(e, n);
168
          e.forward = true;
169
        }
170
      }
171
      else {
172
        Parent::nextIn(e);
173
      }
174
    }
175

	
176
    void firstInc(Edge &e, bool &d, const Node &n) const {
177
      d = true;
178
      Parent::firstOut(e, n);
179
      if (e != INVALID) return;
180
      d = false;
181
      Parent::firstIn(e, n);
182
    }
183

	
184
    void nextInc(Edge &e, bool &d) const {
185
      if (d) {
186
        Node s = Parent::source(e);
187
        Parent::nextOut(e);
188
        if (e != INVALID) return;
189
        d = false;
190
        Parent::firstIn(e, s);
191
      } else {
192
        Parent::nextIn(e);
193
      }
194
    }
195

	
196
    Node nodeFromId(int ix) const {
197
      return Parent::nodeFromId(ix);
198
    }
199

	
200
    Arc arcFromId(int ix) const {
201
      return direct(Parent::arcFromId(ix >> 1), bool(ix & 1));
202
    }
203

	
204
    Edge edgeFromId(int ix) const {
205
      return Parent::arcFromId(ix);
206
    }
207

	
208
    int id(const Node &n) const {
209
      return Parent::id(n);
210
    }
211

	
212
    int id(const Edge &e) const {
213
      return Parent::id(e);
214
    }
215

	
216
    int id(const Arc &e) const {
217
      return 2 * Parent::id(e) + int(e.forward);
218
    }
219

	
220
    int maxNodeId() const {
221
      return Parent::maxNodeId();
222
    }
223

	
224
    int maxArcId() const {
225
      return 2 * Parent::maxArcId() + 1;
226
    }
227

	
228
    int maxEdgeId() const {
229
      return Parent::maxArcId();
230
    }
231

	
232
    int arcNum() const {
233
      return 2 * Parent::arcNum();
234
    }
235

	
236
    int edgeNum() const {
237
      return Parent::arcNum();
238
    }
239

	
240
    Arc findArc(Node s, Node t, Arc p = INVALID) const {
241
      if (p == INVALID) {
242
        Edge arc = Parent::findArc(s, t);
243
        if (arc != INVALID) return direct(arc, true);
244
        arc = Parent::findArc(t, s);
245
        if (arc != INVALID) return direct(arc, false);
246
      } else if (direction(p)) {
247
        Edge arc = Parent::findArc(s, t, p);
248
        if (arc != INVALID) return direct(arc, true);
249
        arc = Parent::findArc(t, s);
250
        if (arc != INVALID) return direct(arc, false);
251
      } else {
252
        Edge arc = Parent::findArc(t, s, p);
253
        if (arc != INVALID) return direct(arc, false);
254
      }
255
      return INVALID;
256
    }
257

	
258
    Edge findEdge(Node s, Node t, Edge p = INVALID) const {
259
      if (s != t) {
260
        if (p == INVALID) {
261
          Edge arc = Parent::findArc(s, t);
262
          if (arc != INVALID) return arc;
263
          arc = Parent::findArc(t, s);
264
          if (arc != INVALID) return arc;
265
        } else if (Parent::s(p) == s) {
266
          Edge arc = Parent::findArc(s, t, p);
267
          if (arc != INVALID) return arc;
268
          arc = Parent::findArc(t, s);
269
          if (arc != INVALID) return arc;
270
        } else {
271
          Edge arc = Parent::findArc(t, s, p);
272
          if (arc != INVALID) return arc;
273
        }
274
      } else {
275
        return Parent::findArc(s, t, p);
276
      }
277
      return INVALID;
278
    }
279
  };
280

	
281
  template <typename Base>
282
  class BidirBpGraphExtender : public Base {
283
    typedef Base Parent;
284

	
285
  public:
286
    typedef BidirBpGraphExtender Digraph;
287

	
288
    typedef typename Parent::Node Node;
289
    typedef typename Parent::Edge Edge;
290

	
291

	
292
    using Parent::first;
293
    using Parent::next;
294

	
295
    using Parent::id;
296

	
297
    class Red : public Node {
298
      friend class BidirBpGraphExtender;
299
    public:
300
      Red() {}
301
      Red(const Node& node) : Node(node) {
302
        LEMON_DEBUG(Parent::red(node) || node == INVALID,
303
                    typename Parent::NodeSetError());
304
      }
305
      Red& operator=(const Node& node) {
306
        LEMON_DEBUG(Parent::red(node) || node == INVALID,
307
                    typename Parent::NodeSetError());
308
        Node::operator=(node);
309
        return *this;
310
      }
311
      Red(Invalid) : Node(INVALID) {}
312
      Red& operator=(Invalid) {
313
        Node::operator=(INVALID);
314
        return *this;
315
      }
316
    };
317

	
318
    void first(Red& node) const {
319
      Parent::firstRed(static_cast<Node&>(node));
320
    }
321
    void next(Red& node) const {
322
      Parent::nextRed(static_cast<Node&>(node));
323
    }
324

	
325
    int id(const Red& node) const {
326
      return Parent::redId(node);
327
    }
328

	
329
    class Blue : public Node {
330
      friend class BidirBpGraphExtender;
331
    public:
332
      Blue() {}
333
      Blue(const Node& node) : Node(node) {
334
        LEMON_DEBUG(Parent::blue(node) || node == INVALID,
335
                    typename Parent::NodeSetError());
336
      }
337
      Blue& operator=(const Node& node) {
338
        LEMON_DEBUG(Parent::blue(node) || node == INVALID,
339
                    typename Parent::NodeSetError());
340
        Node::operator=(node);
341
        return *this;
342
      }
343
      Blue(Invalid) : Node(INVALID) {}
344
      Blue& operator=(Invalid) {
345
        Node::operator=(INVALID);
346
        return *this;
347
      }
348
    };
349

	
350
    void first(Blue& node) const {
351
      Parent::firstBlue(static_cast<Node&>(node));
352
    }
353
    void next(Blue& node) const {
354
      Parent::nextBlue(static_cast<Node&>(node));
355
    }
356

	
357
    int id(const Blue& node) const {
358
      return Parent::redId(node);
359
    }
360

	
361
    Node source(const Edge& arc) const {
362
      return red(arc);
363
    }
364
    Node target(const Edge& arc) const {
365
      return blue(arc);
366
    }
367

	
368
    void firstInc(Edge& arc, bool& dir, const Node& node) const {
369
      if (Parent::red(node)) {
370
        Parent::firstFromRed(arc, node);
371
        dir = true;
372
      } else {
373
        Parent::firstFromBlue(arc, node);
374
        dir = static_cast<Edge&>(arc) == INVALID;
375
      }
376
    }
377
    void nextInc(Edge& arc, bool& dir) const {
378
      if (dir) {
379
        Parent::nextFromRed(arc);
380
      } else {
381
        Parent::nextFromBlue(arc);
382
        if (arc == INVALID) dir = true;
383
      }
384
    }
385

	
386
    class Arc : public Edge {
387
      friend class BidirBpGraphExtender;
388
    protected:
389
      bool forward;
390

	
391
      Arc(const Edge& arc, bool _forward)
392
        : Edge(arc), forward(_forward) {}
393

	
394
    public:
395
      Arc() {}
396
      Arc (Invalid) : Edge(INVALID), forward(true) {}
397
      bool operator==(const Arc& i) const {
398
        return Edge::operator==(i) && forward == i.forward;
399
      }
400
      bool operator!=(const Arc& i) const {
401
        return Edge::operator!=(i) || forward != i.forward;
402
      }
403
      bool operator<(const Arc& i) const {
404
        return Edge::operator<(i) ||
405
          (!(i.forward<forward) && Edge(*this)<Edge(i));
406
      }
407
    };
408

	
409
    void first(Arc& arc) const {
410
      Parent::first(static_cast<Edge&>(arc));
411
      arc.forward = true;
412
    }
413

	
414
    void next(Arc& arc) const {
415
      if (!arc.forward) {
416
        Parent::next(static_cast<Edge&>(arc));
417
      }
418
      arc.forward = !arc.forward;
419
    }
420

	
421
    void firstOut(Arc& arc, const Node& node) const {
422
      if (Parent::red(node)) {
423
        Parent::firstFromRed(arc, node);
424
        arc.forward = true;
425
      } else {
426
        Parent::firstFromBlue(arc, node);
427
        arc.forward = static_cast<Edge&>(arc) == INVALID;
428
      }
429
    }
430
    void nextOut(Arc& arc) const {
431
      if (arc.forward) {
432
        Parent::nextFromRed(arc);
433
      } else {
434
        Parent::nextFromBlue(arc);
435
        arc.forward = static_cast<Edge&>(arc) == INVALID;
436
      }
437
    }
438

	
439
    void firstIn(Arc& arc, const Node& node) const {
440
      if (Parent::blue(node)) {
441
        Parent::firstFromBlue(arc, node);
442
        arc.forward = true;
443
      } else {
444
        Parent::firstFromRed(arc, node);
445
        arc.forward = static_cast<Edge&>(arc) == INVALID;
446
      }
447
    }
448
    void nextIn(Arc& arc) const {
449
      if (arc.forward) {
450
        Parent::nextFromBlue(arc);
451
      } else {
452
        Parent::nextFromRed(arc);
453
        arc.forward = static_cast<Edge&>(arc) == INVALID;
454
      }
455
    }
456

	
457
    Node source(const Arc& arc) const {
458
      return arc.forward ? Parent::red(arc) : Parent::blue(arc);
459
    }
460
    Node target(const Arc& arc) const {
461
      return arc.forward ? Parent::blue(arc) : Parent::red(arc);
462
    }
463

	
464
    int id(const Arc& arc) const {
465
      return (Parent::id(static_cast<const Edge&>(arc)) << 1) +
466
        (arc.forward ? 0 : 1);
467
    }
468
    Arc arcFromId(int ix) const {
469
      return Arc(Parent::fromEdgeId(ix >> 1), (ix & 1) == 0);
470
    }
471
    int maxArcId() const {
472
      return (Parent::maxEdgeId() << 1) + 1;
473
    }
474

	
475
    bool direction(const Arc& arc) const {
476
      return arc.forward;
477
    }
478

	
479
    Arc direct(const Edge& arc, bool dir) const {
480
      return Arc(arc, dir);
481
    }
482

	
483
    int arcNum() const {
484
      return 2 * Parent::edgeNum();
485
    }
486

	
487
    int edgeNum() const {
488
      return Parent::edgeNum();
489
    }
490

	
491

	
492
  };
493
}
494

	
495
#endif

Changeset was too big and was cut off... Show full diff

0 comments (0 inline)