Hashing and equality of `SimpleGraphs.SimpleEdgeIter`

[mxhbl]

SimpleGraphs.SimpleEdgeIter implements ==, but does not have a custom Base.hash implementation, meaning that equal SimpleEdgeIters have differing hashes:

julia> using Graphs

julia> g1 = Graph(0);

julia> g2 = Graph(0);

julia> edges(g1) == edges(g2)
true

julia> hash(edges(g1)) == hash(edges(g2))
false

This breaks an important property of the == function and may lead to incorrect behavior of Dicts and Sets.

A straightforward way to fix this would be to implement something like this:

function Base.hash(edgeiter::Graphs.SimpleGraphs.SimpleEdgeIter, h::UInt)
    for edge in edgeiter
        h = hash(edge, h)
    end
    return h
end

But the problem with this is that ==(e1::SimpleEdgeIter, e2::AbstractVector{SimpleEdge}) is also defined, and the hash of a AbstractVector{SimpleEdge}, being an array, depends on the array hash seed and other Julia internals. Moreover, ==(e1::Set{SimpleEdge}, e2::SimpleEdgeIter is also defined and would imply that the value of hash(edgeiter) cannot depend on the order of the edges.

I guess the chance of this actually leading to problematic behavior is quite low, so maybe fixing this is not worth the effort. But in that case maybe the documentation of edges should warn against constructing Sets and Dicts of the returned edge iterator?

[Krastanov]

Here are some rambling comments and a suggestion for a fix at the very bottom:

Just as a reference about isequal, ==, and hash: https://stackoverflow.com/questions/57945372/when-should-i-use-vs-vs-isequal

isequal(a, b) implies hash(a) == hash(b)

If isequal is not defined, then it falls back to ==

My reading is that == is encouraged to do fancy things like NaN != NaN and -0.0 == 0.0, === is meant to be purely structural, and isequal exists for situations where the natural choice for == and hash are at odds.

So it is fine if ==(e1::SimpleEdgeIter, e2::AbstractVector{SimpleEdge}) is fancy and does extra equality checks, while isequal is simple and more structural and returns false for isequal(edges(g), collect(edges(g))) (and matches hash). If anything, I would actually find it confusing if the hashes of two different types of containers (of the same edges).

---

A straightforward way to fix this would be to implement something like this:

I am not a big fan of this particular fix because it is slow (hashes are meant to be fast, at the cost of the occasional collision). And for the reason mentioned above.

---

How about this:

julia> using Graphs

julia> Base.hash(e::T, h::UInt) where {T<:Graphs.SimpleGraphs.SimpleEdgeIter} = hash(hash(T, h), hash(e.g))

julia> g1 = Graph(0)
{0, 0} undirected simple Int64 graph

julia> g2 = Graph(0)
{0, 0} undirected simple Int64 graph

julia> hash(edges(g1)) == hash(edges(g2))
true

And if isequal is smart enough we can simplify it to hash(hash(SOME_CONSTANT, h), hash(e.g))

[mxhbl]

Thanks for your thoughts. I agree that having a separate isequal that returns false for isequal(edges(g), collect(edges(g))) is the most natural solution.

I also agree that the hashing should be fast, although a potential issue with your suggested hash is that it breaks if one of the graphs has extra unconnected vertices:

julia> g1 = Graph(1);

julia> g2 = Graph(2);

julia> edges(g1) == edges(g2)
true

julia> hash(edges(g1)) == hash(edges(g2))
false

The base Julia hash skips array elements once an array is large enough, maybe some sort of incomplete/sparse iteration over edges would also work here? Or maybe there are other graph invariants that can be hashed and are unaffected by unconnected vertices?

[Krastanov]

Oh, jeez, this is a great example of a failure... I concur with your last paragraph and do not have better suggestions.