Consider this graph with 5 vertices which contains a cycle B -> D -> E -> B
:
An outbound traversal without uniqueness restrictions will run into this loop and visit some of the vertices and edges multiple times on a single path, until the maximum traversal depth is reached:
FOR v,e,p IN 1..10 OUTBOUND "vert/A" edge
OPTIONS { uniqueVertices: "none", uniqueEdges: "none" }
RETURN CONCAT_SEPARATOR(" --> ", p.vertices[*]._key)
[
"A --> B",
"A --> B --> C",
"A --> B --> D",
"A --> B --> D --> E",
"A --> B --> D --> E --> B",
"A --> B --> D --> E --> B --> C",
"A --> B --> D --> E --> B --> D",
"A --> B --> D --> E --> B --> D --> E",
"A --> B --> D --> E --> B --> D --> E --> B",
"A --> B --> D --> E --> B --> D --> E --> B --> C",
"A --> B --> D --> E --> B --> D --> E --> B --> D",
"A --> B --> D --> E --> B --> D --> E --> B --> D --> E",
"A --> B --> D --> E --> B --> D --> E --> B --> D --> E --> B"
]
By default, uniqueVertices
is "none"
and uniqueEdges
is "path"
. These options avoid that the same edge is followed twice for one path. This prevents the traversal from entering the cycle a second time (the edge from B to D), but the latter two paths include B twice nonetheless:
FOR v,e,p IN 1..10 OUTBOUND "vert/A" edge
OPTIONS { uniqueVertices: "none", uniqueEdges: "path" }
RETURN CONCAT_SEPARATOR(" --> ", p.vertices[*]._key)
[
"A --> B",
"A --> B --> C",
"A --> B --> D",
"A --> B --> D --> E",
"A --> B --> D --> E --> B",
"A --> B --> D --> E --> B --> C"
]
By restricting the uniqueness to "path"
for both vertices and edges, no vertex or edge will be visited twice per path. The edge from E to B is followed, because it's the first time that this edge is encountered on the path (whether uniqueEdges
is "none"
or "path"
does not matter with this particular graph). But the vertex B was already visited in the beginning (A --> B --> D
), so the traversal stops there and does not include B a second time:
FOR v,e,p IN 1..10 OUTBOUND "vert/A" edge
OPTIONS { uniqueVertices: "path", uniqueEdges: "path" }
RETURN CONCAT_SEPARATOR(" --> ", p.vertices[*]._key)
[
"A --> B",
"A --> B --> C",
"A --> B --> D",
"A --> B --> D --> E"
]
A different example graph is required to show the effect of uniqueVertices: "global"
, with 4 vertices in a diamond shape:
An outbound traversal starting at F leads via G and H to the same vertex I. No vertex or edge can possibly be visited twice, but each discovered path may include I:
FOR v,e,p IN 1..10 OUTBOUND "vert/F" edge
OPTIONS { bfs: true, uniqueVertices: "path", uniqueEdges: "path" }
RETURN CONCAT_SEPARATOR(" --> ", p.vertices[*]._key)
[
"F --> G",
"F --> H",
"F --> G --> I",
"F --> H --> I"
]
If we now change the uniqueness for vertices to "global"
, only one path can end in I. Which route is taken (via G or H) is undefined:
FOR v,e,p IN 1..10 OUTBOUND "vert/F" edge
OPTIONS { bfs: true, uniqueVertices: "global", uniqueEdges: "path" }
RETURN CONCAT_SEPARATOR(" --> ", p.vertices[*]._key)
[
"F --> G",
"F --> H",
"F --> G --> I"
]
Note that uniqueVertices: "global"
requires bfs: true
(breadth-first search). While it doesn't make the traversal deterministic, it does make it more predictable. With a depth-first search, it would follow down a path until the end (or until the maximum depth is reached) before other edges at the same depth would be followed. The traversal would then be stopped early on some paths if they contained an already visited vertex, but the order in which paths are discovered is undefined and that could result in different sets of vertices being returned for the same query. A breadth-first search on the other hand ensures that the same set of vertices is returned, even though the edges followed may vary between runs.