折叠路径

简介

“折叠路径”算法是一种遍历算法，能够在遍历的起始节点和结束节点之间创建关系。换句话说，起始节点和结束节点之间的路径被“折叠”为单个关系（直接路径）。该算法旨在支持许多图算法所需的单部图 (monopartite graphs) 的创建。

该算法的主要输入是一组路径模板。从指定图中的每个节点开始，按照配置中指定的顺序依次遍历每个模板的关系。只有在遍历完完整路径后到达的节点才会被用作结束节点。对于每对至少存在一条从起始节点到结束节点的路径的节点，将精确创建一条有向关系。

语法

各模式下的折叠路径语法

在命名图上以变异 (mutate) 模式运行折叠路径。

CALL gds.collapsePath.mutate(
  graphName: String,
  configuration: Map
)
YIELD
  preProcessingMillis: Integer,
  computeMillis: Integer,
  mutateMillis: Integer,
  relationshipsWritten: Integer,
  configuration: Map

表 1. 参数
名称	类型	默认	可选	描述
graphName	字符串	`不适用`	否	存储在目录中的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

表 2. 在命名图上执行算法的通用配置。
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。
concurrency	整数	`4 ^[1]`	是	用于运行算法的并发线程数。
1. 在 GDS 会话中，默认值为可用处理器数量。

表 3. 算法特定配置
名称	类型	默认	可选	描述
pathTemplates (路径模板)	字符串列表的列表	`不适用`	否	路径模板是用于遍历的关系类型的有序列表。可以多次添加相同的关系类型，以按指示进行遍历。此外，您可以指定多个路径模板一次性处理。
mutateRelationshipType	字符串	`不适用`	否	新创建关系的关系类型。
allowSelfLoops (允许自循环)	布尔值	`false`	是	指示是否可以创建自引用关系，即起始节点和结束节点相同的关系。

表 4. 结果
名称	类型	描述
`preProcessingMillis`	整数	预处理数据的毫秒数。
`computeMillis`	整数	运行算法的毫秒数。
`mutateMillis`	整数	向投影图添加属性的毫秒数。
`relationshipsWritten`	整数	算法创建的关系数量。
`配置`	Map	用于运行算法的配置。

示例

以下所有示例应在空数据库中运行。

本示例将 Cypher 投影作为标准。原生投影将在未来的版本中弃用。

考虑由以下 Cypher 语句创建的图

CREATE
  (Dan:Person),
  (Annie:Person),
  (Matt:Person),
  (Jeff:Person),

  (Guitar:Instrument),
  (Flute:Instrument),

  (Dan)-[:PLAYS]->(Guitar),
  (Annie)-[:PLAYS]->(Guitar),

  (Matt)-[:PLAYS]->(Flute),
  (Jeff)-[:PLAYS]->(Flute)

在此示例中，我们希望在演奏相同乐器的 Person 节点之间创建名为 PLAYS_SAME_INSTRUMENT 的关系。为此，我们必须遍历由以下 Cypher 模式指定的路径

(p1:Person)-[:PLAYS]->(:Instrument)-[:PLAYED_BY]->(p2:Person)

在我们的源图中，仅存在 PLAYS 关系类型。可以通过以 REVERSE（反向）加载 PLAYS 关系类型来创建 PLAYED_BY 关系类型。以下查询将投影这样一个图

MATCH (p:Person)-[:PLAYS]->(i:Instrument)
CALL (p, i) {
  RETURN id(p) AS sourceId, id(i) AS targetId, 'PLAYS' AS rType
  UNION
  WITH p, i
  RETURN id(i) AS sourceId, id(p) AS targetId, 'PLAYED_BY' AS rType
}
RETURN gds.graph.project('persons', sourceId, targetId, { relationshipType: rType })

现在，我们可以通过在 pathTemplates 选项中指定遍历 PLAYS, PLAYED_BY 来运行该算法。

CALL gds.collapsePath.mutate(
  'persons',
  {
    pathTemplates: [['PLAYS', 'PLAYED_BY']],
    allowSelfLoops: false,
    mutateRelationshipType: 'PLAYS_SAME_INSTRUMENT'
  }
) YIELD relationshipsWritten

表 5. 结果
relationshipsWritten
4

当按 PLAYS_SAME_INSTRUMENT 关系过滤时，变异后的图将如下所示

CREATE
  (Dan:Person),
  (Annie:Person),
  (Matt:Person),
  (Jeff:Person),

  (Guitar:Instrument),
  (Flute:Instrument),

  (Dan)-[:PLAYS_SAME_INSTRUMENT]->(Annie),
  (Annie)-[:PLAYS_SAME_INSTRUMENT]->(Dan),

  (Matt)-[:PLAYS_SAME_INSTRUMENT]->(Jeff),
  (Jeff)-[:PLAYS_SAME_INSTRUMENT]->(Matt)