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

(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ

ГРАФОВ

Изобретение относится к области вычислительной техники и может быть использовано при исследовании сетевых графов, а также при организации вычислительного процесса в диспетчерах управляющих многомашинных вычислительных систем при решении информационно-связанного пакета задач управления объектом или процессом. . Известно устройство для опредёления максимальных путей в графах, содержащее триггеры по числу строк и столбцов матрИ ной модели, генератор тактовых импульсов, элемент ИЛИ, пер вый элемент И, по чис;лу столбцов мат ричной модели сети первые элемёнтй И счетчики весов вершин триггеры уп равления, вторые элементы И, регистрирующие счётчики, по числу строк матричной модели сети элементы ИЛЙ-Н выходы которых подсоединены к управляющим входам одноименных первых , элементов И, выходы которых соединены с входами одноименных счетчиков весов вершин, выходы которых подсоединены к установочным входам триг геров одноименных столбцов и к входа одноименных триггеров управления, вы ходы которых соединены с управляющими входами одноименных вторых элемен тов и и с входами элемента ИЛИ, вы-. ход которого подсоединен к первому входу первого элемента.И, выход которого соединен, с информационными входами первых и вторьах элементов И,выход генератора.тактовых импульсов подсоединен к второму входу первого элемента И l. Наиболее близким техническим решением к изобретению является устройство для определения максимальных путей в графах, содержащее триггеры,. группу элементов ИЛИ-НЕ, первую группу элементов И, группу счетчиков веса вершины, группу триггеров равления, вторую группу элементов И, элемент ИЛИ, первый элемент И, генератор тактовых импульсов, второй элемент И, блок выбора кода максимального числа, дополнительный счетчик, дешифратор, элементы И, третью группу элементов И, группу элементов ИЛИ, группу регистрирующих триггеров и четвертую группу элементов И Недостатком известных устройств является невозможность определения числа выходящих дуг для каждой вершины моделируемого графа. Цель изобретения - расширение функциональных., возможностей устройства за счет определения числа выходя .тих- дуг для каждой вершины моделиру мого графа. Указанная цель достигается тем, что в устройство для моделирования сетевых графов, содержащее матрицу формирователей дуг, в каждом формир вателе дуг матрицы выход триггера соединен с управляющим входом элеме та И, выходы элементов И одноименной строки матрицы подключены к входам элементов ИЛИ первой группы, группу элементов И, первый и второй элемен ты.И, выход первого элемента И соединен с информационными входами элементов И группы, выход каждого элемента И группы подключен к входу соответствующего регистрирующего счетчика первой группы, первый счетчик, генератор тактовых импульсов, выход которого соединены с информациейными входами первого и второго элементов И, выхол второго элемента И подключен к входу второго счетчика, первый выход которого соединен со входом дешифратора, введены группа схем сравнения, триггер, вторая группа регистрирующих счетчиков вторая группа элементов ИЛИ, выходы которых подключены к управляющим входам соответствующих элементов И группы, выход первого счетчика соеди нен с первыми входами схем сравнения группы, выхрдьй которых подключены к входам триггеров соответствующей строки матрицы формирователей дуг, выходы триггеров каждого столбца мат рицы формирователей дуг соедине - ка со входами соответствующего элемента ИЛИ второй группы, выходы регистрирующих счетчиков первой группы под ключены ко вторым входам соответствующих схем сравнения группы, выход первого элемента И соединен с входом первого счетчика, второй выход второ го счетчика подключен к входу триггера, выходы которого соединены с управляющими входами первого и второ го элементов И, выходы дешифратора подключены к ивформадионнь входам элементов И формирователей дуг матрицы, выходы элементов ИЛИ первой группы соединены со входами регистри рующих счетчиков второй группы . На чертеже приведена структурная схема устройства. Устройство для моделирования сете ВЕлх-графов содержит матрицу 1 формирователей дуг в составе триггеров 2 и элементов И 3, по числу столбцов .матрлцы вторую группу г лёментов ИЛИ 4|,42, .. . ,4ц, где п - максимальное число вершин в графе, группу элементов И Sj, , Sj.,. ., 5,, первую группу регистрирующих счетчиков б , б, ., . 6 группу схем сравнения 7 ,7г,,..7ц, -вторую группу элементов ИЛИ 8 , 8yj,.. . , 8,, вторую группу регистрирую щих счетчиков 9 , 9, , , . , ,Э , первый счетчик 10, .первый элемент И 11, ге-; нератор тактовых импульсов 12, триггер 13, второй элемент И 14, второй счетчик 15, дешифратор 1б, вход 17, выход 18. Устройство работает следующим образом. Первоначально в триггеры 2 матрицы 1 заносится информация о топологии моделируемого графа сети. При этом триггеры 2 формирователей дугi моделирующих ветви графа, устанавливаются в единичное состояние. Соответствующий триггер 2 формирователей дуг определяется пересечением строки с номером, равным номеру начального узла моделируемой ветви, и столица с номером, равным номеру ее конечного узла. После занесения исходной информации на выходах элементов ИЛИ 4, объединяющих выходы триггеров 2 формирователей дуг в столбцах, соответствующих начальным узлам моделируемого графа,.будут низкие потенциалы, так как в однонаправленном графе без циклов и петель начальные узлы не содержат входящих ветвей, и триггеры формирователей дуг, находящихся, в этом столбце, находятся в. ну левом состоянии. Регистрирующие счетчики В и 9, а также счетчики 10 и 15 числа импульсов в исходном состоянии сброшены в нулевое состояние. Определение числа дуг, исходящих из данной вершины, осуществляется ; после записи информации (при наличии входного сигнала на входе 17). Так. как триггер 13 находится в нулевом состоянии, то на его нулевом выходе высокий потенциал, поэтому счетные импульсы с выхода генератора 12 через открытьай элемент И 14 поступают на вход счетчика 15, выход которого подключен к входу дешифратора 16, на.выходе которого поочередно возбуждаются выходные шины. Каждая выходная шина дешифратор1а 16 подключена к первым входам элементов И 3 одноименного столбца матрицы. Поэтому с приходом первого импульса на вход счетчика 15 возбуждается первая выходная шина дешифратора 16 и через элементы ИЛИ 8 импульсы напряжения поступают на входы счетчиков 9, соответствующих тем вершинам, для которых имеется дуга в первую вершину, и т.д. для всех вершин моделируемого графа. Сигнал переполнения счетчика 15 с его второго выхода свидетельствует о завершении этапа определения числа дуг из данной вершины (для всех вершин) и поступает на вход триггера 13, который перебрасывается в единичное состояние, после чего с выхода генератора 12 прекращается подача счетных импульсов на вход счетчика 15 и начинается поступление счетных импульсов через элемент И 11 на входы элементов И 5 и вход счетчика 10 этап распределения вершин графа по рангам. При этом импульсы не проходят через элементы И 5 на счетчики 6 тех столбцов., все триггеры 2. которых находятся в нулевом состоянии. Далее содержимое счетчиков 6 поступ ет на первые входы одноименных схем сравнения 7 соответствующего столбца а на другие входы этих схем поступает информация с выхода счетчика 10. При несовпадении показаний счетчиков 6 и 10 схемы 7 вырабатывают импульс, который сбрасывает в нулевое состояние триггера 2 формирователей дуг стройи с номером, равным номеру столб ца, в схеме сравнения которого не произошло сравнение. После этого с выхода: генератора 1:2 через элемент И U.1 поступает очередной импульс на элементов И 5 и счетчика 10. Вычислительный процесс продолжается до тех пор, пока ПРОИСХОДИТ сравнение в схемах 7 и на выходе 18 счетчика 10 появляется сигнал переполнения. Это свидетельствует о том, что все .вершины моделируемого графа распределены по рангам. Максимальное число последовательных шагов при работе устройства не превышает 2п где п - число вершин в мод;елируемом графе. Число импульсов, зафиксирован ное на . счетчиках 6,, соответствует МО меру ранга для каждой вераины. Таким образом, благодаря введению в устройство новых элементов и связей расширяются его функциональные возможности (оперативное определение числа дуг, исходящих из данной верии НЫ). :; Формула изобретения Устройство для моделирования сете вых.графов, содержащее матрицу форми рователей дуг, в каждом формировател уг матрицы выход триггера соединен С управляющим входом элемента И, выходы 1 элементов И одноименной строки матрицы формирователей дуг подключены к входам элементов ИЛИ первой группы, группу :Элемен ов И, первый и второй элементы И, выход первого элемента И соединен с информационными входами элементов И группы, выход каждого элемента И группы подключен к входу соответствующего регистрирующего счетчика первой группы, первый счетчик, генератор тактовых импульсов, выход которого соединен с информационными входами первого и второго элементов И, выход второго элемента И подключен к входу второго счетчика, первый выход которого соединен со входом дешифратора, отличающееся тем, что, с целью расширения функциональных возможностей за счет определения числа дуг, исходящих из каждой вершины графа, в него введены группа схем сравнения, триггер, вторая группа регистрирующих счетчиков, вторая группа элементов ИЛИ, выходы которых подключены к управляющим входам соответствующих элементов И группы, выход первого счетчика соединен с первыми входами схем сравнения группы, выходы которых подключены к входам триггеров соответствующей строки матрицы формирователей дуг, выходы триггеров каждого столбца матрицы формирователя дуг соединены со входами соответствующего элемента ИЛИ второй группы, выходы регистрирующих счетчиков первой группы подключены ко вторым входам соответствующих схем сравнения группы, выход первого элемента И соединен с входом первого счетчика, второй выход второго счетчика подключен к входу триггера, выходы которого соединены с управляющими входами первого и второго элементов И, выходы дешифратора подключены к информацион-j ным входам элементов И формирователя дуг матрицы, выходы элементов ИЛИ первой группы соединены со входами регистрирующих счетчиков второй группы. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР по заявке № 2861750/18-24, кл. G 06 F 15/20, 1980. 2.Авторское свидетельство СССР по заявке № 3007322/18-24, кл. G 06 F 15/20, 1980 (прототип).