1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_ADAPTORS_H
20 #define LEMON_ADAPTORS_H
22 /// \ingroup graph_adaptors
24 /// \brief Several graph adaptors
26 /// This file contains several useful adaptors for digraphs and graphs.
28 #include <lemon/core.h>
29 #include <lemon/maps.h>
30 #include <lemon/bits/variant.h>
32 #include <lemon/bits/graph_adaptor_extender.h>
33 #include <lemon/tolerance.h>
39 template<typename _Digraph>
40 class DigraphAdaptorBase {
42 typedef _Digraph Digraph;
43 typedef DigraphAdaptorBase Adaptor;
44 typedef Digraph ParentDigraph;
48 DigraphAdaptorBase() : _digraph(0) { }
49 void setDigraph(Digraph& digraph) { _digraph = &digraph; }
52 DigraphAdaptorBase(Digraph& digraph) : _digraph(&digraph) { }
54 typedef typename Digraph::Node Node;
55 typedef typename Digraph::Arc Arc;
57 void first(Node& i) const { _digraph->first(i); }
58 void first(Arc& i) const { _digraph->first(i); }
59 void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); }
60 void firstOut(Arc& i, const Node& n ) const { _digraph->firstOut(i, n); }
62 void next(Node& i) const { _digraph->next(i); }
63 void next(Arc& i) const { _digraph->next(i); }
64 void nextIn(Arc& i) const { _digraph->nextIn(i); }
65 void nextOut(Arc& i) const { _digraph->nextOut(i); }
67 Node source(const Arc& a) const { return _digraph->source(a); }
68 Node target(const Arc& a) const { return _digraph->target(a); }
70 typedef NodeNumTagIndicator<Digraph> NodeNumTag;
71 int nodeNum() const { return _digraph->nodeNum(); }
73 typedef ArcNumTagIndicator<Digraph> ArcNumTag;
74 int arcNum() const { return _digraph->arcNum(); }
76 typedef FindArcTagIndicator<Digraph> FindArcTag;
77 Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const {
78 return _digraph->findArc(u, v, prev);
81 Node addNode() { return _digraph->addNode(); }
82 Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
84 void erase(const Node& n) { _digraph->erase(n); }
85 void erase(const Arc& a) { _digraph->erase(a); }
87 void clear() { _digraph->clear(); }
89 int id(const Node& n) const { return _digraph->id(n); }
90 int id(const Arc& a) const { return _digraph->id(a); }
92 Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
93 Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); }
95 int maxNodeId() const { return _digraph->maxNodeId(); }
96 int maxArcId() const { return _digraph->maxArcId(); }
98 typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
99 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
101 typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier;
102 ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
104 template <typename _Value>
105 class NodeMap : public Digraph::template NodeMap<_Value> {
108 typedef typename Digraph::template NodeMap<_Value> Parent;
110 explicit NodeMap(const Adaptor& adaptor)
111 : Parent(*adaptor._digraph) {}
113 NodeMap(const Adaptor& adaptor, const _Value& value)
114 : Parent(*adaptor._digraph, value) { }
117 NodeMap& operator=(const NodeMap& cmap) {
118 return operator=<NodeMap>(cmap);
121 template <typename CMap>
122 NodeMap& operator=(const CMap& cmap) {
123 Parent::operator=(cmap);
129 template <typename _Value>
130 class ArcMap : public Digraph::template ArcMap<_Value> {
133 typedef typename Digraph::template ArcMap<_Value> Parent;
135 explicit ArcMap(const Adaptor& adaptor)
136 : Parent(*adaptor._digraph) {}
138 ArcMap(const Adaptor& adaptor, const _Value& value)
139 : Parent(*adaptor._digraph, value) {}
142 ArcMap& operator=(const ArcMap& cmap) {
143 return operator=<ArcMap>(cmap);
146 template <typename CMap>
147 ArcMap& operator=(const CMap& cmap) {
148 Parent::operator=(cmap);
156 template<typename _Graph>
157 class GraphAdaptorBase {
159 typedef _Graph Graph;
160 typedef Graph ParentGraph;
165 GraphAdaptorBase() : _graph(0) {}
167 void setGraph(Graph& graph) { _graph = &graph; }
170 GraphAdaptorBase(Graph& graph) : _graph(&graph) {}
172 typedef typename Graph::Node Node;
173 typedef typename Graph::Arc Arc;
174 typedef typename Graph::Edge Edge;
176 void first(Node& i) const { _graph->first(i); }
177 void first(Arc& i) const { _graph->first(i); }
178 void first(Edge& i) const { _graph->first(i); }
179 void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); }
180 void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); }
181 void firstInc(Edge &i, bool &d, const Node &n) const {
182 _graph->firstInc(i, d, n);
185 void next(Node& i) const { _graph->next(i); }
186 void next(Arc& i) const { _graph->next(i); }
187 void next(Edge& i) const { _graph->next(i); }
188 void nextIn(Arc& i) const { _graph->nextIn(i); }
189 void nextOut(Arc& i) const { _graph->nextOut(i); }
190 void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); }
192 Node u(const Edge& e) const { return _graph->u(e); }
193 Node v(const Edge& e) const { return _graph->v(e); }
195 Node source(const Arc& a) const { return _graph->source(a); }
196 Node target(const Arc& a) const { return _graph->target(a); }
198 typedef NodeNumTagIndicator<Graph> NodeNumTag;
199 int nodeNum() const { return _graph->nodeNum(); }
201 typedef ArcNumTagIndicator<Graph> ArcNumTag;
202 int arcNum() const { return _graph->arcNum(); }
204 typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
205 int edgeNum() const { return _graph->edgeNum(); }
207 typedef FindArcTagIndicator<Graph> FindArcTag;
208 Arc findArc(const Node& u, const Node& v,
209 const Arc& prev = INVALID) const {
210 return _graph->findArc(u, v, prev);
213 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
214 Edge findEdge(const Node& u, const Node& v,
215 const Edge& prev = INVALID) const {
216 return _graph->findEdge(u, v, prev);
219 Node addNode() { return _graph->addNode(); }
220 Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }
222 void erase(const Node& i) { _graph->erase(i); }
223 void erase(const Edge& i) { _graph->erase(i); }
225 void clear() { _graph->clear(); }
227 bool direction(const Arc& a) const { return _graph->direction(a); }
228 Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); }
230 int id(const Node& v) const { return _graph->id(v); }
231 int id(const Arc& a) const { return _graph->id(a); }
232 int id(const Edge& e) const { return _graph->id(e); }
234 Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
235 Arc arcFromId(int ix) const { return _graph->arcFromId(ix); }
236 Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); }
238 int maxNodeId() const { return _graph->maxNodeId(); }
239 int maxArcId() const { return _graph->maxArcId(); }
240 int maxEdgeId() const { return _graph->maxEdgeId(); }
242 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
243 NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
245 typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
246 ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
248 typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
249 EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
251 template <typename _Value>
252 class NodeMap : public Graph::template NodeMap<_Value> {
254 typedef typename Graph::template NodeMap<_Value> Parent;
255 explicit NodeMap(const GraphAdaptorBase<Graph>& adapter)
256 : Parent(*adapter._graph) {}
257 NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
258 : Parent(*adapter._graph, value) {}
261 NodeMap& operator=(const NodeMap& cmap) {
262 return operator=<NodeMap>(cmap);
265 template <typename CMap>
266 NodeMap& operator=(const CMap& cmap) {
267 Parent::operator=(cmap);
273 template <typename _Value>
274 class ArcMap : public Graph::template ArcMap<_Value> {
276 typedef typename Graph::template ArcMap<_Value> Parent;
277 explicit ArcMap(const GraphAdaptorBase<Graph>& adapter)
278 : Parent(*adapter._graph) {}
279 ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
280 : Parent(*adapter._graph, value) {}
283 ArcMap& operator=(const ArcMap& cmap) {
284 return operator=<ArcMap>(cmap);
287 template <typename CMap>
288 ArcMap& operator=(const CMap& cmap) {
289 Parent::operator=(cmap);
294 template <typename _Value>
295 class EdgeMap : public Graph::template EdgeMap<_Value> {
297 typedef typename Graph::template EdgeMap<_Value> Parent;
298 explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)
299 : Parent(*adapter._graph) {}
300 EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
301 : Parent(*adapter._graph, value) {}
304 EdgeMap& operator=(const EdgeMap& cmap) {
305 return operator=<EdgeMap>(cmap);
308 template <typename CMap>
309 EdgeMap& operator=(const CMap& cmap) {
310 Parent::operator=(cmap);
317 template <typename _Digraph>
318 class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> {
320 typedef _Digraph Digraph;
321 typedef DigraphAdaptorBase<_Digraph> Parent;
323 ReverseDigraphBase() : Parent() { }
325 typedef typename Parent::Node Node;
326 typedef typename Parent::Arc Arc;
328 void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }
329 void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); }
331 void nextIn(Arc& a) const { Parent::nextOut(a); }
332 void nextOut(Arc& a) const { Parent::nextIn(a); }
334 Node source(const Arc& a) const { return Parent::target(a); }
335 Node target(const Arc& a) const { return Parent::source(a); }
337 Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
339 typedef FindArcTagIndicator<Digraph> FindArcTag;
340 Arc findArc(const Node& u, const Node& v,
341 const Arc& prev = INVALID) const {
342 return Parent::findArc(v, u, prev);
347 /// \ingroup graph_adaptors
349 /// \brief A digraph adaptor which reverses the orientation of the arcs.
351 /// ReverseDigraph reverses the arcs in the adapted digraph. The
352 /// SubDigraph is conform to the \ref concepts::Digraph
353 /// "Digraph concept".
355 /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
356 /// "Digraph concept". The type can be specified to be const.
357 template<typename _Digraph>
358 class ReverseDigraph :
359 public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > {
361 typedef _Digraph Digraph;
362 typedef DigraphAdaptorExtender<
363 ReverseDigraphBase<_Digraph> > Parent;
368 /// \brief Constructor
370 /// Creates a reverse digraph adaptor for the given digraph
371 explicit ReverseDigraph(Digraph& digraph) {
372 Parent::setDigraph(digraph);
376 /// \brief Just gives back a reverse digraph adaptor
378 /// Just gives back a reverse digraph adaptor
379 template<typename Digraph>
380 ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) {
381 return ReverseDigraph<const Digraph>(digraph);
384 template <typename _Digraph, typename _NodeFilterMap,
385 typename _ArcFilterMap, bool _checked = true>
386 class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {
388 typedef _Digraph Digraph;
389 typedef _NodeFilterMap NodeFilterMap;
390 typedef _ArcFilterMap ArcFilterMap;
392 typedef SubDigraphBase Adaptor;
393 typedef DigraphAdaptorBase<_Digraph> Parent;
395 NodeFilterMap* _node_filter;
396 ArcFilterMap* _arc_filter;
398 : Parent(), _node_filter(0), _arc_filter(0) { }
400 void setNodeFilterMap(NodeFilterMap& node_filter) {
401 _node_filter = &node_filter;
403 void setArcFilterMap(ArcFilterMap& arc_filter) {
404 _arc_filter = &arc_filter;
409 typedef typename Parent::Node Node;
410 typedef typename Parent::Arc Arc;
412 void first(Node& i) const {
414 while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
417 void first(Arc& i) const {
419 while (i != INVALID && (!(*_arc_filter)[i]
420 || !(*_node_filter)[Parent::source(i)]
421 || !(*_node_filter)[Parent::target(i)]))
425 void firstIn(Arc& i, const Node& n) const {
426 Parent::firstIn(i, n);
427 while (i != INVALID && (!(*_arc_filter)[i]
428 || !(*_node_filter)[Parent::source(i)]))
432 void firstOut(Arc& i, const Node& n) const {
433 Parent::firstOut(i, n);
434 while (i != INVALID && (!(*_arc_filter)[i]
435 || !(*_node_filter)[Parent::target(i)]))
439 void next(Node& i) const {
441 while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
444 void next(Arc& i) const {
446 while (i != INVALID && (!(*_arc_filter)[i]
447 || !(*_node_filter)[Parent::source(i)]
448 || !(*_node_filter)[Parent::target(i)]))
452 void nextIn(Arc& i) const {
454 while (i != INVALID && (!(*_arc_filter)[i]
455 || !(*_node_filter)[Parent::source(i)]))
459 void nextOut(Arc& i) const {
461 while (i != INVALID && (!(*_arc_filter)[i]
462 || !(*_node_filter)[Parent::target(i)]))
466 void hide(const Node& n) const { _node_filter->set(n, false); }
467 void hide(const Arc& a) const { _arc_filter->set(a, false); }
469 void unHide(const Node& n) const { _node_filter->set(n, true); }
470 void unHide(const Arc& a) const { _arc_filter->set(a, true); }
472 bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
473 bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }
475 typedef False NodeNumTag;
476 typedef False ArcNumTag;
478 typedef FindArcTagIndicator<Digraph> FindArcTag;
479 Arc findArc(const Node& source, const Node& target,
480 const Arc& prev = INVALID) const {
481 if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
484 Arc arc = Parent::findArc(source, target, prev);
485 while (arc != INVALID && !(*_arc_filter)[arc]) {
486 arc = Parent::findArc(source, target, arc);
491 template <typename _Value>
492 class NodeMap : public SubMapExtender<Adaptor,
493 typename Parent::template NodeMap<_Value> > {
495 typedef _Value Value;
496 typedef SubMapExtender<Adaptor, typename Parent::
497 template NodeMap<Value> > MapParent;
499 NodeMap(const Adaptor& adaptor)
500 : MapParent(adaptor) {}
501 NodeMap(const Adaptor& adaptor, const Value& value)
502 : MapParent(adaptor, value) {}
505 NodeMap& operator=(const NodeMap& cmap) {
506 return operator=<NodeMap>(cmap);
509 template <typename CMap>
510 NodeMap& operator=(const CMap& cmap) {
511 MapParent::operator=(cmap);
516 template <typename _Value>
517 class ArcMap : public SubMapExtender<Adaptor,
518 typename Parent::template ArcMap<_Value> > {
520 typedef _Value Value;
521 typedef SubMapExtender<Adaptor, typename Parent::
522 template ArcMap<Value> > MapParent;
524 ArcMap(const Adaptor& adaptor)
525 : MapParent(adaptor) {}
526 ArcMap(const Adaptor& adaptor, const Value& value)
527 : MapParent(adaptor, value) {}
530 ArcMap& operator=(const ArcMap& cmap) {
531 return operator=<ArcMap>(cmap);
534 template <typename CMap>
535 ArcMap& operator=(const CMap& cmap) {
536 MapParent::operator=(cmap);
543 template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>
544 class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>
545 : public DigraphAdaptorBase<_Digraph> {
547 typedef _Digraph Digraph;
548 typedef _NodeFilterMap NodeFilterMap;
549 typedef _ArcFilterMap ArcFilterMap;
551 typedef SubDigraphBase Adaptor;
552 typedef DigraphAdaptorBase<Digraph> Parent;
554 NodeFilterMap* _node_filter;
555 ArcFilterMap* _arc_filter;
557 : Parent(), _node_filter(0), _arc_filter(0) { }
559 void setNodeFilterMap(NodeFilterMap& node_filter) {
560 _node_filter = &node_filter;
562 void setArcFilterMap(ArcFilterMap& arc_filter) {
563 _arc_filter = &arc_filter;
568 typedef typename Parent::Node Node;
569 typedef typename Parent::Arc Arc;
571 void first(Node& i) const {
573 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
576 void first(Arc& i) const {
578 while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
581 void firstIn(Arc& i, const Node& n) const {
582 Parent::firstIn(i, n);
583 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
586 void firstOut(Arc& i, const Node& n) const {
587 Parent::firstOut(i, n);
588 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
591 void next(Node& i) const {
593 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
595 void next(Arc& i) const {
597 while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
599 void nextIn(Arc& i) const {
601 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
604 void nextOut(Arc& i) const {
606 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
609 void hide(const Node& n) const { _node_filter->set(n, false); }
610 void hide(const Arc& e) const { _arc_filter->set(e, false); }
612 void unHide(const Node& n) const { _node_filter->set(n, true); }
613 void unHide(const Arc& e) const { _arc_filter->set(e, true); }
615 bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
616 bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }
618 typedef False NodeNumTag;
619 typedef False ArcNumTag;
621 typedef FindArcTagIndicator<Digraph> FindArcTag;
622 Arc findArc(const Node& source, const Node& target,
623 const Arc& prev = INVALID) const {
624 if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
627 Arc arc = Parent::findArc(source, target, prev);
628 while (arc != INVALID && !(*_arc_filter)[arc]) {
629 arc = Parent::findArc(source, target, arc);
634 template <typename _Value>
635 class NodeMap : public SubMapExtender<Adaptor,
636 typename Parent::template NodeMap<_Value> > {
638 typedef _Value Value;
639 typedef SubMapExtender<Adaptor, typename Parent::
640 template NodeMap<Value> > MapParent;
642 NodeMap(const Adaptor& adaptor)
643 : MapParent(adaptor) {}
644 NodeMap(const Adaptor& adaptor, const Value& value)
645 : MapParent(adaptor, value) {}
648 NodeMap& operator=(const NodeMap& cmap) {
649 return operator=<NodeMap>(cmap);
652 template <typename CMap>
653 NodeMap& operator=(const CMap& cmap) {
654 MapParent::operator=(cmap);
659 template <typename _Value>
660 class ArcMap : public SubMapExtender<Adaptor,
661 typename Parent::template ArcMap<_Value> > {
663 typedef _Value Value;
664 typedef SubMapExtender<Adaptor, typename Parent::
665 template ArcMap<Value> > MapParent;
667 ArcMap(const Adaptor& adaptor)
668 : MapParent(adaptor) {}
669 ArcMap(const Adaptor& adaptor, const Value& value)
670 : MapParent(adaptor, value) {}
673 ArcMap& operator=(const ArcMap& cmap) {
674 return operator=<ArcMap>(cmap);
677 template <typename CMap>
678 ArcMap& operator=(const CMap& cmap) {
679 MapParent::operator=(cmap);
686 /// \ingroup graph_adaptors
688 /// \brief An adaptor for hiding nodes and arcs in a digraph
690 /// SubDigraph hides nodes and arcs in a digraph. A bool node map
691 /// and a bool arc map must be specified, which define the filters
692 /// for nodes and arcs. Just the nodes and arcs with true value are
693 /// shown in the subdigraph. The SubDigraph is conform to the \ref
694 /// concepts::Digraph "Digraph concept". If the \c _checked parameter
695 /// is true, then the arcs incident to filtered nodes are also
698 /// \tparam _Digraph It must be conform to the \ref
699 /// concepts::Digraph "Digraph concept". The type can be specified
701 /// \tparam _NodeFilterMap A bool valued node map of the the adapted digraph.
702 /// \tparam _ArcFilterMap A bool valued arc map of the the adapted digraph.
703 /// \tparam _checked If the parameter is false then the arc filtering
704 /// is not checked with respect to node filter. Otherwise, each arc
705 /// is automatically filtered, which is incident to a filtered node.
709 template<typename _Digraph,
710 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
711 typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,
712 bool _checked = true>
714 : public DigraphAdaptorExtender<
715 SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > {
717 typedef _Digraph Digraph;
718 typedef _NodeFilterMap NodeFilterMap;
719 typedef _ArcFilterMap ArcFilterMap;
721 typedef DigraphAdaptorExtender<
722 SubDigraphBase<Digraph, NodeFilterMap, ArcFilterMap, _checked> >
725 typedef typename Parent::Node Node;
726 typedef typename Parent::Arc Arc;
732 /// \brief Constructor
734 /// Creates a subdigraph for the given digraph with
735 /// given node and arc map filters.
736 SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,
737 ArcFilterMap& arc_filter) {
739 setNodeFilterMap(node_filter);
740 setArcFilterMap(arc_filter);
743 /// \brief Hides the node of the graph
745 /// This function hides \c n in the digraph, i.e. the iteration
746 /// jumps over it. This is done by simply setting the value of \c n
747 /// to be false in the corresponding node-map.
748 void hide(const Node& n) const { Parent::hide(n); }
750 /// \brief Hides the arc of the graph
752 /// This function hides \c a in the digraph, i.e. the iteration
753 /// jumps over it. This is done by simply setting the value of \c a
754 /// to be false in the corresponding arc-map.
755 void hide(const Arc& a) const { Parent::hide(a); }
757 /// \brief Unhides the node of the graph
759 /// The value of \c n is set to be true in the node-map which stores
760 /// hide information. If \c n was hidden previuosly, then it is shown
762 void unHide(const Node& n) const { Parent::unHide(n); }
764 /// \brief Unhides the arc of the graph
766 /// The value of \c a is set to be true in the arc-map which stores
767 /// hide information. If \c a was hidden previuosly, then it is shown
769 void unHide(const Arc& a) const { Parent::unHide(a); }
771 /// \brief Returns true if \c n is hidden.
773 /// Returns true if \c n is hidden.
775 bool hidden(const Node& n) const { return Parent::hidden(n); }
777 /// \brief Returns true if \c a is hidden.
779 /// Returns true if \c a is hidden.
781 bool hidden(const Arc& a) const { return Parent::hidden(a); }
785 /// \brief Just gives back a subdigraph
787 /// Just gives back a subdigraph
788 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
789 SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
790 subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) {
791 return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
795 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
796 SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
797 subDigraph(const Digraph& digraph,
798 const NodeFilterMap& nfm, ArcFilterMap& afm) {
799 return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
803 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
804 SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
805 subDigraph(const Digraph& digraph,
806 NodeFilterMap& nfm, const ArcFilterMap& afm) {
807 return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
811 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
812 SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap>
813 subDigraph(const Digraph& digraph,
814 const NodeFilterMap& nfm, const ArcFilterMap& afm) {
815 return SubDigraph<const Digraph, const NodeFilterMap,
816 const ArcFilterMap>(digraph, nfm, afm);
820 template <typename _Graph, typename NodeFilterMap,
821 typename EdgeFilterMap, bool _checked = true>
822 class SubGraphBase : public GraphAdaptorBase<_Graph> {
824 typedef _Graph Graph;
825 typedef SubGraphBase Adaptor;
826 typedef GraphAdaptorBase<_Graph> Parent;
829 NodeFilterMap* _node_filter_map;
830 EdgeFilterMap* _edge_filter_map;
833 : Parent(), _node_filter_map(0), _edge_filter_map(0) { }
835 void setNodeFilterMap(NodeFilterMap& node_filter_map) {
836 _node_filter_map=&node_filter_map;
838 void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
839 _edge_filter_map=&edge_filter_map;
844 typedef typename Parent::Node Node;
845 typedef typename Parent::Arc Arc;
846 typedef typename Parent::Edge Edge;
848 void first(Node& i) const {
850 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
853 void first(Arc& i) const {
855 while (i!=INVALID && (!(*_edge_filter_map)[i]
856 || !(*_node_filter_map)[Parent::source(i)]
857 || !(*_node_filter_map)[Parent::target(i)]))
861 void first(Edge& i) const {
863 while (i!=INVALID && (!(*_edge_filter_map)[i]
864 || !(*_node_filter_map)[Parent::u(i)]
865 || !(*_node_filter_map)[Parent::v(i)]))
869 void firstIn(Arc& i, const Node& n) const {
870 Parent::firstIn(i, n);
871 while (i!=INVALID && (!(*_edge_filter_map)[i]
872 || !(*_node_filter_map)[Parent::source(i)]))
876 void firstOut(Arc& i, const Node& n) const {
877 Parent::firstOut(i, n);
878 while (i!=INVALID && (!(*_edge_filter_map)[i]
879 || !(*_node_filter_map)[Parent::target(i)]))
883 void firstInc(Edge& i, bool& d, const Node& n) const {
884 Parent::firstInc(i, d, n);
885 while (i!=INVALID && (!(*_edge_filter_map)[i]
886 || !(*_node_filter_map)[Parent::u(i)]
887 || !(*_node_filter_map)[Parent::v(i)]))
888 Parent::nextInc(i, d);
891 void next(Node& i) const {
893 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
896 void next(Arc& i) const {
898 while (i!=INVALID && (!(*_edge_filter_map)[i]
899 || !(*_node_filter_map)[Parent::source(i)]
900 || !(*_node_filter_map)[Parent::target(i)]))
904 void next(Edge& i) const {
906 while (i!=INVALID && (!(*_edge_filter_map)[i]
907 || !(*_node_filter_map)[Parent::u(i)]
908 || !(*_node_filter_map)[Parent::v(i)]))
912 void nextIn(Arc& i) const {
914 while (i!=INVALID && (!(*_edge_filter_map)[i]
915 || !(*_node_filter_map)[Parent::source(i)]))
919 void nextOut(Arc& i) const {
921 while (i!=INVALID && (!(*_edge_filter_map)[i]
922 || !(*_node_filter_map)[Parent::target(i)]))
926 void nextInc(Edge& i, bool& d) const {
927 Parent::nextInc(i, d);
928 while (i!=INVALID && (!(*_edge_filter_map)[i]
929 || !(*_node_filter_map)[Parent::u(i)]
930 || !(*_node_filter_map)[Parent::v(i)]))
931 Parent::nextInc(i, d);
934 void hide(const Node& n) const { _node_filter_map->set(n, false); }
935 void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
937 void unHide(const Node& n) const { _node_filter_map->set(n, true); }
938 void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
940 bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
941 bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
943 typedef False NodeNumTag;
944 typedef False ArcNumTag;
945 typedef False EdgeNumTag;
947 typedef FindArcTagIndicator<Graph> FindArcTag;
948 Arc findArc(const Node& u, const Node& v,
949 const Arc& prev = INVALID) const {
950 if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
953 Arc arc = Parent::findArc(u, v, prev);
954 while (arc != INVALID && !(*_edge_filter_map)[arc]) {
955 arc = Parent::findArc(u, v, arc);
960 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
961 Edge findEdge(const Node& u, const Node& v,
962 const Edge& prev = INVALID) const {
963 if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
966 Edge edge = Parent::findEdge(u, v, prev);
967 while (edge != INVALID && !(*_edge_filter_map)[edge]) {
968 edge = Parent::findEdge(u, v, edge);
973 template <typename _Value>
974 class NodeMap : public SubMapExtender<Adaptor,
975 typename Parent::template NodeMap<_Value> > {
977 typedef _Value Value;
978 typedef SubMapExtender<Adaptor, typename Parent::
979 template NodeMap<Value> > MapParent;
981 NodeMap(const Adaptor& adaptor)
982 : MapParent(adaptor) {}
983 NodeMap(const Adaptor& adaptor, const Value& value)
984 : MapParent(adaptor, value) {}
987 NodeMap& operator=(const NodeMap& cmap) {
988 return operator=<NodeMap>(cmap);
991 template <typename CMap>
992 NodeMap& operator=(const CMap& cmap) {
993 MapParent::operator=(cmap);
998 template <typename _Value>
999 class ArcMap : public SubMapExtender<Adaptor,
1000 typename Parent::template ArcMap<_Value> > {
1002 typedef _Value Value;
1003 typedef SubMapExtender<Adaptor, typename Parent::
1004 template ArcMap<Value> > MapParent;
1006 ArcMap(const Adaptor& adaptor)
1007 : MapParent(adaptor) {}
1008 ArcMap(const Adaptor& adaptor, const Value& value)
1009 : MapParent(adaptor, value) {}
1012 ArcMap& operator=(const ArcMap& cmap) {
1013 return operator=<ArcMap>(cmap);
1016 template <typename CMap>
1017 ArcMap& operator=(const CMap& cmap) {
1018 MapParent::operator=(cmap);
1023 template <typename _Value>
1024 class EdgeMap : public SubMapExtender<Adaptor,
1025 typename Parent::template EdgeMap<_Value> > {
1027 typedef _Value Value;
1028 typedef SubMapExtender<Adaptor, typename Parent::
1029 template EdgeMap<Value> > MapParent;
1031 EdgeMap(const Adaptor& adaptor)
1032 : MapParent(adaptor) {}
1034 EdgeMap(const Adaptor& adaptor, const Value& value)
1035 : MapParent(adaptor, value) {}
1038 EdgeMap& operator=(const EdgeMap& cmap) {
1039 return operator=<EdgeMap>(cmap);
1042 template <typename CMap>
1043 EdgeMap& operator=(const CMap& cmap) {
1044 MapParent::operator=(cmap);
1051 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
1052 class SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
1053 : public GraphAdaptorBase<_Graph> {
1055 typedef _Graph Graph;
1056 typedef SubGraphBase Adaptor;
1057 typedef GraphAdaptorBase<_Graph> Parent;
1059 NodeFilterMap* _node_filter_map;
1060 EdgeFilterMap* _edge_filter_map;
1061 SubGraphBase() : Parent(),
1062 _node_filter_map(0), _edge_filter_map(0) { }
1064 void setNodeFilterMap(NodeFilterMap& node_filter_map) {
1065 _node_filter_map=&node_filter_map;
1067 void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
1068 _edge_filter_map=&edge_filter_map;
1073 typedef typename Parent::Node Node;
1074 typedef typename Parent::Arc Arc;
1075 typedef typename Parent::Edge Edge;
1077 void first(Node& i) const {
1079 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
1082 void first(Arc& i) const {
1084 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1087 void first(Edge& i) const {
1089 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1092 void firstIn(Arc& i, const Node& n) const {
1093 Parent::firstIn(i, n);
1094 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
1097 void firstOut(Arc& i, const Node& n) const {
1098 Parent::firstOut(i, n);
1099 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
1102 void firstInc(Edge& i, bool& d, const Node& n) const {
1103 Parent::firstInc(i, d, n);
1104 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
1107 void next(Node& i) const {
1109 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
1111 void next(Arc& i) const {
1113 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1115 void next(Edge& i) const {
1117 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1119 void nextIn(Arc& i) const {
1121 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
1124 void nextOut(Arc& i) const {
1126 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
1128 void nextInc(Edge& i, bool& d) const {
1129 Parent::nextInc(i, d);
1130 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
1133 void hide(const Node& n) const { _node_filter_map->set(n, false); }
1134 void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
1136 void unHide(const Node& n) const { _node_filter_map->set(n, true); }
1137 void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
1139 bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
1140 bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
1142 typedef False NodeNumTag;
1143 typedef False ArcNumTag;
1144 typedef False EdgeNumTag;
1146 typedef FindArcTagIndicator<Graph> FindArcTag;
1147 Arc findArc(const Node& u, const Node& v,
1148 const Arc& prev = INVALID) const {
1149 Arc arc = Parent::findArc(u, v, prev);
1150 while (arc != INVALID && !(*_edge_filter_map)[arc]) {
1151 arc = Parent::findArc(u, v, arc);
1156 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1157 Edge findEdge(const Node& u, const Node& v,
1158 const Edge& prev = INVALID) const {
1159 Edge edge = Parent::findEdge(u, v, prev);
1160 while (edge != INVALID && !(*_edge_filter_map)[edge]) {
1161 edge = Parent::findEdge(u, v, edge);
1166 template <typename _Value>
1167 class NodeMap : public SubMapExtender<Adaptor,
1168 typename Parent::template NodeMap<_Value> > {
1170 typedef _Value Value;
1171 typedef SubMapExtender<Adaptor, typename Parent::
1172 template NodeMap<Value> > MapParent;
1174 NodeMap(const Adaptor& adaptor)
1175 : MapParent(adaptor) {}
1176 NodeMap(const Adaptor& adaptor, const Value& value)
1177 : MapParent(adaptor, value) {}
1180 NodeMap& operator=(const NodeMap& cmap) {
1181 return operator=<NodeMap>(cmap);
1184 template <typename CMap>
1185 NodeMap& operator=(const CMap& cmap) {
1186 MapParent::operator=(cmap);
1191 template <typename _Value>
1192 class ArcMap : public SubMapExtender<Adaptor,
1193 typename Parent::template ArcMap<_Value> > {
1195 typedef _Value Value;
1196 typedef SubMapExtender<Adaptor, typename Parent::
1197 template ArcMap<Value> > MapParent;
1199 ArcMap(const Adaptor& adaptor)
1200 : MapParent(adaptor) {}
1201 ArcMap(const Adaptor& adaptor, const Value& value)
1202 : MapParent(adaptor, value) {}
1205 ArcMap& operator=(const ArcMap& cmap) {
1206 return operator=<ArcMap>(cmap);
1209 template <typename CMap>
1210 ArcMap& operator=(const CMap& cmap) {
1211 MapParent::operator=(cmap);
1216 template <typename _Value>
1217 class EdgeMap : public SubMapExtender<Adaptor,
1218 typename Parent::template EdgeMap<_Value> > {
1220 typedef _Value Value;
1221 typedef SubMapExtender<Adaptor, typename Parent::
1222 template EdgeMap<Value> > MapParent;
1224 EdgeMap(const Adaptor& adaptor)
1225 : MapParent(adaptor) {}
1227 EdgeMap(const Adaptor& adaptor, const _Value& value)
1228 : MapParent(adaptor, value) {}
1231 EdgeMap& operator=(const EdgeMap& cmap) {
1232 return operator=<EdgeMap>(cmap);
1235 template <typename CMap>
1236 EdgeMap& operator=(const CMap& cmap) {
1237 MapParent::operator=(cmap);
1244 /// \ingroup graph_adaptors
1246 /// \brief A graph adaptor for hiding nodes and edges in an
1247 /// undirected graph.
1249 /// SubGraph hides nodes and edges in a graph. A bool node map and a
1250 /// bool edge map must be specified, which define the filters for
1251 /// nodes and edges. Just the nodes and edges with true value are
1252 /// shown in the subgraph. The SubGraph is conform to the \ref
1253 /// concepts::Graph "Graph concept". If the \c _checked parameter is
1254 /// true, then the edges incident to filtered nodes are also
1257 /// \tparam _Graph It must be conform to the \ref
1258 /// concepts::Graph "Graph concept". The type can be specified
1260 /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
1261 /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted graph.
1262 /// \tparam _checked If the parameter is false then the edge filtering
1263 /// is not checked with respect to node filter. Otherwise, each edge
1264 /// is automatically filtered, which is incident to a filtered node.
1266 /// \see FilterNodes
1267 /// \see FilterEdges
1268 template<typename _Graph, typename NodeFilterMap,
1269 typename EdgeFilterMap, bool _checked = true>
1271 : public GraphAdaptorExtender<
1272 SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, _checked> > {
1274 typedef _Graph Graph;
1275 typedef GraphAdaptorExtender<
1276 SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
1278 typedef typename Parent::Node Node;
1279 typedef typename Parent::Edge Edge;
1285 /// \brief Constructor
1287 /// Creates a subgraph for the given graph with given node and
1288 /// edge map filters.
1289 SubGraph(Graph& _graph, NodeFilterMap& node_filter_map,
1290 EdgeFilterMap& edge_filter_map) {
1292 setNodeFilterMap(node_filter_map);
1293 setEdgeFilterMap(edge_filter_map);
1296 /// \brief Hides the node of the graph
1298 /// This function hides \c n in the graph, i.e. the iteration
1299 /// jumps over it. This is done by simply setting the value of \c n
1300 /// to be false in the corresponding node-map.
1301 void hide(const Node& n) const { Parent::hide(n); }
1303 /// \brief Hides the edge of the graph
1305 /// This function hides \c e in the graph, i.e. the iteration
1306 /// jumps over it. This is done by simply setting the value of \c e
1307 /// to be false in the corresponding edge-map.
1308 void hide(const Edge& e) const { Parent::hide(e); }
1310 /// \brief Unhides the node of the graph
1312 /// The value of \c n is set to be true in the node-map which stores
1313 /// hide information. If \c n was hidden previuosly, then it is shown
1315 void unHide(const Node& n) const { Parent::unHide(n); }
1317 /// \brief Unhides the edge of the graph
1319 /// The value of \c e is set to be true in the edge-map which stores
1320 /// hide information. If \c e was hidden previuosly, then it is shown
1322 void unHide(const Edge& e) const { Parent::unHide(e); }
1324 /// \brief Returns true if \c n is hidden.
1326 /// Returns true if \c n is hidden.
1328 bool hidden(const Node& n) const { return Parent::hidden(n); }
1330 /// \brief Returns true if \c e is hidden.
1332 /// Returns true if \c e is hidden.
1334 bool hidden(const Edge& e) const { return Parent::hidden(e); }
1337 /// \brief Just gives back a subgraph
1339 /// Just gives back a subgraph
1340 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1341 SubGraph<const Graph, NodeFilterMap, ArcFilterMap>
1342 subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) {
1343 return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm);
1346 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1347 SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
1348 subGraph(const Graph& graph,
1349 const NodeFilterMap& nfm, ArcFilterMap& efm) {
1350 return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
1354 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1355 SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
1356 subGraph(const Graph& graph,
1357 NodeFilterMap& nfm, const ArcFilterMap& efm) {
1358 return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
1362 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1363 SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
1364 subGraph(const Graph& graph,
1365 const NodeFilterMap& nfm, const ArcFilterMap& efm) {
1366 return SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
1370 /// \ingroup graph_adaptors
1372 /// \brief An adaptor for hiding nodes from a digraph or a graph.
1374 /// FilterNodes adaptor hides nodes in a graph or a digraph. A bool
1375 /// node map must be specified, which defines the filters for
1376 /// nodes. Just the unfiltered nodes and the arcs or edges incident
1377 /// to unfiltered nodes are shown in the subdigraph or subgraph. The
1378 /// FilterNodes is conform to the \ref concepts::Digraph
1379 /// "Digraph concept" or \ref concepts::Graph "Graph concept" depending
1380 /// on the \c _Digraph template parameter. If the \c _checked
1381 /// parameter is true, then the arc or edges incident to filtered nodes
1382 /// are also filtered out.
1384 /// \tparam _Digraph It must be conform to the \ref
1385 /// concepts::Digraph "Digraph concept" or \ref concepts::Graph
1386 /// "Graph concept". The type can be specified to be const.
1387 /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
1388 /// \tparam _checked If the parameter is false then the arc or edge
1389 /// filtering is not checked with respect to node filter. In this
1390 /// case just isolated nodes can be filtered out from the
1393 template<typename _Digraph,
1394 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
1395 bool _checked = true>
1397 template<typename _Digraph,
1398 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
1399 bool _checked = true,
1400 typename Enable = void>
1403 : public SubDigraph<_Digraph, _NodeFilterMap,
1404 ConstMap<typename _Digraph::Arc, bool>, _checked> {
1407 typedef _Digraph Digraph;
1408 typedef _NodeFilterMap NodeFilterMap;
1410 typedef SubDigraph<Digraph, NodeFilterMap,
1411 ConstMap<typename Digraph::Arc, bool>, _checked>
1414 typedef typename Parent::Node Node;
1417 ConstMap<typename Digraph::Arc, bool> const_true_map;
1419 FilterNodes() : const_true_map(true) {
1420 Parent::setArcFilterMap(const_true_map);
1425 /// \brief Constructor
1427 /// Creates an adaptor for the given digraph or graph with
1428 /// given node filter map.
1429 FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) :
1430 Parent(), const_true_map(true) {
1431 Parent::setDigraph(_digraph);
1432 Parent::setNodeFilterMap(node_filter);
1433 Parent::setArcFilterMap(const_true_map);
1436 /// \brief Hides the node of the graph
1438 /// This function hides \c n in the digraph or graph, i.e. the iteration
1439 /// jumps over it. This is done by simply setting the value of \c n
1440 /// to be false in the corresponding node map.
1441 void hide(const Node& n) const { Parent::hide(n); }
1443 /// \brief Unhides the node of the graph
1445 /// The value of \c n is set to be true in the node-map which stores
1446 /// hide information. If \c n was hidden previuosly, then it is shown
1448 void unHide(const Node& n) const { Parent::unHide(n); }
1450 /// \brief Returns true if \c n is hidden.
1452 /// Returns true if \c n is hidden.
1454 bool hidden(const Node& n) const { return Parent::hidden(n); }
1458 template<typename _Graph, typename _NodeFilterMap, bool _checked>
1459 class FilterNodes<_Graph, _NodeFilterMap, _checked,
1460 typename enable_if<UndirectedTagIndicator<_Graph> >::type>
1461 : public SubGraph<_Graph, _NodeFilterMap,
1462 ConstMap<typename _Graph::Edge, bool>, _checked> {
1464 typedef _Graph Graph;
1465 typedef _NodeFilterMap NodeFilterMap;
1466 typedef SubGraph<Graph, NodeFilterMap,
1467 ConstMap<typename Graph::Edge, bool> > Parent;
1469 typedef typename Parent::Node Node;
1471 ConstMap<typename Graph::Edge, bool> const_true_map;
1473 FilterNodes() : const_true_map(true) {
1474 Parent::setEdgeFilterMap(const_true_map);
1479 FilterNodes(Graph& _graph, NodeFilterMap& node_filter_map) :
1480 Parent(), const_true_map(true) {
1481 Parent::setGraph(_graph);
1482 Parent::setNodeFilterMap(node_filter_map);
1483 Parent::setEdgeFilterMap(const_true_map);
1486 void hide(const Node& n) const { Parent::hide(n); }
1487 void unHide(const Node& n) const { Parent::unHide(n); }
1488 bool hidden(const Node& n) const { return Parent::hidden(n); }
1493 /// \brief Just gives back a FilterNodes adaptor
1495 /// Just gives back a FilterNodes adaptor
1496 template<typename Digraph, typename NodeFilterMap>
1497 FilterNodes<const Digraph, NodeFilterMap>
1498 filterNodes(const Digraph& digraph, NodeFilterMap& nfm) {
1499 return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm);
1502 template<typename Digraph, typename NodeFilterMap>
1503 FilterNodes<const Digraph, const NodeFilterMap>
1504 filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) {
1505 return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm);
1508 /// \ingroup graph_adaptors
1510 /// \brief An adaptor for hiding arcs from a digraph.
1512 /// FilterArcs adaptor hides arcs in a digraph. A bool arc map must
1513 /// be specified, which defines the filters for arcs. Just the
1514 /// unfiltered arcs are shown in the subdigraph. The FilterArcs is
1515 /// conform to the \ref concepts::Digraph "Digraph concept".
1517 /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
1518 /// "Digraph concept". The type can be specified to be const.
1519 /// \tparam _ArcFilterMap A bool valued arc map of the the adapted
1521 template<typename _Digraph, typename _ArcFilterMap>
1523 public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>,
1524 _ArcFilterMap, false> {
1526 typedef _Digraph Digraph;
1527 typedef _ArcFilterMap ArcFilterMap;
1529 typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>,
1530 ArcFilterMap, false> Parent;
1532 typedef typename Parent::Arc Arc;
1535 ConstMap<typename Digraph::Node, bool> const_true_map;
1537 FilterArcs() : const_true_map(true) {
1538 Parent::setNodeFilterMap(const_true_map);
1543 /// \brief Constructor
1545 /// Creates a FilterArcs adaptor for the given graph with
1546 /// given arc map filter.
1547 FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
1548 : Parent(), const_true_map(true) {
1549 Parent::setDigraph(digraph);
1550 Parent::setNodeFilterMap(const_true_map);
1551 Parent::setArcFilterMap(arc_filter);
1554 /// \brief Hides the arc of the graph
1556 /// This function hides \c a in the graph, i.e. the iteration
1557 /// jumps over it. This is done by simply setting the value of \c a
1558 /// to be false in the corresponding arc map.
1559 void hide(const Arc& a) const { Parent::hide(a); }
1561 /// \brief Unhides the arc of the graph
1563 /// The value of \c a is set to be true in the arc-map which stores
1564 /// hide information. If \c a was hidden previuosly, then it is shown
1566 void unHide(const Arc& a) const { Parent::unHide(a); }
1568 /// \brief Returns true if \c a is hidden.
1570 /// Returns true if \c a is hidden.
1572 bool hidden(const Arc& a) const { return Parent::hidden(a); }
1576 /// \brief Just gives back an FilterArcs adaptor
1578 /// Just gives back an FilterArcs adaptor
1579 template<typename Digraph, typename ArcFilterMap>
1580 FilterArcs<const Digraph, ArcFilterMap>
1581 filterArcs(const Digraph& digraph, ArcFilterMap& afm) {
1582 return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm);
1585 template<typename Digraph, typename ArcFilterMap>
1586 FilterArcs<const Digraph, const ArcFilterMap>
1587 filterArcs(const Digraph& digraph, const ArcFilterMap& afm) {
1588 return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm);
1591 /// \ingroup graph_adaptors
1593 /// \brief An adaptor for hiding edges from a graph.
1595 /// FilterEdges adaptor hides edges in a digraph. A bool edge map must
1596 /// be specified, which defines the filters for edges. Just the
1597 /// unfiltered edges are shown in the subdigraph. The FilterEdges is
1598 /// conform to the \ref concepts::Graph "Graph concept".
1600 /// \tparam _Graph It must be conform to the \ref concepts::Graph
1601 /// "Graph concept". The type can be specified to be const.
1602 /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted
1604 template<typename _Graph, typename _EdgeFilterMap>
1606 public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>,
1607 _EdgeFilterMap, false> {
1609 typedef _Graph Graph;
1610 typedef _EdgeFilterMap EdgeFilterMap;
1611 typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>,
1612 EdgeFilterMap, false> Parent;
1613 typedef typename Parent::Edge Edge;
1615 ConstMap<typename Graph::Node, bool> const_true_map;
1617 FilterEdges() : const_true_map(true) {
1618 Parent::setNodeFilterMap(const_true_map);
1623 /// \brief Constructor
1625 /// Creates a FilterEdges adaptor for the given graph with
1626 /// given edge map filters.
1627 FilterEdges(Graph& _graph, EdgeFilterMap& edge_filter_map) :
1628 Parent(), const_true_map(true) {
1629 Parent::setGraph(_graph);
1630 Parent::setNodeFilterMap(const_true_map);
1631 Parent::setEdgeFilterMap(edge_filter_map);
1634 /// \brief Hides the edge of the graph
1636 /// This function hides \c e in the graph, i.e. the iteration
1637 /// jumps over it. This is done by simply setting the value of \c e
1638 /// to be false in the corresponding edge-map.
1639 void hide(const Edge& e) const { Parent::hide(e); }
1641 /// \brief Unhides the edge of the graph
1643 /// The value of \c e is set to be true in the edge-map which stores
1644 /// hide information. If \c e was hidden previuosly, then it is shown
1646 void unHide(const Edge& e) const { Parent::unHide(e); }
1648 /// \brief Returns true if \c e is hidden.
1650 /// Returns true if \c e is hidden.
1652 bool hidden(const Edge& e) const { return Parent::hidden(e); }
1656 /// \brief Just gives back a FilterEdges adaptor
1658 /// Just gives back a FilterEdges adaptor
1659 template<typename Graph, typename EdgeFilterMap>
1660 FilterEdges<const Graph, EdgeFilterMap>
1661 filterEdges(const Graph& graph, EdgeFilterMap& efm) {
1662 return FilterEdges<const Graph, EdgeFilterMap>(graph, efm);
1665 template<typename Graph, typename EdgeFilterMap>
1666 FilterEdges<const Graph, const EdgeFilterMap>
1667 filterEdges(const Graph& graph, const EdgeFilterMap& efm) {
1668 return FilterEdges<const Graph, const EdgeFilterMap>(graph, efm);
1671 template <typename _Digraph>
1672 class UndirectorBase {
1674 typedef _Digraph Digraph;
1675 typedef UndirectorBase Adaptor;
1677 typedef True UndirectedTag;
1679 typedef typename Digraph::Arc Edge;
1680 typedef typename Digraph::Node Node;
1682 class Arc : public Edge {
1683 friend class UndirectorBase;
1687 Arc(const Edge& edge, bool forward) :
1688 Edge(edge), _forward(forward) {}
1693 Arc(Invalid) : Edge(INVALID), _forward(true) {}
1695 bool operator==(const Arc &other) const {
1696 return _forward == other._forward &&
1697 static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
1699 bool operator!=(const Arc &other) const {
1700 return _forward != other._forward ||
1701 static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
1703 bool operator<(const Arc &other) const {
1704 return _forward < other._forward ||
1705 (_forward == other._forward &&
1706 static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
1712 void first(Node& n) const {
1716 void next(Node& n) const {
1720 void first(Arc& a) const {
1725 void next(Arc& a) const {
1734 void first(Edge& e) const {
1738 void next(Edge& e) const {
1742 void firstOut(Arc& a, const Node& n) const {
1743 _digraph->firstIn(a, n);
1744 if( static_cast<const Edge&>(a) != INVALID ) {
1747 _digraph->firstOut(a, n);
1751 void nextOut(Arc &a) const {
1753 Node n = _digraph->target(a);
1754 _digraph->nextIn(a);
1755 if (static_cast<const Edge&>(a) == INVALID ) {
1756 _digraph->firstOut(a, n);
1761 _digraph->nextOut(a);
1765 void firstIn(Arc &a, const Node &n) const {
1766 _digraph->firstOut(a, n);
1767 if (static_cast<const Edge&>(a) != INVALID ) {
1770 _digraph->firstIn(a, n);
1774 void nextIn(Arc &a) const {
1776 Node n = _digraph->source(a);
1777 _digraph->nextOut(a);
1778 if( static_cast<const Edge&>(a) == INVALID ) {
1779 _digraph->firstIn(a, n);
1784 _digraph->nextIn(a);
1788 void firstInc(Edge &e, bool &d, const Node &n) const {
1790 _digraph->firstOut(e, n);
1791 if (e != INVALID) return;
1793 _digraph->firstIn(e, n);
1796 void nextInc(Edge &e, bool &d) const {
1798 Node s = _digraph->source(e);
1799 _digraph->nextOut(e);
1800 if (e != INVALID) return;
1802 _digraph->firstIn(e, s);
1804 _digraph->nextIn(e);
1808 Node u(const Edge& e) const {
1809 return _digraph->source(e);
1812 Node v(const Edge& e) const {
1813 return _digraph->target(e);
1816 Node source(const Arc &a) const {
1817 return a._forward ? _digraph->source(a) : _digraph->target(a);
1820 Node target(const Arc &a) const {
1821 return a._forward ? _digraph->target(a) : _digraph->source(a);
1824 static Arc direct(const Edge &e, bool d) {
1827 Arc direct(const Edge &e, const Node& n) const {
1828 return Arc(e, _digraph->source(e) == n);
1831 static bool direction(const Arc &a) { return a._forward; }
1833 Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
1834 Arc arcFromId(int ix) const {
1835 return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1));
1837 Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); }
1839 int id(const Node &n) const { return _digraph->id(n); }
1840 int id(const Arc &a) const {
1841 return (_digraph->id(a) << 1) | (a._forward ? 1 : 0);
1843 int id(const Edge &e) const { return _digraph->id(e); }
1845 int maxNodeId() const { return _digraph->maxNodeId(); }
1846 int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; }
1847 int maxEdgeId() const { return _digraph->maxArcId(); }
1849 Node addNode() { return _digraph->addNode(); }
1850 Edge addEdge(const Node& u, const Node& v) {
1851 return _digraph->addArc(u, v);
1854 void erase(const Node& i) { _digraph->erase(i); }
1855 void erase(const Edge& i) { _digraph->erase(i); }
1857 void clear() { _digraph->clear(); }
1859 typedef NodeNumTagIndicator<Digraph> NodeNumTag;
1860 int nodeNum() const { return 2 * _digraph->arcNum(); }
1862 typedef ArcNumTagIndicator<Digraph> ArcNumTag;
1863 int arcNum() const { return 2 * _digraph->arcNum(); }
1865 typedef ArcNumTag EdgeNumTag;
1866 int edgeNum() const { return _digraph->arcNum(); }
1868 typedef FindArcTagIndicator<Digraph> FindArcTag;
1869 Arc findArc(Node s, Node t, Arc p = INVALID) const {
1871 Edge arc = _digraph->findArc(s, t);
1872 if (arc != INVALID) return direct(arc, true);
1873 arc = _digraph->findArc(t, s);
1874 if (arc != INVALID) return direct(arc, false);
1875 } else if (direction(p)) {
1876 Edge arc = _digraph->findArc(s, t, p);
1877 if (arc != INVALID) return direct(arc, true);
1878 arc = _digraph->findArc(t, s);
1879 if (arc != INVALID) return direct(arc, false);
1881 Edge arc = _digraph->findArc(t, s, p);
1882 if (arc != INVALID) return direct(arc, false);
1887 typedef FindArcTag FindEdgeTag;
1888 Edge findEdge(Node s, Node t, Edge p = INVALID) const {
1891 Edge arc = _digraph->findArc(s, t);
1892 if (arc != INVALID) return arc;
1893 arc = _digraph->findArc(t, s);
1894 if (arc != INVALID) return arc;
1895 } else if (_digraph->s(p) == s) {
1896 Edge arc = _digraph->findArc(s, t, p);
1897 if (arc != INVALID) return arc;
1898 arc = _digraph->findArc(t, s);
1899 if (arc != INVALID) return arc;
1901 Edge arc = _digraph->findArc(t, s, p);
1902 if (arc != INVALID) return arc;
1905 return _digraph->findArc(s, t, p);
1912 template <typename _Value>
1916 typedef typename Digraph::template ArcMap<_Value> MapImpl;
1920 typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
1922 typedef _Value Value;
1925 ArcMapBase(const Adaptor& adaptor) :
1926 _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
1928 ArcMapBase(const Adaptor& adaptor, const Value& v)
1929 : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}
1931 void set(const Arc& a, const Value& v) {
1935 _backward.set(a, v);
1939 typename MapTraits<MapImpl>::ConstReturnValue
1940 operator[](const Arc& a) const {
1944 return _backward[a];
1948 typename MapTraits<MapImpl>::ReturnValue
1949 operator[](const Arc& a) {
1953 return _backward[a];
1959 MapImpl _forward, _backward;
1965 template <typename _Value>
1966 class NodeMap : public Digraph::template NodeMap<_Value> {
1969 typedef _Value Value;
1970 typedef typename Digraph::template NodeMap<Value> Parent;
1972 explicit NodeMap(const Adaptor& adaptor)
1973 : Parent(*adaptor._digraph) {}
1975 NodeMap(const Adaptor& adaptor, const _Value& value)
1976 : Parent(*adaptor._digraph, value) { }
1979 NodeMap& operator=(const NodeMap& cmap) {
1980 return operator=<NodeMap>(cmap);
1983 template <typename CMap>
1984 NodeMap& operator=(const CMap& cmap) {
1985 Parent::operator=(cmap);
1991 template <typename _Value>
1993 : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
1996 typedef _Value Value;
1997 typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
1999 ArcMap(const Adaptor& adaptor)
2000 : Parent(adaptor) {}
2002 ArcMap(const Adaptor& adaptor, const Value& value)
2003 : Parent(adaptor, value) {}
2006 ArcMap& operator=(const ArcMap& cmap) {
2007 return operator=<ArcMap>(cmap);
2010 template <typename CMap>
2011 ArcMap& operator=(const CMap& cmap) {
2012 Parent::operator=(cmap);
2017 template <typename _Value>
2018 class EdgeMap : public Digraph::template ArcMap<_Value> {
2021 typedef _Value Value;
2022 typedef typename Digraph::template ArcMap<Value> Parent;
2024 explicit EdgeMap(const Adaptor& adaptor)
2025 : Parent(*adaptor._digraph) {}
2027 EdgeMap(const Adaptor& adaptor, const Value& value)
2028 : Parent(*adaptor._digraph, value) {}
2031 EdgeMap& operator=(const EdgeMap& cmap) {
2032 return operator=<EdgeMap>(cmap);
2035 template <typename CMap>
2036 EdgeMap& operator=(const CMap& cmap) {
2037 Parent::operator=(cmap);
2043 typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
2044 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
2048 UndirectorBase() : _digraph(0) {}
2052 void setDigraph(Digraph& digraph) {
2053 _digraph = &digraph;
2058 /// \ingroup graph_adaptors
2060 /// \brief Undirect the graph
2062 /// This adaptor makes an undirected graph from a directed
2063 /// graph. All arcs of the underlying digraph will be showed in the
2064 /// adaptor as an edge. The Orienter adaptor is conform to the \ref
2065 /// concepts::Graph "Graph concept".
2067 /// \tparam _Digraph It must be conform to the \ref
2068 /// concepts::Digraph "Digraph concept". The type can be specified
2070 template<typename _Digraph>
2072 : public GraphAdaptorExtender<UndirectorBase<_Digraph> > {
2074 typedef _Digraph Digraph;
2075 typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent;
2080 /// \brief Constructor
2082 /// Creates a undirected graph from the given digraph
2083 Undirector(_Digraph& digraph) {
2084 setDigraph(digraph);
2087 /// \brief ArcMap combined from two original ArcMap
2089 /// This class adapts two original digraph ArcMap to
2090 /// get an arc map on the undirected graph.
2091 template <typename _ForwardMap, typename _BackwardMap>
2092 class CombinedArcMap {
2095 typedef _ForwardMap ForwardMap;
2096 typedef _BackwardMap BackwardMap;
2098 typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
2100 typedef typename ForwardMap::Value Value;
2101 typedef typename Parent::Arc Key;
2103 /// \brief Constructor
2106 CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
2107 : _forward(&forward), _backward(&backward) {}
2110 /// \brief Sets the value associated with a key.
2112 /// Sets the value associated with a key.
2113 void set(const Key& e, const Value& a) {
2114 if (Parent::direction(e)) {
2115 _forward->set(e, a);
2117 _backward->set(e, a);
2121 /// \brief Returns the value associated with a key.
2123 /// Returns the value associated with a key.
2124 typename MapTraits<ForwardMap>::ConstReturnValue
2125 operator[](const Key& e) const {
2126 if (Parent::direction(e)) {
2127 return (*_forward)[e];
2129 return (*_backward)[e];
2133 /// \brief Returns the value associated with a key.
2135 /// Returns the value associated with a key.
2136 typename MapTraits<ForwardMap>::ReturnValue
2137 operator[](const Key& e) {
2138 if (Parent::direction(e)) {
2139 return (*_forward)[e];
2141 return (*_backward)[e];
2147 ForwardMap* _forward;
2148 BackwardMap* _backward;
2152 /// \brief Just gives back a combined arc map
2154 /// Just gives back a combined arc map
2155 template <typename ForwardMap, typename BackwardMap>
2156 static CombinedArcMap<ForwardMap, BackwardMap>
2157 combinedArcMap(ForwardMap& forward, BackwardMap& backward) {
2158 return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward);
2161 template <typename ForwardMap, typename BackwardMap>
2162 static CombinedArcMap<const ForwardMap, BackwardMap>
2163 combinedArcMap(const ForwardMap& forward, BackwardMap& backward) {
2164 return CombinedArcMap<const ForwardMap,
2165 BackwardMap>(forward, backward);
2168 template <typename ForwardMap, typename BackwardMap>
2169 static CombinedArcMap<ForwardMap, const BackwardMap>
2170 combinedArcMap(ForwardMap& forward, const BackwardMap& backward) {
2171 return CombinedArcMap<ForwardMap,
2172 const BackwardMap>(forward, backward);
2175 template <typename ForwardMap, typename BackwardMap>
2176 static CombinedArcMap<const ForwardMap, const BackwardMap>
2177 combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) {
2178 return CombinedArcMap<const ForwardMap,
2179 const BackwardMap>(forward, backward);
2184 /// \brief Just gives back an undirected view of the given digraph
2186 /// Just gives back an undirected view of the given digraph
2187 template<typename Digraph>
2188 Undirector<const Digraph>
2189 undirector(const Digraph& digraph) {
2190 return Undirector<const Digraph>(digraph);
2193 template <typename _Graph, typename _DirectionMap>
2194 class OrienterBase {
2197 typedef _Graph Graph;
2198 typedef _DirectionMap DirectionMap;
2200 typedef typename Graph::Node Node;
2201 typedef typename Graph::Edge Arc;
2203 void reverseArc(const Arc& arc) {
2204 _direction->set(arc, !(*_direction)[arc]);
2207 void first(Node& i) const { _graph->first(i); }
2208 void first(Arc& i) const { _graph->first(i); }
2209 void firstIn(Arc& i, const Node& n) const {
2211 _graph->firstInc(i, d, n);
2212 while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
2214 void firstOut(Arc& i, const Node& n ) const {
2216 _graph->firstInc(i, d, n);
2217 while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
2220 void next(Node& i) const { _graph->next(i); }
2221 void next(Arc& i) const { _graph->next(i); }
2222 void nextIn(Arc& i) const {
2223 bool d = !(*_direction)[i];
2224 _graph->nextInc(i, d);
2225 while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
2227 void nextOut(Arc& i) const {
2228 bool d = (*_direction)[i];
2229 _graph->nextInc(i, d);
2230 while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
2233 Node source(const Arc& e) const {
2234 return (*_direction)[e] ? _graph->u(e) : _graph->v(e);
2236 Node target(const Arc& e) const {
2237 return (*_direction)[e] ? _graph->v(e) : _graph->u(e);
2240 typedef NodeNumTagIndicator<Graph> NodeNumTag;
2241 int nodeNum() const { return _graph->nodeNum(); }
2243 typedef EdgeNumTagIndicator<Graph> ArcNumTag;
2244 int arcNum() const { return _graph->edgeNum(); }
2246 typedef FindEdgeTagIndicator<Graph> FindArcTag;
2247 Arc findArc(const Node& u, const Node& v,
2248 const Arc& prev = INVALID) const {
2250 bool d = arc == INVALID ? true : (*_direction)[arc];
2252 arc = _graph->findEdge(u, v, arc);
2253 while (arc != INVALID && !(*_direction)[arc]) {
2254 _graph->findEdge(u, v, arc);
2256 if (arc != INVALID) return arc;
2258 _graph->findEdge(v, u, arc);
2259 while (arc != INVALID && (*_direction)[arc]) {
2260 _graph->findEdge(u, v, arc);
2266 return Node(_graph->addNode());
2269 Arc addArc(const Node& u, const Node& v) {
2270 Arc arc = _graph->addArc(u, v);
2271 _direction->set(arc, _graph->source(arc) == u);
2275 void erase(const Node& i) { _graph->erase(i); }
2276 void erase(const Arc& i) { _graph->erase(i); }
2278 void clear() { _graph->clear(); }
2280 int id(const Node& v) const { return _graph->id(v); }
2281 int id(const Arc& e) const { return _graph->id(e); }
2283 Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
2284 Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
2286 int maxNodeId() const { return _graph->maxNodeId(); }
2287 int maxArcId() const { return _graph->maxEdgeId(); }
2289 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
2290 NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
2292 typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
2293 ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
2295 template <typename _Value>
2296 class NodeMap : public _Graph::template NodeMap<_Value> {
2299 typedef typename _Graph::template NodeMap<_Value> Parent;
2301 explicit NodeMap(const OrienterBase& adapter)
2302 : Parent(*adapter._graph) {}
2304 NodeMap(const OrienterBase& adapter, const _Value& value)
2305 : Parent(*adapter._graph, value) {}
2308 NodeMap& operator=(const NodeMap& cmap) {
2309 return operator=<NodeMap>(cmap);
2312 template <typename CMap>
2313 NodeMap& operator=(const CMap& cmap) {
2314 Parent::operator=(cmap);
2320 template <typename _Value>
2321 class ArcMap : public _Graph::template EdgeMap<_Value> {
2324 typedef typename Graph::template EdgeMap<_Value> Parent;
2326 explicit ArcMap(const OrienterBase& adapter)
2327 : Parent(*adapter._graph) { }
2329 ArcMap(const OrienterBase& adapter, const _Value& value)
2330 : Parent(*adapter._graph, value) { }
2333 ArcMap& operator=(const ArcMap& cmap) {
2334 return operator=<ArcMap>(cmap);
2337 template <typename CMap>
2338 ArcMap& operator=(const CMap& cmap) {
2339 Parent::operator=(cmap);
2348 DirectionMap* _direction;
2350 void setDirectionMap(DirectionMap& direction) {
2351 _direction = &direction;
2354 void setGraph(Graph& graph) {
2360 /// \ingroup graph_adaptors
2362 /// \brief Orients the edges of the graph to get a digraph
2364 /// This adaptor orients each edge in the undirected graph. The
2365 /// direction of the arcs stored in an edge node map. The arcs can
2366 /// be easily reverted by the \c reverseArc() member function in the
2367 /// adaptor. The Orienter adaptor is conform to the \ref
2368 /// concepts::Digraph "Digraph concept".
2370 /// \tparam _Graph It must be conform to the \ref concepts::Graph
2371 /// "Graph concept". The type can be specified to be const.
2372 /// \tparam _DirectionMap A bool valued edge map of the the adapted
2376 template<typename _Graph,
2377 typename DirectionMap = typename _Graph::template EdgeMap<bool> >
2379 public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > {
2381 typedef _Graph Graph;
2382 typedef DigraphAdaptorExtender<
2383 OrienterBase<_Graph, DirectionMap> > Parent;
2384 typedef typename Parent::Arc Arc;
2389 /// \brief Constructor of the adaptor
2391 /// Constructor of the adaptor
2392 Orienter(Graph& graph, DirectionMap& direction) {
2394 setDirectionMap(direction);
2397 /// \brief Reverse arc
2399 /// It reverse the given arc. It simply negate the direction in the map.
2400 void reverseArc(const Arc& a) {
2401 Parent::reverseArc(a);
2405 /// \brief Just gives back a Orienter
2407 /// Just gives back a Orienter
2408 template<typename Graph, typename DirectionMap>
2409 Orienter<const Graph, DirectionMap>
2410 orienter(const Graph& graph, DirectionMap& dm) {
2411 return Orienter<const Graph, DirectionMap>(graph, dm);
2414 template<typename Graph, typename DirectionMap>
2415 Orienter<const Graph, const DirectionMap>
2416 orienter(const Graph& graph, const DirectionMap& dm) {
2417 return Orienter<const Graph, const DirectionMap>(graph, dm);
2420 namespace _adaptor_bits {
2422 template<typename _Digraph,
2423 typename _CapacityMap = typename _Digraph::template ArcMap<int>,
2424 typename _FlowMap = _CapacityMap,
2425 typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
2426 class ResForwardFilter {
2429 typedef _Digraph Digraph;
2430 typedef _CapacityMap CapacityMap;
2431 typedef _FlowMap FlowMap;
2432 typedef _Tolerance Tolerance;
2434 typedef typename Digraph::Arc Key;
2439 const CapacityMap* _capacity;
2440 const FlowMap* _flow;
2441 Tolerance _tolerance;
2444 ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,
2445 const Tolerance& tolerance = Tolerance())
2446 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
2448 bool operator[](const typename Digraph::Arc& a) const {
2449 return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
2453 template<typename _Digraph,
2454 typename _CapacityMap = typename _Digraph::template ArcMap<int>,
2455 typename _FlowMap = _CapacityMap,
2456 typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
2457 class ResBackwardFilter {
2460 typedef _Digraph Digraph;
2461 typedef _CapacityMap CapacityMap;
2462 typedef _FlowMap FlowMap;
2463 typedef _Tolerance Tolerance;
2465 typedef typename Digraph::Arc Key;
2470 const CapacityMap* _capacity;
2471 const FlowMap* _flow;
2472 Tolerance _tolerance;
2476 ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,
2477 const Tolerance& tolerance = Tolerance())
2478 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
2480 bool operator[](const typename Digraph::Arc& a) const {
2481 return _tolerance.positive((*_flow)[a]);
2487 /// \ingroup graph_adaptors
2489 /// \brief An adaptor for composing the residual graph for directed
2490 /// flow and circulation problems.
2492 /// An adaptor for composing the residual graph for directed flow and
2493 /// circulation problems. Let \f$ G=(V, A) \f$ be a directed graph
2494 /// and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
2495 /// be functions on the arc-set.
2497 /// Then Residual implements the digraph structure with
2498 /// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward} \f$,
2499 /// where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
2500 /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so
2501 /// called residual graph. When we take the union
2502 /// \f$ A_{forward}\cup A_{backward} \f$, multiplicities are counted,
2503 /// i.e. if an arc is in both \f$ A_{forward} \f$ and
2504 /// \f$ A_{backward} \f$, then in the adaptor it appears in both
2507 /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
2508 /// "Digraph concept". The type is implicitly const.
2509 /// \tparam _CapacityMap An arc map of some numeric type, it defines
2510 /// the capacities in the flow problem. The map is implicitly const.
2511 /// \tparam _FlowMap An arc map of some numeric type, it defines
2512 /// the capacities in the flow problem.
2513 /// \tparam _Tolerance Handler for inexact computation.
2514 template<typename _Digraph,
2515 typename _CapacityMap = typename _Digraph::template ArcMap<int>,
2516 typename _FlowMap = _CapacityMap,
2517 typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
2520 Undirector<const _Digraph>,
2521 typename Undirector<const _Digraph>::template CombinedArcMap<
2522 _adaptor_bits::ResForwardFilter<const _Digraph, _CapacityMap,
2523 _FlowMap, _Tolerance>,
2524 _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap,
2525 _FlowMap, _Tolerance> > >
2529 typedef _Digraph Digraph;
2530 typedef _CapacityMap CapacityMap;
2531 typedef _FlowMap FlowMap;
2532 typedef _Tolerance Tolerance;
2534 typedef typename CapacityMap::Value Value;
2535 typedef Residual Adaptor;
2539 typedef Undirector<const Digraph> Undirected;
2541 typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap,
2542 FlowMap, Tolerance> ForwardFilter;
2544 typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap,
2545 FlowMap, Tolerance> BackwardFilter;
2547 typedef typename Undirected::
2548 template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
2550 typedef FilterArcs<Undirected, ArcFilter> Parent;
2552 const CapacityMap* _capacity;
2556 ForwardFilter _forward_filter;
2557 BackwardFilter _backward_filter;
2558 ArcFilter _arc_filter;
2562 /// \brief Constructor of the residual digraph.
2564 /// Constructor of the residual graph. The parameters are the digraph,
2565 /// the flow map, the capacity map and a tolerance object.
2566 Residual(const Digraph& digraph, const CapacityMap& capacity,
2567 FlowMap& flow, const Tolerance& tolerance = Tolerance())
2568 : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
2569 _forward_filter(capacity, flow, tolerance),
2570 _backward_filter(capacity, flow, tolerance),
2571 _arc_filter(_forward_filter, _backward_filter)
2573 Parent::setDigraph(_graph);
2574 Parent::setArcFilterMap(_arc_filter);
2577 typedef typename Parent::Arc Arc;
2579 /// \brief Gives back the residual capacity of the arc.
2581 /// Gives back the residual capacity of the arc.
2582 Value residualCapacity(const Arc& a) const {
2583 if (Undirected::direction(a)) {
2584 return (*_capacity)[a] - (*_flow)[a];
2590 /// \brief Augment on the given arc in the residual graph.
2592 /// Augment on the given arc in the residual graph. It increase
2593 /// or decrease the flow on the original arc depend on the direction
2594 /// of the residual arc.
2595 void augment(const Arc& a, const Value& v) const {
2596 if (Undirected::direction(a)) {
2597 _flow->set(a, (*_flow)[a] + v);
2599 _flow->set(a, (*_flow)[a] - v);
2603 /// \brief Returns the direction of the arc.
2605 /// Returns true when the arc is same oriented as the original arc.
2606 static bool forward(const Arc& a) {
2607 return Undirected::direction(a);
2610 /// \brief Returns the direction of the arc.
2612 /// Returns true when the arc is opposite oriented as the original arc.
2613 static bool backward(const Arc& a) {
2614 return !Undirected::direction(a);
2617 /// \brief Gives back the forward oriented residual arc.
2619 /// Gives back the forward oriented residual arc.
2620 static Arc forward(const typename Digraph::Arc& a) {
2621 return Undirected::direct(a, true);
2624 /// \brief Gives back the backward oriented residual arc.
2626 /// Gives back the backward oriented residual arc.
2627 static Arc backward(const typename Digraph::Arc& a) {
2628 return Undirected::direct(a, false);
2631 /// \brief Residual capacity map.
2633 /// In generic residual graph the residual capacity can be obtained
2635 class ResidualCapacity {
2637 const Adaptor* _adaptor;
2642 typedef typename _CapacityMap::Value Value;
2645 ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}
2648 Value operator[](const Arc& a) const {
2649 return _adaptor->residualCapacity(a);
2656 template <typename _Digraph>
2657 class SplitNodesBase {
2660 typedef _Digraph Digraph;
2661 typedef DigraphAdaptorBase<const _Digraph> Parent;
2662 typedef SplitNodesBase Adaptor;
2664 typedef typename Digraph::Node DigraphNode;
2665 typedef typename Digraph::Arc DigraphArc;
2672 template <typename T> class NodeMapBase;
2673 template <typename T> class ArcMapBase;
2677 class Node : public DigraphNode {
2678 friend class SplitNodesBase;
2679 template <typename T> friend class NodeMapBase;
2683 Node(DigraphNode node, bool in)
2684 : DigraphNode(node), _in(in) {}
2689 Node(Invalid) : DigraphNode(INVALID), _in(true) {}
2691 bool operator==(const Node& node) const {
2692 return DigraphNode::operator==(node) && _in == node._in;
2695 bool operator!=(const Node& node) const {
2696 return !(*this == node);
2699 bool operator<(const Node& node) const {
2700 return DigraphNode::operator<(node) ||
2701 (DigraphNode::operator==(node) && _in < node._in);
2706 friend class SplitNodesBase;
2707 template <typename T> friend class ArcMapBase;
2709 typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;
2711 explicit Arc(const DigraphArc& arc) : _item(arc) {}
2712 explicit Arc(const DigraphNode& node) : _item(node) {}
2718 Arc(Invalid) : _item(DigraphArc(INVALID)) {}
2720 bool operator==(const Arc& arc) const {
2721 if (_item.firstState()) {
2722 if (arc._item.firstState()) {
2723 return _item.first() == arc._item.first();
2726 if (arc._item.secondState()) {
2727 return _item.second() == arc._item.second();
2733 bool operator!=(const Arc& arc) const {
2734 return !(*this == arc);
2737 bool operator<(const Arc& arc) const {
2738 if (_item.firstState()) {
2739 if (arc._item.firstState()) {
2740 return _item.first() < arc._item.first();
2744 if (arc._item.secondState()) {
2745 return _item.second() < arc._item.second();
2751 operator DigraphArc() const { return _item.first(); }
2752 operator DigraphNode() const { return _item.second(); }
2756 void first(Node& n) const {
2761 void next(Node& n) const {
2770 void first(Arc& e) const {
2771 e._item.setSecond();
2772 _digraph->first(e._item.second());
2773 if (e._item.second() == INVALID) {
2775 _digraph->first(e._item.first());
2779 void next(Arc& e) const {
2780 if (e._item.secondState()) {
2781 _digraph->next(e._item.second());
2782 if (e._item.second() == INVALID) {
2784 _digraph->first(e._item.first());
2787 _digraph->next(e._item.first());
2791 void firstOut(Arc& e, const Node& n) const {
2793 e._item.setSecond(n);
2796 _digraph->firstOut(e._item.first(), n);
2800 void nextOut(Arc& e) const {
2801 if (!e._item.firstState()) {
2802 e._item.setFirst(INVALID);
2804 _digraph->nextOut(e._item.first());
2808 void firstIn(Arc& e, const Node& n) const {
2810 e._item.setSecond(n);
2813 _digraph->firstIn(e._item.first(), n);
2817 void nextIn(Arc& e) const {
2818 if (!e._item.firstState()) {
2819 e._item.setFirst(INVALID);
2821 _digraph->nextIn(e._item.first());
2825 Node source(const Arc& e) const {
2826 if (e._item.firstState()) {
2827 return Node(_digraph->source(e._item.first()), false);
2829 return Node(e._item.second(), true);
2833 Node target(const Arc& e) const {
2834 if (e._item.firstState()) {
2835 return Node(_digraph->target(e._item.first()), true);
2837 return Node(e._item.second(), false);
2841 int id(const Node& n) const {
2842 return (_digraph->id(n) << 1) | (n._in ? 0 : 1);
2844 Node nodeFromId(int ix) const {
2845 return Node(_digraph->nodeFromId(ix >> 1), (ix & 1) == 0);
2847 int maxNodeId() const {
2848 return 2 * _digraph->maxNodeId() + 1;
2851 int id(const Arc& e) const {
2852 if (e._item.firstState()) {
2853 return _digraph->id(e._item.first()) << 1;
2855 return (_digraph->id(e._item.second()) << 1) | 1;
2858 Arc arcFromId(int ix) const {
2859 if ((ix & 1) == 0) {
2860 return Arc(_digraph->arcFromId(ix >> 1));
2862 return Arc(_digraph->nodeFromId(ix >> 1));
2865 int maxArcId() const {
2866 return std::max(_digraph->maxNodeId() << 1,
2867 (_digraph->maxArcId() << 1) | 1);
2870 static bool inNode(const Node& n) {
2874 static bool outNode(const Node& n) {
2878 static bool origArc(const Arc& e) {
2879 return e._item.firstState();
2882 static bool bindArc(const Arc& e) {
2883 return e._item.secondState();
2886 static Node inNode(const DigraphNode& n) {
2887 return Node(n, true);
2890 static Node outNode(const DigraphNode& n) {
2891 return Node(n, false);
2894 static Arc arc(const DigraphNode& n) {
2898 static Arc arc(const DigraphArc& e) {
2902 typedef True NodeNumTag;
2903 int nodeNum() const {
2904 return 2 * countNodes(*_digraph);
2907 typedef True ArcNumTag;
2908 int arcNum() const {
2909 return countArcs(*_digraph) + countNodes(*_digraph);
2912 typedef True FindArcTag;
2913 Arc findArc(const Node& u, const Node& v,
2914 const Arc& prev = INVALID) const {
2917 if (static_cast<const DigraphNode&>(u) ==
2918 static_cast<const DigraphNode&>(v) && prev == INVALID) {
2924 return Arc(::lemon::findArc(*_digraph, u, v, prev));
2932 template <typename _Value>
2934 : public MapTraits<typename Parent::template NodeMap<_Value> > {
2935 typedef typename Parent::template NodeMap<_Value> NodeImpl;
2938 typedef _Value Value;
2940 NodeMapBase(const Adaptor& adaptor)
2941 : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
2942 NodeMapBase(const Adaptor& adaptor, const Value& value)
2943 : _in_map(*adaptor._digraph, value),
2944 _out_map(*adaptor._digraph, value) {}
2946 void set(const Node& key, const Value& val) {
2947 if (Adaptor::inNode(key)) { _in_map.set(key, val); }
2948 else {_out_map.set(key, val); }
2951 typename MapTraits<NodeImpl>::ReturnValue
2952 operator[](const Node& key) {
2953 if (Adaptor::inNode(key)) { return _in_map[key]; }
2954 else { return _out_map[key]; }
2957 typename MapTraits<NodeImpl>::ConstReturnValue
2958 operator[](const Node& key) const {
2959 if (Adaptor::inNode(key)) { return _in_map[key]; }
2960 else { return _out_map[key]; }
2964 NodeImpl _in_map, _out_map;
2967 template <typename _Value>
2969 : public MapTraits<typename Parent::template ArcMap<_Value> > {
2970 typedef typename Parent::template ArcMap<_Value> ArcImpl;
2971 typedef typename Parent::template NodeMap<_Value> NodeImpl;
2974 typedef _Value Value;
2976 ArcMapBase(const Adaptor& adaptor)
2977 : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
2978 ArcMapBase(const Adaptor& adaptor, const Value& value)
2979 : _arc_map(*adaptor._digraph, value),
2980 _node_map(*adaptor._digraph, value) {}
2982 void set(const Arc& key, const Value& val) {
2983 if (Adaptor::origArc(key)) {
2984 _arc_map.set(key._item.first(), val);
2986 _node_map.set(key._item.second(), val);
2990 typename MapTraits<ArcImpl>::ReturnValue
2991 operator[](const Arc& key) {
2992 if (Adaptor::origArc(key)) {
2993 return _arc_map[key._item.first()];
2995 return _node_map[key._item.second()];
2999 typename MapTraits<ArcImpl>::ConstReturnValue
3000 operator[](const Arc& key) const {
3001 if (Adaptor::origArc(key)) {
3002 return _arc_map[key._item.first()];
3004 return _node_map[key._item.second()];
3015 template <typename _Value>
3017 : public SubMapExtender<Adaptor, NodeMapBase<_Value> >
3020 typedef _Value Value;
3021 typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent;
3023 NodeMap(const Adaptor& adaptor)
3024 : Parent(adaptor) {}
3026 NodeMap(const Adaptor& adaptor, const Value& value)
3027 : Parent(adaptor, value) {}
3030 NodeMap& operator=(const NodeMap& cmap) {
3031 return operator=<NodeMap>(cmap);
3034 template <typename CMap>
3035 NodeMap& operator=(const CMap& cmap) {
3036 Parent::operator=(cmap);
3041 template <typename _Value>
3043 : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
3046 typedef _Value Value;
3047 typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
3049 ArcMap(const Adaptor& adaptor)
3050 : Parent(adaptor) {}
3052 ArcMap(const Adaptor& adaptor, const Value& value)
3053 : Parent(adaptor, value) {}
3056 ArcMap& operator=(const ArcMap& cmap) {
3057 return operator=<ArcMap>(cmap);
3060 template <typename CMap>
3061 ArcMap& operator=(const CMap& cmap) {
3062 Parent::operator=(cmap);
3069 SplitNodesBase() : _digraph(0) {}
3073 void setDigraph(Digraph& digraph) {
3074 _digraph = &digraph;
3079 /// \ingroup graph_adaptors
3081 /// \brief Split the nodes of a directed graph
3083 /// The SplitNodes adaptor splits each node into an in-node and an
3084 /// out-node. Formaly, the adaptor replaces each \f$ u \f$ node in
3085 /// the digraph with two nodes(namely node \f$ u_{in} \f$ and node
3086 /// \f$ u_{out} \f$). If there is a \f$ (v, u) \f$ arc in the
3087 /// original digraph the new target of the arc will be \f$ u_{in} \f$
3088 /// and similarly the source of the original \f$ (u, v) \f$ arc
3089 /// will be \f$ u_{out} \f$. The adaptor will add for each node in
3090 /// the original digraph an additional arc which connects
3091 /// \f$ (u_{in}, u_{out}) \f$.
3093 /// The aim of this class is to run algorithm with node costs if the
3094 /// algorithm can use directly just arc costs. In this case we should use
3095 /// a \c SplitNodes and set the node cost of the graph to the
3096 /// bind arc in the adapted graph.
3098 /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
3099 /// "Digraph concept". The type can be specified to be const.
3100 template <typename _Digraph>
3102 : public DigraphAdaptorExtender<SplitNodesBase<const _Digraph> > {
3104 typedef _Digraph Digraph;
3105 typedef DigraphAdaptorExtender<SplitNodesBase<const Digraph> > Parent;
3107 typedef typename Digraph::Node DigraphNode;
3108 typedef typename Digraph::Arc DigraphArc;
3110 typedef typename Parent::Node Node;
3111 typedef typename Parent::Arc Arc;
3113 /// \brief Constructor of the adaptor.
3115 /// Constructor of the adaptor.
3116 SplitNodes(const Digraph& g) {
3117 Parent::setDigraph(g);
3120 /// \brief Returns true when the node is in-node.
3122 /// Returns true when the node is in-node.
3123 static bool inNode(const Node& n) {
3124 return Parent::inNode(n);
3127 /// \brief Returns true when the node is out-node.
3129 /// Returns true when the node is out-node.
3130 static bool outNode(const Node& n) {
3131 return Parent::outNode(n);
3134 /// \brief Returns true when the arc is arc in the original digraph.
3136 /// Returns true when the arc is arc in the original digraph.
3137 static bool origArc(const Arc& a) {
3138 return Parent::origArc(a);
3141 /// \brief Returns true when the arc binds an in-node and an out-node.
3143 /// Returns true when the arc binds an in-node and an out-node.
3144 static bool bindArc(const Arc& a) {
3145 return Parent::bindArc(a);
3148 /// \brief Gives back the in-node created from the \c node.
3150 /// Gives back the in-node created from the \c node.
3151 static Node inNode(const DigraphNode& n) {
3152 return Parent::inNode(n);
3155 /// \brief Gives back the out-node created from the \c node.
3157 /// Gives back the out-node created from the \c node.
3158 static Node outNode(const DigraphNode& n) {
3159 return Parent::outNode(n);
3162 /// \brief Gives back the arc binds the two part of the node.
3164 /// Gives back the arc binds the two part of the node.
3165 static Arc arc(const DigraphNode& n) {
3166 return Parent::arc(n);
3169 /// \brief Gives back the arc of the original arc.
3171 /// Gives back the arc of the original arc.
3172 static Arc arc(const DigraphArc& a) {
3173 return Parent::arc(a);
3176 /// \brief NodeMap combined from two original NodeMap
3178 /// This class adapt two of the original digraph NodeMap to
3179 /// get a node map on the adapted digraph.
3180 template <typename InNodeMap, typename OutNodeMap>
3181 class CombinedNodeMap {
3185 typedef typename InNodeMap::Value Value;
3187 /// \brief Constructor
3190 CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
3191 : _in_map(in_map), _out_map(out_map) {}
3193 /// \brief The subscript operator.
3195 /// The subscript operator.
3196 Value& operator[](const Key& key) {
3197 if (Parent::inNode(key)) {
3198 return _in_map[key];
3200 return _out_map[key];
3204 /// \brief The const subscript operator.
3206 /// The const subscript operator.
3207 Value operator[](const Key& key) const {
3208 if (Parent::inNode(key)) {
3209 return _in_map[key];
3211 return _out_map[key];
3215 /// \brief The setter function of the map.
3217 /// The setter function of the map.
3218 void set(const Key& key, const Value& value) {
3219 if (Parent::inNode(key)) {
3220 _in_map.set(key, value);
3222 _out_map.set(key, value);
3229 OutNodeMap& _out_map;
3234 /// \brief Just gives back a combined node map
3236 /// Just gives back a combined node map
3237 template <typename InNodeMap, typename OutNodeMap>
3238 static CombinedNodeMap<InNodeMap, OutNodeMap>
3239 combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
3240 return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
3243 template <typename InNodeMap, typename OutNodeMap>
3244 static CombinedNodeMap<const InNodeMap, OutNodeMap>
3245 combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
3246 return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
3249 template <typename InNodeMap, typename OutNodeMap>
3250 static CombinedNodeMap<InNodeMap, const OutNodeMap>
3251 combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
3252 return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
3255 template <typename InNodeMap, typename OutNodeMap>
3256 static CombinedNodeMap<const InNodeMap, const OutNodeMap>
3257 combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
3258 return CombinedNodeMap<const InNodeMap,
3259 const OutNodeMap>(in_map, out_map);
3262 /// \brief ArcMap combined from an original ArcMap and a NodeMap
3264 /// This class adapt an original ArcMap and a NodeMap to get an
3265 /// arc map on the adapted digraph
3266 template <typename DigraphArcMap, typename DigraphNodeMap>
3267 class CombinedArcMap {
3271 typedef typename DigraphArcMap::Value Value;
3273 /// \brief Constructor
3276 CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)
3277 : _arc_map(arc_map), _node_map(node_map) {}
3279 /// \brief The subscript operator.
3281 /// The subscript operator.
3282 void set(const Arc& arc, const Value& val) {
3283 if (Parent::origArc(arc)) {
3284 _arc_map.set(arc, val);
3286 _node_map.set(arc, val);
3290 /// \brief The const subscript operator.
3292 /// The const subscript operator.
3293 Value operator[](const Key& arc) const {
3294 if (Parent::origArc(arc)) {
3295 return _arc_map[arc];
3297 return _node_map[arc];
3301 /// \brief The const subscript operator.
3303 /// The const subscript operator.
3304 Value& operator[](const Key& arc) {
3305 if (Parent::origArc(arc)) {
3306 return _arc_map[arc];
3308 return _node_map[arc];
3313 DigraphArcMap& _arc_map;
3314 DigraphNodeMap& _node_map;
3317 /// \brief Just gives back a combined arc map
3319 /// Just gives back a combined arc map
3320 template <typename DigraphArcMap, typename DigraphNodeMap>
3321 static CombinedArcMap<DigraphArcMap, DigraphNodeMap>
3322 combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
3323 return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map);
3326 template <typename DigraphArcMap, typename DigraphNodeMap>
3327 static CombinedArcMap<const DigraphArcMap, DigraphNodeMap>
3328 combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
3329 return CombinedArcMap<const DigraphArcMap,
3330 DigraphNodeMap>(arc_map, node_map);
3333 template <typename DigraphArcMap, typename DigraphNodeMap>
3334 static CombinedArcMap<DigraphArcMap, const DigraphNodeMap>
3335 combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) {
3336 return CombinedArcMap<DigraphArcMap,
3337 const DigraphNodeMap>(arc_map, node_map);
3340 template <typename DigraphArcMap, typename DigraphNodeMap>
3341 static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap>
3342 combinedArcMap(const DigraphArcMap& arc_map,
3343 const DigraphNodeMap& node_map) {
3344 return CombinedArcMap<const DigraphArcMap,
3345 const DigraphNodeMap>(arc_map, node_map);
3350 /// \brief Just gives back a node splitter
3352 /// Just gives back a node splitter
3353 template<typename Digraph>
3355 splitNodes(const Digraph& digraph) {
3356 return SplitNodes<Digraph>(digraph);
3362 #endif //LEMON_ADAPTORS_H