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 { graph->forward(e); }
211 bool backward(const Edge& e) const { graph->backward(e); }
213 Edge opposite(const Edge& e) const { 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 // void setCapacityMap(const CapacityMap& _capacity) {
997 // capacity=&_capacity;
999 // void setFlowMap(FlowMap& _flow) {
1005 BidirGraphWrapper(Graph& _graph) : Parent() {
1006 Parent::setGraph(_graph);
1007 Parent::setForwardFilterMap(cm);
1008 Parent::setBackwardFilterMap(cm);
1015 template<typename Graph>
1016 class OldBidirGraphWrapper : public GraphWrapper<Graph> {
1018 typedef GraphWrapper<Graph> Parent;
1020 //const CapacityMap* capacity;
1023 OldBidirGraphWrapper() : GraphWrapper<Graph>()/*,
1024 capacity(0), flow(0)*/ { }
1025 // void setCapacityMap(const CapacityMap& _capacity) {
1026 // capacity=&_capacity;
1028 // void setFlowMap(FlowMap& _flow) {
1034 OldBidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity,
1036 GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
1041 friend class OutEdgeIt;
1043 //template<typename T> class NodeMap;
1044 template<typename T> class EdgeMap;
1046 typedef typename GraphWrapper<Graph>::Node Node;
1047 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1049 class Edge : public Graph::Edge {
1050 friend class OldBidirGraphWrapper<Graph>;
1051 ///\bug ez nem is kell
1052 //template<typename T> friend class NodeMap;
1053 template<typename T> friend class EdgeMap;
1055 bool backward; //true, iff backward
1056 // typename Graph::Edge e;
1059 ///\bug =false kell-e? zsoltnak kell az addEdge miatt
1060 Edge(const typename Graph::Edge& _e, bool _backward=false) :
1061 Graph::Edge(_e), backward(_backward) { }
1062 Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
1063 //the unique invalid iterator
1064 friend bool operator==(const Edge& u, const Edge& v) {
1065 return (v.backward==u.backward &&
1066 static_cast<typename Graph::Edge>(u)==
1067 static_cast<typename Graph::Edge>(v));
1069 friend bool operator!=(const Edge& u, const Edge& v) {
1070 return (v.backward!=u.backward ||
1071 static_cast<typename Graph::Edge>(u)!=
1072 static_cast<typename Graph::Edge>(v));
1077 friend class OldBidirGraphWrapper<Graph>;
1079 typename Graph::OutEdgeIt out;
1080 typename Graph::InEdgeIt in;
1085 // OutEdgeIt(const Edge& e) : Edge(e) { }
1086 OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1087 //the unique invalid iterator
1088 OutEdgeIt(const OldBidirGraphWrapper<Graph>& _G, Node v) {
1090 _G.graph->first(out, v);
1091 while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
1092 if (!_G.graph->valid(out)) {
1094 _G.graph->first(in, v);
1095 while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
1098 operator Edge() const {
1100 // e.forward=this->forward;
1101 // if (this->forward) e=out; else e=in;
1104 return Edge(in, this->backward);
1106 return Edge(out, this->backward);
1111 friend class OldBidirGraphWrapper<Graph>;
1113 typename Graph::OutEdgeIt out;
1114 typename Graph::InEdgeIt in;
1119 // OutEdgeIt(const Edge& e) : Edge(e) { }
1120 InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1121 //the unique invalid iterator
1122 InEdgeIt(const OldBidirGraphWrapper<Graph>& _G, Node v) {
1124 _G.graph->first(in, v);
1125 while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
1126 if (!_G.graph->valid(in)) {
1128 _G.graph->first(out, v);
1129 while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
1132 operator Edge() const {
1134 // e.forward=this->forward;
1135 // if (this->forward) e=out; else e=in;
1138 return Edge(out, this->backward);
1140 return Edge(in, this->backward);
1145 friend class OldBidirGraphWrapper<Graph>;
1147 typename Graph::EdgeIt e;
1151 EdgeIt(const Invalid& i) : e(i), backward(true) { }
1152 EdgeIt(const OldBidirGraphWrapper<Graph>& _G) {
1155 while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
1156 if (!_G.graph->valid(e)) {
1159 while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
1162 operator Edge() const {
1163 return Edge(e, this->backward);
1167 using GraphWrapper<Graph>::first;
1168 // NodeIt& first(NodeIt& i) const {
1169 // i=NodeIt(*this); return i;
1171 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1172 i=OutEdgeIt(*this, p); return i;
1175 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1176 i=InEdgeIt(*this, p); return i;
1178 EdgeIt& first(EdgeIt& i) const {
1179 i=EdgeIt(*this); return i;
1182 using GraphWrapper<Graph>::next;
1183 // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
1184 OutEdgeIt& next(OutEdgeIt& e) const {
1186 Node v=this->graph->aNode(e.out);
1187 this->graph->next(e.out);
1188 while(this->graph->valid(e.out) && !enabled(e)) {
1189 this->graph->next(e.out); }
1190 if (!this->graph->valid(e.out)) {
1192 this->graph->first(e.in, v);
1193 while(this->graph->valid(e.in) && !enabled(e)) {
1194 this->graph->next(e.in); }
1197 this->graph->next(e.in);
1198 while(this->graph->valid(e.in) && !enabled(e)) {
1199 this->graph->next(e.in); }
1204 InEdgeIt& next(InEdgeIt& e) const {
1206 Node v=this->graph->aNode(e.in);
1207 this->graph->next(e.in);
1208 while(this->graph->valid(e.in) && !enabled(e)) {
1209 this->graph->next(e.in); }
1210 if (!this->graph->valid(e.in)) {
1212 this->graph->first(e.out, v);
1213 while(this->graph->valid(e.out) && !enabled(e)) {
1214 this->graph->next(e.out); }
1217 this->graph->next(e.out);
1218 while(this->graph->valid(e.out) && !enabled(e)) {
1219 this->graph->next(e.out); }
1223 EdgeIt& next(EdgeIt& e) const {
1225 this->graph->next(e.e);
1226 while(this->graph->valid(e.e) && !enabled(e)) {
1227 this->graph->next(e.e); }
1228 if (!this->graph->valid(e.e)) {
1230 this->graph->first(e.e);
1231 while(this->graph->valid(e.e) && !enabled(e)) {
1232 this->graph->next(e.e); }
1235 this->graph->next(e.e);
1236 while(this->graph->valid(e.e) && !enabled(e)) {
1237 this->graph->next(e.e); }
1242 Node tail(Edge e) const {
1243 return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
1244 Node head(Edge e) const {
1245 return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
1247 Node aNode(OutEdgeIt e) const {
1248 return ((!e.backward) ? this->graph->aNode(e.out) :
1249 this->graph->aNode(e.in)); }
1250 Node bNode(OutEdgeIt e) const {
1251 return ((!e.backward) ? this->graph->bNode(e.out) :
1252 this->graph->bNode(e.in)); }
1254 Node aNode(InEdgeIt e) const {
1255 return ((!e.backward) ? this->graph->aNode(e.in) :
1256 this->graph->aNode(e.out)); }
1257 Node bNode(InEdgeIt e) const {
1258 return ((!e.backward) ? this->graph->bNode(e.in) :
1259 this->graph->bNode(e.out)); }
1261 /// Gives back the opposite edge.
1262 Edge opposite(const Edge& e) const {
1264 f.backward=!f.backward;
1268 // int nodeNum() const { return graph->nodeNum(); }
1270 void edgeNum() const { }
1271 //int edgeNum() const { return graph->edgeNum(); }
1274 // int id(Node v) const { return graph->id(v); }
1276 bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
1277 bool valid(Edge e) const {
1278 return this->graph->valid(e);
1279 //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
1282 bool forward(const Edge& e) const { return !e.backward; }
1283 bool backward(const Edge& e) const { return e.backward; }
1285 // void augment(const Edge& e, Number a) const {
1287 // // flow->set(e.out, flow->get(e.out)+a);
1288 // flow->set(e, (*flow)[e]+a);
1290 // // flow->set(e.in, flow->get(e.in)-a);
1291 // flow->set(e, (*flow)[e]-a);
1294 bool enabled(const Edge& e) const {
1296 // return (capacity->get(e.out)-flow->get(e.out));
1297 //return ((*capacity)[e]-(*flow)[e]);
1300 // return (flow->get(e.in));
1301 //return ((*flow)[e]);
1305 // Number enabled(typename Graph::OutEdgeIt out) const {
1306 // // return (capacity->get(out)-flow->get(out));
1307 // return ((*capacity)[out]-(*flow)[out]);
1310 // Number enabled(typename Graph::InEdgeIt in) const {
1311 // // return (flow->get(in));
1312 // return ((*flow)[in]);
1315 template <typename T>
1317 typename Graph::template EdgeMap<T> forward_map, backward_map;
1319 typedef T ValueType;
1320 typedef Edge KeyType;
1321 EdgeMap(const OldBidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1322 EdgeMap(const OldBidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1323 void set(Edge e, T a) {
1325 forward_map.set(e/*.out*/, a);
1327 backward_map.set(e/*.in*/, a);
1329 T operator[](Edge e) const {
1331 return forward_map[e/*.out*/];
1333 return backward_map[e/*.in*/];
1336 forward_map.update();
1337 backward_map.update();
1339 // T get(Edge e) const {
1341 // return forward_map.get(e.out);
1343 // return backward_map.get(e.in);
1350 /// \brief A bidirected graph template.
1352 /// A bidirected graph template.
1353 /// Such a bidirected graph stores each pair of oppositely directed edges
1354 /// ones in the memory, i.e. a directed graph of type
1355 /// \c Graph is used for that.
1356 /// As the oppositely directed edges are logically different ones
1357 /// the maps are able to attach different values for them.
1359 template<typename Graph>
1360 class BidirGraph : public BidirGraphWrapper<Graph> {
1362 typedef UndirGraphWrapper<Graph> Parent;
1366 BidirGraph() : BidirGraphWrapper<Graph>() {
1367 Parent::setGraph(gr);
1373 template<typename Graph, typename Number,
1374 typename CapacityMap, typename FlowMap>
1375 class ForwardFilter {
1377 const CapacityMap* capacity;
1378 const FlowMap* flow;
1380 ForwardFilter(const Graph& _graph,
1381 const CapacityMap& _capacity, const FlowMap& _flow) :
1382 graph(&_graph), capacity(&_capacity), flow(&_flow) { }
1383 bool operator[](const typename Graph::Edge& e) const {
1384 return ((*flow)[e] < (*capacity)[e]);
1388 template<typename Graph, typename Number,
1389 typename CapacityMap, typename FlowMap>
1390 class BackwardFilter {
1392 const CapacityMap* capacity;
1393 const FlowMap* flow;
1395 BackwardFilter(const Graph& _graph,
1396 const CapacityMap& _capacity, const FlowMap& _flow) :
1397 graph(&_graph), capacity(&_capacity), flow(&_flow) { }
1398 bool operator[](const typename Graph::Edge& e) const {
1399 return (0 < (*flow)[e]);
1404 /// A wrapper for composing the residual graph for directed flow and circulation problems.
1406 /// A wrapper for composing the residual graph for directed flow and circulation problems.
1407 template<typename Graph, typename Number,
1408 typename CapacityMap, typename FlowMap>
1409 class ResGraphWrapper :
1410 public SubBidirGraphWrapper<
1412 ForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1413 BackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1415 typedef SubBidirGraphWrapper<
1417 ForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1418 BackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1420 const CapacityMap* capacity;
1422 ForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1423 BackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1425 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1427 Parent(), capacity(&_capacity), flow(&_flow),
1428 forward_filter(_graph, _capacity, _flow),
1429 backward_filter(_graph, _capacity, _flow) {
1430 Parent::setGraph(_graph);
1431 Parent::setForwardFilterMap(forward_filter);
1432 Parent::setBackwardFilterMap(backward_filter);
1435 // bool forward(const Parent::Edge& e) const { return Parent::forward(e); }
1436 //bool backward(const Edge& e) const { return e.backward; }
1438 void augment(const typename Parent::Edge& e, Number a) const {
1439 if (Parent::forward(e))
1440 // flow->set(e.out, flow->get(e.out)+a);
1441 flow->set(e, (*flow)[e]+a);
1443 //flow->set(e.in, flow->get(e.in)-a);
1444 flow->set(e, (*flow)[e]-a);
1447 Number resCap(const typename Parent::Edge& e) const {
1448 if (Parent::forward(e))
1449 // return (capacity->get(e.out)-flow->get(e.out));
1450 return ((*capacity)[e]-(*flow)[e]);
1452 // return (flow->get(e.in));
1453 return ((*flow)[e]);
1461 template<typename Graph, typename Number,
1462 typename CapacityMap, typename FlowMap>
1463 class OldResGraphWrapper : public GraphWrapper<Graph> {
1465 typedef GraphWrapper<Graph> Parent;
1467 const CapacityMap* capacity;
1470 OldResGraphWrapper() : GraphWrapper<Graph>(0),
1471 capacity(0), flow(0) { }
1472 void setCapacityMap(const CapacityMap& _capacity) {
1473 capacity=&_capacity;
1475 void setFlowMap(FlowMap& _flow) {
1481 OldResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1483 GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
1488 friend class OutEdgeIt;
1490 typedef typename GraphWrapper<Graph>::Node Node;
1491 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1492 class Edge : public Graph::Edge {
1493 friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1495 bool backward; //true, iff backward
1496 // typename Graph::Edge e;
1499 Edge(const typename Graph::Edge& _e, bool _backward) :
1500 Graph::Edge(_e), backward(_backward) { }
1501 Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
1502 //the unique invalid iterator
1503 friend bool operator==(const Edge& u, const Edge& v) {
1504 return (v.backward==u.backward &&
1505 static_cast<typename Graph::Edge>(u)==
1506 static_cast<typename Graph::Edge>(v));
1508 friend bool operator!=(const Edge& u, const Edge& v) {
1509 return (v.backward!=u.backward ||
1510 static_cast<typename Graph::Edge>(u)!=
1511 static_cast<typename Graph::Edge>(v));
1516 friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1518 typename Graph::OutEdgeIt out;
1519 typename Graph::InEdgeIt in;
1524 // OutEdgeIt(const Edge& e) : Edge(e) { }
1525 OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1526 //the unique invalid iterator
1527 OutEdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
1529 _G.graph->first(out, v);
1530 while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
1531 if (!_G.graph->valid(out)) {
1533 _G.graph->first(in, v);
1534 while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
1537 operator Edge() const {
1539 // e.forward=this->forward;
1540 // if (this->forward) e=out; else e=in;
1543 return Edge(in, this->backward);
1545 return Edge(out, this->backward);
1550 friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1552 typename Graph::OutEdgeIt out;
1553 typename Graph::InEdgeIt in;
1558 // OutEdgeIt(const Edge& e) : Edge(e) { }
1559 InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1560 //the unique invalid iterator
1561 InEdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
1563 _G.graph->first(in, v);
1564 while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
1565 if (!_G.graph->valid(in)) {
1567 _G.graph->first(out, v);
1568 while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
1571 operator Edge() const {
1573 // e.forward=this->forward;
1574 // if (this->forward) e=out; else e=in;
1577 return Edge(out, this->backward);
1579 return Edge(in, this->backward);
1584 friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1586 typename Graph::EdgeIt e;
1590 EdgeIt(const Invalid& i) : e(i), backward(true) { }
1591 EdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) {
1594 while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
1595 if (!_G.graph->valid(e)) {
1598 while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
1601 operator Edge() const {
1602 return Edge(e, this->backward);
1606 using GraphWrapper<Graph>::first;
1607 // NodeIt& first(NodeIt& i) const {
1608 // i=NodeIt(*this); return i;
1610 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1611 i=OutEdgeIt(*this, p); return i;
1614 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1615 i=InEdgeIt(*this, p); return i;
1617 EdgeIt& first(EdgeIt& i) const {
1618 i=EdgeIt(*this); return i;
1621 using GraphWrapper<Graph>::next;
1622 // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
1623 OutEdgeIt& next(OutEdgeIt& e) const {
1625 Node v=this->graph->aNode(e.out);
1626 this->graph->next(e.out);
1627 while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1628 this->graph->next(e.out); }
1629 if (!this->graph->valid(e.out)) {
1631 this->graph->first(e.in, v);
1632 while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1633 this->graph->next(e.in); }
1636 this->graph->next(e.in);
1637 while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1638 this->graph->next(e.in); }
1643 InEdgeIt& next(InEdgeIt& e) const {
1645 Node v=this->graph->aNode(e.in);
1646 this->graph->next(e.in);
1647 while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1648 this->graph->next(e.in); }
1649 if (!this->graph->valid(e.in)) {
1651 this->graph->first(e.out, v);
1652 while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1653 this->graph->next(e.out); }
1656 this->graph->next(e.out);
1657 while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1658 this->graph->next(e.out); }
1662 EdgeIt& next(EdgeIt& e) const {
1664 this->graph->next(e.e);
1665 while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1666 this->graph->next(e.e); }
1667 if (!this->graph->valid(e.e)) {
1669 this->graph->first(e.e);
1670 while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1671 this->graph->next(e.e); }
1674 this->graph->next(e.e);
1675 while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1676 this->graph->next(e.e); }
1681 Node tail(Edge e) const {
1682 return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
1683 Node head(Edge e) const {
1684 return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
1686 Node aNode(OutEdgeIt e) const {
1687 return ((!e.backward) ? this->graph->aNode(e.out) :
1688 this->graph->aNode(e.in)); }
1689 Node bNode(OutEdgeIt e) const {
1690 return ((!e.backward) ? this->graph->bNode(e.out) :
1691 this->graph->bNode(e.in)); }
1693 Node aNode(InEdgeIt e) const {
1694 return ((!e.backward) ? this->graph->aNode(e.in) :
1695 this->graph->aNode(e.out)); }
1696 Node bNode(InEdgeIt e) const {
1697 return ((!e.backward) ? this->graph->bNode(e.in) :
1698 this->graph->bNode(e.out)); }
1700 // int nodeNum() const { return graph->nodeNum(); }
1702 void edgeNum() const { }
1703 //int edgeNum() const { return graph->edgeNum(); }
1706 // int id(Node v) const { return graph->id(v); }
1708 bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
1709 bool valid(Edge e) const {
1710 return this->graph->valid(e);
1711 //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
1714 bool forward(const Edge& e) const { return !e.backward; }
1715 bool backward(const Edge& e) const { return e.backward; }
1717 void augment(const Edge& e, Number a) const {
1719 // flow->set(e.out, flow->get(e.out)+a);
1720 flow->set(e, (*flow)[e]+a);
1722 // flow->set(e.in, flow->get(e.in)-a);
1723 flow->set(e, (*flow)[e]-a);
1726 Number resCap(const Edge& e) const {
1728 // return (capacity->get(e.out)-flow->get(e.out));
1729 return ((*capacity)[e]-(*flow)[e]);
1731 // return (flow->get(e.in));
1732 return ((*flow)[e]);
1735 // Number resCap(typename Graph::OutEdgeIt out) const {
1736 // // return (capacity->get(out)-flow->get(out));
1737 // return ((*capacity)[out]-(*flow)[out]);
1740 // Number resCap(typename Graph::InEdgeIt in) const {
1741 // // return (flow->get(in));
1742 // return ((*flow)[in]);
1745 template <typename T>
1747 typename Graph::template EdgeMap<T> forward_map, backward_map;
1749 typedef T ValueType;
1750 typedef Edge KeyType;
1751 EdgeMap(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1752 EdgeMap(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1753 void set(Edge e, T a) {
1755 forward_map.set(e/*.out*/, a);
1757 backward_map.set(e/*.in*/, a);
1759 T operator[](Edge e) const {
1761 return forward_map[e/*.out*/];
1763 return backward_map[e/*.in*/];
1766 forward_map.update();
1767 backward_map.update();
1769 // T get(Edge e) const {
1771 // return forward_map.get(e.out);
1773 // return backward_map.get(e.in);
1780 /// For blocking flows.
1782 /// This graph wrapper is used for Dinits blocking flow computations.
1783 /// For each node, an out-edge is stored which is used when the
1785 /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1789 ///\author Marton Makai
1790 template<typename Graph, typename FirstOutEdgesMap>
1791 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1793 typedef GraphWrapper<Graph> Parent;
1795 FirstOutEdgesMap* first_out_edges;
1797 ErasingFirstGraphWrapper(Graph& _graph,
1798 FirstOutEdgesMap& _first_out_edges) :
1799 GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
1801 typedef typename GraphWrapper<Graph>::Node Node;
1803 // friend class GraphWrapper<Graph>;
1804 // friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1805 // typename Graph::NodeIt n;
1808 // NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
1809 // NodeIt(const Invalid& i) : n(i) { }
1810 // NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1811 // n(*(_G.graph)) { }
1812 // operator Node() const { return Node(typename Graph::Node(n)); }
1814 typedef typename GraphWrapper<Graph>::Edge Edge;
1816 friend class GraphWrapper<Graph>;
1817 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1818 // typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1819 typename Graph::OutEdgeIt e;
1822 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
1823 OutEdgeIt(const Invalid& i) : e(i) { }
1824 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1826 e((*_G.first_out_edges)[_n]) { }
1827 operator Edge() const { return Edge(typename Graph::Edge(e)); }
1830 friend class GraphWrapper<Graph>;
1831 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1832 // typedef typename Graph::InEdgeIt GraphInEdgeIt;
1833 typename Graph::InEdgeIt e;
1836 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1837 InEdgeIt(const Invalid& i) : e(i) { }
1838 InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1840 e(*(_G.graph), typename Graph::Node(_n)) { }
1841 operator Edge() const { return Edge(typename Graph::Edge(e)); }
1843 //typedef typename Graph::SymEdgeIt SymEdgeIt;
1845 friend class GraphWrapper<Graph>;
1846 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1847 // typedef typename Graph::EdgeIt GraphEdgeIt;
1848 typename Graph::EdgeIt e;
1851 EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
1852 EdgeIt(const Invalid& i) : e(i) { }
1853 EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1855 operator Edge() const { return Edge(typename Graph::Edge(e)); }
1858 using GraphWrapper<Graph>::first;
1859 // NodeIt& first(NodeIt& i) const {
1860 // i=NodeIt(*this); return i;
1862 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1863 i=OutEdgeIt(*this, p); return i;
1865 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1866 i=InEdgeIt(*this, p); return i;
1868 EdgeIt& first(EdgeIt& i) const {
1869 i=EdgeIt(*this); return i;
1872 using GraphWrapper<Graph>::next;
1873 // NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
1874 OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
1875 InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
1876 EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }
1878 Node aNode(const OutEdgeIt& e) const {
1879 return Node(this->graph->aNode(e.e)); }
1880 Node aNode(const InEdgeIt& e) const {
1881 return Node(this->graph->aNode(e.e)); }
1882 Node bNode(const OutEdgeIt& e) const {
1883 return Node(this->graph->bNode(e.e)); }
1884 Node bNode(const InEdgeIt& e) const {
1885 return Node(this->graph->bNode(e.e)); }
1887 void erase(const OutEdgeIt& e) const {
1890 first_out_edges->set(this->tail(e), f.e);
1898 #endif //HUGO_GRAPH_WRAPPER_H