Efficient iteration over connected subgraphs, spanning trees, and more

Sometimes, I would like to iterate over the subgraphs of a graph. For example, I think it would be cool if you could do

using Graphs

g = # some graph

for sg in connected_subgraphs(g)
    # do something with `sg`
end

The problem is that a naive implementation of connected_subgraphs would usually keep track of all generated subgraphs to filter out duplicates, which eat lots of memory. One way to avoid this the so-called reverse search algorithm. The basic idea is to impose a tree structure on the set of output subgraphs. Enumeration of subgraphs then becomes a tree traversal, which does not need to store the entire tree all at once and duplicates are impossible.

I implemented a minimal example of a reverse-search-based algorithm (following the algorithm introduced by Avis and Fukuda) for enumerating connected subgraphs in this demo package called GraphsEnum.jl. Properties of this implementation include:

• No memory growth. Working memory is O(nv(g)) and independent of how many subgraphs are produced, the only allocations are the output subgraphs
• Every subgraph is generated exactly once, with no deduplication bookkeeping.
• Bounded delay. The time between successive outputs is polynomial in the size of the graph and does not degrade as the enumeration goes on.
• Optional multi-threading, since independent subtrees can be explored concurrently.
• The implementation of connected_subgraphs is only about 80 lines. All of the enumeration logic is contained in a (also pretty compact) general Julia implementation of reverse search I've been working on.

If there is interested in connected_subgraphs or similar enumeration/iteration features, I would be happy to also implement algorithms for spanning tree enumeration and everything else I can think of. I'd be happy to register this as a separate enumeration package, or even contribute it here if the dependency on ReverseSearch.jl is acceptable. Happy to hear any comments and feedback!

Start by reviewing the proposed connected_subgraphs implementation in GraphsEnum.jl and the general reverse-search logic in ReverseSearch.jl, then compare their APIs with Graphs.jl conventions. Done means agreeing on whether connected-subgraph and related enumeration belong in Graphs.jl or a separate package, including the acceptable dependency and scope.