Skip to content

Commit 8079ecf

Browse files
cvvergaracvvergara
committed
Standardizing pgr_binaryBreadthFirstSearch to one path result columns
1 parent bd2cff4 commit 8079ecf

6 files changed

Lines changed: 71 additions & 142 deletions

File tree

‎doc/src/migration.rst‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -81,6 +81,8 @@ types.
8181
- `Migration of single path functions`_
8282
* - .. versionchanged:: 4.0.0 :doc:`pgr_bellmanFord` [3]_
8383
- `Migration of single path functions`_
84+
* - .. versionchanged:: 4.0.0 :doc:`pgr_binaryBreadthFirstSearch` [3]_
85+
- `Migration of single path functions`_
8486
* - .. versionchanged:: 4.0.0 :doc:`pgr_dagShortestPath` [3]_
8587
- `Migration of single path functions`_
8688
* - .. versionchanged:: 4.0.0 :doc:`pgr_edwardMoore` [3]_

‎doc/traversal/pgr_binaryBreadthFirstSearch.rst‎

Lines changed: 14 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -29,15 +29,19 @@ non-negative integer, is termed as a 'binary graph'.
2929

3030
.. rubric:: Availability
3131

32-
* Version 3.2.0
32+
.. rubric:: Version 4.0.0
3333

34-
* New experimental signature:
34+
* Output columns standardized to |short-generic-result|
3535

36-
* pgr_binaryBreadthFirstSearch(Combinations)
36+
.. rubric:: Version 3.2.0
3737

38-
* Version 3.0.0
38+
* New experimental signature:
3939

40-
* New experimental function.
40+
* pgr_binaryBreadthFirstSearch(Combinations)
41+
42+
.. rubric:: Version 3.0.0
43+
44+
* New experimental function.
4145

4246
Description
4347
-------------------------------------------------------------------------------
@@ -47,7 +51,7 @@ vertices can be found using Breadth First Search in :math:`O(|E|)` in an
4751
unweighted graph, i.e. the distance is the minimal number of edges that you
4852
need to traverse from the source to another vertex. We can interpret such a
4953
graph also as a weighted graph, where every edge has the weight :math:`1`.
50-
If not alledges in graph have the same weight, that we need a more general
54+
If not all edges in graph have the same weight, that we need a more general
5155
algorithm, like Dijkstra's Algorithm which runs in :math:`O(|E|log|V|)` time.
5256

5357
However if the weights are more constrained, we can use a faster algorithm.
@@ -87,7 +91,7 @@ Signatures
8791
| pgr_binaryBreadthFirstSearch(`Edges SQL`_, **start vids**, **end vids**, [``directed``])
8892
| pgr_binaryBreadthFirstSearch(`Edges SQL`_, `Combinations SQL`_, [``directed``])
8993
90-
| Returns set of |old-generic-result|
94+
| Returns set of |short-generic-result|
9195
| OR EMPTY SET
9296
9397
**Note:** Using the :doc:`sampledata` Network as all weights are same (i.e
@@ -104,7 +108,7 @@ One to One
104108

105109
| pgr_binaryBreadthFirstSearch(`Edges SQL`_, **start vid**, **end vid**, [``directed``])
106110
107-
| Returns set of |result-1-1|
111+
| Returns set of |short-generic-result|
108112
| OR EMPTY SET
109113
110114
:Example: From vertex :math:`6` to vertex :math:`10` on a **directed** graph
@@ -124,7 +128,7 @@ One to Many
124128

125129
| pgr_binaryBreadthFirstSearch(`Edges SQL`_, **start vid**, **end vids**, [``directed``])
126130
127-
| Returns set of |result-1-m|
131+
| Returns set of |short-generic-result|
128132
| OR EMPTY SET
129133
130134
:Example: From vertex :math:`6` to vertices :math:`\{10, 17\}` on a **directed**
@@ -145,7 +149,7 @@ Many to One
145149

146150
| pgr_binaryBreadthFirstSearch(`Edges SQL`_, **start vids**, **end vid**, [``directed``])
147151
148-
| Returns set of |result-m-1|
152+
| Returns set of |short-generic-result|
149153
| OR EMPTY SET
150154
151155
:Example: From vertices :math:`\{6, 1\}` to vertex :math:`17` on a **directed**

‎docqueries/traversal/binaryBreadthFirstSearch.result‎

Lines changed: 34 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -6,52 +6,52 @@ SET
66
SELECT * FROM pgr_binaryBreadthFirstSearch(
77
'SELECT id, source, target, cost, reverse_cost from edges',
88
6, 10, true);
9-
seq | path_seq | node | edge | cost | agg_cost
10-
-----+----------+------+------+------+----------
11-
1 | 1 | 6 | 4 | 1 | 0
12-
2 | 2 | 7 | 8 | 1 | 1
13-
3 | 3 | 11 | 9 | 1 | 2
14-
4 | 4 | 16 | 16 | 1 | 3
15-
5 | 5 | 15 | 3 | 1 | 4
16-
6 | 6 | 10 | -1 | 0 | 5
9+
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
10+
-----+----------+-----------+---------+------+------+------+----------
11+
1 | 1 | 6 | 10 | 6 | 4 | 1 | 0
12+
2 | 2 | 6 | 10 | 7 | 8 | 1 | 1
13+
3 | 3 | 6 | 10 | 11 | 9 | 1 | 2
14+
4 | 4 | 6 | 10 | 16 | 16 | 1 | 3
15+
5 | 5 | 6 | 10 | 15 | 3 | 1 | 4
16+
6 | 6 | 6 | 10 | 10 | -1 | 0 | 5
1717
(6 rows)
1818

1919
/* -- q2 */
2020
SELECT * FROM pgr_binaryBreadthFirstSearch(
2121
'SELECT id, source, target, cost, reverse_cost from edges',
2222
6, ARRAY[10, 17]);
23-
seq | path_seq | end_vid | node | edge | cost | agg_cost
24-
-----+----------+---------+------+------+------+----------
25-
1 | 1 | 10 | 6 | 4 | 1 | 0
26-
2 | 2 | 10 | 7 | 8 | 1 | 1
27-
3 | 3 | 10 | 11 | 9 | 1 | 2
28-
4 | 4 | 10 | 16 | 16 | 1 | 3
29-
5 | 5 | 10 | 15 | 3 | 1 | 4
30-
6 | 6 | 10 | 10 | -1 | 0 | 5
31-
7 | 1 | 17 | 6 | 4 | 1 | 0
32-
8 | 2 | 17 | 7 | 8 | 1 | 1
33-
9 | 3 | 17 | 11 | 11 | 1 | 2
34-
10 | 4 | 17 | 12 | 13 | 1 | 3
35-
11 | 5 | 17 | 17 | -1 | 0 | 4
23+
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
24+
-----+----------+-----------+---------+------+------+------+----------
25+
1 | 1 | 6 | 10 | 6 | 4 | 1 | 0
26+
2 | 2 | 6 | 10 | 7 | 8 | 1 | 1
27+
3 | 3 | 6 | 10 | 11 | 9 | 1 | 2
28+
4 | 4 | 6 | 10 | 16 | 16 | 1 | 3
29+
5 | 5 | 6 | 10 | 15 | 3 | 1 | 4
30+
6 | 6 | 6 | 10 | 10 | -1 | 0 | 5
31+
7 | 1 | 6 | 17 | 6 | 4 | 1 | 0
32+
8 | 2 | 6 | 17 | 7 | 8 | 1 | 1
33+
9 | 3 | 6 | 17 | 11 | 11 | 1 | 2
34+
10 | 4 | 6 | 17 | 12 | 13 | 1 | 3
35+
11 | 5 | 6 | 17 | 17 | -1 | 0 | 4
3636
(11 rows)
3737

3838
/* -- q3 */
3939
SELECT * FROM pgr_binaryBreadthFirstSearch(
4040
'SELECT id, source, target, cost, reverse_cost from edges',
4141
ARRAY[6, 1], 17);
42-
seq | path_seq | start_vid | node | edge | cost | agg_cost
43-
-----+----------+-----------+------+------+------+----------
44-
1 | 1 | 1 | 1 | 6 | 1 | 0
45-
2 | 2 | 1 | 3 | 7 | 1 | 1
46-
3 | 3 | 1 | 7 | 8 | 1 | 2
47-
4 | 4 | 1 | 11 | 11 | 1 | 3
48-
5 | 5 | 1 | 12 | 13 | 1 | 4
49-
6 | 6 | 1 | 17 | -1 | 0 | 5
50-
7 | 1 | 6 | 6 | 4 | 1 | 0
51-
8 | 2 | 6 | 7 | 8 | 1 | 1
52-
9 | 3 | 6 | 11 | 11 | 1 | 2
53-
10 | 4 | 6 | 12 | 13 | 1 | 3
54-
11 | 5 | 6 | 17 | -1 | 0 | 4
42+
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
43+
-----+----------+-----------+---------+------+------+------+----------
44+
1 | 1 | 1 | 17 | 1 | 6 | 1 | 0
45+
2 | 2 | 1 | 17 | 3 | 7 | 1 | 1
46+
3 | 3 | 1 | 17 | 7 | 8 | 1 | 2
47+
4 | 4 | 1 | 17 | 11 | 11 | 1 | 3
48+
5 | 5 | 1 | 17 | 12 | 13 | 1 | 4
49+
6 | 6 | 1 | 17 | 17 | -1 | 0 | 5
50+
7 | 1 | 6 | 17 | 6 | 4 | 1 | 0
51+
8 | 2 | 6 | 17 | 7 | 8 | 1 | 1
52+
9 | 3 | 6 | 17 | 11 | 11 | 1 | 2
53+
10 | 4 | 6 | 17 | 12 | 13 | 1 | 3
54+
11 | 5 | 6 | 17 | 17 | -1 | 0 | 4
5555
(11 rows)
5656

5757
/* -- q4 */

‎pgtap/traversal/binaryBreadthFirstSearch/types_check.pg‎

Lines changed: 2 additions & 83 deletions
Original file line numberDiff line numberDiff line change
@@ -19,90 +19,9 @@ Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
1919
********************************************************************PGR-GNU*/
2020
BEGIN;
2121

22-
SELECT plan (13);
22+
SELECT CASE WHEN min_version('4.0.0') THEN plan(13) WHEN min_version('3.2.0') THEN plan(12) ELSE PLAN(10) END;
2323

24-
CREATE OR REPLACE FUNCTION types_check()
25-
RETURNS SETOF TEXT AS
26-
$BODY$
27-
BEGIN
28-
29-
RETURN QUERY
30-
SELECT has_function('pgr_binarybreadthfirstsearch');
31-
32-
RETURN QUERY SELECT has_function('pgr_binarybreadthfirstsearch', ARRAY['text','bigint','bigint','boolean']);
33-
RETURN QUERY SELECT has_function('pgr_binarybreadthfirstsearch', ARRAY['text','bigint','anyarray','boolean']);
34-
RETURN QUERY SELECT has_function('pgr_binarybreadthfirstsearch', ARRAY['text','anyarray','bigint','boolean']);
35-
RETURN QUERY SELECT has_function('pgr_binarybreadthfirstsearch', ARRAY['text','anyarray','anyarray','boolean']);
36-
37-
RETURN QUERY SELECT function_returns('pgr_binarybreadthfirstsearch', ARRAY['text','bigint','bigint','boolean'], 'setof record');
38-
RETURN QUERY SELECT function_returns('pgr_binarybreadthfirstsearch', ARRAY['text','bigint','anyarray','boolean'], 'setof record');
39-
RETURN QUERY SELECT function_returns('pgr_binarybreadthfirstsearch', ARRAY['text','anyarray','bigint','boolean'], 'setof record');
40-
RETURN QUERY SELECT function_returns('pgr_binarybreadthfirstsearch', ARRAY['text','anyarray','anyarray','boolean'], 'setof record');
41-
42-
RETURN QUERY
43-
SELECT CASE
44-
WHEN min_version('3.2.0') THEN
45-
collect_tap(
46-
has_function('pgr_binarybreadthfirstsearch', ARRAY['text','text','boolean']),
47-
function_returns('pgr_binarybreadthfirstsearch', ARRAY['text','text','boolean'], 'setof record')
48-
)
49-
ELSE
50-
skip(2, 'Combinations functiontionality new on 3.2.0')
51-
END;
52-
53-
RETURN QUERY
54-
SELECT CASE
55-
WHEN min_version('3.2.0') THEN
56-
collect_tap(
57-
58-
function_args_eq('pgr_binarybreadthfirstsearch',
59-
$$VALUES
60-
('{"","","","directed","seq","path_seq","node","edge","cost","agg_cost"}'::TEXT[]),
61-
('{"","","","directed","seq","path_seq","start_vid","node","edge","cost","agg_cost"}'::TEXT[]),
62-
('{"","","","directed","seq","path_seq","end_vid","node","edge","cost","agg_cost"}'::TEXT[]),
63-
('{"","","","directed","seq","path_seq","start_vid","end_vid","node","edge","cost","agg_cost"}'::TEXT[]),
64-
('{"","","directed","seq","path_seq","start_vid","end_vid","node","edge","cost","agg_cost"}'::TEXT[])
65-
$$
66-
),
67-
68-
function_types_eq('pgr_binarybreadthfirstsearch',
69-
$$VALUES
70-
('{text,int8,int8,bool,int4,int4,int8,int8,float8,float8}'::TEXT[]),
71-
('{text,int8,anyarray,bool,int4,int4,int8,int8,int8,float8,float8}'::TEXT[]),
72-
('{text,anyarray,int8,bool,int4,int4,int8,int8,int8,float8,float8}'::TEXT[]),
73-
('{text,anyarray,anyarray,bool,int4,int4,int8,int8,int8,int8,float8,float8}'::TEXT[]),
74-
('{text,text,bool,int4,int4,int8,int8,int8,int8,float8,float8}'::TEXT[])
75-
$$
76-
)
77-
)
78-
ELSE
79-
collect_tap(
80-
81-
function_args_eq('pgr_binarybreadthfirstsearch',
82-
$$VALUES
83-
('{"","","","directed","seq","path_seq","node","edge","cost","agg_cost"}'::TEXT[]),
84-
('{"","","","directed","seq","path_seq","start_vid","node","edge","cost","agg_cost"}'::TEXT[]),
85-
('{"","","","directed","seq","path_seq","end_vid","node","edge","cost","agg_cost"}'::TEXT[]),
86-
('{"","","","directed","seq","path_seq","start_vid","end_vid","node","edge","cost","agg_cost"}'::TEXT[])
87-
$$
88-
),
89-
90-
function_types_eq('pgr_binarybreadthfirstsearch',
91-
$$VALUES
92-
('{text,int8,int8,bool,int4,int4,int8,int8,float8,float8}'::TEXT[]),
93-
('{text,int8,anyarray,bool,int4,int4,int8,int8,int8,float8,float8}'::TEXT[]),
94-
('{text,anyarray,int8,bool,int4,int4,int8,int8,int8,float8,float8}'::TEXT[]),
95-
('{text,anyarray,anyarray,bool,int4,int4,int8,int8,int8,int8,float8,float8}'::TEXT[])
96-
$$
97-
)
98-
)
99-
END;
100-
101-
END;
102-
$BODY$
103-
LANGUAGE plpgsql;
104-
105-
SELECT types_check();
24+
SELECT single_path_types_check('pgr_binarybreadthfirstsearch', standard_v => '4.0.0');
10625

10726
SELECT * FROM finish();
10827
ROLLBACK;

‎sql/breadthFirstSearch/binaryBreadthFirstSearch.sql‎

Lines changed: 15 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@ Copyright (c) 2019 pgRouting developers
55
Mail: project@pgrouting.org
66
77
Copyright (c) 2019 Gudesa Venkata Sai Akhil
8-
Mail: gvs.akhil1997@gmail.com
8+
Mail: gvs.akhil1997 at gmail.com
99
1010
------
1111
@@ -24,9 +24,6 @@ along with this program; if not, write to the Free Software
2424
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
2525
2626
********************************************************************PGR-GNU*/
27-
---------------
28-
-- pgr_binaryBreadthFirstSearch
29-
---------------
3027

3128
-- ONE to ONE
3229
--v3.0
@@ -39,14 +36,16 @@ CREATE FUNCTION pgr_binaryBreadthFirstSearch(
3936

4037
OUT seq INTEGER,
4138
OUT path_seq INTEGER,
39+
OUT start_vid BIGINT,
40+
OUT end_vid BIGINT,
4241
OUT node BIGINT,
4342
OUT edge BIGINT,
4443
OUT cost FLOAT,
4544
OUT agg_cost FLOAT)
4645
RETURNS SETOF RECORD AS
4746
$BODY$
48-
SELECT a.seq, a.path_seq, a.node, a.edge, a.cost, a.agg_cost
49-
FROM _pgr_binaryBreadthFirstSearch(_pgr_get_statement($1), ARRAY[$2]::BIGINT[], ARRAY[$3]::BIGINT[], $4) AS a;
47+
SELECT seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost
48+
FROM _pgr_binaryBreadthFirstSearch(_pgr_get_statement($1), ARRAY[$2]::BIGINT[], ARRAY[$3]::BIGINT[], $4);
5049
$BODY$
5150
LANGUAGE sql VOLATILE STRICT;
5251

@@ -62,15 +61,16 @@ CREATE FUNCTION pgr_binaryBreadthFirstSearch(
6261

6362
OUT seq INTEGER,
6463
OUT path_seq INTEGER,
64+
OUT start_vid BIGINT,
6565
OUT end_vid BIGINT,
6666
OUT node BIGINT,
6767
OUT edge BIGINT,
6868
OUT cost FLOAT,
6969
OUT agg_cost FLOAT)
7070
RETURNS SETOF RECORD AS
7171
$BODY$
72-
SELECT a.seq, a.path_seq, a.end_vid, a.node, a.edge, a.cost, a.agg_cost
73-
FROM _pgr_binaryBreadthFirstSearch(_pgr_get_statement($1), ARRAY[$2]::BIGINT[], $3::BIGINT[], $4) AS a;
72+
SELECT seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost
73+
FROM _pgr_binaryBreadthFirstSearch(_pgr_get_statement($1), ARRAY[$2]::BIGINT[], $3::BIGINT[], $4);
7474
$BODY$
7575
LANGUAGE sql VOLATILE STRICT;
7676

@@ -87,14 +87,15 @@ CREATE FUNCTION pgr_binaryBreadthFirstSearch(
8787
OUT seq INTEGER,
8888
OUT path_seq INTEGER,
8989
OUT start_vid BIGINT,
90+
OUT end_vid BIGINT,
9091
OUT node BIGINT,
9192
OUT edge BIGINT,
9293
OUT cost FLOAT,
9394
OUT agg_cost FLOAT)
9495
RETURNS SETOF RECORD AS
9596
$BODY$
96-
SELECT a.seq, a.path_seq, a.start_vid, a.node, a.edge, a.cost, a.agg_cost
97-
FROM _pgr_binaryBreadthFirstSearch(_pgr_get_statement($1), $2::BIGINT[], ARRAY[$3]::BIGINT[], $4) AS a;
97+
SELECT seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost
98+
FROM _pgr_binaryBreadthFirstSearch(_pgr_get_statement($1), $2::BIGINT[], ARRAY[$3]::BIGINT[], $4);
9899
$BODY$
99100
LANGUAGE sql VOLATILE STRICT;
100101

@@ -118,8 +119,8 @@ CREATE FUNCTION pgr_binaryBreadthFirstSearch(
118119
OUT agg_cost FLOAT)
119120
RETURNS SETOF RECORD AS
120121
$BODY$
121-
SELECT a.seq, a.path_seq, a.start_vid, a.end_vid, a.node, a.edge, a.cost, a.agg_cost
122-
FROM _pgr_binaryBreadthFirstSearch(_pgr_get_statement($1), $2::BIGINT[], $3::BIGINT[], $4) AS a;
122+
SELECT seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost
123+
FROM _pgr_binaryBreadthFirstSearch(_pgr_get_statement($1), $2::BIGINT[], $3::BIGINT[], $4);
123124
$BODY$
124125
LANGUAGE sql VOLATILE STRICT;
125126

@@ -142,12 +143,11 @@ CREATE FUNCTION pgr_binaryBreadthFirstSearch(
142143
OUT agg_cost FLOAT)
143144
RETURNS SETOF RECORD AS
144145
$BODY$
145-
SELECT a.seq, a.path_seq, a.start_vid, a.end_vid, a.node, a.edge, a.cost, a.agg_cost
146-
FROM _pgr_binaryBreadthFirstSearch(_pgr_get_statement($1), _pgr_get_statement($2), $3) AS a;
146+
SELECT seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost
147+
FROM _pgr_binaryBreadthFirstSearch(_pgr_get_statement($1), _pgr_get_statement($2), directed);
147148
$BODY$
148149
LANGUAGE SQL VOLATILE STRICT;
149150

150-
-- COMMENTS
151151

152152
COMMENT ON FUNCTION pgr_binaryBreadthFirstSearch(TEXT, BIGINT, BIGINT, BOOLEAN)
153153
IS 'pgr_binaryBreadthFirstSearch(One to One)

‎sql/scripts/build-extension-update-files.pl‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -291,6 +291,10 @@ sub generate_upgrade_script {
291291
push @commands, drop_special_case_function("pgr_bellmanford(text,anyarray,bigint,boolean)");
292292
push @commands, drop_special_case_function("pgr_bellmanford(text,bigint,anyarray,boolean)");
293293

294+
push @commands, drop_special_case_function("pgr_binarybreadthfirstsearch(text,bigint,bigint,boolean)");
295+
push @commands, drop_special_case_function("pgr_binarybreadthfirstsearch(text,anyarray,bigint,boolean)");
296+
push @commands, drop_special_case_function("pgr_binarybreadthfirstsearch(text,bigint,anyarray,boolean)");
297+
294298
push @commands, drop_special_case_function("pgr_dagshortestpath(text,bigint,bigint)");
295299
push @commands, drop_special_case_function("pgr_dagshortestpath(text,bigint,anyarray)");
296300
push @commands, drop_special_case_function("pgr_dagshortestpath(text,anyarray,bigint)");

0 commit comments

Comments
 (0)