Структура данных и алгоритмы для ориентированного циклического графа (F #)

Question

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

Что я хочу сделать, это проанализировать каждую сборку-сборкуСоедините и создайте представление о том, где что-то не так.

Мне нужно несколько советов о том, что будет хорошей структурой данных для этого.Я не слишком уверен, что смогу создать неизменный объект, но я не против, чтобы он был изменяемым внутри, а затем преобразован в неизменяемый в конце.

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

Answer 1

Вы можете просто использовать NDepend , он анализирует ваши сборки и определяет циклы зависимостей.

Если вы действительно хотите сделать это самостоятельно, я бы использовал QuickGraph для моделирования графиков зависимостей, он также включает алгоритмы графиков, такие как топологическая сортировка.

Answer 2

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

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

Я только что реализовал это в F #, а топологическая сортировка - всего 12 строк кода ...: -)

Answer 3

То, что вы хотите сделать, называется «Топологическая сортировка». Википедия имеет хороший обзор:

http://en.wikipedia.org/wiki/Topological_sort