1.1 --- a/src/work/marci/graph_wrapper.h Mon Apr 05 18:24:37 2004 +0000
1.2 +++ b/src/work/marci/graph_wrapper.h Tue Apr 06 12:00:34 2004 +0000
1.3 @@ -12,6 +12,7 @@
1.4 Graph* graph;
1.5
1.6 public:
1.7 +// typedef Graph BaseGraph;
1.8 typedef Graph ParentGraph;
1.9
1.10 // TrivGraphWrapper() : graph(0) { }
1.11 @@ -24,9 +25,13 @@
1.12 public:
1.13 NodeIt() { }
1.14 NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
1.15 +// NodeIt(const typename BaseGraph::NodeIt& n) : Graph::NodeIt(n) { }
1.16 NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
1.17 NodeIt(const TrivGraphWrapper<Graph>& _G) :
1.18 Graph::NodeIt(*(_G.graph)) { }
1.19 +// operator typename BaseGraph::NodeIt() {
1.20 +// return typename BaseGraph::NodeIt(this->Graph::NodeIt);
1.21 +// }
1.22 };
1.23 typedef typename Graph::Edge Edge;
1.24 class OutEdgeIt : public Graph::OutEdgeIt {
1.25 @@ -59,10 +64,6 @@
1.26 i=NodeIt(*this);
1.27 return i;
1.28 }
1.29 - EdgeIt& first(EdgeIt& i) const {
1.30 - i=EdgeIt(*this);
1.31 - return i;
1.32 - }
1.33 // template<typename I> I& first(I& i) const {
1.34 // i=I(*this);
1.35 // return i;
1.36 @@ -75,6 +76,10 @@
1.37 i=InEdgeIt(*this, p);
1.38 return i;
1.39 }
1.40 + EdgeIt& first(EdgeIt& i) const {
1.41 + i=EdgeIt(*this);
1.42 + return i;
1.43 + }
1.44 // template<typename I, typename P> I& first(I& i, const P& p) const {
1.45 // i=I(*this, p);
1.46 // return i;
1.47 @@ -82,7 +87,11 @@
1.48
1.49 // template<typename I> I getNext(const I& i) const {
1.50 // return graph->getNext(i); }
1.51 - template<typename I> I& next(I &i) const { graph->next(i); return i; }
1.52 +// template<typename I> I& next(I &i) const { graph->next(i); return i; }
1.53 + NodeIt& next(NodeIt& i) const { graph->next(i); return i; }
1.54 + OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i); return i; }
1.55 + InEdgeIt& next(InEdgeIt& i) const { graph->next(i); return i; }
1.56 + EdgeIt& next(EdgeIt& i) const { graph->next(i); return i; }
1.57
1.58 template< typename It > It first() const {
1.59 It e; this->first(e); return e; }
1.60 @@ -157,6 +166,7 @@
1.61 Graph* graph;
1.62
1.63 public:
1.64 + typedef Graph BaseGraph;
1.65 typedef Graph ParentGraph;
1.66
1.67 // GraphWrapper() : graph(0) { }
1.68 @@ -204,10 +214,6 @@
1.69 i=NodeIt(*this);
1.70 return i;
1.71 }
1.72 - EdgeIt& first(EdgeIt& i) const {
1.73 - i=EdgeIt(*this);
1.74 - return i;
1.75 - }
1.76 // template<typename I> I& first(I& i) const {
1.77 // i=I(*this);
1.78 // return i;
1.79 @@ -220,6 +226,10 @@
1.80 i=InEdgeIt(*this, p);
1.81 return i;
1.82 }
1.83 + EdgeIt& first(EdgeIt& i) const {
1.84 + i=EdgeIt(*this);
1.85 + return i;
1.86 + }
1.87 // template<typename I, typename P> I& first(I& i, const P& p) const {
1.88 // i=I(*this, p);
1.89 // return i;
1.90 @@ -227,7 +237,11 @@
1.91
1.92 // template<typename I> I getNext(const I& i) const {
1.93 // return gw.getNext(i); }
1.94 - template<typename I> I& next(I &i) const { graph->next(i); return i; }
1.95 +// template<typename I> I& next(I &i) const { graph->next(i); return i; }
1.96 + NodeIt& next(NodeIt& i) const { graph->next(i); return i; }
1.97 + OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i); return i; }
1.98 + InEdgeIt& next(InEdgeIt& i) const { graph->next(i); return i; }
1.99 + EdgeIt& next(EdgeIt& i) const { graph->next(i); return i; }
1.100
1.101 template< typename It > It first() const {
1.102 It e; this->first(e); return e; }
1.103 @@ -385,44 +399,138 @@
1.104 };
1.105
1.106 //Subgraph on the same node-set and partial edge-set
1.107 - template<typename Graph, typename EdgeFilterMap>
1.108 + template<typename Graph, typename NodeFilterMap,
1.109 + typename EdgeFilterMap>
1.110 class SubGraphWrapper : public GraphWrapper<Graph> {
1.111 protected:
1.112 - EdgeFilterMap* filter_map;
1.113 + NodeFilterMap* node_filter_map;
1.114 + EdgeFilterMap* edge_filter_map;
1.115 public:
1.116 - typedef typename GraphWrapper<Graph>::Node Node;
1.117 - typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.118 - typedef typename GraphWrapper<Graph>::Edge Edge;
1.119 - typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
1.120 - typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt;
1.121 - typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt;
1.122 +// SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { }
1.123 + SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
1.124 + EdgeFilterMap& _edge_filter_map) :
1.125 + GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
1.126 + edge_filter_map(&_edge_filter_map) { }
1.127
1.128 -// SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { }
1.129 - SubGraphWrapper(Graph& _graph, EdgeFilterMap& _filter_map) :
1.130 - GraphWrapper<Graph>(_graph), filter_map(&_filter_map) { }
1.131
1.132 - template<typename I> I& first(I& i) const {
1.133 - graph->first(i);
1.134 - //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
1.135 - while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); }
1.136 + typedef typename Graph::Node Node;
1.137 + class NodeIt : public Graph::NodeIt {
1.138 +// typedef typename Graph::NodeIt GraphNodeIt;
1.139 + public:
1.140 + NodeIt() { }
1.141 + NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
1.142 + NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
1.143 + NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
1.144 + Graph::NodeIt(*(_G.graph)) {
1.145 + while (_G.graph->valid((*this)/*.GraphNodeIt*/) &&
1.146 + !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/])
1.147 + _G.graph->next((*this)/*.GraphNodeIt*/);
1.148 + }
1.149 + };
1.150 + typedef typename Graph::Edge Edge;
1.151 + class OutEdgeIt : public Graph::OutEdgeIt {
1.152 +// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1.153 + public:
1.154 + OutEdgeIt() { }
1.155 + OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
1.156 + OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
1.157 + OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>&
1.158 + _G, const Node& n) :
1.159 + Graph::OutEdgeIt(*(_G.graph), n) {
1.160 + while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) &&
1.161 + !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/])
1.162 + _G.graph->next((*this)/*.GraphOutEdgeIt*/);
1.163 + }
1.164 + };
1.165 + class InEdgeIt : public Graph::InEdgeIt {
1.166 +// typedef typename Graph::InEdgeIt GraphInEdgeIt;
1.167 + public:
1.168 + InEdgeIt() { }
1.169 + InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
1.170 + InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
1.171 + InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
1.172 + const Node& n) :
1.173 + Graph::InEdgeIt(*(_G.graph), n) {
1.174 + while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) &&
1.175 + !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/])
1.176 + _G.graph->next((*this)/*.GraphInEdgeIt*/);
1.177 + }
1.178 + };
1.179 +// //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.180 + class EdgeIt : public Graph::EdgeIt {
1.181 +// typedef typename Graph::EdgeIt GraphEdgeIt;
1.182 + public:
1.183 + EdgeIt() { }
1.184 + EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
1.185 + EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
1.186 + EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
1.187 + Graph::EdgeIt(*(_G.graph)) {
1.188 + while (_G.graph->valid((*this)/*.GraphEdgeIt*/) &&
1.189 + !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/])
1.190 + _G.graph->next((*this)/*.GraphEdgeIt*/);
1.191 + }
1.192 + };
1.193 +
1.194 + NodeIt& first(NodeIt& i) const {
1.195 + i=NodeIt(*this);
1.196 return i;
1.197 }
1.198 - template<typename I, typename P> I& first(I& i, const P& p) const {
1.199 - graph->first(i, p);
1.200 -// while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
1.201 - while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); }
1.202 + OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
1.203 + i=OutEdgeIt(*this, n);
1.204 + return i;
1.205 + }
1.206 + InEdgeIt& first(InEdgeIt& i, const Node& n) const {
1.207 + i=InEdgeIt(*this, n);
1.208 + return i;
1.209 + }
1.210 + EdgeIt& first(EdgeIt& i) const {
1.211 + i=EdgeIt(*this);
1.212 return i;
1.213 }
1.214
1.215 +// template<typename I> I& first(I& i) const {
1.216 +// graph->first(i);
1.217 +// //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
1.218 +// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
1.219 +// return i;
1.220 +// }
1.221 +// template<typename I, typename P> I& first(I& i, const P& p) const {
1.222 +// graph->first(i, p);
1.223 +// // while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
1.224 +// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
1.225 +// return i;
1.226 +// }
1.227 +
1.228 + NodeIt& next(NodeIt& i) const {
1.229 + graph->next(i);
1.230 + while (graph->valid(i) && !(*node_filter_map)[i]) { graph->next(i); }
1.231 + return i;
1.232 + }
1.233 + OutEdgeIt& next(OutEdgeIt& i) const {
1.234 + graph->next(i);
1.235 + while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
1.236 + return i;
1.237 + }
1.238 + InEdgeIt& next(InEdgeIt& i) const {
1.239 + graph->next(i);
1.240 + while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
1.241 + return i;
1.242 + }
1.243 + EdgeIt& next(EdgeIt& i) const {
1.244 + graph->next(i);
1.245 + while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
1.246 + return i;
1.247 + }
1.248 +
1.249 //template<typename I> I getNext(const I& i) const {
1.250 // return gw.getNext(i);
1.251 //}
1.252 - template<typename I> I& next(I &i) const {
1.253 - graph->next(i);
1.254 -// while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); }
1.255 - while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); }
1.256 - return i;
1.257 - }
1.258 +// template<typename I> I& next(I &i) const {
1.259 +// graph->next(i);
1.260 +// // while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); }
1.261 +// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
1.262 +// return i;
1.263 +// }
1.264
1.265 template< typename It > It first() const {
1.266 It e; this->first(e); return e; }
1.267 @@ -844,10 +952,7 @@
1.268
1.269
1.270 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.271 - class ResGraphWrapper : public GraphWrapper<Graph>{
1.272 - public:
1.273 - typedef typename GraphWrapper<Graph>::Node Node;
1.274 - typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.275 + class ResGraphWrapper : public GraphWrapper<Graph> {
1.276 protected:
1.277 typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1.278 typedef typename Graph::InEdgeIt GraphInEdgeIt;
1.279 @@ -865,6 +970,8 @@
1.280 friend class Edge;
1.281 friend class OutEdgeIt;
1.282
1.283 + typedef typename GraphWrapper<Graph>::Node Node;
1.284 + typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.285 class Edge {
1.286 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.287 protected:
1.288 @@ -892,8 +999,6 @@
1.289 if (out_or_in) return(out); else return(in);
1.290 }
1.291 };
1.292 -
1.293 -
1.294 class OutEdgeIt : public Edge {
1.295 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.296 public:
1.297 @@ -930,7 +1035,7 @@
1.298 };
1.299
1.300 //FIXME This is just for having InEdgeIt
1.301 - typedef void InEdgeIt;
1.302 +// class InEdgeIt : public Edge { };
1.303
1.304 class EdgeIt : public Edge {
1.305 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.306 @@ -993,18 +1098,25 @@
1.307 // }
1.308 };
1.309
1.310 - NodeIt& first(NodeIt& v) const { graph->first(v); return v; }
1.311 - OutEdgeIt& first(OutEdgeIt& e, Node v) const {
1.312 - e=OutEdgeIt(*this, v);
1.313 - return e;
1.314 + NodeIt& first(NodeIt& i) const {
1.315 + i=NodeIt(*this);
1.316 + return i;
1.317 }
1.318 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.319 + i=OutEdgeIt(*this, p);
1.320 + return i;
1.321 + }
1.322 + //FIXME Not yet implemented
1.323 + //InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.324 + //i=InEdgeIt(*this, p);
1.325 + // return i;
1.326 + //}
1.327 EdgeIt& first(EdgeIt& e) const {
1.328 e=EdgeIt(*this);
1.329 return e;
1.330 }
1.331
1.332 NodeIt& next(NodeIt& n) const { graph->next(n); return n; }
1.333 -
1.334 OutEdgeIt& next(OutEdgeIt& e) const {
1.335 if (e.out_or_in) {
1.336 Node v=graph->aNode(e.out);
1.337 @@ -1021,7 +1133,10 @@
1.338 }
1.339 return e;
1.340 }
1.341 -
1.342 + //FIXME Not yet implemented
1.343 + //InEdgeIt& next(InEdgeIt& e) const {
1.344 + // return e;
1.345 + //}
1.346 EdgeIt& next(EdgeIt& e) const {
1.347 if (e.out_or_in) {
1.348 graph->next(e.out);
1.349 @@ -1169,38 +1284,106 @@
1.350 protected:
1.351 FirstOutEdgesMap* first_out_edges;
1.352 public:
1.353 - typedef typename GraphWrapper<Graph>::Node Node;
1.354 - typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.355 - typedef typename GraphWrapper<Graph>::Edge Edge;
1.356 - typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
1.357 - typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt;
1.358 - typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt;
1.359 -
1.360 ErasingFirstGraphWrapper(Graph& _graph,
1.361 FirstOutEdgesMap& _first_out_edges) :
1.362 GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
1.363
1.364 - template<typename I> I& first(I& i) const {
1.365 - graph->first(i);
1.366 + typedef typename Graph::Node Node;
1.367 + class NodeIt : public Graph::NodeIt {
1.368 + public:
1.369 + NodeIt() { }
1.370 + NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
1.371 + NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
1.372 + NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1.373 + Graph::NodeIt(*(_G.graph)) { }
1.374 + };
1.375 + typedef typename Graph::Edge Edge;
1.376 + class OutEdgeIt : public Graph::OutEdgeIt {
1.377 + public:
1.378 + OutEdgeIt() { }
1.379 + OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
1.380 + OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
1.381 + OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1.382 + const Node& n) :
1.383 + Graph::OutEdgeIt((*_G.first_out_edges)[n]) { }
1.384 + };
1.385 + class InEdgeIt : public Graph::InEdgeIt {
1.386 + public:
1.387 + InEdgeIt() { }
1.388 + InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
1.389 + InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
1.390 + InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1.391 + const Node& n) :
1.392 + Graph::InEdgeIt(*(_G.graph), n) { }
1.393 + };
1.394 + //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.395 + class EdgeIt : public Graph::EdgeIt {
1.396 + public:
1.397 + EdgeIt() { }
1.398 + EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
1.399 + EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
1.400 + EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1.401 + Graph::EdgeIt(*(_G.graph)) { }
1.402 + };
1.403 +
1.404 + NodeIt& first(NodeIt& i) const {
1.405 + i=NodeIt(*this);
1.406 return i;
1.407 }
1.408 - OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1.409 -// e=first_out_edges->get(n);
1.410 - e=(*first_out_edges)[n];
1.411 - return e;
1.412 - }
1.413 - template<typename I, typename P> I& first(I& i, const P& p) const {
1.414 - graph->first(i, p);
1.415 + OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
1.416 + i=OutEdgeIt(*this, n);
1.417 +// i=(*first_out_edges)[n];
1.418 return i;
1.419 }
1.420 + InEdgeIt& first(InEdgeIt& i, const Node& n) const {
1.421 + i=InEdgeIt(*this, n);
1.422 + return i;
1.423 + }
1.424 + EdgeIt& first(EdgeIt& i) const {
1.425 + i=EdgeIt(*this);
1.426 + return i;
1.427 + }
1.428 +
1.429 +// template<typename I> I& first(I& i) const {
1.430 +// graph->first(i);
1.431 +// return i;
1.432 +// }
1.433 +// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1.434 +// // e=first_out_edges->get(n);
1.435 +// e=(*first_out_edges)[n];
1.436 +// return e;
1.437 +// }
1.438 +// template<typename I, typename P> I& first(I& i, const P& p) const {
1.439 +// graph->first(i, p);
1.440 +// return i;
1.441 +// }
1.442
1.443 //template<typename I> I getNext(const I& i) const {
1.444 // return gw.getNext(i);
1.445 //}
1.446 - template<typename I> I& next(I &i) const {
1.447 +
1.448 +
1.449 + NodeIt& next(NodeIt& i) const {
1.450 graph->next(i);
1.451 return i;
1.452 }
1.453 + OutEdgeIt& next(OutEdgeIt& i) const {
1.454 + graph->next(i);
1.455 + return i;
1.456 + }
1.457 + InEdgeIt& next(InEdgeIt& i) const {
1.458 + graph->next(i);
1.459 + return i;
1.460 + }
1.461 + EdgeIt& next(EdgeIt& i) const {
1.462 + graph->next(i);
1.463 + return i;
1.464 + }
1.465 +
1.466 +// template<typename I> I& next(I &i) const {
1.467 +// graph->next(i);
1.468 +// return i;
1.469 +// }
1.470
1.471 template< typename It > It first() const {
1.472 It e; this->first(e); return e; }