COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/klao/path.h @ 524:bd8109f8e2fa

Last change on this file since 524:bd8109f8e2fa was 493:bbd1db03f0fe, checked in by Mihaly Barasz, 17 years ago

DirPath? fejlodes.
Kiserleti struktura a forditasi idoben kapcsolhato konzisztencia es range
ellenorzesekre.

File size: 18.7 KB
Line 
1// -*- c++ -*- //
2
3///\ingroup datas
4///\file
5///\brief Classes for representing paths in graphs.
6
7#ifndef HUGO_PATH_H
8#define HUGO_PATH_H
9
10#include <deque>
11#include <vector>
12#include <algorithm>
13
14#include <invalid.h>
15#include <error.h>
16#include <debug.h>
17
18namespace hugo {
19
20  /// \addtogroup datas
21  /// @{
22
23
24  //! \brief A structure for representing directed path in a graph.
25  //!
26  //! \param Graph The graph type in which the path is.
27  //! \param DM DebugMode, defaults to DefaultDebugMode.
28  //!
29  //! In a sense, the path can be treated as a graph, for is has \c NodeIt
30  //! and \c EdgeIt with the same usage. These types converts to the \c Node
31  //! and \c Edge of the original graph.
32  //!
33  //! \todo Thoroughfully check all the range and consistency tests.
34  template<typename Graph, typename DM = DefaultDebugMode>
35  class DirPath {
36  public:
37    typedef typename Graph::Edge GraphEdge;
38    typedef typename Graph::Node GraphNode;
39    class NodeIt;
40    class EdgeIt;
41
42  protected:
43    const Graph *gr;
44    typedef std::vector<GraphEdge> Container;
45    Container edges;
46
47  public:
48
49    /// \param _G The graph in which the path is.
50    ///
51    DirPath(const Graph &_G) : gr(&_G) {}
52
53    /// \brief Subpath constructor.
54    ///
55    /// Subpath defined by two nodes.
56    /// \warning It is an error if the two edges are not in order!
57    /// \todo Implement!
58    DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b);
59    /// \brief Subpath constructor.
60    ///
61    /// Subpath defined by two edges. Contains edges in [a,b)
62    /// \warning It is an error if the two edges are not in order!
63    /// \todo Implement!
64    DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b);
65
66    /// Length of the path.
67    size_t length() const { return edges.size(); }
68    /// Returns whether the path is empty.
69    bool empty() const { return edges.empty(); }
70
71    /// Resets the path to an empty path.
72    void clear() { edges.clear(); }
73
74    /// \brief Starting point of the path.
75    ///
76    /// Starting point of the path.
77    /// Returns INVALID if the path is empty.
78    GraphNode from() const {
79      return empty() ? INVALID : gr->tail(edges[0]);
80    }
81    /// \brief End point of the path.
82    ///
83    /// End point of the path.
84    /// Returns INVALID if the path is empty.
85    GraphNode to() const {
86      return empty() ? INVALID : gr->head(edges[length()-1]);
87    }
88
89    /// \brief Initializes node or edge iterator to point to the first
90    /// node or edge.
91    ///
92    /// \sa nth
93    template<typename It>
94    It& first(It &i) const { return i=It(*this); }
95
96    /// \brief Initializes node or edge iterator to point to the node or edge
97    /// of a given index.
98    template<typename It>
99    It& nth(It &i, int n) const {
100      // FIXME: this test should be different for NodeIt and EdgeIt:
101      if( DM::range_check && (n<0 || n>int(length())) )
102        fault("DirPath::nth: index out of range");
103      return i=It(*this, n);
104    }
105
106    /// Checks validity of a node or edge iterator.
107    template<typename It>
108    bool valid(const It &i) const { return i.valid(); }
109
110    /// Steps the given node or edge iterator.
111    template<typename It>
112    It& next(It &e) const {
113      if( DM::range_check && !e.valid() )
114        fault("DirPath::next() on invalid iterator");
115      return ++e;
116    }
117
118    /// \brief Returns node iterator pointing to the head node of the
119    /// given edge iterator.
120    NodeIt head(const EdgeIt& e) const {
121      return NodeIt(*this, e.idx+1);
122    }
123
124    /// \brief Returns node iterator pointing to the tail node of the
125    /// given edge iterator.
126    NodeIt tail(const EdgeIt& e) const {
127      return NodeIt(*this, e.idx);
128    }
129
130
131    /*** Iterator classes ***/
132    class EdgeIt {
133      friend class DirPath;
134
135      int idx;
136      const DirPath *p;
137    public:
138      EdgeIt() {}
139      EdgeIt(Invalid) : idx(-1), p(0) {}
140      EdgeIt(const DirPath &_p, int _idx = 0) :
141        idx(_idx), p(&_p) { validate(); }
142
143      bool valid() const { return idx!=-1; }
144
145      operator GraphEdge () const {
146        return valid() ? p->edges[idx] : INVALID;
147      }
148      EdgeIt& operator++() { ++idx; validate(); return *this; }
149
150      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
151      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
152      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
153
154    private:
155      // FIXME: comparison between signed and unsigned...
156      // Jo ez igy? Vagy esetleg legyen a length() int?
157      void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
158    };
159
160    class NodeIt {
161      friend class DirPath;
162
163      int idx;
164      const DirPath *p;
165    public:
166      NodeIt() {}
167      NodeIt(Invalid) : idx(-1), p(0) {}
168      NodeIt(const DirPath &_p, int _idx = 0) :
169        idx(_idx), p(&_p) { validate(); }
170
171      bool valid() const { return idx!=-1; }
172
173      operator const GraphEdge& () const {
174        if(idx >= p->length())
175          return p->to();
176        else if(idx >= 0)
177          return p->gr->tail(p->edges[idx]);
178        else
179          return INVALID;
180      }
181      NodeIt& operator++() { ++idx; validate(); return *this; }
182
183      bool operator==(const NodeIt& e) const { return idx==e.idx; }
184      bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
185      bool operator<(const NodeIt& e) const { return idx<e.idx; }
186
187    private:
188      void validate() { if( size_t(idx) > p->length() ) idx=-1; }
189    };
190
191    friend class Builder;   
192
193    /**
194     * \brief Class to build paths
195     *
196     * \ingroup datas
197     * This class is used to fill a path with edges.
198     *
199     * You can push new edges to the front and to the back of the path in
200     * arbitrary order the you can commit these changes to the graph.
201     *
202     * Fundamentally, for most "Paths" (classes fulfilling the
203     * PathConcept) while the builder is active (after the first modifying
204     * operation and until the commit()) the original Path is in a
205     * "transitional" state (operations ot it have undefined result). But
206     * in the case of DirPath the original path is unchanged until the
207     * commit. However we don't recomend that you use this feature.
208     */
209    class Builder {
210      DirPath &P;
211      Container front, back;
212
213    public:
214      ///\param _P the path you want to fill in.
215      ///
216      Builder(DirPath &_P) : P(_P) {}
217
218      ///Sets the first node of the path.
219     
220      ///Sets the first node of the path. If the path is empty, this
221      ///function or setTo() have to be called before any call to \ref
222      ///pushFront() or \ref pushBack()
223      void setFrom(const GraphNode &) {}
224     
225      ///Sets the last node of the path.
226     
227      ///Sets the last node of the path. If the path is empty, this
228      ///function or setFrom() have to be called before any call of \ref
229      ///pushFront() or \ref pushBack()
230      void setTo(const GraphNode &) {}
231     
232      ///Push a new edge to the front of the path
233
234      ///Push a new edge to the front of the path.
235      ///\sa setTo
236      void pushFront(const GraphEdge& e) {
237        if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
238          fault("DirPath::Builder::pushFront: nonincident edge");
239        }
240        front.push_back(e);
241      }
242
243      ///Push a new edge to the back of the path
244
245      ///Push a new edge to the back of the path.
246      ///\sa setFrom
247      void pushBack(const GraphEdge& e) {
248        if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
249          fault("DirPath::Builder::pushBack: nonincident edge");
250        }
251        back.push_back(e);
252      }
253
254      ///Commit the changes to the path.
255      void commit() {
256        if( !(front.empty() && back.empty()) ) {
257          Container tmp;
258          tmp.reserve(front.size()+back.size()+P.length());
259          tmp.insert(tmp.end(), front.rbegin(), front.rend());
260          tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
261          tmp.insert(tmp.end(), back.begin(), back.end());
262          P.edges.swap(tmp);
263          front.clear();
264          back.clear();
265        }
266      }
267
268//       ///Desctuctor
269
270//       ///The desctuctor.
271//       ///It commit also commit the changes.
272//       ///\todo Is this what we want?
273//  Nope. Let's use commit() explicitly.
274//       ~Builder() { commit(); }
275
276      // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
277      // Hogy kenyelmes egy ilyet hasznalni?
278      void reserve(size_t r) {
279        front.reserve(r);
280        back.reserve(r);
281      }
282
283    private:
284      bool empty() {
285        return front.empty() && back.empty() && P.empty();
286      }
287
288      GraphNode from() const {
289        if( ! front.empty() )
290          return P.gr->tail(front[front.size()-1]);
291        else if( ! P.empty() )
292          return P.gr->tail(P.edges[0]);
293        else if( ! back.empty() )
294          return P.gr->tail(back[0]);
295        else
296          return INVALID;
297      }
298      GraphNode to() const {
299        if( ! back.empty() )
300          return P.gr->head(back[back.size()-1]);
301        else if( ! P.empty() )
302          return P.gr->head(P.edges[P.length()-1]);
303        else if( ! front.empty() )
304          return P.gr->head(front[0]);
305        else
306          return INVALID;
307      }
308
309    };
310
311  };
312
313
314
315
316
317
318
319
320
321
322  /**********************************************************************/
323
324
325  /* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata
326     elott. Eleg bonyinak nez ki, ahogyan azokat az STL-ben hasznaljak. */
327
328  template<typename Graph>
329  class DynamicPath {
330
331  public:
332    typedef typename Graph::Edge GraphEdge;
333    typedef typename Graph::Node GraphNode;
334    class NodeIt;
335    class EdgeIt;
336
337  protected:
338    Graph& G;
339    // FIXME: ehelyett eleg lenne tarolni ket boolt: a ket szelso el
340    // iranyitasat:
341    GraphNode _first, _last;
342    typedef std::deque<GraphEdge> Container;
343    Container edges;
344
345  public:
346
347    DynamicPath(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {}
348
349    /// Subpath defined by two nodes.
350    /// Nodes may be in reversed order, then
351    /// we contstruct the reversed path.
352    DynamicPath(const DynamicPath &P, const NodeIt &a, const NodeIt &b);
353    /// Subpath defined by two edges. Contains edges in [a,b)
354    /// It is an error if the two edges are not in order!
355    DynamicPath(const DynamicPath &P, const EdgeIt &a, const EdgeIt &b);
356   
357    size_t length() const { return edges.size(); }
358    GraphNode from() const { return _first; }
359    GraphNode to() const { return _last; }
360
361    NodeIt& first(NodeIt &n) const { return nth(n, 0); }
362    EdgeIt& first(EdgeIt &e) const { return nth(e, 0); }
363    template<typename It>
364    It first() const {
365      It e;
366      first(e);
367      return e;
368    }
369
370    NodeIt& nth(NodeIt &, size_t) const;
371    EdgeIt& nth(EdgeIt &, size_t) const;
372    template<typename It>
373    It nth(size_t n) const {
374      It e;
375      nth(e, n);
376      return e;
377    }
378
379    bool valid(const NodeIt &n) const { return n.idx <= length(); }
380    bool valid(const EdgeIt &e) const { return e.it < edges.end(); }
381
382    bool isForward(const EdgeIt &e) const { return e.forw; }
383
384    /// index of a node on the path. Returns length+2 for the invalid NodeIt
385    int index(const NodeIt &n) const { return n.idx; }
386    /// index of an edge on the path. Returns length+1 for the invalid EdgeIt
387    int index(const EdgeIt &e) const { return e.it - edges.begin(); }
388
389    EdgeIt& next(EdgeIt &e) const;
390    NodeIt& next(NodeIt &n) const;
391    template <typename It>
392    It getNext(It it) const {
393      It tmp(it); return next(tmp);
394    }
395
396    // A path is constructed using the following four functions.
397    // They return false if the requested operation is inconsistent
398    // with the path constructed so far.
399    // If your path has only one edge you MUST set either "from" or "to"!
400    // So you probably SHOULD call it in any case to be safe (and check the
401    // returned value to check if your path is consistent with your idea).
402    bool pushFront(const GraphEdge &e);
403    bool pushBack(const GraphEdge &e);
404    bool setFrom(const GraphNode &n);
405    bool setTo(const GraphNode &n);
406
407    // WARNING: these two functions return the head/tail of an edge with
408    // respect to the direction of the path!
409    // So G.head(P.graphEdge(e)) == P.graphNode(P.head(e)) holds only if
410    // P.forward(e) is true (or the edge is a loop)!
411    NodeIt head(const EdgeIt& e) const;
412    NodeIt tail(const EdgeIt& e) const;
413
414    // FIXME: ezeknek valami jobb nev kellene!!!
415    GraphEdge graphEdge(const EdgeIt& e) const;
416    GraphNode graphNode(const NodeIt& n) const;
417
418
419    /*** Iterator classes ***/
420    class EdgeIt {
421      friend class DynamicPath;
422
423      typename Container::const_iterator it;
424      bool forw;
425    public:
426      // FIXME: jarna neki ilyen is...
427      // EdgeIt(Invalid);
428
429      bool forward() const { return forw; }
430
431      bool operator==(const EdgeIt& e) const { return it==e.it; }
432      bool operator!=(const EdgeIt& e) const { return it!=e.it; }
433      bool operator<(const EdgeIt& e) const { return it<e.it; }
434    };
435
436    class NodeIt {
437      friend class DynamicPath;
438
439      size_t idx;
440      bool tail;  // Is this node the tail of the edge with same idx?
441
442    public:
443      // FIXME: jarna neki ilyen is...
444      // NodeIt(Invalid);
445
446      bool operator==(const NodeIt& n) const { return idx==n.idx; }
447      bool operator!=(const NodeIt& n) const { return idx!=n.idx; }
448      bool operator<(const NodeIt& n) const { return idx<n.idx; }
449    };
450
451  private:
452    bool edgeIncident(const GraphEdge &e, const GraphNode &a,
453                      GraphNode &b);
454    bool connectTwoEdges(const GraphEdge &e, const GraphEdge &f);
455  };
456
457  template<typename Gr>
458  typename DynamicPath<Gr>::EdgeIt&
459  DynamicPath<Gr>::next(DynamicPath::EdgeIt &e) const {
460    if( e.it == edges.end() )
461      return e;
462
463    GraphNode common_node = ( e.forw ? G.head(*e.it) : G.tail(*e.it) );
464    ++e.it;
465
466    // Invalid edgeit is always forward :)
467    if( e.it == edges.end() ) {
468      e.forw = true;
469      return e;
470    }
471
472    e.forw = ( G.tail(*e.it) == common_node );
473    return e;
474  }
475
476  template<typename Gr>
477  typename DynamicPath<Gr>::NodeIt& DynamicPath<Gr>::next(NodeIt &n) const {
478    if( n.idx >= length() ) {
479      // FIXME: invalid
480      n.idx = length()+1;
481      return n;
482    }
483
484   
485    GraphNode next_node = ( n.tail ? G.head(edges[n.idx]) :
486                              G.tail(edges[n.idx]) );
487    ++n.idx;
488    if( n.idx < length() ) {
489      n.tail = ( next_node == G.tail(edges[n.idx]) );
490    }
491    else {
492      n.tail = true;
493    }
494
495    return n;
496  }
497
498  template<typename Gr>
499  bool DynamicPath<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a,
500                          GraphNode &b) {
501    if( G.tail(e) == a ) {
502      b=G.head(e);
503      return true;
504    }
505    if( G.head(e) == a ) {
506      b=G.tail(e);
507      return true;
508    }
509    return false;
510  }
511
512  template<typename Gr>
513  bool DynamicPath<Gr>::connectTwoEdges(const GraphEdge &e,
514                             const GraphEdge &f) {
515    if( edgeIncident(f, G.tail(e), _last) ) {
516      _first = G.head(e);
517      return true;
518    }
519    if( edgeIncident(f, G.head(e), _last) ) {
520      _first = G.tail(e);
521      return true;
522    }
523    return false;
524  }
525
526  template<typename Gr>
527  bool DynamicPath<Gr>::pushFront(const GraphEdge &e) {
528    if( G.valid(_first) ) {
529        if( edgeIncident(e, _first, _first) ) {
530          edges.push_front(e);
531          return true;
532        }
533        else
534          return false;
535    }
536    else if( length() < 1 || connectTwoEdges(e, edges[0]) ) {
537      edges.push_front(e);
538      return true;
539    }
540    else
541      return false;
542  }
543
544  template<typename Gr>
545  bool DynamicPath<Gr>::pushBack(const GraphEdge &e) {
546    if( G.valid(_last) ) {
547        if( edgeIncident(e, _last, _last) ) {
548          edges.push_back(e);
549          return true;
550        }
551        else
552          return false;
553    }
554    else if( length() < 1 || connectTwoEdges(edges[0], e) ) {
555      edges.push_back(e);
556      return true;
557    }
558    else
559      return false;
560  }
561
562
563  template<typename Gr>
564  bool DynamicPath<Gr>::setFrom(const GraphNode &n) {
565    if( G.valid(_first) ) {
566      return _first == n;
567    }
568    else {
569      if( length() > 0) {
570        if( edgeIncident(edges[0], n, _last) ) {
571          _first = n;
572          return true;
573        }
574        else return false;
575      }
576      else {
577        _first = _last = n;
578        return true;
579      }
580    }
581  }
582
583  template<typename Gr>
584  bool DynamicPath<Gr>::setTo(const GraphNode &n) {
585    if( G.valid(_last) ) {
586      return _last == n;
587    }
588    else {
589      if( length() > 0) {
590        if( edgeIncident(edges[0], n, _first) ) {
591          _last = n;
592          return true;
593        }
594        else return false;
595      }
596      else {
597        _first = _last = n;
598        return true;
599      }
600    }
601  }
602
603
604  template<typename Gr>
605  typename DynamicPath<Gr>::NodeIt
606  DynamicPath<Gr>::tail(const EdgeIt& e) const {
607    NodeIt n;
608
609    if( e.it == edges.end() ) {
610      // FIXME: invalid-> invalid
611      n.idx = length() + 1;
612      n.tail = true;
613      return n;
614    }
615
616    n.idx = e.it-edges.begin();
617    n.tail = e.forw;
618    return n;
619  }
620
621  template<typename Gr>
622  typename DynamicPath<Gr>::NodeIt
623  DynamicPath<Gr>::head(const EdgeIt& e) const {
624    if( e.it == edges.end()-1 ) {
625      return _last;
626    }
627
628    EdgeIt next_edge = e;
629    next(next_edge);
630    return tail(next_edge);
631  }
632     
633  template<typename Gr>
634  typename DynamicPath<Gr>::GraphEdge
635  DynamicPath<Gr>::graphEdge(const EdgeIt& e) const {
636    if( e.it != edges.end() ) {
637      return *e.it;
638    }
639    else {
640      return INVALID;
641    }
642  }
643 
644  template<typename Gr>
645  typename DynamicPath<Gr>::GraphNode
646  DynamicPath<Gr>::graphNode(const NodeIt& n) const {
647    if( n.idx < length() ) {
648      return n.tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]);
649    }
650    else if( n.idx == length() ) {
651      return _last;
652    }
653    else {
654      return INVALID;
655    }
656  }
657
658  template<typename Gr>
659  typename DynamicPath<Gr>::EdgeIt&
660  DynamicPath<Gr>::nth(EdgeIt &e, size_t k) const {
661    if( k>=length() ) {
662      // FIXME: invalid EdgeIt
663      e.it = edges.end();
664      e.forw = true;
665      return e;
666    }
667
668    e.it = edges.begin()+k;
669    if(k==0) {
670      e.forw = ( G.tail(*e.it) == _first );
671    }
672    else {
673      e.forw = ( G.tail(*e.it) == G.tail(edges[k-1]) ||
674                 G.tail(*e.it) == G.head(edges[k-1]) );
675    }
676    return e;
677  }
678   
679  template<typename Gr>
680  typename DynamicPath<Gr>::NodeIt&
681  DynamicPath<Gr>::nth(NodeIt &n, size_t k) const {
682    if( k>length() ) {
683      // FIXME: invalid NodeIt
684      n.idx = length()+1;
685      n.tail = true;
686      return n;
687    }
688    if( k==length() ) {
689      n.idx = length();
690      n.tail = true;
691      return n;
692    }
693    n = tail(nth<EdgeIt>(k));
694    return n;
695  }
696
697  // Reszut konstruktorok:
698
699
700  template<typename Gr>
701  DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const EdgeIt &a,
702                               const EdgeIt &b) :
703    G(P.G), edges(a.it, b.it)    // WARNING: if b.it < a.it this will blow up!
704  {
705    if( G.valid(P._first) && a.it < P.edges.end() ) {
706      _first = ( a.forw ? G.tail(*a.it) : G.head(*a.it) );
707      if( b.it < P.edges.end() ) {
708        _last = ( b.forw ? G.tail(*b.it) : G.head(*b.it) );
709      }
710      else {
711        _last = P._last;
712      }
713    }
714  }
715
716  template<typename Gr>
717  DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const NodeIt &a,
718                               const NodeIt &b) : G(P.G)
719  {
720    if( !P.valid(a) || !P.valid(b) )
721      return;
722
723    int ai = a.idx, bi = b.idx;
724    if( bi<ai )
725      std::swap(ai,bi);
726   
727    edges.resize(bi-ai);
728    copy(P.edges.begin()+ai, P.edges.begin()+bi, edges.begin());
729
730    _first = P.graphNode(a);
731    _last = P.graphNode(b);
732  }
733
734  ///@}
735
736} // namespace hugo
737
738#endif // HUGO_PATH_H
Note: See TracBrowser for help on using the repository browser.