1.1 --- a/lemon/Makefile.am Thu Jan 24 16:49:10 2008 +0000
1.2 +++ b/lemon/Makefile.am Thu Jan 24 17:36:45 2008 +0000
1.3 @@ -18,7 +18,6 @@
1.4 lemon/dim2.h \
1.5 lemon/maps.h \
1.6 lemon/path.h \
1.7 - lemon/path_utils.h \
1.8 lemon/random.h \
1.9 lemon/list_graph.h \
1.10 lemon/tolerance.h
2.1 --- a/lemon/path.h Thu Jan 24 16:49:10 2008 +0000
2.2 +++ b/lemon/path.h Thu Jan 24 17:36:45 2008 +0000
2.3 @@ -27,7 +27,6 @@
2.4 #include <vector>
2.5 #include <algorithm>
2.6
2.7 -#include <lemon/path_utils.h>
2.8 #include <lemon/error.h>
2.9 #include <lemon/bits/invalid.h>
2.10
2.11 @@ -896,6 +895,182 @@
2.12 Arc* arcs;
2.13 };
2.14
2.15 + ///////////////////////////////////////////////////////////////////////
2.16 + // Additional utilities
2.17 + ///////////////////////////////////////////////////////////////////////
2.18 +
2.19 + namespace _path_bits {
2.20 +
2.21 + template <typename Path, typename Enable = void>
2.22 + struct RevTagIndicator {
2.23 + static const bool value = false;
2.24 + };
2.25 +
2.26 + template <typename Digraph>
2.27 + struct RevTagIndicator<
2.28 + Digraph,
2.29 + typename enable_if<typename Digraph::RevTag, void>::type
2.30 + > {
2.31 + static const bool value = true;
2.32 + };
2.33 +
2.34 + template <typename Target, typename Source,
2.35 + typename BuildEnable = void, typename RevEnable = void>
2.36 + struct PathCopySelector {
2.37 + static void copy(Target& target, const Source& source) {
2.38 + target.clear();
2.39 + for (typename Source::ArcIt it(source); it != INVALID; ++it) {
2.40 + target.addBack(it);
2.41 + }
2.42 + }
2.43 + };
2.44 +
2.45 + template <typename Target, typename Source, typename BuildEnable>
2.46 + struct PathCopySelector<
2.47 + Target, Source, BuildEnable,
2.48 + typename enable_if<typename Source::RevPathTag, void>::type> {
2.49 + static void copy(Target& target, const Source& source) {
2.50 + target.clear();
2.51 + for (typename Source::RevArcIt it(source); it != INVALID; ++it) {
2.52 + target.addFront(it);
2.53 + }
2.54 + }
2.55 + };
2.56 +
2.57 + template <typename Target, typename Source, typename RevEnable>
2.58 + struct PathCopySelector<
2.59 + Target, Source,
2.60 + typename enable_if<typename Target::BuildTag, void>::type, RevEnable> {
2.61 + static void copy(Target& target, const Source& source) {
2.62 + target.clear();
2.63 + target.build(source);
2.64 + }
2.65 + };
2.66 +
2.67 + template <typename Target, typename Source>
2.68 + struct PathCopySelector<
2.69 + Target, Source,
2.70 + typename enable_if<typename Target::BuildTag, void>::type,
2.71 + typename enable_if<typename Source::RevPathTag, void>::type> {
2.72 + static void copy(Target& target, const Source& source) {
2.73 + target.clear();
2.74 + target.buildRev(source);
2.75 + }
2.76 + };
2.77 +
2.78 + }
2.79 +
2.80 +
2.81 + /// \brief Make a copy of a path.
2.82 + ///
2.83 + /// This function makes a copy of a path.
2.84 + template <typename Target, typename Source>
2.85 + void copyPath(Target& target, const Source& source) {
2.86 + checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>();
2.87 + _path_bits::PathCopySelector<Target, Source>::copy(target, source);
2.88 + }
2.89 +
2.90 + /// \brief Check the consistency of a path.
2.91 + ///
2.92 + /// This function checks that the target of each arc is the same
2.93 + /// as the source of the next one.
2.94 + ///
2.95 + template <typename Digraph, typename Path>
2.96 + bool checkPath(const Digraph& digraph, const Path& path) {
2.97 + typename Path::ArcIt it(path);
2.98 + if (it == INVALID) return true;
2.99 + typename Digraph::Node node = digraph.target(it);
2.100 + ++it;
2.101 + while (it != INVALID) {
2.102 + if (digraph.source(it) != node) return false;
2.103 + node = digraph.target(it);
2.104 + ++it;
2.105 + }
2.106 + return true;
2.107 + }
2.108 +
2.109 + /// \brief The source of a path
2.110 + ///
2.111 + /// This function returns the source of the given path.
2.112 + template <typename Digraph, typename Path>
2.113 + typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
2.114 + return digraph.source(path.front());
2.115 + }
2.116 +
2.117 + /// \brief The target of a path
2.118 + ///
2.119 + /// This function returns the target of the given path.
2.120 + template <typename Digraph, typename Path>
2.121 + typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
2.122 + return digraph.target(path.back());
2.123 + }
2.124 +
2.125 + /// \brief Class which helps to iterate through the nodes of a path
2.126 + ///
2.127 + /// In a sense, the path can be treated as a list of arcs. The
2.128 + /// lemon path type stores only this list. As a consequence, it
2.129 + /// cannot enumerate the nodes in the path and the zero length paths
2.130 + /// cannot have a source node.
2.131 + ///
2.132 + /// This class implements the node iterator of a path structure. To
2.133 + /// provide this feature, the underlying digraph should be passed to
2.134 + /// the constructor of the iterator.
2.135 + template <typename Path>
2.136 + class PathNodeIt {
2.137 + private:
2.138 + const typename Path::Digraph *_digraph;
2.139 + typename Path::ArcIt _it;
2.140 + typename Path::Digraph::Node _nd;
2.141 +
2.142 + public:
2.143 +
2.144 + typedef typename Path::Digraph Digraph;
2.145 + typedef typename Digraph::Node Node;
2.146 +
2.147 + /// Default constructor
2.148 + PathNodeIt() {}
2.149 + /// Invalid constructor
2.150 + PathNodeIt(Invalid)
2.151 + : _digraph(0), _it(INVALID), _nd(INVALID) {}
2.152 + /// Constructor
2.153 + PathNodeIt(const Digraph& digraph, const Path& path)
2.154 + : _digraph(&digraph), _it(path) {
2.155 + _nd = (_it != INVALID ? _digraph->source(_it) : INVALID);
2.156 + }
2.157 + /// Constructor
2.158 + PathNodeIt(const Digraph& digraph, const Path& path, const Node& src)
2.159 + : _digraph(&digraph), _it(path), _nd(src) {}
2.160 +
2.161 + ///Conversion to Digraph::Node
2.162 + operator Node() const {
2.163 + return _nd;
2.164 + }
2.165 +
2.166 + /// Next node
2.167 + PathNodeIt& operator++() {
2.168 + if (_it == INVALID) _nd = INVALID;
2.169 + else {
2.170 + _nd = _digraph->target(_it);
2.171 + ++_it;
2.172 + }
2.173 + return *this;
2.174 + }
2.175 +
2.176 + /// Comparison operator
2.177 + bool operator==(const PathNodeIt& n) const {
2.178 + return _it == n._it && _nd == n._nd;
2.179 + }
2.180 + /// Comparison operator
2.181 + bool operator!=(const PathNodeIt& n) const {
2.182 + return _it != n._it || _nd != n._nd;
2.183 + }
2.184 + /// Comparison operator
2.185 + bool operator<(const PathNodeIt& n) const {
2.186 + return (_it < n._it && _nd != INVALID);
2.187 + }
2.188 +
2.189 + };
2.190 +
2.191 ///@}
2.192
2.193 } // namespace lemon
3.1 --- a/lemon/path_utils.h Thu Jan 24 16:49:10 2008 +0000
3.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
3.3 @@ -1,205 +0,0 @@
3.4 -/* -*- C++ -*-
3.5 - *
3.6 - * This file is a part of LEMON, a generic C++ optimization library
3.7 - *
3.8 - * Copyright (C) 2003-2008
3.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.11 - *
3.12 - * Permission to use, modify and distribute this software is granted
3.13 - * provided that this copyright notice appears in all copies. For
3.14 - * precise terms see the accompanying LICENSE file.
3.15 - *
3.16 - * This software is provided "AS IS" with no warranty of any kind,
3.17 - * express or implied, and with no claim as to its suitability for any
3.18 - * purpose.
3.19 - *
3.20 - */
3.21 -
3.22 -///\ingroup paths
3.23 -///\file
3.24 -///\brief Classes for representing paths in digraphs.
3.25 -///
3.26 -
3.27 -#ifndef LEMON_PATH_UTILS_H
3.28 -#define LEMON_PATH_UTILS_H
3.29 -
3.30 -#include <lemon/concepts/path.h>
3.31 -
3.32 -namespace lemon {
3.33 -
3.34 - namespace _path_bits {
3.35 -
3.36 - template <typename Path, typename Enable = void>
3.37 - struct RevTagIndicator {
3.38 - static const bool value = false;
3.39 - };
3.40 -
3.41 - template <typename Digraph>
3.42 - struct RevTagIndicator<
3.43 - Digraph,
3.44 - typename enable_if<typename Digraph::RevTag, void>::type
3.45 - > {
3.46 - static const bool value = true;
3.47 - };
3.48 -
3.49 - template <typename Target, typename Source,
3.50 - typename BuildEnable = void, typename RevEnable = void>
3.51 - struct PathCopySelector {
3.52 - static void copy(Target& target, const Source& source) {
3.53 - target.clear();
3.54 - for (typename Source::ArcIt it(source); it != INVALID; ++it) {
3.55 - target.addBack(it);
3.56 - }
3.57 - }
3.58 - };
3.59 -
3.60 - template <typename Target, typename Source, typename BuildEnable>
3.61 - struct PathCopySelector<
3.62 - Target, Source, BuildEnable,
3.63 - typename enable_if<typename Source::RevPathTag, void>::type> {
3.64 - static void copy(Target& target, const Source& source) {
3.65 - target.clear();
3.66 - for (typename Source::RevArcIt it(source); it != INVALID; ++it) {
3.67 - target.addFront(it);
3.68 - }
3.69 - }
3.70 - };
3.71 -
3.72 - template <typename Target, typename Source, typename RevEnable>
3.73 - struct PathCopySelector<
3.74 - Target, Source,
3.75 - typename enable_if<typename Target::BuildTag, void>::type, RevEnable> {
3.76 - static void copy(Target& target, const Source& source) {
3.77 - target.clear();
3.78 - target.build(source);
3.79 - }
3.80 - };
3.81 -
3.82 - template <typename Target, typename Source>
3.83 - struct PathCopySelector<
3.84 - Target, Source,
3.85 - typename enable_if<typename Target::BuildTag, void>::type,
3.86 - typename enable_if<typename Source::RevPathTag, void>::type> {
3.87 - static void copy(Target& target, const Source& source) {
3.88 - target.clear();
3.89 - target.buildRev(source);
3.90 - }
3.91 - };
3.92 -
3.93 - }
3.94 -
3.95 -
3.96 - /// \brief Make a copy of a path.
3.97 - ///
3.98 - /// This function makes a copy of a path.
3.99 - template <typename Target, typename Source>
3.100 - void copyPath(Target& target, const Source& source) {
3.101 - checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>();
3.102 - _path_bits::PathCopySelector<Target, Source>::copy(target, source);
3.103 - }
3.104 -
3.105 - /// \brief Check the consistency of a path.
3.106 - ///
3.107 - /// This function checks that the target of each arc is the same
3.108 - /// as the source of the next one.
3.109 - ///
3.110 - template <typename Digraph, typename Path>
3.111 - bool checkPath(const Digraph& digraph, const Path& path) {
3.112 - typename Path::ArcIt it(path);
3.113 - if (it == INVALID) return true;
3.114 - typename Digraph::Node node = digraph.target(it);
3.115 - ++it;
3.116 - while (it != INVALID) {
3.117 - if (digraph.source(it) != node) return false;
3.118 - node = digraph.target(it);
3.119 - ++it;
3.120 - }
3.121 - return true;
3.122 - }
3.123 -
3.124 - /// \brief The source of a path
3.125 - ///
3.126 - /// This function returns the source of the given path.
3.127 - template <typename Digraph, typename Path>
3.128 - typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
3.129 - return digraph.source(path.front());
3.130 - }
3.131 -
3.132 - /// \brief The target of a path
3.133 - ///
3.134 - /// This function returns the target of the given path.
3.135 - template <typename Digraph, typename Path>
3.136 - typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
3.137 - return digraph.target(path.back());
3.138 - }
3.139 -
3.140 - /// \brief Class which helps to iterate through the nodes of a path
3.141 - ///
3.142 - /// In a sense, the path can be treated as a list of arcs. The
3.143 - /// lemon path type stores only this list. As a consequence, it
3.144 - /// cannot enumerate the nodes in the path and the zero length paths
3.145 - /// cannot have a source node.
3.146 - ///
3.147 - /// This class implements the node iterator of a path structure. To
3.148 - /// provide this feature, the underlying digraph should be passed to
3.149 - /// the constructor of the iterator.
3.150 - template <typename Path>
3.151 - class PathNodeIt {
3.152 - private:
3.153 - const typename Path::Digraph *_digraph;
3.154 - typename Path::ArcIt _it;
3.155 - typename Path::Digraph::Node _nd;
3.156 -
3.157 - public:
3.158 -
3.159 - typedef typename Path::Digraph Digraph;
3.160 - typedef typename Digraph::Node Node;
3.161 -
3.162 - /// Default constructor
3.163 - PathNodeIt() {}
3.164 - /// Invalid constructor
3.165 - PathNodeIt(Invalid)
3.166 - : _digraph(0), _it(INVALID), _nd(INVALID) {}
3.167 - /// Constructor
3.168 - PathNodeIt(const Digraph& digraph, const Path& path)
3.169 - : _digraph(&digraph), _it(path) {
3.170 - _nd = (_it != INVALID ? _digraph->source(_it) : INVALID);
3.171 - }
3.172 - /// Constructor
3.173 - PathNodeIt(const Digraph& digraph, const Path& path, const Node& src)
3.174 - : _digraph(&digraph), _it(path), _nd(src) {}
3.175 -
3.176 - ///Conversion to Digraph::Node
3.177 - operator Node() const {
3.178 - return _nd;
3.179 - }
3.180 -
3.181 - /// Next node
3.182 - PathNodeIt& operator++() {
3.183 - if (_it == INVALID) _nd = INVALID;
3.184 - else {
3.185 - _nd = _digraph->target(_it);
3.186 - ++_it;
3.187 - }
3.188 - return *this;
3.189 - }
3.190 -
3.191 - /// Comparison operator
3.192 - bool operator==(const PathNodeIt& n) const {
3.193 - return _it == n._it && _nd == n._nd;
3.194 - }
3.195 - /// Comparison operator
3.196 - bool operator!=(const PathNodeIt& n) const {
3.197 - return _it != n._it || _nd != n._nd;
3.198 - }
3.199 - /// Comparison operator
3.200 - bool operator<(const PathNodeIt& n) const {
3.201 - return (_it < n._it && _nd != INVALID);
3.202 - }
3.203 -
3.204 - };
3.205 -
3.206 -}
3.207 -
3.208 -#endif