COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/klao/path.h @ 764:615aca7091d2

Last change on this file since 764:615aca7091d2 was 686:fc8a3393e0d9, checked in by Alpar Juttner, 20 years ago

src/work/alpar/path.h (docs) is merged into src/work/klao/path.h
(and removed)

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