COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/path.h @ 831:b6ae3446098a

Last change on this file since 831:b6ae3446098a was 831:b6ae3446098a, checked in by Hegyi Péter, 16 years ago

The first version of new path test program. The old became old_path_test.

File size: 31.3 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#include <hugo/error.h>
32//#include <hugo/debug.h>
33
34namespace hugo {
35
36  /// \addtogroup paths
37  /// @{
38
39
40  //! \brief A structure for representing directed paths in a graph.
41  //!
42  //! A structure for representing directed path in a graph.
43  //! \param Graph The graph type in which the path is.
44  //! \param DM DebugMode, defaults to DefaultDebugMode.
45  //!
46  //! In a sense, the path can be treated as a graph, for is has \c NodeIt
47  //! and \c EdgeIt with the same usage. These types converts to the \c Node
48  //! and \c Edge of the original graph.
49  //!
50  //! \todo Thoroughfully check all the range and consistency tests.
51  template<typename Graph>
52  class DirPath {
53  public:
54    /// Edge type of the underlying graph.
55    typedef typename Graph::Edge GraphEdge;
56    /// Node type of the underlying graph.
57    typedef typename Graph::Node GraphNode;
58    class NodeIt;
59    class EdgeIt;
60
61  protected:
62    const Graph *gr;
63    typedef std::vector<GraphEdge> Container;
64    Container edges;
65
66  public:
67
68    /// \param _G The graph in which the path is.
69    ///
70    DirPath(const Graph &_G) : gr(&_G) {}
71
72    /// \brief Subpath constructor.
73    ///
74    /// Subpath defined by two nodes.
75    /// \warning It is an error if the two edges are not in order!
76    DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
77      if(!a.valid() || !b.valid) {
78        // FIXME: this check should be more elaborate...
79        fault("DirPath, subpath ctor: invalid bounding nodes");
80      }
81      gr = P.gr;
82      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
83    }
84
85    /// \brief Subpath constructor.
86    ///
87    /// Subpath defined by two edges. Contains edges in [a,b)
88    /// \warning It is an error if the two edges are not in order!
89    DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
90      if (!a.valid() || !b.valid) {
91        // FIXME: this check should be more elaborate...
92        fault("DirPath, subpath ctor: invalid bounding nodes");
93      }
94      gr = P.gr;
95      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
96    }
97
98    /// Length of the path.
99    size_t length() const { return edges.size(); }
100    /// Returns whether the path is empty.
101    bool empty() const { return edges.empty(); }
102
103    /// Resets the path to an empty path.
104    void clear() { edges.clear(); }
105
106    /// \brief Starting point of the path.
107    ///
108    /// Starting point of the path.
109    /// Returns INVALID if the path is empty.
110    GraphNode tail() const {
111      return empty() ? INVALID : gr->tail(edges[0]);
112    }
113    /// \brief End point of the path.
114    ///
115    /// End point of the path.
116    /// Returns INVALID if the path is empty.
117    GraphNode head() const {
118      return empty() ? INVALID : gr->head(edges[length()-1]);
119    }
120
121    /// \brief Initializes node or edge iterator to point to the first
122    /// node or edge.
123    ///
124    /// \sa nth
125    template<typename It>
126    It& first(It &i) const { return i=It(*this); }
127
128    /// \brief Initializes node iterator to point to the node of a given index.
129    NodeIt& nth(NodeIt &i, int n) const {
130      if(n<0 || n>int(length()))
131        fault("DirPath::nth: index out of range");
132      return i=NodeIt(*this, n);
133    }
134
135    /// \brief Initializes edge iterator to point to the edge of a given index.
136    EdgeIt& nth(EdgeIt &i, int n) const {
137      if(n<0 || n>=int(length()))
138        fault("DirPath::nth: index out of range");
139      return i=EdgeIt(*this, n);
140    }
141
142    /// Checks validity of a node or edge iterator.
143    template<typename It>
144    static
145    bool valid(const It &i) { return i.valid(); }
146
147    /// Steps the given node or edge iterator.
148    template<typename It>
149    static
150    It& next(It &e) {
151      if( !e.valid() )
152        fault("DirPath::next() on invalid iterator");
153      return ++e;
154    }
155
156    /// \brief Returns node iterator pointing to the head node of the
157    /// given edge iterator.
158    NodeIt head(const EdgeIt& e) const {
159      if( !e.valid() )
160        fault("DirPath::head() on invalid iterator");
161      return NodeIt(*this, e.idx+1);
162    }
163
164    /// \brief Returns node iterator pointing to the tail node of the
165    /// given edge iterator.
166    NodeIt tail(const EdgeIt& e) const {
167      if( !e.valid() )
168        fault("DirPath::tail() on invalid iterator");
169      return NodeIt(*this, e.idx);
170    }
171
172
173    /* Iterator classes */
174
175    /**
176     * \brief Iterator class to iterate on the edges of the paths
177     *
178     * \ingroup paths
179     * This class is used to iterate on the edges of the paths
180     *
181     * Of course it converts to Graph::Edge
182     *
183     * \todo Its interface differs from the standard edge iterator.
184     * Yes, it shouldn't.
185     */
186    class EdgeIt {
187      friend class DirPath;
188
189      int idx;
190      const DirPath *p;
191    public:
192      /// Default constructor
193      EdgeIt() {}
194      /// Invalid constructor
195      EdgeIt(Invalid) : idx(-1), p(0) {}
196      /// Constructor with starting point
197      EdgeIt(const DirPath &_p, int _idx = 0) :
198        idx(_idx), p(&_p) { validate(); }
199
200      ///Validity check
201      bool valid() const { return idx!=-1; }
202
203      ///Conversion to Graph::Edge
204      operator GraphEdge () const {
205        return valid() ? p->edges[idx] : INVALID;
206      }
207
208      /// Next edge
209      EdgeIt& operator++() { ++idx; validate(); return *this; }
210
211      /// Comparison operator
212      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
213      /// Comparison operator
214      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
215      /// Comparison operator
216      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
217
218    private:
219      // FIXME: comparison between signed and unsigned...
220      // Jo ez igy? Vagy esetleg legyen a length() int?
221      void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
222    };
223
224    /**
225     * \brief Iterator class to iterate on the nodes of the paths
226     *
227     * \ingroup paths
228     * This class is used to iterate on the nodes of the paths
229     *
230     * Of course it converts to Graph::Node
231     *
232     * \todo Its interface differs from the standard node iterator.
233     * Yes, it shouldn't.
234     */
235    class NodeIt {
236      friend class DirPath;
237
238      int idx;
239      const DirPath *p;
240    public:
241      /// Default constructor
242      NodeIt() {}
243      /// Invalid constructor
244      NodeIt(Invalid) : idx(-1), p(0) {}
245      /// Constructor with starting point
246      NodeIt(const DirPath &_p, int _idx = 0) :
247        idx(_idx), p(&_p) { validate(); }
248
249      ///Validity check
250      bool valid() const { return idx!=-1; }
251
252      ///Conversion to Graph::Node
253      operator const GraphNode& () const {
254        if(idx >= p->length())
255          return p->head();
256        else if(idx >= 0)
257          return p->gr->tail(p->edges[idx]);
258        else
259          return INVALID;
260      }
261      /// Next node
262      NodeIt& operator++() { ++idx; validate(); return *this; }
263
264      /// Comparison operator
265      bool operator==(const NodeIt& e) const { return idx==e.idx; }
266      /// Comparison operator
267      bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
268      /// Comparison operator
269      bool operator<(const NodeIt& e) const { return idx<e.idx; }
270
271    private:
272      void validate() { if( size_t(idx) > p->length() ) idx=-1; }
273    };
274
275    friend class Builder;   
276
277    /**
278     * \brief Class to build paths
279     *
280     * \ingroup paths
281     * This class is used to fill a path with edges.
282     *
283     * You can push new edges to the front and to the back of the path in
284     * arbitrary order then you should commit these changes to the graph.
285     *
286     * Fundamentally, for most "Paths" (classes fulfilling the
287     * PathConcept) while the builder is active (after the first modifying
288     * operation and until the commit()) the original Path is in a
289     * "transitional" state (operations on it have undefined result). But
290     * in the case of DirPath the original path remains unchanged until the
291     * commit. However we don't recomend that you use this feature.
292     */
293    class Builder {
294      DirPath &P;
295      Container front, back;
296
297    public:
298      ///\param _P the path you want to fill in.
299      ///
300      Builder(DirPath &_P) : P(_P) {}
301
302      /// Sets the starting node of the path.
303     
304      /// Sets the starting node of the path. Edge added to the path
305      /// afterwards have to be incident to this node.
306      /// It should be called iff the path is empty and before any call to
307      /// \ref pushFront() or \ref pushBack()
308      void setStartNode(const GraphNode &) {}
309
310      ///Push a new edge to the front of the path
311
312      ///Push a new edge to the front of the path.
313      ///\sa setStartNode
314      void pushFront(const GraphEdge& e) {
315        if( !empty() && P.gr->head(e)!=tail() ) {
316          fault("DirPath::Builder::pushFront: nonincident edge");
317        }
318        front.push_back(e);
319      }
320
321      ///Push a new edge to the back of the path
322
323      ///Push a new edge to the back of the path.
324      ///\sa setStartNode
325      void pushBack(const GraphEdge& e) {
326        if( !empty() && P.gr->tail(e)!=head() ) {
327          fault("DirPath::Builder::pushBack: nonincident edge");
328        }
329        back.push_back(e);
330      }
331
332      ///Commit the changes to the path.
333      void commit() {
334        if( !(front.empty() && back.empty()) ) {
335          Container tmp;
336          tmp.reserve(front.size()+back.size()+P.length());
337          tmp.insert(tmp.end(), front.rbegin(), front.rend());
338          tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
339          tmp.insert(tmp.end(), back.begin(), back.end());
340          P.edges.swap(tmp);
341          front.clear();
342          back.clear();
343        }
344      }
345
346      // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
347      // Hogy kenyelmes egy ilyet hasznalni?
348 
349      ///Reserve storage for the builder in advance.
350
351      ///If you know an reasonable upper bound of the number of the edges
352      ///to add, using this function you can speed up the building.
353      void reserve(size_t r) {
354        front.reserve(r);
355        back.reserve(r);
356      }
357
358      void reserveFront(size_t r) {}
359      void reserveBack(size_t r) {}
360
361    private:
362      bool empty() {
363        return front.empty() && back.empty() && P.empty();
364      }
365
366      GraphNode tail() const {
367        if( ! front.empty() )
368          return P.gr->tail(front[front.size()-1]);
369        else if( ! P.empty() )
370          return P.gr->tail(P.edges[0]);
371        else if( ! back.empty() )
372          return P.gr->tail(back[0]);
373        else
374          return INVALID;
375      }
376      GraphNode head() const {
377        if( ! back.empty() )
378          return P.gr->head(back[back.size()-1]);
379        else if( ! P.empty() )
380          return P.gr->head(P.edges[P.length()-1]);
381        else if( ! front.empty() )
382          return P.gr->head(front[0]);
383        else
384          return INVALID;
385      }
386
387    };
388
389  };
390
391
392
393
394
395
396
397
398
399
400  /**********************************************************************/
401
402
403  //! \brief A structure for representing undirected path in a graph.
404  //!
405  //! A structure for representing undirected path in a graph. Ie. this is
406  //! a path in a \e directed graph but the edges should not be directed
407  //! forward.
408  //!
409  //! \param Graph The graph type in which the path is.
410  //! \param DM DebugMode, defaults to DefaultDebugMode.
411  //!
412  //! In a sense, the path can be treated as a graph, for is has \c NodeIt
413  //! and \c EdgeIt with the same usage. These types converts to the \c Node
414  //! and \c Edge of the original graph.
415  //!
416  //! \todo Thoroughfully check all the range and consistency tests.
417  template<typename Graph>
418  class UndirPath {
419  public:
420    /// Edge type of the underlying graph.
421    typedef typename Graph::Edge GraphEdge;
422     /// Node type of the underlying graph.
423   typedef typename Graph::Node GraphNode;
424    class NodeIt;
425    class EdgeIt;
426
427  protected:
428    const Graph *gr;
429    typedef std::vector<GraphEdge> Container;
430    Container edges;
431
432  public:
433
434    /// \param _G The graph in which the path is.
435    ///
436    UndirPath(const Graph &_G) : gr(&_G) {}
437
438    /// \brief Subpath constructor.
439    ///
440    /// Subpath defined by two nodes.
441    /// \warning It is an error if the two edges are not in order!
442    UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
443      if(!a.valid() || !b.valid) {
444        // FIXME: this check should be more elaborate...
445        fault("UndirPath, subpath ctor: invalid bounding nodes");
446      }
447      gr = P.gr;
448      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
449    }
450
451    /// \brief Subpath constructor.
452    ///
453    /// Subpath defined by two edges. Contains edges in [a,b)
454    /// \warning It is an error if the two edges are not in order!
455    UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
456      if(!a.valid() || !b.valid) {
457        // FIXME: this check should be more elaborate...
458        fault("UndirPath, subpath ctor: invalid bounding nodes");
459      }
460      gr = P.gr;
461      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
462    }
463
464    /// Length of the path.
465    size_t length() const { return edges.size(); }
466    /// Returns whether the path is empty.
467    bool empty() const { return edges.empty(); }
468
469    /// Resets the path to an empty path.
470    void clear() { edges.clear(); }
471
472    /// \brief Starting point of the path.
473    ///
474    /// Starting point of the path.
475    /// Returns INVALID if the path is empty.
476    GraphNode tail() const {
477      return empty() ? INVALID : gr->tail(edges[0]);
478    }
479    /// \brief End point of the path.
480    ///
481    /// End point of the path.
482    /// Returns INVALID if the path is empty.
483    GraphNode head() const {
484      return empty() ? INVALID : gr->head(edges[length()-1]);
485    }
486
487    /// \brief Initializes node or edge iterator to point to the first
488    /// node or edge.
489    ///
490    /// \sa nth
491    template<typename It>
492    It& first(It &i) const { return i=It(*this); }
493
494    /// \brief Initializes node iterator to point to the node of a given index.
495    NodeIt& nth(NodeIt &i, int n) const {
496      if(n<0 || n>int(length()))
497        fault("UndirPath::nth: index out of range");
498      return i=NodeIt(*this, n);
499    }
500
501    /// \brief Initializes edge iterator to point to the edge of a given index.
502    EdgeIt& nth(EdgeIt &i, int n) const {
503      if(n<0 || n>=int(length()))
504        fault("UndirPath::nth: index out of range");
505      return i=EdgeIt(*this, n);
506    }
507
508    /// Checks validity of a node or edge iterator.
509    template<typename It>
510    static
511    bool valid(const It &i) { return i.valid(); }
512
513    /// Steps the given node or edge iterator.
514    template<typename It>
515    static
516    It& next(It &e) {
517      if( !e.valid() )
518        fault("UndirPath::next() on invalid iterator");
519      return ++e;
520    }
521
522    /// \brief Returns node iterator pointing to the head node of the
523    /// given edge iterator.
524    NodeIt head(const EdgeIt& e) const {
525      if( !e.valid() )
526        fault("UndirPath::head() on invalid iterator");
527      return NodeIt(*this, e.idx+1);
528    }
529
530    /// \brief Returns node iterator pointing to the tail node of the
531    /// given edge iterator.
532    NodeIt tail(const EdgeIt& e) const {
533      if( !e.valid() )
534        fault("UndirPath::tail() on invalid iterator");
535      return NodeIt(*this, e.idx);
536    }
537
538
539
540    /**
541     * \brief Iterator class to iterate on the edges of the paths
542     *
543     * \ingroup paths
544     * This class is used to iterate on the edges of the paths
545     *
546     * Of course it converts to Graph::Edge
547     *
548     * \todo Its interface differs from the standard edge iterator.
549     * Yes, it shouldn't.
550     */
551    class EdgeIt {
552      friend class UndirPath;
553
554      int idx;
555      const UndirPath *p;
556    public:
557      /// Default constructor
558      EdgeIt() {}
559      /// Invalid constructor
560      EdgeIt(Invalid) : idx(-1), p(0) {}
561      /// Constructor with starting point
562      EdgeIt(const UndirPath &_p, int _idx = 0) :
563        idx(_idx), p(&_p) { validate(); }
564
565      ///Validity check
566      bool valid() const { return idx!=-1; }
567
568      ///Conversion to Graph::Edge
569      operator GraphEdge () const {
570        return valid() ? p->edges[idx] : INVALID;
571      }
572      /// Next edge
573     EdgeIt& operator++() { ++idx; validate(); return *this; }
574
575      /// Comparison operator
576      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
577      /// Comparison operator
578      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
579      /// Comparison operator
580      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
581
582    private:
583      // FIXME: comparison between signed and unsigned...
584      // Jo ez igy? Vagy esetleg legyen a length() int?
585      void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
586    };
587
588    /**
589     * \brief Iterator class to iterate on the nodes of the paths
590     *
591     * \ingroup paths
592     * This class is used to iterate on the nodes of the paths
593     *
594     * Of course it converts to Graph::Node
595     *
596     * \todo Its interface differs from the standard node iterator.
597     * Yes, it shouldn't.
598     */
599    class NodeIt {
600      friend class UndirPath;
601
602      int idx;
603      const UndirPath *p;
604    public:
605      /// Default constructor
606      NodeIt() {}
607      /// Invalid constructor
608      NodeIt(Invalid) : idx(-1), p(0) {}
609      /// Constructor with starting point
610      NodeIt(const UndirPath &_p, int _idx = 0) :
611        idx(_idx), p(&_p) { validate(); }
612
613      ///Validity check
614      bool valid() const { return idx!=-1; }
615
616      ///Conversion to Graph::Node
617      operator const GraphNode& () const {
618        if(idx >= p->length())
619          return p->head();
620        else if(idx >= 0)
621          return p->gr->tail(p->edges[idx]);
622        else
623          return INVALID;
624      }
625      /// Next node
626      NodeIt& operator++() { ++idx; validate(); return *this; }
627
628      /// Comparison operator
629      bool operator==(const NodeIt& e) const { return idx==e.idx; }
630      /// Comparison operator
631      bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
632       /// Comparison operator
633     bool operator<(const NodeIt& e) const { return idx<e.idx; }
634
635    private:
636      void validate() { if( size_t(idx) > p->length() ) idx=-1; }
637    };
638
639    friend class Builder;   
640
641    /**
642     * \brief Class to build paths
643     *
644     * \ingroup paths
645     * This class is used to fill a path with edges.
646     *
647     * You can push new edges to the front and to the back of the path in
648     * arbitrary order then you should commit these changes to the graph.
649     *
650     * Fundamentally, for most "Paths" (classes fulfilling the
651     * PathConcept) while the builder is active (after the first modifying
652     * operation and until the commit()) the original Path is in a
653     * "transitional" state (operations ot it have undefined result). But
654     * in the case of UndirPath the original path is unchanged until the
655     * commit. However we don't recomend that you use this feature.
656     */
657    class Builder {
658      UndirPath &P;
659      Container front, back;
660
661    public:
662      ///\param _P the path you want to fill in.
663      ///
664      Builder(UndirPath &_P) : P(_P) {}
665
666      /// Sets the starting node of the path.
667     
668      /// Sets the starting node of the path. Edge added to the path
669      /// afterwards have to be incident to this node.
670      /// It should be called iff the path is empty and before any call to
671      /// \ref pushFront() or \ref pushBack()
672      void setStartNode(const GraphNode &) {}
673
674      ///Push a new edge to the front of the path
675
676      ///Push a new edge to the front of the path.
677      ///\sa setStartNode
678      void pushFront(const GraphEdge& e) {
679        if( !empty() && P.gr->head(e)!=tail() ) {
680          fault("UndirPath::Builder::pushFront: nonincident edge");
681        }
682        front.push_back(e);
683      }
684
685      ///Push a new edge to the back of the path
686
687      ///Push a new edge to the back of the path.
688      ///\sa setStartNode
689      void pushBack(const GraphEdge& e) {
690        if( !empty() && P.gr->tail(e)!=head() ) {
691          fault("UndirPath::Builder::pushBack: nonincident edge");
692        }
693        back.push_back(e);
694      }
695
696      ///Commit the changes to the path.
697      void commit() {
698        if( !(front.empty() && back.empty()) ) {
699          Container tmp;
700          tmp.reserve(front.size()+back.size()+P.length());
701          tmp.insert(tmp.end(), front.rbegin(), front.rend());
702          tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
703          tmp.insert(tmp.end(), back.begin(), back.end());
704          P.edges.swap(tmp);
705          front.clear();
706          back.clear();
707        }
708      }
709
710      // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
711      // Hogy kenyelmes egy ilyet hasznalni?
712
713      ///Reserve storage for the builder in advance.
714
715      ///If you know an reasonable upper bound of the number of the edges
716      ///to add, using this function you can speed up the building.
717       void reserve(size_t r) {
718        front.reserve(r);
719        back.reserve(r);
720      }
721
722      void reserveFront(size_t r) {}
723      void reserveBack(size_t r) {}
724
725    private:
726      bool empty() {
727        return front.empty() && back.empty() && P.empty();
728      }
729
730      GraphNode tail() const {
731        if( ! front.empty() )
732          return P.gr->tail(front[front.size()-1]);
733        else if( ! P.empty() )
734          return P.gr->tail(P.edges[0]);
735        else if( ! back.empty() )
736          return P.gr->tail(back[0]);
737        else
738          return INVALID;
739      }
740      GraphNode head() const {
741        if( ! back.empty() )
742          return P.gr->head(back[back.size()-1]);
743        else if( ! P.empty() )
744          return P.gr->head(P.edges[P.length()-1]);
745        else if( ! front.empty() )
746          return P.gr->head(front[0]);
747        else
748          return INVALID;
749      }
750
751    };
752
753  };
754
755
756
757
758
759
760
761
762
763
764  /**********************************************************************/
765
766
767  /* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata
768     elott. Eleg bonyinak nez ki, ahogyan azokat az STL-ben hasznaljak. */
769
770  template<typename Graph>
771  class DynamicPath {
772
773  public:
774    typedef typename Graph::Edge GraphEdge;
775    typedef typename Graph::Node GraphNode;
776    class NodeIt;
777    class EdgeIt;
778
779  protected:
780    Graph& G;
781    // FIXME: ehelyett eleg lenne tarolni ket boolt: a ket szelso el
782    // iranyitasat:
783    GraphNode _first, _last;
784    typedef std::deque<GraphEdge> Container;
785    Container edges;
786
787  public:
788
789    DynamicPath(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {}
790
791    /// Subpath defined by two nodes.
792    /// Nodes may be in reversed order, then
793    /// we contstruct the reversed path.
794    DynamicPath(const DynamicPath &P, const NodeIt &a, const NodeIt &b);
795    /// Subpath defined by two edges. Contains edges in [a,b)
796    /// It is an error if the two edges are not in order!
797    DynamicPath(const DynamicPath &P, const EdgeIt &a, const EdgeIt &b);
798   
799    size_t length() const { return edges.size(); }
800    GraphNode tail() const { return _first; }
801    GraphNode head() const { return _last; }
802
803    NodeIt& first(NodeIt &n) const { return nth(n, 0); }
804    EdgeIt& first(EdgeIt &e) const { return nth(e, 0); }
805    template<typename It>
806    It first() const {
807      It e;
808      first(e);
809      return e;
810    }
811
812    NodeIt& nth(NodeIt &, size_t) const;
813    EdgeIt& nth(EdgeIt &, size_t) const;
814    template<typename It>
815    It nth(size_t n) const {
816      It e;
817      nth(e, n);
818      return e;
819    }
820
821    bool valid(const NodeIt &n) const { return n.idx <= length(); }
822    bool valid(const EdgeIt &e) const { return e.it < edges.end(); }
823
824    bool isForward(const EdgeIt &e) const { return e.forw; }
825
826    /// index of a node on the path. Returns length+2 for the invalid NodeIt
827    int index(const NodeIt &n) const { return n.idx; }
828    /// index of an edge on the path. Returns length+1 for the invalid EdgeIt
829    int index(const EdgeIt &e) const { return e.it - edges.begin(); }
830
831    EdgeIt& next(EdgeIt &e) const;
832    NodeIt& next(NodeIt &n) const;
833    template <typename It>
834    It getNext(It it) const {
835      It tmp(it); return next(tmp);
836    }
837
838    // A path is constructed using the following four functions.
839    // They return false if the requested operation is inconsistent
840    // with the path constructed so far.
841    // If your path has only one edge you MUST set either "from" or "to"!
842    // So you probably SHOULD call it in any case to be safe (and check the
843    // returned value to check if your path is consistent with your idea).
844    bool pushFront(const GraphEdge &e);
845    bool pushBack(const GraphEdge &e);
846    bool setFrom(const GraphNode &n);
847    bool setTo(const GraphNode &n);
848
849    // WARNING: these two functions return the head/tail of an edge with
850    // respect to the direction of the path!
851    // So G.head(P.graphEdge(e)) == P.graphNode(P.head(e)) holds only if
852    // P.forward(e) is true (or the edge is a loop)!
853    NodeIt head(const EdgeIt& e) const;
854    NodeIt tail(const EdgeIt& e) const;
855
856    // FIXME: ezeknek valami jobb nev kellene!!!
857    GraphEdge graphEdge(const EdgeIt& e) const;
858    GraphNode graphNode(const NodeIt& n) const;
859
860
861    /*** Iterator classes ***/
862    class EdgeIt {
863      friend class DynamicPath;
864
865      typename Container::const_iterator it;
866      bool forw;
867    public:
868      // FIXME: jarna neki ilyen is...
869      // EdgeIt(Invalid);
870
871      bool forward() const { return forw; }
872
873      bool operator==(const EdgeIt& e) const { return it==e.it; }
874      bool operator!=(const EdgeIt& e) const { return it!=e.it; }
875      bool operator<(const EdgeIt& e) const { return it<e.it; }
876    };
877
878    class NodeIt {
879      friend class DynamicPath;
880
881      size_t idx;
882      bool tail;  // Is this node the tail of the edge with same idx?
883
884    public:
885      // FIXME: jarna neki ilyen is...
886      // NodeIt(Invalid);
887
888      bool operator==(const NodeIt& n) const { return idx==n.idx; }
889      bool operator!=(const NodeIt& n) const { return idx!=n.idx; }
890      bool operator<(const NodeIt& n) const { return idx<n.idx; }
891    };
892
893  private:
894    bool edgeIncident(const GraphEdge &e, const GraphNode &a,
895                      GraphNode &b);
896    bool connectTwoEdges(const GraphEdge &e, const GraphEdge &f);
897  };
898
899  template<typename Gr>
900  typename DynamicPath<Gr>::EdgeIt&
901  DynamicPath<Gr>::next(DynamicPath::EdgeIt &e) const {
902    if( e.it == edges.end() )
903      return e;
904
905    GraphNode common_node = ( e.forw ? G.head(*e.it) : G.tail(*e.it) );
906    ++e.it;
907
908    // Invalid edgeit is always forward :)
909    if( e.it == edges.end() ) {
910      e.forw = true;
911      return e;
912    }
913
914    e.forw = ( G.tail(*e.it) == common_node );
915    return e;
916  }
917
918  template<typename Gr>
919  typename DynamicPath<Gr>::NodeIt& DynamicPath<Gr>::next(NodeIt &n) const {
920    if( n.idx >= length() ) {
921      // FIXME: invalid
922      n.idx = length()+1;
923      return n;
924    }
925
926   
927    GraphNode next_node = ( n.tail ? G.head(edges[n.idx]) :
928                              G.tail(edges[n.idx]) );
929    ++n.idx;
930    if( n.idx < length() ) {
931      n.tail = ( next_node == G.tail(edges[n.idx]) );
932    }
933    else {
934      n.tail = true;
935    }
936
937    return n;
938  }
939
940  template<typename Gr>
941  bool DynamicPath<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a,
942                          GraphNode &b) {
943    if( G.tail(e) == a ) {
944      b=G.head(e);
945      return true;
946    }
947    if( G.head(e) == a ) {
948      b=G.tail(e);
949      return true;
950    }
951    return false;
952  }
953
954  template<typename Gr>
955  bool DynamicPath<Gr>::connectTwoEdges(const GraphEdge &e,
956                             const GraphEdge &f) {
957    if( edgeIncident(f, G.tail(e), _last) ) {
958      _first = G.head(e);
959      return true;
960    }
961    if( edgeIncident(f, G.head(e), _last) ) {
962      _first = G.tail(e);
963      return true;
964    }
965    return false;
966  }
967
968  template<typename Gr>
969  bool DynamicPath<Gr>::pushFront(const GraphEdge &e) {
970    if( G.valid(_first) ) {
971        if( edgeIncident(e, _first, _first) ) {
972          edges.push_front(e);
973          return true;
974        }
975        else
976          return false;
977    }
978    else if( length() < 1 || connectTwoEdges(e, edges[0]) ) {
979      edges.push_front(e);
980      return true;
981    }
982    else
983      return false;
984  }
985
986  template<typename Gr>
987  bool DynamicPath<Gr>::pushBack(const GraphEdge &e) {
988    if( G.valid(_last) ) {
989        if( edgeIncident(e, _last, _last) ) {
990          edges.push_back(e);
991          return true;
992        }
993        else
994          return false;
995    }
996    else if( length() < 1 || connectTwoEdges(edges[0], e) ) {
997      edges.push_back(e);
998      return true;
999    }
1000    else
1001      return false;
1002  }
1003
1004
1005  template<typename Gr>
1006  bool DynamicPath<Gr>::setFrom(const GraphNode &n) {
1007    if( G.valid(_first) ) {
1008      return _first == n;
1009    }
1010    else {
1011      if( length() > 0) {
1012        if( edgeIncident(edges[0], n, _last) ) {
1013          _first = n;
1014          return true;
1015        }
1016        else return false;
1017      }
1018      else {
1019        _first = _last = n;
1020        return true;
1021      }
1022    }
1023  }
1024
1025  template<typename Gr>
1026  bool DynamicPath<Gr>::setTo(const GraphNode &n) {
1027    if( G.valid(_last) ) {
1028      return _last == n;
1029    }
1030    else {
1031      if( length() > 0) {
1032        if( edgeIncident(edges[0], n, _first) ) {
1033          _last = n;
1034          return true;
1035        }
1036        else return false;
1037      }
1038      else {
1039        _first = _last = n;
1040        return true;
1041      }
1042    }
1043  }
1044
1045
1046  template<typename Gr>
1047  typename DynamicPath<Gr>::NodeIt
1048  DynamicPath<Gr>::tail(const EdgeIt& e) const {
1049    NodeIt n;
1050
1051    if( e.it == edges.end() ) {
1052      // FIXME: invalid-> invalid
1053      n.idx = length() + 1;
1054      n.tail = true;
1055      return n;
1056    }
1057
1058    n.idx = e.it-edges.begin();
1059    n.tail = e.forw;
1060    return n;
1061  }
1062
1063  template<typename Gr>
1064  typename DynamicPath<Gr>::NodeIt
1065  DynamicPath<Gr>::head(const EdgeIt& e) const {
1066    if( e.it == edges.end()-1 ) {
1067      return _last;
1068    }
1069
1070    EdgeIt next_edge = e;
1071    next(next_edge);
1072    return tail(next_edge);
1073  }
1074     
1075  template<typename Gr>
1076  typename DynamicPath<Gr>::GraphEdge
1077  DynamicPath<Gr>::graphEdge(const EdgeIt& e) const {
1078    if( e.it != edges.end() ) {
1079      return *e.it;
1080    }
1081    else {
1082      return INVALID;
1083    }
1084  }
1085 
1086  template<typename Gr>
1087  typename DynamicPath<Gr>::GraphNode
1088  DynamicPath<Gr>::graphNode(const NodeIt& n) const {
1089    if( n.idx < length() ) {
1090      return n.tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]);
1091    }
1092    else if( n.idx == length() ) {
1093      return _last;
1094    }
1095    else {
1096      return INVALID;
1097    }
1098  }
1099
1100  template<typename Gr>
1101  typename DynamicPath<Gr>::EdgeIt&
1102  DynamicPath<Gr>::nth(EdgeIt &e, size_t k) const {
1103    if( k>=length() ) {
1104      // FIXME: invalid EdgeIt
1105      e.it = edges.end();
1106      e.forw = true;
1107      return e;
1108    }
1109
1110    e.it = edges.begin()+k;
1111    if(k==0) {
1112      e.forw = ( G.tail(*e.it) == _first );
1113    }
1114    else {
1115      e.forw = ( G.tail(*e.it) == G.tail(edges[k-1]) ||
1116                 G.tail(*e.it) == G.head(edges[k-1]) );
1117    }
1118    return e;
1119  }
1120   
1121  template<typename Gr>
1122  typename DynamicPath<Gr>::NodeIt&
1123  DynamicPath<Gr>::nth(NodeIt &n, size_t k) const {
1124    if( k>length() ) {
1125      // FIXME: invalid NodeIt
1126      n.idx = length()+1;
1127      n.tail = true;
1128      return n;
1129    }
1130    if( k==length() ) {
1131      n.idx = length();
1132      n.tail = true;
1133      return n;
1134    }
1135    n = tail(nth<EdgeIt>(k));
1136    return n;
1137  }
1138
1139  // Reszut konstruktorok:
1140
1141
1142  template<typename Gr>
1143  DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const EdgeIt &a,
1144                               const EdgeIt &b) :
1145    G(P.G), edges(a.it, b.it)    // WARNING: if b.it < a.it this will blow up!
1146  {
1147    if( G.valid(P._first) && a.it < P.edges.end() ) {
1148      _first = ( a.forw ? G.tail(*a.it) : G.head(*a.it) );
1149      if( b.it < P.edges.end() ) {
1150        _last = ( b.forw ? G.tail(*b.it) : G.head(*b.it) );
1151      }
1152      else {
1153        _last = P._last;
1154      }
1155    }
1156  }
1157
1158  template<typename Gr>
1159  DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const NodeIt &a,
1160                               const NodeIt &b) : G(P.G)
1161  {
1162    if( !P.valid(a) || !P.valid(b) )
1163      return;
1164
1165    int ai = a.idx, bi = b.idx;
1166    if( bi<ai )
1167      std::swap(ai,bi);
1168   
1169    edges.resize(bi-ai);
1170    copy(P.edges.begin()+ai, P.edges.begin()+bi, edges.begin());
1171
1172    _first = P.graphNode(a);
1173    _last = P.graphNode(b);
1174  }
1175
1176  ///@}
1177
1178} // namespace hugo
1179
1180#endif // HUGO_PATH_H
Note: See TracBrowser for help on using the repository browser.