COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/graph_extender.h @ 2585:20d42311e344

Last change on this file since 2585:20d42311e344 was 2585:20d42311e344, checked in by Balazs Dezso, 17 years ago

Backport of bug fix hg 2de55e4f57a7

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