桥

此功能在 Aura 图分析无服务器版中不可用。

有向

无向

异构节点

异构关系

加权关系

词汇表

有向: 有向特性。该算法在有向图上定义良好。
有向: 有向特性。该算法忽略图的方向。
有向: 有向特性。该算法不在有向图上运行。
无向: 无向特性。该算法在无向图上定义良好。
无向: 无向特性。该算法忽略图的无向性。
异构节点: 异构节点完全支持。该算法能够区分不同类型的节点。
异构节点: 异构节点允许。该算法对所有选定的节点进行相似处理，无论其标签如何。
异构关系: 异构关系完全支持。该算法能够区分不同类型的关系。
异构关系: 异构关系允许。该算法对所有选定的关系进行相似处理，无论其类型如何。
加权关系: 加权特性。该算法支持将关系属性用作权重，通过 relationshipWeightProperty 配置参数指定。
加权关系: 加权特性。该算法将每个关系视为同等重要，并舍弃任何关系权重的价值。

简介

给定一个图，桥是这样一种关系：移除它会增加图中连通分量的数量。等价地，一个关系当且仅当它不包含在任何环中时，才可能是一座桥。Neo4j GDS 库提供了一种高效的线性时间顺序算法来计算图中的所有桥。

有关此算法的更多信息，请参阅

桥（图论）

语法

本节介绍在每种执行模式下运行 Bridges 算法所使用的语法。我们将描述命名图语法的变体。要了解有关通用语法变体的更多信息，请参阅语法概述。

各模式下的 Bridges 语法

在命名图上以流模式运行 Bridges。

CALL gds.bridges.stream(
  graphName: String,
  configuration: Map
)
YIELD
  from: Integer,
  to: Integer
  remainingSizes: List of Long

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

表 2. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。将包含具有任何给定类型的关系。
concurrency	整数	`1`	是	该算法是单线程的，更改并发参数对运行时没有影响。
jobId	字符串	`内部生成`	是	一个可用于更轻松地跟踪算法进度的 ID。
logProgress	布尔值	`true`	是	如果禁用，将不会记录进度百分比。

表 3. 结果
名称	类型	描述
起始节点	整数	起始节点 ID。
结束节点	整数	结束节点 ID。
splitComponens	长整型列表	一个列表，其中包含移除关系后组件的最终大小。

示例

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

这些示例通常使用 Cypher 投影。原生投影将在未来版本中弃用。

在本节中，我们将展示在具体图上运行 Bridges 算法的示例。目的是说明结果是什么样子，并提供在实际环境中如何使用该算法的指南。我们将在一个由少量节点以特定模式连接而成的小型社交网络图上进行此操作。示例图如下所示：

以下 Cypher 语句将在 Neo4j 数据库中创建示例图

CREATE
  (nAlice:User {name: 'Alice'}),
  (nBridget:User {name: 'Bridget'}),
  (nCharles:User {name: 'Charles'}),
  (nDoug:User {name: 'Doug'}),
  (nMark:User {name: 'Mark'}),
  (nMichael:User {name: 'Michael'}),

  (nAlice)-[:LINK]->(nBridget),
  (nAlice)-[:LINK]->(nCharles),
  (nCharles)-[:LINK]->(nBridget),

  (nAlice)-[:LINK]->(nDoug),

  (nMark)-[:LINK]->(nDoug),
  (nMark)-[:LINK]->(nMichael),
  (nMichael)-[:LINK]->(nDoug);

该图有两个 Users 簇，它们紧密连接。这些簇之间只有一条边。

以下语句将使用 Cypher 投影来投影一个图，并将其以名称 'myGraph' 存储在图目录中。

MATCH (source:User)-[r:LINK]->(target:User)
RETURN gds.graph.project(
  'myGraph',
  source,
  target,
  {},
  { undirectedRelationshipTypes: ['*'] }
)

内存估算

首先，我们将使用 estimate 过程来估算运行算法的成本。这可以在任何执行模式下完成。在本例中，我们将使用 stream 模式。估算算法有助于了解在图上运行算法将产生的内存影响。当您随后实际在某种执行模式下运行算法时，系统将执行一次估算。如果估算显示执行超出其内存限制的可能性非常高，则禁止执行。要了解更多信息，请参阅自动估算和执行阻止。

有关 estimate 的更多详细信息，请参阅内存估算。

以下将估算运行算法所需的内存

CALL gds.bridges.stream.estimate('myGraph', {})
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory

表 4. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
6	14	1152	1152	"1152 字节"

流式

在 stream 执行模式下，算法返回每个关系的桥。这使我们能够直接检查结果或在 Cypher 中对它们进行后处理，而不会产生任何副作用。

有关 stream 模式的更多详细信息，请参阅流式。

以下将在 stream 模式下运行算法

CALL gds.bridges.stream('myGraph')
YIELD from, to, remainingSizes
RETURN gds.util.asNode(from).name AS fromName, gds.util.asNode(to).name AS toName, remainingSizes
ORDER BY fromName ASC, toName ASC

表 5. 结果
fromName	toName	remainingSizes
"Alice"	"Doug"	[3, 3]