COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/iterable_graph_extender.h @ 1854:a68d4f93b1fb

Last change on this file since 1854:a68d4f93b1fb was 1820:22099ef840d7, checked in by Balazs Dezso, 18 years ago

Undir Bipartite Graph/Full? and Smart/ without concept, doc and concept
checking

File size: 11.8 KB
Line 
1// -*- c++ -*-
2#ifndef LEMON_ITERABLE_GRAPH_EXTENDER_H
3#define LEMON_ITERABLE_GRAPH_EXTENDER_H
4
5#include <lemon/invalid.h>
6#include <lemon/utility.h>
7
8namespace lemon {
9 
10  template <typename _Base>
11  class IterableGraphExtender : public _Base {
12  public:
13
14    /// Indicates that the graph is undirected.
15
16    ///\todo Better name?
17    ///
18    ///\bug Should it be here?
19    typedef False UndirTag;
20
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
36      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
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
59      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
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)
83        : graph(&_graph) {
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)
107        : graph(&_graph) {
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
121    /// \brief Base node of the iterator
122    ///
123    /// Returns the base node (ie. the source in this case) of the iterator
124    Node baseNode(const OutEdgeIt &e) const {
125      return Parent::source((Edge)e);
126    }
127    /// \brief Running node of the iterator
128    ///
129    /// Returns the running node (ie. the target in this case) of the
130    /// iterator
131    Node runningNode(const OutEdgeIt &e) const {
132      return Parent::target((Edge)e);
133    }
134
135    /// \brief Base node of the iterator
136    ///
137    /// Returns the base node (ie. the target in this case) of the iterator
138    Node baseNode(const InEdgeIt &e) const {
139      return Parent::target((Edge)e);
140    }
141    /// \brief Running node of the iterator
142    ///
143    /// Returns the running node (ie. the source in this case) of the
144    /// iterator
145    Node runningNode(const InEdgeIt &e) const {
146      return Parent::source((Edge)e);
147    }
148
149    using Parent::first;
150
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
162  private:
163
164    // void first(NodeIt &) const;
165    // void first(EdgeIt &) const;
166    // void first(OutEdgeIt &) const;
167    // void first(InEdgeIt &) const;
168
169  };
170
171
172
173
174
175 
176  template <typename _Base>
177  class IterableUndirGraphExtender : public IterableGraphExtender<_Base> {
178  public:
179
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.
187    typedef True UndirTag;
188
189    typedef IterableGraphExtender<_Base> Parent;
190    typedef IterableUndirGraphExtender<_Base> Graph;
191    typedef typename Parent::Node Node;
192    typedef typename Parent::Edge Edge;
193    typedef typename Parent::UndirEdge UndirEdge;
194
195    class UndirEdgeIt : public Parent::UndirEdge {
196      const Graph* graph;
197    public:
198
199      UndirEdgeIt() { }
200
201      UndirEdgeIt(Invalid i) : UndirEdge(i) { }
202
203      explicit UndirEdgeIt(const Graph& _graph) : graph(&_graph) {
204        _graph.first(*static_cast<UndirEdge*>(this));
205      }
206
207      UndirEdgeIt(const Graph& _graph, const UndirEdge& e) :
208        UndirEdge(e), graph(&_graph) { }
209
210      UndirEdgeIt& operator++() {
211        graph->next(*this);
212        return *this;
213      }
214
215    };
216
217    class IncEdgeIt : public Parent::UndirEdge {
218      const Graph* graph;
219      bool direction;
220      friend class IterableUndirGraphExtender;
221    public:
222
223      IncEdgeIt() { }
224
225      IncEdgeIt(Invalid i) : UndirEdge(i), direction(false) { }
226
227      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
228        _graph.firstInc(*this, direction, n);
229      }
230
231      IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n)
232        : graph(&_graph), UndirEdge(ue) {
233        direction = (_graph.source(ue) == n);
234      }
235
236      IncEdgeIt& operator++() {
237        graph->nextInc(*this, direction);
238        return *this;
239      }
240    };
241
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 {
249      return e.direction ? source(e) : target(e);
250    }
251    /// Running node of the iterator
252    ///
253    /// Returns the running node of the iterator
254    Node runningNode(const IncEdgeIt &e) const {
255      return e.direction ? target(e) : source(e);
256    }
257
258    /// \brief The opposite node on the given undirected edge.
259    ///
260    /// Gives back the opposite on the given undirected edge.
261    Node oppositeNode(const Node& n, const UndirEdge& e) const {
262      if (Parent::source(e) == n) {
263        return Parent::target(e);
264      } else {
265        return Parent::source(e);
266      }
267    }
268
269  };
270
271
272  template <typename _Base>
273  class IterableUndirBipartiteGraphExtender : public _Base {
274  public:
275    typedef _Base Parent;
276    typedef IterableUndirBipartiteGraphExtender Graph;
277   
278    typedef typename Parent::Node Node;
279    typedef typename Parent::UpperNode UpperNode;
280    typedef typename Parent::LowerNode LowerNode;
281    typedef typename Parent::Edge Edge;
282    typedef typename Parent::UndirEdge UndirEdge;
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
306    class UpperNodeIt : public Node {
307      friend class IterableUndirBipartiteGraphExtender;
308      const Graph* graph;
309    public:
310   
311      UpperNodeIt() { }
312   
313      UpperNodeIt(Invalid i) : Node(INVALID) { }
314   
315      explicit UpperNodeIt(const Graph& _graph) : graph(&_graph) {
316        graph->firstUpper(static_cast<Node&>(*this));
317      }
318
319      UpperNodeIt(const Graph& _graph, const Node& node)
320        : Node(node), graph(&_graph) {}
321   
322      UpperNodeIt& operator++() {
323        graph->nextUpper(*this);
324        return *this;
325      }
326    };
327
328    class LowerNodeIt : public Node {
329      friend class IterableUndirBipartiteGraphExtender;
330      const Graph* graph;
331    public:
332   
333      LowerNodeIt() { }
334   
335      LowerNodeIt(Invalid i) : Node(INVALID) { }
336   
337      explicit LowerNodeIt(const Graph& _graph) : graph(&_graph) {
338        graph->firstLower(static_cast<Node&>(*this));
339      }
340
341      LowerNodeIt(const Graph& _graph, const Node& node)
342        : Node(node), graph(&_graph) {}
343   
344      LowerNodeIt& operator++() {
345        graph->nextLower(*this);
346        return *this;
347      }
348    };
349
350    class EdgeIt : public Edge {
351      friend class IterableUndirBipartiteGraphExtender;
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
373    class UndirEdgeIt : public UndirEdge {
374      friend class IterableUndirBipartiteGraphExtender;
375      const Graph* graph;
376    public:
377   
378      UndirEdgeIt() { }
379   
380      UndirEdgeIt(Invalid i) : UndirEdge(INVALID) { }
381   
382      explicit UndirEdgeIt(const Graph& _graph) : graph(&_graph) {
383        graph->first(static_cast<UndirEdge&>(*this));
384      }
385
386      UndirEdgeIt(const Graph& _graph, const UndirEdge& edge)
387        : UndirEdge(edge), graph(&_graph) { }
388   
389      UndirEdgeIt& operator++() {
390        graph->next(*this);
391        return *this;
392      }
393    };
394
395    class OutEdgeIt : public Edge {
396      friend class IterableUndirBipartiteGraphExtender;
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 {
421      friend class IterableUndirBipartiteGraphExtender;
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 
472    class IncEdgeIt : public Parent::UndirEdge {
473      friend class IterableUndirBipartiteGraphExtender;
474      const Graph* graph;
475      bool direction;
476    public:
477   
478      IncEdgeIt() { }
479   
480      IncEdgeIt(Invalid i) : UndirEdge(i), direction(true) { }
481   
482      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
483        graph->firstInc(*this, direction, n);
484      }
485
486      IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n)
487        : graph(&_graph), UndirEdge(ue) {
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
514}
515
516#endif // LEMON_GRAPH_EXTENDER_H
Note: See TracBrowser for help on using the repository browser.