COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/graph_extender.h @ 1999:2ff283124dfc

Last change on this file since 1999:2ff283124dfc was 1999:2ff283124dfc, checked in by Balazs Dezso, 13 years ago

Clarifing alteration observing system
It is directly connected now to a container

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