Промежуточные данные подпрограммы LAYMC (M, M) - матрица смежности графа конфликтов соединений; SC (M) - вектор цветов, в которые окрашены вершины. Например, SC 5=2 означает, что 5-я вершина графа конфликтов окрашена во второй цвет (т. е. пятое соединение помещено во второй слой); F - переменная для счета числа итераций алгоритма раскраски; I, J - номера вершин графа конфликтов; К - номер цвета вершин (номер слоя платы); KV(S) - количество вершин Р -го цвета, смежных I -й вершине. Например, KV 2 = 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).
|