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

 

Устройство для моделирования сетевых графов относится к области вычислительной техники. Целью изобретения является повышение быстродействия и расширение функциональных возможностей устройства за счет определения замкнутых контуров и петель в графе. Устройство содержит матрицу 1 графа из N к N формирователей 2-- дуг графа (i, j 1,2, .., ,N ), каждьй из которых содержит триггер 3, элемент И 4, элемент И 5; кроме того, устройство включает группы элементов ИЛИ 6 ,..., 6 , и 7,. ,..., 7| , группу элементов И 8, ,..., 8, группу элементов 1-ШИ 9.i,..., 9ц,груп§ (Л

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

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

РЕСПУБЛИК цю <в (504G06 F 1 /20 j Д

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (Z1) 3863978/24-24 (22) 25.02.85 (46) 15.12 .86. Бюл. Ф 46 (72) В.А.Титов, В.Л.Гайдуков, А.Г.Крупнов и И.Е.Харитонов (53) 681.333(088,8) (56) Авторское свидетельство СССР

N 913389, кл. G Об F 15/20, 1982.

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

У 1242982, кл. G 06 F 15/20, 1984. (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

СЕТЕВЫХ ГРАФОВ (57) Устройство для моделирования сетевых графов относится к области вычислительной техники. Целью изобретения является повышение быстродей- ствия и расширение функциональных возможностей устройства sa счет определения замкнутых контуров и петель н графе. Устройство содержит матрицу 1 графа из И х И формирователей 2;„ дуг графа (i, j = 1,2, ...,N ), каждый из которых содержит триггер 3, элемент И 4, элемент И 5; кроме того, устройство включает группы элементов ИЛИ 6,,...,6, и 7,,..., 7, группу элементов И 8 ... °, 8,„, группу элементов ИЛИ 9,1,...,9„,груп1277131 пу триггеров элементов И 1 триггеров 12 сравнения. l3„ чиков 14 ь ° ..

ИЛИ 15уь...ь1

1ч ° ° ° ь ° ° ь ьа ° еь1

14

5 ь гр,, 10, группу ,11, группу

И ь i2,, группу схем

3„, группу счетгруппу элементов уппу триггеров

16,,..., 16, элемент ИЛИ 17,генератор тактовых импульсов 18, элемент

И 19, счетчик 20, дешифратор 21,эле" менты И 22 и 23, счетчик 24, вход запуска 25 и выходы 26 и 27 устройства, 1 ил, 25

ЗО

1

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

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

Структурная схема устройства для моделирования сетевых графов приведена на чертеже.

Устройство содержит матрицу 1 графа из N x N формирователей 2;„ дуг графа (i j = 1,2...,,N) каждый из которых содержит триггер 3 и элементы И4, И5, группы элементов ИЛИ 6,...,6 ц и 7,...,7 группу

6 Ф ° элементов И 8,...,8, группу эле-.

1ь ° ° ° ь ментов ИЛИ 9, ь...,9, группу тригге, ров 10,...„10 „ группу элементов И

111,,11м, группу тр геров 12!

12„,, группу схем сравнения 13,,..., 13„.,группу счетчиков 14 14,, группу элементов ИПИ 15...,,,15,„, группу триггеров 16,,...,16„,çëåмент ИЛИ 17, генератор 18 тактовых импульсов, элемент И 19, счетчик 20, дешифратор 21, элементы И 22 и 23, счетчик 24, вход 25 запуска, выход 26 определения ранга вершины графа и выход 27 наличия циклов устройства.

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

Первоначально устанавливаются в нулевое состояние все триггеры 10, 12, 16, 3, кроме того, счетчики 14 и 24 находятся в нулевом состоячии.

На счетчике 20 установлен крд числа

N+1, где N — число вершин моделируемого графа. Информация о топологии моделируемого графа заносится путем установки соответ твующих триггеров

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

7, объединяющих выходы триггеров 3 формирователей дуг в строках, соответствуюших начальным узлам моделируемого графа, присутствуют низкие потенциалы„ Это справедливо только для однонаправленных графов без циклов и петель для начальных вершин, для которых триггеры 3 этих строк находятся в нулевом состоянии. EIa информационных входах элементов И !1 этих строк — нулевой потенциал, а в других строках — высокий.

Определение вершин графа, образующих транзитивное замыкание, QG ратное транзитивпое замыкание для вершины графа, а также наличие циклов и петель для нее осуществляется последовательно, начиная с N é вер шины, после занесения исходной информации и подачи пускового сигнала на вход 25 устройства. При этом импульсы с выхода генератора 18 поступают на информационный вход элемента И 19.

Так как на его втором управляющем входе находится вшсокий потенциал с выхода дешифратора 21 (сигнал ненулевого состояния счетчика 20),то импульс с выхода элемента И 19 поступает на вход счет-..ика 20, а на И-м выходе дешифратора 21 появляется высокчй потенциал, который поступает на соответствующие входы элементов

ИЛИ 15, 9,„ь И 8,„.

1277131

10

25

3D

Высоким потенциалом с выхода элемента ИЛИ 9 устанавливается в единичное состояние триггер 10 а и высоким потенциалом с выхода элемента HJIR 15 д устанавливается в единичное состояние триггер 16, Далее высокий потенциал с выхода триггера 10 поступает на управляемые. входы элементов И 4 одноименного столбца матричной модели графа, после чего при наличии дуги из N-й вершины графа в 1-ю высокий потенциал с выхода элемента ИЛИ 7 . поступает

J через элемент ИЛИ 9 на вход триггеJ ра 10„. Затем высоким потенциалом перебрасывается в единичное состояние триггер 10 „, с выхода которого высокий потенциал поступает на управляемые входы элементов H4 j и строки матрицы 1 до тех пор, пока существует путь из j-й вершины в очередную и т.д, Таким образом, определяются все вершины, образующие транзитивное замыкание для N-й вершины графа. Таким вершинам соответствует единичное состояние триггеров 10.

Одновременно с выхода триггера

16,„, установленного в " 1" высоким потенциалом с выхода элемента ИЛИ

15„,, единичный сигнал поступает на управляемые входы элементов И 5 одноименного столбца матричной модели графа, после чего при наличии дуги в N-ю вершину графа из К-й (К=1, ...,N) высокий потенциал с выхода элемента И 5,„ через элемент ИЛИ

15 перебрасывает в единичное состоя" У ние триггер 16 . С выхода триггера

1бу высокий потенциал поступает на вторые входы элементов И 5 К-й строки матрицы 1 до тех пор, пока имеется дуга из предшествующей вершины в данную. Так определяются все вершины, образующие обратное транзитивное замыкание для N-й вершины. Таким вершинам соответствует единичное состояние триггеров 1 б.

Через время, достаточное для за.— вершения всех переходных процессов в матричной модели сети, на выходе генератора 18 появляется очередной импульс, который обеспечивает сброс триггеров 10 и 16 в исходное нулевое состояние. Кроме того, этот импульс поступает также на вычитающий счетчик 20 через открытый элемент

И 19, в результате чего на счетчике 20 фиксируется код числа N-1.Пропесс определения вершин, образующих транзитивное и обратное транзитивное замыкания, происходит аналогичным образом: возбуждается (N-1)-я выходная шина дешифратора 2 1, после чего устанавливаются в единичное состояние триггеры 10,и 16,,и т,д.

Наличие циклов в графе определяется поочередно (начиная с N-й) для каждой вершины моделируемого графа.

Например, для N-й вершины наличие цикла определяется следующим образом.

Так как цикл в графе образуют вершины, в число которых входит и данная

N-я вершина, то один или несколько триггеров 3 формирователей 2„ находятся в единичном состоянии.Поэтому в данном случае на выходе элемента ИЛИ 7 появляется высокий поN тенциал, а так как на управляемом входе элемента И8 — высокий потенциал, то он далее через элемент ИЛИ

17 поступает на выход 27 устройства.

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

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

Далее начинается процесс определения порядковой функции моделируемого графа. Первый импульс с выхода элемента И 22 поступает на вход счетчика 24 и на информационные входы элементов И 11. При этом импульсы не проходят через элементы И 11 на входы регистрирующих счетчиков 14 тех строк, для которых все триггеры

3 находятся в нулевом состоянии.Далее содержимое счетчика 14; поступает на первый вход схемы 13; сравнения, а на вторые входы этих схем 13; сравнения поступает код с выхода счетчика 24. Синхронизация схем 13 сравнения. осуществляется тактовым сигналом с выхода генератора 18. При несовпадении показаний счетчиков 14 и

24 соответствующая схема 13 сравнения вырабатывает импульс, который сбрасывает в нулевое состояние триг127713 геры 3 формирователей 2 дуг столбца, равного номеру строки, В которой пе ! lP 0119 0tlU1 0 С P BB11011H B . <3Д110< В II Q 1 1< i <110 сигнал несравнечия с выхода схемы

13; пос<у13ает на вход установки 13

" l" триггера 12;, с выхода которого единичный си.гнал поступает на одноимеп11ый вход элемента И 23, прямой выход 2б которого является выходом устройства. Сигнал н<1 13ыходе 26 «!о- 10 является при распределении Всех

ВЕРШИН ГРафа По ЯРУСаМ, т.Е, <З СПУчае когда все триггеры 12 находятСЯ 13 ЕДИНИЧ!<ОМ <..ОС СОЯ IIIII а С IIHP PPC ного выхода элемента И23 низким Io 15 тенциалом закрывается элемент И 22. тзт<С110 ИМПУЛЬСОВ, ЗафИКСИРОВаННOe па с-l<<тч зкау; 1

Таки11 образом, предлагаемое устройство обсспечитзает распределение 25

ВЕРШИН ГРафа ПО РаНГаМ, ОПРЕттЕЛЕНИЕ наличия цтиклов в графе,, а такжЕ определение Вершин, образутощих транзитивное и обратное транзит IBE

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

И х .Л формирователей дуг, генератор такто1зых импульсов, первый и 13торой элементы И„ первый «1 второй. счетчики, дешифратор, элемент ИЛИ, первую и 13Top÷î группы э;тементов ИЛИ., перВую и Вторую 1чруппы триггеров,, nepI3yIo и Вторую группы элементов И,группу счетчиков, первый информац .1он1ый

13ыход 3-го формироваl еля дуги каждого j-го столбца мат1рицьт подключен к 3-му входу 3-го элемента ИЛИ пер-.

ВОИ I pyIIIIbl (1 j — 1 121 ф, «

« 11 подключен к 33хОду уста.новк11 13 1 5О одноименного триггера первой группы, входы установки в "О" триггера:н первой и второй групп объединены, Второй информационный 13ход:ь--т.о формирователя дуги j-и строки матрицы

ПОЦКЛ1ОЧЕН К 1. "МУ ВХОДУ ) ГО Э 1ЕМЕН та ИЛИ. второй группы, Вы::Io;.1 генераТОРа ТНКТОВЫХ ИМПУЛЬСОВ 110ÄI Л«3<: РЕ<

t» ПР13Гзым Входам первОГО и 1?Тор03 О

1 6 элементов И, выход первого э3:":1ента И подключен к с 1етному Вход, первого счетчика, выход которого т-одкзпо. чен квходу,дешифратора, ка31тдьlH Bbl ход группы 1< информационных выходов которого подключен к первому входу одноименного элеме-IT

IJIH, третья группа триггеров„ группа схем сравнения из третий элемент

И, причем первый Вход первого элемента И являе гся Входом запуска устройства, второй вх<зд первого элемента И подключен к (N+1)-му информационному выходу дешифратора, (N+2)-й информационный выход которого подключен к второму входу второго элемента И, каждый j--и выход группы N информационных выходов дешифратора подключен к первом» Входу j -го элемента ИЛИ третьей группы и к (<1+1)-му ,Входу j-гO >лемента ИЛИ первой группы, третий информационный 1зыхоц 1 -го формирователя дуги 3-и строки матрицы подклточен к 3.-м.l Входу j ã0 элемента ИЛИ четвертой гру пы,выход каждого элемента И.И второй группы подключен к втором.» входу одноименного элемента ИЛИ гретьей группы и к второму Входу одно"зменного элемента И первой группы, выход. каждого элемента HJIH третьей группы подключен к ВХОДУ »стс1н013ки B 1 ОДНО ит1енного триггера 13торой группы, выход которого подклточен к пер13ым информационным Входам формирователей дуг одноименного с".Oëáöà матрицы.

Выход каждого элемента ИЛИ етверТой ГРУППЫ ПОДКЛ1ОЧЕН К I3TOPONjj ВХОду одноименного элемента И второй группы, выход которого подключен к счетному входу одноименного счетчика группы, выход которого подключен к первому входу одноименной схемы

СРаВНЕНИЯ ГРУППЫ, тттОРЫЕ ВХОДЫ ВСЕХ схем сравнения группы объединены и подключены к Выходу Второго счетчика, выход второго элемента И подключен ко вхоцу второго счетчика и к первым входам элементов И второй группы, выход генератора тактовых импульсов подключен ко входам син1277131

Составитель E. Сапунова

Редактор И. Рыбченко Техред N.Коданич Корректор В. Бутяга

Заказ 6669/44 Тираж 671 Подписное

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

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4 хронизации схем сравнения группы и ко входам установки в "0" триггеров первой и второй групп, выход каждой схемы сравнения группы подключен ко входу одноименного триггера группы и ко вторым информационным входам формирователей дуг одноименного столбца матрицы, выход каждого триг;гера первой группы подключен к третьим информационным входам формирователей дуг одноименной строки маJ трицы, выход каждого элемента И первой группы подключен к одноименному входу элемента ИЛИ, выход которого является выходом наличия циклов устройства, выход каждого триггера

5 третьей группы подключен к одноименному входу третьего элемента И, прямой выход которого является выходом ,определения ранга вершины графа, а инверсный выход третьего элемента И

10 подключен к третьему входу второго элемента И.