JuliaGraphs / JuliaGraphs/Graphs.jl
Hashing and equality of `SimpleGraphs.SimpleEdgeIter`
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
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- 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