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

пу триггеров 10,.,.,10 , группу элементов И 11 ,,..., 11 , группу триггеров 12 ,.,., 12, группу схем сравнения. 13 ,, .., 1 3, группу счет- чкков lAi,..., 1 4д,|, группу элементов ШШ 15, ... , 15{д, группу триггеров

1 ,

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

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

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

Устройство содержит матрицу 1 графа из N X N формирователей 2 дуг графа (i, j 1,25..,N), кажды из которых содержит триггер 3 и элементы И4, И5, группы элементов ИЛИ 6,,,.,,6 и 7 ,,. .,7 группу элементов И 8 ,.,,,8|, группу элементов ИЛИ 9, ,...,9|v|5 группу тригге . ров 10|5..,,10j, группу элементов И

11

12

N

jlliyj группу триггеров 12,,, группу схем сравнения 13, 5..., 13„.; руппу счетчиков 14, ,, .., 14 |, группу элементов ШШ 15 ,...-, 15f, группу триггеров Тб, , . , ., 16,, эле- мент ШШ 17, генератор 18 тактовых импульсов, элемент И 19, счетчик 20 дешифратор 21, элементы И 22 и 23, счетчик 24, вход 25 запуска, выход 26 определения ранга вершины графа и выход 27 наличия циклов устройства.

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

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

16,,.,, 16|, элемент ИЛИ 17,генератор тактовых импульсов 18, элемент И 19, счетчик 20, дешифратор 21,элементы И 22 и 23, счетчик 24, вход запуска 25 и выхода 26 и 27 устройства, 1 1-ш.

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

т у

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

ветствуюш.их начальным узлам модели

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

для которьк триггеры 3 этих строк находятся В нулевом состоянии. На информационных входах элементов И 1,1 этих строк - нулевой.потенциал, а в других строках - высокий.

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

последовательно, начиная с N-й вершины, после занесения исходной информации и подачи пускового сигнала на вход 25 устройства. При этом импульсы с выхода генератора 18 поступают

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

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

ШШ 15„, 9, И 8,.

3

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

kJ

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

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

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

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

Наличие циклов в графе определяется поочередно (начиная с N-й) для каждой вершины моделируемого графа. Например, для N-й вершины наличие цикла определяется следукщим образом Так как цикл в графе образуют вершины, в число которых входит и данная N-я вершина, то один или несколько триггеров 3 формирователей 2. находятся в единичном состоянии.Поэтому в данном случае на выходе элемента ИЛИ 7 появляется высокий потенциал, а так как на управляемом входе элемента И8| - высокий потенциал, то он далее через элемент ИЛИ 17 поступает на выход 27 устройства. Аналогично обнаруживаются циклы и дл других вершин моделируемого графа.

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

Далее начинается процесс определения порядковой функции моделируемого графа. Первый импульс с выхода элемента И 22 поступает на вход счетчика 24 и на информационные входы элементов И 11, При этом импульсы не проходят через элементы И 11 на входы регистрирующих счетчиков 14 тех строк, для которых все триггеры 3 находятся в нулевом состоянии.Далее содержимое счетчика 14,- поступает на первый вход схемы 13; сравнения а на вторые входы этих схем 13j сравнения поступает код с выхода счетчика 24. Синхронизация схем 13 сравнения, осуществляется тактовым сигналом с выхода генератора 18. При несовпадении показаний счетчиков 14 и 24 соответствующая схема 13 сравнения вырабатывает импульс, который сбрасывает в нулевое состояние триггеры 3 формирователей 2 дуг столбца равного номеру строки, в которой ие произошло сравнение« ОдиоЕременно сигнал несравнения с выхода схемы 13; поступает на вход, установки в три;ггера 12,-, с выхода которого единичный сигнал поступает на. односменный вход элемента И 23, выход 26 которого является выходом устройства. Сигнал на выходе 26 появляется при распределении всех вершин rpatjia по ярусам, т.е. в случае, когда все триггеры 12 находятся в единичном состоянии, а с ингер ного выхода элемента И23 низким потенциалом закрывается элемент И 22.

Число импульсов 5 заЛшксированное па c le r iJiKax .14, соответствуют значению порядковой функции ,ля соот- ветствующейгвершины графа (номер уровня в графе). Это значение всег- |да находится в пределах от нуля до No

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

Ф о р м у л

изобретения

40

каждого элемента И. Ш второй группы

Устройство для моделирования сете- подключен к второму входу одноименных графов 5 содержаш,ее матрицу из N X N формирователей дуг, генератор тактовых импyJтьcoв,, первый к второй .элементы И, первый и второй счетчики, дешифратор , эочемент ИЛИ, первую 1-1 вторую группы элементов ИЛИ,, первую и вторую группы трип еров,, первую .и вторую группы элементов М,груп- иу счетчиков, первый информационньй выход 1-го формирователя дуги каждого j-ro столбца матрицы подклгпче1г к i-му входу j-ro элемаита ШШ первой гру.ппы (i, j 1,2,.,,5,N), выход

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

45 выход каждого элемента ИЛИ четвертой группы подключен к второму входу одноименного элемента И второй группы, выход которого подключеп к счетному входу одноименного счетчикаяодо.го элемента Ш1Б. первой группы подключен к входу установки в 1 одноименного триггера первой группы,. входы установки в О триггеров перво.й и второй групп объедине.ны, второй информационньй вход i-го формирователя дуги строки матррщы подключен к i-му входу j-ro эламен.- та .Ш1И второй группы, выкод генератора тактовых импульсов .подк.лючек .к первы входам первого и в .горого

элементов И, выход первого sj.CMeH- та И подключен к счетному вхо/ ;,у первого счетчи са, выход которого подключен к входу дешифратора, ка.лодый выход группы N информационн х выходов которого подключен к первому входу одноименного элемента И первой группы, первые входы элементов И второй группы объединены, о т л и ч а ю

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

третья и четвертая группы элементов 1ШИ, третья группа триггеров., группа схем сравнения л третий элемент И, причем первый вход первого элемента И.является входом запуска устройства, второй вход первого элемента И подключен к (Н+1)-му информационному выходу дешифратора, (Н+2)-й информационный выход которого подключен к второму входу второго элемента И каждый --й выход группы N информационных выходов дешифратора подключен к .первому входу j-ro элемента ИЛИ третьей группы и к (N+1)-My ;входу j-ro элемента ИЛИ первой группы, третий инфор.ма}дионный выход i-i o формирователя дуги j-й строки матри- Ц.Ы нодключен к i-му входу j-ro элемента ИЛИ четвертой группы,выход

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

выход каждого элемента ИЛИ четвертой группы подключен к второму входу одноименного элемента И второй группы, выход которого подключеп к счетному входу одноименного счетчика группы, выход которого подключен к первому входу одноименной схемы сравнения группы, вторые входы всех схем сравнения группы объединены и подключены к выходу второго счетчика, выход второго .емента И подключен ко входу второго счетчика и к первым входам элементов И второй группы, выход генератора тактовых импульсов подключен ко входам син7 12771318

хронизации схем сравнения группы и ковой группы подключен к одноименному

входам установки в О триггероввходу элемента ИЛИ, выход которого

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

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

столбца матрицы, выход каждого триг-;определения ранга вершины графа, а

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

третьим информационным входам форми-Ш подключен к третьему входу второго

рователей дуг одноименной строки ма-элемента И. трицы, выход каждого элемента И пер

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