COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/klao/path.h @ 418:32a2a16027e0

Last change on this file since 418:32a2a16027e0 was 369:dc9c19f4ca9a, checked in by Mihaly Barasz, 17 years ago

Directed path structure.
Proposal for a path building interface.

File size: 14.4 KB
Line 
1// -*- c++ -*- //
2
3/**
4 *
5 * Class for representing paths in graphs.
6 *
7 */
8
9#ifndef HUGO_PATH_H
10#define HUGO_PATH_H
11
12#include <deque>
13#include <vector>
14#include <algorithm>
15
16#include <invalid.h>
17
18namespace hugo {
19
20  template<typename Graph>
21  class DirPath {
22  public:
23    typedef typename Graph::Edge GraphEdge;
24    typedef typename Graph::Node GraphNode;
25    class NodeIt;
26    class EdgeIt;
27
28  protected:
29    const Graph *gr;
30    typedef std::vector<GraphEdge> Container;
31    Container edges;
32
33  public:
34
35    DirPath(const Graph &_G) : gr(&_G) {}
36
37    /// Subpath defined by two nodes.
38    /// It is an error if the two edges are not in order!
39    DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b);
40    /// Subpath defined by two edges. Contains edges in [a,b)
41    /// It is an error if the two edges are not in order!
42    DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b);
43
44    size_t length() const { return edges.size(); }
45    bool empty() const { return edges.empty(); }
46    GraphNode from() const {
47      return empty() ? INVALID : gr->tail(edges[0]);
48    }
49    GraphNode to() const {
50      return empty() ? INVALID : gr->head(edges[length()-1]);
51    }
52
53    template<typename It>
54    It& first(It &i) const { return i=It(*this); }
55
56    template<typename It>
57    It& nth(It &i, int n) const { return i=It(*this, n); }
58
59    template<typename It>
60    bool valid(const It &i) const { return i.valid(); }
61
62    template<typename It>
63    It& next(It &e) const { return ++e; }
64
65    /// \todo !
66    NodeIt head(const EdgeIt& e) const;
67    NodeIt tail(const EdgeIt& e) const;
68
69
70    /*** Iterator classes ***/
71    class EdgeIt {
72      friend class DirPath;
73
74      int idx;
75      const DirPath *p;
76    public:
77      EdgeIt() {}
78      EdgeIt(Invalid) : idx(-1), p(0) {}
79      EdgeIt(const DirPath &_p, int _idx = 0) :
80        idx(_idx), p(&_p) { validate(); }
81
82      bool valid() const { return idx!=-1; }
83
84      operator GraphEdge () const {
85        return valid() ? p->edges[idx] : INVALID;
86      }
87      EdgeIt& operator++() { ++idx; validate(); return *this; }
88
89      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
90      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
91      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
92
93    private:
94      // FIXME: comparison between signed and unsigned...
95      // Jo ez igy? Vagy esetleg legyen a length() int?
96      void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
97    };
98
99    class NodeIt {
100      friend class DirPath;
101
102      int idx;
103      const DirPath *p;
104    public:
105      NodeIt() {}
106      NodeIt(Invalid) : idx(-1), p(0) {}
107      NodeIt(const DirPath &_p, int _idx = 0) :
108        idx(_idx), p(&_p) { validate(); }
109
110      bool valid() const { return idx!=-1; }
111
112      operator const GraphEdge& () const {
113        if(idx >= p->length())
114          return p->to();
115        else if(idx >= 0)
116          return p->gr->tail(p->edges[idx]);
117        else
118          return INVALID;
119      }
120      NodeIt& operator++() { ++idx; validate(); return *this; }
121
122      bool operator==(const NodeIt& e) const { return idx==e.idx; }
123      bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
124      bool operator<(const NodeIt& e) const { return idx<e.idx; }
125
126    private:
127      void validate() { if( size_t(idx) > p->length() ) idx=-1; }
128    };
129
130    friend class Builder;   
131    class Builder {
132      DirPath &P;
133      Container d;
134
135    public:
136      Builder(DirPath &_P) : P(_P) {}
137
138      bool pushFront(const GraphEdge& e) {
139        if( empty() || P.gr->head(e)==from() ) {
140          d.push_back(e);
141          return true;
142        }
143        return false;
144      }
145      bool pushBack(const GraphEdge& e) {
146        if( empty() || P.gr->tail(e)==to() ) {
147          P.edges.push_back(e);
148          return true;
149        }
150        return false;
151      }
152
153      void commit() {
154        if( !d.empty() ) {
155          P.edges.insert(P.edges.begin(), d.rbegin(), d.rend());
156          d.clear();
157        }
158      }
159
160      ~Builder() { commit(); }
161
162      // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
163      // Hogy kenyelmes egy ilyet hasznalni?
164      void reserve(size_t r) {
165        d.reserve(r);
166        P.edges.reserve(P.length()+r);
167      }
168
169    private:
170      bool empty() { return d.empty() && P.empty(); }
171
172      GraphNode from() const {
173        if( ! d.empty() )
174          return P.gr->tail(d[d.size()-1]);
175        else if( ! P.empty() )
176          return P.gr->tail(P.edges[0]);
177        else
178          return INVALID;
179      }
180      GraphNode to() const {
181        if( ! P.empty() )
182          return P.gr->head(P.edges[P.length()-1]);
183        else if( ! d.empty() )
184          return P.gr->head(d[0]);
185        else
186          return INVALID;
187      }
188
189    };
190
191  };
192
193
194
195
196
197
198
199
200
201
202
203  /**********************************************************************/
204
205
206  /* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata
207     elott. Eleg bonyinak nez ki, ahogyan azokat az STL-ben hasznaljak. */
208
209  template<typename Graph>
210  class DynamicPath {
211
212  public:
213    typedef typename Graph::Edge GraphEdge;
214    typedef typename Graph::Node GraphNode;
215    class NodeIt;
216    class EdgeIt;
217
218  protected:
219    Graph& G;
220    // FIXME: ehelyett eleg lenne tarolni ket boolt: a ket szelso el
221    // iranyitasat:
222    GraphNode _first, _last;
223    typedef std::deque<GraphEdge> Container;
224    Container edges;
225
226  public:
227
228    DynamicPath(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {}
229
230    /// Subpath defined by two nodes.
231    /// Nodes may be in reversed order, then
232    /// we contstruct the reversed path.
233    DynamicPath(const DynamicPath &P, const NodeIt &a, const NodeIt &b);
234    /// Subpath defined by two edges. Contains edges in [a,b)
235    /// It is an error if the two edges are not in order!
236    DynamicPath(const DynamicPath &P, const EdgeIt &a, const EdgeIt &b);
237   
238    size_t length() const { return edges.size(); }
239    GraphNode from() const { return _first; }
240    GraphNode to() const { return _last; }
241
242    NodeIt& first(NodeIt &n) const { return nth(n, 0); }
243    EdgeIt& first(EdgeIt &e) const { return nth(e, 0); }
244    template<typename It>
245    It first() const {
246      It e;
247      first(e);
248      return e;
249    }
250
251    NodeIt& nth(NodeIt &, size_t) const;
252    EdgeIt& nth(EdgeIt &, size_t) const;
253    template<typename It>
254    It nth(size_t n) const {
255      It e;
256      nth(e, n);
257      return e;
258    }
259
260    bool valid(const NodeIt &n) const { return n.idx <= length(); }
261    bool valid(const EdgeIt &e) const { return e.it < edges.end(); }
262
263    bool isForward(const EdgeIt &e) const { return e.forw; }
264
265    /// index of a node on the path. Returns length+2 for the invalid NodeIt
266    int index(const NodeIt &n) const { return n.idx; }
267    /// index of an edge on the path. Returns length+1 for the invalid EdgeIt
268    int index(const EdgeIt &e) const { return e.it - edges.begin(); }
269
270    EdgeIt& next(EdgeIt &e) const;
271    NodeIt& next(NodeIt &n) const;
272    template <typename It>
273    It getNext(It it) const {
274      It tmp(it); return next(tmp);
275    }
276
277    // A path is constructed using the following four functions.
278    // They return false if the requested operation is inconsistent
279    // with the path constructed so far.
280    // If your path has only one edge you MUST set either "from" or "to"!
281    // So you probably SHOULD call it in any case to be safe (and check the
282    // returned value to check if your path is consistent with your idea).
283    bool pushFront(const GraphEdge &e);
284    bool pushBack(const GraphEdge &e);
285    bool setFrom(const GraphNode &n);
286    bool setTo(const GraphNode &n);
287
288    // WARNING: these two functions return the head/tail of an edge with
289    // respect to the direction of the path!
290    // So G.head(P.graphEdge(e)) == P.graphNode(P.head(e)) holds only if
291    // P.forward(e) is true (or the edge is a loop)!
292    NodeIt head(const EdgeIt& e) const;
293    NodeIt tail(const EdgeIt& e) const;
294
295    // FIXME: ezeknek valami jobb nev kellene!!!
296    GraphEdge graphEdge(const EdgeIt& e) const;
297    GraphNode graphNode(const NodeIt& n) const;
298
299
300    /*** Iterator classes ***/
301    class EdgeIt {
302      friend class DynamicPath;
303
304      typename Container::const_iterator it;
305      bool forw;
306    public:
307      // FIXME: jarna neki ilyen is...
308      // EdgeIt(Invalid);
309
310      bool forward() const { return forw; }
311
312      bool operator==(const EdgeIt& e) const { return it==e.it; }
313      bool operator!=(const EdgeIt& e) const { return it!=e.it; }
314      bool operator<(const EdgeIt& e) const { return it<e.it; }
315    };
316
317    class NodeIt {
318      friend class DynamicPath;
319
320      size_t idx;
321      bool tail;  // Is this node the tail of the edge with same idx?
322
323    public:
324      // FIXME: jarna neki ilyen is...
325      // NodeIt(Invalid);
326
327      bool operator==(const NodeIt& n) const { return idx==n.idx; }
328      bool operator!=(const NodeIt& n) const { return idx!=n.idx; }
329      bool operator<(const NodeIt& n) const { return idx<n.idx; }
330    };
331
332  private:
333    bool edgeIncident(const GraphEdge &e, const GraphNode &a,
334                      GraphNode &b);
335    bool connectTwoEdges(const GraphEdge &e, const GraphEdge &f);
336  };
337
338  template<typename Gr>
339  typename DynamicPath<Gr>::EdgeIt&
340  DynamicPath<Gr>::next(DynamicPath::EdgeIt &e) const {
341    if( e.it == edges.end() )
342      return e;
343
344    GraphNode common_node = ( e.forw ? G.head(*e.it) : G.tail(*e.it) );
345    ++e.it;
346
347    // Invalid edgeit is always forward :)
348    if( e.it == edges.end() ) {
349      e.forw = true;
350      return e;
351    }
352
353    e.forw = ( G.tail(*e.it) == common_node );
354    return e;
355  }
356
357  template<typename Gr>
358  typename DynamicPath<Gr>::NodeIt& DynamicPath<Gr>::next(NodeIt &n) const {
359    if( n.idx >= length() ) {
360      // FIXME: invalid
361      n.idx = length()+1;
362      return n;
363    }
364
365   
366    GraphNode next_node = ( n.tail ? G.head(edges[n.idx]) :
367                              G.tail(edges[n.idx]) );
368    ++n.idx;
369    if( n.idx < length() ) {
370      n.tail = ( next_node == G.tail(edges[n.idx]) );
371    }
372    else {
373      n.tail = true;
374    }
375
376    return n;
377  }
378
379  template<typename Gr>
380  bool DynamicPath<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a,
381                          GraphNode &b) {
382    if( G.tail(e) == a ) {
383      b=G.head(e);
384      return true;
385    }
386    if( G.head(e) == a ) {
387      b=G.tail(e);
388      return true;
389    }
390    return false;
391  }
392
393  template<typename Gr>
394  bool DynamicPath<Gr>::connectTwoEdges(const GraphEdge &e,
395                             const GraphEdge &f) {
396    if( edgeIncident(f, G.tail(e), _last) ) {
397      _first = G.head(e);
398      return true;
399    }
400    if( edgeIncident(f, G.head(e), _last) ) {
401      _first = G.tail(e);
402      return true;
403    }
404    return false;
405  }
406
407  template<typename Gr>
408  bool DynamicPath<Gr>::pushFront(const GraphEdge &e) {
409    if( G.valid(_first) ) {
410        if( edgeIncident(e, _first, _first) ) {
411          edges.push_front(e);
412          return true;
413        }
414        else
415          return false;
416    }
417    else if( length() < 1 || connectTwoEdges(e, edges[0]) ) {
418      edges.push_front(e);
419      return true;
420    }
421    else
422      return false;
423  }
424
425  template<typename Gr>
426  bool DynamicPath<Gr>::pushBack(const GraphEdge &e) {
427    if( G.valid(_last) ) {
428        if( edgeIncident(e, _last, _last) ) {
429          edges.push_back(e);
430          return true;
431        }
432        else
433          return false;
434    }
435    else if( length() < 1 || connectTwoEdges(edges[0], e) ) {
436      edges.push_back(e);
437      return true;
438    }
439    else
440      return false;
441  }
442
443
444  template<typename Gr>
445  bool DynamicPath<Gr>::setFrom(const GraphNode &n) {
446    if( G.valid(_first) ) {
447      return _first == n;
448    }
449    else {
450      if( length() > 0) {
451        if( edgeIncident(edges[0], n, _last) ) {
452          _first = n;
453          return true;
454        }
455        else return false;
456      }
457      else {
458        _first = _last = n;
459        return true;
460      }
461    }
462  }
463
464  template<typename Gr>
465  bool DynamicPath<Gr>::setTo(const GraphNode &n) {
466    if( G.valid(_last) ) {
467      return _last == n;
468    }
469    else {
470      if( length() > 0) {
471        if( edgeIncident(edges[0], n, _first) ) {
472          _last = n;
473          return true;
474        }
475        else return false;
476      }
477      else {
478        _first = _last = n;
479        return true;
480      }
481    }
482  }
483
484
485  template<typename Gr>
486  typename DynamicPath<Gr>::NodeIt
487  DynamicPath<Gr>::tail(const EdgeIt& e) const {
488    NodeIt n;
489
490    if( e.it == edges.end() ) {
491      // FIXME: invalid-> invalid
492      n.idx = length() + 1;
493      n.tail = true;
494      return n;
495    }
496
497    n.idx = e.it-edges.begin();
498    n.tail = e.forw;
499    return n;
500  }
501
502  template<typename Gr>
503  typename DynamicPath<Gr>::NodeIt
504  DynamicPath<Gr>::head(const EdgeIt& e) const {
505    if( e.it == edges.end()-1 ) {
506      return _last;
507    }
508
509    EdgeIt next_edge = e;
510    next(next_edge);
511    return tail(next_edge);
512  }
513     
514  template<typename Gr>
515  typename DynamicPath<Gr>::GraphEdge
516  DynamicPath<Gr>::graphEdge(const EdgeIt& e) const {
517    if( e.it != edges.end() ) {
518      return *e.it;
519    }
520    else {
521      return INVALID;
522    }
523  }
524 
525  template<typename Gr>
526  typename DynamicPath<Gr>::GraphNode
527  DynamicPath<Gr>::graphNode(const NodeIt& n) const {
528    if( n.idx < length() ) {
529      return n.tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]);
530    }
531    else if( n.idx == length() ) {
532      return _last;
533    }
534    else {
535      return INVALID;
536    }
537  }
538
539  template<typename Gr>
540  typename DynamicPath<Gr>::EdgeIt&
541  DynamicPath<Gr>::nth(EdgeIt &e, size_t k) const {
542    if( k<0 || k>=length() ) {
543      // FIXME: invalid EdgeIt
544      e.it = edges.end();
545      e.forw = true;
546      return e;
547    }
548
549    e.it = edges.begin()+k;
550    if(k==0) {
551      e.forw = ( G.tail(*e.it) == _first );
552    }
553    else {
554      e.forw = ( G.tail(*e.it) == G.tail(edges[k-1]) ||
555                 G.tail(*e.it) == G.head(edges[k-1]) );
556    }
557    return e;
558  }
559   
560  template<typename Gr>
561  typename DynamicPath<Gr>::NodeIt&
562  DynamicPath<Gr>::nth(NodeIt &n, size_t k) const {
563    if( k<0 || k>length() ) {
564      // FIXME: invalid NodeIt
565      n.idx = length()+1;
566      n.tail = true;
567      return n;
568    }
569    if( k==length() ) {
570      n.idx = length();
571      n.tail = true;
572      return n;
573    }
574    n = tail(nth<EdgeIt>(k));
575    return n;
576  }
577
578  // Reszut konstruktorok:
579
580
581  template<typename Gr>
582  DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const EdgeIt &a,
583                               const EdgeIt &b) :
584    G(P.G), edges(a.it, b.it)    // WARNING: if b.it < a.it this will blow up!
585  {
586    if( G.valid(P._first) && a.it < P.edges.end() ) {
587      _first = ( a.forw ? G.tail(*a.it) : G.head(*a.it) );
588      if( b.it < P.edges.end() ) {
589        _last = ( b.forw ? G.tail(*b.it) : G.head(*b.it) );
590      }
591      else {
592        _last = P._last;
593      }
594    }
595  }
596
597  template<typename Gr>
598  DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const NodeIt &a,
599                               const NodeIt &b) : G(P.G)
600  {
601    if( !P.valid(a) || !P.valid(b) )
602      return;
603
604    int ai = a.idx, bi = b.idx;
605    if( bi<ai )
606      swap(ai,bi);
607   
608    edges.resize(bi-ai);
609    copy(P.edges.begin()+ai, P.edges.begin()+bi, edges.begin());
610
611    _first = P.graphNode(a);
612    _last = P.graphNode(b);
613  }
614
615
616} // namespace hugo
617
618#endif // HUGO_PATH_H
Note: See TracBrowser for help on using the repository browser.