Which functions go where?

gdalle commented 1 year ago

Splitting out GraphsBase.jl means deciding which functions

Have to be overridden by users (the "interface")
Rely on the interface while remaining reasonably basic (the "core")
Rely on the interface and core while adding more sophisticated functionality (the "algorithms")

The interface and core will go in GraphsBase.jl, the algorithms will remain in Graphs.jl.

gdalle commented 1 year ago

First classification attempt based on

@etiennedeg please comment and correct so I can update it:

Function	Interface	Core	Algorithms
`src(e)`	x
`dst(e)`	x
`zero(g)`		x
`vertices(g)`	x
`nv(g)`		x
`has_vertex(g, v)`		x
`edges(g)`	x
`ne(g)`		x
`has_edge(g, e)`		x
`edges(g, u, v)`	x
`has_self_loops(g)`		x
`num_self_loops(g)`			x
`[in/out_]edges(g, v)`	x
`[in/out_]neighbors(g, v)`		x
`common_[in/out_]neighbors(g, v)`			x
`[in/out_]degree(g, v)`		x
`[in/out_]degree(g)`			x
`[in/out_]Δ(g)`			x
`[in/out_]δ(g)`			x
`[in/out_]degree_histogram(g)`			x
`[in/out_]density(g)`			x
`[in/out_]adjacency_matrix(g)`		x
`add/rm_vertex!(g)`	x
`add/rm_vertices!(g)`		x
`add/rm_edge!(g)`	x
`add/rm_edges!(g)`		x
`weight(e)`	x
`weights(g)`	x
`set_weight!(g, e)`	x
`squash(g)`		x
`noallocextreme(f, comp, init, g)`			x
`reverse(g)`		x
`induced_subgraph(g)`		x
`intersect(g, h)`			x
`join(g, h)`			x
`union(g, h)`			x
`cartesian_product(g, h)`			x

Note that core functions can still be overridden for performance.

The list above also makes renaming propositions to homogeneize the style.

etiennedeg commented 1 year ago

I have some doubts on the following functions:

squash : would it be defined only for integer graphs? Maybe algorithm...
reverse(g) (and probably reverse(e) also): I don't know how well this is defined. If we want to reverse an edge with metadata, I suppose we want to keep it, however, this is not always possible. For example, we define a directed graph with two types of edges, structural edges, and edges corresponding to the transitive closure of the graph, with as metadata a path between these two vertices. If we reverse the edge, the metadata is no longer a valid path between its extremities. However we can totally have a wrapper than allows to navigate the graph in reverse direction.
induced_subgraph: algorithm maybe?

gdalle commented 1 year ago

squash : would it be defined only for integer graphs? Maybe algorithm...

Honestly we could also get rid of it. Maybe I'll open an issue on deprecations

reverse(g) (and probably reverse(e) also): I don't know how well this is defined.

If we have reverse(e) we can define reverse(g), so maybe reverse(e) should be part of the interface?

induced_subgraph: algorithm maybe?

I don't know, no strong opinion on my end.

etiennedeg commented 1 year ago

My point is that reverse(e) is already ill-defined for meta-edges, for the example I gave on my last message, I have no idea what reverse could return.

gdalle commented 1 year ago

My point is that reverse(e) is already ill-defined for meta-edges, for the example I gave on my last message, I have no idea what reverse could return.

Indeed so that is something we should ask users to implement

JuliaGraphs / GraphsBase.jl

Which functions go where? #4