-1

推移閉包を見つける Python コードがあります。

例：

入力: {('A','B'),('B','C'),('C','D'),('E','F')}

出力: {('B', 'C'), ('A', 'D') , ('A', 'B'), ('C', 'D'), ('B', 'D ') , ('E', 'F'), ('A', 'C') }

コードは完璧に機能しますが、私が探しているのは、出力をサブグラフのセットとして持つことです。私はPythonの初心者で、その方法がわかりません。

与えられた入力によると、ここに私が探している出力があります。これはセットに 2 つの要素があり、それぞれが推移閉包出力からのサブグラフを表します: {(A, B, C, D), (E, F) }

コードは次のとおりです。

from collections import defaultdict

def transitive_closure(elements):
    edges = defaultdict(set)
    # map from first element of input tuples to "reachable" second elements
    for x, y in elements: edges[x].add(y)

    for _ in range(len(elements) - 1):
        edges = defaultdict(set, (
                                  (k, v.union(*(edges[i] for i in v)))
                                  for (k, v) in edges.items()
                                  ))

    return set((k, i) for (k, v) in edges.items() for i in v)

result = set(transitive_closure([('A','B'),('B','C'),('C','D'),('E','F')]))
print result
4

1 に答える 1

1

Python でnetworkxを使用して問題を解決しました。networkxは、特定のグラフのすべてのサブグラフを検索する機能を提供します。

必要なのは、transitive_closure()メソッドの出力を取得し、それを networkx のグラフに変換してから、新しく作成されたグラフをnetworkx が提供するconnected_component_subgraphs()メソッドへの入力として取得することだけです。

H=nx.connected_component_subgraphs(G)

H は、必要なすべてのサブグラフを含むセットです。

主な欠点は処理時間ですが、それは私が見つけることができる最高のものです.

于 2012-12-23T23:54:38.327 に答える