Структура данных и алгоритмы для направленного циклического графика (F#)
Я пытаюсь проанализировать приложение, где ссылки на сборки должны быть направленным графом без петель, но не. Существует также связанная проблема компонентов, ссылающихся на различные версии одного подкомпонента (думайте Escher...),
То, что я хочу сделать, анализируют каждую пару компонента блока и создают изображение того, где вещи являются неправильными.
Мне нужно некоторое руководство на том, что было бы хорошей структурой данных для этого. Я не слишком уверен, что могу создать неизменный, но я не возражаю иметь его изменяемый внутренне затем преобразованный к неизменному в конце.
Другая часть вопроса - то, какие алгоритмы я должен использовать для заполнения структуры данных, и также впоследствии для 'анализа' проблем.
3 ответа
Вы можете просто использовать NDepend, он анализирует ваши сборки и обнаруживает циклы зависимостей.
Если вы действительно хотите сделать это самостоятельно, я бы использовал QuickGraph для моделирования графов зависимостей, он также включает алгоритмы работы с графами, например, топологическую сортировку.
Я не против, чтобы он был изменен внутри, а затем преобразован в неизменяемый в конце.
Возможно, вам будет проще использовать неизменяемые структуры данных повсюду. В частности, вы можете легко представить граф в виде Карты от исходных узлов до наборов конечных узлов. Для топологической сортировки вам нужен эффективный доступ к исходным узлам целевого узла, поэтому вы можете захотеть дополнить свой граф другой Map , идущей в противоположном направлении.
Я только что реализовал это на F #, и топологическая сортировка занимает всего 12 строк кода ...: -)
То, что вы хотите сделать, называется «Топологическая сортировка». В Википедии есть хороший обзор: