COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/graph_extender.h @ 1996:5dc13b93f8b4

Last change on this file since 1996:5dc13b93f8b4 was 1996:5dc13b93f8b4, checked in by Balazs Dezso, 13 years ago

Some documentation arrangement modification

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