COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/graph_extender.h @ 2031:080d51024ac5

Last change on this file since 2031:080d51024ac5 was 2031:080d51024ac5, checked in by Balazs Dezso, 13 years ago

Correcting the structure of the graph's and adaptor's map.
The template assign operators and map iterators can be used for adaptors also.

Some bugfix in the adaptors

New class SwapBpUGraphAdaptor which swaps the two nodeset of the graph.

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      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      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.