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
86 template<typename Graph>
90 GraphWrapper() : graph(0) { }
91 void setGraph(Graph& _graph) { graph=&_graph; }
94 typedef Graph BaseGraph;
95 typedef Graph ParentGraph;
97 GraphWrapper(Graph& _graph) : graph(&_graph) { }
98 // Graph& getGraph() const { return *graph; }
100 // typedef typename Graph::Node Node;
101 class Node : public Graph::Node {
102 friend class GraphWrapper<Graph>;
105 Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
106 Node(const Invalid& i) : Graph::Node(i) { }
109 friend class GraphWrapper<Graph>;
110 typename Graph::NodeIt n;
113 NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
114 NodeIt(const Invalid& i) : n(i) { }
115 NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
116 operator Node() const { return Node(typename Graph::Node(n)); }
118 // typedef typename Graph::Edge Edge;
119 class Edge : public Graph::Edge {
120 friend class GraphWrapper<Graph>;
123 Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
124 Edge(const Invalid& i) : Graph::Edge(i) { }
127 friend class GraphWrapper<Graph>;
128 typename Graph::OutEdgeIt e;
131 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
132 OutEdgeIt(const Invalid& i) : e(i) { }
133 OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
134 e(*(_G.graph), typename Graph::Node(_n)) { }
135 operator Edge() const { return Edge(typename Graph::Edge(e)); }
138 friend class GraphWrapper<Graph>;
139 typename Graph::InEdgeIt e;
142 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
143 InEdgeIt(const Invalid& i) : e(i) { }
144 InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
145 e(*(_G.graph), typename Graph::Node(_n)) { }
146 operator Edge() const { return Edge(typename Graph::Edge(e)); }
148 //typedef typename Graph::SymEdgeIt SymEdgeIt;
150 friend class GraphWrapper<Graph>;
151 typename Graph::EdgeIt e;
154 EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
155 EdgeIt(const Invalid& i) : e(i) { }
156 EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
157 operator Edge() const { return Edge(typename Graph::Edge(e)); }
160 NodeIt& first(NodeIt& i) const {
161 i=NodeIt(*this); return i;
163 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
164 i=OutEdgeIt(*this, p); return i;
166 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
167 i=InEdgeIt(*this, p); return i;
169 EdgeIt& first(EdgeIt& i) const {
170 i=EdgeIt(*this); return i;
173 NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
174 OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
175 InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
176 EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
178 Node tail(const Edge& e) const {
179 return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
180 Node head(const Edge& e) const {
181 return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
183 bool valid(const Node& n) const {
184 return graph->valid(static_cast<typename Graph::Node>(n)); }
185 bool valid(const Edge& e) const {
186 return graph->valid(static_cast<typename Graph::Edge>(e)); }
188 int nodeNum() const { return graph->nodeNum(); }
189 int edgeNum() const { return graph->edgeNum(); }
191 Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
192 Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
193 Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
194 Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
196 Node addNode() const { return Node(graph->addNode()); }
197 Edge addEdge(const Node& tail, const Node& head) const {
198 return Edge(graph->addEdge(tail, head)); }
200 void erase(const Node& i) const { graph->erase(i); }
201 void erase(const Edge& i) const { graph->erase(i); }
203 void clear() const { graph->clear(); }
205 template<typename T> class NodeMap : public Graph::template NodeMap<T> {
206 typedef typename Graph::template NodeMap<T> Parent;
208 NodeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
209 NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
212 template<typename T> class EdgeMap : public Graph::template EdgeMap<T> {
213 typedef typename Graph::template EdgeMap<T> Parent;
215 EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
216 EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
222 /// A graph wrapper which reverses the orientation of the edges.
224 /// A graph wrapper which reverses the orientation of the edges.
225 /// Thus \c Graph have to be a directed graph type.
227 ///\author Marton Makai
228 template<typename Graph>
229 class RevGraphWrapper : public GraphWrapper<Graph> {
231 RevGraphWrapper() : GraphWrapper<Graph>() { }
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 /// A graph 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>(),
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]; }
469 /// This is a linear time operation and works only if
470 /// NodeIt is defined.
471 int nodeNum() const {
474 for (this->first(n); this->valid(n); this->next(n)) ++i;
478 /// This is a linear time operation and works only if
479 /// EdgeIt is defined.
480 int edgeNum() const {
483 for (this->first(e); this->valid(e); this->next(e)) ++i;
491 /// \brief A wrapper for forgetting the orientation of a graph.
493 /// A wrapper for getting an undirected graph by forgetting
494 /// the orientation of a directed one.
496 /// \author Marton Makai
497 template<typename Graph>
498 class UndirGraphWrapper : public GraphWrapper<Graph> {
500 UndirGraphWrapper() : GraphWrapper<Graph>() { }
503 typedef typename GraphWrapper<Graph>::Node Node;
504 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
505 typedef typename GraphWrapper<Graph>::Edge Edge;
506 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
508 UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
511 friend class UndirGraphWrapper<Graph>;
512 bool out_or_in; //true iff out
513 typename Graph::OutEdgeIt out;
514 typename Graph::InEdgeIt in;
517 OutEdgeIt(const Invalid& i) : Edge(i) { }
518 OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
519 out_or_in=true; _G.graph->first(out, _n);
520 if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); }
522 operator Edge() const {
523 if (out_or_in) return Edge(out); else return Edge(in);
528 typedef OutEdgeIt InEdgeIt;
530 using GraphWrapper<Graph>::first;
531 // NodeIt& first(NodeIt& i) const {
532 // i=NodeIt(*this); return i;
534 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
535 i=OutEdgeIt(*this, p); return i;
538 // InEdgeIt& first(InEdgeIt& i, const Node& p) const {
539 // i=InEdgeIt(*this, p); return i;
541 // EdgeIt& first(EdgeIt& i) const {
542 // i=EdgeIt(*this); return i;
545 using GraphWrapper<Graph>::next;
546 // NodeIt& next(NodeIt& n) const {
547 // GraphWrapper<Graph>::next(n);
550 OutEdgeIt& next(OutEdgeIt& e) const {
552 typename Graph::Node n=this->graph->tail(e.out);
553 this->graph->next(e.out);
554 if (!this->graph->valid(e.out)) {
555 e.out_or_in=false; this->graph->first(e.in, n); }
557 this->graph->next(e.in);
562 // EdgeIt& next(EdgeIt& e) const {
563 // GraphWrapper<Graph>::next(n);
564 // // graph->next(e.e);
568 Node aNode(const OutEdgeIt& e) const {
569 if (e.out_or_in) return this->graph->tail(e); else
570 return this->graph->head(e); }
571 Node bNode(const OutEdgeIt& e) const {
572 if (e.out_or_in) return this->graph->head(e); else
573 return this->graph->tail(e); }
576 /// \brief An undirected graph template.
578 /// An undirected graph template.
579 /// This class works as an undirected graph and a directed graph of
580 /// class \c Graph is used for the physical storage.
582 template<typename Graph>
583 class UndirGraph : public UndirGraphWrapper<Graph> {
584 typedef UndirGraphWrapper<Graph> Parent;
588 UndirGraph() : UndirGraphWrapper<Graph>() {
589 Parent::setGraph(gr);
594 ///\brief A wrapper for composing bidirected graph from a directed one.
595 /// experimental, for fezso's sake.
597 /// A wrapper for composing bidirected graph from a directed one.
598 /// experimental, for fezso's sake.
599 /// A bidirected graph is composed over the directed one without physical
600 /// storage. As the oppositely directed edges are logically different ones
601 /// the maps are able to attach different values for them.
602 template<typename Graph>
603 class BidirGraphWrapper : public GraphWrapper<Graph> {
605 //const CapacityMap* capacity;
608 BidirGraphWrapper() : GraphWrapper<Graph>()/*,
609 capacity(0), flow(0)*/ { }
610 // void setCapacityMap(const CapacityMap& _capacity) {
611 // capacity=&_capacity;
613 // void setFlowMap(FlowMap& _flow) {
619 BidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity,
621 GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
626 friend class OutEdgeIt;
628 //template<typename T> class NodeMap;
629 template<typename T> class EdgeMap;
631 typedef typename GraphWrapper<Graph>::Node Node;
632 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
634 class Edge : public Graph::Edge {
635 friend class BidirGraphWrapper<Graph>;
636 ///\bug ez nem is kell
637 //template<typename T> friend class NodeMap;
638 template<typename T> friend class EdgeMap;
640 bool backward; //true, iff backward
641 // typename Graph::Edge e;
644 Edge(const typename Graph::Edge& _e, bool _backward) :
645 Graph::Edge(_e), backward(_backward) { }
646 Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
647 //the unique invalid iterator
648 friend bool operator==(const Edge& u, const Edge& v) {
649 return (v.backward==u.backward &&
650 static_cast<typename Graph::Edge>(u)==
651 static_cast<typename Graph::Edge>(v));
653 friend bool operator!=(const Edge& u, const Edge& v) {
654 return (v.backward!=u.backward ||
655 static_cast<typename Graph::Edge>(u)!=
656 static_cast<typename Graph::Edge>(v));
661 friend class BidirGraphWrapper<Graph>;
663 typename Graph::OutEdgeIt out;
664 typename Graph::InEdgeIt in;
669 // OutEdgeIt(const Edge& e) : Edge(e) { }
670 OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
671 //the unique invalid iterator
672 OutEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) {
674 _G.graph->first(out, v);
675 while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
676 if (!_G.graph->valid(out)) {
678 _G.graph->first(in, v);
679 while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
682 operator Edge() const {
684 // e.forward=this->forward;
685 // if (this->forward) e=out; else e=in;
688 return Edge(in, this->backward);
690 return Edge(out, this->backward);
695 friend class BidirGraphWrapper<Graph>;
697 typename Graph::OutEdgeIt out;
698 typename Graph::InEdgeIt in;
703 // OutEdgeIt(const Edge& e) : Edge(e) { }
704 InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
705 //the unique invalid iterator
706 InEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) {
708 _G.graph->first(in, v);
709 while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
710 if (!_G.graph->valid(in)) {
712 _G.graph->first(out, v);
713 while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
716 operator Edge() const {
718 // e.forward=this->forward;
719 // if (this->forward) e=out; else e=in;
722 return Edge(out, this->backward);
724 return Edge(in, this->backward);
729 friend class BidirGraphWrapper<Graph>;
731 typename Graph::EdgeIt e;
735 EdgeIt(const Invalid& i) : e(i), backward(true) { }
736 EdgeIt(const BidirGraphWrapper<Graph>& _G) {
739 while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
740 if (!_G.graph->valid(e)) {
743 while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
746 operator Edge() const {
747 return Edge(e, this->backward);
751 using GraphWrapper<Graph>::first;
752 // NodeIt& first(NodeIt& i) const {
753 // i=NodeIt(*this); return i;
755 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
756 i=OutEdgeIt(*this, p); return i;
759 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
760 i=InEdgeIt(*this, p); return i;
762 EdgeIt& first(EdgeIt& i) const {
763 i=EdgeIt(*this); return i;
766 using GraphWrapper<Graph>::next;
767 // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
768 OutEdgeIt& next(OutEdgeIt& e) const {
770 Node v=this->graph->aNode(e.out);
771 this->graph->next(e.out);
772 while(this->graph->valid(e.out) && !enabled(e)) {
773 this->graph->next(e.out); }
774 if (!this->graph->valid(e.out)) {
776 this->graph->first(e.in, v);
777 while(this->graph->valid(e.in) && !enabled(e)) {
778 this->graph->next(e.in); }
781 this->graph->next(e.in);
782 while(this->graph->valid(e.in) && !enabled(e)) {
783 this->graph->next(e.in); }
788 InEdgeIt& next(InEdgeIt& e) const {
790 Node v=this->graph->aNode(e.in);
791 this->graph->next(e.in);
792 while(this->graph->valid(e.in) && !enabled(e)) {
793 this->graph->next(e.in); }
794 if (!this->graph->valid(e.in)) {
796 this->graph->first(e.out, v);
797 while(this->graph->valid(e.out) && !enabled(e)) {
798 this->graph->next(e.out); }
801 this->graph->next(e.out);
802 while(this->graph->valid(e.out) && !enabled(e)) {
803 this->graph->next(e.out); }
807 EdgeIt& next(EdgeIt& e) const {
809 this->graph->next(e.e);
810 while(this->graph->valid(e.e) && !enabled(e)) {
811 this->graph->next(e.e); }
812 if (!this->graph->valid(e.e)) {
814 this->graph->first(e.e);
815 while(this->graph->valid(e.e) && !enabled(e)) {
816 this->graph->next(e.e); }
819 this->graph->next(e.e);
820 while(this->graph->valid(e.e) && !enabled(e)) {
821 this->graph->next(e.e); }
826 Node tail(Edge e) const {
827 return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
828 Node head(Edge e) const {
829 return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
831 Node aNode(OutEdgeIt e) const {
832 return ((!e.backward) ? this->graph->aNode(e.out) :
833 this->graph->aNode(e.in)); }
834 Node bNode(OutEdgeIt e) const {
835 return ((!e.backward) ? this->graph->bNode(e.out) :
836 this->graph->bNode(e.in)); }
838 Node aNode(InEdgeIt e) const {
839 return ((!e.backward) ? this->graph->aNode(e.in) :
840 this->graph->aNode(e.out)); }
841 Node bNode(InEdgeIt e) const {
842 return ((!e.backward) ? this->graph->bNode(e.in) :
843 this->graph->bNode(e.out)); }
845 /// Gives back the opposite edge.
846 Edge opposite(const Edge& e) const {
848 f.backward=!f.backward;
852 // int nodeNum() const { return graph->nodeNum(); }
854 void edgeNum() const { }
855 //int edgeNum() const { return graph->edgeNum(); }
858 // int id(Node v) const { return graph->id(v); }
860 bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
861 bool valid(Edge e) const {
862 return this->graph->valid(e);
863 //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
866 bool forward(const Edge& e) const { return !e.backward; }
867 bool backward(const Edge& e) const { return e.backward; }
869 // void augment(const Edge& e, Number a) const {
871 // // flow->set(e.out, flow->get(e.out)+a);
872 // flow->set(e, (*flow)[e]+a);
874 // // flow->set(e.in, flow->get(e.in)-a);
875 // flow->set(e, (*flow)[e]-a);
878 bool enabled(const Edge& e) const {
880 // return (capacity->get(e.out)-flow->get(e.out));
881 //return ((*capacity)[e]-(*flow)[e]);
884 // return (flow->get(e.in));
885 //return ((*flow)[e]);
889 // Number enabled(typename Graph::OutEdgeIt out) const {
890 // // return (capacity->get(out)-flow->get(out));
891 // return ((*capacity)[out]-(*flow)[out]);
894 // Number enabled(typename Graph::InEdgeIt in) const {
895 // // return (flow->get(in));
896 // return ((*flow)[in]);
899 template <typename T>
901 typename Graph::template EdgeMap<T> forward_map, backward_map;
904 typedef Edge KeyType;
905 EdgeMap(const BidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
906 EdgeMap(const BidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
907 void set(Edge e, T a) {
909 forward_map.set(e/*.out*/, a);
911 backward_map.set(e/*.in*/, a);
913 T operator[](Edge e) const {
915 return forward_map[e/*.out*/];
917 return backward_map[e/*.in*/];
920 forward_map.update();
921 backward_map.update();
923 // T get(Edge e) const {
925 // return forward_map.get(e.out);
927 // return backward_map.get(e.in);
932 /// \brief A bidirected graph template.
934 /// A bidirected graph template.
935 /// Such a bidirected graph stores each pair of oppositely directed edges
936 /// ones in the memory, i.e. a directed graph of type
937 /// \c Graph is used for that.
938 /// As the oppositely directed edges are logically different ones
939 /// the maps are able to attach different values for them.
941 template<typename Graph>
942 class BidirGraph : public BidirGraphWrapper<Graph> {
943 typedef UndirGraphWrapper<Graph> Parent;
947 BidirGraph() : BidirGraphWrapper<Graph>() {
948 Parent::setGraph(gr);
953 /// A wrapper for composing the residual graph for directed flow and circulation problems.
955 /// A wrapper for composing the residual graph for directed flow and circulation problems.
956 template<typename Graph, typename Number,
957 typename CapacityMap, typename FlowMap>
958 class ResGraphWrapper : public GraphWrapper<Graph> {
960 const CapacityMap* capacity;
963 ResGraphWrapper() : GraphWrapper<Graph>(0),
964 capacity(0), flow(0) { }
965 void setCapacityMap(const CapacityMap& _capacity) {
968 void setFlowMap(FlowMap& _flow) {
974 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
976 GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
981 friend class OutEdgeIt;
983 typedef typename GraphWrapper<Graph>::Node Node;
984 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
985 class Edge : public Graph::Edge {
986 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
988 bool backward; //true, iff backward
989 // typename Graph::Edge e;
992 Edge(const typename Graph::Edge& _e, bool _backward) :
993 Graph::Edge(_e), backward(_backward) { }
994 Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
995 //the unique invalid iterator
996 friend bool operator==(const Edge& u, const Edge& v) {
997 return (v.backward==u.backward &&
998 static_cast<typename Graph::Edge>(u)==
999 static_cast<typename Graph::Edge>(v));
1001 friend bool operator!=(const Edge& u, const Edge& v) {
1002 return (v.backward!=u.backward ||
1003 static_cast<typename Graph::Edge>(u)!=
1004 static_cast<typename Graph::Edge>(v));
1009 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1011 typename Graph::OutEdgeIt out;
1012 typename Graph::InEdgeIt in;
1017 // OutEdgeIt(const Edge& e) : Edge(e) { }
1018 OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1019 //the unique invalid iterator
1020 OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
1022 _G.graph->first(out, v);
1023 while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
1024 if (!_G.graph->valid(out)) {
1026 _G.graph->first(in, v);
1027 while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
1030 operator Edge() const {
1032 // e.forward=this->forward;
1033 // if (this->forward) e=out; else e=in;
1036 return Edge(in, this->backward);
1038 return Edge(out, this->backward);
1043 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1045 typename Graph::OutEdgeIt out;
1046 typename Graph::InEdgeIt in;
1051 // OutEdgeIt(const Edge& e) : Edge(e) { }
1052 InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1053 //the unique invalid iterator
1054 InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
1056 _G.graph->first(in, v);
1057 while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
1058 if (!_G.graph->valid(in)) {
1060 _G.graph->first(out, v);
1061 while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
1064 operator Edge() const {
1066 // e.forward=this->forward;
1067 // if (this->forward) e=out; else e=in;
1070 return Edge(out, this->backward);
1072 return Edge(in, this->backward);
1077 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1079 typename Graph::EdgeIt e;
1083 EdgeIt(const Invalid& i) : e(i), backward(true) { }
1084 EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) {
1087 while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
1088 if (!_G.graph->valid(e)) {
1091 while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
1094 operator Edge() const {
1095 return Edge(e, this->backward);
1099 using GraphWrapper<Graph>::first;
1100 // NodeIt& first(NodeIt& i) const {
1101 // i=NodeIt(*this); return i;
1103 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1104 i=OutEdgeIt(*this, p); return i;
1107 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1108 i=InEdgeIt(*this, p); return i;
1110 EdgeIt& first(EdgeIt& i) const {
1111 i=EdgeIt(*this); return i;
1114 using GraphWrapper<Graph>::next;
1115 // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
1116 OutEdgeIt& next(OutEdgeIt& e) const {
1118 Node v=this->graph->aNode(e.out);
1119 this->graph->next(e.out);
1120 while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1121 this->graph->next(e.out); }
1122 if (!this->graph->valid(e.out)) {
1124 this->graph->first(e.in, v);
1125 while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1126 this->graph->next(e.in); }
1129 this->graph->next(e.in);
1130 while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1131 this->graph->next(e.in); }
1136 InEdgeIt& next(InEdgeIt& e) const {
1138 Node v=this->graph->aNode(e.in);
1139 this->graph->next(e.in);
1140 while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1141 this->graph->next(e.in); }
1142 if (!this->graph->valid(e.in)) {
1144 this->graph->first(e.out, v);
1145 while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1146 this->graph->next(e.out); }
1149 this->graph->next(e.out);
1150 while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1151 this->graph->next(e.out); }
1155 EdgeIt& next(EdgeIt& e) const {
1157 this->graph->next(e.e);
1158 while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1159 this->graph->next(e.e); }
1160 if (!this->graph->valid(e.e)) {
1162 this->graph->first(e.e);
1163 while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1164 this->graph->next(e.e); }
1167 this->graph->next(e.e);
1168 while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1169 this->graph->next(e.e); }
1174 Node tail(Edge e) const {
1175 return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
1176 Node head(Edge e) const {
1177 return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
1179 Node aNode(OutEdgeIt e) const {
1180 return ((!e.backward) ? this->graph->aNode(e.out) :
1181 this->graph->aNode(e.in)); }
1182 Node bNode(OutEdgeIt e) const {
1183 return ((!e.backward) ? this->graph->bNode(e.out) :
1184 this->graph->bNode(e.in)); }
1186 Node aNode(InEdgeIt e) const {
1187 return ((!e.backward) ? this->graph->aNode(e.in) :
1188 this->graph->aNode(e.out)); }
1189 Node bNode(InEdgeIt e) const {
1190 return ((!e.backward) ? this->graph->bNode(e.in) :
1191 this->graph->bNode(e.out)); }
1193 // int nodeNum() const { return graph->nodeNum(); }
1195 void edgeNum() const { }
1196 //int edgeNum() const { return graph->edgeNum(); }
1199 // int id(Node v) const { return graph->id(v); }
1201 bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
1202 bool valid(Edge e) const {
1203 return this->graph->valid(e);
1204 //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
1207 bool forward(const Edge& e) const { return !e.backward; }
1208 bool backward(const Edge& e) const { return e.backward; }
1210 void augment(const Edge& e, Number a) const {
1212 // flow->set(e.out, flow->get(e.out)+a);
1213 flow->set(e, (*flow)[e]+a);
1215 // flow->set(e.in, flow->get(e.in)-a);
1216 flow->set(e, (*flow)[e]-a);
1219 Number resCap(const Edge& e) const {
1221 // return (capacity->get(e.out)-flow->get(e.out));
1222 return ((*capacity)[e]-(*flow)[e]);
1224 // return (flow->get(e.in));
1225 return ((*flow)[e]);
1228 // Number resCap(typename Graph::OutEdgeIt out) const {
1229 // // return (capacity->get(out)-flow->get(out));
1230 // return ((*capacity)[out]-(*flow)[out]);
1233 // Number resCap(typename Graph::InEdgeIt in) const {
1234 // // return (flow->get(in));
1235 // return ((*flow)[in]);
1238 template <typename T>
1240 typename Graph::template EdgeMap<T> forward_map, backward_map;
1242 typedef T ValueType;
1243 typedef Edge KeyType;
1244 EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1245 EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1246 void set(Edge e, T a) {
1248 forward_map.set(e/*.out*/, a);
1250 backward_map.set(e/*.in*/, a);
1252 T operator[](Edge e) const {
1254 return forward_map[e/*.out*/];
1256 return backward_map[e/*.in*/];
1259 forward_map.update();
1260 backward_map.update();
1262 // T get(Edge e) const {
1264 // return forward_map.get(e.out);
1266 // return backward_map.get(e.in);
1273 /// For blocking flows.
1275 /// This graph wrapper is used for Dinits blocking flow computations.
1276 /// For each node, an out-edge is stored which is used when the
1278 /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1282 ///\author Marton Makai
1283 template<typename Graph, typename FirstOutEdgesMap>
1284 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1286 FirstOutEdgesMap* first_out_edges;
1288 ErasingFirstGraphWrapper(Graph& _graph,
1289 FirstOutEdgesMap& _first_out_edges) :
1290 GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
1292 typedef typename GraphWrapper<Graph>::Node Node;
1294 // friend class GraphWrapper<Graph>;
1295 // friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1296 // typename Graph::NodeIt n;
1299 // NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
1300 // NodeIt(const Invalid& i) : n(i) { }
1301 // NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1302 // n(*(_G.graph)) { }
1303 // operator Node() const { return Node(typename Graph::Node(n)); }
1305 typedef typename GraphWrapper<Graph>::Edge Edge;
1307 friend class GraphWrapper<Graph>;
1308 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1309 // typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1310 typename Graph::OutEdgeIt e;
1313 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
1314 OutEdgeIt(const Invalid& i) : e(i) { }
1315 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1317 e((*_G.first_out_edges)[_n]) { }
1318 operator Edge() const { return Edge(typename Graph::Edge(e)); }
1321 friend class GraphWrapper<Graph>;
1322 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1323 // typedef typename Graph::InEdgeIt GraphInEdgeIt;
1324 typename Graph::InEdgeIt e;
1327 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1328 InEdgeIt(const Invalid& i) : e(i) { }
1329 InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1331 e(*(_G.graph), typename Graph::Node(_n)) { }
1332 operator Edge() const { return Edge(typename Graph::Edge(e)); }
1334 //typedef typename Graph::SymEdgeIt SymEdgeIt;
1336 friend class GraphWrapper<Graph>;
1337 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1338 // typedef typename Graph::EdgeIt GraphEdgeIt;
1339 typename Graph::EdgeIt e;
1342 EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
1343 EdgeIt(const Invalid& i) : e(i) { }
1344 EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1346 operator Edge() const { return Edge(typename Graph::Edge(e)); }
1349 using GraphWrapper<Graph>::first;
1350 // NodeIt& first(NodeIt& i) const {
1351 // i=NodeIt(*this); return i;
1353 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1354 i=OutEdgeIt(*this, p); return i;
1356 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1357 i=InEdgeIt(*this, p); return i;
1359 EdgeIt& first(EdgeIt& i) const {
1360 i=EdgeIt(*this); return i;
1363 using GraphWrapper<Graph>::next;
1364 // NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
1365 OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
1366 InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
1367 EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }
1369 Node aNode(const OutEdgeIt& e) const {
1370 return Node(this->graph->aNode(e.e)); }
1371 Node aNode(const InEdgeIt& e) const {
1372 return Node(this->graph->aNode(e.e)); }
1373 Node bNode(const OutEdgeIt& e) const {
1374 return Node(this->graph->bNode(e.e)); }
1375 Node bNode(const InEdgeIt& e) const {
1376 return Node(this->graph->bNode(e.e)); }
1378 void erase(const OutEdgeIt& e) const {
1381 first_out_edges->set(this->tail(e), f.e);
1389 #endif //HUGO_GRAPH_WRAPPER_H