Unionfind changes induced some bugs here. Also some augmentations made.
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 /// \ingroup graph_adaptors
43 /// \brief Base type for the Graph Adaptors
45 /// This is the base type for most of LEMON graph adaptors.
46 /// This class implements a trivial graph adaptor i.e. it only wraps the
47 /// functions and types of the graph. The purpose of this class is to
48 /// make easier implementing graph adaptors. E.g. if an adaptor is
49 /// considered which differs from the wrapped graph only in some of its
50 /// functions or types, then it can be derived from GraphAdaptor, and only
51 /// the differences should be implemented.
53 /// \author Balazs Dezso
54 template<typename _UGraph>
55 class UGraphAdaptorBase {
57 typedef _UGraph Graph;
58 typedef Graph ParentGraph;
63 UGraphAdaptorBase() : graph(0) {}
65 void setGraph(Graph& _graph) { graph=&_graph; }
67 Graph& getGraph() { return *graph; }
68 const Graph& getGraph() const { return *graph; }
71 UGraphAdaptorBase(Graph& _graph) : graph(&_graph) {}
73 typedef typename Graph::Node Node;
74 typedef typename Graph::Edge Edge;
75 typedef typename Graph::UEdge UEdge;
77 void first(Node& i) const { graph->first(i); }
78 void first(Edge& i) const { graph->first(i); }
79 void first(UEdge& i) const { graph->first(i); }
80 void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
81 void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
82 void firstInc(UEdge &i, bool &d, const Node &n) const {
83 graph->firstInc(i, d, n);
86 void next(Node& i) const { graph->next(i); }
87 void next(Edge& i) const { graph->next(i); }
88 void next(UEdge& i) const { graph->next(i); }
89 void nextIn(Edge& i) const { graph->nextIn(i); }
90 void nextOut(Edge& i) const { graph->nextOut(i); }
91 void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); }
93 Node source(const UEdge& e) const { return graph->source(e); }
94 Node target(const UEdge& e) const { return graph->target(e); }
96 Node source(const Edge& e) const { return graph->source(e); }
97 Node target(const Edge& e) const { return graph->target(e); }
99 typedef NodeNumTagIndicator<Graph> NodeNumTag;
100 int nodeNum() const { return graph->nodeNum(); }
102 typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
103 int edgeNum() const { return graph->edgeNum(); }
105 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
106 Edge findEdge(const Node& source, const Node& target,
107 const Edge& prev = INVALID) {
108 return graph->findEdge(source, target, prev);
110 UEdge findUEdge(const Node& source, const Node& target,
111 const UEdge& prev = INVALID) {
112 return graph->findUEdge(source, target, prev);
115 Node addNode() const { return graph->addNode(); }
116 UEdge addEdge(const Node& source, const Node& target) const {
117 return graph->addEdge(source, target);
120 void erase(const Node& i) const { graph->erase(i); }
121 void erase(const Edge& i) const { graph->erase(i); }
123 void clear() const { graph->clear(); }
125 int id(const Node& v) const { return graph->id(v); }
126 int id(const UEdge& e) const { return graph->id(e); }
128 bool direction(const Edge& e) const { return graph->direction(e); }
129 Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); }
131 int maxNodeId() const {
132 return graph->maxNodeId();
135 int maxEdgeId() const {
136 return graph->maxEdgeId();
139 int maxUEdgeId() const {
140 return graph->maxEdgeId();
143 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
145 NodeNotifier& getNotifier(Node) const {
146 return graph->getNotifier(Node());
149 typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
151 EdgeNotifier& getNotifier(Edge) const {
152 return graph->getNotifier(Edge());
155 typedef typename ItemSetTraits<Graph, UEdge>::ItemNotifier UEdgeNotifier;
157 UEdgeNotifier& getNotifier(UEdge) const {
158 return graph->getNotifier(UEdge());
161 template <typename _Value>
162 class NodeMap : public Graph::template NodeMap<_Value> {
164 typedef typename Graph::template NodeMap<_Value> Parent;
165 explicit NodeMap(const UGraphAdaptorBase<Graph>& ga)
166 : Parent(*ga.graph) {}
167 NodeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
168 : Parent(*ga.graph, value) {}
170 NodeMap& operator=(const NodeMap& cmap) {
171 return operator=<NodeMap>(cmap);
174 template <typename CMap>
175 NodeMap& operator=(const CMap& cmap) {
176 checkConcept<concept::ReadMap<Node, _Value>, CMap>();
177 const typename Parent::Graph* graph = Parent::getGraph();
179 for (graph->first(it); it != INVALID; graph->next(it)) {
180 Parent::set(it, cmap[it]);
186 template <typename _Value>
187 class EdgeMap : public Graph::template EdgeMap<_Value> {
189 typedef typename Graph::template EdgeMap<_Value> Parent;
190 explicit EdgeMap(const UGraphAdaptorBase<Graph>& ga)
191 : Parent(*ga.graph) {}
192 EdgeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
193 : Parent(*ga.graph, value) {}
195 EdgeMap& operator=(const EdgeMap& cmap) {
196 return operator=<EdgeMap>(cmap);
199 template <typename CMap>
200 EdgeMap& operator=(const CMap& cmap) {
201 checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
202 const typename Parent::Graph* graph = Parent::getGraph();
204 for (graph->first(it); it != INVALID; graph->next(it)) {
205 Parent::set(it, cmap[it]);
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 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
227 const typename Parent::Graph* graph = Parent::getGraph();
229 for (graph->first(it); it != INVALID; graph->next(it)) {
230 Parent::set(it, cmap[it]);
238 /// \ingroup 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 UGraphAdaptorBase<_UGraph> Parent;
260 NodeFilterMap* node_filter_map;
261 UEdgeFilterMap* uedge_filter_map;
263 SubUGraphAdaptorBase()
264 : Parent(), node_filter_map(0), uedge_filter_map(0) { }
266 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
267 node_filter_map=&_node_filter_map;
269 void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {
270 uedge_filter_map=&_uedge_filter_map;
275 typedef typename Parent::Node Node;
276 typedef typename Parent::Edge Edge;
277 typedef typename Parent::UEdge UEdge;
279 void first(Node& i) const {
281 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
284 void first(Edge& i) const {
286 while (i!=INVALID && (!(*uedge_filter_map)[i]
287 || !(*node_filter_map)[Parent::source(i)]
288 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
291 void first(UEdge& i) const {
293 while (i!=INVALID && (!(*uedge_filter_map)[i]
294 || !(*node_filter_map)[Parent::source(i)]
295 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
298 void firstIn(Edge& i, const Node& n) const {
299 Parent::firstIn(i, n);
300 while (i!=INVALID && (!(*uedge_filter_map)[i]
301 || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
304 void firstOut(Edge& i, const Node& n) const {
305 Parent::firstOut(i, n);
306 while (i!=INVALID && (!(*uedge_filter_map)[i]
307 || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
310 void firstInc(UEdge& i, bool& d, const Node& n) const {
311 Parent::firstInc(i, d, n);
312 while (i!=INVALID && (!(*uedge_filter_map)[i]
313 || !(*node_filter_map)[Parent::target(i)])) Parent::nextInc(i, d);
316 void next(Node& i) const {
318 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
321 void next(Edge& i) const {
323 while (i!=INVALID && (!(*uedge_filter_map)[i]
324 || !(*node_filter_map)[Parent::source(i)]
325 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
328 void next(UEdge& i) const {
330 while (i!=INVALID && (!(*uedge_filter_map)[i]
331 || !(*node_filter_map)[Parent::source(i)]
332 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
335 void nextIn(Edge& i) const {
337 while (i!=INVALID && (!(*uedge_filter_map)[i]
338 || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
341 void nextOut(Edge& i) const {
343 while (i!=INVALID && (!(*uedge_filter_map)[i]
344 || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
347 void nextInc(UEdge& i, bool& d) const {
348 Parent::nextInc(i, d);
349 while (i!=INVALID && (!(*uedge_filter_map)[i]
350 || !(*node_filter_map)[Parent::source(i)])) Parent::nextInc(i, d);
355 /// This function hides \c n in the graph, i.e. the iteration
356 /// jumps over it. This is done by simply setting the value of \c n
357 /// to be false in the corresponding node-map.
358 void hide(const Node& n) const { node_filter_map->set(n, false); }
362 /// This function hides \c e in the graph, i.e. the iteration
363 /// jumps over it. This is done by simply setting the value of \c e
364 /// to be false in the corresponding edge-map.
365 void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
369 /// The value of \c n is set to be true in the node-map which stores
370 /// hide information. If \c n was hidden previuosly, then it is shown
372 void unHide(const Node& n) const { node_filter_map->set(n, true); }
376 /// The value of \c e is set to be true in the edge-map which stores
377 /// hide information. If \c e was hidden previuosly, then it is shown
379 void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
381 /// Returns true if \c n is hidden.
385 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
387 /// Returns true if \c n is hidden.
391 bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
393 typedef False NodeNumTag;
394 typedef False EdgeNumTag;
396 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
397 Edge findEdge(const Node& source, const Node& target,
398 const Edge& prev = INVALID) {
399 if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
402 Edge edge = Parent::findEdge(source, target, prev);
403 while (edge != INVALID && !(*uedge_filter_map)[edge]) {
404 edge = Parent::findEdge(source, target, edge);
408 UEdge findUEdge(const Node& source, const Node& target,
409 const UEdge& prev = INVALID) {
410 if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
413 UEdge uedge = Parent::findUEdge(source, target, prev);
414 while (uedge != INVALID && !(*uedge_filter_map)[uedge]) {
415 uedge = Parent::findUEdge(source, target, uedge);
421 template <typename _UGraph, typename NodeFilterMap, typename UEdgeFilterMap>
422 class SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, false>
423 : public UGraphAdaptorBase<_UGraph> {
425 typedef _UGraph Graph;
426 typedef UGraphAdaptorBase<_UGraph> Parent;
428 NodeFilterMap* node_filter_map;
429 UEdgeFilterMap* uedge_filter_map;
430 SubUGraphAdaptorBase() : Parent(),
431 node_filter_map(0), uedge_filter_map(0) { }
433 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
434 node_filter_map=&_node_filter_map;
436 void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {
437 uedge_filter_map=&_uedge_filter_map;
442 typedef typename Parent::Node Node;
443 typedef typename Parent::Edge Edge;
444 typedef typename Parent::UEdge UEdge;
446 void first(Node& i) const {
448 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
451 void first(Edge& i) const {
453 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
456 void first(UEdge& i) const {
458 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
461 void firstIn(Edge& i, const Node& n) const {
462 Parent::firstIn(i, n);
463 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextIn(i);
466 void firstOut(Edge& i, const Node& n) const {
467 Parent::firstOut(i, n);
468 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextOut(i);
471 void firstInc(UEdge& i, bool& d, const Node& n) const {
472 Parent::firstInc(i, d, n);
473 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d);
476 void next(Node& i) const {
478 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
480 void next(Edge& i) const {
482 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
484 void next(UEdge& i) const {
486 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
488 void nextIn(Edge& i) const {
490 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextIn(i);
493 void nextOut(Edge& i) const {
495 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextOut(i);
497 void nextInc(UEdge& i, bool& d) const {
498 Parent::nextInc(i, d);
499 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d);
504 /// This function hides \c n in the graph, i.e. the iteration
505 /// jumps over it. This is done by simply setting the value of \c n
506 /// to be false in the corresponding node-map.
507 void hide(const Node& n) const { node_filter_map->set(n, false); }
511 /// This function hides \c e in the graph, i.e. the iteration
512 /// jumps over it. This is done by simply setting the value of \c e
513 /// to be false in the corresponding edge-map.
514 void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
518 /// The value of \c n is set to be true in the node-map which stores
519 /// hide information. If \c n was hidden previuosly, then it is shown
521 void unHide(const Node& n) const { node_filter_map->set(n, true); }
525 /// The value of \c e is set to be true in the edge-map which stores
526 /// hide information. If \c e was hidden previuosly, then it is shown
528 void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
530 /// Returns true if \c n is hidden.
534 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
536 /// Returns true if \c n is hidden.
540 bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
542 typedef False NodeNumTag;
543 typedef False EdgeNumTag;
545 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
546 Edge findEdge(const Node& source, const Node& target,
547 const Edge& prev = INVALID) {
548 Edge edge = Parent::findEdge(source, target, prev);
549 while (edge != INVALID && !(*uedge_filter_map)[edge]) {
550 edge = Parent::findEdge(source, target, edge);
554 UEdge findUEdge(const Node& source, const Node& target,
555 const UEdge& prev = INVALID) {
556 UEdge uedge = Parent::findUEdge(source, target, prev);
557 while (uedge != INVALID && !(*uedge_filter_map)[uedge]) {
558 uedge = Parent::findUEdge(source, target, uedge);
564 /// \ingroup graph_adaptors
566 /// \brief A graph adaptor for hiding nodes and edges from an undirected
569 /// SubUGraphAdaptor shows the undirected graph with filtered node-set and
570 /// edge-set. If the \c checked parameter is true then it filters the edgeset
571 /// to do not get invalid edges without source or target.
573 /// If the \c checked template parameter is false then we have to note that
574 /// the node-iterator cares only the filter on the node-set, and the
575 /// edge-iterator cares only the filter on the edge-set.
576 /// This way the edge-map
577 /// should filter all edges which's source or target is filtered by the
580 /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
581 /// \c Graph::Node that is why \c g.id(n) can be applied.
583 template<typename _UGraph, typename NodeFilterMap,
584 typename UEdgeFilterMap, bool checked = true>
585 class SubUGraphAdaptor :
586 public UGraphAdaptorExtender<
587 SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, checked> > {
589 typedef _UGraph Graph;
590 typedef UGraphAdaptorExtender<
591 SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap> > Parent;
593 SubUGraphAdaptor() { }
595 SubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map,
596 UEdgeFilterMap& _uedge_filter_map) {
598 setNodeFilterMap(_node_filter_map);
599 setUEdgeFilterMap(_uedge_filter_map);
603 template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
604 SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>
605 subUGraphAdaptor(const UGraph& graph,
606 NodeFilterMap& nfm, EdgeFilterMap& efm) {
607 return SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>
611 template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
612 SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>
613 subUGraphAdaptor(const UGraph& graph,
614 NodeFilterMap& nfm, EdgeFilterMap& efm) {
615 return SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>
619 template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
620 SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>
621 subUGraphAdaptor(const UGraph& graph,
622 NodeFilterMap& nfm, EdgeFilterMap& efm) {
623 return SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>
627 template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
628 SubUGraphAdaptor<const UGraph, const NodeFilterMap, const EdgeFilterMap>
629 subUGraphAdaptor(const UGraph& graph,
630 NodeFilterMap& nfm, EdgeFilterMap& efm) {
631 return SubUGraphAdaptor<const UGraph, const NodeFilterMap,
632 const EdgeFilterMap>(graph, nfm, efm);
635 /// \ingroup graph_adaptors
637 /// \brief An adaptor for hiding nodes from an undirected graph.
639 /// An adaptor for hiding nodes from an undirected graph.
640 /// This adaptor specializes SubUGraphAdaptor in the way that only
642 /// can be filtered. In usual case the checked parameter is true, we get the
643 /// induced subgraph. But if the checked parameter is false then we can only
644 /// filter only isolated nodes.
645 template<typename _UGraph, typename NodeFilterMap, bool checked = true>
646 class NodeSubUGraphAdaptor :
647 public SubUGraphAdaptor<_UGraph, NodeFilterMap,
648 ConstMap<typename _UGraph::UEdge, bool>, checked> {
650 typedef SubUGraphAdaptor<_UGraph, NodeFilterMap,
651 ConstMap<typename _UGraph::UEdge, bool> > Parent;
652 typedef _UGraph Graph;
654 ConstMap<typename _UGraph::UEdge, bool> const_true_map;
656 NodeSubUGraphAdaptor() : const_true_map(true) {
657 Parent::setUEdgeFilterMap(const_true_map);
661 NodeSubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
662 Parent(), const_true_map(true) {
663 Parent::setGraph(_graph);
664 Parent::setNodeFilterMap(_node_filter_map);
665 Parent::setUEdgeFilterMap(const_true_map);
669 template<typename UGraph, typename NodeFilterMap>
670 NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>
671 nodeSubUGraphAdaptor(const UGraph& graph, NodeFilterMap& nfm) {
672 return NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>(graph, nfm);
675 template<typename UGraph, typename NodeFilterMap>
676 NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>
677 nodeSubUGraphAdaptor(const UGraph& graph, const NodeFilterMap& nfm) {
678 return NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>(graph, nfm);
682 /// \brief An adaptor for hiding undirected edges from an undirected graph.
684 /// \warning Graph adaptors are in even more experimental state
685 /// than the other parts of the lib. Use them at you own risk.
687 /// An adaptor for hiding undirected edges from an undirected graph.
688 /// This adaptor specializes SubUGraphAdaptor in the way that
689 /// only the edge-set
691 template<typename _UGraph, typename UEdgeFilterMap>
692 class EdgeSubUGraphAdaptor :
693 public SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>,
694 UEdgeFilterMap, false> {
696 typedef SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>,
697 UEdgeFilterMap, false> Parent;
698 typedef _UGraph Graph;
700 ConstMap<typename Graph::Node, bool> const_true_map;
702 EdgeSubUGraphAdaptor() : const_true_map(true) {
703 Parent::setNodeFilterMap(const_true_map);
707 EdgeSubUGraphAdaptor(Graph& _graph, UEdgeFilterMap& _uedge_filter_map) :
708 Parent(), const_true_map(true) {
709 Parent::setGraph(_graph);
710 Parent::setNodeFilterMap(const_true_map);
711 Parent::setUEdgeFilterMap(_uedge_filter_map);
715 template<typename UGraph, typename EdgeFilterMap>
716 EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>
717 edgeSubUGraphAdaptor(const UGraph& graph, EdgeFilterMap& efm) {
718 return EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>(graph, efm);
721 template<typename UGraph, typename EdgeFilterMap>
722 EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>
723 edgeSubUGraphAdaptor(const UGraph& graph, const EdgeFilterMap& efm) {
724 return EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>(graph, efm);
727 template <typename _UGraph, typename _DirectionMap>
728 class DirUGraphAdaptorBase {
731 typedef _UGraph Graph;
732 typedef _DirectionMap DirectionMap;
734 typedef typename _UGraph::Node Node;
735 typedef typename _UGraph::UEdge Edge;
737 void reverseEdge(const Edge& edge) {
738 direction->set(edge, !(*direction)[edge]);
741 void first(Node& i) const { graph->first(i); }
742 void first(Edge& i) const { graph->first(i); }
743 void firstIn(Edge& i, const Node& n) const {
745 graph->firstInc(i, d, n);
746 while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
748 void firstOut(Edge& i, const Node& n ) const {
750 graph->firstInc(i, d, n);
751 while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
754 void next(Node& i) const { graph->next(i); }
755 void next(Edge& i) const { graph->next(i); }
756 void nextIn(Edge& i) const {
757 bool d = !(*direction)[i];
758 graph->nextInc(i, d);
759 while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
761 void nextOut(Edge& i) const {
762 bool d = (*direction)[i];
763 graph->nextInc(i, d);
764 while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
767 Node source(const Edge& e) const {
768 return (*direction)[e] ? graph->source(e) : graph->target(e);
770 Node target(const Edge& e) const {
771 return (*direction)[e] ? graph->target(e) : graph->source(e);
774 typedef NodeNumTagIndicator<Graph> NodeNumTag;
775 int nodeNum() const { return graph->nodeNum(); }
777 typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
778 int edgeNum() const { return graph->uEdgeNum(); }
780 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
781 Edge findEdge(const Node& source, const Node& target,
782 const Edge& prev = INVALID) {
784 bool d = edge == INVALID ? true : (*direction)[edge];
786 edge = graph->findUEdge(source, target, edge);
787 while (edge != INVALID && !(*direction)[edge]) {
788 graph->findUEdge(source, target, edge);
790 if (edge != INVALID) return edge;
792 graph->findUEdge(target, source, edge);
793 while (edge != INVALID && (*direction)[edge]) {
794 graph->findUEdge(source, target, edge);
799 Node addNode() const {
800 return Node(graph->addNode());
803 Edge addEdge(const Node& source, const Node& target) const {
804 Edge edge = graph->addEdge(source, target);
805 (*direction)[edge] = graph->source(edge) == source;
809 void erase(const Node& i) const { graph->erase(i); }
810 void erase(const Edge& i) const { graph->erase(i); }
812 void clear() const { graph->clear(); }
814 int id(const Node& v) const { return graph->id(v); }
815 int id(const Edge& e) const { return graph->id(e); }
817 int maxNodeId() const {
818 return graph->maxNodeId();
821 int maxEdgeId() const {
822 return graph->maxEdgeId();
825 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
827 NodeNotifier& getNotifier(Node) const {
828 return graph->getNotifier(Node());
831 typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
833 EdgeNotifier& getNotifier(Edge) const {
834 return graph->getNotifier(Edge());
837 template <typename _Value>
838 class NodeMap : public _UGraph::template NodeMap<_Value> {
840 typedef typename _UGraph::template NodeMap<_Value> Parent;
841 explicit NodeMap(const DirUGraphAdaptorBase& ga)
842 : Parent(*ga.graph) { }
843 NodeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
844 : Parent(*ga.graph, value) { }
847 template <typename _Value>
848 class EdgeMap : public _UGraph::template UEdgeMap<_Value> {
850 typedef typename _UGraph::template UEdgeMap<_Value> Parent;
851 explicit EdgeMap(const DirUGraphAdaptorBase& ga)
852 : Parent(*ga.graph) { }
853 EdgeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
854 : Parent(*ga.graph, value) { }
861 DirectionMap* direction;
863 void setDirectionMap(DirectionMap& _direction) {
864 direction = &_direction;
867 void setGraph(Graph& _graph) {
874 /// \ingroup graph_adaptors
876 /// \brief A directed graph is made from an undirected graph by an adaptor
878 /// This adaptor gives a direction for each uedge in the undirected graph.
879 /// The direction of the edges stored in the DirectionMap. This map is
880 /// a bool map on the undirected edges. If the uedge is mapped to true
881 /// then the direction of the directed edge will be the same as the
882 /// default direction of the uedge. The edges can be easily reverted
883 /// by the reverseEdge member in the adaptor.
884 template<typename _Graph,
885 typename DirectionMap = typename _Graph::template UEdgeMap<bool> >
886 class DirUGraphAdaptor :
887 public GraphAdaptorExtender<
888 DirUGraphAdaptorBase<_Graph, DirectionMap> > {
890 typedef _Graph Graph;
891 typedef GraphAdaptorExtender<
892 DirUGraphAdaptorBase<_Graph, DirectionMap> > Parent;
894 DirUGraphAdaptor() { }
896 DirUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) {
898 setDirectionMap(_direction_map);
902 template<typename UGraph, typename DirectionMap>
903 DirUGraphAdaptor<const UGraph, DirectionMap>
904 dirUGraphAdaptor(const UGraph& graph, DirectionMap& dm) {
905 return DirUGraphAdaptor<const UGraph, DirectionMap>(graph, dm);
908 template<typename UGraph, typename DirectionMap>
909 DirUGraphAdaptor<const UGraph, const DirectionMap>
910 dirUGraphAdaptor(const UGraph& graph, const DirectionMap& dm) {
911 return DirUGraphAdaptor<const UGraph, const DirectionMap>(graph, dm);