algorithm - 子图枚举

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)，你只需要一个算法，它可以生成所有 CONNECTED 子图作为迭代器（产生每个元素）。这可以通过一次递归地删除一个元素（可选地从“边界”）、检查剩余的元素集是否在缓存中（否则添加它）、产生它并递归来完成。如果您的分子非常链状且循环次数很少，则此方法效果很好。例如，如果您的元素是 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 上的深度优先搜索，并且对于每条边 (v_i, v_j) 都有一个形式为 (i, j, l(v_i), l(v_i, v_j), l(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/