COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concept/path.h @ 2229:4dbb6dd2dd4b

Last change on this file since 2229:4dbb6dd2dd4b was 1993:2115143eceea, checked in by Balazs Dezso, 14 years ago

utility, invalid and traits moved to bits

File size: 6.7 KB
RevLine 
[959]1/* -*- C++ -*-
2 *
[1956]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
[1359]7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
[959]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.
[1151]22///
23///\todo Iterators have obsolete style
[959]24
25#ifndef LEMON_CONCEPT_PATH_H
26#define LEMON_CONCEPT_PATH_H
27
[1993]28#include <lemon/bits/invalid.h>
[1643]29#include <lemon/concept_check.h>
[959]30
31namespace lemon {
32  namespace concept {
33    /// \addtogroup concept
34    /// @{
35
36
[967]37    //! \brief A skeleton structure for representing directed paths in a graph.
[959]38    //!
39    //! A skeleton structure for representing directed paths in a graph.
40    //! \param GR The graph type in which the path is.
41    //!
[1270]42    //! In a sense, the path can be treated as a graph, for it has \c NodeIt
[959]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
[1624]58      /// \param _g The graph in which the path is.
[959]59      ///
[1643]60      Path(const Graph &_g) {
61        ignore_unused_variable_warning(_g);
62      }
[959]63
64      /// Length of the path.
[1282]65      int length() const {return 0;}
[959]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.
[986]76      GraphNode/*It*/ target() const {return INVALID;}
[959]77      /// \brief End point of the path.
78      ///
79      /// End point of the path.
80      /// Returns INVALID if the path is empty.
[986]81      GraphNode/*It*/ source() const {return INVALID;}
[959]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
[986]90      /// \brief The target of an edge.
[959]91      ///
[986]92      /// Returns node iterator pointing to the target node of the
[959]93      /// given edge iterator.
[1367]94      NodeIt target(const EdgeIt&) const {return INVALID;}
[959]95
[986]96      /// \brief The source of an edge.
[959]97      ///
[986]98      /// Returns node iterator pointing to the source node of the
[959]99      /// given edge iterator.
[1367]100      NodeIt source(const EdgeIt&) const {return INVALID;}
[959]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
[1367]120        EdgeIt(const Path &) {}
[959]121
122        operator GraphEdge () const {}
123
124        /// Next edge
125        EdgeIt& operator++() {return *this;}
126
127        /// Comparison operator
[1367]128        bool operator==(const EdgeIt&) const {return true;}
[959]129        /// Comparison operator
[1367]130        bool operator!=(const EdgeIt&) const {return true;}
[959]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
[1367]152        NodeIt(const Path &) {}
[959]153
154        ///Conversion to Graph::Node
155        operator const GraphNode& () const {}
156        /// Next node
157        NodeIt& operator++() {return *this;}
158
159        /// Comparison operator
[1367]160        bool operator==(const NodeIt&) const {return true;}
[959]161        /// Comparison operator
[1367]162        bool operator!=(const NodeIt&) const {return true;}
[959]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
[1270]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).
[959]183       */
184      class Builder {
185      public:
186
187        Path &P;
188
[1624]189        ///\param _p the path you want to fill in.
[959]190        ///
[1228]191
192        Builder(Path &_p) : P(_p) {}
[959]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.
[1270]198        /// You \em must start building an empty path with these functions.
[959]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().
[1367]209        void pushFront(const GraphEdge&) {}
[959]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().
[1367]216        void pushBack(const GraphEdge&) {}
[959]217
218        ///Commit the changes to the path.
219        void commit() {}
220
221        ///Reserve (front) storage for the builder in advance.
222
[1270]223        ///If you know a reasonable upper bound on the number of the edges
[959]224        ///to add to the front of the path,
225        ///using this function you may speed up the building.
[1367]226        void reserveFront(size_t) {}
[959]227        ///Reserve (back) storage for the builder in advance.
228
[1270]229        ///If you know a reasonable upper bound on the number of the edges
[959]230        ///to add to the back of the path,
231        ///using this function you may speed up the building.
[1367]232        void reserveBack(size_t) {}
[959]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.