1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2009
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_BITS_GRAPH_EXTENDER_H
20 #define LEMON_BITS_GRAPH_EXTENDER_H
22 #include <lemon/core.h>
24 #include <lemon/bits/map_extender.h>
25 #include <lemon/bits/default_map.h>
27 #include <lemon/concept_check.h>
28 #include <lemon/concepts/maps.h>
32 //\brief Extenders for the graph types
37 // \brief Extender for the digraph implementations
38 template <typename Base>
39 class DigraphExtender : public Base {
44 typedef DigraphExtender Digraph;
48 typedef typename Parent::Node Node;
49 typedef typename Parent::Arc Arc;
51 int maxId(Node) const {
52 return Parent::maxNodeId();
55 int maxId(Arc) const {
56 return Parent::maxArcId();
59 static Node fromId(int id, Node) {
60 return Parent::nodeFromId(id);
63 static Arc fromId(int id, Arc) {
64 return Parent::arcFromId(id);
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);
76 // Alterable extension
78 typedef AlterationNotifier<DigraphExtender, Node> NodeNotifier;
79 typedef AlterationNotifier<DigraphExtender, Arc> ArcNotifier;
84 mutable NodeNotifier node_notifier;
85 mutable ArcNotifier arc_notifier;
89 NodeNotifier& notifier(Node) const {
93 ArcNotifier& notifier(Arc) const {
97 class NodeIt : public Node {
98 const Digraph* _digraph;
103 NodeIt(Invalid i) : Node(i) { }
105 explicit NodeIt(const Digraph& digraph) : _digraph(&digraph) {
106 _digraph->first(static_cast<Node&>(*this));
109 NodeIt(const Digraph& digraph, const Node& node)
110 : Node(node), _digraph(&digraph) {}
112 NodeIt& operator++() {
113 _digraph->next(*this);
120 class ArcIt : public Arc {
121 const Digraph* _digraph;
126 ArcIt(Invalid i) : Arc(i) { }
128 explicit ArcIt(const Digraph& digraph) : _digraph(&digraph) {
129 _digraph->first(static_cast<Arc&>(*this));
132 ArcIt(const Digraph& digraph, const Arc& arc) :
133 Arc(arc), _digraph(&digraph) { }
135 ArcIt& operator++() {
136 _digraph->next(*this);
143 class OutArcIt : public Arc {
144 const Digraph* _digraph;
149 OutArcIt(Invalid i) : Arc(i) { }
151 OutArcIt(const Digraph& digraph, const Node& node)
152 : _digraph(&digraph) {
153 _digraph->firstOut(*this, node);
156 OutArcIt(const Digraph& digraph, const Arc& arc)
157 : Arc(arc), _digraph(&digraph) {}
159 OutArcIt& operator++() {
160 _digraph->nextOut(*this);
167 class InArcIt : public Arc {
168 const Digraph* _digraph;
173 InArcIt(Invalid i) : Arc(i) { }
175 InArcIt(const Digraph& digraph, const Node& node)
176 : _digraph(&digraph) {
177 _digraph->firstIn(*this, node);
180 InArcIt(const Digraph& digraph, const Arc& arc) :
181 Arc(arc), _digraph(&digraph) {}
183 InArcIt& operator++() {
184 _digraph->nextIn(*this);
190 // \brief Base node of the iterator
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);
196 // \brief Running node of the iterator
198 // Returns the running node (i.e. the target in this case) of the
200 Node runningNode(const OutArcIt &arc) const {
201 return Parent::target(arc);
204 // \brief Base node of the iterator
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);
210 // \brief Running node of the iterator
212 // Returns the running node (i.e. the source in this case) of the
214 Node runningNode(const InArcIt &arc) const {
215 return Parent::source(arc);
219 template <typename _Value>
221 : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
222 typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
225 explicit NodeMap(const Digraph& digraph)
227 NodeMap(const Digraph& digraph, const _Value& value)
228 : Parent(digraph, value) {}
231 NodeMap& operator=(const NodeMap& cmap) {
232 return operator=<NodeMap>(cmap);
235 template <typename CMap>
236 NodeMap& operator=(const CMap& cmap) {
237 Parent::operator=(cmap);
243 template <typename _Value>
245 : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
246 typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
249 explicit ArcMap(const Digraph& digraph)
251 ArcMap(const Digraph& digraph, const _Value& value)
252 : Parent(digraph, value) {}
255 ArcMap& operator=(const ArcMap& cmap) {
256 return operator=<ArcMap>(cmap);
259 template <typename CMap>
260 ArcMap& operator=(const CMap& cmap) {
261 Parent::operator=(cmap);
268 Node node = Parent::addNode();
269 notifier(Node()).add(node);
273 Arc addArc(const Node& from, const Node& to) {
274 Arc arc = Parent::addArc(from, to);
275 notifier(Arc()).add(arc);
280 notifier(Arc()).clear();
281 notifier(Node()).clear();
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();
292 void erase(const Node& node) {
294 Parent::firstOut(arc, node);
295 while (arc != INVALID ) {
297 Parent::firstOut(arc, node);
300 Parent::firstIn(arc, node);
301 while (arc != INVALID ) {
303 Parent::firstIn(arc, node);
306 notifier(Node()).erase(node);
310 void erase(const Arc& arc) {
311 notifier(Arc()).erase(arc);
316 node_notifier.setContainer(*this);
317 arc_notifier.setContainer(*this);
322 arc_notifier.clear();
323 node_notifier.clear();
327 // \ingroup _graphbits
329 // \brief Extender for the Graphs
330 template <typename Base>
331 class GraphExtender : public Base {
336 typedef GraphExtender Graph;
338 typedef True UndirectedTag;
340 typedef typename Parent::Node Node;
341 typedef typename Parent::Arc Arc;
342 typedef typename Parent::Edge Edge;
346 int maxId(Node) const {
347 return Parent::maxNodeId();
350 int maxId(Arc) const {
351 return Parent::maxArcId();
354 int maxId(Edge) const {
355 return Parent::maxEdgeId();
358 static Node fromId(int id, Node) {
359 return Parent::nodeFromId(id);
362 static Arc fromId(int id, Arc) {
363 return Parent::arcFromId(id);
366 static Edge fromId(int id, Edge) {
367 return Parent::edgeFromId(id);
370 Node oppositeNode(const Node &n, const Edge &e) const {
371 if( n == Parent::u(e))
373 else if( n == Parent::v(e))
379 Arc oppositeArc(const Arc &arc) const {
380 return Parent::direct(arc, !Parent::direction(arc));
383 using Parent::direct;
384 Arc direct(const Edge &edge, const Node &node) const {
385 return Parent::direct(edge, Parent::u(edge) == node);
388 // Alterable extension
390 typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
391 typedef AlterationNotifier<GraphExtender, Arc> ArcNotifier;
392 typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;
397 mutable NodeNotifier node_notifier;
398 mutable ArcNotifier arc_notifier;
399 mutable EdgeNotifier edge_notifier;
403 NodeNotifier& notifier(Node) const {
404 return node_notifier;
407 ArcNotifier& notifier(Arc) const {
411 EdgeNotifier& notifier(Edge) const {
412 return edge_notifier;
417 class NodeIt : public Node {
423 NodeIt(Invalid i) : Node(i) { }
425 explicit NodeIt(const Graph& graph) : _graph(&graph) {
426 _graph->first(static_cast<Node&>(*this));
429 NodeIt(const Graph& graph, const Node& node)
430 : Node(node), _graph(&graph) {}
432 NodeIt& operator++() {
440 class ArcIt : public Arc {
446 ArcIt(Invalid i) : Arc(i) { }
448 explicit ArcIt(const Graph& graph) : _graph(&graph) {
449 _graph->first(static_cast<Arc&>(*this));
452 ArcIt(const Graph& graph, const Arc& arc) :
453 Arc(arc), _graph(&graph) { }
455 ArcIt& operator++() {
463 class OutArcIt : public Arc {
469 OutArcIt(Invalid i) : Arc(i) { }
471 OutArcIt(const Graph& graph, const Node& node)
473 _graph->firstOut(*this, node);
476 OutArcIt(const Graph& graph, const Arc& arc)
477 : Arc(arc), _graph(&graph) {}
479 OutArcIt& operator++() {
480 _graph->nextOut(*this);
487 class InArcIt : public Arc {
493 InArcIt(Invalid i) : Arc(i) { }
495 InArcIt(const Graph& graph, const Node& node)
497 _graph->firstIn(*this, node);
500 InArcIt(const Graph& graph, const Arc& arc) :
501 Arc(arc), _graph(&graph) {}
503 InArcIt& operator++() {
504 _graph->nextIn(*this);
511 class EdgeIt : public Parent::Edge {
517 EdgeIt(Invalid i) : Edge(i) { }
519 explicit EdgeIt(const Graph& graph) : _graph(&graph) {
520 _graph->first(static_cast<Edge&>(*this));
523 EdgeIt(const Graph& graph, const Edge& edge) :
524 Edge(edge), _graph(&graph) { }
526 EdgeIt& operator++() {
533 class IncEdgeIt : public Parent::Edge {
534 friend class GraphExtender;
541 IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
543 IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) {
544 _graph->firstInc(*this, _direction, node);
547 IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node)
548 : _graph(&graph), Edge(edge) {
549 _direction = (_graph->source(edge) == node);
552 IncEdgeIt& operator++() {
553 _graph->nextInc(*this, _direction);
558 // \brief Base node of the iterator
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));
564 // \brief Running node of the iterator
566 // Returns the running node (ie. the target in this case) of the
568 Node runningNode(const OutArcIt &arc) const {
569 return Parent::target(static_cast<const Arc&>(arc));
572 // \brief Base node of the iterator
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));
578 // \brief Running node of the iterator
580 // Returns the running node (ie. the source in this case) of the
582 Node runningNode(const InArcIt &arc) const {
583 return Parent::source(static_cast<const Arc&>(arc));
586 // Base node of the iterator
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);
592 // Running node of the iterator
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);
599 // Mappable extension
601 template <typename _Value>
603 : public MapExtender<DefaultMap<Graph, Node, _Value> > {
604 typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
607 explicit NodeMap(const Graph& graph)
609 NodeMap(const Graph& graph, const _Value& value)
610 : Parent(graph, value) {}
613 NodeMap& operator=(const NodeMap& cmap) {
614 return operator=<NodeMap>(cmap);
617 template <typename CMap>
618 NodeMap& operator=(const CMap& cmap) {
619 Parent::operator=(cmap);
625 template <typename _Value>
627 : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
628 typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
631 explicit ArcMap(const Graph& graph)
633 ArcMap(const Graph& graph, const _Value& value)
634 : Parent(graph, value) {}
637 ArcMap& operator=(const ArcMap& cmap) {
638 return operator=<ArcMap>(cmap);
641 template <typename CMap>
642 ArcMap& operator=(const CMap& cmap) {
643 Parent::operator=(cmap);
649 template <typename _Value>
651 : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
652 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
655 explicit EdgeMap(const Graph& graph)
658 EdgeMap(const Graph& graph, const _Value& value)
659 : Parent(graph, value) {}
662 EdgeMap& operator=(const EdgeMap& cmap) {
663 return operator=<EdgeMap>(cmap);
666 template <typename CMap>
667 EdgeMap& operator=(const CMap& cmap) {
668 Parent::operator=(cmap);
674 // Alteration extension
677 Node node = Parent::addNode();
678 notifier(Node()).add(node);
682 Edge addEdge(const Node& from, const Node& to) {
683 Edge edge = Parent::addEdge(from, to);
684 notifier(Edge()).add(edge);
686 ev.push_back(Parent::direct(edge, true));
687 ev.push_back(Parent::direct(edge, false));
688 notifier(Arc()).add(ev);
693 notifier(Arc()).clear();
694 notifier(Edge()).clear();
695 notifier(Node()).clear();
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();
708 void erase(const Node& node) {
710 Parent::firstOut(arc, node);
711 while (arc != INVALID ) {
713 Parent::firstOut(arc, node);
716 Parent::firstIn(arc, node);
717 while (arc != INVALID ) {
719 Parent::firstIn(arc, node);
722 notifier(Node()).erase(node);
726 void erase(const Edge& edge) {
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);
736 node_notifier.setContainer(*this);
737 arc_notifier.setContainer(*this);
738 edge_notifier.setContainer(*this);
742 edge_notifier.clear();
743 arc_notifier.clear();
744 node_notifier.clear();
749 // \ingroup _graphbits
751 // \brief Extender for the BpGraphs
752 template <typename Base>
753 class BpGraphExtender : public Base {
758 typedef BpGraphExtender BpGraph;
760 typedef True UndirectedTag;
762 typedef typename Parent::Node Node;
763 typedef typename Parent::Arc Arc;
764 typedef typename Parent::Edge Edge;
768 class RedNode : public Node {
771 RedNode(const RedNode& node) : Node(node) {}
772 RedNode(Invalid) : Node(INVALID){}
773 RedNode(const Node& node) : Node(node) {}
775 class BlueNode : public Node {
778 BlueNode(const BlueNode& node) : Node(node) {}
779 BlueNode(Invalid) : Node(INVALID){}
780 BlueNode(const Node& node) : Node(node) {}
786 void first(RedNode& node) const {
787 Parent::firstRed(node);
790 void next(RedNode& node) const {
791 Parent::nextRed(node);
794 void first(BlueNode& node) const {
795 Parent::firstBlue(node);
798 void next(BlueNode& node) const {
799 Parent::nextBlue(node);
804 int id(const RedNode& node) const {
805 return Parent::redId(node);
808 int id(const BlueNode& node) const {
809 return Parent::blueId(node);
812 int maxId(Node) const {
813 return Parent::maxNodeId();
816 int maxId(RedNode) const {
817 return Parent::maxRedId();
820 int maxId(BlueNode) const {
821 return Parent::maxBlueId();
824 int maxId(Arc) const {
825 return Parent::maxArcId();
828 int maxId(Edge) const {
829 return Parent::maxEdgeId();
832 static Node fromId(int id, Node) {
833 return Parent::nodeFromId(id);
836 static Arc fromId(int id, Arc) {
837 return Parent::arcFromId(id);
840 static Edge fromId(int id, Edge) {
841 return Parent::edgeFromId(id);
844 Node oppositeNode(const Node &n, const Edge &e) const {
845 if( n == Parent::u(e))
847 else if( n == Parent::v(e))
853 Arc oppositeArc(const Arc &arc) const {
854 return Parent::direct(arc, !Parent::direction(arc));
857 using Parent::direct;
858 Arc direct(const Edge &edge, const Node &node) const {
859 return Parent::direct(edge, Parent::u(edge) == node);
862 // Alterable extension
864 typedef AlterationNotifier<BpGraphExtender, Node> NodeNotifier;
865 typedef AlterationNotifier<BpGraphExtender, RedNode> RedNodeNotifier;
866 typedef AlterationNotifier<BpGraphExtender, BlueNode> BlueNodeNotifier;
867 typedef AlterationNotifier<BpGraphExtender, Arc> ArcNotifier;
868 typedef AlterationNotifier<BpGraphExtender, Edge> EdgeNotifier;
873 mutable NodeNotifier node_notifier;
874 mutable RedNodeNotifier red_node_notifier;
875 mutable BlueNodeNotifier blue_node_notifier;
876 mutable ArcNotifier arc_notifier;
877 mutable EdgeNotifier edge_notifier;
881 NodeNotifier& notifier(Node) const {
882 return node_notifier;
885 RedNodeNotifier& notifier(RedNode) const {
886 return red_node_notifier;
889 BlueNodeNotifier& notifier(BlueNode) const {
890 return blue_node_notifier;
893 ArcNotifier& notifier(Arc) const {
897 EdgeNotifier& notifier(Edge) const {
898 return edge_notifier;
903 class NodeIt : public Node {
904 const BpGraph* _graph;
909 NodeIt(Invalid i) : Node(i) { }
911 explicit NodeIt(const BpGraph& graph) : _graph(&graph) {
912 _graph->first(static_cast<Node&>(*this));
915 NodeIt(const BpGraph& graph, const Node& node)
916 : Node(node), _graph(&graph) {}
918 NodeIt& operator++() {
925 class RedIt : public Node {
926 const BpGraph* _graph;
931 RedIt(Invalid i) : Node(i) { }
933 explicit RedIt(const BpGraph& graph) : _graph(&graph) {
934 _graph->firstRed(static_cast<Node&>(*this));
937 RedIt(const BpGraph& graph, const Node& node)
938 : Node(node), _graph(&graph) {
939 LEMON_DEBUG(_graph->red(node), "Node has to be red.");
942 RedIt& operator++() {
943 _graph->nextRed(*this);
949 class BlueIt : public Node {
950 const BpGraph* _graph;
955 BlueIt(Invalid i) : Node(i) { }
957 explicit BlueIt(const BpGraph& graph) : _graph(&graph) {
958 _graph->firstBlue(static_cast<Node&>(*this));
961 BlueIt(const BpGraph& graph, const Node& node)
962 : Node(node), _graph(&graph) {
963 LEMON_DEBUG(_graph->blue(node), "Node has to be blue.");
966 BlueIt& operator++() {
967 _graph->nextBlue(*this);
974 class ArcIt : public Arc {
975 const BpGraph* _graph;
980 ArcIt(Invalid i) : Arc(i) { }
982 explicit ArcIt(const BpGraph& graph) : _graph(&graph) {
983 _graph->first(static_cast<Arc&>(*this));
986 ArcIt(const BpGraph& graph, const Arc& arc) :
987 Arc(arc), _graph(&graph) { }
989 ArcIt& operator++() {
997 class OutArcIt : public Arc {
998 const BpGraph* _graph;
1003 OutArcIt(Invalid i) : Arc(i) { }
1005 OutArcIt(const BpGraph& graph, const Node& node)
1007 _graph->firstOut(*this, node);
1010 OutArcIt(const BpGraph& graph, const Arc& arc)
1011 : Arc(arc), _graph(&graph) {}
1013 OutArcIt& operator++() {
1014 _graph->nextOut(*this);
1021 class InArcIt : public Arc {
1022 const BpGraph* _graph;
1027 InArcIt(Invalid i) : Arc(i) { }
1029 InArcIt(const BpGraph& graph, const Node& node)
1031 _graph->firstIn(*this, node);
1034 InArcIt(const BpGraph& graph, const Arc& arc) :
1035 Arc(arc), _graph(&graph) {}
1037 InArcIt& operator++() {
1038 _graph->nextIn(*this);
1045 class EdgeIt : public Parent::Edge {
1046 const BpGraph* _graph;
1051 EdgeIt(Invalid i) : Edge(i) { }
1053 explicit EdgeIt(const BpGraph& graph) : _graph(&graph) {
1054 _graph->first(static_cast<Edge&>(*this));
1057 EdgeIt(const BpGraph& graph, const Edge& edge) :
1058 Edge(edge), _graph(&graph) { }
1060 EdgeIt& operator++() {
1061 _graph->next(*this);
1067 class IncEdgeIt : public Parent::Edge {
1068 friend class BpGraphExtender;
1069 const BpGraph* _graph;
1075 IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
1077 IncEdgeIt(const BpGraph& graph, const Node &node) : _graph(&graph) {
1078 _graph->firstInc(*this, _direction, node);
1081 IncEdgeIt(const BpGraph& graph, const Edge &edge, const Node &node)
1082 : _graph(&graph), Edge(edge) {
1083 _direction = (_graph->source(edge) == node);
1086 IncEdgeIt& operator++() {
1087 _graph->nextInc(*this, _direction);
1092 // \brief Base node of the iterator
1094 // Returns the base node (ie. the source in this case) of the iterator
1095 Node baseNode(const OutArcIt &arc) const {
1096 return Parent::source(static_cast<const Arc&>(arc));
1098 // \brief Running node of the iterator
1100 // Returns the running node (ie. the target in this case) of the
1102 Node runningNode(const OutArcIt &arc) const {
1103 return Parent::target(static_cast<const Arc&>(arc));
1106 // \brief Base node of the iterator
1108 // Returns the base node (ie. the target in this case) of the iterator
1109 Node baseNode(const InArcIt &arc) const {
1110 return Parent::target(static_cast<const Arc&>(arc));
1112 // \brief Running node of the iterator
1114 // Returns the running node (ie. the source in this case) of the
1116 Node runningNode(const InArcIt &arc) const {
1117 return Parent::source(static_cast<const Arc&>(arc));
1120 // Base node of the iterator
1122 // Returns the base node of the iterator
1123 Node baseNode(const IncEdgeIt &edge) const {
1124 return edge._direction ? this->u(edge) : this->v(edge);
1126 // Running node of the iterator
1128 // Returns the running node of the iterator
1129 Node runningNode(const IncEdgeIt &edge) const {
1130 return edge._direction ? this->v(edge) : this->u(edge);
1133 // Mappable extension
1135 template <typename _Value>
1137 : public MapExtender<DefaultMap<BpGraph, Node, _Value> > {
1138 typedef MapExtender<DefaultMap<BpGraph, Node, _Value> > Parent;
1141 explicit NodeMap(const BpGraph& bpgraph)
1142 : Parent(bpgraph) {}
1143 NodeMap(const BpGraph& bpgraph, const _Value& value)
1144 : Parent(bpgraph, value) {}
1147 NodeMap& operator=(const NodeMap& cmap) {
1148 return operator=<NodeMap>(cmap);
1151 template <typename CMap>
1152 NodeMap& operator=(const CMap& cmap) {
1153 Parent::operator=(cmap);
1159 template <typename _Value>
1161 : public MapExtender<DefaultMap<BpGraph, RedNode, _Value> > {
1162 typedef MapExtender<DefaultMap<BpGraph, RedNode, _Value> > Parent;
1165 explicit RedMap(const BpGraph& bpgraph)
1166 : Parent(bpgraph) {}
1167 RedMap(const BpGraph& bpgraph, const _Value& value)
1168 : Parent(bpgraph, value) {}
1171 RedMap& operator=(const RedMap& cmap) {
1172 return operator=<RedMap>(cmap);
1175 template <typename CMap>
1176 RedMap& operator=(const CMap& cmap) {
1177 Parent::operator=(cmap);
1183 template <typename _Value>
1185 : public MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > {
1186 typedef MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > Parent;
1189 explicit BlueMap(const BpGraph& bpgraph)
1190 : Parent(bpgraph) {}
1191 BlueMap(const BpGraph& bpgraph, const _Value& value)
1192 : Parent(bpgraph, value) {}
1195 BlueMap& operator=(const BlueMap& cmap) {
1196 return operator=<BlueMap>(cmap);
1199 template <typename CMap>
1200 BlueMap& operator=(const CMap& cmap) {
1201 Parent::operator=(cmap);
1207 template <typename _Value>
1209 : public MapExtender<DefaultMap<BpGraph, Arc, _Value> > {
1210 typedef MapExtender<DefaultMap<BpGraph, Arc, _Value> > Parent;
1213 explicit ArcMap(const BpGraph& graph)
1215 ArcMap(const BpGraph& graph, const _Value& value)
1216 : Parent(graph, value) {}
1219 ArcMap& operator=(const ArcMap& cmap) {
1220 return operator=<ArcMap>(cmap);
1223 template <typename CMap>
1224 ArcMap& operator=(const CMap& cmap) {
1225 Parent::operator=(cmap);
1231 template <typename _Value>
1233 : public MapExtender<DefaultMap<BpGraph, Edge, _Value> > {
1234 typedef MapExtender<DefaultMap<BpGraph, Edge, _Value> > Parent;
1237 explicit EdgeMap(const BpGraph& graph)
1240 EdgeMap(const BpGraph& graph, const _Value& value)
1241 : Parent(graph, value) {}
1244 EdgeMap& operator=(const EdgeMap& cmap) {
1245 return operator=<EdgeMap>(cmap);
1248 template <typename CMap>
1249 EdgeMap& operator=(const CMap& cmap) {
1250 Parent::operator=(cmap);
1256 // Alteration extension
1259 Node node = Parent::addRedNode();
1260 notifier(RedNode()).add(node);
1261 notifier(Node()).add(node);
1265 Node addBlueNode() {
1266 Node node = Parent::addBlueNode();
1267 notifier(BlueNode()).add(node);
1268 notifier(Node()).add(node);
1272 Edge addEdge(const Node& from, const Node& to) {
1273 Edge edge = Parent::addEdge(from, to);
1274 notifier(Edge()).add(edge);
1275 std::vector<Arc> av;
1276 av.push_back(Parent::direct(edge, true));
1277 av.push_back(Parent::direct(edge, false));
1278 notifier(Arc()).add(av);
1283 notifier(Arc()).clear();
1284 notifier(Edge()).clear();
1285 notifier(Node()).clear();
1286 notifier(BlueNode()).clear();
1287 notifier(RedNode()).clear();
1291 template <typename BpGraph, typename NodeRefMap, typename EdgeRefMap>
1292 void build(const BpGraph& graph, NodeRefMap& nodeRef,
1293 EdgeRefMap& edgeRef) {
1294 Parent::build(graph, nodeRef, edgeRef);
1295 notifier(RedNode()).build();
1296 notifier(BlueNode()).build();
1297 notifier(Node()).build();
1298 notifier(Edge()).build();
1299 notifier(Arc()).build();
1302 void erase(const Node& node) {
1304 Parent::firstOut(arc, node);
1305 while (arc != INVALID ) {
1307 Parent::firstOut(arc, node);
1310 Parent::firstIn(arc, node);
1311 while (arc != INVALID ) {
1313 Parent::firstIn(arc, node);
1316 if (Parent::red(node)) {
1317 notifier(RedNode()).erase(node);
1319 notifier(BlueNode()).erase(node);
1322 notifier(Node()).erase(node);
1323 Parent::erase(node);
1326 void erase(const Edge& edge) {
1327 std::vector<Arc> av;
1328 av.push_back(Parent::direct(edge, true));
1329 av.push_back(Parent::direct(edge, false));
1330 notifier(Arc()).erase(av);
1331 notifier(Edge()).erase(edge);
1332 Parent::erase(edge);
1336 red_node_notifier.setContainer(*this);
1337 blue_node_notifier.setContainer(*this);
1338 node_notifier.setContainer(*this);
1339 arc_notifier.setContainer(*this);
1340 edge_notifier.setContainer(*this);
1343 ~BpGraphExtender() {
1344 edge_notifier.clear();
1345 arc_notifier.clear();
1346 node_notifier.clear();
1347 blue_node_notifier.clear();
1348 red_node_notifier.clear();