子圖枚舉

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