Устройство для анализа параметров графа

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51) 4 С 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ASTOPCHOIVlV СВИДЕТЕЛЬСТВУ

Ъ»

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4183153/ 24-24 (22) 22.01.87 (46) 23.08.88. Бюл. N 31 (71) Институт проблем моделирования в энергетике AH УССР (72) В.В.Васильев и В.Л.Баранов (53) 681.333 (088.8) (56) Авторское свидетельство СССР

Ф 805300, кл., G 06 Р 15/20, 1978.

Авторское свидетельство СССР

Ф 1246110, кл. С 06 F 15/20, 1984. (54) УСТРОЙСТВО ДЛЯ АНАЛИЗА ПАРАИЕТР0В ГРАФА (57) Изобретение относится к вычислительной технике, может быть использо„.SU„„1418736 А1 вано для исследования кратчайчих путей в графе. В состав устройства введены В групп из P регистров сдвига, где  — количество вершин в графе, P — количество ребер в графе. Перед началом работы информация о весе ребер графа заносится в регистры сдвига всех групп, а топология графа задается коммутацией соответствующих контактов первого и второго наборных полей. После пуска устройство последовательно решает задачу отыскания кратчайшего пути, используя для этой цели служебные (старшие) разряды регистров сдвига. Этим достигается сокращение аппаратурных затрат. 3 ил.

f418736

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

27 синхронизации блока 1 синхронизации и группа из P выходов 28 синхронизации блока 1 синхронизации.

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

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

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

На фиг. представлена функциональная схема устройства; на фиг. 2 — 10 временная диаграмма работы блока синхронизации; на фиг. 3 — топология графа, на примере которого рассмотрена работа устройства.

Устройство содержит блок 1 синхро- 1В йизации, первую матрицу из В P элементов И 2, где  — количество вершин графе, Р— количество ребер в графе, вторую матрицу из В . P элементов

И 3, первую группу из В элементов 20

ЯЛИ 4, первую группу из В элементов

И 5, группу из В последовательных

Сумматоров 6, вторую группу из В э ементов И 7, вторую группу из В элементов ИЛИ 8, третью группу из В элементов И 9, третью группу из В элементов ИЛИ 10, четвертую группу из

В элементов ИЛИ 11, первую группу из

В триггеров 12, вторую группу из В триггеров 13, группу из В ключей 14, 30 группу из В элементов НЕ 15, В групп из Р регистров 16 сдвига.

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

В контактов 18 первогонаборного поля, первой группой из В массивов по Р 4п контактов 19 в каждоммассиве второго наборного поля и второй группой из

В массивов по P контактов 20 в каждом массиве второго наборного поля„

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

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

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

16 используются как служебные (здесь формируется признак исполнения ребра) и перед началом работы обнуляются.! i!87736

Таким образом, в первый регистр

16 будет записано 010 (служебный разряд и дополнительный двоичный код числа 2), во второй регистр 16 — 010, в третий — 011, в четвертый — 001..

На вход начальной установки устройства подают импульсный сигнал единичного уровня. При этом все триггеры

12 и 13 переходят в нулевое состояние, размыкаются исполнительные цепи ключей 14. На первый вход 23 задания начальной вершины графа подают импульсный сигнал единичного уровня.

При этом первый триггер 12 переходит 15 в единичное состояние. На второй вход

24 подают импульсный сигнал единичного уровня. При этом второй ключ 14 замыкает свою исполнительную цепь (задана конечная вершина графа). На Zp вход 22 запуска подают импульсный сигнал единичного уровня. При этом блок 1 синхронизации начинает свою работу. Блок 1 синхронизации вырабатывает импульсы единичного уровня 25 на своем тактовом выходе 25 и выходе

16. При этом во всех регистрах 16 информация сдвигается на один разряд в сторону младших разрядов, информация с выхода сумматоров 6 поразрядно со 30 стороны старших разрядов записывается в В-е регистры всех групп. Через

Т импульсов, где Т вЂ” разрядность регистров 16, на выходе 27 блока 1-ro разряда — 100, По импульсу на выходе

27 блока 1 третий триггер 12 первой группы будет установлен в единицу (исполнено третье ребро графа, достигнута третья вершина графа). Далее процесс протекает аналогично: через 40

В Т тактов осуществляется один такт исполнения ребра графа (сложение кода в регистрах 16 с единицей младшего разряда для всех регистров 16 к младшим разрядам которых, через контакты .17 и 18 первого наборного поля, прибавляется единица с выхода триггера 12).

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

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

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

Устройство для анализа параметров графа, содержащее две матрицы из В "

< Р элементов И, где  — количество вершин в графе, P — количество ребер в графе, В групп из В регистров сдвига, три группы из В элементов И, четыре группы из В элементов ИЛИ, две группы из В триггеров, группу из В последовательных сумматоров, группу из В элементов HF. группу из В ключей, два наборных поля и блок синхронизации, вход пуска которого является входом пуска устройства, причем

М-й контакт (М = 1,..., P) К-ro массива (К = 1,.. °, В). первой группы первого наборного поля подключен к первому входу М-ro элемента И К-го столбца первой матрицы, выход которого подключен к М-му входу К-го элемента ИЛИ первой группы, выход которого подключен к первому входу К-го элемента И первой группы. выход которого подключен к входу первого слагаемого К-го последовательного сумматора группы, выход которого подключен к входу старшего разряда В-го регистра сдвига К-й группы, выход младшего разряда Н-го регистра сдвига К-й группы (Н = 2..., P) подключен к входу старшего разряда (Н-1)-го регистра сдвига К-й группы, выход младшего разряда первого регистра сдвига К-й группы подключен к входу второго слагаемого К-ro последовательного сумматора группы, К-й вход задания начальной вершины графа устройства подключен к первому входу К-го элемента ИЛИ второй группы, выход которого подключен к входу установки в 11 К-го триггера первой группы, выход которого подключен к К-му контакту второй группь| первого наборного поля и к входу К-го элемента НЕ группы, выход которого подключен к второму входу

К-ro элемента И первой группы, М-й

5 1 контакт К-го массива первой группы второго наборного поля подключен к

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

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

:блока синхронизации подключен к третьим входам всех элементов И первой

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

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

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

К-го последовательного сумматора группы подключен к второму входу

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

rO первому входу К-го элемента И второй группы, второй вход которого подключен к выходу младшего разряда первого регистра сдвига К-й группы, M-й выход синхронизации группы блока син25 хронизации подключен к вторым входам

M-х элементов И всех столбцов первой и второй матриц.

Фмй!

1418736

14! 8736

Составитель А.Мишин

Редактор Г.Волкова Техред А.Кравчук

Корректор И.Васильева

Закаэ 4155/47 Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам иэобретений и открытий

1 13035, Москва, Ж-35, Раушская наб., д. 4/5

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