{"action":"created","issue":{"url":"https://api.github.com/repos/Project-OSRM/osrm-backend/issues/1556","labels_url":"https://api.github.com/repos/Project-OSRM/osrm-backend/issues/1556/labels{/name}","comments_url":"https://api.github.com/repos/Project-OSRM/osrm-backend/issues/1556/comments","events_url":"https://api.github.com/repos/Project-OSRM/osrm-backend/issues/1556/events","html_url":"https://github.com/Project-OSRM/osrm-backend/issues/1556","id":92098186,"number":1556,"title":"TarjanSCC in EdgeBasedGraphFactory finds weakly connected components","user":{"login":"icokk","id":491482,"avatar_url":"https://avatars.githubusercontent.com/u/491482?v=3","gravatar_id":"","url":"https://api.github.com/users/icokk","html_url":"https://github.com/icokk","followers_url":"https://api.github.com/users/icokk/followers","following_url":"https://api.github.com/users/icokk/following{/other_user}","gists_url":"https://api.github.com/users/icokk/gists{/gist_id}","starred_url":"https://api.github.com/users/icokk/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/icokk/subscriptions","organizations_url":"https://api.github.com/users/icokk/orgs","repos_url":"https://api.github.com/users/icokk/repos","events_url":"https://api.github.com/users/icokk/events{/privacy}","received_events_url":"https://api.github.com/users/icokk/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/Project-OSRM/osrm-backend/labels/Bug%20Report","name":"Bug Report","color":"e10c02"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2015-06-30T13:45:38Z","updated_at":"2015-07-01T09:06:27Z","closed_at":null,"body":"The NodeBasedDynamicGraph in EdgeBasedGraphFactory::GenerateEdgeExpandedNodes is constructed in such a way that it contains the reverse directions of all one-way roads (they are the edges with edgeBasedNodeID=-1 and have forward=false in EdgeData). Since TarjanSCC doesn't check whether the edge can be traversed in the forward direction, it works effectively on an undirected graph and finds only weakly connected components. Routing then gets stuck on small strongly connected components, which aren't ignored when creating phantom nodes as they should be.\r\n\r\nThe other application of TarjanSCC, in components.cpp, correctly constructs a StaticGraph by adding just one direction for one-way roads."},"comment":{"url":"https://api.github.com/repos/Project-OSRM/osrm-backend/issues/comments/117553550","html_url":"https://github.com/Project-OSRM/osrm-backend/issues/1556#issuecomment-117553550","issue_url":"https://api.github.com/repos/Project-OSRM/osrm-backend/issues/1556","id":117553550,"user":{"login":"TheMarex","id":606968,"avatar_url":"https://avatars.githubusercontent.com/u/606968?v=3","gravatar_id":"","url":"https://api.github.com/users/TheMarex","html_url":"https://github.com/TheMarex","followers_url":"https://api.github.com/users/TheMarex/followers","following_url":"https://api.github.com/users/TheMarex/following{/other_user}","gists_url":"https://api.github.com/users/TheMarex/gists{/gist_id}","starred_url":"https://api.github.com/users/TheMarex/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/TheMarex/subscriptions","organizations_url":"https://api.github.com/users/TheMarex/orgs","repos_url":"https://api.github.com/users/TheMarex/repos","events_url":"https://api.github.com/users/TheMarex/events{/privacy}","received_events_url":"https://api.github.com/users/TheMarex/received_events","type":"User","site_admin":false},"created_at":"2015-07-01T09:06:27Z","updated_at":"2015-07-01T09:06:27Z","body":"@icokk good catch. It has more issues than that see for example here https://github.com/Project-OSRM/osrm-backend/pull/1493"}}