{"action":"created","issue":{"url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/495","repository_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl","labels_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/495/labels{/name}","comments_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/495/comments","events_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/495/events","html_url":"https://github.com/JuliaGraphs/LightGraphs.jl/issues/495","id":186173927,"number":495,"title":"Slow gdistances","user":{"login":"bkamins","id":6187170,"avatar_url":"https://avatars.githubusercontent.com/u/6187170?v=3","gravatar_id":"","url":"https://api.github.com/users/bkamins","html_url":"https://github.com/bkamins","followers_url":"https://api.github.com/users/bkamins/followers","following_url":"https://api.github.com/users/bkamins/following{/other_user}","gists_url":"https://api.github.com/users/bkamins/gists{/gist_id}","starred_url":"https://api.github.com/users/bkamins/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bkamins/subscriptions","organizations_url":"https://api.github.com/users/bkamins/orgs","repos_url":"https://api.github.com/users/bkamins/repos","events_url":"https://api.github.com/users/bkamins/events{/privacy}","received_events_url":"https://api.github.com/users/bkamins/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":10,"created_at":"2016-10-30T23:38:53Z","updated_at":"2016-12-04T21:18:32Z","closed_at":"2016-12-04T21:18:32Z","body":"In Julia 0.5 when I found that `gdistances` function was relatively slow. I have manually written BFS finding geodesic distances in `g` from `source` and it is significantly faster than the current implementation. Here is the code and some tests:\n\n```\nusing LightGraphs\n\nfunction new_gd(g::SimpleGraph, source)\n    n = nv(g)\n    dist = fill(-1, n)\n    queue = fill(-1, n)\n    queue[1] = source\n    dist[1] = 0\n    head = 1\n    tail = 1\n    while head <= tail\n        current = queue[head]\n        distance = dist[current] + 1\n        head += 1\n        for j in fadj(g, current)\n            if dist[j] == -1\n                dist[j] = distance\n                tail += 1\n                queue[tail] = j\n            end\n        end\n    end\n    dist\nend\n\nfunction test(size, d)\n    g = watts_strogatz(size, d, 0.5)\n    r = (@elapsed x2 = gdistances(g, 1)) / (@elapsed x1 = new_gd(g, 1))\n    @assert x1 == x2\n    lpad(round(r, 2), 7)\nend\n\ntest(5,1)\nfor d in [10, 60, 360], i in 0:2\n    s = 1000*5^i\n    println(\"graph size $(lpad(s, 5)) and avg. degree $(lpad(d, 3)): $(test(s, d))\")\nend\n```\n\nThe relative speedups are:\n\n```\ngraph size  1000 and avg. degree  10:   558.1\ngraph size  5000 and avg. degree  10:   33.72\ngraph size 25000 and avg. degree  10:   32.89\ngraph size  1000 and avg. degree  60:   70.34\ngraph size  5000 and avg. degree  60:   59.55\ngraph size 25000 and avg. degree  60:   51.31\ngraph size  1000 and avg. degree 360:  161.21\ngraph size  5000 and avg. degree 360:  144.11\ngraph size 25000 and avg. degree 360:  115.99\n```\n\nDo I miss something important in implementation of `gdistances` that is not covered in implementation of `new_gd` (the current implementation assumes that `source` is a single vertex but it can be simply extended)?\n"},"comment":{"url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/comments/264731974","html_url":"https://github.com/JuliaGraphs/LightGraphs.jl/issues/495#issuecomment-264731974","issue_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/495","id":264731974,"user":{"login":"sbromberger","id":941359,"avatar_url":"https://avatars.githubusercontent.com/u/941359?v=3","gravatar_id":"","url":"https://api.github.com/users/sbromberger","html_url":"https://github.com/sbromberger","followers_url":"https://api.github.com/users/sbromberger/followers","following_url":"https://api.github.com/users/sbromberger/following{/other_user}","gists_url":"https://api.github.com/users/sbromberger/gists{/gist_id}","starred_url":"https://api.github.com/users/sbromberger/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sbromberger/subscriptions","organizations_url":"https://api.github.com/users/sbromberger/orgs","repos_url":"https://api.github.com/users/sbromberger/repos","events_url":"https://api.github.com/users/sbromberger/events{/privacy}","received_events_url":"https://api.github.com/users/sbromberger/received_events","type":"User","site_admin":false},"created_at":"2016-12-04T21:18:32Z","updated_at":"2016-12-04T21:18:32Z","body":"I'm gonna close this out - feel free to continue discussion though. If we need to reopen it, just let me know."}}
{"actor":{"display_login":"sbromberger"}}