1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/klao/path.h Sun Mar 21 16:16:08 2004 +0000
1.3 @@ -0,0 +1,383 @@
1.4 +// -*- c++ -*- //
1.5 +
1.6 +/**
1.7 + *
1.8 + * Class for representing paths in graphs.
1.9 + *
1.10 + */
1.11 +
1.12 +#ifndef HUGO_PATH_H
1.13 +#define HUGO_PATH_H
1.14 +
1.15 +#include <deque>
1.16 +
1.17 +#include <invalid.h>
1.18 +
1.19 +namespace hugo {
1.20 +
1.21 + /* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata
1.22 + elott. Eleg bonyinak nez ki, ahogyan azokat az STL-ben hasznaljak. */
1.23 +
1.24 + template<typename Graph>
1.25 + class Path {
1.26 +
1.27 + public:
1.28 + typedef typename Graph::Edge GraphEdge;
1.29 + typedef typename Graph::Node GraphNode;
1.30 + class NodeIt;
1.31 + class EdgeIt;
1.32 +
1.33 + protected:
1.34 + Graph& G;
1.35 + // FIXME: ehelyett eleg lenne tarolni ket boolt: a ket szelso el
1.36 + // iranyitasat:
1.37 + GraphNode _first, _last;
1.38 + typedef std::deque<GraphEdge> Container;
1.39 + Container edges;
1.40 +
1.41 + public:
1.42 +
1.43 + Path(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {}
1.44 +
1.45 + /// Subpath defined by two nodes
1.46 + Path(Path const& P, NodeIt a, NodeIt b) { FIXME; }
1.47 + /// Subpath defined by tow edges. Contains edges in [a,b)
1.48 + Path(Path const& P, EdgeIt a, EdgeIt b) { FIXME; }
1.49 +
1.50 + size_t length() const { return edges.size(); }
1.51 + GraphNode from() const { return _first; }
1.52 + GraphNode to() const { return _last; }
1.53 +
1.54 + NodeIt& first(NodeIt &n) const { return nth(n, 0); }
1.55 + EdgeIt& first(EdgeIt &e) const { return nth(e, 0); }
1.56 + template<typename It>
1.57 + It first() const {
1.58 + It e;
1.59 + first(e);
1.60 + return e;
1.61 + }
1.62 +
1.63 + NodeIt& nth(NodeIt &, size_t) const;
1.64 + EdgeIt& nth(EdgeIt &, size_t) const;
1.65 + template<typename It>
1.66 + It nth(size_t n) const {
1.67 + It e;
1.68 + nth(e, n);
1.69 + return e;
1.70 + }
1.71 +
1.72 + bool valid(const NodeIt &n) const { return n.idx <= length(); }
1.73 + bool valid(const EdgeIt &e) const { return e.it < edges.end(); }
1.74 +
1.75 + bool isForward(const EdgeIt &e) const { return e.forw; }
1.76 +
1.77 + EdgeIt& next(EdgeIt &e) const;
1.78 + NodeIt& next(NodeIt &n) const;
1.79 + template <typename It>
1.80 + It getNext(It it) const {
1.81 + It tmp(it); return next(tmp);
1.82 + }
1.83 +
1.84 + // A path is constructed using the following four functions.
1.85 + // They return false if the requested operation is inconsistent
1.86 + // with the path constructed so far.
1.87 + // If your path has only one edge you MUST set either "from" or "to"!
1.88 + // So you probably SHOULD call it in any case to be safe (and check the
1.89 + // returned value to check if your path is consistent with your idea).
1.90 + bool pushFront(const GraphEdge &e);
1.91 + bool pushBack(const GraphEdge &e);
1.92 + bool setFrom(const GraphNode &n);
1.93 + bool setTo(const GraphNode &n);
1.94 +
1.95 + // WARNING: these two functions return the head/tail of an edge with
1.96 + // respect to the direction of the path!
1.97 + // So G.head(P.graphEdge(e)) == P.graphNode(P.head(e)) holds only if
1.98 + // P.forward(e) is true (or the edge is a loop)!
1.99 + NodeIt head(const EdgeIt& e) const;
1.100 + NodeIt tail(const EdgeIt& e) const;
1.101 +
1.102 + // FIXME: ezeknek valami jobb nev kellene!!!
1.103 + GraphEdge graphEdge(const EdgeIt& e) const;
1.104 + GraphNode graphNode(const NodeIt& n) const;
1.105 +
1.106 +
1.107 + /*** Iterator classes ***/
1.108 + class EdgeIt {
1.109 + friend class Path;
1.110 +
1.111 + typename Container::const_iterator it;
1.112 + bool forw;
1.113 + public:
1.114 + // FIXME: jarna neki ilyen is...
1.115 + // EdgeIt(Invalid);
1.116 +
1.117 + bool forward() const { return forw; }
1.118 +
1.119 + bool operator==(const EdgeIt& e) const { return it==e.it; }
1.120 + bool operator!=(const EdgeIt& e) const { return it!=e.it; }
1.121 + bool operator<(const EdgeIt& e) const { return it<e.it; }
1.122 + };
1.123 +
1.124 + class NodeIt {
1.125 + friend class Path;
1.126 + friend class EdgeIt;
1.127 +
1.128 + int idx;
1.129 + bool tail; // Is this node the tail of the edge with same idx?
1.130 +
1.131 + public:
1.132 + // FIXME: jarna neki ilyen is...
1.133 + // NodeIt(Invalid);
1.134 +
1.135 + bool operator==(const NodeIt& n) const { return idx==n.idx; }
1.136 + bool operator!=(const NodeIt& n) const { return idx!=n.idx; }
1.137 + bool operator<(const NodeIt& n) const { return idx<n.idx; }
1.138 + };
1.139 +
1.140 + private:
1.141 + bool edgeIncident(const GraphEdge &e, const GraphNode &a,
1.142 + GraphNode &b);
1.143 + bool connectTwoEdges(const GraphEdge &e, const GraphEdge &f);
1.144 + };
1.145 +
1.146 + template<typename Gr>
1.147 + typename Path<Gr>::EdgeIt&
1.148 + Path<Gr>::next(Path::EdgeIt &e) const {
1.149 + if( e.it == edges.end() )
1.150 + return e;
1.151 +
1.152 + GraphNode common_node = ( e.forw ? G.head(*e.it) : G.tail(*e.it) );
1.153 + ++e.it;
1.154 +
1.155 + // Invalid edgeit is always forward :)
1.156 + if( e.it == edges.end() ) {
1.157 + e.forw = true;
1.158 + return e;
1.159 + }
1.160 +
1.161 + e.forw = ( G.tail(*e.it) == common_node );
1.162 + return e;
1.163 + }
1.164 +
1.165 + template<typename Gr>
1.166 + typename Path<Gr>::NodeIt& Path<Gr>::next(NodeIt &n) const {
1.167 + if( n.idx >= length() ) {
1.168 + // FIXME: invalid
1.169 + n.idx = length()+1;
1.170 + return n;
1.171 + }
1.172 +
1.173 +
1.174 + GraphNode next_node = ( n.tail ? G.head(edges[n.idx]) :
1.175 + G.tail(edges[n.idx]) );
1.176 + ++n.idx;
1.177 + if( n.idx < length() ) {
1.178 + n.tail = ( next_node == G.tail(edges[n.idx]) );
1.179 + }
1.180 + else {
1.181 + n.tail = true;
1.182 + }
1.183 +
1.184 + return n;
1.185 + }
1.186 +
1.187 + template<typename Gr>
1.188 + bool Path<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a,
1.189 + GraphNode &b) {
1.190 + if( G.tail(e) == a ) {
1.191 + b=G.head(e);
1.192 + return true;
1.193 + }
1.194 + if( G.head(e) == a ) {
1.195 + b=G.tail(e);
1.196 + return true;
1.197 + }
1.198 + return false;
1.199 + }
1.200 +
1.201 + template<typename Gr>
1.202 + bool Path<Gr>::connectTwoEdges(const GraphEdge &e,
1.203 + const GraphEdge &f) {
1.204 + if( edgeIncident(f, G.tail(e), _last) ) {
1.205 + _first = G.head(e);
1.206 + return true;
1.207 + }
1.208 + if( edgeIncident(f, G.head(e), _last) ) {
1.209 + _first = G.tail(e);
1.210 + return true;
1.211 + }
1.212 + return false;
1.213 + }
1.214 +
1.215 + template<typename Gr>
1.216 + bool Path<Gr>::pushFront(const GraphEdge &e) {
1.217 + if( G.valid(_first) ) {
1.218 + if( edgeIncident(e, _first, _first) ) {
1.219 + edges.push_front(e);
1.220 + return true;
1.221 + }
1.222 + else
1.223 + return false;
1.224 + }
1.225 + else if( length() < 1 || connectTwoEdges(e, edges[0]) ) {
1.226 + edges.push_front(e);
1.227 + return true;
1.228 + }
1.229 + else
1.230 + return false;
1.231 + }
1.232 +
1.233 + template<typename Gr>
1.234 + bool Path<Gr>::pushBack(const GraphEdge &e) {
1.235 + if( G.valid(_last) ) {
1.236 + if( edgeIncident(e, _last, _last) ) {
1.237 + edges.push_back(e);
1.238 + return true;
1.239 + }
1.240 + else
1.241 + return false;
1.242 + }
1.243 + else if( length() < 1 || connectTwoEdges(edges[0], e) ) {
1.244 + edges.push_back(e);
1.245 + return true;
1.246 + }
1.247 + else
1.248 + return false;
1.249 + }
1.250 +
1.251 +
1.252 + template<typename Gr>
1.253 + bool Path<Gr>::setFrom(const GraphNode &n) {
1.254 + if( G.valid(_first) ) {
1.255 + return _first == n;
1.256 + }
1.257 + else {
1.258 + if( length() > 0) {
1.259 + if( edgeIncident(edges[0], n, _last) ) {
1.260 + _first = n;
1.261 + return true;
1.262 + }
1.263 + else return false;
1.264 + }
1.265 + else {
1.266 + _first = _last = n;
1.267 + return true;
1.268 + }
1.269 + }
1.270 + }
1.271 +
1.272 + template<typename Gr>
1.273 + bool Path<Gr>::setTo(const GraphNode &n) {
1.274 + if( G.valid(_last) ) {
1.275 + return _last == n;
1.276 + }
1.277 + else {
1.278 + if( length() > 0) {
1.279 + if( edgeIncident(edges[0], n, _first) ) {
1.280 + _last = n;
1.281 + return true;
1.282 + }
1.283 + else return false;
1.284 + }
1.285 + else {
1.286 + _first = _last = n;
1.287 + return true;
1.288 + }
1.289 + }
1.290 + }
1.291 +
1.292 +
1.293 + template<typename Gr>
1.294 + typename Path<Gr>::NodeIt
1.295 + Path<Gr>::tail(const EdgeIt& e) const {
1.296 + NodeIt n;
1.297 +
1.298 + if( e.it == edges.end() ) {
1.299 + // FIXME: invalid-> invalid
1.300 + n.idx = length() + 1;
1.301 + n.tail = true;
1.302 + return n;
1.303 + }
1.304 +
1.305 + n.idx = e.it-edges.begin();
1.306 + n.tail = e.forw;
1.307 + }
1.308 +
1.309 + template<typename Gr>
1.310 + typename Path<Gr>::NodeIt
1.311 + Path<Gr>::head(const EdgeIt& e) const {
1.312 + if( e.it == edges.end()-1 ) {
1.313 + return _last;
1.314 + }
1.315 +
1.316 + EdgeIt next_edge = e;
1.317 + next(next_edge);
1.318 + return tail(next_edge);
1.319 + }
1.320 +
1.321 + template<typename Gr>
1.322 + typename Path<Gr>::GraphEdge
1.323 + Path<Gr>::graphEdge(const EdgeIt& e) const {
1.324 + if( e.it != edges.end() ) {
1.325 + return *e.it;
1.326 + }
1.327 + else {
1.328 + return INVALID;
1.329 + }
1.330 + }
1.331 +
1.332 + template<typename Gr>
1.333 + typename Path<Gr>::GraphNode
1.334 + Path<Gr>::graphNode(const NodeIt& n) const {
1.335 + if( n.idx < length() ) {
1.336 + return n.tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]);
1.337 + }
1.338 + else if( n.idx == length() ) {
1.339 + return _last;
1.340 + }
1.341 + else {
1.342 + return INVALID;
1.343 + }
1.344 + }
1.345 +
1.346 + template<typename Gr>
1.347 + typename Path<Gr>::EdgeIt& Path<Gr>::nth(EdgeIt &e, size_t k) const {
1.348 + if( k<0 || k>=length() ) {
1.349 + // FIXME: invalid EdgeIt
1.350 + e.it = edges.end();
1.351 + e.forw = true;
1.352 + return e;
1.353 + }
1.354 +
1.355 + e.it = edges.begin()+k;
1.356 + if(k==0) {
1.357 + e.forw = ( G.tail(*e.it) == _first );
1.358 + }
1.359 + else {
1.360 + e.forw = ( G.tail(*e.it) == G.tail(edges[k-1]) ||
1.361 + G.tail(*e.it) == G.head(edges[k-1]) );
1.362 + }
1.363 + return e;
1.364 + }
1.365 +
1.366 + template<typename Gr>
1.367 + typename Path<Gr>::NodeIt& Path<Gr>::nth(NodeIt &n, size_t k) const {
1.368 + if( k<0 || k>length() ) {
1.369 + // FIXME: invalid NodeIt
1.370 + n.idx = length()+1;
1.371 + n.tail = true;
1.372 + return n;
1.373 + }
1.374 + if( k==length() ) {
1.375 + n.idx = length();
1.376 + n.tail = true;
1.377 + return n;
1.378 + }
1.379 + n = tail(nth<EdgeIt>(k));
1.380 + return n;
1.381 + }
1.382 +
1.383 +
1.384 +} // namespace hugo
1.385 +
1.386 +#endif // HUGO_PATH_H