子图枚举

Question

如何高效枚举父图的所有子图？在我的特定情况下，父图是分子图，因此它将是连通的，并且通常包含少于100个顶点。

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

- Narwe

---

你想要所有子图还是所有连通的子图？ - Ted Hopp

无论你有多高效，遍历2^100个顶点的子集都需要非常长的时间，更不用说边可以存在或不存在了。你能否转换到一个可能在太阳爆炸之前就能完成的问题上来？ - btilly

@btilly：你说得对，假设这是一个带顶点标签的图，这通常是应用场景。如果顶点没有标记（即它们不可区分），那么例如n个顶点的完全图只有n个子图（包括本身）。 - j_random_hacker

我只对完整的子图感兴趣。我已经编辑了这个问题。 - Narwe

抱歉，那是个脑抽了。我的意思是连接的，而不是完成的。 - Narwe

Answer 1

这个问题在这个问题的被接受的答案中有更好的回答。它避免了@ninjagecko答案中标记为“ you fill in above function”的计算复杂步骤。它能高效地处理多个环组成的化合物。

请查看链接问题获取完整细节，以下是摘要。（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))

- Andrew Rose

Answer 2

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

与数学子图的比较：

您可以为每个元素分配0到N之间的编号，然后将每个子图枚举为长度为N的任何二进制数。您根本不需要扫描图形。

如果您真正想要具有某些属性（完全连接等）的子图，则不同，您需要更新您的问题。正如评论者指出的那样，2^100非常大，因此您绝对不想（像上面那样）枚举数学上正确但物理上无聊的断开子图。假设每秒十亿次枚举，至少需要40万亿年才能枚举完所有内容。

连通子图生成器：

如果您想要一种保留某些度量下子图的DAG属性的枚举方法，例如(1,2,3)->(2,3)->(2)、(1,2,3)->(1,2)->(2)，您只需要一个可以作为迭代器生成所有连接的子图的算法（产生每个元素）。这可以通过递归一次删除一个元素（可选地从“边界”中），检查剩余的元素集是否在缓存中（否则添加它），产生它并进行递归来完成。如果您的分子非常像链式结构，很少有环，则此方法可以正常工作。例如，如果您的元素是一个具有N个元素的五角星，则只有约（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})

- ninjagecko

---

不幸的是，化合物中往往会有一个或多个环。但是，在最大环数为零的情况下，您的算法应该是可行的。 - Narwe

我认为{环直径，或某些东西的最小直径，或环如何组成更复杂结构（例如晶体中）}可能比环的数量更重要，关于子图的大致数量。这是一个与上面代码中能够优化生成连续子图的问题不同的问题。另外，由于空间结构的原因，可能有很好的方法可以根据在3空间中的嵌入来划分问题。只是一种直觉。 - ninjagecko

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/

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

- Chris

---

虽然这个链接可能回答了问题，但最好在此处包含答案的基本部分并提供参考链接。如果链接页面更改，仅链接的答案可能会失效。-【来自审查】 - Someone_who_likes_SE