pgr_hawickCircuits - 实验¶
pgr_hawickCircuits — 使用 Hawick 回路算法返回回路列表。
Warning
可能服务器崩溃
这些功能可能会导致服务器崩溃
Warning
实验功能
它们不是当前版本的正式版本。
它们可能不会正式成为下一个版本的一部分：
这些函数可能不使用 ANY-INTEGER 和 ANY-NUMERICAL
名称可能会改变。
签名可能会改变。
功能可能会改变。
pgTap 测试可能丢失。
可能需要 c/c++编码。
可能缺乏文档。
文档（如果有）可能需要重写。
可能需要自动生成文档示例。
可能需要社区的大量反馈。
可能取决于 pgRouting 的拟议功能
可能依赖于 pgRouting 的已弃用函数
可用性
版本 3.4.0
新 实验性 签名：
pgr_hawickCircuits
描述¶
Hawick Circuit 算法由 Ken Hawick 和 Health A. James 于 2008 年发表。 该算法解决了图中电路的检测和枚举问题。 它能够在具有有向弧、多弧和自弧的图中进行电路枚举，并具有内存高效和高性能的实现。 它是寻找有向图所有基本电路的约翰逊算法的扩展。
Boost Graph Library 中定义了 2 个变体。 在这里，我们只实现了第二个，因为它服务于最合适和最实用的用例。 在这个变体中，我们在过滤掉由平行边缘引起的电路后得到电路。 当您想要计算数量时，并行边缘电路有更多用例。 也许将来我们也会实现这种变化。
主要特点是：
该算法实现仅适用于有向图
这是对于电路枚举的一种格式，基于Johnson的算法。
该算法输出图中存在的不同电路。
时间复杂度： \(O((V + E) (c + 1))\)
其中 \(|E|\) 是图中的边数、
\(|V|\) 是图中的顶点数。
\(|c|\) 是图中的电路数量。
签名¶
总结
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost) 的集合- 示例:
pgRouting 示例数据 中存在的电路
SELECT * FROM pgr_hawickCircuits(
'SELECT id, source, target, cost, reverse_cost FROM edges'
);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 0 | 1 | 1 | 1 | 6 | 1 | 0
2 | 1 | 1 | 1 | 1 | 3 | 6 | 1 | 1
3 | 1 | 2 | 1 | 1 | 1 | -1 | 0 | 2
4 | 2 | 0 | 3 | 3 | 3 | 7 | 1 | 0
5 | 2 | 1 | 3 | 3 | 7 | 7 | 1 | 1
6 | 2 | 2 | 3 | 3 | 3 | -1 | 0 | 2
7 | 3 | 0 | 7 | 7 | 7 | 4 | 1 | 0
8 | 3 | 1 | 7 | 7 | 6 | 4 | 1 | 1
9 | 3 | 2 | 7 | 7 | 7 | -1 | 0 | 2
10 | 4 | 0 | 7 | 7 | 7 | 8 | 1 | 0
11 | 4 | 1 | 7 | 7 | 11 | 8 | 1 | 1
12 | 4 | 2 | 7 | 7 | 7 | -1 | 0 | 2
13 | 5 | 0 | 7 | 7 | 7 | 8 | 1 | 0
14 | 5 | 1 | 7 | 7 | 11 | 11 | 1 | 1
15 | 5 | 2 | 7 | 7 | 12 | 13 | 1 | 2
16 | 5 | 3 | 7 | 7 | 17 | 15 | 1 | 3
17 | 5 | 4 | 7 | 7 | 16 | 16 | 1 | 4
18 | 5 | 5 | 7 | 7 | 15 | 3 | 1 | 5
19 | 5 | 6 | 7 | 7 | 10 | 2 | 1 | 6
20 | 5 | 7 | 7 | 7 | 6 | 4 | 1 | 7
21 | 5 | 8 | 7 | 7 | 7 | -1 | 0 | 8
22 | 6 | 0 | 7 | 7 | 7 | 8 | 1 | 0
23 | 6 | 1 | 7 | 7 | 11 | 9 | 1 | 1
24 | 6 | 2 | 7 | 7 | 16 | 16 | 1 | 2
25 | 6 | 3 | 7 | 7 | 15 | 3 | 1 | 3
26 | 6 | 4 | 7 | 7 | 10 | 2 | 1 | 4
27 | 6 | 5 | 7 | 7 | 6 | 4 | 1 | 5
28 | 6 | 6 | 7 | 7 | 7 | -1 | 0 | 6
29 | 7 | 0 | 7 | 7 | 7 | 10 | 1 | 0
30 | 7 | 1 | 7 | 7 | 8 | 10 | 1 | 1
31 | 7 | 2 | 7 | 7 | 7 | -1 | 0 | 2
32 | 8 | 0 | 7 | 7 | 7 | 10 | 1 | 0
33 | 8 | 1 | 7 | 7 | 8 | 12 | 1 | 1
34 | 8 | 2 | 7 | 7 | 12 | 13 | 1 | 2
35 | 8 | 3 | 7 | 7 | 17 | 15 | 1 | 3
36 | 8 | 4 | 7 | 7 | 16 | 9 | 1 | 4
37 | 8 | 5 | 7 | 7 | 11 | 8 | 1 | 5
38 | 8 | 6 | 7 | 7 | 7 | -1 | 0 | 6
39 | 9 | 0 | 7 | 7 | 7 | 10 | 1 | 0
40 | 9 | 1 | 7 | 7 | 8 | 12 | 1 | 1
41 | 9 | 2 | 7 | 7 | 12 | 13 | 1 | 2
42 | 9 | 3 | 7 | 7 | 17 | 15 | 1 | 3
43 | 9 | 4 | 7 | 7 | 16 | 16 | 1 | 4
44 | 9 | 5 | 7 | 7 | 15 | 3 | 1 | 5
45 | 9 | 6 | 7 | 7 | 10 | 2 | 1 | 6
46 | 9 | 7 | 7 | 7 | 6 | 4 | 1 | 7
47 | 9 | 8 | 7 | 7 | 7 | -1 | 0 | 8
48 | 10 | 0 | 7 | 7 | 7 | 10 | 1 | 0
49 | 10 | 1 | 7 | 7 | 8 | 12 | 1 | 1
50 | 10 | 2 | 7 | 7 | 12 | 13 | 1 | 2
51 | 10 | 3 | 7 | 7 | 17 | 15 | 1 | 3
52 | 10 | 4 | 7 | 7 | 16 | 16 | 1 | 4
53 | 10 | 5 | 7 | 7 | 15 | 3 | 1 | 5
54 | 10 | 6 | 7 | 7 | 10 | 5 | 1 | 6
55 | 10 | 7 | 7 | 7 | 11 | 8 | 1 | 7
56 | 10 | 8 | 7 | 7 | 7 | -1 | 0 | 8
57 | 11 | 0 | 6 | 6 | 6 | 1 | 1 | 0
58 | 11 | 1 | 6 | 6 | 5 | 1 | 1 | 1
59 | 11 | 2 | 6 | 6 | 6 | -1 | 0 | 2
60 | 12 | 0 | 10 | 10 | 10 | 5 | 1 | 0
61 | 12 | 1 | 10 | 10 | 11 | 11 | 1 | 1
62 | 12 | 2 | 10 | 10 | 12 | 13 | 1 | 2
63 | 12 | 3 | 10 | 10 | 17 | 15 | 1 | 3
64 | 12 | 4 | 10 | 10 | 16 | 16 | 1 | 4
65 | 12 | 5 | 10 | 10 | 15 | 3 | 1 | 5
66 | 12 | 6 | 10 | 10 | 10 | -1 | 0 | 6
67 | 13 | 0 | 10 | 10 | 10 | 5 | 1 | 0
68 | 13 | 1 | 10 | 10 | 11 | 9 | 1 | 1
69 | 13 | 2 | 10 | 10 | 16 | 16 | 1 | 2
70 | 13 | 3 | 10 | 10 | 15 | 3 | 1 | 3
71 | 13 | 4 | 10 | 10 | 10 | -1 | 0 | 4
72 | 14 | 0 | 11 | 11 | 11 | 11 | 1 | 0
73 | 14 | 1 | 11 | 11 | 12 | 13 | 1 | 1
74 | 14 | 2 | 11 | 11 | 17 | 15 | 1 | 2
75 | 14 | 3 | 11 | 11 | 16 | 9 | 1 | 3
76 | 14 | 4 | 11 | 11 | 11 | -1 | 0 | 4
77 | 15 | 0 | 11 | 11 | 11 | 9 | 1 | 0
78 | 15 | 1 | 11 | 11 | 16 | 9 | 1 | 1
79 | 15 | 2 | 11 | 11 | 11 | -1 | 0 | 2
80 | 16 | 0 | 8 | 8 | 8 | 14 | 1 | 0
81 | 16 | 1 | 8 | 8 | 9 | 14 | 1 | 1
82 | 16 | 2 | 8 | 8 | 8 | -1 | 0 | 2
83 | 17 | 0 | 2 | 2 | 2 | 17 | 1 | 0
84 | 17 | 1 | 2 | 2 | 4 | 17 | 1 | 1
85 | 17 | 2 | 2 | 2 | 2 | -1 | 0 | 2
86 | 18 | 0 | 13 | 13 | 13 | 18 | 1 | 0
87 | 18 | 1 | 13 | 13 | 14 | 18 | 1 | 1
88 | 18 | 2 | 13 | 13 | 13 | -1 | 0 | 2
89 | 19 | 0 | 17 | 17 | 17 | 15 | 1 | 0
90 | 19 | 1 | 17 | 17 | 16 | 15 | 1 | 1
91 | 19 | 2 | 17 | 17 | 17 | -1 | 0 | 2
92 | 20 | 0 | 16 | 16 | 16 | 16 | 1 | 0
93 | 20 | 1 | 16 | 16 | 15 | 16 | 1 | 1
94 | 20 | 2 | 16 | 16 | 16 | -1 | 0 | 2
(94 rows)
参数¶
参数 |
类型 |
默认 |
描述 |
|---|---|---|---|
|
Edges SQL 如下所述。 |
可选参数¶
列 |
类型 |
默认 |
描述 |
|---|---|---|---|
|
|
|
|
内部查询¶
Edges SQL¶
列 |
类型 |
默认 |
描述 |
|---|---|---|---|
|
ANY-INTEGER |
边的第一个端点顶点的标识符。 |
|
|
ANY-INTEGER |
边的第二个端点顶点的标识符。 |
|
|
ANY-NUMERICAL |
边( |
|
|
ANY-NUMERICAL |
-1 |
边(
|
其中：
- ANY-INTEGER:
SMALLINT,INTEGER,BIGINT- ANY-NUMERICAL:
SMALLINT,INTEGER,BIGINT,REAL,FLOAT
结果列¶
列 |
类型 |
描述 |
|---|---|---|
|
|
从 |
|
|
电路id从 |
|
|
路径中的相对位置。 路径开头的值为 |
|
|
电路起始顶点的标识符。 |
|
|
电路结束顶点的标识符。 |
|
|
从 vid 到下一个 vid 的路径中节点的标识符。 |
|
|
用于从路径序列中的 |
|
|
从使用 |
|
|
从 |
另请参阅¶
索引和表格