Устройство для моделирования сетевых графов

 

Изобретение относится к вычис- ; лительной технике. Целью изобретения является расширение функциональных возможностей устройства путем определения ширины ярусов моделируемого графа. Поставленная цель достигается тем, что устройство содержит матрицу 1 размером п х п формирователей дуг, где п - количество вершин в графе, блок 2 управления, генератор 3 импульсов , триггеры 4, п элементов ИЛИ 5 5„, п элементов И 6, - 6„, п счетчиков 7, - 7 , счетчиков 8 числа импульсов и блоки 9 - 9„ сравнения , регистр 10 числа нераспределенных вершин, сумматор 11, вычитатепь 12, блок 13 сравнения с нулем, дополнительный элемент И .14, коммутатор 15, группу из п регистров 16, - 16, блок 17 задержки. 2 ил. с SS (Я со О) оо ю со 4 ГЧ)

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН

„„SU„„1363234

А2 (51) 4 G 06 F 15/20

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ 1:.:,

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ г (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

СЕТЕВЫХ ГРАФОВ (57) Изобретение относится к вычислительной технике ° Целью изобретения является расширение функциональных воэможностей устройства путем опреРие. 1 (6)) .716043 (2)) 4080490/24-24 (22) 15 05.86 (46) 30.12.87. Бюл. Ф 48 (72) Г.Н.Лаврик, Г.В.Буряк и К.В.Митько (53) 628.333(088.8) (56) Авторское свидетельство СССР

Ф 716043, кл. G 06 F 15/20, 1977. деления ширины ярусов моделируемого графа. Поставленная цель достигается тем, что устройство содержит матрицу

1 размером и х и формирователей дуг, где n — количество вершин в графе, блок 2 управления, генератор 3 импульсов, триггеры 4, и элементов

ИЛИ 5 5„, и элементов И 61 - 6., 1 и счетчиков 7, — 7„, счетчиков 8 числа импульсов и блоки 9 1 — 9„ сравнения, регистр IO числа нераспределенных вершин, сумматор 11, вычитатель

12, блок 13 сравнения с нулем, дополнительный элемент И,)4, коммутатор

l5, группу из и регистров 16, — 16„, блок 17 задержки. 2 ил.

1363234

Изобретение относится к вычислительной технике и является усовершенствованием известного устройства по авт. св. СССР Р 716043.

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

На фиг 1 представлена структурная схема предлагаемого устройства; на фиг.2 — структура блока управления.

Устройство содержит матрицу 1 размером и х п, где и — число вершин графа формирователей дуг, блок 2 управления, генератор 3 импульсов, триггеры 4 матрицы, элементы ИЛИ 5, элементы И 6, регистрирующие счетчики 7, счетчик 8 числа-импульсов, блоки 9 сравнения, регистр 10 числа нераспределенных вершин, сумматор 11, вычитатель 12, блок 13 сравнения с нулем, дополнительный элемент И 14, коммутатор 15, группу из и регистров

16, блок 17 задержки. 25

Блок 2 управления содержит ключ

L8 и триггер 19.

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

Первоначально в матрицу 1 заносит- 30 ся информация о топологии моделируемого графа сети. При этом триггеры

4, соответствующие дугам моделируемого графа, устанавливаются в состояние "1". Соответствующий триггер

4 формирователей дуг определяется пересечением строки с номером, равным номеру начального узла моделируемой ветви, и столбца с номером, равным номеру ее конечного узла. После зане- 10 сения исходной информации на выходах элементов ИЛИ 5, объединяющих выходы триггеров 4 формирователей дуг в столбцах, соответствующих начальным узлам моделируемого графа, имеются низкие потенциалы, так как в однонаправленном графе без циклов и петель начальные узлы не содержат входящих ветвей и триггеры 4 формирователей дуг, находящихся в этом столбце, будут в нулевом состоянии. Счетчики 7 в исходном состоянии, а также счетчик 8 и регистры 16 сброшены в нулевое состояние. В регистр 10 заносится код числа вершин в моделируемом графе. Коммутатор 15 в исходном состоянии запрещает прохождение сигналов с информационного входа на выходы.

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

9 вырабатывает импульс, который сбра- сывает в нулевое состояние триггеры

4 формирователей дуг строки с номером, равным номеру столбца, в блоке

9 сравнения которого сравнения не произошло.

При поступлении каждого очередного импульса от генератора 3 через блок 2 управления в схему устройства сумматор 11 формирует на своем выходе двоичный код числа нераспределенных в данный момент времени вершин графа. Этот код вычитается в вычитателе 12 из кода числа, сформированного при поступлении в схему предыдущего импульса, в результате чего форми-, руется код значения ширины j-ro яруса, где j — уменьшенный на единицу порядковый номер поступившего импульса. Текущий код числа нераспределенных вершин через блок 17 задержки поступает в регистр 10. Код значения ширины яруса через коммутатор

15 записывается в соответствующий регистр 16. Коммутатор 15 при поступлении на управляющий вход очередного импульса подключает информационный вход к выходу, номер которого равен порядковому номеру поступившего импульса.

При появлении на выходе сумматора

11 нулевого кода (все вершины распределены) блок 13 фиксирует это собы- . тие выдачей сигнала на вход элемента И 14, который в свою очередь формирует сигнал на входе блока 2 управления. В этом случае происходит останов устройства. В счетчике 8 фиксируется код числа ярусов в моделиI руемом графе, в регистрах 16 содержатся коды значений ширины ярусов, а в регистрирующих счетчиках 7 размещаются коды номеров ярусов (ранги), 1363234 к которым относятся соответствующие вершины.

Формула изобретения

Составитель В. Смирнов

Техред М.Дидьг

Корректор В.Гирняк

Редактор А. Маковская

Заказ 6364/42

Тираж 671 Подписное

BI1HHIIH Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

Устройство для моделирования сетевых графов по авт.св. 9 716043, о тл и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей путем определения значений ширины ярусов моделируемого графа, в него дополнительно введены сумматор, регистр числа нераспределенных вершин, вычитатель, блок сравнения с нулем, дополнительный элемент И, коммутатор, блок задержки и группа из п регистров, где и — число вершин графа, причем i-й (i = 1,...,n) информационный вход сумматора подключен к выходу i-ro элемента И, информационный выход сумматора подключен к входу блока сравнения с нулем, к входу блока задержки и к первому информационному входу вычитателя, выход блока задержки подключен к информационному входу регистра числа нераспределенных вершин, выход которого подключен к второму информационному входу вычитателя, выход которого подключен к информационному входу . коммутатора, выход блока сравнения с нулем подключен к первому входу дополнительного элемента И, выход которого подключен к входу останова блока управления, выход которого подключен к второму входу дополнительного элемента И и к управляющему входу коммутатора, i-й выход которого подключен к информационному входу

i-го регистра группы.