Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Extract path #94

Open
wants to merge 3 commits into
base: master
Choose a base branch
from
Open

Extract path #94

wants to merge 3 commits into from

Conversation

mstou
Copy link

@mstou mstou commented Aug 25, 2018

This pull request fixes #89 .

Copy link

@dionyziz dionyziz left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Concept ACK


it("returns weight: 0 and path: [source], from source to source", function() {
var shortestPaths = {
"a": { distance:0 },

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

nit: space after :


it("throws an error when given an invalid destination vertex", function() {
var shortestPaths = {
"a": { distance:0 },

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

nit: space after :

"a": { distance: 0 },
"b": { distance: 17, predecessor: "d" },
"c": { distance: 42, predecessor: "b" },
"d": { distance: 73, predecessor: "c" }

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Is it possible for this output to ever be the output of a shortest paths algorithm? Can you give an example?

Copy link
Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This ( or similar cyclic results ) can not be the output of a shortest path algorithm, so the cycle detection might be an overkill here. I just added it to the implementation so that we can be sure that runExtractPath() will always exit its recursion, indepedendly of the results object that it is called on. Appart from that, I can't really see a use case in which extractPath() will be called on an object not produced by a shortest path algorithm , so I can remove it if u wish

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think removing this test would be sensible.

test/alg/extract-path-tests.js Outdated Show resolved Hide resolved
lib/alg/extract-path.js Outdated Show resolved Hide resolved
@mstou mstou mentioned this pull request Aug 28, 2018
@mstou
Copy link
Author

mstou commented Aug 28, 2018

I refactored runExtractPath(), now it just iterates on predecessors and pushes them in the path array. When the iteration is finished, it reverses the array and returns it.

Just for history - I also had a second option, to push each predecessor at the start of the array with Array.unshift() . I ran the two options on a chain graph of 10^5 nodes and impressively enough, unshift() took ~3200ms and reverse() took just 30ms !

@dionyziz
Copy link

dionyziz commented Aug 29, 2018

This is not unexpected - unshift takes Θ(n) so running it n times takes Θ(n^2). Push takes Θ(1) and reverse takes Θ(n), so running push n times followed by a reverse takes Θ(n).

@mstou
Copy link
Author

mstou commented Aug 29, 2018

Yes, of course this result was expexted! - I couldnt find the unshift complexity from an official source with a quick search, so I just tested it on my own :)
The new iterative version of extractPath is ready for reviewing. I forgot to mention that when this PR is merged I will also update the documentation accordingly.

@mstou
Copy link
Author

mstou commented Sep 2, 2018

PTAL :)

@pkakelas
Copy link

pkakelas commented Sep 4, 2018

LGTM. Good job once again!

lib/alg/extract-path.js Outdated Show resolved Hide resolved
@dionyziz
Copy link

dionyziz commented Sep 4, 2018

Please rebase and squash commits with the commits that they fix so that your history is clean.

@mstou mstou force-pushed the extract-shortest-path branch from ee00ef6 to 2862de4 Compare September 4, 2018 16:37
@lutzroeder lutzroeder force-pushed the master branch 3 times, most recently from 64a1b87 to cf48a25 Compare February 16, 2019 02:57
@tdmartino
Copy link

Hello, will this pr be merged any time soon? I see activity in Feb, but last comment is from Sep 2019.

@lutzroeder
Copy link
Contributor

@tdmartino, can you review this change and do some more testing?

@assafsun
Copy link

also looking at this PR

@assafsun
Copy link

Nice work!
My comments:

  1. Need to update the test file according to the style, running make returns an error of
    Expected indentation of 2 spaces but found 4

  2. I think that additional checking to see if shortestPaths[source] and shortestPaths[destination] is required because the function can't take any assumptions on the passed shortestPaths parameter.

  3. Because there is no types checking and alignment to the return object from the algorithm, it is worth to verify that also the value distance exists same as predecessor which is part of the return object.

@mstou
Copy link
Author

mstou commented Apr 10, 2020

Thanks for the review @assafsun ! I agree with your points, I'll make the necessary changes

@assafsun
Copy link

@mstou Thanks for the update

@zekenie
Copy link

zekenie commented Jun 3, 2024

Welp, I also could really use this. Until then i'll just use the pr code

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Path extraction function
7 participants