COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concept/path.h @ 1993:2115143eceea

Last change on this file since 1993:2115143eceea was 1993:2115143eceea, checked in by Balazs Dezso, 18 years ago

utility, invalid and traits moved to bits

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