{"action":"created","issue":{"url":"https://api.github.com/repos/bluss/petgraph/issues/143","repository_url":"https://api.github.com/repos/bluss/petgraph","labels_url":"https://api.github.com/repos/bluss/petgraph/issues/143/labels{/name}","comments_url":"https://api.github.com/repos/bluss/petgraph/issues/143/comments","events_url":"https://api.github.com/repos/bluss/petgraph/issues/143/events","html_url":"https://github.com/bluss/petgraph/pull/143","id":223319750,"number":143,"title":"Add A* pathfinding algorithm","user":{"login":"jmcomets","id":1894019,"avatar_url":"https://avatars2.githubusercontent.com/u/1894019?v=4","gravatar_id":"","url":"https://api.github.com/users/jmcomets","html_url":"https://github.com/jmcomets","followers_url":"https://api.github.com/users/jmcomets/followers","following_url":"https://api.github.com/users/jmcomets/following{/other_user}","gists_url":"https://api.github.com/users/jmcomets/gists{/gist_id}","starred_url":"https://api.github.com/users/jmcomets/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jmcomets/subscriptions","organizations_url":"https://api.github.com/users/jmcomets/orgs","repos_url":"https://api.github.com/users/jmcomets/repos","events_url":"https://api.github.com/users/jmcomets/events{/privacy}","received_events_url":"https://api.github.com/users/jmcomets/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":1,"created_at":"2017-04-21T08:51:10Z","updated_at":"2017-09-02T00:28:47Z","closed_at":null,"author_association":"CONTRIBUTOR","pull_request":{"url":"https://api.github.com/repos/bluss/petgraph/pulls/143","html_url":"https://github.com/bluss/petgraph/pull/143","diff_url":"https://github.com/bluss/petgraph/pull/143.diff","patch_url":"https://github.com/bluss/petgraph/pull/143.patch"},"body":"## Summary\r\n\r\nI've written the current A* to return the full path from start to finish, unlike the Dijkstra that simply computes all costs, stopping if the goal is found. Additionally, I could add in the computed cost of the path.\r\n\r\nI've added a test that validates a basic usage, although there should be a proof that the heuristic drives the pathfinding.\r\n\r\nPerformance-wise, the tracking of previous nodes to later rebuild the path from start to finish adds on the Dijkstra's performance cost, otherwise it's roughly equivalent.\r\n\r\n## Sidenotes\r\n\r\nSome work could be done to allow more flexibility in terms of data-structures used by the algorithm, as it currently requires that node IDs be `Eq` + `Hash` when we could have another version only requiring `Ord` which would use trees instead of hashmaps.\r\n\r\n## Questions\r\n\r\n- Should the path returned be the list of node IDs or the actual edge IDs?\r\n- Should there be bench tests on the A* vs the Dijkstra when `H(x) = 0` to measure the cost of tracking the path?\r\n- Should the pathfinding algorithms be reworked to share some common \"flexible\" interface?\r\n\r\n(fixes #138)"},"comment":{"url":"https://api.github.com/repos/bluss/petgraph/issues/comments/326709584","html_url":"https://github.com/bluss/petgraph/pull/143#issuecomment-326709584","issue_url":"https://api.github.com/repos/bluss/petgraph/issues/143","id":326709584,"user":{"login":"bluss","id":3209739,"avatar_url":"https://avatars1.githubusercontent.com/u/3209739?v=4","gravatar_id":"","url":"https://api.github.com/users/bluss","html_url":"https://github.com/bluss","followers_url":"https://api.github.com/users/bluss/followers","following_url":"https://api.github.com/users/bluss/following{/other_user}","gists_url":"https://api.github.com/users/bluss/gists{/gist_id}","starred_url":"https://api.github.com/users/bluss/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bluss/subscriptions","organizations_url":"https://api.github.com/users/bluss/orgs","repos_url":"https://api.github.com/users/bluss/repos","events_url":"https://api.github.com/users/bluss/events{/privacy}","received_events_url":"https://api.github.com/users/bluss/received_events","type":"User","site_admin":false},"created_at":"2017-09-02T00:28:47Z","updated_at":"2017-09-02T00:28:47Z","author_association":"OWNER","body":"This is where I think of something like the inverse of an iterator (Think instead of Iterator::next we have a generalization of Vec::push, something that eats elements) -- so that the user could submit both a vector for path and for edges, if they wanted to save both those."}}
{"actor":{"display_login":"bluss"}}