# Help with LightGraphs.jl

**URL:** <https://discourse.julialang.org/t/help-with-lightgraphs-jl/66663>\
**Category:** Graphs\
**Tags:** package, lightgraphs\
**Created:** [August 19, 2021, 11:41am UTC](https://discourse.julialang.org/t/help-with-lightgraphs-jl/66663 "2021-08-19T11:41:21Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![HelgavonLichtenstein](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/helgavonlichtenstein/32/5005_2.png) [@HelgavonLichtenstein](https://discourse.julialang.org/u/HelgavonLichtenstein)\
**Post date:** [August 19, 2021, 11:41am UTC](https://discourse.julialang.org/t/help-with-lightgraphs-jl/66663/1 "2021-08-19T11:41:21Z")

</div>

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](https://global.discourse-cdn.com/julialang/original/3X/5/6/5626d7ba346e0898435875643c95435fc04a0313.png)

In R the code is

```julia
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](https://juliagraphs.org/LightGraphs.jl/v1.2/pathing.html#Shortest-Path-Algorithms-1), but I am unable to get it to work.

```julia
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?

---

<div class="post-metadata">

**Author:** ![etienne\_dg](https://avatars.discourse-cdn.com/v4/letter/e/fbc32d/32.png) [@etienne\_dg](https://discourse.julialang.org/u/etienne_dg)\
**Post date:** [August 19, 2021, 12:24pm UTC](https://discourse.julialang.org/t/help-with-lightgraphs-jl/66663/2 "2021-08-19T12:24:03Z")

</div>

Hi,

```julia
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`.

---

<div class="post-metadata">

**Author:** ![hdavid16](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hdavid16/32/11531_2.png) [@hdavid16](https://discourse.julialang.org/u/hdavid16)\
**Post date:** [August 19, 2021, 1:49pm UTC](https://discourse.julialang.org/t/help-with-lightgraphs-jl/66663/3 "2021-08-19T13:49:04Z")

</div>

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:

```julia
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:

```julia
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`

---

<div class="post-metadata">

**Author:** ![etienne\_dg](https://avatars.discourse-cdn.com/v4/letter/e/fbc32d/32.png) [@etienne\_dg](https://discourse.julialang.org/u/etienne_dg)\
**Post date:** [August 20, 2021, 6:58am UTC](https://discourse.julialang.org/t/help-with-lightgraphs-jl/66663/4 "2021-08-20T06:58:00Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![HelgavonLichtenstein](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/helgavonlichtenstein/32/5005_2.png) [@HelgavonLichtenstein](https://discourse.julialang.org/u/HelgavonLichtenstein)\
**Post date:** [August 20, 2021, 9:46am UTC](https://discourse.julialang.org/t/help-with-lightgraphs-jl/66663/5 "2021-08-20T09:46:20Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![etienne\_dg](https://avatars.discourse-cdn.com/v4/letter/e/fbc32d/32.png) [@etienne\_dg](https://discourse.julialang.org/u/etienne_dg)\
**Post date:** [August 20, 2021, 10:00am UTC](https://discourse.julialang.org/t/help-with-lightgraphs-jl/66663/6 "2021-08-20T10:00:07Z")

</div>

```julia
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](https://juliagraphs.org/LightGraphs.jl/latest/pathing/#Path-States), 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)

---

<div class="post-metadata">

**Author:** ![HelgavonLichtenstein](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/helgavonlichtenstein/32/5005_2.png) [@HelgavonLichtenstein](https://discourse.julialang.org/u/HelgavonLichtenstein)\
**Post date:** [August 20, 2021, 10:13am UTC](https://discourse.julialang.org/t/help-with-lightgraphs-jl/66663/7 "2021-08-20T10:13:24Z")

</div>

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]`.