arangodb · jsteemann · Sep 3, 2018 · Aug 30, 2018 · Aug 30, 2018 · Aug 30, 2018
diff --git a/CHANGELOG b/CHANGELOG
@@ -1,6 +1,10 @@
 v3.3.15 (XXXX-XX-XX)
 --------------------
 
+* fixed issue #5941 if using breadth-first search in traversals uniqueness checks
+  on path (vertices and edges) have not been applied. In SmartGraphs the checks
+  have been executed properly.
+
 * added more detailed progress output to arangorestore, showing the percentage of
   how much data is restored for bigger collections plus a set of overview statistics
   after each processed collection

diff --git a/arangod/Graph/BreadthFirstEnumerator.cpp b/arangod/Graph/BreadthFirstEnumerator.cpp
@@ -141,8 +141,22 @@ bool BreadthFirstEnumerator::next() {
             return;
           }
         }
+        if (_opts->uniqueEdges == TraverserOptions::UniquenessLevel::PATH) {
+          if (pathContainsEdge(nextIdx, eid)) {
+            // This edge is on the path.
+            return;
+          }
+        }
 
         if (_traverser->getSingleVertex(e, nextVertex, _currentDepth + 1, vId)) {
+
+          if (_opts->uniqueVertices == TraverserOptions::UniquenessLevel::PATH) {
+            if (pathContainsVertex(nextIdx, vId)) {
+              // This vertex is on the path.
+              return;
+            }
+          }
+
           _schreier.emplace_back(
               std::make_unique<PathStep>(nextIdx, std::move(eid), vId));
           if (_currentDepth < _opts->maxDepth - 1) {
@@ -221,3 +235,37 @@ arangodb::aql::AqlValue BreadthFirstEnumerator::pathToAqlValue(
   result.close();
   return arangodb::aql::AqlValue(result.slice());
 }
+
+bool BreadthFirstEnumerator::pathContainsVertex(size_t index, StringRef vertex) const {
+  while (true) {
+    TRI_ASSERT(index < _schreier.size());
+    auto const& step = _schreier[index];
+    // Massive logic error, only valid pointers should be inserted into _schreier
+    TRI_ASSERT(step != nullptr);
+    if (step->vertex == vertex) {
+      // We have the
8000
 given vertex on this path
+      return true;
+    }
+    if (index == 0) {
+      // We have checked the complete path
+      return false;
+    }
+    index = step->sourceIdx;
+  }
+  return false;
+}
+
+bool BreadthFirstEnumerator::pathContainsEdge(size_t index, graph::EdgeDocumentToken const& edge) const {
+  while (index != 0) {
+    TRI_ASSERT(index < _schreier.size());
+    auto const& step = _schreier[index];
+    // Massive logic error, only valid pointers should be inserted into _schreier
+    TRI_ASSERT(step != nullptr);
+    if (step->edge.equals(edge)) {
+      // We have the given vertex on this path
+      return true;
+    }
+    index = step->sourceIdx;
+  } 
+  return false;
+}
diff --git a/arangod/Graph/BreadthFirstEnumerator.h b/arangod/Graph/BreadthFirstEnumerator.h
@@ -152,12 +152,27 @@ class BreadthFirstEnumerator final
     return depth;
   }
 
-  //////////////////////////////////////////////////////////////////////////////
-  /// @brief Build the enumerated path for the given index in the schreier
-  ///        vector.
-  //////////////////////////////////////////////////////////////////////////////
-
-  void computeEnumeratedPath(size_t index);
+  /**
+   * @brief Helper function to validate if the path contains the given
+   *        vertex.
+   *
+   * @param index The index of the path to search for
+   * @param vertex The vertex that should be checked against.
+   *
+   * @return true if the vertex is already in the path 
+   */
+  bool pathContainsVertex(size_t index, StringRef vertex) const;
+
+  /**
+   * @brief Helper function to validate if the path contains the given
+   *        edge.
+   *
+   * @param index The index of the path to search for
+   * @param edge The edge that should be checked against.
+   *
+   * @return true if the edge is already in the path 
+   */
+  bool pathContainsEdge(size_t index, graph::EdgeDocumentToken const& edge) const;
 };
 }
 }

diff --git a/arangod/Graph/EdgeDocumentToken.h b/arangod/Graph/EdgeDocumentToken.h
@@ -26,6 +26,7 @@
 
 #include "Basics/Common.h"
 #include "Basics/StringRef.h"
+#include "Cluster/ServerState.h"
 #include "VocBase/LocalDocumentId.h"
 #include "VocBase/voc-types.h"
 
@@ -118,6 +119,13 @@ struct EdgeDocumentToken {
     return _data.document.cid == other.cid() &&
            _data.document.localDocumentId == other.localDocumentId();
   }
+
+  bool equals(EdgeDocumentToken const& other) const {
+    if (ServerState::instance()->isCoordinator()) {
+      return equalsCoordinator(other);
+    }
+    return equalsLocal(other);
+  }
 
 private:
 

diff --git a/js/server/tests/aql/aql-graph.js b/js/server/tests/aql/aql-graph.js
@@ -912,7 +912,59 @@ function ah
8000
uacatlQueryBreadthFirstTestSuite () {
       var actual = getQueryResults(query);
       assertEqual(actual.length, 6);
       assertEqual(actual, [ "BC","BD","CA","CA","EC","EF" ]);
-    }
+    },
+
+    testPathUniqueVertices : function () {
+      // Only depth 2 can yield results
+      // Depth 3 will return to the startVertex (A)
+      // and thereby is non-unique and will be excluded
+      const query = `WITH ${vn}
+      FOR v, e, p IN 2..4 OUTBOUND "${center}" ${en}
+        OPTIONS {bfs: true, uniqueVertices: "path"}
+        LET keys = CONCAT(p.vertices[*]._key)
+        SORT keys RETURN keys`;
+
+      const actual = getQueryResults(query);
+
+      const expected = [
+        "AEC",
+        "AEF",
+        "ABC",
+        "ABD"
+      ].sort();
+      assertEqual(actual.length, expected.length);
+      assertEqual(actual, expected);
+    },
+
+    testPathUniqueEdges : function () {
+      // Only depth 4 and 5 can yield results
+      // Depth 6 will have to reuse an edge (A->E or A->B)
+      // and thereby is non-unique and will be excluded
+      // uniqueEdges: path is the default
+      const query = `WITH ${vn}
+      FOR v, e, p IN 4..7 OUTBOUND "${center}" ${en}
+        OPTIONS {bfs: true}
+        LET keys = CONCAT(p.vertices[*]._key)
+        SORT keys RETURN keys`;
+
+      const actual = getQueryResults(query);
+
+      const expected = [
+        "AECAB",
+        "AECAD",
+        "AECAF",
+        "AECABC",
+        "AECABD",
+        "ABCAE",
+        "ABCAD",
+        "ABCAF",
+        "ABCAEC",
+        "ABCAEF"
+      ].sort();
+      assertEqual(actual.length, expected.length);
+      assertEqual(actual, expected);
+    },
+
   };
 }