1.1 --- a/src/include/dijkstra.h Fri Apr 02 12:10:11 2004 +0000
1.2 +++ b/src/include/dijkstra.h Fri Apr 02 14:53:05 2004 +0000
1.3 @@ -205,7 +205,8 @@
1.4 heap.pop();
1.5 distance.set(v, oldvalue);
1.6
1.7 - for(OutEdgeIt e(G,v); G.valid(e); G.next(e)) {
1.8 + for(OutEdgeIt e = G.template first<OutEdgeIt>(v);
1.9 + G.valid(e); G.next(e)) {
1.10 Node w=G.head(e);
1.11
1.12 switch(heap.state(w)) {
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/athos/graph_wrapper.h Fri Apr 02 14:53:05 2004 +0000
2.3 @@ -0,0 +1,1708 @@
2.4 +// -*- c++ -*-
2.5 +#ifndef HUGO_GRAPH_WRAPPER_H
2.6 +#define HUGO_GRAPH_WRAPPER_H
2.7 +
2.8 +#include <invalid.h>
2.9 +
2.10 +namespace hugo {
2.11 +
2.12 + template<typename Graph>
2.13 + class TrivGraphWrapper {
2.14 + protected:
2.15 + Graph* graph;
2.16 +
2.17 + public:
2.18 + typedef Graph BaseGraph;
2.19 +
2.20 + typedef typename Graph::Node Node;
2.21 + class NodeIt : public Graph::NodeIt {
2.22 + public:
2.23 + NodeIt() { }
2.24 + NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
2.25 + NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
2.26 + NodeIt(const TrivGraphWrapper<Graph>& _G) :
2.27 + Graph::NodeIt(*(_G.graph)) { }
2.28 + };
2.29 + typedef typename Graph::Edge Edge;
2.30 + //typedef typename Graph::OutEdgeIt OutEdgeIt;
2.31 + class OutEdgeIt : public Graph::OutEdgeIt {
2.32 + public:
2.33 + OutEdgeIt() { }
2.34 + OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
2.35 + OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
2.36 + OutEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :
2.37 + Graph::OutEdgeIt(*(_G.graph), n) { }
2.38 + };
2.39 + //typedef typename Graph::InEdgeIt InEdgeIt;
2.40 + class InEdgeIt : public Graph::InEdgeIt {
2.41 + public:
2.42 + InEdgeIt() { }
2.43 + InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
2.44 + InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
2.45 + InEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :
2.46 + Graph::InEdgeIt(*(_G.graph), n) { }
2.47 + };
2.48 + //typedef typename Graph::SymEdgeIt SymEdgeIt;
2.49 + //typedef typename Graph::EdgeIt EdgeIt;
2.50 + class EdgeIt : public Graph::EdgeIt {
2.51 + public:
2.52 + EdgeIt() { }
2.53 + EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
2.54 + EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
2.55 + EdgeIt(const TrivGraphWrapper<Graph>& _G) :
2.56 + Graph::EdgeIt(*(_G.graph)) { }
2.57 + };
2.58 +
2.59 + //TrivGraphWrapper() : graph(0) { }
2.60 + TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
2.61 +
2.62 +// void setGraph(Graph& _graph) { graph = &_graph; }
2.63 +// Graph& getGraph() const { return (*graph); }
2.64 +
2.65 + NodeIt& first(NodeIt& i) const {
2.66 + i=NodeIt(*this);
2.67 + return i;
2.68 + }
2.69 + EdgeIt& first(EdgeIt& i) const {
2.70 + i=EdgeIt(*this);
2.71 + return i;
2.72 + }
2.73 +// template<typename I> I& first(I& i) const {
2.74 +// //return graph->first(i);
2.75 +// i=I(*this);
2.76 +// return i;
2.77 +// }
2.78 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
2.79 + i=OutEdgeIt(*this, p);
2.80 + return i;
2.81 + }
2.82 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
2.83 + i=InEdgeIt(*this, p);
2.84 + return i;
2.85 + }
2.86 +// template<typename I, typename P> I& first(I& i, const P& p) const {
2.87 +// //return graph->first(i, p);
2.88 +// i=I(*this, p);
2.89 +// return i;
2.90 +// }
2.91 +
2.92 +// template<typename I> I getNext(const I& i) const {
2.93 +// return graph->getNext(i); }
2.94 + template<typename I> I& next(I &i) const { graph->next(i); return i; }
2.95 +
2.96 + template< typename It > It first() const {
2.97 + It e; first(e); return e; }
2.98 +
2.99 + template< typename It > It first(const Node& v) const {
2.100 + It e; first(e, v); return e; }
2.101 +
2.102 + Node head(const Edge& e) const { return graph->head(e); }
2.103 + Node tail(const Edge& e) const { return graph->tail(e); }
2.104 +
2.105 + template<typename I> bool valid(const I& i) const
2.106 + { return graph->valid(i); }
2.107 +
2.108 + //template<typename I> void setInvalid(const I &i);
2.109 + //{ return graph->setInvalid(i); }
2.110 +
2.111 + int nodeNum() const { return graph->nodeNum(); }
2.112 + int edgeNum() const { return graph->edgeNum(); }
2.113 +
2.114 + template<typename I> Node aNode(const I& e) const {
2.115 + return graph->aNode(e); }
2.116 + template<typename I> Node bNode(const I& e) const {
2.117 + return graph->bNode(e); }
2.118 +
2.119 + Node addNode() const { return graph->addNode(); }
2.120 + Edge addEdge(const Node& tail, const Node& head) const {
2.121 + return graph->addEdge(tail, head); }
2.122 +
2.123 + template<typename I> void erase(const I& i) const { graph->erase(i); }
2.124 +
2.125 + void clear() const { graph->clear(); }
2.126 +
2.127 + template<typename T> class NodeMap : public Graph::NodeMap<T> {
2.128 + public:
2.129 + NodeMap(const TrivGraphWrapper<Graph>& _G) :
2.130 + Graph::NodeMap<T>(*(_G.graph)) { }
2.131 + NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :
2.132 + Graph::NodeMap<T>(*(_G.graph), a) { }
2.133 + };
2.134 +
2.135 + template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
2.136 + public:
2.137 + EdgeMap(const TrivGraphWrapper<Graph>& _G) :
2.138 + Graph::EdgeMap<T>(*(_G.graph)) { }
2.139 + EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :
2.140 + Graph::EdgeMap<T>(*(_G.graph), a) { }
2.141 + };
2.142 +
2.143 + template<typename Map, typename T> class NodeMapWrapper {
2.144 + protected:
2.145 + Map* map;
2.146 + public:
2.147 + NodeMapWrapper(Map& _map) : map(&_map) { }
2.148 + //template<typename T>
2.149 + void set(Node n, T a) { map->set(n, a); }
2.150 + //template<typename T>
2.151 + T get(Node n) const { return map->get(n); }
2.152 + };
2.153 +
2.154 + template<typename Map, typename T> class EdgeMapWrapper {
2.155 + protected:
2.156 + Map* map;
2.157 + public:
2.158 + EdgeMapWrapper(Map& _map) : map(&_map) { }
2.159 + //template<typename T>
2.160 + void set(Edge n, T a) { map->set(n, a); }
2.161 + //template<typename T>
2.162 + T get(Edge n) const { return map->get(n); }
2.163 + };
2.164 + };
2.165 +
2.166 + template<typename GraphWrapper>
2.167 + class GraphWrapperSkeleton {
2.168 + protected:
2.169 + GraphWrapper gw;
2.170 +
2.171 + public:
2.172 + //typedef typename GraphWrapper::BaseGraph BaseGraph;
2.173 +
2.174 +// typedef typename GraphWrapper::Node Node;
2.175 +// typedef typename GraphWrapper::NodeIt NodeIt;
2.176 +
2.177 +// typedef typename GraphWrapper::Edge Edge;
2.178 +// typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
2.179 +// typedef typename GraphWrapper::InEdgeIt InEdgeIt;
2.180 +// //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;
2.181 +// typedef typename GraphWrapper::EdgeIt EdgeIt;
2.182 +
2.183 + typedef typename GraphWrapper::Node Node;
2.184 + class NodeIt : public GraphWrapper::NodeIt {
2.185 + public:
2.186 + NodeIt() { }
2.187 + NodeIt(const typename GraphWrapper::NodeIt& n) :
2.188 + GraphWrapper::NodeIt(n) { }
2.189 + NodeIt(const Invalid& i) : GraphWrapper::NodeIt(i) { }
2.190 + NodeIt(const GraphWrapperSkeleton<GraphWrapper>& _G) :
2.191 + GraphWrapper::NodeIt(_G.gw) { }
2.192 + };
2.193 + typedef typename GraphWrapper::Edge Edge;
2.194 + //typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
2.195 + class OutEdgeIt : public GraphWrapper::OutEdgeIt {
2.196 + public:
2.197 + OutEdgeIt() { }
2.198 + OutEdgeIt(const typename GraphWrapper::OutEdgeIt& e) :
2.199 + GraphWrapper::OutEdgeIt(e) { }
2.200 + OutEdgeIt(const Invalid& i) : GraphWrapper::OutEdgeIt(i) { }
2.201 + OutEdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G, const Node& n) :
2.202 + GraphWrapper::OutEdgeIt(_G.gw, n) { }
2.203 + };
2.204 + //typedef typename GraphWrapper::InEdgeIt InEdgeIt;
2.205 + class InEdgeIt : public GraphWrapper::InEdgeIt {
2.206 + public:
2.207 + InEdgeIt() { }
2.208 + InEdgeIt(const typename GraphWrapper::InEdgeIt& e) :
2.209 + GraphWrapper::InEdgeIt(e) { }
2.210 + InEdgeIt(const Invalid& i) : GraphWrapper::InEdgeIt(i) { }
2.211 + InEdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G, const Node& n) :
2.212 + GraphWrapper::InEdgeIt(_G.gw, n) { }
2.213 + };
2.214 + //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;
2.215 + //typedef typename GraphWrapper::EdgeIt EdgeIt;
2.216 + class EdgeIt : public GraphWrapper::EdgeIt {
2.217 + public:
2.218 + EdgeIt() { }
2.219 + EdgeIt(const typename GraphWrapper::EdgeIt& e) :
2.220 + GraphWrapper::EdgeIt(e) { }
2.221 + EdgeIt(const Invalid& i) : GraphWrapper::EdgeIt(i) { }
2.222 + EdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G) :
2.223 + GraphWrapper::EdgeIt(_G.gw) { }
2.224 + };
2.225 +
2.226 +
2.227 + //GraphWrapperSkeleton() : gw() { }
2.228 + GraphWrapperSkeleton(GraphWrapper _gw) : gw(_gw) { }
2.229 +
2.230 + //void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); }
2.231 + //BaseGraph& getGraph() const { return gw.getGraph(); }
2.232 +
2.233 + template<typename I> I& first(I& i) const {
2.234 + i=I(*this);
2.235 + return i;
2.236 + }
2.237 + template<typename I, typename P> I& first(I& i, const P& p) const {
2.238 + i=I(*this, p);
2.239 + return i;
2.240 + }
2.241 +
2.242 +// template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
2.243 + template<typename I> I& next(I &i) const { gw.next(i); return i; }
2.244 +
2.245 + template< typename It > It first() const {
2.246 + It e; this->first(e); return e; }
2.247 +
2.248 + template< typename It > It first(const Node& v) const {
2.249 + It e; this->first(e, v); return e; }
2.250 +
2.251 + Node head(const Edge& e) const { return gw.head(e); }
2.252 + Node tail(const Edge& e) const { return gw.tail(e); }
2.253 +
2.254 + template<typename I> bool valid(const I& i) const { return gw.valid(i); }
2.255 +
2.256 + //template<typename I> void setInvalid(const I &i);
2.257 + //{ return graph->setInvalid(i); }
2.258 +
2.259 + int nodeNum() const { return gw.nodeNum(); }
2.260 + int edgeNum() const { return gw.edgeNum(); }
2.261 +
2.262 + template<typename I> Node aNode(const I& e) const { return gw.aNode(e); }
2.263 + template<typename I> Node bNode(const I& e) const { return gw.bNode(e); }
2.264 +
2.265 + Node addNode() const { return gw.addNode(); }
2.266 + Edge addEdge(const Node& tail, const Node& head) const {
2.267 + return gw.addEdge(tail, head); }
2.268 +
2.269 + template<typename I> void erase(const I& i) const { gw.erase(i); }
2.270 +
2.271 + void clear() const { gw.clear(); }
2.272 +
2.273 + template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
2.274 + public:
2.275 + NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) :
2.276 + GraphWrapper::NodeMap<T>(_G.gw) { }
2.277 + NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) :
2.278 + GraphWrapper::NodeMap<T>(_G.gw, a) { }
2.279 + };
2.280 +
2.281 + template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
2.282 + public:
2.283 + EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) :
2.284 + GraphWrapper::EdgeMap<T>(_G.gw) { }
2.285 + EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) :
2.286 + GraphWrapper::EdgeMap<T>(_G.gw, a) { }
2.287 + };
2.288 + };
2.289 +
2.290 +// template<typename Graph>
2.291 +// class RevGraphWrapper
2.292 +// {
2.293 +// protected:
2.294 +// Graph* graph;
2.295 +
2.296 +// public:
2.297 +// typedef Graph BaseGraph;
2.298 +
2.299 +// typedef typename Graph::Node Node;
2.300 +// typedef typename Graph::NodeIt NodeIt;
2.301 +
2.302 +// typedef typename Graph::Edge Edge;
2.303 +// typedef typename Graph::OutEdgeIt InEdgeIt;
2.304 +// typedef typename Graph::InEdgeIt OutEdgeIt;
2.305 +// //typedef typename Graph::SymEdgeIt SymEdgeIt;
2.306 +// typedef typename Graph::EdgeIt EdgeIt;
2.307 +
2.308 +// //RevGraphWrapper() : graph(0) { }
2.309 +// RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
2.310 +
2.311 +// void setGraph(Graph& _graph) { graph = &_graph; }
2.312 +// Graph& getGraph() const { return (*graph); }
2.313 +
2.314 +// template<typename I> I& first(I& i) const { return graph->first(i); }
2.315 +// template<typename I, typename P> I& first(I& i, const P& p) const {
2.316 +// return graph->first(i, p); }
2.317 +
2.318 +// template<typename I> I getNext(const I& i) const {
2.319 +// return graph->getNext(i); }
2.320 +// template<typename I> I& next(I &i) const { return graph->next(i); }
2.321 +
2.322 +// template< typename It > It first() const {
2.323 +// It e; first(e); return e; }
2.324 +
2.325 +// template< typename It > It first(const Node& v) const {
2.326 +// It e; first(e, v); return e; }
2.327 +
2.328 +// Node head(const Edge& e) const { return graph->tail(e); }
2.329 +// Node tail(const Edge& e) const { return graph->head(e); }
2.330 +
2.331 +// template<typename I> bool valid(const I& i) const
2.332 +// { return graph->valid(i); }
2.333 +
2.334 +// //template<typename I> void setInvalid(const I &i);
2.335 +// //{ return graph->setInvalid(i); }
2.336 +
2.337 +// template<typename I> Node aNode(const I& e) const {
2.338 +// return graph->aNode(e); }
2.339 +// template<typename I> Node bNode(const I& e) const {
2.340 +// return graph->bNode(e); }
2.341 +
2.342 +// Node addNode() const { return graph->addNode(); }
2.343 +// Edge addEdge(const Node& tail, const Node& head) const {
2.344 +// return graph->addEdge(tail, head); }
2.345 +
2.346 +// int nodeNum() const { return graph->nodeNum(); }
2.347 +// int edgeNum() const { return graph->edgeNum(); }
2.348 +
2.349 +// template<typename I> void erase(const I& i) const { graph->erase(i); }
2.350 +
2.351 +// void clear() const { graph->clear(); }
2.352 +
2.353 +// template<typename T> class NodeMap : public Graph::NodeMap<T> {
2.354 +// public:
2.355 +// NodeMap(const RevGraphWrapper<Graph>& _G) :
2.356 +// Graph::NodeMap<T>(_G.getGraph()) { }
2.357 +// NodeMap(const RevGraphWrapper<Graph>& _G, T a) :
2.358 +// Graph::NodeMap<T>(_G.getGraph(), a) { }
2.359 +// };
2.360 +
2.361 +// template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
2.362 +// public:
2.363 +// EdgeMap(const RevGraphWrapper<Graph>& _G) :
2.364 +// Graph::EdgeMap<T>(_G.getGraph()) { }
2.365 +// EdgeMap(const RevGraphWrapper<Graph>& _G, T a) :
2.366 +// Graph::EdgeMap<T>(_G.getGraph(), a) { }
2.367 +// };
2.368 +// };
2.369 +
2.370 +// template<typename /*Graph*/GraphWrapper
2.371 +// /*=typename GraphWrapperSkeleton< TrivGraphWrapper<Graph>*/ >
2.372 +// class RevGraphWrapper :
2.373 +// public GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/ {
2.374 +// protected:
2.375 +// //Graph* graph;
2.376 +
2.377 +// public:
2.378 +// //typedef Graph BaseGraph;
2.379 +
2.380 +// //typedef typename Graph::Node Node;
2.381 +// //typedef typename Graph::NodeIt NodeIt;
2.382 +
2.383 +// //typedef typename Graph::Edge Edge;
2.384 +// typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::OutEdgeIt InEdgeIt;
2.385 +// typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::InEdgeIt OutEdgeIt;
2.386 +// //typedef typename Graph::SymEdgeIt SymEdgeIt;
2.387 +// //typedef typename Graph::EdgeIt EdgeIt;
2.388 +
2.389 +// //RevGraphWrapper() : graph(0) { }
2.390 +// RevGraphWrapper(GraphWrapper _gw/*BaseGraph& _graph*/) : GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/(_gw/*TrivGraphWrapper<Graph>(_graph)*/) { }
2.391 +
2.392 +// //void setGraph(Graph& _graph) { graph = &_graph; }
2.393 +// //Graph& getGraph() const { return (*graph); }
2.394 +
2.395 +// //template<typename I> I& first(I& i) const { return graph->first(i); }
2.396 +// //template<typename I, typename P> I& first(I& i, const P& p) const {
2.397 +// // return graph->first(i, p); }
2.398 +
2.399 +// //template<typename I> I getNext(const I& i) const {
2.400 +// // return graph->getNext(i); }
2.401 +// //template<typename I> I& next(I &i) const { return graph->next(i); }
2.402 +
2.403 +// //template< typename It > It first() const {
2.404 +// // It e; first(e); return e; }
2.405 +
2.406 +// //template< typename It > It first(const Node& v) const {
2.407 +// // It e; first(e, v); return e; }
2.408 +
2.409 +// //Node head(const Edge& e) const { return graph->tail(e); }
2.410 +// //Node tail(const Edge& e) const { return graph->head(e); }
2.411 +
2.412 +// //template<typename I> bool valid(const I& i) const
2.413 +// // { return graph->valid(i); }
2.414 +
2.415 +// //template<typename I> void setInvalid(const I &i);
2.416 +// //{ return graph->setInvalid(i); }
2.417 +
2.418 +// //template<typename I> Node aNode(const I& e) const {
2.419 +// // return graph->aNode(e); }
2.420 +// //template<typename I> Node bNode(const I& e) const {
2.421 +// // return graph->bNode(e); }
2.422 +
2.423 +// //Node addNode() const { return graph->addNode(); }
2.424 +// //Edge addEdge(const Node& tail, const Node& head) const {
2.425 +// // return graph->addEdge(tail, head); }
2.426 +
2.427 +// //int nodeNum() const { return graph->nodeNum(); }
2.428 +// //int edgeNum() const { return graph->edgeNum(); }
2.429 +
2.430 +// //template<typename I> void erase(const I& i) const { graph->erase(i); }
2.431 +
2.432 +// //void clear() const { graph->clear(); }
2.433 +
2.434 +// template<typename T> class NodeMap :
2.435 +// public GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>
2.436 +// {
2.437 +// public:
2.438 +// NodeMap(const RevGraphWrapper<GraphWrapper>& _gw) :
2.439 +// GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw) { }
2.440 +// NodeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) :
2.441 +// GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw, a) { }
2.442 +// };
2.443 +
2.444 +// template<typename T> class EdgeMap :
2.445 +// public GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T> {
2.446 +// public:
2.447 +// EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw) :
2.448 +// GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw) { }
2.449 +// EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) :
2.450 +// GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw, a) { }
2.451 +// };
2.452 +// };
2.453 +
2.454 +
2.455 + template<typename GraphWrapper>
2.456 + class RevGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
2.457 + public:
2.458 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
2.459 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
2.460 + typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt InEdgeIt;
2.461 + typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt OutEdgeIt;
2.462 +
2.463 + RevGraphWrapper(GraphWrapper _gw) :
2.464 + GraphWrapperSkeleton<GraphWrapper>(_gw) { }
2.465 +
2.466 + Node head(const Edge& e) const
2.467 + { return GraphWrapperSkeleton<GraphWrapper>::tail(e); }
2.468 + Node tail(const Edge& e) const
2.469 + { return GraphWrapperSkeleton<GraphWrapper>::head(e); }
2.470 + };
2.471 +
2.472 + //Subgraph on the same node-set and partial edge-set
2.473 + template<typename GraphWrapper, typename EdgeFilterMap>
2.474 + class SubGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
2.475 + protected:
2.476 + EdgeFilterMap* filter_map;
2.477 + public:
2.478 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
2.479 + typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
2.480 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
2.481 + typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt;
2.482 + typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt;
2.483 + typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt;
2.484 +
2.485 + SubGraphWrapper(GraphWrapper _gw, EdgeFilterMap& _filter_map) :
2.486 + GraphWrapperSkeleton<GraphWrapper>(_gw), filter_map(&_filter_map) { }
2.487 +
2.488 + template<typename I> I& first(I& i) const {
2.489 + gw.first(i);
2.490 + while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
2.491 + return i;
2.492 + }
2.493 + template<typename I, typename P> I& first(I& i, const P& p) const {
2.494 + gw.first(i, p);
2.495 + while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
2.496 + return i;
2.497 + }
2.498 +
2.499 + //template<typename I> I getNext(const I& i) const {
2.500 + // return gw.getNext(i);
2.501 + //}
2.502 + template<typename I> I& next(I &i) const {
2.503 + gw.next(i);
2.504 + while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
2.505 + return i;
2.506 + }
2.507 +
2.508 + template< typename It > It first() const {
2.509 + It e; this->first(e); return e; }
2.510 +
2.511 + template< typename It > It first(const Node& v) const {
2.512 + It e; this->first(e, v); return e; }
2.513 + };
2.514 +
2.515 +// template<typename GraphWrapper>
2.516 +// class UndirGraphWrapper {
2.517 +// protected:
2.518 +// //Graph* graph;
2.519 +// GraphWrapper gw;
2.520 +
2.521 +// public:
2.522 +// typedef GraphWrapper BaseGraph;
2.523 +
2.524 +// typedef typename GraphWrapper::Node Node;
2.525 +// typedef typename GraphWrapper::NodeIt NodeIt;
2.526 +
2.527 +// //typedef typename Graph::Edge Edge;
2.528 +// //typedef typename Graph::OutEdgeIt OutEdgeIt;
2.529 +// //typedef typename Graph::InEdgeIt InEdgeIt;
2.530 +// //typedef typename Graph::SymEdgeIt SymEdgeIt;
2.531 +// //typedef typename Graph::EdgeIt EdgeIt;
2.532 +
2.533 +// //private:
2.534 +// typedef typename GraphWrapper::Edge GraphEdge;
2.535 +// typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;
2.536 +// typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;
2.537 +// //public:
2.538 +
2.539 +// //UndirGraphWrapper() : graph(0) { }
2.540 +// UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
2.541 +
2.542 +// //void setGraph(Graph& _graph) { graph = &_graph; }
2.543 +// //Graph& getGraph() const { return (*graph); }
2.544 +
2.545 +// class Edge {
2.546 +// friend class UndirGraphWrapper<GraphWrapper>;
2.547 +// bool out_or_in; //true iff out
2.548 +// GraphOutEdgeIt out;
2.549 +// GraphInEdgeIt in;
2.550 +// public:
2.551 +// Edge() : out_or_in(), out(), in() { }
2.552 +// Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
2.553 +// operator GraphEdge() const {
2.554 +// if (out_or_in) return(out); else return(in);
2.555 +// }
2.556 +// friend bool operator==(const Edge& u, const Edge& v) {
2.557 +// if (v.out_or_in)
2.558 +// return (u.out_or_in && u.out==v.out);
2.559 +// else
2.560 +// return (!u.out_or_in && u.in==v.in);
2.561 +// }
2.562 +// friend bool operator!=(const Edge& u, const Edge& v) {
2.563 +// if (v.out_or_in)
2.564 +// return (!u.out_or_in || u.out!=v.out);
2.565 +// else
2.566 +// return (u.out_or_in || u.in!=v.in);
2.567 +// }
2.568 +// };
2.569 +
2.570 +// class OutEdgeIt : public Edge {
2.571 +// friend class UndirGraphWrapper<GraphWrapper>;
2.572 +// public:
2.573 +// OutEdgeIt() : Edge() { }
2.574 +// OutEdgeIt(const Invalid& i) : Edge(i) { }
2.575 +// OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)
2.576 +// : Edge() {
2.577 +// out_or_in=true;
2.578 +// _G.gw.first(out, n);
2.579 +// if (!(_G.gw.valid(out))) {
2.580 +// out_or_in=false;
2.581 +// _G.gw.first(in, n);
2.582 +// }
2.583 +// }
2.584 +// };
2.585 +
2.586 +// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
2.587 +// e.out_or_in=true;
2.588 +// gw.first(e.out, n);
2.589 +// if (!(gw.valid(e.out))) {
2.590 +// e.out_or_in=false;
2.591 +// gw.first(e.in, n);
2.592 +// }
2.593 +// return e;
2.594 +// }
2.595 +
2.596 +// OutEdgeIt& next(OutEdgeIt& e) const {
2.597 +// if (e.out_or_in) {
2.598 +// Node n=gw.tail(e.out);
2.599 +// gw.next(e.out);
2.600 +// if (!gw.valid(e.out)) {
2.601 +// e.out_or_in=false;
2.602 +// gw.first(e.in, n);
2.603 +// }
2.604 +// } else {
2.605 +// gw.next(e.in);
2.606 +// }
2.607 +// return e;
2.608 +// }
2.609 +
2.610 +// Node aNode(const OutEdgeIt& e) const {
2.611 +// if (e.out_or_in) return gw.tail(e); else return gw.head(e); }
2.612 +// Node bNode(const OutEdgeIt& e) const {
2.613 +// if (e.out_or_in) return gw.head(e); else return gw.tail(e); }
2.614 +
2.615 +// typedef OutEdgeIt InEdgeIt;
2.616 +
2.617 +// template<typename I> I& first(I& i) const { return gw.first(i); }
2.618 +// // template<typename I, typename P> I& first(I& i, const P& p) const {
2.619 +// // return graph->first(i, p); }
2.620 +
2.621 +// template<typename I> I getNext(const I& i) const {
2.622 +// return gw.getNext(i); }
2.623 +// template<typename I> I& next(I &i) const { return gw.next(i); }
2.624 +
2.625 +// template< typename It > It first() const {
2.626 +// It e; first(e); return e; }
2.627 +
2.628 +// template< typename It > It first(const Node& v) const {
2.629 +// It e; first(e, v); return e; }
2.630 +
2.631 +// Node head(const Edge& e) const { return gw.head(e); }
2.632 +// Node tail(const Edge& e) const { return gw.tail(e); }
2.633 +
2.634 +// template<typename I> bool valid(const I& i) const
2.635 +// { return gw.valid(i); }
2.636 +
2.637 +// //template<typename I> void setInvalid(const I &i);
2.638 +// //{ return graph->setInvalid(i); }
2.639 +
2.640 +// int nodeNum() const { return gw.nodeNum(); }
2.641 +// int edgeNum() const { return gw.edgeNum(); }
2.642 +
2.643 +// // template<typename I> Node aNode(const I& e) const {
2.644 +// // return graph->aNode(e); }
2.645 +// // template<typename I> Node bNode(const I& e) const {
2.646 +// // return graph->bNode(e); }
2.647 +
2.648 +// Node addNode() const { return gw.addNode(); }
2.649 +// // FIXME: ez igy nem jo, mert nem
2.650 +// // Edge addEdge(const Node& tail, const Node& head) const {
2.651 +// // return graph->addEdge(tail, head); }
2.652 +
2.653 +// template<typename I> void erase(const I& i) const { gw.erase(i); }
2.654 +
2.655 +// void clear() const { gw.clear(); }
2.656 +
2.657 +// template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
2.658 +// public:
2.659 +// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
2.660 +// GraphWrapper::NodeMap<T>(_G.gw) { }
2.661 +// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
2.662 +// GraphWrapper::NodeMap<T>(_G.gw, a) { }
2.663 +// };
2.664 +
2.665 +// template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
2.666 +// public:
2.667 +// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
2.668 +// GraphWrapper::EdgeMap<T>(_G.gw) { }
2.669 +// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
2.670 +// GraphWrapper::EdgeMap<T>(_G.gw, a) { }
2.671 +// };
2.672 +// };
2.673 +
2.674 +
2.675 + template<typename GraphWrapper>
2.676 + class UndirGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
2.677 + protected:
2.678 +// GraphWrapper gw;
2.679 +
2.680 + public:
2.681 + //typedef GraphWrapper BaseGraph;
2.682 +
2.683 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
2.684 + typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
2.685 +
2.686 + //private:
2.687 + //FIXME ezeknek valojaban a GraphWrapper megfelelo dolgai kellene hogy
2.688 + //legyenek, at kell irni
2.689 + typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
2.690 + GraphWrapper::Edge GraphEdge;
2.691 + typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
2.692 + GraphWrapper::OutEdgeIt GraphOutEdgeIt;
2.693 + typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
2.694 + GraphWrapper::InEdgeIt GraphInEdgeIt;
2.695 + //public:
2.696 +
2.697 + //UndirGraphWrapper() : graph(0) { }
2.698 + UndirGraphWrapper(GraphWrapper _gw) :
2.699 + GraphWrapperSkeleton<GraphWrapper>(_gw) { }
2.700 +
2.701 + //UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
2.702 +
2.703 + //void setGraph(Graph& _graph) { graph = &_graph; }
2.704 + //Graph& getGraph() const { return (*graph); }
2.705 +
2.706 + class Edge {
2.707 + friend class UndirGraphWrapper<GraphWrapper>;
2.708 + bool out_or_in; //true iff out
2.709 + GraphOutEdgeIt out;
2.710 + GraphInEdgeIt in;
2.711 + public:
2.712 + Edge() : out_or_in(), out(), in() { }
2.713 + Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
2.714 + operator GraphEdge() const {
2.715 + if (out_or_in) return(out); else return(in);
2.716 + }
2.717 +//FIXME
2.718 +//2 edges are equal if they "refer" to the same physical edge
2.719 +//is it good?
2.720 + friend bool operator==(const Edge& u, const Edge& v) {
2.721 + if (v.out_or_in)
2.722 + if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in);
2.723 + //return (u.out_or_in && u.out==v.out);
2.724 + else
2.725 + if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in);
2.726 + //return (!u.out_or_in && u.in==v.in);
2.727 + }
2.728 + friend bool operator!=(const Edge& u, const Edge& v) {
2.729 + if (v.out_or_in)
2.730 + if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in);
2.731 + //return (!u.out_or_in || u.out!=v.out);
2.732 + else
2.733 + if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in);
2.734 + //return (u.out_or_in || u.in!=v.in);
2.735 + }
2.736 + };
2.737 +
2.738 + class OutEdgeIt : public Edge {
2.739 + friend class UndirGraphWrapper<GraphWrapper>;
2.740 + public:
2.741 + OutEdgeIt() : Edge() { }
2.742 + OutEdgeIt(const Invalid& i) : Edge(i) { }
2.743 + OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)
2.744 + : Edge() {
2.745 + out_or_in=true; _G.gw.first(out, n);
2.746 + if (!(_G.gw.valid(out))) { out_or_in=false; _G.gw.first(in, n); }
2.747 + }
2.748 + };
2.749 +
2.750 + typedef OutEdgeIt InEdgeIt;
2.751 +
2.752 + class EdgeIt : public Edge {
2.753 + friend class UndirGraphWrapper<GraphWrapper>;
2.754 + protected:
2.755 + NodeIt v;
2.756 + public:
2.757 + EdgeIt() : Edge() { }
2.758 + EdgeIt(const Invalid& i) : Edge(i) { }
2.759 + EdgeIt(const UndirGraphWrapper<GraphWrapper>& _G)
2.760 + : Edge() {
2.761 + out_or_in=true;
2.762 + //Node v;
2.763 + _G.first(v);
2.764 + if (_G.valid(v)) _G.gw.first(out); else out=INVALID;
2.765 + while (_G.valid(v) && !_G.gw.valid(out)) {
2.766 + _G.gw.next(v);
2.767 + if (_G.valid(v)) _G.gw.first(out);
2.768 + }
2.769 + }
2.770 + };
2.771 +
2.772 + OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
2.773 + e.out_or_in=true; gw.first(e.out, n);
2.774 + if (!(gw.valid(e.out))) { e.out_or_in=false; gw.first(e.in, n); }
2.775 + return e;
2.776 + }
2.777 +
2.778 + EdgeIt& first(EdgeIt& e) const {
2.779 + e.out_or_in=true;
2.780 + //NodeIt v;
2.781 + first(e.v);
2.782 + if (valid(e.v)) gw.first(e.out, e.v); else e.out=INVALID;
2.783 + while (valid(e.v) && !gw.valid(e.out)) {
2.784 + gw.next(e.v);
2.785 + if (valid(e.v)) gw.first(e.out, e.v);
2.786 + }
2.787 + return e;
2.788 + }
2.789 +
2.790 + template<typename I> I& first(I& i) const { gw.first(i); return i; }
2.791 + template<typename I, typename P> I& first(I& i, const P& p) const {
2.792 + gw.first(i, p); return i; }
2.793 +
2.794 + OutEdgeIt& next(OutEdgeIt& e) const {
2.795 + if (e.out_or_in) {
2.796 + Node n=gw.tail(e.out);
2.797 + gw.next(e.out);
2.798 + if (!gw.valid(e.out)) { e.out_or_in=false; gw.first(e.in, n); }
2.799 + } else {
2.800 + gw.next(e.in);
2.801 + }
2.802 + return e;
2.803 + }
2.804 +
2.805 + EdgeIt& next(EdgeIt& e) const {
2.806 + //NodeIt v=tail(e);
2.807 + gw.next(e.out);
2.808 + while (valid(e.v) && !gw.valid(e.out)) {
2.809 + next(e.v);
2.810 + if (valid(e.v)) gw.first(e.out, e.v);
2.811 + }
2.812 + return e;
2.813 + }
2.814 +
2.815 + template<typename I> I& next(I &i) const { return gw.next(i); }
2.816 +// template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
2.817 +
2.818 + template< typename It > It first() const {
2.819 + It e; first(e); return e; }
2.820 +
2.821 + template< typename It > It first(const Node& v) const {
2.822 + It e; first(e, v); return e; }
2.823 +
2.824 +// Node head(const Edge& e) const { return gw.head(e); }
2.825 +// Node tail(const Edge& e) const { return gw.tail(e); }
2.826 +
2.827 +// template<typename I> bool valid(const I& i) const
2.828 +// { return gw.valid(i); }
2.829 +
2.830 +// int nodeNum() const { return gw.nodeNum(); }
2.831 +// int edgeNum() const { return gw.edgeNum(); }
2.832 +
2.833 +// template<typename I> Node aNode(const I& e) const {
2.834 +// return graph->aNode(e); }
2.835 +// template<typename I> Node bNode(const I& e) const {
2.836 +// return graph->bNode(e); }
2.837 +
2.838 + Node aNode(const OutEdgeIt& e) const {
2.839 + if (e.out_or_in) return gw.tail(e); else return gw.head(e); }
2.840 + Node bNode(const OutEdgeIt& e) const {
2.841 + if (e.out_or_in) return gw.head(e); else return gw.tail(e); }
2.842 +
2.843 +// Node addNode() const { return gw.addNode(); }
2.844 +
2.845 +// FIXME: ez igy nem jo, mert nem
2.846 +// Edge addEdge(const Node& tail, const Node& head) const {
2.847 +// return graph->addEdge(tail, head); }
2.848 +
2.849 +// template<typename I> void erase(const I& i) const { gw.erase(i); }
2.850 +
2.851 +// void clear() const { gw.clear(); }
2.852 +
2.853 +// template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
2.854 +// public:
2.855 +// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
2.856 +// GraphWrapper::NodeMap<T>(_G.gw) { }
2.857 +// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
2.858 +// GraphWrapper::NodeMap<T>(_G.gw, a) { }
2.859 +// };
2.860 +
2.861 +// template<typename T> class EdgeMap :
2.862 +// public GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T> {
2.863 +// public:
2.864 +// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
2.865 +// GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T>(_G.gw) { }
2.866 +// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
2.867 +// GraphWrapper::EdgeMap<T>(_G.gw, a) { }
2.868 +// };
2.869 + };
2.870 +
2.871 +
2.872 +
2.873 +
2.874 +
2.875 +// template<typename Graph>
2.876 +// class SymGraphWrapper
2.877 +// {
2.878 +// Graph* graph;
2.879 +
2.880 +// public:
2.881 +// typedef Graph BaseGraph;
2.882 +
2.883 +// typedef typename Graph::Node Node;
2.884 +// typedef typename Graph::Edge Edge;
2.885 +
2.886 +// typedef typename Graph::NodeIt NodeIt;
2.887 +
2.888 +// //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
2.889 +// //iranyitatlant, ami van
2.890 +// //mert csak 1 dolgot lehet be typedef-elni
2.891 +// typedef typename Graph::OutEdgeIt SymEdgeIt;
2.892 +// //typedef typename Graph::InEdgeIt SymEdgeIt;
2.893 +// //typedef typename Graph::SymEdgeIt SymEdgeIt;
2.894 +// typedef typename Graph::EdgeIt EdgeIt;
2.895 +
2.896 +// int nodeNum() const { return graph->nodeNum(); }
2.897 +// int edgeNum() const { return graph->edgeNum(); }
2.898 +
2.899 +// template<typename I> I& first(I& i) const { return graph->first(i); }
2.900 +// template<typename I, typename P> I& first(I& i, const P& p) const {
2.901 +// return graph->first(i, p); }
2.902 +// //template<typename I> I next(const I i); { return graph->goNext(i); }
2.903 +// //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
2.904 +
2.905 +// template< typename It > It first() const {
2.906 +// It e; first(e); return e; }
2.907 +
2.908 +// template< typename It > It first(Node v) const {
2.909 +// It e; first(e, v); return e; }
2.910 +
2.911 +// Node head(const Edge& e) const { return graph->head(e); }
2.912 +// Node tail(const Edge& e) const { return graph->tail(e); }
2.913 +
2.914 +// template<typename I> Node aNode(const I& e) const {
2.915 +// return graph->aNode(e); }
2.916 +// template<typename I> Node bNode(const I& e) const {
2.917 +// return graph->bNode(e); }
2.918 +
2.919 +// //template<typename I> bool valid(const I i);
2.920 +// //{ return graph->valid(i); }
2.921 +
2.922 +// //template<typename I> void setInvalid(const I &i);
2.923 +// //{ return graph->setInvalid(i); }
2.924 +
2.925 +// Node addNode() { return graph->addNode(); }
2.926 +// Edge addEdge(const Node& tail, const Node& head) {
2.927 +// return graph->addEdge(tail, head); }
2.928 +
2.929 +// template<typename I> void erase(const I& i) { graph->erase(i); }
2.930 +
2.931 +// void clear() { graph->clear(); }
2.932 +
2.933 +// template<typename T> class NodeMap : public Graph::NodeMap<T> { };
2.934 +// template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
2.935 +
2.936 +// void setGraph(Graph& _graph) { graph = &_graph; }
2.937 +// Graph& getGraph() { return (*graph); }
2.938 +
2.939 +// //SymGraphWrapper() : graph(0) { }
2.940 +// SymGraphWrapper(Graph& _graph) : graph(&_graph) { }
2.941 +// };
2.942 +
2.943 +
2.944 + template<typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
2.945 + class ResGraphWrapper : public GraphWrapperSkeleton<GraphWrapper>{
2.946 + public:
2.947 + //typedef Graph BaseGraph;
2.948 + //typedef TrivGraphWrapper<const Graph> GraphWrapper;
2.949 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
2.950 + typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
2.951 + private:
2.952 + typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
2.953 + GraphWrapper::OutEdgeIt OldOutEdgeIt;
2.954 + typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
2.955 + GraphWrapper::InEdgeIt OldInEdgeIt;
2.956 +
2.957 + typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
2.958 + GraphWrapper::Edge OldEdge;
2.959 + protected:
2.960 + //const Graph* graph;
2.961 + //GraphWrapper gw;
2.962 + FlowMap* flow;
2.963 + const CapacityMap* capacity;
2.964 + public:
2.965 +
2.966 + ResGraphWrapper(const GraphWrapper& _gw, FlowMap& _flow,
2.967 + const CapacityMap& _capacity) :
2.968 + GraphWrapperSkeleton<GraphWrapper>(_gw),
2.969 + flow(&_flow), capacity(&_capacity) { }
2.970 +
2.971 + //void setGraph(const Graph& _graph) { graph = &_graph; }
2.972 + //const Graph& getGraph() const { return (*graph); }
2.973 +
2.974 + class Edge;
2.975 + class OutEdgeIt;
2.976 + friend class Edge;
2.977 + friend class OutEdgeIt;
2.978 +
2.979 + class Edge {
2.980 + friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
2.981 + protected:
2.982 + bool out_or_in; //true, iff out
2.983 + OldOutEdgeIt out;
2.984 + OldInEdgeIt in;
2.985 + public:
2.986 + Edge() : out_or_in(true) { }
2.987 + Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
2.988 +// bool valid() const {
2.989 +// return out_or_in && out.valid() || in.valid(); }
2.990 + friend bool operator==(const Edge& u, const Edge& v) {
2.991 + if (v.out_or_in)
2.992 + return (u.out_or_in && u.out==v.out);
2.993 + else
2.994 + return (!u.out_or_in && u.in==v.in);
2.995 + }
2.996 + friend bool operator!=(const Edge& u, const Edge& v) {
2.997 + if (v.out_or_in)
2.998 + return (!u.out_or_in || u.out!=v.out);
2.999 + else
2.1000 + return (u.out_or_in || u.in!=v.in);
2.1001 + }
2.1002 + operator OldEdge() {
2.1003 + if(out_or_in)
2.1004 + return out;
2.1005 + else
2.1006 + return in;
2.1007 + }
2.1008 + };
2.1009 +
2.1010 +
2.1011 + class OutEdgeIt : public Edge {
2.1012 + friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
2.1013 + public:
2.1014 + OutEdgeIt() { }
2.1015 + //FIXME
2.1016 + OutEdgeIt(const Edge& e) : Edge(e) { }
2.1017 + OutEdgeIt(const Invalid& i) : Edge(i) { }
2.1018 + protected:
2.1019 + OutEdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
2.1020 + resG.gw.first(out, v);
2.1021 + while( resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
2.1022 + if (!resG.gw.valid(out)) {
2.1023 + out_or_in=0;
2.1024 + resG.gw.first(in, v);
2.1025 + while( resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
2.1026 + }
2.1027 + }
2.1028 +// public:
2.1029 +// OutEdgeIt& operator++() {
2.1030 +// if (out_or_in) {
2.1031 +// Node v=/*resG->*/G->aNode(out);
2.1032 +// ++out;
2.1033 +// while( out.valid() && !(Edge::resCap()>0) ) { ++out; }
2.1034 +// if (!out.valid()) {
2.1035 +// out_or_in=0;
2.1036 +// G->first(in, v);
2.1037 +// while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
2.1038 +// }
2.1039 +// } else {
2.1040 +// ++in;
2.1041 +// while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
2.1042 +// }
2.1043 +// return *this;
2.1044 +// }
2.1045 + };
2.1046 +
2.1047 + //FIXME This is just for having InEdgeIt
2.1048 + typedef void InEdgeIt;
2.1049 +
2.1050 + class EdgeIt : public Edge {
2.1051 + friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
2.1052 + NodeIt v;
2.1053 + public:
2.1054 + EdgeIt() { }
2.1055 + //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
2.1056 + EdgeIt(const Invalid& i) : Edge(i) { }
2.1057 + EdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG) : Edge() {
2.1058 + resG.gw.first(v);
2.1059 + if (resG.gw.valid(v)) resG.gw.first(out, v); else out=INVALID;
2.1060 + while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
2.1061 + while (resG.gw.valid(v) && !resG.gw.valid(out)) {
2.1062 + resG.gw.next(v);
2.1063 + if (resG.gw.valid(v)) resG.gw.first(out, v);
2.1064 + while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
2.1065 + }
2.1066 + if (!resG.gw.valid(out)) {
2.1067 + out_or_in=0;
2.1068 + resG.gw.first(v);
2.1069 + if (resG.gw.valid(v)) resG.gw.first(in, v); else in=INVALID;
2.1070 + while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
2.1071 + while (resG.gw.valid(v) && !resG.gw.valid(in)) {
2.1072 + resG.gw.next(v);
2.1073 + if (resG.gw.valid(v)) resG.gw.first(in, v);
2.1074 + while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
2.1075 + }
2.1076 + }
2.1077 + }
2.1078 +// EdgeIt& operator++() {
2.1079 +// if (out_or_in) {
2.1080 +// ++out;
2.1081 +// while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
2.1082 +// while (v.valid() && !out.valid()) {
2.1083 +// ++v;
2.1084 +// if (v.valid()) G->first(out, v);
2.1085 +// while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
2.1086 +// }
2.1087 +// if (!out.valid()) {
2.1088 +// out_or_in=0;
2.1089 +// G->first(v);
2.1090 +// if (v.valid()) G->first(in, v); else in=OldInEdgeIt();
2.1091 +// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
2.1092 +// while (v.valid() && !in.valid()) {
2.1093 +// ++v;
2.1094 +// if (v.valid()) G->first(in, v);
2.1095 +// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
2.1096 +// }
2.1097 +// }
2.1098 +// } else {
2.1099 +// ++in;
2.1100 +// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
2.1101 +// while (v.valid() && !in.valid()) {
2.1102 +// ++v;
2.1103 +// if (v.valid()) G->first(in, v);
2.1104 +// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
2.1105 +// }
2.1106 +// }
2.1107 +// return *this;
2.1108 +// }
2.1109 + };
2.1110 +
2.1111 + NodeIt& first(NodeIt& v) const { gw.first(v); return v; }
2.1112 + OutEdgeIt& first(OutEdgeIt& e, Node v) const {
2.1113 + e=OutEdgeIt(*this, v);
2.1114 + return e;
2.1115 + }
2.1116 + EdgeIt& first(EdgeIt& e) const {
2.1117 + e=EdgeIt(*this);
2.1118 + return e;
2.1119 + }
2.1120 +
2.1121 + NodeIt& next(NodeIt& n) const { return gw.next(n); }
2.1122 +
2.1123 + OutEdgeIt& next(OutEdgeIt& e) const {
2.1124 + if (e.out_or_in) {
2.1125 + Node v=gw.aNode(e.out);
2.1126 + gw.next(e.out);
2.1127 + while( gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
2.1128 + if (!gw.valid(e.out)) {
2.1129 + e.out_or_in=0;
2.1130 + gw.first(e.in, v);
2.1131 + while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
2.1132 + }
2.1133 + } else {
2.1134 + gw.next(e.in);
2.1135 + while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
2.1136 + }
2.1137 + return e;
2.1138 + }
2.1139 +
2.1140 + EdgeIt& next(EdgeIt& e) const {
2.1141 + if (e.out_or_in) {
2.1142 + gw.next(e.out);
2.1143 + while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
2.1144 + while (gw.valid(e.v) && !gw.valid(e.out)) {
2.1145 + gw.next(e.v);
2.1146 + if (gw.valid(e.v)) gw.first(e.out, e.v);
2.1147 + while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
2.1148 + }
2.1149 + if (!gw.valid(e.out)) {
2.1150 + e.out_or_in=0;
2.1151 + gw.first(e.v);
2.1152 + if (gw.valid(e.v)) gw.first(e.in, e.v); else e.in=INVALID;
2.1153 + while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
2.1154 + while (gw.valid(e.v) && !gw.valid(e.in)) {
2.1155 + gw.next(e.v);
2.1156 + if (gw.valid(e.v)) gw.first(e.in, e.v);
2.1157 + while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
2.1158 + }
2.1159 + }
2.1160 + } else {
2.1161 + gw.next(e.in);
2.1162 + while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
2.1163 + while (gw.valid(e.v) && !gw.valid(e.in)) {
2.1164 + gw.next(e.v);
2.1165 + if (gw.valid(e.v)) gw.first(e.in, e.v);
2.1166 + while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
2.1167 + }
2.1168 + }
2.1169 + return e;
2.1170 + }
2.1171 +
2.1172 +
2.1173 + template< typename It >
2.1174 + It first() const {
2.1175 + It e;
2.1176 + first(e);
2.1177 + return e;
2.1178 + }
2.1179 +
2.1180 + template< typename It >
2.1181 + It first(Node v) const {
2.1182 + It e;
2.1183 + first(e, v);
2.1184 + return e;
2.1185 + }
2.1186 +
2.1187 + Node tail(Edge e) const {
2.1188 + return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); }
2.1189 + Node head(Edge e) const {
2.1190 + return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }
2.1191 +
2.1192 + Node aNode(OutEdgeIt e) const {
2.1193 + return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); }
2.1194 + Node bNode(OutEdgeIt e) const {
2.1195 + return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }
2.1196 +
2.1197 + int nodeNum() const { return gw.nodeNum(); }
2.1198 + //FIXME
2.1199 + //int edgeNum() const { return gw.edgeNum(); }
2.1200 +
2.1201 +
2.1202 + int id(Node v) const { return gw.id(v); }
2.1203 +
2.1204 + bool valid(Node n) const { return gw.valid(n); }
2.1205 + bool valid(Edge e) const {
2.1206 + return e.out_or_in ? gw.valid(e.out) : gw.valid(e.in); }
2.1207 +
2.1208 + void augment(const Edge& e, Number a) const {
2.1209 + if (e.out_or_in)
2.1210 + flow->set(e.out, flow->get(e.out)+a);
2.1211 + else
2.1212 + flow->set(e.in, flow->get(e.in)-a);
2.1213 + }
2.1214 +
2.1215 + Number resCap(const Edge& e) const {
2.1216 + if (e.out_or_in)
2.1217 + return (capacity->get(e.out)-flow->get(e.out));
2.1218 + else
2.1219 + return (flow->get(e.in));
2.1220 + }
2.1221 +
2.1222 + Number resCap(OldOutEdgeIt out) const {
2.1223 + return ( (*capacity)[out] - (*flow)[out]);
2.1224 + }
2.1225 +
2.1226 + Number resCap(OldInEdgeIt in) const {
2.1227 + return ( (*flow)[in] );
2.1228 + }
2.1229 +
2.1230 +// template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
2.1231 +// public:
2.1232 +// NodeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G)
2.1233 +// : GraphWrapper::NodeMap<T>(_G.gw) { }
2.1234 +// NodeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G,
2.1235 +// T a) : GraphWrapper::NodeMap<T>(_G.gw, a) { }
2.1236 +// };
2.1237 +
2.1238 +// template <typename T>
2.1239 +// class NodeMap {
2.1240 +// typename Graph::NodeMap<T> node_map;
2.1241 +// public:
2.1242 +// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
2.1243 +// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
2.1244 +// void set(Node nit, T a) { node_map.set(nit, a); }
2.1245 +// T get(Node nit) const { return node_map.get(nit); }
2.1246 +// };
2.1247 +
2.1248 + template <typename T>
2.1249 + class EdgeMap {
2.1250 + typename GraphWrapper::EdgeMap<T> forward_map, backward_map;
2.1251 + public:
2.1252 + EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.gw), backward_map(_G.gw) { }
2.1253 + EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.gw, a), backward_map(_G.gw, a) { }
2.1254 + void set(Edge e, T a) {
2.1255 + if (e.out_or_in)
2.1256 + forward_map.set(e.out, a);
2.1257 + else
2.1258 + backward_map.set(e.in, a);
2.1259 + }
2.1260 + T get(Edge e) {
2.1261 + if (e.out_or_in)
2.1262 + return forward_map.get(e.out);
2.1263 + else
2.1264 + return backward_map.get(e.in);
2.1265 + }
2.1266 + };
2.1267 + };
2.1268 +
2.1269 + //Subgraph on the same node-set and partial edge-set
2.1270 + template<typename GraphWrapper, typename FirstOutEdgesMap>
2.1271 + class ErasingFirstGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
2.1272 + protected:
2.1273 + FirstOutEdgesMap* first_out_edges;
2.1274 + public:
2.1275 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
2.1276 + typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
2.1277 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
2.1278 + typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt;
2.1279 + typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt;
2.1280 + typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt;
2.1281 +
2.1282 + ErasingFirstGraphWrapper(GraphWrapper _gw, FirstOutEdgesMap& _first_out_edges) :
2.1283 + GraphWrapperSkeleton<GraphWrapper>(_gw), first_out_edges(&_first_out_edges) { }
2.1284 +
2.1285 + template<typename I> I& first(I& i) const {
2.1286 + gw.first(i);
2.1287 + //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
2.1288 + return i;
2.1289 + }
2.1290 + OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
2.1291 + e=first_out_edges->get(n);
2.1292 + return e;
2.1293 + }
2.1294 + template<typename I, typename P> I& first(I& i, const P& p) const {
2.1295 + gw.first(i, p);
2.1296 + //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
2.1297 + return i;
2.1298 + }
2.1299 +
2.1300 + //template<typename I> I getNext(const I& i) const {
2.1301 + // return gw.getNext(i);
2.1302 + //}
2.1303 + template<typename I> I& next(I &i) const {
2.1304 + gw.next(i);
2.1305 + //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
2.1306 + return i;
2.1307 + }
2.1308 +
2.1309 + template< typename It > It first() const {
2.1310 + It e; this->first(e); return e; }
2.1311 +
2.1312 + template< typename It > It first(const Node& v) const {
2.1313 + It e; this->first(e, v); return e; }
2.1314 +
2.1315 + void erase(const OutEdgeIt& e) const {
2.1316 + OutEdgeIt f=e;
2.1317 + this->next(f);
2.1318 + first_out_edges->set(this->tail(e), f);
2.1319 + }
2.1320 + };
2.1321 +
2.1322 +// template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
2.1323 +// class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
2.1324 +// protected:
2.1325 +// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
2.1326 +// //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
2.1327 +// public:
2.1328 +// ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow,
2.1329 +// const CapacityMap& _capacity) :
2.1330 +// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),
2.1331 +// first_out_edges(*this) /*, dist(*this)*/ {
2.1332 +// for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) {
2.1333 +// OutEdgeIt e;
2.1334 +// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
2.1335 +// first_out_edges.set(n, e);
2.1336 +// }
2.1337 +// }
2.1338 +
2.1339 +// //void setGraph(Graph& _graph) { graph = &_graph; }
2.1340 +// //Graph& getGraph() const { return (*graph); }
2.1341 +
2.1342 +// //TrivGraphWrapper() : graph(0) { }
2.1343 +// //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }
2.1344 +
2.1345 +// //typedef Graph BaseGraph;
2.1346 +
2.1347 +// //typedef typename Graph::Node Node;
2.1348 +// //typedef typename Graph::NodeIt NodeIt;
2.1349 +
2.1350 +// //typedef typename Graph::Edge Edge;
2.1351 +// //typedef typename Graph::OutEdgeIt OutEdgeIt;
2.1352 +// //typedef typename Graph::InEdgeIt InEdgeIt;
2.1353 +// //typedef typename Graph::SymEdgeIt SymEdgeIt;
2.1354 +// //typedef typename Graph::EdgeIt EdgeIt;
2.1355 +
2.1356 +// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
2.1357 +// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
2.1358 +
2.1359 +// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
2.1360 +// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
2.1361 +// //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
2.1362 +// //typedef typename Graph::SymEdgeIt SymEdgeIt;
2.1363 +// //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
2.1364 +
2.1365 +// NodeIt& first(NodeIt& n) const {
2.1366 +// return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
2.1367 +// }
2.1368 +
2.1369 +// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
2.1370 +// e=first_out_edges.get(n);
2.1371 +// return e;
2.1372 +// }
2.1373 +
2.1374 +// //ROSSZ template<typename I> I& first(I& i) const { return first(i); }
2.1375 +// //ROSSZ template<typename I, typename P> I& first(I& i, const P& p) const {
2.1376 +// // return first(i, p); }
2.1377 +
2.1378 +// //template<typename I> I getNext(const I& i) const {
2.1379 +// // return gw.getNext(i); }
2.1380 +// //template<typename I> I& next(I &i) const { return gw.next(i); }
2.1381 +
2.1382 +// template< typename It > It first() const {
2.1383 +// It e; first(e); return e; }
2.1384 +
2.1385 +// template< typename It > It first(const Node& v) const {
2.1386 +// It e; first(e, v); return e; }
2.1387 +
2.1388 +// //Node head(const Edge& e) const { return gw.head(e); }
2.1389 +// //Node tail(const Edge& e) const { return gw.tail(e); }
2.1390 +
2.1391 +// //template<typename I> bool valid(const I& i) const
2.1392 +// // { return gw.valid(i); }
2.1393 +
2.1394 +// //int nodeNum() const { return gw.nodeNum(); }
2.1395 +// //int edgeNum() const { return gw.edgeNum(); }
2.1396 +
2.1397 +// //template<typename I> Node aNode(const I& e) const {
2.1398 +// // return gw.aNode(e); }
2.1399 +// //template<typename I> Node bNode(const I& e) const {
2.1400 +// // return gw.bNode(e); }
2.1401 +
2.1402 +// //Node addNode() const { return gw.addNode(); }
2.1403 +// //Edge addEdge(const Node& tail, const Node& head) const {
2.1404 +// // return gw.addEdge(tail, head); }
2.1405 +
2.1406 +// //void erase(const OutEdgeIt& e) {
2.1407 +// // first_out_edge(this->tail(e))=e;
2.1408 +// //}
2.1409 +// void erase(const Edge& e) {
2.1410 +// OutEdgeIt f(e);
2.1411 +// next(f);
2.1412 +// first_out_edges.set(this->tail(e), f);
2.1413 +// }
2.1414 +// //template<typename I> void erase(const I& i) const { gw.erase(i); }
2.1415 +
2.1416 +// //void clear() const { gw.clear(); }
2.1417 +
2.1418 +// template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
2.1419 +// public:
2.1420 +// NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
2.1421 +// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
2.1422 +// NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
2.1423 +// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
2.1424 +// };
2.1425 +
2.1426 +// template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
2.1427 +// public:
2.1428 +// EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
2.1429 +// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
2.1430 +// EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
2.1431 +// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
2.1432 +// };
2.1433 +// };
2.1434 +
2.1435 +// template<typename GraphWrapper>
2.1436 +// class FilterGraphWrapper {
2.1437 +// };
2.1438 +
2.1439 +// template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
2.1440 +// class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
2.1441 +
2.1442 +// //Graph* graph;
2.1443 +
2.1444 +// public:
2.1445 +// //typedef Graph BaseGraph;
2.1446 +
2.1447 +// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
2.1448 +// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
2.1449 +
2.1450 +// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
2.1451 +// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
2.1452 +// //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
2.1453 +// //typedef typename Graph::SymEdgeIt SymEdgeIt;
2.1454 +// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
2.1455 +
2.1456 +// //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
2.1457 +
2.1458 +// public:
2.1459 +// FilterGraphWrapper(const Graph& _G, FlowMap& _flow,
2.1460 +// const CapacityMap& _capacity) :
2.1461 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this, gw.nodeNum()) {
2.1462 +// }
2.1463 +
2.1464 +// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
2.1465 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
2.1466 +// while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e))))
2.1467 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
2.1468 +// return e;
2.1469 +// }
2.1470 +
2.1471 +// NodeIt& next(NodeIt& e) const {
2.1472 +// return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
2.1473 +// }
2.1474 +
2.1475 +// OutEdgeIt& next(OutEdgeIt& e) const {
2.1476 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
2.1477 +// while (valid(e) && (dist.get(tail(e))/*+1!*/>=dist.get(head(e))))
2.1478 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
2.1479 +// return e;
2.1480 +// }
2.1481 +
2.1482 +// NodeIt& first(NodeIt& n) const {
2.1483 +// return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
2.1484 +// }
2.1485 +
2.1486 +// void erase(const Edge& e) {
2.1487 +// OutEdgeIt f(e);
2.1488 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
2.1489 +// while (valid(f) && (dist.get(tail(f))/*+1!=*/>=dist.get(head(f))))
2.1490 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
2.1491 +// first_out_edges.set(this->tail(e), f);
2.1492 +// }
2.1493 +
2.1494 +// //TrivGraphWrapper() : graph(0) { }
2.1495 +// //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
2.1496 +
2.1497 +// //void setGraph(Graph& _graph) { graph = &_graph; }
2.1498 +// //Graph& getGraph() const { return (*graph); }
2.1499 +
2.1500 +// //template<typename I> I& first(I& i) const { return gw.first(i); }
2.1501 +// //template<typename I, typename P> I& first(I& i, const P& p) const {
2.1502 +// // return gw.first(i, p); }
2.1503 +
2.1504 +// //template<typename I> I getNext(const I& i) const {
2.1505 +// // return gw.getNext(i); }
2.1506 +// //template<typename I> I& next(I &i) const { return gw.next(i); }
2.1507 +
2.1508 +// template< typename It > It first() const {
2.1509 +// It e; first(e); return e; }
2.1510 +
2.1511 +// template< typename It > It first(const Node& v) const {
2.1512 +// It e; first(e, v); return e; }
2.1513 +
2.1514 +// //Node head(const Edge& e) const { return gw.head(e); }
2.1515 +// //Node tail(const Edge& e) const { return gw.tail(e); }
2.1516 +
2.1517 +// //template<typename I> bool valid(const I& i) const
2.1518 +// // { return gw.valid(i); }
2.1519 +
2.1520 +// //template<typename I> void setInvalid(const I &i);
2.1521 +// //{ return gw.setInvalid(i); }
2.1522 +
2.1523 +// //int nodeNum() const { return gw.nodeNum(); }
2.1524 +// //int edgeNum() const { return gw.edgeNum(); }
2.1525 +
2.1526 +// //template<typename I> Node aNode(const I& e) const {
2.1527 +// // return gw.aNode(e); }
2.1528 +// //template<typename I> Node bNode(const I& e) const {
2.1529 +// // return gw.bNode(e); }
2.1530 +
2.1531 +// //Node addNode() const { return gw.addNode(); }
2.1532 +// //Edge addEdge(const Node& tail, const Node& head) const {
2.1533 +// // return gw.addEdge(tail, head); }
2.1534 +
2.1535 +// //template<typename I> void erase(const I& i) const { gw.erase(i); }
2.1536 +
2.1537 +// //void clear() const { gw.clear(); }
2.1538 +
2.1539 +// template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
2.1540 +// public:
2.1541 +// NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
2.1542 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
2.1543 +// NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
2.1544 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
2.1545 +// };
2.1546 +
2.1547 +// template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
2.1548 +// public:
2.1549 +// EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
2.1550 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
2.1551 +// EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
2.1552 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
2.1553 +// };
2.1554 +
2.1555 +// public:
2.1556 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
2.1557 +
2.1558 +// };
2.1559 +
2.1560 +
2.1561 +
2.1562 +// // FIXME: comparison should be made better!!!
2.1563 +// template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
2.1564 +// class ResGraphWrapper
2.1565 +// {
2.1566 +// Graph* graph;
2.1567 +
2.1568 +// public:
2.1569 +// typedef Graph BaseGraph;
2.1570 +
2.1571 +// typedef typename Graph::Node Node;
2.1572 +// typedef typename Graph::Edge Edge;
2.1573 +
2.1574 +// typedef typename Graph::NodeIt NodeIt;
2.1575 +
2.1576 +// class OutEdgeIt {
2.1577 +// public:
2.1578 +// //Graph::Node n;
2.1579 +// bool out_or_in;
2.1580 +// typename Graph::OutEdgeIt o;
2.1581 +// typename Graph::InEdgeIt i;
2.1582 +// };
2.1583 +// class InEdgeIt {
2.1584 +// public:
2.1585 +// //Graph::Node n;
2.1586 +// bool out_or_in;
2.1587 +// typename Graph::OutEdgeIt o;
2.1588 +// typename Graph::InEdgeIt i;
2.1589 +// };
2.1590 +// typedef typename Graph::SymEdgeIt SymEdgeIt;
2.1591 +// typedef typename Graph::EdgeIt EdgeIt;
2.1592 +
2.1593 +// int nodeNum() const { return gw.nodeNum(); }
2.1594 +// int edgeNum() const { return gw.edgeNum(); }
2.1595 +
2.1596 +// Node& first(Node& n) const { return gw.first(n); }
2.1597 +
2.1598 +// // Edge and SymEdge is missing!!!!
2.1599 +// // Edge <-> In/OutEdgeIt conversion is missing!!!!
2.1600 +
2.1601 +// //FIXME
2.1602 +// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const
2.1603 +// {
2.1604 +// e.n=n;
2.1605 +// gw.first(e.o,n);
2.1606 +// while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
2.1607 +// gw.goNext(e.o);
2.1608 +// if(!gw.valid(e.o)) {
2.1609 +// gw.first(e.i,n);
2.1610 +// while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
2.1611 +// gw.goNext(e.i);
2.1612 +// }
2.1613 +// return e;
2.1614 +// }
2.1615 +// /*
2.1616 +// OutEdgeIt &goNext(OutEdgeIt &e)
2.1617 +// {
2.1618 +// if(gw.valid(e.o)) {
2.1619 +// while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
2.1620 +// gw.goNext(e.o);
2.1621 +// if(gw.valid(e.o)) return e;
2.1622 +// else gw.first(e.i,e.n);
2.1623 +// }
2.1624 +// else {
2.1625 +// while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
2.1626 +// gw.goNext(e.i);
2.1627 +// return e;
2.1628 +// }
2.1629 +// }
2.1630 +// OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
2.1631 +// */
2.1632 +// //bool valid(const OutEdgeIt e) { return gw.valid(e.o)||gw.valid(e.i);}
2.1633 +
2.1634 +// //FIXME
2.1635 +// InEdgeIt& first(InEdgeIt& e, const Node& n) const
2.1636 +// {
2.1637 +// e.n=n;
2.1638 +// gw.first(e.i,n);
2.1639 +// while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
2.1640 +// gw.goNext(e.i);
2.1641 +// if(!gw.valid(e.i)) {
2.1642 +// gw.first(e.o,n);
2.1643 +// while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
2.1644 +// gw.goNext(e.o);
2.1645 +// }
2.1646 +// return e;
2.1647 +// }
2.1648 +// /*
2.1649 +// InEdgeIt &goNext(InEdgeIt &e)
2.1650 +// {
2.1651 +// if(gw.valid(e.i)) {
2.1652 +// while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
2.1653 +// gw.goNext(e.i);
2.1654 +// if(gw.valid(e.i)) return e;
2.1655 +// else gw.first(e.o,e.n);
2.1656 +// }
2.1657 +// else {
2.1658 +// while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
2.1659 +// gw.goNext(e.o);
2.1660 +// return e;
2.1661 +// }
2.1662 +// }
2.1663 +// InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
2.1664 +// */
2.1665 +// //bool valid(const InEdgeIt e) { return gw.valid(e.i)||gw.valid(e.o);}
2.1666 +
2.1667 +// //template<typename I> I &goNext(I &i); { return gw.goNext(i); }
2.1668 +// //template<typename I> I next(const I i); { return gw.goNext(i); }
2.1669 +
2.1670 +// template< typename It > It first() const {
2.1671 +// It e; first(e); return e; }
2.1672 +
2.1673 +// template< typename It > It first(Node v) const {
2.1674 +// It e; first(e, v); return e; }
2.1675 +
2.1676 +// Node head(const Edge& e) const { return gw.head(e); }
2.1677 +// Node tail(const Edge& e) const { return gw.tail(e); }
2.1678 +
2.1679 +// template<typename I> Node aNode(const I& e) const {
2.1680 +// return gw.aNode(e); }
2.1681 +// template<typename I> Node bNode(const I& e) const {
2.1682 +// return gw.bNode(e); }
2.1683 +
2.1684 +// //template<typename I> bool valid(const I i);
2.1685 +// //{ return gw.valid(i); }
2.1686 +
2.1687 +// //template<typename I> void setInvalid(const I &i);
2.1688 +// //{ return gw.setInvalid(i); }
2.1689 +
2.1690 +// Node addNode() { return gw.addNode(); }
2.1691 +// Edge addEdge(const Node& tail, const Node& head) {
2.1692 +// return gw.addEdge(tail, head); }
2.1693 +
2.1694 +// template<typename I> void erase(const I& i) { gw.erase(i); }
2.1695 +
2.1696 +// void clear() { gw.clear(); }
2.1697 +
2.1698 +// template<typename S> class NodeMap : public Graph::NodeMap<S> { };
2.1699 +// template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
2.1700 +
2.1701 +// void setGraph(Graph& _graph) { graph = &_graph; }
2.1702 +// Graph& getGraph() { return (*graph); }
2.1703 +
2.1704 +// //ResGraphWrapper() : graph(0) { }
2.1705 +// ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
2.1706 +// };
2.1707 +
2.1708 +} //namespace hugo
2.1709 +
2.1710 +#endif //HUGO_GRAPH_WRAPPER_H
2.1711 +
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/work/athos/suurballe.cc Fri Apr 02 14:53:05 2004 +0000
3.3 @@ -0,0 +1,126 @@
3.4 +// -*- c++ -*-
3.5 +//#include <iostream>
3.6 +//#include <vector>
3.7 +//#include <string>
3.8 +
3.9 +#include <list_graph.h>
3.10 +#include <suurballe.h>
3.11 +
3.12 +using namespace hugo;
3.13 +
3.14 +
3.15 +int main()
3.16 +{
3.17 +
3.18 +
3.19 + typedef ListGraph::Node Node;
3.20 + typedef ListGraph::Edge Edge;
3.21 +
3.22 + ListGraph graph;
3.23 +
3.24 + /*
3.25 + //Marci példája
3.26 +
3.27 +
3.28 + NodeIt s=graph.addNode();
3.29 + NodeIt v1=graph.addNode();
3.30 + NodeIt v2=graph.addNode();
3.31 + NodeIt v3=graph.addNode();
3.32 + NodeIt v4=graph.addNode();
3.33 + NodeIt t=graph.addNode();
3.34 +
3.35 +
3.36 + EdgeIt s_v1=graph.addEdge(s, v1);
3.37 + EdgeIt s_v2=graph.addEdge(s, v2);
3.38 + EdgeIt v1_v2=graph.addEdge(v1, v2);
3.39 + EdgeIt v2_v1=graph.addEdge(v2, v1);
3.40 + EdgeIt v1_v3=graph.addEdge(v1, v3);
3.41 + EdgeIt v3_v2=graph.addEdge(v3, v2);
3.42 + EdgeIt v2_v4=graph.addEdge(v2, v4);
3.43 + EdgeIt v4_v3=graph.addEdge(v4, v3);
3.44 + EdgeIt v3_t=graph.addEdge(v3, t);
3.45 + EdgeIt v4_t=graph.addEdge(v4, t);
3.46 +
3.47 + ListGraph::EdgeMap<int> length(graph);
3.48 +
3.49 + length.set(s_v1, 16);
3.50 + length.set(s_v2, 13);
3.51 + length.set(v1_v2, 10);
3.52 + length.set(v2_v1, 4);
3.53 + length.set(v1_v3, 12);
3.54 + length.set(v3_v2, 9);
3.55 + length.set(v2_v4, 14);
3.56 + length.set(v4_v3, 7);
3.57 + length.set(v3_t, 20);
3.58 + length.set(v4_t, 4);
3.59 + */
3.60 +
3.61 +
3.62 + //Ahuja könyv példája
3.63 +
3.64 + Node s=graph.addNode();
3.65 + Node v2=graph.addNode();
3.66 + Node v3=graph.addNode();
3.67 + Node v4=graph.addNode();
3.68 + Node v5=graph.addNode();
3.69 + Node t=graph.addNode();
3.70 +
3.71 + Edge s_v2=graph.addEdge(s, v2);
3.72 + Edge s_v3=graph.addEdge(s, v3);
3.73 + Edge v2_v4=graph.addEdge(v2, v4);
3.74 + Edge v2_v5=graph.addEdge(v2, v5);
3.75 + Edge v3_v5=graph.addEdge(v3, v5);
3.76 + Edge v4_t=graph.addEdge(v4, t);
3.77 + Edge v5_t=graph.addEdge(v5, t);
3.78 +
3.79 + //Kis modositas
3.80 + //edge_iterator v2_s=graph.add_edge(v2, s);
3.81 +
3.82 + ListGraph::EdgeMap<int> length(graph);
3.83 +
3.84 + length.set(s_v2, 10);
3.85 + length.set(s_v3, 10);
3.86 + length.set(v2_v4, 5);
3.87 + length.set(v2_v5, 8);
3.88 + length.set(v3_v5, 5);
3.89 + length.set(v4_t, 8);
3.90 + length.set(v5_t, 8);
3.91 +
3.92 + //Kis modositas
3.93 + //length.put(v2_s, 100);
3.94 +
3.95 +
3.96 +
3.97 +
3.98 + /*Egyszerű példa
3.99 + NodeIt s=flow_test.add_node();
3.100 + NodeIt v1=flow_test.add_node();
3.101 + NodeIt v2=flow_test.add_node();
3.102 + NodeIt t=flow_test.add_node();
3.103 +
3.104 + node_property_vector<list_graph, std::string> node_name(flow_test);
3.105 + node_name.put(s, "s");
3.106 + node_name.put(v1, "v1");
3.107 + node_name.put(v2, "v2");
3.108 + node_name.put(t, "t");
3.109 +
3.110 + edge_iterator s_v1=flow_test.add_edge(s, v1);
3.111 + edge_iterator v1_v2=flow_test.add_edge(v1, v2);
3.112 + edge_iterator v2_t=flow_test.add_edge(v2, t);
3.113 +
3.114 + edge_property_vector<list_graph, int> length(flow_test);
3.115 +
3.116 + length.put(s_v1, 16);
3.117 + length.put(v1_v2, 10);
3.118 + length.put(v2_t, 4);
3.119 + */
3.120 +
3.121 + std::cout << "Suurballe algorithm test..." << std::endl;
3.122 +
3.123 +
3.124 + int k=1;
3.125 + Suurballe<ListGraph, int> surb_test(graph, length);
3.126 + std::cout << surb_test.run(s,t,k)<<std::endl;
3.127 +
3.128 + return 0;
3.129 +}
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/src/work/athos/suurballe.h Fri Apr 02 14:53:05 2004 +0000
4.3 @@ -0,0 +1,133 @@
4.4 +// -*- c++ -*-
4.5 +#ifndef HUGO_SUURBALLE_H
4.6 +#define HUGO_SUURBALLE_H
4.7 +
4.8 +#include <iostream>
4.9 +#include <dijkstra.h>
4.10 +#include <graph_wrapper.h>
4.11 +namespace hugo {
4.12 +
4.13 +
4.14 +///\brief Implementation of Suurballe's algorithm
4.15 +///
4.16 +/// The class \ref hugo::Suurballe "Suurballe" implements
4.17 +/// Suurballe's algorithm which seeks for k edge-disjoint paths
4.18 +/// from a given source node to a given target node in an
4.19 +/// edge-weighted directed graph having minimal total cost.
4.20 +///
4.21 +///
4.22 +
4.23 +
4.24 + template <typename Graph, typename T,
4.25 + typename LengthMap=typename Graph::EdgeMap<T> >
4.26 + class Suurballe {
4.27 +
4.28 +
4.29 + //Writing maps
4.30 + class ConstMap {
4.31 + public :
4.32 + typedef int ValueType;
4.33 + int operator[](typename Graph::Edge e) const {
4.34 + return 1;
4.35 + }
4.36 + };
4.37 + /*
4.38 + // template <typename Graph, typename T>
4.39 + class ModLengthMap {
4.40 + typedef typename Graph::EdgeMap<T> EdgeMap;
4.41 + typedef typename Graph::NodeMap<T> NodeMap;
4.42 +
4.43 + const EdgeMap &ol;
4.44 + const NodeMap &pot;
4.45 + public :
4.46 + typedef typename EdgeMap::KeyType KeyType;
4.47 + typedef typename EdgeMap::ValueType ValueType;
4.48 +
4.49 + double operator[](typename Graph::EdgeIt e) const {
4.50 + return 10;//ol.get(e)-pot.get(v)-pot.get(u);
4.51 + }
4.52 +
4.53 + ModLengthMap(const EdgeMap &o,
4.54 + const NodeMap &p) :
4.55 + ol(o), pot(p){};
4.56 + };
4.57 + */
4.58 +
4.59 +
4.60 + typedef typename Graph::Node Node;
4.61 + typedef typename Graph::NodeIt NodeIt;
4.62 + typedef typename Graph::Edge Edge;
4.63 + typedef typename Graph::OutEdgeIt OutEdgeIt;
4.64 + typedef ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap > ResGraphType;
4.65 +
4.66 + const Graph& G;
4.67 + const LengthMap& length;
4.68 +
4.69 +
4.70 + //auxiliary variables
4.71 +
4.72 + typename Graph::EdgeMap<int> reversed;
4.73 + typename Graph::NodeMap<T> dijkstra_dist;
4.74 +
4.75 + public :
4.76 +
4.77 +
4.78 + Suurballe(Graph& _G, LengthMap& _length) : G(_G),
4.79 + length(_length), reversed(_G), dijkstra_dist(_G){ }
4.80 +
4.81 + ///Runs Suurballe's algorithm
4.82 + ///Returns true iff there are k edge-disjoint paths from s to t
4.83 + bool run(Node s, Node t, int k) {
4.84 +
4.85 + LengthMap mod_length_c = length;
4.86 + ConstMap const1map;
4.87 + //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap>
4.88 + ResGraphType res_graph(G, reversed, const1map);
4.89 + //ModLengthMap modified_length(length, dijkstra_dist);
4.90 + //Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, modified_length);
4.91 + //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap>
4.92 + Dijkstra<ResGraphType, LengthMap> dijkstra(res_graph, mod_length_c);
4.93 +
4.94 + for (int i=0; i<k; ++i){
4.95 + dijkstra.run(s);
4.96 + if (!dijkstra.reached(t)){
4.97 + //There is no k path from s to t
4.98 + return false;
4.99 + };
4.100 + {
4.101 + //We have to copy the potential
4.102 + typename ResGraphType::EdgeIt e;
4.103 + for ( res_graph.first(e) ; res_graph.valid(e) ; res_graph.next(e) ) {
4.104 + //dijkstra_dist[e] = dijkstra.distMap()[e];
4.105 + mod_length_c[Edge(e)] = mod_length_c[Edge(e)] -
4.106 + dijkstra.distMap()[res_graph.head(e)] +
4.107 + dijkstra.distMap()[res_graph.tail(e)];
4.108 + }
4.109 + }
4.110 +
4.111 + //Reversing the sortest path
4.112 + Node n=t;
4.113 + Edge e;
4.114 + while (n!=s){
4.115 + e=dijkstra.pred(n);
4.116 + n=dijkstra.predNode(n);
4.117 + reversed[e] = 1-reversed[e];
4.118 + }
4.119 +
4.120 +
4.121 + }
4.122 + return true;
4.123 + }
4.124 +
4.125 +
4.126 +
4.127 +
4.128 +
4.129 + };//class Suurballe
4.130 +
4.131 +
4.132 +
4.133 +
4.134 +} //namespace hugo
4.135 +
4.136 +#endif //HUGO_SUURBALLE_H