3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
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_BPUGRAPH_EXTENDER_H
20 #define LEMON_BITS_BPUGRAPH_EXTENDER_H
22 #include <lemon/bits/invalid.h>
23 #include <lemon/error.h>
25 #include <lemon/bits/map_extender.h>
26 #include <lemon/bits/default_map.h>
28 #include <lemon/concept_check.h>
29 #include <lemon/concept/maps.h>
33 ///\brief Extenders for the graph types
36 /// \ingroup graphbits
38 /// \brief Extender for the BpUGraphs
39 template <typename Base>
40 class BpUGraphExtender : public Base {
43 typedef BpUGraphExtender Graph;
45 typedef typename Parent::Node Node;
46 typedef typename Parent::UEdge UEdge;
54 class ANode : public Node {
55 friend class BpUGraphExtender;
58 ANode(const Node& node) : Node(node) {
59 LEMON_ASSERT(Parent::aNode(node) || node == INVALID,
60 typename Parent::NodeSetError());
62 ANode(Invalid) : Node(INVALID) {}
65 void first(ANode& node) const {
66 Parent::firstANode(static_cast<Node&>(node));
68 void next(ANode& node) const {
69 Parent::nextANode(static_cast<Node&>(node));
72 int id(const ANode& node) const {
73 return Parent::aNodeId(node);
76 class BNode : public Node {
77 friend class BpUGraphExtender;
80 BNode(const Node& node) : Node(node) {
81 LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
82 typename Parent::NodeSetError());
84 BNode(Invalid) : Node(INVALID) {}
87 void first(BNode& node) const {
88 Parent::firstBNode(static_cast<Node&>(node));
90 void next(BNode& node) const {
91 Parent::nextBNode(static_cast<Node&>(node));
94 int id(const BNode& node) const {
95 return Parent::aNodeId(node);
98 Node source(const UEdge& edge) const {
101 Node target(const UEdge& edge) const {
105 void firstInc(UEdge& edge, bool& direction, const Node& node) const {
106 if (Parent::aNode(node)) {
107 Parent::firstFromANode(edge, node);
110 Parent::firstFromBNode(edge, node);
111 direction = static_cast<UEdge&>(edge) == INVALID;
114 void nextInc(UEdge& edge, bool& direction) const {
116 Parent::nextFromANode(edge);
118 Parent::nextFromBNode(edge);
119 if (edge == INVALID) direction = true;
123 class Edge : public UEdge {
124 friend class BpUGraphExtender;
128 Edge(const UEdge& edge, bool _forward)
129 : UEdge(edge), forward(_forward) {}
133 Edge (Invalid) : UEdge(INVALID), forward(true) {}
134 bool operator==(const Edge& i) const {
135 return UEdge::operator==(i) && forward == i.forward;
137 bool operator!=(const Edge& i) const {
138 return UEdge::operator!=(i) || forward != i.forward;
140 bool operator<(const Edge& i) const {
141 return UEdge::operator<(i) ||
142 (!(i.forward<forward) && UEdge(*this)<UEdge(i));
146 void first(Edge& edge) const {
147 Parent::first(static_cast<UEdge&>(edge));
151 void next(Edge& edge) const {
153 Parent::next(static_cast<UEdge&>(edge));
155 edge.forward = !edge.forward;
158 void firstOut(Edge& edge, const Node& node) const {
159 if (Parent::aNode(node)) {
160 Parent::firstFromANode(edge, node);
163 Parent::firstFromBNode(edge, node);
164 edge.forward = static_cast<UEdge&>(edge) == INVALID;
167 void nextOut(Edge& edge) const {
169 Parent::nextFromANode(edge);
171 Parent::nextFromBNode(edge);
172 edge.forward = static_cast<UEdge&>(edge) == INVALID;
176 void firstIn(Edge& edge, const Node& node) const {
177 if (Parent::bNode(node)) {
178 Parent::firstFromBNode(edge, node);
181 Parent::firstFromANode(edge, node);
182 edge.forward = static_cast<UEdge&>(edge) == INVALID;
185 void nextIn(Edge& edge) const {
187 Parent::nextFromBNode(edge);
189 Parent::nextFromANode(edge);
190 edge.forward = static_cast<UEdge&>(edge) == INVALID;
194 Node source(const Edge& edge) const {
195 return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
197 Node target(const Edge& edge) const {
198 return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
201 int id(const Edge& edge) const {
202 return (Parent::id(static_cast<const UEdge&>(edge)) << 1) +
203 (edge.forward ? 0 : 1);
205 Edge edgeFromId(int id) const {
206 return Edge(Parent::fromUEdgeId(id >> 1), (id & 1) == 0);
208 int maxEdgeId() const {
209 return (Parent::maxUEdgeId(UEdge()) << 1) + 1;
212 bool direction(const Edge& edge) const {
216 Edge direct(const UEdge& edge, bool direction) const {
217 return Edge(edge, direction);
220 int edgeNum() const {
221 return 2 * Parent::uEdgeNum();
224 int uEdgeNum() const {
225 return Parent::uEdgeNum();
228 Node oppositeNode(const UEdge& edge, const Node& node) const {
229 return source(edge) == node ?
230 target(edge) : source(edge);
233 Edge direct(const UEdge& edge, const Node& node) const {
234 return Edge(edge, node == Parent::source(edge));
237 Edge oppositeEdge(const Edge& edge) const {
238 return Parent::direct(edge, !Parent::direction(edge));
242 int maxId(Node) const {
243 return Parent::maxNodeId();
245 int maxId(BNode) const {
246 return Parent::maxBNodeId();
248 int maxId(ANode) const {
249 return Parent::maxANodeId();
251 int maxId(Edge) const {
254 int maxId(UEdge) const {
255 return Parent::maxUEdgeId();
259 Node fromId(int id, Node) const {
260 return Parent::nodeFromId(id);
262 ANode fromId(int id, ANode) const {
263 return Parent::fromANodeId(id);
265 BNode fromId(int id, BNode) const {
266 return Parent::fromBNodeId(id);
268 Edge fromId(int id, Edge) const {
269 return Parent::edgeFromId(id);
271 UEdge fromId(int id, UEdge) const {
272 return Parent::uEdgeFromId(id);
275 typedef AlterationNotifier<BpUGraphExtender, ANode> ANodeNotifier;
276 typedef AlterationNotifier<BpUGraphExtender, BNode> BNodeNotifier;
277 typedef AlterationNotifier<BpUGraphExtender, Node> NodeNotifier;
278 typedef AlterationNotifier<BpUGraphExtender, Edge> EdgeNotifier;
279 typedef AlterationNotifier<BpUGraphExtender, UEdge> UEdgeNotifier;
283 mutable ANodeNotifier anode_notifier;
284 mutable BNodeNotifier bnode_notifier;
285 mutable NodeNotifier node_notifier;
286 mutable EdgeNotifier edge_notifier;
287 mutable UEdgeNotifier uedge_notifier;
291 NodeNotifier& getNotifier(Node) const {
292 return node_notifier;
295 ANodeNotifier& getNotifier(ANode) const {
296 return anode_notifier;
299 BNodeNotifier& getNotifier(BNode) const {
300 return bnode_notifier;
303 EdgeNotifier& getNotifier(Edge) const {
304 return edge_notifier;
307 UEdgeNotifier& getNotifier(UEdge) const {
308 return uedge_notifier;
311 class NodeIt : public Node {
317 NodeIt(Invalid i) : Node(INVALID) { }
319 explicit NodeIt(const Graph& _graph) : graph(&_graph) {
320 graph->first(static_cast<Node&>(*this));
323 NodeIt(const Graph& _graph, const Node& node)
324 : Node(node), graph(&_graph) { }
326 NodeIt& operator++() {
333 class ANodeIt : public Node {
334 friend class BpUGraphExtender;
340 ANodeIt(Invalid i) : Node(INVALID) { }
342 explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
343 graph->firstANode(static_cast<Node&>(*this));
346 ANodeIt(const Graph& _graph, const Node& node)
347 : Node(node), graph(&_graph) {}
349 ANodeIt& operator++() {
350 graph->nextANode(*this);
355 class BNodeIt : public Node {
356 friend class BpUGraphExtender;
362 BNodeIt(Invalid i) : Node(INVALID) { }
364 explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
365 graph->firstBNode(static_cast<Node&>(*this));
368 BNodeIt(const Graph& _graph, const Node& node)
369 : Node(node), graph(&_graph) {}
371 BNodeIt& operator++() {
372 graph->nextBNode(*this);
377 class EdgeIt : public Edge {
378 friend class BpUGraphExtender;
384 EdgeIt(Invalid i) : Edge(INVALID) { }
386 explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
387 graph->first(static_cast<Edge&>(*this));
390 EdgeIt(const Graph& _graph, const Edge& edge)
391 : Edge(edge), graph(&_graph) { }
393 EdgeIt& operator++() {
400 class UEdgeIt : public UEdge {
401 friend class BpUGraphExtender;
407 UEdgeIt(Invalid i) : UEdge(INVALID) { }
409 explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
410 graph->first(static_cast<UEdge&>(*this));
413 UEdgeIt(const Graph& _graph, const UEdge& edge)
414 : UEdge(edge), graph(&_graph) { }
416 UEdgeIt& operator++() {
422 class OutEdgeIt : public Edge {
423 friend class BpUGraphExtender;
429 OutEdgeIt(Invalid i) : Edge(i) { }
431 OutEdgeIt(const Graph& _graph, const Node& node)
433 graph->firstOut(*this, node);
436 OutEdgeIt(const Graph& _graph, const Edge& edge)
437 : Edge(edge), graph(&_graph) {}
439 OutEdgeIt& operator++() {
440 graph->nextOut(*this);
447 class InEdgeIt : public Edge {
448 friend class BpUGraphExtender;
454 InEdgeIt(Invalid i) : Edge(i) { }
456 InEdgeIt(const Graph& _graph, const Node& node)
458 graph->firstIn(*this, node);
461 InEdgeIt(const Graph& _graph, const Edge& edge) :
462 Edge(edge), graph(&_graph) {}
464 InEdgeIt& operator++() {
465 graph->nextIn(*this);
471 /// \brief Base node of the iterator
473 /// Returns the base node (ie. the source in this case) of the iterator
474 Node baseNode(const OutEdgeIt &e) const {
475 return Parent::source((Edge&)e);
477 /// \brief Running node of the iterator
479 /// Returns the running node (ie. the target in this case) of the
481 Node runningNode(const OutEdgeIt &e) const {
482 return Parent::target((Edge&)e);
485 /// \brief Base node of the iterator
487 /// Returns the base node (ie. the target in this case) of the iterator
488 Node baseNode(const InEdgeIt &e) const {
489 return Parent::target((Edge&)e);
491 /// \brief Running node of the iterator
493 /// Returns the running node (ie. the source in this case) of the
495 Node runningNode(const InEdgeIt &e) const {
496 return Parent::source((Edge&)e);
499 class IncEdgeIt : public Parent::UEdge {
500 friend class BpUGraphExtender;
507 IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
509 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
510 graph->firstInc(*this, direction, n);
513 IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
514 : graph(&_graph), UEdge(ue) {
515 direction = (graph->source(ue) == n);
518 IncEdgeIt& operator++() {
519 graph->nextInc(*this, direction);
525 /// Base node of the iterator
527 /// Returns the base node of the iterator
528 Node baseNode(const IncEdgeIt &e) const {
529 return e.direction ? source(e) : target(e);
532 /// Running node of the iterator
534 /// Returns the running node of the iterator
535 Node runningNode(const IncEdgeIt &e) const {
536 return e.direction ? target(e) : source(e);
539 template <typename _Value>
541 : public MapExtender<DefaultMap<Graph, ANode, _Value> > {
543 typedef BpUGraphExtender Graph;
544 typedef MapExtender<DefaultMap<Graph, ANode, _Value> > Parent;
546 ANodeMap(const Graph& graph)
548 ANodeMap(const Graph& graph, const _Value& value)
549 : Parent(graph, value) {}
551 ANodeMap& operator=(const ANodeMap& cmap) {
552 return operator=<ANodeMap>(cmap);
555 template <typename CMap>
556 ANodeMap& operator=(const CMap& cmap) {
557 Parent::operator=(cmap);
563 template <typename _Value>
565 : public MapExtender<DefaultMap<Graph, BNode, _Value> > {
567 typedef BpUGraphExtender Graph;
568 typedef MapExtender<DefaultMap<Graph, BNode, _Value> > Parent;
570 BNodeMap(const Graph& graph)
572 BNodeMap(const Graph& graph, const _Value& value)
573 : Parent(graph, value) {}
575 BNodeMap& operator=(const BNodeMap& cmap) {
576 return operator=<BNodeMap>(cmap);
579 template <typename CMap>
580 BNodeMap& operator=(const CMap& cmap) {
581 Parent::operator=(cmap);
589 template <typename _Value>
592 typedef BpUGraphExtender Graph;
595 typedef _Value Value;
597 /// The reference type of the map;
598 typedef typename ANodeMap<_Value>::Reference Reference;
599 /// The const reference type of the map;
600 typedef typename ANodeMap<_Value>::ConstReference ConstReference;
602 typedef True ReferenceMapTag;
604 NodeMap(const Graph& _graph)
605 : graph(_graph), aNodeMap(_graph), bNodeMap(_graph) {}
606 NodeMap(const Graph& _graph, const _Value& _value)
607 : graph(_graph), aNodeMap(_graph, _value), bNodeMap(_graph, _value) {}
609 NodeMap& operator=(const NodeMap& cmap) {
610 return operator=<NodeMap>(cmap);
613 template <typename CMap>
614 NodeMap& operator=(const CMap& cmap) {
615 checkConcept<concept::ReadMap<Node, _Value>, CMap>();
616 const typename Parent::Notifier* notifier = Parent::getNotifier();
618 for (graph.first(it); it != INVALID; graph.next(it)) {
619 Parent::set(it, cmap[it]);
624 ConstReference operator[](const Key& node) const {
625 if (Parent::aNode(node)) {
626 return aNodeMap[node];
628 return bNodeMap[node];
632 Reference operator[](const Key& node) {
633 if (Parent::aNode(node)) {
634 return aNodeMap[node];
636 return bNodeMap[node];
640 void set(const Key& node, const Value& value) {
641 if (Parent::aNode(node)) {
642 aNodeMap.set(node, value);
644 bNodeMap.set(node, value);
648 class MapIt : public NodeIt {
651 typedef NodeIt Parent;
653 explicit MapIt(NodeMap& _map)
654 : Parent(_map.graph), map(_map) {}
656 typename MapTraits<NodeMap>::ConstReturnValue operator*() const {
660 typename MapTraits<NodeMap>::ReturnValue operator*() {
664 void set(const Value& value) {
665 map.set(*this, value);
672 class ConstMapIt : public NodeIt {
675 typedef NodeIt Parent;
677 explicit ConstMapIt(const NodeMap& _map)
678 : Parent(_map.graph), map(_map) {}
680 typename MapTraits<NodeMap>::ConstReturnValue operator*() const {
688 class ItemIt : public NodeIt {
691 typedef NodeIt Parent;
693 explicit ItemIt(const NodeMap& _map)
694 : Parent(_map.graph) {}
700 ANodeMap<_Value> aNodeMap;
701 BNodeMap<_Value> bNodeMap;
705 template <typename _Value>
707 : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
709 typedef BpUGraphExtender Graph;
710 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
712 EdgeMap(const Graph& graph)
714 EdgeMap(const Graph& graph, const _Value& value)
715 : Parent(graph, value) {}
717 EdgeMap& operator=(const EdgeMap& cmap) {
718 return operator=<EdgeMap>(cmap);
721 template <typename CMap>
722 EdgeMap& operator=(const CMap& cmap) {
723 Parent::operator=(cmap);
728 template <typename _Value>
730 : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
732 typedef BpUGraphExtender Graph;
733 typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
735 UEdgeMap(const Graph& graph)
737 UEdgeMap(const Graph& graph, const _Value& value)
738 : Parent(graph, value) {}
740 UEdgeMap& operator=(const UEdgeMap& cmap) {
741 return operator=<UEdgeMap>(cmap);
744 template <typename CMap>
745 UEdgeMap& operator=(const CMap& cmap) {
746 Parent::operator=(cmap);
753 Node node = Parent::addANode();
754 getNotifier(ANode()).add(node);
755 getNotifier(Node()).add(node);
760 Node node = Parent::addBNode();
761 getNotifier(BNode()).add(node);
762 getNotifier(Node()).add(node);
766 UEdge addEdge(const Node& source, const Node& target) {
767 UEdge uedge = Parent::addEdge(source, target);
768 getNotifier(UEdge()).add(uedge);
770 std::vector<Edge> edges;
771 edges.push_back(direct(uedge, true));
772 edges.push_back(direct(uedge, false));
773 getNotifier(Edge()).add(edges);
779 getNotifier(Edge()).clear();
780 getNotifier(UEdge()).clear();
781 getNotifier(Node()).clear();
782 getNotifier(BNode()).clear();
783 getNotifier(ANode()).clear();
787 void erase(const Node& node) {
789 if (Parent::aNode(node)) {
790 Parent::firstFromANode(uedge, node);
791 while (uedge != INVALID) {
793 Parent::firstFromANode(uedge, node);
796 Parent::firstFromBNode(uedge, node);
797 while (uedge != INVALID) {
799 Parent::firstFromBNode(uedge, node);
803 getNotifier(Node()).erase(node);
807 void erase(const UEdge& uedge) {
808 std::vector<Edge> edges;
809 edges.push_back(direct(uedge, true));
810 edges.push_back(direct(uedge, false));
811 getNotifier(Edge()).erase(edges);
812 getNotifier(UEdge()).erase(uedge);
813 Parent::erase(uedge);
818 anode_notifier.setContainer(*this);
819 bnode_notifier.setContainer(*this);
820 node_notifier.setContainer(*this);
821 edge_notifier.setContainer(*this);
822 uedge_notifier.setContainer(*this);
825 ~BpUGraphExtender() {
826 uedge_notifier.clear();
827 edge_notifier.clear();
828 node_notifier.clear();
829 anode_notifier.clear();
830 bnode_notifier.clear();