Interface without needing `AbstractGraph`?

[MilesCranmer]

In https://juliagraphs.org/Graphs.jl/stable/ecosystem/interface/ it specifies that we need to subtype to AbstractGraph to use these methods. I am wondering if there could be a trait-based version instead? Since Julia doesn't allow multiple inheritance it means we wouldn't be able to depend on both our own abstract type (which includes non-graph objects) as well as interface with Graphs.jl

cc @robdancer. x-ref https://github.com/SymbolicML/DynamicExpressions.jl/pull/98#issuecomment-2284986304

[gdalle]

Ideally I'd love that, but it's even harder to test due to the notorious lack of interface specification in Julia. The AbstractGraph must have been introduced a decade ago or so, and at least it's a guarantee that you don't try to graphify anything and everything without being aware of it.

Additionally, I haven't yet found a traits package that does everything I want and doesn't muddy the stack traces. For instance the use of SimpleTraits here causes problem with JET's analysis in Julia v1.11, which we're gonna have to fix.

[gdalle]

See also:

• https://github.com/JuliaGraphs/GraphsBase.jl/issues/26

[MilesCranmer]

Is the issue that the current code relies on implementing methods on Base? From looking through https://juliagraphs.org/Graphs.jl/stable/first_steps/access/#Graph-access it seems like there shouldn't be any conflicts, no?

(Btw I really like Interfaces.jl which I use this in DynamicExpressions.)

[MilesCranmer]

Surely if https://github.com/JuliaCollections/AbstractTrees.jl works without a type hierarchy, Graphs.jl could also work? I don't see a fundamental reason one would work and not the other

[gdalle]

There's no fundamental reason to prevent it, indeed. But as with most other big changes people want from Graphs, it would require time and manpower that we don't have at the moment. And it would probably be breaking.

Is the issue that the current code relies on implementing methods on Base?

I hadn't even thought of that but it could indeed be a problem for eltype, reverse and zero, see https://juliagraphs.org/Graphs.jl/stable/core_functions/interface/.

(Btw I really like Interfaces.jl which I use this in DynamicExpressions.)

I do too, and I use it in GraphsInterfaceChecker.jl to formalize the AbstractGraph interface. But I think it is based on subtyping so it won't solve this specific issue. RequiredInterfaces.jl might be better suited.

[MilesCranmer]

I hadn't even thought of that but it could indeed be a problem for eltype, reverse and zero, see https://juliagraphs.org/Graphs.jl/stable/core_functions/interface/.

Probably the easiest thing to do is define a separate Graphs.eltype like

module Graphs

eltype(x) = Base.eltype(x)

end

Then you can overload as normal directly on Base.eltype within Graphs, and they would be forwarded through, but I would be able to extend the Graphs.eltype definition with my own types.