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

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

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

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

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

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

В триггеры 2 матрицы 1 заносится информация о топологии моделируемого графа. При этом триггеры 2, .соответствующие ветвям графа, устанавливаются в единичное состояние согласно матрице смежности графа.

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

Счетчики 6 и 9, 10 и 15 устанавливаются в нулевое состояние.

После пуска устройства триггер 13 находится в нулевом состояний и на его инверсном выходе присутствует высокий потенциал. Поэтому импульсы с выхода генератора 12 через открытьй элемент И 14 поступают на вход счетчика 15. Благодаря этому на выходе дег- шифрЗтора 16 поочередно возбуждаются выхеды.

.

д

|5 20 25 зо

.,5 0

.с

0

5

Каждый выход дешифратора 16 подключен к первому входу элемента И 3 одноименного столбца матрицы. Поэтому с приходом на вход счетчика 15 первого импульса возбуждается первый выход дешифратора 16 и через элементы ИЛИ.8 на входы счетчиков 9, соответствующих вершинам, связанным с первой вершиной, .поступают импульсы. В то же время сигналы с выходов элементов И 3 первого столбца матрицы поступают на входы первого сумматора 19, в котором формируется количество входящих в первую Вершину.дуг. Подобным образом процесс повторяется для всех вершин моделируемого графа. Сигнал переполнения счетчика 15 свидетельствует о завершении этапа определения количества дуг, выходящих из данной вершины. Этот же сигнал разрешает прохождение через элементы И блоков 21 на вторые входы сумматоров 20 значений количества дуг, выходящих из вершин моделируемого графа, обеспечивая тем самым формирование на сумматорах значений суммарного количества дуг,вхо- и выходящих из каждой вершины моделируемого графа.

Кроме того, сигнал переполнения счетчика 15 поступает на вход триггера 13, который переходит в единичное состояние, после чего импульсы с выхода генератора 12 начинают поступать через элемент И 11 на входы элементов И 5 и вход счетчика 10 - на- чи1 ается этап распределения вершин графа по рангам. При этом импульсы не поступают на входы счетчиков 6 тех столбцов, все триггеры которых находятся в нулевом состоянии. Содержимое счетчиков 6 поступает на первые входы одноименных схем 7 сравнения, на другие входы которых поступает информация с выхода счетчика 10.При несовпадении показаний счетчиков 6 и 10 схемы 7 вырабатывают импульс, который устанавливает в нулевое состояние триггеры 2 формирователей дуг строки с номером, равным номеру столбца, в схеме сравнения которого не произошло сравнение.

Вычислительный процесс продолжается до тех пор, пока на выходе 18 устройства не появится сигнал окончания моделирования, который свидетельствует о том, что все вершины моделируемого графа распределены по рангам. Максимальное число последонательных шагов при работе устройства не превышает 2 Р, при этом число импульсов, зафиксированное в счетчиках 6, соответствует номеру ранга каждой вершины.

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

Устройство для моделирования сетевых графов.по авт.св. № 959090, отличающееся тем, что, с целью расширения функциональных возможностей устройства за счет определения суммарного количества входящих и выходящих дуг для каждой вершины моделируемого графа, в него введены две группы по Р сумматоров,где

Р - количество вершин в графе, и группа из Р блоков элементов И, причем выход К-го элемента И (,...,Р) ,формирователя дуги М-й строки матрицы подключен к входу М-го слагаемого К-го сумматора первой группы, выход iKOTOporo подключен к входу первого слагаемого К-го сумматора второй группы, выход М-го счетчика второй группы подключен к первому входу М-го блока элементов И группы, выход которого подключен к входу второго слагаемого М-го сумматора второй группы, выход признака переполнения второго счетчика подключен к второму входу всех блоков элементов И группы.

Изобретение относится к вычислительной технике, может быть испольt зовано для исследования сетевых графов без циклов и- петель и позволяет определить суммарное количество дуг, входящих и выходящих в каждую вершину графа. Устройство содержит матрицу 1 формирователей дуг, каждый из которых содержит триггер 2 и.элемент .ИЗ, группу из Р элементов ИЛИ 4, где Р - количество вершин в графе, группу из Р элементов И 5, группу из Р счетчиков 6, группу из Р схем сравнения, вторую группу из Р счетчиков 9, первый счетчик 10, первый элемент И 11, генератор 12 тактовых импульсов, триггер 13, второй элемент И 14, второй счетчик 15, дешифратор 16, вход 17 пуска устройства, выход 18 признака окончания работы, первую группу сумматоров 19, вторую группу сумматоров 20 и группу блоков 21 элементов И. Введение в базовое устройство группы сумматоров 19 позволяет определять количество дуг, входящих в каждую вершину графа, а введение группы блоков 21 элементов И и группы сумматоров 20 позволяет определять значение суммарного количества входящих и выходящих дуг для каждой вершины графа. 1 ил. Q Ф «Л со о о ;о О) ТЧ)