Open gdalle opened 9 months ago
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).
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.
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
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.
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)
?