COIN-OR::LEMON - Graph Library

source: lemon/lemon/bits/graph_extender.h

Last change on this file was 1270:dceba191c00d, checked in by Alpar Juttner <alpar@…>, 6 years ago

Apply unify-sources.sh to the source tree

File size: 30.9 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//\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    // Alterable extension
844
845    typedef AlterationNotifier<BpGraphExtender, Node> NodeNotifier;
846    typedef AlterationNotifier<BpGraphExtender, RedNode> RedNodeNotifier;
847    typedef AlterationNotifier<BpGraphExtender, BlueNode> BlueNodeNotifier;
848    typedef AlterationNotifier<BpGraphExtender, Arc> ArcNotifier;
849    typedef AlterationNotifier<BpGraphExtender, Edge> EdgeNotifier;
850
851
852  protected:
853
854    mutable NodeNotifier node_notifier;
855    mutable RedNodeNotifier red_node_notifier;
856    mutable BlueNodeNotifier blue_node_notifier;
857    mutable ArcNotifier arc_notifier;
858    mutable EdgeNotifier edge_notifier;
859
860  public:
861
862    NodeNotifier& notifier(Node) const {
863      return node_notifier;
864    }
865
866    RedNodeNotifier& notifier(RedNode) const {
867      return red_node_notifier;
868    }
869
870    BlueNodeNotifier& notifier(BlueNode) const {
871      return blue_node_notifier;
872    }
873
874    ArcNotifier& notifier(Arc) const {
875      return arc_notifier;
876    }
877
878    EdgeNotifier& notifier(Edge) const {
879      return edge_notifier;
880    }
881
882
883
884    class NodeIt : public Node {
885      const BpGraph* _graph;
886    public:
887
888      NodeIt() {}
889
890      NodeIt(Invalid i) : Node(i) { }
891
892      explicit NodeIt(const BpGraph& graph) : _graph(&graph) {
893        _graph->first(static_cast<Node&>(*this));
894      }
895
896      NodeIt(const BpGraph& graph, const Node& node)
897        : Node(node), _graph(&graph) {}
898
899      NodeIt& operator++() {
900        _graph->next(*this);
901        return *this;
902      }
903
904    };
905
906    class RedNodeIt : public RedNode {
907      const BpGraph* _graph;
908    public:
909
910      RedNodeIt() {}
911
912      RedNodeIt(Invalid i) : RedNode(i) { }
913
914      explicit RedNodeIt(const BpGraph& graph) : _graph(&graph) {
915        _graph->first(static_cast<RedNode&>(*this));
916      }
917
918      RedNodeIt(const BpGraph& graph, const RedNode& node)
919        : RedNode(node), _graph(&graph) {}
920
921      RedNodeIt& operator++() {
922        _graph->next(static_cast<RedNode&>(*this));
923        return *this;
924      }
925
926    };
927
928    class BlueNodeIt : public BlueNode {
929      const BpGraph* _graph;
930    public:
931
932      BlueNodeIt() {}
933
934      BlueNodeIt(Invalid i) : BlueNode(i) { }
935
936      explicit BlueNodeIt(const BpGraph& graph) : _graph(&graph) {
937        _graph->first(static_cast<BlueNode&>(*this));
938      }
939
940      BlueNodeIt(const BpGraph& graph, const BlueNode& node)
941        : BlueNode(node), _graph(&graph) {}
942
943      BlueNodeIt& operator++() {
944        _graph->next(static_cast<BlueNode&>(*this));
945        return *this;
946      }
947
948    };
949
950
951    class ArcIt : public Arc {
952      const BpGraph* _graph;
953    public:
954
955      ArcIt() { }
956
957      ArcIt(Invalid i) : Arc(i) { }
958
959      explicit ArcIt(const BpGraph& graph) : _graph(&graph) {
960        _graph->first(static_cast<Arc&>(*this));
961      }
962
963      ArcIt(const BpGraph& graph, const Arc& arc) :
964        Arc(arc), _graph(&graph) { }
965
966      ArcIt& operator++() {
967        _graph->next(*this);
968        return *this;
969      }
970
971    };
972
973
974    class OutArcIt : public Arc {
975      const BpGraph* _graph;
976    public:
977
978      OutArcIt() { }
979
980      OutArcIt(Invalid i) : Arc(i) { }
981
982      OutArcIt(const BpGraph& graph, const Node& node)
983        : _graph(&graph) {
984        _graph->firstOut(*this, node);
985      }
986
987      OutArcIt(const BpGraph& graph, const Arc& arc)
988        : Arc(arc), _graph(&graph) {}
989
990      OutArcIt& operator++() {
991        _graph->nextOut(*this);
992        return *this;
993      }
994
995    };
996
997
998    class InArcIt : public Arc {
999      const BpGraph* _graph;
1000    public:
1001
1002      InArcIt() { }
1003
1004      InArcIt(Invalid i) : Arc(i) { }
1005
1006      InArcIt(const BpGraph& graph, const Node& node)
1007        : _graph(&graph) {
1008        _graph->firstIn(*this, node);
1009      }
1010
1011      InArcIt(const BpGraph& graph, const Arc& arc) :
1012        Arc(arc), _graph(&graph) {}
1013
1014      InArcIt& operator++() {
1015        _graph->nextIn(*this);
1016        return *this;
1017      }
1018
1019    };
1020
1021
1022    class EdgeIt : public Parent::Edge {
1023      const BpGraph* _graph;
1024    public:
1025
1026      EdgeIt() { }
1027
1028      EdgeIt(Invalid i) : Edge(i) { }
1029
1030      explicit EdgeIt(const BpGraph& graph) : _graph(&graph) {
1031        _graph->first(static_cast<Edge&>(*this));
1032      }
1033
1034      EdgeIt(const BpGraph& graph, const Edge& edge) :
1035        Edge(edge), _graph(&graph) { }
1036
1037      EdgeIt& operator++() {
1038        _graph->next(*this);
1039        return *this;
1040      }
1041
1042    };
1043
1044    class IncEdgeIt : public Parent::Edge {
1045      friend class BpGraphExtender;
1046      const BpGraph* _graph;
1047      bool _direction;
1048    public:
1049
1050      IncEdgeIt() { }
1051
1052      IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
1053
1054      IncEdgeIt(const BpGraph& graph, const Node &node) : _graph(&graph) {
1055        _graph->firstInc(*this, _direction, node);
1056      }
1057
1058      IncEdgeIt(const BpGraph& graph, const Edge &edge, const Node &node)
1059        : _graph(&graph), Edge(edge) {
1060        _direction = (_graph->source(edge) == node);
1061      }
1062
1063      IncEdgeIt& operator++() {
1064        _graph->nextInc(*this, _direction);
1065        return *this;
1066      }
1067    };
1068
1069    // \brief Base node of the iterator
1070    //
1071    // Returns the base node (ie. the source in this case) of the iterator
1072    Node baseNode(const OutArcIt &arc) const {
1073      return Parent::source(static_cast<const Arc&>(arc));
1074    }
1075    // \brief Running node of the iterator
1076    //
1077    // Returns the running node (ie. the target in this case) of the
1078    // iterator
1079    Node runningNode(const OutArcIt &arc) const {
1080      return Parent::target(static_cast<const Arc&>(arc));
1081    }
1082
1083    // \brief Base node of the iterator
1084    //
1085    // Returns the base node (ie. the target in this case) of the iterator
1086    Node baseNode(const InArcIt &arc) const {
1087      return Parent::target(static_cast<const Arc&>(arc));
1088    }
1089    // \brief Running node of the iterator
1090    //
1091    // Returns the running node (ie. the source in this case) of the
1092    // iterator
1093    Node runningNode(const InArcIt &arc) const {
1094      return Parent::source(static_cast<const Arc&>(arc));
1095    }
1096
1097    // Base node of the iterator
1098    //
1099    // Returns the base node of the iterator
1100    Node baseNode(const IncEdgeIt &edge) const {
1101      return edge._direction ? this->u(edge) : this->v(edge);
1102    }
1103    // Running node of the iterator
1104    //
1105    // Returns the running node of the iterator
1106    Node runningNode(const IncEdgeIt &edge) const {
1107      return edge._direction ? this->v(edge) : this->u(edge);
1108    }
1109
1110    // Mappable extension
1111
1112    template <typename _Value>
1113    class NodeMap
1114      : public MapExtender<DefaultMap<BpGraph, Node, _Value> > {
1115      typedef MapExtender<DefaultMap<BpGraph, Node, _Value> > Parent;
1116
1117    public:
1118      explicit NodeMap(const BpGraph& bpgraph)
1119        : Parent(bpgraph) {}
1120      NodeMap(const BpGraph& bpgraph, const _Value& value)
1121        : Parent(bpgraph, value) {}
1122
1123    private:
1124      NodeMap& operator=(const NodeMap& cmap) {
1125        return operator=<NodeMap>(cmap);
1126      }
1127
1128      template <typename CMap>
1129      NodeMap& operator=(const CMap& cmap) {
1130        Parent::operator=(cmap);
1131        return *this;
1132      }
1133
1134    };
1135
1136    template <typename _Value>
1137    class RedNodeMap
1138      : public MapExtender<DefaultMap<BpGraph, RedNode, _Value> > {
1139      typedef MapExtender<DefaultMap<BpGraph, RedNode, _Value> > Parent;
1140
1141    public:
1142      explicit RedNodeMap(const BpGraph& bpgraph)
1143        : Parent(bpgraph) {}
1144      RedNodeMap(const BpGraph& bpgraph, const _Value& value)
1145        : Parent(bpgraph, value) {}
1146
1147    private:
1148      RedNodeMap& operator=(const RedNodeMap& cmap) {
1149        return operator=<RedNodeMap>(cmap);
1150      }
1151
1152      template <typename CMap>
1153      RedNodeMap& operator=(const CMap& cmap) {
1154        Parent::operator=(cmap);
1155        return *this;
1156      }
1157
1158    };
1159
1160    template <typename _Value>
1161    class BlueNodeMap
1162      : public MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > {
1163      typedef MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > Parent;
1164
1165    public:
1166      explicit BlueNodeMap(const BpGraph& bpgraph)
1167        : Parent(bpgraph) {}
1168      BlueNodeMap(const BpGraph& bpgraph, const _Value& value)
1169        : Parent(bpgraph, value) {}
1170
1171    private:
1172      BlueNodeMap& operator=(const BlueNodeMap& cmap) {
1173        return operator=<BlueNodeMap>(cmap);
1174      }
1175
1176      template <typename CMap>
1177      BlueNodeMap& operator=(const CMap& cmap) {
1178        Parent::operator=(cmap);
1179        return *this;
1180      }
1181
1182    };
1183
1184    template <typename _Value>
1185    class ArcMap
1186      : public MapExtender<DefaultMap<BpGraph, Arc, _Value> > {
1187      typedef MapExtender<DefaultMap<BpGraph, Arc, _Value> > Parent;
1188
1189    public:
1190      explicit ArcMap(const BpGraph& graph)
1191        : Parent(graph) {}
1192      ArcMap(const BpGraph& graph, const _Value& value)
1193        : Parent(graph, value) {}
1194
1195    private:
1196      ArcMap& operator=(const ArcMap& cmap) {
1197        return operator=<ArcMap>(cmap);
1198      }
1199
1200      template <typename CMap>
1201      ArcMap& operator=(const CMap& cmap) {
1202        Parent::operator=(cmap);
1203        return *this;
1204      }
1205    };
1206
1207
1208    template <typename _Value>
1209    class EdgeMap
1210      : public MapExtender<DefaultMap<BpGraph, Edge, _Value> > {
1211      typedef MapExtender<DefaultMap<BpGraph, Edge, _Value> > Parent;
1212
1213    public:
1214      explicit EdgeMap(const BpGraph& graph)
1215        : Parent(graph) {}
1216
1217      EdgeMap(const BpGraph& graph, const _Value& value)
1218        : Parent(graph, value) {}
1219
1220    private:
1221      EdgeMap& operator=(const EdgeMap& cmap) {
1222        return operator=<EdgeMap>(cmap);
1223      }
1224
1225      template <typename CMap>
1226      EdgeMap& operator=(const CMap& cmap) {
1227        Parent::operator=(cmap);
1228        return *this;
1229      }
1230
1231    };
1232
1233    // Alteration extension
1234
1235    RedNode addRedNode() {
1236      RedNode node = Parent::addRedNode();
1237      notifier(RedNode()).add(node);
1238      notifier(Node()).add(node);
1239      return node;
1240    }
1241
1242    BlueNode addBlueNode() {
1243      BlueNode node = Parent::addBlueNode();
1244      notifier(BlueNode()).add(node);
1245      notifier(Node()).add(node);
1246      return node;
1247    }
1248
1249    Edge addEdge(const RedNode& from, const BlueNode& to) {
1250      Edge edge = Parent::addEdge(from, to);
1251      notifier(Edge()).add(edge);
1252      std::vector<Arc> av;
1253      av.push_back(Parent::direct(edge, true));
1254      av.push_back(Parent::direct(edge, false));
1255      notifier(Arc()).add(av);
1256      return edge;
1257    }
1258
1259    void clear() {
1260      notifier(Arc()).clear();
1261      notifier(Edge()).clear();
1262      notifier(Node()).clear();
1263      notifier(BlueNode()).clear();
1264      notifier(RedNode()).clear();
1265      Parent::clear();
1266    }
1267
1268    template <typename BpGraph, typename NodeRefMap, typename EdgeRefMap>
1269    void build(const BpGraph& graph, NodeRefMap& nodeRef,
1270               EdgeRefMap& edgeRef) {
1271      Parent::build(graph, nodeRef, edgeRef);
1272      notifier(RedNode()).build();
1273      notifier(BlueNode()).build();
1274      notifier(Node()).build();
1275      notifier(Edge()).build();
1276      notifier(Arc()).build();
1277    }
1278
1279    void erase(const Node& node) {
1280      Arc arc;
1281      Parent::firstOut(arc, node);
1282      while (arc != INVALID ) {
1283        erase(arc);
1284        Parent::firstOut(arc, node);
1285      }
1286
1287      Parent::firstIn(arc, node);
1288      while (arc != INVALID ) {
1289        erase(arc);
1290        Parent::firstIn(arc, node);
1291      }
1292
1293      if (Parent::red(node)) {
1294        notifier(RedNode()).erase(this->asRedNodeUnsafe(node));
1295      } else {
1296        notifier(BlueNode()).erase(this->asBlueNodeUnsafe(node));
1297      }
1298
1299      notifier(Node()).erase(node);
1300      Parent::erase(node);
1301    }
1302
1303    void erase(const Edge& edge) {
1304      std::vector<Arc> av;
1305      av.push_back(Parent::direct(edge, true));
1306      av.push_back(Parent::direct(edge, false));
1307      notifier(Arc()).erase(av);
1308      notifier(Edge()).erase(edge);
1309      Parent::erase(edge);
1310    }
1311
1312    BpGraphExtender() {
1313      red_node_notifier.setContainer(*this);
1314      blue_node_notifier.setContainer(*this);
1315      node_notifier.setContainer(*this);
1316      arc_notifier.setContainer(*this);
1317      edge_notifier.setContainer(*this);
1318    }
1319
1320    ~BpGraphExtender() {
1321      edge_notifier.clear();
1322      arc_notifier.clear();
1323      node_notifier.clear();
1324      blue_node_notifier.clear();
1325      red_node_notifier.clear();
1326    }
1327
1328  };
1329
1330}
1331
1332#endif
Note: See TracBrowser for help on using the repository browser.