COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/edge_set_extender.h @ 2498:290e43cddc1a

Last change on this file since 2498:290e43cddc1a was 2498:290e43cddc1a, checked in by Balazs Dezso, 12 years ago

Bug fix in undirected graphs (adding loops)
Bug fix in undirected edgesets (alteration notifying)

Redesigned undirected edgesets (like the smart or ugraph)

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