I only corrected some errors in the documentation.
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/bits/variant.h>
32 #include <lemon/maps.h>
34 #include <lemon/bits/base_extender.h>
35 #include <lemon/bits/graph_adaptor_extender.h>
36 #include <lemon/bits/graph_extender.h>
38 #include <lemon/tolerance.h>
44 ///\brief Base type for the 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 ///\ingroup graph_adaptors
197 ///\brief Trivial Graph Adaptor
199 /// This class is an adaptor which does not change the adapted graph.
200 /// It can be used only to test the graph adaptors.
201 template <typename _Graph>
203 public GraphAdaptorExtender<GraphAdaptorBase<_Graph> > {
205 typedef _Graph Graph;
206 typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent;
208 GraphAdaptor() : Parent() { }
211 explicit GraphAdaptor(Graph& _graph) { setGraph(_graph); }
214 /// \brief Just gives back a graph adaptor
216 /// Just gives back a graph adaptor which
217 /// should be provide original graph
218 template<typename Graph>
219 GraphAdaptor<const Graph>
220 graphAdaptor(const Graph& graph) {
221 return GraphAdaptor<const Graph>(graph);
225 template <typename _Graph>
226 class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
228 typedef _Graph Graph;
229 typedef GraphAdaptorBase<_Graph> Parent;
231 RevGraphAdaptorBase() : Parent() { }
233 typedef typename Parent::Node Node;
234 typedef typename Parent::Edge Edge;
236 void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
237 void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
239 void nextIn(Edge& i) const { Parent::nextOut(i); }
240 void nextOut(Edge& i) const { Parent::nextIn(i); }
242 Node source(const Edge& e) const { return Parent::target(e); }
243 Node target(const Edge& e) const { return Parent::source(e); }
245 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
246 Edge findEdge(const Node& source, const Node& target,
247 const Edge& prev = INVALID) {
248 return Parent::findEdge(target, source, prev);
254 ///\ingroup graph_adaptors
256 ///\brief A graph adaptor which reverses the orientation of the edges.
258 /// If \c g is defined as
264 /// RevGraphAdaptor<ListGraph> ga(g);
266 /// implements the graph obtained from \c g by
267 /// reversing the orientation of its edges.
269 /// A good example of using RevGraphAdaptor is to decide that the
270 /// directed graph is wheter strongly connected or not. If from one
271 /// node each node is reachable and from each node is reachable this
272 /// node then and just then the graph is strongly connected. Instead of
273 /// this condition we use a little bit different. From one node each node
274 /// ahould be reachable in the graph and in the reversed graph. Now this
275 /// condition can be checked with the Dfs algorithm class and the
276 /// RevGraphAdaptor algorithm class.
278 /// And look at the code:
281 /// bool stronglyConnected(const Graph& graph) {
282 /// if (NodeIt(graph) == INVALID) return true;
283 /// Dfs<Graph> dfs(graph);
284 /// dfs.run(NodeIt(graph));
285 /// for (NodeIt it(graph); it != INVALID; ++it) {
286 /// if (!dfs.reached(it)) {
290 /// typedef RevGraphAdaptor<const Graph> RGraph;
291 /// RGraph rgraph(graph);
292 /// DfsVisit<RGraph> rdfs(rgraph);
293 /// rdfs.run(NodeIt(graph));
294 /// for (NodeIt it(graph); it != INVALID; ++it) {
295 /// if (!rdfs.reached(it)) {
302 template<typename _Graph>
303 class RevGraphAdaptor :
304 public GraphAdaptorExtender<RevGraphAdaptorBase<_Graph> > {
306 typedef _Graph Graph;
307 typedef GraphAdaptorExtender<
308 RevGraphAdaptorBase<_Graph> > Parent;
310 RevGraphAdaptor() { }
312 explicit RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
315 /// \brief Just gives back a reverse graph adaptor
317 /// Just gives back a reverse graph adaptor
318 template<typename Graph>
319 RevGraphAdaptor<const Graph>
320 revGraphAdaptor(const Graph& graph) {
321 return RevGraphAdaptor<const Graph>(graph);
324 template <typename _Graph, typename NodeFilterMap,
325 typename EdgeFilterMap, bool checked = true>
326 class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
328 typedef _Graph Graph;
329 typedef SubGraphAdaptorBase Adaptor;
330 typedef GraphAdaptorBase<_Graph> Parent;
332 NodeFilterMap* node_filter_map;
333 EdgeFilterMap* edge_filter_map;
334 SubGraphAdaptorBase() : Parent(),
335 node_filter_map(0), edge_filter_map(0) { }
337 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
338 node_filter_map=&_node_filter_map;
340 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
341 edge_filter_map=&_edge_filter_map;
346 typedef typename Parent::Node Node;
347 typedef typename Parent::Edge Edge;
349 void first(Node& i) const {
351 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
354 void first(Edge& i) const {
356 while (i!=INVALID && (!(*edge_filter_map)[i]
357 || !(*node_filter_map)[Parent::source(i)]
358 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
361 void firstIn(Edge& i, const Node& n) const {
362 Parent::firstIn(i, n);
363 while (i!=INVALID && (!(*edge_filter_map)[i]
364 || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
367 void firstOut(Edge& i, const Node& n) const {
368 Parent::firstOut(i, n);
369 while (i!=INVALID && (!(*edge_filter_map)[i]
370 || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
373 void next(Node& i) const {
375 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
378 void next(Edge& i) const {
380 while (i!=INVALID && (!(*edge_filter_map)[i]
381 || !(*node_filter_map)[Parent::source(i)]
382 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
385 void nextIn(Edge& i) const {
387 while (i!=INVALID && (!(*edge_filter_map)[i]
388 || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
391 void nextOut(Edge& i) const {
393 while (i!=INVALID && (!(*edge_filter_map)[i]
394 || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
399 /// This function hides \c n in the graph, i.e. the iteration
400 /// jumps over it. This is done by simply setting the value of \c n
401 /// to be false in the corresponding node-map.
402 void hide(const Node& n) const { node_filter_map->set(n, false); }
406 /// This function hides \c e in the graph, i.e. the iteration
407 /// jumps over it. This is done by simply setting the value of \c e
408 /// to be false in the corresponding edge-map.
409 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
413 /// The value of \c n is set to be true in the node-map which stores
414 /// hide information. If \c n was hidden previuosly, then it is shown
416 void unHide(const Node& n) const { node_filter_map->set(n, true); }
420 /// The value of \c e is set to be true in the edge-map which stores
421 /// hide information. If \c e was hidden previuosly, then it is shown
423 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
425 /// Returns true if \c n is hidden.
429 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
431 /// Returns true if \c n is hidden.
435 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
437 typedef False NodeNumTag;
438 typedef False EdgeNumTag;
440 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
441 Edge findEdge(const Node& source, const Node& target,
442 const Edge& prev = INVALID) {
443 if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
446 Edge edge = Parent::findEdge(source, target, prev);
447 while (edge != INVALID && !(*edge_filter_map)[edge]) {
448 edge = Parent::findEdge(source, target, edge);
453 template <typename _Value>
455 : public SubMapExtender<Adaptor,
456 typename Parent::template NodeMap<_Value> >
459 typedef Adaptor Graph;
460 typedef SubMapExtender<Adaptor, typename Parent::
461 template NodeMap<_Value> > Parent;
463 NodeMap(const Graph& graph)
465 NodeMap(const Graph& graph, const _Value& value)
466 : Parent(graph, value) {}
468 NodeMap& operator=(const NodeMap& cmap) {
469 return operator=<NodeMap>(cmap);
472 template <typename CMap>
473 NodeMap& operator=(const CMap& cmap) {
474 Parent::operator=(cmap);
479 template <typename _Value>
481 : public SubMapExtender<Adaptor,
482 typename Parent::template EdgeMap<_Value> >
485 typedef Adaptor Graph;
486 typedef SubMapExtender<Adaptor, typename Parent::
487 template EdgeMap<_Value> > Parent;
489 EdgeMap(const Graph& graph)
491 EdgeMap(const Graph& graph, const _Value& value)
492 : Parent(graph, value) {}
494 EdgeMap& operator=(const EdgeMap& cmap) {
495 return operator=<EdgeMap>(cmap);
498 template <typename CMap>
499 EdgeMap& operator=(const CMap& cmap) {
500 Parent::operator=(cmap);
507 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
508 class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
509 : public GraphAdaptorBase<_Graph> {
511 typedef _Graph Graph;
512 typedef SubGraphAdaptorBase Adaptor;
513 typedef GraphAdaptorBase<_Graph> Parent;
515 NodeFilterMap* node_filter_map;
516 EdgeFilterMap* edge_filter_map;
517 SubGraphAdaptorBase() : Parent(),
518 node_filter_map(0), edge_filter_map(0) { }
520 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
521 node_filter_map=&_node_filter_map;
523 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
524 edge_filter_map=&_edge_filter_map;
529 typedef typename Parent::Node Node;
530 typedef typename Parent::Edge Edge;
532 void first(Node& i) const {
534 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
537 void first(Edge& i) const {
539 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
542 void firstIn(Edge& i, const Node& n) const {
543 Parent::firstIn(i, n);
544 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
547 void firstOut(Edge& i, const Node& n) const {
548 Parent::firstOut(i, n);
549 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
552 void next(Node& i) const {
554 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
556 void next(Edge& i) const {
558 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
560 void nextIn(Edge& i) const {
562 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
565 void nextOut(Edge& i) const {
567 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
572 /// This function hides \c n in the graph, i.e. the iteration
573 /// jumps over it. This is done by simply setting the value of \c n
574 /// to be false in the corresponding node-map.
575 void hide(const Node& n) const { node_filter_map->set(n, false); }
579 /// This function hides \c e in the graph, i.e. the iteration
580 /// jumps over it. This is done by simply setting the value of \c e
581 /// to be false in the corresponding edge-map.
582 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
586 /// The value of \c n is set to be true in the node-map which stores
587 /// hide information. If \c n was hidden previuosly, then it is shown
589 void unHide(const Node& n) const { node_filter_map->set(n, true); }
593 /// The value of \c e is set to be true in the edge-map which stores
594 /// hide information. If \c e was hidden previuosly, then it is shown
596 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
598 /// Returns true if \c n is hidden.
602 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
604 /// Returns true if \c n is hidden.
608 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
610 typedef False NodeNumTag;
611 typedef False EdgeNumTag;
613 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
614 Edge findEdge(const Node& source, const Node& target,
615 const Edge& prev = INVALID) {
616 if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
619 Edge edge = Parent::findEdge(source, target, prev);
620 while (edge != INVALID && !(*edge_filter_map)[edge]) {
621 edge = Parent::findEdge(source, target, edge);
626 template <typename _Value>
628 : public SubMapExtender<Adaptor,
629 typename Parent::template NodeMap<_Value> >
632 typedef Adaptor Graph;
633 typedef SubMapExtender<Adaptor, typename Parent::
634 template NodeMap<_Value> > Parent;
636 NodeMap(const Graph& graph)
638 NodeMap(const Graph& graph, const _Value& value)
639 : Parent(graph, value) {}
641 NodeMap& operator=(const NodeMap& cmap) {
642 return operator=<NodeMap>(cmap);
645 template <typename CMap>
646 NodeMap& operator=(const CMap& cmap) {
647 Parent::operator=(cmap);
652 template <typename _Value>
654 : public SubMapExtender<Adaptor,
655 typename Parent::template EdgeMap<_Value> >
658 typedef Adaptor Graph;
659 typedef SubMapExtender<Adaptor, typename Parent::
660 template EdgeMap<_Value> > Parent;
662 EdgeMap(const Graph& graph)
664 EdgeMap(const Graph& graph, const _Value& value)
665 : Parent(graph, value) {}
667 EdgeMap& operator=(const EdgeMap& cmap) {
668 return operator=<EdgeMap>(cmap);
671 template <typename CMap>
672 EdgeMap& operator=(const CMap& cmap) {
673 Parent::operator=(cmap);
680 /// \ingroup graph_adaptors
682 /// \brief A graph adaptor for hiding nodes and edges from a graph.
684 /// SubGraphAdaptor shows the graph with filtered node-set and
685 /// edge-set. If the \c checked parameter is true then it filters the edgeset
686 /// to do not get invalid edges without source or target.
687 /// Let \f$ G=(V, A) \f$ be a directed graph
688 /// and suppose that the graph instance \c g of type ListGraph
689 /// implements \f$ G \f$.
690 /// Let moreover \f$ b_V \f$ and \f$ b_A \f$ be bool-valued functions resp.
691 /// on the node-set and edge-set.
692 /// SubGraphAdaptor<...>::NodeIt iterates
693 /// on the node-set \f$ \{v\in V : b_V(v)=true\} \f$ and
694 /// SubGraphAdaptor<...>::EdgeIt iterates
695 /// on the edge-set \f$ \{e\in A : b_A(e)=true\} \f$. Similarly,
696 /// SubGraphAdaptor<...>::OutEdgeIt and
697 /// SubGraphAdaptor<...>::InEdgeIt iterates
698 /// only on edges leaving and entering a specific node which have true value.
700 /// If the \c checked template parameter is false then we have to note that
701 /// the node-iterator cares only the filter on the node-set, and the
702 /// edge-iterator cares only the filter on the edge-set.
703 /// This way the edge-map
704 /// should filter all edges which's source or target is filtered by the
707 /// typedef ListGraph Graph;
709 /// typedef Graph::Node Node;
710 /// typedef Graph::Edge Edge;
711 /// Node u=g.addNode(); //node of id 0
712 /// Node v=g.addNode(); //node of id 1
713 /// Node e=g.addEdge(u, v); //edge of id 0
714 /// Node f=g.addEdge(v, u); //edge of id 1
715 /// Graph::NodeMap<bool> nm(g, true);
716 /// nm.set(u, false);
717 /// Graph::EdgeMap<bool> em(g, true);
718 /// em.set(e, false);
719 /// typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGA;
720 /// SubGA ga(g, nm, em);
721 /// for (SubGA::NodeIt n(ga); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
722 /// std::cout << ":-)" << std::endl;
723 /// for (SubGA::EdgeIt e(ga); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
725 /// The output of the above code is the following.
731 /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
732 /// \c Graph::Node that is why \c g.id(n) can be applied.
734 /// For other examples see also the documentation of NodeSubGraphAdaptor and
735 /// EdgeSubGraphAdaptor.
737 /// \author Marton Makai
739 template<typename _Graph, typename NodeFilterMap,
740 typename EdgeFilterMap, bool checked = true>
741 class SubGraphAdaptor :
742 public GraphAdaptorExtender<
743 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
745 typedef _Graph Graph;
746 typedef GraphAdaptorExtender< SubGraphAdaptorBase<_Graph, NodeFilterMap,
747 EdgeFilterMap, checked> >
751 SubGraphAdaptor() { }
754 SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
755 EdgeFilterMap& _edge_filter_map) {
757 setNodeFilterMap(_node_filter_map);
758 setEdgeFilterMap(_edge_filter_map);
763 /// \brief Just gives back a sub graph adaptor
765 /// Just gives back a sub graph adaptor
766 template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
767 SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>
768 subGraphAdaptor(const Graph& graph,
769 NodeFilterMap& nfm, EdgeFilterMap& efm) {
770 return SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>
774 template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
775 SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>
776 subGraphAdaptor(const Graph& graph,
777 NodeFilterMap& nfm, EdgeFilterMap& efm) {
778 return SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>
782 template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
783 SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>
784 subGraphAdaptor(const Graph& graph,
785 NodeFilterMap& nfm, EdgeFilterMap& efm) {
786 return SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>
790 template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
791 SubGraphAdaptor<const Graph, const NodeFilterMap, const EdgeFilterMap>
792 subGraphAdaptor(const Graph& graph,
793 NodeFilterMap& nfm, EdgeFilterMap& efm) {
794 return SubGraphAdaptor<const Graph, const NodeFilterMap,
795 const EdgeFilterMap>(graph, nfm, efm);
800 ///\ingroup graph_adaptors
802 ///\brief An adaptor for hiding nodes from a graph.
804 ///An adaptor for hiding nodes from a graph.
805 ///This adaptor specializes SubGraphAdaptor in the way that only
807 ///can be filtered. In usual case the checked parameter is true, we get the
808 ///induced subgraph. But if the checked parameter is false then we can only
809 ///filter only isolated nodes.
810 ///\author Marton Makai
811 template<typename Graph, typename NodeFilterMap, bool checked = true>
812 class NodeSubGraphAdaptor :
813 public SubGraphAdaptor<Graph, NodeFilterMap,
814 ConstMap<typename Graph::Edge,bool>, checked> {
817 typedef SubGraphAdaptor<Graph, NodeFilterMap,
818 ConstMap<typename Graph::Edge,bool>, checked >
822 ConstMap<typename Graph::Edge, bool> const_true_map;
824 NodeSubGraphAdaptor() : const_true_map(true) {
825 Parent::setEdgeFilterMap(const_true_map);
830 NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
831 Parent(), const_true_map(true) {
832 Parent::setGraph(_graph);
833 Parent::setNodeFilterMap(_node_filter_map);
834 Parent::setEdgeFilterMap(const_true_map);
840 /// \brief Just gives back a node sub graph adaptor
842 /// Just gives back a node sub graph adaptor
843 template<typename Graph, typename NodeFilterMap>
844 NodeSubGraphAdaptor<const Graph, NodeFilterMap>
845 nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) {
846 return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm);
849 template<typename Graph, typename NodeFilterMap>
850 NodeSubGraphAdaptor<const Graph, const NodeFilterMap>
851 nodeSubGraphAdaptor(const Graph& graph, const NodeFilterMap& nfm) {
852 return NodeSubGraphAdaptor<const Graph, const NodeFilterMap>(graph, nfm);
855 ///\ingroup graph_adaptors
857 ///\brief An adaptor for hiding edges from a graph.
859 ///An adaptor for hiding edges from a graph.
860 ///This adaptor specializes SubGraphAdaptor in the way that
862 ///can be filtered. The usefulness of this adaptor is demonstrated in the
863 ///problem of searching a maximum number of edge-disjoint shortest paths
865 ///two nodes \c s and \c t. Shortest here means being shortest w.r.t.
866 ///non-negative edge-lengths. Note that
867 ///the comprehension of the presented solution
868 ///need's some elementary knowledge from combinatorial optimization.
870 ///If a single shortest path is to be
871 ///searched between \c s and \c t, then this can be done easily by
872 ///applying the Dijkstra algorithm. What happens, if a maximum number of
873 ///edge-disjoint shortest paths is to be computed. It can be proved that an
874 ///edge can be in a shortest path if and only
875 ///if it is tight with respect to
876 ///the potential function computed by Dijkstra.
877 ///Moreover, any path containing
878 ///only such edges is a shortest one.
879 ///Thus we have to compute a maximum number
880 ///of edge-disjoint paths between \c s and \c t in
881 ///the graph which has edge-set
882 ///all the tight edges. The computation will be demonstrated
884 ///graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
885 ///The full source code is available in \ref sub_graph_adaptor_demo.cc.
886 ///If you are interested in more demo programs, you can use
887 ///\ref dim_to_dot.cc to generate .dot files from dimacs files.
888 ///The .dot file of the following figure was generated by
889 ///the demo program \ref dim_to_dot.cc.
892 ///digraph lemon_dot_example {
893 ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
894 ///n0 [ label="0 (s)" ];
900 ///n6 [ label="6 (t)" ];
901 ///edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
902 ///n5 -> n6 [ label="9, length:4" ];
903 ///n4 -> n6 [ label="8, length:2" ];
904 ///n3 -> n5 [ label="7, length:1" ];
905 ///n2 -> n5 [ label="6, length:3" ];
906 ///n2 -> n6 [ label="5, length:5" ];
907 ///n2 -> n4 [ label="4, length:2" ];
908 ///n1 -> n4 [ label="3, length:3" ];
909 ///n0 -> n3 [ label="2, length:1" ];
910 ///n0 -> n2 [ label="1, length:2" ];
911 ///n0 -> n1 [ label="0, length:3" ];
918 ///LengthMap length(g);
920 ///readDimacs(std::cin, g, length, s, t);
922 ///cout << "edges with lengths (of form id, source--length->target): " << endl;
923 ///for(EdgeIt e(g); e!=INVALID; ++e)
924 /// cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
925 /// << length[e] << "->" << g.id(g.target(e)) << endl;
927 ///cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
929 ///Next, the potential function is computed with Dijkstra.
931 ///typedef Dijkstra<Graph, LengthMap> Dijkstra;
932 ///Dijkstra dijkstra(g, length);
935 ///Next, we consrtruct a map which filters the edge-set to the tight edges.
937 ///typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
939 ///TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
941 ///typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGA;
942 ///SubGA ga(g, tight_edge_filter);
944 ///Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
945 ///with a max flow algorithm Preflow.
947 ///ConstMap<Edge, int> const_1_map(1);
948 ///Graph::EdgeMap<int> flow(g, 0);
950 ///Preflow<SubGA, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
951 /// preflow(ga, s, t, const_1_map, flow);
954 ///Last, the output is:
956 ///cout << "maximum number of edge-disjoint shortest path: "
957 /// << preflow.flowValue() << endl;
958 ///cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
960 ///for(EdgeIt e(g); e!=INVALID; ++e)
962 /// cout << " " << g.id(g.source(e)) << "--"
963 /// << length[e] << "->" << g.id(g.target(e)) << endl;
965 ///The program has the following (expected :-)) output:
967 ///edges with lengths (of form id, source--length->target):
979 ///maximum number of edge-disjoint shortest path: 2
980 ///edges of the maximum number of edge-disjoint shortest s-t paths:
989 ///\author Marton Makai
990 template<typename Graph, typename EdgeFilterMap>
991 class EdgeSubGraphAdaptor :
992 public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
993 EdgeFilterMap, false> {
995 typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
996 EdgeFilterMap, false> Parent;
998 ConstMap<typename Graph::Node, bool> const_true_map;
1000 EdgeSubGraphAdaptor() : const_true_map(true) {
1001 Parent::setNodeFilterMap(const_true_map);
1006 EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
1007 Parent(), const_true_map(true) {
1008 Parent::setGraph(_graph);
1009 Parent::setNodeFilterMap(const_true_map);
1010 Parent::setEdgeFilterMap(_edge_filter_map);
1015 /// \brief Just gives back an edge sub graph adaptor
1017 /// Just gives back an edge sub graph adaptor
1018 template<typename Graph, typename EdgeFilterMap>
1019 EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>
1020 edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) {
1021 return EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>(graph, efm);
1024 template<typename Graph, typename EdgeFilterMap>
1025 EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>
1026 edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) {
1027 return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm);
1030 template <typename _Graph>
1031 class UndirGraphAdaptorBase :
1032 public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
1034 typedef _Graph Graph;
1035 typedef UndirGraphAdaptorBase Adaptor;
1036 typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
1040 UndirGraphAdaptorBase() : Parent() {}
1044 typedef typename Parent::UEdge UEdge;
1045 typedef typename Parent::Edge Edge;
1049 template <typename _Value>
1053 typedef typename _Graph::template EdgeMap<_Value> MapImpl;
1057 typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
1059 typedef _Value Value;
1062 EdgeMapBase(const Adaptor& adaptor) :
1063 forward_map(*adaptor.graph), backward_map(*adaptor.graph) {}
1065 EdgeMapBase(const Adaptor& adaptor, const Value& v)
1066 : forward_map(*adaptor.graph, v), backward_map(*adaptor.graph, v) {}
1068 void set(const Edge& e, const Value& a) {
1069 if (Parent::direction(e)) {
1070 forward_map.set(e, a);
1072 backward_map.set(e, a);
1076 typename MapTraits<MapImpl>::ConstReturnValue operator[](Edge e) const {
1077 if (Parent::direction(e)) {
1078 return forward_map[e];
1080 return backward_map[e];
1084 typename MapTraits<MapImpl>::ReturnValue operator[](Edge e) {
1085 if (Parent::direction(e)) {
1086 return forward_map[e];
1088 return backward_map[e];
1094 MapImpl forward_map, backward_map;
1100 template <typename _Value>
1102 : public SubMapExtender<Adaptor, EdgeMapBase<_Value> >
1105 typedef Adaptor Graph;
1106 typedef SubMapExtender<Adaptor, EdgeMapBase<_Value> > Parent;
1108 EdgeMap(const Graph& graph)
1110 EdgeMap(const Graph& graph, const _Value& value)
1111 : Parent(graph, value) {}
1113 EdgeMap& operator=(const EdgeMap& cmap) {
1114 return operator=<EdgeMap>(cmap);
1117 template <typename CMap>
1118 EdgeMap& operator=(const CMap& cmap) {
1119 Parent::operator=(cmap);
1124 template <typename _Value>
1125 class UEdgeMap : public Graph::template EdgeMap<_Value> {
1128 typedef typename Graph::template EdgeMap<_Value> Parent;
1130 explicit UEdgeMap(const Adaptor& ga)
1131 : Parent(*ga.graph) {}
1133 UEdgeMap(const Adaptor& ga, const _Value& value)
1134 : Parent(*ga.graph, value) {}
1136 UEdgeMap& operator=(const UEdgeMap& cmap) {
1137 return operator=<UEdgeMap>(cmap);
1140 template <typename CMap>
1141 UEdgeMap& operator=(const CMap& cmap) {
1142 Parent::operator=(cmap);
1150 template <typename _Graph, typename Enable = void>
1151 class AlterableUndirGraphAdaptor
1152 : public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > {
1154 typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent;
1158 AlterableUndirGraphAdaptor() : Parent() {}
1162 typedef typename Parent::EdgeNotifier UEdgeNotifier;
1163 typedef InvalidType EdgeNotifier;
1167 template <typename _Graph>
1168 class AlterableUndirGraphAdaptor<
1170 typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type >
1171 : public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > {
1174 typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent;
1175 typedef _Graph Graph;
1176 typedef typename _Graph::Edge GraphEdge;
1180 AlterableUndirGraphAdaptor()
1181 : Parent(), edge_notifier(*this), edge_notifier_proxy(*this) {}
1183 void setGraph(_Graph& graph) {
1184 Parent::setGraph(graph);
1185 edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge()));
1190 ~AlterableUndirGraphAdaptor() {
1191 edge_notifier.clear();
1194 typedef typename Parent::UEdge UEdge;
1195 typedef typename Parent::Edge Edge;
1197 typedef typename Parent::EdgeNotifier UEdgeNotifier;
1199 using Parent::getNotifier;
1201 typedef AlterationNotifier<AlterableUndirGraphAdaptor,
1203 EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
1207 class NotifierProxy : public Graph::EdgeNotifier::ObserverBase {
1210 typedef typename Graph::EdgeNotifier::ObserverBase Parent;
1211 typedef AlterableUndirGraphAdaptor AdaptorBase;
1213 NotifierProxy(const AdaptorBase& _adaptor)
1214 : Parent(), adaptor(&_adaptor) {
1217 virtual ~NotifierProxy() {
1218 if (Parent::attached()) {
1223 void setNotifier(typename Graph::EdgeNotifier& notifier) {
1224 Parent::attach(notifier);
1230 virtual void add(const GraphEdge& ge) {
1231 std::vector<Edge> edges;
1232 edges.push_back(AdaptorBase::Parent::direct(ge, true));
1233 edges.push_back(AdaptorBase::Parent::direct(ge, false));
1234 adaptor->getNotifier(Edge()).add(edges);
1236 virtual void add(const std::vector<GraphEdge>& ge) {
1237 std::vector<Edge> edges;
1238 for (int i = 0; i < (int)ge.size(); ++i) {
1239 edges.push_back(AdaptorBase::Parent::direct(ge[i], true));
1240 edges.push_back(AdaptorBase::Parent::direct(ge[i], false));
1242 adaptor->getNotifier(Edge()).add(edges);
1244 virtual void erase(const GraphEdge& ge) {
1245 std::vector<Edge> edges;
1246 edges.push_back(AdaptorBase::Parent::direct(ge, true));
1247 edges.push_back(AdaptorBase::Parent::direct(ge, false));
1248 adaptor->getNotifier(Edge()).erase(edges);
1250 virtual void erase(const std::vector<GraphEdge>& ge) {
1251 std::vector<Edge> edges;
1252 for (int i = 0; i < (int)ge.size(); ++i) {
1253 edges.push_back(AdaptorBase::Parent::direct(ge[i], true));
1254 edges.push_back(AdaptorBase::Parent::direct(ge[i], false));
1256 adaptor->getNotifier(Edge()).erase(edges);
1258 virtual void build() {
1259 adaptor->getNotifier(Edge()).build();
1261 virtual void clear() {
1262 adaptor->getNotifier(Edge()).clear();
1265 const AdaptorBase* adaptor;
1269 mutable EdgeNotifier edge_notifier;
1270 NotifierProxy edge_notifier_proxy;
1275 ///\ingroup graph_adaptors
1277 /// \brief An undirected graph is made from a directed graph by an adaptor
1279 /// This adaptor makes an undirected graph from a directed
1280 /// graph. All edge of the underlying will be showed in the adaptor
1281 /// as an undirected edge. Let's see an informal example about using
1284 /// There is a network of the streets of a town. Of course there are
1285 /// some one-way street in the town hence the network is a directed
1286 /// one. There is a crazy driver who go oppositely in the one-way
1287 /// street without moral sense. Of course he can pass this streets
1288 /// slower than the regular way, in fact his speed is half of the
1289 /// normal speed. How long should he drive to get from a source
1290 /// point to the target? Let see the example code which calculate it:
1293 /// typedef UndirGraphAdaptor<Graph> UGraph;
1294 /// UGraph ugraph(graph);
1296 /// typedef SimpleMap<LengthMap> FLengthMap;
1297 /// FLengthMap flength(length);
1299 /// typedef ScaleMap<LengthMap> RLengthMap;
1300 /// RLengthMap rlength(length, 2.0);
1302 /// typedef UGraph::CombinedEdgeMap<FLengthMap, RLengthMap > ULengthMap;
1303 /// ULengthMap ulength(flength, rlength);
1305 /// Dijkstra<UGraph, ULengthMap> dijkstra(ugraph, ulength);
1306 /// std::cout << "Driving time : " << dijkstra.run(src, trg) << std::endl;
1309 /// The combined edge map makes the length map for the undirected
1310 /// graph. It is created from a forward and reverse map. The forward
1311 /// map is created from the original length map with a SimpleMap
1312 /// adaptor which just makes a read-write map from the reference map
1313 /// i.e. it forgets that it can be return reference to values. The
1314 /// reverse map is just the scaled original map with the ScaleMap
1315 /// adaptor. The combination solves that passing the reverse way
1316 /// takes double time than the original. To get the driving time we
1317 /// run the dijkstra algorithm on the undirected graph.
1319 /// \author Marton Makai and Balazs Dezso
1320 template<typename _Graph>
1321 class UndirGraphAdaptor : public AlterableUndirGraphAdaptor<_Graph> {
1323 typedef _Graph Graph;
1324 typedef AlterableUndirGraphAdaptor<_Graph> Parent;
1326 UndirGraphAdaptor() { }
1329 /// \brief Constructor
1332 UndirGraphAdaptor(_Graph& _graph) {
1336 /// \brief EdgeMap combined from two original EdgeMap
1338 /// This class adapts two original graph EdgeMap to
1339 /// get an edge map on the adaptor.
1340 template <typename _ForwardMap, typename _BackwardMap>
1341 class CombinedEdgeMap {
1344 typedef _ForwardMap ForwardMap;
1345 typedef _BackwardMap BackwardMap;
1347 typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
1349 typedef typename ForwardMap::Value Value;
1350 typedef typename Parent::Edge Key;
1352 /// \brief Constructor
1355 CombinedEdgeMap() : forward_map(0), backward_map(0) {}
1357 /// \brief Constructor
1360 CombinedEdgeMap(ForwardMap& _forward_map, BackwardMap& _backward_map)
1361 : forward_map(&_forward_map), backward_map(&_backward_map) {}
1364 /// \brief Sets the value associated with a key.
1366 /// Sets the value associated with a key.
1367 void set(const Key& e, const Value& a) {
1368 if (Parent::direction(e)) {
1369 forward_map->set(e, a);
1371 backward_map->set(e, a);
1375 /// \brief Returns the value associated with a key.
1377 /// Returns the value associated with a key.
1378 typename MapTraits<ForwardMap>::ConstReturnValue
1379 operator[](const Key& e) const {
1380 if (Parent::direction(e)) {
1381 return (*forward_map)[e];
1383 return (*backward_map)[e];
1387 /// \brief Returns the value associated with a key.
1389 /// Returns the value associated with a key.
1390 typename MapTraits<ForwardMap>::ReturnValue
1391 operator[](const Key& e) {
1392 if (Parent::direction(e)) {
1393 return (*forward_map)[e];
1395 return (*backward_map)[e];
1399 /// \brief Sets the forward map
1401 /// Sets the forward map
1402 void setForwardMap(ForwardMap& _forward_map) {
1403 forward_map = &_forward_map;
1406 /// \brief Sets the backward map
1408 /// Sets the backward map
1409 void setBackwardMap(BackwardMap& _backward_map) {
1410 backward_map = &_backward_map;
1415 ForwardMap* forward_map;
1416 BackwardMap* backward_map;
1422 /// \brief Just gives back an undir graph adaptor
1424 /// Just gives back an undir graph adaptor
1425 template<typename Graph>
1426 UndirGraphAdaptor<const Graph>
1427 undirGraphAdaptor(const Graph& graph) {
1428 return UndirGraphAdaptor<const Graph>(graph);
1431 template<typename Graph, typename Number,
1432 typename CapacityMap, typename FlowMap,
1433 typename Tol = Tolerance<Number> >
1434 class ResForwardFilter {
1435 const CapacityMap* capacity;
1436 const FlowMap* flow;
1439 typedef typename Graph::Edge Key;
1442 ResForwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
1443 const Tol& _tolerance = Tol())
1444 : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
1446 ResForwardFilter(const Tol& _tolerance)
1447 : capacity(0), flow(0), tolerance(_tolerance) { }
1449 void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
1450 void setFlow(const FlowMap& _flow) { flow = &_flow; }
1452 bool operator[](const typename Graph::Edge& e) const {
1453 return tolerance.less((*flow)[e], (*capacity)[e]);
1457 template<typename Graph, typename Number,
1458 typename CapacityMap, typename FlowMap,
1459 typename Tol = Tolerance<Number> >
1460 class ResBackwardFilter {
1461 const CapacityMap* capacity;
1462 const FlowMap* flow;
1465 typedef typename Graph::Edge Key;
1468 ResBackwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
1469 const Tol& _tolerance = Tol())
1470 : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
1471 ResBackwardFilter(const Tol& _tolerance = Tol())
1472 : capacity(0), flow(0), tolerance(_tolerance) { }
1473 void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
1474 void setFlow(const FlowMap& _flow) { flow = &_flow; }
1475 bool operator[](const typename Graph::Edge& e) const {
1476 return tolerance.less(0, Number((*flow)[e]));
1481 ///\ingroup graph_adaptors
1483 ///\brief An adaptor for composing the residual
1484 ///graph for directed flow and circulation problems.
1486 ///An adaptor for composing the residual graph for directed flow and
1487 ///circulation problems. Let \f$ G=(V, A) \f$ be a directed graph
1488 ///and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
1489 ///be functions on the edge-set.
1491 ///In the appications of ResGraphAdaptor, \f$ f \f$ usually stands
1492 ///for a flow and \f$ c \f$ for a capacity function. Suppose that a
1493 ///graph instange \c g of type \c ListGraph implements \f$ G \f$.
1499 ///Then RevGraphAdaptor implements the graph structure with node-set
1500 /// \f$ V \f$ and edge-set \f$ A_{forward}\cup A_{backward} \f$,
1501 ///where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
1502 /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so called
1503 ///residual graph. When we take the union
1504 /// \f$ A_{forward}\cup A_{backward} \f$, multilicities are counted, i.e.
1505 ///if an edge is in both \f$ A_{forward} \f$ and \f$ A_{backward} \f$,
1506 ///then in the adaptor it appears twice. The following code shows how
1507 ///such an instance can be constructed.
1510 /// typedef ListGraph Graph;
1511 /// Graph::EdgeMap<int> f(g);
1512 /// Graph::EdgeMap<int> c(g);
1513 /// ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > ga(g);
1515 ///\author Marton Makai
1517 template<typename Graph, typename Number,
1518 typename CapacityMap, typename FlowMap,
1519 typename Tol = Tolerance<Number> >
1520 class ResGraphAdaptor :
1521 public EdgeSubGraphAdaptor<
1522 UndirGraphAdaptor<const Graph>,
1523 typename UndirGraphAdaptor<const Graph>::template CombinedEdgeMap<
1524 ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>,
1525 ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap> > > {
1528 typedef UndirGraphAdaptor<const Graph> UGraph;
1530 typedef ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>
1533 typedef ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap>
1536 typedef typename UGraph::
1537 template CombinedEdgeMap<ForwardFilter, BackwardFilter>
1540 typedef EdgeSubGraphAdaptor<UGraph, EdgeFilter> Parent;
1544 const CapacityMap* capacity;
1548 ForwardFilter forward_filter;
1549 BackwardFilter backward_filter;
1550 EdgeFilter edge_filter;
1552 void setCapacityMap(const CapacityMap& _capacity) {
1553 capacity=&_capacity;
1554 forward_filter.setCapacity(_capacity);
1555 backward_filter.setCapacity(_capacity);
1558 void setFlowMap(FlowMap& _flow) {
1560 forward_filter.setFlow(_flow);
1561 backward_filter.setFlow(_flow);
1566 /// \brief Constructor of the residual graph.
1568 /// Constructor of the residual graph. The parameters are the graph type,
1569 /// the flow map, the capacity map and a tolerance object.
1570 ResGraphAdaptor(const Graph& _graph, const CapacityMap& _capacity,
1571 FlowMap& _flow, const Tol& _tolerance = Tol())
1572 : Parent(), capacity(&_capacity), flow(&_flow), ugraph(_graph),
1573 forward_filter(_capacity, _flow, _tolerance),
1574 backward_filter(_capacity, _flow, _tolerance),
1575 edge_filter(forward_filter, backward_filter)
1577 Parent::setGraph(ugraph);
1578 Parent::setEdgeFilterMap(edge_filter);
1581 typedef typename Parent::Edge Edge;
1583 /// \brief Gives back the residual capacity of the edge.
1585 /// Gives back the residual capacity of the edge.
1586 Number rescap(const Edge& edge) const {
1587 if (UGraph::direction(edge)) {
1588 return (*capacity)[edge]-(*flow)[edge];
1590 return (*flow)[edge];
1594 /// \brief Augment on the given edge in the residual graph.
1596 /// Augment on the given edge in the residual graph. It increase
1597 /// or decrease the flow on the original edge depend on the direction
1598 /// of the residual edge.
1599 void augment(const Edge& e, Number a) const {
1600 if (UGraph::direction(e)) {
1601 flow->set(e, (*flow)[e] + a);
1603 flow->set(e, (*flow)[e] - a);
1607 /// \brief Returns the direction of the edge.
1609 /// Returns true when the edge is same oriented as the original edge.
1610 static bool forward(const Edge& e) {
1611 return UGraph::direction(e);
1614 /// \brief Returns the direction of the edge.
1616 /// Returns true when the edge is opposite oriented as the original edge.
1617 static bool backward(const Edge& e) {
1618 return !UGraph::direction(e);
1621 /// \brief Gives back the forward oriented residual edge.
1623 /// Gives back the forward oriented residual edge.
1624 static Edge forward(const typename Graph::Edge& e) {
1625 return UGraph::direct(e, true);
1628 /// \brief Gives back the backward oriented residual edge.
1630 /// Gives back the backward oriented residual edge.
1631 static Edge backward(const typename Graph::Edge& e) {
1632 return UGraph::direct(e, false);
1635 /// \brief Residual capacity map.
1637 /// In generic residual graphs the residual capacity can be obtained
1641 const ResGraphAdaptor* res_graph;
1643 typedef Number Value;
1645 ResCap(const ResGraphAdaptor& _res_graph)
1646 : res_graph(&_res_graph) {}
1648 Number operator[](const Edge& e) const {
1649 return res_graph->rescap(e);
1658 template <typename _Graph, typename FirstOutEdgesMap>
1659 class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
1661 typedef _Graph Graph;
1662 typedef GraphAdaptorBase<_Graph> Parent;
1664 FirstOutEdgesMap* first_out_edges;
1665 ErasingFirstGraphAdaptorBase() : Parent(),
1666 first_out_edges(0) { }
1668 void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1669 first_out_edges=&_first_out_edges;
1674 typedef typename Parent::Node Node;
1675 typedef typename Parent::Edge Edge;
1677 void firstOut(Edge& i, const Node& n) const {
1678 i=(*first_out_edges)[n];
1681 void erase(const Edge& e) const {
1685 first_out_edges->set(n, f);
1690 ///\ingroup graph_adaptors
1692 ///\brief For blocking flows.
1694 ///This graph adaptor is used for on-the-fly
1695 ///Dinits blocking flow computations.
1696 ///For each node, an out-edge is stored which is used when the
1698 ///OutEdgeIt& first(OutEdgeIt&, const Node&)
1702 ///\author Marton Makai
1704 template <typename _Graph, typename FirstOutEdgesMap>
1705 class ErasingFirstGraphAdaptor :
1706 public GraphAdaptorExtender<
1707 ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
1709 typedef _Graph Graph;
1710 typedef GraphAdaptorExtender<
1711 ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
1712 ErasingFirstGraphAdaptor(Graph& _graph,
1713 FirstOutEdgesMap& _first_out_edges) {
1715 setFirstOutEdgesMap(_first_out_edges);
1720 /// \brief Base class for split graph adaptor
1722 /// Base class of split graph adaptor. In most case you do not need to
1723 /// use it directly but the documented member functions of this class can
1724 /// be used with the SplitGraphAdaptor class.
1725 /// \sa SplitGraphAdaptor
1726 template <typename _Graph>
1727 class SplitGraphAdaptorBase
1728 : public GraphAdaptorBase<const _Graph> {
1731 typedef _Graph Graph;
1733 typedef GraphAdaptorBase<const _Graph> Parent;
1735 typedef typename Graph::Node GraphNode;
1736 typedef typename Graph::Edge GraphEdge;
1741 template <typename T> class NodeMap;
1742 template <typename T> class EdgeMap;
1745 class Node : public GraphNode {
1746 friend class SplitGraphAdaptorBase;
1747 template <typename T> friend class NodeMap;
1751 Node(GraphNode _node, bool _in_node)
1752 : GraphNode(_node), in_node(_in_node) {}
1757 Node(Invalid) : GraphNode(INVALID), in_node(true) {}
1759 bool operator==(const Node& node) const {
1760 return GraphNode::operator==(node) && in_node == node.in_node;
1763 bool operator!=(const Node& node) const {
1764 return !(*this == node);
1767 bool operator<(const Node& node) const {
1768 return GraphNode::operator<(node) ||
1769 (GraphNode::operator==(node) && in_node < node.in_node);
1774 friend class SplitGraphAdaptorBase;
1775 template <typename T> friend class EdgeMap;
1777 typedef BiVariant<GraphEdge, GraphNode> EdgeImpl;
1779 explicit Edge(const GraphEdge& edge) : item(edge) {}
1780 explicit Edge(const GraphNode& node) : item(node) {}
1786 Edge(Invalid) : item(GraphEdge(INVALID)) {}
1788 bool operator==(const Edge& edge) const {
1789 if (item.firstState()) {
1790 if (edge.item.firstState()) {
1791 return item.first() == edge.item.first();
1794 if (edge.item.secondState()) {
1795 return item.second() == edge.item.second();
1801 bool operator!=(const Edge& edge) const {
1802 return !(*this == edge);
1805 bool operator<(const Edge& edge) const {
1806 if (item.firstState()) {
1807 if (edge.item.firstState()) {
1808 return item.first() < edge.item.first();
1812 if (edge.item.secondState()) {
1813 return item.second() < edge.item.second();
1819 operator GraphEdge() const { return item.first(); }
1820 operator GraphNode() const { return item.second(); }
1824 void first(Node& node) const {
1825 Parent::first(node);
1826 node.in_node = true;
1829 void next(Node& node) const {
1831 node.in_node = false;
1833 node.in_node = true;
1838 void first(Edge& edge) const {
1839 edge.item.setSecond();
1840 Parent::first(edge.item.second());
1841 if (edge.item.second() == INVALID) {
1842 edge.item.setFirst();
1843 Parent::first(edge.item.first());
1847 void next(Edge& edge) const {
1848 if (edge.item.secondState()) {
1849 Parent::next(edge.item.second());
1850 if (edge.item.second() == INVALID) {
1851 edge.item.setFirst();
1852 Parent::first(edge.item.first());
1855 Parent::next(edge.item.first());
1859 void firstOut(Edge& edge, const Node& node) const {
1861 edge.item.setSecond(node);
1863 edge.item.setFirst();
1864 Parent::firstOut(edge.item.first(), node);
1868 void nextOut(Edge& edge) const {
1869 if (!edge.item.firstState()) {
1870 edge.item.setFirst(INVALID);
1872 Parent::nextOut(edge.item.first());
1876 void firstIn(Edge& edge, const Node& node) const {
1877 if (!node.in_node) {
1878 edge.item.setSecond(node);
1880 edge.item.setFirst();
1881 Parent::firstIn(edge.item.first(), node);
1885 void nextIn(Edge& edge) const {
1886 if (!edge.item.firstState()) {
1887 edge.item.setFirst(INVALID);
1889 Parent::nextIn(edge.item.first());
1893 Node source(const Edge& edge) const {
1894 if (edge.item.firstState()) {
1895 return Node(Parent::source(edge.item.first()), false);
1897 return Node(edge.item.second(), true);
1901 Node target(const Edge& edge) const {
1902 if (edge.item.firstState()) {
1903 return Node(Parent::target(edge.item.first()), true);
1905 return Node(edge.item.second(), false);
1909 int id(const Node& node) const {
1910 return (Parent::id(node) << 1) | (node.in_node ? 0 : 1);
1912 Node nodeFromId(int id) const {
1913 return Node(Parent::nodeFromId(id >> 1), (id & 1) == 0);
1915 int maxNodeId() const {
1916 return 2 * Parent::maxNodeId() + 1;
1919 int id(const Edge& edge) const {
1920 if (edge.item.firstState()) {
1921 return Parent::id(edge.item.first()) << 1;
1923 return (Parent::id(edge.item.second()) << 1) | 1;
1926 Edge edgeFromId(int id) const {
1927 if ((id & 1) == 0) {
1928 return Edge(Parent::edgeFromId(id >> 1));
1930 return Edge(Parent::nodeFromId(id >> 1));
1933 int maxEdgeId() const {
1934 return std::max(Parent::maxNodeId() << 1,
1935 (Parent::maxEdgeId() << 1) | 1);
1938 /// \brief Returns true when the node is in-node.
1940 /// Returns true when the node is in-node.
1941 static bool inNode(const Node& node) {
1942 return node.in_node;
1945 /// \brief Returns true when the node is out-node.
1947 /// Returns true when the node is out-node.
1948 static bool outNode(const Node& node) {
1949 return !node.in_node;
1952 /// \brief Returns true when the edge is edge in the original graph.
1954 /// Returns true when the edge is edge in the original graph.
1955 static bool origEdge(const Edge& edge) {
1956 return edge.item.firstState();
1959 /// \brief Returns true when the edge binds an in-node and an out-node.
1961 /// Returns true when the edge binds an in-node and an out-node.
1962 static bool bindEdge(const Edge& edge) {
1963 return edge.item.secondState();
1966 /// \brief Gives back the in-node created from the \c node.
1968 /// Gives back the in-node created from the \c node.
1969 static Node inNode(const GraphNode& node) {
1970 return Node(node, true);
1973 /// \brief Gives back the out-node created from the \c node.
1975 /// Gives back the out-node created from the \c node.
1976 static Node outNode(const GraphNode& node) {
1977 return Node(node, false);
1980 /// \brief Gives back the edge binds the two part of the node.
1982 /// Gives back the edge binds the two part of the node.
1983 static Edge edge(const GraphNode& node) {
1987 /// \brief Gives back the edge of the original edge.
1989 /// Gives back the edge of the original edge.
1990 static Edge edge(const GraphEdge& edge) {
1994 typedef True NodeNumTag;
1996 int nodeNum() const {
1997 return 2 * countNodes(*Parent::graph);
2000 typedef True EdgeNumTag;
2002 int edgeNum() const {
2003 return countEdges(*Parent::graph) + countNodes(*Parent::graph);
2006 typedef True FindEdgeTag;
2008 Edge findEdge(const Node& source, const Node& target,
2009 const Edge& prev = INVALID) const {
2010 if (inNode(source)) {
2011 if (outNode(target)) {
2012 if ((GraphNode&)source == (GraphNode&)target && prev == INVALID) {
2013 return Edge(source);
2017 if (inNode(target)) {
2018 return Edge(findEdge(*Parent::graph, source, target, prev));
2024 template <typename T>
2025 class NodeMap : public MapBase<Node, T> {
2026 typedef typename Parent::template NodeMap<T> NodeImpl;
2028 NodeMap(const SplitGraphAdaptorBase& _graph)
2029 : inNodeMap(_graph), outNodeMap(_graph) {}
2030 NodeMap(const SplitGraphAdaptorBase& _graph, const T& t)
2031 : inNodeMap(_graph, t), outNodeMap(_graph, t) {}
2033 void set(const Node& key, const T& val) {
2034 if (SplitGraphAdaptorBase::inNode(key)) { inNodeMap.set(key, val); }
2035 else {outNodeMap.set(key, val); }
2038 typename MapTraits<NodeImpl>::ReturnValue
2039 operator[](const Node& key) {
2040 if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; }
2041 else { return outNodeMap[key]; }
2044 typename MapTraits<NodeImpl>::ConstReturnValue
2045 operator[](const Node& key) const {
2046 if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; }
2047 else { return outNodeMap[key]; }
2051 NodeImpl inNodeMap, outNodeMap;
2054 template <typename T>
2055 class EdgeMap : public MapBase<Edge, T> {
2056 typedef typename Parent::template EdgeMap<T> EdgeMapImpl;
2057 typedef typename Parent::template NodeMap<T> NodeMapImpl;
2060 EdgeMap(const SplitGraphAdaptorBase& _graph)
2061 : edge_map(_graph), node_map(_graph) {}
2062 EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t)
2063 : edge_map(_graph, t), node_map(_graph, t) {}
2065 void set(const Edge& key, const T& val) {
2066 if (SplitGraphAdaptorBase::origEdge(key)) {
2067 edge_map.set(key.item.first(), val);
2069 node_map.set(key.item.second(), val);
2073 typename MapTraits<EdgeMapImpl>::ReturnValue
2074 operator[](const Edge& key) {
2075 if (SplitGraphAdaptorBase::origEdge(key)) {
2076 return edge_map[key.item.first()];
2078 return node_map[key.item.second()];
2082 typename MapTraits<EdgeMapImpl>::ConstReturnValue
2083 operator[](const Edge& key) const {
2084 if (SplitGraphAdaptorBase::origEdge(key)) {
2085 return edge_map[key.item.first()];
2087 return node_map[key.item.second()];
2092 typename Parent::template EdgeMap<T> edge_map;
2093 typename Parent::template NodeMap<T> node_map;
2099 template <typename _Graph, typename NodeEnable = void,
2100 typename EdgeEnable = void>
2101 class AlterableSplitGraphAdaptor
2102 : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
2105 typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
2106 typedef _Graph Graph;
2108 typedef typename Graph::Node GraphNode;
2109 typedef typename Graph::Node GraphEdge;
2113 AlterableSplitGraphAdaptor() : Parent() {}
2117 typedef InvalidType NodeNotifier;
2118 typedef InvalidType EdgeNotifier;
2122 template <typename _Graph, typename EdgeEnable>
2123 class AlterableSplitGraphAdaptor<
2125 typename enable_if<typename _Graph::NodeNotifier::Notifier>::type,
2127 : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
2130 typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
2131 typedef _Graph Graph;
2133 typedef typename Graph::Node GraphNode;
2134 typedef typename Graph::Edge GraphEdge;
2136 typedef typename Parent::Node Node;
2137 typedef typename Parent::Edge Edge;
2141 AlterableSplitGraphAdaptor()
2142 : Parent(), node_notifier(*this), node_notifier_proxy(*this) {}
2144 void setGraph(_Graph& graph) {
2145 Parent::setGraph(graph);
2146 node_notifier_proxy.setNotifier(graph.getNotifier(GraphNode()));
2151 ~AlterableSplitGraphAdaptor() {
2152 node_notifier.clear();
2155 typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier;
2156 typedef InvalidType EdgeNotifier;
2158 NodeNotifier& getNotifier(Node) const { return node_notifier; }
2162 class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase {
2165 typedef typename Graph::NodeNotifier::ObserverBase Parent;
2166 typedef AlterableSplitGraphAdaptor AdaptorBase;
2168 NodeNotifierProxy(const AdaptorBase& _adaptor)
2169 : Parent(), adaptor(&_adaptor) {
2172 virtual ~NodeNotifierProxy() {
2173 if (Parent::attached()) {
2178 void setNotifier(typename Graph::NodeNotifier& graph_notifier) {
2179 Parent::attach(graph_notifier);
2185 virtual void add(const GraphNode& gn) {
2186 std::vector<Node> nodes;
2187 nodes.push_back(AdaptorBase::Parent::inNode(gn));
2188 nodes.push_back(AdaptorBase::Parent::outNode(gn));
2189 adaptor->getNotifier(Node()).add(nodes);
2192 virtual void add(const std::vector<GraphNode>& gn) {
2193 std::vector<Node> nodes;
2194 for (int i = 0; i < (int)gn.size(); ++i) {
2195 nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2196 nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2198 adaptor->getNotifier(Node()).add(nodes);
2201 virtual void erase(const GraphNode& gn) {
2202 std::vector<Node> nodes;
2203 nodes.push_back(AdaptorBase::Parent::inNode(gn));
2204 nodes.push_back(AdaptorBase::Parent::outNode(gn));
2205 adaptor->getNotifier(Node()).erase(nodes);
2208 virtual void erase(const std::vector<GraphNode>& gn) {
2209 std::vector<Node> nodes;
2210 for (int i = 0; i < (int)gn.size(); ++i) {
2211 nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2212 nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2214 adaptor->getNotifier(Node()).erase(nodes);
2216 virtual void build() {
2217 adaptor->getNotifier(Node()).build();
2219 virtual void clear() {
2220 adaptor->getNotifier(Node()).clear();
2223 const AdaptorBase* adaptor;
2227 mutable NodeNotifier node_notifier;
2229 NodeNotifierProxy node_notifier_proxy;
2233 template <typename _Graph>
2234 class AlterableSplitGraphAdaptor<
2236 typename enable_if<typename _Graph::NodeNotifier::Notifier>::type,
2237 typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type>
2238 : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
2241 typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
2242 typedef _Graph Graph;
2244 typedef typename Graph::Node GraphNode;
2245 typedef typename Graph::Edge GraphEdge;
2247 typedef typename Parent::Node Node;
2248 typedef typename Parent::Edge Edge;
2252 AlterableSplitGraphAdaptor()
2253 : Parent(), node_notifier(*this), edge_notifier(*this),
2254 node_notifier_proxy(*this), edge_notifier_proxy(*this) {}
2256 void setGraph(_Graph& graph) {
2257 Parent::setGraph(graph);
2258 node_notifier_proxy.setNotifier(graph.getNotifier(GraphNode()));
2259 edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge()));
2264 ~AlterableSplitGraphAdaptor() {
2265 node_notifier.clear();
2266 edge_notifier.clear();
2269 typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier;
2270 typedef AlterationNotifier<AlterableSplitGraphAdaptor, Edge> EdgeNotifier;
2272 NodeNotifier& getNotifier(Node) const { return node_notifier; }
2273 EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
2277 class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase {
2280 typedef typename Graph::NodeNotifier::ObserverBase Parent;
2281 typedef AlterableSplitGraphAdaptor AdaptorBase;
2283 NodeNotifierProxy(const AdaptorBase& _adaptor)
2284 : Parent(), adaptor(&_adaptor) {
2287 virtual ~NodeNotifierProxy() {
2288 if (Parent::attached()) {
2293 void setNotifier(typename Graph::NodeNotifier& graph_notifier) {
2294 Parent::attach(graph_notifier);
2300 virtual void add(const GraphNode& gn) {
2301 std::vector<Node> nodes;
2302 nodes.push_back(AdaptorBase::Parent::inNode(gn));
2303 nodes.push_back(AdaptorBase::Parent::outNode(gn));
2304 adaptor->getNotifier(Node()).add(nodes);
2305 adaptor->getNotifier(Edge()).add(AdaptorBase::Parent::edge(gn));
2307 virtual void add(const std::vector<GraphNode>& gn) {
2308 std::vector<Node> nodes;
2309 std::vector<Edge> edges;
2310 for (int i = 0; i < (int)gn.size(); ++i) {
2311 edges.push_back(AdaptorBase::Parent::edge(gn[i]));
2312 nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2313 nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2315 adaptor->getNotifier(Node()).add(nodes);
2316 adaptor->getNotifier(Edge()).add(edges);
2318 virtual void erase(const GraphNode& gn) {
2319 adaptor->getNotifier(Edge()).erase(AdaptorBase::Parent::edge(gn));
2320 std::vector<Node> nodes;
2321 nodes.push_back(AdaptorBase::Parent::inNode(gn));
2322 nodes.push_back(AdaptorBase::Parent::outNode(gn));
2323 adaptor->getNotifier(Node()).erase(nodes);
2325 virtual void erase(const std::vector<GraphNode>& gn) {
2326 std::vector<Node> nodes;
2327 std::vector<Edge> edges;
2328 for (int i = 0; i < (int)gn.size(); ++i) {
2329 edges.push_back(AdaptorBase::Parent::edge(gn[i]));
2330 nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2331 nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2333 adaptor->getNotifier(Edge()).erase(edges);
2334 adaptor->getNotifier(Node()).erase(nodes);
2336 virtual void build() {
2337 std::vector<Edge> edges;
2338 const typename Parent::Notifier* notifier = Parent::getNotifier();
2340 for (notifier->first(it); it != INVALID; notifier->next(it)) {
2341 edges.push_back(AdaptorBase::Parent::edge(it));
2343 adaptor->getNotifier(Node()).build();
2344 adaptor->getNotifier(Edge()).add(edges);
2346 virtual void clear() {
2347 std::vector<Edge> edges;
2348 const typename Parent::Notifier* notifier = Parent::getNotifier();
2350 for (notifier->first(it); it != INVALID; notifier->next(it)) {
2351 edges.push_back(AdaptorBase::Parent::edge(it));
2353 adaptor->getNotifier(Edge()).erase(edges);
2354 adaptor->getNotifier(Node()).clear();
2357 const AdaptorBase* adaptor;
2360 class EdgeNotifierProxy : public Graph::EdgeNotifier::ObserverBase {
2363 typedef typename Graph::EdgeNotifier::ObserverBase Parent;
2364 typedef AlterableSplitGraphAdaptor AdaptorBase;
2366 EdgeNotifierProxy(const AdaptorBase& _adaptor)
2367 : Parent(), adaptor(&_adaptor) {
2370 virtual ~EdgeNotifierProxy() {
2371 if (Parent::attached()) {
2376 void setNotifier(typename Graph::EdgeNotifier& graph_notifier) {
2377 Parent::attach(graph_notifier);
2383 virtual void add(const GraphEdge& ge) {
2384 adaptor->getNotifier(Edge()).add(AdaptorBase::edge(ge));
2386 virtual void add(const std::vector<GraphEdge>& ge) {
2387 std::vector<Edge> edges;
2388 for (int i = 0; i < (int)ge.size(); ++i) {
2389 edges.push_back(AdaptorBase::edge(ge[i]));
2391 adaptor->getNotifier(Edge()).add(edges);
2393 virtual void erase(const GraphEdge& ge) {
2394 adaptor->getNotifier(Edge()).erase(AdaptorBase::edge(ge));
2396 virtual void erase(const std::vector<GraphEdge>& ge) {
2397 std::vector<Edge> edges;
2398 for (int i = 0; i < (int)ge.size(); ++i) {
2399 edges.push_back(AdaptorBase::edge(ge[i]));
2401 adaptor->getNotifier(Edge()).erase(edges);
2403 virtual void build() {
2404 std::vector<Edge> edges;
2405 const typename Parent::Notifier* notifier = Parent::getNotifier();
2407 for (notifier->first(it); it != INVALID; notifier->next(it)) {
2408 edges.push_back(AdaptorBase::Parent::edge(it));
2410 adaptor->getNotifier(Edge()).add(edges);
2412 virtual void clear() {
2413 std::vector<Edge> edges;
2414 const typename Parent::Notifier* notifier = Parent::getNotifier();
2416 for (notifier->first(it); it != INVALID; notifier->next(it)) {
2417 edges.push_back(AdaptorBase::Parent::edge(it));
2419 adaptor->getNotifier(Edge()).erase(edges);
2422 const AdaptorBase* adaptor;
2426 mutable NodeNotifier node_notifier;
2427 mutable EdgeNotifier edge_notifier;
2429 NodeNotifierProxy node_notifier_proxy;
2430 EdgeNotifierProxy edge_notifier_proxy;
2434 /// \ingroup graph_adaptors
2436 /// \brief Split graph adaptor class
2438 /// This is an graph adaptor which splits all node into an in-node
2439 /// and an out-node. Formaly, the adaptor replaces each \f$ u \f$
2440 /// node in the graph with two node, \f$ u_{in} \f$ node and
2441 /// \f$ u_{out} \f$ node. If there is an \f$ (v, u) \f$ edge in the
2442 /// original graph the new target of the edge will be \f$ u_{in} \f$ and
2443 /// similarly the source of the original \f$ (u, v) \f$ edge will be
2444 /// \f$ u_{out} \f$. The adaptor will add for each node in the
2445 /// original graph an additional edge which will connect
2446 /// \f$ (u_{in}, u_{out}) \f$.
2448 /// The aim of this class is to run algorithm with node costs if the
2449 /// algorithm can use directly just edge costs. In this case we should use
2450 /// a \c SplitGraphAdaptor and set the node cost of the graph to the
2451 /// bind edge in the adapted graph.
2453 /// By example a maximum flow algoritm can compute how many edge
2454 /// disjoint paths are in the graph. But we would like to know how
2455 /// many node disjoint paths are in the graph. First we have to
2456 /// adapt the graph with the \c SplitGraphAdaptor. Then run the flow
2457 /// algorithm on the adapted graph. The bottleneck of the flow will
2458 /// be the bind edges which bounds the flow with the count of the
2459 /// node disjoint paths.
2463 /// typedef SplitGraphAdaptor<SmartGraph> SGraph;
2465 /// SGraph sgraph(graph);
2467 /// typedef ConstMap<SGraph::Edge, int> SCapacity;
2468 /// SCapacity scapacity(1);
2470 /// SGraph::EdgeMap<int> sflow(sgraph);
2472 /// Preflow<SGraph, int, SCapacity>
2473 /// spreflow(sgraph, SGraph::outNode(source),SGraph::inNode(target),
2474 /// scapacity, sflow);
2480 /// The result of the mamixum flow on the original graph
2481 /// shows the next figure:
2483 /// \image html edge_disjoint.png
2484 /// \image latex edge_disjoint.eps "Edge disjoint paths" width=\textwidth
2486 /// And the maximum flow on the adapted graph:
2488 /// \image html node_disjoint.png
2489 /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth
2491 /// The second solution contains just 3 disjoint paths while the first 4.
2492 /// The full code can be found in the \ref disjoint_paths_demo.cc demo file.
2494 /// This graph adaptor is fully conform to the
2495 /// \ref concepts::Graph "Graph" concept and
2496 /// contains some additional member functions and types. The
2497 /// documentation of some member functions may be found just in the
2498 /// SplitGraphAdaptorBase class.
2500 /// \sa SplitGraphAdaptorBase
2501 template <typename _Graph>
2502 class SplitGraphAdaptor : public AlterableSplitGraphAdaptor<_Graph> {
2504 typedef AlterableSplitGraphAdaptor<_Graph> Parent;
2506 typedef typename Parent::Node Node;
2507 typedef typename Parent::Edge Edge;
2509 /// \brief Constructor of the adaptor.
2511 /// Constructor of the adaptor.
2512 SplitGraphAdaptor(_Graph& graph) {
2513 Parent::setGraph(graph);
2516 /// \brief NodeMap combined from two original NodeMap
2518 /// This class adapt two of the original graph NodeMap to
2519 /// get a node map on the adapted graph.
2520 template <typename InNodeMap, typename OutNodeMap>
2521 class CombinedNodeMap {
2525 typedef typename InNodeMap::Value Value;
2527 /// \brief Constructor
2530 CombinedNodeMap(InNodeMap& _inNodeMap, OutNodeMap& _outNodeMap)
2531 : inNodeMap(_inNodeMap), outNodeMap(_outNodeMap) {}
2533 /// \brief The subscript operator.
2535 /// The subscript operator.
2536 Value& operator[](const Key& key) {
2537 if (Parent::inNode(key)) {
2538 return inNodeMap[key];
2540 return outNodeMap[key];
2544 /// \brief The const subscript operator.
2546 /// The const subscript operator.
2547 Value operator[](const Key& key) const {
2548 if (Parent::inNode(key)) {
2549 return inNodeMap[key];
2551 return outNodeMap[key];
2555 /// \brief The setter function of the map.
2557 /// The setter function of the map.
2558 void set(const Key& key, const Value& value) {
2559 if (Parent::inNode(key)) {
2560 inNodeMap.set(key, value);
2562 outNodeMap.set(key, value);
2568 InNodeMap& inNodeMap;
2569 OutNodeMap& outNodeMap;
2574 /// \brief Just gives back a combined node map.
2576 /// Just gives back a combined node map.
2577 template <typename InNodeMap, typename OutNodeMap>
2578 static CombinedNodeMap<InNodeMap, OutNodeMap>
2579 combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
2580 return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
2583 template <typename InNodeMap, typename OutNodeMap>
2584 static CombinedNodeMap<const InNodeMap, OutNodeMap>
2585 combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
2586 return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
2589 template <typename InNodeMap, typename OutNodeMap>
2590 static CombinedNodeMap<InNodeMap, const OutNodeMap>
2591 combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
2592 return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
2595 template <typename InNodeMap, typename OutNodeMap>
2596 static CombinedNodeMap<const InNodeMap, const OutNodeMap>
2597 combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
2598 return CombinedNodeMap<const InNodeMap,
2599 const OutNodeMap>(in_map, out_map);
2602 /// \brief EdgeMap combined from an original EdgeMap and NodeMap
2604 /// This class adapt an original graph EdgeMap and NodeMap to
2605 /// get an edge map on the adapted graph.
2606 template <typename GraphEdgeMap, typename GraphNodeMap>
2607 class CombinedEdgeMap
2608 : public MapBase<Edge, typename GraphEdgeMap::Value> {
2610 typedef MapBase<Edge, typename GraphEdgeMap::Value> Parent;
2612 typedef typename Parent::Key Key;
2613 typedef typename Parent::Value Value;
2615 /// \brief Constructor
2618 CombinedEdgeMap(GraphEdgeMap& _edge_map, GraphNodeMap& _node_map)
2619 : edge_map(_edge_map), node_map(_node_map) {}
2621 /// \brief The subscript operator.
2623 /// The subscript operator.
2624 void set(const Edge& edge, const Value& val) {
2625 if (Parent::origEdge(edge)) {
2626 edge_map.set(edge, val);
2628 node_map.set(edge, val);
2632 /// \brief The const subscript operator.
2634 /// The const subscript operator.
2635 Value operator[](const Key& edge) const {
2636 if (Parent::origEdge(edge)) {
2637 return edge_map[edge];
2639 return node_map[edge];
2643 /// \brief The const subscript operator.
2645 /// The const subscript operator.
2646 Value& operator[](const Key& edge) {
2647 if (Parent::origEdge(edge)) {
2648 return edge_map[edge];
2650 return node_map[edge];
2655 GraphEdgeMap& edge_map;
2656 GraphNodeMap& node_map;
2659 /// \brief Just gives back a combined edge map.
2661 /// Just gives back a combined edge map.
2662 template <typename GraphEdgeMap, typename GraphNodeMap>
2663 static CombinedEdgeMap<GraphEdgeMap, GraphNodeMap>
2664 combinedEdgeMap(GraphEdgeMap& edge_map, GraphNodeMap& node_map) {
2665 return CombinedEdgeMap<GraphEdgeMap, GraphNodeMap>(edge_map, node_map);
2668 template <typename GraphEdgeMap, typename GraphNodeMap>
2669 static CombinedEdgeMap<const GraphEdgeMap, GraphNodeMap>
2670 combinedEdgeMap(const GraphEdgeMap& edge_map, GraphNodeMap& node_map) {
2671 return CombinedEdgeMap<const GraphEdgeMap,
2672 GraphNodeMap>(edge_map, node_map);
2675 template <typename GraphEdgeMap, typename GraphNodeMap>
2676 static CombinedEdgeMap<GraphEdgeMap, const GraphNodeMap>
2677 combinedEdgeMap(GraphEdgeMap& edge_map, const GraphNodeMap& node_map) {
2678 return CombinedEdgeMap<GraphEdgeMap,
2679 const GraphNodeMap>(edge_map, node_map);
2682 template <typename GraphEdgeMap, typename GraphNodeMap>
2683 static CombinedEdgeMap<const GraphEdgeMap, const GraphNodeMap>
2684 combinedEdgeMap(const GraphEdgeMap& edge_map,
2685 const GraphNodeMap& node_map) {
2686 return CombinedEdgeMap<const GraphEdgeMap,
2687 const GraphNodeMap>(edge_map, node_map);
2692 /// \brief Just gives back a split graph adaptor
2694 /// Just gives back a split graph adaptor
2695 template<typename Graph>
2696 SplitGraphAdaptor<Graph>
2697 splitGraphAdaptor(const Graph& graph) {
2698 return SplitGraphAdaptor<Graph>(graph);
2704 #endif //LEMON_GRAPH_ADAPTOR_H