Help with LightGraphs.jl

Specific Domains Graphs
,
1

Hello,

I am trying to move away from the R package iGraph to LightGraphs.jl but am having difficulty.
I have a food web where each species is a node and a link connects it to another species (node) - this is translated into a binary array. My end goal is to have an array with link distances (how many link are between two species). For example, the distance between species 1 and species 4 is 2.

image
image1107×380 10.2 KB

In R the code is

library(igraph)
one.g.mat = matrix(c(0,0,0,0,1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0), nrow = 5, byrow = TRUE)
one.g = graph_from_adjacency_matrix(one.g.mat, mode = "undirected")
dists = shortest.paths(one.g)
#output - the distances between each species and the other species
#     [,1] [,2] [,3] [,4] [,5]
#[1,]    0    3    3    2    1
#[2,]    3    0    2    1    2
#[3,]    3    2    0    1    2
#[4,]    2    1    1    0    1
#[5,]    1    2    2    1    0

In Julia I am struggling to do something similar. I assume I need to use a shortest path algorithm, but I am unable to get it to work.

using LightGraphs

one.g.mat= [0 0 0 0 1;
        0 0 0 1 0;
        0 0 0 1 0;
        0 0 0 0 1;
        0 0 0 0 0]

test_graph = DiGraph(one.g.mat)
a = adjacency_matrix(test_graph) 
a_star(a, s, t[, distmx][, heuristic]) # syntax: unexpected ","
dijkstra_shortest_paths(a, srcs, distmx=weights(a)) # MethodError: no method matching weights(::SparseArrays.SparseMatrixCSC{Int64, Int64})

Can someone help me?

2

Hi,

julia> a_star(test_graph, 3, 5) # shortest path between 3 and 5
2-element Vector{LightGraphs.SimpleGraphs.SimpleEdge{Int64}}:
 Edge 3 => 4
 Edge 4 => 5

julia> a_star(test_graph, 1,2) # shortest path between 1 and 2 (does not exist because test_graph is directed)
LightGraphs.SimpleGraphs.SimpleEdge{Int64}[]

julia> dijkstra_shortest_paths(test_graph, 2) # compute all shortest paths from 2 to the other nodes
LightGraphs.DijkstraState{Int64, Int64}([0, 0, 0, 2, 4], [9223372036854775807, 0, 9223372036854775807, 1, 2], [Int64[], Int64[], Int64[], Int64[], Int64[]], [0.0, 1.0, 0.0, 1.0, 1.0], Int64[])
# The LightGraphs.DijkstraState is really not well documented
# [0, 0, 0, 2, 4] parents to build the shortest paths
# [9223372036854775807, 0, 9223372036854775807, 1, 2]  lengths of shortests paths
# [Int64[], Int64[], Int64[], Int64[], Int64[]] Ignore I think
# [0.0, 1.0, 0.0, 1.0, 1.0] number of shortest paths
# Int64[] ignore I think

julia> println(floyd_warshall_shortest_paths(test_graph)) # all shortest paths between all pairs of vertices
LightGraphs.FloydWarshallState{Int64, Int64}([0 9223372036854775807 9223372036854775807 9223372036854775807 1; 9223372036854775807 0 9223372036854775807 1 2; 9223372036854775807 9223372036854775807 0 1 2; 9223372036854775807 9223372036854775807 9223372036854775807 0 1; 9223372036854775807 9223372036854775807 9223372036854775807 9223372036854775807 0], [0 0 0 0 1; 0 0 0 2 4; 0 0 0 3 4; 0 0 0 0 4; 0 0 0 0 0])
# first list : distances
# second list : parents

julia> g = SimpleGraph(test_graph) # cast to an undirected graph
{5, 4} undirected simple Int64 graph

julia> println(floyd_warshall_shortest_paths(g)) # what you are searching for
LightGraphs.FloydWarshallState{Int64, Int64}([0 3 3 2 1; 3 0 2 1 2; 3 2 0 1 2; 2 1 1 0 1; 1 2 2 1 0], [0 4 4 5 1; 5 0 4 2 4; 5 4 0 3 4; 5 4 4 0 4; 5 4 4 5 0])

I’m surprised there is no undirected mode for shortest paths search in Lightgraphs (At least I didn’t found one). Casting can be costly, especially in LightGraphs.

3

You can do it with LightGraphs.jl, just use an undirected graph for your example, since there is no path from node 1 to node 4 in the directed version of the graph.

You can rebuild your adjacency matrix so that it is symmetric and pass it to SimpleGraph, or just build it edge, by edge:

using LightGraphs

g=SimpleGraph(5)
add_edge!(g,1,5)
add_edge!(g,2,4)
add_edge!(g,3,4)
add_edge!(g,4,5)

Then, you can create your distance matrix as follows:

distance = zeros(Int,5,5)

for i in vertices(g), j in vertices(g)
    distance[i,j] = length(a_star(g,i,j))
end

julia> distance
5×5 Matrix{Int64}:
 0  3  3  2  1
 3  0  2  1  2
 3  2  0  1  2
 2  1  1  0  1
 1  2  2  1  0

Note: done with LightGraphs v1.3.5

1 Like
4

Using floyd_warshall_shortest_paths is much more efficient to compute the distance matrix than iterating an a_star over all pairs of nodes.

5

Thank you for your replies - I am indeed looking for something like floyd_warshall_shortest_paths.

How can I access the first element of floyd_warshall_shortest_paths (the distances)? I will need to save this.

@hdavid16 My food webs are large so it would not be practical to add edges manually.

6 
julia> result = floyd_warshall_shortest_paths(g)

julia> result.dists
5×5 Matrix{Int64}:
 0  3  3  2  1
 3  0  2  1  2
 ⋮           
 1  2  2  1  0

julia> result.parents
5×5 Matrix{Int64}:
 0  4  4  5  1
 5  0  4  2  4
 ⋮           
 5  4  4  5  0

At the bottom of the documentation, it is precised that almost all states returned from a shortest path computation have a dists field and a parents field
I don’t know if there is a way to avoid the computation of the undirected graphs… (cc @anon94023334)

1 Like
7

Thank you. I didn’t understand what was meant by

The above state types (with the exception of YenState) have the following common information, accessible via the type: .dists Holds a vector of distances computed, indexed by source vertex.

I was trying nonsense like g(.dists) and g[.dists].