1.1 --- a/src/hugo/graph_wrapper.h Mon Aug 30 12:01:47 2004 +0000
1.2 +++ b/src/hugo/graph_wrapper.h Tue Aug 31 11:26:59 2004 +0000
1.3 @@ -347,6 +347,8 @@
1.4
1.5 };
1.6
1.7 +
1.8 +
1.9 /// A graph wrapper for hiding nodes and edges from a graph.
1.10
1.11 /// This wrapper shows a graph with filtered node-set and
1.12 @@ -380,69 +382,109 @@
1.13 edge_filter_map(&_edge_filter_map) { }
1.14
1.15 typedef typename GraphWrapper<Graph>::Node Node;
1.16 - class NodeIt {
1.17 - friend class GraphWrapper<Graph>;
1.18 +// class NodeIt {
1.19 +// friend class GraphWrapper<Graph>;
1.20 +// friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.21 +// typename Graph::NodeIt n;
1.22 +// public:
1.23 +// NodeIt() { }
1.24 +// NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
1.25 +// NodeIt(const Invalid& i) : n(i) { }
1.26 +// NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
1.27 +// n(*(_G.graph)) {
1.28 +// while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
1.29 +// _G.graph->next(n);
1.30 +// }
1.31 +// operator Node() const { return Node(typename Graph::Node(n)); }
1.32 +// };
1.33 + class NodeIt : public Node {
1.34 + const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
1.35 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.36 - typename Graph::NodeIt n;
1.37 - public:
1.38 + public:
1.39 NodeIt() { }
1.40 - NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
1.41 - NodeIt(const Invalid& i) : n(i) { }
1.42 - NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
1.43 - n(*(_G.graph)) {
1.44 - while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
1.45 - _G.graph->next(n);
1.46 + // NodeIt(const NodeIt& n) : Node(n), gw(n.gw) { }
1.47 + NodeIt(Invalid i) : Node(i) { }
1.48 + NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
1.49 + Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { }
1.50 + NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
1.51 + const Node& n) :
1.52 + Node(n), gw(&_gw) { }
1.53 + NodeIt& operator++() {
1.54 + *(static_cast<Node*>(this))=
1.55 + ++(typename Graph::NodeIt(*(gw->graph), *this));
1.56 + while (*static_cast<Node*>(this)!=INVALID &&
1.57 + !(*(gw->node_filter_map))[*this])
1.58 + *(static_cast<Node*>(this))=
1.59 + ++(typename Graph::NodeIt(*(gw->graph), *this));
1.60 + return *this;
1.61 }
1.62 - operator Node() const { return Node(typename Graph::Node(n)); }
1.63 };
1.64 typedef typename GraphWrapper<Graph>::Edge Edge;
1.65 - class OutEdgeIt {
1.66 - friend class GraphWrapper<Graph>;
1.67 + class OutEdgeIt : public Edge {
1.68 + const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
1.69 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.70 - typename Graph::OutEdgeIt e;
1.71 public:
1.72 OutEdgeIt() { }
1.73 - OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
1.74 - OutEdgeIt(const Invalid& i) : e(i) { }
1.75 - OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
1.76 - const Node& _n) :
1.77 - e(*(_G.graph), typename Graph::Node(_n)) {
1.78 - while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
1.79 - _G.graph->next(e);
1.80 + // OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
1.81 + OutEdgeIt(Invalid i) : Edge(i) { }
1.82 + OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
1.83 + Edge(typename Graph::OutEdgeIt(*(_gw.graph)), n), gw(&_gw) { }
1.84 + OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
1.85 + const Edge& e) :
1.86 + Edge(e), gw(&_gw) { }
1.87 + OutEdgeIt& operator++() {
1.88 + *(static_cast<Edge*>(this))=
1.89 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1.90 + while (*static_cast<Edge*>(this)!=INVALID &&
1.91 + !(*(gw->edge_filter_map))[*this])
1.92 + *(static_cast<Edge*>(this))=
1.93 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1.94 + return *this;
1.95 }
1.96 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.97 };
1.98 - class InEdgeIt {
1.99 - friend class GraphWrapper<Graph>;
1.100 + class InEdgeIt : public Edge {
1.101 + const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
1.102 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.103 - typename Graph::InEdgeIt e;
1.104 public:
1.105 InEdgeIt() { }
1.106 - InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1.107 - InEdgeIt(const Invalid& i) : e(i) { }
1.108 - InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
1.109 - const Node& _n) :
1.110 - e(*(_G.graph), typename Graph::Node(_n)) {
1.111 - while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
1.112 - _G.graph->next(e);
1.113 + // InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
1.114 + InEdgeIt(Invalid i) : Edge(i) { }
1.115 + InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
1.116 + Edge(typename Graph::InEdgeIt(*(_gw.graph)), n), gw(&_gw) { }
1.117 + InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
1.118 + const Edge& e) :
1.119 + Edge(e), gw(&_gw) { }
1.120 + InEdgeIt& operator++() {
1.121 + *(static_cast<Edge*>(this))=
1.122 + ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1.123 + while (*static_cast<Edge*>(this)!=INVALID &&
1.124 + !(*(gw->edge_filter_map))[*this])
1.125 + *(static_cast<Edge*>(this))=
1.126 + ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1.127 + return *this;
1.128 }
1.129 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.130 };
1.131 - //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.132 - class EdgeIt {
1.133 - friend class GraphWrapper<Graph>;
1.134 + class EdgeIt : public Edge {
1.135 + const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
1.136 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
1.137 - typename Graph::EdgeIt e;
1.138 public:
1.139 EdgeIt() { }
1.140 - EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
1.141 - EdgeIt(const Invalid& i) : e(i) { }
1.142 - EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
1.143 - e(*(_G.graph)) {
1.144 - while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
1.145 - _G.graph->next(e);
1.146 + // EdgeIt(const EdgeIt& e) : Edge(e), gw(e.gw) { }
1.147 + EdgeIt(Invalid i) : Edge(i) { }
1.148 + EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
1.149 + Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { }
1.150 + EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
1.151 + const Edge& e) :
1.152 + Edge(e), gw(&_gw) { }
1.153 + EdgeIt& operator++() {
1.154 + *(static_cast<Edge*>(this))=
1.155 + ++(typename Graph::EdgeIt(*(gw->graph), *this));
1.156 + while (*static_cast<Edge*>(this)!=INVALID &&
1.157 + !(*(gw->edge_filter_map))[*this])
1.158 + *(static_cast<Edge*>(this))=
1.159 + ++(typename Graph::EdgeIt(*(gw->graph), *this));
1.160 + return *this;
1.161 }
1.162 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
1.163 };
1.164
1.165 NodeIt& first(NodeIt& i) const {
1.166 @@ -458,39 +500,39 @@
1.167 i=EdgeIt(*this); return i;
1.168 }
1.169
1.170 - NodeIt& next(NodeIt& i) const {
1.171 - this->graph->next(i.n);
1.172 - while (this->graph->valid(i) && !(*node_filter_map)[i.n]) {
1.173 - this->graph->next(i.n); }
1.174 - return i;
1.175 - }
1.176 - OutEdgeIt& next(OutEdgeIt& i) const {
1.177 - this->graph->next(i.e);
1.178 - while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
1.179 - this->graph->next(i.e); }
1.180 - return i;
1.181 - }
1.182 - InEdgeIt& next(InEdgeIt& i) const {
1.183 - this->graph->next(i.e);
1.184 - while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
1.185 - this->graph->next(i.e); }
1.186 - return i;
1.187 - }
1.188 - EdgeIt& next(EdgeIt& i) const {
1.189 - this->graph->next(i.e);
1.190 - while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
1.191 - this->graph->next(i.e); }
1.192 - return i;
1.193 - }
1.194 +// NodeIt& next(NodeIt& i) const {
1.195 +// this->graph->next(i.n);
1.196 +// while (this->graph->valid(i) && !(*node_filter_map)[i.n]) {
1.197 +// this->graph->next(i.n); }
1.198 +// return i;
1.199 +// }
1.200 +// OutEdgeIt& next(OutEdgeIt& i) const {
1.201 +// this->graph->next(i.e);
1.202 +// while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
1.203 +// this->graph->next(i.e); }
1.204 +// return i;
1.205 +// }
1.206 +// InEdgeIt& next(InEdgeIt& i) const {
1.207 +// this->graph->next(i.e);
1.208 +// while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
1.209 +// this->graph->next(i.e); }
1.210 +// return i;
1.211 +// }
1.212 +// EdgeIt& next(EdgeIt& i) const {
1.213 +// this->graph->next(i.e);
1.214 +// while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
1.215 +// this->graph->next(i.e); }
1.216 +// return i;
1.217 +// }
1.218
1.219 - Node aNode(const OutEdgeIt& e) const {
1.220 - return Node(this->graph->aNode(e.e)); }
1.221 - Node aNode(const InEdgeIt& e) const {
1.222 - return Node(this->graph->aNode(e.e)); }
1.223 - Node bNode(const OutEdgeIt& e) const {
1.224 - return Node(this->graph->bNode(e.e)); }
1.225 - Node bNode(const InEdgeIt& e) const {
1.226 - return Node(this->graph->bNode(e.e)); }
1.227 +// Node aNode(const OutEdgeIt& e) const {
1.228 +// return Node(this->graph->aNode(e.e)); }
1.229 +// Node aNode(const InEdgeIt& e) const {
1.230 +// return Node(this->graph->aNode(e.e)); }
1.231 +// Node bNode(const OutEdgeIt& e) const {
1.232 +// return Node(this->graph->bNode(e.e)); }
1.233 +// Node bNode(const InEdgeIt& e) const {
1.234 +// return Node(this->graph->bNode(e.e)); }
1.235
1.236 /// This function hides \c n in the graph, i.e. the iteration
1.237 /// jumps over it. This is done by simply setting the value of \c n
1.238 @@ -753,13 +795,14 @@
1.239 !(*(gw->forward_filter))[*this])
1.240 *(static_cast<GraphEdge*>(this))=
1.241 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1.242 - if (*static_cast<GraphEdge*>(this)==INVALID)
1.243 + if (*static_cast<GraphEdge*>(this)==INVALID) {
1.244 *static_cast<Edge*>(this)=
1.245 Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true);
1.246 - while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.247 - !(*(gw->backward_filter))[*this])
1.248 - *(static_cast<GraphEdge*>(this))=
1.249 - ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1.250 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.251 + !(*(gw->backward_filter))[*this])
1.252 + *(static_cast<GraphEdge*>(this))=
1.253 + ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1.254 + }
1.255 }
1.256 OutEdgeIt(const SubBidirGraphWrapper<Graph,
1.257 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
1.258 @@ -773,13 +816,14 @@
1.259 !(*(gw->forward_filter))[*this])
1.260 *(static_cast<GraphEdge*>(this))=
1.261 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1.262 - if (*static_cast<GraphEdge*>(this)==INVALID)
1.263 + if (*static_cast<GraphEdge*>(this)==INVALID) {
1.264 *static_cast<Edge*>(this)=
1.265 Edge(typename Graph::InEdgeIt(*(gw->graph), n), true);
1.266 - while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.267 - !(*(gw->backward_filter))[*this])
1.268 - *(static_cast<GraphEdge*>(this))=
1.269 - ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1.270 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.271 + !(*(gw->backward_filter))[*this])
1.272 + *(static_cast<GraphEdge*>(this))=
1.273 + ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1.274 + }
1.275 } else {
1.276 *(static_cast<GraphEdge*>(this))=
1.277 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1.278 @@ -809,33 +853,35 @@
1.279 !(*(gw->forward_filter))[*this])
1.280 *(static_cast<GraphEdge*>(this))=
1.281 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1.282 - if (*static_cast<GraphEdge*>(this)==INVALID)
1.283 + if (*static_cast<GraphEdge*>(this)==INVALID) {
1.284 *static_cast<Edge*>(this)=
1.285 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true);
1.286 - while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.287 - !(*(gw->backward_filter))[*this])
1.288 - *(static_cast<GraphEdge*>(this))=
1.289 - ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1.290 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.291 + !(*(gw->backward_filter))[*this])
1.292 + *(static_cast<GraphEdge*>(this))=
1.293 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1.294 + }
1.295 }
1.296 InEdgeIt(const SubBidirGraphWrapper<Graph,
1.297 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
1.298 Edge(e), gw(&_gw) { }
1.299 InEdgeIt& operator++() {
1.300 if (!this->backward) {
1.301 - Node n=gw->head(*this);
1.302 + Node n=gw->tail(*this);
1.303 *(static_cast<GraphEdge*>(this))=
1.304 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1.305 while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.306 !(*(gw->forward_filter))[*this])
1.307 *(static_cast<GraphEdge*>(this))=
1.308 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
1.309 - if (*static_cast<GraphEdge*>(this)==INVALID)
1.310 + if (*static_cast<GraphEdge*>(this)==INVALID) {
1.311 *static_cast<Edge*>(this)=
1.312 Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true);
1.313 - while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.314 - !(*(gw->backward_filter))[*this])
1.315 - *(static_cast<GraphEdge*>(this))=
1.316 - ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1.317 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.318 + !(*(gw->backward_filter))[*this])
1.319 + *(static_cast<GraphEdge*>(this))=
1.320 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1.321 + }
1.322 } else {
1.323 *(static_cast<GraphEdge*>(this))=
1.324 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1.325 @@ -859,19 +905,20 @@
1.326 EdgeIt(Invalid i) : Edge(i) { }
1.327 //the unique invalid iterator
1.328 EdgeIt(const SubBidirGraphWrapper<Graph,
1.329 - ForwardFilterMap, BackwardFilterMap>& _gw) :
1.330 - Edge(typename Graph::EdgeIt(*(_gw.graph)), false), gw(&_gw) {
1.331 + ForwardFilterMap, BackwardFilterMap>& _gw) :
1.332 + Edge(typename Graph::OutEdgeIt(*(_gw.graph)), false), gw(&_gw) {
1.333 while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.334 !(*(gw->forward_filter))[*this])
1.335 *(static_cast<GraphEdge*>(this))=
1.336 ++(typename Graph::EdgeIt(*(gw->graph), *this));
1.337 - if (*static_cast<GraphEdge*>(this)==INVALID)
1.338 + if (*static_cast<GraphEdge*>(this)==INVALID) {
1.339 *static_cast<Edge*>(this)=
1.340 Edge(typename Graph::EdgeIt(*(_gw.graph)), true);
1.341 - while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.342 - !(*(gw->backward_filter))[*this])
1.343 - *(static_cast<GraphEdge*>(this))=
1.344 - ++(typename Graph::EdgeIt(*(gw->graph), *this));
1.345 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.346 + !(*(gw->backward_filter))[*this])
1.347 + *(static_cast<GraphEdge*>(this))=
1.348 + ++(typename Graph::EdgeIt(*(gw->graph), *this));
1.349 + }
1.350 }
1.351 EdgeIt(const SubBidirGraphWrapper<Graph,
1.352 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
1.353 @@ -884,13 +931,14 @@
1.354 !(*(gw->forward_filter))[*this])
1.355 *(static_cast<GraphEdge*>(this))=
1.356 ++(typename Graph::EdgeIt(*(gw->graph), *this));
1.357 - if (*static_cast<GraphEdge*>(this)==INVALID)
1.358 + if (*static_cast<GraphEdge*>(this)==INVALID) {
1.359 *static_cast<Edge*>(this)=
1.360 Edge(typename Graph::EdgeIt(*(gw->graph)), true);
1.361 - while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.362 - !(*(gw->backward_filter))[*this])
1.363 - *(static_cast<GraphEdge*>(this))=
1.364 - ++(typename Graph::EdgeIt(*(gw->graph), *this));
1.365 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
1.366 + !(*(gw->backward_filter))[*this])
1.367 + *(static_cast<GraphEdge*>(this))=
1.368 + ++(typename Graph::EdgeIt(*(gw->graph), *this));
1.369 + }
1.370 } else {
1.371 *(static_cast<GraphEdge*>(this))=
1.372 ++(typename Graph::EdgeIt(*(gw->graph), *this));
2.1 --- a/src/work/marci/augmenting_flow.h Mon Aug 30 12:01:47 2004 +0000
2.2 +++ b/src/work/marci/augmenting_flow.h Tue Aug 31 11:26:59 2004 +0000
2.3 @@ -1020,7 +1020,7 @@
2.4 break;
2.5 case AFTER_AUGMENTING:
2.6 // std::cout << "AFTER_AUGMENTING" << std::endl;
2.7 - for(g->first(v); g->valid(v); g->next(v)) {
2.8 + for(g->first(v); v!=INVALID; ++v) {
2.9 if (level[v]) {
2.10 M.set(v, true);
2.11 } else {
2.12 @@ -1030,7 +1030,7 @@
2.13 break;
2.14 case AFTER_FAST_AUGMENTING:
2.15 // std::cout << "AFTER_FAST_AUGMENTING" << std::endl;
2.16 - for(g->first(v); g->valid(v); g->next(v)) {
2.17 + for(g->first(v); v!=INVALID; ++v) {
2.18 if (level[v]==number_of_augmentations) {
2.19 M.set(v, true);
2.20 } else {
2.21 @@ -1053,7 +1053,7 @@
2.22 queue.pop();
2.23
2.24 OutEdgeIt e;
2.25 - for(g->first(e,w) ; g->valid(e); g->next(e)) {
2.26 + for(g->first(e,w) ; e!=INVALID; ++e) {
2.27 Node v=g->head(e);
2.28 if (!M[v] && (*flow)[e] < (*capacity)[e] ) {
2.29 queue.push(v);
2.30 @@ -1062,7 +1062,7 @@
2.31 }
2.32
2.33 InEdgeIt f;
2.34 - for(g->first(f,w) ; g->valid(f); g->next(f)) {
2.35 + for(g->first(f,w) ; f!=INVALID; ++f) {
2.36 Node v=g->tail(f);
2.37 if (!M[v] && (*flow)[f] > 0 ) {
2.38 queue.push(v);
2.39 @@ -1133,11 +1133,11 @@
2.40 //searching for augmenting path
2.41 while ( !bfs.finished() ) {
2.42 ResGWOutEdgeIt e=bfs;
2.43 - if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
2.44 + if (e!=INVALID && bfs.isBNodeNewlyReached()) {
2.45 Node v=res_graph.tail(e);
2.46 Node w=res_graph.head(e);
2.47 pred.set(w, e);
2.48 - if (res_graph.valid(pred[v])) {
2.49 + if (pred[v]!=INVALID) {
2.50 free.set(w, std::min(free[v], res_graph.resCap(e)));
2.51 } else {
2.52 free.set(w, res_graph.resCap(e));
2.53 @@ -1151,7 +1151,7 @@
2.54 if (_augment) {
2.55 Node n=t;
2.56 Num augment_value=free[t];
2.57 - while (res_graph.valid(pred[n])) {
2.58 + while (pred[n]!=INVALID) {
2.59 ResGWEdge e=pred[n];
2.60 res_graph.augment(e, augment_value);
2.61 n=res_graph.tail(e);
2.62 @@ -1190,11 +1190,11 @@
2.63 //searching for augmenting path
2.64 while ( !bfs.finished() ) {
2.65 ResGWOutEdgeIt e=bfs;
2.66 - if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
2.67 + if (e!=INVALID && bfs.isBNodeNewlyReached()) {
2.68 Node v=res_graph.tail(e);
2.69 Node w=res_graph.head(e);
2.70 pred.set(w, e);
2.71 - if (res_graph.valid(pred[v])) {
2.72 + if (pred[v]!=INVALID) {
2.73 free.set(w, std::min(free[v], res_graph.resCap(e)));
2.74 } else {
2.75 free.set(w, res_graph.resCap(e));
2.76 @@ -1208,7 +1208,7 @@
2.77 if (_augment) {
2.78 Node n=t;
2.79 Num augment_value=free[t];
2.80 - while (res_graph.valid(pred[n])) {
2.81 + while (pred[n]!=INVALID) {
2.82 ResGWEdge e=pred[n];
2.83 res_graph.augment(e, augment_value);
2.84 n=res_graph.tail(e);
2.85 @@ -1244,7 +1244,7 @@
2.86 res_graph_to_F(res_graph);
2.87 {
2.88 typename ResGW::NodeIt n;
2.89 - for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {
2.90 + for(res_graph.first(n); n!=INVALID; ++n) {
2.91 res_graph_to_F.set(n, F.addNode());
2.92 }
2.93 }
2.94 @@ -1256,7 +1256,7 @@
2.95
2.96 while ( !bfs.finished() ) {
2.97 ResGWOutEdgeIt e=bfs;
2.98 - if (res_graph.valid(e)) {
2.99 + if (e!=INVALID) {
2.100 if (bfs.isBNodeNewlyReached()) {
2.101 dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
2.102 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)],
2.103 @@ -1299,7 +1299,7 @@
2.104 typename MG::Node v=F.aNode(dfs);
2.105 typename MG::Node w=F.bNode(dfs);
2.106 pred.set(w, dfs);
2.107 - if (F.valid(pred[v])) {
2.108 + if (pred[v]!=INVALID) {
2.109 free.set(w, std::min(free[v], residual_capacity[dfs]));
2.110 } else {
2.111 free.set(w, residual_capacity[dfs]);
2.112 @@ -1319,7 +1319,7 @@
2.113 if (__augment) {
2.114 typename MG::Node n=tF;
2.115 Num augment_value=free[tF];
2.116 - while (F.valid(pred[n])) {
2.117 + while (pred[n]!=INVALID) {
2.118 typename MG::Edge e=pred[n];
2.119 res_graph.augment(original_edge[e], augment_value);
2.120 n=F.tail(e);
2.121 @@ -1337,8 +1337,6 @@
2.122 }
2.123
2.124
2.125 -
2.126 -
2.127 template <typename Graph, typename Num, typename CapMap, typename FlowMap>
2.128 bool AugmentingFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2()
2.129 {
2.130 @@ -1354,7 +1352,7 @@
2.131 DistanceMap<ResGW> dist(res_graph);
2.132 while ( !bfs.finished() ) {
2.133 ResGWOutEdgeIt e=bfs;
2.134 - if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
2.135 + if (e!=INVALID && bfs.isBNodeNewlyReached()) {
2.136 dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
2.137 }
2.138 ++bfs;
2.139 @@ -1371,8 +1369,7 @@
2.140 typename FilterResGW::template NodeMap<typename FilterResGW::OutEdgeIt>
2.141 first_out_edges(filter_res_graph);
2.142 typename FilterResGW::NodeIt v;
2.143 - for(filter_res_graph.first(v); filter_res_graph.valid(v);
2.144 - filter_res_graph.next(v))
2.145 + for(filter_res_graph.first(v); v!=INVALID; ++v)
2.146 {
2.147 typename FilterResGW::OutEdgeIt e;
2.148 filter_res_graph.first(e, v);
2.149 @@ -1418,7 +1415,7 @@
2.150 typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);
2.151
2.152 pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
2.153 - if (erasing_res_graph.valid(pred[v])) {
2.154 + if (pred[v]!=INVALID) {
2.155 free1.set
2.156 (w, std::min(free1[v], res_graph.resCap
2.157 (typename ErasingResGW::OutEdgeIt(dfs))));
3.1 --- a/src/work/marci/makefile Mon Aug 30 12:01:47 2004 +0000
3.2 +++ b/src/work/marci/makefile Tue Aug 31 11:26:59 2004 +0000
3.3 @@ -4,7 +4,7 @@
3.4 INCLUDEDIRS ?= -I../{jacint,marci,alpar,klao,akos,athos} -I../.. -I.. -I$(BOOSTROOT)
3.5
3.6 LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
3.7 -BINARIES = graph_wrapper_time max_flow_demo iterator_bfs_demo macro_test lg_vs_sg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_demo top_sort_test max_flow_1 proba7
3.8 +BINARIES = graph_wrapper_time max_flow_demo iterator_bfs_demo macro_test lg_vs_sg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_demo top_sort_test max_flow_1 proba7 proba8
3.9 #BINARIES = preflow_bug
3.10 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
3.11
4.1 --- a/src/work/marci/max_flow_demo.cc Mon Aug 30 12:01:47 2004 +0000
4.2 +++ b/src/work/marci/max_flow_demo.cc Tue Aug 31 11:26:59 2004 +0000
4.3 @@ -16,23 +16,7 @@
4.4 using namespace hugo;
4.5
4.6 // Use a DIMACS max flow file as stdin.
4.7 -// read_dimacs_demo < dimacs_max_flow_file
4.8 -
4.9 -
4.10 -// struct Ize {
4.11 -// };
4.12 -
4.13 -// struct Mize {
4.14 -// Ize bumm;
4.15 -// };
4.16 -
4.17 -// template <typename B>
4.18 -// class Huha {
4.19 -// public:
4.20 -// int u;
4.21 -// B brr;
4.22 -// };
4.23 -
4.24 +// max_flow_demo < dimacs_max_flow_file
4.25
4.26 int main(int, char **) {
4.27
4.28 @@ -44,28 +28,6 @@
4.29 typedef Graph::Node Node;
4.30 typedef Graph::EdgeIt EdgeIt;
4.31
4.32 -
4.33 -// Mize mize[10];
4.34 -// Mize bize[0];
4.35 -// Mize zize;
4.36 -// typedef Mize Tize[0];
4.37 -
4.38 -// std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
4.39 -// std::cout << sizeof(bize) << std::endl;
4.40 -
4.41 -
4.42 -// Huha<Tize> k;
4.43 -// std::cout << sizeof(k) << std::endl;
4.44 -
4.45 -
4.46 -// struct Bumm {
4.47 -// //int a;
4.48 -// bool b;
4.49 -// };
4.50 -
4.51 -// std::cout << sizeof(Bumm) << std::endl;
4.52 -
4.53 -
4.54 Graph g;
4.55
4.56 Node s, t;
4.57 @@ -141,35 +103,24 @@
4.58 }
4.59
4.60 // {
4.61 -// std::cout << "faster physical blocking flow augmentation ..." << std::endl;
4.62 +// std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
4.63 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
4.64 // ts.reset();
4.65 // int i=0;
4.66 -// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
4.67 +// while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
4.68 // std::cout << "elapsed time: " << ts << std::endl;
4.69 // std::cout << "number of augmentation phases: " << i << std::endl;
4.70 -// std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
4.71 +// std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
4.72 +
4.73 +// FOR_EACH_LOC(Graph::EdgeIt, e, g) {
4.74 +// if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
4.75 +// std::cout << "Slackness does not hold!" << std::endl;
4.76 +// if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
4.77 +// std::cout << "Slackness does not hold!" << std::endl;
4.78 +// }
4.79 // }
4.80
4.81 {
4.82 - std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
4.83 - FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
4.84 - ts.reset();
4.85 - int i=0;
4.86 - while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
4.87 - std::cout << "elapsed time: " << ts << std::endl;
4.88 - std::cout << "number of augmentation phases: " << i << std::endl;
4.89 - std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
4.90 -
4.91 - FOR_EACH_LOC(Graph::EdgeIt, e, g) {
4.92 - if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
4.93 - std::cout << "Slackness does not hold!" << std::endl;
4.94 - if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
4.95 - std::cout << "Slackness does not hold!" << std::endl;
4.96 - }
4.97 - }
4.98 -
4.99 - {
4.100 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
4.101 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
4.102 ts.reset();