Which functions go where?

[gdalle]

Splitting out GraphsBase.jl means deciding which functions

1. Have to be overridden by users (the "interface")
2. Rely on the interface while remaining reasonably basic (the "core")
3. 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]

First classification attempt based on

• Discussion : API for Graphs.jl 2.0 Graphs.jl#146
• https://juliagraphs.org/Graphs.jl/stable/core_functions/interface/
• https://juliagraphs.org/Graphs.jl/stable/core_functions/core/
• https://juliagraphs.org/Graphs.jl/stable/core_functions/operators/

@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]

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]

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]

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]

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