COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/path.h @ 835:eb9587f09b42

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

Remove one remaining range checking.

File size: 29.6 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      // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
321      // Hogy kenyelmes egy ilyet hasznalni?
322 
323      ///Reserve storage for the builder in advance.
324
325      ///If you know an reasonable upper bound of the number of the edges
326      ///to add, using this function you can speed up the building.
327      void reserve(size_t r) {
328        front.reserve(r);
329        back.reserve(r);
330      }
331
332      void reserveFront(size_t r) {}
333      void reserveBack(size_t r) {}
334
335    private:
336      bool empty() {
337        return front.empty() && back.empty() && P.empty();
338      }
339
340      GraphNode tail() const {
341        if( ! front.empty() )
342          return P.gr->tail(front[front.size()-1]);
343        else if( ! P.empty() )
344          return P.gr->tail(P.edges[0]);
345        else if( ! back.empty() )
346          return P.gr->tail(back[0]);
347        else
348          return INVALID;
349      }
350      GraphNode head() const {
351        if( ! back.empty() )
352          return P.gr->head(back[back.size()-1]);
353        else if( ! P.empty() )
354          return P.gr->head(P.edges[P.length()-1]);
355        else if( ! front.empty() )
356          return P.gr->head(front[0]);
357        else
358          return INVALID;
359      }
360
361    };
362
363  };
364
365
366
367
368
369
370
371
372
373
374  /**********************************************************************/
375
376
377  //! \brief A structure for representing undirected path in a graph.
378  //!
379  //! A structure for representing undirected path in a graph. Ie. this is
380  //! a path in a \e directed graph but the edges should not be directed
381  //! forward.
382  //!
383  //! \param Graph The graph type in which the path is.
384  //! \param DM DebugMode, defaults to DefaultDebugMode.
385  //!
386  //! In a sense, the path can be treated as a graph, for is has \c NodeIt
387  //! and \c EdgeIt with the same usage. These types converts to the \c Node
388  //! and \c Edge of the original graph.
389  //!
390  //! \todo Thoroughfully check all the range and consistency tests.
391  template<typename Graph>
392  class UndirPath {
393  public:
394    /// Edge type of the underlying graph.
395    typedef typename Graph::Edge GraphEdge;
396     /// Node type of the underlying graph.
397   typedef typename Graph::Node GraphNode;
398    class NodeIt;
399    class EdgeIt;
400
401  protected:
402    const Graph *gr;
403    typedef std::vector<GraphEdge> Container;
404    Container edges;
405
406  public:
407
408    /// \param _G The graph in which the path is.
409    ///
410    UndirPath(const Graph &_G) : gr(&_G) {}
411
412    /// \brief Subpath constructor.
413    ///
414    /// Subpath defined by two nodes.
415    /// \warning It is an error if the two edges are not in order!
416    UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
417      gr = P.gr;
418      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
419    }
420
421    /// \brief Subpath constructor.
422    ///
423    /// Subpath defined by two edges. Contains edges in [a,b)
424    /// \warning It is an error if the two edges are not in order!
425    UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
426      gr = P.gr;
427      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
428    }
429
430    /// Length of the path.
431    size_t length() const { return edges.size(); }
432    /// Returns whether the path is empty.
433    bool empty() const { return edges.empty(); }
434
435    /// Resets the path to an empty path.
436    void clear() { edges.clear(); }
437
438    /// \brief Starting point of the path.
439    ///
440    /// Starting point of the path.
441    /// Returns INVALID if the path is empty.
442    GraphNode tail() const {
443      return empty() ? INVALID : gr->tail(edges[0]);
444    }
445    /// \brief End point of the path.
446    ///
447    /// End point of the path.
448    /// Returns INVALID if the path is empty.
449    GraphNode head() const {
450      return empty() ? INVALID : gr->head(edges[length()-1]);
451    }
452
453    /// \brief Initializes node or edge iterator to point to the first
454    /// node or edge.
455    ///
456    /// \sa nth
457    template<typename It>
458    It& first(It &i) const { return i=It(*this); }
459
460    /// \brief Initializes node iterator to point to the node of a given index.
461    NodeIt& nth(NodeIt &i, int n) const {
462      return i=NodeIt(*this, n);
463    }
464
465    /// \brief Initializes edge iterator to point to the edge of a given index.
466    EdgeIt& nth(EdgeIt &i, int n) const {
467      return i=EdgeIt(*this, n);
468    }
469
470    /// Checks validity of a node or edge iterator.
471    template<typename It>
472    static
473    bool valid(const It &i) { return i.valid(); }
474
475    /// Steps the given node or edge iterator.
476    template<typename It>
477    static
478    It& next(It &e) {
479      return ++e;
480    }
481
482    /// \brief Returns node iterator pointing to the head node of the
483    /// given edge iterator.
484    NodeIt head(const EdgeIt& e) const {
485      return NodeIt(*this, e.idx+1);
486    }
487
488    /// \brief Returns node iterator pointing to the tail node of the
489    /// given edge iterator.
490    NodeIt tail(const EdgeIt& e) const {
491      return NodeIt(*this, e.idx);
492    }
493
494
495
496    /**
497     * \brief Iterator class to iterate on the edges of the paths
498     *
499     * \ingroup paths
500     * This class is used to iterate on the edges of the paths
501     *
502     * Of course it converts to Graph::Edge
503     *
504     * \todo Its interface differs from the standard edge iterator.
505     * Yes, it shouldn't.
506     */
507    class EdgeIt {
508      friend class UndirPath;
509
510      int idx;
511      const UndirPath *p;
512    public:
513      /// Default constructor
514      EdgeIt() {}
515      /// Invalid constructor
516      EdgeIt(Invalid) : idx(-1), p(0) {}
517      /// Constructor with starting point
518      EdgeIt(const UndirPath &_p, int _idx = 0) :
519        idx(_idx), p(&_p) { validate(); }
520
521      ///Validity check
522      bool valid() const { return idx!=-1; }
523
524      ///Conversion to Graph::Edge
525      operator GraphEdge () const {
526        return valid() ? p->edges[idx] : INVALID;
527      }
528      /// Next edge
529     EdgeIt& operator++() { ++idx; validate(); return *this; }
530
531      /// Comparison operator
532      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
533      /// Comparison operator
534      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
535      /// Comparison operator
536      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
537
538    private:
539      // FIXME: comparison between signed and unsigned...
540      // Jo ez igy? Vagy esetleg legyen a length() int?
541      void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
542    };
543
544    /**
545     * \brief Iterator class to iterate on the nodes of the paths
546     *
547     * \ingroup paths
548     * This class is used to iterate on the nodes of the paths
549     *
550     * Of course it converts to Graph::Node
551     *
552     * \todo Its interface differs from the standard node iterator.
553     * Yes, it shouldn't.
554     */
555    class NodeIt {
556      friend class UndirPath;
557
558      int idx;
559      const UndirPath *p;
560    public:
561      /// Default constructor
562      NodeIt() {}
563      /// Invalid constructor
564      NodeIt(Invalid) : idx(-1), p(0) {}
565      /// Constructor with starting point
566      NodeIt(const UndirPath &_p, int _idx = 0) :
567        idx(_idx), p(&_p) { validate(); }
568
569      ///Validity check
570      bool valid() const { return idx!=-1; }
571
572      ///Conversion to Graph::Node
573      operator const GraphNode& () const {
574        if(idx >= p->length())
575          return p->head();
576        else if(idx >= 0)
577          return p->gr->tail(p->edges[idx]);
578        else
579          return INVALID;
580      }
581      /// Next node
582      NodeIt& operator++() { ++idx; validate(); return *this; }
583
584      /// Comparison operator
585      bool operator==(const NodeIt& e) const { return idx==e.idx; }
586      /// Comparison operator
587      bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
588       /// Comparison operator
589     bool operator<(const NodeIt& e) const { return idx<e.idx; }
590
591    private:
592      void validate() { if( size_t(idx) > p->length() ) idx=-1; }
593    };
594
595    friend class Builder;   
596
597    /**
598     * \brief Class to build paths
599     *
600     * \ingroup paths
601     * This class is used to fill a path with edges.
602     *
603     * You can push new edges to the front and to the back of the path in
604     * arbitrary order then you should commit these changes to the graph.
605     *
606     * Fundamentally, for most "Paths" (classes fulfilling the
607     * PathConcept) while the builder is active (after the first modifying
608     * operation and until the commit()) the original Path is in a
609     * "transitional" state (operations ot it have undefined result). But
610     * in the case of UndirPath the original path is unchanged until the
611     * commit. However we don't recomend that you use this feature.
612     */
613    class Builder {
614      UndirPath &P;
615      Container front, back;
616
617    public:
618      ///\param _P the path you want to fill in.
619      ///
620      Builder(UndirPath &_P) : P(_P) {}
621
622      /// Sets the starting node of the path.
623     
624      /// Sets the starting node of the path. Edge added to the path
625      /// afterwards have to be incident to this node.
626      /// It should be called iff the path is empty and before any call to
627      /// \ref pushFront() or \ref pushBack()
628      void setStartNode(const GraphNode &) {}
629
630      ///Push a new edge to the front of the path
631
632      ///Push a new edge to the front of the path.
633      ///\sa setStartNode
634      void pushFront(const GraphEdge& e) {
635        front.push_back(e);
636      }
637
638      ///Push a new edge to the back of the path
639
640      ///Push a new edge to the back of the path.
641      ///\sa setStartNode
642      void pushBack(const GraphEdge& e) {
643        back.push_back(e);
644      }
645
646      ///Commit the changes to the path.
647      void commit() {
648        if( !(front.empty() && back.empty()) ) {
649          Container tmp;
650          tmp.reserve(front.size()+back.size()+P.length());
651          tmp.insert(tmp.end(), front.rbegin(), front.rend());
652          tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
653          tmp.insert(tmp.end(), back.begin(), back.end());
654          P.edges.swap(tmp);
655          front.clear();
656          back.clear();
657        }
658      }
659
660      // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
661      // Hogy kenyelmes egy ilyet hasznalni?
662
663      ///Reserve storage for the builder in advance.
664
665      ///If you know an reasonable upper bound of the number of the edges
666      ///to add, using this function you can speed up the building.
667       void reserve(size_t r) {
668        front.reserve(r);
669        back.reserve(r);
670      }
671
672      void reserveFront(size_t r) {}
673      void reserveBack(size_t r) {}
674
675    private:
676      bool empty() {
677        return front.empty() && back.empty() && P.empty();
678      }
679
680      GraphNode tail() const {
681        if( ! front.empty() )
682          return P.gr->tail(front[front.size()-1]);
683        else if( ! P.empty() )
684          return P.gr->tail(P.edges[0]);
685        else if( ! back.empty() )
686          return P.gr->tail(back[0]);
687        else
688          return INVALID;
689      }
690      GraphNode head() const {
691        if( ! back.empty() )
692          return P.gr->head(back[back.size()-1]);
693        else if( ! P.empty() )
694          return P.gr->head(P.edges[P.length()-1]);
695        else if( ! front.empty() )
696          return P.gr->head(front[0]);
697        else
698          return INVALID;
699      }
700
701    };
702
703  };
704
705
706
707
708
709
710
711
712
713
714  /**********************************************************************/
715
716
717  /* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata
718     elott. Eleg bonyinak nez ki, ahogyan azokat az STL-ben hasznaljak. */
719
720  template<typename Graph>
721  class DynamicPath {
722
723  public:
724    typedef typename Graph::Edge GraphEdge;
725    typedef typename Graph::Node GraphNode;
726    class NodeIt;
727    class EdgeIt;
728
729  protected:
730    Graph& G;
731    // FIXME: ehelyett eleg lenne tarolni ket boolt: a ket szelso el
732    // iranyitasat:
733    GraphNode _first, _last;
734    typedef std::deque<GraphEdge> Container;
735    Container edges;
736
737  public:
738
739    DynamicPath(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {}
740
741    /// Subpath defined by two nodes.
742    /// Nodes may be in reversed order, then
743    /// we contstruct the reversed path.
744    DynamicPath(const DynamicPath &P, const NodeIt &a, const NodeIt &b);
745    /// Subpath defined by two edges. Contains edges in [a,b)
746    /// It is an error if the two edges are not in order!
747    DynamicPath(const DynamicPath &P, const EdgeIt &a, const EdgeIt &b);
748   
749    size_t length() const { return edges.size(); }
750    GraphNode tail() const { return _first; }
751    GraphNode head() const { return _last; }
752
753    NodeIt& first(NodeIt &n) const { return nth(n, 0); }
754    EdgeIt& first(EdgeIt &e) const { return nth(e, 0); }
755    template<typename It>
756    It first() const {
757      It e;
758      first(e);
759      return e;
760    }
761
762    NodeIt& nth(NodeIt &, size_t) const;
763    EdgeIt& nth(EdgeIt &, size_t) const;
764    template<typename It>
765    It nth(size_t n) const {
766      It e;
767      nth(e, n);
768      return e;
769    }
770
771    bool valid(const NodeIt &n) const { return n.idx <= length(); }
772    bool valid(const EdgeIt &e) const { return e.it < edges.end(); }
773
774    bool isForward(const EdgeIt &e) const { return e.forw; }
775
776    /// index of a node on the path. Returns length+2 for the invalid NodeIt
777    int index(const NodeIt &n) const { return n.idx; }
778    /// index of an edge on the path. Returns length+1 for the invalid EdgeIt
779    int index(const EdgeIt &e) const { return e.it - edges.begin(); }
780
781    EdgeIt& next(EdgeIt &e) const;
782    NodeIt& next(NodeIt &n) const;
783    template <typename It>
784    It getNext(It it) const {
785      It tmp(it); return next(tmp);
786    }
787
788    // A path is constructed using the following four functions.
789    // They return false if the requested operation is inconsistent
790    // with the path constructed so far.
791    // If your path has only one edge you MUST set either "from" or "to"!
792    // So you probably SHOULD call it in any case to be safe (and check the
793    // returned value to check if your path is consistent with your idea).
794    bool pushFront(const GraphEdge &e);
795    bool pushBack(const GraphEdge &e);
796    bool setFrom(const GraphNode &n);
797    bool setTo(const GraphNode &n);
798
799    // WARNING: these two functions return the head/tail of an edge with
800    // respect to the direction of the path!
801    // So G.head(P.graphEdge(e)) == P.graphNode(P.head(e)) holds only if
802    // P.forward(e) is true (or the edge is a loop)!
803    NodeIt head(const EdgeIt& e) const;
804    NodeIt tail(const EdgeIt& e) const;
805
806    // FIXME: ezeknek valami jobb nev kellene!!!
807    GraphEdge graphEdge(const EdgeIt& e) const;
808    GraphNode graphNode(const NodeIt& n) const;
809
810
811    /*** Iterator classes ***/
812    class EdgeIt {
813      friend class DynamicPath;
814
815      typename Container::const_iterator it;
816      bool forw;
817    public:
818      // FIXME: jarna neki ilyen is...
819      // EdgeIt(Invalid);
820
821      bool forward() const { return forw; }
822
823      bool operator==(const EdgeIt& e) const { return it==e.it; }
824      bool operator!=(const EdgeIt& e) const { return it!=e.it; }
825      bool operator<(const EdgeIt& e) const { return it<e.it; }
826    };
827
828    class NodeIt {
829      friend class DynamicPath;
830
831      size_t idx;
832      bool tail;  // Is this node the tail of the edge with same idx?
833
834    public:
835      // FIXME: jarna neki ilyen is...
836      // NodeIt(Invalid);
837
838      bool operator==(const NodeIt& n) const { return idx==n.idx; }
839      bool operator!=(const NodeIt& n) const { return idx!=n.idx; }
840      bool operator<(const NodeIt& n) const { return idx<n.idx; }
841    };
842
843  private:
844    bool edgeIncident(const GraphEdge &e, const GraphNode &a,
845                      GraphNode &b);
846    bool connectTwoEdges(const GraphEdge &e, const GraphEdge &f);
847  };
848
849  template<typename Gr>
850  typename DynamicPath<Gr>::EdgeIt&
851  DynamicPath<Gr>::next(DynamicPath::EdgeIt &e) const {
852    if( e.it == edges.end() )
853      return e;
854
855    GraphNode common_node = ( e.forw ? G.head(*e.it) : G.tail(*e.it) );
856    ++e.it;
857
858    // Invalid edgeit is always forward :)
859    if( e.it == edges.end() ) {
860      e.forw = true;
861      return e;
862    }
863
864    e.forw = ( G.tail(*e.it) == common_node );
865    return e;
866  }
867
868  template<typename Gr>
869  typename DynamicPath<Gr>::NodeIt& DynamicPath<Gr>::next(NodeIt &n) const {
870    if( n.idx >= length() ) {
871      // FIXME: invalid
872      n.idx = length()+1;
873      return n;
874    }
875
876   
877    GraphNode next_node = ( n.tail ? G.head(edges[n.idx]) :
878                              G.tail(edges[n.idx]) );
879    ++n.idx;
880    if( n.idx < length() ) {
881      n.tail = ( next_node == G.tail(edges[n.idx]) );
882    }
883    else {
884      n.tail = true;
885    }
886
887    return n;
888  }
889
890  template<typename Gr>
891  bool DynamicPath<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a,
892                          GraphNode &b) {
893    if( G.tail(e) == a ) {
894      b=G.head(e);
895      return true;
896    }
897    if( G.head(e) == a ) {
898      b=G.tail(e);
899      return true;
900    }
901    return false;
902  }
903
904  template<typename Gr>
905  bool DynamicPath<Gr>::connectTwoEdges(const GraphEdge &e,
906                             const GraphEdge &f) {
907    if( edgeIncident(f, G.tail(e), _last) ) {
908      _first = G.head(e);
909      return true;
910    }
911    if( edgeIncident(f, G.head(e), _last) ) {
912      _first = G.tail(e);
913      return true;
914    }
915    return false;
916  }
917
918  template<typename Gr>
919  bool DynamicPath<Gr>::pushFront(const GraphEdge &e) {
920    if( G.valid(_first) ) {
921        if( edgeIncident(e, _first, _first) ) {
922          edges.push_front(e);
923          return true;
924        }
925        else
926          return false;
927    }
928    else if( length() < 1 || connectTwoEdges(e, edges[0]) ) {
929      edges.push_front(e);
930      return true;
931    }
932    else
933      return false;
934  }
935
936  template<typename Gr>
937  bool DynamicPath<Gr>::pushBack(const GraphEdge &e) {
938    if( G.valid(_last) ) {
939        if( edgeIncident(e, _last, _last) ) {
940          edges.push_back(e);
941          return true;
942        }
943        else
944          return false;
945    }
946    else if( length() < 1 || connectTwoEdges(edges[0], e) ) {
947      edges.push_back(e);
948      return true;
949    }
950    else
951      return false;
952  }
953
954
955  template<typename Gr>
956  bool DynamicPath<Gr>::setFrom(const GraphNode &n) {
957    if( G.valid(_first) ) {
958      return _first == n;
959    }
960    else {
961      if( length() > 0) {
962        if( edgeIncident(edges[0], n, _last) ) {
963          _first = n;
964          return true;
965        }
966        else return false;
967      }
968      else {
969        _first = _last = n;
970        return true;
971      }
972    }
973  }
974
975  template<typename Gr>
976  bool DynamicPath<Gr>::setTo(const GraphNode &n) {
977    if( G.valid(_last) ) {
978      return _last == n;
979    }
980    else {
981      if( length() > 0) {
982        if( edgeIncident(edges[0], n, _first) ) {
983          _last = n;
984          return true;
985        }
986        else return false;
987      }
988      else {
989        _first = _last = n;
990        return true;
991      }
992    }
993  }
994
995
996  template<typename Gr>
997  typename DynamicPath<Gr>::NodeIt
998  DynamicPath<Gr>::tail(const EdgeIt& e) const {
999    NodeIt n;
1000
1001    if( e.it == edges.end() ) {
1002      // FIXME: invalid-> invalid
1003      n.idx = length() + 1;
1004      n.tail = true;
1005      return n;
1006    }
1007
1008    n.idx = e.it-edges.begin();
1009    n.tail = e.forw;
1010    return n;
1011  }
1012
1013  template<typename Gr>
1014  typename DynamicPath<Gr>::NodeIt
1015  DynamicPath<Gr>::head(const EdgeIt& e) const {
1016    if( e.it == edges.end()-1 ) {
1017      return _last;
1018    }
1019
1020    EdgeIt next_edge = e;
1021    next(next_edge);
1022    return tail(next_edge);
1023  }
1024     
1025  template<typename Gr>
1026  typename DynamicPath<Gr>::GraphEdge
1027  DynamicPath<Gr>::graphEdge(const EdgeIt& e) const {
1028    if( e.it != edges.end() ) {
1029      return *e.it;
1030    }
1031    else {
1032      return INVALID;
1033    }
1034  }
1035 
1036  template<typename Gr>
1037  typename DynamicPath<Gr>::GraphNode
1038  DynamicPath<Gr>::graphNode(const NodeIt& n) const {
1039    if( n.idx < length() ) {
1040      return n.tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]);
1041    }
1042    else if( n.idx == length() ) {
1043      return _last;
1044    }
1045    else {
1046      return INVALID;
1047    }
1048  }
1049
1050  template<typename Gr>
1051  typename DynamicPath<Gr>::EdgeIt&
1052  DynamicPath<Gr>::nth(EdgeIt &e, size_t k) const {
1053    if( k>=length() ) {
1054      // FIXME: invalid EdgeIt
1055      e.it = edges.end();
1056      e.forw = true;
1057      return e;
1058    }
1059
1060    e.it = edges.begin()+k;
1061    if(k==0) {
1062      e.forw = ( G.tail(*e.it) == _first );
1063    }
1064    else {
1065      e.forw = ( G.tail(*e.it) == G.tail(edges[k-1]) ||
1066                 G.tail(*e.it) == G.head(edges[k-1]) );
1067    }
1068    return e;
1069  }
1070   
1071  template<typename Gr>
1072  typename DynamicPath<Gr>::NodeIt&
1073  DynamicPath<Gr>::nth(NodeIt &n, size_t k) const {
1074    if( k>length() ) {
1075      // FIXME: invalid NodeIt
1076      n.idx = length()+1;
1077      n.tail = true;
1078      return n;
1079    }
1080    if( k==length() ) {
1081      n.idx = length();
1082      n.tail = true;
1083      return n;
1084    }
1085    n = tail(nth<EdgeIt>(k));
1086    return n;
1087  }
1088
1089  // Reszut konstruktorok:
1090
1091
1092  template<typename Gr>
1093  DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const EdgeIt &a,
1094                               const EdgeIt &b) :
1095    G(P.G), edges(a.it, b.it)    // WARNING: if b.it < a.it this will blow up!
1096  {
1097    if( G.valid(P._first) && a.it < P.edges.end() ) {
1098      _first = ( a.forw ? G.tail(*a.it) : G.head(*a.it) );
1099      if( b.it < P.edges.end() ) {
1100        _last = ( b.forw ? G.tail(*b.it) : G.head(*b.it) );
1101      }
1102      else {
1103        _last = P._last;
1104      }
1105    }
1106  }
1107
1108  template<typename Gr>
1109  DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const NodeIt &a,
1110                               const NodeIt &b) : G(P.G)
1111  {
1112    if( !P.valid(a) || !P.valid(b) )
1113      return;
1114
1115    int ai = a.idx, bi = b.idx;
1116    if( bi<ai )
1117      std::swap(ai,bi);
1118   
1119    edges.resize(bi-ai);
1120    copy(P.edges.begin()+ai, P.edges.begin()+bi, edges.begin());
1121
1122    _first = P.graphNode(a);
1123    _last = P.graphNode(b);
1124  }
1125
1126  ///@}
1127
1128} // namespace hugo
1129
1130#endif // HUGO_PATH_H
Note: See TracBrowser for help on using the repository browser.