COIN-OR::LEMON - Graph Library

source: lemon/lemon/bits/graph_extender.h @ 209:765619b7cbb2

Last change on this file since 209:765619b7cbb2 was 209:765619b7cbb2, checked in by Alpar Juttner <alpar@…>, 16 years ago

Apply unify-sources.sh to the source tree

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