1.1 --- a/lemon/concept/path.h Tue Oct 24 16:49:41 2006 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,294 +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-2006
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 concept
1.23 -///\file
1.24 -///\brief Classes for representing paths in graphs.
1.25 -///
1.26 -///\todo Iterators have obsolete style
1.27 -
1.28 -#ifndef LEMON_CONCEPT_PATH_H
1.29 -#define LEMON_CONCEPT_PATH_H
1.30 -
1.31 -#include <lemon/bits/invalid.h>
1.32 -#include <lemon/concept_check.h>
1.33 -
1.34 -namespace lemon {
1.35 - namespace concept {
1.36 - /// \addtogroup concept
1.37 - /// @{
1.38 -
1.39 -
1.40 - //! \brief A skeleton structure for representing directed paths in a graph.
1.41 - //!
1.42 - //! A skeleton structure for representing directed paths in a graph.
1.43 - //! \param _Graph The graph type in which the path is.
1.44 - //!
1.45 - //! In a sense, the path can be treated as a graph, for it has \c NodeIt
1.46 - //! and \c EdgeIt with the same usage. These types converts to the \c Node
1.47 - //! and \c Edge of the original graph.
1.48 - template<typename _Graph>
1.49 - class Path {
1.50 - public:
1.51 -
1.52 - /// Type of the underlying graph.
1.53 - typedef _Graph Graph;
1.54 - /// Edge type of the underlying graph.
1.55 - typedef typename Graph::Edge Edge;
1.56 - /// Node type of the underlying graph.
1.57 - typedef typename Graph::Node Node;
1.58 -
1.59 - class NodeIt;
1.60 - class EdgeIt;
1.61 -
1.62 - /// \param _g The graph in which the path is.
1.63 - ///
1.64 - Path(const Graph &_g) {
1.65 - ignore_unused_variable_warning(_g);
1.66 - }
1.67 -
1.68 - /// Length of the path ie. the number of edges in the path.
1.69 - int length() const {return 0;}
1.70 -
1.71 - /// Returns whether the path is empty.
1.72 - bool empty() const { return true;}
1.73 -
1.74 - /// Resets the path to an empty path.
1.75 - void clear() {}
1.76 -
1.77 - /// \brief Starting point of the path.
1.78 - ///
1.79 - /// Starting point of the path.
1.80 - /// Returns INVALID if the path is empty.
1.81 - Node target() const {return INVALID;}
1.82 - /// \brief End point of the path.
1.83 - ///
1.84 - /// End point of the path.
1.85 - /// Returns INVALID if the path is empty.
1.86 - Node source() const {return INVALID;}
1.87 -
1.88 - /// \brief The target of an edge.
1.89 - ///
1.90 - /// Returns node iterator pointing to the target node of the
1.91 - /// given edge iterator.
1.92 - NodeIt target(const EdgeIt&) const {return INVALID;}
1.93 -
1.94 - /// \brief The source of an edge.
1.95 - ///
1.96 - /// Returns node iterator pointing to the source node of the
1.97 - /// given edge iterator.
1.98 - NodeIt source(const EdgeIt&) const {return INVALID;}
1.99 -
1.100 - /// \brief Iterator class to iterate on the nodes of the paths
1.101 - ///
1.102 - /// This class is used to iterate on the nodes of the paths
1.103 - ///
1.104 - /// Of course it converts to Graph::Node.
1.105 - class NodeIt {
1.106 - public:
1.107 - /// Default constructor
1.108 - NodeIt() {}
1.109 - /// Invalid constructor
1.110 - NodeIt(Invalid) {}
1.111 - /// Constructor with starting point
1.112 - NodeIt(const Path &) {}
1.113 -
1.114 - ///Conversion to Graph::Node
1.115 - operator Node() const { return INVALID; }
1.116 - /// Next node
1.117 - NodeIt& operator++() {return *this;}
1.118 -
1.119 - /// Comparison operator
1.120 - bool operator==(const NodeIt&) const {return true;}
1.121 - /// Comparison operator
1.122 - bool operator!=(const NodeIt&) const {return true;}
1.123 - /// Comparison operator
1.124 - bool operator<(const NodeIt&) const {return false;}
1.125 -
1.126 - };
1.127 -
1.128 - /// \brief Iterator class to iterate on the edges of the paths
1.129 - ///
1.130 - /// This class is used to iterate on the edges of the paths
1.131 - ///
1.132 - /// Of course it converts to Graph::Edge
1.133 - class EdgeIt {
1.134 - public:
1.135 - /// Default constructor
1.136 - EdgeIt() {}
1.137 - /// Invalid constructor
1.138 - EdgeIt(Invalid) {}
1.139 - /// Constructor with starting point
1.140 - EdgeIt(const Path &) {}
1.141 -
1.142 - operator Edge() const { return INVALID; }
1.143 -
1.144 - /// Next edge
1.145 - EdgeIt& operator++() {return *this;}
1.146 -
1.147 - /// Comparison operator
1.148 - bool operator==(const EdgeIt&) const {return true;}
1.149 - /// Comparison operator
1.150 - bool operator!=(const EdgeIt&) const {return true;}
1.151 - /// Comparison operator
1.152 - bool operator<(const EdgeIt&) const {return false;}
1.153 -
1.154 - };
1.155 -
1.156 -
1.157 - friend class Builder;
1.158 -
1.159 - /// \brief Class to build paths
1.160 - ///
1.161 - /// This class is used to fill a path with edges.
1.162 - ///
1.163 - /// You can push new edges to the front and to the back of the path in
1.164 - /// arbitrary order then you should commit these changes to the graph.
1.165 - ///
1.166 - /// While the builder is active (after the first modifying
1.167 - /// operation and until the call of \ref commit()) the
1.168 - /// underlining Path is in a "transitional" state (operations on
1.169 - /// it have undefined result).
1.170 - class Builder {
1.171 - public:
1.172 -
1.173 - /// Constructor
1.174 -
1.175 - /// Constructor
1.176 - /// \param _path the path you want to fill in.
1.177 - ///
1.178 -
1.179 - Builder(Path &_path) { ignore_unused_variable_warning(_path); }
1.180 -
1.181 - /// Sets the starting node of the path.
1.182 -
1.183 - /// Sets the starting node of the path. Edge added to the path
1.184 - /// afterwards have to be incident to this node.
1.185 - /// You \em must start building an empty path with these functions.
1.186 - /// (And you \em must \em not use it later).
1.187 - /// \sa pushFront()
1.188 - /// \sa pushBack()
1.189 - void setStartNode(const Node &) {}
1.190 -
1.191 - ///Push a new edge to the front of the path
1.192 -
1.193 - ///Push a new edge to the front of the path.
1.194 - ///If the path is empty, you \em must call \ref setStartNode() before
1.195 - ///the first use of \ref pushFront().
1.196 - void pushFront(const Edge&) {}
1.197 -
1.198 - ///Push a new edge to the back of the path
1.199 -
1.200 - ///Push a new edge to the back of the path.
1.201 - ///If the path is empty, you \em must call \ref setStartNode() before
1.202 - ///the first use of \ref pushBack().
1.203 - void pushBack(const Edge&) {}
1.204 -
1.205 - ///Commit the changes to the path.
1.206 -
1.207 - ///Commit the changes to the path.
1.208 - ///
1.209 - void commit() {}
1.210 -
1.211 - ///Reserve (front) storage for the builder in advance.
1.212 -
1.213 - ///If you know a reasonable upper bound on the number of the edges
1.214 - ///to add to the front of the path,
1.215 - ///using this function you may speed up the building.
1.216 - void reserveFront(size_t) {}
1.217 - ///Reserve (back) storage for the builder in advance.
1.218 -
1.219 - ///If you know a reasonable upper bound on the number of the edges
1.220 - ///to add to the back of the path,
1.221 - ///using this function you may speed up the building.
1.222 - void reserveBack(size_t) {}
1.223 - };
1.224 -
1.225 - template <typename _Path>
1.226 - struct Constraints {
1.227 - void constraints() {
1.228 - typedef typename _Path::Node Node;
1.229 - typedef typename _Path::NodeIt NodeIt;
1.230 - typedef typename Graph::Node GraphNode;
1.231 -
1.232 - typedef typename _Path::Edge Edge;
1.233 - typedef typename _Path::EdgeIt EdgeIt;
1.234 - typedef typename Graph::Edge GraphEdge;
1.235 -
1.236 - typedef typename _Path::Builder Builder;
1.237 -
1.238 - path = _Path(graph);
1.239 -
1.240 - bool b = cpath.empty();
1.241 - int l = cpath.length();
1.242 -
1.243 - Node gn;
1.244 - Edge ge;
1.245 - gn = cpath.source();
1.246 - gn = cpath.target();
1.247 -
1.248 - NodeIt nit;
1.249 - EdgeIt eit(INVALID);
1.250 - nit = path.source(eit);
1.251 - nit = path.target(eit);
1.252 -
1.253 - nit = NodeIt();
1.254 - nit = NodeIt(cpath);
1.255 - nit = INVALID;
1.256 - gn = nit;
1.257 - ++nit;
1.258 - b = nit == nit;
1.259 - b = nit != nit;
1.260 - b = nit < nit;
1.261 -
1.262 - eit = EdgeIt();
1.263 - eit = EdgeIt(cpath);
1.264 - eit = INVALID;
1.265 - ge = eit;
1.266 - ++eit;
1.267 - b = eit == eit;
1.268 - b = eit != eit;
1.269 - b = eit < eit;
1.270 -
1.271 - size_t st = 0;
1.272 -
1.273 - Builder builder(path);
1.274 - builder.setStartNode(gn);
1.275 - builder.pushFront(ge);
1.276 - builder.pushBack(ge);
1.277 - builder.commit();
1.278 - builder.reserveFront(st);
1.279 - builder.reserveBack(st);
1.280 -
1.281 - ignore_unused_variable_warning(l);
1.282 - ignore_unused_variable_warning(b);
1.283 - }
1.284 -
1.285 - const Graph& graph;
1.286 - const _Path& cpath;
1.287 - _Path& path;
1.288 - };
1.289 -
1.290 - };
1.291 -
1.292 - ///@}
1.293 - }
1.294 -
1.295 -} // namespace lemon
1.296 -
1.297 -#endif // LEMON_CONCEPT_PATH_H