Question about performance of dijkstra_shortest_paths

[KristofferC]

Hello,

I want to find the shortest distance between two points under the constrain that the length of each edge in the path has to be smaller than a given value. I construct the graph in a naive way by looping over my points like this:

function construct_graph_naive(points::Array{Point, 1}, radius::Float64)
  n_points = length(points)
  inc_list = simple_inclist(n_points, is_directed=false)
  dists = Float64[]
  for i = 1:n_points
    for j = i+1:n_points
      point_1 = points[i]
      point_2 = points[j]
      dist = distance_point(point_1, point_2) # Computes the distance between two points
      if dist < radius
        add_edge!(inc_list, i, j)
        push!(dists, dist)
      end
    end
  end
  return inc_list, dists
end

This generates a graph with ~12 000 vertices and ~100 000 edges. I then call dijkstra on the returned values:

path_state = dijkstra_shortest_paths(inc_list, dists, start_node)

The call to dijkstra currently takes around 4.6 seconds. Comparing these 4.6 seconds for a 12 000 vertices, 100 000 edge graph and the stated "a benchmark shows that it takes about 15 milliseconds to run the Dijkstra’s algorithm over a graph with 10 thousand vertices and 1 million edges on a macbook pro." makes me think I am doing something wrong.

The same graph in scipys dijkstra (http://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.sparse.csgraph.dijkstra.html) takes on the same computer about 0.2 seconds.

I am quite new to Julia so I might have made some obvious performance killing mistake.

Thanks in advance!

[mlubin]

Try using simple_graph instead of simple_inclist.

[KristofferC]

And we are down to 9 ms! I don't really know about the strengths and weaknesses in the different graph data structures but obviously the graph was much faster than the inclist.

Thank you!

[KristofferC]

I also noticed that the time to take the graph went down by a factor of 10 as well. Guess it pays off to know your data structures!

[mlubin]

It's not just data structures, this was probably made much slower by #135.