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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИН 801363 2 5114 С 06 Р 15 Я ОПИСАНИЕ ИЗОБРЕТК А ВТОРСКОМУ СВИДЕТЕЛЬСТВУс,РиеГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(56) Авторское свидетельство СССРВ 716043, кл. С 06 Р 15/20, 1977.(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯСЕТЕВЫХ ГРАФОВ(57) Изобретение относится к вычислительной техникеЦелью изобретенияявляется расширение функциональныхвоэможностей устройства путем определения ширины ярусов моделируемого графа. Поставленная цель достигается тем, что устройство содержит матрицу 1 размером и х и формирователей дуг, где и - количество вершин в графе, блок 2 управления, генератор 3 импульсов, триггеры 4, и элементовэлемен1п счетчиков 7, - 7, счетчиков 8 числа импульсов и блоки 9 1 - 9сравнения, регистр О числа нераспределенных вершин, сумматор 11, вычитатель 12, блок 13 сравнения с нулем, дополнительный элемент И,4, коммутатор 5, группу из п регистров 16, - 16, блок 17 задержки. 2 ил.50 Изобретение относится к вычислительной технике и является усовершенствованием известного устройствапо авт. св, СССР Р 716043.Целью изобретения является расширение функциональных возможностейпутем определения значений шириныярусов моделируемого графа.На фиг 1 представлена структурная .10схема предлагаемого устройства; нафиг.2 - структура блока управления.Устройство содержит матрицу 1 размером п х и, где и - число вершинграфа формирователей дуг, блок 2 уп бравления,. генератор 3 импульсов,триггеры 4 матрицы, элементы ИЛИ 5,элементы И 6, регистрирующие счетчики 7, счетчик 8 числа. импульсов, блоки 9 сравнения, регистр 10 числа нераспределенных вершин, сумматор 11,вычитатель 12, блок 13 сравнения снулем, дополнительный элемент И 14,коммутатор 15, группу из и регистров16, блок 17 задержки. 25Блок 2 управления содержит ключ8 и триггер 19,Устройство работает следующим образом,Первоначально в матрицу 1 заносится информация о топологии моделируемого графа сети. При этом триггеры4, соответствующие дугам моделируемого графа, устанавливаются в состояние "1". Соответствующий триггер354 формирователей дуг определяетсяпересечением строки с номером, равнымномеру начального узла моделируемойветви, и столбца с номером, равнымномеру ее конечного узла. После зане- ф 0сения исходной информации на выходахэлементов ИЛИ 5, объединяющих выходытриггеров 4 формирователей дуг встолбцах, соответствующих начальнымузлам моделируемого графа, имеютсянизкие потенциалы, так как в однонаправленном графе без циклов и петельначальные узлы не содержат входящихветвей и триггеры 4 формирователейдуг, находящихся в этом столбце, будут в нулевом состоянии. Счетчики 7в исходном состоянии, а также счетчик 8 и регистры 16 сброшены в нулевое состояние, В регистр 1 О заносится код числа вершин в моделируемомграфе. Коммутатор 15 в исходном состоянии запрещает прохождение сигналов с информационного входа на выходы. С появлением пускового сигнала на входе устройства блок 2 управления разрешает прохождение импульсов с выхода импульса генератора 3 на вторые входы всех элементов 6 и счетчика 8. При этом импульсы не проходят через элементы 6 на счетчики 7 тех столбцов, все триггеры 4 которых находятся в нулевом состоянии. Далее содержимое счетчиков 7 поступает на один вход блока 9 сравнения соответствующего столбца, а на другие входы этих блоков сравнения поступает информация со счетчика 8, При несовпадении показаний счетчиков 7 и 8 блок 9 вырабатывает импульс, который сбра- сывает в нулевое состояние триггеры 4 формирователей дуг строки с номером, равным номеру столбца, в блоке 9 сравнения которого сравнения не произошло.При поступлении каждого очередного импульса от генератора 3 через блок 2 управления в схему устройства сумматор 11 формирует на своем выходе двоичный код числа нераспределенных в данный момент времени вершин графа, Этот код вычитается в вычитателе 12 из кода числа, сформированного при поступлении в схему предыдущего импульса, в результате чего форми-, руется код значения ширины -го яруса, где 3 - уменьшенный на единицу порядковый номер поступившего импульса. Текущий код числа нераспределенных вершин через блок 17 задержки поступает в регистр 10. Код значе" ния ширины яруса через коммутатор 15 записывается в соответствующий регистр 16. Коммутатор 15 при поступлении на управляющий вход очередного импульса подключает информационный вход к выходу, номер которого равенпорядковому номеру поступившего импульса.При появлении на выходе сумматора 11 нулевого кода (все вершины распределены) блок 13 фиксирует это событие выдачей сигнала на вход элемента И 14, который в свою очередь формирует сигнал на входе блока 2 управления. В этом случае происходит останов устройства. В счетчике 8 фиксируется код числа ярусов в моделируемом графе, в регистрах 16 содержатся коды значений ширины ярусов, а в регистрирующих счетчиках 7 размещаются коды номеров ярусов (ранги),1363234 Составительаковская Техред М.Дид н В,В.Ги А к каз 636 2 Тираж 67 Государст елам иэоб Москва, Подпикомитета СССРи открытийушская наб., д. е енного етений -35, Р по 11303изводственно-полиграфическое предприятие, г. Ужгород, ул. Проектная,к которым относятся соответствующиевершины. Формула изобретения Устройство для моделирования сетевых графов по авт.св. У 716043, о тл и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей путем определения значений ширины ярусов моделируемого графа, в него дополнительно введены сумматор, регистр числа нераспределенных вершин, вычитатель, блок сравнения 15 с нулем, дополнительный элемент И, коммутатор, блок задержки и группа из и регистров, где и - число вершин графа, причем д-й (1 = 1п) информационный вход сумматора подключен к выходу -го элемента И, информационный выход сумматора подключенк входу блока сравнения с нулем, квходу блока задержки и к первому информационному входу вычитателя, выход блока задержки подключен к информационному входу регистра числа нераспределенных вершин, выход которого подключен к второму информационному входу вычитателя, выход которого подключен к информационному входу,коммутатора, выход блока сравненияс нулем подключен к первому входудополнительного элемента И, выход которого подключен к входу остановаблока управления, выход которого подключен к второму входу дополнительного элемента И и к управляющему входу коммутатора, д-й выход которогоподключен к информационному входу