10

親グラフのすべてのサブグラフを列挙するための効率的なアルゴリズムは何ですか? 私の特定のケースでは、親グラフは分子グラフであるため、接続され、通常は 100 未満の頂点が含まれます。

編集:接続されたサブグラフにのみ興味があります。

4

3 に答える 3

5

この質問には、この質問に対する受け入れられた回答でより良い回答があります。@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))
于 2013-03-30T19:28:42.487 に答える
4

親グラフのすべてのサブグラフを列挙するための効率的なアルゴリズムは何ですか? 私の特定のケースでは、親グラフは分子グラフであるため、接続され、通常は 100 未満の頂点が含まれます。

数学的サブグラフとの比較:

各要素に 0 から N までの数値を指定し、各サブグラフを長さ N の任意の 2 進数として列挙することができます。グラフをスキャンする必要はまったくありません。

本当に必要なのは、特定のプロパティ ( full connectedなど) を持つサブグラフであり、それが異なる場合は、質問を更新する必要があります。コメンターが指摘したように、2^100 は非常に大きいため、(上記のように) 数学的に正しいが物理的に退屈な切断されたサブグラフを列挙したくないことは間違いありません。1 秒間に 10 億回の列挙が行われると仮定すると、それらすべてを列挙するには少なくとも 40 兆年かかることになります。

Connected-subgraph-generator:

(1,2,3)->(2,3)->(2)、(1,2,3)->(1 など) いくつかのメトリックの下でサブグラフの DAG プロパティを保持するある種の列挙が必要な場合,2)->(2)、すべての CONNECTED サブグラフを反復子として生成できるアルゴリズムが必要なだけです (各要素を生成します)。これは、一度に 1 つの要素を (オプションで「境界」から) 再帰的に削除し、残りの要素のセットがキャッシュにあるかどうかを確認し (そうでない場合は追加します)、それを生成し、再帰することによって実現できます。これは、分子が非常に少ないサイクルで非常に鎖状である場合にうまく機能します。たとえば、要素が 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})
于 2011-05-12T21:23:47.217 に答える