pgr_edgeDisjointPaths¶
pgr_edgeDisjointPaths - 计算两组顶点之间的边不相交路径。
Boost 图内部¶
可用性
版本3.2.0
新的 拟议 函数：
pgr_edgeDisjointPaths(组合)
版本3.0.0
官方 函数
版本2.5.0
拟议 函数
版本2.3.0
新的 实验 函数
描述¶
计算两组顶点之间的边不相交路径。 利用底层最大流量算法来计算路径。
- 主要特点是：
计算任意两组顶点之间的边相交路径。
当源和目标相同或无法到达时，返回 EMPTY SET。
图可以是有向或无向的。
使用 pgr_boykovKolmogorov 计算路径。
签名¶
总结
pgr_edgeDisjointPaths(Edges SQL, start vid, end vid, [
directed])pgr_edgeDisjointPaths(Edges SQL, start vid, end vids, [
directed])pgr_edgeDisjointPaths(Edges SQL, start vid, end vid, [
directed])pgr_edgeDisjointPaths(Edges SQL, start vids, end vids, [
directed])Returns set of
(seq, path_id, path_seq, [start_vid,] [end_vid,] node, edge, cost, agg_cost)OR EMPTY SET
一对一¶
pgr_edgeDisjointPaths(Edges SQL, start vid, end vid, [
directed])返回
(seq, path_id, path_seq, node, edge, cost, agg_cost) 的集合OR EMPTY SET
- 示例:
从顶点 \(11\) 到顶点 \(12\)
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost
FROM edges',
11, 12);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 | 1 | 1 | 11 | 8 | 1 | 0
2 | 1 | 2 | 7 | 10 | 1 | 1
3 | 1 | 3 | 8 | 12 | 1 | 2
4 | 1 | 4 | 12 | -1 | 0 | 3
5 | 2 | 1 | 11 | 11 | 1 | 0
6 | 2 | 2 | 12 | -1 | 0 | 1
(6 rows)
一对多¶
pgr_edgeDisjointPaths(Edges SQL, start vid, end vids, [
directed])返回|result-disjoint-1-m|的集合
OR EMPTY SET
- 示例:
从顶点 \(11\) 到顶点 \(\{5, 10, 12\}\)
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost
FROM edges',
11, ARRAY[5, 10, 12]);
seq | path_id | path_seq | end_vid | node | edge | cost | agg_cost
-----+---------+----------+---------+------+------+------+----------
1 | 1 | 1 | 5 | 11 | 8 | 1 | 0
2 | 1 | 2 | 5 | 7 | 4 | 1 | 1
3 | 1 | 3 | 5 | 6 | 1 | 1 | 2
4 | 1 | 4 | 5 | 5 | -1 | 0 | 3
5 | 2 | 1 | 10 | 11 | 9 | 1 | 0
6 | 2 | 2 | 10 | 16 | 16 | 1 | 1
7 | 2 | 3 | 10 | 15 | 3 | 1 | 2
8 | 2 | 4 | 10 | 10 | -1 | 0 | 3
9 | 3 | 1 | 12 | 11 | 8 | 1 | 0
10 | 3 | 2 | 12 | 7 | 10 | 1 | 1
11 | 3 | 3 | 12 | 8 | 12 | 1 | 2
12 | 3 | 4 | 12 | 12 | -1 | 0 | 3
13 | 4 | 1 | 12 | 11 | 11 | 1 | 0
14 | 4 | 2 | 12 | 12 | -1 | 0 | 1
(14 rows)
多对一¶
pgr_edgeDisjointPaths(Edges SQL, start vid, end vid, [
directed])Returns set of
(seq, path_id, path_seq, start_vid, node, edge, cost, agg_cost)OR EMPTY SET
- 示例:
从顶点 \(\{11, 3, 17\}\) 到顶点 \(12\)
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost
FROM edges',
ARRAY[11, 3, 17], 12);
seq | path_id | path_seq | start_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+------+------+------+----------
1 | 1 | 1 | 3 | 3 | 7 | 1 | 0
2 | 1 | 2 | 3 | 7 | 8 | 1 | 1
3 | 1 | 3 | 3 | 11 | 11 | 1 | 2
4 | 1 | 4 | 3 | 12 | -1 | 0 | 3
5 | 2 | 1 | 11 | 11 | 8 | 1 | 0
6 | 2 | 2 | 11 | 7 | 10 | 1 | 1
7 | 2 | 3 | 11 | 8 | 12 | 1 | 2
8 | 2 | 4 | 11 | 12 | -1 | 0 | 3
9 | 3 | 1 | 11 | 11 | 11 | 1 | 0
10 | 3 | 2 | 11 | 12 | -1 | 0 | 1
11 | 4 | 1 | 17 | 17 | 15 | 1 | 0
12 | 4 | 2 | 17 | 16 | 9 | 1 | 1
13 | 4 | 3 | 17 | 11 | 11 | 1 | 2
14 | 4 | 4 | 17 | 12 | -1 | 0 | 3
(14 rows)
多对多¶
pgr_edgeDisjointPaths(Edges SQL, start vids, end vids, [
directed])返回|result-disjoint-m-m|的集合
OR EMPTY SET
- 示例:
从顶点 \(\{11, 3, 17\}\) 到顶点 \(\{5, 10, 12\}\)
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost
FROM edges',
ARRAY[11, 3, 17], ARRAY[5, 10, 12]);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 3 | 5 | 3 | 7 | 1 | 0
2 | 1 | 2 | 3 | 5 | 7 | 4 | 1 | 1
3 | 1 | 3 | 3 | 5 | 6 | 1 | 1 | 2
4 | 1 | 4 | 3 | 5 | 5 | -1 | 0 | 3
5 | 2 | 1 | 3 | 10 | 3 | 7 | 1 | 0
6 | 2 | 2 | 3 | 10 | 7 | 8 | 1 | 1
7 | 2 | 3 | 3 | 10 | 11 | 9 | 1 | 2
8 | 2 | 4 | 3 | 10 | 16 | 16 | 1 | 3
9 | 2 | 5 | 3 | 10 | 15 | 3 | 1 | 4
10 | 2 | 6 | 3 | 10 | 10 | -1 | 0 | 5
11 | 3 | 1 | 3 | 12 | 3 | 7 | 1 | 0
12 | 3 | 2 | 3 | 12 | 7 | 8 | 1 | 1
13 | 3 | 3 | 3 | 12 | 11 | 11 | 1 | 2
14 | 3 | 4 | 3 | 12 | 12 | -1 | 0 | 3
15 | 4 | 1 | 11 | 5 | 11 | 8 | 1 | 0
16 | 4 | 2 | 11 | 5 | 7 | 4 | 1 | 1
17 | 4 | 3 | 11 | 5 | 6 | 1 | 1 | 2
18 | 4 | 4 | 11 | 5 | 5 | -1 | 0 | 3
19 | 5 | 1 | 11 | 10 | 11 | 9 | 1 | 0
20 | 5 | 2 | 11 | 10 | 16 | 16 | 1 | 1
21 | 5 | 3 | 11 | 10 | 15 | 3 | 1 | 2
22 | 5 | 4 | 11 | 10 | 10 | -1 | 0 | 3
23 | 6 | 1 | 11 | 12 | 11 | 8 | 1 | 0
24 | 6 | 2 | 11 | 12 | 7 | 10 | 1 | 1
25 | 6 | 3 | 11 | 12 | 8 | 12 | 1 | 2
26 | 6 | 4 | 11 | 12 | 12 | -1 | 0 | 3
27 | 7 | 1 | 11 | 12 | 11 | 11 | 1 | 0
28 | 7 | 2 | 11 | 12 | 12 | -1 | 0 | 1
29 | 8 | 1 | 17 | 5 | 17 | 15 | 1 | 0
30 | 8 | 2 | 17 | 5 | 16 | 16 | 1 | 1
31 | 8 | 3 | 17 | 5 | 15 | 3 | 1 | 2
32 | 8 | 4 | 17 | 5 | 10 | 2 | 1 | 3
33 | 8 | 5 | 17 | 5 | 6 | 1 | 1 | 4
34 | 8 | 6 | 17 | 5 | 5 | -1 | 0 | 5
35 | 9 | 1 | 17 | 10 | 17 | 15 | 1 | 0
36 | 9 | 2 | 17 | 10 | 16 | 16 | 1 | 1
37 | 9 | 3 | 17 | 10 | 15 | 3 | 1 | 2
38 | 9 | 4 | 17 | 10 | 10 | -1 | 0 | 3
39 | 10 | 1 | 17 | 12 | 17 | 15 | 1 | 0
40 | 10 | 2 | 17 | 12 | 16 | 9 | 1 | 1
41 | 10 | 3 | 17 | 12 | 11 | 11 | 1 | 2
42 | 10 | 4 | 17 | 12 | 12 | -1 | 0 | 3
(42 rows)
组合¶
返回|result-disjoint-m-m|的集合
OR EMPTY SET
- 示例:
使用组合表，相当于计算无向图上从顶点 \(\{5, 6\}\) 到顶点 \(\{10, 15, 14\}\) 的结果。
组合表：
SELECT source, target FROM combinations
WHERE target NOT IN (5, 6);
source | target
--------+--------
5 | 10
6 | 15
6 | 14
(3 rows)
查询：
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost
FROM edges',
'SELECT * FROM combinations WHERE target NOT IN (5, 6)',
directed => false);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 5 | 10 | 5 | 1 | 1 | 0
2 | 1 | 2 | 5 | 10 | 6 | 2 | -1 | 1
3 | 1 | 3 | 5 | 10 | 10 | -1 | 0 | 0
4 | 2 | 1 | 6 | 15 | 6 | 4 | 1 | 0
5 | 2 | 2 | 6 | 15 | 7 | 8 | 1 | 1
6 | 2 | 3 | 6 | 15 | 11 | 9 | 1 | 2
7 | 2 | 4 | 6 | 15 | 16 | 16 | 1 | 3
8 | 2 | 5 | 6 | 15 | 15 | -1 | 0 | 4
9 | 3 | 1 | 6 | 15 | 6 | 2 | -1 | 0
10 | 3 | 2 | 6 | 15 | 10 | 3 | -1 | -1
11 | 3 | 3 | 6 | 15 | 15 | -1 | 0 | -2
(11 rows)
参数¶
列 |
类型 |
描述 |
|---|---|---|
|
Edges SQL 如下所述 |
|
|
Combinations SQL 如下所述 |
|
start vid |
|
路径起始顶点的标识符。 |
start vids |
|
起始顶点的标识符数组。 |
end vid |
|
路径结束顶点的标识符。 |
end vids |
|
结束顶点的标识符数组。 |
可选参数¶
列 |
类型 |
默认 |
描述 |
|---|---|---|---|
|
|
|
|
内部查询¶
Edges SQL¶
列 |
类型 |
默认 |
描述 |
|---|---|---|---|
|
ANY-INTEGER |
边的标识符。 |
|
|
ANY-INTEGER |
边的第一个端点顶点的标识符。 |
|
|
ANY-INTEGER |
边的第二个端点顶点的标识符。 |
|
|
ANY-NUMERICAL |
边( |
|
|
ANY-NUMERICAL |
-1 |
边(
|
其中：
- ANY-INTEGER:
SMALLINT,INTEGER,BIGINT- ANY-NUMERICAL:
SMALLINT,INTEGER,BIGINT,REAL,FLOAT
分量 SQL¶
参数 |
类型 |
描述 |
|---|---|---|
|
ANY-INTEGER |
出发顶点的标识符。 |
|
ANY-INTEGER |
到达顶点的标识符。 |
其中：
- ANY-INTEGER:
SMALLINT,INTEGER,BIGINT
结果列¶
(seq, path_id, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost) 集合
列 |
类型 |
描述 |
|---|---|---|
|
|
从 1 开始的顺序值。 |
|
|
路径标识符。
|
|
|
路径中的相对位置。 路径开头的值为 1。 |
|
|
起始顶点的标识符。 当查询中有多个起始向量时返回。 |
|
|
结束顶点的标识符。 当查询中有多个结束顶点时返回。 |
|
|
从 |
|
|
用于从路径序列中的 |
|
|
从使用 |
|
|
从 |
其他示例¶
- 示例:
在无向图上手动分配顶点组合。
SELECT * FROM pgr_edgeDisjointPaths(
'SELECT id, source, target, cost, reverse_cost
FROM edges',
'SELECT * FROM (VALUES (5, 10), (6, 15), (6, 14)) AS t(source, target)',
directed => false);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 5 | 10 | 5 | 1 | 1 | 0
2 | 1 | 2 | 5 | 10 | 6 | 2 | -1 | 1
3 | 1 | 3 | 5 | 10 | 10 | -1 | 0 | 0
4 | 2 | 1 | 6 | 15 | 6 | 4 | 1 | 0
5 | 2 | 2 | 6 | 15 | 7 | 8 | 1 | 1
6 | 2 | 3 | 6 | 15 | 11 | 9 | 1 | 2
7 | 2 | 4 | 6 | 15 | 16 | 16 | 1 | 3
8 | 2 | 5 | 6 | 15 | 15 | -1 | 0 | 4
9 | 3 | 1 | 6 | 15 | 6 | 2 | -1 | 0
10 | 3 | 2 | 6 | 15 | 10 | 3 | -1 | -1
11 | 3 | 3 | 6 | 15 | 15 | -1 | 0 | -2
(11 rows)
另请参阅¶
索引和表格