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

 

УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ ГРАФОВ, содержащее матричную модель графа, ij -и узел которой включает триггер, первый и второй элементы И, причем выход триггера подключен к первым входам первого и второго элементов И, первую и вторую группы элементов ИЛИ, первую и вторую группы триггеров, элемент И, генератор тактовых импульсов, счетчик, причем выход (-го (; ...п) .триггера первой группы подключен к вторым входам первых элементов И i -и с троки матричной модели графа, выход -го триггера второй группы соединен с вторыми входами вторых элементов И i-го столбца матричной модели графа, выход первого элемента И Ц -го узла матричной модели графа подключен к соответствующему входу i -го элемента ИЛИ первой группы, выход второго элемента И ij -го узла матричной модели графа соединен с соответствующим входом i -го элемента ИЛИ второй группы, выход i-го элемента ИЛИ первой группы подключен к единичному входу i -го триггера первой группы , выход i-го элемента ИЛИ второй группы соединен с единичным входом i-ro триггера второй группы, отличающееся тем, что, с целью повышения быстродействия, в него введены дешифратор и элемент i задержки, выход которого подключен к нулевым входам триггеров первой (Л и второй групп, выход генератора тактовых импульсов соединен с первым входом элемента И, второй вход которого является входом запуска устройства , выход элемента И подключен к входу элемента задержки и входу счетчика, выход которого соединен с входом дешифратора, выходы которого подключены соответственно к входам элементов ИЛИ первой и второй групп.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН

3(51) 6

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

H АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3529159/18-24 (22) 27 ° 12.82 (46) 23.02.84. Бюл. М .7 (72) В.A.Òèòîâ, В.Л.Гайдуков и В.В.Зотов (53) 681. 3 33 (088. 8)

{56) 1. Авторское свидетельство СССР

9 716043, кл. Cj 06 Р 15/20, 1980.

2. Авторское свидетельство СССР

Р 913389, кл. С« 06 Г 15/20, 1982 (прототип) . (54) (57) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

СЕТЕВЫХ ГРАФОВ, содержащее матричную модель графа, «« -й узел которой включает триггер, первый и второй элементы И, причем выход триггера подключен к первым входам первого и второго элементов И, первую и вторуЮ группы элементов ИЛИ, первую и вторую группы триггеров, элемент И, генератор тактовых импульсов, счетчик, причем выход « -го (j ...n) .триггера первой группы подключен к вторым входам .-первых элементов И « -й строки матрич1 ной модели графа, выход « -го триггера второй группы соединен с вторыми входами вторых элементов И « --ro столбца матричной модели графа, выas>®

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

1075268

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

I 1

Известно устройство для моделирования сетевых графов, содержащее блок упранления, первый вход которого соединен с выходом генератора тактовых импульсов, счетчик импульсов, тригге- 15 ры формирователей дуг по числу строк и столбов матричной модели сети, по числу столбцов матричной модели сети элементы ИЛИ, элементы И, регистрирующие счетчики, схемы сравнения, выходы каждой из которой подключены к нулевым входам триггеров одноименной со столбцом строки матричной модели сети, а первые входы — к выходам регистрирующих счетчиков, вторые входы схем сравнения подключены к выходу счетчика импульсов, вход которого подключен к выходу блока управления, первые входы элементов И подключены к выходу блока управления, вторые входы элементов И подключены к выходам элементов ИЛИ, входы которых подключены к выходам триггеров формирователей дуг одиоименного столбца матричной модели сети (1) .

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

Наиболее близким к изобретению является устройство для моделирования сетевых графов, содержащее блок управления, первый вход которого 45 соединен с выходом генератора тактовых импульсов, счетчик импульсов, триггеры формирователей дуг по числу строк и столбцов матричной модели сети, по числу столбцов матричной модели сети первые элементы ИЛИ, элементы И, регистрирующие счетчики, схемы сравнения, входы каждой из которых подключены к нулевым входам триггеров одноименной со столбцом строки матричной модели сети, а первые входы — к выходам регистрирукщих счетчиков, вторые входы схем .сравнения подключены к выходу счетчика импульсов, вход которого подключен к выходу блока управления, первые вхо- 60 ды элементов И подключены к выходу блока управления, вторые входы элементов И подключены к выходам соответствующих первых элементов ИЛИ, входы которых подключены к выходам 5 триггеров формирователей дуг одноименного столбца матричной модели сети, элемент НЕ, элемент И, выход которого через элемент HE подключен. к управляемому входу блока управления, по числу столбцов матричной модели сети вторые и третьи элементы ИЛИ, триггеры прямого и обратного отображения, управляющие триггеры, по числу строк и столбцов матричной модели сети первые и вторые элементы И, информационные входы каждого из которых подключены к входу соответствующего триггера формирователя дуг, входы каждого второго элемента ИЛИ подключены к выходам первых элементов И одноименного столбца матричной модели сети, а выходы — к входам соответствующих триггеров прямого отображения, выходы которых подключены к управляемыМ входам первых элементов И одноименной строки матричной модели сети, входы каждого третьего элемента ИЛИ подключены к выходам вторых элементов И одноименной строки матричной модели сети, а выходы — к входам соответствующих триггеров обратного

Отображения, выходы которых подключены к управляемым входам вторых элементов И одноименного столбца матричной модели сети, входы каждого управляющего триггера подключены к выходам соответствующей схемы сравнения, а выходы - к одноименным входам первого элемента И (2) .

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

Целью изобретения является повышение быстродействия.

Поставленная цель достигается тем, что в устройство для моделирования сетевых графов, содержащее матричную модель графа, 11 -й узел которой включает триггер, первый и второй элементы И, причем ныход тригге-, ра подключен к первым входам перного и второго элементов И, первую и вторую группы элементов ИЛИ, первую и вторую группы триггеров, элемент И, генератор. тактовых импульсов, счетчик, причем выход j --го ({=1, ...,п) триггера первой группы подключен ко вторым входам первых элементов И -й строки матричной модели графа, выход < -го триггера второй группы соединен со вторыми входами вторых элементов И s -го столбца матричной модели графа, выход первого

1075268

Определение вераин графа, обра зующих транзитивное замыкание, а также обратное транзитивное замыкание для всех вершин графа начинается после занесения исходной информации элемента И ij -го узла матричной модели графа подключен к соответствующему входу 1 -го элемента ИЛИ первой группы, выход второго элемента И ) -ro узла матричной модели графа

5 соединен с соответствукщим входом

1-го элемента ИЛИ второй группы, выход -го элемента ИЛИ первой группы подключен к единичному входу < -го триггера первой группы, выход (-го элемента ИЛИ второй группы соедине н 10

c åäèíè÷íûì входом 1-го триггера, второй группы введены дешифратор и элемент задержки, выход которого подключен к нулевым входам триггеров первой и второй групп, выход генера- (5 тора тактовых импульсов соединен с первым входом элемента И, второй вход которого является входом запуска устройства, выход элемента И подключен к входу элемента задержки и входу счетчика, выход которого соединен с входом дешифратора, выходы которого подключены соответственно к входам элементов ИЛИ первой и второй групп. 25

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

Устройство .содержит матричную модель 1 графа, триггеры 2 (Формирователей дуг), первые 3 и вторые 4 элементы И, по числу столбцов матричной модели графа первые 5(, ..., 5q и вторые 6», ..., 6 элементы ИЛИ, первые 7<, ..., 7 и вторые 8(, ..., 8„ триггеры, дешифратор 9, счетчик 10, элемент 11 задержки, элемент И 12, генератор 13 тактовых импульсов, вход 14 запуска, выходы 15», 15яю 161 ° - ° ю 16п и 17., Матричная модель 1 графа представляет собой матрицу пхп 40 где n — максимальное число вершин в графе, однородных ячеек в составе триггера 2, первого 3 и второго 4 элементов И.

Устройство для моделирования се- 45 тевых графов работает следукщим образом.

Первоначально в нулевое положение. устанавливаются все триггеры 7, 8 и счетчик 10. Информация о топологии 50 моделируемого графа заносится путем установки соответствующих триггеров 2 в единичное состояние. Соответствующий триггер 2, (1,j= 1, ...,n) формирователя дуги определяется

55 пересечением (-й строки ((— номер начальной вершины моделируемой ветви грифа) с 1 -м столбцом (1 — номер конечной вершины моделируемой ветви графа). на соответствукщие триггеры 2 и обнуления триггеров 7 и 8, а также счетчика 10. После подачи управляющего сигнала на вход 14 импульсы с генератора 13 начинают поступать через элемент И 12 на вход счетчика 10 и элемента 11 задержки. С выхода счетчика 10 код (первоначально 0...01) поступает на вход дешифратора 9, на выходе которого возбуждается только одна шина (вначале первая), после чего единичный сигнал через элементы ИЛИ 5 и 6 перебрасывает в единичное состояние соответствующие триггеры 7 и 8 (вначале триггеры 7(и 8() .

Единичный сигнал с выхода триггера 7((= 1,..., Л ) поступает на вторые входы элементов. И 3 s -й строки матричной модели, вторые входы которых подсоединены к выходу одноименного триггера 2, а выход — к одноименному входу элемента ИЛИ 5>, () = 1,..., я) единичным сигналом с выхода которого устанавливается в единичное состояние триггер 71, и т.д. Так определяются все вершины, образукщие транзитивное замыкание для -й вершины. Таким вершинам соответствует единичное состояние триггеров 7, и соответствукщий код снимается с выходов 15 устройства °

В этом коде единица в ) -м разряде соответствует номеру вершины, входящей в транзитивное замыкание для л-й вершины моделируемого графа.

Одновременно единичный сигнал с

% выхода триггера 8 ((=lp ° ° ° goal) по" ступает на вторые входы элементов И 4 -го столбца матричной модели, вторые входы которых подсоединены к выходу одноименного триггера 2, а выход — к одноименному входу элемента 6 1 (j= 1,...,п), единичным сигналом с выхода которого устанавливается в единичное состояние триггер 8), и т .д. Так определяются все вершины, образующие обратное транзитивное замыкание для (-й вер шины. Таким вершинам соответствует единичное состояние триггеров 8, а соответствующий код снимается с выходов 16 устройства.

Далее, после завершения всех переходных процессов по определению транзитивного и обратного транзитивного замыканий, единичный сигнал с выхода элемента 11 задержки перебррсывает все триггеры 7 и 8 в нулевое состояние.

На вход счетчика 10 поступает очередной импульс, и транзитивное и обратное транзитивное замыкания определяются для второй вершины моделируемого графа и так далее, до тех пор, пока на счетчике не зафик1075268

Составитель И.Дубинина

Редактор Н.Пушненкова ТехредМ.Гергель: КорректорГ.Решетник

» « I

Заказ 503/43 Тираж 699 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5 Филиал ППП Патент, г.ужгород, ул.Проектная, 4 сируется код числа П, после чего с приходом очередного импульса счетчик 10 переполняется, о чем свидетельствует единичный сигнал на Вы- ходе 17 устройства.

Таким образом, устройство обеспе- .чивает определение транэитивного и обратного транзитивного замыканий одновременно для всех вершин моделируемого графа.