1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/lemon/concept/path.h Thu Nov 04 20:24:59 2004 +0000
1.3 @@ -0,0 +1,236 @@
1.4 +/* -*- C++ -*-
1.5 + * src/lemon/concept/path.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Combinatorial Optimization Research Group, 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 +#ifndef LEMON_CONCEPT_PATH_H
1.25 +#define LEMON_CONCEPT_PATH_H
1.26 +
1.27 +#include <lemon/invalid.h>
1.28 +
1.29 +namespace lemon {
1.30 + namespace concept {
1.31 + /// \addtogroup concept
1.32 + /// @{
1.33 +
1.34 +
1.35 + //! \brief A skeletom structure for representing directed paths in a graph.
1.36 + //!
1.37 + //! A skeleton structure for representing directed paths in a graph.
1.38 + //! \param GR The graph type in which the path is.
1.39 + //!
1.40 + //! In a sense, the path can be treated as a graph, for is has \c NodeIt
1.41 + //! and \c EdgeIt with the same usage. These types converts to the \c Node
1.42 + //! and \c Edge of the original graph.
1.43 + template<typename GR>
1.44 + class Path {
1.45 + public:
1.46 +
1.47 + /// Type of the underlying graph.
1.48 + typedef /*typename*/ GR Graph;
1.49 + /// Edge type of the underlying graph.
1.50 + typedef typename Graph::Edge GraphEdge;
1.51 + /// Node type of the underlying graph.
1.52 + typedef typename Graph::Node GraphNode;
1.53 + class NodeIt;
1.54 + class EdgeIt;
1.55 +
1.56 + /// \param _G The graph in which the path is.
1.57 + ///
1.58 + Path(const Graph &_G) {}
1.59 +
1.60 + /// Length of the path.
1.61 + size_t length() const {return 0;}
1.62 + /// Returns whether the path is empty.
1.63 + bool empty() const { return true;}
1.64 +
1.65 + /// Resets the path to an empty path.
1.66 + void clear() {}
1.67 +
1.68 + /// \brief Starting point of the path.
1.69 + ///
1.70 + /// Starting point of the path.
1.71 + /// Returns INVALID if the path is empty.
1.72 + GraphNode/*It*/ head() const {return INVALID;}
1.73 + /// \brief End point of the path.
1.74 + ///
1.75 + /// End point of the path.
1.76 + /// Returns INVALID if the path is empty.
1.77 + GraphNode/*It*/ tail() const {return INVALID;}
1.78 +
1.79 + /// \brief First NodeIt/EdgeIt.
1.80 + ///
1.81 + /// Initializes node or edge iterator to point to the first
1.82 + /// node or edge.
1.83 + template<typename It>
1.84 + It& first(It &i) const { return i=It(*this); }
1.85 +
1.86 + /// \brief The head of an edge.
1.87 + ///
1.88 + /// Returns node iterator pointing to the head node of the
1.89 + /// given edge iterator.
1.90 + NodeIt head(const EdgeIt& e) const {return INVALID;}
1.91 +
1.92 + /// \brief The tail of an edge.
1.93 + ///
1.94 + /// Returns node iterator pointing to the tail node of the
1.95 + /// given edge iterator.
1.96 + NodeIt tail(const EdgeIt& e) const {return INVALID;}
1.97 +
1.98 +
1.99 + /* Iterator classes */
1.100 +
1.101 + /**
1.102 + * \brief Iterator class to iterate on the edges of the paths
1.103 + *
1.104 + * \ingroup concept
1.105 + * This class is used to iterate on the edges of the paths
1.106 + *
1.107 + * Of course it converts to Graph::Edge
1.108 + *
1.109 + */
1.110 + class EdgeIt {
1.111 + public:
1.112 + /// Default constructor
1.113 + EdgeIt() {}
1.114 + /// Invalid constructor
1.115 + EdgeIt(Invalid) {}
1.116 + /// Constructor with starting point
1.117 + EdgeIt(const Path &_p) {}
1.118 +
1.119 + operator GraphEdge () const {}
1.120 +
1.121 + /// Next edge
1.122 + EdgeIt& operator++() {return *this;}
1.123 +
1.124 + /// Comparison operator
1.125 + bool operator==(const EdgeIt& e) const {return true;}
1.126 + /// Comparison operator
1.127 + bool operator!=(const EdgeIt& e) const {return true;}
1.128 +// /// Comparison operator
1.129 +// /// \todo It is not clear what is the "natural" ordering.
1.130 +// bool operator<(const EdgeIt& e) const {}
1.131 +
1.132 + };
1.133 +
1.134 + /**
1.135 + * \brief Iterator class to iterate on the nodes of the paths
1.136 + *
1.137 + * \ingroup concept
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 &_p) {}
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& e) const {return true;}
1.159 + /// Comparison operator
1.160 + bool operator!=(const NodeIt& e) 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 + * \ingroup concept
1.173 + * This class is used to fill a path with edges.
1.174 + *
1.175 + * You can push new edges to the front and to the back of the path in
1.176 + * arbitrary order then you should commit these changes to the graph.
1.177 + *
1.178 + * While the builder is active (after the first modifying
1.179 + * operation and until the call of \ref commit())
1.180 + * the underlining Path is in a
1.181 + * "transitional" state (operations on it have undefined result).
1.182 + */
1.183 + class Builder {
1.184 + public:
1.185 +
1.186 + Path &P;
1.187 +
1.188 + ///\param _P the path you want to fill in.
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 empry path with this 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& e) {}
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& e) {}
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 an reasonable upper bound of 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 r) {}
1.225 + ///Reserve (back) storage for the builder in advance.
1.226 +
1.227 + ///If you know an reasonable upper bound of 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 r) {}
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