Neighbors related functions give wrong result after `rem_edge!` because it just set edge weight to 0

[ChasingZenith]

Removing an edge just sets the edge weight to 0 #43 Another bug brought by this implementation is that neighbors related functions such as neighbors, inneighbors and outneighbors give wrong result.

julia> g = SimpleWeightedGraph([1 0 ; 0 1])
g {2, 2} undirected simple Int64 graph

julia> inneighbors(g, 2)
Int64[2]

julia> rem_edge!(g, edgetype(g)(2, 2))

julia> inneighbors(g, 2)
Int64[2] # it will be Int64[] if we use SimpleGraph or SimpleDiGraph

It is because we never dropzeros! every time we remove an edge. I think that should be corrected at least when we run neighbors because rem_edge! is explicitly declaring that link is removed so they should no longer be neighbors to each others.

[sbromberger]

Definitely a bug, but dropzeros! is very expensive. I suppose we can create a warning in the notes that modifying a SWG is expensive, and do this.

[ChasingZenith]

How does SimpleGraph solve this problem. Do they use dropzero! everytime?

[sbromberger]

We don't use sparse matrices in SimpleGraph.

[jsundram]

This is super confusing. I ended up writing two functions to workaround this (after pulling some hair out):

function real_neighbors(g::SimpleWeightedGraph, src::Int)::Array{Int}
    return collect(filter(n -> has_edge(g, src, n), neighbors(g, src)))
end

function real_edges(g::SimpleWeightedGraph)::Array{AbstractEdge}
    return filter(e -> has_edge(g, e.src, e.dst), collect(edges(g)))
end

I'd rather have rem_edge! throw an exception when used on this graph type, or have neighbors (and edges...) do filtering similar to what I wrote above.

[sbromberger]

It's definitely a bug. I'm out of pocket until the week of the 8th but plan on thinking about the best way to solve this until I can come up with some code. Nothing I've thought about so far is cost-neutral so there may be a (significant) performance impact to edge removal.

Edited: we should fix this in rem_edge because neighbors is performance critical for a huge number of functions.

[FalafelGood]

Why not write a function like hrd_rem_edge() that incorporates the dropzero! and can be used as a less cost-efficient method when needed? You can Leave the warning in the rem_edge docs and give the user their choice of performance. Win win I think. (Edit: Or vice versa -- make a function sft_rem_edge() which sets the weight to zero and have rem_edge() literally remove the edge. That's probably more accurate)

[sbromberger]

@FalafelGood the reason is that we don't keep bugs around. Correctness is of paramount importance, so once we've labeled something as a bug, we have to fix it, even if there's a performance hit to doing so.

[Wikunia]

After I read "Note that adding or removing vertices or edges from these graph types is not particularly performant" in the readme I thought this will be done but it seems like the bug is still there? I'm not really sure when one should use this package and when to use MetaGraphs. Maybe you can clarify on that :wink: Thank you