1.1 --- a/src/work/klao/path.h Sun Mar 21 16:16:08 2004 +0000
1.2 +++ b/src/work/klao/path.h Sun Mar 21 17:09:16 2004 +0000
1.3 @@ -10,6 +10,7 @@
1.4 #define HUGO_PATH_H
1.5
1.6 #include <deque>
1.7 +#include <algorithm>
1.8
1.9 #include <invalid.h>
1.10
1.11 @@ -39,10 +40,13 @@
1.12
1.13 Path(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {}
1.14
1.15 - /// Subpath defined by two nodes
1.16 - Path(Path const& P, NodeIt a, NodeIt b) { FIXME; }
1.17 - /// Subpath defined by tow edges. Contains edges in [a,b)
1.18 - Path(Path const& P, EdgeIt a, EdgeIt b) { FIXME; }
1.19 + /// Subpath defined by two nodes.
1.20 + /// Nodes may be in reversed order, then
1.21 + /// we contstruct the reversed path.
1.22 + Path(const Path &P, const NodeIt &a, const NodeIt &b);
1.23 + /// Subpath defined by two edges. Contains edges in [a,b)
1.24 + /// It is an error if the two edges are not in order!
1.25 + Path(const Path &P, const EdgeIt &a, const EdgeIt &b);
1.26
1.27 size_t length() const { return edges.size(); }
1.28 GraphNode from() const { return _first; }
1.29 @@ -71,6 +75,11 @@
1.30
1.31 bool isForward(const EdgeIt &e) const { return e.forw; }
1.32
1.33 + /// index of a node on the path. Returns length+2 for the invalid NodeIt
1.34 + int index(const NodeIt &n) const { return n.idx; }
1.35 + /// index of an edge on the path. Returns length+1 for the invalid EdgeIt
1.36 + int index(const EdgeIt &e) const { return e.it - edges.begin(); }
1.37 +
1.38 EdgeIt& next(EdgeIt &e) const;
1.39 NodeIt& next(NodeIt &n) const;
1.40 template <typename It>
1.41 @@ -122,7 +131,7 @@
1.42 friend class Path;
1.43 friend class EdgeIt;
1.44
1.45 - int idx;
1.46 + size_t idx;
1.47 bool tail; // Is this node the tail of the edge with same idx?
1.48
1.49 public:
1.50 @@ -301,6 +310,7 @@
1.51
1.52 n.idx = e.it-edges.begin();
1.53 n.tail = e.forw;
1.54 + return n;
1.55 }
1.56
1.57 template<typename Gr>
1.58 @@ -377,6 +387,43 @@
1.59 return n;
1.60 }
1.61
1.62 + // Reszut konstruktorok:
1.63 +
1.64 +
1.65 + template<typename Gr>
1.66 + Path<Gr>::Path(const Path &P, const EdgeIt &a, const EdgeIt &b) :
1.67 + G(P.G), edges(a.it, b.it) // WARNING: if b.it < a.it this will blow up!
1.68 + {
1.69 + if( G.valid(P._first) && a.it < P.edges.end() ) {
1.70 + _first = ( a.forw ? G.tail(*a.it) : G.head(*a.it) );
1.71 + if( b.it < P.edges.end() ) {
1.72 + _last = ( b.forw ? G.tail(*b.it) : G.head(*b.it) );
1.73 + }
1.74 + else {
1.75 + _last = P._last;
1.76 + }
1.77 + }
1.78 + }
1.79 +
1.80 +
1.81 + template<typename Gr>
1.82 + Path<Gr>::Path(const Path &P, const NodeIt &a, const NodeIt &b) :
1.83 + G(P.G)
1.84 + {
1.85 + if( !P.valid(a) || !P.valid(b) )
1.86 + return;
1.87 +
1.88 + int ai = a.idx, bi = b.idx;
1.89 + if( bi<ai )
1.90 + swap(ai,bi);
1.91 +
1.92 + edges.resize(bi-ai);
1.93 + copy(P.edges.begin()+ai, P.edges.begin()+bi, edges.begin());
1.94 +
1.95 + _first = P.graphNode(a);
1.96 + _last = P.graphNode(b);
1.97 + }
1.98 +
1.99
1.100 } // namespace hugo
1.101
2.1 --- a/src/work/klao/path_test.cc Sun Mar 21 16:16:08 2004 +0000
2.2 +++ b/src/work/klao/path_test.cc Sun Mar 21 17:09:16 2004 +0000
2.3 @@ -109,6 +109,70 @@
2.4 check(P.isForward(e));
2.5 }
2.6
2.7 + {
2.8 + cout << "Reszut letrehozasa: [2. el, 4. el)..." << endl;
2.9 + LPath P2(P, P.nth<EdgeIt>(1), P.nth<EdgeIt>(3));
2.10 +
2.11 + cout << "P2.length() == " << P2.length() << endl;
2.12 + check(P2.length() == 2);
2.13 +
2.14 + cout << "P2.from()==v1 ? " << (P2.from()==v1) << endl;
2.15 + check(P2.from() == v1);
2.16 + cout << "P2.to()==v3 ? " << (P2.to()==v3) << endl;
2.17 + check(P2.to() == v3);
2.18 + }
2.19 + {
2.20 + cout << "Reszut letrehozasa: [1. el, 6. el)..." << endl;
2.21 + LPath P2(P, P.nth<EdgeIt>(0), P.nth<EdgeIt>(5));
2.22 +
2.23 + cout << "P2.length() == " << P2.length() << endl;
2.24 + check(P2.length() == 5);
2.25 +
2.26 + cout << "P2.from()==s ? " << (P2.from()==s) << endl;
2.27 + check(P2.from() == s);
2.28 + cout << "P2.to()==t ? " << (P2.to()==t) << endl;
2.29 + check(P2.to() == t);
2.30 + }
2.31 +
2.32 + {
2.33 + cout << "Ket pont altal megadott reszut letrehozasa: [2. pont, 4. pont]..."
2.34 + << endl;
2.35 + LPath P2(P, P.nth<NodeIt>(1), P.nth<NodeIt>(3));
2.36 +
2.37 + cout << "P2.length() == " << P2.length() << endl;
2.38 + check(P2.length() == 2);
2.39 +
2.40 + cout << "P2.from()==v1 ? " << (P2.from()==v1) << endl;
2.41 + check(P2.from() == v1);
2.42 + cout << "P2.to()==v3 ? " << (P2.to()==v3) << endl;
2.43 + check(P2.to() == v3);
2.44 + }
2.45 + {
2.46 + cout << "Egy pontu reszut letrehozasa: [4. pont, 4. pont]..."
2.47 + << endl;
2.48 + LPath P2(P, P.nth<NodeIt>(3), P.nth<NodeIt>(3));
2.49 +
2.50 + cout << "P2.length() == " << P2.length() << endl;
2.51 + check(P2.length() == 0);
2.52 +
2.53 + cout << "P2.from()==v3 ? " << (P2.from()==v3) << endl;
2.54 + check(P2.from() == v3);
2.55 + cout << "P2.to()==v3 ? " << (P2.to()==v3) << endl;
2.56 + check(P2.to() == v3);
2.57 + }
2.58 + {
2.59 + cout << "Forditott ut letrehozasa: [6. pont, 1. pont]..."
2.60 + << endl;
2.61 + LPath P2(P, P.nth<NodeIt>(5), P.nth<NodeIt>(0));
2.62 +
2.63 + cout << "P2.length() == " << P2.length() << endl;
2.64 + check(P2.length() == 5);
2.65 +
2.66 + cout << "P2.from()==t ? " << (P2.from()==t) << endl;
2.67 + check(P2.from() == t);
2.68 + cout << "P2.to()==s ? " << (P2.to()==s) << endl;
2.69 + check(P2.to() == s);
2.70 + }
2.71
2.72
2.73 cout << (passed ? "All tests passed." : "Some of the tests failed!!!")