如何在 ArangoDB 中的图遍历期间消除通过特定文档或顶点的所有路径 [英] How to eliminate all paths that pass through particular document or vertex while during Graph Traversal in ArangoDB

问题描述

我正在尝试在这里进行图形遍历

I am trying to do a graph traversal here

我在 ArangoDB 中创建了两个集合，一个文档集合 "Node" 和一个边集合 "Path".我的所有节点都有一个 name 属性(标签)，并由边(线)连接，如上图所示.

I created two collections in ArangoDB, a document collection "Node" and an edge collection "Path". All my nodes have a name attribute (labels) and are connected by edges (lines) as shown in above illustration.

我尝试了以下查询来查找以 end 或 error 节点结尾的路径:

I tried below query to find paths that end with an end or error node:

FOR v, e, p IN 1..10 OUTBOUND 'Node/start_0' Path     
OPTIONS { bfs: true}     
FILTER (v.name == "end" OR v.name == "error")     
RETURN CONCAT_SEPARATOR(' - ', p.vertices[*].name)

上述查询按预期工作并返回两条路径:

The above query works as expected and returns me two paths:

["start - decide - execute1 - error"
 "start - decide - execute2 - end"]

但我正在探索如何消除通过特定节点的所有相应路径.例如，我想消除所有通过 execute1 的路径.我试过这个查询:

But I am exploring how to eliminate all corresponding paths that pass through a particular node. For example, I want to eliminate all paths that pass through execute1. I tried this query:

 FOR v, e, p IN 1..10 OUTBOUND 'Node/start_0' Path     
 OPTIONS { bfs: true}     
 FILTER ((v.name == "end" OR v.name == "error") AND v.name != "execute1")     
 RETURN CONCAT_SEPARATOR(' - ', p.vertices[*].name)

但它不起作用 - 它仍然返回给我两条路径.

But it doesn't work - it still returns me the two paths.

任何人都可以帮助我如何重新构建此查询以使其仅返回一条路径，即开始 - 决定 - 执行 2 - 结束"?

Can any one help me on how to reframe this query to make it return only one path, i.e. "start - decide - execute2 - end"?

推荐答案

您的遍历具有 1..10 的可变深度，它将找到以下路径:

Your traversal has a variable depth of 1..10, which will find the followings paths:

1. 开始 - 决定
2. 开始 - 决定 - 执行 1
3. 开始 - 决定 - 执行 2
4. 开始 - 决定 - 执行 1 - 错误
5. 开始 - 决定 - 执行 2 - 结束

注意一跳 (1) 和两跳 (2, 3) 的路径是如何返回的.它们在一到十个跃点之间.您的期望可能是遍历只会发出叶节点 (4, 5).但是，它为您提供了所有五种路径.

Note how the paths with one hop (1) and two hops (2, 3) are returned as well. They are within one to ten hops. Your expectation might have been that only leaf nodes (4, 5) would be emitted by the traversal. It gives you all five paths however.

您的 name 属性 FILTER 条件针对 v 进行测试，它代表每个路径的最后一个顶点.

Your name attribute FILTER conditions are tested against v, which represents the last vertex of each of these paths.

• "decide" 不等于 "end" 或 "error"，所以路径 1 被过滤掉了.
• "execute1" 和 "execute2" 不等于 "end" 或 "error"，所以路径 2 和 3 也被过滤掉了.
• "error" 和 "end" 等于这些值中的任何一个，但它们也满足条件 !="execute1"- 您正在针对停止节点而不是此处路径上的所有节点进行测试，因此行为是正确的，但不是您想要的

• "decide" is not equal to "end" or "error", so path 1 is filtered out.
• "execute1" and "execute2" are not equal to "end" or "error", so paths 2 and 3 are filtered out as well.
• "error" and "end" are equal to either of these values, but they also fulfill the condition != "execute1" - you are testing against the stop nodes and not all the nodes on the path here, so the behavior is correct but not what you want

您的选择是:

• 过滤掉包含名称为"execute1"的顶点的所有路径:
  FILTER p.vertices[*].name NONE == "execute1" AND v.name IN ["end", "error"]
• 不要让遍历器通过 "execute1" 使用 PRUNE(自 v3.4.5 和 v3.5.0 起可用):
  PRUNE v.name == "execute1" ... FILTER v.name IN ["end", "error"]
• 不要让遍历器越过 "execute1", "end" 或 "error" (针对上述查询的优化):
  PRUNE v.name IN ["execute1", "end", "error"] ... FILTER v.name IN ["end", "error"]

• filter out all paths which contain a vertex with name "execute1":
  FILTER p.vertices[*].name NONE == "execute1" AND v.name IN ["end", "error"]
• don't let the traverser go past "execute1" using PRUNE (available since v3.4.5 and v3.5.0):
  PRUNE v.name == "execute1" … FILTER v.name IN ["end", "error"]
• don't let the traverser go past "execute1", "end" or "error" (optimization for above query):
  PRUNE v.name IN ["execute1", "end", "error"] … FILTER v.name IN ["end", "error"]

请注意，PRUNE 将包括条件为真的顶点，即发现路径 2，但随后被 FILTER 条件过滤掉.PRUNE 单独不会过滤出路径 2.然而，它会阻止从 "execute1" 继续遍历，这意味着不会发现路径 4.FILTER 从结果中删除路径 1、2 和 3，只留下路径 5.

Note that PRUNE will include the vertex for which the conditions are true, i.e. path 2 is discovered, but then filtered out by the FILTER conditions. PRUNE alone does not filter path 2 out. It will prevent the traversal to continue from "execute1" however, which means path 4 will not be discovered. FILTER removes the paths 1, 2 and 3 from the result, leaving only path 5.

还要注意PRUNE子句必须放在OPTIONS之前！

Also note that the PRUNE clause must be placed before OPTIONS!

FOR v, e, p IN 1..10 OUTBOUND 'Node/start_0' Path
PRUNE v.name IN ["execute1", "end", "error"]
OPTIONS { bfs: true }
FILTER v.name IN ["end", "error"]
RETURN CONCAT_SEPARATOR(' - ', p.vertices[*].name)

结果:[开始-决定-执行2-结束"]

文档:图遍历中的修剪

这篇关于如何在 ArangoDB 中的图遍历期间消除通过特定文档或顶点的所有路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！