COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/skeletons/path.h @ 831:b6ae3446098a

Last change on this file since 831:b6ae3446098a was 831:b6ae3446098a, checked in by Hegyi Péter, 16 years ago

The first version of new path test program. The old became old_path_test.

File size: 6.1 KB
Line 
1// -*- c++ -*- //
2
3///\ingroup skeletons
4///\file
5///\brief Classes for representing paths in graphs.
6
7#ifndef HUGO_SKELETON_PATH_H
8#define HUGO_SKELETON_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 {return 0;}
45      /// Returns whether the path is empty.
46      bool empty() const { return true;}
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      GraphNode/*It*/ head() const {return INVALID;}
56      /// \brief End point of the path.
57      ///
58      /// End point of the path.
59      /// Returns INVALID if the path is empty.
60      GraphNode/*It*/ tail() const {return INVALID;}
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 {return INVALID;}
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 {return INVALID;}
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++() {return *this;}
106
107        /// Comparison operator
108        bool operator==(const EdgeIt& e) const {return true;}
109        /// Comparison operator
110        bool operator!=(const EdgeIt& e) const {return true;}
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++() {return *this;}
139
140        /// Comparison operator
141        bool operator==(const NodeIt& e) const {return true;}
142        /// Comparison operator
143        bool operator!=(const NodeIt& e) const {return true;}
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
169        Path &P;
170
171        ///\param _P the path you want to fill in.
172        ///
173        Builder(Path &_P) : P(_P) {}
174
175        /// Sets the starting node of the path.
176
177        /// Sets the starting node of the path. Edge added to the path
178        /// afterwards have to be incident to this node.
179        /// You \em must start building an empry path with this functions.
180        /// (And you \em must \em not use it later).
181        /// \sa pushFront()
182        /// \sa pushBack()
183        void setStartNode(const GraphNode &) {}
184
185        ///Push a new edge to the front of the path
186
187        ///Push a new edge to the front of the path.
188        ///If the path is empty, you \em must call \ref setStartNode() before
189        ///the first use of \ref pushFront().
190        void pushFront(const GraphEdge& e) {}
191
192        ///Push a new edge to the back of the path
193
194        ///Push a new edge to the back of the path.
195        ///If the path is empty, you \em must call \ref setStartNode() before
196        ///the first use of \ref pushBack().
197        void pushBack(const GraphEdge& e) {}
198
199        ///Commit the changes to the path.
200        void commit() {}
201
202        ///Reserve (front) storage for the builder in advance.
203
204        ///If you know an reasonable upper bound of the number of the edges
205        ///to add to the front of the path,
206        ///using this function you may speed up the building.
207        void reserveFront(size_t r) {}
208        ///Reserve (back) storage for the builder in advance.
209
210        ///If you know an reasonable upper bound of the number of the edges
211        ///to add to the back of the path,
212        ///using this function you may speed up the building.
213        void reserveBack(size_t r) {}
214      };
215    };
216
217  ///@}
218  }
219
220} // namespace hugo
221
222#endif // HUGO_SKELETON_PATH_H
Note: See TracBrowser for help on using the repository browser.