00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef LEMON_GRAPH_WRAPPER_H
00018 #define LEMON_GRAPH_WRAPPER_H
00019
00027
00028 #include <lemon/invalid.h>
00029 #include <lemon/maps.h>
00030 #include <lemon/iterable_graph_extender.h>
00031 #include <iostream>
00032
00033 namespace lemon {
00034
00035
00036
00112 template<typename _Graph>
00113 class GraphWrapperBase {
00114 public:
00115 typedef _Graph Graph;
00117 typedef Graph BaseGraph;
00118 typedef Graph ParentGraph;
00119
00120 protected:
00121 Graph* graph;
00122 GraphWrapperBase() : graph(0) { }
00123 void setGraph(Graph& _graph) { graph=&_graph; }
00124
00125 public:
00126 GraphWrapperBase(Graph& _graph) : graph(&_graph) { }
00127
00128 typedef typename Graph::Node Node;
00129 typedef typename Graph::Edge Edge;
00130
00131 void first(Node& i) const { graph->first(i); }
00132 void first(Edge& i) const { graph->first(i); }
00133 void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
00134 void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
00135
00136 void next(Node& i) const { graph->next(i); }
00137 void next(Edge& i) const { graph->next(i); }
00138 void nextIn(Edge& i) const { graph->nextIn(i); }
00139 void nextOut(Edge& i) const { graph->nextOut(i); }
00140
00141 Node source(const Edge& e) const { return graph->source(e); }
00142 Node target(const Edge& e) const { return graph->target(e); }
00143
00144 int nodeNum() const { return graph->nodeNum(); }
00145 int edgeNum() const { return graph->edgeNum(); }
00146
00147 Node addNode() const { return Node(graph->addNode()); }
00148 Edge addEdge(const Node& source, const Node& target) const {
00149 return Edge(graph->addEdge(source, target)); }
00150
00151 void erase(const Node& i) const { graph->erase(i); }
00152 void erase(const Edge& i) const { graph->erase(i); }
00153
00154 void clear() const { graph->clear(); }
00155
00156 bool forward(const Edge& e) const { return graph->forward(e); }
00157 bool backward(const Edge& e) const { return graph->backward(e); }
00158
00159 int id(const Node& v) const { return graph->id(v); }
00160 int id(const Edge& e) const { return graph->id(e); }
00161
00162 Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }
00163
00164 template <typename _Value>
00165 class NodeMap : public _Graph::template NodeMap<_Value> {
00166 public:
00167 typedef typename _Graph::template NodeMap<_Value> Parent;
00168 NodeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
00169 NodeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
00170 : Parent(*gw.graph, value) { }
00171 };
00172
00173 template <typename _Value>
00174 class EdgeMap : public _Graph::template EdgeMap<_Value> {
00175 public:
00176 typedef typename _Graph::template EdgeMap<_Value> Parent;
00177 EdgeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
00178 EdgeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
00179 : Parent(*gw.graph, value) { }
00180 };
00181
00182 };
00183
00184 template <typename _Graph>
00185 class GraphWrapper :
00186 public IterableGraphExtender<GraphWrapperBase<_Graph> > {
00187 public:
00188 typedef _Graph Graph;
00189 typedef IterableGraphExtender<GraphWrapperBase<_Graph> > Parent;
00190 protected:
00191 GraphWrapper() : Parent() { }
00192
00193 public:
00194 GraphWrapper(Graph& _graph) { setGraph(_graph); }
00195 };
00196
00197 template <typename _Graph>
00198 class RevGraphWrapperBase : public GraphWrapperBase<_Graph> {
00199 public:
00200 typedef _Graph Graph;
00201 typedef GraphWrapperBase<_Graph> Parent;
00202 protected:
00203 RevGraphWrapperBase() : Parent() { }
00204 public:
00205 typedef typename Parent::Node Node;
00206 typedef typename Parent::Edge Edge;
00207
00208 using Parent::first;
00209 void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
00210 void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
00211
00212 using Parent::next;
00213 void nextIn(Edge& i) const { Parent::nextOut(i); }
00214 void nextOut(Edge& i) const { Parent::nextIn(i); }
00215
00216 Node source(const Edge& e) const { return Parent::target(e); }
00217 Node target(const Edge& e) const { return Parent::source(e); }
00218 };
00219
00220
00222
00244 template<typename _Graph>
00245 class RevGraphWrapper :
00246 public IterableGraphExtender<RevGraphWrapperBase<_Graph> > {
00247 public:
00248 typedef _Graph Graph;
00249 typedef IterableGraphExtender<
00250 RevGraphWrapperBase<_Graph> > Parent;
00251 protected:
00252 RevGraphWrapper() { }
00253 public:
00254 RevGraphWrapper(_Graph& _graph) { setGraph(_graph); }
00255 };
00256
00257
00258 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
00259 class SubGraphWrapperBase : public GraphWrapperBase<_Graph> {
00260 public:
00261 typedef _Graph Graph;
00262 typedef GraphWrapperBase<_Graph> Parent;
00263 protected:
00264 NodeFilterMap* node_filter_map;
00265 EdgeFilterMap* edge_filter_map;
00266 SubGraphWrapperBase() : Parent(),
00267 node_filter_map(0), edge_filter_map(0) { }
00268
00269 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
00270 node_filter_map=&_node_filter_map;
00271 }
00272 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
00273 edge_filter_map=&_edge_filter_map;
00274 }
00275
00276 public:
00277
00278
00279
00280
00281
00282
00283
00284 typedef typename Parent::Node Node;
00285 typedef typename Parent::Edge Edge;
00286
00287 void first(Node& i) const {
00288 Parent::first(i);
00289 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
00290 }
00291 void first(Edge& i) const {
00292 Parent::first(i);
00293 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
00294 }
00295 void firstIn(Edge& i, const Node& n) const {
00296 Parent::firstIn(i, n);
00297 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
00298 }
00299 void firstOut(Edge& i, const Node& n) const {
00300 Parent::firstOut(i, n);
00301 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
00302 }
00303
00304 void next(Node& i) const {
00305 Parent::next(i);
00306 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
00307 }
00308 void next(Edge& i) const {
00309 Parent::next(i);
00310 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
00311 }
00312 void nextIn(Edge& i) const {
00313 Parent::nextIn(i);
00314 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
00315 }
00316 void nextOut(Edge& i) const {
00317 Parent::nextOut(i);
00318 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
00319 }
00320
00324 void hide(const Node& n) const { node_filter_map->set(n, false); }
00325
00329 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
00330
00334 void unHide(const Node& n) const { node_filter_map->set(n, true); }
00335
00339 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
00340
00342 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
00343
00345 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
00346
00350 int nodeNum() const {
00351 int i=0;
00352 Node n;
00353 for (first(n); n!=INVALID; next(n)) ++i;
00354 return i;
00355 }
00356
00360 int edgeNum() const {
00361 int i=0;
00362 Edge e;
00363 for (first(e); e!=INVALID; next(e)) ++i;
00364 return i;
00365 }
00366
00367
00368 };
00369
00416 template<typename _Graph, typename NodeFilterMap,
00417 typename EdgeFilterMap>
00418 class SubGraphWrapper :
00419 public IterableGraphExtender<
00420 SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
00421 public:
00422 typedef _Graph Graph;
00423 typedef IterableGraphExtender<
00424 SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
00425 protected:
00426 SubGraphWrapper() { }
00427 public:
00428 SubGraphWrapper(_Graph& _graph, NodeFilterMap& _node_filter_map,
00429 EdgeFilterMap& _edge_filter_map) {
00430 setGraph(_graph);
00431 setNodeFilterMap(_node_filter_map);
00432 setEdgeFilterMap(_edge_filter_map);
00433 }
00434 };
00435
00436
00437
00449 template<typename Graph, typename NodeFilterMap>
00450 class NodeSubGraphWrapper :
00451 public SubGraphWrapper<Graph, NodeFilterMap,
00452 ConstMap<typename Graph::Edge,bool> > {
00453 public:
00454 typedef SubGraphWrapper<Graph, NodeFilterMap,
00455 ConstMap<typename Graph::Edge,bool> > Parent;
00456 protected:
00457 ConstMap<typename Graph::Edge, bool> const_true_map;
00458 public:
00459 NodeSubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map) :
00460 Parent(), const_true_map(true) {
00461 Parent::setGraph(_graph);
00462 Parent::setNodeFilterMap(_node_filter_map);
00463 Parent::setEdgeFilterMap(const_true_map);
00464 }
00465 };
00466
00467
00594 template<typename Graph, typename EdgeFilterMap>
00595 class EdgeSubGraphWrapper :
00596 public SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
00597 EdgeFilterMap> {
00598 public:
00599 typedef SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
00600 EdgeFilterMap> Parent;
00601 protected:
00602 ConstMap<typename Graph::Node, bool> const_true_map;
00603 public:
00604 EdgeSubGraphWrapper(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
00605 Parent(), const_true_map(true) {
00606 Parent::setGraph(_graph);
00607 Parent::setNodeFilterMap(const_true_map);
00608 Parent::setEdgeFilterMap(_edge_filter_map);
00609 }
00610 };
00611
00612
00613 template<typename Graph>
00614 class UndirGraphWrapper : public GraphWrapper<Graph> {
00615 public:
00616 typedef GraphWrapper<Graph> Parent;
00617 protected:
00618 UndirGraphWrapper() : GraphWrapper<Graph>() { }
00619
00620 public:
00621 typedef typename GraphWrapper<Graph>::Node Node;
00622 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
00623 typedef typename GraphWrapper<Graph>::Edge Edge;
00624 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
00625
00626 UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
00627
00628 class OutEdgeIt {
00629 friend class UndirGraphWrapper<Graph>;
00630 bool out_or_in;
00631 typename Graph::OutEdgeIt out;
00632 typename Graph::InEdgeIt in;
00633 public:
00634 OutEdgeIt() { }
00635 OutEdgeIt(const Invalid& i) : Edge(i) { }
00636 OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
00637 out_or_in=true; _G.graph->first(out, _n);
00638 if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); }
00639 }
00640 operator Edge() const {
00641 if (out_or_in) return Edge(out); else return Edge(in);
00642 }
00643 };
00644
00645 typedef OutEdgeIt InEdgeIt;
00646
00647 using GraphWrapper<Graph>::first;
00648 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
00649 i=OutEdgeIt(*this, p); return i;
00650 }
00651
00652 using GraphWrapper<Graph>::next;
00653
00654 OutEdgeIt& next(OutEdgeIt& e) const {
00655 if (e.out_or_in) {
00656 typename Graph::Node n=this->graph->source(e.out);
00657 this->graph->next(e.out);
00658 if (!this->graph->valid(e.out)) {
00659 e.out_or_in=false; this->graph->first(e.in, n); }
00660 } else {
00661 this->graph->next(e.in);
00662 }
00663 return e;
00664 }
00665
00666 Node aNode(const OutEdgeIt& e) const {
00667 if (e.out_or_in) return this->graph->source(e); else
00668 return this->graph->target(e); }
00669 Node bNode(const OutEdgeIt& e) const {
00670 if (e.out_or_in) return this->graph->target(e); else
00671 return this->graph->source(e); }
00672
00673
00674
00675 };
00676
00677
00678
00679
00680
00681
00682
00683
00684
00685
00686 template<typename Graph>
00687 class UndirGraph : public UndirGraphWrapper<Graph> {
00688 typedef UndirGraphWrapper<Graph> Parent;
00689 protected:
00690 Graph gr;
00691 public:
00692 UndirGraph() : UndirGraphWrapper<Graph>() {
00693 Parent::setGraph(gr);
00694 }
00695
00696
00697 };
00698
00699
00700 template <typename _Graph,
00701 typename ForwardFilterMap, typename BackwardFilterMap>
00702 class SubBidirGraphWrapperBase : public GraphWrapperBase<_Graph> {
00703 public:
00704 typedef _Graph Graph;
00705 typedef GraphWrapperBase<_Graph> Parent;
00706 protected:
00707 ForwardFilterMap* forward_filter;
00708 BackwardFilterMap* backward_filter;
00709 SubBidirGraphWrapperBase() : Parent(),
00710 forward_filter(0), backward_filter(0) { }
00711
00712 void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
00713 forward_filter=&_forward_filter;
00714 }
00715 void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
00716 backward_filter=&_backward_filter;
00717 }
00718
00719 public:
00720
00721
00722
00723
00724
00725
00726
00727 typedef typename Parent::Node Node;
00728 typedef typename _Graph::Edge GraphEdge;
00729 template <typename T> class EdgeMap;
00734 class Edge : public _Graph::Edge {
00735 friend class SubBidirGraphWrapperBase<
00736 Graph, ForwardFilterMap, BackwardFilterMap>;
00737 template<typename T> friend class EdgeMap;
00738 protected:
00739 bool backward;
00740 public:
00741 Edge() { }
00745 Edge(const typename _Graph::Edge& e, bool _backward) :
00746 _Graph::Edge(e), backward(_backward) { }
00747 Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
00748 bool operator==(const Edge& v) const {
00749 return (this->backward==v.backward &&
00750 static_cast<typename _Graph::Edge>(*this)==
00751 static_cast<typename _Graph::Edge>(v));
00752 }
00753 bool operator!=(const Edge& v) const {
00754 return (this->backward!=v.backward ||
00755 static_cast<typename _Graph::Edge>(*this)!=
00756 static_cast<typename _Graph::Edge>(v));
00757 }
00758 };
00759
00760 void first(Node& i) const {
00761 Parent::first(i);
00762 }
00763
00764 void first(Edge& i) const {
00765 Parent::first(i);
00766 i.backward=false;
00767 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00768 !(*forward_filter)[i]) Parent::next(i);
00769 if (*static_cast<GraphEdge*>(&i)==INVALID) {
00770 Parent::first(i);
00771 i.backward=true;
00772 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00773 !(*backward_filter)[i]) Parent::next(i);
00774 }
00775 }
00776
00777 void firstIn(Edge& i, const Node& n) const {
00778 Parent::firstIn(i, n);
00779 i.backward=false;
00780 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00781 !(*forward_filter)[i]) Parent::nextOut(i);
00782 if (*static_cast<GraphEdge*>(&i)==INVALID) {
00783 Parent::firstOut(i, n);
00784 i.backward=true;
00785 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00786 !(*backward_filter)[i]) Parent::nextOut(i);
00787 }
00788 }
00789
00790 void firstOut(Edge& i, const Node& n) const {
00791 Parent::firstOut(i, n);
00792 i.backward=false;
00793 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00794 !(*forward_filter)[i]) Parent::nextOut(i);
00795 if (*static_cast<GraphEdge*>(&i)==INVALID) {
00796 Parent::firstIn(i, n);
00797 i.backward=true;
00798 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00799 !(*backward_filter)[i]) Parent::nextIn(i);
00800 }
00801 }
00802
00803 void next(Node& i) const {
00804 Parent::next(i);
00805 }
00806
00807 void next(Edge& i) const {
00808 if (!(i.backward)) {
00809 Parent::next(i);
00810 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00811 !(*forward_filter)[i]) Parent::next(i);
00812 if (*static_cast<GraphEdge*>(&i)==INVALID) {
00813 Parent::first(i);
00814 i.backward=true;
00815 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00816 !(*backward_filter)[i]) Parent::next(i);
00817 }
00818 } else {
00819 Parent::next(i);
00820 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00821 !(*backward_filter)[i]) Parent::next(i);
00822 }
00823 }
00824
00825 void nextIn(Edge& i) const {
00826 if (!(i.backward)) {
00827 Node n=Parent::target(i);
00828 Parent::nextIn(i);
00829 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00830 !(*forward_filter)[i]) Parent::nextIn(i);
00831 if (*static_cast<GraphEdge*>(&i)==INVALID) {
00832 Parent::firstOut(i, n);
00833 i.backward=true;
00834 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00835 !(*backward_filter)[i]) Parent::nextOut(i);
00836 }
00837 } else {
00838 Parent::nextOut(i);
00839 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00840 !(*backward_filter)[i]) Parent::nextOut(i);
00841 }
00842 }
00843
00844 void nextOut(Edge& i) const {
00845 if (!(i.backward)) {
00846 Node n=Parent::source(i);
00847 Parent::nextOut(i);
00848 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00849 !(*forward_filter)[i]) Parent::nextOut(i);
00850 if (*static_cast<GraphEdge*>(&i)==INVALID) {
00851 Parent::firstIn(i, n);
00852 i.backward=true;
00853 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00854 !(*backward_filter)[i]) Parent::nextIn(i);
00855 }
00856 } else {
00857 Parent::nextIn(i);
00858 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00859 !(*backward_filter)[i]) Parent::nextIn(i);
00860 }
00861 }
00862
00863 Node source(Edge e) const {
00864 return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
00865 Node target(Edge e) const {
00866 return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
00867
00869 Edge opposite(const Edge& e) const {
00870 Edge f=e;
00871 f.backward=!f.backward;
00872 return f;
00873 }
00874
00878 int edgeNum() const {
00879 int i=0;
00880 Edge e;
00881 for (first(e); e!=INVALID; next(e)) ++i;
00882 return i;
00883 }
00884
00885 bool forward(const Edge& e) const { return !e.backward; }
00886 bool backward(const Edge& e) const { return e.backward; }
00887
00888 template <typename T>
00892 class EdgeMap {
00893 template <typename TT> friend class EdgeMap;
00894 typename _Graph::template EdgeMap<T> forward_map, backward_map;
00895 public:
00896 typedef T Value;
00897 typedef Edge Key;
00898
00899 EdgeMap(const SubBidirGraphWrapperBase<_Graph,
00900 ForwardFilterMap, BackwardFilterMap>& g) :
00901 forward_map(*(g.graph)), backward_map(*(g.graph)) { }
00902
00903 EdgeMap(const SubBidirGraphWrapperBase<_Graph,
00904 ForwardFilterMap, BackwardFilterMap>& g, T a) :
00905 forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
00906
00907 void set(Edge e, T a) {
00908 if (!e.backward)
00909 forward_map.set(e, a);
00910 else
00911 backward_map.set(e, a);
00912 }
00913
00914
00915
00916
00917
00918
00919
00920
00921
00922
00923 T operator[](Edge e) const {
00924 if (!e.backward)
00925 return forward_map[e];
00926 else
00927 return backward_map[e];
00928 }
00929
00930 void update() {
00931 forward_map.update();
00932 backward_map.update();
00933 }
00934 };
00935
00936 };
00937
00938
00976 template<typename _Graph,
00977 typename ForwardFilterMap, typename BackwardFilterMap>
00978 class SubBidirGraphWrapper :
00979 public IterableGraphExtender<
00980 SubBidirGraphWrapperBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
00981 public:
00982 typedef _Graph Graph;
00983 typedef IterableGraphExtender<
00984 SubBidirGraphWrapperBase<
00985 _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
00986 protected:
00987 SubBidirGraphWrapper() { }
00988 public:
00989 SubBidirGraphWrapper(_Graph& _graph, ForwardFilterMap& _forward_filter,
00990 BackwardFilterMap& _backward_filter) {
00991 setGraph(_graph);
00992 setForwardFilterMap(_forward_filter);
00993 setBackwardFilterMap(_backward_filter);
00994 }
00995 };
00996
00997
00998
01008 template<typename Graph>
01009 class BidirGraphWrapper :
01010 public SubBidirGraphWrapper<
01011 Graph,
01012 ConstMap<typename Graph::Edge, bool>,
01013 ConstMap<typename Graph::Edge, bool> > {
01014 public:
01015 typedef SubBidirGraphWrapper<
01016 Graph,
01017 ConstMap<typename Graph::Edge, bool>,
01018 ConstMap<typename Graph::Edge, bool> > Parent;
01019 protected:
01020 ConstMap<typename Graph::Edge, bool> cm;
01021
01022 BidirGraphWrapper() : Parent(), cm(true) {
01023 Parent::setForwardFilterMap(cm);
01024 Parent::setBackwardFilterMap(cm);
01025 }
01026 public:
01027 BidirGraphWrapper(Graph& _graph) : Parent() {
01028 Parent::setGraph(_graph);
01029 Parent::setForwardFilterMap(cm);
01030 Parent::setBackwardFilterMap(cm);
01031 }
01032
01033 int edgeNum() const {
01034 return 2*this->graph->edgeNum();
01035 }
01036
01037 };
01038
01039
01040 template<typename Graph, typename Number,
01041 typename CapacityMap, typename FlowMap>
01042 class ResForwardFilter {
01043
01044 const CapacityMap* capacity;
01045 const FlowMap* flow;
01046 public:
01047 ResForwardFilter(
01048 const CapacityMap& _capacity, const FlowMap& _flow) :
01049 capacity(&_capacity), flow(&_flow) { }
01050 ResForwardFilter() : capacity(0), flow(0) { }
01051 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
01052 void setFlow(const FlowMap& _flow) { flow=&_flow; }
01053 bool operator[](const typename Graph::Edge& e) const {
01054 return (Number((*flow)[e]) < Number((*capacity)[e]));
01055 }
01056 };
01057
01058 template<typename Graph, typename Number,
01059 typename CapacityMap, typename FlowMap>
01060 class ResBackwardFilter {
01061 const CapacityMap* capacity;
01062 const FlowMap* flow;
01063 public:
01064 ResBackwardFilter(
01065 const CapacityMap& _capacity, const FlowMap& _flow) :
01066 capacity(&_capacity), flow(&_flow) { }
01067 ResBackwardFilter() : capacity(0), flow(0) { }
01068 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
01069 void setFlow(const FlowMap& _flow) { flow=&_flow; }
01070 bool operator[](const typename Graph::Edge& e) const {
01071 return (Number(0) < Number((*flow)[e]));
01072 }
01073 };
01074
01075
01077
01082 template<typename Graph, typename Number,
01083 typename CapacityMap, typename FlowMap>
01084 class ResGraphWrapper :
01085 public SubBidirGraphWrapper<
01086 Graph,
01087 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
01088 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
01089 public:
01090 typedef SubBidirGraphWrapper<
01091 Graph,
01092 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
01093 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
01094 protected:
01095 const CapacityMap* capacity;
01096 FlowMap* flow;
01097 ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
01098 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
01099 ResGraphWrapper() : Parent(),
01100 capacity(0), flow(0) { }
01101 void setCapacityMap(const CapacityMap& _capacity) {
01102 capacity=&_capacity;
01103 forward_filter.setCapacity(_capacity);
01104 backward_filter.setCapacity(_capacity);
01105 }
01106 void setFlowMap(FlowMap& _flow) {
01107 flow=&_flow;
01108 forward_filter.setFlow(_flow);
01109 backward_filter.setFlow(_flow);
01110 }
01111 public:
01112 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
01113 FlowMap& _flow) :
01114 Parent(), capacity(&_capacity), flow(&_flow),
01115 forward_filter( _capacity, _flow),
01116 backward_filter( _capacity, _flow) {
01117 Parent::setGraph(_graph);
01118 Parent::setForwardFilterMap(forward_filter);
01119 Parent::setBackwardFilterMap(backward_filter);
01120 }
01121
01122 typedef typename Parent::Edge Edge;
01123
01124 void augment(const Edge& e, Number a) const {
01125 if (Parent::forward(e))
01126 flow->set(e, (*flow)[e]+a);
01127 else
01128 flow->set(e, (*flow)[e]-a);
01129 }
01130
01135 class ResCap {
01136 protected:
01137 const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
01138 public:
01139 typedef Number Value;
01140 typedef Edge Key;
01141 ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>&
01142 _res_graph) : res_graph(&_res_graph) { }
01143 Number operator[](const Edge& e) const {
01144 if (res_graph->forward(e))
01145 return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
01146 else
01147 return (*(res_graph->flow))[e];
01148 }
01149 };
01150
01151
01152 };
01153
01154
01155
01156 template <typename _Graph, typename FirstOutEdgesMap>
01157 class ErasingFirstGraphWrapperBase : public GraphWrapperBase<_Graph> {
01158 public:
01159 typedef _Graph Graph;
01160 typedef GraphWrapperBase<_Graph> Parent;
01161 protected:
01162 FirstOutEdgesMap* first_out_edges;
01163 ErasingFirstGraphWrapperBase() : Parent(),
01164 first_out_edges(0) { }
01165
01166 void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
01167 first_out_edges=&_first_out_edges;
01168 }
01169
01170 public:
01171
01172 typedef typename Parent::Node Node;
01173 typedef typename Parent::Edge Edge;
01174
01175 void firstOut(Edge& i, const Node& n) const {
01176 i=(*first_out_edges)[n];
01177 }
01178
01179 void erase(const Edge& e) const {
01180 Node n=source(e);
01181 Edge f=e;
01182 Parent::nextOut(f);
01183 first_out_edges->set(n, f);
01184 }
01185 };
01186
01187
01189
01202 template <typename _Graph, typename FirstOutEdgesMap>
01203 class ErasingFirstGraphWrapper :
01204 public IterableGraphExtender<
01205 ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > {
01206 public:
01207 typedef _Graph Graph;
01208 typedef IterableGraphExtender<
01209 ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > Parent;
01210 ErasingFirstGraphWrapper(Graph& _graph,
01211 FirstOutEdgesMap& _first_out_edges) {
01212 setGraph(_graph);
01213 setFirstOutEdgesMap(_first_out_edges);
01214 }
01215
01216 };
01217
01219
01220 }
01221
01222 #endif //LEMON_GRAPH_WRAPPER_H
01223