Устройство для раскраски графов Советский патент 1989 года по МПК G06F15/173 

со 4; ч|

Изобретние относится к вычислительной технике и может быть использовано при автоматизации разработки печатных плат, в этом случае число красок определяет верхнюю границу количества слоев платы при том, что вершины одного цвета могут быть расположены в одном ее слое.

4704

очередного класса. Через время достаточное для подготовки схем блока 2, блок 1 синхронизации снимает сигнал с выхода 7 и форм1грует импульсный сигнал уровня логической единицы на выходе 8. При этом блок 2 определяет класс раскраски верпган, принадлежащих очередному классу. Через время, доста

Изобретение относится к вычислительной технике и может быть использовано при автоматизации разработки печатных плат. В этом случае число красок (классов раскраски) определяет верхнюю границу количества слоев платы, при том, что вершины одного цвета могут быть расположены в одном ее слое. Цель изобретения - повышение быстродействия устройства. Устройство содержит блок 1 синхронизации, блок 2 определения класса раскраски, блок 3 задания матрицы смежности и блок 4 регистрации. Кроме этого, на фиг. 1 цифровые обозначения имеют вход 5 начальной установки устройства, вход 6 пуска устройства, с первого по третий выходы 7...9 блока 1 синхронизации и выходы 10 группы блока 1 синхронизации, выходы 11 признаков наличия ветвей графа блока 3 и выходы 12 признаков принадлежности вершин составу класса блока 2 определения класса раскраски. После начальной установки устройства в блок 3 заносят информацию о топологии графа. После подачи сигнала на вход 6 пуска блок 1 синхронизации формирует последовательность сигналов, обеспечивающую определение при помощи блока 2 состава вершин каждого класса раскраски и регистрацию в блоке 3. 1 з.п. ф-лы, 4 ил.

Цель изобретения - повьппение быст- д точное для определения всех вершин

класса, блок 1 синхронизации формир ет импульсный сигнал уровня логичес кой единицы на выходе 9. При этом с тав вершин, принадлежащих текущему классу, заносится в блок 4 регистра ци:и. Блок 1 синхронизации формирует сигнал уровня логической единицы на выходе 8 и втором выходе 10.

родействия устройства.

На фиг. 1 представлена функциональная схема устройства; на фиг. 2 - временная диаграма работы блока синхро- низации; на фиг. 3 - функциональная схема блока определения класса раскраски; на фиг. 4 - функциональная схема узла синхро ни за1щи.

Устройство содержит блок 1 синхронизации, блок 2 определения класса раскраски, блок 3 задания матрицы смежности и блок 4 регистрации. Кроме того, устройство имеет вход 5 начальной установки устройства, вход 6 пуска устройства, с первого по третий выходы 7-9 блока 1 синхронизации и выходы 10 группы блока 1 синхрониза-.: ции, выходы 11 признаков наличия ветвей графа блока 3 и выходы 12 признаков принадлежности вершин составу класса блока 2 определения класса раскраски.

° Блок 2 определения .класса раскраски содержит узел 13 синхронизации, коммутатор 14, узел 15 логического сложения, узел 16 проверки смежности вершин, накапливаюш;ий узел 17 логического сложения, тактовый выход 18 узла 13 синхронизации и его выходы 19 группы.

Устройство работает следующим образом.

На вход 5 начальной уста новки подают импульсньй сигнал уровня логической единицы. При этом в блоках 2 и 4 производятся начальные установки, В блок 3 задания матрицы смежности заносят информацию о топологии графа. На вход 6 пуска устройства подают, импульсный сигнал уровня логической .единицы. При этом блок 1 синхронизации формирует последовательность сигналов предусмотренную его временной диаграммой. Сигнал уровня логической единицы появляется на первом выходе 7 и первом выходе 10 блока 1 синхрониза ции. При этом в блоке 2 определения класса раскраски производится подготовка к определению состава вершин

д точное для определения всех вершин

5

0

5 0

5

0

5

0

класса, блок 1 синхронизации формирует импульсный сигнал уровня логической единицы на выходе 9. При этом состав вершин, принадлежащих текущему классу, заносится в блок 4 регистра- ци:и. Блок 1 синхронизации формирует сигнал уровня логической единицы на выходе 8 и втором выходе 10.

Работа устройства повторяется до тех пор пока не будут раскрашены все вершины графа. В общем случае для этого может потребоваться от одного до В тактов, где В - количество вершин в графе.

Блок 2 определения класса раскраски работает следующим образом.

По сигналу начальной установки коммутатор 14 замыкает каждую из своих В информационных цепей. По сигналу подготовки накапливающий узел логического сложения обнуляется. По сигналу пуска 13 синхронизации начинает формировать сигналы, предусмотренные временной диаграммой его работы. Сигнал уровня логической единицы появляется на первом выходе 19 узла 13 синхронизации. При этом узел 16 проверки смежности проверяет отсутствие смежности вершин, накопленных на выходе узла 15. Через время, достаточное для проверки, узел 13 синхронизации формирует сигнал уровня.логической единицы на своем тактовом выходе 18. При этом блок 16 вьщает значение признака отсутствия смежности на такто- вьш вход накапливающего узла 17 логического сложения. Если значение признака равно единице (т.е. вершина, номер которой соответствует номеру возбужденного выхода 19 узла 13, не смежна ни с одной из вершин, которые уже отнесены к текзпцему классу), узел 15 накапливает (по ИЛИ) код на своем информационном входе (вершина, номер которой соответствует Номеру возбужденного выхода 19, добавляется к текущему классу), Одновременно сигналом с выхода узла 17 размыкается до подачи сигнала с входа 5 начапьной установки соответствующая информационная цепь коммутатора 14. При равенстве нулк5 признака отсутствия смежности накопления кода и отключен НИН информационной цепи коммутатора 14 не происходит. Через время, достаточное для накопления кода, узел 13 синхронизации снимает сигнал со свое15

го тактового выхода 18 и текущего вы- Q ки блока регистрации и блока определе- хода 19 и формирует сигнал на следующем по порядку выходе 19. Далее работа устройства повторяется. После того, как будут просмотрены все вершины на предмет их включения в текущий класс раскраски, на выходе узла 17 формируется состав вершин текущего класса. При следующем запуске работа блока 2 повторяется, однако все вершины, отнесенные к предьщущим классам исключаются из рассмотрения отключением соответствующих их номерам информационных цепей коммутато- чра 14.

20

ления класса раскраски.

блок регистрации и блок задания мат- 30 М-мУ управляющему входу коммутатора

и к М-му разряду входа второго слагаемого субблока логического сложения, М-й разряд информационного выхода которого подключен к входу признака соФормула изобретения

ицы смежности, причем вход пуска устройства подключен к входу пуска блока синхронизации, отличающееся тем, что, с целью повьш1е- ния быстродействия устройства,в него введён блок определения класса раскраски, причем первый и второй выходы блока синхронизации подключены к входу подготовки и к входу пуска блока определения класса раскраски соответственно,выход признака наличия (К,М)-й ветви блока задания матрицы смежности (К 1 , ..., В; М 1, ..., В; где В-количество вершин в графе)

35

ответствия М-й вершины составу опрашиваемых узла проверки смежности вершин, вход признака наличия (К, М)-й ветви которого является одноименным входом блока определения класса вер- 40 шин, тактовый выход узла синхронизации подключен к входу опроса узла проверки смежных вершин, выход признака отсутствия смежности которого подключен к тактовому входу накапливаннцего

подключен к одноименному входу блока 45 Узла логического смежения, вход установки в О которого является входом подготовки блока определения класса раскраски, вход начальной установки которого подключен к входу вкпюче- 50 ния информационных цепей коммутатора.

определения класса раскраски, выход признака принадлежности М-й вершины составу класса которого подключен к М-му разряду информационного входа блока регистрации, Р-й выход группы

блока синхронизации (Р 1, ..,, Т , где Т - количество классов раскраски) подключен к Р-му разряду адресного входа блока регистрации, вход признака записи которого подключен к третьему выходу блока синхронизации, вход начальной установки устройства подключен к входам начальной установ15

Q

25

Q

20

25

ответствия М-й вершины составу опрашиваемых узла проверки смежности вершин, вход признака наличия (К, М)-й ветви которого является одноименным входом блока определения класса вер- шин, тактовый выход узла синхронизации подключен к входу опроса узла проверки смежных вершин, выход признака отсутствия смежности которого подключен к тактовому входу накапливаннцего

12,12 12в

0t/2.3

Фг/г.