COIN-OR::LEMON - Graph Library

source: lemon/lemon/bits/edge_set_extender.h @ 1337:4add05447ca0

Last change on this file since 1337:4add05447ca0 was 1337:4add05447ca0, checked in by Alpar Juttner <alpar@…>, 5 years ago

Tests and bugfixes for the STL style iterators (#325)

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