Uh oh!
There was an error while loading.Please reload this page.
- Notifications
You must be signed in to change notification settings - Fork5.7k
feat: added Astar Search Algorithm in Graphs#1739
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 ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
base:master
Are you sure you want to change the base?
Uh oh!
There was an error while loading.Please reload this page.
Conversation
codecov-commenter commentedOct 20, 2024 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
Codecov ReportAttention: Patch coverage is
Additional details and impacted files@@ Coverage Diff @@## master #1739 +/- ##==========================================- Coverage 84.76% 83.88% -0.88%========================================== Files 378 379 +1 Lines 19738 19945 +207 Branches 2957 2958 +1 ========================================== Hits 16731 16731- Misses 3007 3214 +207 ☔ View full report in Codecov by Sentry. 🚀 New features to boost your workflow:
|
@appgurueu@raklaptudirm |
Graphs/Astar.js Outdated
| @@ -0,0 +1,107 @@ | |||
| /** | |||
| * Author: Mathang Peddi | |||
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Please use JSDoc annotations like@author.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Have changed it to@author: Mathang Peddi
Do I need to make any other change here?
Graphs/Astar.js Outdated
| @@ -0,0 +1,107 @@ | |||
| /** | |||
| * Author: Mathang Peddi | |||
| * A* Search Algorithm implementation in JavaScript | |||
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
| * A* Search Algorithm implementation in JavaScript |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Removed this line.
Graphs/Astar.js Outdated
| * It uses graph data structure. | ||
| */ | ||
| function createGraph(V, E) { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
This function is unnecessary. Just take the graph in adjacency list representation. There is also no need to restrict this to undirected graphs.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Removed this function, created an adjacency list and directly passed it to the function.
Graphs/Astar.js Outdated
| } | ||
| // Heuristic function to estimate the cost to reach the goal | ||
| // You can modify this based on your specific problem, for now, we're using Manhattan distance |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
This is not a useful manhattan distance. This is just the absolute distance between vertex IDs. Instead you want some kind of associated "points" (say, in 2d or 3d space) for which you compute distances.
In any case, the heuristic function should probably be a (mandatory) parameter.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
I have made the changes, I am using Euclidian Distance here, do I need to make any other change here?
Graphs/Astar.js Outdated
| return Math.abs(a - b) | ||
| } | ||
| function aStar(graph, V, src, target) { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Again, just take the graph in adjacency list representation.V is then redundant (and also conflicts with our naming scheme).
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Changed it.
Graphs/Astar.js Outdated
| } | ||
| } | ||
| return [] // Return empty path if there's no path to the target |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Should benull instead.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Changed.
Graphs/Astar.js Outdated
| function aStar(graph, V, src, target) { | ||
| const openSet = new Set([src]) // Nodes to explore | ||
| const cameFrom = Array(V).fill(-1) // Keep track of path |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Usenull instead of-1, it's the idiomatic value to use in JS for absence of a value.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Changed.
Graphs/Astar.js Outdated
| openSet.delete(current) | ||
| // Explore neighbors | ||
| for (let i = 0; i < graph[current].length; i++) { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Just dofor (const [neighbor, weight] of graph[current])
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Changed.
Graphs/Astar.js Outdated
| module.exports = { createGraph, aStar } | ||
| // const V = 9 |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Should be a test instead.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Removed this part, do you want me to add a Astar.test.js file as a part of Unit Testing?
Graphs/Astar.js Outdated
| return [] // Return empty path if there's no path to the target | ||
| } | ||
| module.exports = { createGraph, aStar } |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
| module.exports={ createGraph, aStar} | |
| export{aStar} |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Changed.
@appgurueu Can you check if all the changes are proper? |
| } | ||
| // Priority Queue (Min-Heap) implementation | ||
| class PriorityQueue { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Please import this (we have a priority queue implementation in this repo) rather than reimplementing it.
| } | ||
| } | ||
| function aStar(graph, src, target, points) { |
appgurueuOct 23, 2024 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Where are these parameters documented? Also why is the heuristic function not a parameter (which may default to a simple euclidean heuristic)?
| return path.reverse() | ||
| } | ||
| // Explore neighbors using destructuring for cleaner code |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
the "using destructuring for cleaner code part" is obvious
| return null // Return null if there's no path to the target | ||
| } | ||
| // Define the graph as an adjacency list |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
This should be a proper test case.
Uh oh!
There was an error while loading.Please reload this page.
Describe your change:
Checklist:
Example:
UserProfile.jsis allowed butuserprofile.js,Userprofile.js,user-Profile.js,userProfile.jsare notFixes: #{$ISSUE_NO}.