@cvvergara When one wants to find isochrones, then pgr_drivingDistance
obviously gives incomplete results. It gives correct results according to the definition but incomplete for a particular use case. @EPajares had many examples where he wanted to find isochrones but was using the pgr_drivingDistance
and getting incomplete results. These are the examples that my fix is going to cover.
Given that the interest is in isochrones and not in nodes that are reached in time <= drivingDistance
, I asked if the fix maybe deserves a new function name and probably a different result.
@EPajares Just a side note,
One of the biggest issues that pgRouting had when the release 2.0 had was that all the functions were done thinking on real problems, then tests were done with "real" data, and code was adjusted to fit the "real" data.
Even pgr_dijkstra, to test this, download version 2.0 compile it and run a pgr_dijkstra on the sample data for a directed graph from vertex 1 to vertex 3, if you see the sample data graph answer should be (vertex ordering) 1->2->5->6->9->4->3 but version 2.0 returns 1->2->3
pgRouting is about graphs, graphs can be for streets which I think its your "real problem", but can also be for people relationships, electricity distribution, rivers, and so many other kind of data that I can not think of.
But, in the case of driving distance This is the definition we are using:
Using the Dijkstra algorithm, extracts all the nodes that have costs less than or equal to the value distance. The edges extracted will conform to the corresponding spanning tree.
Note that its not the minimum spanning tree its a spanning tree. where the root is the starting vertex.
The important thing here is the statement "extracts all the nodes that have costs less than or equal to the value distance."
So in your testing try to find an example where results are wrong given the definition we are using. (aka it returns a node that is not less than or equal to the value distance)
Thinking of sets, here is a problem
given S = {1,2,3,4,5}
which are the numbers less than 3.2?
Answer: A = {1,2,3}
@cvvergara pgr_drivingDistance
behaves as the definition states, there are no examples showing that the behavior is different from the definition.
I believe most users use the OSM heavily discrete graph together with pgrouting.
In this case, many of the reachable points in the continuous world on the network defined by the graph will not be included in the resulting edges. #584 shows one example of a point reachable in the real world but the edge including that point is not in the result.
@EPajares needs these points and pgr_drivingDistance
is not complete for his usecase.
Given that his usecase is finding these reachable points where travel time is exactly the given drivingDistance
(points that define the isochrones map), we ask if maybe the function implementing this continuous use case deserves a different name or maybe it does not belong in the pgrouting
codebase at all.
I am thinking of edge cases: (for simplicity suppose all edges cost is 1 and undirected graph)
E = {e(v1,v2) e(v1,v3) e(v2,v3)} V= {v1,v2,v3}
pgr_drivingDistance results for a distance of 1.2:
The spanning tree is {e(v1,v2) e(v1,v3)}
The vertices within the distance {v1,v2,v3}
The edge in question is e(v2,v3)v2 ==+------+==v3
So, get the vertices that are (vertices that are leafs of the tree, 1.2 - agg_cost to get there): {(v2,0.2)(v3,0.2)}
v2 ==v5------v5==v3
Regarding the pgr_drivingDistance
before I understand the use case and I have also had the one @EPajares describes.
However, as @cvvergara describes correctly the functions is about nodes and not actually edges and according to the definiton it does what it should do.
That said, there is definitely a need for another function, that could for example extend pgr_drivingDistance
and might make a lot of people happy. ;-)
However, pgRouting is an Open Source project and so it is some sort of "do-ocracy" and every contribution or pull request will be highly appreciated.
And if that's not the case, most Open Source projects are funded in some way, and so it is the case with pgRouting.
It's not only volunteer time, so whoever needs something, consider to fund the development!
https://funding.communitybridge.org/projects/pgrouting
Back to the pgr_drivingDistance
function, it should be possible to
So it should be possible to compute, which fraction of each connected edge can be reached with the remaining cost.
It takes a bit of time to develop this function, especially to make it applicable to generic use cases, but in my opinion it's solvable.
There are two approaches (as outlined in the pdf that @EPajares put a while ago https://gitter.im/pgRouting/pgrouting?at=5ed76ad07da67d06faebe5a3). One is to get the leaves using pgr_drivingDistance and then go to all the neighbors of a leaf L by travelling partially on the edges. This means that if someone was following the shortest path and arrived at leaf L then traveling partially on the outgoing edges reaches the drivingDistance limit. This method returns the largest number of edges.
If, on the other hand, we put the partial edges in the priority queue of the dijkstra algorithm then some of these partial edges will be ignored (the edge case described at the bottom of pdf).
It depends on what the user wants.
First approach does not require changes to the algorithm and can be a postprocessing step.
Second approach cannot be achieved without directly controlling the dijkstra search loop.
I implemented the second approach https://github.com/vjeranc/pgrouting (branch partial_isochrones) and backported it to 2.6.3 (main branch). @EPajares is testing this branch.
During development I noticed that my pgr_isochrones
function is 2-35x times faster than pgr_drivingDistance
. I believe there's unintentional quadratic behavior in the Path
data structure. Speed difference increases with the average number of neighbors of each node. I guess you'd definitely want a speed improvement PR (fix in Path
).
It took me a while to be able to do some tests (running pgr_dijkstra
and using pgrouting data structures against my implementation) with simple executables (without linking to postgres libraries and libpgrouting.so) so maybe a PR reorganizing cmake build so that it's easy to just add executables with CMakeLists.txt can also be the outcome of this endeavour.
purpose make sure detachment of "current real problem" and because the code is not using a Boost function
pgr_isochrones
in this topic)pgr_isochrones
(if so applies)virtual vertex
, (that gives the exact distance used on the call of pgr_isochrones
, then executing pgr_dijkstraWithPoints
from the start_vid to the virtual vertex
will give the total aggregate cost with the same value distance
used with the call to pgr_isochrones
. (actually this same function can be used when the node is a real vertex on the graph).Remember a test is independent from the code, so to design a test first make the graph, write down the expected results.
Example
From this query:
SELECT * FROM pgr_isochrones(
'SELECT id, source, target, cost, reverse_cost FROM edge_table WHERE id > 20',
1, 2.5::FLOAT, true);
empty results are expected, because the internally generated graph is G=(E={}, V={1}) so the pgtap test would be:
SELECT is_empty($$
SELECT * FROM pgr_isochrones(
'SELECT id, source, target, cost, reverse_cost FROM edge_table WHERE id > 20',
1, 2.5::FLOAT, true)
$$);
@cvvergara Ma'am in GitHub builds, I am facing this problem: https://github.com/pgRouting/GSoC-pgRouting/pull/43/checks?check_run_id=760255460#step:3:562
Ver Cluster Port Status Owner Data directory Log file
9.5 main 5433 down postgres /var/lib/postgresql/9.5/main /var/log/postgresql/postgresql-9.5-main.log
Maybe the postgresql on port 5433 is down, so, anything which can be done to fix this, or is it just a GitHub actions problem and we shall just wait for the problem to get resolved?
I got this error in all the commits which I made yesterday; the builds on travis and appveyor are passing.
I tried re-running several times, still the problems isn't resolved.
@rajhim2 Maybe you are still facing the same problem in your pull request in the GSoC-pgRouting repository : pgRouting/GSoC-pgRouting#42
Your build is failing there, though it passed in your forked repository's branch
@cvvergara Ma'am, for the pgTAP unit tests, are we required to use the pgRouting's Sample Data (edge_table
) somehow for graphs like 2 vertices + 1 edge, or 3 vertices, or 4 vertices?
Or, for each such graph (3 vertices, 4 vertices etc), we can create a separate table and then use set_eq
to match the queries and the results?
SELECT * FROM pgr_boyerMyrvold(
'SELECT id, source, target, cost, reverse_cost
FROM edge_table WHERE id IN (15,8,16,9)'
);
id | source | target | cost | reverse_cost
----+--------+--------+-----------------------+--------------
1 | 8 | 5 | 2.96439387504748e-323 | 1
2 | 9 | 6 | 4.44659081257122e-323 | 1
3 | 15 | 9 | 5.92878775009496e-323 | 1
4 | 16 | 4 | 4.44659081257122e-323 | 1
(4 rows)
id | source | target | cost | reverse_cost
----+--------+--------+------+--------------
8 | 5 | 6 | 1 | 1
9 | 6 | 9 | 1 | 1
15 | 9 | 12 | 1 | 1
16 | 4 | 9 | 1 | 1
(4 rows)
Generating html/en documentation ...
Running Sphinx v2.4.0
loading translations [en]... done
loading pickled environment... done
building [mo]: targets for 0 po files that are out of date
building [html]: targets for 0 source files that are out of date
updating environment: 0 added, 0 changed, 0 removed
looking for now-outdated files... none found
no targets are out of date.
build succeeded.
The HTML pages are in html/en.
Built target html-en
Built target html
Built target doc
[100%] Generating API documentation with Doxygen
Error: /home/himanshu/GSoC-pgRouting/build/doxygen/html/inline_dotgraph_2.dot: syntax error in line 14 near '-'
Error: /home/himanshu/GSoC-pgRouting/build/doxygen/html/inline_dotgraph_2.dot: syntax error in line 14 near '-'
Error: /home/himanshu/GSoC-pgRouting/build/doxygen/latex/inline_dotgraph_2.dot: syntax error in line 14 near '-'
Segmentation fault (core dumped)
doxygen/CMakeFiles/doxy.dir/build.make:57: recipe for target 'doxygen/CMakeFiles/doxy' failed
make[3]: *** [doxygen/CMakeFiles/doxy] Error 139
CMakeFiles/Makefile2:2563: recipe for target 'doxygen/CMakeFiles/doxy.dir/all' failed
make[2]: *** [doxygen/CMakeFiles/doxy.dir/all] Error 2
CMakeFiles/Makefile2:2570: recipe for target 'doxygen/CMakeFiles/doxy.dir/rule' failed
make[1]: *** [doxygen/CMakeFiles/doxy.dir/rule] Error 2
Makefile:593: recipe for target 'doxy' failed
make: *** [doxy] Error 2
id | source | target | cost | reverse_cost
----+--------+--------+------+--------------
1 | 1 | 1 | -1 | -1
(1 row)
id | source | target | cost | reverse_cost
----+--------+--------+------+--------------
1 | 1 | 2 | -1 | -1
2 | 2 | 1 | -1 | -1
(2 rows)
insert_edges
function which then calls the graph_add_edge
function. But the second function returns directly if both the cost and reverse_cost are negative (i.e. when the edge does not exist in the graph).
I think these lines should be removed for this:
https://github.com/pgRouting/pgrouting/blob/master/include/cpp_common/pgr_base_graph.hpp#L722
https://github.com/pgRouting/pgrouting/blob/master/include/cpp_common/pgr_base_graph.hpp#L937
https://github.com/pgRouting/pgrouting/blob/master/include/cpp_common/pgr_base_graph.hpp#L973
Then it will create both the vertices (source and target vertex, even though they are connected or not).
insert_edges
function of pgRouting (pgr_base_graph.hpp
)?
insert_edges
function defined in pgr_base_graph.hpp