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

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

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

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

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

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

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

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

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

При поступлении каждого очередного импульса от генератора 3 через блок 2 управления в схему устройства сумматор 11 формирует на своем выходе двоичный код числа нераспределенных в данный момент времени вершин графа. Этот код вычитается в вычита5

0

5

0

5

го при поступлении.в схему предыдущего импульса, в результате чего формиг руется код значения ширины j-ro яруса, где j - уменьшенный на единицу порядковый номер поступившего импульса. Текущий код числа нераспределенных вершин через блок 17 задержки поступает в регистр 10. Код значения ширины яруса через коммутатор 15 записывается в соответствующий регистр 16. Коммутатор 15 при поступлении на управляющий вход: очередного импульса подключает информационный вход к выходу, номер которого равен порядковому номеру поступившего импульса.

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

к которым относятся вершины.

соответствующие

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

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

Изобретение относится к вычис- ; лительной технике. Целью изобретения является расширение функциональных возможностей устройства путем определения ширины ярусов моделируемого графа. Поставленная цель достигается тем, что устройство содержит матрицу 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 ГЧ)

Составитель В. Смирнов Редактор А. Маковская Техред М.ДидкхКорректор В.Гирняк

Заказ 6364/42

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Разпааская наб., д, 4/5

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

иа 2