COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/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: 12.2 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
20///\ingroup paths
21///\file
22///\brief Classes for representing paths in graphs.
23///
24
25#ifndef LEMON_PATH_H
26#define LEMON_PATH_H
27
28#include <vector>
29#include <algorithm>
30
31#include <lemon/error.h>
32#include <lemon/bits/invalid.h>
33
34namespace lemon {
35
36  /// \addtogroup paths
37  /// @{
38
39
40  //! \brief A structure for representing directed paths in a graph.
41  //!
42  //! A structure for representing directed path in a graph.
43  //! \param Graph The graph type in which the path is.
44  //!
45  //! In a sense, the path can be treated as a graph, for is has \c NodeIt
46  //! and \c EdgeIt with the same usage. These types converts to the \c Node
47  //! and \c Edge of the original graph.
48  //!
49  //! \todo Thoroughfully check all the range and consistency tests.
50  template<typename Graph>
51  class Path {
52  public:
53    /// Edge type of the underlying graph.
54    typedef typename Graph::Edge Edge;
55    /// Node type of the underlying graph.
56    typedef typename Graph::Node Node;
57
58    class NodeIt;
59    class EdgeIt;
60
61    struct PathError : public LogicError {
62      virtual const char* what() const throw() {
63        return "lemon::PathError";
64      }     
65    };
66
67  public:
68
69    /// \brief Constructor
70    ///
71    /// Constructor
72    /// \param _G The graph in which the path is.
73    Path(const Graph &_graph) : graph(&_graph), start(INVALID) {}
74   
75    /// \brief Subpath constructor.
76    ///
77    /// Subpath defined by two nodes.
78    /// \warning It is an error if the two edges are not in order!
79    Path(const Path &other, const NodeIt &a, const NodeIt &b) {
80      graph = other.graph;
81      start = a;
82      edges.insert(edges.end(),
83                   other.edges.begin() + a.id, other.edges.begin() + b.id);
84    }
85
86    /// \brief Subpath constructor.
87    ///
88    /// Subpath defined by two edges. Contains edges in [a,b)
89    /// \warning It is an error if the two edges are not in order!
90    Path(const Path &other, const EdgeIt &a, const EdgeIt &b) {
91      graph = other.graph;
92      start = graph->source(a);
93      edges.insert(edges.end(),
94                   other.edges.begin() + a.id, other.edges.begin() + b.id);
95    }
96
97    /// \brief Length of the path.
98    ///
99    /// The number of the edges in the path. It can be zero if the
100    /// path has only one node or it is empty.
101    int length() const { return edges.size(); }
102
103    /// \brief Returns whether the path is empty.
104    ///
105    /// Returns true when the path does not contain neither edge nor
106    /// node.
107    bool empty() const { return start == INVALID; }
108
109    /// \brief Resets the path to an empty path.
110    ///
111    /// Resets the path to an empty path.
112    void clear() { edges.clear(); start = INVALID; }
113
114    /// \brief Starting point of the path.
115    ///
116    /// Starting point of the path.
117    /// Returns INVALID if the path is empty.
118    Node source() const {
119      return start;
120    }
121    /// \brief End point of the path.
122    ///
123    /// End point of the path.
124    /// Returns INVALID if the path is empty.
125    Node target() const {
126      return length() == 0 ? start : graph->target(edges[length()-1]);
127    }
128
129    /// \brief Gives back a node iterator to point to the node of a
130    /// given index.
131    ///
132    /// Gives back a node iterator to point to the node of a given
133    /// index.
134    /// \pre n should less or equal to \c length()
135    NodeIt nthNode(int n) const {
136      return NodeIt(*this, n);
137    }
138
139    /// \brief Gives back an edge iterator to point to the edge of a
140    /// given index.
141    ///
142    /// Gives back an edge iterator to point to the node of a given
143    /// index. 
144    /// \pre n should less than \c length()
145    EdgeIt nthEdge(int n) const {
146      return EdgeIt(*this, n);
147    }
148
149    /// \brief Returns node iterator pointing to the source node of the
150    /// given edge iterator.
151    ///
152    /// Returns node iterator pointing to the source node of the given
153    /// edge iterator.
154    NodeIt source(const EdgeIt& e) const {
155      return NodeIt(*this, e.id);
156    }
157
158    /// \brief Returns node iterator pointing to the target node of the
159    /// given edge iterator.
160    ///
161    /// Returns node iterator pointing to the target node of the given
162    /// edge iterator.
163    NodeIt target(const EdgeIt& e) const {
164      return NodeIt(*this, e.id + 1);
165    }
166
167
168    /// \brief Iterator class to iterate on the nodes of the paths
169    ///
170    /// This class is used to iterate on the nodes of the paths
171    ///
172    /// Of course it converts to Graph::Node
173    class NodeIt {
174      friend class Path;
175    public:
176
177      /// \brief Default constructor
178      ///
179      /// Default constructor
180      NodeIt() {}
181
182      /// \brief Invalid constructor
183      ///
184      /// Invalid constructor
185      NodeIt(Invalid) : id(-1), path(0) {}
186
187      /// \brief Constructor with starting point
188      ///
189      /// Constructor with starting point
190      NodeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) {
191        if (id > path->length()) id = -1;
192      }
193
194      /// \brief Conversion to Graph::Node
195      ///
196      /// Conversion to Graph::Node
197      operator Node() const {
198        if (id > 0) {
199          return path->graph->target(path->edges[id - 1]);
200        } else if (id == 0) {
201          return path->start;
202        } else {
203          return INVALID;
204        }
205      }
206
207      /// \brief Steps to the next node
208      ///
209      /// Steps to the next node
210      NodeIt& operator++() {
211        ++id;
212        if (id > path->length()) id = -1;
213        return *this;
214      }
215
216      /// \brief Comparison operator
217      ///
218      /// Comparison operator
219      bool operator==(const NodeIt& n) const { return id == n.id; }
220
221      /// \brief Comparison operator
222      ///
223      /// Comparison operator
224      bool operator!=(const NodeIt& n) const { return id != n.id; }
225
226      /// \brief Comparison operator
227      ///
228      /// Comparison operator
229      bool operator<(const NodeIt& n) const { return id < n.id; }
230
231    private:
232      int id;
233      const Path *path;
234    };
235
236    /// \brief Iterator class to iterate on the edges of the paths
237    ///
238    /// This class is used to iterate on the edges of the paths
239    /// Of course it converts to Graph::Edge
240    class EdgeIt {
241      friend class Path;
242    public:
243
244      /// \brief Default constructor
245      ///
246      /// Default constructor
247      EdgeIt() {}
248
249      /// \brief Invalid constructor
250      ///
251      /// Invalid constructor
252      EdgeIt(Invalid) : id(-1), path(0) {}
253
254      /// \brief Constructor with starting point
255      ///
256      /// Constructor with starting point
257      EdgeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) {
258        if (id >= path->length()) id = -1;
259      }
260
261      /// \brief Conversion to Graph::Edge
262      ///
263      /// Conversion to Graph::Edge
264      operator Edge() const {
265        return id != -1 ? path->edges[id] : INVALID;
266      }
267
268      /// \brief Steps to the next edge
269      ///
270      /// Steps to the next edge
271      EdgeIt& operator++() {
272        ++id;
273        if (id >= path->length()) id = -1;
274        return *this;
275      }
276
277      /// \brief Comparison operator
278      ///
279      /// Comparison operator
280      bool operator==(const EdgeIt& e) const { return id == e.id; }
281
282      /// \brief Comparison operator
283      ///
284      /// Comparison operator
285      bool operator!=(const EdgeIt& e) const { return id != e.id; }
286
287      /// \brief Comparison operator
288      ///
289      /// Comparison operator
290      bool operator<(const EdgeIt& e) const { return id < e.id; }
291
292    private:
293
294      int id;
295      const Path *path;
296    };
297
298  protected:
299
300    const Graph *graph;
301
302    typedef std::vector<Edge> Container;
303    Container edges;
304    Node start;
305
306  public:
307
308    friend class Builder;
309
310    /// \brief Class to build paths
311    ///
312    /// This class is used to fill a path with edges.
313    ///
314    /// You can push new edges to the front and to the back of the
315    /// path in arbitrary order then you should commit these changes
316    /// to the graph.
317    ///
318    /// Fundamentally, for most "Paths" (classes fulfilling the
319    /// PathConcept) while the builder is active (after the first
320    /// modifying operation and until the commit()) the original Path
321    /// is in a "transitional" state (operations on it have undefined
322    /// result). But in the case of Path the original path remains
323    /// unchanged until the commit. However we don't recomend that you
324    /// use this feature.
325    class Builder {
326    public:
327      /// \brief Constructor
328      ///
329      /// Constructor
330      /// \param _path the path you want to fill in.
331      Builder(Path &_path) : path(_path), start(INVALID) {}
332
333      /// \brief Destructor
334      ///
335      /// Destructor
336      ~Builder() {
337        LEMON_ASSERT(front.empty() && back.empty() && start == INVALID,
338                     PathError());
339      }
340
341      /// \brief Sets the starting node of the path.
342      ///
343      /// Sets the starting node of the path. Edge added to the path
344      /// afterwards have to be incident to this node.  It should be
345      /// called if and only if the path is empty and before any call
346      /// to \ref pushFront() or \ref pushBack()
347      void setStartNode(const Node &_start) {
348        LEMON_ASSERT(path.empty() && start == INVALID, PathError());
349        start = _start;
350      }
351
352      /// \brief Push a new edge to the front of the path
353      ///
354      /// Push a new edge to the front of the path. 
355      /// \sa setStartNode
356      void pushFront(const Edge& e) {
357        LEMON_ASSERT(front.empty() ||
358                     (path.graph->source(front.back()) ==
359                      path.graph->target(e)), PathError());
360        LEMON_ASSERT(path.empty() ||
361                     (path.source() == path.graph->target(e)), PathError());
362        LEMON_ASSERT(!path.empty() || !front.empty() ||
363                     (start == path.graph->target(e)), PathError());
364        front.push_back(e);
365      }
366
367      /// \brief Push a new edge to the back of the path
368      ///
369      /// Push a new edge to the back of the path.
370      /// \sa setStartNode
371      void pushBack(const Edge& e) {
372        LEMON_ASSERT(back.empty() ||
373                     (path.graph->target(back.back()) ==
374                      path.graph->source(e)), PathError());
375        LEMON_ASSERT(path.empty() ||
376                     (path.target() == path.graph->source(e)), PathError());
377        LEMON_ASSERT(!path.empty() || !back.empty() ||
378                     (start == path.graph->source(e)), PathError());
379        back.push_back(e);
380      }
381
382      /// \brief Commit the changes to the path.
383      ///
384      /// Commit the changes to the path.
385      void commit() {
386        if( !front.empty() || !back.empty() || start != INVALID) {
387          Container tmp;
388          tmp.reserve(front.size() + back.size() + path.length());
389          tmp.insert(tmp.end(), front.rbegin(), front.rend());
390          tmp.insert(tmp.end(), path.edges.begin(), path.edges.end());
391          tmp.insert(tmp.end(), back.begin(), back.end());
392          path.edges.swap(tmp);
393          if (!front.empty()) {
394            path.start = path.graph->source(front.back());
395          } else {
396            path.start = start;
397          }
398          start = INVALID;
399          front.clear();
400          back.clear();
401        }
402      }
403
404      /// \brief Reserve storage for the builder in advance.
405      ///
406      /// If you know a reasonable upper bound of the number of the
407      /// edges to add to the front, using this function you can speed
408      /// up the building.
409      void reserveFront(size_t r) {front.reserve(r);}
410
411      /// \brief Reserve storage for the builder in advance.
412      ///
413      /// If you know a reasonable upper bound of the number of the
414      /// edges to add to the back, using this function you can speed
415      /// up the building.
416      void reserveBack(size_t r) {back.reserve(r);}
417
418    private:
419
420      Path &path;
421      Container front, back;
422      Node start;
423
424    };
425
426  };
427
428  ///@}
429
430} // namespace lemon
431
432#endif // LEMON_PATH_H
Note: See TracBrowser for help on using the repository browser.