2 #ifndef HUGO_GRAPH_WRAPPER_H
3 #define HUGO_GRAPH_WRAPPER_H
7 ///\brief Several graph wrappers.
9 ///This file contains several useful graph wrapper functions.
11 ///\author Marton Makai
13 #include <hugo/invalid.h>
14 #include <hugo/maps.h>
21 /// \addtogroup gwrappers
22 /// A main parts of HUGOlib are the different graph structures,
23 /// generic graph algorithms, graph concepts which couple these, and
24 /// graph wrappers. While the previous ones are more or less clear, the
25 /// latter notion needs further explanation.
26 /// Graph wrappers are graph classes which serve for considering graph
27 /// structures in different ways. A short example makes the notion much
29 /// Suppose that we have an instance \c g of a directed graph
30 /// type say \c ListGraph and an algorithm
31 /// \code template<typename Graph> int algorithm(const Graph&); \endcode
32 /// is needed to run on the reversely oriented graph.
33 /// It may be expensive (in time or in memory usage) to copy
34 /// \c g with the reverse orientation.
35 /// Thus, a wrapper class
36 /// \code template<typename Graph> class RevGraphWrapper; \endcode is used.
37 /// The code looks as follows
40 /// RevGraphWrapper<ListGraph> rgw(g);
41 /// int result=algorithm(rgw);
43 /// After running the algorithm, the original graph \c g
44 /// remains untouched. Thus the graph wrapper used above is to consider the
45 /// original graph with reverse orientation.
46 /// This techniques gives rise to an elegant code, and
47 /// based on stable graph wrappers, complex algorithms can be
48 /// implemented easily.
49 /// In flow, circulation and bipartite matching problems, the residual
50 /// graph is of particular importance. Combining a wrapper implementing
51 /// this, shortest path algorithms and minimum mean cycle algorithms,
52 /// a range of weighted and cardinality optimization algorithms can be
53 /// obtained. For lack of space, for other examples,
54 /// the interested user is referred to the detailed documentation of graph
56 /// The behavior of graph wrappers can be very different. Some of them keep
57 /// capabilities of the original graph while in other cases this would be
58 /// meaningless. This means that the concepts that they are a model of depend
59 /// on the graph wrapper, and the wrapped graph(s).
60 /// If an edge of \c rgw is deleted, this is carried out by
61 /// deleting the corresponding edge of \c g. But for a residual
62 /// graph, this operation has no sense.
63 /// Let we stand one more example here to simplify your work.
65 /// \code template<typename Graph> class RevGraphWrapper; \endcode
67 /// <tt> RevGraphWrapper(Graph& _g)</tt>.
68 /// This means that in a situation,
69 /// when a <tt> const ListGraph& </tt> reference to a graph is given,
70 /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
72 /// int algorithm1(const ListGraph& g) {
73 /// RevGraphWrapper<const ListGraph> rgw(g);
74 /// return algorithm2(rgw);
78 /// \addtogroup gwrappers
81 ///Base type for the Graph Wrappers
83 ///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 GraphWrapper(const GraphWrapper<Graph>& gw) : graph(gw.graph) { }
100 // Graph& getGraph() const { return *graph; }
102 typedef typename Graph::Node Node;
103 class NodeIt : public Node {
104 const GraphWrapper<Graph>* gw;
105 friend class GraphWrapper<Graph>;
108 // NodeIt(const NodeIt& n) : Node(n), gw(n.gw) { }
109 NodeIt(Invalid i) : Node(i) { }
110 NodeIt(const GraphWrapper<Graph>& _gw) :
111 Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { }
112 NodeIt(const GraphWrapper<Graph>& _gw, const Node& n) :
113 Node(n), gw(&_gw) { }
114 NodeIt& operator++() {
115 *(static_cast<Node*>(this))=
116 ++(typename Graph::NodeIt(*(gw->graph), *this));
120 typedef typename Graph::Edge Edge;
121 class OutEdgeIt : public Edge {
122 const GraphWrapper<Graph>* gw;
123 friend class GraphWrapper<Graph>;
126 //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
127 OutEdgeIt(Invalid i) : Edge(i) { }
128 OutEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) :
129 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
130 OutEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
131 Edge(e), gw(&_gw) { }
132 OutEdgeIt& operator++() {
133 *(static_cast<Edge*>(this))=
134 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
138 class InEdgeIt : public Edge {
139 const GraphWrapper<Graph>* gw;
140 friend class GraphWrapper<Graph>;
143 //InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
144 InEdgeIt(Invalid i) : Edge(i) { }
145 InEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) :
146 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
147 InEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
148 Edge(e), gw(&_gw) { }
149 InEdgeIt& operator++() {
150 *(static_cast<Edge*>(this))=
151 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
155 //typedef typename Graph::SymEdgeIt SymEdgeIt;
156 class EdgeIt : public Edge {
157 const GraphWrapper<Graph>* gw;
158 friend class GraphWrapper<Graph>;
161 //EdgeIt(const EdgeIt& e) : Edge(e), gw(e.gw) { }
162 EdgeIt(Invalid i) : Edge(i) { }
163 EdgeIt(const GraphWrapper<Graph>& _gw) :
164 Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { }
165 EdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
166 Edge(e), gw(&_gw) { }
167 EdgeIt& operator++() {
168 *(static_cast<Edge*>(this))=
169 ++(typename Graph::EdgeIt(*(gw->graph), *this));
174 NodeIt& first(NodeIt& i) const {
175 i=NodeIt(*this); return i;
177 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
178 i=OutEdgeIt(*this, p); return i;
180 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
181 i=InEdgeIt(*this, p); return i;
183 EdgeIt& first(EdgeIt& i) const {
184 i=EdgeIt(*this); return i;
187 // NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
188 // OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
189 // InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
190 // EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
192 Node tail(const Edge& e) const {
193 return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
194 Node head(const Edge& e) const {
195 return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
197 // bool valid(const Node& n) const {
198 // return graph->valid(static_cast<typename Graph::Node>(n)); }
199 // bool valid(const Edge& e) const {
200 // return graph->valid(static_cast<typename Graph::Edge>(e)); }
202 int nodeNum() const { return graph->nodeNum(); }
203 int edgeNum() const { return graph->edgeNum(); }
205 // Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
206 // Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
207 // Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
208 // Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
210 Node addNode() const { return Node(graph->addNode()); }
211 Edge addEdge(const Node& tail, const Node& head) const {
212 return Edge(graph->addEdge(tail, head)); }
214 void erase(const Node& i) const { graph->erase(i); }
215 void erase(const Edge& i) const { graph->erase(i); }
217 void clear() const { graph->clear(); }
219 bool forward(const Edge& e) const { return graph->forward(e); }
220 bool backward(const Edge& e) const { return graph->backward(e); }
222 int id(const Node& v) const { return graph->id(v); }
223 int id(const Edge& e) const { return graph->id(e); }
225 Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }
227 template<typename T> class NodeMap : public Graph::template NodeMap<T> {
228 typedef typename Graph::template NodeMap<T> Parent;
230 NodeMap(const GraphWrapper<Graph>& gw) : Parent(*(gw.graph)) { }
231 NodeMap(const GraphWrapper<Graph>& gw, T a) : Parent(*(gw.graph), a) { }
234 template<typename T> class EdgeMap : public Graph::template EdgeMap<T> {
235 typedef typename Graph::template EdgeMap<T> Parent;
237 EdgeMap(const GraphWrapper<Graph>& gw) : Parent(*(gw.graph)) { }
238 EdgeMap(const GraphWrapper<Graph>& gw, T a) : Parent(*(gw.graph), a) { }
244 /// A graph wrapper which reverses the orientation of the edges.
246 /// A graph wrapper which reverses the orientation of the edges.
247 /// Thus \c Graph have to be a directed graph type.
249 ///\author Marton Makai
250 template<typename Graph>
251 class RevGraphWrapper : public GraphWrapper<Graph> {
253 typedef GraphWrapper<Graph> Parent;
255 RevGraphWrapper() : GraphWrapper<Graph>() { }
257 RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
258 RevGraphWrapper(const RevGraphWrapper<Graph>& gw) : Parent(gw) { }
260 typedef typename GraphWrapper<Graph>::Node Node;
261 typedef typename GraphWrapper<Graph>::Edge Edge;
262 //remark: OutEdgeIt and InEdgeIt cannot be typedef-ed to each other
263 //because this does not work is some of them are not defined in the
264 //original graph. The problem with this is that typedef-ed stuff
265 //are instantiated in c++.
266 class OutEdgeIt : public Edge {
267 const RevGraphWrapper<Graph>* gw;
268 friend class GraphWrapper<Graph>;
271 //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
272 OutEdgeIt(Invalid i) : Edge(i) { }
273 OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) :
274 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
275 OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) :
276 Edge(e), gw(&_gw) { }
277 OutEdgeIt& operator++() {
278 *(static_cast<Edge*>(this))=
279 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
283 class InEdgeIt : public Edge {
284 const RevGraphWrapper<Graph>* gw;
285 friend class GraphWrapper<Graph>;
288 //InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
289 InEdgeIt(Invalid i) : Edge(i) { }
290 InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) :
291 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
292 InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) :
293 Edge(e), gw(&_gw) { }
294 InEdgeIt& operator++() {
295 *(static_cast<Edge*>(this))=
296 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
301 using GraphWrapper<Graph>::first;
302 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
303 i=OutEdgeIt(*this, p); return i;
305 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
306 i=InEdgeIt(*this, p); return i;
309 // using GraphWrapper<Graph>::next;
310 // OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
311 // InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
313 // Node aNode(const OutEdgeIt& e) const {
314 // return Node(this->graph->aNode(e.e)); }
315 // Node aNode(const InEdgeIt& e) const {
316 // return Node(this->graph->aNode(e.e)); }
317 // Node bNode(const OutEdgeIt& e) const {
318 // return Node(this->graph->bNode(e.e)); }
319 // Node bNode(const InEdgeIt& e) const {
320 // return Node(this->graph->bNode(e.e)); }
322 Node tail(const Edge& e) const {
323 return GraphWrapper<Graph>::head(e); }
324 Node head(const Edge& e) const {
325 return GraphWrapper<Graph>::tail(e); }
331 /// A graph wrapper for hiding nodes and edges from a graph.
333 /// This wrapper shows a graph with filtered node-set and
334 /// edge-set. The quick brown fox iterator jumps over
335 /// the lazy dog nodes or edges if the values for them are false
336 /// in the bool maps.
338 ///\author Marton Makai
339 template<typename Graph, typename NodeFilterMap,
340 typename EdgeFilterMap>
341 class SubGraphWrapper : public GraphWrapper<Graph> {
343 typedef GraphWrapper<Graph> Parent;
345 NodeFilterMap* node_filter_map;
346 EdgeFilterMap* edge_filter_map;
348 SubGraphWrapper() : GraphWrapper<Graph>(),
349 node_filter_map(0), edge_filter_map(0) { }
350 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
351 node_filter_map=&_node_filter_map;
353 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
354 edge_filter_map=&_edge_filter_map;
358 SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
359 EdgeFilterMap& _edge_filter_map) :
360 GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
361 edge_filter_map(&_edge_filter_map) { }
363 typedef typename GraphWrapper<Graph>::Node Node;
364 class NodeIt : public Node {
365 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
366 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
369 // NodeIt(const NodeIt& n) : Node(n), gw(n.gw) { }
370 NodeIt(Invalid i) : Node(i) { }
371 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
372 Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { }
373 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
375 Node(n), gw(&_gw) { }
376 NodeIt& operator++() {
377 *(static_cast<Node*>(this))=
378 ++(typename Graph::NodeIt(*(gw->graph), *this));
379 while (*static_cast<Node*>(this)!=INVALID &&
380 !(*(gw->node_filter_map))[*this])
381 *(static_cast<Node*>(this))=
382 ++(typename Graph::NodeIt(*(gw->graph), *this));
386 typedef typename GraphWrapper<Graph>::Edge Edge;
387 class OutEdgeIt : public Edge {
388 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
389 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
392 // OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
393 OutEdgeIt(Invalid i) : Edge(i) { }
394 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
395 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
396 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
398 Edge(e), gw(&_gw) { }
399 OutEdgeIt& operator++() {
400 *(static_cast<Edge*>(this))=
401 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
402 while (*static_cast<Edge*>(this)!=INVALID &&
403 !(*(gw->edge_filter_map))[*this])
404 *(static_cast<Edge*>(this))=
405 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
409 class InEdgeIt : public Edge {
410 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
411 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
414 // InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
415 InEdgeIt(Invalid i) : Edge(i) { }
416 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
417 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
418 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
420 Edge(e), gw(&_gw) { }
421 InEdgeIt& operator++() {
422 *(static_cast<Edge*>(this))=
423 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
424 while (*static_cast<Edge*>(this)!=INVALID &&
425 !(*(gw->edge_filter_map))[*this])
426 *(static_cast<Edge*>(this))=
427 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
431 class EdgeIt : public Edge {
432 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
433 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
436 // EdgeIt(const EdgeIt& e) : Edge(e), gw(e.gw) { }
437 EdgeIt(Invalid i) : Edge(i) { }
438 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
439 Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { }
440 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
442 Edge(e), gw(&_gw) { }
443 EdgeIt& operator++() {
444 *(static_cast<Edge*>(this))=
445 ++(typename Graph::EdgeIt(*(gw->graph), *this));
446 while (*static_cast<Edge*>(this)!=INVALID &&
447 !(*(gw->edge_filter_map))[*this])
448 *(static_cast<Edge*>(this))=
449 ++(typename Graph::EdgeIt(*(gw->graph), *this));
454 NodeIt& first(NodeIt& i) const {
455 i=NodeIt(*this); return i;
457 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
458 i=OutEdgeIt(*this, p); return i;
460 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
461 i=InEdgeIt(*this, p); return i;
463 EdgeIt& first(EdgeIt& i) const {
464 i=EdgeIt(*this); return i;
467 // NodeIt& next(NodeIt& i) const {
468 // this->graph->next(i.n);
469 // while (this->graph->valid(i) && !(*node_filter_map)[i.n]) {
470 // this->graph->next(i.n); }
473 // OutEdgeIt& next(OutEdgeIt& i) const {
474 // this->graph->next(i.e);
475 // while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
476 // this->graph->next(i.e); }
479 // InEdgeIt& next(InEdgeIt& i) const {
480 // this->graph->next(i.e);
481 // while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
482 // this->graph->next(i.e); }
485 // EdgeIt& next(EdgeIt& i) const {
486 // this->graph->next(i.e);
487 // while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
488 // this->graph->next(i.e); }
492 // Node aNode(const OutEdgeIt& e) const {
493 // return Node(this->graph->aNode(e.e)); }
494 // Node aNode(const InEdgeIt& e) const {
495 // return Node(this->graph->aNode(e.e)); }
496 // Node bNode(const OutEdgeIt& e) const {
497 // return Node(this->graph->bNode(e.e)); }
498 // Node bNode(const InEdgeIt& e) const {
499 // return Node(this->graph->bNode(e.e)); }
501 /// This function hides \c n in the graph, i.e. the iteration
502 /// jumps over it. This is done by simply setting the value of \c n
503 /// to be false in the corresponding node-map.
504 void hide(const Node& n) const { node_filter_map->set(n, false); }
506 /// This function hides \c e in the graph, i.e. the iteration
507 /// jumps over it. This is done by simply setting the value of \c e
508 /// to be false in the corresponding edge-map.
509 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
511 /// The value of \c n is set to be true in the node-map which stores
512 /// hide information. If \c n was hidden previuosly, then it is shown
514 void unHide(const Node& n) const { node_filter_map->set(n, true); }
516 /// The value of \c e is set to be true in the edge-map which stores
517 /// hide information. If \c e was hidden previuosly, then it is shown
519 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
521 /// Returns true if \c n is hidden.
522 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
524 /// Returns true if \c n is hidden.
525 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
527 /// \warning This is a linear time operation and works only if
528 /// \c Graph::NodeIt is defined.
529 int nodeNum() const {
531 for (NodeIt n(*this); n!=INVALID; ++n) ++i;
535 /// \warning This is a linear time operation and works only if
536 /// \c Graph::EdgeIt is defined.
537 int edgeNum() const {
539 for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
547 /// \brief A wrapper for forgetting the orientation of a graph.
549 /// A wrapper for getting an undirected graph by forgetting
550 /// the orientation of a directed one.
552 /// \author Marton Makai
553 template<typename Graph>
554 class UndirGraphWrapper : public GraphWrapper<Graph> {
556 typedef GraphWrapper<Graph> Parent;
558 UndirGraphWrapper() : GraphWrapper<Graph>() { }
561 typedef typename GraphWrapper<Graph>::Node Node;
562 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
563 typedef typename GraphWrapper<Graph>::Edge Edge;
564 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
566 UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
569 friend class UndirGraphWrapper<Graph>;
570 bool out_or_in; //true iff out
571 typename Graph::OutEdgeIt out;
572 typename Graph::InEdgeIt in;
575 OutEdgeIt(const Invalid& i) : Edge(i) { }
576 OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
577 out_or_in=true; _G.graph->first(out, _n);
578 if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); }
580 operator Edge() const {
581 if (out_or_in) return Edge(out); else return Edge(in);
586 typedef OutEdgeIt InEdgeIt;
588 using GraphWrapper<Graph>::first;
589 // NodeIt& first(NodeIt& i) const {
590 // i=NodeIt(*this); return i;
592 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
593 i=OutEdgeIt(*this, p); return i;
596 // InEdgeIt& first(InEdgeIt& i, const Node& p) const {
597 // i=InEdgeIt(*this, p); return i;
599 // EdgeIt& first(EdgeIt& i) const {
600 // i=EdgeIt(*this); return i;
603 using GraphWrapper<Graph>::next;
604 // NodeIt& next(NodeIt& n) const {
605 // GraphWrapper<Graph>::next(n);
608 OutEdgeIt& next(OutEdgeIt& e) const {
610 typename Graph::Node n=this->graph->tail(e.out);
611 this->graph->next(e.out);
612 if (!this->graph->valid(e.out)) {
613 e.out_or_in=false; this->graph->first(e.in, n); }
615 this->graph->next(e.in);
620 // EdgeIt& next(EdgeIt& e) const {
621 // GraphWrapper<Graph>::next(n);
622 // // graph->next(e.e);
626 Node aNode(const OutEdgeIt& e) const {
627 if (e.out_or_in) return this->graph->tail(e); else
628 return this->graph->head(e); }
629 Node bNode(const OutEdgeIt& e) const {
630 if (e.out_or_in) return this->graph->head(e); else
631 return this->graph->tail(e); }
634 /// \brief An undirected graph template.
636 /// An undirected graph template.
637 /// This class works as an undirected graph and a directed graph of
638 /// class \c Graph is used for the physical storage.
640 template<typename Graph>
641 class UndirGraph : public UndirGraphWrapper<Graph> {
642 typedef UndirGraphWrapper<Graph> Parent;
646 UndirGraph() : UndirGraphWrapper<Graph>() {
647 Parent::setGraph(gr);
653 ///\brief A wrapper for composing a subgraph of a
654 /// bidirected graph made from a directed one.
656 /// Suppose that for a directed graph $G=(V, A)$,
657 /// two predicates on the edge-set, $forward_filter$, and $backward_filter$
658 /// is given, and we are dealing with the directed graph
659 /// a $G'=(V, \{uv : uv\in A \mbox{ and } forward_filter(uv) \mbox{ is true}\}+\{vu : uv\in A \mbox{ and } backward_filter(uv) \mbox{ is true}\})$.
660 /// The purpose of writing + instead of union is because parallel
662 /// In other words, a subgraph of the bidirected graph obtained, which
663 /// is given by orienting the edges of the original graph in both directions.
664 /// An example for such a construction is the \c RevGraphWrapper where the
665 /// forward_filter is everywhere false and the backward_filter is
666 /// everywhere true. We note that for sake of efficiency,
667 /// \c RevGraphWrapper is implemented in a different way.
668 /// But BidirGraphWrapper is obtained from
669 /// SubBidirGraphWrapper by considering everywhere true
670 /// predicates both forward_filter and backward_filter.
671 /// Finally, one of the most important applications of SubBidirGraphWrapper
672 /// is ResGraphWrapper, which stands for the residual graph in directed
673 /// flow and circulation problems.
674 /// As wrappers usually, the SubBidirGraphWrapper implements the
675 /// above mentioned graph structure without its physical storage,
676 /// that is the whole stuff eats constant memory.
677 /// As the oppositely directed edges are logical different,
678 /// the maps are able to attach different values for them.
679 template<typename Graph,
680 typename ForwardFilterMap, typename BackwardFilterMap>
681 class SubBidirGraphWrapper : public GraphWrapper<Graph> {
683 typedef GraphWrapper<Graph> Parent;
685 ForwardFilterMap* forward_filter;
686 BackwardFilterMap* backward_filter;
688 SubBidirGraphWrapper() : GraphWrapper<Graph>() { }
689 void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
690 forward_filter=&_forward_filter;
692 void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
693 backward_filter=&_backward_filter;
698 SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter,
699 BackwardFilterMap& _backward_filter) :
700 GraphWrapper<Graph>(_graph),
701 forward_filter(&_forward_filter), backward_filter(&_backward_filter) { }
702 SubBidirGraphWrapper(const SubBidirGraphWrapper<Graph,
703 ForwardFilterMap, BackwardFilterMap>& gw) :
705 forward_filter(gw.forward_filter),
706 backward_filter(gw.backward_filter) { }
711 friend class OutEdgeIt;
713 template<typename T> class EdgeMap;
715 typedef typename GraphWrapper<Graph>::Node Node;
717 typedef typename Graph::Edge GraphEdge;
718 /// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from
719 /// Graph::Edge. It contains an extra bool flag which shows if the
720 /// edge is the backward version of the original edge.
721 class Edge : public Graph::Edge {
722 friend class SubBidirGraphWrapper<Graph,
723 ForwardFilterMap, BackwardFilterMap>;
724 template<typename T> friend class EdgeMap;
726 bool backward; //true, iff backward
729 /// \todo =false is needed, or causes problems?
730 /// If \c _backward is false, then we get an edge corresponding to the
731 /// original one, otherwise its oppositely directed pair is obtained.
732 Edge(const typename Graph::Edge& e, bool _backward/*=false*/) :
733 Graph::Edge(e), backward(_backward) { }
734 Edge(Invalid i) : Graph::Edge(i), backward(true) { }
735 //the unique invalid iterator
736 // friend bool operator==(const Edge& u, const Edge& v) {
737 // return (u.backward==v.backward &&
738 // static_cast<typename Graph::Edge>(u)==
739 // static_cast<typename Graph::Edge>(v));
741 // friend bool operator!=(const Edge& u, const Edge& v) {
742 // return (u.backward!=v.backward ||
743 // static_cast<typename Graph::Edge>(u)!=
744 // static_cast<typename Graph::Edge>(v));
746 bool operator==(const Edge& v) const {
747 return (this->backward==v.backward &&
748 static_cast<typename Graph::Edge>(*this)==
749 static_cast<typename Graph::Edge>(v));
751 bool operator!=(const Edge& v) const {
752 return (this->backward!=v.backward ||
753 static_cast<typename Graph::Edge>(*this)!=
754 static_cast<typename Graph::Edge>(v));
758 class OutEdgeIt : public Edge {
759 friend class SubBidirGraphWrapper<Graph,
760 ForwardFilterMap, BackwardFilterMap>;
762 const SubBidirGraphWrapper<Graph,
763 ForwardFilterMap, BackwardFilterMap>* gw;
766 OutEdgeIt(Invalid i) : Edge(i) { }
767 //the unique invalid iterator
768 OutEdgeIt(const SubBidirGraphWrapper<Graph,
769 ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
770 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
771 while (*static_cast<GraphEdge*>(this)!=INVALID &&
772 !(*(gw->forward_filter))[*this])
773 *(static_cast<GraphEdge*>(this))=
774 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
775 if (*static_cast<GraphEdge*>(this)==INVALID) {
776 *static_cast<Edge*>(this)=
777 Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true);
778 while (*static_cast<GraphEdge*>(this)!=INVALID &&
779 !(*(gw->backward_filter))[*this])
780 *(static_cast<GraphEdge*>(this))=
781 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
784 OutEdgeIt(const SubBidirGraphWrapper<Graph,
785 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
786 Edge(e), gw(&_gw) { }
787 OutEdgeIt& operator++() {
788 if (!this->backward) {
789 Node n=gw->tail(*this);
790 *(static_cast<GraphEdge*>(this))=
791 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
792 while (*static_cast<GraphEdge*>(this)!=INVALID &&
793 !(*(gw->forward_filter))[*this])
794 *(static_cast<GraphEdge*>(this))=
795 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
796 if (*static_cast<GraphEdge*>(this)==INVALID) {
797 *static_cast<Edge*>(this)=
798 Edge(typename Graph::InEdgeIt(*(gw->graph), n), true);
799 while (*static_cast<GraphEdge*>(this)!=INVALID &&
800 !(*(gw->backward_filter))[*this])
801 *(static_cast<GraphEdge*>(this))=
802 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
805 *(static_cast<GraphEdge*>(this))=
806 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
807 while (*static_cast<GraphEdge*>(this)!=INVALID &&
808 !(*(gw->backward_filter))[*this])
809 *(static_cast<GraphEdge*>(this))=
810 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
816 class InEdgeIt : public Edge {
817 friend class SubBidirGraphWrapper<Graph,
818 ForwardFilterMap, BackwardFilterMap>;
820 const SubBidirGraphWrapper<Graph,
821 ForwardFilterMap, BackwardFilterMap>* gw;
824 InEdgeIt(Invalid i) : Edge(i) { }
825 //the unique invalid iterator
826 InEdgeIt(const SubBidirGraphWrapper<Graph,
827 ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
828 Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
829 while (*static_cast<GraphEdge*>(this)!=INVALID &&
830 !(*(gw->forward_filter))[*this])
831 *(static_cast<GraphEdge*>(this))=
832 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
833 if (*static_cast<GraphEdge*>(this)==INVALID) {
834 *static_cast<Edge*>(this)=
835 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true);
836 while (*static_cast<GraphEdge*>(this)!=INVALID &&
837 !(*(gw->backward_filter))[*this])
838 *(static_cast<GraphEdge*>(this))=
839 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
842 InEdgeIt(const SubBidirGraphWrapper<Graph,
843 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
844 Edge(e), gw(&_gw) { }
845 InEdgeIt& operator++() {
846 if (!this->backward) {
847 Node n=gw->tail(*this);
848 *(static_cast<GraphEdge*>(this))=
849 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
850 while (*static_cast<GraphEdge*>(this)!=INVALID &&
851 !(*(gw->forward_filter))[*this])
852 *(static_cast<GraphEdge*>(this))=
853 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
854 if (*static_cast<GraphEdge*>(this)==INVALID) {
855 *static_cast<Edge*>(this)=
856 Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true);
857 while (*static_cast<GraphEdge*>(this)!=INVALID &&
858 !(*(gw->backward_filter))[*this])
859 *(static_cast<GraphEdge*>(this))=
860 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
863 *(static_cast<GraphEdge*>(this))=
864 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
865 while (*static_cast<GraphEdge*>(this)!=INVALID &&
866 !(*(gw->backward_filter))[*this])
867 *(static_cast<GraphEdge*>(this))=
868 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
874 class EdgeIt : public Edge {
875 friend class SubBidirGraphWrapper<Graph,
876 ForwardFilterMap, BackwardFilterMap>;
878 const SubBidirGraphWrapper<Graph,
879 ForwardFilterMap, BackwardFilterMap>* gw;
882 EdgeIt(Invalid i) : Edge(i) { }
883 //the unique invalid iterator
884 EdgeIt(const SubBidirGraphWrapper<Graph,
885 ForwardFilterMap, BackwardFilterMap>& _gw) :
886 Edge(typename Graph::OutEdgeIt(*(_gw.graph)), false), gw(&_gw) {
887 while (*static_cast<GraphEdge*>(this)!=INVALID &&
888 !(*(gw->forward_filter))[*this])
889 *(static_cast<GraphEdge*>(this))=
890 ++(typename Graph::EdgeIt(*(gw->graph), *this));
891 if (*static_cast<GraphEdge*>(this)==INVALID) {
892 *static_cast<Edge*>(this)=
893 Edge(typename Graph::EdgeIt(*(_gw.graph)), true);
894 while (*static_cast<GraphEdge*>(this)!=INVALID &&
895 !(*(gw->backward_filter))[*this])
896 *(static_cast<GraphEdge*>(this))=
897 ++(typename Graph::EdgeIt(*(gw->graph), *this));
900 EdgeIt(const SubBidirGraphWrapper<Graph,
901 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
902 Edge(e), gw(&_gw) { }
903 EdgeIt& operator++() {
904 if (!this->backward) {
905 *(static_cast<GraphEdge*>(this))=
906 ++(typename Graph::EdgeIt(*(gw->graph), *this));
907 while (*static_cast<GraphEdge*>(this)!=INVALID &&
908 !(*(gw->forward_filter))[*this])
909 *(static_cast<GraphEdge*>(this))=
910 ++(typename Graph::EdgeIt(*(gw->graph), *this));
911 if (*static_cast<GraphEdge*>(this)==INVALID) {
912 *static_cast<Edge*>(this)=
913 Edge(typename Graph::EdgeIt(*(gw->graph)), true);
914 while (*static_cast<GraphEdge*>(this)!=INVALID &&
915 !(*(gw->backward_filter))[*this])
916 *(static_cast<GraphEdge*>(this))=
917 ++(typename Graph::EdgeIt(*(gw->graph), *this));
920 *(static_cast<GraphEdge*>(this))=
921 ++(typename Graph::EdgeIt(*(gw->graph), *this));
922 while (*static_cast<GraphEdge*>(this)!=INVALID &&
923 !(*(gw->backward_filter))[*this])
924 *(static_cast<GraphEdge*>(this))=
925 ++(typename Graph::EdgeIt(*(gw->graph), *this));
931 using GraphWrapper<Graph>::first;
932 // NodeIt& first(NodeIt& i) const {
933 // i=NodeIt(*this); return i;
935 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
936 i=OutEdgeIt(*this, p); return i;
938 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
939 i=InEdgeIt(*this, p); return i;
941 EdgeIt& first(EdgeIt& i) const {
942 i=EdgeIt(*this); return i;
945 // using GraphWrapper<Graph>::next;
946 // // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
947 // OutEdgeIt& next(OutEdgeIt& e) const {
948 // if (!e.backward) {
949 // Node v=this->graph->aNode(e.out);
950 // this->graph->next(e.out);
951 // while(this->graph->valid(e.out) && !(*forward_filter)[e]) {
952 // this->graph->next(e.out); }
953 // if (!this->graph->valid(e.out)) {
955 // this->graph->first(e.in, v);
956 // while(this->graph->valid(e.in) && !(*backward_filter)[e]) {
957 // this->graph->next(e.in); }
960 // this->graph->next(e.in);
961 // while(this->graph->valid(e.in) && !(*backward_filter)[e]) {
962 // this->graph->next(e.in); }
966 // // FIXME Not tested
967 // InEdgeIt& next(InEdgeIt& e) const {
968 // if (!e.backward) {
969 // Node v=this->graph->aNode(e.in);
970 // this->graph->next(e.in);
971 // while(this->graph->valid(e.in) && !(*forward_filter)[e]) {
972 // this->graph->next(e.in); }
973 // if (!this->graph->valid(e.in)) {
975 // this->graph->first(e.out, v);
976 // while(this->graph->valid(e.out) && !(*backward_filter)[e]) {
977 // this->graph->next(e.out); }
980 // this->graph->next(e.out);
981 // while(this->graph->valid(e.out) && !(*backward_filter)[e]) {
982 // this->graph->next(e.out); }
986 // EdgeIt& next(EdgeIt& e) const {
987 // if (!e.backward) {
988 // this->graph->next(e.e);
989 // while(this->graph->valid(e.e) && !(*forward_filter)[e]) {
990 // this->graph->next(e.e); }
991 // if (!this->graph->valid(e.e)) {
993 // this->graph->first(e.e);
994 // while(this->graph->valid(e.e) && !(*backward_filter)[e]) {
995 // this->graph->next(e.e); }
998 // this->graph->next(e.e);
999 // while(this->graph->valid(e.e) && !(*backward_filter)[e]) {
1000 // this->graph->next(e.e); }
1005 Node tail(Edge e) const {
1006 return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
1007 Node head(Edge e) const {
1008 return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
1010 // Node aNode(OutEdgeIt e) const {
1011 // return ((!e.backward) ? this->graph->aNode(e.out) :
1012 // this->graph->aNode(e.in)); }
1013 // Node bNode(OutEdgeIt e) const {
1014 // return ((!e.backward) ? this->graph->bNode(e.out) :
1015 // this->graph->bNode(e.in)); }
1017 // Node aNode(InEdgeIt e) const {
1018 // return ((!e.backward) ? this->graph->aNode(e.in) :
1019 // this->graph->aNode(e.out)); }
1020 // Node bNode(InEdgeIt e) const {
1021 // return ((!e.backward) ? this->graph->bNode(e.in) :
1022 // this->graph->bNode(e.out)); }
1024 /// Gives back the opposite edge.
1025 Edge opposite(const Edge& e) const {
1027 f.backward=!f.backward;
1031 /// \warning This is a linear time operation and works only if
1032 /// \c Graph::EdgeIt is defined.
1033 int edgeNum() const {
1035 for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
1039 bool forward(const Edge& e) const { return !e.backward; }
1040 bool backward(const Edge& e) const { return e.backward; }
1043 template <typename T>
1044 /// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two
1045 /// Graph::EdgeMap one for the forward edges and
1046 /// one for the backward edges.
1048 typename Graph::template EdgeMap<T> forward_map, backward_map;
1050 typedef T ValueType;
1051 typedef Edge KeyType;
1052 EdgeMap(const SubBidirGraphWrapper<Graph,
1053 ForwardFilterMap, BackwardFilterMap>& g) :
1054 forward_map(*(g.graph)), backward_map(*(g.graph)) { }
1055 EdgeMap(const SubBidirGraphWrapper<Graph,
1056 ForwardFilterMap, BackwardFilterMap>& g, T a) :
1057 forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
1058 void set(Edge e, T a) {
1060 forward_map.set(e, a);
1062 backward_map.set(e, a);
1064 T operator[](Edge e) const {
1066 return forward_map[e];
1068 return backward_map[e];
1071 forward_map.update();
1072 backward_map.update();
1074 // T get(Edge e) const {
1076 // return forward_map.get(e.out);
1078 // return backward_map.get(e.in);
1084 ///\brief A wrapper for composing bidirected graph from a directed one.
1086 /// A wrapper for composing bidirected graph from a directed one.
1087 /// A bidirected graph is composed over the directed one without physical
1088 /// storage. As the oppositely directed edges are logically different ones
1089 /// the maps are able to attach different values for them.
1090 template<typename Graph>
1091 class BidirGraphWrapper :
1092 public SubBidirGraphWrapper<
1094 ConstMap<typename Graph::Edge, bool>,
1095 ConstMap<typename Graph::Edge, bool> > {
1097 typedef SubBidirGraphWrapper<
1099 ConstMap<typename Graph::Edge, bool>,
1100 ConstMap<typename Graph::Edge, bool> > Parent;
1102 ConstMap<typename Graph::Edge, bool> cm;
1104 BidirGraphWrapper() : Parent(), cm(true) {
1105 Parent::setForwardFilterMap(cm);
1106 Parent::setBackwardFilterMap(cm);
1109 BidirGraphWrapper(Graph& _graph) : Parent() {
1110 Parent::setGraph(_graph);
1111 Parent::setForwardFilterMap(cm);
1112 Parent::setBackwardFilterMap(cm);
1115 int edgeNum() const {
1116 return 2*this->graph->edgeNum();
1122 // this is a direct implementation of the bidirected-graph wrapper.
1123 // in early hugo, it was implemented that way.
1124 template<typename Graph>
1125 class OldBidirGraphWrapper : public GraphWrapper<Graph> {
1127 typedef GraphWrapper<Graph> Parent;
1129 OldBidirGraphWrapper() : GraphWrapper<Graph>() { }
1133 OldBidirGraphWrapper(Graph& _graph) :
1134 GraphWrapper<Graph>(_graph) { }
1139 friend class OutEdgeIt;
1141 //template<typename T> class NodeMap;
1142 template<typename T> class EdgeMap;
1144 typedef typename GraphWrapper<Graph>::Node Node;
1145 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1147 class Edge : public Graph::Edge {
1148 friend class OldBidirGraphWrapper<Graph>;
1149 ///\bug ez nem is kell
1150 //template<typename T> friend class NodeMap;
1151 template<typename T> friend class EdgeMap;
1153 bool backward; //true, iff backward
1154 // typename Graph::Edge e;
1157 ///\bug =false kell-e? zsoltnak kell az addEdge miatt
1158 Edge(const typename Graph::Edge& _e, bool _backward=false) :
1159 Graph::Edge(_e), backward(_backward) { }
1160 Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
1161 //the unique invalid iterator
1162 friend bool operator==(const Edge& u, const Edge& v) {
1163 return (v.backward==u.backward &&
1164 static_cast<typename Graph::Edge>(u)==
1165 static_cast<typename Graph::Edge>(v));
1167 friend bool operator!=(const Edge& u, const Edge& v) {
1168 return (v.backward!=u.backward ||
1169 static_cast<typename Graph::Edge>(u)!=
1170 static_cast<typename Graph::Edge>(v));
1175 friend class OldBidirGraphWrapper<Graph>;
1177 typename Graph::OutEdgeIt out;
1178 typename Graph::InEdgeIt in;
1183 // OutEdgeIt(const Edge& e) : Edge(e) { }
1184 OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1185 //the unique invalid iterator
1186 OutEdgeIt(const OldBidirGraphWrapper<Graph>& _G, Node v) {
1188 _G.graph->first(out, v);
1189 while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
1190 if (!_G.graph->valid(out)) {
1192 _G.graph->first(in, v);
1193 while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
1196 operator Edge() const {
1198 // e.forward=this->forward;
1199 // if (this->forward) e=out; else e=in;
1202 return Edge(in, this->backward);
1204 return Edge(out, this->backward);
1209 friend class OldBidirGraphWrapper<Graph>;
1211 typename Graph::OutEdgeIt out;
1212 typename Graph::InEdgeIt in;
1217 // OutEdgeIt(const Edge& e) : Edge(e) { }
1218 InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1219 //the unique invalid iterator
1220 InEdgeIt(const OldBidirGraphWrapper<Graph>& _G, Node v) {
1222 _G.graph->first(in, v);
1223 while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
1224 if (!_G.graph->valid(in)) {
1226 _G.graph->first(out, v);
1227 while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
1230 operator Edge() const {
1232 // e.forward=this->forward;
1233 // if (this->forward) e=out; else e=in;
1236 return Edge(out, this->backward);
1238 return Edge(in, this->backward);
1243 friend class OldBidirGraphWrapper<Graph>;
1245 typename Graph::EdgeIt e;
1249 EdgeIt(const Invalid& i) : e(i), backward(true) { }
1250 EdgeIt(const OldBidirGraphWrapper<Graph>& _G) {
1253 while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
1254 if (!_G.graph->valid(e)) {
1257 while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
1260 operator Edge() const {
1261 return Edge(e, this->backward);
1265 using GraphWrapper<Graph>::first;
1266 // NodeIt& first(NodeIt& i) const {
1267 // i=NodeIt(*this); return i;
1269 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1270 i=OutEdgeIt(*this, p); return i;
1273 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1274 i=InEdgeIt(*this, p); return i;
1276 EdgeIt& first(EdgeIt& i) const {
1277 i=EdgeIt(*this); return i;
1280 using GraphWrapper<Graph>::next;
1281 // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
1282 OutEdgeIt& next(OutEdgeIt& e) const {
1284 Node v=this->graph->aNode(e.out);
1285 this->graph->next(e.out);
1286 while(this->graph->valid(e.out) && !enabled(e)) {
1287 this->graph->next(e.out); }
1288 if (!this->graph->valid(e.out)) {
1290 this->graph->first(e.in, v);
1291 while(this->graph->valid(e.in) && !enabled(e)) {
1292 this->graph->next(e.in); }
1295 this->graph->next(e.in);
1296 while(this->graph->valid(e.in) && !enabled(e)) {
1297 this->graph->next(e.in); }
1302 InEdgeIt& next(InEdgeIt& e) const {
1304 Node v=this->graph->aNode(e.in);
1305 this->graph->next(e.in);
1306 while(this->graph->valid(e.in) && !enabled(e)) {
1307 this->graph->next(e.in); }
1308 if (!this->graph->valid(e.in)) {
1310 this->graph->first(e.out, v);
1311 while(this->graph->valid(e.out) && !enabled(e)) {
1312 this->graph->next(e.out); }
1315 this->graph->next(e.out);
1316 while(this->graph->valid(e.out) && !enabled(e)) {
1317 this->graph->next(e.out); }
1321 EdgeIt& next(EdgeIt& e) const {
1323 this->graph->next(e.e);
1324 while(this->graph->valid(e.e) && !enabled(e)) {
1325 this->graph->next(e.e); }
1326 if (!this->graph->valid(e.e)) {
1328 this->graph->first(e.e);
1329 while(this->graph->valid(e.e) && !enabled(e)) {
1330 this->graph->next(e.e); }
1333 this->graph->next(e.e);
1334 while(this->graph->valid(e.e) && !enabled(e)) {
1335 this->graph->next(e.e); }
1340 Node tail(Edge e) const {
1341 return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
1342 Node head(Edge e) const {
1343 return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
1345 Node aNode(OutEdgeIt e) const {
1346 return ((!e.backward) ? this->graph->aNode(e.out) :
1347 this->graph->aNode(e.in)); }
1348 Node bNode(OutEdgeIt e) const {
1349 return ((!e.backward) ? this->graph->bNode(e.out) :
1350 this->graph->bNode(e.in)); }
1352 Node aNode(InEdgeIt e) const {
1353 return ((!e.backward) ? this->graph->aNode(e.in) :
1354 this->graph->aNode(e.out)); }
1355 Node bNode(InEdgeIt e) const {
1356 return ((!e.backward) ? this->graph->bNode(e.in) :
1357 this->graph->bNode(e.out)); }
1359 /// Gives back the opposite edge.
1360 Edge opposite(const Edge& e) const {
1362 f.backward=!f.backward;
1366 // int nodeNum() const { return graph->nodeNum(); }
1368 void edgeNum() const { }
1369 //int edgeNum() const { return graph->edgeNum(); }
1372 // int id(Node v) const { return graph->id(v); }
1374 bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
1375 bool valid(Edge e) const {
1376 return this->graph->valid(e);
1377 //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
1380 bool forward(const Edge& e) const { return !e.backward; }
1381 bool backward(const Edge& e) const { return e.backward; }
1383 bool enabled(const Edge& e) const {
1385 // return (capacity->get(e.out)-flow->get(e.out));
1386 //return ((*capacity)[e]-(*flow)[e]);
1389 // return (flow->get(e.in));
1390 //return ((*flow)[e]);
1394 // Number enabled(typename Graph::OutEdgeIt out) const {
1395 // // return (capacity->get(out)-flow->get(out));
1396 // return ((*capacity)[out]-(*flow)[out]);
1399 // Number enabled(typename Graph::InEdgeIt in) const {
1400 // // return (flow->get(in));
1401 // return ((*flow)[in]);
1404 template <typename T>
1406 typename Graph::template EdgeMap<T> forward_map, backward_map;
1408 typedef T ValueType;
1409 typedef Edge KeyType;
1410 EdgeMap(const OldBidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1411 EdgeMap(const OldBidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1412 void set(Edge e, T a) {
1414 forward_map.set(e/*.out*/, a);
1416 backward_map.set(e/*.in*/, a);
1418 T operator[](Edge e) const {
1420 return forward_map[e/*.out*/];
1422 return backward_map[e/*.in*/];
1425 forward_map.update();
1426 backward_map.update();
1428 // T get(Edge e) const {
1430 // return forward_map.get(e.out);
1432 // return backward_map.get(e.in);
1439 /// \brief A bidirected graph template.
1441 /// A bidirected graph template.
1442 /// Such a bidirected graph stores each pair of oppositely directed edges
1443 /// ones in the memory, i.e. a directed graph of type
1444 /// \c Graph is used for that.
1445 /// As the oppositely directed edges are logically different ones
1446 /// the maps are able to attach different values for them.
1448 template<typename Graph>
1449 class BidirGraph : public BidirGraphWrapper<Graph> {
1451 typedef UndirGraphWrapper<Graph> Parent;
1455 BidirGraph() : BidirGraphWrapper<Graph>() {
1456 Parent::setGraph(gr);
1462 template<typename Graph, typename Number,
1463 typename CapacityMap, typename FlowMap>
1464 class ResForwardFilter {
1465 // const Graph* graph;
1466 const CapacityMap* capacity;
1467 const FlowMap* flow;
1469 ResForwardFilter(/*const Graph& _graph, */
1470 const CapacityMap& _capacity, const FlowMap& _flow) :
1471 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1472 ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1473 //void setGraph(const Graph& _graph) { graph=&_graph; }
1474 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1475 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1476 bool operator[](const typename Graph::Edge& e) const {
1477 return (Number((*flow)[e]) < Number((*capacity)[e]));
1481 template<typename Graph, typename Number,
1482 typename CapacityMap, typename FlowMap>
1483 class ResBackwardFilter {
1484 //const Graph* graph;
1485 const CapacityMap* capacity;
1486 const FlowMap* flow;
1488 ResBackwardFilter(/*const Graph& _graph,*/
1489 const CapacityMap& _capacity, const FlowMap& _flow) :
1490 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1491 ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1492 //void setGraph(const Graph& _graph) { graph=&_graph; }
1493 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1494 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1495 bool operator[](const typename Graph::Edge& e) const {
1496 return (Number(0) < Number((*flow)[e]));
1501 /// A wrapper for composing the residual graph for directed flow and circulation problems.
1503 /// A wrapper for composing the residual graph for directed flow and circulation problems.
1504 template<typename Graph, typename Number,
1505 typename CapacityMap, typename FlowMap>
1506 class ResGraphWrapper :
1507 public SubBidirGraphWrapper<
1509 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1510 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1512 typedef SubBidirGraphWrapper<
1514 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1515 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1517 const CapacityMap* capacity;
1519 ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1520 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1521 ResGraphWrapper() : Parent(),
1522 capacity(0), flow(0) { }
1523 void setCapacityMap(const CapacityMap& _capacity) {
1524 capacity=&_capacity;
1525 forward_filter.setCapacity(_capacity);
1526 backward_filter.setCapacity(_capacity);
1528 void setFlowMap(FlowMap& _flow) {
1530 forward_filter.setFlow(_flow);
1531 backward_filter.setFlow(_flow);
1533 // /// \bug does graph reference needed in filtermaps??
1534 // void setGraph(const Graph& _graph) {
1535 // Parent::setGraph(_graph);
1536 // forward_filter.setGraph(_graph);
1537 // backward_filter.setGraph(_graph);
1540 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1542 Parent(), capacity(&_capacity), flow(&_flow),
1543 forward_filter(/*_graph,*/ _capacity, _flow),
1544 backward_filter(/*_graph,*/ _capacity, _flow) {
1545 Parent::setGraph(_graph);
1546 Parent::setForwardFilterMap(forward_filter);
1547 Parent::setBackwardFilterMap(backward_filter);
1550 typedef typename Parent::Edge Edge;
1552 // bool forward(const Parent::Edge& e) const { return Parent::forward(e); }
1553 //bool backward(const Edge& e) const { return e.backward; }
1555 void augment(const Edge& e, Number a) const {
1556 if (Parent::forward(e))
1557 // flow->set(e.out, flow->get(e.out)+a);
1558 flow->set(e, (*flow)[e]+a);
1560 //flow->set(e.in, flow->get(e.in)-a);
1561 flow->set(e, (*flow)[e]-a);
1566 Number resCap(const Edge& e) const {
1567 if (Parent::forward(e))
1568 // return (capacity->get(e.out)-flow->get(e.out));
1569 return ((*capacity)[e]-(*flow)[e]);
1571 // return (flow->get(e.in));
1572 return ((*flow)[e]);
1575 /// \brief Residual capacity map.
1577 /// In generic residual graphs the residual capacity can be obtained as a map. Not tested.
1580 const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
1582 typedef Number ValueType;
1583 typedef Edge KeyType;
1584 ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _res_graph) :
1585 res_graph(&_res_graph) { }
1586 Number operator[](const Edge& e) const {
1587 if (res_graph->forward(e))
1588 // return (capacity->get(e.out)-flow->get(e.out));
1589 return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1591 // return (flow->get(e.in));
1592 return (*(res_graph->flow))[e];
1594 /// \bug not needed with dynamic maps, or does it?
1601 template<typename Graph, typename Number,
1602 typename CapacityMap, typename FlowMap>
1603 class OldResGraphWrapper : public GraphWrapper<Graph> {
1605 typedef GraphWrapper<Graph> Parent;
1607 const CapacityMap* capacity;
1610 OldResGraphWrapper() : GraphWrapper<Graph>(0),
1611 capacity(0), flow(0) { }
1612 void setCapacityMap(const CapacityMap& _capacity) {
1613 capacity=&_capacity;
1615 void setFlowMap(FlowMap& _flow) {
1621 OldResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1623 GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
1628 friend class OutEdgeIt;
1630 typedef typename GraphWrapper<Graph>::Node Node;
1631 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1632 class Edge : public Graph::Edge {
1633 friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1635 bool backward; //true, iff backward
1636 // typename Graph::Edge e;
1639 Edge(const typename Graph::Edge& _e, bool _backward) :
1640 Graph::Edge(_e), backward(_backward) { }
1641 Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
1642 //the unique invalid iterator
1643 friend bool operator==(const Edge& u, const Edge& v) {
1644 return (v.backward==u.backward &&
1645 static_cast<typename Graph::Edge>(u)==
1646 static_cast<typename Graph::Edge>(v));
1648 friend bool operator!=(const Edge& u, const Edge& v) {
1649 return (v.backward!=u.backward ||
1650 static_cast<typename Graph::Edge>(u)!=
1651 static_cast<typename Graph::Edge>(v));
1656 friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1658 typename Graph::OutEdgeIt out;
1659 typename Graph::InEdgeIt in;
1664 // OutEdgeIt(const Edge& e) : Edge(e) { }
1665 OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1666 //the unique invalid iterator
1667 OutEdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
1669 _G.graph->first(out, v);
1670 while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
1671 if (!_G.graph->valid(out)) {
1673 _G.graph->first(in, v);
1674 while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
1677 operator Edge() const {
1679 // e.forward=this->forward;
1680 // if (this->forward) e=out; else e=in;
1683 return Edge(in, this->backward);
1685 return Edge(out, this->backward);
1690 friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1692 typename Graph::OutEdgeIt out;
1693 typename Graph::InEdgeIt in;
1698 // OutEdgeIt(const Edge& e) : Edge(e) { }
1699 InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1700 //the unique invalid iterator
1701 InEdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
1703 _G.graph->first(in, v);
1704 while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
1705 if (!_G.graph->valid(in)) {
1707 _G.graph->first(out, v);
1708 while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
1711 operator Edge() const {
1713 // e.forward=this->forward;
1714 // if (this->forward) e=out; else e=in;
1717 return Edge(out, this->backward);
1719 return Edge(in, this->backward);
1724 friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1726 typename Graph::EdgeIt e;
1730 EdgeIt(const Invalid& i) : e(i), backward(true) { }
1731 EdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) {
1734 while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
1735 if (!_G.graph->valid(e)) {
1738 while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
1741 operator Edge() const {
1742 return Edge(e, this->backward);
1746 using GraphWrapper<Graph>::first;
1747 // NodeIt& first(NodeIt& i) const {
1748 // i=NodeIt(*this); return i;
1750 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1751 i=OutEdgeIt(*this, p); return i;
1754 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1755 i=InEdgeIt(*this, p); return i;
1757 EdgeIt& first(EdgeIt& i) const {
1758 i=EdgeIt(*this); return i;
1761 using GraphWrapper<Graph>::next;
1762 // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
1763 OutEdgeIt& next(OutEdgeIt& e) const {
1765 Node v=this->graph->aNode(e.out);
1766 this->graph->next(e.out);
1767 while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1768 this->graph->next(e.out); }
1769 if (!this->graph->valid(e.out)) {
1771 this->graph->first(e.in, v);
1772 while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1773 this->graph->next(e.in); }
1776 this->graph->next(e.in);
1777 while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1778 this->graph->next(e.in); }
1783 InEdgeIt& next(InEdgeIt& e) const {
1785 Node v=this->graph->aNode(e.in);
1786 this->graph->next(e.in);
1787 while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1788 this->graph->next(e.in); }
1789 if (!this->graph->valid(e.in)) {
1791 this->graph->first(e.out, v);
1792 while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1793 this->graph->next(e.out); }
1796 this->graph->next(e.out);
1797 while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1798 this->graph->next(e.out); }
1802 EdgeIt& next(EdgeIt& e) const {
1804 this->graph->next(e.e);
1805 while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1806 this->graph->next(e.e); }
1807 if (!this->graph->valid(e.e)) {
1809 this->graph->first(e.e);
1810 while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1811 this->graph->next(e.e); }
1814 this->graph->next(e.e);
1815 while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1816 this->graph->next(e.e); }
1821 Node tail(Edge e) const {
1822 return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
1823 Node head(Edge e) const {
1824 return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
1826 Node aNode(OutEdgeIt e) const {
1827 return ((!e.backward) ? this->graph->aNode(e.out) :
1828 this->graph->aNode(e.in)); }
1829 Node bNode(OutEdgeIt e) const {
1830 return ((!e.backward) ? this->graph->bNode(e.out) :
1831 this->graph->bNode(e.in)); }
1833 Node aNode(InEdgeIt e) const {
1834 return ((!e.backward) ? this->graph->aNode(e.in) :
1835 this->graph->aNode(e.out)); }
1836 Node bNode(InEdgeIt e) const {
1837 return ((!e.backward) ? this->graph->bNode(e.in) :
1838 this->graph->bNode(e.out)); }
1840 // int nodeNum() const { return graph->nodeNum(); }
1842 void edgeNum() const { }
1843 //int edgeNum() const { return graph->edgeNum(); }
1846 // int id(Node v) const { return graph->id(v); }
1848 bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
1849 bool valid(Edge e) const {
1850 return this->graph->valid(e);
1851 //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
1854 bool forward(const Edge& e) const { return !e.backward; }
1855 bool backward(const Edge& e) const { return e.backward; }
1857 void augment(const Edge& e, Number a) const {
1859 // flow->set(e.out, flow->get(e.out)+a);
1860 flow->set(e, (*flow)[e]+a);
1862 // flow->set(e.in, flow->get(e.in)-a);
1863 flow->set(e, (*flow)[e]-a);
1866 Number resCap(const Edge& e) const {
1868 // return (capacity->get(e.out)-flow->get(e.out));
1869 return ((*capacity)[e]-(*flow)[e]);
1871 // return (flow->get(e.in));
1872 return ((*flow)[e]);
1875 // Number resCap(typename Graph::OutEdgeIt out) const {
1876 // // return (capacity->get(out)-flow->get(out));
1877 // return ((*capacity)[out]-(*flow)[out]);
1880 // Number resCap(typename Graph::InEdgeIt in) const {
1881 // // return (flow->get(in));
1882 // return ((*flow)[in]);
1885 template <typename T>
1887 typename Graph::template EdgeMap<T> forward_map, backward_map;
1889 typedef T ValueType;
1890 typedef Edge KeyType;
1891 EdgeMap(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1892 EdgeMap(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1893 void set(Edge e, T a) {
1895 forward_map.set(e/*.out*/, a);
1897 backward_map.set(e/*.in*/, a);
1899 T operator[](Edge e) const {
1901 return forward_map[e/*.out*/];
1903 return backward_map[e/*.in*/];
1906 forward_map.update();
1907 backward_map.update();
1909 // T get(Edge e) const {
1911 // return forward_map.get(e.out);
1913 // return backward_map.get(e.in);
1920 /// For blocking flows.
1922 /// This graph wrapper is used for on-the-fly
1923 /// Dinits blocking flow computations.
1924 /// For each node, an out-edge is stored which is used when the
1926 /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1930 /// \author Marton Makai
1931 template<typename Graph, typename FirstOutEdgesMap>
1932 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1934 typedef GraphWrapper<Graph> Parent;
1936 FirstOutEdgesMap* first_out_edges;
1938 ErasingFirstGraphWrapper(Graph& _graph,
1939 FirstOutEdgesMap& _first_out_edges) :
1940 GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
1942 typedef typename GraphWrapper<Graph>::Node Node;
1943 typedef typename GraphWrapper<Graph>::Edge Edge;
1944 class OutEdgeIt : public Edge {
1945 friend class GraphWrapper<Graph>;
1946 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1947 const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>* gw;
1950 //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
1951 OutEdgeIt(Invalid i) : Edge(i) { }
1952 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
1954 Edge((*(_gw.first_out_edges))[n]), gw(&_gw) { }
1955 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
1957 Edge(e), gw(&_gw) { }
1958 OutEdgeIt& operator++() {
1959 *(static_cast<Edge*>(this))=
1960 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1965 // friend class GraphWrapper<Graph>;
1966 // friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1967 // // typedef typename Graph::InEdgeIt GraphInEdgeIt;
1968 // typename Graph::InEdgeIt e;
1971 // InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1972 // InEdgeIt(const Invalid& i) : e(i) { }
1973 // InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1974 // const Node& _n) :
1975 // e(*(_G.graph), typename Graph::Node(_n)) { }
1976 // operator Edge() const { return Edge(typename Graph::Edge(e)); }
1978 //typedef typename Graph::SymEdgeIt SymEdgeIt;
1980 // friend class GraphWrapper<Graph>;
1981 // friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1982 // // typedef typename Graph::EdgeIt GraphEdgeIt;
1983 // typename Graph::EdgeIt e;
1986 // EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
1987 // EdgeIt(const Invalid& i) : e(i) { }
1988 // EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1989 // e(*(_G.graph)) { }
1990 // operator Edge() const { return Edge(typename Graph::Edge(e)); }
1993 using GraphWrapper<Graph>::first;
1994 // NodeIt& first(NodeIt& i) const {
1995 // i=NodeIt(*this); return i;
1997 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1998 i=OutEdgeIt(*this, p); return i;
2000 // InEdgeIt& first(InEdgeIt& i, const Node& p) const {
2001 // i=InEdgeIt(*this, p); return i;
2003 // EdgeIt& first(EdgeIt& i) const {
2004 // i=EdgeIt(*this); return i;
2007 // using GraphWrapper<Graph>::next;
2008 // // NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
2009 // OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
2010 // InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
2011 // EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }
2013 // Node aNode(const OutEdgeIt& e) const {
2014 // return Node(this->graph->aNode(e.e)); }
2015 // Node aNode(const InEdgeIt& e) const {
2016 // return Node(this->graph->aNode(e.e)); }
2017 // Node bNode(const OutEdgeIt& e) const {
2018 // return Node(this->graph->bNode(e.e)); }
2019 // Node bNode(const InEdgeIt& e) const {
2020 // return Node(this->graph->bNode(e.e)); }
2022 void erase(const Edge& e) const {
2024 typename Graph::OutEdgeIt f(*graph, n);
2026 first_out_edges->set(n, f);
2034 #endif //HUGO_GRAPH_WRAPPER_H