Deleting edges from SimpleWeightedDiGraph based on edge weight

Specific Domains Graphs
1

Hi,

i would like to remove multiple edges from a SimpleWeightedDiGraph based on their weight.

However, naively looping over edges as in the example below does not yield the desired result, presumably because the internal ordering of the edges is changed when an edge is removed.

using LightGraphs, SimpleWeightedGraphs

g = SimpleWeightedDiGraph([1, 2, 3], [2, 3, 1], [1.0, 6.0, 4.0])
c = 5.0
for e in edges(g)
    if weight(e) < c 
        rem_edge!(g, e) 
    end
 end

julia> ne(g)
3

Does anyone have an efficient solution for this?

Best
Jakob

2

the idiomatic way to do this is to collect(edges(g)) in the for loop. This allocates.

The quick-n-dirty, not-guaranteed-to-work-in-the-future, you’re-on-your-own, please-don’t-do-this way is to manipulate the sparse matrix directly:

g.weights[g.weights .< c] .= 0

However: there’s a bug in edges(g) for SimpleWeightedGraphs in that zero-weight edges are still showing up. This is a persistent problem for us with no great solution.

presumably because the internal ordering of the edges is changed when an edge is removed.

Nope. It’s this issue with structural vs stored zeros. I’ll try to come up with an acceptable fix.

3

If you want to try out the sbromberger/fix-zeros branch of SimpleWeightedGraphs and report back, I’d appreciate it. Note that things like neighbors and edges are now iterators, so plan accordingly.

4

Thanks for the quick and helpful reply!

I tried the branch and the edge removal example works fine now.
however, when I try to get degrees:

g = SimpleWeightedDiGraph([1, 2, 3], [2, 3, 1], [1.0, 6.0, 4.0])
outdegree(g)

I now get the following error:

<strong>MethodError: no method matching length(::Base.Iterators.Filter{Base.var"#58#59"{typeof(iszero)},SubArray{Int64,1,Array{Int64,1},Tuple{UnitRange{Int64}},true}})</strong>

<strong>Closest candidates are:
length(!Matched::Core.SimpleVector) at essentials.jl:593
length(!Matched::Base.MethodList) at reflection.jl:849
length(!Matched::Core.MethodTable) at reflection.jl:923
...</strong>
in top-level scope at [untitled:15](#)
in outdegree at [LightGraphs\UPjU9\src\core.jl:97](#)
in outdegree at [LightGraphs\UPjU9\src\core.jl:97](#)
in collect at [base\array.jl:622](#)
in iterate at [base\generator.jl:47](#)
in at [base\none](#)
in outdegree at [LightGraphs\UPjU9\src\core.jl:96](#)

This seems to be due to the type change of outneighbors. Calling length on the .itr field of neighbors does the job:

onb = outneighbors(g, 1)
length(onb.itr)

Also, i noticed that when i convert a SimpleWeightedDiGraph to a SimpleDiGraph, the edge directions seem to revert:

[println(e) for e in edges(g)]

Edge 1 => 2 with weight 1.0
Edge 2 => 3 with weight 6.0
Edge 3 => 1 with weight 4.0

[println(e) for e in edges(SimpleDiGraph(g))]

Edge 1 => 3
Edge 2 => 1
Edge 3 => 2

Not sure if this is expected behavior or if maybe I’m not supposed to do it like that, though.

5

Both of those are bugs. The first is because we switched the neighbors functions to be iterators, and you can’t get the length of an iterator. The second needs some more exploration but it’ll be a simple fix.