По сути, ваши классы, объекты или что у вас есть, хранятся в матрице (называемой матрица смежности ), которая представляет ориентированный граф (с циклами или без них). См. График ниже и соответствующую матрицу смежности.
Исходя из этого, мы можем вычислить матрицу достижимости, которая описывает, к каким узлам можно добраться от текущего узла. Для этого графика матрица достижимости равна
Вам нужен алгоритм, который переставляет строки и столбцы матрицы так, чтобы все ненулевые элементы были ниже главной диагонали. Последовательность индексов объектов, для которых это верно, может быть выполнена в том порядке, в котором они появляются в матрице, и все необходимые зависимости для каждого объекта будут выполнены. Если известно, что граф является ациклическим, это может быть достигнуто путем топологической сортировки .
Когда в ориентированном графе появляются циклы, вы не сможете найти порядок, для которого это верно.
Введите Матрица структуры проектирования / зависимости (DSM). Для разделения объектов на уровни можно реализовать так называемый алгоритм разделения. Для каждого из этих уровней объекты могут выполняться в произвольном порядке и не зависят ни от того, ни от другого. Для приведенного выше графика узлы 3, 4 и 5 не зависят друг от друга и могут выполняться в любом порядке.
Алгоритм разделения был разработан в (Warfield 1973), который способен обнаруживать и изолировать циклы в DSM. Это похоже на алгоритм топологической сортировки, но с использованием матрицы достижимости для обнаружения и выделения циклов.
Алгоритм кратко:
- Создать новый уровень раздела
- Рассчитать достижимость и предшествующие множества R (s) и A (s)
- Для каждого элемента в DSM рассчитайте установленное произведение R (s) A (s)
- Если R (s) A (s) = R (s), то добавить элемент
s к текущему уровню
- Удалить элемент
s из списка и все ссылки на него из наборов достижимости и предшествующих наборов всех других элементов.
- Повторите с 1, если список элементов не пуст.
Предыдущий набор A (s) - это набор индексов строк ненулевых элементов в столбце s, в то время как набор достижимости R (s) - это набор индексов столбцов ненулевых элементов s.
Наконец, некоторый псевдокод (в VB.NET, не менее):
CalculateInitialAntecedentSets()
CalculateInitialReachabilitySets()
While UnlabelledItems > 0
Sequence.AddNewPartitionLevel()
For Each s In ReachabilityMatrix
If NoDependencies(s) and AlreadyConsidered(s) Then
AddToLevel(CurrentLevel, s)
End If
Next
RemoveDependencies(ReachabilitySets, Sequence.Level(CurrentLevel))
RemoveDependencies(AntecedentSets, Sequence.Level(CurrentLevel))
UpdateConsideredList(Sequence.Level(CurrentLevel))
Unlabelled = Unlabelled - Sequence.Level(CurrentLevel).Count
CurrentLevel = CurrentLevel + 1
End While
(Это была тема моей магистерской диссертации несколько лет назад)
Уорфилд, Джон Н. (1973), «Бинарные матрицы в моделировании систем», IEEE Транзакции по системам, человеку и кибернетике SMC-3 (5), 441--449.