Устройство для моделирования графов
Изобретение относится к области вычислительной техники, может быть использовано при исследовании сетевых графов и позволяет определить все возможные пути к вершинам моделируемого графа. Наличие в устройстве для моделирования графов блока памяти и матричной модели графа позволяет хранить в памяти устройства ярусную структуру моделируемого графа, производить формирование путей к какой-либо вершине этого графа путем дополнения всех путей к предшествующим вершинам номером данной вершины, а также объединить все дополненные пути и занести их в блоки памяти соответствующих блоков определения путей устройства, что позволяет повысить качество и полноту исследования сетевых графов, используемых в качестве математических средств описания сложных объектов и процессов. При применении сетевых графов для обобщенного описания процесса функционирования программных комплексов внедрение изобретения позволит определить все возможные варианты последовательного выполнения элементов программного комплекса и значительно повысить качество его испытаний. 1 з.п. ф-лы, 2 ил. (/ С
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (19) (11) А1
GD 4
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4043897/24-24 (22) 26,03.86 (46) 07.07.87. Бюл. У 25 (72) Г.Н.Лаврик, Г.В ° Буряк, А.Ю.Печунов и Ю.И.Скорин (53) 681.333(088,8) (56) Авторское свидетельство СССР
М 1076909, кл. G 06 F 15/20, 1982.
Авторское свидетельство СССР
N- 1075268, кл. G 06 F 15/20, 1982, (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ
ГРАФОВ (57) Изобретение относится к области вычислительной техники, может быть использовано при исследовании сетевых графов и позволяет определить все возможные пути к вершинам моделируемого графа. Наличие в устройстве для моделирования графов блока памяти и матричной модели графа позволяет хранить в памяти устройства ярусную ! структуру моделируемого графа, производить формирование путей к какой-либо вершине этого графа путем дополнения всех путей к предшествующим вершинам номером данной вершины, а также объединить все дополненные пути и занести их в блоки памяти соответствующих блоков определения путей устройства, что позволяет повысить качество и полноту исследования сетевых графов, используемых в качестве математических средств описания сложных объектов и процессов, При применении сетевых графов для обобщенного описания процесса функционирования программных комплексов внедрение изобретения позволит определить все возможные варианты последовательного выполнения элементов программного комплекса и значительно повысить качество его испытаний, 1 з.п. ф-лы, 2 ил.
1322306
Изобретение относится к вычислительной технике и может быть использовано при исследовании сетевых графов для определения всех возможных путей к его вершинам.
Целью изобретения является расширение класса решаемых задач эа счет определения всех возможных путей к вершинам моделируемого граф».
На фиг. 1 приведена функцион я и.няя схема устройства; на фиг, 2 — функциональная схема блока определения путей, Устройство содержит матричную модель 1 графа, в узлах которой расположены триггеры 2, элементы И 3 и ключи 4, блок 5 памяти, первый и второй элементы ИЛИ б и 7, дешифраторы
8 и 9, коммутатор 10, группу ком гутаторог 11, группу блоков 12 определения путей, генератор 13 тактовых импульсов, вход 14 пуска устройства, информационный вход 15 устройства и группу ключей 16.
В состав каждого блока 12 входят первый, второй и третий коммутаторы
17-19, элемент HF. 20, блок 21 памяти, блок 22 сравнения кодов, с первого по четвертый элементы ИХ1И 23-?6, блок
27 логического сложения, элементы
28-30 задержки, ключи 31-33, счетчик
34 адреса чтения, регистры 35-37, счетчик 38 адреса з»ппси, третий счетчик 39, тактовый вход 40 блока определения путей, вхоп 41 признака чтения блока 12, вход 42 адреса чтения блси;а 12, информационный вьгход
43 блока 12, выход 44 признак» окончания работы блока 12, выход 45 адреса чтения блока 12, выход 46 признака чтения блока 13, информационный вход
47 блока 12, вход 48 признака наличия дуги блока 12, вьгход 49 признака выбора очередного узла блок» 12, вьгход
50 признака пуска блока 12.
Устройство работает следующим образом.
Перед запуском устройства все коммутаторы всех блоков 12 уст»и»впиваются в состояние, при котором первые информационные входы этих коммутаторов соединены с их первыми вьгходами.
Счетчики 38 и 39 устанавливаются в нулевое состояние.
Ключи 32 всех блоков 12 ycòàí»âливаются в состояние, при котором выход счетчика 38 адреса записи оказывается подключенным к входу регист25
55 ра 36, т.е. в открытое состояние. В регистры 37 всех блоков 12 заносятся двоичные коды, в которьгх в единичном состоянии находится только разряд с номером, равным номеру соответствую щей блоку 12 вершины (номеру столбцц матричной модели 1 графа, коммутатор
11 которого управляется блоком 12 через выход 49). Содержимое блоков
21 памяти всех блоков 12 обнуляется, а в блок 5 памяти по входу 15 устроиствя записываются двоичные коды номеров вершин моделируемого графа.
При этом первым записывается код номера начальной вершины, после чего в произвольном порядке записываются коды нсмеров вершин, составляющих первый ярус графа, затем аналогичным обр»зом записываются коды номеров верюипг, составляющих второй, третий и т.д. ярусы. После записи всех ко,цов номеров вершин в блок 5 памяти записывается нулевой код, являющийся признаком окончания информации о вершипах моделируемого графа.
Первоначально коммутаторы 11 матричной модели 1 устанавливаются в состояние, при котором (M+1)-я групп» связей подключается к первой. Информация о топологии моделируемого графя заносится путем установки в единичное состояние (Р, К)-й триггеров 2, расположенных на перенесении
К-й строки (К вЂ” номер начальной вершины моделируемой ветви графа) с Р-м столбцом (Р— номер конечной вершины моделируемой ветви графа).
Запуск устройства осуществляется подачей специального сигнала на вход
l4. По этому сигналу осуществляется запуск генератора 13 коммутатор 10 переводится в состояние, при котором выход блока 5 памяти оказывается подключенным к информационному входу дешифратора 9, По этому же сигналу производится пересылка первого кода номера вершины моделируемого графа (кода номера начальной вершины) в дешифратор 9. На выходе дешифратора
9, соответствующем поступившему коду, формируется сигнал запуска в первом режиме блока 12, совпадающего по номеру с начальной вершиной моделируемого графа, являющийся в то же время сигналом перевода коммутатора
10 в единичное состояние, счетчик 38 адреса записи переводит коммутатор
18 в состояние, при котором к второму группы, т. е. случаю рассмотрения К-й вершины в качестве предшественника для вершины, соответствующей активному блоку 12.
Рассмотрим порядок спределения путей для случая, когда активный блок
12 имеет номер P.
В каждом такте блок 12 может работать либо во втором, либо в третьем режиме. Второй режим соответствует отсутствюо дуги, ведущей от вершггны с номером К к вершине с номером
P. В этом случае после подключения в
P-м коммутаторе 11 к связям (И+1)-й групп1я связей К-й группы на входе 48 активного блока отсутствует единичный сигнал, что обеспечивает открывание ключа 33 и прохождение очередного тактового импульса с первого .информационного выхода коммутатора 17 на первый вход элемента ИЛИ 24. На выходе этого элемента формируется сигнал, поступающий на выход 49 блока 12 как сигнал переключения P-го коммутатора 11 на (К+1)-ю группу связей, а также увеличивающий на единицу содержимое счетчика 39 и устанавливающий коммутатор 17 в исходное состояние.
Третий режим соответствует наличию в графе дуги, ведущей от вершины с номером K кK в еeр ш и нHе с нHо мерам P. В этом случае на входе 48 P-га блока
12 присутствует единичный сигнал, который обеспечивает закрытие ключа
33. Очередной тактовый импульс, поступивший по входу 40, после прохождения через коммутатор 17 производит установку в нулевое состояние счетчика 34 и подключение с помощью коммутатора 19 входа 47 к входу регистра 35. Этот же импульс поступает через элемент ИЛИ 23, выход 46 узла, нулевую и К-ю группы связей P-го коммутатора 11, К-й ключ 4 P-го столбца модели 1 и вход 41 К-го блока 12 в качестве импульса чтения на вход признака чтения блока 21 памяти
К-го блока 12. Адрес чтения (в данном случае нулевой) в блок 21 памяти
К-ro блока 12 поступает из счетчика
34 адреса чтечия активного блока 12 через выход 45 этого блока, (И+1)-ю и К-ю группы связей P-ro коммутатора
11, К-й ключ 4 P-го столбца модели 1 и вход 41 К-го блока 12, По импульсу чтения из нулевой ячейки блока 21
К-го блока 12 считывается кад количества путей от начальной вершины к
3 1322306 4 входу блока 21 памяти подключается выход регистра 37. Этот же сигнал является сигналом записи, который после прохождения через элемент
ИЛИ 25 поступает на вход признака за5 писи блока 21 памяти и обеспечивает занесение в этот блок по адресу, равному 1, двоичного кода из регистра
37. Одновременно адрес записи, равный 1, записывается в регистр 36. К этому моменту времени поступивший по входу 50 блока 12 и задержанный в элементе 28 сигнал появляется на выходе элемента ИЛИ 26. Он переводит коммутатор 18 в состояние, при кото- 15 ром к информационному входу записи блока 21 памяти подключается выход регистра 36, содержащего конечный адрес записи. Этот же сигнал поступает на выход 44 блока 12, одновре- 2р менно закрывает ключ 32, предотвращая тем самым изменение содержимого регистра 36, устанавливает счетчик
38 адреса записи в нулевое состояние.
Рассматриваемый сигнал обеспечивает 25 запись в блок 21 памяти по адресу, равному О, значения конечного адреса записи кодов в этот блок (двоичного значения количества путей к соответствующей блоку 12 вершине) . Зр
Сигнал с вьгхода 44 запущеннаг о в первом режиме блока 12 после прохождения через элемент ИЛИ 6 обеспечи- е вает передачу в дешифратор 8 када номера первой вершины первого яруса 35 (ярусы нумеруются начиная с 0) из блока 5 памяти. Дешифратор 8 преобразует этот код в сигнал на соответствующем выходе. Этот сигнал обеспечивает прохождение сигналов от триг- 4Р геров 2 через элементы И 3 на управляющие входы ключей 4 для всех узлов соответствующего столбца матричной модели 1 графа, а также поступление на вход 40 соответствующего блока 12 45 тактовых импульсов от генератора 13 °
Те ключи 4 столбца, на которые поступили сигналы от триггеров 2, устанавливаются в открытое состояние. С этого момента блок 12, соответствую- 5Р щий по номеру выхода дешифратора 8 (активный блок 12), начинает цикл формирования кодов путей к вершине, код номера которой поступил на дешифратор 8, Этот цикл состоит из M так- 55 roe, Такт с номером К соответствует случаю подключения к связям (М+1) группы коммутатора 11 связей К-й
1322306
К-й. Этот код переда(ггся н ре. истр
35 активного блока 12 через выход
43 K-го узла 12, К-й кл)оч 4 Р-га столбца матричной модели I, К-и и нулевую группы связей P-го коммутатора
11, вход 47 P-га блока 12 и коммутатор 19 этого блока. Уклзяннь<й тактовый импульс кроме того ус.танлвливлет коммутатор 17 в состояние, при котором его 3п3формациа)3ный вход подклю- 1О чен к второму информационному выходу.
Следующий тактовый импульс после прохождения через коммутатор 17 открывает к)поч 32, обеспечивая тем самым возможность передачи текун1его адреса 15 записи из счетчика 38 в регистр 36, подкл)очает с помощью каммутлтора 19 вход 47 P-ro блокл 21 к 3)ходу блока
27, подключает с помощью ко".ьмутлтарл
18 и))формационный вход злп);си б:)окл 20
21 памяти к выходу блока 27, л тлкже перевод)п коммутатор 17 в сс.; таяние, при котором обеспечивается прохождение последующих тл)<тавых импульсoo через третий информационный выход 25 этого коммутатора.
Очередной тактовый импульс с IIxoдл 40 Г-го блока 12 увеличивает на сд)<ницу содержимое счетчиков 34 и 38.
Новый адрес чтения из счетчика 34 30 поступает на вход блакл 22 сравнения кодов, где он срлвнпвлс.тся с количеством путей, 33акапле)3)3)нх в блоке
21 плмяти К-го блакя 12. Если этат адрес чтения превьпнлет количество путей, ведущих к предшествующей К-и вершине, то нл выходе блока 22 отсутствует сигII QJI, К этому ."(оменту импульс с третьего информационного выходя коммутатора 17 после злдержки 40 в элеме. те 29 поступает через открытый ключ 31 и элемент ИЛИ 23 в клчестве признака чтения кодл пути из блока 21 памяти К-го блока 12 по адресу, хранящемуся в счетчике 34 P-го 45 блока 12 (в данном случае па первому адресу). Пути передачи импульса чтения и адреса рассмотрены выше. Считанный из блока 21 памяти К-га блока
12 код пути поступает через вход 47 50
Pro узла 12 и ключ 19 этого:блока в блок 27 ° Здесь поступивший код пути складывается с кодом P-й вершины, хранящимся в регистре 37, в результате чего образуется код пути от на- 55 чальной к P-й вершине, Этот кад через коммутатор 18 поступает на информационный вход записи блока 21 памяти, При поступлении через элемент ИЛИ
25 нл вход признака записи блока 21 тактового импульса, задержанного на время формирования кода пути в элементе 30 задержки, производится запись сформированного кода в блок 21 памяти по адресу, присутствующему на выходе счетчика 38 адреса записи.
Следу3ощий тактовый импульс производит описанным образом чтение из блока 21 памяти К-го блока 12 очередного кода пути, дополняет его единицей в P-м разряде путем сложения в блоке 27 Р-ro блока 12 и записывает полученный код пути в очередную ячейку блока 21 памяти P-го узла 12. Если в некоторый момент времени адрес чтения, установленный в счетчике 34, превысит ка.)пп<ество путей к К-й вершине, хранящееся в регистре 35 P-го узла, та сигнал с выхода блока 22 после прохождения через элемент
ИЛ11 24 поступит на выход 49 Р-го блока 12 как сигнал перекл)очения Р-га коммутатора на (К+1)-ю группу связей, увеличит содержимое счетчика 39 на едп)3ицу, запрет с помошью ключа 31 выдачу по выходу 46 P-го Слака 12 импульса чтения и установит коммутатор 17 в исходное состояние, Если содержимое счетчика 39 окажется равным количеству вершин в графе, то цикл формирования путей к P-й вершине заканчивается. При этом сигнал с выхода счетчика 39 после прохождения через элемент ИЛИ 26 поступает на выход 44 P-го блока 12, переводит коммутатор 18 в состояние, нри котором к информационному входу записи блока 21 памяти подключается выход регистра 36, где записан код номера последнего записанного в блок
21 кода пути (количество путей), Этот же сигнал закрывает ключ 32, предотвращая изменение содержимого регистра 36 при изменении адреса записи в счетчике 38, устанавливает нулевой адрес записи в счетчике 38 и поступает в качестве признака з".ïèñè через элемент ИЛИ 25 на вход признака записи блока 21 памяти, В результате этих действий в нулевую ячейку блока 21 памяти записывается код количества путей к P-й вершине. Сигнал с выхода 44 P-ro блока 12 проходит через элемент ИЛИ 6 на вход признака чтения блока 5 памяти,обеспечивая передачу на дешифратор 8 из 1322306 блока 5 кода очередной вершины. Д(— шифратор 8 выводит из активного состояния P-й блок 12 с помощью Р-го ключа 16, блокирует P-й столбец модели 1 и переводи- описанным ранее 5 способом в активное состояние блок
12, соответствующее очередной вершине. Цикл формирования путей к этой вершине аналогичен рассмотренному циклу формированггя путей к P-й верши- 10 не.
Если на вход дешифратора 8 поступит нулевой код, то на (М+1)-м выходе дешифратора 8 появится сигнал останова генератора 13, завершающий функционирование устройства.
Результатами работы устройства являются коды путей к вершинам графа, накопленные в блоках 21 памяти блоков 12.
20
Формул а изобретения
1. Устройство для моделировлнг(я графов, содержащее дешифратор, гене25 ратор тактовых импульсов и матричную модель графа из М строк и M столбпон; (Р, К)-й узел которой (Р = 1,...,М, К = 1,...,М) содержит элемент И и триггер, информационный выход которо- З0 го подключен к первому входу злемента И того же узла матричной модели графа, о т л и ч а ю щ е е с я тем, что, с целью расширения класса решаемых задач за счет определения всех 35 возможных путей к вершинам моделируемого графа, в него введена группа блоков определения путей, группа коммутаторов, коммутатор, два элемента
ИЛИ, блок памяти, группа ключей и двл 0 дешифратора, а в каждый узел матричной модели графа введен ключ, причем информационный вход блока памяти является информационным входом устройства, вход пуска генератора тактовых 45 импульсов подключен к (М+1)-му входу первого элемента ИЛИ, к первому управляющему входу коммутатора и является входом пуска устройства, вьгход первого элемента ИЛИ подключен к 50 входу признака чтения блока памяти, выход которого подключен к первому информационному входу коммутатора, первый информационный выход которого подключен к информационному входу 55 дешифратора, P-й выход которого подключен к входу пуска Р-го блока определения путей и к Р-му входу второго э:(еwгег<тл ИЛИ, выход которого подключен к второму упраггляюпГему входу коммутатора, второй информационный выход которог о пс дключ«н к информационному нход Второ(0 дешифратоpë, P é выход которог(i подключен к второму входу лементл 11 каждого узла Р-го столбца матричной модели графа и к управляющему входу Р-го ключ l группы, выход которого подключен к тактовому входу Р-го блока определения путей, (М+1)-й выход второго дешифратора полк.пючен к входу остлнова генераторл тлктовьгх импульсов, выход которого подключен к информационным входам всех ключей группы, выход элемента И (Р,К)-го узла матричной модели графа подключен к управляющему входу ключа того же уз.. л и к первому информационному входу
К-й группы Р-го ком;гутлторл группы, н«рвый информационный выход (М+1) — и гр:ппы которого подключен к входу признака наличия дуги Р-го блока определения путей, информационный выход которого подключен к первым инфоpMационным вход IM всех ключей К-й строки узлов (К=Р) млтри гной модели графа, первый информационный вьгход ключа (Р,К)-го уэлл матричной модели графа подключен к второму информационному входу К-й группы Р-го коммутатора, второй информационный вьгход которого соединен с информационным входом Р-го блока опр",äå: «Hич путей, выход адреса чтения которого подключен к первому информационному входу (М+1) группы Р-го коммутатора группы, первый информационный выход
K-й группы которого подключен к второму информационному входу ключа (i,Ê)-го узла матричной модели графа, второй информационный Bbfxofl; которого подключен к входу адреса чтения P-го блока определения путей, выход признака чтения которого подключен к второму информационному входу (М+ 1) -й группы P-го коммутатора группы, второй информационный выход К-й группы которого подключен к треть(.му информационному входу ключа (Р,К)-го узла матричной модели графа, третий информационный выход которого подг,лючеH к входу признака чтения P-го блока определения путей, выход признака выбора очередного узла которого подключен к управляющему входу P-ro коммутатора группы, выход ггричнакл окон9 1322306 10 (а«ия работы 1)-го блока (»ipe;je)iei!Iiff является Выходом признака выбора путей подкл!оче« к Г-му В оду пер(зого очередного узла блока определения элемента ИЛИ ° путей, информационный выход третьего счетчика подключен к первому входу третьего элемента ИЛИ, выход которого подкл!очен к входу установки в "0 ) 2. Устройство по и. 1, о т л и— ч а ю щ е е с я тем, что каждый блок определения путей содержит три ключа, три ко!(мутатора, блок памяти, четыре элемента ИЛИ, три элемента задержки, блок сравнения кодов, три регистра, счетчик адреса чтения, счетчик адреса зап!!сп, третий счетчик, элемент III . и блок лог!!ческого сложения, причем информационг«!й вход первого коммута Гора я()ляется
T <) Ii Tt) !3f.1м ВХОДО;! б 3(ок а 0 I(()O) j(Jic> !i! if!
:;",! С. >! ilk P f3(1! f !1«фо()г! !! 1! !to! i il!: l 13(!Х()Д
;I0P»O»0 КОЬ!г!У (Ь(тоР(3 !(С)<7((.(ГО (Е«К С13ОЕ ((с >(с . () f30;f)< с>!3р 1!3ЛЯ(ГГ(Е>! "с> 13 0 (()< 1
f3.,0j\)< < ста«ОБ!с!! 13 0 c>IÐ i 1(!!(» а„ ц)ес:(»те«пя,; первому упр(3!»(я 77>()му
»Э:t> (Э 13 то POI О ЕО".!МУ 1 с(тОРа) Е с !! Г) аВ
