Converted the "minlengthpaths" alg. to the new style graph_wrappers.
1.1 --- a/src/work/athos/graph_wrapper.h Mon Apr 05 17:56:31 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,1708 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -#ifndef HUGO_GRAPH_WRAPPER_H
1.6 -#define HUGO_GRAPH_WRAPPER_H
1.7 -
1.8 -#include <invalid.h>
1.9 -
1.10 -namespace hugo {
1.11 -
1.12 - template<typename Graph>
1.13 - class TrivGraphWrapper {
1.14 - protected:
1.15 - Graph* graph;
1.16 -
1.17 - public:
1.18 - typedef Graph BaseGraph;
1.19 -
1.20 - typedef typename Graph::Node Node;
1.21 - class NodeIt : public Graph::NodeIt {
1.22 - public:
1.23 - NodeIt() { }
1.24 - NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
1.25 - NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
1.26 - NodeIt(const TrivGraphWrapper<Graph>& _G) :
1.27 - Graph::NodeIt(*(_G.graph)) { }
1.28 - };
1.29 - typedef typename Graph::Edge Edge;
1.30 - //typedef typename Graph::OutEdgeIt OutEdgeIt;
1.31 - class OutEdgeIt : public Graph::OutEdgeIt {
1.32 - public:
1.33 - OutEdgeIt() { }
1.34 - OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
1.35 - OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
1.36 - OutEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :
1.37 - Graph::OutEdgeIt(*(_G.graph), n) { }
1.38 - };
1.39 - //typedef typename Graph::InEdgeIt InEdgeIt;
1.40 - class InEdgeIt : public Graph::InEdgeIt {
1.41 - public:
1.42 - InEdgeIt() { }
1.43 - InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
1.44 - InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
1.45 - InEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :
1.46 - Graph::InEdgeIt(*(_G.graph), n) { }
1.47 - };
1.48 - //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.49 - //typedef typename Graph::EdgeIt EdgeIt;
1.50 - class EdgeIt : public Graph::EdgeIt {
1.51 - public:
1.52 - EdgeIt() { }
1.53 - EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
1.54 - EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
1.55 - EdgeIt(const TrivGraphWrapper<Graph>& _G) :
1.56 - Graph::EdgeIt(*(_G.graph)) { }
1.57 - };
1.58 -
1.59 - //TrivGraphWrapper() : graph(0) { }
1.60 - TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.61 -
1.62 -// void setGraph(Graph& _graph) { graph = &_graph; }
1.63 -// Graph& getGraph() const { return (*graph); }
1.64 -
1.65 - NodeIt& first(NodeIt& i) const {
1.66 - i=NodeIt(*this);
1.67 - return i;
1.68 - }
1.69 - EdgeIt& first(EdgeIt& i) const {
1.70 - i=EdgeIt(*this);
1.71 - return i;
1.72 - }
1.73 -// template<typename I> I& first(I& i) const {
1.74 -// //return graph->first(i);
1.75 -// i=I(*this);
1.76 -// return i;
1.77 -// }
1.78 - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.79 - i=OutEdgeIt(*this, p);
1.80 - return i;
1.81 - }
1.82 - InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.83 - i=InEdgeIt(*this, p);
1.84 - return i;
1.85 - }
1.86 -// template<typename I, typename P> I& first(I& i, const P& p) const {
1.87 -// //return graph->first(i, p);
1.88 -// i=I(*this, p);
1.89 -// return i;
1.90 -// }
1.91 -
1.92 -// template<typename I> I getNext(const I& i) const {
1.93 -// return graph->getNext(i); }
1.94 - template<typename I> I& next(I &i) const { graph->next(i); return i; }
1.95 -
1.96 - template< typename It > It first() const {
1.97 - It e; first(e); return e; }
1.98 -
1.99 - template< typename It > It first(const Node& v) const {
1.100 - It e; first(e, v); return e; }
1.101 -
1.102 - Node head(const Edge& e) const { return graph->head(e); }
1.103 - Node tail(const Edge& e) const { return graph->tail(e); }
1.104 -
1.105 - template<typename I> bool valid(const I& i) const
1.106 - { return graph->valid(i); }
1.107 -
1.108 - //template<typename I> void setInvalid(const I &i);
1.109 - //{ return graph->setInvalid(i); }
1.110 -
1.111 - int nodeNum() const { return graph->nodeNum(); }
1.112 - int edgeNum() const { return graph->edgeNum(); }
1.113 -
1.114 - template<typename I> Node aNode(const I& e) const {
1.115 - return graph->aNode(e); }
1.116 - template<typename I> Node bNode(const I& e) const {
1.117 - return graph->bNode(e); }
1.118 -
1.119 - Node addNode() const { return graph->addNode(); }
1.120 - Edge addEdge(const Node& tail, const Node& head) const {
1.121 - return graph->addEdge(tail, head); }
1.122 -
1.123 - template<typename I> void erase(const I& i) const { graph->erase(i); }
1.124 -
1.125 - void clear() const { graph->clear(); }
1.126 -
1.127 - template<typename T> class NodeMap : public Graph::NodeMap<T> {
1.128 - public:
1.129 - NodeMap(const TrivGraphWrapper<Graph>& _G) :
1.130 - Graph::NodeMap<T>(*(_G.graph)) { }
1.131 - NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :
1.132 - Graph::NodeMap<T>(*(_G.graph), a) { }
1.133 - };
1.134 -
1.135 - template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
1.136 - public:
1.137 - EdgeMap(const TrivGraphWrapper<Graph>& _G) :
1.138 - Graph::EdgeMap<T>(*(_G.graph)) { }
1.139 - EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :
1.140 - Graph::EdgeMap<T>(*(_G.graph), a) { }
1.141 - };
1.142 -
1.143 - template<typename Map, typename T> class NodeMapWrapper {
1.144 - protected:
1.145 - Map* map;
1.146 - public:
1.147 - NodeMapWrapper(Map& _map) : map(&_map) { }
1.148 - //template<typename T>
1.149 - void set(Node n, T a) { map->set(n, a); }
1.150 - //template<typename T>
1.151 - T get(Node n) const { return map->get(n); }
1.152 - };
1.153 -
1.154 - template<typename Map, typename T> class EdgeMapWrapper {
1.155 - protected:
1.156 - Map* map;
1.157 - public:
1.158 - EdgeMapWrapper(Map& _map) : map(&_map) { }
1.159 - //template<typename T>
1.160 - void set(Edge n, T a) { map->set(n, a); }
1.161 - //template<typename T>
1.162 - T get(Edge n) const { return map->get(n); }
1.163 - };
1.164 - };
1.165 -
1.166 - template<typename GraphWrapper>
1.167 - class GraphWrapperSkeleton {
1.168 - protected:
1.169 - GraphWrapper gw;
1.170 -
1.171 - public:
1.172 - //typedef typename GraphWrapper::BaseGraph BaseGraph;
1.173 -
1.174 -// typedef typename GraphWrapper::Node Node;
1.175 -// typedef typename GraphWrapper::NodeIt NodeIt;
1.176 -
1.177 -// typedef typename GraphWrapper::Edge Edge;
1.178 -// typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
1.179 -// typedef typename GraphWrapper::InEdgeIt InEdgeIt;
1.180 -// //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;
1.181 -// typedef typename GraphWrapper::EdgeIt EdgeIt;
1.182 -
1.183 - typedef typename GraphWrapper::Node Node;
1.184 - class NodeIt : public GraphWrapper::NodeIt {
1.185 - public:
1.186 - NodeIt() { }
1.187 - NodeIt(const typename GraphWrapper::NodeIt& n) :
1.188 - GraphWrapper::NodeIt(n) { }
1.189 - NodeIt(const Invalid& i) : GraphWrapper::NodeIt(i) { }
1.190 - NodeIt(const GraphWrapperSkeleton<GraphWrapper>& _G) :
1.191 - GraphWrapper::NodeIt(_G.gw) { }
1.192 - };
1.193 - typedef typename GraphWrapper::Edge Edge;
1.194 - //typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
1.195 - class OutEdgeIt : public GraphWrapper::OutEdgeIt {
1.196 - public:
1.197 - OutEdgeIt() { }
1.198 - OutEdgeIt(const typename GraphWrapper::OutEdgeIt& e) :
1.199 - GraphWrapper::OutEdgeIt(e) { }
1.200 - OutEdgeIt(const Invalid& i) : GraphWrapper::OutEdgeIt(i) { }
1.201 - OutEdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G, const Node& n) :
1.202 - GraphWrapper::OutEdgeIt(_G.gw, n) { }
1.203 - };
1.204 - //typedef typename GraphWrapper::InEdgeIt InEdgeIt;
1.205 - class InEdgeIt : public GraphWrapper::InEdgeIt {
1.206 - public:
1.207 - InEdgeIt() { }
1.208 - InEdgeIt(const typename GraphWrapper::InEdgeIt& e) :
1.209 - GraphWrapper::InEdgeIt(e) { }
1.210 - InEdgeIt(const Invalid& i) : GraphWrapper::InEdgeIt(i) { }
1.211 - InEdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G, const Node& n) :
1.212 - GraphWrapper::InEdgeIt(_G.gw, n) { }
1.213 - };
1.214 - //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;
1.215 - //typedef typename GraphWrapper::EdgeIt EdgeIt;
1.216 - class EdgeIt : public GraphWrapper::EdgeIt {
1.217 - public:
1.218 - EdgeIt() { }
1.219 - EdgeIt(const typename GraphWrapper::EdgeIt& e) :
1.220 - GraphWrapper::EdgeIt(e) { }
1.221 - EdgeIt(const Invalid& i) : GraphWrapper::EdgeIt(i) { }
1.222 - EdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G) :
1.223 - GraphWrapper::EdgeIt(_G.gw) { }
1.224 - };
1.225 -
1.226 -
1.227 - //GraphWrapperSkeleton() : gw() { }
1.228 - GraphWrapperSkeleton(GraphWrapper _gw) : gw(_gw) { }
1.229 -
1.230 - //void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); }
1.231 - //BaseGraph& getGraph() const { return gw.getGraph(); }
1.232 -
1.233 - template<typename I> I& first(I& i) const {
1.234 - i=I(*this);
1.235 - return i;
1.236 - }
1.237 - template<typename I, typename P> I& first(I& i, const P& p) const {
1.238 - i=I(*this, p);
1.239 - return i;
1.240 - }
1.241 -
1.242 -// template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
1.243 - template<typename I> I& next(I &i) const { gw.next(i); return i; }
1.244 -
1.245 - template< typename It > It first() const {
1.246 - It e; this->first(e); return e; }
1.247 -
1.248 - template< typename It > It first(const Node& v) const {
1.249 - It e; this->first(e, v); return e; }
1.250 -
1.251 - Node head(const Edge& e) const { return gw.head(e); }
1.252 - Node tail(const Edge& e) const { return gw.tail(e); }
1.253 -
1.254 - template<typename I> bool valid(const I& i) const { return gw.valid(i); }
1.255 -
1.256 - //template<typename I> void setInvalid(const I &i);
1.257 - //{ return graph->setInvalid(i); }
1.258 -
1.259 - int nodeNum() const { return gw.nodeNum(); }
1.260 - int edgeNum() const { return gw.edgeNum(); }
1.261 -
1.262 - template<typename I> Node aNode(const I& e) const { return gw.aNode(e); }
1.263 - template<typename I> Node bNode(const I& e) const { return gw.bNode(e); }
1.264 -
1.265 - Node addNode() const { return gw.addNode(); }
1.266 - Edge addEdge(const Node& tail, const Node& head) const {
1.267 - return gw.addEdge(tail, head); }
1.268 -
1.269 - template<typename I> void erase(const I& i) const { gw.erase(i); }
1.270 -
1.271 - void clear() const { gw.clear(); }
1.272 -
1.273 - template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
1.274 - public:
1.275 - NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) :
1.276 - GraphWrapper::NodeMap<T>(_G.gw) { }
1.277 - NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) :
1.278 - GraphWrapper::NodeMap<T>(_G.gw, a) { }
1.279 - };
1.280 -
1.281 - template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
1.282 - public:
1.283 - EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) :
1.284 - GraphWrapper::EdgeMap<T>(_G.gw) { }
1.285 - EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) :
1.286 - GraphWrapper::EdgeMap<T>(_G.gw, a) { }
1.287 - };
1.288 - };
1.289 -
1.290 -// template<typename Graph>
1.291 -// class RevGraphWrapper
1.292 -// {
1.293 -// protected:
1.294 -// Graph* graph;
1.295 -
1.296 -// public:
1.297 -// typedef Graph BaseGraph;
1.298 -
1.299 -// typedef typename Graph::Node Node;
1.300 -// typedef typename Graph::NodeIt NodeIt;
1.301 -
1.302 -// typedef typename Graph::Edge Edge;
1.303 -// typedef typename Graph::OutEdgeIt InEdgeIt;
1.304 -// typedef typename Graph::InEdgeIt OutEdgeIt;
1.305 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.306 -// typedef typename Graph::EdgeIt EdgeIt;
1.307 -
1.308 -// //RevGraphWrapper() : graph(0) { }
1.309 -// RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.310 -
1.311 -// void setGraph(Graph& _graph) { graph = &_graph; }
1.312 -// Graph& getGraph() const { return (*graph); }
1.313 -
1.314 -// template<typename I> I& first(I& i) const { return graph->first(i); }
1.315 -// template<typename I, typename P> I& first(I& i, const P& p) const {
1.316 -// return graph->first(i, p); }
1.317 -
1.318 -// template<typename I> I getNext(const I& i) const {
1.319 -// return graph->getNext(i); }
1.320 -// template<typename I> I& next(I &i) const { return graph->next(i); }
1.321 -
1.322 -// template< typename It > It first() const {
1.323 -// It e; first(e); return e; }
1.324 -
1.325 -// template< typename It > It first(const Node& v) const {
1.326 -// It e; first(e, v); return e; }
1.327 -
1.328 -// Node head(const Edge& e) const { return graph->tail(e); }
1.329 -// Node tail(const Edge& e) const { return graph->head(e); }
1.330 -
1.331 -// template<typename I> bool valid(const I& i) const
1.332 -// { return graph->valid(i); }
1.333 -
1.334 -// //template<typename I> void setInvalid(const I &i);
1.335 -// //{ return graph->setInvalid(i); }
1.336 -
1.337 -// template<typename I> Node aNode(const I& e) const {
1.338 -// return graph->aNode(e); }
1.339 -// template<typename I> Node bNode(const I& e) const {
1.340 -// return graph->bNode(e); }
1.341 -
1.342 -// Node addNode() const { return graph->addNode(); }
1.343 -// Edge addEdge(const Node& tail, const Node& head) const {
1.344 -// return graph->addEdge(tail, head); }
1.345 -
1.346 -// int nodeNum() const { return graph->nodeNum(); }
1.347 -// int edgeNum() const { return graph->edgeNum(); }
1.348 -
1.349 -// template<typename I> void erase(const I& i) const { graph->erase(i); }
1.350 -
1.351 -// void clear() const { graph->clear(); }
1.352 -
1.353 -// template<typename T> class NodeMap : public Graph::NodeMap<T> {
1.354 -// public:
1.355 -// NodeMap(const RevGraphWrapper<Graph>& _G) :
1.356 -// Graph::NodeMap<T>(_G.getGraph()) { }
1.357 -// NodeMap(const RevGraphWrapper<Graph>& _G, T a) :
1.358 -// Graph::NodeMap<T>(_G.getGraph(), a) { }
1.359 -// };
1.360 -
1.361 -// template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
1.362 -// public:
1.363 -// EdgeMap(const RevGraphWrapper<Graph>& _G) :
1.364 -// Graph::EdgeMap<T>(_G.getGraph()) { }
1.365 -// EdgeMap(const RevGraphWrapper<Graph>& _G, T a) :
1.366 -// Graph::EdgeMap<T>(_G.getGraph(), a) { }
1.367 -// };
1.368 -// };
1.369 -
1.370 -// template<typename /*Graph*/GraphWrapper
1.371 -// /*=typename GraphWrapperSkeleton< TrivGraphWrapper<Graph>*/ >
1.372 -// class RevGraphWrapper :
1.373 -// public GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/ {
1.374 -// protected:
1.375 -// //Graph* graph;
1.376 -
1.377 -// public:
1.378 -// //typedef Graph BaseGraph;
1.379 -
1.380 -// //typedef typename Graph::Node Node;
1.381 -// //typedef typename Graph::NodeIt NodeIt;
1.382 -
1.383 -// //typedef typename Graph::Edge Edge;
1.384 -// typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::OutEdgeIt InEdgeIt;
1.385 -// typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::InEdgeIt OutEdgeIt;
1.386 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.387 -// //typedef typename Graph::EdgeIt EdgeIt;
1.388 -
1.389 -// //RevGraphWrapper() : graph(0) { }
1.390 -// RevGraphWrapper(GraphWrapper _gw/*BaseGraph& _graph*/) : GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/(_gw/*TrivGraphWrapper<Graph>(_graph)*/) { }
1.391 -
1.392 -// //void setGraph(Graph& _graph) { graph = &_graph; }
1.393 -// //Graph& getGraph() const { return (*graph); }
1.394 -
1.395 -// //template<typename I> I& first(I& i) const { return graph->first(i); }
1.396 -// //template<typename I, typename P> I& first(I& i, const P& p) const {
1.397 -// // return graph->first(i, p); }
1.398 -
1.399 -// //template<typename I> I getNext(const I& i) const {
1.400 -// // return graph->getNext(i); }
1.401 -// //template<typename I> I& next(I &i) const { return graph->next(i); }
1.402 -
1.403 -// //template< typename It > It first() const {
1.404 -// // It e; first(e); return e; }
1.405 -
1.406 -// //template< typename It > It first(const Node& v) const {
1.407 -// // It e; first(e, v); return e; }
1.408 -
1.409 -// //Node head(const Edge& e) const { return graph->tail(e); }
1.410 -// //Node tail(const Edge& e) const { return graph->head(e); }
1.411 -
1.412 -// //template<typename I> bool valid(const I& i) const
1.413 -// // { return graph->valid(i); }
1.414 -
1.415 -// //template<typename I> void setInvalid(const I &i);
1.416 -// //{ return graph->setInvalid(i); }
1.417 -
1.418 -// //template<typename I> Node aNode(const I& e) const {
1.419 -// // return graph->aNode(e); }
1.420 -// //template<typename I> Node bNode(const I& e) const {
1.421 -// // return graph->bNode(e); }
1.422 -
1.423 -// //Node addNode() const { return graph->addNode(); }
1.424 -// //Edge addEdge(const Node& tail, const Node& head) const {
1.425 -// // return graph->addEdge(tail, head); }
1.426 -
1.427 -// //int nodeNum() const { return graph->nodeNum(); }
1.428 -// //int edgeNum() const { return graph->edgeNum(); }
1.429 -
1.430 -// //template<typename I> void erase(const I& i) const { graph->erase(i); }
1.431 -
1.432 -// //void clear() const { graph->clear(); }
1.433 -
1.434 -// template<typename T> class NodeMap :
1.435 -// public GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>
1.436 -// {
1.437 -// public:
1.438 -// NodeMap(const RevGraphWrapper<GraphWrapper>& _gw) :
1.439 -// GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw) { }
1.440 -// NodeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) :
1.441 -// GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw, a) { }
1.442 -// };
1.443 -
1.444 -// template<typename T> class EdgeMap :
1.445 -// public GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T> {
1.446 -// public:
1.447 -// EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw) :
1.448 -// GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw) { }
1.449 -// EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) :
1.450 -// GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw, a) { }
1.451 -// };
1.452 -// };
1.453 -
1.454 -
1.455 - template<typename GraphWrapper>
1.456 - class RevGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
1.457 - public:
1.458 - typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
1.459 - typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
1.460 - typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt InEdgeIt;
1.461 - typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt OutEdgeIt;
1.462 -
1.463 - RevGraphWrapper(GraphWrapper _gw) :
1.464 - GraphWrapperSkeleton<GraphWrapper>(_gw) { }
1.465 -
1.466 - Node head(const Edge& e) const
1.467 - { return GraphWrapperSkeleton<GraphWrapper>::tail(e); }
1.468 - Node tail(const Edge& e) const
1.469 - { return GraphWrapperSkeleton<GraphWrapper>::head(e); }
1.470 - };
1.471 -
1.472 - //Subgraph on the same node-set and partial edge-set
1.473 - template<typename GraphWrapper, typename EdgeFilterMap>
1.474 - class SubGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
1.475 - protected:
1.476 - EdgeFilterMap* filter_map;
1.477 - public:
1.478 - typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
1.479 - typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
1.480 - typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
1.481 - typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt;
1.482 - typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt;
1.483 - typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt;
1.484 -
1.485 - SubGraphWrapper(GraphWrapper _gw, EdgeFilterMap& _filter_map) :
1.486 - GraphWrapperSkeleton<GraphWrapper>(_gw), filter_map(&_filter_map) { }
1.487 -
1.488 - template<typename I> I& first(I& i) const {
1.489 - gw.first(i);
1.490 - while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
1.491 - return i;
1.492 - }
1.493 - template<typename I, typename P> I& first(I& i, const P& p) const {
1.494 - gw.first(i, p);
1.495 - while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
1.496 - return i;
1.497 - }
1.498 -
1.499 - //template<typename I> I getNext(const I& i) const {
1.500 - // return gw.getNext(i);
1.501 - //}
1.502 - template<typename I> I& next(I &i) const {
1.503 - gw.next(i);
1.504 - while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
1.505 - return i;
1.506 - }
1.507 -
1.508 - template< typename It > It first() const {
1.509 - It e; this->first(e); return e; }
1.510 -
1.511 - template< typename It > It first(const Node& v) const {
1.512 - It e; this->first(e, v); return e; }
1.513 - };
1.514 -
1.515 -// template<typename GraphWrapper>
1.516 -// class UndirGraphWrapper {
1.517 -// protected:
1.518 -// //Graph* graph;
1.519 -// GraphWrapper gw;
1.520 -
1.521 -// public:
1.522 -// typedef GraphWrapper BaseGraph;
1.523 -
1.524 -// typedef typename GraphWrapper::Node Node;
1.525 -// typedef typename GraphWrapper::NodeIt NodeIt;
1.526 -
1.527 -// //typedef typename Graph::Edge Edge;
1.528 -// //typedef typename Graph::OutEdgeIt OutEdgeIt;
1.529 -// //typedef typename Graph::InEdgeIt InEdgeIt;
1.530 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.531 -// //typedef typename Graph::EdgeIt EdgeIt;
1.532 -
1.533 -// //private:
1.534 -// typedef typename GraphWrapper::Edge GraphEdge;
1.535 -// typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;
1.536 -// typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;
1.537 -// //public:
1.538 -
1.539 -// //UndirGraphWrapper() : graph(0) { }
1.540 -// UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
1.541 -
1.542 -// //void setGraph(Graph& _graph) { graph = &_graph; }
1.543 -// //Graph& getGraph() const { return (*graph); }
1.544 -
1.545 -// class Edge {
1.546 -// friend class UndirGraphWrapper<GraphWrapper>;
1.547 -// bool out_or_in; //true iff out
1.548 -// GraphOutEdgeIt out;
1.549 -// GraphInEdgeIt in;
1.550 -// public:
1.551 -// Edge() : out_or_in(), out(), in() { }
1.552 -// Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
1.553 -// operator GraphEdge() const {
1.554 -// if (out_or_in) return(out); else return(in);
1.555 -// }
1.556 -// friend bool operator==(const Edge& u, const Edge& v) {
1.557 -// if (v.out_or_in)
1.558 -// return (u.out_or_in && u.out==v.out);
1.559 -// else
1.560 -// return (!u.out_or_in && u.in==v.in);
1.561 -// }
1.562 -// friend bool operator!=(const Edge& u, const Edge& v) {
1.563 -// if (v.out_or_in)
1.564 -// return (!u.out_or_in || u.out!=v.out);
1.565 -// else
1.566 -// return (u.out_or_in || u.in!=v.in);
1.567 -// }
1.568 -// };
1.569 -
1.570 -// class OutEdgeIt : public Edge {
1.571 -// friend class UndirGraphWrapper<GraphWrapper>;
1.572 -// public:
1.573 -// OutEdgeIt() : Edge() { }
1.574 -// OutEdgeIt(const Invalid& i) : Edge(i) { }
1.575 -// OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)
1.576 -// : Edge() {
1.577 -// out_or_in=true;
1.578 -// _G.gw.first(out, n);
1.579 -// if (!(_G.gw.valid(out))) {
1.580 -// out_or_in=false;
1.581 -// _G.gw.first(in, n);
1.582 -// }
1.583 -// }
1.584 -// };
1.585 -
1.586 -// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1.587 -// e.out_or_in=true;
1.588 -// gw.first(e.out, n);
1.589 -// if (!(gw.valid(e.out))) {
1.590 -// e.out_or_in=false;
1.591 -// gw.first(e.in, n);
1.592 -// }
1.593 -// return e;
1.594 -// }
1.595 -
1.596 -// OutEdgeIt& next(OutEdgeIt& e) const {
1.597 -// if (e.out_or_in) {
1.598 -// Node n=gw.tail(e.out);
1.599 -// gw.next(e.out);
1.600 -// if (!gw.valid(e.out)) {
1.601 -// e.out_or_in=false;
1.602 -// gw.first(e.in, n);
1.603 -// }
1.604 -// } else {
1.605 -// gw.next(e.in);
1.606 -// }
1.607 -// return e;
1.608 -// }
1.609 -
1.610 -// Node aNode(const OutEdgeIt& e) const {
1.611 -// if (e.out_or_in) return gw.tail(e); else return gw.head(e); }
1.612 -// Node bNode(const OutEdgeIt& e) const {
1.613 -// if (e.out_or_in) return gw.head(e); else return gw.tail(e); }
1.614 -
1.615 -// typedef OutEdgeIt InEdgeIt;
1.616 -
1.617 -// template<typename I> I& first(I& i) const { return gw.first(i); }
1.618 -// // template<typename I, typename P> I& first(I& i, const P& p) const {
1.619 -// // return graph->first(i, p); }
1.620 -
1.621 -// template<typename I> I getNext(const I& i) const {
1.622 -// return gw.getNext(i); }
1.623 -// template<typename I> I& next(I &i) const { return gw.next(i); }
1.624 -
1.625 -// template< typename It > It first() const {
1.626 -// It e; first(e); return e; }
1.627 -
1.628 -// template< typename It > It first(const Node& v) const {
1.629 -// It e; first(e, v); return e; }
1.630 -
1.631 -// Node head(const Edge& e) const { return gw.head(e); }
1.632 -// Node tail(const Edge& e) const { return gw.tail(e); }
1.633 -
1.634 -// template<typename I> bool valid(const I& i) const
1.635 -// { return gw.valid(i); }
1.636 -
1.637 -// //template<typename I> void setInvalid(const I &i);
1.638 -// //{ return graph->setInvalid(i); }
1.639 -
1.640 -// int nodeNum() const { return gw.nodeNum(); }
1.641 -// int edgeNum() const { return gw.edgeNum(); }
1.642 -
1.643 -// // template<typename I> Node aNode(const I& e) const {
1.644 -// // return graph->aNode(e); }
1.645 -// // template<typename I> Node bNode(const I& e) const {
1.646 -// // return graph->bNode(e); }
1.647 -
1.648 -// Node addNode() const { return gw.addNode(); }
1.649 -// // FIXME: ez igy nem jo, mert nem
1.650 -// // Edge addEdge(const Node& tail, const Node& head) const {
1.651 -// // return graph->addEdge(tail, head); }
1.652 -
1.653 -// template<typename I> void erase(const I& i) const { gw.erase(i); }
1.654 -
1.655 -// void clear() const { gw.clear(); }
1.656 -
1.657 -// template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
1.658 -// public:
1.659 -// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
1.660 -// GraphWrapper::NodeMap<T>(_G.gw) { }
1.661 -// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
1.662 -// GraphWrapper::NodeMap<T>(_G.gw, a) { }
1.663 -// };
1.664 -
1.665 -// template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
1.666 -// public:
1.667 -// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
1.668 -// GraphWrapper::EdgeMap<T>(_G.gw) { }
1.669 -// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
1.670 -// GraphWrapper::EdgeMap<T>(_G.gw, a) { }
1.671 -// };
1.672 -// };
1.673 -
1.674 -
1.675 - template<typename GraphWrapper>
1.676 - class UndirGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
1.677 - protected:
1.678 -// GraphWrapper gw;
1.679 -
1.680 - public:
1.681 - //typedef GraphWrapper BaseGraph;
1.682 -
1.683 - typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
1.684 - typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
1.685 -
1.686 - //private:
1.687 - //FIXME ezeknek valojaban a GraphWrapper megfelelo dolgai kellene hogy
1.688 - //legyenek, at kell irni
1.689 - typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
1.690 - GraphWrapper::Edge GraphEdge;
1.691 - typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
1.692 - GraphWrapper::OutEdgeIt GraphOutEdgeIt;
1.693 - typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
1.694 - GraphWrapper::InEdgeIt GraphInEdgeIt;
1.695 - //public:
1.696 -
1.697 - //UndirGraphWrapper() : graph(0) { }
1.698 - UndirGraphWrapper(GraphWrapper _gw) :
1.699 - GraphWrapperSkeleton<GraphWrapper>(_gw) { }
1.700 -
1.701 - //UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
1.702 -
1.703 - //void setGraph(Graph& _graph) { graph = &_graph; }
1.704 - //Graph& getGraph() const { return (*graph); }
1.705 -
1.706 - class Edge {
1.707 - friend class UndirGraphWrapper<GraphWrapper>;
1.708 - bool out_or_in; //true iff out
1.709 - GraphOutEdgeIt out;
1.710 - GraphInEdgeIt in;
1.711 - public:
1.712 - Edge() : out_or_in(), out(), in() { }
1.713 - Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
1.714 - operator GraphEdge() const {
1.715 - if (out_or_in) return(out); else return(in);
1.716 - }
1.717 -//FIXME
1.718 -//2 edges are equal if they "refer" to the same physical edge
1.719 -//is it good?
1.720 - friend bool operator==(const Edge& u, const Edge& v) {
1.721 - if (v.out_or_in)
1.722 - if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in);
1.723 - //return (u.out_or_in && u.out==v.out);
1.724 - else
1.725 - if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in);
1.726 - //return (!u.out_or_in && u.in==v.in);
1.727 - }
1.728 - friend bool operator!=(const Edge& u, const Edge& v) {
1.729 - if (v.out_or_in)
1.730 - if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in);
1.731 - //return (!u.out_or_in || u.out!=v.out);
1.732 - else
1.733 - if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in);
1.734 - //return (u.out_or_in || u.in!=v.in);
1.735 - }
1.736 - };
1.737 -
1.738 - class OutEdgeIt : public Edge {
1.739 - friend class UndirGraphWrapper<GraphWrapper>;
1.740 - public:
1.741 - OutEdgeIt() : Edge() { }
1.742 - OutEdgeIt(const Invalid& i) : Edge(i) { }
1.743 - OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)
1.744 - : Edge() {
1.745 - out_or_in=true; _G.gw.first(out, n);
1.746 - if (!(_G.gw.valid(out))) { out_or_in=false; _G.gw.first(in, n); }
1.747 - }
1.748 - };
1.749 -
1.750 - typedef OutEdgeIt InEdgeIt;
1.751 -
1.752 - class EdgeIt : public Edge {
1.753 - friend class UndirGraphWrapper<GraphWrapper>;
1.754 - protected:
1.755 - NodeIt v;
1.756 - public:
1.757 - EdgeIt() : Edge() { }
1.758 - EdgeIt(const Invalid& i) : Edge(i) { }
1.759 - EdgeIt(const UndirGraphWrapper<GraphWrapper>& _G)
1.760 - : Edge() {
1.761 - out_or_in=true;
1.762 - //Node v;
1.763 - _G.first(v);
1.764 - if (_G.valid(v)) _G.gw.first(out); else out=INVALID;
1.765 - while (_G.valid(v) && !_G.gw.valid(out)) {
1.766 - _G.gw.next(v);
1.767 - if (_G.valid(v)) _G.gw.first(out);
1.768 - }
1.769 - }
1.770 - };
1.771 -
1.772 - OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1.773 - e.out_or_in=true; gw.first(e.out, n);
1.774 - if (!(gw.valid(e.out))) { e.out_or_in=false; gw.first(e.in, n); }
1.775 - return e;
1.776 - }
1.777 -
1.778 - EdgeIt& first(EdgeIt& e) const {
1.779 - e.out_or_in=true;
1.780 - //NodeIt v;
1.781 - first(e.v);
1.782 - if (valid(e.v)) gw.first(e.out, e.v); else e.out=INVALID;
1.783 - while (valid(e.v) && !gw.valid(e.out)) {
1.784 - gw.next(e.v);
1.785 - if (valid(e.v)) gw.first(e.out, e.v);
1.786 - }
1.787 - return e;
1.788 - }
1.789 -
1.790 - template<typename I> I& first(I& i) const { gw.first(i); return i; }
1.791 - template<typename I, typename P> I& first(I& i, const P& p) const {
1.792 - gw.first(i, p); return i; }
1.793 -
1.794 - OutEdgeIt& next(OutEdgeIt& e) const {
1.795 - if (e.out_or_in) {
1.796 - Node n=gw.tail(e.out);
1.797 - gw.next(e.out);
1.798 - if (!gw.valid(e.out)) { e.out_or_in=false; gw.first(e.in, n); }
1.799 - } else {
1.800 - gw.next(e.in);
1.801 - }
1.802 - return e;
1.803 - }
1.804 -
1.805 - EdgeIt& next(EdgeIt& e) const {
1.806 - //NodeIt v=tail(e);
1.807 - gw.next(e.out);
1.808 - while (valid(e.v) && !gw.valid(e.out)) {
1.809 - next(e.v);
1.810 - if (valid(e.v)) gw.first(e.out, e.v);
1.811 - }
1.812 - return e;
1.813 - }
1.814 -
1.815 - template<typename I> I& next(I &i) const { return gw.next(i); }
1.816 -// template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
1.817 -
1.818 - template< typename It > It first() const {
1.819 - It e; first(e); return e; }
1.820 -
1.821 - template< typename It > It first(const Node& v) const {
1.822 - It e; first(e, v); return e; }
1.823 -
1.824 -// Node head(const Edge& e) const { return gw.head(e); }
1.825 -// Node tail(const Edge& e) const { return gw.tail(e); }
1.826 -
1.827 -// template<typename I> bool valid(const I& i) const
1.828 -// { return gw.valid(i); }
1.829 -
1.830 -// int nodeNum() const { return gw.nodeNum(); }
1.831 -// int edgeNum() const { return gw.edgeNum(); }
1.832 -
1.833 -// template<typename I> Node aNode(const I& e) const {
1.834 -// return graph->aNode(e); }
1.835 -// template<typename I> Node bNode(const I& e) const {
1.836 -// return graph->bNode(e); }
1.837 -
1.838 - Node aNode(const OutEdgeIt& e) const {
1.839 - if (e.out_or_in) return gw.tail(e); else return gw.head(e); }
1.840 - Node bNode(const OutEdgeIt& e) const {
1.841 - if (e.out_or_in) return gw.head(e); else return gw.tail(e); }
1.842 -
1.843 -// Node addNode() const { return gw.addNode(); }
1.844 -
1.845 -// FIXME: ez igy nem jo, mert nem
1.846 -// Edge addEdge(const Node& tail, const Node& head) const {
1.847 -// return graph->addEdge(tail, head); }
1.848 -
1.849 -// template<typename I> void erase(const I& i) const { gw.erase(i); }
1.850 -
1.851 -// void clear() const { gw.clear(); }
1.852 -
1.853 -// template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
1.854 -// public:
1.855 -// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
1.856 -// GraphWrapper::NodeMap<T>(_G.gw) { }
1.857 -// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
1.858 -// GraphWrapper::NodeMap<T>(_G.gw, a) { }
1.859 -// };
1.860 -
1.861 -// template<typename T> class EdgeMap :
1.862 -// public GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T> {
1.863 -// public:
1.864 -// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
1.865 -// GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T>(_G.gw) { }
1.866 -// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
1.867 -// GraphWrapper::EdgeMap<T>(_G.gw, a) { }
1.868 -// };
1.869 - };
1.870 -
1.871 -
1.872 -
1.873 -
1.874 -
1.875 -// template<typename Graph>
1.876 -// class SymGraphWrapper
1.877 -// {
1.878 -// Graph* graph;
1.879 -
1.880 -// public:
1.881 -// typedef Graph BaseGraph;
1.882 -
1.883 -// typedef typename Graph::Node Node;
1.884 -// typedef typename Graph::Edge Edge;
1.885 -
1.886 -// typedef typename Graph::NodeIt NodeIt;
1.887 -
1.888 -// //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
1.889 -// //iranyitatlant, ami van
1.890 -// //mert csak 1 dolgot lehet be typedef-elni
1.891 -// typedef typename Graph::OutEdgeIt SymEdgeIt;
1.892 -// //typedef typename Graph::InEdgeIt SymEdgeIt;
1.893 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.894 -// typedef typename Graph::EdgeIt EdgeIt;
1.895 -
1.896 -// int nodeNum() const { return graph->nodeNum(); }
1.897 -// int edgeNum() const { return graph->edgeNum(); }
1.898 -
1.899 -// template<typename I> I& first(I& i) const { return graph->first(i); }
1.900 -// template<typename I, typename P> I& first(I& i, const P& p) const {
1.901 -// return graph->first(i, p); }
1.902 -// //template<typename I> I next(const I i); { return graph->goNext(i); }
1.903 -// //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
1.904 -
1.905 -// template< typename It > It first() const {
1.906 -// It e; first(e); return e; }
1.907 -
1.908 -// template< typename It > It first(Node v) const {
1.909 -// It e; first(e, v); return e; }
1.910 -
1.911 -// Node head(const Edge& e) const { return graph->head(e); }
1.912 -// Node tail(const Edge& e) const { return graph->tail(e); }
1.913 -
1.914 -// template<typename I> Node aNode(const I& e) const {
1.915 -// return graph->aNode(e); }
1.916 -// template<typename I> Node bNode(const I& e) const {
1.917 -// return graph->bNode(e); }
1.918 -
1.919 -// //template<typename I> bool valid(const I i);
1.920 -// //{ return graph->valid(i); }
1.921 -
1.922 -// //template<typename I> void setInvalid(const I &i);
1.923 -// //{ return graph->setInvalid(i); }
1.924 -
1.925 -// Node addNode() { return graph->addNode(); }
1.926 -// Edge addEdge(const Node& tail, const Node& head) {
1.927 -// return graph->addEdge(tail, head); }
1.928 -
1.929 -// template<typename I> void erase(const I& i) { graph->erase(i); }
1.930 -
1.931 -// void clear() { graph->clear(); }
1.932 -
1.933 -// template<typename T> class NodeMap : public Graph::NodeMap<T> { };
1.934 -// template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
1.935 -
1.936 -// void setGraph(Graph& _graph) { graph = &_graph; }
1.937 -// Graph& getGraph() { return (*graph); }
1.938 -
1.939 -// //SymGraphWrapper() : graph(0) { }
1.940 -// SymGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.941 -// };
1.942 -
1.943 -
1.944 - template<typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
1.945 - class ResGraphWrapper : public GraphWrapperSkeleton<GraphWrapper>{
1.946 - public:
1.947 - //typedef Graph BaseGraph;
1.948 - //typedef TrivGraphWrapper<const Graph> GraphWrapper;
1.949 - typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
1.950 - typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
1.951 - private:
1.952 - typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
1.953 - GraphWrapper::OutEdgeIt OldOutEdgeIt;
1.954 - typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
1.955 - GraphWrapper::InEdgeIt OldInEdgeIt;
1.956 -
1.957 - typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/
1.958 - GraphWrapper::Edge OldEdge;
1.959 - protected:
1.960 - //const Graph* graph;
1.961 - //GraphWrapper gw;
1.962 - FlowMap* flow;
1.963 - const CapacityMap* capacity;
1.964 - public:
1.965 -
1.966 - ResGraphWrapper(const GraphWrapper& _gw, FlowMap& _flow,
1.967 - const CapacityMap& _capacity) :
1.968 - GraphWrapperSkeleton<GraphWrapper>(_gw),
1.969 - flow(&_flow), capacity(&_capacity) { }
1.970 -
1.971 - //void setGraph(const Graph& _graph) { graph = &_graph; }
1.972 - //const Graph& getGraph() const { return (*graph); }
1.973 -
1.974 - class Edge;
1.975 - class OutEdgeIt;
1.976 - friend class Edge;
1.977 - friend class OutEdgeIt;
1.978 -
1.979 - class Edge {
1.980 - friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
1.981 - protected:
1.982 - bool out_or_in; //true, iff out
1.983 - OldOutEdgeIt out;
1.984 - OldInEdgeIt in;
1.985 - public:
1.986 - Edge() : out_or_in(true) { }
1.987 - Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
1.988 -// bool valid() const {
1.989 -// return out_or_in && out.valid() || in.valid(); }
1.990 - friend bool operator==(const Edge& u, const Edge& v) {
1.991 - if (v.out_or_in)
1.992 - return (u.out_or_in && u.out==v.out);
1.993 - else
1.994 - return (!u.out_or_in && u.in==v.in);
1.995 - }
1.996 - friend bool operator!=(const Edge& u, const Edge& v) {
1.997 - if (v.out_or_in)
1.998 - return (!u.out_or_in || u.out!=v.out);
1.999 - else
1.1000 - return (u.out_or_in || u.in!=v.in);
1.1001 - }
1.1002 - operator OldEdge() {
1.1003 - if(out_or_in)
1.1004 - return out;
1.1005 - else
1.1006 - return in;
1.1007 - }
1.1008 - };
1.1009 -
1.1010 -
1.1011 - class OutEdgeIt : public Edge {
1.1012 - friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
1.1013 - public:
1.1014 - OutEdgeIt() { }
1.1015 - //FIXME
1.1016 - OutEdgeIt(const Edge& e) : Edge(e) { }
1.1017 - OutEdgeIt(const Invalid& i) : Edge(i) { }
1.1018 - protected:
1.1019 - OutEdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
1.1020 - resG.gw.first(out, v);
1.1021 - while( resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
1.1022 - if (!resG.gw.valid(out)) {
1.1023 - out_or_in=0;
1.1024 - resG.gw.first(in, v);
1.1025 - while( resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
1.1026 - }
1.1027 - }
1.1028 -// public:
1.1029 -// OutEdgeIt& operator++() {
1.1030 -// if (out_or_in) {
1.1031 -// Node v=/*resG->*/G->aNode(out);
1.1032 -// ++out;
1.1033 -// while( out.valid() && !(Edge::resCap()>0) ) { ++out; }
1.1034 -// if (!out.valid()) {
1.1035 -// out_or_in=0;
1.1036 -// G->first(in, v);
1.1037 -// while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.1038 -// }
1.1039 -// } else {
1.1040 -// ++in;
1.1041 -// while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.1042 -// }
1.1043 -// return *this;
1.1044 -// }
1.1045 - };
1.1046 -
1.1047 - //FIXME This is just for having InEdgeIt
1.1048 - typedef void InEdgeIt;
1.1049 -
1.1050 - class EdgeIt : public Edge {
1.1051 - friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;
1.1052 - NodeIt v;
1.1053 - public:
1.1054 - EdgeIt() { }
1.1055 - //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
1.1056 - EdgeIt(const Invalid& i) : Edge(i) { }
1.1057 - EdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG) : Edge() {
1.1058 - resG.gw.first(v);
1.1059 - if (resG.gw.valid(v)) resG.gw.first(out, v); else out=INVALID;
1.1060 - while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
1.1061 - while (resG.gw.valid(v) && !resG.gw.valid(out)) {
1.1062 - resG.gw.next(v);
1.1063 - if (resG.gw.valid(v)) resG.gw.first(out, v);
1.1064 - while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
1.1065 - }
1.1066 - if (!resG.gw.valid(out)) {
1.1067 - out_or_in=0;
1.1068 - resG.gw.first(v);
1.1069 - if (resG.gw.valid(v)) resG.gw.first(in, v); else in=INVALID;
1.1070 - while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
1.1071 - while (resG.gw.valid(v) && !resG.gw.valid(in)) {
1.1072 - resG.gw.next(v);
1.1073 - if (resG.gw.valid(v)) resG.gw.first(in, v);
1.1074 - while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
1.1075 - }
1.1076 - }
1.1077 - }
1.1078 -// EdgeIt& operator++() {
1.1079 -// if (out_or_in) {
1.1080 -// ++out;
1.1081 -// while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
1.1082 -// while (v.valid() && !out.valid()) {
1.1083 -// ++v;
1.1084 -// if (v.valid()) G->first(out, v);
1.1085 -// while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
1.1086 -// }
1.1087 -// if (!out.valid()) {
1.1088 -// out_or_in=0;
1.1089 -// G->first(v);
1.1090 -// if (v.valid()) G->first(in, v); else in=OldInEdgeIt();
1.1091 -// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.1092 -// while (v.valid() && !in.valid()) {
1.1093 -// ++v;
1.1094 -// if (v.valid()) G->first(in, v);
1.1095 -// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.1096 -// }
1.1097 -// }
1.1098 -// } else {
1.1099 -// ++in;
1.1100 -// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.1101 -// while (v.valid() && !in.valid()) {
1.1102 -// ++v;
1.1103 -// if (v.valid()) G->first(in, v);
1.1104 -// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1.1105 -// }
1.1106 -// }
1.1107 -// return *this;
1.1108 -// }
1.1109 - };
1.1110 -
1.1111 - NodeIt& first(NodeIt& v) const { gw.first(v); return v; }
1.1112 - OutEdgeIt& first(OutEdgeIt& e, Node v) const {
1.1113 - e=OutEdgeIt(*this, v);
1.1114 - return e;
1.1115 - }
1.1116 - EdgeIt& first(EdgeIt& e) const {
1.1117 - e=EdgeIt(*this);
1.1118 - return e;
1.1119 - }
1.1120 -
1.1121 - NodeIt& next(NodeIt& n) const { return gw.next(n); }
1.1122 -
1.1123 - OutEdgeIt& next(OutEdgeIt& e) const {
1.1124 - if (e.out_or_in) {
1.1125 - Node v=gw.aNode(e.out);
1.1126 - gw.next(e.out);
1.1127 - while( gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
1.1128 - if (!gw.valid(e.out)) {
1.1129 - e.out_or_in=0;
1.1130 - gw.first(e.in, v);
1.1131 - while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
1.1132 - }
1.1133 - } else {
1.1134 - gw.next(e.in);
1.1135 - while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
1.1136 - }
1.1137 - return e;
1.1138 - }
1.1139 -
1.1140 - EdgeIt& next(EdgeIt& e) const {
1.1141 - if (e.out_or_in) {
1.1142 - gw.next(e.out);
1.1143 - while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
1.1144 - while (gw.valid(e.v) && !gw.valid(e.out)) {
1.1145 - gw.next(e.v);
1.1146 - if (gw.valid(e.v)) gw.first(e.out, e.v);
1.1147 - while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
1.1148 - }
1.1149 - if (!gw.valid(e.out)) {
1.1150 - e.out_or_in=0;
1.1151 - gw.first(e.v);
1.1152 - if (gw.valid(e.v)) gw.first(e.in, e.v); else e.in=INVALID;
1.1153 - while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
1.1154 - while (gw.valid(e.v) && !gw.valid(e.in)) {
1.1155 - gw.next(e.v);
1.1156 - if (gw.valid(e.v)) gw.first(e.in, e.v);
1.1157 - while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
1.1158 - }
1.1159 - }
1.1160 - } else {
1.1161 - gw.next(e.in);
1.1162 - while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
1.1163 - while (gw.valid(e.v) && !gw.valid(e.in)) {
1.1164 - gw.next(e.v);
1.1165 - if (gw.valid(e.v)) gw.first(e.in, e.v);
1.1166 - while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
1.1167 - }
1.1168 - }
1.1169 - return e;
1.1170 - }
1.1171 -
1.1172 -
1.1173 - template< typename It >
1.1174 - It first() const {
1.1175 - It e;
1.1176 - first(e);
1.1177 - return e;
1.1178 - }
1.1179 -
1.1180 - template< typename It >
1.1181 - It first(Node v) const {
1.1182 - It e;
1.1183 - first(e, v);
1.1184 - return e;
1.1185 - }
1.1186 -
1.1187 - Node tail(Edge e) const {
1.1188 - return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); }
1.1189 - Node head(Edge e) const {
1.1190 - return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }
1.1191 -
1.1192 - Node aNode(OutEdgeIt e) const {
1.1193 - return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); }
1.1194 - Node bNode(OutEdgeIt e) const {
1.1195 - return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }
1.1196 -
1.1197 - int nodeNum() const { return gw.nodeNum(); }
1.1198 - //FIXME
1.1199 - //int edgeNum() const { return gw.edgeNum(); }
1.1200 -
1.1201 -
1.1202 - int id(Node v) const { return gw.id(v); }
1.1203 -
1.1204 - bool valid(Node n) const { return gw.valid(n); }
1.1205 - bool valid(Edge e) const {
1.1206 - return e.out_or_in ? gw.valid(e.out) : gw.valid(e.in); }
1.1207 -
1.1208 - void augment(const Edge& e, Number a) const {
1.1209 - if (e.out_or_in)
1.1210 - flow->set(e.out, flow->get(e.out)+a);
1.1211 - else
1.1212 - flow->set(e.in, flow->get(e.in)-a);
1.1213 - }
1.1214 -
1.1215 - Number resCap(const Edge& e) const {
1.1216 - if (e.out_or_in)
1.1217 - return (capacity->get(e.out)-flow->get(e.out));
1.1218 - else
1.1219 - return (flow->get(e.in));
1.1220 - }
1.1221 -
1.1222 - Number resCap(OldOutEdgeIt out) const {
1.1223 - return ( (*capacity)[out] - (*flow)[out]);
1.1224 - }
1.1225 -
1.1226 - Number resCap(OldInEdgeIt in) const {
1.1227 - return ( (*flow)[in] );
1.1228 - }
1.1229 -
1.1230 -// template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
1.1231 -// public:
1.1232 -// NodeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G)
1.1233 -// : GraphWrapper::NodeMap<T>(_G.gw) { }
1.1234 -// NodeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G,
1.1235 -// T a) : GraphWrapper::NodeMap<T>(_G.gw, a) { }
1.1236 -// };
1.1237 -
1.1238 -// template <typename T>
1.1239 -// class NodeMap {
1.1240 -// typename Graph::NodeMap<T> node_map;
1.1241 -// public:
1.1242 -// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
1.1243 -// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
1.1244 -// void set(Node nit, T a) { node_map.set(nit, a); }
1.1245 -// T get(Node nit) const { return node_map.get(nit); }
1.1246 -// };
1.1247 -
1.1248 - template <typename T>
1.1249 - class EdgeMap {
1.1250 - typename GraphWrapper::EdgeMap<T> forward_map, backward_map;
1.1251 - public:
1.1252 - EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.gw), backward_map(_G.gw) { }
1.1253 - EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.gw, a), backward_map(_G.gw, a) { }
1.1254 - void set(Edge e, T a) {
1.1255 - if (e.out_or_in)
1.1256 - forward_map.set(e.out, a);
1.1257 - else
1.1258 - backward_map.set(e.in, a);
1.1259 - }
1.1260 - T get(Edge e) {
1.1261 - if (e.out_or_in)
1.1262 - return forward_map.get(e.out);
1.1263 - else
1.1264 - return backward_map.get(e.in);
1.1265 - }
1.1266 - };
1.1267 - };
1.1268 -
1.1269 - //Subgraph on the same node-set and partial edge-set
1.1270 - template<typename GraphWrapper, typename FirstOutEdgesMap>
1.1271 - class ErasingFirstGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
1.1272 - protected:
1.1273 - FirstOutEdgesMap* first_out_edges;
1.1274 - public:
1.1275 - typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
1.1276 - typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
1.1277 - typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
1.1278 - typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt;
1.1279 - typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt;
1.1280 - typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt;
1.1281 -
1.1282 - ErasingFirstGraphWrapper(GraphWrapper _gw, FirstOutEdgesMap& _first_out_edges) :
1.1283 - GraphWrapperSkeleton<GraphWrapper>(_gw), first_out_edges(&_first_out_edges) { }
1.1284 -
1.1285 - template<typename I> I& first(I& i) const {
1.1286 - gw.first(i);
1.1287 - //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
1.1288 - return i;
1.1289 - }
1.1290 - OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1.1291 - e=first_out_edges->get(n);
1.1292 - return e;
1.1293 - }
1.1294 - template<typename I, typename P> I& first(I& i, const P& p) const {
1.1295 - gw.first(i, p);
1.1296 - //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
1.1297 - return i;
1.1298 - }
1.1299 -
1.1300 - //template<typename I> I getNext(const I& i) const {
1.1301 - // return gw.getNext(i);
1.1302 - //}
1.1303 - template<typename I> I& next(I &i) const {
1.1304 - gw.next(i);
1.1305 - //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
1.1306 - return i;
1.1307 - }
1.1308 -
1.1309 - template< typename It > It first() const {
1.1310 - It e; this->first(e); return e; }
1.1311 -
1.1312 - template< typename It > It first(const Node& v) const {
1.1313 - It e; this->first(e, v); return e; }
1.1314 -
1.1315 - void erase(const OutEdgeIt& e) const {
1.1316 - OutEdgeIt f=e;
1.1317 - this->next(f);
1.1318 - first_out_edges->set(this->tail(e), f);
1.1319 - }
1.1320 - };
1.1321 -
1.1322 -// template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.1323 -// class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
1.1324 -// protected:
1.1325 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
1.1326 -// //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
1.1327 -// public:
1.1328 -// ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow,
1.1329 -// const CapacityMap& _capacity) :
1.1330 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),
1.1331 -// first_out_edges(*this) /*, dist(*this)*/ {
1.1332 -// for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) {
1.1333 -// OutEdgeIt e;
1.1334 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
1.1335 -// first_out_edges.set(n, e);
1.1336 -// }
1.1337 -// }
1.1338 -
1.1339 -// //void setGraph(Graph& _graph) { graph = &_graph; }
1.1340 -// //Graph& getGraph() const { return (*graph); }
1.1341 -
1.1342 -// //TrivGraphWrapper() : graph(0) { }
1.1343 -// //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.1344 -
1.1345 -// //typedef Graph BaseGraph;
1.1346 -
1.1347 -// //typedef typename Graph::Node Node;
1.1348 -// //typedef typename Graph::NodeIt NodeIt;
1.1349 -
1.1350 -// //typedef typename Graph::Edge Edge;
1.1351 -// //typedef typename Graph::OutEdgeIt OutEdgeIt;
1.1352 -// //typedef typename Graph::InEdgeIt InEdgeIt;
1.1353 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.1354 -// //typedef typename Graph::EdgeIt EdgeIt;
1.1355 -
1.1356 -// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
1.1357 -// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
1.1358 -
1.1359 -// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
1.1360 -// typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
1.1361 -// //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
1.1362 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.1363 -// //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
1.1364 -
1.1365 -// NodeIt& first(NodeIt& n) const {
1.1366 -// return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
1.1367 -// }
1.1368 -
1.1369 -// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1.1370 -// e=first_out_edges.get(n);
1.1371 -// return e;
1.1372 -// }
1.1373 -
1.1374 -// //ROSSZ template<typename I> I& first(I& i) const { return first(i); }
1.1375 -// //ROSSZ template<typename I, typename P> I& first(I& i, const P& p) const {
1.1376 -// // return first(i, p); }
1.1377 -
1.1378 -// //template<typename I> I getNext(const I& i) const {
1.1379 -// // return gw.getNext(i); }
1.1380 -// //template<typename I> I& next(I &i) const { return gw.next(i); }
1.1381 -
1.1382 -// template< typename It > It first() const {
1.1383 -// It e; first(e); return e; }
1.1384 -
1.1385 -// template< typename It > It first(const Node& v) const {
1.1386 -// It e; first(e, v); return e; }
1.1387 -
1.1388 -// //Node head(const Edge& e) const { return gw.head(e); }
1.1389 -// //Node tail(const Edge& e) const { return gw.tail(e); }
1.1390 -
1.1391 -// //template<typename I> bool valid(const I& i) const
1.1392 -// // { return gw.valid(i); }
1.1393 -
1.1394 -// //int nodeNum() const { return gw.nodeNum(); }
1.1395 -// //int edgeNum() const { return gw.edgeNum(); }
1.1396 -
1.1397 -// //template<typename I> Node aNode(const I& e) const {
1.1398 -// // return gw.aNode(e); }
1.1399 -// //template<typename I> Node bNode(const I& e) const {
1.1400 -// // return gw.bNode(e); }
1.1401 -
1.1402 -// //Node addNode() const { return gw.addNode(); }
1.1403 -// //Edge addEdge(const Node& tail, const Node& head) const {
1.1404 -// // return gw.addEdge(tail, head); }
1.1405 -
1.1406 -// //void erase(const OutEdgeIt& e) {
1.1407 -// // first_out_edge(this->tail(e))=e;
1.1408 -// //}
1.1409 -// void erase(const Edge& e) {
1.1410 -// OutEdgeIt f(e);
1.1411 -// next(f);
1.1412 -// first_out_edges.set(this->tail(e), f);
1.1413 -// }
1.1414 -// //template<typename I> void erase(const I& i) const { gw.erase(i); }
1.1415 -
1.1416 -// //void clear() const { gw.clear(); }
1.1417 -
1.1418 -// template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
1.1419 -// public:
1.1420 -// NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
1.1421 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
1.1422 -// NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
1.1423 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
1.1424 -// };
1.1425 -
1.1426 -// template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
1.1427 -// public:
1.1428 -// EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
1.1429 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
1.1430 -// EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
1.1431 -// ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
1.1432 -// };
1.1433 -// };
1.1434 -
1.1435 -// template<typename GraphWrapper>
1.1436 -// class FilterGraphWrapper {
1.1437 -// };
1.1438 -
1.1439 -// template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.1440 -// class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
1.1441 -
1.1442 -// //Graph* graph;
1.1443 -
1.1444 -// public:
1.1445 -// //typedef Graph BaseGraph;
1.1446 -
1.1447 -// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
1.1448 -// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
1.1449 -
1.1450 -// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
1.1451 -// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
1.1452 -// //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
1.1453 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.1454 -// typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
1.1455 -
1.1456 -// //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
1.1457 -
1.1458 -// public:
1.1459 -// FilterGraphWrapper(const Graph& _G, FlowMap& _flow,
1.1460 -// const CapacityMap& _capacity) :
1.1461 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this, gw.nodeNum()) {
1.1462 -// }
1.1463 -
1.1464 -// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1.1465 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
1.1466 -// while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e))))
1.1467 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1.1468 -// return e;
1.1469 -// }
1.1470 -
1.1471 -// NodeIt& next(NodeIt& e) const {
1.1472 -// return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1.1473 -// }
1.1474 -
1.1475 -// OutEdgeIt& next(OutEdgeIt& e) const {
1.1476 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1.1477 -// while (valid(e) && (dist.get(tail(e))/*+1!*/>=dist.get(head(e))))
1.1478 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1.1479 -// return e;
1.1480 -// }
1.1481 -
1.1482 -// NodeIt& first(NodeIt& n) const {
1.1483 -// return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
1.1484 -// }
1.1485 -
1.1486 -// void erase(const Edge& e) {
1.1487 -// OutEdgeIt f(e);
1.1488 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
1.1489 -// while (valid(f) && (dist.get(tail(f))/*+1!=*/>=dist.get(head(f))))
1.1490 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
1.1491 -// first_out_edges.set(this->tail(e), f);
1.1492 -// }
1.1493 -
1.1494 -// //TrivGraphWrapper() : graph(0) { }
1.1495 -// //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.1496 -
1.1497 -// //void setGraph(Graph& _graph) { graph = &_graph; }
1.1498 -// //Graph& getGraph() const { return (*graph); }
1.1499 -
1.1500 -// //template<typename I> I& first(I& i) const { return gw.first(i); }
1.1501 -// //template<typename I, typename P> I& first(I& i, const P& p) const {
1.1502 -// // return gw.first(i, p); }
1.1503 -
1.1504 -// //template<typename I> I getNext(const I& i) const {
1.1505 -// // return gw.getNext(i); }
1.1506 -// //template<typename I> I& next(I &i) const { return gw.next(i); }
1.1507 -
1.1508 -// template< typename It > It first() const {
1.1509 -// It e; first(e); return e; }
1.1510 -
1.1511 -// template< typename It > It first(const Node& v) const {
1.1512 -// It e; first(e, v); return e; }
1.1513 -
1.1514 -// //Node head(const Edge& e) const { return gw.head(e); }
1.1515 -// //Node tail(const Edge& e) const { return gw.tail(e); }
1.1516 -
1.1517 -// //template<typename I> bool valid(const I& i) const
1.1518 -// // { return gw.valid(i); }
1.1519 -
1.1520 -// //template<typename I> void setInvalid(const I &i);
1.1521 -// //{ return gw.setInvalid(i); }
1.1522 -
1.1523 -// //int nodeNum() const { return gw.nodeNum(); }
1.1524 -// //int edgeNum() const { return gw.edgeNum(); }
1.1525 -
1.1526 -// //template<typename I> Node aNode(const I& e) const {
1.1527 -// // return gw.aNode(e); }
1.1528 -// //template<typename I> Node bNode(const I& e) const {
1.1529 -// // return gw.bNode(e); }
1.1530 -
1.1531 -// //Node addNode() const { return gw.addNode(); }
1.1532 -// //Edge addEdge(const Node& tail, const Node& head) const {
1.1533 -// // return gw.addEdge(tail, head); }
1.1534 -
1.1535 -// //template<typename I> void erase(const I& i) const { gw.erase(i); }
1.1536 -
1.1537 -// //void clear() const { gw.clear(); }
1.1538 -
1.1539 -// template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
1.1540 -// public:
1.1541 -// NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
1.1542 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
1.1543 -// NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
1.1544 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
1.1545 -// };
1.1546 -
1.1547 -// template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
1.1548 -// public:
1.1549 -// EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
1.1550 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
1.1551 -// EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
1.1552 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
1.1553 -// };
1.1554 -
1.1555 -// public:
1.1556 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
1.1557 -
1.1558 -// };
1.1559 -
1.1560 -
1.1561 -
1.1562 -// // FIXME: comparison should be made better!!!
1.1563 -// template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
1.1564 -// class ResGraphWrapper
1.1565 -// {
1.1566 -// Graph* graph;
1.1567 -
1.1568 -// public:
1.1569 -// typedef Graph BaseGraph;
1.1570 -
1.1571 -// typedef typename Graph::Node Node;
1.1572 -// typedef typename Graph::Edge Edge;
1.1573 -
1.1574 -// typedef typename Graph::NodeIt NodeIt;
1.1575 -
1.1576 -// class OutEdgeIt {
1.1577 -// public:
1.1578 -// //Graph::Node n;
1.1579 -// bool out_or_in;
1.1580 -// typename Graph::OutEdgeIt o;
1.1581 -// typename Graph::InEdgeIt i;
1.1582 -// };
1.1583 -// class InEdgeIt {
1.1584 -// public:
1.1585 -// //Graph::Node n;
1.1586 -// bool out_or_in;
1.1587 -// typename Graph::OutEdgeIt o;
1.1588 -// typename Graph::InEdgeIt i;
1.1589 -// };
1.1590 -// typedef typename Graph::SymEdgeIt SymEdgeIt;
1.1591 -// typedef typename Graph::EdgeIt EdgeIt;
1.1592 -
1.1593 -// int nodeNum() const { return gw.nodeNum(); }
1.1594 -// int edgeNum() const { return gw.edgeNum(); }
1.1595 -
1.1596 -// Node& first(Node& n) const { return gw.first(n); }
1.1597 -
1.1598 -// // Edge and SymEdge is missing!!!!
1.1599 -// // Edge <-> In/OutEdgeIt conversion is missing!!!!
1.1600 -
1.1601 -// //FIXME
1.1602 -// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const
1.1603 -// {
1.1604 -// e.n=n;
1.1605 -// gw.first(e.o,n);
1.1606 -// while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1.1607 -// gw.goNext(e.o);
1.1608 -// if(!gw.valid(e.o)) {
1.1609 -// gw.first(e.i,n);
1.1610 -// while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1.1611 -// gw.goNext(e.i);
1.1612 -// }
1.1613 -// return e;
1.1614 -// }
1.1615 -// /*
1.1616 -// OutEdgeIt &goNext(OutEdgeIt &e)
1.1617 -// {
1.1618 -// if(gw.valid(e.o)) {
1.1619 -// while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
1.1620 -// gw.goNext(e.o);
1.1621 -// if(gw.valid(e.o)) return e;
1.1622 -// else gw.first(e.i,e.n);
1.1623 -// }
1.1624 -// else {
1.1625 -// while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
1.1626 -// gw.goNext(e.i);
1.1627 -// return e;
1.1628 -// }
1.1629 -// }
1.1630 -// OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
1.1631 -// */
1.1632 -// //bool valid(const OutEdgeIt e) { return gw.valid(e.o)||gw.valid(e.i);}
1.1633 -
1.1634 -// //FIXME
1.1635 -// InEdgeIt& first(InEdgeIt& e, const Node& n) const
1.1636 -// {
1.1637 -// e.n=n;
1.1638 -// gw.first(e.i,n);
1.1639 -// while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1.1640 -// gw.goNext(e.i);
1.1641 -// if(!gw.valid(e.i)) {
1.1642 -// gw.first(e.o,n);
1.1643 -// while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1.1644 -// gw.goNext(e.o);
1.1645 -// }
1.1646 -// return e;
1.1647 -// }
1.1648 -// /*
1.1649 -// InEdgeIt &goNext(InEdgeIt &e)
1.1650 -// {
1.1651 -// if(gw.valid(e.i)) {
1.1652 -// while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
1.1653 -// gw.goNext(e.i);
1.1654 -// if(gw.valid(e.i)) return e;
1.1655 -// else gw.first(e.o,e.n);
1.1656 -// }
1.1657 -// else {
1.1658 -// while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
1.1659 -// gw.goNext(e.o);
1.1660 -// return e;
1.1661 -// }
1.1662 -// }
1.1663 -// InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
1.1664 -// */
1.1665 -// //bool valid(const InEdgeIt e) { return gw.valid(e.i)||gw.valid(e.o);}
1.1666 -
1.1667 -// //template<typename I> I &goNext(I &i); { return gw.goNext(i); }
1.1668 -// //template<typename I> I next(const I i); { return gw.goNext(i); }
1.1669 -
1.1670 -// template< typename It > It first() const {
1.1671 -// It e; first(e); return e; }
1.1672 -
1.1673 -// template< typename It > It first(Node v) const {
1.1674 -// It e; first(e, v); return e; }
1.1675 -
1.1676 -// Node head(const Edge& e) const { return gw.head(e); }
1.1677 -// Node tail(const Edge& e) const { return gw.tail(e); }
1.1678 -
1.1679 -// template<typename I> Node aNode(const I& e) const {
1.1680 -// return gw.aNode(e); }
1.1681 -// template<typename I> Node bNode(const I& e) const {
1.1682 -// return gw.bNode(e); }
1.1683 -
1.1684 -// //template<typename I> bool valid(const I i);
1.1685 -// //{ return gw.valid(i); }
1.1686 -
1.1687 -// //template<typename I> void setInvalid(const I &i);
1.1688 -// //{ return gw.setInvalid(i); }
1.1689 -
1.1690 -// Node addNode() { return gw.addNode(); }
1.1691 -// Edge addEdge(const Node& tail, const Node& head) {
1.1692 -// return gw.addEdge(tail, head); }
1.1693 -
1.1694 -// template<typename I> void erase(const I& i) { gw.erase(i); }
1.1695 -
1.1696 -// void clear() { gw.clear(); }
1.1697 -
1.1698 -// template<typename S> class NodeMap : public Graph::NodeMap<S> { };
1.1699 -// template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
1.1700 -
1.1701 -// void setGraph(Graph& _graph) { graph = &_graph; }
1.1702 -// Graph& getGraph() { return (*graph); }
1.1703 -
1.1704 -// //ResGraphWrapper() : graph(0) { }
1.1705 -// ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.1706 -// };
1.1707 -
1.1708 -} //namespace hugo
1.1709 -
1.1710 -#endif //HUGO_GRAPH_WRAPPER_H
1.1711 -
2.1 --- a/src/work/athos/minlengthpaths.h Mon Apr 05 17:56:31 2004 +0000
2.2 +++ b/src/work/athos/minlengthpaths.h Mon Apr 05 18:24:37 2004 +0000
2.3 @@ -13,31 +13,18 @@
2.4 namespace hugo {
2.5
2.6
2.7 -///\brief Implementation of an algorithm for finding k paths between 2 nodes
2.8 + ///\brief Implementation of an algorithm for finding k paths between 2 nodes
2.9 /// of minimal total length
2.10 -///
2.11 -/// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements
2.12 -/// an algorithm which finds k edge-disjoint paths
2.13 -/// from a given source node to a given target node in an
2.14 -/// edge-weighted directed graph having minimal total weigth (length).
2.15 -///
2.16 -///
2.17 + ///
2.18 + /// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements
2.19 + /// an algorithm which finds k edge-disjoint paths
2.20 + /// from a given source node to a given target node in an
2.21 + /// edge-weighted directed graph having minimal total weigth (length).
2.22
2.23 - template <typename Graph, typename T,
2.24 - typename LengthMap=typename Graph::EdgeMap<T> >
2.25 + template <typename Graph, typename LengthMap>
2.26 class MinLengthPaths {
2.27
2.28 -
2.29 -// class ConstMap {
2.30 -// public :
2.31 -// typedef int ValueType;
2.32 -// typedef typename Graph::Edge KeyType;
2.33 -
2.34 -// int operator[](typename Graph::Edge e) const {
2.35 -// return 1;
2.36 -// }
2.37 -// };
2.38 -
2.39 + typedef typename LengthMap::ValueType Length;
2.40
2.41 typedef typename Graph::Node Node;
2.42 typedef typename Graph::NodeIt NodeIt;
2.43 @@ -47,18 +34,15 @@
2.44
2.45 typedef ConstMap<Edge,int> ConstMap;
2.46
2.47 - typedef TrivGraphWrapper<const Graph> TrivGraphType;
2.48 - typedef ResGraphWrapper<TrivGraphType,int,EdgeIntMap,
2.49 - ConstMap> ResGraphType;
2.50 + typedef ResGraphWrapper<const Graph,int,EdgeIntMap,ConstMap> ResGraphType;
2.51
2.52
2.53 - //template <typename Graph, typename T>
2.54 class ModLengthMap {
2.55 - typedef typename ResGraphType::NodeMap<T> NodeMap;
2.56 + typedef typename ResGraphType::NodeMap<Length> NodeMap;
2.57 const ResGraphType& G;
2.58 - const EdgeIntMap& rev;
2.59 - const LengthMap &ol;
2.60 - const NodeMap &pot;
2.61 + const EdgeIntMap& rev;
2.62 + const LengthMap &ol;
2.63 + const NodeMap &pot;
2.64 public :
2.65 typedef typename LengthMap::KeyType KeyType;
2.66 typedef typename LengthMap::ValueType ValueType;
2.67 @@ -71,8 +55,8 @@
2.68 return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);
2.69 }
2.70
2.71 - ModLengthMap( const ResGraphType& _G, const EdgeIntMap& _rev,
2.72 - const LengthMap &o, const NodeMap &p) :
2.73 + ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev,
2.74 + const LengthMap &o, const NodeMap &p) :
2.75 G(_G), rev(_rev), ol(o), pot(p){};
2.76 };
2.77
2.78 @@ -86,7 +70,7 @@
2.79
2.80
2.81 public :
2.82 -
2.83 +
2.84
2.85 MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G),
2.86 length(_length), reversed(_G)/*, dijkstra_dist(_G)*/{ }
2.87 @@ -102,8 +86,8 @@
2.88 ResGraphType res_graph(G, reversed, const1map);
2.89
2.90 //Initialize the copy of the Dijkstra potential to zero
2.91 - typename ResGraphType::NodeMap<T> dijkstra_dist(G);
2.92 - ModLengthMap mod_length( res_graph, reversed, length, dijkstra_dist);
2.93 + typename ResGraphType::NodeMap<Length> dijkstra_dist(res_graph);
2.94 + ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist);
2.95
2.96 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
2.97
2.98 @@ -111,7 +95,8 @@
2.99 dijkstra.run(s);
2.100 if (!dijkstra.reached(t)){
2.101 //There is no k path from s to t
2.102 - return ++i;
2.103 + /// \TODO mit keresett itt ez a ++?
2.104 + return i;
2.105 };
2.106
2.107 {
2.108 @@ -123,19 +108,6 @@
2.109 }
2.110
2.111
2.112 - /*
2.113 - {
2.114 - //We have to copy the potential
2.115 - typename ResGraphType::EdgeIt e;
2.116 - for ( res_graph.first(e) ; res_graph.valid(e) ; res_graph.next(e) ) {
2.117 - //dijkstra_dist[e] = dijkstra.distMap()[e];
2.118 - mod_length_c[Edge(e)] = mod_length_c[Edge(e)] -
2.119 - dijkstra.distMap()[res_graph.head(e)] +
2.120 - dijkstra.distMap()[res_graph.tail(e)];
2.121 - }
2.122 - }
2.123 - */
2.124 -
2.125 //Reversing the sortest path
2.126 Node n=t;
2.127 Edge e;
2.128 @@ -149,14 +121,12 @@
2.129 }
2.130 return k;
2.131 }
2.132 -
2.133 -
2.134
2.135
2.136
2.137 - };//class MinLengthPaths
2.138
2.139
2.140 + }; //class MinLengthPaths
2.141
2.142
2.143 } //namespace hugo
3.1 --- a/src/work/athos/suurballe.cc Mon Apr 05 17:56:31 2004 +0000
3.2 +++ b/src/work/athos/suurballe.cc Mon Apr 05 18:24:37 2004 +0000
3.3 @@ -119,8 +119,9 @@
3.4
3.5
3.6 int k=3;
3.7 - MinLengthPaths<ListGraph, int> surb_test(graph, length);
3.8 - std::cout << surb_test.run(s,t,k)<<std::endl;
3.9 + MinLengthPaths<ListGraph, ListGraph::EdgeMap<int> >
3.10 + surb_test(graph, length);
3.11 + std::cout << surb_test.run(s,t,k) << std::endl;
3.12
3.13 return 0;
3.14 }
4.1 --- a/src/work/klao/Makefile Mon Apr 05 17:56:31 2004 +0000
4.2 +++ b/src/work/klao/Makefile Mon Apr 05 18:24:37 2004 +0000
4.3 @@ -1,4 +1,4 @@
4.4 -BINARIES = path_test map_test
4.5 +BINARIES = path_test map_test minlengthpaths
4.6 INCLUDEDIRS= -I. -I.. -I../../include -I../{marci,jacint,alpar,johanna,akos}
4.7 include ../makefile
4.8
5.1 --- a/src/work/klao/minlengthpaths.cc Mon Apr 05 17:56:31 2004 +0000
5.2 +++ b/src/work/klao/minlengthpaths.cc Mon Apr 05 18:24:37 2004 +0000
5.3 @@ -119,8 +119,9 @@
5.4
5.5
5.6 int k=3;
5.7 - MinLengthPaths<ListGraph, int> surb_test(graph, length);
5.8 - std::cout << surb_test.run(s,t,k)<<std::endl;
5.9 + MinLengthPaths<ListGraph, ListGraph::EdgeMap<int> >
5.10 + surb_test(graph, length);
5.11 + std::cout << surb_test.run(s,t,k) << std::endl;
5.12
5.13 return 0;
5.14 }
6.1 --- a/src/work/klao/minlengthpaths.h Mon Apr 05 17:56:31 2004 +0000
6.2 +++ b/src/work/klao/minlengthpaths.h Mon Apr 05 18:24:37 2004 +0000
6.3 @@ -13,31 +13,18 @@
6.4 namespace hugo {
6.5
6.6
6.7 -///\brief Implementation of an algorithm for finding k paths between 2 nodes
6.8 + ///\brief Implementation of an algorithm for finding k paths between 2 nodes
6.9 /// of minimal total length
6.10 -///
6.11 -/// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements
6.12 -/// an algorithm which finds k edge-disjoint paths
6.13 -/// from a given source node to a given target node in an
6.14 -/// edge-weighted directed graph having minimal total weigth (length).
6.15 -///
6.16 -///
6.17 + ///
6.18 + /// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements
6.19 + /// an algorithm which finds k edge-disjoint paths
6.20 + /// from a given source node to a given target node in an
6.21 + /// edge-weighted directed graph having minimal total weigth (length).
6.22
6.23 - template <typename Graph, typename T,
6.24 - typename LengthMap=typename Graph::EdgeMap<T> >
6.25 + template <typename Graph, typename LengthMap>
6.26 class MinLengthPaths {
6.27
6.28 -
6.29 -// class ConstMap {
6.30 -// public :
6.31 -// typedef int ValueType;
6.32 -// typedef typename Graph::Edge KeyType;
6.33 -
6.34 -// int operator[](typename Graph::Edge e) const {
6.35 -// return 1;
6.36 -// }
6.37 -// };
6.38 -
6.39 + typedef typename LengthMap::ValueType Length;
6.40
6.41 typedef typename Graph::Node Node;
6.42 typedef typename Graph::NodeIt NodeIt;
6.43 @@ -47,18 +34,15 @@
6.44
6.45 typedef ConstMap<Edge,int> ConstMap;
6.46
6.47 - typedef TrivGraphWrapper<const Graph> TrivGraphType;
6.48 - typedef ResGraphWrapper<TrivGraphType,int,EdgeIntMap,
6.49 - ConstMap> ResGraphType;
6.50 + typedef ResGraphWrapper<const Graph,int,EdgeIntMap,ConstMap> ResGraphType;
6.51
6.52
6.53 - //template <typename Graph, typename T>
6.54 class ModLengthMap {
6.55 - typedef typename ResGraphType::NodeMap<T> NodeMap;
6.56 + typedef typename ResGraphType::NodeMap<Length> NodeMap;
6.57 const ResGraphType& G;
6.58 - const EdgeIntMap& rev;
6.59 - const LengthMap &ol;
6.60 - const NodeMap &pot;
6.61 + const EdgeIntMap& rev;
6.62 + const LengthMap &ol;
6.63 + const NodeMap &pot;
6.64 public :
6.65 typedef typename LengthMap::KeyType KeyType;
6.66 typedef typename LengthMap::ValueType ValueType;
6.67 @@ -71,8 +55,8 @@
6.68 return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);
6.69 }
6.70
6.71 - ModLengthMap( const ResGraphType& _G, const EdgeIntMap& _rev,
6.72 - const LengthMap &o, const NodeMap &p) :
6.73 + ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev,
6.74 + const LengthMap &o, const NodeMap &p) :
6.75 G(_G), rev(_rev), ol(o), pot(p){};
6.76 };
6.77
6.78 @@ -86,7 +70,7 @@
6.79
6.80
6.81 public :
6.82 -
6.83 +
6.84
6.85 MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G),
6.86 length(_length), reversed(_G)/*, dijkstra_dist(_G)*/{ }
6.87 @@ -102,8 +86,8 @@
6.88 ResGraphType res_graph(G, reversed, const1map);
6.89
6.90 //Initialize the copy of the Dijkstra potential to zero
6.91 - typename ResGraphType::NodeMap<T> dijkstra_dist(G);
6.92 - ModLengthMap mod_length( res_graph, reversed, length, dijkstra_dist);
6.93 + typename ResGraphType::NodeMap<Length> dijkstra_dist(res_graph);
6.94 + ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist);
6.95
6.96 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
6.97
6.98 @@ -111,7 +95,8 @@
6.99 dijkstra.run(s);
6.100 if (!dijkstra.reached(t)){
6.101 //There is no k path from s to t
6.102 - return ++i;
6.103 + /// \TODO mit keresett itt ez a ++?
6.104 + return i;
6.105 };
6.106
6.107 {
6.108 @@ -123,19 +108,6 @@
6.109 }
6.110
6.111
6.112 - /*
6.113 - {
6.114 - //We have to copy the potential
6.115 - typename ResGraphType::EdgeIt e;
6.116 - for ( res_graph.first(e) ; res_graph.valid(e) ; res_graph.next(e) ) {
6.117 - //dijkstra_dist[e] = dijkstra.distMap()[e];
6.118 - mod_length_c[Edge(e)] = mod_length_c[Edge(e)] -
6.119 - dijkstra.distMap()[res_graph.head(e)] +
6.120 - dijkstra.distMap()[res_graph.tail(e)];
6.121 - }
6.122 - }
6.123 - */
6.124 -
6.125 //Reversing the sortest path
6.126 Node n=t;
6.127 Edge e;
6.128 @@ -149,14 +121,12 @@
6.129 }
6.130 return k;
6.131 }
6.132 -
6.133 -
6.134
6.135
6.136
6.137 - };//class MinLengthPaths
6.138
6.139
6.140 + }; //class MinLengthPaths
6.141
6.142
6.143 } //namespace hugo