COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/skeletons/path.h @ 823:afba7fbbb239

Last change on this file since 823:afba7fbbb239 was 823:afba7fbbb239, checked in by Hegyi Péter, 20 years ago

There was a little troublie with the true return statement

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