COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/bits/edge_set_extender.h @ 559:c5fd2d996909

Last change on this file since 559:c5fd2d996909 was 559:c5fd2d996909, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Various doc improvements (#248)

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