子图枚举

Question

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

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

Answer 1

这个问题有在接受答案this question一个更好的答案。它避免了在@ 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非常大，所以你绝对不希望（像上面那样）列举数学上正确但物理上无聊的断开的子图。如果假设每秒钟进行十亿次计数，至少需要40万亿年才能列举出所有这些数据，否则它会从字面上把你带走。

连接 - 子发电机：

如果你想要某种枚举的，在某些指标保留子图的DAG属性，例如（1,2,3） - >（2,3） - >（2），（1,2,3） - >（1,2） - >（2），您只需要一个可以生成所有CONNECTED子图都作为迭代器（产生每个元素）。这可以通过递归地删除单个元素（可选地从“边界”）来完成，检查剩余的元素集是否在缓存中（否则添加它），产生它并递归。如果您的分子非常连锁且周期非常短，这种方法很好。例如，如果你的元素是一个N元素的五角星，它只会有（100/5）^ 5 = 320万个结果（小于1秒）。但是，如果您开始添加多个单个戒指，例如芳香族化合物和其他，你可能会很难过。

例如在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})