COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/edge_set_extender.h @ 1993:2115143eceea

Last change on this file since 1993:2115143eceea was 1991:d7442141d9ef, checked in by Balazs Dezso, 18 years ago

The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor?, where
we have to proxy the signals from the graph.

The SubBidirGraphAdaptor? is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor?<UndirGraphAdaptor?<Graph>>.

The ResGraphAdaptor? is based on this composition.

File size: 13.4 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19
20namespace lemon {
21
22  template <typename Base>
23  class EdgeSetExtender : public Base {
24  public:
25
26    typedef Base Parent;
27    typedef EdgeSetExtender Graph;
28
29    // Base extensions
30
31    typedef typename Parent::Node Node;
32    typedef typename Parent::Edge Edge;
33
34    int maxId(Node) const {
35      return Parent::maxNodeId();
36    }
37
38    int maxId(Edge) const {
39      return Parent::maxEdgeId();
40    }
41
42    Node fromId(int id, Node) const {
43      return Parent::nodeFromId(id);
44    }
45
46    Edge fromId(int id, Edge) const {
47      return Parent::edgeFromId(id);
48    }
49
50    Node oppositeNode(const Node &n, const Edge &e) const {
51      if (n == Parent::source(e))
52        return Parent::target(e);
53      else if(n==Parent::target(e))
54        return Parent::source(e);
55      else
56        return INVALID;
57    }
58
59
60    // Alteration notifier extensions
61
62    /// The edge observer registry.
63    typedef AlterationNotifier<Edge> EdgeNotifier;
64
65  protected:
66
67    mutable EdgeNotifier edge_notifier;
68
69  public:
70
71    using Parent::getNotifier;
72
73    /// \brief Gives back the edge alteration notifier.
74    ///
75    /// Gives back the edge alteration notifier.
76    EdgeNotifier& getNotifier(Edge) const {
77      return edge_notifier;
78    }
79
80    // Iterable extensions
81
82    class NodeIt : public Node {
83      const Graph* graph;
84    public:
85
86      NodeIt() {}
87
88      NodeIt(Invalid i) : Node(i) { }
89
90      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
91        _graph.first(*static_cast<Node*>(this));
92      }
93
94      NodeIt(const Graph& _graph, const Node& node)
95        : Node(node), graph(&_graph) {}
96
97      NodeIt& operator++() {
98        graph->next(*this);
99        return *this;
100      }
101
102    };
103
104
105    class EdgeIt : public Edge {
106      const Graph* graph;
107    public:
108
109      EdgeIt() { }
110
111      EdgeIt(Invalid i) : Edge(i) { }
112
113      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
114        _graph.first(*static_cast<Edge*>(this));
115      }
116
117      EdgeIt(const Graph& _graph, const Edge& e) :
118        Edge(e), graph(&_graph) { }
119
120      EdgeIt& operator++() {
121        graph->next(*this);
122        return *this;
123      }
124
125    };
126
127
128    class OutEdgeIt : public Edge {
129      const Graph* graph;
130    public:
131
132      OutEdgeIt() { }
133
134      OutEdgeIt(Invalid i) : Edge(i) { }
135
136      OutEdgeIt(const Graph& _graph, const Node& node)
137        : graph(&_graph) {
138        _graph.firstOut(*this, node);
139      }
140
141      OutEdgeIt(const Graph& _graph, const Edge& edge)
142        : Edge(edge), graph(&_graph) {}
143
144      OutEdgeIt& operator++() {
145        graph->nextOut(*this);
146        return *this;
147      }
148
149    };
150
151
152    class InEdgeIt : public Edge {
153      const Graph* graph;
154    public:
155
156      InEdgeIt() { }
157
158      InEdgeIt(Invalid i) : Edge(i) { }
159
160      InEdgeIt(const Graph& _graph, const Node& node)
161        : graph(&_graph) {
162        _graph.firstIn(*this, node);
163      }
164
165      InEdgeIt(const Graph& _graph, const Edge& edge) :
166        Edge(edge), graph(&_graph) {}
167
168      InEdgeIt& operator++() {
169        graph->nextIn(*this);
170        return *this;
171      }
172
173    };
174
175    /// \brief Base node of the iterator
176    ///
177    /// Returns the base node (ie. the source in this case) of the iterator
178    Node baseNode(const OutEdgeIt &e) const {
179      return Parent::source((Edge)e);
180    }
181    /// \brief Running node of the iterator
182    ///
183    /// Returns the running node (ie. the target in this case) of the
184    /// iterator
185    Node runningNode(const OutEdgeIt &e) const {
186      return Parent::target((Edge)e);
187    }
188
189    /// \brief Base node of the iterator
190    ///
191    /// Returns the base node (ie. the target in this case) of the iterator
192    Node baseNode(const InEdgeIt &e) const {
193      return Parent::target((Edge)e);
194    }
195    /// \brief Running node of the iterator
196    ///
197    /// Returns the running node (ie. the source in this case) of the
198    /// iterator
199    Node runningNode(const InEdgeIt &e) const {
200      return Parent::source((Edge)e);
201    }
202
203    using Parent::first;
204
205    // Mappable extension
206   
207    template <typename _Value>
208    class EdgeMap
209      : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
210    public:
211      typedef EdgeSetExtender Graph;
212      typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
213
214      EdgeMap(const Graph& _g)
215        : Parent(_g) {}
216      EdgeMap(const Graph& _g, const _Value& _v)
217        : Parent(_g, _v) {}
218
219      EdgeMap& operator=(const EdgeMap& cmap) {
220        return operator=<EdgeMap>(cmap);
221      }
222
223      template <typename CMap>
224      EdgeMap& operator=(const CMap& cmap) {
225        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
226        const typename Parent::Graph* graph = Parent::getGraph();
227        Edge it;
228        for (graph->first(it); it != INVALID; graph->next(it)) {
229          Parent::set(it, cmap[it]);
230        }
231        return *this;
232      }
233    };
234
235
236    // Alteration extension
237
238    Edge addEdge(const Node& from, const Node& to) {
239      Edge edge = Parent::addEdge(from, to);
240      getNotifier(Edge()).add(edge);
241      return edge;
242    }
243   
244    void clear() {
245      getNotifier(Edge()).clear();
246      Parent::clear();
247    }
248
249    void erase(const Edge& edge) {
250      getNotifier(Edge()).erase(edge);
251      Parent::erase(edge);
252    }
253
254
255    ~EdgeSetExtender() {
256      edge_notifier.clear();
257    }
258
259  };
260
261
262  template <typename Base>
263  class UEdgeSetExtender : public Base {
264
265  public:
266
267    typedef Base Parent;
268    typedef UEdgeSetExtender Graph;
269
270    typedef typename Parent::Node Node;
271    typedef typename Parent::Edge Edge;
272    typedef typename Parent::UEdge UEdge;
273
274
275    int maxId(Node) const {
276      return Parent::maxNodeId();
277    }
278
279    int maxId(Edge) const {
280      return Parent::maxEdgeId();
281    }
282
283    int maxId(UEdge) const {
284      return Parent::maxUEdgeId();
285    }
286
287    Node fromId(int id, Node) const {
288      return Parent::nodeFromId(id);
289    }
290
291    Edge fromId(int id, Edge) const {
292      return Parent::edgeFromId(id);
293    }
294
295    UEdge fromId(int id, UEdge) const {
296      return Parent::uEdgeFromId(id);
297    }
298
299    Node oppositeNode(const Node &n, const UEdge &e) const {
300      if( n == Parent::source(e))
301        return Parent::target(e);
302      else if( n == Parent::target(e))
303        return Parent::source(e);
304      else
305        return INVALID;
306    }
307
308    Edge oppositeEdge(const Edge &e) const {
309      return Parent::direct(e, !Parent::direction(e));
310    }
311
312    using Parent::direct;
313    Edge direct(const UEdge &ue, const Node &s) const {
314      return Parent::direct(ue, Parent::source(ue) == s);
315    }
316
317    typedef AlterationNotifier<Edge> EdgeNotifier;
318    typedef AlterationNotifier<UEdge> UEdgeNotifier;
319
320
321  protected:
322
323    mutable EdgeNotifier edge_notifier;
324    mutable UEdgeNotifier uedge_notifier;
325
326  public:
327
328    using Parent::getNotifier;
329   
330    EdgeNotifier& getNotifier(Edge) const {
331      return edge_notifier;
332    }
333
334    UEdgeNotifier& getNotifier(UEdge) const {
335      return uedge_notifier;
336    }
337
338
339    class NodeIt : public Node {
340      const Graph* graph;
341    public:
342
343      NodeIt() {}
344
345      NodeIt(Invalid i) : Node(i) { }
346
347      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
348        _graph.first(*static_cast<Node*>(this));
349      }
350
351      NodeIt(const Graph& _graph, const Node& node)
352        : Node(node), graph(&_graph) {}
353
354      NodeIt& operator++() {
355        graph->next(*this);
356        return *this;
357      }
358
359    };
360
361
362    class EdgeIt : public Edge {
363      const Graph* graph;
364    public:
365
366      EdgeIt() { }
367
368      EdgeIt(Invalid i) : Edge(i) { }
369
370      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
371        _graph.first(*static_cast<Edge*>(this));
372      }
373
374      EdgeIt(const Graph& _graph, const Edge& e) :
375        Edge(e), graph(&_graph) { }
376
377      EdgeIt& operator++() {
378        graph->next(*this);
379        return *this;
380      }
381
382    };
383
384
385    class OutEdgeIt : public Edge {
386      const Graph* graph;
387    public:
388
389      OutEdgeIt() { }
390
391      OutEdgeIt(Invalid i) : Edge(i) { }
392
393      OutEdgeIt(const Graph& _graph, const Node& node)
394        : graph(&_graph) {
395        _graph.firstOut(*this, node);
396      }
397
398      OutEdgeIt(const Graph& _graph, const Edge& edge)
399        : Edge(edge), graph(&_graph) {}
400
401      OutEdgeIt& operator++() {
402        graph->nextOut(*this);
403        return *this;
404      }
405
406    };
407
408
409    class InEdgeIt : public Edge {
410      const Graph* graph;
411    public:
412
413      InEdgeIt() { }
414
415      InEdgeIt(Invalid i) : Edge(i) { }
416
417      InEdgeIt(const Graph& _graph, const Node& node)
418        : graph(&_graph) {
419        _graph.firstIn(*this, node);
420      }
421
422      InEdgeIt(const Graph& _graph, const Edge& edge) :
423        Edge(edge), graph(&_graph) {}
424
425      InEdgeIt& operator++() {
426        graph->nextIn(*this);
427        return *this;
428      }
429
430    };
431
432
433    class UEdgeIt : public Parent::UEdge {
434      const Graph* graph;
435    public:
436
437      UEdgeIt() { }
438
439      UEdgeIt(Invalid i) : UEdge(i) { }
440
441      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
442        _graph.first(*static_cast<UEdge*>(this));
443      }
444
445      UEdgeIt(const Graph& _graph, const UEdge& e) :
446        UEdge(e), graph(&_graph) { }
447
448      UEdgeIt& operator++() {
449        graph->next(*this);
450        return *this;
451      }
452
453    };
454
455    class IncEdgeIt : public Parent::UEdge {
456      friend class UEdgeSetExtender;
457      const Graph* graph;
458      bool direction;
459    public:
460
461      IncEdgeIt() { }
462
463      IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
464
465      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
466        _graph.firstInc(*this, direction, n);
467      }
468
469      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
470        : graph(&_graph), UEdge(ue) {
471        direction = (_graph.source(ue) == n);
472      }
473
474      IncEdgeIt& operator++() {
475        graph->nextInc(*this, direction);
476        return *this;
477      }
478    };
479
480    /// \brief Base node of the iterator
481    ///
482    /// Returns the base node (ie. the source in this case) of the iterator
483    Node baseNode(const OutEdgeIt &e) const {
484      return Parent::source((Edge)e);
485    }
486    /// \brief Running node of the iterator
487    ///
488    /// Returns the running node (ie. the target in this case) of the
489    /// iterator
490    Node runningNode(const OutEdgeIt &e) const {
491      return Parent::target((Edge)e);
492    }
493
494    /// \brief Base node of the iterator
495    ///
496    /// Returns the base node (ie. the target in this case) of the iterator
497    Node baseNode(const InEdgeIt &e) const {
498      return Parent::target((Edge)e);
499    }
500    /// \brief Running node of the iterator
501    ///
502    /// Returns the running node (ie. the source in this case) of the
503    /// iterator
504    Node runningNode(const InEdgeIt &e) const {
505      return Parent::source((Edge)e);
506    }
507
508    /// Base node of the iterator
509    ///
510    /// Returns the base node of the iterator
511    Node baseNode(const IncEdgeIt &e) const {
512      return e.direction ? source(e) : target(e);
513    }
514    /// Running node of the iterator
515    ///
516    /// Returns the running node of the iterator
517    Node runningNode(const IncEdgeIt &e) const {
518      return e.direction ? target(e) : source(e);
519    }
520
521
522    template <typename _Value>
523    class EdgeMap
524      : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
525    public:
526      typedef UEdgeSetExtender Graph;
527      typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
528
529      EdgeMap(const Graph& _g)
530        : Parent(_g) {}
531      EdgeMap(const Graph& _g, const _Value& _v)
532        : Parent(_g, _v) {}
533
534      EdgeMap& operator=(const EdgeMap& cmap) {
535        return operator=<EdgeMap>(cmap);
536      }
537
538      template <typename CMap>
539      EdgeMap& operator=(const CMap& cmap) {
540        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
541        const typename Parent::Graph* graph = Parent::getGraph();
542        Edge it;
543        for (graph->first(it); it != INVALID; graph->next(it)) {
544          Parent::set(it, cmap[it]);
545        }
546        return *this;
547      }
548    };
549
550
551    template <typename _Value>
552    class UEdgeMap
553      : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
554    public:
555      typedef UEdgeSetExtender Graph;
556      typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
557
558      UEdgeMap(const Graph& _g)
559        : Parent(_g) {}
560      UEdgeMap(const Graph& _g, const _Value& _v)
561        : Parent(_g, _v) {}
562
563      UEdgeMap& operator=(const UEdgeMap& cmap) {
564        return operator=<UEdgeMap>(cmap);
565      }
566
567      template <typename CMap>
568      UEdgeMap& operator=(const CMap& cmap) {
569        checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
570        const typename Parent::Graph* graph = Parent::getGraph();
571        UEdge it;
572        for (graph->first(it); it != INVALID; graph->next(it)) {
573          Parent::set(it, cmap[it]);
574        }
575        return *this;
576      }
577    };
578
579
580    // Alteration extension
581
582    UEdge addEdge(const Node& from, const Node& to) {
583      UEdge uedge = Parent::addEdge(from, to);
584      getNotifier(UEdge()).add(uedge);
585      getNotifier(Edge()).add(Parent::direct(uedge, true));
586      getNotifier(Edge()).add(Parent::direct(uedge, false));
587      return uedge;
588    }
589   
590    void clear() {
591      getNotifier(Edge()).clear();
592      getNotifier(UEdge()).clear();
593      Parent::clear();
594    }
595
596    void erase(const UEdge& uedge) {
597      getNotifier(Edge()).erase(Parent::direct(uedge, true));
598      getNotifier(Edge()).erase(Parent::direct(uedge, false));
599      getNotifier(UEdge()).erase(uedge);
600      Parent::erase(uedge);
601    }
602
603
604    ~UEdgeSetExtender() {
605      getNotifier(Edge()).clear();
606      getNotifier(UEdge()).clear();
607    }
608   
609  };
610}
Note: See TracBrowser for help on using the repository browser.