子图枚举

Question

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

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

Answer 1

这个问题在这个问题的接受答案中有更好的答案。它避免了@ninjagecko 的答案中标记为“您填写上述函数”的计算复杂步骤。它可以有效地处理有多个环的化合物。

有关完整详细信息，请参阅链接的问题，但这是摘要。 （N(v) 表示顶点 v 的邻居集合。在“选择顶点”步骤中，您可以选择任意顶点。）

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

Answer 2

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

与数学子图的比较：

您可以为每个元素指定一个从 0 到 N 的数字，然后将每个子图枚举为长度为 N 的任意二进制数。您根本不需要扫描该图。

如果您真正想要的是具有不同属性（完全连接等）的子图，那么您需要更新您的问题。正如评论者指出的，2^100 非常大，所以你绝对不想（像上面那样）枚举数学上正确但物理上无聊的断开子图。假设每秒进行 10 亿次枚举，实际上需要至少 40 万亿年才能将它们全部枚举出来。

连通子图生成器：

如果您想要某种枚举来保留某些指标下子图的 DAG 属性，例如 (1,2,3)->(2,3)-> (2), (1,2,3)->(1,2)->(2)，您只需要一个可以将所有连接的子图生成为迭代器的算法（产生每个 元素）。这可以通过一次递归地删除一个元素（可选地从“边界”）、检查剩余的元素集是否在缓存中（否则添加它）、产生它并递归来完成。如果你的分子非常呈链状且循环很少，那么这种方法就很有效。例如，如果您的元素是由 N 个元素组成的 5 角星形，则它只会有大约 (100/5)^5 = 320 万个结果（不到一秒）。但如果你开始添加多个环，例如芳香族化合物和其他化合物，你可能会遇到困难。

例如在 python 中

class Graph(object):
    def __init__(self, vertices):
        self.vertices = frozenset(vertices)
        # add edge logic here and to methods, etc. etc.

    def subgraphs(self):
        cache = set()
        def helper(graph):
            yield graph
            for element in graph:
                if {{REMOVING ELEMENT WOULD DISCONNECT GRAPH}}:
                    # you fill in above function; easy if
                    # there is 0 or 1 ring in molecule
                    # (keep track if molecule has ring, e.g.
                    #  self.numRings, maybe even more data)
                    # if you know there are 0 rings the operation
                    #  takes O(1) time
                    continue
                subgraph = Graph(graph.vertices-{element})
                if not subgraph in cache:
                    cache.add(subgraph)
                    for s in helper(subgraph):
                        yield s
        for graph in helper(self):
            yield graph

    def __eq__(self, other):
        return self.vertices == other.vertices
    def __hash__(self):
        return hash(self.vertices)
    def __iter__(self):
        return iter(self.vertices)
    def __repr__(self):
        return 'Graph(%s)' % repr(set(self.vertices))

演示：

G = Graph({1,2,3,4,5})

for subgraph in G.subgraphs():
    print(subgraph)

结果：

Graph({1, 2, 3, 4, 5})                                                                                                                                                                                                                                              
Graph({2, 3, 4, 5})
Graph({3, 4, 5})
Graph({4, 5})
Graph({5})
Graph(set())
Graph({4})
Graph({3, 5})
Graph({3})
Graph({3, 4})
Graph({2, 4, 5})
Graph({2, 5})
Graph({2})
Graph({2, 4})
Graph({2, 3, 5})
Graph({2, 3})
Graph({2, 3, 4})
Graph({1, 3, 4, 5})
Graph({1, 4, 5})
Graph({1, 5})
Graph({1})
Graph({1, 4})
Graph({1, 3, 5})
Graph({1, 3})
Graph({1, 3, 4})
Graph({1, 2, 4, 5})
Graph({1, 2, 5})
Graph({1, 2})
Graph({1, 2, 4})
Graph({1, 2, 3, 5})
Graph({1, 2, 3})
Graph({1, 2, 3, 4})

Answer 3

有一种称为 gspan [1] 的算法，已用于计算频繁子图，它也可用于枚举所有子图。您可以在这里找到它的实现 [2]。

这个想法如下：图由所谓的 DFS 代码表示。 DFS 代码对应于图 G 上的深度优先搜索，并具有以下形式的条目
(i, j, l(v_i), l(v_i, v_j), l(v_j))，对于图的每条边 (v_i, v_j)，其中顶点下标对应于发现顶点的顺序DFS。可以在所有 DFS 代码的集合上定义全序（如 [1] 中所做的那样），并因此通过计算表示该图的所有 DFS 代码的最小值来获得给定图的规范图标签。这意味着如果两个图具有相同的最小 DFS 代码，则它们是同构的。现在，从长度为 1 的所有可能的 DFS 代码（每条边一个）开始，可以通过随后一次向代码添加一条边来枚举图的所有子图，从而生成一棵枚举树，其中每个节点对应于一个图。如果仔细地进行枚举（即，与DFS代码上的顺序兼容），首先遇到最小的DFS代码。因此，每当遇到非最小的 DFS 代码时，就可以修剪其相应的子树。请参阅[1]了解更多详细信息。

[1] https://sites.cs.ucsb.edu/~xyan /papers/gSpan.pdf
[2] http://www.nowozin.net/sebastian/gboost/