pgr_hawickCircuits - Experimental¶
pgr_hawickCircuits — Returns the list of cirucits using hawick circuits algorithm.
Warning
Possible server crash
These functions might create a server crash
Warning
Experimental functions
They are not officially of the current release.
They likely will not be officially be part of the next release:
The functions might not make use of ANY-INTEGER and ANY-NUMERICAL
Name might change.
Signature might change.
Functionality might change.
pgTap tests might be missing.
Might need c/c++ coding.
May lack documentation.
Documentation if any might need to be rewritten.
Documentation examples might need to be automatically generated.
Might need a lot of feedback from the comunity.
Might depend on a proposed function of pgRouting
Might depend on a deprecated function of pgRouting
Availability
Version 3.4.0
New experimental signature:
pgr_hawickCircuits
Description¶
Hawick Circuit algorithm, is published in 2008 by Ken Hawick and Health A. James. This algorithm solves the problem of detecting and enumerating circuits in graphs. It is capable of circuit enumeration in graphs with directed-arcs, multiple-arcs and self-arcs with a memory efficient and high-performance im-plementation. It is an extension of Johnson’s Algorithm of finding all the elementary circuits of a directed graph.
There are 2 variations defined in the Boost Graph Library. Here, we have implemented only 2nd as it serves the most suitable and practical usecase. In this variation we get the circuits after filtering out the circuits caused by parallel edges. Parallel edge circuits have more use cases when you want to count the no. of circuits.Maybe in future, we will also implemenent this variation.
The main Characteristics are:
The algorithm implementation works only for directed graph
It is a variation of Johnson’s algorithm for circuit enumeration.
The algorithm outputs the distinct circuits present in the graph.
Time Complexity: \(O((V + E) (c + 1))\)
where \(|E|\) is the number of edges in the graph,
\(|V|\) is the number of vertices in the graph.
\(|c|\) is the number of circuts in the graph.
Signatures¶
Summary
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)- Example:
Circuits present in the pgRouting Sample Data
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)
Parameters¶
Parameter |
Type |
Default |
Description |
|---|---|---|---|
|
Edges SQL as described below. |
Optional parameters¶
Column |
Type |
Default |
Description |
|---|---|---|---|
|
|
|
|
Inner Queries¶
Edges SQL¶
Column |
Type |
Default |
Description |
|---|---|---|---|
|
ANY-INTEGER |
Identifier of the first end point vertex of the edge. |
|
|
ANY-INTEGER |
Identifier of the second end point vertex of the edge. |
|
|
ANY-NUMERICAL |
Weight of the edge ( |
|
|
ANY-NUMERICAL |
-1 |
Weight of the edge (
|
Where:
- ANY-INTEGER:
SMALLINT,INTEGER,BIGINT- ANY-NUMERICAL:
SMALLINT,INTEGER,BIGINT,REAL,FLOAT
Result columns¶
Column |
Type |
Description |
|---|---|---|
|
|
Sequential value starting from |
|
|
Id of the circuit starting from |
|
|
Relative postion in the path. Has value |
|
|
Identifier of the starting vertex of the circuit. |
|
|
Identifier of the ending vertex of the circuit. |
|
|
Identifier of the node in the path from a vid to next vid. |
|
|
Identifier of the edge used to go from |
|
|
Cost to traverse from |
|
|
Aggregate cost from |
See Also¶
Indices and tables