7 ms·

Algorithm-Visualizer

79 points by walker_tw 6y ago

walker_tw 6y ago
While job searching me and a mate made an interactive app to learn ReactJS and teach graphing algorithms (Dijkstra, A*, BFS etc). Enjoy it (and contact us if you have any exciting jr. dev roles/opportunities !)
- ColinWright 6y ago
  While I don't have any roles or opportunities available, when you say things like this: contact us if you have any exciting jr. dev roles/opportunities ... it would help if you had contact details in your HN profile.
  - walker_tw 6y ago
    Thanks for the help! I hope that you enjoyed the app. I have updated it (but ill put it just here in case) https://www.linkedin.com/in/thomas-w-walker/ https://www.linkedin.com/in/thomas-w-walker/
    - ColinWright 6y ago
      You might want to re-visit this. Under "Depth First Search" you say: > Depth first search is the only algorithm listed which will NOT find the shortest path. That turns out not to be the case. Euclidean will also sometimes not find the shortest path. And indeed, you say so in the section on Euclidean you say: > *However because our grid is only traversable on horizontal or vertical vertices using this heurtistic will NOT always give the shortest path, ..." You also mis-spelled "heuristics", but that's easily done, and easily fixed. The app is nice ... well done.
      - walker_tw 6y ago
        Thank you very much for the feedback. And for adding the url above.
ColinWright 6y ago
For anyone wanting to try it directly, here's a quick link: https://algo-visualiser.herokuapp.com/ https://algo-visualiser.herokuapp.com/
inetsee 6y ago
From the title I was expecting a more general purpose algorithm visualizer. I think this is more accurately described as "Graph Traversal Algorithm Visualizer".
- oefrha 6y ago
  Even the use of “graph traversal algorithm” is not accurate. Dijkstra and A* aren’t for graph traversal. These are pathfinding algorithms.
  - Jaxan 6y ago
    You can use Dijkstra as a traversal, since you don’t need and endpoint. I still agree that comparing a DFS and an A* is a bit strange, they have different use cases.
- Gehinnn 6y ago
  You might like the Debug Visualizer for VS Code! It's a general purpose visualizer. However it's not as easy to use as this project. https://github.com/hediet/vscode-debug-visualizer/blob/master/extension/README.md https://github.com/hediet/vscode-debug-visualizer/blob/maste...
carterklein13 6y ago
This would've been very useful in my college days. A 300-person lecture plus a professor with horrible chalk handwriting who didn't host any TA sections was not conducive to learning.
- bsas 6y ago
  Glad you found it to be informative!
pveierland 6y ago
The site states that the A* algorithm with the Euclidean heuristic does not always find the shortest path. This appears to be true for the implementation [0], but should not be true in general, as it should be guaranteed that A* will provide a shortest path when used with an admissible heuristic such as the Euclidean distance. [0] https://imgur.com/a/UCAFHA4 https://imgur.com/a/UCAFHA4
- walker_tw 6y ago
  Ah hello thanks for looking at the app. The reason that we state that Euclidean does not always find the shortest path is because the way the distance heuristic is calculated. Euclidean will not work on a quad-directional traversal grid such as this (we cant use diagonals) so instead the Manhattan distance is used to override this issue.
  - pveierland 6y ago
    Cool app! However shouldn't using the Euclidean heuristic still result in finding the shortest path, as it will not overestimate the distance to the goal when evaluating a node, even if it is not possible to travel diagonally in the grid? Also - is the behavior shown in the screenshot working as intended, as the shown path includes a detour?
  - birktj 6y ago
    I don't think this is true. From Wikipedia [1]: > The heuristic function is problem-specific. If the heuristic function is admissible, meaning that it never overestimates the actual cost to get to the goal, A* is guaranteed to return a least-cost path from start to goal. In this case the euclidean does not overestimate so I would guess there is a bug in the implementation. [1] https://en.wikipedia.org/wiki/A*_search_algorithm https://en.wikipedia.org/wiki/A*_search_algorithm Edit: Having taken a look at the source code I believe the problems mostly stem from the `addNeighboursToOpen` function [2]. It sets the distance and parent of unvisited neighbors of the current node. However this may happen multiple times for a node before it is actually visited. Meaning that the distance and parent is updated multiple times and the value at the end is not the optimal one. A simple fix would be to do a if check to see if the node already has a distance assigned. [2] https://github.com/Walker-TW/Algorithm-Visualizer/blob/master/src/Algorithms/a*euclidean.js#L22 https://github.com/Walker-TW/Algorithm-Visualizer/blob/maste...
clashmeifyoucan 6y ago
Something similar in python to visualize algorithms and generate videos: https://github.com/CCExtractor/vardbg https://github.com/CCExtractor/vardbg
laszlokorte 6y ago
I am working on a similar project, but for self drawn graphs instead of grid graphs [0]. But it's not finished yet and missing documentation. [0]: https://algorithms.laszlokorte.de/ https://algorithms.laszlokorte.de/

79 points by walker_tw 6y ago

While job searching me and a mate made an interactive app to learn ReactJS and teach graphing algorithms (Dijkstra, A*, BFS etc). Enjoy it (and contact us if you have any exciting jr. dev roles/opportunities !)

ColinWright 6y ago
While I don't have any roles or opportunities available, when you say things like this: contact us if you have any exciting jr. dev roles/opportunities ... it would help if you had contact details in your HN profile.
- walker_tw 6y ago
  Thanks for the help! I hope that you enjoyed the app. I have updated it (but ill put it just here in case) https://www.linkedin.com/in/thomas-w-walker/ https://www.linkedin.com/in/thomas-w-walker/
  - ColinWright 6y ago
    You might want to re-visit this. Under "Depth First Search" you say: > Depth first search is the only algorithm listed which will NOT find the shortest path. That turns out not to be the case. Euclidean will also sometimes not find the shortest path. And indeed, you say so in the section on Euclidean you say: > *However because our grid is only traversable on horizontal or vertical vertices using this heurtistic will NOT always give the shortest path, ..." You also mis-spelled "heuristics", but that's easily done, and easily fixed. The app is nice ... well done.
    - walker_tw 6y ago
      Thank you very much for the feedback. And for adding the url above.

ColinWright 6y ago

For anyone wanting to try it directly, here's a quick link: https://algo-visualiser.herokuapp.com/ https://algo-visualiser.herokuapp.com/

inetsee 6y ago

From the title I was expecting a more general purpose algorithm visualizer. I think this is more accurately described as "Graph Traversal Algorithm Visualizer".

oefrha 6y ago
Even the use of “graph traversal algorithm” is not accurate. Dijkstra and A* aren’t for graph traversal. These are pathfinding algorithms.
- Jaxan 6y ago
  You can use Dijkstra as a traversal, since you don’t need and endpoint. I still agree that comparing a DFS and an A* is a bit strange, they have different use cases.
Gehinnn 6y ago
You might like the Debug Visualizer for VS Code! It's a general purpose visualizer. However it's not as easy to use as this project. https://github.com/hediet/vscode-debug-visualizer/blob/master/extension/README.md https://github.com/hediet/vscode-debug-visualizer/blob/maste...

carterklein13 6y ago

This would've been very useful in my college days. A 300-person lecture plus a professor with horrible chalk handwriting who didn't host any TA sections was not conducive to learning.

bsas 6y ago
Glad you found it to be informative!

pveierland 6y ago

The site states that the A* algorithm with the Euclidean heuristic does not always find the shortest path. This appears to be true for the implementation [0], but should not be true in general, as it should be guaranteed that A* will provide a shortest path when used with an admissible heuristic such as the Euclidean distance. [0] https://imgur.com/a/UCAFHA4 https://imgur.com/a/UCAFHA4

walker_tw 6y ago
Ah hello thanks for looking at the app. The reason that we state that Euclidean does not always find the shortest path is because the way the distance heuristic is calculated. Euclidean will not work on a quad-directional traversal grid such as this (we cant use diagonals) so instead the Manhattan distance is used to override this issue.
- pveierland 6y ago
  Cool app! However shouldn't using the Euclidean heuristic still result in finding the shortest path, as it will not overestimate the distance to the goal when evaluating a node, even if it is not possible to travel diagonally in the grid? Also - is the behavior shown in the screenshot working as intended, as the shown path includes a detour?
- birktj 6y ago
  I don't think this is true. From Wikipedia [1]: > The heuristic function is problem-specific. If the heuristic function is admissible, meaning that it never overestimates the actual cost to get to the goal, A* is guaranteed to return a least-cost path from start to goal. In this case the euclidean does not overestimate so I would guess there is a bug in the implementation. [1] https://en.wikipedia.org/wiki/A*_search_algorithm https://en.wikipedia.org/wiki/A*_search_algorithm Edit: Having taken a look at the source code I believe the problems mostly stem from the `addNeighboursToOpen` function [2]. It sets the distance and parent of unvisited neighbors of the current node. However this may happen multiple times for a node before it is actually visited. Meaning that the distance and parent is updated multiple times and the value at the end is not the optimal one. A simple fix would be to do a if check to see if the node already has a distance assigned. [2] https://github.com/Walker-TW/Algorithm-Visualizer/blob/master/src/Algorithms/a*euclidean.js#L22 https://github.com/Walker-TW/Algorithm-Visualizer/blob/maste...

clashmeifyoucan 6y ago

Something similar in python to visualize algorithms and generate videos: https://github.com/CCExtractor/vardbg https://github.com/CCExtractor/vardbg

laszlokorte 6y ago

I am working on a similar project, but for self drawn graphs instead of grid graphs [0]. But it's not finished yet and missing documentation. [0]: https://algorithms.laszlokorte.de/ https://algorithms.laszlokorte.de/