{"action":"created","issue":{"url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/496","repository_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl","labels_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/496/labels{/name}","comments_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/496/comments","events_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/496/events","html_url":"https://github.com/JuliaGraphs/LightGraphs.jl/pull/496","id":186221664,"number":496,"title":"Faster and less memory hungry version of 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":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":11,"created_at":"2016-10-31T07:33:42Z","updated_at":"2016-11-01T01:51:11Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls/496","html_url":"https://github.com/JuliaGraphs/LightGraphs.jl/pull/496","diff_url":"https://github.com/JuliaGraphs/LightGraphs.jl/pull/496.diff","patch_url":"https://github.com/JuliaGraphs/LightGraphs.jl/pull/496.patch"},"body":"#495 Here is the proposed code. I have moved the definitions to the end of the file as they use custom BFS implemenation.\r\n\r\nHere is the performance testing code I used:\r\n```\r\ng = smallgraph(:tutte)\r\nprintln(\"tutte 3\")\r\n@time a = gdistances(g,3);\r\n\r\nsrand(1)\r\nfor i in 0:5\r\n    g = watts_strogatz(20000, 100, 0.5)\r\n    vl = sample(1:100, 5i, replace=false)\r\n    println(\"Watts-Strogatz \", vl)\r\n    @time a = gdistances(g,vl);\r\nend\r\n```\r\n\r\nIt seems to use less time and memory than the current implementation. I have also updated tests for a corner case of emply `source` collection."},"comment":{"url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/comments/257471006","html_url":"https://github.com/JuliaGraphs/LightGraphs.jl/pull/496#issuecomment-257471006","issue_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/496","id":257471006,"user":{"login":"jpfairbanks","id":2753998,"avatar_url":"https://avatars.githubusercontent.com/u/2753998?v=3","gravatar_id":"","url":"https://api.github.com/users/jpfairbanks","html_url":"https://github.com/jpfairbanks","followers_url":"https://api.github.com/users/jpfairbanks/followers","following_url":"https://api.github.com/users/jpfairbanks/following{/other_user}","gists_url":"https://api.github.com/users/jpfairbanks/gists{/gist_id}","starred_url":"https://api.github.com/users/jpfairbanks/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jpfairbanks/subscriptions","organizations_url":"https://api.github.com/users/jpfairbanks/orgs","repos_url":"https://api.github.com/users/jpfairbanks/repos","events_url":"https://api.github.com/users/jpfairbanks/events{/privacy}","received_events_url":"https://api.github.com/users/jpfairbanks/received_events","type":"User","site_admin":false},"created_at":"2016-11-01T01:51:11Z","updated_at":"2016-11-01T01:51:11Z","body":"Here is a basic profiling result based on @bkamins' benchmarkk\r\n```julia\r\njulia> g = watts_strogatz(10000, 2000, 0.5)\r\n{10000, 10000000} undirected graph\r\n\r\njulia> @profile gdistances(g, 3); Base.Profile.print()\r\n4533 ./event.jl:68; (::Base.REPL.##3#4{Base.REPL.REPLBackend})()\r\n 4533 ./REPL.jl:95; macro expansion\r\n  4533 ./REPL.jl:64; eval_user_input(::Any, ::Base.REPL.REPLBackend)\r\n   4533 ./boot.jl:234; eval(::Module, ::Any)\r\n    4533 ./<missing>:?; anonymous\r\n     4533 ./profile.jl:16; macro expansion;\r\n      4533 ...ia/v0.5/LightGraphs/src/traversals/bfs.jl:113; gdistances(::LightGraphs.Graph, ::Int64)\r\n       4533 ...ia/v0.5/LightGraphs/src/traversals/bfs.jl:99; gdistances!(::LightGraphs.Graph, ::Int64, ::Array{Int64,1})\r\n        4533 ./<missing>:0; (::LightGraphs.#kw##traverse_graph!)(::Array{Any,1}, ::LightGr...\r\n         4533 ...a/v0.5/LightGraphs/src/traversals/bfs.jl:73; #traverse_graph!#15(::Array{Int64,1}, ::LightGraphs.DummyEdg...\r\n          2048 .../v0.5/LightGraphs/src/traversals/bfs.jl:40; breadth_first_visit_impl!(::LightGraphs.Graph, ::Array{Int64...\r\n           14 ./array.jl:0; done(::Array{Int64,1}, ::Int64)\r\n           4  ./array.jl:381; done(::Array{Int64,1}, ::Int64)\r\n           56 ./array.jl:380; next(::Array{Int64,1}, ::Int64)\r\n           7  ./bool.jl:0; !(::Bool)\r\n           9  ./bool.jl:16; !(::Bool)\r\n           1  ...mes/.julia/v0.5/LightGraphs/src/core.jl:243; out_neighbors(::LightGraphs.Graph, ::Int64)\r\n          404  .../v0.5/LightGraphs/src/traversals/bfs.jl:41; breadth_first_visit_impl!(::LightGraphs.Graph, ::Array{Int64...\r\n           4  ./abstractarray.jl:0; get(::Array{Int64,1}, ::Int64, ::Int64)\r\n           26 ./abstractarray.jl:912; get(::Array{Int64,1}, ::Int64, ::Int64)\r\n          1169 .../v0.5/LightGraphs/src/traversals/bfs.jl:42; breadth_first_visit_impl!(::LightGraphs.Graph, ::Array{Int64...\r\n           8 ./essentials.jl:0; convert(::Type{Int64}, ::Int64)\r\n          547  .../v0.5/LightGraphs/src/traversals/bfs.jl:44; breadth_first_visit_impl!(::LightGraphs.Graph, ::Array{Int64...\r\n          322  .../v0.5/LightGraphs/src/traversals/bfs.jl:46; breadth_first_visit_impl!(::LightGraphs.Graph, ::Array{Int64...\r\n           1  ./promotion.jl:0; ==(::Int64, ::Int64)\r\n           10 ./promotion.jl:269; ==(::Int64, ::Int64)\r\n\r\n```\r\n\r\n\r\nThis appears to be the offender:  `1169 .../v0.5/LightGraphs/src/traversals/bfs.jl:42; breadth_first_visit_impl!(::LightGraphs.Graph, ::Array{Int64...`\r\n\r\nAnd Line 42 in the source is `v_edge = Edge(u,v)` \r\n\r\nWhich is inconsistent with my conception of the Pair{Int,Int} type being put on the stack instead of the heap."}}
{"actor":{"display_login":"jpfairbanks"}}