Найти острова в ориентированном графе

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

Звучит так, как будто вы хотите создать коллекцию связанных компонентов , найденных на графике зависимостей.Оттуда вы можете выполнить итерацию коллекции и определить самый большой компонент (или любую другую интересную метрику).

Answer 2

было бы проще использовать библиотеку графов, потому что такие вещи встроены.как правило, они позволяют вам хранить произвольную информацию в узлах, ребрах, так что вы все равно можете использовать свои собственные классы для данных, но библиотека предоставляет поддержку и стандартные алгоритмы.

алгоритм, как вы описываете, кажется немного неяснымна каких корневых узлах.если вы не начнете с корня, то вы не найдете «весь остров» - только части ниже (дети), с которых вы начали.Вы можете исправить это, следуя за родителями, а также за детьми.кроме того, это звучит нормально - он делает, как говорит ответ PaulF, насколько я могу судить, и находит подключенные компоненты.

см. также Хорошая библиотека алгоритмов графов Java?