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>
15 //#include <iter_map.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 ///This is the base type for the Graph Wrappers.
84 ///\todo Some more docs...
86 ///\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 // /// \bug construction throughrthr multiple levels should be
108 // /// handled better
109 // Node(const typename ParentGraph::ParentGraph::Node& _n) :
110 // Graph::Node(_n) { }
111 Node(const Invalid& i) : Graph::Node(i) { }
114 friend class GraphWrapper<Graph>;
115 typename Graph::NodeIt n;
118 NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
119 NodeIt(const Invalid& i) : n(i) { }
120 NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
121 operator Node() const { return Node(typename Graph::Node(n)); }
123 // typedef typename Graph::Edge Edge;
124 class Edge : public Graph::Edge {
125 friend class GraphWrapper<Graph>;
128 Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
129 Edge(const Invalid& i) : Graph::Edge(i) { }
132 friend class GraphWrapper<Graph>;
133 typename Graph::OutEdgeIt e;
136 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
137 OutEdgeIt(const Invalid& i) : e(i) { }
138 OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
139 e(*(_G.graph), typename Graph::Node(_n)) { }
140 operator Edge() const { return Edge(typename Graph::Edge(e)); }
143 friend class GraphWrapper<Graph>;
144 typename Graph::InEdgeIt e;
147 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
148 InEdgeIt(const Invalid& i) : e(i) { }
149 InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
150 e(*(_G.graph), typename Graph::Node(_n)) { }
151 operator Edge() const { return Edge(typename Graph::Edge(e)); }
153 //typedef typename Graph::SymEdgeIt SymEdgeIt;
155 friend class GraphWrapper<Graph>;
156 typename Graph::EdgeIt e;
159 EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
160 EdgeIt(const Invalid& i) : e(i) { }
161 EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
162 operator Edge() const { return Edge(typename Graph::Edge(e)); }
165 NodeIt& first(NodeIt& i) const {
166 i=NodeIt(*this); return i;
168 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
169 i=OutEdgeIt(*this, p); return i;
171 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
172 i=InEdgeIt(*this, p); return i;
174 EdgeIt& first(EdgeIt& i) const {
175 i=EdgeIt(*this); return i;
178 NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
179 OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
180 InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
181 EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
183 Node tail(const Edge& e) const {
184 return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
185 Node head(const Edge& e) const {
186 return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
188 bool valid(const Node& n) const {
189 return graph->valid(static_cast<typename Graph::Node>(n)); }
190 bool valid(const Edge& e) const {
191 return graph->valid(static_cast<typename Graph::Edge>(e)); }
193 int nodeNum() const { return graph->nodeNum(); }
194 int edgeNum() const { return graph->edgeNum(); }
196 Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
197 Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
198 Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
199 Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
201 Node addNode() const { return Node(graph->addNode()); }
202 Edge addEdge(const Node& tail, const Node& head) const {
203 return Edge(graph->addEdge(tail, head)); }
205 void erase(const Node& i) const { graph->erase(i); }
206 void erase(const Edge& i) const { graph->erase(i); }
208 void clear() const { graph->clear(); }
210 bool forward(const Edge& e) const { return graph->forward(e); }
211 bool backward(const Edge& e) const { return graph->backward(e); }
213 Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }
215 template<typename T> class NodeMap : public Graph::template NodeMap<T> {
216 typedef typename Graph::template NodeMap<T> Parent;
218 NodeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
219 NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
222 template<typename T> class EdgeMap : public Graph::template EdgeMap<T> {
223 typedef typename Graph::template EdgeMap<T> Parent;
225 EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
226 EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
232 /// A graph wrapper which reverses the orientation of the edges.
234 /// A graph wrapper which reverses the orientation of the edges.
235 /// Thus \c Graph have to be a directed graph type.
237 ///\author Marton Makai
238 template<typename Graph>
239 class RevGraphWrapper : public GraphWrapper<Graph> {
241 typedef GraphWrapper<Graph> Parent;
243 RevGraphWrapper() : GraphWrapper<Graph>() { }
245 RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
247 typedef typename GraphWrapper<Graph>::Node Node;
248 typedef typename GraphWrapper<Graph>::Edge Edge;
249 //If Graph::OutEdgeIt is not defined
250 //and we do not want to use RevGraphWrapper::InEdgeIt,
251 //the typdef techinque does not work.
252 //Unfortunately all the typedefs are instantiated in templates.
253 //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
254 //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
257 friend class GraphWrapper<Graph>;
258 friend class RevGraphWrapper<Graph>;
259 typename Graph::InEdgeIt e;
262 OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
263 OutEdgeIt(const Invalid& i) : e(i) { }
264 OutEdgeIt(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 friend class GraphWrapper<Graph>;
270 friend class RevGraphWrapper<Graph>;
271 typename Graph::OutEdgeIt e;
274 InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
275 InEdgeIt(const Invalid& i) : e(i) { }
276 InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
277 e(*(_G.graph), typename Graph::Node(_n)) { }
278 operator Edge() const { return Edge(typename Graph::Edge(e)); }
281 using GraphWrapper<Graph>::first;
282 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
283 i=OutEdgeIt(*this, p); return i;
285 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
286 i=InEdgeIt(*this, p); return i;
289 using GraphWrapper<Graph>::next;
290 OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
291 InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
293 Node aNode(const OutEdgeIt& e) const {
294 return Node(this->graph->aNode(e.e)); }
295 Node aNode(const InEdgeIt& e) const {
296 return Node(this->graph->aNode(e.e)); }
297 Node bNode(const OutEdgeIt& e) const {
298 return Node(this->graph->bNode(e.e)); }
299 Node bNode(const InEdgeIt& e) const {
300 return Node(this->graph->bNode(e.e)); }
302 Node tail(const Edge& e) const {
303 return GraphWrapper<Graph>::head(e); }
304 Node head(const Edge& e) const {
305 return GraphWrapper<Graph>::tail(e); }
311 /// A graph wrapper for hiding nodes and edges from a graph.
313 /// This wrapper shows a graph with filtered node-set and
314 /// edge-set. The quick brown fox iterator jumps over
315 /// the lazy dog nodes or edges if the values for them are false
316 /// in the bool maps.
318 ///\author Marton Makai
319 template<typename Graph, typename NodeFilterMap,
320 typename EdgeFilterMap>
321 class SubGraphWrapper : public GraphWrapper<Graph> {
323 typedef GraphWrapper<Graph> Parent;
325 NodeFilterMap* node_filter_map;
326 EdgeFilterMap* edge_filter_map;
328 SubGraphWrapper() : GraphWrapper<Graph>(),
329 node_filter_map(0), edge_filter_map(0) { }
330 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
331 node_filter_map=&_node_filter_map;
333 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
334 edge_filter_map=&_edge_filter_map;
338 SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
339 EdgeFilterMap& _edge_filter_map) :
340 GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
341 edge_filter_map(&_edge_filter_map) { }
343 typedef typename GraphWrapper<Graph>::Node Node;
345 friend class GraphWrapper<Graph>;
346 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
347 typename Graph::NodeIt n;
350 NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
351 NodeIt(const Invalid& i) : n(i) { }
352 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
354 while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
357 operator Node() const { return Node(typename Graph::Node(n)); }
359 typedef typename GraphWrapper<Graph>::Edge Edge;
361 friend class GraphWrapper<Graph>;
362 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
363 typename Graph::OutEdgeIt e;
366 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
367 OutEdgeIt(const Invalid& i) : e(i) { }
368 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
370 e(*(_G.graph), typename Graph::Node(_n)) {
371 while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
374 operator Edge() const { return Edge(typename Graph::Edge(e)); }
377 friend class GraphWrapper<Graph>;
378 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
379 typename Graph::InEdgeIt e;
382 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
383 InEdgeIt(const Invalid& i) : e(i) { }
384 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
386 e(*(_G.graph), typename Graph::Node(_n)) {
387 while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
390 operator Edge() const { return Edge(typename Graph::Edge(e)); }
392 //typedef typename Graph::SymEdgeIt SymEdgeIt;
394 friend class GraphWrapper<Graph>;
395 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
396 typename Graph::EdgeIt e;
399 EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
400 EdgeIt(const Invalid& i) : e(i) { }
401 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
403 while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
406 operator Edge() const { return Edge(typename Graph::Edge(e)); }
409 NodeIt& first(NodeIt& i) const {
410 i=NodeIt(*this); return i;
412 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
413 i=OutEdgeIt(*this, p); return i;
415 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
416 i=InEdgeIt(*this, p); return i;
418 EdgeIt& first(EdgeIt& i) const {
419 i=EdgeIt(*this); return i;
422 NodeIt& next(NodeIt& i) const {
423 this->graph->next(i.n);
424 while (this->graph->valid(i) && !(*node_filter_map)[i.n]) {
425 this->graph->next(i.n); }
428 OutEdgeIt& next(OutEdgeIt& i) const {
429 this->graph->next(i.e);
430 while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
431 this->graph->next(i.e); }
434 InEdgeIt& next(InEdgeIt& i) const {
435 this->graph->next(i.e);
436 while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
437 this->graph->next(i.e); }
440 EdgeIt& next(EdgeIt& i) const {
441 this->graph->next(i.e);
442 while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
443 this->graph->next(i.e); }
447 Node aNode(const OutEdgeIt& e) const {
448 return Node(this->graph->aNode(e.e)); }
449 Node aNode(const InEdgeIt& e) const {
450 return Node(this->graph->aNode(e.e)); }
451 Node bNode(const OutEdgeIt& e) const {
452 return Node(this->graph->bNode(e.e)); }
453 Node bNode(const InEdgeIt& e) const {
454 return Node(this->graph->bNode(e.e)); }
456 /// This function hides \c n in the graph, i.e. the iteration
457 /// jumps over it. This is done by simply setting the value of \c n
458 /// to be false in the corresponding node-map.
459 void hide(const Node& n) const { node_filter_map->set(n, false); }
461 /// This function hides \c e in the graph, i.e. the iteration
462 /// jumps over it. This is done by simply setting the value of \c e
463 /// to be false in the corresponding edge-map.
464 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
466 /// The value of \c n is set to be true in the node-map which stores
467 /// hide information. If \c n was hidden previuosly, then it is shown
469 void unHide(const Node& n) const { node_filter_map->set(n, true); }
471 /// The value of \c e is set to be true in the edge-map which stores
472 /// hide information. If \c e was hidden previuosly, then it is shown
474 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
476 /// Returns true if \c n is hidden.
477 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
479 /// Returns true if \c n is hidden.
480 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
482 /// This is a linear time operation and works only if
483 /// NodeIt is defined.
484 int nodeNum() const {
487 for (this->first(n); this->valid(n); this->next(n)) ++i;
491 /// This is a linear time operation and works only if
492 /// EdgeIt is defined.
493 int edgeNum() const {
496 for (this->first(e); this->valid(e); this->next(e)) ++i;
504 /// \brief A wrapper for forgetting the orientation of a graph.
506 /// A wrapper for getting an undirected graph by forgetting
507 /// the orientation of a directed one.
509 /// \author Marton Makai
510 template<typename Graph>
511 class UndirGraphWrapper : public GraphWrapper<Graph> {
513 typedef GraphWrapper<Graph> Parent;
515 UndirGraphWrapper() : GraphWrapper<Graph>() { }
518 typedef typename GraphWrapper<Graph>::Node Node;
519 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
520 typedef typename GraphWrapper<Graph>::Edge Edge;
521 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
523 UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
526 friend class UndirGraphWrapper<Graph>;
527 bool out_or_in; //true iff out
528 typename Graph::OutEdgeIt out;
529 typename Graph::InEdgeIt in;
532 OutEdgeIt(const Invalid& i) : Edge(i) { }
533 OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
534 out_or_in=true; _G.graph->first(out, _n);
535 if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); }
537 operator Edge() const {
538 if (out_or_in) return Edge(out); else return Edge(in);
543 typedef OutEdgeIt InEdgeIt;
545 using GraphWrapper<Graph>::first;
546 // NodeIt& first(NodeIt& i) const {
547 // i=NodeIt(*this); return i;
549 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
550 i=OutEdgeIt(*this, p); return i;
553 // InEdgeIt& first(InEdgeIt& i, const Node& p) const {
554 // i=InEdgeIt(*this, p); return i;
556 // EdgeIt& first(EdgeIt& i) const {
557 // i=EdgeIt(*this); return i;
560 using GraphWrapper<Graph>::next;
561 // NodeIt& next(NodeIt& n) const {
562 // GraphWrapper<Graph>::next(n);
565 OutEdgeIt& next(OutEdgeIt& e) const {
567 typename Graph::Node n=this->graph->tail(e.out);
568 this->graph->next(e.out);
569 if (!this->graph->valid(e.out)) {
570 e.out_or_in=false; this->graph->first(e.in, n); }
572 this->graph->next(e.in);
577 // EdgeIt& next(EdgeIt& e) const {
578 // GraphWrapper<Graph>::next(n);
579 // // graph->next(e.e);
583 Node aNode(const OutEdgeIt& e) const {
584 if (e.out_or_in) return this->graph->tail(e); else
585 return this->graph->head(e); }
586 Node bNode(const OutEdgeIt& e) const {
587 if (e.out_or_in) return this->graph->head(e); else
588 return this->graph->tail(e); }
591 /// \brief An undirected graph template.
593 /// An undirected graph template.
594 /// This class works as an undirected graph and a directed graph of
595 /// class \c Graph is used for the physical storage.
597 template<typename Graph>
598 class UndirGraph : public UndirGraphWrapper<Graph> {
599 typedef UndirGraphWrapper<Graph> Parent;
603 UndirGraph() : UndirGraphWrapper<Graph>() {
604 Parent::setGraph(gr);
610 ///\brief A wrapper for composing a subgraph of a
611 /// bidirected graph composed from a directed one.
612 /// experimental, for fezso's sake.
614 /// A wrapper for composing a subgraps of a
615 /// bidirected graph composed from a directed one.
616 /// experimental, for fezso's sake.
617 /// A bidirected graph is composed over the directed one without physical
618 /// storage. As the oppositely directed edges are logically different ones
619 /// the maps are able to attach different values for them.
620 template<typename Graph,
621 typename ForwardFilterMap, typename BackwardFilterMap>
622 class SubBidirGraphWrapper : public GraphWrapper<Graph> {
624 typedef GraphWrapper<Graph> Parent;
626 //const CapacityMap* capacity;
629 ForwardFilterMap* forward_filter;
630 BackwardFilterMap* backward_filter;
632 SubBidirGraphWrapper() : GraphWrapper<Graph>()/*,
633 capacity(0), flow(0)*/ { }
634 void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
635 forward_filter=&_forward_filter;
637 void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
638 backward_filter=&_backward_filter;
643 SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter,
644 BackwardFilterMap& _backward_filter) :
645 GraphWrapper<Graph>(_graph),
646 forward_filter(&_forward_filter), backward_filter(&_backward_filter) { }
651 friend class OutEdgeIt;
653 //template<typename T> class NodeMap;
654 template<typename T> class EdgeMap;
656 typedef typename GraphWrapper<Graph>::Node Node;
657 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
659 class Edge : public Graph::Edge {
660 friend class SubBidirGraphWrapper<Graph,
661 ForwardFilterMap, BackwardFilterMap>;
662 ///\bug ez nem is kell
663 //template<typename T> friend class NodeMap;
664 template<typename T> friend class EdgeMap;
666 bool backward; //true, iff backward
667 // typename Graph::Edge e;
670 ///\bug =false kell-e? zsoltnak kell az addEdge miatt
671 Edge(const typename Graph::Edge& _e, bool _backward=false) :
672 Graph::Edge(_e), backward(_backward) { }
673 Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
674 //the unique invalid iterator
675 friend bool operator==(const Edge& u, const Edge& v) {
676 return (v.backward==u.backward &&
677 static_cast<typename Graph::Edge>(u)==
678 static_cast<typename Graph::Edge>(v));
680 friend bool operator!=(const Edge& u, const Edge& v) {
681 return (v.backward!=u.backward ||
682 static_cast<typename Graph::Edge>(u)!=
683 static_cast<typename Graph::Edge>(v));
688 friend class SubBidirGraphWrapper<Graph,
689 ForwardFilterMap, BackwardFilterMap>;
691 typename Graph::OutEdgeIt out;
692 typename Graph::InEdgeIt in;
697 // OutEdgeIt(const Edge& e) : Edge(e) { }
698 OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
699 //the unique invalid iterator
700 OutEdgeIt(const SubBidirGraphWrapper<Graph,
701 ForwardFilterMap, BackwardFilterMap>& _G, Node v) {
703 _G.graph->first(out, v);
704 while(_G.graph->valid(out) && !(*_G.forward_filter)[*this]) { _G.graph->next(out); }
705 if (!_G.graph->valid(out)) {
707 _G.graph->first(in, v);
708 while(_G.graph->valid(in) && !(*_G.backward_filter)[*this]) { _G.graph->next(in); }
711 operator Edge() const {
713 // e.forward=this->forward;
714 // if (this->forward) e=out; else e=in;
717 return Edge(in, this->backward);
719 return Edge(out, this->backward);
724 friend class SubBidirGraphWrapper<Graph,
725 ForwardFilterMap, BackwardFilterMap>;
727 typename Graph::OutEdgeIt out;
728 typename Graph::InEdgeIt in;
733 // OutEdgeIt(const Edge& e) : Edge(e) { }
734 InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
735 //the unique invalid iterator
736 InEdgeIt(const SubBidirGraphWrapper<Graph,
737 ForwardFilterMap, BackwardFilterMap>& _G, Node v) {
739 _G.graph->first(in, v);
740 while(_G.graph->valid(in) && !(*_G.forward_filter)[*this]) { _G.graph->next(in); }
741 if (!_G.graph->valid(in)) {
743 _G.graph->first(out, v);
744 while(_G.graph->valid(out) && !(*_G.backward_filter)[*this]) { _G.graph->next(out); }
747 operator Edge() const {
749 // e.forward=this->forward;
750 // if (this->forward) e=out; else e=in;
753 return Edge(out, this->backward);
755 return Edge(in, this->backward);
760 friend class SubBidirGraphWrapper<Graph,
761 ForwardFilterMap, BackwardFilterMap>;
763 typename Graph::EdgeIt e;
767 EdgeIt(const Invalid& i) : e(i), backward(true) { }
768 EdgeIt(const SubBidirGraphWrapper<Graph,
769 ForwardFilterMap, BackwardFilterMap>& _G) {
772 while (_G.graph->valid(e) && !(*_G.forward_filter)[*this]) _G.graph->next(e);
773 if (!_G.graph->valid(e)) {
776 while (_G.graph->valid(e) && !(*_G.backward_filter)[*this]) _G.graph->next(e);
779 operator Edge() const {
780 return Edge(e, this->backward);
784 using GraphWrapper<Graph>::first;
785 // NodeIt& first(NodeIt& i) const {
786 // i=NodeIt(*this); return i;
788 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
789 i=OutEdgeIt(*this, p); return i;
792 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
793 i=InEdgeIt(*this, p); return i;
795 EdgeIt& first(EdgeIt& i) const {
796 i=EdgeIt(*this); return i;
799 using GraphWrapper<Graph>::next;
800 // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
801 OutEdgeIt& next(OutEdgeIt& e) const {
803 Node v=this->graph->aNode(e.out);
804 this->graph->next(e.out);
805 while(this->graph->valid(e.out) && !(*forward_filter)[e]) {
806 this->graph->next(e.out); }
807 if (!this->graph->valid(e.out)) {
809 this->graph->first(e.in, v);
810 while(this->graph->valid(e.in) && !(*backward_filter)[e]) {
811 this->graph->next(e.in); }
814 this->graph->next(e.in);
815 while(this->graph->valid(e.in) && !(*backward_filter)[e]) {
816 this->graph->next(e.in); }
821 InEdgeIt& next(InEdgeIt& e) const {
823 Node v=this->graph->aNode(e.in);
824 this->graph->next(e.in);
825 while(this->graph->valid(e.in) && !(*forward_filter)[e]) {
826 this->graph->next(e.in); }
827 if (!this->graph->valid(e.in)) {
829 this->graph->first(e.out, v);
830 while(this->graph->valid(e.out) && !(*backward_filter)[e]) {
831 this->graph->next(e.out); }
834 this->graph->next(e.out);
835 while(this->graph->valid(e.out) && !(*backward_filter)[e]) {
836 this->graph->next(e.out); }
840 EdgeIt& next(EdgeIt& e) const {
842 this->graph->next(e.e);
843 while(this->graph->valid(e.e) && !(*forward_filter)[e]) {
844 this->graph->next(e.e); }
845 if (!this->graph->valid(e.e)) {
847 this->graph->first(e.e);
848 while(this->graph->valid(e.e) && !(*backward_filter)[e]) {
849 this->graph->next(e.e); }
852 this->graph->next(e.e);
853 while(this->graph->valid(e.e) && !(*backward_filter)[e]) {
854 this->graph->next(e.e); }
859 Node tail(Edge e) const {
860 return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
861 Node head(Edge e) const {
862 return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
864 Node aNode(OutEdgeIt e) const {
865 return ((!e.backward) ? this->graph->aNode(e.out) :
866 this->graph->aNode(e.in)); }
867 Node bNode(OutEdgeIt e) const {
868 return ((!e.backward) ? this->graph->bNode(e.out) :
869 this->graph->bNode(e.in)); }
871 Node aNode(InEdgeIt e) const {
872 return ((!e.backward) ? this->graph->aNode(e.in) :
873 this->graph->aNode(e.out)); }
874 Node bNode(InEdgeIt e) const {
875 return ((!e.backward) ? this->graph->bNode(e.in) :
876 this->graph->bNode(e.out)); }
878 /// Gives back the opposite edge.
879 Edge opposite(const Edge& e) const {
881 f.backward=!f.backward;
885 // int nodeNum() const { return graph->nodeNum(); }
887 void edgeNum() const { }
888 //int edgeNum() const { return graph->edgeNum(); }
891 // int id(Node v) const { return graph->id(v); }
893 bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
894 bool valid(Edge e) const {
895 return this->graph->valid(e);
896 //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
899 bool forward(const Edge& e) const { return !e.backward; }
900 bool backward(const Edge& e) const { return e.backward; }
902 // void augment(const Edge& e, Number a) const {
904 // // flow->set(e.out, flow->get(e.out)+a);
905 // flow->set(e, (*flow)[e]+a);
907 // // flow->set(e.in, flow->get(e.in)-a);
908 // flow->set(e, (*flow)[e]-a);
911 // bool enabled(const Edge& e) const {
913 // // return (capacity->get(e.out)-flow->get(e.out));
914 // //return ((*capacity)[e]-(*flow)[e]);
917 // // return (flow->get(e.in));
918 // //return ((*flow)[e]);
922 // Number enabled(typename Graph::OutEdgeIt out) const {
923 // // return (capacity->get(out)-flow->get(out));
924 // return ((*capacity)[out]-(*flow)[out]);
927 // Number enabled(typename Graph::InEdgeIt in) const {
928 // // return (flow->get(in));
929 // return ((*flow)[in]);
932 template <typename T>
934 typename Graph::template EdgeMap<T> forward_map, backward_map;
937 typedef Edge KeyType;
938 EdgeMap(const SubBidirGraphWrapper<Graph,
939 ForwardFilterMap, BackwardFilterMap>& _G) :
940 forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
941 EdgeMap(const SubBidirGraphWrapper<Graph,
942 ForwardFilterMap, BackwardFilterMap>& _G, T a) :
943 forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
944 void set(Edge e, T a) {
946 forward_map.set(e/*.out*/, a);
948 backward_map.set(e/*.in*/, a);
950 T operator[](Edge e) const {
952 return forward_map[e/*.out*/];
954 return backward_map[e/*.in*/];
957 forward_map.update();
958 backward_map.update();
960 // T get(Edge e) const {
962 // return forward_map.get(e.out);
964 // return backward_map.get(e.in);
971 ///\brief A wrapper for composing bidirected graph from a directed one.
972 /// experimental, for fezso's sake.
974 /// A wrapper for composing bidirected graph from a directed one.
975 /// experimental, for fezso's sake.
976 /// A bidirected graph is composed over the directed one without physical
977 /// storage. As the oppositely directed edges are logically different ones
978 /// the maps are able to attach different values for them.
979 template<typename Graph>
980 class BidirGraphWrapper :
981 public SubBidirGraphWrapper<
983 ConstMap<typename Graph::Edge, bool>,
984 ConstMap<typename Graph::Edge, bool> > {
986 typedef SubBidirGraphWrapper<
988 ConstMap<typename Graph::Edge, bool>,
989 ConstMap<typename Graph::Edge, bool> > Parent;
991 ConstMap<typename Graph::Edge, bool> cm;
992 //const CapacityMap* capacity;
995 BidirGraphWrapper() : Parent(), cm(true) {
996 Parent::setForwardFilterMap(cm);
997 Parent::setBackwardFilterMap(cm);
999 // void setCapacityMap(const CapacityMap& _capacity) {
1000 // capacity=&_capacity;
1002 // void setFlowMap(FlowMap& _flow) {
1008 BidirGraphWrapper(Graph& _graph) : Parent() {
1009 Parent::setGraph(_graph);
1010 Parent::setForwardFilterMap(cm);
1011 Parent::setBackwardFilterMap(cm);
1014 int edgeNum() const {
1015 return 2*this->graph->edgeNum();
1022 template<typename Graph>
1023 class OldBidirGraphWrapper : public GraphWrapper<Graph> {
1025 typedef GraphWrapper<Graph> Parent;
1027 //const CapacityMap* capacity;
1030 OldBidirGraphWrapper() : GraphWrapper<Graph>()/*,
1031 capacity(0), flow(0)*/ { }
1032 // void setCapacityMap(const CapacityMap& _capacity) {
1033 // capacity=&_capacity;
1035 // void setFlowMap(FlowMap& _flow) {
1041 OldBidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity,
1043 GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
1048 friend class OutEdgeIt;
1050 //template<typename T> class NodeMap;
1051 template<typename T> class EdgeMap;
1053 typedef typename GraphWrapper<Graph>::Node Node;
1054 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1056 class Edge : public Graph::Edge {
1057 friend class OldBidirGraphWrapper<Graph>;
1058 ///\bug ez nem is kell
1059 //template<typename T> friend class NodeMap;
1060 template<typename T> friend class EdgeMap;
1062 bool backward; //true, iff backward
1063 // typename Graph::Edge e;
1066 ///\bug =false kell-e? zsoltnak kell az addEdge miatt
1067 Edge(const typename Graph::Edge& _e, bool _backward=false) :
1068 Graph::Edge(_e), backward(_backward) { }
1069 Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
1070 //the unique invalid iterator
1071 friend bool operator==(const Edge& u, const Edge& v) {
1072 return (v.backward==u.backward &&
1073 static_cast<typename Graph::Edge>(u)==
1074 static_cast<typename Graph::Edge>(v));
1076 friend bool operator!=(const Edge& u, const Edge& v) {
1077 return (v.backward!=u.backward ||
1078 static_cast<typename Graph::Edge>(u)!=
1079 static_cast<typename Graph::Edge>(v));
1084 friend class OldBidirGraphWrapper<Graph>;
1086 typename Graph::OutEdgeIt out;
1087 typename Graph::InEdgeIt in;
1092 // OutEdgeIt(const Edge& e) : Edge(e) { }
1093 OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1094 //the unique invalid iterator
1095 OutEdgeIt(const OldBidirGraphWrapper<Graph>& _G, Node v) {
1097 _G.graph->first(out, v);
1098 while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
1099 if (!_G.graph->valid(out)) {
1101 _G.graph->first(in, v);
1102 while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
1105 operator Edge() const {
1107 // e.forward=this->forward;
1108 // if (this->forward) e=out; else e=in;
1111 return Edge(in, this->backward);
1113 return Edge(out, this->backward);
1118 friend class OldBidirGraphWrapper<Graph>;
1120 typename Graph::OutEdgeIt out;
1121 typename Graph::InEdgeIt in;
1126 // OutEdgeIt(const Edge& e) : Edge(e) { }
1127 InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1128 //the unique invalid iterator
1129 InEdgeIt(const OldBidirGraphWrapper<Graph>& _G, Node v) {
1131 _G.graph->first(in, v);
1132 while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
1133 if (!_G.graph->valid(in)) {
1135 _G.graph->first(out, v);
1136 while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
1139 operator Edge() const {
1141 // e.forward=this->forward;
1142 // if (this->forward) e=out; else e=in;
1145 return Edge(out, this->backward);
1147 return Edge(in, this->backward);
1152 friend class OldBidirGraphWrapper<Graph>;
1154 typename Graph::EdgeIt e;
1158 EdgeIt(const Invalid& i) : e(i), backward(true) { }
1159 EdgeIt(const OldBidirGraphWrapper<Graph>& _G) {
1162 while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
1163 if (!_G.graph->valid(e)) {
1166 while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
1169 operator Edge() const {
1170 return Edge(e, this->backward);
1174 using GraphWrapper<Graph>::first;
1175 // NodeIt& first(NodeIt& i) const {
1176 // i=NodeIt(*this); return i;
1178 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1179 i=OutEdgeIt(*this, p); return i;
1182 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1183 i=InEdgeIt(*this, p); return i;
1185 EdgeIt& first(EdgeIt& i) const {
1186 i=EdgeIt(*this); return i;
1189 using GraphWrapper<Graph>::next;
1190 // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
1191 OutEdgeIt& next(OutEdgeIt& e) const {
1193 Node v=this->graph->aNode(e.out);
1194 this->graph->next(e.out);
1195 while(this->graph->valid(e.out) && !enabled(e)) {
1196 this->graph->next(e.out); }
1197 if (!this->graph->valid(e.out)) {
1199 this->graph->first(e.in, v);
1200 while(this->graph->valid(e.in) && !enabled(e)) {
1201 this->graph->next(e.in); }
1204 this->graph->next(e.in);
1205 while(this->graph->valid(e.in) && !enabled(e)) {
1206 this->graph->next(e.in); }
1211 InEdgeIt& next(InEdgeIt& e) const {
1213 Node v=this->graph->aNode(e.in);
1214 this->graph->next(e.in);
1215 while(this->graph->valid(e.in) && !enabled(e)) {
1216 this->graph->next(e.in); }
1217 if (!this->graph->valid(e.in)) {
1219 this->graph->first(e.out, v);
1220 while(this->graph->valid(e.out) && !enabled(e)) {
1221 this->graph->next(e.out); }
1224 this->graph->next(e.out);
1225 while(this->graph->valid(e.out) && !enabled(e)) {
1226 this->graph->next(e.out); }
1230 EdgeIt& next(EdgeIt& e) const {
1232 this->graph->next(e.e);
1233 while(this->graph->valid(e.e) && !enabled(e)) {
1234 this->graph->next(e.e); }
1235 if (!this->graph->valid(e.e)) {
1237 this->graph->first(e.e);
1238 while(this->graph->valid(e.e) && !enabled(e)) {
1239 this->graph->next(e.e); }
1242 this->graph->next(e.e);
1243 while(this->graph->valid(e.e) && !enabled(e)) {
1244 this->graph->next(e.e); }
1249 Node tail(Edge e) const {
1250 return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
1251 Node head(Edge e) const {
1252 return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
1254 Node aNode(OutEdgeIt e) const {
1255 return ((!e.backward) ? this->graph->aNode(e.out) :
1256 this->graph->aNode(e.in)); }
1257 Node bNode(OutEdgeIt e) const {
1258 return ((!e.backward) ? this->graph->bNode(e.out) :
1259 this->graph->bNode(e.in)); }
1261 Node aNode(InEdgeIt e) const {
1262 return ((!e.backward) ? this->graph->aNode(e.in) :
1263 this->graph->aNode(e.out)); }
1264 Node bNode(InEdgeIt e) const {
1265 return ((!e.backward) ? this->graph->bNode(e.in) :
1266 this->graph->bNode(e.out)); }
1268 /// Gives back the opposite edge.
1269 Edge opposite(const Edge& e) const {
1271 f.backward=!f.backward;
1275 // int nodeNum() const { return graph->nodeNum(); }
1277 void edgeNum() const { }
1278 //int edgeNum() const { return graph->edgeNum(); }
1281 // int id(Node v) const { return graph->id(v); }
1283 bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
1284 bool valid(Edge e) const {
1285 return this->graph->valid(e);
1286 //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
1289 bool forward(const Edge& e) const { return !e.backward; }
1290 bool backward(const Edge& e) const { return e.backward; }
1292 // void augment(const Edge& e, Number a) const {
1294 // // flow->set(e.out, flow->get(e.out)+a);
1295 // flow->set(e, (*flow)[e]+a);
1297 // // flow->set(e.in, flow->get(e.in)-a);
1298 // flow->set(e, (*flow)[e]-a);
1301 bool enabled(const Edge& e) const {
1303 // return (capacity->get(e.out)-flow->get(e.out));
1304 //return ((*capacity)[e]-(*flow)[e]);
1307 // return (flow->get(e.in));
1308 //return ((*flow)[e]);
1312 // Number enabled(typename Graph::OutEdgeIt out) const {
1313 // // return (capacity->get(out)-flow->get(out));
1314 // return ((*capacity)[out]-(*flow)[out]);
1317 // Number enabled(typename Graph::InEdgeIt in) const {
1318 // // return (flow->get(in));
1319 // return ((*flow)[in]);
1322 template <typename T>
1324 typename Graph::template EdgeMap<T> forward_map, backward_map;
1326 typedef T ValueType;
1327 typedef Edge KeyType;
1328 EdgeMap(const OldBidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1329 EdgeMap(const OldBidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1330 void set(Edge e, T a) {
1332 forward_map.set(e/*.out*/, a);
1334 backward_map.set(e/*.in*/, a);
1336 T operator[](Edge e) const {
1338 return forward_map[e/*.out*/];
1340 return backward_map[e/*.in*/];
1343 forward_map.update();
1344 backward_map.update();
1346 // T get(Edge e) const {
1348 // return forward_map.get(e.out);
1350 // return backward_map.get(e.in);
1357 /// \brief A bidirected graph template.
1359 /// A bidirected graph template.
1360 /// Such a bidirected graph stores each pair of oppositely directed edges
1361 /// ones in the memory, i.e. a directed graph of type
1362 /// \c Graph is used for that.
1363 /// As the oppositely directed edges are logically different ones
1364 /// the maps are able to attach different values for them.
1366 template<typename Graph>
1367 class BidirGraph : public BidirGraphWrapper<Graph> {
1369 typedef UndirGraphWrapper<Graph> Parent;
1373 BidirGraph() : BidirGraphWrapper<Graph>() {
1374 Parent::setGraph(gr);
1380 template<typename Graph, typename Number,
1381 typename CapacityMap, typename FlowMap>
1382 class ResForwardFilter {
1383 // const Graph* graph;
1384 const CapacityMap* capacity;
1385 const FlowMap* flow;
1387 ResForwardFilter(/*const Graph& _graph, */
1388 const CapacityMap& _capacity, const FlowMap& _flow) :
1389 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1390 ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1391 //void setGraph(const Graph& _graph) { graph=&_graph; }
1392 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1393 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1394 bool operator[](const typename Graph::Edge& e) const {
1395 return (Number((*flow)[e]) < Number((*capacity)[e]));
1399 template<typename Graph, typename Number,
1400 typename CapacityMap, typename FlowMap>
1401 class ResBackwardFilter {
1402 //const Graph* graph;
1403 const CapacityMap* capacity;
1404 const FlowMap* flow;
1406 ResBackwardFilter(/*const Graph& _graph,*/
1407 const CapacityMap& _capacity, const FlowMap& _flow) :
1408 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1409 ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1410 //void setGraph(const Graph& _graph) { graph=&_graph; }
1411 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1412 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1413 bool operator[](const typename Graph::Edge& e) const {
1414 return (Number(0) < Number((*flow)[e]));
1419 /// A wrapper for composing the residual graph for directed flow and circulation problems.
1421 /// A wrapper for composing the residual graph for directed flow and circulation problems.
1422 template<typename Graph, typename Number,
1423 typename CapacityMap, typename FlowMap>
1424 class ResGraphWrapper :
1425 public SubBidirGraphWrapper<
1427 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1428 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1430 typedef SubBidirGraphWrapper<
1432 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1433 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1435 const CapacityMap* capacity;
1437 ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1438 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1439 ResGraphWrapper() : Parent(),
1440 capacity(0), flow(0) { }
1441 void setCapacityMap(const CapacityMap& _capacity) {
1442 capacity=&_capacity;
1443 forward_filter.setCapacity(_capacity);
1444 backward_filter.setCapacity(_capacity);
1446 void setFlowMap(FlowMap& _flow) {
1448 forward_filter.setFlow(_flow);
1449 backward_filter.setFlow(_flow);
1451 // /// \bug does graph reference needed in filtermaps??
1452 // void setGraph(const Graph& _graph) {
1453 // Parent::setGraph(_graph);
1454 // forward_filter.setGraph(_graph);
1455 // backward_filter.setGraph(_graph);
1458 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1460 Parent(), capacity(&_capacity), flow(&_flow),
1461 forward_filter(/*_graph,*/ _capacity, _flow),
1462 backward_filter(/*_graph,*/ _capacity, _flow) {
1463 Parent::setGraph(_graph);
1464 Parent::setForwardFilterMap(forward_filter);
1465 Parent::setBackwardFilterMap(backward_filter);
1468 typedef typename Parent::Edge Edge;
1470 // bool forward(const Parent::Edge& e) const { return Parent::forward(e); }
1471 //bool backward(const Edge& e) const { return e.backward; }
1473 void augment(const Edge& e, Number a) const {
1474 if (Parent::forward(e))
1475 // flow->set(e.out, flow->get(e.out)+a);
1476 flow->set(e, (*flow)[e]+a);
1478 //flow->set(e.in, flow->get(e.in)-a);
1479 flow->set(e, (*flow)[e]-a);
1484 Number resCap(const Edge& e) const {
1485 if (Parent::forward(e))
1486 // return (capacity->get(e.out)-flow->get(e.out));
1487 return ((*capacity)[e]-(*flow)[e]);
1489 // return (flow->get(e.in));
1490 return ((*flow)[e]);
1493 /// \brief Residual capacity map.
1495 /// In generic residual graphs the residual capacity can be obtained as a map.
1498 const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
1500 typedef Number ValueType;
1501 typedef Edge KeyType;
1502 ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _res_graph) :
1503 res_graph(&_res_graph) { }
1504 Number operator[](const Edge& e) const {
1505 if (res_graph->forward(e))
1506 // return (capacity->get(e.out)-flow->get(e.out));
1507 return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1509 // return (flow->get(e.in));
1510 return (*(res_graph->flow))[e];
1512 /// \bug not needed with dynamic maps, or does it?
1519 template<typename Graph, typename Number,
1520 typename CapacityMap, typename FlowMap>
1521 class OldResGraphWrapper : public GraphWrapper<Graph> {
1523 typedef GraphWrapper<Graph> Parent;
1525 const CapacityMap* capacity;
1528 OldResGraphWrapper() : GraphWrapper<Graph>(0),
1529 capacity(0), flow(0) { }
1530 void setCapacityMap(const CapacityMap& _capacity) {
1531 capacity=&_capacity;
1533 void setFlowMap(FlowMap& _flow) {
1539 OldResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1541 GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
1546 friend class OutEdgeIt;
1548 typedef typename GraphWrapper<Graph>::Node Node;
1549 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1550 class Edge : public Graph::Edge {
1551 friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1553 bool backward; //true, iff backward
1554 // typename Graph::Edge e;
1557 Edge(const typename Graph::Edge& _e, bool _backward) :
1558 Graph::Edge(_e), backward(_backward) { }
1559 Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
1560 //the unique invalid iterator
1561 friend bool operator==(const Edge& u, const Edge& v) {
1562 return (v.backward==u.backward &&
1563 static_cast<typename Graph::Edge>(u)==
1564 static_cast<typename Graph::Edge>(v));
1566 friend bool operator!=(const Edge& u, const Edge& v) {
1567 return (v.backward!=u.backward ||
1568 static_cast<typename Graph::Edge>(u)!=
1569 static_cast<typename Graph::Edge>(v));
1574 friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1576 typename Graph::OutEdgeIt out;
1577 typename Graph::InEdgeIt in;
1582 // OutEdgeIt(const Edge& e) : Edge(e) { }
1583 OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1584 //the unique invalid iterator
1585 OutEdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
1587 _G.graph->first(out, v);
1588 while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
1589 if (!_G.graph->valid(out)) {
1591 _G.graph->first(in, v);
1592 while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
1595 operator Edge() const {
1597 // e.forward=this->forward;
1598 // if (this->forward) e=out; else e=in;
1601 return Edge(in, this->backward);
1603 return Edge(out, this->backward);
1608 friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1610 typename Graph::OutEdgeIt out;
1611 typename Graph::InEdgeIt in;
1616 // OutEdgeIt(const Edge& e) : Edge(e) { }
1617 InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1618 //the unique invalid iterator
1619 InEdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
1621 _G.graph->first(in, v);
1622 while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
1623 if (!_G.graph->valid(in)) {
1625 _G.graph->first(out, v);
1626 while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
1629 operator Edge() const {
1631 // e.forward=this->forward;
1632 // if (this->forward) e=out; else e=in;
1635 return Edge(out, this->backward);
1637 return Edge(in, this->backward);
1642 friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1644 typename Graph::EdgeIt e;
1648 EdgeIt(const Invalid& i) : e(i), backward(true) { }
1649 EdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) {
1652 while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
1653 if (!_G.graph->valid(e)) {
1656 while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
1659 operator Edge() const {
1660 return Edge(e, this->backward);
1664 using GraphWrapper<Graph>::first;
1665 // NodeIt& first(NodeIt& i) const {
1666 // i=NodeIt(*this); return i;
1668 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1669 i=OutEdgeIt(*this, p); return i;
1672 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1673 i=InEdgeIt(*this, p); return i;
1675 EdgeIt& first(EdgeIt& i) const {
1676 i=EdgeIt(*this); return i;
1679 using GraphWrapper<Graph>::next;
1680 // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
1681 OutEdgeIt& next(OutEdgeIt& e) const {
1683 Node v=this->graph->aNode(e.out);
1684 this->graph->next(e.out);
1685 while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1686 this->graph->next(e.out); }
1687 if (!this->graph->valid(e.out)) {
1689 this->graph->first(e.in, v);
1690 while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1691 this->graph->next(e.in); }
1694 this->graph->next(e.in);
1695 while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1696 this->graph->next(e.in); }
1701 InEdgeIt& next(InEdgeIt& e) const {
1703 Node v=this->graph->aNode(e.in);
1704 this->graph->next(e.in);
1705 while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1706 this->graph->next(e.in); }
1707 if (!this->graph->valid(e.in)) {
1709 this->graph->first(e.out, v);
1710 while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1711 this->graph->next(e.out); }
1714 this->graph->next(e.out);
1715 while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1716 this->graph->next(e.out); }
1720 EdgeIt& next(EdgeIt& e) const {
1722 this->graph->next(e.e);
1723 while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1724 this->graph->next(e.e); }
1725 if (!this->graph->valid(e.e)) {
1727 this->graph->first(e.e);
1728 while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1729 this->graph->next(e.e); }
1732 this->graph->next(e.e);
1733 while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1734 this->graph->next(e.e); }
1739 Node tail(Edge e) const {
1740 return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
1741 Node head(Edge e) const {
1742 return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
1744 Node aNode(OutEdgeIt e) const {
1745 return ((!e.backward) ? this->graph->aNode(e.out) :
1746 this->graph->aNode(e.in)); }
1747 Node bNode(OutEdgeIt e) const {
1748 return ((!e.backward) ? this->graph->bNode(e.out) :
1749 this->graph->bNode(e.in)); }
1751 Node aNode(InEdgeIt e) const {
1752 return ((!e.backward) ? this->graph->aNode(e.in) :
1753 this->graph->aNode(e.out)); }
1754 Node bNode(InEdgeIt e) const {
1755 return ((!e.backward) ? this->graph->bNode(e.in) :
1756 this->graph->bNode(e.out)); }
1758 // int nodeNum() const { return graph->nodeNum(); }
1760 void edgeNum() const { }
1761 //int edgeNum() const { return graph->edgeNum(); }
1764 // int id(Node v) const { return graph->id(v); }
1766 bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
1767 bool valid(Edge e) const {
1768 return this->graph->valid(e);
1769 //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
1772 bool forward(const Edge& e) const { return !e.backward; }
1773 bool backward(const Edge& e) const { return e.backward; }
1775 void augment(const Edge& e, Number a) const {
1777 // flow->set(e.out, flow->get(e.out)+a);
1778 flow->set(e, (*flow)[e]+a);
1780 // flow->set(e.in, flow->get(e.in)-a);
1781 flow->set(e, (*flow)[e]-a);
1784 Number resCap(const Edge& e) const {
1786 // return (capacity->get(e.out)-flow->get(e.out));
1787 return ((*capacity)[e]-(*flow)[e]);
1789 // return (flow->get(e.in));
1790 return ((*flow)[e]);
1793 // Number resCap(typename Graph::OutEdgeIt out) const {
1794 // // return (capacity->get(out)-flow->get(out));
1795 // return ((*capacity)[out]-(*flow)[out]);
1798 // Number resCap(typename Graph::InEdgeIt in) const {
1799 // // return (flow->get(in));
1800 // return ((*flow)[in]);
1803 template <typename T>
1805 typename Graph::template EdgeMap<T> forward_map, backward_map;
1807 typedef T ValueType;
1808 typedef Edge KeyType;
1809 EdgeMap(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1810 EdgeMap(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1811 void set(Edge e, T a) {
1813 forward_map.set(e/*.out*/, a);
1815 backward_map.set(e/*.in*/, a);
1817 T operator[](Edge e) const {
1819 return forward_map[e/*.out*/];
1821 return backward_map[e/*.in*/];
1824 forward_map.update();
1825 backward_map.update();
1827 // T get(Edge e) const {
1829 // return forward_map.get(e.out);
1831 // return backward_map.get(e.in);
1838 /// For blocking flows.
1840 /// This graph wrapper is used for Dinits blocking flow computations.
1841 /// For each node, an out-edge is stored which is used when the
1843 /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1847 ///\author Marton Makai
1848 template<typename Graph, typename FirstOutEdgesMap>
1849 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1851 typedef GraphWrapper<Graph> Parent;
1853 FirstOutEdgesMap* first_out_edges;
1855 ErasingFirstGraphWrapper(Graph& _graph,
1856 FirstOutEdgesMap& _first_out_edges) :
1857 GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
1859 typedef typename GraphWrapper<Graph>::Node Node;
1861 // friend class GraphWrapper<Graph>;
1862 // friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1863 // typename Graph::NodeIt n;
1866 // NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
1867 // NodeIt(const Invalid& i) : n(i) { }
1868 // NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1869 // n(*(_G.graph)) { }
1870 // operator Node() const { return Node(typename Graph::Node(n)); }
1872 typedef typename GraphWrapper<Graph>::Edge Edge;
1874 friend class GraphWrapper<Graph>;
1875 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1876 // typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1877 typename Graph::OutEdgeIt e;
1880 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
1881 OutEdgeIt(const Invalid& i) : e(i) { }
1882 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1884 e((*_G.first_out_edges)[_n]) { }
1885 operator Edge() const { return Edge(typename Graph::Edge(e)); }
1888 friend class GraphWrapper<Graph>;
1889 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1890 // typedef typename Graph::InEdgeIt GraphInEdgeIt;
1891 typename Graph::InEdgeIt e;
1894 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1895 InEdgeIt(const Invalid& i) : e(i) { }
1896 InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1898 e(*(_G.graph), typename Graph::Node(_n)) { }
1899 operator Edge() const { return Edge(typename Graph::Edge(e)); }
1901 //typedef typename Graph::SymEdgeIt SymEdgeIt;
1903 friend class GraphWrapper<Graph>;
1904 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1905 // typedef typename Graph::EdgeIt GraphEdgeIt;
1906 typename Graph::EdgeIt e;
1909 EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
1910 EdgeIt(const Invalid& i) : e(i) { }
1911 EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1913 operator Edge() const { return Edge(typename Graph::Edge(e)); }
1916 using GraphWrapper<Graph>::first;
1917 // NodeIt& first(NodeIt& i) const {
1918 // i=NodeIt(*this); return i;
1920 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1921 i=OutEdgeIt(*this, p); return i;
1923 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1924 i=InEdgeIt(*this, p); return i;
1926 EdgeIt& first(EdgeIt& i) const {
1927 i=EdgeIt(*this); return i;
1930 using GraphWrapper<Graph>::next;
1931 // NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
1932 OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
1933 InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
1934 EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }
1936 Node aNode(const OutEdgeIt& e) const {
1937 return Node(this->graph->aNode(e.e)); }
1938 Node aNode(const InEdgeIt& e) const {
1939 return Node(this->graph->aNode(e.e)); }
1940 Node bNode(const OutEdgeIt& e) const {
1941 return Node(this->graph->bNode(e.e)); }
1942 Node bNode(const InEdgeIt& e) const {
1943 return Node(this->graph->bNode(e.e)); }
1945 void erase(const OutEdgeIt& e) const {
1948 first_out_edges->set(this->tail(e), f.e);
1956 #endif //HUGO_GRAPH_WRAPPER_H