1.1 --- a/src/lemon/concept/path.h Sat May 21 21:04:57 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,236 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/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