COIN-OR::LEMON - Graph Library

source: lemon/lemon/bits/graph_extender.h @ 1343:20f95cd51aba

Last change on this file since 1343:20f95cd51aba was 1336:0759d974de81, checked in by Gabor Gevay <ggab90@…>, 10 years ago

STL style iterators (#325)

For

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