COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/path.h @ 852:d50d89b86870

Last change on this file since 852:d50d89b86870 was 852:d50d89b86870, checked in by Alpar Juttner, 16 years ago

Remove obsolete features.

File size: 19.2 KB
Line 
1// -*- c++ -*- //
2
3/**
4@defgroup paths Path Structures
5@ingroup datas
6\brief Path structures implemented in Hugo.
7
8Hugolib provides flexible data structures
9to work with paths.
10
11All of them have the same interface, especially they can be built or extended
12using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
13algorithm to store its result in any kind of path structure.
14
15\sa hugo::skeleton::Path
16
17*/
18
19///\ingroup paths
20///\file
21///\brief Classes for representing paths in graphs.
22
23#ifndef HUGO_PATH_H
24#define HUGO_PATH_H
25
26#include <deque>
27#include <vector>
28#include <algorithm>
29
30#include <hugo/invalid.h>
31
32namespace hugo {
33
34  /// \addtogroup paths
35  /// @{
36
37
38  //! \brief A structure for representing directed paths in a graph.
39  //!
40  //! A structure for representing directed path in a graph.
41  //! \param Graph The graph type in which the path is.
42  //! \param DM DebugMode, defaults to DefaultDebugMode.
43  //!
44  //! In a sense, the path can be treated as a graph, for is has \c NodeIt
45  //! and \c EdgeIt with the same usage. These types converts to the \c Node
46  //! and \c Edge of the original graph.
47  //!
48  //! \todo Thoroughfully check all the range and consistency tests.
49  template<typename Graph>
50  class DirPath {
51  public:
52    /// Edge type of the underlying graph.
53    typedef typename Graph::Edge GraphEdge;
54    /// Node type of the underlying graph.
55    typedef typename Graph::Node GraphNode;
56    class NodeIt;
57    class EdgeIt;
58
59  protected:
60    const Graph *gr;
61    typedef std::vector<GraphEdge> Container;
62    Container edges;
63
64  public:
65
66    /// \param _G The graph in which the path is.
67    ///
68    DirPath(const Graph &_G) : gr(&_G) {}
69
70    /// \brief Subpath constructor.
71    ///
72    /// Subpath defined by two nodes.
73    /// \warning It is an error if the two edges are not in order!
74    DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
75      gr = P.gr;
76      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
77    }
78
79    /// \brief Subpath constructor.
80    ///
81    /// Subpath defined by two edges. Contains edges in [a,b)
82    /// \warning It is an error if the two edges are not in order!
83    DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
84      gr = P.gr;
85      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
86    }
87
88    /// Length of the path.
89    size_t length() const { return edges.size(); }
90    /// Returns whether the path is empty.
91    bool empty() const { return edges.empty(); }
92
93    /// Resets the path to an empty path.
94    void clear() { edges.clear(); }
95
96    /// \brief Starting point of the path.
97    ///
98    /// Starting point of the path.
99    /// Returns INVALID if the path is empty.
100    GraphNode tail() const {
101      return empty() ? INVALID : gr->tail(edges[0]);
102    }
103    /// \brief End point of the path.
104    ///
105    /// End point of the path.
106    /// Returns INVALID if the path is empty.
107    GraphNode head() const {
108      return empty() ? INVALID : gr->head(edges[length()-1]);
109    }
110
111    /// \brief Initializes node or edge iterator to point to the first
112    /// node or edge.
113    ///
114    /// \sa nth
115    template<typename It>
116    It& first(It &i) const { return i=It(*this); }
117
118    /// \brief Initializes node iterator to point to the node of a given index.
119    NodeIt& nth(NodeIt &i, int n) const {
120      return i=NodeIt(*this, n);
121    }
122
123    /// \brief Initializes edge iterator to point to the edge of a given index.
124    EdgeIt& nth(EdgeIt &i, int n) const {
125      return i=EdgeIt(*this, n);
126    }
127
128    /// \brief Returns node iterator pointing to the head node of the
129    /// given edge iterator.
130    NodeIt head(const EdgeIt& e) const {
131      return NodeIt(*this, e.idx+1);
132    }
133
134    /// \brief Returns node iterator pointing to the tail node of the
135    /// given edge iterator.
136    NodeIt tail(const EdgeIt& e) const {
137      return NodeIt(*this, e.idx);
138    }
139
140
141    /* Iterator classes */
142
143    /**
144     * \brief Iterator class to iterate on the edges of the paths
145     *
146     * \ingroup paths
147     * This class is used to iterate on the edges of the paths
148     *
149     * Of course it converts to Graph::Edge
150     *
151     */
152    class EdgeIt {
153      friend class DirPath;
154
155      int idx;
156      const DirPath *p;
157    public:
158      /// Default constructor
159      EdgeIt() {}
160      /// Invalid constructor
161      EdgeIt(Invalid) : idx(-1), p(0) {}
162      /// Constructor with starting point
163      EdgeIt(const DirPath &_p, int _idx = 0) :
164        idx(_idx), p(&_p) { validate(); }
165
166      ///Validity check
167      bool valid() const { return idx!=-1; }
168
169      ///Conversion to Graph::Edge
170      operator GraphEdge () const {
171        return valid() ? p->edges[idx] : INVALID;
172      }
173
174      /// Next edge
175      EdgeIt& operator++() { ++idx; validate(); return *this; }
176
177      /// Comparison operator
178      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
179      /// Comparison operator
180      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
181      /// Comparison operator
182      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
183
184    private:
185      // FIXME: comparison between signed and unsigned...
186      // Jo ez igy? Vagy esetleg legyen a length() int?
187      void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
188    };
189
190    /**
191     * \brief Iterator class to iterate on the nodes of the paths
192     *
193     * \ingroup paths
194     * This class is used to iterate on the nodes of the paths
195     *
196     * Of course it converts to Graph::Node
197     *
198     */
199    class NodeIt {
200      friend class DirPath;
201
202      int idx;
203      const DirPath *p;
204    public:
205      /// Default constructor
206      NodeIt() {}
207      /// Invalid constructor
208      NodeIt(Invalid) : idx(-1), p(0) {}
209      /// Constructor with starting point
210      NodeIt(const DirPath &_p, int _idx = 0) :
211        idx(_idx), p(&_p) { validate(); }
212
213      ///Validity check
214      bool valid() const { return idx!=-1; }
215
216      ///Conversion to Graph::Node
217      operator const GraphNode& () const {
218        if(idx >= p->length())
219          return p->head();
220        else if(idx >= 0)
221          return p->gr->tail(p->edges[idx]);
222        else
223          return INVALID;
224      }
225      /// Next node
226      NodeIt& operator++() { ++idx; validate(); return *this; }
227
228      /// Comparison operator
229      bool operator==(const NodeIt& e) const { return idx==e.idx; }
230      /// Comparison operator
231      bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
232      /// Comparison operator
233      bool operator<(const NodeIt& e) const { return idx<e.idx; }
234
235    private:
236      void validate() { if( size_t(idx) > p->length() ) idx=-1; }
237    };
238
239    friend class Builder;
240
241    /**
242     * \brief Class to build paths
243     *
244     * \ingroup paths
245     * This class is used to fill a path with edges.
246     *
247     * You can push new edges to the front and to the back of the path in
248     * arbitrary order then you should commit these changes to the graph.
249     *
250     * Fundamentally, for most "Paths" (classes fulfilling the
251     * PathConcept) while the builder is active (after the first modifying
252     * operation and until the commit()) the original Path is in a
253     * "transitional" state (operations on it have undefined result). But
254     * in the case of DirPath the original path remains unchanged until the
255     * commit. However we don't recomend that you use this feature.
256     */
257    class Builder {
258      DirPath &P;
259      Container front, back;
260
261    public:
262      ///\param _P the path you want to fill in.
263      ///
264      Builder(DirPath &_P) : P(_P) {}
265
266      /// Sets the starting node of the path.
267
268      /// Sets the starting node of the path. Edge added to the path
269      /// afterwards have to be incident to this node.
270      /// It should be called iff the path is empty and before any call to
271      /// \ref pushFront() or \ref pushBack()
272      void setStartNode(const GraphNode &) {}
273
274      ///Push a new edge to the front of the path
275
276      ///Push a new edge to the front of the path.
277      ///\sa setStartNode
278      void pushFront(const GraphEdge& e) {
279        front.push_back(e);
280      }
281
282      ///Push a new edge to the back of the path
283
284      ///Push a new edge to the back of the path.
285      ///\sa setStartNode
286      void pushBack(const GraphEdge& e) {
287        back.push_back(e);
288      }
289
290      ///Commit the changes to the path.
291      void commit() {
292        if( !front.empty() || !back.empty() ) {
293          Container tmp;
294          tmp.reserve(front.size()+back.size()+P.length());
295          tmp.insert(tmp.end(), front.rbegin(), front.rend());
296          tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
297          tmp.insert(tmp.end(), back.begin(), back.end());
298          P.edges.swap(tmp);
299          front.clear();
300          back.clear();
301        }
302      }
303
304      ///Reserve storage for the builder in advance.
305
306      ///If you know a reasonable upper bound of the number of the edges
307      ///to add to the front, using this function you can speed up the building.
308
309      void reserveFront(size_t r) {front.reserve(r);}
310
311      ///Reserve storage for the builder in advance.
312
313      ///If you know a reasonable upper bound of the number of the edges
314      ///to add to the back, using this function you can speed up the building.
315
316      void reserveBack(size_t r) {back.reserve(r);}
317
318    private:
319      bool empty() {
320        return front.empty() && back.empty() && P.empty();
321      }
322
323      GraphNode tail() const {
324        if( ! front.empty() )
325          return P.gr->tail(front[front.size()-1]);
326        else if( ! P.empty() )
327          return P.gr->tail(P.edges[0]);
328        else if( ! back.empty() )
329          return P.gr->tail(back[0]);
330        else
331          return INVALID;
332      }
333      GraphNode head() const {
334        if( ! back.empty() )
335          return P.gr->head(back[back.size()-1]);
336        else if( ! P.empty() )
337          return P.gr->head(P.edges[P.length()-1]);
338        else if( ! front.empty() )
339          return P.gr->head(front[0]);
340        else
341          return INVALID;
342      }
343
344    };
345
346  };
347
348
349
350
351
352
353
354
355
356
357  /**********************************************************************/
358
359
360  //! \brief A structure for representing undirected path in a graph.
361  //!
362  //! A structure for representing undirected path in a graph. Ie. this is
363  //! a path in a \e directed graph but the edges should not be directed
364  //! forward.
365  //!
366  //! \param Graph The graph type in which the path is.
367  //! \param DM DebugMode, defaults to DefaultDebugMode.
368  //!
369  //! In a sense, the path can be treated as a graph, for is has \c NodeIt
370  //! and \c EdgeIt with the same usage. These types converts to the \c Node
371  //! and \c Edge of the original graph.
372  //!
373  //! \todo Thoroughfully check all the range and consistency tests.
374  template<typename Graph>
375  class UndirPath {
376  public:
377    /// Edge type of the underlying graph.
378    typedef typename Graph::Edge GraphEdge;
379     /// Node type of the underlying graph.
380   typedef typename Graph::Node GraphNode;
381    class NodeIt;
382    class EdgeIt;
383
384  protected:
385    const Graph *gr;
386    typedef std::vector<GraphEdge> Container;
387    Container edges;
388
389  public:
390
391    /// \param _G The graph in which the path is.
392    ///
393    UndirPath(const Graph &_G) : gr(&_G) {}
394
395    /// \brief Subpath constructor.
396    ///
397    /// Subpath defined by two nodes.
398    /// \warning It is an error if the two edges are not in order!
399    UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
400      gr = P.gr;
401      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
402    }
403
404    /// \brief Subpath constructor.
405    ///
406    /// Subpath defined by two edges. Contains edges in [a,b)
407    /// \warning It is an error if the two edges are not in order!
408    UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
409      gr = P.gr;
410      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
411    }
412
413    /// Length of the path.
414    size_t length() const { return edges.size(); }
415    /// Returns whether the path is empty.
416    bool empty() const { return edges.empty(); }
417
418    /// Resets the path to an empty path.
419    void clear() { edges.clear(); }
420
421    /// \brief Starting point of the path.
422    ///
423    /// Starting point of the path.
424    /// Returns INVALID if the path is empty.
425    GraphNode tail() const {
426      return empty() ? INVALID : gr->tail(edges[0]);
427    }
428    /// \brief End point of the path.
429    ///
430    /// End point of the path.
431    /// Returns INVALID if the path is empty.
432    GraphNode head() const {
433      return empty() ? INVALID : gr->head(edges[length()-1]);
434    }
435
436    /// \brief Initializes node or edge iterator to point to the first
437    /// node or edge.
438    ///
439    /// \sa nth
440    template<typename It>
441    It& first(It &i) const { return i=It(*this); }
442
443    /// \brief Initializes node iterator to point to the node of a given index.
444    NodeIt& nth(NodeIt &i, int n) const {
445      return i=NodeIt(*this, n);
446    }
447
448    /// \brief Initializes edge iterator to point to the edge of a given index.
449    EdgeIt& nth(EdgeIt &i, int n) const {
450      return i=EdgeIt(*this, n);
451    }
452
453    /// Checks validity of a node or edge iterator.
454    template<typename It>
455    static
456    bool valid(const It &i) { return i.valid(); }
457
458    /// Steps the given node or edge iterator.
459    template<typename It>
460    static
461    It& next(It &e) {
462      return ++e;
463    }
464
465    /// \brief Returns node iterator pointing to the head node of the
466    /// given edge iterator.
467    NodeIt head(const EdgeIt& e) const {
468      return NodeIt(*this, e.idx+1);
469    }
470
471    /// \brief Returns node iterator pointing to the tail node of the
472    /// given edge iterator.
473    NodeIt tail(const EdgeIt& e) const {
474      return NodeIt(*this, e.idx);
475    }
476
477
478
479    /**
480     * \brief Iterator class to iterate on the edges of the paths
481     *
482     * \ingroup paths
483     * This class is used to iterate on the edges of the paths
484     *
485     * Of course it converts to Graph::Edge
486     *
487     * \todo Its interface differs from the standard edge iterator.
488     * Yes, it shouldn't.
489     */
490    class EdgeIt {
491      friend class UndirPath;
492
493      int idx;
494      const UndirPath *p;
495    public:
496      /// Default constructor
497      EdgeIt() {}
498      /// Invalid constructor
499      EdgeIt(Invalid) : idx(-1), p(0) {}
500      /// Constructor with starting point
501      EdgeIt(const UndirPath &_p, int _idx = 0) :
502        idx(_idx), p(&_p) { validate(); }
503
504      ///Validity check
505      bool valid() const { return idx!=-1; }
506
507      ///Conversion to Graph::Edge
508      operator GraphEdge () const {
509        return valid() ? p->edges[idx] : INVALID;
510      }
511      /// Next edge
512     EdgeIt& operator++() { ++idx; validate(); return *this; }
513
514      /// Comparison operator
515      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
516      /// Comparison operator
517      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
518      /// Comparison operator
519      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
520
521    private:
522      // FIXME: comparison between signed and unsigned...
523      // Jo ez igy? Vagy esetleg legyen a length() int?
524      void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
525    };
526
527    /**
528     * \brief Iterator class to iterate on the nodes of the paths
529     *
530     * \ingroup paths
531     * This class is used to iterate on the nodes of the paths
532     *
533     * Of course it converts to Graph::Node
534     *
535     * \todo Its interface differs from the standard node iterator.
536     * Yes, it shouldn't.
537     */
538    class NodeIt {
539      friend class UndirPath;
540
541      int idx;
542      const UndirPath *p;
543    public:
544      /// Default constructor
545      NodeIt() {}
546      /// Invalid constructor
547      NodeIt(Invalid) : idx(-1), p(0) {}
548      /// Constructor with starting point
549      NodeIt(const UndirPath &_p, int _idx = 0) :
550        idx(_idx), p(&_p) { validate(); }
551
552      ///Validity check
553      bool valid() const { return idx!=-1; }
554
555      ///Conversion to Graph::Node
556      operator const GraphNode& () const {
557        if(idx >= p->length())
558          return p->head();
559        else if(idx >= 0)
560          return p->gr->tail(p->edges[idx]);
561        else
562          return INVALID;
563      }
564      /// Next node
565      NodeIt& operator++() { ++idx; validate(); return *this; }
566
567      /// Comparison operator
568      bool operator==(const NodeIt& e) const { return idx==e.idx; }
569      /// Comparison operator
570      bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
571       /// Comparison operator
572     bool operator<(const NodeIt& e) const { return idx<e.idx; }
573
574    private:
575      void validate() { if( size_t(idx) > p->length() ) idx=-1; }
576    };
577
578    friend class Builder;
579
580    /**
581     * \brief Class to build paths
582     *
583     * \ingroup paths
584     * This class is used to fill a path with edges.
585     *
586     * You can push new edges to the front and to the back of the path in
587     * arbitrary order then you should commit these changes to the graph.
588     *
589     * Fundamentally, for most "Paths" (classes fulfilling the
590     * PathConcept) while the builder is active (after the first modifying
591     * operation and until the commit()) the original Path is in a
592     * "transitional" state (operations ot it have undefined result). But
593     * in the case of UndirPath the original path is unchanged until the
594     * commit. However we don't recomend that you use this feature.
595     */
596    class Builder {
597      UndirPath &P;
598      Container front, back;
599
600    public:
601      ///\param _P the path you want to fill in.
602      ///
603      Builder(UndirPath &_P) : P(_P) {}
604
605      /// Sets the starting node of the path.
606
607      /// Sets the starting node of the path. Edge added to the path
608      /// afterwards have to be incident to this node.
609      /// It should be called iff the path is empty and before any call to
610      /// \ref pushFront() or \ref pushBack()
611      void setStartNode(const GraphNode &) {}
612
613      ///Push a new edge to the front of the path
614
615      ///Push a new edge to the front of the path.
616      ///\sa setStartNode
617      void pushFront(const GraphEdge& e) {
618        front.push_back(e);
619      }
620
621      ///Push a new edge to the back of the path
622
623      ///Push a new edge to the back of the path.
624      ///\sa setStartNode
625      void pushBack(const GraphEdge& e) {
626        back.push_back(e);
627      }
628
629      ///Commit the changes to the path.
630      void commit() {
631        if( !(front.empty() && back.empty()) ) {
632          Container tmp;
633          tmp.reserve(front.size()+back.size()+P.length());
634          tmp.insert(tmp.end(), front.rbegin(), front.rend());
635          tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
636          tmp.insert(tmp.end(), back.begin(), back.end());
637          P.edges.swap(tmp);
638          front.clear();
639          back.clear();
640        }
641      }
642
643
644      ///Reserve storage for the builder in advance.
645
646      ///If you know a reasonable upper bound of the number of the edges
647      ///to add to the front, using this function you can speed up the building.
648
649      void reserveFront(size_t r) {front.reserve(r);}
650
651      ///Reserve storage for the builder in advance.
652
653      ///If you know a reasonable upper bound of the number of the edges
654      ///to add to the back, using this function you can speed up the building.
655
656      void reserveBack(size_t r) {back.reserve(r);}
657
658    private:
659      bool empty() {
660        return front.empty() && back.empty() && P.empty();
661      }
662
663      GraphNode tail() const {
664        if( ! front.empty() )
665          return P.gr->tail(front[front.size()-1]);
666        else if( ! P.empty() )
667          return P.gr->tail(P.edges[0]);
668        else if( ! back.empty() )
669          return P.gr->tail(back[0]);
670        else
671          return INVALID;
672      }
673      GraphNode head() const {
674        if( ! back.empty() )
675          return P.gr->head(back[back.size()-1]);
676        else if( ! P.empty() )
677          return P.gr->head(P.edges[P.length()-1]);
678        else if( ! front.empty() )
679          return P.gr->head(front[0]);
680        else
681          return INVALID;
682      }
683
684    };
685
686  };
687
688
689  ///@}
690
691} // namespace hugo
692
693#endif // HUGO_PATH_H
Note: See TracBrowser for help on using the repository browser.