COIN-OR::LEMON - Graph Library

source: lemon/lemon/bits/graph_extender.h @ 1193:c8fa41fcc4a7

Last change on this file since 1193:c8fa41fcc4a7 was 1193:c8fa41fcc4a7, checked in by Balazs Dezso <deba@…>, 9 years ago

Type safe red and blue node set (#69)

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