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 status(const Node& n, bool v) const { _node_filter->set(n, v); }
478 void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
480 bool status(const Node& n) const { return (*_node_filter)[n]; }
481 bool status(const Arc& a) const { return (*_arc_filter)[a]; }
483 typedef False NodeNumTag;
484 typedef False ArcNumTag;
486 typedef FindArcTagIndicator<Digraph> FindArcTag;
487 Arc findArc(const Node& source, const Node& target,
488 const Arc& prev = INVALID) const {
489 if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
492 Arc arc = Parent::findArc(source, target, prev);
493 while (arc != INVALID && !(*_arc_filter)[arc]) {
494 arc = Parent::findArc(source, target, arc);
499 template <typename _Value>
500 class NodeMap : public SubMapExtender<Adaptor,
501 typename Parent::template NodeMap<_Value> > {
503 typedef _Value Value;
504 typedef SubMapExtender<Adaptor, typename Parent::
505 template NodeMap<Value> > MapParent;
507 NodeMap(const Adaptor& adaptor)
508 : MapParent(adaptor) {}
509 NodeMap(const Adaptor& adaptor, const Value& value)
510 : MapParent(adaptor, value) {}
513 NodeMap& operator=(const NodeMap& cmap) {
514 return operator=<NodeMap>(cmap);
517 template <typename CMap>
518 NodeMap& operator=(const CMap& cmap) {
519 MapParent::operator=(cmap);
524 template <typename _Value>
525 class ArcMap : public SubMapExtender<Adaptor,
526 typename Parent::template ArcMap<_Value> > {
528 typedef _Value Value;
529 typedef SubMapExtender<Adaptor, typename Parent::
530 template ArcMap<Value> > MapParent;
532 ArcMap(const Adaptor& adaptor)
533 : MapParent(adaptor) {}
534 ArcMap(const Adaptor& adaptor, const Value& value)
535 : MapParent(adaptor, value) {}
538 ArcMap& operator=(const ArcMap& cmap) {
539 return operator=<ArcMap>(cmap);
542 template <typename CMap>
543 ArcMap& operator=(const CMap& cmap) {
544 MapParent::operator=(cmap);
551 template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>
552 class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>
553 : public DigraphAdaptorBase<_Digraph> {
555 typedef _Digraph Digraph;
556 typedef _NodeFilterMap NodeFilterMap;
557 typedef _ArcFilterMap ArcFilterMap;
559 typedef SubDigraphBase Adaptor;
560 typedef DigraphAdaptorBase<Digraph> Parent;
562 NodeFilterMap* _node_filter;
563 ArcFilterMap* _arc_filter;
565 : Parent(), _node_filter(0), _arc_filter(0) { }
567 void setNodeFilterMap(NodeFilterMap& node_filter) {
568 _node_filter = &node_filter;
570 void setArcFilterMap(ArcFilterMap& arc_filter) {
571 _arc_filter = &arc_filter;
576 typedef typename Parent::Node Node;
577 typedef typename Parent::Arc Arc;
579 void first(Node& i) const {
581 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
584 void first(Arc& i) const {
586 while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
589 void firstIn(Arc& i, const Node& n) const {
590 Parent::firstIn(i, n);
591 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
594 void firstOut(Arc& i, const Node& n) const {
595 Parent::firstOut(i, n);
596 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
599 void next(Node& i) const {
601 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
603 void next(Arc& i) const {
605 while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
607 void nextIn(Arc& i) const {
609 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
612 void nextOut(Arc& i) const {
614 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
617 void status(const Node& n, bool v) const { _node_filter->set(n, v); }
618 void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
620 bool status(const Node& n) const { return (*_node_filter)[n]; }
621 bool status(const Arc& a) const { return (*_arc_filter)[a]; }
623 typedef False NodeNumTag;
624 typedef False ArcNumTag;
626 typedef FindArcTagIndicator<Digraph> FindArcTag;
627 Arc findArc(const Node& source, const Node& target,
628 const Arc& prev = INVALID) const {
629 if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
632 Arc arc = Parent::findArc(source, target, prev);
633 while (arc != INVALID && !(*_arc_filter)[arc]) {
634 arc = Parent::findArc(source, target, arc);
639 template <typename _Value>
640 class NodeMap : public SubMapExtender<Adaptor,
641 typename Parent::template NodeMap<_Value> > {
643 typedef _Value Value;
644 typedef SubMapExtender<Adaptor, typename Parent::
645 template NodeMap<Value> > MapParent;
647 NodeMap(const Adaptor& adaptor)
648 : MapParent(adaptor) {}
649 NodeMap(const Adaptor& adaptor, const Value& value)
650 : MapParent(adaptor, value) {}
653 NodeMap& operator=(const NodeMap& cmap) {
654 return operator=<NodeMap>(cmap);
657 template <typename CMap>
658 NodeMap& operator=(const CMap& cmap) {
659 MapParent::operator=(cmap);
664 template <typename _Value>
665 class ArcMap : public SubMapExtender<Adaptor,
666 typename Parent::template ArcMap<_Value> > {
668 typedef _Value Value;
669 typedef SubMapExtender<Adaptor, typename Parent::
670 template ArcMap<Value> > MapParent;
672 ArcMap(const Adaptor& adaptor)
673 : MapParent(adaptor) {}
674 ArcMap(const Adaptor& adaptor, const Value& value)
675 : MapParent(adaptor, value) {}
678 ArcMap& operator=(const ArcMap& cmap) {
679 return operator=<ArcMap>(cmap);
682 template <typename CMap>
683 ArcMap& operator=(const CMap& cmap) {
684 MapParent::operator=(cmap);
691 /// \ingroup graph_adaptors
693 /// \brief Adaptor class for hiding nodes and arcs in a digraph
695 /// SubDigraph can be used for hiding nodes and arcs in a digraph.
696 /// A \c bool node map and a \c bool arc map must be specified, which
697 /// define the filters for nodes and arcs.
698 /// Only the nodes and arcs with \c true filter value are
699 /// shown in the subdigraph. This adaptor conforms to the \ref
700 /// concepts::Digraph "Digraph" concept. If the \c _checked parameter
701 /// is \c true, then the arcs incident to hidden nodes are also
704 /// The adapted digraph can also be modified through this adaptor
705 /// by adding or removing nodes or arcs, unless the \c _Digraph template
706 /// parameter is set to be \c const.
708 /// \tparam _Digraph The type of the adapted digraph.
709 /// It must conform to the \ref concepts::Digraph "Digraph" concept.
710 /// It can also be specified to be \c const.
711 /// \tparam _NodeFilterMap A \c bool (or convertible) node map of the
712 /// adapted digraph. The default map type is
713 /// \ref concepts::Digraph::NodeMap "_Digraph::NodeMap<bool>".
714 /// \tparam _ArcFilterMap A \c bool (or convertible) arc map of the
715 /// adapted digraph. The default map type is
716 /// \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<bool>".
717 /// \tparam _checked If this parameter is set to \c false, then the arc
718 /// filtering is not checked with respect to the node filter.
719 /// Otherwise, each arc that is incident to a hidden node is automatically
720 /// filtered out. This is the default option.
722 /// \note The \c Node and \c Arc types of this adaptor and the adapted
723 /// digraph are convertible to each other.
728 template<typename _Digraph,
729 typename _NodeFilterMap,
730 typename _ArcFilterMap,
733 template<typename _Digraph,
734 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
735 typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,
736 bool _checked = true>
739 : public DigraphAdaptorExtender<
740 SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > {
742 /// The type of the adapted digraph.
743 typedef _Digraph Digraph;
744 /// The type of the node filter map.
745 typedef _NodeFilterMap NodeFilterMap;
746 /// The type of the arc filter map.
747 typedef _ArcFilterMap ArcFilterMap;
749 typedef DigraphAdaptorExtender<
750 SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> >
753 typedef typename Parent::Node Node;
754 typedef typename Parent::Arc Arc;
760 /// \brief Constructor
762 /// Creates a subdigraph for the given digraph with the
763 /// given node and arc filter maps.
764 SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,
765 ArcFilterMap& arc_filter) {
767 setNodeFilterMap(node_filter);
768 setArcFilterMap(arc_filter);
771 /// \brief Sets the status of the given node
773 /// This function sets the status of the given node.
774 /// It is done by simply setting the assigned value of \c n
775 /// to \c v in the node filter map.
776 void status(const Node& n, bool v) const { Parent::status(n, v); }
778 /// \brief Sets the status of the given arc
780 /// This function sets the status of the given arc.
781 /// It is done by simply setting the assigned value of \c a
782 /// to \c v in the arc filter map.
783 void status(const Arc& a, bool v) const { Parent::status(a, v); }
785 /// \brief Returns the status of the given node
787 /// This function returns the status of the given node.
788 /// It is \c true if the given node is enabled (i.e. not hidden).
789 bool status(const Node& n) const { return Parent::status(n); }
791 /// \brief Returns the status of the given arc
793 /// This function returns the status of the given arc.
794 /// It is \c true if the given arc is enabled (i.e. not hidden).
795 bool status(const Arc& a) const { return Parent::status(a); }
797 /// \brief Disables the given node
799 /// This function disables the given node in the subdigraph,
800 /// so the iteration jumps over it.
801 /// It is the same as \ref status() "status(n, false)".
802 void disable(const Node& n) const { Parent::status(n, false); }
804 /// \brief Disables the given arc
806 /// This function disables the given arc in the subdigraph,
807 /// so the iteration jumps over it.
808 /// It is the same as \ref status() "status(a, false)".
809 void disable(const Arc& a) const { Parent::status(a, false); }
811 /// \brief Enables the given node
813 /// This function enables the given node in the subdigraph.
814 /// It is the same as \ref status() "status(n, true)".
815 void enable(const Node& n) const { Parent::status(n, true); }
817 /// \brief Enables the given arc
819 /// This function enables the given arc in the subdigraph.
820 /// It is the same as \ref status() "status(a, true)".
821 void enable(const Arc& a) const { Parent::status(a, true); }
825 /// \brief Returns a read-only SubDigraph adaptor
827 /// This function just returns a read-only \ref SubDigraph adaptor.
828 /// \ingroup graph_adaptors
829 /// \relates SubDigraph
830 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
831 SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
832 subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) {
833 return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
837 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
838 SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
839 subDigraph(const Digraph& digraph,
840 const NodeFilterMap& nfm, ArcFilterMap& afm) {
841 return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
845 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
846 SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
847 subDigraph(const Digraph& digraph,
848 NodeFilterMap& nfm, const ArcFilterMap& afm) {
849 return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
853 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
854 SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap>
855 subDigraph(const Digraph& digraph,
856 const NodeFilterMap& nfm, const ArcFilterMap& afm) {
857 return SubDigraph<const Digraph, const NodeFilterMap,
858 const ArcFilterMap>(digraph, nfm, afm);
862 template <typename _Graph, typename _NodeFilterMap,
863 typename _EdgeFilterMap, bool _checked = true>
864 class SubGraphBase : public GraphAdaptorBase<_Graph> {
866 typedef _Graph Graph;
867 typedef _NodeFilterMap NodeFilterMap;
868 typedef _EdgeFilterMap EdgeFilterMap;
870 typedef SubGraphBase Adaptor;
871 typedef GraphAdaptorBase<_Graph> Parent;
874 NodeFilterMap* _node_filter_map;
875 EdgeFilterMap* _edge_filter_map;
878 : Parent(), _node_filter_map(0), _edge_filter_map(0) { }
880 void setNodeFilterMap(NodeFilterMap& node_filter_map) {
881 _node_filter_map=&node_filter_map;
883 void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
884 _edge_filter_map=&edge_filter_map;
889 typedef typename Parent::Node Node;
890 typedef typename Parent::Arc Arc;
891 typedef typename Parent::Edge Edge;
893 void first(Node& i) const {
895 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
898 void first(Arc& i) const {
900 while (i!=INVALID && (!(*_edge_filter_map)[i]
901 || !(*_node_filter_map)[Parent::source(i)]
902 || !(*_node_filter_map)[Parent::target(i)]))
906 void first(Edge& i) const {
908 while (i!=INVALID && (!(*_edge_filter_map)[i]
909 || !(*_node_filter_map)[Parent::u(i)]
910 || !(*_node_filter_map)[Parent::v(i)]))
914 void firstIn(Arc& i, const Node& n) const {
915 Parent::firstIn(i, n);
916 while (i!=INVALID && (!(*_edge_filter_map)[i]
917 || !(*_node_filter_map)[Parent::source(i)]))
921 void firstOut(Arc& i, const Node& n) const {
922 Parent::firstOut(i, n);
923 while (i!=INVALID && (!(*_edge_filter_map)[i]
924 || !(*_node_filter_map)[Parent::target(i)]))
928 void firstInc(Edge& i, bool& d, const Node& n) const {
929 Parent::firstInc(i, d, n);
930 while (i!=INVALID && (!(*_edge_filter_map)[i]
931 || !(*_node_filter_map)[Parent::u(i)]
932 || !(*_node_filter_map)[Parent::v(i)]))
933 Parent::nextInc(i, d);
936 void next(Node& i) const {
938 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
941 void next(Arc& i) const {
943 while (i!=INVALID && (!(*_edge_filter_map)[i]
944 || !(*_node_filter_map)[Parent::source(i)]
945 || !(*_node_filter_map)[Parent::target(i)]))
949 void next(Edge& i) const {
951 while (i!=INVALID && (!(*_edge_filter_map)[i]
952 || !(*_node_filter_map)[Parent::u(i)]
953 || !(*_node_filter_map)[Parent::v(i)]))
957 void nextIn(Arc& i) const {
959 while (i!=INVALID && (!(*_edge_filter_map)[i]
960 || !(*_node_filter_map)[Parent::source(i)]))
964 void nextOut(Arc& i) const {
966 while (i!=INVALID && (!(*_edge_filter_map)[i]
967 || !(*_node_filter_map)[Parent::target(i)]))
971 void nextInc(Edge& i, bool& d) const {
972 Parent::nextInc(i, d);
973 while (i!=INVALID && (!(*_edge_filter_map)[i]
974 || !(*_node_filter_map)[Parent::u(i)]
975 || !(*_node_filter_map)[Parent::v(i)]))
976 Parent::nextInc(i, d);
979 void status(const Node& n, bool v) const { _node_filter_map->set(n, v); }
980 void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); }
982 bool status(const Node& n) const { return (*_node_filter_map)[n]; }
983 bool status(const Edge& e) const { return (*_edge_filter_map)[e]; }
985 typedef False NodeNumTag;
986 typedef False ArcNumTag;
987 typedef False EdgeNumTag;
989 typedef FindArcTagIndicator<Graph> FindArcTag;
990 Arc findArc(const Node& u, const Node& v,
991 const Arc& prev = INVALID) const {
992 if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
995 Arc arc = Parent::findArc(u, v, prev);
996 while (arc != INVALID && !(*_edge_filter_map)[arc]) {
997 arc = Parent::findArc(u, v, arc);
1002 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1003 Edge findEdge(const Node& u, const Node& v,
1004 const Edge& prev = INVALID) const {
1005 if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
1008 Edge edge = Parent::findEdge(u, v, prev);
1009 while (edge != INVALID && !(*_edge_filter_map)[edge]) {
1010 edge = Parent::findEdge(u, v, edge);
1015 template <typename _Value>
1016 class NodeMap : public SubMapExtender<Adaptor,
1017 typename Parent::template NodeMap<_Value> > {
1019 typedef _Value Value;
1020 typedef SubMapExtender<Adaptor, typename Parent::
1021 template NodeMap<Value> > MapParent;
1023 NodeMap(const Adaptor& adaptor)
1024 : MapParent(adaptor) {}
1025 NodeMap(const Adaptor& adaptor, const Value& value)
1026 : MapParent(adaptor, value) {}
1029 NodeMap& operator=(const NodeMap& cmap) {
1030 return operator=<NodeMap>(cmap);
1033 template <typename CMap>
1034 NodeMap& operator=(const CMap& cmap) {
1035 MapParent::operator=(cmap);
1040 template <typename _Value>
1041 class ArcMap : public SubMapExtender<Adaptor,
1042 typename Parent::template ArcMap<_Value> > {
1044 typedef _Value Value;
1045 typedef SubMapExtender<Adaptor, typename Parent::
1046 template ArcMap<Value> > MapParent;
1048 ArcMap(const Adaptor& adaptor)
1049 : MapParent(adaptor) {}
1050 ArcMap(const Adaptor& adaptor, const Value& value)
1051 : MapParent(adaptor, value) {}
1054 ArcMap& operator=(const ArcMap& cmap) {
1055 return operator=<ArcMap>(cmap);
1058 template <typename CMap>
1059 ArcMap& operator=(const CMap& cmap) {
1060 MapParent::operator=(cmap);
1065 template <typename _Value>
1066 class EdgeMap : public SubMapExtender<Adaptor,
1067 typename Parent::template EdgeMap<_Value> > {
1069 typedef _Value Value;
1070 typedef SubMapExtender<Adaptor, typename Parent::
1071 template EdgeMap<Value> > MapParent;
1073 EdgeMap(const Adaptor& adaptor)
1074 : MapParent(adaptor) {}
1076 EdgeMap(const Adaptor& adaptor, const Value& value)
1077 : MapParent(adaptor, value) {}
1080 EdgeMap& operator=(const EdgeMap& cmap) {
1081 return operator=<EdgeMap>(cmap);
1084 template <typename CMap>
1085 EdgeMap& operator=(const CMap& cmap) {
1086 MapParent::operator=(cmap);
1093 template <typename _Graph, typename _NodeFilterMap, typename _EdgeFilterMap>
1094 class SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, false>
1095 : public GraphAdaptorBase<_Graph> {
1097 typedef _Graph Graph;
1098 typedef _NodeFilterMap NodeFilterMap;
1099 typedef _EdgeFilterMap EdgeFilterMap;
1101 typedef SubGraphBase Adaptor;
1102 typedef GraphAdaptorBase<_Graph> Parent;
1104 NodeFilterMap* _node_filter_map;
1105 EdgeFilterMap* _edge_filter_map;
1106 SubGraphBase() : Parent(),
1107 _node_filter_map(0), _edge_filter_map(0) { }
1109 void setNodeFilterMap(NodeFilterMap& node_filter_map) {
1110 _node_filter_map=&node_filter_map;
1112 void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
1113 _edge_filter_map=&edge_filter_map;
1118 typedef typename Parent::Node Node;
1119 typedef typename Parent::Arc Arc;
1120 typedef typename Parent::Edge Edge;
1122 void first(Node& i) const {
1124 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
1127 void first(Arc& i) const {
1129 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1132 void first(Edge& i) const {
1134 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1137 void firstIn(Arc& i, const Node& n) const {
1138 Parent::firstIn(i, n);
1139 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
1142 void firstOut(Arc& i, const Node& n) const {
1143 Parent::firstOut(i, n);
1144 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
1147 void firstInc(Edge& i, bool& d, const Node& n) const {
1148 Parent::firstInc(i, d, n);
1149 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
1152 void next(Node& i) const {
1154 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
1156 void next(Arc& i) const {
1158 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1160 void next(Edge& i) const {
1162 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1164 void nextIn(Arc& i) const {
1166 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
1169 void nextOut(Arc& i) const {
1171 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
1173 void nextInc(Edge& i, bool& d) const {
1174 Parent::nextInc(i, d);
1175 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
1178 void status(const Node& n, bool v) const { _node_filter_map->set(n, v); }
1179 void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); }
1181 bool status(const Node& n) const { return (*_node_filter_map)[n]; }
1182 bool status(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 Sets the status of the given node
1368 /// This function sets the status of the given node.
1369 /// It is done by simply setting the assigned value of \c n
1370 /// to \c v in the node filter map.
1371 void status(const Node& n, bool v) const { Parent::status(n, v); }
1373 /// \brief Sets the status of the given edge
1375 /// This function sets the status of the given edge.
1376 /// It is done by simply setting the assigned value of \c e
1377 /// to \c v in the edge filter map.
1378 void status(const Edge& e, bool v) const { Parent::status(e, v); }
1380 /// \brief Returns the status of the given node
1382 /// This function returns the status of the given node.
1383 /// It is \c true if the given node is enabled (i.e. not hidden).
1384 bool status(const Node& n) const { return Parent::status(n); }
1386 /// \brief Returns the status of the given edge
1388 /// This function returns the status of the given edge.
1389 /// It is \c true if the given edge is enabled (i.e. not hidden).
1390 bool status(const Edge& e) const { return Parent::status(e); }
1392 /// \brief Disables the given node
1394 /// This function disables the given node in the subdigraph,
1395 /// so the iteration jumps over it.
1396 /// It is the same as \ref status() "status(n, false)".
1397 void disable(const Node& n) const { Parent::status(n, false); }
1399 /// \brief Disables the given edge
1401 /// This function disables the given edge in the subgraph,
1402 /// so the iteration jumps over it.
1403 /// It is the same as \ref status() "status(e, false)".
1404 void disable(const Edge& e) const { Parent::status(e, false); }
1406 /// \brief Enables the given node
1408 /// This function enables the given node in the subdigraph.
1409 /// It is the same as \ref status() "status(n, true)".
1410 void enable(const Node& n) const { Parent::status(n, true); }
1412 /// \brief Enables the given edge
1414 /// This function enables the given edge in the subgraph.
1415 /// It is the same as \ref status() "status(e, true)".
1416 void enable(const Edge& e) const { Parent::status(e, true); }
1420 /// \brief Returns a read-only SubGraph adaptor
1422 /// This function just returns a read-only \ref SubGraph adaptor.
1423 /// \ingroup graph_adaptors
1424 /// \relates SubGraph
1425 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1426 SubGraph<const Graph, NodeFilterMap, ArcFilterMap>
1427 subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) {
1428 return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm);
1431 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1432 SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
1433 subGraph(const Graph& graph,
1434 const NodeFilterMap& nfm, ArcFilterMap& efm) {
1435 return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
1439 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1440 SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
1441 subGraph(const Graph& graph,
1442 NodeFilterMap& nfm, const ArcFilterMap& efm) {
1443 return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
1447 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1448 SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
1449 subGraph(const Graph& graph,
1450 const NodeFilterMap& nfm, const ArcFilterMap& efm) {
1451 return SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
1456 /// \ingroup graph_adaptors
1458 /// \brief Adaptor class for hiding nodes in a digraph or a graph.
1460 /// FilterNodes adaptor can be used for hiding nodes in a digraph or a
1461 /// graph. A \c bool node map must be specified, which defines the filter
1462 /// for the nodes. Only the nodes with \c true filter value and the
1463 /// arcs/edges incident to nodes both with \c true filter value are shown
1464 /// in the subgraph. This adaptor conforms to the \ref concepts::Digraph
1465 /// "Digraph" concept or the \ref concepts::Graph "Graph" concept
1466 /// depending on the \c _Graph template parameter.
1468 /// The adapted (di)graph can also be modified through this adaptor
1469 /// by adding or removing nodes or arcs/edges, unless the \c _Graph template
1470 /// parameter is set to be \c const.
1472 /// \tparam _Graph The type of the adapted digraph or graph.
1473 /// It must conform to the \ref concepts::Digraph "Digraph" concept
1474 /// or the \ref concepts::Graph "Graph" concept.
1475 /// It can also be specified to be \c const.
1476 /// \tparam _NodeFilterMap A \c bool (or convertible) node map of the
1477 /// adapted (di)graph. The default map type is
1478 /// \ref concepts::Graph::NodeMap "_Graph::NodeMap<bool>".
1479 /// \tparam _checked If this parameter is set to \c false then the arc/edge
1480 /// filtering is not checked with respect to the node filter. In this
1481 /// case only isolated nodes can be filtered out from the graph.
1482 /// Otherwise, each arc/edge that is incident to a hidden node is
1483 /// automatically filtered out. This is the default option.
1485 /// \note The \c Node and <tt>Arc/Edge</tt> types of this adaptor and the
1486 /// adapted (di)graph are convertible to each other.
1488 template<typename _Graph,
1489 typename _NodeFilterMap,
1492 template<typename _Digraph,
1493 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
1494 bool _checked = true,
1495 typename Enable = void>
1498 : public SubDigraph<_Digraph, _NodeFilterMap,
1499 ConstMap<typename _Digraph::Arc, bool>, _checked> {
1502 typedef _Digraph Digraph;
1503 typedef _NodeFilterMap NodeFilterMap;
1505 typedef SubDigraph<Digraph, NodeFilterMap,
1506 ConstMap<typename Digraph::Arc, bool>, _checked>
1509 typedef typename Parent::Node Node;
1512 ConstMap<typename Digraph::Arc, bool> const_true_map;
1514 FilterNodes() : const_true_map(true) {
1515 Parent::setArcFilterMap(const_true_map);
1520 /// \brief Constructor
1522 /// Creates a subgraph for the given digraph or graph with the
1523 /// given node filter map.
1525 FilterNodes(_Graph& graph, _NodeFilterMap& node_filter) :
1527 FilterNodes(Digraph& graph, NodeFilterMap& node_filter) :
1529 Parent(), const_true_map(true) {
1530 Parent::setDigraph(graph);
1531 Parent::setNodeFilterMap(node_filter);
1532 Parent::setArcFilterMap(const_true_map);
1535 /// \brief Sets the status of the given node
1537 /// This function sets the status of the given node.
1538 /// It is done by simply setting the assigned value of \c n
1539 /// to \c v in the node filter map.
1540 void status(const Node& n, bool v) const { Parent::status(n, v); }
1542 /// \brief Returns the status of the given node
1544 /// This function returns the status of the given node.
1545 /// It is \c true if the given node is enabled (i.e. not hidden).
1546 bool status(const Node& n) const { return Parent::status(n); }
1548 /// \brief Disables the given node
1550 /// This function disables the given node, so the iteration
1552 /// It is the same as \ref status() "status(n, false)".
1553 void disable(const Node& n) const { Parent::status(n, false); }
1555 /// \brief Enables the given node
1557 /// This function enables the given node.
1558 /// It is the same as \ref status() "status(n, true)".
1559 void enable(const Node& n) const { Parent::status(n, true); }
1563 template<typename _Graph, typename _NodeFilterMap, bool _checked>
1564 class FilterNodes<_Graph, _NodeFilterMap, _checked,
1565 typename enable_if<UndirectedTagIndicator<_Graph> >::type>
1566 : public SubGraph<_Graph, _NodeFilterMap,
1567 ConstMap<typename _Graph::Edge, bool>, _checked> {
1569 typedef _Graph Graph;
1570 typedef _NodeFilterMap NodeFilterMap;
1571 typedef SubGraph<Graph, NodeFilterMap,
1572 ConstMap<typename Graph::Edge, bool> > Parent;
1574 typedef typename Parent::Node Node;
1576 ConstMap<typename Graph::Edge, bool> const_true_map;
1578 FilterNodes() : const_true_map(true) {
1579 Parent::setEdgeFilterMap(const_true_map);
1584 FilterNodes(Graph& _graph, NodeFilterMap& node_filter_map) :
1585 Parent(), const_true_map(true) {
1586 Parent::setGraph(_graph);
1587 Parent::setNodeFilterMap(node_filter_map);
1588 Parent::setEdgeFilterMap(const_true_map);
1591 void status(const Node& n, bool v) const { Parent::status(n, v); }
1592 bool status(const Node& n) const { return Parent::status(n); }
1593 void disable(const Node& n) const { Parent::status(n, false); }
1594 void enable(const Node& n) const { Parent::status(n, true); }
1599 /// \brief Returns a read-only FilterNodes adaptor
1601 /// This function just returns a read-only \ref FilterNodes adaptor.
1602 /// \ingroup graph_adaptors
1603 /// \relates FilterNodes
1604 template<typename Digraph, typename NodeFilterMap>
1605 FilterNodes<const Digraph, NodeFilterMap>
1606 filterNodes(const Digraph& digraph, NodeFilterMap& nfm) {
1607 return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm);
1610 template<typename Digraph, typename NodeFilterMap>
1611 FilterNodes<const Digraph, const NodeFilterMap>
1612 filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) {
1613 return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm);
1616 /// \ingroup graph_adaptors
1618 /// \brief Adaptor class for hiding arcs in a digraph.
1620 /// FilterArcs adaptor can be used for hiding arcs in a digraph.
1621 /// A \c bool arc map must be specified, which defines the filter for
1622 /// the arcs. Only the arcs with \c true filter value are shown in the
1623 /// subdigraph. This adaptor conforms to the \ref concepts::Digraph
1624 /// "Digraph" concept.
1626 /// The adapted digraph can also be modified through this adaptor
1627 /// by adding or removing nodes or arcs, unless the \c _Digraph template
1628 /// parameter is set to be \c const.
1630 /// \tparam _Digraph The type of the adapted digraph.
1631 /// It must conform to the \ref concepts::Digraph "Digraph" concept.
1632 /// It can also be specified to be \c const.
1633 /// \tparam _ArcFilterMap A \c bool (or convertible) arc map of the
1634 /// adapted digraph. The default map type is
1635 /// \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<bool>".
1637 /// \note The \c Node and \c Arc types of this adaptor and the adapted
1638 /// digraph are convertible to each other.
1640 template<typename _Digraph,
1641 typename _ArcFilterMap>
1643 template<typename _Digraph,
1644 typename _ArcFilterMap = typename _Digraph::template ArcMap<bool> >
1647 public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>,
1648 _ArcFilterMap, false> {
1651 typedef _Digraph Digraph;
1652 typedef _ArcFilterMap ArcFilterMap;
1654 typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>,
1655 ArcFilterMap, false> Parent;
1657 typedef typename Parent::Arc Arc;
1660 ConstMap<typename Digraph::Node, bool> const_true_map;
1662 FilterArcs() : const_true_map(true) {
1663 Parent::setNodeFilterMap(const_true_map);
1668 /// \brief Constructor
1670 /// Creates a subdigraph for the given digraph with the given arc
1672 FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
1673 : Parent(), const_true_map(true) {
1674 Parent::setDigraph(digraph);
1675 Parent::setNodeFilterMap(const_true_map);
1676 Parent::setArcFilterMap(arc_filter);
1679 /// \brief Sets the status of the given arc
1681 /// This function sets the status of the given arc.
1682 /// It is done by simply setting the assigned value of \c a
1683 /// to \c v in the arc filter map.
1684 void status(const Arc& a, bool v) const { Parent::status(a, v); }
1686 /// \brief Returns the status of the given arc
1688 /// This function returns the status of the given arc.
1689 /// It is \c true if the given arc is enabled (i.e. not hidden).
1690 bool status(const Arc& a) const { return Parent::status(a); }
1692 /// \brief Disables the given arc
1694 /// This function disables the given arc in the subdigraph,
1695 /// so the iteration jumps over it.
1696 /// It is the same as \ref status() "status(a, false)".
1697 void disable(const Arc& a) const { Parent::status(a, false); }
1699 /// \brief Enables the given arc
1701 /// This function enables the given arc in the subdigraph.
1702 /// It is the same as \ref status() "status(a, true)".
1703 void enable(const Arc& a) const { Parent::status(a, true); }
1707 /// \brief Returns a read-only FilterArcs adaptor
1709 /// This function just returns a read-only \ref FilterArcs adaptor.
1710 /// \ingroup graph_adaptors
1711 /// \relates FilterArcs
1712 template<typename Digraph, typename ArcFilterMap>
1713 FilterArcs<const Digraph, ArcFilterMap>
1714 filterArcs(const Digraph& digraph, ArcFilterMap& afm) {
1715 return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm);
1718 template<typename Digraph, typename ArcFilterMap>
1719 FilterArcs<const Digraph, const ArcFilterMap>
1720 filterArcs(const Digraph& digraph, const ArcFilterMap& afm) {
1721 return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm);
1724 /// \ingroup graph_adaptors
1726 /// \brief Adaptor class for hiding edges in a graph.
1728 /// FilterEdges adaptor can be used for hiding edges in a graph.
1729 /// A \c bool edge map must be specified, which defines the filter for
1730 /// the edges. Only the edges with \c true filter value are shown in the
1731 /// subgraph. This adaptor conforms to the \ref concepts::Graph
1732 /// "Graph" concept.
1734 /// The adapted graph can also be modified through this adaptor
1735 /// by adding or removing nodes or edges, unless the \c _Graph template
1736 /// parameter is set to be \c const.
1738 /// \tparam _Graph The type of the adapted graph.
1739 /// It must conform to the \ref concepts::Graph "Graph" concept.
1740 /// It can also be specified to be \c const.
1741 /// \tparam _EdgeFilterMap A \c bool (or convertible) edge map of the
1742 /// adapted graph. The default map type is
1743 /// \ref concepts::Graph::EdgeMap "_Graph::EdgeMap<bool>".
1745 /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the
1746 /// adapted graph are convertible to each other.
1748 template<typename _Graph,
1749 typename _EdgeFilterMap>
1751 template<typename _Graph,
1752 typename _EdgeFilterMap = typename _Graph::template EdgeMap<bool> >
1755 public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>,
1756 _EdgeFilterMap, false> {
1758 typedef _Graph Graph;
1759 typedef _EdgeFilterMap EdgeFilterMap;
1760 typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>,
1761 EdgeFilterMap, false> Parent;
1762 typedef typename Parent::Edge Edge;
1764 ConstMap<typename Graph::Node, bool> const_true_map;
1766 FilterEdges() : const_true_map(true) {
1767 Parent::setNodeFilterMap(const_true_map);
1772 /// \brief Constructor
1774 /// Creates a subgraph for the given graph with the given edge
1776 FilterEdges(Graph& graph, EdgeFilterMap& edge_filter_map) :
1777 Parent(), const_true_map(true) {
1778 Parent::setGraph(graph);
1779 Parent::setNodeFilterMap(const_true_map);
1780 Parent::setEdgeFilterMap(edge_filter_map);
1783 /// \brief Sets the status of the given edge
1785 /// This function sets the status of the given edge.
1786 /// It is done by simply setting the assigned value of \c e
1787 /// to \c v in the edge filter map.
1788 void status(const Edge& e, bool v) const { Parent::status(e, v); }
1790 /// \brief Returns the status of the given edge
1792 /// This function returns the status of the given edge.
1793 /// It is \c true if the given edge is enabled (i.e. not hidden).
1794 bool status(const Edge& e) const { return Parent::status(e); }
1796 /// \brief Disables the given edge
1798 /// This function disables the given edge in the subgraph,
1799 /// so the iteration jumps over it.
1800 /// It is the same as \ref status() "status(e, false)".
1801 void disable(const Edge& e) const { Parent::status(e, false); }
1803 /// \brief Enables the given edge
1805 /// This function enables the given edge in the subgraph.
1806 /// It is the same as \ref status() "status(e, true)".
1807 void enable(const Edge& e) const { Parent::status(e, true); }
1811 /// \brief Returns a read-only FilterEdges adaptor
1813 /// This function just returns a read-only \ref FilterEdges adaptor.
1814 /// \ingroup graph_adaptors
1815 /// \relates FilterEdges
1816 template<typename Graph, typename EdgeFilterMap>
1817 FilterEdges<const Graph, EdgeFilterMap>
1818 filterEdges(const Graph& graph, EdgeFilterMap& efm) {
1819 return FilterEdges<const Graph, EdgeFilterMap>(graph, efm);
1822 template<typename Graph, typename EdgeFilterMap>
1823 FilterEdges<const Graph, const EdgeFilterMap>
1824 filterEdges(const Graph& graph, const EdgeFilterMap& efm) {
1825 return FilterEdges<const Graph, const EdgeFilterMap>(graph, efm);
1829 template <typename _Digraph>
1830 class UndirectorBase {
1832 typedef _Digraph Digraph;
1833 typedef UndirectorBase Adaptor;
1835 typedef True UndirectedTag;
1837 typedef typename Digraph::Arc Edge;
1838 typedef typename Digraph::Node Node;
1840 class Arc : public Edge {
1841 friend class UndirectorBase;
1845 Arc(const Edge& edge, bool forward) :
1846 Edge(edge), _forward(forward) {}
1851 Arc(Invalid) : Edge(INVALID), _forward(true) {}
1853 bool operator==(const Arc &other) const {
1854 return _forward == other._forward &&
1855 static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
1857 bool operator!=(const Arc &other) const {
1858 return _forward != other._forward ||
1859 static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
1861 bool operator<(const Arc &other) const {
1862 return _forward < other._forward ||
1863 (_forward == other._forward &&
1864 static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
1868 void first(Node& n) const {
1872 void next(Node& n) const {
1876 void first(Arc& a) const {
1881 void next(Arc& a) const {
1890 void first(Edge& e) const {
1894 void next(Edge& e) const {
1898 void firstOut(Arc& a, const Node& n) const {
1899 _digraph->firstIn(a, n);
1900 if( static_cast<const Edge&>(a) != INVALID ) {
1903 _digraph->firstOut(a, n);
1907 void nextOut(Arc &a) const {
1909 Node n = _digraph->target(a);
1910 _digraph->nextIn(a);
1911 if (static_cast<const Edge&>(a) == INVALID ) {
1912 _digraph->firstOut(a, n);
1917 _digraph->nextOut(a);
1921 void firstIn(Arc &a, const Node &n) const {
1922 _digraph->firstOut(a, n);
1923 if (static_cast<const Edge&>(a) != INVALID ) {
1926 _digraph->firstIn(a, n);
1930 void nextIn(Arc &a) const {
1932 Node n = _digraph->source(a);
1933 _digraph->nextOut(a);
1934 if( static_cast<const Edge&>(a) == INVALID ) {
1935 _digraph->firstIn(a, n);
1940 _digraph->nextIn(a);
1944 void firstInc(Edge &e, bool &d, const Node &n) const {
1946 _digraph->firstOut(e, n);
1947 if (e != INVALID) return;
1949 _digraph->firstIn(e, n);
1952 void nextInc(Edge &e, bool &d) const {
1954 Node s = _digraph->source(e);
1955 _digraph->nextOut(e);
1956 if (e != INVALID) return;
1958 _digraph->firstIn(e, s);
1960 _digraph->nextIn(e);
1964 Node u(const Edge& e) const {
1965 return _digraph->source(e);
1968 Node v(const Edge& e) const {
1969 return _digraph->target(e);
1972 Node source(const Arc &a) const {
1973 return a._forward ? _digraph->source(a) : _digraph->target(a);
1976 Node target(const Arc &a) const {
1977 return a._forward ? _digraph->target(a) : _digraph->source(a);
1980 static Arc direct(const Edge &e, bool d) {
1983 Arc direct(const Edge &e, const Node& n) const {
1984 return Arc(e, _digraph->source(e) == n);
1987 static bool direction(const Arc &a) { return a._forward; }
1989 Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
1990 Arc arcFromId(int ix) const {
1991 return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1));
1993 Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); }
1995 int id(const Node &n) const { return _digraph->id(n); }
1996 int id(const Arc &a) const {
1997 return (_digraph->id(a) << 1) | (a._forward ? 1 : 0);
1999 int id(const Edge &e) const { return _digraph->id(e); }
2001 int maxNodeId() const { return _digraph->maxNodeId(); }
2002 int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; }
2003 int maxEdgeId() const { return _digraph->maxArcId(); }
2005 Node addNode() { return _digraph->addNode(); }
2006 Edge addEdge(const Node& u, const Node& v) {
2007 return _digraph->addArc(u, v);
2010 void erase(const Node& i) { _digraph->erase(i); }
2011 void erase(const Edge& i) { _digraph->erase(i); }
2013 void clear() { _digraph->clear(); }
2015 typedef NodeNumTagIndicator<Digraph> NodeNumTag;
2016 int nodeNum() const { return _digraph->nodeNum(); }
2018 typedef ArcNumTagIndicator<Digraph> ArcNumTag;
2019 int arcNum() const { return 2 * _digraph->arcNum(); }
2021 typedef ArcNumTag EdgeNumTag;
2022 int edgeNum() const { return _digraph->arcNum(); }
2024 typedef FindArcTagIndicator<Digraph> FindArcTag;
2025 Arc findArc(Node s, Node t, Arc p = INVALID) const {
2027 Edge arc = _digraph->findArc(s, t);
2028 if (arc != INVALID) return direct(arc, true);
2029 arc = _digraph->findArc(t, s);
2030 if (arc != INVALID) return direct(arc, false);
2031 } else if (direction(p)) {
2032 Edge arc = _digraph->findArc(s, t, p);
2033 if (arc != INVALID) return direct(arc, true);
2034 arc = _digraph->findArc(t, s);
2035 if (arc != INVALID) return direct(arc, false);
2037 Edge arc = _digraph->findArc(t, s, p);
2038 if (arc != INVALID) return direct(arc, false);
2043 typedef FindArcTag FindEdgeTag;
2044 Edge findEdge(Node s, Node t, Edge p = INVALID) const {
2047 Edge arc = _digraph->findArc(s, t);
2048 if (arc != INVALID) return arc;
2049 arc = _digraph->findArc(t, s);
2050 if (arc != INVALID) return arc;
2051 } else if (_digraph->source(p) == s) {
2052 Edge arc = _digraph->findArc(s, t, p);
2053 if (arc != INVALID) return arc;
2054 arc = _digraph->findArc(t, s);
2055 if (arc != INVALID) return arc;
2057 Edge arc = _digraph->findArc(t, s, p);
2058 if (arc != INVALID) return arc;
2061 return _digraph->findArc(s, t, p);
2068 template <typename _Value>
2072 typedef typename Digraph::template ArcMap<_Value> MapImpl;
2076 typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
2078 typedef _Value Value;
2080 typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue;
2081 typedef typename MapTraits<MapImpl>::ReturnValue ReturnValue;
2082 typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReference;
2083 typedef typename MapTraits<MapImpl>::ReturnValue Reference;
2085 ArcMapBase(const Adaptor& adaptor) :
2086 _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
2088 ArcMapBase(const Adaptor& adaptor, const Value& v)
2089 : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}
2091 void set(const Arc& a, const Value& v) {
2095 _backward.set(a, v);
2099 ConstReturnValue operator[](const Arc& a) const {
2103 return _backward[a];
2107 ReturnValue operator[](const Arc& a) {
2111 return _backward[a];
2117 MapImpl _forward, _backward;
2123 template <typename _Value>
2124 class NodeMap : public Digraph::template NodeMap<_Value> {
2127 typedef _Value Value;
2128 typedef typename Digraph::template NodeMap<Value> Parent;
2130 explicit NodeMap(const Adaptor& adaptor)
2131 : Parent(*adaptor._digraph) {}
2133 NodeMap(const Adaptor& adaptor, const _Value& value)
2134 : Parent(*adaptor._digraph, value) { }
2137 NodeMap& operator=(const NodeMap& cmap) {
2138 return operator=<NodeMap>(cmap);
2141 template <typename CMap>
2142 NodeMap& operator=(const CMap& cmap) {
2143 Parent::operator=(cmap);
2149 template <typename _Value>
2151 : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
2154 typedef _Value Value;
2155 typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
2157 explicit ArcMap(const Adaptor& adaptor)
2158 : Parent(adaptor) {}
2160 ArcMap(const Adaptor& adaptor, const Value& value)
2161 : Parent(adaptor, value) {}
2164 ArcMap& operator=(const ArcMap& cmap) {
2165 return operator=<ArcMap>(cmap);
2168 template <typename CMap>
2169 ArcMap& operator=(const CMap& cmap) {
2170 Parent::operator=(cmap);
2175 template <typename _Value>
2176 class EdgeMap : public Digraph::template ArcMap<_Value> {
2179 typedef _Value Value;
2180 typedef typename Digraph::template ArcMap<Value> Parent;
2182 explicit EdgeMap(const Adaptor& adaptor)
2183 : Parent(*adaptor._digraph) {}
2185 EdgeMap(const Adaptor& adaptor, const Value& value)
2186 : Parent(*adaptor._digraph, value) {}
2189 EdgeMap& operator=(const EdgeMap& cmap) {
2190 return operator=<EdgeMap>(cmap);
2193 template <typename CMap>
2194 EdgeMap& operator=(const CMap& cmap) {
2195 Parent::operator=(cmap);
2201 typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
2202 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
2204 typedef typename ItemSetTraits<Digraph, Edge>::ItemNotifier EdgeNotifier;
2205 EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
2209 UndirectorBase() : _digraph(0) {}
2213 void setDigraph(Digraph& digraph) {
2214 _digraph = &digraph;
2219 /// \ingroup graph_adaptors
2221 /// \brief Adaptor class for viewing a digraph as an undirected graph.
2223 /// Undirector adaptor can be used for viewing a digraph as an undirected
2224 /// graph. All arcs of the underlying digraph are showed in the
2225 /// adaptor as an edge (and also as a pair of arcs, of course).
2226 /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
2228 /// The adapted digraph can also be modified through this adaptor
2229 /// by adding or removing nodes or edges, unless the \c _Digraph template
2230 /// parameter is set to be \c const.
2232 /// \tparam _Digraph The type of the adapted digraph.
2233 /// It must conform to the \ref concepts::Digraph "Digraph" concept.
2234 /// It can also be specified to be \c const.
2236 /// \note The \c Node type of this adaptor and the adapted digraph are
2237 /// convertible to each other, moreover the \c Edge type of the adaptor
2238 /// and the \c Arc type of the adapted digraph are also convertible to
2240 /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type
2241 /// of the adapted digraph.)
2242 template<typename _Digraph>
2244 : public GraphAdaptorExtender<UndirectorBase<_Digraph> > {
2246 typedef _Digraph Digraph;
2247 typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent;
2252 /// \brief Constructor
2254 /// Creates an undirected graph from the given digraph.
2255 Undirector(_Digraph& digraph) {
2256 setDigraph(digraph);
2259 /// \brief Arc map combined from two original arc maps
2261 /// This map adaptor class adapts two arc maps of the underlying
2262 /// digraph to get an arc map of the undirected graph.
2263 /// Its value type is inherited from the first arc map type
2264 /// (\c %ForwardMap).
2265 template <typename _ForwardMap, typename _BackwardMap>
2266 class CombinedArcMap {
2269 typedef _ForwardMap ForwardMap;
2270 typedef _BackwardMap BackwardMap;
2272 typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
2274 /// The key type of the map
2275 typedef typename Parent::Arc Key;
2276 /// The value type of the map
2277 typedef typename ForwardMap::Value Value;
2279 typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue;
2280 typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReturnValue;
2281 typedef typename MapTraits<ForwardMap>::ReturnValue Reference;
2282 typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference;
2285 CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
2286 : _forward(&forward), _backward(&backward) {}
2288 /// Sets the value associated with the given key.
2289 void set(const Key& e, const Value& a) {
2290 if (Parent::direction(e)) {
2291 _forward->set(e, a);
2293 _backward->set(e, a);
2297 /// Returns the value associated with the given key.
2298 ConstReturnValue operator[](const Key& e) const {
2299 if (Parent::direction(e)) {
2300 return (*_forward)[e];
2302 return (*_backward)[e];
2306 /// Returns a reference to the value associated with the given key.
2307 ReturnValue operator[](const Key& e) {
2308 if (Parent::direction(e)) {
2309 return (*_forward)[e];
2311 return (*_backward)[e];
2317 ForwardMap* _forward;
2318 BackwardMap* _backward;
2322 /// \brief Returns a combined arc map
2324 /// This function just returns a combined arc map.
2325 template <typename ForwardMap, typename BackwardMap>
2326 static CombinedArcMap<ForwardMap, BackwardMap>
2327 combinedArcMap(ForwardMap& forward, BackwardMap& backward) {
2328 return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward);
2331 template <typename ForwardMap, typename BackwardMap>
2332 static CombinedArcMap<const ForwardMap, BackwardMap>
2333 combinedArcMap(const ForwardMap& forward, BackwardMap& backward) {
2334 return CombinedArcMap<const ForwardMap,
2335 BackwardMap>(forward, backward);
2338 template <typename ForwardMap, typename BackwardMap>
2339 static CombinedArcMap<ForwardMap, const BackwardMap>
2340 combinedArcMap(ForwardMap& forward, const BackwardMap& backward) {
2341 return CombinedArcMap<ForwardMap,
2342 const BackwardMap>(forward, backward);
2345 template <typename ForwardMap, typename BackwardMap>
2346 static CombinedArcMap<const ForwardMap, const BackwardMap>
2347 combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) {
2348 return CombinedArcMap<const ForwardMap,
2349 const BackwardMap>(forward, backward);
2354 /// \brief Returns a read-only Undirector adaptor
2356 /// This function just returns a read-only \ref Undirector adaptor.
2357 /// \ingroup graph_adaptors
2358 /// \relates Undirector
2359 template<typename Digraph>
2360 Undirector<const Digraph>
2361 undirector(const Digraph& digraph) {
2362 return Undirector<const Digraph>(digraph);
2366 template <typename _Graph, typename _DirectionMap>
2367 class OrienterBase {
2370 typedef _Graph Graph;
2371 typedef _DirectionMap DirectionMap;
2373 typedef typename Graph::Node Node;
2374 typedef typename Graph::Edge Arc;
2376 void reverseArc(const Arc& arc) {
2377 _direction->set(arc, !(*_direction)[arc]);
2380 void first(Node& i) const { _graph->first(i); }
2381 void first(Arc& i) const { _graph->first(i); }
2382 void firstIn(Arc& i, const Node& n) const {
2384 _graph->firstInc(i, d, n);
2385 while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
2387 void firstOut(Arc& i, const Node& n ) const {
2389 _graph->firstInc(i, d, n);
2390 while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
2393 void next(Node& i) const { _graph->next(i); }
2394 void next(Arc& i) const { _graph->next(i); }
2395 void nextIn(Arc& i) const {
2396 bool d = !(*_direction)[i];
2397 _graph->nextInc(i, d);
2398 while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
2400 void nextOut(Arc& i) const {
2401 bool d = (*_direction)[i];
2402 _graph->nextInc(i, d);
2403 while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
2406 Node source(const Arc& e) const {
2407 return (*_direction)[e] ? _graph->u(e) : _graph->v(e);
2409 Node target(const Arc& e) const {
2410 return (*_direction)[e] ? _graph->v(e) : _graph->u(e);
2413 typedef NodeNumTagIndicator<Graph> NodeNumTag;
2414 int nodeNum() const { return _graph->nodeNum(); }
2416 typedef EdgeNumTagIndicator<Graph> ArcNumTag;
2417 int arcNum() const { return _graph->edgeNum(); }
2419 typedef FindEdgeTagIndicator<Graph> FindArcTag;
2420 Arc findArc(const Node& u, const Node& v,
2421 const Arc& prev = INVALID) const {
2422 Arc arc = _graph->findEdge(u, v, prev);
2423 while (arc != INVALID && source(arc) != u) {
2424 arc = _graph->findEdge(u, v, arc);
2430 return Node(_graph->addNode());
2433 Arc addArc(const Node& u, const Node& v) {
2434 Arc arc = _graph->addEdge(u, v);
2435 _direction->set(arc, _graph->u(arc) == u);
2439 void erase(const Node& i) { _graph->erase(i); }
2440 void erase(const Arc& i) { _graph->erase(i); }
2442 void clear() { _graph->clear(); }
2444 int id(const Node& v) const { return _graph->id(v); }
2445 int id(const Arc& e) const { return _graph->id(e); }
2447 Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
2448 Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
2450 int maxNodeId() const { return _graph->maxNodeId(); }
2451 int maxArcId() const { return _graph->maxEdgeId(); }
2453 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
2454 NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
2456 typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
2457 ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
2459 template <typename _Value>
2460 class NodeMap : public _Graph::template NodeMap<_Value> {
2463 typedef typename _Graph::template NodeMap<_Value> Parent;
2465 explicit NodeMap(const OrienterBase& adapter)
2466 : Parent(*adapter._graph) {}
2468 NodeMap(const OrienterBase& adapter, const _Value& value)
2469 : Parent(*adapter._graph, value) {}
2472 NodeMap& operator=(const NodeMap& cmap) {
2473 return operator=<NodeMap>(cmap);
2476 template <typename CMap>
2477 NodeMap& operator=(const CMap& cmap) {
2478 Parent::operator=(cmap);
2484 template <typename _Value>
2485 class ArcMap : public _Graph::template EdgeMap<_Value> {
2488 typedef typename Graph::template EdgeMap<_Value> Parent;
2490 explicit ArcMap(const OrienterBase& adapter)
2491 : Parent(*adapter._graph) { }
2493 ArcMap(const OrienterBase& adapter, const _Value& value)
2494 : Parent(*adapter._graph, value) { }
2497 ArcMap& operator=(const ArcMap& cmap) {
2498 return operator=<ArcMap>(cmap);
2501 template <typename CMap>
2502 ArcMap& operator=(const CMap& cmap) {
2503 Parent::operator=(cmap);
2512 DirectionMap* _direction;
2514 void setDirectionMap(DirectionMap& direction) {
2515 _direction = &direction;
2518 void setGraph(Graph& graph) {
2524 /// \ingroup graph_adaptors
2526 /// \brief Adaptor class for orienting the edges of a graph to get a digraph
2528 /// Orienter adaptor can be used for orienting the edges of a graph to
2529 /// get a digraph. A \c bool edge map of the underlying graph must be
2530 /// specified, which define the direction of the arcs in the adaptor.
2531 /// The arcs can be easily reversed by the \c reverseArc() member function
2533 /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
2535 /// The adapted graph can also be modified through this adaptor
2536 /// by adding or removing nodes or arcs, unless the \c _Graph template
2537 /// parameter is set to be \c const.
2539 /// \tparam _Graph The type of the adapted graph.
2540 /// It must conform to the \ref concepts::Graph "Graph" concept.
2541 /// It can also be specified to be \c const.
2542 /// \tparam _DirectionMap A \c bool (or convertible) edge map of the
2543 /// adapted graph. The default map type is
2544 /// \ref concepts::Graph::EdgeMap "_Graph::EdgeMap<bool>".
2546 /// \note The \c Node type of this adaptor and the adapted graph are
2547 /// convertible to each other, moreover the \c Arc type of the adaptor
2548 /// and the \c Edge type of the adapted graph are also convertible to
2551 template<typename _Graph,
2552 typename _DirectionMap>
2554 template<typename _Graph,
2555 typename _DirectionMap = typename _Graph::template EdgeMap<bool> >
2558 public DigraphAdaptorExtender<OrienterBase<_Graph, _DirectionMap> > {
2561 /// The type of the adapted graph.
2562 typedef _Graph Graph;
2563 /// The type of the direction edge map.
2564 typedef _DirectionMap DirectionMap;
2566 typedef DigraphAdaptorExtender<
2567 OrienterBase<_Graph, _DirectionMap> > Parent;
2568 typedef typename Parent::Arc Arc;
2573 /// \brief Constructor
2575 /// Constructor of the adaptor.
2576 Orienter(Graph& graph, DirectionMap& direction) {
2578 setDirectionMap(direction);
2581 /// \brief Reverses the given arc
2583 /// This function reverses the given arc.
2584 /// It is done by simply negate the assigned value of \c a
2585 /// in the direction map.
2586 void reverseArc(const Arc& a) {
2587 Parent::reverseArc(a);
2591 /// \brief Returns a read-only Orienter adaptor
2593 /// This function just returns a read-only \ref Orienter adaptor.
2594 /// \ingroup graph_adaptors
2595 /// \relates Orienter
2596 template<typename Graph, typename DirectionMap>
2597 Orienter<const Graph, DirectionMap>
2598 orienter(const Graph& graph, DirectionMap& dm) {
2599 return Orienter<const Graph, DirectionMap>(graph, dm);
2602 template<typename Graph, typename DirectionMap>
2603 Orienter<const Graph, const DirectionMap>
2604 orienter(const Graph& graph, const DirectionMap& dm) {
2605 return Orienter<const Graph, const DirectionMap>(graph, dm);
2608 namespace _adaptor_bits {
2610 template<typename _Digraph,
2611 typename _CapacityMap = typename _Digraph::template ArcMap<int>,
2612 typename _FlowMap = _CapacityMap,
2613 typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
2614 class ResForwardFilter {
2617 typedef _Digraph Digraph;
2618 typedef _CapacityMap CapacityMap;
2619 typedef _FlowMap FlowMap;
2620 typedef _Tolerance Tolerance;
2622 typedef typename Digraph::Arc Key;
2627 const CapacityMap* _capacity;
2628 const FlowMap* _flow;
2629 Tolerance _tolerance;
2632 ResForwardFilter(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((*_capacity)[a] - (*_flow)[a]);
2641 template<typename _Digraph,
2642 typename _CapacityMap = typename _Digraph::template ArcMap<int>,
2643 typename _FlowMap = _CapacityMap,
2644 typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
2645 class ResBackwardFilter {
2648 typedef _Digraph Digraph;
2649 typedef _CapacityMap CapacityMap;
2650 typedef _FlowMap FlowMap;
2651 typedef _Tolerance Tolerance;
2653 typedef typename Digraph::Arc Key;
2658 const CapacityMap* _capacity;
2659 const FlowMap* _flow;
2660 Tolerance _tolerance;
2664 ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,
2665 const Tolerance& tolerance = Tolerance())
2666 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
2668 bool operator[](const typename Digraph::Arc& a) const {
2669 return _tolerance.positive((*_flow)[a]);
2675 /// \ingroup graph_adaptors
2677 /// \brief Adaptor class for composing the residual digraph for directed
2678 /// flow and circulation problems.
2680 /// Residual can be used for composing the \e residual digraph for directed
2681 /// flow and circulation problems. Let \f$ G=(V, A) \f$ be a directed graph
2682 /// and let \f$ F \f$ be a number type. Let \f$ flow, cap: A\to F \f$ be
2683 /// functions on the arcs.
2684 /// This adaptor implements a digraph structure with node set \f$ V \f$
2685 /// and arc set \f$ A_{forward}\cup A_{backward} \f$,
2686 /// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)<cap(uv)\} \f$ and
2687 /// \f$ A_{backward}=\{vu : uv\in A, flow(uv)>0\} \f$, i.e. the so
2688 /// called residual digraph.
2689 /// When the union \f$ A_{forward}\cup A_{backward} \f$ is taken,
2690 /// multiplicities are counted, i.e. the adaptor has exactly
2691 /// \f$ |A_{forward}| + |A_{backward}|\f$ arcs (it may have parallel
2693 /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
2695 /// \tparam _Digraph The type of the adapted digraph.
2696 /// It must conform to the \ref concepts::Digraph "Digraph" concept.
2697 /// It is implicitly \c const.
2698 /// \tparam _CapacityMap An arc map of some numerical type, which defines
2699 /// the capacities in the flow problem. It is implicitly \c const.
2700 /// The default map type is
2701 /// \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>".
2702 /// \tparam _FlowMap An arc map of some numerical type, which defines
2703 /// the flow values in the flow problem.
2704 /// The default map type is \c _CapacityMap.
2705 /// \tparam _Tolerance Tolerance type for handling inexact computation.
2706 /// The default tolerance type depends on the value type of the
2709 /// \note This adaptor is implemented using Undirector and FilterArcs
2712 /// \note The \c Node type of this adaptor and the adapted digraph are
2713 /// convertible to each other, moreover the \c Arc type of the adaptor
2714 /// is convertible to the \c Arc type of the adapted digraph.
2716 template<typename _Digraph,
2717 typename _CapacityMap,
2719 typename _Tolerance>
2722 template<typename _Digraph,
2723 typename _CapacityMap = typename _Digraph::template ArcMap<int>,
2724 typename _FlowMap = _CapacityMap,
2725 typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
2728 Undirector<const _Digraph>,
2729 typename Undirector<const _Digraph>::template CombinedArcMap<
2730 _adaptor_bits::ResForwardFilter<const _Digraph, _CapacityMap,
2731 _FlowMap, _Tolerance>,
2732 _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap,
2733 _FlowMap, _Tolerance> > >
2738 /// The type of the underlying digraph.
2739 typedef _Digraph Digraph;
2740 /// The type of the capacity map.
2741 typedef _CapacityMap CapacityMap;
2742 /// The type of the flow map.
2743 typedef _FlowMap FlowMap;
2744 typedef _Tolerance Tolerance;
2746 typedef typename CapacityMap::Value Value;
2747 typedef Residual Adaptor;
2751 typedef Undirector<const Digraph> Undirected;
2753 typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap,
2754 FlowMap, Tolerance> ForwardFilter;
2756 typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap,
2757 FlowMap, Tolerance> BackwardFilter;
2759 typedef typename Undirected::
2760 template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
2762 typedef FilterArcs<Undirected, ArcFilter> Parent;
2764 const CapacityMap* _capacity;
2768 ForwardFilter _forward_filter;
2769 BackwardFilter _backward_filter;
2770 ArcFilter _arc_filter;
2774 /// \brief Constructor
2776 /// Constructor of the residual digraph adaptor. The parameters are the
2777 /// digraph, the capacity map, the flow map, and a tolerance object.
2778 Residual(const Digraph& digraph, const CapacityMap& capacity,
2779 FlowMap& flow, const Tolerance& tolerance = Tolerance())
2780 : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
2781 _forward_filter(capacity, flow, tolerance),
2782 _backward_filter(capacity, flow, tolerance),
2783 _arc_filter(_forward_filter, _backward_filter)
2785 Parent::setDigraph(_graph);
2786 Parent::setArcFilterMap(_arc_filter);
2789 typedef typename Parent::Arc Arc;
2791 /// \brief Returns the residual capacity of the given arc.
2793 /// Returns the residual capacity of the given arc.
2794 Value residualCapacity(const Arc& a) const {
2795 if (Undirected::direction(a)) {
2796 return (*_capacity)[a] - (*_flow)[a];
2802 /// \brief Augments on the given arc in the residual digraph.
2804 /// Augments on the given arc in the residual digraph. It increases
2805 /// or decreases the flow value on the original arc according to the
2806 /// direction of the residual arc.
2807 void augment(const Arc& a, const Value& v) const {
2808 if (Undirected::direction(a)) {
2809 _flow->set(a, (*_flow)[a] + v);
2811 _flow->set(a, (*_flow)[a] - v);
2815 /// \brief Returns \c true if the given residual arc is a forward arc.
2817 /// Returns \c true if the given residual arc has the same orientation
2818 /// as the original arc, i.e. it is a so called forward arc.
2819 static bool forward(const Arc& a) {
2820 return Undirected::direction(a);
2823 /// \brief Returns \c true if the given residual arc is a backward arc.
2825 /// Returns \c true if the given residual arc has the opposite orientation
2826 /// than the original arc, i.e. it is a so called backward arc.
2827 static bool backward(const Arc& a) {
2828 return !Undirected::direction(a);
2831 /// \brief Returns the forward oriented residual arc.
2833 /// Returns the forward oriented residual arc related to the given
2834 /// arc of the underlying digraph.
2835 static Arc forward(const typename Digraph::Arc& a) {
2836 return Undirected::direct(a, true);
2839 /// \brief Returns the backward oriented residual arc.
2841 /// Returns the backward oriented residual arc related to the given
2842 /// arc of the underlying digraph.
2843 static Arc backward(const typename Digraph::Arc& a) {
2844 return Undirected::direct(a, false);
2847 /// \brief Residual capacity map.
2849 /// This map adaptor class can be used for obtaining the residual
2850 /// capacities as an arc map of the residual digraph.
2851 /// Its value type is inherited from the capacity map.
2852 class ResidualCapacity {
2854 const Adaptor* _adaptor;
2856 /// The key type of the map
2858 /// The value type of the map
2859 typedef typename _CapacityMap::Value Value;
2862 ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}
2864 /// Returns the value associated with the given residual arc
2865 Value operator[](const Arc& a) const {
2866 return _adaptor->residualCapacity(a);
2871 /// \brief Returns a residual capacity map
2873 /// This function just returns a residual capacity map.
2874 ResidualCapacity residualCapacity() const {
2875 return ResidualCapacity(*this);
2880 /// \brief Returns a (read-only) Residual adaptor
2882 /// This function just returns a (read-only) \ref Residual adaptor.
2883 /// \ingroup graph_adaptors
2884 /// \relates Residual
2885 template<typename Digraph, typename CapacityMap, typename FlowMap>
2886 Residual<Digraph, CapacityMap, FlowMap>
2887 residual(const Digraph& digraph,
2888 const CapacityMap& capacity,
2891 return Residual<Digraph, CapacityMap, FlowMap> (digraph, capacity, flow);
2895 template <typename _Digraph>
2896 class SplitNodesBase {
2899 typedef _Digraph Digraph;
2900 typedef DigraphAdaptorBase<const _Digraph> Parent;
2901 typedef SplitNodesBase Adaptor;
2903 typedef typename Digraph::Node DigraphNode;
2904 typedef typename Digraph::Arc DigraphArc;
2911 template <typename T> class NodeMapBase;
2912 template <typename T> class ArcMapBase;
2916 class Node : public DigraphNode {
2917 friend class SplitNodesBase;
2918 template <typename T> friend class NodeMapBase;
2922 Node(DigraphNode node, bool in)
2923 : DigraphNode(node), _in(in) {}
2928 Node(Invalid) : DigraphNode(INVALID), _in(true) {}
2930 bool operator==(const Node& node) const {
2931 return DigraphNode::operator==(node) && _in == node._in;
2934 bool operator!=(const Node& node) const {
2935 return !(*this == node);
2938 bool operator<(const Node& node) const {
2939 return DigraphNode::operator<(node) ||
2940 (DigraphNode::operator==(node) && _in < node._in);
2945 friend class SplitNodesBase;
2946 template <typename T> friend class ArcMapBase;
2948 typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;
2950 explicit Arc(const DigraphArc& arc) : _item(arc) {}
2951 explicit Arc(const DigraphNode& node) : _item(node) {}
2957 Arc(Invalid) : _item(DigraphArc(INVALID)) {}
2959 bool operator==(const Arc& arc) const {
2960 if (_item.firstState()) {
2961 if (arc._item.firstState()) {
2962 return _item.first() == arc._item.first();
2965 if (arc._item.secondState()) {
2966 return _item.second() == arc._item.second();
2972 bool operator!=(const Arc& arc) const {
2973 return !(*this == arc);
2976 bool operator<(const Arc& arc) const {
2977 if (_item.firstState()) {
2978 if (arc._item.firstState()) {
2979 return _item.first() < arc._item.first();
2983 if (arc._item.secondState()) {
2984 return _item.second() < arc._item.second();
2990 operator DigraphArc() const { return _item.first(); }
2991 operator DigraphNode() const { return _item.second(); }
2995 void first(Node& n) const {
3000 void next(Node& n) const {
3009 void first(Arc& e) const {
3010 e._item.setSecond();
3011 _digraph->first(e._item.second());
3012 if (e._item.second() == INVALID) {
3014 _digraph->first(e._item.first());
3018 void next(Arc& e) const {
3019 if (e._item.secondState()) {
3020 _digraph->next(e._item.second());
3021 if (e._item.second() == INVALID) {
3023 _digraph->first(e._item.first());
3026 _digraph->next(e._item.first());
3030 void firstOut(Arc& e, const Node& n) const {
3032 e._item.setSecond(n);
3035 _digraph->firstOut(e._item.first(), n);
3039 void nextOut(Arc& e) const {
3040 if (!e._item.firstState()) {
3041 e._item.setFirst(INVALID);
3043 _digraph->nextOut(e._item.first());
3047 void firstIn(Arc& e, const Node& n) const {
3049 e._item.setSecond(n);
3052 _digraph->firstIn(e._item.first(), n);
3056 void nextIn(Arc& e) const {
3057 if (!e._item.firstState()) {
3058 e._item.setFirst(INVALID);
3060 _digraph->nextIn(e._item.first());
3064 Node source(const Arc& e) const {
3065 if (e._item.firstState()) {
3066 return Node(_digraph->source(e._item.first()), false);
3068 return Node(e._item.second(), true);
3072 Node target(const Arc& e) const {
3073 if (e._item.firstState()) {
3074 return Node(_digraph->target(e._item.first()), true);
3076 return Node(e._item.second(), false);
3080 int id(const Node& n) const {
3081 return (_digraph->id(n) << 1) | (n._in ? 0 : 1);
3083 Node nodeFromId(int ix) const {
3084 return Node(_digraph->nodeFromId(ix >> 1), (ix & 1) == 0);
3086 int maxNodeId() const {
3087 return 2 * _digraph->maxNodeId() + 1;
3090 int id(const Arc& e) const {
3091 if (e._item.firstState()) {
3092 return _digraph->id(e._item.first()) << 1;
3094 return (_digraph->id(e._item.second()) << 1) | 1;
3097 Arc arcFromId(int ix) const {
3098 if ((ix & 1) == 0) {
3099 return Arc(_digraph->arcFromId(ix >> 1));
3101 return Arc(_digraph->nodeFromId(ix >> 1));
3104 int maxArcId() const {
3105 return std::max(_digraph->maxNodeId() << 1,
3106 (_digraph->maxArcId() << 1) | 1);
3109 static bool inNode(const Node& n) {
3113 static bool outNode(const Node& n) {
3117 static bool origArc(const Arc& e) {
3118 return e._item.firstState();
3121 static bool bindArc(const Arc& e) {
3122 return e._item.secondState();
3125 static Node inNode(const DigraphNode& n) {
3126 return Node(n, true);
3129 static Node outNode(const DigraphNode& n) {
3130 return Node(n, false);
3133 static Arc arc(const DigraphNode& n) {
3137 static Arc arc(const DigraphArc& e) {
3141 typedef True NodeNumTag;
3142 int nodeNum() const {
3143 return 2 * countNodes(*_digraph);
3146 typedef True ArcNumTag;
3147 int arcNum() const {
3148 return countArcs(*_digraph) + countNodes(*_digraph);
3151 typedef True FindArcTag;
3152 Arc findArc(const Node& u, const Node& v,
3153 const Arc& prev = INVALID) const {
3154 if (inNode(u) && outNode(v)) {
3155 if (static_cast<const DigraphNode&>(u) ==
3156 static_cast<const DigraphNode&>(v) && prev == INVALID) {
3160 else if (outNode(u) && inNode(v)) {
3161 return Arc(::lemon::findArc(*_digraph, u, v, prev));
3168 template <typename _Value>
3170 : public MapTraits<typename Parent::template NodeMap<_Value> > {
3171 typedef typename Parent::template NodeMap<_Value> NodeImpl;
3174 typedef _Value Value;
3175 typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag;
3176 typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue;
3177 typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReturnValue;
3178 typedef typename MapTraits<NodeImpl>::ReturnValue Reference;
3179 typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference;
3181 NodeMapBase(const Adaptor& adaptor)
3182 : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
3183 NodeMapBase(const Adaptor& adaptor, const Value& value)
3184 : _in_map(*adaptor._digraph, value),
3185 _out_map(*adaptor._digraph, value) {}
3187 void set(const Node& key, const Value& val) {
3188 if (Adaptor::inNode(key)) { _in_map.set(key, val); }
3189 else {_out_map.set(key, val); }
3192 ReturnValue operator[](const Node& key) {
3193 if (Adaptor::inNode(key)) { return _in_map[key]; }
3194 else { return _out_map[key]; }
3197 ConstReturnValue operator[](const Node& key) const {
3198 if (Adaptor::inNode(key)) { return _in_map[key]; }
3199 else { return _out_map[key]; }
3203 NodeImpl _in_map, _out_map;
3206 template <typename _Value>
3208 : public MapTraits<typename Parent::template ArcMap<_Value> > {
3209 typedef typename Parent::template ArcMap<_Value> ArcImpl;
3210 typedef typename Parent::template NodeMap<_Value> NodeImpl;
3213 typedef _Value Value;
3214 typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag;
3215 typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue;
3216 typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReturnValue;
3217 typedef typename MapTraits<ArcImpl>::ReturnValue Reference;
3218 typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference;
3220 ArcMapBase(const Adaptor& adaptor)
3221 : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
3222 ArcMapBase(const Adaptor& adaptor, const Value& value)
3223 : _arc_map(*adaptor._digraph, value),
3224 _node_map(*adaptor._digraph, value) {}
3226 void set(const Arc& key, const Value& val) {
3227 if (Adaptor::origArc(key)) {
3228 _arc_map.set(key._item.first(), val);
3230 _node_map.set(key._item.second(), val);
3234 ReturnValue operator[](const Arc& key) {
3235 if (Adaptor::origArc(key)) {
3236 return _arc_map[key._item.first()];
3238 return _node_map[key._item.second()];
3242 ConstReturnValue operator[](const Arc& key) const {
3243 if (Adaptor::origArc(key)) {
3244 return _arc_map[key._item.first()];
3246 return _node_map[key._item.second()];
3257 template <typename _Value>
3259 : public SubMapExtender<Adaptor, NodeMapBase<_Value> >
3262 typedef _Value Value;
3263 typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent;
3265 NodeMap(const Adaptor& adaptor)
3266 : Parent(adaptor) {}
3268 NodeMap(const Adaptor& adaptor, const Value& value)
3269 : Parent(adaptor, value) {}
3272 NodeMap& operator=(const NodeMap& cmap) {
3273 return operator=<NodeMap>(cmap);
3276 template <typename CMap>
3277 NodeMap& operator=(const CMap& cmap) {
3278 Parent::operator=(cmap);
3283 template <typename _Value>
3285 : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
3288 typedef _Value Value;
3289 typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
3291 ArcMap(const Adaptor& adaptor)
3292 : Parent(adaptor) {}
3294 ArcMap(const Adaptor& adaptor, const Value& value)
3295 : Parent(adaptor, value) {}
3298 ArcMap& operator=(const ArcMap& cmap) {
3299 return operator=<ArcMap>(cmap);
3302 template <typename CMap>
3303 ArcMap& operator=(const CMap& cmap) {
3304 Parent::operator=(cmap);
3311 SplitNodesBase() : _digraph(0) {}
3315 void setDigraph(Digraph& digraph) {
3316 _digraph = &digraph;
3321 /// \ingroup graph_adaptors
3323 /// \brief Adaptor class for splitting the nodes of a digraph.
3325 /// SplitNodes adaptor can be used for splitting each node into an
3326 /// \e in-node and an \e out-node in a digraph. Formaly, the adaptor
3327 /// replaces each node \f$ u \f$ in the digraph with two nodes,
3328 /// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$.
3329 /// If there is a \f$ (v, u) \f$ arc in the original digraph, then the
3330 /// new target of the arc will be \f$ u_{in} \f$ and similarly the
3331 /// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$.
3332 /// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$
3333 /// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph.
3335 /// The aim of this class is running an algorithm with respect to node
3336 /// costs or capacities if the algorithm considers only arc costs or
3337 /// capacities directly.
3338 /// In this case you can use \c SplitNodes adaptor, and set the node
3339 /// costs/capacities of the original digraph to the \e bind \e arcs
3342 /// \tparam _Digraph The type of the adapted digraph.
3343 /// It must conform to the \ref concepts::Digraph "Digraph" concept.
3344 /// It is implicitly \c const.
3346 /// \note The \c Node type of this adaptor is converible to the \c Node
3347 /// type of the adapted digraph.
3348 template <typename _Digraph>
3350 : public DigraphAdaptorExtender<SplitNodesBase<const _Digraph> > {
3352 typedef _Digraph Digraph;
3353 typedef DigraphAdaptorExtender<SplitNodesBase<const Digraph> > Parent;
3355 typedef typename Digraph::Node DigraphNode;
3356 typedef typename Digraph::Arc DigraphArc;
3358 typedef typename Parent::Node Node;
3359 typedef typename Parent::Arc Arc;
3361 /// \brief Constructor
3363 /// Constructor of the adaptor.
3364 SplitNodes(const Digraph& g) {
3365 Parent::setDigraph(g);
3368 /// \brief Returns \c true if the given node is an in-node.
3370 /// Returns \c true if the given node is an in-node.
3371 static bool inNode(const Node& n) {
3372 return Parent::inNode(n);
3375 /// \brief Returns \c true if the given node is an out-node.
3377 /// Returns \c true if the given node is an out-node.
3378 static bool outNode(const Node& n) {
3379 return Parent::outNode(n);
3382 /// \brief Returns \c true if the given arc is an original arc.
3384 /// Returns \c true if the given arc is one of the arcs in the
3385 /// original digraph.
3386 static bool origArc(const Arc& a) {
3387 return Parent::origArc(a);
3390 /// \brief Returns \c true if the given arc is a bind arc.
3392 /// Returns \c true if the given arc is a bind arc, i.e. it connects
3393 /// an in-node and an out-node.
3394 static bool bindArc(const Arc& a) {
3395 return Parent::bindArc(a);
3398 /// \brief Returns the in-node created from the given original node.
3400 /// Returns the in-node created from the given original node.
3401 static Node inNode(const DigraphNode& n) {
3402 return Parent::inNode(n);
3405 /// \brief Returns the out-node created from the given original node.
3407 /// Returns the out-node created from the given original node.
3408 static Node outNode(const DigraphNode& n) {
3409 return Parent::outNode(n);
3412 /// \brief Returns the bind arc that corresponds to the given
3415 /// Returns the bind arc in the adaptor that corresponds to the given
3416 /// original node, i.e. the arc connecting the in-node and out-node
3418 static Arc arc(const DigraphNode& n) {
3419 return Parent::arc(n);
3422 /// \brief Returns the arc that corresponds to the given original arc.
3424 /// Returns the arc in the adaptor that corresponds to the given
3426 static Arc arc(const DigraphArc& a) {
3427 return Parent::arc(a);
3430 /// \brief Node map combined from two original node maps
3432 /// This map adaptor class adapts two node maps of the original digraph
3433 /// to get a node map of the split digraph.
3434 /// Its value type is inherited from the first node map type
3436 template <typename InNodeMap, typename OutNodeMap>
3437 class CombinedNodeMap {
3440 /// The key type of the map
3442 /// The value type of the map
3443 typedef typename InNodeMap::Value Value;
3445 typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag;
3446 typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue;
3447 typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReturnValue;
3448 typedef typename MapTraits<InNodeMap>::ReturnValue Reference;
3449 typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference;
3452 CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
3453 : _in_map(in_map), _out_map(out_map) {}
3455 /// Returns the value associated with the given key.
3456 Value operator[](const Key& key) const {
3457 if (Parent::inNode(key)) {
3458 return _in_map[key];
3460 return _out_map[key];
3464 /// Returns a reference to the value associated with the given key.
3465 Value& operator[](const Key& key) {
3466 if (Parent::inNode(key)) {
3467 return _in_map[key];
3469 return _out_map[key];
3473 /// Sets the value associated with the given key.
3474 void set(const Key& key, const Value& value) {
3475 if (Parent::inNode(key)) {
3476 _in_map.set(key, value);
3478 _out_map.set(key, value);
3485 OutNodeMap& _out_map;
3490 /// \brief Returns a combined node map
3492 /// This function just returns a combined node map.
3493 template <typename InNodeMap, typename OutNodeMap>
3494 static CombinedNodeMap<InNodeMap, OutNodeMap>
3495 combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
3496 return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
3499 template <typename InNodeMap, typename OutNodeMap>
3500 static CombinedNodeMap<const InNodeMap, OutNodeMap>
3501 combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
3502 return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
3505 template <typename InNodeMap, typename OutNodeMap>
3506 static CombinedNodeMap<InNodeMap, const OutNodeMap>
3507 combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
3508 return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
3511 template <typename InNodeMap, typename OutNodeMap>
3512 static CombinedNodeMap<const InNodeMap, const OutNodeMap>
3513 combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
3514 return CombinedNodeMap<const InNodeMap,
3515 const OutNodeMap>(in_map, out_map);
3518 /// \brief Arc map combined from an arc map and a node map of the
3519 /// original digraph.
3521 /// This map adaptor class adapts an arc map and a node map of the
3522 /// original digraph to get an arc map of the split digraph.
3523 /// Its value type is inherited from the original arc map type
3524 /// (\c DigraphArcMap).
3525 template <typename DigraphArcMap, typename DigraphNodeMap>
3526 class CombinedArcMap {
3529 /// The key type of the map
3531 /// The value type of the map
3532 typedef typename DigraphArcMap::Value Value;
3534 typedef typename MapTraits<DigraphArcMap>::ReferenceMapTag
3536 typedef typename MapTraits<DigraphArcMap>::ReturnValue
3538 typedef typename MapTraits<DigraphArcMap>::ConstReturnValue
3540 typedef typename MapTraits<DigraphArcMap>::ReturnValue
3542 typedef typename MapTraits<DigraphArcMap>::ConstReturnValue
3546 CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)
3547 : _arc_map(arc_map), _node_map(node_map) {}
3549 /// Returns the value associated with the given key.
3550 Value operator[](const Key& arc) const {
3551 if (Parent::origArc(arc)) {
3552 return _arc_map[arc];
3554 return _node_map[arc];
3558 /// Returns a reference to the value associated with the given key.
3559 Value& operator[](const Key& arc) {
3560 if (Parent::origArc(arc)) {
3561 return _arc_map[arc];
3563 return _node_map[arc];
3567 /// Sets the value associated with the given key.
3568 void set(const Arc& arc, const Value& val) {
3569 if (Parent::origArc(arc)) {
3570 _arc_map.set(arc, val);
3572 _node_map.set(arc, val);
3577 DigraphArcMap& _arc_map;
3578 DigraphNodeMap& _node_map;
3581 /// \brief Returns a combined arc map
3583 /// This function just returns a combined arc map.
3584 template <typename DigraphArcMap, typename DigraphNodeMap>
3585 static CombinedArcMap<DigraphArcMap, DigraphNodeMap>
3586 combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
3587 return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map);
3590 template <typename DigraphArcMap, typename DigraphNodeMap>
3591 static CombinedArcMap<const DigraphArcMap, DigraphNodeMap>
3592 combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
3593 return CombinedArcMap<const DigraphArcMap,
3594 DigraphNodeMap>(arc_map, node_map);
3597 template <typename DigraphArcMap, typename DigraphNodeMap>
3598 static CombinedArcMap<DigraphArcMap, const DigraphNodeMap>
3599 combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) {
3600 return CombinedArcMap<DigraphArcMap,
3601 const DigraphNodeMap>(arc_map, node_map);
3604 template <typename DigraphArcMap, typename DigraphNodeMap>
3605 static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap>
3606 combinedArcMap(const DigraphArcMap& arc_map,
3607 const DigraphNodeMap& node_map) {
3608 return CombinedArcMap<const DigraphArcMap,
3609 const DigraphNodeMap>(arc_map, node_map);
3614 /// \brief Returns a (read-only) SplitNodes adaptor
3616 /// This function just returns a (read-only) \ref SplitNodes adaptor.
3617 /// \ingroup graph_adaptors
3618 /// \relates SplitNodes
3619 template<typename Digraph>
3621 splitNodes(const Digraph& digraph) {
3622 return SplitNodes<Digraph>(digraph);
3628 #endif //LEMON_ADAPTORS_H