pgr_topologicalSort - 实验

pgr_topologicalSort — 有向无环图 (DAG) 的顶点的线性排序。

Boost 图内部

Warning

可能服务器崩溃

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

Warning

实验功能

• 它们不是当前版本的正式版本。

• 它们可能不会正式成为下一个版本的一部分：

  • 这些函数可能不使用 ANY-INTEGER 和 ANY-NUMERICAL

  • 名称可能会改变。

  • 签名可能会改变。

  • 功能可能会改变。

  • pgTap 测试可能丢失。

  • 可能需要 c/c++编码。

  • 可能缺乏文档。

  • 文档（如果有）可能需要重写。

  • 可能需要自动生成文档示例。

  • 可能需要社区的大量反馈。

  • 可能取决于 pgRouting 的拟议功能

  • 可能依赖于 pgRouting 的已弃用函数

可用性

• 版本3.0.0

  • 新 实验 函数

描述

拓扑排序算法创建了一个顶点的线性排序，使得如果图中存在边 \((u,v)\)，则在排序中 \(v\) 出现在 \(u\) 之前。

主要特点是：

• 该过程仅对有向无环图有效。 否则它会抛出警告。

• 出于优化目的，如果有多个答案，则该函数

  将返回其中之一。

• 返回的值按拓扑顺序排序：

• 运行时间： \(O(V + E)\)

签名

总结

pgr_topologicalSort(Edges SQL)

Returns set of (seq, sorted_v)

OR EMPTY SET

示例:

对图进行拓扑排序

SELECT * FROM pgr_topologicalsort(
  $$SELECT id, source, target, cost
  FROM edges WHERE cost >= 0
  UNION
  SELECT id, target, source, reverse_cost
  FROM edges WHERE cost < 0$$);
 seq | sorted_v
-----+----------
   1 |        1
   2 |        5
   3 |        2
   4 |        4
   5 |        3
   6 |       13
   7 |       14
   8 |       15
   9 |       10
  10 |        6
  11 |        7
  12 |        8
  13 |        9
  14 |       11
  15 |       16
  16 |       12
  17 |       17
(17 rows)

参数

参数	类型	描述
Edges SQL	TEXT	Edges SQL 如下所述。

内部查询

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

结果列

Returns set of (seq, sorted_v)

列	类型	描述
seq	INTEGER	从 \(1\) 开始的连续数值
sorted_v	BIGINT	顶点的线性拓扑排序

其他示例

示例:

对单向段进行拓扑排序

SELECT * FROM pgr_topologicalsort(
  $$SELECT id, source, target, cost, -1 AS reverse_cost
  FROM edges WHERE cost >= 0
  UNION
  SELECT id, source, target, -1, reverse_cost
  FROM edges WHERE cost < 0$$);
 seq | sorted_v
-----+----------
   1 |        5
   2 |        2
   3 |        4
   4 |       13
   5 |       14
   6 |        1
   7 |        3
   8 |       15
   9 |       10
  10 |        6
  11 |        7
  12 |        8
  13 |        9
  14 |       11
  15 |       12
  16 |       16
  17 |       17
(17 rows)

示例:

图不是 DAG

SELECT * FROM pgr_topologicalsort(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$);
ERROR:  Graph is not DAG
HINT:
CONTEXT:  SQL function "pgr_topologicalsort" statement 1

另请参阅

• 示例数据

• https://en.wikipedia.org/wiki/Topological_sorting

索引和表格

• Index

• Search Page