4

警告として、私はまだPythonに少し慣れていません

networkx ライブラリを使用して、有向グラフの推移還元を実行しようとしています。アルゴリズムを見つけましたが、実装に問題があります。簡単な検索の後、他のスタック交換の質問で私のものと同様のアルゴリズムを見つけましたが、アルゴリズムを実際にコーディングする方法のデモンストレーションはありませんでした。

ここに私のアルゴリズムがあります：

    For X in Nodes
    For Y in Nodes
    For z in Nodes
    if (x,y) != (y,z) and (x,y) != (x,z)
    if edges xy and yz are in Graph
    delete xz

これをpythonで表現しようとする私の試みは次のとおりです。

    G = graph
    N = G.Nodes()
    for  x in N:
       for y in N:
          for z in N:
             if (x,y) != (y,z) and (x,y) != (x,z):
                if (x,y) and (y,z) in G:
                    G.remove_edge(x,z)

ネットワーク内のエッジのすべての順列を適切に呼び出しているとは思わず、itertools を使用しようと考えていました。可能なすべての順列があったとしても、その情報を使用してアルゴリズムを実装する方法がわかりません。

どんな助けでも素晴らしいでしょう。ありがとう！

4

4 に答える 4

3

tredユーティリティ (graphviz ユーティリティの一部として dot fromat でグラフの推移縮小を計算する)のソースを正しく読んだ場合、使用するアルゴリズムは次のとおりです。グラフのすべての頂点と各頂点について、その子のそれぞれで DFS を実行します。そのように通過した頂点ごとに、元の親頂点からその頂点へのエッジをすべて削除します。

次のようにnetworkxを使用してそのアルゴリズムを実装しました。

g = nx.read_graphml("input.dot")
for n1 in g.nodes_iter():
    if g.has_edge(n1, n1):
        g.remove_edge(n1, n1)
    for n2 in g.successors(n1):
        for n3 in g.successors(n2):
            for n4 in nx.dfs_preorder_nodes(g, n3):
                if g.has_edge(n1, n4):
                    g.remove_edge(n1, n4)    
nx.write_graphml(g, "output.dot")

ネスティング レベルは恐ろしい複雑さを示唆していますが、実際には、後で実行される DFS の最初の 2 つのステップを既に実行しています。そのようにすると、現在のノードが親の直接の後継者であるかどうかを DFS 部分でチェックすることが回避されます (networkx の DFS 結果には、トラバーサルが開始された頂点が含まれるため)。したがって、代替の定式化は次のようになります。これは、このアルゴリズムの複雑さをよりよく示していますが、最も内側の looptgoo での追加のチェックのために少し遅くなります。

g = nx.read_graphml("input.dot")
for n1 in g.nodes_iter():
    c = set(g.successors(n1))
    for n2 in nx.dfs_preorder_nodes(g, n1):
        if n2 in c:
            continue
        if g.has_edge(n1, n2):
            g.remove_edge(n1, n2)    
nx.write_graphml(g, "output.dot")

操作は Python 辞書を使用するためhas_edge、平均的です。DFS の最悪の場合の時間の複雑さは、グラフ内のエッジの数です。DFS は(頂点の数で)回実行されるため、上記のアルゴリズムの時間計算量は です。remove_edgeO(1)O(E)ENNO(NE)

tredもう 1 つの面白い観察結果は、上記の Python コードが、graphviz スイートのユーティリティよりも桁違いに高速であるように見えることです。これがなぜなのかわかりません。以下は、482 個の頂点と 9656 個の辺を持つ非巡回グラフの実行時間の比較です。

  • トレッド: 58.218 秒
  • Python: 4.720 秒

また、14956 個の頂点と 190993 個のエッジを持つグラフで別のベンチマークを試しましたが、上記の Python コードは 11 分で終了しましtredたが、この記事の執筆時点では 2 時間の実行時間後もまだ実行されています。

編集: 7 日と 3 時間後、tredそのグラフはまだ変化しています。私は今あきらめています。

于 2015-05-31T06:57:04.087 に答える
0

それまでの間、推移還元は に組み込まれていnetworkxます。

import networkx as nx
G = nx.DiGraph()
G.add_edges_from([(0,1),(0,2),(0,3),(0,4),(1,2),(1,4),(1,4),(3,4)])
H = nx.transitive_reduction(G)
print(H.edges)
# [(0, 1), (0, 3), (1, 2), (1, 4), (3, 4)]
于 2020-08-15T18:57:28.387 に答える