Промежуточные данные подпрограммы LAY

MC (M, M) - матрица смежности графа конфликтов соединений;

SC (M) - вектор цветов, в которые окрашены вершины. Например, SC ₅=2 означает, что 5-я вершина графа конфликтов окрашена во второй цвет (т. е. пятое соединение помещено во второй слой);

F - переменная для счета числа итераций алгоритма раскраски;

I, J - номера вершин графа конфликтов;

К - номер цвета вершин (номер слоя платы);

KV(S) - количество вершин Р -го цвета, смежных I -й вершине. Например, KV ₂ = 4 означает, что из всех вершин, смежных 2 -й вершине, четыре окрашены во 2-й цвет;

P, H - переменные для запоминания номера цвета.

Описание схемы подпрограммы TREE (рис. 11)

В программе ТRЕЕ реализован алгоритм Прима, который работает следующим образом. Выбирается оче­редная электрическая цепь схемы (блоки 2, 3, 18), определяется (блок 4) число Q ее контактов (концов), их координаты ХС, YC(Q), и формируется матрица ML(Q, Q) длин ребер полного графа (блок 5), построенного на этих контактах.

 

 

Рис. 11. Схема программного модуля TLO-3

 

 

 

 

Рис. 12. Схема подпрограммы LAY-3

 

Первоначально (блок 6) все метки и локальные степени вершин принимают нулевые значения. Затем одна из вершин (здесь первая) вклю­чается (блок 7) в дерево. Далее фрагмент дерева разрастается. Вы­бирается ближайшая к фрагменту I -я вершина (блоки 8...I6). Затем I -я вершина включается (блок 23) в дерево, а соответствующее сое­динение пополняет (блоки 24, 25) список соединений. Процесс продол­жается до тех пор, пока не будет выбрано ровно (Q -1) ребер для оче­редной цепи (блоки 7, 8, 17).

Описание подпрограммы LAY (рис. 12)

Блок 1 предназначен для формирования матрицы смежности графа конфликтов соединений. Предварительно все вершины окрашива­ются одинаково (блок 3). Далее выбирается очередная I -я вершина (блоки 5, 17), отыскиваются смежные с ней J -е вершины (блоки 7, 8, 10) и среди них подсчитывается число вершин каждого (P -го) цвета (блок 9). Затем определяется цвет Н, в который окрашено минимальное число вершин, смежных с I -й (блоки 11,..., 15), и в этот цвет окрашивается I -я вершина (блок 16). В случае если I -я вершина изолирована (P =0), т.е. соединение не конфликтует с дру­гими, то его помещают (блок 16) в тот слой, где находятся другие соединения той же цепи. Перекраска вершин выполняется заданное число раз (блоки 4, 18).