{"action":"created","issue":{"url":"https://api.github.com/repos/Project-OSRM/osrm-backend/issues/3313","repository_url":"https://api.github.com/repos/Project-OSRM/osrm-backend","labels_url":"https://api.github.com/repos/Project-OSRM/osrm-backend/issues/3313/labels{/name}","comments_url":"https://api.github.com/repos/Project-OSRM/osrm-backend/issues/3313/comments","events_url":"https://api.github.com/repos/Project-OSRM/osrm-backend/issues/3313/events","html_url":"https://github.com/Project-OSRM/osrm-backend/issues/3313","id":189348530,"number":3313,"title":"Re-use intersection forms","user":{"login":"MoKob","id":12932279,"avatar_url":"https://avatars.githubusercontent.com/u/12932279?v=3","gravatar_id":"","url":"https://api.github.com/users/MoKob","html_url":"https://github.com/MoKob","followers_url":"https://api.github.com/users/MoKob/followers","following_url":"https://api.github.com/users/MoKob/following{/other_user}","gists_url":"https://api.github.com/users/MoKob/gists{/gist_id}","starred_url":"https://api.github.com/users/MoKob/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MoKob/subscriptions","organizations_url":"https://api.github.com/users/MoKob/orgs","repos_url":"https://api.github.com/users/MoKob/repos","events_url":"https://api.github.com/users/MoKob/events{/privacy}","received_events_url":"https://api.github.com/users/MoKob/received_events","type":"User","site_admin":false},"labels":[{"id":336727645,"url":"https://api.github.com/repos/Project-OSRM/osrm-backend/labels/Refactor","name":"Refactor","color":"009800","default":false}],"state":"closed","locked":false,"assignee":{"login":"MoKob","id":12932279,"avatar_url":"https://avatars.githubusercontent.com/u/12932279?v=3","gravatar_id":"","url":"https://api.github.com/users/MoKob","html_url":"https://github.com/MoKob","followers_url":"https://api.github.com/users/MoKob/followers","following_url":"https://api.github.com/users/MoKob/following{/other_user}","gists_url":"https://api.github.com/users/MoKob/gists{/gist_id}","starred_url":"https://api.github.com/users/MoKob/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MoKob/subscriptions","organizations_url":"https://api.github.com/users/MoKob/orgs","repos_url":"https://api.github.com/users/MoKob/repos","events_url":"https://api.github.com/users/MoKob/events{/privacy}","received_events_url":"https://api.github.com/users/MoKob/received_events","type":"User","site_admin":false},"assignees":[{"login":"MoKob","id":12932279,"avatar_url":"https://avatars.githubusercontent.com/u/12932279?v=3","gravatar_id":"","url":"https://api.github.com/users/MoKob","html_url":"https://github.com/MoKob","followers_url":"https://api.github.com/users/MoKob/followers","following_url":"https://api.github.com/users/MoKob/following{/other_user}","gists_url":"https://api.github.com/users/MoKob/gists{/gist_id}","starred_url":"https://api.github.com/users/MoKob/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MoKob/subscriptions","organizations_url":"https://api.github.com/users/MoKob/orgs","repos_url":"https://api.github.com/users/MoKob/repos","events_url":"https://api.github.com/users/MoKob/events{/privacy}","received_events_url":"https://api.github.com/users/MoKob/received_events","type":"User","site_admin":false}],"milestone":{"url":"https://api.github.com/repos/Project-OSRM/osrm-backend/milestones/20","html_url":"https://github.com/Project-OSRM/osrm-backend/milestones/5.6.0","labels_url":"https://api.github.com/repos/Project-OSRM/osrm-backend/milestones/20/labels","id":1985499,"number":20,"title":"5.6.0","description":"","creator":{"login":"MoKob","id":12932279,"avatar_url":"https://avatars.githubusercontent.com/u/12932279?v=3","gravatar_id":"","url":"https://api.github.com/users/MoKob","html_url":"https://github.com/MoKob","followers_url":"https://api.github.com/users/MoKob/followers","following_url":"https://api.github.com/users/MoKob/following{/other_user}","gists_url":"https://api.github.com/users/MoKob/gists{/gist_id}","starred_url":"https://api.github.com/users/MoKob/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MoKob/subscriptions","organizations_url":"https://api.github.com/users/MoKob/orgs","repos_url":"https://api.github.com/users/MoKob/repos","events_url":"https://api.github.com/users/MoKob/events{/privacy}","received_events_url":"https://api.github.com/users/MoKob/received_events","type":"User","site_admin":false},"open_issues":43,"closed_issues":12,"state":"open","created_at":"2016-09-06T07:09:04Z","updated_at":"2016-12-01T16:07:54Z","due_on":null,"closed_at":null},"comments":1,"created_at":"2016-11-15T10:04:15Z","updated_at":"2016-12-01T16:07:54Z","closed_at":"2016-12-01T16:07:54Z","body":"In creating the edge-expanded graph, the workload for creating correct intersection forms has increased quite a lot from OSRM 5.4 to 5.5.\r\n\r\nOne thing we could do is to reduce the work performed [here](https://github.com/Project-OSRM/osrm-backend/blob/3235f30a988a77a3f0dcb100d65c8f37eac244c8/src/extractor/edge_based_graph_factory.cpp#L366-L378) by re-using intersection shapes.\r\n\r\nThe general problem is that we look at every intersection in the form\r\n`node_u -> edge_u_v -> node_v` for every `node_v`. So if a node has four incoming roads, we compute the intersection shape at `node_v` four times (once for each road).\r\n\r\nHowever: the general shape of the intersection does not change, depending on the incoming road.\r\nWe should make sure to re-use the intersection shape during the computation an only change the (possibly influenced by turn restrictions) flags that indicate allowed entry.\r\n\r\nTo do so, we need to restructure the processing the following way:\r\n\r\n - [ ] make [this](https://github.com/Project-OSRM/osrm-backend/blob/3235f30a988a77a3f0dcb100d65c8f37eac244c8/src/extractor/edge_based_graph_factory.cpp#L366) loop go over all intersections\r\n  - [ ]  instead of [here](https://github.com/Project-OSRM/osrm-backend/blob/3235f30a988a77a3f0dcb100d65c8f37eac244c8/src/extractor/edge_based_graph_factory.cpp#L378) compute the intersection shape (at node_u) [here](https://github.com/Project-OSRM/osrm-backend/blob/3235f30a988a77a3f0dcb100d65c8f37eac244c8/src/extractor/edge_based_graph_factory.cpp#L368)\r\n - [ ] loop over all incoming edges [here](https://github.com/Project-OSRM/osrm-backend/blob/3235f30a988a77a3f0dcb100d65c8f37eac244c8/src/extractor/edge_based_graph_factory.cpp#L369) and set the correct turn-types/entry-allowed-flags [here](https://github.com/Project-OSRM/osrm-backend/blob/3235f30a988a77a3f0dcb100d65c8f37eac244c8/src/extractor/edge_based_graph_factory.cpp#L378-L384)\r\n\r\nFrom the potential, we could be looking at a speed-up in creating the edge-based graph factory anywhere between two and three (given that the turn analysis still isn't free and the average degree of all nodes is somewhere around 2-4)."},"comment":{"url":"https://api.github.com/repos/Project-OSRM/osrm-backend/issues/comments/264214694","html_url":"https://github.com/Project-OSRM/osrm-backend/issues/3313#issuecomment-264214694","issue_url":"https://api.github.com/repos/Project-OSRM/osrm-backend/issues/3313","id":264214694,"user":{"login":"MoKob","id":12932279,"avatar_url":"https://avatars.githubusercontent.com/u/12932279?v=3","gravatar_id":"","url":"https://api.github.com/users/MoKob","html_url":"https://github.com/MoKob","followers_url":"https://api.github.com/users/MoKob/followers","following_url":"https://api.github.com/users/MoKob/following{/other_user}","gists_url":"https://api.github.com/users/MoKob/gists{/gist_id}","starred_url":"https://api.github.com/users/MoKob/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MoKob/subscriptions","organizations_url":"https://api.github.com/users/MoKob/orgs","repos_url":"https://api.github.com/users/MoKob/repos","events_url":"https://api.github.com/users/MoKob/events{/privacy}","received_events_url":"https://api.github.com/users/MoKob/received_events","type":"User","site_admin":false},"created_at":"2016-12-01T16:07:54Z","updated_at":"2016-12-01T16:07:54Z","body":"This just landed"}}
{"actor":{"display_login":"MoKob"}}