COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/edge_set_extender.h @ 1996:5dc13b93f8b4

Last change on this file since 1996:5dc13b93f8b4 was 1996:5dc13b93f8b4, checked in by Balazs Dezso, 14 years ago

Some documentation arrangement modification

File size: 13.8 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<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 IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
223    public:
224      typedef EdgeSetExtender Graph;
225      typedef IterableMapExtender<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
268    ~EdgeSetExtender() {
269      edge_notifier.clear();
270    }
271
272  };
273
274
275  /// \ingroup graphbits
276  ///
277  /// \brief Extender for the UEdgeSets
278  template <typename Base>
279  class UEdgeSetExtender : public Base {
280
281  public:
282
283    typedef Base Parent;
284    typedef UEdgeSetExtender Graph;
285
286    typedef typename Parent::Node Node;
287    typedef typename Parent::Edge Edge;
288    typedef typename Parent::UEdge UEdge;
289
290
291    int maxId(Node) const {
292      return Parent::maxNodeId();
293    }
294
295    int maxId(Edge) const {
296      return Parent::maxEdgeId();
297    }
298
299    int maxId(UEdge) const {
300      return Parent::maxUEdgeId();
301    }
302
303    Node fromId(int id, Node) const {
304      return Parent::nodeFromId(id);
305    }
306
307    Edge fromId(int id, Edge) const {
308      return Parent::edgeFromId(id);
309    }
310
311    UEdge fromId(int id, UEdge) const {
312      return Parent::uEdgeFromId(id);
313    }
314
315    Node oppositeNode(const Node &n, const UEdge &e) const {
316      if( n == Parent::source(e))
317        return Parent::target(e);
318      else if( n == Parent::target(e))
319        return Parent::source(e);
320      else
321        return INVALID;
322    }
323
324    Edge oppositeEdge(const Edge &e) const {
325      return Parent::direct(e, !Parent::direction(e));
326    }
327
328    using Parent::direct;
329    Edge direct(const UEdge &ue, const Node &s) const {
330      return Parent::direct(ue, Parent::source(ue) == s);
331    }
332
333    typedef AlterationNotifier<Edge> EdgeNotifier;
334    typedef AlterationNotifier<UEdge> UEdgeNotifier;
335
336
337  protected:
338
339    mutable EdgeNotifier edge_notifier;
340    mutable UEdgeNotifier uedge_notifier;
341
342  public:
343
344    using Parent::getNotifier;
345   
346    EdgeNotifier& getNotifier(Edge) const {
347      return edge_notifier;
348    }
349
350    UEdgeNotifier& getNotifier(UEdge) const {
351      return uedge_notifier;
352    }
353
354
355    class NodeIt : public Node {
356      const Graph* graph;
357    public:
358
359      NodeIt() {}
360
361      NodeIt(Invalid i) : Node(i) { }
362
363      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
364        _graph.first(*static_cast<Node*>(this));
365      }
366
367      NodeIt(const Graph& _graph, const Node& node)
368        : Node(node), graph(&_graph) {}
369
370      NodeIt& operator++() {
371        graph->next(*this);
372        return *this;
373      }
374
375    };
376
377
378    class EdgeIt : public Edge {
379      const Graph* graph;
380    public:
381
382      EdgeIt() { }
383
384      EdgeIt(Invalid i) : Edge(i) { }
385
386      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
387        _graph.first(*static_cast<Edge*>(this));
388      }
389
390      EdgeIt(const Graph& _graph, const Edge& e) :
391        Edge(e), graph(&_graph) { }
392
393      EdgeIt& operator++() {
394        graph->next(*this);
395        return *this;
396      }
397
398    };
399
400
401    class OutEdgeIt : public Edge {
402      const Graph* graph;
403    public:
404
405      OutEdgeIt() { }
406
407      OutEdgeIt(Invalid i) : Edge(i) { }
408
409      OutEdgeIt(const Graph& _graph, const Node& node)
410        : graph(&_graph) {
411        _graph.firstOut(*this, node);
412      }
413
414      OutEdgeIt(const Graph& _graph, const Edge& edge)
415        : Edge(edge), graph(&_graph) {}
416
417      OutEdgeIt& operator++() {
418        graph->nextOut(*this);
419        return *this;
420      }
421
422    };
423
424
425    class InEdgeIt : public Edge {
426      const Graph* graph;
427    public:
428
429      InEdgeIt() { }
430
431      InEdgeIt(Invalid i) : Edge(i) { }
432
433      InEdgeIt(const Graph& _graph, const Node& node)
434        : graph(&_graph) {
435        _graph.firstIn(*this, node);
436      }
437
438      InEdgeIt(const Graph& _graph, const Edge& edge) :
439        Edge(edge), graph(&_graph) {}
440
441      InEdgeIt& operator++() {
442        graph->nextIn(*this);
443        return *this;
444      }
445
446    };
447
448
449    class UEdgeIt : public Parent::UEdge {
450      const Graph* graph;
451    public:
452
453      UEdgeIt() { }
454
455      UEdgeIt(Invalid i) : UEdge(i) { }
456
457      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
458        _graph.first(*static_cast<UEdge*>(this));
459      }
460
461      UEdgeIt(const Graph& _graph, const UEdge& e) :
462        UEdge(e), graph(&_graph) { }
463
464      UEdgeIt& operator++() {
465        graph->next(*this);
466        return *this;
467      }
468
469    };
470
471    class IncEdgeIt : public Parent::UEdge {
472      friend class UEdgeSetExtender;
473      const Graph* graph;
474      bool direction;
475    public:
476
477      IncEdgeIt() { }
478
479      IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
480
481      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
482        _graph.firstInc(*this, direction, n);
483      }
484
485      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
486        : graph(&_graph), UEdge(ue) {
487        direction = (_graph.source(ue) == n);
488      }
489
490      IncEdgeIt& operator++() {
491        graph->nextInc(*this, direction);
492        return *this;
493      }
494    };
495
496    /// \brief Base node of the iterator
497    ///
498    /// Returns the base node (ie. the source in this case) of the iterator
499    Node baseNode(const OutEdgeIt &e) const {
500      return Parent::source((Edge)e);
501    }
502    /// \brief Running node of the iterator
503    ///
504    /// Returns the running node (ie. the target in this case) of the
505    /// iterator
506    Node runningNode(const OutEdgeIt &e) const {
507      return Parent::target((Edge)e);
508    }
509
510    /// \brief Base node of the iterator
511    ///
512    /// Returns the base node (ie. the target in this case) of the iterator
513    Node baseNode(const InEdgeIt &e) const {
514      return Parent::target((Edge)e);
515    }
516    /// \brief Running node of the iterator
517    ///
518    /// Returns the running node (ie. the source in this case) of the
519    /// iterator
520    Node runningNode(const InEdgeIt &e) const {
521      return Parent::source((Edge)e);
522    }
523
524    /// Base node of the iterator
525    ///
526    /// Returns the base node of the iterator
527    Node baseNode(const IncEdgeIt &e) const {
528      return e.direction ? source(e) : target(e);
529    }
530    /// Running node of the iterator
531    ///
532    /// Returns the running node of the iterator
533    Node runningNode(const IncEdgeIt &e) const {
534      return e.direction ? target(e) : source(e);
535    }
536
537
538    template <typename _Value>
539    class EdgeMap
540      : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
541    public:
542      typedef UEdgeSetExtender Graph;
543      typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
544
545      EdgeMap(const Graph& _g)
546        : Parent(_g) {}
547      EdgeMap(const Graph& _g, const _Value& _v)
548        : Parent(_g, _v) {}
549
550      EdgeMap& operator=(const EdgeMap& cmap) {
551        return operator=<EdgeMap>(cmap);
552      }
553
554      template <typename CMap>
555      EdgeMap& operator=(const CMap& cmap) {
556        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
557        const typename Parent::Graph* graph = Parent::getGraph();
558        Edge it;
559        for (graph->first(it); it != INVALID; graph->next(it)) {
560          Parent::set(it, cmap[it]);
561        }
562        return *this;
563      }
564    };
565
566
567    template <typename _Value>
568    class UEdgeMap
569      : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
570    public:
571      typedef UEdgeSetExtender Graph;
572      typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
573
574      UEdgeMap(const Graph& _g)
575        : Parent(_g) {}
576      UEdgeMap(const Graph& _g, const _Value& _v)
577        : Parent(_g, _v) {}
578
579      UEdgeMap& operator=(const UEdgeMap& cmap) {
580        return operator=<UEdgeMap>(cmap);
581      }
582
583      template <typename CMap>
584      UEdgeMap& operator=(const CMap& cmap) {
585        checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
586        const typename Parent::Graph* graph = Parent::getGraph();
587        UEdge it;
588        for (graph->first(it); it != INVALID; graph->next(it)) {
589          Parent::set(it, cmap[it]);
590        }
591        return *this;
592      }
593    };
594
595
596    // Alteration extension
597
598    UEdge addEdge(const Node& from, const Node& to) {
599      UEdge uedge = Parent::addEdge(from, to);
600      getNotifier(UEdge()).add(uedge);
601      getNotifier(Edge()).add(Parent::direct(uedge, true));
602      getNotifier(Edge()).add(Parent::direct(uedge, false));
603      return uedge;
604    }
605   
606    void clear() {
607      getNotifier(Edge()).clear();
608      getNotifier(UEdge()).clear();
609      Parent::clear();
610    }
611
612    void erase(const UEdge& uedge) {
613      getNotifier(Edge()).erase(Parent::direct(uedge, true));
614      getNotifier(Edge()).erase(Parent::direct(uedge, false));
615      getNotifier(UEdge()).erase(uedge);
616      Parent::erase(uedge);
617    }
618
619
620    ~UEdgeSetExtender() {
621      getNotifier(Edge()).clear();
622      getNotifier(UEdge()).clear();
623    }
624   
625  };
626
627}
628
629#endif
Note: See TracBrowser for help on using the repository browser.