COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/edge_set_extender.h @ 2553:bfced05fa852

Last change on this file since 2553:bfced05fa852 was 2553:bfced05fa852, checked in by Alpar Juttner, 12 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

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-2008
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.