Redesigned CapacityScaling algorithm with almost the same interface.
The new version does not use the ResidualGraphAdaptor for performance reasons.
Scaling can be enabled and disabled with a parameter of the run() function.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
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& u, const Node& v,
103 const Edge& prev = INVALID) {
104 return graph->findEdge(u, v, prev);
106 UEdge findUEdge(const Node& u, const Node& v,
107 const UEdge& prev = INVALID) {
108 return graph->findUEdge(u, v, prev);
111 Node addNode() const { return graph->addNode(); }
112 UEdge addEdge(const Node& u, const Node& v) const {
113 return graph->addEdge(u, v);
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 ix) const {
129 return graph->fromNodeId(ix);
132 Edge fromEdgeId(int ix) const {
133 return graph->fromEdgeId(ix);
136 UEdge fromUEdgeId(int ix) const {
137 return graph->fromUEdgeId(ix);
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& notifier(Node) const {
155 return graph->notifier(Node());
158 typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
160 EdgeNotifier& notifier(Edge) const {
161 return graph->notifier(Edge());
164 typedef typename ItemSetTraits<Graph, UEdge>::ItemNotifier UEdgeNotifier;
166 UEdgeNotifier& notifier(UEdge) const {
167 return graph->notifier(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::source(i)]
315 || !(*node_filter_map)[Parent::target(i)])) Parent::nextInc(i, d);
318 void next(Node& i) const {
320 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
323 void next(Edge& i) const {
325 while (i!=INVALID && (!(*uedge_filter_map)[i]
326 || !(*node_filter_map)[Parent::source(i)]
327 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
330 void next(UEdge& i) const {
332 while (i!=INVALID && (!(*uedge_filter_map)[i]
333 || !(*node_filter_map)[Parent::source(i)]
334 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
337 void nextIn(Edge& i) const {
339 while (i!=INVALID && (!(*uedge_filter_map)[i]
340 || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
343 void nextOut(Edge& i) const {
345 while (i!=INVALID && (!(*uedge_filter_map)[i]
346 || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
349 void nextInc(UEdge& i, bool& d) const {
350 Parent::nextInc(i, d);
351 while (i!=INVALID && (!(*uedge_filter_map)[i]
352 || !(*node_filter_map)[Parent::source(i)]
353 || !(*node_filter_map)[Parent::target(i)])) Parent::nextInc(i, d);
356 /// \brief Hide the given node in the graph.
358 /// This function hides \c n in the graph, i.e. the iteration
359 /// jumps over it. This is done by simply setting the value of \c n
360 /// to be false in the corresponding node-map.
361 void hide(const Node& n) const { node_filter_map->set(n, false); }
363 /// \brief Hide the given undirected edge in the graph.
365 /// This function hides \c e in the graph, i.e. the iteration
366 /// jumps over it. This is done by simply setting the value of \c e
367 /// to be false in the corresponding uedge-map.
368 void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
370 /// \brief Unhide the given node in the graph.
372 /// The value of \c n is set to be true in the node-map which stores
373 /// hide information. If \c n was hidden previuosly, then it is shown
375 void unHide(const Node& n) const { node_filter_map->set(n, true); }
377 /// \brief Hide the given undirected edge in the graph.
379 /// The value of \c e is set to be true in the uedge-map which stores
380 /// hide information. If \c e was hidden previuosly, then it is shown
382 void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
384 /// \brief Returns true if \c n is hidden.
386 /// Returns true if \c n is hidden.
387 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
389 /// \brief Returns true if \c e is hidden.
391 /// Returns true if \c e is hidden.
392 bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
394 typedef False NodeNumTag;
395 typedef False EdgeNumTag;
397 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
398 Edge findEdge(const Node& u, const Node& v,
399 const Edge& prev = INVALID) {
400 if (!(*node_filter_map)[u] || !(*node_filter_map)[v]) {
403 Edge edge = Parent::findEdge(u, v, prev);
404 while (edge != INVALID && !(*uedge_filter_map)[edge]) {
405 edge = Parent::findEdge(u, v, edge);
409 UEdge findUEdge(const Node& u, const Node& v,
410 const UEdge& prev = INVALID) {
411 if (!(*node_filter_map)[u] || !(*node_filter_map)[v]) {
414 UEdge uedge = Parent::findUEdge(u, v, prev);
415 while (uedge != INVALID && !(*uedge_filter_map)[uedge]) {
416 uedge = Parent::findUEdge(u, v, uedge);
421 template <typename _Value>
423 : public SubMapExtender<Adaptor,
424 typename Parent::template NodeMap<_Value> >
427 typedef Adaptor Graph;
428 typedef SubMapExtender<Adaptor, typename Parent::
429 template NodeMap<_Value> > Parent;
431 NodeMap(const Graph& g)
433 NodeMap(const Graph& g, const _Value& v)
436 NodeMap& operator=(const NodeMap& cmap) {
437 return operator=<NodeMap>(cmap);
440 template <typename CMap>
441 NodeMap& operator=(const CMap& cmap) {
442 Parent::operator=(cmap);
447 template <typename _Value>
449 : public SubMapExtender<Adaptor,
450 typename Parent::template EdgeMap<_Value> >
453 typedef Adaptor Graph;
454 typedef SubMapExtender<Adaptor, typename Parent::
455 template EdgeMap<_Value> > Parent;
457 EdgeMap(const Graph& g)
459 EdgeMap(const Graph& g, const _Value& v)
462 EdgeMap& operator=(const EdgeMap& cmap) {
463 return operator=<EdgeMap>(cmap);
466 template <typename CMap>
467 EdgeMap& operator=(const CMap& cmap) {
468 Parent::operator=(cmap);
473 template <typename _Value>
475 : public SubMapExtender<Adaptor,
476 typename Parent::template UEdgeMap<_Value> >
479 typedef Adaptor Graph;
480 typedef SubMapExtender<Adaptor, typename Parent::
481 template UEdgeMap<_Value> > Parent;
483 UEdgeMap(const Graph& g)
485 UEdgeMap(const Graph& g, const _Value& v)
488 UEdgeMap& operator=(const UEdgeMap& cmap) {
489 return operator=<UEdgeMap>(cmap);
492 template <typename CMap>
493 UEdgeMap& operator=(const CMap& cmap) {
494 Parent::operator=(cmap);
501 template <typename _UGraph, typename NodeFilterMap, typename UEdgeFilterMap>
502 class SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, false>
503 : public UGraphAdaptorBase<_UGraph> {
505 typedef _UGraph Graph;
506 typedef SubUGraphAdaptorBase Adaptor;
507 typedef UGraphAdaptorBase<_UGraph> Parent;
509 NodeFilterMap* node_filter_map;
510 UEdgeFilterMap* uedge_filter_map;
511 SubUGraphAdaptorBase() : Parent(),
512 node_filter_map(0), uedge_filter_map(0) { }
514 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
515 node_filter_map=&_node_filter_map;
517 void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {
518 uedge_filter_map=&_uedge_filter_map;
523 typedef typename Parent::Node Node;
524 typedef typename Parent::Edge Edge;
525 typedef typename Parent::UEdge UEdge;
527 void first(Node& i) const {
529 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
532 void first(Edge& i) const {
534 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
537 void first(UEdge& i) const {
539 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
542 void firstIn(Edge& i, const Node& n) const {
543 Parent::firstIn(i, n);
544 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextIn(i);
547 void firstOut(Edge& i, const Node& n) const {
548 Parent::firstOut(i, n);
549 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextOut(i);
552 void firstInc(UEdge& i, bool& d, const Node& n) const {
553 Parent::firstInc(i, d, n);
554 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d);
557 void next(Node& i) const {
559 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
561 void next(Edge& i) const {
563 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
565 void next(UEdge& i) const {
567 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
569 void nextIn(Edge& i) const {
571 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextIn(i);
574 void nextOut(Edge& i) const {
576 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextOut(i);
578 void nextInc(UEdge& i, bool& d) const {
579 Parent::nextInc(i, d);
580 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d);
583 /// \brief Hide the given node in the graph.
585 /// This function hides \c n in the graph, i.e. the iteration
586 /// jumps over it. This is done by simply setting the value of \c n
587 /// to be false in the corresponding node-map.
588 void hide(const Node& n) const { node_filter_map->set(n, false); }
590 /// \brief Hide the given undirected edge in the graph.
592 /// This function hides \c e in the graph, i.e. the iteration
593 /// jumps over it. This is done by simply setting the value of \c e
594 /// to be false in the corresponding uedge-map.
595 void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
597 /// \brief Unhide the given node in the graph.
599 /// The value of \c n is set to be true in the node-map which stores
600 /// hide information. If \c n was hidden previuosly, then it is shown
602 void unHide(const Node& n) const { node_filter_map->set(n, true); }
604 /// \brief Hide the given undirected edge in the graph.
606 /// The value of \c e is set to be true in the uedge-map which stores
607 /// hide information. If \c e was hidden previuosly, then it is shown
609 void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
611 /// \brief Returns true if \c n is hidden.
613 /// Returns true if \c n is hidden.
614 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
616 /// \brief Returns true if \c e is hidden.
618 /// Returns true if \c e is hidden.
619 bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
621 typedef False NodeNumTag;
622 typedef False EdgeNumTag;
624 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
625 Edge findEdge(const Node& u, const Node& v,
626 const Edge& prev = INVALID) {
627 Edge edge = Parent::findEdge(u, v, prev);
628 while (edge != INVALID && !(*uedge_filter_map)[edge]) {
629 edge = Parent::findEdge(u, v, edge);
633 UEdge findUEdge(const Node& u, const Node& v,
634 const UEdge& prev = INVALID) {
635 UEdge uedge = Parent::findUEdge(u, v, prev);
636 while (uedge != INVALID && !(*uedge_filter_map)[uedge]) {
637 uedge = Parent::findUEdge(u, v, uedge);
642 template <typename _Value>
644 : public SubMapExtender<Adaptor,
645 typename Parent::template NodeMap<_Value> >
648 typedef Adaptor Graph;
649 typedef SubMapExtender<Adaptor, typename Parent::
650 template NodeMap<_Value> > Parent;
652 NodeMap(const Graph& g)
654 NodeMap(const Graph& g, const _Value& v)
657 NodeMap& operator=(const NodeMap& cmap) {
658 return operator=<NodeMap>(cmap);
661 template <typename CMap>
662 NodeMap& operator=(const CMap& cmap) {
663 Parent::operator=(cmap);
668 template <typename _Value>
670 : public SubMapExtender<Adaptor,
671 typename Parent::template EdgeMap<_Value> >
674 typedef Adaptor Graph;
675 typedef SubMapExtender<Adaptor, typename Parent::
676 template EdgeMap<_Value> > Parent;
678 EdgeMap(const Graph& g)
680 EdgeMap(const Graph& g, const _Value& v)
683 EdgeMap& operator=(const EdgeMap& cmap) {
684 return operator=<EdgeMap>(cmap);
687 template <typename CMap>
688 EdgeMap& operator=(const CMap& cmap) {
689 Parent::operator=(cmap);
694 template <typename _Value>
696 : public SubMapExtender<Adaptor,
697 typename Parent::template UEdgeMap<_Value> >
700 typedef Adaptor Graph;
701 typedef SubMapExtender<Adaptor, typename Parent::
702 template UEdgeMap<_Value> > Parent;
704 UEdgeMap(const Graph& g)
706 UEdgeMap(const Graph& g, const _Value& v)
709 UEdgeMap& operator=(const UEdgeMap& cmap) {
710 return operator=<UEdgeMap>(cmap);
713 template <typename CMap>
714 UEdgeMap& operator=(const CMap& cmap) {
715 Parent::operator=(cmap);
721 /// \ingroup graph_adaptors
723 /// \brief A graph adaptor for hiding nodes and edges from an undirected
726 /// SubUGraphAdaptor shows the undirected graph with filtered node-set and
727 /// edge-set. If the \c checked parameter is true then it filters the edgeset
728 /// to do not get invalid edges without source or target.
730 /// If the \c checked template parameter is false then we have to note that
731 /// the node-iterator cares only the filter on the node-set, and the
732 /// edge-iterator cares only the filter on the edge-set.
733 /// This way the edge-map
734 /// should filter all edges which's source or target is filtered by the
737 template<typename _UGraph, typename NodeFilterMap,
738 typename UEdgeFilterMap, bool checked = true>
739 class SubUGraphAdaptor :
740 public UGraphAdaptorExtender<
741 SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, checked> > {
743 typedef _UGraph Graph;
744 typedef UGraphAdaptorExtender<
745 SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap> > Parent;
747 SubUGraphAdaptor() { }
749 SubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map,
750 UEdgeFilterMap& _uedge_filter_map) {
752 setNodeFilterMap(_node_filter_map);
753 setUEdgeFilterMap(_uedge_filter_map);
757 template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
758 SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>
759 subUGraphAdaptor(const UGraph& graph,
760 NodeFilterMap& nfm, EdgeFilterMap& efm) {
761 return SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>
765 template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
766 SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>
767 subUGraphAdaptor(const UGraph& graph,
768 NodeFilterMap& nfm, EdgeFilterMap& efm) {
769 return SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>
773 template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
774 SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>
775 subUGraphAdaptor(const UGraph& graph,
776 NodeFilterMap& nfm, EdgeFilterMap& efm) {
777 return SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>
781 template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
782 SubUGraphAdaptor<const UGraph, const NodeFilterMap, const EdgeFilterMap>
783 subUGraphAdaptor(const UGraph& graph,
784 NodeFilterMap& nfm, EdgeFilterMap& efm) {
785 return SubUGraphAdaptor<const UGraph, const NodeFilterMap,
786 const EdgeFilterMap>(graph, nfm, efm);
789 /// \ingroup graph_adaptors
791 /// \brief An adaptor for hiding nodes from an undirected graph.
793 /// An adaptor for hiding nodes from an undirected graph. This
794 /// adaptor specializes SubUGraphAdaptor in the way that only the
795 /// node-set can be filtered. In usual case the checked parameter is
796 /// true, we get the induced subgraph. But if the checked parameter
797 /// is false then we can filter only isolated nodes.
798 template<typename _UGraph, typename NodeFilterMap, bool checked = true>
799 class NodeSubUGraphAdaptor :
800 public SubUGraphAdaptor<_UGraph, NodeFilterMap,
801 ConstMap<typename _UGraph::UEdge, bool>, checked> {
803 typedef SubUGraphAdaptor<_UGraph, NodeFilterMap,
804 ConstMap<typename _UGraph::UEdge, bool> > Parent;
805 typedef _UGraph Graph;
807 ConstMap<typename _UGraph::UEdge, bool> const_true_map;
809 NodeSubUGraphAdaptor() : const_true_map(true) {
810 Parent::setUEdgeFilterMap(const_true_map);
814 NodeSubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
815 Parent(), const_true_map(true) {
816 Parent::setGraph(_graph);
817 Parent::setNodeFilterMap(_node_filter_map);
818 Parent::setUEdgeFilterMap(const_true_map);
822 template<typename UGraph, typename NodeFilterMap>
823 NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>
824 nodeSubUGraphAdaptor(const UGraph& graph, NodeFilterMap& nfm) {
825 return NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>(graph, nfm);
828 template<typename UGraph, typename NodeFilterMap>
829 NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>
830 nodeSubUGraphAdaptor(const UGraph& graph, const NodeFilterMap& nfm) {
831 return NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>(graph, nfm);
834 /// \ingroup graph_adaptors
836 /// \brief An adaptor for hiding undirected edges from an undirected graph.
838 /// \warning Graph adaptors are in even more experimental state
839 /// than the other parts of the lib. Use them at you own risk.
841 /// An adaptor for hiding undirected edges from an undirected graph.
842 /// This adaptor specializes SubUGraphAdaptor in the way that
843 /// only the edge-set
845 template<typename _UGraph, typename UEdgeFilterMap>
846 class EdgeSubUGraphAdaptor :
847 public SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>,
848 UEdgeFilterMap, false> {
850 typedef SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>,
851 UEdgeFilterMap, false> Parent;
852 typedef _UGraph Graph;
854 ConstMap<typename Graph::Node, bool> const_true_map;
856 EdgeSubUGraphAdaptor() : const_true_map(true) {
857 Parent::setNodeFilterMap(const_true_map);
862 EdgeSubUGraphAdaptor(Graph& _graph, UEdgeFilterMap& _uedge_filter_map) :
863 Parent(), const_true_map(true) {
864 Parent::setGraph(_graph);
865 Parent::setNodeFilterMap(const_true_map);
866 Parent::setUEdgeFilterMap(_uedge_filter_map);
871 template<typename UGraph, typename EdgeFilterMap>
872 EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>
873 edgeSubUGraphAdaptor(const UGraph& graph, EdgeFilterMap& efm) {
874 return EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>(graph, efm);
877 template<typename UGraph, typename EdgeFilterMap>
878 EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>
879 edgeSubUGraphAdaptor(const UGraph& graph, const EdgeFilterMap& efm) {
880 return EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>(graph, efm);
883 /// \brief Base of direct undirected graph adaptor
885 /// Base class of the direct undirected graph adaptor. All public member
886 /// of this class can be used with the DirUGraphAdaptor too.
887 /// \sa DirUGraphAdaptor
888 template <typename _UGraph, typename _DirectionMap>
889 class DirUGraphAdaptorBase {
892 typedef _UGraph Graph;
893 typedef _DirectionMap DirectionMap;
895 typedef typename _UGraph::Node Node;
896 typedef typename _UGraph::UEdge Edge;
898 /// \brief Reverse edge
900 /// It reverse the given edge. It simply negate the direction in the map.
901 void reverseEdge(const Edge& edge) {
902 direction->set(edge, !(*direction)[edge]);
905 void first(Node& i) const { graph->first(i); }
906 void first(Edge& i) const { graph->first(i); }
907 void firstIn(Edge& i, const Node& n) const {
909 graph->firstInc(i, d, n);
910 while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
912 void firstOut(Edge& i, const Node& n ) const {
914 graph->firstInc(i, d, n);
915 while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
918 void next(Node& i) const { graph->next(i); }
919 void next(Edge& i) const { graph->next(i); }
920 void nextIn(Edge& i) const {
921 bool d = !(*direction)[i];
922 graph->nextInc(i, d);
923 while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
925 void nextOut(Edge& i) const {
926 bool d = (*direction)[i];
927 graph->nextInc(i, d);
928 while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
931 Node source(const Edge& e) const {
932 return (*direction)[e] ? graph->source(e) : graph->target(e);
934 Node target(const Edge& e) const {
935 return (*direction)[e] ? graph->target(e) : graph->source(e);
938 typedef NodeNumTagIndicator<Graph> NodeNumTag;
939 int nodeNum() const { return graph->nodeNum(); }
941 typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
942 int edgeNum() const { return graph->uEdgeNum(); }
944 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
945 Edge findEdge(const Node& u, const Node& v,
946 const Edge& prev = INVALID) {
948 bool d = edge == INVALID ? true : (*direction)[edge];
950 edge = graph->findUEdge(u, v, edge);
951 while (edge != INVALID && !(*direction)[edge]) {
952 graph->findUEdge(u, v, edge);
954 if (edge != INVALID) return edge;
956 graph->findUEdge(v, u, edge);
957 while (edge != INVALID && (*direction)[edge]) {
958 graph->findUEdge(u, v, edge);
963 Node addNode() const {
964 return Node(graph->addNode());
967 Edge addEdge(const Node& u, const Node& v) const {
968 Edge edge = graph->addEdge(u, v);
969 direction->set(edge, graph->source(edge) == u);
973 void erase(const Node& i) const { graph->erase(i); }
974 void erase(const Edge& i) const { graph->erase(i); }
976 void clear() const { graph->clear(); }
978 int id(const Node& v) const { return graph->id(v); }
979 int id(const Edge& e) const { return graph->id(e); }
981 int maxNodeId() const {
982 return graph->maxNodeId();
985 int maxEdgeId() const {
986 return graph->maxEdgeId();
989 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
991 NodeNotifier& notifier(Node) const {
992 return graph->notifier(Node());
995 typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
997 EdgeNotifier& notifier(Edge) const {
998 return graph->notifier(Edge());
1001 template <typename _Value>
1002 class NodeMap : public _UGraph::template NodeMap<_Value> {
1005 typedef typename _UGraph::template NodeMap<_Value> Parent;
1007 explicit NodeMap(const DirUGraphAdaptorBase& ga)
1008 : Parent(*ga.graph) {}
1010 NodeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
1011 : Parent(*ga.graph, value) {}
1013 NodeMap& operator=(const NodeMap& cmap) {
1014 return operator=<NodeMap>(cmap);
1017 template <typename CMap>
1018 NodeMap& operator=(const CMap& cmap) {
1019 Parent::operator=(cmap);
1025 template <typename _Value>
1026 class EdgeMap : public _UGraph::template UEdgeMap<_Value> {
1029 typedef typename _UGraph::template UEdgeMap<_Value> Parent;
1031 explicit EdgeMap(const DirUGraphAdaptorBase& ga)
1032 : Parent(*ga.graph) { }
1034 EdgeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
1035 : Parent(*ga.graph, value) { }
1037 EdgeMap& operator=(const EdgeMap& cmap) {
1038 return operator=<EdgeMap>(cmap);
1041 template <typename CMap>
1042 EdgeMap& operator=(const CMap& cmap) {
1043 Parent::operator=(cmap);
1052 DirectionMap* direction;
1054 void setDirectionMap(DirectionMap& _direction) {
1055 direction = &_direction;
1058 void setGraph(Graph& _graph) {
1065 /// \ingroup graph_adaptors
1067 /// \brief A directed graph is made from an undirected graph by an adaptor
1069 /// This adaptor gives a direction for each uedge in the undirected
1070 /// graph. The direction of the edges stored in the
1071 /// DirectionMap. This map is a bool map on the undirected edges. If
1072 /// the uedge is mapped to true then the direction of the directed
1073 /// edge will be the same as the default direction of the uedge. The
1074 /// edges can be easily reverted by the \ref
1075 /// DirUGraphAdaptorBase::reverseEdge "reverseEdge()" member in the
1078 /// It can be used to solve orientation problems on directed graphs.
1079 /// By example how can we orient an undirected graph to get the minimum
1080 /// number of strongly connected components. If we orient the edges with
1081 /// the dfs algorithm out from the source then we will get such an
1084 /// We use the \ref DfsVisitor "visitor" interface of the
1085 /// \ref DfsVisit "dfs" algorithm:
1087 /// template <typename DirMap>
1088 /// class OrientVisitor : public DfsVisitor<UGraph> {
1091 /// OrientVisitor(const UGraph& ugraph, DirMap& dirMap)
1092 /// : _ugraph(ugraph), _dirMap(dirMap), _processed(ugraph, false) {}
1094 /// void discover(const Edge& edge) {
1095 /// _processed.set(edge, true);
1096 /// _dirMap.set(edge, _ugraph.direction(edge));
1099 /// void examine(const Edge& edge) {
1100 /// if (_processed[edge]) return;
1101 /// _processed.set(edge, true);
1102 /// _dirMap.set(edge, _ugraph.direction(edge));
1106 /// const UGraph& _ugraph;
1107 /// DirMap& _dirMap;
1108 /// UGraph::UEdgeMap<bool> _processed;
1112 /// And now we can use the orientation:
1114 /// UGraph::UEdgeMap<bool> dmap(ugraph);
1116 /// typedef OrientVisitor<UGraph::UEdgeMap<bool> > Visitor;
1117 /// Visitor visitor(ugraph, dmap);
1119 /// DfsVisit<UGraph, Visitor> dfs(ugraph, visitor);
1123 /// typedef DirUGraphAdaptor<UGraph> DGraph;
1124 /// DGraph dgraph(ugraph, dmap);
1126 /// LEMON_ASSERT(countStronglyConnectedComponents(dgraph) ==
1127 /// countBiEdgeConnectedComponents(ugraph), "Wrong Orientation");
1130 /// The number of the bi-connected components is a lower bound for
1131 /// the number of the strongly connected components in the directed
1132 /// graph because if we contract the bi-connected components to
1133 /// nodes we will get a tree therefore we cannot orient edges in
1134 /// both direction between bi-connected components. In the other way
1135 /// the algorithm will orient one component to be strongly
1136 /// connected. The two relations proof that the assertion will
1137 /// be always true and the found solution is optimal.
1139 /// \sa DirUGraphAdaptorBase
1140 /// \sa dirUGraphAdaptor
1141 template<typename _Graph,
1142 typename DirectionMap = typename _Graph::template UEdgeMap<bool> >
1143 class DirUGraphAdaptor :
1144 public GraphAdaptorExtender<
1145 DirUGraphAdaptorBase<_Graph, DirectionMap> > {
1147 typedef _Graph Graph;
1148 typedef GraphAdaptorExtender<
1149 DirUGraphAdaptorBase<_Graph, DirectionMap> > Parent;
1151 DirUGraphAdaptor() { }
1154 /// \brief Constructor of the adaptor
1156 /// Constructor of the adaptor
1157 DirUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) {
1159 setDirectionMap(_direction_map);
1163 /// \brief Just gives back a DirUGraphAdaptor
1165 /// Just gives back a DirUGraphAdaptor
1166 template<typename UGraph, typename DirectionMap>
1167 DirUGraphAdaptor<const UGraph, DirectionMap>
1168 dirUGraphAdaptor(const UGraph& graph, DirectionMap& dm) {
1169 return DirUGraphAdaptor<const UGraph, DirectionMap>(graph, dm);
1172 template<typename UGraph, typename DirectionMap>
1173 DirUGraphAdaptor<const UGraph, const DirectionMap>
1174 dirUGraphAdaptor(const UGraph& graph, const DirectionMap& dm) {
1175 return DirUGraphAdaptor<const UGraph, const DirectionMap>(graph, dm);