apoc.path.spanningTree
过程

此过程不建议在多线程中运行，因此并行运行时（Parallel runtime）不支持该过程。有关更多信息，请参阅 Cypher 手册 → 并行运行时。

详细信息
语法	`apoc.path.spanningTree(startNode, config) :: (path)`
描述	返回从起始 `NODE`（节点）开始，沿着给定的 `RELATIONSHIP`（关系）类型扩展到最大深度的生成树 `PATH`（路径）值。
输入参数	名称	类型	描述
	`startNode`	`ANY`	算法开始的起始节点。`startNode` 可以是 `STRING` (elementId())、`INTEGER` (id())、`NODE` 或 `LIST<STRING \| INTEGER \| NODE> 类型。
	`config`	`MAP`	`{ minLevel = -1 :: INTEGER, maxLevel = -1 :: INTEGER, relationshipFilter :: STRING, labelFilter :: STRING, beginSequenceAtStart = true :: BOOLEAN, uniqueness = "RELATIONSHIP_PATH" :: STRING, bfs = true :: BOOLEAN, filterStartNode = false :: BOOLEAN, limit = -1 :: INTEGER, optional = false :: BOOLEAN, endNodes :: LIST<NODES>, terminatorNodes:: LIST<NODES>, allowlistNodes:: LIST<NODES>, denylistNodes:: LIST<NODES> }`
返回参数	名称	类型	描述
返回参数	`path`	`PATH`	生成树路径。

配置参数

该过程支持以下配置参数

配置参数
名称	类型	默认	描述
`minLevel`	`INTEGER（整数）`	-1	遍历的最小跳数。如果指定，必须为 0 或 1
`maxLevel`	`INTEGER（整数）`	-1	遍历的最大跳数
`relationshipFilter`	`STRING`	null	要遍历的关系类型和方向。参见关系过滤器 (Relationship Filters)。
`labelFilter`	`STRING`	null	要遍历的节点标签。参见标签过滤器 (Label Filters)。
`beginSequenceAtStart`	`布尔值 (BOOLEAN)`	true	从距离起始节点一步之遥的位置开始匹配节点标签和/或关系类型序列（在 `relationshipFilter`、`labelFilter` 或 `sequences` 中定义）。
`bfs`	`布尔值 (BOOLEAN)`	true	遍历时使用广度优先搜索。如果设置为 `false`，则使用深度优先搜索
`filterStartNode`	`布尔值 (BOOLEAN)`	false	`labelFilter` 和 `sequence` 是否应用于展开的起始节点。
`limit`	`INTEGER（整数）`	-1	限制返回的路径数量。当使用 `bfs:true` 时，效果是返回到达终止或结束节点过滤器中包含标签的最近 `n` 个节点的路径，其中 `n` 为给定的限制值。如果设置为 `true`，则当展开因没有结果而导致行被消除时，会产生一个 `null` 值。
`endNodes`	`LIST<NODE>`	null	只有这些节点可以结束返回的路径，如果可能，扩展将继续经过这些节点。
`terminatorNodes`	`LIST<NODE>`	null	只有这些节点可以结束返回的路径，并且扩展不会在这些节点之后继续。
`allowlistNodes`	`LIST<NODE>`	null	只有这些节点允许在扩展中出现（如果存在，endNodes 和 terminatorNodes 也将被允许）。
`denylistNodes`	`LIST<NODE>`	null	返回的所有路径都不会包含这些节点。
`whitelistNodes` (已弃用)	`LIST<NODE>`	null	请参阅 allowlistNodes。
`blacklistNodes` (已弃用)	`LIST<NODE>`	null	请参阅 denylistNodes。

它还有以下固定参数

配置参数
名称	类型	默认	描述
`uniqueness`	`STRING`	NODE_GLOBAL	在遍历中展开关系时使用的策略。`NODE_GLOBAL` 表示一个节点不能被遍历超过一次。这与遗留的遍历框架行为一致。

关系过滤器

关系过滤器的语法描述如下

语法: [<]RELATIONSHIP_TYPE1[>]|[<]RELATIONSHIP_TYPE2[>]|…

input type 方向

input	type	方向
`LIKES>`	`LIKES`	OUTGOING (出站)
`<FOLLOWS`	`FOLLOWS`	INCOMING (入站)
`KNOWS`	`KNOWS`	BOTH (双向)
`>`	`任意类型`	OUTGOING (出站)
`<`	`任意类型`	INCOMING (入站)

LIKES>

LIKES

OUTGOING (出站)

<FOLLOWS

FOLLOWS

INCOMING (入站)

KNOWS

BOTH (双向)

>

任意类型

OUTGOING (出站)

<

任意类型

INCOMING (入站)

标签过滤器

标签过滤器的语法描述如下

语法: [+-/>]LABEL1|LABEL2|*|…

符号过滤器类型输入示例描述

符号	过滤器类型	输入示例	描述
`-`	黑名单 (Denylist)	`-Foe`	路径中的任何节点都不会拥有存在于黑名单中的标签。
`+`	白名单 (Allowlist)	`+Friend`	路径中的所有节点必须拥有白名单中的标签（如果使用这些过滤器，则豁免终止和结束节点）。如果没有白名单运算符，则允许所有标签。
`/`	终止 (Termination)	`/Friend`	只返回到达具有给定标签节点的路径，并在该点停止进一步扩展。终止节点不需要遵守白名单。终止过滤优先于结束节点过滤。
`>`	结束节点 (End node)	`>Friend`	只返回到达具有给定标签节点的路径，但继续扩展以匹配其后的结束节点。结束节点不需要遵守白名单即可被返回，但只有在节点具有白名单中的标签时，才允许在其后进行扩展。
`:`	复合标签	`Foe:Friend`	这返回标签的合取，例如 /Foo:Bar 意味着终止节点必须同时匹配 `Foo` 和 `Bar`。要包含没有特殊含义的 `:` 标签，请使用 `\` 转义它们，例如 Foo\:Bar 是标签 `Foo:Bar`。

-

黑名单 (Denylist)

-Foe

路径中的任何节点都不会拥有存在于黑名单中的标签。

+

白名单 (Allowlist)

+Friend

路径中的所有节点必须拥有白名单中的标签（如果使用这些过滤器，则豁免终止和结束节点）。如果没有白名单运算符，则允许所有标签。

/

终止 (Termination)

/Friend

只返回到达具有给定标签节点的路径，并在该点停止进一步扩展。终止节点不需要遵守白名单。终止过滤优先于结束节点过滤。

>

结束节点 (End node)

>Friend

只返回到达具有给定标签节点的路径，但继续扩展以匹配其后的结束节点。结束节点不需要遵守白名单即可被返回，但只有在节点具有白名单中的标签时，才允许在其后进行扩展。

:

复合标签

Foe:Friend

这返回标签的合取，例如 /Foo:Bar 意味着终止节点必须同时匹配 Foo 和 Bar。要包含没有特殊含义的 : 标签，请使用 \ 转义它们，例如 Foo\:Bar 是标签 Foo:Bar。

标签过滤运算符的优先级和行为

允许多个标签过滤器同时使用。请看以下示例

labelFilter:'+Person|Movie|-SciFi|>Western|/Romance'

如果我们分析这个标签过滤器，可以看到

:Person 和 :Movie 标签在白名单中
:SciFi 在黑名单中
:Western 是结束节点标签
:Romance 是终止标签。

运算符评估的优先级不依赖于它们在 labelFilter 中的位置，而是固定的

黑名单过滤器 -，终止过滤器 /，结束节点过滤器 >，白名单过滤器 +。

这意味着

没有列入黑名单的标签 - 会出现在返回路径的节点中，即使相同的标签（或具有黑名单标签节点的其他标签）包含在其他过滤器列表中。
如果使用了终止过滤器 / 或结束节点过滤器 >，则仅返回到达具有这些标签的节点的路径。这些结束节点豁免于白名单过滤器。
如果一个节点是终止节点 /，则不会在该节点之后进行进一步扩展。
白名单仅适用于除终止节点或结束节点过滤器定义的节点之外的路径节点。如果没有结束节点或终止节点运算符，则白名单适用于路径的所有节点。
如果 labelFilter 中不存在白名单运算符，则视为所有标签均在白名单中。

输出参数

名称	类型
path	PATH

名称

类型

path

PATH

使用示例

本节中的示例基于以下示例图

MERGE (mark:Person:DevRel {name: "Mark"})
MERGE (lju:Person:DevRel {name: "Lju"})
MERGE (praveena:Person:Engineering {name: "Praveena"})
MERGE (zhen:Person:Engineering {name: "Zhen"})
MERGE (martin:Person:Engineering {name: "Martin"})
MERGE (joe:Person:Field {name: "Joe"})
MERGE (stefan:Person:Field {name: "Stefan"})
MERGE (alicia:Person:Product {name: "Alicia"})
MERGE (jake:Person:Product {name: "Jake"})
MERGE (john:Person:Product {name: "John"})
MERGE (jonny:Person:Sales {name: "Jonny"})
MERGE (anthony:Person:Sales {name: "Anthony"})
MERGE (rik:Person:Sales {name: "Rik"})

MERGE (zhen)-[:KNOWS]-(stefan)
MERGE (zhen)-[:KNOWS]-(lju)
MERGE (zhen)-[:KNOWS]-(praveena)
MERGE (zhen)-[:KNOWS]-(martin)
MERGE (mark)-[:KNOWS]-(jake)
MERGE (alicia)-[:KNOWS]-(jake)
MERGE (jonny)-[:KNOWS]-(anthony)
MERGE (john)-[:KNOWS]-(rik)

MERGE (alicia)-[:FOLLOWS]->(joe)
MERGE (joe)-[:FOLLOWS]->(mark)
MERGE (joe)-[:FOLLOWS]->(praveena)
MERGE (joe)-[:FOLLOWS]->(zhen)
MERGE (mark)-[:FOLLOWS]->(stefan)
MERGE (stefan)-[:FOLLOWS]->(joe)
MERGE (praveena)-[:FOLLOWS]->(joe)
MERGE (lju)-[:FOLLOWS]->(jake)
MERGE (alicia)-[:FOLLOWS]->(jonny)
MERGE (zhen)-[:FOLLOWS]->(john)
MERGE (anthony)-[:FOLLOWS]->(joe)

下面的 Neo4j 浏览器可视化显示了示例图

图 1. 示例图

KNOWS 关系类型被认为是双向的，如果 Zhen 认识 Stefan，我们可以暗示 Stefan 也认识 Zhen。当使用 KNOWS 关系时，我们将忽略方向。

FOLLOWS 关系是有方向的，因此我们在使用它时会指定方向。

关系类型和节点标签过滤器

让我们从 Praveena 节点开始展开路径。我们只想考虑 KNOWS 关系类型，因此我们将把它指定为 relationshipFilter 参数。

以下查询返回从 Praveena 开始，并遍历 KNOWS 关系类型 1 到 2 跳的生成树。

MATCH (p:Person {name: "Praveena"})
CALL apoc.path.spanningTree(p, {
	relationshipFilter: "KNOWS",
    minLevel: 1,
    maxLevel: 2
})
YIELD path
RETURN path;

我们可以在从 Praveena 开始的生成树中看到该生成树的 Neo4j 浏览器可视化效果。

图 2. 从 Praveena 开始的生成树

该生成树除了 Praveena 外还包含 4 个节点。Praveena 仅与 Zhen 有直接的 KNOWS 关系，但 Zhen 与其他 3 个人有 KNOWS 关系，这意味着他们也被包含在生成树中。

我们还可以提供节点标签过滤器来限制返回的节点。如果我们只想返回每个节点都带有 Engineering 标签的路径，我们将给 labelFilter 参数提供值 +Engineering。

以下查询返回从 Praveena 开始，遍历 KNOWS 关系类型 1 到 2 跳，且仅包含 Engineering（工程）标签节点的生成树。

MATCH (p:Person {name: "Praveena"})
CALL apoc.path.spanningTree(p, {
	relationshipFilter: "KNOWS",
	labelFilter: "+Engineering",
    minLevel: 1,
    maxLevel: 2
})
YIELD path
RETURN path;

我们可以在从 Praveena 到工程节点的生成树中看到该生成树的 Neo4j 浏览器可视化效果。

图 3. 从 Praveena 到工程节点的生成树

我们丢失了生成树中的 Lju 和 Stefan，因为这两个节点都没有 Engineering 标签。

我们可以指定多种关系类型。以下查询从 Alicia 节点开始，然后展开 FOLLOWS 和 KNOWS 关系

以下查询返回从 Alicia 开始，遍历 FOLLOWS 或 KNOWS 关系类型 1 到 3 跳的生成树。

MATCH (p:Person {name: "Alicia"})
CALL apoc.path.spanningTree(p, {
    relationshipFilter: "FOLLOWS>|KNOWS",
    minLevel: 1,
    maxLevel: 3
})
YIELD path
RETURN path;

我们可以在从 Alicia 开始的生成树中看到该生成树的 Neo4j 浏览器可视化效果。

图 4. 从 Alicia 开始的生成树

该查询返回了图中 12 人中 11 人的路径，这表明 Alicia 的人脉非常广泛。

我们还可以使用标签过滤器指定遍历终止标准。如果我们想在遍历遇到包含 Engineering 标签的节点时立即终止遍历，我们可以使用 /Engineering 节点过滤器。

以下查询返回从 Alicia 开始，遍历 FOLLOWS 或 KNOWS 关系类型 1 到 3 跳，并在到达带有 Engineering 标签的节点时立即终止的生成树。

MATCH (p:Person {name: "Alicia"})
CALL apoc.path.spanningTree(p, {
    relationshipFilter: "FOLLOWS>|KNOWS",
    labelFilter: "/Engineering",
    minLevel: 1,
    maxLevel: 3
})
YIELD path
RETURN path;

我们可以在从 Alicia 开始并在 Engineering 节点终止的生成树中看到该生成树的 Neo4j 浏览器可视化效果。

图 5. 从 Alicia 开始并在 Engineering 节点终止的生成树

我们的生成树现在除了 Alicia 外只剩下 3 个节点。但此查询没有捕获从 Alicia 开始包含 Engineering 标签节点的完整生成树。我们可以使用 >Engineering 节点过滤器来定义遍历，以便

仅返回在带有 Engineering 标签的节点处结束的路径
并在那之后继续扩展到结束节点，寻找更多以 Engineering 标签结尾的路径

以下查询返回从 Alicia 开始，遍历 FOLLOWS 或 KNOWS 关系类型 1 到 3 跳的生成树，其中路径以带有 Engineering 标签的节点结束。

MATCH (p:Person {name: "Alicia"})
CALL apoc.path.spanningTree(p, {
    relationshipFilter: "FOLLOWS>|KNOWS",
    labelFilter: ">Engineering",
    minLevel: 1,
    maxLevel: 3
})
YIELD path
RETURN path;

我们可以在从 Alicia 到 Engineering 节点的生成树中看到该生成树的 Neo4j 浏览器可视化效果。

图 6. 从 Alicia 到 Engineering 节点的生成树

现在，生成树通过 Zhen 的关系也到达了 Martin。

终止节点和结束节点

除了为遍历指定终止和结束标签外，我们还可以指定终止和结束节点。

让我们基于之前的查询进行扩展，该查询找出了 Alicia KNOWS 或 FOLLOWS 的人。我们希望返回的生成树在到达 Mark、Joe、Zhen 或 Praveena 节点时立即停止。我们可以通过将这些节点传递给 terminatorNodes 参数来实现。

以下查询返回 Alicia FOLLOWS 或 KNOWS 的人 1 到 3 跳的生成树，并在到达 Mark、Joe、Zhen 或 Rik 节点时立即终止。

MATCH (p:Person {name: "Alicia"})
MATCH (terminator:Person)
WHERE terminator.name IN ["Mark", "Joe", "Zhen", "Rik"]
WITH p, collect(terminator) AS terminatorNodes
CALL apoc.path.spanningTree(p, {
    relationshipFilter: "FOLLOWS>|KNOWS",
    minLevel: 1,
    maxLevel: 3,
    terminatorNodes: terminatorNodes
})
YIELD path
RETURN path;

我们可以在从 Alicia 开始，在 Mark、Joe、Zhen 或 Rik 处终止的生成树中看到该生成树的 Neo4j 浏览器可视化效果。

图 7. 从 Alicia 开始，在 Mark、Joe、Zhen 或 Rik 处终止的生成树

Mark 和 Joe 被包含在生成树中，但无法到达 Rik 和 Zhen。这可能是因为没有不经过 Mark 和 Joe 而到达 Zhen 和 Rik 的路径，或者意味着根据其他遍历条件没有路径。

我们可以通过将这些节点传递给 endNodes 参数来查看 Mark、Joe、Zhen 或 Rik 是否可达。

以下查询返回 Alicia FOLLOWS 或 KNOWS 的人 1 到 3 跳的生成树，并在到达 Mark、Joe、Zhen 或 Rik 节点时结束。

MATCH (p:Person {name: "Alicia"})
MATCH (end:Person)
WHERE end.name IN ["Mark", "Joe", "Zhen", "Rik"]
WITH p, collect(end) AS endNodes
CALL apoc.path.spanningTree(p, {
    relationshipFilter: "FOLLOWS>|KNOWS",
    minLevel: 1,
    maxLevel: 3,
    endNodes: endNodes
})
YIELD path
RETURN path;

我们可以在从 Alicia 开始，在 Mark、Joe、Zhen 或 Rik 处结束的生成树中看到该生成树的 Neo4j 浏览器可视化效果。

图 8. 从 Alicia 开始，在 Mark、Joe、Zhen 或 Rik 处结束的生成树

我们的生成树现在包含了 Joe、Mark 和 Zhen，但 Rik 仍然无法到达。

允许列表节点和拒绝列表节点

还可以指定白名单和黑名单节点。

让我们基于之前找到 Alicia KNOWS 或 FOLLOWS 的人的查询进行构建。我们希望任何返回的路径仅包含 Mark、Joe、Zhen 和 Praveena 节点，我们可以通过将这些节点传递给 allowlistNodes 参数来实现这一点。

以下查询返回从 Alicia 开始，通过 FOLLOWS 或 KNOWS 关系类型在 1 到 3 跳内可到达的生成树，其中到达这些节点的路径必须仅包含 Mark、Jonny 或 Zhen。

MATCH (p:Person {name: "Alicia"})
MATCH (allowlist:Person)
WHERE allowlist.name IN ["Jonny", "Mark", "Zhen"]
WITH p, collect(allowlist) AS allowlistNodes
CALL apoc.path.spanningTree(p, {
    relationshipFilter: "FOLLOWS>|KNOWS",
    minLevel: 1,
    maxLevel: 3,
    allowlistNodes: allowlistNodes
})
YIELD path
RETURN path;

我们可以在从 Alicia 开始，路径包含 Mark、Jonny 或 Zhen 的生成树中看到该生成树的 Neo4j 浏览器可视化效果。

图 9. 从 Alicia 开始，路径包含 Mark、Jonny 或 Zhen 的生成树

只有 Jonny 可以到达。因此我们可以推断 Mark 和 Zhen 只能通过未包含在白名单中的其他节点到达。

黑名单用于从通往可到达节点的路径中排除节点。如果我们想返回在不经过 Joe 的情况下可以到达的节点，我们可以通过将 Joe 节点传递给 denylistNodes 参数来实现。

以下查询返回从 Alicia 开始，通过 FOLLOWS 或 KNOWS 关系类型在 1 到 3 跳内可到达的生成树，其中到达这些节点的路径不能经过 Joe。

MATCH (p:Person {name: "Alicia"})
MATCH (joe:Person {name: "Joe"})
CALL apoc.path.spanningTree(p, {
    relationshipFilter: "FOLLOWS>|KNOWS",
    minLevel: 1,
    maxLevel: 3,
    denylistNodes: [joe]
})
YIELD path
RETURN path;

我们可以在从 Alicia 开始，路径不能经过 Joe 的生成树中看到该生成树的 Neo4j 浏览器可视化效果。

apoc.path.spanningTree.alicia denylist joe

图 10. 从 Alicia 开始，路径不能经过 Joe 的生成树

关系类型序列

可以通过逗号分隔传递给 relationshipFilter 的值来指定关系类型的序列。

例如，如果我们想从 Joe 节点开始，遍历 FOLLOWS 关系（出站方向）和 KNOWS 关系（任一方向）的序列，我们可以指定关系过滤器 FOLLOWS>,KNOWS。

以下查询返回从 Joe 开始通过交替遵循 FOLLOWS 和 KNOWS 关系类型所能到达的节点

MATCH (p:Person {name: "Joe"})
CALL apoc.path.spanningTree(p, {
	relationshipFilter: "FOLLOWS>,KNOWS",
	beginSequenceAtStart: true,
	minLevel: 1,
	maxLevel: 4
})
YIELD path
RETURN path;

我们可以在从 Joe 开始，通过交替的 FOLLOWS 和 KNOWS 关系类型的生成树中看到该生成树的 Neo4j 浏览器可视化效果。

图 11. 从 Joe 开始，通过交替的 FOLLOWS 和 KNOWS 关系类型的生成树

关于 apoc.path.spanningTree 的更多文档

apoc.path.spanningTree过程