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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК 9) О 1) 12 А 4 с 06 ОСУДАРСТВЕННЫЙ КОМИТЕТ СССР О ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ(56) Авторское свидетельство СССР943738, кл. С 06 Р 15/20, 1980.Авторское свидетельство СССР1076909, кл. С 06 Г 15/20, 1982. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ПУТЕЙ В ГРАФАХ(57) Изобретение относится к области вычислительной техники и может быть применено .при исследовании параметров сетевых графов, Цель изобретения состоит в расширении функциональных возможностей за счет определения минимального критического пути. Устрой ство содержит матрицу и+ и формирователей дуг, каждый из которых состоит из триггера и элемента И-ИЛИ, группуэлементов ИЛИ, первую группу блоковэлементов И, Г 1)уппу элементов задержки, группу регйстров, группу блоковэлементов И-ИЛИ, вторую группу блоков элементов Й, третью группу блоков элементов И, первую группу элементов И, группу триггеров, вторуюгруппу элементов И, сумматор, блокэлементов ИЛИ, узел выбора максимапь.ного кода, блок элементов И-ИЛИ, генератор импульсов, первый элемент И,вычитающий счетчик, первый дешифратор, второй элемент И, суммирующийсчетчик, второй дешифратор, третийдешйфратор, пусковой вход устройства,вход управлений режимами работы устройства. Расширение функциональныхвозможностей дбстигается за счет определения веса и вершин минимальногокритического пути. 1 ил.40 1 12281Изобретение относится к вычислигельной технике и может быть испольювано при исследовании параметров:етевых графов, а также при аппарат,юй реализации в специализированныхлроцессорах макрокоманды определения.максимальных или минимальных критических путей в графах.Цель изобретения - расширениеФункциональных возможностей за счетопределения минимального критического пути.На чертеже представлена функционадьная схема предлагаемого устройства. 15Устройство содержит матрицу .1ии (и - число вершин графа) формирователей дуг, каждый из которых вклю.чает в себя триггер 2 и элементИ-ИЛИ 3, группу элементов ИЛИ 4, первую группу блоков элементов И 5,группу элементов б задержки, группурегистров 7, группу блоков элементовИ-ИЛИ 8, вторую группу блоков элементов И 9, третью группу блоков элементов И 1 О, первую группу элементовИ 11, группу триггеров 12, вторуюгруппу элементов И 13, сумматор 14,блок элементов ИЛИ 15, узел 16 выбора максимального кода, блок элементов И-ИЛИ 17, генератор 18 импульсов, первьй элемент И 19, вычитающийсчетчик 20, первый дешифратор 21,второй элемент И 22, суммирующийсчетчик 23, второй дешифратор 24,третий дешифратор 25, пусковой вход352 б устройства, вход 27 задания режима, работы устройства.Узел 16 осуществляет выбор кодамаксимального числа из поступающихна входы кодов чисел и выдает на выход числа прямой и обратный кодымаксимального числа, на разрядныйвыход - позиционный код, в которомединичный сигнал присутствует на по 45зиции, соответствующей номеру входа,по которому подано максимальное число.Первоначально в матрицу 1 заносит.ся информация о топологии моделируемого графа. При этом триггеры 2,50моделирующие ветви графа, устанавливаются в единичное состояние. Соответствующий триггер 2 определяетсяпересечением строки с номером, равным номеру начального узла модели 55руемой ветви, и столбца с номером,равным номеру ее конечного узла. Врегистры 7 заносятся коды чисел, со 12 3ответствующие весам вершин. В счетчик 20 заносится код числа и вершин ,графа, счетчик 23 находится в нулевом состоянии. При этом исходная информация о графе заносится в модель в порядке, при котором наименьший номер (первый) имеет начальная вершина, а наибольший - конечная вершина, В единичное состояние устанавливается также триггер 12 соответствующий начальной вершине. На вход 27 подается нулевой сигнал, если отыскивается максимальный критический нуль, или единичный сигнал, если отыскивается минимальный критический нуль. Такое занесение исходной информации о графе позволяет использовать процедуру динамического программирования.Устройство работает следующим образом.С кодового выхода счетчика 20 код поступает на вход дешифратора 21, в результате чего на одном из его выходов (вначале на и-м) появит ся высокий потенциал. В случае, если триггеры 2 в даннойстроке находятся в единичном состоянии, через соответствующие элементы И-ИЛИ 3 и ИЛИ 4 высокий потенциал с выходов этих триггеров подается на входы соответствующих элементов И 10, что в свою очередь обеспечивает подачу кодов через блок элементов И-ИЛИ 8 с регистров 7 на входы узла 16. Узел 16 обеспечивает выбор из поступивших на его вход кодов максимального и выдачу его через блок 17 в прямом или обратном коде (в зависимости от возбужденной выходной шины дешифратора 25) на второй вход сумматора 14. Одновременно на первый вход сумматора 14 подается прямой или обратный код с выхода регистра 7 через соответствующие элементы И-ИЛИ 8, И 9 и ИЛИ 15. Результат с выхода сумматора 14 через открытый блок элементов И 5 (к этому моменту времени на входе блока элементов И 5 появится высокий потенциал с выхода элемента 6 задержки) поступит на вход регистра 7, На этом этап формирования кода максимального (или минимального) пути для и-й отдельной вершины заканчивается.С появлением пускового сигнала на входе 26 устройства элемент И 19 обес печивает прохождение импульсов с выхода генератора 18 на вход счетчика 20, так как на втором входе эле35 50 э 1228 мента И 19 будет высокий потенциал с выхода счетчика 20, на котором появляется обратный сигнал его нулевого состояния. Когда на вход счетчика 20 поступает первый импульс, возбуждается (п - 1)-й выход дешифратора 21, и процесс формирования величины критического пути для очередной вершины графа будет происходить аналогично.Вычислительный процесс будет продолжаться до тех пор, пока на счетчике 20 не появится нулевой код, после чего появится нулевой код и появится низкий потенциал на втором входе элемента И.19, а подача импульсов на15 вход счетчика 20 прекращается. Одновременно высокий потенциал с выхода счетчика 20 обеспечивает выдачу сигналов с выхода генератора 18 через элемент И 22 на вход счетчика 23 со 20 ответственно состояниям которого единичные игналы поочередно появляются на выходах дешифратора 24. Если тот или иной триггер 12 находится в единичном состоянии, то высокий потенци 25 ал с его выхода через одноименный элемент И 13 будет поступать на входы элементов И-ИЛИ 3 одноименнойстроки матрицы 1 и далее через элементы ИЛИ 4 на те входы элементов И 10, которым в данной строке матри 30 цы 1 соответствует дуга графа, т.е. единичное состояние триггера 2. Наличие высоких потенциалов на входах элементов И 10 обеспечивает поступление прямых или обратных кодов, в зависимости от сигнала на входе 27 и выходе дешифратора 25, с выходов регистров 7.через соответствующие блоки элементов И-ИЛИ 8, И 1 О на входы узла 16, который обеспечивает 40 выбор максимального кода из поступивших кодов, при этом соответствующие триггеры 12 перебрасываются в единичное состояние импульсом, проходящим через одноименный элемент 45 И 11, и т.д.Процесс поиска максимального (или минимального) критического пути заканчивается при достижении показания счетчика 23 значения и числа вершин. Единичное состояние триггеров 12 указывает вершины искомого пути, а показания регистров 7 - величины критических путей из соответствующих вершин до и-й вершины графа. 55 Формула изо брет енияУстройство для исследования путей в графах, содержащее матрицу п . и 112 4(и - число вершин графа) формирователей дуг, состоящих каждый из триггера и элемента И-ИЛИ, группу элементов ИЛИ, группу элементов задержки, первую, вторую и третью группы блоков элементов И, группу триггеров, группу регистров, блок элементов ИЛИ сумматор, узел выбора максимального кода, две группы элементов И, два элемента И, генератор импульсов, суммирующий и вычитающий счетчики, два дешифратора, причем в каждом формирователе дуги выход триггера соединен с первым входом элемента И-ИЛИ, выход генератора импульсов подключен к первым входам первого и второго элементов И, выход первого элемента И соединен с входом вычи-. тающего счетчика, инверсный и прямой выходы нулевого состояния которого подключены к вторым входам первого и второго элементов И и первым входам элементов И первой группы, информационный выход вычитающего счетчика соединен с входом первого дешифратора 1-й (1.=1,п) выход которого подключен к вторым входам элементов И-ИЛИ формирователей дуг х-й строки матрицы, входу -го элемента задержки и первому входу -го блока элементов И второй группы, выход которого соединен с 1-м входом блока элементов ИЛИ, выход которого подключен к первому входу сумматора, выход которого соединен с первыми входами блоков элементов И первой грппы, вторые входы которых подключены к выходам соответствующих элементов задержки группы, а выходы - к входам соответствующих регистров группы, третий вход первого элемента И является пусковым входом" устройства, выходы элементов И-ИЛИ формирователей дуг каждого столбца матриц соединены с входами соответствующего элемента ИЛИ группы, выход которого подключен к первому входу соответствующего блока элементов И третьей группы, выход которого соединен с соответствующим входом узла выбора максимального кода, выходы выдачи позиционного кода которого подключены к первым входам соответствующих элементов И первой группы, выходы которых соединены с входами триггеров группы, выходы которых подключены к первым входам соответствующих элементов И второй группы, выходы которых соединены с третьими входами элементов И-ИЛИ фор.1228112 ставитель А.Шеоенковхред И.Попович ктор И. Самборска Редактор 1 О а Тираж 671 ИИПИ Государственн по делам изобрете 3035) Москва, 3-35 Подписмитета СССРоткрытийская наб., д. 4/5 Заказ 2288/50В о к й и ау роиэводственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4. мирователей дуг соответствующих строкматрицы, вьход второго элемента Иподключен к входу суммирующего счетчика, выход которого соединен с входом второго дешифратора, выходы которого соединены с вторыми входами соответствующих элементов И второйгруппы, о т л и ч а ю щ е е с я тем,что, с целью расширения функциональных возможностей за счет определенияминимального критического пути, вустройство введены группа блоков эле.ментов И-ИЛИ, блок элементов И-ИЛИи третий дешифратор, вход которогоявляется входом задания режима работы устройства, причем выход каждогоблока элементов И-ИЛИ соединен с вто. рыми входами соответствующих блоков элементов И второй и третьей групп, выход блока элементов И-ИЛИ подключен к второму входу сумматора, выход кода максимального числа блока выбора максимального кода соединен с первым входом .блока элементов И-ИЛИ, выход прямого кода числа каждого 1 О регистра группы подключен к первому,а выход обратного кода числак второму входу соответствующего блока элементов И-ИЛИ группы, первый и втоАрой выходы третьего дешифратора со единены соответственно с третьими ичетвертыми входами блока элементов И-ИЛИ и блоков элементов И-ИЛИ груп