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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскикСоциалистическихРеспублик рн 947869(22) Заявлено 201180 (21)3007322/18-24с присоединением заявки Мо(31) М. Кл. С 06 Р, 15/20 Государственный комитет СССР но леяам изобретений н открытийОпубликовано 300782. Бюллетень Мо 28 Дата опубликования описания 30,07.82 72) Авторыизобретения В.А, Тит П. Афанасьев и А.С,) Заявитель(54) уС ТВО ДЛЯ ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНЫ ПУТЕЙ В ГРАФАХ 2 2 Изобретение относится к вычислительной технике и может быть использовано при исследовании параметров сетевых графов.Задача определения максимального критического пути в графе заключается в определении значения величины и идентификации вершин, образутощих этот путь.Известно устройство для определения максимального критического пути в графе, содержащее генератор тактовых импульсов, выход которого подключен к входу первого элемента И, управляемый вход которого подключен к выходу элемента НЕ,.вход которого подключен к выходу второго элемента И по числу строк и столбцов матричной модели графа цепочки иэ последовательно соединенных счетчика и триггера, по числу столбцов матрич ной модели графа группы элементов И, дополнительные элементы НЕ, первые и вторые группы элементов И, дополнительные счетчики, входы каждого иэ которых подключены к выходу элемента И второй группы, управляемый вход которого подключен к выходу дополнительного элемента НЕ, выходы триггеров одноименного столбца матричной модели графа подключены к соответствующим входам группы элементов И, выход которой подключен к входу дополнительного элемента НЕ и управляемому входу элемента И первой группы, выход которого подключен к соответствующему входу второго элемента И и входам счетчиков одноименной строки матричной модели графа, информационные входы первых и вторых элементов И группы подключены к выходу первого элемента И 11Недостатками данного устройства являются необходимость перехода от графа с нагруженными вершинами к графу с нагруженными дугами, ниа - кое быстродействие, так как определение максимального критического пути в известном устройстве осуществ ляется последовательно в три этапа, первые два из которых связаны с занесением исходной информации о топо%логии и т твесов т дуг моделируемого графа и подсчета импульсов в счетчиках весов дуг, а третий этап - с сравнением результатов двух подсчетов в схемах сравнения.Наиболее близким к предлагаемому является устройство для определения максимальных путей в графах, в сос 9478 б 9тав которого входят триггеры по числу строк и столбцов матричной модели, генератор тактовых импульсов, элемент ИЛИ, первый элемент И, по числу столбцов матричной модели сети первые элементы И, счетчики фвесов вершин, триггеры управления, вторые элементы И, регистрирующие счетчики, по числу строк матричной модели сети элементы ИЛИ-НЕ, выходы которых подсоединены к управляющим 10 входам одноименных первых элементов И, выходы которых соединены с входами одноименных счетчиков фвесов вершин, выходы которых подсоединены к установочным входам триг геров одноименных столбцов матрицы и к входам одноименных триггеров управления, выходы которых соединены с управляющими входами одноименных вторых элементов И и с входами элемента ИЛИ, выход которого подсоединен к первому входу первого элемента И, выход которого соединен с информационными входами первых и вторых элементов И, выход генератора тактовых импульсов подсоединен к второму входу первого элемента И 2) .Цель изобретения - расширение функциональных возможностей за счет идентификации вершин, образующих максимальный критический путь и повышение быстродействия. Поставленная цель достигается тем, что в устройство для определения максимальных путей в графах, 35 содержащее триггеры по числу строк и столбцов матричной модели графа, группу элементов ИЛИ-НЕ по числу строк матричной модели графа, первуюгруппу элементов И по числу столб в 40 цов матричной модели графа, группу счетчиков весами вершины по числу столбцов матричной модели графа, группу триггеров управления по числу столбцов матричноЙ модели графа, вторую группу элементов И по числу столбцов матричной модели графа, элемент ИЛИ, первый элемент И, генератор тактовых импульсов, причем выходы триггеров одноименной строки матричной модели графа подключены к входам элемента ИЛИ-НЕ группы одноименной строки, выход каждого из которых соединен с управляющим входом элемента И первой группы одноименного столбца, выход которого через счетчик веса вершины группы одноименного столбца подключен к установочным входам триггеров одноименного столбца матричной модели графа и к входу триггера управления ОО группы одноименного столбца, выход которого соединен с управляющим входом элемента И второй группы одноименного столбца и с соответствующим входом элемента ИЛИ, выход 65 которого подключен к первому входу первого элемента И, выход которого соединен с информационными входами элементов И первой и второй групп, выход генератора тактовых импульсов подключен к второму входу первого элемента И, введены второй элемент И, блок выбора кода максимального числа, дополнительный счетчик, дешифратор, элементы И по числу строк и столбцов матричной модели графа, третья группа элементов И по числу столбцов матричной модели сети, группа элементов ИЛИ по числу столбцов матричной модели графа, группа регистрирующих триггеров по числу столбцов матричной модели графа и четвертая группа элементов И по числу столбцов матричной модели графа, выход каждого элемента И четвертой группы одноименного столбца подключен к первым входам элементов И одноименной строки матричной модели графа, выходы элементов И одноименного столбца матричной модели графа соединены с входами элемента,ИЛИ группы одноименного столбца, выход которого подключен к управляющему входу элемента И третьей группы одноименного столбца, информационный вход которого соединен с выходом регистрирующего счетчика группы одноименного столбца, выходы элементов И третьей группы подключены к соответствующим входам блока выбора кода максимального числа, выходы которого соединены с входами регистрирующих триггеров группы соответственно, выход каждого из которых подключен к информационному входу элемента И четвертой группы одноименного столбца, управляемый вход которого соединен с соответствующим выходом дешифратора, вход которого подключен к выходу дополнительного счетчика, выход генератора тактовых импульсов соединен с информационным входом второго элемента И, выход которого подкпючен к входу дополнительного счетчика, выходкаждого триггера матричной модели графа соединен с вторым входом элемента И матрицы.На фиг.1 показана структурная схема предлагаемого устройства; на фиг,2 - блок выбора кода максимального числа.Устройство (фиг,1) содержит матричную модель 1 графа, по числу строк и столбцов матричной модели графа триггеры 2, по числу строк и столбцов матричной модели графа элементы И 3, по числу столбцов матричной модели графа группу элементов ИЛИ-НЕ 4, группу элементов ИЛИ 5 по числу столбцов матричной модели графа, первую группу элементов И 6по числу столбцов матричной моделиграфа, группу счетчиков веса7 вершины по числу столбцов матричной модели графа, группу триггеров8 управления по числу столбцов матричной модели графа, вторую группу 5элементов И 9 по числу столбцовматричной модели графа, группу регистрирующих счетчиков 10 по числустолбцов матричной модели графа,третью группу элементов И 11 по 1 Очислу столбцов матричной модели графа, группу регистрирующих триггеров12 по числу столбцов матричной модели, графа, четвертую группу элементов И 13 по числу матричной моделигрйфа, блок 14 выбора максимальногокода числа, элемент ИЛИ 15, первыйэлемент И 16, генератор 17 тактовыхимпульсов, второй элемент И 18,счетчик 19, дешифратор 20, входы 21и 22, выход 23.Блок 14 (фиг.2) содержит поразрядные узлы переноса 24, 2424,где в - максимальная разрядность кода критического пути, которая совпадает с разрядностью счетчиков 10,группы элементов И и ИЛИ 25+2,25, состоящие из элементовИЛЙ 26 и элементов И 27, элементыИЛИ-НЕ 28,28 28, входные шины29+29 29, выходные шины301 р ЗОВг 30 рдовательно все триггеры 2 в этойстроке находятся в нулевом состоянии.Определение вершин графа, образующих максимальный критическийпуть, осуществляется в два этапа.На первом этапе с появлением пускового сигнала на входе 21 элемента И 16 импульсы с выхода генеРатора17 поступают на входы элементов И 6и 9, При этом импульсы проходят навсе счетчики 10, так как в исходномсостоянии все триггеры 8 находятсяв нулевом состоянии, а управляемыевходы элементов И 9 подключены кнулевым выходам триггеров 8. Крометого, счетные импульсы поступают через элементы И 6 на те счетчики 7,для которых триггеры 2 одноименнойстроки матрицы находятся в нулевомсостоянии. Поэтому на выходе соответствующих элементов ИЛИ-НЕ 4 будетвысокий потенциал, благодаря чемуна управляемом входе одноименногоэлемента И 6 будет также высокийпотенциал.Отсчитав число импульсов, пропорциональное весу моделируемойвершины, счетчик 7 переполняется,устанавливает в единичное состояниесоответствующий триггер 8, а всетриггеры 2 в данном столбце матричной модели - в нулевое состояние.Переброс триггера 8 в единичное состояние обеспечивает прекращение подачи счетных импульсов через элемент И 9 на вход регистрирующего З 5 счетчика 10, на котором Фиксируетсякод максимального пути из даннойвершины до конечной вершины графасети. Вычислительный процесс продолжается до тех пор, пока на выходах 40 всех триггеров 8 не будут присутствовать низкие потенциалы . На выходеэлемента ИЛИ 15 будет низкий потенциал, в результате чего прекращаетсяподача счетных импульсов с выходагенератора 17 через элемент И 1 5 наинформационные входы элементов И 6 и9. На этом первый этап работы устройства заканчивается. 5055ЧЕ,эО65 Матричная модель графа 1 представляет собой матрицу однородных цепочек из последовательно соединенных триггера 2 и элемента И 3. Размер матричной модели пхни,где и - максимальное число вершин моделируемого графа.устройство работает следующим образом.Первоначально в модель 1 заносится информация о топологии моделируемого графа (сети), При этом триггеры 21 (1, = 1,п), которые являются формирователями дуг, устанавливаются в единичное, состояние, если есть информационная связь из 1-ой вершины в )-ую вершину. Соответствующий триггер 2 1 определяется пересечением 1-ой строки и 1-го столбца.Другие триггеры 2 1, а также триггеры 8 и счетчики 10 и 19 находятся в нулевом состоянии. В счетчики 7 соответствующих вершин графа заносятся числа импульсов, дополняющие веса вершин до полной емкости счетчиков, После занесения исходной информации на входах элементов 4 ИЛИ-Н объединяющих выходы триггеров 2 в строках, соответствующим конечным вершинам моделируемого графа, будут высокие потенциалы. Это объясняется тем, что в однонаправленном графе беэ циклов и петель конечные вершины не содержат выходящих ветвей, а сле" На втором этапе заносится только информация в виде матрицы смежности моделируемого графа, а также устанавливается в.единичное состояние. триггер 12, соответствующий начальной вершине моделируемого графа.После занесения исходной информации на вход 22 подается разрешающий сигнал, в результате чего счетные импульсы с выхода генератора 12 через элемент И 18 поступают на вход счетчика 19, с вихода которого код поступает иа входы дешифратора 20. Н выходе дешифратора 20 возбущцаются поочередно выходные шины, которые подсоединены к управляемым входам соответствующих элементов И 13. Еслипри этом триггер 12 находится вединичном состоянии, то высокийпотенциал поступает на элементы И 13,а с его выхбда.поступает на информационные входы элементов И 3 одноименной строки матричной модели сети 5и поступает далее через элемент ИЛИ 5только на те управляемые входы элементов И 11, которым в данной строке матричной модели сети соответствует дуга графа, т .е. единичное состояние триггера 2. Наличие высокихпотенциалов на .управляемых входах.элементов И 11 с выходов элементов ИЛИ 5 обеспечивает поступлениекодов с выходов счетчиков 10 на входы 15блока 14, который, в свою очередь,обеспечивает выбор максимального изпоступивших кодов, при этом, соответствующие триггеры 12 перебрасываютсяединичное сосие и т.д. Процесспоиска максимального критическогопути заканчивается при появленииединичного сигнала на выходе 23.Блок 14 обеспечивает поиск максимального кода из множества поступивших со счетчиков 10 через элементы И 11. Для этого на входы 29схемы 14 через открытые элементыИ 11 поступают коды с единичных выходбв счетчиков 1 О. В первый моментанализируются старшие разряды. Еслиодин из старших разрядов чисел равен 1, то на выходе элемента 284 фор.мируется О, который служит сигналомзапрета для каждого из остальныхчисел. При этом, если старший разряд 351-го числа равен О, то все 1-ыеразряды. не проходят через элементыИ 27 1-ой группы первого поразряд,ного узла переноса.Если старшийразряд 1-го числа равен 1, то 1-ое 40число проходит через элементы И 271-ой группы первого поразрядногоузла переноса 24,Если старшие разряды всех чисел равны О, то на выходе элемента ИЛИ-НЕ 28 формируется 1, которая дает разрешение на прохождение всех кодов через элементы И 27 узла переноса 24, На выходе этих элементов И 27 формируются прямые коды чисел, начиная со второго по щ-ый. Вторым элементом ИЛИ-НЕ 28 совместно с элементами ИЛИ 26 поразрядного узлапереноса 24анализируются вторые по старшийству разряды чисел такЧм же образом, как и старших разрядов, и т.д. Позиционный код номера экстремального числа получается путем совпадения всех сигналов запрета, сформированных в каждом -ом поразрядном узле переноса, При сигналах запрета, равных 1, на выходе блока 14 формируется позиционный код с 1 в разряде, соответствующем максимальному коду,: 65при определениия всех вершинледующем приРабота устройства максимальных путей дл в графе пояснена на с мере.Пусть задан граф, матрицей смежности А весов вершин описываемыйи вектором Т О 1 1 1 О 0 0 0 0 1 00001 0 0 О 0 0 О 0 0 0 0 0 0 0 0 0 0.00 0 0 00000 00000 0 0 0 0 0 00000 0 1 0 0 0 1 1 0 1 0 0 1 0 0 0 00110 00110 00010 0 0 0 0 1 00001 00000 Т : 1 р Зр 2 у 5 У 4 У ЗР 4 У ЗР 2 У 2, где элементыО, если нет дуги из 1-ой верши- а. =ны в -ую; 4 1, если есть дуга из 1-ой вершины в - ую; Т - вес 1-ой вершины моделируемогографа.После .занесения исходной информации на входах элемента ИЛИ-НЕ 4 О будет низкий потенциал, а на выходе высокий. На выходах элементов ИЛИ-НЕ 2 - 2 д будет низкий потенциал, поэтому после подачи пускового сигнала на вход 21 устройства счетные импуль - сы с выхода генератора 17 через элемент И 16 поступают через элементы И 9 - 9 на входы регистрирующих счетчиков 101 - 10 , а также через элемент И бо на вход счетчика 7 о Через Т = 2, т.е. с приходом второго импульса, который заполняет до пол,ной емкости счетчик 7,о, перебрасывается в единичное состояние триггер 8, а все триггеры 2, о 2 юо в нулевое состояние . Переброс триггера 8 в единичное состояние вызывает прекращение подачи счетных импульсов на регистрирующий счетчик 10 О . Таким образом, на выходах элементов ИЛИ-НЕ 4, 49 и 4 после прихода второго импульса с выхода генератора 17 через элементы ИЛИ 15, И б и И 9 появятся высокие потенциалы, после чего счетные импульсы поступят на входы счетчиков 7 и 7 , и т.д.ФВычислительный процесс первого этапа заканчивается с приходом четырнадцатого импульса, после чего прекращается подача счетных импульсов на вход счетчика 10 (на все другие счетчики 10 подача импульсов прекращается ранее); на выходе элемента ИЛИ 15 будет низкий потенциал, вследствиечегО прекращается подача счетных импульсов на входы счетчиков 7 и 10. Показания счетчиков 10 соответствуют максимальнымвеличинам в графе для каждой вершийы, при этом каждому номеру вершины сопоставлен счетчик. В данном случае эти показания, начиная с первого, следующие; 14; 12; 11; 13; 9; 8; .8,5; 4; 2.5На втором этапе работы устройства после повторного занесения информации в виде матрицы А в матричную модель графа, установки триггера 12 в единичное состояние и подачи пус кового сигнала на вход 22 с приходом первого импульса с генератора 17 через элемент 18 на счетчике 19 устанавливается код 001,который поступает на дешифратор 20. Появление такого кода на входе дешифратора 20 вызывает возбуждение первой его выходной шины, в результате чего с выхода элемента И 131 высокий потенциал поступает на управляемые входы вентилей первой строки матричной модели графа, поэтому на входы блока 14 поступят коды со счетчиков 10, 103 и 104 через элементы И 11 т 113 и 11,. соответственно. Максимальный из этих кодов код со счетчика 10 (1 3), поэтому в единичное состояние перебросится триггер 124 .Далее к содержимому счетчика 19 прибавляется единица и процесс продолжается до тех пор, пока не переполнится счетчик 19, после чего на выходе 23 устройства будет выдан единичный сигнал. В данном примере критический максимальный путь составляет 1, 4, 7, 9 и 10 вершины, о З 5 чем свидетельствуют единичные состояния триггеров 12, 124, 12 , 12, и 12 о1Таким образом, применение предлагаемого устройства за счет введения дополнительных элементов с новыми связями обеспечивает возможность определения вершин, образующих максимальный критический путь, и повышает его быстродействие.Формула изобретенияУстройство для определения максимальных путей в графах, содержащее триггеры по числу строк и столбцовматричной модели графа, группу элементов ИЛИ-НЕ по числу строк матрич" ной .модели графа, первую группу эле ментов И по числу столбцов матричной модели графа, группу счетчиков весаф вершины по числу столбцов матричной модели графа, группу триггеров управления по числу столбцов 60 матричной модели графа, вторую группу элементов И по числу столбцов матричной модели графа, элементИЛИ, первый элемент И, генератор тактовых импульсов, причем выходы 65 триггеров одноименной строки матрич ной модели графа подключены к входам элемента ИЛИ-НЕ группы одноименной строки, выход каждого из ко" торых соединен с управляющим входом элемента И первой группы одноименного столбца, выход которого через счетчик фвеса вершины группы одноименного столбца подключен к установочным входам триггеров одноименного столбца матричной модели графа и к входу триггера управления группы одноименного столбца, выход которого соединен с управляющим входом элемента И второй группы одно. именного столбца и с соответствующим входом элемента ИЛИ,.выход которого подключен к первому входу первого элемента И, выход которого сое" динен с информационными входами элементов И первой и второй групп, выход генератора тактовых импульсов подключен к второму входу первого элемента И, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены второй элемент И, блок выбора кода максимального числа, дополнительный счетчик, дешифратор, элементы И по числу строк и столбцов матричной модели графа, третья группа элементов И по числу столбцов матричной модели сети, группа элементов ИЛИ по числу столбцов матричной модели графа, группа регистрирующих триггеров по числу столбцов матричной модели графа и четвертая группа элементов И по числу столбцов матричной модели графа, выход каждого элемента И четвертой группы одноименного столбца подключен к первым входам элементов И одноименной строки матричной модели графа, выходы элементов И одноименного столбца матричной модели графа соединены с входами элемента ИЛИ группы одноименного столбца, выход которого подключен к управляющему входу элемента И третьей группы одноименного столбца, информационный вход которого соединен с выходом регистрирующего счетчика группы одноименного столбца, выходы элементов И третьей группы подключены к соответствующим входам блока выбора кода максимального числа, выходы которого соединены с входами регистрирующих триггеров группы со" ответственно, выход каждого из которых подключен к информационному входу элемента И четвертой группы одноименного столбца, управляемый вход которого соединен с соответствующим выходом дешифратора, вход которого подключен к выходу дополнительного счетчика, выход генератора тактовых импульсов соединен с информационным входом второго элемента И, выход которого подключенк входу дополнитель но го сче тчик а,выход каждого триггера матричноймодели графа соединен с вторым вхо.дом элемента И матрицы.Источники информации,принятые во внимание при экспертизе 1, Авторское свидетельство СССРР 798854, кл, 6 06 Р 15/20, 1978,2. Авторское свидетельство СССРпо заявке Р 2861750/18-24,кл. 6 06 Р 15/20, 1980 (прототип).947869 гь,убини наа КоРРектоР И, Муска дактор Н. Ковале 653/73 Тираж 731ВНИИПИ Государственногопо делам изобретени113035, Москва, Ж, Раую а Филиал ПППф Патент, г. Ужгород, ул. Проектная, 4 оставитель И.ехред Т. Мать Подписн окомитета СССРи открытийкая наб., д. 4/5