7 / 13
N
1
=
v
∈
V
dep
|
V
−
1
dep
(
v
) =
∅
,
N
2
=
v
∈
V
dep
\
N
1
|
V
−
1
dep
(
v
)
⊆
N
1
,
N
3
=
v
∈
V
dep
\
(
N
1
S
N
2
)
|
V
−
1
dep
(
v
)
⊆
N
1
S
N
2
,
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
N
r
=
v
∈
V
dep
\
r
−
1
S
i
=1
N
i
|
V
−
1
dep
(
v
)
⊆
r
−
1
S
i
=1
N
i
,
где
r
— наименьшее число, такое, что
V
dep
\
r
S
i
=1
N
i
=
∅
.
Полученные подмножества упорядочены так, что, если вершина
входит в подмножество с номером
i
, то следующая за ней вершина
в графе входит в подмножество с номером, большим
i
. Полученные
непересекающиеся подмножества называются уровнями. Чтобы вы-
полнить задачи разбиения множества вершин графа зависимостей на
уровни может быть использован алгоритм, приведенный ниже:
ModelElements
=
V
dep
;
LevelElements
=
∅
;
Level
= 0;
whileModelElements
6
=
∅
{
Level
=
Level
+ 1;
LevelElements
[
Level
] =
getLevelElements
(
ModelElements
);
if
(
LevelElements
[
Level
] =
∅
)
{
exit
_
with
_
error
;
}
remove
_
all
(
ModelElements, LevelElements
[
Level
]);
}
getLevelElements
(
ModelElements
)
{
result
=
∅
;
foreach e
:
ModelElements
{
if
(
getAscendants
(
e
)
⊆
V
dep
\
ModelElements
)
{
push
(
result, e
);
}
}
return result
;
}
В качестве входных данных алгоритм использует множество
вершин графа зависимостей. В цикле выполняется поиск элемен-
тов множества
V
dep
, соответствующих текущему уровню (функция
getLevelElements
). Поиск осуществляется среди всех элементов, уро-
вень которых еще не был установлен, согласно приведенному выше
определению разбиения множества вершин ориентированного графа
без контуров (функция
getAscendants
возвращает набор вершин, из
которых выходит дуга, входящая в текущую вершину
e
). После того,
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 3 85