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_DIGRAPH_ADAPTOR_H
20 #define LEMON_DIGRAPH_ADAPTOR_H
22 ///\ingroup graph_adaptors
24 ///\brief Several digraph adaptors.
26 ///This file contains several useful digraph adaptor classes.
28 #include <lemon/core.h>
29 #include <lemon/maps.h>
30 #include <lemon/bits/variant.h>
32 #include <lemon/bits/base_extender.h>
33 #include <lemon/bits/graph_adaptor_extender.h>
34 #include <lemon/bits/graph_extender.h>
35 #include <lemon/tolerance.h>
41 template<typename _Digraph>
42 class DigraphAdaptorBase {
44 typedef _Digraph Digraph;
45 typedef DigraphAdaptorBase Adaptor;
46 typedef Digraph ParentDigraph;
50 DigraphAdaptorBase() : _digraph(0) { }
51 void setDigraph(Digraph& digraph) { _digraph = &digraph; }
54 DigraphAdaptorBase(Digraph& digraph) : _digraph(&digraph) { }
56 typedef typename Digraph::Node Node;
57 typedef typename Digraph::Arc Arc;
59 void first(Node& i) const { _digraph->first(i); }
60 void first(Arc& i) const { _digraph->first(i); }
61 void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); }
62 void firstOut(Arc& i, const Node& n ) const { _digraph->firstOut(i, n); }
64 void next(Node& i) const { _digraph->next(i); }
65 void next(Arc& i) const { _digraph->next(i); }
66 void nextIn(Arc& i) const { _digraph->nextIn(i); }
67 void nextOut(Arc& i) const { _digraph->nextOut(i); }
69 Node source(const Arc& a) const { return _digraph->source(a); }
70 Node target(const Arc& a) const { return _digraph->target(a); }
72 typedef NodeNumTagIndicator<Digraph> NodeNumTag;
73 int nodeNum() const { return _digraph->nodeNum(); }
75 typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
76 int arcNum() const { return _digraph->arcNum(); }
78 typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
79 Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
80 return _digraph->findArc(u, v, prev);
83 Node addNode() { return _digraph->addNode(); }
84 Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
86 void erase(const Node& n) const { _digraph->erase(n); }
87 void erase(const Arc& a) const { _digraph->erase(a); }
89 void clear() const { _digraph->clear(); }
91 int id(const Node& n) const { return _digraph->id(n); }
92 int id(const Arc& a) const { return _digraph->id(a); }
94 Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
95 Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); }
97 int maxNodeId() const { return _digraph->maxNodeId(); }
98 int maxArcId() const { return _digraph->maxArcId(); }
100 typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
101 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
103 typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier;
104 ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
106 template <typename _Value>
107 class NodeMap : public Digraph::template NodeMap<_Value> {
110 typedef typename Digraph::template NodeMap<_Value> Parent;
112 explicit NodeMap(const Adaptor& adaptor)
113 : Parent(*adaptor._digraph) {}
115 NodeMap(const Adaptor& adaptor, const _Value& value)
116 : Parent(*adaptor._digraph, value) { }
119 NodeMap& operator=(const NodeMap& cmap) {
120 return operator=<NodeMap>(cmap);
123 template <typename CMap>
124 NodeMap& operator=(const CMap& cmap) {
125 Parent::operator=(cmap);
131 template <typename _Value>
132 class ArcMap : public Digraph::template ArcMap<_Value> {
135 typedef typename Digraph::template ArcMap<_Value> Parent;
137 explicit ArcMap(const Adaptor& adaptor)
138 : Parent(*adaptor._digraph) {}
140 ArcMap(const Adaptor& adaptor, const _Value& value)
141 : Parent(*adaptor._digraph, value) {}
144 ArcMap& operator=(const ArcMap& cmap) {
145 return operator=<ArcMap>(cmap);
148 template <typename CMap>
149 ArcMap& operator=(const CMap& cmap) {
150 Parent::operator=(cmap);
159 template <typename _Digraph>
160 class RevDigraphAdaptorBase : public DigraphAdaptorBase<_Digraph> {
162 typedef _Digraph Digraph;
163 typedef DigraphAdaptorBase<_Digraph> Parent;
165 RevDigraphAdaptorBase() : Parent() { }
167 typedef typename Parent::Node Node;
168 typedef typename Parent::Arc Arc;
170 void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }
171 void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); }
173 void nextIn(Arc& a) const { Parent::nextOut(a); }
174 void nextOut(Arc& a) const { Parent::nextIn(a); }
176 Node source(const Arc& a) const { return Parent::target(a); }
177 Node target(const Arc& a) const { return Parent::source(a); }
179 typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
180 Arc findArc(const Node& u, const Node& v,
181 const Arc& prev = INVALID) {
182 return Parent::findArc(v, u, prev);
188 ///\ingroup graph_adaptors
190 ///\brief A digraph adaptor which reverses the orientation of the arcs.
192 /// If \c g is defined as
198 /// RevDigraphAdaptor<ListDigraph> dga(dg);
200 /// implements the digraph obtained from \c dg by
201 /// reversing the orientation of its arcs.
203 /// A good example of using RevDigraphAdaptor is to decide whether
204 /// the directed graph is strongly connected or not. The digraph is
205 /// strongly connected iff each node is reachable from one node and
206 /// this node is reachable from the others. Instead of this
207 /// condition we use a slightly different, from one node each node
208 /// is reachable both in the digraph and the reversed digraph. Now
209 /// this condition can be checked with the Dfs algorithm and the
210 /// RevDigraphAdaptor class.
212 /// The implementation:
214 /// bool stronglyConnected(const Digraph& digraph) {
215 /// if (NodeIt(digraph) == INVALID) return true;
216 /// Dfs<Digraph> dfs(digraph);
217 /// dfs.run(NodeIt(digraph));
218 /// for (NodeIt it(digraph); it != INVALID; ++it) {
219 /// if (!dfs.reached(it)) {
223 /// typedef RevDigraphAdaptor<const Digraph> RDigraph;
224 /// RDigraph rdigraph(digraph);
225 /// DfsVisit<RDigraph> rdfs(rdigraph);
226 /// rdfs.run(NodeIt(digraph));
227 /// for (NodeIt it(digraph); it != INVALID; ++it) {
228 /// if (!rdfs.reached(it)) {
235 template<typename _Digraph>
236 class RevDigraphAdaptor :
237 public DigraphAdaptorExtender<RevDigraphAdaptorBase<_Digraph> > {
239 typedef _Digraph Digraph;
240 typedef DigraphAdaptorExtender<
241 RevDigraphAdaptorBase<_Digraph> > Parent;
243 RevDigraphAdaptor() { }
246 /// \brief Constructor
248 /// Creates a reverse graph adaptor for the given digraph
249 explicit RevDigraphAdaptor(Digraph& digraph) {
250 Parent::setDigraph(digraph);
254 /// \brief Just gives back a reverse digraph adaptor
256 /// Just gives back a reverse digraph adaptor
257 template<typename Digraph>
258 RevDigraphAdaptor<const Digraph>
259 revDigraphAdaptor(const Digraph& digraph) {
260 return RevDigraphAdaptor<const Digraph>(digraph);
263 template <typename _Digraph, typename _NodeFilterMap,
264 typename _ArcFilterMap, bool checked = true>
265 class SubDigraphAdaptorBase : public DigraphAdaptorBase<_Digraph> {
267 typedef _Digraph Digraph;
268 typedef _NodeFilterMap NodeFilterMap;
269 typedef _ArcFilterMap ArcFilterMap;
271 typedef SubDigraphAdaptorBase Adaptor;
272 typedef DigraphAdaptorBase<_Digraph> Parent;
274 NodeFilterMap* _node_filter;
275 ArcFilterMap* _arc_filter;
276 SubDigraphAdaptorBase()
277 : Parent(), _node_filter(0), _arc_filter(0) { }
279 void setNodeFilterMap(NodeFilterMap& node_filter) {
280 _node_filter = &node_filter;
282 void setArcFilterMap(ArcFilterMap& arc_filter) {
283 _arc_filter = &arc_filter;
288 typedef typename Parent::Node Node;
289 typedef typename Parent::Arc Arc;
291 void first(Node& i) const {
293 while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
296 void first(Arc& i) const {
298 while (i != INVALID && (!(*_arc_filter)[i]
299 || !(*_node_filter)[Parent::source(i)]
300 || !(*_node_filter)[Parent::target(i)])) Parent::next(i);
303 void firstIn(Arc& i, const Node& n) const {
304 Parent::firstIn(i, n);
305 while (i != INVALID && (!(*_arc_filter)[i]
306 || !(*_node_filter)[Parent::source(i)])) Parent::nextIn(i);
309 void firstOut(Arc& i, const Node& n) const {
310 Parent::firstOut(i, n);
311 while (i != INVALID && (!(*_arc_filter)[i]
312 || !(*_node_filter)[Parent::target(i)])) Parent::nextOut(i);
315 void next(Node& i) const {
317 while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
320 void next(Arc& i) const {
322 while (i != INVALID && (!(*_arc_filter)[i]
323 || !(*_node_filter)[Parent::source(i)]
324 || !(*_node_filter)[Parent::target(i)])) Parent::next(i);
327 void nextIn(Arc& i) const {
329 while (i != INVALID && (!(*_arc_filter)[i]
330 || !(*_node_filter)[Parent::source(i)])) Parent::nextIn(i);
333 void nextOut(Arc& i) const {
335 while (i != INVALID && (!(*_arc_filter)[i]
336 || !(*_node_filter)[Parent::target(i)])) Parent::nextOut(i);
339 void hide(const Node& n) const { _node_filter->set(n, false); }
340 void hide(const Arc& a) const { _arc_filter->set(a, false); }
342 void unHide(const Node& n) const { _node_filter->set(n, true); }
343 void unHide(const Arc& a) const { _arc_filter->set(a, true); }
345 bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
346 bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }
348 typedef False NodeNumTag;
349 typedef False EdgeNumTag;
351 typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
352 Arc findArc(const Node& source, const Node& target,
353 const Arc& prev = INVALID) {
354 if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
357 Arc arc = Parent::findArc(source, target, prev);
358 while (arc != INVALID && !(*_arc_filter)[arc]) {
359 arc = Parent::findArc(source, target, arc);
364 template <typename _Value>
365 class NodeMap : public SubMapExtender<Adaptor,
366 typename Parent::template NodeMap<_Value> > {
368 typedef _Value Value;
369 typedef SubMapExtender<Adaptor, typename Parent::
370 template NodeMap<Value> > MapParent;
372 NodeMap(const Adaptor& adaptor)
373 : MapParent(adaptor) {}
374 NodeMap(const Adaptor& adaptor, const Value& value)
375 : MapParent(adaptor, value) {}
378 NodeMap& operator=(const NodeMap& cmap) {
379 return operator=<NodeMap>(cmap);
382 template <typename CMap>
383 NodeMap& operator=(const CMap& cmap) {
384 MapParent::operator=(cmap);
389 template <typename _Value>
390 class ArcMap : public SubMapExtender<Adaptor,
391 typename Parent::template ArcMap<_Value> > {
393 typedef _Value Value;
394 typedef SubMapExtender<Adaptor, typename Parent::
395 template ArcMap<Value> > MapParent;
397 ArcMap(const Adaptor& adaptor)
398 : MapParent(adaptor) {}
399 ArcMap(const Adaptor& adaptor, const Value& value)
400 : MapParent(adaptor, value) {}
403 ArcMap& operator=(const ArcMap& cmap) {
404 return operator=<ArcMap>(cmap);
407 template <typename CMap>
408 ArcMap& operator=(const CMap& cmap) {
409 MapParent::operator=(cmap);
416 template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>
417 class SubDigraphAdaptorBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>
418 : public DigraphAdaptorBase<_Digraph> {
420 typedef _Digraph Digraph;
421 typedef _NodeFilterMap NodeFilterMap;
422 typedef _ArcFilterMap ArcFilterMap;
424 typedef SubDigraphAdaptorBase Adaptor;
425 typedef DigraphAdaptorBase<Digraph> Parent;
427 NodeFilterMap* _node_filter;
428 ArcFilterMap* _arc_filter;
429 SubDigraphAdaptorBase()
430 : Parent(), _node_filter(0), _arc_filter(0) { }
432 void setNodeFilterMap(NodeFilterMap& node_filter) {
433 _node_filter = &node_filter;
435 void setArcFilterMap(ArcFilterMap& arc_filter) {
436 _arc_filter = &arc_filter;
441 typedef typename Parent::Node Node;
442 typedef typename Parent::Arc Arc;
444 void first(Node& i) const {
446 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
449 void first(Arc& i) const {
451 while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
454 void firstIn(Arc& i, const Node& n) const {
455 Parent::firstIn(i, n);
456 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
459 void firstOut(Arc& i, const Node& n) const {
460 Parent::firstOut(i, n);
461 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
464 void next(Node& i) const {
466 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
468 void next(Arc& i) const {
470 while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
472 void nextIn(Arc& i) const {
474 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
477 void nextOut(Arc& i) const {
479 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
482 void hide(const Node& n) const { _node_filter->set(n, false); }
483 void hide(const Arc& e) const { _arc_filter->set(e, false); }
485 void unHide(const Node& n) const { _node_filter->set(n, true); }
486 void unHide(const Arc& e) const { _arc_filter->set(e, true); }
488 bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
489 bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }
491 typedef False NodeNumTag;
492 typedef False EdgeNumTag;
494 typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
495 Arc findArc(const Node& source, const Node& target,
496 const Arc& prev = INVALID) {
497 if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
500 Arc arc = Parent::findArc(source, target, prev);
501 while (arc != INVALID && !(*_arc_filter)[arc]) {
502 arc = Parent::findArc(source, target, arc);
507 template <typename _Value>
508 class NodeMap : public SubMapExtender<Adaptor,
509 typename Parent::template NodeMap<_Value> > {
511 typedef _Value Value;
512 typedef SubMapExtender<Adaptor, typename Parent::
513 template NodeMap<Value> > MapParent;
515 NodeMap(const Adaptor& adaptor)
516 : MapParent(adaptor) {}
517 NodeMap(const Adaptor& adaptor, const Value& value)
518 : MapParent(adaptor, value) {}
521 NodeMap& operator=(const NodeMap& cmap) {
522 return operator=<NodeMap>(cmap);
525 template <typename CMap>
526 NodeMap& operator=(const CMap& cmap) {
527 MapParent::operator=(cmap);
532 template <typename _Value>
533 class ArcMap : public SubMapExtender<Adaptor,
534 typename Parent::template ArcMap<_Value> > {
536 typedef _Value Value;
537 typedef SubMapExtender<Adaptor, typename Parent::
538 template ArcMap<Value> > MapParent;
540 ArcMap(const Adaptor& adaptor)
541 : MapParent(adaptor) {}
542 ArcMap(const Adaptor& adaptor, const Value& value)
543 : MapParent(adaptor, value) {}
546 ArcMap& operator=(const ArcMap& cmap) {
547 return operator=<ArcMap>(cmap);
550 template <typename CMap>
551 ArcMap& operator=(const CMap& cmap) {
552 MapParent::operator=(cmap);
559 /// \ingroup graph_adaptors
561 /// \brief A digraph adaptor for hiding nodes and arcs from a digraph.
563 /// SubDigraphAdaptor shows the digraph with filtered node-set and
564 /// arc-set. If the \c checked parameter is true then it filters the arc-set
565 /// respect to the source and target.
567 /// If the \c checked template parameter is false then the
568 /// node-iterator cares only the filter on the node-set, and the
569 /// arc-iterator cares only the filter on the arc-set. Therefore
570 /// the arc-map have to filter all arcs which's source or target is
571 /// filtered by the node-filter.
573 /// typedef ListDigraph Digraph;
574 /// DIGRAPH_TYPEDEFS(Digraph);
576 /// Node u=g.addNode(); //node of id 0
577 /// Node v=g.addNode(); //node of id 1
578 /// Arc a=g.addArc(u, v); //arc of id 0
579 /// Arc f=g.addArc(v, u); //arc of id 1
580 /// BoolNodeMap nm(g, true);
581 /// nm.set(u, false);
582 /// BoolArcMap am(g, true);
583 /// am.set(a, false);
584 /// typedef SubDigraphAdaptor<Digraph, BoolNodeMap, BoolArcMap> SubDGA;
585 /// SubDGA ga(g, nm, am);
586 /// for (SubDGA::NodeIt n(ga); n!=INVALID; ++n)
587 /// std::cout << g.id(n) << std::endl;
588 /// for (SubDGA::ArcIt a(ga); a!=INVALID; ++a)
589 /// std::cout << g.id(a) << std::endl;
591 /// The output of the above code is the following.
596 /// Note that \c n is of type \c SubDGA::NodeIt, but it can be converted to
597 /// \c Digraph::Node that is why \c g.id(n) can be applied.
599 /// For other examples see also the documentation of
600 /// NodeSubDigraphAdaptor and ArcSubDigraphAdaptor.
601 template<typename _Digraph,
602 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
603 typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,
605 class SubDigraphAdaptor :
606 public DigraphAdaptorExtender<
607 SubDigraphAdaptorBase<_Digraph, _NodeFilterMap, _ArcFilterMap, checked> > {
609 typedef _Digraph Digraph;
610 typedef _NodeFilterMap NodeFilterMap;
611 typedef _ArcFilterMap ArcFilterMap;
613 typedef DigraphAdaptorExtender<
614 SubDigraphAdaptorBase<Digraph, NodeFilterMap, ArcFilterMap, checked> >
617 typedef typename Parent::Node Node;
618 typedef typename Parent::Arc Arc;
621 SubDigraphAdaptor() { }
624 /// \brief Constructor
626 /// Creates a sub-digraph-adaptor for the given digraph with
627 /// given node and arc map filters.
628 SubDigraphAdaptor(Digraph& digraph, NodeFilterMap& node_filter,
629 ArcFilterMap& arc_filter) {
631 setNodeFilterMap(node_filter);
632 setArcFilterMap(arc_filter);
635 /// \brief Hides the node of the graph
637 /// This function hides \c n in the digraph, i.e. the iteration
638 /// jumps over it. This is done by simply setting the value of \c n
639 /// to be false in the corresponding node-map.
640 void hide(const Node& n) const { Parent::hide(n); }
642 /// \brief Hides the arc of the graph
644 /// This function hides \c a in the digraph, i.e. the iteration
645 /// jumps over it. This is done by simply setting the value of \c a
646 /// to be false in the corresponding arc-map.
647 void hide(const Arc& a) const { Parent::hide(a); }
649 /// \brief Unhides the node of the graph
651 /// The value of \c n is set to be true in the node-map which stores
652 /// hide information. If \c n was hidden previuosly, then it is shown
654 void unHide(const Node& n) const { Parent::unHide(n); }
656 /// \brief Unhides the arc of the graph
658 /// The value of \c a is set to be true in the arc-map which stores
659 /// hide information. If \c a was hidden previuosly, then it is shown
661 void unHide(const Arc& a) const { Parent::unHide(a); }
663 /// \brief Returns true if \c n is hidden.
665 /// Returns true if \c n is hidden.
667 bool hidden(const Node& n) const { return Parent::hidden(n); }
669 /// \brief Returns true if \c a is hidden.
671 /// Returns true if \c a is hidden.
673 bool hidden(const Arc& a) const { return Parent::hidden(a); }
677 /// \brief Just gives back a sub-digraph-adaptor
679 /// Just gives back a sub-digraph-adaptor
680 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
681 SubDigraphAdaptor<const Digraph, NodeFilterMap, ArcFilterMap>
682 subDigraphAdaptor(const Digraph& digraph,
683 NodeFilterMap& nfm, ArcFilterMap& afm) {
684 return SubDigraphAdaptor<const Digraph, NodeFilterMap, ArcFilterMap>
688 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
689 SubDigraphAdaptor<const Digraph, const NodeFilterMap, ArcFilterMap>
690 subDigraphAdaptor(const Digraph& digraph,
691 NodeFilterMap& nfm, ArcFilterMap& afm) {
692 return SubDigraphAdaptor<const Digraph, const NodeFilterMap, ArcFilterMap>
696 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
697 SubDigraphAdaptor<const Digraph, NodeFilterMap, const ArcFilterMap>
698 subDigraphAdaptor(const Digraph& digraph,
699 NodeFilterMap& nfm, ArcFilterMap& afm) {
700 return SubDigraphAdaptor<const Digraph, NodeFilterMap, const ArcFilterMap>
704 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
705 SubDigraphAdaptor<const Digraph, const NodeFilterMap, const ArcFilterMap>
706 subDigraphAdaptor(const Digraph& digraph,
707 NodeFilterMap& nfm, ArcFilterMap& afm) {
708 return SubDigraphAdaptor<const Digraph, const NodeFilterMap,
709 const ArcFilterMap>(digraph, nfm, afm);
715 ///\ingroup graph_adaptors
717 ///\brief An adaptor for hiding nodes from a digraph.
719 ///An adaptor for hiding nodes from a digraph. This adaptor
720 ///specializes SubDigraphAdaptor in the way that only the node-set
721 ///can be filtered. In usual case the checked parameter is true, we
722 ///get the induced subgraph. But if the checked parameter is false
723 ///then we can filter only isolated nodes.
724 template<typename _Digraph,
725 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
727 class NodeSubDigraphAdaptor :
728 public SubDigraphAdaptor<_Digraph, _NodeFilterMap,
729 ConstMap<typename _Digraph::Arc, bool>, checked> {
732 typedef _Digraph Digraph;
733 typedef _NodeFilterMap NodeFilterMap;
735 typedef SubDigraphAdaptor<Digraph, NodeFilterMap,
736 ConstMap<typename Digraph::Arc, bool>, checked>
739 typedef typename Parent::Node Node;
742 ConstMap<typename Digraph::Arc, bool> const_true_map;
744 NodeSubDigraphAdaptor() : const_true_map(true) {
745 Parent::setArcFilterMap(const_true_map);
750 /// \brief Constructor
752 /// Creates a node-sub-digraph-adaptor for the given digraph with
753 /// given node map filter.
754 NodeSubDigraphAdaptor(Digraph& _digraph, NodeFilterMap& node_filter) :
755 Parent(), const_true_map(true) {
756 Parent::setDigraph(_digraph);
757 Parent::setNodeFilterMap(node_filter);
758 Parent::setArcFilterMap(const_true_map);
761 /// \brief Hides the node of the graph
763 /// This function hides \c n in the digraph, i.e. the iteration
764 /// jumps over it. This is done by simply setting the value of \c n
765 /// to be false in the corresponding node-map.
766 void hide(const Node& n) const { Parent::hide(n); }
768 /// \brief Unhides the node of the graph
770 /// The value of \c n is set to be true in the node-map which stores
771 /// hide information. If \c n was hidden previuosly, then it is shown
773 void unHide(const Node& n) const { Parent::unHide(n); }
775 /// \brief Returns true if \c n is hidden.
777 /// Returns true if \c n is hidden.
779 bool hidden(const Node& n) const { return Parent::hidden(n); }
784 /// \brief Just gives back a node-sub-digraph adaptor
786 /// Just gives back a node-sub-digraph adaptor
787 template<typename Digraph, typename NodeFilterMap>
788 NodeSubDigraphAdaptor<const Digraph, NodeFilterMap>
789 nodeSubDigraphAdaptor(const Digraph& digraph, NodeFilterMap& nfm) {
790 return NodeSubDigraphAdaptor<const Digraph, NodeFilterMap>(digraph, nfm);
793 template<typename Digraph, typename NodeFilterMap>
794 NodeSubDigraphAdaptor<const Digraph, const NodeFilterMap>
795 nodeSubDigraphAdaptor(const Digraph& digraph, const NodeFilterMap& nfm) {
796 return NodeSubDigraphAdaptor<const Digraph, const NodeFilterMap>
800 ///\ingroup graph_adaptors
802 ///\brief An adaptor for hiding arcs from a digraph.
804 ///An adaptor for hiding arcs from a digraph. This adaptor
805 ///specializes SubDigraphAdaptor in the way that only the arc-set
806 ///can be filtered. The usefulness of this adaptor is demonstrated
807 ///in the problem of searching a maximum number of arc-disjoint
808 ///shortest paths between two nodes \c s and \c t. Shortest here
809 ///means being shortest with respect to non-negative
810 ///arc-lengths. Note that the comprehension of the presented
811 ///solution need's some elementary knowledge from combinatorial
814 ///If a single shortest path is to be searched between \c s and \c
815 ///t, then this can be done easily by applying the Dijkstra
816 ///algorithm. What happens, if a maximum number of arc-disjoint
817 ///shortest paths is to be computed. It can be proved that an arc
818 ///can be in a shortest path if and only if it is tight with respect
819 ///to the potential function computed by Dijkstra. Moreover, any
820 ///path containing only such arcs is a shortest one. Thus we have
821 ///to compute a maximum number of arc-disjoint paths between \c s
822 ///and \c t in the digraph which has arc-set all the tight arcs. The
823 ///computation will be demonstrated on the following digraph, which
824 ///is read from the dimacs file \c sub_digraph_adaptor_demo.dim.
825 ///The full source code is available in \ref
826 ///sub_digraph_adaptor_demo.cc. If you are interested in more demo
827 ///programs, you can use \ref dim_to_dot.cc to generate .dot files
828 ///from dimacs files. The .dot file of the following figure was
829 ///generated by the demo program \ref dim_to_dot.cc.
832 ///digraph lemon_dot_example {
833 ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
834 ///n0 [ label="0 (s)" ];
840 ///n6 [ label="6 (t)" ];
841 ///arc [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
842 ///n5 -> n6 [ label="9, length:4" ];
843 ///n4 -> n6 [ label="8, length:2" ];
844 ///n3 -> n5 [ label="7, length:1" ];
845 ///n2 -> n5 [ label="6, length:3" ];
846 ///n2 -> n6 [ label="5, length:5" ];
847 ///n2 -> n4 [ label="4, length:2" ];
848 ///n1 -> n4 [ label="3, length:3" ];
849 ///n0 -> n3 [ label="2, length:1" ];
850 ///n0 -> n2 [ label="1, length:2" ];
851 ///n0 -> n1 [ label="0, length:3" ];
858 ///LengthMap length(g);
860 ///readDimacs(std::cin, g, length, s, t);
862 ///cout << "arcs with lengths (of form id, source--length->target): " << endl;
863 ///for(ArcIt e(g); e!=INVALID; ++e)
864 /// cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
865 /// << length[e] << "->" << g.id(g.target(e)) << endl;
867 ///cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
869 ///Next, the potential function is computed with Dijkstra.
871 ///typedef Dijkstra<Digraph, LengthMap> Dijkstra;
872 ///Dijkstra dijkstra(g, length);
875 ///Next, we consrtruct a map which filters the arc-set to the tight arcs.
877 ///typedef TightArcFilterMap<Digraph, const Dijkstra::DistMap, LengthMap>
879 ///TightArcFilter tight_arc_filter(g, dijkstra.distMap(), length);
881 ///typedef ArcSubDigraphAdaptor<Digraph, TightArcFilter> SubGA;
882 ///SubGA ga(g, tight_arc_filter);
884 ///Then, the maximum nimber of arc-disjoint \c s-\c t paths are computed
885 ///with a max flow algorithm Preflow.
887 ///ConstMap<Arc, int> const_1_map(1);
888 ///Digraph::ArcMap<int> flow(g, 0);
890 ///Preflow<SubGA, ConstMap<Arc, int>, Digraph::ArcMap<int> >
891 /// preflow(ga, const_1_map, s, t);
894 ///Last, the output is:
896 ///cout << "maximum number of arc-disjoint shortest path: "
897 /// << preflow.flowValue() << endl;
898 ///cout << "arcs of the maximum number of arc-disjoint shortest s-t paths: "
900 ///for(ArcIt e(g); e!=INVALID; ++e)
901 /// if (preflow.flow(e))
902 /// cout << " " << g.id(g.source(e)) << "--"
903 /// << length[e] << "->" << g.id(g.target(e)) << endl;
905 ///The program has the following (expected :-)) output:
907 ///arcs with lengths (of form id, source--length->target):
919 ///maximum number of arc-disjoint shortest path: 2
920 ///arcs of the maximum number of arc-disjoint shortest s-t paths:
928 template<typename _Digraph, typename _ArcFilterMap>
929 class ArcSubDigraphAdaptor :
930 public SubDigraphAdaptor<_Digraph, ConstMap<typename _Digraph::Node, bool>,
931 _ArcFilterMap, false> {
933 typedef _Digraph Digraph;
934 typedef _ArcFilterMap ArcFilterMap;
936 typedef SubDigraphAdaptor<Digraph, ConstMap<typename Digraph::Node, bool>,
937 ArcFilterMap, false> Parent;
939 typedef typename Parent::Arc Arc;
942 ConstMap<typename Digraph::Node, bool> const_true_map;
944 ArcSubDigraphAdaptor() : const_true_map(true) {
945 Parent::setNodeFilterMap(const_true_map);
950 /// \brief Constructor
952 /// Creates a arc-sub-digraph-adaptor for the given digraph with
953 /// given arc map filter.
954 ArcSubDigraphAdaptor(Digraph& digraph, ArcFilterMap& arc_filter)
955 : Parent(), const_true_map(true) {
956 Parent::setDigraph(digraph);
957 Parent::setNodeFilterMap(const_true_map);
958 Parent::setArcFilterMap(arc_filter);
961 /// \brief Hides the arc of the graph
963 /// This function hides \c a in the digraph, i.e. the iteration
964 /// jumps over it. This is done by simply setting the value of \c a
965 /// to be false in the corresponding arc-map.
966 void hide(const Arc& a) const { Parent::hide(a); }
968 /// \brief Unhides the arc of the graph
970 /// The value of \c a is set to be true in the arc-map which stores
971 /// hide information. If \c a was hidden previuosly, then it is shown
973 void unHide(const Arc& a) const { Parent::unHide(a); }
975 /// \brief Returns true if \c a is hidden.
977 /// Returns true if \c a is hidden.
979 bool hidden(const Arc& a) const { return Parent::hidden(a); }
983 /// \brief Just gives back an arc-sub-digraph adaptor
985 /// Just gives back an arc-sub-digraph adaptor
986 template<typename Digraph, typename ArcFilterMap>
987 ArcSubDigraphAdaptor<const Digraph, ArcFilterMap>
988 arcSubDigraphAdaptor(const Digraph& digraph, ArcFilterMap& afm) {
989 return ArcSubDigraphAdaptor<const Digraph, ArcFilterMap>(digraph, afm);
992 template<typename Digraph, typename ArcFilterMap>
993 ArcSubDigraphAdaptor<const Digraph, const ArcFilterMap>
994 arcSubDigraphAdaptor(const Digraph& digraph, const ArcFilterMap& afm) {
995 return ArcSubDigraphAdaptor<const Digraph, const ArcFilterMap>
999 template <typename _Digraph>
1000 class UndirDigraphAdaptorBase {
1002 typedef _Digraph Digraph;
1003 typedef UndirDigraphAdaptorBase Adaptor;
1005 typedef True UndirectedTag;
1007 typedef typename Digraph::Arc Edge;
1008 typedef typename Digraph::Node Node;
1010 class Arc : public Edge {
1011 friend class UndirDigraphAdaptorBase;
1015 Arc(const Edge& edge, bool forward) :
1016 Edge(edge), _forward(forward) {}
1021 Arc(Invalid) : Edge(INVALID), _forward(true) {}
1023 bool operator==(const Arc &other) const {
1024 return _forward == other._forward &&
1025 static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
1027 bool operator!=(const Arc &other) const {
1028 return _forward != other._forward ||
1029 static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
1031 bool operator<(const Arc &other) const {
1032 return _forward < other._forward ||
1033 (_forward == other._forward &&
1034 static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
1040 void first(Node& n) const {
1044 void next(Node& n) const {
1048 void first(Arc& a) const {
1053 void next(Arc& a) const {
1062 void first(Edge& e) const {
1066 void next(Edge& e) const {
1070 void firstOut(Arc& a, const Node& n) const {
1071 _digraph->firstIn(a, n);
1072 if( static_cast<const Edge&>(a) != INVALID ) {
1075 _digraph->firstOut(a, n);
1079 void nextOut(Arc &a) const {
1081 Node n = _digraph->target(a);
1082 _digraph->nextIn(a);
1083 if (static_cast<const Edge&>(a) == INVALID ) {
1084 _digraph->firstOut(a, n);
1089 _digraph->nextOut(a);
1093 void firstIn(Arc &a, const Node &n) const {
1094 _digraph->firstOut(a, n);
1095 if (static_cast<const Edge&>(a) != INVALID ) {
1098 _digraph->firstIn(a, n);
1102 void nextIn(Arc &a) const {
1104 Node n = _digraph->source(a);
1105 _digraph->nextOut(a);
1106 if( static_cast<const Edge&>(a) == INVALID ) {
1107 _digraph->firstIn(a, n);
1112 _digraph->nextIn(a);
1116 void firstInc(Edge &e, bool &d, const Node &n) const {
1118 _digraph->firstOut(e, n);
1119 if (e != INVALID) return;
1121 _digraph->firstIn(e, n);
1124 void nextInc(Edge &e, bool &d) const {
1126 Node s = _digraph->source(e);
1127 _digraph->nextOut(e);
1128 if (e != INVALID) return;
1130 _digraph->firstIn(e, s);
1132 _digraph->nextIn(e);
1136 Node u(const Edge& e) const {
1137 return _digraph->source(e);
1140 Node v(const Edge& e) const {
1141 return _digraph->target(e);
1144 Node source(const Arc &a) const {
1145 return a._forward ? _digraph->source(a) : _digraph->target(a);
1148 Node target(const Arc &a) const {
1149 return a._forward ? _digraph->target(a) : _digraph->source(a);
1152 static Arc direct(const Edge &e, bool d) {
1155 Arc direct(const Edge &e, const Node& n) const {
1156 return Arc(e, _digraph->source(e) == n);
1159 static bool direction(const Arc &a) { return a._forward; }
1161 Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
1162 Arc arcFromId(int ix) const {
1163 return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1));
1165 Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); }
1167 int id(const Node &n) const { return _digraph->id(n); }
1168 int id(const Arc &a) const {
1169 return (_digraph->id(a) << 1) | (a._forward ? 1 : 0);
1171 int id(const Edge &e) const { return _digraph->id(e); }
1173 int maxNodeId() const { return _digraph->maxNodeId(); }
1174 int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; }
1175 int maxEdgeId() const { return _digraph->maxArcId(); }
1177 Node addNode() { return _digraph->addNode(); }
1178 Edge addEdge(const Node& u, const Node& v) {
1179 return _digraph->addArc(u, v);
1182 void erase(const Node& i) { _digraph->erase(i); }
1183 void erase(const Edge& i) { _digraph->erase(i); }
1185 void clear() { _digraph->clear(); }
1187 typedef NodeNumTagIndicator<Digraph> NodeNumTag;
1188 int nodeNum() const { return 2 * _digraph->arcNum(); }
1189 typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
1190 int arcNum() const { return 2 * _digraph->arcNum(); }
1191 int edgeNum() const { return _digraph->arcNum(); }
1193 typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
1194 Arc findArc(Node s, Node t, Arc p = INVALID) const {
1196 Edge arc = _digraph->findArc(s, t);
1197 if (arc != INVALID) return direct(arc, true);
1198 arc = _digraph->findArc(t, s);
1199 if (arc != INVALID) return direct(arc, false);
1200 } else if (direction(p)) {
1201 Edge arc = _digraph->findArc(s, t, p);
1202 if (arc != INVALID) return direct(arc, true);
1203 arc = _digraph->findArc(t, s);
1204 if (arc != INVALID) return direct(arc, false);
1206 Edge arc = _digraph->findArc(t, s, p);
1207 if (arc != INVALID) return direct(arc, false);
1212 Edge findEdge(Node s, Node t, Edge p = INVALID) const {
1215 Edge arc = _digraph->findArc(s, t);
1216 if (arc != INVALID) return arc;
1217 arc = _digraph->findArc(t, s);
1218 if (arc != INVALID) return arc;
1219 } else if (_digraph->s(p) == s) {
1220 Edge arc = _digraph->findArc(s, t, p);
1221 if (arc != INVALID) return arc;
1222 arc = _digraph->findArc(t, s);
1223 if (arc != INVALID) return arc;
1225 Edge arc = _digraph->findArc(t, s, p);
1226 if (arc != INVALID) return arc;
1229 return _digraph->findArc(s, t, p);
1236 template <typename _Value>
1240 typedef typename Digraph::template ArcMap<_Value> MapImpl;
1244 typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
1246 typedef _Value Value;
1249 ArcMapBase(const Adaptor& adaptor) :
1250 _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
1252 ArcMapBase(const Adaptor& adaptor, const Value& v)
1253 : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}
1255 void set(const Arc& a, const Value& v) {
1259 _backward.set(a, v);
1263 typename MapTraits<MapImpl>::ConstReturnValue
1264 operator[](const Arc& a) const {
1268 return _backward[a];
1272 typename MapTraits<MapImpl>::ReturnValue
1273 operator[](const Arc& a) {
1277 return _backward[a];
1283 MapImpl _forward, _backward;
1289 template <typename _Value>
1290 class NodeMap : public Digraph::template NodeMap<_Value> {
1293 typedef _Value Value;
1294 typedef typename Digraph::template NodeMap<Value> Parent;
1296 explicit NodeMap(const Adaptor& adaptor)
1297 : Parent(*adaptor._digraph) {}
1299 NodeMap(const Adaptor& adaptor, const _Value& value)
1300 : Parent(*adaptor._digraph, value) { }
1303 NodeMap& operator=(const NodeMap& cmap) {
1304 return operator=<NodeMap>(cmap);
1307 template <typename CMap>
1308 NodeMap& operator=(const CMap& cmap) {
1309 Parent::operator=(cmap);
1315 template <typename _Value>
1317 : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
1320 typedef _Value Value;
1321 typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
1323 ArcMap(const Adaptor& adaptor)
1324 : Parent(adaptor) {}
1326 ArcMap(const Adaptor& adaptor, const Value& value)
1327 : Parent(adaptor, value) {}
1330 ArcMap& operator=(const ArcMap& cmap) {
1331 return operator=<ArcMap>(cmap);
1334 template <typename CMap>
1335 ArcMap& operator=(const CMap& cmap) {
1336 Parent::operator=(cmap);
1341 template <typename _Value>
1342 class EdgeMap : public Digraph::template ArcMap<_Value> {
1345 typedef _Value Value;
1346 typedef typename Digraph::template ArcMap<Value> Parent;
1348 explicit EdgeMap(const Adaptor& adaptor)
1349 : Parent(*adaptor._digraph) {}
1351 EdgeMap(const Adaptor& adaptor, const Value& value)
1352 : Parent(*adaptor._digraph, value) {}
1355 EdgeMap& operator=(const EdgeMap& cmap) {
1356 return operator=<EdgeMap>(cmap);
1359 template <typename CMap>
1360 EdgeMap& operator=(const CMap& cmap) {
1361 Parent::operator=(cmap);
1367 typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
1368 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
1372 UndirDigraphAdaptorBase() : _digraph(0) {}
1376 void setDigraph(Digraph& digraph) {
1377 _digraph = &digraph;
1382 ///\ingroup graph_adaptors
1384 /// \brief A graph is made from a directed digraph by an adaptor
1386 /// This adaptor makes an undirected graph from a directed
1387 /// graph. All arc of the underlying digraph will be showed in the
1388 /// adaptor as an edge. Let's see an informal example about using
1391 /// There is a network of the streets of a town. Of course there are
1392 /// some one-way street in the town hence the network is a directed
1393 /// one. There is a crazy driver who go oppositely in the one-way
1394 /// street without moral sense. Of course he can pass this streets
1395 /// slower than the regular way, in fact his speed is half of the
1396 /// normal speed. How long should he drive to get from a source
1397 /// point to the target? Let see the example code which calculate it:
1399 /// \todo BadCode, SimpleMap does no exists
1401 /// typedef UndirDigraphAdaptor<Digraph> Graph;
1402 /// Graph graph(digraph);
1404 /// typedef SimpleMap<LengthMap> FLengthMap;
1405 /// FLengthMap flength(length);
1407 /// typedef ScaleMap<LengthMap> RLengthMap;
1408 /// RLengthMap rlength(length, 2.0);
1410 /// typedef Graph::CombinedArcMap<FLengthMap, RLengthMap > ULengthMap;
1411 /// ULengthMap ulength(flength, rlength);
1413 /// Dijkstra<Graph, ULengthMap> dijkstra(graph, ulength);
1414 /// std::cout << "Driving time : " << dijkstra.run(src, trg) << std::endl;
1417 /// The combined arc map makes the length map for the undirected
1418 /// graph. It is created from a forward and reverse map. The forward
1419 /// map is created from the original length map with a SimpleMap
1420 /// adaptor which just makes a read-write map from the reference map
1421 /// i.e. it forgets that it can be return reference to values. The
1422 /// reverse map is just the scaled original map with the ScaleMap
1423 /// adaptor. The combination solves that passing the reverse way
1424 /// takes double time than the original. To get the driving time we
1425 /// run the dijkstra algorithm on the graph.
1426 template<typename _Digraph>
1427 class UndirDigraphAdaptor
1428 : public GraphAdaptorExtender<UndirDigraphAdaptorBase<_Digraph> > {
1430 typedef _Digraph Digraph;
1431 typedef GraphAdaptorExtender<UndirDigraphAdaptorBase<Digraph> > Parent;
1433 UndirDigraphAdaptor() { }
1436 /// \brief Constructor
1439 UndirDigraphAdaptor(_Digraph& _digraph) {
1440 setDigraph(_digraph);
1443 /// \brief ArcMap combined from two original ArcMap
1445 /// This class adapts two original digraph ArcMap to
1446 /// get an arc map on the adaptor.
1447 template <typename _ForwardMap, typename _BackwardMap>
1448 class CombinedArcMap {
1451 typedef _ForwardMap ForwardMap;
1452 typedef _BackwardMap BackwardMap;
1454 typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
1456 typedef typename ForwardMap::Value Value;
1457 typedef typename Parent::Arc Key;
1459 /// \brief Constructor
1462 CombinedArcMap() : _forward(0), _backward(0) {}
1464 /// \brief Constructor
1467 CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
1468 : _forward(&forward), _backward(&backward) {}
1471 /// \brief Sets the value associated with a key.
1473 /// Sets the value associated with a key.
1474 void set(const Key& e, const Value& a) {
1475 if (Parent::direction(e)) {
1476 _forward->set(e, a);
1478 _backward->set(e, a);
1482 /// \brief Returns the value associated with a key.
1484 /// Returns the value associated with a key.
1485 typename MapTraits<ForwardMap>::ConstReturnValue
1486 operator[](const Key& e) const {
1487 if (Parent::direction(e)) {
1488 return (*_forward)[e];
1490 return (*_backward)[e];
1494 /// \brief Returns the value associated with a key.
1496 /// Returns the value associated with a key.
1497 typename MapTraits<ForwardMap>::ReturnValue
1498 operator[](const Key& e) {
1499 if (Parent::direction(e)) {
1500 return (*_forward)[e];
1502 return (*_backward)[e];
1506 /// \brief Sets the forward map
1508 /// Sets the forward map
1509 void setForwardMap(ForwardMap& forward) {
1510 _forward = &forward;
1513 /// \brief Sets the backward map
1515 /// Sets the backward map
1516 void setBackwardMap(BackwardMap& backward) {
1517 _backward = &backward;
1522 ForwardMap* _forward;
1523 BackwardMap* _backward;
1529 /// \brief Just gives back an undir digraph adaptor
1531 /// Just gives back an undir digraph adaptor
1532 template<typename Digraph>
1533 UndirDigraphAdaptor<const Digraph>
1534 undirDigraphAdaptor(const Digraph& digraph) {
1535 return UndirDigraphAdaptor<const Digraph>(digraph);
1538 template<typename _Digraph,
1539 typename _CapacityMap = typename _Digraph::template ArcMap<int>,
1540 typename _FlowMap = _CapacityMap,
1541 typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
1542 class ResForwardFilter {
1545 typedef _Digraph Digraph;
1546 typedef _CapacityMap CapacityMap;
1547 typedef _FlowMap FlowMap;
1548 typedef _Tolerance Tolerance;
1550 typedef typename Digraph::Arc Key;
1555 const CapacityMap* _capacity;
1556 const FlowMap* _flow;
1557 Tolerance _tolerance;
1560 ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,
1561 const Tolerance& tolerance = Tolerance())
1562 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
1564 ResForwardFilter(const Tolerance& tolerance = Tolerance())
1565 : _capacity(0), _flow(0), _tolerance(tolerance) { }
1567 void setCapacity(const CapacityMap& capacity) { _capacity = &capacity; }
1568 void setFlow(const FlowMap& flow) { _flow = &flow; }
1570 bool operator[](const typename Digraph::Arc& a) const {
1571 return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
1575 template<typename _Digraph,
1576 typename _CapacityMap = typename _Digraph::template ArcMap<int>,
1577 typename _FlowMap = _CapacityMap,
1578 typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
1579 class ResBackwardFilter {
1582 typedef _Digraph Digraph;
1583 typedef _CapacityMap CapacityMap;
1584 typedef _FlowMap FlowMap;
1585 typedef _Tolerance Tolerance;
1587 typedef typename Digraph::Arc Key;
1592 const CapacityMap* _capacity;
1593 const FlowMap* _flow;
1594 Tolerance _tolerance;
1598 ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,
1599 const Tolerance& tolerance = Tolerance())
1600 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
1601 ResBackwardFilter(const Tolerance& tolerance = Tolerance())
1602 : _capacity(0), _flow(0), _tolerance(tolerance) { }
1604 void setCapacity(const CapacityMap& capacity) { _capacity = &capacity; }
1605 void setFlow(const FlowMap& flow) { _flow = &flow; }
1607 bool operator[](const typename Digraph::Arc& a) const {
1608 return _tolerance.positive((*_flow)[a]);
1613 ///\ingroup graph_adaptors
1615 ///\brief An adaptor for composing the residual graph for directed
1616 ///flow and circulation problems.
1618 ///An adaptor for composing the residual graph for directed flow and
1619 ///circulation problems. Let \f$ G=(V, A) \f$ be a directed digraph
1620 ///and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F
1621 ///\f$, be functions on the arc-set.
1623 ///In the appications of ResDigraphAdaptor, \f$ f \f$ usually stands
1624 ///for a flow and \f$ c \f$ for a capacity function. Suppose that a
1625 ///graph instance \c g of type \c ListDigraph implements \f$ G \f$.
1631 ///Then ResDigraphAdaptor implements the digraph structure with
1632 /// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward}
1633 /// \f$, where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
1634 /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so
1635 /// called residual graph. When we take the union \f$
1636 /// A_{forward}\cup A_{backward} \f$, multilicities are counted,
1637 /// i.e. if an arc is in both \f$ A_{forward} \f$ and \f$
1638 /// A_{backward} \f$, then in the adaptor it appears twice. The
1639 /// following code shows how such an instance can be constructed.
1642 /// typedef ListDigraph Digraph;
1643 /// IntArcMap f(g), c(g);
1644 /// ResDigraphAdaptor<Digraph, int, IntArcMap, IntArcMap> ga(g);
1646 template<typename _Digraph,
1647 typename _CapacityMap = typename _Digraph::template ArcMap<int>,
1648 typename _FlowMap = _CapacityMap,
1649 typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
1650 class ResDigraphAdaptor :
1651 public ArcSubDigraphAdaptor<
1652 UndirDigraphAdaptor<const _Digraph>,
1653 typename UndirDigraphAdaptor<const _Digraph>::template CombinedArcMap<
1654 ResForwardFilter<const _Digraph, _CapacityMap, _FlowMap>,
1655 ResBackwardFilter<const _Digraph, _CapacityMap, _FlowMap> > > {
1658 typedef _Digraph Digraph;
1659 typedef _CapacityMap CapacityMap;
1660 typedef _FlowMap FlowMap;
1661 typedef _Tolerance Tolerance;
1663 typedef typename CapacityMap::Value Value;
1664 typedef ResDigraphAdaptor Adaptor;
1668 typedef UndirDigraphAdaptor<const Digraph> UndirDigraph;
1670 typedef ResForwardFilter<const Digraph, CapacityMap, FlowMap>
1673 typedef ResBackwardFilter<const Digraph, CapacityMap, FlowMap>
1676 typedef typename UndirDigraph::
1677 template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
1679 typedef ArcSubDigraphAdaptor<UndirDigraph, ArcFilter> Parent;
1681 const CapacityMap* _capacity;
1684 UndirDigraph _graph;
1685 ForwardFilter _forward_filter;
1686 BackwardFilter _backward_filter;
1687 ArcFilter _arc_filter;
1689 void setCapacityMap(const CapacityMap& capacity) {
1690 _capacity = &capacity;
1691 _forward_filter.setCapacity(capacity);
1692 _backward_filter.setCapacity(capacity);
1695 void setFlowMap(FlowMap& flow) {
1697 _forward_filter.setFlow(flow);
1698 _backward_filter.setFlow(flow);
1703 /// \brief Constructor of the residual digraph.
1705 /// Constructor of the residual graph. The parameters are the digraph type,
1706 /// the flow map, the capacity map and a tolerance object.
1707 ResDigraphAdaptor(const Digraph& digraph, const CapacityMap& capacity,
1708 FlowMap& flow, const Tolerance& tolerance = Tolerance())
1709 : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
1710 _forward_filter(capacity, flow, tolerance),
1711 _backward_filter(capacity, flow, tolerance),
1712 _arc_filter(_forward_filter, _backward_filter)
1714 Parent::setDigraph(_graph);
1715 Parent::setArcFilterMap(_arc_filter);
1718 typedef typename Parent::Arc Arc;
1720 /// \brief Gives back the residual capacity of the arc.
1722 /// Gives back the residual capacity of the arc.
1723 Value rescap(const Arc& arc) const {
1724 if (UndirDigraph::direction(arc)) {
1725 return (*_capacity)[arc] - (*_flow)[arc];
1727 return (*_flow)[arc];
1731 /// \brief Augment on the given arc in the residual digraph.
1733 /// Augment on the given arc in the residual digraph. It increase
1734 /// or decrease the flow on the original arc depend on the direction
1735 /// of the residual arc.
1736 void augment(const Arc& e, const Value& a) const {
1737 if (UndirDigraph::direction(e)) {
1738 _flow->set(e, (*_flow)[e] + a);
1740 _flow->set(e, (*_flow)[e] - a);
1744 /// \brief Returns the direction of the arc.
1746 /// Returns true when the arc is same oriented as the original arc.
1747 static bool forward(const Arc& e) {
1748 return UndirDigraph::direction(e);
1751 /// \brief Returns the direction of the arc.
1753 /// Returns true when the arc is opposite oriented as the original arc.
1754 static bool backward(const Arc& e) {
1755 return !UndirDigraph::direction(e);
1758 /// \brief Gives back the forward oriented residual arc.
1760 /// Gives back the forward oriented residual arc.
1761 static Arc forward(const typename Digraph::Arc& e) {
1762 return UndirDigraph::direct(e, true);
1765 /// \brief Gives back the backward oriented residual arc.
1767 /// Gives back the backward oriented residual arc.
1768 static Arc backward(const typename Digraph::Arc& e) {
1769 return UndirDigraph::direct(e, false);
1772 /// \brief Residual capacity map.
1774 /// In generic residual digraphs the residual capacity can be obtained
1778 const Adaptor* _adaptor;
1781 typedef typename _CapacityMap::Value Value;
1783 ResCap(const Adaptor& adaptor) : _adaptor(&adaptor) {}
1785 Value operator[](const Arc& e) const {
1786 return _adaptor->rescap(e);
1793 template <typename _Digraph>
1794 class SplitDigraphAdaptorBase {
1797 typedef _Digraph Digraph;
1798 typedef DigraphAdaptorBase<const _Digraph> Parent;
1799 typedef SplitDigraphAdaptorBase Adaptor;
1801 typedef typename Digraph::Node DigraphNode;
1802 typedef typename Digraph::Arc DigraphArc;
1809 template <typename T> class NodeMapBase;
1810 template <typename T> class ArcMapBase;
1814 class Node : public DigraphNode {
1815 friend class SplitDigraphAdaptorBase;
1816 template <typename T> friend class NodeMapBase;
1820 Node(DigraphNode node, bool in)
1821 : DigraphNode(node), _in(in) {}
1826 Node(Invalid) : DigraphNode(INVALID), _in(true) {}
1828 bool operator==(const Node& node) const {
1829 return DigraphNode::operator==(node) && _in == node._in;
1832 bool operator!=(const Node& node) const {
1833 return !(*this == node);
1836 bool operator<(const Node& node) const {
1837 return DigraphNode::operator<(node) ||
1838 (DigraphNode::operator==(node) && _in < node._in);
1843 friend class SplitDigraphAdaptorBase;
1844 template <typename T> friend class ArcMapBase;
1846 typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;
1848 explicit Arc(const DigraphArc& arc) : _item(arc) {}
1849 explicit Arc(const DigraphNode& node) : _item(node) {}
1855 Arc(Invalid) : _item(DigraphArc(INVALID)) {}
1857 bool operator==(const Arc& arc) const {
1858 if (_item.firstState()) {
1859 if (arc._item.firstState()) {
1860 return _item.first() == arc._item.first();
1863 if (arc._item.secondState()) {
1864 return _item.second() == arc._item.second();
1870 bool operator!=(const Arc& arc) const {
1871 return !(*this == arc);
1874 bool operator<(const Arc& arc) const {
1875 if (_item.firstState()) {
1876 if (arc._item.firstState()) {
1877 return _item.first() < arc._item.first();
1881 if (arc._item.secondState()) {
1882 return _item.second() < arc._item.second();
1888 operator DigraphArc() const { return _item.first(); }
1889 operator DigraphNode() const { return _item.second(); }
1893 void first(Node& n) const {
1898 void next(Node& n) const {
1907 void first(Arc& e) const {
1908 e._item.setSecond();
1909 _digraph->first(e._item.second());
1910 if (e._item.second() == INVALID) {
1912 _digraph->first(e._item.first());
1916 void next(Arc& e) const {
1917 if (e._item.secondState()) {
1918 _digraph->next(e._item.second());
1919 if (e._item.second() == INVALID) {
1921 _digraph->first(e._item.first());
1924 _digraph->next(e._item.first());
1928 void firstOut(Arc& e, const Node& n) const {
1930 e._item.setSecond(n);
1933 _digraph->firstOut(e._item.first(), n);
1937 void nextOut(Arc& e) const {
1938 if (!e._item.firstState()) {
1939 e._item.setFirst(INVALID);
1941 _digraph->nextOut(e._item.first());
1945 void firstIn(Arc& e, const Node& n) const {
1947 e._item.setSecond(n);
1950 _digraph->firstIn(e._item.first(), n);
1954 void nextIn(Arc& e) const {
1955 if (!e._item.firstState()) {
1956 e._item.setFirst(INVALID);
1958 _digraph->nextIn(e._item.first());
1962 Node source(const Arc& e) const {
1963 if (e._item.firstState()) {
1964 return Node(_digraph->source(e._item.first()), false);
1966 return Node(e._item.second(), true);
1970 Node target(const Arc& e) const {
1971 if (e._item.firstState()) {
1972 return Node(_digraph->target(e._item.first()), true);
1974 return Node(e._item.second(), false);
1978 int id(const Node& n) const {
1979 return (_digraph->id(n) << 1) | (n._in ? 0 : 1);
1981 Node nodeFromId(int ix) const {
1982 return Node(_digraph->nodeFromId(ix >> 1), (ix & 1) == 0);
1984 int maxNodeId() const {
1985 return 2 * _digraph->maxNodeId() + 1;
1988 int id(const Arc& e) const {
1989 if (e._item.firstState()) {
1990 return _digraph->id(e._item.first()) << 1;
1992 return (_digraph->id(e._item.second()) << 1) | 1;
1995 Arc arcFromId(int ix) const {
1996 if ((ix & 1) == 0) {
1997 return Arc(_digraph->arcFromId(ix >> 1));
1999 return Arc(_digraph->nodeFromId(ix >> 1));
2002 int maxArcId() const {
2003 return std::max(_digraph->maxNodeId() << 1,
2004 (_digraph->maxArcId() << 1) | 1);
2007 static bool inNode(const Node& n) {
2011 static bool outNode(const Node& n) {
2015 static bool origArc(const Arc& e) {
2016 return e._item.firstState();
2019 static bool bindArc(const Arc& e) {
2020 return e._item.secondState();
2023 static Node inNode(const DigraphNode& n) {
2024 return Node(n, true);
2027 static Node outNode(const DigraphNode& n) {
2028 return Node(n, false);
2031 static Arc arc(const DigraphNode& n) {
2035 static Arc arc(const DigraphArc& e) {
2039 typedef True NodeNumTag;
2041 int nodeNum() const {
2042 return 2 * countNodes(*_digraph);
2045 typedef True EdgeNumTag;
2046 int arcNum() const {
2047 return countArcs(*_digraph) + countNodes(*_digraph);
2050 typedef True FindEdgeTag;
2051 Arc findArc(const Node& u, const Node& v,
2052 const Arc& prev = INVALID) const {
2055 if (static_cast<const DigraphNode&>(u) ==
2056 static_cast<const DigraphNode&>(v) && prev == INVALID) {
2062 return Arc(::lemon::findArc(*_digraph, u, v, prev));
2070 template <typename _Value>
2072 : public MapTraits<typename Parent::template NodeMap<_Value> > {
2073 typedef typename Parent::template NodeMap<_Value> NodeImpl;
2076 typedef _Value Value;
2078 NodeMapBase(const Adaptor& adaptor)
2079 : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
2080 NodeMapBase(const Adaptor& adaptor, const Value& value)
2081 : _in_map(*adaptor._digraph, value),
2082 _out_map(*adaptor._digraph, value) {}
2084 void set(const Node& key, const Value& val) {
2085 if (Adaptor::inNode(key)) { _in_map.set(key, val); }
2086 else {_out_map.set(key, val); }
2089 typename MapTraits<NodeImpl>::ReturnValue
2090 operator[](const Node& key) {
2091 if (Adaptor::inNode(key)) { return _in_map[key]; }
2092 else { return _out_map[key]; }
2095 typename MapTraits<NodeImpl>::ConstReturnValue
2096 operator[](const Node& key) const {
2097 if (Adaptor::inNode(key)) { return _in_map[key]; }
2098 else { return _out_map[key]; }
2102 NodeImpl _in_map, _out_map;
2105 template <typename _Value>
2107 : public MapTraits<typename Parent::template ArcMap<_Value> > {
2108 typedef typename Parent::template ArcMap<_Value> ArcImpl;
2109 typedef typename Parent::template NodeMap<_Value> NodeImpl;
2112 typedef _Value Value;
2114 ArcMapBase(const Adaptor& adaptor)
2115 : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
2116 ArcMapBase(const Adaptor& adaptor, const Value& value)
2117 : _arc_map(*adaptor._digraph, value),
2118 _node_map(*adaptor._digraph, value) {}
2120 void set(const Arc& key, const Value& val) {
2121 if (Adaptor::origArc(key)) {
2122 _arc_map.set(key._item.first(), val);
2124 _node_map.set(key._item.second(), val);
2128 typename MapTraits<ArcImpl>::ReturnValue
2129 operator[](const Arc& key) {
2130 if (Adaptor::origArc(key)) {
2131 return _arc_map[key._item.first()];
2133 return _node_map[key._item.second()];
2137 typename MapTraits<ArcImpl>::ConstReturnValue
2138 operator[](const Arc& key) const {
2139 if (Adaptor::origArc(key)) {
2140 return _arc_map[key._item.first()];
2142 return _node_map[key._item.second()];
2153 template <typename _Value>
2155 : public SubMapExtender<Adaptor, NodeMapBase<_Value> >
2158 typedef _Value Value;
2159 typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent;
2161 NodeMap(const Adaptor& adaptor)
2162 : Parent(adaptor) {}
2164 NodeMap(const Adaptor& adaptor, const Value& value)
2165 : Parent(adaptor, value) {}
2168 NodeMap& operator=(const NodeMap& cmap) {
2169 return operator=<NodeMap>(cmap);
2172 template <typename CMap>
2173 NodeMap& operator=(const CMap& cmap) {
2174 Parent::operator=(cmap);
2179 template <typename _Value>
2181 : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
2184 typedef _Value Value;
2185 typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
2187 ArcMap(const Adaptor& adaptor)
2188 : Parent(adaptor) {}
2190 ArcMap(const Adaptor& adaptor, const Value& value)
2191 : Parent(adaptor, value) {}
2194 ArcMap& operator=(const ArcMap& cmap) {
2195 return operator=<ArcMap>(cmap);
2198 template <typename CMap>
2199 ArcMap& operator=(const CMap& cmap) {
2200 Parent::operator=(cmap);
2207 SplitDigraphAdaptorBase() : _digraph(0) {}
2211 void setDigraph(Digraph& digraph) {
2212 _digraph = &digraph;
2217 /// \ingroup graph_adaptors
2219 /// \brief Split digraph adaptor class
2221 /// This is an digraph adaptor which splits all node into an in-node
2222 /// and an out-node. Formaly, the adaptor replaces each \f$ u \f$
2223 /// node in the digraph with two node, \f$ u_{in} \f$ node and
2224 /// \f$ u_{out} \f$ node. If there is an \f$ (v, u) \f$ arc in the
2225 /// original digraph the new target of the arc will be \f$ u_{in} \f$ and
2226 /// similarly the source of the original \f$ (u, v) \f$ arc will be
2227 /// \f$ u_{out} \f$. The adaptor will add for each node in the
2228 /// original digraph an additional arc which will connect
2229 /// \f$ (u_{in}, u_{out}) \f$.
2231 /// The aim of this class is to run algorithm with node costs if the
2232 /// algorithm can use directly just arc costs. In this case we should use
2233 /// a \c SplitDigraphAdaptor and set the node cost of the digraph to the
2234 /// bind arc in the adapted digraph.
2236 /// For example a maximum flow algorithm can compute how many arc
2237 /// disjoint paths are in the digraph. But we would like to know how
2238 /// many node disjoint paths are in the digraph. First we have to
2239 /// adapt the digraph with the \c SplitDigraphAdaptor. Then run the flow
2240 /// algorithm on the adapted digraph. The bottleneck of the flow will
2241 /// be the bind arcs which bounds the flow with the count of the
2242 /// node disjoint paths.
2246 /// typedef SplitDigraphAdaptor<SmartDigraph> SDigraph;
2248 /// SDigraph sdigraph(digraph);
2250 /// typedef ConstMap<SDigraph::Arc, int> SCapacity;
2251 /// SCapacity scapacity(1);
2253 /// SDigraph::ArcMap<int> sflow(sdigraph);
2255 /// Preflow<SDigraph, SCapacity>
2256 /// spreflow(sdigraph, scapacity,
2257 /// SDigraph::outNode(source), SDigraph::inNode(target));
2263 /// The result of the mamixum flow on the original digraph
2264 /// shows the next figure:
2266 /// \image html arc_disjoint.png
2267 /// \image latex arc_disjoint.eps "Arc disjoint paths" width=\textwidth
2269 /// And the maximum flow on the adapted digraph:
2271 /// \image html node_disjoint.png
2272 /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth
2274 /// The second solution contains just 3 disjoint paths while the first 4.
2275 /// The full code can be found in the \ref disjoint_paths_demo.cc demo file.
2277 /// This digraph adaptor is fully conform to the
2278 /// \ref concepts::Digraph "Digraph" concept and
2279 /// contains some additional member functions and types. The
2280 /// documentation of some member functions may be found just in the
2281 /// SplitDigraphAdaptorBase class.
2283 /// \sa SplitDigraphAdaptorBase
2284 template <typename _Digraph>
2285 class SplitDigraphAdaptor
2286 : public DigraphAdaptorExtender<SplitDigraphAdaptorBase<_Digraph> > {
2288 typedef _Digraph Digraph;
2289 typedef DigraphAdaptorExtender<SplitDigraphAdaptorBase<Digraph> > Parent;
2291 typedef typename Digraph::Node DigraphNode;
2292 typedef typename Digraph::Arc DigraphArc;
2294 typedef typename Parent::Node Node;
2295 typedef typename Parent::Arc Arc;
2297 /// \brief Constructor of the adaptor.
2299 /// Constructor of the adaptor.
2300 SplitDigraphAdaptor(Digraph& g) {
2301 Parent::setDigraph(g);
2304 /// \brief Returns true when the node is in-node.
2306 /// Returns true when the node is in-node.
2307 static bool inNode(const Node& n) {
2308 return Parent::inNode(n);
2311 /// \brief Returns true when the node is out-node.
2313 /// Returns true when the node is out-node.
2314 static bool outNode(const Node& n) {
2315 return Parent::outNode(n);
2318 /// \brief Returns true when the arc is arc in the original digraph.
2320 /// Returns true when the arc is arc in the original digraph.
2321 static bool origArc(const Arc& a) {
2322 return Parent::origArc(a);
2325 /// \brief Returns true when the arc binds an in-node and an out-node.
2327 /// Returns true when the arc binds an in-node and an out-node.
2328 static bool bindArc(const Arc& a) {
2329 return Parent::bindArc(a);
2332 /// \brief Gives back the in-node created from the \c node.
2334 /// Gives back the in-node created from the \c node.
2335 static Node inNode(const DigraphNode& n) {
2336 return Parent::inNode(n);
2339 /// \brief Gives back the out-node created from the \c node.
2341 /// Gives back the out-node created from the \c node.
2342 static Node outNode(const DigraphNode& n) {
2343 return Parent::outNode(n);
2346 /// \brief Gives back the arc binds the two part of the node.
2348 /// Gives back the arc binds the two part of the node.
2349 static Arc arc(const DigraphNode& n) {
2350 return Parent::arc(n);
2353 /// \brief Gives back the arc of the original arc.
2355 /// Gives back the arc of the original arc.
2356 static Arc arc(const DigraphArc& a) {
2357 return Parent::arc(a);
2360 /// \brief NodeMap combined from two original NodeMap
2362 /// This class adapt two of the original digraph NodeMap to
2363 /// get a node map on the adapted digraph.
2364 template <typename InNodeMap, typename OutNodeMap>
2365 class CombinedNodeMap {
2369 typedef typename InNodeMap::Value Value;
2371 /// \brief Constructor
2374 CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
2375 : _in_map(in_map), _out_map(out_map) {}
2377 /// \brief The subscript operator.
2379 /// The subscript operator.
2380 Value& operator[](const Key& key) {
2381 if (Parent::inNode(key)) {
2382 return _in_map[key];
2384 return _out_map[key];
2388 /// \brief The const subscript operator.
2390 /// The const subscript operator.
2391 Value operator[](const Key& key) const {
2392 if (Parent::inNode(key)) {
2393 return _in_map[key];
2395 return _out_map[key];
2399 /// \brief The setter function of the map.
2401 /// The setter function of the map.
2402 void set(const Key& key, const Value& value) {
2403 if (Parent::inNode(key)) {
2404 _in_map.set(key, value);
2406 _out_map.set(key, value);
2413 OutNodeMap& _out_map;
2418 /// \brief Just gives back a combined node map.
2420 /// Just gives back a combined node map.
2421 template <typename InNodeMap, typename OutNodeMap>
2422 static CombinedNodeMap<InNodeMap, OutNodeMap>
2423 combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
2424 return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
2427 template <typename InNodeMap, typename OutNodeMap>
2428 static CombinedNodeMap<const InNodeMap, OutNodeMap>
2429 combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
2430 return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
2433 template <typename InNodeMap, typename OutNodeMap>
2434 static CombinedNodeMap<InNodeMap, const OutNodeMap>
2435 combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
2436 return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
2439 template <typename InNodeMap, typename OutNodeMap>
2440 static CombinedNodeMap<const InNodeMap, const OutNodeMap>
2441 combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
2442 return CombinedNodeMap<const InNodeMap,
2443 const OutNodeMap>(in_map, out_map);
2446 /// \brief ArcMap combined from an original ArcMap and NodeMap
2448 /// This class adapt an original digraph ArcMap and NodeMap to
2449 /// get an arc map on the adapted digraph.
2450 template <typename DigraphArcMap, typename DigraphNodeMap>
2451 class CombinedArcMap {
2455 typedef typename DigraphArcMap::Value Value;
2457 /// \brief Constructor
2460 CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)
2461 : _arc_map(arc_map), _node_map(node_map) {}
2463 /// \brief The subscript operator.
2465 /// The subscript operator.
2466 void set(const Arc& arc, const Value& val) {
2467 if (Parent::origArc(arc)) {
2468 _arc_map.set(arc, val);
2470 _node_map.set(arc, val);
2474 /// \brief The const subscript operator.
2476 /// The const subscript operator.
2477 Value operator[](const Key& arc) const {
2478 if (Parent::origArc(arc)) {
2479 return _arc_map[arc];
2481 return _node_map[arc];
2485 /// \brief The const subscript operator.
2487 /// The const subscript operator.
2488 Value& operator[](const Key& arc) {
2489 if (Parent::origArc(arc)) {
2490 return _arc_map[arc];
2492 return _node_map[arc];
2497 DigraphArcMap& _arc_map;
2498 DigraphNodeMap& _node_map;
2501 /// \brief Just gives back a combined arc map.
2503 /// Just gives back a combined arc map.
2504 template <typename DigraphArcMap, typename DigraphNodeMap>
2505 static CombinedArcMap<DigraphArcMap, DigraphNodeMap>
2506 combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
2507 return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map);
2510 template <typename DigraphArcMap, typename DigraphNodeMap>
2511 static CombinedArcMap<const DigraphArcMap, DigraphNodeMap>
2512 combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
2513 return CombinedArcMap<const DigraphArcMap,
2514 DigraphNodeMap>(arc_map, node_map);
2517 template <typename DigraphArcMap, typename DigraphNodeMap>
2518 static CombinedArcMap<DigraphArcMap, const DigraphNodeMap>
2519 combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) {
2520 return CombinedArcMap<DigraphArcMap,
2521 const DigraphNodeMap>(arc_map, node_map);
2524 template <typename DigraphArcMap, typename DigraphNodeMap>
2525 static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap>
2526 combinedArcMap(const DigraphArcMap& arc_map,
2527 const DigraphNodeMap& node_map) {
2528 return CombinedArcMap<const DigraphArcMap,
2529 const DigraphNodeMap>(arc_map, node_map);
2534 /// \brief Just gives back a split digraph adaptor
2536 /// Just gives back a split digraph adaptor
2537 template<typename Digraph>
2538 SplitDigraphAdaptor<Digraph>
2539 splitDigraphAdaptor(const Digraph& digraph) {
2540 return SplitDigraphAdaptor<Digraph>(digraph);
2546 #endif //LEMON_DIGRAPH_ADAPTOR_H