1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/concept/path.h Mon May 23 04:48:14 2005 +0000
1.3 @@ -0,0 +1,236 @@
1.4 +/* -*- C++ -*-
1.5 + * lemon/concept/path.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +///\ingroup concept
1.21 +///\file
1.22 +///\brief Classes for representing paths in graphs.
1.23 +///
1.24 +///\todo Iterators have obsolete style
1.25 +
1.26 +#ifndef LEMON_CONCEPT_PATH_H
1.27 +#define LEMON_CONCEPT_PATH_H
1.28 +
1.29 +#include <lemon/invalid.h>
1.30 +
1.31 +namespace lemon {
1.32 + namespace concept {
1.33 + /// \addtogroup concept
1.34 + /// @{
1.35 +
1.36 +
1.37 + //! \brief A skeleton structure for representing directed paths in a graph.
1.38 + //!
1.39 + //! A skeleton structure for representing directed paths in a graph.
1.40 + //! \param GR The graph type in which the path is.
1.41 + //!
1.42 + //! In a sense, the path can be treated as a graph, for it has \c NodeIt
1.43 + //! and \c EdgeIt with the same usage. These types converts to the \c Node
1.44 + //! and \c Edge of the original graph.
1.45 + template<typename GR>
1.46 + class Path {
1.47 + public:
1.48 +
1.49 + /// Type of the underlying graph.
1.50 + typedef /*typename*/ GR Graph;
1.51 + /// Edge type of the underlying graph.
1.52 + typedef typename Graph::Edge GraphEdge;
1.53 + /// Node type of the underlying graph.
1.54 + typedef typename Graph::Node GraphNode;
1.55 + class NodeIt;
1.56 + class EdgeIt;
1.57 +
1.58 + /// \param _G The graph in which the path is.
1.59 + ///
1.60 + Path(const Graph &) {}
1.61 +
1.62 + /// Length of the path.
1.63 + int length() const {return 0;}
1.64 + /// Returns whether the path is empty.
1.65 + bool empty() const { return true;}
1.66 +
1.67 + /// Resets the path to an empty path.
1.68 + void clear() {}
1.69 +
1.70 + /// \brief Starting point of the path.
1.71 + ///
1.72 + /// Starting point of the path.
1.73 + /// Returns INVALID if the path is empty.
1.74 + GraphNode/*It*/ target() const {return INVALID;}
1.75 + /// \brief End point of the path.
1.76 + ///
1.77 + /// End point of the path.
1.78 + /// Returns INVALID if the path is empty.
1.79 + GraphNode/*It*/ source() const {return INVALID;}
1.80 +
1.81 + /// \brief First NodeIt/EdgeIt.
1.82 + ///
1.83 + /// Initializes node or edge iterator to point to the first
1.84 + /// node or edge.
1.85 + template<typename It>
1.86 + It& first(It &i) const { return i=It(*this); }
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 +
1.101 + /* Iterator classes */
1.102 +
1.103 + /**
1.104 + * \brief Iterator class to iterate on the edges of the paths
1.105 + *
1.106 + * This class is used to iterate on the edges of the paths
1.107 + *
1.108 + * Of course it converts to Graph::Edge
1.109 + *
1.110 + */
1.111 + class EdgeIt {
1.112 + public:
1.113 + /// Default constructor
1.114 + EdgeIt() {}
1.115 + /// Invalid constructor
1.116 + EdgeIt(Invalid) {}
1.117 + /// Constructor with starting point
1.118 + EdgeIt(const Path &) {}
1.119 +
1.120 + operator GraphEdge () const {}
1.121 +
1.122 + /// Next edge
1.123 + EdgeIt& operator++() {return *this;}
1.124 +
1.125 + /// Comparison operator
1.126 + bool operator==(const EdgeIt&) const {return true;}
1.127 + /// Comparison operator
1.128 + bool operator!=(const EdgeIt&) const {return true;}
1.129 +// /// Comparison operator
1.130 +// /// \todo It is not clear what is the "natural" ordering.
1.131 +// bool operator<(const EdgeIt& e) const {}
1.132 +
1.133 + };
1.134 +
1.135 + /**
1.136 + * \brief Iterator class to iterate on the nodes of the paths
1.137 + *
1.138 + * This class is used to iterate on the nodes of the paths
1.139 + *
1.140 + * Of course it converts to Graph::Node.
1.141 + *
1.142 + */
1.143 + class NodeIt {
1.144 + public:
1.145 + /// Default constructor
1.146 + NodeIt() {}
1.147 + /// Invalid constructor
1.148 + NodeIt(Invalid) {}
1.149 + /// Constructor with starting point
1.150 + NodeIt(const Path &) {}
1.151 +
1.152 + ///Conversion to Graph::Node
1.153 + operator const GraphNode& () const {}
1.154 + /// Next node
1.155 + NodeIt& operator++() {return *this;}
1.156 +
1.157 + /// Comparison operator
1.158 + bool operator==(const NodeIt&) const {return true;}
1.159 + /// Comparison operator
1.160 + bool operator!=(const NodeIt&) const {return true;}
1.161 +// /// Comparison operator
1.162 +// /// \todo It is not clear what is the "natural" ordering.
1.163 +// bool operator<(const NodeIt& e) const {}
1.164 +
1.165 + };
1.166 +
1.167 + friend class Builder;
1.168 +
1.169 + /**
1.170 + * \brief Class to build paths
1.171 + *
1.172 + * This class is used to fill a path with edges.
1.173 + *
1.174 + * You can push new edges to the front and to the back of the path in
1.175 + * arbitrary order then you should commit these changes to the graph.
1.176 + *
1.177 + * While the builder is active (after the first modifying
1.178 + * operation and until the call of \ref commit()) the
1.179 + * underlining Path is in a "transitional" state (operations on
1.180 + * it have undefined result).
1.181 + */
1.182 + class Builder {
1.183 + public:
1.184 +
1.185 + Path &P;
1.186 +
1.187 + ///\param _P the path you want to fill in.
1.188 + ///
1.189 +
1.190 + Builder(Path &_p) : P(_p) {}
1.191 +
1.192 + /// Sets the starting node of the path.
1.193 +
1.194 + /// Sets the starting node of the path. Edge added to the path
1.195 + /// afterwards have to be incident to this node.
1.196 + /// You \em must start building an empty path with these functions.
1.197 + /// (And you \em must \em not use it later).
1.198 + /// \sa pushFront()
1.199 + /// \sa pushBack()
1.200 + void setStartNode(const GraphNode &) {}
1.201 +
1.202 + ///Push a new edge to the front of the path
1.203 +
1.204 + ///Push a new edge to the front of the path.
1.205 + ///If the path is empty, you \em must call \ref setStartNode() before
1.206 + ///the first use of \ref pushFront().
1.207 + void pushFront(const GraphEdge&) {}
1.208 +
1.209 + ///Push a new edge to the back of the path
1.210 +
1.211 + ///Push a new edge to the back of the path.
1.212 + ///If the path is empty, you \em must call \ref setStartNode() before
1.213 + ///the first use of \ref pushBack().
1.214 + void pushBack(const GraphEdge&) {}
1.215 +
1.216 + ///Commit the changes to the path.
1.217 + void commit() {}
1.218 +
1.219 + ///Reserve (front) storage for the builder in advance.
1.220 +
1.221 + ///If you know a reasonable upper bound on the number of the edges
1.222 + ///to add to the front of the path,
1.223 + ///using this function you may speed up the building.
1.224 + void reserveFront(size_t) {}
1.225 + ///Reserve (back) storage for the builder in advance.
1.226 +
1.227 + ///If you know a reasonable upper bound on the number of the edges
1.228 + ///to add to the back of the path,
1.229 + ///using this function you may speed up the building.
1.230 + void reserveBack(size_t) {}
1.231 + };
1.232 + };
1.233 +
1.234 + ///@}
1.235 + }
1.236 +
1.237 +} // namespace lemon
1.238 +
1.239 +#endif // LEMON_CONCEPT_PATH_H