Я работаю на непонятном языке с плохим управлением зависимостями. Чтобы помочь кодовой базе из 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);
Это должно дать мне самый большой остров. Оттуда я могу просмотреть и исключить любые наборы, содержащие какие-либо посещенные узлы, а затем запустить его снова, чтобы получить следующий по величине остров, и так далее.
Это точный алгоритм? Есть ли лучший способ решить эту проблему, которого я не вижу?