1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/path_utils.h Thu Jan 24 11:31:19 2008 +0000
1.3 @@ -0,0 +1,204 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2008
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +///\ingroup paths
1.23 +///\file
1.24 +///\brief Classes for representing paths in digraphs.
1.25 +///
1.26 +
1.27 +#ifndef LEMON_PATH_UTILS_H
1.28 +#define LEMON_PATH_UTILS_H
1.29 +
1.30 +#include <lemon/concepts/path.h>
1.31 +
1.32 +namespace lemon {
1.33 +
1.34 + namespace _path_bits {
1.35 +
1.36 + template <typename Path, typename Enable = void>
1.37 + struct RevTagIndicator {
1.38 + static const bool value = false;
1.39 + };
1.40 +
1.41 + template <typename Digraph>
1.42 + struct RevTagIndicator<
1.43 + Digraph,
1.44 + typename enable_if<typename Digraph::RevTag, void>::type
1.45 + > {
1.46 + static const bool value = true;
1.47 + };
1.48 +
1.49 + template <typename Target, typename Source,
1.50 + typename BuildEnable = void, typename RevEnable = void>
1.51 + struct PathCopySelector {
1.52 + static void copy(Target& target, const Source& source) {
1.53 + target.clear();
1.54 + for (typename Source::ArcIt it(source); it != INVALID; ++it) {
1.55 + target.addBack(it);
1.56 + }
1.57 + }
1.58 + };
1.59 +
1.60 + template <typename Target, typename Source, typename BuildEnable>
1.61 + struct PathCopySelector<
1.62 + Target, Source, BuildEnable,
1.63 + typename enable_if<typename Source::RevPathTag, void>::type> {
1.64 + static void copy(Target& target, const Source& source) {
1.65 + target.clear();
1.66 + for (typename Source::RevArcIt it(source); it != INVALID; ++it) {
1.67 + target.addFront(it);
1.68 + }
1.69 + }
1.70 + };
1.71 +
1.72 + template <typename Target, typename Source, typename RevEnable>
1.73 + struct PathCopySelector<
1.74 + Target, Source,
1.75 + typename enable_if<typename Target::BuildTag, void>::type, RevEnable> {
1.76 + static void copy(Target& target, const Source& source) {
1.77 + target.clear();
1.78 + target.build(source);
1.79 + }
1.80 + };
1.81 +
1.82 + template <typename Target, typename Source>
1.83 + struct PathCopySelector<
1.84 + Target, Source,
1.85 + typename enable_if<typename Target::BuildTag, void>::type,
1.86 + typename enable_if<typename Source::RevPathTag, void>::type> {
1.87 + static void copy(Target& target, const Source& source) {
1.88 + target.clear();
1.89 + target.buildRev(source);
1.90 + }
1.91 + };
1.92 +
1.93 + }
1.94 +
1.95 +
1.96 + /// \brief Make of copy of a path.
1.97 + ///
1.98 + /// Make of copy of a path.
1.99 + template <typename Target, typename Source>
1.100 + void copyPath(Target& target, const Source& source) {
1.101 + checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>();
1.102 + _path_bits::PathCopySelector<Target, Source>::copy(target, source);
1.103 + }
1.104 +
1.105 + /// \brief Checks the path's consistency.
1.106 + ///
1.107 + /// Checks that each arc's target is the next's source.
1.108 + ///
1.109 + template <typename Digraph, typename Path>
1.110 + bool checkPath(const Digraph& digraph, const Path& path) {
1.111 + typename Path::ArcIt it(path);
1.112 + if (it == INVALID) return true;
1.113 + typename Digraph::Node node = digraph.target(it);
1.114 + ++it;
1.115 + while (it != INVALID) {
1.116 + if (digraph.source(it) != node) return false;
1.117 + node = digraph.target(it);
1.118 + ++it;
1.119 + }
1.120 + return true;
1.121 + }
1.122 +
1.123 + /// \brief Gives back the source of the path
1.124 + ///
1.125 + /// Gives back the source of the path.
1.126 + template <typename Digraph, typename Path>
1.127 + typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
1.128 + return digraph.source(path.front());
1.129 + }
1.130 +
1.131 + /// \brief Gives back the target of the path
1.132 + ///
1.133 + /// Gives back the target of the path.
1.134 + template <typename Digraph, typename Path>
1.135 + typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
1.136 + return digraph.target(path.back());
1.137 + }
1.138 +
1.139 + /// \brief Class which helps to iterate the nodes of a path
1.140 + ///
1.141 + /// In a sense, the path can be treated as a list of arcs. The
1.142 + /// lemon path type stores just this list. As a consequence it
1.143 + /// cannot enumerate the nodes in the path and the zero length paths
1.144 + /// cannot store the node.
1.145 + ///
1.146 + /// This class implements the node iterator of a path structure. To
1.147 + /// provide this feature, the underlying digraph should be given to
1.148 + /// the constructor of the iterator.
1.149 + template <typename Path>
1.150 + class PathNodeIt {
1.151 + private:
1.152 + const typename Path::Digraph *_digraph;
1.153 + typename Path::ArcIt _it;
1.154 + typename Path::Digraph::Node _nd;
1.155 +
1.156 + public:
1.157 +
1.158 + typedef typename Path::Digraph Digraph;
1.159 + typedef typename Digraph::Node Node;
1.160 +
1.161 + /// Default constructor
1.162 + PathNodeIt() {}
1.163 + /// Invalid constructor
1.164 + PathNodeIt(Invalid)
1.165 + : _digraph(0), _it(INVALID), _nd(INVALID) {}
1.166 + /// Constructor
1.167 + PathNodeIt(const Digraph& digraph, const Path& path)
1.168 + : _digraph(&digraph), _it(path) {
1.169 + _nd = (_it != INVALID ? _digraph->source(_it) : INVALID);
1.170 + }
1.171 + /// Constructor
1.172 + PathNodeIt(const Digraph& digraph, const Path& path, const Node& src)
1.173 + : _digraph(&digraph), _it(path), _nd(src) {}
1.174 +
1.175 + ///Conversion to Digraph::Node
1.176 + operator Node() const {
1.177 + return _nd;
1.178 + }
1.179 +
1.180 + /// Next node
1.181 + PathNodeIt& operator++() {
1.182 + if (_it == INVALID) _nd = INVALID;
1.183 + else {
1.184 + _nd = _digraph->target(_it);
1.185 + ++_it;
1.186 + }
1.187 + return *this;
1.188 + }
1.189 +
1.190 + /// Comparison operator
1.191 + bool operator==(const PathNodeIt& n) const {
1.192 + return _it == n._it && _nd == n._nd;
1.193 + }
1.194 + /// Comparison operator
1.195 + bool operator!=(const PathNodeIt& n) const {
1.196 + return _it != n._it || _nd != n._nd;
1.197 + }
1.198 + /// Comparison operator
1.199 + bool operator<(const PathNodeIt& n) const {
1.200 + return (_it < n._it && _nd != INVALID);
1.201 + }
1.202 +
1.203 + };
1.204 +
1.205 +}
1.206 +
1.207 +#endif