2 * src/lemon/graph_wrapper.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #ifndef LEMON_GRAPH_WRAPPER_H
18 #define LEMON_GRAPH_WRAPPER_H
22 ///\brief Several graph wrappers.
24 ///This file contains several useful graph wrapper functions.
26 ///\author Marton Makai
28 #include <lemon/invalid.h>
29 #include <lemon/maps.h>
30 #include <lemon/map_defines.h>
37 /// \addtogroup gwrappers
38 /// The main parts of LEMON are the different graph structures,
39 /// generic graph algorithms, graph concepts which couple these, and
40 /// graph wrappers. While the previous ones are more or less clear, the
41 /// latter notion needs further explanation.
42 /// Graph wrappers are graph classes which serve for considering graph
43 /// structures in different ways. A short example makes the notion much
45 /// Suppose that we have an instance \c g of a directed graph
46 /// type say \c ListGraph and an algorithm
47 /// \code template<typename Graph> int algorithm(const Graph&); \endcode
48 /// is needed to run on the reversely oriented graph.
49 /// It may be expensive (in time or in memory usage) to copy
50 /// \c g with the reverse orientation.
51 /// Thus, a wrapper class
52 /// \code template<typename Graph> class RevGraphWrapper; \endcode is used.
53 /// The code looks as follows
56 /// RevGraphWrapper<ListGraph> rgw(g);
57 /// int result=algorithm(rgw);
59 /// After running the algorithm, the original graph \c g
60 /// remains untouched. Thus the graph wrapper used above is to consider the
61 /// original graph with reverse orientation.
62 /// This techniques gives rise to an elegant code, and
63 /// based on stable graph wrappers, complex algorithms can be
64 /// implemented easily.
65 /// In flow, circulation and bipartite matching problems, the residual
66 /// graph is of particular importance. Combining a wrapper implementing
67 /// this, shortest path algorithms and minimum mean cycle algorithms,
68 /// a range of weighted and cardinality optimization algorithms can be
69 /// obtained. For lack of space, for other examples,
70 /// the interested user is referred to the detailed documentation of graph
72 /// The behavior of graph wrappers can be very different. Some of them keep
73 /// capabilities of the original graph while in other cases this would be
74 /// meaningless. This means that the concepts that they are a model of depend
75 /// on the graph wrapper, and the wrapped graph(s).
76 /// If an edge of \c rgw is deleted, this is carried out by
77 /// deleting the corresponding edge of \c g. But for a residual
78 /// graph, this operation has no sense.
79 /// Let we stand one more example here to simplify your work.
81 /// \code template<typename Graph> class RevGraphWrapper; \endcode
83 /// <tt> RevGraphWrapper(Graph& _g)</tt>.
84 /// This means that in a situation,
85 /// when a <tt> const ListGraph& </tt> reference to a graph is given,
86 /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
88 /// int algorithm1(const ListGraph& g) {
89 /// RevGraphWrapper<const ListGraph> rgw(g);
90 /// return algorithm2(rgw);
94 /// \addtogroup gwrappers
97 ///Base type for the Graph Wrappers
99 ///\warning Graph wrappers are in even more experimental state than the other
100 ///parts of the lib. Use them at you own risk.
102 /// This is the base type for most of LEMON graph wrappers.
103 /// This class implements a trivial graph wrapper i.e. it only wraps the
104 /// functions and types of the graph. The purpose of this class is to
105 /// make easier implementing graph wrappers. E.g. if a wrapper is
106 /// considered which differs from the wrapped graph only in some of its
107 /// functions or types, then it can be derived from GraphWrapper, and only the
108 /// differences should be implemented.
110 ///\author Marton Makai
111 template<typename _Graph>
112 class GraphWrapperBase {
114 typedef _Graph Graph;
115 /// \todo Is it needed?
116 typedef Graph BaseGraph;
117 typedef Graph ParentGraph;
121 GraphWrapperBase() : graph(0) { }
122 void setGraph(Graph& _graph) { graph=&_graph; }
125 GraphWrapperBase(Graph& _graph) : graph(&_graph) { }
126 GraphWrapperBase(const GraphWrapperBase<_Graph>& gw) : graph(gw.graph) { }
128 typedef typename Graph::Node Node;
129 typedef typename Graph::Edge Edge;
131 void first(Node& i) const { graph->first(i); }
132 void first(Edge& i) const { graph->first(i); }
133 void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
134 void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
135 // NodeIt& first(NodeIt& i) const {
136 // i=NodeIt(*this); return i;
138 // OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
139 // i=OutEdgeIt(*this, p); return i;
141 // InEdgeIt& first(InEdgeIt& i, const Node& p) const {
142 // i=InEdgeIt(*this, p); return i;
144 // EdgeIt& first(EdgeIt& i) const {
145 // i=EdgeIt(*this); return i;
148 void next(Node& i) const { graph->next(i); }
149 void next(Edge& i) const { graph->next(i); }
150 void nextIn(Edge& i) const { graph->nextIn(i); }
151 void nextOut(Edge& i) const { graph->nextOut(i); }
153 Node source(const Edge& e) const { return graph->source(e); }
154 Node target(const Edge& e) const { return graph->target(e); }
155 // Node source(const Edge& e) const {
156 // return Node(graph->source(static_cast<typename Graph::Edge>(e))); }
157 // Node target(const Edge& e) const {
158 // return Node(graph->target(static_cast<typename Graph::Edge>(e))); }
160 int nodeNum() const { return graph->nodeNum(); }
161 int edgeNum() const { return graph->edgeNum(); }
163 Node addNode() const { return Node(graph->addNode()); }
164 Edge addEdge(const Node& source, const Node& target) const {
165 return Edge(graph->addEdge(source, target)); }
167 void erase(const Node& i) const { graph->erase(i); }
168 void erase(const Edge& i) const { graph->erase(i); }
170 void clear() const { graph->clear(); }
172 bool forward(const Edge& e) const { return graph->forward(e); }
173 bool backward(const Edge& e) const { return graph->backward(e); }
175 int id(const Node& v) const { return graph->id(v); }
176 int id(const Edge& e) const { return graph->id(e); }
178 Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }
180 template <typename _Value>
181 class NodeMap : public _Graph::template NodeMap<_Value> {
183 typedef typename _Graph::template NodeMap<_Value> Parent;
184 NodeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
185 NodeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
186 : Parent(*gw.graph, value) { }
189 template <typename _Value>
190 class EdgeMap : public _Graph::template EdgeMap<_Value> {
192 typedef typename _Graph::template EdgeMap<_Value> Parent;
193 EdgeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
194 EdgeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
195 : Parent(*gw.graph, value) { }
200 template <typename _Graph>
202 public IterableGraphExtender<GraphWrapperBase<_Graph> > {
204 typedef _Graph Graph;
205 typedef IterableGraphExtender<GraphWrapperBase<_Graph> > Parent;
207 GraphWrapper() : Parent() { }
210 GraphWrapper(Graph& _graph) { setGraph(_graph); }
213 /// A graph wrapper which reverses the orientation of the edges.
215 ///\warning Graph wrappers are in even more experimental state than the other
216 ///parts of the lib. Use them at you own risk.
218 /// Let \f$G=(V, A)\f$ be a directed graph and
219 /// suppose that a graph instange \c g of type
220 /// \c ListGraph implements \f$G\f$.
224 /// For each directed edge
225 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
226 /// reversing its orientation.
227 /// Then RevGraphWrapper implements the graph structure with node-set
228 /// \f$V\f$ and edge-set
229 /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
230 /// reversing the orientation of its edges. The following code shows how
231 /// such an instance can be constructed.
233 /// RevGraphWrapper<ListGraph> gw(g);
235 ///\author Marton Makai
236 template<typename Graph>
237 class RevGraphWrapper : public GraphWrapper<Graph> {
239 typedef GraphWrapper<Graph> Parent;
241 RevGraphWrapper() : GraphWrapper<Graph>() { }
243 RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
244 RevGraphWrapper(const RevGraphWrapper<Graph>& gw) : Parent(gw) { }
246 typedef typename GraphWrapper<Graph>::Node Node;
247 typedef typename GraphWrapper<Graph>::Edge Edge;
248 //remark: OutEdgeIt and InEdgeIt cannot be typedef-ed to each other
249 //because this does not work is some of them are not defined in the
250 //original graph. The problem with this is that typedef-ed stuff
251 //are instantiated in c++.
252 class OutEdgeIt : public Edge {
253 const RevGraphWrapper<Graph>* gw;
254 friend class GraphWrapper<Graph>;
257 OutEdgeIt(Invalid i) : Edge(i) { }
258 OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) :
259 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
260 OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) :
261 Edge(e), gw(&_gw) { }
262 OutEdgeIt& operator++() {
263 *(static_cast<Edge*>(this))=
264 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
268 class InEdgeIt : public Edge {
269 const RevGraphWrapper<Graph>* gw;
270 friend class GraphWrapper<Graph>;
273 InEdgeIt(Invalid i) : Edge(i) { }
274 InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) :
275 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
276 InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) :
277 Edge(e), gw(&_gw) { }
278 InEdgeIt& operator++() {
279 *(static_cast<Edge*>(this))=
280 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
285 using GraphWrapper<Graph>::first;
286 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
287 i=OutEdgeIt(*this, p); return i;
289 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
290 i=InEdgeIt(*this, p); return i;
293 Node source(const Edge& e) const {
294 return GraphWrapper<Graph>::target(e); }
295 Node target(const Edge& e) const {
296 return GraphWrapper<Graph>::source(e); }
298 // KEEP_MAPS(Parent, RevGraphWrapper);
304 /*! \brief A graph wrapper for hiding nodes and edges from a graph.
306 \warning Graph wrappers are in even more experimental state than the other
307 parts of the lib. Use them at you own risk.
309 This wrapper shows a graph with filtered node-set and
311 Given a bool-valued map on the node-set and one on
312 the edge-set of the graph, the iterators show only the objects
313 having true value. We have to note that this does not mean that an
314 induced subgraph is obtained, the node-iterator cares only the filter
315 on the node-set, and the edge-iterators care only the filter on the
318 typedef SmartGraph Graph;
320 typedef Graph::Node Node;
321 typedef Graph::Edge Edge;
322 Node u=g.addNode(); //node of id 0
323 Node v=g.addNode(); //node of id 1
324 Node e=g.addEdge(u, v); //edge of id 0
325 Node f=g.addEdge(v, u); //edge of id 1
326 Graph::NodeMap<bool> nm(g, true);
328 Graph::EdgeMap<bool> em(g, true);
330 typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
332 for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
333 std::cout << ":-)" << std::endl;
334 for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
336 The output of the above code is the following.
342 Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
343 \c Graph::Node that is why \c g.id(n) can be applied.
345 For other examples see also the documentation of NodeSubGraphWrapper and
350 template<typename Graph, typename NodeFilterMap,
351 typename EdgeFilterMap>
352 class SubGraphWrapper : public GraphWrapper<Graph> {
354 typedef GraphWrapper<Graph> Parent;
356 NodeFilterMap* node_filter_map;
357 EdgeFilterMap* edge_filter_map;
359 SubGraphWrapper() : GraphWrapper<Graph>(),
360 node_filter_map(0), edge_filter_map(0) { }
361 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
362 node_filter_map=&_node_filter_map;
364 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
365 edge_filter_map=&_edge_filter_map;
369 SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
370 EdgeFilterMap& _edge_filter_map) :
371 GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
372 edge_filter_map(&_edge_filter_map) { }
374 typedef typename GraphWrapper<Graph>::Node Node;
375 class NodeIt : public Node {
376 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
377 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
380 NodeIt(Invalid i) : Node(i) { }
381 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
382 Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) {
383 while (*static_cast<Node*>(this)!=INVALID &&
384 !(*(gw->node_filter_map))[*this])
385 *(static_cast<Node*>(this))=
386 ++(typename Graph::NodeIt(*(gw->graph), *this));
388 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
390 Node(n), gw(&_gw) { }
391 NodeIt& operator++() {
392 *(static_cast<Node*>(this))=
393 ++(typename Graph::NodeIt(*(gw->graph), *this));
394 while (*static_cast<Node*>(this)!=INVALID &&
395 !(*(gw->node_filter_map))[*this])
396 *(static_cast<Node*>(this))=
397 ++(typename Graph::NodeIt(*(gw->graph), *this));
401 typedef typename GraphWrapper<Graph>::Edge Edge;
402 class OutEdgeIt : public Edge {
403 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
404 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
407 OutEdgeIt(Invalid i) : Edge(i) { }
408 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
409 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) {
410 while (*static_cast<Edge*>(this)!=INVALID &&
411 !(*(gw->edge_filter_map))[*this])
412 *(static_cast<Edge*>(this))=
413 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
415 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
417 Edge(e), gw(&_gw) { }
418 OutEdgeIt& operator++() {
419 *(static_cast<Edge*>(this))=
420 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
421 while (*static_cast<Edge*>(this)!=INVALID &&
422 !(*(gw->edge_filter_map))[*this])
423 *(static_cast<Edge*>(this))=
424 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
428 class InEdgeIt : public Edge {
429 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
430 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
433 // InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
434 InEdgeIt(Invalid i) : Edge(i) { }
435 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
436 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) {
437 while (*static_cast<Edge*>(this)!=INVALID &&
438 !(*(gw->edge_filter_map))[*this])
439 *(static_cast<Edge*>(this))=
440 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
442 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
444 Edge(e), gw(&_gw) { }
445 InEdgeIt& operator++() {
446 *(static_cast<Edge*>(this))=
447 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
448 while (*static_cast<Edge*>(this)!=INVALID &&
449 !(*(gw->edge_filter_map))[*this])
450 *(static_cast<Edge*>(this))=
451 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
455 class EdgeIt : public Edge {
456 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
457 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
460 EdgeIt(Invalid i) : Edge(i) { }
461 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
462 Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) {
463 while (*static_cast<Edge*>(this)!=INVALID &&
464 !(*(gw->edge_filter_map))[*this])
465 *(static_cast<Edge*>(this))=
466 ++(typename Graph::EdgeIt(*(gw->graph), *this));
468 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
470 Edge(e), gw(&_gw) { }
471 EdgeIt& operator++() {
472 *(static_cast<Edge*>(this))=
473 ++(typename Graph::EdgeIt(*(gw->graph), *this));
474 while (*static_cast<Edge*>(this)!=INVALID &&
475 !(*(gw->edge_filter_map))[*this])
476 *(static_cast<Edge*>(this))=
477 ++(typename Graph::EdgeIt(*(gw->graph), *this));
482 NodeIt& first(NodeIt& i) const {
483 i=NodeIt(*this); return i;
485 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
486 i=OutEdgeIt(*this, p); return i;
488 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
489 i=InEdgeIt(*this, p); return i;
491 EdgeIt& first(EdgeIt& i) const {
492 i=EdgeIt(*this); return i;
495 /// This function hides \c n in the graph, i.e. the iteration
496 /// jumps over it. This is done by simply setting the value of \c n
497 /// to be false in the corresponding node-map.
498 void hide(const Node& n) const { node_filter_map->set(n, false); }
500 /// This function hides \c e in the graph, i.e. the iteration
501 /// jumps over it. This is done by simply setting the value of \c e
502 /// to be false in the corresponding edge-map.
503 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
505 /// The value of \c n is set to be true in the node-map which stores
506 /// hide information. If \c n was hidden previuosly, then it is shown
508 void unHide(const Node& n) const { node_filter_map->set(n, true); }
510 /// The value of \c e is set to be true in the edge-map which stores
511 /// hide information. If \c e was hidden previuosly, then it is shown
513 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
515 /// Returns true if \c n is hidden.
516 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
518 /// Returns true if \c n is hidden.
519 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
521 /// \warning This is a linear time operation and works only if
522 /// \c Graph::NodeIt is defined.
523 int nodeNum() const {
525 for (NodeIt n(*this); n!=INVALID; ++n) ++i;
529 /// \warning This is a linear time operation and works only if
530 /// \c Graph::EdgeIt is defined.
531 int edgeNum() const {
533 for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
537 // KEEP_MAPS(Parent, SubGraphWrapper);
541 /*! \brief A wrapper for hiding nodes from a graph.
543 \warning Graph wrappers are in even more experimental state than the other
544 parts of the lib. Use them at you own risk.
546 A wrapper for hiding nodes from a graph.
547 This wrapper specializes SubGraphWrapper in the way that only the node-set
548 can be filtered. Note that this does not mean of considering induced
549 subgraph, the edge-iterators consider the original edge-set.
552 template<typename Graph, typename NodeFilterMap>
553 class NodeSubGraphWrapper :
554 public SubGraphWrapper<Graph, NodeFilterMap,
555 ConstMap<typename Graph::Edge,bool> > {
557 typedef SubGraphWrapper<Graph, NodeFilterMap,
558 ConstMap<typename Graph::Edge,bool> > Parent;
560 ConstMap<typename Graph::Edge, bool> const_true_map;
562 NodeSubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map) :
563 Parent(), const_true_map(true) {
564 Parent::setGraph(_graph);
565 Parent::setNodeFilterMap(_node_filter_map);
566 Parent::setEdgeFilterMap(const_true_map);
571 /*! \brief A wrapper for hiding edges from a graph.
573 \warning Graph wrappers are in even more experimental state than the other
574 parts of the lib. Use them at you own risk.
576 A wrapper for hiding edges from a graph.
577 This wrapper specializes SubGraphWrapper in the way that only the edge-set
578 can be filtered. The usefulness of this wrapper is demonstrated in the
579 problem of searching a maximum number of edge-disjoint shortest paths
581 two nodes \c s and \c t. Shortest here means being shortest w.r.t.
582 non-negative edge-lengths. Note that
583 the comprehension of the presented solution
584 need's some knowledge from elementary combinatorial optimization.
586 If a single shortest path is to be
587 searched between two nodes \c s and \c t, then this can be done easily by
588 applying the Dijkstra algorithm class. What happens, if a maximum number of
589 edge-disjoint shortest paths is to be computed. It can be proved that an
590 edge can be in a shortest path if and only if it is tight with respect to
591 the potential function computed by Dijkstra. Moreover, any path containing
592 only such edges is a shortest one. Thus we have to compute a maximum number
593 of edge-disjoint paths between \c s and \c t in the graph which has edge-set
594 all the tight edges. The computation will be demonstrated on the following
595 graph, which is read from a dimacs file.
598 digraph lemon_dot_example {
599 node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
600 n0 [ label="0 (s)" ];
606 n6 [ label="6 (t)" ];
607 edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
608 n5 -> n6 [ label="9, length:4" ];
609 n4 -> n6 [ label="8, length:2" ];
610 n3 -> n5 [ label="7, length:1" ];
611 n2 -> n5 [ label="6, length:3" ];
612 n2 -> n6 [ label="5, length:5" ];
613 n2 -> n4 [ label="4, length:2" ];
614 n1 -> n4 [ label="3, length:3" ];
615 n0 -> n3 [ label="2, length:1" ];
616 n0 -> n2 [ label="1, length:2" ];
617 n0 -> n1 [ label="0, length:3" ];
626 readDimacs(std::cin, g, length, s, t);
628 cout << "edges with lengths (of form id, source--length->target): " << endl;
629 for(EdgeIt e(g); e!=INVALID; ++e)
630 cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
631 << length[e] << "->" << g.id(g.target(e)) << endl;
633 cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
635 Next, the potential function is computed with Dijkstra.
637 typedef Dijkstra<Graph, LengthMap> Dijkstra;
638 Dijkstra dijkstra(g, length);
641 Next, we consrtruct a map which filters the edge-set to the tight edges.
643 typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
645 TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
647 typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;
648 SubGW gw(g, tight_edge_filter);
650 Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
651 with a max flow algorithm Preflow.
653 ConstMap<Edge, int> const_1_map(1);
654 Graph::EdgeMap<int> flow(g, 0);
656 Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
657 preflow(gw, s, t, const_1_map, flow);
662 cout << "maximum number of edge-disjoint shortest path: "
663 << preflow.flowValue() << endl;
664 cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
666 for(EdgeIt e(g); e!=INVALID; ++e)
668 cout << " " << g.id(g.source(e)) << "--"
669 << length[e] << "->" << g.id(g.target(e)) << endl;
671 The program has the following (expected :-)) output:
673 edges with lengths (of form id, source--length->target):
685 maximum number of edge-disjoint shortest path: 2
686 edges of the maximum number of edge-disjoint shortest s-t paths:
697 template<typename Graph, typename EdgeFilterMap>
698 class EdgeSubGraphWrapper :
699 public SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
702 typedef SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
703 EdgeFilterMap> Parent;
705 ConstMap<typename Graph::Node, bool> const_true_map;
707 EdgeSubGraphWrapper(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
708 Parent(), const_true_map(true) {
709 Parent::setGraph(_graph);
710 Parent::setNodeFilterMap(const_true_map);
711 Parent::setEdgeFilterMap(_edge_filter_map);
716 template<typename Graph>
717 class UndirGraphWrapper : public GraphWrapper<Graph> {
719 typedef GraphWrapper<Graph> Parent;
721 UndirGraphWrapper() : GraphWrapper<Graph>() { }
724 typedef typename GraphWrapper<Graph>::Node Node;
725 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
726 typedef typename GraphWrapper<Graph>::Edge Edge;
727 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
729 UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
732 friend class UndirGraphWrapper<Graph>;
733 bool out_or_in; //true iff out
734 typename Graph::OutEdgeIt out;
735 typename Graph::InEdgeIt in;
738 OutEdgeIt(const Invalid& i) : Edge(i) { }
739 OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
740 out_or_in=true; _G.graph->first(out, _n);
741 if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); }
743 operator Edge() const {
744 if (out_or_in) return Edge(out); else return Edge(in);
748 typedef OutEdgeIt InEdgeIt;
750 using GraphWrapper<Graph>::first;
751 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
752 i=OutEdgeIt(*this, p); return i;
755 using GraphWrapper<Graph>::next;
757 OutEdgeIt& next(OutEdgeIt& e) const {
759 typename Graph::Node n=this->graph->source(e.out);
760 this->graph->next(e.out);
761 if (!this->graph->valid(e.out)) {
762 e.out_or_in=false; this->graph->first(e.in, n); }
764 this->graph->next(e.in);
769 Node aNode(const OutEdgeIt& e) const {
770 if (e.out_or_in) return this->graph->source(e); else
771 return this->graph->target(e); }
772 Node bNode(const OutEdgeIt& e) const {
773 if (e.out_or_in) return this->graph->target(e); else
774 return this->graph->source(e); }
776 // KEEP_MAPS(Parent, UndirGraphWrapper);
780 // /// \brief An undirected graph template.
782 // ///\warning Graph wrappers are in even more experimental state than the other
783 // ///parts of the lib. Use them at your own risk.
785 // /// An undirected graph template.
786 // /// This class works as an undirected graph and a directed graph of
787 // /// class \c Graph is used for the physical storage.
788 // /// \ingroup graphs
789 template<typename Graph>
790 class UndirGraph : public UndirGraphWrapper<Graph> {
791 typedef UndirGraphWrapper<Graph> Parent;
795 UndirGraph() : UndirGraphWrapper<Graph>() {
796 Parent::setGraph(gr);
799 // KEEP_MAPS(Parent, UndirGraph);
804 ///\brief A wrapper for composing a subgraph of a
805 /// bidirected graph made from a directed one.
807 /// A wrapper for composing a subgraph of a
808 /// bidirected graph made from a directed one.
810 ///\warning Graph wrappers are in even more experimental state than the other
811 ///parts of the lib. Use them at you own risk.
813 /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
814 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
815 /// reversing its orientation. We are given moreover two bool valued
816 /// maps on the edge-set,
817 /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
818 /// SubBidirGraphWrapper implements the graph structure with node-set
819 /// \f$V\f$ and edge-set
820 /// \f$\{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\}\f$.
821 /// The purpose of writing + instead of union is because parallel
822 /// edges can arise. (Similarly, antiparallel edges also can arise).
823 /// In other words, a subgraph of the bidirected graph obtained, which
824 /// is given by orienting the edges of the original graph in both directions.
825 /// As the oppositely directed edges are logically different,
826 /// the maps are able to attach different values for them.
828 /// An example for such a construction is \c RevGraphWrapper where the
829 /// forward_filter is everywhere false and the backward_filter is
830 /// everywhere true. We note that for sake of efficiency,
831 /// \c RevGraphWrapper is implemented in a different way.
832 /// But BidirGraphWrapper is obtained from
833 /// SubBidirGraphWrapper by considering everywhere true
834 /// valued maps both for forward_filter and backward_filter.
835 /// Finally, one of the most important applications of SubBidirGraphWrapper
836 /// is ResGraphWrapper, which stands for the residual graph in directed
837 /// flow and circulation problems.
838 /// As wrappers usually, the SubBidirGraphWrapper implements the
839 /// above mentioned graph structure without its physical storage,
840 /// that is the whole stuff is stored in constant memory.
841 template<typename Graph,
842 typename ForwardFilterMap, typename BackwardFilterMap>
843 class SubBidirGraphWrapper : public GraphWrapper<Graph> {
845 typedef GraphWrapper<Graph> Parent;
847 ForwardFilterMap* forward_filter;
848 BackwardFilterMap* backward_filter;
850 SubBidirGraphWrapper() : GraphWrapper<Graph>() { }
851 void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
852 forward_filter=&_forward_filter;
854 void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
855 backward_filter=&_backward_filter;
860 SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter,
861 BackwardFilterMap& _backward_filter) :
862 GraphWrapper<Graph>(_graph),
863 forward_filter(&_forward_filter), backward_filter(&_backward_filter) { }
864 SubBidirGraphWrapper(const SubBidirGraphWrapper<Graph,
865 ForwardFilterMap, BackwardFilterMap>& gw) :
867 forward_filter(gw.forward_filter),
868 backward_filter(gw.backward_filter) { }
873 friend class OutEdgeIt;
875 template<typename T> class EdgeMap;
877 typedef typename GraphWrapper<Graph>::Node Node;
879 typedef typename Graph::Edge GraphEdge;
880 /// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from
881 /// Graph::Edge. It contains an extra bool flag which is true
882 /// if and only if the
883 /// edge is the backward version of the original edge.
884 class Edge : public Graph::Edge {
885 friend class SubBidirGraphWrapper<Graph,
886 ForwardFilterMap, BackwardFilterMap>;
887 template<typename T> friend class EdgeMap;
889 bool backward; //true, iff backward
892 /// \todo =false is needed, or causes problems?
893 /// If \c _backward is false, then we get an edge corresponding to the
894 /// original one, otherwise its oppositely directed pair is obtained.
895 Edge(const typename Graph::Edge& e, bool _backward/*=false*/) :
896 Graph::Edge(e), backward(_backward) { }
897 Edge(Invalid i) : Graph::Edge(i), backward(true) { }
898 bool operator==(const Edge& v) const {
899 return (this->backward==v.backward &&
900 static_cast<typename Graph::Edge>(*this)==
901 static_cast<typename Graph::Edge>(v));
903 bool operator!=(const Edge& v) const {
904 return (this->backward!=v.backward ||
905 static_cast<typename Graph::Edge>(*this)!=
906 static_cast<typename Graph::Edge>(v));
910 class OutEdgeIt : public Edge {
911 friend class SubBidirGraphWrapper<Graph,
912 ForwardFilterMap, BackwardFilterMap>;
914 const SubBidirGraphWrapper<Graph,
915 ForwardFilterMap, BackwardFilterMap>* gw;
918 OutEdgeIt(Invalid i) : Edge(i) { }
919 OutEdgeIt(const SubBidirGraphWrapper<Graph,
920 ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
921 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
922 while (*static_cast<GraphEdge*>(this)!=INVALID &&
923 !(*(gw->forward_filter))[*this])
924 *(static_cast<GraphEdge*>(this))=
925 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
926 if (*static_cast<GraphEdge*>(this)==INVALID) {
927 *static_cast<Edge*>(this)=
928 Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true);
929 while (*static_cast<GraphEdge*>(this)!=INVALID &&
930 !(*(gw->backward_filter))[*this])
931 *(static_cast<GraphEdge*>(this))=
932 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
935 OutEdgeIt(const SubBidirGraphWrapper<Graph,
936 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
937 Edge(e), gw(&_gw) { }
938 OutEdgeIt& operator++() {
939 if (!this->backward) {
940 Node n=gw->source(*this);
941 *(static_cast<GraphEdge*>(this))=
942 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
943 while (*static_cast<GraphEdge*>(this)!=INVALID &&
944 !(*(gw->forward_filter))[*this])
945 *(static_cast<GraphEdge*>(this))=
946 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
947 if (*static_cast<GraphEdge*>(this)==INVALID) {
948 *static_cast<Edge*>(this)=
949 Edge(typename Graph::InEdgeIt(*(gw->graph), n), true);
950 while (*static_cast<GraphEdge*>(this)!=INVALID &&
951 !(*(gw->backward_filter))[*this])
952 *(static_cast<GraphEdge*>(this))=
953 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
956 *(static_cast<GraphEdge*>(this))=
957 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
958 while (*static_cast<GraphEdge*>(this)!=INVALID &&
959 !(*(gw->backward_filter))[*this])
960 *(static_cast<GraphEdge*>(this))=
961 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
967 class InEdgeIt : public Edge {
968 friend class SubBidirGraphWrapper<Graph,
969 ForwardFilterMap, BackwardFilterMap>;
971 const SubBidirGraphWrapper<Graph,
972 ForwardFilterMap, BackwardFilterMap>* gw;
975 InEdgeIt(Invalid i) : Edge(i) { }
976 InEdgeIt(const SubBidirGraphWrapper<Graph,
977 ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
978 Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
979 while (*static_cast<GraphEdge*>(this)!=INVALID &&
980 !(*(gw->forward_filter))[*this])
981 *(static_cast<GraphEdge*>(this))=
982 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
983 if (*static_cast<GraphEdge*>(this)==INVALID) {
984 *static_cast<Edge*>(this)=
985 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true);
986 while (*static_cast<GraphEdge*>(this)!=INVALID &&
987 !(*(gw->backward_filter))[*this])
988 *(static_cast<GraphEdge*>(this))=
989 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
992 InEdgeIt(const SubBidirGraphWrapper<Graph,
993 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
994 Edge(e), gw(&_gw) { }
995 InEdgeIt& operator++() {
996 if (!this->backward) {
997 Node n=gw->source(*this);
998 *(static_cast<GraphEdge*>(this))=
999 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1000 while (*static_cast<GraphEdge*>(this)!=INVALID &&
1001 !(*(gw->forward_filter))[*this])
1002 *(static_cast<GraphEdge*>(this))=
1003 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1004 if (*static_cast<GraphEdge*>(this)==INVALID) {
1005 *static_cast<Edge*>(this)=
1006 Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true);
1007 while (*static_cast<GraphEdge*>(this)!=INVALID &&
1008 !(*(gw->backward_filter))[*this])
1009 *(static_cast<GraphEdge*>(this))=
1010 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1013 *(static_cast<GraphEdge*>(this))=
1014 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1015 while (*static_cast<GraphEdge*>(this)!=INVALID &&
1016 !(*(gw->backward_filter))[*this])
1017 *(static_cast<GraphEdge*>(this))=
1018 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1024 class EdgeIt : public Edge {
1025 friend class SubBidirGraphWrapper<Graph,
1026 ForwardFilterMap, BackwardFilterMap>;
1028 const SubBidirGraphWrapper<Graph,
1029 ForwardFilterMap, BackwardFilterMap>* gw;
1032 EdgeIt(Invalid i) : Edge(i) { }
1033 EdgeIt(const SubBidirGraphWrapper<Graph,
1034 ForwardFilterMap, BackwardFilterMap>& _gw) :
1035 Edge(typename Graph::EdgeIt(*(_gw.graph)), false), gw(&_gw) {
1036 while (*static_cast<GraphEdge*>(this)!=INVALID &&
1037 !(*(gw->forward_filter))[*this])
1038 *(static_cast<GraphEdge*>(this))=
1039 ++(typename Graph::EdgeIt(*(gw->graph), *this));
1040 if (*static_cast<GraphEdge*>(this)==INVALID) {
1041 *static_cast<Edge*>(this)=
1042 Edge(typename Graph::EdgeIt(*(_gw.graph)), true);
1043 while (*static_cast<GraphEdge*>(this)!=INVALID &&
1044 !(*(gw->backward_filter))[*this])
1045 *(static_cast<GraphEdge*>(this))=
1046 ++(typename Graph::EdgeIt(*(gw->graph), *this));
1049 EdgeIt(const SubBidirGraphWrapper<Graph,
1050 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
1051 Edge(e), gw(&_gw) { }
1052 EdgeIt& operator++() {
1053 if (!this->backward) {
1054 *(static_cast<GraphEdge*>(this))=
1055 ++(typename Graph::EdgeIt(*(gw->graph), *this));
1056 while (*static_cast<GraphEdge*>(this)!=INVALID &&
1057 !(*(gw->forward_filter))[*this])
1058 *(static_cast<GraphEdge*>(this))=
1059 ++(typename Graph::EdgeIt(*(gw->graph), *this));
1060 if (*static_cast<GraphEdge*>(this)==INVALID) {
1061 *static_cast<Edge*>(this)=
1062 Edge(typename Graph::EdgeIt(*(gw->graph)), true);
1063 while (*static_cast<GraphEdge*>(this)!=INVALID &&
1064 !(*(gw->backward_filter))[*this])
1065 *(static_cast<GraphEdge*>(this))=
1066 ++(typename Graph::EdgeIt(*(gw->graph), *this));
1069 *(static_cast<GraphEdge*>(this))=
1070 ++(typename Graph::EdgeIt(*(gw->graph), *this));
1071 while (*static_cast<GraphEdge*>(this)!=INVALID &&
1072 !(*(gw->backward_filter))[*this])
1073 *(static_cast<GraphEdge*>(this))=
1074 ++(typename Graph::EdgeIt(*(gw->graph), *this));
1080 // using GraphWrapper<Graph>::first;
1081 // OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1082 // i=OutEdgeIt(*this, p); return i;
1084 // InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1085 // i=InEdgeIt(*this, p); return i;
1087 // EdgeIt& first(EdgeIt& i) const {
1088 // i=EdgeIt(*this); return i;
1092 Node source(Edge e) const {
1093 return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
1094 Node target(Edge e) const {
1095 return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
1097 /// Gives back the opposite edge.
1098 Edge opposite(const Edge& e) const {
1100 f.backward=!f.backward;
1104 /// \warning This is a linear time operation and works only if
1105 /// \c Graph::EdgeIt is defined.
1106 int edgeNum() const {
1108 for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
1112 bool forward(const Edge& e) const { return !e.backward; }
1113 bool backward(const Edge& e) const { return e.backward; }
1116 template <typename T>
1117 /// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two
1118 /// Graph::EdgeMap one for the forward edges and
1119 /// one for the backward edges.
1121 template <typename TT> friend class EdgeMap;
1122 typename Graph::template EdgeMap<T> forward_map, backward_map;
1124 typedef T ValueType;
1125 typedef Edge KeyType;
1127 EdgeMap(const SubBidirGraphWrapper<Graph,
1128 ForwardFilterMap, BackwardFilterMap>& g) :
1129 forward_map(*(g.graph)), backward_map(*(g.graph)) { }
1131 EdgeMap(const SubBidirGraphWrapper<Graph,
1132 ForwardFilterMap, BackwardFilterMap>& g, T a) :
1133 forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
1135 template <typename TT>
1136 EdgeMap(const EdgeMap<TT>& copy)
1137 : forward_map(copy.forward_map), backward_map(copy.backward_map) {}
1139 template <typename TT>
1140 EdgeMap& operator=(const EdgeMap<TT>& copy) {
1141 forward_map = copy.forward_map;
1142 backward_map = copy.backward_map;
1146 void set(Edge e, T a) {
1148 forward_map.set(e, a);
1150 backward_map.set(e, a);
1153 typename Graph::template EdgeMap<T>::ConstReferenceType
1154 operator[](Edge e) const {
1156 return forward_map[e];
1158 return backward_map[e];
1161 typename Graph::template EdgeMap<T>::ReferenceType
1162 operator[](Edge e) {
1164 return forward_map[e];
1166 return backward_map[e];
1170 forward_map.update();
1171 backward_map.update();
1176 // KEEP_NODE_MAP(Parent, SubBidirGraphWrapper);
1181 ///\brief A wrapper for composing bidirected graph from a directed one.
1183 ///\warning Graph wrappers are in even more experimental state than the other
1184 ///parts of the lib. Use them at you own risk.
1186 /// A wrapper for composing bidirected graph from a directed one.
1187 /// A bidirected graph is composed over the directed one without physical
1188 /// storage. As the oppositely directed edges are logically different ones
1189 /// the maps are able to attach different values for them.
1190 template<typename Graph>
1191 class BidirGraphWrapper :
1192 public SubBidirGraphWrapper<
1194 ConstMap<typename Graph::Edge, bool>,
1195 ConstMap<typename Graph::Edge, bool> > {
1197 typedef SubBidirGraphWrapper<
1199 ConstMap<typename Graph::Edge, bool>,
1200 ConstMap<typename Graph::Edge, bool> > Parent;
1202 ConstMap<typename Graph::Edge, bool> cm;
1204 BidirGraphWrapper() : Parent(), cm(true) {
1205 Parent::setForwardFilterMap(cm);
1206 Parent::setBackwardFilterMap(cm);
1209 BidirGraphWrapper(Graph& _graph) : Parent() {
1210 Parent::setGraph(_graph);
1211 Parent::setForwardFilterMap(cm);
1212 Parent::setBackwardFilterMap(cm);
1215 int edgeNum() const {
1216 return 2*this->graph->edgeNum();
1218 // KEEP_MAPS(Parent, BidirGraphWrapper);
1222 /// \brief A bidirected graph template.
1224 ///\warning Graph wrappers are in even more experimental state than the other
1225 ///parts of the lib. Use them at you own risk.
1227 /// A bidirected graph template.
1228 /// Such a bidirected graph stores each pair of oppositely directed edges
1229 /// ones in the memory, i.e. a directed graph of type
1230 /// \c Graph is used for that.
1231 /// As the oppositely directed edges are logically different ones
1232 /// the maps are able to attach different values for them.
1234 template<typename Graph>
1235 class BidirGraph : public BidirGraphWrapper<Graph> {
1237 typedef UndirGraphWrapper<Graph> Parent;
1241 BidirGraph() : BidirGraphWrapper<Graph>() {
1242 Parent::setGraph(gr);
1244 // KEEP_MAPS(Parent, BidirGraph);
1249 template<typename Graph, typename Number,
1250 typename CapacityMap, typename FlowMap>
1251 class ResForwardFilter {
1252 // const Graph* graph;
1253 const CapacityMap* capacity;
1254 const FlowMap* flow;
1256 ResForwardFilter(/*const Graph& _graph, */
1257 const CapacityMap& _capacity, const FlowMap& _flow) :
1258 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1259 ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1260 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1261 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1262 bool operator[](const typename Graph::Edge& e) const {
1263 return (Number((*flow)[e]) < Number((*capacity)[e]));
1267 template<typename Graph, typename Number,
1268 typename CapacityMap, typename FlowMap>
1269 class ResBackwardFilter {
1270 const CapacityMap* capacity;
1271 const FlowMap* flow;
1273 ResBackwardFilter(/*const Graph& _graph,*/
1274 const CapacityMap& _capacity, const FlowMap& _flow) :
1275 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1276 ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1277 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1278 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1279 bool operator[](const typename Graph::Edge& e) const {
1280 return (Number(0) < Number((*flow)[e]));
1285 /// A wrapper for composing the residual graph for directed flow and circulation problems.
1287 ///\warning Graph wrappers are in even more experimental state than the other
1288 ///parts of the lib. Use them at you own risk.
1290 /// A wrapper for composing the residual graph for directed flow and circulation problems.
1291 template<typename Graph, typename Number,
1292 typename CapacityMap, typename FlowMap>
1293 class ResGraphWrapper :
1294 public SubBidirGraphWrapper<
1296 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1297 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1299 typedef SubBidirGraphWrapper<
1301 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1302 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1304 const CapacityMap* capacity;
1306 ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1307 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1308 ResGraphWrapper() : Parent(),
1309 capacity(0), flow(0) { }
1310 void setCapacityMap(const CapacityMap& _capacity) {
1311 capacity=&_capacity;
1312 forward_filter.setCapacity(_capacity);
1313 backward_filter.setCapacity(_capacity);
1315 void setFlowMap(FlowMap& _flow) {
1317 forward_filter.setFlow(_flow);
1318 backward_filter.setFlow(_flow);
1321 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1323 Parent(), capacity(&_capacity), flow(&_flow),
1324 forward_filter(/*_graph,*/ _capacity, _flow),
1325 backward_filter(/*_graph,*/ _capacity, _flow) {
1326 Parent::setGraph(_graph);
1327 Parent::setForwardFilterMap(forward_filter);
1328 Parent::setBackwardFilterMap(backward_filter);
1331 typedef typename Parent::Edge Edge;
1333 void augment(const Edge& e, Number a) const {
1334 if (Parent::forward(e))
1335 flow->set(e, (*flow)[e]+a);
1337 flow->set(e, (*flow)[e]-a);
1340 /// \brief Residual capacity map.
1342 /// In generic residual graphs the residual capacity can be obtained
1346 const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
1348 typedef Number ValueType;
1349 typedef Edge KeyType;
1350 ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>&
1351 _res_graph) : res_graph(&_res_graph) { }
1352 Number operator[](const Edge& e) const {
1353 if (res_graph->forward(e))
1354 return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1356 return (*(res_graph->flow))[e];
1360 // KEEP_MAPS(Parent, ResGraphWrapper);
1364 /// For blocking flows.
1366 ///\warning Graph wrappers are in even more experimental state than the other
1367 ///parts of the lib. Use them at you own risk.
1369 /// This graph wrapper is used for on-the-fly
1370 /// Dinits blocking flow computations.
1371 /// For each node, an out-edge is stored which is used when the
1373 /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1377 /// \author Marton Makai
1378 template<typename Graph, typename FirstOutEdgesMap>
1379 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1381 typedef GraphWrapper<Graph> Parent;
1383 FirstOutEdgesMap* first_out_edges;
1385 ErasingFirstGraphWrapper(Graph& _graph,
1386 FirstOutEdgesMap& _first_out_edges) :
1387 GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
1389 typedef typename GraphWrapper<Graph>::Node Node;
1390 typedef typename GraphWrapper<Graph>::Edge Edge;
1391 class OutEdgeIt : public Edge {
1392 friend class GraphWrapper<Graph>;
1393 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1394 const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>* gw;
1397 OutEdgeIt(Invalid i) : Edge(i) { }
1398 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
1400 Edge((*(_gw.first_out_edges))[n]), gw(&_gw) { }
1401 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
1403 Edge(e), gw(&_gw) { }
1404 OutEdgeIt& operator++() {
1405 *(static_cast<Edge*>(this))=
1406 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1411 // using GraphWrapper<Graph>::first;
1412 // OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1413 // i=OutEdgeIt(*this, p); return i;
1415 void erase(const Edge& e) const {
1417 typename Graph::OutEdgeIt f(*Parent::graph, n);
1419 first_out_edges->set(n, f);
1422 // KEEP_MAPS(Parent, ErasingFirstGraphWrapper);
1429 #endif //LEMON_GRAPH_WRAPPER_H