COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/graph_extender.h @ 2204:5617107d27e9

Last change on this file since 2204:5617107d27e9 was 2203:5f1a83b565fb, checked in by Balazs Dezso, 18 years ago

Signaling alterations in BpUGraphs

File size: 35.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/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 (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      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::UEdge UEdge;
738
739
740    using Parent::first;
741    using Parent::next;
742
743    using Parent::id;
744
745    class ANode : public Node {
746      friend class BpUGraphExtender;
747    public:
748      ANode() {}
749      ANode(const Node& node) : Node(node) {
750        LEMON_ASSERT(Parent::aNode(node) || node == INVALID,
751                     typename Parent::NodeSetError());
752      }
753      ANode(Invalid) : Node(INVALID) {}
754    };
755
756    void first(ANode& node) const {
757      Parent::firstANode(static_cast<Node&>(node));
758    }
759    void next(ANode& node) const {
760      Parent::nextANode(static_cast<Node&>(node));
761    }
762
763    int id(const ANode& node) const {
764      return Parent::aNodeId(node);
765    }
766
767    class BNode : public Node {
768      friend class BpUGraphExtender;
769    public:
770      BNode() {}
771      BNode(const Node& node) : Node(node) {
772        LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
773                     typename Parent::NodeSetError());
774      }
775      BNode(Invalid) : Node(INVALID) {}
776    };
777
778    void first(BNode& node) const {
779      Parent::firstBNode(static_cast<Node&>(node));
780    }
781    void next(BNode& node) const {
782      Parent::nextBNode(static_cast<Node&>(node));
783    }
784 
785    int id(const BNode& node) const {
786      return Parent::aNodeId(node);
787    }
788
789    Node source(const UEdge& edge) const {
790      return aNode(edge);
791    }
792    Node target(const UEdge& edge) const {
793      return bNode(edge);
794    }
795
796    void firstInc(UEdge& edge, bool& direction, const Node& node) const {
797      if (Parent::aNode(node)) {
798        Parent::firstFromANode(edge, node);
799        direction = true;
800      } else {
801        Parent::firstFromBNode(edge, node);
802        direction = static_cast<UEdge&>(edge) == INVALID;
803      }
804    }
805    void nextInc(UEdge& edge, bool& direction) const {
806      if (direction) {
807        Parent::nextFromANode(edge);
808      } else {
809        Parent::nextFromBNode(edge);
810        if (edge == INVALID) direction = true;
811      }
812    }
813
814    class Edge : public UEdge {
815      friend class BpUGraphExtender;
816    protected:
817      bool forward;
818
819      Edge(const UEdge& edge, bool _forward)
820        : UEdge(edge), forward(_forward) {}
821
822    public:
823      Edge() {}
824      Edge (Invalid) : UEdge(INVALID), forward(true) {}
825      bool operator==(const Edge& i) const {
826        return UEdge::operator==(i) && forward == i.forward;
827      }
828      bool operator!=(const Edge& i) const {
829        return UEdge::operator!=(i) || forward != i.forward;
830      }
831      bool operator<(const Edge& i) const {
832        return UEdge::operator<(i) ||
833          (!(i.forward<forward) && UEdge(*this)<UEdge(i));
834      }
835    };
836
837    void first(Edge& edge) const {
838      Parent::first(static_cast<UEdge&>(edge));
839      edge.forward = true;
840    }
841
842    void next(Edge& edge) const {
843      if (!edge.forward) {
844        Parent::next(static_cast<UEdge&>(edge));
845      }
846      edge.forward = !edge.forward;
847    }
848
849    void firstOut(Edge& edge, const Node& node) const {
850      if (Parent::aNode(node)) {
851        Parent::firstFromANode(edge, node);
852        edge.forward = true;
853      } else {
854        Parent::firstFromBNode(edge, node);
855        edge.forward = static_cast<UEdge&>(edge) == INVALID;
856      }
857    }
858    void nextOut(Edge& edge) const {
859      if (edge.forward) {
860        Parent::nextFromANode(edge);
861      } else {
862        Parent::nextFromBNode(edge);
863        edge.forward = static_cast<UEdge&>(edge) == INVALID;
864      }
865    }
866
867    void firstIn(Edge& edge, const Node& node) const {
868      if (Parent::bNode(node)) {
869        Parent::firstFromBNode(edge, node);
870        edge.forward = true;   
871      } else {
872        Parent::firstFromANode(edge, node);
873        edge.forward = static_cast<UEdge&>(edge) == INVALID;
874      }
875    }
876    void nextIn(Edge& edge) const {
877      if (edge.forward) {
878        Parent::nextFromBNode(edge);
879      } else {
880        Parent::nextFromANode(edge);
881        edge.forward = static_cast<UEdge&>(edge) == INVALID;
882      }
883    }
884
885    Node source(const Edge& edge) const {
886      return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
887    }
888    Node target(const Edge& edge) const {
889      return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
890    }
891
892    int id(const Edge& edge) const {
893      return (Parent::id(static_cast<const UEdge&>(edge)) << 1) +
894        (edge.forward ? 0 : 1);
895    }
896    Edge edgeFromId(int id) const {
897      return Edge(Parent::fromUEdgeId(id >> 1), (id & 1) == 0);
898    }
899    int maxEdgeId() const {
900      return (Parent::maxUEdgeId(UEdge()) << 1) + 1;
901    }
902
903    bool direction(const Edge& edge) const {
904      return edge.forward;
905    }
906
907    Edge direct(const UEdge& edge, bool direction) const {
908      return Edge(edge, direction);
909    }
910
911    int edgeNum() const {
912      return 2 * Parent::uEdgeNum();
913    }
914
915    int uEdgeNum() const {
916      return Parent::uEdgeNum();
917    }
918
919    Node oppositeNode(const UEdge& edge, const Node& node) const {
920      return source(edge) == node ?
921        target(edge) : source(edge);
922    }
923
924    Edge direct(const UEdge& edge, const Node& node) const {
925      return Edge(edge, node == Parent::source(edge));
926    }
927
928    Edge oppositeEdge(const Edge& edge) const {
929      return Parent::direct(edge, !Parent::direction(edge));
930    }
931
932
933    int maxId(Node) const {
934      return Parent::maxNodeId();
935    }
936    int maxId(BNode) const {
937      return Parent::maxBNodeId();
938    }
939    int maxId(ANode) const {
940      return Parent::maxANodeId();
941    }
942    int maxId(Edge) const {
943      return maxEdgeId();
944    }
945    int maxId(UEdge) const {
946      return Parent::maxUEdgeId();
947    }
948
949
950    Node fromId(int id, Node) const {
951      return Parent::nodeFromId(id);
952    }
953    ANode fromId(int id, ANode) const {
954      return Parent::fromANodeId(id);
955    }
956    BNode fromId(int id, BNode) const {
957      return Parent::fromBNodeId(id);
958    }
959    Edge fromId(int id, Edge) const {
960      return Parent::edgeFromId(id);
961    }
962    UEdge fromId(int id, UEdge) const {
963      return Parent::uEdgeFromId(id);
964    } 
965 
966    typedef AlterationNotifier<BpUGraphExtender, ANode> ANodeNotifier;
967    typedef AlterationNotifier<BpUGraphExtender, BNode> BNodeNotifier;
968    typedef AlterationNotifier<BpUGraphExtender, Node> NodeNotifier;
969    typedef AlterationNotifier<BpUGraphExtender, Edge> EdgeNotifier;
970    typedef AlterationNotifier<BpUGraphExtender, UEdge> UEdgeNotifier;
971
972  protected:
973
974    mutable ANodeNotifier anode_notifier;
975    mutable BNodeNotifier bnode_notifier;
976    mutable NodeNotifier node_notifier;
977    mutable EdgeNotifier edge_notifier;
978    mutable UEdgeNotifier uedge_notifier;
979
980  public:
981
982    NodeNotifier& getNotifier(Node) const {
983      return node_notifier;
984    }
985
986    ANodeNotifier& getNotifier(ANode) const {
987      return anode_notifier;
988    }
989
990    BNodeNotifier& getNotifier(BNode) const {
991      return bnode_notifier;
992    }
993
994    EdgeNotifier& getNotifier(Edge) const {
995      return edge_notifier;
996    }
997
998    UEdgeNotifier& getNotifier(UEdge) const {
999      return uedge_notifier;
1000    }
1001
1002    class NodeIt : public Node {
1003      const Graph* graph;
1004    public:
1005   
1006      NodeIt() { }
1007   
1008      NodeIt(Invalid i) : Node(INVALID) { }
1009   
1010      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
1011        graph->first(static_cast<Node&>(*this));
1012      }
1013
1014      NodeIt(const Graph& _graph, const Node& node)
1015        : Node(node), graph(&_graph) { }
1016   
1017      NodeIt& operator++() {
1018        graph->next(*this);
1019        return *this;
1020      }
1021
1022    };
1023
1024    class ANodeIt : public Node {
1025      friend class BpUGraphExtender;
1026      const Graph* graph;
1027    public:
1028   
1029      ANodeIt() { }
1030   
1031      ANodeIt(Invalid i) : Node(INVALID) { }
1032   
1033      explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
1034        graph->firstANode(static_cast<Node&>(*this));
1035      }
1036
1037      ANodeIt(const Graph& _graph, const Node& node)
1038        : Node(node), graph(&_graph) {}
1039   
1040      ANodeIt& operator++() {
1041        graph->nextANode(*this);
1042        return *this;
1043      }
1044    };
1045
1046    class BNodeIt : public Node {
1047      friend class BpUGraphExtender;
1048      const Graph* graph;
1049    public:
1050   
1051      BNodeIt() { }
1052   
1053      BNodeIt(Invalid i) : Node(INVALID) { }
1054   
1055      explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
1056        graph->firstBNode(static_cast<Node&>(*this));
1057      }
1058
1059      BNodeIt(const Graph& _graph, const Node& node)
1060        : Node(node), graph(&_graph) {}
1061   
1062      BNodeIt& operator++() {
1063        graph->nextBNode(*this);
1064        return *this;
1065      }
1066    };
1067
1068    class EdgeIt : public Edge {
1069      friend class BpUGraphExtender;
1070      const Graph* graph;
1071    public:
1072   
1073      EdgeIt() { }
1074   
1075      EdgeIt(Invalid i) : Edge(INVALID) { }
1076   
1077      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
1078        graph->first(static_cast<Edge&>(*this));
1079      }
1080
1081      EdgeIt(const Graph& _graph, const Edge& edge)
1082        : Edge(edge), graph(&_graph) { }
1083   
1084      EdgeIt& operator++() {
1085        graph->next(*this);
1086        return *this;
1087      }
1088
1089    };
1090
1091    class UEdgeIt : public UEdge {
1092      friend class BpUGraphExtender;
1093      const Graph* graph;
1094    public:
1095   
1096      UEdgeIt() { }
1097   
1098      UEdgeIt(Invalid i) : UEdge(INVALID) { }
1099   
1100      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
1101        graph->first(static_cast<UEdge&>(*this));
1102      }
1103
1104      UEdgeIt(const Graph& _graph, const UEdge& edge)
1105        : UEdge(edge), graph(&_graph) { }
1106   
1107      UEdgeIt& operator++() {
1108        graph->next(*this);
1109        return *this;
1110      }
1111    };
1112
1113    class OutEdgeIt : public Edge {
1114      friend class BpUGraphExtender;
1115      const Graph* graph;
1116    public:
1117   
1118      OutEdgeIt() { }
1119   
1120      OutEdgeIt(Invalid i) : Edge(i) { }
1121   
1122      OutEdgeIt(const Graph& _graph, const Node& node)
1123        : graph(&_graph) {
1124        graph->firstOut(*this, node);
1125      }
1126   
1127      OutEdgeIt(const Graph& _graph, const Edge& edge)
1128        : Edge(edge), graph(&_graph) {}
1129   
1130      OutEdgeIt& operator++() {
1131        graph->nextOut(*this);
1132        return *this;
1133      }
1134
1135    };
1136
1137
1138    class InEdgeIt : public Edge {
1139      friend class BpUGraphExtender;
1140      const Graph* graph;
1141    public:
1142   
1143      InEdgeIt() { }
1144   
1145      InEdgeIt(Invalid i) : Edge(i) { }
1146   
1147      InEdgeIt(const Graph& _graph, const Node& node)
1148        : graph(&_graph) {
1149        graph->firstIn(*this, node);
1150      }
1151   
1152      InEdgeIt(const Graph& _graph, const Edge& edge) :
1153        Edge(edge), graph(&_graph) {}
1154   
1155      InEdgeIt& operator++() {
1156        graph->nextIn(*this);
1157        return *this;
1158      }
1159
1160    };
1161 
1162    /// \brief Base node of the iterator
1163    ///
1164    /// Returns the base node (ie. the source in this case) of the iterator
1165    Node baseNode(const OutEdgeIt &e) const {
1166      return Parent::source((Edge&)e);
1167    }
1168    /// \brief Running node of the iterator
1169    ///
1170    /// Returns the running node (ie. the target in this case) of the
1171    /// iterator
1172    Node runningNode(const OutEdgeIt &e) const {
1173      return Parent::target((Edge&)e);
1174    }
1175 
1176    /// \brief Base node of the iterator
1177    ///
1178    /// Returns the base node (ie. the target in this case) of the iterator
1179    Node baseNode(const InEdgeIt &e) const {
1180      return Parent::target((Edge&)e);
1181    }
1182    /// \brief Running node of the iterator
1183    ///
1184    /// Returns the running node (ie. the source in this case) of the
1185    /// iterator
1186    Node runningNode(const InEdgeIt &e) const {
1187      return Parent::source((Edge&)e);
1188    }
1189 
1190    class IncEdgeIt : public Parent::UEdge {
1191      friend class BpUGraphExtender;
1192      const Graph* graph;
1193      bool direction;
1194    public:
1195   
1196      IncEdgeIt() { }
1197   
1198      IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
1199   
1200      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
1201        graph->firstInc(*this, direction, n);
1202      }
1203
1204      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
1205        : graph(&_graph), UEdge(ue) {
1206        direction = (graph->source(ue) == n);
1207      }
1208
1209      IncEdgeIt& operator++() {
1210        graph->nextInc(*this, direction);
1211        return *this;
1212      }
1213    };
1214 
1215
1216    /// Base node of the iterator
1217    ///
1218    /// Returns the base node of the iterator
1219    Node baseNode(const IncEdgeIt &e) const {
1220      return e.direction ? source(e) : target(e);
1221    }
1222
1223    /// Running node of the iterator
1224    ///
1225    /// Returns the running node of the iterator
1226    Node runningNode(const IncEdgeIt &e) const {
1227      return e.direction ? target(e) : source(e);
1228    }
1229
1230    template <typename _Value>
1231    class ANodeMap
1232      : public MapExtender<DefaultMap<Graph, ANode, _Value> > {
1233    public:
1234      typedef BpUGraphExtender Graph;
1235      typedef MapExtender<DefaultMap<Graph, ANode, _Value> > Parent;
1236   
1237      ANodeMap(const Graph& graph)
1238        : Parent(graph) {}
1239      ANodeMap(const Graph& graph, const _Value& value)
1240        : Parent(graph, value) {}
1241   
1242      ANodeMap& operator=(const ANodeMap& cmap) {
1243        return operator=<ANodeMap>(cmap);
1244      }
1245   
1246      template <typename CMap>
1247      ANodeMap& operator=(const CMap& cmap) {
1248        Parent::operator=(cmap);
1249        return *this;
1250      }
1251   
1252    };
1253
1254    template <typename _Value>
1255    class BNodeMap
1256      : public MapExtender<DefaultMap<Graph, BNode, _Value> > {
1257    public:
1258      typedef BpUGraphExtender Graph;
1259      typedef MapExtender<DefaultMap<Graph, BNode, _Value> > Parent;
1260   
1261      BNodeMap(const Graph& graph)
1262        : Parent(graph) {}
1263      BNodeMap(const Graph& graph, const _Value& value)
1264        : Parent(graph, value) {}
1265   
1266      BNodeMap& operator=(const BNodeMap& cmap) {
1267        return operator=<BNodeMap>(cmap);
1268      }
1269   
1270      template <typename CMap>
1271      BNodeMap& operator=(const CMap& cmap) {
1272        Parent::operator=(cmap);
1273        return *this;
1274      }
1275   
1276    };
1277
1278  public:
1279
1280    template <typename _Value>
1281    class NodeMap {
1282    public:
1283      typedef BpUGraphExtender Graph;
1284
1285      typedef Node Key;
1286      typedef _Value Value;
1287
1288      /// The reference type of the map;
1289      typedef typename ANodeMap<_Value>::Reference Reference;
1290      /// The const reference type of the map;
1291      typedef typename ANodeMap<_Value>::ConstReference ConstReference;
1292
1293      typedef True ReferenceMapTag;
1294
1295      NodeMap(const Graph& _graph)
1296        : graph(_graph), aNodeMap(_graph), bNodeMap(_graph) {}
1297      NodeMap(const Graph& _graph, const _Value& _value)
1298        : graph(_graph), aNodeMap(_graph, _value), bNodeMap(_graph, _value) {}
1299
1300      NodeMap& operator=(const NodeMap& cmap) {
1301        return operator=<NodeMap>(cmap);
1302      }
1303   
1304      template <typename CMap>
1305      NodeMap& operator=(const CMap& cmap) {
1306        checkConcept<concept::ReadMap<Node, _Value>, CMap>();
1307        const typename Parent::Notifier* notifier = Parent::getNotifier();
1308        Edge it;
1309        for (graph.first(it); it != INVALID; graph.next(it)) {
1310          Parent::set(it, cmap[it]);
1311        }
1312        return *this;
1313      }
1314
1315      ConstReference operator[](const Key& node) const {
1316        if (Parent::aNode(node)) {
1317          return aNodeMap[node];
1318        } else {
1319          return bNodeMap[node];
1320        }
1321      }
1322
1323      Reference operator[](const Key& node) {
1324        if (Parent::aNode(node)) {
1325          return aNodeMap[node];
1326        } else {
1327          return bNodeMap[node];
1328        }
1329      }
1330
1331      void set(const Key& node, const Value& value) {
1332        if (Parent::aNode(node)) {
1333          aNodeMap.set(node, value);
1334        } else {
1335          bNodeMap.set(node, value);
1336        }
1337      }
1338
1339      class MapIt : public NodeIt {
1340      public:
1341
1342        typedef NodeIt Parent;
1343       
1344        explicit MapIt(NodeMap& _map)
1345          : Parent(_map.graph), map(_map) {}
1346       
1347        typename MapTraits<NodeMap>::ConstReturnValue operator*() const {
1348          return map[*this];
1349        }
1350       
1351        typename MapTraits<NodeMap>::ReturnValue operator*() {
1352          return map[*this];
1353        }
1354       
1355        void set(const Value& value) {
1356          map.set(*this, value);
1357        }
1358
1359      private:
1360        NodeMap& map;
1361      };
1362
1363      class ConstMapIt : public NodeIt {
1364      public:
1365
1366        typedef NodeIt Parent;
1367       
1368        explicit ConstMapIt(const NodeMap& _map)
1369          : Parent(_map.graph), map(_map) {}
1370       
1371        typename MapTraits<NodeMap>::ConstReturnValue operator*() const {
1372          return map[*this];
1373        }
1374       
1375      private:
1376        const NodeMap& map;
1377      };
1378
1379      class ItemIt : public NodeIt {
1380      public:
1381
1382        typedef NodeIt Parent;
1383
1384        explicit ItemIt(const NodeMap& _map)
1385          : Parent(_map.graph) {}
1386       
1387      };
1388     
1389    private:
1390      const Graph& graph;
1391      ANodeMap<_Value> aNodeMap;
1392      BNodeMap<_Value> bNodeMap;
1393    };
1394   
1395
1396    template <typename _Value>
1397    class EdgeMap
1398      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
1399    public:
1400      typedef BpUGraphExtender Graph;
1401      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
1402   
1403      EdgeMap(const Graph& graph)
1404        : Parent(graph) {}
1405      EdgeMap(const Graph& graph, const _Value& value)
1406        : Parent(graph, value) {}
1407   
1408      EdgeMap& operator=(const EdgeMap& cmap) {
1409        return operator=<EdgeMap>(cmap);
1410      }
1411   
1412      template <typename CMap>
1413      EdgeMap& operator=(const CMap& cmap) {
1414        Parent::operator=(cmap);
1415        return *this;
1416      }
1417    };
1418
1419    template <typename _Value>
1420    class UEdgeMap
1421      : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
1422    public:
1423      typedef BpUGraphExtender Graph;
1424      typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
1425   
1426      UEdgeMap(const Graph& graph)
1427        : Parent(graph) {}
1428      UEdgeMap(const Graph& graph, const _Value& value)
1429        : Parent(graph, value) {}
1430   
1431      UEdgeMap& operator=(const UEdgeMap& cmap) {
1432        return operator=<UEdgeMap>(cmap);
1433      }
1434   
1435      template <typename CMap>
1436      UEdgeMap& operator=(const CMap& cmap) {
1437        Parent::operator=(cmap);
1438        return *this;
1439      }
1440    };
1441
1442 
1443    Node addANode() {
1444      Node node = Parent::addANode();
1445      getNotifier(ANode()).add(node);
1446      getNotifier(Node()).add(node);
1447      return node;
1448    }
1449
1450    Node addBNode() {
1451      Node node = Parent::addBNode();
1452      getNotifier(BNode()).add(node);
1453      getNotifier(Node()).add(node);
1454      return node;
1455    }
1456 
1457    UEdge addEdge(const Node& source, const Node& target) {
1458      UEdge uedge = Parent::addEdge(source, target);
1459      getNotifier(UEdge()).add(uedge);
1460   
1461      std::vector<Edge> edges;
1462      edges.push_back(direct(uedge, true));
1463      edges.push_back(direct(uedge, false));
1464      getNotifier(Edge()).add(edges);
1465   
1466      return uedge;
1467    }
1468
1469    void clear() {
1470      getNotifier(Edge()).clear();
1471      getNotifier(UEdge()).clear();
1472      getNotifier(Node()).clear();
1473      getNotifier(BNode()).clear();
1474      getNotifier(ANode()).clear();
1475      Parent::clear();
1476    }
1477
1478    void erase(const Node& node) {
1479      UEdge uedge;
1480      if (Parent::aNode(node)) {
1481        Parent::firstFromANode(uedge, node);
1482        while (uedge != INVALID) {
1483          erase(uedge);
1484          Parent::firstFromANode(uedge, node);
1485        }
1486        getNotifier(ANode()).erase(node);
1487      } else {
1488        Parent::firstFromBNode(uedge, node);
1489        while (uedge != INVALID) {
1490          erase(uedge);
1491          Parent::firstFromBNode(uedge, node);
1492        }
1493        getNotifier(BNode()).erase(node);
1494      }
1495
1496      getNotifier(Node()).erase(node);
1497      Parent::erase(node);
1498    }
1499   
1500    void erase(const UEdge& uedge) {
1501      std::vector<Edge> edges;
1502      edges.push_back(direct(uedge, true));
1503      edges.push_back(direct(uedge, false));
1504      getNotifier(Edge()).erase(edges);
1505      getNotifier(UEdge()).erase(uedge);
1506      Parent::erase(uedge);
1507    }
1508
1509
1510    BpUGraphExtender() {
1511      anode_notifier.setContainer(*this);
1512      bnode_notifier.setContainer(*this);
1513      node_notifier.setContainer(*this);
1514      edge_notifier.setContainer(*this);
1515      uedge_notifier.setContainer(*this);
1516    }
1517
1518    ~BpUGraphExtender() {
1519      uedge_notifier.clear();
1520      edge_notifier.clear();
1521      node_notifier.clear();
1522      anode_notifier.clear();
1523      bnode_notifier.clear();
1524    }
1525
1526
1527  };
1528
1529}
1530
1531#endif
Note: See TracBrowser for help on using the repository browser.