COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/graph_extender.h @ 2260:4274224f8a7d

Last change on this file since 2260:4274224f8a7d was 2260:4274224f8a7d, checked in by Alpar Juttner, 17 years ago

concept -> concepts (namespace & directory)

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