Модель ветви графа Советский патент 1975 года по МПК G06F15/173 

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

Генератор импульсов 14 вырабатывает на своих выходах 36 и 37 импульсы FHi и riiz, сдвинутые относительно друг друга.

Предварительно в счетчики начального и конечного адресов 6 и 7 заносятся соответственно адреса начального и конечного узлов моделируемой ветви графа.

В формирователь временного интервала 10 заносится длительность ветви, а триггеры 8 и 9 устанавливаются в нулевое состояние.

Для запуска модели ветви 11 блок автоматического формирования топологии 12 подает на вход 23 модели ветви 11 импульсы серии ГИ2 до тех пор, нока на выходе счетчика начального адреса 6 не появится сигнал. В этот момент блок управления 13 прекращает подачу импульсов серии ГИа из блока автоматического формирования топологии 12 на вход 23 и одновременно с импульсом ГИа подает на вход 22 модели ветви 11 через элемент «ИЛИ 18 пусковой импульс из блока автоматического формирования топологии 12. Пусковой импульс со входа 22 поступает на второй вход элемента «И 2. Сигнал с выхода триггера 9 поступает на третий вход элемента «Fi 2. Ксли модель ветви 11 принадлежит ветви, исходящей из начального узла, сигнал с выхода счетчика «ачального адреса 6 поступает па первый вход элемента «И 2. Выходной сигнал элемента «И 2 разрешает для формирователя временного интервала 10 счет импульсов серии ГИь поступающий по входу 24 из блока автоматического формирования топологии 12. Отсчитав, число импульсов, пропорциональное длительности данной ветви, формирователь временного интервала 10 выдает сигнал, который поступает на первый вход элемента «И 1. При наличии на втором входе элемента «И 1 разрещающего сигнала с выхода триггера 9, сигнал с выхода этого элемента устанавливает в единичное состояние триггер 8. Сигнал с единичного выхода триггера 8 поступает на первый вход элемента «И 5 и при наличии разрещающего сигнала на втором входе элемента «И 5 с выхода триггера 9, сигнал с выхода элемента «И 5 по выходу 25 поступает в блок автоматического формирования топологии 12 на один из входов группы входов 27 элемента «ИЛИ 15, к остальным входам которого подсоединены одноименные выходы других моделей ветвей, не изображенных на чертеже. Пройдя через элемент «ИЛИ 15, сигнал поступает па вход инвертора 21, который вырабатывает запрет на одном из входов элемепта «И 20. Второй вход элемента «PI 20 соединен со входом 31 и далее с выходом 36 генератора импульсов 14, поэтому серия импульсов ГЙ больше не поступает на вход 24 модели ветви И. Одновременно с выхода элемента «ИЛИ 15 на один из входов элемеита «И 19 поступает разрешение, и через элемент «И 19, второй вход которого соединен со входом 32 и далее- с выходом 37 генератора импульсов 14,

серия импульсов ГИ2, пройдя элемент «ИЛИ

10,поступает по выходу 34 на вход 23 модели ветви 11.

Серию ИлМпульсов ГИ2 начинают считать одповременно счетчики начального и конечного адресов и и 7. Сигнал переполнения с выхода счетчика конечного адреса 7 поступает на входы элементов «И 3 и 4. Если данная ветвь закончилась, то на втором входе элемента «И

4 имеется разрешающий сигнал с единичного триггера 8, и сигнал переполнения счетчика конечного адреса 7, пройдя через элемент «И 4, поступит по выходу 26 в блок автоматического формирования топологии 12 па одип из

входов группы входов 28 элемента «ИЛИ 17, к остальным входам которого подсоедипены одноименные выходы других моделей ветвей, не изображенных на чертеже. Выходной сигнал эле.мента «ИЛИ 17 блока автоматического формирования топологии 12, пройдя через элемент «ИЛИ 18, поступает через вход 22 модели ветви 11 на входы элементов «И 2 и 3. Одновременное появление сигнала на входе 22 и выходе счетчика конечного адреса 7 свидетельствует о том, что данная ветвь закончилась ранее других ветвей, входящих в узел, адрес которого записан в счетчике конечного адреса 7. Так как счетчики начального и конечного адресов 6 и 7 считают импульсы одновременно, то на выходе счетчика начального адреса 6 модели ветви 11 и других моделей ветвей, исходящих из рассматриваемого узла, будут разрещающие потенциалы. В модели ветви 11 этот потенциал поступает на вход

элемента «И 1. И если на входе 22 имеется в этот момент разрещающий потенциал, то выходной сигнал элемента «И 1 модели ветви

11,других моделей ветвей, исходящих из рассматриваемого узла, подготавливает формирователь временного интервала 10 для отсчета импульсов, поступающих на вход 24.

Сигналы с выхода счетчика конечного адреса 7 поступают на вход элемента «И 3 при наличии разрешения на входе 22. Во всех моделях ветвей, входящих в узел графа, выходной сигнал элемента «И 3 устанавливает в единичное состояние триггер 9, и выходной сигпал триггера 9 запрещает прохождение сигпала с единичного выхода триггера 8 через

элемент «И 5 на соответствующий выход 25 и запрещает установку в единичное состояние триггера 8 с выхода элемента «И 1, если в модели ветви И, входящей в данный узел, счет импульсов закончился нозже.

Импульсы серии ГИз ноступают на вход 23 модели ветви 11 до тех пор, пока на любом из входов группы входов 27 блока автоматического формирования тонологии 12 присутствует сигнал. Таким образом, в случае одновред енного окончания работы блоков-моделей ветвей, входящих в разные узлы графа, каждый из них опращивается. После того, как опращиваются все модели ветвей, в которых закончено формирование временного интервала,

схема «ИЛИ 15 блока автоматического формирования топологии 12 запрещает подачу импульсов ГИ2 на входы 23 и разрешает поступление импульсов THi на входы 24.

При появлении сигнала на входе 22, фиксирующего окончание какой-либо ветви, входящей в конечный узел графа, блок управления 13 прекращает работу.

Суммарное количество импульсов, поступивщее по входу 24 начала счета, равно величине кратчайшего пути. Единичный выход трнггера 8 модели ветви 11 индуцирует принадлежность ветви дереву кратчайших путей.

Предмет изобретения

Модель ветви графа, содержащая триггер, формирователь временного интервала, счетчики начального и конечного адресов и элементы «И, причем один вход первого элемента «И соединен с выходом формирователя временного интервала, первый вход которого соединен с выходом второго элемента «И, первый вход которого соединен с выходом с гетчи6

ка начального адреса, выход счетчика конечного адреса соединен с первыми входами третьего и четвертого элементов «И, второй вход третьего элемента «И соединен со вторым входом второго элемента «И, третий вход которого соединен с выходом триггера, а вход счетчика начального адреса соединен со входом модели, отличающаяся тем, что, с пелью сокращения оборудования, она содержит второй триггер, вход которого сое0динен с выходом первого элемента «И, второй вход которого и первый вход пятого элемента «И соедипены с выходом первого триггера, второй вход пятого элемента «И соеди5нен с выходом второго триггера и со вторым входом четвертого элемента «II, вторые входы формирователя временного интервала и третьего элемента «И соединены с соответствуюн ими входами модели ветви, выходы которой соединены с выходами четвертого и пятого элементов «И, а вход счетчика конечного адреса соединен со входом счетчика нача.-|ьиого адреса.

-- 1л-I ..г Л i2:; V .:-. и-г-Щ}