8000 Bug fix 3.3/pathuniqueness in bfs (#6303) · arangodb/arangodb@99640a0 · GitHub
[go: up one dir, main page]
Skip to content

Commit 99640a0

Browse files
mchackijsteemann
mchacki
authored and
jsteemann
committed
Bug fix 3.3/pathuniqueness in bfs (#6303)
1 parent 6d888d4 commit 99640a0

File tree

5 files changed

+134
-7
lines changed

5 files changed

+134
-7
lines changed

‎CHANGELOG

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,10 @@
11
v3.3.15 (XXXX-XX-XX)
22
--------------------
33

4+
* fixed issue #5941 if using breadth-first search in traversals uniqueness checks
5+
on path (vertices and edges) have not been applied. In SmartGraphs the checks
6+
have been executed properly.
7+
48
* added more detailed progress output to arangorestore, showing the percentage of
59
how much data is restored for bigger collections plus a set of overview statistics
610
after each processed collection

‎arangod/Graph/BreadthFirstEnumerator.cpp

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -141,8 +141,22 @@ bool BreadthFirstEnumerator::next() {
141141
return;
142142
}
143143
}
144+
if (_opts->uniqueEdges == TraverserOptions::UniquenessLevel::PATH) {
145+
if (pathContainsEdge(nextIdx, eid)) {
146+
// This edge is on the path.
147+
return;
148+
}
149+
}
144150

145151
if (_traverser->getSingleVertex(e, nextVertex, _currentDepth + 1, vId)) {
152+
153+
if (_opts->uniqueVertices == TraverserOptions::UniquenessLevel::PATH) {
154+
if (pathContainsVertex(nextIdx, vId)) {
155+
// This vertex is on the path.
156+
return;
157+
}
158+
}
159+
146160
_schreier.emplace_back(
147161
std::make_unique<PathStep>(nextIdx, std::move(eid), vId));
148162
if (_currentDepth < _opts->maxDepth - 1) {
@@ -221,3 +235,37 @@ arangodb::aql::AqlValue BreadthFirstEnumerator::pathToAqlValue(
221235
result.close();
222236
return arangodb::aql::AqlValue(result.slice());
223237
}
238+
239+
bool BreadthFirstEnumerator::pathContainsVertex(size_t index, StringRef vertex) const {
240+
while (true) {
241+
TRI_ASSERT(index < _schreier.size());
242+
auto const& step = _schreier[index];
243+
// Massive logic error, only valid pointers should be inserted into _schreier
244+
TRI_ASSERT(step != nullptr);
245+
if (step->vertex == vertex) {
246+
// We have the given vertex on this path
247+
return true;
248+
}
249+
if (index == 0) {
250+
// We have checked the complete path
251+
return false;
252+
}
253+
index = step->sourceIdx;
254+
}
255+
return false;
256+
}
257+
258+
bool BreadthFirstEnumerator::pathContainsEdge(size_t index, graph::EdgeDocumentToken const& edge) const {
259+
while (index != 0) {
260+
TRI_ASSERT(index < _schreier.size());
261+
auto const& step = _schreier[index];
262+
// Massive logic error, only valid pointers should be inserted into _schreier
263+
TRI_ASSERT(step != nullptr);
264+
if (step->edge.equals(edge)) {
265+
// We have the given vertex on this path
266+
return true;
267+
}
268+
index = step->sourceIdx;
269+
}
270+
return false;
271+
}

‎arangod/Graph/BreadthFirstEnumerator.h

Lines changed: 21 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -152,12 +152,27 @@ class BreadthFirstEnumerator final
152152
return depth;
153153
}
154154

155-
//////////////////////////////////////////////////////////////////////////////
156-
/// @brief Build the enumerated path for the given index in the schreier
157-
/// vector.
158-
//////////////////////////////////////////////////////////////////////////////
159-
160-
void computeEnumeratedPath(size_t index);
155+
/**
156+
* @brief Helper function to validate if the path contains the given
157+
* vertex.
158+
*
159+
* @param index The index of the path to search for
160+
* @param vertex The vertex that should be checked against.
161+
*
162+
* @return true if the vertex is already in the path
163+
*/
164+
bool pathContainsVertex(size_t index, StringRef vertex) const;
165+
166+
/**
167+
* @brief Helper function to validate if the path contains the given
168+
* edge.
169+
*
170+
* @param index The index of the path to search for
171+
* @param edge The edge that should be checked against.
172+
*
173+
* @return true if the edge is already in the path
174+
*/
175+
bool pathContainsEdge(size_t index, graph::EdgeDocumentToken const& edge) const;
161176
};
162177
}
163178
}

‎arangod/Graph/EdgeDocumentToken.h

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,7 @@
2626

2727
#include "Basics/Common.h"
2828
#include "Basics/StringRef.h"
29+
#include "Cluster/ServerState.h"
2930
#include "VocBase/LocalDocumentId.h"
3031
#include "VocBase/voc-types.h"
3132

@@ -118,6 +119,13 @@ struct EdgeDocumentToken {
118119
return _data.document.cid == other.cid() &&
119120
_data.document.localDocumentId == other.localDocumentId();
120121
}
122+
123+
bool equals(EdgeDocumentToken const& other) const {
124+
if (ServerState::instance()->isCoordinator()) {
125+
return equalsCoordinator(other);
126+
}
127+
return equalsLocal(other);
128+
}
121129

122130
private:
123131

‎js/server/tests/aql/aql-graph.js

Lines changed: 53 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -912,7 +912,59 @@ function ahuacatlQueryBreadthFirstTestSuite () {
912912
var actual = getQueryResults(query);
913913
assertEqual(actual.length, 6);
914914
assertEqual(actual, [ "BC","BD","CA","CA","EC","EF" ]);
915-
}
915+
},
916+
917+
testPathUniqueVertices : function () {
918+
// Only depth 2 can yield results
919+
// Depth 3 will return to the startVertex (A)
920+
// and thereby is non-unique and will be excluded
921+
const query = `WITH ${vn}
922+
FOR v, e, p IN 2..4 OUTBOUND "${center}" ${en}
923+
OPTIONS {bfs: true, uniqueVertices: "path"}
924+
LET keys = CONCAT(p.vertices[*]._key)
925+
SORT keys RETURN keys`;
926+
927+
const actual = getQueryResults(query);
928+
929+
const expected = [
930+
"AEC",
931+
"AEF",
932+
"ABC",
933+
"ABD"
934+
].sort();
935+
assertEqual(actual.length, expected.length);
936+
assertEqual(actual, expected);
937+
},
938+
939+
testPathUniqueEdges : function () {
940+
// Only depth 4 and 5 can yield results
941+
// Depth 6 will have to reuse an edge (A->E or A->B)
942+
// and thereby is non-unique and will be excluded
943+
// uniqueEdges: path is the default
944+
const query = `WITH ${vn}
945+
FOR v, e, p IN 4..7 OUTBOUND "${center}" ${en}
946+
OPTIONS {bfs: true}
947+
LET keys = CONCAT(p.vertices[*]._key)
948+
SORT keys RETURN keys`;
949+
950+
const actual = getQueryResults(query);
951+
952+
const expected = [
953+
"AECAB",
954+
"AECAD",
955+
"AECAF",
956+
"AECABC",
957+
"AECABD",
958+
"ABCAE",
959+
"ABCAD",
960+
"ABCAF",
961+
"ABCAEC",
962+
"ABCAEF"
963+
].sort();
964+
assertEqual(actual.length, expected.length);
965+
assertEqual(actual, expected);
966+
},
967+
916968
};
917969
}
918970

0 commit comments

Comments
 (0)
0