在有向图中查找岛屿

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

听起来您想构建在依赖关系图中找到的连接组件的集合。从那里您可以迭代集合并识别最大的组件（或任何其他有趣的指标）。