1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/work/klao/.cvsignore	Sun Mar 21 16:16:08 2004 +0000
     1.3 @@ -0,0 +1,2 @@
     1.4 +.depend
     1.5 +path_test

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/src/work/klao/Makefile	Sun Mar 21 16:16:08 2004 +0000
     2.3 @@ -0,0 +1,4 @@
     2.4 +BINARIES = path_test
     2.5 +INCLUDEDIRS= -I. -I.. -I../../include -I../{marci,jacint,alpar,johanna,akos}
     2.6 +include ../makefile
     2.7 +

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/src/work/klao/path.h	Sun Mar 21 16:16:08 2004 +0000
     3.3 @@ -0,0 +1,383 @@
     3.4 +// -*- c++ -*- //
     3.5 +
     3.6 +/**
     3.7 + *
     3.8 + * Class for representing paths in graphs.
     3.9 + *
    3.10 + */
    3.11 +
    3.12 +#ifndef HUGO_PATH_H
    3.13 +#define HUGO_PATH_H
    3.14 +
    3.15 +#include <deque>
    3.16 +
    3.17 +#include <invalid.h>
    3.18 +
    3.19 +namespace hugo {
    3.20 +
    3.21 +  /* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata
    3.22 +     elott. Eleg bonyinak nez ki, ahogyan azokat az STL-ben hasznaljak. */
    3.23 +
    3.24 +  template<typename Graph>
    3.25 +  class Path {
    3.26 +
    3.27 +  public:
    3.28 +    typedef typename Graph::Edge GraphEdge;
    3.29 +    typedef typename Graph::Node GraphNode;
    3.30 +    class NodeIt;
    3.31 +    class EdgeIt;
    3.32 +
    3.33 +  protected:
    3.34 +    Graph& G;
    3.35 +    // FIXME: ehelyett eleg lenne tarolni ket boolt: a ket szelso el
    3.36 +    // iranyitasat:
    3.37 +    GraphNode _first, _last;
    3.38 +    typedef std::deque<GraphEdge> Container;
    3.39 +    Container edges;
    3.40 +
    3.41 +  public:
    3.42 +
    3.43 +    Path(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {}
    3.44 +
    3.45 +    /// Subpath defined by two nodes
    3.46 +    Path(Path const& P, NodeIt a, NodeIt b) { FIXME; }
    3.47 +    /// Subpath defined by tow edges. Contains edges in [a,b)
    3.48 +    Path(Path const& P, EdgeIt a, EdgeIt b) { FIXME; }
    3.49 +    
    3.50 +    size_t length() const { return edges.size(); }
    3.51 +    GraphNode from() const { return _first; }
    3.52 +    GraphNode to() const { return _last; }
    3.53 +
    3.54 +    NodeIt& first(NodeIt &n) const { return nth(n, 0); }
    3.55 +    EdgeIt& first(EdgeIt &e) const { return nth(e, 0); }
    3.56 +    template<typename It>
    3.57 +    It first() const { 
    3.58 +      It e;
    3.59 +      first(e);
    3.60 +      return e; 
    3.61 +    }
    3.62 +
    3.63 +    NodeIt& nth(NodeIt &, size_t) const;
    3.64 +    EdgeIt& nth(EdgeIt &, size_t) const;
    3.65 +    template<typename It>
    3.66 +    It nth(size_t n) const { 
    3.67 +      It e;
    3.68 +      nth(e, n);
    3.69 +      return e; 
    3.70 +    }
    3.71 +
    3.72 +    bool valid(const NodeIt &n) const { return n.idx <= length(); }
    3.73 +    bool valid(const EdgeIt &e) const { return e.it < edges.end(); }
    3.74 +
    3.75 +    bool isForward(const EdgeIt &e) const { return e.forw; }
    3.76 +
    3.77 +    EdgeIt& next(EdgeIt &e) const;
    3.78 +    NodeIt& next(NodeIt &n) const;
    3.79 +    template <typename It>
    3.80 +    It getNext(It it) const {
    3.81 +      It tmp(it); return next(tmp);
    3.82 +    }
    3.83 +
    3.84 +    // A path is constructed using the following four functions.
    3.85 +    // They return false if the requested operation is inconsistent
    3.86 +    // with the path constructed so far.
    3.87 +    // If your path has only one edge you MUST set either "from" or "to"!
    3.88 +    // So you probably SHOULD call it in any case to be safe (and check the
    3.89 +    // returned value to check if your path is consistent with your idea).
    3.90 +    bool pushFront(const GraphEdge &e);
    3.91 +    bool pushBack(const GraphEdge &e);
    3.92 +    bool setFrom(const GraphNode &n);
    3.93 +    bool setTo(const GraphNode &n);
    3.94 +
    3.95 +    // WARNING: these two functions return the head/tail of an edge with
    3.96 +    // respect to the direction of the path!
    3.97 +    // So G.head(P.graphEdge(e)) == P.graphNode(P.head(e)) holds only if 
    3.98 +    // P.forward(e) is true (or the edge is a loop)!
    3.99 +    NodeIt head(const EdgeIt& e) const;
   3.100 +    NodeIt tail(const EdgeIt& e) const;
   3.101 +
   3.102 +    // FIXME: ezeknek valami jobb nev kellene!!!
   3.103 +    GraphEdge graphEdge(const EdgeIt& e) const;
   3.104 +    GraphNode graphNode(const NodeIt& n) const;
   3.105 +
   3.106 +
   3.107 +    /*** Iterator classes ***/
   3.108 +    class EdgeIt {
   3.109 +      friend class Path;
   3.110 +
   3.111 +      typename Container::const_iterator it;
   3.112 +      bool forw;
   3.113 +    public:
   3.114 +      // FIXME: jarna neki ilyen is...
   3.115 +      // EdgeIt(Invalid);
   3.116 +
   3.117 +      bool forward() const { return forw; }
   3.118 +
   3.119 +      bool operator==(const EdgeIt& e) const { return it==e.it; }
   3.120 +      bool operator!=(const EdgeIt& e) const { return it!=e.it; }
   3.121 +      bool operator<(const EdgeIt& e) const { return it<e.it; }
   3.122 +    };
   3.123 +
   3.124 +    class NodeIt {
   3.125 +      friend class Path;
   3.126 +      friend class EdgeIt;
   3.127 +
   3.128 +      int idx;
   3.129 +      bool tail;  // Is this node the tail of the edge with same idx?
   3.130 +
   3.131 +    public:
   3.132 +      // FIXME: jarna neki ilyen is...
   3.133 +      // NodeIt(Invalid);
   3.134 +
   3.135 +      bool operator==(const NodeIt& n) const { return idx==n.idx; }
   3.136 +      bool operator!=(const NodeIt& n) const { return idx!=n.idx; }
   3.137 +      bool operator<(const NodeIt& n) const { return idx<n.idx; }
   3.138 +    };
   3.139 +
   3.140 +  private:
   3.141 +    bool edgeIncident(const GraphEdge &e, const GraphNode &a,
   3.142 +		      GraphNode &b);
   3.143 +    bool connectTwoEdges(const GraphEdge &e, const GraphEdge &f);
   3.144 +  };
   3.145 +
   3.146 +  template<typename Gr>
   3.147 +  typename Path<Gr>::EdgeIt&
   3.148 +  Path<Gr>::next(Path::EdgeIt &e) const {
   3.149 +    if( e.it == edges.end() ) 
   3.150 +      return e;
   3.151 +
   3.152 +    GraphNode common_node = ( e.forw ? G.head(*e.it) : G.tail(*e.it) );
   3.153 +    ++e.it;
   3.154 +
   3.155 +    // Invalid edgeit is always forward :)
   3.156 +    if( e.it == edges.end() ) {
   3.157 +      e.forw = true;
   3.158 +      return e;
   3.159 +    }
   3.160 +
   3.161 +    e.forw = ( G.tail(*e.it) == common_node );
   3.162 +    return e;
   3.163 +  }
   3.164 +
   3.165 +  template<typename Gr>
   3.166 +  typename Path<Gr>::NodeIt& Path<Gr>::next(NodeIt &n) const {
   3.167 +    if( n.idx >= length() ) {
   3.168 +      // FIXME: invalid
   3.169 +      n.idx = length()+1;
   3.170 +      return n;
   3.171 +    }
   3.172 +
   3.173 +    
   3.174 +    GraphNode next_node = ( n.tail ? G.head(edges[n.idx]) :
   3.175 +			      G.tail(edges[n.idx]) );
   3.176 +    ++n.idx;
   3.177 +    if( n.idx < length() ) {
   3.178 +      n.tail = ( next_node == G.tail(edges[n.idx]) );
   3.179 +    }
   3.180 +    else {
   3.181 +      n.tail = true;
   3.182 +    }
   3.183 +
   3.184 +    return n;
   3.185 +  }
   3.186 +
   3.187 +  template<typename Gr>
   3.188 +  bool Path<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a,
   3.189 +			  GraphNode &b) {
   3.190 +    if( G.tail(e) == a ) {
   3.191 +      b=G.head(e);
   3.192 +      return true;
   3.193 +    }
   3.194 +    if( G.head(e) == a ) {
   3.195 +      b=G.tail(e);
   3.196 +      return true;
   3.197 +    }
   3.198 +    return false;
   3.199 +  }
   3.200 +
   3.201 +  template<typename Gr>
   3.202 +  bool Path<Gr>::connectTwoEdges(const GraphEdge &e,
   3.203 +			     const GraphEdge &f) {
   3.204 +    if( edgeIncident(f, G.tail(e), _last) ) {
   3.205 +      _first = G.head(e);
   3.206 +      return true;
   3.207 +    }
   3.208 +    if( edgeIncident(f, G.head(e), _last) ) {
   3.209 +      _first = G.tail(e);
   3.210 +      return true;
   3.211 +    }
   3.212 +    return false;
   3.213 +  }
   3.214 +
   3.215 +  template<typename Gr>
   3.216 +  bool Path<Gr>::pushFront(const GraphEdge &e) {
   3.217 +    if( G.valid(_first) ) {
   3.218 +	if( edgeIncident(e, _first, _first) ) {
   3.219 +	  edges.push_front(e);
   3.220 +	  return true;
   3.221 +	}
   3.222 +	else
   3.223 +	  return false;
   3.224 +    }
   3.225 +    else if( length() < 1 || connectTwoEdges(e, edges[0]) ) {
   3.226 +      edges.push_front(e);
   3.227 +      return true;
   3.228 +    }
   3.229 +    else
   3.230 +      return false;
   3.231 +  }
   3.232 +
   3.233 +  template<typename Gr>
   3.234 +  bool Path<Gr>::pushBack(const GraphEdge &e) {
   3.235 +    if( G.valid(_last) ) {
   3.236 +	if( edgeIncident(e, _last, _last) ) {
   3.237 +	  edges.push_back(e);
   3.238 +	  return true;
   3.239 +	}
   3.240 +	else
   3.241 +	  return false;
   3.242 +    }
   3.243 +    else if( length() < 1 || connectTwoEdges(edges[0], e) ) {
   3.244 +      edges.push_back(e);
   3.245 +      return true;
   3.246 +    }
   3.247 +    else
   3.248 +      return false;
   3.249 +  }
   3.250 +
   3.251 +
   3.252 +  template<typename Gr>
   3.253 +  bool Path<Gr>::setFrom(const GraphNode &n) {
   3.254 +    if( G.valid(_first) ) {
   3.255 +      return _first == n;
   3.256 +    }
   3.257 +    else {
   3.258 +      if( length() > 0) {
   3.259 +	if( edgeIncident(edges[0], n, _last) ) {
   3.260 +	  _first = n;
   3.261 +	  return true;
   3.262 +	}
   3.263 +	else return false;
   3.264 +      }
   3.265 +      else {
   3.266 +	_first = _last = n;
   3.267 +	return true;
   3.268 +      }
   3.269 +    }
   3.270 +  }
   3.271 +
   3.272 +  template<typename Gr>
   3.273 +  bool Path<Gr>::setTo(const GraphNode &n) {
   3.274 +    if( G.valid(_last) ) {
   3.275 +      return _last == n;
   3.276 +    }
   3.277 +    else {
   3.278 +      if( length() > 0) {
   3.279 +	if( edgeIncident(edges[0], n, _first) ) {
   3.280 +	  _last = n;
   3.281 +	  return true;
   3.282 +	}
   3.283 +	else return false;
   3.284 +      }
   3.285 +      else {
   3.286 +	_first = _last = n;
   3.287 +	return true;
   3.288 +      }
   3.289 +    }
   3.290 +  }
   3.291 +
   3.292 +
   3.293 +  template<typename Gr>
   3.294 +  typename Path<Gr>::NodeIt
   3.295 +  Path<Gr>::tail(const EdgeIt& e) const {
   3.296 +    NodeIt n;
   3.297 +
   3.298 +    if( e.it == edges.end() ) {
   3.299 +      // FIXME: invalid-> invalid
   3.300 +      n.idx = length() + 1;
   3.301 +      n.tail = true;
   3.302 +      return n;
   3.303 +    }
   3.304 +
   3.305 +    n.idx = e.it-edges.begin();
   3.306 +    n.tail = e.forw;
   3.307 +  }
   3.308 +
   3.309 +  template<typename Gr>
   3.310 +  typename Path<Gr>::NodeIt
   3.311 +  Path<Gr>::head(const EdgeIt& e) const {
   3.312 +    if( e.it == edges.end()-1 ) {
   3.313 +      return _last;
   3.314 +    }
   3.315 +
   3.316 +    EdgeIt next_edge = e;
   3.317 +    next(next_edge);
   3.318 +    return tail(next_edge);
   3.319 +  }
   3.320 +      
   3.321 +  template<typename Gr>
   3.322 +  typename Path<Gr>::GraphEdge
   3.323 +  Path<Gr>::graphEdge(const EdgeIt& e) const {
   3.324 +    if( e.it != edges.end() ) {
   3.325 +      return *e.it;
   3.326 +    }
   3.327 +    else {
   3.328 +      return INVALID;
   3.329 +    }
   3.330 +  }
   3.331 +  
   3.332 +  template<typename Gr>
   3.333 +  typename Path<Gr>::GraphNode
   3.334 +  Path<Gr>::graphNode(const NodeIt& n) const {
   3.335 +    if( n.idx < length() ) {
   3.336 +      return n.tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]);
   3.337 +    }
   3.338 +    else if( n.idx == length() ) {
   3.339 +      return _last;
   3.340 +    }
   3.341 +    else {
   3.342 +      return INVALID;
   3.343 +    }
   3.344 +  }
   3.345 +
   3.346 +  template<typename Gr>
   3.347 +  typename Path<Gr>::EdgeIt& Path<Gr>::nth(EdgeIt &e, size_t k) const {
   3.348 +    if( k<0 || k>=length() ) {
   3.349 +      // FIXME: invalid EdgeIt
   3.350 +      e.it = edges.end();
   3.351 +      e.forw = true;
   3.352 +      return e;
   3.353 +    }
   3.354 +
   3.355 +    e.it = edges.begin()+k;
   3.356 +    if(k==0) {
   3.357 +      e.forw = ( G.tail(*e.it) == _first );
   3.358 +    }
   3.359 +    else {
   3.360 +      e.forw = ( G.tail(*e.it) == G.tail(edges[k-1]) ||
   3.361 +		 G.tail(*e.it) == G.head(edges[k-1]) );
   3.362 +    }
   3.363 +    return e;
   3.364 +  }
   3.365 +    
   3.366 +  template<typename Gr>
   3.367 +  typename Path<Gr>::NodeIt& Path<Gr>::nth(NodeIt &n, size_t k) const {
   3.368 +    if( k<0 || k>length() ) {
   3.369 +      // FIXME: invalid NodeIt
   3.370 +      n.idx = length()+1;
   3.371 +      n.tail = true;
   3.372 +      return n;
   3.373 +    }
   3.374 +    if( k==length() ) {
   3.375 +      n.idx = length();
   3.376 +      n.tail = true;
   3.377 +      return n;
   3.378 +    }
   3.379 +    n = tail(nth<EdgeIt>(k));
   3.380 +    return n;
   3.381 +  }
   3.382 +
   3.383 +
   3.384 +} // namespace hugo
   3.385 +
   3.386 +#endif // HUGO_PATH_H

     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/src/work/klao/path_test.cc	Sun Mar 21 16:16:08 2004 +0000
     4.3 @@ -0,0 +1,118 @@
     4.4 +#include <string>
     4.5 +#include <iostream>
     4.6 +
     4.7 +#include <path.h>
     4.8 +#include <list_graph.h>
     4.9 +
    4.10 +using namespace std;
    4.11 +using namespace hugo;
    4.12 +
    4.13 +bool passed = true;
    4.14 +
    4.15 +void check(bool rc) {
    4.16 +  passed = passed && rc;
    4.17 +  if(!rc) {
    4.18 +    cout << "Test failed!" << endl;
    4.19 +  }
    4.20 +}
    4.21 +
    4.22 +int main() {
    4.23 +
    4.24 +  typedef ListGraph::Node Node;
    4.25 +  typedef ListGraph::Edge Edge;
    4.26 +
    4.27 +  ListGraph G;
    4.28 +
    4.29 +  Node s=G.addNode();
    4.30 +  Node v1=G.addNode();
    4.31 +  Node v2=G.addNode();
    4.32 +  Node v3=G.addNode();
    4.33 +  Node v4=G.addNode();
    4.34 +  Node t=G.addNode();
    4.35 +  
    4.36 +  Edge e1 = G.addEdge(s, v1);
    4.37 +  Edge e2 = G.addEdge(s, v2);
    4.38 +  Edge e3 = G.addEdge(v1, v2);
    4.39 +  Edge e4 = G.addEdge(v2, v1);
    4.40 +  Edge e5 = G.addEdge(v1, v3);
    4.41 +  Edge e6 = G.addEdge(v3, v2);
    4.42 +  Edge e7 = G.addEdge(v2, v4);
    4.43 +  Edge e8 = G.addEdge(v4, v3);
    4.44 +  Edge e9 = G.addEdge(v3, t);
    4.45 +  Edge e10 = G.addEdge(v4, t);
    4.46 +
    4.47 +  bool rc;
    4.48 +
    4.49 +  cout << "Ures path letrehozasa" << endl;
    4.50 +  typedef Path<ListGraph> LPath;
    4.51 +  LPath P(G);
    4.52 +
    4.53 +  cout << "P.length() == " << P.length() << endl;
    4.54 +  check(P.length() == 0);
    4.55 +
    4.56 +  cout << "P.from() valid? " << G.valid(P.from()) << endl;
    4.57 +  check(! G.valid(P.from()));
    4.58 +
    4.59 +  cout << "Hozzaadunk ket elet..." << endl;
    4.60 +  check(P.pushBack(e1));
    4.61 +  check(P.pushBack(e3));
    4.62 +  cout << "P.length() == " << P.length() << endl;
    4.63 +  check(P.length() == 2);
    4.64 +
    4.65 +  cout << "P.from() valid? " << G.valid(P.from()) << endl;
    4.66 +  check(G.valid(P.from()));
    4.67 +  
    4.68 +  cout << "P.from()==s ? " << (P.from()==s) << endl;
    4.69 +  check(P.from() == s);
    4.70 +
    4.71 +  cout << "Hozzaadunk egy nem illeszkedo elt." << endl;
    4.72 +  rc = P.pushBack(e8);
    4.73 +  cout << "Sukerult: " << rc << endl;
    4.74 +  check(!rc);
    4.75 +
    4.76 +  cout << "Meg 3 el hozzaadasa, nem mind sorrendben..." << endl;
    4.77 +  check(P.pushBack(e6));
    4.78 +  check(P.pushBack(e8));
    4.79 +  check(P.pushBack(e10));
    4.80 +
    4.81 +  cout << "P.length() == " << P.length() << endl;
    4.82 +  check(P.length() == 5);
    4.83 +
    4.84 +  cout << "P.from()==s ? " << (P.from()==s) << endl;
    4.85 +  check(P.from() == s);
    4.86 +  cout << "P.to()==t ? " << (P.to()==t) << endl;
    4.87 +  check(P.to() == t);
    4.88 +
    4.89 +  cout << "Vegpont bellitasa: " << endl;
    4.90 +  rc = P.setTo(v2);
    4.91 +  cout << "Hibasra: " << rc << endl;
    4.92 +  check(!rc);
    4.93 +  rc = P.setTo(t);
    4.94 +  cout << "Helyesre: " << rc << endl;
    4.95 +  check(rc);
    4.96 +
    4.97 +  cout << "Elek iranyitasanak ellenorzese." << endl;
    4.98 +  cout << "El: " << e1 << ", G.tail(el): " << G.head(e1) << endl;
    4.99 +  check(G.tail(e1)==s);
   4.100 +
   4.101 +  cout << "Vegigiteralunk az eleken." << endl;
   4.102 +  typedef LPath::NodeIt NodeIt;
   4.103 +  typedef LPath::EdgeIt EdgeIt;
   4.104 +  EdgeIt e = P.first<EdgeIt>();
   4.105 +  int i=1;
   4.106 +  for(; P.valid(e); P.next(e), ++i) {
   4.107 +    cout << i << ". el: " << P.graphEdge(e)
   4.108 +	 << ", elore el? " << P.isForward(e) << endl;
   4.109 +    if(i>=3 && i<5) 
   4.110 +      check(!P.isForward(e));
   4.111 +    else
   4.112 +      check(P.isForward(e));
   4.113 +  }
   4.114 +
   4.115 +
   4.116 +
   4.117 +  cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
   4.118 +       << endl;
   4.119 +
   4.120 +  return passed ? 0 : 1;
   4.121 +}