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
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) {}
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> > {
247 typedef DigraphExtender Digraph;
248 typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
250 explicit ArcMap(const Digraph& digraph)
252 ArcMap(const Digraph& digraph, const _Value& value)
253 : Parent(digraph, value) {}
256 ArcMap& operator=(const ArcMap& cmap) {
257 return operator=<ArcMap>(cmap);
260 template <typename CMap>
261 ArcMap& operator=(const CMap& cmap) {
262 Parent::operator=(cmap);
269 Node node = Parent::addNode();
270 notifier(Node()).add(node);
274 Arc addArc(const Node& from, const Node& to) {
275 Arc arc = Parent::addArc(from, to);
276 notifier(Arc()).add(arc);
281 notifier(Arc()).clear();
282 notifier(Node()).clear();
286 template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
287 void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
288 Parent::build(digraph, nodeRef, arcRef);
289 notifier(Node()).build();
290 notifier(Arc()).build();
293 void erase(const Node& node) {
295 Parent::firstOut(arc, node);
296 while (arc != INVALID ) {
298 Parent::firstOut(arc, node);
301 Parent::firstIn(arc, node);
302 while (arc != INVALID ) {
304 Parent::firstIn(arc, node);
307 notifier(Node()).erase(node);
311 void erase(const Arc& arc) {
312 notifier(Arc()).erase(arc);
317 node_notifier.setContainer(*this);
318 arc_notifier.setContainer(*this);
323 arc_notifier.clear();
324 node_notifier.clear();
328 // \ingroup _graphbits
330 // \brief Extender for the Graphs
331 template <typename Base>
332 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 Node fromId(int id, Node) const {
359 return Parent::nodeFromId(id);
362 Arc fromId(int id, Arc) const {
363 return Parent::arcFromId(id);
366 Edge fromId(int id, Edge) const {
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 ? u(edge) : 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 ? v(edge) : u(edge);
599 // Mappable extension
601 template <typename _Value>
603 : public MapExtender<DefaultMap<Graph, Node, _Value> > {
605 typedef GraphExtender Graph;
606 typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
608 NodeMap(const Graph& graph)
610 NodeMap(const Graph& graph, const _Value& value)
611 : Parent(graph, value) {}
614 NodeMap& operator=(const NodeMap& cmap) {
615 return operator=<NodeMap>(cmap);
618 template <typename CMap>
619 NodeMap& operator=(const CMap& cmap) {
620 Parent::operator=(cmap);
626 template <typename _Value>
628 : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
630 typedef GraphExtender Graph;
631 typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
633 ArcMap(const Graph& graph)
635 ArcMap(const Graph& graph, const _Value& value)
636 : Parent(graph, value) {}
639 ArcMap& operator=(const ArcMap& cmap) {
640 return operator=<ArcMap>(cmap);
643 template <typename CMap>
644 ArcMap& operator=(const CMap& cmap) {
645 Parent::operator=(cmap);
651 template <typename _Value>
653 : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
655 typedef GraphExtender Graph;
656 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
658 EdgeMap(const Graph& graph)
661 EdgeMap(const Graph& graph, const _Value& value)
662 : Parent(graph, value) {}
665 EdgeMap& operator=(const EdgeMap& cmap) {
666 return operator=<EdgeMap>(cmap);
669 template <typename CMap>
670 EdgeMap& operator=(const CMap& cmap) {
671 Parent::operator=(cmap);
677 // Alteration extension
680 Node node = Parent::addNode();
681 notifier(Node()).add(node);
685 Edge addEdge(const Node& from, const Node& to) {
686 Edge edge = Parent::addEdge(from, to);
687 notifier(Edge()).add(edge);
689 ev.push_back(Parent::direct(edge, true));
690 ev.push_back(Parent::direct(edge, false));
691 notifier(Arc()).add(ev);
696 notifier(Arc()).clear();
697 notifier(Edge()).clear();
698 notifier(Node()).clear();
702 template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
703 void build(const Graph& graph, NodeRefMap& nodeRef,
704 EdgeRefMap& edgeRef) {
705 Parent::build(graph, nodeRef, edgeRef);
706 notifier(Node()).build();
707 notifier(Edge()).build();
708 notifier(Arc()).build();
711 void erase(const Node& node) {
713 Parent::firstOut(arc, node);
714 while (arc != INVALID ) {
716 Parent::firstOut(arc, node);
719 Parent::firstIn(arc, node);
720 while (arc != INVALID ) {
722 Parent::firstIn(arc, node);
725 notifier(Node()).erase(node);
729 void erase(const Edge& edge) {
731 av.push_back(Parent::direct(edge, true));
732 av.push_back(Parent::direct(edge, false));
733 notifier(Arc()).erase(av);
734 notifier(Edge()).erase(edge);
739 node_notifier.setContainer(*this);
740 arc_notifier.setContainer(*this);
741 edge_notifier.setContainer(*this);
745 edge_notifier.clear();
746 arc_notifier.clear();
747 node_notifier.clear();