dagrejs
Extract path
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 !
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).
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.
Please rebase and squash commits with the commits that they fix so that your history is clean.
Hello, will this pr be merged any time soon? I see activity in Feb, but last comment is from Sep 2019.
Nice work! My comments:
-
Need to update the test file according to the style, running make returns an error of Expected indentation of 2 spaces but found 4
-
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.
-
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.
Thanks for the review @assafsun ! I agree with your points, I'll make the necessary changes