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 functions.
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 ///\brief Base type for the Digraph Adaptors
43 ///Base type for the Digraph Adaptors
45 ///This is the base type for most of LEMON digraph adaptors. This
46 ///class implements a trivial digraph adaptor i.e. it only wraps the
47 ///functions and types of the digraph. The purpose of this class is
48 ///to make easier implementing digraph adaptors. E.g. if an adaptor
49 ///is considered which differs from the wrapped digraph only in some
50 ///of its functions or types, then it can be derived from
51 ///DigraphAdaptor, and only the differences should be implemented.
52 template<typename _Digraph>
53 class DigraphAdaptorBase {
55 typedef _Digraph Digraph;
56 typedef DigraphAdaptorBase Adaptor;
57 typedef Digraph ParentDigraph;
61 DigraphAdaptorBase() : _digraph(0) { }
62 void setDigraph(Digraph& digraph) { _digraph = &digraph; }
65 DigraphAdaptorBase(Digraph& digraph) : _digraph(&digraph) { }
67 typedef typename Digraph::Node Node;
68 typedef typename Digraph::Arc Arc;
70 void first(Node& i) const { _digraph->first(i); }
71 void first(Arc& i) const { _digraph->first(i); }
72 void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); }
73 void firstOut(Arc& i, const Node& n ) const { _digraph->firstOut(i, n); }
75 void next(Node& i) const { _digraph->next(i); }
76 void next(Arc& i) const { _digraph->next(i); }
77 void nextIn(Arc& i) const { _digraph->nextIn(i); }
78 void nextOut(Arc& i) const { _digraph->nextOut(i); }
80 Node source(const Arc& a) const { return _digraph->source(a); }
81 Node target(const Arc& a) const { return _digraph->target(a); }
83 typedef NodeNumTagIndicator<Digraph> NodeNumTag;
84 int nodeNum() const { return _digraph->nodeNum(); }
86 typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
87 int arcNum() const { return _digraph->arcNum(); }
89 typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
90 Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
91 return _digraph->findArc(u, v, prev);
94 Node addNode() { return _digraph->addNode(); }
95 Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
97 void erase(const Node& n) const { _digraph->erase(n); }
98 void erase(const Arc& a) const { _digraph->erase(a); }
100 void clear() const { _digraph->clear(); }
102 int id(const Node& n) const { return _digraph->id(n); }
103 int id(const Arc& a) const { return _digraph->id(a); }
105 Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
106 Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); }
108 int maxNodeId() const { return _digraph->maxNodeId(); }
109 int maxArcId() const { return _digraph->maxArcId(); }
111 typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
112 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
114 typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier;
115 ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
117 template <typename _Value>
118 class NodeMap : public Digraph::template NodeMap<_Value> {
121 typedef typename Digraph::template NodeMap<_Value> Parent;
123 explicit NodeMap(const Adaptor& adaptor)
124 : Parent(*adaptor._digraph) {}
126 NodeMap(const Adaptor& adaptor, const _Value& value)
127 : Parent(*adaptor._digraph, value) { }
130 NodeMap& operator=(const NodeMap& cmap) {
131 return operator=<NodeMap>(cmap);
134 template <typename CMap>
135 NodeMap& operator=(const CMap& cmap) {
136 Parent::operator=(cmap);
142 template <typename _Value>
143 class ArcMap : public Digraph::template ArcMap<_Value> {
146 typedef typename Digraph::template ArcMap<_Value> Parent;
148 explicit ArcMap(const Adaptor& adaptor)
149 : Parent(*adaptor._digraph) {}
151 ArcMap(const Adaptor& adaptor, const _Value& value)
152 : Parent(*adaptor._digraph, value) {}
155 ArcMap& operator=(const ArcMap& cmap) {
156 return operator=<ArcMap>(cmap);
159 template <typename CMap>
160 ArcMap& operator=(const CMap& cmap) {
161 Parent::operator=(cmap);
169 ///\ingroup graph_adaptors
171 ///\brief Trivial Digraph Adaptor
173 /// This class is an adaptor which does not change the adapted
174 /// digraph. It can be used only to test the digraph adaptors.
175 template <typename _Digraph>
176 class DigraphAdaptor :
177 public DigraphAdaptorExtender<DigraphAdaptorBase<_Digraph> > {
179 typedef _Digraph Digraph;
180 typedef DigraphAdaptorExtender<DigraphAdaptorBase<_Digraph> > Parent;
182 DigraphAdaptor() : Parent() { }
185 explicit DigraphAdaptor(Digraph& digraph) { setDigraph(digraph); }
188 /// \brief Just gives back a digraph adaptor
190 /// Just gives back a digraph adaptor which
191 /// should be provide original digraph
192 template<typename Digraph>
193 DigraphAdaptor<const Digraph>
194 digraphAdaptor(const Digraph& digraph) {
195 return DigraphAdaptor<const Digraph>(digraph);
199 template <typename _Digraph>
200 class RevDigraphAdaptorBase : public DigraphAdaptorBase<_Digraph> {
202 typedef _Digraph Digraph;
203 typedef DigraphAdaptorBase<_Digraph> Parent;
205 RevDigraphAdaptorBase() : Parent() { }
207 typedef typename Parent::Node Node;
208 typedef typename Parent::Arc Arc;
210 void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }
211 void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); }
213 void nextIn(Arc& a) const { Parent::nextOut(a); }
214 void nextOut(Arc& a) const { Parent::nextIn(a); }
216 Node source(const Arc& a) const { return Parent::target(a); }
217 Node target(const Arc& a) const { return Parent::source(a); }
219 typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
220 Arc findArc(const Node& u, const Node& v,
221 const Arc& prev = INVALID) {
222 return Parent::findArc(v, u, prev);
228 ///\ingroup graph_adaptors
230 ///\brief A digraph adaptor which reverses the orientation of the arcs.
232 /// If \c g is defined as
238 /// RevDigraphAdaptor<ListDigraph> ga(g);
240 /// implements the digraph obtained from \c g by
241 /// reversing the orientation of its arcs.
243 /// A good example of using RevDigraphAdaptor is to decide that the
244 /// directed graph is wheter strongly connected or not. If from one
245 /// node each node is reachable and from each node is reachable this
246 /// node then and just then the digraph is strongly
247 /// connected. Instead of this condition we use a little bit
248 /// different. From one node each node ahould be reachable in the
249 /// digraph and in the reversed digraph. Now this condition can be
250 /// checked with the Dfs algorithm class and the RevDigraphAdaptor
253 /// And look at the code:
256 /// bool stronglyConnected(const Digraph& digraph) {
257 /// if (NodeIt(digraph) == INVALID) return true;
258 /// Dfs<Digraph> dfs(digraph);
259 /// dfs.run(NodeIt(digraph));
260 /// for (NodeIt it(digraph); it != INVALID; ++it) {
261 /// if (!dfs.reached(it)) {
265 /// typedef RevDigraphAdaptor<const Digraph> RDigraph;
266 /// RDigraph rdigraph(digraph);
267 /// DfsVisit<RDigraph> rdfs(rdigraph);
268 /// rdfs.run(NodeIt(digraph));
269 /// for (NodeIt it(digraph); it != INVALID; ++it) {
270 /// if (!rdfs.reached(it)) {
277 template<typename _Digraph>
278 class RevDigraphAdaptor :
279 public DigraphAdaptorExtender<RevDigraphAdaptorBase<_Digraph> > {
281 typedef _Digraph Digraph;
282 typedef DigraphAdaptorExtender<
283 RevDigraphAdaptorBase<_Digraph> > Parent;
285 RevDigraphAdaptor() { }
287 explicit RevDigraphAdaptor(Digraph& digraph) {
288 Parent::setDigraph(digraph);
292 /// \brief Just gives back a reverse digraph adaptor
294 /// Just gives back a reverse digraph adaptor
295 template<typename Digraph>
296 RevDigraphAdaptor<const Digraph>
297 revDigraphAdaptor(const Digraph& digraph) {
298 return RevDigraphAdaptor<const Digraph>(digraph);
301 template <typename _Digraph, typename _NodeFilterMap,
302 typename _ArcFilterMap, bool checked = true>
303 class SubDigraphAdaptorBase : public DigraphAdaptorBase<_Digraph> {
305 typedef _Digraph Digraph;
306 typedef _NodeFilterMap NodeFilterMap;
307 typedef _ArcFilterMap ArcFilterMap;
309 typedef SubDigraphAdaptorBase Adaptor;
310 typedef DigraphAdaptorBase<_Digraph> Parent;
312 NodeFilterMap* _node_filter;
313 ArcFilterMap* _arc_filter;
314 SubDigraphAdaptorBase()
315 : Parent(), _node_filter(0), _arc_filter(0) { }
317 void setNodeFilterMap(NodeFilterMap& node_filter) {
318 _node_filter = &node_filter;
320 void setArcFilterMap(ArcFilterMap& arc_filter) {
321 _arc_filter = &arc_filter;
326 typedef typename Parent::Node Node;
327 typedef typename Parent::Arc Arc;
329 void first(Node& i) const {
331 while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
334 void first(Arc& i) const {
336 while (i != INVALID && (!(*_arc_filter)[i]
337 || !(*_node_filter)[Parent::source(i)]
338 || !(*_node_filter)[Parent::target(i)])) Parent::next(i);
341 void firstIn(Arc& i, const Node& n) const {
342 Parent::firstIn(i, n);
343 while (i != INVALID && (!(*_arc_filter)[i]
344 || !(*_node_filter)[Parent::source(i)])) Parent::nextIn(i);
347 void firstOut(Arc& i, const Node& n) const {
348 Parent::firstOut(i, n);
349 while (i != INVALID && (!(*_arc_filter)[i]
350 || !(*_node_filter)[Parent::target(i)])) Parent::nextOut(i);
353 void next(Node& i) const {
355 while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
358 void next(Arc& i) const {
360 while (i != INVALID && (!(*_arc_filter)[i]
361 || !(*_node_filter)[Parent::source(i)]
362 || !(*_node_filter)[Parent::target(i)])) Parent::next(i);
365 void nextIn(Arc& i) const {
367 while (i != INVALID && (!(*_arc_filter)[i]
368 || !(*_node_filter)[Parent::source(i)])) Parent::nextIn(i);
371 void nextOut(Arc& i) const {
373 while (i != INVALID && (!(*_arc_filter)[i]
374 || !(*_node_filter)[Parent::target(i)])) Parent::nextOut(i);
379 /// This function hides \c n in the digraph, i.e. the iteration
380 /// jumps over it. This is done by simply setting the value of \c n
381 /// to be false in the corresponding node-map.
382 void hide(const Node& n) const { _node_filter->set(n, false); }
386 /// This function hides \c a in the digraph, i.e. the iteration
387 /// jumps over it. This is done by simply setting the value of \c a
388 /// to be false in the corresponding arc-map.
389 void hide(const Arc& a) const { _arc_filter->set(a, false); }
393 /// The value of \c n is set to be true in the node-map which stores
394 /// hide information. If \c n was hidden previuosly, then it is shown
396 void unHide(const Node& n) const { _node_filter->set(n, true); }
400 /// The value of \c a is set to be true in the arc-map which stores
401 /// hide information. If \c a was hidden previuosly, then it is shown
403 void unHide(const Arc& a) const { _arc_filter->set(a, true); }
405 /// Returns true if \c n is hidden.
409 bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
411 /// Returns true if \c a is hidden.
415 bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }
417 typedef False NodeNumTag;
418 typedef False EdgeNumTag;
420 typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
421 Arc findArc(const Node& source, const Node& target,
422 const Arc& prev = INVALID) {
423 if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
426 Arc arc = Parent::findArc(source, target, prev);
427 while (arc != INVALID && !(*_arc_filter)[arc]) {
428 arc = Parent::findArc(source, target, arc);
433 template <typename _Value>
434 class NodeMap : public SubMapExtender<Adaptor,
435 typename Parent::template NodeMap<_Value> > {
437 typedef _Value Value;
438 typedef SubMapExtender<Adaptor, typename Parent::
439 template NodeMap<Value> > MapParent;
441 NodeMap(const Adaptor& adaptor)
442 : MapParent(adaptor) {}
443 NodeMap(const Adaptor& adaptor, const Value& value)
444 : MapParent(adaptor, value) {}
447 NodeMap& operator=(const NodeMap& cmap) {
448 return operator=<NodeMap>(cmap);
451 template <typename CMap>
452 NodeMap& operator=(const CMap& cmap) {
453 MapParent::operator=(cmap);
458 template <typename _Value>
459 class ArcMap : public SubMapExtender<Adaptor,
460 typename Parent::template ArcMap<_Value> > {
462 typedef _Value Value;
463 typedef SubMapExtender<Adaptor, typename Parent::
464 template ArcMap<Value> > MapParent;
466 ArcMap(const Adaptor& adaptor)
467 : MapParent(adaptor) {}
468 ArcMap(const Adaptor& adaptor, const Value& value)
469 : MapParent(adaptor, value) {}
472 ArcMap& operator=(const ArcMap& cmap) {
473 return operator=<ArcMap>(cmap);
476 template <typename CMap>
477 ArcMap& operator=(const CMap& cmap) {
478 MapParent::operator=(cmap);
485 template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>
486 class SubDigraphAdaptorBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>
487 : public DigraphAdaptorBase<_Digraph> {
489 typedef _Digraph Digraph;
490 typedef _NodeFilterMap NodeFilterMap;
491 typedef _ArcFilterMap ArcFilterMap;
493 typedef SubDigraphAdaptorBase Adaptor;
494 typedef DigraphAdaptorBase<Digraph> Parent;
496 NodeFilterMap* _node_filter;
497 ArcFilterMap* _arc_filter;
498 SubDigraphAdaptorBase()
499 : Parent(), _node_filter(0), _arc_filter(0) { }
501 void setNodeFilterMap(NodeFilterMap& node_filter) {
502 _node_filter = &node_filter;
504 void setArcFilterMap(ArcFilterMap& arc_filter) {
505 _arc_filter = &arc_filter;
510 typedef typename Parent::Node Node;
511 typedef typename Parent::Arc Arc;
513 void first(Node& i) const {
515 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
518 void first(Arc& i) const {
520 while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
523 void firstIn(Arc& i, const Node& n) const {
524 Parent::firstIn(i, n);
525 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
528 void firstOut(Arc& i, const Node& n) const {
529 Parent::firstOut(i, n);
530 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
533 void next(Node& i) const {
535 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
537 void next(Arc& i) const {
539 while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
541 void nextIn(Arc& i) const {
543 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
546 void nextOut(Arc& i) const {
548 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
553 /// This function hides \c n in the digraph, i.e. the iteration
554 /// jumps over it. This is done by simply setting the value of \c n
555 /// to be false in the corresponding node-map.
556 void hide(const Node& n) const { _node_filter->set(n, false); }
560 /// This function hides \c e in the digraph, i.e. the iteration
561 /// jumps over it. This is done by simply setting the value of \c e
562 /// to be false in the corresponding arc-map.
563 void hide(const Arc& e) const { _arc_filter->set(e, false); }
567 /// The value of \c n is set to be true in the node-map which stores
568 /// hide information. If \c n was hidden previuosly, then it is shown
570 void unHide(const Node& n) const { _node_filter->set(n, true); }
574 /// The value of \c e is set to be true in the arc-map which stores
575 /// hide information. If \c e was hidden previuosly, then it is shown
577 void unHide(const Arc& e) const { _arc_filter->set(e, true); }
579 /// Returns true if \c n is hidden.
583 bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
585 /// Returns true if \c n is hidden.
589 bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }
591 typedef False NodeNumTag;
592 typedef False EdgeNumTag;
594 typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
595 Arc findArc(const Node& source, const Node& target,
596 const Arc& prev = INVALID) {
597 if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
600 Arc arc = Parent::findArc(source, target, prev);
601 while (arc != INVALID && !(*_arc_filter)[arc]) {
602 arc = Parent::findArc(source, target, arc);
607 template <typename _Value>
608 class NodeMap : public SubMapExtender<Adaptor,
609 typename Parent::template NodeMap<_Value> > {
611 typedef _Value Value;
612 typedef SubMapExtender<Adaptor, typename Parent::
613 template NodeMap<Value> > MapParent;
615 NodeMap(const Adaptor& adaptor)
616 : MapParent(adaptor) {}
617 NodeMap(const Adaptor& adaptor, const Value& value)
618 : MapParent(adaptor, value) {}
621 NodeMap& operator=(const NodeMap& cmap) {
622 return operator=<NodeMap>(cmap);
625 template <typename CMap>
626 NodeMap& operator=(const CMap& cmap) {
627 MapParent::operator=(cmap);
632 template <typename _Value>
633 class ArcMap : public SubMapExtender<Adaptor,
634 typename Parent::template ArcMap<_Value> > {
636 typedef _Value Value;
637 typedef SubMapExtender<Adaptor, typename Parent::
638 template ArcMap<Value> > MapParent;
640 ArcMap(const Adaptor& adaptor)
641 : MapParent(adaptor) {}
642 ArcMap(const Adaptor& adaptor, const Value& value)
643 : MapParent(adaptor, value) {}
646 ArcMap& operator=(const ArcMap& cmap) {
647 return operator=<ArcMap>(cmap);
650 template <typename CMap>
651 ArcMap& operator=(const CMap& cmap) {
652 MapParent::operator=(cmap);
659 /// \ingroup graph_adaptors
661 /// \brief A digraph adaptor for hiding nodes and arcs from a digraph.
663 /// SubDigraphAdaptor shows the digraph with filtered node-set and
664 /// arc-set. If the \c checked parameter is true then it filters the arcset
665 /// to do not get invalid arcs without source or target.
666 /// Let \f$ G=(V, A) \f$ be a directed digraph
667 /// and suppose that the digraph instance \c g of type ListDigraph
668 /// implements \f$ G \f$.
669 /// Let moreover \f$ b_V \f$ and \f$ b_A \f$ be bool-valued functions resp.
670 /// on the node-set and arc-set.
671 /// SubDigraphAdaptor<...>::NodeIt iterates
672 /// on the node-set \f$ \{v\in V : b_V(v)=true\} \f$ and
673 /// SubDigraphAdaptor<...>::ArcIt iterates
674 /// on the arc-set \f$ \{e\in A : b_A(e)=true\} \f$. Similarly,
675 /// SubDigraphAdaptor<...>::OutArcIt and
676 /// SubDigraphAdaptor<...>::InArcIt iterates
677 /// only on arcs leaving and entering a specific node which have true value.
679 /// If the \c checked template parameter is false then we have to
680 /// note that the node-iterator cares only the filter on the
681 /// node-set, and the arc-iterator cares only the filter on the
682 /// arc-set. This way the arc-map should filter all arcs which's
683 /// source or target is filtered by the node-filter.
685 /// typedef ListDigraph Digraph;
686 /// DIGRAPH_TYPEDEFS(Digraph);
688 /// Node u=g.addNode(); //node of id 0
689 /// Node v=g.addNode(); //node of id 1
690 /// Arc a=g.addArc(u, v); //arc of id 0
691 /// Arc f=g.addArc(v, u); //arc of id 1
692 /// BoolNodeMap nm(g, true);
693 /// nm.set(u, false);
694 /// BoolArcMap am(g, true);
695 /// am.set(a, false);
696 /// typedef SubDigraphAdaptor<Digraph, BoolNodeMap, BoolArcMap> SubGA;
697 /// SubGA ga(g, nm, am);
698 /// for (SubGA::NodeIt n(ga); n!=INVALID; ++n)
699 /// std::cout << g.id(n) << std::endl;
700 /// std::cout << ":-)" << std::endl;
701 /// for (SubGA::ArcIt a(ga); a!=INVALID; ++a)
702 /// std::cout << g.id(a) << std::endl;
704 /// The output of the above code is the following.
710 /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
711 /// \c Digraph::Node that is why \c g.id(n) can be applied.
713 /// For other examples see also the documentation of
714 /// NodeSubDigraphAdaptor and ArcSubDigraphAdaptor.
715 template<typename _Digraph,
716 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
717 typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,
719 class SubDigraphAdaptor :
720 public DigraphAdaptorExtender<
721 SubDigraphAdaptorBase<_Digraph, _NodeFilterMap, _ArcFilterMap, checked> > {
723 typedef _Digraph Digraph;
724 typedef _NodeFilterMap NodeFilterMap;
725 typedef _ArcFilterMap ArcFilterMap;
727 typedef DigraphAdaptorExtender<
728 SubDigraphAdaptorBase<Digraph, NodeFilterMap, ArcFilterMap, checked> >
732 SubDigraphAdaptor() { }
735 SubDigraphAdaptor(Digraph& digraph, NodeFilterMap& node_filter,
736 ArcFilterMap& arc_filter) {
738 setNodeFilterMap(node_filter);
739 setArcFilterMap(arc_filter);
744 /// \brief Just gives back a sub digraph adaptor
746 /// Just gives back a sub digraph adaptor
747 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
748 SubDigraphAdaptor<const Digraph, NodeFilterMap, ArcFilterMap>
749 subDigraphAdaptor(const Digraph& digraph,
750 NodeFilterMap& nfm, ArcFilterMap& afm) {
751 return SubDigraphAdaptor<const Digraph, NodeFilterMap, ArcFilterMap>
755 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
756 SubDigraphAdaptor<const Digraph, const NodeFilterMap, ArcFilterMap>
757 subDigraphAdaptor(const Digraph& digraph,
758 NodeFilterMap& nfm, ArcFilterMap& afm) {
759 return SubDigraphAdaptor<const Digraph, const NodeFilterMap, ArcFilterMap>
763 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
764 SubDigraphAdaptor<const Digraph, NodeFilterMap, const ArcFilterMap>
765 subDigraphAdaptor(const Digraph& digraph,
766 NodeFilterMap& nfm, ArcFilterMap& afm) {
767 return SubDigraphAdaptor<const Digraph, NodeFilterMap, const ArcFilterMap>
771 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
772 SubDigraphAdaptor<const Digraph, const NodeFilterMap, const ArcFilterMap>
773 subDigraphAdaptor(const Digraph& digraph,
774 NodeFilterMap& nfm, ArcFilterMap& afm) {
775 return SubDigraphAdaptor<const Digraph, const NodeFilterMap,
776 const ArcFilterMap>(digraph, nfm, afm);
781 ///\ingroup graph_adaptors
783 ///\brief An adaptor for hiding nodes from a digraph.
785 ///An adaptor for hiding nodes from a digraph. This adaptor
786 ///specializes SubDigraphAdaptor in the way that only the node-set
787 ///can be filtered. In usual case the checked parameter is true, we
788 ///get the induced subgraph. But if the checked parameter is false
789 ///then we can filter only isolated nodes.
790 template<typename _Digraph,
791 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
793 class NodeSubDigraphAdaptor :
794 public SubDigraphAdaptor<_Digraph, _NodeFilterMap,
795 ConstMap<typename _Digraph::Arc, bool>, checked> {
798 typedef _Digraph Digraph;
799 typedef _NodeFilterMap NodeFilterMap;
801 typedef SubDigraphAdaptor<Digraph, NodeFilterMap,
802 ConstMap<typename Digraph::Arc, bool>, checked>
806 ConstMap<typename Digraph::Arc, bool> const_true_map;
808 NodeSubDigraphAdaptor() : const_true_map(true) {
809 Parent::setArcFilterMap(const_true_map);
814 NodeSubDigraphAdaptor(Digraph& _digraph, NodeFilterMap& node_filter) :
815 Parent(), const_true_map(true) {
816 Parent::setDigraph(_digraph);
817 Parent::setNodeFilterMap(node_filter);
818 Parent::setArcFilterMap(const_true_map);
824 /// \brief Just gives back a \c NodeSubDigraphAdaptor
826 /// Just gives back a \c NodeSubDigraphAdaptor
827 template<typename Digraph, typename NodeFilterMap>
828 NodeSubDigraphAdaptor<const Digraph, NodeFilterMap>
829 nodeSubDigraphAdaptor(const Digraph& digraph, NodeFilterMap& nfm) {
830 return NodeSubDigraphAdaptor<const Digraph, NodeFilterMap>(digraph, nfm);
833 template<typename Digraph, typename NodeFilterMap>
834 NodeSubDigraphAdaptor<const Digraph, const NodeFilterMap>
835 nodeSubDigraphAdaptor(const Digraph& digraph, const NodeFilterMap& nfm) {
836 return NodeSubDigraphAdaptor<const Digraph, const NodeFilterMap>
840 ///\ingroup graph_adaptors
842 ///\brief An adaptor for hiding arcs from a digraph.
844 ///An adaptor for hiding arcs from a digraph. This adaptor
845 ///specializes SubDigraphAdaptor in the way that only the arc-set
846 ///can be filtered. The usefulness of this adaptor is demonstrated
847 ///in the problem of searching a maximum number of arc-disjoint
848 ///shortest paths between two nodes \c s and \c t. Shortest here
849 ///means being shortest w.r.t. non-negative arc-lengths. Note that
850 ///the comprehension of the presented solution need's some
851 ///elementary knowlarc from combinatorial optimization.
853 ///If a single shortest path is to be searched between \c s and \c
854 ///t, then this can be done easily by applying the Dijkstra
855 ///algorithm. What happens, if a maximum number of arc-disjoint
856 ///shortest paths is to be computed. It can be proved that an arc
857 ///can be in a shortest path if and only if it is tight with respect
858 ///to the potential function computed by Dijkstra. Moreover, any
859 ///path containing only such arcs is a shortest one. Thus we have
860 ///to compute a maximum number of arc-disjoint paths between \c s
861 ///and \c t in the digraph which has arc-set all the tight arcs. The
862 ///computation will be demonstrated on the following digraph, which
863 ///is read from the dimacs file \c sub_digraph_adaptor_demo.dim.
864 ///The full source code is available in \ref
865 ///sub_digraph_adaptor_demo.cc. If you are interested in more demo
866 ///programs, you can use \ref dim_to_dot.cc to generate .dot files
867 ///from dimacs files. The .dot file of the following figure was
868 ///generated by the demo program \ref dim_to_dot.cc.
871 ///didigraph lemon_dot_example {
872 ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
873 ///n0 [ label="0 (s)" ];
879 ///n6 [ label="6 (t)" ];
880 ///arc [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
881 ///n5 -> n6 [ label="9, length:4" ];
882 ///n4 -> n6 [ label="8, length:2" ];
883 ///n3 -> n5 [ label="7, length:1" ];
884 ///n2 -> n5 [ label="6, length:3" ];
885 ///n2 -> n6 [ label="5, length:5" ];
886 ///n2 -> n4 [ label="4, length:2" ];
887 ///n1 -> n4 [ label="3, length:3" ];
888 ///n0 -> n3 [ label="2, length:1" ];
889 ///n0 -> n2 [ label="1, length:2" ];
890 ///n0 -> n1 [ label="0, length:3" ];
897 ///LengthMap length(g);
899 ///readDimacs(std::cin, g, length, s, t);
901 ///cout << "arcs with lengths (of form id, source--length->target): " << endl;
902 ///for(ArcIt e(g); e!=INVALID; ++e)
903 /// cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
904 /// << length[e] << "->" << g.id(g.target(e)) << endl;
906 ///cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
908 ///Next, the potential function is computed with Dijkstra.
910 ///typedef Dijkstra<Digraph, LengthMap> Dijkstra;
911 ///Dijkstra dijkstra(g, length);
914 ///Next, we consrtruct a map which filters the arc-set to the tight arcs.
916 ///typedef TightArcFilterMap<Digraph, const Dijkstra::DistMap, LengthMap>
918 ///TightArcFilter tight_arc_filter(g, dijkstra.distMap(), length);
920 ///typedef ArcSubDigraphAdaptor<Digraph, TightArcFilter> SubGA;
921 ///SubGA ga(g, tight_arc_filter);
923 ///Then, the maximum nimber of arc-disjoint \c s-\c t paths are computed
924 ///with a max flow algorithm Preflow.
926 ///ConstMap<Arc, int> const_1_map(1);
927 ///Digraph::ArcMap<int> flow(g, 0);
929 ///Preflow<SubGA, ConstMap<Arc, int>, Digraph::ArcMap<int> >
930 /// preflow(ga, const_1_map, s, t);
933 ///Last, the output is:
935 ///cout << "maximum number of arc-disjoint shortest path: "
936 /// << preflow.flowValue() << endl;
937 ///cout << "arcs of the maximum number of arc-disjoint shortest s-t paths: "
939 ///for(ArcIt e(g); e!=INVALID; ++e)
940 /// if (preflow.flow(e))
941 /// cout << " " << g.id(g.source(e)) << "--"
942 /// << length[e] << "->" << g.id(g.target(e)) << endl;
944 ///The program has the following (expected :-)) output:
946 ///arcs with lengths (of form id, source--length->target):
958 ///maximum number of arc-disjoint shortest path: 2
959 ///arcs of the maximum number of arc-disjoint shortest s-t paths:
967 template<typename _Digraph, typename _ArcFilterMap>
968 class ArcSubDigraphAdaptor :
969 public SubDigraphAdaptor<_Digraph, ConstMap<typename _Digraph::Node, bool>,
970 _ArcFilterMap, false> {
972 typedef _Digraph Digraph;
973 typedef _ArcFilterMap ArcFilterMap;
975 typedef SubDigraphAdaptor<Digraph, ConstMap<typename Digraph::Node, bool>,
976 ArcFilterMap, false> Parent;
978 ConstMap<typename Digraph::Node, bool> const_true_map;
980 ArcSubDigraphAdaptor() : const_true_map(true) {
981 Parent::setNodeFilterMap(const_true_map);
986 ArcSubDigraphAdaptor(Digraph& digraph, ArcFilterMap& arc_filter)
987 : Parent(), const_true_map(true) {
988 Parent::setDigraph(digraph);
989 Parent::setNodeFilterMap(const_true_map);
990 Parent::setArcFilterMap(arc_filter);
995 /// \brief Just gives back an arc sub digraph adaptor
997 /// Just gives back an arc sub digraph adaptor
998 template<typename Digraph, typename ArcFilterMap>
999 ArcSubDigraphAdaptor<const Digraph, ArcFilterMap>
1000 arcSubDigraphAdaptor(const Digraph& digraph, ArcFilterMap& afm) {
1001 return ArcSubDigraphAdaptor<const Digraph, ArcFilterMap>(digraph, afm);
1004 template<typename Digraph, typename ArcFilterMap>
1005 ArcSubDigraphAdaptor<const Digraph, const ArcFilterMap>
1006 arcSubDigraphAdaptor(const Digraph& digraph, const ArcFilterMap& afm) {
1007 return ArcSubDigraphAdaptor<const Digraph, const ArcFilterMap>
1011 template <typename _Digraph>
1012 class UndirDigraphAdaptorBase {
1014 typedef _Digraph Digraph;
1015 typedef UndirDigraphAdaptorBase Adaptor;
1017 typedef True UndirectedTag;
1019 typedef typename Digraph::Arc Edge;
1020 typedef typename Digraph::Node Node;
1022 class Arc : public Edge {
1023 friend class UndirDigraphAdaptorBase;
1027 Arc(const Edge& edge, bool forward) :
1028 Edge(edge), _forward(forward) {}
1033 Arc(Invalid) : Edge(INVALID), _forward(true) {}
1035 bool operator==(const Arc &other) const {
1036 return _forward == other._forward &&
1037 static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
1039 bool operator!=(const Arc &other) const {
1040 return _forward != other._forward ||
1041 static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
1043 bool operator<(const Arc &other) const {
1044 return _forward < other._forward ||
1045 (_forward == other._forward &&
1046 static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
1052 void first(Node& n) const {
1056 void next(Node& n) const {
1060 void first(Arc& a) const {
1065 void next(Arc& a) const {
1074 void first(Edge& e) const {
1078 void next(Edge& e) const {
1082 void firstOut(Arc& a, const Node& n) const {
1083 _digraph->firstIn(a, n);
1084 if( static_cast<const Edge&>(a) != INVALID ) {
1087 _digraph->firstOut(a, n);
1091 void nextOut(Arc &a) const {
1093 Node n = _digraph->target(a);
1094 _digraph->nextIn(a);
1095 if (static_cast<const Edge&>(a) == INVALID ) {
1096 _digraph->firstOut(a, n);
1101 _digraph->nextOut(a);
1105 void firstIn(Arc &a, const Node &n) const {
1106 _digraph->firstOut(a, n);
1107 if (static_cast<const Edge&>(a) != INVALID ) {
1110 _digraph->firstIn(a, n);
1114 void nextIn(Arc &a) const {
1116 Node n = _digraph->source(a);
1117 _digraph->nextOut(a);
1118 if( static_cast<const Edge&>(a) == INVALID ) {
1119 _digraph->firstIn(a, n);
1124 _digraph->nextIn(a);
1128 void firstInc(Edge &e, bool &d, const Node &n) const {
1130 _digraph->firstOut(e, n);
1131 if (e != INVALID) return;
1133 _digraph->firstIn(e, n);
1136 void nextInc(Edge &e, bool &d) const {
1138 Node s = _digraph->source(e);
1139 _digraph->nextOut(e);
1140 if (e != INVALID) return;
1142 _digraph->firstIn(e, s);
1144 _digraph->nextIn(e);
1148 Node u(const Edge& e) const {
1149 return _digraph->source(e);
1152 Node v(const Edge& e) const {
1153 return _digraph->target(e);
1156 Node source(const Arc &a) const {
1157 return a._forward ? _digraph->source(a) : _digraph->target(a);
1160 Node target(const Arc &a) const {
1161 return a._forward ? _digraph->target(a) : _digraph->source(a);
1164 static Arc direct(const Edge &e, bool d) {
1167 Arc direct(const Edge &e, const Node& n) const {
1168 return Arc(e, _digraph->source(e) == n);
1171 static bool direction(const Arc &a) { return a._forward; }
1173 Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
1174 Arc arcFromId(int ix) const {
1175 return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1));
1177 Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); }
1179 int id(const Node &n) const { return _digraph->id(n); }
1180 int id(const Arc &a) const {
1181 return (_digraph->id(a) << 1) | (a._forward ? 1 : 0);
1183 int id(const Edge &e) const { return _digraph->id(e); }
1185 int maxNodeId() const { return _digraph->maxNodeId(); }
1186 int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; }
1187 int maxEdgeId() const { return _digraph->maxArcId(); }
1189 Node addNode() { return _digraph->addNode(); }
1190 Edge addEdge(const Node& u, const Node& v) {
1191 return _digraph->addArc(u, v);
1194 void erase(const Node& i) { _digraph->erase(i); }
1195 void erase(const Edge& i) { _digraph->erase(i); }
1197 void clear() { _digraph->clear(); }
1199 typedef NodeNumTagIndicator<Digraph> NodeNumTag;
1200 int nodeNum() const { return 2 * _digraph->arcNum(); }
1201 typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
1202 int arcNum() const { return 2 * _digraph->arcNum(); }
1203 int edgeNum() const { return _digraph->arcNum(); }
1205 typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
1206 Arc findArc(Node s, Node t, Arc p = INVALID) const {
1208 Edge arc = _digraph->findArc(s, t);
1209 if (arc != INVALID) return direct(arc, true);
1210 arc = _digraph->findArc(t, s);
1211 if (arc != INVALID) return direct(arc, false);
1212 } else if (direction(p)) {
1213 Edge arc = _digraph->findArc(s, t, p);
1214 if (arc != INVALID) return direct(arc, true);
1215 arc = _digraph->findArc(t, s);
1216 if (arc != INVALID) return direct(arc, false);
1218 Edge arc = _digraph->findArc(t, s, p);
1219 if (arc != INVALID) return direct(arc, false);
1224 Edge findEdge(Node s, Node t, Edge p = INVALID) const {
1227 Edge arc = _digraph->findArc(s, t);
1228 if (arc != INVALID) return arc;
1229 arc = _digraph->findArc(t, s);
1230 if (arc != INVALID) return arc;
1231 } else if (_digraph->s(p) == s) {
1232 Edge arc = _digraph->findArc(s, t, p);
1233 if (arc != INVALID) return arc;
1234 arc = _digraph->findArc(t, s);
1235 if (arc != INVALID) return arc;
1237 Edge arc = _digraph->findArc(t, s, p);
1238 if (arc != INVALID) return arc;
1241 return _digraph->findArc(s, t, p);
1248 template <typename _Value>
1252 typedef typename Digraph::template ArcMap<_Value> MapImpl;
1256 typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
1258 typedef _Value Value;
1261 ArcMapBase(const Adaptor& adaptor) :
1262 _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
1264 ArcMapBase(const Adaptor& adaptor, const Value& v)
1265 : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}
1267 void set(const Arc& a, const Value& v) {
1271 _backward.set(a, v);
1275 typename MapTraits<MapImpl>::ConstReturnValue
1276 operator[](const Arc& a) const {
1280 return _backward[a];
1284 typename MapTraits<MapImpl>::ReturnValue
1285 operator[](const Arc& a) {
1289 return _backward[a];
1295 MapImpl _forward, _backward;
1301 template <typename _Value>
1302 class NodeMap : public Digraph::template NodeMap<_Value> {
1305 typedef _Value Value;
1306 typedef typename Digraph::template NodeMap<Value> Parent;
1308 explicit NodeMap(const Adaptor& adaptor)
1309 : Parent(*adaptor._digraph) {}
1311 NodeMap(const Adaptor& adaptor, const _Value& value)
1312 : Parent(*adaptor._digraph, value) { }
1315 NodeMap& operator=(const NodeMap& cmap) {
1316 return operator=<NodeMap>(cmap);
1319 template <typename CMap>
1320 NodeMap& operator=(const CMap& cmap) {
1321 Parent::operator=(cmap);
1327 template <typename _Value>
1329 : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
1332 typedef _Value Value;
1333 typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
1335 ArcMap(const Adaptor& adaptor)
1336 : Parent(adaptor) {}
1338 ArcMap(const Adaptor& adaptor, const Value& value)
1339 : Parent(adaptor, value) {}
1342 ArcMap& operator=(const ArcMap& cmap) {
1343 return operator=<ArcMap>(cmap);
1346 template <typename CMap>
1347 ArcMap& operator=(const CMap& cmap) {
1348 Parent::operator=(cmap);
1353 template <typename _Value>
1354 class EdgeMap : public Digraph::template ArcMap<_Value> {
1357 typedef _Value Value;
1358 typedef typename Digraph::template ArcMap<Value> Parent;
1360 explicit EdgeMap(const Adaptor& adaptor)
1361 : Parent(*adaptor._digraph) {}
1363 EdgeMap(const Adaptor& adaptor, const Value& value)
1364 : Parent(*adaptor._digraph, value) {}
1367 EdgeMap& operator=(const EdgeMap& cmap) {
1368 return operator=<EdgeMap>(cmap);
1371 template <typename CMap>
1372 EdgeMap& operator=(const CMap& cmap) {
1373 Parent::operator=(cmap);
1379 typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
1380 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
1384 UndirDigraphAdaptorBase() : _digraph(0) {}
1388 void setDigraph(Digraph& digraph) {
1389 _digraph = &digraph;
1394 ///\ingroup graph_adaptors
1396 /// \brief An graph is made from a directed digraph by an adaptor
1398 /// This adaptor makes an undirected graph from a directed
1399 /// digraph. All arc of the underlying will be showed in the adaptor
1400 /// as an edge. Let's see an informal example about using
1403 /// There is a network of the streets of a town. Of course there are
1404 /// some one-way street in the town hence the network is a directed
1405 /// one. There is a crazy driver who go oppositely in the one-way
1406 /// street without moral sense. Of course he can pass this streets
1407 /// slower than the regular way, in fact his speed is half of the
1408 /// normal speed. How long should he drive to get from a source
1409 /// point to the target? Let see the example code which calculate it:
1411 /// \todo BadCode, SimpleMap does no exists
1413 /// typedef UndirDigraphAdaptor<Digraph> Graph;
1414 /// Graph graph(digraph);
1416 /// typedef SimpleMap<LengthMap> FLengthMap;
1417 /// FLengthMap flength(length);
1419 /// typedef ScaleMap<LengthMap> RLengthMap;
1420 /// RLengthMap rlength(length, 2.0);
1422 /// typedef Graph::CombinedArcMap<FLengthMap, RLengthMap > ULengthMap;
1423 /// ULengthMap ulength(flength, rlength);
1425 /// Dijkstra<Graph, ULengthMap> dijkstra(graph, ulength);
1426 /// std::cout << "Driving time : " << dijkstra.run(src, trg) << std::endl;
1429 /// The combined arc map makes the length map for the undirected
1430 /// graph. It is created from a forward and reverse map. The forward
1431 /// map is created from the original length map with a SimpleMap
1432 /// adaptor which just makes a read-write map from the reference map
1433 /// i.e. it forgets that it can be return reference to values. The
1434 /// reverse map is just the scaled original map with the ScaleMap
1435 /// adaptor. The combination solves that passing the reverse way
1436 /// takes double time than the original. To get the driving time we
1437 /// run the dijkstra algorithm on the graph.
1438 template<typename _Digraph>
1439 class UndirDigraphAdaptor
1440 : public GraphAdaptorExtender<UndirDigraphAdaptorBase<_Digraph> > {
1442 typedef _Digraph Digraph;
1443 typedef GraphAdaptorExtender<UndirDigraphAdaptorBase<Digraph> > Parent;
1445 UndirDigraphAdaptor() { }
1448 /// \brief Constructor
1451 UndirDigraphAdaptor(_Digraph& _digraph) {
1452 setDigraph(_digraph);
1455 /// \brief ArcMap combined from two original ArcMap
1457 /// This class adapts two original digraph ArcMap to
1458 /// get an arc map on the adaptor.
1459 template <typename _ForwardMap, typename _BackwardMap>
1460 class CombinedArcMap {
1463 typedef _ForwardMap ForwardMap;
1464 typedef _BackwardMap BackwardMap;
1466 typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
1468 typedef typename ForwardMap::Value Value;
1469 typedef typename Parent::Arc Key;
1471 /// \brief Constructor
1474 CombinedArcMap() : _forward(0), _backward(0) {}
1476 /// \brief Constructor
1479 CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
1480 : _forward(&forward), _backward(&backward) {}
1483 /// \brief Sets the value associated with a key.
1485 /// Sets the value associated with a key.
1486 void set(const Key& e, const Value& a) {
1487 if (Parent::direction(e)) {
1488 _forward->set(e, a);
1490 _backward->set(e, a);
1494 /// \brief Returns the value associated with a key.
1496 /// Returns the value associated with a key.
1497 typename MapTraits<ForwardMap>::ConstReturnValue
1498 operator[](const Key& e) const {
1499 if (Parent::direction(e)) {
1500 return (*_forward)[e];
1502 return (*_backward)[e];
1506 /// \brief Returns the value associated with a key.
1508 /// Returns the value associated with a key.
1509 typename MapTraits<ForwardMap>::ReturnValue
1510 operator[](const Key& e) {
1511 if (Parent::direction(e)) {
1512 return (*_forward)[e];
1514 return (*_backward)[e];
1518 /// \brief Sets the forward map
1520 /// Sets the forward map
1521 void setForwardMap(ForwardMap& forward) {
1522 _forward = &forward;
1525 /// \brief Sets the backward map
1527 /// Sets the backward map
1528 void setBackwardMap(BackwardMap& backward) {
1529 _backward = &backward;
1534 ForwardMap* _forward;
1535 BackwardMap* _backward;
1541 /// \brief Just gives back an undir digraph adaptor
1543 /// Just gives back an undir digraph adaptor
1544 template<typename Digraph>
1545 UndirDigraphAdaptor<const Digraph>
1546 undirDigraphAdaptor(const Digraph& digraph) {
1547 return UndirDigraphAdaptor<const Digraph>(digraph);
1550 template<typename _Digraph,
1551 typename _CapacityMap = typename _Digraph::template ArcMap<int>,
1552 typename _FlowMap = _CapacityMap,
1553 typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
1554 class ResForwardFilter {
1557 typedef _Digraph Digraph;
1558 typedef _CapacityMap CapacityMap;
1559 typedef _FlowMap FlowMap;
1560 typedef _Tolerance Tolerance;
1562 typedef typename Digraph::Arc Key;
1567 const CapacityMap* _capacity;
1568 const FlowMap* _flow;
1569 Tolerance _tolerance;
1572 ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,
1573 const Tolerance& tolerance = Tolerance())
1574 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
1576 ResForwardFilter(const Tolerance& tolerance = Tolerance())
1577 : _capacity(0), _flow(0), _tolerance(tolerance) { }
1579 void setCapacity(const CapacityMap& capacity) { _capacity = &capacity; }
1580 void setFlow(const FlowMap& flow) { _flow = &flow; }
1582 bool operator[](const typename Digraph::Arc& a) const {
1583 return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
1587 template<typename _Digraph,
1588 typename _CapacityMap = typename _Digraph::template ArcMap<int>,
1589 typename _FlowMap = _CapacityMap,
1590 typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
1591 class ResBackwardFilter {
1594 typedef _Digraph Digraph;
1595 typedef _CapacityMap CapacityMap;
1596 typedef _FlowMap FlowMap;
1597 typedef _Tolerance Tolerance;
1599 typedef typename Digraph::Arc Key;
1604 const CapacityMap* _capacity;
1605 const FlowMap* _flow;
1606 Tolerance _tolerance;
1610 ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,
1611 const Tolerance& tolerance = Tolerance())
1612 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
1613 ResBackwardFilter(const Tolerance& tolerance = Tolerance())
1614 : _capacity(0), _flow(0), _tolerance(tolerance) { }
1616 void setCapacity(const CapacityMap& capacity) { _capacity = &capacity; }
1617 void setFlow(const FlowMap& flow) { _flow = &flow; }
1619 bool operator[](const typename Digraph::Arc& a) const {
1620 return _tolerance.positive((*_flow)[a]);
1625 ///\ingroup graph_adaptors
1627 ///\brief An adaptor for composing the residual graph for directed
1628 ///flow and circulation problems.
1630 ///An adaptor for composing the residual graph for directed flow and
1631 ///circulation problems. Let \f$ G=(V, A) \f$ be a directed digraph
1632 ///and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F
1633 ///\f$, be functions on the arc-set.
1635 ///In the appications of ResDigraphAdaptor, \f$ f \f$ usually stands
1636 ///for a flow and \f$ c \f$ for a capacity function. Suppose that a
1637 ///graph instance \c g of type \c ListDigraph implements \f$ G \f$.
1643 ///Then ResDigraphAdaptor implements the digraph structure with
1644 /// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward}
1645 /// \f$, where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
1646 /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so
1647 /// called residual graph. When we take the union \f$
1648 /// A_{forward}\cup A_{backward} \f$, multilicities are counted,
1649 /// i.e. if an arc is in both \f$ A_{forward} \f$ and \f$
1650 /// A_{backward} \f$, then in the adaptor it appears twice. The
1651 /// following code shows how such an instance can be constructed.
1654 /// typedef ListDigraph Digraph;
1655 /// IntArcMap f(g), c(g);
1656 /// ResDigraphAdaptor<Digraph, int, IntArcMap, IntArcMap> ga(g);
1658 template<typename _Digraph,
1659 typename _CapacityMap = typename _Digraph::template ArcMap<int>,
1660 typename _FlowMap = _CapacityMap,
1661 typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
1662 class ResDigraphAdaptor :
1663 public ArcSubDigraphAdaptor<
1664 UndirDigraphAdaptor<const _Digraph>,
1665 typename UndirDigraphAdaptor<const _Digraph>::template CombinedArcMap<
1666 ResForwardFilter<const _Digraph, _CapacityMap, _FlowMap>,
1667 ResBackwardFilter<const _Digraph, _CapacityMap, _FlowMap> > > {
1670 typedef _Digraph Digraph;
1671 typedef _CapacityMap CapacityMap;
1672 typedef _FlowMap FlowMap;
1673 typedef _Tolerance Tolerance;
1675 typedef typename CapacityMap::Value Value;
1676 typedef ResDigraphAdaptor Adaptor;
1680 typedef UndirDigraphAdaptor<const Digraph> UndirDigraph;
1682 typedef ResForwardFilter<const Digraph, CapacityMap, FlowMap>
1685 typedef ResBackwardFilter<const Digraph, CapacityMap, FlowMap>
1688 typedef typename UndirDigraph::
1689 template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
1691 typedef ArcSubDigraphAdaptor<UndirDigraph, ArcFilter> Parent;
1693 const CapacityMap* _capacity;
1696 UndirDigraph _graph;
1697 ForwardFilter _forward_filter;
1698 BackwardFilter _backward_filter;
1699 ArcFilter _arc_filter;
1701 void setCapacityMap(const CapacityMap& capacity) {
1702 _capacity = &capacity;
1703 _forward_filter.setCapacity(capacity);
1704 _backward_filter.setCapacity(capacity);
1707 void setFlowMap(FlowMap& flow) {
1709 _forward_filter.setFlow(flow);
1710 _backward_filter.setFlow(flow);
1715 /// \brief Constructor of the residual digraph.
1717 /// Constructor of the residual graph. The parameters are the digraph type,
1718 /// the flow map, the capacity map and a tolerance object.
1719 ResDigraphAdaptor(const Digraph& digraph, const CapacityMap& capacity,
1720 FlowMap& flow, const Tolerance& tolerance = Tolerance())
1721 : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
1722 _forward_filter(capacity, flow, tolerance),
1723 _backward_filter(capacity, flow, tolerance),
1724 _arc_filter(_forward_filter, _backward_filter)
1726 Parent::setDigraph(_graph);
1727 Parent::setArcFilterMap(_arc_filter);
1730 typedef typename Parent::Arc Arc;
1732 /// \brief Gives back the residual capacity of the arc.
1734 /// Gives back the residual capacity of the arc.
1735 Value rescap(const Arc& arc) const {
1736 if (UndirDigraph::direction(arc)) {
1737 return (*_capacity)[arc] - (*_flow)[arc];
1739 return (*_flow)[arc];
1743 /// \brief Augment on the given arc in the residual digraph.
1745 /// Augment on the given arc in the residual digraph. It increase
1746 /// or decrease the flow on the original arc depend on the direction
1747 /// of the residual arc.
1748 void augment(const Arc& e, const Value& a) const {
1749 if (UndirDigraph::direction(e)) {
1750 _flow->set(e, (*_flow)[e] + a);
1752 _flow->set(e, (*_flow)[e] - a);
1756 /// \brief Returns the direction of the arc.
1758 /// Returns true when the arc is same oriented as the original arc.
1759 static bool forward(const Arc& e) {
1760 return UndirDigraph::direction(e);
1763 /// \brief Returns the direction of the arc.
1765 /// Returns true when the arc is opposite oriented as the original arc.
1766 static bool backward(const Arc& e) {
1767 return !UndirDigraph::direction(e);
1770 /// \brief Gives back the forward oriented residual arc.
1772 /// Gives back the forward oriented residual arc.
1773 static Arc forward(const typename Digraph::Arc& e) {
1774 return UndirDigraph::direct(e, true);
1777 /// \brief Gives back the backward oriented residual arc.
1779 /// Gives back the backward oriented residual arc.
1780 static Arc backward(const typename Digraph::Arc& e) {
1781 return UndirDigraph::direct(e, false);
1784 /// \brief Residual capacity map.
1786 /// In generic residual digraphs the residual capacity can be obtained
1790 const Adaptor* _adaptor;
1793 typedef typename _CapacityMap::Value Value;
1795 ResCap(const Adaptor& adaptor) : _adaptor(&adaptor) {}
1797 Value operator[](const Arc& e) const {
1798 return _adaptor->rescap(e);
1805 /// \brief Base class for split digraph adaptor
1807 /// Base class of split digraph adaptor. In most case you do not need to
1808 /// use it directly but the documented member functions of this class can
1809 /// be used with the SplitDigraphAdaptor class.
1810 /// \sa SplitDigraphAdaptor
1811 template <typename _Digraph>
1812 class SplitDigraphAdaptorBase {
1815 typedef _Digraph Digraph;
1816 typedef DigraphAdaptorBase<const _Digraph> Parent;
1817 typedef SplitDigraphAdaptorBase Adaptor;
1819 typedef typename Digraph::Node DigraphNode;
1820 typedef typename Digraph::Arc DigraphArc;
1827 template <typename T> class NodeMapBase;
1828 template <typename T> class ArcMapBase;
1832 class Node : public DigraphNode {
1833 friend class SplitDigraphAdaptorBase;
1834 template <typename T> friend class NodeMapBase;
1838 Node(DigraphNode node, bool in)
1839 : DigraphNode(node), _in(in) {}
1844 Node(Invalid) : DigraphNode(INVALID), _in(true) {}
1846 bool operator==(const Node& node) const {
1847 return DigraphNode::operator==(node) && _in == node._in;
1850 bool operator!=(const Node& node) const {
1851 return !(*this == node);
1854 bool operator<(const Node& node) const {
1855 return DigraphNode::operator<(node) ||
1856 (DigraphNode::operator==(node) && _in < node._in);
1861 friend class SplitDigraphAdaptorBase;
1862 template <typename T> friend class ArcMapBase;
1864 typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;
1866 explicit Arc(const DigraphArc& arc) : _item(arc) {}
1867 explicit Arc(const DigraphNode& node) : _item(node) {}
1873 Arc(Invalid) : _item(DigraphArc(INVALID)) {}
1875 bool operator==(const Arc& arc) const {
1876 if (_item.firstState()) {
1877 if (arc._item.firstState()) {
1878 return _item.first() == arc._item.first();
1881 if (arc._item.secondState()) {
1882 return _item.second() == arc._item.second();
1888 bool operator!=(const Arc& arc) const {
1889 return !(*this == arc);
1892 bool operator<(const Arc& arc) const {
1893 if (_item.firstState()) {
1894 if (arc._item.firstState()) {
1895 return _item.first() < arc._item.first();
1899 if (arc._item.secondState()) {
1900 return _item.second() < arc._item.second();
1906 operator DigraphArc() const { return _item.first(); }
1907 operator DigraphNode() const { return _item.second(); }
1911 void first(Node& n) const {
1916 void next(Node& n) const {
1925 void first(Arc& e) const {
1926 e._item.setSecond();
1927 _digraph->first(e._item.second());
1928 if (e._item.second() == INVALID) {
1930 _digraph->first(e._item.first());
1934 void next(Arc& e) const {
1935 if (e._item.secondState()) {
1936 _digraph->next(e._item.second());
1937 if (e._item.second() == INVALID) {
1939 _digraph->first(e._item.first());
1942 _digraph->next(e._item.first());
1946 void firstOut(Arc& e, const Node& n) const {
1948 e._item.setSecond(n);
1951 _digraph->firstOut(e._item.first(), n);
1955 void nextOut(Arc& e) const {
1956 if (!e._item.firstState()) {
1957 e._item.setFirst(INVALID);
1959 _digraph->nextOut(e._item.first());
1963 void firstIn(Arc& e, const Node& n) const {
1965 e._item.setSecond(n);
1968 _digraph->firstIn(e._item.first(), n);
1972 void nextIn(Arc& e) const {
1973 if (!e._item.firstState()) {
1974 e._item.setFirst(INVALID);
1976 _digraph->nextIn(e._item.first());
1980 Node source(const Arc& e) const {
1981 if (e._item.firstState()) {
1982 return Node(_digraph->source(e._item.first()), false);
1984 return Node(e._item.second(), true);
1988 Node target(const Arc& e) const {
1989 if (e._item.firstState()) {
1990 return Node(_digraph->target(e._item.first()), true);
1992 return Node(e._item.second(), false);
1996 int id(const Node& n) const {
1997 return (_digraph->id(n) << 1) | (n._in ? 0 : 1);
1999 Node nodeFromId(int ix) const {
2000 return Node(_digraph->nodeFromId(ix >> 1), (ix & 1) == 0);
2002 int maxNodeId() const {
2003 return 2 * _digraph->maxNodeId() + 1;
2006 int id(const Arc& e) const {
2007 if (e._item.firstState()) {
2008 return _digraph->id(e._item.first()) << 1;
2010 return (_digraph->id(e._item.second()) << 1) | 1;
2013 Arc arcFromId(int ix) const {
2014 if ((ix & 1) == 0) {
2015 return Arc(_digraph->arcFromId(ix >> 1));
2017 return Arc(_digraph->nodeFromId(ix >> 1));
2020 int maxArcId() const {
2021 return std::max(_digraph->maxNodeId() << 1,
2022 (_digraph->maxArcId() << 1) | 1);
2025 /// \brief Returns true when the node is in-node.
2027 /// Returns true when the node is in-node.
2028 static bool inNode(const Node& n) {
2032 /// \brief Returns true when the node is out-node.
2034 /// Returns true when the node is out-node.
2035 static bool outNode(const Node& n) {
2039 /// \brief Returns true when the arc is arc in the original digraph.
2041 /// Returns true when the arc is arc in the original digraph.
2042 static bool origArc(const Arc& e) {
2043 return e._item.firstState();
2046 /// \brief Returns true when the arc binds an in-node and an out-node.
2048 /// Returns true when the arc binds an in-node and an out-node.
2049 static bool bindArc(const Arc& e) {
2050 return e._item.secondState();
2053 /// \brief Gives back the in-node created from the \c node.
2055 /// Gives back the in-node created from the \c node.
2056 static Node inNode(const DigraphNode& n) {
2057 return Node(n, true);
2060 /// \brief Gives back the out-node created from the \c node.
2062 /// Gives back the out-node created from the \c node.
2063 static Node outNode(const DigraphNode& n) {
2064 return Node(n, false);
2067 /// \brief Gives back the arc binds the two part of the node.
2069 /// Gives back the arc binds the two part of the node.
2070 static Arc arc(const DigraphNode& n) {
2074 /// \brief Gives back the arc of the original arc.
2076 /// Gives back the arc of the original arc.
2077 static Arc arc(const DigraphArc& e) {
2081 typedef True NodeNumTag;
2083 int nodeNum() const {
2084 return 2 * countNodes(*_digraph);
2087 typedef True EdgeNumTag;
2088 int arcNum() const {
2089 return countArcs(*_digraph) + countNodes(*_digraph);
2092 typedef True FindEdgeTag;
2093 Arc findArc(const Node& u, const Node& v,
2094 const Arc& prev = INVALID) const {
2097 if (static_cast<const DigraphNode&>(u) ==
2098 static_cast<const DigraphNode&>(v) && prev == INVALID) {
2104 return Arc(::lemon::findArc(*_digraph, u, v, prev));
2112 template <typename _Value>
2114 : public MapTraits<typename Parent::template NodeMap<_Value> > {
2115 typedef typename Parent::template NodeMap<_Value> NodeImpl;
2118 typedef _Value Value;
2120 NodeMapBase(const Adaptor& adaptor)
2121 : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
2122 NodeMapBase(const Adaptor& adaptor, const Value& value)
2123 : _in_map(*adaptor._digraph, value),
2124 _out_map(*adaptor._digraph, value) {}
2126 void set(const Node& key, const Value& val) {
2127 if (Adaptor::inNode(key)) { _in_map.set(key, val); }
2128 else {_out_map.set(key, val); }
2131 typename MapTraits<NodeImpl>::ReturnValue
2132 operator[](const Node& key) {
2133 if (Adaptor::inNode(key)) { return _in_map[key]; }
2134 else { return _out_map[key]; }
2137 typename MapTraits<NodeImpl>::ConstReturnValue
2138 operator[](const Node& key) const {
2139 if (Adaptor::inNode(key)) { return _in_map[key]; }
2140 else { return _out_map[key]; }
2144 NodeImpl _in_map, _out_map;
2147 template <typename _Value>
2149 : public MapTraits<typename Parent::template ArcMap<_Value> > {
2150 typedef typename Parent::template ArcMap<_Value> ArcImpl;
2151 typedef typename Parent::template NodeMap<_Value> NodeImpl;
2154 typedef _Value Value;
2156 ArcMapBase(const Adaptor& adaptor)
2157 : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
2158 ArcMapBase(const Adaptor& adaptor, const Value& value)
2159 : _arc_map(*adaptor._digraph, value),
2160 _node_map(*adaptor._digraph, value) {}
2162 void set(const Arc& key, const Value& val) {
2163 if (Adaptor::origArc(key)) {
2164 _arc_map.set(key._item.first(), val);
2166 _node_map.set(key._item.second(), val);
2170 typename MapTraits<ArcImpl>::ReturnValue
2171 operator[](const Arc& key) {
2172 if (Adaptor::origArc(key)) {
2173 return _arc_map[key._item.first()];
2175 return _node_map[key._item.second()];
2179 typename MapTraits<ArcImpl>::ConstReturnValue
2180 operator[](const Arc& key) const {
2181 if (Adaptor::origArc(key)) {
2182 return _arc_map[key._item.first()];
2184 return _node_map[key._item.second()];
2195 template <typename _Value>
2197 : public SubMapExtender<Adaptor, NodeMapBase<_Value> >
2200 typedef _Value Value;
2201 typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent;
2203 NodeMap(const Adaptor& adaptor)
2204 : Parent(adaptor) {}
2206 NodeMap(const Adaptor& adaptor, const Value& value)
2207 : Parent(adaptor, value) {}
2210 NodeMap& operator=(const NodeMap& cmap) {
2211 return operator=<NodeMap>(cmap);
2214 template <typename CMap>
2215 NodeMap& operator=(const CMap& cmap) {
2216 Parent::operator=(cmap);
2221 template <typename _Value>
2223 : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
2226 typedef _Value Value;
2227 typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
2229 ArcMap(const Adaptor& adaptor)
2230 : Parent(adaptor) {}
2232 ArcMap(const Adaptor& adaptor, const Value& value)
2233 : Parent(adaptor, value) {}
2236 ArcMap& operator=(const ArcMap& cmap) {
2237 return operator=<ArcMap>(cmap);
2240 template <typename CMap>
2241 ArcMap& operator=(const CMap& cmap) {
2242 Parent::operator=(cmap);
2249 SplitDigraphAdaptorBase() : _digraph(0) {}
2253 void setDigraph(Digraph& digraph) {
2254 _digraph = &digraph;
2259 /// \ingroup graph_adaptors
2261 /// \brief Split digraph adaptor class
2263 /// This is an digraph adaptor which splits all node into an in-node
2264 /// and an out-node. Formaly, the adaptor replaces each \f$ u \f$
2265 /// node in the digraph with two node, \f$ u_{in} \f$ node and
2266 /// \f$ u_{out} \f$ node. If there is an \f$ (v, u) \f$ arc in the
2267 /// original digraph the new target of the arc will be \f$ u_{in} \f$ and
2268 /// similarly the source of the original \f$ (u, v) \f$ arc will be
2269 /// \f$ u_{out} \f$. The adaptor will add for each node in the
2270 /// original digraph an additional arc which will connect
2271 /// \f$ (u_{in}, u_{out}) \f$.
2273 /// The aim of this class is to run algorithm with node costs if the
2274 /// algorithm can use directly just arc costs. In this case we should use
2275 /// a \c SplitDigraphAdaptor and set the node cost of the digraph to the
2276 /// bind arc in the adapted digraph.
2278 /// By example a maximum flow algoritm can compute how many arc
2279 /// disjoint paths are in the digraph. But we would like to know how
2280 /// many node disjoint paths are in the digraph. First we have to
2281 /// adapt the digraph with the \c SplitDigraphAdaptor. Then run the flow
2282 /// algorithm on the adapted digraph. The bottleneck of the flow will
2283 /// be the bind arcs which bounds the flow with the count of the
2284 /// node disjoint paths.
2288 /// typedef SplitDigraphAdaptor<SmartDigraph> SDigraph;
2290 /// SDigraph sdigraph(digraph);
2292 /// typedef ConstMap<SDigraph::Arc, int> SCapacity;
2293 /// SCapacity scapacity(1);
2295 /// SDigraph::ArcMap<int> sflow(sdigraph);
2297 /// Preflow<SDigraph, SCapacity>
2298 /// spreflow(sdigraph, scapacity,
2299 /// SDigraph::outNode(source), SDigraph::inNode(target));
2305 /// The result of the mamixum flow on the original digraph
2306 /// shows the next figure:
2308 /// \image html arc_disjoint.png
2309 /// \image latex arc_disjoint.eps "Arc disjoint paths" width=\textwidth
2311 /// And the maximum flow on the adapted digraph:
2313 /// \image html node_disjoint.png
2314 /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth
2316 /// The second solution contains just 3 disjoint paths while the first 4.
2317 /// The full code can be found in the \ref disjoint_paths_demo.cc demo file.
2319 /// This digraph adaptor is fully conform to the
2320 /// \ref concepts::Digraph "Digraph" concept and
2321 /// contains some additional member functions and types. The
2322 /// documentation of some member functions may be found just in the
2323 /// SplitDigraphAdaptorBase class.
2325 /// \sa SplitDigraphAdaptorBase
2326 template <typename _Digraph>
2327 class SplitDigraphAdaptor
2328 : public DigraphAdaptorExtender<SplitDigraphAdaptorBase<_Digraph> > {
2330 typedef _Digraph Digraph;
2331 typedef DigraphAdaptorExtender<SplitDigraphAdaptorBase<Digraph> > Parent;
2333 typedef typename Parent::Node Node;
2334 typedef typename Parent::Arc Arc;
2336 /// \brief Constructor of the adaptor.
2338 /// Constructor of the adaptor.
2339 SplitDigraphAdaptor(Digraph& g) {
2340 Parent::setDigraph(g);
2343 /// \brief NodeMap combined from two original NodeMap
2345 /// This class adapt two of the original digraph NodeMap to
2346 /// get a node map on the adapted digraph.
2347 template <typename InNodeMap, typename OutNodeMap>
2348 class CombinedNodeMap {
2352 typedef typename InNodeMap::Value Value;
2354 /// \brief Constructor
2357 CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
2358 : _in_map(in_map), _out_map(out_map) {}
2360 /// \brief The subscript operator.
2362 /// The subscript operator.
2363 Value& operator[](const Key& key) {
2364 if (Parent::inNode(key)) {
2365 return _in_map[key];
2367 return _out_map[key];
2371 /// \brief The const subscript operator.
2373 /// The const subscript operator.
2374 Value operator[](const Key& key) const {
2375 if (Parent::inNode(key)) {
2376 return _in_map[key];
2378 return _out_map[key];
2382 /// \brief The setter function of the map.
2384 /// The setter function of the map.
2385 void set(const Key& key, const Value& value) {
2386 if (Parent::inNode(key)) {
2387 _in_map.set(key, value);
2389 _out_map.set(key, value);
2396 OutNodeMap& _out_map;
2401 /// \brief Just gives back a combined node map.
2403 /// Just gives back a combined node map.
2404 template <typename InNodeMap, typename OutNodeMap>
2405 static CombinedNodeMap<InNodeMap, OutNodeMap>
2406 combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
2407 return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
2410 template <typename InNodeMap, typename OutNodeMap>
2411 static CombinedNodeMap<const InNodeMap, OutNodeMap>
2412 combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
2413 return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
2416 template <typename InNodeMap, typename OutNodeMap>
2417 static CombinedNodeMap<InNodeMap, const OutNodeMap>
2418 combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
2419 return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
2422 template <typename InNodeMap, typename OutNodeMap>
2423 static CombinedNodeMap<const InNodeMap, const OutNodeMap>
2424 combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
2425 return CombinedNodeMap<const InNodeMap,
2426 const OutNodeMap>(in_map, out_map);
2429 /// \brief ArcMap combined from an original ArcMap and NodeMap
2431 /// This class adapt an original digraph ArcMap and NodeMap to
2432 /// get an arc map on the adapted digraph.
2433 template <typename DigraphArcMap, typename DigraphNodeMap>
2434 class CombinedArcMap {
2438 typedef typename DigraphArcMap::Value Value;
2440 /// \brief Constructor
2443 CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)
2444 : _arc_map(arc_map), _node_map(node_map) {}
2446 /// \brief The subscript operator.
2448 /// The subscript operator.
2449 void set(const Arc& arc, const Value& val) {
2450 if (Parent::origArc(arc)) {
2451 _arc_map.set(arc, val);
2453 _node_map.set(arc, val);
2457 /// \brief The const subscript operator.
2459 /// The const subscript operator.
2460 Value operator[](const Key& arc) const {
2461 if (Parent::origArc(arc)) {
2462 return _arc_map[arc];
2464 return _node_map[arc];
2468 /// \brief The const subscript operator.
2470 /// The const subscript operator.
2471 Value& operator[](const Key& arc) {
2472 if (Parent::origArc(arc)) {
2473 return _arc_map[arc];
2475 return _node_map[arc];
2480 DigraphArcMap& _arc_map;
2481 DigraphNodeMap& _node_map;
2484 /// \brief Just gives back a combined arc map.
2486 /// Just gives back a combined arc map.
2487 template <typename DigraphArcMap, typename DigraphNodeMap>
2488 static CombinedArcMap<DigraphArcMap, DigraphNodeMap>
2489 combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
2490 return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map);
2493 template <typename DigraphArcMap, typename DigraphNodeMap>
2494 static CombinedArcMap<const DigraphArcMap, DigraphNodeMap>
2495 combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
2496 return CombinedArcMap<const DigraphArcMap,
2497 DigraphNodeMap>(arc_map, node_map);
2500 template <typename DigraphArcMap, typename DigraphNodeMap>
2501 static CombinedArcMap<DigraphArcMap, const DigraphNodeMap>
2502 combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) {
2503 return CombinedArcMap<DigraphArcMap,
2504 const DigraphNodeMap>(arc_map, node_map);
2507 template <typename DigraphArcMap, typename DigraphNodeMap>
2508 static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap>
2509 combinedArcMap(const DigraphArcMap& arc_map,
2510 const DigraphNodeMap& node_map) {
2511 return CombinedArcMap<const DigraphArcMap,
2512 const DigraphNodeMap>(arc_map, node_map);
2517 /// \brief Just gives back a split digraph adaptor
2519 /// Just gives back a split digraph adaptor
2520 template<typename Digraph>
2521 SplitDigraphAdaptor<Digraph>
2522 splitDigraphAdaptor(const Digraph& digraph) {
2523 return SplitDigraphAdaptor<Digraph>(digraph);
2529 #endif //LEMON_DIGRAPH_ADAPTOR_H