COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/graph_extender.h @ 2290:f30867b359a8

Last change on this file since 2290:f30867b359a8 was 2290:f30867b359a8, checked in by Balazs Dezso, 13 years ago

GraphCopy? and UGraphCopy modifications
Preliminary support for static graphs

=> cloning graphs

Added BpUGraphCopy

Tests for graph copies

File size: 32.3 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/concepts/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 (i.e. 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 (i.e. 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 (i.e. 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 (i.e. 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    template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
286    void clone(const Graph& graph, NodeRefMap& nodeRef, EdgeRefMap& edgeRef) {
287      Parent::clone(graph, nodeRef, edgeRef);
288      getNotifier(Node()).build();
289      getNotifier(Edge()).build();
290    }
291
292    void erase(const Node& node) {
293      Edge edge;
294      Parent::firstOut(edge, node);
295      while (edge != INVALID ) {
296        erase(edge);
297        Parent::firstOut(edge, node);
298      }
299
300      Parent::firstIn(edge, node);
301      while (edge != INVALID ) {
302        erase(edge);
303        Parent::firstIn(edge, node);
304      }
305
306      getNotifier(Node()).erase(node);
307      Parent::erase(node);
308    }
309   
310    void erase(const Edge& edge) {
311      getNotifier(Edge()).erase(edge);
312      Parent::erase(edge);
313    }
314
315    GraphExtender() {
316      node_notifier.setContainer(*this);
317      edge_notifier.setContainer(*this);
318    }
319   
320
321    ~GraphExtender() {
322      edge_notifier.clear();
323      node_notifier.clear();
324    }
325  };
326
327  /// \ingroup graphbits
328  ///
329  /// \brief Extender for the UGraphs
330  template <typename Base>
331  class UGraphExtender : public Base {
332  public:
333   
334    typedef Base Parent;
335    typedef UGraphExtender Graph;
336
337    typedef typename Parent::Node Node;
338    typedef typename Parent::Edge Edge;
339    typedef typename Parent::UEdge UEdge;
340
341    // UGraph extension   
342
343    int maxId(Node) const {
344      return Parent::maxNodeId();
345    }
346
347    int maxId(Edge) const {
348      return Parent::maxEdgeId();
349    }
350
351    int maxId(UEdge) const {
352      return Parent::maxUEdgeId();
353    }
354
355    Node fromId(int id, Node) const {
356      return Parent::nodeFromId(id);
357    }
358
359    Edge fromId(int id, Edge) const {
360      return Parent::edgeFromId(id);
361    }
362
363    UEdge fromId(int id, UEdge) const {
364      return Parent::uEdgeFromId(id);
365    }
366
367    Node oppositeNode(const Node &n, const UEdge &e) const {
368      if( n == Parent::source(e))
369        return Parent::target(e);
370      else if( n == Parent::target(e))
371        return Parent::source(e);
372      else
373        return INVALID;
374    }
375
376    Edge oppositeEdge(const Edge &e) const {
377      return Parent::direct(e, !Parent::direction(e));
378    }
379
380    using Parent::direct;
381    Edge direct(const UEdge &ue, const Node &s) const {
382      return Parent::direct(ue, Parent::source(ue) == s);
383    }
384
385    // Alterable extension
386
387    typedef AlterationNotifier<UGraphExtender, Node> NodeNotifier;
388    typedef AlterationNotifier<UGraphExtender, Edge> EdgeNotifier;
389    typedef AlterationNotifier<UGraphExtender, UEdge> UEdgeNotifier;
390
391
392  protected:
393
394    mutable NodeNotifier node_notifier;
395    mutable EdgeNotifier edge_notifier;
396    mutable UEdgeNotifier uedge_notifier;
397
398  public:
399
400    NodeNotifier& getNotifier(Node) const {
401      return node_notifier;
402    }
403   
404    EdgeNotifier& getNotifier(Edge) const {
405      return edge_notifier;
406    }
407
408    UEdgeNotifier& getNotifier(UEdge) const {
409      return uedge_notifier;
410    }
411
412
413
414    class NodeIt : public Node {
415      const Graph* graph;
416    public:
417
418      NodeIt() {}
419
420      NodeIt(Invalid i) : Node(i) { }
421
422      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
423        _graph.first(static_cast<Node&>(*this));
424      }
425
426      NodeIt(const Graph& _graph, const Node& node)
427        : Node(node), graph(&_graph) {}
428
429      NodeIt& operator++() {
430        graph->next(*this);
431        return *this;
432      }
433
434    };
435
436
437    class EdgeIt : public Edge {
438      const Graph* graph;
439    public:
440
441      EdgeIt() { }
442
443      EdgeIt(Invalid i) : Edge(i) { }
444
445      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
446        _graph.first(static_cast<Edge&>(*this));
447      }
448
449      EdgeIt(const Graph& _graph, const Edge& e) :
450        Edge(e), graph(&_graph) { }
451
452      EdgeIt& operator++() {
453        graph->next(*this);
454        return *this;
455      }
456
457    };
458
459
460    class OutEdgeIt : public Edge {
461      const Graph* graph;
462    public:
463
464      OutEdgeIt() { }
465
466      OutEdgeIt(Invalid i) : Edge(i) { }
467
468      OutEdgeIt(const Graph& _graph, const Node& node)
469        : graph(&_graph) {
470        _graph.firstOut(*this, node);
471      }
472
473      OutEdgeIt(const Graph& _graph, const Edge& edge)
474        : Edge(edge), graph(&_graph) {}
475
476      OutEdgeIt& operator++() {
477        graph->nextOut(*this);
478        return *this;
479      }
480
481    };
482
483
484    class InEdgeIt : public Edge {
485      const Graph* graph;
486    public:
487
488      InEdgeIt() { }
489
490      InEdgeIt(Invalid i) : Edge(i) { }
491
492      InEdgeIt(const Graph& _graph, const Node& node)
493        : graph(&_graph) {
494        _graph.firstIn(*this, node);
495      }
496
497      InEdgeIt(const Graph& _graph, const Edge& edge) :
498        Edge(edge), graph(&_graph) {}
499
500      InEdgeIt& operator++() {
501        graph->nextIn(*this);
502        return *this;
503      }
504
505    };
506
507
508    class UEdgeIt : public Parent::UEdge {
509      const Graph* graph;
510    public:
511
512      UEdgeIt() { }
513
514      UEdgeIt(Invalid i) : UEdge(i) { }
515
516      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
517        _graph.first(static_cast<UEdge&>(*this));
518      }
519
520      UEdgeIt(const Graph& _graph, const UEdge& e) :
521        UEdge(e), graph(&_graph) { }
522
523      UEdgeIt& operator++() {
524        graph->next(*this);
525        return *this;
526      }
527
528    };
529
530    class IncEdgeIt : public Parent::UEdge {
531      friend class UGraphExtender;
532      const Graph* graph;
533      bool direction;
534    public:
535
536      IncEdgeIt() { }
537
538      IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
539
540      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
541        _graph.firstInc(*this, direction, n);
542      }
543
544      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
545        : graph(&_graph), UEdge(ue) {
546        direction = (_graph.source(ue) == n);
547      }
548
549      IncEdgeIt& operator++() {
550        graph->nextInc(*this, direction);
551        return *this;
552      }
553    };
554
555    /// \brief Base node of the iterator
556    ///
557    /// Returns the base node (ie. the source in this case) of the iterator
558    Node baseNode(const OutEdgeIt &e) const {
559      return Parent::source((Edge)e);
560    }
561    /// \brief Running node of the iterator
562    ///
563    /// Returns the running node (ie. the target in this case) of the
564    /// iterator
565    Node runningNode(const OutEdgeIt &e) const {
566      return Parent::target((Edge)e);
567    }
568
569    /// \brief Base node of the iterator
570    ///
571    /// Returns the base node (ie. the target in this case) of the iterator
572    Node baseNode(const InEdgeIt &e) const {
573      return Parent::target((Edge)e);
574    }
575    /// \brief Running node of the iterator
576    ///
577    /// Returns the running node (ie. the source in this case) of the
578    /// iterator
579    Node runningNode(const InEdgeIt &e) const {
580      return Parent::source((Edge)e);
581    }
582
583    /// Base node of the iterator
584    ///
585    /// Returns the base node of the iterator
586    Node baseNode(const IncEdgeIt &e) const {
587      return e.direction ? source(e) : target(e);
588    }
589    /// Running node of the iterator
590    ///
591    /// Returns the running node of the iterator
592    Node runningNode(const IncEdgeIt &e) const {
593      return e.direction ? target(e) : source(e);
594    }
595
596    // Mappable extension
597
598    template <typename _Value>
599    class NodeMap
600      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
601    public:
602      typedef UGraphExtender Graph;
603      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
604
605      NodeMap(const Graph& graph)
606        : Parent(graph) {}
607      NodeMap(const Graph& graph, const _Value& value)
608        : Parent(graph, value) {}
609
610      NodeMap& operator=(const NodeMap& cmap) {
611        return operator=<NodeMap>(cmap);
612      }
613
614      template <typename CMap>
615      NodeMap& operator=(const CMap& cmap) {
616        Parent::operator=(cmap);
617        return *this;
618      }
619
620    };
621
622    template <typename _Value>
623    class EdgeMap
624      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
625    public:
626      typedef UGraphExtender Graph;
627      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
628
629      EdgeMap(const Graph& graph)
630        : Parent(graph) {}
631      EdgeMap(const Graph& graph, const _Value& value)
632        : Parent(graph, value) {}
633
634      EdgeMap& operator=(const EdgeMap& cmap) {
635        return operator=<EdgeMap>(cmap);
636      }
637
638      template <typename CMap>
639      EdgeMap& operator=(const CMap& cmap) {
640        Parent::operator=(cmap);
641        return *this;
642      }
643    };
644
645
646    template <typename _Value>
647    class UEdgeMap
648      : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
649    public:
650      typedef UGraphExtender Graph;
651      typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
652
653      UEdgeMap(const Graph& graph)
654        : Parent(graph) {}
655
656      UEdgeMap(const Graph& graph, const _Value& value)
657        : Parent(graph, value) {}
658
659      UEdgeMap& operator=(const UEdgeMap& cmap) {
660        return operator=<UEdgeMap>(cmap);
661      }
662
663      template <typename CMap>
664      UEdgeMap& operator=(const CMap& cmap) {
665        Parent::operator=(cmap);
666        return *this;
667      }
668
669    };
670
671    // Alteration extension
672
673    Node addNode() {
674      Node node = Parent::addNode();
675      getNotifier(Node()).add(node);
676      return node;
677    }
678
679    UEdge addEdge(const Node& from, const Node& to) {
680      UEdge uedge = Parent::addEdge(from, to);
681      getNotifier(UEdge()).add(uedge);
682      std::vector<Edge> edges;
683      edges.push_back(Parent::direct(uedge, true));
684      edges.push_back(Parent::direct(uedge, false));     
685      getNotifier(Edge()).add(edges);
686      return uedge;
687    }
688   
689    void clear() {
690      getNotifier(Edge()).clear();
691      getNotifier(UEdge()).clear();
692      getNotifier(Node()).clear();
693      Parent::clear();
694    }
695
696    template <typename Graph, typename NodeRefMap, typename UEdgeRefMap>
697    void clone(const Graph& graph, NodeRefMap& nodeRef,
698               UEdgeRefMap& uEdgeRef) {
699      Parent::clone(graph, nodeRef, uEdgeRef);
700      getNotifier(Node()).build();
701      getNotifier(UEdge()).build();
702      getNotifier(Edge()).build();
703    }
704
705    void erase(const Node& node) {
706      Edge edge;
707      Parent::firstOut(edge, node);
708      while (edge != INVALID ) {
709        erase(edge);
710        Parent::firstOut(edge, node);
711      }
712
713      Parent::firstIn(edge, node);
714      while (edge != INVALID ) {
715        erase(edge);
716        Parent::firstIn(edge, node);
717      }
718
719      getNotifier(Node()).erase(node);
720      Parent::erase(node);
721    }
722
723    void erase(const UEdge& uedge) {
724      std::vector<Edge> edges;
725      edges.push_back(Parent::direct(uedge, true));
726      edges.push_back(Parent::direct(uedge, false));     
727      getNotifier(Edge()).erase(edges);
728      getNotifier(UEdge()).erase(uedge);
729      Parent::erase(uedge);
730    }
731
732    UGraphExtender() {
733      node_notifier.setContainer(*this);
734      edge_notifier.setContainer(*this);
735      uedge_notifier.setContainer(*this);
736    }
737
738    ~UGraphExtender() {
739      uedge_notifier.clear();
740      edge_notifier.clear();
741      node_notifier.clear();
742    }
743
744  };
745
746  /// \ingroup graphbits
747  ///
748  /// \brief Extender for the BpUGraphs
749  template <typename Base>
750  class BpUGraphExtender : public Base {
751  public:
752
753    typedef Base Parent;
754    typedef BpUGraphExtender Graph;
755
756    typedef typename Parent::Node Node;
757    typedef typename Parent::ANode ANode;
758    typedef typename Parent::BNode BNode;
759    typedef typename Parent::Edge Edge;
760    typedef typename Parent::UEdge UEdge;
761
762
763    Node oppositeNode(const Node& node, const UEdge& edge) const {
764      return Parent::aNode(edge) == node ?
765        Parent::bNode(edge) : Parent::aNode(edge);
766    }
767
768    using Parent::direct;
769    Edge direct(const UEdge& edge, const Node& node) const {
770      return Parent::direct(edge, node == Parent::source(edge));
771    }
772
773    Edge oppositeEdge(const Edge& edge) const {
774      return direct(edge, !Parent::direction(edge));
775    }
776   
777    int maxId(Node) const {
778      return Parent::maxNodeId();
779    }
780    int maxId(BNode) const {
781      return Parent::maxBNodeId();
782    }
783    int maxId(ANode) const {
784      return Parent::maxANodeId();
785    }
786    int maxId(Edge) const {
787      return Parent::maxEdgeId();
788    }
789    int maxId(UEdge) const {
790      return Parent::maxUEdgeId();
791    }
792
793
794    Node fromId(int id, Node) const {
795      return Parent::nodeFromId(id);
796    }
797    ANode fromId(int id, ANode) const {
798      return Parent::nodeFromANodeId(id);
799    }
800    BNode fromId(int id, BNode) const {
801      return Parent::nodeFromBNodeId(id);
802    }
803    Edge fromId(int id, Edge) const {
804      return Parent::edgeFromId(id);
805    }
806    UEdge fromId(int id, UEdge) const {
807      return Parent::uEdgeFromId(id);
808    } 
809 
810    typedef AlterationNotifier<BpUGraphExtender, ANode> ANodeNotifier;
811    typedef AlterationNotifier<BpUGraphExtender, BNode> BNodeNotifier;
812    typedef AlterationNotifier<BpUGraphExtender, Node> NodeNotifier;
813    typedef AlterationNotifier<BpUGraphExtender, Edge> EdgeNotifier;
814    typedef AlterationNotifier<BpUGraphExtender, UEdge> UEdgeNotifier;
815
816  protected:
817
818    mutable ANodeNotifier anode_notifier;
819    mutable BNodeNotifier bnode_notifier;
820    mutable NodeNotifier node_notifier;
821    mutable EdgeNotifier edge_notifier;
822    mutable UEdgeNotifier uedge_notifier;
823
824  public:
825
826    NodeNotifier& getNotifier(Node) const {
827      return node_notifier;
828    }
829
830    ANodeNotifier& getNotifier(ANode) const {
831      return anode_notifier;
832    }
833
834    BNodeNotifier& getNotifier(BNode) const {
835      return bnode_notifier;
836    }
837
838    EdgeNotifier& getNotifier(Edge) const {
839      return edge_notifier;
840    }
841
842    UEdgeNotifier& getNotifier(UEdge) const {
843      return uedge_notifier;
844    }
845
846    class NodeIt : public Node {
847      const Graph* graph;
848    public:
849   
850      NodeIt() { }
851   
852      NodeIt(Invalid i) : Node(INVALID) { }
853   
854      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
855        graph->first(static_cast<Node&>(*this));
856      }
857
858      NodeIt(const Graph& _graph, const Node& node)
859        : Node(node), graph(&_graph) { }
860   
861      NodeIt& operator++() {
862        graph->next(*this);
863        return *this;
864      }
865
866    };
867
868    class ANodeIt : public Node {
869      friend class BpUGraphExtender;
870      const Graph* graph;
871    public:
872   
873      ANodeIt() { }
874   
875      ANodeIt(Invalid i) : Node(INVALID) { }
876   
877      explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
878        graph->firstANode(static_cast<Node&>(*this));
879      }
880
881      ANodeIt(const Graph& _graph, const Node& node)
882        : Node(node), graph(&_graph) {}
883   
884      ANodeIt& operator++() {
885        graph->nextANode(*this);
886        return *this;
887      }
888    };
889
890    class BNodeIt : public Node {
891      friend class BpUGraphExtender;
892      const Graph* graph;
893    public:
894   
895      BNodeIt() { }
896   
897      BNodeIt(Invalid i) : Node(INVALID) { }
898   
899      explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
900        graph->firstBNode(static_cast<Node&>(*this));
901      }
902
903      BNodeIt(const Graph& _graph, const Node& node)
904        : Node(node), graph(&_graph) {}
905   
906      BNodeIt& operator++() {
907        graph->nextBNode(*this);
908        return *this;
909      }
910    };
911
912    class EdgeIt : public Edge {
913      friend class BpUGraphExtender;
914      const Graph* graph;
915    public:
916   
917      EdgeIt() { }
918   
919      EdgeIt(Invalid i) : Edge(INVALID) { }
920   
921      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
922        graph->first(static_cast<Edge&>(*this));
923      }
924
925      EdgeIt(const Graph& _graph, const Edge& edge)
926        : Edge(edge), graph(&_graph) { }
927   
928      EdgeIt& operator++() {
929        graph->next(*this);
930        return *this;
931      }
932
933    };
934
935    class UEdgeIt : public UEdge {
936      friend class BpUGraphExtender;
937      const Graph* graph;
938    public:
939   
940      UEdgeIt() { }
941   
942      UEdgeIt(Invalid i) : UEdge(INVALID) { }
943   
944      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
945        graph->first(static_cast<UEdge&>(*this));
946      }
947
948      UEdgeIt(const Graph& _graph, const UEdge& edge)
949        : UEdge(edge), graph(&_graph) { }
950   
951      UEdgeIt& operator++() {
952        graph->next(*this);
953        return *this;
954      }
955    };
956
957    class OutEdgeIt : public Edge {
958      friend class BpUGraphExtender;
959      const Graph* graph;
960    public:
961   
962      OutEdgeIt() { }
963   
964      OutEdgeIt(Invalid i) : Edge(i) { }
965   
966      OutEdgeIt(const Graph& _graph, const Node& node)
967        : graph(&_graph) {
968        graph->firstOut(*this, node);
969      }
970   
971      OutEdgeIt(const Graph& _graph, const Edge& edge)
972        : Edge(edge), graph(&_graph) {}
973   
974      OutEdgeIt& operator++() {
975        graph->nextOut(*this);
976        return *this;
977      }
978
979    };
980
981
982    class InEdgeIt : public Edge {
983      friend class BpUGraphExtender;
984      const Graph* graph;
985    public:
986   
987      InEdgeIt() { }
988   
989      InEdgeIt(Invalid i) : Edge(i) { }
990   
991      InEdgeIt(const Graph& _graph, const Node& node)
992        : graph(&_graph) {
993        graph->firstIn(*this, node);
994      }
995   
996      InEdgeIt(const Graph& _graph, const Edge& edge) :
997        Edge(edge), graph(&_graph) {}
998   
999      InEdgeIt& operator++() {
1000        graph->nextIn(*this);
1001        return *this;
1002      }
1003
1004    };
1005 
1006    /// \brief Base node of the iterator
1007    ///
1008    /// Returns the base node (ie. the source in this case) of the iterator
1009    Node baseNode(const OutEdgeIt &e) const {
1010      return Parent::source((Edge&)e);
1011    }
1012    /// \brief Running node of the iterator
1013    ///
1014    /// Returns the running node (ie. the target in this case) of the
1015    /// iterator
1016    Node runningNode(const OutEdgeIt &e) const {
1017      return Parent::target((Edge&)e);
1018    }
1019 
1020    /// \brief Base node of the iterator
1021    ///
1022    /// Returns the base node (ie. the target in this case) of the iterator
1023    Node baseNode(const InEdgeIt &e) const {
1024      return Parent::target((Edge&)e);
1025    }
1026    /// \brief Running node of the iterator
1027    ///
1028    /// Returns the running node (ie. the source in this case) of the
1029    /// iterator
1030    Node runningNode(const InEdgeIt &e) const {
1031      return Parent::source((Edge&)e);
1032    }
1033 
1034    class IncEdgeIt : public Parent::UEdge {
1035      friend class BpUGraphExtender;
1036      const Graph* graph;
1037      bool direction;
1038    public:
1039   
1040      IncEdgeIt() { }
1041   
1042      IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
1043   
1044      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
1045        graph->firstInc(*this, direction, n);
1046      }
1047
1048      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
1049        : graph(&_graph), UEdge(ue) {
1050        direction = (graph->source(ue) == n);
1051      }
1052
1053      IncEdgeIt& operator++() {
1054        graph->nextInc(*this, direction);
1055        return *this;
1056      }
1057    };
1058 
1059
1060    /// Base node of the iterator
1061    ///
1062    /// Returns the base node of the iterator
1063    Node baseNode(const IncEdgeIt &e) const {
1064      return e.direction ? source(e) : target(e);
1065    }
1066
1067    /// Running node of the iterator
1068    ///
1069    /// Returns the running node of the iterator
1070    Node runningNode(const IncEdgeIt &e) const {
1071      return e.direction ? target(e) : source(e);
1072    }
1073
1074    template <typename _Value>
1075    class ANodeMap
1076      : public MapExtender<DefaultMap<Graph, ANode, _Value> > {
1077    public:
1078      typedef BpUGraphExtender Graph;
1079      typedef MapExtender<DefaultMap<Graph, ANode, _Value> > Parent;
1080   
1081      ANodeMap(const Graph& graph)
1082        : Parent(graph) {}
1083      ANodeMap(const Graph& graph, const _Value& value)
1084        : Parent(graph, value) {}
1085   
1086      ANodeMap& operator=(const ANodeMap& cmap) {
1087        return operator=<ANodeMap>(cmap);
1088      }
1089   
1090      template <typename CMap>
1091      ANodeMap& operator=(const CMap& cmap) {
1092        Parent::operator=(cmap);
1093        return *this;
1094      }
1095   
1096    };
1097
1098    template <typename _Value>
1099    class BNodeMap
1100      : public MapExtender<DefaultMap<Graph, BNode, _Value> > {
1101    public:
1102      typedef BpUGraphExtender Graph;
1103      typedef MapExtender<DefaultMap<Graph, BNode, _Value> > Parent;
1104   
1105      BNodeMap(const Graph& graph)
1106        : Parent(graph) {}
1107      BNodeMap(const Graph& graph, const _Value& value)
1108        : Parent(graph, value) {}
1109   
1110      BNodeMap& operator=(const BNodeMap& cmap) {
1111        return operator=<BNodeMap>(cmap);
1112      }
1113   
1114      template <typename CMap>
1115      BNodeMap& operator=(const CMap& cmap) {
1116        Parent::operator=(cmap);
1117        return *this;
1118      }
1119   
1120    };
1121
1122  public:
1123
1124    template <typename _Value>
1125    class NodeMap {
1126    public:
1127      typedef BpUGraphExtender Graph;
1128
1129      typedef Node Key;
1130      typedef _Value Value;
1131
1132      /// The reference type of the map;
1133      typedef typename ANodeMap<_Value>::Reference Reference;
1134      /// The const reference type of the map;
1135      typedef typename ANodeMap<_Value>::ConstReference ConstReference;
1136
1137      typedef True ReferenceMapTag;
1138
1139      NodeMap(const Graph& _graph)
1140        : graph(_graph), aNodeMap(_graph), bNodeMap(_graph) {}
1141      NodeMap(const Graph& _graph, const _Value& _value)
1142        : graph(_graph), aNodeMap(_graph, _value), bNodeMap(_graph, _value) {}
1143
1144      NodeMap& operator=(const NodeMap& cmap) {
1145        return operator=<NodeMap>(cmap);
1146      }
1147   
1148      template <typename CMap>
1149      NodeMap& operator=(const CMap& cmap) {
1150        checkConcept<concepts::ReadMap<Node, _Value>, CMap>();
1151        aNodeMap = cmap;
1152        bNodeMap = cmap;
1153        return *this;
1154      }
1155
1156      ConstReference operator[](const Key& node) const {
1157        if (Parent::aNode(node)) {
1158          return aNodeMap[node];
1159        } else {
1160          return bNodeMap[node];
1161        }
1162      }
1163
1164      Reference operator[](const Key& node) {
1165        if (Parent::aNode(node)) {
1166          return aNodeMap[node];
1167        } else {
1168          return bNodeMap[node];
1169        }
1170      }
1171
1172      void set(const Key& node, const Value& value) {
1173        if (Parent::aNode(node)) {
1174          aNodeMap.set(node, value);
1175        } else {
1176          bNodeMap.set(node, value);
1177        }
1178      }
1179
1180      class MapIt : public NodeIt {
1181      public:
1182
1183        typedef NodeIt Parent;
1184       
1185        explicit MapIt(NodeMap& _map)
1186          : Parent(_map.graph), map(_map) {}
1187       
1188        typename MapTraits<NodeMap>::ConstReturnValue operator*() const {
1189          return map[*this];
1190        }
1191       
1192        typename MapTraits<NodeMap>::ReturnValue operator*() {
1193          return map[*this];
1194        }
1195       
1196        void set(const Value& value) {
1197          map.set(*this, value);
1198        }
1199
1200      private:
1201        NodeMap& map;
1202      };
1203
1204      class ConstMapIt : public NodeIt {
1205      public:
1206
1207        typedef NodeIt Parent;
1208       
1209        explicit ConstMapIt(const NodeMap& _map)
1210          : Parent(_map.graph), map(_map) {}
1211       
1212        typename MapTraits<NodeMap>::ConstReturnValue operator*() const {
1213          return map[*this];
1214        }
1215       
1216      private:
1217        const NodeMap& map;
1218      };
1219
1220      class ItemIt : public NodeIt {
1221      public:
1222
1223        typedef NodeIt Parent;
1224
1225        explicit ItemIt(const NodeMap& _map)
1226          : Parent(_map.graph) {}
1227       
1228      };
1229     
1230    private:
1231      const Graph& graph;
1232      ANodeMap<_Value> aNodeMap;
1233      BNodeMap<_Value> bNodeMap;
1234    };
1235   
1236
1237    template <typename _Value>
1238    class EdgeMap
1239      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
1240    public:
1241      typedef BpUGraphExtender Graph;
1242      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
1243   
1244      EdgeMap(const Graph& graph)
1245        : Parent(graph) {}
1246      EdgeMap(const Graph& graph, const _Value& value)
1247        : Parent(graph, value) {}
1248   
1249      EdgeMap& operator=(const EdgeMap& cmap) {
1250        return operator=<EdgeMap>(cmap);
1251      }
1252   
1253      template <typename CMap>
1254      EdgeMap& operator=(const CMap& cmap) {
1255        Parent::operator=(cmap);
1256        return *this;
1257      }
1258    };
1259
1260    template <typename _Value>
1261    class UEdgeMap
1262      : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
1263    public:
1264      typedef BpUGraphExtender Graph;
1265      typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
1266   
1267      UEdgeMap(const Graph& graph)
1268        : Parent(graph) {}
1269      UEdgeMap(const Graph& graph, const _Value& value)
1270        : Parent(graph, value) {}
1271   
1272      UEdgeMap& operator=(const UEdgeMap& cmap) {
1273        return operator=<UEdgeMap>(cmap);
1274      }
1275   
1276      template <typename CMap>
1277      UEdgeMap& operator=(const CMap& cmap) {
1278        Parent::operator=(cmap);
1279        return *this;
1280      }
1281    };
1282
1283 
1284    Node addANode() {
1285      Node node = Parent::addANode();
1286      getNotifier(ANode()).add(node);
1287      getNotifier(Node()).add(node);
1288      return node;
1289    }
1290
1291    Node addBNode() {
1292      Node node = Parent::addBNode();
1293      getNotifier(BNode()).add(node);
1294      getNotifier(Node()).add(node);
1295      return node;
1296    }
1297 
1298    UEdge addEdge(const Node& source, const Node& target) {
1299      UEdge uedge = Parent::addEdge(source, target);
1300      getNotifier(UEdge()).add(uedge);
1301   
1302      std::vector<Edge> edges;
1303      edges.push_back(Parent::direct(uedge, true));
1304      edges.push_back(Parent::direct(uedge, false));
1305      getNotifier(Edge()).add(edges);
1306   
1307      return uedge;
1308    }
1309
1310    void clear() {
1311      getNotifier(Edge()).clear();
1312      getNotifier(UEdge()).clear();
1313      getNotifier(Node()).clear();
1314      getNotifier(BNode()).clear();
1315      getNotifier(ANode()).clear();
1316      Parent::clear();
1317    }
1318
1319    template <typename Graph, typename ANodeRefMap,
1320              typename BNodeRefMap, typename UEdgeRefMap>
1321    void clone(const Graph& graph, ANodeRefMap& aNodeRef,
1322               BNodeRefMap& bNodeRef, UEdgeRefMap& uEdgeRef) {
1323      Parent::clone(graph, aNodeRef, bNodeRef, uEdgeRef);
1324      getNotifier(ANode()).build();
1325      getNotifier(BNode()).build();
1326      getNotifier(Node()).build();
1327      getNotifier(UEdge()).build();
1328      getNotifier(Edge()).build();
1329    }
1330
1331    void erase(const Node& node) {
1332      UEdge uedge;
1333      if (Parent::aNode(node)) {
1334        Parent::firstFromANode(uedge, node);
1335        while (uedge != INVALID) {
1336          erase(uedge);
1337          Parent::firstFromANode(uedge, node);
1338        }
1339        getNotifier(ANode()).erase(node);
1340      } else {
1341        Parent::firstFromBNode(uedge, node);
1342        while (uedge != INVALID) {
1343          erase(uedge);
1344          Parent::firstFromBNode(uedge, node);
1345        }
1346        getNotifier(BNode()).erase(node);
1347      }
1348
1349      getNotifier(Node()).erase(node);
1350      Parent::erase(node);
1351    }
1352   
1353    void erase(const UEdge& uedge) {
1354      std::vector<Edge> edges;
1355      edges.push_back(Parent::direct(uedge, true));
1356      edges.push_back(Parent::direct(uedge, false));
1357      getNotifier(Edge()).erase(edges);
1358      getNotifier(UEdge()).erase(uedge);
1359      Parent::erase(uedge);
1360    }
1361
1362
1363    BpUGraphExtender() {
1364      anode_notifier.setContainer(*this);
1365      bnode_notifier.setContainer(*this);
1366      node_notifier.setContainer(*this);
1367      edge_notifier.setContainer(*this);
1368      uedge_notifier.setContainer(*this);
1369    }
1370
1371    ~BpUGraphExtender() {
1372      uedge_notifier.clear();
1373      edge_notifier.clear();
1374      node_notifier.clear();
1375      anode_notifier.clear();
1376      bnode_notifier.clear();
1377    }
1378
1379    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
1380      UEdge uedge = Parent::findUEdge(u, v, prev);
1381      if (uedge != INVALID) {
1382        return Parent::direct(uedge, Parent::aNode(u));
1383      } else {
1384        return INVALID;
1385      }
1386    }
1387
1388  };
1389
1390}
1391
1392#endif
Note: See TracBrowser for help on using the repository browser.