COIN-OR::LEMON - Graph Library

source: lemon/lemon/bits/graph_extender.h @ 1188:5ef0ab7b61cd

Last change on this file since 1188:5ef0ab7b61cd was 1188:5ef0ab7b61cd, checked in by Balazs Dezso <deba@…>, 10 years ago

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