3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
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/bits/invalid.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 digraph types
35 /// \ingroup graphbits
37 /// \brief Extender for the Digraphs
38 template <typename Base>
39 class DigraphExtender : public Base {
43 typedef DigraphExtender Digraph;
47 typedef typename Parent::Node Node;
48 typedef typename Parent::Arc Arc;
50 int maxId(Node) const {
51 return Parent::maxNodeId();
54 int maxId(Arc) const {
55 return Parent::maxArcId();
58 Node fromId(int id, Node) const {
59 return Parent::nodeFromId(id);
62 Arc fromId(int id, Arc) const {
63 return Parent::arcFromId(id);
66 Node oppositeNode(const Node &n, const Arc &e) const {
67 if (n == Parent::source(e))
68 return Parent::target(e);
69 else if(n==Parent::target(e))
70 return Parent::source(e);
75 // Alterable extension
77 typedef AlterationNotifier<DigraphExtender, Node> NodeNotifier;
78 typedef AlterationNotifier<DigraphExtender, Arc> ArcNotifier;
83 mutable NodeNotifier node_notifier;
84 mutable ArcNotifier arc_notifier;
88 NodeNotifier& notifier(Node) const {
92 ArcNotifier& notifier(Arc) const {
96 class NodeIt : public Node {
97 const Digraph* digraph;
102 NodeIt(Invalid i) : Node(i) { }
104 explicit NodeIt(const Digraph& _digraph) : digraph(&_digraph) {
105 _digraph.first(static_cast<Node&>(*this));
108 NodeIt(const Digraph& _digraph, const Node& node)
109 : Node(node), digraph(&_digraph) {}
111 NodeIt& operator++() {
112 digraph->next(*this);
119 class ArcIt : public Arc {
120 const Digraph* digraph;
125 ArcIt(Invalid i) : Arc(i) { }
127 explicit ArcIt(const Digraph& _digraph) : digraph(&_digraph) {
128 _digraph.first(static_cast<Arc&>(*this));
131 ArcIt(const Digraph& _digraph, const Arc& e) :
132 Arc(e), digraph(&_digraph) { }
134 ArcIt& operator++() {
135 digraph->next(*this);
142 class OutArcIt : public Arc {
143 const Digraph* digraph;
148 OutArcIt(Invalid i) : Arc(i) { }
150 OutArcIt(const Digraph& _digraph, const Node& node)
151 : digraph(&_digraph) {
152 _digraph.firstOut(*this, node);
155 OutArcIt(const Digraph& _digraph, const Arc& arc)
156 : Arc(arc), digraph(&_digraph) {}
158 OutArcIt& operator++() {
159 digraph->nextOut(*this);
166 class InArcIt : public Arc {
167 const Digraph* digraph;
172 InArcIt(Invalid i) : Arc(i) { }
174 InArcIt(const Digraph& _digraph, const Node& node)
175 : digraph(&_digraph) {
176 _digraph.firstIn(*this, node);
179 InArcIt(const Digraph& _digraph, const Arc& arc) :
180 Arc(arc), digraph(&_digraph) {}
182 InArcIt& operator++() {
183 digraph->nextIn(*this);
189 /// \brief Base node of the iterator
191 /// Returns the base node (i.e. the source in this case) of the iterator
192 Node baseNode(const OutArcIt &e) const {
193 return Parent::source(e);
195 /// \brief Running node of the iterator
197 /// Returns the running node (i.e. the target in this case) of the
199 Node runningNode(const OutArcIt &e) const {
200 return Parent::target(e);
203 /// \brief Base node of the iterator
205 /// Returns the base node (i.e. the target in this case) of the iterator
206 Node baseNode(const InArcIt &e) const {
207 return Parent::target(e);
209 /// \brief Running node of the iterator
211 /// Returns the running node (i.e. the source in this case) of the
213 Node runningNode(const InArcIt &e) const {
214 return Parent::source(e);
218 template <typename _Value>
220 : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
222 typedef DigraphExtender Digraph;
223 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) {}
230 NodeMap& operator=(const NodeMap& cmap) {
231 return operator=<NodeMap>(cmap);
234 template <typename CMap>
235 NodeMap& operator=(const CMap& cmap) {
236 Parent::operator=(cmap);
242 template <typename _Value>
244 : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
246 typedef DigraphExtender Digraph;
247 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) {}
254 ArcMap& operator=(const ArcMap& cmap) {
255 return operator=<ArcMap>(cmap);
258 template <typename CMap>
259 ArcMap& operator=(const CMap& cmap) {
260 Parent::operator=(cmap);
267 Node node = Parent::addNode();
268 notifier(Node()).add(node);
272 Arc addArc(const Node& from, const Node& to) {
273 Arc arc = Parent::addArc(from, to);
274 notifier(Arc()).add(arc);
279 notifier(Arc()).clear();
280 notifier(Node()).clear();
284 template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
285 void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
286 Parent::build(digraph, nodeRef, arcRef);
287 notifier(Node()).build();
288 notifier(Arc()).build();
291 void erase(const Node& node) {
293 Parent::firstOut(arc, node);
294 while (arc != INVALID ) {
296 Parent::firstOut(arc, node);
299 Parent::firstIn(arc, node);
300 while (arc != INVALID ) {
302 Parent::firstIn(arc, node);
305 notifier(Node()).erase(node);
309 void erase(const Arc& arc) {
310 notifier(Arc()).erase(arc);
315 node_notifier.setContainer(*this);
316 arc_notifier.setContainer(*this);
321 arc_notifier.clear();
322 node_notifier.clear();
326 /// \ingroup graphbits
328 /// \brief Extender for the Graphs
329 template <typename Base>
330 class GraphExtender : public Base {
334 typedef GraphExtender Digraph;
336 typedef typename Parent::Node Node;
337 typedef typename Parent::Arc Arc;
338 typedef typename Parent::Edge Edge;
342 int maxId(Node) const {
343 return Parent::maxNodeId();
346 int maxId(Arc) const {
347 return Parent::maxArcId();
350 int maxId(Edge) const {
351 return Parent::maxEdgeId();
354 Node fromId(int id, Node) const {
355 return Parent::nodeFromId(id);
358 Arc fromId(int id, Arc) const {
359 return Parent::arcFromId(id);
362 Edge fromId(int id, Edge) const {
363 return Parent::edgeFromId(id);
366 Node oppositeNode(const Node &n, const Edge &e) const {
367 if( n == Parent::source(e))
368 return Parent::target(e);
369 else if( n == Parent::target(e))
370 return Parent::source(e);
375 Arc oppositeArc(const Arc &e) const {
376 return Parent::direct(e, !Parent::direction(e));
379 using Parent::direct;
380 Arc direct(const Edge &ue, const Node &s) const {
381 return Parent::direct(ue, Parent::source(ue) == s);
384 // Alterable extension
386 typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
387 typedef AlterationNotifier<GraphExtender, Arc> ArcNotifier;
388 typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;
393 mutable NodeNotifier node_notifier;
394 mutable ArcNotifier arc_notifier;
395 mutable EdgeNotifier edge_notifier;
399 NodeNotifier& notifier(Node) const {
400 return node_notifier;
403 ArcNotifier& notifier(Arc) const {
407 EdgeNotifier& notifier(Edge) const {
408 return edge_notifier;
413 class NodeIt : public Node {
414 const Digraph* digraph;
419 NodeIt(Invalid i) : Node(i) { }
421 explicit NodeIt(const Digraph& _digraph) : digraph(&_digraph) {
422 _digraph.first(static_cast<Node&>(*this));
425 NodeIt(const Digraph& _digraph, const Node& node)
426 : Node(node), digraph(&_digraph) {}
428 NodeIt& operator++() {
429 digraph->next(*this);
436 class ArcIt : public Arc {
437 const Digraph* digraph;
442 ArcIt(Invalid i) : Arc(i) { }
444 explicit ArcIt(const Digraph& _digraph) : digraph(&_digraph) {
445 _digraph.first(static_cast<Arc&>(*this));
448 ArcIt(const Digraph& _digraph, const Arc& e) :
449 Arc(e), digraph(&_digraph) { }
451 ArcIt& operator++() {
452 digraph->next(*this);
459 class OutArcIt : public Arc {
460 const Digraph* digraph;
465 OutArcIt(Invalid i) : Arc(i) { }
467 OutArcIt(const Digraph& _digraph, const Node& node)
468 : digraph(&_digraph) {
469 _digraph.firstOut(*this, node);
472 OutArcIt(const Digraph& _digraph, const Arc& arc)
473 : Arc(arc), digraph(&_digraph) {}
475 OutArcIt& operator++() {
476 digraph->nextOut(*this);
483 class InArcIt : public Arc {
484 const Digraph* digraph;
489 InArcIt(Invalid i) : Arc(i) { }
491 InArcIt(const Digraph& _digraph, const Node& node)
492 : digraph(&_digraph) {
493 _digraph.firstIn(*this, node);
496 InArcIt(const Digraph& _digraph, const Arc& arc) :
497 Arc(arc), digraph(&_digraph) {}
499 InArcIt& operator++() {
500 digraph->nextIn(*this);
507 class EdgeIt : public Parent::Edge {
508 const Digraph* digraph;
513 EdgeIt(Invalid i) : Edge(i) { }
515 explicit EdgeIt(const Digraph& _digraph) : digraph(&_digraph) {
516 _digraph.first(static_cast<Edge&>(*this));
519 EdgeIt(const Digraph& _digraph, const Edge& e) :
520 Edge(e), digraph(&_digraph) { }
522 EdgeIt& operator++() {
523 digraph->next(*this);
529 class IncArcIt : public Parent::Edge {
530 friend class GraphExtender;
531 const Digraph* digraph;
537 IncArcIt(Invalid i) : Edge(i), direction(false) { }
539 IncArcIt(const Digraph& _digraph, const Node &n) : digraph(&_digraph) {
540 _digraph.firstInc(*this, direction, n);
543 IncArcIt(const Digraph& _digraph, const Edge &ue, const Node &n)
544 : digraph(&_digraph), Edge(ue) {
545 direction = (_digraph.source(ue) == n);
548 IncArcIt& operator++() {
549 digraph->nextInc(*this, direction);
554 /// \brief Base node of the iterator
556 /// Returns the base node (ie. the source in this case) of the iterator
557 Node baseNode(const OutArcIt &e) const {
558 return Parent::source(static_cast<const Arc&>(e));
560 /// \brief Running node of the iterator
562 /// Returns the running node (ie. the target in this case) of the
564 Node runningNode(const OutArcIt &e) const {
565 return Parent::target(static_cast<const Arc&>(e));
568 /// \brief Base node of the iterator
570 /// Returns the base node (ie. the target in this case) of the iterator
571 Node baseNode(const InArcIt &e) const {
572 return Parent::target(static_cast<const Arc&>(e));
574 /// \brief Running node of the iterator
576 /// Returns the running node (ie. the source in this case) of the
578 Node runningNode(const InArcIt &e) const {
579 return Parent::source(static_cast<const Arc&>(e));
582 /// Base node of the iterator
584 /// Returns the base node of the iterator
585 Node baseNode(const IncArcIt &e) const {
586 return e.direction ? source(e) : target(e);
588 /// Running node of the iterator
590 /// Returns the running node of the iterator
591 Node runningNode(const IncArcIt &e) const {
592 return e.direction ? target(e) : source(e);
595 // Mappable extension
597 template <typename _Value>
599 : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
601 typedef GraphExtender Digraph;
602 typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
604 NodeMap(const Digraph& digraph)
606 NodeMap(const Digraph& digraph, const _Value& value)
607 : Parent(digraph, value) {}
609 NodeMap& operator=(const NodeMap& cmap) {
610 return operator=<NodeMap>(cmap);
613 template <typename CMap>
614 NodeMap& operator=(const CMap& cmap) {
615 Parent::operator=(cmap);
621 template <typename _Value>
623 : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
625 typedef GraphExtender Digraph;
626 typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
628 ArcMap(const Digraph& digraph)
630 ArcMap(const Digraph& digraph, const _Value& value)
631 : Parent(digraph, value) {}
633 ArcMap& operator=(const ArcMap& cmap) {
634 return operator=<ArcMap>(cmap);
637 template <typename CMap>
638 ArcMap& operator=(const CMap& cmap) {
639 Parent::operator=(cmap);
645 template <typename _Value>
647 : public MapExtender<DefaultMap<Digraph, Edge, _Value> > {
649 typedef GraphExtender Digraph;
650 typedef MapExtender<DefaultMap<Digraph, Edge, _Value> > Parent;
652 EdgeMap(const Digraph& digraph)
655 EdgeMap(const Digraph& digraph, const _Value& value)
656 : Parent(digraph, value) {}
658 EdgeMap& operator=(const EdgeMap& cmap) {
659 return operator=<EdgeMap>(cmap);
662 template <typename CMap>
663 EdgeMap& operator=(const CMap& cmap) {
664 Parent::operator=(cmap);
670 // Alteration extension
673 Node node = Parent::addNode();
674 notifier(Node()).add(node);
678 Edge addEdge(const Node& from, const Node& to) {
679 Edge edge = Parent::addEdge(from, to);
680 notifier(Edge()).add(edge);
682 ev.push_back(Parent::direct(edge, true));
683 ev.push_back(Parent::direct(edge, false));
684 notifier(Arc()).add(ev);
689 notifier(Arc()).clear();
690 notifier(Edge()).clear();
691 notifier(Node()).clear();
695 template <typename Digraph, typename NodeRefMap, typename EdgeRefMap>
696 void build(const Digraph& digraph, NodeRefMap& nodeRef,
697 EdgeRefMap& edgeRef) {
698 Parent::build(digraph, nodeRef, edgeRef);
699 notifier(Node()).build();
700 notifier(Edge()).build();
701 notifier(Arc()).build();
704 void erase(const Node& node) {
706 Parent::firstOut(arc, node);
707 while (arc != INVALID ) {
709 Parent::firstOut(arc, node);
712 Parent::firstIn(arc, node);
713 while (arc != INVALID ) {
715 Parent::firstIn(arc, node);
718 notifier(Node()).erase(node);
722 void erase(const Edge& edge) {
724 ev.push_back(Parent::direct(edge, true));
725 ev.push_back(Parent::direct(edge, false));
726 notifier(Arc()).erase(ev);
727 notifier(Edge()).erase(edge);
732 node_notifier.setContainer(*this);
733 arc_notifier.setContainer(*this);
734 edge_notifier.setContainer(*this);
738 edge_notifier.clear();
739 arc_notifier.clear();
740 node_notifier.clear();