3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
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_GRAPH_ADAPTOR_H
20 #define LEMON_GRAPH_ADAPTOR_H
22 ///\ingroup graph_adaptors
24 ///\brief Several graph adaptors.
26 ///This file contains several useful graph adaptor functions.
28 ///\author Marton Makai and Balazs Dezso
30 #include <lemon/bits/invalid.h>
31 #include <lemon/maps.h>
33 #include <lemon/bits/base_extender.h>
34 #include <lemon/bits/graph_adaptor_extender.h>
35 #include <lemon/bits/graph_extender.h>
37 #include <lemon/tolerance.h>
43 ///\brief Base type for the Graph Adaptors
45 ///Base type for the Graph Adaptors
47 ///This is the base type for most of LEMON graph adaptors.
48 ///This class implements a trivial graph adaptor i.e. it only wraps the
49 ///functions and types of the graph. The purpose of this class is to
50 ///make easier implementing graph adaptors. E.g. if an adaptor is
51 ///considered which differs from the wrapped graph only in some of its
52 ///functions or types, then it can be derived from GraphAdaptor,
54 ///differences should be implemented.
56 ///author Marton Makai
57 template<typename _Graph>
58 class GraphAdaptorBase {
61 typedef GraphAdaptorBase Adaptor;
62 typedef Graph ParentGraph;
66 GraphAdaptorBase() : graph(0) { }
67 void setGraph(Graph& _graph) { graph=&_graph; }
70 GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
72 typedef typename Graph::Node Node;
73 typedef typename Graph::Edge Edge;
75 void first(Node& i) const { graph->first(i); }
76 void first(Edge& i) const { graph->first(i); }
77 void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
78 void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
80 void next(Node& i) const { graph->next(i); }
81 void next(Edge& i) const { graph->next(i); }
82 void nextIn(Edge& i) const { graph->nextIn(i); }
83 void nextOut(Edge& i) const { graph->nextOut(i); }
85 Node source(const Edge& e) const { return graph->source(e); }
86 Node target(const Edge& e) const { return graph->target(e); }
88 typedef NodeNumTagIndicator<Graph> NodeNumTag;
89 int nodeNum() const { return graph->nodeNum(); }
91 typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
92 int edgeNum() const { return graph->edgeNum(); }
94 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
95 Edge findEdge(const Node& source, const Node& target,
96 const Edge& prev = INVALID) {
97 return graph->findEdge(source, target, prev);
100 Node addNode() const {
101 return Node(graph->addNode());
104 Edge addEdge(const Node& source, const Node& target) const {
105 return Edge(graph->addEdge(source, target));
108 void erase(const Node& i) const { graph->erase(i); }
109 void erase(const Edge& i) const { graph->erase(i); }
111 void clear() const { graph->clear(); }
113 int id(const Node& v) const { return graph->id(v); }
114 int id(const Edge& e) const { return graph->id(e); }
116 Node fromNodeId(int id) const {
117 return graph->fromNodeId(id);
120 Edge fromEdgeId(int id) const {
121 return graph->fromEdgeId(id);
124 int maxNodeId() const {
125 return graph->maxNodeId();
128 int maxEdgeId() const {
129 return graph->maxEdgeId();
132 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
134 NodeNotifier& getNotifier(Node) const {
135 return graph->getNotifier(Node());
138 typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
140 EdgeNotifier& getNotifier(Edge) const {
141 return graph->getNotifier(Edge());
144 template <typename _Value>
145 class NodeMap : public Graph::template NodeMap<_Value> {
148 typedef typename Graph::template NodeMap<_Value> Parent;
150 explicit NodeMap(const Adaptor& ga)
151 : Parent(*ga.graph) {}
153 NodeMap(const Adaptor& ga, const _Value& value)
154 : Parent(*ga.graph, value) { }
156 NodeMap& operator=(const NodeMap& cmap) {
157 return operator=<NodeMap>(cmap);
160 template <typename CMap>
161 NodeMap& operator=(const CMap& cmap) {
162 Parent::operator=(cmap);
168 template <typename _Value>
169 class EdgeMap : public Graph::template EdgeMap<_Value> {
172 typedef typename Graph::template EdgeMap<_Value> Parent;
174 explicit EdgeMap(const Adaptor& ga)
175 : Parent(*ga.graph) {}
177 EdgeMap(const Adaptor& ga, const _Value& value)
178 : Parent(*ga.graph, value) {}
180 EdgeMap& operator=(const EdgeMap& cmap) {
181 return operator=<EdgeMap>(cmap);
184 template <typename CMap>
185 EdgeMap& operator=(const CMap& cmap) {
186 Parent::operator=(cmap);
194 ///\ingroup graph_adaptors
196 ///\brief Trivial Graph Adaptor
198 /// This class is an adaptor which does not change the adapted graph.
199 /// It can be used only to test the graph adaptors.
200 template <typename _Graph>
202 public GraphAdaptorExtender<GraphAdaptorBase<_Graph> > {
204 typedef _Graph Graph;
205 typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent;
207 GraphAdaptor() : Parent() { }
210 explicit GraphAdaptor(Graph& _graph) { setGraph(_graph); }
213 /// \brief Just gives back a graph adaptor
215 /// Just gives back a graph adaptor which
216 /// should be provide original graph
217 template<typename Graph>
218 GraphAdaptor<const Graph>
219 graphAdaptor(const Graph& graph) {
220 return GraphAdaptor<const Graph>(graph);
224 template <typename _Graph>
225 class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
227 typedef _Graph Graph;
228 typedef GraphAdaptorBase<_Graph> Parent;
230 RevGraphAdaptorBase() : Parent() { }
232 typedef typename Parent::Node Node;
233 typedef typename Parent::Edge Edge;
235 void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
236 void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
238 void nextIn(Edge& i) const { Parent::nextOut(i); }
239 void nextOut(Edge& i) const { Parent::nextIn(i); }
241 Node source(const Edge& e) const { return Parent::target(e); }
242 Node target(const Edge& e) const { return Parent::source(e); }
244 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
245 Edge findEdge(const Node& source, const Node& target,
246 const Edge& prev = INVALID) {
247 return Parent::findEdge(target, source, prev);
253 ///\ingroup graph_adaptors
255 ///\brief A graph adaptor which reverses the orientation of the edges.
257 /// If \c g is defined as
263 /// RevGraphAdaptor<ListGraph> ga(g);
265 /// implements the graph obtained from \c g by
266 /// reversing the orientation of its edges.
267 template<typename _Graph>
268 class RevGraphAdaptor :
269 public GraphAdaptorExtender<RevGraphAdaptorBase<_Graph> > {
271 typedef _Graph Graph;
272 typedef GraphAdaptorExtender<
273 RevGraphAdaptorBase<_Graph> > Parent;
275 RevGraphAdaptor() { }
277 explicit RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
280 /// \brief Just gives back a reverse graph adaptor
282 /// Just gives back a reverse graph adaptor
283 template<typename Graph>
284 RevGraphAdaptor<const Graph>
285 revGraphAdaptor(const Graph& graph) {
286 return RevGraphAdaptor<const Graph>(graph);
289 template <typename _Graph, typename NodeFilterMap,
290 typename EdgeFilterMap, bool checked = true>
291 class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
293 typedef _Graph Graph;
294 typedef SubGraphAdaptorBase Adaptor;
295 typedef GraphAdaptorBase<_Graph> Parent;
297 NodeFilterMap* node_filter_map;
298 EdgeFilterMap* edge_filter_map;
299 SubGraphAdaptorBase() : Parent(),
300 node_filter_map(0), edge_filter_map(0) { }
302 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
303 node_filter_map=&_node_filter_map;
305 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
306 edge_filter_map=&_edge_filter_map;
311 typedef typename Parent::Node Node;
312 typedef typename Parent::Edge Edge;
314 void first(Node& i) const {
316 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
319 void first(Edge& i) const {
321 while (i!=INVALID && (!(*edge_filter_map)[i]
322 || !(*node_filter_map)[Parent::source(i)]
323 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
326 void firstIn(Edge& i, const Node& n) const {
327 Parent::firstIn(i, n);
328 while (i!=INVALID && (!(*edge_filter_map)[i]
329 || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
332 void firstOut(Edge& i, const Node& n) const {
333 Parent::firstOut(i, n);
334 while (i!=INVALID && (!(*edge_filter_map)[i]
335 || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
338 void next(Node& i) const {
340 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
343 void next(Edge& i) const {
345 while (i!=INVALID && (!(*edge_filter_map)[i]
346 || !(*node_filter_map)[Parent::source(i)]
347 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
350 void nextIn(Edge& i) const {
352 while (i!=INVALID && (!(*edge_filter_map)[i]
353 || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
356 void nextOut(Edge& i) const {
358 while (i!=INVALID && (!(*edge_filter_map)[i]
359 || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
364 /// This function hides \c n in the graph, i.e. the iteration
365 /// jumps over it. This is done by simply setting the value of \c n
366 /// to be false in the corresponding node-map.
367 void hide(const Node& n) const { node_filter_map->set(n, false); }
371 /// This function hides \c e in the graph, i.e. the iteration
372 /// jumps over it. This is done by simply setting the value of \c e
373 /// to be false in the corresponding edge-map.
374 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
378 /// The value of \c n is set to be true in the node-map which stores
379 /// hide information. If \c n was hidden previuosly, then it is shown
381 void unHide(const Node& n) const { node_filter_map->set(n, true); }
385 /// The value of \c e is set to be true in the edge-map which stores
386 /// hide information. If \c e was hidden previuosly, then it is shown
388 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
390 /// Returns true if \c n is hidden.
394 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
396 /// Returns true if \c n is hidden.
400 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
402 typedef False NodeNumTag;
403 typedef False EdgeNumTag;
405 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
406 Edge findEdge(const Node& source, const Node& target,
407 const Edge& prev = INVALID) {
408 if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
411 Edge edge = Parent::findEdge(source, target, prev);
412 while (edge != INVALID && !(*edge_filter_map)[edge]) {
413 edge = Parent::findEdge(source, target, edge);
418 template <typename _Value>
420 : public SubMapExtender<Adaptor,
421 typename Parent::template NodeMap<_Value> >
424 typedef Adaptor Graph;
425 typedef SubMapExtender<Adaptor, typename Parent::
426 template NodeMap<_Value> > Parent;
428 NodeMap(const Graph& graph)
430 NodeMap(const Graph& graph, const _Value& value)
431 : Parent(graph, value) {}
433 NodeMap& operator=(const NodeMap& cmap) {
434 return operator=<NodeMap>(cmap);
437 template <typename CMap>
438 NodeMap& operator=(const CMap& cmap) {
439 Parent::operator=(cmap);
444 template <typename _Value>
446 : public SubMapExtender<Adaptor,
447 typename Parent::template EdgeMap<_Value> >
450 typedef Adaptor Graph;
451 typedef SubMapExtender<Adaptor, typename Parent::
452 template EdgeMap<_Value> > Parent;
454 EdgeMap(const Graph& graph)
456 EdgeMap(const Graph& graph, const _Value& value)
457 : Parent(graph, value) {}
459 EdgeMap& operator=(const EdgeMap& cmap) {
460 return operator=<EdgeMap>(cmap);
463 template <typename CMap>
464 EdgeMap& operator=(const CMap& cmap) {
465 Parent::operator=(cmap);
472 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
473 class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
474 : public GraphAdaptorBase<_Graph> {
476 typedef _Graph Graph;
477 typedef SubGraphAdaptorBase Adaptor;
478 typedef GraphAdaptorBase<_Graph> Parent;
480 NodeFilterMap* node_filter_map;
481 EdgeFilterMap* edge_filter_map;
482 SubGraphAdaptorBase() : Parent(),
483 node_filter_map(0), edge_filter_map(0) { }
485 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
486 node_filter_map=&_node_filter_map;
488 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
489 edge_filter_map=&_edge_filter_map;
494 typedef typename Parent::Node Node;
495 typedef typename Parent::Edge Edge;
497 void first(Node& i) const {
499 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
502 void first(Edge& i) const {
504 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
507 void firstIn(Edge& i, const Node& n) const {
508 Parent::firstIn(i, n);
509 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
512 void firstOut(Edge& i, const Node& n) const {
513 Parent::firstOut(i, n);
514 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
517 void next(Node& i) const {
519 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
521 void next(Edge& i) const {
523 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
525 void nextIn(Edge& i) const {
527 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
530 void nextOut(Edge& i) const {
532 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
537 /// This function hides \c n in the graph, i.e. the iteration
538 /// jumps over it. This is done by simply setting the value of \c n
539 /// to be false in the corresponding node-map.
540 void hide(const Node& n) const { node_filter_map->set(n, false); }
544 /// This function hides \c e in the graph, i.e. the iteration
545 /// jumps over it. This is done by simply setting the value of \c e
546 /// to be false in the corresponding edge-map.
547 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
551 /// The value of \c n is set to be true in the node-map which stores
552 /// hide information. If \c n was hidden previuosly, then it is shown
554 void unHide(const Node& n) const { node_filter_map->set(n, true); }
558 /// The value of \c e is set to be true in the edge-map which stores
559 /// hide information. If \c e was hidden previuosly, then it is shown
561 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
563 /// Returns true if \c n is hidden.
567 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
569 /// Returns true if \c n is hidden.
573 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
575 typedef False NodeNumTag;
576 typedef False EdgeNumTag;
578 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
579 Edge findEdge(const Node& source, const Node& target,
580 const Edge& prev = INVALID) {
581 if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
584 Edge edge = Parent::findEdge(source, target, prev);
585 while (edge != INVALID && !(*edge_filter_map)[edge]) {
586 edge = Parent::findEdge(source, target, edge);
591 template <typename _Value>
593 : public SubMapExtender<Adaptor,
594 typename Parent::template NodeMap<_Value> >
597 typedef Adaptor Graph;
598 typedef SubMapExtender<Adaptor, typename Parent::
599 template NodeMap<_Value> > Parent;
601 NodeMap(const Graph& graph)
603 NodeMap(const Graph& graph, const _Value& value)
604 : Parent(graph, value) {}
606 NodeMap& operator=(const NodeMap& cmap) {
607 return operator=<NodeMap>(cmap);
610 template <typename CMap>
611 NodeMap& operator=(const CMap& cmap) {
612 Parent::operator=(cmap);
617 template <typename _Value>
619 : public SubMapExtender<Adaptor,
620 typename Parent::template EdgeMap<_Value> >
623 typedef Adaptor Graph;
624 typedef SubMapExtender<Adaptor, typename Parent::
625 template EdgeMap<_Value> > Parent;
627 EdgeMap(const Graph& graph)
629 EdgeMap(const Graph& graph, const _Value& value)
630 : Parent(graph, value) {}
632 EdgeMap& operator=(const EdgeMap& cmap) {
633 return operator=<EdgeMap>(cmap);
636 template <typename CMap>
637 EdgeMap& operator=(const CMap& cmap) {
638 Parent::operator=(cmap);
645 /// \ingroup graph_adaptors
647 /// \brief A graph adaptor for hiding nodes and edges from a graph.
649 /// SubGraphAdaptor shows the graph with filtered node-set and
650 /// edge-set. If the \c checked parameter is true then it filters the edgeset
651 /// to do not get invalid edges without source or target.
652 /// Let \f$ G=(V, A) \f$ be a directed graph
653 /// and suppose that the graph instance \c g of type ListGraph
654 /// implements \f$ G \f$.
655 /// Let moreover \f$ b_V \f$ and \f$ b_A \f$ be bool-valued functions resp.
656 /// on the node-set and edge-set.
657 /// SubGraphAdaptor<...>::NodeIt iterates
658 /// on the node-set \f$ \{v\in V : b_V(v)=true\} \f$ and
659 /// SubGraphAdaptor<...>::EdgeIt iterates
660 /// on the edge-set \f$ \{e\in A : b_A(e)=true\} \f$. Similarly,
661 /// SubGraphAdaptor<...>::OutEdgeIt and
662 /// SubGraphAdaptor<...>::InEdgeIt iterates
663 /// only on edges leaving and entering a specific node which have true value.
665 /// If the \c checked template parameter is false then we have to note that
666 /// the node-iterator cares only the filter on the node-set, and the
667 /// edge-iterator cares only the filter on the edge-set.
668 /// This way the edge-map
669 /// should filter all edges which's source or target is filtered by the
672 /// typedef ListGraph Graph;
674 /// typedef Graph::Node Node;
675 /// typedef Graph::Edge Edge;
676 /// Node u=g.addNode(); //node of id 0
677 /// Node v=g.addNode(); //node of id 1
678 /// Node e=g.addEdge(u, v); //edge of id 0
679 /// Node f=g.addEdge(v, u); //edge of id 1
680 /// Graph::NodeMap<bool> nm(g, true);
681 /// nm.set(u, false);
682 /// Graph::EdgeMap<bool> em(g, true);
683 /// em.set(e, false);
684 /// typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGA;
685 /// SubGA ga(g, nm, em);
686 /// for (SubGA::NodeIt n(ga); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
687 /// std::cout << ":-)" << std::endl;
688 /// for (SubGA::EdgeIt e(ga); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
690 /// The output of the above code is the following.
696 /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
697 /// \c Graph::Node that is why \c g.id(n) can be applied.
699 /// For other examples see also the documentation of NodeSubGraphAdaptor and
700 /// EdgeSubGraphAdaptor.
702 /// \author Marton Makai
704 template<typename _Graph, typename NodeFilterMap,
705 typename EdgeFilterMap, bool checked = true>
706 class SubGraphAdaptor :
707 public GraphAdaptorExtender<
708 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
710 typedef _Graph Graph;
711 typedef GraphAdaptorExtender< SubGraphAdaptorBase<_Graph, NodeFilterMap,
712 EdgeFilterMap, checked> >
716 SubGraphAdaptor() { }
719 SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
720 EdgeFilterMap& _edge_filter_map) {
722 setNodeFilterMap(_node_filter_map);
723 setEdgeFilterMap(_edge_filter_map);
728 /// \brief Just gives back a sub graph adaptor
730 /// Just gives back a sub graph adaptor
731 template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
732 SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>
733 subGraphAdaptor(const Graph& graph,
734 NodeFilterMap& nfm, EdgeFilterMap& efm) {
735 return SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>
739 template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
740 SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>
741 subGraphAdaptor(const Graph& graph,
742 NodeFilterMap& nfm, EdgeFilterMap& efm) {
743 return SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>
747 template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
748 SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>
749 subGraphAdaptor(const Graph& graph,
750 NodeFilterMap& nfm, EdgeFilterMap& efm) {
751 return SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>
755 template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
756 SubGraphAdaptor<const Graph, const NodeFilterMap, const EdgeFilterMap>
757 subGraphAdaptor(const Graph& graph,
758 NodeFilterMap& nfm, EdgeFilterMap& efm) {
759 return SubGraphAdaptor<const Graph, const NodeFilterMap,
760 const EdgeFilterMap>(graph, nfm, efm);
765 ///\ingroup graph_adaptors
767 ///\brief An adaptor for hiding nodes from a graph.
769 ///An adaptor for hiding nodes from a graph.
770 ///This adaptor specializes SubGraphAdaptor in the way that only
772 ///can be filtered. In usual case the checked parameter is true, we get the
773 ///induced subgraph. But if the checked parameter is false then we can only
774 ///filter only isolated nodes.
775 ///\author Marton Makai
776 template<typename Graph, typename NodeFilterMap, bool checked = true>
777 class NodeSubGraphAdaptor :
778 public SubGraphAdaptor<Graph, NodeFilterMap,
779 ConstMap<typename Graph::Edge,bool>, checked> {
782 typedef SubGraphAdaptor<Graph, NodeFilterMap,
783 ConstMap<typename Graph::Edge,bool>, checked >
787 ConstMap<typename Graph::Edge, bool> const_true_map;
789 NodeSubGraphAdaptor() : const_true_map(true) {
790 Parent::setEdgeFilterMap(const_true_map);
795 NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
796 Parent(), const_true_map(true) {
797 Parent::setGraph(_graph);
798 Parent::setNodeFilterMap(_node_filter_map);
799 Parent::setEdgeFilterMap(const_true_map);
805 /// \brief Just gives back a node sub graph adaptor
807 /// Just gives back a node sub graph adaptor
808 template<typename Graph, typename NodeFilterMap>
809 NodeSubGraphAdaptor<const Graph, NodeFilterMap>
810 nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) {
811 return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm);
814 template<typename Graph, typename NodeFilterMap>
815 NodeSubGraphAdaptor<const Graph, const NodeFilterMap>
816 nodeSubGraphAdaptor(const Graph& graph, const NodeFilterMap& nfm) {
817 return NodeSubGraphAdaptor<const Graph, const NodeFilterMap>(graph, nfm);
820 ///\ingroup graph_adaptors
822 ///\brief An adaptor for hiding edges from a graph.
824 ///An adaptor for hiding edges from a graph.
825 ///This adaptor specializes SubGraphAdaptor in the way that
827 ///can be filtered. The usefulness of this adaptor is demonstrated in the
828 ///problem of searching a maximum number of edge-disjoint shortest paths
830 ///two nodes \c s and \c t. Shortest here means being shortest w.r.t.
831 ///non-negative edge-lengths. Note that
832 ///the comprehension of the presented solution
833 ///need's some elementary knowledge from combinatorial optimization.
835 ///If a single shortest path is to be
836 ///searched between \c s and \c t, then this can be done easily by
837 ///applying the Dijkstra algorithm. What happens, if a maximum number of
838 ///edge-disjoint shortest paths is to be computed. It can be proved that an
839 ///edge can be in a shortest path if and only
840 ///if it is tight with respect to
841 ///the potential function computed by Dijkstra.
842 ///Moreover, any path containing
843 ///only such edges is a shortest one.
844 ///Thus we have to compute a maximum number
845 ///of edge-disjoint paths between \c s and \c t in
846 ///the graph which has edge-set
847 ///all the tight edges. The computation will be demonstrated
849 ///graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
850 ///The full source code is available in \ref sub_graph_adaptor_demo.cc.
851 ///If you are interested in more demo programs, you can use
852 ///\ref dim_to_dot.cc to generate .dot files from dimacs files.
853 ///The .dot file of the following figure was generated by
854 ///the demo program \ref dim_to_dot.cc.
857 ///digraph lemon_dot_example {
858 ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
859 ///n0 [ label="0 (s)" ];
865 ///n6 [ label="6 (t)" ];
866 ///edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
867 ///n5 -> n6 [ label="9, length:4" ];
868 ///n4 -> n6 [ label="8, length:2" ];
869 ///n3 -> n5 [ label="7, length:1" ];
870 ///n2 -> n5 [ label="6, length:3" ];
871 ///n2 -> n6 [ label="5, length:5" ];
872 ///n2 -> n4 [ label="4, length:2" ];
873 ///n1 -> n4 [ label="3, length:3" ];
874 ///n0 -> n3 [ label="2, length:1" ];
875 ///n0 -> n2 [ label="1, length:2" ];
876 ///n0 -> n1 [ label="0, length:3" ];
883 ///LengthMap length(g);
885 ///readDimacs(std::cin, g, length, s, t);
887 ///cout << "edges with lengths (of form id, source--length->target): " << endl;
888 ///for(EdgeIt e(g); e!=INVALID; ++e)
889 /// cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
890 /// << length[e] << "->" << g.id(g.target(e)) << endl;
892 ///cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
894 ///Next, the potential function is computed with Dijkstra.
896 ///typedef Dijkstra<Graph, LengthMap> Dijkstra;
897 ///Dijkstra dijkstra(g, length);
900 ///Next, we consrtruct a map which filters the edge-set to the tight edges.
902 ///typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
904 ///TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
906 ///typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGA;
907 ///SubGA ga(g, tight_edge_filter);
909 ///Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
910 ///with a max flow algorithm Preflow.
912 ///ConstMap<Edge, int> const_1_map(1);
913 ///Graph::EdgeMap<int> flow(g, 0);
915 ///Preflow<SubGA, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
916 /// preflow(ga, s, t, const_1_map, flow);
919 ///Last, the output is:
921 ///cout << "maximum number of edge-disjoint shortest path: "
922 /// << preflow.flowValue() << endl;
923 ///cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
925 ///for(EdgeIt e(g); e!=INVALID; ++e)
927 /// cout << " " << g.id(g.source(e)) << "--"
928 /// << length[e] << "->" << g.id(g.target(e)) << endl;
930 ///The program has the following (expected :-)) output:
932 ///edges with lengths (of form id, source--length->target):
944 ///maximum number of edge-disjoint shortest path: 2
945 ///edges of the maximum number of edge-disjoint shortest s-t paths:
954 ///\author Marton Makai
955 template<typename Graph, typename EdgeFilterMap>
956 class EdgeSubGraphAdaptor :
957 public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
958 EdgeFilterMap, false> {
960 typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
961 EdgeFilterMap, false> Parent;
963 ConstMap<typename Graph::Node, bool> const_true_map;
965 EdgeSubGraphAdaptor() : const_true_map(true) {
966 Parent::setNodeFilterMap(const_true_map);
971 EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
972 Parent(), const_true_map(true) {
973 Parent::setGraph(_graph);
974 Parent::setNodeFilterMap(const_true_map);
975 Parent::setEdgeFilterMap(_edge_filter_map);
980 /// \brief Just gives back an edge sub graph adaptor
982 /// Just gives back an edge sub graph adaptor
983 template<typename Graph, typename EdgeFilterMap>
984 EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>
985 edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) {
986 return EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>(graph, efm);
989 template<typename Graph, typename EdgeFilterMap>
990 EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>
991 edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) {
992 return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm);
995 template <typename _Graph>
996 class UndirGraphAdaptorBase :
997 public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
999 typedef _Graph Graph;
1000 typedef UndirGraphAdaptorBase Adaptor;
1001 typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
1005 UndirGraphAdaptorBase() : Parent() {}
1009 typedef typename Parent::UEdge UEdge;
1010 typedef typename Parent::Edge Edge;
1014 template <typename _Value>
1018 typedef typename _Graph::template EdgeMap<_Value> MapImpl;
1022 typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
1024 typedef _Value Value;
1027 EdgeMapBase(const Adaptor& adaptor) :
1028 forward_map(*adaptor.graph), backward_map(*adaptor.graph) {}
1030 EdgeMapBase(const Adaptor& adaptor, const Value& v)
1031 : forward_map(*adaptor.graph, v), backward_map(*adaptor.graph, v) {}
1033 void set(const Edge& e, const Value& a) {
1034 if (Parent::direction(e)) {
1035 forward_map.set(e, a);
1037 backward_map.set(e, a);
1041 typename MapTraits<MapImpl>::ConstReturnValue operator[](Edge e) const {
1042 if (Parent::direction(e)) {
1043 return forward_map[e];
1045 return backward_map[e];
1049 typename MapTraits<MapImpl>::ReturnValue operator[](Edge e) {
1050 if (Parent::direction(e)) {
1051 return forward_map[e];
1053 return backward_map[e];
1059 MapImpl forward_map, backward_map;
1065 template <typename _Value>
1067 : public SubMapExtender<Adaptor, EdgeMapBase<_Value> >
1070 typedef Adaptor Graph;
1071 typedef SubMapExtender<Adaptor, EdgeMapBase<_Value> > Parent;
1073 EdgeMap(const Graph& graph)
1075 EdgeMap(const Graph& graph, const _Value& value)
1076 : Parent(graph, value) {}
1078 EdgeMap& operator=(const EdgeMap& cmap) {
1079 return operator=<EdgeMap>(cmap);
1082 template <typename CMap>
1083 EdgeMap& operator=(const CMap& cmap) {
1084 Parent::operator=(cmap);
1089 template <typename _Value>
1090 class UEdgeMap : public Graph::template EdgeMap<_Value> {
1093 typedef typename Graph::template EdgeMap<_Value> Parent;
1095 explicit UEdgeMap(const Adaptor& ga)
1096 : Parent(*ga.graph) {}
1098 UEdgeMap(const Adaptor& ga, const _Value& value)
1099 : Parent(*ga.graph, value) {}
1101 UEdgeMap& operator=(const UEdgeMap& cmap) {
1102 return operator=<UEdgeMap>(cmap);
1105 template <typename CMap>
1106 UEdgeMap& operator=(const CMap& cmap) {
1107 Parent::operator=(cmap);
1115 template <typename _Graph, typename Enable = void>
1116 class AlterableUndirGraphAdaptor
1117 : public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > {
1119 typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent;
1123 AlterableUndirGraphAdaptor() : Parent() {}
1127 typedef typename Parent::EdgeNotifier UEdgeNotifier;
1128 typedef InvalidType EdgeNotifier;
1132 template <typename _Graph>
1133 class AlterableUndirGraphAdaptor<
1135 typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type >
1136 : public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > {
1139 typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent;
1140 typedef _Graph Graph;
1141 typedef typename _Graph::Edge GraphEdge;
1145 AlterableUndirGraphAdaptor()
1146 : Parent(), edge_notifier(*this), edge_notifier_proxy(*this) {}
1148 void setGraph(_Graph& graph) {
1149 Parent::setGraph(graph);
1150 edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge()));
1155 ~AlterableUndirGraphAdaptor() {
1156 edge_notifier.clear();
1159 typedef typename Parent::UEdge UEdge;
1160 typedef typename Parent::Edge Edge;
1162 typedef typename Parent::EdgeNotifier UEdgeNotifier;
1164 using Parent::getNotifier;
1166 typedef AlterationNotifier<AlterableUndirGraphAdaptor,
1168 EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
1172 class NotifierProxy : public Graph::EdgeNotifier::ObserverBase {
1175 typedef typename Graph::EdgeNotifier::ObserverBase Parent;
1176 typedef AlterableUndirGraphAdaptor AdaptorBase;
1178 NotifierProxy(const AdaptorBase& _adaptor)
1179 : Parent(), adaptor(&_adaptor) {
1182 virtual ~NotifierProxy() {
1183 if (Parent::attached()) {
1188 void setNotifier(typename Graph::EdgeNotifier& notifier) {
1189 Parent::attach(notifier);
1195 virtual void add(const GraphEdge& ge) {
1196 std::vector<Edge> edges;
1197 edges.push_back(AdaptorBase::Parent::direct(ge, true));
1198 edges.push_back(AdaptorBase::Parent::direct(ge, false));
1199 adaptor->getNotifier(Edge()).add(edges);
1201 virtual void add(const std::vector<GraphEdge>& ge) {
1202 std::vector<Edge> edges;
1203 for (int i = 0; i < (int)ge.size(); ++i) {
1204 edges.push_back(AdaptorBase::Parent::direct(ge[i], true));
1205 edges.push_back(AdaptorBase::Parent::direct(ge[i], false));
1207 adaptor->getNotifier(Edge()).add(edges);
1209 virtual void erase(const GraphEdge& ge) {
1210 std::vector<Edge> edges;
1211 edges.push_back(AdaptorBase::Parent::direct(ge, true));
1212 edges.push_back(AdaptorBase::Parent::direct(ge, false));
1213 adaptor->getNotifier(Edge()).erase(edges);
1215 virtual void erase(const std::vector<GraphEdge>& ge) {
1216 std::vector<Edge> edges;
1217 for (int i = 0; i < (int)ge.size(); ++i) {
1218 edges.push_back(AdaptorBase::Parent::direct(ge[i], true));
1219 edges.push_back(AdaptorBase::Parent::direct(ge[i], false));
1221 adaptor->getNotifier(Edge()).erase(edges);
1223 virtual void build() {
1224 adaptor->getNotifier(Edge()).build();
1226 virtual void clear() {
1227 adaptor->getNotifier(Edge()).clear();
1230 const AdaptorBase* adaptor;
1234 mutable EdgeNotifier edge_notifier;
1235 NotifierProxy edge_notifier_proxy;
1240 ///\ingroup graph_adaptors
1242 /// \brief An undirected graph is made from a directed graph by an adaptor
1244 /// Undocumented, untested!!!
1245 /// If somebody knows nice demo application, let's polulate it.
1247 /// \author Marton Makai
1248 template<typename _Graph>
1249 class UndirGraphAdaptor : public AlterableUndirGraphAdaptor<_Graph> {
1251 typedef _Graph Graph;
1252 typedef AlterableUndirGraphAdaptor<_Graph> Parent;
1254 UndirGraphAdaptor() { }
1256 UndirGraphAdaptor(_Graph& _graph) {
1260 template <typename _ForwardMap, typename _BackwardMap>
1261 class CombinedEdgeMap {
1264 typedef _ForwardMap ForwardMap;
1265 typedef _BackwardMap BackwardMap;
1267 typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
1269 typedef typename ForwardMap::Value Value;
1270 typedef typename Parent::Edge Key;
1272 CombinedEdgeMap() : forward_map(0), backward_map(0) {}
1274 CombinedEdgeMap(ForwardMap& _forward_map, BackwardMap& _backward_map)
1275 : forward_map(&_forward_map), backward_map(&_backward_map) {}
1277 void set(const Key& e, const Value& a) {
1278 if (Parent::direction(e)) {
1279 forward_map->set(e, a);
1281 backward_map->set(e, a);
1285 typename MapTraits<ForwardMap>::ConstReturnValue
1286 operator[](const Key& e) const {
1287 if (Parent::direction(e)) {
1288 return (*forward_map)[e];
1290 return (*backward_map)[e];
1294 typename MapTraits<ForwardMap>::ReturnValue
1295 operator[](const Key& e) {
1296 if (Parent::direction(e)) {
1297 return (*forward_map)[e];
1299 return (*backward_map)[e];
1303 void setForwardMap(ForwardMap& _forward_map) {
1304 forward_map = &_forward_map;
1307 void setBackwardMap(BackwardMap& _backward_map) {
1308 backward_map = &_backward_map;
1313 ForwardMap* forward_map;
1314 BackwardMap* backward_map;
1320 /// \brief Just gives back an undir graph adaptor
1322 /// Just gives back an undir graph adaptor
1323 template<typename Graph>
1324 UndirGraphAdaptor<const Graph>
1325 undirGraphAdaptor(const Graph& graph) {
1326 return UndirGraphAdaptor<const Graph>(graph);
1329 template<typename Graph, typename Number,
1330 typename CapacityMap, typename FlowMap,
1331 typename Tolerance = Tolerance<Number> >
1332 class ResForwardFilter {
1333 const CapacityMap* capacity;
1334 const FlowMap* flow;
1335 Tolerance tolerance;
1337 typedef typename Graph::Edge Key;
1340 ResForwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
1341 const Tolerance& _tolerance = Tolerance())
1342 : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
1344 ResForwardFilter(const Tolerance& _tolerance)
1345 : capacity(0), flow(0), tolerance(_tolerance) { }
1347 void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
1348 void setFlow(const FlowMap& _flow) { flow = &_flow; }
1350 bool operator[](const typename Graph::Edge& e) const {
1351 return tolerance.less((*flow)[e], (*capacity)[e]);
1355 template<typename Graph, typename Number,
1356 typename CapacityMap, typename FlowMap,
1357 typename Tolerance = Tolerance<Number> >
1358 class ResBackwardFilter {
1359 const CapacityMap* capacity;
1360 const FlowMap* flow;
1361 Tolerance tolerance;
1363 typedef typename Graph::Edge Key;
1366 ResBackwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
1367 const Tolerance& _tolerance = Tolerance())
1368 : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
1369 ResBackwardFilter(const Tolerance& _tolerance = Tolerance())
1370 : capacity(0), flow(0), tolerance(_tolerance) { }
1371 void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
1372 void setFlow(const FlowMap& _flow) { flow = &_flow; }
1373 bool operator[](const typename Graph::Edge& e) const {
1374 return tolerance.less(0, Number((*flow)[e]));
1379 ///\ingroup graph_adaptors
1381 ///\brief An adaptor for composing the residual
1382 ///graph for directed flow and circulation problems.
1384 ///An adaptor for composing the residual graph for directed flow and
1385 ///circulation problems. Let \f$ G=(V, A) \f$ be a directed graph
1386 ///and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
1387 ///be functions on the edge-set.
1389 ///In the appications of ResGraphAdaptor, \f$ f \f$ usually stands
1390 ///for a flow and \f$ c \f$ for a capacity function. Suppose that a
1391 ///graph instange \c g of type \c ListGraph implements \f$ G \f$.
1397 ///Then RevGraphAdaptor implements the graph structure with node-set
1398 /// \f$ V \f$ and edge-set \f$ A_{forward}\cup A_{backward} \f$,
1399 ///where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
1400 /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so called
1401 ///residual graph. When we take the union
1402 /// \f$ A_{forward}\cup A_{backward} \f$, multilicities are counted, i.e.
1403 ///if an edge is in both \f$ A_{forward} \f$ and \f$ A_{backward} \f$,
1404 ///then in the adaptor it appears twice. The following code shows how
1405 ///such an instance can be constructed.
1408 /// typedef ListGraph Graph;
1409 /// Graph::EdgeMap<int> f(g);
1410 /// Graph::EdgeMap<int> c(g);
1411 /// ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > ga(g);
1413 ///\author Marton Makai
1415 template<typename Graph, typename Number,
1416 typename CapacityMap, typename FlowMap,
1417 typename Tolerance = Tolerance<Number> >
1418 class ResGraphAdaptor :
1419 public EdgeSubGraphAdaptor<
1420 UndirGraphAdaptor<const Graph>,
1421 typename UndirGraphAdaptor<const Graph>::template CombinedEdgeMap<
1422 ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>,
1423 ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap> > > {
1426 typedef UndirGraphAdaptor<const Graph> UGraph;
1428 typedef ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>
1431 typedef ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap>
1434 typedef typename UGraph::
1435 template CombinedEdgeMap<ForwardFilter, BackwardFilter>
1438 typedef EdgeSubGraphAdaptor<UGraph, EdgeFilter> Parent;
1442 const CapacityMap* capacity;
1446 ForwardFilter forward_filter;
1447 BackwardFilter backward_filter;
1448 EdgeFilter edge_filter;
1450 void setCapacityMap(const CapacityMap& _capacity) {
1451 capacity=&_capacity;
1452 forward_filter.setCapacity(_capacity);
1453 backward_filter.setCapacity(_capacity);
1456 void setFlowMap(FlowMap& _flow) {
1458 forward_filter.setFlow(_flow);
1459 backward_filter.setFlow(_flow);
1464 /// \brief Constructor of the residual graph.
1466 /// Constructor of the residual graph. The parameters are the graph type,
1467 /// the flow map, the capacity map and a tolerance object.
1468 ResGraphAdaptor(const Graph& _graph, const CapacityMap& _capacity,
1469 FlowMap& _flow, const Tolerance& _tolerance = Tolerance())
1470 : Parent(), capacity(&_capacity), flow(&_flow), ugraph(_graph),
1471 forward_filter(_capacity, _flow, _tolerance),
1472 backward_filter(_capacity, _flow, _tolerance),
1473 edge_filter(forward_filter, backward_filter)
1475 Parent::setGraph(ugraph);
1476 Parent::setEdgeFilterMap(edge_filter);
1479 typedef typename Parent::Edge Edge;
1481 /// \brief Gives back the residual capacity of the edge.
1483 /// Gives back the residual capacity of the edge.
1484 Number rescap(const Edge& edge) const {
1485 if (UGraph::direction(edge)) {
1486 return (*capacity)[edge]-(*flow)[edge];
1488 return (*flow)[edge];
1492 /// \brief Augment on the given edge in the residual graph.
1494 /// Augment on the given edge in the residual graph. It increase
1495 /// or decrease the flow on the original edge depend on the direction
1496 /// of the residual edge.
1497 void augment(const Edge& e, Number a) const {
1498 if (UGraph::direction(e)) {
1499 flow->set(e, (*flow)[e] + a);
1501 flow->set(e, (*flow)[e] - a);
1505 /// \brief Returns the direction of the edge.
1507 /// Returns true when the edge is same oriented as the original edge.
1508 static bool forward(const Edge& e) {
1509 return UGraph::direction(e);
1512 /// \brief Returns the direction of the edge.
1514 /// Returns true when the edge is opposite oriented as the original edge.
1515 static bool backward(const Edge& e) {
1516 return !UGraph::direction(e);
1519 /// \brief Gives back the forward oriented residual edge.
1521 /// Gives back the forward oriented residual edge.
1522 static Edge forward(const typename Graph::Edge& e) {
1523 return UGraph::direct(e, true);
1526 /// \brief Gives back the backward oriented residual edge.
1528 /// Gives back the backward oriented residual edge.
1529 static Edge backward(const typename Graph::Edge& e) {
1530 return UGraph::direct(e, false);
1533 /// \brief Residual capacity map.
1535 /// In generic residual graphs the residual capacity can be obtained
1539 const ResGraphAdaptor* res_graph;
1541 typedef Number Value;
1543 ResCap(const ResGraphAdaptor& _res_graph)
1544 : res_graph(&_res_graph) {}
1546 Number operator[](const Edge& e) const {
1547 return res_graph->rescap(e);
1556 template <typename _Graph, typename FirstOutEdgesMap>
1557 class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
1559 typedef _Graph Graph;
1560 typedef GraphAdaptorBase<_Graph> Parent;
1562 FirstOutEdgesMap* first_out_edges;
1563 ErasingFirstGraphAdaptorBase() : Parent(),
1564 first_out_edges(0) { }
1566 void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1567 first_out_edges=&_first_out_edges;
1572 typedef typename Parent::Node Node;
1573 typedef typename Parent::Edge Edge;
1575 void firstOut(Edge& i, const Node& n) const {
1576 i=(*first_out_edges)[n];
1579 void erase(const Edge& e) const {
1583 first_out_edges->set(n, f);
1588 ///\ingroup graph_adaptors
1590 ///\brief For blocking flows.
1592 ///This graph adaptor is used for on-the-fly
1593 ///Dinits blocking flow computations.
1594 ///For each node, an out-edge is stored which is used when the
1596 ///OutEdgeIt& first(OutEdgeIt&, const Node&)
1600 ///\author Marton Makai
1602 template <typename _Graph, typename FirstOutEdgesMap>
1603 class ErasingFirstGraphAdaptor :
1604 public GraphAdaptorExtender<
1605 ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
1607 typedef _Graph Graph;
1608 typedef GraphAdaptorExtender<
1609 ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
1610 ErasingFirstGraphAdaptor(Graph& _graph,
1611 FirstOutEdgesMap& _first_out_edges) {
1613 setFirstOutEdgesMap(_first_out_edges);
1618 /// \brief Base class for split graph adaptor
1620 /// Base class of split graph adaptor. In most case you do not need to
1621 /// use it directly but the documented member functions of this class can
1622 /// be used with the SplitGraphAdaptor class.
1623 /// \sa SplitGraphAdaptor
1624 template <typename _Graph>
1625 class SplitGraphAdaptorBase
1626 : public GraphAdaptorBase<const _Graph> {
1629 typedef _Graph Graph;
1631 typedef GraphAdaptorBase<const _Graph> Parent;
1633 typedef typename Graph::Node GraphNode;
1634 typedef typename Graph::Edge GraphEdge;
1639 template <typename T> class NodeMap;
1640 template <typename T> class EdgeMap;
1643 class Node : public GraphNode {
1644 friend class SplitGraphAdaptorBase;
1645 template <typename T> friend class NodeMap;
1649 Node(GraphNode _node, bool _in_node)
1650 : GraphNode(_node), in_node(_in_node) {}
1655 Node(Invalid) : GraphNode(INVALID), in_node(true) {}
1657 bool operator==(const Node& node) const {
1658 return GraphNode::operator==(node) && in_node == node.in_node;
1661 bool operator!=(const Node& node) const {
1662 return !(*this == node);
1665 bool operator<(const Node& node) const {
1666 return GraphNode::operator<(node) ||
1667 (GraphNode::operator==(node) && in_node < node.in_node);
1672 friend class SplitGraphAdaptorBase;
1673 template <typename T> friend class EdgeMap;
1675 typedef BiVariant<GraphEdge, GraphNode> EdgeImpl;
1677 explicit Edge(const GraphEdge& edge) : item(edge) {}
1678 explicit Edge(const GraphNode& node) : item(node) {}
1684 Edge(Invalid) : item(GraphEdge(INVALID)) {}
1686 bool operator==(const Edge& edge) const {
1687 if (item.firstState()) {
1688 if (edge.item.firstState()) {
1689 return item.first() == edge.item.first();
1692 if (edge.item.secondState()) {
1693 return item.second() == edge.item.second();
1699 bool operator!=(const Edge& edge) const {
1700 return !(*this == edge);
1703 bool operator<(const Edge& edge) const {
1704 if (item.firstState()) {
1705 if (edge.item.firstState()) {
1706 return item.first() < edge.item.first();
1710 if (edge.item.secondState()) {
1711 return item.second() < edge.item.second();
1717 operator GraphEdge() const { return item.first(); }
1718 operator GraphNode() const { return item.second(); }
1722 void first(Node& node) const {
1723 Parent::first(node);
1724 node.in_node = true;
1727 void next(Node& node) const {
1729 node.in_node = false;
1731 node.in_node = true;
1736 void first(Edge& edge) const {
1737 edge.item.setSecond();
1738 Parent::first(edge.item.second());
1739 if (edge.item.second() == INVALID) {
1740 edge.item.setFirst();
1741 Parent::first(edge.item.first());
1745 void next(Edge& edge) const {
1746 if (edge.item.secondState()) {
1747 Parent::next(edge.item.second());
1748 if (edge.item.second() == INVALID) {
1749 edge.item.setFirst();
1750 Parent::first(edge.item.first());
1753 Parent::next(edge.item.first());
1757 void firstOut(Edge& edge, const Node& node) const {
1759 edge.item.setSecond(node);
1761 edge.item.setFirst();
1762 Parent::firstOut(edge.item.first(), node);
1766 void nextOut(Edge& edge) const {
1767 if (!edge.item.firstState()) {
1768 edge.item.setFirst(INVALID);
1770 Parent::nextOut(edge.item.first());
1774 void firstIn(Edge& edge, const Node& node) const {
1775 if (!node.in_node) {
1776 edge.item.setSecond(node);
1778 edge.item.setFirst();
1779 Parent::firstIn(edge.item.first(), node);
1783 void nextIn(Edge& edge) const {
1784 if (!edge.item.firstState()) {
1785 edge.item.setFirst(INVALID);
1787 Parent::nextIn(edge.item.first());
1791 Node source(const Edge& edge) const {
1792 if (edge.item.firstState()) {
1793 return Node(Parent::source(edge.item.first()), false);
1795 return Node(edge.item.second(), true);
1799 Node target(const Edge& edge) const {
1800 if (edge.item.firstState()) {
1801 return Node(Parent::target(edge.item.first()), true);
1803 return Node(edge.item.second(), false);
1807 int id(const Node& node) const {
1808 return (Parent::id(node) << 1) | (node.in_node ? 0 : 1);
1810 Node nodeFromId(int id) const {
1811 return Node(Parent::nodeFromId(id >> 1), (id & 1) == 0);
1813 int maxNodeId() const {
1814 return 2 * Parent::maxNodeId() + 1;
1817 int id(const Edge& edge) const {
1818 if (edge.item.firstState()) {
1819 return Parent::id(edge.item.first()) << 1;
1821 return (Parent::id(edge.item.second()) << 1) | 1;
1824 Edge edgeFromId(int id) const {
1825 if ((id & 1) == 0) {
1826 return Edge(Parent::edgeFromId(id >> 1));
1828 return Edge(Parent::nodeFromId(id >> 1));
1831 int maxEdgeId() const {
1832 return std::max(Parent::maxNodeId() << 1,
1833 (Parent::maxEdgeId() << 1) | 1);
1836 /// \brief Returns true when the node is in-node.
1838 /// Returns true when the node is in-node.
1839 static bool inNode(const Node& node) {
1840 return node.in_node;
1843 /// \brief Returns true when the node is out-node.
1845 /// Returns true when the node is out-node.
1846 static bool outNode(const Node& node) {
1847 return !node.in_node;
1850 /// \brief Returns true when the edge is edge in the original graph.
1852 /// Returns true when the edge is edge in the original graph.
1853 static bool origEdge(const Edge& edge) {
1854 return edge.item.firstState();
1857 /// \brief Returns true when the edge binds an in-node and an out-node.
1859 /// Returns true when the edge binds an in-node and an out-node.
1860 static bool bindEdge(const Edge& edge) {
1861 return edge.item.secondState();
1864 /// \brief Gives back the in-node created from the \c node.
1866 /// Gives back the in-node created from the \c node.
1867 static Node inNode(const GraphNode& node) {
1868 return Node(node, true);
1871 /// \brief Gives back the out-node created from the \c node.
1873 /// Gives back the out-node created from the \c node.
1874 static Node outNode(const GraphNode& node) {
1875 return Node(node, false);
1878 /// \brief Gives back the edge binds the two part of the node.
1880 /// Gives back the edge binds the two part of the node.
1881 static Edge edge(const GraphNode& node) {
1885 /// \brief Gives back the edge of the original edge.
1887 /// Gives back the edge of the original edge.
1888 static Edge edge(const GraphEdge& edge) {
1892 typedef True NodeNumTag;
1894 int nodeNum() const {
1895 return 2 * countNodes(*Parent::graph);
1898 typedef True EdgeNumTag;
1900 int edgeNum() const {
1901 return countEdges(*Parent::graph) + countNodes(*Parent::graph);
1904 typedef True FindEdgeTag;
1906 Edge findEdge(const Node& source, const Node& target,
1907 const Edge& prev = INVALID) const {
1908 if (inNode(source)) {
1909 if (outNode(target)) {
1910 if ((GraphNode&)source == (GraphNode&)target && prev == INVALID) {
1911 return Edge(source);
1915 if (inNode(target)) {
1916 return Edge(findEdge(*Parent::graph, source, target, prev));
1922 template <typename T>
1923 class NodeMap : public MapBase<Node, T> {
1924 typedef typename Parent::template NodeMap<T> NodeImpl;
1926 NodeMap(const SplitGraphAdaptorBase& _graph)
1927 : inNodeMap(_graph), outNodeMap(_graph) {}
1928 NodeMap(const SplitGraphAdaptorBase& _graph, const T& t)
1929 : inNodeMap(_graph, t), outNodeMap(_graph, t) {}
1931 void set(const Node& key, const T& val) {
1932 if (SplitGraphAdaptorBase::inNode(key)) { inNodeMap.set(key, val); }
1933 else {outNodeMap.set(key, val); }
1936 typename MapTraits<NodeImpl>::ReturnValue
1937 operator[](const Node& key) {
1938 if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; }
1939 else { return outNodeMap[key]; }
1942 typename MapTraits<NodeImpl>::ConstReturnValue
1943 operator[](const Node& key) const {
1944 if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; }
1945 else { return outNodeMap[key]; }
1949 NodeImpl inNodeMap, outNodeMap;
1952 template <typename T>
1953 class EdgeMap : public MapBase<Edge, T> {
1954 typedef typename Parent::template EdgeMap<T> EdgeMapImpl;
1955 typedef typename Parent::template NodeMap<T> NodeMapImpl;
1958 EdgeMap(const SplitGraphAdaptorBase& _graph)
1959 : edge_map(_graph), node_map(_graph) {}
1960 EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t)
1961 : edge_map(_graph, t), node_map(_graph, t) {}
1963 void set(const Edge& key, const T& val) {
1964 if (SplitGraphAdaptorBase::origEdge(key)) {
1965 edge_map.set(key.item.first(), val);
1967 node_map.set(key.item.second(), val);
1971 typename MapTraits<EdgeMapImpl>::ReturnValue
1972 operator[](const Edge& key) {
1973 if (SplitGraphAdaptorBase::origEdge(key)) {
1974 return edge_map[key.item.first()];
1976 return node_map[key.item.second()];
1980 typename MapTraits<EdgeMapImpl>::ConstReturnValue
1981 operator[](const Edge& key) const {
1982 if (SplitGraphAdaptorBase::origEdge(key)) {
1983 return edge_map[key.item.first()];
1985 return node_map[key.item.second()];
1990 typename Parent::template EdgeMap<T> edge_map;
1991 typename Parent::template NodeMap<T> node_map;
1997 template <typename _Graph, typename NodeEnable = void,
1998 typename EdgeEnable = void>
1999 class AlterableSplitGraphAdaptor
2000 : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
2003 typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
2004 typedef _Graph Graph;
2006 typedef typename Graph::Node GraphNode;
2007 typedef typename Graph::Node GraphEdge;
2011 AlterableSplitGraphAdaptor() : Parent() {}
2015 typedef InvalidType NodeNotifier;
2016 typedef InvalidType EdgeNotifier;
2020 template <typename _Graph, typename EdgeEnable>
2021 class AlterableSplitGraphAdaptor<
2023 typename enable_if<typename _Graph::NodeNotifier::Notifier>::type,
2025 : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
2028 typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
2029 typedef _Graph Graph;
2031 typedef typename Graph::Node GraphNode;
2032 typedef typename Graph::Edge GraphEdge;
2034 typedef typename Parent::Node Node;
2035 typedef typename Parent::Edge Edge;
2039 AlterableSplitGraphAdaptor()
2040 : Parent(), node_notifier(*this), node_notifier_proxy(*this) {}
2042 void setGraph(_Graph& graph) {
2043 Parent::setGraph(graph);
2044 node_notifier_proxy.setNotifier(graph.getNotifier(GraphNode()));
2049 ~AlterableSplitGraphAdaptor() {
2050 node_notifier.clear();
2053 typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier;
2054 typedef InvalidType EdgeNotifier;
2056 NodeNotifier& getNotifier(Node) const { return node_notifier; }
2060 class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase {
2063 typedef typename Graph::NodeNotifier::ObserverBase Parent;
2064 typedef AlterableSplitGraphAdaptor AdaptorBase;
2066 NodeNotifierProxy(const AdaptorBase& _adaptor)
2067 : Parent(), adaptor(&_adaptor) {
2070 virtual ~NodeNotifierProxy() {
2071 if (Parent::attached()) {
2076 void setNotifier(typename Graph::NodeNotifier& graph_notifier) {
2077 Parent::attach(graph_notifier);
2083 virtual void add(const GraphNode& gn) {
2084 std::vector<Node> nodes;
2085 nodes.push_back(AdaptorBase::Parent::inNode(gn));
2086 nodes.push_back(AdaptorBase::Parent::outNode(gn));
2087 adaptor->getNotifier(Node()).add(nodes);
2090 virtual void add(const std::vector<GraphNode>& gn) {
2091 std::vector<Node> nodes;
2092 for (int i = 0; i < (int)gn.size(); ++i) {
2093 nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2094 nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2096 adaptor->getNotifier(Node()).add(nodes);
2099 virtual void erase(const GraphNode& gn) {
2100 std::vector<Node> nodes;
2101 nodes.push_back(AdaptorBase::Parent::inNode(gn));
2102 nodes.push_back(AdaptorBase::Parent::outNode(gn));
2103 adaptor->getNotifier(Node()).erase(nodes);
2106 virtual void erase(const std::vector<GraphNode>& gn) {
2107 std::vector<Node> nodes;
2108 for (int i = 0; i < (int)gn.size(); ++i) {
2109 nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2110 nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2112 adaptor->getNotifier(Node()).erase(nodes);
2114 virtual void build() {
2115 adaptor->getNotifier(Node()).build();
2117 virtual void clear() {
2118 adaptor->getNotifier(Node()).clear();
2121 const AdaptorBase* adaptor;
2125 mutable NodeNotifier node_notifier;
2127 NodeNotifierProxy node_notifier_proxy;
2131 template <typename _Graph>
2132 class AlterableSplitGraphAdaptor<
2134 typename enable_if<typename _Graph::NodeNotifier::Notifier>::type,
2135 typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type>
2136 : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
2139 typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
2140 typedef _Graph Graph;
2142 typedef typename Graph::Node GraphNode;
2143 typedef typename Graph::Edge GraphEdge;
2145 typedef typename Parent::Node Node;
2146 typedef typename Parent::Edge Edge;
2150 AlterableSplitGraphAdaptor()
2151 : Parent(), node_notifier(*this), edge_notifier(*this),
2152 node_notifier_proxy(*this), edge_notifier_proxy(*this) {}
2154 void setGraph(_Graph& graph) {
2155 Parent::setGraph(graph);
2156 node_notifier_proxy.setNotifier(graph.getNotifier(GraphNode()));
2157 edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge()));
2162 ~AlterableSplitGraphAdaptor() {
2163 node_notifier.clear();
2164 edge_notifier.clear();
2167 typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier;
2168 typedef AlterationNotifier<AlterableSplitGraphAdaptor, Edge> EdgeNotifier;
2170 NodeNotifier& getNotifier(Node) const { return node_notifier; }
2171 EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
2175 class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase {
2178 typedef typename Graph::NodeNotifier::ObserverBase Parent;
2179 typedef AlterableSplitGraphAdaptor AdaptorBase;
2181 NodeNotifierProxy(const AdaptorBase& _adaptor)
2182 : Parent(), adaptor(&_adaptor) {
2185 virtual ~NodeNotifierProxy() {
2186 if (Parent::attached()) {
2191 void setNotifier(typename Graph::NodeNotifier& graph_notifier) {
2192 Parent::attach(graph_notifier);
2198 virtual void add(const GraphNode& gn) {
2199 std::vector<Node> nodes;
2200 nodes.push_back(AdaptorBase::Parent::inNode(gn));
2201 nodes.push_back(AdaptorBase::Parent::outNode(gn));
2202 adaptor->getNotifier(Node()).add(nodes);
2203 adaptor->getNotifier(Edge()).add(AdaptorBase::Parent::edge(gn));
2205 virtual void add(const std::vector<GraphNode>& gn) {
2206 std::vector<Node> nodes;
2207 std::vector<Edge> edges;
2208 for (int i = 0; i < (int)gn.size(); ++i) {
2209 edges.push_back(AdaptorBase::Parent::edge(gn[i]));
2210 nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2211 nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2213 adaptor->getNotifier(Node()).add(nodes);
2214 adaptor->getNotifier(Edge()).add(edges);
2216 virtual void erase(const GraphNode& gn) {
2217 adaptor->getNotifier(Edge()).erase(AdaptorBase::Parent::edge(gn));
2218 std::vector<Node> nodes;
2219 nodes.push_back(AdaptorBase::Parent::inNode(gn));
2220 nodes.push_back(AdaptorBase::Parent::outNode(gn));
2221 adaptor->getNotifier(Node()).erase(nodes);
2223 virtual void erase(const std::vector<GraphNode>& gn) {
2224 std::vector<Node> nodes;
2225 std::vector<Edge> edges;
2226 for (int i = 0; i < (int)gn.size(); ++i) {
2227 edges.push_back(AdaptorBase::Parent::edge(gn[i]));
2228 nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2229 nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2231 adaptor->getNotifier(Edge()).erase(edges);
2232 adaptor->getNotifier(Node()).erase(nodes);
2234 virtual void build() {
2235 std::vector<Edge> edges;
2236 const typename Parent::Notifier* notifier = Parent::getNotifier();
2238 for (notifier->first(it); it != INVALID; notifier->next(it)) {
2239 edges.push_back(AdaptorBase::Parent::edge(it));
2241 adaptor->getNotifier(Node()).build();
2242 adaptor->getNotifier(Edge()).add(edges);
2244 virtual void clear() {
2245 std::vector<Edge> edges;
2246 const typename Parent::Notifier* notifier = Parent::getNotifier();
2248 for (notifier->first(it); it != INVALID; notifier->next(it)) {
2249 edges.push_back(AdaptorBase::Parent::edge(it));
2251 adaptor->getNotifier(Edge()).erase(edges);
2252 adaptor->getNotifier(Node()).clear();
2255 const AdaptorBase* adaptor;
2258 class EdgeNotifierProxy : public Graph::EdgeNotifier::ObserverBase {
2261 typedef typename Graph::EdgeNotifier::ObserverBase Parent;
2262 typedef AlterableSplitGraphAdaptor AdaptorBase;
2264 EdgeNotifierProxy(const AdaptorBase& _adaptor)
2265 : Parent(), adaptor(&_adaptor) {
2268 virtual ~EdgeNotifierProxy() {
2269 if (Parent::attached()) {
2274 void setNotifier(typename Graph::EdgeNotifier& graph_notifier) {
2275 Parent::attach(graph_notifier);
2281 virtual void add(const GraphEdge& ge) {
2282 adaptor->getNotifier(Edge()).add(AdaptorBase::edge(ge));
2284 virtual void add(const std::vector<GraphEdge>& ge) {
2285 std::vector<Edge> edges;
2286 for (int i = 0; i < (int)ge.size(); ++i) {
2287 edges.push_back(AdaptorBase::edge(ge[i]));
2289 adaptor->getNotifier(Edge()).add(edges);
2291 virtual void erase(const GraphEdge& ge) {
2292 adaptor->getNotifier(Edge()).erase(AdaptorBase::edge(ge));
2294 virtual void erase(const std::vector<GraphEdge>& ge) {
2295 std::vector<Edge> edges;
2296 for (int i = 0; i < (int)ge.size(); ++i) {
2297 edges.push_back(AdaptorBase::edge(ge[i]));
2299 adaptor->getNotifier(Edge()).erase(edges);
2301 virtual void build() {
2302 std::vector<Edge> edges;
2303 const typename Parent::Notifier* notifier = Parent::getNotifier();
2305 for (notifier->first(it); it != INVALID; notifier->next(it)) {
2306 edges.push_back(AdaptorBase::Parent::edge(it));
2308 adaptor->getNotifier(Edge()).add(edges);
2310 virtual void clear() {
2311 std::vector<Edge> edges;
2312 const typename Parent::Notifier* notifier = Parent::getNotifier();
2314 for (notifier->first(it); it != INVALID; notifier->next(it)) {
2315 edges.push_back(AdaptorBase::Parent::edge(it));
2317 adaptor->getNotifier(Edge()).erase(edges);
2320 const AdaptorBase* adaptor;
2324 mutable NodeNotifier node_notifier;
2325 mutable EdgeNotifier edge_notifier;
2327 NodeNotifierProxy node_notifier_proxy;
2328 EdgeNotifierProxy edge_notifier_proxy;
2332 /// \ingroup graph_adaptors
2334 /// \brief Split graph adaptor class
2336 /// This is an graph adaptor which splits all node into an in-node
2337 /// and an out-node. Formaly, the adaptor replaces each \f$ u \f$
2338 /// node in the graph with two node, \f$ u_{in} \f$ node and
2339 /// \f$ u_{out} \f$ node. If there is an \f$ (v, u) \f$ edge in the
2340 /// original graph the new target of the edge will be \f$ u_{in} \f$ and
2341 /// similarly the source of the original \f$ (u, v) \f$ edge will be
2342 /// \f$ u_{out} \f$. The adaptor will add for each node in the
2343 /// original graph an additional edge which will connect
2344 /// \f$ (u_{in}, u_{out}) \f$.
2346 /// The aim of this class is to run algorithm with node costs if the
2347 /// algorithm can use directly just edge costs. In this case we should use
2348 /// a \c SplitGraphAdaptor and set the node cost of the graph to the
2349 /// bind edge in the adapted graph.
2351 /// By example a maximum flow algoritm can compute how many edge
2352 /// disjoint paths are in the graph. But we would like to know how
2353 /// many node disjoint paths are in the graph. First we have to
2354 /// adapt the graph with the \c SplitGraphAdaptor. Then run the flow
2355 /// algorithm on the adapted graph. The bottleneck of the flow will
2356 /// be the bind edges which bounds the flow with the count of the
2357 /// node disjoint paths.
2361 /// typedef SplitGraphAdaptor<SmartGraph> SGraph;
2363 /// SGraph sgraph(graph);
2365 /// typedef ConstMap<SGraph::Edge, int> SCapacity;
2366 /// SCapacity scapacity(1);
2368 /// SGraph::EdgeMap<int> sflow(sgraph);
2370 /// Preflow<SGraph, int, SCapacity>
2371 /// spreflow(sgraph, SGraph::outNode(source),SGraph::inNode(target),
2372 /// scapacity, sflow);
2378 /// The result of the mamixum flow on the original graph
2379 /// shows the next figure:
2381 /// \image html edge_disjoint.png
2382 /// \image latex edge_disjoint.eps "Edge disjoint paths" width=\textwidth
2384 /// And the maximum flow on the adapted graph:
2386 /// \image html node_disjoint.png
2387 /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth
2389 /// The second solution contains just 3 disjoint paths while the first 4.
2390 /// The full code can be found in the \ref disjoint_paths.cc demo file.
2392 /// This graph adaptor is fully conform to the
2393 /// \ref concept::StaticGraph "StaticGraph" concept and
2394 /// contains some additional member functions and types. The
2395 /// documentation of some member functions may be found just in the
2396 /// SplitGraphAdaptorBase class.
2398 /// \sa SplitGraphAdaptorBase
2399 template <typename _Graph>
2400 class SplitGraphAdaptor : public AlterableSplitGraphAdaptor<_Graph> {
2402 typedef AlterableSplitGraphAdaptor<_Graph> Parent;
2404 typedef typename Parent::Node Node;
2405 typedef typename Parent::Edge Edge;
2407 /// \brief Constructor of the adaptor.
2409 /// Constructor of the adaptor.
2410 SplitGraphAdaptor(_Graph& graph) {
2411 Parent::setGraph(graph);
2414 /// \brief NodeMap combined from two original NodeMap
2416 /// This class adapt two of the original graph NodeMap to
2417 /// get a node map on the adapted graph.
2418 template <typename InNodeMap, typename OutNodeMap>
2419 class CombinedNodeMap {
2423 typedef typename InNodeMap::Value Value;
2425 /// \brief Constructor
2428 CombinedNodeMap(InNodeMap& _inNodeMap, OutNodeMap& _outNodeMap)
2429 : inNodeMap(_inNodeMap), outNodeMap(_outNodeMap) {}
2431 /// \brief The subscript operator.
2433 /// The subscript operator.
2434 Value& operator[](const Key& key) {
2435 if (Parent::inNode(key)) {
2436 return inNodeMap[key];
2438 return outNodeMap[key];
2442 /// \brief The const subscript operator.
2444 /// The const subscript operator.
2445 Value operator[](const Key& key) const {
2446 if (Parent::inNode(key)) {
2447 return inNodeMap[key];
2449 return outNodeMap[key];
2453 /// \brief The setter function of the map.
2455 /// The setter function of the map.
2456 void set(const Key& key, const Value& value) {
2457 if (Parent::inNode(key)) {
2458 inNodeMap.set(key, value);
2460 outNodeMap.set(key, value);
2466 InNodeMap& inNodeMap;
2467 OutNodeMap& outNodeMap;
2472 /// \brief Just gives back a combined node map.
2474 /// Just gives back a combined node map.
2475 template <typename InNodeMap, typename OutNodeMap>
2476 static CombinedNodeMap<InNodeMap, OutNodeMap>
2477 combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
2478 return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
2481 template <typename InNodeMap, typename OutNodeMap>
2482 static CombinedNodeMap<const InNodeMap, OutNodeMap>
2483 combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
2484 return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
2487 template <typename InNodeMap, typename OutNodeMap>
2488 static CombinedNodeMap<InNodeMap, const OutNodeMap>
2489 combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
2490 return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
2493 template <typename InNodeMap, typename OutNodeMap>
2494 static CombinedNodeMap<const InNodeMap, const OutNodeMap>
2495 combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
2496 return CombinedNodeMap<const InNodeMap,
2497 const OutNodeMap>(in_map, out_map);
2500 /// \brief EdgeMap combined from an original EdgeMap and NodeMap
2502 /// This class adapt an original graph EdgeMap and NodeMap to
2503 /// get an edge map on the adapted graph.
2504 template <typename GraphEdgeMap, typename GraphNodeMap>
2505 class CombinedEdgeMap
2506 : public MapBase<Edge, typename GraphEdgeMap::Value> {
2508 typedef MapBase<Edge, typename GraphEdgeMap::Value> Parent;
2510 typedef typename Parent::Key Key;
2511 typedef typename Parent::Value Value;
2513 /// \brief Constructor
2516 CombinedEdgeMap(GraphEdgeMap& _edge_map, GraphNodeMap& _node_map)
2517 : edge_map(_edge_map), node_map(_node_map) {}
2519 /// \brief The subscript operator.
2521 /// The subscript operator.
2522 void set(const Edge& edge, const Value& val) {
2523 if (Parent::origEdge(edge)) {
2524 edge_map.set(edge, val);
2526 node_map.set(edge, val);
2530 /// \brief The const subscript operator.
2532 /// The const subscript operator.
2533 Value operator[](const Key& edge) const {
2534 if (Parent::origEdge(edge)) {
2535 return edge_map[edge];
2537 return node_map[edge];
2541 /// \brief The const subscript operator.
2543 /// The const subscript operator.
2544 Value& operator[](const Key& edge) {
2545 if (Parent::origEdge(edge)) {
2546 return edge_map[edge];
2548 return node_map[edge];
2553 GraphEdgeMap& edge_map;
2554 GraphNodeMap& node_map;
2557 /// \brief Just gives back a combined edge map.
2559 /// Just gives back a combined edge map.
2560 template <typename GraphEdgeMap, typename GraphNodeMap>
2561 static CombinedEdgeMap<GraphEdgeMap, GraphNodeMap>
2562 combinedEdgeMap(GraphEdgeMap& edge_map, GraphNodeMap& node_map) {
2563 return CombinedEdgeMap<GraphEdgeMap, GraphNodeMap>(edge_map, node_map);
2566 template <typename GraphEdgeMap, typename GraphNodeMap>
2567 static CombinedEdgeMap<const GraphEdgeMap, GraphNodeMap>
2568 combinedEdgeMap(const GraphEdgeMap& edge_map, GraphNodeMap& node_map) {
2569 return CombinedEdgeMap<const GraphEdgeMap,
2570 GraphNodeMap>(edge_map, node_map);
2573 template <typename GraphEdgeMap, typename GraphNodeMap>
2574 static CombinedEdgeMap<GraphEdgeMap, const GraphNodeMap>
2575 combinedEdgeMap(GraphEdgeMap& edge_map, const GraphNodeMap& node_map) {
2576 return CombinedEdgeMap<GraphEdgeMap,
2577 const GraphNodeMap>(edge_map, node_map);
2580 template <typename GraphEdgeMap, typename GraphNodeMap>
2581 static CombinedEdgeMap<const GraphEdgeMap, const GraphNodeMap>
2582 combinedEdgeMap(const GraphEdgeMap& edge_map,
2583 const GraphNodeMap& node_map) {
2584 return CombinedEdgeMap<const GraphEdgeMap,
2585 const GraphNodeMap>(edge_map, node_map);
2593 #endif //LEMON_GRAPH_ADAPTOR_H