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
44 ///\ingroup graph_adaptors
46 ///Base type for the Graph Adaptors
48 ///This is the base type for most of LEMON graph adaptors.
49 ///This class implements a trivial graph adaptor i.e. it only wraps the
50 ///functions and types of the graph. The purpose of this class is to
51 ///make easier implementing graph adaptors. E.g. if an adaptor is
52 ///considered which differs from the wrapped graph only in some of its
53 ///functions or types, then it can be derived from GraphAdaptor,
55 ///differences should be implemented.
57 ///author Marton Makai
58 template<typename _Graph>
59 class GraphAdaptorBase {
62 typedef GraphAdaptorBase Adaptor;
63 typedef Graph ParentGraph;
67 GraphAdaptorBase() : graph(0) { }
68 void setGraph(Graph& _graph) { graph=&_graph; }
71 GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
73 typedef typename Graph::Node Node;
74 typedef typename Graph::Edge Edge;
76 void first(Node& i) const { graph->first(i); }
77 void first(Edge& i) const { graph->first(i); }
78 void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
79 void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
81 void next(Node& i) const { graph->next(i); }
82 void next(Edge& i) const { graph->next(i); }
83 void nextIn(Edge& i) const { graph->nextIn(i); }
84 void nextOut(Edge& i) const { graph->nextOut(i); }
86 Node source(const Edge& e) const { return graph->source(e); }
87 Node target(const Edge& e) const { return graph->target(e); }
89 typedef NodeNumTagIndicator<Graph> NodeNumTag;
90 int nodeNum() const { return graph->nodeNum(); }
92 typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
93 int edgeNum() const { return graph->edgeNum(); }
95 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
96 Edge findEdge(const Node& source, const Node& target,
97 const Edge& prev = INVALID) {
98 return graph->findEdge(source, target, prev);
101 Node addNode() const {
102 return Node(graph->addNode());
105 Edge addEdge(const Node& source, const Node& target) const {
106 return Edge(graph->addEdge(source, target));
109 void erase(const Node& i) const { graph->erase(i); }
110 void erase(const Edge& i) const { graph->erase(i); }
112 void clear() const { graph->clear(); }
114 int id(const Node& v) const { return graph->id(v); }
115 int id(const Edge& e) const { return graph->id(e); }
117 Node fromNodeId(int id) const {
118 return graph->fromNodeId(id);
121 Edge fromEdgeId(int id) const {
122 return graph->fromEdgeId(id);
125 int maxNodeId() const {
126 return graph->maxNodeId();
129 int maxEdgeId() const {
130 return graph->maxEdgeId();
133 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
135 NodeNotifier& getNotifier(Node) const {
136 return graph->getNotifier(Node());
139 typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
141 EdgeNotifier& getNotifier(Edge) const {
142 return graph->getNotifier(Edge());
145 template <typename _Value>
146 class NodeMap : public Graph::template NodeMap<_Value> {
149 typedef typename Graph::template NodeMap<_Value> Parent;
151 explicit NodeMap(const Adaptor& ga)
152 : Parent(*ga.graph) {}
154 NodeMap(const Adaptor& ga, const _Value& value)
155 : Parent(*ga.graph, value) { }
157 NodeMap& operator=(const NodeMap& cmap) {
158 return operator=<NodeMap>(cmap);
161 template <typename CMap>
162 NodeMap& operator=(const CMap& cmap) {
163 Parent::operator=(cmap);
169 template <typename _Value>
170 class EdgeMap : public Graph::template EdgeMap<_Value> {
173 typedef typename Graph::template EdgeMap<_Value> Parent;
175 explicit EdgeMap(const Adaptor& ga)
176 : Parent(*ga.graph) {}
178 EdgeMap(const Adaptor& ga, const _Value& value)
179 : Parent(*ga.graph, value) {}
181 EdgeMap& operator=(const EdgeMap& cmap) {
182 return operator=<EdgeMap>(cmap);
185 template <typename CMap>
186 EdgeMap& operator=(const CMap& cmap) {
187 Parent::operator=(cmap);
195 template <typename _Graph>
197 public GraphAdaptorExtender<GraphAdaptorBase<_Graph> > {
199 typedef _Graph Graph;
200 typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent;
202 GraphAdaptor() : Parent() { }
205 explicit GraphAdaptor(Graph& _graph) { setGraph(_graph); }
208 /// \brief Just gives back a graph adaptor
210 /// Just gives back a graph adaptor which
211 /// should be provide original graph
212 template<typename Graph>
213 GraphAdaptor<const Graph>
214 graphAdaptor(const Graph& graph) {
215 return GraphAdaptor<const Graph>(graph);
219 template <typename _Graph>
220 class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
222 typedef _Graph Graph;
223 typedef GraphAdaptorBase<_Graph> Parent;
225 RevGraphAdaptorBase() : Parent() { }
227 typedef typename Parent::Node Node;
228 typedef typename Parent::Edge Edge;
230 void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
231 void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
233 void nextIn(Edge& i) const { Parent::nextOut(i); }
234 void nextOut(Edge& i) const { Parent::nextIn(i); }
236 Node source(const Edge& e) const { return Parent::target(e); }
237 Node target(const Edge& e) const { return Parent::source(e); }
239 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
240 Edge findEdge(const Node& source, const Node& target,
241 const Edge& prev = INVALID) {
242 return Parent::findEdge(target, source, prev);
248 ///\brief A graph adaptor which reverses the orientation of the edges.
249 ///\ingroup graph_adaptors
251 /// If \c g is defined as
257 /// RevGraphAdaptor<ListGraph> ga(g);
259 /// implements the graph obtained from \c g by
260 /// reversing the orientation of its edges.
261 template<typename _Graph>
262 class RevGraphAdaptor :
263 public GraphAdaptorExtender<RevGraphAdaptorBase<_Graph> > {
265 typedef _Graph Graph;
266 typedef GraphAdaptorExtender<
267 RevGraphAdaptorBase<_Graph> > Parent;
269 RevGraphAdaptor() { }
271 explicit RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
274 /// \brief Just gives back a reverse graph adaptor
276 /// Just gives back a reverse graph adaptor
277 template<typename Graph>
278 RevGraphAdaptor<const Graph>
279 revGraphAdaptor(const Graph& graph) {
280 return RevGraphAdaptor<const Graph>(graph);
283 template <typename _Graph, typename NodeFilterMap,
284 typename EdgeFilterMap, bool checked = true>
285 class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
287 typedef _Graph Graph;
288 typedef SubGraphAdaptorBase Adaptor;
289 typedef GraphAdaptorBase<_Graph> Parent;
291 NodeFilterMap* node_filter_map;
292 EdgeFilterMap* edge_filter_map;
293 SubGraphAdaptorBase() : Parent(),
294 node_filter_map(0), edge_filter_map(0) { }
296 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
297 node_filter_map=&_node_filter_map;
299 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
300 edge_filter_map=&_edge_filter_map;
305 typedef typename Parent::Node Node;
306 typedef typename Parent::Edge Edge;
308 void first(Node& i) const {
310 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
313 void first(Edge& i) const {
315 while (i!=INVALID && (!(*edge_filter_map)[i]
316 || !(*node_filter_map)[Parent::source(i)]
317 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
320 void firstIn(Edge& i, const Node& n) const {
321 Parent::firstIn(i, n);
322 while (i!=INVALID && (!(*edge_filter_map)[i]
323 || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
326 void firstOut(Edge& i, const Node& n) const {
327 Parent::firstOut(i, n);
328 while (i!=INVALID && (!(*edge_filter_map)[i]
329 || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
332 void next(Node& i) const {
334 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
337 void next(Edge& i) const {
339 while (i!=INVALID && (!(*edge_filter_map)[i]
340 || !(*node_filter_map)[Parent::source(i)]
341 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
344 void nextIn(Edge& i) const {
346 while (i!=INVALID && (!(*edge_filter_map)[i]
347 || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
350 void nextOut(Edge& i) const {
352 while (i!=INVALID && (!(*edge_filter_map)[i]
353 || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
358 /// This function hides \c n in the graph, i.e. the iteration
359 /// jumps over it. This is done by simply setting the value of \c n
360 /// to be false in the corresponding node-map.
361 void hide(const Node& n) const { node_filter_map->set(n, false); }
365 /// This function hides \c e in the graph, i.e. the iteration
366 /// jumps over it. This is done by simply setting the value of \c e
367 /// to be false in the corresponding edge-map.
368 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
372 /// The value of \c n is set to be true in the node-map which stores
373 /// hide information. If \c n was hidden previuosly, then it is shown
375 void unHide(const Node& n) const { node_filter_map->set(n, true); }
379 /// The value of \c e is set to be true in the edge-map which stores
380 /// hide information. If \c e was hidden previuosly, then it is shown
382 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
384 /// Returns true if \c n is hidden.
388 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
390 /// Returns true if \c n is hidden.
394 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
396 typedef False NodeNumTag;
397 typedef False EdgeNumTag;
399 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
400 Edge findEdge(const Node& source, const Node& target,
401 const Edge& prev = INVALID) {
402 if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
405 Edge edge = Parent::findEdge(source, target, prev);
406 while (edge != INVALID && !(*edge_filter_map)[edge]) {
407 edge = Parent::findEdge(source, target, edge);
412 template <typename _Value>
414 : public SubMapExtender<Adaptor,
415 typename Parent::template NodeMap<_Value> >
418 typedef Adaptor Graph;
419 typedef SubMapExtender<Adaptor, typename Parent::
420 template NodeMap<_Value> > Parent;
422 NodeMap(const Graph& graph)
424 NodeMap(const Graph& graph, const _Value& value)
425 : Parent(graph, value) {}
427 NodeMap& operator=(const NodeMap& cmap) {
428 return operator=<NodeMap>(cmap);
431 template <typename CMap>
432 NodeMap& operator=(const CMap& cmap) {
433 Parent::operator=(cmap);
438 template <typename _Value>
440 : public SubMapExtender<Adaptor,
441 typename Parent::template EdgeMap<_Value> >
444 typedef Adaptor Graph;
445 typedef SubMapExtender<Adaptor, typename Parent::
446 template EdgeMap<_Value> > Parent;
448 EdgeMap(const Graph& graph)
450 EdgeMap(const Graph& graph, const _Value& value)
451 : Parent(graph, value) {}
453 EdgeMap& operator=(const EdgeMap& cmap) {
454 return operator=<EdgeMap>(cmap);
457 template <typename CMap>
458 EdgeMap& operator=(const CMap& cmap) {
459 Parent::operator=(cmap);
466 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
467 class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
468 : public GraphAdaptorBase<_Graph> {
470 typedef _Graph Graph;
471 typedef SubGraphAdaptorBase Adaptor;
472 typedef GraphAdaptorBase<_Graph> Parent;
474 NodeFilterMap* node_filter_map;
475 EdgeFilterMap* edge_filter_map;
476 SubGraphAdaptorBase() : Parent(),
477 node_filter_map(0), edge_filter_map(0) { }
479 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
480 node_filter_map=&_node_filter_map;
482 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
483 edge_filter_map=&_edge_filter_map;
488 typedef typename Parent::Node Node;
489 typedef typename Parent::Edge Edge;
491 void first(Node& i) const {
493 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
496 void first(Edge& i) const {
498 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
501 void firstIn(Edge& i, const Node& n) const {
502 Parent::firstIn(i, n);
503 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
506 void firstOut(Edge& i, const Node& n) const {
507 Parent::firstOut(i, n);
508 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
511 void next(Node& i) const {
513 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
515 void next(Edge& i) const {
517 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
519 void nextIn(Edge& i) const {
521 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
524 void nextOut(Edge& i) const {
526 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
531 /// This function hides \c n in the graph, i.e. the iteration
532 /// jumps over it. This is done by simply setting the value of \c n
533 /// to be false in the corresponding node-map.
534 void hide(const Node& n) const { node_filter_map->set(n, false); }
538 /// This function hides \c e in the graph, i.e. the iteration
539 /// jumps over it. This is done by simply setting the value of \c e
540 /// to be false in the corresponding edge-map.
541 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
545 /// The value of \c n is set to be true in the node-map which stores
546 /// hide information. If \c n was hidden previuosly, then it is shown
548 void unHide(const Node& n) const { node_filter_map->set(n, true); }
552 /// The value of \c e is set to be true in the edge-map which stores
553 /// hide information. If \c e was hidden previuosly, then it is shown
555 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
557 /// Returns true if \c n is hidden.
561 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
563 /// Returns true if \c n is hidden.
567 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
569 typedef False NodeNumTag;
570 typedef False EdgeNumTag;
572 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
573 Edge findEdge(const Node& source, const Node& target,
574 const Edge& prev = INVALID) {
575 if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
578 Edge edge = Parent::findEdge(source, target, prev);
579 while (edge != INVALID && !(*edge_filter_map)[edge]) {
580 edge = Parent::findEdge(source, target, edge);
585 template <typename _Value>
587 : public SubMapExtender<Adaptor,
588 typename Parent::template NodeMap<_Value> >
591 typedef Adaptor Graph;
592 typedef SubMapExtender<Adaptor, typename Parent::
593 template NodeMap<_Value> > Parent;
595 NodeMap(const Graph& graph)
597 NodeMap(const Graph& graph, const _Value& value)
598 : Parent(graph, value) {}
600 NodeMap& operator=(const NodeMap& cmap) {
601 return operator=<NodeMap>(cmap);
604 template <typename CMap>
605 NodeMap& operator=(const CMap& cmap) {
606 Parent::operator=(cmap);
611 template <typename _Value>
613 : public SubMapExtender<Adaptor,
614 typename Parent::template EdgeMap<_Value> >
617 typedef Adaptor Graph;
618 typedef SubMapExtender<Adaptor, typename Parent::
619 template EdgeMap<_Value> > Parent;
621 EdgeMap(const Graph& graph)
623 EdgeMap(const Graph& graph, const _Value& value)
624 : Parent(graph, value) {}
626 EdgeMap& operator=(const EdgeMap& cmap) {
627 return operator=<EdgeMap>(cmap);
630 template <typename CMap>
631 EdgeMap& operator=(const CMap& cmap) {
632 Parent::operator=(cmap);
639 /// \brief A graph adaptor for hiding nodes and edges from a graph.
640 /// \ingroup graph_adaptors
642 /// SubGraphAdaptor shows the graph with filtered node-set and
643 /// edge-set. If the \c checked parameter is true then it filters the edgeset
644 /// to do not get invalid edges without source or target.
645 /// Let \f$ G=(V, A) \f$ be a directed graph
646 /// and suppose that the graph instance \c g of type ListGraph
647 /// implements \f$ G \f$.
648 /// Let moreover \f$ b_V \f$ and \f$ b_A \f$ be bool-valued functions resp.
649 /// on the node-set and edge-set.
650 /// SubGraphAdaptor<...>::NodeIt iterates
651 /// on the node-set \f$ \{v\in V : b_V(v)=true\} \f$ and
652 /// SubGraphAdaptor<...>::EdgeIt iterates
653 /// on the edge-set \f$ \{e\in A : b_A(e)=true\} \f$. Similarly,
654 /// SubGraphAdaptor<...>::OutEdgeIt and
655 /// SubGraphAdaptor<...>::InEdgeIt iterates
656 /// only on edges leaving and entering a specific node which have true value.
658 /// If the \c checked template parameter is false then we have to note that
659 /// the node-iterator cares only the filter on the node-set, and the
660 /// edge-iterator cares only the filter on the edge-set.
661 /// This way the edge-map
662 /// should filter all edges which's source or target is filtered by the
665 /// typedef ListGraph Graph;
667 /// typedef Graph::Node Node;
668 /// typedef Graph::Edge Edge;
669 /// Node u=g.addNode(); //node of id 0
670 /// Node v=g.addNode(); //node of id 1
671 /// Node e=g.addEdge(u, v); //edge of id 0
672 /// Node f=g.addEdge(v, u); //edge of id 1
673 /// Graph::NodeMap<bool> nm(g, true);
674 /// nm.set(u, false);
675 /// Graph::EdgeMap<bool> em(g, true);
676 /// em.set(e, false);
677 /// typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGA;
678 /// SubGA ga(g, nm, em);
679 /// for (SubGA::NodeIt n(ga); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
680 /// std::cout << ":-)" << std::endl;
681 /// for (SubGA::EdgeIt e(ga); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
683 /// The output of the above code is the following.
689 /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
690 /// \c Graph::Node that is why \c g.id(n) can be applied.
692 /// For other examples see also the documentation of NodeSubGraphAdaptor and
693 /// EdgeSubGraphAdaptor.
695 /// \author Marton Makai
697 template<typename _Graph, typename NodeFilterMap,
698 typename EdgeFilterMap, bool checked = true>
699 class SubGraphAdaptor :
700 public GraphAdaptorExtender<
701 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
703 typedef _Graph Graph;
704 typedef GraphAdaptorExtender< SubGraphAdaptorBase<_Graph, NodeFilterMap,
705 EdgeFilterMap, checked> >
709 SubGraphAdaptor() { }
712 SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
713 EdgeFilterMap& _edge_filter_map) {
715 setNodeFilterMap(_node_filter_map);
716 setEdgeFilterMap(_edge_filter_map);
721 /// \brief Just gives back a sub graph adaptor
723 /// Just gives back a sub graph adaptor
724 template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
725 SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>
726 subGraphAdaptor(const Graph& graph,
727 NodeFilterMap& nfm, EdgeFilterMap& efm) {
728 return SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>
732 template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
733 SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>
734 subGraphAdaptor(const Graph& graph,
735 NodeFilterMap& nfm, EdgeFilterMap& efm) {
736 return SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>
740 template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
741 SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>
742 subGraphAdaptor(const Graph& graph,
743 NodeFilterMap& nfm, EdgeFilterMap& efm) {
744 return SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>
748 template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
749 SubGraphAdaptor<const Graph, const NodeFilterMap, const EdgeFilterMap>
750 subGraphAdaptor(const Graph& graph,
751 NodeFilterMap& nfm, EdgeFilterMap& efm) {
752 return SubGraphAdaptor<const Graph, const NodeFilterMap,
753 const EdgeFilterMap>(graph, nfm, efm);
758 ///\brief An adaptor for hiding nodes from a graph.
759 ///\ingroup graph_adaptors
761 ///An adaptor for hiding nodes from a graph.
762 ///This adaptor specializes SubGraphAdaptor in the way that only
764 ///can be filtered. In usual case the checked parameter is true, we get the
765 ///induced subgraph. But if the checked parameter is false then we can only
766 ///filter only isolated nodes.
767 ///\author Marton Makai
768 template<typename Graph, typename NodeFilterMap, bool checked = true>
769 class NodeSubGraphAdaptor :
770 public SubGraphAdaptor<Graph, NodeFilterMap,
771 ConstMap<typename Graph::Edge,bool>, checked> {
774 typedef SubGraphAdaptor<Graph, NodeFilterMap,
775 ConstMap<typename Graph::Edge,bool>, checked >
779 ConstMap<typename Graph::Edge, bool> const_true_map;
781 NodeSubGraphAdaptor() : const_true_map(true) {
782 Parent::setEdgeFilterMap(const_true_map);
787 NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
788 Parent(), const_true_map(true) {
789 Parent::setGraph(_graph);
790 Parent::setNodeFilterMap(_node_filter_map);
791 Parent::setEdgeFilterMap(const_true_map);
797 /// \brief Just gives back a node sub graph adaptor
799 /// Just gives back a node sub graph adaptor
800 template<typename Graph, typename NodeFilterMap>
801 NodeSubGraphAdaptor<const Graph, NodeFilterMap>
802 nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) {
803 return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm);
806 template<typename Graph, typename NodeFilterMap>
807 NodeSubGraphAdaptor<const Graph, const NodeFilterMap>
808 nodeSubGraphAdaptor(const Graph& graph, const NodeFilterMap& nfm) {
809 return NodeSubGraphAdaptor<const Graph, const NodeFilterMap>(graph, nfm);
812 ///\brief An adaptor for hiding edges from a graph.
814 ///An adaptor for hiding edges from a graph.
815 ///This adaptor specializes SubGraphAdaptor in the way that
817 ///can be filtered. The usefulness of this adaptor is demonstrated in the
818 ///problem of searching a maximum number of edge-disjoint shortest paths
820 ///two nodes \c s and \c t. Shortest here means being shortest w.r.t.
821 ///non-negative edge-lengths. Note that
822 ///the comprehension of the presented solution
823 ///need's some elementary knowledge from combinatorial optimization.
825 ///If a single shortest path is to be
826 ///searched between \c s and \c t, then this can be done easily by
827 ///applying the Dijkstra algorithm. What happens, if a maximum number of
828 ///edge-disjoint shortest paths is to be computed. It can be proved that an
829 ///edge can be in a shortest path if and only
830 ///if it is tight with respect to
831 ///the potential function computed by Dijkstra.
832 ///Moreover, any path containing
833 ///only such edges is a shortest one.
834 ///Thus we have to compute a maximum number
835 ///of edge-disjoint paths between \c s and \c t in
836 ///the graph which has edge-set
837 ///all the tight edges. The computation will be demonstrated
839 ///graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
840 ///The full source code is available in \ref sub_graph_adaptor_demo.cc.
841 ///If you are interested in more demo programs, you can use
842 ///\ref dim_to_dot.cc to generate .dot files from dimacs files.
843 ///The .dot file of the following figure was generated by
844 ///the demo program \ref dim_to_dot.cc.
847 ///digraph lemon_dot_example {
848 ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
849 ///n0 [ label="0 (s)" ];
855 ///n6 [ label="6 (t)" ];
856 ///edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
857 ///n5 -> n6 [ label="9, length:4" ];
858 ///n4 -> n6 [ label="8, length:2" ];
859 ///n3 -> n5 [ label="7, length:1" ];
860 ///n2 -> n5 [ label="6, length:3" ];
861 ///n2 -> n6 [ label="5, length:5" ];
862 ///n2 -> n4 [ label="4, length:2" ];
863 ///n1 -> n4 [ label="3, length:3" ];
864 ///n0 -> n3 [ label="2, length:1" ];
865 ///n0 -> n2 [ label="1, length:2" ];
866 ///n0 -> n1 [ label="0, length:3" ];
873 ///LengthMap length(g);
875 ///readDimacs(std::cin, g, length, s, t);
877 ///cout << "edges with lengths (of form id, source--length->target): " << endl;
878 ///for(EdgeIt e(g); e!=INVALID; ++e)
879 /// cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
880 /// << length[e] << "->" << g.id(g.target(e)) << endl;
882 ///cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
884 ///Next, the potential function is computed with Dijkstra.
886 ///typedef Dijkstra<Graph, LengthMap> Dijkstra;
887 ///Dijkstra dijkstra(g, length);
890 ///Next, we consrtruct a map which filters the edge-set to the tight edges.
892 ///typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
894 ///TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
896 ///typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGA;
897 ///SubGA ga(g, tight_edge_filter);
899 ///Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
900 ///with a max flow algorithm Preflow.
902 ///ConstMap<Edge, int> const_1_map(1);
903 ///Graph::EdgeMap<int> flow(g, 0);
905 ///Preflow<SubGA, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
906 /// preflow(ga, s, t, const_1_map, flow);
909 ///Last, the output is:
911 ///cout << "maximum number of edge-disjoint shortest path: "
912 /// << preflow.flowValue() << endl;
913 ///cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
915 ///for(EdgeIt e(g); e!=INVALID; ++e)
917 /// cout << " " << g.id(g.source(e)) << "--"
918 /// << length[e] << "->" << g.id(g.target(e)) << endl;
920 ///The program has the following (expected :-)) output:
922 ///edges with lengths (of form id, source--length->target):
934 ///maximum number of edge-disjoint shortest path: 2
935 ///edges of the maximum number of edge-disjoint shortest s-t paths:
944 ///\author Marton Makai
945 template<typename Graph, typename EdgeFilterMap>
946 class EdgeSubGraphAdaptor :
947 public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
948 EdgeFilterMap, false> {
950 typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
951 EdgeFilterMap, false> Parent;
953 ConstMap<typename Graph::Node, bool> const_true_map;
955 EdgeSubGraphAdaptor() : const_true_map(true) {
956 Parent::setNodeFilterMap(const_true_map);
961 EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
962 Parent(), const_true_map(true) {
963 Parent::setGraph(_graph);
964 Parent::setNodeFilterMap(const_true_map);
965 Parent::setEdgeFilterMap(_edge_filter_map);
970 /// \brief Just gives back an edge sub graph adaptor
972 /// Just gives back an edge sub graph adaptor
973 template<typename Graph, typename EdgeFilterMap>
974 EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>
975 edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) {
976 return EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>(graph, efm);
979 template<typename Graph, typename EdgeFilterMap>
980 EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>
981 edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) {
982 return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm);
985 template <typename _Graph>
986 class UndirGraphAdaptorBase :
987 public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
989 typedef _Graph Graph;
990 typedef UndirGraphAdaptorBase Adaptor;
991 typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
995 UndirGraphAdaptorBase() : Parent() {}
999 typedef typename Parent::UEdge UEdge;
1000 typedef typename Parent::Edge Edge;
1004 template <typename _Value>
1008 typedef typename _Graph::template EdgeMap<_Value> MapImpl;
1012 typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
1014 typedef _Value Value;
1017 EdgeMapBase(const Adaptor& adaptor) :
1018 forward_map(*adaptor.graph), backward_map(*adaptor.graph) {}
1020 EdgeMapBase(const Adaptor& adaptor, const Value& v)
1021 : forward_map(*adaptor.graph, v), backward_map(*adaptor.graph, v) {}
1023 void set(const Edge& e, const Value& a) {
1024 if (Parent::direction(e)) {
1025 forward_map.set(e, a);
1027 backward_map.set(e, a);
1031 typename MapTraits<MapImpl>::ConstReturnValue operator[](Edge e) const {
1032 if (Parent::direction(e)) {
1033 return forward_map[e];
1035 return backward_map[e];
1039 typename MapTraits<MapImpl>::ReturnValue operator[](Edge e) {
1040 if (Parent::direction(e)) {
1041 return forward_map[e];
1043 return backward_map[e];
1049 MapImpl forward_map, backward_map;
1055 template <typename _Value>
1057 : public SubMapExtender<Adaptor, EdgeMapBase<_Value> >
1060 typedef Adaptor Graph;
1061 typedef SubMapExtender<Adaptor, EdgeMapBase<_Value> > Parent;
1063 EdgeMap(const Graph& graph)
1065 EdgeMap(const Graph& graph, const _Value& value)
1066 : Parent(graph, value) {}
1068 EdgeMap& operator=(const EdgeMap& cmap) {
1069 return operator=<EdgeMap>(cmap);
1072 template <typename CMap>
1073 EdgeMap& operator=(const CMap& cmap) {
1074 Parent::operator=(cmap);
1079 template <typename _Value>
1080 class UEdgeMap : public Graph::template EdgeMap<_Value> {
1083 typedef typename Graph::template EdgeMap<_Value> Parent;
1085 explicit UEdgeMap(const Adaptor& ga)
1086 : Parent(*ga.graph) {}
1088 UEdgeMap(const Adaptor& ga, const _Value& value)
1089 : Parent(*ga.graph, value) {}
1091 UEdgeMap& operator=(const UEdgeMap& cmap) {
1092 return operator=<UEdgeMap>(cmap);
1095 template <typename CMap>
1096 UEdgeMap& operator=(const CMap& cmap) {
1097 Parent::operator=(cmap);
1105 template <typename _Graph, typename Enable = void>
1106 class AlterableUndirGraphAdaptor
1107 : public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > {
1109 typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent;
1113 AlterableUndirGraphAdaptor() : Parent() {}
1117 typedef typename Parent::EdgeNotifier UEdgeNotifier;
1118 typedef InvalidType EdgeNotifier;
1122 template <typename _Graph>
1123 class AlterableUndirGraphAdaptor<
1125 typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type >
1126 : public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > {
1129 typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent;
1130 typedef _Graph Graph;
1131 typedef typename _Graph::Edge GraphEdge;
1135 AlterableUndirGraphAdaptor()
1136 : Parent(), edge_notifier(*this), edge_notifier_proxy(*this) {}
1138 void setGraph(_Graph& graph) {
1139 Parent::setGraph(graph);
1140 edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge()));
1145 ~AlterableUndirGraphAdaptor() {
1146 edge_notifier.clear();
1149 typedef typename Parent::UEdge UEdge;
1150 typedef typename Parent::Edge Edge;
1152 typedef typename Parent::EdgeNotifier UEdgeNotifier;
1154 using Parent::getNotifier;
1156 typedef AlterationNotifier<AlterableUndirGraphAdaptor,
1158 EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
1162 class NotifierProxy : public Graph::EdgeNotifier::ObserverBase {
1165 typedef typename Graph::EdgeNotifier::ObserverBase Parent;
1166 typedef AlterableUndirGraphAdaptor AdaptorBase;
1168 NotifierProxy(const AdaptorBase& _adaptor)
1169 : Parent(), adaptor(&_adaptor) {
1172 virtual ~NotifierProxy() {
1173 if (Parent::attached()) {
1178 void setNotifier(typename Graph::EdgeNotifier& notifier) {
1179 Parent::attach(notifier);
1185 virtual void add(const GraphEdge& ge) {
1186 std::vector<Edge> edges;
1187 edges.push_back(AdaptorBase::Parent::direct(ge, true));
1188 edges.push_back(AdaptorBase::Parent::direct(ge, false));
1189 adaptor->getNotifier(Edge()).add(edges);
1191 virtual void add(const std::vector<GraphEdge>& ge) {
1192 std::vector<Edge> edges;
1193 for (int i = 0; i < (int)ge.size(); ++i) {
1194 edges.push_back(AdaptorBase::Parent::direct(ge[i], true));
1195 edges.push_back(AdaptorBase::Parent::direct(ge[i], false));
1197 adaptor->getNotifier(Edge()).add(edges);
1199 virtual void erase(const GraphEdge& ge) {
1200 std::vector<Edge> edges;
1201 edges.push_back(AdaptorBase::Parent::direct(ge, true));
1202 edges.push_back(AdaptorBase::Parent::direct(ge, false));
1203 adaptor->getNotifier(Edge()).erase(edges);
1205 virtual void erase(const std::vector<GraphEdge>& ge) {
1206 std::vector<Edge> edges;
1207 for (int i = 0; i < (int)ge.size(); ++i) {
1208 edges.push_back(AdaptorBase::Parent::direct(ge[i], true));
1209 edges.push_back(AdaptorBase::Parent::direct(ge[i], false));
1211 adaptor->getNotifier(Edge()).erase(edges);
1213 virtual void build() {
1214 adaptor->getNotifier(Edge()).build();
1216 virtual void clear() {
1217 adaptor->getNotifier(Edge()).clear();
1220 const AdaptorBase* adaptor;
1224 mutable EdgeNotifier edge_notifier;
1225 NotifierProxy edge_notifier_proxy;
1230 /// \brief An undirected graph is made from a directed graph by an adaptor
1231 /// \ingroup graph_adaptors
1233 /// Undocumented, untested!!!
1234 /// If somebody knows nice demo application, let's polulate it.
1236 /// \author Marton Makai
1237 template<typename _Graph>
1238 class UndirGraphAdaptor : public AlterableUndirGraphAdaptor<_Graph> {
1240 typedef _Graph Graph;
1241 typedef AlterableUndirGraphAdaptor<_Graph> Parent;
1243 UndirGraphAdaptor() { }
1245 UndirGraphAdaptor(_Graph& _graph) {
1249 template <typename _ForwardMap, typename _BackwardMap>
1250 class CombinedEdgeMap {
1253 typedef _ForwardMap ForwardMap;
1254 typedef _BackwardMap BackwardMap;
1256 typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
1258 typedef typename ForwardMap::Value Value;
1259 typedef typename Parent::Edge Key;
1261 CombinedEdgeMap() : forward_map(0), backward_map(0) {}
1263 CombinedEdgeMap(ForwardMap& _forward_map, BackwardMap& _backward_map)
1264 : forward_map(&_forward_map), backward_map(&_backward_map) {}
1266 void set(const Key& e, const Value& a) {
1267 if (Parent::direction(e)) {
1268 forward_map->set(e, a);
1270 backward_map->set(e, a);
1274 typename MapTraits<ForwardMap>::ConstReturnValue
1275 operator[](const Key& e) const {
1276 if (Parent::direction(e)) {
1277 return (*forward_map)[e];
1279 return (*backward_map)[e];
1283 typename MapTraits<ForwardMap>::ReturnValue
1284 operator[](const Key& e) {
1285 if (Parent::direction(e)) {
1286 return (*forward_map)[e];
1288 return (*backward_map)[e];
1292 void setForwardMap(ForwardMap& _forward_map) {
1293 forward_map = &_forward_map;
1296 void setBackwardMap(BackwardMap& _backward_map) {
1297 backward_map = &_backward_map;
1302 ForwardMap* forward_map;
1303 BackwardMap* backward_map;
1309 /// \brief Just gives back an undir graph adaptor
1311 /// Just gives back an undir graph adaptor
1312 template<typename Graph>
1313 UndirGraphAdaptor<const Graph>
1314 undirGraphAdaptor(const Graph& graph) {
1315 return UndirGraphAdaptor<const Graph>(graph);
1318 template<typename Graph, typename Number,
1319 typename CapacityMap, typename FlowMap,
1320 typename Tolerance = Tolerance<Number> >
1321 class ResForwardFilter {
1322 const CapacityMap* capacity;
1323 const FlowMap* flow;
1324 Tolerance tolerance;
1326 typedef typename Graph::Edge Key;
1329 ResForwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
1330 const Tolerance& _tolerance = Tolerance())
1331 : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
1333 ResForwardFilter(const Tolerance& _tolerance)
1334 : capacity(0), flow(0), tolerance(_tolerance) { }
1336 void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
1337 void setFlow(const FlowMap& _flow) { flow = &_flow; }
1339 bool operator[](const typename Graph::Edge& e) const {
1340 return tolerance.less((*flow)[e], (*capacity)[e]);
1344 template<typename Graph, typename Number,
1345 typename CapacityMap, typename FlowMap,
1346 typename Tolerance = Tolerance<Number> >
1347 class ResBackwardFilter {
1348 const CapacityMap* capacity;
1349 const FlowMap* flow;
1350 Tolerance tolerance;
1352 typedef typename Graph::Edge Key;
1355 ResBackwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
1356 const Tolerance& _tolerance = Tolerance())
1357 : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
1358 ResBackwardFilter(const Tolerance& _tolerance = Tolerance())
1359 : capacity(0), flow(0), tolerance(_tolerance) { }
1360 void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
1361 void setFlow(const FlowMap& _flow) { flow = &_flow; }
1362 bool operator[](const typename Graph::Edge& e) const {
1363 return tolerance.less(0, Number((*flow)[e]));
1368 ///\brief An adaptor for composing the residual
1369 ///graph for directed flow and circulation problems.
1371 ///\ingroup graph_adaptors
1373 ///An adaptor for composing the residual graph for directed flow and
1374 ///circulation problems. Let \f$ G=(V, A) \f$ be a directed graph
1375 ///and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
1376 ///be functions on the edge-set.
1378 ///In the appications of ResGraphAdaptor, \f$ f \f$ usually stands
1379 ///for a flow and \f$ c \f$ for a capacity function. Suppose that a
1380 ///graph instange \c g of type \c ListGraph implements \f$ G \f$.
1386 ///Then RevGraphAdaptor implements the graph structure with node-set
1387 /// \f$ V \f$ and edge-set \f$ A_{forward}\cup A_{backward} \f$,
1388 ///where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
1389 /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so called
1390 ///residual graph. When we take the union
1391 /// \f$ A_{forward}\cup A_{backward} \f$, multilicities are counted, i.e.
1392 ///if an edge is in both \f$ A_{forward} \f$ and \f$ A_{backward} \f$,
1393 ///then in the adaptor it appears twice. The following code shows how
1394 ///such an instance can be constructed.
1397 /// typedef ListGraph Graph;
1398 /// Graph::EdgeMap<int> f(g);
1399 /// Graph::EdgeMap<int> c(g);
1400 /// ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > ga(g);
1402 ///\author Marton Makai
1404 template<typename Graph, typename Number,
1405 typename CapacityMap, typename FlowMap,
1406 typename Tolerance = Tolerance<Number> >
1407 class ResGraphAdaptor :
1408 public EdgeSubGraphAdaptor<
1409 UndirGraphAdaptor<const Graph>,
1410 typename UndirGraphAdaptor<const Graph>::template CombinedEdgeMap<
1411 ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>,
1412 ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap> > > {
1415 typedef UndirGraphAdaptor<const Graph> UGraph;
1417 typedef ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>
1420 typedef ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap>
1423 typedef typename UGraph::
1424 template CombinedEdgeMap<ForwardFilter, BackwardFilter>
1427 typedef EdgeSubGraphAdaptor<UGraph, EdgeFilter> Parent;
1431 const CapacityMap* capacity;
1435 ForwardFilter forward_filter;
1436 BackwardFilter backward_filter;
1437 EdgeFilter edge_filter;
1439 void setCapacityMap(const CapacityMap& _capacity) {
1440 capacity=&_capacity;
1441 forward_filter.setCapacity(_capacity);
1442 backward_filter.setCapacity(_capacity);
1445 void setFlowMap(FlowMap& _flow) {
1447 forward_filter.setFlow(_flow);
1448 backward_filter.setFlow(_flow);
1453 /// \brief Constructor of the residual graph.
1455 /// Constructor of the residual graph. The parameters are the graph type,
1456 /// the flow map, the capacity map and a tolerance object.
1457 ResGraphAdaptor(const Graph& _graph, const CapacityMap& _capacity,
1458 FlowMap& _flow, const Tolerance& _tolerance = Tolerance())
1459 : Parent(), capacity(&_capacity), flow(&_flow), ugraph(_graph),
1460 forward_filter(_capacity, _flow, _tolerance),
1461 backward_filter(_capacity, _flow, _tolerance),
1462 edge_filter(forward_filter, backward_filter)
1464 Parent::setGraph(ugraph);
1465 Parent::setEdgeFilterMap(edge_filter);
1468 typedef typename Parent::Edge Edge;
1470 /// \brief Gives back the residual capacity of the edge.
1472 /// Gives back the residual capacity of the edge.
1473 Number rescap(const Edge& edge) const {
1474 if (UGraph::direction(edge)) {
1475 return (*capacity)[edge]-(*flow)[edge];
1477 return (*flow)[edge];
1481 /// \brief Augment on the given edge in the residual graph.
1483 /// Augment on the given edge in the residual graph. It increase
1484 /// or decrease the flow on the original edge depend on the direction
1485 /// of the residual edge.
1486 void augment(const Edge& e, Number a) const {
1487 if (UGraph::direction(e)) {
1488 flow->set(e, (*flow)[e] + a);
1490 flow->set(e, (*flow)[e] - a);
1494 /// \brief Returns the direction of the edge.
1496 /// Returns true when the edge is same oriented as the original edge.
1497 static bool forward(const Edge& e) {
1498 return UGraph::direction(e);
1501 /// \brief Returns the direction of the edge.
1503 /// Returns true when the edge is opposite oriented as the original edge.
1504 static bool backward(const Edge& e) {
1505 return !UGraph::direction(e);
1508 /// \brief Gives back the forward oriented residual edge.
1510 /// Gives back the forward oriented residual edge.
1511 static Edge forward(const typename Graph::Edge& e) {
1512 return UGraph::direct(e, true);
1515 /// \brief Gives back the backward oriented residual edge.
1517 /// Gives back the backward oriented residual edge.
1518 static Edge backward(const typename Graph::Edge& e) {
1519 return UGraph::direct(e, false);
1522 /// \brief Residual capacity map.
1524 /// In generic residual graphs the residual capacity can be obtained
1528 const ResGraphAdaptor* res_graph;
1530 typedef Number Value;
1532 ResCap(const ResGraphAdaptor& _res_graph)
1533 : res_graph(&_res_graph) {}
1535 Number operator[](const Edge& e) const {
1536 return res_graph->rescap(e);
1545 template <typename _Graph, typename FirstOutEdgesMap>
1546 class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
1548 typedef _Graph Graph;
1549 typedef GraphAdaptorBase<_Graph> Parent;
1551 FirstOutEdgesMap* first_out_edges;
1552 ErasingFirstGraphAdaptorBase() : Parent(),
1553 first_out_edges(0) { }
1555 void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1556 first_out_edges=&_first_out_edges;
1561 typedef typename Parent::Node Node;
1562 typedef typename Parent::Edge Edge;
1564 void firstOut(Edge& i, const Node& n) const {
1565 i=(*first_out_edges)[n];
1568 void erase(const Edge& e) const {
1572 first_out_edges->set(n, f);
1577 ///\brief For blocking flows.
1578 ///\ingroup graph_adaptors
1580 ///This graph adaptor is used for on-the-fly
1581 ///Dinits blocking flow computations.
1582 ///For each node, an out-edge is stored which is used when the
1584 ///OutEdgeIt& first(OutEdgeIt&, const Node&)
1588 ///\author Marton Makai
1590 template <typename _Graph, typename FirstOutEdgesMap>
1591 class ErasingFirstGraphAdaptor :
1592 public GraphAdaptorExtender<
1593 ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
1595 typedef _Graph Graph;
1596 typedef GraphAdaptorExtender<
1597 ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
1598 ErasingFirstGraphAdaptor(Graph& _graph,
1599 FirstOutEdgesMap& _first_out_edges) {
1601 setFirstOutEdgesMap(_first_out_edges);
1606 /// \brief Base class for split graph adaptor
1608 /// Base class of split graph adaptor. In most case you do not need to
1609 /// use it directly but the documented member functions of this class can
1610 /// be used with the SplitGraphAdaptor class.
1611 /// \sa SplitGraphAdaptor
1612 template <typename _Graph>
1613 class SplitGraphAdaptorBase
1614 : public GraphAdaptorBase<const _Graph> {
1617 typedef _Graph Graph;
1619 typedef GraphAdaptorBase<const _Graph> Parent;
1621 typedef typename Graph::Node GraphNode;
1622 typedef typename Graph::Edge GraphEdge;
1627 template <typename T> class NodeMap;
1628 template <typename T> class EdgeMap;
1631 class Node : public GraphNode {
1632 friend class SplitGraphAdaptorBase;
1633 template <typename T> friend class NodeMap;
1637 Node(GraphNode _node, bool _in_node)
1638 : GraphNode(_node), in_node(_in_node) {}
1643 Node(Invalid) : GraphNode(INVALID), in_node(true) {}
1645 bool operator==(const Node& node) const {
1646 return GraphNode::operator==(node) && in_node == node.in_node;
1649 bool operator!=(const Node& node) const {
1650 return !(*this == node);
1653 bool operator<(const Node& node) const {
1654 return GraphNode::operator<(node) ||
1655 (GraphNode::operator==(node) && in_node < node.in_node);
1660 friend class SplitGraphAdaptorBase;
1661 template <typename T> friend class EdgeMap;
1663 typedef BiVariant<GraphEdge, GraphNode> EdgeImpl;
1665 explicit Edge(const GraphEdge& edge) : item(edge) {}
1666 explicit Edge(const GraphNode& node) : item(node) {}
1672 Edge(Invalid) : item(GraphEdge(INVALID)) {}
1674 bool operator==(const Edge& edge) const {
1675 if (item.firstState()) {
1676 if (edge.item.firstState()) {
1677 return item.first() == edge.item.first();
1680 if (edge.item.secondState()) {
1681 return item.second() == edge.item.second();
1687 bool operator!=(const Edge& edge) const {
1688 return !(*this == edge);
1691 bool operator<(const Edge& edge) const {
1692 if (item.firstState()) {
1693 if (edge.item.firstState()) {
1694 return item.first() < edge.item.first();
1698 if (edge.item.secondState()) {
1699 return item.second() < edge.item.second();
1705 operator GraphEdge() const { return item.first(); }
1706 operator GraphNode() const { return item.second(); }
1710 void first(Node& node) const {
1711 Parent::first(node);
1712 node.in_node = true;
1715 void next(Node& node) const {
1717 node.in_node = false;
1719 node.in_node = true;
1724 void first(Edge& edge) const {
1725 edge.item.setSecond();
1726 Parent::first(edge.item.second());
1727 if (edge.item.second() == INVALID) {
1728 edge.item.setFirst();
1729 Parent::first(edge.item.first());
1733 void next(Edge& edge) const {
1734 if (edge.item.secondState()) {
1735 Parent::next(edge.item.second());
1736 if (edge.item.second() == INVALID) {
1737 edge.item.setFirst();
1738 Parent::first(edge.item.first());
1741 Parent::next(edge.item.first());
1745 void firstOut(Edge& edge, const Node& node) const {
1747 edge.item.setSecond(node);
1749 edge.item.setFirst();
1750 Parent::firstOut(edge.item.first(), node);
1754 void nextOut(Edge& edge) const {
1755 if (!edge.item.firstState()) {
1756 edge.item.setFirst(INVALID);
1758 Parent::nextOut(edge.item.first());
1762 void firstIn(Edge& edge, const Node& node) const {
1763 if (!node.in_node) {
1764 edge.item.setSecond(node);
1766 edge.item.setFirst();
1767 Parent::firstIn(edge.item.first(), node);
1771 void nextIn(Edge& edge) const {
1772 if (!edge.item.firstState()) {
1773 edge.item.setFirst(INVALID);
1775 Parent::nextIn(edge.item.first());
1779 Node source(const Edge& edge) const {
1780 if (edge.item.firstState()) {
1781 return Node(Parent::source(edge.item.first()), false);
1783 return Node(edge.item.second(), true);
1787 Node target(const Edge& edge) const {
1788 if (edge.item.firstState()) {
1789 return Node(Parent::target(edge.item.first()), true);
1791 return Node(edge.item.second(), false);
1795 int id(const Node& node) const {
1796 return (Parent::id(node) << 1) | (node.in_node ? 0 : 1);
1798 Node nodeFromId(int id) const {
1799 return Node(Parent::nodeFromId(id >> 1), (id & 1) == 0);
1801 int maxNodeId() const {
1802 return 2 * Parent::maxNodeId() + 1;
1805 int id(const Edge& edge) const {
1806 if (edge.item.firstState()) {
1807 return Parent::id(edge.item.first()) << 1;
1809 return (Parent::id(edge.item.second()) << 1) | 1;
1812 Edge edgeFromId(int id) const {
1813 if ((id & 1) == 0) {
1814 return Edge(Parent::edgeFromId(id >> 1));
1816 return Edge(Parent::nodeFromId(id >> 1));
1819 int maxEdgeId() const {
1820 return std::max(Parent::maxNodeId() << 1,
1821 (Parent::maxEdgeId() << 1) | 1);
1824 /// \brief Returns true when the node is in-node.
1826 /// Returns true when the node is in-node.
1827 static bool inNode(const Node& node) {
1828 return node.in_node;
1831 /// \brief Returns true when the node is out-node.
1833 /// Returns true when the node is out-node.
1834 static bool outNode(const Node& node) {
1835 return !node.in_node;
1838 /// \brief Returns true when the edge is edge in the original graph.
1840 /// Returns true when the edge is edge in the original graph.
1841 static bool origEdge(const Edge& edge) {
1842 return edge.item.firstState();
1845 /// \brief Returns true when the edge binds an in-node and an out-node.
1847 /// Returns true when the edge binds an in-node and an out-node.
1848 static bool bindEdge(const Edge& edge) {
1849 return edge.item.secondState();
1852 /// \brief Gives back the in-node created from the \c node.
1854 /// Gives back the in-node created from the \c node.
1855 static Node inNode(const GraphNode& node) {
1856 return Node(node, true);
1859 /// \brief Gives back the out-node created from the \c node.
1861 /// Gives back the out-node created from the \c node.
1862 static Node outNode(const GraphNode& node) {
1863 return Node(node, false);
1866 /// \brief Gives back the edge binds the two part of the node.
1868 /// Gives back the edge binds the two part of the node.
1869 static Edge edge(const GraphNode& node) {
1873 /// \brief Gives back the edge of the original edge.
1875 /// Gives back the edge of the original edge.
1876 static Edge edge(const GraphEdge& edge) {
1880 typedef True NodeNumTag;
1882 int nodeNum() const {
1883 return 2 * countNodes(*Parent::graph);
1886 typedef True EdgeNumTag;
1888 int edgeNum() const {
1889 return countEdges(*Parent::graph) + countNodes(*Parent::graph);
1892 typedef True FindEdgeTag;
1894 Edge findEdge(const Node& source, const Node& target,
1895 const Edge& prev = INVALID) const {
1896 if (inNode(source)) {
1897 if (outNode(target)) {
1898 if ((GraphNode&)source == (GraphNode&)target && prev == INVALID) {
1899 return Edge(source);
1903 if (inNode(target)) {
1904 return Edge(findEdge(*Parent::graph, source, target, prev));
1910 template <typename T>
1911 class NodeMap : public MapBase<Node, T> {
1912 typedef typename Parent::template NodeMap<T> NodeImpl;
1914 NodeMap(const SplitGraphAdaptorBase& _graph)
1915 : inNodeMap(_graph), outNodeMap(_graph) {}
1916 NodeMap(const SplitGraphAdaptorBase& _graph, const T& t)
1917 : inNodeMap(_graph, t), outNodeMap(_graph, t) {}
1919 void set(const Node& key, const T& val) {
1920 if (SplitGraphAdaptorBase::inNode(key)) { inNodeMap.set(key, val); }
1921 else {outNodeMap.set(key, val); }
1924 typename MapTraits<NodeImpl>::ReturnValue
1925 operator[](const Node& key) {
1926 if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; }
1927 else { return outNodeMap[key]; }
1930 typename MapTraits<NodeImpl>::ConstReturnValue
1931 operator[](const Node& key) const {
1932 if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; }
1933 else { return outNodeMap[key]; }
1937 NodeImpl inNodeMap, outNodeMap;
1940 template <typename T>
1941 class EdgeMap : public MapBase<Edge, T> {
1942 typedef typename Parent::template EdgeMap<T> EdgeMapImpl;
1943 typedef typename Parent::template NodeMap<T> NodeMapImpl;
1946 EdgeMap(const SplitGraphAdaptorBase& _graph)
1947 : edge_map(_graph), node_map(_graph) {}
1948 EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t)
1949 : edge_map(_graph, t), node_map(_graph, t) {}
1951 void set(const Edge& key, const T& val) {
1952 if (SplitGraphAdaptorBase::origEdge(key)) {
1953 edge_map.set(key.item.first(), val);
1955 node_map.set(key.item.second(), val);
1959 typename MapTraits<EdgeMapImpl>::ReturnValue
1960 operator[](const Edge& key) {
1961 if (SplitGraphAdaptorBase::origEdge(key)) {
1962 return edge_map[key.item.first()];
1964 return node_map[key.item.second()];
1968 typename MapTraits<EdgeMapImpl>::ConstReturnValue
1969 operator[](const Edge& key) const {
1970 if (SplitGraphAdaptorBase::origEdge(key)) {
1971 return edge_map[key.item.first()];
1973 return node_map[key.item.second()];
1978 typename Parent::template EdgeMap<T> edge_map;
1979 typename Parent::template NodeMap<T> node_map;
1985 template <typename _Graph, typename NodeEnable = void,
1986 typename EdgeEnable = void>
1987 class AlterableSplitGraphAdaptor
1988 : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
1991 typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
1992 typedef _Graph Graph;
1994 typedef typename Graph::Node GraphNode;
1995 typedef typename Graph::Node GraphEdge;
1999 AlterableSplitGraphAdaptor() : Parent() {}
2003 typedef InvalidType NodeNotifier;
2004 typedef InvalidType EdgeNotifier;
2008 template <typename _Graph, typename EdgeEnable>
2009 class AlterableSplitGraphAdaptor<
2011 typename enable_if<typename _Graph::NodeNotifier::Notifier>::type,
2013 : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
2016 typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
2017 typedef _Graph Graph;
2019 typedef typename Graph::Node GraphNode;
2020 typedef typename Graph::Edge GraphEdge;
2022 typedef typename Parent::Node Node;
2023 typedef typename Parent::Edge Edge;
2027 AlterableSplitGraphAdaptor()
2028 : Parent(), node_notifier(*this), node_notifier_proxy(*this) {}
2030 void setGraph(_Graph& graph) {
2031 Parent::setGraph(graph);
2032 node_notifier_proxy.setNotifier(graph.getNotifier(GraphNode()));
2037 ~AlterableSplitGraphAdaptor() {
2038 node_notifier.clear();
2041 typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier;
2042 typedef InvalidType EdgeNotifier;
2044 NodeNotifier& getNotifier(Node) const { return node_notifier; }
2048 class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase {
2051 typedef typename Graph::NodeNotifier::ObserverBase Parent;
2052 typedef AlterableSplitGraphAdaptor AdaptorBase;
2054 NodeNotifierProxy(const AdaptorBase& _adaptor)
2055 : Parent(), adaptor(&_adaptor) {
2058 virtual ~NodeNotifierProxy() {
2059 if (Parent::attached()) {
2064 void setNotifier(typename Graph::NodeNotifier& graph_notifier) {
2065 Parent::attach(graph_notifier);
2071 virtual void add(const GraphNode& gn) {
2072 std::vector<Node> nodes;
2073 nodes.push_back(AdaptorBase::Parent::inNode(gn));
2074 nodes.push_back(AdaptorBase::Parent::outNode(gn));
2075 adaptor->getNotifier(Node()).add(nodes);
2078 virtual void add(const std::vector<GraphNode>& gn) {
2079 std::vector<Node> nodes;
2080 for (int i = 0; i < (int)gn.size(); ++i) {
2081 nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2082 nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2084 adaptor->getNotifier(Node()).add(nodes);
2087 virtual void erase(const GraphNode& gn) {
2088 std::vector<Node> nodes;
2089 nodes.push_back(AdaptorBase::Parent::inNode(gn));
2090 nodes.push_back(AdaptorBase::Parent::outNode(gn));
2091 adaptor->getNotifier(Node()).erase(nodes);
2094 virtual void erase(const std::vector<GraphNode>& gn) {
2095 std::vector<Node> nodes;
2096 for (int i = 0; i < (int)gn.size(); ++i) {
2097 nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2098 nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2100 adaptor->getNotifier(Node()).erase(nodes);
2102 virtual void build() {
2103 adaptor->getNotifier(Node()).build();
2105 virtual void clear() {
2106 adaptor->getNotifier(Node()).clear();
2109 const AdaptorBase* adaptor;
2113 mutable NodeNotifier node_notifier;
2115 NodeNotifierProxy node_notifier_proxy;
2119 template <typename _Graph>
2120 class AlterableSplitGraphAdaptor<
2122 typename enable_if<typename _Graph::NodeNotifier::Notifier>::type,
2123 typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type>
2124 : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
2127 typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
2128 typedef _Graph Graph;
2130 typedef typename Graph::Node GraphNode;
2131 typedef typename Graph::Edge GraphEdge;
2133 typedef typename Parent::Node Node;
2134 typedef typename Parent::Edge Edge;
2138 AlterableSplitGraphAdaptor()
2139 : Parent(), node_notifier(*this), edge_notifier(*this),
2140 node_notifier_proxy(*this), edge_notifier_proxy(*this) {}
2142 void setGraph(_Graph& graph) {
2143 Parent::setGraph(graph);
2144 node_notifier_proxy.setNotifier(graph.getNotifier(GraphNode()));
2145 edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge()));
2150 ~AlterableSplitGraphAdaptor() {
2151 node_notifier.clear();
2152 edge_notifier.clear();
2155 typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier;
2156 typedef AlterationNotifier<AlterableSplitGraphAdaptor, Edge> EdgeNotifier;
2158 NodeNotifier& getNotifier(Node) const { return node_notifier; }
2159 EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
2163 class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase {
2166 typedef typename Graph::NodeNotifier::ObserverBase Parent;
2167 typedef AlterableSplitGraphAdaptor AdaptorBase;
2169 NodeNotifierProxy(const AdaptorBase& _adaptor)
2170 : Parent(), adaptor(&_adaptor) {
2173 virtual ~NodeNotifierProxy() {
2174 if (Parent::attached()) {
2179 void setNotifier(typename Graph::NodeNotifier& graph_notifier) {
2180 Parent::attach(graph_notifier);
2186 virtual void add(const GraphNode& gn) {
2187 std::vector<Node> nodes;
2188 nodes.push_back(AdaptorBase::Parent::inNode(gn));
2189 nodes.push_back(AdaptorBase::Parent::outNode(gn));
2190 adaptor->getNotifier(Node()).add(nodes);
2191 adaptor->getNotifier(Edge()).add(AdaptorBase::Parent::edge(gn));
2193 virtual void add(const std::vector<GraphNode>& gn) {
2194 std::vector<Node> nodes;
2195 std::vector<Edge> edges;
2196 for (int i = 0; i < (int)gn.size(); ++i) {
2197 edges.push_back(AdaptorBase::Parent::edge(gn[i]));
2198 nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2199 nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2201 adaptor->getNotifier(Node()).add(nodes);
2202 adaptor->getNotifier(Edge()).add(edges);
2204 virtual void erase(const GraphNode& gn) {
2205 adaptor->getNotifier(Edge()).erase(AdaptorBase::Parent::edge(gn));
2206 std::vector<Node> nodes;
2207 nodes.push_back(AdaptorBase::Parent::inNode(gn));
2208 nodes.push_back(AdaptorBase::Parent::outNode(gn));
2209 adaptor->getNotifier(Node()).erase(nodes);
2211 virtual void erase(const std::vector<GraphNode>& gn) {
2212 std::vector<Node> nodes;
2213 std::vector<Edge> edges;
2214 for (int i = 0; i < (int)gn.size(); ++i) {
2215 edges.push_back(AdaptorBase::Parent::edge(gn[i]));
2216 nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2217 nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2219 adaptor->getNotifier(Edge()).erase(edges);
2220 adaptor->getNotifier(Node()).erase(nodes);
2222 virtual void build() {
2223 std::vector<Edge> edges;
2224 const typename Parent::Notifier* notifier = Parent::getNotifier();
2226 for (notifier->first(it); it != INVALID; notifier->next(it)) {
2227 edges.push_back(AdaptorBase::Parent::edge(it));
2229 adaptor->getNotifier(Node()).build();
2230 adaptor->getNotifier(Edge()).add(edges);
2232 virtual void clear() {
2233 std::vector<Edge> edges;
2234 const typename Parent::Notifier* notifier = Parent::getNotifier();
2236 for (notifier->first(it); it != INVALID; notifier->next(it)) {
2237 edges.push_back(AdaptorBase::Parent::edge(it));
2239 adaptor->getNotifier(Edge()).erase(edges);
2240 adaptor->getNotifier(Node()).clear();
2243 const AdaptorBase* adaptor;
2246 class EdgeNotifierProxy : public Graph::EdgeNotifier::ObserverBase {
2249 typedef typename Graph::EdgeNotifier::ObserverBase Parent;
2250 typedef AlterableSplitGraphAdaptor AdaptorBase;
2252 EdgeNotifierProxy(const AdaptorBase& _adaptor)
2253 : Parent(), adaptor(&_adaptor) {
2256 virtual ~EdgeNotifierProxy() {
2257 if (Parent::attached()) {
2262 void setNotifier(typename Graph::EdgeNotifier& graph_notifier) {
2263 Parent::attach(graph_notifier);
2269 virtual void add(const GraphEdge& ge) {
2270 adaptor->getNotifier(Edge()).add(AdaptorBase::edge(ge));
2272 virtual void add(const std::vector<GraphEdge>& ge) {
2273 std::vector<Edge> edges;
2274 for (int i = 0; i < (int)ge.size(); ++i) {
2275 edges.push_back(AdaptorBase::edge(ge[i]));
2277 adaptor->getNotifier(Edge()).add(edges);
2279 virtual void erase(const GraphEdge& ge) {
2280 adaptor->getNotifier(Edge()).erase(AdaptorBase::edge(ge));
2282 virtual void erase(const std::vector<GraphEdge>& ge) {
2283 std::vector<Edge> edges;
2284 for (int i = 0; i < (int)ge.size(); ++i) {
2285 edges.push_back(AdaptorBase::edge(ge[i]));
2287 adaptor->getNotifier(Edge()).erase(edges);
2289 virtual void build() {
2290 std::vector<Edge> edges;
2291 const typename Parent::Notifier* notifier = Parent::getNotifier();
2293 for (notifier->first(it); it != INVALID; notifier->next(it)) {
2294 edges.push_back(AdaptorBase::Parent::edge(it));
2296 adaptor->getNotifier(Edge()).add(edges);
2298 virtual void clear() {
2299 std::vector<Edge> edges;
2300 const typename Parent::Notifier* notifier = Parent::getNotifier();
2302 for (notifier->first(it); it != INVALID; notifier->next(it)) {
2303 edges.push_back(AdaptorBase::Parent::edge(it));
2305 adaptor->getNotifier(Edge()).erase(edges);
2308 const AdaptorBase* adaptor;
2312 mutable NodeNotifier node_notifier;
2313 mutable EdgeNotifier edge_notifier;
2315 NodeNotifierProxy node_notifier_proxy;
2316 EdgeNotifierProxy edge_notifier_proxy;
2320 /// \ingroup graph_adaptors
2322 /// \brief SplitGraphAdaptor class
2324 /// This is an graph adaptor which splits all node into an in-node
2325 /// and an out-node. Formaly, the adaptor replaces each \f$ u \f$
2326 /// node in the graph with two node, \f$ u_{in} \f$ node and
2327 /// \f$ u_{out} \f$ node. If there is an \f$ (v, u) \f$ edge in the
2328 /// original graph the new target of the edge will be \f$ u_{in} \f$ and
2329 /// similarly the source of the original \f$ (u, v) \f$ edge will be
2330 /// \f$ u_{out} \f$. The adaptor will add for each node in the
2331 /// original graph an additional edge which will connect
2332 /// \f$ (u_{in}, u_{out}) \f$.
2334 /// The aim of this class is to run algorithm with node costs if the
2335 /// algorithm can use directly just edge costs. In this case we should use
2336 /// a \c SplitGraphAdaptor and set the node cost of the graph to the
2337 /// bind edge in the adapted graph.
2339 /// By example a maximum flow algoritm can compute how many edge
2340 /// disjoint paths are in the graph. But we would like to know how
2341 /// many node disjoint paths are in the graph. First we have to
2342 /// adapt the graph with the \c SplitGraphAdaptor. Then run the flow
2343 /// algorithm on the adapted graph. The bottleneck of the flow will
2344 /// be the bind edges which bounds the flow with the count of the
2345 /// node disjoint paths.
2349 /// typedef SplitGraphAdaptor<SmartGraph> SGraph;
2351 /// SGraph sgraph(graph);
2353 /// typedef ConstMap<SGraph::Edge, int> SCapacity;
2354 /// SCapacity scapacity(1);
2356 /// SGraph::EdgeMap<int> sflow(sgraph);
2358 /// Preflow<SGraph, int, SCapacity>
2359 /// spreflow(sgraph, SGraph::outNode(source),SGraph::inNode(target),
2360 /// scapacity, sflow);
2366 /// The result of the mamixum flow on the original graph
2367 /// shows the next figure:
2369 /// \image html edge_disjoint.png
2370 /// \image latex edge_disjoint.eps "Edge disjoint paths" width=\textwidth
2372 /// And the maximum flow on the adapted graph:
2374 /// \image html node_disjoint.png
2375 /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth
2377 /// The second solution contains just 3 disjoint paths while the first 4.
2379 /// This graph adaptor is fully conform to the
2380 /// \ref concept::StaticGraph "StaticGraph" concept and
2381 /// contains some additional member functions and types. The
2382 /// documentation of some member functions may be found just in the
2383 /// SplitGraphAdaptorBase class.
2385 /// \sa SplitGraphAdaptorBase
2386 template <typename _Graph>
2387 class SplitGraphAdaptor : public AlterableSplitGraphAdaptor<_Graph> {
2389 typedef AlterableSplitGraphAdaptor<_Graph> Parent;
2391 typedef typename Parent::Node Node;
2392 typedef typename Parent::Edge Edge;
2394 /// \brief Constructor of the adaptor.
2396 /// Constructor of the adaptor.
2397 SplitGraphAdaptor(_Graph& graph) {
2398 Parent::setGraph(graph);
2401 /// \brief NodeMap combined from two original NodeMap
2403 /// This class adapt two of the original graph NodeMap to
2404 /// get a node map on the adapted graph.
2405 template <typename InNodeMap, typename OutNodeMap>
2406 class CombinedNodeMap {
2410 typedef typename InNodeMap::Value Value;
2412 /// \brief Constructor
2415 CombinedNodeMap(InNodeMap& _inNodeMap, OutNodeMap& _outNodeMap)
2416 : inNodeMap(_inNodeMap), outNodeMap(_outNodeMap) {}
2418 /// \brief The subscript operator.
2420 /// The subscript operator.
2421 Value& operator[](const Key& key) {
2422 if (Parent::inNode(key)) {
2423 return inNodeMap[key];
2425 return outNodeMap[key];
2429 /// \brief The const subscript operator.
2431 /// The const subscript operator.
2432 Value operator[](const Key& key) const {
2433 if (Parent::inNode(key)) {
2434 return inNodeMap[key];
2436 return outNodeMap[key];
2440 /// \brief The setter function of the map.
2442 /// The setter function of the map.
2443 void set(const Key& key, const Value& value) {
2444 if (Parent::inNode(key)) {
2445 inNodeMap.set(key, value);
2447 outNodeMap.set(key, value);
2453 InNodeMap& inNodeMap;
2454 OutNodeMap& outNodeMap;
2459 /// \brief Just gives back a combined node map.
2461 /// Just gives back a combined node map.
2462 template <typename InNodeMap, typename OutNodeMap>
2463 static CombinedNodeMap<InNodeMap, OutNodeMap>
2464 combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
2465 return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
2468 template <typename InNodeMap, typename OutNodeMap>
2469 static CombinedNodeMap<const InNodeMap, OutNodeMap>
2470 combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
2471 return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
2474 template <typename InNodeMap, typename OutNodeMap>
2475 static CombinedNodeMap<InNodeMap, const OutNodeMap>
2476 combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
2477 return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
2480 template <typename InNodeMap, typename OutNodeMap>
2481 static CombinedNodeMap<const InNodeMap, const OutNodeMap>
2482 combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
2483 return CombinedNodeMap<const InNodeMap,
2484 const OutNodeMap>(in_map, out_map);
2487 /// \brief EdgeMap combined from an original EdgeMap and NodeMap
2489 /// This class adapt an original graph EdgeMap and NodeMap to
2490 /// get an edge map on the adapted graph.
2491 template <typename GraphEdgeMap, typename GraphNodeMap>
2492 class CombinedEdgeMap
2493 : public MapBase<Edge, typename GraphEdgeMap::Value> {
2495 typedef MapBase<Edge, typename GraphEdgeMap::Value> Parent;
2497 typedef typename Parent::Key Key;
2498 typedef typename Parent::Value Value;
2500 /// \brief Constructor
2503 CombinedEdgeMap(GraphEdgeMap& _edge_map, GraphNodeMap& _node_map)
2504 : edge_map(_edge_map), node_map(_node_map) {}
2506 /// \brief The subscript operator.
2508 /// The subscript operator.
2509 void set(const Edge& edge, const Value& val) {
2510 if (Parent::origEdge(edge)) {
2511 edge_map.set(edge, val);
2513 node_map.set(edge, val);
2517 /// \brief The const subscript operator.
2519 /// The const subscript operator.
2520 Value operator[](const Key& edge) const {
2521 if (Parent::origEdge(edge)) {
2522 return edge_map[edge];
2524 return node_map[edge];
2528 /// \brief The const subscript operator.
2530 /// The const subscript operator.
2531 Value& operator[](const Key& edge) {
2532 if (Parent::origEdge(edge)) {
2533 return edge_map[edge];
2535 return node_map[edge];
2540 GraphEdgeMap& edge_map;
2541 GraphNodeMap& node_map;
2544 /// \brief Just gives back a combined edge map.
2546 /// Just gives back a combined edge map.
2547 template <typename GraphEdgeMap, typename GraphNodeMap>
2548 static CombinedEdgeMap<GraphEdgeMap, GraphNodeMap>
2549 combinedEdgeMap(GraphEdgeMap& edge_map, GraphNodeMap& node_map) {
2550 return CombinedEdgeMap<GraphEdgeMap, GraphNodeMap>(edge_map, node_map);
2553 template <typename GraphEdgeMap, typename GraphNodeMap>
2554 static CombinedEdgeMap<const GraphEdgeMap, GraphNodeMap>
2555 combinedEdgeMap(const GraphEdgeMap& edge_map, GraphNodeMap& node_map) {
2556 return CombinedEdgeMap<const GraphEdgeMap,
2557 GraphNodeMap>(edge_map, node_map);
2560 template <typename GraphEdgeMap, typename GraphNodeMap>
2561 static CombinedEdgeMap<GraphEdgeMap, const GraphNodeMap>
2562 combinedEdgeMap(GraphEdgeMap& edge_map, const GraphNodeMap& node_map) {
2563 return CombinedEdgeMap<GraphEdgeMap,
2564 const GraphNodeMap>(edge_map, node_map);
2567 template <typename GraphEdgeMap, typename GraphNodeMap>
2568 static CombinedEdgeMap<const GraphEdgeMap, const GraphNodeMap>
2569 combinedEdgeMap(const GraphEdgeMap& edge_map,
2570 const GraphNodeMap& node_map) {
2571 return CombinedEdgeMap<const GraphEdgeMap,
2572 const GraphNodeMap>(edge_map, node_map);
2580 #endif //LEMON_GRAPH_ADAPTOR_H