COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/graph_extender.h @ 2283:a877258468e4

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

Bug fix

File size: 31.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
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      std::vector<Edge> edges;
677      edges.push_back(Parent::direct(uedge, true));
678      edges.push_back(Parent::direct(uedge, false));     
679      getNotifier(Edge()).add(edges);
680      return uedge;
681    }
682   
683    void clear() {
684      getNotifier(Edge()).clear();
685      getNotifier(UEdge()).clear();
686      getNotifier(Node()).clear();
687      Parent::clear();
688    }
689
690    void erase(const Node& node) {
691      Edge edge;
692      Parent::firstOut(edge, node);
693      while (edge != INVALID ) {
694        erase(edge);
695        Parent::firstOut(edge, node);
696      }
697
698      Parent::firstIn(edge, node);
699      while (edge != INVALID ) {
700        erase(edge);
701        Parent::firstIn(edge, node);
702      }
703
704      getNotifier(Node()).erase(node);
705      Parent::erase(node);
706    }
707
708    void erase(const UEdge& uedge) {
709      std::vector<Edge> edges;
710      edges.push_back(Parent::direct(uedge, true));
711      edges.push_back(Parent::direct(uedge, false));     
712      getNotifier(Edge()).erase(edges);
713      getNotifier(UEdge()).erase(uedge);
714      Parent::erase(uedge);
715    }
716
717    UGraphExtender() {
718      node_notifier.setContainer(*this);
719      edge_notifier.setContainer(*this);
720      uedge_notifier.setContainer(*this);
721    }
722
723    ~UGraphExtender() {
724      uedge_notifier.clear();
725      edge_notifier.clear();
726      node_notifier.clear();
727    }
728
729  };
730
731  /// \ingroup graphbits
732  ///
733  /// \brief Extender for the BpUGraphs
734  template <typename Base>
735  class BpUGraphExtender : public Base {
736  public:
737
738    typedef Base Parent;
739    typedef BpUGraphExtender Graph;
740
741    typedef typename Parent::Node Node;
742    typedef typename Parent::ANode ANode;
743    typedef typename Parent::BNode BNode;
744    typedef typename Parent::Edge Edge;
745    typedef typename Parent::UEdge UEdge;
746
747
748    Node oppositeNode(const Node& node, const UEdge& edge) const {
749      return Parent::aNode(edge) == node ?
750        Parent::bNode(edge) : Parent::aNode(edge);
751    }
752
753    using Parent::direct;
754    Edge direct(const UEdge& edge, const Node& node) const {
755      return Parent::direct(edge, node == Parent::source(edge));
756    }
757
758    Edge oppositeEdge(const Edge& edge) const {
759      return direct(edge, !Parent::direction(edge));
760    }
761   
762    int maxId(Node) const {
763      return Parent::maxNodeId();
764    }
765    int maxId(BNode) const {
766      return Parent::maxBNodeId();
767    }
768    int maxId(ANode) const {
769      return Parent::maxANodeId();
770    }
771    int maxId(Edge) const {
772      return Parent::maxEdgeId();
773    }
774    int maxId(UEdge) const {
775      return Parent::maxUEdgeId();
776    }
777
778
779    Node fromId(int id, Node) const {
780      return Parent::nodeFromId(id);
781    }
782    ANode fromId(int id, ANode) const {
783      return Parent::nodeFromANodeId(id);
784    }
785    BNode fromId(int id, BNode) const {
786      return Parent::nodeFromBNodeId(id);
787    }
788    Edge fromId(int id, Edge) const {
789      return Parent::edgeFromId(id);
790    }
791    UEdge fromId(int id, UEdge) const {
792      return Parent::uEdgeFromId(id);
793    } 
794 
795    typedef AlterationNotifier<BpUGraphExtender, ANode> ANodeNotifier;
796    typedef AlterationNotifier<BpUGraphExtender, BNode> BNodeNotifier;
797    typedef AlterationNotifier<BpUGraphExtender, Node> NodeNotifier;
798    typedef AlterationNotifier<BpUGraphExtender, Edge> EdgeNotifier;
799    typedef AlterationNotifier<BpUGraphExtender, UEdge> UEdgeNotifier;
800
801  protected:
802
803    mutable ANodeNotifier anode_notifier;
804    mutable BNodeNotifier bnode_notifier;
805    mutable NodeNotifier node_notifier;
806    mutable EdgeNotifier edge_notifier;
807    mutable UEdgeNotifier uedge_notifier;
808
809  public:
810
811    NodeNotifier& getNotifier(Node) const {
812      return node_notifier;
813    }
814
815    ANodeNotifier& getNotifier(ANode) const {
816      return anode_notifier;
817    }
818
819    BNodeNotifier& getNotifier(BNode) const {
820      return bnode_notifier;
821    }
822
823    EdgeNotifier& getNotifier(Edge) const {
824      return edge_notifier;
825    }
826
827    UEdgeNotifier& getNotifier(UEdge) const {
828      return uedge_notifier;
829    }
830
831    class NodeIt : public Node {
832      const Graph* graph;
833    public:
834   
835      NodeIt() { }
836   
837      NodeIt(Invalid i) : Node(INVALID) { }
838   
839      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
840        graph->first(static_cast<Node&>(*this));
841      }
842
843      NodeIt(const Graph& _graph, const Node& node)
844        : Node(node), graph(&_graph) { }
845   
846      NodeIt& operator++() {
847        graph->next(*this);
848        return *this;
849      }
850
851    };
852
853    class ANodeIt : public Node {
854      friend class BpUGraphExtender;
855      const Graph* graph;
856    public:
857   
858      ANodeIt() { }
859   
860      ANodeIt(Invalid i) : Node(INVALID) { }
861   
862      explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
863        graph->firstANode(static_cast<Node&>(*this));
864      }
865
866      ANodeIt(const Graph& _graph, const Node& node)
867        : Node(node), graph(&_graph) {}
868   
869      ANodeIt& operator++() {
870        graph->nextANode(*this);
871        return *this;
872      }
873    };
874
875    class BNodeIt : public Node {
876      friend class BpUGraphExtender;
877      const Graph* graph;
878    public:
879   
880      BNodeIt() { }
881   
882      BNodeIt(Invalid i) : Node(INVALID) { }
883   
884      explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
885        graph->firstBNode(static_cast<Node&>(*this));
886      }
887
888      BNodeIt(const Graph& _graph, const Node& node)
889        : Node(node), graph(&_graph) {}
890   
891      BNodeIt& operator++() {
892        graph->nextBNode(*this);
893        return *this;
894      }
895    };
896
897    class EdgeIt : public Edge {
898      friend class BpUGraphExtender;
899      const Graph* graph;
900    public:
901   
902      EdgeIt() { }
903   
904      EdgeIt(Invalid i) : Edge(INVALID) { }
905   
906      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
907        graph->first(static_cast<Edge&>(*this));
908      }
909
910      EdgeIt(const Graph& _graph, const Edge& edge)
911        : Edge(edge), graph(&_graph) { }
912   
913      EdgeIt& operator++() {
914        graph->next(*this);
915        return *this;
916      }
917
918    };
919
920    class UEdgeIt : public UEdge {
921      friend class BpUGraphExtender;
922      const Graph* graph;
923    public:
924   
925      UEdgeIt() { }
926   
927      UEdgeIt(Invalid i) : UEdge(INVALID) { }
928   
929      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
930        graph->first(static_cast<UEdge&>(*this));
931      }
932
933      UEdgeIt(const Graph& _graph, const UEdge& edge)
934        : UEdge(edge), graph(&_graph) { }
935   
936      UEdgeIt& operator++() {
937        graph->next(*this);
938        return *this;
939      }
940    };
941
942    class OutEdgeIt : public Edge {
943      friend class BpUGraphExtender;
944      const Graph* graph;
945    public:
946   
947      OutEdgeIt() { }
948   
949      OutEdgeIt(Invalid i) : Edge(i) { }
950   
951      OutEdgeIt(const Graph& _graph, const Node& node)
952        : graph(&_graph) {
953        graph->firstOut(*this, node);
954      }
955   
956      OutEdgeIt(const Graph& _graph, const Edge& edge)
957        : Edge(edge), graph(&_graph) {}
958   
959      OutEdgeIt& operator++() {
960        graph->nextOut(*this);
961        return *this;
962      }
963
964    };
965
966
967    class InEdgeIt : public Edge {
968      friend class BpUGraphExtender;
969      const Graph* graph;
970    public:
971   
972      InEdgeIt() { }
973   
974      InEdgeIt(Invalid i) : Edge(i) { }
975   
976      InEdgeIt(const Graph& _graph, const Node& node)
977        : graph(&_graph) {
978        graph->firstIn(*this, node);
979      }
980   
981      InEdgeIt(const Graph& _graph, const Edge& edge) :
982        Edge(edge), graph(&_graph) {}
983   
984      InEdgeIt& operator++() {
985        graph->nextIn(*this);
986        return *this;
987      }
988
989    };
990 
991    /// \brief Base node of the iterator
992    ///
993    /// Returns the base node (ie. the source in this case) of the iterator
994    Node baseNode(const OutEdgeIt &e) const {
995      return Parent::source((Edge&)e);
996    }
997    /// \brief Running node of the iterator
998    ///
999    /// Returns the running node (ie. the target in this case) of the
1000    /// iterator
1001    Node runningNode(const OutEdgeIt &e) const {
1002      return Parent::target((Edge&)e);
1003    }
1004 
1005    /// \brief Base node of the iterator
1006    ///
1007    /// Returns the base node (ie. the target in this case) of the iterator
1008    Node baseNode(const InEdgeIt &e) const {
1009      return Parent::target((Edge&)e);
1010    }
1011    /// \brief Running node of the iterator
1012    ///
1013    /// Returns the running node (ie. the source in this case) of the
1014    /// iterator
1015    Node runningNode(const InEdgeIt &e) const {
1016      return Parent::source((Edge&)e);
1017    }
1018 
1019    class IncEdgeIt : public Parent::UEdge {
1020      friend class BpUGraphExtender;
1021      const Graph* graph;
1022      bool direction;
1023    public:
1024   
1025      IncEdgeIt() { }
1026   
1027      IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
1028   
1029      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
1030        graph->firstInc(*this, direction, n);
1031      }
1032
1033      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
1034        : graph(&_graph), UEdge(ue) {
1035        direction = (graph->source(ue) == n);
1036      }
1037
1038      IncEdgeIt& operator++() {
1039        graph->nextInc(*this, direction);
1040        return *this;
1041      }
1042    };
1043 
1044
1045    /// Base node of the iterator
1046    ///
1047    /// Returns the base node of the iterator
1048    Node baseNode(const IncEdgeIt &e) const {
1049      return e.direction ? source(e) : target(e);
1050    }
1051
1052    /// Running node of the iterator
1053    ///
1054    /// Returns the running node of the iterator
1055    Node runningNode(const IncEdgeIt &e) const {
1056      return e.direction ? target(e) : source(e);
1057    }
1058
1059    template <typename _Value>
1060    class ANodeMap
1061      : public MapExtender<DefaultMap<Graph, ANode, _Value> > {
1062    public:
1063      typedef BpUGraphExtender Graph;
1064      typedef MapExtender<DefaultMap<Graph, ANode, _Value> > Parent;
1065   
1066      ANodeMap(const Graph& graph)
1067        : Parent(graph) {}
1068      ANodeMap(const Graph& graph, const _Value& value)
1069        : Parent(graph, value) {}
1070   
1071      ANodeMap& operator=(const ANodeMap& cmap) {
1072        return operator=<ANodeMap>(cmap);
1073      }
1074   
1075      template <typename CMap>
1076      ANodeMap& operator=(const CMap& cmap) {
1077        Parent::operator=(cmap);
1078        return *this;
1079      }
1080   
1081    };
1082
1083    template <typename _Value>
1084    class BNodeMap
1085      : public MapExtender<DefaultMap<Graph, BNode, _Value> > {
1086    public:
1087      typedef BpUGraphExtender Graph;
1088      typedef MapExtender<DefaultMap<Graph, BNode, _Value> > Parent;
1089   
1090      BNodeMap(const Graph& graph)
1091        : Parent(graph) {}
1092      BNodeMap(const Graph& graph, const _Value& value)
1093        : Parent(graph, value) {}
1094   
1095      BNodeMap& operator=(const BNodeMap& cmap) {
1096        return operator=<BNodeMap>(cmap);
1097      }
1098   
1099      template <typename CMap>
1100      BNodeMap& operator=(const CMap& cmap) {
1101        Parent::operator=(cmap);
1102        return *this;
1103      }
1104   
1105    };
1106
1107  public:
1108
1109    template <typename _Value>
1110    class NodeMap {
1111    public:
1112      typedef BpUGraphExtender Graph;
1113
1114      typedef Node Key;
1115      typedef _Value Value;
1116
1117      /// The reference type of the map;
1118      typedef typename ANodeMap<_Value>::Reference Reference;
1119      /// The const reference type of the map;
1120      typedef typename ANodeMap<_Value>::ConstReference ConstReference;
1121
1122      typedef True ReferenceMapTag;
1123
1124      NodeMap(const Graph& _graph)
1125        : graph(_graph), aNodeMap(_graph), bNodeMap(_graph) {}
1126      NodeMap(const Graph& _graph, const _Value& _value)
1127        : graph(_graph), aNodeMap(_graph, _value), bNodeMap(_graph, _value) {}
1128
1129      NodeMap& operator=(const NodeMap& cmap) {
1130        return operator=<NodeMap>(cmap);
1131      }
1132   
1133      template <typename CMap>
1134      NodeMap& operator=(const CMap& cmap) {
1135        checkConcept<concepts::ReadMap<Node, _Value>, CMap>();
1136        aNodeMap = cmap;
1137        bNodeMap = cmap;
1138        return *this;
1139      }
1140
1141      ConstReference operator[](const Key& node) const {
1142        if (Parent::aNode(node)) {
1143          return aNodeMap[node];
1144        } else {
1145          return bNodeMap[node];
1146        }
1147      }
1148
1149      Reference operator[](const Key& node) {
1150        if (Parent::aNode(node)) {
1151          return aNodeMap[node];
1152        } else {
1153          return bNodeMap[node];
1154        }
1155      }
1156
1157      void set(const Key& node, const Value& value) {
1158        if (Parent::aNode(node)) {
1159          aNodeMap.set(node, value);
1160        } else {
1161          bNodeMap.set(node, value);
1162        }
1163      }
1164
1165      class MapIt : public NodeIt {
1166      public:
1167
1168        typedef NodeIt Parent;
1169       
1170        explicit MapIt(NodeMap& _map)
1171          : Parent(_map.graph), map(_map) {}
1172       
1173        typename MapTraits<NodeMap>::ConstReturnValue operator*() const {
1174          return map[*this];
1175        }
1176       
1177        typename MapTraits<NodeMap>::ReturnValue operator*() {
1178          return map[*this];
1179        }
1180       
1181        void set(const Value& value) {
1182          map.set(*this, value);
1183        }
1184
1185      private:
1186        NodeMap& map;
1187      };
1188
1189      class ConstMapIt : public NodeIt {
1190      public:
1191
1192        typedef NodeIt Parent;
1193       
1194        explicit ConstMapIt(const NodeMap& _map)
1195          : Parent(_map.graph), map(_map) {}
1196       
1197        typename MapTraits<NodeMap>::ConstReturnValue operator*() const {
1198          return map[*this];
1199        }
1200       
1201      private:
1202        const NodeMap& map;
1203      };
1204
1205      class ItemIt : public NodeIt {
1206      public:
1207
1208        typedef NodeIt Parent;
1209
1210        explicit ItemIt(const NodeMap& _map)
1211          : Parent(_map.graph) {}
1212       
1213      };
1214     
1215    private:
1216      const Graph& graph;
1217      ANodeMap<_Value> aNodeMap;
1218      BNodeMap<_Value> bNodeMap;
1219    };
1220   
1221
1222    template <typename _Value>
1223    class EdgeMap
1224      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
1225    public:
1226      typedef BpUGraphExtender Graph;
1227      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
1228   
1229      EdgeMap(const Graph& graph)
1230        : Parent(graph) {}
1231      EdgeMap(const Graph& graph, const _Value& value)
1232        : Parent(graph, value) {}
1233   
1234      EdgeMap& operator=(const EdgeMap& cmap) {
1235        return operator=<EdgeMap>(cmap);
1236      }
1237   
1238      template <typename CMap>
1239      EdgeMap& operator=(const CMap& cmap) {
1240        Parent::operator=(cmap);
1241        return *this;
1242      }
1243    };
1244
1245    template <typename _Value>
1246    class UEdgeMap
1247      : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
1248    public:
1249      typedef BpUGraphExtender Graph;
1250      typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
1251   
1252      UEdgeMap(const Graph& graph)
1253        : Parent(graph) {}
1254      UEdgeMap(const Graph& graph, const _Value& value)
1255        : Parent(graph, value) {}
1256   
1257      UEdgeMap& operator=(const UEdgeMap& cmap) {
1258        return operator=<UEdgeMap>(cmap);
1259      }
1260   
1261      template <typename CMap>
1262      UEdgeMap& operator=(const CMap& cmap) {
1263        Parent::operator=(cmap);
1264        return *this;
1265      }
1266    };
1267
1268 
1269    Node addANode() {
1270      Node node = Parent::addANode();
1271      getNotifier(ANode()).add(node);
1272      getNotifier(Node()).add(node);
1273      return node;
1274    }
1275
1276    Node addBNode() {
1277      Node node = Parent::addBNode();
1278      getNotifier(BNode()).add(node);
1279      getNotifier(Node()).add(node);
1280      return node;
1281    }
1282 
1283    UEdge addEdge(const Node& source, const Node& target) {
1284      UEdge uedge = Parent::addEdge(source, target);
1285      getNotifier(UEdge()).add(uedge);
1286   
1287      std::vector<Edge> edges;
1288      edges.push_back(Parent::direct(uedge, true));
1289      edges.push_back(Parent::direct(uedge, false));
1290      getNotifier(Edge()).add(edges);
1291   
1292      return uedge;
1293    }
1294
1295    void clear() {
1296      getNotifier(Edge()).clear();
1297      getNotifier(UEdge()).clear();
1298      getNotifier(Node()).clear();
1299      getNotifier(BNode()).clear();
1300      getNotifier(ANode()).clear();
1301      Parent::clear();
1302    }
1303
1304    void erase(const Node& node) {
1305      UEdge uedge;
1306      if (Parent::aNode(node)) {
1307        Parent::firstFromANode(uedge, node);
1308        while (uedge != INVALID) {
1309          erase(uedge);
1310          Parent::firstFromANode(uedge, node);
1311        }
1312        getNotifier(ANode()).erase(node);
1313      } else {
1314        Parent::firstFromBNode(uedge, node);
1315        while (uedge != INVALID) {
1316          erase(uedge);
1317          Parent::firstFromBNode(uedge, node);
1318        }
1319        getNotifier(BNode()).erase(node);
1320      }
1321
1322      getNotifier(Node()).erase(node);
1323      Parent::erase(node);
1324    }
1325   
1326    void erase(const UEdge& uedge) {
1327      std::vector<Edge> edges;
1328      edges.push_back(Parent::direct(uedge, true));
1329      edges.push_back(Parent::direct(uedge, false));
1330      getNotifier(Edge()).erase(edges);
1331      getNotifier(UEdge()).erase(uedge);
1332      Parent::erase(uedge);
1333    }
1334
1335
1336    BpUGraphExtender() {
1337      anode_notifier.setContainer(*this);
1338      bnode_notifier.setContainer(*this);
1339      node_notifier.setContainer(*this);
1340      edge_notifier.setContainer(*this);
1341      uedge_notifier.setContainer(*this);
1342    }
1343
1344    ~BpUGraphExtender() {
1345      uedge_notifier.clear();
1346      edge_notifier.clear();
1347      node_notifier.clear();
1348      anode_notifier.clear();
1349      bnode_notifier.clear();
1350    }
1351
1352    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
1353      UEdge uedge = Parent::findUEdge(u, v, prev);
1354      if (uedge != INVALID) {
1355        return Parent::direct(uedge, Parent::aNode(u));
1356      } else {
1357        return INVALID;
1358      }
1359    }
1360
1361  };
1362
1363}
1364
1365#endif
Note: See TracBrowser for help on using the repository browser.