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 Several graph adaptors
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) {
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) const { _digraph->erase(n); }
85 void erase(const Arc& a) const { _digraph->erase(a); }
87 void clear() const { _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, const Arc& prev = INVALID) {
209 return _graph->findArc(u, v, prev);
212 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
213 Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) {
214 return _graph->findEdge(u, v, prev);
217 Node addNode() { return _graph->addNode(); }
218 Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }
220 void erase(const Node& i) { _graph->erase(i); }
221 void erase(const Edge& i) { _graph->erase(i); }
223 void clear() { _graph->clear(); }
225 bool direction(const Arc& a) const { return _graph->direction(a); }
226 Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); }
228 int id(const Node& v) const { return _graph->id(v); }
229 int id(const Arc& a) const { return _graph->id(a); }
230 int id(const Edge& e) const { return _graph->id(e); }
232 Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
233 Arc arcFromId(int ix) const { return _graph->arcFromId(ix); }
234 Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); }
236 int maxNodeId() const { return _graph->maxNodeId(); }
237 int maxArcId() const { return _graph->maxArcId(); }
238 int maxEdgeId() const { return _graph->maxEdgeId(); }
240 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
241 NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
243 typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
244 ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
246 typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
247 EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
249 template <typename _Value>
250 class NodeMap : public Graph::template NodeMap<_Value> {
252 typedef typename Graph::template NodeMap<_Value> Parent;
253 explicit NodeMap(const GraphAdaptorBase<Graph>& adapter)
254 : Parent(*adapter._graph) {}
255 NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
256 : Parent(*adapter._graph, value) {}
259 NodeMap& operator=(const NodeMap& cmap) {
260 return operator=<NodeMap>(cmap);
263 template <typename CMap>
264 NodeMap& operator=(const CMap& cmap) {
265 Parent::operator=(cmap);
271 template <typename _Value>
272 class ArcMap : public Graph::template ArcMap<_Value> {
274 typedef typename Graph::template ArcMap<_Value> Parent;
275 explicit ArcMap(const GraphAdaptorBase<Graph>& adapter)
276 : Parent(*adapter._graph) {}
277 ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
278 : Parent(*adapter._graph, value) {}
281 ArcMap& operator=(const ArcMap& cmap) {
282 return operator=<ArcMap>(cmap);
285 template <typename CMap>
286 ArcMap& operator=(const CMap& cmap) {
287 Parent::operator=(cmap);
292 template <typename _Value>
293 class EdgeMap : public Graph::template EdgeMap<_Value> {
295 typedef typename Graph::template EdgeMap<_Value> Parent;
296 explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)
297 : Parent(*adapter._graph) {}
298 EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
299 : Parent(*adapter._graph, value) {}
302 EdgeMap& operator=(const EdgeMap& cmap) {
303 return operator=<EdgeMap>(cmap);
306 template <typename CMap>
307 EdgeMap& operator=(const CMap& cmap) {
308 Parent::operator=(cmap);
315 template <typename _Digraph>
316 class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> {
318 typedef _Digraph Digraph;
319 typedef DigraphAdaptorBase<_Digraph> Parent;
321 ReverseDigraphBase() : Parent() { }
323 typedef typename Parent::Node Node;
324 typedef typename Parent::Arc Arc;
326 void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }
327 void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); }
329 void nextIn(Arc& a) const { Parent::nextOut(a); }
330 void nextOut(Arc& a) const { Parent::nextIn(a); }
332 Node source(const Arc& a) const { return Parent::target(a); }
333 Node target(const Arc& a) const { return Parent::source(a); }
335 Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
337 typedef FindArcTagIndicator<Digraph> FindArcTag;
338 Arc findArc(const Node& u, const Node& v,
339 const Arc& prev = INVALID) {
340 return Parent::findArc(v, u, prev);
345 /// \ingroup graph_adaptors
347 /// \brief A digraph adaptor which reverses the orientation of the arcs.
349 /// ReverseDigraph reverses the arcs in the adapted digraph. The
350 /// SubDigraph is conform to the \ref concepts::Digraph
351 /// "Digraph concept".
353 /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
354 /// "Digraph concept". The type can be specified to be const.
355 template<typename _Digraph>
356 class ReverseDigraph :
357 public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > {
359 typedef _Digraph Digraph;
360 typedef DigraphAdaptorExtender<
361 ReverseDigraphBase<_Digraph> > Parent;
366 /// \brief Constructor
368 /// Creates a reverse digraph adaptor for the given digraph
369 explicit ReverseDigraph(Digraph& digraph) {
370 Parent::setDigraph(digraph);
374 /// \brief Just gives back a reverse digraph adaptor
376 /// Just gives back a reverse digraph adaptor
377 template<typename Digraph>
378 ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) {
379 return ReverseDigraph<const Digraph>(digraph);
382 template <typename _Digraph, typename _NodeFilterMap,
383 typename _ArcFilterMap, bool _checked = true>
384 class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {
386 typedef _Digraph Digraph;
387 typedef _NodeFilterMap NodeFilterMap;
388 typedef _ArcFilterMap ArcFilterMap;
390 typedef SubDigraphBase Adaptor;
391 typedef DigraphAdaptorBase<_Digraph> Parent;
393 NodeFilterMap* _node_filter;
394 ArcFilterMap* _arc_filter;
396 : Parent(), _node_filter(0), _arc_filter(0) { }
398 void setNodeFilterMap(NodeFilterMap& node_filter) {
399 _node_filter = &node_filter;
401 void setArcFilterMap(ArcFilterMap& arc_filter) {
402 _arc_filter = &arc_filter;
407 typedef typename Parent::Node Node;
408 typedef typename Parent::Arc Arc;
410 void first(Node& i) const {
412 while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
415 void first(Arc& i) const {
417 while (i != INVALID && (!(*_arc_filter)[i]
418 || !(*_node_filter)[Parent::source(i)]
419 || !(*_node_filter)[Parent::target(i)]))
423 void firstIn(Arc& i, const Node& n) const {
424 Parent::firstIn(i, n);
425 while (i != INVALID && (!(*_arc_filter)[i]
426 || !(*_node_filter)[Parent::source(i)]))
430 void firstOut(Arc& i, const Node& n) const {
431 Parent::firstOut(i, n);
432 while (i != INVALID && (!(*_arc_filter)[i]
433 || !(*_node_filter)[Parent::target(i)]))
437 void next(Node& i) const {
439 while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
442 void next(Arc& i) const {
444 while (i != INVALID && (!(*_arc_filter)[i]
445 || !(*_node_filter)[Parent::source(i)]
446 || !(*_node_filter)[Parent::target(i)]))
450 void nextIn(Arc& i) const {
452 while (i != INVALID && (!(*_arc_filter)[i]
453 || !(*_node_filter)[Parent::source(i)]))
457 void nextOut(Arc& i) const {
459 while (i != INVALID && (!(*_arc_filter)[i]
460 || !(*_node_filter)[Parent::target(i)]))
464 void hide(const Node& n) const { _node_filter->set(n, false); }
465 void hide(const Arc& a) const { _arc_filter->set(a, false); }
467 void unHide(const Node& n) const { _node_filter->set(n, true); }
468 void unHide(const Arc& a) const { _arc_filter->set(a, true); }
470 bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
471 bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }
473 typedef False NodeNumTag;
474 typedef False ArcNumTag;
476 typedef FindArcTagIndicator<Digraph> FindArcTag;
477 Arc findArc(const Node& source, const Node& target,
478 const Arc& prev = INVALID) {
479 if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
482 Arc arc = Parent::findArc(source, target, prev);
483 while (arc != INVALID && !(*_arc_filter)[arc]) {
484 arc = Parent::findArc(source, target, arc);
489 template <typename _Value>
490 class NodeMap : public SubMapExtender<Adaptor,
491 typename Parent::template NodeMap<_Value> > {
493 typedef _Value Value;
494 typedef SubMapExtender<Adaptor, typename Parent::
495 template NodeMap<Value> > MapParent;
497 NodeMap(const Adaptor& adaptor)
498 : MapParent(adaptor) {}
499 NodeMap(const Adaptor& adaptor, const Value& value)
500 : MapParent(adaptor, value) {}
503 NodeMap& operator=(const NodeMap& cmap) {
504 return operator=<NodeMap>(cmap);
507 template <typename CMap>
508 NodeMap& operator=(const CMap& cmap) {
509 MapParent::operator=(cmap);
514 template <typename _Value>
515 class ArcMap : public SubMapExtender<Adaptor,
516 typename Parent::template ArcMap<_Value> > {
518 typedef _Value Value;
519 typedef SubMapExtender<Adaptor, typename Parent::
520 template ArcMap<Value> > MapParent;
522 ArcMap(const Adaptor& adaptor)
523 : MapParent(adaptor) {}
524 ArcMap(const Adaptor& adaptor, const Value& value)
525 : MapParent(adaptor, value) {}
528 ArcMap& operator=(const ArcMap& cmap) {
529 return operator=<ArcMap>(cmap);
532 template <typename CMap>
533 ArcMap& operator=(const CMap& cmap) {
534 MapParent::operator=(cmap);
541 template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>
542 class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>
543 : public DigraphAdaptorBase<_Digraph> {
545 typedef _Digraph Digraph;
546 typedef _NodeFilterMap NodeFilterMap;
547 typedef _ArcFilterMap ArcFilterMap;
549 typedef SubDigraphBase Adaptor;
550 typedef DigraphAdaptorBase<Digraph> Parent;
552 NodeFilterMap* _node_filter;
553 ArcFilterMap* _arc_filter;
555 : Parent(), _node_filter(0), _arc_filter(0) { }
557 void setNodeFilterMap(NodeFilterMap& node_filter) {
558 _node_filter = &node_filter;
560 void setArcFilterMap(ArcFilterMap& arc_filter) {
561 _arc_filter = &arc_filter;
566 typedef typename Parent::Node Node;
567 typedef typename Parent::Arc Arc;
569 void first(Node& i) const {
571 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
574 void first(Arc& i) const {
576 while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
579 void firstIn(Arc& i, const Node& n) const {
580 Parent::firstIn(i, n);
581 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
584 void firstOut(Arc& i, const Node& n) const {
585 Parent::firstOut(i, n);
586 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
589 void next(Node& i) const {
591 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
593 void next(Arc& i) const {
595 while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
597 void nextIn(Arc& i) const {
599 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
602 void nextOut(Arc& i) const {
604 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
607 void hide(const Node& n) const { _node_filter->set(n, false); }
608 void hide(const Arc& e) const { _arc_filter->set(e, false); }
610 void unHide(const Node& n) const { _node_filter->set(n, true); }
611 void unHide(const Arc& e) const { _arc_filter->set(e, true); }
613 bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
614 bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }
616 typedef False NodeNumTag;
617 typedef False ArcNumTag;
619 typedef FindArcTagIndicator<Digraph> FindArcTag;
620 Arc findArc(const Node& source, const Node& target,
621 const Arc& prev = INVALID) {
622 if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
625 Arc arc = Parent::findArc(source, target, prev);
626 while (arc != INVALID && !(*_arc_filter)[arc]) {
627 arc = Parent::findArc(source, target, arc);
632 template <typename _Value>
633 class NodeMap : public SubMapExtender<Adaptor,
634 typename Parent::template NodeMap<_Value> > {
636 typedef _Value Value;
637 typedef SubMapExtender<Adaptor, typename Parent::
638 template NodeMap<Value> > MapParent;
640 NodeMap(const Adaptor& adaptor)
641 : MapParent(adaptor) {}
642 NodeMap(const Adaptor& adaptor, const Value& value)
643 : MapParent(adaptor, value) {}
646 NodeMap& operator=(const NodeMap& cmap) {
647 return operator=<NodeMap>(cmap);
650 template <typename CMap>
651 NodeMap& operator=(const CMap& cmap) {
652 MapParent::operator=(cmap);
657 template <typename _Value>
658 class ArcMap : public SubMapExtender<Adaptor,
659 typename Parent::template ArcMap<_Value> > {
661 typedef _Value Value;
662 typedef SubMapExtender<Adaptor, typename Parent::
663 template ArcMap<Value> > MapParent;
665 ArcMap(const Adaptor& adaptor)
666 : MapParent(adaptor) {}
667 ArcMap(const Adaptor& adaptor, const Value& value)
668 : MapParent(adaptor, value) {}
671 ArcMap& operator=(const ArcMap& cmap) {
672 return operator=<ArcMap>(cmap);
675 template <typename CMap>
676 ArcMap& operator=(const CMap& cmap) {
677 MapParent::operator=(cmap);
684 /// \ingroup graph_adaptors
686 /// \brief An adaptor for hiding nodes and arcs in a digraph
688 /// SubDigraph hides nodes and arcs in a digraph. A bool node map
689 /// and a bool arc map must be specified, which define the filters
690 /// for nodes and arcs. Just the nodes and arcs with true value are
691 /// shown in the subdigraph. The SubDigraph is conform to the \ref
692 /// concepts::Digraph "Digraph concept". If the \c _checked parameter
693 /// is true, then the arcs incident to filtered nodes are also
696 /// \tparam _Digraph It must be conform to the \ref
697 /// concepts::Digraph "Digraph concept". The type can be specified
699 /// \tparam _NodeFilterMap A bool valued node map of the the adapted digraph.
700 /// \tparam _ArcFilterMap A bool valued arc map of the the adapted digraph.
701 /// \tparam _checked If the parameter is false then the arc filtering
702 /// is not checked with respect to node filter. Otherwise, each arc
703 /// is automatically filtered, which is incident to a filtered node.
707 template<typename _Digraph,
708 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
709 typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,
710 bool _checked = true>
712 : public DigraphAdaptorExtender<
713 SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > {
715 typedef _Digraph Digraph;
716 typedef _NodeFilterMap NodeFilterMap;
717 typedef _ArcFilterMap ArcFilterMap;
719 typedef DigraphAdaptorExtender<
720 SubDigraphBase<Digraph, NodeFilterMap, ArcFilterMap, _checked> >
723 typedef typename Parent::Node Node;
724 typedef typename Parent::Arc Arc;
730 /// \brief Constructor
732 /// Creates a subdigraph for the given digraph with
733 /// given node and arc map filters.
734 SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,
735 ArcFilterMap& arc_filter) {
737 setNodeFilterMap(node_filter);
738 setArcFilterMap(arc_filter);
741 /// \brief Hides the node of the graph
743 /// This function hides \c n in the digraph, i.e. the iteration
744 /// jumps over it. This is done by simply setting the value of \c n
745 /// to be false in the corresponding node-map.
746 void hide(const Node& n) const { Parent::hide(n); }
748 /// \brief Hides the arc of the graph
750 /// This function hides \c a in the digraph, i.e. the iteration
751 /// jumps over it. This is done by simply setting the value of \c a
752 /// to be false in the corresponding arc-map.
753 void hide(const Arc& a) const { Parent::hide(a); }
755 /// \brief Unhides the node of the graph
757 /// The value of \c n is set to be true in the node-map which stores
758 /// hide information. If \c n was hidden previuosly, then it is shown
760 void unHide(const Node& n) const { Parent::unHide(n); }
762 /// \brief Unhides the arc of the graph
764 /// The value of \c a is set to be true in the arc-map which stores
765 /// hide information. If \c a was hidden previuosly, then it is shown
767 void unHide(const Arc& a) const { Parent::unHide(a); }
769 /// \brief Returns true if \c n is hidden.
771 /// Returns true if \c n is hidden.
773 bool hidden(const Node& n) const { return Parent::hidden(n); }
775 /// \brief Returns true if \c a is hidden.
777 /// Returns true if \c a is hidden.
779 bool hidden(const Arc& a) const { return Parent::hidden(a); }
783 /// \brief Just gives back a subdigraph
785 /// Just gives back a subdigraph
786 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
787 SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
788 subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) {
789 return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
793 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
794 SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
795 subDigraph(const Digraph& digraph,
796 const NodeFilterMap& nfm, ArcFilterMap& afm) {
797 return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
801 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
802 SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
803 subDigraph(const Digraph& digraph,
804 NodeFilterMap& nfm, const ArcFilterMap& afm) {
805 return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
809 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
810 SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap>
811 subDigraph(const Digraph& digraph,
812 const NodeFilterMap& nfm, const ArcFilterMap& afm) {
813 return SubDigraph<const Digraph, const NodeFilterMap,
814 const ArcFilterMap>(digraph, nfm, afm);
818 template <typename _Graph, typename NodeFilterMap,
819 typename EdgeFilterMap, bool _checked = true>
820 class SubGraphBase : public GraphAdaptorBase<_Graph> {
822 typedef _Graph Graph;
823 typedef SubGraphBase Adaptor;
824 typedef GraphAdaptorBase<_Graph> Parent;
827 NodeFilterMap* _node_filter_map;
828 EdgeFilterMap* _edge_filter_map;
831 : Parent(), _node_filter_map(0), _edge_filter_map(0) { }
833 void setNodeFilterMap(NodeFilterMap& node_filter_map) {
834 _node_filter_map=&node_filter_map;
836 void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
837 _edge_filter_map=&edge_filter_map;
842 typedef typename Parent::Node Node;
843 typedef typename Parent::Arc Arc;
844 typedef typename Parent::Edge Edge;
846 void first(Node& i) const {
848 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
851 void first(Arc& i) const {
853 while (i!=INVALID && (!(*_edge_filter_map)[i]
854 || !(*_node_filter_map)[Parent::source(i)]
855 || !(*_node_filter_map)[Parent::target(i)]))
859 void first(Edge& i) const {
861 while (i!=INVALID && (!(*_edge_filter_map)[i]
862 || !(*_node_filter_map)[Parent::u(i)]
863 || !(*_node_filter_map)[Parent::v(i)]))
867 void firstIn(Arc& i, const Node& n) const {
868 Parent::firstIn(i, n);
869 while (i!=INVALID && (!(*_edge_filter_map)[i]
870 || !(*_node_filter_map)[Parent::source(i)]))
874 void firstOut(Arc& i, const Node& n) const {
875 Parent::firstOut(i, n);
876 while (i!=INVALID && (!(*_edge_filter_map)[i]
877 || !(*_node_filter_map)[Parent::target(i)]))
881 void firstInc(Edge& i, bool& d, const Node& n) const {
882 Parent::firstInc(i, d, n);
883 while (i!=INVALID && (!(*_edge_filter_map)[i]
884 || !(*_node_filter_map)[Parent::u(i)]
885 || !(*_node_filter_map)[Parent::v(i)]))
886 Parent::nextInc(i, d);
889 void next(Node& i) const {
891 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
894 void next(Arc& i) const {
896 while (i!=INVALID && (!(*_edge_filter_map)[i]
897 || !(*_node_filter_map)[Parent::source(i)]
898 || !(*_node_filter_map)[Parent::target(i)]))
902 void next(Edge& i) const {
904 while (i!=INVALID && (!(*_edge_filter_map)[i]
905 || !(*_node_filter_map)[Parent::u(i)]
906 || !(*_node_filter_map)[Parent::v(i)]))
910 void nextIn(Arc& i) const {
912 while (i!=INVALID && (!(*_edge_filter_map)[i]
913 || !(*_node_filter_map)[Parent::source(i)]))
917 void nextOut(Arc& i) const {
919 while (i!=INVALID && (!(*_edge_filter_map)[i]
920 || !(*_node_filter_map)[Parent::target(i)]))
924 void nextInc(Edge& i, bool& d) const {
925 Parent::nextInc(i, d);
926 while (i!=INVALID && (!(*_edge_filter_map)[i]
927 || !(*_node_filter_map)[Parent::u(i)]
928 || !(*_node_filter_map)[Parent::v(i)]))
929 Parent::nextInc(i, d);
932 void hide(const Node& n) const { _node_filter_map->set(n, false); }
933 void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
935 void unHide(const Node& n) const { _node_filter_map->set(n, true); }
936 void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
938 bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
939 bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
941 typedef False NodeNumTag;
942 typedef False ArcNumTag;
943 typedef False EdgeNumTag;
945 typedef FindArcTagIndicator<Graph> FindArcTag;
946 Arc findArc(const Node& u, const Node& v,
947 const Arc& prev = INVALID) {
948 if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
951 Arc arc = Parent::findArc(u, v, prev);
952 while (arc != INVALID && !(*_edge_filter_map)[arc]) {
953 arc = Parent::findArc(u, v, arc);
958 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
959 Edge findEdge(const Node& u, const Node& v,
960 const Edge& prev = INVALID) {
961 if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
964 Edge edge = Parent::findEdge(u, v, prev);
965 while (edge != INVALID && !(*_edge_filter_map)[edge]) {
966 edge = Parent::findEdge(u, v, edge);
971 template <typename _Value>
972 class NodeMap : public SubMapExtender<Adaptor,
973 typename Parent::template NodeMap<_Value> > {
975 typedef _Value Value;
976 typedef SubMapExtender<Adaptor, typename Parent::
977 template NodeMap<Value> > MapParent;
979 NodeMap(const Adaptor& adaptor)
980 : MapParent(adaptor) {}
981 NodeMap(const Adaptor& adaptor, const Value& value)
982 : MapParent(adaptor, value) {}
985 NodeMap& operator=(const NodeMap& cmap) {
986 return operator=<NodeMap>(cmap);
989 template <typename CMap>
990 NodeMap& operator=(const CMap& cmap) {
991 MapParent::operator=(cmap);
996 template <typename _Value>
997 class ArcMap : public SubMapExtender<Adaptor,
998 typename Parent::template ArcMap<_Value> > {
1000 typedef _Value Value;
1001 typedef SubMapExtender<Adaptor, typename Parent::
1002 template ArcMap<Value> > MapParent;
1004 ArcMap(const Adaptor& adaptor)
1005 : MapParent(adaptor) {}
1006 ArcMap(const Adaptor& adaptor, const Value& value)
1007 : MapParent(adaptor, value) {}
1010 ArcMap& operator=(const ArcMap& cmap) {
1011 return operator=<ArcMap>(cmap);
1014 template <typename CMap>
1015 ArcMap& operator=(const CMap& cmap) {
1016 MapParent::operator=(cmap);
1021 template <typename _Value>
1022 class EdgeMap : public SubMapExtender<Adaptor,
1023 typename Parent::template EdgeMap<_Value> > {
1025 typedef _Value Value;
1026 typedef SubMapExtender<Adaptor, typename Parent::
1027 template EdgeMap<Value> > MapParent;
1029 EdgeMap(const Adaptor& adaptor)
1030 : MapParent(adaptor) {}
1032 EdgeMap(const Adaptor& adaptor, const Value& value)
1033 : MapParent(adaptor, value) {}
1036 EdgeMap& operator=(const EdgeMap& cmap) {
1037 return operator=<EdgeMap>(cmap);
1040 template <typename CMap>
1041 EdgeMap& operator=(const CMap& cmap) {
1042 MapParent::operator=(cmap);
1049 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
1050 class SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
1051 : public GraphAdaptorBase<_Graph> {
1053 typedef _Graph Graph;
1054 typedef SubGraphBase Adaptor;
1055 typedef GraphAdaptorBase<_Graph> Parent;
1057 NodeFilterMap* _node_filter_map;
1058 EdgeFilterMap* _edge_filter_map;
1059 SubGraphBase() : Parent(),
1060 _node_filter_map(0), _edge_filter_map(0) { }
1062 void setNodeFilterMap(NodeFilterMap& node_filter_map) {
1063 _node_filter_map=&node_filter_map;
1065 void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
1066 _edge_filter_map=&edge_filter_map;
1071 typedef typename Parent::Node Node;
1072 typedef typename Parent::Arc Arc;
1073 typedef typename Parent::Edge Edge;
1075 void first(Node& i) const {
1077 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
1080 void first(Arc& i) const {
1082 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1085 void first(Edge& i) const {
1087 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1090 void firstIn(Arc& i, const Node& n) const {
1091 Parent::firstIn(i, n);
1092 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
1095 void firstOut(Arc& i, const Node& n) const {
1096 Parent::firstOut(i, n);
1097 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
1100 void firstInc(Edge& i, bool& d, const Node& n) const {
1101 Parent::firstInc(i, d, n);
1102 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
1105 void next(Node& i) const {
1107 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
1109 void next(Arc& i) const {
1111 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1113 void next(Edge& i) const {
1115 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1117 void nextIn(Arc& i) const {
1119 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
1122 void nextOut(Arc& i) const {
1124 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
1126 void nextInc(Edge& i, bool& d) const {
1127 Parent::nextInc(i, d);
1128 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
1131 void hide(const Node& n) const { _node_filter_map->set(n, false); }
1132 void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
1134 void unHide(const Node& n) const { _node_filter_map->set(n, true); }
1135 void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
1137 bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
1138 bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
1140 typedef False NodeNumTag;
1141 typedef False ArcNumTag;
1142 typedef False EdgeNumTag;
1144 typedef FindArcTagIndicator<Graph> FindArcTag;
1145 Arc findArc(const Node& u, const Node& v,
1146 const Arc& prev = INVALID) {
1147 Arc arc = Parent::findArc(u, v, prev);
1148 while (arc != INVALID && !(*_edge_filter_map)[arc]) {
1149 arc = Parent::findArc(u, v, arc);
1154 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1155 Edge findEdge(const Node& u, const Node& v,
1156 const Edge& prev = INVALID) {
1157 Edge edge = Parent::findEdge(u, v, prev);
1158 while (edge != INVALID && !(*_edge_filter_map)[edge]) {
1159 edge = Parent::findEdge(u, v, edge);
1164 template <typename _Value>
1165 class NodeMap : public SubMapExtender<Adaptor,
1166 typename Parent::template NodeMap<_Value> > {
1168 typedef _Value Value;
1169 typedef SubMapExtender<Adaptor, typename Parent::
1170 template NodeMap<Value> > MapParent;
1172 NodeMap(const Adaptor& adaptor)
1173 : MapParent(adaptor) {}
1174 NodeMap(const Adaptor& adaptor, const Value& value)
1175 : MapParent(adaptor, value) {}
1178 NodeMap& operator=(const NodeMap& cmap) {
1179 return operator=<NodeMap>(cmap);
1182 template <typename CMap>
1183 NodeMap& operator=(const CMap& cmap) {
1184 MapParent::operator=(cmap);
1189 template <typename _Value>
1190 class ArcMap : public SubMapExtender<Adaptor,
1191 typename Parent::template ArcMap<_Value> > {
1193 typedef _Value Value;
1194 typedef SubMapExtender<Adaptor, typename Parent::
1195 template ArcMap<Value> > MapParent;
1197 ArcMap(const Adaptor& adaptor)
1198 : MapParent(adaptor) {}
1199 ArcMap(const Adaptor& adaptor, const Value& value)
1200 : MapParent(adaptor, value) {}
1203 ArcMap& operator=(const ArcMap& cmap) {
1204 return operator=<ArcMap>(cmap);
1207 template <typename CMap>
1208 ArcMap& operator=(const CMap& cmap) {
1209 MapParent::operator=(cmap);
1214 template <typename _Value>
1215 class EdgeMap : public SubMapExtender<Adaptor,
1216 typename Parent::template EdgeMap<_Value> > {
1218 typedef _Value Value;
1219 typedef SubMapExtender<Adaptor, typename Parent::
1220 template EdgeMap<Value> > MapParent;
1222 EdgeMap(const Adaptor& adaptor)
1223 : MapParent(adaptor) {}
1225 EdgeMap(const Adaptor& adaptor, const _Value& value)
1226 : MapParent(adaptor, value) {}
1229 EdgeMap& operator=(const EdgeMap& cmap) {
1230 return operator=<EdgeMap>(cmap);
1233 template <typename CMap>
1234 EdgeMap& operator=(const CMap& cmap) {
1235 MapParent::operator=(cmap);
1242 /// \ingroup graph_adaptors
1244 /// \brief A graph adaptor for hiding nodes and edges in an
1245 /// undirected graph.
1247 /// SubGraph hides nodes and edges in a graph. A bool node map and a
1248 /// bool edge map must be specified, which define the filters for
1249 /// nodes and edges. Just the nodes and edges with true value are
1250 /// shown in the subgraph. The SubGraph is conform to the \ref
1251 /// concepts::Graph "Graph concept". If the \c _checked parameter is
1252 /// true, then the edges incident to filtered nodes are also
1255 /// \tparam _Graph It must be conform to the \ref
1256 /// concepts::Graph "Graph concept". The type can be specified
1258 /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
1259 /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted graph.
1260 /// \tparam _checked If the parameter is false then the edge filtering
1261 /// is not checked with respect to node filter. Otherwise, each edge
1262 /// is automatically filtered, which is incident to a filtered node.
1264 /// \see FilterNodes
1265 /// \see FilterEdges
1266 template<typename _Graph, typename NodeFilterMap,
1267 typename EdgeFilterMap, bool _checked = true>
1269 : public GraphAdaptorExtender<
1270 SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, _checked> > {
1272 typedef _Graph Graph;
1273 typedef GraphAdaptorExtender<
1274 SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
1276 typedef typename Parent::Node Node;
1277 typedef typename Parent::Edge Edge;
1283 /// \brief Constructor
1285 /// Creates a subgraph for the given graph with given node and
1286 /// edge map filters.
1287 SubGraph(Graph& _graph, NodeFilterMap& node_filter_map,
1288 EdgeFilterMap& edge_filter_map) {
1290 setNodeFilterMap(node_filter_map);
1291 setEdgeFilterMap(edge_filter_map);
1294 /// \brief Hides the node of the graph
1296 /// This function hides \c n in the graph, i.e. the iteration
1297 /// jumps over it. This is done by simply setting the value of \c n
1298 /// to be false in the corresponding node-map.
1299 void hide(const Node& n) const { Parent::hide(n); }
1301 /// \brief Hides the edge of the graph
1303 /// This function hides \c e in the graph, i.e. the iteration
1304 /// jumps over it. This is done by simply setting the value of \c e
1305 /// to be false in the corresponding edge-map.
1306 void hide(const Edge& e) const { Parent::hide(e); }
1308 /// \brief Unhides the node of the graph
1310 /// The value of \c n is set to be true in the node-map which stores
1311 /// hide information. If \c n was hidden previuosly, then it is shown
1313 void unHide(const Node& n) const { Parent::unHide(n); }
1315 /// \brief Unhides the edge of the graph
1317 /// The value of \c e is set to be true in the edge-map which stores
1318 /// hide information. If \c e was hidden previuosly, then it is shown
1320 void unHide(const Edge& e) const { Parent::unHide(e); }
1322 /// \brief Returns true if \c n is hidden.
1324 /// Returns true if \c n is hidden.
1326 bool hidden(const Node& n) const { return Parent::hidden(n); }
1328 /// \brief Returns true if \c e is hidden.
1330 /// Returns true if \c e is hidden.
1332 bool hidden(const Edge& e) const { return Parent::hidden(e); }
1335 /// \brief Just gives back a subgraph
1337 /// Just gives back a subgraph
1338 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1339 SubGraph<const Graph, NodeFilterMap, ArcFilterMap>
1340 subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) {
1341 return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm);
1344 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1345 SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
1346 subGraph(const Graph& graph,
1347 const NodeFilterMap& nfm, ArcFilterMap& efm) {
1348 return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
1352 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1353 SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
1354 subGraph(const Graph& graph,
1355 NodeFilterMap& nfm, const ArcFilterMap& efm) {
1356 return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
1360 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1361 SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
1362 subGraph(const Graph& graph,
1363 const NodeFilterMap& nfm, const ArcFilterMap& efm) {
1364 return SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
1368 /// \ingroup graph_adaptors
1370 /// \brief An adaptor for hiding nodes from a digraph or a graph.
1372 /// FilterNodes adaptor hides nodes in a graph or a digraph. A bool
1373 /// node map must be specified, which defines the filters for
1374 /// nodes. Just the unfiltered nodes and the arcs or edges incident
1375 /// to unfiltered nodes are shown in the subdigraph or subgraph. The
1376 /// FilterNodes is conform to the \ref concepts::Digraph
1377 /// "Digraph concept" or \ref concepts::Graph "Graph concept" depending
1378 /// on the \c _Digraph template parameter. If the \c _checked
1379 /// parameter is true, then the arc or edges incident to filtered nodes
1380 /// are also filtered out.
1382 /// \tparam _Digraph It must be conform to the \ref
1383 /// concepts::Digraph "Digraph concept" or \ref concepts::Graph
1384 /// "Graph concept". The type can be specified to be const.
1385 /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
1386 /// \tparam _checked If the parameter is false then the arc or edge
1387 /// filtering is not checked with respect to node filter. In this
1388 /// case just isolated nodes can be filtered out from the
1391 template<typename _Digraph,
1392 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
1393 bool _checked = true>
1395 template<typename _Digraph,
1396 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
1397 bool _checked = true,
1398 typename Enable = void>
1401 : public SubDigraph<_Digraph, _NodeFilterMap,
1402 ConstMap<typename _Digraph::Arc, bool>, _checked> {
1405 typedef _Digraph Digraph;
1406 typedef _NodeFilterMap NodeFilterMap;
1408 typedef SubDigraph<Digraph, NodeFilterMap,
1409 ConstMap<typename Digraph::Arc, bool>, _checked>
1412 typedef typename Parent::Node Node;
1415 ConstMap<typename Digraph::Arc, bool> const_true_map;
1417 FilterNodes() : const_true_map(true) {
1418 Parent::setArcFilterMap(const_true_map);
1423 /// \brief Constructor
1425 /// Creates an adaptor for the given digraph or graph with
1426 /// given node filter map.
1427 FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) :
1428 Parent(), const_true_map(true) {
1429 Parent::setDigraph(_digraph);
1430 Parent::setNodeFilterMap(node_filter);
1431 Parent::setArcFilterMap(const_true_map);
1434 /// \brief Hides the node of the graph
1436 /// This function hides \c n in the digraph or graph, i.e. the iteration
1437 /// jumps over it. This is done by simply setting the value of \c n
1438 /// to be false in the corresponding node map.
1439 void hide(const Node& n) const { Parent::hide(n); }
1441 /// \brief Unhides the node of the graph
1443 /// The value of \c n is set to be true in the node-map which stores
1444 /// hide information. If \c n was hidden previuosly, then it is shown
1446 void unHide(const Node& n) const { Parent::unHide(n); }
1448 /// \brief Returns true if \c n is hidden.
1450 /// Returns true if \c n is hidden.
1452 bool hidden(const Node& n) const { return Parent::hidden(n); }
1456 template<typename _Graph, typename _NodeFilterMap, bool _checked>
1457 class FilterNodes<_Graph, _NodeFilterMap, _checked,
1458 typename enable_if<UndirectedTagIndicator<_Graph> >::type>
1459 : public SubGraph<_Graph, _NodeFilterMap,
1460 ConstMap<typename _Graph::Edge, bool>, _checked> {
1462 typedef _Graph Graph;
1463 typedef _NodeFilterMap NodeFilterMap;
1464 typedef SubGraph<Graph, NodeFilterMap,
1465 ConstMap<typename Graph::Edge, bool> > Parent;
1467 typedef typename Parent::Node Node;
1469 ConstMap<typename Graph::Edge, bool> const_true_map;
1471 FilterNodes() : const_true_map(true) {
1472 Parent::setEdgeFilterMap(const_true_map);
1477 FilterNodes(Graph& _graph, NodeFilterMap& node_filter_map) :
1478 Parent(), const_true_map(true) {
1479 Parent::setGraph(_graph);
1480 Parent::setNodeFilterMap(node_filter_map);
1481 Parent::setEdgeFilterMap(const_true_map);
1484 void hide(const Node& n) const { Parent::hide(n); }
1485 void unHide(const Node& n) const { Parent::unHide(n); }
1486 bool hidden(const Node& n) const { return Parent::hidden(n); }
1491 /// \brief Just gives back a FilterNodes adaptor
1493 /// Just gives back a FilterNodes adaptor
1494 template<typename Digraph, typename NodeFilterMap>
1495 FilterNodes<const Digraph, NodeFilterMap>
1496 filterNodes(const Digraph& digraph, NodeFilterMap& nfm) {
1497 return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm);
1500 template<typename Digraph, typename NodeFilterMap>
1501 FilterNodes<const Digraph, const NodeFilterMap>
1502 filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) {
1503 return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm);
1506 /// \ingroup graph_adaptors
1508 /// \brief An adaptor for hiding arcs from a digraph.
1510 /// FilterArcs adaptor hides arcs in a digraph. A bool arc map must
1511 /// be specified, which defines the filters for arcs. Just the
1512 /// unfiltered arcs are shown in the subdigraph. The FilterArcs is
1513 /// conform to the \ref concepts::Digraph "Digraph concept".
1515 /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
1516 /// "Digraph concept". The type can be specified to be const.
1517 /// \tparam _ArcFilterMap A bool valued arc map of the the adapted
1519 template<typename _Digraph, typename _ArcFilterMap>
1521 public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>,
1522 _ArcFilterMap, false> {
1524 typedef _Digraph Digraph;
1525 typedef _ArcFilterMap ArcFilterMap;
1527 typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>,
1528 ArcFilterMap, false> Parent;
1530 typedef typename Parent::Arc Arc;
1533 ConstMap<typename Digraph::Node, bool> const_true_map;
1535 FilterArcs() : const_true_map(true) {
1536 Parent::setNodeFilterMap(const_true_map);
1541 /// \brief Constructor
1543 /// Creates a FilterArcs adaptor for the given graph with
1544 /// given arc map filter.
1545 FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
1546 : Parent(), const_true_map(true) {
1547 Parent::setDigraph(digraph);
1548 Parent::setNodeFilterMap(const_true_map);
1549 Parent::setArcFilterMap(arc_filter);
1552 /// \brief Hides the arc of the graph
1554 /// This function hides \c a in the graph, i.e. the iteration
1555 /// jumps over it. This is done by simply setting the value of \c a
1556 /// to be false in the corresponding arc map.
1557 void hide(const Arc& a) const { Parent::hide(a); }
1559 /// \brief Unhides the arc of the graph
1561 /// The value of \c a is set to be true in the arc-map which stores
1562 /// hide information. If \c a was hidden previuosly, then it is shown
1564 void unHide(const Arc& a) const { Parent::unHide(a); }
1566 /// \brief Returns true if \c a is hidden.
1568 /// Returns true if \c a is hidden.
1570 bool hidden(const Arc& a) const { return Parent::hidden(a); }
1574 /// \brief Just gives back an FilterArcs adaptor
1576 /// Just gives back an FilterArcs adaptor
1577 template<typename Digraph, typename ArcFilterMap>
1578 FilterArcs<const Digraph, ArcFilterMap>
1579 filterArcs(const Digraph& digraph, ArcFilterMap& afm) {
1580 return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm);
1583 template<typename Digraph, typename ArcFilterMap>
1584 FilterArcs<const Digraph, const ArcFilterMap>
1585 filterArcs(const Digraph& digraph, const ArcFilterMap& afm) {
1586 return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm);
1589 /// \ingroup graph_adaptors
1591 /// \brief An adaptor for hiding edges from a graph.
1593 /// FilterEdges adaptor hides edges in a digraph. A bool edge map must
1594 /// be specified, which defines the filters for edges. Just the
1595 /// unfiltered edges are shown in the subdigraph. The FilterEdges is
1596 /// conform to the \ref concepts::Graph "Graph concept".
1598 /// \tparam _Graph It must be conform to the \ref concepts::Graph
1599 /// "Graph concept". The type can be specified to be const.
1600 /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted
1602 template<typename _Graph, typename _EdgeFilterMap>
1604 public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>,
1605 _EdgeFilterMap, false> {
1607 typedef _Graph Graph;
1608 typedef _EdgeFilterMap EdgeFilterMap;
1609 typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>,
1610 EdgeFilterMap, false> Parent;
1611 typedef typename Parent::Edge Edge;
1613 ConstMap<typename Graph::Node, bool> const_true_map;
1615 FilterEdges() : const_true_map(true) {
1616 Parent::setNodeFilterMap(const_true_map);
1621 /// \brief Constructor
1623 /// Creates a FilterEdges adaptor for the given graph with
1624 /// given edge map filters.
1625 FilterEdges(Graph& _graph, EdgeFilterMap& edge_filter_map) :
1626 Parent(), const_true_map(true) {
1627 Parent::setGraph(_graph);
1628 Parent::setNodeFilterMap(const_true_map);
1629 Parent::setEdgeFilterMap(edge_filter_map);
1632 /// \brief Hides the edge of the graph
1634 /// This function hides \c e in the graph, i.e. the iteration
1635 /// jumps over it. This is done by simply setting the value of \c e
1636 /// to be false in the corresponding edge-map.
1637 void hide(const Edge& e) const { Parent::hide(e); }
1639 /// \brief Unhides the edge of the graph
1641 /// The value of \c e is set to be true in the edge-map which stores
1642 /// hide information. If \c e was hidden previuosly, then it is shown
1644 void unHide(const Edge& e) const { Parent::unHide(e); }
1646 /// \brief Returns true if \c e is hidden.
1648 /// Returns true if \c e is hidden.
1650 bool hidden(const Edge& e) const { return Parent::hidden(e); }
1654 /// \brief Just gives back a FilterEdges adaptor
1656 /// Just gives back a FilterEdges adaptor
1657 template<typename Graph, typename EdgeFilterMap>
1658 FilterEdges<const Graph, EdgeFilterMap>
1659 filterEdges(const Graph& graph, EdgeFilterMap& efm) {
1660 return FilterEdges<const Graph, EdgeFilterMap>(graph, efm);
1663 template<typename Graph, typename EdgeFilterMap>
1664 FilterEdges<const Graph, const EdgeFilterMap>
1665 filterEdges(const Graph& graph, const EdgeFilterMap& efm) {
1666 return FilterEdges<const Graph, const EdgeFilterMap>(graph, efm);
1669 template <typename _Digraph>
1670 class UndirectorBase {
1672 typedef _Digraph Digraph;
1673 typedef UndirectorBase Adaptor;
1675 typedef True UndirectedTag;
1677 typedef typename Digraph::Arc Edge;
1678 typedef typename Digraph::Node Node;
1680 class Arc : public Edge {
1681 friend class UndirectorBase;
1685 Arc(const Edge& edge, bool forward) :
1686 Edge(edge), _forward(forward) {}
1691 Arc(Invalid) : Edge(INVALID), _forward(true) {}
1693 bool operator==(const Arc &other) const {
1694 return _forward == other._forward &&
1695 static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
1697 bool operator!=(const Arc &other) const {
1698 return _forward != other._forward ||
1699 static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
1701 bool operator<(const Arc &other) const {
1702 return _forward < other._forward ||
1703 (_forward == other._forward &&
1704 static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
1710 void first(Node& n) const {
1714 void next(Node& n) const {
1718 void first(Arc& a) const {
1723 void next(Arc& a) const {
1732 void first(Edge& e) const {
1736 void next(Edge& e) const {
1740 void firstOut(Arc& a, const Node& n) const {
1741 _digraph->firstIn(a, n);
1742 if( static_cast<const Edge&>(a) != INVALID ) {
1745 _digraph->firstOut(a, n);
1749 void nextOut(Arc &a) const {
1751 Node n = _digraph->target(a);
1752 _digraph->nextIn(a);
1753 if (static_cast<const Edge&>(a) == INVALID ) {
1754 _digraph->firstOut(a, n);
1759 _digraph->nextOut(a);
1763 void firstIn(Arc &a, const Node &n) const {
1764 _digraph->firstOut(a, n);
1765 if (static_cast<const Edge&>(a) != INVALID ) {
1768 _digraph->firstIn(a, n);
1772 void nextIn(Arc &a) const {
1774 Node n = _digraph->source(a);
1775 _digraph->nextOut(a);
1776 if( static_cast<const Edge&>(a) == INVALID ) {
1777 _digraph->firstIn(a, n);
1782 _digraph->nextIn(a);
1786 void firstInc(Edge &e, bool &d, const Node &n) const {
1788 _digraph->firstOut(e, n);
1789 if (e != INVALID) return;
1791 _digraph->firstIn(e, n);
1794 void nextInc(Edge &e, bool &d) const {
1796 Node s = _digraph->source(e);
1797 _digraph->nextOut(e);
1798 if (e != INVALID) return;
1800 _digraph->firstIn(e, s);
1802 _digraph->nextIn(e);
1806 Node u(const Edge& e) const {
1807 return _digraph->source(e);
1810 Node v(const Edge& e) const {
1811 return _digraph->target(e);
1814 Node source(const Arc &a) const {
1815 return a._forward ? _digraph->source(a) : _digraph->target(a);
1818 Node target(const Arc &a) const {
1819 return a._forward ? _digraph->target(a) : _digraph->source(a);
1822 static Arc direct(const Edge &e, bool d) {
1825 Arc direct(const Edge &e, const Node& n) const {
1826 return Arc(e, _digraph->source(e) == n);
1829 static bool direction(const Arc &a) { return a._forward; }
1831 Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
1832 Arc arcFromId(int ix) const {
1833 return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1));
1835 Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); }
1837 int id(const Node &n) const { return _digraph->id(n); }
1838 int id(const Arc &a) const {
1839 return (_digraph->id(a) << 1) | (a._forward ? 1 : 0);
1841 int id(const Edge &e) const { return _digraph->id(e); }
1843 int maxNodeId() const { return _digraph->maxNodeId(); }
1844 int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; }
1845 int maxEdgeId() const { return _digraph->maxArcId(); }
1847 Node addNode() { return _digraph->addNode(); }
1848 Edge addEdge(const Node& u, const Node& v) {
1849 return _digraph->addArc(u, v);
1852 void erase(const Node& i) { _digraph->erase(i); }
1853 void erase(const Edge& i) { _digraph->erase(i); }
1855 void clear() { _digraph->clear(); }
1857 typedef NodeNumTagIndicator<Digraph> NodeNumTag;
1858 int nodeNum() const { return 2 * _digraph->arcNum(); }
1860 typedef ArcNumTagIndicator<Digraph> ArcNumTag;
1861 int arcNum() const { return 2 * _digraph->arcNum(); }
1863 typedef ArcNumTag EdgeNumTag;
1864 int edgeNum() const { return _digraph->arcNum(); }
1866 typedef FindArcTagIndicator<Digraph> FindArcTag;
1867 Arc findArc(Node s, Node t, Arc p = INVALID) const {
1869 Edge arc = _digraph->findArc(s, t);
1870 if (arc != INVALID) return direct(arc, true);
1871 arc = _digraph->findArc(t, s);
1872 if (arc != INVALID) return direct(arc, false);
1873 } else if (direction(p)) {
1874 Edge arc = _digraph->findArc(s, t, p);
1875 if (arc != INVALID) return direct(arc, true);
1876 arc = _digraph->findArc(t, s);
1877 if (arc != INVALID) return direct(arc, false);
1879 Edge arc = _digraph->findArc(t, s, p);
1880 if (arc != INVALID) return direct(arc, false);
1885 typedef FindArcTag FindEdgeTag;
1886 Edge findEdge(Node s, Node t, Edge p = INVALID) const {
1889 Edge arc = _digraph->findArc(s, t);
1890 if (arc != INVALID) return arc;
1891 arc = _digraph->findArc(t, s);
1892 if (arc != INVALID) return arc;
1893 } else if (_digraph->s(p) == s) {
1894 Edge arc = _digraph->findArc(s, t, p);
1895 if (arc != INVALID) return arc;
1896 arc = _digraph->findArc(t, s);
1897 if (arc != INVALID) return arc;
1899 Edge arc = _digraph->findArc(t, s, p);
1900 if (arc != INVALID) return arc;
1903 return _digraph->findArc(s, t, p);
1910 template <typename _Value>
1914 typedef typename Digraph::template ArcMap<_Value> MapImpl;
1918 typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
1920 typedef _Value Value;
1923 ArcMapBase(const Adaptor& adaptor) :
1924 _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
1926 ArcMapBase(const Adaptor& adaptor, const Value& v)
1927 : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}
1929 void set(const Arc& a, const Value& v) {
1933 _backward.set(a, v);
1937 typename MapTraits<MapImpl>::ConstReturnValue
1938 operator[](const Arc& a) const {
1942 return _backward[a];
1946 typename MapTraits<MapImpl>::ReturnValue
1947 operator[](const Arc& a) {
1951 return _backward[a];
1957 MapImpl _forward, _backward;
1963 template <typename _Value>
1964 class NodeMap : public Digraph::template NodeMap<_Value> {
1967 typedef _Value Value;
1968 typedef typename Digraph::template NodeMap<Value> Parent;
1970 explicit NodeMap(const Adaptor& adaptor)
1971 : Parent(*adaptor._digraph) {}
1973 NodeMap(const Adaptor& adaptor, const _Value& value)
1974 : Parent(*adaptor._digraph, value) { }
1977 NodeMap& operator=(const NodeMap& cmap) {
1978 return operator=<NodeMap>(cmap);
1981 template <typename CMap>
1982 NodeMap& operator=(const CMap& cmap) {
1983 Parent::operator=(cmap);
1989 template <typename _Value>
1991 : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
1994 typedef _Value Value;
1995 typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
1997 ArcMap(const Adaptor& adaptor)
1998 : Parent(adaptor) {}
2000 ArcMap(const Adaptor& adaptor, const Value& value)
2001 : Parent(adaptor, value) {}
2004 ArcMap& operator=(const ArcMap& cmap) {
2005 return operator=<ArcMap>(cmap);
2008 template <typename CMap>
2009 ArcMap& operator=(const CMap& cmap) {
2010 Parent::operator=(cmap);
2015 template <typename _Value>
2016 class EdgeMap : public Digraph::template ArcMap<_Value> {
2019 typedef _Value Value;
2020 typedef typename Digraph::template ArcMap<Value> Parent;
2022 explicit EdgeMap(const Adaptor& adaptor)
2023 : Parent(*adaptor._digraph) {}
2025 EdgeMap(const Adaptor& adaptor, const Value& value)
2026 : Parent(*adaptor._digraph, value) {}
2029 EdgeMap& operator=(const EdgeMap& cmap) {
2030 return operator=<EdgeMap>(cmap);
2033 template <typename CMap>
2034 EdgeMap& operator=(const CMap& cmap) {
2035 Parent::operator=(cmap);
2041 typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
2042 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
2046 UndirectorBase() : _digraph(0) {}
2050 void setDigraph(Digraph& digraph) {
2051 _digraph = &digraph;
2056 /// \ingroup graph_adaptors
2058 /// \brief Undirect the graph
2060 /// This adaptor makes an undirected graph from a directed
2061 /// graph. All arcs of the underlying digraph will be showed in the
2062 /// adaptor as an edge. The Orienter adaptor is conform to the \ref
2063 /// concepts::Graph "Graph concept".
2065 /// \tparam _Digraph It must be conform to the \ref
2066 /// concepts::Digraph "Digraph concept". The type can be specified
2068 template<typename _Digraph>
2070 : public GraphAdaptorExtender<UndirectorBase<_Digraph> > {
2072 typedef _Digraph Digraph;
2073 typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent;
2078 /// \brief Constructor
2080 /// Creates a undirected graph from the given digraph
2081 Undirector(_Digraph& digraph) {
2082 setDigraph(digraph);
2085 /// \brief ArcMap combined from two original ArcMap
2087 /// This class adapts two original digraph ArcMap to
2088 /// get an arc map on the undirected graph.
2089 template <typename _ForwardMap, typename _BackwardMap>
2090 class CombinedArcMap {
2093 typedef _ForwardMap ForwardMap;
2094 typedef _BackwardMap BackwardMap;
2096 typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
2098 typedef typename ForwardMap::Value Value;
2099 typedef typename Parent::Arc Key;
2101 /// \brief Constructor
2104 CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
2105 : _forward(&forward), _backward(&backward) {}
2108 /// \brief Sets the value associated with a key.
2110 /// Sets the value associated with a key.
2111 void set(const Key& e, const Value& a) {
2112 if (Parent::direction(e)) {
2113 _forward->set(e, a);
2115 _backward->set(e, a);
2119 /// \brief Returns the value associated with a key.
2121 /// Returns the value associated with a key.
2122 typename MapTraits<ForwardMap>::ConstReturnValue
2123 operator[](const Key& e) const {
2124 if (Parent::direction(e)) {
2125 return (*_forward)[e];
2127 return (*_backward)[e];
2131 /// \brief Returns the value associated with a key.
2133 /// Returns the value associated with a key.
2134 typename MapTraits<ForwardMap>::ReturnValue
2135 operator[](const Key& e) {
2136 if (Parent::direction(e)) {
2137 return (*_forward)[e];
2139 return (*_backward)[e];
2145 ForwardMap* _forward;
2146 BackwardMap* _backward;
2150 /// \brief Just gives back a combined arc map
2152 /// Just gives back a combined arc map
2153 template <typename ForwardMap, typename BackwardMap>
2154 static CombinedArcMap<ForwardMap, BackwardMap>
2155 combinedArcMap(ForwardMap& forward, BackwardMap& backward) {
2156 return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward);
2159 template <typename ForwardMap, typename BackwardMap>
2160 static CombinedArcMap<const ForwardMap, BackwardMap>
2161 combinedArcMap(const ForwardMap& forward, BackwardMap& backward) {
2162 return CombinedArcMap<const ForwardMap,
2163 BackwardMap>(forward, backward);
2166 template <typename ForwardMap, typename BackwardMap>
2167 static CombinedArcMap<ForwardMap, const BackwardMap>
2168 combinedArcMap(ForwardMap& forward, const BackwardMap& backward) {
2169 return CombinedArcMap<ForwardMap,
2170 const BackwardMap>(forward, backward);
2173 template <typename ForwardMap, typename BackwardMap>
2174 static CombinedArcMap<const ForwardMap, const BackwardMap>
2175 combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) {
2176 return CombinedArcMap<const ForwardMap,
2177 const BackwardMap>(forward, backward);
2182 /// \brief Just gives back an undirected view of the given digraph
2184 /// Just gives back an undirected view of the given digraph
2185 template<typename Digraph>
2186 Undirector<const Digraph>
2187 undirector(const Digraph& digraph) {
2188 return Undirector<const Digraph>(digraph);
2191 template <typename _Graph, typename _DirectionMap>
2192 class OrienterBase {
2195 typedef _Graph Graph;
2196 typedef _DirectionMap DirectionMap;
2198 typedef typename Graph::Node Node;
2199 typedef typename Graph::Edge Arc;
2201 void reverseArc(const Arc& arc) {
2202 _direction->set(arc, !(*_direction)[arc]);
2205 void first(Node& i) const { _graph->first(i); }
2206 void first(Arc& i) const { _graph->first(i); }
2207 void firstIn(Arc& i, const Node& n) const {
2209 _graph->firstInc(i, d, n);
2210 while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
2212 void firstOut(Arc& i, const Node& n ) const {
2214 _graph->firstInc(i, d, n);
2215 while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
2218 void next(Node& i) const { _graph->next(i); }
2219 void next(Arc& i) const { _graph->next(i); }
2220 void nextIn(Arc& i) const {
2221 bool d = !(*_direction)[i];
2222 _graph->nextInc(i, d);
2223 while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
2225 void nextOut(Arc& i) const {
2226 bool d = (*_direction)[i];
2227 _graph->nextInc(i, d);
2228 while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
2231 Node source(const Arc& e) const {
2232 return (*_direction)[e] ? _graph->u(e) : _graph->v(e);
2234 Node target(const Arc& e) const {
2235 return (*_direction)[e] ? _graph->v(e) : _graph->u(e);
2238 typedef NodeNumTagIndicator<Graph> NodeNumTag;
2239 int nodeNum() const { return _graph->nodeNum(); }
2241 typedef EdgeNumTagIndicator<Graph> ArcNumTag;
2242 int arcNum() const { return _graph->edgeNum(); }
2244 typedef FindEdgeTagIndicator<Graph> FindArcTag;
2245 Arc findArc(const Node& u, const Node& v,
2246 const Arc& prev = INVALID) {
2248 bool d = arc == INVALID ? true : (*_direction)[arc];
2250 arc = _graph->findEdge(u, v, arc);
2251 while (arc != INVALID && !(*_direction)[arc]) {
2252 _graph->findEdge(u, v, arc);
2254 if (arc != INVALID) return arc;
2256 _graph->findEdge(v, u, arc);
2257 while (arc != INVALID && (*_direction)[arc]) {
2258 _graph->findEdge(u, v, arc);
2264 return Node(_graph->addNode());
2267 Arc addArc(const Node& u, const Node& v) {
2268 Arc arc = _graph->addArc(u, v);
2269 _direction->set(arc, _graph->source(arc) == u);
2273 void erase(const Node& i) { _graph->erase(i); }
2274 void erase(const Arc& i) { _graph->erase(i); }
2276 void clear() { _graph->clear(); }
2278 int id(const Node& v) const { return _graph->id(v); }
2279 int id(const Arc& e) const { return _graph->id(e); }
2281 Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
2282 Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
2284 int maxNodeId() const { return _graph->maxNodeId(); }
2285 int maxArcId() const { return _graph->maxEdgeId(); }
2287 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
2288 NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
2290 typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
2291 ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
2293 template <typename _Value>
2294 class NodeMap : public _Graph::template NodeMap<_Value> {
2297 typedef typename _Graph::template NodeMap<_Value> Parent;
2299 explicit NodeMap(const OrienterBase& adapter)
2300 : Parent(*adapter._graph) {}
2302 NodeMap(const OrienterBase& adapter, const _Value& value)
2303 : Parent(*adapter._graph, value) {}
2306 NodeMap& operator=(const NodeMap& cmap) {
2307 return operator=<NodeMap>(cmap);
2310 template <typename CMap>
2311 NodeMap& operator=(const CMap& cmap) {
2312 Parent::operator=(cmap);
2318 template <typename _Value>
2319 class ArcMap : public _Graph::template EdgeMap<_Value> {
2322 typedef typename Graph::template EdgeMap<_Value> Parent;
2324 explicit ArcMap(const OrienterBase& adapter)
2325 : Parent(*adapter._graph) { }
2327 ArcMap(const OrienterBase& adapter, const _Value& value)
2328 : Parent(*adapter._graph, value) { }
2331 ArcMap& operator=(const ArcMap& cmap) {
2332 return operator=<ArcMap>(cmap);
2335 template <typename CMap>
2336 ArcMap& operator=(const CMap& cmap) {
2337 Parent::operator=(cmap);
2346 DirectionMap* _direction;
2348 void setDirectionMap(DirectionMap& direction) {
2349 _direction = &direction;
2352 void setGraph(Graph& graph) {
2358 /// \ingroup graph_adaptors
2360 /// \brief Orients the edges of the graph to get a digraph
2362 /// This adaptor orients each edge in the undirected graph. The
2363 /// direction of the arcs stored in an edge node map. The arcs can
2364 /// be easily reverted by the \c reverseArc() member function in the
2365 /// adaptor. The Orienter adaptor is conform to the \ref
2366 /// concepts::Digraph "Digraph concept".
2368 /// \tparam _Graph It must be conform to the \ref concepts::Graph
2369 /// "Graph concept". The type can be specified to be const.
2370 /// \tparam _DirectionMap A bool valued edge map of the the adapted
2374 template<typename _Graph,
2375 typename DirectionMap = typename _Graph::template EdgeMap<bool> >
2377 public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > {
2379 typedef _Graph Graph;
2380 typedef DigraphAdaptorExtender<
2381 OrienterBase<_Graph, DirectionMap> > Parent;
2382 typedef typename Parent::Arc Arc;
2387 /// \brief Constructor of the adaptor
2389 /// Constructor of the adaptor
2390 Orienter(Graph& graph, DirectionMap& direction) {
2392 setDirectionMap(direction);
2395 /// \brief Reverse arc
2397 /// It reverse the given arc. It simply negate the direction in the map.
2398 void reverseArc(const Arc& a) {
2399 Parent::reverseArc(a);
2403 /// \brief Just gives back a Orienter
2405 /// Just gives back a Orienter
2406 template<typename Graph, typename DirectionMap>
2407 Orienter<const Graph, DirectionMap>
2408 orienter(const Graph& graph, DirectionMap& dm) {
2409 return Orienter<const Graph, DirectionMap>(graph, dm);
2412 template<typename Graph, typename DirectionMap>
2413 Orienter<const Graph, const DirectionMap>
2414 orienter(const Graph& graph, const DirectionMap& dm) {
2415 return Orienter<const Graph, const DirectionMap>(graph, dm);
2418 namespace _adaptor_bits {
2420 template<typename _Digraph,
2421 typename _CapacityMap = typename _Digraph::template ArcMap<int>,
2422 typename _FlowMap = _CapacityMap,
2423 typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
2424 class ResForwardFilter {
2427 typedef _Digraph Digraph;
2428 typedef _CapacityMap CapacityMap;
2429 typedef _FlowMap FlowMap;
2430 typedef _Tolerance Tolerance;
2432 typedef typename Digraph::Arc Key;
2437 const CapacityMap* _capacity;
2438 const FlowMap* _flow;
2439 Tolerance _tolerance;
2442 ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,
2443 const Tolerance& tolerance = Tolerance())
2444 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
2446 bool operator[](const typename Digraph::Arc& a) const {
2447 return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
2451 template<typename _Digraph,
2452 typename _CapacityMap = typename _Digraph::template ArcMap<int>,
2453 typename _FlowMap = _CapacityMap,
2454 typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
2455 class ResBackwardFilter {
2458 typedef _Digraph Digraph;
2459 typedef _CapacityMap CapacityMap;
2460 typedef _FlowMap FlowMap;
2461 typedef _Tolerance Tolerance;
2463 typedef typename Digraph::Arc Key;
2468 const CapacityMap* _capacity;
2469 const FlowMap* _flow;
2470 Tolerance _tolerance;
2474 ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,
2475 const Tolerance& tolerance = Tolerance())
2476 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
2478 bool operator[](const typename Digraph::Arc& a) const {
2479 return _tolerance.positive((*_flow)[a]);
2485 /// \ingroup graph_adaptors
2487 /// \brief An adaptor for composing the residual graph for directed
2488 /// flow and circulation problems.
2490 /// An adaptor for composing the residual graph for directed flow and
2491 /// circulation problems. Let \f$ G=(V, A) \f$ be a directed graph
2492 /// and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
2493 /// be functions on the arc-set.
2495 /// Then Residual implements the digraph structure with
2496 /// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward} \f$,
2497 /// where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
2498 /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so
2499 /// called residual graph. When we take the union
2500 /// \f$ A_{forward}\cup A_{backward} \f$, multiplicities are counted,
2501 /// i.e. if an arc is in both \f$ A_{forward} \f$ and
2502 /// \f$ A_{backward} \f$, then in the adaptor it appears in both
2505 /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
2506 /// "Digraph concept". The type is implicitly const.
2507 /// \tparam _CapacityMap An arc map of some numeric type, it defines
2508 /// the capacities in the flow problem. The map is implicitly const.
2509 /// \tparam _FlowMap An arc map of some numeric type, it defines
2510 /// the capacities in the flow problem.
2511 /// \tparam _Tolerance Handler for inexact computation.
2512 template<typename _Digraph,
2513 typename _CapacityMap = typename _Digraph::template ArcMap<int>,
2514 typename _FlowMap = _CapacityMap,
2515 typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
2518 Undirector<const _Digraph>,
2519 typename Undirector<const _Digraph>::template CombinedArcMap<
2520 _adaptor_bits::ResForwardFilter<const _Digraph, _CapacityMap,
2521 _FlowMap, _Tolerance>,
2522 _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap,
2523 _FlowMap, _Tolerance> > >
2527 typedef _Digraph Digraph;
2528 typedef _CapacityMap CapacityMap;
2529 typedef _FlowMap FlowMap;
2530 typedef _Tolerance Tolerance;
2532 typedef typename CapacityMap::Value Value;
2533 typedef Residual Adaptor;
2537 typedef Undirector<const Digraph> Undirected;
2539 typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap,
2540 FlowMap, Tolerance> ForwardFilter;
2542 typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap,
2543 FlowMap, Tolerance> BackwardFilter;
2545 typedef typename Undirected::
2546 template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
2548 typedef FilterArcs<Undirected, ArcFilter> Parent;
2550 const CapacityMap* _capacity;
2554 ForwardFilter _forward_filter;
2555 BackwardFilter _backward_filter;
2556 ArcFilter _arc_filter;
2560 /// \brief Constructor of the residual digraph.
2562 /// Constructor of the residual graph. The parameters are the digraph,
2563 /// the flow map, the capacity map and a tolerance object.
2564 Residual(const Digraph& digraph, const CapacityMap& capacity,
2565 FlowMap& flow, const Tolerance& tolerance = Tolerance())
2566 : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
2567 _forward_filter(capacity, flow, tolerance),
2568 _backward_filter(capacity, flow, tolerance),
2569 _arc_filter(_forward_filter, _backward_filter)
2571 Parent::setDigraph(_graph);
2572 Parent::setArcFilterMap(_arc_filter);
2575 typedef typename Parent::Arc Arc;
2577 /// \brief Gives back the residual capacity of the arc.
2579 /// Gives back the residual capacity of the arc.
2580 Value residualCapacity(const Arc& a) const {
2581 if (Undirected::direction(a)) {
2582 return (*_capacity)[a] - (*_flow)[a];
2588 /// \brief Augment on the given arc in the residual graph.
2590 /// Augment on the given arc in the residual graph. It increase
2591 /// or decrease the flow on the original arc depend on the direction
2592 /// of the residual arc.
2593 void augment(const Arc& a, const Value& v) const {
2594 if (Undirected::direction(a)) {
2595 _flow->set(a, (*_flow)[a] + v);
2597 _flow->set(a, (*_flow)[a] - v);
2601 /// \brief Returns the direction of the arc.
2603 /// Returns true when the arc is same oriented as the original arc.
2604 static bool forward(const Arc& a) {
2605 return Undirected::direction(a);
2608 /// \brief Returns the direction of the arc.
2610 /// Returns true when the arc is opposite oriented as the original arc.
2611 static bool backward(const Arc& a) {
2612 return !Undirected::direction(a);
2615 /// \brief Gives back the forward oriented residual arc.
2617 /// Gives back the forward oriented residual arc.
2618 static Arc forward(const typename Digraph::Arc& a) {
2619 return Undirected::direct(a, true);
2622 /// \brief Gives back the backward oriented residual arc.
2624 /// Gives back the backward oriented residual arc.
2625 static Arc backward(const typename Digraph::Arc& a) {
2626 return Undirected::direct(a, false);
2629 /// \brief Residual capacity map.
2631 /// In generic residual graph the residual capacity can be obtained
2633 class ResidualCapacity {
2635 const Adaptor* _adaptor;
2640 typedef typename _CapacityMap::Value Value;
2643 ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}
2646 Value operator[](const Arc& a) const {
2647 return _adaptor->residualCapacity(a);
2654 template <typename _Digraph>
2655 class SplitNodesBase {
2658 typedef _Digraph Digraph;
2659 typedef DigraphAdaptorBase<const _Digraph> Parent;
2660 typedef SplitNodesBase Adaptor;
2662 typedef typename Digraph::Node DigraphNode;
2663 typedef typename Digraph::Arc DigraphArc;
2670 template <typename T> class NodeMapBase;
2671 template <typename T> class ArcMapBase;
2675 class Node : public DigraphNode {
2676 friend class SplitNodesBase;
2677 template <typename T> friend class NodeMapBase;
2681 Node(DigraphNode node, bool in)
2682 : DigraphNode(node), _in(in) {}
2687 Node(Invalid) : DigraphNode(INVALID), _in(true) {}
2689 bool operator==(const Node& node) const {
2690 return DigraphNode::operator==(node) && _in == node._in;
2693 bool operator!=(const Node& node) const {
2694 return !(*this == node);
2697 bool operator<(const Node& node) const {
2698 return DigraphNode::operator<(node) ||
2699 (DigraphNode::operator==(node) && _in < node._in);
2704 friend class SplitNodesBase;
2705 template <typename T> friend class ArcMapBase;
2707 typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;
2709 explicit Arc(const DigraphArc& arc) : _item(arc) {}
2710 explicit Arc(const DigraphNode& node) : _item(node) {}
2716 Arc(Invalid) : _item(DigraphArc(INVALID)) {}
2718 bool operator==(const Arc& arc) const {
2719 if (_item.firstState()) {
2720 if (arc._item.firstState()) {
2721 return _item.first() == arc._item.first();
2724 if (arc._item.secondState()) {
2725 return _item.second() == arc._item.second();
2731 bool operator!=(const Arc& arc) const {
2732 return !(*this == arc);
2735 bool operator<(const Arc& arc) const {
2736 if (_item.firstState()) {
2737 if (arc._item.firstState()) {
2738 return _item.first() < arc._item.first();
2742 if (arc._item.secondState()) {
2743 return _item.second() < arc._item.second();
2749 operator DigraphArc() const { return _item.first(); }
2750 operator DigraphNode() const { return _item.second(); }
2754 void first(Node& n) const {
2759 void next(Node& n) const {
2768 void first(Arc& e) const {
2769 e._item.setSecond();
2770 _digraph->first(e._item.second());
2771 if (e._item.second() == INVALID) {
2773 _digraph->first(e._item.first());
2777 void next(Arc& e) const {
2778 if (e._item.secondState()) {
2779 _digraph->next(e._item.second());
2780 if (e._item.second() == INVALID) {
2782 _digraph->first(e._item.first());
2785 _digraph->next(e._item.first());
2789 void firstOut(Arc& e, const Node& n) const {
2791 e._item.setSecond(n);
2794 _digraph->firstOut(e._item.first(), n);
2798 void nextOut(Arc& e) const {
2799 if (!e._item.firstState()) {
2800 e._item.setFirst(INVALID);
2802 _digraph->nextOut(e._item.first());
2806 void firstIn(Arc& e, const Node& n) const {
2808 e._item.setSecond(n);
2811 _digraph->firstIn(e._item.first(), n);
2815 void nextIn(Arc& e) const {
2816 if (!e._item.firstState()) {
2817 e._item.setFirst(INVALID);
2819 _digraph->nextIn(e._item.first());
2823 Node source(const Arc& e) const {
2824 if (e._item.firstState()) {
2825 return Node(_digraph->source(e._item.first()), false);
2827 return Node(e._item.second(), true);
2831 Node target(const Arc& e) const {
2832 if (e._item.firstState()) {
2833 return Node(_digraph->target(e._item.first()), true);
2835 return Node(e._item.second(), false);
2839 int id(const Node& n) const {
2840 return (_digraph->id(n) << 1) | (n._in ? 0 : 1);
2842 Node nodeFromId(int ix) const {
2843 return Node(_digraph->nodeFromId(ix >> 1), (ix & 1) == 0);
2845 int maxNodeId() const {
2846 return 2 * _digraph->maxNodeId() + 1;
2849 int id(const Arc& e) const {
2850 if (e._item.firstState()) {
2851 return _digraph->id(e._item.first()) << 1;
2853 return (_digraph->id(e._item.second()) << 1) | 1;
2856 Arc arcFromId(int ix) const {
2857 if ((ix & 1) == 0) {
2858 return Arc(_digraph->arcFromId(ix >> 1));
2860 return Arc(_digraph->nodeFromId(ix >> 1));
2863 int maxArcId() const {
2864 return std::max(_digraph->maxNodeId() << 1,
2865 (_digraph->maxArcId() << 1) | 1);
2868 static bool inNode(const Node& n) {
2872 static bool outNode(const Node& n) {
2876 static bool origArc(const Arc& e) {
2877 return e._item.firstState();
2880 static bool bindArc(const Arc& e) {
2881 return e._item.secondState();
2884 static Node inNode(const DigraphNode& n) {
2885 return Node(n, true);
2888 static Node outNode(const DigraphNode& n) {
2889 return Node(n, false);
2892 static Arc arc(const DigraphNode& n) {
2896 static Arc arc(const DigraphArc& e) {
2900 typedef True NodeNumTag;
2901 int nodeNum() const {
2902 return 2 * countNodes(*_digraph);
2905 typedef True ArcNumTag;
2906 int arcNum() const {
2907 return countArcs(*_digraph) + countNodes(*_digraph);
2910 typedef True FindArcTag;
2911 Arc findArc(const Node& u, const Node& v,
2912 const Arc& prev = INVALID) const {
2915 if (static_cast<const DigraphNode&>(u) ==
2916 static_cast<const DigraphNode&>(v) && prev == INVALID) {
2922 return Arc(::lemon::findArc(*_digraph, u, v, prev));
2930 template <typename _Value>
2932 : public MapTraits<typename Parent::template NodeMap<_Value> > {
2933 typedef typename Parent::template NodeMap<_Value> NodeImpl;
2936 typedef _Value Value;
2938 NodeMapBase(const Adaptor& adaptor)
2939 : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
2940 NodeMapBase(const Adaptor& adaptor, const Value& value)
2941 : _in_map(*adaptor._digraph, value),
2942 _out_map(*adaptor._digraph, value) {}
2944 void set(const Node& key, const Value& val) {
2945 if (Adaptor::inNode(key)) { _in_map.set(key, val); }
2946 else {_out_map.set(key, val); }
2949 typename MapTraits<NodeImpl>::ReturnValue
2950 operator[](const Node& key) {
2951 if (Adaptor::inNode(key)) { return _in_map[key]; }
2952 else { return _out_map[key]; }
2955 typename MapTraits<NodeImpl>::ConstReturnValue
2956 operator[](const Node& key) const {
2957 if (Adaptor::inNode(key)) { return _in_map[key]; }
2958 else { return _out_map[key]; }
2962 NodeImpl _in_map, _out_map;
2965 template <typename _Value>
2967 : public MapTraits<typename Parent::template ArcMap<_Value> > {
2968 typedef typename Parent::template ArcMap<_Value> ArcImpl;
2969 typedef typename Parent::template NodeMap<_Value> NodeImpl;
2972 typedef _Value Value;
2974 ArcMapBase(const Adaptor& adaptor)
2975 : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
2976 ArcMapBase(const Adaptor& adaptor, const Value& value)
2977 : _arc_map(*adaptor._digraph, value),
2978 _node_map(*adaptor._digraph, value) {}
2980 void set(const Arc& key, const Value& val) {
2981 if (Adaptor::origArc(key)) {
2982 _arc_map.set(key._item.first(), val);
2984 _node_map.set(key._item.second(), val);
2988 typename MapTraits<ArcImpl>::ReturnValue
2989 operator[](const Arc& key) {
2990 if (Adaptor::origArc(key)) {
2991 return _arc_map[key._item.first()];
2993 return _node_map[key._item.second()];
2997 typename MapTraits<ArcImpl>::ConstReturnValue
2998 operator[](const Arc& key) const {
2999 if (Adaptor::origArc(key)) {
3000 return _arc_map[key._item.first()];
3002 return _node_map[key._item.second()];
3013 template <typename _Value>
3015 : public SubMapExtender<Adaptor, NodeMapBase<_Value> >
3018 typedef _Value Value;
3019 typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent;
3021 NodeMap(const Adaptor& adaptor)
3022 : Parent(adaptor) {}
3024 NodeMap(const Adaptor& adaptor, const Value& value)
3025 : Parent(adaptor, value) {}
3028 NodeMap& operator=(const NodeMap& cmap) {
3029 return operator=<NodeMap>(cmap);
3032 template <typename CMap>
3033 NodeMap& operator=(const CMap& cmap) {
3034 Parent::operator=(cmap);
3039 template <typename _Value>
3041 : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
3044 typedef _Value Value;
3045 typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
3047 ArcMap(const Adaptor& adaptor)
3048 : Parent(adaptor) {}
3050 ArcMap(const Adaptor& adaptor, const Value& value)
3051 : Parent(adaptor, value) {}
3054 ArcMap& operator=(const ArcMap& cmap) {
3055 return operator=<ArcMap>(cmap);
3058 template <typename CMap>
3059 ArcMap& operator=(const CMap& cmap) {
3060 Parent::operator=(cmap);
3067 SplitNodesBase() : _digraph(0) {}
3071 void setDigraph(Digraph& digraph) {
3072 _digraph = &digraph;
3077 /// \ingroup graph_adaptors
3079 /// \brief Split the nodes of a directed graph
3081 /// The SplitNodes adaptor splits each node into an in-node and an
3082 /// out-node. Formaly, the adaptor replaces each \f$ u \f$ node in
3083 /// the digraph with two nodes(namely node \f$ u_{in} \f$ and node
3084 /// \f$ u_{out} \f$). If there is a \f$ (v, u) \f$ arc in the
3085 /// original digraph the new target of the arc will be \f$ u_{in} \f$
3086 /// and similarly the source of the original \f$ (u, v) \f$ arc
3087 /// will be \f$ u_{out} \f$. The adaptor will add for each node in
3088 /// the original digraph an additional arc which connects
3089 /// \f$ (u_{in}, u_{out}) \f$.
3091 /// The aim of this class is to run algorithm with node costs if the
3092 /// algorithm can use directly just arc costs. In this case we should use
3093 /// a \c SplitNodes and set the node cost of the graph to the
3094 /// bind arc in the adapted graph.
3096 /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
3097 /// "Digraph concept". The type can be specified to be const.
3098 template <typename _Digraph>
3100 : public DigraphAdaptorExtender<SplitNodesBase<_Digraph> > {
3102 typedef _Digraph Digraph;
3103 typedef DigraphAdaptorExtender<SplitNodesBase<Digraph> > Parent;
3105 typedef typename Digraph::Node DigraphNode;
3106 typedef typename Digraph::Arc DigraphArc;
3108 typedef typename Parent::Node Node;
3109 typedef typename Parent::Arc Arc;
3111 /// \brief Constructor of the adaptor.
3113 /// Constructor of the adaptor.
3114 SplitNodes(Digraph& g) {
3115 Parent::setDigraph(g);
3118 /// \brief Returns true when the node is in-node.
3120 /// Returns true when the node is in-node.
3121 static bool inNode(const Node& n) {
3122 return Parent::inNode(n);
3125 /// \brief Returns true when the node is out-node.
3127 /// Returns true when the node is out-node.
3128 static bool outNode(const Node& n) {
3129 return Parent::outNode(n);
3132 /// \brief Returns true when the arc is arc in the original digraph.
3134 /// Returns true when the arc is arc in the original digraph.
3135 static bool origArc(const Arc& a) {
3136 return Parent::origArc(a);
3139 /// \brief Returns true when the arc binds an in-node and an out-node.
3141 /// Returns true when the arc binds an in-node and an out-node.
3142 static bool bindArc(const Arc& a) {
3143 return Parent::bindArc(a);
3146 /// \brief Gives back the in-node created from the \c node.
3148 /// Gives back the in-node created from the \c node.
3149 static Node inNode(const DigraphNode& n) {
3150 return Parent::inNode(n);
3153 /// \brief Gives back the out-node created from the \c node.
3155 /// Gives back the out-node created from the \c node.
3156 static Node outNode(const DigraphNode& n) {
3157 return Parent::outNode(n);
3160 /// \brief Gives back the arc binds the two part of the node.
3162 /// Gives back the arc binds the two part of the node.
3163 static Arc arc(const DigraphNode& n) {
3164 return Parent::arc(n);
3167 /// \brief Gives back the arc of the original arc.
3169 /// Gives back the arc of the original arc.
3170 static Arc arc(const DigraphArc& a) {
3171 return Parent::arc(a);
3174 /// \brief NodeMap combined from two original NodeMap
3176 /// This class adapt two of the original digraph NodeMap to
3177 /// get a node map on the adapted digraph.
3178 template <typename InNodeMap, typename OutNodeMap>
3179 class CombinedNodeMap {
3183 typedef typename InNodeMap::Value Value;
3185 /// \brief Constructor
3188 CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
3189 : _in_map(in_map), _out_map(out_map) {}
3191 /// \brief The subscript operator.
3193 /// The subscript operator.
3194 Value& operator[](const Key& key) {
3195 if (Parent::inNode(key)) {
3196 return _in_map[key];
3198 return _out_map[key];
3202 /// \brief The const subscript operator.
3204 /// The const subscript operator.
3205 Value operator[](const Key& key) const {
3206 if (Parent::inNode(key)) {
3207 return _in_map[key];
3209 return _out_map[key];
3213 /// \brief The setter function of the map.
3215 /// The setter function of the map.
3216 void set(const Key& key, const Value& value) {
3217 if (Parent::inNode(key)) {
3218 _in_map.set(key, value);
3220 _out_map.set(key, value);
3227 OutNodeMap& _out_map;
3232 /// \brief Just gives back a combined node map
3234 /// Just gives back a combined node map
3235 template <typename InNodeMap, typename OutNodeMap>
3236 static CombinedNodeMap<InNodeMap, OutNodeMap>
3237 combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
3238 return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
3241 template <typename InNodeMap, typename OutNodeMap>
3242 static CombinedNodeMap<const InNodeMap, OutNodeMap>
3243 combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
3244 return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
3247 template <typename InNodeMap, typename OutNodeMap>
3248 static CombinedNodeMap<InNodeMap, const OutNodeMap>
3249 combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
3250 return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
3253 template <typename InNodeMap, typename OutNodeMap>
3254 static CombinedNodeMap<const InNodeMap, const OutNodeMap>
3255 combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
3256 return CombinedNodeMap<const InNodeMap,
3257 const OutNodeMap>(in_map, out_map);
3260 /// \brief ArcMap combined from an original ArcMap and a NodeMap
3262 /// This class adapt an original ArcMap and a NodeMap to get an
3263 /// arc map on the adapted digraph
3264 template <typename DigraphArcMap, typename DigraphNodeMap>
3265 class CombinedArcMap {
3269 typedef typename DigraphArcMap::Value Value;
3271 /// \brief Constructor
3274 CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)
3275 : _arc_map(arc_map), _node_map(node_map) {}
3277 /// \brief The subscript operator.
3279 /// The subscript operator.
3280 void set(const Arc& arc, const Value& val) {
3281 if (Parent::origArc(arc)) {
3282 _arc_map.set(arc, val);
3284 _node_map.set(arc, val);
3288 /// \brief The const subscript operator.
3290 /// The const subscript operator.
3291 Value operator[](const Key& arc) const {
3292 if (Parent::origArc(arc)) {
3293 return _arc_map[arc];
3295 return _node_map[arc];
3299 /// \brief The const subscript operator.
3301 /// The const subscript operator.
3302 Value& operator[](const Key& arc) {
3303 if (Parent::origArc(arc)) {
3304 return _arc_map[arc];
3306 return _node_map[arc];
3311 DigraphArcMap& _arc_map;
3312 DigraphNodeMap& _node_map;
3315 /// \brief Just gives back a combined arc map
3317 /// Just gives back a combined arc map
3318 template <typename DigraphArcMap, typename DigraphNodeMap>
3319 static CombinedArcMap<DigraphArcMap, DigraphNodeMap>
3320 combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
3321 return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map);
3324 template <typename DigraphArcMap, typename DigraphNodeMap>
3325 static CombinedArcMap<const DigraphArcMap, DigraphNodeMap>
3326 combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
3327 return CombinedArcMap<const DigraphArcMap,
3328 DigraphNodeMap>(arc_map, node_map);
3331 template <typename DigraphArcMap, typename DigraphNodeMap>
3332 static CombinedArcMap<DigraphArcMap, const DigraphNodeMap>
3333 combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) {
3334 return CombinedArcMap<DigraphArcMap,
3335 const DigraphNodeMap>(arc_map, node_map);
3338 template <typename DigraphArcMap, typename DigraphNodeMap>
3339 static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap>
3340 combinedArcMap(const DigraphArcMap& arc_map,
3341 const DigraphNodeMap& node_map) {
3342 return CombinedArcMap<const DigraphArcMap,
3343 const DigraphNodeMap>(arc_map, node_map);
3348 /// \brief Just gives back a node splitter
3350 /// Just gives back a node splitter
3351 template<typename Digraph>
3353 splitNodes(const Digraph& digraph) {
3354 return SplitNodes<Digraph>(digraph);
3360 #endif //LEMON_ADAPTORS_H