LightGraphs: inconsistency between weighted and non-weighted graphs?

Specific Domains Graphs
1

I want to get the unweighted adjacency matrix from a weighted graph. I thought that weighs gives the weighted adjacency matrix and adjacency_matrix gives the unweighted adjacency matrix. I found out this is not true:

gw = SimpleWeightedDiGraph(2)
{2, 0} directed simple Int64 graph with Float64 weights

julia> add_edge!(gw,1,2,3)
true

julia> adjacency_matrix(gw)
2×2 SparseMatrixCSC{Float64,Int64} with 1 stored entry:
  [1, 2]  =  3.0

Can this be done? Is there a function that will give me the unweighted adjacency matrix?

So I decided to cast my SimpleWeightedDiGraph to a SimpleDiGraph and then take the adjacency matrix:

julia> g = SimpleDiGraph(gw)
{2, 1} directed simple Int64 graph

julia> adjacency_matrix(g)
2×2 SparseMatrixCSC{Int64,Int64} with 1 stored entry:
  [2, 1]  =  1

For some reason this gives me the transposed adjacency matrix! What is happening here? Is this how this should work?

2

Is there a function that will give me the unweighted adjacency matrix?

You can get the unweighted (Float64 ones) adjacency matrix just by coercing the weighted AM to 1s:

am = min.(adjacency_matrix(gw), 1.0)

For some reason this gives me the transposed adjacency matrix! What is happening here? Is this how this should work?

This is probably a bug. We’ve done some (in retrospect) silly things in an effort to improve performance of AM generation and this looks indicative of one of those things.

The bug is in the construction of the DiGraph from the SimpleWeightedDiGraph:

julia> zz = DiGraph(gw)
{2, 1} directed simple Int64 graph

julia> collect(edges(zz))
1-element Array{LightGraphs.SimpleGraphs.SimpleEdge{Int64},1}:
 Edge 2 => 1
3

The workaround you propose assumes that the weights are larger than 1, which is not always the case for me.

4

Good point, but I only have your example to go on. Here’s a more general solution that gives you Ints:

am = (!iszero).(adjacency_matrix(gw))
5

Thanks, that works.

6

Awesome. I’ll try to remember to file a bug report for the constructor issue. For now, if you need to do this, just create it using the adjacency matrix:

dg = DiGraph(adjacency_matrix(gw))
7

Out of curiosity, is there any particular reason it was decided that adjacency_matrix and weights should return the same matrix? I mean what is the point of weights if it was decided that adjacency_matrix will return the weighted adjacency matrix?

8

In the case of SimpleWeightedGraphs, it was primarily because this is an O(1) operation that does not allocate, and it met the needs of the author/user at the time.

I mean what is the point of weights if it was decided that adjacency_matrix will return the weighted adjacency matrix?

I’m not sure that the fact that two functions return the same result in a particular implementation of a graph structure is a valid criticism. For SimpleGraphs 1:nv(g) and vertices(g) return the same thing, but we encourage their use in different scenarios. weights is not necessarily guaranteed to return a “real” matrix (look at DefaultDistance in SimpleGraphs for the example); just something that can be indexed into to retrieve a weight value.