`pgr_breadthFirstSearch` - 实验¶

pgr_breadthFirstSearch —使用广度优先搜索算法返回遍历顺序。

Warning

可能服务器崩溃

这些功能可能会导致服务器崩溃

Warning

实验功能

它们不是当前版本的正式版本。
它们可能不会正式成为下一个版本的一部分：
- 这些函数可能不使用 ANY-INTEGER 和 ANY-NUMERICAL
- 名称可能会改变。
- 签名可能会改变。
- 功能可能会改变。
- pgTap 测试可能丢失。
- 可能需要 c/c++编码。
- 可能缺乏文档。
- 文档（如果有）可能需要重写。
- 可能需要自动生成文档示例。
- 可能需要社区的大量反馈。
- 可能取决于 pgRouting 的拟议功能
- 可能依赖于 pgRouting 的已弃用函数

可用性

版本3.0.0
- 新 实验性 签名：
  - pgr_breadthFirstSearch (单顶点搜索)
  - pgr_breadthFirstSearch (多顶点搜索)

描述¶

提供从根顶点到特定深度的广度优先搜索遍历顺序。

主要特点是：

该实现适用于任何类型的图。
提供从源节点到目标深度级别的广度优先搜索遍历顺序。
运行时间： \(O(E + V)\)

签名¶

总结

pgr_breadthFirstSearch(Edges SQL, root vid, [options])
pgr_breadthFirstSearch(Edges SQL, root vids, [options])
options: [max_depth, directed]

返回 (seq, depth, start_vid, node, edge, cost, agg_cost) 的集合

单顶点¶

pgr_breadthFirstSearch(Edges SQL, root vid, [options])

options: [max_depth, directed]

返回 (seq, depth, start_vid, node, edge, cost, agg_cost) 的集合

示例:: 从根顶点 \(6\) 开始，该顶点位于一个有向图中，其边按 id 升序排列

SELECT * FROM pgr_breadthFirstSearch(
  'SELECT id, source, target, cost, reverse_cost
  FROM edges ORDER BY id',
  6);
 seq | depth | start_vid | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+----------
   1 |     0 |         6 |    6 |   -1 |    0 |        0
   2 |     1 |         6 |    5 |    1 |    1 |        1
   3 |     1 |         6 |    7 |    4 |    1 |        1
   4 |     2 |         6 |    3 |    7 |    1 |        2
   5 |     2 |         6 |   11 |    8 |    1 |        2
   6 |     2 |         6 |    8 |   10 |    1 |        2
   7 |     3 |         6 |    1 |    6 |    1 |        3
   8 |     3 |         6 |   16 |    9 |    1 |        3
   9 |     3 |         6 |   12 |   11 |    1 |        3
  10 |     3 |         6 |    9 |   14 |    1 |        3
  11 |     4 |         6 |   17 |   15 |    1 |        4
  12 |     4 |         6 |   15 |   16 |    1 |        4
  13 |     5 |         6 |   10 |    3 |    1 |        5
(13 rows)

多个顶点¶

pgr_breadthFirstSearch(Edges SQL, root vids, [options])

options: [max_depth, directed]

返回 (seq, depth, start_vid, node, edge, cost, agg_cost) 的集合

示例:: 从根顶点开始 \({12, 6\}\) 在一个无向图上，depth \(<=2\)，边按 id 升序排列

SELECT * FROM pgr_breadthFirstSearch(
  'SELECT id, source, target, cost, reverse_cost
  FROM edges ORDER BY id',
  ARRAY[12, 6], directed => false, max_depth => 2);
 seq | depth | start_vid | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+----------
   1 |     0 |         6 |    6 |   -1 |    0 |        0
   2 |     1 |         6 |    5 |    1 |    1 |        1
   3 |     1 |         6 |   10 |    2 |    1 |        1
   4 |     1 |         6 |    7 |    4 |    1 |        1
   5 |     2 |         6 |   15 |    3 |    1 |        2
   6 |     2 |         6 |   11 |    5 |    1 |        2
   7 |     2 |         6 |    3 |    7 |    1 |        2
   8 |     2 |         6 |    8 |   10 |    1 |        2
   9 |     0 |        12 |   12 |   -1 |    0 |        0
  10 |     1 |        12 |   11 |   11 |    1 |        1
  11 |     1 |        12 |    8 |   12 |    1 |        1
  12 |     1 |        12 |   17 |   13 |    1 |        1
  13 |     2 |        12 |   10 |    5 |    1 |        2
  14 |     2 |        12 |    7 |    8 |    1 |        2
  15 |     2 |        12 |   16 |    9 |    1 |        2
  16 |     2 |        12 |    9 |   14 |    1 |        2
(16 rows)

参数¶

参数	类型	描述
Edges SQL	`TEXT`	Edges SQL 如下所述。
root vid	`BIGINT`	树的根顶点的标识符。当值为 \(0\) 时，则获取从森林中每棵树的随机节点开始的生成森林。
root vids	`ARRAY` [ ANY-INTEGER ]	根顶点的标识符数组。 \(0\) 值被忽略出于优化目的，任何重复的值都将被忽略。

参数

类型

描述

Edges SQL

TEXT

Edges SQL 如下所述。

root vid

BIGINT

树的根顶点的标识符。

当值为 \(0\) 时，则获取从森林中每棵树的随机节点开始的生成森林。

root vids

ARRAY [ ANY-INTEGER ]

根顶点的标识符数组。

\(0\) 值被忽略

出于优化目的，任何重复的值都将被忽略。

其中：

ANY-INTEGER:: SMALLINT, INTEGER, BIGINT
ANY-NUMERIC:: SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC

可选参数¶

列	类型	默认	描述
`directed`	`BOOLEAN`	`true`	当 `true` 时，该图被视为有有向如果为 `false` ，则该图被视为无向。

DFS 可选参数¶

参数	类型	默认	描述
`max_depth`	`BIGINT`	\(9223372036854775807\)	树深度的上限。为负数时抛出错误。

参数

类型

默认

描述

max_depth

BIGINT

\(9223372036854775807\)

树深度的上限。

为负数时抛出错误。

内部查询¶

Edges SQL¶

列	类型	默认	描述
`id`	ANY-INTEGER		边的标识符。
`source`	ANY-INTEGER		边的第一个端点顶点的标识符。
`target`	ANY-INTEGER		边的第二个端点顶点的标识符。
`cost`	ANY-NUMERICAL		边(`source`, `target`)的权重
`reverse_cost`	ANY-NUMERICAL	-1	边(`target`, `source`)的权重当为负时：边（ `target`, `source` ）不存在，因此它不是图的一部分。

其中：

ANY-INTEGER:: SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL:: SMALLINT, INTEGER, BIGINT, REAL, FLOAT

结果列¶

返回一组 (seq, depth, start_vid, node, edge, cost, agg_cost)

参数	类型	描述
`seq`	`BIGINT`	从 \(1\) 开始的顺序值。
`depth`	`BIGINT`	`node` 的深度。 \(0\) 当 `node` = `start_vid`。
`start_vid`	`BIGINT`	根顶点的标识符。
`node`	`BIGINT`	使用 `edge` 到达的``node`` 的标识符。
`edge`	`BIGINT`	用于到达 `node` 的 `edge` 的标识符。 \(-1\) 当 `node` = `start_vid`。
`cost`	`FLOAT`	遍历 `edge` 的成本。
`agg_cost`	`FLOAT`	从 `start_vid` 到 `node` 的总成本。

其中：

ANY-INTEGER:: SMALLINT, INTEGER, BIGINT
ANY-NUMERIC:: SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC

其他示例¶

示例:: 与单个顶点相同，边按 id 升序排列。

SELECT * FROM pgr_breadthFirstSearch(
  'SELECT id, source, target, cost, reverse_cost
  FROM edges ORDER BY id',
  6);
 seq | depth | start_vid | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+----------
   1 |     0 |         6 |    6 |   -1 |    0 |        0
   2 |     1 |         6 |    5 |    1 |    1 |        1
   3 |     1 |         6 |    7 |    4 |    1 |        1
   4 |     2 |         6 |    3 |    7 |    1 |        2
   5 |     2 |         6 |   11 |    8 |    1 |        2
   6 |     2 |         6 |    8 |   10 |    1 |        2
   7 |     3 |         6 |    1 |    6 |    1 |        3
   8 |     3 |         6 |   16 |    9 |    1 |        3
   9 |     3 |         6 |   12 |   11 |    1 |        3
  10 |     3 |         6 |    9 |   14 |    1 |        3
  11 |     4 |         6 |   17 |   15 |    1 |        4
  12 |     4 |         6 |   15 |   16 |    1 |        4
  13 |     5 |         6 |   10 |    3 |    1 |        5
(13 rows)

示例:: 与单个顶点相同，边按 id 降序排列。

SELECT * FROM pgr_breadthFirstSearch(
  'SELECT id, source, target, cost, reverse_cost
  FROM edges ORDER BY id DESC',
  6);
 seq | depth | start_vid | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+----------
   1 |     0 |         6 |    6 |   -1 |    0 |        0
   2 |     1 |         6 |    7 |    4 |    1 |        1
   3 |     1 |         6 |    5 |    1 |    1 |        1
   4 |     2 |         6 |    8 |   10 |    1 |        2
   5 |     2 |         6 |   11 |    8 |    1 |        2
   6 |     2 |         6 |    3 |    7 |    1 |        2
   7 |     3 |         6 |    9 |   14 |    1 |        3
   8 |     3 |         6 |   12 |   12 |    1 |        3
   9 |     3 |         6 |   16 |    9 |    1 |        3
  10 |     3 |         6 |    1 |    6 |    1 |        3
  11 |     4 |         6 |   17 |   13 |    1 |        4
  12 |     4 |         6 |   15 |   16 |    1 |        4
  13 |     5 |         6 |   10 |    3 |    1 |        5
(13 rows)

由此产生的遍历是不同的。

左图显示的是按 ID 升序排列的结果，右图显示的是按边缘标识符降序排列的结果。

另请参阅¶

索引和表格

pgr_breadthFirstSearch - 实验¶

描述¶

签名¶

单顶点¶

多个顶点¶

参数¶

可选参数¶

DFS 可选参数¶

内部查询¶

Edges SQL¶

结果列¶

其他示例¶

另请参阅¶

`pgr_breadthFirstSearch` - 实验¶