桥接
词汇表
- 有向
-
有向特性。该算法在有向图上定义良好。
- 有向
-
有向特性。该算法忽略图的方向。
- 有向
-
有向特性。该算法不能在有向图上运行。
- 无向
-
无向特性。该算法在无向图上定义良好。
- 无向
-
无向特性。该算法忽略图的无向性。
- 异构节点
-
异构节点 完全支持。该算法能够区分不同类型的节点。
- 异构节点
-
异构节点 允许。该算法对所有选定的节点进行类似的处理,而不管其标签如何。
- 异构关系
-
异构关系 完全支持。该算法能够区分不同类型的关系。
- 异构关系
-
异构关系 允许。该算法对所有选定的关系进行类似的处理,而不管其类型如何。
- 加权关系
-
加权特性。该算法支持使用关系属性作为权重,通过 relationshipWeightProperty 配置参数指定。
- 加权关系
-
加权特性。该算法将每个关系视为同等重要,丢弃任何关系权重的值。
简介
给定一个图,桥是指移除后会增加图中连通分量数量的关系。等效地,当且仅当一个关系不包含在任何循环中时,它才能是桥。Neo4j GDS 库提供了一种高效的线性时间顺序算法来计算图中的所有桥。
有关此算法的更多信息,请参见
语法
本节介绍了在每种执行模式下执行 Bridges 算法所使用的语法。我们正在描述语法的命名图变体。要了解有关通用语法变体的更多信息,请参见语法概述。
CALL gds.bridges.stream(
graphName: String,
configuration: Map
)
YIELD
from: Integer,
to: Integer
名称 | 类型 | 默认值 | 可选 | 描述 |
---|---|---|---|---|
graphName |
字符串 |
|
否 |
存储在目录中的图的名称。 |
configuration |
映射 |
|
是 |
算法特定和/或图过滤的配置。 |
名称 | 类型 | 默认值 | 可选 | 描述 |
---|---|---|---|---|
字符串列表 |
|
是 |
使用给定的节点标签过滤命名图。将包含具有任何给定标签的节点。 |
|
字符串列表 |
|
是 |
使用给定的关系类型过滤命名图。将包含具有任何给定类型的关系。 |
|
整数 |
|
是 |
该算法是单线程的,更改并发参数不会影响运行时间。 |
|
字符串 |
|
是 |
可以提供的 ID,以便更轻松地跟踪算法的进度。 |
|
布尔值 |
|
是 |
如果禁用,则不会记录进度百分比。 |
名称 | 类型 | 描述 |
---|---|---|
from |
整数 |
起始节点 ID。 |
to |
整数 |
结束节点 ID。 |
示例
以下所有示例都应在空数据库中运行。 这些示例使用Cypher 投影作为规范。原生投影将在未来版本中弃用。 |
在本节中,我们将展示在具体图上运行 Bridges 算法的示例。目的是说明结果是什么样子,并提供有关如何在实际环境中使用该算法的指南。我们将在少量节点以特定模式连接的小型社交网络图上执行此操作。示例图如下所示
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);
该图有两个紧密连接的用户集群。这两个集群之间只有一条边。
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
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
fromName | toName |
---|---|
"Alice" |
"Doug" |