COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/skeletons/path.h @ 807:ce85435185c3

Last change on this file since 807:ce85435185c3 was 807:ce85435185c3, checked in by Alpar Juttner, 20 years ago

Correction in doc: skeleton/path.h has been moved to the 'skeletons' module.

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