Better handling of inexact computation.
We do not use tolerance for excess, just for edges
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
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_UGRAPH_ADAPTOR_H
20 #define LEMON_UGRAPH_ADAPTOR_H
22 ///\ingroup graph_adaptors
24 ///\brief Several graph adaptors.
26 ///This file contains several useful ugraph adaptor functions.
28 ///\author Balazs Dezso
30 #include <lemon/bits/invalid.h>
31 #include <lemon/maps.h>
33 #include <lemon/bits/graph_adaptor_extender.h>
35 #include <lemon/bits/traits.h>
41 /// \brief Base type for the Graph Adaptors
43 /// This is the base type for most of LEMON graph adaptors.
44 /// This class implements a trivial graph adaptor i.e. it only wraps the
45 /// functions and types of the graph. The purpose of this class is to
46 /// make easier implementing graph adaptors. E.g. if an adaptor is
47 /// considered which differs from the wrapped graph only in some of its
48 /// functions or types, then it can be derived from GraphAdaptor, and only
49 /// the differences should be implemented.
51 /// \author Balazs Dezso
52 template<typename _UGraph>
53 class UGraphAdaptorBase {
55 typedef _UGraph Graph;
56 typedef Graph ParentGraph;
61 UGraphAdaptorBase() : graph(0) {}
63 void setGraph(Graph& _graph) { graph=&_graph; }
66 UGraphAdaptorBase(Graph& _graph) : graph(&_graph) {}
68 typedef typename Graph::Node Node;
69 typedef typename Graph::Edge Edge;
70 typedef typename Graph::UEdge UEdge;
72 void first(Node& i) const { graph->first(i); }
73 void first(Edge& i) const { graph->first(i); }
74 void first(UEdge& i) const { graph->first(i); }
75 void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
76 void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
77 void firstInc(UEdge &i, bool &d, const Node &n) const {
78 graph->firstInc(i, d, n);
81 void next(Node& i) const { graph->next(i); }
82 void next(Edge& i) const { graph->next(i); }
83 void next(UEdge& i) const { graph->next(i); }
84 void nextIn(Edge& i) const { graph->nextIn(i); }
85 void nextOut(Edge& i) const { graph->nextOut(i); }
86 void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); }
88 Node source(const UEdge& e) const { return graph->source(e); }
89 Node target(const UEdge& e) const { return graph->target(e); }
91 Node source(const Edge& e) const { return graph->source(e); }
92 Node target(const Edge& e) const { return graph->target(e); }
94 typedef NodeNumTagIndicator<Graph> NodeNumTag;
95 int nodeNum() const { return graph->nodeNum(); }
97 typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
98 int edgeNum() const { return graph->edgeNum(); }
99 int uEdgeNum() const { return graph->uEdgeNum(); }
101 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
102 Edge findEdge(const Node& source, const Node& target,
103 const Edge& prev = INVALID) {
104 return graph->findEdge(source, target, prev);
106 UEdge findUEdge(const Node& source, const Node& target,
107 const UEdge& prev = INVALID) {
108 return graph->findUEdge(source, target, prev);
111 Node addNode() const { return graph->addNode(); }
112 UEdge addEdge(const Node& source, const Node& target) const {
113 return graph->addEdge(source, target);
116 void erase(const Node& i) const { graph->erase(i); }
117 void erase(const UEdge& i) const { graph->erase(i); }
119 void clear() const { graph->clear(); }
121 bool direction(const Edge& e) const { return graph->direction(e); }
122 Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); }
124 int id(const Node& v) const { return graph->id(v); }
125 int id(const Edge& e) const { return graph->id(e); }
126 int id(const UEdge& e) const { return graph->id(e); }
128 Node fromNodeId(int id) const {
129 return graph->fromNodeId(id);
132 Edge fromEdgeId(int id) const {
133 return graph->fromEdgeId(id);
136 UEdge fromUEdgeId(int id) const {
137 return graph->fromUEdgeId(id);
140 int maxNodeId() const {
141 return graph->maxNodeId();
144 int maxEdgeId() const {
145 return graph->maxEdgeId();
148 int maxUEdgeId() const {
149 return graph->maxEdgeId();
152 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
154 NodeNotifier& getNotifier(Node) const {
155 return graph->getNotifier(Node());
158 typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
160 EdgeNotifier& getNotifier(Edge) const {
161 return graph->getNotifier(Edge());
164 typedef typename ItemSetTraits<Graph, UEdge>::ItemNotifier UEdgeNotifier;
166 UEdgeNotifier& getNotifier(UEdge) const {
167 return graph->getNotifier(UEdge());
170 template <typename _Value>
171 class NodeMap : public Graph::template NodeMap<_Value> {
173 typedef typename Graph::template NodeMap<_Value> Parent;
174 explicit NodeMap(const UGraphAdaptorBase<Graph>& ga)
175 : Parent(*ga.graph) {}
176 NodeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
177 : Parent(*ga.graph, value) {}
179 NodeMap& operator=(const NodeMap& cmap) {
180 return operator=<NodeMap>(cmap);
183 template <typename CMap>
184 NodeMap& operator=(const CMap& cmap) {
185 Parent::operator=(cmap);
191 template <typename _Value>
192 class EdgeMap : public Graph::template EdgeMap<_Value> {
194 typedef typename Graph::template EdgeMap<_Value> Parent;
195 explicit EdgeMap(const UGraphAdaptorBase<Graph>& ga)
196 : Parent(*ga.graph) {}
197 EdgeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
198 : Parent(*ga.graph, value) {}
200 EdgeMap& operator=(const EdgeMap& cmap) {
201 return operator=<EdgeMap>(cmap);
204 template <typename CMap>
205 EdgeMap& operator=(const CMap& cmap) {
206 Parent::operator=(cmap);
211 template <typename _Value>
212 class UEdgeMap : public Graph::template UEdgeMap<_Value> {
214 typedef typename Graph::template UEdgeMap<_Value> Parent;
215 explicit UEdgeMap(const UGraphAdaptorBase<Graph>& ga)
216 : Parent(*ga.graph) {}
217 UEdgeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
218 : Parent(*ga.graph, value) {}
220 UEdgeMap& operator=(const UEdgeMap& cmap) {
221 return operator=<UEdgeMap>(cmap);
224 template <typename CMap>
225 UEdgeMap& operator=(const CMap& cmap) {
226 Parent::operator=(cmap);
233 /// \ingroup graph_adaptors
235 /// \brief Trivial undirected graph adaptor
237 /// This class is an adaptor which does not change the adapted undirected
238 /// graph. It can be used only to test the undirected graph adaptors.
239 template <typename _UGraph>
241 : public UGraphAdaptorExtender< UGraphAdaptorBase<_UGraph> > {
243 typedef _UGraph Graph;
244 typedef UGraphAdaptorExtender<UGraphAdaptorBase<_UGraph> > Parent;
246 UGraphAdaptor() : Parent() {}
249 explicit UGraphAdaptor(Graph& _graph) { setGraph(_graph); }
252 template <typename _UGraph, typename NodeFilterMap,
253 typename UEdgeFilterMap, bool checked = true>
254 class SubUGraphAdaptorBase : public UGraphAdaptorBase<_UGraph> {
256 typedef _UGraph Graph;
257 typedef SubUGraphAdaptorBase Adaptor;
258 typedef UGraphAdaptorBase<_UGraph> Parent;
261 NodeFilterMap* node_filter_map;
262 UEdgeFilterMap* uedge_filter_map;
264 SubUGraphAdaptorBase()
265 : Parent(), node_filter_map(0), uedge_filter_map(0) { }
267 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
268 node_filter_map=&_node_filter_map;
270 void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {
271 uedge_filter_map=&_uedge_filter_map;
276 typedef typename Parent::Node Node;
277 typedef typename Parent::Edge Edge;
278 typedef typename Parent::UEdge UEdge;
280 void first(Node& i) const {
282 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
285 void first(Edge& i) const {
287 while (i!=INVALID && (!(*uedge_filter_map)[i]
288 || !(*node_filter_map)[Parent::source(i)]
289 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
292 void first(UEdge& i) const {
294 while (i!=INVALID && (!(*uedge_filter_map)[i]
295 || !(*node_filter_map)[Parent::source(i)]
296 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
299 void firstIn(Edge& i, const Node& n) const {
300 Parent::firstIn(i, n);
301 while (i!=INVALID && (!(*uedge_filter_map)[i]
302 || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
305 void firstOut(Edge& i, const Node& n) const {
306 Parent::firstOut(i, n);
307 while (i!=INVALID && (!(*uedge_filter_map)[i]
308 || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
311 void firstInc(UEdge& i, bool& d, const Node& n) const {
312 Parent::firstInc(i, d, n);
313 while (i!=INVALID && (!(*uedge_filter_map)[i]
314 || !(*node_filter_map)[Parent::target(i)])) Parent::nextInc(i, d);
317 void next(Node& i) const {
319 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
322 void next(Edge& i) const {
324 while (i!=INVALID && (!(*uedge_filter_map)[i]
325 || !(*node_filter_map)[Parent::source(i)]
326 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
329 void next(UEdge& i) const {
331 while (i!=INVALID && (!(*uedge_filter_map)[i]
332 || !(*node_filter_map)[Parent::source(i)]
333 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
336 void nextIn(Edge& i) const {
338 while (i!=INVALID && (!(*uedge_filter_map)[i]
339 || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
342 void nextOut(Edge& i) const {
344 while (i!=INVALID && (!(*uedge_filter_map)[i]
345 || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
348 void nextInc(UEdge& i, bool& d) const {
349 Parent::nextInc(i, d);
350 while (i!=INVALID && (!(*uedge_filter_map)[i]
351 || !(*node_filter_map)[Parent::source(i)])) Parent::nextInc(i, d);
354 /// \brief Hide the given node in the graph.
356 /// This function hides \c n in the graph, i.e. the iteration
357 /// jumps over it. This is done by simply setting the value of \c n
358 /// to be false in the corresponding node-map.
359 void hide(const Node& n) const { node_filter_map->set(n, false); }
361 /// \brief Hide the given undirected edge in the graph.
363 /// This function hides \c e in the graph, i.e. the iteration
364 /// jumps over it. This is done by simply setting the value of \c e
365 /// to be false in the corresponding uedge-map.
366 void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
368 /// \brief Unhide the given node in the graph.
370 /// The value of \c n is set to be true in the node-map which stores
371 /// hide information. If \c n was hidden previuosly, then it is shown
373 void unHide(const Node& n) const { node_filter_map->set(n, true); }
375 /// \brief Hide the given undirected edge in the graph.
377 /// The value of \c e is set to be true in the uedge-map which stores
378 /// hide information. If \c e was hidden previuosly, then it is shown
380 void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
382 /// \brief Returns true if \c n is hidden.
384 /// Returns true if \c n is hidden.
385 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
387 /// \brief Returns true if \c e is hidden.
389 /// Returns true if \c e is hidden.
390 bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
392 typedef False NodeNumTag;
393 typedef False EdgeNumTag;
395 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
396 Edge findEdge(const Node& source, const Node& target,
397 const Edge& prev = INVALID) {
398 if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
401 Edge edge = Parent::findEdge(source, target, prev);
402 while (edge != INVALID && !(*uedge_filter_map)[edge]) {
403 edge = Parent::findEdge(source, target, edge);
407 UEdge findUEdge(const Node& source, const Node& target,
408 const UEdge& prev = INVALID) {
409 if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
412 UEdge uedge = Parent::findUEdge(source, target, prev);
413 while (uedge != INVALID && !(*uedge_filter_map)[uedge]) {
414 uedge = Parent::findUEdge(source, target, uedge);
419 template <typename _Value>
421 : public SubMapExtender<Adaptor,
422 typename Parent::template NodeMap<_Value> >
425 typedef Adaptor Graph;
426 typedef SubMapExtender<Adaptor, typename Parent::
427 template NodeMap<_Value> > Parent;
429 NodeMap(const Graph& graph)
431 NodeMap(const Graph& graph, const _Value& value)
432 : Parent(graph, value) {}
434 NodeMap& operator=(const NodeMap& cmap) {
435 return operator=<NodeMap>(cmap);
438 template <typename CMap>
439 NodeMap& operator=(const CMap& cmap) {
440 Parent::operator=(cmap);
445 template <typename _Value>
447 : public SubMapExtender<Adaptor,
448 typename Parent::template EdgeMap<_Value> >
451 typedef Adaptor Graph;
452 typedef SubMapExtender<Adaptor, typename Parent::
453 template EdgeMap<_Value> > Parent;
455 EdgeMap(const Graph& graph)
457 EdgeMap(const Graph& graph, const _Value& value)
458 : Parent(graph, value) {}
460 EdgeMap& operator=(const EdgeMap& cmap) {
461 return operator=<EdgeMap>(cmap);
464 template <typename CMap>
465 EdgeMap& operator=(const CMap& cmap) {
466 Parent::operator=(cmap);
471 template <typename _Value>
473 : public SubMapExtender<Adaptor,
474 typename Parent::template UEdgeMap<_Value> >
477 typedef Adaptor Graph;
478 typedef SubMapExtender<Adaptor, typename Parent::
479 template UEdgeMap<_Value> > Parent;
481 UEdgeMap(const Graph& graph)
483 UEdgeMap(const Graph& graph, const _Value& value)
484 : Parent(graph, value) {}
486 UEdgeMap& operator=(const UEdgeMap& cmap) {
487 return operator=<UEdgeMap>(cmap);
490 template <typename CMap>
491 UEdgeMap& operator=(const CMap& cmap) {
492 Parent::operator=(cmap);
499 template <typename _UGraph, typename NodeFilterMap, typename UEdgeFilterMap>
500 class SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, false>
501 : public UGraphAdaptorBase<_UGraph> {
503 typedef _UGraph Graph;
504 typedef SubUGraphAdaptorBase Adaptor;
505 typedef UGraphAdaptorBase<_UGraph> Parent;
507 NodeFilterMap* node_filter_map;
508 UEdgeFilterMap* uedge_filter_map;
509 SubUGraphAdaptorBase() : Parent(),
510 node_filter_map(0), uedge_filter_map(0) { }
512 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
513 node_filter_map=&_node_filter_map;
515 void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {
516 uedge_filter_map=&_uedge_filter_map;
521 typedef typename Parent::Node Node;
522 typedef typename Parent::Edge Edge;
523 typedef typename Parent::UEdge UEdge;
525 void first(Node& i) const {
527 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
530 void first(Edge& i) const {
532 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
535 void first(UEdge& i) const {
537 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
540 void firstIn(Edge& i, const Node& n) const {
541 Parent::firstIn(i, n);
542 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextIn(i);
545 void firstOut(Edge& i, const Node& n) const {
546 Parent::firstOut(i, n);
547 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextOut(i);
550 void firstInc(UEdge& i, bool& d, const Node& n) const {
551 Parent::firstInc(i, d, n);
552 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d);
555 void next(Node& i) const {
557 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
559 void next(Edge& i) const {
561 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
563 void next(UEdge& i) const {
565 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
567 void nextIn(Edge& i) const {
569 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextIn(i);
572 void nextOut(Edge& i) const {
574 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextOut(i);
576 void nextInc(UEdge& i, bool& d) const {
577 Parent::nextInc(i, d);
578 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d);
581 /// \brief Hide the given node in the graph.
583 /// This function hides \c n in the graph, i.e. the iteration
584 /// jumps over it. This is done by simply setting the value of \c n
585 /// to be false in the corresponding node-map.
586 void hide(const Node& n) const { node_filter_map->set(n, false); }
588 /// \brief Hide the given undirected edge in the graph.
590 /// This function hides \c e in the graph, i.e. the iteration
591 /// jumps over it. This is done by simply setting the value of \c e
592 /// to be false in the corresponding uedge-map.
593 void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
595 /// \brief Unhide the given node in the graph.
597 /// The value of \c n is set to be true in the node-map which stores
598 /// hide information. If \c n was hidden previuosly, then it is shown
600 void unHide(const Node& n) const { node_filter_map->set(n, true); }
602 /// \brief Hide the given undirected edge in the graph.
604 /// The value of \c e is set to be true in the uedge-map which stores
605 /// hide information. If \c e was hidden previuosly, then it is shown
607 void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
609 /// \brief Returns true if \c n is hidden.
611 /// Returns true if \c n is hidden.
612 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
614 /// \brief Returns true if \c e is hidden.
616 /// Returns true if \c e is hidden.
617 bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
619 typedef False NodeNumTag;
620 typedef False EdgeNumTag;
622 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
623 Edge findEdge(const Node& source, const Node& target,
624 const Edge& prev = INVALID) {
625 Edge edge = Parent::findEdge(source, target, prev);
626 while (edge != INVALID && !(*uedge_filter_map)[edge]) {
627 edge = Parent::findEdge(source, target, edge);
631 UEdge findUEdge(const Node& source, const Node& target,
632 const UEdge& prev = INVALID) {
633 UEdge uedge = Parent::findUEdge(source, target, prev);
634 while (uedge != INVALID && !(*uedge_filter_map)[uedge]) {
635 uedge = Parent::findUEdge(source, target, uedge);
640 template <typename _Value>
642 : public SubMapExtender<Adaptor,
643 typename Parent::template NodeMap<_Value> >
646 typedef Adaptor Graph;
647 typedef SubMapExtender<Adaptor, typename Parent::
648 template NodeMap<_Value> > Parent;
650 NodeMap(const Graph& graph)
652 NodeMap(const Graph& graph, const _Value& value)
653 : Parent(graph, value) {}
655 NodeMap& operator=(const NodeMap& cmap) {
656 return operator=<NodeMap>(cmap);
659 template <typename CMap>
660 NodeMap& operator=(const CMap& cmap) {
661 Parent::operator=(cmap);
666 template <typename _Value>
668 : public SubMapExtender<Adaptor,
669 typename Parent::template EdgeMap<_Value> >
672 typedef Adaptor Graph;
673 typedef SubMapExtender<Adaptor, typename Parent::
674 template EdgeMap<_Value> > Parent;
676 EdgeMap(const Graph& graph)
678 EdgeMap(const Graph& graph, const _Value& value)
679 : Parent(graph, value) {}
681 EdgeMap& operator=(const EdgeMap& cmap) {
682 return operator=<EdgeMap>(cmap);
685 template <typename CMap>
686 EdgeMap& operator=(const CMap& cmap) {
687 Parent::operator=(cmap);
692 template <typename _Value>
694 : public SubMapExtender<Adaptor,
695 typename Parent::template UEdgeMap<_Value> >
698 typedef Adaptor Graph;
699 typedef SubMapExtender<Adaptor, typename Parent::
700 template UEdgeMap<_Value> > Parent;
702 UEdgeMap(const Graph& graph)
704 UEdgeMap(const Graph& graph, const _Value& value)
705 : Parent(graph, value) {}
707 UEdgeMap& operator=(const UEdgeMap& cmap) {
708 return operator=<UEdgeMap>(cmap);
711 template <typename CMap>
712 UEdgeMap& operator=(const CMap& cmap) {
713 Parent::operator=(cmap);
719 /// \ingroup graph_adaptors
721 /// \brief A graph adaptor for hiding nodes and edges from an undirected
724 /// SubUGraphAdaptor shows the undirected graph with filtered node-set and
725 /// edge-set. If the \c checked parameter is true then it filters the edgeset
726 /// to do not get invalid edges without source or target.
728 /// If the \c checked template parameter is false then we have to note that
729 /// the node-iterator cares only the filter on the node-set, and the
730 /// edge-iterator cares only the filter on the edge-set.
731 /// This way the edge-map
732 /// should filter all edges which's source or target is filtered by the
735 template<typename _UGraph, typename NodeFilterMap,
736 typename UEdgeFilterMap, bool checked = true>
737 class SubUGraphAdaptor :
738 public UGraphAdaptorExtender<
739 SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, checked> > {
741 typedef _UGraph Graph;
742 typedef UGraphAdaptorExtender<
743 SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap> > Parent;
745 SubUGraphAdaptor() { }
747 SubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map,
748 UEdgeFilterMap& _uedge_filter_map) {
750 setNodeFilterMap(_node_filter_map);
751 setUEdgeFilterMap(_uedge_filter_map);
755 template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
756 SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>
757 subUGraphAdaptor(const UGraph& graph,
758 NodeFilterMap& nfm, EdgeFilterMap& efm) {
759 return SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>
763 template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
764 SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>
765 subUGraphAdaptor(const UGraph& graph,
766 NodeFilterMap& nfm, EdgeFilterMap& efm) {
767 return SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>
771 template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
772 SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>
773 subUGraphAdaptor(const UGraph& graph,
774 NodeFilterMap& nfm, EdgeFilterMap& efm) {
775 return SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>
779 template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
780 SubUGraphAdaptor<const UGraph, const NodeFilterMap, const EdgeFilterMap>
781 subUGraphAdaptor(const UGraph& graph,
782 NodeFilterMap& nfm, EdgeFilterMap& efm) {
783 return SubUGraphAdaptor<const UGraph, const NodeFilterMap,
784 const EdgeFilterMap>(graph, nfm, efm);
787 /// \ingroup graph_adaptors
789 /// \brief An adaptor for hiding nodes from an undirected graph.
791 /// An adaptor for hiding nodes from an undirected graph.
792 /// This adaptor specializes SubUGraphAdaptor in the way that only
794 /// can be filtered. In usual case the checked parameter is true, we get the
795 /// induced subgraph. But if the checked parameter is false then we can only
796 /// filter only isolated nodes.
797 template<typename _UGraph, typename NodeFilterMap, bool checked = true>
798 class NodeSubUGraphAdaptor :
799 public SubUGraphAdaptor<_UGraph, NodeFilterMap,
800 ConstMap<typename _UGraph::UEdge, bool>, checked> {
802 typedef SubUGraphAdaptor<_UGraph, NodeFilterMap,
803 ConstMap<typename _UGraph::UEdge, bool> > Parent;
804 typedef _UGraph Graph;
806 ConstMap<typename _UGraph::UEdge, bool> const_true_map;
808 NodeSubUGraphAdaptor() : const_true_map(true) {
809 Parent::setUEdgeFilterMap(const_true_map);
813 NodeSubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
814 Parent(), const_true_map(true) {
815 Parent::setGraph(_graph);
816 Parent::setNodeFilterMap(_node_filter_map);
817 Parent::setUEdgeFilterMap(const_true_map);
821 template<typename UGraph, typename NodeFilterMap>
822 NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>
823 nodeSubUGraphAdaptor(const UGraph& graph, NodeFilterMap& nfm) {
824 return NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>(graph, nfm);
827 template<typename UGraph, typename NodeFilterMap>
828 NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>
829 nodeSubUGraphAdaptor(const UGraph& graph, const NodeFilterMap& nfm) {
830 return NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>(graph, nfm);
833 /// \ingroup graph_adaptors
835 /// \brief An adaptor for hiding undirected edges from an undirected graph.
837 /// \warning Graph adaptors are in even more experimental state
838 /// than the other parts of the lib. Use them at you own risk.
840 /// An adaptor for hiding undirected edges from an undirected graph.
841 /// This adaptor specializes SubUGraphAdaptor in the way that
842 /// only the edge-set
844 template<typename _UGraph, typename UEdgeFilterMap>
845 class EdgeSubUGraphAdaptor :
846 public SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>,
847 UEdgeFilterMap, false> {
849 typedef SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>,
850 UEdgeFilterMap, false> Parent;
851 typedef _UGraph Graph;
853 ConstMap<typename Graph::Node, bool> const_true_map;
855 EdgeSubUGraphAdaptor() : const_true_map(true) {
856 Parent::setNodeFilterMap(const_true_map);
861 EdgeSubUGraphAdaptor(Graph& _graph, UEdgeFilterMap& _uedge_filter_map) :
862 Parent(), const_true_map(true) {
863 Parent::setGraph(_graph);
864 Parent::setNodeFilterMap(const_true_map);
865 Parent::setUEdgeFilterMap(_uedge_filter_map);
870 template<typename UGraph, typename EdgeFilterMap>
871 EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>
872 edgeSubUGraphAdaptor(const UGraph& graph, EdgeFilterMap& efm) {
873 return EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>(graph, efm);
876 template<typename UGraph, typename EdgeFilterMap>
877 EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>
878 edgeSubUGraphAdaptor(const UGraph& graph, const EdgeFilterMap& efm) {
879 return EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>(graph, efm);
882 /// \brief Base of direct undirected graph adaptor
884 /// Base class of the direct undirected graph adaptor. All public member
885 /// of this class can be used with the DirUGraphAdaptor too.
886 /// \sa DirUGraphAdaptor
887 template <typename _UGraph, typename _DirectionMap>
888 class DirUGraphAdaptorBase {
891 typedef _UGraph Graph;
892 typedef _DirectionMap DirectionMap;
894 typedef typename _UGraph::Node Node;
895 typedef typename _UGraph::UEdge Edge;
897 /// \brief Reverse edge
899 /// It reverse the given edge. It simply negate the direction in the map.
900 void reverseEdge(const Edge& edge) {
901 direction->set(edge, !(*direction)[edge]);
904 void first(Node& i) const { graph->first(i); }
905 void first(Edge& i) const { graph->first(i); }
906 void firstIn(Edge& i, const Node& n) const {
908 graph->firstInc(i, d, n);
909 while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
911 void firstOut(Edge& i, const Node& n ) const {
913 graph->firstInc(i, d, n);
914 while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
917 void next(Node& i) const { graph->next(i); }
918 void next(Edge& i) const { graph->next(i); }
919 void nextIn(Edge& i) const {
920 bool d = !(*direction)[i];
921 graph->nextInc(i, d);
922 while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
924 void nextOut(Edge& i) const {
925 bool d = (*direction)[i];
926 graph->nextInc(i, d);
927 while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
930 Node source(const Edge& e) const {
931 return (*direction)[e] ? graph->source(e) : graph->target(e);
933 Node target(const Edge& e) const {
934 return (*direction)[e] ? graph->target(e) : graph->source(e);
937 typedef NodeNumTagIndicator<Graph> NodeNumTag;
938 int nodeNum() const { return graph->nodeNum(); }
940 typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
941 int edgeNum() const { return graph->uEdgeNum(); }
943 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
944 Edge findEdge(const Node& source, const Node& target,
945 const Edge& prev = INVALID) {
947 bool d = edge == INVALID ? true : (*direction)[edge];
949 edge = graph->findUEdge(source, target, edge);
950 while (edge != INVALID && !(*direction)[edge]) {
951 graph->findUEdge(source, target, edge);
953 if (edge != INVALID) return edge;
955 graph->findUEdge(target, source, edge);
956 while (edge != INVALID && (*direction)[edge]) {
957 graph->findUEdge(source, target, edge);
962 Node addNode() const {
963 return Node(graph->addNode());
966 Edge addEdge(const Node& source, const Node& target) const {
967 Edge edge = graph->addEdge(source, target);
968 direction->set(edge, graph->source(edge) == source);
972 void erase(const Node& i) const { graph->erase(i); }
973 void erase(const Edge& i) const { graph->erase(i); }
975 void clear() const { graph->clear(); }
977 int id(const Node& v) const { return graph->id(v); }
978 int id(const Edge& e) const { return graph->id(e); }
980 int maxNodeId() const {
981 return graph->maxNodeId();
984 int maxEdgeId() const {
985 return graph->maxEdgeId();
988 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
990 NodeNotifier& getNotifier(Node) const {
991 return graph->getNotifier(Node());
994 typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
996 EdgeNotifier& getNotifier(Edge) const {
997 return graph->getNotifier(Edge());
1000 template <typename _Value>
1001 class NodeMap : public _UGraph::template NodeMap<_Value> {
1004 typedef typename _UGraph::template NodeMap<_Value> Parent;
1006 explicit NodeMap(const DirUGraphAdaptorBase& ga)
1007 : Parent(*ga.graph) {}
1009 NodeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
1010 : Parent(*ga.graph, value) {}
1012 NodeMap& operator=(const NodeMap& cmap) {
1013 return operator=<NodeMap>(cmap);
1016 template <typename CMap>
1017 NodeMap& operator=(const CMap& cmap) {
1018 Parent::operator=(cmap);
1024 template <typename _Value>
1025 class EdgeMap : public _UGraph::template UEdgeMap<_Value> {
1028 typedef typename _UGraph::template UEdgeMap<_Value> Parent;
1030 explicit EdgeMap(const DirUGraphAdaptorBase& ga)
1031 : Parent(*ga.graph) { }
1033 EdgeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
1034 : Parent(*ga.graph, value) { }
1036 EdgeMap& operator=(const EdgeMap& cmap) {
1037 return operator=<EdgeMap>(cmap);
1040 template <typename CMap>
1041 EdgeMap& operator=(const CMap& cmap) {
1042 Parent::operator=(cmap);
1051 DirectionMap* direction;
1053 void setDirectionMap(DirectionMap& _direction) {
1054 direction = &_direction;
1057 void setGraph(Graph& _graph) {
1064 /// \ingroup graph_adaptors
1066 /// \brief A directed graph is made from an undirected graph by an adaptor
1068 /// This adaptor gives a direction for each uedge in the undirected
1069 /// graph. The direction of the edges stored in the
1070 /// DirectionMap. This map is a bool map on the undirected edges. If
1071 /// the uedge is mapped to true then the direction of the directed
1072 /// edge will be the same as the default direction of the uedge. The
1073 /// edges can be easily reverted by the \ref
1074 /// DirUGraphAdaptorBase::reverseEdge "reverseEdge()" member in the
1077 /// It can be used to solve orientation problems on directed graphs.
1078 /// By example how can we orient an undirected graph to get the minimum
1079 /// number of strongly connected components. If we orient the edges with
1080 /// the dfs algorithm out from the source then we will get such an
1083 /// We use the \ref DfsVisitor "visitor" interface of the
1084 /// \ref DfsVisit "dfs" algorithm:
1086 /// template <typename DirMap>
1087 /// class OrientVisitor : public DfsVisitor<UGraph> {
1090 /// OrientVisitor(const UGraph& ugraph, DirMap& dirMap)
1091 /// : _ugraph(ugraph), _dirMap(dirMap), _processed(ugraph, false) {}
1093 /// void discover(const Edge& edge) {
1094 /// _processed.set(edge, true);
1095 /// _dirMap.set(edge, _ugraph.direction(edge));
1098 /// void examine(const Edge& edge) {
1099 /// if (_processed[edge]) return;
1100 /// _processed.set(edge, true);
1101 /// _dirMap.set(edge, _ugraph.direction(edge));
1105 /// const UGraph& _ugraph;
1106 /// DirMap& _dirMap;
1107 /// UGraph::UEdgeMap<bool> _processed;
1111 /// And now we can use the orientation:
1113 /// UGraph::UEdgeMap<bool> dmap(ugraph);
1115 /// typedef OrientVisitor<UGraph::UEdgeMap<bool> > Visitor;
1116 /// Visitor visitor(ugraph, dmap);
1118 /// DfsVisit<UGraph, Visitor> dfs(ugraph, visitor);
1122 /// typedef DirUGraphAdaptor<UGraph> DGraph;
1123 /// DGraph dgraph(ugraph, dmap);
1125 /// LEMON_ASSERT(countStronglyConnectedComponents(dgraph) ==
1126 /// countBiEdgeConnectedComponents(ugraph), "Wrong Orientation");
1129 /// The number of the bi-connected components is a lower bound for
1130 /// the number of the strongly connected components in the directed
1131 /// graph because if we contract the bi-connected components to
1132 /// nodes we will get a tree therefore we cannot orient edges in
1133 /// both direction between bi-connected components. In the other way
1134 /// the algorithm will orient one component to be strongly
1135 /// connected. The two relations proof that the assertion will
1136 /// be always true and the found solution is optimal.
1138 /// \sa DirUGraphAdaptorBase
1139 /// \sa dirUGraphAdaptor
1140 template<typename _Graph,
1141 typename DirectionMap = typename _Graph::template UEdgeMap<bool> >
1142 class DirUGraphAdaptor :
1143 public GraphAdaptorExtender<
1144 DirUGraphAdaptorBase<_Graph, DirectionMap> > {
1146 typedef _Graph Graph;
1147 typedef GraphAdaptorExtender<
1148 DirUGraphAdaptorBase<_Graph, DirectionMap> > Parent;
1150 DirUGraphAdaptor() { }
1153 /// \brief Constructor of the adaptor
1155 /// Constructor of the adaptor
1156 DirUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) {
1158 setDirectionMap(_direction_map);
1162 /// \brief Just gives back a DirUGraphAdaptor
1164 /// Just gives back a DirUGraphAdaptor
1165 template<typename UGraph, typename DirectionMap>
1166 DirUGraphAdaptor<const UGraph, DirectionMap>
1167 dirUGraphAdaptor(const UGraph& graph, DirectionMap& dm) {
1168 return DirUGraphAdaptor<const UGraph, DirectionMap>(graph, dm);
1171 template<typename UGraph, typename DirectionMap>
1172 DirUGraphAdaptor<const UGraph, const DirectionMap>
1173 dirUGraphAdaptor(const UGraph& graph, const DirectionMap& dm) {
1174 return DirUGraphAdaptor<const UGraph, const DirectionMap>(graph, dm);