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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Республик

<щ959090 (1

/,».",» (61) Дополнительное к авт, свид-ву (22) Заявлено 020281 (21) 3243208/18-24

f $ $ 3 М. Кп. з

G 06 F 15/20

Ф с присоединением заявки №

Государственный комитет

СССР по делам изобретений и открытий (23) Приоритет (Щ УДК . 681. 333 (088.8) Опубликовано 150982. Бюллетень ¹ 34

Дата опубликования описания 150982 г .

» (72) Автор изобретения

В.А. Титов »

» (71) Заявитель (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ

ГРАФОВ

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

Известно устройство для определения максимальных путей в графах, содержащее триггеры по числу строк и столбцов матричной модели, генератор тактовых импульсов, элемент ИЛИ, первый элемент И, по числу столбцов матричной модели сети первые элементы И, счетчики "весов" вершин, триггеры управления, вторые элементы И, регистрирующие счетчики, по числу строк матричной модели сети элементы ИЛИ-НЕ, выходы которых подсоединены к управляющим входам одноименных первых элементов И, выходы кОторых соединены с входами одноименных счетчиков

"весов" вершин, выходы которых под- 25 соединены к установочным входам триггеров одноименных столбцов и к входам одноименных триггеров управления, выходы которых соединены с управляющими входами одноименных вторых элемен- 30

» тов И и с входами элемента ИЛИ, вы-. ход которого подсоединен к первому входу первого элемента.И, выход которого соединен с информационными входами первых и вторых элементов И,выход генератора. тактовых импульсов подсоединен к второму входу первого элемента И 1).

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

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

HJIH, группу регистрирующих триггеров и четвертую группу элементов И $2);

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

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

Указанная цель достигается тем, что в устройство для моделирования сетевых графов, содержащее матрицу формирователей дуг, в каждом формиро- вателе дуг матрицы выход триггера соединен с управляющим входом элемента И, выходы элементов И одноименной строки матрицы подключены к входам 30 . элементов ИЛИ первой группы, группу элементов И, первый и второй элемен ты: И, выход первого элемента И соединен с информационными входами элементов И группы, выход каждого элемента И группы подключен к входу соответствующего регистрирующего счетчика первой группы, первый счетчик, генератор тактовых импульсов, выход которого соединены с информационными входами первого и второго элементов И, выход второго элемента И подключен к входу второго счетчика, первый выход которого соединен со входам дешифратора, введены группа схем сравнения, триггер, вторая группа регистрирующих счетчиков, . вторая группа элементов ИЛИ, выходы которых подключены к управляющим входам соответствующих элементов И группы, выход первого счетчика соеди-30 нен с первыми входами схем сравнения группы, выходы которых подключены к входам триггеров соответствующей строки матрицы формирователей дуг, выходы триггеров каждого столбца мат-35 рицы формирователей дуг соединены со входами соответствующего элемен.та ИЛИ второй группы, выходы регистрирующих счетчиков первой группы подключены ко вторым входам соответст- 4О вующих схем сравнения группы, выход первого элемента И соединен с входом первого счетчика, второй выход второ" го счетчика подключен к входу триггера, выходы которого соединены с управляющими входами первого и второго элементов И, выходы дешифратора подключены к информационным входам элементов И формирователей дуг матрицы, выходы элементов ИЛИ первой группы соединены со входами регистрирующих счетчиков второй группы.

На чертеже приведена структурная схема устройства.

1 Устройство для моделирования сетевьис -графов содержит матрицу 1 формирователей дуг в составе триггеров 2 и элементов И 3, по числу столбцов ,матрицы вторую группу элементов ИДИ

4,4>,...,4>, где n " максимальное чйсло вершин в графе, группу элемен- 6Î тов И 5„, 5,...5, первую группу регистрирующих счетчиков 6 р 6д у ° ° би группу схем сравнения 7,7,...7, -вторую группу элементов ИЛИ 8, 8« ...,8, вторую группу регистрирую- 65 щих счетчиков 9, 9,...,9,„, первый счетчик 10, .первый элемент И 11, ге-. нератор тактовых импульсов 12, триггер 13, второй элемент И 14, второй счетчик 15, дешифратор 16, вход 17, выход 18.

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

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

4, объединяющих выходы триггеров 2 формирователей дуг в столбцах, соответствующих начальным узлам моделируемого графа,.будут низкие потенциалы, так как в,однонаправленном графе без циклов и петель начальные узлы не содержат входящих ветвей, и триггеры формирователей дуг, находящихся.в этом столбце, находятся в нулевом состоянии. Регистрирующие счетчики 6 и 9, а также счетчики 10 и 15 числа импульсов в исходном состоянии сброшены в нулевое состояние.

Определение числа дуг, исходящих из данной вершины, осуществляется после записи информации (при наличии входного сигнала на входе 17). Так. как триггер 13 находится н нулевом" состоянии, то на его нулевом выходе высокий потенциал, поэтому счетные импульсы с выхода генератора 12 через открытый элемент И 14 поступают на вход счетчика 15, выход которого подключен к входу дешифратора 16, на выходе которого поочередно возбуждаются выходные шины. Каждая выходная шина дешифратора 16 подключена к первым входам элеменroa И 3 одноименного столбца матрицы. Поэтому с приходом первого импульса на вход счетчика 15 возбуждается первая выходная шина дешифратора 16 и через элементы ИЛИ 8 импульсы напряжения поступают на входы счетчиков 9, соответствующих тем вершинам, для которых имеется дуга в первую вершину, и т.д. для всех вершин моделируемого графа.

Сигнал переполнения счетчика 15 с его второго выхода свидетельствует о завершении этапа определения числа дуг иэ данной вершины (для всех вершин) и поступает на вход триггера 1.3, который перебрасывается в единичное состояние, после чего с выхода генератора 12 прекращается подача счетных импульсов на .вход счетчика 15 и начинается поступление счетных им959090 пульсов через элемент И 11 на входы элементов И 5 и вход счетчика 10 этап распределения вершин графа по рангам. При этом импульсы не проходят через элементы И 5 на счетчики б тех столбцов., все триггеры 2.которых находятся в нулевом состоянии .

Далее содержимое счетчиков б поступает на первые входы одноименных схем сравнения 7 соответствующего столбца, а на другие входы этих схем поступа- 10 ет информация с выхода счетчика 10.

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

11 поступает очередной импульс на 2О входы элементов И 5 и счетчика 10.

Вычислительный процесс продолжается до тех пор, пока происходит сравнение в схемах 7 и на выходе 18 счетчика 10 появляется сигнал переполне. ния. Это свидетельствует о том, что все .вершины моделируемого графа распределены по рангам. Максимальное число последовательных шагов при работе устройства не превышает 2N, где n — - число вершин в моделируемом графе. Число импульсов, зафиксированное на.счетчиках б, соответствует номеру ранга для каждой вершины.

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

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

Устройство для моделирования сетевых графов, содержащее матрицу Форми- 45 рователей дуг, в каждом формирователе дуг матрицы выход триггера соединен с управляющим входом элемента И, выходы

; элементов И одноименной строки матри- . цы формирователей дуг подключены к вхо- О . дам элементов ИЛИ первой группы, группу,элементов И,первый и второй элементы

И, выход первого элемента И соединен с информационными входами элементов

И группы, выход каждого элемента И группы подключен к входу соответствующего регистрирующего счетчика первой группы, первый счетчик, генератор тактовых импульсов, выход которого соединен с информационными входами первого и второго элементов И, выход второго элемента И подключен к входу второго счетчика, первый выход которого соединен со входом дешифратора, о т— л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет определения числа дуг, исходящих из каждой вершины граФа,. s него введены группа схем сравнения, триггер, вторая группа регистрирующих счетчиков, вторая группа элементов ИЛИ, выходы которых подключены к управляющим входам соответствующих элементов И группы, выход первого счетчика соединен с первыми входами схем сравнения группы, выходы которых подключены к входам триггеров соответствующей строки матрицы Формирователей .дуг,. выходы триггеров каждого столбца матрицы формирователя дуг соединены со входами. соответствующего элемента ИЛИ второй группы, выходы регистрирующих счетчиков первой группы подключены ко вторым входам соответствующих схем сравнения группы,:выход первого элемента И соединен с входом первого счетчика, второй выход второго счетчика подключен к входу триггера, выходы которого соединены с управляющими входами первого и второго элементов И, выходы дешифратора подключены:к информацион-I ным входам элементов И формирователя дуг матрицы, выходы элементов ИЛИ первой группы соединены со входами регистрирующих счетчиков второй группы.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР по заявке 9 2861750/18-24, кл. G Об F 15/20, 1980.

2. Авторское свидетельство СССР по заявке 9 3007322/18-24, кл. G 06 F 15/20, 1980 (прототип) .

Составитель И.Дубинина

Редактор О.Колесникова Техред. 3.Палий Корректор A.Гринденко

Закаэ 7018/бб Тираж 731 Подписное

ВНИИПИ Государственного комитета СССР по .делам иэобретений и открытий

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

Филиал ППП "Патент", г. УЖгород, ул . Проектная, 4