Directed vs undirected edges

[gdalle]

The edge types in Graphs.jl are directed but used for undirected graphs too, in sometimes incoherent ways. Should there be an undirected edge acting like a set? And if so, should the syntax change, eg. other_endpoint(e,u)?

[gdalle]

Related:

• Should undirected edges == and hash be undirected? Graphs.jl#184
• Consistent approach to graph direction Graphs.jl#69
• todirected and toundirected interfaces Graphs.jl#220

[CameronBieganek]

Yeah, I think it makes sense for directed and undirected edges to be separate. In my GraphInterface/GraphTypes proposal, I have the following:

# GraphInterface.jl
abstract type AbstractEdge end
abstract type AbstractUndirectedEdge <: AbstractEdge end
abstract type AbstractDirectedEdge <: AbstractEdge end

# GraphTypes.jl
struct Edge <: AbstractUndirectedEdge
    # ...
end

...And I have Edge implemented so that Edge(1, 2) == Edge(2, 1) (and they hash the same).

[CameronBieganek]

One question: Do we want to support mixed graphs that include both directed and undirected graphs? I think that would have a significant impact on the interface design.

[gdalle]

I would love a design where undirected edges have the right to exist, and where we can turn src(e) / dst(e) into other_vertex(e, v) or neighbor(e, v).

As for mixed graphs, it's a good question. My feeling is that if we get the interface right for the edges, most things should... sorta just work out of the box? Like a Dijkstra algorithm would return a mixed vector of directed and undirected

[mofeing]

I like @CameronBieganek's decision on Edge(a,b) == Edge(b,a). If we also define Base.in such that DiEdge(a,b) in Edge(a,b) == DiEdge(b,a) in Edge(a,b) == true, that should solve most problems with mixed graphs.

Only thing I'm not sure about is the use of AbstractUndirectedEdge and AbstractDirectedEdge. What interface do they define? What are their assumptions? Specifically I'm thinking about the implications for hypergraphs #23 and open edges.