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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Свюз СоветскихСоциалистическихРеспублик(22) Заявлено 020281 (21) 3243208/18-24 Р 1 М Кп з С 06 Г 15/20 с присоединением заявки Ио Государственный комитет СССР но делам изобретений и открытийОпубликовано 15.0282, Бюллетень Мо 34 Дата опубликования описания 150982(72) Авторизобретения В.А. Титов 1) Заявитель 4) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ ГРАФОВИзобретение относится к области вычислительной техники и может быть использовано при исследовании сетевых графов, а также при организации. вычислительного процесса в диспетчерах управляющих многомашинных вычис" лительных систем при решении инфор-.мационно-связанного пакета задач управления объектом или процессом. 0Известно устройство для определения максимальных путей в графах, содержащее триггеры по числу строк и столбцов матричной модели, генератор тактовых импульсов, элемент ИЛИ, первый элемент И, по числу столбцов матричной модели сети первые элементы И, счетчики "весов" вершин, триггеры управления, вторые элементы И, регистрирующие счетчики, по числу строк матричной модели сети элементы ИЛИ-НЕ, выходы которых подсоединены к управ" ляющим входам одноименных первых элементов И, выходы кОторых соединены с входами одноименных счетчиков "весов" вершин, выходы которых под соединены к установочным входам триггеров одноименных столбцов и к входам одноименных триггеров управления, выходы которых соединены с управляющи" ми входами одноименных вторых элементов И и с входами элемента ИЛИ, вы-.ход которого подсоединен к первомувходу первого элемента.И, выход которого соединен. с информационными входами первых и вторых элементов И,выход генератора. тактовых импульсовподсоединен к второму входу первогоэлемента И 1.Наиболее близким техническим решением к изобретению является устройство для определения максимальных путей в графах, содержащее триггеры,.группу элементов ИЛИ-НЕ, первую группу элементов И, группу счетчиков"веса 1 вершины, группу триггеров уп-равления, вторую группу элементов И,элемент ИЛИ, первый элемент И, генератор тактовых импульсов, второйэлемент И, блок выбора кода максимального числа, дополнительный счетчик, дешифратор, .элементы И, третьюгруппу элементов И, группу. элементовИЛИ, группу регистрирующих триггерови четвертую группу элементов И 2);Недостатком известных устройствявляется невозможность определениячисла выходящих дуг для каждой вершины моделируемого графа,Цель изобретения - расширениефункциональных возможностей устройства эа счет определения числа выходя,щих дуг для каждой вершины моделируемого графа.Указанная цель достигается тем,что в устройство для моделированиясетевых графов, содержащее матрицу 5формирователей дуг, в каждом формиро-вателе дуг матрицы выход триггерасоединен с управляющим входом элемента И, выходы элементов И одноименнойстроки матрицы подключены к входам 10, элементов ИЛИ первой группы, группуэлементов И, первый и второй элементы:И, выход первого элемента И соединен с информационными входами элементов И группы, выход каждого элемента И группы подключен к входусоответствующего регистрирующегосчетчика первой группь, первыйсчетчик, генератор тактовых импульсов, выход которого соединены с информационными входами первого ивторого элементов И, выход второгоэлемента И подключен к входу второгосчетчика, первый выход которого соединен со входом дешифратора, введеныгруппа схем сравнения, триггер, вторая группа регистрирующих счетчиков,. вторая группа элементов ИЛИ, выходыкоторых подключены к управляющимвходам соответствующих элементов Игруппы, выход первого счетчика соеди-ЗОнен с первыми входами схем сравнениягруппы, выходы которых подключенык входам триггеров соответствующейстроки матрицы формирователей дуг,выходы триггеров каждого столбца мат рицы Формирователей дуг соединенысо входами соответствующего элемен.та ИЛИ второй группы, выходы регист"рирующих счетчиков первой группы подключены ко вторым входам соответст рвующих схем сравнения группы, выходпервого элемента И соединен с входомпервого счетчика, второй выход второ"го счетчика подключен к входу триггера, выходы которого соединены суправляющими входами первого и второго элементов И, выходы дешифратораподключены к информационным входамэлементов И формирователей дуг матрицы, выходы элементов ИЛИ первойгруппы соединены со входами регистрирующих счетчиков второй группы,На чертеже приведена структурнаясхема устройства..Устройство для моделирования сетевьв графов содержит матрицу 1 формирователей дуг в составе триггеров 2и элементов И 3, по числу столбцов,матрицы вторую группу элементов ИДИ4,44 где п " максимальноечйсло вершин в граФе, группу элемен Отов И 5, 5,5, первую группурегистрирующих счетчиков 66 ,6;группу схем сравнения 7,7 а,7,вторую группу элементов ИЛИ 8,88, вторую группу регистрирую щих счетчиков 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 подключена к первым входам элементов И 3 одноименного столбца матрицы. Поэтому с приходом первого импульса на вход счетчика 15 возбуждается первая выходная шина дешифратора 16 и через элементы ИЛИ 8 импульсы напряжения поступают на входы счетчиков 9, соответствующих тем вершинам, для которых имеется дуга в первую вершину, и т.д. для всех вершин моделируемого графа. Сигнал переполнения счетчика 15 с его второго выхода свидетельствует о завершении этапа определения числа дуг иэ данной вершины (для всех вершин) и поступает на вход триггера 1.3, который перебрасывается в единичное состояние, после чего с выхода генератора 12 прекращается подача счетных импульсов на .вход счетчика 15 и начинается поступление счетных импульсов через элемент И 11 на входыэлементов И 5 и вход счетчика 10этап распределения вершин графа порангам. При этом импульсы не прохо"дят через элементы И 5 на счетчикиб тех столбцов., все триггеры 2.кото"рых находятся в нулевом состоянии.Далее содержимое счетчиков б поступает на первые входы одноименных схемсравнения 7 соответствующего столбца,а на другие входы этих схем поступает информация с выхода счетчика 10,При несовпадении показаний счетчиковб и 10 схемы 7 вырабатывают импульс,который сбрасывает в нулевое состояние триггера 2 формирователей дугстроки с номером, равным номеру столбца, в схеме сравнения которого непроизошло сравнение. После этого свыхода генератора 12 через элемент И11 поступает очередной импульс на 2 Овходы элементов И 5 и счетчика 10.Вычислительный процесс продолжается до тех пор, пока происходит сравнение в схемах 7 и на выходе 18 счетчика 10 появляется сигнал переполне. ния. Это свидетельствует о том, чтовсе .вершины моделируемого графа распределены по рангам, Максимальноечисло последовательных шагов при работе устройства не превышает 2 И,где и - число вершин в моделируемомграфе. Число импульсов, зафиксированное на.счетчиках б, соответствует номеру ранга .для каждой вершины.Таким образом, благодаря введениюв устройство новых элементов и свя- . З 5зей расширяются его функциональные. возможности оперативное определениечисла дуг, исходящих из данной верши"ны).40Формула изобретенияУстройство для моделирования сетевых графов, содержащее матрицу Форми рователей дуг, в каждом формирователе дуг матрицы выход триггера соединен С управляющим входом элемента И, выходы ;элементов И одноименной строки матри" цы формирователей дуг подключены к вхо-дам элементов ИЛИ первой группы, группу,элементов И,первый и второй элементыИ, выход первого элемента И соединенс информационными входами элементовИ группы, выход каждого элемента Игруппы подключен к входу соответствующего регистрирующего счетчика первойгруппы, первый счетчик, генератор так"товых импульсов, выход которого соединен с информационными входами первогои второго элементов И, выход второгоэлемента И подключен к входу второгосчетчика, первый выход которого соединен со входом дешифратора, о т -л и ч а ю щ е е с я тем, что, сцелью расширения Функциональных возможностей за счет определения числадуг, исходящих из каждой вершины гра"фа,. в него введены группа схем сравнения, триггер, вторая группа регистрирующих счетчиков, вторая группа элементов ИЛИ, выходы которых подключенык управляющим входам соответствующихэлементов И группы, выход первогосчетчика соединен с первыми входамисхем сравнения группы, выходы которыхподключены к входам триггеров соответствующей строки матрицы формирователей .дуг,. выходы триггеров каждогостолбца матрицы формирователя дугсоединены со входами. соответствующего элемента ИЛИ второй группы, выходы регистрирующих счетчиков первойгруппы подключены ко вторым входамсоответствующих схем сравнения группы,:выход первого элемента И соединен с входом первого счетчика, второй выход второго счетчика подключенк входу триггера, выходы которогосоединены с управляющими входами первого и второго элементов И, выходыдешифратора подключены:к информацион-ным входам элементов И формирователядуг матрицы, выходы элементов ИЛИпервой группы соединены со входамирегистрирующих счетчиков второй группы.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССР. по заявке Р 28 б 1750/18-24,кл. О Об Г 15/20, 1980.2. Авторское свидетельство СССРпо заявке 9 3007322/18-24,кл. 6 Об Г 15/20, 1980 (прототип)..Колесникова Техред. З.ПалийКорректор А.Гриценк дакт писное 5 Филиал ППП "Патент", г. УЖгород, ул . Проектная, 4 Закаэ 7018/бб ТиВНИИПИ Государстпо .делам иэобр 113035, Москва,аж 731 Пенного комитета СССРтений и открытий