- Join over
**1.5M+ people** - Join over
**100K+ communities** - Free
**without limits** - Create
**your own community**

- 20:39ImreSamu synchronize #1375
- 16:19ImreSamu synchronize #1375
- 16:10ImreSamu synchronize #1375
- 15:52ImreSamu synchronize #1375
- 14:42
cvvergara on gh-pages

[index] fixing index (compare)

- 13:42cvvergara commented #1375
- 13:41cvvergara labeled #1375
- 13:27cvvergara labeled #1375
- 13:27cvvergara labeled #1375
- 13:27cvvergara milestoned #1375
- 13:27cvvergara review_requested #1375
- 13:27cvvergara review_requested #1375
- 13:27cvvergara review_requested #1375
- 13:27cvvergara review_requested #1375
- 13:27cvvergara review_requested #1375
- 13:26cvvergara review_requested #1375
- 10:11EPajares commented #1345
- 03:15dkastl commented #1345
- 02:53sanak commented #1345
- 02:27dkastl commented #1345

Why the same build passes on appveyor and fails on travis-ci.

@rajhim2 I don't have any idea how it passes on appveyor, however, there's an error in your added files.

In the file `src/kargersContraction/kargersContraction.c`

, the function's name shall be in all lowercase, as PostgreSQL converts all unquoted names to lowercase (`_pgr_kargerscontraction`

instead of `_pgr_kargersContraction`

).

You need to change this in all the three lines:

https://github.com/rajhim2/GSoC-pgRouting/blob/him/src/kargersContraction/kargersContraction.c#L43

https://github.com/rajhim2/GSoC-pgRouting/blob/him/src/kargersContraction/kargersContraction.c#L44

https://github.com/rajhim2/GSoC-pgRouting/blob/him/src/kargersContraction/kargersContraction.c#L116

Why the same build passes on appveyor and fails on travis-ci.

@rajhim2 I don't have any idea how it passes on appveyor, however, there's an error in your added files.

In the file

`src/kargersContraction/kargersContraction.c`

, the function's name shall be in all lowercase, as PostgreSQL converts all unquoted names to lowercase (`_pgr_kargerscontraction`

instead of`_pgr_kargersContraction`

).You need to change this in all the three lines:

https://github.com/rajhim2/GSoC-pgRouting/blob/him/src/kargersContraction/kargersContraction.c#L43

https://github.com/rajhim2/GSoC-pgRouting/blob/him/src/kargersContraction/kargersContraction.c#L44

https://github.com/rajhim2/GSoC-pgRouting/blob/him/src/kargersContraction/kargersContraction.c#L116

Thank you @krashish8 ! It worked like a charm.

For the functionality request of the pgr_dijkstra with the combinations sql

the issue has an example

step 2) Other issue (maybe there is already one that talks about using ctlr-C and in the comment put the possible solution.

Then once we located both issues, Mahmoud will open a PR with tilte "Closes #xx and closes #yyy" with a small comment on the message

After that, @cvvergara will open an issue about using the method for stoping execution on each function.

For example: "Normal" flag is not needed

other example: To create pgr_dikstraCost with combinations

Once that

- Contributor name has been added to modified files
- Contributor name is on the license of new files
- Contributor name is been added to the Contributors List

From the console terminal:

```
# make sure that you are in the correct branch
git checkout combinationsSQL
# update to latest main repo contents
git fetch upstream
# Put your work on top of what develop
git rebase upstream/develop
```

Once you have updated the repo, the following that I forgot to mention on our last meeting must be done:

in

`doc/src/release_notes.rst`

in the corresponding 3.1.0 release notes add`.. rubric:: New functions * pgr_dijkstra(combinations)`

- Commit and push

From the github website:

- make a PR to develop branch
# end of topic

I was adding the boost functionality to the function `pgr_depthFirstSearch`

(pgRouting/GSoC-pgRouting#38) I was implementing.

For this I was supposed to use boost::depth_first_search - for directed graphs, and boost::undirected_dfs - for undirected graphs.

In the current implementation, I have used `pgrouting::UndirectedGraph`

(#L117) and called `boost::depth_first_search`

, yet the function gives the correct result, as expected, for the undirected graph. The documentation for `boost::depth_first_search`

says the graph `Graph& g`

should be directed, however in the current implementation, I use undirected graph with it, and it is working alright.

Moreover, in the pgrouting, we have the functions pgr_primDFS and pgr_kruskalDFS, both of which work only for **Undirected Graphs**, but in the implementation, I see that the function calls the `boost::depth_first_search`

which is supposed to take only Directed Graphs as input.

As the current implementation works good on calling `boost::depth_first_search`

for both directed and undirected graphs, I don't consider the need to use `boost::undirected_dfs`

as everything is working fine.

Anyone has any idea why does the `boost::depth_first_search`

still works for undirected graphs?

Yes, I have an idea, because you are using this general graph class that I created so you get the graph that you need:

https://docs.pgrouting.org/doxy/3.0/classpgrouting_1_1graph_1_1Pgr__base__graph.html

https://docs.pgrouting.org/doxy/3.0/classpgrouting_1_1graph_1_1Pgr__base__graph.html

So, with the if-then-else you need to make sure you are calling to the correct boost function

(Not for the GSoC students)

The branch https://github.com/mahmsakr/pgrouting/tree/combinationsSQL is almost ready and to merge the interruptions to that branch the following has to be done:

The branch https://github.com/mahmsakr/pgrouting/tree/combinationsSQL is almost ready and to merge the interruptions to that branch the following has to be done:

Use the website

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

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

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.
I am currently returning 0 rows for the pgr_kargersContraction query.

@rajhim2 You can check the error from Line Number 1878 - 1888

https://travis-ci.org/github/rajhim2/GSoC-pgRouting/jobs/694570795#L1878

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.

@cvvergara I guess there's some error with the

The pgTAP tests are failing for 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.

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.

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

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

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

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