The graph_factory branch (@ 1321) has been merged to trunk.
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>
115 GraphWrapper() : graph(0) { }
116 void setGraph(Graph& _graph) { graph=&_graph; }
119 typedef Graph BaseGraph;
120 typedef Graph ParentGraph;
122 GraphWrapper(Graph& _graph) : graph(&_graph) { }
123 GraphWrapper(const GraphWrapper<Graph>& gw) : graph(gw.graph) { }
125 typedef typename Graph::Node Node;
126 class NodeIt : public Node {
127 const GraphWrapper<Graph>* gw;
128 friend class GraphWrapper<Graph>;
131 NodeIt(Invalid i) : Node(i) { }
132 NodeIt(const GraphWrapper<Graph>& _gw) :
133 Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { }
134 NodeIt(const GraphWrapper<Graph>& _gw, const Node& n) :
135 Node(n), gw(&_gw) { }
136 NodeIt& operator++() {
137 *(static_cast<Node*>(this))=
138 ++(typename Graph::NodeIt(*(gw->graph), *this));
142 typedef typename Graph::Edge Edge;
143 class OutEdgeIt : public Edge {
144 const GraphWrapper<Graph>* gw;
145 friend class GraphWrapper<Graph>;
148 OutEdgeIt(Invalid i) : Edge(i) { }
149 OutEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) :
150 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
151 OutEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
152 Edge(e), gw(&_gw) { }
153 OutEdgeIt& operator++() {
154 *(static_cast<Edge*>(this))=
155 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
159 class InEdgeIt : public Edge {
160 const GraphWrapper<Graph>* gw;
161 friend class GraphWrapper<Graph>;
164 InEdgeIt(Invalid i) : Edge(i) { }
165 InEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) :
166 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
167 InEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
168 Edge(e), gw(&_gw) { }
169 InEdgeIt& operator++() {
170 *(static_cast<Edge*>(this))=
171 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
175 class EdgeIt : public Edge {
176 const GraphWrapper<Graph>* gw;
177 friend class GraphWrapper<Graph>;
180 EdgeIt(Invalid i) : Edge(i) { }
181 EdgeIt(const GraphWrapper<Graph>& _gw) :
182 Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { }
183 EdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
184 Edge(e), gw(&_gw) { }
185 EdgeIt& operator++() {
186 *(static_cast<Edge*>(this))=
187 ++(typename Graph::EdgeIt(*(gw->graph), *this));
192 NodeIt& first(NodeIt& i) const {
193 i=NodeIt(*this); return i;
195 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
196 i=OutEdgeIt(*this, p); return i;
198 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
199 i=InEdgeIt(*this, p); return i;
201 EdgeIt& first(EdgeIt& i) const {
202 i=EdgeIt(*this); return i;
205 Node tail(const Edge& e) const {
206 return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
207 Node head(const Edge& e) const {
208 return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
210 int nodeNum() const { return graph->nodeNum(); }
211 int edgeNum() const { return graph->edgeNum(); }
213 Node addNode() const { return Node(graph->addNode()); }
214 Edge addEdge(const Node& tail, const Node& head) const {
215 return Edge(graph->addEdge(tail, head)); }
217 void erase(const Node& i) const { graph->erase(i); }
218 void erase(const Edge& i) const { graph->erase(i); }
220 void clear() const { graph->clear(); }
222 bool forward(const Edge& e) const { return graph->forward(e); }
223 bool backward(const Edge& e) const { return graph->backward(e); }
225 int id(const Node& v) const { return graph->id(v); }
226 int id(const Edge& e) const { return graph->id(e); }
228 Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }
231 IMPORT_NODE_MAP(Graph, *(gw.graph), GraphWrapper, gw);
232 IMPORT_EDGE_MAP(Graph, *(gw.graph), GraphWrapper, gw);
239 /// A graph wrapper which reverses the orientation of the edges.
241 ///\warning Graph wrappers are in even more experimental state than the other
242 ///parts of the lib. Use them at you own risk.
244 /// Let \f$G=(V, A)\f$ be a directed graph and
245 /// suppose that a graph instange \c g of type
246 /// \c ListGraph implements \f$G\f$.
250 /// For each directed edge
251 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
252 /// reversing its orientation.
253 /// Then RevGraphWrapper implements the graph structure with node-set
254 /// \f$V\f$ and edge-set
255 /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
256 /// reversing the orientation of its edges. The following code shows how
257 /// such an instance can be constructed.
259 /// RevGraphWrapper<ListGraph> gw(g);
261 ///\author Marton Makai
262 template<typename Graph>
263 class RevGraphWrapper : public GraphWrapper<Graph> {
265 typedef GraphWrapper<Graph> Parent;
267 RevGraphWrapper() : GraphWrapper<Graph>() { }
269 RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
270 RevGraphWrapper(const RevGraphWrapper<Graph>& gw) : Parent(gw) { }
272 typedef typename GraphWrapper<Graph>::Node Node;
273 typedef typename GraphWrapper<Graph>::Edge Edge;
274 //remark: OutEdgeIt and InEdgeIt cannot be typedef-ed to each other
275 //because this does not work is some of them are not defined in the
276 //original graph. The problem with this is that typedef-ed stuff
277 //are instantiated in c++.
278 class OutEdgeIt : public Edge {
279 const RevGraphWrapper<Graph>* gw;
280 friend class GraphWrapper<Graph>;
283 OutEdgeIt(Invalid i) : Edge(i) { }
284 OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) :
285 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
286 OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) :
287 Edge(e), gw(&_gw) { }
288 OutEdgeIt& operator++() {
289 *(static_cast<Edge*>(this))=
290 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
294 class InEdgeIt : public Edge {
295 const RevGraphWrapper<Graph>* gw;
296 friend class GraphWrapper<Graph>;
299 InEdgeIt(Invalid i) : Edge(i) { }
300 InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) :
301 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
302 InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) :
303 Edge(e), gw(&_gw) { }
304 InEdgeIt& operator++() {
305 *(static_cast<Edge*>(this))=
306 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
311 using GraphWrapper<Graph>::first;
312 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
313 i=OutEdgeIt(*this, p); return i;
315 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
316 i=InEdgeIt(*this, p); return i;
319 Node tail(const Edge& e) const {
320 return GraphWrapper<Graph>::head(e); }
321 Node head(const Edge& e) const {
322 return GraphWrapper<Graph>::tail(e); }
324 // KEEP_MAPS(Parent, RevGraphWrapper);
330 /*! \brief A graph wrapper for hiding nodes and edges from a graph.
332 \warning Graph wrappers are in even more experimental state than the other
333 parts of the lib. Use them at you own risk.
335 This wrapper shows a graph with filtered node-set and
337 Given a bool-valued map on the node-set and one on
338 the edge-set of the graph, the iterators show only the objects
339 having true value. We have to note that this does not mean that an
340 induced subgraph is obtained, the node-iterator cares only the filter
341 on the node-set, and the edge-iterators care only the filter on the
344 typedef SmartGraph Graph;
346 typedef Graph::Node Node;
347 typedef Graph::Edge Edge;
348 Node u=g.addNode(); //node of id 0
349 Node v=g.addNode(); //node of id 1
350 Node e=g.addEdge(u, v); //edge of id 0
351 Node f=g.addEdge(v, u); //edge of id 1
352 Graph::NodeMap<bool> nm(g, true);
354 Graph::EdgeMap<bool> em(g, true);
356 typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
358 for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
359 std::cout << ":-)" << std::endl;
360 for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
362 The output of the above code is the following.
368 Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
369 \c Graph::Node that is why \c g.id(n) can be applied.
371 For other examples see also the documentation of NodeSubGraphWrapper and
376 template<typename Graph, typename NodeFilterMap,
377 typename EdgeFilterMap>
378 class SubGraphWrapper : public GraphWrapper<Graph> {
380 typedef GraphWrapper<Graph> Parent;
382 NodeFilterMap* node_filter_map;
383 EdgeFilterMap* edge_filter_map;
385 SubGraphWrapper() : GraphWrapper<Graph>(),
386 node_filter_map(0), edge_filter_map(0) { }
387 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
388 node_filter_map=&_node_filter_map;
390 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
391 edge_filter_map=&_edge_filter_map;
395 SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
396 EdgeFilterMap& _edge_filter_map) :
397 GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
398 edge_filter_map(&_edge_filter_map) { }
400 typedef typename GraphWrapper<Graph>::Node Node;
401 class NodeIt : public Node {
402 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
403 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
406 NodeIt(Invalid i) : Node(i) { }
407 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
408 Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) {
409 while (*static_cast<Node*>(this)!=INVALID &&
410 !(*(gw->node_filter_map))[*this])
411 *(static_cast<Node*>(this))=
412 ++(typename Graph::NodeIt(*(gw->graph), *this));
414 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
416 Node(n), gw(&_gw) { }
417 NodeIt& operator++() {
418 *(static_cast<Node*>(this))=
419 ++(typename Graph::NodeIt(*(gw->graph), *this));
420 while (*static_cast<Node*>(this)!=INVALID &&
421 !(*(gw->node_filter_map))[*this])
422 *(static_cast<Node*>(this))=
423 ++(typename Graph::NodeIt(*(gw->graph), *this));
427 typedef typename GraphWrapper<Graph>::Edge Edge;
428 class OutEdgeIt : public Edge {
429 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
430 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
433 OutEdgeIt(Invalid i) : Edge(i) { }
434 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
435 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) {
436 while (*static_cast<Edge*>(this)!=INVALID &&
437 !(*(gw->edge_filter_map))[*this])
438 *(static_cast<Edge*>(this))=
439 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
441 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
443 Edge(e), gw(&_gw) { }
444 OutEdgeIt& operator++() {
445 *(static_cast<Edge*>(this))=
446 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
447 while (*static_cast<Edge*>(this)!=INVALID &&
448 !(*(gw->edge_filter_map))[*this])
449 *(static_cast<Edge*>(this))=
450 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
454 class InEdgeIt : public Edge {
455 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
456 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
459 // InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
460 InEdgeIt(Invalid i) : Edge(i) { }
461 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
462 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) {
463 while (*static_cast<Edge*>(this)!=INVALID &&
464 !(*(gw->edge_filter_map))[*this])
465 *(static_cast<Edge*>(this))=
466 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
468 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
470 Edge(e), gw(&_gw) { }
471 InEdgeIt& operator++() {
472 *(static_cast<Edge*>(this))=
473 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
474 while (*static_cast<Edge*>(this)!=INVALID &&
475 !(*(gw->edge_filter_map))[*this])
476 *(static_cast<Edge*>(this))=
477 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
481 class EdgeIt : public Edge {
482 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
483 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
486 EdgeIt(Invalid i) : Edge(i) { }
487 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
488 Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) {
489 while (*static_cast<Edge*>(this)!=INVALID &&
490 !(*(gw->edge_filter_map))[*this])
491 *(static_cast<Edge*>(this))=
492 ++(typename Graph::EdgeIt(*(gw->graph), *this));
494 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
496 Edge(e), gw(&_gw) { }
497 EdgeIt& operator++() {
498 *(static_cast<Edge*>(this))=
499 ++(typename Graph::EdgeIt(*(gw->graph), *this));
500 while (*static_cast<Edge*>(this)!=INVALID &&
501 !(*(gw->edge_filter_map))[*this])
502 *(static_cast<Edge*>(this))=
503 ++(typename Graph::EdgeIt(*(gw->graph), *this));
508 NodeIt& first(NodeIt& i) const {
509 i=NodeIt(*this); return i;
511 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
512 i=OutEdgeIt(*this, p); return i;
514 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
515 i=InEdgeIt(*this, p); return i;
517 EdgeIt& first(EdgeIt& i) const {
518 i=EdgeIt(*this); return i;
521 /// This function hides \c n in the graph, i.e. the iteration
522 /// jumps over it. This is done by simply setting the value of \c n
523 /// to be false in the corresponding node-map.
524 void hide(const Node& n) const { node_filter_map->set(n, false); }
526 /// This function hides \c e in the graph, i.e. the iteration
527 /// jumps over it. This is done by simply setting the value of \c e
528 /// to be false in the corresponding edge-map.
529 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
531 /// The value of \c n is set to be true in the node-map which stores
532 /// hide information. If \c n was hidden previuosly, then it is shown
534 void unHide(const Node& n) const { node_filter_map->set(n, true); }
536 /// The value of \c e is set to be true in the edge-map which stores
537 /// hide information. If \c e was hidden previuosly, then it is shown
539 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
541 /// Returns true if \c n is hidden.
542 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
544 /// Returns true if \c n is hidden.
545 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
547 /// \warning This is a linear time operation and works only if
548 /// \c Graph::NodeIt is defined.
549 int nodeNum() const {
551 for (NodeIt n(*this); n!=INVALID; ++n) ++i;
555 /// \warning This is a linear time operation and works only if
556 /// \c Graph::EdgeIt is defined.
557 int edgeNum() const {
559 for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
563 // KEEP_MAPS(Parent, SubGraphWrapper);
567 /*! \brief A wrapper for hiding nodes from a graph.
569 \warning Graph wrappers are in even more experimental state than the other
570 parts of the lib. Use them at you own risk.
572 A wrapper for hiding nodes from a graph.
573 This wrapper specializes SubGraphWrapper in the way that only the node-set
574 can be filtered. Note that this does not mean of considering induced
575 subgraph, the edge-iterators consider the original edge-set.
578 template<typename Graph, typename NodeFilterMap>
579 class NodeSubGraphWrapper :
580 public SubGraphWrapper<Graph, NodeFilterMap,
581 ConstMap<typename Graph::Edge,bool> > {
583 typedef SubGraphWrapper<Graph, NodeFilterMap,
584 ConstMap<typename Graph::Edge,bool> > Parent;
586 ConstMap<typename Graph::Edge, bool> const_true_map;
588 NodeSubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map) :
589 Parent(), const_true_map(true) {
590 Parent::setGraph(_graph);
591 Parent::setNodeFilterMap(_node_filter_map);
592 Parent::setEdgeFilterMap(const_true_map);
597 /*! \brief A wrapper for hiding edges from a graph.
599 \warning Graph wrappers are in even more experimental state than the other
600 parts of the lib. Use them at you own risk.
602 A wrapper for hiding edges from a graph.
603 This wrapper specializes SubGraphWrapper in the way that only the edge-set
604 can be filtered. The usefulness of this wrapper is demonstrated in the
605 problem of searching a maximum number of edge-disjoint shortest paths
607 two nodes \c s and \c t. Shortest here means being shortest w.r.t.
608 non-negative edge-lengths. Note that
609 the comprehension of the presented solution
610 need's some knowledge from elementary combinatorial optimization.
612 If a single shortest path is to be
613 searched between two nodes \c s and \c t, then this can be done easily by
614 applying the Dijkstra algorithm class. What happens, if a maximum number of
615 edge-disjoint shortest paths is to be computed. It can be proved that an
616 edge can be in a shortest path if and only if it is tight with respect to
617 the potential function computed by Dijkstra. Moreover, any path containing
618 only such edges is a shortest one. Thus we have to compute a maximum number
619 of edge-disjoint paths between \c s and \c t in the graph which has edge-set
620 all the tight edges. The computation will be demonstrated on the following
621 graph, which is read from a dimacs file.
624 digraph lemon_dot_example {
625 node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
626 n0 [ label="0 (s)" ];
632 n6 [ label="6 (t)" ];
633 edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
634 n5 -> n6 [ label="9, length:4" ];
635 n4 -> n6 [ label="8, length:2" ];
636 n3 -> n5 [ label="7, length:1" ];
637 n2 -> n5 [ label="6, length:3" ];
638 n2 -> n6 [ label="5, length:5" ];
639 n2 -> n4 [ label="4, length:2" ];
640 n1 -> n4 [ label="3, length:3" ];
641 n0 -> n3 [ label="2, length:1" ];
642 n0 -> n2 [ label="1, length:2" ];
643 n0 -> n1 [ label="0, length:3" ];
652 readDimacs(std::cin, g, length, s, t);
654 cout << "edges with lengths (of form id, tail--length->head): " << endl;
655 for(EdgeIt e(g); e!=INVALID; ++e)
656 cout << g.id(e) << ", " << g.id(g.tail(e)) << "--"
657 << length[e] << "->" << g.id(g.head(e)) << endl;
659 cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
661 Next, the potential function is computed with Dijkstra.
663 typedef Dijkstra<Graph, LengthMap> Dijkstra;
664 Dijkstra dijkstra(g, length);
667 Next, we consrtruct a map which filters the edge-set to the tight edges.
669 typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
671 TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
673 typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;
674 SubGW gw(g, tight_edge_filter);
676 Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
677 with a max flow algorithm Preflow.
679 ConstMap<Edge, int> const_1_map(1);
680 Graph::EdgeMap<int> flow(g, 0);
682 Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
683 preflow(gw, s, t, const_1_map, flow);
688 cout << "maximum number of edge-disjoint shortest path: "
689 << preflow.flowValue() << endl;
690 cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
692 for(EdgeIt e(g); e!=INVALID; ++e)
694 cout << " " << g.id(g.tail(e)) << "--"
695 << length[e] << "->" << g.id(g.head(e)) << endl;
697 The program has the following (expected :-)) output:
699 edges with lengths (of form id, tail--length->head):
711 maximum number of edge-disjoint shortest path: 2
712 edges of the maximum number of edge-disjoint shortest s-t paths:
723 template<typename Graph, typename EdgeFilterMap>
724 class EdgeSubGraphWrapper :
725 public SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
728 typedef SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
729 EdgeFilterMap> Parent;
731 ConstMap<typename Graph::Node, bool> const_true_map;
733 EdgeSubGraphWrapper(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
734 Parent(), const_true_map(true) {
735 Parent::setGraph(_graph);
736 Parent::setNodeFilterMap(const_true_map);
737 Parent::setEdgeFilterMap(_edge_filter_map);
742 template<typename Graph>
743 class UndirGraphWrapper : public GraphWrapper<Graph> {
745 typedef GraphWrapper<Graph> Parent;
747 UndirGraphWrapper() : GraphWrapper<Graph>() { }
750 typedef typename GraphWrapper<Graph>::Node Node;
751 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
752 typedef typename GraphWrapper<Graph>::Edge Edge;
753 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
755 UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
758 friend class UndirGraphWrapper<Graph>;
759 bool out_or_in; //true iff out
760 typename Graph::OutEdgeIt out;
761 typename Graph::InEdgeIt in;
764 OutEdgeIt(const Invalid& i) : Edge(i) { }
765 OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
766 out_or_in=true; _G.graph->first(out, _n);
767 if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); }
769 operator Edge() const {
770 if (out_or_in) return Edge(out); else return Edge(in);
774 typedef OutEdgeIt InEdgeIt;
776 using GraphWrapper<Graph>::first;
777 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
778 i=OutEdgeIt(*this, p); return i;
781 using GraphWrapper<Graph>::next;
783 OutEdgeIt& next(OutEdgeIt& e) const {
785 typename Graph::Node n=this->graph->tail(e.out);
786 this->graph->next(e.out);
787 if (!this->graph->valid(e.out)) {
788 e.out_or_in=false; this->graph->first(e.in, n); }
790 this->graph->next(e.in);
795 Node aNode(const OutEdgeIt& e) const {
796 if (e.out_or_in) return this->graph->tail(e); else
797 return this->graph->head(e); }
798 Node bNode(const OutEdgeIt& e) const {
799 if (e.out_or_in) return this->graph->head(e); else
800 return this->graph->tail(e); }
802 // KEEP_MAPS(Parent, UndirGraphWrapper);
806 // /// \brief An undirected graph template.
808 // ///\warning Graph wrappers are in even more experimental state than the other
809 // ///parts of the lib. Use them at your own risk.
811 // /// An undirected graph template.
812 // /// This class works as an undirected graph and a directed graph of
813 // /// class \c Graph is used for the physical storage.
814 // /// \ingroup graphs
815 template<typename Graph>
816 class UndirGraph : public UndirGraphWrapper<Graph> {
817 typedef UndirGraphWrapper<Graph> Parent;
821 UndirGraph() : UndirGraphWrapper<Graph>() {
822 Parent::setGraph(gr);
825 // KEEP_MAPS(Parent, UndirGraph);
830 ///\brief A wrapper for composing a subgraph of a
831 /// bidirected graph made from a directed one.
833 /// A wrapper for composing a subgraph of a
834 /// bidirected graph made from a directed one.
836 ///\warning Graph wrappers are in even more experimental state than the other
837 ///parts of the lib. Use them at you own risk.
839 /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
840 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
841 /// reversing its orientation. We are given moreover two bool valued
842 /// maps on the edge-set,
843 /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
844 /// SubBidirGraphWrapper implements the graph structure with node-set
845 /// \f$V\f$ and edge-set
846 /// \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$.
847 /// The purpose of writing + instead of union is because parallel
848 /// edges can arise. (Similarly, antiparallel edges also can arise).
849 /// In other words, a subgraph of the bidirected graph obtained, which
850 /// is given by orienting the edges of the original graph in both directions.
851 /// As the oppositely directed edges are logically different,
852 /// the maps are able to attach different values for them.
854 /// An example for such a construction is \c RevGraphWrapper where the
855 /// forward_filter is everywhere false and the backward_filter is
856 /// everywhere true. We note that for sake of efficiency,
857 /// \c RevGraphWrapper is implemented in a different way.
858 /// But BidirGraphWrapper is obtained from
859 /// SubBidirGraphWrapper by considering everywhere true
860 /// valued maps both for forward_filter and backward_filter.
861 /// Finally, one of the most important applications of SubBidirGraphWrapper
862 /// is ResGraphWrapper, which stands for the residual graph in directed
863 /// flow and circulation problems.
864 /// As wrappers usually, the SubBidirGraphWrapper implements the
865 /// above mentioned graph structure without its physical storage,
866 /// that is the whole stuff is stored in constant memory.
867 template<typename Graph,
868 typename ForwardFilterMap, typename BackwardFilterMap>
869 class SubBidirGraphWrapper : public GraphWrapper<Graph> {
871 typedef GraphWrapper<Graph> Parent;
873 ForwardFilterMap* forward_filter;
874 BackwardFilterMap* backward_filter;
876 SubBidirGraphWrapper() : GraphWrapper<Graph>() { }
877 void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
878 forward_filter=&_forward_filter;
880 void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
881 backward_filter=&_backward_filter;
886 SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter,
887 BackwardFilterMap& _backward_filter) :
888 GraphWrapper<Graph>(_graph),
889 forward_filter(&_forward_filter), backward_filter(&_backward_filter) { }
890 SubBidirGraphWrapper(const SubBidirGraphWrapper<Graph,
891 ForwardFilterMap, BackwardFilterMap>& gw) :
893 forward_filter(gw.forward_filter),
894 backward_filter(gw.backward_filter) { }
899 friend class OutEdgeIt;
901 template<typename T> class EdgeMap;
903 typedef typename GraphWrapper<Graph>::Node Node;
905 typedef typename Graph::Edge GraphEdge;
906 /// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from
907 /// Graph::Edge. It contains an extra bool flag which is true
908 /// if and only if the
909 /// edge is the backward version of the original edge.
910 class Edge : public Graph::Edge {
911 friend class SubBidirGraphWrapper<Graph,
912 ForwardFilterMap, BackwardFilterMap>;
913 template<typename T> friend class EdgeMap;
915 bool backward; //true, iff backward
918 /// \todo =false is needed, or causes problems?
919 /// If \c _backward is false, then we get an edge corresponding to the
920 /// original one, otherwise its oppositely directed pair is obtained.
921 Edge(const typename Graph::Edge& e, bool _backward/*=false*/) :
922 Graph::Edge(e), backward(_backward) { }
923 Edge(Invalid i) : Graph::Edge(i), backward(true) { }
924 bool operator==(const Edge& v) const {
925 return (this->backward==v.backward &&
926 static_cast<typename Graph::Edge>(*this)==
927 static_cast<typename Graph::Edge>(v));
929 bool operator!=(const Edge& v) const {
930 return (this->backward!=v.backward ||
931 static_cast<typename Graph::Edge>(*this)!=
932 static_cast<typename Graph::Edge>(v));
936 class OutEdgeIt : public Edge {
937 friend class SubBidirGraphWrapper<Graph,
938 ForwardFilterMap, BackwardFilterMap>;
940 const SubBidirGraphWrapper<Graph,
941 ForwardFilterMap, BackwardFilterMap>* gw;
944 OutEdgeIt(Invalid i) : Edge(i) { }
945 OutEdgeIt(const SubBidirGraphWrapper<Graph,
946 ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
947 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
948 while (*static_cast<GraphEdge*>(this)!=INVALID &&
949 !(*(gw->forward_filter))[*this])
950 *(static_cast<GraphEdge*>(this))=
951 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
952 if (*static_cast<GraphEdge*>(this)==INVALID) {
953 *static_cast<Edge*>(this)=
954 Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true);
955 while (*static_cast<GraphEdge*>(this)!=INVALID &&
956 !(*(gw->backward_filter))[*this])
957 *(static_cast<GraphEdge*>(this))=
958 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
961 OutEdgeIt(const SubBidirGraphWrapper<Graph,
962 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
963 Edge(e), gw(&_gw) { }
964 OutEdgeIt& operator++() {
965 if (!this->backward) {
966 Node n=gw->tail(*this);
967 *(static_cast<GraphEdge*>(this))=
968 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
969 while (*static_cast<GraphEdge*>(this)!=INVALID &&
970 !(*(gw->forward_filter))[*this])
971 *(static_cast<GraphEdge*>(this))=
972 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
973 if (*static_cast<GraphEdge*>(this)==INVALID) {
974 *static_cast<Edge*>(this)=
975 Edge(typename Graph::InEdgeIt(*(gw->graph), n), true);
976 while (*static_cast<GraphEdge*>(this)!=INVALID &&
977 !(*(gw->backward_filter))[*this])
978 *(static_cast<GraphEdge*>(this))=
979 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
982 *(static_cast<GraphEdge*>(this))=
983 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
984 while (*static_cast<GraphEdge*>(this)!=INVALID &&
985 !(*(gw->backward_filter))[*this])
986 *(static_cast<GraphEdge*>(this))=
987 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
993 class InEdgeIt : public Edge {
994 friend class SubBidirGraphWrapper<Graph,
995 ForwardFilterMap, BackwardFilterMap>;
997 const SubBidirGraphWrapper<Graph,
998 ForwardFilterMap, BackwardFilterMap>* gw;
1001 InEdgeIt(Invalid i) : Edge(i) { }
1002 InEdgeIt(const SubBidirGraphWrapper<Graph,
1003 ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
1004 Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
1005 while (*static_cast<GraphEdge*>(this)!=INVALID &&
1006 !(*(gw->forward_filter))[*this])
1007 *(static_cast<GraphEdge*>(this))=
1008 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1009 if (*static_cast<GraphEdge*>(this)==INVALID) {
1010 *static_cast<Edge*>(this)=
1011 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true);
1012 while (*static_cast<GraphEdge*>(this)!=INVALID &&
1013 !(*(gw->backward_filter))[*this])
1014 *(static_cast<GraphEdge*>(this))=
1015 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1018 InEdgeIt(const SubBidirGraphWrapper<Graph,
1019 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
1020 Edge(e), gw(&_gw) { }
1021 InEdgeIt& operator++() {
1022 if (!this->backward) {
1023 Node n=gw->tail(*this);
1024 *(static_cast<GraphEdge*>(this))=
1025 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1026 while (*static_cast<GraphEdge*>(this)!=INVALID &&
1027 !(*(gw->forward_filter))[*this])
1028 *(static_cast<GraphEdge*>(this))=
1029 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1030 if (*static_cast<GraphEdge*>(this)==INVALID) {
1031 *static_cast<Edge*>(this)=
1032 Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true);
1033 while (*static_cast<GraphEdge*>(this)!=INVALID &&
1034 !(*(gw->backward_filter))[*this])
1035 *(static_cast<GraphEdge*>(this))=
1036 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1039 *(static_cast<GraphEdge*>(this))=
1040 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1041 while (*static_cast<GraphEdge*>(this)!=INVALID &&
1042 !(*(gw->backward_filter))[*this])
1043 *(static_cast<GraphEdge*>(this))=
1044 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1050 class EdgeIt : public Edge {
1051 friend class SubBidirGraphWrapper<Graph,
1052 ForwardFilterMap, BackwardFilterMap>;
1054 const SubBidirGraphWrapper<Graph,
1055 ForwardFilterMap, BackwardFilterMap>* gw;
1058 EdgeIt(Invalid i) : Edge(i) { }
1059 EdgeIt(const SubBidirGraphWrapper<Graph,
1060 ForwardFilterMap, BackwardFilterMap>& _gw) :
1061 Edge(typename Graph::EdgeIt(*(_gw.graph)), false), gw(&_gw) {
1062 while (*static_cast<GraphEdge*>(this)!=INVALID &&
1063 !(*(gw->forward_filter))[*this])
1064 *(static_cast<GraphEdge*>(this))=
1065 ++(typename Graph::EdgeIt(*(gw->graph), *this));
1066 if (*static_cast<GraphEdge*>(this)==INVALID) {
1067 *static_cast<Edge*>(this)=
1068 Edge(typename Graph::EdgeIt(*(_gw.graph)), true);
1069 while (*static_cast<GraphEdge*>(this)!=INVALID &&
1070 !(*(gw->backward_filter))[*this])
1071 *(static_cast<GraphEdge*>(this))=
1072 ++(typename Graph::EdgeIt(*(gw->graph), *this));
1075 EdgeIt(const SubBidirGraphWrapper<Graph,
1076 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
1077 Edge(e), gw(&_gw) { }
1078 EdgeIt& operator++() {
1079 if (!this->backward) {
1080 *(static_cast<GraphEdge*>(this))=
1081 ++(typename Graph::EdgeIt(*(gw->graph), *this));
1082 while (*static_cast<GraphEdge*>(this)!=INVALID &&
1083 !(*(gw->forward_filter))[*this])
1084 *(static_cast<GraphEdge*>(this))=
1085 ++(typename Graph::EdgeIt(*(gw->graph), *this));
1086 if (*static_cast<GraphEdge*>(this)==INVALID) {
1087 *static_cast<Edge*>(this)=
1088 Edge(typename Graph::EdgeIt(*(gw->graph)), true);
1089 while (*static_cast<GraphEdge*>(this)!=INVALID &&
1090 !(*(gw->backward_filter))[*this])
1091 *(static_cast<GraphEdge*>(this))=
1092 ++(typename Graph::EdgeIt(*(gw->graph), *this));
1095 *(static_cast<GraphEdge*>(this))=
1096 ++(typename Graph::EdgeIt(*(gw->graph), *this));
1097 while (*static_cast<GraphEdge*>(this)!=INVALID &&
1098 !(*(gw->backward_filter))[*this])
1099 *(static_cast<GraphEdge*>(this))=
1100 ++(typename Graph::EdgeIt(*(gw->graph), *this));
1106 using GraphWrapper<Graph>::first;
1107 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1108 i=OutEdgeIt(*this, p); return i;
1110 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1111 i=InEdgeIt(*this, p); return i;
1113 EdgeIt& first(EdgeIt& i) const {
1114 i=EdgeIt(*this); return i;
1118 Node tail(Edge e) const {
1119 return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
1120 Node head(Edge e) const {
1121 return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
1123 /// Gives back the opposite edge.
1124 Edge opposite(const Edge& e) const {
1126 f.backward=!f.backward;
1130 /// \warning This is a linear time operation and works only if
1131 /// \c Graph::EdgeIt is defined.
1132 int edgeNum() const {
1134 for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
1138 bool forward(const Edge& e) const { return !e.backward; }
1139 bool backward(const Edge& e) const { return e.backward; }
1142 template <typename T>
1143 /// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two
1144 /// Graph::EdgeMap one for the forward edges and
1145 /// one for the backward edges.
1147 template <typename TT> friend class EdgeMap;
1148 typename Graph::template EdgeMap<T> forward_map, backward_map;
1150 typedef T ValueType;
1151 typedef Edge KeyType;
1153 EdgeMap(const SubBidirGraphWrapper<Graph,
1154 ForwardFilterMap, BackwardFilterMap>& g) :
1155 forward_map(*(g.graph)), backward_map(*(g.graph)) { }
1157 EdgeMap(const SubBidirGraphWrapper<Graph,
1158 ForwardFilterMap, BackwardFilterMap>& g, T a) :
1159 forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
1161 template <typename TT>
1162 EdgeMap(const EdgeMap<TT>& copy)
1163 : forward_map(copy.forward_map), backward_map(copy.backward_map) {}
1165 template <typename TT>
1166 EdgeMap& operator=(const EdgeMap<TT>& copy) {
1167 forward_map = copy.forward_map;
1168 backward_map = copy.backward_map;
1172 void set(Edge e, T a) {
1174 forward_map.set(e, a);
1176 backward_map.set(e, a);
1179 typename Graph::template EdgeMap<T>::ConstReferenceType
1180 operator[](Edge e) const {
1182 return forward_map[e];
1184 return backward_map[e];
1187 typename Graph::template EdgeMap<T>::ReferenceType
1188 operator[](Edge e) {
1190 return forward_map[e];
1192 return backward_map[e];
1196 forward_map.update();
1197 backward_map.update();
1202 // KEEP_NODE_MAP(Parent, SubBidirGraphWrapper);
1207 ///\brief A wrapper for composing bidirected graph from a directed one.
1209 ///\warning Graph wrappers are in even more experimental state than the other
1210 ///parts of the lib. Use them at you own risk.
1212 /// A wrapper for composing bidirected graph from a directed one.
1213 /// A bidirected graph is composed over the directed one without physical
1214 /// storage. As the oppositely directed edges are logically different ones
1215 /// the maps are able to attach different values for them.
1216 template<typename Graph>
1217 class BidirGraphWrapper :
1218 public SubBidirGraphWrapper<
1220 ConstMap<typename Graph::Edge, bool>,
1221 ConstMap<typename Graph::Edge, bool> > {
1223 typedef SubBidirGraphWrapper<
1225 ConstMap<typename Graph::Edge, bool>,
1226 ConstMap<typename Graph::Edge, bool> > Parent;
1228 ConstMap<typename Graph::Edge, bool> cm;
1230 BidirGraphWrapper() : Parent(), cm(true) {
1231 Parent::setForwardFilterMap(cm);
1232 Parent::setBackwardFilterMap(cm);
1235 BidirGraphWrapper(Graph& _graph) : Parent() {
1236 Parent::setGraph(_graph);
1237 Parent::setForwardFilterMap(cm);
1238 Parent::setBackwardFilterMap(cm);
1241 int edgeNum() const {
1242 return 2*this->graph->edgeNum();
1244 // KEEP_MAPS(Parent, BidirGraphWrapper);
1248 /// \brief A bidirected graph template.
1250 ///\warning Graph wrappers are in even more experimental state than the other
1251 ///parts of the lib. Use them at you own risk.
1253 /// A bidirected graph template.
1254 /// Such a bidirected graph stores each pair of oppositely directed edges
1255 /// ones in the memory, i.e. a directed graph of type
1256 /// \c Graph is used for that.
1257 /// As the oppositely directed edges are logically different ones
1258 /// the maps are able to attach different values for them.
1260 template<typename Graph>
1261 class BidirGraph : public BidirGraphWrapper<Graph> {
1263 typedef UndirGraphWrapper<Graph> Parent;
1267 BidirGraph() : BidirGraphWrapper<Graph>() {
1268 Parent::setGraph(gr);
1270 // KEEP_MAPS(Parent, BidirGraph);
1275 template<typename Graph, typename Number,
1276 typename CapacityMap, typename FlowMap>
1277 class ResForwardFilter {
1278 // const Graph* graph;
1279 const CapacityMap* capacity;
1280 const FlowMap* flow;
1282 ResForwardFilter(/*const Graph& _graph, */
1283 const CapacityMap& _capacity, const FlowMap& _flow) :
1284 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1285 ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1286 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1287 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1288 bool operator[](const typename Graph::Edge& e) const {
1289 return (Number((*flow)[e]) < Number((*capacity)[e]));
1293 template<typename Graph, typename Number,
1294 typename CapacityMap, typename FlowMap>
1295 class ResBackwardFilter {
1296 const CapacityMap* capacity;
1297 const FlowMap* flow;
1299 ResBackwardFilter(/*const Graph& _graph,*/
1300 const CapacityMap& _capacity, const FlowMap& _flow) :
1301 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1302 ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1303 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1304 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1305 bool operator[](const typename Graph::Edge& e) const {
1306 return (Number(0) < Number((*flow)[e]));
1311 /// A wrapper for composing the residual graph for directed flow and circulation problems.
1313 ///\warning Graph wrappers are in even more experimental state than the other
1314 ///parts of the lib. Use them at you own risk.
1316 /// A wrapper for composing the residual graph for directed flow and circulation problems.
1317 template<typename Graph, typename Number,
1318 typename CapacityMap, typename FlowMap>
1319 class ResGraphWrapper :
1320 public SubBidirGraphWrapper<
1322 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1323 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1325 typedef SubBidirGraphWrapper<
1327 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1328 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1330 const CapacityMap* capacity;
1332 ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1333 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1334 ResGraphWrapper() : Parent(),
1335 capacity(0), flow(0) { }
1336 void setCapacityMap(const CapacityMap& _capacity) {
1337 capacity=&_capacity;
1338 forward_filter.setCapacity(_capacity);
1339 backward_filter.setCapacity(_capacity);
1341 void setFlowMap(FlowMap& _flow) {
1343 forward_filter.setFlow(_flow);
1344 backward_filter.setFlow(_flow);
1347 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1349 Parent(), capacity(&_capacity), flow(&_flow),
1350 forward_filter(/*_graph,*/ _capacity, _flow),
1351 backward_filter(/*_graph,*/ _capacity, _flow) {
1352 Parent::setGraph(_graph);
1353 Parent::setForwardFilterMap(forward_filter);
1354 Parent::setBackwardFilterMap(backward_filter);
1357 typedef typename Parent::Edge Edge;
1359 void augment(const Edge& e, Number a) const {
1360 if (Parent::forward(e))
1361 flow->set(e, (*flow)[e]+a);
1363 flow->set(e, (*flow)[e]-a);
1366 /// \brief Residual capacity map.
1368 /// In generic residual graphs the residual capacity can be obtained
1372 const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
1374 typedef Number ValueType;
1375 typedef Edge KeyType;
1376 ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>&
1377 _res_graph) : res_graph(&_res_graph) { }
1378 Number operator[](const Edge& e) const {
1379 if (res_graph->forward(e))
1380 return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1382 return (*(res_graph->flow))[e];
1386 // KEEP_MAPS(Parent, ResGraphWrapper);
1390 /// For blocking flows.
1392 ///\warning Graph wrappers are in even more experimental state than the other
1393 ///parts of the lib. Use them at you own risk.
1395 /// This graph wrapper is used for on-the-fly
1396 /// Dinits blocking flow computations.
1397 /// For each node, an out-edge is stored which is used when the
1399 /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1403 /// \author Marton Makai
1404 template<typename Graph, typename FirstOutEdgesMap>
1405 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1407 typedef GraphWrapper<Graph> Parent;
1409 FirstOutEdgesMap* first_out_edges;
1411 ErasingFirstGraphWrapper(Graph& _graph,
1412 FirstOutEdgesMap& _first_out_edges) :
1413 GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
1415 typedef typename GraphWrapper<Graph>::Node Node;
1416 typedef typename GraphWrapper<Graph>::Edge Edge;
1417 class OutEdgeIt : public Edge {
1418 friend class GraphWrapper<Graph>;
1419 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1420 const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>* gw;
1423 OutEdgeIt(Invalid i) : Edge(i) { }
1424 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
1426 Edge((*(_gw.first_out_edges))[n]), gw(&_gw) { }
1427 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
1429 Edge(e), gw(&_gw) { }
1430 OutEdgeIt& operator++() {
1431 *(static_cast<Edge*>(this))=
1432 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1437 using GraphWrapper<Graph>::first;
1438 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1439 i=OutEdgeIt(*this, p); return i;
1441 void erase(const Edge& e) const {
1443 typename Graph::OutEdgeIt f(*Parent::graph, n);
1445 first_out_edges->set(n, f);
1448 // KEEP_MAPS(Parent, ErasingFirstGraphWrapper);
1455 #endif //LEMON_GRAPH_WRAPPER_H