{"action":"opened","issue":{"url":"https://api.github.com/repos/gonum/graph/issues/59","labels_url":"https://api.github.com/repos/gonum/graph/issues/59/labels{/name}","comments_url":"https://api.github.com/repos/gonum/graph/issues/59/comments","events_url":"https://api.github.com/repos/gonum/graph/issues/59/events","html_url":"https://github.com/gonum/graph/issues/59","id":77293383,"number":59,"title":"search: FloydWarshall is incorrect","user":{"login":"kortschak","id":275221,"avatar_url":"https://avatars.githubusercontent.com/u/275221?v=3","gravatar_id":"","url":"https://api.github.com/users/kortschak","html_url":"https://github.com/kortschak","followers_url":"https://api.github.com/users/kortschak/followers","following_url":"https://api.github.com/users/kortschak/following{/other_user}","gists_url":"https://api.github.com/users/kortschak/gists{/gist_id}","starred_url":"https://api.github.com/users/kortschak/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kortschak/subscriptions","organizations_url":"https://api.github.com/users/kortschak/orgs","repos_url":"https://api.github.com/users/kortschak/repos","events_url":"https://api.github.com/users/kortschak/events{/privacy}","received_events_url":"https://api.github.com/users/kortschak/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":0,"created_at":"2015-05-17T11:59:17Z","updated_at":"2015-05-17T11:59:17Z","closed_at":null,"body":"I have been working on cleaning up various things, and part of that is to generalise the FloydWarshall function.\r\n\r\nThe current state of that is in the api-explore branch. There is a requirement for an id sort of the nodes on input. I've spent a few hours trying to sort out why this is - at first I thought it was because of the changes I have made, but I have come to the belief that the implementation is based on an incorrect interpretation of the algorithm, one that makes the outcome dependent on the order of the adjacency matrix iterations (i.e. the order the nodes are explored). This does not show up in the current master test case because the order is deterministic, but does in mine because it is based on a map iteration.\r\n\r\nThis can be demonstrated by inverting the order of nodes in the graph input to TestFWConfoundingPath (0, 1, 2, 3, 4, 5 = 5, 4, 3, 2, 1, 0) and amending the test expectations appropriately.\r\n\r\nThe test fails with spectacularly with too many paths being returned by all paths func (the single path return is correct).\r\n\r\nI believe that the tests used to store multiple paths in the shortest path tree is incorrect - depending on distance matrix state that has been mutated since, and I cannot find anywhere else that does this. If I could see another implementation or a paper that uses this technique, I would be happier, but at this stage I am thinking the function should not attempt to do this at all."}}