by

Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Repo info
Activity
  • 15:05
    cvvergara edited #1599
  • 15:03
    krashish8 review_requested #1599
  • 15:03
    krashish8 review_requested #1599
  • 15:03
    krashish8 review_requested #1599
  • 15:03
    krashish8 review_requested #1599
  • 15:03
    krashish8 labeled #1599
  • 15:03
    krashish8 labeled #1599
  • 15:03
    krashish8 assigned #1599
  • 15:03
    krashish8 opened #1599
  • Aug 05 11:26
    landryb commented #1356
  • Aug 05 10:41
    landryb commented #1356
  • Aug 05 05:23
    landryb commented #1356
  • Aug 04 03:48
    krashish8 edited #1348
  • Aug 03 20:04

    cvvergara on v3.1.0

    (compare)

  • Aug 03 19:36

    cvvergara on gh-pages

    Removing extra character (compare)

  • Aug 03 19:35

    cvvergara on gh-pages

    Simplifying index of documentat… (compare)

  • Aug 03 19:12

    cvvergara on gh-pages

    Using redirection instead of sy… (compare)

  • Aug 03 19:08

    cvvergara on gh-pages

    Using redirection instead of sy… (compare)

  • Aug 03 18:45

    cvvergara on gh-pages

    doxy/2.2. adding link to latest… (compare)

  • Aug 03 18:39

    cvvergara on gh-pages

    Removing doxy/2.2. from index d… (compare)

Elias Pajares
@EPajares
potentialfix_pgrouting_issue#584..pdf

Dear pgrouting-community,

we are big fans of your work! And are especially using the driving-distance feature of the pgrouting library.
There is one known issue with this function though, that is summarized in the issue #584.
With the help of @vjeranc I was exploring possibilities to fix this.
In this attempt we were having some preliminary results that are summarized in the PDF attached.
We wanted to contact you because so far the best fix for us seemed to be a custom dijkstra-function as we were not managing to fix this using Boost.
Therefore, we wanted to hear your opinion on that. Is this something that could be accepted? Looking forward to discuss with you.

Best,

Elias

Vicky Vergara
@cvvergara

@EPajares Hi, starting a discussion:
For simplicity suppose there is a graph G(E,V) where E= {(u,v,cost=10)} AND V={u,v} and a driving distance of 4 departing from
u=======+----------------------------v
then between vertex u & v at the "+" its where the driving distance is reached
From the documentation this are the possible columns

RETURNS SET OF (seq, [start_vid,] node, edge, cost, agg_cost)

What would the result be with this graph?

Elias Pajares
@EPajares
Thanks Vicky for your response. We were thinking that the result could be: RETURNS SET OF (seq, [start_vid,] node, edge, cost, agg_cost, partial_edge) We would have in the response all current edges + all edges that can only be "partially traversed" in the reality and are currently not in the response. With the additional parameter 'partial_edge' we could mark all edges that can only be "partially traversed". With post-processing we could use the cost, agg_cost and max_cost to extrapolate along the edge. But this also means that we would probably not have a node at the position "+" but would also create this one with post-processing.
Himanshu Raj
@rajhim2
Can anyone help me with this why docqueries tests are failing.
I am currently returning 0 rows for the pgr_kargersContraction query.
Ashish Kumar
@krashish8
@rajhim2 You can check the error from Line Number 1878 - 1888
https://travis-ci.org/github/rajhim2/GSoC-pgRouting/jobs/694570795#L1878

Your result file contains

SELECT * FROM pgr_kargersContraction(

whereas it should be

SELECT * FROM _pgr_kargersContraction(

according to your queries.

I think the docqueries should call the main function, not the underscored one. So, better change the queries.
Ashish Kumar
@krashish8
@cvvergara I guess there's some error with the kruskalBFS function (an already-implemented function).
The pgTAP tests are failing for the kruskalBFS-edge-cases: https://travis-ci.org/github/krashish8/GSoC-pgRouting/jobs/694577924#L1323
I have encountered such error around 4-5 times in travis in the last 3 weeks, but not always. And every time I re-run the job, it passes.
This time I haven't re-ran it, just to check if there's something I am missing, or there's some error with the tests / the function.
Himanshu Raj
@rajhim2

I think the docqueries should call the main function, not the underscored one. So, better change the queries.

Yes , it is calling only the main function.

Ashish Kumar
@krashish8

https://github.com/rajhim2/GSoC-pgRouting/blob/him/docqueries/kargersContraction/doc-pgr_kargersContraction.result

This is the result file. The main queries lie in the *.test.sql file - https://github.com/rajhim2/GSoC-pgRouting/blob/him/docqueries/kargersContraction/doc-pgr_kargersContraction.test.sql

In your case, all the three queries are calling the underscored function, so, I guess, if you change it to the main function, then the test will pass.

Himanshu Raj
@rajhim2
Oh my bad! Thank you :)
vjeranc
@vjeranc

@EPajares Hi, starting a discussion:
For simplicity suppose there is a graph G(E,V) where E= {(u,v,cost=10)} AND V={u,v} and a driving distance of 4 departing from
u=======+----------------------------v
then between vertex u & v at the "+" its where the driving distance is reached
From the documentation this are the possible columns

RETURNS SET OF (seq, [start_vid,] node, edge, cost, agg_cost)

What would the result be with this graph?

@cvvergara
The result also does not need to contain additional columns. The partial edges can have agg_cost=drivingDistance and cost of the edge can stay the same. User would then check the predecessor agg_cost of the node at edge to figure out the partially traveled part.

The result would be (seq, [start_vid,] node, edge, cost, agg_cost) = (1, u, v, 1, 10, 4). Given that predecessor of v using edge 1 is u and agg_cost at u is 0 then it's simple to figure out the partially traveled part.

I'm understand that implicitly marking the partial edges in this way complicates the function unnecessarily but I have not figured out a simpler way without adding an extra column in the result.

Vicky Vergara
@cvvergara
@EPajares
Then, please, can you give the solution using the columns that you mention, to the one edge graph.
@rajhim2 I hope it was clear to you that you start coding the function that is using boost. we are to discuss the contraction one today.
@EPajares ahhh, I just saw your next message. forget about my request before.
Himanshu Raj
@rajhim2

@rajhim2 I hope it was clear to you that you start coding the function that is using boost. we are to discuss the contraction one today.

Yes, Mam I have done some coding related to my proposed function.

Vicky Vergara
@cvvergara
@EPajares I like the line of thinking.
Q, for you to think a bit more what about something like this:
(seq, [start_vid,] node, edge, cost, agg_cost) = (1, u, v, 1, 4, 4)
vjeranc
@vjeranc
@cvvergara If edge cost is reduced to match the partial travel time, then one can find all the partial edges easily. Edges are found by comparing the cost of the input edges with same edge id and the output edges. This is definitely more elegant than finding the predecessors and checking the agg_cost for the predecessor.
Vicky Vergara
@cvvergara
@EPajares So that would be a breaking change, because of the additional lines, but what if have in the signature an optional named parameter (and last on the list of parameters) I am thinking of this possibilities: names can be different of the possibilities I mention but the important thing is that the default value must give the current results
  • tails with default value FALSE
  • OR vertex_ending with default TRUE
vjeranc
@vjeranc

@cvvergara Yeah, the naming can be related to tree leaves, given that the current result is a spanning tree, this would extend the leaves with partial edges that end at a place between vertices of the real edge.

The implementation of the fix can be made in such a way to keep the current results. What worries me the most is the fact that the fix requires a custom dijkstra implementation and does not use any of the datastructures used by all of the graph algorithms in pgrouting codebase. I'm confident that the code is correct and performs well.
@EPajares and I will do exhaustive testing to see that the examples deemed previously incorrect (without partial edges or tails as you call it) are now fully correct.

The reason why the pgr_drivingDistance function is useful is for finding isochrones. In this case all the nodes at which agg_cost is less than the given drivingDistance are not useful.

Maybe that deserves a new function name?

Vicky Vergara
@cvvergara
it finds the nodes where cost from source to node is <= distance
Why are the results incorrect given that definition?
note that we are not finding edges that are within the distance
the results on the edges is a spanning graph, its not a minimum spanning graph, its just a spanning graph.
The current implementation calculates nodes that are within the distance.
Give me a counter example, an execution, where the nodes are not within the distance.
Note that: A node on the "tail" is not within the distance because its further away than distance. So this is not what I am asking for.
I will be waiting for your tests.
vjeranc
@vjeranc

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

Vicky Vergara
@cvvergara
the results are not incomplete given the definition of finding the nodes within the distance.
vjeranc
@vjeranc
@cvvergara If one wants to find the isochrones where a starting point is a school and driving distance is 15 minutes. The pgr_drivingDistance result does not give all of the isochrones reachable in the real world. It sometimes does not return any nodes where drivingDistance == 15.
vjeranc
@vjeranc
I believe the users expect to get points on the road network but they end up getting nodes in the discretization of the road network.
At least that's my interpretation of the issue (#584)[pgRouting/pgrouting#584]
Elias Pajares
@EPajares
@cvvergara and @vjeranc thanks for your discussions on this. I think it is a matter of definition whether the current result of pgr_drivingDistance can be regarded as complete or incomplete. So maybe there is no need for a debate on this. I would say what we are trying to attempt is to make the result more realistic when moving on a street network. I would propose that we could do the implementation for the testing with a new function name while always considering the maximum of compatibility with the current input and output parameters. @cvvergara I will think further about your comments. After the first demonstration testings we could discuss again more closely about further details and the compatibility with the existing function.
Vicky Vergara
@cvvergara

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

vjeranc
@vjeranc

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

Vicky Vergara
@cvvergara
Well, I understand the problem, but maybe the solution is a combination of using:
pgr_drivingDistance results + PostgreSQL queries + PostGIS functionality
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.

about tests

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