COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/graph_extender.h @ 2067:cd414bfbe38b

Last change on this file since 2067:cd414bfbe38b was 2046:66d160810c0a, checked in by Mihaly Barasz, 18 years ago

more explicit :)

File size: 30.6 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/map_extender.h>
26#include <lemon/bits/default_map.h>
27
28#include <lemon/concept_check.h>
29#include <lemon/concept/maps.h>
30
31///\ingroup graphbits
32///\file
33///\brief Extenders for the graph types
34namespace lemon {
35
36  /// \ingroup graphbits
37  ///
38  /// \brief Extender for the Graphs
39  template <typename Base>
40  class GraphExtender : public Base {
41  public:
42
43    typedef Base Parent;
44    typedef GraphExtender Graph;
45
46    // Base extensions
47
48    typedef typename Parent::Node Node;
49    typedef typename Parent::Edge Edge;
50
51    int maxId(Node) const {
52      return Parent::maxNodeId();
53    }
54
55    int maxId(Edge) const {
56      return Parent::maxEdgeId();
57    }
58
59    Node fromId(int id, Node) const {
60      return Parent::nodeFromId(id);
61    }
62
63    Edge fromId(int id, Edge) const {
64      return Parent::edgeFromId(id);
65    }
66
67    Node oppositeNode(const Node &n, const Edge &e) const {
68      if (n == Parent::source(e))
69        return Parent::target(e);
70      else if(n==Parent::target(e))
71        return Parent::source(e);
72      else
73        return INVALID;
74    }
75
76    // Alterable extension
77
78    typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
79    typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;
80
81
82  protected:
83
84    mutable NodeNotifier node_notifier;
85    mutable EdgeNotifier edge_notifier;
86
87  public:
88
89    NodeNotifier& getNotifier(Node) const {
90      return node_notifier;
91    }
92   
93    EdgeNotifier& getNotifier(Edge) const {
94      return edge_notifier;
95    }
96
97    class NodeIt : public Node {
98      const Graph* graph;
99    public:
100
101      NodeIt() {}
102
103      NodeIt(Invalid i) : Node(i) { }
104
105      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
106        _graph.first(static_cast<Node&>(*this));
107      }
108
109      NodeIt(const Graph& _graph, const Node& node)
110        : Node(node), graph(&_graph) {}
111
112      NodeIt& operator++() {
113        graph->next(*this);
114        return *this;
115      }
116
117    };
118
119
120    class EdgeIt : public Edge {
121      const Graph* graph;
122    public:
123
124      EdgeIt() { }
125
126      EdgeIt(Invalid i) : Edge(i) { }
127
128      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
129        _graph.first(static_cast<Edge&>(*this));
130      }
131
132      EdgeIt(const Graph& _graph, const Edge& e) :
133        Edge(e), graph(&_graph) { }
134
135      EdgeIt& operator++() {
136        graph->next(*this);
137        return *this;
138      }
139
140    };
141
142
143    class OutEdgeIt : public Edge {
144      const Graph* graph;
145    public:
146
147      OutEdgeIt() { }
148
149      OutEdgeIt(Invalid i) : Edge(i) { }
150
151      OutEdgeIt(const Graph& _graph, const Node& node)
152        : graph(&_graph) {
153        _graph.firstOut(*this, node);
154      }
155
156      OutEdgeIt(const Graph& _graph, const Edge& edge)
157        : Edge(edge), graph(&_graph) {}
158
159      OutEdgeIt& operator++() {
160        graph->nextOut(*this);
161        return *this;
162      }
163
164    };
165
166
167    class InEdgeIt : public Edge {
168      const Graph* graph;
169    public:
170
171      InEdgeIt() { }
172
173      InEdgeIt(Invalid i) : Edge(i) { }
174
175      InEdgeIt(const Graph& _graph, const Node& node)
176        : graph(&_graph) {
177        _graph.firstIn(*this, node);
178      }
179
180      InEdgeIt(const Graph& _graph, const Edge& edge) :
181        Edge(edge), graph(&_graph) {}
182
183      InEdgeIt& operator++() {
184        graph->nextIn(*this);
185        return *this;
186      }
187
188    };
189
190    /// \brief Base node of the iterator
191    ///
192    /// Returns the base node (ie. the source in this case) of the iterator
193    Node baseNode(const OutEdgeIt &e) const {
194      return Parent::source(e);
195    }
196    /// \brief Running node of the iterator
197    ///
198    /// Returns the running node (ie. the target in this case) of the
199    /// iterator
200    Node runningNode(const OutEdgeIt &e) const {
201      return Parent::target(e);
202    }
203
204    /// \brief Base node of the iterator
205    ///
206    /// Returns the base node (ie. the target in this case) of the iterator
207    Node baseNode(const InEdgeIt &e) const {
208      return Parent::target(e);
209    }
210    /// \brief Running node of the iterator
211    ///
212    /// Returns the running node (ie. the source in this case) of the
213    /// iterator
214    Node runningNode(const InEdgeIt &e) const {
215      return Parent::source(e);
216    }
217
218   
219    template <typename _Value>
220    class NodeMap
221      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
222    public:
223      typedef GraphExtender Graph;
224      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
225
226      explicit NodeMap(const Graph& graph)
227        : Parent(graph) {}
228      NodeMap(const Graph& graph, const _Value& value)
229        : Parent(graph, value) {}
230
231      NodeMap& operator=(const NodeMap& cmap) {
232        return operator=<NodeMap>(cmap);
233      }
234
235      template <typename CMap>
236      NodeMap& operator=(const CMap& cmap) {
237        Parent::operator=(cmap);
238        return *this;
239      }
240
241    };
242
243    template <typename _Value>
244    class EdgeMap
245      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
246    public:
247      typedef GraphExtender Graph;
248      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
249
250      explicit EdgeMap(const Graph& graph)
251        : Parent(graph) {}
252      EdgeMap(const Graph& graph, const _Value& value)
253        : Parent(graph, value) {}
254
255      EdgeMap& operator=(const EdgeMap& cmap) {
256        return operator=<EdgeMap>(cmap);
257      }
258
259      template <typename CMap>
260      EdgeMap& operator=(const CMap& cmap) {
261        Parent::operator=(cmap);
262        return *this;
263      }
264    };
265
266
267    Node addNode() {
268      Node node = Parent::addNode();
269      getNotifier(Node()).add(node);
270      return node;
271    }
272   
273    Edge addEdge(const Node& from, const Node& to) {
274      Edge edge = Parent::addEdge(from, to);
275      getNotifier(Edge()).add(edge);
276      return edge;
277    }
278
279    void clear() {
280      getNotifier(Edge()).clear();
281      getNotifier(Node()).clear();
282      Parent::clear();
283    }
284
285
286    void erase(const Node& node) {
287      Edge edge;
288      Parent::firstOut(edge, node);
289      while (edge != INVALID ) {
290        erase(edge);
291        Parent::firstOut(edge, node);
292      }
293
294      Parent::firstIn(edge, node);
295      while (edge != INVALID ) {
296        erase(edge);
297        Parent::firstIn(edge, node);
298      }
299
300      getNotifier(Node()).erase(node);
301      Parent::erase(node);
302    }
303   
304    void erase(const Edge& edge) {
305      getNotifier(Edge()).erase(edge);
306      Parent::erase(edge);
307    }
308
309    GraphExtender() {
310      node_notifier.setContainer(*this);
311      edge_notifier.setContainer(*this);
312    }
313   
314
315    ~GraphExtender() {
316      edge_notifier.clear();
317      node_notifier.clear();
318    }
319  };
320
321  /// \ingroup graphbits
322  ///
323  /// \brief Extender for the UGraphs
324  template <typename Base>
325  class UGraphExtender : public Base {
326  public:
327   
328    typedef Base Parent;
329    typedef UGraphExtender Graph;
330
331    typedef typename Parent::Node Node;
332    typedef typename Parent::Edge Edge;
333    typedef typename Parent::UEdge UEdge;
334
335    // UGraph extension   
336
337    int maxId(Node) const {
338      return Parent::maxNodeId();
339    }
340
341    int maxId(Edge) const {
342      return Parent::maxEdgeId();
343    }
344
345    int maxId(UEdge) const {
346      return Parent::maxUEdgeId();
347    }
348
349    Node fromId(int id, Node) const {
350      return Parent::nodeFromId(id);
351    }
352
353    Edge fromId(int id, Edge) const {
354      return Parent::edgeFromId(id);
355    }
356
357    UEdge fromId(int id, UEdge) const {
358      return Parent::uEdgeFromId(id);
359    }
360
361    Node oppositeNode(const Node &n, const UEdge &e) const {
362      if( n == Parent::source(e))
363        return Parent::target(e);
364      else if( n == Parent::target(e))
365        return Parent::source(e);
366      else
367        return INVALID;
368    }
369
370    Edge oppositeEdge(const Edge &e) const {
371      return Parent::direct(e, !Parent::direction(e));
372    }
373
374    using Parent::direct;
375    Edge direct(const UEdge &ue, const Node &s) const {
376      return Parent::direct(ue, Parent::source(ue) == s);
377    }
378
379    // Alterable extension
380
381    typedef AlterationNotifier<UGraphExtender, Node> NodeNotifier;
382    typedef AlterationNotifier<UGraphExtender, Edge> EdgeNotifier;
383    typedef AlterationNotifier<UGraphExtender, UEdge> UEdgeNotifier;
384
385
386  protected:
387
388    mutable NodeNotifier node_notifier;
389    mutable EdgeNotifier edge_notifier;
390    mutable UEdgeNotifier uedge_notifier;
391
392  public:
393
394    NodeNotifier& getNotifier(Node) const {
395      return node_notifier;
396    }
397   
398    EdgeNotifier& getNotifier(Edge) const {
399      return edge_notifier;
400    }
401
402    UEdgeNotifier& getNotifier(UEdge) const {
403      return uedge_notifier;
404    }
405
406
407
408    class NodeIt : public Node {
409      const Graph* graph;
410    public:
411
412      NodeIt() {}
413
414      NodeIt(Invalid i) : Node(i) { }
415
416      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
417        _graph.first(static_cast<Node&>(*this));
418      }
419
420      NodeIt(const Graph& _graph, const Node& node)
421        : Node(node), graph(&_graph) {}
422
423      NodeIt& operator++() {
424        graph->next(*this);
425        return *this;
426      }
427
428    };
429
430
431    class EdgeIt : public Edge {
432      const Graph* graph;
433    public:
434
435      EdgeIt() { }
436
437      EdgeIt(Invalid i) : Edge(i) { }
438
439      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
440        _graph.first(static_cast<Edge&>(*this));
441      }
442
443      EdgeIt(const Graph& _graph, const Edge& e) :
444        Edge(e), graph(&_graph) { }
445
446      EdgeIt& operator++() {
447        graph->next(*this);
448        return *this;
449      }
450
451    };
452
453
454    class OutEdgeIt : public Edge {
455      const Graph* graph;
456    public:
457
458      OutEdgeIt() { }
459
460      OutEdgeIt(Invalid i) : Edge(i) { }
461
462      OutEdgeIt(const Graph& _graph, const Node& node)
463        : graph(&_graph) {
464        _graph.firstOut(*this, node);
465      }
466
467      OutEdgeIt(const Graph& _graph, const Edge& edge)
468        : Edge(edge), graph(&_graph) {}
469
470      OutEdgeIt& operator++() {
471        graph->nextOut(*this);
472        return *this;
473      }
474
475    };
476
477
478    class InEdgeIt : public Edge {
479      const Graph* graph;
480    public:
481
482      InEdgeIt() { }
483
484      InEdgeIt(Invalid i) : Edge(i) { }
485
486      InEdgeIt(const Graph& _graph, const Node& node)
487        : graph(&_graph) {
488        _graph.firstIn(*this, node);
489      }
490
491      InEdgeIt(const Graph& _graph, const Edge& edge) :
492        Edge(edge), graph(&_graph) {}
493
494      InEdgeIt& operator++() {
495        graph->nextIn(*this);
496        return *this;
497      }
498
499    };
500
501
502    class UEdgeIt : public Parent::UEdge {
503      const Graph* graph;
504    public:
505
506      UEdgeIt() { }
507
508      UEdgeIt(Invalid i) : UEdge(i) { }
509
510      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
511        _graph.first(static_cast<UEdge&>(*this));
512      }
513
514      UEdgeIt(const Graph& _graph, const UEdge& e) :
515        UEdge(e), graph(&_graph) { }
516
517      UEdgeIt& operator++() {
518        graph->next(*this);
519        return *this;
520      }
521
522    };
523
524    class IncEdgeIt : public Parent::UEdge {
525      friend class UGraphExtender;
526      const Graph* graph;
527      bool direction;
528    public:
529
530      IncEdgeIt() { }
531
532      IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
533
534      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
535        _graph.firstInc(*this, direction, n);
536      }
537
538      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
539        : graph(&_graph), UEdge(ue) {
540        direction = (_graph.source(ue) == n);
541      }
542
543      IncEdgeIt& operator++() {
544        graph->nextInc(*this, direction);
545        return *this;
546      }
547    };
548
549    /// \brief Base node of the iterator
550    ///
551    /// Returns the base node (ie. the source in this case) of the iterator
552    Node baseNode(const OutEdgeIt &e) const {
553      return Parent::source((Edge)e);
554    }
555    /// \brief Running node of the iterator
556    ///
557    /// Returns the running node (ie. the target in this case) of the
558    /// iterator
559    Node runningNode(const OutEdgeIt &e) const {
560      return Parent::target((Edge)e);
561    }
562
563    /// \brief Base node of the iterator
564    ///
565    /// Returns the base node (ie. the target in this case) of the iterator
566    Node baseNode(const InEdgeIt &e) const {
567      return Parent::target((Edge)e);
568    }
569    /// \brief Running node of the iterator
570    ///
571    /// Returns the running node (ie. the source in this case) of the
572    /// iterator
573    Node runningNode(const InEdgeIt &e) const {
574      return Parent::source((Edge)e);
575    }
576
577    /// Base node of the iterator
578    ///
579    /// Returns the base node of the iterator
580    Node baseNode(const IncEdgeIt &e) const {
581      return e.direction ? source(e) : target(e);
582    }
583    /// Running node of the iterator
584    ///
585    /// Returns the running node of the iterator
586    Node runningNode(const IncEdgeIt &e) const {
587      return e.direction ? target(e) : source(e);
588    }
589
590    // Mappable extension
591
592    template <typename _Value>
593    class NodeMap
594      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
595    public:
596      typedef UGraphExtender Graph;
597      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
598
599      NodeMap(const Graph& graph)
600        : Parent(graph) {}
601      NodeMap(const Graph& graph, const _Value& value)
602        : Parent(graph, value) {}
603
604      NodeMap& operator=(const NodeMap& cmap) {
605        return operator=<NodeMap>(cmap);
606      }
607
608      template <typename CMap>
609      NodeMap& operator=(const CMap& cmap) {
610        Parent::operator=(cmap);
611        return *this;
612      }
613
614    };
615
616    template <typename _Value>
617    class EdgeMap
618      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
619    public:
620      typedef UGraphExtender Graph;
621      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
622
623      EdgeMap(const Graph& graph)
624        : Parent(graph) {}
625      EdgeMap(const Graph& graph, const _Value& value)
626        : Parent(graph, value) {}
627
628      EdgeMap& operator=(const EdgeMap& cmap) {
629        return operator=<EdgeMap>(cmap);
630      }
631
632      template <typename CMap>
633      EdgeMap& operator=(const CMap& cmap) {
634        Parent::operator=(cmap);
635        return *this;
636      }
637    };
638
639
640    template <typename _Value>
641    class UEdgeMap
642      : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
643    public:
644      typedef UGraphExtender Graph;
645      typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
646
647      UEdgeMap(const Graph& graph)
648        : Parent(graph) {}
649
650      UEdgeMap(const Graph& graph, const _Value& value)
651        : Parent(graph, value) {}
652
653      UEdgeMap& operator=(const UEdgeMap& cmap) {
654        return operator=<UEdgeMap>(cmap);
655      }
656
657      template <typename CMap>
658      UEdgeMap& operator=(const CMap& cmap) {
659        Parent::operator=(cmap);
660        return *this;
661      }
662
663    };
664
665    // Alteration extension
666
667    Node addNode() {
668      Node node = Parent::addNode();
669      getNotifier(Node()).add(node);
670      return node;
671    }
672
673    UEdge addEdge(const Node& from, const Node& to) {
674      UEdge uedge = Parent::addEdge(from, to);
675      getNotifier(UEdge()).add(uedge);
676      getNotifier(Edge()).add(Parent::direct(uedge, true));
677      getNotifier(Edge()).add(Parent::direct(uedge, false));
678      return uedge;
679    }
680   
681    void clear() {
682      getNotifier(Edge()).clear();
683      getNotifier(UEdge()).clear();
684      getNotifier(Node()).clear();
685      Parent::clear();
686    }
687
688    void erase(const Node& node) {
689      Edge edge;
690      Parent::firstOut(edge, node);
691      while (edge != INVALID ) {
692        erase(edge);
693        Parent::firstOut(edge, node);
694      }
695
696      Parent::firstIn(edge, node);
697      while (edge != INVALID ) {
698        erase(edge);
699        Parent::firstIn(edge, node);
700      }
701
702      getNotifier(Node()).erase(node);
703      Parent::erase(node);
704    }
705
706    void erase(const UEdge& uedge) {
707      getNotifier(Edge()).erase(Parent::direct(uedge, true));
708      getNotifier(Edge()).erase(Parent::direct(uedge, false));
709      getNotifier(UEdge()).erase(uedge);
710      Parent::erase(uedge);
711    }
712
713    UGraphExtender() {
714      node_notifier.setContainer(*this);
715      edge_notifier.setContainer(*this);
716      uedge_notifier.setContainer(*this);
717    }
718
719    ~UGraphExtender() {
720      uedge_notifier.clear();
721      edge_notifier.clear();
722      node_notifier.clear();
723    }
724
725  };
726
727  /// \ingroup graphbits
728  ///
729  /// \brief Extender for the BpUGraphs
730  template <typename Base>
731  class BpUGraphExtender : public Base {
732  public:
733    typedef Base Parent;
734    typedef BpUGraphExtender Graph;
735
736    typedef typename Parent::Node Node;
737    typedef typename Parent::BNode BNode;
738    typedef typename Parent::ANode ANode;
739    typedef typename Parent::Edge Edge;
740    typedef typename Parent::UEdge UEdge;
741
742    Node oppositeNode(const UEdge& edge, const Node& node) const {
743      return source(edge) == node ?
744        target(edge) : source(edge);
745    }
746
747    using Parent::direct;
748    Edge direct(const UEdge& edge, const Node& node) const {
749      return Edge(edge, node == Parent::source(edge));
750    }
751
752    Edge oppositeEdge(const Edge& edge) const {
753      return Parent::direct(edge, !Parent::direction(edge));
754    }
755
756
757    int maxId(Node) const {
758      return Parent::maxNodeId();
759    }
760    int maxId(BNode) const {
761      return Parent::maxBNodeId();
762    }
763    int maxId(ANode) const {
764      return Parent::maxANodeId();
765    }
766    int maxId(Edge) const {
767      return Parent::maxEdgeId();
768    }
769    int maxId(UEdge) const {
770      return Parent::maxUEdgeId();
771    }
772
773
774    Node fromId(int id, Node) const {
775      return Parent::nodeFromId(id);
776    }
777    ANode fromId(int id, ANode) const {
778      return Parent::fromANodeId(id);
779    }
780    BNode fromId(int id, BNode) const {
781      return Parent::fromBNodeId(id);
782    }
783    Edge fromId(int id, Edge) const {
784      return Parent::edgeFromId(id);
785    }
786    UEdge fromId(int id, UEdge) const {
787      return Parent::uEdgeFromId(id);
788    } 
789 
790    typedef AlterationNotifier<BpUGraphExtender, ANode> ANodeNotifier;
791    typedef AlterationNotifier<BpUGraphExtender, BNode> BNodeNotifier;
792    typedef AlterationNotifier<BpUGraphExtender, Node> NodeNotifier;
793    typedef AlterationNotifier<BpUGraphExtender, Edge> EdgeNotifier;
794    typedef AlterationNotifier<BpUGraphExtender, UEdge> UEdgeNotifier;
795
796  protected:
797
798    mutable ANodeNotifier anode_notifier;
799    mutable BNodeNotifier bnode_notifier;
800    mutable NodeNotifier node_notifier;
801    mutable EdgeNotifier edge_notifier;
802    mutable UEdgeNotifier uedge_notifier;
803
804  public:
805
806    NodeNotifier& getNotifier(Node) const {
807      return node_notifier;
808    }
809
810    ANodeNotifier& getNotifier(ANode) const {
811      return anode_notifier;
812    }
813
814    BNodeNotifier& getNotifier(BNode) const {
815      return bnode_notifier;
816    }
817
818    EdgeNotifier& getNotifier(Edge) const {
819      return edge_notifier;
820    }
821
822    UEdgeNotifier& getNotifier(UEdge) const {
823      return uedge_notifier;
824    }
825
826    class NodeIt : public Node {
827      const Graph* graph;
828    public:
829   
830      NodeIt() { }
831   
832      NodeIt(Invalid i) : Node(INVALID) { }
833   
834      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
835        graph->first(static_cast<Node&>(*this));
836      }
837
838      NodeIt(const Graph& _graph, const Node& node)
839        : Node(node), graph(&_graph) { }
840   
841      NodeIt& operator++() {
842        graph->next(*this);
843        return *this;
844      }
845
846    };
847
848    class ANodeIt : public Node {
849      friend class BpUGraphExtender;
850      const Graph* graph;
851    public:
852   
853      ANodeIt() { }
854   
855      ANodeIt(Invalid i) : Node(INVALID) { }
856   
857      explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
858        graph->firstANode(static_cast<Node&>(*this));
859      }
860
861      ANodeIt(const Graph& _graph, const Node& node)
862        : Node(node), graph(&_graph) {}
863   
864      ANodeIt& operator++() {
865        graph->nextANode(*this);
866        return *this;
867      }
868    };
869
870    class BNodeIt : public Node {
871      friend class BpUGraphExtender;
872      const Graph* graph;
873    public:
874   
875      BNodeIt() { }
876   
877      BNodeIt(Invalid i) : Node(INVALID) { }
878   
879      explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
880        graph->firstBNode(static_cast<Node&>(*this));
881      }
882
883      BNodeIt(const Graph& _graph, const Node& node)
884        : Node(node), graph(&_graph) {}
885   
886      BNodeIt& operator++() {
887        graph->nextBNode(*this);
888        return *this;
889      }
890    };
891
892    class EdgeIt : public Edge {
893      friend class BpUGraphExtender;
894      const Graph* graph;
895    public:
896   
897      EdgeIt() { }
898   
899      EdgeIt(Invalid i) : Edge(INVALID) { }
900   
901      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
902        graph->first(static_cast<Edge&>(*this));
903      }
904
905      EdgeIt(const Graph& _graph, const Edge& edge)
906        : Edge(edge), graph(&_graph) { }
907   
908      EdgeIt& operator++() {
909        graph->next(*this);
910        return *this;
911      }
912
913    };
914
915    class UEdgeIt : public UEdge {
916      friend class BpUGraphExtender;
917      const Graph* graph;
918    public:
919   
920      UEdgeIt() { }
921   
922      UEdgeIt(Invalid i) : UEdge(INVALID) { }
923   
924      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
925        graph->first(static_cast<UEdge&>(*this));
926      }
927
928      UEdgeIt(const Graph& _graph, const UEdge& edge)
929        : UEdge(edge), graph(&_graph) { }
930   
931      UEdgeIt& operator++() {
932        graph->next(*this);
933        return *this;
934      }
935    };
936
937    class OutEdgeIt : public Edge {
938      friend class BpUGraphExtender;
939      const Graph* graph;
940    public:
941   
942      OutEdgeIt() { }
943   
944      OutEdgeIt(Invalid i) : Edge(i) { }
945   
946      OutEdgeIt(const Graph& _graph, const Node& node)
947        : graph(&_graph) {
948        graph->firstOut(*this, node);
949      }
950   
951      OutEdgeIt(const Graph& _graph, const Edge& edge)
952        : Edge(edge), graph(&_graph) {}
953   
954      OutEdgeIt& operator++() {
955        graph->nextOut(*this);
956        return *this;
957      }
958
959    };
960
961
962    class InEdgeIt : public Edge {
963      friend class BpUGraphExtender;
964      const Graph* graph;
965    public:
966   
967      InEdgeIt() { }
968   
969      InEdgeIt(Invalid i) : Edge(i) { }
970   
971      InEdgeIt(const Graph& _graph, const Node& node)
972        : graph(&_graph) {
973        graph->firstIn(*this, node);
974      }
975   
976      InEdgeIt(const Graph& _graph, const Edge& edge) :
977        Edge(edge), graph(&_graph) {}
978   
979      InEdgeIt& operator++() {
980        graph->nextIn(*this);
981        return *this;
982      }
983
984    };
985 
986    /// \brief Base node of the iterator
987    ///
988    /// Returns the base node (ie. the source in this case) of the iterator
989    Node baseNode(const OutEdgeIt &e) const {
990      return Parent::source((Edge&)e);
991    }
992    /// \brief Running node of the iterator
993    ///
994    /// Returns the running node (ie. the target in this case) of the
995    /// iterator
996    Node runningNode(const OutEdgeIt &e) const {
997      return Parent::target((Edge&)e);
998    }
999 
1000    /// \brief Base node of the iterator
1001    ///
1002    /// Returns the base node (ie. the target in this case) of the iterator
1003    Node baseNode(const InEdgeIt &e) const {
1004      return Parent::target((Edge&)e);
1005    }
1006    /// \brief Running node of the iterator
1007    ///
1008    /// Returns the running node (ie. the source in this case) of the
1009    /// iterator
1010    Node runningNode(const InEdgeIt &e) const {
1011      return Parent::source((Edge&)e);
1012    }
1013 
1014    class IncEdgeIt : public Parent::UEdge {
1015      friend class BpUGraphExtender;
1016      const Graph* graph;
1017      bool direction;
1018    public:
1019   
1020      IncEdgeIt() { }
1021   
1022      IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
1023   
1024      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
1025        graph->firstInc(*this, direction, n);
1026      }
1027
1028      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
1029        : graph(&_graph), UEdge(ue) {
1030        direction = (graph->source(ue) == n);
1031      }
1032
1033      IncEdgeIt& operator++() {
1034        graph->nextInc(*this, direction);
1035        return *this;
1036      }
1037    };
1038 
1039
1040    /// Base node of the iterator
1041    ///
1042    /// Returns the base node of the iterator
1043    Node baseNode(const IncEdgeIt &e) const {
1044      return e.direction ? source(e) : target(e);
1045    }
1046
1047    /// Running node of the iterator
1048    ///
1049    /// Returns the running node of the iterator
1050    Node runningNode(const IncEdgeIt &e) const {
1051      return e.direction ? target(e) : source(e);
1052    }
1053
1054    template <typename _Value>
1055    class ANodeMap
1056      : public MapExtender<DefaultMap<Graph, ANode, _Value> > {
1057    public:
1058      typedef BpUGraphExtender Graph;
1059      typedef MapExtender<DefaultMap<Graph, ANode, _Value> > Parent;
1060   
1061      ANodeMap(const Graph& graph)
1062        : Parent(graph) {}
1063      ANodeMap(const Graph& graph, const _Value& value)
1064        : Parent(graph, value) {}
1065   
1066      ANodeMap& operator=(const ANodeMap& cmap) {
1067        return operator=<ANodeMap>(cmap);
1068      }
1069   
1070      template <typename CMap>
1071      ANodeMap& operator=(const CMap& cmap) {
1072        Parent::operator=(cmap);
1073        return *this;
1074      }
1075   
1076    };
1077
1078    template <typename _Value>
1079    class BNodeMap
1080      : public MapExtender<DefaultMap<Graph, BNode, _Value> > {
1081    public:
1082      typedef BpUGraphExtender Graph;
1083      typedef MapExtender<DefaultMap<Graph, BNode, _Value> > Parent;
1084   
1085      BNodeMap(const Graph& graph)
1086        : Parent(graph) {}
1087      BNodeMap(const Graph& graph, const _Value& value)
1088        : Parent(graph, value) {}
1089   
1090      BNodeMap& operator=(const BNodeMap& cmap) {
1091        return operator=<BNodeMap>(cmap);
1092      }
1093   
1094      template <typename CMap>
1095      BNodeMap& operator=(const CMap& cmap) {
1096        Parent::operator=(cmap);
1097        return *this;
1098      }
1099   
1100    };
1101
1102  public:
1103
1104    template <typename _Value>
1105    class NodeMap {
1106    public:
1107      typedef BpUGraphExtender Graph;
1108
1109      typedef Node Key;
1110      typedef _Value Value;
1111
1112      /// The reference type of the map;
1113      typedef typename ANodeMap<_Value>::Reference Reference;
1114      /// The const reference type of the map;
1115      typedef typename ANodeMap<_Value>::ConstReference ConstReference;
1116
1117      typedef True ReferenceMapTag;
1118
1119      NodeMap(const Graph& _graph)
1120        : graph(_graph), aNodeMap(_graph), bNodeMap(_graph) {}
1121      NodeMap(const Graph& _graph, const _Value& _value)
1122        : graph(_graph), aNodeMap(_graph, _value), bNodeMap(_graph, _value) {}
1123
1124      NodeMap& operator=(const NodeMap& cmap) {
1125        return operator=<NodeMap>(cmap);
1126      }
1127   
1128      template <typename CMap>
1129      NodeMap& operator=(const CMap& cmap) {
1130        checkConcept<concept::ReadMap<Node, _Value>, CMap>();
1131        const typename Parent::Notifier* notifier = Parent::getNotifier();
1132        Edge it;
1133        for (graph.first(it); it != INVALID; graph.next(it)) {
1134          Parent::set(it, cmap[it]);
1135        }
1136        return *this;
1137      }
1138
1139      ConstReference operator[](const Key& node) const {
1140        if (Parent::aNode(node)) {
1141          return aNodeMap[node];
1142        } else {
1143          return bNodeMap[node];
1144        }
1145      }
1146
1147      Reference operator[](const Key& node) {
1148        if (Parent::aNode(node)) {
1149          return aNodeMap[node];
1150        } else {
1151          return bNodeMap[node];
1152        }
1153      }
1154
1155      void set(const Key& node, const Value& value) {
1156        if (Parent::aNode(node)) {
1157          aNodeMap.set(node, value);
1158        } else {
1159          bNodeMap.set(node, value);
1160        }
1161      }
1162
1163      class MapIt : public NodeIt {
1164      public:
1165
1166        typedef NodeIt Parent;
1167       
1168        explicit MapIt(NodeMap& _map)
1169          : Parent(_map.graph), map(_map) {}
1170       
1171        typename MapTraits<NodeMap>::ConstReturnValue operator*() const {
1172          return map[*this];
1173        }
1174       
1175        typename MapTraits<NodeMap>::ReturnValue operator*() {
1176          return map[*this];
1177        }
1178       
1179        void set(const Value& value) {
1180          map.set(*this, value);
1181        }
1182
1183      private:
1184        NodeMap& map;
1185      };
1186
1187      class ConstMapIt : public NodeIt {
1188      public:
1189
1190        typedef NodeIt Parent;
1191       
1192        explicit ConstMapIt(const NodeMap& _map)
1193          : Parent(_map.graph), map(_map) {}
1194       
1195        typename MapTraits<NodeMap>::ConstReturnValue operator*() const {
1196          return map[*this];
1197        }
1198       
1199      private:
1200        const NodeMap& map;
1201      };
1202
1203      class ItemIt : public NodeIt {
1204      public:
1205
1206        typedef NodeIt Parent;
1207
1208        explicit ItemIt(const NodeMap& _map)
1209          : Parent(_map.graph) {}
1210       
1211      };
1212     
1213    private:
1214      const Graph& graph;
1215      ANodeMap<_Value> aNodeMap;
1216      BNodeMap<_Value> bNodeMap;
1217    };
1218   
1219
1220    template <typename _Value>
1221    class EdgeMap
1222      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
1223    public:
1224      typedef BpUGraphExtender Graph;
1225      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
1226   
1227      EdgeMap(const Graph& graph)
1228        : Parent(graph) {}
1229      EdgeMap(const Graph& graph, const _Value& value)
1230        : Parent(graph, value) {}
1231   
1232      EdgeMap& operator=(const EdgeMap& cmap) {
1233        return operator=<EdgeMap>(cmap);
1234      }
1235   
1236      template <typename CMap>
1237      EdgeMap& operator=(const CMap& cmap) {
1238        Parent::operator=(cmap);
1239        return *this;
1240      }
1241    };
1242
1243    template <typename _Value>
1244    class UEdgeMap
1245      : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
1246    public:
1247      typedef BpUGraphExtender Graph;
1248      typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
1249   
1250      UEdgeMap(const Graph& graph)
1251        : Parent(graph) {}
1252      UEdgeMap(const Graph& graph, const _Value& value)
1253        : Parent(graph, value) {}
1254   
1255      UEdgeMap& operator=(const UEdgeMap& cmap) {
1256        return operator=<UEdgeMap>(cmap);
1257      }
1258   
1259      template <typename CMap>
1260      UEdgeMap& operator=(const CMap& cmap) {
1261        Parent::operator=(cmap);
1262        return *this;
1263      }
1264    };
1265
1266 
1267    Node addANode() {
1268      Node node = Parent::addANode();
1269      getNotifier(ANode()).add(node);
1270      getNotifier(Node()).add(node);
1271      return node;
1272    }
1273
1274    Node addBNode() {
1275      Node node = Parent::addBNode();
1276      getNotifier(BNode()).add(node);
1277      getNotifier(Node()).add(node);
1278      return node;
1279    }
1280 
1281    UEdge addEdge(const Node& source, const Node& target) {
1282      UEdge uedge = Parent::addEdge(source, target);
1283      getNotifier(UEdge()).add(uedge);
1284   
1285      std::vector<Edge> edges;
1286      edges.push_back(direct(uedge, true));
1287      edges.push_back(direct(uedge, false));
1288      getNotifier(Edge()).add(edges);
1289   
1290      return uedge;
1291    }
1292
1293    void clear() {
1294      getNotifier(Edge()).clear();
1295      getNotifier(UEdge()).clear();
1296      getNotifier(Node()).clear();
1297      getNotifier(BNode()).clear();
1298      getNotifier(ANode()).clear();
1299      Parent::clear();
1300    }
1301
1302    void erase(const Node& node) {
1303      UEdge uedge;
1304      bool dir;
1305      Parent::firstInc(uedge, dir, node);
1306      while (uedge != INVALID ) {
1307        erase(uedge);
1308        Parent::firstInc(uedge, dir, node);
1309      }
1310
1311      getNotifier(Node()).erase(node);
1312      Parent::erase(node);
1313    }
1314   
1315    void erase(const UEdge& uedge) {
1316      std::vector<Edge> edges;
1317      edges.push_back(direct(uedge, true));
1318      edges.push_back(direct(uedge, false));
1319      getNotifier(Edge()).erase(edges);
1320      getNotifier(UEdge()).erase(uedge);
1321      Parent::erase(uedge);
1322    }
1323
1324
1325    BpUGraphExtender() {
1326      anode_notifier.setContainer(*this);
1327      bnode_notifier.setContainer(*this);
1328      node_notifier.setContainer(*this);
1329      edge_notifier.setContainer(*this);
1330      uedge_notifier.setContainer(*this);
1331    }
1332
1333    ~BpUGraphExtender() {
1334      uedge_notifier.clear();
1335      edge_notifier.clear();
1336      node_notifier.clear();
1337      anode_notifier.clear();
1338      bnode_notifier.clear();
1339    }
1340
1341
1342  };
1343
1344}
1345
1346#endif
Note: See TracBrowser for help on using the repository browser.