1.1 --- a/src/work/marci/graph_wrapper.h Tue Mar 23 11:12:48 2004 +0000
1.2 +++ b/src/work/marci/graph_wrapper.h Tue Mar 23 13:31:02 2004 +0000
1.3 @@ -333,27 +333,27 @@
1.4 typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt InEdgeIt;
1.5 typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt OutEdgeIt;
1.6
1.7 + RevGraphWrapper(GraphWrapper _gw) :
1.8 + GraphWrapperSkeleton<GraphWrapper>(_gw) { }
1.9 +
1.10 Node head(const Edge& e) const
1.11 { return GraphWrapperSkeleton<GraphWrapper>::tail(e); }
1.12 Node tail(const Edge& e) const
1.13 { return GraphWrapperSkeleton<GraphWrapper>::head(e); }
1.14 -
1.15 - RevGraphWrapper(GraphWrapper _gw) :
1.16 - GraphWrapperSkeleton<GraphWrapper>(_gw) { }
1.17 };
1.18
1.19
1.20 -
1.21 -// template<typename Graph>
1.22 +// template<typename GraphWrapper>
1.23 // class UndirGraphWrapper {
1.24 // protected:
1.25 -// Graph* graph;
1.26 -
1.27 +// //Graph* graph;
1.28 +// GraphWrapper gw;
1.29 +
1.30 // public:
1.31 -// typedef Graph BaseGraph;
1.32 +// typedef GraphWrapper BaseGraph;
1.33
1.34 -// typedef typename Graph::Node Node;
1.35 -// typedef typename Graph::NodeIt NodeIt;
1.36 +// typedef typename GraphWrapper::Node Node;
1.37 +// typedef typename GraphWrapper::NodeIt NodeIt;
1.38
1.39 // //typedef typename Graph::Edge Edge;
1.40 // //typedef typename Graph::OutEdgeIt OutEdgeIt;
1.41 @@ -362,19 +362,19 @@
1.42 // //typedef typename Graph::EdgeIt EdgeIt;
1.43
1.44 // //private:
1.45 -// typedef typename Graph::Edge GraphEdge;
1.46 -// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1.47 -// typedef typename Graph::InEdgeIt GraphInEdgeIt;
1.48 +// typedef typename GraphWrapper::Edge GraphEdge;
1.49 +// typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;
1.50 +// typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;
1.51 // //public:
1.52
1.53 // //UndirGraphWrapper() : graph(0) { }
1.54 -// UndirGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.55 +// UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
1.56
1.57 -// void setGraph(Graph& _graph) { graph = &_graph; }
1.58 -// Graph& getGraph() const { return (*graph); }
1.59 +// //void setGraph(Graph& _graph) { graph = &_graph; }
1.60 +// //Graph& getGraph() const { return (*graph); }
1.61
1.62 // class Edge {
1.63 -// friend class UndirGraphWrapper<Graph>;
1.64 +// friend class UndirGraphWrapper<GraphWrapper>;
1.65 // bool out_or_in; //true iff out
1.66 // GraphOutEdgeIt out;
1.67 // GraphInEdgeIt in;
1.68 @@ -399,58 +399,59 @@
1.69 // };
1.70
1.71 // class OutEdgeIt : public Edge {
1.72 -// friend class UndirGraphWrapper<Graph>;
1.73 +// friend class UndirGraphWrapper<GraphWrapper>;
1.74 // public:
1.75 // OutEdgeIt() : Edge() { }
1.76 // OutEdgeIt(const Invalid& i) : Edge(i) { }
1.77 -// OutEdgeIt(const UndirGraphWrapper& _G, const Node& n) : Edge() {
1.78 +// OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)
1.79 +// : Edge() {
1.80 // out_or_in=true;
1.81 -// _G.graph->first(out, n);
1.82 -// if (!(_G.graph->valid(out))) {
1.83 +// _G.gw.first(out, n);
1.84 +// if (!(_G.gw.valid(out))) {
1.85 // out_or_in=false;
1.86 -// _G.graph->first(in, n);
1.87 +// _G.gw.first(in, n);
1.88 // }
1.89 // }
1.90 // };
1.91
1.92 // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1.93 // e.out_or_in=true;
1.94 -// graph->first(e.out, n);
1.95 -// if (!(graph->valid(e.out))) {
1.96 +// gw.first(e.out, n);
1.97 +// if (!(gw.valid(e.out))) {
1.98 // e.out_or_in=false;
1.99 -// graph->first(e.in, n);
1.100 +// gw.first(e.in, n);
1.101 // }
1.102 // return e;
1.103 // }
1.104
1.105 // OutEdgeIt& next(OutEdgeIt& e) const {
1.106 // if (e.out_or_in) {
1.107 -// Node n=graph->tail(e.out);
1.108 -// graph->next(e.out);
1.109 -// if (!graph->valid(e.out)) {
1.110 +// Node n=gw.tail(e.out);
1.111 +// gw.next(e.out);
1.112 +// if (!gw.valid(e.out)) {
1.113 // e.out_or_in=false;
1.114 -// graph->first(e.in, n);
1.115 +// gw.first(e.in, n);
1.116 // }
1.117 // } else {
1.118 -// graph->next(e.in);
1.119 +// gw.next(e.in);
1.120 // }
1.121 // return e;
1.122 // }
1.123
1.124 // Node aNode(const OutEdgeIt& e) const {
1.125 -// if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
1.126 +// if (e.out_or_in) return gw.tail(e); else return gw.head(e); }
1.127 // Node bNode(const OutEdgeIt& e) const {
1.128 -// if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
1.129 +// if (e.out_or_in) return gw.head(e); else return gw.tail(e); }
1.130
1.131 // typedef OutEdgeIt InEdgeIt;
1.132
1.133 -// template<typename I> I& first(I& i) const { return graph->first(i); }
1.134 +// template<typename I> I& first(I& i) const { return gw.first(i); }
1.135 // // template<typename I, typename P> I& first(I& i, const P& p) const {
1.136 // // return graph->first(i, p); }
1.137
1.138 // template<typename I> I getNext(const I& i) const {
1.139 -// return graph->getNext(i); }
1.140 -// template<typename I> I& next(I &i) const { return graph->next(i); }
1.141 +// return gw.getNext(i); }
1.142 +// template<typename I> I& next(I &i) const { return gw.next(i); }
1.143
1.144 // template< typename It > It first() const {
1.145 // It e; first(e); return e; }
1.146 @@ -458,76 +459,72 @@
1.147 // template< typename It > It first(const Node& v) const {
1.148 // It e; first(e, v); return e; }
1.149
1.150 -// Node head(const Edge& e) const { return graph->head(e); }
1.151 -// Node tail(const Edge& e) const { return graph->tail(e); }
1.152 +// Node head(const Edge& e) const { return gw.head(e); }
1.153 +// Node tail(const Edge& e) const { return gw.tail(e); }
1.154
1.155 // template<typename I> bool valid(const I& i) const
1.156 -// { return graph->valid(i); }
1.157 +// { return gw.valid(i); }
1.158
1.159 // //template<typename I> void setInvalid(const I &i);
1.160 // //{ return graph->setInvalid(i); }
1.161
1.162 -// int nodeNum() const { return graph->nodeNum(); }
1.163 -// int edgeNum() const { return graph->edgeNum(); }
1.164 +// int nodeNum() const { return gw.nodeNum(); }
1.165 +// int edgeNum() const { return gw.edgeNum(); }
1.166
1.167 // // template<typename I> Node aNode(const I& e) const {
1.168 // // return graph->aNode(e); }
1.169 // // template<typename I> Node bNode(const I& e) const {
1.170 // // return graph->bNode(e); }
1.171
1.172 -// Node addNode() const { return graph->addNode(); }
1.173 +// Node addNode() const { return gw.addNode(); }
1.174 // // FIXME: ez igy nem jo, mert nem
1.175 // // Edge addEdge(const Node& tail, const Node& head) const {
1.176 // // return graph->addEdge(tail, head); }
1.177
1.178 -// template<typename I> void erase(const I& i) const { graph->erase(i); }
1.179 +// template<typename I> void erase(const I& i) const { gw.erase(i); }
1.180
1.181 -// void clear() const { graph->clear(); }
1.182 +// void clear() const { gw.clear(); }
1.183
1.184 -// template<typename T> class NodeMap : public Graph::NodeMap<T> {
1.185 +// template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
1.186 // public:
1.187 -// NodeMap(const UndirGraphWrapper<Graph>& _G) :
1.188 -// Graph::NodeMap<T>(_G.getGraph()) { }
1.189 -// NodeMap(const UndirGraphWrapper<Graph>& _G, T a) :
1.190 -// Graph::NodeMap<T>(_G.getGraph(), a) { }
1.191 +// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
1.192 +// GraphWrapper::NodeMap<T>(_G.gw) { }
1.193 +// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
1.194 +// GraphWrapper::NodeMap<T>(_G.gw, a) { }
1.195 // };
1.196
1.197 -// template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
1.198 +// template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
1.199 // public:
1.200 -// EdgeMap(const UndirGraphWrapper<Graph>& _G) :
1.201 -// Graph::EdgeMap<T>(_G.getGraph()) { }
1.202 -// EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) :
1.203 -// Graph::EdgeMap<T>(_G.getGraph(), a) { }
1.204 +// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
1.205 +// GraphWrapper::EdgeMap<T>(_G.gw) { }
1.206 +// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
1.207 +// GraphWrapper::EdgeMap<T>(_G.gw, a) { }
1.208 // };
1.209 // };
1.210
1.211
1.212 template<typename GraphWrapper>
1.213 - class UndirGraphWrapper {
1.214 + class UndirGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
1.215 protected:
1.216 - //Graph* graph;
1.217 - GraphWrapper gw;
1.218 +// GraphWrapper gw;
1.219
1.220 public:
1.221 - typedef GraphWrapper BaseGraph;
1.222 + //typedef GraphWrapper BaseGraph;
1.223
1.224 - typedef typename GraphWrapper::Node Node;
1.225 - typedef typename GraphWrapper::NodeIt NodeIt;
1.226 -
1.227 - //typedef typename Graph::Edge Edge;
1.228 - //typedef typename Graph::OutEdgeIt OutEdgeIt;
1.229 - //typedef typename Graph::InEdgeIt InEdgeIt;
1.230 - //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.231 - //typedef typename Graph::EdgeIt EdgeIt;
1.232 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
1.233 + typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
1.234
1.235 //private:
1.236 - typedef typename GraphWrapper::Edge GraphEdge;
1.237 - typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;
1.238 - typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;
1.239 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge GraphEdge;
1.240 + typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt GraphOutEdgeIt;
1.241 + typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt GraphInEdgeIt;
1.242 //public:
1.243
1.244 //UndirGraphWrapper() : graph(0) { }
1.245 - UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
1.246 + UndirGraphWrapper(GraphWrapper _gw) :
1.247 + GraphWrapperSkeleton<GraphWrapper>(_gw) { }
1.248 +
1.249 + //UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
1.250
1.251 //void setGraph(Graph& _graph) { graph = &_graph; }
1.252 //Graph& getGraph() const { return (*graph); }
1.253 @@ -573,6 +570,28 @@
1.254 }
1.255 };
1.256
1.257 + typedef OutEdgeIt InEdgeIt;
1.258 +
1.259 + class EdgeIt : public Edge {
1.260 + friend class UndirGraphWrapper<GraphWrapper>;
1.261 + protected:
1.262 + NodeIt v;
1.263 + public:
1.264 + EdgeIt() : Edge() { }
1.265 + EdgeIt(const Invalid& i) : Edge(i) { }
1.266 + EdgeIt(const UndirGraphWrapper<GraphWrapper>& _G)
1.267 + : Edge() {
1.268 + out_or_in=true;
1.269 + //Node v;
1.270 + _G.first(v);
1.271 + if (_G.valid(v)) _G.gw.first(out); else out=INVALID;
1.272 + while (_G.valid(v) && !_G.gw.valid(out)) {
1.273 + _G.gw.next(v);
1.274 + if (_G.valid(v)) _G.gw.first(out);
1.275 + }
1.276 + }
1.277 + };
1.278 +
1.279 OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1.280 e.out_or_in=true;
1.281 gw.first(e.out, n);
1.282 @@ -583,6 +602,22 @@
1.283 return e;
1.284 }
1.285
1.286 + EdgeIt& first(EdgeIt& e) const {
1.287 + e.out_or_in=true;
1.288 + //NodeIt v;
1.289 + first(e.v);
1.290 + if (valid(e.v)) gw.first(e.out, e.v); else e.out=INVALID;
1.291 + while (valid(e.v) && !gw.valid(e.out)) {
1.292 + gw.next(e.v);
1.293 + if (valid(e.v)) gw.first(e.out, e.v);
1.294 + }
1.295 + return e;
1.296 + }
1.297 +
1.298 + template<typename I> I& first(I& i) const { return gw.first(i); }
1.299 + template<typename I, typename P> I& first(I& i, const P& p) const {
1.300 + return graph->first(i, p); }
1.301 +
1.302 OutEdgeIt& next(OutEdgeIt& e) const {
1.303 if (e.out_or_in) {
1.304 Node n=gw.tail(e.out);
1.305 @@ -597,20 +632,20 @@
1.306 return e;
1.307 }
1.308
1.309 - Node aNode(const OutEdgeIt& e) const {
1.310 - if (e.out_or_in) return gw.tail(e); else return gw.head(e); }
1.311 - Node bNode(const OutEdgeIt& e) const {
1.312 - if (e.out_or_in) return gw.head(e); else return gw.tail(e); }
1.313 + EdgeIt& next(EdgeIt& e) const {
1.314 + //NodeIt v=tail(e);
1.315 + gw.next(e.out);
1.316 + while (valid(e.v) && !gw.valid(e.out)) {
1.317 + next(e.v);
1.318 + if (valid(e.v)) gw.first(e.out, e.v);
1.319 + }
1.320 + return e;
1.321 + }
1.322
1.323 - typedef OutEdgeIt InEdgeIt;
1.324 -
1.325 - template<typename I> I& first(I& i) const { return gw.first(i); }
1.326 -// template<typename I, typename P> I& first(I& i, const P& p) const {
1.327 -// return graph->first(i, p); }
1.328 + template<typename I> I& next(I &i) const { return gw.next(i); }
1.329
1.330 template<typename I> I getNext(const I& i) const {
1.331 return gw.getNext(i); }
1.332 - template<typename I> I& next(I &i) const { return gw.next(i); }
1.333
1.334 template< typename It > It first() const {
1.335 It e; first(e); return e; }
1.336 @@ -618,48 +653,52 @@
1.337 template< typename It > It first(const Node& v) const {
1.338 It e; first(e, v); return e; }
1.339
1.340 - Node head(const Edge& e) const { return gw.head(e); }
1.341 - Node tail(const Edge& e) const { return gw.tail(e); }
1.342 +// Node head(const Edge& e) const { return gw.head(e); }
1.343 +// Node tail(const Edge& e) const { return gw.tail(e); }
1.344
1.345 - template<typename I> bool valid(const I& i) const
1.346 - { return gw.valid(i); }
1.347 +// template<typename I> bool valid(const I& i) const
1.348 +// { return gw.valid(i); }
1.349
1.350 - //template<typename I> void setInvalid(const I &i);
1.351 - //{ return graph->setInvalid(i); }
1.352 -
1.353 - int nodeNum() const { return gw.nodeNum(); }
1.354 - int edgeNum() const { return gw.edgeNum(); }
1.355 +// int nodeNum() const { return gw.nodeNum(); }
1.356 +// int edgeNum() const { return gw.edgeNum(); }
1.357
1.358 // template<typename I> Node aNode(const I& e) const {
1.359 // return graph->aNode(e); }
1.360 // template<typename I> Node bNode(const I& e) const {
1.361 // return graph->bNode(e); }
1.362 +
1.363 + Node aNode(const OutEdgeIt& e) const {
1.364 + if (e.out_or_in) return gw.tail(e); else return gw.head(e); }
1.365 + Node bNode(const OutEdgeIt& e) const {
1.366 + if (e.out_or_in) return gw.head(e); else return gw.tail(e); }
1.367
1.368 - Node addNode() const { return gw.addNode(); }
1.369 +// Node addNode() const { return gw.addNode(); }
1.370 +
1.371 // FIXME: ez igy nem jo, mert nem
1.372 // Edge addEdge(const Node& tail, const Node& head) const {
1.373 // return graph->addEdge(tail, head); }
1.374
1.375 - template<typename I> void erase(const I& i) const { gw.erase(i); }
1.376 +// template<typename I> void erase(const I& i) const { gw.erase(i); }
1.377
1.378 - void clear() const { gw.clear(); }
1.379 +// void clear() const { gw.clear(); }
1.380
1.381 - template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
1.382 - public:
1.383 - NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
1.384 - GraphWrapper::NodeMap<T>(_G.gw) { }
1.385 - NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
1.386 - GraphWrapper::NodeMap<T>(_G.gw, a) { }
1.387 - };
1.388 +// template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
1.389 +// public:
1.390 +// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
1.391 +// GraphWrapper::NodeMap<T>(_G.gw) { }
1.392 +// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
1.393 +// GraphWrapper::NodeMap<T>(_G.gw, a) { }
1.394 +// };
1.395
1.396 - template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
1.397 - public:
1.398 - EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
1.399 - GraphWrapper::EdgeMap<T>(_G.gw) { }
1.400 - EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
1.401 - GraphWrapper::EdgeMap<T>(_G.gw, a) { }
1.402 - };
1.403 - };
1.404 +// template<typename T> class EdgeMap :
1.405 +// public GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T> {
1.406 +// public:
1.407 +// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
1.408 +// GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T>(_G.gw) { }
1.409 +// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
1.410 +// GraphWrapper::EdgeMap<T>(_G.gw, a) { }
1.411 +// };
1.412 + };
1.413
1.414
1.415