Changeset 226:616bc397c83a in lemon-0.x for src/work/klao

Timestamp:

03/21/04 18:09:16 (20 years ago)

Author:

Mihaly Barasz

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@323

Message:

Reszutas konstruktorok

Location:

src/work/klao

Files:

• path.h (modified) (6 diffs)
• path_test.cc (modified) (1 diff)

src/work/klao/path.h

@@ -11 +11 @@
 
 #include <deque>
+#include <algorithm>
 
 #include <invalid.h>
@@ -40 +41 @@
     Path(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {}
 
-    /// Subpath defined by two nodes
-    Path(Path const& P, NodeIt a, NodeIt b) { FIXME; }
-    /// Subpath defined by tow edges. Contains edges in [a,b)
-    Path(Path const& P, EdgeIt a, EdgeIt b) { FIXME; }
+    /// Subpath defined by two nodes.
+    /// Nodes may be in reversed order, then
+    /// we contstruct the reversed path.
+    Path(const Path &P, const NodeIt &a, const NodeIt &b);
+    /// Subpath defined by two edges. Contains edges in [a,b)
+    /// It is an error if the two edges are not in order!
+    Path(const Path &P, const EdgeIt &a, const EdgeIt &b);
     
     size_t length() const { return edges.size(); }
@@ -71 +75 @@
 
     bool isForward(const EdgeIt &e) const { return e.forw; }
+
+    /// index of a node on the path. Returns length+2 for the invalid NodeIt
+    int index(const NodeIt &n) const { return n.idx; }
+    /// index of an edge on the path. Returns length+1 for the invalid EdgeIt
+    int index(const EdgeIt &e) const { return e.it - edges.begin(); }
 
     EdgeIt& next(EdgeIt &e) const;
@@ -123 +132 @@
       friend class EdgeIt;
 
-      int idx;
+      size_t idx;
       bool tail;  // Is this node the tail of the edge with same idx?
 
@@ -302 +311 @@
     n.idx = e.it-edges.begin();
     n.tail = e.forw;
+    return n;
   }
 
@@ -378 +388 @@
   }
 
+  // Reszut konstruktorok:
+
+
+  template<typename Gr>
+  Path<Gr>::Path(const Path &P, const EdgeIt &a, const EdgeIt &b) :
+    G(P.G), edges(a.it, b.it)    // WARNING: if b.it < a.it this will blow up! 
+  {
+    if( G.valid(P._first) && a.it < P.edges.end() ) {
+      _first = ( a.forw ? G.tail(*a.it) : G.head(*a.it) );
+      if( b.it < P.edges.end() ) {
+        _last = ( b.forw ? G.tail(*b.it) : G.head(*b.it) );
+      }
+      else {
+        _last = P._last;
+      }
+    }
+  }
+
+
+  template<typename Gr>
+  Path<Gr>::Path(const Path &P, const NodeIt &a, const NodeIt &b) :
+    G(P.G)
+  {
+    if( !P.valid(a) || !P.valid(b) )
+      return;
+
+    int ai = a.idx, bi = b.idx;
+    if( bi<ai )
+      swap(ai,bi);
+    
+    edges.resize(bi-ai);
+    copy(P.edges.begin()+ai, P.edges.begin()+bi, edges.begin());
+
+    _first = P.graphNode(a);
+    _last = P.graphNode(b);
+  }
+
 
 } // namespace hugo

src/work/klao/path_test.cc

@@ -110 +110 @@
   }
 
+  {
+    cout << "Reszut letrehozasa: [2. el, 4. el)..." << endl;
+    LPath P2(P, P.nth<EdgeIt>(1), P.nth<EdgeIt>(3));
+
+    cout << "P2.length() == " << P2.length() << endl;
+    check(P2.length() == 2);
+    
+    cout << "P2.from()==v1 ? " << (P2.from()==v1) << endl;
+    check(P2.from() == v1);
+    cout << "P2.to()==v3 ? " << (P2.to()==v3) << endl;
+    check(P2.to() == v3);
+  }
+  {
+    cout << "Reszut letrehozasa: [1. el, 6. el)..." << endl;
+    LPath P2(P, P.nth<EdgeIt>(0), P.nth<EdgeIt>(5));
+
+    cout << "P2.length() == " << P2.length() << endl;
+    check(P2.length() == 5);
+    
+    cout << "P2.from()==s ? " << (P2.from()==s) << endl;
+    check(P2.from() == s);
+    cout << "P2.to()==t ? " << (P2.to()==t) << endl;
+    check(P2.to() == t);
+  }
+
+  {
+    cout << "Ket pont altal megadott reszut letrehozasa: [2. pont, 4. pont]..."
+         << endl;
+    LPath P2(P, P.nth<NodeIt>(1), P.nth<NodeIt>(3));
+
+    cout << "P2.length() == " << P2.length() << endl;
+    check(P2.length() == 2);
+    
+    cout << "P2.from()==v1 ? " << (P2.from()==v1) << endl;
+    check(P2.from() == v1);
+    cout << "P2.to()==v3 ? " << (P2.to()==v3) << endl;
+    check(P2.to() == v3);
+  }
+  {
+    cout << "Egy pontu reszut letrehozasa: [4. pont, 4. pont]..."
+         << endl;
+    LPath P2(P, P.nth<NodeIt>(3), P.nth<NodeIt>(3));
+
+    cout << "P2.length() == " << P2.length() << endl;
+    check(P2.length() == 0);
+    
+    cout << "P2.from()==v3 ? " << (P2.from()==v3) << endl;
+    check(P2.from() == v3);
+    cout << "P2.to()==v3 ? " << (P2.to()==v3) << endl;
+    check(P2.to() == v3);
+  }
+  {
+    cout << "Forditott ut letrehozasa: [6. pont, 1. pont]..."
+         << endl;
+    LPath P2(P, P.nth<NodeIt>(5), P.nth<NodeIt>(0));
+
+    cout << "P2.length() == " << P2.length() << endl;
+    check(P2.length() == 5);
+    
+    cout << "P2.from()==t ? " << (P2.from()==t) << endl;
+    check(P2.from() == t);
+    cout << "P2.to()==s ? " << (P2.to()==s) << endl;
+    check(P2.to() == s);
+  }