1.1 --- a/lemon/path_utils.h Thu Jan 24 16:49:10 2008 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,205 +0,0 @@
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 a copy of a path.
1.97 - ///
1.98 - /// This function makes a 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 Check the consistency of a path.
1.106 - ///
1.107 - /// This function checks that the target of each arc is the same
1.108 - /// as the source of the next one.
1.109 - ///
1.110 - template <typename Digraph, typename Path>
1.111 - bool checkPath(const Digraph& digraph, const Path& path) {
1.112 - typename Path::ArcIt it(path);
1.113 - if (it == INVALID) return true;
1.114 - typename Digraph::Node node = digraph.target(it);
1.115 - ++it;
1.116 - while (it != INVALID) {
1.117 - if (digraph.source(it) != node) return false;
1.118 - node = digraph.target(it);
1.119 - ++it;
1.120 - }
1.121 - return true;
1.122 - }
1.123 -
1.124 - /// \brief The source of a path
1.125 - ///
1.126 - /// This function returns the source of the given path.
1.127 - template <typename Digraph, typename Path>
1.128 - typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
1.129 - return digraph.source(path.front());
1.130 - }
1.131 -
1.132 - /// \brief The target of a path
1.133 - ///
1.134 - /// This function returns the target of the given path.
1.135 - template <typename Digraph, typename Path>
1.136 - typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
1.137 - return digraph.target(path.back());
1.138 - }
1.139 -
1.140 - /// \brief Class which helps to iterate through the nodes of a path
1.141 - ///
1.142 - /// In a sense, the path can be treated as a list of arcs. The
1.143 - /// lemon path type stores only this list. As a consequence, it
1.144 - /// cannot enumerate the nodes in the path and the zero length paths
1.145 - /// cannot have a source node.
1.146 - ///
1.147 - /// This class implements the node iterator of a path structure. To
1.148 - /// provide this feature, the underlying digraph should be passed to
1.149 - /// the constructor of the iterator.
1.150 - template <typename Path>
1.151 - class PathNodeIt {
1.152 - private:
1.153 - const typename Path::Digraph *_digraph;
1.154 - typename Path::ArcIt _it;
1.155 - typename Path::Digraph::Node _nd;
1.156 -
1.157 - public:
1.158 -
1.159 - typedef typename Path::Digraph Digraph;
1.160 - typedef typename Digraph::Node Node;
1.161 -
1.162 - /// Default constructor
1.163 - PathNodeIt() {}
1.164 - /// Invalid constructor
1.165 - PathNodeIt(Invalid)
1.166 - : _digraph(0), _it(INVALID), _nd(INVALID) {}
1.167 - /// Constructor
1.168 - PathNodeIt(const Digraph& digraph, const Path& path)
1.169 - : _digraph(&digraph), _it(path) {
1.170 - _nd = (_it != INVALID ? _digraph->source(_it) : INVALID);
1.171 - }
1.172 - /// Constructor
1.173 - PathNodeIt(const Digraph& digraph, const Path& path, const Node& src)
1.174 - : _digraph(&digraph), _it(path), _nd(src) {}
1.175 -
1.176 - ///Conversion to Digraph::Node
1.177 - operator Node() const {
1.178 - return _nd;
1.179 - }
1.180 -
1.181 - /// Next node
1.182 - PathNodeIt& operator++() {
1.183 - if (_it == INVALID) _nd = INVALID;
1.184 - else {
1.185 - _nd = _digraph->target(_it);
1.186 - ++_it;
1.187 - }
1.188 - return *this;
1.189 - }
1.190 -
1.191 - /// Comparison operator
1.192 - bool operator==(const PathNodeIt& n) const {
1.193 - return _it == n._it && _nd == n._nd;
1.194 - }
1.195 - /// Comparison operator
1.196 - bool operator!=(const PathNodeIt& n) const {
1.197 - return _it != n._it || _nd != n._nd;
1.198 - }
1.199 - /// Comparison operator
1.200 - bool operator<(const PathNodeIt& n) const {
1.201 - return (_it < n._it && _nd != INVALID);
1.202 - }
1.203 -
1.204 - };
1.205 -
1.206 -}
1.207 -
1.208 -#endif