1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
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 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 &node, const Arc &arc) const {
67 if (node == Parent::source(arc))
68 return Parent::target(arc);
69 else if(node == Parent::target(arc))
70 return Parent::source(arc);
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& arc) :
132 Arc(arc), _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 &arc) const {
193 return Parent::source(arc);
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 &arc) const {
200 return Parent::target(arc);
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 &arc) const {
207 return Parent::target(arc);
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 &arc) const {
214 return Parent::source(arc);
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 Graph;
336 typedef True UndirectedTag;
338 typedef typename Parent::Node Node;
339 typedef typename Parent::Arc Arc;
340 typedef typename Parent::Edge Edge;
344 int maxId(Node) const {
345 return Parent::maxNodeId();
348 int maxId(Arc) const {
349 return Parent::maxArcId();
352 int maxId(Edge) const {
353 return Parent::maxEdgeId();
356 Node fromId(int id, Node) const {
357 return Parent::nodeFromId(id);
360 Arc fromId(int id, Arc) const {
361 return Parent::arcFromId(id);
364 Edge fromId(int id, Edge) const {
365 return Parent::edgeFromId(id);
368 Node oppositeNode(const Node &n, const Edge &e) const {
369 if( n == Parent::u(e))
371 else if( n == Parent::v(e))
377 Arc oppositeArc(const Arc &arc) const {
378 return Parent::direct(arc, !Parent::direction(arc));
381 using Parent::direct;
382 Arc direct(const Edge &edge, const Node &node) const {
383 return Parent::direct(edge, Parent::u(edge) == node);
386 // Alterable extension
388 typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
389 typedef AlterationNotifier<GraphExtender, Arc> ArcNotifier;
390 typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;
395 mutable NodeNotifier node_notifier;
396 mutable ArcNotifier arc_notifier;
397 mutable EdgeNotifier edge_notifier;
401 NodeNotifier& notifier(Node) const {
402 return node_notifier;
405 ArcNotifier& notifier(Arc) const {
409 EdgeNotifier& notifier(Edge) const {
410 return edge_notifier;
415 class NodeIt : public Node {
421 NodeIt(Invalid i) : Node(i) { }
423 explicit NodeIt(const Graph& graph) : _graph(&graph) {
424 _graph->first(static_cast<Node&>(*this));
427 NodeIt(const Graph& graph, const Node& node)
428 : Node(node), _graph(&graph) {}
430 NodeIt& operator++() {
438 class ArcIt : public Arc {
444 ArcIt(Invalid i) : Arc(i) { }
446 explicit ArcIt(const Graph& graph) : _graph(&graph) {
447 _graph->first(static_cast<Arc&>(*this));
450 ArcIt(const Graph& graph, const Arc& arc) :
451 Arc(arc), _graph(&graph) { }
453 ArcIt& operator++() {
461 class OutArcIt : public Arc {
467 OutArcIt(Invalid i) : Arc(i) { }
469 OutArcIt(const Graph& graph, const Node& node)
471 _graph->firstOut(*this, node);
474 OutArcIt(const Graph& graph, const Arc& arc)
475 : Arc(arc), _graph(&graph) {}
477 OutArcIt& operator++() {
478 _graph->nextOut(*this);
485 class InArcIt : public Arc {
491 InArcIt(Invalid i) : Arc(i) { }
493 InArcIt(const Graph& graph, const Node& node)
495 _graph->firstIn(*this, node);
498 InArcIt(const Graph& graph, const Arc& arc) :
499 Arc(arc), _graph(&graph) {}
501 InArcIt& operator++() {
502 _graph->nextIn(*this);
509 class EdgeIt : public Parent::Edge {
515 EdgeIt(Invalid i) : Edge(i) { }
517 explicit EdgeIt(const Graph& graph) : _graph(&graph) {
518 _graph->first(static_cast<Edge&>(*this));
521 EdgeIt(const Graph& graph, const Edge& edge) :
522 Edge(edge), _graph(&graph) { }
524 EdgeIt& operator++() {
531 class IncEdgeIt : public Parent::Edge {
532 friend class GraphExtender;
539 IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
541 IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) {
542 _graph->firstInc(*this, _direction, node);
545 IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node)
546 : _graph(&graph), Edge(edge) {
547 _direction = (_graph->source(edge) == node);
550 IncEdgeIt& operator++() {
551 _graph->nextInc(*this, _direction);
556 /// \brief Base node of the iterator
558 /// Returns the base node (ie. the source in this case) of the iterator
559 Node baseNode(const OutArcIt &arc) const {
560 return Parent::source(static_cast<const Arc&>(arc));
562 /// \brief Running node of the iterator
564 /// Returns the running node (ie. the target in this case) of the
566 Node runningNode(const OutArcIt &arc) const {
567 return Parent::target(static_cast<const Arc&>(arc));
570 /// \brief Base node of the iterator
572 /// Returns the base node (ie. the target in this case) of the iterator
573 Node baseNode(const InArcIt &arc) const {
574 return Parent::target(static_cast<const Arc&>(arc));
576 /// \brief Running node of the iterator
578 /// Returns the running node (ie. the source in this case) of the
580 Node runningNode(const InArcIt &arc) const {
581 return Parent::source(static_cast<const Arc&>(arc));
584 /// Base node of the iterator
586 /// Returns the base node of the iterator
587 Node baseNode(const IncEdgeIt &edge) const {
588 return edge._direction ? u(edge) : v(edge);
590 /// Running node of the iterator
592 /// Returns the running node of the iterator
593 Node runningNode(const IncEdgeIt &edge) const {
594 return edge._direction ? v(edge) : u(edge);
597 // Mappable extension
599 template <typename _Value>
601 : public MapExtender<DefaultMap<Graph, Node, _Value> > {
603 typedef GraphExtender Graph;
604 typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
606 NodeMap(const Graph& graph)
608 NodeMap(const Graph& graph, const _Value& value)
609 : Parent(graph, value) {}
611 NodeMap& operator=(const NodeMap& cmap) {
612 return operator=<NodeMap>(cmap);
615 template <typename CMap>
616 NodeMap& operator=(const CMap& cmap) {
617 Parent::operator=(cmap);
623 template <typename _Value>
625 : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
627 typedef GraphExtender Graph;
628 typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
630 ArcMap(const Graph& graph)
632 ArcMap(const Graph& graph, const _Value& value)
633 : Parent(graph, value) {}
635 ArcMap& operator=(const ArcMap& cmap) {
636 return operator=<ArcMap>(cmap);
639 template <typename CMap>
640 ArcMap& operator=(const CMap& cmap) {
641 Parent::operator=(cmap);
647 template <typename _Value>
649 : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
651 typedef GraphExtender Graph;
652 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
654 EdgeMap(const Graph& graph)
657 EdgeMap(const Graph& graph, const _Value& value)
658 : Parent(graph, value) {}
660 EdgeMap& operator=(const EdgeMap& cmap) {
661 return operator=<EdgeMap>(cmap);
664 template <typename CMap>
665 EdgeMap& operator=(const CMap& cmap) {
666 Parent::operator=(cmap);
672 // Alteration extension
675 Node node = Parent::addNode();
676 notifier(Node()).add(node);
680 Edge addEdge(const Node& from, const Node& to) {
681 Edge edge = Parent::addEdge(from, to);
682 notifier(Edge()).add(edge);
684 ev.push_back(Parent::direct(edge, true));
685 ev.push_back(Parent::direct(edge, false));
686 notifier(Arc()).add(ev);
691 notifier(Arc()).clear();
692 notifier(Edge()).clear();
693 notifier(Node()).clear();
697 template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
698 void build(const Graph& graph, NodeRefMap& nodeRef,
699 EdgeRefMap& edgeRef) {
700 Parent::build(graph, nodeRef, edgeRef);
701 notifier(Node()).build();
702 notifier(Edge()).build();
703 notifier(Arc()).build();
706 void erase(const Node& node) {
708 Parent::firstOut(arc, node);
709 while (arc != INVALID ) {
711 Parent::firstOut(arc, node);
714 Parent::firstIn(arc, node);
715 while (arc != INVALID ) {
717 Parent::firstIn(arc, node);
720 notifier(Node()).erase(node);
724 void erase(const Edge& edge) {
726 av.push_back(Parent::direct(edge, true));
727 av.push_back(Parent::direct(edge, false));
728 notifier(Arc()).erase(av);
729 notifier(Edge()).erase(edge);
734 node_notifier.setContainer(*this);
735 arc_notifier.setContainer(*this);
736 edge_notifier.setContainer(*this);
740 edge_notifier.clear();
741 arc_notifier.clear();
742 node_notifier.clear();