COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/path.h @ 837:2d50d1f045c5

Last change on this file since 837:2d50d1f045c5 was 837:2d50d1f045c5, checked in by Hegyi Péter, 16 years ago

Reserve is resolved.

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