1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_ADAPTORS_H
20 #define LEMON_ADAPTORS_H
22 /// \ingroup graph_adaptors
24 /// \brief Adaptor classes for digraphs and graphs
26 /// This file contains several useful adaptors for digraphs and graphs.
28 #include <lemon/core.h>
29 #include <lemon/maps.h>
30 #include <lemon/bits/variant.h>
32 #include <lemon/bits/graph_adaptor_extender.h>
33 #include <lemon/tolerance.h>
39 template<typename _Digraph>
40 class DigraphAdaptorBase {
42 typedef _Digraph Digraph;
43 typedef DigraphAdaptorBase Adaptor;
44 typedef Digraph ParentDigraph;
48 DigraphAdaptorBase() : _digraph(0) { }
49 void setDigraph(Digraph& digraph) { _digraph = &digraph; }
52 DigraphAdaptorBase(Digraph& digraph) : _digraph(&digraph) { }
54 typedef typename Digraph::Node Node;
55 typedef typename Digraph::Arc Arc;
57 void first(Node& i) const { _digraph->first(i); }
58 void first(Arc& i) const { _digraph->first(i); }
59 void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); }
60 void firstOut(Arc& i, const Node& n ) const { _digraph->firstOut(i, n); }
62 void next(Node& i) const { _digraph->next(i); }
63 void next(Arc& i) const { _digraph->next(i); }
64 void nextIn(Arc& i) const { _digraph->nextIn(i); }
65 void nextOut(Arc& i) const { _digraph->nextOut(i); }
67 Node source(const Arc& a) const { return _digraph->source(a); }
68 Node target(const Arc& a) const { return _digraph->target(a); }
70 typedef NodeNumTagIndicator<Digraph> NodeNumTag;
71 int nodeNum() const { return _digraph->nodeNum(); }
73 typedef ArcNumTagIndicator<Digraph> ArcNumTag;
74 int arcNum() const { return _digraph->arcNum(); }
76 typedef FindArcTagIndicator<Digraph> FindArcTag;
77 Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const {
78 return _digraph->findArc(u, v, prev);
81 Node addNode() { return _digraph->addNode(); }
82 Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
84 void erase(const Node& n) { _digraph->erase(n); }
85 void erase(const Arc& a) { _digraph->erase(a); }
87 void clear() { _digraph->clear(); }
89 int id(const Node& n) const { return _digraph->id(n); }
90 int id(const Arc& a) const { return _digraph->id(a); }
92 Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
93 Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); }
95 int maxNodeId() const { return _digraph->maxNodeId(); }
96 int maxArcId() const { return _digraph->maxArcId(); }
98 typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
99 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
101 typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier;
102 ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
104 template <typename _Value>
105 class NodeMap : public Digraph::template NodeMap<_Value> {
108 typedef typename Digraph::template NodeMap<_Value> Parent;
110 explicit NodeMap(const Adaptor& adaptor)
111 : Parent(*adaptor._digraph) {}
113 NodeMap(const Adaptor& adaptor, const _Value& value)
114 : Parent(*adaptor._digraph, value) { }
117 NodeMap& operator=(const NodeMap& cmap) {
118 return operator=<NodeMap>(cmap);
121 template <typename CMap>
122 NodeMap& operator=(const CMap& cmap) {
123 Parent::operator=(cmap);
129 template <typename _Value>
130 class ArcMap : public Digraph::template ArcMap<_Value> {
133 typedef typename Digraph::template ArcMap<_Value> Parent;
135 explicit ArcMap(const Adaptor& adaptor)
136 : Parent(*adaptor._digraph) {}
138 ArcMap(const Adaptor& adaptor, const _Value& value)
139 : Parent(*adaptor._digraph, value) {}
142 ArcMap& operator=(const ArcMap& cmap) {
143 return operator=<ArcMap>(cmap);
146 template <typename CMap>
147 ArcMap& operator=(const CMap& cmap) {
148 Parent::operator=(cmap);
156 template<typename _Graph>
157 class GraphAdaptorBase {
159 typedef _Graph Graph;
160 typedef Graph ParentGraph;
165 GraphAdaptorBase() : _graph(0) {}
167 void setGraph(Graph& graph) { _graph = &graph; }
170 GraphAdaptorBase(Graph& graph) : _graph(&graph) {}
172 typedef typename Graph::Node Node;
173 typedef typename Graph::Arc Arc;
174 typedef typename Graph::Edge Edge;
176 void first(Node& i) const { _graph->first(i); }
177 void first(Arc& i) const { _graph->first(i); }
178 void first(Edge& i) const { _graph->first(i); }
179 void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); }
180 void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); }
181 void firstInc(Edge &i, bool &d, const Node &n) const {
182 _graph->firstInc(i, d, n);
185 void next(Node& i) const { _graph->next(i); }
186 void next(Arc& i) const { _graph->next(i); }
187 void next(Edge& i) const { _graph->next(i); }
188 void nextIn(Arc& i) const { _graph->nextIn(i); }
189 void nextOut(Arc& i) const { _graph->nextOut(i); }
190 void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); }
192 Node u(const Edge& e) const { return _graph->u(e); }
193 Node v(const Edge& e) const { return _graph->v(e); }
195 Node source(const Arc& a) const { return _graph->source(a); }
196 Node target(const Arc& a) const { return _graph->target(a); }
198 typedef NodeNumTagIndicator<Graph> NodeNumTag;
199 int nodeNum() const { return _graph->nodeNum(); }
201 typedef ArcNumTagIndicator<Graph> ArcNumTag;
202 int arcNum() const { return _graph->arcNum(); }
204 typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
205 int edgeNum() const { return _graph->edgeNum(); }
207 typedef FindArcTagIndicator<Graph> FindArcTag;
208 Arc findArc(const Node& u, const Node& v,
209 const Arc& prev = INVALID) const {
210 return _graph->findArc(u, v, prev);
213 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
214 Edge findEdge(const Node& u, const Node& v,
215 const Edge& prev = INVALID) const {
216 return _graph->findEdge(u, v, prev);
219 Node addNode() { return _graph->addNode(); }
220 Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }
222 void erase(const Node& i) { _graph->erase(i); }
223 void erase(const Edge& i) { _graph->erase(i); }
225 void clear() { _graph->clear(); }
227 bool direction(const Arc& a) const { return _graph->direction(a); }
228 Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); }
230 int id(const Node& v) const { return _graph->id(v); }
231 int id(const Arc& a) const { return _graph->id(a); }
232 int id(const Edge& e) const { return _graph->id(e); }
234 Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
235 Arc arcFromId(int ix) const { return _graph->arcFromId(ix); }
236 Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); }
238 int maxNodeId() const { return _graph->maxNodeId(); }
239 int maxArcId() const { return _graph->maxArcId(); }
240 int maxEdgeId() const { return _graph->maxEdgeId(); }
242 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
243 NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
245 typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
246 ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
248 typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
249 EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
251 template <typename _Value>
252 class NodeMap : public Graph::template NodeMap<_Value> {
254 typedef typename Graph::template NodeMap<_Value> Parent;
255 explicit NodeMap(const GraphAdaptorBase<Graph>& adapter)
256 : Parent(*adapter._graph) {}
257 NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
258 : Parent(*adapter._graph, value) {}
261 NodeMap& operator=(const NodeMap& cmap) {
262 return operator=<NodeMap>(cmap);
265 template <typename CMap>
266 NodeMap& operator=(const CMap& cmap) {
267 Parent::operator=(cmap);
273 template <typename _Value>
274 class ArcMap : public Graph::template ArcMap<_Value> {
276 typedef typename Graph::template ArcMap<_Value> Parent;
277 explicit ArcMap(const GraphAdaptorBase<Graph>& adapter)
278 : Parent(*adapter._graph) {}
279 ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
280 : Parent(*adapter._graph, value) {}
283 ArcMap& operator=(const ArcMap& cmap) {
284 return operator=<ArcMap>(cmap);
287 template <typename CMap>
288 ArcMap& operator=(const CMap& cmap) {
289 Parent::operator=(cmap);
294 template <typename _Value>
295 class EdgeMap : public Graph::template EdgeMap<_Value> {
297 typedef typename Graph::template EdgeMap<_Value> Parent;
298 explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)
299 : Parent(*adapter._graph) {}
300 EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
301 : Parent(*adapter._graph, value) {}
304 EdgeMap& operator=(const EdgeMap& cmap) {
305 return operator=<EdgeMap>(cmap);
308 template <typename CMap>
309 EdgeMap& operator=(const CMap& cmap) {
310 Parent::operator=(cmap);
317 template <typename _Digraph>
318 class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> {
320 typedef _Digraph Digraph;
321 typedef DigraphAdaptorBase<_Digraph> Parent;
323 ReverseDigraphBase() : Parent() { }
325 typedef typename Parent::Node Node;
326 typedef typename Parent::Arc Arc;
328 void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }
329 void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); }
331 void nextIn(Arc& a) const { Parent::nextOut(a); }
332 void nextOut(Arc& a) const { Parent::nextIn(a); }
334 Node source(const Arc& a) const { return Parent::target(a); }
335 Node target(const Arc& a) const { return Parent::source(a); }
337 Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
339 typedef FindArcTagIndicator<Digraph> FindArcTag;
340 Arc findArc(const Node& u, const Node& v,
341 const Arc& prev = INVALID) const {
342 return Parent::findArc(v, u, prev);
347 /// \ingroup graph_adaptors
349 /// \brief Adaptor class for reversing the orientation of the arcs in
352 /// ReverseDigraph can be used for reversing the arcs in a digraph.
353 /// It conforms to the \ref concepts::Digraph "Digraph" concept.
355 /// The adapted digraph can also be modified through this adaptor
356 /// by adding or removing nodes or arcs, unless the \c _Digraph template
357 /// parameter is set to be \c const.
359 /// \tparam _Digraph The type of the adapted digraph.
360 /// It must conform to the \ref concepts::Digraph "Digraph" concept.
361 /// It can also be specified to be \c const.
363 /// \note The \c Node and \c Arc types of this adaptor and the adapted
364 /// digraph are convertible to each other.
365 template<typename _Digraph>
366 class ReverseDigraph :
367 public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > {
369 typedef _Digraph Digraph;
370 typedef DigraphAdaptorExtender<
371 ReverseDigraphBase<_Digraph> > Parent;
376 /// \brief Constructor
378 /// Creates a reverse digraph adaptor for the given digraph.
379 explicit ReverseDigraph(Digraph& digraph) {
380 Parent::setDigraph(digraph);
384 /// \brief Returns a read-only ReverseDigraph adaptor
386 /// This function just returns a read-only \ref ReverseDigraph adaptor.
387 /// \ingroup graph_adaptors
388 /// \relates ReverseDigraph
389 template<typename Digraph>
390 ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) {
391 return ReverseDigraph<const Digraph>(digraph);
395 template <typename _Digraph, typename _NodeFilterMap,
396 typename _ArcFilterMap, bool _checked = true>
397 class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {
399 typedef _Digraph Digraph;
400 typedef _NodeFilterMap NodeFilterMap;
401 typedef _ArcFilterMap ArcFilterMap;
403 typedef SubDigraphBase Adaptor;
404 typedef DigraphAdaptorBase<_Digraph> Parent;
406 NodeFilterMap* _node_filter;
407 ArcFilterMap* _arc_filter;
409 : Parent(), _node_filter(0), _arc_filter(0) { }
411 void setNodeFilterMap(NodeFilterMap& node_filter) {
412 _node_filter = &node_filter;
414 void setArcFilterMap(ArcFilterMap& arc_filter) {
415 _arc_filter = &arc_filter;
420 typedef typename Parent::Node Node;
421 typedef typename Parent::Arc Arc;
423 void first(Node& i) const {
425 while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
428 void first(Arc& i) const {
430 while (i != INVALID && (!(*_arc_filter)[i]
431 || !(*_node_filter)[Parent::source(i)]
432 || !(*_node_filter)[Parent::target(i)]))
436 void firstIn(Arc& i, const Node& n) const {
437 Parent::firstIn(i, n);
438 while (i != INVALID && (!(*_arc_filter)[i]
439 || !(*_node_filter)[Parent::source(i)]))
443 void firstOut(Arc& i, const Node& n) const {
444 Parent::firstOut(i, n);
445 while (i != INVALID && (!(*_arc_filter)[i]
446 || !(*_node_filter)[Parent::target(i)]))
450 void next(Node& i) const {
452 while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
455 void next(Arc& i) const {
457 while (i != INVALID && (!(*_arc_filter)[i]
458 || !(*_node_filter)[Parent::source(i)]
459 || !(*_node_filter)[Parent::target(i)]))
463 void nextIn(Arc& i) const {
465 while (i != INVALID && (!(*_arc_filter)[i]
466 || !(*_node_filter)[Parent::source(i)]))
470 void nextOut(Arc& i) const {
472 while (i != INVALID && (!(*_arc_filter)[i]
473 || !(*_node_filter)[Parent::target(i)]))
477 void hide(const Node& n) const { _node_filter->set(n, false); }
478 void hide(const Arc& a) const { _arc_filter->set(a, false); }
480 void unHide(const Node& n) const { _node_filter->set(n, true); }
481 void unHide(const Arc& a) const { _arc_filter->set(a, true); }
483 bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
484 bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }
486 typedef False NodeNumTag;
487 typedef False ArcNumTag;
489 typedef FindArcTagIndicator<Digraph> FindArcTag;
490 Arc findArc(const Node& source, const Node& target,
491 const Arc& prev = INVALID) const {
492 if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
495 Arc arc = Parent::findArc(source, target, prev);
496 while (arc != INVALID && !(*_arc_filter)[arc]) {
497 arc = Parent::findArc(source, target, arc);
502 template <typename _Value>
503 class NodeMap : public SubMapExtender<Adaptor,
504 typename Parent::template NodeMap<_Value> > {
506 typedef _Value Value;
507 typedef SubMapExtender<Adaptor, typename Parent::
508 template NodeMap<Value> > MapParent;
510 NodeMap(const Adaptor& adaptor)
511 : MapParent(adaptor) {}
512 NodeMap(const Adaptor& adaptor, const Value& value)
513 : MapParent(adaptor, value) {}
516 NodeMap& operator=(const NodeMap& cmap) {
517 return operator=<NodeMap>(cmap);
520 template <typename CMap>
521 NodeMap& operator=(const CMap& cmap) {
522 MapParent::operator=(cmap);
527 template <typename _Value>
528 class ArcMap : public SubMapExtender<Adaptor,
529 typename Parent::template ArcMap<_Value> > {
531 typedef _Value Value;
532 typedef SubMapExtender<Adaptor, typename Parent::
533 template ArcMap<Value> > MapParent;
535 ArcMap(const Adaptor& adaptor)
536 : MapParent(adaptor) {}
537 ArcMap(const Adaptor& adaptor, const Value& value)
538 : MapParent(adaptor, value) {}
541 ArcMap& operator=(const ArcMap& cmap) {
542 return operator=<ArcMap>(cmap);
545 template <typename CMap>
546 ArcMap& operator=(const CMap& cmap) {
547 MapParent::operator=(cmap);
554 template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>
555 class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>
556 : public DigraphAdaptorBase<_Digraph> {
558 typedef _Digraph Digraph;
559 typedef _NodeFilterMap NodeFilterMap;
560 typedef _ArcFilterMap ArcFilterMap;
562 typedef SubDigraphBase Adaptor;
563 typedef DigraphAdaptorBase<Digraph> Parent;
565 NodeFilterMap* _node_filter;
566 ArcFilterMap* _arc_filter;
568 : Parent(), _node_filter(0), _arc_filter(0) { }
570 void setNodeFilterMap(NodeFilterMap& node_filter) {
571 _node_filter = &node_filter;
573 void setArcFilterMap(ArcFilterMap& arc_filter) {
574 _arc_filter = &arc_filter;
579 typedef typename Parent::Node Node;
580 typedef typename Parent::Arc Arc;
582 void first(Node& i) const {
584 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
587 void first(Arc& i) const {
589 while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
592 void firstIn(Arc& i, const Node& n) const {
593 Parent::firstIn(i, n);
594 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
597 void firstOut(Arc& i, const Node& n) const {
598 Parent::firstOut(i, n);
599 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
602 void next(Node& i) const {
604 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
606 void next(Arc& i) const {
608 while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
610 void nextIn(Arc& i) const {
612 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
615 void nextOut(Arc& i) const {
617 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
620 void hide(const Node& n) const { _node_filter->set(n, false); }
621 void hide(const Arc& e) const { _arc_filter->set(e, false); }
623 void unHide(const Node& n) const { _node_filter->set(n, true); }
624 void unHide(const Arc& e) const { _arc_filter->set(e, true); }
626 bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
627 bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }
629 typedef False NodeNumTag;
630 typedef False ArcNumTag;
632 typedef FindArcTagIndicator<Digraph> FindArcTag;
633 Arc findArc(const Node& source, const Node& target,
634 const Arc& prev = INVALID) const {
635 if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
638 Arc arc = Parent::findArc(source, target, prev);
639 while (arc != INVALID && !(*_arc_filter)[arc]) {
640 arc = Parent::findArc(source, target, arc);
645 template <typename _Value>
646 class NodeMap : public SubMapExtender<Adaptor,
647 typename Parent::template NodeMap<_Value> > {
649 typedef _Value Value;
650 typedef SubMapExtender<Adaptor, typename Parent::
651 template NodeMap<Value> > MapParent;
653 NodeMap(const Adaptor& adaptor)
654 : MapParent(adaptor) {}
655 NodeMap(const Adaptor& adaptor, const Value& value)
656 : MapParent(adaptor, value) {}
659 NodeMap& operator=(const NodeMap& cmap) {
660 return operator=<NodeMap>(cmap);
663 template <typename CMap>
664 NodeMap& operator=(const CMap& cmap) {
665 MapParent::operator=(cmap);
670 template <typename _Value>
671 class ArcMap : public SubMapExtender<Adaptor,
672 typename Parent::template ArcMap<_Value> > {
674 typedef _Value Value;
675 typedef SubMapExtender<Adaptor, typename Parent::
676 template ArcMap<Value> > MapParent;
678 ArcMap(const Adaptor& adaptor)
679 : MapParent(adaptor) {}
680 ArcMap(const Adaptor& adaptor, const Value& value)
681 : MapParent(adaptor, value) {}
684 ArcMap& operator=(const ArcMap& cmap) {
685 return operator=<ArcMap>(cmap);
688 template <typename CMap>
689 ArcMap& operator=(const CMap& cmap) {
690 MapParent::operator=(cmap);
697 /// \ingroup graph_adaptors
699 /// \brief Adaptor class for hiding nodes and arcs in a digraph
701 /// SubDigraph can be used for hiding nodes and arcs in a digraph.
702 /// A \c bool node map and a \c bool arc map must be specified, which
703 /// define the filters for nodes and arcs.
704 /// Only the nodes and arcs with \c true filter value are
705 /// shown in the subdigraph. This adaptor conforms to the \ref
706 /// concepts::Digraph "Digraph" concept. If the \c _checked parameter
707 /// is \c true, then the arcs incident to hidden nodes are also
710 /// The adapted digraph can also be modified through this adaptor
711 /// by adding or removing nodes or arcs, unless the \c _Digraph template
712 /// parameter is set to be \c const.
714 /// \tparam _Digraph The type of the adapted digraph.
715 /// It must conform to the \ref concepts::Digraph "Digraph" concept.
716 /// It can also be specified to be \c const.
717 /// \tparam _NodeFilterMap A \c bool (or convertible) node map of the
718 /// adapted digraph. The default map type is
719 /// \ref concepts::Digraph::NodeMap "_Digraph::NodeMap<bool>".
720 /// \tparam _ArcFilterMap A \c bool (or convertible) arc map of the
721 /// adapted digraph. The default map type is
722 /// \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<bool>".
723 /// \tparam _checked If this parameter is set to \c false, then the arc
724 /// filtering is not checked with respect to the node filter.
725 /// Otherwise, each arc that is incident to a hidden node is automatically
726 /// filtered out. This is the default option.
728 /// \note The \c Node and \c Arc types of this adaptor and the adapted
729 /// digraph are convertible to each other.
734 template<typename _Digraph,
735 typename _NodeFilterMap,
736 typename _ArcFilterMap,
739 template<typename _Digraph,
740 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
741 typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,
742 bool _checked = true>
745 : public DigraphAdaptorExtender<
746 SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > {
748 /// The type of the adapted digraph.
749 typedef _Digraph Digraph;
750 /// The type of the node filter map.
751 typedef _NodeFilterMap NodeFilterMap;
752 /// The type of the arc filter map.
753 typedef _ArcFilterMap ArcFilterMap;
755 typedef DigraphAdaptorExtender<
756 SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> >
759 typedef typename Parent::Node Node;
760 typedef typename Parent::Arc Arc;
766 /// \brief Constructor
768 /// Creates a subdigraph for the given digraph with the
769 /// given node and arc filter maps.
770 SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,
771 ArcFilterMap& arc_filter) {
773 setNodeFilterMap(node_filter);
774 setArcFilterMap(arc_filter);
777 /// \brief Hides the given node
779 /// This function hides the given node in the subdigraph,
780 /// i.e. the iteration jumps over it.
781 /// It is done by simply setting the assigned value of \c n
782 /// to be \c false in the node filter map.
783 void hide(const Node& n) const { Parent::hide(n); }
785 /// \brief Hides the given arc
787 /// This function hides the given arc in the subdigraph,
788 /// i.e. the iteration jumps over it.
789 /// It is done by simply setting the assigned value of \c a
790 /// to be \c false in the arc filter map.
791 void hide(const Arc& a) const { Parent::hide(a); }
793 /// \brief Shows the given node
795 /// This function shows the given node in the subdigraph.
796 /// It is done by simply setting the assigned value of \c n
797 /// to be \c true in the node filter map.
798 void unHide(const Node& n) const { Parent::unHide(n); }
800 /// \brief Shows the given arc
802 /// This function shows the given arc in the subdigraph.
803 /// It is done by simply setting the assigned value of \c a
804 /// to be \c true in the arc filter map.
805 void unHide(const Arc& a) const { Parent::unHide(a); }
807 /// \brief Returns \c true if the given node is hidden.
809 /// This function returns \c true if the given node is hidden.
810 bool hidden(const Node& n) const { return Parent::hidden(n); }
812 /// \brief Returns \c true if the given arc is hidden.
814 /// This function returns \c true if the given arc is hidden.
815 bool hidden(const Arc& a) const { return Parent::hidden(a); }
819 /// \brief Returns a read-only SubDigraph adaptor
821 /// This function just returns a read-only \ref SubDigraph adaptor.
822 /// \ingroup graph_adaptors
823 /// \relates SubDigraph
824 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
825 SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
826 subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) {
827 return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
831 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
832 SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
833 subDigraph(const Digraph& digraph,
834 const NodeFilterMap& nfm, ArcFilterMap& afm) {
835 return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
839 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
840 SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
841 subDigraph(const Digraph& digraph,
842 NodeFilterMap& nfm, const ArcFilterMap& afm) {
843 return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
847 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
848 SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap>
849 subDigraph(const Digraph& digraph,
850 const NodeFilterMap& nfm, const ArcFilterMap& afm) {
851 return SubDigraph<const Digraph, const NodeFilterMap,
852 const ArcFilterMap>(digraph, nfm, afm);
856 template <typename _Graph, typename _NodeFilterMap,
857 typename _EdgeFilterMap, bool _checked = true>
858 class SubGraphBase : public GraphAdaptorBase<_Graph> {
860 typedef _Graph Graph;
861 typedef _NodeFilterMap NodeFilterMap;
862 typedef _EdgeFilterMap EdgeFilterMap;
864 typedef SubGraphBase Adaptor;
865 typedef GraphAdaptorBase<_Graph> Parent;
868 NodeFilterMap* _node_filter_map;
869 EdgeFilterMap* _edge_filter_map;
872 : Parent(), _node_filter_map(0), _edge_filter_map(0) { }
874 void setNodeFilterMap(NodeFilterMap& node_filter_map) {
875 _node_filter_map=&node_filter_map;
877 void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
878 _edge_filter_map=&edge_filter_map;
883 typedef typename Parent::Node Node;
884 typedef typename Parent::Arc Arc;
885 typedef typename Parent::Edge Edge;
887 void first(Node& i) const {
889 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
892 void first(Arc& i) const {
894 while (i!=INVALID && (!(*_edge_filter_map)[i]
895 || !(*_node_filter_map)[Parent::source(i)]
896 || !(*_node_filter_map)[Parent::target(i)]))
900 void first(Edge& i) const {
902 while (i!=INVALID && (!(*_edge_filter_map)[i]
903 || !(*_node_filter_map)[Parent::u(i)]
904 || !(*_node_filter_map)[Parent::v(i)]))
908 void firstIn(Arc& i, const Node& n) const {
909 Parent::firstIn(i, n);
910 while (i!=INVALID && (!(*_edge_filter_map)[i]
911 || !(*_node_filter_map)[Parent::source(i)]))
915 void firstOut(Arc& i, const Node& n) const {
916 Parent::firstOut(i, n);
917 while (i!=INVALID && (!(*_edge_filter_map)[i]
918 || !(*_node_filter_map)[Parent::target(i)]))
922 void firstInc(Edge& i, bool& d, const Node& n) const {
923 Parent::firstInc(i, d, n);
924 while (i!=INVALID && (!(*_edge_filter_map)[i]
925 || !(*_node_filter_map)[Parent::u(i)]
926 || !(*_node_filter_map)[Parent::v(i)]))
927 Parent::nextInc(i, d);
930 void next(Node& i) const {
932 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
935 void next(Arc& i) const {
937 while (i!=INVALID && (!(*_edge_filter_map)[i]
938 || !(*_node_filter_map)[Parent::source(i)]
939 || !(*_node_filter_map)[Parent::target(i)]))
943 void next(Edge& i) const {
945 while (i!=INVALID && (!(*_edge_filter_map)[i]
946 || !(*_node_filter_map)[Parent::u(i)]
947 || !(*_node_filter_map)[Parent::v(i)]))
951 void nextIn(Arc& i) const {
953 while (i!=INVALID && (!(*_edge_filter_map)[i]
954 || !(*_node_filter_map)[Parent::source(i)]))
958 void nextOut(Arc& i) const {
960 while (i!=INVALID && (!(*_edge_filter_map)[i]
961 || !(*_node_filter_map)[Parent::target(i)]))
965 void nextInc(Edge& i, bool& d) const {
966 Parent::nextInc(i, d);
967 while (i!=INVALID && (!(*_edge_filter_map)[i]
968 || !(*_node_filter_map)[Parent::u(i)]
969 || !(*_node_filter_map)[Parent::v(i)]))
970 Parent::nextInc(i, d);
973 void hide(const Node& n) const { _node_filter_map->set(n, false); }
974 void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
976 void unHide(const Node& n) const { _node_filter_map->set(n, true); }
977 void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
979 bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
980 bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
982 typedef False NodeNumTag;
983 typedef False ArcNumTag;
984 typedef False EdgeNumTag;
986 typedef FindArcTagIndicator<Graph> FindArcTag;
987 Arc findArc(const Node& u, const Node& v,
988 const Arc& prev = INVALID) const {
989 if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
992 Arc arc = Parent::findArc(u, v, prev);
993 while (arc != INVALID && !(*_edge_filter_map)[arc]) {
994 arc = Parent::findArc(u, v, arc);
999 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1000 Edge findEdge(const Node& u, const Node& v,
1001 const Edge& prev = INVALID) const {
1002 if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
1005 Edge edge = Parent::findEdge(u, v, prev);
1006 while (edge != INVALID && !(*_edge_filter_map)[edge]) {
1007 edge = Parent::findEdge(u, v, edge);
1012 template <typename _Value>
1013 class NodeMap : public SubMapExtender<Adaptor,
1014 typename Parent::template NodeMap<_Value> > {
1016 typedef _Value Value;
1017 typedef SubMapExtender<Adaptor, typename Parent::
1018 template NodeMap<Value> > MapParent;
1020 NodeMap(const Adaptor& adaptor)
1021 : MapParent(adaptor) {}
1022 NodeMap(const Adaptor& adaptor, const Value& value)
1023 : MapParent(adaptor, value) {}
1026 NodeMap& operator=(const NodeMap& cmap) {
1027 return operator=<NodeMap>(cmap);
1030 template <typename CMap>
1031 NodeMap& operator=(const CMap& cmap) {
1032 MapParent::operator=(cmap);
1037 template <typename _Value>
1038 class ArcMap : public SubMapExtender<Adaptor,
1039 typename Parent::template ArcMap<_Value> > {
1041 typedef _Value Value;
1042 typedef SubMapExtender<Adaptor, typename Parent::
1043 template ArcMap<Value> > MapParent;
1045 ArcMap(const Adaptor& adaptor)
1046 : MapParent(adaptor) {}
1047 ArcMap(const Adaptor& adaptor, const Value& value)
1048 : MapParent(adaptor, value) {}
1051 ArcMap& operator=(const ArcMap& cmap) {
1052 return operator=<ArcMap>(cmap);
1055 template <typename CMap>
1056 ArcMap& operator=(const CMap& cmap) {
1057 MapParent::operator=(cmap);
1062 template <typename _Value>
1063 class EdgeMap : public SubMapExtender<Adaptor,
1064 typename Parent::template EdgeMap<_Value> > {
1066 typedef _Value Value;
1067 typedef SubMapExtender<Adaptor, typename Parent::
1068 template EdgeMap<Value> > MapParent;
1070 EdgeMap(const Adaptor& adaptor)
1071 : MapParent(adaptor) {}
1073 EdgeMap(const Adaptor& adaptor, const Value& value)
1074 : MapParent(adaptor, value) {}
1077 EdgeMap& operator=(const EdgeMap& cmap) {
1078 return operator=<EdgeMap>(cmap);
1081 template <typename CMap>
1082 EdgeMap& operator=(const CMap& cmap) {
1083 MapParent::operator=(cmap);
1090 template <typename _Graph, typename _NodeFilterMap, typename _EdgeFilterMap>
1091 class SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, false>
1092 : public GraphAdaptorBase<_Graph> {
1094 typedef _Graph Graph;
1095 typedef _NodeFilterMap NodeFilterMap;
1096 typedef _EdgeFilterMap EdgeFilterMap;
1098 typedef SubGraphBase Adaptor;
1099 typedef GraphAdaptorBase<_Graph> Parent;
1101 NodeFilterMap* _node_filter_map;
1102 EdgeFilterMap* _edge_filter_map;
1103 SubGraphBase() : Parent(),
1104 _node_filter_map(0), _edge_filter_map(0) { }
1106 void setNodeFilterMap(NodeFilterMap& node_filter_map) {
1107 _node_filter_map=&node_filter_map;
1109 void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
1110 _edge_filter_map=&edge_filter_map;
1115 typedef typename Parent::Node Node;
1116 typedef typename Parent::Arc Arc;
1117 typedef typename Parent::Edge Edge;
1119 void first(Node& i) const {
1121 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
1124 void first(Arc& i) const {
1126 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1129 void first(Edge& i) const {
1131 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1134 void firstIn(Arc& i, const Node& n) const {
1135 Parent::firstIn(i, n);
1136 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
1139 void firstOut(Arc& i, const Node& n) const {
1140 Parent::firstOut(i, n);
1141 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
1144 void firstInc(Edge& i, bool& d, const Node& n) const {
1145 Parent::firstInc(i, d, n);
1146 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
1149 void next(Node& i) const {
1151 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
1153 void next(Arc& i) const {
1155 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1157 void next(Edge& i) const {
1159 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1161 void nextIn(Arc& i) const {
1163 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
1166 void nextOut(Arc& i) const {
1168 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
1170 void nextInc(Edge& i, bool& d) const {
1171 Parent::nextInc(i, d);
1172 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
1175 void hide(const Node& n) const { _node_filter_map->set(n, false); }
1176 void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
1178 void unHide(const Node& n) const { _node_filter_map->set(n, true); }
1179 void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
1181 bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
1182 bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
1184 typedef False NodeNumTag;
1185 typedef False ArcNumTag;
1186 typedef False EdgeNumTag;
1188 typedef FindArcTagIndicator<Graph> FindArcTag;
1189 Arc findArc(const Node& u, const Node& v,
1190 const Arc& prev = INVALID) const {
1191 Arc arc = Parent::findArc(u, v, prev);
1192 while (arc != INVALID && !(*_edge_filter_map)[arc]) {
1193 arc = Parent::findArc(u, v, arc);
1198 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1199 Edge findEdge(const Node& u, const Node& v,
1200 const Edge& prev = INVALID) const {
1201 Edge edge = Parent::findEdge(u, v, prev);
1202 while (edge != INVALID && !(*_edge_filter_map)[edge]) {
1203 edge = Parent::findEdge(u, v, edge);
1208 template <typename _Value>
1209 class NodeMap : public SubMapExtender<Adaptor,
1210 typename Parent::template NodeMap<_Value> > {
1212 typedef _Value Value;
1213 typedef SubMapExtender<Adaptor, typename Parent::
1214 template NodeMap<Value> > MapParent;
1216 NodeMap(const Adaptor& adaptor)
1217 : MapParent(adaptor) {}
1218 NodeMap(const Adaptor& adaptor, const Value& value)
1219 : MapParent(adaptor, value) {}
1222 NodeMap& operator=(const NodeMap& cmap) {
1223 return operator=<NodeMap>(cmap);
1226 template <typename CMap>
1227 NodeMap& operator=(const CMap& cmap) {
1228 MapParent::operator=(cmap);
1233 template <typename _Value>
1234 class ArcMap : public SubMapExtender<Adaptor,
1235 typename Parent::template ArcMap<_Value> > {
1237 typedef _Value Value;
1238 typedef SubMapExtender<Adaptor, typename Parent::
1239 template ArcMap<Value> > MapParent;
1241 ArcMap(const Adaptor& adaptor)
1242 : MapParent(adaptor) {}
1243 ArcMap(const Adaptor& adaptor, const Value& value)
1244 : MapParent(adaptor, value) {}
1247 ArcMap& operator=(const ArcMap& cmap) {
1248 return operator=<ArcMap>(cmap);
1251 template <typename CMap>
1252 ArcMap& operator=(const CMap& cmap) {
1253 MapParent::operator=(cmap);
1258 template <typename _Value>
1259 class EdgeMap : public SubMapExtender<Adaptor,
1260 typename Parent::template EdgeMap<_Value> > {
1262 typedef _Value Value;
1263 typedef SubMapExtender<Adaptor, typename Parent::
1264 template EdgeMap<Value> > MapParent;
1266 EdgeMap(const Adaptor& adaptor)
1267 : MapParent(adaptor) {}
1269 EdgeMap(const Adaptor& adaptor, const _Value& value)
1270 : MapParent(adaptor, value) {}
1273 EdgeMap& operator=(const EdgeMap& cmap) {
1274 return operator=<EdgeMap>(cmap);
1277 template <typename CMap>
1278 EdgeMap& operator=(const CMap& cmap) {
1279 MapParent::operator=(cmap);
1286 /// \ingroup graph_adaptors
1288 /// \brief Adaptor class for hiding nodes and edges in an undirected
1291 /// SubGraph can be used for hiding nodes and edges in a graph.
1292 /// A \c bool node map and a \c bool edge map must be specified, which
1293 /// define the filters for nodes and edges.
1294 /// Only the nodes and edges with \c true filter value are
1295 /// shown in the subgraph. This adaptor conforms to the \ref
1296 /// concepts::Graph "Graph" concept. If the \c _checked parameter is
1297 /// \c true, then the edges incident to hidden nodes are also
1300 /// The adapted graph can also be modified through this adaptor
1301 /// by adding or removing nodes or edges, unless the \c _Graph template
1302 /// parameter is set to be \c const.
1304 /// \tparam _Graph The type of the adapted graph.
1305 /// It must conform to the \ref concepts::Graph "Graph" concept.
1306 /// It can also be specified to be \c const.
1307 /// \tparam _NodeFilterMap A \c bool (or convertible) node map of the
1308 /// adapted graph. The default map type is
1309 /// \ref concepts::Graph::NodeMap "_Graph::NodeMap<bool>".
1310 /// \tparam _EdgeFilterMap A \c bool (or convertible) edge map of the
1311 /// adapted graph. The default map type is
1312 /// \ref concepts::Graph::EdgeMap "_Graph::EdgeMap<bool>".
1313 /// \tparam _checked If this parameter is set to \c false, then the edge
1314 /// filtering is not checked with respect to the node filter.
1315 /// Otherwise, each edge that is incident to a hidden node is automatically
1316 /// filtered out. This is the default option.
1318 /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the
1319 /// adapted graph are convertible to each other.
1321 /// \see FilterNodes
1322 /// \see FilterEdges
1324 template<typename _Graph,
1325 typename _NodeFilterMap,
1326 typename _EdgeFilterMap,
1329 template<typename _Graph,
1330 typename _NodeFilterMap = typename _Graph::template NodeMap<bool>,
1331 typename _EdgeFilterMap = typename _Graph::template EdgeMap<bool>,
1332 bool _checked = true>
1335 : public GraphAdaptorExtender<
1336 SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, _checked> > {
1338 /// The type of the adapted graph.
1339 typedef _Graph Graph;
1340 /// The type of the node filter map.
1341 typedef _NodeFilterMap NodeFilterMap;
1342 /// The type of the edge filter map.
1343 typedef _EdgeFilterMap EdgeFilterMap;
1345 typedef GraphAdaptorExtender<
1346 SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, _checked> > Parent;
1348 typedef typename Parent::Node Node;
1349 typedef typename Parent::Edge Edge;
1355 /// \brief Constructor
1357 /// Creates a subgraph for the given graph with the given node
1358 /// and edge filter maps.
1359 SubGraph(Graph& graph, NodeFilterMap& node_filter_map,
1360 EdgeFilterMap& edge_filter_map) {
1362 setNodeFilterMap(node_filter_map);
1363 setEdgeFilterMap(edge_filter_map);
1366 /// \brief Hides the given node
1368 /// This function hides the given node in the subgraph,
1369 /// i.e. the iteration jumps over it.
1370 /// It is done by simply setting the assigned value of \c n
1371 /// to be \c false in the node filter map.
1372 void hide(const Node& n) const { Parent::hide(n); }
1374 /// \brief Hides the given edge
1376 /// This function hides the given edge in the subgraph,
1377 /// i.e. the iteration jumps over it.
1378 /// It is done by simply setting the assigned value of \c e
1379 /// to be \c false in the edge filter map.
1380 void hide(const Edge& e) const { Parent::hide(e); }
1382 /// \brief Shows the given node
1384 /// This function shows the given node in the subgraph.
1385 /// It is done by simply setting the assigned value of \c n
1386 /// to be \c true in the node filter map.
1387 void unHide(const Node& n) const { Parent::unHide(n); }
1389 /// \brief Shows the given edge
1391 /// This function shows the given edge in the subgraph.
1392 /// It is done by simply setting the assigned value of \c e
1393 /// to be \c true in the edge filter map.
1394 void unHide(const Edge& e) const { Parent::unHide(e); }
1396 /// \brief Returns \c true if the given node is hidden.
1398 /// This function returns \c true if the given node is hidden.
1399 bool hidden(const Node& n) const { return Parent::hidden(n); }
1401 /// \brief Returns \c true if the given edge is hidden.
1403 /// This function returns \c true if the given edge is hidden.
1404 bool hidden(const Edge& e) const { return Parent::hidden(e); }
1407 /// \brief Returns a read-only SubGraph adaptor
1409 /// This function just returns a read-only \ref SubGraph adaptor.
1410 /// \ingroup graph_adaptors
1411 /// \relates SubGraph
1412 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1413 SubGraph<const Graph, NodeFilterMap, ArcFilterMap>
1414 subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) {
1415 return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm);
1418 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1419 SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
1420 subGraph(const Graph& graph,
1421 const NodeFilterMap& nfm, ArcFilterMap& efm) {
1422 return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
1426 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1427 SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
1428 subGraph(const Graph& graph,
1429 NodeFilterMap& nfm, const ArcFilterMap& efm) {
1430 return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
1434 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1435 SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
1436 subGraph(const Graph& graph,
1437 const NodeFilterMap& nfm, const ArcFilterMap& efm) {
1438 return SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
1443 /// \ingroup graph_adaptors
1445 /// \brief Adaptor class for hiding nodes in a digraph or a graph.
1447 /// FilterNodes adaptor can be used for hiding nodes in a digraph or a
1448 /// graph. A \c bool node map must be specified, which defines the filter
1449 /// for the nodes. Only the nodes with \c true filter value and the
1450 /// arcs/edges incident to nodes both with \c true filter value are shown
1451 /// in the subgraph. This adaptor conforms to the \ref concepts::Digraph
1452 /// "Digraph" concept or the \ref concepts::Graph "Graph" concept
1453 /// depending on the \c _Graph template parameter.
1455 /// The adapted (di)graph can also be modified through this adaptor
1456 /// by adding or removing nodes or arcs/edges, unless the \c _Graph template
1457 /// parameter is set to be \c const.
1459 /// \tparam _Graph The type of the adapted digraph or graph.
1460 /// It must conform to the \ref concepts::Digraph "Digraph" concept
1461 /// or the \ref concepts::Graph "Graph" concept.
1462 /// It can also be specified to be \c const.
1463 /// \tparam _NodeFilterMap A \c bool (or convertible) node map of the
1464 /// adapted (di)graph. The default map type is
1465 /// \ref concepts::Graph::NodeMap "_Graph::NodeMap<bool>".
1466 /// \tparam _checked If this parameter is set to \c false then the arc/edge
1467 /// filtering is not checked with respect to the node filter. In this
1468 /// case only isolated nodes can be filtered out from the graph.
1469 /// Otherwise, each arc/edge that is incident to a hidden node is
1470 /// automatically filtered out. This is the default option.
1472 /// \note The \c Node and <tt>Arc/Edge</tt> types of this adaptor and the
1473 /// adapted (di)graph are convertible to each other.
1475 template<typename _Graph,
1476 typename _NodeFilterMap,
1479 template<typename _Digraph,
1480 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
1481 bool _checked = true,
1482 typename Enable = void>
1485 : public SubDigraph<_Digraph, _NodeFilterMap,
1486 ConstMap<typename _Digraph::Arc, bool>, _checked> {
1489 typedef _Digraph Digraph;
1490 typedef _NodeFilterMap NodeFilterMap;
1492 typedef SubDigraph<Digraph, NodeFilterMap,
1493 ConstMap<typename Digraph::Arc, bool>, _checked>
1496 typedef typename Parent::Node Node;
1499 ConstMap<typename Digraph::Arc, bool> const_true_map;
1501 FilterNodes() : const_true_map(true) {
1502 Parent::setArcFilterMap(const_true_map);
1507 /// \brief Constructor
1509 /// Creates a subgraph for the given digraph or graph with the
1510 /// given node filter map.
1512 FilterNodes(_Graph& graph, _NodeFilterMap& node_filter) :
1514 FilterNodes(Digraph& graph, NodeFilterMap& node_filter) :
1516 Parent(), const_true_map(true) {
1517 Parent::setDigraph(graph);
1518 Parent::setNodeFilterMap(node_filter);
1519 Parent::setArcFilterMap(const_true_map);
1522 /// \brief Hides the given node
1524 /// This function hides the given node in the subgraph,
1525 /// i.e. the iteration jumps over it.
1526 /// It is done by simply setting the assigned value of \c n
1527 /// to be \c false in the node filter map.
1528 void hide(const Node& n) const { Parent::hide(n); }
1530 /// \brief Shows the given node
1532 /// This function shows the given node in the subgraph.
1533 /// It is done by simply setting the assigned value of \c n
1534 /// to be \c true in the node filter map.
1535 void unHide(const Node& n) const { Parent::unHide(n); }
1537 /// \brief Returns \c true if the given node is hidden.
1539 /// This function returns \c true if the given node is hidden.
1540 bool hidden(const Node& n) const { return Parent::hidden(n); }
1544 template<typename _Graph, typename _NodeFilterMap, bool _checked>
1545 class FilterNodes<_Graph, _NodeFilterMap, _checked,
1546 typename enable_if<UndirectedTagIndicator<_Graph> >::type>
1547 : public SubGraph<_Graph, _NodeFilterMap,
1548 ConstMap<typename _Graph::Edge, bool>, _checked> {
1550 typedef _Graph Graph;
1551 typedef _NodeFilterMap NodeFilterMap;
1552 typedef SubGraph<Graph, NodeFilterMap,
1553 ConstMap<typename Graph::Edge, bool> > Parent;
1555 typedef typename Parent::Node Node;
1557 ConstMap<typename Graph::Edge, bool> const_true_map;
1559 FilterNodes() : const_true_map(true) {
1560 Parent::setEdgeFilterMap(const_true_map);
1565 FilterNodes(Graph& _graph, NodeFilterMap& node_filter_map) :
1566 Parent(), const_true_map(true) {
1567 Parent::setGraph(_graph);
1568 Parent::setNodeFilterMap(node_filter_map);
1569 Parent::setEdgeFilterMap(const_true_map);
1572 void hide(const Node& n) const { Parent::hide(n); }
1573 void unHide(const Node& n) const { Parent::unHide(n); }
1574 bool hidden(const Node& n) const { return Parent::hidden(n); }
1579 /// \brief Returns a read-only FilterNodes adaptor
1581 /// This function just returns a read-only \ref FilterNodes adaptor.
1582 /// \ingroup graph_adaptors
1583 /// \relates FilterNodes
1584 template<typename Digraph, typename NodeFilterMap>
1585 FilterNodes<const Digraph, NodeFilterMap>
1586 filterNodes(const Digraph& digraph, NodeFilterMap& nfm) {
1587 return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm);
1590 template<typename Digraph, typename NodeFilterMap>
1591 FilterNodes<const Digraph, const NodeFilterMap>
1592 filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) {
1593 return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm);
1596 /// \ingroup graph_adaptors
1598 /// \brief Adaptor class for hiding arcs in a digraph.
1600 /// FilterArcs adaptor can be used for hiding arcs in a digraph.
1601 /// A \c bool arc map must be specified, which defines the filter for
1602 /// the arcs. Only the arcs with \c true filter value are shown in the
1603 /// subdigraph. This adaptor conforms to the \ref concepts::Digraph
1604 /// "Digraph" concept.
1606 /// The adapted digraph can also be modified through this adaptor
1607 /// by adding or removing nodes or arcs, unless the \c _Digraph template
1608 /// parameter is set to be \c const.
1610 /// \tparam _Digraph The type of the adapted digraph.
1611 /// It must conform to the \ref concepts::Digraph "Digraph" concept.
1612 /// It can also be specified to be \c const.
1613 /// \tparam _ArcFilterMap A \c bool (or convertible) arc map of the
1614 /// adapted digraph. The default map type is
1615 /// \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<bool>".
1617 /// \note The \c Node and \c Arc types of this adaptor and the adapted
1618 /// digraph are convertible to each other.
1620 template<typename _Digraph,
1621 typename _ArcFilterMap>
1623 template<typename _Digraph,
1624 typename _ArcFilterMap = typename _Digraph::template ArcMap<bool> >
1627 public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>,
1628 _ArcFilterMap, false> {
1631 typedef _Digraph Digraph;
1632 typedef _ArcFilterMap ArcFilterMap;
1634 typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>,
1635 ArcFilterMap, false> Parent;
1637 typedef typename Parent::Arc Arc;
1640 ConstMap<typename Digraph::Node, bool> const_true_map;
1642 FilterArcs() : const_true_map(true) {
1643 Parent::setNodeFilterMap(const_true_map);
1648 /// \brief Constructor
1650 /// Creates a subdigraph for the given digraph with the given arc
1652 FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
1653 : Parent(), const_true_map(true) {
1654 Parent::setDigraph(digraph);
1655 Parent::setNodeFilterMap(const_true_map);
1656 Parent::setArcFilterMap(arc_filter);
1659 /// \brief Hides the given arc
1661 /// This function hides the given arc in the subdigraph,
1662 /// i.e. the iteration jumps over it.
1663 /// It is done by simply setting the assigned value of \c a
1664 /// to be \c false in the arc filter map.
1665 void hide(const Arc& a) const { Parent::hide(a); }
1667 /// \brief Shows the given arc
1669 /// This function shows the given arc in the subdigraph.
1670 /// It is done by simply setting the assigned value of \c a
1671 /// to be \c true in the arc filter map.
1672 void unHide(const Arc& a) const { Parent::unHide(a); }
1674 /// \brief Returns \c true if the given arc is hidden.
1676 /// This function returns \c true if the given arc is hidden.
1677 bool hidden(const Arc& a) const { return Parent::hidden(a); }
1681 /// \brief Returns a read-only FilterArcs adaptor
1683 /// This function just returns a read-only \ref FilterArcs adaptor.
1684 /// \ingroup graph_adaptors
1685 /// \relates FilterArcs
1686 template<typename Digraph, typename ArcFilterMap>
1687 FilterArcs<const Digraph, ArcFilterMap>
1688 filterArcs(const Digraph& digraph, ArcFilterMap& afm) {
1689 return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm);
1692 template<typename Digraph, typename ArcFilterMap>
1693 FilterArcs<const Digraph, const ArcFilterMap>
1694 filterArcs(const Digraph& digraph, const ArcFilterMap& afm) {
1695 return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm);
1698 /// \ingroup graph_adaptors
1700 /// \brief Adaptor class for hiding edges in a graph.
1702 /// FilterEdges adaptor can be used for hiding edges in a graph.
1703 /// A \c bool edge map must be specified, which defines the filter for
1704 /// the edges. Only the edges with \c true filter value are shown in the
1705 /// subgraph. This adaptor conforms to the \ref concepts::Graph
1706 /// "Graph" concept.
1708 /// The adapted graph can also be modified through this adaptor
1709 /// by adding or removing nodes or edges, unless the \c _Graph template
1710 /// parameter is set to be \c const.
1712 /// \tparam _Graph The type of the adapted graph.
1713 /// It must conform to the \ref concepts::Graph "Graph" concept.
1714 /// It can also be specified to be \c const.
1715 /// \tparam _EdgeFilterMap A \c bool (or convertible) edge map of the
1716 /// adapted graph. The default map type is
1717 /// \ref concepts::Graph::EdgeMap "_Graph::EdgeMap<bool>".
1719 /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the
1720 /// adapted graph are convertible to each other.
1722 template<typename _Graph,
1723 typename _EdgeFilterMap>
1725 template<typename _Graph,
1726 typename _EdgeFilterMap = typename _Graph::template EdgeMap<bool> >
1729 public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>,
1730 _EdgeFilterMap, false> {
1732 typedef _Graph Graph;
1733 typedef _EdgeFilterMap EdgeFilterMap;
1734 typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>,
1735 EdgeFilterMap, false> Parent;
1736 typedef typename Parent::Edge Edge;
1738 ConstMap<typename Graph::Node, bool> const_true_map;
1740 FilterEdges() : const_true_map(true) {
1741 Parent::setNodeFilterMap(const_true_map);
1746 /// \brief Constructor
1748 /// Creates a subgraph for the given graph with the given edge
1750 FilterEdges(Graph& graph, EdgeFilterMap& edge_filter_map) :
1751 Parent(), const_true_map(true) {
1752 Parent::setGraph(graph);
1753 Parent::setNodeFilterMap(const_true_map);
1754 Parent::setEdgeFilterMap(edge_filter_map);
1757 /// \brief Hides the given edge
1759 /// This function hides the given edge in the subgraph,
1760 /// i.e. the iteration jumps over it.
1761 /// It is done by simply setting the assigned value of \c e
1762 /// to be \c false in the edge filter map.
1763 void hide(const Edge& e) const { Parent::hide(e); }
1765 /// \brief Shows the given edge
1767 /// This function shows the given edge in the subgraph.
1768 /// It is done by simply setting the assigned value of \c e
1769 /// to be \c true in the edge filter map.
1770 void unHide(const Edge& e) const { Parent::unHide(e); }
1772 /// \brief Returns \c true if the given edge is hidden.
1774 /// This function returns \c true if the given edge is hidden.
1775 bool hidden(const Edge& e) const { return Parent::hidden(e); }
1779 /// \brief Returns a read-only FilterEdges adaptor
1781 /// This function just returns a read-only \ref FilterEdges adaptor.
1782 /// \ingroup graph_adaptors
1783 /// \relates FilterEdges
1784 template<typename Graph, typename EdgeFilterMap>
1785 FilterEdges<const Graph, EdgeFilterMap>
1786 filterEdges(const Graph& graph, EdgeFilterMap& efm) {
1787 return FilterEdges<const Graph, EdgeFilterMap>(graph, efm);
1790 template<typename Graph, typename EdgeFilterMap>
1791 FilterEdges<const Graph, const EdgeFilterMap>
1792 filterEdges(const Graph& graph, const EdgeFilterMap& efm) {
1793 return FilterEdges<const Graph, const EdgeFilterMap>(graph, efm);
1797 template <typename _Digraph>
1798 class UndirectorBase {
1800 typedef _Digraph Digraph;
1801 typedef UndirectorBase Adaptor;
1803 typedef True UndirectedTag;
1805 typedef typename Digraph::Arc Edge;
1806 typedef typename Digraph::Node Node;
1808 class Arc : public Edge {
1809 friend class UndirectorBase;
1813 Arc(const Edge& edge, bool forward) :
1814 Edge(edge), _forward(forward) {}
1819 Arc(Invalid) : Edge(INVALID), _forward(true) {}
1821 bool operator==(const Arc &other) const {
1822 return _forward == other._forward &&
1823 static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
1825 bool operator!=(const Arc &other) const {
1826 return _forward != other._forward ||
1827 static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
1829 bool operator<(const Arc &other) const {
1830 return _forward < other._forward ||
1831 (_forward == other._forward &&
1832 static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
1836 void first(Node& n) const {
1840 void next(Node& n) const {
1844 void first(Arc& a) const {
1849 void next(Arc& a) const {
1858 void first(Edge& e) const {
1862 void next(Edge& e) const {
1866 void firstOut(Arc& a, const Node& n) const {
1867 _digraph->firstIn(a, n);
1868 if( static_cast<const Edge&>(a) != INVALID ) {
1871 _digraph->firstOut(a, n);
1875 void nextOut(Arc &a) const {
1877 Node n = _digraph->target(a);
1878 _digraph->nextIn(a);
1879 if (static_cast<const Edge&>(a) == INVALID ) {
1880 _digraph->firstOut(a, n);
1885 _digraph->nextOut(a);
1889 void firstIn(Arc &a, const Node &n) const {
1890 _digraph->firstOut(a, n);
1891 if (static_cast<const Edge&>(a) != INVALID ) {
1894 _digraph->firstIn(a, n);
1898 void nextIn(Arc &a) const {
1900 Node n = _digraph->source(a);
1901 _digraph->nextOut(a);
1902 if( static_cast<const Edge&>(a) == INVALID ) {
1903 _digraph->firstIn(a, n);
1908 _digraph->nextIn(a);
1912 void firstInc(Edge &e, bool &d, const Node &n) const {
1914 _digraph->firstOut(e, n);
1915 if (e != INVALID) return;
1917 _digraph->firstIn(e, n);
1920 void nextInc(Edge &e, bool &d) const {
1922 Node s = _digraph->source(e);
1923 _digraph->nextOut(e);
1924 if (e != INVALID) return;
1926 _digraph->firstIn(e, s);
1928 _digraph->nextIn(e);
1932 Node u(const Edge& e) const {
1933 return _digraph->source(e);
1936 Node v(const Edge& e) const {
1937 return _digraph->target(e);
1940 Node source(const Arc &a) const {
1941 return a._forward ? _digraph->source(a) : _digraph->target(a);
1944 Node target(const Arc &a) const {
1945 return a._forward ? _digraph->target(a) : _digraph->source(a);
1948 static Arc direct(const Edge &e, bool d) {
1951 Arc direct(const Edge &e, const Node& n) const {
1952 return Arc(e, _digraph->source(e) == n);
1955 static bool direction(const Arc &a) { return a._forward; }
1957 Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
1958 Arc arcFromId(int ix) const {
1959 return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1));
1961 Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); }
1963 int id(const Node &n) const { return _digraph->id(n); }
1964 int id(const Arc &a) const {
1965 return (_digraph->id(a) << 1) | (a._forward ? 1 : 0);
1967 int id(const Edge &e) const { return _digraph->id(e); }
1969 int maxNodeId() const { return _digraph->maxNodeId(); }
1970 int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; }
1971 int maxEdgeId() const { return _digraph->maxArcId(); }
1973 Node addNode() { return _digraph->addNode(); }
1974 Edge addEdge(const Node& u, const Node& v) {
1975 return _digraph->addArc(u, v);
1978 void erase(const Node& i) { _digraph->erase(i); }
1979 void erase(const Edge& i) { _digraph->erase(i); }
1981 void clear() { _digraph->clear(); }
1983 typedef NodeNumTagIndicator<Digraph> NodeNumTag;
1984 int nodeNum() const { return _digraph->nodeNum(); }
1986 typedef ArcNumTagIndicator<Digraph> ArcNumTag;
1987 int arcNum() const { return 2 * _digraph->arcNum(); }
1989 typedef ArcNumTag EdgeNumTag;
1990 int edgeNum() const { return _digraph->arcNum(); }
1992 typedef FindArcTagIndicator<Digraph> FindArcTag;
1993 Arc findArc(Node s, Node t, Arc p = INVALID) const {
1995 Edge arc = _digraph->findArc(s, t);
1996 if (arc != INVALID) return direct(arc, true);
1997 arc = _digraph->findArc(t, s);
1998 if (arc != INVALID) return direct(arc, false);
1999 } else if (direction(p)) {
2000 Edge arc = _digraph->findArc(s, t, p);
2001 if (arc != INVALID) return direct(arc, true);
2002 arc = _digraph->findArc(t, s);
2003 if (arc != INVALID) return direct(arc, false);
2005 Edge arc = _digraph->findArc(t, s, p);
2006 if (arc != INVALID) return direct(arc, false);
2011 typedef FindArcTag FindEdgeTag;
2012 Edge findEdge(Node s, Node t, Edge p = INVALID) const {
2015 Edge arc = _digraph->findArc(s, t);
2016 if (arc != INVALID) return arc;
2017 arc = _digraph->findArc(t, s);
2018 if (arc != INVALID) return arc;
2019 } else if (_digraph->source(p) == s) {
2020 Edge arc = _digraph->findArc(s, t, p);
2021 if (arc != INVALID) return arc;
2022 arc = _digraph->findArc(t, s);
2023 if (arc != INVALID) return arc;
2025 Edge arc = _digraph->findArc(t, s, p);
2026 if (arc != INVALID) return arc;
2029 return _digraph->findArc(s, t, p);
2036 template <typename _Value>
2040 typedef typename Digraph::template ArcMap<_Value> MapImpl;
2044 typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
2046 typedef _Value Value;
2048 typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue;
2049 typedef typename MapTraits<MapImpl>::ReturnValue ReturnValue;
2050 typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReference;
2051 typedef typename MapTraits<MapImpl>::ReturnValue Reference;
2053 ArcMapBase(const Adaptor& adaptor) :
2054 _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
2056 ArcMapBase(const Adaptor& adaptor, const Value& v)
2057 : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}
2059 void set(const Arc& a, const Value& v) {
2063 _backward.set(a, v);
2067 ConstReturnValue operator[](const Arc& a) const {
2071 return _backward[a];
2075 ReturnValue operator[](const Arc& a) {
2079 return _backward[a];
2085 MapImpl _forward, _backward;
2091 template <typename _Value>
2092 class NodeMap : public Digraph::template NodeMap<_Value> {
2095 typedef _Value Value;
2096 typedef typename Digraph::template NodeMap<Value> Parent;
2098 explicit NodeMap(const Adaptor& adaptor)
2099 : Parent(*adaptor._digraph) {}
2101 NodeMap(const Adaptor& adaptor, const _Value& value)
2102 : Parent(*adaptor._digraph, value) { }
2105 NodeMap& operator=(const NodeMap& cmap) {
2106 return operator=<NodeMap>(cmap);
2109 template <typename CMap>
2110 NodeMap& operator=(const CMap& cmap) {
2111 Parent::operator=(cmap);
2117 template <typename _Value>
2119 : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
2122 typedef _Value Value;
2123 typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
2125 explicit ArcMap(const Adaptor& adaptor)
2126 : Parent(adaptor) {}
2128 ArcMap(const Adaptor& adaptor, const Value& value)
2129 : Parent(adaptor, value) {}
2132 ArcMap& operator=(const ArcMap& cmap) {
2133 return operator=<ArcMap>(cmap);
2136 template <typename CMap>
2137 ArcMap& operator=(const CMap& cmap) {
2138 Parent::operator=(cmap);
2143 template <typename _Value>
2144 class EdgeMap : public Digraph::template ArcMap<_Value> {
2147 typedef _Value Value;
2148 typedef typename Digraph::template ArcMap<Value> Parent;
2150 explicit EdgeMap(const Adaptor& adaptor)
2151 : Parent(*adaptor._digraph) {}
2153 EdgeMap(const Adaptor& adaptor, const Value& value)
2154 : Parent(*adaptor._digraph, value) {}
2157 EdgeMap& operator=(const EdgeMap& cmap) {
2158 return operator=<EdgeMap>(cmap);
2161 template <typename CMap>
2162 EdgeMap& operator=(const CMap& cmap) {
2163 Parent::operator=(cmap);
2169 typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
2170 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
2172 typedef typename ItemSetTraits<Digraph, Edge>::ItemNotifier EdgeNotifier;
2173 EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
2177 UndirectorBase() : _digraph(0) {}
2181 void setDigraph(Digraph& digraph) {
2182 _digraph = &digraph;
2187 /// \ingroup graph_adaptors
2189 /// \brief Adaptor class for viewing a digraph as an undirected graph.
2191 /// Undirector adaptor can be used for viewing a digraph as an undirected
2192 /// graph. All arcs of the underlying digraph are showed in the
2193 /// adaptor as an edge (and also as a pair of arcs, of course).
2194 /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
2196 /// The adapted digraph can also be modified through this adaptor
2197 /// by adding or removing nodes or edges, unless the \c _Digraph template
2198 /// parameter is set to be \c const.
2200 /// \tparam _Digraph The type of the adapted digraph.
2201 /// It must conform to the \ref concepts::Digraph "Digraph" concept.
2202 /// It can also be specified to be \c const.
2204 /// \note The \c Node type of this adaptor and the adapted digraph are
2205 /// convertible to each other, moreover the \c Edge type of the adaptor
2206 /// and the \c Arc type of the adapted digraph are also convertible to
2208 /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type
2209 /// of the adapted digraph.)
2210 template<typename _Digraph>
2212 : public GraphAdaptorExtender<UndirectorBase<_Digraph> > {
2214 typedef _Digraph Digraph;
2215 typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent;
2220 /// \brief Constructor
2222 /// Creates an undirected graph from the given digraph.
2223 Undirector(_Digraph& digraph) {
2224 setDigraph(digraph);
2227 /// \brief Arc map combined from two original arc maps
2229 /// This map adaptor class adapts two arc maps of the underlying
2230 /// digraph to get an arc map of the undirected graph.
2231 /// Its value type is inherited from the first arc map type
2232 /// (\c %ForwardMap).
2233 template <typename _ForwardMap, typename _BackwardMap>
2234 class CombinedArcMap {
2237 typedef _ForwardMap ForwardMap;
2238 typedef _BackwardMap BackwardMap;
2240 typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
2242 /// The key type of the map
2243 typedef typename Parent::Arc Key;
2244 /// The value type of the map
2245 typedef typename ForwardMap::Value Value;
2247 typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue;
2248 typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReturnValue;
2249 typedef typename MapTraits<ForwardMap>::ReturnValue Reference;
2250 typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference;
2253 CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
2254 : _forward(&forward), _backward(&backward) {}
2256 /// Sets the value associated with the given key.
2257 void set(const Key& e, const Value& a) {
2258 if (Parent::direction(e)) {
2259 _forward->set(e, a);
2261 _backward->set(e, a);
2265 /// Returns the value associated with the given key.
2266 ConstReturnValue operator[](const Key& e) const {
2267 if (Parent::direction(e)) {
2268 return (*_forward)[e];
2270 return (*_backward)[e];
2274 /// Returns a reference to the value associated with the given key.
2275 ReturnValue operator[](const Key& e) {
2276 if (Parent::direction(e)) {
2277 return (*_forward)[e];
2279 return (*_backward)[e];
2285 ForwardMap* _forward;
2286 BackwardMap* _backward;
2290 /// \brief Returns a combined arc map
2292 /// This function just returns a combined arc map.
2293 template <typename ForwardMap, typename BackwardMap>
2294 static CombinedArcMap<ForwardMap, BackwardMap>
2295 combinedArcMap(ForwardMap& forward, BackwardMap& backward) {
2296 return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward);
2299 template <typename ForwardMap, typename BackwardMap>
2300 static CombinedArcMap<const ForwardMap, BackwardMap>
2301 combinedArcMap(const ForwardMap& forward, BackwardMap& backward) {
2302 return CombinedArcMap<const ForwardMap,
2303 BackwardMap>(forward, backward);
2306 template <typename ForwardMap, typename BackwardMap>
2307 static CombinedArcMap<ForwardMap, const BackwardMap>
2308 combinedArcMap(ForwardMap& forward, const BackwardMap& backward) {
2309 return CombinedArcMap<ForwardMap,
2310 const BackwardMap>(forward, backward);
2313 template <typename ForwardMap, typename BackwardMap>
2314 static CombinedArcMap<const ForwardMap, const BackwardMap>
2315 combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) {
2316 return CombinedArcMap<const ForwardMap,
2317 const BackwardMap>(forward, backward);
2322 /// \brief Returns a read-only Undirector adaptor
2324 /// This function just returns a read-only \ref Undirector adaptor.
2325 /// \ingroup graph_adaptors
2326 /// \relates Undirector
2327 template<typename Digraph>
2328 Undirector<const Digraph>
2329 undirector(const Digraph& digraph) {
2330 return Undirector<const Digraph>(digraph);
2334 template <typename _Graph, typename _DirectionMap>
2335 class OrienterBase {
2338 typedef _Graph Graph;
2339 typedef _DirectionMap DirectionMap;
2341 typedef typename Graph::Node Node;
2342 typedef typename Graph::Edge Arc;
2344 void reverseArc(const Arc& arc) {
2345 _direction->set(arc, !(*_direction)[arc]);
2348 void first(Node& i) const { _graph->first(i); }
2349 void first(Arc& i) const { _graph->first(i); }
2350 void firstIn(Arc& i, const Node& n) const {
2352 _graph->firstInc(i, d, n);
2353 while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
2355 void firstOut(Arc& i, const Node& n ) const {
2357 _graph->firstInc(i, d, n);
2358 while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
2361 void next(Node& i) const { _graph->next(i); }
2362 void next(Arc& i) const { _graph->next(i); }
2363 void nextIn(Arc& i) const {
2364 bool d = !(*_direction)[i];
2365 _graph->nextInc(i, d);
2366 while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
2368 void nextOut(Arc& i) const {
2369 bool d = (*_direction)[i];
2370 _graph->nextInc(i, d);
2371 while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
2374 Node source(const Arc& e) const {
2375 return (*_direction)[e] ? _graph->u(e) : _graph->v(e);
2377 Node target(const Arc& e) const {
2378 return (*_direction)[e] ? _graph->v(e) : _graph->u(e);
2381 typedef NodeNumTagIndicator<Graph> NodeNumTag;
2382 int nodeNum() const { return _graph->nodeNum(); }
2384 typedef EdgeNumTagIndicator<Graph> ArcNumTag;
2385 int arcNum() const { return _graph->edgeNum(); }
2387 typedef FindEdgeTagIndicator<Graph> FindArcTag;
2388 Arc findArc(const Node& u, const Node& v,
2389 const Arc& prev = INVALID) const {
2390 Arc arc = _graph->findEdge(u, v, prev);
2391 while (arc != INVALID && source(arc) != u) {
2392 arc = _graph->findEdge(u, v, arc);
2398 return Node(_graph->addNode());
2401 Arc addArc(const Node& u, const Node& v) {
2402 Arc arc = _graph->addEdge(u, v);
2403 _direction->set(arc, _graph->u(arc) == u);
2407 void erase(const Node& i) { _graph->erase(i); }
2408 void erase(const Arc& i) { _graph->erase(i); }
2410 void clear() { _graph->clear(); }
2412 int id(const Node& v) const { return _graph->id(v); }
2413 int id(const Arc& e) const { return _graph->id(e); }
2415 Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
2416 Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
2418 int maxNodeId() const { return _graph->maxNodeId(); }
2419 int maxArcId() const { return _graph->maxEdgeId(); }
2421 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
2422 NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
2424 typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
2425 ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
2427 template <typename _Value>
2428 class NodeMap : public _Graph::template NodeMap<_Value> {
2431 typedef typename _Graph::template NodeMap<_Value> Parent;
2433 explicit NodeMap(const OrienterBase& adapter)
2434 : Parent(*adapter._graph) {}
2436 NodeMap(const OrienterBase& adapter, const _Value& value)
2437 : Parent(*adapter._graph, value) {}
2440 NodeMap& operator=(const NodeMap& cmap) {
2441 return operator=<NodeMap>(cmap);
2444 template <typename CMap>
2445 NodeMap& operator=(const CMap& cmap) {
2446 Parent::operator=(cmap);
2452 template <typename _Value>
2453 class ArcMap : public _Graph::template EdgeMap<_Value> {
2456 typedef typename Graph::template EdgeMap<_Value> Parent;
2458 explicit ArcMap(const OrienterBase& adapter)
2459 : Parent(*adapter._graph) { }
2461 ArcMap(const OrienterBase& adapter, const _Value& value)
2462 : Parent(*adapter._graph, value) { }
2465 ArcMap& operator=(const ArcMap& cmap) {
2466 return operator=<ArcMap>(cmap);
2469 template <typename CMap>
2470 ArcMap& operator=(const CMap& cmap) {
2471 Parent::operator=(cmap);
2480 DirectionMap* _direction;
2482 void setDirectionMap(DirectionMap& direction) {
2483 _direction = &direction;
2486 void setGraph(Graph& graph) {
2492 /// \ingroup graph_adaptors
2494 /// \brief Adaptor class for orienting the edges of a graph to get a digraph
2496 /// Orienter adaptor can be used for orienting the edges of a graph to
2497 /// get a digraph. A \c bool edge map of the underlying graph must be
2498 /// specified, which define the direction of the arcs in the adaptor.
2499 /// The arcs can be easily reversed by the \c reverseArc() member function
2501 /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
2503 /// The adapted graph can also be modified through this adaptor
2504 /// by adding or removing nodes or arcs, unless the \c _Graph template
2505 /// parameter is set to be \c const.
2507 /// \tparam _Graph The type of the adapted graph.
2508 /// It must conform to the \ref concepts::Graph "Graph" concept.
2509 /// It can also be specified to be \c const.
2510 /// \tparam _DirectionMap A \c bool (or convertible) edge map of the
2511 /// adapted graph. The default map type is
2512 /// \ref concepts::Graph::EdgeMap "_Graph::EdgeMap<bool>".
2514 /// \note The \c Node type of this adaptor and the adapted graph are
2515 /// convertible to each other, moreover the \c Arc type of the adaptor
2516 /// and the \c Edge type of the adapted graph are also convertible to
2519 template<typename _Graph,
2520 typename _DirectionMap>
2522 template<typename _Graph,
2523 typename _DirectionMap = typename _Graph::template EdgeMap<bool> >
2526 public DigraphAdaptorExtender<OrienterBase<_Graph, _DirectionMap> > {
2529 /// The type of the adapted graph.
2530 typedef _Graph Graph;
2531 /// The type of the direction edge map.
2532 typedef _DirectionMap DirectionMap;
2534 typedef DigraphAdaptorExtender<
2535 OrienterBase<_Graph, _DirectionMap> > Parent;
2536 typedef typename Parent::Arc Arc;
2541 /// \brief Constructor
2543 /// Constructor of the adaptor.
2544 Orienter(Graph& graph, DirectionMap& direction) {
2546 setDirectionMap(direction);
2549 /// \brief Reverses the given arc
2551 /// This function reverses the given arc.
2552 /// It is done by simply negate the assigned value of \c a
2553 /// in the direction map.
2554 void reverseArc(const Arc& a) {
2555 Parent::reverseArc(a);
2559 /// \brief Returns a read-only Orienter adaptor
2561 /// This function just returns a read-only \ref Orienter adaptor.
2562 /// \ingroup graph_adaptors
2563 /// \relates Orienter
2564 template<typename Graph, typename DirectionMap>
2565 Orienter<const Graph, DirectionMap>
2566 orienter(const Graph& graph, DirectionMap& dm) {
2567 return Orienter<const Graph, DirectionMap>(graph, dm);
2570 template<typename Graph, typename DirectionMap>
2571 Orienter<const Graph, const DirectionMap>
2572 orienter(const Graph& graph, const DirectionMap& dm) {
2573 return Orienter<const Graph, const DirectionMap>(graph, dm);
2576 namespace _adaptor_bits {
2578 template<typename _Digraph,
2579 typename _CapacityMap = typename _Digraph::template ArcMap<int>,
2580 typename _FlowMap = _CapacityMap,
2581 typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
2582 class ResForwardFilter {
2585 typedef _Digraph Digraph;
2586 typedef _CapacityMap CapacityMap;
2587 typedef _FlowMap FlowMap;
2588 typedef _Tolerance Tolerance;
2590 typedef typename Digraph::Arc Key;
2595 const CapacityMap* _capacity;
2596 const FlowMap* _flow;
2597 Tolerance _tolerance;
2600 ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,
2601 const Tolerance& tolerance = Tolerance())
2602 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
2604 bool operator[](const typename Digraph::Arc& a) const {
2605 return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
2609 template<typename _Digraph,
2610 typename _CapacityMap = typename _Digraph::template ArcMap<int>,
2611 typename _FlowMap = _CapacityMap,
2612 typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
2613 class ResBackwardFilter {
2616 typedef _Digraph Digraph;
2617 typedef _CapacityMap CapacityMap;
2618 typedef _FlowMap FlowMap;
2619 typedef _Tolerance Tolerance;
2621 typedef typename Digraph::Arc Key;
2626 const CapacityMap* _capacity;
2627 const FlowMap* _flow;
2628 Tolerance _tolerance;
2632 ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,
2633 const Tolerance& tolerance = Tolerance())
2634 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
2636 bool operator[](const typename Digraph::Arc& a) const {
2637 return _tolerance.positive((*_flow)[a]);
2643 /// \ingroup graph_adaptors
2645 /// \brief Adaptor class for composing the residual digraph for directed
2646 /// flow and circulation problems.
2648 /// Residual can be used for composing the \e residual digraph for directed
2649 /// flow and circulation problems. Let \f$ G=(V, A) \f$ be a directed graph
2650 /// and let \f$ F \f$ be a number type. Let \f$ flow, cap: A\to F \f$ be
2651 /// functions on the arcs.
2652 /// This adaptor implements a digraph structure with node set \f$ V \f$
2653 /// and arc set \f$ A_{forward}\cup A_{backward} \f$,
2654 /// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)<cap(uv)\} \f$ and
2655 /// \f$ A_{backward}=\{vu : uv\in A, flow(uv)>0\} \f$, i.e. the so
2656 /// called residual digraph.
2657 /// When the union \f$ A_{forward}\cup A_{backward} \f$ is taken,
2658 /// multiplicities are counted, i.e. the adaptor has exactly
2659 /// \f$ |A_{forward}| + |A_{backward}|\f$ arcs (it may have parallel
2661 /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
2663 /// \tparam _Digraph The type of the adapted digraph.
2664 /// It must conform to the \ref concepts::Digraph "Digraph" concept.
2665 /// It is implicitly \c const.
2666 /// \tparam _CapacityMap An arc map of some numerical type, which defines
2667 /// the capacities in the flow problem. It is implicitly \c const.
2668 /// The default map type is
2669 /// \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>".
2670 /// \tparam _FlowMap An arc map of some numerical type, which defines
2671 /// the flow values in the flow problem.
2672 /// The default map type is \c _CapacityMap.
2673 /// \tparam _Tolerance Tolerance type for handling inexact computation.
2674 /// The default tolerance type depends on the value type of the
2677 /// \note This adaptor is implemented using Undirector and FilterArcs
2680 /// \note The \c Node type of this adaptor and the adapted digraph are
2681 /// convertible to each other, moreover the \c Arc type of the adaptor
2682 /// is convertible to the \c Arc type of the adapted digraph.
2684 template<typename _Digraph,
2685 typename _CapacityMap,
2687 typename _Tolerance>
2690 template<typename _Digraph,
2691 typename _CapacityMap = typename _Digraph::template ArcMap<int>,
2692 typename _FlowMap = _CapacityMap,
2693 typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
2696 Undirector<const _Digraph>,
2697 typename Undirector<const _Digraph>::template CombinedArcMap<
2698 _adaptor_bits::ResForwardFilter<const _Digraph, _CapacityMap,
2699 _FlowMap, _Tolerance>,
2700 _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap,
2701 _FlowMap, _Tolerance> > >
2706 /// The type of the underlying digraph.
2707 typedef _Digraph Digraph;
2708 /// The type of the capacity map.
2709 typedef _CapacityMap CapacityMap;
2710 /// The type of the flow map.
2711 typedef _FlowMap FlowMap;
2712 typedef _Tolerance Tolerance;
2714 typedef typename CapacityMap::Value Value;
2715 typedef Residual Adaptor;
2719 typedef Undirector<const Digraph> Undirected;
2721 typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap,
2722 FlowMap, Tolerance> ForwardFilter;
2724 typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap,
2725 FlowMap, Tolerance> BackwardFilter;
2727 typedef typename Undirected::
2728 template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
2730 typedef FilterArcs<Undirected, ArcFilter> Parent;
2732 const CapacityMap* _capacity;
2736 ForwardFilter _forward_filter;
2737 BackwardFilter _backward_filter;
2738 ArcFilter _arc_filter;
2742 /// \brief Constructor
2744 /// Constructor of the residual digraph adaptor. The parameters are the
2745 /// digraph, the capacity map, the flow map, and a tolerance object.
2746 Residual(const Digraph& digraph, const CapacityMap& capacity,
2747 FlowMap& flow, const Tolerance& tolerance = Tolerance())
2748 : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
2749 _forward_filter(capacity, flow, tolerance),
2750 _backward_filter(capacity, flow, tolerance),
2751 _arc_filter(_forward_filter, _backward_filter)
2753 Parent::setDigraph(_graph);
2754 Parent::setArcFilterMap(_arc_filter);
2757 typedef typename Parent::Arc Arc;
2759 /// \brief Returns the residual capacity of the given arc.
2761 /// Returns the residual capacity of the given arc.
2762 Value residualCapacity(const Arc& a) const {
2763 if (Undirected::direction(a)) {
2764 return (*_capacity)[a] - (*_flow)[a];
2770 /// \brief Augment on the given arc in the residual digraph.
2772 /// Augment on the given arc in the residual digraph. It increases
2773 /// or decreases the flow value on the original arc according to the
2774 /// direction of the residual arc.
2775 void augment(const Arc& a, const Value& v) const {
2776 if (Undirected::direction(a)) {
2777 _flow->set(a, (*_flow)[a] + v);
2779 _flow->set(a, (*_flow)[a] - v);
2783 /// \brief Returns \c true if the given residual arc is a forward arc.
2785 /// Returns \c true if the given residual arc has the same orientation
2786 /// as the original arc, i.e. it is a so called forward arc.
2787 static bool forward(const Arc& a) {
2788 return Undirected::direction(a);
2791 /// \brief Returns \c true if the given residual arc is a backward arc.
2793 /// Returns \c true if the given residual arc has the opposite orientation
2794 /// than the original arc, i.e. it is a so called backward arc.
2795 static bool backward(const Arc& a) {
2796 return !Undirected::direction(a);
2799 /// \brief Returns the forward oriented residual arc.
2801 /// Returns the forward oriented residual arc related to the given
2802 /// arc of the underlying digraph.
2803 static Arc forward(const typename Digraph::Arc& a) {
2804 return Undirected::direct(a, true);
2807 /// \brief Returns the backward oriented residual arc.
2809 /// Returns the backward oriented residual arc related to the given
2810 /// arc of the underlying digraph.
2811 static Arc backward(const typename Digraph::Arc& a) {
2812 return Undirected::direct(a, false);
2815 /// \brief Residual capacity map.
2817 /// This map adaptor class can be used for obtaining the residual
2818 /// capacities as an arc map of the residual digraph.
2819 /// Its value type is inherited from the capacity map.
2820 class ResidualCapacity {
2822 const Adaptor* _adaptor;
2824 /// The key type of the map
2826 /// The value type of the map
2827 typedef typename _CapacityMap::Value Value;
2830 ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}
2832 /// Returns the value associated with the given residual arc
2833 Value operator[](const Arc& a) const {
2834 return _adaptor->residualCapacity(a);
2839 /// \brief Returns a residual capacity map
2841 /// This function just returns a residual capacity map.
2842 ResidualCapacity residualCapacity() const {
2843 return ResidualCapacity(*this);
2848 /// \brief Returns a (read-only) Residual adaptor
2850 /// This function just returns a (read-only) \ref Residual adaptor.
2851 /// \ingroup graph_adaptors
2852 /// \relates Residual
2853 template<typename Digraph, typename CapacityMap, typename FlowMap>
2854 Residual<Digraph, CapacityMap, FlowMap>
2855 residual(const Digraph& digraph,
2856 const CapacityMap& capacity,
2859 return Residual<Digraph, CapacityMap, FlowMap> (digraph, capacity, flow);
2863 template <typename _Digraph>
2864 class SplitNodesBase {
2867 typedef _Digraph Digraph;
2868 typedef DigraphAdaptorBase<const _Digraph> Parent;
2869 typedef SplitNodesBase Adaptor;
2871 typedef typename Digraph::Node DigraphNode;
2872 typedef typename Digraph::Arc DigraphArc;
2879 template <typename T> class NodeMapBase;
2880 template <typename T> class ArcMapBase;
2884 class Node : public DigraphNode {
2885 friend class SplitNodesBase;
2886 template <typename T> friend class NodeMapBase;
2890 Node(DigraphNode node, bool in)
2891 : DigraphNode(node), _in(in) {}
2896 Node(Invalid) : DigraphNode(INVALID), _in(true) {}
2898 bool operator==(const Node& node) const {
2899 return DigraphNode::operator==(node) && _in == node._in;
2902 bool operator!=(const Node& node) const {
2903 return !(*this == node);
2906 bool operator<(const Node& node) const {
2907 return DigraphNode::operator<(node) ||
2908 (DigraphNode::operator==(node) && _in < node._in);
2913 friend class SplitNodesBase;
2914 template <typename T> friend class ArcMapBase;
2916 typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;
2918 explicit Arc(const DigraphArc& arc) : _item(arc) {}
2919 explicit Arc(const DigraphNode& node) : _item(node) {}
2925 Arc(Invalid) : _item(DigraphArc(INVALID)) {}
2927 bool operator==(const Arc& arc) const {
2928 if (_item.firstState()) {
2929 if (arc._item.firstState()) {
2930 return _item.first() == arc._item.first();
2933 if (arc._item.secondState()) {
2934 return _item.second() == arc._item.second();
2940 bool operator!=(const Arc& arc) const {
2941 return !(*this == arc);
2944 bool operator<(const Arc& arc) const {
2945 if (_item.firstState()) {
2946 if (arc._item.firstState()) {
2947 return _item.first() < arc._item.first();
2951 if (arc._item.secondState()) {
2952 return _item.second() < arc._item.second();
2958 operator DigraphArc() const { return _item.first(); }
2959 operator DigraphNode() const { return _item.second(); }
2963 void first(Node& n) const {
2968 void next(Node& n) const {
2977 void first(Arc& e) const {
2978 e._item.setSecond();
2979 _digraph->first(e._item.second());
2980 if (e._item.second() == INVALID) {
2982 _digraph->first(e._item.first());
2986 void next(Arc& e) const {
2987 if (e._item.secondState()) {
2988 _digraph->next(e._item.second());
2989 if (e._item.second() == INVALID) {
2991 _digraph->first(e._item.first());
2994 _digraph->next(e._item.first());
2998 void firstOut(Arc& e, const Node& n) const {
3000 e._item.setSecond(n);
3003 _digraph->firstOut(e._item.first(), n);
3007 void nextOut(Arc& e) const {
3008 if (!e._item.firstState()) {
3009 e._item.setFirst(INVALID);
3011 _digraph->nextOut(e._item.first());
3015 void firstIn(Arc& e, const Node& n) const {
3017 e._item.setSecond(n);
3020 _digraph->firstIn(e._item.first(), n);
3024 void nextIn(Arc& e) const {
3025 if (!e._item.firstState()) {
3026 e._item.setFirst(INVALID);
3028 _digraph->nextIn(e._item.first());
3032 Node source(const Arc& e) const {
3033 if (e._item.firstState()) {
3034 return Node(_digraph->source(e._item.first()), false);
3036 return Node(e._item.second(), true);
3040 Node target(const Arc& e) const {
3041 if (e._item.firstState()) {
3042 return Node(_digraph->target(e._item.first()), true);
3044 return Node(e._item.second(), false);
3048 int id(const Node& n) const {
3049 return (_digraph->id(n) << 1) | (n._in ? 0 : 1);
3051 Node nodeFromId(int ix) const {
3052 return Node(_digraph->nodeFromId(ix >> 1), (ix & 1) == 0);
3054 int maxNodeId() const {
3055 return 2 * _digraph->maxNodeId() + 1;
3058 int id(const Arc& e) const {
3059 if (e._item.firstState()) {
3060 return _digraph->id(e._item.first()) << 1;
3062 return (_digraph->id(e._item.second()) << 1) | 1;
3065 Arc arcFromId(int ix) const {
3066 if ((ix & 1) == 0) {
3067 return Arc(_digraph->arcFromId(ix >> 1));
3069 return Arc(_digraph->nodeFromId(ix >> 1));
3072 int maxArcId() const {
3073 return std::max(_digraph->maxNodeId() << 1,
3074 (_digraph->maxArcId() << 1) | 1);
3077 static bool inNode(const Node& n) {
3081 static bool outNode(const Node& n) {
3085 static bool origArc(const Arc& e) {
3086 return e._item.firstState();
3089 static bool bindArc(const Arc& e) {
3090 return e._item.secondState();
3093 static Node inNode(const DigraphNode& n) {
3094 return Node(n, true);
3097 static Node outNode(const DigraphNode& n) {
3098 return Node(n, false);
3101 static Arc arc(const DigraphNode& n) {
3105 static Arc arc(const DigraphArc& e) {
3109 typedef True NodeNumTag;
3110 int nodeNum() const {
3111 return 2 * countNodes(*_digraph);
3114 typedef True ArcNumTag;
3115 int arcNum() const {
3116 return countArcs(*_digraph) + countNodes(*_digraph);
3119 typedef True FindArcTag;
3120 Arc findArc(const Node& u, const Node& v,
3121 const Arc& prev = INVALID) const {
3122 if (inNode(u) && outNode(v)) {
3123 if (static_cast<const DigraphNode&>(u) ==
3124 static_cast<const DigraphNode&>(v) && prev == INVALID) {
3128 else if (outNode(u) && inNode(v)) {
3129 return Arc(::lemon::findArc(*_digraph, u, v, prev));
3136 template <typename _Value>
3138 : public MapTraits<typename Parent::template NodeMap<_Value> > {
3139 typedef typename Parent::template NodeMap<_Value> NodeImpl;
3142 typedef _Value Value;
3143 typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag;
3144 typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue;
3145 typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReturnValue;
3146 typedef typename MapTraits<NodeImpl>::ReturnValue Reference;
3147 typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference;
3149 NodeMapBase(const Adaptor& adaptor)
3150 : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
3151 NodeMapBase(const Adaptor& adaptor, const Value& value)
3152 : _in_map(*adaptor._digraph, value),
3153 _out_map(*adaptor._digraph, value) {}
3155 void set(const Node& key, const Value& val) {
3156 if (Adaptor::inNode(key)) { _in_map.set(key, val); }
3157 else {_out_map.set(key, val); }
3160 ReturnValue operator[](const Node& key) {
3161 if (Adaptor::inNode(key)) { return _in_map[key]; }
3162 else { return _out_map[key]; }
3165 ConstReturnValue operator[](const Node& key) const {
3166 if (Adaptor::inNode(key)) { return _in_map[key]; }
3167 else { return _out_map[key]; }
3171 NodeImpl _in_map, _out_map;
3174 template <typename _Value>
3176 : public MapTraits<typename Parent::template ArcMap<_Value> > {
3177 typedef typename Parent::template ArcMap<_Value> ArcImpl;
3178 typedef typename Parent::template NodeMap<_Value> NodeImpl;
3181 typedef _Value Value;
3182 typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag;
3183 typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue;
3184 typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReturnValue;
3185 typedef typename MapTraits<ArcImpl>::ReturnValue Reference;
3186 typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference;
3188 ArcMapBase(const Adaptor& adaptor)
3189 : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
3190 ArcMapBase(const Adaptor& adaptor, const Value& value)
3191 : _arc_map(*adaptor._digraph, value),
3192 _node_map(*adaptor._digraph, value) {}
3194 void set(const Arc& key, const Value& val) {
3195 if (Adaptor::origArc(key)) {
3196 _arc_map.set(key._item.first(), val);
3198 _node_map.set(key._item.second(), val);
3202 ReturnValue operator[](const Arc& key) {
3203 if (Adaptor::origArc(key)) {
3204 return _arc_map[key._item.first()];
3206 return _node_map[key._item.second()];
3210 ConstReturnValue operator[](const Arc& key) const {
3211 if (Adaptor::origArc(key)) {
3212 return _arc_map[key._item.first()];
3214 return _node_map[key._item.second()];
3225 template <typename _Value>
3227 : public SubMapExtender<Adaptor, NodeMapBase<_Value> >
3230 typedef _Value Value;
3231 typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent;
3233 NodeMap(const Adaptor& adaptor)
3234 : Parent(adaptor) {}
3236 NodeMap(const Adaptor& adaptor, const Value& value)
3237 : Parent(adaptor, value) {}
3240 NodeMap& operator=(const NodeMap& cmap) {
3241 return operator=<NodeMap>(cmap);
3244 template <typename CMap>
3245 NodeMap& operator=(const CMap& cmap) {
3246 Parent::operator=(cmap);
3251 template <typename _Value>
3253 : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
3256 typedef _Value Value;
3257 typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
3259 ArcMap(const Adaptor& adaptor)
3260 : Parent(adaptor) {}
3262 ArcMap(const Adaptor& adaptor, const Value& value)
3263 : Parent(adaptor, value) {}
3266 ArcMap& operator=(const ArcMap& cmap) {
3267 return operator=<ArcMap>(cmap);
3270 template <typename CMap>
3271 ArcMap& operator=(const CMap& cmap) {
3272 Parent::operator=(cmap);
3279 SplitNodesBase() : _digraph(0) {}
3283 void setDigraph(Digraph& digraph) {
3284 _digraph = &digraph;
3289 /// \ingroup graph_adaptors
3291 /// \brief Adaptor class for splitting the nodes of a digraph.
3293 /// SplitNodes adaptor can be used for splitting each node into an
3294 /// \e in-node and an \e out-node in a digraph. Formaly, the adaptor
3295 /// replaces each node \f$ u \f$ in the digraph with two nodes,
3296 /// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$.
3297 /// If there is a \f$ (v, u) \f$ arc in the original digraph, then the
3298 /// new target of the arc will be \f$ u_{in} \f$ and similarly the
3299 /// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$.
3300 /// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$
3301 /// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph.
3303 /// The aim of this class is running an algorithm with respect to node
3304 /// costs or capacities if the algorithm considers only arc costs or
3305 /// capacities directly.
3306 /// In this case you can use \c SplitNodes adaptor, and set the node
3307 /// costs/capacities of the original digraph to the \e bind \e arcs
3310 /// \tparam _Digraph The type of the adapted digraph.
3311 /// It must conform to the \ref concepts::Digraph "Digraph" concept.
3312 /// It is implicitly \c const.
3314 /// \note The \c Node type of this adaptor is converible to the \c Node
3315 /// type of the adapted digraph.
3316 template <typename _Digraph>
3318 : public DigraphAdaptorExtender<SplitNodesBase<const _Digraph> > {
3320 typedef _Digraph Digraph;
3321 typedef DigraphAdaptorExtender<SplitNodesBase<const Digraph> > Parent;
3323 typedef typename Digraph::Node DigraphNode;
3324 typedef typename Digraph::Arc DigraphArc;
3326 typedef typename Parent::Node Node;
3327 typedef typename Parent::Arc Arc;
3329 /// \brief Constructor
3331 /// Constructor of the adaptor.
3332 SplitNodes(const Digraph& g) {
3333 Parent::setDigraph(g);
3336 /// \brief Returns \c true if the given node is an in-node.
3338 /// Returns \c true if the given node is an in-node.
3339 static bool inNode(const Node& n) {
3340 return Parent::inNode(n);
3343 /// \brief Returns \c true if the given node is an out-node.
3345 /// Returns \c true if the given node is an out-node.
3346 static bool outNode(const Node& n) {
3347 return Parent::outNode(n);
3350 /// \brief Returns \c true if the given arc is an original arc.
3352 /// Returns \c true if the given arc is one of the arcs in the
3353 /// original digraph.
3354 static bool origArc(const Arc& a) {
3355 return Parent::origArc(a);
3358 /// \brief Returns \c true if the given arc is a bind arc.
3360 /// Returns \c true if the given arc is a bind arc, i.e. it connects
3361 /// an in-node and an out-node.
3362 static bool bindArc(const Arc& a) {
3363 return Parent::bindArc(a);
3366 /// \brief Returns the in-node created from the given original node.
3368 /// Returns the in-node created from the given original node.
3369 static Node inNode(const DigraphNode& n) {
3370 return Parent::inNode(n);
3373 /// \brief Returns the out-node created from the given original node.
3375 /// Returns the out-node created from the given original node.
3376 static Node outNode(const DigraphNode& n) {
3377 return Parent::outNode(n);
3380 /// \brief Returns the bind arc that corresponds to the given
3383 /// Returns the bind arc in the adaptor that corresponds to the given
3384 /// original node, i.e. the arc connecting the in-node and out-node
3386 static Arc arc(const DigraphNode& n) {
3387 return Parent::arc(n);
3390 /// \brief Returns the arc that corresponds to the given original arc.
3392 /// Returns the arc in the adaptor that corresponds to the given
3394 static Arc arc(const DigraphArc& a) {
3395 return Parent::arc(a);
3398 /// \brief Node map combined from two original node maps
3400 /// This map adaptor class adapts two node maps of the original digraph
3401 /// to get a node map of the split digraph.
3402 /// Its value type is inherited from the first node map type
3404 template <typename InNodeMap, typename OutNodeMap>
3405 class CombinedNodeMap {
3408 /// The key type of the map
3410 /// The value type of the map
3411 typedef typename InNodeMap::Value Value;
3413 typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag;
3414 typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue;
3415 typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReturnValue;
3416 typedef typename MapTraits<InNodeMap>::ReturnValue Reference;
3417 typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference;
3420 CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
3421 : _in_map(in_map), _out_map(out_map) {}
3423 /// Returns the value associated with the given key.
3424 Value operator[](const Key& key) const {
3425 if (Parent::inNode(key)) {
3426 return _in_map[key];
3428 return _out_map[key];
3432 /// Returns a reference to the value associated with the given key.
3433 Value& operator[](const Key& key) {
3434 if (Parent::inNode(key)) {
3435 return _in_map[key];
3437 return _out_map[key];
3441 /// Sets the value associated with the given key.
3442 void set(const Key& key, const Value& value) {
3443 if (Parent::inNode(key)) {
3444 _in_map.set(key, value);
3446 _out_map.set(key, value);
3453 OutNodeMap& _out_map;
3458 /// \brief Returns a combined node map
3460 /// This function just returns a combined node map.
3461 template <typename InNodeMap, typename OutNodeMap>
3462 static CombinedNodeMap<InNodeMap, OutNodeMap>
3463 combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
3464 return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
3467 template <typename InNodeMap, typename OutNodeMap>
3468 static CombinedNodeMap<const InNodeMap, OutNodeMap>
3469 combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
3470 return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
3473 template <typename InNodeMap, typename OutNodeMap>
3474 static CombinedNodeMap<InNodeMap, const OutNodeMap>
3475 combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
3476 return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
3479 template <typename InNodeMap, typename OutNodeMap>
3480 static CombinedNodeMap<const InNodeMap, const OutNodeMap>
3481 combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
3482 return CombinedNodeMap<const InNodeMap,
3483 const OutNodeMap>(in_map, out_map);
3486 /// \brief Arc map combined from an arc map and a node map of the
3487 /// original digraph.
3489 /// This map adaptor class adapts an arc map and a node map of the
3490 /// original digraph to get an arc map of the split digraph.
3491 /// Its value type is inherited from the original arc map type
3492 /// (\c DigraphArcMap).
3493 template <typename DigraphArcMap, typename DigraphNodeMap>
3494 class CombinedArcMap {
3497 /// The key type of the map
3499 /// The value type of the map
3500 typedef typename DigraphArcMap::Value Value;
3502 typedef typename MapTraits<DigraphArcMap>::ReferenceMapTag
3504 typedef typename MapTraits<DigraphArcMap>::ReturnValue
3506 typedef typename MapTraits<DigraphArcMap>::ConstReturnValue
3508 typedef typename MapTraits<DigraphArcMap>::ReturnValue
3510 typedef typename MapTraits<DigraphArcMap>::ConstReturnValue
3514 CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)
3515 : _arc_map(arc_map), _node_map(node_map) {}
3517 /// Returns the value associated with the given key.
3518 Value operator[](const Key& arc) const {
3519 if (Parent::origArc(arc)) {
3520 return _arc_map[arc];
3522 return _node_map[arc];
3526 /// Returns a reference to the value associated with the given key.
3527 Value& operator[](const Key& arc) {
3528 if (Parent::origArc(arc)) {
3529 return _arc_map[arc];
3531 return _node_map[arc];
3535 /// Sets the value associated with the given key.
3536 void set(const Arc& arc, const Value& val) {
3537 if (Parent::origArc(arc)) {
3538 _arc_map.set(arc, val);
3540 _node_map.set(arc, val);
3545 DigraphArcMap& _arc_map;
3546 DigraphNodeMap& _node_map;
3549 /// \brief Returns a combined arc map
3551 /// This function just returns a combined arc map.
3552 template <typename DigraphArcMap, typename DigraphNodeMap>
3553 static CombinedArcMap<DigraphArcMap, DigraphNodeMap>
3554 combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
3555 return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map);
3558 template <typename DigraphArcMap, typename DigraphNodeMap>
3559 static CombinedArcMap<const DigraphArcMap, DigraphNodeMap>
3560 combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
3561 return CombinedArcMap<const DigraphArcMap,
3562 DigraphNodeMap>(arc_map, node_map);
3565 template <typename DigraphArcMap, typename DigraphNodeMap>
3566 static CombinedArcMap<DigraphArcMap, const DigraphNodeMap>
3567 combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) {
3568 return CombinedArcMap<DigraphArcMap,
3569 const DigraphNodeMap>(arc_map, node_map);
3572 template <typename DigraphArcMap, typename DigraphNodeMap>
3573 static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap>
3574 combinedArcMap(const DigraphArcMap& arc_map,
3575 const DigraphNodeMap& node_map) {
3576 return CombinedArcMap<const DigraphArcMap,
3577 const DigraphNodeMap>(arc_map, node_map);
3582 /// \brief Returns a (read-only) SplitNodes adaptor
3584 /// This function just returns a (read-only) \ref SplitNodes adaptor.
3585 /// \ingroup graph_adaptors
3586 /// \relates SplitNodes
3587 template<typename Digraph>
3589 splitNodes(const Digraph& digraph) {
3590 return SplitNodes<Digraph>(digraph);
3596 #endif //LEMON_ADAPTORS_H