COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concept/path.h @ 2247:269a0dcee70b

Last change on this file since 2247:269a0dcee70b was 2247:269a0dcee70b, checked in by Balazs Dezso, 13 years ago

Update the Path concept
Concept check for paths

DirPath? renamed to Path
The interface updated to the new lemon interface
Make difference between the empty path and the path from one node
Builder interface have not been changed

I wanted but there was not accordance about it

UPath is removed
It was a buggy implementation, it could not iterate on the
nodes in the right order
Right way to use undirected paths => path of edges in undirected graphs

The tests have been modified to the current implementation

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 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 _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.