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

00

j

оо

(

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

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

На фиг. 1 представлена функциональная схема устройства; на фиг. 2 - временная диаграмма работы блока синхронизации; на фиг. 3 - топология графа, на примере которого рассмотре- ijia работа устройства. ; Устройство содержит блок 1 синхро- йизации, первую матрицу из В Р эле- fieHTOB И 2, где В - количество вершин графе, Р - количество ребер в графе, вторую матрицу из В Р элементов 3, первую группу из В элементов ЛИ А, первую группу из В элементов И 5, группу из В последовательных фумматоров 6, вторую группу из В зле- ментов И 7, вторую группу из В элементов ИЛИ 8, третью группу из В элементов И 9, третью группу из В элементов ИЛ1-1 10, четвертую группу из В элементов ИЛИ 11, первую группу из В триггеров 12, вторую группу из В триггеров 13, группу из В ключей 14, группу из В элементов НЕ 15, В групп из Р регистров 16 сдвига.

Для большей наглядности на фиг, 1 первое и второе наборные поля не имеют цифровых обозначений и представлены первой группой В массивов по Р Контактов 17 в каждом массиве первого наборного поля, второй группой из В контактов 18 первого наборного поля,, первой группой из В массивов по Р контактов 19 в каждом массиве второго наборного поля и второй группой из В массивов по Р контактов 20 в каждом массиве второго наборного поля.

Кроме того, на фиг„ 1 цифровые обозначения имеют вход 21 начальной установки устройства, вход 22 пуска устройства, В входов 23 задания начальной вершины графа, В входов 23 задания конечной вершины графа, тактовый выход 25 блока 1 синхронизации, первый выход 26 синхронизации блока 1 синхронизации, второй выход 27 синхронизации блока 1 синхронизации и группа из Р выходов 28 синхронизации блока 1 синхронизации.

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

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

на фиг. 3 (цифры без скобок указывают номера вершин, цифры в круглых скобках - номера ребер, цифры в квадратных скобках - веса соответствующих ребер графа).

Перед началом работы контакты первого и второго наборных полей соединяют согласно топологии графа (первое наборное поле используют для решения задачи определения кратчайшего пути, в графе, второе наборное поле - для индикации вершин кратчайшего пути) . Для графа, топология которого представлена на фиг. 1, первый контакт 18 второй группы первого наборного поля подключают к третьему контакту 17 третьего массива и к второму контакту 17 четвертого массива первой группы первого наборного поля,

третий контакт 18 второй группы первого наборного поля подключают к первому контакту 17 второго массива первой группы первого наборного поля, четвертый контакт 18 второй группы

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

поля подключают к первому контакту 19 третьего массива первой группы второго наборного поля, четвертый контакт 20 второго массива второй группы второго наборного поля подключают кчетверто гу контакту 19 четвертого массива первой группы второго наборного поля, второй контакт 20 четвертого массива второй группы второго наборного поля подключают к второму

контакту 19 первого массива первой группы второго наборного поля (задают ребро 1-4), третий контакт 20 третьего массива второй группы второго наборного поля подключают к третьему

контакту 19 первого массива первой группы второго наборного поля (задают ребро 1-3). В регистры 16 всех групп заносят информацию о весах соответствующих ребер графа. Вес графа

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

Таким образом, в первый регистр 16 будет записано 010 (служебный разряд и дополнительный двоичный код числа 2), во второй регистр 16 - 010 в третий - 011, в четвертый - 001. . На вход начальной установки устройства подают импульсный сигнал единичного уровня. При этом все триггеры 12 и 13 переходят в нулевое состоя- ние, размыкаются исполнительные цепи ключей 14. На первый вход 23 задания начальной вершины графа подают импульсный сигнал единичного уровня. При этом первый триггер 12 переходит в единичное состояние. На второй вхо 24 подают импульсный сигнал единичного уровня. При этом второй ключ 14 замыкает свою исполнительную цепь (задана конечная вершина графа). На вход 22 запуска подают импульсный сигнал единичного уровня. При этом блок 1 синхронизации начинает свою работу. Блок 1 синхронизации вырабатывает импульсы единичного уровня на своем тактовом выходе 25 и выходе 16. При этом во всех регистрах 16 информация сдвигается на один разряд в сторону младших разрядов, информация с выхода сумматоров 6 поразрядно со стороны старших разрядов записывается в В-е регистры всех групп. Через Т импульсов., где Т - разрядност-ь регистров 16, на выходе 27 блока 1-го разряда - 100. По импульсу на выходе 27 блока 1 третий триггер 12 первой группы будет установлен в единицу (исполнено третье ребро графа, достигнута третья вершина графа). Далее процесс протекает аналогично: через В Т тактов осуществляется один такт исполнения ребра графа (сложение кода в регистрах 16 с единицей младшег разряда для всех регистров 16 к младшим разрядам которых, через контакты -17 и 18 первого наборного поля, прибавляется единица с выхода триггера 12).

Одновременно с установкой в едини цу второго триггера 12 первой группы (т.е. при достижении конечной вершины графа) устанавливается в единицу второй триггер 13 второй группы (начинается этап индикации кратчайшего пути). Единичный потенциал с выхода триггера 13 стробируется импульсом с Мо-го выхода 28 блока 1 синхронизации (М 1, ..., В) и распространяется через В Т импульсов с выхода

25 блока 1 черем контакты 19 и 20 второго наборного поля, от одного триггера 13, принадлежащего кратчайшему пути, к другому, устанавливая их в единичное состояние. Выход триггера 13, принадлежащего начальной вершине графа, может быть заведен на вход останова блока 1 синхронизации и 1спользоваться в качестве признака окончания работы устройства.

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

Устройство для анализа параметров графа, содержащее две матрицы из В : Р элементов И, где В - количество вершин в графе, Р - количество ребер в графе, В групп из В регистров сдвига, три группы из В элементов И, четыре группы из В элементов UTOi, две группы из В триггеров, группу из В последовательных су 1маторов, группу из В элементов НЕ, группу из В ключей, два наборных поля и блок синхронизации, вход пуска которого является входом пуска устройства, причем М-й контакт (М 1,... , Р) К-го массива (К 1,..., В), первой группы первого наборного поля подключен к первому входу М-го элемента И К-го столбца первой матрицы, выход которого подключен к М-му входу К-го элемента ИЛИ первой группы, выход которого подключен к первому входу К-го элемента И первой группы, выход которого подключен к входу первого слагаемого К-го последовательного сумматора группы, выход которого подключен к входу старшего разряда В-го регистра сдвига К-й группы, выход младшего разряда Н-го регистра сдвига К-й группы (Н 2,,,, Р) подключен к входу старшего разряда (Н-1)-го регистра сдвига К-й группы, выход младшего разряда первого регистра сдвига К-й группы подключен к входу второго слагаемого К-го последовательного сумматора группы, К-й вход задания начальной вершины графа устройства подключен к первому входу К-го элемента ИЛИ второй группы, выход которого подключен к входу установки в 1 К-го триггера первой группы, выход которого подключен к К-му контакту второй группы первого наборного поля и к входу К-го элемента НЕ группы, выход которого подключен к второму входу К-го элемента И первой группы, М-й

5

контакт К-го массива первой группы второго наборного поля подключен к М-му входу К-го элемента ИЛИ третьей :Группы, выход которого подключен к первому входу К-го элемента ИЛИ четвертой группы, К-й вход задания ко- |нечной вершины графа подключен к управляющему входу К-го ключа группы, выход которого подключен к второму ;Входу К-го элемента ИЛИ четвертой труппы, выход К-го элемента И второй |Группы подключен к первьм входам JBcex элементов И К-го столбца второй |матриды, выход М-го элемента И К-го столбца второй матрицы подключен к |М-му контакту К-го массива второй |группы второго наборного поля, так- |товый выход блока синхронизации под- |Ключен к входам признаков сдвига |вправо всех регистров сдвига всех Iгрупп, первый выход синхронизации I блока синхронизации подключен к тре- 1тьим входам всех элементов И первой I группы, второй выход синхронизации блока синхронизации подключен к пер- ;Вым входам всех элементов И третьей

366

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

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

второму входу К-го элемента ИЛИ второй группы, выход К-го элемента ИЛИ четвёртой группы подключен к входу установ.ки в 1 К-го триггера второй группы, выход которого подключен к первому входу К-го элемента И второй группы, второй вход которого подключен к выходу младшего разряда перво- го регистра сдвига К-й группы, М-й выход синхронизации группы блока синхронизации подключен к вторым входам М-х элементов И всех столбцов первой и второй матриц.

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

Фиг

, -)0SM-к,

I. гtI

JQ

§

tJS 8Q

к, -

CM

Фи.З

(t}