有向グラフで島を見つける

Question

私は依存性の低い管理であいまいな言語で作業しています。 14000ファイルのコードベースを助けるために、私はいくつかの構文解析ツール（Javaで）を書いて、依存グラフを生成しました。

私は自分のグラフとBFSクラスを書いて、うまく動作します。それらと私はgetParents()とgetChildren()のようなメソッドを持っています。

今、私はこのグラフで「島」を見つけようとしています。つまり、私は、コードベースのどのセクションが互いに独立したモジュールに集まることを期待して、互いに依存していないかを調べようとしています。

また、個々の島を分析して、モジュールの障壁を設定し、そのモジュールのインターフェースを定義できる弱点があるかどうかを確認する予定ですが、それは道のりです。

今、私はこれをやってと思っています：

Map<DependencyEntry, Set<DependencyEntry>> allChildren = new ...; 
for(DependencyEntry entry : allFiles) allChildren.put(entry,getAllChildren(entry)); 
Set<DependencyEntry> visited = new ...; 
Set<DependencyEntry> largest = new HashSet<DependencyEntry>(); // size 0 
// slightly more expensive but more readable 
for(DependencyEntry entry : allChildren.keySet()) { 
    Set<DependencyEntry> set = allChildren.get(key); 
    if(set.size() > largest.size()) largest = set; 
} 
visited.addAll(largest); 

これが私の最大の島を与える必要があります。そこから、訪問先のノードを含むセットをすべて除外してから、次に実行して次に大きい島を取得するなどのことができます。

これは正確なアルゴリズムですか？私が見ていないこの問題を解決する良い方法はありますか？

Answer 1

あなたはconnected componentsのコレクションを依存関係グラフに追加したいと思っています。そこからコレクションを繰り返し、最大のコンポーネント（または他の興味深いメトリック）を特定できます。

Answer 2

これらの種類のものが組み込まれているので、グラフライブラリを使用する方が簡単でした。通常、ノード、エッジに任意の情報を格納できるため、独自のクラスをデータに使用できますが、ライブラリはサポートアルゴリズムと標準アルゴリズムを提供します。

あなたが説明するアルゴリズムは、ルートノードとは何かが不明瞭です。あなたがルートで始まらなければ、あなたはあなたが始めたところの下の部分（子供たち）だけを見つけることはできません。あなたは子供だけでなく、両親に従うことでこれを解決することができます。それとは別に、それは大丈夫だと思います。PaulFの答えは、私が知る限り、接続されたコンポーネントを見つけるということです。

は、どのように私はYY言語でXXをするか、またはエラーコードで0x34の質問を助けるんからの変更をリフレッシュ、Good Java graph algorithm library?