COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/bits/edge_set_extender.h @ 535:6a17a722b50e

Last change on this file since 535:6a17a722b50e was 519:c786cd201266, checked in by Balazs Dezso <deba@…>, 15 years ago

Fix several missing includes (#232)

File size: 13.5 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    /// \brief Gives back the arc alteration notifier.
87    ///
88    /// Gives back the arc alteration notifier.
89    ArcNotifier& notifier(Arc) const {
90      return arc_notifier;
91    }
92
93    // Iterable extensions
94
95    class NodeIt : public Node {
96      const Digraph* digraph;
97    public:
98
99      NodeIt() {}
100
101      NodeIt(Invalid i) : Node(i) { }
102
103      explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
104        _graph.first(static_cast<Node&>(*this));
105      }
106
107      NodeIt(const Digraph& _graph, const Node& node)
108        : Node(node), digraph(&_graph) {}
109
110      NodeIt& operator++() {
111        digraph->next(*this);
112        return *this;
113      }
114
115    };
116
117
118    class ArcIt : public Arc {
119      const Digraph* digraph;
120    public:
121
122      ArcIt() { }
123
124      ArcIt(Invalid i) : Arc(i) { }
125
126      explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
127        _graph.first(static_cast<Arc&>(*this));
128      }
129
130      ArcIt(const Digraph& _graph, const Arc& e) :
131        Arc(e), digraph(&_graph) { }
132
133      ArcIt& operator++() {
134        digraph->next(*this);
135        return *this;
136      }
137
138    };
139
140
141    class OutArcIt : public Arc {
142      const Digraph* digraph;
143    public:
144
145      OutArcIt() { }
146
147      OutArcIt(Invalid i) : Arc(i) { }
148
149      OutArcIt(const Digraph& _graph, const Node& node)
150        : digraph(&_graph) {
151        _graph.firstOut(*this, node);
152      }
153
154      OutArcIt(const Digraph& _graph, const Arc& arc)
155        : Arc(arc), digraph(&_graph) {}
156
157      OutArcIt& operator++() {
158        digraph->nextOut(*this);
159        return *this;
160      }
161
162    };
163
164
165    class InArcIt : public Arc {
166      const Digraph* digraph;
167    public:
168
169      InArcIt() { }
170
171      InArcIt(Invalid i) : Arc(i) { }
172
173      InArcIt(const Digraph& _graph, const Node& node)
174        : digraph(&_graph) {
175        _graph.firstIn(*this, node);
176      }
177
178      InArcIt(const Digraph& _graph, const Arc& arc) :
179        Arc(arc), digraph(&_graph) {}
180
181      InArcIt& operator++() {
182        digraph->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 OutArcIt &e) const {
192      return Parent::source(static_cast<const Arc&>(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 OutArcIt &e) const {
199      return Parent::target(static_cast<const Arc&>(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 InArcIt &e) const {
206      return Parent::target(static_cast<const Arc&>(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 InArcIt &e) const {
213      return Parent::source(static_cast<const Arc&>(e));
214    }
215
216    using Parent::first;
217
218    // Mappable extension
219   
220    template <typename _Value>
221    class ArcMap
222      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
223    public:
224      typedef ArcSetExtender Digraph;
225      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
226
227      explicit ArcMap(const Digraph& _g)
228        : Parent(_g) {}
229      ArcMap(const Digraph& _g, const _Value& _v)
230        : Parent(_g, _v) {}
231
232      ArcMap& operator=(const ArcMap& cmap) {
233        return operator=<ArcMap>(cmap);
234      }
235
236      template <typename CMap>
237      ArcMap& operator=(const CMap& cmap) {
238        Parent::operator=(cmap);
239        return *this;
240      }
241
242    };
243
244
245    // Alteration extension
246
247    Arc addArc(const Node& from, const Node& to) {
248      Arc arc = Parent::addArc(from, to);
249      notifier(Arc()).add(arc);
250      return arc;
251    }
252   
253    void clear() {
254      notifier(Arc()).clear();
255      Parent::clear();
256    }
257
258    void erase(const Arc& arc) {
259      notifier(Arc()).erase(arc);
260      Parent::erase(arc);
261    }
262
263    ArcSetExtender() {
264      arc_notifier.setContainer(*this);
265    }
266
267    ~ArcSetExtender() {
268      arc_notifier.clear();
269    }
270
271  };
272
273
274  /// \ingroup digraphbits
275  ///
276  /// \brief Extender for the EdgeSets
277  template <typename Base>
278  class EdgeSetExtender : public Base {
279
280  public:
281
282    typedef Base Parent;
283    typedef EdgeSetExtender Digraph;
284
285    typedef typename Parent::Node Node;
286    typedef typename Parent::Arc Arc;
287    typedef typename Parent::Edge Edge;
288
289
290    int maxId(Node) const {
291      return Parent::maxNodeId();
292    }
293
294    int maxId(Arc) const {
295      return Parent::maxArcId();
296    }
297
298    int maxId(Edge) const {
299      return Parent::maxEdgeId();
300    }
301
302    Node fromId(int id, Node) const {
303      return Parent::nodeFromId(id);
304    }
305
306    Arc fromId(int id, Arc) const {
307      return Parent::arcFromId(id);
308    }
309
310    Edge fromId(int id, Edge) const {
311      return Parent::edgeFromId(id);
312    }
313
314    Node oppositeNode(const Node &n, const Edge &e) const {
315      if( n == Parent::u(e))
316        return Parent::v(e);
317      else if( n == Parent::v(e))
318        return Parent::u(e);
319      else
320        return INVALID;
321    }
322
323    Arc oppositeArc(const Arc &e) const {
324      return Parent::direct(e, !Parent::direction(e));
325    }
326
327    using Parent::direct;
328    Arc direct(const Edge &e, const Node &s) const {
329      return Parent::direct(e, Parent::u(e) == s);
330    }
331
332    typedef AlterationNotifier<EdgeSetExtender, Arc> ArcNotifier;
333    typedef AlterationNotifier<EdgeSetExtender, Edge> EdgeNotifier;
334
335
336  protected:
337
338    mutable ArcNotifier arc_notifier;
339    mutable EdgeNotifier edge_notifier;
340
341  public:
342
343    using Parent::notifier;
344   
345    ArcNotifier& notifier(Arc) const {
346      return arc_notifier;
347    }
348
349    EdgeNotifier& notifier(Edge) const {
350      return edge_notifier;
351    }
352
353
354    class NodeIt : public Node {
355      const Digraph* digraph;
356    public:
357
358      NodeIt() {}
359
360      NodeIt(Invalid i) : Node(i) { }
361
362      explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
363        _graph.first(static_cast<Node&>(*this));
364      }
365
366      NodeIt(const Digraph& _graph, const Node& node)
367        : Node(node), digraph(&_graph) {}
368
369      NodeIt& operator++() {
370        digraph->next(*this);
371        return *this;
372      }
373
374    };
375
376
377    class ArcIt : public Arc {
378      const Digraph* digraph;
379    public:
380
381      ArcIt() { }
382
383      ArcIt(Invalid i) : Arc(i) { }
384
385      explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
386        _graph.first(static_cast<Arc&>(*this));
387      }
388
389      ArcIt(const Digraph& _graph, const Arc& e) :
390        Arc(e), digraph(&_graph) { }
391
392      ArcIt& operator++() {
393        digraph->next(*this);
394        return *this;
395      }
396
397    };
398
399
400    class OutArcIt : public Arc {
401      const Digraph* digraph;
402    public:
403
404      OutArcIt() { }
405
406      OutArcIt(Invalid i) : Arc(i) { }
407
408      OutArcIt(const Digraph& _graph, const Node& node)
409        : digraph(&_graph) {
410        _graph.firstOut(*this, node);
411      }
412
413      OutArcIt(const Digraph& _graph, const Arc& arc)
414        : Arc(arc), digraph(&_graph) {}
415
416      OutArcIt& operator++() {
417        digraph->nextOut(*this);
418        return *this;
419      }
420
421    };
422
423
424    class InArcIt : public Arc {
425      const Digraph* digraph;
426    public:
427
428      InArcIt() { }
429
430      InArcIt(Invalid i) : Arc(i) { }
431
432      InArcIt(const Digraph& _graph, const Node& node)
433        : digraph(&_graph) {
434        _graph.firstIn(*this, node);
435      }
436
437      InArcIt(const Digraph& _graph, const Arc& arc) :
438        Arc(arc), digraph(&_graph) {}
439
440      InArcIt& operator++() {
441        digraph->nextIn(*this);
442        return *this;
443      }
444
445    };
446
447
448    class EdgeIt : public Parent::Edge {
449      const Digraph* digraph;
450    public:
451
452      EdgeIt() { }
453
454      EdgeIt(Invalid i) : Edge(i) { }
455
456      explicit EdgeIt(const Digraph& _graph) : digraph(&_graph) {
457        _graph.first(static_cast<Edge&>(*this));
458      }
459
460      EdgeIt(const Digraph& _graph, const Edge& e) :
461        Edge(e), digraph(&_graph) { }
462
463      EdgeIt& operator++() {
464        digraph->next(*this);
465        return *this;
466      }
467
468    };
469
470    class IncEdgeIt : public Parent::Edge {
471      friend class EdgeSetExtender;
472      const Digraph* digraph;
473      bool direction;
474    public:
475
476      IncEdgeIt() { }
477
478      IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
479
480      IncEdgeIt(const Digraph& _graph, const Node &n) : digraph(&_graph) {
481        _graph.firstInc(*this, direction, n);
482      }
483
484      IncEdgeIt(const Digraph& _graph, const Edge &ue, const Node &n)
485        : digraph(&_graph), Edge(ue) {
486        direction = (_graph.source(ue) == n);
487      }
488
489      IncEdgeIt& operator++() {
490        digraph->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 OutArcIt &e) const {
499      return Parent::source(static_cast<const Arc&>(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 OutArcIt &e) const {
506      return Parent::target(static_cast<const Arc&>(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 InArcIt &e) const {
513      return Parent::target(static_cast<const Arc&>(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 InArcIt &e) const {
520      return Parent::source(static_cast<const Arc&>(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 ? u(e) : v(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 ? v(e) : u(e);
534    }
535
536
537    template <typename _Value>
538    class ArcMap
539      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
540    public:
541      typedef EdgeSetExtender Digraph;
542      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
543
544      ArcMap(const Digraph& _g)
545        : Parent(_g) {}
546      ArcMap(const Digraph& _g, const _Value& _v)
547        : Parent(_g, _v) {}
548
549      ArcMap& operator=(const ArcMap& cmap) {
550        return operator=<ArcMap>(cmap);
551      }
552
553      template <typename CMap>
554      ArcMap& operator=(const CMap& cmap) {
555        Parent::operator=(cmap);
556        return *this;
557      }
558
559    };
560
561
562    template <typename _Value>
563    class EdgeMap
564      : public MapExtender<DefaultMap<Digraph, Edge, _Value> > {
565    public:
566      typedef EdgeSetExtender Digraph;
567      typedef MapExtender<DefaultMap<Digraph, Edge, _Value> > Parent;
568
569      EdgeMap(const Digraph& _g)
570        : Parent(_g) {}
571
572      EdgeMap(const Digraph& _g, const _Value& _v)
573        : Parent(_g, _v) {}
574
575      EdgeMap& operator=(const EdgeMap& cmap) {
576        return operator=<EdgeMap>(cmap);
577      }
578
579      template <typename CMap>
580      EdgeMap& operator=(const CMap& cmap) {
581        Parent::operator=(cmap);
582        return *this;
583      }
584
585    };
586
587
588    // Alteration extension
589
590    Edge addEdge(const Node& from, const Node& to) {
591      Edge edge = Parent::addEdge(from, to);
592      notifier(Edge()).add(edge);
593      std::vector<Arc> arcs;
594      arcs.push_back(Parent::direct(edge, true));
595      arcs.push_back(Parent::direct(edge, false));
596      notifier(Arc()).add(arcs);
597      return edge;
598    }
599   
600    void clear() {
601      notifier(Arc()).clear();
602      notifier(Edge()).clear();
603      Parent::clear();
604    }
605
606    void erase(const Edge& edge) {
607      std::vector<Arc> arcs;
608      arcs.push_back(Parent::direct(edge, true));
609      arcs.push_back(Parent::direct(edge, false));
610      notifier(Arc()).erase(arcs);
611      notifier(Edge()).erase(edge);
612      Parent::erase(edge);
613    }
614
615
616    EdgeSetExtender() {
617      arc_notifier.setContainer(*this);
618      edge_notifier.setContainer(*this);
619    }
620
621    ~EdgeSetExtender() {
622      edge_notifier.clear();
623      arc_notifier.clear();
624    }
625   
626  };
627
628}
629
630#endif
Note: See TracBrowser for help on using the repository browser.