6

質問の正しい用語が正確にわからないので、何をしたいのかを説明します。有向グラフがあり、ノードを削除した後、独立して関連するすべてのノードも削除したいと思います。

次に例を示します。

ここに画像の説明を入力してください

たとえば、ノード「11」を削除します。ノード「2」も削除する必要があります（私自身の例では、2未満のノードになりますが、これも削除する必要があります）。もうメイングラフ。ノード「8」と「3」はまだ接続されているため、ノード「9」または「10」は削除しないでください。

私はPythonライブラリnetworkxを使用しています。ドキュメントを検索しましたが、用語がわからないため、これが何と呼ばれるかわかりません。可能であれば、グラフを介して独自の再帰を作成するよりも、ライブラリが提供する関数を使用したいと思います（グラフが非常に大きいため）。

これを行う方法についてのヘルプや提案は素晴らしいでしょう。

ありがとう！

4

2 に答える 2

6

私は次のことが真実であると仮定しています：

  • グラフは非巡回です。コメントでこれについて言及されましたが、これが最初の前提であることを明示したいと思います。
  • ルートノードの既知のセットがあります。どのノードが常に到達可能であると見なされるかを知るための何らかの方法が必要であり、（どういうわけか）この情報はわかっていると思います。
  • 最初のグラフには、余分なノードは含まれていません。つまり、最初のグラフに削除する必要のあるノードが含まれている場合、それらはすでに削除されています。これにより、すべてのノードが存在する必要があるという不変条件を維持することにより、アルゴリズムが機能します。

この場合、初期設定が与えられると、ノードがグラフに表示される唯一の理由は次のいずれかになります。

  1. ノードがルート到達可能なノードのセットにある、または
  2. ノードには、ルート到達可能なノードのセットにある親があります。

したがって、グラフからノードを削除するときはいつでも、削除する必要がある可能性のあるノードはそのノードの子孫だけです。削除するノードがルートセットにある場合は、グラフの多くを整理する必要があります。削除するノードが、独自の子孫がほとんどない子孫ノードである場合は、ほとんど何もする必要がありません。

この設定では、ノードが削除されたら、そのノードのすべての子をスキャンして、グラフに保持する他の親がないかどうかを確認する必要があります。グラフ内のノードはそこにある必要があるノードのみであると想定しているため、削除されたノードの子に少なくとも1つの他の親がある場合、それはグラフ内にあるはずです。それ以外の場合は、そのノードを削除する必要があります。したがって、削除手順を実行する1つの方法は、次の再帰的アルゴリズムです。

  • 削除するノードの子ごとに：
    • そのノードに親が1つだけある場合:(削除しようとしているノードである必要があります）
      • そのノードをグラフから再帰的に削除します。
  • 指定したノードをグラフから削除します。

ただし、グラフが大きい場合、関連する再帰がかなり深くなる可能性があるため、これは直接実装するのに適したアルゴリズムではない可能性があります。したがって、次のようなワークリストアルゴリズムを使用して実装することをお勧めします。

  • ワークリストWを作成します。
  • 削除するノードであるvをWに追加します。
  • Wが空ではない場合：
    • Wから最初のエントリを削除します。それをwと呼びます。
    • wの子のそれぞれについて：
      • その子に親が1つしかない場合は、それをWに追加します。
    • グラフからwを削除します。

理論的にはすべてのエッジをスキャンする必要があるため、これは最終的に最悪の場合のO（m）時間になります。ここで、mはグラフ内のエッジの数です。ただし、グラフに冗長性があると仮定すると、はるかに高速になる可能性があります。

お役に立てれば！

于 2012-01-08T20:50:03.793 に答える
5

あなたのタスクを解決するPythonnetworkXコードを提供しましょう：

import networkx as nx
import matplotlib.pyplot as plt#for the purpose of drawing the graphs
DG=nx.DiGraph()
DG.add_edges_from([(3,8),(3,10),(5,11),(7,11),(7,8),(11,2),(11,9),(11,10),(8,9)])
DG.remove_node(11)

connected_componentsメソッドは、驚くべきことに有向グラフでは機能しないため、グラフを無向に変え、接続されていないノードを見つけて、有向グラフから削除します。

UG=DG.to_undirected()
not_connected_nodes=[]
for component in nx.connected_components(UG):
    if len(component)==1:#if it's not connected, there's only one node inside
        not_connected_nodes.append(component[0])
for node in not_connected_nodes:
    DG.remove_node(node)#delete non-connected nodes

結果を確認したい場合は、スクリプトに次の2行を追加します。

nx.draw(DG)
plt.show()
于 2012-01-09T15:35:36.257 に答える