JuliaGraphs / JuliaGraphs/Graphs.jl

Hashing and equality of `SimpleGraphs.SimpleEdgeIter`

Open
#504 4 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Julia
Stars
538
Forks
128
Avg merge
10h 25m
Merged PRs (30d)
2

Description

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?

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start at SimpleGraphs.SimpleEdgeIter's equality implementation and the edges entry point, then compare the Julia hash behavior referenced for AbstractVector and the existing equality with Set{SimpleEdge}. Determine whether consistent hashing can satisfy all stated equality relationships; done means either a tested hash design or documentation warning about using the returned iterator in Sets and Dicts.

Written by the indexing model from the issue text.

Assessment

Tech stack
julia
Domain
data
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
42/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.