Some utility functions, graph enumeration, completion, and is_property functions

[anandijain]

I’ve been seeing a lot of movement in Graphs lately! I wanted to take the opportunity to shamelessly promote a package https://github.com/anandijain/GraphHelpers.jl that houses some utilities I wrote for graphs but haven’t taken the time to extensively document or make into a PR.

There are a couple of things here though that I could see being useful to others.

The first is a simple interface for graph enumeration and completion. The interface requires defining possible_edges(g::MyGraphType). Additionally, if Graphs.Experimental.has_isomorph(g1::T, g2::T) is defined, we can enumerate all unique graphs (unlabeled).

https://github.com/anandijain/GraphHelpers.jl/blob/main/src/gen.jl This gives a pretty good sense of the interface.

Since the interface requires possible_edges we can make an interface for complete!(g::T) = add_edges!(g, possible_edges(g)) which is pretty insignificant but sometimes nice to have. We could then make Graphs.complete_(di)graph(n) = complete!(Simple(Di)Graph, n) where possible_edges(g::SimpleGraph{T}) where {T} = Iterators.map(x -> edgetype(g)(Tuple(x)), combinations(1:nv(g), 2))

I use it to enumerate all the non-isomorphic simple graphs, but keeping it generic to hypergraphs and multigraphs (although multigraphs might not exactly work since you need a bound on the multiedge degree, otherwise length(possible_edges(MultiGraph, 1)) == Inf.

An example of hypergraph enumeration can be found https://github.com/anandijain/Hypergraphs.jl/blob/main/test/hypergraphs.jl
I haven't written an algorithm for checking hypergraph isomorphism. I would like to at some point.

It was mostly just a hobby project to recreate some OEIS sequences like:

using GraphHelpers, Graphs, Test
gs = all_labeled_graphs.(1:5)
@test length.(gs) == GraphHelpers.n_labeled_graphs.(1:5)

ug = unique_graphs.(gs)
ag = all_graphs.(1:5)
@test all(map(x -> GraphHelpers.is_set_isomorphic(x), zip(ug, ag)))
@test length.(ag) == [1, 2, 4, 11, 34] # A000088

cgs = map(xs -> unique_graphs(filter(is_connected, xs)), gs)
@test length.(cgs) == [1, 1, 2, 6, 21] # OEIS A001349

It also houses some is_property functions, like is_complete, is_tree, and is_star for SimpleGraphs. I also wanted to implement is_planar, but haven't gotten there. These are maybe not the most performant, but for people just learning and playing with graphs they may be sufficient.

If this isn't useful then of course we should keep it out of Graphs.jl.

Thanks