COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/klao/path.h @ 225:b72b36a25170

Last change on this file since 225:b72b36a25170 was 225:b72b36a25170, checked in by Mihaly Barasz, 17 years ago

Ut struktura. Elso valtozat.

File size: 8.6 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
14#include <invalid.h>
15
16namespace hugo {
17
18  /* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata
19     elott. Eleg bonyinak nez ki, ahogyan azokat az STL-ben hasznaljak. */
20
21  template<typename Graph>
22  class Path {
23
24  public:
25    typedef typename Graph::Edge GraphEdge;
26    typedef typename Graph::Node GraphNode;
27    class NodeIt;
28    class EdgeIt;
29
30  protected:
31    Graph& G;
32    // FIXME: ehelyett eleg lenne tarolni ket boolt: a ket szelso el
33    // iranyitasat:
34    GraphNode _first, _last;
35    typedef std::deque<GraphEdge> Container;
36    Container edges;
37
38  public:
39
40    Path(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {}
41
42    /// Subpath defined by two nodes
43    Path(Path const& P, NodeIt a, NodeIt b) { FIXME; }
44    /// Subpath defined by tow edges. Contains edges in [a,b)
45    Path(Path const& P, EdgeIt a, EdgeIt b) { FIXME; }
46   
47    size_t length() const { return edges.size(); }
48    GraphNode from() const { return _first; }
49    GraphNode to() const { return _last; }
50
51    NodeIt& first(NodeIt &n) const { return nth(n, 0); }
52    EdgeIt& first(EdgeIt &e) const { return nth(e, 0); }
53    template<typename It>
54    It first() const {
55      It e;
56      first(e);
57      return e;
58    }
59
60    NodeIt& nth(NodeIt &, size_t) const;
61    EdgeIt& nth(EdgeIt &, size_t) const;
62    template<typename It>
63    It nth(size_t n) const {
64      It e;
65      nth(e, n);
66      return e;
67    }
68
69    bool valid(const NodeIt &n) const { return n.idx <= length(); }
70    bool valid(const EdgeIt &e) const { return e.it < edges.end(); }
71
72    bool isForward(const EdgeIt &e) const { return e.forw; }
73
74    EdgeIt& next(EdgeIt &e) const;
75    NodeIt& next(NodeIt &n) const;
76    template <typename It>
77    It getNext(It it) const {
78      It tmp(it); return next(tmp);
79    }
80
81    // A path is constructed using the following four functions.
82    // They return false if the requested operation is inconsistent
83    // with the path constructed so far.
84    // If your path has only one edge you MUST set either "from" or "to"!
85    // So you probably SHOULD call it in any case to be safe (and check the
86    // returned value to check if your path is consistent with your idea).
87    bool pushFront(const GraphEdge &e);
88    bool pushBack(const GraphEdge &e);
89    bool setFrom(const GraphNode &n);
90    bool setTo(const GraphNode &n);
91
92    // WARNING: these two functions return the head/tail of an edge with
93    // respect to the direction of the path!
94    // So G.head(P.graphEdge(e)) == P.graphNode(P.head(e)) holds only if
95    // P.forward(e) is true (or the edge is a loop)!
96    NodeIt head(const EdgeIt& e) const;
97    NodeIt tail(const EdgeIt& e) const;
98
99    // FIXME: ezeknek valami jobb nev kellene!!!
100    GraphEdge graphEdge(const EdgeIt& e) const;
101    GraphNode graphNode(const NodeIt& n) const;
102
103
104    /*** Iterator classes ***/
105    class EdgeIt {
106      friend class Path;
107
108      typename Container::const_iterator it;
109      bool forw;
110    public:
111      // FIXME: jarna neki ilyen is...
112      // EdgeIt(Invalid);
113
114      bool forward() const { return forw; }
115
116      bool operator==(const EdgeIt& e) const { return it==e.it; }
117      bool operator!=(const EdgeIt& e) const { return it!=e.it; }
118      bool operator<(const EdgeIt& e) const { return it<e.it; }
119    };
120
121    class NodeIt {
122      friend class Path;
123      friend class EdgeIt;
124
125      int idx;
126      bool tail;  // Is this node the tail of the edge with same idx?
127
128    public:
129      // FIXME: jarna neki ilyen is...
130      // NodeIt(Invalid);
131
132      bool operator==(const NodeIt& n) const { return idx==n.idx; }
133      bool operator!=(const NodeIt& n) const { return idx!=n.idx; }
134      bool operator<(const NodeIt& n) const { return idx<n.idx; }
135    };
136
137  private:
138    bool edgeIncident(const GraphEdge &e, const GraphNode &a,
139                      GraphNode &b);
140    bool connectTwoEdges(const GraphEdge &e, const GraphEdge &f);
141  };
142
143  template<typename Gr>
144  typename Path<Gr>::EdgeIt&
145  Path<Gr>::next(Path::EdgeIt &e) const {
146    if( e.it == edges.end() )
147      return e;
148
149    GraphNode common_node = ( e.forw ? G.head(*e.it) : G.tail(*e.it) );
150    ++e.it;
151
152    // Invalid edgeit is always forward :)
153    if( e.it == edges.end() ) {
154      e.forw = true;
155      return e;
156    }
157
158    e.forw = ( G.tail(*e.it) == common_node );
159    return e;
160  }
161
162  template<typename Gr>
163  typename Path<Gr>::NodeIt& Path<Gr>::next(NodeIt &n) const {
164    if( n.idx >= length() ) {
165      // FIXME: invalid
166      n.idx = length()+1;
167      return n;
168    }
169
170   
171    GraphNode next_node = ( n.tail ? G.head(edges[n.idx]) :
172                              G.tail(edges[n.idx]) );
173    ++n.idx;
174    if( n.idx < length() ) {
175      n.tail = ( next_node == G.tail(edges[n.idx]) );
176    }
177    else {
178      n.tail = true;
179    }
180
181    return n;
182  }
183
184  template<typename Gr>
185  bool Path<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a,
186                          GraphNode &b) {
187    if( G.tail(e) == a ) {
188      b=G.head(e);
189      return true;
190    }
191    if( G.head(e) == a ) {
192      b=G.tail(e);
193      return true;
194    }
195    return false;
196  }
197
198  template<typename Gr>
199  bool Path<Gr>::connectTwoEdges(const GraphEdge &e,
200                             const GraphEdge &f) {
201    if( edgeIncident(f, G.tail(e), _last) ) {
202      _first = G.head(e);
203      return true;
204    }
205    if( edgeIncident(f, G.head(e), _last) ) {
206      _first = G.tail(e);
207      return true;
208    }
209    return false;
210  }
211
212  template<typename Gr>
213  bool Path<Gr>::pushFront(const GraphEdge &e) {
214    if( G.valid(_first) ) {
215        if( edgeIncident(e, _first, _first) ) {
216          edges.push_front(e);
217          return true;
218        }
219        else
220          return false;
221    }
222    else if( length() < 1 || connectTwoEdges(e, edges[0]) ) {
223      edges.push_front(e);
224      return true;
225    }
226    else
227      return false;
228  }
229
230  template<typename Gr>
231  bool Path<Gr>::pushBack(const GraphEdge &e) {
232    if( G.valid(_last) ) {
233        if( edgeIncident(e, _last, _last) ) {
234          edges.push_back(e);
235          return true;
236        }
237        else
238          return false;
239    }
240    else if( length() < 1 || connectTwoEdges(edges[0], e) ) {
241      edges.push_back(e);
242      return true;
243    }
244    else
245      return false;
246  }
247
248
249  template<typename Gr>
250  bool Path<Gr>::setFrom(const GraphNode &n) {
251    if( G.valid(_first) ) {
252      return _first == n;
253    }
254    else {
255      if( length() > 0) {
256        if( edgeIncident(edges[0], n, _last) ) {
257          _first = n;
258          return true;
259        }
260        else return false;
261      }
262      else {
263        _first = _last = n;
264        return true;
265      }
266    }
267  }
268
269  template<typename Gr>
270  bool Path<Gr>::setTo(const GraphNode &n) {
271    if( G.valid(_last) ) {
272      return _last == n;
273    }
274    else {
275      if( length() > 0) {
276        if( edgeIncident(edges[0], n, _first) ) {
277          _last = n;
278          return true;
279        }
280        else return false;
281      }
282      else {
283        _first = _last = n;
284        return true;
285      }
286    }
287  }
288
289
290  template<typename Gr>
291  typename Path<Gr>::NodeIt
292  Path<Gr>::tail(const EdgeIt& e) const {
293    NodeIt n;
294
295    if( e.it == edges.end() ) {
296      // FIXME: invalid-> invalid
297      n.idx = length() + 1;
298      n.tail = true;
299      return n;
300    }
301
302    n.idx = e.it-edges.begin();
303    n.tail = e.forw;
304  }
305
306  template<typename Gr>
307  typename Path<Gr>::NodeIt
308  Path<Gr>::head(const EdgeIt& e) const {
309    if( e.it == edges.end()-1 ) {
310      return _last;
311    }
312
313    EdgeIt next_edge = e;
314    next(next_edge);
315    return tail(next_edge);
316  }
317     
318  template<typename Gr>
319  typename Path<Gr>::GraphEdge
320  Path<Gr>::graphEdge(const EdgeIt& e) const {
321    if( e.it != edges.end() ) {
322      return *e.it;
323    }
324    else {
325      return INVALID;
326    }
327  }
328 
329  template<typename Gr>
330  typename Path<Gr>::GraphNode
331  Path<Gr>::graphNode(const NodeIt& n) const {
332    if( n.idx < length() ) {
333      return n.tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]);
334    }
335    else if( n.idx == length() ) {
336      return _last;
337    }
338    else {
339      return INVALID;
340    }
341  }
342
343  template<typename Gr>
344  typename Path<Gr>::EdgeIt& Path<Gr>::nth(EdgeIt &e, size_t k) const {
345    if( k<0 || k>=length() ) {
346      // FIXME: invalid EdgeIt
347      e.it = edges.end();
348      e.forw = true;
349      return e;
350    }
351
352    e.it = edges.begin()+k;
353    if(k==0) {
354      e.forw = ( G.tail(*e.it) == _first );
355    }
356    else {
357      e.forw = ( G.tail(*e.it) == G.tail(edges[k-1]) ||
358                 G.tail(*e.it) == G.head(edges[k-1]) );
359    }
360    return e;
361  }
362   
363  template<typename Gr>
364  typename Path<Gr>::NodeIt& Path<Gr>::nth(NodeIt &n, size_t k) const {
365    if( k<0 || k>length() ) {
366      // FIXME: invalid NodeIt
367      n.idx = length()+1;
368      n.tail = true;
369      return n;
370    }
371    if( k==length() ) {
372      n.idx = length();
373      n.tail = true;
374      return n;
375    }
376    n = tail(nth<EdgeIt>(k));
377    return n;
378  }
379
380
381} // namespace hugo
382
383#endif // HUGO_PATH_H
Note: See TracBrowser for help on using the repository browser.