graphlib icon indicating copy to clipboard operation
graphlib copied to clipboard

Published 20 hours ago • verified publisher icon dagrejs

Add Bellman-Ford algorithm

Open mstou opened this issue 7 years ago • 13 comments

Fixes #87 . As requested in issue #87, I implemented the bellman-ford algorithm, respecting the coding style of the repository. I included the bellmanFord function in the module exported by lib/alg and added some tests in tests/alg/bellman-ford-tests.js

mstou avatar Aug 24 '18 19:08 mstou

@dionyziz can you help reviewing and testing this change?

lutzroeder avatar Aug 25 '18 04:08 lutzroeder

Thanks for the feedback @dionyziz @lutzroeder . Im working on the changes

mstou avatar Aug 25 '18 10:08 mstou

@dionyziz @lutzroeder

  • I fixed the code format in all files
  • I changed the edge traversal as requested and added the relaxAllEdges() function in bellman-ford.js
  • I also corrected the behavior of bellman-ford regarding the reversed edges ( lines 37-40 )
  • I merged the common test cases of bellman-ford and dijkstra in shortest-paths-tests.js

mstou avatar Aug 25 '18 22:08 mstou

@pkakelas could also help with this review

dionyziz avatar Aug 27 '18 14:08 dionyziz

LGTM, good job :)

pkakelas avatar Aug 28 '18 17:08 pkakelas

This pull request now fixes #87 . Summary:

  • Implemented the bellman-ford algorithm
  • Created shortestPaths() which in Θ(E) checks whether the graph contains a negative weight edge and chooses to use dijkstra or bellman-ford accordingly
  • Added the shortest-paths-test.js file, which tests the shortestPaths function and also exports a test function for shortest paths algorithms that is used in bellman-ford and dijkstra tests to avoid code duplication

mstou avatar Sep 02 '18 13:09 mstou

PTAL

mstou avatar Sep 04 '18 11:09 mstou

Hi @mstou

Thanks for the work!

I'm trying to review the open PR in order to reduce the amount of issues and PRs. In case you want to continue your work, I will appreciate if you can rebase and create a new iteration. I will review it and try to make sure it will be pushed as I think this is a nice algorithm to support.

If not, I will try to continue it.

assafsun avatar Apr 10 '20 09:04 assafsun

Hi @assafsun, I'll be glad to rebase this to master and squash the commits

mstou avatar Apr 10 '20 10:04 mstou

@mstou Thanks for the update, I will follow this PR.

assafsun avatar Apr 10 '20 10:04 assafsun

Hi @assafsun, sorry for the delay, I rebased to master and squashed the fixup commits. Take a look whenever you have time :)

mstou avatar Apr 29 '20 20:04 mstou

@mstou Thank you for the new iteration. I ran your code and the tests passed. I left some small comments.

assafsun avatar May 01 '20 11:05 assafsun