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_GRAPH_ADAPTOR_H
20 #define LEMON_GRAPH_ADAPTOR_H
22 ///\ingroup graph_adaptors
24 ///\brief Several graph adaptors.
26 ///This file contains several useful undirected graph adaptor classes.
28 #include <lemon/core.h>
29 #include <lemon/maps.h>
30 #include <lemon/bits/graph_adaptor_extender.h>
34 template<typename _Graph>
35 class GraphAdaptorBase {
38 typedef Graph ParentGraph;
43 GraphAdaptorBase() : _graph(0) {}
45 void setGraph(Graph& graph) { _graph = &graph; }
48 GraphAdaptorBase(Graph& graph) : _graph(&graph) {}
50 typedef typename Graph::Node Node;
51 typedef typename Graph::Arc Arc;
52 typedef typename Graph::Edge Edge;
54 void first(Node& i) const { _graph->first(i); }
55 void first(Arc& i) const { _graph->first(i); }
56 void first(Edge& i) const { _graph->first(i); }
57 void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); }
58 void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); }
59 void firstInc(Edge &i, bool &d, const Node &n) const {
60 _graph->firstInc(i, d, n);
63 void next(Node& i) const { _graph->next(i); }
64 void next(Arc& i) const { _graph->next(i); }
65 void next(Edge& i) const { _graph->next(i); }
66 void nextIn(Arc& i) const { _graph->nextIn(i); }
67 void nextOut(Arc& i) const { _graph->nextOut(i); }
68 void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); }
70 Node u(const Edge& e) const { return _graph->u(e); }
71 Node v(const Edge& e) const { return _graph->v(e); }
73 Node source(const Arc& a) const { return _graph->source(a); }
74 Node target(const Arc& a) const { return _graph->target(a); }
76 typedef NodeNumTagIndicator<Graph> NodeNumTag;
77 int nodeNum() const { return _graph->nodeNum(); }
79 typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
80 int arcNum() const { return _graph->arcNum(); }
81 int edgeNum() const { return _graph->edgeNum(); }
83 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
84 Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
85 return _graph->findArc(u, v, prev);
87 Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) {
88 return _graph->findEdge(u, v, prev);
91 Node addNode() { return _graph->addNode(); }
92 Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }
94 void erase(const Node& i) { _graph->erase(i); }
95 void erase(const Edge& i) { _graph->erase(i); }
97 void clear() { _graph->clear(); }
99 bool direction(const Arc& a) const { return _graph->direction(a); }
100 Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); }
102 int id(const Node& v) const { return _graph->id(v); }
103 int id(const Arc& a) const { return _graph->id(a); }
104 int id(const Edge& e) const { return _graph->id(e); }
106 Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
107 Arc arcFromId(int ix) const { return _graph->arcFromId(ix); }
108 Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); }
110 int maxNodeId() const { return _graph->maxNodeId(); }
111 int maxArcId() const { return _graph->maxArcId(); }
112 int maxEdgeId() const { return _graph->maxEdgeId(); }
114 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
115 NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
117 typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
118 ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
120 typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
121 EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
123 template <typename _Value>
124 class NodeMap : public Graph::template NodeMap<_Value> {
126 typedef typename Graph::template NodeMap<_Value> Parent;
127 explicit NodeMap(const GraphAdaptorBase<Graph>& adapter)
128 : Parent(*adapter._graph) {}
129 NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
130 : Parent(*adapter._graph, value) {}
133 NodeMap& operator=(const NodeMap& cmap) {
134 return operator=<NodeMap>(cmap);
137 template <typename CMap>
138 NodeMap& operator=(const CMap& cmap) {
139 Parent::operator=(cmap);
145 template <typename _Value>
146 class ArcMap : public Graph::template ArcMap<_Value> {
148 typedef typename Graph::template ArcMap<_Value> Parent;
149 explicit ArcMap(const GraphAdaptorBase<Graph>& adapter)
150 : Parent(*adapter._graph) {}
151 ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
152 : Parent(*adapter._graph, value) {}
155 ArcMap& operator=(const ArcMap& cmap) {
156 return operator=<ArcMap>(cmap);
159 template <typename CMap>
160 ArcMap& operator=(const CMap& cmap) {
161 Parent::operator=(cmap);
166 template <typename _Value>
167 class EdgeMap : public Graph::template EdgeMap<_Value> {
169 typedef typename Graph::template EdgeMap<_Value> Parent;
170 explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)
171 : Parent(*adapter._graph) {}
172 EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
173 : Parent(*adapter._graph, value) {}
176 EdgeMap& operator=(const EdgeMap& cmap) {
177 return operator=<EdgeMap>(cmap);
180 template <typename CMap>
181 EdgeMap& operator=(const CMap& cmap) {
182 Parent::operator=(cmap);
189 template <typename _Graph, typename NodeFilterMap,
190 typename EdgeFilterMap, bool checked = true>
191 class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
193 typedef _Graph Graph;
194 typedef SubGraphAdaptorBase Adaptor;
195 typedef GraphAdaptorBase<_Graph> Parent;
198 NodeFilterMap* _node_filter_map;
199 EdgeFilterMap* _edge_filter_map;
201 SubGraphAdaptorBase()
202 : Parent(), _node_filter_map(0), _edge_filter_map(0) { }
204 void setNodeFilterMap(NodeFilterMap& node_filter_map) {
205 _node_filter_map=&node_filter_map;
207 void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
208 _edge_filter_map=&edge_filter_map;
213 typedef typename Parent::Node Node;
214 typedef typename Parent::Arc Arc;
215 typedef typename Parent::Edge Edge;
217 void first(Node& i) const {
219 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
222 void first(Arc& i) const {
224 while (i!=INVALID && (!(*_edge_filter_map)[i]
225 || !(*_node_filter_map)[Parent::source(i)]
226 || !(*_node_filter_map)[Parent::target(i)])) Parent::next(i);
229 void first(Edge& i) const {
231 while (i!=INVALID && (!(*_edge_filter_map)[i]
232 || !(*_node_filter_map)[Parent::u(i)]
233 || !(*_node_filter_map)[Parent::v(i)])) Parent::next(i);
236 void firstIn(Arc& i, const Node& n) const {
237 Parent::firstIn(i, n);
238 while (i!=INVALID && (!(*_edge_filter_map)[i]
239 || !(*_node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
242 void firstOut(Arc& i, const Node& n) const {
243 Parent::firstOut(i, n);
244 while (i!=INVALID && (!(*_edge_filter_map)[i]
245 || !(*_node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
248 void firstInc(Edge& i, bool& d, const Node& n) const {
249 Parent::firstInc(i, d, n);
250 while (i!=INVALID && (!(*_edge_filter_map)[i]
251 || !(*_node_filter_map)[Parent::u(i)]
252 || !(*_node_filter_map)[Parent::v(i)])) Parent::nextInc(i, d);
255 void next(Node& i) const {
257 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
260 void next(Arc& i) const {
262 while (i!=INVALID && (!(*_edge_filter_map)[i]
263 || !(*_node_filter_map)[Parent::source(i)]
264 || !(*_node_filter_map)[Parent::target(i)])) Parent::next(i);
267 void next(Edge& i) const {
269 while (i!=INVALID && (!(*_edge_filter_map)[i]
270 || !(*_node_filter_map)[Parent::u(i)]
271 || !(*_node_filter_map)[Parent::v(i)])) Parent::next(i);
274 void nextIn(Arc& i) const {
276 while (i!=INVALID && (!(*_edge_filter_map)[i]
277 || !(*_node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
280 void nextOut(Arc& i) const {
282 while (i!=INVALID && (!(*_edge_filter_map)[i]
283 || !(*_node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
286 void nextInc(Edge& i, bool& d) const {
287 Parent::nextInc(i, d);
288 while (i!=INVALID && (!(*_edge_filter_map)[i]
289 || !(*_node_filter_map)[Parent::u(i)]
290 || !(*_node_filter_map)[Parent::v(i)])) Parent::nextInc(i, d);
293 void hide(const Node& n) const { _node_filter_map->set(n, false); }
294 void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
296 void unHide(const Node& n) const { _node_filter_map->set(n, true); }
297 void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
299 bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
300 bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
302 typedef False NodeNumTag;
303 typedef False EdgeNumTag;
305 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
306 Arc findArc(const Node& u, const Node& v,
307 const Arc& prev = INVALID) {
308 if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
311 Arc arc = Parent::findArc(u, v, prev);
312 while (arc != INVALID && !(*_edge_filter_map)[arc]) {
313 arc = Parent::findArc(u, v, arc);
317 Edge findEdge(const Node& u, const Node& v,
318 const Edge& prev = INVALID) {
319 if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
322 Edge edge = Parent::findEdge(u, v, prev);
323 while (edge != INVALID && !(*_edge_filter_map)[edge]) {
324 edge = Parent::findEdge(u, v, edge);
329 template <typename _Value>
330 class NodeMap : public SubMapExtender<Adaptor,
331 typename Parent::template NodeMap<_Value> > {
333 typedef _Value Value;
334 typedef SubMapExtender<Adaptor, typename Parent::
335 template NodeMap<Value> > MapParent;
337 NodeMap(const Adaptor& adaptor)
338 : MapParent(adaptor) {}
339 NodeMap(const Adaptor& adaptor, const Value& value)
340 : MapParent(adaptor, value) {}
343 NodeMap& operator=(const NodeMap& cmap) {
344 return operator=<NodeMap>(cmap);
347 template <typename CMap>
348 NodeMap& operator=(const CMap& cmap) {
349 MapParent::operator=(cmap);
354 template <typename _Value>
355 class ArcMap : public SubMapExtender<Adaptor,
356 typename Parent::template ArcMap<_Value> > {
358 typedef _Value Value;
359 typedef SubMapExtender<Adaptor, typename Parent::
360 template ArcMap<Value> > MapParent;
362 ArcMap(const Adaptor& adaptor)
363 : MapParent(adaptor) {}
364 ArcMap(const Adaptor& adaptor, const Value& value)
365 : MapParent(adaptor, value) {}
368 ArcMap& operator=(const ArcMap& cmap) {
369 return operator=<ArcMap>(cmap);
372 template <typename CMap>
373 ArcMap& operator=(const CMap& cmap) {
374 MapParent::operator=(cmap);
379 template <typename _Value>
380 class EdgeMap : public SubMapExtender<Adaptor,
381 typename Parent::template EdgeMap<_Value> > {
383 typedef _Value Value;
384 typedef SubMapExtender<Adaptor, typename Parent::
385 template EdgeMap<Value> > MapParent;
387 EdgeMap(const Adaptor& adaptor)
388 : MapParent(adaptor) {}
390 EdgeMap(const Adaptor& adaptor, const Value& value)
391 : MapParent(adaptor, value) {}
394 EdgeMap& operator=(const EdgeMap& cmap) {
395 return operator=<EdgeMap>(cmap);
398 template <typename CMap>
399 EdgeMap& operator=(const CMap& cmap) {
400 MapParent::operator=(cmap);
407 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
408 class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
409 : public GraphAdaptorBase<_Graph> {
411 typedef _Graph Graph;
412 typedef SubGraphAdaptorBase Adaptor;
413 typedef GraphAdaptorBase<_Graph> Parent;
415 NodeFilterMap* _node_filter_map;
416 EdgeFilterMap* _edge_filter_map;
417 SubGraphAdaptorBase() : Parent(),
418 _node_filter_map(0), _edge_filter_map(0) { }
420 void setNodeFilterMap(NodeFilterMap& node_filter_map) {
421 _node_filter_map=&node_filter_map;
423 void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
424 _edge_filter_map=&edge_filter_map;
429 typedef typename Parent::Node Node;
430 typedef typename Parent::Arc Arc;
431 typedef typename Parent::Edge Edge;
433 void first(Node& i) const {
435 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
438 void first(Arc& i) const {
440 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
443 void first(Edge& i) const {
445 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
448 void firstIn(Arc& i, const Node& n) const {
449 Parent::firstIn(i, n);
450 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
453 void firstOut(Arc& i, const Node& n) const {
454 Parent::firstOut(i, n);
455 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
458 void firstInc(Edge& i, bool& d, const Node& n) const {
459 Parent::firstInc(i, d, n);
460 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
463 void next(Node& i) const {
465 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
467 void next(Arc& i) const {
469 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
471 void next(Edge& i) const {
473 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
475 void nextIn(Arc& i) const {
477 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
480 void nextOut(Arc& i) const {
482 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
484 void nextInc(Edge& i, bool& d) const {
485 Parent::nextInc(i, d);
486 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
489 void hide(const Node& n) const { _node_filter_map->set(n, false); }
490 void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
492 void unHide(const Node& n) const { _node_filter_map->set(n, true); }
493 void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
495 bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
496 bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
498 typedef False NodeNumTag;
499 typedef False EdgeNumTag;
501 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
502 Arc findArc(const Node& u, const Node& v,
503 const Arc& prev = INVALID) {
504 Arc arc = Parent::findArc(u, v, prev);
505 while (arc != INVALID && !(*_edge_filter_map)[arc]) {
506 arc = Parent::findArc(u, v, arc);
510 Edge findEdge(const Node& u, const Node& v,
511 const Edge& prev = INVALID) {
512 Edge edge = Parent::findEdge(u, v, prev);
513 while (edge != INVALID && !(*_edge_filter_map)[edge]) {
514 edge = Parent::findEdge(u, v, edge);
519 template <typename _Value>
520 class NodeMap : public SubMapExtender<Adaptor,
521 typename Parent::template NodeMap<_Value> > {
523 typedef _Value Value;
524 typedef SubMapExtender<Adaptor, typename Parent::
525 template NodeMap<Value> > MapParent;
527 NodeMap(const Adaptor& adaptor)
528 : MapParent(adaptor) {}
529 NodeMap(const Adaptor& adaptor, const Value& value)
530 : MapParent(adaptor, value) {}
533 NodeMap& operator=(const NodeMap& cmap) {
534 return operator=<NodeMap>(cmap);
537 template <typename CMap>
538 NodeMap& operator=(const CMap& cmap) {
539 MapParent::operator=(cmap);
544 template <typename _Value>
545 class ArcMap : public SubMapExtender<Adaptor,
546 typename Parent::template ArcMap<_Value> > {
548 typedef _Value Value;
549 typedef SubMapExtender<Adaptor, typename Parent::
550 template ArcMap<Value> > MapParent;
552 ArcMap(const Adaptor& adaptor)
553 : MapParent(adaptor) {}
554 ArcMap(const Adaptor& adaptor, const Value& value)
555 : MapParent(adaptor, value) {}
558 ArcMap& operator=(const ArcMap& cmap) {
559 return operator=<ArcMap>(cmap);
562 template <typename CMap>
563 ArcMap& operator=(const CMap& cmap) {
564 MapParent::operator=(cmap);
569 template <typename _Value>
570 class EdgeMap : public SubMapExtender<Adaptor,
571 typename Parent::template EdgeMap<_Value> > {
573 typedef _Value Value;
574 typedef SubMapExtender<Adaptor, typename Parent::
575 template EdgeMap<Value> > MapParent;
577 EdgeMap(const Adaptor& adaptor)
578 : MapParent(adaptor) {}
580 EdgeMap(const Adaptor& adaptor, const _Value& value)
581 : MapParent(adaptor, value) {}
584 EdgeMap& operator=(const EdgeMap& cmap) {
585 return operator=<EdgeMap>(cmap);
588 template <typename CMap>
589 EdgeMap& operator=(const CMap& cmap) {
590 MapParent::operator=(cmap);
597 /// \ingroup graph_adaptors
599 /// \brief A graph adaptor for hiding nodes and edges from an
600 /// undirected graph.
602 /// SubGraphAdaptor shows the graph with filtered node-set and
603 /// edge-set. If the \c checked parameter is true then it filters
604 /// the edge-set to do not get invalid edges which incident node is
607 /// If the \c checked template parameter is false then we have to
608 /// note that the node-iterator cares only the filter on the
609 /// node-set, and the edge-iterator cares only the filter on the
610 /// edge-set. This way the edge-map should filter all arcs which
611 /// has filtered end node.
612 template<typename _Graph, typename NodeFilterMap,
613 typename EdgeFilterMap, bool checked = true>
614 class SubGraphAdaptor :
615 public GraphAdaptorExtender<
616 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
618 typedef _Graph Graph;
619 typedef GraphAdaptorExtender<
620 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
622 typedef typename Parent::Node Node;
623 typedef typename Parent::Edge Edge;
626 SubGraphAdaptor() { }
629 /// \brief Constructor
631 /// Creates a sub-graph-adaptor for the given graph with
632 /// given node and edge map filters.
633 SubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map,
634 EdgeFilterMap& edge_filter_map) {
636 setNodeFilterMap(node_filter_map);
637 setEdgeFilterMap(edge_filter_map);
640 /// \brief Hides the node of the graph
642 /// This function hides \c n in the digraph, i.e. the iteration
643 /// jumps over it. This is done by simply setting the value of \c n
644 /// to be false in the corresponding node-map.
645 void hide(const Node& n) const { Parent::hide(n); }
647 /// \brief Hides the edge of the graph
649 /// This function hides \c e in the digraph, i.e. the iteration
650 /// jumps over it. This is done by simply setting the value of \c e
651 /// to be false in the corresponding edge-map.
652 void hide(const Edge& e) const { Parent::hide(e); }
654 /// \brief Unhides the node of the graph
656 /// The value of \c n is set to be true in the node-map which stores
657 /// hide information. If \c n was hidden previuosly, then it is shown
659 void unHide(const Node& n) const { Parent::unHide(n); }
661 /// \brief Unhides the edge of the graph
663 /// The value of \c e is set to be true in the edge-map which stores
664 /// hide information. If \c e was hidden previuosly, then it is shown
666 void unHide(const Edge& e) const { Parent::unHide(e); }
668 /// \brief Returns true if \c n is hidden.
670 /// Returns true if \c n is hidden.
672 bool hidden(const Node& n) const { return Parent::hidden(n); }
674 /// \brief Returns true if \c e is hidden.
676 /// Returns true if \c e is hidden.
678 bool hidden(const Edge& e) const { return Parent::hidden(e); }
681 /// \brief Just gives back a sub-graph adaptor
683 /// Just gives back a sub-graph adaptor
684 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
685 SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap>
686 subGraphAdaptor(const Graph& graph,
687 NodeFilterMap& nfm, ArcFilterMap& efm) {
688 return SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap>
692 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
693 SubGraphAdaptor<const Graph, const NodeFilterMap, ArcFilterMap>
694 subGraphAdaptor(const Graph& graph,
695 NodeFilterMap& nfm, ArcFilterMap& efm) {
696 return SubGraphAdaptor<const Graph, const NodeFilterMap, ArcFilterMap>
700 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
701 SubGraphAdaptor<const Graph, NodeFilterMap, const ArcFilterMap>
702 subGraphAdaptor(const Graph& graph,
703 NodeFilterMap& nfm, ArcFilterMap& efm) {
704 return SubGraphAdaptor<const Graph, NodeFilterMap, const ArcFilterMap>
708 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
709 SubGraphAdaptor<const Graph, const NodeFilterMap, const ArcFilterMap>
710 subGraphAdaptor(const Graph& graph,
711 NodeFilterMap& nfm, ArcFilterMap& efm) {
712 return SubGraphAdaptor<const Graph, const NodeFilterMap,
713 const ArcFilterMap>(graph, nfm, efm);
716 /// \ingroup graph_adaptors
718 /// \brief An adaptor for hiding nodes from an graph.
720 /// An adaptor for hiding nodes from an graph. This
721 /// adaptor specializes SubGraphAdaptor in the way that only the
722 /// node-set can be filtered. In usual case the checked parameter is
723 /// true, we get the induced subgraph. But if the checked parameter
724 /// is false then we can filter only isolated nodes.
725 template<typename _Graph, typename _NodeFilterMap, bool checked = true>
726 class NodeSubGraphAdaptor :
727 public SubGraphAdaptor<_Graph, _NodeFilterMap,
728 ConstMap<typename _Graph::Edge, bool>, checked> {
730 typedef _Graph Graph;
731 typedef _NodeFilterMap NodeFilterMap;
732 typedef SubGraphAdaptor<Graph, NodeFilterMap,
733 ConstMap<typename Graph::Edge, bool> > Parent;
735 typedef typename Parent::Node Node;
737 ConstMap<typename Graph::Edge, bool> const_true_map;
739 NodeSubGraphAdaptor() : const_true_map(true) {
740 Parent::setEdgeFilterMap(const_true_map);
745 /// \brief Constructor
747 /// Creates a node-sub-graph-adaptor for the given graph with
748 /// given node map filters.
749 NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map) :
750 Parent(), const_true_map(true) {
751 Parent::setGraph(_graph);
752 Parent::setNodeFilterMap(node_filter_map);
753 Parent::setEdgeFilterMap(const_true_map);
756 /// \brief Hides the node of the graph
758 /// This function hides \c n in the digraph, i.e. the iteration
759 /// jumps over it. This is done by simply setting the value of \c n
760 /// to be false in the corresponding node-map.
761 void hide(const Node& n) const { Parent::hide(n); }
763 /// \brief Unhides the node of the graph
765 /// The value of \c n is set to be true in the node-map which stores
766 /// hide information. If \c n was hidden previuosly, then it is shown
768 void unHide(const Node& n) const { Parent::unHide(n); }
770 /// \brief Returns true if \c n is hidden.
772 /// Returns true if \c n is hidden.
774 bool hidden(const Node& n) const { return Parent::hidden(n); }
778 /// \brief Just gives back a node-sub-graph adaptor
780 /// Just gives back a node-sub-graph adaptor
781 template<typename Graph, typename NodeFilterMap>
782 NodeSubGraphAdaptor<const Graph, NodeFilterMap>
783 nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) {
784 return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm);
787 template<typename Graph, typename NodeFilterMap>
788 NodeSubGraphAdaptor<const Graph, const NodeFilterMap>
789 nodeSubGraphAdaptor(const Graph& graph, const NodeFilterMap& nfm) {
790 return NodeSubGraphAdaptor<const Graph, const NodeFilterMap>(graph, nfm);
793 /// \ingroup graph_adaptors
795 /// \brief An adaptor for hiding edges from an graph.
797 /// \warning Graph adaptors are in even more experimental state
798 /// than the other parts of the lib. Use them at you own risk.
800 /// An adaptor for hiding edges from an graph.
801 /// This adaptor specializes SubGraphAdaptor in the way that
804 template<typename _Graph, typename _EdgeFilterMap>
805 class EdgeSubGraphAdaptor :
806 public SubGraphAdaptor<_Graph, ConstMap<typename _Graph::Node,bool>,
807 _EdgeFilterMap, false> {
809 typedef _Graph Graph;
810 typedef _EdgeFilterMap EdgeFilterMap;
811 typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
812 EdgeFilterMap, false> Parent;
813 typedef typename Parent::Edge Edge;
815 ConstMap<typename Graph::Node, bool> const_true_map;
817 EdgeSubGraphAdaptor() : const_true_map(true) {
818 Parent::setNodeFilterMap(const_true_map);
823 /// \brief Constructor
825 /// Creates a edge-sub-graph-adaptor for the given graph with
826 /// given node map filters.
827 EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& edge_filter_map) :
828 Parent(), const_true_map(true) {
829 Parent::setGraph(_graph);
830 Parent::setNodeFilterMap(const_true_map);
831 Parent::setEdgeFilterMap(edge_filter_map);
834 /// \brief Hides the edge of the graph
836 /// This function hides \c e in the digraph, i.e. the iteration
837 /// jumps over it. This is done by simply setting the value of \c e
838 /// to be false in the corresponding edge-map.
839 void hide(const Edge& e) const { Parent::hide(e); }
841 /// \brief Unhides the edge of the graph
843 /// The value of \c e is set to be true in the edge-map which stores
844 /// hide information. If \c e was hidden previuosly, then it is shown
846 void unHide(const Edge& e) const { Parent::unHide(e); }
848 /// \brief Returns true if \c e is hidden.
850 /// Returns true if \c e is hidden.
852 bool hidden(const Edge& e) const { return Parent::hidden(e); }
856 /// \brief Just gives back an edge-sub-graph adaptor
858 /// Just gives back an edge-sub-graph adaptor
859 template<typename Graph, typename EdgeFilterMap>
860 EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>
861 edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) {
862 return EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>(graph, efm);
865 template<typename Graph, typename EdgeFilterMap>
866 EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>
867 edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) {
868 return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm);
871 template <typename _Graph, typename _DirectionMap>
872 class DirGraphAdaptorBase {
875 typedef _Graph Graph;
876 typedef _DirectionMap DirectionMap;
878 typedef typename Graph::Node Node;
879 typedef typename Graph::Edge Arc;
881 /// \brief Reverse arc
883 /// It reverse the given arc. It simply negate the direction in the map.
884 void reverseArc(const Arc& arc) {
885 _direction->set(arc, !(*_direction)[arc]);
888 void first(Node& i) const { _graph->first(i); }
889 void first(Arc& i) const { _graph->first(i); }
890 void firstIn(Arc& i, const Node& n) const {
892 _graph->firstInc(i, d, n);
893 while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
895 void firstOut(Arc& i, const Node& n ) const {
897 _graph->firstInc(i, d, n);
898 while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
901 void next(Node& i) const { _graph->next(i); }
902 void next(Arc& i) const { _graph->next(i); }
903 void nextIn(Arc& i) const {
904 bool d = !(*_direction)[i];
905 _graph->nextInc(i, d);
906 while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
908 void nextOut(Arc& i) const {
909 bool d = (*_direction)[i];
910 _graph->nextInc(i, d);
911 while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
914 Node source(const Arc& e) const {
915 return (*_direction)[e] ? _graph->u(e) : _graph->v(e);
917 Node target(const Arc& e) const {
918 return (*_direction)[e] ? _graph->v(e) : _graph->u(e);
921 typedef NodeNumTagIndicator<Graph> NodeNumTag;
922 int nodeNum() const { return _graph->nodeNum(); }
924 typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
925 int arcNum() const { return _graph->edgeNum(); }
927 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
928 Arc findArc(const Node& u, const Node& v,
929 const Arc& prev = INVALID) {
931 bool d = arc == INVALID ? true : (*_direction)[arc];
933 arc = _graph->findEdge(u, v, arc);
934 while (arc != INVALID && !(*_direction)[arc]) {
935 _graph->findEdge(u, v, arc);
937 if (arc != INVALID) return arc;
939 _graph->findEdge(v, u, arc);
940 while (arc != INVALID && (*_direction)[arc]) {
941 _graph->findEdge(u, v, arc);
947 return Node(_graph->addNode());
950 Arc addArc(const Node& u, const Node& v) {
951 Arc arc = _graph->addArc(u, v);
952 _direction->set(arc, _graph->source(arc) == u);
956 void erase(const Node& i) { _graph->erase(i); }
957 void erase(const Arc& i) { _graph->erase(i); }
959 void clear() { _graph->clear(); }
961 int id(const Node& v) const { return _graph->id(v); }
962 int id(const Arc& e) const { return _graph->id(e); }
964 Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
965 Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
967 int maxNodeId() const { return _graph->maxNodeId(); }
968 int maxArcId() const { return _graph->maxEdgeId(); }
970 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
971 NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
973 typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
974 ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
976 template <typename _Value>
977 class NodeMap : public _Graph::template NodeMap<_Value> {
980 typedef typename _Graph::template NodeMap<_Value> Parent;
982 explicit NodeMap(const DirGraphAdaptorBase& adapter)
983 : Parent(*adapter._graph) {}
985 NodeMap(const DirGraphAdaptorBase& adapter, const _Value& value)
986 : Parent(*adapter._graph, value) {}
989 NodeMap& operator=(const NodeMap& cmap) {
990 return operator=<NodeMap>(cmap);
993 template <typename CMap>
994 NodeMap& operator=(const CMap& cmap) {
995 Parent::operator=(cmap);
1001 template <typename _Value>
1002 class ArcMap : public _Graph::template EdgeMap<_Value> {
1005 typedef typename Graph::template EdgeMap<_Value> Parent;
1007 explicit ArcMap(const DirGraphAdaptorBase& adapter)
1008 : Parent(*adapter._graph) { }
1010 ArcMap(const DirGraphAdaptorBase& adapter, const _Value& value)
1011 : Parent(*adapter._graph, value) { }
1014 ArcMap& operator=(const ArcMap& cmap) {
1015 return operator=<ArcMap>(cmap);
1018 template <typename CMap>
1019 ArcMap& operator=(const CMap& cmap) {
1020 Parent::operator=(cmap);
1029 DirectionMap* _direction;
1031 void setDirectionMap(DirectionMap& direction) {
1032 _direction = &direction;
1035 void setGraph(Graph& graph) {
1042 /// \ingroup graph_adaptors
1044 /// \brief A directed graph is made from an graph by an adaptor
1046 /// This adaptor gives a direction for each edge in the undirected
1047 /// graph. The direction of the arcs stored in the
1048 /// DirectionMap. This map is a bool map on the edges. If
1049 /// the edge is mapped to true then the direction of the directed
1050 /// arc will be the same as the default direction of the edge. The
1051 /// arcs can be easily reverted by the \ref
1052 /// DirGraphAdaptorBase::reverseArc "reverseArc()" member in the
1055 /// It can be used to solve orientation problems on directed graphs.
1056 /// For example how can we orient an graph to get the minimum
1057 /// number of strongly connected components. If we orient the arcs with
1058 /// the dfs algorithm out from the source then we will get such an
1061 /// We use the \ref DfsVisitor "visitor" interface of the
1062 /// \ref DfsVisit "dfs" algorithm:
1064 /// template <typename DirMap>
1065 /// class OrientVisitor : public DfsVisitor<Graph> {
1068 /// OrientVisitor(const Graph& graph, DirMap& dirMap)
1069 /// : _graph(graph), _dirMap(dirMap), _processed(graph, false) {}
1071 /// void discover(const Arc& arc) {
1072 /// _processed.set(arc, true);
1073 /// _dirMap.set(arc, _graph.direction(arc));
1076 /// void examine(const Arc& arc) {
1077 /// if (_processed[arc]) return;
1078 /// _processed.set(arc, true);
1079 /// _dirMap.set(arc, _graph.direction(arc));
1083 /// const Graph& _graph;
1084 /// DirMap& _dirMap;
1085 /// Graph::EdgeMap<bool> _processed;
1089 /// And now we can use the orientation:
1091 /// Graph::EdgeMap<bool> dmap(graph);
1093 /// typedef OrientVisitor<Graph::EdgeMap<bool> > Visitor;
1094 /// Visitor visitor(graph, dmap);
1096 /// DfsVisit<Graph, Visitor> dfs(graph, visitor);
1100 /// typedef DirGraphAdaptor<Graph> DGraph;
1101 /// DGraph dgraph(graph, dmap);
1103 /// LEMON_ASSERT(countStronglyConnectedComponents(dgraph) ==
1104 /// countBiArcConnectedComponents(graph), "Wrong Orientation");
1107 /// The number of the bi-connected components is a lower bound for
1108 /// the number of the strongly connected components in the directed
1109 /// graph because if we contract the bi-connected components to
1110 /// nodes we will get a tree therefore we cannot orient arcs in
1111 /// both direction between bi-connected components. In the other way
1112 /// the algorithm will orient one component to be strongly
1113 /// connected. The two relations proof that the assertion will
1114 /// be always true and the found solution is optimal.
1116 /// \sa DirGraphAdaptorBase
1117 /// \sa dirGraphAdaptor
1118 template<typename _Graph,
1119 typename DirectionMap = typename _Graph::template EdgeMap<bool> >
1120 class DirGraphAdaptor :
1121 public DigraphAdaptorExtender<DirGraphAdaptorBase<_Graph, DirectionMap> > {
1123 typedef _Graph Graph;
1124 typedef DigraphAdaptorExtender<
1125 DirGraphAdaptorBase<_Graph, DirectionMap> > Parent;
1126 typedef typename Parent::Arc Arc;
1128 DirGraphAdaptor() { }
1131 /// \brief Constructor of the adaptor
1133 /// Constructor of the adaptor
1134 DirGraphAdaptor(Graph& graph, DirectionMap& direction) {
1136 setDirectionMap(direction);
1139 /// \brief Reverse arc
1141 /// It reverse the given arc. It simply negate the direction in the map.
1142 void reverseArc(const Arc& a) {
1143 Parent::reverseArc(a);
1147 /// \brief Just gives back a DirGraphAdaptor
1149 /// Just gives back a DirGraphAdaptor
1150 template<typename Graph, typename DirectionMap>
1151 DirGraphAdaptor<const Graph, DirectionMap>
1152 dirGraphAdaptor(const Graph& graph, DirectionMap& dm) {
1153 return DirGraphAdaptor<const Graph, DirectionMap>(graph, dm);
1156 template<typename Graph, typename DirectionMap>
1157 DirGraphAdaptor<const Graph, const DirectionMap>
1158 dirGraphAdaptor(const Graph& graph, const DirectionMap& dm) {
1159 return DirGraphAdaptor<const Graph, const DirectionMap>(graph, dm);