2 #ifndef GRAPH_WRAPPER_H
3 #define GRAPH_WRAPPER_H
9 template<typename Graph>
10 class TrivGraphWrapper {
15 typedef Graph BaseGraph;
17 typedef typename Graph::Node Node;
18 typedef typename Graph::NodeIt NodeIt;
20 typedef typename Graph::Edge Edge;
21 typedef typename Graph::OutEdgeIt OutEdgeIt;
22 typedef typename Graph::InEdgeIt InEdgeIt;
23 //typedef typename Graph::SymEdgeIt SymEdgeIt;
24 typedef typename Graph::EdgeIt EdgeIt;
26 //TrivGraphWrapper() : graph(0) { }
27 TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
29 void setGraph(Graph& _graph) { graph = &_graph; }
30 Graph& getGraph() const { return (*graph); }
32 template<typename I> I& first(I& i) const { return graph->first(i); }
33 template<typename I, typename P> I& first(I& i, const P& p) const {
34 return graph->first(i, p); }
36 template<typename I> I getNext(const I& i) const {
37 return graph->getNext(i); }
38 template<typename I> I& next(I &i) const { return graph->next(i); }
40 template< typename It > It first() const {
41 It e; first(e); return e; }
43 template< typename It > It first(const Node& v) const {
44 It e; first(e, v); return e; }
46 Node head(const Edge& e) const { return graph->head(e); }
47 Node tail(const Edge& e) const { return graph->tail(e); }
49 template<typename I> bool valid(const I& i) const
50 { return graph->valid(i); }
52 //template<typename I> void setInvalid(const I &i);
53 //{ return graph->setInvalid(i); }
55 int nodeNum() const { return graph->nodeNum(); }
56 int edgeNum() const { return graph->edgeNum(); }
58 template<typename I> Node aNode(const I& e) const {
59 return graph->aNode(e); }
60 template<typename I> Node bNode(const I& e) const {
61 return graph->bNode(e); }
63 Node addNode() const { return graph->addNode(); }
64 Edge addEdge(const Node& tail, const Node& head) const {
65 return graph->addEdge(tail, head); }
67 template<typename I> void erase(const I& i) const { graph->erase(i); }
69 void clear() const { graph->clear(); }
71 template<typename T> class NodeMap : public Graph::NodeMap<T> {
73 NodeMap(const TrivGraphWrapper<Graph>& _G) :
74 Graph::NodeMap<T>(_G.getGraph()) { }
75 NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :
76 Graph::NodeMap<T>(_G.getGraph(), a) { }
79 template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
81 EdgeMap(const TrivGraphWrapper<Graph>& _G) :
82 Graph::EdgeMap<T>(_G.getGraph()) { }
83 EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :
84 Graph::EdgeMap<T>(_G.getGraph(), a) { }
88 template<typename GraphWrapper>
89 class GraphWrapperSkeleton {
94 typedef typename GraphWrapper::BaseGraph BaseGraph;
96 typedef typename GraphWrapper::Node Node;
97 typedef typename GraphWrapper::NodeIt NodeIt;
99 typedef typename GraphWrapper::Edge Edge;
100 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
101 typedef typename GraphWrapper::InEdgeIt InEdgeIt;
102 //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;
103 typedef typename GraphWrapper::EdgeIt EdgeIt;
105 //GraphWrapperSkeleton() : gw() { }
106 GraphWrapperSkeleton(GraphWrapper _gw) : gw(_gw) { }
108 void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); }
109 BaseGraph& getGraph() const { return gw.getGraph(); }
111 template<typename I> I& first(I& i) const { return gw.first(i); }
112 template<typename I, typename P> I& first(I& i, const P& p) const {
113 return gw.first(i, p); }
115 template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
116 template<typename I> I& next(I &i) const { return gw.next(i); }
118 template< typename It > It first() const {
119 It e; this->first(e); return e; }
121 template< typename It > It first(const Node& v) const {
122 It e; this->first(e, v); return e; }
124 Node head(const Edge& e) const { return gw.head(e); }
125 Node tail(const Edge& e) const { return gw.tail(e); }
127 template<typename I> bool valid(const I& i) const { return gw.valid(i); }
129 //template<typename I> void setInvalid(const I &i);
130 //{ return graph->setInvalid(i); }
132 int nodeNum() const { return gw.nodeNum(); }
133 int edgeNum() const { return gw.edgeNum(); }
135 template<typename I> Node aNode(const I& e) const { return gw.aNode(e); }
136 template<typename I> Node bNode(const I& e) const { return gw.bNode(e); }
138 Node addNode() const { return gw.addNode(); }
139 Edge addEdge(const Node& tail, const Node& head) const {
140 return gw.addEdge(tail, head); }
142 template<typename I> void erase(const I& i) const { gw.erase(i); }
144 void clear() const { gw.clear(); }
146 template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
148 NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) :
149 GraphWrapper::NodeMap<T>(_G.gw) { }
150 NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) :
151 GraphWrapper::NodeMap<T>(_G.gw, a) { }
154 template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
156 EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) :
157 GraphWrapper::EdgeMap<T>(_G.gw) { }
158 EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) :
159 GraphWrapper::EdgeMap<T>(_G.gw, a) { }
163 // template<typename Graph>
164 // class RevGraphWrapper
170 // typedef Graph BaseGraph;
172 // typedef typename Graph::Node Node;
173 // typedef typename Graph::NodeIt NodeIt;
175 // typedef typename Graph::Edge Edge;
176 // typedef typename Graph::OutEdgeIt InEdgeIt;
177 // typedef typename Graph::InEdgeIt OutEdgeIt;
178 // //typedef typename Graph::SymEdgeIt SymEdgeIt;
179 // typedef typename Graph::EdgeIt EdgeIt;
181 // //RevGraphWrapper() : graph(0) { }
182 // RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
184 // void setGraph(Graph& _graph) { graph = &_graph; }
185 // Graph& getGraph() const { return (*graph); }
187 // template<typename I> I& first(I& i) const { return graph->first(i); }
188 // template<typename I, typename P> I& first(I& i, const P& p) const {
189 // return graph->first(i, p); }
191 // template<typename I> I getNext(const I& i) const {
192 // return graph->getNext(i); }
193 // template<typename I> I& next(I &i) const { return graph->next(i); }
195 // template< typename It > It first() const {
196 // It e; first(e); return e; }
198 // template< typename It > It first(const Node& v) const {
199 // It e; first(e, v); return e; }
201 // Node head(const Edge& e) const { return graph->tail(e); }
202 // Node tail(const Edge& e) const { return graph->head(e); }
204 // template<typename I> bool valid(const I& i) const
205 // { return graph->valid(i); }
207 // //template<typename I> void setInvalid(const I &i);
208 // //{ return graph->setInvalid(i); }
210 // template<typename I> Node aNode(const I& e) const {
211 // return graph->aNode(e); }
212 // template<typename I> Node bNode(const I& e) const {
213 // return graph->bNode(e); }
215 // Node addNode() const { return graph->addNode(); }
216 // Edge addEdge(const Node& tail, const Node& head) const {
217 // return graph->addEdge(tail, head); }
219 // int nodeNum() const { return graph->nodeNum(); }
220 // int edgeNum() const { return graph->edgeNum(); }
222 // template<typename I> void erase(const I& i) const { graph->erase(i); }
224 // void clear() const { graph->clear(); }
226 // template<typename T> class NodeMap : public Graph::NodeMap<T> {
228 // NodeMap(const RevGraphWrapper<Graph>& _G) :
229 // Graph::NodeMap<T>(_G.getGraph()) { }
230 // NodeMap(const RevGraphWrapper<Graph>& _G, T a) :
231 // Graph::NodeMap<T>(_G.getGraph(), a) { }
234 // template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
236 // EdgeMap(const RevGraphWrapper<Graph>& _G) :
237 // Graph::EdgeMap<T>(_G.getGraph()) { }
238 // EdgeMap(const RevGraphWrapper<Graph>& _G, T a) :
239 // Graph::EdgeMap<T>(_G.getGraph(), a) { }
243 template<typename /*Graph*/GraphWrapper
244 /*=typename GraphWrapperSkeleton< TrivGraphWrapper<Graph>*/ >
245 class RevGraphWrapper :
246 public GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/ {
251 //typedef Graph BaseGraph;
253 //typedef typename Graph::Node Node;
254 //typedef typename Graph::NodeIt NodeIt;
256 //typedef typename Graph::Edge Edge;
257 typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::OutEdgeIt InEdgeIt;
258 typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::InEdgeIt OutEdgeIt;
259 //typedef typename Graph::SymEdgeIt SymEdgeIt;
260 //typedef typename Graph::EdgeIt EdgeIt;
262 //RevGraphWrapper() : graph(0) { }
263 RevGraphWrapper(GraphWrapper _gw/*BaseGraph& _graph*/) : GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/(_gw/*TrivGraphWrapper<Graph>(_graph)*/) { }
265 //void setGraph(Graph& _graph) { graph = &_graph; }
266 //Graph& getGraph() const { return (*graph); }
268 //template<typename I> I& first(I& i) const { return graph->first(i); }
269 //template<typename I, typename P> I& first(I& i, const P& p) const {
270 // return graph->first(i, p); }
272 //template<typename I> I getNext(const I& i) const {
273 // return graph->getNext(i); }
274 //template<typename I> I& next(I &i) const { return graph->next(i); }
276 //template< typename It > It first() const {
277 // It e; first(e); return e; }
279 //template< typename It > It first(const Node& v) const {
280 // It e; first(e, v); return e; }
282 //Node head(const Edge& e) const { return graph->tail(e); }
283 //Node tail(const Edge& e) const { return graph->head(e); }
285 //template<typename I> bool valid(const I& i) const
286 // { return graph->valid(i); }
288 //template<typename I> void setInvalid(const I &i);
289 //{ return graph->setInvalid(i); }
291 //template<typename I> Node aNode(const I& e) const {
292 // return graph->aNode(e); }
293 //template<typename I> Node bNode(const I& e) const {
294 // return graph->bNode(e); }
296 //Node addNode() const { return graph->addNode(); }
297 //Edge addEdge(const Node& tail, const Node& head) const {
298 // return graph->addEdge(tail, head); }
300 //int nodeNum() const { return graph->nodeNum(); }
301 //int edgeNum() const { return graph->edgeNum(); }
303 //template<typename I> void erase(const I& i) const { graph->erase(i); }
305 //void clear() const { graph->clear(); }
307 template<typename T> class NodeMap :
308 public GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>
311 NodeMap(const RevGraphWrapper<GraphWrapper>& _gw) :
312 GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw) { }
313 NodeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) :
314 GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw, a) { }
317 template<typename T> class EdgeMap :
318 public GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T> {
320 EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw) :
321 GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw) { }
322 EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) :
323 GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw, a) { }
328 template<typename Graph>
329 class UndirGraphWrapper {
334 typedef Graph BaseGraph;
336 typedef typename Graph::Node Node;
337 typedef typename Graph::NodeIt NodeIt;
339 //typedef typename Graph::Edge Edge;
340 //typedef typename Graph::OutEdgeIt OutEdgeIt;
341 //typedef typename Graph::InEdgeIt InEdgeIt;
342 //typedef typename Graph::SymEdgeIt SymEdgeIt;
343 //typedef typename Graph::EdgeIt EdgeIt;
346 typedef typename Graph::Edge GraphEdge;
347 typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
348 typedef typename Graph::InEdgeIt GraphInEdgeIt;
351 //UndirGraphWrapper() : graph(0) { }
352 UndirGraphWrapper(Graph& _graph) : graph(&_graph) { }
354 void setGraph(Graph& _graph) { graph = &_graph; }
355 Graph& getGraph() const { return (*graph); }
358 friend class UndirGraphWrapper<Graph>;
359 bool out_or_in; //true iff out
363 Edge() : out_or_in(), out(), in() { }
364 Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
365 operator GraphEdge() const {
366 if (out_or_in) return(out); else return(in);
368 friend bool operator==(const Edge& u, const Edge& v) {
370 return (u.out_or_in && u.out==v.out);
372 return (!u.out_or_in && u.in==v.in);
374 friend bool operator!=(const Edge& u, const Edge& v) {
376 return (!u.out_or_in || u.out!=v.out);
378 return (u.out_or_in || u.in!=v.in);
382 class OutEdgeIt : public Edge {
383 friend class UndirGraphWrapper<Graph>;
385 OutEdgeIt() : Edge() { }
386 OutEdgeIt(const Invalid& i) : Edge(i) { }
387 OutEdgeIt(const UndirGraphWrapper& _G, const Node& n) : Edge() {
389 _G.graph->first(out, n);
390 if (!(_G.graph->valid(out))) {
392 _G.graph->first(in, n);
397 OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
399 graph->first(e.out, n);
400 if (!(graph->valid(e.out))) {
402 graph->first(e.in, n);
407 OutEdgeIt& next(OutEdgeIt& e) const {
409 Node n=graph->tail(e.out);
411 if (!graph->valid(e.out)) {
413 graph->first(e.in, n);
421 Node aNode(const OutEdgeIt& e) const {
422 if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
423 Node bNode(const OutEdgeIt& e) const {
424 if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
426 typedef OutEdgeIt InEdgeIt;
428 template<typename I> I& first(I& i) const { return graph->first(i); }
429 // template<typename I, typename P> I& first(I& i, const P& p) const {
430 // return graph->first(i, p); }
432 template<typename I> I getNext(const I& i) const {
433 return graph->getNext(i); }
434 template<typename I> I& next(I &i) const { return graph->next(i); }
436 template< typename It > It first() const {
437 It e; first(e); return e; }
439 template< typename It > It first(const Node& v) const {
440 It e; first(e, v); return e; }
442 Node head(const Edge& e) const { return graph->head(e); }
443 Node tail(const Edge& e) const { return graph->tail(e); }
445 template<typename I> bool valid(const I& i) const
446 { return graph->valid(i); }
448 //template<typename I> void setInvalid(const I &i);
449 //{ return graph->setInvalid(i); }
451 int nodeNum() const { return graph->nodeNum(); }
452 int edgeNum() const { return graph->edgeNum(); }
454 // template<typename I> Node aNode(const I& e) const {
455 // return graph->aNode(e); }
456 // template<typename I> Node bNode(const I& e) const {
457 // return graph->bNode(e); }
459 Node addNode() const { return graph->addNode(); }
460 // FIXME: ez igy nem jo, mert nem
461 // Edge addEdge(const Node& tail, const Node& head) const {
462 // return graph->addEdge(tail, head); }
464 template<typename I> void erase(const I& i) const { graph->erase(i); }
466 void clear() const { graph->clear(); }
468 template<typename T> class NodeMap : public Graph::NodeMap<T> {
470 NodeMap(const UndirGraphWrapper<Graph>& _G) :
471 Graph::NodeMap<T>(_G.getGraph()) { }
472 NodeMap(const UndirGraphWrapper<Graph>& _G, T a) :
473 Graph::NodeMap<T>(_G.getGraph(), a) { }
476 template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
478 EdgeMap(const UndirGraphWrapper<Graph>& _G) :
479 Graph::EdgeMap<T>(_G.getGraph()) { }
480 EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) :
481 Graph::EdgeMap<T>(_G.getGraph(), a) { }
487 // template<typename Graph>
488 // class SymGraphWrapper
493 // typedef Graph BaseGraph;
495 // typedef typename Graph::Node Node;
496 // typedef typename Graph::Edge Edge;
498 // typedef typename Graph::NodeIt NodeIt;
500 // //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
501 // //iranyitatlant, ami van
502 // //mert csak 1 dolgot lehet be typedef-elni
503 // typedef typename Graph::OutEdgeIt SymEdgeIt;
504 // //typedef typename Graph::InEdgeIt SymEdgeIt;
505 // //typedef typename Graph::SymEdgeIt SymEdgeIt;
506 // typedef typename Graph::EdgeIt EdgeIt;
508 // int nodeNum() const { return graph->nodeNum(); }
509 // int edgeNum() const { return graph->edgeNum(); }
511 // template<typename I> I& first(I& i) const { return graph->first(i); }
512 // template<typename I, typename P> I& first(I& i, const P& p) const {
513 // return graph->first(i, p); }
514 // //template<typename I> I next(const I i); { return graph->goNext(i); }
515 // //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
517 // template< typename It > It first() const {
518 // It e; first(e); return e; }
520 // template< typename It > It first(Node v) const {
521 // It e; first(e, v); return e; }
523 // Node head(const Edge& e) const { return graph->head(e); }
524 // Node tail(const Edge& e) const { return graph->tail(e); }
526 // template<typename I> Node aNode(const I& e) const {
527 // return graph->aNode(e); }
528 // template<typename I> Node bNode(const I& e) const {
529 // return graph->bNode(e); }
531 // //template<typename I> bool valid(const I i);
532 // //{ return graph->valid(i); }
534 // //template<typename I> void setInvalid(const I &i);
535 // //{ return graph->setInvalid(i); }
537 // Node addNode() { return graph->addNode(); }
538 // Edge addEdge(const Node& tail, const Node& head) {
539 // return graph->addEdge(tail, head); }
541 // template<typename I> void erase(const I& i) { graph->erase(i); }
543 // void clear() { graph->clear(); }
545 // template<typename T> class NodeMap : public Graph::NodeMap<T> { };
546 // template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
548 // void setGraph(Graph& _graph) { graph = &_graph; }
549 // Graph& getGraph() { return (*graph); }
551 // //SymGraphWrapper() : graph(0) { }
552 // SymGraphWrapper(Graph& _graph) : graph(&_graph) { }
556 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
557 class ResGraphWrapper {
559 typedef Graph BaseGraph;
560 typedef typename Graph::Node Node;
561 typedef typename Graph::NodeIt NodeIt;
563 typedef typename Graph::OutEdgeIt OldOutEdgeIt;
564 typedef typename Graph::InEdgeIt OldInEdgeIt;
568 const CapacityMap* capacity;
571 ResGraphWrapper(const Graph& _G, FlowMap& _flow,
572 const CapacityMap& _capacity) :
573 graph(&_G), flow(&_flow), capacity(&_capacity) { }
575 void setGraph(const Graph& _graph) { graph = &_graph; }
576 const Graph& getGraph() const { return (*graph); }
581 friend class OutEdgeIt;
584 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
586 bool out_or_in; //true, iff out
590 Edge() : out_or_in(true) { }
591 Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
592 // bool valid() const {
593 // return out_or_in && out.valid() || in.valid(); }
594 friend bool operator==(const Edge& u, const Edge& v) {
596 return (u.out_or_in && u.out==v.out);
598 return (!u.out_or_in && u.in==v.in);
600 friend bool operator!=(const Edge& u, const Edge& v) {
602 return (!u.out_or_in || u.out!=v.out);
604 return (u.out_or_in || u.in!=v.in);
609 class OutEdgeIt : public Edge {
610 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
614 OutEdgeIt(const Edge& e) : Edge(e) { }
615 OutEdgeIt(const Invalid& i) : Edge(i) { }
617 OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
618 resG.graph->first(out, v);
619 while( resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); }
620 if (!resG.graph->valid(out)) {
622 resG.graph->first(in, v);
623 while( resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); }
627 // OutEdgeIt& operator++() {
629 // Node v=/*resG->*/G->aNode(out);
631 // while( out.valid() && !(Edge::free()>0) ) { ++out; }
632 // if (!out.valid()) {
635 // while( in.valid() && !(Edge::free()>0) ) { ++in; }
639 // while( in.valid() && !(Edge::free()>0) ) { ++in; }
645 class EdgeIt : public Edge {
646 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
647 typename Graph::NodeIt v;
650 //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
651 EdgeIt(const Invalid& i) : Edge(i) { }
652 EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
653 resG.graph->first(v);
654 if (resG.graph->valid(v)) resG.graph->first(out, v); else out=OldOutEdgeIt(INVALID);
655 while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); }
656 while (resG.graph->valid(v) && !resG.graph->valid(out)) {
658 if (resG.graph->valid(v)) resG.graph->first(out, v);
659 while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); }
661 if (!resG.graph->valid(out)) {
663 resG.graph->first(v);
664 if (resG.graph->valid(v)) resG.graph->first(in, v); else in=OldInEdgeIt(INVALID);
665 while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); }
666 while (resG.graph->valid(v) && !resG.graph->valid(in)) {
668 if (resG.graph->valid(v)) resG.graph->first(in, v);
669 while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); }
673 // EdgeIt& operator++() {
676 // while (out.valid() && !(Edge::free()>0) ) { ++out; }
677 // while (v.valid() && !out.valid()) {
679 // if (v.valid()) G->first(out, v);
680 // while (out.valid() && !(Edge::free()>0) ) { ++out; }
682 // if (!out.valid()) {
685 // if (v.valid()) G->first(in, v); else in=OldInEdgeIt();
686 // while (in.valid() && !(Edge::free()>0) ) { ++in; }
687 // while (v.valid() && !in.valid()) {
689 // if (v.valid()) G->first(in, v);
690 // while (in.valid() && !(Edge::free()>0) ) { ++in; }
695 // while (in.valid() && !(Edge::free()>0) ) { ++in; }
696 // while (v.valid() && !in.valid()) {
698 // if (v.valid()) G->first(in, v);
699 // while (in.valid() && !(Edge::free()>0) ) { ++in; }
706 NodeIt& first(NodeIt& v) const { return graph->first(v); }
707 OutEdgeIt& first(OutEdgeIt& e, Node v) const {
708 e=OutEdgeIt(*this, v);
711 EdgeIt& first(EdgeIt& e) const {
716 NodeIt& next(NodeIt& n) const { return graph->next(n); }
718 OutEdgeIt& next(OutEdgeIt& e) const {
720 Node v=graph->aNode(e.out);
722 while( graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); }
723 if (!graph->valid(e.out)) {
725 graph->first(e.in, v);
726 while( graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
730 while( graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
735 EdgeIt& next(EdgeIt& e) const {
738 while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); }
739 while (graph->valid(e.v) && !graph->valid(e.out)) {
741 if (graph->valid(e.v)) graph->first(e.out, e.v);
742 while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); }
744 if (!graph->valid(e.out)) {
747 if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=OldInEdgeIt(INVALID);
748 while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
749 while (graph->valid(e.v) && !graph->valid(e.in)) {
751 if (graph->valid(e.v)) graph->first(e.in, e.v);
752 while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
757 while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
758 while (graph->valid(e.v) && !graph->valid(e.in)) {
760 if (graph->valid(e.v)) graph->first(e.in, e.v);
761 while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
768 template< typename It >
775 template< typename It >
776 It first(Node v) const {
782 Node tail(Edge e) const {
783 return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
784 Node head(Edge e) const {
785 return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
787 Node aNode(OutEdgeIt e) const {
788 return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
789 Node bNode(OutEdgeIt e) const {
790 return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
792 int id(Node v) const { return graph->id(v); }
794 bool valid(Node n) const { return graph->valid(n); }
795 bool valid(Edge e) const {
796 return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); }
798 void augment(const Edge& e, Number a) const {
800 flow->set(e.out, flow->get(e.out)+a);
802 flow->set(e.in, flow->get(e.in)-a);
805 Number free(const Edge& e) const {
807 return (capacity->get(e.out)-flow->get(e.out));
809 return (flow->get(e.in));
812 Number free(OldOutEdgeIt out) const {
813 return (capacity->get(out)-flow->get(out));
816 Number free(OldInEdgeIt in) const {
817 return (flow->get(in));
820 template<typename T> class NodeMap : public Graph::NodeMap<T> {
822 NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
823 : Graph::NodeMap<T>(_G.getGraph()) { }
824 NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
825 T a) : Graph::NodeMap<T>(_G.getGraph(), a) { }
828 // template <typename T>
830 // typename Graph::NodeMap<T> node_map;
832 // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
833 // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
834 // void set(Node nit, T a) { node_map.set(nit, a); }
835 // T get(Node nit) const { return node_map.get(nit); }
838 template <typename T>
840 typename Graph::EdgeMap<T> forward_map, backward_map;
842 EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.getGraph()), backward_map(_G.getGraph()) { }
843 EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.getGraph(), a), backward_map(_G.getGraph(), a) { }
844 void set(Edge e, T a) {
846 forward_map.set(e.out, a);
848 backward_map.set(e.in, a);
852 return forward_map.get(e.out);
854 return backward_map.get(e.in);
859 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
860 class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
862 ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
863 //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
865 ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow,
866 const CapacityMap& _capacity) :
867 ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),
868 first_out_edges(*this) /*, dist(*this)*/ {
869 for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) {
871 ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
872 first_out_edges.set(n, e);
876 //void setGraph(Graph& _graph) { graph = &_graph; }
877 //Graph& getGraph() const { return (*graph); }
879 //TrivGraphWrapper() : graph(0) { }
880 //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }
882 //typedef Graph BaseGraph;
884 //typedef typename Graph::Node Node;
885 //typedef typename Graph::NodeIt NodeIt;
887 //typedef typename Graph::Edge Edge;
888 //typedef typename Graph::OutEdgeIt OutEdgeIt;
889 //typedef typename Graph::InEdgeIt InEdgeIt;
890 //typedef typename Graph::SymEdgeIt SymEdgeIt;
891 //typedef typename Graph::EdgeIt EdgeIt;
893 typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
894 typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
896 typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
897 typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
898 //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
899 //typedef typename Graph::SymEdgeIt SymEdgeIt;
900 //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
902 NodeIt& first(NodeIt& n) const {
903 return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
906 OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
907 e=first_out_edges.get(n);
911 //ROSSZ template<typename I> I& first(I& i) const { return first(i); }
912 //ROSSZ template<typename I, typename P> I& first(I& i, const P& p) const {
913 // return first(i, p); }
915 //template<typename I> I getNext(const I& i) const {
916 // return graph->getNext(i); }
917 //template<typename I> I& next(I &i) const { return graph->next(i); }
919 template< typename It > It first() const {
920 It e; first(e); return e; }
922 template< typename It > It first(const Node& v) const {
923 It e; first(e, v); return e; }
925 //Node head(const Edge& e) const { return graph->head(e); }
926 //Node tail(const Edge& e) const { return graph->tail(e); }
928 //template<typename I> bool valid(const I& i) const
929 // { return graph->valid(i); }
931 //int nodeNum() const { return graph->nodeNum(); }
932 //int edgeNum() const { return graph->edgeNum(); }
934 //template<typename I> Node aNode(const I& e) const {
935 // return graph->aNode(e); }
936 //template<typename I> Node bNode(const I& e) const {
937 // return graph->bNode(e); }
939 //Node addNode() const { return graph->addNode(); }
940 //Edge addEdge(const Node& tail, const Node& head) const {
941 // return graph->addEdge(tail, head); }
943 //void erase(const OutEdgeIt& e) {
944 // first_out_edge(this->tail(e))=e;
946 void erase(const Edge& e) {
949 first_out_edges.set(this->tail(e), f);
951 //template<typename I> void erase(const I& i) const { graph->erase(i); }
953 //void clear() const { graph->clear(); }
955 template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
957 NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
958 ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
959 NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
960 ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
963 template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
965 EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
966 ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
967 EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
968 ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
972 template<typename GraphWrapper>
973 class FilterGraphWrapper {
976 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
977 class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
982 //typedef Graph BaseGraph;
984 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
985 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
987 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
988 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
989 //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
990 //typedef typename Graph::SymEdgeIt SymEdgeIt;
991 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
993 //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
996 FilterGraphWrapper(const Graph& _G, FlowMap& _flow,
997 const CapacityMap& _capacity) :
998 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this, graph->nodeNum()) {
1001 OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1002 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
1003 while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e))))
1004 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1008 NodeIt& next(NodeIt& e) const {
1009 return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1012 OutEdgeIt& next(OutEdgeIt& e) const {
1013 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1014 while (valid(e) && (dist.get(tail(e))/*+1!*/>=dist.get(head(e))))
1015 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1019 NodeIt& first(NodeIt& n) const {
1020 return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
1023 void erase(const Edge& e) {
1025 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
1026 while (valid(f) && (dist.get(tail(f))/*+1!=*/>=dist.get(head(f))))
1027 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
1028 first_out_edges.set(this->tail(e), f);
1031 //TrivGraphWrapper() : graph(0) { }
1032 //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
1034 //void setGraph(Graph& _graph) { graph = &_graph; }
1035 //Graph& getGraph() const { return (*graph); }
1037 //template<typename I> I& first(I& i) const { return graph->first(i); }
1038 //template<typename I, typename P> I& first(I& i, const P& p) const {
1039 // return graph->first(i, p); }
1041 //template<typename I> I getNext(const I& i) const {
1042 // return graph->getNext(i); }
1043 //template<typename I> I& next(I &i) const { return graph->next(i); }
1045 template< typename It > It first() const {
1046 It e; first(e); return e; }
1048 template< typename It > It first(const Node& v) const {
1049 It e; first(e, v); return e; }
1051 //Node head(const Edge& e) const { return graph->head(e); }
1052 //Node tail(const Edge& e) const { return graph->tail(e); }
1054 //template<typename I> bool valid(const I& i) const
1055 // { return graph->valid(i); }
1057 //template<typename I> void setInvalid(const I &i);
1058 //{ return graph->setInvalid(i); }
1060 //int nodeNum() const { return graph->nodeNum(); }
1061 //int edgeNum() const { return graph->edgeNum(); }
1063 //template<typename I> Node aNode(const I& e) const {
1064 // return graph->aNode(e); }
1065 //template<typename I> Node bNode(const I& e) const {
1066 // return graph->bNode(e); }
1068 //Node addNode() const { return graph->addNode(); }
1069 //Edge addEdge(const Node& tail, const Node& head) const {
1070 // return graph->addEdge(tail, head); }
1072 //template<typename I> void erase(const I& i) const { graph->erase(i); }
1074 //void clear() const { graph->clear(); }
1076 template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
1078 NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
1079 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
1080 NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
1081 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
1084 template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
1086 EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
1087 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
1088 EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
1089 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
1093 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
1099 // // FIXME: comparison should be made better!!!
1100 // template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
1101 // class ResGraphWrapper
1106 // typedef Graph BaseGraph;
1108 // typedef typename Graph::Node Node;
1109 // typedef typename Graph::Edge Edge;
1111 // typedef typename Graph::NodeIt NodeIt;
1113 // class OutEdgeIt {
1117 // typename Graph::OutEdgeIt o;
1118 // typename Graph::InEdgeIt i;
1124 // typename Graph::OutEdgeIt o;
1125 // typename Graph::InEdgeIt i;
1127 // typedef typename Graph::SymEdgeIt SymEdgeIt;
1128 // typedef typename Graph::EdgeIt EdgeIt;
1130 // int nodeNum() const { return graph->nodeNum(); }
1131 // int edgeNum() const { return graph->edgeNum(); }
1133 // Node& first(Node& n) const { return graph->first(n); }
1135 // // Edge and SymEdge is missing!!!!
1136 // // Edge <-> In/OutEdgeIt conversion is missing!!!!
1139 // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const
1142 // graph->first(e.o,n);
1143 // while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1144 // graph->goNext(e.o);
1145 // if(!graph->valid(e.o)) {
1146 // graph->first(e.i,n);
1147 // while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1148 // graph->goNext(e.i);
1153 // OutEdgeIt &goNext(OutEdgeIt &e)
1155 // if(graph->valid(e.o)) {
1156 // while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1157 // graph->goNext(e.o);
1158 // if(graph->valid(e.o)) return e;
1159 // else graph->first(e.i,e.n);
1162 // while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1163 // graph->goNext(e.i);
1167 // OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
1169 // //bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);}
1172 // InEdgeIt& first(InEdgeIt& e, const Node& n) const
1175 // graph->first(e.i,n);
1176 // while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1177 // graph->goNext(e.i);
1178 // if(!graph->valid(e.i)) {
1179 // graph->first(e.o,n);
1180 // while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1181 // graph->goNext(e.o);
1186 // InEdgeIt &goNext(InEdgeIt &e)
1188 // if(graph->valid(e.i)) {
1189 // while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1190 // graph->goNext(e.i);
1191 // if(graph->valid(e.i)) return e;
1192 // else graph->first(e.o,e.n);
1195 // while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1196 // graph->goNext(e.o);
1200 // InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
1202 // //bool valid(const InEdgeIt e) { return graph->valid(e.i)||graph->valid(e.o);}
1204 // //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
1205 // //template<typename I> I next(const I i); { return graph->goNext(i); }
1207 // template< typename It > It first() const {
1208 // It e; first(e); return e; }
1210 // template< typename It > It first(Node v) const {
1211 // It e; first(e, v); return e; }
1213 // Node head(const Edge& e) const { return graph->head(e); }
1214 // Node tail(const Edge& e) const { return graph->tail(e); }
1216 // template<typename I> Node aNode(const I& e) const {
1217 // return graph->aNode(e); }
1218 // template<typename I> Node bNode(const I& e) const {
1219 // return graph->bNode(e); }
1221 // //template<typename I> bool valid(const I i);
1222 // //{ return graph->valid(i); }
1224 // //template<typename I> void setInvalid(const I &i);
1225 // //{ return graph->setInvalid(i); }
1227 // Node addNode() { return graph->addNode(); }
1228 // Edge addEdge(const Node& tail, const Node& head) {
1229 // return graph->addEdge(tail, head); }
1231 // template<typename I> void erase(const I& i) { graph->erase(i); }
1233 // void clear() { graph->clear(); }
1235 // template<typename S> class NodeMap : public Graph::NodeMap<S> { };
1236 // template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
1238 // void setGraph(Graph& _graph) { graph = &_graph; }
1239 // Graph& getGraph() { return (*graph); }
1241 // //ResGraphWrapper() : graph(0) { }
1242 // ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
1247 #endif //GRAPH_WRAPPER_H