3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
21 ///\brief Classes for representing paths in digraphs.
24 #ifndef LEMON_PATH_UTILS_H
25 #define LEMON_PATH_UTILS_H
27 #include <lemon/concepts/path.h>
31 namespace _path_bits {
33 template <typename Path, typename Enable = void>
34 struct RevTagIndicator {
35 static const bool value = false;
38 template <typename Digraph>
39 struct RevTagIndicator<
41 typename enable_if<typename Digraph::RevTag, void>::type
43 static const bool value = true;
46 template <typename Target, typename Source,
47 typename BuildEnable = void, typename RevEnable = void>
48 struct PathCopySelector {
49 static void copy(Target& target, const Source& source) {
51 for (typename Source::ArcIt it(source); it != INVALID; ++it) {
57 template <typename Target, typename Source, typename BuildEnable>
58 struct PathCopySelector<
59 Target, Source, BuildEnable,
60 typename enable_if<typename Source::RevPathTag, void>::type> {
61 static void copy(Target& target, const Source& source) {
63 for (typename Source::RevArcIt it(source); it != INVALID; ++it) {
69 template <typename Target, typename Source, typename RevEnable>
70 struct PathCopySelector<
72 typename enable_if<typename Target::BuildTag, void>::type, RevEnable> {
73 static void copy(Target& target, const Source& source) {
79 template <typename Target, typename Source>
80 struct PathCopySelector<
82 typename enable_if<typename Target::BuildTag, void>::type,
83 typename enable_if<typename Source::RevPathTag, void>::type> {
84 static void copy(Target& target, const Source& source) {
86 target.buildRev(source);
93 /// \brief Make of copy of a path.
95 /// Make of copy of a path.
96 template <typename Target, typename Source>
97 void copyPath(Target& target, const Source& source) {
98 checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>();
99 _path_bits::PathCopySelector<Target, Source>::copy(target, source);
102 /// \brief Checks the path's consistency.
104 /// Checks that each arc's target is the next's source.
106 template <typename Digraph, typename Path>
107 bool checkPath(const Digraph& digraph, const Path& path) {
108 typename Path::ArcIt it(path);
109 if (it == INVALID) return true;
110 typename Digraph::Node node = digraph.target(it);
112 while (it != INVALID) {
113 if (digraph.source(it) != node) return false;
114 node = digraph.target(it);
120 /// \brief Gives back the source of the path
122 /// Gives back the source of the path.
123 template <typename Digraph, typename Path>
124 typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
125 return digraph.source(path.front());
128 /// \brief Gives back the target of the path
130 /// Gives back the target of the path.
131 template <typename Digraph, typename Path>
132 typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
133 return digraph.target(path.back());
136 /// \brief Class which helps to iterate the nodes of a path
138 /// In a sense, the path can be treated as a list of arcs. The
139 /// lemon path type stores just this list. As a consequence it
140 /// cannot enumerate the nodes in the path and the zero length paths
141 /// cannot store the node.
143 /// This class implements the node iterator of a path structure. To
144 /// provide this feature, the underlying digraph should be given to
145 /// the constructor of the iterator.
146 template <typename Path>
149 const typename Path::Digraph *_digraph;
150 typename Path::ArcIt _it;
151 typename Path::Digraph::Node _nd;
155 typedef typename Path::Digraph Digraph;
156 typedef typename Digraph::Node Node;
158 /// Default constructor
160 /// Invalid constructor
162 : _digraph(0), _it(INVALID), _nd(INVALID) {}
164 PathNodeIt(const Digraph& digraph, const Path& path)
165 : _digraph(&digraph), _it(path) {
166 _nd = (_it != INVALID ? _digraph->source(_it) : INVALID);
169 PathNodeIt(const Digraph& digraph, const Path& path, const Node& src)
170 : _digraph(&digraph), _it(path), _nd(src) {}
172 ///Conversion to Digraph::Node
173 operator Node() const {
178 PathNodeIt& operator++() {
179 if (_it == INVALID) _nd = INVALID;
181 _nd = _digraph->target(_it);
187 /// Comparison operator
188 bool operator==(const PathNodeIt& n) const {
189 return _it == n._it && _nd == n._nd;
191 /// Comparison operator
192 bool operator!=(const PathNodeIt& n) const {
193 return _it != n._it || _nd != n._nd;
195 /// Comparison operator
196 bool operator<(const PathNodeIt& n) const {
197 return (_it < n._it && _nd != INVALID);