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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советскик

Социалистических

Республик »947869 (61) Дополнительное к авт. сеид-ву (22) Заявлено 201180 (21)3007322/18-24 сприсоединениемзаявки ¹ (23) Приоритет (51) М. Кп.

G 06 F. 15/20

Государственный комитет

СССР но деяам изобретений н открытий

{53) УДК 681. 333 (088. 8) Опубликовано 300782. Бюллетень ¹28

Дата опубликования описания 30.07.82 (72) Авторы изобретения

В.A Титов, Ю.П. Афанасьев и А.С. К (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНЫХ

ПУТЕЙ В ГРАФАХ

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

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

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

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

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

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

0 максимальных путей в графах, в сос947869 тав которого входят триггеры по числу строк и столбцов матричной модели, генератор тактовых импульсов, элемент ИЛИ, первый элемент И, по числу столбцов матричной модели сети первые элементы И, счетчики весов вершин, триггеры управления, вторые элементы И, регистрирующие счетчики, по числу строк матричной модели сети элементы ИЛИ-НЕ, выходы которых подсоединены к управляющим входам одноименных первых элементов И, выходы которых соединены с входами одноименных счетчиков весов вершин, выходы которых подсоединены к установочным входам триг- 15 геров одноименных столбцов матрицы и к входам одноименных триггеров управления, выходы которых соединены с управляющими входами одноименных вторых элементов И и с входами элемента ИЛИ, выход которого подсоединен к первому входу первого элемента И, выход которого соединен с информационными входами первых и вторых элементов И, выход генератора тактовых импульсов подсоединен к второму входу первого элемента И (2).

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

Поставленная цель достигается тем, что в устройство для определения максимальных путей в графах, 35 содержащее триггеры по числу строк и столбцов матричной модели графа, группу элементов ИЛИ-НЕ по числу строк матричной модели графа, первую группу элементов И по числу столб- 4О цов матричной модели графа, группу .счетчиков . веса вершины по числу столбцов матричной модели графа, группу триггеров управления по числу столбцов матричноЙ модели графа, вторую группу элементов И по числу столбцов матричной модели графа, элемент ИЛИ, первый элемент И, генератор тактовых импульсов, причем выходы триггеров одноименной строки матричной модели графа подключены к входам элемента ИЛИ-НЕ группы одноименной строки, выход каждого из которых соединен с управляющим входом элемента И первой группы одноименного столбца, выход которого через счетчик веса вершины группы одноименного столбца подключен к установочным входам триггеров одноименного столбца матричной модели графа и к входу триггера управления 6О группы одноименного столбца, выход которого соединен с управляющим входом элемента И второй группы одноименного столбца и с соответствующим входом элемента ИЛИ, выход которого подключен к первому входу первого элемента И, выход которого соединен с информационными входами элементов И первой и второй групп, выход генератора тактовых импульсов подключен к второму входу первого элемента И, введены второй элемент

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

На фиг.1 показана структурная схема предлагаемого устройства; на фиг,2 — блок выбора кода максимального числа. !

Устройство (фиг,1) содержит матричную модель 1 графа, по числу строк и столбцов матричной модели графа триггеры 2, по числу строк и столбцов матричной модели графа элементы И 3, по числу столбцов матричной модели графа группу элементов

ИЛИ-НЕ 4, группу элементов ИЛИ 5 по числу столбцов матричной модели графа, первую группу элементов И 6

947869 по числу столбцов матричной модели графа, группу счетчиков веса

7 вершины по числу столбцов матричной модели графа, группу триггеров

8 управления по числу столбцов матричной модели графа, вторую группу 5 элементов И 9 по числу столбцов матричной модели графа, группу регистрирующих счетчиков 10 по числу столбцов матричной модели графа, третью группу элементов И 11 по 10 числу столбцов матричной модели графа, группу регистрирующих триггеров

12 по числу столбцов матричной модели, графа, четвертую группу элементов И 13 по числу матричной модели графа, блок 14 выбора максимального кода числа, элемент ИЛИ 15, первый элемент И 16, генератор 17 тактовых импульсов, второй элемент И 18, счетчик 19, дешифратор 20, входы 21 и 22, выход 23.

Блок 14 (фиг.2) содержит поразрядные узлы переноса 24, 24 . ..24,„, где m — максимальная разрядность кода критического пути, которая совпадает с разрядностью счетчиков 10, группы элементов И и ИЛИ 25«,25

25 и, состоящие из элементов

ИЛЙ 26 и элементов И 27, элементы

ИЛИ-НЕ 28,28,..., 28„„,р входные шины

29«,29«,..., 29„„, выходные шины

30,30д..., 30 . довательно все триггеры 2 в этой строке находятся в нулевом состоянии.

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

На первом этапе с появлением пускового сигнала на входе 21 элемента И 16 импульсы с выхода генеРатора

17 поступают на входы элементов И 6 и 9, При этом импульсы проходят на все счетчики 10, так как в исходном состоянии все триггеры 8 находятся в нулевом остоянии, а управляемые входы элементов И 9 подключены к нулевым выходам триггеров 8. Кроме того, счетные импульсы поступают через элементы И 6 на те счетчики 7, для которых триггеры 2 одноименной строки матрицы находятся в нулевом состоянии. Поэтому на выходе соответствующих элементов ИЛИ-НЕ 4 будет высокий потенциал, благодаря чему на управляемом входе одноименного элемента И 6 будет также высокий потенциал.

Отсчитав число импульсов, пропорциональное весу моделируемой вершины, счетчик 7 переполняется, устанавливает в единичное состояние соответствующий триггер 8, а все триггеры 2 в данном столбце матричной модели — в нулевое состояние.

Переброс триггера 8 в единичное состояние обеспечивает прекращение подачи счетных импульсов через элемент И 9 на вход регистрирующего

З5 счетчика 10, на котором фиксируется код максимального пути из данной вершины до конечной вершины графа сети. Вычислительный процесс продолжается до тех пор, пока на выходах

4О всех триггеров 8 не будут присутствовать низкие потенциалы . На выходе элемента ИЛИ 15 будет низкий потенциал, в результате чего прекращается подача счетных импульсов с выхода генератора 17 через элемент И 1 5 на информационные входы элементов И 6 и

9. На этом первый этап работы устройства заканчивается.

Е, эО

Матричная модель графа 1 представляет собой матрицу однородных цепочек из последовательно соединенных триггера 2 и элемента И 3. Размер матричной модели пхни,где n — максимальное число вершин моделируемого графа. устройство работает следующим .образом.

Первоначально в модель 1 заносится информация о топологии моделируемого графа (сети). При этом триггеры

2i) (i,j = 1,n), которые являются формирователями дуг, устанавливаются в единичное, состояние, если есть информационная связь из i-ой вершины в )-ую вершину. Соответствующий триггер 2 1,(определяется пересечением i-ой строки и 1-го столбца.Другие триггеры 2 1(, а также триггеры

8 и счетчики 10 и 19 находятся в нулевом состоянии. В счетчики 7 соответствующих вершин графа заносятся числа импульсов, дополняющие веса вершин до полной емкости счетчиков. После занесения исходной информации на входах элементов 4 ИЛИ-Н объединяющих выходы триггеров 2 в строках, соответствующим конечным вершинам моделируемого графа, будут высокие потенциалы. Это объясняется тем, что в однонаправленном графе беэ циклов и петель конечные вершины не содержат выходящих ветвей, а слеНа втором этапе заносится только информация в виде матрицы смежности моделируемого графа, а также устанавливается в единичное состояние. триггер 12, соответствующий начальной вершине моделируемого графа.

После занесения исходной информации на вход 22 подается разрешающий сигнал, в результате чего счетные импульсы с выхода генератора 17 через элемент И 18 поступают на вход счетчика 19, с вихода которого код поступает иа входы дешифратора 20. Н» выходе дешифратора 20 возбущцаются поочередно выходные шины, которые подсоединены к управляемым входам соответствующих элементов И 13. Если

947869 при этом триггер 12 находится в единичном состоянии, то высокий потенциал поступает на элементы И 13, а с его выхбда.поступает на информа ционные входы элементов И 3 одноименной строки матричной модели сети и поступает далее через элемент ИЛИ 5 только на те управляемые входы элементов И 11, которым в данной строке матричной модели сети соответствует дуга графа, т .е. единичное сос- 10 тояние триггера 2 . Наличие высоких потенциалов на .управляемых входах элементов И 11 с выходов элеглентов ИЛИ 5 обеспечивает поступление кодов с выходов счетчиков 10 на входы 5 блока 14, который, в свою очередь, обеспечивает выбор максимального из поступивших кодов, при этом, соответствующие триггеры 12 перебрасываются в единичное состояние и т.д. Процесс 2 поиска максимального критического пути заканчивается при появлении единичного сигнала на выходе 23.

Блок 14 обеспечивает поиск максимального кода из множества посту25 пивших со счетчиков 10 через элементы И 11. Для этого на входы 29 схемы 14 через открытые элементы

И 11 поступают коды с единичных выходов счетчиков 1 О. В первый момент анализируются старшие разряды. Если один из старших разрядов чисел равен 1, то на выходе элемента 284 формируется О, который служит сигналом запрета для каждого из остальных чисел. При этом, если старший разряд 35

i-го числа равен О, то все 1-ые разряды. не проходят через элементы

И 27 i-ой группы первого поразряд,ного узла переноса. Если старший разряд i-ro числа равен 1, то i-oe 40 число проходит через элементы И 27

i-ой группы первого поразрядного узла переноса 24, Если старшие разряды всех чисел равны О, то на выходе элемента

ИЛИ-HE 28 формируется 1, которая дает разрешение на прохождение всех кодов через элементы И 27 узла переноса 24г. На выходе этих элементов И 27 формируются прямые коды чисел, начиная со второго по m-ый.

Вторым элементом ИЛИ-НЕ 28 совместно с элементами ИЛИ 26 поразрядного узла переноса 24 анализируются вторые по старшийству разряды чисел такси же образом, как и старших разрядов, и т.д. Позиционный код номера экстремального числа получается путем совпадения всех сигналов запрета, сформированных в каждом 3-ом поразрядном узле переноса. При сигналах запрета, равных 1, на выходе блока 14 формируется позиционный код с 1 в разряде, соответствующем максимальному коду.: 65 при определении я всех вершин ледующем приРабота устройства максимальных путей дл в графе пояснена на с мере.

Пусть задан граф, матрицей смежности A весов вершин описываемый и вектором Т

О 1 1 1 О

О О О О 1

О О О О 1

О О 0 О О

О О О О О

О 0 О О О

О О О О О

О О О О О

О О О О О

О О О О О

О О О О О

О 1 О О О

1 1 О 1 О

О 1 О О О

О О 1 1 О

О О 1 1 О

О О О 1 О

О О О О 1

О О О О 1

О О О О 0

Т„. = 1; 3; 2; 5; 4; 3; 4; 3; 2; 2) где элем енты

О, если нет дуги из i-ой вершиа ° . = ны в 1-ую;

1, если есть дуга из i-ой вершины в г-ую;

Т вЂ” вес i-ой вершины моделируемого граф а.

После .занесения исходной информации на входах элемента ИЛИ-НЕ 4 0 будет низкий потенциал, а на выходе высокий. На выходах элементов ИЛИ вЂ 

2 — 2g будет низкий потенциал, поэтому после подачи пускового сигнала на вход 21 устройства счетные импуль— сы с выхода генератора 17 через элемент И 16 поступают через элементы

И 9А — 9 на входы регистрирующих счетчиков 101 — 10, а также через элемент И 6 на вход счетчика 7 0

Через Т„ = 2, т.е. с приходом второго импульса, который заполняет до пол.ной емкости счетчик 7„, перебрасывается в единичное состояние триггер 8„, а все триггеры 2.г,гц -2,го в нулевое состояние . Переброс триггера 8 в единичное состояние вызывает прекращение подачи счетных импульсов на регистрирующий счетчик

10„ц . Таким образом, на выходах элементов ИЛИ-НЕ 4g, 49 и 4„ после прихода второго импульса с выхода генератора 17 через элементы ИЛИ 15, И 6 и И 9 появятся высокие потенциалы, после чего счетные импульсы поступят на входы счетчиков 7 и

7, и т.д.

Вычислительный процесс первого этапа заканчивается с приходом четырнадцатого импульса, после чего прекращается подача счетных импульсов на вход счетчика 10г (на все другие счетчики 10 подача импульсов прекращается ранее); на выходе элемента ИЛИ 15 будет низкий потенциал, вследствие чего прекращается подача счетных импульсов на входы счетчиков 7 и 10. Показания счетчиков 10 соответствуют максимальным

947869

10 величинам в графе для каждой вершийы, при этом каждому номеру вершины сопоставлен счетчик. В данном случае эти показания, начиная с первого, следующие: 14; 12; 11; 13; 9; 8; .

8,5; 4; 2. 5

На втором этапе работы устройства после повторного занесения информации в виде матрицы А в матричную модель графа, установки триггера 12 в единичное состояние и подачи пус- lÎ кового сигнала на вход 22 с приходом первого импульса с генератора 17 через элемент 18 на счетчике 19 устан.авливается код 001, который поступает на дешифратор 20. Появление такого кода на входе дешифратора

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

14 поступят коды со счетчиков 10, 10 и 104 через элементы И ll, 11 и 114 соответственно. Максимальный из этих кодов код со счетчика 10+ (13), поэтому в единичное состояние пере бросится триггер 1 24 .

Далее к содержимому счетчика 19 прибавляется единица и процесс продолжается до тех пор, пока не переполнится счетчик 19, после чего на выходе 23 устройства будет выдан единичный сигнал. В данном примере критический максимальный путь составляет 1, 4, 7, 9 и 10 вершины, о чем свидетельствуют единичные состояния триггеров 12 1 24, 12, 12, и 12<о

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

Формула изобретения

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

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

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

947869 к входу дополнительного счетчика, выход каждого триггера матричной модели графа соединен с вторым вхо-дом элемента И матрицы.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

798854, кл, G 06 F 15/20, 1978.

2. Авторское свидетельство СССР по заявке Р 2861750/18-24, кл. G 06 F 15/20, 1980 (прототип).

947869

24пп

Составитель И. Дубинина

Редактор H. Ковалева Техред Т. Матбчка Корректор И. Муска

Заказ 5653/73 Тираж 731 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб, д. 4/5

Филиал ППП Патент, г. Ужгород, ул. Проектная, 4