桥接

词汇表

有向

有向特性。该算法在有向图上定义良好。

有向

有向特性。该算法忽略图的方向。

有向

有向特性。该算法不能在有向图上运行。

无向

无向特性。该算法在无向图上定义良好。

无向

无向特性。该算法忽略图的无向性。

异构节点

异构节点 完全支持。该算法能够区分不同类型的节点。

异构节点

异构节点 允许。该算法对所有选定的节点进行类似的处理,而不管其标签如何。

异构关系

异构关系 完全支持。该算法能够区分不同类型的关系。

异构关系

异构关系 允许。该算法对所有选定的关系进行类似的处理,而不管其类型如何。

加权关系

加权特性。该算法支持使用关系属性作为权重,通过 relationshipWeightProperty 配置参数指定。

加权关系

加权特性。该算法将每个关系视为同等重要,丢弃任何关系权重的值。

简介

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

有关此算法的更多信息,请参见

语法

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

每种模式下的 Bridges 语法
在命名图上以流模式运行 Bridges。
CALL gds.bridges.stream(
  graphName: String,
  configuration: Map
)
YIELD
  from: Integer,
  to: Integer
表 1. 参数
名称 类型 默认值 可选 描述

graphName

字符串

n/a

存储在目录中的图的名称。

configuration

映射

{}

算法特定和/或图过滤的配置。

表 2. 配置
名称 类型 默认值 可选 描述

nodeLabels

字符串列表

['*']

使用给定的节点标签过滤命名图。将包含具有任何给定标签的节点。

relationshipTypes

字符串列表

['*']

使用给定的关系类型过滤命名图。将包含具有任何给定类型的关系。

concurrency

整数

1

该算法是单线程的,更改并发参数不会影响运行时间。

jobId

字符串

内部生成

可以提供的 ID,以便更轻松地跟踪算法的进度。

logProgress

布尔值

如果禁用,则不会记录进度百分比。

表 3. 结果
名称 类型 描述

from

整数

起始节点 ID。

to

整数

结束节点 ID。

示例

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

这些示例使用Cypher 投影作为规范。原生投影将在未来版本中弃用。

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

Visualization of the example graph
以下 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);

该图有两个紧密连接的用户集群。这两个集群之间只有一条边。

以下语句将使用 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

1040

1040

"1040 字节"

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

有关stream模式的更多详细信息,请参见

以下将在stream模式下运行算法:
CALL gds.bridges.stream('myGraph')
YIELD from, to
RETURN gds.util.asNode(from).name AS fromName, gds.util.asNode(to).name AS toName
ORDER BY fromName ASC, toName ASC
表 5. 结果
fromName toName

"Alice"

"Doug"