ArangoDB 唯一顶点:路径还是全局?

sczxawaw  于 2022-12-09  发布在  Go
关注(0)|答案(1)|浏览(220)

UniqueVertices之间的区别是什么:路径和唯一顶点:全球?
根据ARANGO文件:

  1. path”-确保返回的路径中没有重复的顶点
    1.“global”-保证每个顶点在遍历过程中最多只被访问一次,无论从起始顶点到这个顶点有多少条路径。如果你以最小深度〉1开始,那么在最小深度之前找到的顶点可能根本不会被返回(它仍然可能是路径的一部分)。注意:使用此配置,结果不再具有确定性。如果从startVertex到vertex有多条路径,则选择其中一条。需要设置bfs:true,因为使用深度优先搜索时,结果将不可预测。
    UniqueVertices global的作用是什么?在遍历过程中,顶点最多被访问一次,这意味着什么?
8yparm6h

8yparm6h1#

考虑这个有5个顶点的图,它包含一个圈B -> D -> E -> B

没有唯一性限制的出站遍历将进入该循环,并在单个路径上多次访问某些顶点和边,直到达到最大遍历深度:
第一个
默认情况下,uniqueVertices"none"uniqueEdges"path"。这些选项可避免同一条路径两次遍历同一条边。这可防止遍历第二次进入循环(从B到D的边),但后两条路径仍两次包含B:
第一次
通过将顶点和边的唯一性限制为"path",每个路径将不会访问任何顶点或边两次。因为这是第一次在路径上遇到这条边(uniqueEdges"none"还是"path"对于这个特定的图来说并不重要),但是顶点B在开始时就已经被访问过了(A --> B --> D),因此遍历在此停止并且第二次不包括B:
第一个
需要一个不同的示例图来显示uniqueVertices: "global"的效果,该示例图具有菱形中的4个顶点:

在F处开始的出站遍历经由G和H通向同一顶点I。没有顶点或边可能被访问两次,但是每个发现的路径可以包括I:
第一个
如果我们现在将顶点的唯一性改变为"global",那么只有一条路径可以以I结束。选择哪条路径(经由G或H)是未定义的:

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"
]

请注意,uniqueVertices: "global"需要bfs: true(广度优先搜索)。虽然它不能使遍历具有确定性,但它确实使遍历更具可预测性。使用深度优先搜索,它会沿着一条路径一直走到尽头(或直到达到最大深度)。然后,如果某些路径包含已经访问过的顶点,则在这些路径上的遍历将提前停止,但是发现路径的顺序是未定义的,并且这可能导致对于同一查询返回不同的顶点集合。另一方面,第一次搜索确保返回相同的顶点集,即使在运行之间跟随的边可能变化。

相关问题