COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concepts/path.h @ 2260:4274224f8a7d

Last change on this file since 2260:4274224f8a7d was 2260:4274224f8a7d, checked in by Alpar Juttner, 17 years ago

concept -> concepts (namespace & directory)

File size: 8.0 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 concepts {
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 _Graph 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 _Graph>
46    class Path {
47    public:
48
49      /// Type of the underlying graph.
50      typedef _Graph Graph;
51      /// Edge type of the underlying graph.
52      typedef typename Graph::Edge Edge;
53      /// Node type of the underlying graph.
54      typedef typename Graph::Node Node;
55
56      class NodeIt;
57      class EdgeIt;
58
59      /// \param _g The graph in which the path is.
60      ///
61      Path(const Graph &_g) {
62        ignore_unused_variable_warning(_g);
63      }
64
65      /// Length of the path ie. the number of edges in the path.
66      int length() const {return 0;}
67
68      /// Returns whether the path is empty.
69      bool empty() const { return true;}
70
71      /// Resets the path to an empty path.
72      void clear() {}
73
74      /// \brief Starting point of the path.
75      ///
76      /// Starting point of the path.
77      /// Returns INVALID if the path is empty.
78      Node target() const {return INVALID;}
79      /// \brief End point of the path.
80      ///
81      /// End point of the path.
82      /// Returns INVALID if the path is empty.
83      Node source() const {return INVALID;}
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&) 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&) const {return INVALID;}
96
97      /// \brief Iterator class to iterate on the nodes of the paths
98      ///
99      /// This class is used to iterate on the nodes of the paths
100      ///
101      /// Of course it converts to Graph::Node.
102      class NodeIt {
103      public:
104        /// Default constructor
105        NodeIt() {}
106        /// Invalid constructor
107        NodeIt(Invalid) {}
108        /// Constructor with starting point
109        NodeIt(const Path &) {}
110
111        ///Conversion to Graph::Node
112        operator Node() const { return INVALID; }
113        /// Next node
114        NodeIt& operator++() {return *this;}
115
116        /// Comparison operator
117        bool operator==(const NodeIt&) const {return true;}
118        /// Comparison operator
119        bool operator!=(const NodeIt&) const {return true;}
120        /// Comparison operator
121        bool operator<(const NodeIt&) const {return false;}
122
123      };
124
125      /// \brief Iterator class to iterate on the edges of the paths
126      ///
127      /// This class is used to iterate on the edges of the paths
128      ///
129      /// Of course it converts to Graph::Edge
130      class EdgeIt {
131      public:
132        /// Default constructor
133        EdgeIt() {}
134        /// Invalid constructor
135        EdgeIt(Invalid) {}
136        /// Constructor with starting point
137        EdgeIt(const Path &) {}
138
139        operator Edge() const { return INVALID; }
140
141        /// Next edge
142        EdgeIt& operator++() {return *this;}
143
144        /// Comparison operator
145        bool operator==(const EdgeIt&) const {return true;}
146        /// Comparison operator
147        bool operator!=(const EdgeIt&) const {return true;}
148        /// Comparison operator
149        bool operator<(const EdgeIt&) const {return false;}
150
151      };
152
153
154      friend class Builder;
155
156      /// \brief Class to build paths
157      ///
158      /// This class is used to fill a path with edges.
159      ///
160      /// You can push new edges to the front and to the back of the path in
161      /// arbitrary order then you should commit these changes to the graph.
162      ///
163      /// While the builder is active (after the first modifying
164      /// operation and until the call of \ref commit()) the
165      /// underlining Path is in a "transitional" state (operations on
166      /// it have undefined result).
167      class Builder {
168      public:
169
170        /// Constructor
171
172        /// Constructor
173        /// \param _path the path you want to fill in.
174        ///
175
176        Builder(Path &_path) { ignore_unused_variable_warning(_path); }
177
178        /// Sets the starting node of the path.
179
180        /// Sets the starting node of the path. Edge added to the path
181        /// afterwards have to be incident to this node.
182        /// You \em must start building an empty path with these functions.
183        /// (And you \em must \em not use it later).
184        /// \sa pushFront()
185        /// \sa pushBack()
186        void setStartNode(const Node &) {}
187
188        ///Push a new edge to the front of the path
189
190        ///Push a new edge to the front of the path.
191        ///If the path is empty, you \em must call \ref setStartNode() before
192        ///the first use of \ref pushFront().
193        void pushFront(const Edge&) {}
194
195        ///Push a new edge to the back of the path
196
197        ///Push a new edge to the back of the path.
198        ///If the path is empty, you \em must call \ref setStartNode() before
199        ///the first use of \ref pushBack().
200        void pushBack(const Edge&) {}
201
202        ///Commit the changes to the path.
203
204        ///Commit the changes to the path.
205        ///
206        void commit() {}
207
208        ///Reserve (front) storage for the builder in advance.
209
210        ///If you know a reasonable upper bound on the number of the edges
211        ///to add to the front of the path,
212        ///using this function you may speed up the building.
213        void reserveFront(size_t) {}
214        ///Reserve (back) storage for the builder in advance.
215
216        ///If you know a reasonable upper bound on the number of the edges
217        ///to add to the back of the path,
218        ///using this function you may speed up the building.
219        void reserveBack(size_t) {}
220      };
221
222      template <typename _Path>
223      struct Constraints {
224        void constraints() {
225          typedef typename _Path::Node Node;
226          typedef typename _Path::NodeIt NodeIt;
227          typedef typename Graph::Node GraphNode;
228
229          typedef typename _Path::Edge Edge;
230          typedef typename _Path::EdgeIt EdgeIt;
231          typedef typename Graph::Edge GraphEdge;
232
233          typedef typename _Path::Builder Builder;
234
235          path = _Path(graph);
236
237          bool b = cpath.empty();
238          int l = cpath.length();
239
240          Node gn;
241          Edge ge;
242          gn = cpath.source();
243          gn = cpath.target();
244
245          NodeIt nit;
246          EdgeIt eit(INVALID);
247          nit = path.source(eit);
248          nit = path.target(eit);
249         
250          nit = NodeIt();
251          nit = NodeIt(cpath);
252          nit = INVALID;
253          gn = nit;
254          ++nit;
255          b = nit == nit;
256          b = nit != nit;
257          b = nit < nit;
258
259          eit = EdgeIt();
260          eit = EdgeIt(cpath);
261          eit = INVALID;
262          ge = eit;
263          ++eit;
264          b = eit == eit;
265          b = eit != eit;
266          b = eit < eit;
267
268          size_t st = 0;
269
270          Builder builder(path);
271          builder.setStartNode(gn);
272          builder.pushFront(ge);
273          builder.pushBack(ge);
274          builder.commit();
275          builder.reserveFront(st);
276          builder.reserveBack(st);
277         
278          ignore_unused_variable_warning(l);
279          ignore_unused_variable_warning(b);
280        }
281
282        const Graph& graph;
283        const _Path& cpath;
284        _Path& path;
285      };
286
287    };
288
289  ///@}
290  }
291
292} // namespace lemon
293
294#endif // LEMON_CONCEPT_PATH_H
Note: See TracBrowser for help on using the repository browser.