Subgraph enumeration

Question

What is an efficient algorithm for the enumeration of all subgraphs of a parent graph. In my particular case, the parent graph is a molecular graph, and so it will be connected and typically contain fewer than 100 vertices.

Edit: I am only interested in the connected subgraphs.

Answer 1

This question has a better answer in the accepted answer to this question. It avoids the computationally complex step marked "you fill in above function" in @ninjagecko's answer. It can deal efficiently with compounds where there are several rings.

See the linked question for the full details, but here's the summary. (N(v) denotes the set of neighbors of vertex v. In the "choose a vertex" step, you can choose any arbitrary vertex.)

GenerateConnectedSubgraphs(verticesNotYetConsidered, subsetSoFar, neighbors):
    if subsetSoFar is empty:
        let candidates = verticesNotYetConsidered
    else
        let candidates = verticesNotYetConsidered intersect neighbors
    if candidates is empty:
        yield subsetSoFar
    else:
        choose a vertex v from candidates
        GenerateConnectedSubgraphs(verticesNotYetConsidered - {v},
                                   subsetSoFar,
                                   neighbors)
        GenerateConnectedSubgraphs(verticesNotYetConsidered - {v},
                                   subsetSoFar union {v},
                                   neighbors union N(v))