Skip to content

Commit 2612933

Browse files
vicennialvicennial
committed
[breadthFirstSearch] Updated function to print results beginning at depth 0
1 parent 59e6130 commit 2612933

3 files changed

Lines changed: 67 additions & 64 deletions

File tree

‎doc/queries/doc-pgr_breadthFirstSearch.queries‎

Lines changed: 33 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -9,19 +9,20 @@ SELECT * FROM pgr_breadthFirstSearch(
99
);
1010
seq | depth | start_vid | node | edge | cost | agg_cost
1111
-----+-------+-----------+------+------+------+----------
12-
1 | 1 | 2 | 1 | 1 | 1 | 1
13-
2 | 1 | 2 | 5 | 4 | 1 | 1
14-
3 | 2 | 2 | 8 | 7 | 1 | 2
15-
4 | 2 | 2 | 6 | 8 | 1 | 2
16-
5 | 2 | 2 | 10 | 10 | 1 | 2
17-
6 | 3 | 2 | 7 | 6 | 1 | 3
18-
7 | 3 | 2 | 9 | 9 | 1 | 3
19-
8 | 3 | 2 | 11 | 11 | 1 | 3
20-
9 | 3 | 2 | 13 | 14 | 1 | 3
21-
10 | 4 | 2 | 12 | 15 | 1 | 4
22-
11 | 4 | 2 | 4 | 16 | 1 | 4
23-
12 | 5 | 2 | 3 | 3 | 1 | 5
24-
(12 rows)
12+
1 | 0 | 2 | 2 | -1 | 0 | 0
13+
2 | 1 | 2 | 1 | 1 | 1 | 1
14+
3 | 1 | 2 | 5 | 4 | 1 | 1
15+
4 | 2 | 2 | 8 | 7 | 1 | 2
16+
5 | 2 | 2 | 6 | 8 | 1 | 2
17+
6 | 2 | 2 | 10 | 10 | 1 | 2
18+
7 | 3 | 2 | 7 | 6 | 1 | 3
19+
8 | 3 | 2 | 9 | 9 | 1 | 3
20+
9 | 3 | 2 | 11 | 11 | 1 | 3
21+
10 | 3 | 2 | 13 | 14 | 1 | 3
22+
11 | 4 | 2 | 12 | 15 | 1 | 4
23+
12 | 4 | 2 | 4 | 16 | 1 | 4
24+
13 | 5 | 2 | 3 | 3 | 1 | 5
25+
(13 rows)
2526

2627
--q2
2728
SELECT * FROM pgr_breadthFirstSearch(
@@ -30,23 +31,25 @@ SELECT * FROM pgr_breadthFirstSearch(
3031
);
3132
seq | depth | start_vid | node | edge | cost | agg_cost
3233
-----+-------+-----------+------+------+------+----------
33-
1 | 1 | 2 | 1 | 1 | 1 | 1
34-
2 | 1 | 2 | 5 | 4 | 1 | 1
35-
3 | 2 | 2 | 8 | 7 | 1 | 2
36-
4 | 2 | 2 | 6 | 8 | 1 | 2
37-
5 | 2 | 2 | 10 | 10 | 1 | 2
38-
6 | 3 | 2 | 7 | 6 | 1 | 3
39-
7 | 3 | 2 | 9 | 9 | 1 | 3
40-
8 | 3 | 2 | 11 | 11 | 1 | 3
41-
9 | 3 | 2 | 13 | 14 | 1 | 3
42-
10 | 1 | 13 | 10 | 14 | 1 | 1
43-
11 | 2 | 13 | 5 | 10 | 1 | 2
44-
12 | 2 | 13 | 11 | 12 | 1 | 2
45-
13 | 3 | 13 | 2 | 4 | 1 | 3
46-
14 | 3 | 13 | 8 | 7 | 1 | 3
47-
15 | 3 | 13 | 6 | 8 | 1 | 3
48-
16 | 3 | 13 | 12 | 13 | 1 | 3
49-
(16 rows)
34+
1 | 0 | 2 | 2 | -1 | 0 | 0
35+
2 | 1 | 2 | 1 | 1 | 1 | 1
36+
3 | 1 | 2 | 5 | 4 | 1 | 1
37+
4 | 2 | 2 | 8 | 7 | 1 | 2
38+
5 | 2 | 2 | 6 | 8 | 1 | 2
39+
6 | 2 | 2 | 10 | 10 | 1 | 2
40+
7 | 3 | 2 | 7 | 6 | 1 | 3
41+
8 | 3 | 2 | 9 | 9 | 1 | 3
42+
9 | 3 | 2 | 11 | 11 | 1 | 3
43+
10 | 3 | 2 | 13 | 14 | 1 | 3
44+
11 | 0 | 13 | 13 | -1 | 0 | 0
45+
12 | 1 | 13 | 10 | 14 | 1 | 1
46+
13 | 2 | 13 | 5 | 10 | 1 | 2
47+
14 | 2 | 13 | 11 | 12 | 1 | 2
48+
15 | 3 | 13 | 2 | 4 | 1 | 3
49+
16 | 3 | 13 | 8 | 7 | 1 | 3
50+
17 | 3 | 13 | 6 | 8 | 1 | 3
51+
18 | 3 | 13 | 12 | 13 | 1 | 3
52+
(18 rows)
5053

5154
--q3
5255
SELECT * FROM pgr_breadthFirstSearch(

‎include/breadthFirstSearch/pgr_breadthFirstSearch.hpp‎

Lines changed: 1 addition & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -57,6 +57,7 @@ class Pgr_breadthFirstSearch
5757
for (auto source : start_vertex)
5858
{
5959
std::vector<E> visited_order;
60+
results.push_back({source, 0, source, -1, 0.0, 0.0});
6061
if (graph.has_vertex(source))
6162
{
6263
boost::breadth_first_search(graph.graph,
@@ -66,10 +67,6 @@ class Pgr_breadthFirstSearch
6667
auto single_source_results = get_results(visited_order, source, depth, graph);
6768
results.insert(results.end(), single_source_results.begin(), single_source_results.end());
6869
}
69-
else
70-
{
71-
results.push_back({source, 0, source, -1, 0.0, 0.0});
72-
}
7370
}
7471
return results;
7572
}

‎test/breadthFirstSearch/doc-pgr_breadthFirstSearch.result‎

Lines changed: 33 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -9,19 +9,20 @@ SELECT * FROM pgr_breadthFirstSearch(
99
);
1010
seq | depth | start_vid | node | edge | cost | agg_cost
1111
-----+-------+-----------+------+------+------+----------
12-
1 | 1 | 2 | 1 | 1 | 1 | 1
13-
2 | 1 | 2 | 5 | 4 | 1 | 1
14-
3 | 2 | 2 | 8 | 7 | 1 | 2
15-
4 | 2 | 2 | 6 | 8 | 1 | 2
16-
5 | 2 | 2 | 10 | 10 | 1 | 2
17-
6 | 3 | 2 | 7 | 6 | 1 | 3
18-
7 | 3 | 2 | 9 | 9 | 1 | 3
19-
8 | 3 | 2 | 11 | 11 | 1 | 3
20-
9 | 3 | 2 | 13 | 14 | 1 | 3
21-
10 | 4 | 2 | 12 | 15 | 1 | 4
22-
11 | 4 | 2 | 4 | 16 | 1 | 4
23-
12 | 5 | 2 | 3 | 3 | 1 | 5
24-
(12 rows)
12+
1 | 0 | 2 | 2 | -1 | 0 | 0
13+
2 | 1 | 2 | 1 | 1 | 1 | 1
14+
3 | 1 | 2 | 5 | 4 | 1 | 1
15+
4 | 2 | 2 | 8 | 7 | 1 | 2
16+
5 | 2 | 2 | 6 | 8 | 1 | 2
17+
6 | 2 | 2 | 10 | 10 | 1 | 2
18+
7 | 3 | 2 | 7 | 6 | 1 | 3
19+
8 | 3 | 2 | 9 | 9 | 1 | 3
20+
9 | 3 | 2 | 11 | 11 | 1 | 3
21+
10 | 3 | 2 | 13 | 14 | 1 | 3
22+
11 | 4 | 2 | 12 | 15 | 1 | 4
23+
12 | 4 | 2 | 4 | 16 | 1 | 4
24+
13 | 5 | 2 | 3 | 3 | 1 | 5
25+
(13 rows)
2526

2627
--q2
2728
SELECT * FROM pgr_breadthFirstSearch(
@@ -30,23 +31,25 @@ SELECT * FROM pgr_breadthFirstSearch(
3031
);
3132
seq | depth | start_vid | node | edge | cost | agg_cost
3233
-----+-------+-----------+------+------+------+----------
33-
1 | 1 | 2 | 1 | 1 | 1 | 1
34-
2 | 1 | 2 | 5 | 4 | 1 | 1
35-
3 | 2 | 2 | 8 | 7 | 1 | 2
36-
4 | 2 | 2 | 6 | 8 | 1 | 2
37-
5 | 2 | 2 | 10 | 10 | 1 | 2
38-
6 | 3 | 2 | 7 | 6 | 1 | 3
39-
7 | 3 | 2 | 9 | 9 | 1 | 3
40-
8 | 3 | 2 | 11 | 11 | 1 | 3
41-
9 | 3 | 2 | 13 | 14 | 1 | 3
42-
10 | 1 | 13 | 10 | 14 | 1 | 1
43-
11 | 2 | 13 | 5 | 10 | 1 | 2
44-
12 | 2 | 13 | 11 | 12 | 1 | 2
45-
13 | 3 | 13 | 2 | 4 | 1 | 3
46-
14 | 3 | 13 | 8 | 7 | 1 | 3
47-
15 | 3 | 13 | 6 | 8 | 1 | 3
48-
16 | 3 | 13 | 12 | 13 | 1 | 3
49-
(16 rows)
34+
1 | 0 | 2 | 2 | -1 | 0 | 0
35+
2 | 1 | 2 | 1 | 1 | 1 | 1
36+
3 | 1 | 2 | 5 | 4 | 1 | 1
37+
4 | 2 | 2 | 8 | 7 | 1 | 2
38+
5 | 2 | 2 | 6 | 8 | 1 | 2
39+
6 | 2 | 2 | 10 | 10 | 1 | 2
40+
7 | 3 | 2 | 7 | 6 | 1 | 3
41+
8 | 3 | 2 | 9 | 9 | 1 | 3
42+
9 | 3 | 2 | 11 | 11 | 1 | 3
43+
10 | 3 | 2 | 13 | 14 | 1 | 3
44+
11 | 0 | 13 | 13 | -1 | 0 | 0
45+
12 | 1 | 13 | 10 | 14 | 1 | 1
46+
13 | 2 | 13 | 5 | 10 | 1 | 2
47+
14 | 2 | 13 | 11 | 12 | 1 | 2
48+
15 | 3 | 13 | 2 | 4 | 1 | 3
49+
16 | 3 | 13 | 8 | 7 | 1 | 3
50+
17 | 3 | 13 | 6 | 8 | 1 | 3
51+
18 | 3 | 13 | 12 | 13 | 1 | 3
52+
(18 rows)
5053

5154
--q3
5255
SELECT * FROM pgr_breadthFirstSearch(

0 commit comments

Comments
 (0)