COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/edge_set_extender.h @ 2028:d0e8a86a1ff2

Last change on this file since 2028:d0e8a86a1ff2 was 1999:2ff283124dfc, checked in by Balazs Dezso, 18 years ago

Clarifing alteration observing system
It is directly connected now to a container

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