New EdgeSubGraphWrapper class specializing SubGraphWrapper in the way that only the edge-set can be filtered.
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 Consider now a mathematically more invloved problem, where the application
372 of SubGraphWrapper is reasonable sure enough. If a shortest path is to be
373 searched between two nodes \c s and \c t, then this can be done easily by
374 applying the Dijkstra algorithm class. What happens, if a maximum number of
375 edge-disjoint shortest paths is to be computed. It can be proved that an
376 edge can be in a shortest path if and only if it is tight with respect to
377 the potential function computed by Dijkstra. Moreover, any path containing
378 only such edges is a shortest one. Thus we have to compute a maximum number
379 of edge-disjoint path between \c s and \c t in the graph which has edge-set
380 all the tight edges. The computation will be demonstrated on the following
381 graph, which is read from a dimacs file.
384 digraph lemon_dot_example {
385 node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
386 n0 [ label="0 (s)" ];
392 n6 [ label="6 (t)" ];
393 edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
394 n5 -> n6 [ label="9, length:4" ];
395 n4 -> n6 [ label="8, length:2" ];
396 n3 -> n5 [ label="7, length:1" ];
397 n2 -> n5 [ label="6, length:3" ];
398 n2 -> n6 [ label="5, length:5" ];
399 n2 -> n4 [ label="4, length:2" ];
400 n1 -> n4 [ label="3, length:3" ];
401 n0 -> n3 [ label="2, length:1" ];
402 n0 -> n2 [ label="1, length:2" ];
403 n0 -> n1 [ label="0, length:3" ];
412 readDimacs(std::cin, g, length, s, t);
414 cout << "edges with lengths (of form id, tail--length->head): " << endl;
415 for(EdgeIt e(g); e!=INVALID; ++e)
416 cout << g.id(e) << ", " << g.id(g.tail(e)) << "--"
417 << length[e] << "->" << g.id(g.head(e)) << endl;
419 cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
421 Next, the potential function is computed with Dijkstra.
423 typedef Dijkstra<Graph, LengthMap> Dijkstra;
424 Dijkstra dijkstra(g, length);
427 Next, we consrtruct a map which filters the edge-set to the tight edges.
429 typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
431 TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
433 typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;
434 SubGW gw(g, tight_edge_filter);
436 Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
437 with a max flow algorithm Preflow.
439 ConstMap<Edge, int> const_1_map(1);
440 Graph::EdgeMap<int> flow(g, 0);
442 Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
443 preflow(gw, s, t, const_1_map, flow);
448 cout << "maximum number of edge-disjoint shortest path: "
449 << preflow.flowValue() << endl;
450 cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
452 for(EdgeIt e(g); e!=INVALID; ++e)
454 cout << " " << g.id(g.tail(e)) << "--"
455 << length[e] << "->" << g.id(g.head(e)) << endl;
457 The program has the following (expected :-)) output:
459 edges with lengths (of form id, tail--length->head):
471 maximum number of edge-disjoint shortest path: 2
472 edges of the maximum number of edge-disjoint shortest s-t paths:
482 template<typename Graph, typename NodeFilterMap,
483 typename EdgeFilterMap>
484 class SubGraphWrapper : public GraphWrapper<Graph> {
486 typedef GraphWrapper<Graph> Parent;
488 NodeFilterMap* node_filter_map;
489 EdgeFilterMap* edge_filter_map;
491 SubGraphWrapper() : GraphWrapper<Graph>(),
492 node_filter_map(0), edge_filter_map(0) { }
493 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
494 node_filter_map=&_node_filter_map;
496 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
497 edge_filter_map=&_edge_filter_map;
501 SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
502 EdgeFilterMap& _edge_filter_map) :
503 GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
504 edge_filter_map(&_edge_filter_map) { }
506 typedef typename GraphWrapper<Graph>::Node Node;
507 class NodeIt : public Node {
508 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
509 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
512 NodeIt(Invalid i) : Node(i) { }
513 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
514 Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) {
515 while (*static_cast<Node*>(this)!=INVALID &&
516 !(*(gw->node_filter_map))[*this])
517 *(static_cast<Node*>(this))=
518 ++(typename Graph::NodeIt(*(gw->graph), *this));
520 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
522 Node(n), gw(&_gw) { }
523 NodeIt& operator++() {
524 *(static_cast<Node*>(this))=
525 ++(typename Graph::NodeIt(*(gw->graph), *this));
526 while (*static_cast<Node*>(this)!=INVALID &&
527 !(*(gw->node_filter_map))[*this])
528 *(static_cast<Node*>(this))=
529 ++(typename Graph::NodeIt(*(gw->graph), *this));
533 typedef typename GraphWrapper<Graph>::Edge Edge;
534 class OutEdgeIt : public Edge {
535 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
536 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
539 OutEdgeIt(Invalid i) : Edge(i) { }
540 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
541 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) {
542 while (*static_cast<Edge*>(this)!=INVALID &&
543 !(*(gw->edge_filter_map))[*this])
544 *(static_cast<Edge*>(this))=
545 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
547 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
549 Edge(e), gw(&_gw) { }
550 OutEdgeIt& operator++() {
551 *(static_cast<Edge*>(this))=
552 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
553 while (*static_cast<Edge*>(this)!=INVALID &&
554 !(*(gw->edge_filter_map))[*this])
555 *(static_cast<Edge*>(this))=
556 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
560 class InEdgeIt : public Edge {
561 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
562 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
565 // InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
566 InEdgeIt(Invalid i) : Edge(i) { }
567 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
568 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) {
569 while (*static_cast<Edge*>(this)!=INVALID &&
570 !(*(gw->edge_filter_map))[*this])
571 *(static_cast<Edge*>(this))=
572 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
574 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
576 Edge(e), gw(&_gw) { }
577 InEdgeIt& operator++() {
578 *(static_cast<Edge*>(this))=
579 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
580 while (*static_cast<Edge*>(this)!=INVALID &&
581 !(*(gw->edge_filter_map))[*this])
582 *(static_cast<Edge*>(this))=
583 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
587 class EdgeIt : public Edge {
588 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
589 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
592 EdgeIt(Invalid i) : Edge(i) { }
593 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
594 Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) {
595 while (*static_cast<Edge*>(this)!=INVALID &&
596 !(*(gw->edge_filter_map))[*this])
597 *(static_cast<Edge*>(this))=
598 ++(typename Graph::EdgeIt(*(gw->graph), *this));
600 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
602 Edge(e), gw(&_gw) { }
603 EdgeIt& operator++() {
604 *(static_cast<Edge*>(this))=
605 ++(typename Graph::EdgeIt(*(gw->graph), *this));
606 while (*static_cast<Edge*>(this)!=INVALID &&
607 !(*(gw->edge_filter_map))[*this])
608 *(static_cast<Edge*>(this))=
609 ++(typename Graph::EdgeIt(*(gw->graph), *this));
614 NodeIt& first(NodeIt& i) const {
615 i=NodeIt(*this); return i;
617 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
618 i=OutEdgeIt(*this, p); return i;
620 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
621 i=InEdgeIt(*this, p); return i;
623 EdgeIt& first(EdgeIt& i) const {
624 i=EdgeIt(*this); return i;
627 /// This function hides \c n in the graph, i.e. the iteration
628 /// jumps over it. This is done by simply setting the value of \c n
629 /// to be false in the corresponding node-map.
630 void hide(const Node& n) const { node_filter_map->set(n, false); }
632 /// This function hides \c e in the graph, i.e. the iteration
633 /// jumps over it. This is done by simply setting the value of \c e
634 /// to be false in the corresponding edge-map.
635 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
637 /// The value of \c n is set to be true in the node-map which stores
638 /// hide information. If \c n was hidden previuosly, then it is shown
640 void unHide(const Node& n) const { node_filter_map->set(n, true); }
642 /// The value of \c e is set to be true in the edge-map which stores
643 /// hide information. If \c e was hidden previuosly, then it is shown
645 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
647 /// Returns true if \c n is hidden.
648 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
650 /// Returns true if \c n is hidden.
651 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
653 /// \warning This is a linear time operation and works only if
654 /// \c Graph::NodeIt is defined.
655 int nodeNum() const {
657 for (NodeIt n(*this); n!=INVALID; ++n) ++i;
661 /// \warning This is a linear time operation and works only if
662 /// \c Graph::EdgeIt is defined.
663 int edgeNum() const {
665 for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
669 // KEEP_MAPS(Parent, SubGraphWrapper);
673 /*! \brief A wrapper for hiding edges from a graph.
675 \warning Graph wrappers are in even more experimental state than the other
676 parts of the lib. Use them at you own risk.
678 A wrapper for hiding edges from a graph.
679 This wrapper specializes SubGraphWrapper in the way that only the edge-set
683 template<typename Graph, typename EdgeFilterMap>
684 class EdgeSubGraphWrapper :
685 public SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
688 typedef SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
689 EdgeFilterMap> Parent;
691 ConstMap<typename Graph::Node, bool> const_true_map;
693 EdgeSubGraphWrapper(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
694 Parent(), const_true_map(true) {
695 Parent::setGraph(_graph);
696 Parent::setNodeFilterMap(const_true_map);
697 Parent::setEdgeFilterMap(_edge_filter_map);
702 template<typename Graph>
703 class UndirGraphWrapper : public GraphWrapper<Graph> {
705 typedef GraphWrapper<Graph> Parent;
707 UndirGraphWrapper() : GraphWrapper<Graph>() { }
710 typedef typename GraphWrapper<Graph>::Node Node;
711 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
712 typedef typename GraphWrapper<Graph>::Edge Edge;
713 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
715 UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
718 friend class UndirGraphWrapper<Graph>;
719 bool out_or_in; //true iff out
720 typename Graph::OutEdgeIt out;
721 typename Graph::InEdgeIt in;
724 OutEdgeIt(const Invalid& i) : Edge(i) { }
725 OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
726 out_or_in=true; _G.graph->first(out, _n);
727 if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); }
729 operator Edge() const {
730 if (out_or_in) return Edge(out); else return Edge(in);
734 typedef OutEdgeIt InEdgeIt;
736 using GraphWrapper<Graph>::first;
737 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
738 i=OutEdgeIt(*this, p); return i;
741 using GraphWrapper<Graph>::next;
743 OutEdgeIt& next(OutEdgeIt& e) const {
745 typename Graph::Node n=this->graph->tail(e.out);
746 this->graph->next(e.out);
747 if (!this->graph->valid(e.out)) {
748 e.out_or_in=false; this->graph->first(e.in, n); }
750 this->graph->next(e.in);
755 Node aNode(const OutEdgeIt& e) const {
756 if (e.out_or_in) return this->graph->tail(e); else
757 return this->graph->head(e); }
758 Node bNode(const OutEdgeIt& e) const {
759 if (e.out_or_in) return this->graph->head(e); else
760 return this->graph->tail(e); }
762 // KEEP_MAPS(Parent, UndirGraphWrapper);
766 // /// \brief An undirected graph template.
768 // ///\warning Graph wrappers are in even more experimental state than the other
769 // ///parts of the lib. Use them at your own risk.
771 // /// An undirected graph template.
772 // /// This class works as an undirected graph and a directed graph of
773 // /// class \c Graph is used for the physical storage.
774 // /// \ingroup graphs
775 template<typename Graph>
776 class UndirGraph : public UndirGraphWrapper<Graph> {
777 typedef UndirGraphWrapper<Graph> Parent;
781 UndirGraph() : UndirGraphWrapper<Graph>() {
782 Parent::setGraph(gr);
785 // KEEP_MAPS(Parent, UndirGraph);
790 ///\brief A wrapper for composing a subgraph of a
791 /// bidirected graph made from a directed one.
793 /// A wrapper for composing a subgraph of a
794 /// bidirected graph made from a directed one.
796 ///\warning Graph wrappers are in even more experimental state than the other
797 ///parts of the lib. Use them at you own risk.
799 /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
800 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
801 /// reversing its orientation. We are given moreover two bool valued
802 /// maps on the edge-set,
803 /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
804 /// SubBidirGraphWrapper implements the graph structure with node-set
805 /// \f$V\f$ and edge-set
806 /// \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$.
807 /// The purpose of writing + instead of union is because parallel
808 /// edges can arise. (Similarly, antiparallel edges also can arise).
809 /// In other words, a subgraph of the bidirected graph obtained, which
810 /// is given by orienting the edges of the original graph in both directions.
811 /// As the oppositely directed edges are logically different,
812 /// the maps are able to attach different values for them.
814 /// An example for such a construction is \c RevGraphWrapper where the
815 /// forward_filter is everywhere false and the backward_filter is
816 /// everywhere true. We note that for sake of efficiency,
817 /// \c RevGraphWrapper is implemented in a different way.
818 /// But BidirGraphWrapper is obtained from
819 /// SubBidirGraphWrapper by considering everywhere true
820 /// valued maps both for forward_filter and backward_filter.
821 /// Finally, one of the most important applications of SubBidirGraphWrapper
822 /// is ResGraphWrapper, which stands for the residual graph in directed
823 /// flow and circulation problems.
824 /// As wrappers usually, the SubBidirGraphWrapper implements the
825 /// above mentioned graph structure without its physical storage,
826 /// that is the whole stuff is stored in constant memory.
827 template<typename Graph,
828 typename ForwardFilterMap, typename BackwardFilterMap>
829 class SubBidirGraphWrapper : public GraphWrapper<Graph> {
831 typedef GraphWrapper<Graph> Parent;
833 ForwardFilterMap* forward_filter;
834 BackwardFilterMap* backward_filter;
836 SubBidirGraphWrapper() : GraphWrapper<Graph>() { }
837 void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
838 forward_filter=&_forward_filter;
840 void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
841 backward_filter=&_backward_filter;
846 SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter,
847 BackwardFilterMap& _backward_filter) :
848 GraphWrapper<Graph>(_graph),
849 forward_filter(&_forward_filter), backward_filter(&_backward_filter) { }
850 SubBidirGraphWrapper(const SubBidirGraphWrapper<Graph,
851 ForwardFilterMap, BackwardFilterMap>& gw) :
853 forward_filter(gw.forward_filter),
854 backward_filter(gw.backward_filter) { }
859 friend class OutEdgeIt;
861 template<typename T> class EdgeMap;
863 typedef typename GraphWrapper<Graph>::Node Node;
865 typedef typename Graph::Edge GraphEdge;
866 /// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from
867 /// Graph::Edge. It contains an extra bool flag which is true
868 /// if and only if the
869 /// edge is the backward version of the original edge.
870 class Edge : public Graph::Edge {
871 friend class SubBidirGraphWrapper<Graph,
872 ForwardFilterMap, BackwardFilterMap>;
873 template<typename T> friend class EdgeMap;
875 bool backward; //true, iff backward
878 /// \todo =false is needed, or causes problems?
879 /// If \c _backward is false, then we get an edge corresponding to the
880 /// original one, otherwise its oppositely directed pair is obtained.
881 Edge(const typename Graph::Edge& e, bool _backward/*=false*/) :
882 Graph::Edge(e), backward(_backward) { }
883 Edge(Invalid i) : Graph::Edge(i), backward(true) { }
884 bool operator==(const Edge& v) const {
885 return (this->backward==v.backward &&
886 static_cast<typename Graph::Edge>(*this)==
887 static_cast<typename Graph::Edge>(v));
889 bool operator!=(const Edge& v) const {
890 return (this->backward!=v.backward ||
891 static_cast<typename Graph::Edge>(*this)!=
892 static_cast<typename Graph::Edge>(v));
896 class OutEdgeIt : public Edge {
897 friend class SubBidirGraphWrapper<Graph,
898 ForwardFilterMap, BackwardFilterMap>;
900 const SubBidirGraphWrapper<Graph,
901 ForwardFilterMap, BackwardFilterMap>* gw;
904 OutEdgeIt(Invalid i) : Edge(i) { }
905 OutEdgeIt(const SubBidirGraphWrapper<Graph,
906 ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
907 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
908 while (*static_cast<GraphEdge*>(this)!=INVALID &&
909 !(*(gw->forward_filter))[*this])
910 *(static_cast<GraphEdge*>(this))=
911 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
912 if (*static_cast<GraphEdge*>(this)==INVALID) {
913 *static_cast<Edge*>(this)=
914 Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true);
915 while (*static_cast<GraphEdge*>(this)!=INVALID &&
916 !(*(gw->backward_filter))[*this])
917 *(static_cast<GraphEdge*>(this))=
918 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
921 OutEdgeIt(const SubBidirGraphWrapper<Graph,
922 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
923 Edge(e), gw(&_gw) { }
924 OutEdgeIt& operator++() {
925 if (!this->backward) {
926 Node n=gw->tail(*this);
927 *(static_cast<GraphEdge*>(this))=
928 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
929 while (*static_cast<GraphEdge*>(this)!=INVALID &&
930 !(*(gw->forward_filter))[*this])
931 *(static_cast<GraphEdge*>(this))=
932 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
933 if (*static_cast<GraphEdge*>(this)==INVALID) {
934 *static_cast<Edge*>(this)=
935 Edge(typename Graph::InEdgeIt(*(gw->graph), n), true);
936 while (*static_cast<GraphEdge*>(this)!=INVALID &&
937 !(*(gw->backward_filter))[*this])
938 *(static_cast<GraphEdge*>(this))=
939 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
942 *(static_cast<GraphEdge*>(this))=
943 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
944 while (*static_cast<GraphEdge*>(this)!=INVALID &&
945 !(*(gw->backward_filter))[*this])
946 *(static_cast<GraphEdge*>(this))=
947 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
953 class InEdgeIt : public Edge {
954 friend class SubBidirGraphWrapper<Graph,
955 ForwardFilterMap, BackwardFilterMap>;
957 const SubBidirGraphWrapper<Graph,
958 ForwardFilterMap, BackwardFilterMap>* gw;
961 InEdgeIt(Invalid i) : Edge(i) { }
962 InEdgeIt(const SubBidirGraphWrapper<Graph,
963 ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
964 Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
965 while (*static_cast<GraphEdge*>(this)!=INVALID &&
966 !(*(gw->forward_filter))[*this])
967 *(static_cast<GraphEdge*>(this))=
968 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
969 if (*static_cast<GraphEdge*>(this)==INVALID) {
970 *static_cast<Edge*>(this)=
971 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true);
972 while (*static_cast<GraphEdge*>(this)!=INVALID &&
973 !(*(gw->backward_filter))[*this])
974 *(static_cast<GraphEdge*>(this))=
975 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
978 InEdgeIt(const SubBidirGraphWrapper<Graph,
979 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
980 Edge(e), gw(&_gw) { }
981 InEdgeIt& operator++() {
982 if (!this->backward) {
983 Node n=gw->tail(*this);
984 *(static_cast<GraphEdge*>(this))=
985 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
986 while (*static_cast<GraphEdge*>(this)!=INVALID &&
987 !(*(gw->forward_filter))[*this])
988 *(static_cast<GraphEdge*>(this))=
989 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
990 if (*static_cast<GraphEdge*>(this)==INVALID) {
991 *static_cast<Edge*>(this)=
992 Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true);
993 while (*static_cast<GraphEdge*>(this)!=INVALID &&
994 !(*(gw->backward_filter))[*this])
995 *(static_cast<GraphEdge*>(this))=
996 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
999 *(static_cast<GraphEdge*>(this))=
1000 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1001 while (*static_cast<GraphEdge*>(this)!=INVALID &&
1002 !(*(gw->backward_filter))[*this])
1003 *(static_cast<GraphEdge*>(this))=
1004 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1010 class EdgeIt : public Edge {
1011 friend class SubBidirGraphWrapper<Graph,
1012 ForwardFilterMap, BackwardFilterMap>;
1014 const SubBidirGraphWrapper<Graph,
1015 ForwardFilterMap, BackwardFilterMap>* gw;
1018 EdgeIt(Invalid i) : Edge(i) { }
1019 EdgeIt(const SubBidirGraphWrapper<Graph,
1020 ForwardFilterMap, BackwardFilterMap>& _gw) :
1021 Edge(typename Graph::EdgeIt(*(_gw.graph)), false), gw(&_gw) {
1022 while (*static_cast<GraphEdge*>(this)!=INVALID &&
1023 !(*(gw->forward_filter))[*this])
1024 *(static_cast<GraphEdge*>(this))=
1025 ++(typename Graph::EdgeIt(*(gw->graph), *this));
1026 if (*static_cast<GraphEdge*>(this)==INVALID) {
1027 *static_cast<Edge*>(this)=
1028 Edge(typename Graph::EdgeIt(*(_gw.graph)), true);
1029 while (*static_cast<GraphEdge*>(this)!=INVALID &&
1030 !(*(gw->backward_filter))[*this])
1031 *(static_cast<GraphEdge*>(this))=
1032 ++(typename Graph::EdgeIt(*(gw->graph), *this));
1035 EdgeIt(const SubBidirGraphWrapper<Graph,
1036 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
1037 Edge(e), gw(&_gw) { }
1038 EdgeIt& operator++() {
1039 if (!this->backward) {
1040 *(static_cast<GraphEdge*>(this))=
1041 ++(typename Graph::EdgeIt(*(gw->graph), *this));
1042 while (*static_cast<GraphEdge*>(this)!=INVALID &&
1043 !(*(gw->forward_filter))[*this])
1044 *(static_cast<GraphEdge*>(this))=
1045 ++(typename Graph::EdgeIt(*(gw->graph), *this));
1046 if (*static_cast<GraphEdge*>(this)==INVALID) {
1047 *static_cast<Edge*>(this)=
1048 Edge(typename Graph::EdgeIt(*(gw->graph)), true);
1049 while (*static_cast<GraphEdge*>(this)!=INVALID &&
1050 !(*(gw->backward_filter))[*this])
1051 *(static_cast<GraphEdge*>(this))=
1052 ++(typename Graph::EdgeIt(*(gw->graph), *this));
1055 *(static_cast<GraphEdge*>(this))=
1056 ++(typename Graph::EdgeIt(*(gw->graph), *this));
1057 while (*static_cast<GraphEdge*>(this)!=INVALID &&
1058 !(*(gw->backward_filter))[*this])
1059 *(static_cast<GraphEdge*>(this))=
1060 ++(typename Graph::EdgeIt(*(gw->graph), *this));
1066 using GraphWrapper<Graph>::first;
1067 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1068 i=OutEdgeIt(*this, p); return i;
1070 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1071 i=InEdgeIt(*this, p); return i;
1073 EdgeIt& first(EdgeIt& i) const {
1074 i=EdgeIt(*this); return i;
1078 Node tail(Edge e) const {
1079 return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
1080 Node head(Edge e) const {
1081 return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
1083 /// Gives back the opposite edge.
1084 Edge opposite(const Edge& e) const {
1086 f.backward=!f.backward;
1090 /// \warning This is a linear time operation and works only if
1091 /// \c Graph::EdgeIt is defined.
1092 int edgeNum() const {
1094 for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
1098 bool forward(const Edge& e) const { return !e.backward; }
1099 bool backward(const Edge& e) const { return e.backward; }
1102 template <typename T>
1103 /// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two
1104 /// Graph::EdgeMap one for the forward edges and
1105 /// one for the backward edges.
1107 template <typename TT> friend class EdgeMap;
1108 typename Graph::template EdgeMap<T> forward_map, backward_map;
1110 typedef T ValueType;
1111 typedef Edge KeyType;
1113 EdgeMap(const SubBidirGraphWrapper<Graph,
1114 ForwardFilterMap, BackwardFilterMap>& g) :
1115 forward_map(*(g.graph)), backward_map(*(g.graph)) { }
1117 EdgeMap(const SubBidirGraphWrapper<Graph,
1118 ForwardFilterMap, BackwardFilterMap>& g, T a) :
1119 forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
1121 template <typename TT>
1122 EdgeMap(const EdgeMap<TT>& copy)
1123 : forward_map(copy.forward_map), backward_map(copy.backward_map) {}
1125 template <typename TT>
1126 EdgeMap& operator=(const EdgeMap<TT>& copy) {
1127 forward_map = copy.forward_map;
1128 backward_map = copy.backward_map;
1132 void set(Edge e, T a) {
1134 forward_map.set(e, a);
1136 backward_map.set(e, a);
1139 typename Graph::template EdgeMap<T>::ConstReferenceType
1140 operator[](Edge e) const {
1142 return forward_map[e];
1144 return backward_map[e];
1147 typename Graph::template EdgeMap<T>::ReferenceType
1148 operator[](Edge e) {
1150 return forward_map[e];
1152 return backward_map[e];
1156 forward_map.update();
1157 backward_map.update();
1162 // KEEP_NODE_MAP(Parent, SubBidirGraphWrapper);
1167 ///\brief A wrapper for composing bidirected graph from a directed one.
1169 ///\warning Graph wrappers are in even more experimental state than the other
1170 ///parts of the lib. Use them at you own risk.
1172 /// A wrapper for composing bidirected graph from a directed one.
1173 /// A bidirected graph is composed over the directed one without physical
1174 /// storage. As the oppositely directed edges are logically different ones
1175 /// the maps are able to attach different values for them.
1176 template<typename Graph>
1177 class BidirGraphWrapper :
1178 public SubBidirGraphWrapper<
1180 ConstMap<typename Graph::Edge, bool>,
1181 ConstMap<typename Graph::Edge, bool> > {
1183 typedef SubBidirGraphWrapper<
1185 ConstMap<typename Graph::Edge, bool>,
1186 ConstMap<typename Graph::Edge, bool> > Parent;
1188 ConstMap<typename Graph::Edge, bool> cm;
1190 BidirGraphWrapper() : Parent(), cm(true) {
1191 Parent::setForwardFilterMap(cm);
1192 Parent::setBackwardFilterMap(cm);
1195 BidirGraphWrapper(Graph& _graph) : Parent() {
1196 Parent::setGraph(_graph);
1197 Parent::setForwardFilterMap(cm);
1198 Parent::setBackwardFilterMap(cm);
1201 int edgeNum() const {
1202 return 2*this->graph->edgeNum();
1204 // KEEP_MAPS(Parent, BidirGraphWrapper);
1208 /// \brief A bidirected graph template.
1210 ///\warning Graph wrappers are in even more experimental state than the other
1211 ///parts of the lib. Use them at you own risk.
1213 /// A bidirected graph template.
1214 /// Such a bidirected graph stores each pair of oppositely directed edges
1215 /// ones in the memory, i.e. a directed graph of type
1216 /// \c Graph is used for that.
1217 /// As the oppositely directed edges are logically different ones
1218 /// the maps are able to attach different values for them.
1220 template<typename Graph>
1221 class BidirGraph : public BidirGraphWrapper<Graph> {
1223 typedef UndirGraphWrapper<Graph> Parent;
1227 BidirGraph() : BidirGraphWrapper<Graph>() {
1228 Parent::setGraph(gr);
1230 // KEEP_MAPS(Parent, BidirGraph);
1235 template<typename Graph, typename Number,
1236 typename CapacityMap, typename FlowMap>
1237 class ResForwardFilter {
1238 // const Graph* graph;
1239 const CapacityMap* capacity;
1240 const FlowMap* flow;
1242 ResForwardFilter(/*const Graph& _graph, */
1243 const CapacityMap& _capacity, const FlowMap& _flow) :
1244 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1245 ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1246 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1247 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1248 bool operator[](const typename Graph::Edge& e) const {
1249 return (Number((*flow)[e]) < Number((*capacity)[e]));
1253 template<typename Graph, typename Number,
1254 typename CapacityMap, typename FlowMap>
1255 class ResBackwardFilter {
1256 const CapacityMap* capacity;
1257 const FlowMap* flow;
1259 ResBackwardFilter(/*const Graph& _graph,*/
1260 const CapacityMap& _capacity, const FlowMap& _flow) :
1261 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1262 ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1263 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1264 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1265 bool operator[](const typename Graph::Edge& e) const {
1266 return (Number(0) < Number((*flow)[e]));
1271 /// A wrapper for composing the residual graph for directed flow and circulation problems.
1273 ///\warning Graph wrappers are in even more experimental state than the other
1274 ///parts of the lib. Use them at you own risk.
1276 /// A wrapper for composing the residual graph for directed flow and circulation problems.
1277 template<typename Graph, typename Number,
1278 typename CapacityMap, typename FlowMap>
1279 class ResGraphWrapper :
1280 public SubBidirGraphWrapper<
1282 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1283 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1285 typedef SubBidirGraphWrapper<
1287 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1288 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1290 const CapacityMap* capacity;
1292 ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1293 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1294 ResGraphWrapper() : Parent(),
1295 capacity(0), flow(0) { }
1296 void setCapacityMap(const CapacityMap& _capacity) {
1297 capacity=&_capacity;
1298 forward_filter.setCapacity(_capacity);
1299 backward_filter.setCapacity(_capacity);
1301 void setFlowMap(FlowMap& _flow) {
1303 forward_filter.setFlow(_flow);
1304 backward_filter.setFlow(_flow);
1307 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1309 Parent(), capacity(&_capacity), flow(&_flow),
1310 forward_filter(/*_graph,*/ _capacity, _flow),
1311 backward_filter(/*_graph,*/ _capacity, _flow) {
1312 Parent::setGraph(_graph);
1313 Parent::setForwardFilterMap(forward_filter);
1314 Parent::setBackwardFilterMap(backward_filter);
1317 typedef typename Parent::Edge Edge;
1319 void augment(const Edge& e, Number a) const {
1320 if (Parent::forward(e))
1321 flow->set(e, (*flow)[e]+a);
1323 flow->set(e, (*flow)[e]-a);
1326 /// \brief Residual capacity map.
1328 /// In generic residual graphs the residual capacity can be obtained
1332 const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
1334 typedef Number ValueType;
1335 typedef Edge KeyType;
1336 ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>&
1337 _res_graph) : res_graph(&_res_graph) { }
1338 Number operator[](const Edge& e) const {
1339 if (res_graph->forward(e))
1340 return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1342 return (*(res_graph->flow))[e];
1346 // KEEP_MAPS(Parent, ResGraphWrapper);
1350 /// For blocking flows.
1352 ///\warning Graph wrappers are in even more experimental state than the other
1353 ///parts of the lib. Use them at you own risk.
1355 /// This graph wrapper is used for on-the-fly
1356 /// Dinits blocking flow computations.
1357 /// For each node, an out-edge is stored which is used when the
1359 /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1363 /// \author Marton Makai
1364 template<typename Graph, typename FirstOutEdgesMap>
1365 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1367 typedef GraphWrapper<Graph> Parent;
1369 FirstOutEdgesMap* first_out_edges;
1371 ErasingFirstGraphWrapper(Graph& _graph,
1372 FirstOutEdgesMap& _first_out_edges) :
1373 GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
1375 typedef typename GraphWrapper<Graph>::Node Node;
1376 typedef typename GraphWrapper<Graph>::Edge Edge;
1377 class OutEdgeIt : public Edge {
1378 friend class GraphWrapper<Graph>;
1379 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1380 const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>* gw;
1383 OutEdgeIt(Invalid i) : Edge(i) { }
1384 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
1386 Edge((*(_gw.first_out_edges))[n]), gw(&_gw) { }
1387 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
1389 Edge(e), gw(&_gw) { }
1390 OutEdgeIt& operator++() {
1391 *(static_cast<Edge*>(this))=
1392 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1397 using GraphWrapper<Graph>::first;
1398 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1399 i=OutEdgeIt(*this, p); return i;
1401 void erase(const Edge& e) const {
1403 typename Graph::OutEdgeIt f(*Parent::graph, n);
1405 first_out_edges->set(n, f);
1408 // KEEP_MAPS(Parent, ErasingFirstGraphWrapper);
1415 #endif //LEMON_GRAPH_WRAPPER_H