Устройство для определения максимальных путей в графах Советский патент 1982 года по МПК G06F15/173 

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

Задача определения максимального критического пути в графе заключается в определении значения величины и идентификации вершин, образующих этот путь.

Известно устройство для определения максимального критического пути в графе, содержащее генератор тактовых импульсов, выход которого подключен к входу первого элемента И, управляег«лй вход которого подключен к выходу элемента НЕ,.вход которого подключен к выходу второго элемента И по числу строк и столбцов матричной модели графа цепочки из последовательно соединенных счетчика и триггера, по числу столбцов матричной модели графа группы элементов И, дополнительные элементы НЕ, первые и вторые группы элементов И, дополнительные счетчики, входы каждого из которых подключены к выходу элемента И второй группы, управляемый вход которого подключен к выходу дополнительного элемента НЕ, выходы триггеров одноименного столбца матричной модели графа подключены к соответствующим входам группы элементов И, выход которой подключен к входу дополнительного элемента НЕ и управляемому входу элемента И первой группы, выход которого подключен к соответствующему входу второго элемента И и входам счетчиков одноименной строки матричной модели

10 графа, информационные входы первых и элементов И группы подключены к выходу первого элемента И 1.

Недостатками данного устройства ЯВ.ПЯЮТСЯ необходимость перехода

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

Наиболее близким к предлагаемому является устройство для определения

10 максимальных путей в графах, в соетав которого входят триггеры по чи лу строк и столбцов матричной моде ли, генератор тактовых импульсов, элемент ИЛИ, пе,рвый элемент И, по числу столбцов матричной модели се первые элементы И, счетчики весов вершин, триггеры управления, вторые элементы И, регистрирующие счетчики, по числу строк матричной модели сети элементы ИЛИ-НЕ, выход которых подсоединены к управляющи входам одноименных первых элементов И, выходы которых соединены с входами одноименных счетчиков ве сов вершин, выходы KOTOpiJx подсо динены к установочным входам триггеров одноименных столбцов матрицы и к входам одноименных триггеров у равления, выходы которых соединены с управляющими входами одноименных вторых элементов И и с входами эле мента ИЛИ, выход которого подсоеди нен к первому входу iiepBorio элемента И, выход которого соединен с информационными входами первых и втор элементов И, выход генератора тактовых импульсов подсоединен к второ му входу первого элемента И 2. Цель изобретения - расширение функциональных возможностей за счет идентификации вершин, образующих максимальный критический путь и повышение быстродействия. Поставленная цель достигается тем, что в устройство для определения максимальных путей в графах, содержащее триггеры по числу строк и столбцов матричной модели графа, группу элементов ИЛИ-НЕ по числу строк матричной модели графа, перву группу элементов И по числу столбцов матричной модели графа, группу .счетчиков .веса вершины по числу столбцов матричной модели трафа, группу триггеров управления по числу столбцов матричной модели графа вторую группу элементов И по числу столбцов матричной модели графа, элемент ИЛИ, первый элемент И, гене ратор тактовых импульсов, причем выходы триггеров одноименной строки матричной модели графа подключены к входам элемента ИЛИ-НЕ группы одноименной строки, выход каждого из которых соединен с управляющим входом элемента И первой группы одноименного столбца, выход которого черфз счетчик веса вершины груп :пы одноименного столбца подключен к установочным входам триггеров одноименного столбца матричной модели графа и к входу триггера управления группы одноименного столбца, выход которого соединен с управляющим входом элемента И второй группы одноименного столбца и с соответствующим входом элемента ИЛИ, выход которого подключен к первому входу первого элемента И, выход которого соединен с информационными входами элементов И первой и второй групп, выход генератора тактовых импульсов подключен к второму входу первого элемента И, введены второй элемент И, блок выбора кода максимального числа, дополнительный счетчик, дешифратор, элементы И по числу строк и столбцов матричной модели графа, третья группа элементов И по числу столбцов матричной модели сети,группа элементов ИЛИ по числу столбцов матричной модели графа, группа регистрирующих триггеров по числу столбцов матричной модели графа и четвертая группа элементов И по числу столбцов матричной модели графа, выход каждого элемента И четвертой группы одноименного столбца подключен к первым входам элементов И одноименной строки матричной модели графа, выходы элементов И одноименного столбца матричной модели графа соединены с входами элемента,ИЛИ группы одноименного столбца, выход которого подключен к управляющему входу элемента И третьей группы одноименного столбца, информационный вход которого соединен с выходом регистрирующего счетчика группы одноименного столбца, выходы элементов И третьей группы подключены к соответствующим входам блока выбору кода максимального числа, выходы которого соединены с входами регистрирующих триггеров группы соответственно, выход каждого из которых подключен к информационному входу элемента И четвертой группы одноименного столбца, управляемый вход которого соединен с соответствующим выходом дешифратора, вход которого подключен к выходу дополнительного счетчика, выход генератора тактовых импульсов соединен с информационным входом второго элемента И, выход которого подключен к входу дополнительного .счетчика, выход каждого триггера матричной модели графа соединен с вторым входом элемента И матрицы. На фиг.1 показана структурная сзхема предлагаемого устройства на фиг.2 - блок выбора кода максимального числа. I Устройство (фиг.1) содержит матричную модель 1 графа, по числу строк и столбцов матричной модели графа триггеры 2, по числу строк и столбцов матричной модели графа элементы И 3, по числу столбцов матричной модели графа группу элементов ИЛИ-НЕ 4, группу элементов ИЛИ 5 по числу столбцов матричной модели графа, первую группу элементов И 6 по числу столбцов матричной модели графа, группу счетчиков веса 7вершины по числу столбцов матричной модели графа, группу триггеров 8управления по числу столбцов матричной модели графа, вторую группу элементов И 9 по числу столбцов матричной модели графа, группу регистрирующих счетчиков 10 по числу столбцов матричной модели графа, треты§ группу элементов И 11 по числу столбцов матричной модели гра фа, группу регистрирующих триггеров 12 по числу столбцов матричной модели .графа, четвертую группу элемен тов И 13 по числу матричной модели , блок 14 выбора -максимального кода числа, элемент ИЛИ 15, первый элемент И 16, генератор 17 тактовых импульсов, второй элемент И 18, счетчик 19, дешифратор 20, входы 21 и 22, выход 23. Блок 14 (фиг.2) содержит поразря ные узлы переноса 24, 242., . . . ,, где m - максимальная разрядность ко да критического пути, которая совпадает с разрядностью счетчиков 10, группы элементов И и ИЛИ 25, ,25,. 25 щи, состоящие из элементов 26 и элементов И 27, элементы ИЛИ-НЕ 28- ,28-, . . . , 28у,, входные шин 29 ,29,..., 29, выходные шины 30xf ,302j . . ., 30,. Матричная модель графа 1 предста ляет собой матрицу однородных цепочек из последовательно соединенных триггера 2 и элемента И 3.Размер матричной модели пхт,где п - максимальное число вершин моделируемого графа. Устройство работает следующим обраэом. Первоначально в модель 1 заносит ся информация о топологии моделируе мого графа (сети). При этом триггер 21j (i, 1гП), которые являются формирователями дуг, устанавливаются в единичное .состояние, если есть информационная связь из i-ой вершин в j-ую вершину. Соответствующий триггер 2 ij опреде.ляется пересечением i-ой строки и /-го столбца.Дру гие триггеры 2 ij , а также триггеры 8 и счетчики 10 и 19 находятся в ну левом состоянии. В счетчики 7 соответствующих вершин графа заносятся числа импульсов, дополняющие веса вершин до полной емкости счетчиков. После занесения исходной информации на входах элементов 4 ИЛИ- объединяющих выходы триггеров 2 в строках, соответствующим конечным вершинам моделируемого графа, будут высокие потенциалы. Это объясняется тем, что в однонаправленном графе без циклов и петель конечные вершин не содержат выходящих ветвей, а еле довательно все триггеры 2 в этой строке находятся в нулевом состоянии. Определение вершин графа, образующих максимальный критический путь, осуществляется в два этапа. На первом этапе с появлением пускового сигнала на входе 21 элемента И 16 импульсы с выхода гене)атора 17 поступают на входы элементов И 6 и 9. При этом импульсы проходят на все счетчики 10, так как в исходном состоянии все триггеры 8 находятся в нулевом состоянии, а управляемые входы элементов И 9 подключены к нулевым выходам триггеров 8. Кроме того, счетные импульсы поступают через элементы И 6 на те счетчики 7, для которых триггеры 2 одноименной строки матрицы находятся в нулевом состоянии. Поэтому на выходе соответствующих элементов ИЛИ-НЕ 4 будет высокий потенциал, благодаря чему на управляемом входе одноименного элемента И 6 будет также высокий потенциал. Отсчитав число импульсов, пропорциональное весу моделируемой вершины, счетчик 7 переполняется, устанавливает в единичное состояние соответствующий триггер 8, а все триггеры 2 в данном столбце матричной модели - в нулевое состояние. Переброс триггера 8 в единичное состояние обеспечивает прекращение подачи счетных импульсов через элемент И 9 на вход регистрирующего счетчика 10, на котором фиксируется код максимального пути из данной вершины до конечной вершины графа сети. Вычислительный процесс продолжается до тех пор, пока на выходах всех триггеров 8 не будут присутствовать низкие потенциалы. На выходе элемента ИЛИ 15 будет низкий потенциал, в результате чего прекращается подача счетных импульсов с выхода генератора IV через элемент И 15 на информационные входы элементов И 6 и 9. На этом первый этап работы устройства заканчивается. На втором этапе заносится только информация в виде матрицы смежности моделируемого графа, а тежже устанавливается в единичное состояние, триггер 12, соответствующий начальной вершине моделируемого графа. После занесения исходной информации на вход 22 подается разрешающий сигнал, в результате чего счетные импульсы с выхода генератора 17 через элемент И 18 поступают на вход счетчика 19 с выхода которого код поступает на входы дешифратора 20. На выходе дешифратора 20 возбуждаются поочередно выходные шины, которые подсоединены к управляемым входам соотв.етствующих элементов И 13. Если при этом триггер 12 находится в единичном состоянии, то высокий потенциал поступает на элементы И 1 а с его .поступает на информа ционные входы элементов И 3 одноименной строки матричной модели сет и поступает далее через элемент ИЛИ только на те управляемые входы элементов И 11, которым в данной строке матричной модели сети соответствует дуга графа, т.е. единичное сое тояние триггера 2. Наличие высоких потенциалов на управляемых входах, элементов И 11 с выходов элементов ИЛИ 5 обеспечивает поступление кодов с выходов счетчиков 10 на вхо блока 14, который, в свою очередь, обеспечивает выбор максимального из поступивших кодов, при этом, соотве ствующие триггеры 12 перебрасываютс в единичное состояние и т.д. Процес поиска максимального критического пути заканчивается при появлении единичного сигнала на выходе 23. Блок 14 обеспечивает поиск максимального кода из множества поступивших со счетчиков 10 через элементы И 11. Для этого на входы 29 схемы 14 через открытые элементы И 11 поступают коды с единичных выход(5в счетчиков 10. В первый момент анализируются старшие разряды. Если один из старших разрядов чисел равен 1, то на выходе элемента 28. фо мируется О, который служит сигналом запрета для каждого из остальных чисел. При этом, если старший разря i-ro числа равен О, то все 1-ые разряды, не проходят через элементы И 27 1-ой группы первого поразряд.ного узла переноса. Если старший разряд i-ro числа равен 1, то i-oe число проходит через -элементы И 27 i-ой группы первого поразрядного узла перенос а 24 . Если старшие разряды всех чисел равны О, то на выходе элемента ИЛИ-НЕ 28 формируется 1, которая Дает разрешение на прохождение всех кодов через элементы И 27 узла переноса 24. На выходе этих элементов И 27 формируются прямые коды чисел, начиная со второго по т-ый. Вторым элементом ИЛИ-НЕ 28,2 совмест но с элементами ИЛИ 26 поразрядного узла переноса 24 анализируются вторые по старшинству разряды чисел так1 же образом, как и старших раз рядов, и т.д. Позиционный код номера экстремального числа получается путем совпадения всех сигналов запрета, сформированных в каждом 1-ом поразрядном узле переноса. При сигналах запрета, равных 1, на выходе блока 14 формируется позиционный код с 1 В- разряде, соответствующем максимальному коду. Работа устройства при определении максимальных путей для всех вершин в графе пояснена на следующем примере . Пусть задан граф, описываемый матрицей смежности А и вектором Т весов вершин 0111000000 0000101000 0000111010 0000001000 0000000110 -А 0000000110 0.о 00000010 0000000001 0000000001 0000000000 Т J1; 3; 2; 5; 4; 3; 4; 3; 2; 2j, где элементы (О, если нет дуги из 1-ой вершины в j -ую; 1, если есть дуга из i-ой вер- . шины в - вес i-ой вершины моделируемого графа. После .занесения исходной информации на входах элемента ИЛИ-НЕ будет низкий потенциал, а на выходе высокий. На выходах элементов ИЛИ-НЕ 2 - 2д будет низкий потенциал, поэтому после подачи пускового сигнала на вход 21 устройства счетные импульсы с выхода генератора 17 через элемент И 16 поступают через элементы И 9 - на входы регистрирующих счетчиков 10 - 10, а также через элемент И на вход счетчика 7 . Через Т. 2, т.е. с приходом второго импульса, который заполняет до полной емкости счетчик , -перебрасывается в единичное состояние триггер , а все триггеры 2v д ,о в нулевое состояние. Переброс триггера 8,-в единичное состояние вытизывает прекращение подачи счетных импульсов на регистрирующий счетчик 1 . Таким образом, на выходах элементов ИЛИ-НЕ 4, 4д и после прихода второго импульса с выхода генератора 17 через элементы ИЛИ 15, И 6 и И 9 появятся высокие потенциалы, после чего счетные импульсы поступят на входы счетчиков 7g и 1д , и Т.Д. Вычислительный процесс первого этапа заканчивается с приходом четырнадцатого импульса, после чего прекращается подача счетных импульсов на вход счетчика 10 (на все другие счетчики 10 подача импульсов прекрсицается ранее); на выходе элемента ИЛИ 15 будет низкий потенциал, вследствиеЧего прекращается подача счетных импутиьсов на входы счетчиков 7 и 10. Показания счетчиков 10 соответствуют максимальным величинам в графе для каждой вершин при этом каждому номеру вершины сопоставлен счетчик. В данном случае эти показания, начиная с первого следующие: 14; 12; 11; 13; 9; 8; . 8,5; 4; 2. На втором этапе работы устройств после повторного занесения информации в виде матрицы А в матричную мо дель графа, установки триггера 12у в единичное состояние и подачи пускового сигнала на вход 22 с приходом первого импульса с генератора 1 через элемент 18 на счетчике 19 устанавливается код О01,который поступает на дешифратор 20. Появле.ние такого кода на входе дешифратор 20 вызывает возбуждение первой его выходной шины, в результате чего с выхода элемента И 13 высокий потен циал поступает на управляемые входы вентилей первой строки матричной модели графа, поэтому на входы блок 14 поступят коды со счетчиков 10, Юз и 10 через эле1(енты И И, 11, и И. соответственно. Максимальный из этих кодов код со счетчика 10. (13), поэтому в единичное состояние перебросится триггер 124. Далее к содержимому счетчика 19 прибавляется единица и процесс продолжается до тех ПОР г пока не переполнится счетчик 19, после чего на выходе 23 устройства будет выдан единичной сигнал. В данном примере критический максимальный путь соста ляет 1, 4, 7, 9 и 10 вершины, о чем свидетельствуют единичные состояния триггеров 12, 12, 12 , 12 и Таким образом, применение предлагаемого устройства за счёт введения дополнительных элементов с новы ми связями обеспечивает возможность определения вершин, образующи максимальный критический путь, и по вышает его быстродействие. Формула изобретения Устройство для определения макси мальных путей в графах, содержащее триггеры по числу строк и столбцов матричной модели графа, группу элементов ИЛИ-НЕ по числу строк матрич ной..модели графа, первую группу эле ментов И по числу столбцов матрично модели графа, группу счетчиков ве са вершины по числу столбцов матричной модели графа, группу триггеров управления по числу столбцов матричной модели графа, вторую груп пу элементов И по числу столбцов матричной модели графа, элемент ИЛИ, первый элемент И, генератор тактовых импульсов, причем выходы триггеров одноименной строки матрич ной модели графа подключены к входам элемента ИЛИ-НЕ группы одноименной строки, выход каждого из которых соединен с управляющим входом элемента И первой группы одноименного столбца, выход которого через счетчик веса вершины группы одноименного столбца подключен к установочным входам триггеров одноименного столбца матричной модели графа и к входу триггера управления группы одноименного столбца, выход которого соединен с управляющим входом элемента И второй группы одноименного столбца и с соответствующим входом элемента ИЛИ,.выход которого подключен к первому входу первого элемента И выход которого соединен с информационньми входами элементов И первой и второй групп, выход генератора тактовых импульсов подключен к второму входу первого элемента И, отличающееся: тем, что, с целью повышения быстродействия, в него введены второй элемент И, блок выбора кода максимального числа, дополнительный счетчик, дешифратор, элементы И по числу строк и столбцов матричной модели графа, третья группа элементов И по числу столбцов матричной модели сети, группа элементов ИЛИ по числу столбцов матричной модели графа, группа регистрирующих триггеров по числу столбцов матричной модели, графа и четвертая группа элементов И по числу столбцов матричной модели графа, выход каждого элемента И четвертой группы одноименного столбца подключен к первым входам элементов И одноименной строки матричной модели графа, выходы элементов И одноименного столбца матричной модели графа соединены с входами элемента ИЛИ группы одноименного столбца, выход которого подключен к управляющему входу элемента И третьей группы одноименного столбца, информационный вход которого соединен с выходом регистрирующего счетчика группы одноименного столбца, выходы элементов И третьей группы подключены к соответствующим входам блока выбора кода максимального числа, выходы которого соединены с входами регистрирующих триггеров группы соответственно, выход каждого из которых подключен к информационному входу элемента И четвертой группы одноименного столбца, управляемый вход которого соединен с соответствующим выходом дешифратора, вход которого подключен к выходу дополнительного счетчика, выход геиератора тактовых импульсов соединен с информационным входом второго элемента И, выход которого подключен К входу дополнительного счетчика, выход каждого триггера матричной модели графа соединен с вторым входом элемента И матрицы. Источники информации, принятые во внимание при экспертизе 5 1. Авторское свидетельство СССР №798854, кл. G 06 F 15/20, 1978. 2. Авторское свидетельство СССР по заявке 2861750/18-24, л. G 06 Р 15/20, 1980 (прототип).

п

/