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

4 со 1

00

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

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

На фиг. представлена функциональветственно числа 4,5,4,2,1,3,5 и 4

(задают номера узлов, в которые входят соответствующие адресам ветви графа). В блок 7 вьшода информации по адресам ,2,3,4 и 5 заносят соответственно списки (5), (2), (6), (3,1, 8) и (4J7)(задают списки ветвей, вхо дящих в соответствующие адресам спис- ная схема устройства, на фиг. 2 - вре- щд,- о « о

U ков узлы графа}., В блок о вьгоода инменная диаграмма работы первого и

формации по адресам 1 , 2,3,4 и 5 заносят соответственно списки чисел (6), (1,7), (2,3,4), (5) и (8) (задают спис ки ветвей, выходящих из соответст- 5 вующих адресам списков узлов графа). На вход 30 подают число 3 (номер начального узла пути). На вход 31 подают число 1 (номер начального узла пути).

второго блоков синхронизации на фиг, .3 - временная диаграмма работы третьего блока синхронизации, на фиг. 4 - пример исследуемого графа.

Устройство содержит с первого по пятый блоки 1-5 памяти таймер б, пе-рвый и второй блоки 7 и 8 вывода информации, с первого по третий блок 9-1 синхронизации, с первого по чет вертый регистры 12-15, блоки 16 сравнения, счетчик 17, первьш и второй триггеры 18 и 19, с первого по трети блоки 20-22 элементов И, с первого по третий элементы ИЛИ 22-25, элемент И 26 и элемент НЕ 27,

Кроме того, на фиг. I цифровые обозначения имеют вход 28 начальной установки устройства, вход 29 пуска устройства, вход 30 задания номера начального узла пути устройства,вход 31 задания номера конечного узла пути устройства, выход 32 признака окончания работы устройства, выход

На вход 28 начальной установки устройства подают импульсный сигнал единичного уровня. При этом снимаются все прерывания и обнуляются все каналы таймера, устанавливается в ноль триггер 18, обнуляется счет чик 7, устанавливается в единичное состояние триггер 19, в регистр 2 наносится число 3, в регистр 15 - число 1. На вход пуска устройства подают импульсный сигнал единичного уровня. При этом блок 7 вьшода информации выдает число 6, на свой информационный выход (номер ветви первой в списке входящих в началь33 веса кратчайшего пути в графе уст-35 „ь,й узел пути) и i-счпульсньй сигнал роиства, тактовьй вход 34 устройст- единичного уровня на выход призна- ва, с первого по пятый выходы 35-39

ка выдачи слова. При этом блок 9 си хронизации начинает формировать по следовательность сигналов в соответ

первого блока 9 синхронизации, с первого по пятый выходы 40-44 второго блока 10 синхронизации и с первого по четвертый выходы 45-48 третьего блока 11 синхронизации.

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

Пусть требуется определить величину кратчайшего пути между третьим и первым узлами в графе, предоставленном на фиг. 4 (цифры в скобках указывают номера узлов графа, цифры без скобок в числителе - номер, присвоенный ветви, в знаменателе - вес ветви). Перед началом работы обнуляют блоки 1, 3 и 5 памяти, в блок 2 памяти по адресам I, 2, 3, 4, 5, 6, 7 и 8 заносят соответственно.числа: 4, 2, 4, 2, i, 2, 1 и4 (задают длительность соответствующих адресам ветвей графа), в блок 4 памяти по адресам 1 5 2,3-,4,5,6,7 и 8 заносят состветственно числа 4,5,4,2,1,3,5 и 4

(задают номера узлов, в которые входят соответствующие адресам ветви графа). В блок 7 вьшода информации по адресам ,2,3,4 и 5 заносят соответственно списки (5), (2), (6), (3,1, 8) и (4J7)(задают списки ветвей, вхо

формации по адресам 1 , 2,3,4 и 5 заносят соответственно списки чисел (6), (1,7), (2,3,4), (5) и (8) (задают списки ветвей, выходящих из соответст- вующих адресам списков узлов графа). На вход 30 подают число 3 (номер начального узла пути). На вход 31 подают число 1 (номер начального узла пути).

На вход 28 начальной установки устройства подают импульсный сигнал единичного уровня. При этом снимаются все прерывания и обнуляются все каналы таймера, устанавливается в ноль триггер 18, обнуляется счетчик 7, устанавливается в единичное состояние триггер 19, в регистр 2 наносится число 3, в регистр 15 - число 1. На вход пуска устройства подают импульсный сигнал единичного уровня. При этом блок 7 вьшода информации выдает число 6, на свой информационный выход (номер ветви первой в списке входящих в началь

„ь,й узел пути) и i-счпульсньй сигнал единичного уровня на выход призна-

„ь,й узел пути) и i-счпульсньй сигнал единичного уровня на выход призна-

ка выдачи слова. При этом блок 9 синхронизации начинает формировать последовательность сигналов в соответствии с временной диаграммой работы (фиг. 2) На выходе 35 появляется импульс единичного уровня. При этом код числа 6 заносится в регистр 13. Через время Т , достаточное для

записи информации в регистр 13, на вькоде 36 блока 7 синхронизации появляется сигнал единугчного уровня. При этом в блок памяти по адресу 6 заносится 1 (начальный узел пути

считается достигнутым, а все входящие в него ветви свершенныг-ш), из блока 5 памяти по-адресу 6 считывается нулевое информационное слово. Через время Х, достаточное для чтения информации из блока 5 памяти, на выходе 37 блока 9 синхронизации появляется сигнал единичного уровня. При этом устанавливается в ноль нулевой канал rai iMep 6 (холостая

3143

операция, так как таймер 6 еще не был занят моделированием ветви). Через время Т, достаточное для установки в ноль канала таймера, на выходе 38 блока 9 синхронизации появляется импульс единичного уровня.При этом устанавливается в ноль регистр

13.После этого на выходе 39 блока

9синхронизации появляется импульс единичного уровня. При этом блок 7 вьшода информации формирует импульс единичного уровня на своем выходе признака конца списка (список ветвей, входящих в третий начальный узел, ис- черпан). При этом блок В вьшода информации вьщает на информационный выход число 2 (номер ветви первой в списке ветвей, выходящих из начального третьего узла), и импульс еди- ничного уровня появляется на выходе признака вьщачи слова. При этом блок

10синхронизации начинает формировать последовательность сигналов в соответствии со своей временной диа- граммой. На выходе 40 блока 10 появляется импульсный сигнал единичного уровня. При этом число 2 заносится

в регистр 14. Через время Tj, достаточное для записи информации в регистр

14,на выходе 41 блока 10 появляется сигнал единичного уровня. При этом из блока 1 памяти считывается ноль (признак того, что ветвь 2 еще не исполнялась). На выходе элемента 27 НЕ появляется сигнал единичного уровня, при этом таймер 6 выдает -на свой выход номера загружаемого канала номер свободного канала, например номер 1,и кроме того, на вькоде блока 2 памяти появляется число 2 (вес ветви 2). Через время TJ, достаточное для чтения информации из блоков I и 2 памяти и выдачи номера свободного канала таймером 6, на выходе 42 блока 10 син- хронизации появляется сигнал единичного уровня. При этом по адресу 2 в блок 5 памяти производится запись числа 1 (по адресу ветви 2 запоминается номер канала таймера 6 заняты ее моделированием), по адресу 1 в

блок 3 памяти производится запись числа 2 (по адресу номера канала занятого моделированием ветви запоминается ее номер), в первьй канал таймера 6 загружается число 2 (вес ветви 2). Через время Tj, достаточное для окончания процессов записи в блоках 5 и 3 памяти и в первом канале таймера 6, на выходе 43 блока 10 синхронизации появляется импульсный сигнал единичного уровня. При этом устанавливается в ноль регистр 14. После этого на выходе 44 блока 10 синхронизации появляется импульс- ный сигнал единичного уровня. При этом на информационном выходе блока В вьшода информации появляется число 3 (номер очередной ветви, выходящей из начального узла пути), на выходе признака вьщачи слова блока В появляется импульсньй сигнал единичного уровня. Далее устройство работает аналогично и на втором и третьем тактах работы блока 10 в. блок 5 памяти по адресам 3 и 4 записаны числа

2и 3 соответственно (номера каналов таймера, занятых исполнением моделированием ветвей 3 и 4, в блок 3 памяти по адресам 2 и 3 будут записаны числа 3 и 4 соответственно (номера ветвей, которые моделирует второй и третий каналы таймера 6), во второй и третий каналы таймера 6 записаны числа 4 и 3 соответственно (веса ветвей 3 и 4). При подаче на вход 44 блока В вьшода информации очяредного тактового импульса он вьщает

на свой выход признака конца списка импульсный сигнал единичного уровня. При этом устанавливается в единицу триггер 1В, таймер 6 и счетчик 17 начинают счет тактовых импульсов. Через 2 тактовых импульса на выходе пррывания таймера 6 появляется сигнал единичного уровня. При этом устанавливается в ноль триггер 1В, таймер 6 и счетчик 17 прекращает счет тактовых импульсов, блок 11 синхронизации начинает формировать последовательность сигналов в соответствии с временной программой (фиг. 3), на выходе номера загружаемого канала таймера 6 появляется код числа 1 (номер канала таймера с высшим приоритетом, первым выставивший прерьшание). Сигнал единичного уровня появляется на выходе 45 блока 11. При этом из блок

3памяти по, адресу 1 считьшается число 2 (номер ветви, исполненной данным каналом). Через время Т, достаточное для окончания чтения из блока 3 памяти, на выходе 46 блока 11 появляется сигнал единичного уровня, при этом из блока 4 памяти по адресу 2 считывается число 2 (номер узла, в который входит исполненная

5

ветвь 2). Через время Tj, достаточное для.окончания операции чтения блока 4 памяти, на выходе 47 блока

11появляется импульсньй сигнал едничного уровня. При этом в регистр

12заносится число 2 (номер достигнутого узла). На выходе 48 блока 1 появляется сигнал единичногр уровн При этом блок 7 вьшода информации вьщает на свой информационный выхо число 1 (номер ветви, стоящей перв в списке исходящих из первого узла графа)

Далее работа устройства проходи аналогично. Под управлением первог блока синхронизации производится запись в блок 1 памяти меток свершения по адресам (номерам) всех вевей, входящих в достигнутый узел, при зтом об,нуля1отся каналы, занятые моделированием этих ветвей и снимаются прерьшания от этих канал если они были. Далее под управлени блока 10 синхронизации свободные и освободившиеся каналы таймера 6 загружаются весами ветвей, исходящих из достигнутого узла и устанавливается в единицу триггер 18. Если в таймере 6 не осталось необработанных прерываний, процесс исполнения ветвей (счет импульсов в таймере 6 и в .счетчике 17) продолжается. В противном случае сигнал прерывания устанавливает триггер 18 в нулевое состояние и запускает блок I1 синхронизации. Работа устройства прекращается, когда будет исполнена первая из ветвей, входяп ая.р конечный узел пути. После того как номер конечного узла пути (в данном случае он равен единице) записан 3 регистр 12, блок 16 сравнения выработает сигнал единичного уровня, которьй остановит блок 11 синхронизации. Работа устройства прекратится. При этом счетчик 17 хранит количество импульсов, численно равное весу кратчайшего пути из начальной в конечную вершину графа.

Формула

изобретения

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

o

5

5

0

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

5

0

0

5

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

5 третьего регистра, к входу признака чтения первого блока памяти, к входу.установки в О третьего регистра и к тактовому входу второго блока вывода информации сортветст-

0 венно, третий выход второго блока

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

40 блока памяти, второму входу второго элемента ИЛИ и к второму входу треть- го элемента ИЛИ соответственно, выход второго элемента ИЛИ подключен к входу признака записи первого ре45 гистра.

Ptie.Z

Фиг.З

Изобретение относится к области вычислительной техникии может быть использовано для определения величины кратчайшего пути в графе, С этой целью устройство содержит пять блоков/ памяти и два блока вывода, с помощью которых задается топология исследуемого графа и отмечается движение по его ветвям (исполнение) верошн.Веса ветвей, исходящих из достигнутой вершины графа, моделируются одновременно при помощи многоканального таймера . Это позволяет определить величину кратчайшего пути в графе за время, пропорциональное весу пути. 4 ил. |

(J

V«

j5/i П)