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

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

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

На фиг. 1 представлена функциональная схема устройства; на фиг. 2 - временная диаграмма работы блока синхронизации: на фиг. 3 - функциональная схема блока определения достижимых вершин.

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

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

Перед началом работы обнуляют накапливающий блок 4 логического сложения, в блок 3 задания матрицы смежности заносят информацию о топологии графа.

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

К

О

ел ( о

если из первой вершины достижимы все остальные вершины графа, на выходе 9 блока 2 появляется сигнал уровня логической единицы. Через время, достаточное для окончания проверки принадлежности вершины массиву истоков, блок 1 синхронизации формирует сигнал уровня логической единицы на выходе 7. При э ом накапливающий блок 4 логического сложения (при наличии сигнала уровня логической единицы на выходе 9) добавляет (по ИЛИ) первую вершину к текущему массиву истоков. Через время, достаточное для окончания операции логического сложения в блоке 4, блок 1 синхронизации снимает сигналы уровня логической единицы с первого выхода 8 и выхода 7 и формирует сигнал уровня логической единицы на втором выходе 8. Далее работа устройства повторяется до тех пор,

Блок 2 определения достижимых вершин работает следующим образом.

На входы 15 блока подается информация о топологии графа. На один из входов 5 14 спроса подают сигнал уровня логической единицы. При этом на выходах 16 блока формируется состав вершин достижимых из опрошенной. Если достижимы все вер шины графа, сигнал уровня логической еди 10 ницы появляется на выходе 9 блока 2.

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

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

пока не будут проверены все вершины гра- 20 М-й выход группы блока синхронизации (М

фа, при этом на выходах 10 устройства будет сформирован массив истоков графа.

Блок 2 определения достижимых вершин содержит матрицу из В х В элементов 25 И 11, где В - количество вершин в графе, группу из В элементов И 12, группу из В элементов ИЛИ 13 и элемент И 14, причем вход 14 опроса М-й вершины блока 2

() подключен к первому входу М-го 30

элемента И группы, выход которого подключен к первым входам всех элементов И 11 М-й строки матрицы, вход 15 признака наличия (К,М)-й дуги блока 2 () подключен к второму входу К-го элемента И 11 35 М-ой строки матрицы, выход которого подключен к М-у входу К-го элемента ИЛИ 13 группы, выход которого является выходом 16 признака достижимости К-й вершины блока 2 и подключен к второму входу М-го 40 элемента И группы и к М-у входу элемента И -14, выход которого является выходом 9 признака достижимости всех вершин графа блока 2.

01

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

Блок 2 определения достижимых вершин работает следующим образом.

На входы 15 блока подается информация о топологии графа. На один из входов 14 спроса подают сигнал уровня логической единицы. При этом на выходах 16 блока формируется состав вершин достижимых из опрошенной. Если достижимы все вершины графа, сигнал уровня логической еди- ницы появляется на выходе 9 блока 2.

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

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

М-й выход группы блока синхронизации (М

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

Фиг.1