COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/skeletons/path.h @ 949:b16a10926781

Last change on this file since 949:b16a10926781 was 921:818510fa3d99, checked in by Alpar Juttner, 20 years ago

hugo -> lemon

File size: 6.7 KB
RevLine 
[906]1/* -*- C++ -*-
[921]2 * src/lemon/skeletons/path.h - Part of LEMON, a generic C++ optimization library
[906]3 *
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
[797]16
[807]17///\ingroup skeletons
[797]18///\file
19///\brief Classes for representing paths in graphs.
20
[921]21#ifndef LEMON_SKELETON_PATH_H
22#define LEMON_SKELETON_PATH_H
[797]23
[921]24#include <lemon/invalid.h>
[797]25
[921]26namespace lemon {
[803]27  namespace skeleton {
28    /// \addtogroup skeletons
29    /// @{
[831]30
31
[806]32    //! \brief A skeletom structure for representing directed paths in a graph.
[803]33    //!
[806]34    //! A skeleton structure for representing directed paths in a graph.
[803]35    //! \param GR The graph type in which the path is.
[831]36    //!
[803]37    //! In a sense, the path can be treated as a graph, for is has \c NodeIt
38    //! and \c EdgeIt with the same usage. These types converts to the \c Node
39    //! and \c Edge of the original graph.
40    template<typename GR>
41    class Path {
42    public:
[831]43
[803]44      /// Type of the underlying graph.
[818]45      typedef /*typename*/ GR Graph;
[803]46      /// Edge type of the underlying graph.
[831]47      typedef typename Graph::Edge GraphEdge;
[803]48      /// Node type of the underlying graph.
[818]49     typedef typename Graph::Node GraphNode;
[803]50      class NodeIt;
51      class EdgeIt;
[831]52
[803]53      /// \param _G The graph in which the path is.
54      ///
55      Path(const Graph &_G) {}
[831]56
[803]57      /// Length of the path.
[818]58      size_t length() const {return 0;}
[803]59      /// Returns whether the path is empty.
[831]60      bool empty() const { return true;}
61
[803]62      /// Resets the path to an empty path.
63      void clear() {}
[797]64
[803]65      /// \brief Starting point of the path.
66      ///
67      /// Starting point of the path.
68      /// Returns INVALID if the path is empty.
[818]69      GraphNode/*It*/ head() const {return INVALID;}
[803]70      /// \brief End point of the path.
71      ///
72      /// End point of the path.
73      /// Returns INVALID if the path is empty.
[818]74      GraphNode/*It*/ tail() const {return INVALID;}
[797]75
[803]76      /// \brief First NodeIt/EdgeIt.
77      ///
78      /// Initializes node or edge iterator to point to the first
79      /// node or edge.
80      template<typename It>
81      It& first(It &i) const { return i=It(*this); }
[797]82
[803]83      /// \brief The head of an edge.
84      ///
85      /// Returns node iterator pointing to the head node of the
86      /// given edge iterator.
[831]87      NodeIt head(const EdgeIt& e) const {return INVALID;}
[797]88
[803]89      /// \brief The tail of an edge.
90      ///
91      /// Returns node iterator pointing to the tail node of the
92      /// given edge iterator.
[831]93      NodeIt tail(const EdgeIt& e) const {return INVALID;}
[797]94
95
[803]96      /* Iterator classes */
[797]97
[803]98      /**
99       * \brief Iterator class to iterate on the edges of the paths
[831]100       *
[803]101       * \ingroup skeletons
102       * This class is used to iterate on the edges of the paths
103       *
104       * Of course it converts to Graph::Edge
[831]105       *
[803]106       */
107      class EdgeIt {
108      public:
109        /// Default constructor
110        EdgeIt() {}
111        /// Invalid constructor
112        EdgeIt(Invalid) {}
113        /// Constructor with starting point
114        EdgeIt(const Path &_p) {}
[797]115
[803]116        operator GraphEdge () const {}
[797]117
[803]118        /// Next edge
[831]119        EdgeIt& operator++() {return *this;}
[797]120
[803]121        /// Comparison operator
[823]122        bool operator==(const EdgeIt& e) const {return true;}
[803]123        /// Comparison operator
[823]124        bool operator!=(const EdgeIt& e) const {return true;}
[803]125//      /// Comparison operator
126//      /// \todo It is not clear what is the "natural" ordering.
127//      bool operator<(const EdgeIt& e) const {}
[797]128
[803]129      };
[797]130
[803]131      /**
132       * \brief Iterator class to iterate on the nodes of the paths
[831]133       *
[803]134       * \ingroup skeletons
135       * This class is used to iterate on the nodes of the paths
136       *
137       * Of course it converts to Graph::Node.
[831]138       *
[803]139       */
140      class NodeIt {
141      public:
142        /// Default constructor
143        NodeIt() {}
144        /// Invalid constructor
145        NodeIt(Invalid) {}
146        /// Constructor with starting point
147        NodeIt(const Path &_p) {}
[797]148
[803]149        ///Conversion to Graph::Node
150        operator const GraphNode& () const {}
151        /// Next node
[831]152        NodeIt& operator++() {return *this;}
[797]153
[803]154        /// Comparison operator
[831]155        bool operator==(const NodeIt& e) const {return true;}
[803]156        /// Comparison operator
[831]157        bool operator!=(const NodeIt& e) const {return true;}
[803]158//      /// Comparison operator
159//      /// \todo It is not clear what is the "natural" ordering.
160//      bool operator<(const NodeIt& e) const {}
[797]161
[803]162      };
[797]163
[831]164      friend class Builder;
[797]165
[803]166      /**
167       * \brief Class to build paths
[831]168       *
[803]169       * \ingroup skeletons
170       * This class is used to fill a path with edges.
171       *
172       * You can push new edges to the front and to the back of the path in
173       * arbitrary order then you should commit these changes to the graph.
174       *
175       * While the builder is active (after the first modifying
176       * operation and until the call of \ref commit())
177       * the underlining Path is in a
178       * "transitional" state (operations on it have undefined result).
179       */
180      class Builder {
181      public:
[818]182
183        Path &P;
184
[803]185        ///\param _P the path you want to fill in.
186        ///
187        Builder(Path &_P) : P(_P) {}
[797]188
[803]189        /// Sets the starting node of the path.
[831]190
[803]191        /// Sets the starting node of the path. Edge added to the path
192        /// afterwards have to be incident to this node.
193        /// You \em must start building an empry path with this functions.
194        /// (And you \em must \em not use it later).
195        /// \sa pushFront()
196        /// \sa pushBack()
197        void setStartNode(const GraphNode &) {}
[797]198
[803]199        ///Push a new edge to the front of the path
[797]200
[803]201        ///Push a new edge to the front of the path.
202        ///If the path is empty, you \em must call \ref setStartNode() before
203        ///the first use of \ref pushFront().
204        void pushFront(const GraphEdge& e) {}
[797]205
[803]206        ///Push a new edge to the back of the path
[797]207
[803]208        ///Push a new edge to the back of the path.
209        ///If the path is empty, you \em must call \ref setStartNode() before
210        ///the first use of \ref pushBack().
211        void pushBack(const GraphEdge& e) {}
[797]212
[803]213        ///Commit the changes to the path.
214        void commit() {}
[797]215
[803]216        ///Reserve (front) storage for the builder in advance.
[797]217
[803]218        ///If you know an reasonable upper bound of the number of the edges
219        ///to add to the front of the path,
220        ///using this function you may speed up the building.
221        void reserveFront(size_t r) {}
222        ///Reserve (back) storage for the builder in advance.
[797]223
[803]224        ///If you know an reasonable upper bound of the number of the edges
225        ///to add to the back of the path,
226        ///using this function you may speed up the building.
227        void reserveBack(size_t r) {}
228      };
[797]229    };
230
[803]231  ///@}
[797]232  }
[831]233
[921]234} // namespace lemon
[797]235
[921]236#endif // LEMON_SKELETON_PATH_H
Note: See TracBrowser for help on using the repository browser.