## Where communities thrive

• Join over 1.5M+ people
• Join over 100K+ communities
• Free without limits
##### Activity
• May 06 20:13
ziXet commented #140
• Apr 27 23:34
cvvergara commented #1883
• Apr 27 17:59
ImreSamu commented #1883
• Apr 27 17:01
ImreSamu commented #1883
• Apr 27 16:23
robe2 commented #1883
• Apr 27 15:38
robe2 opened #1883
• Apr 27 15:38
TimMcCauley commented #1769
• Apr 27 04:15
cvvergara commented #1769
• Apr 27 04:14
cvvergara unlabeled #1769
• Apr 27 04:11
cvvergara commented #1769
• Apr 27 04:06
cvvergara commented #1769
• Apr 24 09:31
sauravUppoor commented #1769
• Apr 24 02:44
cvvergara commented #1769
• Apr 24 02:31
cvvergara commented #1769
• Apr 24 02:22
cvvergara commented #1769
• Apr 24 02:21
cvvergara labeled #1769
• Apr 20 10:21
dkastl commented #1769
• Apr 20 10:03
TimMcCauley commented #1769
• Apr 19 18:31
sauravUppoor commented #1769
• Apr 17 04:11
ayushvpaliwal commented #973
Vicky Vergara
@cvvergara

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)}

Get the outgoing edges (using postgres queries)
For (v2,0.2): e(v2,v3) (cost is 1 remember)
Then you need 0.2 distance from v2 to v3
For (v3,0.2): e(v3,v2) (remember this example is for undirected)
Then you need 0.2 distance from v3 to v2
Vicky Vergara
@cvvergara
Of course the node does night exist or not so use ST_split to create a new nodes and (permanently or temporarily) breakup the segments
Then the new geometries looks like desired
if the change is done permanently, the topology needed for routing of the new geometries must be updated accordingly
So because some costs are not 1, I am writing the cost in each edge.
new E = {e(v1,v2,1) e(v1,v3,1) e(v2,v4,0.2) e(v4,v5,0.6), e(v5,v3,0.2)}
new V= {v1,v2,v3,v4,v5}
v2 ==v5------v5==v3
Elias Pajares
@EPajares
@cvvergara thanks again! You are right we are solely thinking about street networks. I guess there are many other use cases where the behavior of not including partial edges is intended. The same is also in the definition you mentioned. In fact I am currently doing the post-processing with pgr_drivingDistance results + PostgreSQL queries + PostGIS functionality as you mentioned but I am unhappy with the performance. So this was actually the reason that I thought it might make sense (at least in my naive world ;) )to directly return the "partial edges" in the pgRouting-function.
Elias Pajares
@EPajares
I know for performance there might exist other libraries but I wanted to use pgRouting because I am running calculation on extremely varying graphs. So I cannot use contraction hierarchies and managing everything in the DB is very appealing to me. Currently I am running the tests with the implementation of @vjeranc and performance is very good. I need to do more in-depth testing still but at least for my use case this implementation is very useful. But yeah I understand if it might be rejected as new feature because it is too tailored to as single problem.
Daniel Kastl
@dkastl

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

• know all connected edges from the nodes that can be reached
• know the remaining "costs" from that node

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.

vjeranc
@vjeranc

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.

Daniel Kastl
@dkastl
@vjeranc , thank you!
And sorry if I missed some conversation before at it seems.
It would be great if this could become a pull request, so it can be part of all distribution packages with the next release for example.
There were probably plenty of changes with the 3.0 release, but if you need sosme help with that, let us know!
Vicky Vergara
@cvvergara

# Topic: Requirements for the PR

purpose make sure detachment of "current real problem" and because the code is not using a Boost function

• Clear statement of the problem to be solved
• Mathematically
• Natural language
• Include the kind of graph it works with
• directed
• undirected
• if it problem is not solvable for one of those kinds, clearly state why
• Discussion of the name to be used when added to pgRouting (will use for sake of simplicity pgr_isochrones in this topic)
• User documentation including automatically generated results of example queries
• pgtap unit tests with different graphs on the created by edges_SQL (E set) where the vertices are deduced from E, +1 node given by the start_vid.
• E = {}
• E has one vertex
• E has 2 vertices and one edge
• second node is reachable from start_vid exactly
• second node is unreachable from start_vid so result is within the lone edge
• E has 3 vertices
• many combinations of possible edges that can exist with 3 vertices
• together with many combinations of reach-ability
• E has 4 vertices
• many combinations of possible edges that can exist with 4 vertices
• together with many combinations of reach-ability
• No server crash test
• Normally happens when data is NULL
• Test of persistence
• So that in the future no one accidentally removes the function, changes signature, without our knowledge
• example
• Note that compulsory are unnamed parameters and optional parameters are named parameters see RFC 3
• equivalence tests, examples:
• if the reached node is a real vertex of the graph, then executing pgr_dijkstra will give the total aggregate cost with the same value returned by the pgr_isochrones (if so applies)
• if the reached node is a node within an edge of the graph, 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).
• see example of equivalence test.

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)$$);

# end topic

Ashish Kumar
@krashish8

@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.

Himanshu Raj
@rajhim2
I was also facing the same problem yesterday. Travis and Appveyor builds were passing and other builds were failing. So I re-run that specific job which was failing and it passed. You can try Re-run Jobs for that specific job.
Ashish Kumar
@krashish8

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

Ashish Kumar
@krashish8

@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?

Daniel Kastl
@dkastl
@krashish8 , good question.
I would say that if you can reuse the existing sample data for your case, that would be best, because maintaining multiple sample networks is extra work.
If you think the current sample network is not suitable, maybe we can extend it to also cover your use case.
Himanshu Raj
@rajhim2
Can anyone help me with .hpp file code. The function is testing if an undirected graph is planar or not. If it is planar I want to simply return the rows of id, source , target, cost, reverse_cost in the result otherwise 0 rows.
Currently the .hpp code is returning incorrect output.
 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)
Himanshu Raj
@rajhim2
Whereas the correct output should be : -
 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)
Himanshu Raj
@rajhim2
Generating html/en documentation ...
Running Sphinx v2.4.0
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
This doxygen error comes at the step : Generating API documentation with Doxygen. I have installed doxygen and graphviz and pygraphviz correctly. Can anyone please explain.
Ashish Kumar
@krashish8
How can we create a graph in pgRouting with an isolated vertex, or with two isolated vertices, etc. (vertices having no degree)?
I guess this functionality should be there in pgRouting.
Since we have an edge representation of the graph, the best I can try was to represent the graph in the following way:
For one isolated vertex:
 id | source | target | cost | reverse_cost
----+--------+--------+------+--------------
1 |      1 |      1 |   -1 |           -1
(1 row)
For two isolated vertices:
 id | source | target | cost | reverse_cost
----+--------+--------+------+--------------
1 |      1 |      2 |   -1 |           -1
2 |      2 |      1 |   -1 |           -1
(2 rows)
But in both the cases, the source and target vertices were not created, and the edge was not added.
(If I checked it correctly)
In my opinion, both the source and target vertices should get created, with no edge between them.
While creating a graph in pgRouting, we call the 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).

Then it will create both the vertices (source and target vertex, even though they are connected or not).

Is there some other way to create isolated vertices, by directly using the insert_edges function of pgRouting (pgr_base_graph.hpp)?
Vicky Vergara
@cvvergara
Who wants to create an isolated vertex? pgRouting? the user of pgRouting?
Ashish Kumar
@krashish8
I mean "the user of pgRouting".
But if the user tries to do it in the way I mentioned above, the isolated vertices aren't created internally in pgRouting, if we use the insert_edges function defined in pgr_base_graph.hpp
Vicky Vergara
@cvvergara
Why does the user want to create an isolated vertex?
Ashish Kumar
@krashish8

I mean the user may want to do that. It entirely depends upon the user.

As an example, for the graph coloring algorithm, if the graph contains an isolated vertex, it should also have some color assigned to it.

Example: coloring a map, such that two neighbouring states have different color. If the map contains an island state, it should also have some color assigned to it.
Vicky Vergara
@cvvergara
The island is not isolated
Vicky Vergara
@cvvergara
Portugal, Spain, Mexico, USA, Cuba (using the first letter)
P-S, M-U, M-C, U-C that would be the graph representing neighbours
Ashish Kumar
@krashish8
Fine. Got it!
Vicky Vergara
@cvvergara
To have an isolated vertex use ´0´ the edge will be added so the vertex.
 id | source | target | cost | reverse_cost
----+--------+--------+------+--------------
1 |      1 |      1 |   0 |           -1
(1 row)
Ashish Kumar
@krashish8
Okay. Thanks, got it!
Vicky Vergara
@cvvergara

# As part of the Bolsena code spring:

In around 20 minutes will be working checking the PR #1361 with the author, you are welcome to join
Vicky Vergara
@cvvergara

Mohamed Bakli
@mbakli