COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/graph_extender.h @ 1991:d7442141d9ef

Last change on this file since 1991:d7442141d9ef was 1991:d7442141d9ef, checked in by Balazs Dezso, 14 years ago

The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor?, where
we have to proxy the signals from the graph.

The SubBidirGraphAdaptor? is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor?<UndirGraphAdaptor?<Graph>>.

The ResGraphAdaptor? is based on this composition.

File size: 42.5 KB
RevLine 
[1791]1/* -*- C++ -*-
2 *
[1956]3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
[1791]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_GRAPH_EXTENDER_H
20#define LEMON_GRAPH_EXTENDER_H
21
22#include <lemon/invalid.h>
[1820]23#include <lemon/error.h>
[1791]24
[1979]25#include <lemon/bits/default_map.h>
26
[1791]27namespace lemon {
28
[1979]29  template <typename Base>
30  class GraphExtender : public Base {
[1791]31  public:
32
[1979]33    typedef Base Parent;
[1791]34    typedef GraphExtender Graph;
35
[1979]36    // Base extensions
37
[1791]38    typedef typename Parent::Node Node;
39    typedef typename Parent::Edge Edge;
40
41    int maxId(Node) const {
42      return Parent::maxNodeId();
43    }
44
45    int maxId(Edge) const {
46      return Parent::maxEdgeId();
47    }
48
49    Node fromId(int id, Node) const {
50      return Parent::nodeFromId(id);
51    }
52
53    Edge fromId(int id, Edge) const {
54      return Parent::edgeFromId(id);
55    }
56
57    Node oppositeNode(const Node &n, const Edge &e) const {
58      if (n == Parent::source(e))
59        return Parent::target(e);
60      else if(n==Parent::target(e))
61        return Parent::source(e);
62      else
63        return INVALID;
64    }
65
[1979]66    // Alterable extension
[1791]67
[1979]68    typedef AlterationNotifier<Node> NodeNotifier;
69    typedef AlterationNotifier<Edge> EdgeNotifier;
70
71
72  protected:
73
74    mutable NodeNotifier node_notifier;
75    mutable EdgeNotifier edge_notifier;
[1791]76
77  public:
78
[1979]79    NodeNotifier& getNotifier(Node) const {
80      return node_notifier;
81    }
82   
83    EdgeNotifier& getNotifier(Edge) const {
84      return edge_notifier;
85    }
86
87    class NodeIt : public Node {
88      const Graph* graph;
89    public:
90
91      NodeIt() {}
92
93      NodeIt(Invalid i) : Node(i) { }
94
95      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
96        _graph.first(*static_cast<Node*>(this));
97      }
98
99      NodeIt(const Graph& _graph, const Node& node)
100        : Node(node), graph(&_graph) {}
101
102      NodeIt& operator++() {
103        graph->next(*this);
104        return *this;
105      }
106
107    };
108
109
110    class EdgeIt : public Edge {
111      const Graph* graph;
112    public:
113
114      EdgeIt() { }
115
116      EdgeIt(Invalid i) : Edge(i) { }
117
118      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
119        _graph.first(*static_cast<Edge*>(this));
120      }
121
122      EdgeIt(const Graph& _graph, const Edge& e) :
123        Edge(e), graph(&_graph) { }
124
125      EdgeIt& operator++() {
126        graph->next(*this);
127        return *this;
128      }
129
130    };
131
132
133    class OutEdgeIt : public Edge {
134      const Graph* graph;
135    public:
136
137      OutEdgeIt() { }
138
139      OutEdgeIt(Invalid i) : Edge(i) { }
140
141      OutEdgeIt(const Graph& _graph, const Node& node)
142        : graph(&_graph) {
143        _graph.firstOut(*this, node);
144      }
145
146      OutEdgeIt(const Graph& _graph, const Edge& edge)
147        : Edge(edge), graph(&_graph) {}
148
149      OutEdgeIt& operator++() {
150        graph->nextOut(*this);
151        return *this;
152      }
153
154    };
155
156
157    class InEdgeIt : public Edge {
158      const Graph* graph;
159    public:
160
161      InEdgeIt() { }
162
163      InEdgeIt(Invalid i) : Edge(i) { }
164
165      InEdgeIt(const Graph& _graph, const Node& node)
166        : graph(&_graph) {
167        _graph.firstIn(*this, node);
168      }
169
170      InEdgeIt(const Graph& _graph, const Edge& edge) :
171        Edge(edge), graph(&_graph) {}
172
173      InEdgeIt& operator++() {
174        graph->nextIn(*this);
175        return *this;
176      }
177
178    };
179
180    /// \brief Base node of the iterator
181    ///
182    /// Returns the base node (ie. the source in this case) of the iterator
183    Node baseNode(const OutEdgeIt &e) const {
184      return Parent::source(e);
185    }
186    /// \brief Running node of the iterator
187    ///
188    /// Returns the running node (ie. the target in this case) of the
189    /// iterator
190    Node runningNode(const OutEdgeIt &e) const {
191      return Parent::target(e);
192    }
193
194    /// \brief Base node of the iterator
195    ///
196    /// Returns the base node (ie. the target in this case) of the iterator
197    Node baseNode(const InEdgeIt &e) const {
198      return Parent::target(e);
199    }
200    /// \brief Running node of the iterator
201    ///
202    /// Returns the running node (ie. the source in this case) of the
203    /// iterator
204    Node runningNode(const InEdgeIt &e) const {
205      return Parent::source(e);
206    }
207
208   
209    template <typename _Value>
210    class NodeMap
211      : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > {
212    public:
213      typedef GraphExtender Graph;
214      typedef IterableMapExtender<DefaultMap<Graph, Node, _Value> > Parent;
215
216      NodeMap(const Graph& _g)
217        : Parent(_g) {}
218      NodeMap(const Graph& _g, const _Value& _v)
219        : Parent(_g, _v) {}
220
221      NodeMap& operator=(const NodeMap& cmap) {
222        return operator=<NodeMap>(cmap);
223      }
224
225
226      /// \brief Template assign operator.
227      ///
228      /// The given parameter should be conform to the ReadMap
229      /// concecpt and could be indiced by the current item set of
230      /// the NodeMap. In this case the value for each item
231      /// is assigned by the value of the given ReadMap.
232      template <typename CMap>
233      NodeMap& operator=(const CMap& cmap) {
234        checkConcept<concept::ReadMap<Node, _Value>, CMap>();
235        const typename Parent::Graph* graph = Parent::getGraph();
236        Node it;
237        for (graph->first(it); it != INVALID; graph->next(it)) {
238          Parent::set(it, cmap[it]);
239        }
240        return *this;
241      }
242
243    };
244
245    template <typename _Value>
246    class EdgeMap
247      : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
248    public:
249      typedef GraphExtender Graph;
250      typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
251
252      EdgeMap(const Graph& _g)
253        : Parent(_g) {}
254      EdgeMap(const Graph& _g, const _Value& _v)
255        : Parent(_g, _v) {}
256
257      EdgeMap& operator=(const EdgeMap& cmap) {
258        return operator=<EdgeMap>(cmap);
259      }
260
261      template <typename CMap>
262      EdgeMap& operator=(const CMap& cmap) {
263        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
264        const typename Parent::Graph* graph = Parent::getGraph();
265        Edge it;
266        for (graph->first(it); it != INVALID; graph->next(it)) {
267          Parent::set(it, cmap[it]);
268        }
269        return *this;
270      }
271    };
272
273
274    Node addNode() {
275      Node node = Parent::addNode();
276      getNotifier(Node()).add(node);
277      return node;
278    }
279   
280    Edge addEdge(const Node& from, const Node& to) {
281      Edge edge = Parent::addEdge(from, to);
282      getNotifier(Edge()).add(edge);
283      return edge;
284    }
285
286    void clear() {
287      getNotifier(Edge()).clear();
288      getNotifier(Node()).clear();
289      Parent::clear();
290    }
291
292
293    void erase(const Node& node) {
294      Edge edge;
295      Parent::firstOut(edge, node);
296      while (edge != INVALID ) {
297        erase(edge);
298        Parent::firstOut(edge, node);
299      }
300
301      Parent::firstIn(edge, node);
302      while (edge != INVALID ) {
303        erase(edge);
304        Parent::firstIn(edge, node);
305      }
306
307      getNotifier(Node()).erase(node);
308      Parent::erase(node);
309    }
310   
311    void erase(const Edge& edge) {
312      getNotifier(Edge()).erase(edge);
313      Parent::erase(edge);
314    }
315
316
317    ~GraphExtender() {
318      getNotifier(Edge()).clear();
319      getNotifier(Node()).clear();
320    }
321  };
322
323  template <typename Base>
324  class UGraphBaseExtender : public Base {
325
326  public:
327
328    typedef Base Parent;
[1909]329    typedef typename Parent::Edge UEdge;
[1791]330    typedef typename Parent::Node Node;
331
[1979]332    typedef True UndirectedTag;
333
[1909]334    class Edge : public UEdge {
[1979]335      friend class UGraphBaseExtender;
[1791]336
337    protected:
338      bool forward;
339
[1909]340      Edge(const UEdge &ue, bool _forward) :
341        UEdge(ue), forward(_forward) {}
[1791]342
343    public:
344      Edge() {}
345
346      /// Invalid edge constructor
[1909]347      Edge(Invalid i) : UEdge(i), forward(true) {}
[1791]348
349      bool operator==(const Edge &that) const {
[1909]350        return forward==that.forward && UEdge(*this)==UEdge(that);
[1791]351      }
352      bool operator!=(const Edge &that) const {
[1909]353        return forward!=that.forward || UEdge(*this)!=UEdge(that);
[1791]354      }
355      bool operator<(const Edge &that) const {
356        return forward<that.forward ||
[1909]357          (!(that.forward<forward) && UEdge(*this)<UEdge(that));
[1791]358      }
359    };
360
361
362
363    using Parent::source;
364
365    /// Source of the given Edge.
366    Node source(const Edge &e) const {
367      return e.forward ? Parent::source(e) : Parent::target(e);
368    }
369
370    using Parent::target;
371
372    /// Target of the given Edge.
373    Node target(const Edge &e) const {
374      return e.forward ? Parent::target(e) : Parent::source(e);
375    }
376
377    /// \brief Directed edge from an undirected edge.
378    ///
[1909]379    /// Returns a directed edge corresponding to the specified UEdge.
[1791]380    /// If the given bool is true the given undirected edge and the
381    /// returned edge have the same source node.
[1981]382    static Edge direct(const UEdge &ue, bool d) {
[1791]383      return Edge(ue, d);
384    }
385
386    /// Returns whether the given directed edge is same orientation as the
387    /// corresponding undirected edge.
388    ///
389    /// \todo reference to the corresponding point of the undirected graph
390    /// concept. "What does the direction of an undirected edge mean?"
[1981]391    static bool direction(const Edge &e) { return e.forward; }
[1791]392
393
394    using Parent::first;
[1979]395    using Parent::next;
396
[1791]397    void first(Edge &e) const {
398      Parent::first(e);
399      e.forward=true;
400    }
401
402    void next(Edge &e) const {
403      if( e.forward ) {
404        e.forward = false;
405      }
406      else {
407        Parent::next(e);
408        e.forward = true;
409      }
410    }
411
412    void firstOut(Edge &e, const Node &n) const {
413      Parent::firstIn(e,n);
[1909]414      if( UEdge(e) != INVALID ) {
[1791]415        e.forward = false;
416      }
417      else {
418        Parent::firstOut(e,n);
419        e.forward = true;
420      }
421    }
422    void nextOut(Edge &e) const {
423      if( ! e.forward ) {
424        Node n = Parent::target(e);
425        Parent::nextIn(e);
[1909]426        if( UEdge(e) == INVALID ) {
[1791]427          Parent::firstOut(e, n);
428          e.forward = true;
429        }
430      }
431      else {
432        Parent::nextOut(e);
433      }
434    }
435
436    void firstIn(Edge &e, const Node &n) const {
437      Parent::firstOut(e,n);
[1909]438      if( UEdge(e) != INVALID ) {
[1791]439        e.forward = false;
440      }
441      else {
442        Parent::firstIn(e,n);
443        e.forward = true;
444      }
445    }
446    void nextIn(Edge &e) const {
447      if( ! e.forward ) {
448        Node n = Parent::source(e);
449        Parent::nextOut(e);
[1909]450        if( UEdge(e) == INVALID ) {
[1791]451          Parent::firstIn(e, n);
452          e.forward = true;
453        }
454      }
455      else {
456        Parent::nextIn(e);
457      }
458    }
459
[1909]460    void firstInc(UEdge &e, bool &d, const Node &n) const {
[1791]461      d = true;
462      Parent::firstOut(e, n);
463      if (e != INVALID) return;
464      d = false;
465      Parent::firstIn(e, n);
466    }
[1979]467
[1909]468    void nextInc(UEdge &e, bool &d) const {
[1791]469      if (d) {
470        Node s = Parent::source(e);
471        Parent::nextOut(e);
472        if (e != INVALID) return;
473        d = false;
474        Parent::firstIn(e, s);
475      } else {
476        Parent::nextIn(e);
477      }
478    }
479
[1979]480    Node nodeFromId(int id) const {
481      return Parent::nodeFromId(id);
482    }
[1791]483
[1979]484    Edge edgeFromId(int id) const {
485      return direct(Parent::edgeFromId(id >> 1), bool(id & 1));
486    }
[1791]487
[1979]488    UEdge uEdgeFromId(int id) const {
489      return Parent::edgeFromId(id >> 1);
490    }
[1791]491
492    int id(const Node &n) const {
493      return Parent::id(n);
494    }
495
[1909]496    int id(const UEdge &e) const {
[1791]497      return Parent::id(e);
498    }
499
500    int id(const Edge &e) const {
501      return 2 * Parent::id(e) + int(e.forward);
502    }
503
504    int maxNodeId() const {
505      return Parent::maxNodeId();
506    }
507
508    int maxEdgeId() const {
509      return 2 * Parent::maxEdgeId() + 1;
510    }
511
[1909]512    int maxUEdgeId() const {
[1791]513      return Parent::maxEdgeId();
514    }
515
516
517    int edgeNum() const {
518      return 2 * Parent::edgeNum();
519    }
520
[1909]521    int uEdgeNum() const {
[1791]522      return Parent::edgeNum();
523    }
524
525    Edge findEdge(Node source, Node target, Edge prev) const {
526      if (prev == INVALID) {
[1909]527        UEdge edge = Parent::findEdge(source, target);
[1791]528        if (edge != INVALID) return direct(edge, true);
529        edge = Parent::findEdge(target, source);
530        if (edge != INVALID) return direct(edge, false);
531      } else if (direction(prev)) {
[1909]532        UEdge edge = Parent::findEdge(source, target, prev);
[1791]533        if (edge != INVALID) return direct(edge, true);
534        edge = Parent::findEdge(target, source);
535        if (edge != INVALID) return direct(edge, false);       
536      } else {
[1909]537        UEdge edge = Parent::findEdge(target, source, prev);
[1791]538        if (edge != INVALID) return direct(edge, false);             
539      }
540      return INVALID;
541    }
542
[1909]543    UEdge findUEdge(Node source, Node target, UEdge prev) const {
[1791]544      if (prev == INVALID) {
[1909]545        UEdge edge = Parent::findEdge(source, target);
[1791]546        if (edge != INVALID) return edge;
547        edge = Parent::findEdge(target, source);
548        if (edge != INVALID) return edge;
549      } else if (Parent::source(prev) == source) {
[1909]550        UEdge edge = Parent::findEdge(source, target, prev);
[1791]551        if (edge != INVALID) return edge;
552        edge = Parent::findEdge(target, source);
553        if (edge != INVALID) return edge;       
554      } else {
[1909]555        UEdge edge = Parent::findEdge(target, source, prev);
[1791]556        if (edge != INVALID) return edge;             
557      }
558      return INVALID;
559    }
[1979]560  };
561
562
563  template <typename Base>
564  class UGraphExtender : public Base {
565  public:
566   
567    typedef Base Parent;
568    typedef UGraphExtender Graph;
569
570    typedef typename Parent::Node Node;
571    typedef typename Parent::Edge Edge;
572    typedef typename Parent::UEdge UEdge;
573
574    // UGraph extension   
575
576    int maxId(Node) const {
577      return Parent::maxNodeId();
578    }
579
580    int maxId(Edge) const {
581      return Parent::maxEdgeId();
582    }
583
584    int maxId(UEdge) const {
585      return Parent::maxUEdgeId();
586    }
587
588    Node fromId(int id, Node) const {
589      return Parent::nodeFromId(id);
590    }
591
592    Edge fromId(int id, Edge) const {
593      return Parent::edgeFromId(id);
594    }
595
596    UEdge fromId(int id, UEdge) const {
597      return Parent::uEdgeFromId(id);
598    }
599
600    Node oppositeNode(const Node &n, const UEdge &e) const {
601      if( n == Parent::source(e))
602        return Parent::target(e);
603      else if( n == Parent::target(e))
604        return Parent::source(e);
605      else
606        return INVALID;
607    }
608
609    Edge oppositeEdge(const Edge &e) const {
610      return Parent::direct(e, !Parent::direction(e));
611    }
612
613    using Parent::direct;
614    Edge direct(const UEdge &ue, const Node &s) const {
615      return Parent::direct(ue, Parent::source(ue) == s);
616    }
617
618    // Alterable extension
619
620    typedef AlterationNotifier<Node> NodeNotifier;
621    typedef AlterationNotifier<Edge> EdgeNotifier;
622    typedef AlterationNotifier<UEdge> UEdgeNotifier;
623
624
625  protected:
626
627    mutable NodeNotifier node_notifier;
628    mutable EdgeNotifier edge_notifier;
629    mutable UEdgeNotifier uedge_notifier;
630
631  public:
632
633    NodeNotifier& getNotifier(Node) const {
634      return node_notifier;
635    }
636   
637    EdgeNotifier& getNotifier(Edge) const {
638      return edge_notifier;
639    }
640
641    UEdgeNotifier& getNotifier(UEdge) const {
642      return uedge_notifier;
643    }
644
645
646
647    class NodeIt : public Node {
648      const Graph* graph;
649    public:
650
651      NodeIt() {}
652
653      NodeIt(Invalid i) : Node(i) { }
654
655      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
656        _graph.first(*static_cast<Node*>(this));
657      }
658
659      NodeIt(const Graph& _graph, const Node& node)
660        : Node(node), graph(&_graph) {}
661
662      NodeIt& operator++() {
663        graph->next(*this);
664        return *this;
665      }
666
667    };
668
669
670    class EdgeIt : public Edge {
671      const Graph* graph;
672    public:
673
674      EdgeIt() { }
675
676      EdgeIt(Invalid i) : Edge(i) { }
677
678      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
679        _graph.first(*static_cast<Edge*>(this));
680      }
681
682      EdgeIt(const Graph& _graph, const Edge& e) :
683        Edge(e), graph(&_graph) { }
684
685      EdgeIt& operator++() {
686        graph->next(*this);
687        return *this;
688      }
689
690    };
691
692
693    class OutEdgeIt : public Edge {
694      const Graph* graph;
695    public:
696
697      OutEdgeIt() { }
698
699      OutEdgeIt(Invalid i) : Edge(i) { }
700
701      OutEdgeIt(const Graph& _graph, const Node& node)
702        : graph(&_graph) {
703        _graph.firstOut(*this, node);
704      }
705
706      OutEdgeIt(const Graph& _graph, const Edge& edge)
707        : Edge(edge), graph(&_graph) {}
708
709      OutEdgeIt& operator++() {
710        graph->nextOut(*this);
711        return *this;
712      }
713
714    };
715
716
717    class InEdgeIt : public Edge {
718      const Graph* graph;
719    public:
720
721      InEdgeIt() { }
722
723      InEdgeIt(Invalid i) : Edge(i) { }
724
725      InEdgeIt(const Graph& _graph, const Node& node)
726        : graph(&_graph) {
727        _graph.firstIn(*this, node);
728      }
729
730      InEdgeIt(const Graph& _graph, const Edge& edge) :
731        Edge(edge), graph(&_graph) {}
732
733      InEdgeIt& operator++() {
734        graph->nextIn(*this);
735        return *this;
736      }
737
738    };
739
740
741    class UEdgeIt : public Parent::UEdge {
742      const Graph* graph;
743    public:
744
745      UEdgeIt() { }
746
747      UEdgeIt(Invalid i) : UEdge(i) { }
748
749      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
750        _graph.first(*static_cast<UEdge*>(this));
751      }
752
753      UEdgeIt(const Graph& _graph, const UEdge& e) :
754        UEdge(e), graph(&_graph) { }
755
756      UEdgeIt& operator++() {
757        graph->next(*this);
758        return *this;
759      }
760
761    };
762
763    class IncEdgeIt : public Parent::UEdge {
764      friend class UGraphExtender;
765      const Graph* graph;
766      bool direction;
767    public:
768
769      IncEdgeIt() { }
770
771      IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
772
773      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
774        _graph.firstInc(*this, direction, n);
775      }
776
777      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
778        : graph(&_graph), UEdge(ue) {
779        direction = (_graph.source(ue) == n);
780      }
781
782      IncEdgeIt& operator++() {
783        graph->nextInc(*this, direction);
784        return *this;
785      }
786    };
787
788    /// \brief Base node of the iterator
789    ///
790    /// Returns the base node (ie. the source in this case) of the iterator
791    Node baseNode(const OutEdgeIt &e) const {
792      return Parent::source((Edge)e);
793    }
794    /// \brief Running node of the iterator
795    ///
796    /// Returns the running node (ie. the target in this case) of the
797    /// iterator
798    Node runningNode(const OutEdgeIt &e) const {
799      return Parent::target((Edge)e);
800    }
801
802    /// \brief Base node of the iterator
803    ///
804    /// Returns the base node (ie. the target in this case) of the iterator
805    Node baseNode(const InEdgeIt &e) const {
806      return Parent::target((Edge)e);
807    }
808    /// \brief Running node of the iterator
809    ///
810    /// Returns the running node (ie. the source in this case) of the
811    /// iterator
812    Node runningNode(const InEdgeIt &e) const {
813      return Parent::source((Edge)e);
814    }
815
816    /// Base node of the iterator
817    ///
818    /// Returns the base node of the iterator
819    Node baseNode(const IncEdgeIt &e) const {
820      return e.direction ? source(e) : target(e);
821    }
822    /// Running node of the iterator
823    ///
824    /// Returns the running node of the iterator
825    Node runningNode(const IncEdgeIt &e) const {
826      return e.direction ? target(e) : source(e);
827    }
828
829    // Mappable extension
830
831    template <typename _Value>
832    class NodeMap
833      : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > {
834    public:
835      typedef UGraphExtender Graph;
836      typedef IterableMapExtender<DefaultMap<Graph, Node, _Value> > Parent;
837
838      NodeMap(const Graph& _g)
839        : Parent(_g) {}
840      NodeMap(const Graph& _g, const _Value& _v)
841        : Parent(_g, _v) {}
842
843      NodeMap& operator=(const NodeMap& cmap) {
844        return operator=<NodeMap>(cmap);
845      }
846
847
848      /// \brief Template assign operator.
849      ///
850      /// The given parameter should be conform to the ReadMap
851      /// concecpt and could be indiced by the current item set of
852      /// the NodeMap. In this case the value for each item
853      /// is assigned by the value of the given ReadMap.
854      template <typename CMap>
855      NodeMap& operator=(const CMap& cmap) {
856        checkConcept<concept::ReadMap<Node, _Value>, CMap>();
857        const typename Parent::Graph* graph = Parent::getGraph();
858        Node it;
859        for (graph->first(it); it != INVALID; graph->next(it)) {
860          Parent::set(it, cmap[it]);
861        }
862        return *this;
863      }
864
865    };
866
867    template <typename _Value>
868    class EdgeMap
869      : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
870    public:
871      typedef UGraphExtender Graph;
872      typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
873
874      EdgeMap(const Graph& _g)
875        : Parent(_g) {}
876      EdgeMap(const Graph& _g, const _Value& _v)
877        : Parent(_g, _v) {}
878
879      EdgeMap& operator=(const EdgeMap& cmap) {
880        return operator=<EdgeMap>(cmap);
881      }
882
883      template <typename CMap>
884      EdgeMap& operator=(const CMap& cmap) {
885        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
886        const typename Parent::Graph* graph = Parent::getGraph();
887        Edge it;
888        for (graph->first(it); it != INVALID; graph->next(it)) {
889          Parent::set(it, cmap[it]);
890        }
891        return *this;
892      }
893    };
894
895
896    template <typename _Value>
897    class UEdgeMap
898      : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
899    public:
900      typedef UGraphExtender Graph;
901      typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
902
903      UEdgeMap(const Graph& _g)
904        : Parent(_g) {}
905      UEdgeMap(const Graph& _g, const _Value& _v)
906        : Parent(_g, _v) {}
907
908      UEdgeMap& operator=(const UEdgeMap& cmap) {
909        return operator=<UEdgeMap>(cmap);
910      }
911
912      template <typename CMap>
913      UEdgeMap& operator=(const CMap& cmap) {
914        checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
915        const typename Parent::Graph* graph = Parent::getGraph();
916        UEdge it;
917        for (graph->first(it); it != INVALID; graph->next(it)) {
918          Parent::set(it, cmap[it]);
919        }
920        return *this;
921      }
922    };
923
924    // Alteration extension
925
926    Node addNode() {
927      Node node = Parent::addNode();
928      getNotifier(Node()).add(node);
929      return node;
930    }
931
932    UEdge addEdge(const Node& from, const Node& to) {
933      UEdge uedge = Parent::addEdge(from, to);
934      getNotifier(UEdge()).add(uedge);
935      getNotifier(Edge()).add(Parent::direct(uedge, true));
936      getNotifier(Edge()).add(Parent::direct(uedge, false));
937      return uedge;
938    }
939   
940    void clear() {
941      getNotifier(Edge()).clear();
942      getNotifier(UEdge()).clear();
943      getNotifier(Node()).clear();
944      Parent::clear();
945    }
946
947    void erase(const Node& node) {
948      Edge edge;
949      Parent::firstOut(edge, node);
950      while (edge != INVALID ) {
951        erase(edge);
952        Parent::firstOut(edge, node);
953      }
954
955      Parent::firstIn(edge, node);
956      while (edge != INVALID ) {
957        erase(edge);
958        Parent::firstIn(edge, node);
959      }
960
961      getNotifier(Node()).erase(node);
962      Parent::erase(node);
963    }
964
965    void erase(const UEdge& uedge) {
966      getNotifier(Edge()).erase(Parent::direct(uedge, true));
967      getNotifier(Edge()).erase(Parent::direct(uedge, false));
968      getNotifier(UEdge()).erase(uedge);
969      Parent::erase(uedge);
970    }
971
972    ~UGraphExtender() {
973      getNotifier(Edge()).clear();
974      getNotifier(UEdge()).clear();
975      getNotifier(Node()).clear();
976    }
[1791]977
978  };
979
[1820]980
[1979]981  template <typename Base>
982  class BpUGraphBaseExtender : public Base {
[1820]983  public:
[1979]984    typedef Base Parent;
985    typedef BpUGraphBaseExtender Graph;
[1820]986
987    typedef typename Parent::Node Node;
[1909]988    typedef typename Parent::Edge UEdge;
[1820]989
[1979]990
[1820]991    using Parent::first;
992    using Parent::next;
993
994    using Parent::id;
995
[1979]996    class ANode : public Node {
997      friend class BpUGraphBaseExtender;
998    public:
999      ANode() {}
1000      ANode(const Node& node) : Node(node) {
1001        LEMON_ASSERT(Parent::aNode(node) || node == INVALID,
1002                     typename Parent::NodeSetError());
1003      }
1004      ANode(Invalid) : Node(INVALID) {}
1005    };
1006
1007    void first(ANode& node) const {
1008      Parent::firstANode(static_cast<Node&>(node));
1009    }
1010    void next(ANode& node) const {
1011      Parent::nextANode(static_cast<Node&>(node));
1012    }
1013
1014    int id(const ANode& node) const {
1015      return Parent::aNodeId(node);
1016    }
1017
1018    class BNode : public Node {
1019      friend class BpUGraphBaseExtender;
1020    public:
1021      BNode() {}
1022      BNode(const Node& node) : Node(node) {
1023        LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
1024                     typename Parent::NodeSetError());
1025      }
1026      BNode(Invalid) : Node(INVALID) {}
1027    };
1028
1029    void first(BNode& node) const {
1030      Parent::firstBNode(static_cast<Node&>(node));
1031    }
1032    void next(BNode& node) const {
1033      Parent::nextBNode(static_cast<Node&>(node));
1034    }
1035 
1036    int id(const BNode& node) const {
1037      return Parent::aNodeId(node);
1038    }
1039
[1909]1040    Node source(const UEdge& edge) const {
[1910]1041      return aNode(edge);
[1820]1042    }
[1909]1043    Node target(const UEdge& edge) const {
[1910]1044      return bNode(edge);
[1820]1045    }
1046
[1909]1047    void firstInc(UEdge& edge, bool& direction, const Node& node) const {
[1910]1048      if (Parent::aNode(node)) {
1049        Parent::firstOut(edge, node);
[1820]1050        direction = true;
1051      } else {
[1910]1052        Parent::firstIn(edge, node);
[1909]1053        direction = static_cast<UEdge&>(edge) == INVALID;
[1820]1054      }
1055    }
[1909]1056    void nextInc(UEdge& edge, bool& direction) const {
[1820]1057      if (direction) {
[1910]1058        Parent::nextOut(edge);
[1820]1059      } else {
[1910]1060        Parent::nextIn(edge);
[1820]1061        if (edge == INVALID) direction = true;
1062      }
1063    }
1064
[1909]1065    int maxUEdgeId() const {
[1820]1066      return Parent::maxEdgeId();
1067    }
1068
[1909]1069    UEdge uEdgeFromId(int id) const {
[1820]1070      return Parent::edgeFromId(id);
1071    }
1072
[1909]1073    class Edge : public UEdge {
[1979]1074      friend class BpUGraphBaseExtender;
[1820]1075    protected:
1076      bool forward;
1077
[1909]1078      Edge(const UEdge& edge, bool _forward)
1079        : UEdge(edge), forward(_forward) {}
[1820]1080
1081    public:
1082      Edge() {}
[1909]1083      Edge (Invalid) : UEdge(INVALID), forward(true) {}
[1820]1084      bool operator==(const Edge& i) const {
[1909]1085        return UEdge::operator==(i) && forward == i.forward;
[1820]1086      }
1087      bool operator!=(const Edge& i) const {
[1909]1088        return UEdge::operator!=(i) || forward != i.forward;
[1820]1089      }
1090      bool operator<(const Edge& i) const {
[1909]1091        return UEdge::operator<(i) ||
1092          (!(i.forward<forward) && UEdge(*this)<UEdge(i));
[1820]1093      }
1094    };
1095
1096    void first(Edge& edge) const {
[1909]1097      Parent::first(static_cast<UEdge&>(edge));
[1820]1098      edge.forward = true;
1099    }
1100
1101    void next(Edge& edge) const {
1102      if (!edge.forward) {
[1909]1103        Parent::next(static_cast<UEdge&>(edge));
[1820]1104      }
1105      edge.forward = !edge.forward;
1106    }
1107
1108    void firstOut(Edge& edge, const Node& node) const {
[1910]1109      if (Parent::aNode(node)) {
1110        Parent::firstOut(edge, node);
[1820]1111        edge.forward = true;
1112      } else {
[1910]1113        Parent::firstIn(edge, node);
[1909]1114        edge.forward = static_cast<UEdge&>(edge) == INVALID;
[1820]1115      }
1116    }
1117    void nextOut(Edge& edge) const {
1118      if (edge.forward) {
[1910]1119        Parent::nextOut(edge);
[1820]1120      } else {
[1910]1121        Parent::nextIn(edge);
[1909]1122        edge.forward = static_cast<UEdge&>(edge) == INVALID;
[1820]1123      }
1124    }
1125
1126    void firstIn(Edge& edge, const Node& node) const {
[1910]1127      if (Parent::bNode(node)) {
1128        Parent::firstIn(edge, node);
[1820]1129        edge.forward = true;   
1130      } else {
[1910]1131        Parent::firstOut(edge, node);
[1909]1132        edge.forward = static_cast<UEdge&>(edge) == INVALID;
[1820]1133      }
1134    }
1135    void nextIn(Edge& edge) const {
1136      if (edge.forward) {
[1910]1137        Parent::nextIn(edge);
[1820]1138      } else {
[1910]1139        Parent::nextOut(edge);
[1909]1140        edge.forward = static_cast<UEdge&>(edge) == INVALID;
[1820]1141      }
1142    }
1143
1144    Node source(const Edge& edge) const {
[1910]1145      return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
[1820]1146    }
1147    Node target(const Edge& edge) const {
[1910]1148      return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
[1820]1149    }
1150
1151    int id(const Edge& edge) const {
1152      return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1);
1153    }
1154    Edge edgeFromId(int id) const {
[1909]1155      return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0);
[1820]1156    }
1157    int maxEdgeId() const {
[1909]1158      return (Parent::maxId(UEdge()) << 1) + 1;
[1820]1159    }
1160
[1979]1161    bool direction(const Edge& edge) const {
1162      return edge.forward;
[1820]1163    }
1164
[1979]1165    Edge direct(const UEdge& edge, bool direction) const {
1166      return Edge(edge, direction);
1167    }
1168  };
1169
1170  template <typename Base>
1171  class BpUGraphExtender : public Base {
1172  public:
1173    typedef Base Parent;
1174    typedef BpUGraphExtender Graph;
1175
1176    typedef typename Parent::Node Node;
1177    typedef typename Parent::BNode BNode;
1178    typedef typename Parent::ANode ANode;
1179    typedef typename Parent::Edge Edge;
1180    typedef typename Parent::UEdge UEdge;
1181
1182    Node oppositeNode(const UEdge& edge, const Node& node) const {
1183      return source(edge) == node ?
1184        target(edge) : source(edge);
[1820]1185    }
1186
[1979]1187    using Parent::direct;
1188    Edge direct(const UEdge& edge, const Node& node) const {
1189      return Edge(edge, node == Parent::source(edge));
[1820]1190    }
1191
[1979]1192    Edge oppositeEdge(const Edge& edge) const {
1193      return Parent::direct(edge, !Parent::direction(edge));
1194    }
[1820]1195
1196
1197    int maxId(Node) const {
1198      return Parent::maxNodeId();
1199    }
[1910]1200    int maxId(BNode) const {
1201      return Parent::maxBNodeId();
[1820]1202    }
[1910]1203    int maxId(ANode) const {
1204      return Parent::maxANodeId();
[1820]1205    }
1206    int maxId(Edge) const {
[1979]1207      return Parent::maxEdgeId();
[1820]1208    }
[1909]1209    int maxId(UEdge) const {
[1979]1210      return Parent::maxUEdgeId();
[1820]1211    }
1212
1213
1214    Node fromId(int id, Node) const {
1215      return Parent::nodeFromId(id);
1216    }
[1910]1217    ANode fromId(int id, ANode) const {
1218      return Parent::fromANodeId(id);
[1820]1219    }
[1910]1220    BNode fromId(int id, BNode) const {
1221      return Parent::fromBNodeId(id);
[1820]1222    }
1223    Edge fromId(int id, Edge) const {
[1979]1224      return Parent::edgeFromId(id);
[1820]1225    }
[1909]1226    UEdge fromId(int id, UEdge) const {
[1979]1227      return Parent::uEdgeFromId(id);
1228    } 
1229 
1230    typedef AlterationNotifier<Node> NodeNotifier;
1231    typedef AlterationNotifier<BNode> BNodeNotifier;
1232    typedef AlterationNotifier<ANode> ANodeNotifier;
1233    typedef AlterationNotifier<Edge> EdgeNotifier;
1234    typedef AlterationNotifier<UEdge> UEdgeNotifier;
1235
1236  protected:
1237
1238    mutable NodeNotifier nodeNotifier;
1239    mutable BNodeNotifier bNodeNotifier;
1240    mutable ANodeNotifier aNodeNotifier;
1241    mutable EdgeNotifier edgeNotifier;
1242    mutable UEdgeNotifier uEdgeNotifier;
1243
1244  public:
1245
1246    NodeNotifier& getNotifier(Node) const {
1247      return nodeNotifier;
[1820]1248    }
1249
[1979]1250    BNodeNotifier& getNotifier(BNode) const {
1251      return bNodeNotifier;
1252    }
1253
1254    ANodeNotifier& getNotifier(ANode) const {
1255      return aNodeNotifier;
1256    }
1257
1258    EdgeNotifier& getNotifier(Edge) const {
1259      return edgeNotifier;
1260    }
1261
1262    UEdgeNotifier& getNotifier(UEdge) const {
1263      return uEdgeNotifier;
1264    }
1265
1266    class NodeIt : public Node {
1267      const Graph* graph;
1268    public:
1269   
1270      NodeIt() { }
1271   
1272      NodeIt(Invalid i) : Node(INVALID) { }
1273   
1274      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
1275        graph->first(static_cast<Node&>(*this));
1276      }
1277
1278      NodeIt(const Graph& _graph, const Node& node)
1279        : Node(node), graph(&_graph) { }
1280   
1281      NodeIt& operator++() {
1282        graph->next(*this);
1283        return *this;
1284      }
1285
1286    };
1287
1288    class ANodeIt : public Node {
1289      friend class BpUGraphExtender;
1290      const Graph* graph;
1291    public:
1292   
1293      ANodeIt() { }
1294   
1295      ANodeIt(Invalid i) : Node(INVALID) { }
1296   
1297      explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
1298        graph->firstANode(static_cast<Node&>(*this));
1299      }
1300
1301      ANodeIt(const Graph& _graph, const Node& node)
1302        : Node(node), graph(&_graph) {}
1303   
1304      ANodeIt& operator++() {
1305        graph->nextANode(*this);
1306        return *this;
1307      }
1308    };
1309
1310    class BNodeIt : public Node {
1311      friend class BpUGraphExtender;
1312      const Graph* graph;
1313    public:
1314   
1315      BNodeIt() { }
1316   
1317      BNodeIt(Invalid i) : Node(INVALID) { }
1318   
1319      explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
1320        graph->firstBNode(static_cast<Node&>(*this));
1321      }
1322
1323      BNodeIt(const Graph& _graph, const Node& node)
1324        : Node(node), graph(&_graph) {}
1325   
1326      BNodeIt& operator++() {
1327        graph->nextBNode(*this);
1328        return *this;
1329      }
1330    };
1331
1332    class EdgeIt : public Edge {
1333      friend class BpUGraphExtender;
1334      const Graph* graph;
1335    public:
1336   
1337      EdgeIt() { }
1338   
1339      EdgeIt(Invalid i) : Edge(INVALID) { }
1340   
1341      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
1342        graph->first(static_cast<Edge&>(*this));
1343      }
1344
1345      EdgeIt(const Graph& _graph, const Edge& edge)
1346        : Edge(edge), graph(&_graph) { }
1347   
1348      EdgeIt& operator++() {
1349        graph->next(*this);
1350        return *this;
1351      }
1352
1353    };
1354
1355    class UEdgeIt : public UEdge {
1356      friend class BpUGraphExtender;
1357      const Graph* graph;
1358    public:
1359   
1360      UEdgeIt() { }
1361   
1362      UEdgeIt(Invalid i) : UEdge(INVALID) { }
1363   
1364      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
1365        graph->first(static_cast<UEdge&>(*this));
1366      }
1367
1368      UEdgeIt(const Graph& _graph, const UEdge& edge)
1369        : UEdge(edge), graph(&_graph) { }
1370   
1371      UEdgeIt& operator++() {
1372        graph->next(*this);
1373        return *this;
1374      }
1375    };
1376
1377    class OutEdgeIt : public Edge {
1378      friend class BpUGraphExtender;
1379      const Graph* graph;
1380    public:
1381   
1382      OutEdgeIt() { }
1383   
1384      OutEdgeIt(Invalid i) : Edge(i) { }
1385   
1386      OutEdgeIt(const Graph& _graph, const Node& node)
1387        : graph(&_graph) {
1388        graph->firstOut(*this, node);
1389      }
1390   
1391      OutEdgeIt(const Graph& _graph, const Edge& edge)
1392        : Edge(edge), graph(&_graph) {}
1393   
1394      OutEdgeIt& operator++() {
1395        graph->nextOut(*this);
1396        return *this;
1397      }
1398
1399    };
1400
1401
1402    class InEdgeIt : public Edge {
1403      friend class BpUGraphExtender;
1404      const Graph* graph;
1405    public:
1406   
1407      InEdgeIt() { }
1408   
1409      InEdgeIt(Invalid i) : Edge(i) { }
1410   
1411      InEdgeIt(const Graph& _graph, const Node& node)
1412        : graph(&_graph) {
1413        graph->firstIn(*this, node);
1414      }
1415   
1416      InEdgeIt(const Graph& _graph, const Edge& edge) :
1417        Edge(edge), graph(&_graph) {}
1418   
1419      InEdgeIt& operator++() {
1420        graph->nextIn(*this);
1421        return *this;
1422      }
1423
1424    };
1425 
1426    /// \brief Base node of the iterator
1427    ///
1428    /// Returns the base node (ie. the source in this case) of the iterator
1429    Node baseNode(const OutEdgeIt &e) const {
1430      return Parent::source((Edge&)e);
1431    }
1432    /// \brief Running node of the iterator
1433    ///
1434    /// Returns the running node (ie. the target in this case) of the
1435    /// iterator
1436    Node runningNode(const OutEdgeIt &e) const {
1437      return Parent::target((Edge&)e);
1438    }
1439 
1440    /// \brief Base node of the iterator
1441    ///
1442    /// Returns the base node (ie. the target in this case) of the iterator
1443    Node baseNode(const InEdgeIt &e) const {
1444      return Parent::target((Edge&)e);
1445    }
1446    /// \brief Running node of the iterator
1447    ///
1448    /// Returns the running node (ie. the source in this case) of the
1449    /// iterator
1450    Node runningNode(const InEdgeIt &e) const {
1451      return Parent::source((Edge&)e);
1452    }
1453 
1454    class IncEdgeIt : public Parent::UEdge {
1455      friend class BpUGraphExtender;
1456      const Graph* graph;
1457      bool direction;
1458    public:
1459   
1460      IncEdgeIt() { }
1461   
1462      IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
1463   
1464      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
1465        graph->firstInc(*this, direction, n);
1466      }
1467
1468      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
1469        : graph(&_graph), UEdge(ue) {
1470        direction = (graph->source(ue) == n);
1471      }
1472
1473      IncEdgeIt& operator++() {
1474        graph->nextInc(*this, direction);
1475        return *this;
1476      }
1477    };
1478 
1479
1480    /// Base node of the iterator
1481    ///
1482    /// Returns the base node of the iterator
1483    Node baseNode(const IncEdgeIt &e) const {
1484      return e.direction ? source(e) : target(e);
1485    }
1486
1487    /// Running node of the iterator
1488    ///
1489    /// Returns the running node of the iterator
1490    Node runningNode(const IncEdgeIt &e) const {
1491      return e.direction ? target(e) : source(e);
1492    }
1493
1494    template <typename _Value>
1495    class ANodeMap
1496      : public IterableMapExtender<DefaultMap<Graph, ANode, _Value> > {
1497    public:
1498      typedef BpUGraphExtender Graph;
1499      typedef IterableMapExtender<DefaultMap<Graph, ANode, _Value> >
1500      Parent;
1501   
1502      ANodeMap(const Graph& _g)
1503        : Parent(_g) {}
1504      ANodeMap(const Graph& _g, const _Value& _v)
1505        : Parent(_g, _v) {}
1506   
1507      ANodeMap& operator=(const ANodeMap& cmap) {
1508        return operator=<ANodeMap>(cmap);
1509      }
1510   
1511
1512      /// \brief Template assign operator.
1513      ///
1514      /// The given parameter should be conform to the ReadMap
1515      /// concept and could be indiced by the current item set of
1516      /// the ANodeMap. In this case the value for each item
1517      /// is assigned by the value of the given ReadMap.
1518      template <typename CMap>
1519      ANodeMap& operator=(const CMap& cmap) {
1520        checkConcept<concept::ReadMap<ANode, _Value>, CMap>();
1521        const typename Parent::Graph* graph = Parent::getGraph();
1522        ANode it;
1523        for (graph->first(it); it != INVALID; graph->next(it)) {
1524          Parent::set(it, cmap[it]);
1525        }
1526        return *this;
1527      }
1528   
1529    };
1530
1531    template <typename _Value>
1532    class BNodeMap
1533      : public IterableMapExtender<DefaultMap<Graph, BNode, _Value> > {
1534    public:
1535      typedef BpUGraphExtender Graph;
1536      typedef IterableMapExtender<DefaultMap<Graph, BNode, _Value> >
1537      Parent;
1538   
1539      BNodeMap(const Graph& _g)
1540        : Parent(_g) {}
1541      BNodeMap(const Graph& _g, const _Value& _v)
1542        : Parent(_g, _v) {}
1543   
1544      BNodeMap& operator=(const BNodeMap& cmap) {
1545        return operator=<BNodeMap>(cmap);
1546      }
1547   
1548
1549      /// \brief Template assign operator.
1550      ///
1551      /// The given parameter should be conform to the ReadMap
1552      /// concept and could be indiced by the current item set of
1553      /// the BNodeMap. In this case the value for each item
1554      /// is assigned by the value of the given ReadMap.
1555      template <typename CMap>
1556      BNodeMap& operator=(const CMap& cmap) {
1557        checkConcept<concept::ReadMap<BNode, _Value>, CMap>();
1558        const typename Parent::Graph* graph = Parent::getGraph();
1559        BNode it;
1560        for (graph->first(it); it != INVALID; graph->next(it)) {
1561          Parent::set(it, cmap[it]);
1562        }
1563        return *this;
1564      }
1565   
1566    };
1567
1568  protected:
1569
1570    template <typename _Value>
[1991]1571    class NodeMapBase {
[1979]1572    public:
1573      typedef BpUGraphExtender Graph;
1574
1575      typedef Node Key;
1576      typedef _Value Value;
1577
1578      /// The reference type of the map;
1579      typedef typename BNodeMap<_Value>::Reference Reference;
1580      /// The pointer type of the map;
1581      typedef typename BNodeMap<_Value>::Pointer Pointer;
1582     
1583      /// The const value type of the map.
1584      typedef const Value ConstValue;
1585      /// The const reference type of the map;
1586      typedef typename BNodeMap<_Value>::ConstReference ConstReference;
1587      /// The pointer type of the map;
1588      typedef typename BNodeMap<_Value>::ConstPointer ConstPointer;
1589
1590      typedef True ReferenceMapTag;
1591
1592      NodeMapBase(const Graph& _g)
[1991]1593        : aNodeMap(_g), bNodeMap(_g) {}
[1979]1594      NodeMapBase(const Graph& _g, const _Value& _v)
[1991]1595        : aNodeMap(_g, _v), bNodeMap(_g, _v) {}
[1979]1596
1597      ConstReference operator[](const Key& node) const {
1598        if (Parent::aNode(node)) {
1599          return aNodeMap[node];
1600        } else {
1601          return bNodeMap[node];
1602        }
1603      }
1604
1605      Reference operator[](const Key& node) {
1606        if (Parent::aNode(node)) {
1607          return aNodeMap[node];
1608        } else {
1609          return bNodeMap[node];
1610        }
1611      }
1612
1613      void set(const Key& node, const Value& value) {
1614        if (Parent::aNode(node)) {
1615          aNodeMap.set(node, value);
1616        } else {
1617          bNodeMap.set(node, value);
1618        }
1619      }
1620
[1991]1621      const Graph* getGraph() const {
1622        return aNodeMap.getGraph();
1623      }
[1979]1624
1625    private:
[1991]1626      ANodeMap<_Value> aNodeMap;
[1979]1627      BNodeMap<_Value> bNodeMap;
1628    };
1629   
1630  public:
1631
1632    template <typename _Value>
1633    class NodeMap
1634      : public IterableMapExtender<NodeMapBase<_Value> > {
1635    public:
1636      typedef BpUGraphExtender Graph;
1637      typedef IterableMapExtender< NodeMapBase<_Value> > Parent;
1638   
1639      NodeMap(const Graph& _g)
1640        : Parent(_g) {}
1641      NodeMap(const Graph& _g, const _Value& _v)
1642        : Parent(_g, _v) {}
1643   
1644      NodeMap& operator=(const NodeMap& cmap) {
1645        return operator=<NodeMap>(cmap);
1646      }
1647   
1648
1649      /// \brief Template assign operator.
1650      ///
1651      /// The given parameter should be conform to the ReadMap
1652      /// concept and could be indiced by the current item set of
1653      /// the NodeMap. In this case the value for each item
1654      /// is assigned by the value of the given ReadMap.
1655      template <typename CMap>
1656      NodeMap& operator=(const CMap& cmap) {
1657        checkConcept<concept::ReadMap<Node, _Value>, CMap>();
1658        const typename Parent::Graph* graph = Parent::getGraph();
1659        Node it;
1660        for (graph->first(it); it != INVALID; graph->next(it)) {
1661          Parent::set(it, cmap[it]);
1662        }
1663        return *this;
1664      }
1665   
1666    };
1667
1668
1669
1670    template <typename _Value>
1671    class EdgeMap
1672      : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
1673    public:
1674      typedef BpUGraphExtender Graph;
1675      typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
1676   
1677      EdgeMap(const Graph& _g)
1678        : Parent(_g) {}
1679      EdgeMap(const Graph& _g, const _Value& _v)
1680        : Parent(_g, _v) {}
1681   
1682      EdgeMap& operator=(const EdgeMap& cmap) {
1683        return operator=<EdgeMap>(cmap);
1684      }
1685   
1686      template <typename CMap>
1687      EdgeMap& operator=(const CMap& cmap) {
1688        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
1689        const typename Parent::Graph* graph = Parent::getGraph();
1690        Edge it;
1691        for (graph->first(it); it != INVALID; graph->next(it)) {
1692          Parent::set(it, cmap[it]);
1693        }
1694        return *this;
1695      }
1696    };
1697
1698    template <typename _Value>
1699    class UEdgeMap
1700      : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
1701    public:
1702      typedef BpUGraphExtender Graph;
1703      typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> >
1704      Parent;
1705   
1706      UEdgeMap(const Graph& _g)
1707        : Parent(_g) {}
1708      UEdgeMap(const Graph& _g, const _Value& _v)
1709        : Parent(_g, _v) {}
1710   
1711      UEdgeMap& operator=(const UEdgeMap& cmap) {
1712        return operator=<UEdgeMap>(cmap);
1713      }
1714   
1715      template <typename CMap>
1716      UEdgeMap& operator=(const CMap& cmap) {
1717        checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
1718        const typename Parent::Graph* graph = Parent::getGraph();
1719        UEdge it;
1720        for (graph->first(it); it != INVALID; graph->next(it)) {
1721          Parent::set(it, cmap[it]);
1722        }
1723        return *this;
1724      }
1725    };
1726
1727 
1728    Node addANode() {
1729      Node node = Parent::addANode();
1730      getNotifier(ANode()).add(node);
1731      getNotifier(Node()).add(node);
1732      return node;
1733    }
1734
1735    Node addBNode() {
1736      Node node = Parent::addBNode();
1737      getNotifier(BNode()).add(node);
1738      getNotifier(Node()).add(node);
1739      return node;
1740    }
1741 
1742    UEdge addEdge(const Node& source, const Node& target) {
1743      UEdge uedge = Parent::addEdge(source, target);
1744      getNotifier(UEdge()).add(uedge);
1745   
1746      std::vector<Edge> edges;
1747      edges.push_back(direct(uedge, true));
1748      edges.push_back(direct(uedge, false));
1749      getNotifier(Edge()).add(edges);
1750   
1751      return uedge;
1752    }
1753
1754    void clear() {
1755      getNotifier(Edge()).clear();
1756      getNotifier(UEdge()).clear();
1757      getNotifier(Node()).clear();
1758      getNotifier(BNode()).clear();
1759      getNotifier(ANode()).clear();
1760      Parent::clear();
1761    }
1762
1763    void erase(const Node& node) {
1764      UEdge uedge;
1765      bool dir;
1766      Parent::firstInc(uedge, dir, node);
1767      while (uedge != INVALID ) {
1768        erase(uedge);
1769        Parent::firstInc(uedge, dir, node);
1770      }
1771
1772      getNotifier(Node()).erase(node);
1773      Parent::erase(node);
1774    }
1775   
1776    void erase(const UEdge& uedge) {
1777      std::vector<Edge> edges;
1778      edges.push_back(direct(uedge, true));
1779      edges.push_back(direct(uedge, false));
1780      getNotifier(Edge()).erase(edges);
1781      getNotifier(UEdge()).erase(uedge);
1782      Parent::erase(uedge);
1783    }
1784
1785
1786    ~BpUGraphExtender() {
1787      getNotifier(Edge()).clear();
1788      getNotifier(UEdge()).clear();
1789      getNotifier(Node()).clear();
1790      getNotifier(BNode()).clear();
1791      getNotifier(ANode()).clear();
1792    }
1793
1794
[1820]1795  };
1796
[1791]1797}
1798
1799#endif // LEMON_UNDIR_GRAPH_EXTENDER_H
Note: See TracBrowser for help on using the repository browser.