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

(50 4 6 06 Г 1 /2 ПИСАНИЕ ИЗОБРЕТЕНИЯ А ВТОРСКОМУ СВ ТЕЛ ЬСТ ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(5 б) Авторское свидетельство СССРВ 913389, кл. С 06 Р 15/20, 1982,Авторское свидетельство СССР9 1242982, кл. С 06 Р 15/20, 1984(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯСЕТЕВЫХ ГРАФОВ(57) Устройство дсетевых графов от вычислительной техники. Целью изобретения является повышение быстродей- ствия и расширение функциональных возможностей устройства за счет определения замкнутых контуров и петель н графе. Устройство содержит матрицу 1 графа из И х И формирователей 2; дуг графа (х 1 = 1,2, ,М ), каждый из которых содержит триггер 3, элемент И 4, элемент И 5; кроме того, устройство включает груп. пы элементов ИЛИ 6 ффбя 1 и 7 ф7 , группу элементов И 81, 8 группу элементов ИЛИ 9,9,груп1277131 пу триггеров элементов И 1 триггеров 12 ь сравнения. 13 чиков 14 ьИЛИ 15 уь,1 101ьфььаеь 15 гр10, группу ,11 , 1 руппуИ12 группу схем 3, группу счет- группу элементов уппу триггеров 16, 16 , элемент ИЛИ 17,генератор тактовых импульсов 18, элементИ 19, счетчик 20, дешифратор 21,эле"менты И 22 и 23, счетчик 24, входзапуска 25 и выходы 26 и 27 устройства, 1 ил,25 ЗО 35 40 45 1Изобретение относится к вычислительной технике и может быть исполь" зовано при исследовании параметров сетевых графов для определения порядковой функции, а также вершин графа, образующих транзитивное и обратное транзитивное замыкание, и наличие циклов в графе.Целью изобретения является повышение быстродействия и расширение функциональных возможностей устройства за счет определения замкнутых контуров и петель в графе.Структурная схема устройства для моделирования сетевых графов приведена на чертеже.Устройство содержит матрицу 1 графа из М х Ы формирователей 2, дуг графа (ь 1 = 1 ь 2 ь,ьИ)ь каждый из которых содержит триггер 3 и элементы И 4, И 5, группы элементовИЛИ 6 ьь 6 и 7 7 группуьФФьэлементов И 8 . 8 , группу эле 1ментов ИЛИ 9, ьь 9 ь группу триггеров 10 ,10группу элементов Ируппу три 1 геров 12 ,12 группу схем сравнения 1313.,группу счетчиков 14,14 ьгруппу элементов ИПИ 15,15, группу триггеров 16,16,элемент ИЛИ 17, генератор 18 тактовыхимпульсов, элемент И 19, счетчик 20,дешифратор 21, элементы И 22 и 23,счетчик 24, вход 25 запуска, выход 26 определения ранга вершиныграфа и выход 2 наличия циклов устройства.Устройство для моделирования се-,тевых графов работает следующим образом.Первоначально устанавливаются внулевое состояние все триггеры 10,12, 16, 3, кроме того, счетчики 14и 24 находятся в нулевом состоячии.На счетчике 20 установлен крд числа 2И+1 ь где И - число вершин моделируемого графа. Информация о топологии моделируемого графа заносится путем установки соответ твующих триггеров 3 в единичное состояние. Соответствующий триггер 3 Формирователя 2 дуги определяется пересечением столбца с номером, равным номеру начального узла моделируемой ветви, и строки с номером, равным номеру ее конечного узла. После занесения исходной информации на выходах элементов ИЛИ 7, объединяющих выходы триггеров 3формирователей дуг в строках, соответствуюших начальным узлам моделируемого графа, присутствуют низкиепотенциалы Это справедливо толькодля однонаправленных графов без циклов и петель для начальных верцинь для которых триггеры 3 этих строк находятся в нулевом состоянии, На информационных входах элементов И 11 этих строк - нулевой потенциал, а в других строках - высокий.Определение вершин графа, образующих транзитивное замыкание, обратное транзитивпое замыкание для верцины графа, а также наличие циклов и петель для нее осуществляется последовательно, начиная с И-й вершины, после занесения исходной информации и подачи пускового сигнала на вход 25 устройства. При этом импульсы с выхода генератора 18 поступают на информационный вход элемента И 19. Так как на его втором управляющем входе находится вшсокий потенциал с выхода дешифратора 21 (сигнал ненулевого состояния счетчика 20),то импульс с выхода элемента И 19 поступает на вход счетчика 20, а на И-м выходе дешифратора 21 появляется высокчй потенциал, который поступает на соответствующие входы элементов ИЛИ 15, 9, И 85 10 15 20 30 35 40 45 50 55 Высоким потенциалом с выхода элемента ИЛИ 9 устанавливается в единичное состояние триггер 10 айвысоким потенциалом с выхода элемента ИЛИ 15 д устанавливается в единичное состояние триггер 16, Далее высокий потенциал с выхода триггера 10 поступает на управляемые входы элементов И 4 одноименного столбца матричной модели графа, после чего при наличии дуги из Б-й вершины графа в 1-ю высокий потенциал с выхода элемента ИЛИ 7 . поступает через элемент ИЛИ 9 на вход тригге 4ра 10. Затем высоким потенциалом перебрасывается в единичное состояние триггер 10 , с выхода которого высокийпотенциал поступает на управляемые входы элементов И 4 3-й строки матрицы 1 до тех пор, пока существует путь из 1-й вершины в очередную и т.д, Таким образом, определяются все вершины, образующие транзитивное замыкание для М-й вершины графа. Таким вершинам соответ ствует единичное состояние триггеров 10.Одновременно с выхода триггера 16 установленного в " 1" высоким потенциалом с выхода элемента ИЛИ 15 единичный сигнал поступает на управляемые входы элементов И 5 одноименного столбца матричной модели графа, после чего при наличии дуги в И-ю вершину графа из К-й (К=1, ,М) высокий потенциал с выхода элемента И 5, через элемент ИЛИ 15 перебрасывает в единичное состояние триггер 16 . С выхода триггера 16 у высокий потенциал поступает на вторые входы элементов И 5 К-й строки матрицы 1 до тех пор, пока имеется дуга из предшествующей вершины в данную, Так определяются все вершины, образующие обратное транзитивное замыкание для И-й вершины. Таким вершинам соответствует единичное состояние триггеров 16.Через время, достаточное для за; вершения всех переходных процессов в матричной модели сети, на выходе генератора 18 появляется очередной импульс, который обеспечивает сброс триггеров 10 и 16 в исходное нулевое состояние. Кроме того, этот импульс поступает также на вычитающий счетчик 20 через открытый элемент И 19, в результате чего на счетчике 20 фиксируется код числа И.Процесс определения вершин, образующих транзитивное и обратное транзитивное замыкания, происходит аналогичным образом; возбуждается (И)-я выходная шина дешифратора 2 1, после чего устанавливаются в единичное состояние триггеры 10 ,и 16 и т,д.Наличие циклов в графе определяется поочередно (начиная с И-й) для каждой вершины моделируемого графа.Например, для И-й вершины наличие цикла определяется следующим образом.Так как цикл в графе образуют вершины, в число которых входит и данная И-я вершина, то один или несколько триггеров 3 формирователей 2 находятся в единичном состоянии,Поэтому в данном случае на выходе элемента ИЛИ 7 появляется высокий пойтенциал, а так как на управляемом входе элемента И 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 дуг столбца,равного номеру строки, в которой пеПРОИЗОШЛО СРаВНЕНИЕ, ОДЕот)РЕ.СОсигнал несравнечия с выхода схемы13; ПОСГунаЕТ Н 11 ВХОтт, уСТПНОВКИ В5триггера 12 с выхода которогоедпннчный си.гнал поступает на одноимеп 1 ый вход элемента И 23, прямойвыход 2 б которого является выходомустройства. Сигнал на выходе 26 появляется при распределении всехверяни графа по ярусам, т.е, и случае когда все триг.геры 12 находятСЯ ) ЕДИЕ 1 ЧЕЕОМ СОС ГОЯНИИс 1 С 1 НВ ЕРСного выхода элемента И 23 низким потенциалом закрывается элемент И 22.Число импузьсов, зафиксирозанноеНа С-уотт)Как 14, СООТВЕтС)ву)От ЗнаЧЕЕЕПО ПОРЯДКОВОЙ фтНКЦИИЛ 5 СООТветствующей, вершины графа, номер 20уровня в грайе), Зто значение всег,да находится в пределах от нулядо Н.Таки 1 образом, предлагаемое устройство обсспечизает распределение 25вершин графа по рангам, опреттелениеналичия цтиклов в графе а такжЕ определение Верптин, образу)ощих транзитивное и обратное транзитивное замыканп для побой вер 05 нь моЕтезнеруемо)о Зрт раф;т,ф О р м у л а и 3 О б р е т Р ет и яУстройство для моделирования сете- ., вых графов, содержащее матрицу из11 х .Л формирователей дуг, генератор тактоезых импульсов, первый и Второй эзОтенты И Уервый и второй счетчики, дешифратор, элемент ИЛИ, первую и ВУорую Еруппь э;,ементов ИЛИ, первтт 0 и БТО ру 10 группы ттт 1 ГВР 110 В уРрВук и вторую группы элеменов И,групУтт Счетчиков петвй 111 фо 1 ацтяоЕЕ.1 й узыход з-го формироваф;еля дуги каждого з-го стот 1 бца матриць подключенк з.-му входу з-го эзземеыта ИЛИ пер- ВОИ ГруППЫ (З З - 1 тювт 1 Я) т ЗЫХОд каждого элемента ИЛИ первое групгзя подключен к Входу установки в 1одноименного триггера первой группы, входы установки в "О" триггеровпервой и второй групп Объединены,второй информационный ход з.-)о формирователя дуги з-и строки матрицы ЕЗОУЗКЛОЧЕН К З. "МУ ВХОДУ ЗГО Э,тЕМЕЕЕ та ИЛИ. второй группы, выход генераТОРа ТНКТОВЫХ ИМПУЛЬСОВ 1 ОДКГПОО 5 тПРРЕЗЫМ ВХ(ДЯМ ЕЗЕРВОГО и тТОРОЗ 0 6элементов И, выход первого э.с:ента И подключен к сЕетному вход, первого счетчика, выход которого .садкпо ЧЕН К ВХОДУ тЕШЕ 4 Р)ЗТОРа, КаЕГДЫЙ ВЫ- ход группы Г) информац 1 онных выходов которого подключен к первому входу одноименного элемегга И первой группы, первые входы элементов И гторой группы объединены, о т л и ч а ющ е е с я тем, что, с целью повышения быстродействия и расширения функциональных возможностей за счет определения замкнугых контуров и петель в графах, в него введены третья и четвертая группы элементов ттЛИ. третья группа триггеровгруппа схем сравнения и третий элемент И причем первый Вход первого элемента И являе Гся входом запуска устройства, второй вход первого элемента И подключен к (1 т 1+1)-му информационному выходу депифратора, (11+2)-Й информационный выход которого подключен к второму входу второго элемента И, каждый зи выход группы Б информационных выходов дешифратора подключен к тервом входу з-го элелента ИЛИ третьей группы и к (Гт+1)-му ,входу з-го .лемента ИЛИ первой групь, третий информационный узыход з.-го соормирователя дуги з-й строки матриЕто ПОДКтиОЧЕН К З.-МУ ВХОДУ З-ГО ЗЛЕ- мента ИЛИ четвертой гру)тпы,выход каждого элемента И.И второй группы подключен к втором.1 входу одноименного элемента ИЛИ Гретьей группы и к второму входу одноименного элемента И первой группы, выход. каждого элемента ИЛИ третьей группы подключен к Входу установки В "1" одноименного триггера торой группы,выход которого подклточен к первым информационным входам формирователей дуг одноименного сполбца матрицы. выход каждого элемента ИЛИ етвертой группы подключен к второму входу одноименного элемента И второй группы, выход которого подключен к счетному входу одноименного счетчика группы, выход которого подключен к первому входу одноименной схемы СРаВНЕНИЯ ГРУППЫ, ттОРЫЕ ВХОДЫ ВСЕХ схем сравнения группы объединены и подключены к выходтт второго счетчика, выход второго элемента И подключен ко вхоцу второго счетчика и к первым входам элтментов И второй группы, выход генее атора тактовых импульсов подключен ко входам син1277131 Составитель Т, СапуноваРедактор И. Рыбченко Техред М.Ходанич Корректор В, Бутяга Заказ 6669/44 Тираж 671 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб д. 4/5Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 хронизации схем сравнения группы и ковходам установки в "О" триггеровпервой и второй групп, выход каждойсхемы сравнения группы подключен ковходу одноименного триггера группыи ко вторым информационным входамформирователей дуг одноименногостолбца матрицы, выход каждого триг,гера первой группы подключен ктретьим информационным входам формирователей дуг одноименной строки матрицы, выход каждого элемента И первой группы подключен к одноименномувходу элемента ИЛИ, выход которогоявляется выходом наличия циклов устройства, выход каждого триггера 5 третьей группы подключен к одноименному входу третьего элемента И, прямой выход которого является выходом,определения ранга вершины графа, аинверсный выход третьего элемента И 10 подключен к третьему входу второгоэлемента И.