pgr_lengauerTarjanDominatorTree -实验

pgr_lengauerTarjanDominatorTree — 返回所有顶点的直接支配者。

Boost 图内部

Warning

可能服务器崩溃

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

Warning

实验功能

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

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

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

  • 名称可能会改变。

  • 签名可能会改变。

  • 功能可能会改变。

  • pgTap 测试可能丢失。

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

  • 可能缺乏文档。

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

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

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

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

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

可用性

• 版本3.2.0

  • 新 实验 函数

描述

该算法计算每个顶点的 直接支配者**（称为 **idom），一旦计算出每个顶点的 idom，然后通过将每个顶点的 idom 作为其父节点，可以构建支配树。

主要特点是：

• 该算法仅适用于有向图。

• 返回值没有排序。

• 该算法返回每个顶点的* idom*。

• 如果图中不存在*根顶点*，则返回空集。

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

签名

总结

pgr_lengauerTarjanDominatorTree(Edges SQL, root vertex)

返回 (seq, vertex_id, idom) 的集合

OR EMPTY SET

示例:

具有根顶点 \(5\) 的支配树

SELECT * FROM pgr_lengauertarjandominatortree(
  $$SELECT id,source,target,cost,reverse_cost FROM edges$$,
  5) ORDER BY vertex_id;
 seq | vertex_id | idom
-----+-----------+------
   1 |         1 |    2
   9 |         2 |    0
   2 |         3 |    3
  10 |         4 |    0
  17 |         5 |    0
   4 |         6 |   17
   3 |         7 |    4
   7 |         8 |    3
  11 |         9 |    7
   5 |        10 |   16
   6 |        11 |    3
   8 |        12 |    3
  12 |        13 |    0
  13 |        14 |    0
  16 |        15 |   15
  15 |        16 |    3
  14 |        17 |    3
(17 rows)

参数

列	类型	描述
Edges SQL	TEXT	SQL 查询如上所述。
root vertex	BIGINT	起始顶点的标识符。

内部查询

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, vertex_id, idom)

列	类型	描述
seq	INTEGER	从 1 开始的顺序值。
vertex_id	BIGINT	顶点的标识符。
idom	BIGINT	顶点的直接支配者。

其他示例

示例:

另一个组件的支配树。

SELECT * FROM pgr_lengauertarjandominatortree(
  $$SELECT id,source,target,cost,reverse_cost FROM edges$$,
  13) ORDER BY vertex_id;
 seq | vertex_id | idom
-----+-----------+------
   1 |         1 |    0
   9 |         2 |    0
   2 |         3 |    0
  10 |         4 |    0
  17 |         5 |    0
   4 |         6 |    0
   3 |         7 |    0
   7 |         8 |    0
  11 |         9 |    0
   5 |        10 |    0
   6 |        11 |    0
   8 |        12 |    0
  12 |        13 |    0
  13 |        14 |   12
  16 |        15 |    0
  15 |        16 |    0
  14 |        17 |    0
(17 rows)

另请参阅

• 示例数据

• BOOST：Languer-Tarzan 支配树算法

• 维基百科:支配树

索引和表格

• Index

• Search Page