Учебная САПР электронных средств. Асланянц В.Р. - 47 стр.

UptoLike

ВУЗ: 

ВлГУ | Владимир

Составители: 

Рубрика: 

47
X1, Y1, X2, Y2, CC, SC (M) - упорядоченный список соединений (ко-
ординаты концов соединений; номер цепи соединений; слой, в который
попало соединение).
Промежуточные данные подпрограммы TREE
F - переменная для счета числа цепей, для которых уже построены
соединения;
M - переменная для счета числа соединений, включенных в список;
K - переменная для счета числа выбранных соединений (ребер дере-
ва) очередной цепи;
Q - число контактов, соединяемых очередной цепью;
XC, YC (Q) - координаты концов цепи (вершин дерева);
ML (Q, Q) - матрица длин ребер полного графа, на вершинах которо-
го строится дерево;
RV (Q) - вектор локальных степеней вершин дерева;
MV (Q) - вектор меток вершин. Метка каждой вершины может при-
нимать значение 1 или 0 в зависимости от того, включена или нет данная
вершина в дерево к данному моменту времени.
Промежуточные данные подпрограммы LAY
MC (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), построенного на этих контактах. 
      X1, Y1, X2, Y2, CC, SC (M) - упорядоченный список соединений (ко-
ординаты концов соединений; номер цепи соединений; слой, в который
попало соединение).
      Промежуточные данные подпрограммы TREE
      F - переменная для счета числа цепей, для которых уже построены
соединения;
      M - переменная для счета числа соединений, включенных в список;
      K - переменная для счета числа выбранных соединений (ребер дере-
ва) очередной цепи;
      Q - число контактов, соединяемых очередной цепью;
      XC, YC (Q) - координаты концов цепи (вершин дерева);
      ML (Q, Q) - матрица длин ребер полного графа, на вершинах которо-
го строится дерево;
      RV (Q) - вектор локальных степеней вершин дерева;
      MV (Q) - вектор меток вершин. Метка каждой вершины может при-
нимать значение 1 или 0 в зависимости от того, включена или нет данная
вершина в дерево к данному моменту времени.
      Промежуточные данные подпрограммы LAY
      MC (M, M) - матрица смежности графа конфликтов соединений;
      SC (M) - вектор цветов, в которые окрашены вершины. Например,
SC5=2 означает, что 5-я вершина графа конфликтов окрашена во второй
цвет (т. е. пятое соединение помещено во второй слой);
      F - переменная для счета числа итераций алгоритма раскраски;
      I, J - номера вершин графа конфликтов;
      К - номер цвета вершин (номер слоя платы);
      KV(S) - количество вершин Р-го цвета, смежных I-й вершине. На-
пример, KV2 = 4 означает, что из всех вершин, смежных 2-й вершине, че-
тыре окрашены во 2-й цвет;
      P, H - переменные для запоминания номера цвета.
      Описание схемы подпрограммы TREE (рис. 11)
      В программе ТRЕЕ реализован алгоритм Прима, который работает
следующим образом. Выбирается очередная электрическая цепь схемы
(блоки 2, 3, 18), определяется (блок 4) число Q ее контактов (концов), их
координаты ХС, YC(Q), и формируется матрица ML(Q, Q) длин ребер пол-
ного графа (блок 5), построенного на этих контактах.




                                                                       47

Страницы