Устройство для анализа параметров графа
Изобретение относится к вычислительной технике и может быть использовано для анализа путей в графе. Цель изобретения - расширение функциональных возможностей устройства за счет определения состава ветвей кратчайшего пути в графе. Устройство содержит матрицу из РхР триггеров 1, где Р - количество вершин в графе, матрицу из РхР счетчиков 2, матрицу из РхР элементов И 3, первую группу
СОЮЗ СОВЕТСНИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК
ы) 4 G 06 F 15/20
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21 ) 4159065/24-24 (22) 10, ) 2,86 (46) 30.06.88. Бюл. Н 24 (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) О.Н.Костюк, В.Б.Брагин и Г.В.Моисеенко (53) 681,333 (088.8) (56) Авторское свидетельство СССР
М 842842, кл. G 06 G 7/122, 1979.
Авторское свидетельство СССР
М 1215116, кл. G 06 F 15/20, 1986.
„„SU„„1406601 А 1 (54 ) УСТРОЙСТВО ДЛЯ АНАЛИЗА ПАРАМЕТРОВ ГРАФА (57) Изобретение относится к вычислительной технике и может быть использовано для анализа путей в графе, Кель изобретения — расширение функциональных возможностей устройства за счет определения состава ветвей кратчайшего пути в графе. Устройство содержит матрицу из РхР триггеров 1> где P — количество вершин в графе, матрицу из РхР счетчиков 2, матрицу из РхР элементов И 3, первую группу
140660 из Р элементов ИЛИ 4, вторую группу из р элементов ИЛИ 5, первую группу иэ Р элементов И 6, вторую группу иэ
P элементов И 7, блок 8 синхронизации, первый регистр 9 ° второй регистр 10, перный дешифратор 11, второй дешифратор 12, элемент ИЛИ 13, Перед началом работы задают информацию о топологии графа. После подачи сигнала на вход пуска блок 8 начинает вырабатынать импульсы единичного уровня. В момент перехода через нуль
К-го счетчика 2 начальной строки матрицы (исполнена ветвь, соединяющая начальную и К-ю вершины графа (К =
1,...,P) на его выходе признака переполнения появляется потенциал, открывающий К-й элемент И 6 (разрешение исполнения всех дуг, выходящих
1 из К-й вершины). Работа устройства продолжается аналогично до тех пор, пока на выходе элемента И 7, номер которого соответствует коду н регистре 10, не появится единичный потенциал (достигнута конечная нершина пути), который поступит на вход соответствующего элемента ИЛИ 5 и с его выхода на вход элементов И 3. Те элементы И 3, которые открыты единичным потенциалом с выхода признака переполнения счетчиков 2, выдают на информационные входы триггеров 1 (относящихся к кратчайшему пути) единичные потенциалы. После подачи сигнала на вход опроса устройства все, триггеры
1, соответствующие ветвям кратчайшего пути, будут установлены в единичное состояние. l ил.
Изобретение относится к вычислительной технике и может быть использовано для анализа путей в графе.
Цель изобретения " расширение функциональных воэможностей устройства путем определения состава ветвей кратчайшего пути в графе, На чертеже представлена функциональная схема устройства.
Устройство содержит матрицу из
РхР триггеров 1, где P " количество вершин в графе, матрицу из РхР счетчиков 2, матрицу из РхР элементов
И 3, первую группу из P элементов
ИЛИ 4, вторую группу из P элементов
ИЛИ 5, первую группу из Р элементов
И 6, вторую группу из Р элементов
И 7, блок 8 синхронизации, первый регистр 9, второй регистр 10, первый дешифратор 1l,второй дешифратор 12 элемент ИЛИ 13.
Устройство работает следующим образом.
Перед началом работы установкой
:в единицу ссотнетствующих триггеров
1 задают информацию о топологии графа,в счетчики 2 заносят информацию о весе пути из К-й в M-ю вершины графа (К=l,...Р; M=1,...P), в регистр 9 заносят код номера начальной
2 вершины графа, в регистр 10 — код номера конечной вершины, После подачи сигнала единичного уровня на вход пуска блока 8 синхронизации последний начинает вырабатывать импульсы единичного уровня,поступающие на вторые входы всех элементов И 6. Код, записанный в регистр
9, определяет номер открытого элемен10 та И 6, с выхода которого импульсы единичного уровня поступают на нычитающие входы всех счетчикон 2 строки матрицы с номером, равным номеру начального узла (начинается исполнение ветвей, исходящих из начальной вершины графа). В момент перехода через нуль К-го счетчика 2 данной строки (исполнена ветвь, соединяющая начальную и К-ю вершину графа) на его выходе признака переполнения появляется потенциал единичного уровня, открывающий К-й элемент И 6 (разрешение исполнения всех дуг, выходящих иэ
К-й вершины) и устанавливающий в нуль все триггеры 1 К-го столбца (запрет исполнения дуг, входящих в
К-ю вершину графа). С выхода К-ro элемента И 6 импульсы блока 8 синхронизации прступают на вычитающие входы всех счетчиков К-й строки матрицы
140660
ВНИИПИ Заказ 3195/45 Тираж 704 Подписное
Ужгород, ул. Проектная, 4
Произв..-полигр. пр-тие, г. исполнение ветвей, исходящих из
К-й вершины графа), Работа устройств ва продолжается аналогично до тех пор, пока на выходе элемента И 7, номер которого соответствует коду в регистре 10, не появится потенциал высокого уровня (достигнута конечная вершина пути), С выхода элемента
ИЛИ 13 потенциал единичного уровня останавливает блок 8 синхронизации.
Кроме того, сигнал единичного уровня с выхода элемента И 7, соответствующего номеру конечной вершины пути, поступает на (Р+1)-й вход соответст- 15 вующего элемента ИЛИ 5, с выхода которого потенциал единичного уровня поступает на вторые входы всех элементов И 3 соответствующего столбца матрицы, Те элементы И 3, которые 2р открыты единичным потенциалом с выхода признака переполнения соответствующих счетчиков 2, выдают на информационные входы триггеров 1 (относящихся к кратчайшему пути) еди- 25 ничные потенциалы и, кроме того, через элементы ИЛИ 5 разрешают выдачу единичных потенциалов на все предшествующие триггеры 1 кратчайшего пути. После подачи единичного потен- 3р циала на вход опроса устройства все триггеры 1, соответствующие ветвям кратчайшего пути, будут установлены в единичное, а не относящиеся к кратчайшему пути — в нулевое состоя35 ние, Количество импульсов,. поступивших с выхода блока 8 синхронизации, будет соответствовать величине кратчайшего пути из начальной в конеч- 4р ную вершины графа.
Формула и з обре т е н и я
Устройство для анализа параметров графа, содержащее матрицу из РхР счетчиков, где Р— количество вер- 4 .шин в графе, матрицу из РхР триггеров, две группы из P элементов И, две группы из P элементов ИЛИ и блок синхронизации, причем выход К-го триггера M-й строки матрицы (К
sp
1,..., Р; М = 1,...,P) подключен к входу разрешения счета К"го счетчика M-й строки матрицы, выход признака переполнения которого подключен
4 к M-му входу К-го элемента ИЛИ первой группы, выход которого подключен к входам установки в 0 всех триггеров К-ro столбца матрицы и к первому входу К-го элемента И первой группы, выход которого подключен к вычитающим входам всех счетчиков К-й строки матрицы, вторые входы всех элементов И первой группы подключены к тактовому входу устройства, вход пуска устройства подключен к входу пуска блока синхронизации, выход которого подключен к вторым входам всех элементов И первой группы, о тл и ч а ю щ е е с я тем, что, с целью расширения функциональных воэможностей устройства путем определения состава ветвей кратчайшего пути в графе, в него введены матрица из
РхР элементов И, два регистра, два дешифратора и элемент ИЛИ, выход которого подключен к входу останова блока синхронизации, причем выход признака переполнения К-ro счетчика
М-ой строки матрицы подключен к первому входу К-го элемента И М-й строки матрицы, выход которого подключен к информационному входу К-го триггера M-й строки матрицы и к К-му входу
M-го элемента ИЛИ второй группы, выход которого подключен к вторым входам всех элементов И M-го столбца матрицы, вход задания номера начальной вершины устройства подключен к установочному входу первого регистра, выход которого подключен к входу первого дешифратора, выход К-ro разряда которого подключен к (Р+1)-му входу К-го элемента ИЛИ первой группы, выход которого подключен к первому входу К-го элемента И второй группы, вход задания номера конечной вершины графа подключен к установочному входу второго регистра, выход которого подключен к входу дешифратора, выход К-ro разряда которого подключен к второму входу К-ro элемента И второй группы, выход которого подключен к К-му входу элемента ИЛИ и к (Р+1)му входу К-го элемента ИЛИ второй группы, вход опроса устройства подключен к входам признаков записи всех триггеров матрицы.
