JuliaGraphs / JuliaGraphs/Graphs.jl

Should undirected edges == and hash be undirected?

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

Nobody has claimed this yet.

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

Description

Edges for SimpleGraph still consider their directedness when testing for equality and hashing. This is understandable given that SimpleEdge is used for directed graphs also. Is it worth considering adding a SimpleUndirectedEdge (or similar)? Something along the lines of:

...

function ==(e1::SimpleUndirectedEdge, e2::SimpleUndirectedEdge)
    return (src(e1) == src(e2) && dst(e1) == dst(e2)) ||
        (src(e1) == dst(e2) && dst(e1) == src(e2))
end

hash(e::SimpleUndirectedEdge, h::UInt) = hash(src(e), h) ⊻ hash(dst(e), h)

And then having SimpleGraph instead return edges of this type by default?

This would more easily allow users to maintain sets / dictionaries of edges. For instance, the reason I'm opening this is the associated awkwardness I encountered when implementing a minimum cycle basis that maintains such edge sets.

Happy to do a PR if this change is palatable.

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 by reviewing SimpleGraph's edge return behavior alongside SimpleEdge equality and hash methods. Compare the proposed SimpleUndirectedEdge behavior with the minimum cycle basis use case and existing edge-set expectations. Done means the project has an agreed direction for undirected edge identity and a corresponding, validated API change.

Written by the indexing model from the issue text.

Assessment

Tech stack
julia
Domain
data
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.