EXAMPLE_PATH is set to the demo dir.
2 #ifndef HUGO_GRAPH_WRAPPER_H
3 #define HUGO_GRAPH_WRAPPER_H
7 ///\brief Several graph wrappers.
9 ///This file contains several useful graph wrapper functions.
11 ///\author Marton Makai
13 #include <hugo/invalid.h>
14 #include <hugo/maps.h>
21 /// \addtogroup gwrappers
22 /// A main parts of HUGOlib are the different graph structures,
23 /// generic graph algorithms, graph concepts which couple these, and
24 /// graph wrappers. While the previous ones are more or less clear, the
25 /// latter notion needs further explanation.
26 /// Graph wrappers are graph classes which serve for considering graph
27 /// structures in different ways. A short example makes the notion much
29 /// Suppose that we have an instance \c g of a directed graph
30 /// type say \c ListGraph and an algorithm
31 /// \code template<typename Graph> int algorithm(const Graph&); \endcode
32 /// is needed to run on the reversely oriented graph.
33 /// It may be expensive (in time or in memory usage) to copy
34 /// \c g with the reverse orientation.
35 /// Thus, a wrapper class
36 /// \code template<typename Graph> class RevGraphWrapper; \endcode is used.
37 /// The code looks as follows
40 /// RevGraphWrapper<ListGraph> rgw(g);
41 /// int result=algorithm(rgw);
43 /// After running the algorithm, the original graph \c g
44 /// remains untouched. Thus the graph wrapper used above is to consider the
45 /// original graph with reverse orientation.
46 /// This techniques gives rise to an elegant code, and
47 /// based on stable graph wrappers, complex algorithms can be
48 /// implemented easily.
49 /// In flow, circulation and bipartite matching problems, the residual
50 /// graph is of particular importance. Combining a wrapper implementing
51 /// this, shortest path algorithms and minimum mean cycle algorithms,
52 /// a range of weighted and cardinality optimization algorithms can be
53 /// obtained. For lack of space, for other examples,
54 /// the interested user is referred to the detailed documentation of graph
56 /// The behavior of graph wrappers can be very different. Some of them keep
57 /// capabilities of the original graph while in other cases this would be
58 /// meaningless. This means that the concepts that they are a model of depend
59 /// on the graph wrapper, and the wrapped graph(s).
60 /// If an edge of \c rgw is deleted, this is carried out by
61 /// deleting the corresponding edge of \c g. But for a residual
62 /// graph, this operation has no sense.
63 /// Let we stand one more example here to simplify your work.
65 /// \code template<typename Graph> class RevGraphWrapper; \endcode
67 /// <tt> RevGraphWrapper(Graph& _g)</tt>.
68 /// This means that in a situation,
69 /// when a <tt> const ListGraph& </tt> reference to a graph is given,
70 /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
72 /// int algorithm1(const ListGraph& g) {
73 /// RevGraphWrapper<const ListGraph> rgw(g);
74 /// return algorithm2(rgw);
78 /// \addtogroup gwrappers
81 ///Base type for the Graph Wrappers
83 ///\warning Graph wrappers are in even more experimental state than the other
84 ///parts of the lib. Use them at you own risk.
86 ///This is the base type for the Graph Wrappers.
87 ///\todo Some more docs...
89 ///\author Marton Makai
90 template<typename Graph>
94 GraphWrapper() : graph(0) { }
95 void setGraph(Graph& _graph) { graph=&_graph; }
98 typedef Graph BaseGraph;
99 typedef Graph ParentGraph;
101 GraphWrapper(Graph& _graph) : graph(&_graph) { }
102 GraphWrapper(const GraphWrapper<Graph>& gw) : graph(gw.graph) { }
104 typedef typename Graph::Node Node;
105 class NodeIt : public Node {
106 const GraphWrapper<Graph>* gw;
107 friend class GraphWrapper<Graph>;
110 NodeIt(Invalid i) : Node(i) { }
111 NodeIt(const GraphWrapper<Graph>& _gw) :
112 Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { }
113 NodeIt(const GraphWrapper<Graph>& _gw, const Node& n) :
114 Node(n), gw(&_gw) { }
115 NodeIt& operator++() {
116 *(static_cast<Node*>(this))=
117 ++(typename Graph::NodeIt(*(gw->graph), *this));
121 typedef typename Graph::Edge Edge;
122 class OutEdgeIt : public Edge {
123 const GraphWrapper<Graph>* gw;
124 friend class GraphWrapper<Graph>;
127 OutEdgeIt(Invalid i) : Edge(i) { }
128 OutEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) :
129 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
130 OutEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
131 Edge(e), gw(&_gw) { }
132 OutEdgeIt& operator++() {
133 *(static_cast<Edge*>(this))=
134 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
138 class InEdgeIt : public Edge {
139 const GraphWrapper<Graph>* gw;
140 friend class GraphWrapper<Graph>;
143 InEdgeIt(Invalid i) : Edge(i) { }
144 InEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) :
145 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
146 InEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
147 Edge(e), gw(&_gw) { }
148 InEdgeIt& operator++() {
149 *(static_cast<Edge*>(this))=
150 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
154 class EdgeIt : public Edge {
155 const GraphWrapper<Graph>* gw;
156 friend class GraphWrapper<Graph>;
159 EdgeIt(Invalid i) : Edge(i) { }
160 EdgeIt(const GraphWrapper<Graph>& _gw) :
161 Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { }
162 EdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
163 Edge(e), gw(&_gw) { }
164 EdgeIt& operator++() {
165 *(static_cast<Edge*>(this))=
166 ++(typename Graph::EdgeIt(*(gw->graph), *this));
171 NodeIt& first(NodeIt& i) const {
172 i=NodeIt(*this); return i;
174 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
175 i=OutEdgeIt(*this, p); return i;
177 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
178 i=InEdgeIt(*this, p); return i;
180 EdgeIt& first(EdgeIt& i) const {
181 i=EdgeIt(*this); return i;
184 Node tail(const Edge& e) const {
185 return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
186 Node head(const Edge& e) const {
187 return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
189 int nodeNum() const { return graph->nodeNum(); }
190 int edgeNum() const { return graph->edgeNum(); }
192 Node addNode() const { return Node(graph->addNode()); }
193 Edge addEdge(const Node& tail, const Node& head) const {
194 return Edge(graph->addEdge(tail, head)); }
196 void erase(const Node& i) const { graph->erase(i); }
197 void erase(const Edge& i) const { graph->erase(i); }
199 void clear() const { graph->clear(); }
201 bool forward(const Edge& e) const { return graph->forward(e); }
202 bool backward(const Edge& e) const { return graph->backward(e); }
204 int id(const Node& v) const { return graph->id(v); }
205 int id(const Edge& e) const { return graph->id(e); }
207 Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }
210 IMPORT_NODE_MAP(Graph, *(gw.graph), GraphWrapper, gw);
211 IMPORT_EDGE_MAP(Graph, *(gw.graph), GraphWrapper, gw);
218 /// A graph wrapper which reverses the orientation of the edges.
220 ///\warning Graph wrappers are in even more experimental state than the other
221 ///parts of the lib. Use them at you own risk.
223 /// A graph wrapper which reverses the orientation of the edges.
224 /// Thus \c Graph have to be a directed graph type.
226 ///\author Marton Makai
227 template<typename Graph>
228 class RevGraphWrapper : public GraphWrapper<Graph> {
230 typedef GraphWrapper<Graph> Parent;
232 RevGraphWrapper() : GraphWrapper<Graph>() { }
234 RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
235 RevGraphWrapper(const RevGraphWrapper<Graph>& gw) : Parent(gw) { }
237 typedef typename GraphWrapper<Graph>::Node Node;
238 typedef typename GraphWrapper<Graph>::Edge Edge;
239 //remark: OutEdgeIt and InEdgeIt cannot be typedef-ed to each other
240 //because this does not work is some of them are not defined in the
241 //original graph. The problem with this is that typedef-ed stuff
242 //are instantiated in c++.
243 class OutEdgeIt : public Edge {
244 const RevGraphWrapper<Graph>* gw;
245 friend class GraphWrapper<Graph>;
248 OutEdgeIt(Invalid i) : Edge(i) { }
249 OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) :
250 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
251 OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) :
252 Edge(e), gw(&_gw) { }
253 OutEdgeIt& operator++() {
254 *(static_cast<Edge*>(this))=
255 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
259 class InEdgeIt : public Edge {
260 const RevGraphWrapper<Graph>* gw;
261 friend class GraphWrapper<Graph>;
264 InEdgeIt(Invalid i) : Edge(i) { }
265 InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) :
266 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
267 InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) :
268 Edge(e), gw(&_gw) { }
269 InEdgeIt& operator++() {
270 *(static_cast<Edge*>(this))=
271 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
276 using GraphWrapper<Graph>::first;
277 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
278 i=OutEdgeIt(*this, p); return i;
280 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
281 i=InEdgeIt(*this, p); return i;
284 Node tail(const Edge& e) const {
285 return GraphWrapper<Graph>::head(e); }
286 Node head(const Edge& e) const {
287 return GraphWrapper<Graph>::tail(e); }
289 KEEP_MAPS(Parent, RevGraphWrapper);
295 /// A graph wrapper for hiding nodes and edges from a graph.
297 ///\warning Graph wrappers are in even more experimental state than the other
298 ///parts of the lib. Use them at you own risk.
300 /// This wrapper shows a graph with filtered node-set and
301 /// edge-set. Given a bool-valued map on the node-set and one on
302 /// the edge-set of the graphs, the iterators shows only the objects
303 /// having true value.
304 /// The quick brown fox iterators jump over
305 /// the lazy dog nodes or edges if their values for are false in the
306 /// corresponding bool maps.
308 ///\author Marton Makai
309 template<typename Graph, typename NodeFilterMap,
310 typename EdgeFilterMap>
311 class SubGraphWrapper : public GraphWrapper<Graph> {
313 typedef GraphWrapper<Graph> Parent;
315 NodeFilterMap* node_filter_map;
316 EdgeFilterMap* edge_filter_map;
318 SubGraphWrapper() : GraphWrapper<Graph>(),
319 node_filter_map(0), edge_filter_map(0) { }
320 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
321 node_filter_map=&_node_filter_map;
323 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
324 edge_filter_map=&_edge_filter_map;
328 SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
329 EdgeFilterMap& _edge_filter_map) :
330 GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
331 edge_filter_map(&_edge_filter_map) { }
333 typedef typename GraphWrapper<Graph>::Node Node;
334 class NodeIt : public Node {
335 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
336 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
339 NodeIt(Invalid i) : Node(i) { }
340 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
341 Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) {
342 while (*static_cast<Node*>(this)!=INVALID &&
343 !(*(gw->node_filter_map))[*this])
344 *(static_cast<Node*>(this))=
345 ++(typename Graph::NodeIt(*(gw->graph), *this));
347 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
349 Node(n), gw(&_gw) { }
350 NodeIt& operator++() {
351 *(static_cast<Node*>(this))=
352 ++(typename Graph::NodeIt(*(gw->graph), *this));
353 while (*static_cast<Node*>(this)!=INVALID &&
354 !(*(gw->node_filter_map))[*this])
355 *(static_cast<Node*>(this))=
356 ++(typename Graph::NodeIt(*(gw->graph), *this));
360 typedef typename GraphWrapper<Graph>::Edge Edge;
361 class OutEdgeIt : public Edge {
362 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
363 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
366 OutEdgeIt(Invalid i) : Edge(i) { }
367 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
368 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) {
369 while (*static_cast<Edge*>(this)!=INVALID &&
370 !(*(gw->edge_filter_map))[*this])
371 *(static_cast<Edge*>(this))=
372 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
374 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
376 Edge(e), gw(&_gw) { }
377 OutEdgeIt& operator++() {
378 *(static_cast<Edge*>(this))=
379 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
380 while (*static_cast<Edge*>(this)!=INVALID &&
381 !(*(gw->edge_filter_map))[*this])
382 *(static_cast<Edge*>(this))=
383 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
387 class InEdgeIt : public Edge {
388 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
389 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
392 // InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
393 InEdgeIt(Invalid i) : Edge(i) { }
394 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
395 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) {
396 while (*static_cast<Edge*>(this)!=INVALID &&
397 !(*(gw->edge_filter_map))[*this])
398 *(static_cast<Edge*>(this))=
399 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
401 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
403 Edge(e), gw(&_gw) { }
404 InEdgeIt& operator++() {
405 *(static_cast<Edge*>(this))=
406 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
407 while (*static_cast<Edge*>(this)!=INVALID &&
408 !(*(gw->edge_filter_map))[*this])
409 *(static_cast<Edge*>(this))=
410 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
414 class EdgeIt : public Edge {
415 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
416 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
419 EdgeIt(Invalid i) : Edge(i) { }
420 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
421 Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) {
422 while (*static_cast<Edge*>(this)!=INVALID &&
423 !(*(gw->edge_filter_map))[*this])
424 *(static_cast<Edge*>(this))=
425 ++(typename Graph::EdgeIt(*(gw->graph), *this));
427 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
429 Edge(e), gw(&_gw) { }
430 EdgeIt& operator++() {
431 *(static_cast<Edge*>(this))=
432 ++(typename Graph::EdgeIt(*(gw->graph), *this));
433 while (*static_cast<Edge*>(this)!=INVALID &&
434 !(*(gw->edge_filter_map))[*this])
435 *(static_cast<Edge*>(this))=
436 ++(typename Graph::EdgeIt(*(gw->graph), *this));
441 NodeIt& first(NodeIt& i) const {
442 i=NodeIt(*this); return i;
444 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
445 i=OutEdgeIt(*this, p); return i;
447 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
448 i=InEdgeIt(*this, p); return i;
450 EdgeIt& first(EdgeIt& i) const {
451 i=EdgeIt(*this); return i;
454 /// This function hides \c n in the graph, i.e. the iteration
455 /// jumps over it. This is done by simply setting the value of \c n
456 /// to be false in the corresponding node-map.
457 void hide(const Node& n) const { node_filter_map->set(n, false); }
459 /// This function hides \c e in the graph, i.e. the iteration
460 /// jumps over it. This is done by simply setting the value of \c e
461 /// to be false in the corresponding edge-map.
462 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
464 /// The value of \c n is set to be true in the node-map which stores
465 /// hide information. If \c n was hidden previuosly, then it is shown
467 void unHide(const Node& n) const { node_filter_map->set(n, true); }
469 /// The value of \c e is set to be true in the edge-map which stores
470 /// hide information. If \c e was hidden previuosly, then it is shown
472 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
474 /// Returns true if \c n is hidden.
475 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
477 /// Returns true if \c n is hidden.
478 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
480 /// \warning This is a linear time operation and works only if
481 /// \c Graph::NodeIt is defined.
482 int nodeNum() const {
484 for (NodeIt n(*this); n!=INVALID; ++n) ++i;
488 /// \warning This is a linear time operation and works only if
489 /// \c Graph::EdgeIt is defined.
490 int edgeNum() const {
492 for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
496 KEEP_MAPS(Parent, SubGraphWrapper);
501 template<typename Graph>
502 class UndirGraphWrapper : public GraphWrapper<Graph> {
504 typedef GraphWrapper<Graph> Parent;
506 UndirGraphWrapper() : GraphWrapper<Graph>() { }
509 typedef typename GraphWrapper<Graph>::Node Node;
510 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
511 typedef typename GraphWrapper<Graph>::Edge Edge;
512 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
514 UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
517 friend class UndirGraphWrapper<Graph>;
518 bool out_or_in; //true iff out
519 typename Graph::OutEdgeIt out;
520 typename Graph::InEdgeIt in;
523 OutEdgeIt(const Invalid& i) : Edge(i) { }
524 OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
525 out_or_in=true; _G.graph->first(out, _n);
526 if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); }
528 operator Edge() const {
529 if (out_or_in) return Edge(out); else return Edge(in);
533 typedef OutEdgeIt InEdgeIt;
535 using GraphWrapper<Graph>::first;
536 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
537 i=OutEdgeIt(*this, p); return i;
540 using GraphWrapper<Graph>::next;
542 OutEdgeIt& next(OutEdgeIt& e) const {
544 typename Graph::Node n=this->graph->tail(e.out);
545 this->graph->next(e.out);
546 if (!this->graph->valid(e.out)) {
547 e.out_or_in=false; this->graph->first(e.in, n); }
549 this->graph->next(e.in);
554 Node aNode(const OutEdgeIt& e) const {
555 if (e.out_or_in) return this->graph->tail(e); else
556 return this->graph->head(e); }
557 Node bNode(const OutEdgeIt& e) const {
558 if (e.out_or_in) return this->graph->head(e); else
559 return this->graph->tail(e); }
561 KEEP_MAPS(Parent, UndirGraphWrapper);
565 /// \brief An undirected graph template.
567 ///\warning Graph wrappers are in even more experimental state than the other
568 ///parts of the lib. Use them at you own risk.
570 /// An undirected graph template.
571 /// This class works as an undirected graph and a directed graph of
572 /// class \c Graph is used for the physical storage.
574 template<typename Graph>
575 class UndirGraph : public UndirGraphWrapper<Graph> {
576 typedef UndirGraphWrapper<Graph> Parent;
580 UndirGraph() : UndirGraphWrapper<Graph>() {
581 Parent::setGraph(gr);
584 KEEP_MAPS(Parent, UndirGraph);
589 ///\brief A wrapper for composing a subgraph of a
590 /// bidirected graph made from a directed one.
592 ///\warning Graph wrappers are in even more experimental state than the other
593 ///parts of the lib. Use them at you own risk.
595 /// Suppose that for a directed graph $G=(V, A)$,
596 /// two predicates on the edge-set, $forward_filter$, and $backward_filter$
597 /// is given, and we are dealing with the directed graph
598 /// 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}\})$.
599 /// The purpose of writing + instead of union is because parallel
601 /// In other words, a subgraph of the bidirected graph obtained, which
602 /// is given by orienting the edges of the original graph in both directions.
603 /// An example for such a construction is the \c RevGraphWrapper where the
604 /// forward_filter is everywhere false and the backward_filter is
605 /// everywhere true. We note that for sake of efficiency,
606 /// \c RevGraphWrapper is implemented in a different way.
607 /// But BidirGraphWrapper is obtained from
608 /// SubBidirGraphWrapper by considering everywhere true
609 /// predicates both forward_filter and backward_filter.
610 /// Finally, one of the most important applications of SubBidirGraphWrapper
611 /// is ResGraphWrapper, which stands for the residual graph in directed
612 /// flow and circulation problems.
613 /// As wrappers usually, the SubBidirGraphWrapper implements the
614 /// above mentioned graph structure without its physical storage,
615 /// that is the whole stuff eats constant memory.
616 /// As the oppositely directed edges are logical different,
617 /// the maps are able to attach different values for them.
618 template<typename Graph,
619 typename ForwardFilterMap, typename BackwardFilterMap>
620 class SubBidirGraphWrapper : public GraphWrapper<Graph> {
622 typedef GraphWrapper<Graph> Parent;
624 ForwardFilterMap* forward_filter;
625 BackwardFilterMap* backward_filter;
627 SubBidirGraphWrapper() : GraphWrapper<Graph>() { }
628 void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
629 forward_filter=&_forward_filter;
631 void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
632 backward_filter=&_backward_filter;
637 SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter,
638 BackwardFilterMap& _backward_filter) :
639 GraphWrapper<Graph>(_graph),
640 forward_filter(&_forward_filter), backward_filter(&_backward_filter) { }
641 SubBidirGraphWrapper(const SubBidirGraphWrapper<Graph,
642 ForwardFilterMap, BackwardFilterMap>& gw) :
644 forward_filter(gw.forward_filter),
645 backward_filter(gw.backward_filter) { }
650 friend class OutEdgeIt;
652 template<typename T> class EdgeMap;
654 typedef typename GraphWrapper<Graph>::Node Node;
656 typedef typename Graph::Edge GraphEdge;
657 /// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from
658 /// Graph::Edge. It contains an extra bool flag which shows if the
659 /// edge is the backward version of the original edge.
660 class Edge : public Graph::Edge {
661 friend class SubBidirGraphWrapper<Graph,
662 ForwardFilterMap, BackwardFilterMap>;
663 template<typename T> friend class EdgeMap;
665 bool backward; //true, iff backward
668 /// \todo =false is needed, or causes problems?
669 /// If \c _backward is false, then we get an edge corresponding to the
670 /// original one, otherwise its oppositely directed pair is obtained.
671 Edge(const typename Graph::Edge& e, bool _backward/*=false*/) :
672 Graph::Edge(e), backward(_backward) { }
673 Edge(Invalid i) : Graph::Edge(i), backward(true) { }
674 bool operator==(const Edge& v) const {
675 return (this->backward==v.backward &&
676 static_cast<typename Graph::Edge>(*this)==
677 static_cast<typename Graph::Edge>(v));
679 bool operator!=(const Edge& v) const {
680 return (this->backward!=v.backward ||
681 static_cast<typename Graph::Edge>(*this)!=
682 static_cast<typename Graph::Edge>(v));
686 class OutEdgeIt : public Edge {
687 friend class SubBidirGraphWrapper<Graph,
688 ForwardFilterMap, BackwardFilterMap>;
690 const SubBidirGraphWrapper<Graph,
691 ForwardFilterMap, BackwardFilterMap>* gw;
694 OutEdgeIt(Invalid i) : Edge(i) { }
695 OutEdgeIt(const SubBidirGraphWrapper<Graph,
696 ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
697 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
698 while (*static_cast<GraphEdge*>(this)!=INVALID &&
699 !(*(gw->forward_filter))[*this])
700 *(static_cast<GraphEdge*>(this))=
701 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
702 if (*static_cast<GraphEdge*>(this)==INVALID) {
703 *static_cast<Edge*>(this)=
704 Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true);
705 while (*static_cast<GraphEdge*>(this)!=INVALID &&
706 !(*(gw->backward_filter))[*this])
707 *(static_cast<GraphEdge*>(this))=
708 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
711 OutEdgeIt(const SubBidirGraphWrapper<Graph,
712 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
713 Edge(e), gw(&_gw) { }
714 OutEdgeIt& operator++() {
715 if (!this->backward) {
716 Node n=gw->tail(*this);
717 *(static_cast<GraphEdge*>(this))=
718 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
719 while (*static_cast<GraphEdge*>(this)!=INVALID &&
720 !(*(gw->forward_filter))[*this])
721 *(static_cast<GraphEdge*>(this))=
722 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
723 if (*static_cast<GraphEdge*>(this)==INVALID) {
724 *static_cast<Edge*>(this)=
725 Edge(typename Graph::InEdgeIt(*(gw->graph), n), true);
726 while (*static_cast<GraphEdge*>(this)!=INVALID &&
727 !(*(gw->backward_filter))[*this])
728 *(static_cast<GraphEdge*>(this))=
729 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
732 *(static_cast<GraphEdge*>(this))=
733 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
734 while (*static_cast<GraphEdge*>(this)!=INVALID &&
735 !(*(gw->backward_filter))[*this])
736 *(static_cast<GraphEdge*>(this))=
737 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
743 class InEdgeIt : public Edge {
744 friend class SubBidirGraphWrapper<Graph,
745 ForwardFilterMap, BackwardFilterMap>;
747 const SubBidirGraphWrapper<Graph,
748 ForwardFilterMap, BackwardFilterMap>* gw;
751 InEdgeIt(Invalid i) : Edge(i) { }
752 InEdgeIt(const SubBidirGraphWrapper<Graph,
753 ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
754 Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
755 while (*static_cast<GraphEdge*>(this)!=INVALID &&
756 !(*(gw->forward_filter))[*this])
757 *(static_cast<GraphEdge*>(this))=
758 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
759 if (*static_cast<GraphEdge*>(this)==INVALID) {
760 *static_cast<Edge*>(this)=
761 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true);
762 while (*static_cast<GraphEdge*>(this)!=INVALID &&
763 !(*(gw->backward_filter))[*this])
764 *(static_cast<GraphEdge*>(this))=
765 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
768 InEdgeIt(const SubBidirGraphWrapper<Graph,
769 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
770 Edge(e), gw(&_gw) { }
771 InEdgeIt& operator++() {
772 if (!this->backward) {
773 Node n=gw->tail(*this);
774 *(static_cast<GraphEdge*>(this))=
775 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
776 while (*static_cast<GraphEdge*>(this)!=INVALID &&
777 !(*(gw->forward_filter))[*this])
778 *(static_cast<GraphEdge*>(this))=
779 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
780 if (*static_cast<GraphEdge*>(this)==INVALID) {
781 *static_cast<Edge*>(this)=
782 Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true);
783 while (*static_cast<GraphEdge*>(this)!=INVALID &&
784 !(*(gw->backward_filter))[*this])
785 *(static_cast<GraphEdge*>(this))=
786 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
789 *(static_cast<GraphEdge*>(this))=
790 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
791 while (*static_cast<GraphEdge*>(this)!=INVALID &&
792 !(*(gw->backward_filter))[*this])
793 *(static_cast<GraphEdge*>(this))=
794 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
800 class EdgeIt : public Edge {
801 friend class SubBidirGraphWrapper<Graph,
802 ForwardFilterMap, BackwardFilterMap>;
804 const SubBidirGraphWrapper<Graph,
805 ForwardFilterMap, BackwardFilterMap>* gw;
808 EdgeIt(Invalid i) : Edge(i) { }
809 EdgeIt(const SubBidirGraphWrapper<Graph,
810 ForwardFilterMap, BackwardFilterMap>& _gw) :
811 Edge(typename Graph::OutEdgeIt(*(_gw.graph)), false), gw(&_gw) {
812 while (*static_cast<GraphEdge*>(this)!=INVALID &&
813 !(*(gw->forward_filter))[*this])
814 *(static_cast<GraphEdge*>(this))=
815 ++(typename Graph::EdgeIt(*(gw->graph), *this));
816 if (*static_cast<GraphEdge*>(this)==INVALID) {
817 *static_cast<Edge*>(this)=
818 Edge(typename Graph::EdgeIt(*(_gw.graph)), true);
819 while (*static_cast<GraphEdge*>(this)!=INVALID &&
820 !(*(gw->backward_filter))[*this])
821 *(static_cast<GraphEdge*>(this))=
822 ++(typename Graph::EdgeIt(*(gw->graph), *this));
825 EdgeIt(const SubBidirGraphWrapper<Graph,
826 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
827 Edge(e), gw(&_gw) { }
828 EdgeIt& operator++() {
829 if (!this->backward) {
830 *(static_cast<GraphEdge*>(this))=
831 ++(typename Graph::EdgeIt(*(gw->graph), *this));
832 while (*static_cast<GraphEdge*>(this)!=INVALID &&
833 !(*(gw->forward_filter))[*this])
834 *(static_cast<GraphEdge*>(this))=
835 ++(typename Graph::EdgeIt(*(gw->graph), *this));
836 if (*static_cast<GraphEdge*>(this)==INVALID) {
837 *static_cast<Edge*>(this)=
838 Edge(typename Graph::EdgeIt(*(gw->graph)), true);
839 while (*static_cast<GraphEdge*>(this)!=INVALID &&
840 !(*(gw->backward_filter))[*this])
841 *(static_cast<GraphEdge*>(this))=
842 ++(typename Graph::EdgeIt(*(gw->graph), *this));
845 *(static_cast<GraphEdge*>(this))=
846 ++(typename Graph::EdgeIt(*(gw->graph), *this));
847 while (*static_cast<GraphEdge*>(this)!=INVALID &&
848 !(*(gw->backward_filter))[*this])
849 *(static_cast<GraphEdge*>(this))=
850 ++(typename Graph::EdgeIt(*(gw->graph), *this));
856 using GraphWrapper<Graph>::first;
857 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
858 i=OutEdgeIt(*this, p); return i;
860 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
861 i=InEdgeIt(*this, p); return i;
863 EdgeIt& first(EdgeIt& i) const {
864 i=EdgeIt(*this); return i;
868 Node tail(Edge e) const {
869 return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
870 Node head(Edge e) const {
871 return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
873 /// Gives back the opposite edge.
874 Edge opposite(const Edge& e) const {
876 f.backward=!f.backward;
880 /// \warning This is a linear time operation and works only if
881 /// \c Graph::EdgeIt is defined.
882 int edgeNum() const {
884 for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
888 bool forward(const Edge& e) const { return !e.backward; }
889 bool backward(const Edge& e) const { return e.backward; }
892 template <typename T>
893 /// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two
894 /// Graph::EdgeMap one for the forward edges and
895 /// one for the backward edges.
897 typename Graph::template EdgeMap<T> forward_map, backward_map;
900 typedef Edge KeyType;
901 EdgeMap(const SubBidirGraphWrapper<Graph,
902 ForwardFilterMap, BackwardFilterMap>& g) :
903 forward_map(*(g.graph)), backward_map(*(g.graph)) { }
904 EdgeMap(const SubBidirGraphWrapper<Graph,
905 ForwardFilterMap, BackwardFilterMap>& g, T a) :
906 forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
907 void set(Edge e, T a) {
909 forward_map.set(e, a);
911 backward_map.set(e, a);
913 T operator[](Edge e) const {
915 return forward_map[e];
917 return backward_map[e];
920 forward_map.update();
921 backward_map.update();
926 KEEP_NODE_MAP(Parent, SubBidirGraphWrapper);
931 ///\brief A wrapper for composing bidirected graph from a directed one.
933 ///\warning Graph wrappers are in even more experimental state than the other
934 ///parts of the lib. Use them at you own risk.
936 /// A wrapper for composing bidirected graph from a directed one.
937 /// A bidirected graph is composed over the directed one without physical
938 /// storage. As the oppositely directed edges are logically different ones
939 /// the maps are able to attach different values for them.
940 template<typename Graph>
941 class BidirGraphWrapper :
942 public SubBidirGraphWrapper<
944 ConstMap<typename Graph::Edge, bool>,
945 ConstMap<typename Graph::Edge, bool> > {
947 typedef SubBidirGraphWrapper<
949 ConstMap<typename Graph::Edge, bool>,
950 ConstMap<typename Graph::Edge, bool> > Parent;
952 ConstMap<typename Graph::Edge, bool> cm;
954 BidirGraphWrapper() : Parent(), cm(true) {
955 Parent::setForwardFilterMap(cm);
956 Parent::setBackwardFilterMap(cm);
959 BidirGraphWrapper(Graph& _graph) : Parent() {
960 Parent::setGraph(_graph);
961 Parent::setForwardFilterMap(cm);
962 Parent::setBackwardFilterMap(cm);
965 int edgeNum() const {
966 return 2*this->graph->edgeNum();
968 KEEP_MAPS(Parent, BidirGraphWrapper);
972 /// \brief A bidirected graph template.
974 ///\warning Graph wrappers are in even more experimental state than the other
975 ///parts of the lib. Use them at you own risk.
977 /// A bidirected graph template.
978 /// Such a bidirected graph stores each pair of oppositely directed edges
979 /// ones in the memory, i.e. a directed graph of type
980 /// \c Graph is used for that.
981 /// As the oppositely directed edges are logically different ones
982 /// the maps are able to attach different values for them.
984 template<typename Graph>
985 class BidirGraph : public BidirGraphWrapper<Graph> {
987 typedef UndirGraphWrapper<Graph> Parent;
991 BidirGraph() : BidirGraphWrapper<Graph>() {
992 Parent::setGraph(gr);
994 KEEP_MAPS(Parent, BidirGraph);
999 template<typename Graph, typename Number,
1000 typename CapacityMap, typename FlowMap>
1001 class ResForwardFilter {
1002 // const Graph* graph;
1003 const CapacityMap* capacity;
1004 const FlowMap* flow;
1006 ResForwardFilter(/*const Graph& _graph, */
1007 const CapacityMap& _capacity, const FlowMap& _flow) :
1008 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1009 ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1010 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1011 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1012 bool operator[](const typename Graph::Edge& e) const {
1013 return (Number((*flow)[e]) < Number((*capacity)[e]));
1017 template<typename Graph, typename Number,
1018 typename CapacityMap, typename FlowMap>
1019 class ResBackwardFilter {
1020 const CapacityMap* capacity;
1021 const FlowMap* flow;
1023 ResBackwardFilter(/*const Graph& _graph,*/
1024 const CapacityMap& _capacity, const FlowMap& _flow) :
1025 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1026 ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1027 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1028 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1029 bool operator[](const typename Graph::Edge& e) const {
1030 return (Number(0) < Number((*flow)[e]));
1035 /// A wrapper for composing the residual graph for directed flow and circulation problems.
1037 ///\warning Graph wrappers are in even more experimental state than the other
1038 ///parts of the lib. Use them at you own risk.
1040 /// A wrapper for composing the residual graph for directed flow and circulation problems.
1041 template<typename Graph, typename Number,
1042 typename CapacityMap, typename FlowMap>
1043 class ResGraphWrapper :
1044 public SubBidirGraphWrapper<
1046 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1047 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1049 typedef SubBidirGraphWrapper<
1051 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1052 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1054 const CapacityMap* capacity;
1056 ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1057 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1058 ResGraphWrapper() : Parent(),
1059 capacity(0), flow(0) { }
1060 void setCapacityMap(const CapacityMap& _capacity) {
1061 capacity=&_capacity;
1062 forward_filter.setCapacity(_capacity);
1063 backward_filter.setCapacity(_capacity);
1065 void setFlowMap(FlowMap& _flow) {
1067 forward_filter.setFlow(_flow);
1068 backward_filter.setFlow(_flow);
1071 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1073 Parent(), capacity(&_capacity), flow(&_flow),
1074 forward_filter(/*_graph,*/ _capacity, _flow),
1075 backward_filter(/*_graph,*/ _capacity, _flow) {
1076 Parent::setGraph(_graph);
1077 Parent::setForwardFilterMap(forward_filter);
1078 Parent::setBackwardFilterMap(backward_filter);
1081 typedef typename Parent::Edge Edge;
1083 void augment(const Edge& e, Number a) const {
1084 if (Parent::forward(e))
1085 flow->set(e, (*flow)[e]+a);
1087 flow->set(e, (*flow)[e]-a);
1090 /// \brief Residual capacity map.
1092 /// In generic residual graphs the residual capacity can be obtained as a map. Not tested.
1095 const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
1097 typedef Number ValueType;
1098 typedef Edge KeyType;
1099 ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>&
1100 _res_graph) : res_graph(&_res_graph) { }
1101 Number operator[](const Edge& e) const {
1102 if (res_graph->forward(e))
1103 return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1105 return (*(res_graph->flow))[e];
1109 KEEP_MAPS(Parent, ResGraphWrapper);
1113 /// For blocking flows.
1115 ///\warning Graph wrappers are in even more experimental state than the other
1116 ///parts of the lib. Use them at you own risk.
1118 /// This graph wrapper is used for on-the-fly
1119 /// Dinits blocking flow computations.
1120 /// For each node, an out-edge is stored which is used when the
1122 /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1126 /// \author Marton Makai
1127 template<typename Graph, typename FirstOutEdgesMap>
1128 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1130 typedef GraphWrapper<Graph> Parent;
1132 FirstOutEdgesMap* first_out_edges;
1134 ErasingFirstGraphWrapper(Graph& _graph,
1135 FirstOutEdgesMap& _first_out_edges) :
1136 GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
1138 typedef typename GraphWrapper<Graph>::Node Node;
1139 typedef typename GraphWrapper<Graph>::Edge Edge;
1140 class OutEdgeIt : public Edge {
1141 friend class GraphWrapper<Graph>;
1142 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1143 const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>* gw;
1146 OutEdgeIt(Invalid i) : Edge(i) { }
1147 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
1149 Edge((*(_gw.first_out_edges))[n]), gw(&_gw) { }
1150 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
1152 Edge(e), gw(&_gw) { }
1153 OutEdgeIt& operator++() {
1154 *(static_cast<Edge*>(this))=
1155 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1160 using GraphWrapper<Graph>::first;
1161 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1162 i=OutEdgeIt(*this, p); return i;
1164 void erase(const Edge& e) const {
1166 typename Graph::OutEdgeIt f(*Parent::graph, n);
1168 first_out_edges->set(n, f);
1171 KEEP_MAPS(Parent, ErasingFirstGraphWrapper);
1178 #endif //HUGO_GRAPH_WRAPPER_H