8 / 13
как элементы текущего уровня найдены, они удаляются из множества
ModelElements
, затем происходит поиск вершин следующего уровня.
Алгоритм работает до тех пор, пока множество
ModelElements
не
станет пустым.
Поскольку заранее не известно, содержит ли граф зависимостей
контуры (что свидетельствует о некорректности исходной метамоде-
ли), на каждом шаге алгоритма выполняется проверка. Эта проверка
основана на том, что, если граф зависимостей содержит контуры, су-
ществует некоторое непустое подмножество его вершин, для которых
условие разбиения на уровни не выполняется, так как не существу-
ет дуг, ведущих из тех вершин предыдущего уровня, в одну из вер-
шин, рассматриваемых на текущем шаге. В этой ситуации функция
getLevelElements
ничего не вернет.
Аналогично можно построить алгоритм разбиения графа зависи-
мостей на уровни при использовании другого представления графа,
например, в виде матрицы инциденций или матрицы смежности [14].
Проиллюстрируем рассмотренный алгоритм на примере. Исход-
ная UML-диаграмма приведена на рис. 2,
а
, полученный на ее основе
граф зависимостей — на рис. 2,
б
. Используемый алгоритм представлен
ниже.
Рис. 2. Пример исходной UML-диаграммы (
а
), полученный на ее основе граф
зависимостей (
б
) и результат работы алгоритма (
в
)
86 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 3