Efficient iteration over connected subgraphs, spanning trees, and more

Open
  • Is something wrong?
#521 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
5/5
Estimated time
Over a week
Newbie friendliness
35/100
Issue type
Feature
Clarity
Mostly clear
Activity status
Quiet
Tech stack
julia
Domain
data

Research direction

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.

Written by the indexing model from the issue text.

Description

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!

Dominant language
Julia
Stars
540
Forks
131
No merged PRs in 30d

Getting set up

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from JuliaGraphs/Graphs.jl

All issues in JuliaGraphs/Graphs.jl

Similar issues

More Julia issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.