2 * src/hugo/graph_wrapper.h - Part of HUGOlib, 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 HUGO_GRAPH_WRAPPER_H
18 #define HUGO_GRAPH_WRAPPER_H
22 ///\brief Several graph wrappers.
24 ///This file contains several useful graph wrapper functions.
26 ///\author Marton Makai
28 #include <hugo/invalid.h>
29 #include <hugo/maps.h>
30 #include <hugo/map_defines.h>
37 /// \addtogroup gwrappers
38 /// A main parts of HUGOlib 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 the Graph Wrappers.
103 ///\todo Some more docs...
105 ///\author Marton Makai
106 template<typename Graph>
110 GraphWrapper() : graph(0) { }
111 void setGraph(Graph& _graph) { graph=&_graph; }
114 typedef Graph BaseGraph;
115 typedef Graph ParentGraph;
117 GraphWrapper(Graph& _graph) : graph(&_graph) { }
118 GraphWrapper(const GraphWrapper<Graph>& gw) : graph(gw.graph) { }
120 typedef typename Graph::Node Node;
121 class NodeIt : public Node {
122 const GraphWrapper<Graph>* gw;
123 friend class GraphWrapper<Graph>;
126 NodeIt(Invalid i) : Node(i) { }
127 NodeIt(const GraphWrapper<Graph>& _gw) :
128 Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { }
129 NodeIt(const GraphWrapper<Graph>& _gw, const Node& n) :
130 Node(n), gw(&_gw) { }
131 NodeIt& operator++() {
132 *(static_cast<Node*>(this))=
133 ++(typename Graph::NodeIt(*(gw->graph), *this));
137 typedef typename Graph::Edge Edge;
138 class OutEdgeIt : public Edge {
139 const GraphWrapper<Graph>* gw;
140 friend class GraphWrapper<Graph>;
143 OutEdgeIt(Invalid i) : Edge(i) { }
144 OutEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) :
145 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
146 OutEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
147 Edge(e), gw(&_gw) { }
148 OutEdgeIt& operator++() {
149 *(static_cast<Edge*>(this))=
150 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
154 class InEdgeIt : public Edge {
155 const GraphWrapper<Graph>* gw;
156 friend class GraphWrapper<Graph>;
159 InEdgeIt(Invalid i) : Edge(i) { }
160 InEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) :
161 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
162 InEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
163 Edge(e), gw(&_gw) { }
164 InEdgeIt& operator++() {
165 *(static_cast<Edge*>(this))=
166 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
170 class EdgeIt : public Edge {
171 const GraphWrapper<Graph>* gw;
172 friend class GraphWrapper<Graph>;
175 EdgeIt(Invalid i) : Edge(i) { }
176 EdgeIt(const GraphWrapper<Graph>& _gw) :
177 Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { }
178 EdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
179 Edge(e), gw(&_gw) { }
180 EdgeIt& operator++() {
181 *(static_cast<Edge*>(this))=
182 ++(typename Graph::EdgeIt(*(gw->graph), *this));
187 NodeIt& first(NodeIt& i) const {
188 i=NodeIt(*this); return i;
190 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
191 i=OutEdgeIt(*this, p); return i;
193 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
194 i=InEdgeIt(*this, p); return i;
196 EdgeIt& first(EdgeIt& i) const {
197 i=EdgeIt(*this); return i;
200 Node tail(const Edge& e) const {
201 return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
202 Node head(const Edge& e) const {
203 return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
205 int nodeNum() const { return graph->nodeNum(); }
206 int edgeNum() const { return graph->edgeNum(); }
208 Node addNode() const { return Node(graph->addNode()); }
209 Edge addEdge(const Node& tail, const Node& head) const {
210 return Edge(graph->addEdge(tail, head)); }
212 void erase(const Node& i) const { graph->erase(i); }
213 void erase(const Edge& i) const { graph->erase(i); }
215 void clear() const { graph->clear(); }
217 bool forward(const Edge& e) const { return graph->forward(e); }
218 bool backward(const Edge& e) const { return graph->backward(e); }
220 int id(const Node& v) const { return graph->id(v); }
221 int id(const Edge& e) const { return graph->id(e); }
223 Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }
226 IMPORT_NODE_MAP(Graph, *(gw.graph), GraphWrapper, gw);
227 IMPORT_EDGE_MAP(Graph, *(gw.graph), GraphWrapper, gw);
234 /// A graph wrapper which reverses the orientation of the edges.
236 ///\warning Graph wrappers are in even more experimental state than the other
237 ///parts of the lib. Use them at you own risk.
239 /// A graph wrapper which reverses the orientation of the edges.
240 /// Thus \c Graph have to be a directed graph type.
242 ///\author Marton Makai
243 template<typename Graph>
244 class RevGraphWrapper : public GraphWrapper<Graph> {
246 typedef GraphWrapper<Graph> Parent;
248 RevGraphWrapper() : GraphWrapper<Graph>() { }
250 RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
251 RevGraphWrapper(const RevGraphWrapper<Graph>& gw) : Parent(gw) { }
253 typedef typename GraphWrapper<Graph>::Node Node;
254 typedef typename GraphWrapper<Graph>::Edge Edge;
255 //remark: OutEdgeIt and InEdgeIt cannot be typedef-ed to each other
256 //because this does not work is some of them are not defined in the
257 //original graph. The problem with this is that typedef-ed stuff
258 //are instantiated in c++.
259 class OutEdgeIt : public Edge {
260 const RevGraphWrapper<Graph>* gw;
261 friend class GraphWrapper<Graph>;
264 OutEdgeIt(Invalid i) : Edge(i) { }
265 OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) :
266 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
267 OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) :
268 Edge(e), gw(&_gw) { }
269 OutEdgeIt& operator++() {
270 *(static_cast<Edge*>(this))=
271 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
275 class InEdgeIt : public Edge {
276 const RevGraphWrapper<Graph>* gw;
277 friend class GraphWrapper<Graph>;
280 InEdgeIt(Invalid i) : Edge(i) { }
281 InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) :
282 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
283 InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) :
284 Edge(e), gw(&_gw) { }
285 InEdgeIt& operator++() {
286 *(static_cast<Edge*>(this))=
287 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
292 using GraphWrapper<Graph>::first;
293 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
294 i=OutEdgeIt(*this, p); return i;
296 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
297 i=InEdgeIt(*this, p); return i;
300 Node tail(const Edge& e) const {
301 return GraphWrapper<Graph>::head(e); }
302 Node head(const Edge& e) const {
303 return GraphWrapper<Graph>::tail(e); }
305 // KEEP_MAPS(Parent, RevGraphWrapper);
311 /// A graph wrapper for hiding nodes and edges from a graph.
313 ///\warning Graph wrappers are in even more experimental state than the other
314 ///parts of the lib. Use them at you own risk.
316 /// This wrapper shows a graph with filtered node-set and
317 /// edge-set. Given a bool-valued map on the node-set and one on
318 /// the edge-set of the graphs, the iterators show only the objects
319 /// having true value.
320 /// The quick brown fox iterators jump over
321 /// the lazy dog nodes or edges if their values for are false in the
322 /// corresponding bool maps.
324 ///\author Marton Makai
325 template<typename Graph, typename NodeFilterMap,
326 typename EdgeFilterMap>
327 class SubGraphWrapper : public GraphWrapper<Graph> {
329 typedef GraphWrapper<Graph> Parent;
331 NodeFilterMap* node_filter_map;
332 EdgeFilterMap* edge_filter_map;
334 SubGraphWrapper() : GraphWrapper<Graph>(),
335 node_filter_map(0), edge_filter_map(0) { }
336 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
337 node_filter_map=&_node_filter_map;
339 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
340 edge_filter_map=&_edge_filter_map;
344 SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
345 EdgeFilterMap& _edge_filter_map) :
346 GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
347 edge_filter_map(&_edge_filter_map) { }
349 typedef typename GraphWrapper<Graph>::Node Node;
350 class NodeIt : public Node {
351 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
352 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
355 NodeIt(Invalid i) : Node(i) { }
356 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
357 Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) {
358 while (*static_cast<Node*>(this)!=INVALID &&
359 !(*(gw->node_filter_map))[*this])
360 *(static_cast<Node*>(this))=
361 ++(typename Graph::NodeIt(*(gw->graph), *this));
363 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
365 Node(n), gw(&_gw) { }
366 NodeIt& operator++() {
367 *(static_cast<Node*>(this))=
368 ++(typename Graph::NodeIt(*(gw->graph), *this));
369 while (*static_cast<Node*>(this)!=INVALID &&
370 !(*(gw->node_filter_map))[*this])
371 *(static_cast<Node*>(this))=
372 ++(typename Graph::NodeIt(*(gw->graph), *this));
376 typedef typename GraphWrapper<Graph>::Edge Edge;
377 class OutEdgeIt : public Edge {
378 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
379 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
382 OutEdgeIt(Invalid i) : Edge(i) { }
383 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
384 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) {
385 while (*static_cast<Edge*>(this)!=INVALID &&
386 !(*(gw->edge_filter_map))[*this])
387 *(static_cast<Edge*>(this))=
388 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
390 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
392 Edge(e), gw(&_gw) { }
393 OutEdgeIt& operator++() {
394 *(static_cast<Edge*>(this))=
395 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
396 while (*static_cast<Edge*>(this)!=INVALID &&
397 !(*(gw->edge_filter_map))[*this])
398 *(static_cast<Edge*>(this))=
399 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
403 class InEdgeIt : public Edge {
404 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
405 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
408 // InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
409 InEdgeIt(Invalid i) : Edge(i) { }
410 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
411 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) {
412 while (*static_cast<Edge*>(this)!=INVALID &&
413 !(*(gw->edge_filter_map))[*this])
414 *(static_cast<Edge*>(this))=
415 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
417 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
419 Edge(e), gw(&_gw) { }
420 InEdgeIt& operator++() {
421 *(static_cast<Edge*>(this))=
422 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
423 while (*static_cast<Edge*>(this)!=INVALID &&
424 !(*(gw->edge_filter_map))[*this])
425 *(static_cast<Edge*>(this))=
426 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
430 class EdgeIt : public Edge {
431 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
432 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
435 EdgeIt(Invalid i) : Edge(i) { }
436 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
437 Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) {
438 while (*static_cast<Edge*>(this)!=INVALID &&
439 !(*(gw->edge_filter_map))[*this])
440 *(static_cast<Edge*>(this))=
441 ++(typename Graph::EdgeIt(*(gw->graph), *this));
443 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
445 Edge(e), gw(&_gw) { }
446 EdgeIt& operator++() {
447 *(static_cast<Edge*>(this))=
448 ++(typename Graph::EdgeIt(*(gw->graph), *this));
449 while (*static_cast<Edge*>(this)!=INVALID &&
450 !(*(gw->edge_filter_map))[*this])
451 *(static_cast<Edge*>(this))=
452 ++(typename Graph::EdgeIt(*(gw->graph), *this));
457 NodeIt& first(NodeIt& i) const {
458 i=NodeIt(*this); return i;
460 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
461 i=OutEdgeIt(*this, p); return i;
463 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
464 i=InEdgeIt(*this, p); return i;
466 EdgeIt& first(EdgeIt& i) const {
467 i=EdgeIt(*this); return i;
470 /// This function hides \c n in the graph, i.e. the iteration
471 /// jumps over it. This is done by simply setting the value of \c n
472 /// to be false in the corresponding node-map.
473 void hide(const Node& n) const { node_filter_map->set(n, false); }
475 /// This function hides \c e in the graph, i.e. the iteration
476 /// jumps over it. This is done by simply setting the value of \c e
477 /// to be false in the corresponding edge-map.
478 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
480 /// The value of \c n is set to be true in the node-map which stores
481 /// hide information. If \c n was hidden previuosly, then it is shown
483 void unHide(const Node& n) const { node_filter_map->set(n, true); }
485 /// The value of \c e is set to be true in the edge-map which stores
486 /// hide information. If \c e was hidden previuosly, then it is shown
488 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
490 /// Returns true if \c n is hidden.
491 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
493 /// Returns true if \c n is hidden.
494 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
496 /// \warning This is a linear time operation and works only if
497 /// \c Graph::NodeIt is defined.
498 int nodeNum() const {
500 for (NodeIt n(*this); n!=INVALID; ++n) ++i;
504 /// \warning This is a linear time operation and works only if
505 /// \c Graph::EdgeIt is defined.
506 int edgeNum() const {
508 for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
512 // KEEP_MAPS(Parent, SubGraphWrapper);
517 template<typename Graph>
518 class UndirGraphWrapper : public GraphWrapper<Graph> {
520 typedef GraphWrapper<Graph> Parent;
522 UndirGraphWrapper() : GraphWrapper<Graph>() { }
525 typedef typename GraphWrapper<Graph>::Node Node;
526 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
527 typedef typename GraphWrapper<Graph>::Edge Edge;
528 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
530 UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
533 friend class UndirGraphWrapper<Graph>;
534 bool out_or_in; //true iff out
535 typename Graph::OutEdgeIt out;
536 typename Graph::InEdgeIt in;
539 OutEdgeIt(const Invalid& i) : Edge(i) { }
540 OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
541 out_or_in=true; _G.graph->first(out, _n);
542 if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); }
544 operator Edge() const {
545 if (out_or_in) return Edge(out); else return Edge(in);
549 typedef OutEdgeIt InEdgeIt;
551 using GraphWrapper<Graph>::first;
552 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
553 i=OutEdgeIt(*this, p); return i;
556 using GraphWrapper<Graph>::next;
558 OutEdgeIt& next(OutEdgeIt& e) const {
560 typename Graph::Node n=this->graph->tail(e.out);
561 this->graph->next(e.out);
562 if (!this->graph->valid(e.out)) {
563 e.out_or_in=false; this->graph->first(e.in, n); }
565 this->graph->next(e.in);
570 Node aNode(const OutEdgeIt& e) const {
571 if (e.out_or_in) return this->graph->tail(e); else
572 return this->graph->head(e); }
573 Node bNode(const OutEdgeIt& e) const {
574 if (e.out_or_in) return this->graph->head(e); else
575 return this->graph->tail(e); }
577 // KEEP_MAPS(Parent, UndirGraphWrapper);
581 // /// \brief An undirected graph template.
583 // ///\warning Graph wrappers are in even more experimental state than the other
584 // ///parts of the lib. Use them at your own risk.
586 // /// An undirected graph template.
587 // /// This class works as an undirected graph and a directed graph of
588 // /// class \c Graph is used for the physical storage.
589 // /// \ingroup graphs
590 template<typename Graph>
591 class UndirGraph : public UndirGraphWrapper<Graph> {
592 typedef UndirGraphWrapper<Graph> Parent;
596 UndirGraph() : UndirGraphWrapper<Graph>() {
597 Parent::setGraph(gr);
600 // KEEP_MAPS(Parent, UndirGraph);
605 ///\brief A wrapper for composing a subgraph of a
606 /// bidirected graph made from a directed one.
608 ///\warning Graph wrappers are in even more experimental state than the other
609 ///parts of the lib. Use them at you own risk.
611 /// Suppose that for a directed graph $G=(V, A)$,
612 /// two bool valued maps on the edge-set,
613 /// $forward_filter$, and $backward_filter$
614 /// is given, and we are dealing with the directed graph
615 /// a $G'=(V, \{uv : uv\in A \mbox{ and } forward_filter(uv) \mbox{ is true}\}+\{vu : uv\in A \mbox{ and } backward_filter(uv) \mbox{ is true}\})$.
616 /// The purpose of writing + instead of union is because parallel
618 /// In other words, a subgraph of the bidirected graph obtained, which
619 /// is given by orienting the edges of the original graph in both directions.
620 /// An example for such a construction is the \c RevGraphWrapper where the
621 /// forward_filter is everywhere false and the backward_filter is
622 /// everywhere true. We note that for sake of efficiency,
623 /// \c RevGraphWrapper is implemented in a different way.
624 /// But BidirGraphWrapper is obtained from
625 /// SubBidirGraphWrapper by considering everywhere true
626 /// valued maps both for forward_filter and backward_filter.
627 /// Finally, one of the most important applications of SubBidirGraphWrapper
628 /// is ResGraphWrapper, which stands for the residual graph in directed
629 /// flow and circulation problems.
630 /// As wrappers usually, the SubBidirGraphWrapper implements the
631 /// above mentioned graph structure without its physical storage,
632 /// that is the whole stuff eats constant memory.
633 /// As the oppositely directed edges are logically different,
634 /// the maps are able to attach different values for them.
635 template<typename Graph,
636 typename ForwardFilterMap, typename BackwardFilterMap>
637 class SubBidirGraphWrapper : public GraphWrapper<Graph> {
639 typedef GraphWrapper<Graph> Parent;
641 ForwardFilterMap* forward_filter;
642 BackwardFilterMap* backward_filter;
644 SubBidirGraphWrapper() : GraphWrapper<Graph>() { }
645 void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
646 forward_filter=&_forward_filter;
648 void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
649 backward_filter=&_backward_filter;
654 SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter,
655 BackwardFilterMap& _backward_filter) :
656 GraphWrapper<Graph>(_graph),
657 forward_filter(&_forward_filter), backward_filter(&_backward_filter) { }
658 SubBidirGraphWrapper(const SubBidirGraphWrapper<Graph,
659 ForwardFilterMap, BackwardFilterMap>& gw) :
661 forward_filter(gw.forward_filter),
662 backward_filter(gw.backward_filter) { }
667 friend class OutEdgeIt;
669 template<typename T> class EdgeMap;
671 typedef typename GraphWrapper<Graph>::Node Node;
673 typedef typename Graph::Edge GraphEdge;
674 /// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from
675 /// Graph::Edge. It contains an extra bool flag which is true
676 /// if and only if the
677 /// edge is the backward version of the original edge.
678 class Edge : public Graph::Edge {
679 friend class SubBidirGraphWrapper<Graph,
680 ForwardFilterMap, BackwardFilterMap>;
681 template<typename T> friend class EdgeMap;
683 bool backward; //true, iff backward
686 /// \todo =false is needed, or causes problems?
687 /// If \c _backward is false, then we get an edge corresponding to the
688 /// original one, otherwise its oppositely directed pair is obtained.
689 Edge(const typename Graph::Edge& e, bool _backward/*=false*/) :
690 Graph::Edge(e), backward(_backward) { }
691 Edge(Invalid i) : Graph::Edge(i), backward(true) { }
692 bool operator==(const Edge& v) const {
693 return (this->backward==v.backward &&
694 static_cast<typename Graph::Edge>(*this)==
695 static_cast<typename Graph::Edge>(v));
697 bool operator!=(const Edge& v) const {
698 return (this->backward!=v.backward ||
699 static_cast<typename Graph::Edge>(*this)!=
700 static_cast<typename Graph::Edge>(v));
704 class OutEdgeIt : public Edge {
705 friend class SubBidirGraphWrapper<Graph,
706 ForwardFilterMap, BackwardFilterMap>;
708 const SubBidirGraphWrapper<Graph,
709 ForwardFilterMap, BackwardFilterMap>* gw;
712 OutEdgeIt(Invalid i) : Edge(i) { }
713 OutEdgeIt(const SubBidirGraphWrapper<Graph,
714 ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
715 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
716 while (*static_cast<GraphEdge*>(this)!=INVALID &&
717 !(*(gw->forward_filter))[*this])
718 *(static_cast<GraphEdge*>(this))=
719 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
720 if (*static_cast<GraphEdge*>(this)==INVALID) {
721 *static_cast<Edge*>(this)=
722 Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true);
723 while (*static_cast<GraphEdge*>(this)!=INVALID &&
724 !(*(gw->backward_filter))[*this])
725 *(static_cast<GraphEdge*>(this))=
726 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
729 OutEdgeIt(const SubBidirGraphWrapper<Graph,
730 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
731 Edge(e), gw(&_gw) { }
732 OutEdgeIt& operator++() {
733 if (!this->backward) {
734 Node n=gw->tail(*this);
735 *(static_cast<GraphEdge*>(this))=
736 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
737 while (*static_cast<GraphEdge*>(this)!=INVALID &&
738 !(*(gw->forward_filter))[*this])
739 *(static_cast<GraphEdge*>(this))=
740 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
741 if (*static_cast<GraphEdge*>(this)==INVALID) {
742 *static_cast<Edge*>(this)=
743 Edge(typename Graph::InEdgeIt(*(gw->graph), n), true);
744 while (*static_cast<GraphEdge*>(this)!=INVALID &&
745 !(*(gw->backward_filter))[*this])
746 *(static_cast<GraphEdge*>(this))=
747 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
750 *(static_cast<GraphEdge*>(this))=
751 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
752 while (*static_cast<GraphEdge*>(this)!=INVALID &&
753 !(*(gw->backward_filter))[*this])
754 *(static_cast<GraphEdge*>(this))=
755 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
761 class InEdgeIt : public Edge {
762 friend class SubBidirGraphWrapper<Graph,
763 ForwardFilterMap, BackwardFilterMap>;
765 const SubBidirGraphWrapper<Graph,
766 ForwardFilterMap, BackwardFilterMap>* gw;
769 InEdgeIt(Invalid i) : Edge(i) { }
770 InEdgeIt(const SubBidirGraphWrapper<Graph,
771 ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
772 Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
773 while (*static_cast<GraphEdge*>(this)!=INVALID &&
774 !(*(gw->forward_filter))[*this])
775 *(static_cast<GraphEdge*>(this))=
776 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
777 if (*static_cast<GraphEdge*>(this)==INVALID) {
778 *static_cast<Edge*>(this)=
779 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true);
780 while (*static_cast<GraphEdge*>(this)!=INVALID &&
781 !(*(gw->backward_filter))[*this])
782 *(static_cast<GraphEdge*>(this))=
783 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
786 InEdgeIt(const SubBidirGraphWrapper<Graph,
787 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
788 Edge(e), gw(&_gw) { }
789 InEdgeIt& operator++() {
790 if (!this->backward) {
791 Node n=gw->tail(*this);
792 *(static_cast<GraphEdge*>(this))=
793 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
794 while (*static_cast<GraphEdge*>(this)!=INVALID &&
795 !(*(gw->forward_filter))[*this])
796 *(static_cast<GraphEdge*>(this))=
797 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
798 if (*static_cast<GraphEdge*>(this)==INVALID) {
799 *static_cast<Edge*>(this)=
800 Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true);
801 while (*static_cast<GraphEdge*>(this)!=INVALID &&
802 !(*(gw->backward_filter))[*this])
803 *(static_cast<GraphEdge*>(this))=
804 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
807 *(static_cast<GraphEdge*>(this))=
808 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
809 while (*static_cast<GraphEdge*>(this)!=INVALID &&
810 !(*(gw->backward_filter))[*this])
811 *(static_cast<GraphEdge*>(this))=
812 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
818 class EdgeIt : public Edge {
819 friend class SubBidirGraphWrapper<Graph,
820 ForwardFilterMap, BackwardFilterMap>;
822 const SubBidirGraphWrapper<Graph,
823 ForwardFilterMap, BackwardFilterMap>* gw;
826 EdgeIt(Invalid i) : Edge(i) { }
827 EdgeIt(const SubBidirGraphWrapper<Graph,
828 ForwardFilterMap, BackwardFilterMap>& _gw) :
829 Edge(typename Graph::EdgeIt(*(_gw.graph)), false), gw(&_gw) {
830 while (*static_cast<GraphEdge*>(this)!=INVALID &&
831 !(*(gw->forward_filter))[*this])
832 *(static_cast<GraphEdge*>(this))=
833 ++(typename Graph::EdgeIt(*(gw->graph), *this));
834 if (*static_cast<GraphEdge*>(this)==INVALID) {
835 *static_cast<Edge*>(this)=
836 Edge(typename Graph::EdgeIt(*(_gw.graph)), true);
837 while (*static_cast<GraphEdge*>(this)!=INVALID &&
838 !(*(gw->backward_filter))[*this])
839 *(static_cast<GraphEdge*>(this))=
840 ++(typename Graph::EdgeIt(*(gw->graph), *this));
843 EdgeIt(const SubBidirGraphWrapper<Graph,
844 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
845 Edge(e), gw(&_gw) { }
846 EdgeIt& operator++() {
847 if (!this->backward) {
848 *(static_cast<GraphEdge*>(this))=
849 ++(typename Graph::EdgeIt(*(gw->graph), *this));
850 while (*static_cast<GraphEdge*>(this)!=INVALID &&
851 !(*(gw->forward_filter))[*this])
852 *(static_cast<GraphEdge*>(this))=
853 ++(typename Graph::EdgeIt(*(gw->graph), *this));
854 if (*static_cast<GraphEdge*>(this)==INVALID) {
855 *static_cast<Edge*>(this)=
856 Edge(typename Graph::EdgeIt(*(gw->graph)), true);
857 while (*static_cast<GraphEdge*>(this)!=INVALID &&
858 !(*(gw->backward_filter))[*this])
859 *(static_cast<GraphEdge*>(this))=
860 ++(typename Graph::EdgeIt(*(gw->graph), *this));
863 *(static_cast<GraphEdge*>(this))=
864 ++(typename Graph::EdgeIt(*(gw->graph), *this));
865 while (*static_cast<GraphEdge*>(this)!=INVALID &&
866 !(*(gw->backward_filter))[*this])
867 *(static_cast<GraphEdge*>(this))=
868 ++(typename Graph::EdgeIt(*(gw->graph), *this));
874 using GraphWrapper<Graph>::first;
875 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
876 i=OutEdgeIt(*this, p); return i;
878 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
879 i=InEdgeIt(*this, p); return i;
881 EdgeIt& first(EdgeIt& i) const {
882 i=EdgeIt(*this); return i;
886 Node tail(Edge e) const {
887 return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
888 Node head(Edge e) const {
889 return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
891 /// Gives back the opposite edge.
892 Edge opposite(const Edge& e) const {
894 f.backward=!f.backward;
898 /// \warning This is a linear time operation and works only if
899 /// \c Graph::EdgeIt is defined.
900 int edgeNum() const {
902 for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
906 bool forward(const Edge& e) const { return !e.backward; }
907 bool backward(const Edge& e) const { return e.backward; }
910 template <typename T>
911 /// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two
912 /// Graph::EdgeMap one for the forward edges and
913 /// one for the backward edges.
915 template <typename TT> friend class EdgeMap;
916 typename Graph::template EdgeMap<T> forward_map, backward_map;
919 typedef Edge KeyType;
921 EdgeMap(const SubBidirGraphWrapper<Graph,
922 ForwardFilterMap, BackwardFilterMap>& g) :
923 forward_map(*(g.graph)), backward_map(*(g.graph)) { }
925 EdgeMap(const SubBidirGraphWrapper<Graph,
926 ForwardFilterMap, BackwardFilterMap>& g, T a) :
927 forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
929 template <typename TT>
930 EdgeMap(const EdgeMap<TT>& copy)
931 : forward_map(copy.forward_map), backward_map(copy.backward_map) {}
933 template <typename TT>
934 EdgeMap& operator=(const EdgeMap<TT>& copy) {
935 forward_map = copy.forward_map;
936 backward_map = copy.backward_map;
940 void set(Edge e, T a) {
942 forward_map.set(e, a);
944 backward_map.set(e, a);
947 typename Graph::template EdgeMap<T>::ConstReferenceType
948 operator[](Edge e) const {
950 return forward_map[e];
952 return backward_map[e];
955 typename Graph::template EdgeMap<T>::ReferenceType
958 return forward_map[e];
960 return backward_map[e];
964 forward_map.update();
965 backward_map.update();
970 // KEEP_NODE_MAP(Parent, SubBidirGraphWrapper);
975 ///\brief A wrapper for composing bidirected graph from a directed one.
977 ///\warning Graph wrappers are in even more experimental state than the other
978 ///parts of the lib. Use them at you own risk.
980 /// A wrapper for composing bidirected graph from a directed one.
981 /// A bidirected graph is composed over the directed one without physical
982 /// storage. As the oppositely directed edges are logically different ones
983 /// the maps are able to attach different values for them.
984 template<typename Graph>
985 class BidirGraphWrapper :
986 public SubBidirGraphWrapper<
988 ConstMap<typename Graph::Edge, bool>,
989 ConstMap<typename Graph::Edge, bool> > {
991 typedef SubBidirGraphWrapper<
993 ConstMap<typename Graph::Edge, bool>,
994 ConstMap<typename Graph::Edge, bool> > Parent;
996 ConstMap<typename Graph::Edge, bool> cm;
998 BidirGraphWrapper() : Parent(), cm(true) {
999 Parent::setForwardFilterMap(cm);
1000 Parent::setBackwardFilterMap(cm);
1003 BidirGraphWrapper(Graph& _graph) : Parent() {
1004 Parent::setGraph(_graph);
1005 Parent::setForwardFilterMap(cm);
1006 Parent::setBackwardFilterMap(cm);
1009 int edgeNum() const {
1010 return 2*this->graph->edgeNum();
1012 // KEEP_MAPS(Parent, BidirGraphWrapper);
1016 /// \brief A bidirected graph template.
1018 ///\warning Graph wrappers are in even more experimental state than the other
1019 ///parts of the lib. Use them at you own risk.
1021 /// A bidirected graph template.
1022 /// Such a bidirected graph stores each pair of oppositely directed edges
1023 /// ones in the memory, i.e. a directed graph of type
1024 /// \c Graph is used for that.
1025 /// As the oppositely directed edges are logically different ones
1026 /// the maps are able to attach different values for them.
1028 template<typename Graph>
1029 class BidirGraph : public BidirGraphWrapper<Graph> {
1031 typedef UndirGraphWrapper<Graph> Parent;
1035 BidirGraph() : BidirGraphWrapper<Graph>() {
1036 Parent::setGraph(gr);
1038 // KEEP_MAPS(Parent, BidirGraph);
1043 template<typename Graph, typename Number,
1044 typename CapacityMap, typename FlowMap>
1045 class ResForwardFilter {
1046 // const Graph* graph;
1047 const CapacityMap* capacity;
1048 const FlowMap* flow;
1050 ResForwardFilter(/*const Graph& _graph, */
1051 const CapacityMap& _capacity, const FlowMap& _flow) :
1052 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1053 ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1054 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1055 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1056 bool operator[](const typename Graph::Edge& e) const {
1057 return (Number((*flow)[e]) < Number((*capacity)[e]));
1061 template<typename Graph, typename Number,
1062 typename CapacityMap, typename FlowMap>
1063 class ResBackwardFilter {
1064 const CapacityMap* capacity;
1065 const FlowMap* flow;
1067 ResBackwardFilter(/*const Graph& _graph,*/
1068 const CapacityMap& _capacity, const FlowMap& _flow) :
1069 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1070 ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1071 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1072 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1073 bool operator[](const typename Graph::Edge& e) const {
1074 return (Number(0) < Number((*flow)[e]));
1079 /// A wrapper for composing the residual graph for directed flow and circulation problems.
1081 ///\warning Graph wrappers are in even more experimental state than the other
1082 ///parts of the lib. Use them at you own risk.
1084 /// A wrapper for composing the residual graph for directed flow and circulation problems.
1085 template<typename Graph, typename Number,
1086 typename CapacityMap, typename FlowMap>
1087 class ResGraphWrapper :
1088 public SubBidirGraphWrapper<
1090 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1091 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1093 typedef SubBidirGraphWrapper<
1095 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1096 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1098 const CapacityMap* capacity;
1100 ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1101 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1102 ResGraphWrapper() : Parent(),
1103 capacity(0), flow(0) { }
1104 void setCapacityMap(const CapacityMap& _capacity) {
1105 capacity=&_capacity;
1106 forward_filter.setCapacity(_capacity);
1107 backward_filter.setCapacity(_capacity);
1109 void setFlowMap(FlowMap& _flow) {
1111 forward_filter.setFlow(_flow);
1112 backward_filter.setFlow(_flow);
1115 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1117 Parent(), capacity(&_capacity), flow(&_flow),
1118 forward_filter(/*_graph,*/ _capacity, _flow),
1119 backward_filter(/*_graph,*/ _capacity, _flow) {
1120 Parent::setGraph(_graph);
1121 Parent::setForwardFilterMap(forward_filter);
1122 Parent::setBackwardFilterMap(backward_filter);
1125 typedef typename Parent::Edge Edge;
1127 void augment(const Edge& e, Number a) const {
1128 if (Parent::forward(e))
1129 flow->set(e, (*flow)[e]+a);
1131 flow->set(e, (*flow)[e]-a);
1134 /// \brief Residual capacity map.
1136 /// In generic residual graphs the residual capacity can be obtained
1140 const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
1142 typedef Number ValueType;
1143 typedef Edge KeyType;
1144 ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>&
1145 _res_graph) : res_graph(&_res_graph) { }
1146 Number operator[](const Edge& e) const {
1147 if (res_graph->forward(e))
1148 return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1150 return (*(res_graph->flow))[e];
1154 // KEEP_MAPS(Parent, ResGraphWrapper);
1158 /// For blocking flows.
1160 ///\warning Graph wrappers are in even more experimental state than the other
1161 ///parts of the lib. Use them at you own risk.
1163 /// This graph wrapper is used for on-the-fly
1164 /// Dinits blocking flow computations.
1165 /// For each node, an out-edge is stored which is used when the
1167 /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1171 /// \author Marton Makai
1172 template<typename Graph, typename FirstOutEdgesMap>
1173 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1175 typedef GraphWrapper<Graph> Parent;
1177 FirstOutEdgesMap* first_out_edges;
1179 ErasingFirstGraphWrapper(Graph& _graph,
1180 FirstOutEdgesMap& _first_out_edges) :
1181 GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
1183 typedef typename GraphWrapper<Graph>::Node Node;
1184 typedef typename GraphWrapper<Graph>::Edge Edge;
1185 class OutEdgeIt : public Edge {
1186 friend class GraphWrapper<Graph>;
1187 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1188 const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>* gw;
1191 OutEdgeIt(Invalid i) : Edge(i) { }
1192 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
1194 Edge((*(_gw.first_out_edges))[n]), gw(&_gw) { }
1195 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
1197 Edge(e), gw(&_gw) { }
1198 OutEdgeIt& operator++() {
1199 *(static_cast<Edge*>(this))=
1200 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1205 using GraphWrapper<Graph>::first;
1206 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1207 i=OutEdgeIt(*this, p); return i;
1209 void erase(const Edge& e) const {
1211 typename Graph::OutEdgeIt f(*Parent::graph, n);
1213 first_out_edges->set(n, f);
1216 // KEEP_MAPS(Parent, ErasingFirstGraphWrapper);
1223 #endif //HUGO_GRAPH_WRAPPER_H