COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/path.h @ 834:1dd3167db044

Last change on this file since 834:1dd3167db044 was 834:1dd3167db044, checked in by Hegyi Péter, 19 years ago

There is no runtime debug in path.h

File size: 29.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      // 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        if( !empty() && P.gr->tail(e)!=head() ) {
644          fault("UndirPath::Builder::pushBack: nonincident edge");
645        }
646        back.push_back(e);
647      }
648
649      ///Commit the changes to the path.
650      void commit() {
651        if( !(front.empty() && back.empty()) ) {
652          Container tmp;
653          tmp.reserve(front.size()+back.size()+P.length());
654          tmp.insert(tmp.end(), front.rbegin(), front.rend());
655          tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
656          tmp.insert(tmp.end(), back.begin(), back.end());
657          P.edges.swap(tmp);
658          front.clear();
659          back.clear();
660        }
661      }
662
663      // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
664      // Hogy kenyelmes egy ilyet hasznalni?
665
666      ///Reserve storage for the builder in advance.
667
668      ///If you know an reasonable upper bound of the number of the edges
669      ///to add, using this function you can speed up the building.
670       void reserve(size_t r) {
671        front.reserve(r);
672        back.reserve(r);
673      }
674
675      void reserveFront(size_t r) {}
676      void reserveBack(size_t r) {}
677
678    private:
679      bool empty() {
680        return front.empty() && back.empty() && P.empty();
681      }
682
683      GraphNode tail() const {
684        if( ! front.empty() )
685          return P.gr->tail(front[front.size()-1]);
686        else if( ! P.empty() )
687          return P.gr->tail(P.edges[0]);
688        else if( ! back.empty() )
689          return P.gr->tail(back[0]);
690        else
691          return INVALID;
692      }
693      GraphNode head() const {
694        if( ! back.empty() )
695          return P.gr->head(back[back.size()-1]);
696        else if( ! P.empty() )
697          return P.gr->head(P.edges[P.length()-1]);
698        else if( ! front.empty() )
699          return P.gr->head(front[0]);
700        else
701          return INVALID;
702      }
703
704    };
705
706  };
707
708
709
710
711
712
713
714
715
716
717  /**********************************************************************/
718
719
720  /* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata
721     elott. Eleg bonyinak nez ki, ahogyan azokat az STL-ben hasznaljak. */
722
723  template<typename Graph>
724  class DynamicPath {
725
726  public:
727    typedef typename Graph::Edge GraphEdge;
728    typedef typename Graph::Node GraphNode;
729    class NodeIt;
730    class EdgeIt;
731
732  protected:
733    Graph& G;
734    // FIXME: ehelyett eleg lenne tarolni ket boolt: a ket szelso el
735    // iranyitasat:
736    GraphNode _first, _last;
737    typedef std::deque<GraphEdge> Container;
738    Container edges;
739
740  public:
741
742    DynamicPath(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {}
743
744    /// Subpath defined by two nodes.
745    /// Nodes may be in reversed order, then
746    /// we contstruct the reversed path.
747    DynamicPath(const DynamicPath &P, const NodeIt &a, const NodeIt &b);
748    /// Subpath defined by two edges. Contains edges in [a,b)
749    /// It is an error if the two edges are not in order!
750    DynamicPath(const DynamicPath &P, const EdgeIt &a, const EdgeIt &b);
751   
752    size_t length() const { return edges.size(); }
753    GraphNode tail() const { return _first; }
754    GraphNode head() const { return _last; }
755
756    NodeIt& first(NodeIt &n) const { return nth(n, 0); }
757    EdgeIt& first(EdgeIt &e) const { return nth(e, 0); }
758    template<typename It>
759    It first() const {
760      It e;
761      first(e);
762      return e;
763    }
764
765    NodeIt& nth(NodeIt &, size_t) const;
766    EdgeIt& nth(EdgeIt &, size_t) const;
767    template<typename It>
768    It nth(size_t n) const {
769      It e;
770      nth(e, n);
771      return e;
772    }
773
774    bool valid(const NodeIt &n) const { return n.idx <= length(); }
775    bool valid(const EdgeIt &e) const { return e.it < edges.end(); }
776
777    bool isForward(const EdgeIt &e) const { return e.forw; }
778
779    /// index of a node on the path. Returns length+2 for the invalid NodeIt
780    int index(const NodeIt &n) const { return n.idx; }
781    /// index of an edge on the path. Returns length+1 for the invalid EdgeIt
782    int index(const EdgeIt &e) const { return e.it - edges.begin(); }
783
784    EdgeIt& next(EdgeIt &e) const;
785    NodeIt& next(NodeIt &n) const;
786    template <typename It>
787    It getNext(It it) const {
788      It tmp(it); return next(tmp);
789    }
790
791    // A path is constructed using the following four functions.
792    // They return false if the requested operation is inconsistent
793    // with the path constructed so far.
794    // If your path has only one edge you MUST set either "from" or "to"!
795    // So you probably SHOULD call it in any case to be safe (and check the
796    // returned value to check if your path is consistent with your idea).
797    bool pushFront(const GraphEdge &e);
798    bool pushBack(const GraphEdge &e);
799    bool setFrom(const GraphNode &n);
800    bool setTo(const GraphNode &n);
801
802    // WARNING: these two functions return the head/tail of an edge with
803    // respect to the direction of the path!
804    // So G.head(P.graphEdge(e)) == P.graphNode(P.head(e)) holds only if
805    // P.forward(e) is true (or the edge is a loop)!
806    NodeIt head(const EdgeIt& e) const;
807    NodeIt tail(const EdgeIt& e) const;
808
809    // FIXME: ezeknek valami jobb nev kellene!!!
810    GraphEdge graphEdge(const EdgeIt& e) const;
811    GraphNode graphNode(const NodeIt& n) const;
812
813
814    /*** Iterator classes ***/
815    class EdgeIt {
816      friend class DynamicPath;
817
818      typename Container::const_iterator it;
819      bool forw;
820    public:
821      // FIXME: jarna neki ilyen is...
822      // EdgeIt(Invalid);
823
824      bool forward() const { return forw; }
825
826      bool operator==(const EdgeIt& e) const { return it==e.it; }
827      bool operator!=(const EdgeIt& e) const { return it!=e.it; }
828      bool operator<(const EdgeIt& e) const { return it<e.it; }
829    };
830
831    class NodeIt {
832      friend class DynamicPath;
833
834      size_t idx;
835      bool tail;  // Is this node the tail of the edge with same idx?
836
837    public:
838      // FIXME: jarna neki ilyen is...
839      // NodeIt(Invalid);
840
841      bool operator==(const NodeIt& n) const { return idx==n.idx; }
842      bool operator!=(const NodeIt& n) const { return idx!=n.idx; }
843      bool operator<(const NodeIt& n) const { return idx<n.idx; }
844    };
845
846  private:
847    bool edgeIncident(const GraphEdge &e, const GraphNode &a,
848                      GraphNode &b);
849    bool connectTwoEdges(const GraphEdge &e, const GraphEdge &f);
850  };
851
852  template<typename Gr>
853  typename DynamicPath<Gr>::EdgeIt&
854  DynamicPath<Gr>::next(DynamicPath::EdgeIt &e) const {
855    if( e.it == edges.end() )
856      return e;
857
858    GraphNode common_node = ( e.forw ? G.head(*e.it) : G.tail(*e.it) );
859    ++e.it;
860
861    // Invalid edgeit is always forward :)
862    if( e.it == edges.end() ) {
863      e.forw = true;
864      return e;
865    }
866
867    e.forw = ( G.tail(*e.it) == common_node );
868    return e;
869  }
870
871  template<typename Gr>
872  typename DynamicPath<Gr>::NodeIt& DynamicPath<Gr>::next(NodeIt &n) const {
873    if( n.idx >= length() ) {
874      // FIXME: invalid
875      n.idx = length()+1;
876      return n;
877    }
878
879   
880    GraphNode next_node = ( n.tail ? G.head(edges[n.idx]) :
881                              G.tail(edges[n.idx]) );
882    ++n.idx;
883    if( n.idx < length() ) {
884      n.tail = ( next_node == G.tail(edges[n.idx]) );
885    }
886    else {
887      n.tail = true;
888    }
889
890    return n;
891  }
892
893  template<typename Gr>
894  bool DynamicPath<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a,
895                          GraphNode &b) {
896    if( G.tail(e) == a ) {
897      b=G.head(e);
898      return true;
899    }
900    if( G.head(e) == a ) {
901      b=G.tail(e);
902      return true;
903    }
904    return false;
905  }
906
907  template<typename Gr>
908  bool DynamicPath<Gr>::connectTwoEdges(const GraphEdge &e,
909                             const GraphEdge &f) {
910    if( edgeIncident(f, G.tail(e), _last) ) {
911      _first = G.head(e);
912      return true;
913    }
914    if( edgeIncident(f, G.head(e), _last) ) {
915      _first = G.tail(e);
916      return true;
917    }
918    return false;
919  }
920
921  template<typename Gr>
922  bool DynamicPath<Gr>::pushFront(const GraphEdge &e) {
923    if( G.valid(_first) ) {
924        if( edgeIncident(e, _first, _first) ) {
925          edges.push_front(e);
926          return true;
927        }
928        else
929          return false;
930    }
931    else if( length() < 1 || connectTwoEdges(e, edges[0]) ) {
932      edges.push_front(e);
933      return true;
934    }
935    else
936      return false;
937  }
938
939  template<typename Gr>
940  bool DynamicPath<Gr>::pushBack(const GraphEdge &e) {
941    if( G.valid(_last) ) {
942        if( edgeIncident(e, _last, _last) ) {
943          edges.push_back(e);
944          return true;
945        }
946        else
947          return false;
948    }
949    else if( length() < 1 || connectTwoEdges(edges[0], e) ) {
950      edges.push_back(e);
951      return true;
952    }
953    else
954      return false;
955  }
956
957
958  template<typename Gr>
959  bool DynamicPath<Gr>::setFrom(const GraphNode &n) {
960    if( G.valid(_first) ) {
961      return _first == n;
962    }
963    else {
964      if( length() > 0) {
965        if( edgeIncident(edges[0], n, _last) ) {
966          _first = n;
967          return true;
968        }
969        else return false;
970      }
971      else {
972        _first = _last = n;
973        return true;
974      }
975    }
976  }
977
978  template<typename Gr>
979  bool DynamicPath<Gr>::setTo(const GraphNode &n) {
980    if( G.valid(_last) ) {
981      return _last == n;
982    }
983    else {
984      if( length() > 0) {
985        if( edgeIncident(edges[0], n, _first) ) {
986          _last = n;
987          return true;
988        }
989        else return false;
990      }
991      else {
992        _first = _last = n;
993        return true;
994      }
995    }
996  }
997
998
999  template<typename Gr>
1000  typename DynamicPath<Gr>::NodeIt
1001  DynamicPath<Gr>::tail(const EdgeIt& e) const {
1002    NodeIt n;
1003
1004    if( e.it == edges.end() ) {
1005      // FIXME: invalid-> invalid
1006      n.idx = length() + 1;
1007      n.tail = true;
1008      return n;
1009    }
1010
1011    n.idx = e.it-edges.begin();
1012    n.tail = e.forw;
1013    return n;
1014  }
1015
1016  template<typename Gr>
1017  typename DynamicPath<Gr>::NodeIt
1018  DynamicPath<Gr>::head(const EdgeIt& e) const {
1019    if( e.it == edges.end()-1 ) {
1020      return _last;
1021    }
1022
1023    EdgeIt next_edge = e;
1024    next(next_edge);
1025    return tail(next_edge);
1026  }
1027     
1028  template<typename Gr>
1029  typename DynamicPath<Gr>::GraphEdge
1030  DynamicPath<Gr>::graphEdge(const EdgeIt& e) const {
1031    if( e.it != edges.end() ) {
1032      return *e.it;
1033    }
1034    else {
1035      return INVALID;
1036    }
1037  }
1038 
1039  template<typename Gr>
1040  typename DynamicPath<Gr>::GraphNode
1041  DynamicPath<Gr>::graphNode(const NodeIt& n) const {
1042    if( n.idx < length() ) {
1043      return n.tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]);
1044    }
1045    else if( n.idx == length() ) {
1046      return _last;
1047    }
1048    else {
1049      return INVALID;
1050    }
1051  }
1052
1053  template<typename Gr>
1054  typename DynamicPath<Gr>::EdgeIt&
1055  DynamicPath<Gr>::nth(EdgeIt &e, size_t k) const {
1056    if( k>=length() ) {
1057      // FIXME: invalid EdgeIt
1058      e.it = edges.end();
1059      e.forw = true;
1060      return e;
1061    }
1062
1063    e.it = edges.begin()+k;
1064    if(k==0) {
1065      e.forw = ( G.tail(*e.it) == _first );
1066    }
1067    else {
1068      e.forw = ( G.tail(*e.it) == G.tail(edges[k-1]) ||
1069                 G.tail(*e.it) == G.head(edges[k-1]) );
1070    }
1071    return e;
1072  }
1073   
1074  template<typename Gr>
1075  typename DynamicPath<Gr>::NodeIt&
1076  DynamicPath<Gr>::nth(NodeIt &n, size_t k) const {
1077    if( k>length() ) {
1078      // FIXME: invalid NodeIt
1079      n.idx = length()+1;
1080      n.tail = true;
1081      return n;
1082    }
1083    if( k==length() ) {
1084      n.idx = length();
1085      n.tail = true;
1086      return n;
1087    }
1088    n = tail(nth<EdgeIt>(k));
1089    return n;
1090  }
1091
1092  // Reszut konstruktorok:
1093
1094
1095  template<typename Gr>
1096  DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const EdgeIt &a,
1097                               const EdgeIt &b) :
1098    G(P.G), edges(a.it, b.it)    // WARNING: if b.it < a.it this will blow up!
1099  {
1100    if( G.valid(P._first) && a.it < P.edges.end() ) {
1101      _first = ( a.forw ? G.tail(*a.it) : G.head(*a.it) );
1102      if( b.it < P.edges.end() ) {
1103        _last = ( b.forw ? G.tail(*b.it) : G.head(*b.it) );
1104      }
1105      else {
1106        _last = P._last;
1107      }
1108    }
1109  }
1110
1111  template<typename Gr>
1112  DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const NodeIt &a,
1113                               const NodeIt &b) : G(P.G)
1114  {
1115    if( !P.valid(a) || !P.valid(b) )
1116      return;
1117
1118    int ai = a.idx, bi = b.idx;
1119    if( bi<ai )
1120      std::swap(ai,bi);
1121   
1122    edges.resize(bi-ai);
1123    copy(P.edges.begin()+ai, P.edges.begin()+bi, edges.begin());
1124
1125    _first = P.graphNode(a);
1126    _last = P.graphNode(b);
1127  }
1128
1129  ///@}
1130
1131} // namespace hugo
1132
1133#endif // HUGO_PATH_H
Note: See TracBrowser for help on using the repository browser.