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

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

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

На фиг. 1 приведена фyикциoнaJИзHa схема устройстваJ на фиг. 5 - функциональная схема блока определения путей.

Устройство содержит матричную модель 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, информа1;ионньп1 вькод 43 блока 12, выход 44 признака окон- работы блока 12, выход 45 адреса чтепия блока 12, выход 46 признак чтения блока 12, информационный вход 47 блока 12, вход 48 признака наличи дуги блока 12, выход 49 признака выбора очередного узла блока 12, выход 50 признака пуска блока 12.

Устройство работает следующим образом.

Перед запуском устройства все коммутаторы всех блоков 12 устанавливаются в состояние, при котором первые информационные входы этих комг-гутато- ров соедш1ены с их первыми выходами. Счетчики 38 и 39 устанавливаются в нулевое состояние.

Ключи 32 всех блоков 12 устанавливаются в состояние, прр котором выход счетчика 38 адреса залиси оказывается подключенным к входу регист

ра 36, т.е. в открытое состояние. В регистры 37 всех блоков 12 заносятся двоичные коды, в которых в единичном состоянии находится только разряд с номером, равным номеру соответствующей блоку 12 вершины (номеру столбцу матричной модели 1 графа, комт татор 11 которого управляется блоком 12 через выход 49). Содержимое блоков 21 памяти всех блоков 12 обнуляется, а в блок 5 памяти по входу 15 устройства записываются двоичные коды номеров вершин моделируемого графа. При этом пефвым записывается код номера начал ной вершины, после чего в произвольном порядке записываются коды 1омеров вершин, составляющих парный ярус графа, затем аналогичным образом записываются коды номеров вершин, составляющих второй, третий и т.д. ярусы. После записи всех кодов номеров вершин в блок 5 памяти записывается нулевой код, являющийся приз}шком окончания информации о вершинах моделируемого графа.

Первоначально коммутаторы 11 мат- рично модели 1 устанавливаются в состояние, при котором (М+1)-я группа связей подключается к первой. Информация о топологии моделируемого графа заносится путем установки в единичное состояние (Р, К)-й триггеров 2, расположенных на перенесении К-й строки (к - номер начальной вер-

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

Запуск устройства осуществляется подачей специального сигнала на вход 14. По зтому сигналу осуществляется запуск генератора 13, коммутатор 10 переводится в состояние, при котором выход блока 5 памяти оказывается подклоченным к информационному входу

д,С иифратора 9. По этому же сигналу производится пересылка первого кода номера вершины моделируемого графа (кода номера начальной вершины) в дешифратор 9. На выходе дешифратора

9, соответствующем nocTynjffimeMy коду, формируется сигнал запуска в первом режиме блока 12, совпадающего по номеру с начальной вершиной моделируемого графа, являющиI cя в то же время сигналом перевода коммутатора 10 в единичное состояние, счетчик 38 адреса записи переводит коммутатор 18 в состояние, при котором к второму

входу блока 21 памяти подключается выход регистра ,37. Этот же сигнал является сигналом записи, который после прохождения через элемент RJTli 25 поступает на вход признака записи блока 21 памяти и обеспечивает занесение в этот блок по адресу, равному 1, двоичного кода из регистра 37. Одновременно адрес записи, равный 1, записывается в регистр 36. К этому моменту времени поступивший по входу 50 блока 12 и задержанный в элементе 28 сигнал появляется на выходе, элемента I-UIH 26. Он переводит коммутатор 18 в состояние, при котором к информационному входу записи блока 21 памяти подключается выход регистра 36, содержащего конечный адрес записи. Этот же сигнал поступает на выход 44 блока 12, одновременно закрывает ключ 32, предотвращая тем самым изменение содержимого регистра 36, устанавливает счетчик 38 адреса записи в нулевое состояние Рассматриваемый сигнал обеспечивает запись в блок 21 памяти по адресу, равному О, значения конечного адреса записи кодов в этот блок (двоичного значения количества путей к соответствующей блоку 12 вершине).

Сигнал с выхода 44 запущенного в первом режиме блока 12 после прохождения через элемент ИЛИ 6 обеспечивает передачу в дешифратор 8 кода номера первой вершины первого яруса (ярусы нумеруются начиная с 0) из блока 5 памяти. Дешифратор 8 преобразует этот код в сигнал на соответствующем выходе. Этот сигнал обеспечивает прохождение сигнапов от триггеров 2 через элементы И 3 на управляющие входы ключей 4 для всех узлов соответствующего столбца матричной модели 1 графа, а также поступление на вход 40 соответствующего блока 12 тактовых импульсов от генератора 13. Те ключи 4 столбца, на которые поступили сигналы от триггеров 2, устанавливаются в открытое состояние. С этого момента блок 12, соответствующий по номеру выхода дешифратора 8 (активный блок 12), начинает цикл формирования кодов путей к вершине, код номера которой поступил на дешифратор 8. Этот цикл состоит из М тактов. Такт с номером К соответствует случаю подключения к связям (М-ь 1) группы коммутатора 11 связей К-й

группы, т.е. случаю рассмотрения К-й вершины в качестве предшественника для вершины, соответствующей активному блоку 12.

с Рассмотрим порядок определения путей для случая, когда активный блок 12 имеет номер Р.

В каждом такте блок 12 может работать либо во втором, либо в треть10 ем режиме. Второй режим соответствует отсутствию дуги, ведущей от вершины с номером К к вершине с номером Р. В этом с.ггучае после подключения в Р-м коммутаторе 11. к связям (М+1)-й

f5 rpynrff . связей К-й группы на входе 48 активного блока отсутствует един1гчньгй сигнал, что обеспечивает открывание ключа 33 и прохождение очередного тактового импульса с первого .инфор0 мационного выхода коммутатора 17 на первьш вход элемента ИПИ 24. На выходе этого элемента формируется сигнал, поступающий на выход 49 блока 12 как сигнал переключения Р-го кдммутато5 ра 11 на (К-ь1)-ю группу связей, а

также увеличивающий на единицу содержимое счетчика 39 и устанавливающий коммутатор 17 в исходное состояние. Трет1 Й режим соответствует нали0 чио в графе дуги, ведущей от вершины с номером К к вершине с номером Р. В этом случае на входе 48 Р-го блока , 12 присутствует единичный сигнал, который обеспечивает закрытие ключа

33. Очередной тактовьш импульс, пос- тупивший по входу 40, после прохождения через коммутатор 17 производит установку в нулевое состояние счетчика 34 и подключение с помощью ком0 мутатора 19 входа 47 к входу регистра 35. Этот же импульс поступает через элемент ИЛИ 23, выход 46 узла, нулевую и К-ю группы связей Р-го коммутатора 11, К-й ключ 4 Р-го

5 столбца модели 1 и вход 41 К-го блока 12 в качестве импульса чтения на вход признака чтения блока 21 памяти К-го блока 12. Адрес чтения (в данном случае нулевой) в блок 21

0 К-го блока 12 поступает из счетчика 34 адреса чтения активного блока 12 через выход 45 этого блока, (М+1)-ю и К-ю группы связей Р-го коммутатора 11, К-й ключ 4 Р-го столбца модели 1

5 и вход 41 К-го блока 12. По импульсу чтения из нулевой ячейки блока 21 К-го блока 12 считывается код количества путей от начальной вершины к

K-fi. Этот код передается и регистр 35 активного блока 12 через иыход 43 К-го узла 12, К-й ключ 4 Р-го столбца матричной модели 1, К-ю и нулевую группы связей Р-го комм татора 11, вход 47 Р-го блока 12 и коммутатор 19 этого блока. Указанны тактовый импульс кроме того устанавливает коммутатор 17 в состояние, при котором его 1П1формацио1И ый вход подключен к второму информационному выходу

Следующий тактовый импульс после прохождения через коммутатор 17 открвает клоч 32, обеспечивая тем самым возможность передачи текущего адреса записи из счетчика 38 в регистр 36, подключает с помощью коммутатора 19 вход 47 Р-го блока 21 к ходу блока 27, подключает с помощью коммутатора 18 информационньш вход записи блока 21 памяти к выходу блока 27, а также переводит коммутатор 17 в состояние, при котором обеспечивается 1)юхожде- пие последующих тактовых импульсов через третий информационней выход этого ком 1утатора.

Очередной тактовьй импульс с входа 40 Р-го блока 12 увеличивает на единицу содержиг-гае счетчиков 34 и 38 Hoobrii адрес чтения из счетчика 34 поступает на вход блока 22 сравнения кодов, где он сравнивается с количеством путей, накопленч,гх в блоке 21 памяти К-го блока 12. Если этот адрес т ггения превьпиает количество путей, ведущих к предшествующей К-й вершшш, то на выходе блока 22 отсутствует сигнал. К этому :- омонту импульс с третьего и}1формациопного выхода коммутатора 17 после задержки в элементе 29 поступает через откры- ключ 31 и элемент ИЛИ 23 в качестве признака чтения кода пути из блока 21 памяти К-го блока 12 по адресу, хранящемуся в счетчике 34 Р-го 45 предотвращая изменение содержимого

блока 12 (в данном по первому адресу). Пути передачи импульса чтения и адреса рассмотрены выше. Счи- танньш из блока 21 памяти К-го блока 12 код пути поступает через вход 47 Р-го узла 12 и ключ 19 этого:блока в блок 27. Здесь поступивший код пути складывается с кодом Р-й вершины, хранящимся в регистре 37, в результате чего образуется код пути от на- 55 нал с выхода 44 Рто блока 12 про- чальной к Р-й вершине. Этот код через ходит через элемент ИЛИ 6 на вход коммутатор 18 поступает на информационный вход записи блока 21 памяти.

признака чтения блока 5 памяти,обе печивая передачу на дешифратор 8 и

.

ы

3223066

При поступлении через элемент ИЛИ 25 на вход признака записи блока 21 тактового импульса, задержанного на время формирования кода пути в зле5 менте 30 задержки, производится запись сформированного кода в блок 2f памяти по адресу, присутствующему на выходе счетчика 38 адреса записи. Следующий тактовый импульс произtO водит описанным образом чтение из

блока 21 памяти К-го блока 12 очередного кода пути, дополняет его единиг цей в Р-м разряде путем сложения в блоке 27 1 -го блока 12 и записывает

f5 по;тученный код пути в очередную ячейку блока 21 памяти Р-го узла 12. Если в некоторый момент времени адрес чтения, установленный в счетчике 34, превысит KOJUPiecTBo путей к К-й вершине, хранящееся в регистре 35 Р-го узла, то сигнал с выхода блока 22 после прохождения через элемент ИЛИ 24 поступит на выход 49 Р-го блока 12 как сигнал переключения Р-го

коммутатора на (К+1)-ю группу связей, увеличит содержимое счетчика 39 на единицу, запрет с помош.ью ключа 31 выдачу по выходу 46 Р-го блока 12 импульса чтения и установит коммутатор 17 в исходное состояние.

Если содержимое счетчика 39 окажется равным количеству вершин в графе, то цикл формирования путей к Р-й вершине заканчивается. При этом сигнал с выхода счетчика 39 после прохождения через элемент ИЛИ 26 поступает на выход 44 Р-го блока 12, переводит коммутатор 18 в состояние, при котором к информационному входу

записи блока 21 памяти подключается выход регистра 36, где записан код номера последнего записанного в блок 21 кода пути (количество путей). Этот же сигнал закрывает ключ 32,

регистра 36 при изменении адреса записи в счетчике 38, устанавливает нулевой адрес записи в счетчике 38 и поступает в качестве признака записи 50 через элемент ИЛИ 25 на вход признака записи блока 21 памяти. В результате этих действий в нулевую ячейку блока 21 памяти записывается код колггчества путей к Р-й вершине. Сигнал с выхода 44 Рто блока 12 про- ходит через элемент ИЛИ 6 на вход

признака чтения блока 5 памяти,обеспечивая передачу на дешифратор 8 из

7 1322306

блока 5 кода очерсдноГ нершнны, Де шифратор 8 выводит из активного состояния Р-й блок 12 с помощью Р-го ключа 16, блокирует Р-й столбец модели 1 и переводит описанным ранее способом в активное состояние блок 12, соответствующее очередной вершине. Цикл формирования путей к этой вершине аналогичен рассмотренному

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

циклу формирования путей к Р-й верши- О ключа группы, выход которого подклюке.

Если на вход дешифратора 8 поступит нулевой код, то на (М+1)-м выходе дешифратора 8 появится сигнал останова генератора 13, завершающий функционирование устройства.

Результатами работы ycTpoficTFia являются коды путей к вершинам графа, накопленные в блоках 21 памяти блоков 12.

Формула изобретения

20 :ia и к первому информационному входу К-й 1 руппы Р-го комг-гутатора группы, перн1,гй информационный выход (М+1)-й 1 руппы которого подключен к входу признака наличия дуги Р-го блока определения путей, информационный выход которого подключен к первым информационным входам всех ключей К-й строки узлов () матричной модели графа, первый информационньп выход

25

1. Устройство для моделирования графов, содержащее дешифратор, генератор тактовых импульсов и матричную модель графа из М строк и М столбцов; (Р, К)-й узел которой (Р 1,...,М; К 1,...,М) содержит элемент И и триггер, информационный выход которо- 0 ключа (Р,К)-го узла матричной модели го подключен к первому входу элемен- графа подключен к второму ивформационному входу К-й группы Р-го коммутатора, второй информационный выход которого соединен с информационным 35 входом Р-го блока опроде:7енич путей, адреса чтения которого подключен к первому информационному входу (М+1) группы Р-го комму татора Г руппы, первый информапионный выход ИЛИ, блок памяти, группа ключей и два W К-й группы которого подключен к вто- дешифратора, а в каждый узел матричной рому информационному вхоцу ключа

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

модели графа введен ключ, причем информационный вход блока памяти является информационным входом устройст- в а, вход пуска генератора тактовых импульсов подключен к (М+1)-му входу первого элемента ИЛИ, к первому управляющему входу коммутатора и является входом пуска устройства, выход первого элемента ИЛИ подключен к входу признака чтения блока памяти, выход которого подключен к первому информационному входу коммутатора, первый информационный выход которого подключен к информационному входу дешифратора, Р-й выход которого подключен к входу пуска Р-го блока определения путей и к Р-му входу вто-

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

чен к тактовому входу Р-го блока оп- 11еделения путей, ()-й выход второго дешифратора подключен к входу останова генератора тактовых импульсон, выход которого подключен к ин- (Ьормационным входам всех ключей группы, выход элемента И (P,K)-i-o узла матричной модели графа подключен к управляющему входу ключа того же уз:ia и к первому информационному входу К-й 1 руппы Р-го комг-гутатора группы, перн1,гй информационный выход (М+1)-й 1 руппы которого подключен к входу признака наличия дуги Р-го блока определения путей, информационный выход которого подключен к первым информационным входам всех ключей К-й строки узлов () матричной модели графа, первый информационньп выход

ключа (Р,К)-го узла матричной модели графа подключен к второму ивформа(1,К)-го узла матричной модели графа второй информационньп выход которог о подключен к входу адреса чтения Р-т о

45 блока определения путей, выход признака чтения которого подключен к второму информационному входу (М+1)-и группы Р-го коммутатора группы, второй информационный выход K-ii группы

50 которого подключен к третт,ему информационному входу ключа (Р,К)-го узла матричной модели графа, третиГ; информационный выход которог о подключен к входу признака чтения Р-го блока оп55 ределения путей, выход признака выбора очередного узла которого подключен к управляющему входу Р-го коммутатора группы, выход признака окон-

чапия работь Г-го блока определения nyreii подключен к -му входу первог о элемента ИЛИ.

2. Устройство по I. 1, о т л и - чающееся тем, что каждый блок определения путей содержит три ключа, три коммутатора, блок памяти, четыре элемента ИПИ, три элемента задержки, блок сравнения кодов, три регистра, счетчик адреса чтения, счетчик адреса записи, третий счетчик, элемент НЕ и блок логического сложения, причем информаудиониый вход первого коммутатора является тактовым входом блока опрс/ слсппя i.yTcii, iiopBL.ifi )м;эцпоииый выход первого коммутатора но;),ключен к ciioe ыу норному уп;5а1зля101:1ему входу, к нходу устапонки в О счетчика адреса чтения, к первому унран,:1я:|1тцому второго коммутато1)а, к унрав- ,пя10 .;ему входу первого ключ;; и к пер- iiOMy входу nepBoi o млемспта IIJII, вы- X07J, которого является 1 ы :одом признака чтения -блока определен гч нутеГ, второй )ормадион П)П1 первого чоммутатора подключен г: своему вто- кзму упрапл пощему входу, к lU iiiOMy упрлвляшщеь-гу входу второго клгоча, к 11ерво Гу управляющему, г ;-;од,у TpoTijOro К(, мму гатора и к второму 7з;1пд;у второго коммутатора, трсупш Нох:ррг а Ц1Онпый выход комму- laTopa иодк. почен к тактовому входу счетчпка адреса записи, к входам перг,ого и второго элементов задержки и к та ;товому 1;ход,у счетчика адреса чтения, 1П1фог) адионны11 выход которо- Г о подключен к первому инфop ГlДпoн ному входу блока сравнешм кодов и япляется выходом адреса чтания блока онределен1-ш путей, т ервого элемента задержки по.дключен к информационному входу третьего ключа, ин- формационньст выход которого подключен к второму входу первого элемента П.)1, вход элемента НЕ является г;:о- / iOM признака наличия дуги блока определения путей, выход элемента НЕ подключен к информационному входу первого ключа, информационн1)й выход которого подключен к первому входу второго элемента ИЛИ, выход которого иoдкJmчeн к управляющему входу третьего ключа, к третьему управляю- щему входу первого ко№-гутатора, к счетному входу третьего счетчика и

является выходом признака выбора очередного узла блока определения путей, шп})ормационный выход третьего счетчика подключен к первому входу третьего элемента ИЛИ, выход которого подключен к входу установки в О счетчика адреса записи, к первому управляющему входу четвертого элемента ИЛИ, к управляющему входу второго ключа, к второму управляющему входу

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

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

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

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

1 1t i22;U)6I 2

третьего коммутатора, пыхг)д второго .чяс-тси нходом ад1)еса чтения блока оп- элемента задержки подключен к четпер- редел(М1ия путей, nxo;t признака чтения тому входу четвертого элемента lUlU, блока памяти является входом приэка- вход адреса чтения блока памяти яв- ка чтения блока определения путей.

Изобретение относится к области вычислительной техники, может быть использовано при исследовании сетевых графов и позволяет определить все возможные пути к вершинам моделируемого графа. Наличие в устройстве для моделирования графов блока памяти и матричной модели графа позволяет хранить в памяти устройства ярусную структуру моделируемого графа, производить формирование путей к какой-либо вершине этого графа путем дополнения всех путей к предшествующим вершинам номером данной вершины, а также объединить все дополненные пути и занести их в блоки памяти соответствующих блоков определения путей устройства, что позволяет повысить качество и полноту исследования сетевых графов, используемых в качестве математических средств описания сложных объектов и процессов. При применении сетевых графов для обобщенного описания процесса функционирования программных комплексов внедрение изобретения позволит определить все возможные варианты последовательного выполнения элементов программного комплекса и значительно повысить качество его испытаний. 1 з.п. ф-лы, 2 ил. (/ С

.S-/

I

15

Редактор А.Ворович

Заказ 2867/47

Тираж 672Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграф1гческое предприятие, г. Ужгород, ул. Проектная, 4

Составитель Н.Шелобанова

Техред Л.Олийнык КоррекГор С.Шекмар