1.1 --- a/src/work/marci/bfs_iterator.h Mon Apr 05 15:31:21 2004 +0000
1.2 +++ b/src/work/marci/bfs_iterator.h Mon Apr 05 16:52:46 2004 +0000
1.3 @@ -5,7 +5,6 @@
1.4 #include <queue>
1.5 #include <stack>
1.6 #include <utility>
1.7 -#include <graph_wrapper.h>
1.8
1.9 namespace hugo {
1.10
1.11 @@ -630,40 +629,34 @@
1.12 // };
1.13
1.14
1.15 - template <typename GraphWrapper, /*typename OutEdgeIt,*/
1.16 - typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
1.17 + template <typename Graph, /*typename OutEdgeIt,*/
1.18 + typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
1.19 class BfsIterator5 {
1.20 - typedef typename GraphWrapper::Node Node;
1.21 - typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
1.22 - GraphWrapper G;
1.23 + protected:
1.24 + typedef typename Graph::Node Node;
1.25 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.26 + const Graph* graph;
1.27 std::queue<Node> bfs_queue;
1.28 ReachedMap& reached;
1.29 bool b_node_newly_reached;
1.30 OutEdgeIt actual_edge;
1.31 bool own_reached_map;
1.32 public:
1.33 - BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
1.34 - G(_G), reached(_reached),
1.35 + BfsIterator5(const Graph& _graph, ReachedMap& _reached) :
1.36 + graph(&_graph), reached(_reached),
1.37 own_reached_map(false) { }
1.38 - BfsIterator5(const GraphWrapper& _G) :
1.39 - G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.40 + BfsIterator5(const Graph& _graph) :
1.41 + graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
1.42 own_reached_map(true) { }
1.43 -// BfsIterator5(const typename GraphWrapper::BaseGraph& _G,
1.44 -// ReachedMap& _reached) :
1.45 -// G(_G), reached(_reached),
1.46 -// own_reached_map(false) { }
1.47 -// BfsIterator5(const typename GraphWrapper::BaseGraph& _G) :
1.48 -// G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.49 -// own_reached_map(true) { }
1.50 ~BfsIterator5() { if (own_reached_map) delete &reached; }
1.51 void pushAndSetReached(Node s) {
1.52 reached.set(s, true);
1.53 if (bfs_queue.empty()) {
1.54 bfs_queue.push(s);
1.55 - G./*getF*/first(actual_edge, s);
1.56 - if (G.valid(actual_edge)/*.valid()*/) {
1.57 - Node w=G.bNode(actual_edge);
1.58 - if (!reached.get(w)) {
1.59 + graph->first(actual_edge, s);
1.60 + if (graph->valid(actual_edge)) {
1.61 + Node w=graph->bNode(actual_edge);
1.62 + if (!reached[w]) {
1.63 bfs_queue.push(w);
1.64 reached.set(w, true);
1.65 b_node_newly_reached=true;
1.66 @@ -675,13 +668,13 @@
1.67 bfs_queue.push(s);
1.68 }
1.69 }
1.70 - BfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
1.71 + BfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>&
1.72 operator++() {
1.73 - if (G.valid(actual_edge)/*.valid()*/) {
1.74 - /*++*/G.next(actual_edge);
1.75 - if (G.valid(actual_edge)/*.valid()*/) {
1.76 - Node w=G.bNode(actual_edge);
1.77 - if (!reached.get(w)) {
1.78 + if (graph->valid(actual_edge)) {
1.79 + graph->next(actual_edge);
1.80 + if (graph->valid(actual_edge)) {
1.81 + Node w=graph->bNode(actual_edge);
1.82 + if (!reached[w]) {
1.83 bfs_queue.push(w);
1.84 reached.set(w, true);
1.85 b_node_newly_reached=true;
1.86 @@ -692,10 +685,10 @@
1.87 } else {
1.88 bfs_queue.pop();
1.89 if (!bfs_queue.empty()) {
1.90 - G./*getF*/first(actual_edge, bfs_queue.front());
1.91 - if (G.valid(actual_edge)/*.valid()*/) {
1.92 - Node w=G.bNode(actual_edge);
1.93 - if (!reached.get(w)) {
1.94 + graph->first(actual_edge, bfs_queue.front());
1.95 + if (graph->valid(actual_edge)) {
1.96 + Node w=graph->bNode(actual_edge);
1.97 + if (!reached[w]) {
1.98 bfs_queue.push(w);
1.99 reached.set(w, true);
1.100 b_node_newly_reached=true;
1.101 @@ -710,9 +703,9 @@
1.102 bool finished() const { return bfs_queue.empty(); }
1.103 operator OutEdgeIt () const { return actual_edge; }
1.104 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.105 - bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
1.106 + bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
1.107 Node aNode() const { return bfs_queue.front(); }
1.108 - Node bNode() const { return G.bNode(actual_edge); }
1.109 + Node bNode() const { return graph->bNode(actual_edge); }
1.110 const ReachedMap& getReachedMap() const { return reached; }
1.111 const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
1.112 };
1.113 @@ -773,12 +766,13 @@
1.114 // const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
1.115 // };
1.116
1.117 - template <typename GraphWrapper, /*typename OutEdgeIt,*/
1.118 - typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
1.119 + template <typename Graph, /*typename OutEdgeIt,*/
1.120 + typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
1.121 class DfsIterator5 {
1.122 - typedef typename GraphWrapper::Node Node;
1.123 - typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
1.124 - GraphWrapper G;
1.125 + protected:
1.126 + typedef typename Graph::Node Node;
1.127 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.128 + const Graph* graph;
1.129 std::stack<OutEdgeIt> dfs_stack;
1.130 bool b_node_newly_reached;
1.131 OutEdgeIt actual_edge;
1.132 @@ -786,36 +780,36 @@
1.133 ReachedMap& reached;
1.134 bool own_reached_map;
1.135 public:
1.136 - DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
1.137 - G(_G), reached(_reached),
1.138 + DfsIterator5(const Graph& _graph, ReachedMap& _reached) :
1.139 + graph(&_graph), reached(_reached),
1.140 own_reached_map(false) { }
1.141 - DfsIterator5(const GraphWrapper& _G) :
1.142 - G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.143 + DfsIterator5(const Graph& _graph) :
1.144 + graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
1.145 own_reached_map(true) { }
1.146 ~DfsIterator5() { if (own_reached_map) delete &reached; }
1.147 void pushAndSetReached(Node s) {
1.148 actual_node=s;
1.149 reached.set(s, true);
1.150 OutEdgeIt e;
1.151 - G.first(e, s);
1.152 + graph->first(e, s);
1.153 dfs_stack.push(e);
1.154 }
1.155 - DfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
1.156 + DfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>&
1.157 operator++() {
1.158 actual_edge=dfs_stack.top();
1.159 //actual_node=G.aNode(actual_edge);
1.160 - if (G.valid(actual_edge)/*.valid()*/) {
1.161 - Node w=G.bNode(actual_edge);
1.162 + if (graph->valid(actual_edge)/*.valid()*/) {
1.163 + Node w=graph->bNode(actual_edge);
1.164 actual_node=w;
1.165 - if (!reached.get(w)) {
1.166 + if (!reached[w]) {
1.167 OutEdgeIt e;
1.168 - G.first(e, w);
1.169 + graph->first(e, w);
1.170 dfs_stack.push(e);
1.171 reached.set(w, true);
1.172 b_node_newly_reached=true;
1.173 } else {
1.174 - actual_node=G.aNode(actual_edge);
1.175 - /*++*/G.next(dfs_stack.top());
1.176 + actual_node=graph->aNode(actual_edge);
1.177 + graph->next(dfs_stack.top());
1.178 b_node_newly_reached=false;
1.179 }
1.180 } else {
1.181 @@ -827,7 +821,7 @@
1.182 bool finished() const { return dfs_stack.empty(); }
1.183 operator OutEdgeIt () const { return actual_edge; }
1.184 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.185 - bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
1.186 + bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
1.187 Node aNode() const { return actual_node; /*FIXME*/}
1.188 Node bNode() const { return G.bNode(actual_edge); }
1.189 const ReachedMap& getReachedMap() const { return reached; }
2.1 --- a/src/work/marci/edmonds_karp.h Mon Apr 05 15:31:21 2004 +0000
2.2 +++ b/src/work/marci/edmonds_karp.h Mon Apr 05 16:52:46 2004 +0000
2.3 @@ -8,6 +8,7 @@
2.4
2.5 #include <bfs_iterator.h>
2.6 #include <invalid.h>
2.7 +#include <graph_wrapper.h>
2.8
2.9 namespace hugo {
2.10
2.11 @@ -247,31 +248,29 @@
2.12 };
2.13
2.14
2.15 - template <typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
2.16 + template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
2.17 class MaxFlow {
2.18 protected:
2.19 - typedef GraphWrapper GW;
2.20 - typedef typename GW::Node Node;
2.21 - typedef typename GW::Edge Edge;
2.22 - typedef typename GW::EdgeIt EdgeIt;
2.23 - typedef typename GW::OutEdgeIt OutEdgeIt;
2.24 - typedef typename GW::InEdgeIt InEdgeIt;
2.25 - //const Graph* G;
2.26 - GW gw;
2.27 + typedef typename Graph::Node Node;
2.28 + typedef typename Graph::Edge Edge;
2.29 + typedef typename Graph::EdgeIt EdgeIt;
2.30 + typedef typename Graph::OutEdgeIt OutEdgeIt;
2.31 + typedef typename Graph::InEdgeIt InEdgeIt;
2.32 + const Graph* g;
2.33 Node s;
2.34 Node t;
2.35 FlowMap* flow;
2.36 const CapacityMap* capacity;
2.37 - typedef ResGraphWrapper<GW, Number, FlowMap, CapacityMap > ResGW;
2.38 + typedef ResGraphWrapper<const Graph, Number, FlowMap, CapacityMap > ResGW;
2.39 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
2.40 typedef typename ResGW::Edge ResGWEdge;
2.41 public:
2.42
2.43 - MaxFlow(const GW& _gw, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
2.44 - gw(_gw), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
2.45 + MaxFlow(const Graph& _g, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
2.46 + g(&_g), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
2.47
2.48 bool augmentOnShortestPath() {
2.49 - ResGW res_graph(gw, *flow, *capacity);
2.50 + ResGW res_graph(*g, *flow, *capacity);
2.51 bool _augment=false;
2.52
2.53 typedef typename ResGW::NodeMap<bool> ReachedMap;
2.54 @@ -290,8 +289,8 @@
2.55 Node v=res_graph.tail(e);
2.56 Node w=res_graph.head(e);
2.57 pred.set(w, e);
2.58 - if (res_graph.valid(pred.get(v))) {
2.59 - free.set(w, std::min(free.get(v), res_graph.resCap(e)));
2.60 + if (res_graph.valid(pred[v])) {
2.61 + free.set(w, std::min(free[v], res_graph.resCap(e)));
2.62 } else {
2.63 free.set(w, res_graph.resCap(e));
2.64 }
2.65 @@ -303,9 +302,9 @@
2.66
2.67 if (_augment) {
2.68 Node n=t;
2.69 - Number augment_value=free.get(t);
2.70 - while (res_graph.valid(pred.get(n))) {
2.71 - ResGWEdge e=pred.get(n);
2.72 + Number augment_value=free[t];
2.73 + while (res_graph.valid(pred[n])) {
2.74 + ResGWEdge e=pred[n];
2.75 res_graph.augment(e, augment_value);
2.76 n=res_graph.tail(e);
2.77 }
2.78 @@ -317,14 +316,19 @@
2.79 template<typename MapGraphWrapper>
2.80 class DistanceMap {
2.81 protected:
2.82 - MapGraphWrapper gw;
2.83 + const MapGraphWrapper* g;
2.84 typename MapGraphWrapper::NodeMap<int> dist;
2.85 public:
2.86 - DistanceMap(MapGraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { }
2.87 + DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { }
2.88 void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; }
2.89 - int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; }
2.90 - bool get(const typename MapGraphWrapper::Edge& e) const {
2.91 - return (dist.get(gw.tail(e))<dist.get(gw.head(e)));
2.92 + int operator[](const typename MapGraphWrapper::Node& n)
2.93 + { return dist[n]; }
2.94 +// int get(const typename MapGraphWrapper::Node& n) const {
2.95 +// return dist[n]; }
2.96 +// bool get(const typename MapGraphWrapper::Edge& e) const {
2.97 +// return (dist.get(g->tail(e))<dist.get(g->head(e))); }
2.98 + bool operator[](const typename MapGraphWrapper::Edge& e) const {
2.99 + return (dist[g->tail(e)]<dist[g->head(e)]);
2.100 }
2.101 };
2.102
2.103 @@ -332,7 +336,7 @@
2.104 typedef MutableGraph MG;
2.105 bool _augment=false;
2.106
2.107 - ResGW res_graph(gw, *flow, *capacity);
2.108 + ResGW res_graph(*g, *flow, *capacity);
2.109
2.110 typedef typename ResGW::NodeMap<bool> ReachedMap;
2.111 BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
2.112 @@ -343,7 +347,7 @@
2.113 while ( !bfs.finished() ) {
2.114 ResGWOutEdgeIt e=bfs;
2.115 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
2.116 - dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
2.117 + dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
2.118 }
2.119 ++bfs;
2.120 } //computing distances from s in the residual graph
2.121 @@ -359,8 +363,8 @@
2.122 }
2.123 }
2.124
2.125 - typename MG::Node sF=res_graph_to_F.get(s);
2.126 - typename MG::Node tF=res_graph_to_F.get(t);
2.127 + typename MG::Node sF=res_graph_to_F[s];
2.128 + typename MG::Node tF=res_graph_to_F[t];
2.129 typename MG::EdgeMap<ResGWEdge> original_edge(F);
2.130 typename MG::EdgeMap<Number> residual_capacity(F);
2.131
2.132 @@ -370,7 +374,7 @@
2.133 typename FilterResGW::EdgeIt e;
2.134 for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) {
2.135 //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
2.136 - typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
2.137 + typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
2.138 original_edge.update();
2.139 original_edge.set(f, e);
2.140 residual_capacity.update();
2.141 @@ -400,10 +404,10 @@
2.142 typename MG::Node v=F.aNode(dfs);
2.143 typename MG::Node w=F.bNode(dfs);
2.144 pred.set(w, dfs);
2.145 - if (F.valid(pred.get(v))) {
2.146 - free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
2.147 + if (F.valid(pred[v])) {
2.148 + free.set(w, std::min(free[v], residual_capacity[dfs]));
2.149 } else {
2.150 - free.set(w, residual_capacity.get(dfs));
2.151 + free.set(w, residual_capacity[dfs]);
2.152 }
2.153 if (w==tF) {
2.154 __augment=true;
2.155 @@ -419,15 +423,15 @@
2.156
2.157 if (__augment) {
2.158 typename MG::Node n=tF;
2.159 - Number augment_value=free.get(tF);
2.160 - while (F.valid(pred.get(n))) {
2.161 - typename MG::Edge e=pred.get(n);
2.162 - res_graph.augment(original_edge.get(e), augment_value);
2.163 + Number augment_value=free[tF];
2.164 + while (F.valid(pred[n])) {
2.165 + typename MG::Edge e=pred[n];
2.166 + res_graph.augment(original_edge[e], augment_value);
2.167 n=F.tail(e);
2.168 - if (residual_capacity.get(e)==augment_value)
2.169 + if (residual_capacity[e]==augment_value)
2.170 F.erase(e);
2.171 else
2.172 - residual_capacity.set(e, residual_capacity.get(e)-augment_value);
2.173 + residual_capacity.set(e, residual_capacity[e]-augment_value);
2.174 }
2.175 }
2.176
2.177 @@ -440,7 +444,7 @@
2.178 typedef MutableGraph MG;
2.179 bool _augment=false;
2.180
2.181 - ResGW res_graph(gw, *flow, *capacity);
2.182 + ResGW res_graph(*g, *flow, *capacity);
2.183
2.184 //bfs for distances on the residual graph
2.185 typedef typename ResGW::NodeMap<bool> ReachedMap;
2.186 @@ -459,8 +463,8 @@
2.187 }
2.188 }
2.189
2.190 - typename MG::Node sF=res_graph_to_F.get(s);
2.191 - typename MG::Node tF=res_graph_to_F.get(t);
2.192 + typename MG::Node sF=res_graph_to_F[s];
2.193 + typename MG::Node tF=res_graph_to_F[t];
2.194 typename MG::EdgeMap<ResGWEdge> original_edge(F);
2.195 typename MG::EdgeMap<Number> residual_capacity(F);
2.196
2.197 @@ -468,15 +472,15 @@
2.198 ResGWOutEdgeIt e=bfs;
2.199 if (res_graph.valid(e)) {
2.200 if (bfs.isBNodeNewlyReached()) {
2.201 - dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
2.202 - typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
2.203 + dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
2.204 + typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
2.205 original_edge.update();
2.206 original_edge.set(f, e);
2.207 residual_capacity.update();
2.208 residual_capacity.set(f, res_graph.resCap(e));
2.209 } else {
2.210 - if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {
2.211 - typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
2.212 + if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) {
2.213 + typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
2.214 original_edge.update();
2.215 original_edge.set(f, e);
2.216 residual_capacity.update();
2.217 @@ -508,10 +512,10 @@
2.218 typename MG::Node v=F.aNode(dfs);
2.219 typename MG::Node w=F.bNode(dfs);
2.220 pred.set(w, dfs);
2.221 - if (F.valid(pred.get(v))) {
2.222 - free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
2.223 + if (F.valid(pred[v])) {
2.224 + free.set(w, std::min(free[v], residual_capacity[dfs]));
2.225 } else {
2.226 - free.set(w, residual_capacity.get(dfs));
2.227 + free.set(w, residual_capacity[dfs]);
2.228 }
2.229 if (w==tF) {
2.230 __augment=true;
2.231 @@ -527,15 +531,15 @@
2.232
2.233 if (__augment) {
2.234 typename MG::Node n=tF;
2.235 - Number augment_value=free.get(tF);
2.236 - while (F.valid(pred.get(n))) {
2.237 - typename MG::Edge e=pred.get(n);
2.238 - res_graph.augment(original_edge.get(e), augment_value);
2.239 + Number augment_value=free[tF];
2.240 + while (F.valid(pred[n])) {
2.241 + typename MG::Edge e=pred[n];
2.242 + res_graph.augment(original_edge[e], augment_value);
2.243 n=F.tail(e);
2.244 - if (residual_capacity.get(e)==augment_value)
2.245 + if (residual_capacity[e]==augment_value)
2.246 F.erase(e);
2.247 else
2.248 - residual_capacity.set(e, residual_capacity.get(e)-augment_value);
2.249 + residual_capacity.set(e, residual_capacity[e]-augment_value);
2.250 }
2.251 }
2.252
2.253 @@ -547,7 +551,7 @@
2.254 bool augmentOnBlockingFlow2() {
2.255 bool _augment=false;
2.256
2.257 - ResGW res_graph(gw, *flow, *capacity);
2.258 + ResGW res_graph(*g, *flow, *capacity);
2.259
2.260 typedef typename ResGW::NodeMap<bool> ReachedMap;
2.261 BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
2.262 @@ -557,7 +561,7 @@
2.263 while ( !bfs.finished() ) {
2.264 ResGWOutEdgeIt e=bfs;
2.265 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
2.266 - dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
2.267 + dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
2.268 }
2.269 ++bfs;
2.270 } //computing distances from s in the residual graph
2.271 @@ -610,8 +614,8 @@
2.272 typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);
2.273
2.274 pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
2.275 - if (erasing_res_graph.valid(pred.get(v))) {
2.276 - free.set(w, std::min(free.get(v), res_graph.resCap(dfs)));
2.277 + if (erasing_res_graph.valid(pred[v])) {
2.278 + free.set(w, std::min(free[v], res_graph.resCap(dfs)));
2.279 } else {
2.280 free.set(w, res_graph.resCap(dfs));
2.281 }
2.282 @@ -629,9 +633,9 @@
2.283
2.284 if (__augment) {
2.285 typename ErasingResGW::Node n=t;
2.286 - Number augment_value=free.get(n);
2.287 - while (erasing_res_graph.valid(pred.get(n))) {
2.288 - typename ErasingResGW::OutEdgeIt e=pred.get(n);
2.289 + Number augment_value=free[n];
2.290 + while (erasing_res_graph.valid(pred[n])) {
2.291 + typename ErasingResGW::OutEdgeIt e=pred[n];
2.292 res_graph.augment(e, augment_value);
2.293 n=erasing_res_graph.tail(e);
2.294 if (res_graph.resCap(e)==0)
2.295 @@ -644,95 +648,6 @@
2.296 return _augment;
2.297 }
2.298
2.299 -// bool augmentOnBlockingFlow2() {
2.300 -// bool _augment=false;
2.301 -
2.302 -// //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
2.303 -// typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
2.304 -// typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
2.305 -// typedef typename EAugGraph::Edge EAugEdge;
2.306 -
2.307 -// EAugGraph res_graph(*G, *flow, *capacity);
2.308 -
2.309 -// //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
2.310 -// BfsIterator5<
2.311 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
2.312 -// /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
2.313 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
2.314 -
2.315 -// bfs.pushAndSetReached(s);
2.316 -
2.317 -// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
2.318 -// NodeMap<int>& dist=res_graph.dist;
2.319 -
2.320 -// while ( !bfs.finished() ) {
2.321 -// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
2.322 -// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
2.323 -// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
2.324 -// }
2.325 -// ++bfs;
2.326 -// } //computing distances from s in the residual graph
2.327 -
2.328 -// bool __augment=true;
2.329 -
2.330 -// while (__augment) {
2.331 -
2.332 -// __augment=false;
2.333 -// //computing blocking flow with dfs
2.334 -// typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
2.335 -// DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
2.336 -// dfs(res_graph);
2.337 -// typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
2.338 -// pred.set(s, EAugEdge(INVALID));
2.339 -// //invalid iterators for sources
2.340 -
2.341 -// typename EAugGraph::NodeMap<Number> free(res_graph);
2.342 -
2.343 -// dfs.pushAndSetReached(s);
2.344 -// while (!dfs.finished()) {
2.345 -// ++dfs;
2.346 -// if (res_graph.valid(EAugOutEdgeIt(dfs))) {
2.347 -// if (dfs.isBNodeNewlyReached()) {
2.348 -
2.349 -// typename EAugGraph::Node v=res_graph.aNode(dfs);
2.350 -// typename EAugGraph::Node w=res_graph.bNode(dfs);
2.351 -
2.352 -// pred.set(w, EAugOutEdgeIt(dfs));
2.353 -// if (res_graph.valid(pred.get(v))) {
2.354 -// free.set(w, std::min(free.get(v), res_graph.free(dfs)));
2.355 -// } else {
2.356 -// free.set(w, res_graph.free(dfs));
2.357 -// }
2.358 -
2.359 -// if (w==t) {
2.360 -// __augment=true;
2.361 -// _augment=true;
2.362 -// break;
2.363 -// }
2.364 -// } else {
2.365 -// res_graph.erase(dfs);
2.366 -// }
2.367 -// }
2.368 -
2.369 -// }
2.370 -
2.371 -// if (__augment) {
2.372 -// typename EAugGraph::Node n=t;
2.373 -// Number augment_value=free.get(t);
2.374 -// while (res_graph.valid(pred.get(n))) {
2.375 -// EAugEdge e=pred.get(n);
2.376 -// res_graph.augment(e, augment_value);
2.377 -// n=res_graph.tail(e);
2.378 -// if (res_graph.free(e)==0)
2.379 -// res_graph.erase(e);
2.380 -// }
2.381 -// }
2.382 -
2.383 -// }
2.384 -
2.385 -// return _augment;
2.386 -// }
2.387 -
2.388 void run() {
2.389 //int num_of_augmentations=0;
2.390 while (augmentOnShortestPath()) {
2.391 @@ -754,8 +669,8 @@
2.392 Number flowValue() {
2.393 Number a=0;
2.394 OutEdgeIt e;
2.395 - for(gw.first(e, s); gw.valid(e); gw.next(e)) {
2.396 - a+=flow->get(e);
2.397 + for(g->first(e, s); g->valid(e); g->next(e)) {
2.398 + a+=(*flow)[e];
2.399 }
2.400 return a;
2.401 }
3.1 --- a/src/work/marci/edmonds_karp_demo.cc Mon Apr 05 15:31:21 2004 +0000
3.2 +++ b/src/work/marci/edmonds_karp_demo.cc Mon Apr 05 16:52:46 2004 +0000
3.3 @@ -3,11 +3,11 @@
3.4 #include <fstream>
3.5
3.6 #include <list_graph.h>
3.7 -#include <smart_graph.h>
3.8 +//#include <smart_graph.h>
3.9 #include <dimacs.h>
3.10 #include <edmonds_karp.h>
3.11 #include <time_measure.h>
3.12 -#include <graph_wrapper.h>
3.13 +//#include <graph_wrapper.h>
3.14
3.15 class CM {
3.16 public:
3.17 @@ -90,17 +90,14 @@
3.18
3.19
3.20 {
3.21 - typedef TrivGraphWrapper<const Graph> GW;
3.22 - GW gw(G);
3.23 std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
3.24 - GW::EdgeMap<int> flow(gw); //0 flow
3.25 + Graph::EdgeMap<int> flow(G); //0 flow
3.26
3.27 Timer ts;
3.28 ts.reset();
3.29
3.30 - typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
3.31 - EMW cw(cap);
3.32 - MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
3.33 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
3.34 + max_flow_test(G, s, t, flow, cap);
3.35 int i=0;
3.36 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) {
3.37 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
3.38 @@ -121,17 +118,14 @@
3.39 }
3.40
3.41 {
3.42 - typedef TrivGraphWrapper<const Graph> GW;
3.43 - GW gw(G);
3.44 std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
3.45 - GW::EdgeMap<int> flow(gw); //0 flow
3.46 + Graph::EdgeMap<int> flow(G); //0 flow
3.47
3.48 Timer ts;
3.49 ts.reset();
3.50
3.51 - typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
3.52 - EMW cw(cap);
3.53 - MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
3.54 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
3.55 + max_flow_test(G, s, t, flow, cap);
3.56 int i=0;
3.57 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
3.58 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
3.59 @@ -152,17 +146,14 @@
3.60 }
3.61
3.62 {
3.63 - typedef TrivGraphWrapper<const Graph> GW;
3.64 - GW gw(G);
3.65 std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
3.66 - GW::EdgeMap<int> flow(gw); //0 flow
3.67 + Graph::EdgeMap<int> flow(G); //0 flow
3.68
3.69 Timer ts;
3.70 ts.reset();
3.71
3.72 - typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
3.73 - EMW cw(cap);
3.74 - MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
3.75 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
3.76 + max_flow_test(G, s, t, flow, cap);
3.77 int i=0;
3.78 while (max_flow_test.augmentOnBlockingFlow2()) {
3.79 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
3.80 @@ -183,17 +174,14 @@
3.81 }
3.82
3.83 {
3.84 - typedef TrivGraphWrapper<const Graph> GW;
3.85 - GW gw(G);
3.86 std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
3.87 - GW::EdgeMap<int> flow(gw); //0 flow
3.88 + Graph::EdgeMap<int> flow(G); //0 flow
3.89
3.90 Timer ts;
3.91 ts.reset();
3.92
3.93 - typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
3.94 - EMW cw(cap);
3.95 - MaxFlow<GW, int, GW::EdgeMap<int>, EMW> max_flow_test(gw, s, t, flow, cw);
3.96 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
3.97 + max_flow_test(G, s, t, flow, cap);
3.98 int i=0;
3.99 while (max_flow_test.augmentOnShortestPath()) {
3.100 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
4.1 --- a/src/work/marci/experiment/iterator_bfs_demo.cc Mon Apr 05 15:31:21 2004 +0000
4.2 +++ b/src/work/marci/experiment/iterator_bfs_demo.cc Mon Apr 05 16:52:46 2004 +0000
4.3 @@ -5,8 +5,8 @@
4.4
4.5 #include <list_graph.h>
4.6 //#include <smart_graph.h>
4.7 -#include <bfs_iterator_1.h>
4.8 -#include <graph_wrapper_1.h>
4.9 +#include <bfs_iterator.h>
4.10 +#include <graph_wrapper.h>
4.11
4.12 using namespace hugo;
4.13 using std::cout;
5.1 --- a/src/work/marci/experiment/iterator_bfs_demo_1.cc Mon Apr 05 15:31:21 2004 +0000
5.2 +++ b/src/work/marci/experiment/iterator_bfs_demo_1.cc Mon Apr 05 16:52:46 2004 +0000
5.3 @@ -5,8 +5,8 @@
5.4
5.5 #include <list_graph.h>
5.6 #include <smart_graph.h>
5.7 -#include <bfs_iterator.h>
5.8 -#include <graph_wrapper.h>
5.9 +#include <bfs_iterator_1.h>
5.10 +#include <graph_wrapper_1.h>
5.11
5.12 using namespace hugo;
5.13 using std::cout;
6.1 --- a/src/work/marci/graph_wrapper.h Mon Apr 05 15:31:21 2004 +0000
6.2 +++ b/src/work/marci/graph_wrapper.h Mon Apr 05 16:52:46 2004 +0000
6.3 @@ -12,7 +12,12 @@
6.4 Graph* graph;
6.5
6.6 public:
6.7 - typedef Graph BaseGraph;
6.8 + typedef Graph ParentGraph;
6.9 +
6.10 +// TrivGraphWrapper() : graph(0) { }
6.11 + TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
6.12 +// void setGraph(Graph& _graph) { graph = &_graph; }
6.13 +// Graph& getGraph() const { return *graph; }
6.14
6.15 typedef typename Graph::Node Node;
6.16 class NodeIt : public Graph::NodeIt {
6.17 @@ -24,7 +29,6 @@
6.18 Graph::NodeIt(*(_G.graph)) { }
6.19 };
6.20 typedef typename Graph::Edge Edge;
6.21 - //typedef typename Graph::OutEdgeIt OutEdgeIt;
6.22 class OutEdgeIt : public Graph::OutEdgeIt {
6.23 public:
6.24 OutEdgeIt() { }
6.25 @@ -33,7 +37,6 @@
6.26 OutEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :
6.27 Graph::OutEdgeIt(*(_G.graph), n) { }
6.28 };
6.29 - //typedef typename Graph::InEdgeIt InEdgeIt;
6.30 class InEdgeIt : public Graph::InEdgeIt {
6.31 public:
6.32 InEdgeIt() { }
6.33 @@ -43,7 +46,6 @@
6.34 Graph::InEdgeIt(*(_G.graph), n) { }
6.35 };
6.36 //typedef typename Graph::SymEdgeIt SymEdgeIt;
6.37 - //typedef typename Graph::EdgeIt EdgeIt;
6.38 class EdgeIt : public Graph::EdgeIt {
6.39 public:
6.40 EdgeIt() { }
6.41 @@ -53,12 +55,6 @@
6.42 Graph::EdgeIt(*(_G.graph)) { }
6.43 };
6.44
6.45 - //TrivGraphWrapper() : graph(0) { }
6.46 - TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
6.47 -
6.48 -// void setGraph(Graph& _graph) { graph = &_graph; }
6.49 -// Graph& getGraph() const { return (*graph); }
6.50 -
6.51 NodeIt& first(NodeIt& i) const {
6.52 i=NodeIt(*this);
6.53 return i;
6.54 @@ -68,7 +64,6 @@
6.55 return i;
6.56 }
6.57 // template<typename I> I& first(I& i) const {
6.58 -// //return graph->first(i);
6.59 // i=I(*this);
6.60 // return i;
6.61 // }
6.62 @@ -81,7 +76,6 @@
6.63 return i;
6.64 }
6.65 // template<typename I, typename P> I& first(I& i, const P& p) const {
6.66 -// //return graph->first(i, p);
6.67 // i=I(*this, p);
6.68 // return i;
6.69 // }
6.70 @@ -91,16 +85,16 @@
6.71 template<typename I> I& next(I &i) const { graph->next(i); return i; }
6.72
6.73 template< typename It > It first() const {
6.74 - It e; first(e); return e; }
6.75 + It e; this->first(e); return e; }
6.76
6.77 template< typename It > It first(const Node& v) const {
6.78 - It e; first(e, v); return e; }
6.79 + It e; this->first(e, v); return e; }
6.80
6.81 Node head(const Edge& e) const { return graph->head(e); }
6.82 Node tail(const Edge& e) const { return graph->tail(e); }
6.83
6.84 - template<typename I> bool valid(const I& i) const
6.85 - { return graph->valid(i); }
6.86 + template<typename I> bool valid(const I& i) const {
6.87 + return graph->valid(i); }
6.88
6.89 //template<typename I> void setInvalid(const I &i);
6.90 //{ return graph->setInvalid(i); }
6.91 @@ -137,107 +131,103 @@
6.92 Graph::EdgeMap<T>(*(_G.graph), a) { }
6.93 };
6.94
6.95 - template<typename Map, typename T> class NodeMapWrapper {
6.96 - protected:
6.97 - Map* map;
6.98 - public:
6.99 - NodeMapWrapper(Map& _map) : map(&_map) { }
6.100 - //template<typename T>
6.101 - void set(Node n, T a) { map->set(n, a); }
6.102 - //template<typename T>
6.103 - T get(Node n) const { return map->get(n); }
6.104 - };
6.105 +// template<typename Map, typename T> class NodeMapWrapper {
6.106 +// protected:
6.107 +// Map* map;
6.108 +// public:
6.109 +// NodeMapWrapper(Map& _map) : map(&_map) { }
6.110 +// void set(Node n, T a) { map->set(n, a); }
6.111 +// T get(Node n) const { return map->get(n); }
6.112 +// };
6.113
6.114 - template<typename Map, typename T> class EdgeMapWrapper {
6.115 - protected:
6.116 - Map* map;
6.117 - public:
6.118 - EdgeMapWrapper(Map& _map) : map(&_map) { }
6.119 - //template<typename T>
6.120 - void set(Edge n, T a) { map->set(n, a); }
6.121 - //template<typename T>
6.122 - T get(Edge n) const { return map->get(n); }
6.123 - };
6.124 +// template<typename Map, typename T> class EdgeMapWrapper {
6.125 +// protected:
6.126 +// Map* map;
6.127 +// public:
6.128 +// EdgeMapWrapper(Map& _map) : map(&_map) { }
6.129 +// void set(Edge n, T a) { map->set(n, a); }
6.130 +// T get(Edge n) const { return map->get(n); }
6.131 +// };
6.132 };
6.133
6.134 - template<typename GraphWrapper>
6.135 - class GraphWrapperSkeleton {
6.136 +
6.137 + template<typename Graph>
6.138 + class GraphWrapper {
6.139 protected:
6.140 - GraphWrapper gw;
6.141 + Graph* graph;
6.142
6.143 public:
6.144 - //typedef typename GraphWrapper::BaseGraph BaseGraph;
6.145 + typedef Graph ParentGraph;
6.146
6.147 -// typedef typename GraphWrapper::Node Node;
6.148 -// typedef typename GraphWrapper::NodeIt NodeIt;
6.149 -
6.150 -// typedef typename GraphWrapper::Edge Edge;
6.151 -// typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
6.152 -// typedef typename GraphWrapper::InEdgeIt InEdgeIt;
6.153 -// //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;
6.154 -// typedef typename GraphWrapper::EdgeIt EdgeIt;
6.155 -
6.156 - typedef typename GraphWrapper::Node Node;
6.157 - class NodeIt : public GraphWrapper::NodeIt {
6.158 +// GraphWrapper() : graph(0) { }
6.159 + GraphWrapper(Graph& _graph) : graph(&_graph) { }
6.160 +// void setGraph(Graph& _graph) { graph=&_graph; }
6.161 +// Graph& getGraph() const { return *graph; }
6.162 +
6.163 + typedef typename Graph::Node Node;
6.164 + class NodeIt : public Graph::NodeIt {
6.165 public:
6.166 NodeIt() { }
6.167 - NodeIt(const typename GraphWrapper::NodeIt& n) :
6.168 - GraphWrapper::NodeIt(n) { }
6.169 - NodeIt(const Invalid& i) : GraphWrapper::NodeIt(i) { }
6.170 - NodeIt(const GraphWrapperSkeleton<GraphWrapper>& _G) :
6.171 - GraphWrapper::NodeIt(_G.gw) { }
6.172 + NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
6.173 + NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
6.174 + NodeIt(const GraphWrapper<Graph>& _G) :
6.175 + Graph::NodeIt(*(_G.graph)) { }
6.176 };
6.177 - typedef typename GraphWrapper::Edge Edge;
6.178 - //typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
6.179 - class OutEdgeIt : public GraphWrapper::OutEdgeIt {
6.180 + typedef typename Graph::Edge Edge;
6.181 + class OutEdgeIt : public Graph::OutEdgeIt {
6.182 public:
6.183 OutEdgeIt() { }
6.184 - OutEdgeIt(const typename GraphWrapper::OutEdgeIt& e) :
6.185 - GraphWrapper::OutEdgeIt(e) { }
6.186 - OutEdgeIt(const Invalid& i) : GraphWrapper::OutEdgeIt(i) { }
6.187 - OutEdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G, const Node& n) :
6.188 - GraphWrapper::OutEdgeIt(_G.gw, n) { }
6.189 + OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
6.190 + OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
6.191 + OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) :
6.192 + Graph::OutEdgeIt(*(_G.graph), n) { }
6.193 };
6.194 - //typedef typename GraphWrapper::InEdgeIt InEdgeIt;
6.195 - class InEdgeIt : public GraphWrapper::InEdgeIt {
6.196 + class InEdgeIt : public Graph::InEdgeIt {
6.197 public:
6.198 InEdgeIt() { }
6.199 - InEdgeIt(const typename GraphWrapper::InEdgeIt& e) :
6.200 - GraphWrapper::InEdgeIt(e) { }
6.201 - InEdgeIt(const Invalid& i) : GraphWrapper::InEdgeIt(i) { }
6.202 - InEdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G, const Node& n) :
6.203 - GraphWrapper::InEdgeIt(_G.gw, n) { }
6.204 + InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
6.205 + InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
6.206 + InEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) :
6.207 + Graph::InEdgeIt(*(_G.graph), n) { }
6.208 };
6.209 - //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;
6.210 - //typedef typename GraphWrapper::EdgeIt EdgeIt;
6.211 - class EdgeIt : public GraphWrapper::EdgeIt {
6.212 + //typedef typename Graph::SymEdgeIt SymEdgeIt;
6.213 + class EdgeIt : public Graph::EdgeIt {
6.214 public:
6.215 EdgeIt() { }
6.216 - EdgeIt(const typename GraphWrapper::EdgeIt& e) :
6.217 - GraphWrapper::EdgeIt(e) { }
6.218 - EdgeIt(const Invalid& i) : GraphWrapper::EdgeIt(i) { }
6.219 - EdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G) :
6.220 - GraphWrapper::EdgeIt(_G.gw) { }
6.221 + EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
6.222 + EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
6.223 + EdgeIt(const GraphWrapper<Graph>& _G) :
6.224 + Graph::EdgeIt(*(_G.graph)) { }
6.225 };
6.226 -
6.227 -
6.228 - //GraphWrapperSkeleton() : gw() { }
6.229 - GraphWrapperSkeleton(GraphWrapper _gw) : gw(_gw) { }
6.230 -
6.231 - //void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); }
6.232 - //BaseGraph& getGraph() const { return gw.getGraph(); }
6.233 -
6.234 - template<typename I> I& first(I& i) const {
6.235 - i=I(*this);
6.236 +
6.237 + NodeIt& first(NodeIt& i) const {
6.238 + i=NodeIt(*this);
6.239 return i;
6.240 }
6.241 - template<typename I, typename P> I& first(I& i, const P& p) const {
6.242 - i=I(*this, p);
6.243 - return i;
6.244 + EdgeIt& first(EdgeIt& i) const {
6.245 + i=EdgeIt(*this);
6.246 + return i;
6.247 }
6.248 +// template<typename I> I& first(I& i) const {
6.249 +// i=I(*this);
6.250 +// return i;
6.251 +// }
6.252 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
6.253 + i=OutEdgeIt(*this, p);
6.254 + return i;
6.255 + }
6.256 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
6.257 + i=InEdgeIt(*this, p);
6.258 + return i;
6.259 + }
6.260 +// template<typename I, typename P> I& first(I& i, const P& p) const {
6.261 +// i=I(*this, p);
6.262 +// return i;
6.263 +// }
6.264
6.265 -// template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
6.266 - template<typename I> I& next(I &i) const { gw.next(i); return i; }
6.267 +// template<typename I> I getNext(const I& i) const {
6.268 +// return gw.getNext(i); }
6.269 + template<typename I> I& next(I &i) const { graph->next(i); return i; }
6.270
6.271 template< typename It > It first() const {
6.272 It e; this->first(e); return e; }
6.273 @@ -245,45 +235,49 @@
6.274 template< typename It > It first(const Node& v) const {
6.275 It e; this->first(e, v); return e; }
6.276
6.277 - Node head(const Edge& e) const { return gw.head(e); }
6.278 - Node tail(const Edge& e) const { return gw.tail(e); }
6.279 + Node head(const Edge& e) const { return graph->head(e); }
6.280 + Node tail(const Edge& e) const { return graph->tail(e); }
6.281
6.282 - template<typename I> bool valid(const I& i) const { return gw.valid(i); }
6.283 + template<typename I> bool valid(const I& i) const {
6.284 + return graph->valid(i); }
6.285
6.286 //template<typename I> void setInvalid(const I &i);
6.287 //{ return graph->setInvalid(i); }
6.288
6.289 - int nodeNum() const { return gw.nodeNum(); }
6.290 - int edgeNum() const { return gw.edgeNum(); }
6.291 + int nodeNum() const { return graph->nodeNum(); }
6.292 + int edgeNum() const { return graph->edgeNum(); }
6.293
6.294 - template<typename I> Node aNode(const I& e) const { return gw.aNode(e); }
6.295 - template<typename I> Node bNode(const I& e) const { return gw.bNode(e); }
6.296 + template<typename I> Node aNode(const I& e) const {
6.297 + return graph->aNode(e); }
6.298 + template<typename I> Node bNode(const I& e) const {
6.299 + return graph->bNode(e); }
6.300
6.301 - Node addNode() const { return gw.addNode(); }
6.302 + Node addNode() const { return graph->addNode(); }
6.303 Edge addEdge(const Node& tail, const Node& head) const {
6.304 - return gw.addEdge(tail, head); }
6.305 + return graph->addEdge(tail, head); }
6.306
6.307 - template<typename I> void erase(const I& i) const { gw.erase(i); }
6.308 + template<typename I> void erase(const I& i) const { graph->erase(i); }
6.309
6.310 - void clear() const { gw.clear(); }
6.311 + void clear() const { graph->clear(); }
6.312
6.313 - template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
6.314 + template<typename T> class NodeMap : public Graph::NodeMap<T> {
6.315 public:
6.316 - NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) :
6.317 - GraphWrapper::NodeMap<T>(_G.gw) { }
6.318 - NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) :
6.319 - GraphWrapper::NodeMap<T>(_G.gw, a) { }
6.320 + NodeMap(const GraphWrapper<Graph>& _G) :
6.321 + Graph::NodeMap<T>(*(_G.graph)) { }
6.322 + NodeMap(const GraphWrapper<Graph>& _G, T a) :
6.323 + Graph::NodeMap<T>(*(_G.graph), a) { }
6.324 };
6.325
6.326 - template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
6.327 + template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
6.328 public:
6.329 - EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) :
6.330 - GraphWrapper::EdgeMap<T>(_G.gw) { }
6.331 - EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) :
6.332 - GraphWrapper::EdgeMap<T>(_G.gw, a) { }
6.333 + EdgeMap(const GraphWrapper<Graph>& _G) :
6.334 + Graph::EdgeMap<T>(*(_G.graph)) { }
6.335 + EdgeMap(const GraphWrapper<Graph>& _G, T a) :
6.336 + Graph::EdgeMap<T>(*(_G.graph), a) { }
6.337 };
6.338 };
6.339
6.340 +
6.341 // template<typename Graph>
6.342 // class RevGraphWrapper
6.343 // {
6.344 @@ -291,7 +285,7 @@
6.345 // Graph* graph;
6.346
6.347 // public:
6.348 -// typedef Graph BaseGraph;
6.349 +// typedef Graph ParentGraph;
6.350
6.351 // typedef typename Graph::Node Node;
6.352 // typedef typename Graph::NodeIt NodeIt;
6.353 @@ -364,139 +358,59 @@
6.354 // };
6.355 // };
6.356
6.357 -// template<typename /*Graph*/GraphWrapper
6.358 -// /*=typename GraphWrapperSkeleton< TrivGraphWrapper<Graph>*/ >
6.359 -// class RevGraphWrapper :
6.360 -// public GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/ {
6.361 -// protected:
6.362 -// //Graph* graph;
6.363 -
6.364 -// public:
6.365 -// //typedef Graph BaseGraph;
6.366
6.367 -// //typedef typename Graph::Node Node;
6.368 -// //typedef typename Graph::NodeIt NodeIt;
6.369 -
6.370 -// //typedef typename Graph::Edge Edge;
6.371 -// typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::OutEdgeIt InEdgeIt;
6.372 -// typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::InEdgeIt OutEdgeIt;
6.373 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
6.374 -// //typedef typename Graph::EdgeIt EdgeIt;
6.375 -
6.376 -// //RevGraphWrapper() : graph(0) { }
6.377 -// RevGraphWrapper(GraphWrapper _gw/*BaseGraph& _graph*/) : GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/(_gw/*TrivGraphWrapper<Graph>(_graph)*/) { }
6.378 -
6.379 -// //void setGraph(Graph& _graph) { graph = &_graph; }
6.380 -// //Graph& getGraph() const { return (*graph); }
6.381 -
6.382 -// //template<typename I> I& first(I& i) const { return graph->first(i); }
6.383 -// //template<typename I, typename P> I& first(I& i, const P& p) const {
6.384 -// // return graph->first(i, p); }
6.385 -
6.386 -// //template<typename I> I getNext(const I& i) const {
6.387 -// // return graph->getNext(i); }
6.388 -// //template<typename I> I& next(I &i) const { return graph->next(i); }
6.389 -
6.390 -// //template< typename It > It first() const {
6.391 -// // It e; first(e); return e; }
6.392 -
6.393 -// //template< typename It > It first(const Node& v) const {
6.394 -// // It e; first(e, v); return e; }
6.395 -
6.396 -// //Node head(const Edge& e) const { return graph->tail(e); }
6.397 -// //Node tail(const Edge& e) const { return graph->head(e); }
6.398 -
6.399 -// //template<typename I> bool valid(const I& i) const
6.400 -// // { return graph->valid(i); }
6.401 -
6.402 -// //template<typename I> void setInvalid(const I &i);
6.403 -// //{ return graph->setInvalid(i); }
6.404 -
6.405 -// //template<typename I> Node aNode(const I& e) const {
6.406 -// // return graph->aNode(e); }
6.407 -// //template<typename I> Node bNode(const I& e) const {
6.408 -// // return graph->bNode(e); }
6.409 -
6.410 -// //Node addNode() const { return graph->addNode(); }
6.411 -// //Edge addEdge(const Node& tail, const Node& head) const {
6.412 -// // return graph->addEdge(tail, head); }
6.413 -
6.414 -// //int nodeNum() const { return graph->nodeNum(); }
6.415 -// //int edgeNum() const { return graph->edgeNum(); }
6.416 -
6.417 -// //template<typename I> void erase(const I& i) const { graph->erase(i); }
6.418 -
6.419 -// //void clear() const { graph->clear(); }
6.420 -
6.421 -// template<typename T> class NodeMap :
6.422 -// public GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>
6.423 -// {
6.424 -// public:
6.425 -// NodeMap(const RevGraphWrapper<GraphWrapper>& _gw) :
6.426 -// GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw) { }
6.427 -// NodeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) :
6.428 -// GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw, a) { }
6.429 -// };
6.430 -
6.431 -// template<typename T> class EdgeMap :
6.432 -// public GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T> {
6.433 -// public:
6.434 -// EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw) :
6.435 -// GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw) { }
6.436 -// EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) :
6.437 -// GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw, a) { }
6.438 -// };
6.439 -// };
6.440 -
6.441 - template<typename GraphWrapper>
6.442 - class RevGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
6.443 + template<typename Graph>
6.444 + class RevGraphWrapper : public GraphWrapper<Graph> {
6.445 public:
6.446 - typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
6.447 - typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
6.448 + typedef typename GraphWrapper<Graph>::Node Node;
6.449 + typedef typename GraphWrapper<Graph>::Edge Edge;
6.450 //FIXME
6.451 - //If GraphWrapper::OutEdgeIt is not defined
6.452 + //If Graph::OutEdgeIt is not defined
6.453 //and we do not want to use RevGraphWrapper::InEdgeIt,
6.454 //this won't work, because of typedef
6.455 //OR
6.456 //graphs have to define their non-existing iterators to void
6.457 //Unfortunately all the typedefs are instantiated in templates,
6.458 //unlike other stuff
6.459 - typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt InEdgeIt;
6.460 - typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt OutEdgeIt;
6.461 + typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
6.462 + typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
6.463
6.464 - RevGraphWrapper(GraphWrapper _gw) :
6.465 - GraphWrapperSkeleton<GraphWrapper>(_gw) { }
6.466 +// RevGraphWrapper() : GraphWrapper<Graph>() { }
6.467 + RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
6.468
6.469 Node head(const Edge& e) const
6.470 - { return GraphWrapperSkeleton<GraphWrapper>::tail(e); }
6.471 + { return GraphWrapper<Graph>::tail(e); }
6.472 Node tail(const Edge& e) const
6.473 - { return GraphWrapperSkeleton<GraphWrapper>::head(e); }
6.474 + { return GraphWrapper<Graph>::head(e); }
6.475 };
6.476
6.477 //Subgraph on the same node-set and partial edge-set
6.478 - template<typename GraphWrapper, typename EdgeFilterMap>
6.479 - class SubGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
6.480 + template<typename Graph, typename EdgeFilterMap>
6.481 + class SubGraphWrapper : public GraphWrapper<Graph> {
6.482 protected:
6.483 EdgeFilterMap* filter_map;
6.484 public:
6.485 - typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
6.486 - typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
6.487 - typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
6.488 - typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt;
6.489 - typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt;
6.490 - typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt;
6.491 + typedef typename GraphWrapper<Graph>::Node Node;
6.492 + typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
6.493 + typedef typename GraphWrapper<Graph>::Edge Edge;
6.494 + typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
6.495 + typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt;
6.496 + typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt;
6.497
6.498 - SubGraphWrapper(GraphWrapper _gw, EdgeFilterMap& _filter_map) :
6.499 - GraphWrapperSkeleton<GraphWrapper>(_gw), filter_map(&_filter_map) { }
6.500 +// SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { }
6.501 + SubGraphWrapper(Graph& _graph, EdgeFilterMap& _filter_map) :
6.502 + GraphWrapper<Graph>(_graph), filter_map(&_filter_map) { }
6.503
6.504 template<typename I> I& first(I& i) const {
6.505 - gw.first(i);
6.506 - while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
6.507 + graph->first(i);
6.508 + //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
6.509 + while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); }
6.510 return i;
6.511 }
6.512 template<typename I, typename P> I& first(I& i, const P& p) const {
6.513 - gw.first(i, p);
6.514 - while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
6.515 + graph->first(i, p);
6.516 +// while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
6.517 + while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); }
6.518 return i;
6.519 }
6.520
6.521 @@ -504,8 +418,9 @@
6.522 // return gw.getNext(i);
6.523 //}
6.524 template<typename I> I& next(I &i) const {
6.525 - gw.next(i);
6.526 - while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
6.527 + graph->next(i);
6.528 +// while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); }
6.529 + while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); }
6.530 return i;
6.531 }
6.532
6.533 @@ -523,7 +438,7 @@
6.534 // GraphWrapper gw;
6.535
6.536 // public:
6.537 -// typedef GraphWrapper BaseGraph;
6.538 +// typedef GraphWrapper ParentGraph;
6.539
6.540 // typedef typename GraphWrapper::Node Node;
6.541 // typedef typename GraphWrapper::NodeIt NodeIt;
6.542 @@ -676,39 +591,21 @@
6.543 // };
6.544
6.545
6.546 - template<typename GraphWrapper>
6.547 - class UndirGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
6.548 + template<typename Graph>
6.549 + class UndirGraphWrapper : public GraphWrapper<Graph> {
6.550 protected:
6.551 -// GraphWrapper gw;
6.552 + typedef typename Graph::Edge GraphEdge;
6.553 + typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
6.554 + typedef typename Graph::InEdgeIt GraphInEdgeIt;
6.555 + public:
6.556 + typedef typename GraphWrapper<Graph>::Node Node;
6.557 + typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
6.558
6.559 - public:
6.560 - //typedef GraphWrapper BaseGraph;
6.561 +// UndirGraphWrapper() : GraphWrapper<Graph>() { }
6.562 + UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
6.563
6.564 - typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
6.565 - typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
6.566 -
6.567 - //private:
6.568 - //FIXME ezeknek valojaban a GraphWrapper megfelelo dolgai kellene hogy
6.569 - //legyenek, at kell irni
6.570 - typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
6.571 - GraphWrapper::Edge GraphEdge;
6.572 - typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
6.573 - GraphWrapper::OutEdgeIt GraphOutEdgeIt;
6.574 - typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
6.575 - GraphWrapper::InEdgeIt GraphInEdgeIt;
6.576 - //public:
6.577 -
6.578 - //UndirGraphWrapper() : graph(0) { }
6.579 - UndirGraphWrapper(GraphWrapper _gw) :
6.580 - GraphWrapperSkeleton<GraphWrapper>(_gw) { }
6.581 -
6.582 - //UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
6.583 -
6.584 - //void setGraph(Graph& _graph) { graph = &_graph; }
6.585 - //Graph& getGraph() const { return (*graph); }
6.586 -
6.587 class Edge {
6.588 - friend class UndirGraphWrapper<GraphWrapper>;
6.589 + friend class UndirGraphWrapper<Graph>;
6.590 protected:
6.591 bool out_or_in; //true iff out
6.592 GraphOutEdgeIt out;
6.593 @@ -741,42 +638,42 @@
6.594 };
6.595
6.596 class OutEdgeIt : public Edge {
6.597 - friend class UndirGraphWrapper<GraphWrapper>;
6.598 + friend class UndirGraphWrapper<Graph>;
6.599 public:
6.600 OutEdgeIt() : Edge() { }
6.601 OutEdgeIt(const Invalid& i) : Edge(i) { }
6.602 - OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)
6.603 + OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& n)
6.604 : Edge() {
6.605 - out_or_in=true; _G.gw.first(out, n);
6.606 - if (!(_G.gw.valid(out))) { out_or_in=false; _G.gw.first(in, n); }
6.607 + out_or_in=true; _G.graph->first(out, n);
6.608 + if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); }
6.609 }
6.610 };
6.611
6.612 typedef OutEdgeIt InEdgeIt;
6.613
6.614 class EdgeIt : public Edge {
6.615 - friend class UndirGraphWrapper<GraphWrapper>;
6.616 + friend class UndirGraphWrapper<Graph>;
6.617 protected:
6.618 NodeIt v;
6.619 public:
6.620 EdgeIt() : Edge() { }
6.621 EdgeIt(const Invalid& i) : Edge(i) { }
6.622 - EdgeIt(const UndirGraphWrapper<GraphWrapper>& _G)
6.623 + EdgeIt(const UndirGraphWrapper<Graph>& _G)
6.624 : Edge() {
6.625 out_or_in=true;
6.626 //Node v;
6.627 _G.first(v);
6.628 - if (_G.valid(v)) _G.gw.first(out); else out=INVALID;
6.629 - while (_G.valid(v) && !_G.gw.valid(out)) {
6.630 - _G.gw.next(v);
6.631 - if (_G.valid(v)) _G.gw.first(out);
6.632 + if (_G.valid(v)) _G.graph->first(out); else out=INVALID;
6.633 + while (_G.valid(v) && !_G.graph->valid(out)) {
6.634 + _G.graph->next(v);
6.635 + if (_G.valid(v)) _G.graph->first(out);
6.636 }
6.637 }
6.638 };
6.639
6.640 OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
6.641 - e.out_or_in=true; gw.first(e.out, n);
6.642 - if (!(gw.valid(e.out))) { e.out_or_in=false; gw.first(e.in, n); }
6.643 + e.out_or_in=true; graph->first(e.out, n);
6.644 + if (!(graph->valid(e.out))) { e.out_or_in=false; graph->first(e.in, n); }
6.645 return e;
6.646 }
6.647
6.648 @@ -784,47 +681,47 @@
6.649 e.out_or_in=true;
6.650 //NodeIt v;
6.651 first(e.v);
6.652 - if (valid(e.v)) gw.first(e.out, e.v); else e.out=INVALID;
6.653 - while (valid(e.v) && !gw.valid(e.out)) {
6.654 - gw.next(e.v);
6.655 - if (valid(e.v)) gw.first(e.out, e.v);
6.656 + if (valid(e.v)) graph->first(e.out, e.v); else e.out=INVALID;
6.657 + while (valid(e.v) && !graph->valid(e.out)) {
6.658 + graph->next(e.v);
6.659 + if (valid(e.v)) graph->first(e.out, e.v);
6.660 }
6.661 return e;
6.662 }
6.663
6.664 - template<typename I> I& first(I& i) const { gw.first(i); return i; }
6.665 + template<typename I> I& first(I& i) const { graph->first(i); return i; }
6.666 template<typename I, typename P> I& first(I& i, const P& p) const {
6.667 - gw.first(i, p); return i; }
6.668 + graph->first(i, p); return i; }
6.669
6.670 OutEdgeIt& next(OutEdgeIt& e) const {
6.671 if (e.out_or_in) {
6.672 - Node n=gw.tail(e.out);
6.673 - gw.next(e.out);
6.674 - if (!gw.valid(e.out)) { e.out_or_in=false; gw.first(e.in, n); }
6.675 + Node n=graph->tail(e.out);
6.676 + graph->next(e.out);
6.677 + if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); }
6.678 } else {
6.679 - gw.next(e.in);
6.680 + graph->next(e.in);
6.681 }
6.682 return e;
6.683 }
6.684
6.685 EdgeIt& next(EdgeIt& e) const {
6.686 //NodeIt v=tail(e);
6.687 - gw.next(e.out);
6.688 - while (valid(e.v) && !gw.valid(e.out)) {
6.689 + graph->next(e.out);
6.690 + while (valid(e.v) && !graph->valid(e.out)) {
6.691 next(e.v);
6.692 - if (valid(e.v)) gw.first(e.out, e.v);
6.693 + if (valid(e.v)) graph->first(e.out, e.v);
6.694 }
6.695 return e;
6.696 }
6.697
6.698 - template<typename I> I& next(I &i) const { return gw.next(i); }
6.699 + template<typename I> I& next(I &i) const { return graph->next(i); }
6.700 // template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
6.701
6.702 template< typename It > It first() const {
6.703 - It e; first(e); return e; }
6.704 + It e; this->first(e); return e; }
6.705
6.706 template< typename It > It first(const Node& v) const {
6.707 - It e; first(e, v); return e; }
6.708 + It e; this->first(e, v); return e; }
6.709
6.710 // Node head(const Edge& e) const { return gw.head(e); }
6.711 // Node tail(const Edge& e) const { return gw.tail(e); }
6.712 @@ -841,9 +738,9 @@
6.713 // return graph->bNode(e); }
6.714
6.715 Node aNode(const OutEdgeIt& e) const {
6.716 - if (e.out_or_in) return gw.tail(e); else return gw.head(e); }
6.717 + if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
6.718 Node bNode(const OutEdgeIt& e) const {
6.719 - if (e.out_or_in) return gw.head(e); else return gw.tail(e); }
6.720 + if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
6.721
6.722 // Node addNode() const { return gw.addNode(); }
6.723
6.724 @@ -855,21 +752,21 @@
6.725
6.726 // void clear() const { gw.clear(); }
6.727
6.728 -// template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
6.729 +// template<typename T> class NodeMap : public Graph::NodeMap<T> {
6.730 // public:
6.731 -// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
6.732 -// GraphWrapper::NodeMap<T>(_G.gw) { }
6.733 -// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
6.734 -// GraphWrapper::NodeMap<T>(_G.gw, a) { }
6.735 +// NodeMap(const UndirGraphWrapper<Graph>& _G) :
6.736 +// Graph::NodeMap<T>(_G.gw) { }
6.737 +// NodeMap(const UndirGraphWrapper<Graph>& _G, T a) :
6.738 +// Graph::NodeMap<T>(_G.gw, a) { }
6.739 // };
6.740
6.741 // template<typename T> class EdgeMap :
6.742 -// public GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T> {
6.743 +// public GraphWrapperSkeleton<Graph>::EdgeMap<T> {
6.744 // public:
6.745 -// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
6.746 -// GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T>(_G.gw) { }
6.747 -// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
6.748 -// GraphWrapper::EdgeMap<T>(_G.gw, a) { }
6.749 +// EdgeMap(const UndirGraphWrapper<Graph>& _G) :
6.750 +// GraphWrapperSkeleton<Graph>::EdgeMap<T>(_G.gw) { }
6.751 +// EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) :
6.752 +// Graph::EdgeMap<T>(_G.gw, a) { }
6.753 // };
6.754 };
6.755
6.756 @@ -883,7 +780,7 @@
6.757 // Graph* graph;
6.758
6.759 // public:
6.760 -// typedef Graph BaseGraph;
6.761 +// typedef Graph ParentGraph;
6.762
6.763 // typedef typename Graph::Node Node;
6.764 // typedef typename Graph::Edge Edge;
6.765 @@ -946,32 +843,22 @@
6.766 // };
6.767
6.768
6.769 - template<typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
6.770 - class ResGraphWrapper : public GraphWrapperSkeleton<GraphWrapper>{
6.771 + template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
6.772 + class ResGraphWrapper : public GraphWrapper<Graph>{
6.773 public:
6.774 - //typedef Graph BaseGraph;
6.775 - //typedef TrivGraphWrapper<const Graph> GraphWrapper;
6.776 - typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
6.777 - typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
6.778 - private:
6.779 - typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
6.780 - GraphWrapper::OutEdgeIt OldOutEdgeIt;
6.781 - typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
6.782 - GraphWrapper::InEdgeIt OldInEdgeIt;
6.783 + typedef typename GraphWrapper<Graph>::Node Node;
6.784 + typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
6.785 protected:
6.786 - //const Graph* graph;
6.787 - //GraphWrapper gw;
6.788 + typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
6.789 + typedef typename Graph::InEdgeIt GraphInEdgeIt;
6.790 + typedef typename Graph::Edge GraphEdge;
6.791 FlowMap* flow;
6.792 const CapacityMap* capacity;
6.793 public:
6.794
6.795 - ResGraphWrapper(const GraphWrapper& _gw, FlowMap& _flow,
6.796 + ResGraphWrapper(Graph& _graph, FlowMap& _flow,
6.797 const CapacityMap& _capacity) :
6.798 - GraphWrapperSkeleton<GraphWrapper>(_gw),
6.799 - flow(&_flow), capacity(&_capacity) { }
6.800 -
6.801 - //void setGraph(const Graph& _graph) { graph = &_graph; }
6.802 - //const Graph& getGraph() const { return (*graph); }
6.803 + GraphWrapper<Graph>(_graph), flow(&_flow), capacity(&_capacity) { }
6.804
6.805 class Edge;
6.806 class OutEdgeIt;
6.807 @@ -979,11 +866,11 @@
6.808 friend class OutEdgeIt;
6.809
6.810 class Edge {
6.811 - friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
6.812 + friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
6.813 protected:
6.814 bool out_or_in; //true, iff out
6.815 - OldOutEdgeIt out;
6.816 - OldInEdgeIt in;
6.817 + GraphOutEdgeIt out;
6.818 + GraphInEdgeIt in;
6.819 public:
6.820 Edge() : out_or_in(true) { }
6.821 Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
6.822 @@ -1001,24 +888,27 @@
6.823 else
6.824 return (u.out_or_in || u.in!=v.in);
6.825 }
6.826 + operator GraphEdge() const {
6.827 + if (out_or_in) return(out); else return(in);
6.828 + }
6.829 };
6.830
6.831
6.832 class OutEdgeIt : public Edge {
6.833 - friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
6.834 + friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
6.835 public:
6.836 OutEdgeIt() { }
6.837 //FIXME
6.838 OutEdgeIt(const Edge& e) : Edge(e) { }
6.839 OutEdgeIt(const Invalid& i) : Edge(i) { }
6.840 protected:
6.841 - OutEdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
6.842 - resG.gw.first(out, v);
6.843 - while( resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
6.844 - if (!resG.gw.valid(out)) {
6.845 + OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
6.846 + resG.graph->first(out, v);
6.847 + while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
6.848 + if (!resG.graph->valid(out)) {
6.849 out_or_in=0;
6.850 - resG.gw.first(in, v);
6.851 - while( resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
6.852 + resG.graph->first(in, v);
6.853 + while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
6.854 }
6.855 }
6.856 // public:
6.857 @@ -1044,30 +934,30 @@
6.858 typedef void InEdgeIt;
6.859
6.860 class EdgeIt : public Edge {
6.861 - friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
6.862 + friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
6.863 NodeIt v;
6.864 public:
6.865 EdgeIt() { }
6.866 //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
6.867 EdgeIt(const Invalid& i) : Edge(i) { }
6.868 - EdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG) : Edge() {
6.869 - resG.gw.first(v);
6.870 - if (resG.gw.valid(v)) resG.gw.first(out, v); else out=INVALID;
6.871 - while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
6.872 - while (resG.gw.valid(v) && !resG.gw.valid(out)) {
6.873 - resG.gw.next(v);
6.874 - if (resG.gw.valid(v)) resG.gw.first(out, v);
6.875 - while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
6.876 + EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
6.877 + resG.graph->first(v);
6.878 + if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
6.879 + while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
6.880 + while (resG.graph->valid(v) && !resG.graph->valid(out)) {
6.881 + resG.graph->next(v);
6.882 + if (resG.graph->valid(v)) resG.graph->first(out, v);
6.883 + while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
6.884 }
6.885 - if (!resG.gw.valid(out)) {
6.886 + if (!resG.graph->valid(out)) {
6.887 out_or_in=0;
6.888 - resG.gw.first(v);
6.889 - if (resG.gw.valid(v)) resG.gw.first(in, v); else in=INVALID;
6.890 - while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
6.891 - while (resG.gw.valid(v) && !resG.gw.valid(in)) {
6.892 - resG.gw.next(v);
6.893 - if (resG.gw.valid(v)) resG.gw.first(in, v);
6.894 - while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
6.895 + resG.graph->first(v);
6.896 + if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;
6.897 + while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
6.898 + while (resG.graph->valid(v) && !resG.graph->valid(in)) {
6.899 + resG.graph->next(v);
6.900 + if (resG.graph->valid(v)) resG.graph->first(in, v);
6.901 + while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
6.902 }
6.903 }
6.904 }
6.905 @@ -1083,7 +973,7 @@
6.906 // if (!out.valid()) {
6.907 // out_or_in=0;
6.908 // G->first(v);
6.909 -// if (v.valid()) G->first(in, v); else in=OldInEdgeIt();
6.910 +// if (v.valid()) G->first(in, v); else in=GraphInEdgeIt();
6.911 // while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
6.912 // while (v.valid() && !in.valid()) {
6.913 // ++v;
6.914 @@ -1104,7 +994,7 @@
6.915 // }
6.916 };
6.917
6.918 - NodeIt& first(NodeIt& v) const { gw.first(v); return v; }
6.919 + NodeIt& first(NodeIt& v) const { graph->first(v); return v; }
6.920 OutEdgeIt& first(OutEdgeIt& e, Node v) const {
6.921 e=OutEdgeIt(*this, v);
6.922 return e;
6.923 @@ -1114,52 +1004,52 @@
6.924 return e;
6.925 }
6.926
6.927 - NodeIt& next(NodeIt& n) const { return gw.next(n); }
6.928 + NodeIt& next(NodeIt& n) const { return graph->next(n); }
6.929
6.930 OutEdgeIt& next(OutEdgeIt& e) const {
6.931 if (e.out_or_in) {
6.932 - Node v=gw.aNode(e.out);
6.933 - gw.next(e.out);
6.934 - while( gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
6.935 - if (!gw.valid(e.out)) {
6.936 + Node v=graph->aNode(e.out);
6.937 + graph->next(e.out);
6.938 + while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
6.939 + if (!graph->valid(e.out)) {
6.940 e.out_or_in=0;
6.941 - gw.first(e.in, v);
6.942 - while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
6.943 + graph->first(e.in, v);
6.944 + while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
6.945 }
6.946 } else {
6.947 - gw.next(e.in);
6.948 - while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
6.949 + graph->next(e.in);
6.950 + while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
6.951 }
6.952 return e;
6.953 }
6.954
6.955 EdgeIt& next(EdgeIt& e) const {
6.956 if (e.out_or_in) {
6.957 - gw.next(e.out);
6.958 - while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
6.959 - while (gw.valid(e.v) && !gw.valid(e.out)) {
6.960 - gw.next(e.v);
6.961 - if (gw.valid(e.v)) gw.first(e.out, e.v);
6.962 - while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
6.963 + graph->next(e.out);
6.964 + while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
6.965 + while (graph->valid(e.v) && !graph->valid(e.out)) {
6.966 + graph->next(e.v);
6.967 + if (graph->valid(e.v)) graph->first(e.out, e.v);
6.968 + while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
6.969 }
6.970 - if (!gw.valid(e.out)) {
6.971 + if (!graph->valid(e.out)) {
6.972 e.out_or_in=0;
6.973 - gw.first(e.v);
6.974 - if (gw.valid(e.v)) gw.first(e.in, e.v); else e.in=INVALID;
6.975 - while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
6.976 - while (gw.valid(e.v) && !gw.valid(e.in)) {
6.977 - gw.next(e.v);
6.978 - if (gw.valid(e.v)) gw.first(e.in, e.v);
6.979 - while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
6.980 + graph->first(e.v);
6.981 + if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;
6.982 + while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
6.983 + while (graph->valid(e.v) && !graph->valid(e.in)) {
6.984 + graph->next(e.v);
6.985 + if (graph->valid(e.v)) graph->first(e.in, e.v);
6.986 + while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
6.987 }
6.988 }
6.989 } else {
6.990 - gw.next(e.in);
6.991 - while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
6.992 - while (gw.valid(e.v) && !gw.valid(e.in)) {
6.993 - gw.next(e.v);
6.994 - if (gw.valid(e.v)) gw.first(e.in, e.v);
6.995 - while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
6.996 + graph->next(e.in);
6.997 + while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
6.998 + while (graph->valid(e.v) && !graph->valid(e.in)) {
6.999 + graph->next(e.v);
6.1000 + if (graph->valid(e.v)) graph->first(e.in, e.v);
6.1001 + while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
6.1002 }
6.1003 }
6.1004 return e;
6.1005 @@ -1181,54 +1071,60 @@
6.1006 }
6.1007
6.1008 Node tail(Edge e) const {
6.1009 - return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); }
6.1010 + return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
6.1011 Node head(Edge e) const {
6.1012 - return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }
6.1013 + return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
6.1014
6.1015 Node aNode(OutEdgeIt e) const {
6.1016 - return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); }
6.1017 + return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
6.1018 Node bNode(OutEdgeIt e) const {
6.1019 - return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }
6.1020 + return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
6.1021
6.1022 - int nodeNum() const { return gw.nodeNum(); }
6.1023 + int nodeNum() const { return graph->nodeNum(); }
6.1024 //FIXME
6.1025 - //int edgeNum() const { return gw.edgeNum(); }
6.1026 + //int edgeNum() const { return graph->edgeNum(); }
6.1027
6.1028
6.1029 - int id(Node v) const { return gw.id(v); }
6.1030 + int id(Node v) const { return graph->id(v); }
6.1031
6.1032 - bool valid(Node n) const { return gw.valid(n); }
6.1033 + bool valid(Node n) const { return graph->valid(n); }
6.1034 bool valid(Edge e) const {
6.1035 - return e.out_or_in ? gw.valid(e.out) : gw.valid(e.in); }
6.1036 + return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); }
6.1037
6.1038 void augment(const Edge& e, Number a) const {
6.1039 if (e.out_or_in)
6.1040 - flow->set(e.out, flow->get(e.out)+a);
6.1041 +// flow->set(e.out, flow->get(e.out)+a);
6.1042 + flow->set(e.out, (*flow)[e.out]+a);
6.1043 else
6.1044 - flow->set(e.in, flow->get(e.in)-a);
6.1045 +// flow->set(e.in, flow->get(e.in)-a);
6.1046 + flow->set(e.in, (*flow)[e.in]-a);
6.1047 }
6.1048
6.1049 Number resCap(const Edge& e) const {
6.1050 if (e.out_or_in)
6.1051 - return (capacity->get(e.out)-flow->get(e.out));
6.1052 +// return (capacity->get(e.out)-flow->get(e.out));
6.1053 + return ((*capacity)[e.out]-(*flow)[e.out]);
6.1054 else
6.1055 - return (flow->get(e.in));
6.1056 +// return (flow->get(e.in));
6.1057 + return ((*flow)[e.in]);
6.1058 }
6.1059
6.1060 - Number resCap(OldOutEdgeIt out) const {
6.1061 - return (capacity->get(out)-flow->get(out));
6.1062 + Number resCap(GraphOutEdgeIt out) const {
6.1063 +// return (capacity->get(out)-flow->get(out));
6.1064 + return ((*capacity)[out]-(*flow)[out]);
6.1065 }
6.1066
6.1067 - Number resCap(OldInEdgeIt in) const {
6.1068 - return (flow->get(in));
6.1069 + Number resCap(GraphInEdgeIt in) const {
6.1070 +// return (flow->get(in));
6.1071 + return ((*flow)[in]);
6.1072 }
6.1073
6.1074 -// template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
6.1075 +// template<typename T> class NodeMap : public Graph::NodeMap<T> {
6.1076 // public:
6.1077 -// NodeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G)
6.1078 -// : GraphWrapper::NodeMap<T>(_G.gw) { }
6.1079 -// NodeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G,
6.1080 -// T a) : GraphWrapper::NodeMap<T>(_G.gw, a) { }
6.1081 +// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
6.1082 +// : Graph::NodeMap<T>(_G.gw) { }
6.1083 +// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
6.1084 +// T a) : Graph::NodeMap<T>(_G.gw, a) { }
6.1085 // };
6.1086
6.1087 // template <typename T>
6.1088 @@ -1243,53 +1139,59 @@
6.1089
6.1090 template <typename T>
6.1091 class EdgeMap {
6.1092 - typename GraphWrapper::EdgeMap<T> forward_map, backward_map;
6.1093 + typename Graph::EdgeMap<T> forward_map, backward_map;
6.1094 public:
6.1095 - EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.gw), backward_map(_G.gw) { }
6.1096 - EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.gw, a), backward_map(_G.gw, a) { }
6.1097 + EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
6.1098 + EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
6.1099 void set(Edge e, T a) {
6.1100 if (e.out_or_in)
6.1101 forward_map.set(e.out, a);
6.1102 else
6.1103 backward_map.set(e.in, a);
6.1104 }
6.1105 - T get(Edge e) {
6.1106 + T operator[](Edge e) const {
6.1107 if (e.out_or_in)
6.1108 - return forward_map.get(e.out);
6.1109 + return forward_map[e.out];
6.1110 else
6.1111 - return backward_map.get(e.in);
6.1112 + return backward_map[e.in];
6.1113 }
6.1114 +// T get(Edge e) const {
6.1115 +// if (e.out_or_in)
6.1116 +// return forward_map.get(e.out);
6.1117 +// else
6.1118 +// return backward_map.get(e.in);
6.1119 +// }
6.1120 };
6.1121 };
6.1122
6.1123 - //Subgraph on the same node-set and partial edge-set
6.1124 - template<typename GraphWrapper, typename FirstOutEdgesMap>
6.1125 - class ErasingFirstGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
6.1126 + //ErasingFirstGraphWrapper for blocking flows
6.1127 + template<typename Graph, typename FirstOutEdgesMap>
6.1128 + class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
6.1129 protected:
6.1130 FirstOutEdgesMap* first_out_edges;
6.1131 public:
6.1132 - typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
6.1133 - typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
6.1134 - typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
6.1135 - typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt;
6.1136 - typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt;
6.1137 - typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt;
6.1138 + typedef typename GraphWrapper<Graph>::Node Node;
6.1139 + typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
6.1140 + typedef typename GraphWrapper<Graph>::Edge Edge;
6.1141 + typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
6.1142 + typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt;
6.1143 + typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt;
6.1144
6.1145 - ErasingFirstGraphWrapper(GraphWrapper _gw, FirstOutEdgesMap& _first_out_edges) :
6.1146 - GraphWrapperSkeleton<GraphWrapper>(_gw), first_out_edges(&_first_out_edges) { }
6.1147 + ErasingFirstGraphWrapper(Graph& _graph,
6.1148 + FirstOutEdgesMap& _first_out_edges) :
6.1149 + GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
6.1150
6.1151 template<typename I> I& first(I& i) const {
6.1152 - gw.first(i);
6.1153 - //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
6.1154 + graph->first(i);
6.1155 return i;
6.1156 }
6.1157 OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
6.1158 - e=first_out_edges->get(n);
6.1159 +// e=first_out_edges->get(n);
6.1160 + e=(*first_out_edges)[n];
6.1161 return e;
6.1162 }
6.1163 template<typename I, typename P> I& first(I& i, const P& p) const {
6.1164 - gw.first(i, p);
6.1165 - //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
6.1166 + graph->first(i, p);
6.1167 return i;
6.1168 }
6.1169
6.1170 @@ -1297,8 +1199,7 @@
6.1171 // return gw.getNext(i);
6.1172 //}
6.1173 template<typename I> I& next(I &i) const {
6.1174 - gw.next(i);
6.1175 - //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
6.1176 + graph->next(i);
6.1177 return i;
6.1178 }
6.1179
6.1180 @@ -1315,246 +1216,6 @@
6.1181 }
6.1182 };
6.1183
6.1184 -// template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
6.1185 -// class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
6.1186 -// protected:
6.1187 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
6.1188 -// //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
6.1189 -// public:
6.1190 -// ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow,
6.1191 -// const CapacityMap& _capacity) :
6.1192 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),
6.1193 -// first_out_edges(*this) /*, dist(*this)*/ {
6.1194 -// for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) {
6.1195 -// OutEdgeIt e;
6.1196 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
6.1197 -// first_out_edges.set(n, e);
6.1198 -// }
6.1199 -// }
6.1200 -
6.1201 -// //void setGraph(Graph& _graph) { graph = &_graph; }
6.1202 -// //Graph& getGraph() const { return (*graph); }
6.1203 -
6.1204 -// //TrivGraphWrapper() : graph(0) { }
6.1205 -// //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }
6.1206 -
6.1207 -// //typedef Graph BaseGraph;
6.1208 -
6.1209 -// //typedef typename Graph::Node Node;
6.1210 -// //typedef typename Graph::NodeIt NodeIt;
6.1211 -
6.1212 -// //typedef typename Graph::Edge Edge;
6.1213 -// //typedef typename Graph::OutEdgeIt OutEdgeIt;
6.1214 -// //typedef typename Graph::InEdgeIt InEdgeIt;
6.1215 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
6.1216 -// //typedef typename Graph::EdgeIt EdgeIt;
6.1217 -
6.1218 -// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
6.1219 -// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
6.1220 -
6.1221 -// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
6.1222 -// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
6.1223 -// //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
6.1224 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
6.1225 -// //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
6.1226 -
6.1227 -// NodeIt& first(NodeIt& n) const {
6.1228 -// return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
6.1229 -// }
6.1230 -
6.1231 -// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
6.1232 -// e=first_out_edges.get(n);
6.1233 -// return e;
6.1234 -// }
6.1235 -
6.1236 -// //ROSSZ template<typename I> I& first(I& i) const { return first(i); }
6.1237 -// //ROSSZ template<typename I, typename P> I& first(I& i, const P& p) const {
6.1238 -// // return first(i, p); }
6.1239 -
6.1240 -// //template<typename I> I getNext(const I& i) const {
6.1241 -// // return gw.getNext(i); }
6.1242 -// //template<typename I> I& next(I &i) const { return gw.next(i); }
6.1243 -
6.1244 -// template< typename It > It first() const {
6.1245 -// It e; first(e); return e; }
6.1246 -
6.1247 -// template< typename It > It first(const Node& v) const {
6.1248 -// It e; first(e, v); return e; }
6.1249 -
6.1250 -// //Node head(const Edge& e) const { return gw.head(e); }
6.1251 -// //Node tail(const Edge& e) const { return gw.tail(e); }
6.1252 -
6.1253 -// //template<typename I> bool valid(const I& i) const
6.1254 -// // { return gw.valid(i); }
6.1255 -
6.1256 -// //int nodeNum() const { return gw.nodeNum(); }
6.1257 -// //int edgeNum() const { return gw.edgeNum(); }
6.1258 -
6.1259 -// //template<typename I> Node aNode(const I& e) const {
6.1260 -// // return gw.aNode(e); }
6.1261 -// //template<typename I> Node bNode(const I& e) const {
6.1262 -// // return gw.bNode(e); }
6.1263 -
6.1264 -// //Node addNode() const { return gw.addNode(); }
6.1265 -// //Edge addEdge(const Node& tail, const Node& head) const {
6.1266 -// // return gw.addEdge(tail, head); }
6.1267 -
6.1268 -// //void erase(const OutEdgeIt& e) {
6.1269 -// // first_out_edge(this->tail(e))=e;
6.1270 -// //}
6.1271 -// void erase(const Edge& e) {
6.1272 -// OutEdgeIt f(e);
6.1273 -// next(f);
6.1274 -// first_out_edges.set(this->tail(e), f);
6.1275 -// }
6.1276 -// //template<typename I> void erase(const I& i) const { gw.erase(i); }
6.1277 -
6.1278 -// //void clear() const { gw.clear(); }
6.1279 -
6.1280 -// template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
6.1281 -// public:
6.1282 -// NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
6.1283 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
6.1284 -// NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
6.1285 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
6.1286 -// };
6.1287 -
6.1288 -// template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
6.1289 -// public:
6.1290 -// EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
6.1291 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
6.1292 -// EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
6.1293 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
6.1294 -// };
6.1295 -// };
6.1296 -
6.1297 -// template<typename GraphWrapper>
6.1298 -// class FilterGraphWrapper {
6.1299 -// };
6.1300 -
6.1301 -// template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
6.1302 -// class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
6.1303 -
6.1304 -// //Graph* graph;
6.1305 -
6.1306 -// public:
6.1307 -// //typedef Graph BaseGraph;
6.1308 -
6.1309 -// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
6.1310 -// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
6.1311 -
6.1312 -// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
6.1313 -// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
6.1314 -// //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
6.1315 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
6.1316 -// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
6.1317 -
6.1318 -// //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
6.1319 -
6.1320 -// public:
6.1321 -// FilterGraphWrapper(const Graph& _G, FlowMap& _flow,
6.1322 -// const CapacityMap& _capacity) :
6.1323 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this, gw.nodeNum()) {
6.1324 -// }
6.1325 -
6.1326 -// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
6.1327 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
6.1328 -// while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e))))
6.1329 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
6.1330 -// return e;
6.1331 -// }
6.1332 -
6.1333 -// NodeIt& next(NodeIt& e) const {
6.1334 -// return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
6.1335 -// }
6.1336 -
6.1337 -// OutEdgeIt& next(OutEdgeIt& e) const {
6.1338 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
6.1339 -// while (valid(e) && (dist.get(tail(e))/*+1!*/>=dist.get(head(e))))
6.1340 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
6.1341 -// return e;
6.1342 -// }
6.1343 -
6.1344 -// NodeIt& first(NodeIt& n) const {
6.1345 -// return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
6.1346 -// }
6.1347 -
6.1348 -// void erase(const Edge& e) {
6.1349 -// OutEdgeIt f(e);
6.1350 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
6.1351 -// while (valid(f) && (dist.get(tail(f))/*+1!=*/>=dist.get(head(f))))
6.1352 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
6.1353 -// first_out_edges.set(this->tail(e), f);
6.1354 -// }
6.1355 -
6.1356 -// //TrivGraphWrapper() : graph(0) { }
6.1357 -// //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
6.1358 -
6.1359 -// //void setGraph(Graph& _graph) { graph = &_graph; }
6.1360 -// //Graph& getGraph() const { return (*graph); }
6.1361 -
6.1362 -// //template<typename I> I& first(I& i) const { return gw.first(i); }
6.1363 -// //template<typename I, typename P> I& first(I& i, const P& p) const {
6.1364 -// // return gw.first(i, p); }
6.1365 -
6.1366 -// //template<typename I> I getNext(const I& i) const {
6.1367 -// // return gw.getNext(i); }
6.1368 -// //template<typename I> I& next(I &i) const { return gw.next(i); }
6.1369 -
6.1370 -// template< typename It > It first() const {
6.1371 -// It e; first(e); return e; }
6.1372 -
6.1373 -// template< typename It > It first(const Node& v) const {
6.1374 -// It e; first(e, v); return e; }
6.1375 -
6.1376 -// //Node head(const Edge& e) const { return gw.head(e); }
6.1377 -// //Node tail(const Edge& e) const { return gw.tail(e); }
6.1378 -
6.1379 -// //template<typename I> bool valid(const I& i) const
6.1380 -// // { return gw.valid(i); }
6.1381 -
6.1382 -// //template<typename I> void setInvalid(const I &i);
6.1383 -// //{ return gw.setInvalid(i); }
6.1384 -
6.1385 -// //int nodeNum() const { return gw.nodeNum(); }
6.1386 -// //int edgeNum() const { return gw.edgeNum(); }
6.1387 -
6.1388 -// //template<typename I> Node aNode(const I& e) const {
6.1389 -// // return gw.aNode(e); }
6.1390 -// //template<typename I> Node bNode(const I& e) const {
6.1391 -// // return gw.bNode(e); }
6.1392 -
6.1393 -// //Node addNode() const { return gw.addNode(); }
6.1394 -// //Edge addEdge(const Node& tail, const Node& head) const {
6.1395 -// // return gw.addEdge(tail, head); }
6.1396 -
6.1397 -// //template<typename I> void erase(const I& i) const { gw.erase(i); }
6.1398 -
6.1399 -// //void clear() const { gw.clear(); }
6.1400 -
6.1401 -// template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
6.1402 -// public:
6.1403 -// NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
6.1404 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
6.1405 -// NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
6.1406 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
6.1407 -// };
6.1408 -
6.1409 -// template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
6.1410 -// public:
6.1411 -// EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
6.1412 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
6.1413 -// EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
6.1414 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
6.1415 -// };
6.1416 -
6.1417 -// public:
6.1418 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
6.1419 -
6.1420 -// };
6.1421 -
6.1422 -
6.1423 -
6.1424 // // FIXME: comparison should be made better!!!
6.1425 // template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
6.1426 // class ResGraphWrapper
6.1427 @@ -1562,7 +1223,7 @@
6.1428 // Graph* graph;
6.1429
6.1430 // public:
6.1431 -// typedef Graph BaseGraph;
6.1432 +// typedef Graph ParentGraph;
6.1433
6.1434 // typedef typename Graph::Node Node;
6.1435 // typedef typename Graph::Edge Edge;
7.1 --- a/src/work/marci/makefile Mon Apr 05 15:31:21 2004 +0000
7.2 +++ b/src/work/marci/makefile Mon Apr 05 16:52:46 2004 +0000
7.3 @@ -2,6 +2,8 @@
7.4 CXX2 = g++-2.95
7.5 #CXX3.3 = g++
7.6 CXX3 := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
7.7 +CXX=$(CXX3)
7.8 +CC=$(CXX)
7.9 #CXXFLAGS = -W -Wall -ansi -pedantic -I. -I.. -I../alpar
7.10 #LEDAROOT ?= /ledasrc/LEDA-4.1
7.11 BOOSTROOT ?= /home/marci/boost
7.12 @@ -10,13 +12,13 @@
7.13 CXXFLAGS = -g -O -W -Wall $(INCLUDEDIRS) -ansi -pedantic
7.14
7.15 LEDABINARIES = lg_vs_sg leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
7.16 -BINARIES = edmonds_karp_demo gw_vs_not
7.17 -#preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
7.18 +BINARIES = edmonds_karp_demo iterator_bfs_demo
7.19 +#gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
7.20
7.21 all: $(BINARIES)
7.22
7.23 .depend dep depend:
7.24 - -g++ $(INCLUDEDIRS) -M $(BINARIES:=.cc) > .depend #2>/dev/null
7.25 + -$(CXX) $(INCLUDEDIRS) -M $(BINARIES:=.cc) > .depend #2>/dev/null
7.26 # -g++ $(INCLUDEDIRS) $(LEDAINCLUDE) -M $(LEDABINARIES:=.cc) >> .depend #2>/dev/null
7.27
7.28