1.1 --- a/src/hugo/graph_wrapper.h Fri May 07 06:58:24 2004 +0000
1.2 +++ b/src/hugo/graph_wrapper.h Fri May 07 07:44:44 2004 +0000
1.3 @@ -218,6 +218,8 @@
1.4 };
1.5 };
1.6
1.7 +
1.8 +
1.9 /// A graph wrapper which reverses the orientation of the edges.
1.10
1.11 /// A graph wrapper which reverses the orientation of the edges.
1.12 @@ -292,6 +294,8 @@
1.13
1.14 };
1.15
1.16 +
1.17 +
1.18 /// Wrapper for hiding nodes and edges from a graph.
1.19
1.20 /// This wrapper shows a graph with filtered node-set and
1.21 @@ -463,6 +467,8 @@
1.22 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
1.23 };
1.24
1.25 +
1.26 +
1.27 /// A wrapper for forgetting the orientation of a graph.
1.28
1.29 /// A wrapper for getting an undirected graph by forgetting
1.30 @@ -560,7 +566,321 @@
1.31 }
1.32 };
1.33
1.34 +
1.35 +
1.36 + /// A wrapper for composing bidirected graph from a directed one.
1.37 + /// experimental, for fezso's sake.
1.38 + template<typename Graph>
1.39 + class BidirGraphWrapper : public GraphWrapper<Graph> {
1.40 + protected:
1.41 + //const CapacityMap* capacity;
1.42 + //FlowMap* flow;
1.43 +
1.44 + BidirGraphWrapper() : GraphWrapper<Graph>()/*,
1.45 + capacity(0), flow(0)*/ { }
1.46 +// void setCapacityMap(const CapacityMap& _capacity) {
1.47 +// capacity=&_capacity;
1.48 +// }
1.49 +// void setFlowMap(FlowMap& _flow) {
1.50 +// flow=&_flow;
1.51 +// }
1.52 +
1.53 + public:
1.54 +
1.55 + BidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity,
1.56 + FlowMap& _flow*/) :
1.57 + GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
1.58 +
1.59 + class Edge;
1.60 + class OutEdgeIt;
1.61 + friend class Edge;
1.62 + friend class OutEdgeIt;
1.63 +
1.64 + typedef typename GraphWrapper<Graph>::Node Node;
1.65 + typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.66 + class Edge : public Graph::Edge {
1.67 + friend class BidirGraphWrapper<Graph>;
1.68 + protected:
1.69 + bool backward; //true, iff backward
1.70 +// typename Graph::Edge e;
1.71 + public:
1.72 + Edge() { }
1.73 + Edge(const typename Graph::Edge& _e, bool _backward) :
1.74 + Graph::Edge(_e), backward(_backward) { }
1.75 + Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
1.76 +//the unique invalid iterator
1.77 + friend bool operator==(const Edge& u, const Edge& v) {
1.78 + return (v.backward==u.backward &&
1.79 + static_cast<typename Graph::Edge>(u)==
1.80 + static_cast<typename Graph::Edge>(v));
1.81 + }
1.82 + friend bool operator!=(const Edge& u, const Edge& v) {
1.83 + return (v.backward!=u.backward ||
1.84 + static_cast<typename Graph::Edge>(u)!=
1.85 + static_cast<typename Graph::Edge>(v));
1.86 + }
1.87 + };
1.88 +
1.89 + class OutEdgeIt {
1.90 + friend class BidirGraphWrapper<Graph>;
1.91 + protected:
1.92 + typename Graph::OutEdgeIt out;
1.93 + typename Graph::InEdgeIt in;
1.94 + bool backward;
1.95 + public:
1.96 + OutEdgeIt() { }
1.97 + //FIXME
1.98 +// OutEdgeIt(const Edge& e) : Edge(e) { }
1.99 + OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1.100 +//the unique invalid iterator
1.101 + OutEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) {
1.102 + backward=false;
1.103 + _G.graph->first(out, v);
1.104 + while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
1.105 + if (!_G.graph->valid(out)) {
1.106 + backward=true;
1.107 + _G.graph->first(in, v);
1.108 + while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
1.109 + }
1.110 + }
1.111 + operator Edge() const {
1.112 +// Edge e;
1.113 +// e.forward=this->forward;
1.114 +// if (this->forward) e=out; else e=in;
1.115 +// return e;
1.116 + if (this->backward)
1.117 + return Edge(in, this->backward);
1.118 + else
1.119 + return Edge(out, this->backward);
1.120 + }
1.121 + };
1.122 +
1.123 + class InEdgeIt {
1.124 + friend class BidirGraphWrapper<Graph>;
1.125 + protected:
1.126 + typename Graph::OutEdgeIt out;
1.127 + typename Graph::InEdgeIt in;
1.128 + bool backward;
1.129 + public:
1.130 + InEdgeIt() { }
1.131 + //FIXME
1.132 +// OutEdgeIt(const Edge& e) : Edge(e) { }
1.133 + InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1.134 +//the unique invalid iterator
1.135 + InEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) {
1.136 + backward=false;
1.137 + _G.graph->first(in, v);
1.138 + while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
1.139 + if (!_G.graph->valid(in)) {
1.140 + backward=true;
1.141 + _G.graph->first(out, v);
1.142 + while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
1.143 + }
1.144 + }
1.145 + operator Edge() const {
1.146 +// Edge e;
1.147 +// e.forward=this->forward;
1.148 +// if (this->forward) e=out; else e=in;
1.149 +// return e;
1.150 + if (this->backward)
1.151 + return Edge(out, this->backward);
1.152 + else
1.153 + return Edge(in, this->backward);
1.154 + }
1.155 + };
1.156 +
1.157 + class EdgeIt {
1.158 + friend class BidirGraphWrapper<Graph>;
1.159 + protected:
1.160 + typename Graph::EdgeIt e;
1.161 + bool backward;
1.162 + public:
1.163 + EdgeIt() { }
1.164 + EdgeIt(const Invalid& i) : e(i), backward(true) { }
1.165 + EdgeIt(const BidirGraphWrapper<Graph>& _G) {
1.166 + backward=false;
1.167 + _G.graph->first(e);
1.168 + while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
1.169 + if (!_G.graph->valid(e)) {
1.170 + backward=true;
1.171 + _G.graph->first(e);
1.172 + while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
1.173 + }
1.174 + }
1.175 + operator Edge() const {
1.176 + return Edge(e, this->backward);
1.177 + }
1.178 + };
1.179 +
1.180 + using GraphWrapper<Graph>::first;
1.181 +// NodeIt& first(NodeIt& i) const {
1.182 +// i=NodeIt(*this); return i;
1.183 +// }
1.184 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.185 + i=OutEdgeIt(*this, p); return i;
1.186 + }
1.187 +// FIXME not tested
1.188 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.189 + i=InEdgeIt(*this, p); return i;
1.190 + }
1.191 + EdgeIt& first(EdgeIt& i) const {
1.192 + i=EdgeIt(*this); return i;
1.193 + }
1.194
1.195 + using GraphWrapper<Graph>::next;
1.196 +// NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
1.197 + OutEdgeIt& next(OutEdgeIt& e) const {
1.198 + if (!e.backward) {
1.199 + Node v=this->graph->aNode(e.out);
1.200 + this->graph->next(e.out);
1.201 + while(this->graph->valid(e.out) && !enabled(e)) {
1.202 + this->graph->next(e.out); }
1.203 + if (!this->graph->valid(e.out)) {
1.204 + e.backward=true;
1.205 + this->graph->first(e.in, v);
1.206 + while(this->graph->valid(e.in) && !enabled(e)) {
1.207 + this->graph->next(e.in); }
1.208 + }
1.209 + } else {
1.210 + this->graph->next(e.in);
1.211 + while(this->graph->valid(e.in) && !enabled(e)) {
1.212 + this->graph->next(e.in); }
1.213 + }
1.214 + return e;
1.215 + }
1.216 +// FIXME Not tested
1.217 + InEdgeIt& next(InEdgeIt& e) const {
1.218 + if (!e.backward) {
1.219 + Node v=this->graph->aNode(e.in);
1.220 + this->graph->next(e.in);
1.221 + while(this->graph->valid(e.in) && !enabled(e)) {
1.222 + this->graph->next(e.in); }
1.223 + if (!this->graph->valid(e.in)) {
1.224 + e.backward=true;
1.225 + this->graph->first(e.out, v);
1.226 + while(this->graph->valid(e.out) && !enabled(e)) {
1.227 + this->graph->next(e.out); }
1.228 + }
1.229 + } else {
1.230 + this->graph->next(e.out);
1.231 + while(this->graph->valid(e.out) && !enabled(e)) {
1.232 + this->graph->next(e.out); }
1.233 + }
1.234 + return e;
1.235 + }
1.236 + EdgeIt& next(EdgeIt& e) const {
1.237 + if (!e.backward) {
1.238 + this->graph->next(e.e);
1.239 + while(this->graph->valid(e.e) && !enabled(e)) {
1.240 + this->graph->next(e.e); }
1.241 + if (!this->graph->valid(e.e)) {
1.242 + e.backward=true;
1.243 + this->graph->first(e.e);
1.244 + while(this->graph->valid(e.e) && !enabled(e)) {
1.245 + this->graph->next(e.e); }
1.246 + }
1.247 + } else {
1.248 + this->graph->next(e.e);
1.249 + while(this->graph->valid(e.e) && !enabled(e)) {
1.250 + this->graph->next(e.e); }
1.251 + }
1.252 + return e;
1.253 + }
1.254 +
1.255 + Node tail(Edge e) const {
1.256 + return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
1.257 + Node head(Edge e) const {
1.258 + return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
1.259 +
1.260 + Node aNode(OutEdgeIt e) const {
1.261 + return ((!e.backward) ? this->graph->aNode(e.out) :
1.262 + this->graph->aNode(e.in)); }
1.263 + Node bNode(OutEdgeIt e) const {
1.264 + return ((!e.backward) ? this->graph->bNode(e.out) :
1.265 + this->graph->bNode(e.in)); }
1.266 +
1.267 + Node aNode(InEdgeIt e) const {
1.268 + return ((!e.backward) ? this->graph->aNode(e.in) :
1.269 + this->graph->aNode(e.out)); }
1.270 + Node bNode(InEdgeIt e) const {
1.271 + return ((!e.backward) ? this->graph->bNode(e.in) :
1.272 + this->graph->bNode(e.out)); }
1.273 +
1.274 +// int nodeNum() const { return graph->nodeNum(); }
1.275 + //FIXME
1.276 + void edgeNum() const { }
1.277 + //int edgeNum() const { return graph->edgeNum(); }
1.278 +
1.279 +
1.280 +// int id(Node v) const { return graph->id(v); }
1.281 +
1.282 + bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
1.283 + bool valid(Edge e) const {
1.284 + return this->graph->valid(e);
1.285 + //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
1.286 + }
1.287 +
1.288 + bool forward(const Edge& e) const { return !e.backward; }
1.289 + bool backward(const Edge& e) const { return e.backward; }
1.290 +
1.291 +// void augment(const Edge& e, Number a) const {
1.292 +// if (!e.backward)
1.293 +// // flow->set(e.out, flow->get(e.out)+a);
1.294 +// flow->set(e, (*flow)[e]+a);
1.295 +// else
1.296 +// // flow->set(e.in, flow->get(e.in)-a);
1.297 +// flow->set(e, (*flow)[e]-a);
1.298 +// }
1.299 +
1.300 + bool enabled(const Edge& e) const {
1.301 + if (!e.backward)
1.302 +// return (capacity->get(e.out)-flow->get(e.out));
1.303 + //return ((*capacity)[e]-(*flow)[e]);
1.304 + return true;
1.305 + else
1.306 +// return (flow->get(e.in));
1.307 + //return ((*flow)[e]);
1.308 + return true;
1.309 + }
1.310 +
1.311 +// Number enabled(typename Graph::OutEdgeIt out) const {
1.312 +// // return (capacity->get(out)-flow->get(out));
1.313 +// return ((*capacity)[out]-(*flow)[out]);
1.314 +// }
1.315 +
1.316 +// Number enabled(typename Graph::InEdgeIt in) const {
1.317 +// // return (flow->get(in));
1.318 +// return ((*flow)[in]);
1.319 +// }
1.320 +
1.321 + template <typename T>
1.322 + class EdgeMap {
1.323 + typename Graph::template EdgeMap<T> forward_map, backward_map;
1.324 + public:
1.325 + EdgeMap(const BidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1.326 + EdgeMap(const BidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1.327 + void set(Edge e, T a) {
1.328 + if (!e.backward)
1.329 + forward_map.set(e.out, a);
1.330 + else
1.331 + backward_map.set(e.in, a);
1.332 + }
1.333 + T operator[](Edge e) const {
1.334 + if (!e.backward)
1.335 + return forward_map[e.out];
1.336 + else
1.337 + return backward_map[e.in];
1.338 + }
1.339 +// T get(Edge e) const {
1.340 +// if (e.out_or_in)
1.341 +// return forward_map.get(e.out);
1.342 +// else
1.343 +// return backward_map.get(e.in);
1.344 +// }
1.345 + };
1.346 + };
1.347 +
1.348 +
1.349
1.350 /// A wrapper for composing the residual graph for directed flow and circulation problems.
1.351
1.352 @@ -629,14 +949,14 @@
1.353 // OutEdgeIt(const Edge& e) : Edge(e) { }
1.354 OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1.355 //the unique invalid iterator
1.356 - OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
1.357 + OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
1.358 backward=false;
1.359 - resG.graph->first(out, v);
1.360 - while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
1.361 - if (!resG.graph->valid(out)) {
1.362 + _G.graph->first(out, v);
1.363 + while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
1.364 + if (!_G.graph->valid(out)) {
1.365 backward=true;
1.366 - resG.graph->first(in, v);
1.367 - while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
1.368 + _G.graph->first(in, v);
1.369 + while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
1.370 }
1.371 }
1.372 operator Edge() const {
1.373 @@ -663,14 +983,14 @@
1.374 // OutEdgeIt(const Edge& e) : Edge(e) { }
1.375 InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1.376 //the unique invalid iterator
1.377 - InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
1.378 + InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
1.379 backward=false;
1.380 - resG.graph->first(in, v);
1.381 - while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
1.382 - if (!resG.graph->valid(in)) {
1.383 + _G.graph->first(in, v);
1.384 + while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
1.385 + if (!_G.graph->valid(in)) {
1.386 backward=true;
1.387 - resG.graph->first(out, v);
1.388 - while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
1.389 + _G.graph->first(out, v);
1.390 + while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
1.391 }
1.392 }
1.393 operator Edge() const {
1.394 @@ -693,14 +1013,14 @@
1.395 public:
1.396 EdgeIt() { }
1.397 EdgeIt(const Invalid& i) : e(i), backward(true) { }
1.398 - EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) {
1.399 + EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) {
1.400 backward=false;
1.401 - resG.graph->first(e);
1.402 - while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
1.403 - if (!resG.graph->valid(e)) {
1.404 + _G.graph->first(e);
1.405 + while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
1.406 + if (!_G.graph->valid(e)) {
1.407 backward=true;
1.408 - resG.graph->first(e);
1.409 - while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
1.410 + _G.graph->first(e);
1.411 + while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
1.412 }
1.413 }
1.414 operator Edge() const {
1.415 @@ -874,6 +1194,8 @@
1.416 };
1.417 };
1.418
1.419 +
1.420 +
1.421 /// ErasingFirstGraphWrapper for blocking flows.
1.422
1.423 /// ErasingFirstGraphWrapper for blocking flows.
2.1 --- a/src/work/marci/iterator_bfs_demo.cc Fri May 07 06:58:24 2004 +0000
2.2 +++ b/src/work/marci/iterator_bfs_demo.cc Fri May 07 07:44:44 2004 +0000
2.3 @@ -314,5 +314,88 @@
2.4 }
2.5 }
2.6
2.7 +
2.8 +
2.9 + {
2.10 + typedef BidirGraphWrapper<const Graph> GW;
2.11 + GW gw(G);
2.12 +
2.13 + EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
2.14 +
2.15 + cout << "bfs and dfs iterator demo on the undirected graph" << endl;
2.16 + for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
2.17 + cout << node_name[GW::Node(n)] << ": ";
2.18 + cout << "out edges: ";
2.19 + for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
2.20 + cout << edge_name[e] << " ";
2.21 + cout << "in edges: ";
2.22 + for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
2.23 + cout << edge_name[e] << " ";
2.24 + cout << endl;
2.25 + }
2.26 +// for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) {
2.27 +// cout << edge_name.get(e) << " ";
2.28 +// }
2.29 +// cout << endl;
2.30 +
2.31 + cout << "bfs from t ..." << endl;
2.32 + BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
2.33 + bfs.pushAndSetReached(t);
2.34 + while (!bfs.finished()) {
2.35 + //cout << "edge: ";
2.36 + if (gw.valid(GW::OutEdgeIt(bfs))) {
2.37 + cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
2.38 + node_name[gw.aNode(bfs)] <<
2.39 + (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
2.40 + node_name[gw.bNode(bfs)] <<
2.41 + (bfs.isBNodeNewlyReached() ? ": is newly reached." :
2.42 + ": is not newly reached.");
2.43 + } else {
2.44 + cout << "invalid" << /*endl*/", " <<
2.45 + node_name[bfs.aNode()] <<
2.46 + (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
2.47 +
2.48 + "invalid.";
2.49 + }
2.50 + cout << endl;
2.51 + ++bfs;
2.52 + }
2.53 +
2.54 + cout << " /--> -------------> "<< endl;
2.55 + cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
2.56 + cout << " / | | / /-> \\ "<< endl;
2.57 + cout << " / | | / | ^ \\ "<< endl;
2.58 + cout << "s | | / | | \\-> t "<< endl;
2.59 + cout << " \\ | | / | | /-> "<< endl;
2.60 + cout << " \\ | --/ / | | / "<< endl;
2.61 + cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
2.62 + cout << " \\--> -------------> "<< endl;
2.63 +
2.64 + cout << "dfs from t ..." << endl;
2.65 + DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
2.66 + dfs.pushAndSetReached(t);
2.67 + while (!dfs.finished()) {
2.68 + ++dfs;
2.69 + //cout << "edge: ";
2.70 + if (gw.valid(GW::OutEdgeIt(dfs))) {
2.71 + cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
2.72 + node_name[gw.aNode(dfs)] <<
2.73 + (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
2.74 + node_name[gw.bNode(dfs)] <<
2.75 + (dfs.isBNodeNewlyReached() ? ": is newly reached." :
2.76 + ": is not newly reached.");
2.77 + } else {
2.78 + cout << "invalid" << /*endl*/", " <<
2.79 + node_name[dfs.aNode()] <<
2.80 + (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
2.81 +
2.82 + "invalid.";
2.83 + }
2.84 + cout << endl;
2.85 + }
2.86 + }
2.87 +
2.88 +
2.89 +
2.90 return 0;
2.91 }