pgr_lineGraph - 提议

pgr_lineGraph — 将给定图转换为其相应的基于边的图。

Proposed

Warning

下一版本的拟议功能。

• 它们并未正式出现在当前版本中。

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

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

  • 名字可能不会改变。（但仍然有可能改变）

  • 签名可能不会改变。（但仍然有可能改变）

  • 功能可能不会改变。（但仍然有可能改变）

  • pgTap 测试已经完成。 但可能需要更多。

  • 文档可能需要完善。

可用性

• 版本 3.7.0

  • Function promoted to proposed.

  • 适用于有向和无向图。

• 版本2.5.0

  • 新实验功能。

描述

给定一个图 $G$，其线图 $L(G)$ 是一个图，满足以下条件：

• $L(G)$ 的每个顶点代表 $G$ 的一条边。

• $L(G)$ 的两个顶点相邻，当且仅当它们对应的边在 $G$ 中共享一个共同端点时

主要特点是：

• 适用于有向和无向图。

• 结果中的 cost 和 reverse_cost 列表示边的存在性。

• 当图形是有向的，结果也是有向的。

  • 要获取完整的线图，请在双向边上使用唯一标识符 (See Additional Examples).

• 当图无向时，成本矩阵是对称的。

  • reverse_cost 始终为 $-1$。

Boost 图内部

签名

pgr_lineGraph(Edges SQL, [directed])

Returns set of (seq, source, target, cost, reverse_cost)

OR EMPTY SET

示例:

对于一个undirected graph(无向图)，其边为 :math:'{2,4,5,8}'

SELECT * FROM pgr_lineGraph(
  'SELECT id, source, target, cost, reverse_cost
  FROM edges WHERE id IN (2,4,5,8)',
  false);
 seq | source | target | cost | reverse_cost
-----+--------+--------+------+--------------
   1 |      2 |      4 |    1 |           -1
   2 |      2 |      5 |    1 |           -1
   3 |      4 |      8 |    1 |           -1
   4 |      5 |      8 |    1 |           -1
(4 rows)

参数

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

可选参数

列	类型	默认	描述
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

结果列

Returns set of (seq, source, target, cost, reverse_cost)

列	类型	描述
seq	INTEGER	从 1 开始的顺序值。 给出边的本地标识符
source	BIGINT	当前边的源顶点的标识符。 为负时：源是原始图中的反向边。
target	BIGINT	当前边的目标顶点的标识符。 为负时：目标是原始图中的反向边。
cost	FLOAT	边 (source, target)的权重。 当为负时：边(source, target)不存在，因此它不是图的一部分。
reverse_cost	FLOAT	边 (target, source)的权重。 当为负时：边(target, source)不存在，因此它不是图的一部分。

其他示例

给定以下有向图

$G(V,E)=G(\{1,2,3,4\},\{1\to 2,1\to 4,2\to 3,3\to 1,3\to 2,3\to 4,4\to 3\})$

用共享边标识符定向表示

为了简化数据库中边表的设计，边的标识符采用3位数字表示：

百位:

源点

十位:

始终为 0，用作分隔符

个位:

目标顶点

在这张图片中，

• 单向或双向箭头表示边表中的一条边（行）。

• 黄色阴影中的数字是边缘标识符。

当使用 reverse_cost 列时，两个边对会共享相同的标识符。

• 边 $2\to 3,3\to 2$ 用一条边行表示，标识符其 $id=203$ 。

• 边 $3\to 4,4\to 3$ 用一条边的行表示，标识符为 $id=304$ 。

图表的创建过程如下：

CREATE TABLE edges_shared (
    id BIGINT,
    source BIGINT,
    target BIGINT,
    cost FLOAT,
    reverse_cost FLOAT,
    geom geometry
);
CREATE TABLE
INSERT INTO edges_shared (id, source, target, cost, reverse_cost, geom) VALUES
  (102, 1, 2, 1, -1, ST_MakeLine(ST_POINT(0,  2), ST_POINT(2,  2))),
  (104, 1, 4, 1, -1, ST_MakeLine(ST_POINT(0,  2), ST_POINT(0,  0))),
  (301, 3, 1, 1, -1, ST_MakeLine(ST_POINT(2,  0), ST_POINT(0,  2))),
  (203, 2, 3, 1,  1, ST_MakeLine(ST_POINT(2,  2), ST_POINT(2,  0))),
  (304, 3, 4, 1,  1, ST_MakeLine(ST_POINT(0,  0), ST_POINT(2,  0)));

用共享边表示的有向图的线图

SELECT seq, source, target, cost, reverse_cost
FROM pgr_lineGraph(
  'SELECT id, source, target, cost, reverse_cost FROM edges_shared',
  true);
 seq | source | target | cost | reverse_cost
-----+--------+--------+------+--------------
   1 |    102 |    203 |    1 |           -1
   2 |    104 |    304 |    1 |           -1
   3 |    203 |    203 |    1 |            1
   4 |    203 |    301 |    1 |           -1
   5 |    203 |    304 |    1 |            1
   6 |    301 |    102 |    1 |           -1
   7 |    301 |    104 |    1 |           -1
   8 |    304 |    301 |    1 |           -1
   9 |    304 |    304 |    1 |            1
(9 rows)

• 结果就是一个有向图。

• 对于 $seq=4$ ，从:math:203 leftrightarrow 304 表示两条边

• 所有其他的 seq 值都代表一条边。

• cost 和 reverse_cost 的值表示边的存在。

  • 当为正数时：边缘存在。

  • 负数时：边缘不存在。

作为有向图表示，并使用唯一的边标识符

为了简化数据库中边表的设计，边的标识符采用3位数字表示：

百位:

源点

十位:

始终为 0，用作分隔符

个位:

目标顶点

在这张图片中，

• 单头箭头代表边表中的一条边（行）。

• 没有双向头箭

• 黄色阴影中的数字是边缘标识符。

两对边共享相同的结束节点，不使用 reverse_cost 列。

• 边 $2\to 3,3\to 2‘\mathrm{分}\mathrm{别}\mathrm{用}\mathrm{两}\mathrm{条}\mathrm{边}\mathrm{表}\mathrm{示}，\mathrm{边}\mathrm{标}\mathrm{识}\mathrm{符}\mathrm{为}:math:‘id=203$ 和:math:id=302 。

• 边 $3\to 4,4\to 3‘\mathrm{分}\mathrm{别}\mathrm{用}\mathrm{两}\mathrm{条}\mathrm{边}\mathrm{表}\mathrm{示}，\mathrm{边}\mathrm{标}\mathrm{识}\mathrm{符}\mathrm{为}:math:‘id=304$ 和 $id=403$ 。

图表的创建过程如下：

CREATE TABLE edges_unique (
    id BIGINT,
    source BIGINT,
    target BIGINT,
    cost FLOAT,
    geom geometry
);
CREATE TABLE
INSERT INTO edges_unique (id, source, target, cost, geom) VALUES
  (102, 1, 2, 1, ST_MakeLine(ST_POINT(0,  2), ST_POINT(2,  2))),
  (104, 1, 4, 1, ST_MakeLine(ST_POINT(0,  2), ST_POINT(0,  0))),
  (301, 3, 1, 1, ST_MakeLine(ST_POINT(2,  0), ST_POINT(0,  2))),
  (203, 2, 3, 1, ST_MakeLine(ST_POINT(2,  2), ST_POINT(2,  0))),
  (304, 3, 4, 1, ST_MakeLine(ST_POINT(2,  0), ST_POINT(0,  0))),
  (302, 3, 2, 1, ST_MakeLine(ST_POINT(2,  0), ST_POINT(2,  2))),
  (403, 4, 3, 1, ST_MakeLine(ST_POINT(0,  0), ST_POINT(2,  0)));

用唯一边表示的有向图的线图

SELECT seq, source, target, cost, reverse_cost
FROM pgr_lineGraph(
  'SELECT id, source, target, cost FROM edges_unique',
  true);
 seq | source | target | cost | reverse_cost
-----+--------+--------+------+--------------
   1 |    102 |    203 |    1 |           -1
   2 |    104 |    403 |    1 |           -1
   3 |    203 |    301 |    1 |           -1
   4 |    203 |    304 |    1 |           -1
   5 |    301 |    102 |    1 |           -1
   6 |    301 |    104 |    1 |           -1
   7 |    302 |    203 |    1 |            1
   8 |    304 |    403 |    1 |            1
   9 |    403 |    301 |    1 |           -1
  10 |    403 |    302 |    1 |           -1
(10 rows)

• 结果就是一个有向图。

• 对于 $seq=7$ 从 $203\leftrightarrow 302$ 代表两条边。

• 对于 $seq=8$ ，从 $304\leftrightarrow 403$ 表示两条边。

• 所有其他的 seq 值都代表一条边。

• cost 和 reverse_cost 的值表示边的存在。

  • 当为正数时：边缘存在。

  • 负数时：边缘不存在。

另请参阅

• 维基百科: Line Graph

• MathWorld在线数学资源: Line Graph

• 示例数据

索引和表格

• Index

• Search Page