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 <iter_map.h>
20 /// \addtogroup gwrappers
21 /// A main parts of HUGOlib are the different graph structures,
22 /// generic graph algorithms, graph concepts which couple these, and
23 /// graph wrappers. While the previous ones are more or less clear, the
24 /// latter notion needs further explanation.
25 /// Graph wrappers are graph classes which serve for considering graph
26 /// structures in different ways. A short example makes the notion much
28 /// Suppose that we have an instance \c g of a directed graph
29 /// type say \c ListGraph and an algorithm
30 /// \code template<typename Graph> int algorithm(const Graph&); \endcode
31 /// is needed to run on the reversely oriented graph.
32 /// It may be expensive (in time or in memory usage) to copy
33 /// \c g with the reverse orientation.
34 /// Thus, a wrapper class
35 /// \code template<typename Graph> class RevGraphWrapper; \endcode is used.
36 /// The code looks as follows
39 /// RevGraphWrapper<ListGraph> rgw(g);
40 /// int result=algorithm(rgw);
42 /// After running the algorithm, the original graph \c g
43 /// remains untouched. Thus the graph wrapper used above is to consider the
44 /// original graph with reverse orientation.
45 /// This techniques gives rise to an elegant code, and
46 /// based on stable graph wrappers, complex algorithms can be
47 /// implemented easily.
48 /// In flow, circulation and bipartite matching problems, the residual
49 /// graph is of particular importance. Combining a wrapper implementing
50 /// this, shortest path algorithms and minimum mean cycle algorithms,
51 /// a range of weighted and cardinality optimization algorithms can be
52 /// obtained. For lack of space, for other examples,
53 /// the interested user is referred to the detailed documentation of graph
55 /// The behavior of graph wrappers can be very different. Some of them keep
56 /// capabilities of the original graph while in other cases this would be
57 /// meaningless. This means that the concepts that they are a model of depend
58 /// on the graph wrapper, and the wrapped graph(s).
59 /// If an edge of \c rgw is deleted, this is carried out by
60 /// deleting the corresponding edge of \c g. But for a residual
61 /// graph, this operation has no sense.
62 /// Let we stand one more example here to simplify your work.
64 /// \code template<typename Graph> class RevGraphWrapper; \endcode
66 /// <tt> RevGraphWrapper(Graph& _g)</tt>.
67 /// This means that in a situation,
68 /// when a <tt> const ListGraph& </tt> reference to a graph is given,
69 /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
71 /// int algorithm1(const ListGraph& g) {
72 /// RevGraphWrapper<const ListGraph> rgw(g);
73 /// return algorithm2(rgw);
77 /// \addtogroup gwrappers
80 ///Base type for the Graph Wrappers
82 ///This is the base type for the Graph Wrappers.
83 ///\todo Some more docs...
85 ///\author Marton Makai
87 template<typename Graph>
91 GraphWrapper() : graph(0) { }
92 void setGraph(Graph& _graph) { graph=&_graph; }
95 typedef Graph BaseGraph;
96 typedef Graph ParentGraph;
98 GraphWrapper(Graph& _graph) : graph(&_graph) { }
99 // Graph& getGraph() const { return *graph; }
101 // typedef typename Graph::Node Node;
102 class Node : public Graph::Node {
103 friend class GraphWrapper<Graph>;
106 Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
107 Node(const Invalid& i) : Graph::Node(i) { }
110 friend class GraphWrapper<Graph>;
111 typename Graph::NodeIt n;
114 NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
115 NodeIt(const Invalid& i) : n(i) { }
116 NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
117 operator Node() const { return Node(typename Graph::Node(n)); }
119 // typedef typename Graph::Edge Edge;
120 class Edge : public Graph::Edge {
121 friend class GraphWrapper<Graph>;
124 Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
125 Edge(const Invalid& i) : Graph::Edge(i) { }
128 friend class GraphWrapper<Graph>;
129 typename Graph::OutEdgeIt e;
132 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
133 OutEdgeIt(const Invalid& i) : e(i) { }
134 OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
135 e(*(_G.graph), typename Graph::Node(_n)) { }
136 operator Edge() const { return Edge(typename Graph::Edge(e)); }
139 friend class GraphWrapper<Graph>;
140 typename Graph::InEdgeIt e;
143 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
144 InEdgeIt(const Invalid& i) : e(i) { }
145 InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
146 e(*(_G.graph), typename Graph::Node(_n)) { }
147 operator Edge() const { return Edge(typename Graph::Edge(e)); }
149 //typedef typename Graph::SymEdgeIt SymEdgeIt;
151 friend class GraphWrapper<Graph>;
152 typename Graph::EdgeIt e;
155 EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
156 EdgeIt(const Invalid& i) : e(i) { }
157 EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
158 operator Edge() const { return Edge(typename Graph::Edge(e)); }
161 NodeIt& first(NodeIt& i) const {
162 i=NodeIt(*this); return i;
164 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
165 i=OutEdgeIt(*this, p); return i;
167 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
168 i=InEdgeIt(*this, p); return i;
170 EdgeIt& first(EdgeIt& i) const {
171 i=EdgeIt(*this); return i;
174 NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
175 OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
176 InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
177 EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
179 Node tail(const Edge& e) const {
180 return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
181 Node head(const Edge& e) const {
182 return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
184 bool valid(const Node& n) const {
185 return graph->valid(static_cast<typename Graph::Node>(n)); }
186 bool valid(const Edge& e) const {
187 return graph->valid(static_cast<typename Graph::Edge>(e)); }
189 int nodeNum() const { return graph->nodeNum(); }
190 int edgeNum() const { return graph->edgeNum(); }
192 Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
193 Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
194 Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
195 Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
197 Node addNode() const { return Node(graph->addNode()); }
198 Edge addEdge(const Node& tail, const Node& head) const {
199 return Edge(graph->addEdge(tail, head)); }
201 void erase(const Node& i) const { graph->erase(i); }
202 void erase(const Edge& i) const { graph->erase(i); }
204 void clear() const { graph->clear(); }
206 template<typename T> class NodeMap : public Graph::template NodeMap<T> {
207 typedef typename Graph::template NodeMap<T> Parent;
209 NodeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
210 NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
213 template<typename T> class EdgeMap : public Graph::template EdgeMap<T> {
214 typedef typename Graph::template EdgeMap<T> Parent;
216 EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
217 EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
223 /// A graph wrapper which reverses the orientation of the edges.
225 /// A graph wrapper which reverses the orientation of the edges.
227 ///\author Marton Makai
228 template<typename Graph>
229 class RevGraphWrapper : public GraphWrapper<Graph> {
231 RevGraphWrapper() : GraphWrapper<Graph>(0) { }
233 RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
235 typedef typename GraphWrapper<Graph>::Node Node;
236 typedef typename GraphWrapper<Graph>::Edge Edge;
237 //If Graph::OutEdgeIt is not defined
238 //and we do not want to use RevGraphWrapper::InEdgeIt,
239 //the typdef techinque does not work.
240 //Unfortunately all the typedefs are instantiated in templates.
241 //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
242 //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
245 friend class GraphWrapper<Graph>;
246 friend class RevGraphWrapper<Graph>;
247 typename Graph::InEdgeIt e;
250 OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
251 OutEdgeIt(const Invalid& i) : e(i) { }
252 OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
253 e(*(_G.graph), typename Graph::Node(_n)) { }
254 operator Edge() const { return Edge(typename Graph::Edge(e)); }
257 friend class GraphWrapper<Graph>;
258 friend class RevGraphWrapper<Graph>;
259 typename Graph::OutEdgeIt e;
262 InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
263 InEdgeIt(const Invalid& i) : e(i) { }
264 InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
265 e(*(_G.graph), typename Graph::Node(_n)) { }
266 operator Edge() const { return Edge(typename Graph::Edge(e)); }
269 using GraphWrapper<Graph>::first;
270 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
271 i=OutEdgeIt(*this, p); return i;
273 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
274 i=InEdgeIt(*this, p); return i;
277 using GraphWrapper<Graph>::next;
278 OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
279 InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
281 Node aNode(const OutEdgeIt& e) const {
282 return Node(this->graph->aNode(e.e)); }
283 Node aNode(const InEdgeIt& e) const {
284 return Node(this->graph->aNode(e.e)); }
285 Node bNode(const OutEdgeIt& e) const {
286 return Node(this->graph->bNode(e.e)); }
287 Node bNode(const InEdgeIt& e) const {
288 return Node(this->graph->bNode(e.e)); }
290 Node tail(const Edge& e) const {
291 return GraphWrapper<Graph>::head(e); }
292 Node head(const Edge& e) const {
293 return GraphWrapper<Graph>::tail(e); }
299 /// Wrapper for hiding nodes and edges from a graph.
301 /// This wrapper shows a graph with filtered node-set and
302 /// edge-set. The quick brown fox iterator jumps over
303 /// the lazy dog nodes or edges if the values for them are false
304 /// in the bool maps.
306 ///\author Marton Makai
307 template<typename Graph, typename NodeFilterMap,
308 typename EdgeFilterMap>
309 class SubGraphWrapper : public GraphWrapper<Graph> {
311 NodeFilterMap* node_filter_map;
312 EdgeFilterMap* edge_filter_map;
314 SubGraphWrapper() : GraphWrapper<Graph>(0),
315 node_filter_map(0), edge_filter_map(0) { }
316 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
317 node_filter_map=&_node_filter_map;
319 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
320 edge_filter_map=&_edge_filter_map;
325 SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
326 EdgeFilterMap& _edge_filter_map) :
327 GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
328 edge_filter_map(&_edge_filter_map) { }
330 typedef typename GraphWrapper<Graph>::Node Node;
332 friend class GraphWrapper<Graph>;
333 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
334 typename Graph::NodeIt n;
337 NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
338 NodeIt(const Invalid& i) : n(i) { }
339 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
341 while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
344 operator Node() const { return Node(typename Graph::Node(n)); }
346 typedef typename GraphWrapper<Graph>::Edge Edge;
348 friend class GraphWrapper<Graph>;
349 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
350 typename Graph::OutEdgeIt e;
353 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
354 OutEdgeIt(const Invalid& i) : e(i) { }
355 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
357 e(*(_G.graph), typename Graph::Node(_n)) {
358 while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
361 operator Edge() const { return Edge(typename Graph::Edge(e)); }
364 friend class GraphWrapper<Graph>;
365 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
366 typename Graph::InEdgeIt e;
369 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
370 InEdgeIt(const Invalid& i) : e(i) { }
371 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
373 e(*(_G.graph), typename Graph::Node(_n)) {
374 while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
377 operator Edge() const { return Edge(typename Graph::Edge(e)); }
379 //typedef typename Graph::SymEdgeIt SymEdgeIt;
381 friend class GraphWrapper<Graph>;
382 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
383 typename Graph::EdgeIt e;
386 EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
387 EdgeIt(const Invalid& i) : e(i) { }
388 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
390 while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
393 operator Edge() const { return Edge(typename Graph::Edge(e)); }
396 NodeIt& first(NodeIt& i) const {
397 i=NodeIt(*this); return i;
399 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
400 i=OutEdgeIt(*this, p); return i;
402 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
403 i=InEdgeIt(*this, p); return i;
405 EdgeIt& first(EdgeIt& i) const {
406 i=EdgeIt(*this); return i;
409 NodeIt& next(NodeIt& i) const {
410 this->graph->next(i.n);
411 while (this->graph->valid(i) && !(*node_filter_map)[i.n]) {
412 this->graph->next(i.n); }
415 OutEdgeIt& next(OutEdgeIt& i) const {
416 this->graph->next(i.e);
417 while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
418 this->graph->next(i.e); }
421 InEdgeIt& next(InEdgeIt& i) const {
422 this->graph->next(i.e);
423 while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
424 this->graph->next(i.e); }
427 EdgeIt& next(EdgeIt& i) const {
428 this->graph->next(i.e);
429 while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
430 this->graph->next(i.e); }
434 Node aNode(const OutEdgeIt& e) const {
435 return Node(this->graph->aNode(e.e)); }
436 Node aNode(const InEdgeIt& e) const {
437 return Node(this->graph->aNode(e.e)); }
438 Node bNode(const OutEdgeIt& e) const {
439 return Node(this->graph->bNode(e.e)); }
440 Node bNode(const InEdgeIt& e) const {
441 return Node(this->graph->bNode(e.e)); }
443 /// This function hides \c n in the graph, i.e. the iteration
444 /// jumps over it. This is done by simply setting the value of \c n
445 /// to be false in the corresponding node-map.
446 void hide(const Node& n) const { node_filter_map->set(n, false); }
448 /// This function hides \c e in the graph, i.e. the iteration
449 /// jumps over it. This is done by simply setting the value of \c e
450 /// to be false in the corresponding edge-map.
451 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
453 /// The value of \c n is set to be true in the node-map which stores
454 /// hide information. If \c n was hidden previuosly, then it is shown
456 void unHide(const Node& n) const { node_filter_map->set(n, true); }
458 /// The value of \c e is set to be true in the edge-map which stores
459 /// hide information. If \c e was hidden previuosly, then it is shown
461 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
463 /// Returns true if \c n is hidden.
464 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
466 /// Returns true if \c n is hidden.
467 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
472 /// A wrapper for forgetting the orientation of a graph.
474 /// A wrapper for getting an undirected graph by forgetting
475 /// the orientation of a directed one.
476 template<typename Graph>
477 class UndirGraphWrapper : public GraphWrapper<Graph> {
479 UndirGraphWrapper() : GraphWrapper<Graph>() { }
482 typedef typename GraphWrapper<Graph>::Node Node;
483 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
484 typedef typename GraphWrapper<Graph>::Edge Edge;
485 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
487 UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
490 friend class UndirGraphWrapper<Graph>;
491 bool out_or_in; //true iff out
492 typename Graph::OutEdgeIt out;
493 typename Graph::InEdgeIt in;
496 OutEdgeIt(const Invalid& i) : Edge(i) { }
497 OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
498 out_or_in=true; _G.graph->first(out, _n);
499 if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); }
501 operator Edge() const {
502 if (out_or_in) return Edge(out); else return Edge(in);
507 typedef OutEdgeIt InEdgeIt;
509 using GraphWrapper<Graph>::first;
510 // NodeIt& first(NodeIt& i) const {
511 // i=NodeIt(*this); return i;
513 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
514 i=OutEdgeIt(*this, p); return i;
517 // InEdgeIt& first(InEdgeIt& i, const Node& p) const {
518 // i=InEdgeIt(*this, p); return i;
520 // EdgeIt& first(EdgeIt& i) const {
521 // i=EdgeIt(*this); return i;
524 using GraphWrapper<Graph>::next;
525 // NodeIt& next(NodeIt& n) const {
526 // GraphWrapper<Graph>::next(n);
529 OutEdgeIt& next(OutEdgeIt& e) const {
531 typename Graph::Node n=this->graph->tail(e.out);
532 this->graph->next(e.out);
533 if (!this->graph->valid(e.out)) {
534 e.out_or_in=false; this->graph->first(e.in, n); }
536 this->graph->next(e.in);
541 // EdgeIt& next(EdgeIt& e) const {
542 // GraphWrapper<Graph>::next(n);
543 // // graph->next(e.e);
547 Node aNode(const OutEdgeIt& e) const {
548 if (e.out_or_in) return this->graph->tail(e); else
549 return this->graph->head(e); }
550 Node bNode(const OutEdgeIt& e) const {
551 if (e.out_or_in) return this->graph->head(e); else
552 return this->graph->tail(e); }
557 /// An undirected graph template
558 template<typename Graph>
559 class UndirGraph : public UndirGraphWrapper<Graph> {
560 typedef UndirGraphWrapper<Graph> Parent;
564 UndirGraph() : UndirGraphWrapper<Graph>() {
565 Parent::setGraph(gr);
571 /// A wrapper for composing bidirected graph from a directed one.
572 /// experimental, for fezso's sake.
573 template<typename Graph>
574 class BidirGraphWrapper : public GraphWrapper<Graph> {
576 //const CapacityMap* capacity;
579 BidirGraphWrapper() : GraphWrapper<Graph>()/*,
580 capacity(0), flow(0)*/ { }
581 // void setCapacityMap(const CapacityMap& _capacity) {
582 // capacity=&_capacity;
584 // void setFlowMap(FlowMap& _flow) {
590 BidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity,
592 GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
597 friend class OutEdgeIt;
599 typedef typename GraphWrapper<Graph>::Node Node;
600 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
601 class Edge : public Graph::Edge {
602 friend class BidirGraphWrapper<Graph>;
604 bool backward; //true, iff backward
605 // typename Graph::Edge e;
608 Edge(const typename Graph::Edge& _e, bool _backward) :
609 Graph::Edge(_e), backward(_backward) { }
610 Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
611 //the unique invalid iterator
612 friend bool operator==(const Edge& u, const Edge& v) {
613 return (v.backward==u.backward &&
614 static_cast<typename Graph::Edge>(u)==
615 static_cast<typename Graph::Edge>(v));
617 friend bool operator!=(const Edge& u, const Edge& v) {
618 return (v.backward!=u.backward ||
619 static_cast<typename Graph::Edge>(u)!=
620 static_cast<typename Graph::Edge>(v));
625 friend class BidirGraphWrapper<Graph>;
627 typename Graph::OutEdgeIt out;
628 typename Graph::InEdgeIt in;
633 // OutEdgeIt(const Edge& e) : Edge(e) { }
634 OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
635 //the unique invalid iterator
636 OutEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) {
638 _G.graph->first(out, v);
639 while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
640 if (!_G.graph->valid(out)) {
642 _G.graph->first(in, v);
643 while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
646 operator Edge() const {
648 // e.forward=this->forward;
649 // if (this->forward) e=out; else e=in;
652 return Edge(in, this->backward);
654 return Edge(out, this->backward);
659 friend class BidirGraphWrapper<Graph>;
661 typename Graph::OutEdgeIt out;
662 typename Graph::InEdgeIt in;
667 // OutEdgeIt(const Edge& e) : Edge(e) { }
668 InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
669 //the unique invalid iterator
670 InEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) {
672 _G.graph->first(in, v);
673 while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
674 if (!_G.graph->valid(in)) {
676 _G.graph->first(out, v);
677 while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
680 operator Edge() const {
682 // e.forward=this->forward;
683 // if (this->forward) e=out; else e=in;
686 return Edge(out, this->backward);
688 return Edge(in, this->backward);
693 friend class BidirGraphWrapper<Graph>;
695 typename Graph::EdgeIt e;
699 EdgeIt(const Invalid& i) : e(i), backward(true) { }
700 EdgeIt(const BidirGraphWrapper<Graph>& _G) {
703 while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
704 if (!_G.graph->valid(e)) {
707 while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
710 operator Edge() const {
711 return Edge(e, this->backward);
715 using GraphWrapper<Graph>::first;
716 // NodeIt& first(NodeIt& i) const {
717 // i=NodeIt(*this); return i;
719 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
720 i=OutEdgeIt(*this, p); return i;
723 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
724 i=InEdgeIt(*this, p); return i;
726 EdgeIt& first(EdgeIt& i) const {
727 i=EdgeIt(*this); return i;
730 using GraphWrapper<Graph>::next;
731 // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
732 OutEdgeIt& next(OutEdgeIt& e) const {
734 Node v=this->graph->aNode(e.out);
735 this->graph->next(e.out);
736 while(this->graph->valid(e.out) && !enabled(e)) {
737 this->graph->next(e.out); }
738 if (!this->graph->valid(e.out)) {
740 this->graph->first(e.in, v);
741 while(this->graph->valid(e.in) && !enabled(e)) {
742 this->graph->next(e.in); }
745 this->graph->next(e.in);
746 while(this->graph->valid(e.in) && !enabled(e)) {
747 this->graph->next(e.in); }
752 InEdgeIt& next(InEdgeIt& e) const {
754 Node v=this->graph->aNode(e.in);
755 this->graph->next(e.in);
756 while(this->graph->valid(e.in) && !enabled(e)) {
757 this->graph->next(e.in); }
758 if (!this->graph->valid(e.in)) {
760 this->graph->first(e.out, v);
761 while(this->graph->valid(e.out) && !enabled(e)) {
762 this->graph->next(e.out); }
765 this->graph->next(e.out);
766 while(this->graph->valid(e.out) && !enabled(e)) {
767 this->graph->next(e.out); }
771 EdgeIt& next(EdgeIt& e) const {
773 this->graph->next(e.e);
774 while(this->graph->valid(e.e) && !enabled(e)) {
775 this->graph->next(e.e); }
776 if (!this->graph->valid(e.e)) {
778 this->graph->first(e.e);
779 while(this->graph->valid(e.e) && !enabled(e)) {
780 this->graph->next(e.e); }
783 this->graph->next(e.e);
784 while(this->graph->valid(e.e) && !enabled(e)) {
785 this->graph->next(e.e); }
790 Node tail(Edge e) const {
791 return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
792 Node head(Edge e) const {
793 return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
795 Node aNode(OutEdgeIt e) const {
796 return ((!e.backward) ? this->graph->aNode(e.out) :
797 this->graph->aNode(e.in)); }
798 Node bNode(OutEdgeIt e) const {
799 return ((!e.backward) ? this->graph->bNode(e.out) :
800 this->graph->bNode(e.in)); }
802 Node aNode(InEdgeIt e) const {
803 return ((!e.backward) ? this->graph->aNode(e.in) :
804 this->graph->aNode(e.out)); }
805 Node bNode(InEdgeIt e) const {
806 return ((!e.backward) ? this->graph->bNode(e.in) :
807 this->graph->bNode(e.out)); }
809 /// Gives back the opposite edge.
810 Edge opposite(const Edge& e) const {
812 f.backward=!f.backward;
816 // int nodeNum() const { return graph->nodeNum(); }
818 void edgeNum() const { }
819 //int edgeNum() const { return graph->edgeNum(); }
822 // int id(Node v) const { return graph->id(v); }
824 bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
825 bool valid(Edge e) const {
826 return this->graph->valid(e);
827 //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
830 bool forward(const Edge& e) const { return !e.backward; }
831 bool backward(const Edge& e) const { return e.backward; }
833 // void augment(const Edge& e, Number a) const {
835 // // flow->set(e.out, flow->get(e.out)+a);
836 // flow->set(e, (*flow)[e]+a);
838 // // flow->set(e.in, flow->get(e.in)-a);
839 // flow->set(e, (*flow)[e]-a);
842 bool enabled(const Edge& e) const {
844 // return (capacity->get(e.out)-flow->get(e.out));
845 //return ((*capacity)[e]-(*flow)[e]);
848 // return (flow->get(e.in));
849 //return ((*flow)[e]);
853 // Number enabled(typename Graph::OutEdgeIt out) const {
854 // // return (capacity->get(out)-flow->get(out));
855 // return ((*capacity)[out]-(*flow)[out]);
858 // Number enabled(typename Graph::InEdgeIt in) const {
859 // // return (flow->get(in));
860 // return ((*flow)[in]);
863 template <typename T>
865 typename Graph::template EdgeMap<T> forward_map, backward_map;
867 EdgeMap(const BidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
868 EdgeMap(const BidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
869 void set(Edge e, T a) {
871 forward_map.set(e.out, a);
873 backward_map.set(e.in, a);
875 T operator[](Edge e) const {
877 return forward_map[e.out];
879 return backward_map[e.in];
881 // T get(Edge e) const {
883 // return forward_map.get(e.out);
885 // return backward_map.get(e.in);
892 /// A wrapper for composing the residual graph for directed flow and circulation problems.
894 /// A wrapper for composing the residual graph for directed flow and circulation problems.
895 template<typename Graph, typename Number,
896 typename CapacityMap, typename FlowMap>
897 class ResGraphWrapper : public GraphWrapper<Graph> {
899 const CapacityMap* capacity;
902 ResGraphWrapper() : GraphWrapper<Graph>(0),
903 capacity(0), flow(0) { }
904 void setCapacityMap(const CapacityMap& _capacity) {
907 void setFlowMap(FlowMap& _flow) {
913 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
915 GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
920 friend class OutEdgeIt;
922 typedef typename GraphWrapper<Graph>::Node Node;
923 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
924 class Edge : public Graph::Edge {
925 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
927 bool backward; //true, iff backward
928 // typename Graph::Edge e;
931 Edge(const typename Graph::Edge& _e, bool _backward) :
932 Graph::Edge(_e), backward(_backward) { }
933 Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
934 //the unique invalid iterator
935 friend bool operator==(const Edge& u, const Edge& v) {
936 return (v.backward==u.backward &&
937 static_cast<typename Graph::Edge>(u)==
938 static_cast<typename Graph::Edge>(v));
940 friend bool operator!=(const Edge& u, const Edge& v) {
941 return (v.backward!=u.backward ||
942 static_cast<typename Graph::Edge>(u)!=
943 static_cast<typename Graph::Edge>(v));
948 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
950 typename Graph::OutEdgeIt out;
951 typename Graph::InEdgeIt in;
956 // OutEdgeIt(const Edge& e) : Edge(e) { }
957 OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
958 //the unique invalid iterator
959 OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
961 _G.graph->first(out, v);
962 while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
963 if (!_G.graph->valid(out)) {
965 _G.graph->first(in, v);
966 while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
969 operator Edge() const {
971 // e.forward=this->forward;
972 // if (this->forward) e=out; else e=in;
975 return Edge(in, this->backward);
977 return Edge(out, this->backward);
982 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
984 typename Graph::OutEdgeIt out;
985 typename Graph::InEdgeIt in;
990 // OutEdgeIt(const Edge& e) : Edge(e) { }
991 InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
992 //the unique invalid iterator
993 InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
995 _G.graph->first(in, v);
996 while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
997 if (!_G.graph->valid(in)) {
999 _G.graph->first(out, v);
1000 while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
1003 operator Edge() const {
1005 // e.forward=this->forward;
1006 // if (this->forward) e=out; else e=in;
1009 return Edge(out, this->backward);
1011 return Edge(in, this->backward);
1016 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1018 typename Graph::EdgeIt e;
1022 EdgeIt(const Invalid& i) : e(i), backward(true) { }
1023 EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) {
1026 while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
1027 if (!_G.graph->valid(e)) {
1030 while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
1033 operator Edge() const {
1034 return Edge(e, this->backward);
1038 using GraphWrapper<Graph>::first;
1039 // NodeIt& first(NodeIt& i) const {
1040 // i=NodeIt(*this); return i;
1042 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1043 i=OutEdgeIt(*this, p); return i;
1046 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1047 i=InEdgeIt(*this, p); return i;
1049 EdgeIt& first(EdgeIt& i) const {
1050 i=EdgeIt(*this); return i;
1053 using GraphWrapper<Graph>::next;
1054 // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
1055 OutEdgeIt& next(OutEdgeIt& e) const {
1057 Node v=this->graph->aNode(e.out);
1058 this->graph->next(e.out);
1059 while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1060 this->graph->next(e.out); }
1061 if (!this->graph->valid(e.out)) {
1063 this->graph->first(e.in, v);
1064 while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1065 this->graph->next(e.in); }
1068 this->graph->next(e.in);
1069 while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1070 this->graph->next(e.in); }
1075 InEdgeIt& next(InEdgeIt& e) const {
1077 Node v=this->graph->aNode(e.in);
1078 this->graph->next(e.in);
1079 while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1080 this->graph->next(e.in); }
1081 if (!this->graph->valid(e.in)) {
1083 this->graph->first(e.out, v);
1084 while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1085 this->graph->next(e.out); }
1088 this->graph->next(e.out);
1089 while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1090 this->graph->next(e.out); }
1094 EdgeIt& next(EdgeIt& e) const {
1096 this->graph->next(e.e);
1097 while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1098 this->graph->next(e.e); }
1099 if (!this->graph->valid(e.e)) {
1101 this->graph->first(e.e);
1102 while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1103 this->graph->next(e.e); }
1106 this->graph->next(e.e);
1107 while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1108 this->graph->next(e.e); }
1113 Node tail(Edge e) const {
1114 return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
1115 Node head(Edge e) const {
1116 return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
1118 Node aNode(OutEdgeIt e) const {
1119 return ((!e.backward) ? this->graph->aNode(e.out) :
1120 this->graph->aNode(e.in)); }
1121 Node bNode(OutEdgeIt e) const {
1122 return ((!e.backward) ? this->graph->bNode(e.out) :
1123 this->graph->bNode(e.in)); }
1125 Node aNode(InEdgeIt e) const {
1126 return ((!e.backward) ? this->graph->aNode(e.in) :
1127 this->graph->aNode(e.out)); }
1128 Node bNode(InEdgeIt e) const {
1129 return ((!e.backward) ? this->graph->bNode(e.in) :
1130 this->graph->bNode(e.out)); }
1132 // int nodeNum() const { return graph->nodeNum(); }
1134 void edgeNum() const { }
1135 //int edgeNum() const { return graph->edgeNum(); }
1138 // int id(Node v) const { return graph->id(v); }
1140 bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
1141 bool valid(Edge e) const {
1142 return this->graph->valid(e);
1143 //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
1146 bool forward(const Edge& e) const { return !e.backward; }
1147 bool backward(const Edge& e) const { return e.backward; }
1149 void augment(const Edge& e, Number a) const {
1151 // flow->set(e.out, flow->get(e.out)+a);
1152 flow->set(e, (*flow)[e]+a);
1154 // flow->set(e.in, flow->get(e.in)-a);
1155 flow->set(e, (*flow)[e]-a);
1158 Number resCap(const Edge& e) const {
1160 // return (capacity->get(e.out)-flow->get(e.out));
1161 return ((*capacity)[e]-(*flow)[e]);
1163 // return (flow->get(e.in));
1164 return ((*flow)[e]);
1167 // Number resCap(typename Graph::OutEdgeIt out) const {
1168 // // return (capacity->get(out)-flow->get(out));
1169 // return ((*capacity)[out]-(*flow)[out]);
1172 // Number resCap(typename Graph::InEdgeIt in) const {
1173 // // return (flow->get(in));
1174 // return ((*flow)[in]);
1177 template <typename T>
1179 typename Graph::template EdgeMap<T> forward_map, backward_map;
1181 EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1182 EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1183 void set(Edge e, T a) {
1185 forward_map.set(e.out, a);
1187 backward_map.set(e.in, a);
1189 T operator[](Edge e) const {
1191 return forward_map[e.out];
1193 return backward_map[e.in];
1195 // T get(Edge e) const {
1197 // return forward_map.get(e.out);
1199 // return backward_map.get(e.in);
1206 /// ErasingFirstGraphWrapper for blocking flows.
1208 /// ErasingFirstGraphWrapper for blocking flows.
1210 ///\author Marton Makai
1211 template<typename Graph, typename FirstOutEdgesMap>
1212 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1214 FirstOutEdgesMap* first_out_edges;
1216 ErasingFirstGraphWrapper(Graph& _graph,
1217 FirstOutEdgesMap& _first_out_edges) :
1218 GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
1220 typedef typename GraphWrapper<Graph>::Node Node;
1222 // friend class GraphWrapper<Graph>;
1223 // friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1224 // typename Graph::NodeIt n;
1227 // NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
1228 // NodeIt(const Invalid& i) : n(i) { }
1229 // NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1230 // n(*(_G.graph)) { }
1231 // operator Node() const { return Node(typename Graph::Node(n)); }
1233 typedef typename GraphWrapper<Graph>::Edge Edge;
1235 friend class GraphWrapper<Graph>;
1236 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1237 // typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1238 typename Graph::OutEdgeIt e;
1241 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
1242 OutEdgeIt(const Invalid& i) : e(i) { }
1243 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1245 e((*_G.first_out_edges)[_n]) { }
1246 operator Edge() const { return Edge(typename Graph::Edge(e)); }
1249 friend class GraphWrapper<Graph>;
1250 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1251 // typedef typename Graph::InEdgeIt GraphInEdgeIt;
1252 typename Graph::InEdgeIt e;
1255 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1256 InEdgeIt(const Invalid& i) : e(i) { }
1257 InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1259 e(*(_G.graph), typename Graph::Node(_n)) { }
1260 operator Edge() const { return Edge(typename Graph::Edge(e)); }
1262 //typedef typename Graph::SymEdgeIt SymEdgeIt;
1264 friend class GraphWrapper<Graph>;
1265 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1266 // typedef typename Graph::EdgeIt GraphEdgeIt;
1267 typename Graph::EdgeIt e;
1270 EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
1271 EdgeIt(const Invalid& i) : e(i) { }
1272 EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1274 operator Edge() const { return Edge(typename Graph::Edge(e)); }
1277 using GraphWrapper<Graph>::first;
1278 // NodeIt& first(NodeIt& i) const {
1279 // i=NodeIt(*this); return i;
1281 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1282 i=OutEdgeIt(*this, p); return i;
1284 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1285 i=InEdgeIt(*this, p); return i;
1287 EdgeIt& first(EdgeIt& i) const {
1288 i=EdgeIt(*this); return i;
1291 using GraphWrapper<Graph>::next;
1292 // NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
1293 OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
1294 InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
1295 EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }
1297 Node aNode(const OutEdgeIt& e) const {
1298 return Node(this->graph->aNode(e.e)); }
1299 Node aNode(const InEdgeIt& e) const {
1300 return Node(this->graph->aNode(e.e)); }
1301 Node bNode(const OutEdgeIt& e) const {
1302 return Node(this->graph->bNode(e.e)); }
1303 Node bNode(const InEdgeIt& e) const {
1304 return Node(this->graph->bNode(e.e)); }
1306 void erase(const OutEdgeIt& e) const {
1309 first_out_edges->set(this->tail(e), f.e);
1318 #endif //HUGO_GRAPH_WRAPPER_H