COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/iterable_graph_extender.h @ 1933:a876a3d6a4c7

Last change on this file since 1933:a876a3d6a4c7 was 1933:a876a3d6a4c7, checked in by Balazs Dezso, 18 years ago

Revising the bpugraph concept

We need a public but very limited ANode and BNode class
It can be used with ItemSetTraits? and with some special maps

By example:
DescriptorMap?<Graph, ANode>
InvertableMap?<Graph, ANode, string>
IterableBoolMap?<Graph, ANode>
IterableIntMap?<Graph, ANode>
IterableValueMap?<Graph, ANode, string>

File size: 11.5 KB
RevLine 
[946]1// -*- c++ -*-
2#ifndef LEMON_ITERABLE_GRAPH_EXTENDER_H
3#define LEMON_ITERABLE_GRAPH_EXTENDER_H
4
5#include <lemon/invalid.h>
[1448]6#include <lemon/utility.h>
[946]7
8namespace lemon {
9 
10  template <typename _Base>
11  class IterableGraphExtender : public _Base {
[962]12  public:
[946]13
[1448]14    /// Indicates that the graph is undirected.
15
16    ///\todo Better name?
17    ///
18    ///\bug Should it be here?
[1909]19    typedef False UTag;
[1448]20
[946]21    typedef _Base Parent;
22    typedef IterableGraphExtender<_Base> Graph;
23
24    typedef typename Parent::Node Node;
25    typedef typename Parent::Edge Edge;
26
27
28    class NodeIt : public Node {
29      const Graph* graph;
30    public:
31
32      NodeIt() {}
33
34      NodeIt(Invalid i) : Node(i) { }
35
[962]36      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
[946]37        _graph.first(*static_cast<Node*>(this));
38      }
39
40      NodeIt(const Graph& _graph, const Node& node)
41        : Node(node), graph(&_graph) {}
42
43      NodeIt& operator++() {
44        graph->next(*this);
45        return *this;
46      }
47
48    };
49
50
51    class EdgeIt : public Edge {
52      const Graph* graph;
53    public:
54
55      EdgeIt() { }
56
57      EdgeIt(Invalid i) : Edge(i) { }
58
[962]59      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
[946]60        _graph.first(*static_cast<Edge*>(this));
61      }
62
63      EdgeIt(const Graph& _graph, const Edge& e) :
64        Edge(e), graph(&_graph) { }
65
66      EdgeIt& operator++() {
67        graph->next(*this);
68        return *this;
69      }
70
71    };
72
73
74    class OutEdgeIt : public Edge {
75      const Graph* graph;
76    public:
77
78      OutEdgeIt() { }
79
80      OutEdgeIt(Invalid i) : Edge(i) { }
81
82      OutEdgeIt(const Graph& _graph, const Node& node)
[962]83        : graph(&_graph) {
[946]84        _graph.firstOut(*this, node);
85      }
86
87      OutEdgeIt(const Graph& _graph, const Edge& edge)
88        : Edge(edge), graph(&_graph) {}
89
90      OutEdgeIt& operator++() {
91        graph->nextOut(*this);
92        return *this;
93      }
94
95    };
96
97
98    class InEdgeIt : public Edge {
99      const Graph* graph;
100    public:
101
102      InEdgeIt() { }
103
104      InEdgeIt(Invalid i) : Edge(i) { }
105
106      InEdgeIt(const Graph& _graph, const Node& node)
[962]107        : graph(&_graph) {
[946]108        _graph.firstIn(*this, node);
109      }
110
111      InEdgeIt(const Graph& _graph, const Edge& edge) :
112        Edge(edge), graph(&_graph) {}
113
114      InEdgeIt& operator++() {
115        graph->nextIn(*this);
116        return *this;
117      }
118
119    };
120
[1627]121    /// \brief Base node of the iterator
[1158]122    ///
123    /// Returns the base node (ie. the source in this case) of the iterator
124    Node baseNode(const OutEdgeIt &e) const {
[1564]125      return Parent::source((Edge)e);
[1158]126    }
[1627]127    /// \brief Running node of the iterator
[1158]128    ///
129    /// Returns the running node (ie. the target in this case) of the
130    /// iterator
131    Node runningNode(const OutEdgeIt &e) const {
[1564]132      return Parent::target((Edge)e);
[1158]133    }
134
[1627]135    /// \brief Base node of the iterator
[1158]136    ///
137    /// Returns the base node (ie. the target in this case) of the iterator
138    Node baseNode(const InEdgeIt &e) const {
[1564]139      return Parent::target((Edge)e);
[1158]140    }
[1627]141    /// \brief Running node of the iterator
[1158]142    ///
143    /// Returns the running node (ie. the source in this case) of the
144    /// iterator
145    Node runningNode(const InEdgeIt &e) const {
[1564]146      return Parent::source((Edge)e);
[1158]147    }
148
[946]149    using Parent::first;
150
[1627]151    /// \brief The opposite node on the given edge.
152    ///
153    /// Gives back the opposite on the given edge.
154    Node oppositeNode(const Node& n, const Edge& e) const {
155      if (Parent::source(e) == n) {
156        return Parent::target(e);
157      } else {
158        return Parent::source(e);
159      }
160    }
161
[946]162  private:
163
[1230]164    // void first(NodeIt &) const;
165    // void first(EdgeIt &) const;
166    // void first(OutEdgeIt &) const;
167    // void first(InEdgeIt &) const;
[946]168
169  };
[1158]170
171
172
173
174
[946]175 
[962]176  template <typename _Base>
[1909]177  class IterableUGraphExtender : public IterableGraphExtender<_Base> {
[962]178  public:
179
[1448]180    /// Indicates that the graph is undirected.
181
182    ///\todo Better name?
183    ///
184    ///\bug Should it be here?
185    ///\bug Should be tested in the concept checker whether it is defined
186    ///correctly.
[1909]187    typedef True UTag;
[1448]188
[962]189    typedef IterableGraphExtender<_Base> Parent;
[1909]190    typedef IterableUGraphExtender<_Base> Graph;
[1021]191    typedef typename Parent::Node Node;
[1627]192    typedef typename Parent::Edge Edge;
[1909]193    typedef typename Parent::UEdge UEdge;
[962]194
[1909]195    class UEdgeIt : public Parent::UEdge {
[962]196      const Graph* graph;
197    public:
198
[1909]199      UEdgeIt() { }
[962]200
[1909]201      UEdgeIt(Invalid i) : UEdge(i) { }
[962]202
[1909]203      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
204        _graph.first(*static_cast<UEdge*>(this));
[962]205      }
206
[1909]207      UEdgeIt(const Graph& _graph, const UEdge& e) :
208        UEdge(e), graph(&_graph) { }
[962]209
[1909]210      UEdgeIt& operator++() {
[962]211        graph->next(*this);
212        return *this;
213      }
214
215    };
216
[1909]217    class IncEdgeIt : public Parent::UEdge {
[1021]218      const Graph* graph;
[1704]219      bool direction;
[1909]220      friend class IterableUGraphExtender;
[1021]221    public:
222
[1030]223      IncEdgeIt() { }
[1021]224
[1909]225      IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
[1021]226
[1704]227      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
228        _graph.firstInc(*this, direction, n);
[1021]229      }
230
[1909]231      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
232        : graph(&_graph), UEdge(ue) {
[1704]233        direction = (_graph.source(ue) == n);
[1158]234      }
[1021]235
[1030]236      IncEdgeIt& operator++() {
[1704]237        graph->nextInc(*this, direction);
[1021]238        return *this;
239      }
240    };
241
[1158]242    using Parent::baseNode;
243    using Parent::runningNode;
244
245    /// Base node of the iterator
246    ///
247    /// Returns the base node of the iterator
248    Node baseNode(const IncEdgeIt &e) const {
[1704]249      return e.direction ? source(e) : target(e);
[1021]250    }
[1158]251    /// Running node of the iterator
252    ///
253    /// Returns the running node of the iterator
254    Node runningNode(const IncEdgeIt &e) const {
[1704]255      return e.direction ? target(e) : source(e);
[1021]256    }
257
[1627]258    /// \brief The opposite node on the given undirected edge.
259    ///
260    /// Gives back the opposite on the given undirected edge.
[1909]261    Node oppositeNode(const Node& n, const UEdge& e) const {
[1627]262      if (Parent::source(e) == n) {
263        return Parent::target(e);
264      } else {
265        return Parent::source(e);
266      }
267    }
268
[962]269  };
[1820]270
271
272  template <typename _Base>
[1910]273  class IterableBpUGraphExtender : public _Base {
[1820]274  public:
275    typedef _Base Parent;
[1910]276    typedef IterableBpUGraphExtender Graph;
[1820]277   
278    typedef typename Parent::Node Node;
[1910]279    typedef typename Parent::ANode ANode;
280    typedef typename Parent::BNode BNode;
[1820]281    typedef typename Parent::Edge Edge;
[1909]282    typedef typename Parent::UEdge UEdge;
[1820]283 
284    class NodeIt : public Node {
285      const Graph* graph;
286    public:
287   
288      NodeIt() { }
289   
290      NodeIt(Invalid i) : Node(INVALID) { }
291   
292      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
293        graph->first(static_cast<Node&>(*this));
294      }
295
296      NodeIt(const Graph& _graph, const Node& node)
297        : Node(node), graph(&_graph) { }
298   
299      NodeIt& operator++() {
300        graph->next(*this);
301        return *this;
302      }
303
304    };
305
[1933]306    class ANodeIt : public ANode {
[1910]307      friend class IterableBpUGraphExtender;
[1820]308      const Graph* graph;
309    public:
310   
[1910]311      ANodeIt() { }
[1820]312   
[1910]313      ANodeIt(Invalid i) : Node(INVALID) { }
[1820]314   
[1910]315      explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
316        graph->firstANode(static_cast<Node&>(*this));
[1820]317      }
318
[1910]319      ANodeIt(const Graph& _graph, const Node& node)
[1820]320        : Node(node), graph(&_graph) {}
321   
[1910]322      ANodeIt& operator++() {
323        graph->nextANode(*this);
[1820]324        return *this;
325      }
326    };
327
[1933]328    class BNodeIt : public BNode {
[1910]329      friend class IterableBpUGraphExtender;
[1820]330      const Graph* graph;
331    public:
332   
[1910]333      BNodeIt() { }
[1820]334   
[1910]335      BNodeIt(Invalid i) : Node(INVALID) { }
[1820]336   
[1910]337      explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
338        graph->firstBNode(static_cast<Node&>(*this));
[1820]339      }
340
[1910]341      BNodeIt(const Graph& _graph, const Node& node)
[1820]342        : Node(node), graph(&_graph) {}
343   
[1910]344      BNodeIt& operator++() {
345        graph->nextBNode(*this);
[1820]346        return *this;
347      }
348    };
349
350    class EdgeIt : public Edge {
[1910]351      friend class IterableBpUGraphExtender;
[1820]352      const Graph* graph;
353    public:
354   
355      EdgeIt() { }
356   
357      EdgeIt(Invalid i) : Edge(INVALID) { }
358   
359      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
360        graph->first(static_cast<Edge&>(*this));
361      }
362
363      EdgeIt(const Graph& _graph, const Edge& edge)
364        : Edge(edge), graph(&_graph) { }
365   
366      EdgeIt& operator++() {
367        graph->next(*this);
368        return *this;
369      }
370
371    };
372
[1909]373    class UEdgeIt : public UEdge {
[1910]374      friend class IterableBpUGraphExtender;
[1820]375      const Graph* graph;
376    public:
377   
[1909]378      UEdgeIt() { }
[1820]379   
[1909]380      UEdgeIt(Invalid i) : UEdge(INVALID) { }
[1820]381   
[1909]382      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
383        graph->first(static_cast<UEdge&>(*this));
[1820]384      }
385
[1909]386      UEdgeIt(const Graph& _graph, const UEdge& edge)
387        : UEdge(edge), graph(&_graph) { }
[1820]388   
[1909]389      UEdgeIt& operator++() {
[1820]390        graph->next(*this);
391        return *this;
392      }
393    };
394
395    class OutEdgeIt : public Edge {
[1910]396      friend class IterableBpUGraphExtender;
[1820]397      const Graph* graph;
398    public:
399   
400      OutEdgeIt() { }
401   
402      OutEdgeIt(Invalid i) : Edge(i) { }
403   
404      OutEdgeIt(const Graph& _graph, const Node& node)
405        : graph(&_graph) {
406        graph->firstOut(*this, node);
407      }
408   
409      OutEdgeIt(const Graph& _graph, const Edge& edge)
410        : Edge(edge), graph(&_graph) {}
411   
412      OutEdgeIt& operator++() {
413        graph->nextOut(*this);
414        return *this;
415      }
416
417    };
418
419
420    class InEdgeIt : public Edge {
[1910]421      friend class IterableBpUGraphExtender;
[1820]422      const Graph* graph;
423    public:
424   
425      InEdgeIt() { }
426   
427      InEdgeIt(Invalid i) : Edge(i) { }
428   
429      InEdgeIt(const Graph& _graph, const Node& node)
430        : graph(&_graph) {
431        graph->firstIn(*this, node);
432      }
433   
434      InEdgeIt(const Graph& _graph, const Edge& edge) :
435        Edge(edge), graph(&_graph) {}
436   
437      InEdgeIt& operator++() {
438        graph->nextIn(*this);
439        return *this;
440      }
441
442    };
443 
444    /// \brief Base node of the iterator
445    ///
446    /// Returns the base node (ie. the source in this case) of the iterator
447    Node baseNode(const OutEdgeIt &e) const {
448      return Parent::source((Edge&)e);
449    }
450    /// \brief Running node of the iterator
451    ///
452    /// Returns the running node (ie. the target in this case) of the
453    /// iterator
454    Node runningNode(const OutEdgeIt &e) const {
455      return Parent::target((Edge&)e);
456    }
457 
458    /// \brief Base node of the iterator
459    ///
460    /// Returns the base node (ie. the target in this case) of the iterator
461    Node baseNode(const InEdgeIt &e) const {
462      return Parent::target((Edge&)e);
463    }
464    /// \brief Running node of the iterator
465    ///
466    /// Returns the running node (ie. the source in this case) of the
467    /// iterator
468    Node runningNode(const InEdgeIt &e) const {
469      return Parent::source((Edge&)e);
470    }
471 
[1909]472    class IncEdgeIt : public Parent::UEdge {
[1910]473      friend class IterableBpUGraphExtender;
[1820]474      const Graph* graph;
475      bool direction;
476    public:
477   
478      IncEdgeIt() { }
479   
[1909]480      IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
[1820]481   
482      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
483        graph->firstInc(*this, direction, n);
484      }
485
[1909]486      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
487        : graph(&_graph), UEdge(ue) {
[1820]488        direction = (graph->source(ue) == n);
489      }
490
491      IncEdgeIt& operator++() {
492        graph->nextInc(*this, direction);
493        return *this;
494      }
495    };
496 
497
498    /// Base node of the iterator
499    ///
500    /// Returns the base node of the iterator
501    Node baseNode(const IncEdgeIt &e) const {
502      return e.direction ? source(e) : target(e);
503    }
504
505    /// Running node of the iterator
506    ///
507    /// Returns the running node of the iterator
508    Node runningNode(const IncEdgeIt &e) const {
509      return e.direction ? target(e) : source(e);
510    }
511 
512  };
513
[946]514}
515
516#endif // LEMON_GRAPH_EXTENDER_H
Note: See TracBrowser for help on using the repository browser.