COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/concept/path.h @ 1164:80bb73097736

Last change on this file since 1164:80bb73097736 was 1164:80bb73097736, checked in by Alpar Juttner, 15 years ago

A year has passed again.

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