`pgr_binaryBreadthFirstSearch` - 实验¶

pgr_binaryBreadthFirstSearch — Returns the shortest path in a binary graph.

任何边权属于集合 {0,X} 的图（其中“X”是任何非负整数）都被称为“二元图”。

Warning

可能服务器崩溃

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

Warning

实验功能

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

可用性

版本3.2.0
- 新 实验性 签名：
  - pgr_binaryBreadthFirstSearch(组合)
版本3.0.0
- 新实验签名：
  - pgr_binaryBreadthFirstSearch(一对一)
  - pgr_binaryBreadthFirstSearch(一对多)
  - pgr_binaryBreadthFirstSearch(多对一)
  - pgr_binaryBreadthFirstSearch(多对多)

描述¶

众所周知，在无权重图中，使用广度优先搜索（Breadth First Search）可以在 \(O(|E|)\) 内找到单个源点与所有其他顶点之间的最短路径，也就是说，距离是指从源点到另一个顶点所需的最少边数。我们也可以把这样的图解释为加权图，其中每条边的权重为 \(1\)。如果图中不是所有边的权重都相同，我们就需要一种更通用的算法，比如 Dijkstra 算法，它的运行时间为 \(O(|E|log|V||)\)。

然而，如果权重受到更多限制，我们可以使用一种更快的算法。这个算法被称为'二进制广度优先搜索'，也称为'0-1 BFS'，它是标准广度优先搜索问题的一种变体，用于解决单源最短路径（SSSP）问题，当每条边的权重属于集合{0，X}，其中'X'是任意非负实数时，其时间复杂度为 \(O(|E|)\)。

主要特点是：

过程仅在“二元图”上完成。（“二元图”：边权重属于集合 {0,X} 的任何图，其中“X”是任何非负实整数。）
出于优化目的，start_vids`或 `end_vids 中的任何重复值都将被忽略。
返回值是有序的：
- start_vid 升序
- end_vid 升序
运行时间： \(O(| start\_vids | * |E|)\)

签名¶

总结

pgr_binaryBreadthFirstSearch(Edges SQL, start vid, end vid, [directed])
pgr_binaryBreadthFirstSearch(Edges SQL, start vid, end vids, [directed])
pgr_binaryBreadthFirstSearch(Edges SQL, start vids, end vid, [directed])
pgr_binaryBreadthFirstSearch(Edges SQL, start vids, end vids, [directed])
pgr_binaryBreadthFirstSearch(Edges SQL, Combinations SQL, [directed])

返回 (seq, path_seq, [start_vid], [end_vid], node, edge, cost, agg_cost) 的集合

OR EMPTY SET

注意: 使用示例数据网络，因为所有权重都相同（即为 \(1\)）

一对一¶

pgr_binaryBreadthFirstSearch(Edges SQL, start vid, end vid, [directed])

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

OR EMPTY SET

示例:: 在有向图上从顶点 \(6\) 到顶点 \(10\)

SELECT * FROM pgr_binaryBreadthFirstSearch(
  'SELECT id, source, target, cost, reverse_cost from edges',
  6, 10, true);
 seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
   1 |        1 |    6 |    4 |    1 |        0
   2 |        2 |    7 |    8 |    1 |        1
   3 |        3 |   11 |    9 |    1 |        2
   4 |        4 |   16 |   16 |    1 |        3
   5 |        5 |   15 |    3 |    1 |        4
   6 |        6 |   10 |   -1 |    0 |        5
(6 rows)

一对多¶

pgr_binaryBreadthFirstSearch(Edges SQL, start vid, end vids, [directed])

返回 (seq, path_seq, end_vid, node, edge, cost, agg_cost) 的集合

OR EMPTY SET

示例:: 在有向图上从顶点 \(6\) 到顶点 \(\{10, 17\}\)

SELECT * FROM pgr_binaryBreadthFirstSearch(
  'SELECT id, source, target, cost, reverse_cost from edges',
  6, ARRAY[10, 17]);
 seq | path_seq | end_vid | node | edge | cost | agg_cost
-----+----------+---------+------+------+------+----------
   1 |        1 |      10 |    6 |    4 |    1 |        0
   2 |        2 |      10 |    7 |    8 |    1 |        1
   3 |        3 |      10 |   11 |    9 |    1 |        2
   4 |        4 |      10 |   16 |   16 |    1 |        3
   5 |        5 |      10 |   15 |    3 |    1 |        4
   6 |        6 |      10 |   10 |   -1 |    0 |        5
   7 |        1 |      17 |    6 |    4 |    1 |        0
   8 |        2 |      17 |    7 |    8 |    1 |        1
   9 |        3 |      17 |   11 |   11 |    1 |        2
  10 |        4 |      17 |   12 |   13 |    1 |        3
  11 |        5 |      17 |   17 |   -1 |    0 |        4
(11 rows)

多对一¶

pgr_binaryBreadthFirstSearch(Edges SQL, start vids, end vid, [directed])

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

OR EMPTY SET

示例:: 在有向图上从顶点 \(\{6, 1\}\) 到顶点 \(17\)

SELECT * FROM pgr_binaryBreadthFirstSearch(
  'SELECT id, source, target, cost, reverse_cost from edges',
  ARRAY[6, 1], 17);
 seq | path_seq | start_vid | node | edge | cost | agg_cost
-----+----------+-----------+------+------+------+----------
   1 |        1 |         1 |    1 |    6 |    1 |        0
   2 |        2 |         1 |    3 |    7 |    1 |        1
   3 |        3 |         1 |    7 |    8 |    1 |        2
   4 |        4 |         1 |   11 |   11 |    1 |        3
   5 |        5 |         1 |   12 |   13 |    1 |        4
   6 |        6 |         1 |   17 |   -1 |    0 |        5
   7 |        1 |         6 |    6 |    4 |    1 |        0
   8 |        2 |         6 |    7 |    8 |    1 |        1
   9 |        3 |         6 |   11 |   11 |    1 |        2
  10 |        4 |         6 |   12 |   13 |    1 |        3
  11 |        5 |         6 |   17 |   -1 |    0 |        4
(11 rows)

多对多¶

pgr_binaryBreadthFirstSearch(Edges SQL, start vids, end vids, [directed])

Returns set of (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)

OR EMPTY SET

示例:: 在无向图上从顶点 \(\{6, 1\}\) 到顶点 \(\{10, 17\}\)

SELECT * FROM pgr_binaryBreadthFirstSearch(
  'SELECT id, source, target, cost, reverse_cost from edges',
  ARRAY[6, 1], ARRAY[10, 17],
  directed => false);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
|        1 |         1 |      10 |    1 |    6 |    1 |        0
|        2 |         1 |      10 |    3 |    7 |    1 |        1
|        3 |         1 |      10 |    7 |    4 |    1 |        2
|        4 |         1 |      10 |    6 |    2 |    1 |        3
|        5 |         1 |      10 |   10 |   -1 |    0 |        4
|        1 |         1 |      17 |    1 |    6 |    1 |        0
|        2 |         1 |      17 |    3 |    7 |    1 |        1
|        3 |         1 |      17 |    7 |    8 |    1 |        2
|        4 |         1 |      17 |   11 |   11 |    1 |        3
|        5 |         1 |      17 |   12 |   13 |    1 |        4
|        6 |         1 |      17 |   17 |   -1 |    0 |        5
|        1 |         6 |      10 |    6 |    2 |    1 |        0
|        2 |         6 |      10 |   10 |   -1 |    0 |        1
|        1 |         6 |      17 |    6 |    4 |    1 |        0
|        2 |         6 |      17 |    7 |    8 |    1 |        1
|        3 |         6 |      17 |   11 |   11 |    1 |        2
|        4 |         6 |      17 |   12 |   13 |    1 |        3
|        5 |         6 |      17 |   17 |   -1 |    0 |        4
(18 rows)

组合¶

pgr_binaryBreadthFirstSearch(Edges SQL, Combinations SQL, [directed])

Returns set of (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)

OR EMPTY SET

示例:: 在无向图上使用组合表

组合表：

SELECT source, target FROM combinations;
 source | target
--------+--------
      5 |      6
      5 |     10
      6 |      5
      6 |     15
      6 |     14
(5 rows)

查询：

SELECT * FROM pgr_binaryBreadthFirstSearch(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  'SELECT source, target FROM combinations',
  false);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         5 |       6 |    5 |    1 |    1 |        0
   2 |        2 |         5 |       6 |    6 |   -1 |    0 |        1
   3 |        1 |         5 |      10 |    5 |    1 |    1 |        0
   4 |        2 |         5 |      10 |    6 |    2 |    1 |        1
   5 |        3 |         5 |      10 |   10 |   -1 |    0 |        2
   6 |        1 |         6 |       5 |    6 |    1 |    1 |        0
   7 |        2 |         6 |       5 |    5 |   -1 |    0 |        1
   8 |        1 |         6 |      15 |    6 |    2 |    1 |        0
   9 |        2 |         6 |      15 |   10 |    3 |    1 |        1
  10 |        3 |         6 |      15 |   15 |   -1 |    0 |        2
(10 rows)

参数¶

列	类型	描述
Edges SQL	`TEXT`	Edges SQL 如下所述
Combinations SQL	`TEXT`	Combinations SQL 如下所述
start vid	`BIGINT`	路径起始顶点的标识符。
start vids	`ARRAY[BIGINT]`	起始顶点的标识符数组。
end vid	`BIGINT`	路径结束顶点的标识符。
end vids	`ARRAY[BIGINT]`	结束顶点的标识符数组。

可选参数¶

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

内部查询¶

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

分量 SQL¶

参数	类型	描述
`source`	ANY-INTEGER	出发顶点的标识符。
`target`	ANY-INTEGER	到达顶点的标识符。

其中：

ANY-INTEGER:: SMALLINT, INTEGER, BIGINT

结果列¶

(seq, path_id, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost) 集合

列	类型	描述
`seq`	`INTEGER`	从 1 开始的顺序值。
`path_id`	`INTEGER`	路径标识符。从 `start_vid` 到 `end_vid` 的第一个路径的值为 1 。
`path_seq`	`INTEGER`	路径中的相对位置。路径开头的值为 1。
`start_vid`	`BIGINT`	起始顶点的标识符。当查询中有多个起始向量时返回。多对一多对多组合
`end_vid`	`BIGINT`	结束顶点的标识符。当查询中有多个结束顶点时返回。一对多多对多组合
`node`	`BIGINT`	从 `start_vid` 到 `end_vid` 路径中节点的标识符。
`edge`	`BIGINT`	用于从路径序列中的 `node` 到下一个节点的边的标识符。 -1 表示路径的最后一个节点。
`cost`	`FLOAT`	从使用 `edge` 的 `node` 遍历到路径序列中的下一个节点的成本。
`agg_cost`	`FLOAT`	从 `start_vid` 到 `node` 的总成本。

其他示例¶

示例:: 手动指定的顶点组合。

SELECT * FROM pgr_binaryBreadthFirstSearch(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  'SELECT * FROM (VALUES (6, 10), (6, 7), (12, 10)) AS combinations (source, target)');
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         6 |       7 |    6 |    4 |    1 |        0
   2 |        2 |         6 |       7 |    7 |   -1 |    0 |        1
   3 |        1 |         6 |      10 |    6 |    4 |    1 |        0
   4 |        2 |         6 |      10 |    7 |    8 |    1 |        1
   5 |        3 |         6 |      10 |   11 |    9 |    1 |        2
   6 |        4 |         6 |      10 |   16 |   16 |    1 |        3
   7 |        5 |         6 |      10 |   15 |    3 |    1 |        4
   8 |        6 |         6 |      10 |   10 |   -1 |    0 |        5
   9 |        1 |        12 |      10 |   12 |   13 |    1 |        0
  10 |        2 |        12 |      10 |   17 |   15 |    1 |        1
  11 |        3 |        12 |      10 |   16 |   16 |    1 |        2
  12 |        4 |        12 |      10 |   15 |    3 |    1 |        3
  13 |        5 |        12 |      10 |   10 |   -1 |    0 |        4
(13 rows)

另请参阅¶

索引和表格

pgr_binaryBreadthFirstSearch - 实验¶

描述¶

签名¶

一对一¶

一对多¶

多对一¶

多对多¶

组合¶

参数¶

可选参数¶

内部查询¶

Edges SQL¶

分量 SQL¶

结果列¶

其他示例¶

另请参阅¶

`pgr_binaryBreadthFirstSearch` - 实验¶