Differences in methods of constructing graph and calculating the shortest path

Specific Domains Graphs
, , , ,
1

Hi. I am new to using LightGraphs and SimpleWeightedGraph and have a few questions regarding their usage:

  1. I see that edges with zero weights are ignored when using add_edge! to define edges (also mentioned here); however, if I define the graph using sources, destination, and weights vector, it seems to account for zero weight edges correctly (see below). So, can I safely use the second way of defining a graph if I have zero weight edges os is there a catch?
using LightGraphs, SimpleWeightedGraphs

g = SimpleWeightedGraph(5)
add_edge!(g, 1, 2, 0.5)
add_edge!(g, 1, 4, 0.5)
add_edge!(g, 1, 5, 1)
add_edge!(g, 2, 3, 0.5)
add_edge!(g, 2, 4, 0.2)
add_edge!(g, 3, 4, 0) #Throws warning: adding edges with a zero weight to this graph type has no effect.
add_edge!(g, 4, 5, 0)

print(enumerate_paths(dijkstra_shortest_paths(g, 1), 5))
# Output: [1, 5] -> This is incorrect 

#Defining the same graph in a different way
sources = [1,1,1,2,2,3,4]
destinations = [2,4,5,3,4,4,5]
weights = [0.5, 0.5, 1, 0.5, 0.2, 0, 0]

g = SimpleWeightedGraph(sources, destinations, weights)
print(enumerate_paths(dijkstra_shortest_paths(g, 1), 5))

# Output: [1, 4, 5] -> This is correct
  1. Another difference I noticed is if I don’t define the nodes continuously starting from 1,
    then constructing a graph using add_edges! throws an error, whereas using the second method works perfectly fine.
using LightGraphs, SimpleWeightedGraphs 

# Here the nodes are represented as '10, 20, 30, 40, and 50 (previously there were 1,2,3,4,5)'
g = SimpleWeightedGraph(5)
add_edge!(g, 10, 20, 0.5)
add_edge!(g, 10, 40, 0.5)
add_edge!(g, 10, 50, 1)
add_edge!(g, 20, 30, 0.5)
add_edge!(g, 20, 40, 0.2)
add_edge!(g, 30, 40, 0) 
add_edge!(g, 40, 50, 0)

print(enumerate_paths(dijkstra_shortest_paths(g, 10), 50))

ERROR: LoadError: BoundsError: attempt to access 5-element Vector{Float64} at index [10]

using LightGraphs, SimpleWeightedGraphs

# Defining graph using this method works fine even with discontinuous nodes!
sources = [10,10,10,20,20,30,40]
destinations = [20,40,50,30,40,40,50]
weights = [0.5, 0.5, 1, 0.5, 0.2, 0, 0]

g = SimpleWeightedGraph(sources, destinations, weights)
print(enumerate_paths(dijkstra_shortest_paths(g, 10), 50))

# Output: [10, 40, 50] -> This is correct

Is this expected behavior, or should I not define zero weight edges and discontinuous nodes even with the second method of constructing a graph?

Considering the above two points, why would one want to use add_edge! instead of the second method, which clearly is more generic?

  1. If I am trying to simply find the shortest distance between two nodes in a large graph (say 1000 nodes and 100,000 edges), then what is the most efficient way of doing so? Currently, I execute enumerate_paths(dijkstra_shortest_paths(g, s), d), where s and d are the nodes between which I want to find the minimal path. I suspect that dijkstra_shortest_path(g, s) evaluates the shortest path between s and all other nodes, and then calling enumerate_paths returns the path between s and d specifically. Am I wrong? If not, can I somehow avoid the extra time spent calculating the distance between s and every other node, but rather directly get the path/distance between s and d—[I may be totally wrong here, any corrections and suggestions appreciated].

  2. enumerate_paths(...) return the shortest path; however, is there a built-in function that also returns the distance (I understand that I can calculate it once I have the path, but I am just curious).

  3. Lastly, I don’t see any major difference in the execution time when I use LightGraphs.Parallel for large graphs (~1000 nodes, ~100,000 nodes). I do the usual addprocs(n) at the start of the code and then Parallel.dijkstra_shortest_paths(g, s). Is this the correct way, or am I missing out on something?

Thanks!