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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК бИ 4 ОПИСАНИ АВТОРСКОМУ БРЕТЕН ЕЛЬСТ(54) ГРАФ (57) Е ЛИРО ВАН ИЯ брете ласт е относится ктехники, можеи исследовании вычислительноиспользовано сетевых яет определи к вершинам м в и позвол граф воэм делируестве для жные путиграфа. Наирования чной моде ичие в устро рафов блока и графа позви устройства амяти иляетярусную ть в памя хр ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ структуру моделируемого графа, производить формирование путей к какой-либо вершине этого графа путем дополнения всех путей к предшествующимвершинам номером данной вершины, атакже объединить все дополненныепути и занести их в блоки памяти соответствующих блоков определения путей устройства, что позволяет повысить качество и полноту исследованиясетевых графов, используемых в качестве математических средств описаниясложных объектов и процессов, Приприменении сетевых графов для обобщенного описания процесса функционирования программных комплексов внедрение сизобретения позволит определить всевозможные варианты последовательноговыполнения элементов программногокомплекса и значительно повысить ка- Счество его испытаний, 1 з,п, ф-лы,2 иле1322306 10 15 20 Изобретецие относится к вычислительной техгике и может быть использовано при исследовании сетевых граФов для определения всех возможныхпутей к его вершинам.Целью изобретения является расширение класса решаемых задач эа счетопределения всех возможных путей квершинам моделируемого граф.На фиг. 1 приведена Фуцкццоняц,няясхема устройства, на Фиг, 2 - Функциональная схема блока определенияпутей,Устройство содержит матричную модель 1 графа, в узлах которой расположены триггеры 2, элементы И 3 ик:почи 4, блок 5 памяти, первый и второй элементы ИЛИ 6 и 7, дешифраторы8 и 9, коммутатор 10, группу коммутаторов 11, группу блоков 12 определения путей, генератор 13 тактовыхимпульсов, вход 14 пуска устройства,информационный вход 15 устроцстна цгруппу ключей 16.В состав каждого блока 12 входятпервый, второй и третий коммутаторы17-19, элемент НГ 20, блок 21 памяти,блок 22 сравнения кодов, с первогоцо четвертыи элементы ИХИ 23-26, блок27 логического сложения, элементы28-30 задержки, ключи 31-33, счетчик34 адреса чтения, регистры 35-37,счетчик 38 адреса зпцсьт, третийсчетчик 39, тактовый вход 40 блокаопределеция путей, нхоп 41 признакачтеция блока 12, вход 42 адреса чтеши блок 12, информационный вьгход43 блока 12, выход 44 признак окончания работы блока 12, выход 45 адреса чтения блока 12, выход 46 признакачтения блока 12, инФормационный вход47 блока 12, вход 48 признака наличиядуги блока 12, вьгход 49 признака выбора очередного узла блок 12, вьгход50 признака пуска блока 12,Устройство работает следующимобразом,Перед запуском устройства все коммутаторы всех блоков 12 устяцявпиваются в состояние, прц котором первыеинФормационные входы этих комггутяторон соединены с их первыми вьгходами.Счетчики 38 и 39 устанавливаются ннулевое состояние.Ключи 32 всех блоков 12 устанавливаются в состояние, при которомвыход счетчик 38 адреса записи оказывается подключенным к входу регист 25 30 35 40 45 50 55 ра 36, т,е. в открытое состояние. Врегистры 37 всех блоков 12 заносятсядвоичные коды, в которьгх в единичномсостоянии находится только разряд сномером, равным номеру соответствующей блоку 12 вершины (номеру столбццматричной модели 1 графа, коммутатор11 которого управляется блоком 12через выход 49). Содержимое блоков21 памяти всех блоков 12 обнуляется,а в блок 5 памяти по входу 15 устройства записываются двоичные кодыномеров нершин моделируемого графа.При этом первым записывается код номера начальной вершины, после чегов произвольном порядке записываютсякоды номеров вершин, составляющихпервый ярус графа, затем аналогичнымобрзом записываются коды номеровцерпцгц, составляющих второй, третийи т.д. ярусы. После записи всех ко,цов номеров вершин в блок 5 памяти записывается нулевой код, являющийся признаком окончания информации о верпцгцах моделируемого графа.Пьрвопачально коммутаторы 11 матричной модели 1 устанавливаются в состояние, при котором (М+1)-я груп" пя связей подключается к первой. Информация о топологии моделируемого графа заносится путем установки в единичное состояние (Р, К)-й триггеров 2, расположенных на перенесении К-й строки (К - номер начальной нершицы моделируемой ветви графя) с Р-м столбцом (Р - номер конечной вершины моделируемой ветви графа),3 пуск устройства осуществляется подачей специального сигнала на вход 14. По этому сигналу осуществляется запуск генератора 13, коммутатор 10 переводится в состояние, при котором выход блока 5 памяти оказывается подкгпоченным к информационному входу дешифратор 9, По этому же сигналу производится пересылка первого кода номера вершины моделируемого графа (кода номера начальной вершины) в дешифратор 9. На выходе дешифратора 9, соответствующем поступившему коду, Формируется сигнал запуска в первом режиме блока 12,совпадающего по номеру с начальной вершиной моделируемого графа, являющийся в то же время сигналом перевода коммутатора 10 н единичное состояние, счетчик 38 адреса записи переводит коммутатор 18 в состояние, при котором к второмугруппы, т.е. случаю рассмотрения К-йвершины в качестве предшественникадля вершины, соответствующей активному блоку 12.Рассмотрим порядок спределения путей для случая, когда активный блок12 имеет номер Р,В каждом такте блок 12 может работать либо во втором, либо в третьем режиме. Второй режим соответствует отсутствюо дуги, ведущей от вершины с номером К к вершине с номеромР. В этом случае после подключения вР-м коммутаторе 11 к связям (М+1)-йгрупп 1 я связей К-й группы на входе 48активного блока отсутствует единичныйсигнал, что обеспечивает открываниеключа 33 и прохождение очередноготактового импульса с первого .информационного выхода коммутатора 17 напервый вход элемента ИЛИ 24. На выходе этого элемента формируется сигнал,поступающий на выход 49 блока 12 каксигнал переключения Р-го коммутатора 11 на (К+1)-ю группу связей, атакже увеличивающий на единицу содержимое счетчика 39 и устанавливающийкоммутатор 17 в исходное состояние.Третий режим соответствует наличию в графе дуги, ведущей от вершиныс номером К к вершине с номерам Р. Вэтом случае на входе 48 Р-га блока12 присутствует единичный сигнал,который обеспечивает закрытие ключа33. Очередной тактовый импульс, поступивший по входу 40, после прохождения через коммутатор 17 производитустановку в нулевое состояние счетчика 34 и подключение с помощью коммутатора 19 входа 47 к входу регистра 35. Этот же импульс поступает через элемент ИЛИ 23, выход 46 узла,нулевую и К-ю группы связей Р-гокоммутатора 11, К-й ключ 4 Р-гостолбца модели 1 и вход 41 К-го блока 12 в качестве импульса чтения навход признака чтения блока 21 памятиК-го блока 12. Адрес чтения (в данном случае нулевой) в блок 21 памятиК-го блока 12 поступает из счетчика34 адреса чтечия активнага блока 12через выход 45 этого блока, (М+1)-юи К-ю группы связей Р-го коммутатора11, К-й ключ 4 Р-го столбца модели 1и вход 41 К-го блока 12, По импульсучтения из нулевой ячейки блока 21К-го блока 12 считывается кад количества путей от начальной вершины к 3 1322306 4входу блока 21 памяти подключаетсявыход регистра 37. Этот же сигналявляется сигналом записи, которыйпосле прохождения через элементИЛИ 25 поступает на вход признака за 5писи блока 21 памяти и обеспечиваетзанесение в этот блок по адресу, равному 1, двоичного кода из регистра37. Одновременно адрес записи, равный 1, записывается в регистр 36, К 10этому моменту времени поступившийпо входу 50 блока 12 и задержанный вэлементе 28 сигнал появляется навыходе элемента ИЛИ 26. Он переводиткоммутатор 18 в состояние, при котором к информационному входу записиблока 21 памяти подключается выходрегистра 36, содержащего конечныйадрес записи. Этот же сигнал поступает на выход 44 блока 12, одновре рменно закрывает ключ 32, предотвращая тем самым изменение содержимогорегистра 36, устанавливает счетчик38 адреса записи в нулевое состояние.Рассматриваемый сигнал обеспечивает 25запись в блок 21 памяти по адресу,равному О, значения конечного адресазаписи кодов в этот блок (двоичногозначения количества путей к соответствующей блоку 12 вершине) . 30Сигнал с выхода 44 запущенного впервом режиме блока 12 после прохождения через элемент ИЛИ 6 обеспечи- евает передачу в дешифратор 8 каданомера первой вершины первого яруса 35(ярусы нумеруются начиная с 0) изблока 5 памяти. Дешифратор 8 преобразует этот код в сигнал на соответствующем выходе, Этот сигнал обеспечивает прохождение сигналов от триггеров 2 через элементы И 3 на управляющие входы ключей 4 для всех узловсоответствующего столбца матричноймодели 1 графа, а также поступлениена вход 40 соответствующего блока 12 45тактовых импульсов от генератора 13Те ключи 4 столбца, на которые поступили сигналы от триггеров 2, устанавливаются в открытое состояние. Сэтого момента блок 12, соответствующий по номеру выхода дешифратора 8(активный блок 12), начинает циклформирования кодов путей к вершине,код номера которой поступил на дешифратор 8, Этот цикл состоит из М такгов, Такт с номером К соответствуетслучаю подключения к связям (М+1)группы коммутатора 11 связей К-йК-й. Этот код передаггся ц ре. истр 35 активного блока 12 через выход 43 К-го узла 12, К-й ключ 4 Р-гостолбца матричной модели 1, К-и и нулевую группы связей Р-го коммутатора 11, вход 47 Р-га блока 12 и коммутатор 19 этого блока, Указанный тактовый импульс кроме того устанавливает коммутатор 17 в состояние, прц котором его тптформаццаццый вход подклю О чен к второму информдццаццому выходу,Следующий тактовый импульс после прохождения через коммутатор 17 открывает ключ 32, обеспечивая тем самым возможность передачи текущего адреса 15 записи из счетчика 38 в регистр 36, подключает с помощью коммутлтора 19 вход 47 Р-га блока 21 к входу блока 27, подключает с помощью коммутатора 18 информационный вход злппсц злака 20 21 памяти к выходу блока 27, л тлкже переводит коммутатор 17 в са; таяние, при котором обеспечивается прохождение последующих тактовых импульсов через третий информационный выход 25 этого коммутатора.Очередной тактовый импульс с входа 40 Г-го блока 12 увеличивает ца единицу содержимое счетчиков 34 и 38, 11 авый адрес чтения цз счетчика 34 30 поступает на вход блакл 22 сравнения кодов, где он срдвццвл;тся с количеством путей, накопленных в блоке 21 памяти К-го блока 12. Если этот адрес чтения превышает количество путей, ведущих к предшествующей К-и вершине, то цд выходе блока 22 отсутствует сцгцап, К этому моменту импульс с третьего информационного выхода коммутатора 17 после задержки 40 в элеме те 29 поступает через открытый ключ 31 и элемент ИЛ 11 23 в кдчестве признака чтения кодл пути из блока 21 памяти К-го блока 12 по адресу, хранящемуся в счетчике 34 Р-го 45 блока 12 (в данном случае па первому адресу), 11 ути передачи импульса чтения и адреса рассмотрены выше. Считдццый из блока 21 памяти К-га бцакд 12 код пути поступает через вход 47 50 Р-го узла 12 и ключ 19 этого блока в блок 27Здесь поступивший код пути складывается с кодом Р-й вершины, хранящимся в регистре 37, в результате чего образуется код пути от на чапьной к Р-й вершине, Этот кад через коммутатор 18 поступает ца информационный вход записи блока 21 памяти,Прц поступлении через элемент ИЛИ25 нд вход признака записи блока 21тактового импульса, задержаццого навремя формирования кода пути в элементе 30 задержки, производится записьсформированного кода в блок 21 памяти по адресу, присутствующему навыходе счетчика 38 адреса записи,Следующий тактовый импульс производит описанным образом чтение изблока 21 памяти К-го блока 12 очередного кода пути, дополняет его единицей в Р-м разряде путем сложения вблоке 27 Г-го блока 12 и записываетполученный код пути в очередную ячейку блока 21 памяти Р-го узла 12, Если в некоторый момент времени адресчтения, установленный в счетчике 34,превысит количество путей к К-й вершине, хранящееся в регистре 35 Р-гоузла, то сигнал с выхода блока 22после прохождения через элементИЛ 11 24 поступит на выход 49 Р-го блока 12 как сигнал переключения Р-гакоммутатора ца (К+1)-ю группу связей, увеличит содержимое счетчика 39на единицу, запрет с помошью ключа 31выдачу по выходу 46 Р-го блока 12импульса чтения и установит коммутатор 17 в исходное состояние,Если содержимое счетчика 39 окажется равным количеству вершин в графе, то цикл формирования путей к Р-йвершине заканчивается. При этом сигнал с выхода счетчика 39 после прохождения через элемент ИЛИ 26 поступает на выход 44 Р-го блока 12, переводит коммутатор 18 в состояние,цри котором к информационному входузаписи блока 21 памяти подключаетсявыход регистра 36, где записан кодномера последнего записанного в блок21 кода пути (количество путей),Этот же сигнал закрывает ключ 32,предотвращая изменение содержимогорегистра 36 при изменении адреса записи в счетчике 38, устацавливает нулевой адрес записи в счетчике 38 ипоступает в качестве признака записичерез элемент ИЛИ 25 на вход признака записи блока 21 памяти, В результате этих действий в нулевую ячейкублока 21 памяти записывается кодколичества путей к Р-й вершине. Сигнал с выхода 44 Р-го блока 12 проходит через элемент ИЛИ 6 ца входпризнака чтения блока 5 памяти,обеспечивая передачу на дешифратор 8 изблока 5 кода очередной вери 1 ины, Дев шифратор 8 выводит из активного состояния Р-й блок 12 с помощью Р-го ключа 16, блокирует Р-й столбец модели 1 и переводиз описанным ранее 5 способом в активное состояние блок 12, соответствующее очередной вершине. Цикл формирования путей к этои вершине аналогичен рассмотренному циклу формирования путей к Р-й вершине.Если на вход дешифратора 8 поступит нулевой код, то на (М+1)-м выходе дешифратора 8 появится сигцдл останова генератора 13, завершающий функционирование устройства,Результатами работы устройства являются коды путей к вершинам грдфа, накопленные в блоках 21 пдмяти блоков 12.Форл 1 улаиз обретения1. Устройство для моделировация графов, содержащее дешифратор, гене 25 ратор тактовых импульсов и матричную модель графа из М строк и М столбцов; (Р, К)-й узел которой (Р = 1 М, К = 1 .,М) содержит элемент И и триггер, информационный выход которо- З 0 го подключен к первому входу злемента И того же узла матричной модели графа, о т л и ч а ю щ е е с я тем, что, с целью расширения класса решаемых задач за счет определения всех 35 возможных путей к вершинам моделируемого графа, в него введена группд блоков определения путей, группа коммутаторов, коммутатор, два элемента ИЛИ, блок памяти, группа ключей и два 0 дешифратора, а в каждый узел матричной модели графа введен ключ, причем информационный вход блока памяти является информационным входом устройства, вход пуска генератора тактовых 45 импульсов подключен к (М+1)-му входу первого элемента ИЛИ, к первому управляющему входу коммутатора и является входом пуска устройства, вьгход первого элемента ИЛИ подключен к 50 входу признака чтения блока памяти, выход которого подключен к первому информационному входу коммутатора, первый информационный выход которого подключен к информационному входу 55 дешифратора, Р-й выход которого подключен к входу пуска Р-го блока определения путей и к Р-му входу второго элел 1 цтд ИЛИ, выход которого подключен к второму управ тян 1 щел 1 У входу коммутатора, второй информационный выход которого пс дключц к ицфрмдционцому входу втрого депзифрдторд, Р-й выход которого подключен к второму входу цемента И кдждго узла Р-го столбца матричной модели графа и к управляющему входу Р-го ключа группы, выход которого подключец к тактовому входу Р-г блока опрделения путей, (М+1)-й выход второго дешифратора подключен к входу стацова генератора тактгчгх импульсц, выход которого подключен к инФормационным входам всех ключей группы, выход элемента И (Р,К)-го узла мдтричцои модели графа подключен купрдцляющему входу ключд того же узд ц к первому информдциоцному входу К-й группы Р-го кол 1 лгутдторд группы, црвый информдциоццый вьгход (М+1) - Й группы которого подключен к входу признака наличия дуги Р-го блока определения путей, информационный выход которого подключен к первым информационным входдм всех ключей К-й строки узлов (К=Р) матричной модели графа, первый информационный вьгход ключа (Р,К)-го узла матричной модели графа подключен к второму информационному входу К-й группы Р-го коммутатора, второй информационный выход которого соединен с информационным входом Р-го блока определения путей, выход адреса чтения которого подключен к первому информдциоцному входу (М+1) группы Р-го комлгутдтора группы, первый информационный выход К-й группы которого подключен к второму информационному входу ключа (Р,К)-го узла матричной модели графа, второй информационный выход которого подключен к входу адреса чтения Р-го блока определения путей, выход признака чтения которого подключен к второму информационному входу (М+ 1) -й группы Р-го коммутдторд группы, второй информационный выход К-й группы которого подключен к третьему информационному входу ключд (Р,К)-го узла матричной модели графа, третий информационный выход которого подключен к входу признака чтения Р-го блока определения путей, выход признака выбора очередного узла которого подключен к управляющему входу Р-го коммутатора группы, выход г 1 ричцакд окон9 1322306 10нация работы 1-го бздока определения является выходом признака выбора путей подклдочец к 1)-гду входу первого очередного узла блока определения элемента ИЛИпутей, ицформациоцный выход третьегосчетчика подключен к первому входу третьего элемента ИЛИ, выход которого подклдочен к входу установки в "0 2, Устройство по и. 1, о т л и - ч д ю щ е е с я тем, что каждый блок определеция путей содержит трп ключа, три д(омутатора, блок памяти, четыре элемента ИЛИ, три элемента задержки, блок сравнения кодов, три регистра, счетчик адреса чтения, счетчик адреса записи, третий счетчшп, элемент 1 дЕ и блок лод ддческого сложедддддд, причем ицформациоццьдй вход первого коммутатора яд)ляется тактовым входом бздокд Орсдс)лендяЕд НорГЗсдй ддцфорг )идо)1 цд. 33 дХС)Д пер 0 о комлдутаторд цодкл:оден к соесу цед)30)гу упрддзлядо.ег" 33:(Оду д; ходу устацоцкд в "О" сдегдид(с адрес:Оня, д( первому уцрсддь.дя )щелду д):с)Ц) )3 ТОРОД 0 ЕОЛ)ЛдУГдТОРД) Е Уд)Г)ДВ зд)до.,оу Входу псрдзй 0 езиоч д д( пер 3305 у дзходу перво 0 .)здел 1 еддтс 11,11133 ысчетчика адреса записи, к первому управляющему входу четвертого элемента ИЛИ, к управляющему входу второгоключа, к второму управляющему входу третьего коммутатора и является выходом признака окончания работы блока.определения путей, информационныйвход третьего элемента задержки подклдочец к третьему управляющему входу третьего коммутатора, к счетному входу счетчика адреса записи, к второму ходу четвертого элемента ИЛИ и является входом пуска блока определенияпутей, ицформациоццыи выход третьего.)лемецта задержки подкзпочен к второлду входу третьего элемента ИЛИ итретьему входу четвертого элемента 1 РЛ, Выход которого подключен к входу признака записи блока памяти, информационный выход которого являетх)дз которого яляется д)ыходом ддрддзцдкд ггения блока одрсдсс)Вд путей, д торой ицформдцддоддцдп ьдхо; первого ся яформационным выходом блока опре 5)сдед 5 путей информационный Вход второго коммутатора является информациодпдым Входом блока определения путей, Гдервый информационный Выход которого подключен к информационномуВходу первого регистра, информационцыи выход которого подключен к второму дгнформационному входу блока сравнения кодов, выход признака равенства которого соединен с вторым входом второго элемента ИЛИ, второй информационный выход второго коммутатора подклю)дец к входу первого случаемого блока логического сложения, информационный выход которого подключен к первому информационному входу третьего коммутатора, информационный выходкоторого подключен к информационному Входу записи блока памяти, информационный выход второго регистра подключен к входу второго слагаемого блока логического сложеня и к второму информационному входу третьего коммутатора, информационный выход счетчика адреса записи подключен к входу адреса записи блока памяти и к информационномувходу второго ключа, информационныйвыход которого подключен к информационному входу третьего регистра,иформационный выход которого подключен к третьему информационному входу длдлдудторд подк:почел д; с(зоегу дзто) )лду уцрддз;дднощс.му дзхс)у; пс рддому , и:)Гпз;яо;деу Входу д;торо 0 к.цочд, крд)с)л упрдвлядощему Вхс Ду третьсго д(с)л)у т)д 05) сз д к В тс)рс)л .: др ддзд)цо.д елу ВХ.);,дУ ВТОРОГО КОМ дУТДТОРД, ТРС."Гддй дц.О 1)с,Ноцддыд ход дде,)дзО 0 д(Олдгду о сдт)рд ддйдклдочец к тсд)(ГОБОму дзходу счет;цка адреса здпн и, к )ход;дл це 1)ого д Второго эзделде:од задержкиК тдятОВОМу ХОДУ СЧс.т дцКд ддрЕСд дтсН 5 додс 1)ор(с)плед ВыхОД д(оторо - дт) В) ЦКЗЦОЧЕЦ д( ПСЗРВОЧ" ИцфОРМДЦИОВ ному Входу бздс)ксд срсддзддедд 5 Кодов и является выходом адреса чтения блока од 1)едечецддя путей, выход д:ервого э:демета задержки поддкгдючсгц к дцдфар."дсдддддоццо:ду вхОду Г 1)етьего клочс .н )ОР дсддДддодндЬГ ДЗЬдХОД КОТОРО 0 ПОДКЛдО чец к дзторому дзходу пердзод 0 эзделдецта 1 1:1, Вл(од элемента 11 Е явздяетс 5) Входом признака наличия дугдд блока определения путей, выход .злемецтд 13 Е цодклдочец к ицс 1)ормацгдоддцолду входу первого клича, ГднсЬорлддцгдоцндд Гзьгход кс)торого подключен к пс рвому входу второго эзделдентд ИЛИ, выход которого цодкзпочец к управляющему входутретьего кл)оча, к третьему упрдвля;од;елу входу первого коммутатора, к с)детцолдуходу третьего с детчикд ц 10 15 20 25 30 35 10 45 50 55третьего коммутатора, выход второго элемента задержки подключен к четвертому входу четвертого элемента Ш 111, вход адреса чтения блока памяти являст я нхопом дпресд чтеция блока опрепе:н.ния нутеи, вход признака чтения блока пдмяти яв.чяется входом признака чтения блока определения путей..Олийнык Коррек Соста Техре кмар орович едак т акаэ 2867/47 НИИП пооскв оиэводственно-полиграфическое предприятие, г, Ужгород, ул, Проектная, 4Тираж 672дарственногоиэобретений иЖ, Раушс Подписноомитета СССРоткрытийая наб., д, 4/5