COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concept/path.h @ 1875:98698b69a902

Last change on this file since 1875:98698b69a902 was 1875:98698b69a902, checked in by Alpar Juttner, 14 years ago

Happy new year to LEMON

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