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

(и)943738 Союз СоветскихСоциалистическихРеспублик ОП ИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(23)Приоритет Ъеударстевней квинтет СССР до делам нзобретеннк н атнрмтнйДата опубликования описания 18,07.82(54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ПУТЕЙ В ГРАФАХ1Изобретение относится к вычислительной технике и может быть использованопри исследовании параметров сетевых графов, а также при аппаратной реализациив специализированных процессорах макрокоманды определения максимальных вели5чнн путей в графах,Известно устройство для определенияэкстремальных путей в графах, содержащеематричную модель графа, генератор, устройство управления и по количеству столбцов матрицы элементы ИЛИ, элементы И,дополнительные элементы И и триггеры..Устройство определяет минимальный путьв исследуемом графе 115Недостатками устройства являются невозможность определить ранние и поздниемоменты наступления событий и низкоебыстродействие при определении минимального пути. 20Наиболее близким техническим решением к изобретению является устройство дляопределения минимальных путей в графах,содержащее матрицу ( Ии ) триггеров 2формирования дуг графа, генератор тактовых импульсов, выход которого соединен с первым входом элемента И, второй вход которого является входом в устройство. Кроме того, устройство содержит счетчики весов дуг, элементы И и регистрируюшие счетчики ДНедостатком данна о устройства является его низкое быстродействие, которое особенно очевидно при определении максимальных величин путей в графах, дугам которых соответствуют коды сравнительно больших чисел. Быстродействие подобных устройств обратно пропорционально величине максимального пути в моделируемом графе.Целью изобретения является повышение быстродействия устройства.Поставленная цель достигается тем, что в устройство, содержашее матрицух П ) триггеров формирования дуг графа и генератор тактовых импульсов, выход которого соединен с первым входом элемента И, второй вход которого3 94373 является входом в устройство, введены по числу триггеров формирования дуг элементы И дуг, по числу столбцов матрицы элементы ИЛИ, элементы задержки, регистры, первые, вторые и третьи группы элементов И, группа элементов ИЛИ, многовходовый сумматор, узел выбора максимума, дешифратор, элемент НЕ и реверсивный счетчик, вход которого подключен к выходу элемента И, третий вход 1 э которого через элемент НЕ подключен к выходу устройства и к выходу реверсивного счетчика, выход которого соединен с входом дешифратора, 4 -ый ( 4 = 1, 2 П ), выход которого подключен через элемент задержки к управляющему входу элемента И первой группы-го столбца, к управляющему входу элемента И третьей группы-го столбца и к первым входам элементов И дуг 1 -ой строки, выход каждого триггера формирования дуги соединен с вторым входом элемента И дуги, выход каждого из которых подключен к входу элемента ИЛИ одновременно, 1 -го столбца, выход которого соединен с управляющим входомФэлемента И второй группы 1 -го столбца, выход которого подключен к соответст вуюшему входу узла выбора максимума, выход которого соединен с первым входом многовходового сумматора, выход которого подключен к информационным входам элементов И первой группы, выход элемента И первой группы 1 -ого столбца соединен с входом регистра 1 -ого столбца, выход которого подключен к информационному входу элемента И второй группы 1 -ого столбца и к информационному входу элемента И третьей группы.-ого столбца, выходы элементов И третьей группы соединены соответствен 49 но со входами элементов ИЛИ группы, выходы которых подключены к второму входу многовходового сумматора.На фиг. 1 представлена структурная схема устройства; на фиг, 2 - узел вы 45 бора максимума.Устройство содержит (фиг. 1) матрицу 1 однородных ячеек размером П х П где П - максимальное число узлов модулируемого графа, включающую триггеры форф .мирования дуг 2 и элементы И 3 дуг.Кроме того, устройство содержит по чис- лу столбцов матрицы элементы ИЛИ 4, первую группу элементов И 5, элемент задержки 6, регистр 7, вторую 8 и тре тью 9 группу элементов И, группы элементов ИЛИ 10, сумматор 11, генератор тактовых импульсов 13, элемент И 13,8 4элемент НЕ 14, реверснвный счетчик 15,дешифратор 16, узел выбора максимума17, вход устройства 18 и выход устройства 19,Узел 17 выбора максимума (см.фпг. 2)содержит выходные элементы ИЛИ-НЕ 2020 20;, поразрядные 21, 21,, 21, группы элементов И и ИЛИ21, 22,2 22, состоящие из элемейтов ИЛИ 23 и элементов И 24, входные шины 25 д, 25,д, , 25 п, выходные шины 26, 26 26 и 271,27 27 п.Устройство работает следующим образом.Первоначально в матрицу 1 заноситсяинформация о топологии моделируемогографа (сети). При этом триггеры 2, моделирующие ветви графа, устанавливаются в единичное состояние. Соответствующий триггер 2 определяется пересечениемстроки с номером, равным номеру конечного узла моделируемой ветви, и столбцас номером, равным номеру ее начальногоузла. В регистры 7 заносятся коды чисел,соответствующие весам вершин. Информация о графе заносится в модель в обычном порядке, при котором наименьший номер (первый) имеет начальная вершина,а наибольший - конечная вершина.В счетчик 15 заносится код числавершин. Такое занесение исходной информации о графе позволяет использоватьдля расчета максимальных путей процедуру динамического программирования (см.ниже пример),С появлением пускового сигнала навходе 18 устройства элемент И 13 обеспечивает прохождение счетных импульсовс выхода генератора 12 на вход счетчика 15 (так как на втором управляемомвходе элемента И 13 будет высокий потенциал с выхода элемента НЕ 14, входкоторого подключен к второму выходусчетчика 15 выхода, на котором появляется сигнал нулевого состояния счетчика 15).С первого выхода счетчика код поступает на вход дешифратора 16, в результате чего на одном из выходов дешифратара 15 появляется высокий потенциал,Появление высокого потенциала на одномиз выходов дешифратора обеспечивает подачу высокого потенциала на управялемыевходы соответствующего столбца элементов И 9 и элементов задержки 6, а также элементов И 3 одноименной строкиматрицы 1. В случае, если триггеры 2в данной строке находятся в единичном9437 38 5состоянии, то через элементы И 3 иИЛИ 4 высокий потенциал с этих триггеров 2 подается на управляемые входысоответствующих элементов И 8, что всвою очередь обеспечивает подачу кодовс регистров 7 на входы узла 17, Узел17 обеспечивает выбор из поступившихна ее вход кодов максимального числа иподачу его на первый вход сумматора 11.Одновременно, на второй вход. сумматора 1011 подается код с выбранного регистра7 через соответствующий элемент И 9и группу элементов ИЛИ 10. Результатс сумматора 11 через открытую группуэлементов И 5 (к этому моменту времени на управляемом входе элементов И 5будет высокийпотенциал с выхода элемента задержки 6) поступает на входрегистра 7. На этом этап формированиякода максимального пути для одной очдельной вершины заканчивается. На входсчетчика 15 поступает очередной импульс,в результате чего содержимое счетчика15 уменьшается на единицу, поэтому навыходе дешифратора 16 возбуждается 2 Зочередная шина и процесс формированиявеличины максимального пути для очередной вершины графа происходит аналогично.Вычислительный процесс продолжаетсядо тех пор, пока, на счетчике 15 не по- зоявляется нулевой код, в результате чегопоявляется высокий потенциал на выходеустройства 19 и входе элемента НЕ 14.Следовательно, на выходе элемента НЕ 14будет нулевой потенциал, после чего пре- Зкращается подача счетных импульсов свыхода генератора 12.Узел выбора максимума 17 работаетследующим образом,На входные шины 25 узла 17 поступаеет П чисел, каждое из которых представлено щ разрядами, с выходов регистров 7через группы элементов И 8. В первыймомент анализируются старшие разряды.Если хотя бы один иэ старших разрядовчисел равен 1, то на выходе 26, (встаршем разряде) формируется О, который вырабатывает сигнал запрета длякаждого иэ чисел. При этом, если стар 1ший разряд-го числа равен О, то все1 -ые числа не проходят через элементы И-ой группы первого узла переноса.Если старший разряд-го числа равен 1,то 1 -ое число проходит через элементыИ 4 -ой группы первого поразрядногоузла переноса.Если старшие разряды всех чисел равны О, то на выходе элемента ИЛИ-НЕ 26формируется 1, которая дает разрешение на прохождение всех Н чисел через элементы И первого поразрядного узла гереноса 21 . Таким образом, на выходе элементов И 24 группы 22 формируются прямые коды чисел, начиная со второго по щ -ый. Вторым элементом ИЛИ-НЕ 26 совместно с элементами ИЛИ 23 поразрядного узла переноса 21 анализируются вторые по старшинству разряды Н чисел таким же образом, как и страших разрядов.На выходе элемента ИЛИ-НЕ 26 формируется второй по старшинству разряд экстремального числа, а на выходах элементов И 24 формируются коды чисел, на чиная с третьего разряда по В -ый и т,д.Таким образом, на элементах ИЛИ-НЕ 26 формируется обратный код экстремального числа. Позиционный код номера экс ь. ремального числа получается путем совпа дения всех Н сигналов запрета, сформированных в каждом 1 -ом поразрядном узле переноса. При сигналах запрета, равным 1, на выходе комбинационной схемы формируется также позиционный код с 1 в разряде, соответствующем экстремальному коду.Работа устройства при определении наиболее ранних моментов нас тупления событий идентична работе устройства при определении величин максимальных путей для всех вершин в графе. Разница лишь в том, что матрица смежности графа заносится в матричную модель сети с предварительным транспортированием относительно главной диагонали матрицы.Таким образом, предлагаемое устройство за счет введения дополнительных элементов с новыми связями обеспечивает существенное повышение быстродейсъвия по сравнению с известным. Быстро действие предлагаемого устройства зависит только от числа й вершин в графе и не зависит от величины кодов длительности вершин графа. Формула изобретения Устройство для исследования путей в графах, содержащее матрицу Н,х П триг- геров формирования дуг графа и генератор тактовых импульсов, выход которого соединен с первым входом элемента И, второй вход которого является входом устройства, о т л и ч а ю ш е е с я тем, что, с целью повышения быстродей ствия, в него введены по числу триггеров формирования дуг элементы И дуг,7 9437 по числу столбцов матрицы элементы ИЛИ, элементы задержки, регистры, первые, вторые и третьи группы элементов И, группа элементов ИЛИ, многовходовой сумматор, узел выбора максимума, дешиф-ратор, элемент НЕ и реверсивный счетчик, вход которого подключен к выходу элемента И, третий вход которого через элемент НЕ подключен к выходу устройства и к выходу реверсивного счетчика, 1 О выход которого соединен с входом дешифратора,-ый (= 1, 2 П ), выход которого подключен через элемент задержки к управляющему входу элемента И перФвой группы-го столбца, к управляюще-му входу элемента И 1 -го столбца и к первым входам элементов И дуг 1 -й строки, выход каждого триггера формирования дуги соединен с вторым входом элемента И дуги, выход каждого из кото- о рых подключен к входу элемента ИЛИ одноименного-го столбца, выход которого соединен с управляющим входом элемента И второй группы 1 -го столбца,38 8выход которого подключен к соответствующему входу узла выбора максимума,выход которого соединен с первым входом многовходового сумматора, выходкоторого подключен к информационнымвходам элементов И первой группы, выход элемента И первой группы 1 -гостолбца соединен с входом регистра 1-гостолбца, выход которого подключен к информационному входу элемента И второйгруппы-го столбца и к информационному входу элемента И третьей группы-го столбца, выходы элементов И третьей группы соединены соответственнос входами элементов ИЛИ группы, выходы которых подключены к второму входумноговходового сумматора,Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССР640314,кл.Ц 06 С 7/122, 1978.2. Авторское свидетельство СССРпо заявке2587569/18-24,кл С 06 Р 15/20, 1978 (прототип).