Proposal: Make raph operators work with different graph types than SimpleGraph and SimpleDiGraph

[simonschoelly]

Here is a proposal for something I would like to work on and I would like your inputs.

Graph operators are functions that take a number of graphs and return another graphs. Most of them such as complement and blockiag are defined in operators.jl, but there are also others such as transitiveclosure and squash.

Currently most of them are defined only for SimpleGraph and SimpleDiGraph. Others, such as induced_subgraph are defined for AbstractGraph but would very likely fail if used on arbitrary graph type. The reason for this is are:

• Not all functions necessary to execute these operations are defined for all subtypes of AbstractGraph; such functions are: copying graphs, creating empty graphs, adding or removing vertices and edges.
• Even if these functions is defined, there are issues when vertices and edges store additional features - for example in some cases the resulting graph has edges that are not in any of the input graphs - in that cases it is not clear how we should populate these features and what the calling signature is to add these features.

Furthermore some operations such as blockdiag (merges two graphs without adding edges between the) are only defined for two input graphs. But especially for this function but probably also for others it would be useful if someone could pass an arbitrary amount of graphs. If someone wants to mere 8 graphs they would currently need 7 calls to that operator.

My proposal is now as follows:

• We define the operators such that the leftmost argument to the operator defines the output.
• The leftmost argument can also be a graph type (not an instance of that type) - that type is the resulting type of that operator.
• We create operators with the leftmost argument being SimpleGraph and SimpleDiGraph. The other input graphs can be arbitrary subtypes of AbstractGraph but we just threat them as Simple{Di}Graph.
• For other graph types in other packages we leave it to these packages to create there own methods with their graph type being the leftmost argument.

To give some examples, here is the methods I would create for the unary operator complement:

complement(g::SimpleGraph{T}) # -> SimpleGraph{T}
complement(::Type{SimpleGraph}, g::AbstractGraph{T}) # -> SimpleGraph{T}
complement(::Type{SimpleGraph{S}}, g::AbstractGraph) # -> SimpleGraph{S}

and here is an example for the n-ary (currently binary) operator blockdiag

blockdiag(g::SimpleGraph{T}, hs::Vararg{<:AbstractGraph}) # -> SimpleGraph{T}

# This one is not completely type stable (will show up yellow with @code_warntype)
# as we calculate the smallest eltype for the resulting graph. An alternative would be
# to always choose Int or Int64 - but I think this is not as bad as one can always use
# the signature defined below if they need complete type stability.
blockdiag(::Type{SimpleGraph}, hs::Vararg{<:AbstractGraph}) # -> SimpleGraph{S} where S is sufficient large.

blockdiag(::Type{SimpleGraph{S}}, hs::Vararg{<:AbstractGraph}) # -> SimpleGraph{S}

Some other points:

• If one need to pass other arguments to the operators they can do this with keyword arguments - these arguments might depend on the specific implementation, e.g.
  • How to handle self-loops
  • How to handle metadata
• How should we handle operators on a mixture of directed and undirected graphs? For now I would propose:
  • If the leftmost argument is directed and some argument further to the right is undirected we just handle this argument as it was a directed graph where for every edge also the reverse edge is in that graph.
  • If the leftmost argument is undirected and some rgument further to the right is directed it is not so clear if an edge should count if it only goes in one direction - for now I would just throw an error to avoid an surprises.
• It might be tempting to define default operator implementations such as

  op(g::AbstractGraph{T}) = op(SimpleGraph{T}, g)

  but this might lead to unexpected surprises for other graph types - so we should leave the implementation of op to them.
• For a lot of operators such as blockdiag we could also define inplace versions i.e. blockdiag! that write to their first argument but I would leave that for later.
• Even with this there might still be surprises in the future, if for example SimpleWeightedGraphs.jl implements

  op(g::SimpleWeightedGraph{T}, h::AbstractGraph)

  such that any edge from h not in g is simply populated with the weight one(T) but then later adds an extension

  op(g::SimpleWeightedGraph{T}, h::MetaGraph; edgekey::Symbol)

  that uses edgekey to get the value of an edge in h then that could lead to breaking changes. I don't know how to get around that - but I also don't think that is a case that appears often.

[Krastanov]

This would be great! Generally in favor; here are a few comments:

1. This is a well-defined well-scoped issue that can be a good target for a bounty, hopefully leading to more contributors to the codebase long term. If you are comfortable with that idea and are available to mentor a contributor and do not mind potentially a 3 month delay while we cycle through volunteers, the NSF can provide a 400$ bounty for this work (we will need to scope it a bit more clearly and potentially increase/decrease the bounty depending on scope)

2. Should we consider special-casing reduce(::typeof(graph_operator), graphs)? There has been a lot of thought about how to best structure that type of code in Base recently: WIP: The great pairwise reduction refactor JuliaLang/julia#58418

3. Handling metadata was a long-discussed and eventually well-engineered challenge for DataFrames.jl. Even just on the basis of ecosystem consistency, I would suggest stealing as much as possible from their approach: https://discourse.julialang.org/t/dataframes-jl-metadata/84544 and https://github.com/JuliaData/DataFrames.jl/pull/3055/files#diff-5ec522580bc313447378c5cab2f8fb37d72aeba71dbb98ca8d3b50a05e2f163a

4. It might be useful to track in devdocs or in comments or even through static analysis which operators are implemented in which fashion:

   • (bad, probably broken) uses direct access to internal fields of graph structs
   • (ok, probably slow) internally converts everything to SimpleGraph before performing the operation
   • (best, probably slow) internally uses only standard Graph API (iteration over edges/vertices, etc)

Working on the static analysis tools for something like that would be fun on its own.