子图枚举 [英] Subgraph enumeration

问题描述

什么是一个高效的算法父图的所有子图的枚举。在我的特定情况下，父图是一个分子图，并因此将被连接，并且通常包含少于100的顶点。

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.

编辑：我感兴趣的只是连接的子图

I am only interested in the connected subgraphs.

推荐答案

这个问题已经在接受答案的这个问题。它避免标志着@ ninjagecko的回答您填写上面的函数的计算复杂的一步。它可以用在这里有几个环的化合物有效的处理。

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.

请参阅链接的问题的全部细节，但这里的摘要。 （N（V）表示一组顶点v的邻居，在选择一个顶点的步骤，你可以选择任意的顶点。）

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))

这篇关于子图枚举的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！