1.1 --- a/src/work/iterator_bfs_demo.cc Tue Mar 23 11:12:48 2004 +0000
1.2 +++ b/src/work/iterator_bfs_demo.cc Tue Mar 23 13:31:02 2004 +0000
1.3 @@ -261,6 +261,10 @@
1.4 cout << edge_name.get(e) << " ";
1.5 cout << endl;
1.6 }
1.7 +// for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) {
1.8 +// cout << edge_name.get(e) << " ";
1.9 +// }
1.10 +// cout << endl;
1.11
1.12 cout << "bfs from t ..." << endl;
1.13 BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw);
2.1 --- a/src/work/marci/graph_wrapper.h Tue Mar 23 11:12:48 2004 +0000
2.2 +++ b/src/work/marci/graph_wrapper.h Tue Mar 23 13:31:02 2004 +0000
2.3 @@ -333,27 +333,27 @@
2.4 typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt InEdgeIt;
2.5 typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt OutEdgeIt;
2.6
2.7 + RevGraphWrapper(GraphWrapper _gw) :
2.8 + GraphWrapperSkeleton<GraphWrapper>(_gw) { }
2.9 +
2.10 Node head(const Edge& e) const
2.11 { return GraphWrapperSkeleton<GraphWrapper>::tail(e); }
2.12 Node tail(const Edge& e) const
2.13 { return GraphWrapperSkeleton<GraphWrapper>::head(e); }
2.14 -
2.15 - RevGraphWrapper(GraphWrapper _gw) :
2.16 - GraphWrapperSkeleton<GraphWrapper>(_gw) { }
2.17 };
2.18
2.19
2.20 -
2.21 -// template<typename Graph>
2.22 +// template<typename GraphWrapper>
2.23 // class UndirGraphWrapper {
2.24 // protected:
2.25 -// Graph* graph;
2.26 -
2.27 +// //Graph* graph;
2.28 +// GraphWrapper gw;
2.29 +
2.30 // public:
2.31 -// typedef Graph BaseGraph;
2.32 +// typedef GraphWrapper BaseGraph;
2.33
2.34 -// typedef typename Graph::Node Node;
2.35 -// typedef typename Graph::NodeIt NodeIt;
2.36 +// typedef typename GraphWrapper::Node Node;
2.37 +// typedef typename GraphWrapper::NodeIt NodeIt;
2.38
2.39 // //typedef typename Graph::Edge Edge;
2.40 // //typedef typename Graph::OutEdgeIt OutEdgeIt;
2.41 @@ -362,19 +362,19 @@
2.42 // //typedef typename Graph::EdgeIt EdgeIt;
2.43
2.44 // //private:
2.45 -// typedef typename Graph::Edge GraphEdge;
2.46 -// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
2.47 -// typedef typename Graph::InEdgeIt GraphInEdgeIt;
2.48 +// typedef typename GraphWrapper::Edge GraphEdge;
2.49 +// typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;
2.50 +// typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;
2.51 // //public:
2.52
2.53 // //UndirGraphWrapper() : graph(0) { }
2.54 -// UndirGraphWrapper(Graph& _graph) : graph(&_graph) { }
2.55 +// UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
2.56
2.57 -// void setGraph(Graph& _graph) { graph = &_graph; }
2.58 -// Graph& getGraph() const { return (*graph); }
2.59 +// //void setGraph(Graph& _graph) { graph = &_graph; }
2.60 +// //Graph& getGraph() const { return (*graph); }
2.61
2.62 // class Edge {
2.63 -// friend class UndirGraphWrapper<Graph>;
2.64 +// friend class UndirGraphWrapper<GraphWrapper>;
2.65 // bool out_or_in; //true iff out
2.66 // GraphOutEdgeIt out;
2.67 // GraphInEdgeIt in;
2.68 @@ -399,58 +399,59 @@
2.69 // };
2.70
2.71 // class OutEdgeIt : public Edge {
2.72 -// friend class UndirGraphWrapper<Graph>;
2.73 +// friend class UndirGraphWrapper<GraphWrapper>;
2.74 // public:
2.75 // OutEdgeIt() : Edge() { }
2.76 // OutEdgeIt(const Invalid& i) : Edge(i) { }
2.77 -// OutEdgeIt(const UndirGraphWrapper& _G, const Node& n) : Edge() {
2.78 +// OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)
2.79 +// : Edge() {
2.80 // out_or_in=true;
2.81 -// _G.graph->first(out, n);
2.82 -// if (!(_G.graph->valid(out))) {
2.83 +// _G.gw.first(out, n);
2.84 +// if (!(_G.gw.valid(out))) {
2.85 // out_or_in=false;
2.86 -// _G.graph->first(in, n);
2.87 +// _G.gw.first(in, n);
2.88 // }
2.89 // }
2.90 // };
2.91
2.92 // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
2.93 // e.out_or_in=true;
2.94 -// graph->first(e.out, n);
2.95 -// if (!(graph->valid(e.out))) {
2.96 +// gw.first(e.out, n);
2.97 +// if (!(gw.valid(e.out))) {
2.98 // e.out_or_in=false;
2.99 -// graph->first(e.in, n);
2.100 +// gw.first(e.in, n);
2.101 // }
2.102 // return e;
2.103 // }
2.104
2.105 // OutEdgeIt& next(OutEdgeIt& e) const {
2.106 // if (e.out_or_in) {
2.107 -// Node n=graph->tail(e.out);
2.108 -// graph->next(e.out);
2.109 -// if (!graph->valid(e.out)) {
2.110 +// Node n=gw.tail(e.out);
2.111 +// gw.next(e.out);
2.112 +// if (!gw.valid(e.out)) {
2.113 // e.out_or_in=false;
2.114 -// graph->first(e.in, n);
2.115 +// gw.first(e.in, n);
2.116 // }
2.117 // } else {
2.118 -// graph->next(e.in);
2.119 +// gw.next(e.in);
2.120 // }
2.121 // return e;
2.122 // }
2.123
2.124 // Node aNode(const OutEdgeIt& e) const {
2.125 -// if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
2.126 +// if (e.out_or_in) return gw.tail(e); else return gw.head(e); }
2.127 // Node bNode(const OutEdgeIt& e) const {
2.128 -// if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
2.129 +// if (e.out_or_in) return gw.head(e); else return gw.tail(e); }
2.130
2.131 // typedef OutEdgeIt InEdgeIt;
2.132
2.133 -// template<typename I> I& first(I& i) const { return graph->first(i); }
2.134 +// template<typename I> I& first(I& i) const { return gw.first(i); }
2.135 // // template<typename I, typename P> I& first(I& i, const P& p) const {
2.136 // // return graph->first(i, p); }
2.137
2.138 // template<typename I> I getNext(const I& i) const {
2.139 -// return graph->getNext(i); }
2.140 -// template<typename I> I& next(I &i) const { return graph->next(i); }
2.141 +// return gw.getNext(i); }
2.142 +// template<typename I> I& next(I &i) const { return gw.next(i); }
2.143
2.144 // template< typename It > It first() const {
2.145 // It e; first(e); return e; }
2.146 @@ -458,76 +459,72 @@
2.147 // template< typename It > It first(const Node& v) const {
2.148 // It e; first(e, v); return e; }
2.149
2.150 -// Node head(const Edge& e) const { return graph->head(e); }
2.151 -// Node tail(const Edge& e) const { return graph->tail(e); }
2.152 +// Node head(const Edge& e) const { return gw.head(e); }
2.153 +// Node tail(const Edge& e) const { return gw.tail(e); }
2.154
2.155 // template<typename I> bool valid(const I& i) const
2.156 -// { return graph->valid(i); }
2.157 +// { return gw.valid(i); }
2.158
2.159 // //template<typename I> void setInvalid(const I &i);
2.160 // //{ return graph->setInvalid(i); }
2.161
2.162 -// int nodeNum() const { return graph->nodeNum(); }
2.163 -// int edgeNum() const { return graph->edgeNum(); }
2.164 +// int nodeNum() const { return gw.nodeNum(); }
2.165 +// int edgeNum() const { return gw.edgeNum(); }
2.166
2.167 // // template<typename I> Node aNode(const I& e) const {
2.168 // // return graph->aNode(e); }
2.169 // // template<typename I> Node bNode(const I& e) const {
2.170 // // return graph->bNode(e); }
2.171
2.172 -// Node addNode() const { return graph->addNode(); }
2.173 +// Node addNode() const { return gw.addNode(); }
2.174 // // FIXME: ez igy nem jo, mert nem
2.175 // // Edge addEdge(const Node& tail, const Node& head) const {
2.176 // // return graph->addEdge(tail, head); }
2.177
2.178 -// template<typename I> void erase(const I& i) const { graph->erase(i); }
2.179 +// template<typename I> void erase(const I& i) const { gw.erase(i); }
2.180
2.181 -// void clear() const { graph->clear(); }
2.182 +// void clear() const { gw.clear(); }
2.183
2.184 -// template<typename T> class NodeMap : public Graph::NodeMap<T> {
2.185 +// template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
2.186 // public:
2.187 -// NodeMap(const UndirGraphWrapper<Graph>& _G) :
2.188 -// Graph::NodeMap<T>(_G.getGraph()) { }
2.189 -// NodeMap(const UndirGraphWrapper<Graph>& _G, T a) :
2.190 -// Graph::NodeMap<T>(_G.getGraph(), a) { }
2.191 +// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
2.192 +// GraphWrapper::NodeMap<T>(_G.gw) { }
2.193 +// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
2.194 +// GraphWrapper::NodeMap<T>(_G.gw, a) { }
2.195 // };
2.196
2.197 -// template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
2.198 +// template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
2.199 // public:
2.200 -// EdgeMap(const UndirGraphWrapper<Graph>& _G) :
2.201 -// Graph::EdgeMap<T>(_G.getGraph()) { }
2.202 -// EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) :
2.203 -// Graph::EdgeMap<T>(_G.getGraph(), a) { }
2.204 +// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
2.205 +// GraphWrapper::EdgeMap<T>(_G.gw) { }
2.206 +// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
2.207 +// GraphWrapper::EdgeMap<T>(_G.gw, a) { }
2.208 // };
2.209 // };
2.210
2.211
2.212 template<typename GraphWrapper>
2.213 - class UndirGraphWrapper {
2.214 + class UndirGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
2.215 protected:
2.216 - //Graph* graph;
2.217 - GraphWrapper gw;
2.218 +// GraphWrapper gw;
2.219
2.220 public:
2.221 - typedef GraphWrapper BaseGraph;
2.222 + //typedef GraphWrapper BaseGraph;
2.223
2.224 - typedef typename GraphWrapper::Node Node;
2.225 - typedef typename GraphWrapper::NodeIt NodeIt;
2.226 -
2.227 - //typedef typename Graph::Edge Edge;
2.228 - //typedef typename Graph::OutEdgeIt OutEdgeIt;
2.229 - //typedef typename Graph::InEdgeIt InEdgeIt;
2.230 - //typedef typename Graph::SymEdgeIt SymEdgeIt;
2.231 - //typedef typename Graph::EdgeIt EdgeIt;
2.232 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
2.233 + typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
2.234
2.235 //private:
2.236 - typedef typename GraphWrapper::Edge GraphEdge;
2.237 - typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;
2.238 - typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;
2.239 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge GraphEdge;
2.240 + typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt GraphOutEdgeIt;
2.241 + typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt GraphInEdgeIt;
2.242 //public:
2.243
2.244 //UndirGraphWrapper() : graph(0) { }
2.245 - UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
2.246 + UndirGraphWrapper(GraphWrapper _gw) :
2.247 + GraphWrapperSkeleton<GraphWrapper>(_gw) { }
2.248 +
2.249 + //UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
2.250
2.251 //void setGraph(Graph& _graph) { graph = &_graph; }
2.252 //Graph& getGraph() const { return (*graph); }
2.253 @@ -573,6 +570,28 @@
2.254 }
2.255 };
2.256
2.257 + typedef OutEdgeIt InEdgeIt;
2.258 +
2.259 + class EdgeIt : public Edge {
2.260 + friend class UndirGraphWrapper<GraphWrapper>;
2.261 + protected:
2.262 + NodeIt v;
2.263 + public:
2.264 + EdgeIt() : Edge() { }
2.265 + EdgeIt(const Invalid& i) : Edge(i) { }
2.266 + EdgeIt(const UndirGraphWrapper<GraphWrapper>& _G)
2.267 + : Edge() {
2.268 + out_or_in=true;
2.269 + //Node v;
2.270 + _G.first(v);
2.271 + if (_G.valid(v)) _G.gw.first(out); else out=INVALID;
2.272 + while (_G.valid(v) && !_G.gw.valid(out)) {
2.273 + _G.gw.next(v);
2.274 + if (_G.valid(v)) _G.gw.first(out);
2.275 + }
2.276 + }
2.277 + };
2.278 +
2.279 OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
2.280 e.out_or_in=true;
2.281 gw.first(e.out, n);
2.282 @@ -583,6 +602,22 @@
2.283 return e;
2.284 }
2.285
2.286 + EdgeIt& first(EdgeIt& e) const {
2.287 + e.out_or_in=true;
2.288 + //NodeIt v;
2.289 + first(e.v);
2.290 + if (valid(e.v)) gw.first(e.out, e.v); else e.out=INVALID;
2.291 + while (valid(e.v) && !gw.valid(e.out)) {
2.292 + gw.next(e.v);
2.293 + if (valid(e.v)) gw.first(e.out, e.v);
2.294 + }
2.295 + return e;
2.296 + }
2.297 +
2.298 + template<typename I> I& first(I& i) const { return gw.first(i); }
2.299 + template<typename I, typename P> I& first(I& i, const P& p) const {
2.300 + return graph->first(i, p); }
2.301 +
2.302 OutEdgeIt& next(OutEdgeIt& e) const {
2.303 if (e.out_or_in) {
2.304 Node n=gw.tail(e.out);
2.305 @@ -597,20 +632,20 @@
2.306 return e;
2.307 }
2.308
2.309 - Node aNode(const OutEdgeIt& e) const {
2.310 - if (e.out_or_in) return gw.tail(e); else return gw.head(e); }
2.311 - Node bNode(const OutEdgeIt& e) const {
2.312 - if (e.out_or_in) return gw.head(e); else return gw.tail(e); }
2.313 + EdgeIt& next(EdgeIt& e) const {
2.314 + //NodeIt v=tail(e);
2.315 + gw.next(e.out);
2.316 + while (valid(e.v) && !gw.valid(e.out)) {
2.317 + next(e.v);
2.318 + if (valid(e.v)) gw.first(e.out, e.v);
2.319 + }
2.320 + return e;
2.321 + }
2.322
2.323 - typedef OutEdgeIt InEdgeIt;
2.324 -
2.325 - template<typename I> I& first(I& i) const { return gw.first(i); }
2.326 -// template<typename I, typename P> I& first(I& i, const P& p) const {
2.327 -// return graph->first(i, p); }
2.328 + template<typename I> I& next(I &i) const { return gw.next(i); }
2.329
2.330 template<typename I> I getNext(const I& i) const {
2.331 return gw.getNext(i); }
2.332 - template<typename I> I& next(I &i) const { return gw.next(i); }
2.333
2.334 template< typename It > It first() const {
2.335 It e; first(e); return e; }
2.336 @@ -618,48 +653,52 @@
2.337 template< typename It > It first(const Node& v) const {
2.338 It e; first(e, v); return e; }
2.339
2.340 - Node head(const Edge& e) const { return gw.head(e); }
2.341 - Node tail(const Edge& e) const { return gw.tail(e); }
2.342 +// Node head(const Edge& e) const { return gw.head(e); }
2.343 +// Node tail(const Edge& e) const { return gw.tail(e); }
2.344
2.345 - template<typename I> bool valid(const I& i) const
2.346 - { return gw.valid(i); }
2.347 +// template<typename I> bool valid(const I& i) const
2.348 +// { return gw.valid(i); }
2.349
2.350 - //template<typename I> void setInvalid(const I &i);
2.351 - //{ return graph->setInvalid(i); }
2.352 -
2.353 - int nodeNum() const { return gw.nodeNum(); }
2.354 - int edgeNum() const { return gw.edgeNum(); }
2.355 +// int nodeNum() const { return gw.nodeNum(); }
2.356 +// int edgeNum() const { return gw.edgeNum(); }
2.357
2.358 // template<typename I> Node aNode(const I& e) const {
2.359 // return graph->aNode(e); }
2.360 // template<typename I> Node bNode(const I& e) const {
2.361 // return graph->bNode(e); }
2.362 +
2.363 + Node aNode(const OutEdgeIt& e) const {
2.364 + if (e.out_or_in) return gw.tail(e); else return gw.head(e); }
2.365 + Node bNode(const OutEdgeIt& e) const {
2.366 + if (e.out_or_in) return gw.head(e); else return gw.tail(e); }
2.367
2.368 - Node addNode() const { return gw.addNode(); }
2.369 +// Node addNode() const { return gw.addNode(); }
2.370 +
2.371 // FIXME: ez igy nem jo, mert nem
2.372 // Edge addEdge(const Node& tail, const Node& head) const {
2.373 // return graph->addEdge(tail, head); }
2.374
2.375 - template<typename I> void erase(const I& i) const { gw.erase(i); }
2.376 +// template<typename I> void erase(const I& i) const { gw.erase(i); }
2.377
2.378 - void clear() const { gw.clear(); }
2.379 +// void clear() const { gw.clear(); }
2.380
2.381 - template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
2.382 - public:
2.383 - NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
2.384 - GraphWrapper::NodeMap<T>(_G.gw) { }
2.385 - NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
2.386 - GraphWrapper::NodeMap<T>(_G.gw, a) { }
2.387 - };
2.388 +// template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
2.389 +// public:
2.390 +// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
2.391 +// GraphWrapper::NodeMap<T>(_G.gw) { }
2.392 +// NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
2.393 +// GraphWrapper::NodeMap<T>(_G.gw, a) { }
2.394 +// };
2.395
2.396 - template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
2.397 - public:
2.398 - EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
2.399 - GraphWrapper::EdgeMap<T>(_G.gw) { }
2.400 - EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
2.401 - GraphWrapper::EdgeMap<T>(_G.gw, a) { }
2.402 - };
2.403 - };
2.404 +// template<typename T> class EdgeMap :
2.405 +// public GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T> {
2.406 +// public:
2.407 +// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
2.408 +// GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T>(_G.gw) { }
2.409 +// EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
2.410 +// GraphWrapper::EdgeMap<T>(_G.gw, a) { }
2.411 +// };
2.412 + };
2.413
2.414
2.415