私は依存性の低い管理であいまいな言語で作業しています。 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);
これが私の最大の島を与える必要があります。そこから、訪問先のノードを含むセットをすべて除外してから、次に実行して次に大きい島を取得するなどのことができます。
これは正確なアルゴリズムですか?私が見ていないこの問題を解決する良い方法はありますか?
にも興味深い質問を参照してください! – GBa