1.1 --- a/src/hugo/graph_wrapper.h Thu May 20 09:42:31 2004 +0000
1.2 +++ b/src/hugo/graph_wrapper.h Thu May 20 15:40:59 2004 +0000
1.3 @@ -11,6 +11,7 @@
1.4 ///\author Marton Makai
1.5
1.6 #include <hugo/invalid.h>
1.7 +#include <hugo/maps.h>
1.8 //#include <iter_map.h>
1.9
1.10 namespace hugo {
1.11 @@ -103,6 +104,10 @@
1.12 public:
1.13 Node() { }
1.14 Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
1.15 + // /// \bug construction throughrthr multiple levels should be
1.16 + // /// handled better
1.17 + // Node(const typename ParentGraph::ParentGraph::Node& _n) :
1.18 + // Graph::Node(_n) { }
1.19 Node(const Invalid& i) : Graph::Node(i) { }
1.20 };
1.21 class NodeIt {
1.22 @@ -202,6 +207,11 @@
1.23
1.24 void clear() const { graph->clear(); }
1.25
1.26 + bool forward(const Edge& e) const { graph->forward(e); }
1.27 + bool backward(const Edge& e) const { graph->backward(e); }
1.28 +
1.29 + Edge opposite(const Edge& e) const { Edge(graph->opposite(e)); }
1.30 +
1.31 template<typename T> class NodeMap : public Graph::template NodeMap<T> {
1.32 typedef typename Graph::template NodeMap<T> Parent;
1.33 public:
1.34 @@ -227,6 +237,8 @@
1.35 ///\author Marton Makai
1.36 template<typename Graph>
1.37 class RevGraphWrapper : public GraphWrapper<Graph> {
1.38 + public:
1.39 + typedef GraphWrapper<Graph> Parent;
1.40 protected:
1.41 RevGraphWrapper() : GraphWrapper<Graph>() { }
1.42 public:
1.43 @@ -307,6 +319,8 @@
1.44 template<typename Graph, typename NodeFilterMap,
1.45 typename EdgeFilterMap>
1.46 class SubGraphWrapper : public GraphWrapper<Graph> {
1.47 + public:
1.48 + typedef GraphWrapper<Graph> Parent;
1.49 protected:
1.50 NodeFilterMap* node_filter_map;
1.51 EdgeFilterMap* edge_filter_map;
1.52 @@ -321,7 +335,6 @@
1.53 }
1.54
1.55 public:
1.56 -
1.57 SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
1.58 EdgeFilterMap& _edge_filter_map) :
1.59 GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
1.60 @@ -496,6 +509,8 @@
1.61 /// \author Marton Makai
1.62 template<typename Graph>
1.63 class UndirGraphWrapper : public GraphWrapper<Graph> {
1.64 + public:
1.65 + typedef GraphWrapper<Graph> Parent;
1.66 protected:
1.67 UndirGraphWrapper() : GraphWrapper<Graph>() { }
1.68
1.69 @@ -591,34 +606,44 @@
1.70 };
1.71
1.72
1.73 - ///\brief A wrapper for composing bidirected graph from a directed one.
1.74 +
1.75 + ///\brief A wrapper for composing a subgraph of a
1.76 + /// bidirected graph composed from a directed one.
1.77 /// experimental, for fezso's sake.
1.78 ///
1.79 - /// A wrapper for composing bidirected graph from a directed one.
1.80 + /// A wrapper for composing a subgraps of a
1.81 + /// bidirected graph composed from a directed one.
1.82 /// experimental, for fezso's sake.
1.83 /// A bidirected graph is composed over the directed one without physical
1.84 /// storage. As the oppositely directed edges are logically different ones
1.85 /// the maps are able to attach different values for them.
1.86 - template<typename Graph>
1.87 - class BidirGraphWrapper : public GraphWrapper<Graph> {
1.88 + template<typename Graph,
1.89 + typename ForwardFilterMap, typename BackwardFilterMap>
1.90 + class SubBidirGraphWrapper : public GraphWrapper<Graph> {
1.91 + public:
1.92 + typedef GraphWrapper<Graph> Parent;
1.93 protected:
1.94 //const CapacityMap* capacity;
1.95 //FlowMap* flow;
1.96
1.97 - BidirGraphWrapper() : GraphWrapper<Graph>()/*,
1.98 + ForwardFilterMap* forward_filter;
1.99 + BackwardFilterMap* backward_filter;
1.100 +
1.101 + SubBidirGraphWrapper() : GraphWrapper<Graph>()/*,
1.102 capacity(0), flow(0)*/ { }
1.103 -// void setCapacityMap(const CapacityMap& _capacity) {
1.104 -// capacity=&_capacity;
1.105 -// }
1.106 -// void setFlowMap(FlowMap& _flow) {
1.107 -// flow=&_flow;
1.108 -// }
1.109 + void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
1.110 + forward_filter=&_forward_filter;
1.111 + }
1.112 + void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
1.113 + backward_filter=&_backward_filter;
1.114 + }
1.115
1.116 public:
1.117
1.118 - BidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity,
1.119 - FlowMap& _flow*/) :
1.120 - GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
1.121 + SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter,
1.122 + BackwardFilterMap& _backward_filter) :
1.123 + GraphWrapper<Graph>(_graph),
1.124 + forward_filter(&_forward_filter), backward_filter(&_backward_filter) { }
1.125
1.126 class Edge;
1.127 class OutEdgeIt;
1.128 @@ -632,7 +657,8 @@
1.129 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.130
1.131 class Edge : public Graph::Edge {
1.132 - friend class BidirGraphWrapper<Graph>;
1.133 + friend class SubBidirGraphWrapper<Graph,
1.134 + ForwardFilterMap, BackwardFilterMap>;
1.135 ///\bug ez nem is kell
1.136 //template<typename T> friend class NodeMap;
1.137 template<typename T> friend class EdgeMap;
1.138 @@ -659,7 +685,8 @@
1.139 };
1.140
1.141 class OutEdgeIt {
1.142 - friend class BidirGraphWrapper<Graph>;
1.143 + friend class SubBidirGraphWrapper<Graph,
1.144 + ForwardFilterMap, BackwardFilterMap>;
1.145 protected:
1.146 typename Graph::OutEdgeIt out;
1.147 typename Graph::InEdgeIt in;
1.148 @@ -670,14 +697,15 @@
1.149 // OutEdgeIt(const Edge& e) : Edge(e) { }
1.150 OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1.151 //the unique invalid iterator
1.152 - OutEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) {
1.153 + OutEdgeIt(const SubBidirGraphWrapper<Graph,
1.154 + ForwardFilterMap, BackwardFilterMap>& _G, Node v) {
1.155 backward=false;
1.156 _G.graph->first(out, v);
1.157 - while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
1.158 + while(_G.graph->valid(out) && !(*_G.forward_filter)[*this]) { _G.graph->next(out); }
1.159 if (!_G.graph->valid(out)) {
1.160 backward=true;
1.161 _G.graph->first(in, v);
1.162 - while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
1.163 + while(_G.graph->valid(in) && !(*_G.backward_filter)[*this]) { _G.graph->next(in); }
1.164 }
1.165 }
1.166 operator Edge() const {
1.167 @@ -693,7 +721,8 @@
1.168 };
1.169
1.170 class InEdgeIt {
1.171 - friend class BidirGraphWrapper<Graph>;
1.172 + friend class SubBidirGraphWrapper<Graph,
1.173 + ForwardFilterMap, BackwardFilterMap>;
1.174 protected:
1.175 typename Graph::OutEdgeIt out;
1.176 typename Graph::InEdgeIt in;
1.177 @@ -704,14 +733,15 @@
1.178 // OutEdgeIt(const Edge& e) : Edge(e) { }
1.179 InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1.180 //the unique invalid iterator
1.181 - InEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) {
1.182 + InEdgeIt(const SubBidirGraphWrapper<Graph,
1.183 + ForwardFilterMap, BackwardFilterMap>& _G, Node v) {
1.184 backward=false;
1.185 _G.graph->first(in, v);
1.186 - while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
1.187 + while(_G.graph->valid(in) && !(*_G.forward_filter)[*this]) { _G.graph->next(in); }
1.188 if (!_G.graph->valid(in)) {
1.189 backward=true;
1.190 _G.graph->first(out, v);
1.191 - while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
1.192 + while(_G.graph->valid(out) && !(*_G.backward_filter)[*this]) { _G.graph->next(out); }
1.193 }
1.194 }
1.195 operator Edge() const {
1.196 @@ -727,21 +757,23 @@
1.197 };
1.198
1.199 class EdgeIt {
1.200 - friend class BidirGraphWrapper<Graph>;
1.201 + friend class SubBidirGraphWrapper<Graph,
1.202 + ForwardFilterMap, BackwardFilterMap>;
1.203 protected:
1.204 typename Graph::EdgeIt e;
1.205 bool backward;
1.206 public:
1.207 EdgeIt() { }
1.208 EdgeIt(const Invalid& i) : e(i), backward(true) { }
1.209 - EdgeIt(const BidirGraphWrapper<Graph>& _G) {
1.210 + EdgeIt(const SubBidirGraphWrapper<Graph,
1.211 + ForwardFilterMap, BackwardFilterMap>& _G) {
1.212 backward=false;
1.213 _G.graph->first(e);
1.214 - while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
1.215 + while (_G.graph->valid(e) && !(*_G.forward_filter)[*this]) _G.graph->next(e);
1.216 if (!_G.graph->valid(e)) {
1.217 backward=true;
1.218 _G.graph->first(e);
1.219 - while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
1.220 + while (_G.graph->valid(e) && !(*_G.backward_filter)[*this]) _G.graph->next(e);
1.221 }
1.222 }
1.223 operator Edge() const {
1.224 @@ -770,17 +802,17 @@
1.225 if (!e.backward) {
1.226 Node v=this->graph->aNode(e.out);
1.227 this->graph->next(e.out);
1.228 - while(this->graph->valid(e.out) && !enabled(e)) {
1.229 + while(this->graph->valid(e.out) && !(*forward_filter)[e]) {
1.230 this->graph->next(e.out); }
1.231 if (!this->graph->valid(e.out)) {
1.232 e.backward=true;
1.233 this->graph->first(e.in, v);
1.234 - while(this->graph->valid(e.in) && !enabled(e)) {
1.235 + while(this->graph->valid(e.in) && !(*backward_filter)[e]) {
1.236 this->graph->next(e.in); }
1.237 }
1.238 } else {
1.239 this->graph->next(e.in);
1.240 - while(this->graph->valid(e.in) && !enabled(e)) {
1.241 + while(this->graph->valid(e.in) && !(*backward_filter)[e]) {
1.242 this->graph->next(e.in); }
1.243 }
1.244 return e;
1.245 @@ -790,17 +822,17 @@
1.246 if (!e.backward) {
1.247 Node v=this->graph->aNode(e.in);
1.248 this->graph->next(e.in);
1.249 - while(this->graph->valid(e.in) && !enabled(e)) {
1.250 + while(this->graph->valid(e.in) && !(*forward_filter)[e]) {
1.251 this->graph->next(e.in); }
1.252 if (!this->graph->valid(e.in)) {
1.253 e.backward=true;
1.254 this->graph->first(e.out, v);
1.255 - while(this->graph->valid(e.out) && !enabled(e)) {
1.256 + while(this->graph->valid(e.out) && !(*backward_filter)[e]) {
1.257 this->graph->next(e.out); }
1.258 }
1.259 } else {
1.260 this->graph->next(e.out);
1.261 - while(this->graph->valid(e.out) && !enabled(e)) {
1.262 + while(this->graph->valid(e.out) && !(*backward_filter)[e]) {
1.263 this->graph->next(e.out); }
1.264 }
1.265 return e;
1.266 @@ -808,17 +840,17 @@
1.267 EdgeIt& next(EdgeIt& e) const {
1.268 if (!e.backward) {
1.269 this->graph->next(e.e);
1.270 - while(this->graph->valid(e.e) && !enabled(e)) {
1.271 + while(this->graph->valid(e.e) && !(*forward_filter)[e]) {
1.272 this->graph->next(e.e); }
1.273 if (!this->graph->valid(e.e)) {
1.274 e.backward=true;
1.275 this->graph->first(e.e);
1.276 - while(this->graph->valid(e.e) && !enabled(e)) {
1.277 + while(this->graph->valid(e.e) && !(*backward_filter)[e]) {
1.278 this->graph->next(e.e); }
1.279 }
1.280 } else {
1.281 this->graph->next(e.e);
1.282 - while(this->graph->valid(e.e) && !enabled(e)) {
1.283 + while(this->graph->valid(e.e) && !(*backward_filter)[e]) {
1.284 this->graph->next(e.e); }
1.285 }
1.286 return e;
1.287 @@ -876,16 +908,16 @@
1.288 // flow->set(e, (*flow)[e]-a);
1.289 // }
1.290
1.291 - bool enabled(const Edge& e) const {
1.292 - if (!e.backward)
1.293 -// return (capacity->get(e.out)-flow->get(e.out));
1.294 - //return ((*capacity)[e]-(*flow)[e]);
1.295 - return true;
1.296 - else
1.297 -// return (flow->get(e.in));
1.298 - //return ((*flow)[e]);
1.299 - return true;
1.300 - }
1.301 +// bool enabled(const Edge& e) const {
1.302 +// if (!e.backward)
1.303 +// // return (capacity->get(e.out)-flow->get(e.out));
1.304 +// //return ((*capacity)[e]-(*flow)[e]);
1.305 +// return true;
1.306 +// else
1.307 +// // return (flow->get(e.in));
1.308 +// //return ((*flow)[e]);
1.309 +// return true;
1.310 +// }
1.311
1.312 // Number enabled(typename Graph::OutEdgeIt out) const {
1.313 // // return (capacity->get(out)-flow->get(out));
1.314 @@ -903,8 +935,12 @@
1.315 public:
1.316 typedef T ValueType;
1.317 typedef Edge KeyType;
1.318 - EdgeMap(const BidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1.319 - EdgeMap(const BidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1.320 + EdgeMap(const SubBidirGraphWrapper<Graph,
1.321 + ForwardFilterMap, BackwardFilterMap>& _G) :
1.322 + forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1.323 + EdgeMap(const SubBidirGraphWrapper<Graph,
1.324 + ForwardFilterMap, BackwardFilterMap>& _G, T a) :
1.325 + forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1.326 void set(Edge e, T a) {
1.327 if (!e.backward)
1.328 forward_map.set(e/*.out*/, a);
1.329 @@ -930,6 +966,393 @@
1.330 };
1.331 };
1.332
1.333 +
1.334 +
1.335 + ///\brief A wrapper for composing bidirected graph from a directed one.
1.336 + /// experimental, for fezso's sake.
1.337 + ///
1.338 + /// A wrapper for composing bidirected graph from a directed one.
1.339 + /// experimental, for fezso's sake.
1.340 + /// A bidirected graph is composed over the directed one without physical
1.341 + /// storage. As the oppositely directed edges are logically different ones
1.342 + /// the maps are able to attach different values for them.
1.343 + template<typename Graph>
1.344 + class BidirGraphWrapper :
1.345 + public SubBidirGraphWrapper<
1.346 + Graph,
1.347 + ConstMap<typename Graph::Edge, bool>,
1.348 + ConstMap<typename Graph::Edge, bool> > {
1.349 + public:
1.350 + typedef SubBidirGraphWrapper<
1.351 + Graph,
1.352 + ConstMap<typename Graph::Edge, bool>,
1.353 + ConstMap<typename Graph::Edge, bool> > Parent;
1.354 + protected:
1.355 + ConstMap<typename Graph::Edge, bool> cm;
1.356 + //const CapacityMap* capacity;
1.357 + //FlowMap* flow;
1.358 +
1.359 + BidirGraphWrapper() : Parent(), cm(true) { }
1.360 +// void setCapacityMap(const CapacityMap& _capacity) {
1.361 +// capacity=&_capacity;
1.362 +// }
1.363 +// void setFlowMap(FlowMap& _flow) {
1.364 +// flow=&_flow;
1.365 +// }
1.366 +
1.367 + public:
1.368 +
1.369 + BidirGraphWrapper(Graph& _graph) : Parent() {
1.370 + Parent::setGraph(_graph);
1.371 + Parent::setForwardFilterMap(cm);
1.372 + Parent::setBackwardFilterMap(cm);
1.373 + }
1.374 + };
1.375 +
1.376 +
1.377 +
1.378 +
1.379 +// ///\brief A wrapper for composing bidirected graph from a directed one.
1.380 +// /// experimental, for fezso's sake.
1.381 +// ///
1.382 +// /// A wrapper for composing bidirected graph from a directed one.
1.383 +// /// experimental, for fezso's sake.
1.384 +// /// A bidirected graph is composed over the directed one without physical
1.385 +// /// storage. As the oppositely directed edges are logically different ones
1.386 +// /// the maps are able to attach different values for them.
1.387 +// template<typename Graph>
1.388 +// class BidirGraphWrapper : public GraphWrapper<Graph> {
1.389 +// public:
1.390 +// typedef GraphWrapper<Graph> Parent;
1.391 +// protected:
1.392 +// //const CapacityMap* capacity;
1.393 +// //FlowMap* flow;
1.394 +
1.395 +// BidirGraphWrapper() : GraphWrapper<Graph>()/*,
1.396 +// capacity(0), flow(0)*/ { }
1.397 +// // void setCapacityMap(const CapacityMap& _capacity) {
1.398 +// // capacity=&_capacity;
1.399 +// // }
1.400 +// // void setFlowMap(FlowMap& _flow) {
1.401 +// // flow=&_flow;
1.402 +// // }
1.403 +
1.404 +// public:
1.405 +
1.406 +// BidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity,
1.407 +// FlowMap& _flow*/) :
1.408 +// GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
1.409 +
1.410 +// class Edge;
1.411 +// class OutEdgeIt;
1.412 +// friend class Edge;
1.413 +// friend class OutEdgeIt;
1.414 +
1.415 +// //template<typename T> class NodeMap;
1.416 +// template<typename T> class EdgeMap;
1.417 +
1.418 +// typedef typename GraphWrapper<Graph>::Node Node;
1.419 +// typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.420 +
1.421 +// class Edge : public Graph::Edge {
1.422 +// friend class BidirGraphWrapper<Graph>;
1.423 +// ///\bug ez nem is kell
1.424 +// //template<typename T> friend class NodeMap;
1.425 +// template<typename T> friend class EdgeMap;
1.426 +// protected:
1.427 +// bool backward; //true, iff backward
1.428 +// // typename Graph::Edge e;
1.429 +// public:
1.430 +// Edge() { }
1.431 +// ///\bug =false kell-e? zsoltnak kell az addEdge miatt
1.432 +// Edge(const typename Graph::Edge& _e, bool _backward=false) :
1.433 +// Graph::Edge(_e), backward(_backward) { }
1.434 +// Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
1.435 +// //the unique invalid iterator
1.436 +// friend bool operator==(const Edge& u, const Edge& v) {
1.437 +// return (v.backward==u.backward &&
1.438 +// static_cast<typename Graph::Edge>(u)==
1.439 +// static_cast<typename Graph::Edge>(v));
1.440 +// }
1.441 +// friend bool operator!=(const Edge& u, const Edge& v) {
1.442 +// return (v.backward!=u.backward ||
1.443 +// static_cast<typename Graph::Edge>(u)!=
1.444 +// static_cast<typename Graph::Edge>(v));
1.445 +// }
1.446 +// };
1.447 +
1.448 +// class OutEdgeIt {
1.449 +// friend class BidirGraphWrapper<Graph>;
1.450 +// protected:
1.451 +// typename Graph::OutEdgeIt out;
1.452 +// typename Graph::InEdgeIt in;
1.453 +// bool backward;
1.454 +// public:
1.455 +// OutEdgeIt() { }
1.456 +// //FIXME
1.457 +// // OutEdgeIt(const Edge& e) : Edge(e) { }
1.458 +// OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1.459 +// //the unique invalid iterator
1.460 +// OutEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) {
1.461 +// backward=false;
1.462 +// _G.graph->first(out, v);
1.463 +// while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
1.464 +// if (!_G.graph->valid(out)) {
1.465 +// backward=true;
1.466 +// _G.graph->first(in, v);
1.467 +// while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
1.468 +// }
1.469 +// }
1.470 +// operator Edge() const {
1.471 +// // Edge e;
1.472 +// // e.forward=this->forward;
1.473 +// // if (this->forward) e=out; else e=in;
1.474 +// // return e;
1.475 +// if (this->backward)
1.476 +// return Edge(in, this->backward);
1.477 +// else
1.478 +// return Edge(out, this->backward);
1.479 +// }
1.480 +// };
1.481 +
1.482 +// class InEdgeIt {
1.483 +// friend class BidirGraphWrapper<Graph>;
1.484 +// protected:
1.485 +// typename Graph::OutEdgeIt out;
1.486 +// typename Graph::InEdgeIt in;
1.487 +// bool backward;
1.488 +// public:
1.489 +// InEdgeIt() { }
1.490 +// //FIXME
1.491 +// // OutEdgeIt(const Edge& e) : Edge(e) { }
1.492 +// InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1.493 +// //the unique invalid iterator
1.494 +// InEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) {
1.495 +// backward=false;
1.496 +// _G.graph->first(in, v);
1.497 +// while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
1.498 +// if (!_G.graph->valid(in)) {
1.499 +// backward=true;
1.500 +// _G.graph->first(out, v);
1.501 +// while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
1.502 +// }
1.503 +// }
1.504 +// operator Edge() const {
1.505 +// // Edge e;
1.506 +// // e.forward=this->forward;
1.507 +// // if (this->forward) e=out; else e=in;
1.508 +// // return e;
1.509 +// if (this->backward)
1.510 +// return Edge(out, this->backward);
1.511 +// else
1.512 +// return Edge(in, this->backward);
1.513 +// }
1.514 +// };
1.515 +
1.516 +// class EdgeIt {
1.517 +// friend class BidirGraphWrapper<Graph>;
1.518 +// protected:
1.519 +// typename Graph::EdgeIt e;
1.520 +// bool backward;
1.521 +// public:
1.522 +// EdgeIt() { }
1.523 +// EdgeIt(const Invalid& i) : e(i), backward(true) { }
1.524 +// EdgeIt(const BidirGraphWrapper<Graph>& _G) {
1.525 +// backward=false;
1.526 +// _G.graph->first(e);
1.527 +// while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
1.528 +// if (!_G.graph->valid(e)) {
1.529 +// backward=true;
1.530 +// _G.graph->first(e);
1.531 +// while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
1.532 +// }
1.533 +// }
1.534 +// operator Edge() const {
1.535 +// return Edge(e, this->backward);
1.536 +// }
1.537 +// };
1.538 +
1.539 +// using GraphWrapper<Graph>::first;
1.540 +// // NodeIt& first(NodeIt& i) const {
1.541 +// // i=NodeIt(*this); return i;
1.542 +// // }
1.543 +// OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.544 +// i=OutEdgeIt(*this, p); return i;
1.545 +// }
1.546 +// // FIXME not tested
1.547 +// InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.548 +// i=InEdgeIt(*this, p); return i;
1.549 +// }
1.550 +// EdgeIt& first(EdgeIt& i) const {
1.551 +// i=EdgeIt(*this); return i;
1.552 +// }
1.553 +
1.554 +// using GraphWrapper<Graph>::next;
1.555 +// // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
1.556 +// OutEdgeIt& next(OutEdgeIt& e) const {
1.557 +// if (!e.backward) {
1.558 +// Node v=this->graph->aNode(e.out);
1.559 +// this->graph->next(e.out);
1.560 +// while(this->graph->valid(e.out) && !enabled(e)) {
1.561 +// this->graph->next(e.out); }
1.562 +// if (!this->graph->valid(e.out)) {
1.563 +// e.backward=true;
1.564 +// this->graph->first(e.in, v);
1.565 +// while(this->graph->valid(e.in) && !enabled(e)) {
1.566 +// this->graph->next(e.in); }
1.567 +// }
1.568 +// } else {
1.569 +// this->graph->next(e.in);
1.570 +// while(this->graph->valid(e.in) && !enabled(e)) {
1.571 +// this->graph->next(e.in); }
1.572 +// }
1.573 +// return e;
1.574 +// }
1.575 +// // FIXME Not tested
1.576 +// InEdgeIt& next(InEdgeIt& e) const {
1.577 +// if (!e.backward) {
1.578 +// Node v=this->graph->aNode(e.in);
1.579 +// this->graph->next(e.in);
1.580 +// while(this->graph->valid(e.in) && !enabled(e)) {
1.581 +// this->graph->next(e.in); }
1.582 +// if (!this->graph->valid(e.in)) {
1.583 +// e.backward=true;
1.584 +// this->graph->first(e.out, v);
1.585 +// while(this->graph->valid(e.out) && !enabled(e)) {
1.586 +// this->graph->next(e.out); }
1.587 +// }
1.588 +// } else {
1.589 +// this->graph->next(e.out);
1.590 +// while(this->graph->valid(e.out) && !enabled(e)) {
1.591 +// this->graph->next(e.out); }
1.592 +// }
1.593 +// return e;
1.594 +// }
1.595 +// EdgeIt& next(EdgeIt& e) const {
1.596 +// if (!e.backward) {
1.597 +// this->graph->next(e.e);
1.598 +// while(this->graph->valid(e.e) && !enabled(e)) {
1.599 +// this->graph->next(e.e); }
1.600 +// if (!this->graph->valid(e.e)) {
1.601 +// e.backward=true;
1.602 +// this->graph->first(e.e);
1.603 +// while(this->graph->valid(e.e) && !enabled(e)) {
1.604 +// this->graph->next(e.e); }
1.605 +// }
1.606 +// } else {
1.607 +// this->graph->next(e.e);
1.608 +// while(this->graph->valid(e.e) && !enabled(e)) {
1.609 +// this->graph->next(e.e); }
1.610 +// }
1.611 +// return e;
1.612 +// }
1.613 +
1.614 +// Node tail(Edge e) const {
1.615 +// return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
1.616 +// Node head(Edge e) const {
1.617 +// return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
1.618 +
1.619 +// Node aNode(OutEdgeIt e) const {
1.620 +// return ((!e.backward) ? this->graph->aNode(e.out) :
1.621 +// this->graph->aNode(e.in)); }
1.622 +// Node bNode(OutEdgeIt e) const {
1.623 +// return ((!e.backward) ? this->graph->bNode(e.out) :
1.624 +// this->graph->bNode(e.in)); }
1.625 +
1.626 +// Node aNode(InEdgeIt e) const {
1.627 +// return ((!e.backward) ? this->graph->aNode(e.in) :
1.628 +// this->graph->aNode(e.out)); }
1.629 +// Node bNode(InEdgeIt e) const {
1.630 +// return ((!e.backward) ? this->graph->bNode(e.in) :
1.631 +// this->graph->bNode(e.out)); }
1.632 +
1.633 +// /// Gives back the opposite edge.
1.634 +// Edge opposite(const Edge& e) const {
1.635 +// Edge f=e;
1.636 +// f.backward=!f.backward;
1.637 +// return f;
1.638 +// }
1.639 +
1.640 +// // int nodeNum() const { return graph->nodeNum(); }
1.641 +// //FIXME
1.642 +// void edgeNum() const { }
1.643 +// //int edgeNum() const { return graph->edgeNum(); }
1.644 +
1.645 +
1.646 +// // int id(Node v) const { return graph->id(v); }
1.647 +
1.648 +// bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
1.649 +// bool valid(Edge e) const {
1.650 +// return this->graph->valid(e);
1.651 +// //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
1.652 +// }
1.653 +
1.654 +// bool forward(const Edge& e) const { return !e.backward; }
1.655 +// bool backward(const Edge& e) const { return e.backward; }
1.656 +
1.657 +// // void augment(const Edge& e, Number a) const {
1.658 +// // if (!e.backward)
1.659 +// // // flow->set(e.out, flow->get(e.out)+a);
1.660 +// // flow->set(e, (*flow)[e]+a);
1.661 +// // else
1.662 +// // // flow->set(e.in, flow->get(e.in)-a);
1.663 +// // flow->set(e, (*flow)[e]-a);
1.664 +// // }
1.665 +
1.666 +// bool enabled(const Edge& e) const {
1.667 +// if (!e.backward)
1.668 +// // return (capacity->get(e.out)-flow->get(e.out));
1.669 +// //return ((*capacity)[e]-(*flow)[e]);
1.670 +// return true;
1.671 +// else
1.672 +// // return (flow->get(e.in));
1.673 +// //return ((*flow)[e]);
1.674 +// return true;
1.675 +// }
1.676 +
1.677 +// // Number enabled(typename Graph::OutEdgeIt out) const {
1.678 +// // // return (capacity->get(out)-flow->get(out));
1.679 +// // return ((*capacity)[out]-(*flow)[out]);
1.680 +// // }
1.681 +
1.682 +// // Number enabled(typename Graph::InEdgeIt in) const {
1.683 +// // // return (flow->get(in));
1.684 +// // return ((*flow)[in]);
1.685 +// // }
1.686 +
1.687 +// template <typename T>
1.688 +// class EdgeMap {
1.689 +// typename Graph::template EdgeMap<T> forward_map, backward_map;
1.690 +// public:
1.691 +// typedef T ValueType;
1.692 +// typedef Edge KeyType;
1.693 +// EdgeMap(const BidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1.694 +// EdgeMap(const BidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1.695 +// void set(Edge e, T a) {
1.696 +// if (!e.backward)
1.697 +// forward_map.set(e/*.out*/, a);
1.698 +// else
1.699 +// backward_map.set(e/*.in*/, a);
1.700 +// }
1.701 +// T operator[](Edge e) const {
1.702 +// if (!e.backward)
1.703 +// return forward_map[e/*.out*/];
1.704 +// else
1.705 +// return backward_map[e/*.in*/];
1.706 +// }
1.707 +// void update() {
1.708 +// forward_map.update();
1.709 +// backward_map.update();
1.710 +// }
1.711 +// // T get(Edge e) const {
1.712 +// // if (e.out_or_in)
1.713 +// // return forward_map.get(e.out);
1.714 +// // else
1.715 +// // return backward_map.get(e.in);
1.716 +// // }
1.717 +// };
1.718 +// };
1.719 +
1.720 /// \brief A bidirected graph template.
1.721 ///
1.722 /// A bidirected graph template.
1.723 @@ -941,6 +1364,7 @@
1.724 /// \ingroup graphs
1.725 template<typename Graph>
1.726 class BidirGraph : public BidirGraphWrapper<Graph> {
1.727 + public:
1.728 typedef UndirGraphWrapper<Graph> Parent;
1.729 protected:
1.730 Graph gr;
1.731 @@ -951,12 +1375,161 @@
1.732 };
1.733
1.734
1.735 +
1.736 + /// An experiment for ResGraphWrapper.
1.737 + template<typename Graph, typename Number,
1.738 + typename CapacityMap, typename FlowMap>
1.739 + class ForwardFilter {
1.740 + const Graph* graph;
1.741 + const CapacityMap* capacity;
1.742 + const FlowMap* flow;
1.743 + public:
1.744 + ForwardFilter(const Graph& _graph,
1.745 + const CapacityMap& _capacity, const FlowMap& _flow) :
1.746 + graph(&_graph), capacity(&_capacity), flow(&_flow) { }
1.747 + bool operator[](const typename Graph::Edge& e) const {
1.748 + return ((*flow)[e] < (*capacity)[e]);
1.749 + }
1.750 + };
1.751 +
1.752 + /// An experiment for ResGraphWrapper.
1.753 + template<typename Graph, typename Number,
1.754 + typename CapacityMap, typename FlowMap>
1.755 + class BackwardFilter {
1.756 + const Graph* graph;
1.757 + const CapacityMap* capacity;
1.758 + const FlowMap* flow;
1.759 + public:
1.760 + BackwardFilter(const Graph& _graph,
1.761 + const CapacityMap& _capacity, const FlowMap& _flow) :
1.762 + graph(&_graph), capacity(&_capacity), flow(&_flow) { }
1.763 + bool operator[](const typename Graph::Edge& e) const {
1.764 + return (0 < (*flow)[e]);
1.765 + }
1.766 + };
1.767 +
1.768 +
1.769 + /// An experiment for ResGraphWrapper.
1.770 + template<typename Graph, typename Number,
1.771 + typename CapacityMap, typename FlowMap>
1.772 + class ExpResGraphWrapper :
1.773 + public SubBidirGraphWrapper<
1.774 + Graph,
1.775 + ForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1.776 + BackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1.777 + public:
1.778 + typedef SubBidirGraphWrapper<
1.779 + Graph,
1.780 + ForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1.781 + BackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1.782 + protected:
1.783 + const CapacityMap* capacity;
1.784 + FlowMap* flow;
1.785 + ForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1.786 + BackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1.787 + public:
1.788 + ExpResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1.789 + FlowMap& _flow) :
1.790 + Parent(), capacity(&_capacity), flow(&_flow),
1.791 + forward_filter(_graph, _capacity, _flow),
1.792 + backward_filter(_graph, _capacity, _flow) {
1.793 + Parent::setGraph(_graph);
1.794 + Parent::setForwardFilterMap(forward_filter);
1.795 + Parent::setBackwardFilterMap(backward_filter);
1.796 + }
1.797 +
1.798 + // bool forward(const Parent::Edge& e) const { return Parent::forward(e); }
1.799 + //bool backward(const Edge& e) const { return e.backward; }
1.800 +
1.801 + void augment(const typename Parent::Edge& e, Number a) const {
1.802 + if (Parent::forward(e))
1.803 +// flow->set(e.out, flow->get(e.out)+a);
1.804 + flow->set(e, (*flow)[e]+a);
1.805 + else
1.806 + //flow->set(e.in, flow->get(e.in)-a);
1.807 + flow->set(e, (*flow)[e]-a);
1.808 + }
1.809 +
1.810 + Number resCap(const typename Parent::Edge& e) const {
1.811 + if (Parent::forward(e))
1.812 +// return (capacity->get(e.out)-flow->get(e.out));
1.813 + return ((*capacity)[e]-(*flow)[e]);
1.814 + else
1.815 +// return (flow->get(e.in));
1.816 + return ((*flow)[e]);
1.817 + }
1.818 +
1.819 + };
1.820 +
1.821 +
1.822 +
1.823 +
1.824 +// /// An experiment for ResGraphWrapper.
1.825 +// template<typename Graph, typename Number,
1.826 +// typename CapacityMap, typename FlowMap>
1.827 +// class ExpResGraphWrapper :
1.828 +// public SubGraphWrapper< BidirGraphWrapper<Graph>,
1.829 +// ConstMap<typename BidirGraphWrapper<Graph>::Node,
1.830 +// bool>,
1.831 +// EdgeFilter< BidirGraphWrapper<Graph>,
1.832 +// CapacityMap, FlowMap> > {
1.833 +// public:
1.834 +// typedef SubGraphWrapper< BidirGraphWrapper<Graph>,
1.835 +// ConstMap<typename BidirGraphWrapper<Graph>::Node,
1.836 +// bool>,
1.837 +// EdgeFilter< BidirGraphWrapper<Graph>,
1.838 +// CapacityMap, FlowMap> > Parent;
1.839 +// protected:
1.840 +// const CapacityMap* capacity;
1.841 +// FlowMap* flow;
1.842 +// BidirGraphWrapper<Graph> bidir_graph;
1.843 +// ConstMap<typename BidirGraphWrapper<Graph>::Node, bool> node_filter;
1.844 +// EdgeFilter< BidirGraphWrapper<Graph>, CapacityMap, FlowMap> edge_filter;
1.845 +// public:
1.846 +// ExpResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1.847 +// FlowMap& _flow) :
1.848 +// Parent(), capacity(&_capacity), flow(&_flow),
1.849 +// bidir_graph(_graph),
1.850 +// node_filter(true),
1.851 +// edge_filter(bidir_graph, *capacity, *flow) {
1.852 +// Parent::setGraph(bidir_graph);
1.853 +// Parent::setNodeFilterMap(node_filter);
1.854 +// Parent::setEdgeFilterMap(edge_filter);
1.855 +// }
1.856 +
1.857 +// // bool forward(const Parent::Edge& e) const { return Parent::forward(e); }
1.858 +// //bool backward(const Edge& e) const { return e.backward; }
1.859 +
1.860 +// void augment(const typename Parent::Edge& e, Number a) const {
1.861 +// if (Parent::forward(e))
1.862 +// // flow->set(e.out, flow->get(e.out)+a);
1.863 +// flow->set(e, (*flow)[e]+a);
1.864 +// else
1.865 +// // flow->set(e.in, flow->get(e.in)-a);
1.866 +// flow->set(e, (*flow)[e]-a);
1.867 +// }
1.868 +
1.869 +// Number resCap(const typename Parent::Edge& e) const {
1.870 +// if (Parent::forward(e))
1.871 +// // return (capacity->get(e.out)-flow->get(e.out));
1.872 +// return ((*capacity)[e]-(*flow)[e]);
1.873 +// else
1.874 +// // return (flow->get(e.in));
1.875 +// return ((*flow)[e]);
1.876 +// }
1.877 +
1.878 +// };
1.879 +
1.880 +
1.881 +
1.882 /// A wrapper for composing the residual graph for directed flow and circulation problems.
1.883
1.884 /// A wrapper for composing the residual graph for directed flow and circulation problems.
1.885 template<typename Graph, typename Number,
1.886 typename CapacityMap, typename FlowMap>
1.887 class ResGraphWrapper : public GraphWrapper<Graph> {
1.888 + public:
1.889 + typedef GraphWrapper<Graph> Parent;
1.890 protected:
1.891 const CapacityMap* capacity;
1.892 FlowMap* flow;
1.893 @@ -1283,6 +1856,8 @@
1.894 ///\author Marton Makai
1.895 template<typename Graph, typename FirstOutEdgesMap>
1.896 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1.897 + public:
1.898 + typedef GraphWrapper<Graph> Parent;
1.899 protected:
1.900 FirstOutEdgesMap* first_out_edges;
1.901 public:
2.1 --- a/src/work/jacint/max_flow.h Thu May 20 09:42:31 2004 +0000
2.2 +++ b/src/work/jacint/max_flow.h Thu May 20 15:40:59 2004 +0000
2.3 @@ -63,7 +63,8 @@
2.4 const CapMap* capacity;
2.5 FlowMap* flow;
2.6 int n; //the number of nodes of G
2.7 - typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
2.8 + // typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
2.9 + typedef ExpResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
2.10 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
2.11 typedef typename ResGW::Edge ResGWEdge;
2.12 //typedef typename ResGW::template NodeMap<bool> ReachedMap;
2.13 @@ -139,7 +140,10 @@
2.14 TrickyReachedMap(IntMap& _map, int& _number_of_augmentations) :
2.15 map(&_map), number_of_augmentations(&_number_of_augmentations) { }
2.16 void set(const Node& n, bool b) {
2.17 - map->set(n, *number_of_augmentations);
2.18 + if (b)
2.19 + map->set(n, *number_of_augmentations);
2.20 + else
2.21 + map->set(n, *number_of_augmentations-1);
2.22 }
2.23 bool operator[](const Node& n) const {
2.24 return (*map)[n]==*number_of_augmentations;
2.25 @@ -941,8 +945,8 @@
2.26 bool _augment=false;
2.27
2.28 if (status!=AFTER_AUGMENTING) {
2.29 - FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, -1);
2.30 - number_of_augmentations=0;
2.31 + FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 3*n);
2.32 + number_of_augmentations=3*n+1;
2.33 } else {
2.34 ++number_of_augmentations;
2.35 }
3.1 --- a/src/work/marci/bfs_dfs.h Thu May 20 09:42:31 2004 +0000
3.2 +++ b/src/work/marci/bfs_dfs.h Thu May 20 15:40:59 2004 +0000
3.3 @@ -20,7 +20,7 @@
3.4
3.5 /// Bfs searches for the nodes wich are not marked in
3.6 /// \c reached_map
3.7 - /// Reached have to work as read-write bool Node-map.
3.8 + /// Reached have to be a read-write bool node-map.
3.9 /// \ingroup galgs
3.10 template <typename Graph, /*typename OutEdgeIt,*/
3.11 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
3.12 @@ -36,13 +36,15 @@
3.13 bool own_reached_map;
3.14 public:
3.15 /// In that constructor \c _reached have to be a reference
3.16 - /// for a bool Node-map. The algorithm will search in a bfs order for
3.17 - /// the nodes which are \c false initially
3.18 + /// for a bool bode-map. The algorithm will search for the
3.19 + /// initially \c false nodes
3.20 + /// in a bfs order.
3.21 BfsIterator(const Graph& _graph, ReachedMap& _reached) :
3.22 graph(&_graph), reached(_reached),
3.23 own_reached_map(false) { }
3.24 /// The same as above, but the map storing the reached nodes
3.25 /// is constructed dynamically to everywhere false.
3.26 + /// \deprecated
3.27 BfsIterator(const Graph& _graph) :
3.28 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
3.29 own_reached_map(true) { }
3.30 @@ -121,16 +123,18 @@
3.31 /// \pre The actual edge have to be valid.
3.32 Node bNode() const { return graph->bNode(actual_edge); }
3.33 /// Guess what?
3.34 + /// \deprecated
3.35 const ReachedMap& getReachedMap() const { return reached; }
3.36 /// Guess what?
3.37 + /// \deprecated
3.38 const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
3.39 };
3.40
3.41 /// Bfs searches for the nodes wich are not marked in
3.42 /// \c reached_map
3.43 /// Reached have to work as a read-write bool Node-map,
3.44 - /// Pred is a write Edge Node-map and
3.45 - /// Dist is a read-write Node-map of integral value, have to be.
3.46 + /// Pred is a write edge node-map and
3.47 + /// Dist is a read-write node-map of integral value, have to be.
3.48 /// \ingroup galgs
3.49 template <typename Graph,
3.50 typename ReachedMap=typename Graph::template NodeMap<bool>,
3.51 @@ -179,8 +183,10 @@
3.52 return *this;
3.53 }
3.54 /// Guess what?
3.55 + /// \deprecated
3.56 const PredMap& getPredMap() const { return pred; }
3.57 /// Guess what?
3.58 + /// \deprecated
3.59 const DistMap& getDistMap() const { return dist; }
3.60 };
3.61
3.62 @@ -203,7 +209,7 @@
3.63 bool own_reached_map;
3.64 public:
3.65 /// In that constructor \c _reached have to be a reference
3.66 - /// for a bool Node-map. The algorithm will search in a dfs order for
3.67 + /// for a bool node-map. The algorithm will search in a dfs order for
3.68 /// the nodes which are \c false initially
3.69 DfsIterator(const Graph& _graph, ReachedMap& _reached) :
3.70 graph(&_graph), reached(_reached),
3.71 @@ -265,15 +271,17 @@
3.72 /// \pre The actual edge have to be valid.
3.73 Node bNode() const { return graph->bNode(actual_edge); }
3.74 /// Guess what?
3.75 + /// \deprecated
3.76 const ReachedMap& getReachedMap() const { return reached; }
3.77 /// Guess what?
3.78 + /// \deprecated
3.79 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
3.80 };
3.81
3.82 /// Dfs searches for the nodes wich are not marked in
3.83 /// \c reached_map
3.84 - /// Reached is a read-write bool Node-map,
3.85 - /// Pred is a write Node-map, have to be.
3.86 + /// Reached is a read-write bool node-map,
3.87 + /// Pred is a write node-map, have to be.
3.88 /// \ingroup galgs
3.89 template <typename Graph,
3.90 typename ReachedMap=typename Graph::template NodeMap<bool>,
3.91 @@ -318,6 +326,7 @@
3.92 return *this;
3.93 }
3.94 /// Guess what?
3.95 + /// \deprecated
3.96 const PredMap& getPredMap() const { return pred; }
3.97 };
3.98
4.1 --- a/src/work/marci/leda/leda_graph_wrapper.h Thu May 20 09:42:31 2004 +0000
4.2 +++ b/src/work/marci/leda/leda_graph_wrapper.h Thu May 20 15:40:59 2004 +0000
4.3 @@ -33,10 +33,11 @@
4.4 LedaGraphWrapper() : l_graph(0) { }
4.5 void setGraph(Graph& _l_graph) { l_graph=&_l_graph; }
4.6 public:
4.7 -
4.8 - //LedaGraphWrapper() { }
4.9 +
4.10 + /// Constructor for wrapping LEDA graphs.
4.11 LedaGraphWrapper(Graph& _l_graph) : l_graph(&_l_graph) { }
4.12 - LedaGraphWrapper(const LedaGraphWrapper &G) : l_graph(G.l_graph) { }
4.13 + /// Copy constructor
4.14 + LedaGraphWrapper(const LedaGraphWrapper &g) : l_graph(g.l_graph) { }
4.15
4.16 template <typename T> class NodeMap;
4.17 template <typename T> class EdgeMap;
4.18 @@ -50,7 +51,7 @@
4.19 class OutEdgeIt;
4.20 class InEdgeIt;
4.21
4.22 - /// The base type of the node iterators.
4.23 + /// Trivial node-iterator
4.24 class Node {
4.25 friend class LedaGraphWrapper<Graph>;
4.26 //friend class Edge;
4.27 @@ -65,7 +66,7 @@
4.28 public:
4.29 /// @warning The default constructor sets the iterator
4.30 /// to an undefined value.
4.31 - Node() {} //FIXME
4.32 + Node() { } //FIXME
4.33 /// Initialize the iterator to be invalid
4.34 Node(Invalid) : l_n(0) { }
4.35 //Node(const Node &) {}
4.36 @@ -79,15 +80,15 @@
4.37 public:
4.38 /// @warning The default constructor sets the iterator
4.39 /// to an undefined value.
4.40 - NodeIt() {} //FIXME
4.41 + NodeIt() { } //FIXME
4.42 /// Initialize the iterator to be invalid
4.43 - NodeIt(Invalid i) : Node(i) {}
4.44 + NodeIt(Invalid i) : Node(i) { }
4.45 /// Sets the iterator to the first node of \c G.
4.46 NodeIt(const LedaGraphWrapper &G) : Node(G.l_graph->first_node()) { }
4.47 //NodeIt(const NodeIt &) {} //FIXME
4.48 };
4.49
4.50 - /// The base type of the edge iterators.
4.51 + /// Trivial edge-iterator.
4.52 class Edge {
4.53 friend class LedaGraphWrapper;
4.54 protected:
4.55 @@ -98,24 +99,23 @@
4.56 public:
4.57 /// @warning The default constructor sets the iterator
4.58 /// to an undefined value.
4.59 - Edge() {} //FIXME
4.60 + Edge() { } //FIXME
4.61 /// Initialize the iterator to be invalid
4.62 - Edge(Invalid) : l_e(0) {}
4.63 + Edge(Invalid) : l_e(0) { }
4.64 //Edge(const Edge &) {}
4.65 bool operator==(Edge e) const { return l_e==e.l_e; } //FIXME
4.66 bool operator!=(Edge e) const { return l_e!=e.l_e; } //FIXME
4.67 operator leda_edge () { return l_e; }
4.68 };
4.69
4.70 - /// This iterator goes trought the outgoing edges of a certain graph.
4.71 -
4.72 + /// This iterator goes trought the outgoing edges of a certain node.
4.73 class OutEdgeIt : public Edge {
4.74 public:
4.75 /// @warning The default constructor sets the iterator
4.76 /// to an undefined value.
4.77 - OutEdgeIt() {}
4.78 + OutEdgeIt() { }
4.79 /// Initialize the iterator to be invalid
4.80 - OutEdgeIt(Invalid i) : Edge(i) {}
4.81 + OutEdgeIt(Invalid i) : Edge(i) { }
4.82 /// This constructor sets the iterator to first outgoing edge.
4.83
4.84 /// This constructor set the iterator to the first outgoing edge of
4.85 @@ -125,29 +125,32 @@
4.86 OutEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G.l_graph->first_adj_edge(n.l_n)) { }
4.87 };
4.88
4.89 + /// This iterator goes trought the incoming edges of a certain node.
4.90 class InEdgeIt : public Edge {
4.91 public:
4.92 /// @warning The default constructor sets the iterator
4.93 /// to an undefined value.
4.94 - InEdgeIt() {}
4.95 + InEdgeIt() { }
4.96 /// Initialize the iterator to be invalid
4.97 - InEdgeIt(Invalid i) : Edge(i) {}
4.98 + InEdgeIt(Invalid i) : Edge(i) { }
4.99 InEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G.l_graph->first_in_edge(n.l_n)) { }
4.100 };
4.101
4.102 // class SymEdgeIt : public Edge {};
4.103 +
4.104 + /// This iterator goes trought the edges of the graph.
4.105 class EdgeIt : public Edge {
4.106 public:
4.107 /// @warning The default constructor sets the iterator
4.108 /// to an undefined value.
4.109 - EdgeIt() {}
4.110 + EdgeIt() { }
4.111 /// Initialize the iterator to be invalid
4.112 - EdgeIt(Invalid i) : Edge(i) {}
4.113 + EdgeIt(Invalid i) : Edge(i) { }
4.114 EdgeIt(const LedaGraphWrapper & G) : Edge(G.l_graph->first_edge()) { }
4.115 };
4.116
4.117 /// First node of the graph.
4.118 -
4.119 + ///
4.120 /// \post \c i and the return value will be the first node.
4.121 ///
4.122 NodeIt &first(NodeIt &i) const { i=NodeIt(*this); return i; }
4.123 @@ -163,7 +166,7 @@
4.124 return i;
4.125 }
4.126 // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
4.127 - /// The first edge of the Graph.
4.128 + /// The first edge of the graph.
4.129 EdgeIt &first(EdgeIt &i) const {
4.130 i=EdgeIt(*this);
4.131 return i; }
4.132 @@ -253,7 +256,7 @@
4.133 int nodeNum() const { return l_graph->number_of_nodes(); }
4.134 int edgeNum() const { return l_graph->number_of_edges(); }
4.135
4.136 - ///Read/write map from the nodes to type \c T.
4.137 + /// Read/write map from the nodes to type \c T.
4.138 template<typename T> class NodeMap
4.139 {
4.140 leda_node_map<T> leda_stuff;
4.141 @@ -273,7 +276,7 @@
4.142 //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); } //FIXME: Is it necessary
4.143 };
4.144
4.145 - ///Read/write map from the edges to type \c T.
4.146 + /// Read/write map from the edges to type \c T.
4.147 template<typename T> class EdgeMap
4.148 {
4.149 leda_edge_map<T> leda_stuff;
4.150 @@ -294,20 +297,21 @@
4.151 };
4.152
4.153
4.154 - ///Read/write map from the nodes to type \c T.
4.155 + /// This class is to wrap existing
4.156 + /// LEDA node-maps to HUGO ones.
4.157 template<typename T> class NodeMapWrapper
4.158 {
4.159 - leda_node_map<T>* leda_stuff;
4.160 + leda_node_array<T>* leda_stuff;
4.161 public:
4.162 typedef T ValueType;
4.163 typedef Node KeyType;
4.164
4.165 - NodeMapWrapper(leda_node_map<T>& _leda_stuff) :
4.166 + NodeMapWrapper(leda_node_array<T>& _leda_stuff) :
4.167 leda_stuff(&_leda_stuff) { }
4.168 //NodeMap(leda_node_map& &G, T t) : leda_stuff(*(G.l_graph), t) {}
4.169
4.170 void set(Node i, T t) { (*leda_stuff)[i.l_n]=t; }
4.171 - T get(Node i) const { return (*leda_stuff)[i.l_n]; } //FIXME: Is it necessary
4.172 + //T get(Node i) const { return (*leda_stuff)[i.l_n]; } //FIXME: Is it necessary
4.173 T &operator[](Node i) { return (*leda_stuff)[i.l_n]; }
4.174 const T &operator[](Node i) const { return (*leda_stuff)[i.l_n]; }
4.175
4.176 @@ -315,20 +319,21 @@
4.177 //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); } //FIXME: Is it necessary
4.178 };
4.179
4.180 - ///Read/write map from the edges to type \c T.
4.181 + /// This class is to wrap existing
4.182 + /// LEDA edge-maps to HUGO ones.
4.183 template<typename T> class EdgeMapWrapper
4.184 {
4.185 - leda_edge_map<T>* leda_stuff;
4.186 + leda_edge_array<T>* leda_stuff;
4.187 public:
4.188 typedef T ValueType;
4.189 typedef Edge KeyType;
4.190
4.191 - EdgeMapWrapper(leda_edge_map<T>& _leda_stuff) :
4.192 + EdgeMapWrapper(leda_edge_array<T>& _leda_stuff) :
4.193 leda_stuff(_leda_stuff) { }
4.194 //EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}
4.195
4.196 void set(Edge i, T t) { (*leda_stuff)[i.l_e]=t; }
4.197 - T get(Edge i) const { return (*leda_stuff)[i.l_e]; } //FIXME: Is it necessary
4.198 + //T get(Edge i) const { return (*leda_stuff)[i.l_e]; } //FIXME: Is it necessary
4.199 T &operator[](Edge i) { return (*leda_stuff)[i.l_e]; }
4.200 const T &operator[](Edge i) const { return (*leda_stuff)[i.l_e]; }
4.201
4.202 @@ -336,6 +341,26 @@
4.203 //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); } //FIXME: Is it necessary
4.204 };
4.205
4.206 + /// This class is used for access node-data of
4.207 + /// LEDA parametrized graphs.
4.208 + template<typename T>
4.209 + class NodeDataMap : public NodeMapWrapper<T>
4.210 + {
4.211 + public:
4.212 + NodeDataMap(LedaGraphWrapper<Graph>& LGW) :
4.213 + NodeMapWrapper<T>(*(LGW._g_graph).node_data()) { }
4.214 + };
4.215 +
4.216 + /// This class is used for access edge-data of
4.217 + /// LEDA parametrized graphs.
4.218 + template<typename T>
4.219 + class EdgeDataMap : public EdgeMapWrapper<T>
4.220 + {
4.221 + public:
4.222 + EdgeDataMap(LedaGraphWrapper<Graph>& LGW) :
4.223 + EdgeMapWrapper<T>(*(LGW._g_graph).edge_data()) { }
4.224 + };
4.225 +
4.226 };
4.227
4.228