COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/skeletons/path.h @ 803:c3d832275e69

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