如何在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.

任何人都可以帮助我如何重新构造该查询以使其仅返回一条路径，即开始-决定-execute2-结束"吗?

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. 开始-决定-execute1
3. 开始-决定-execute2
4. 开始-决定-执行1-错误
5. 开始-决定-执行2-结束

请注意，如何同时返回具有一跳(1)和两跳(2、3)的路径.它们在1到10跳之内.您可能希望遍历只会发出叶节点(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"]
• 不要使用PRUNE使遍历器越过"execute1"(自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)

结果:[ "start - decide - execute2 - end" ]

文档:在图形遍历中进行修剪

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