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 /// \brief Base type for the Graph Adaptors
36 /// This is the base type for most of LEMON graph adaptors.
37 /// This class implements a trivial graph adaptor i.e. it only wraps the
38 /// functions and types of the graph. The purpose of this class is to
39 /// make easier implementing graph adaptors. E.g. if an adaptor is
40 /// considered which differs from the wrapped graph only in some of its
41 /// functions or types, then it can be derived from GraphAdaptor, and only
42 /// the differences should be implemented.
43 template<typename _Graph>
44 class GraphAdaptorBase {
47 typedef Graph ParentGraph;
52 GraphAdaptorBase() : _graph(0) {}
54 void setGraph(Graph& graph) { _graph = &graph; }
57 GraphAdaptorBase(Graph& graph) : _graph(&graph) {}
59 typedef typename Graph::Node Node;
60 typedef typename Graph::Arc Arc;
61 typedef typename Graph::Edge Edge;
63 void first(Node& i) const { _graph->first(i); }
64 void first(Arc& i) const { _graph->first(i); }
65 void first(Edge& i) const { _graph->first(i); }
66 void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); }
67 void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); }
68 void firstInc(Edge &i, bool &d, const Node &n) const {
69 _graph->firstInc(i, d, n);
72 void next(Node& i) const { _graph->next(i); }
73 void next(Arc& i) const { _graph->next(i); }
74 void next(Edge& i) const { _graph->next(i); }
75 void nextIn(Arc& i) const { _graph->nextIn(i); }
76 void nextOut(Arc& i) const { _graph->nextOut(i); }
77 void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); }
79 Node u(const Edge& e) const { return _graph->u(e); }
80 Node v(const Edge& e) const { return _graph->v(e); }
82 Node source(const Arc& a) const { return _graph->source(a); }
83 Node target(const Arc& a) const { return _graph->target(a); }
85 typedef NodeNumTagIndicator<Graph> NodeNumTag;
86 int nodeNum() const { return _graph->nodeNum(); }
88 typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
89 int arcNum() const { return _graph->arcNum(); }
90 int edgeNum() const { return _graph->edgeNum(); }
92 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
93 Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
94 return _graph->findArc(u, v, prev);
96 Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) {
97 return _graph->findEdge(u, v, prev);
100 Node addNode() { return _graph->addNode(); }
101 Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }
103 void erase(const Node& i) { _graph->erase(i); }
104 void erase(const Edge& i) { _graph->erase(i); }
106 void clear() { _graph->clear(); }
108 bool direction(const Arc& a) const { return _graph->direction(a); }
109 Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); }
111 int id(const Node& v) const { return _graph->id(v); }
112 int id(const Arc& a) const { return _graph->id(a); }
113 int id(const Edge& e) const { return _graph->id(e); }
115 Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
116 Arc arcFromId(int ix) const { return _graph->arcFromId(ix); }
117 Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); }
119 int maxNodeId() const { return _graph->maxNodeId(); }
120 int maxArcId() const { return _graph->maxArcId(); }
121 int maxEdgeId() const { return _graph->maxEdgeId(); }
123 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
124 NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
126 typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
127 ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
129 typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
130 EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
132 template <typename _Value>
133 class NodeMap : public Graph::template NodeMap<_Value> {
135 typedef typename Graph::template NodeMap<_Value> Parent;
136 explicit NodeMap(const GraphAdaptorBase<Graph>& adapter)
137 : Parent(*adapter._graph) {}
138 NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
139 : Parent(*adapter._graph, value) {}
142 NodeMap& operator=(const NodeMap& cmap) {
143 return operator=<NodeMap>(cmap);
146 template <typename CMap>
147 NodeMap& operator=(const CMap& cmap) {
148 Parent::operator=(cmap);
154 template <typename _Value>
155 class ArcMap : public Graph::template ArcMap<_Value> {
157 typedef typename Graph::template ArcMap<_Value> Parent;
158 explicit ArcMap(const GraphAdaptorBase<Graph>& adapter)
159 : Parent(*adapter._graph) {}
160 ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
161 : Parent(*adapter._graph, value) {}
164 ArcMap& operator=(const ArcMap& cmap) {
165 return operator=<ArcMap>(cmap);
168 template <typename CMap>
169 ArcMap& operator=(const CMap& cmap) {
170 Parent::operator=(cmap);
175 template <typename _Value>
176 class EdgeMap : public Graph::template EdgeMap<_Value> {
178 typedef typename Graph::template EdgeMap<_Value> Parent;
179 explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)
180 : Parent(*adapter._graph) {}
181 EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
182 : Parent(*adapter._graph, value) {}
185 EdgeMap& operator=(const EdgeMap& cmap) {
186 return operator=<EdgeMap>(cmap);
189 template <typename CMap>
190 EdgeMap& operator=(const CMap& cmap) {
191 Parent::operator=(cmap);
198 /// \ingroup graph_adaptors
200 /// \brief Trivial graph adaptor
202 /// This class is an adaptor which does not change the adapted undirected
203 /// graph. It can be used only to test the graph adaptors.
204 template <typename _Graph>
206 : public GraphAdaptorExtender< GraphAdaptorBase<_Graph> > {
208 typedef _Graph Graph;
209 typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent;
211 GraphAdaptor() : Parent() {}
214 explicit GraphAdaptor(Graph& graph) { setGraph(graph); }
217 template <typename _Graph, typename NodeFilterMap,
218 typename EdgeFilterMap, bool checked = true>
219 class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
221 typedef _Graph Graph;
222 typedef SubGraphAdaptorBase Adaptor;
223 typedef GraphAdaptorBase<_Graph> Parent;
226 NodeFilterMap* _node_filter_map;
227 EdgeFilterMap* _edge_filter_map;
229 SubGraphAdaptorBase()
230 : Parent(), _node_filter_map(0), _edge_filter_map(0) { }
232 void setNodeFilterMap(NodeFilterMap& node_filter_map) {
233 _node_filter_map=&node_filter_map;
235 void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
236 _edge_filter_map=&edge_filter_map;
241 typedef typename Parent::Node Node;
242 typedef typename Parent::Arc Arc;
243 typedef typename Parent::Edge Edge;
245 void first(Node& i) const {
247 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
250 void first(Arc& i) const {
252 while (i!=INVALID && (!(*_edge_filter_map)[i]
253 || !(*_node_filter_map)[Parent::source(i)]
254 || !(*_node_filter_map)[Parent::target(i)])) Parent::next(i);
257 void first(Edge& i) const {
259 while (i!=INVALID && (!(*_edge_filter_map)[i]
260 || !(*_node_filter_map)[Parent::u(i)]
261 || !(*_node_filter_map)[Parent::v(i)])) Parent::next(i);
264 void firstIn(Arc& i, const Node& n) const {
265 Parent::firstIn(i, n);
266 while (i!=INVALID && (!(*_edge_filter_map)[i]
267 || !(*_node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
270 void firstOut(Arc& i, const Node& n) const {
271 Parent::firstOut(i, n);
272 while (i!=INVALID && (!(*_edge_filter_map)[i]
273 || !(*_node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
276 void firstInc(Edge& i, bool& d, const Node& n) const {
277 Parent::firstInc(i, d, n);
278 while (i!=INVALID && (!(*_edge_filter_map)[i]
279 || !(*_node_filter_map)[Parent::u(i)]
280 || !(*_node_filter_map)[Parent::v(i)])) Parent::nextInc(i, d);
283 void next(Node& i) const {
285 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
288 void next(Arc& i) const {
290 while (i!=INVALID && (!(*_edge_filter_map)[i]
291 || !(*_node_filter_map)[Parent::source(i)]
292 || !(*_node_filter_map)[Parent::target(i)])) Parent::next(i);
295 void next(Edge& i) const {
297 while (i!=INVALID && (!(*_edge_filter_map)[i]
298 || !(*_node_filter_map)[Parent::u(i)]
299 || !(*_node_filter_map)[Parent::v(i)])) Parent::next(i);
302 void nextIn(Arc& i) const {
304 while (i!=INVALID && (!(*_edge_filter_map)[i]
305 || !(*_node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
308 void nextOut(Arc& i) const {
310 while (i!=INVALID && (!(*_edge_filter_map)[i]
311 || !(*_node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
314 void nextInc(Edge& i, bool& d) const {
315 Parent::nextInc(i, d);
316 while (i!=INVALID && (!(*_edge_filter_map)[i]
317 || !(*_node_filter_map)[Parent::u(i)]
318 || !(*_node_filter_map)[Parent::v(i)])) Parent::nextInc(i, d);
321 /// \brief Hide the given node in the graph.
323 /// This function hides \c n in the graph, i.e. the iteration
324 /// jumps over it. This is done by simply setting the value of \c n
325 /// to be false in the corresponding node-map.
326 void hide(const Node& n) const { _node_filter_map->set(n, false); }
328 /// \brief Hide the given edge in the graph.
330 /// This function hides \c e in the graph, i.e. the iteration
331 /// jumps over it. This is done by simply setting the value of \c e
332 /// to be false in the corresponding edge-map.
333 void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
335 /// \brief Unhide the given node in the graph.
337 /// The value of \c n is set to be true in the node-map which stores
338 /// hide information. If \c n was hidden previuosly, then it is shown
340 void unHide(const Node& n) const { _node_filter_map->set(n, true); }
342 /// \brief Hide the given edge in the graph.
344 /// The value of \c e is set to be true in the edge-map which stores
345 /// hide information. If \c e was hidden previuosly, then it is shown
347 void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
349 /// \brief Returns true if \c n is hidden.
351 /// Returns true if \c n is hidden.
352 bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
354 /// \brief Returns true if \c e is hidden.
356 /// Returns true if \c e is hidden.
357 bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
359 typedef False NodeNumTag;
360 typedef False EdgeNumTag;
362 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
363 Arc findArc(const Node& u, const Node& v,
364 const Arc& prev = INVALID) {
365 if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
368 Arc arc = Parent::findArc(u, v, prev);
369 while (arc != INVALID && !(*_edge_filter_map)[arc]) {
370 arc = Parent::findArc(u, v, arc);
374 Edge findEdge(const Node& u, const Node& v,
375 const Edge& prev = INVALID) {
376 if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
379 Edge edge = Parent::findEdge(u, v, prev);
380 while (edge != INVALID && !(*_edge_filter_map)[edge]) {
381 edge = Parent::findEdge(u, v, edge);
386 template <typename _Value>
387 class NodeMap : public SubMapExtender<Adaptor,
388 typename Parent::template NodeMap<_Value> > {
390 typedef _Value Value;
391 typedef SubMapExtender<Adaptor, typename Parent::
392 template NodeMap<Value> > MapParent;
394 NodeMap(const Adaptor& adaptor)
395 : MapParent(adaptor) {}
396 NodeMap(const Adaptor& adaptor, const Value& value)
397 : MapParent(adaptor, value) {}
400 NodeMap& operator=(const NodeMap& cmap) {
401 return operator=<NodeMap>(cmap);
404 template <typename CMap>
405 NodeMap& operator=(const CMap& cmap) {
406 MapParent::operator=(cmap);
411 template <typename _Value>
412 class ArcMap : public SubMapExtender<Adaptor,
413 typename Parent::template ArcMap<_Value> > {
415 typedef _Value Value;
416 typedef SubMapExtender<Adaptor, typename Parent::
417 template ArcMap<Value> > MapParent;
419 ArcMap(const Adaptor& adaptor)
420 : MapParent(adaptor) {}
421 ArcMap(const Adaptor& adaptor, const Value& value)
422 : MapParent(adaptor, value) {}
425 ArcMap& operator=(const ArcMap& cmap) {
426 return operator=<ArcMap>(cmap);
429 template <typename CMap>
430 ArcMap& operator=(const CMap& cmap) {
431 MapParent::operator=(cmap);
436 template <typename _Value>
437 class EdgeMap : public SubMapExtender<Adaptor,
438 typename Parent::template EdgeMap<_Value> > {
440 typedef _Value Value;
441 typedef SubMapExtender<Adaptor, typename Parent::
442 template EdgeMap<Value> > MapParent;
444 EdgeMap(const Adaptor& adaptor)
445 : MapParent(adaptor) {}
447 EdgeMap(const Adaptor& adaptor, const Value& value)
448 : MapParent(adaptor, value) {}
451 EdgeMap& operator=(const EdgeMap& cmap) {
452 return operator=<EdgeMap>(cmap);
455 template <typename CMap>
456 EdgeMap& operator=(const CMap& cmap) {
457 MapParent::operator=(cmap);
464 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
465 class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
466 : public GraphAdaptorBase<_Graph> {
468 typedef _Graph Graph;
469 typedef SubGraphAdaptorBase Adaptor;
470 typedef GraphAdaptorBase<_Graph> Parent;
472 NodeFilterMap* _node_filter_map;
473 EdgeFilterMap* _edge_filter_map;
474 SubGraphAdaptorBase() : Parent(),
475 _node_filter_map(0), _edge_filter_map(0) { }
477 void setNodeFilterMap(NodeFilterMap& node_filter_map) {
478 _node_filter_map=&node_filter_map;
480 void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
481 _edge_filter_map=&edge_filter_map;
486 typedef typename Parent::Node Node;
487 typedef typename Parent::Arc Arc;
488 typedef typename Parent::Edge Edge;
490 void first(Node& i) const {
492 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
495 void first(Arc& i) const {
497 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
500 void first(Edge& i) const {
502 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
505 void firstIn(Arc& i, const Node& n) const {
506 Parent::firstIn(i, n);
507 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
510 void firstOut(Arc& i, const Node& n) const {
511 Parent::firstOut(i, n);
512 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
515 void firstInc(Edge& i, bool& d, const Node& n) const {
516 Parent::firstInc(i, d, n);
517 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
520 void next(Node& i) const {
522 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
524 void next(Arc& i) const {
526 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
528 void next(Edge& i) const {
530 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
532 void nextIn(Arc& i) const {
534 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
537 void nextOut(Arc& i) const {
539 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
541 void nextInc(Edge& i, bool& d) const {
542 Parent::nextInc(i, d);
543 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
546 /// \brief Hide the given node in the graph.
548 /// This function hides \c n in the graph, i.e. the iteration
549 /// jumps over it. This is done by simply setting the value of \c n
550 /// to be false in the corresponding node-map.
551 void hide(const Node& n) const { _node_filter_map->set(n, false); }
553 /// \brief Hide the given edge in the graph.
555 /// This function hides \c e in the graph, i.e. the iteration
556 /// jumps over it. This is done by simply setting the value of \c e
557 /// to be false in the corresponding edge-map.
558 void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
560 /// \brief Unhide the given node in the graph.
562 /// The value of \c n is set to be true in the node-map which stores
563 /// hide information. If \c n was hidden previuosly, then it is shown
565 void unHide(const Node& n) const { _node_filter_map->set(n, true); }
567 /// \brief Hide the given edge in the graph.
569 /// The value of \c e is set to be true in the edge-map which stores
570 /// hide information. If \c e was hidden previuosly, then it is shown
572 void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
574 /// \brief Returns true if \c n is hidden.
576 /// Returns true if \c n is hidden.
577 bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
579 /// \brief Returns true if \c e is hidden.
581 /// Returns true if \c e is hidden.
582 bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
584 typedef False NodeNumTag;
585 typedef False EdgeNumTag;
587 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
588 Arc findArc(const Node& u, const Node& v,
589 const Arc& prev = INVALID) {
590 Arc arc = Parent::findArc(u, v, prev);
591 while (arc != INVALID && !(*_edge_filter_map)[arc]) {
592 arc = Parent::findArc(u, v, arc);
596 Edge findEdge(const Node& u, const Node& v,
597 const Edge& prev = INVALID) {
598 Edge edge = Parent::findEdge(u, v, prev);
599 while (edge != INVALID && !(*_edge_filter_map)[edge]) {
600 edge = Parent::findEdge(u, v, edge);
605 template <typename _Value>
606 class NodeMap : public SubMapExtender<Adaptor,
607 typename Parent::template NodeMap<_Value> > {
609 typedef _Value Value;
610 typedef SubMapExtender<Adaptor, typename Parent::
611 template NodeMap<Value> > MapParent;
613 NodeMap(const Adaptor& adaptor)
614 : MapParent(adaptor) {}
615 NodeMap(const Adaptor& adaptor, const Value& value)
616 : MapParent(adaptor, value) {}
619 NodeMap& operator=(const NodeMap& cmap) {
620 return operator=<NodeMap>(cmap);
623 template <typename CMap>
624 NodeMap& operator=(const CMap& cmap) {
625 MapParent::operator=(cmap);
630 template <typename _Value>
631 class ArcMap : public SubMapExtender<Adaptor,
632 typename Parent::template ArcMap<_Value> > {
634 typedef _Value Value;
635 typedef SubMapExtender<Adaptor, typename Parent::
636 template ArcMap<Value> > MapParent;
638 ArcMap(const Adaptor& adaptor)
639 : MapParent(adaptor) {}
640 ArcMap(const Adaptor& adaptor, const Value& value)
641 : MapParent(adaptor, value) {}
644 ArcMap& operator=(const ArcMap& cmap) {
645 return operator=<ArcMap>(cmap);
648 template <typename CMap>
649 ArcMap& operator=(const CMap& cmap) {
650 MapParent::operator=(cmap);
655 template <typename _Value>
656 class EdgeMap : public SubMapExtender<Adaptor,
657 typename Parent::template EdgeMap<_Value> > {
659 typedef _Value Value;
660 typedef SubMapExtender<Adaptor, typename Parent::
661 template EdgeMap<Value> > MapParent;
663 EdgeMap(const Adaptor& adaptor)
664 : MapParent(adaptor) {}
666 EdgeMap(const Adaptor& adaptor, const _Value& value)
667 : MapParent(adaptor, value) {}
670 EdgeMap& operator=(const EdgeMap& cmap) {
671 return operator=<EdgeMap>(cmap);
674 template <typename CMap>
675 EdgeMap& operator=(const CMap& cmap) {
676 MapParent::operator=(cmap);
683 /// \ingroup graph_adaptors
685 /// \brief A graph adaptor for hiding nodes and arcs from an
686 /// undirected graph.
688 /// SubGraphAdaptor shows the graph with filtered node-set and
689 /// edge-set. If the \c checked parameter is true then it filters
690 /// the edge-set to do not get invalid edges which incident node is
693 /// If the \c checked template parameter is false then we have to
694 /// note that the node-iterator cares only the filter on the
695 /// node-set, and the edge-iterator cares only the filter on the
696 /// edge-set. This way the edge-map should filter all arcs which
697 /// has filtered end node.
698 template<typename _Graph, typename NodeFilterMap,
699 typename EdgeFilterMap, bool checked = true>
700 class SubGraphAdaptor :
701 public GraphAdaptorExtender<
702 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
704 typedef _Graph Graph;
705 typedef GraphAdaptorExtender<
706 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
708 SubGraphAdaptor() { }
710 SubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map,
711 EdgeFilterMap& edge_filter_map) {
713 setNodeFilterMap(node_filter_map);
714 setEdgeFilterMap(edge_filter_map);
718 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
719 SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap>
720 subGraphAdaptor(const Graph& graph,
721 NodeFilterMap& nfm, ArcFilterMap& efm) {
722 return SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap>
726 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
727 SubGraphAdaptor<const Graph, const NodeFilterMap, ArcFilterMap>
728 subGraphAdaptor(const Graph& graph,
729 NodeFilterMap& nfm, ArcFilterMap& efm) {
730 return SubGraphAdaptor<const Graph, const NodeFilterMap, ArcFilterMap>
734 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
735 SubGraphAdaptor<const Graph, NodeFilterMap, const ArcFilterMap>
736 subGraphAdaptor(const Graph& graph,
737 NodeFilterMap& nfm, ArcFilterMap& efm) {
738 return SubGraphAdaptor<const Graph, NodeFilterMap, const ArcFilterMap>
742 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
743 SubGraphAdaptor<const Graph, const NodeFilterMap, const ArcFilterMap>
744 subGraphAdaptor(const Graph& graph,
745 NodeFilterMap& nfm, ArcFilterMap& efm) {
746 return SubGraphAdaptor<const Graph, const NodeFilterMap,
747 const ArcFilterMap>(graph, nfm, efm);
750 /// \ingroup graph_adaptors
752 /// \brief An adaptor for hiding nodes from an graph.
754 /// An adaptor for hiding nodes from an graph. This
755 /// adaptor specializes SubGraphAdaptor in the way that only the
756 /// node-set can be filtered. In usual case the checked parameter is
757 /// true, we get the induced subgraph. But if the checked parameter
758 /// is false then we can filter only isolated nodes.
759 template<typename _Graph, typename _NodeFilterMap, bool checked = true>
760 class NodeSubGraphAdaptor :
761 public SubGraphAdaptor<_Graph, _NodeFilterMap,
762 ConstMap<typename _Graph::Edge, bool>, checked> {
764 typedef _Graph Graph;
765 typedef _NodeFilterMap NodeFilterMap;
766 typedef SubGraphAdaptor<Graph, NodeFilterMap,
767 ConstMap<typename Graph::Edge, bool> > Parent;
769 ConstMap<typename Graph::Edge, bool> const_true_map;
771 NodeSubGraphAdaptor() : const_true_map(true) {
772 Parent::setEdgeFilterMap(const_true_map);
776 NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map) :
777 Parent(), const_true_map(true) {
778 Parent::setGraph(_graph);
779 Parent::setNodeFilterMap(node_filter_map);
780 Parent::setEdgeFilterMap(const_true_map);
784 template<typename Graph, typename NodeFilterMap>
785 NodeSubGraphAdaptor<const Graph, NodeFilterMap>
786 nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) {
787 return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm);
790 template<typename Graph, typename NodeFilterMap>
791 NodeSubGraphAdaptor<const Graph, const NodeFilterMap>
792 nodeSubGraphAdaptor(const Graph& graph, const NodeFilterMap& nfm) {
793 return NodeSubGraphAdaptor<const Graph, const NodeFilterMap>(graph, nfm);
796 /// \ingroup graph_adaptors
798 /// \brief An adaptor for hiding edges from an graph.
800 /// \warning Graph adaptors are in even more experimental state
801 /// than the other parts of the lib. Use them at you own risk.
803 /// An adaptor for hiding edges from an graph.
804 /// This adaptor specializes SubGraphAdaptor in the way that
807 template<typename _Graph, typename _EdgeFilterMap>
808 class EdgeSubGraphAdaptor :
809 public SubGraphAdaptor<_Graph, ConstMap<typename _Graph::Node,bool>,
810 _EdgeFilterMap, false> {
812 typedef _Graph Graph;
813 typedef _EdgeFilterMap EdgeFilterMap;
814 typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
815 EdgeFilterMap, false> Parent;
817 ConstMap<typename Graph::Node, bool> const_true_map;
819 EdgeSubGraphAdaptor() : const_true_map(true) {
820 Parent::setNodeFilterMap(const_true_map);
825 EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& edge_filter_map) :
826 Parent(), const_true_map(true) {
827 Parent::setGraph(_graph);
828 Parent::setNodeFilterMap(const_true_map);
829 Parent::setEdgeFilterMap(edge_filter_map);
834 template<typename Graph, typename EdgeFilterMap>
835 EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>
836 edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) {
837 return EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>(graph, efm);
840 template<typename Graph, typename EdgeFilterMap>
841 EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>
842 edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) {
843 return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm);
846 /// \brief Base of direct graph adaptor
848 /// Base class of the direct graph adaptor. All public member
849 /// of this class can be used with the DirGraphAdaptor too.
850 /// \sa DirGraphAdaptor
851 template <typename _Graph, typename _DirectionMap>
852 class DirGraphAdaptorBase {
855 typedef _Graph Graph;
856 typedef _DirectionMap DirectionMap;
858 typedef typename Graph::Node Node;
859 typedef typename Graph::Edge Arc;
861 /// \brief Reverse arc
863 /// It reverse the given arc. It simply negate the direction in the map.
864 void reverseArc(const Arc& arc) {
865 _direction->set(arc, !(*_direction)[arc]);
868 void first(Node& i) const { _graph->first(i); }
869 void first(Arc& i) const { _graph->first(i); }
870 void firstIn(Arc& i, const Node& n) const {
872 _graph->firstInc(i, d, n);
873 while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
875 void firstOut(Arc& i, const Node& n ) const {
877 _graph->firstInc(i, d, n);
878 while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
881 void next(Node& i) const { _graph->next(i); }
882 void next(Arc& i) const { _graph->next(i); }
883 void nextIn(Arc& i) const {
884 bool d = !(*_direction)[i];
885 _graph->nextInc(i, d);
886 while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
888 void nextOut(Arc& i) const {
889 bool d = (*_direction)[i];
890 _graph->nextInc(i, d);
891 while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
894 Node source(const Arc& e) const {
895 return (*_direction)[e] ? _graph->u(e) : _graph->v(e);
897 Node target(const Arc& e) const {
898 return (*_direction)[e] ? _graph->v(e) : _graph->u(e);
901 typedef NodeNumTagIndicator<Graph> NodeNumTag;
902 int nodeNum() const { return _graph->nodeNum(); }
904 typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
905 int arcNum() const { return _graph->edgeNum(); }
907 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
908 Arc findArc(const Node& u, const Node& v,
909 const Arc& prev = INVALID) {
911 bool d = arc == INVALID ? true : (*_direction)[arc];
913 arc = _graph->findEdge(u, v, arc);
914 while (arc != INVALID && !(*_direction)[arc]) {
915 _graph->findEdge(u, v, arc);
917 if (arc != INVALID) return arc;
919 _graph->findEdge(v, u, arc);
920 while (arc != INVALID && (*_direction)[arc]) {
921 _graph->findEdge(u, v, arc);
927 return Node(_graph->addNode());
930 Arc addArc(const Node& u, const Node& v) {
931 Arc arc = _graph->addArc(u, v);
932 _direction->set(arc, _graph->source(arc) == u);
936 void erase(const Node& i) { _graph->erase(i); }
937 void erase(const Arc& i) { _graph->erase(i); }
939 void clear() { _graph->clear(); }
941 int id(const Node& v) const { return _graph->id(v); }
942 int id(const Arc& e) const { return _graph->id(e); }
944 Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
945 Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
947 int maxNodeId() const { return _graph->maxNodeId(); }
948 int maxArcId() const { return _graph->maxEdgeId(); }
950 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
951 NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
953 typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
954 ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
956 template <typename _Value>
957 class NodeMap : public _Graph::template NodeMap<_Value> {
960 typedef typename _Graph::template NodeMap<_Value> Parent;
962 explicit NodeMap(const DirGraphAdaptorBase& adapter)
963 : Parent(*adapter._graph) {}
965 NodeMap(const DirGraphAdaptorBase& adapter, const _Value& value)
966 : Parent(*adapter._graph, value) {}
969 NodeMap& operator=(const NodeMap& cmap) {
970 return operator=<NodeMap>(cmap);
973 template <typename CMap>
974 NodeMap& operator=(const CMap& cmap) {
975 Parent::operator=(cmap);
981 template <typename _Value>
982 class ArcMap : public _Graph::template EdgeMap<_Value> {
985 typedef typename Graph::template EdgeMap<_Value> Parent;
987 explicit ArcMap(const DirGraphAdaptorBase& adapter)
988 : Parent(*adapter._graph) { }
990 ArcMap(const DirGraphAdaptorBase& adapter, const _Value& value)
991 : Parent(*adapter._graph, value) { }
994 ArcMap& operator=(const ArcMap& cmap) {
995 return operator=<ArcMap>(cmap);
998 template <typename CMap>
999 ArcMap& operator=(const CMap& cmap) {
1000 Parent::operator=(cmap);
1009 DirectionMap* _direction;
1011 void setDirectionMap(DirectionMap& direction) {
1012 _direction = &direction;
1015 void setGraph(Graph& graph) {
1022 /// \ingroup graph_adaptors
1024 /// \brief A directed graph is made from an graph by an adaptor
1026 /// This adaptor gives a direction for each edge in the undirected
1027 /// graph. The direction of the arcs stored in the
1028 /// DirectionMap. This map is a bool map on the edges. If
1029 /// the edge is mapped to true then the direction of the directed
1030 /// arc will be the same as the default direction of the edge. The
1031 /// arcs can be easily reverted by the \ref
1032 /// DirGraphAdaptorBase::reverseArc "reverseArc()" member in the
1035 /// It can be used to solve orientation problems on directed graphs.
1036 /// For example how can we orient an graph to get the minimum
1037 /// number of strongly connected components. If we orient the arcs with
1038 /// the dfs algorithm out from the source then we will get such an
1041 /// We use the \ref DfsVisitor "visitor" interface of the
1042 /// \ref DfsVisit "dfs" algorithm:
1044 /// template <typename DirMap>
1045 /// class OrientVisitor : public DfsVisitor<Graph> {
1048 /// OrientVisitor(const Graph& graph, DirMap& dirMap)
1049 /// : _graph(graph), _dirMap(dirMap), _processed(graph, false) {}
1051 /// void discover(const Arc& arc) {
1052 /// _processed.set(arc, true);
1053 /// _dirMap.set(arc, _graph.direction(arc));
1056 /// void examine(const Arc& arc) {
1057 /// if (_processed[arc]) return;
1058 /// _processed.set(arc, true);
1059 /// _dirMap.set(arc, _graph.direction(arc));
1063 /// const Graph& _graph;
1064 /// DirMap& _dirMap;
1065 /// Graph::EdgeMap<bool> _processed;
1069 /// And now we can use the orientation:
1071 /// Graph::EdgeMap<bool> dmap(graph);
1073 /// typedef OrientVisitor<Graph::EdgeMap<bool> > Visitor;
1074 /// Visitor visitor(graph, dmap);
1076 /// DfsVisit<Graph, Visitor> dfs(graph, visitor);
1080 /// typedef DirGraphAdaptor<Graph> DGraph;
1081 /// DGraph dgraph(graph, dmap);
1083 /// LEMON_ASSERT(countStronglyConnectedComponents(dgraph) ==
1084 /// countBiArcConnectedComponents(graph), "Wrong Orientation");
1087 /// The number of the bi-connected components is a lower bound for
1088 /// the number of the strongly connected components in the directed
1089 /// graph because if we contract the bi-connected components to
1090 /// nodes we will get a tree therefore we cannot orient arcs in
1091 /// both direction between bi-connected components. In the other way
1092 /// the algorithm will orient one component to be strongly
1093 /// connected. The two relations proof that the assertion will
1094 /// be always true and the found solution is optimal.
1096 /// \sa DirGraphAdaptorBase
1097 /// \sa dirGraphAdaptor
1098 template<typename _Graph,
1099 typename DirectionMap = typename _Graph::template EdgeMap<bool> >
1100 class DirGraphAdaptor :
1101 public DigraphAdaptorExtender<DirGraphAdaptorBase<_Graph, DirectionMap> > {
1103 typedef _Graph Graph;
1104 typedef DigraphAdaptorExtender<
1105 DirGraphAdaptorBase<_Graph, DirectionMap> > Parent;
1107 DirGraphAdaptor() { }
1110 /// \brief Constructor of the adaptor
1112 /// Constructor of the adaptor
1113 DirGraphAdaptor(Graph& graph, DirectionMap& direction) {
1115 setDirectionMap(direction);
1119 /// \brief Just gives back a DirGraphAdaptor
1121 /// Just gives back a DirGraphAdaptor
1122 template<typename Graph, typename DirectionMap>
1123 DirGraphAdaptor<const Graph, DirectionMap>
1124 dirGraphAdaptor(const Graph& graph, DirectionMap& dm) {
1125 return DirGraphAdaptor<const Graph, DirectionMap>(graph, dm);
1128 template<typename Graph, typename DirectionMap>
1129 DirGraphAdaptor<const Graph, const DirectionMap>
1130 dirGraphAdaptor(const Graph& graph, const DirectionMap& dm) {
1131 return DirGraphAdaptor<const Graph, const DirectionMap>(graph, dm);