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

 

Изобретение относится к вычислительной технике и может быть использовано при исследовании параметров сетевых графов. Целью изобретения является повышение быстродействия устройства за счет определения величины критического пути в регистрирующих счетчиках и идентификации вершин критического пути в регистрах в один этап. Устройство содержит матричную модель графа 1, группу элементов 5 ИЛИ-НЕ, группу элементов 6 ИЛИ, группу шифраторов 7, группу регистров 9, группу элементов 8 И, первую 10 и вторую 12 группы триггеров , группу счетчиков веса вершины 11, группу счетчиков максимального пути 13,. элемент 14 ИЛИ, элемент 15 И, генератор 16 тактовых импульсов, вход 17. I ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН

„„SUÄÄ1383386

А1 (58 4 G 06 F 15 20 асср „

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4140720/24-24 (22) 29.10.86 (46) 23.03.88. Бюл. № 11 (72) А. В. Полиско и С. М. Злобин (53) 681.333 (088.8) (56) Авторское свидетельство СССР № 947869, кл. G 06 F 15/20, 1982.

Авторское свидетельство СССР № 995094, кл. G 06 F 15/20, 1983. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНЫХ ПУТЕЙ В ГРАФАХ (57) Изобретение относится к вычислительной технике и может быть использовано при исследовании параметров сетевых графов.

Целью изобретения является повышение быстродействия устройства за счет определения величины критического пути в регистрирующих счетчиках и идентификации вершин критического пути в регистрах в один этап. Устройство содержит матричную модель графа 1, группу элементов 5 ИЛИ вЂ” HE, группу элементов 6 ИЛИ, группу шифраторов 7, группу регистров 9, группу элементов 8 И, первую 10 и вторую 12 группы триггеров, группу счетчиков веса вершины 11, группу счетчиков максимального пути 13, элемент 14 ИЛИ, элемент 15 И, генератор 16 тактовых импульсов, вход 17. 1 ил.

1383386

0111001001

000001001 0

0000001 000

0000011001

0000000 101

0000000111

0000000001

0000000001

0000000000

45

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

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

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

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

Устройство содержит матричную модель 1 графа, каждый узел которой содержит триггер 2, соединенный через элемент 3 задержки с элементом И 4, группы элементов ИЛИ вЂ” НЕ 5 и ИЛИ 6 и группу шифраторов 7, соответствующим образом соединенных с матричной моделью графа, группу элементов И 8, группу регистров 9, первую группу триггеров 10, соединенных с группой счетчиков 11 веса вершины, которые через вторую группу триггеров 12 соединены с группой счетчиков 13 максимального пути, элементы ИЛИ 14 и И 15, генератор 16 тактовых импульсов, вход 17.

Устройство работает следующим образом.

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

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

10 и счетчики 13 устанавливаются в нулевое состояние. Триггеры 12 устанавливаются в единичное состояние. В счетчики 11, которые соответствуют вершинам графа, заносятся числа импульсов, дополняющие веса вершин до полной емкости счетчиков.

После занесения исходной информации на выходах элементов ИЛИ вЂ” НЕ 5,объединяющих выходы триггеров 2 в столбцах, соответствующих начальным вершинам моделируемого графа, присутствуют высокие потенциалы. Это объясняется тем, что в однонаправленном графе без циклов и петель начальные вершины не содержат входящих ветвей, а, следовательно, все триггеры 2 в этом столбце находятся в нулевом состоянии.

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

12 находятся в единичном состоянии и на синхронизирующие входы счетчиков 13 подаются высокие потенциалы) и на счетчик 11 веса начальной вершины (так как пусковой сигнал через элемент ИЛИ 6 и элемент И 8

2 устанавливает управляющий триггер 10 в единичное состояние). Отсчитав число импульсов, пропорциональное весу моделируемой вершины, счетчик 11 переполняется и импульсом переполнения устанавливает триг гер 12 и все триггеры 2 одноименной строки в нулевое состояние. Низкий потенциал с выхода триггера 12 останавливает отсчет импульсов счетчиком 13, на котором фиксируется код максимального пути от началь10 ной вершины до данной вершины. Импульс переполнения со счетчика веса моделируемой вершины через элементы И одноименной строки матричной модели графа, триггеры 2 которой установлены в единичное состояние, поступает на одноименные входы элемента ИЛИ 6 и шифратора 7, переводя при этом триггеры 2 соответствующей строки в нулевое состояние. В регистр 9 записывается код предыдущей вершины, из которой имеется информационная связь в

20 данную вершину. При этом отсчет импульсов происходит в тех счетчиках 11 веса вершин, вершины которых не имеют входящих ве гвей (т.е. все триггеры одноименного столбца матричной модели графа находятся в нулевом состоянии) .. Вычислительный процесс заканчивается после того, как все триггеры 12 перебросятся в нулевое состояние.

После этого на выходе элемента ИЛИ 14 появлятся низкий потенциал, который запрещает прохождение счетных импульсов с генеЗ0 ратора тактовых импульсов.

Устройство при определении величины критического пути и идентификации вершин работает следующим образом.

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

T = I2, 1, 6, 4, 2, 5, 2, 4, 1, 2J> где элементы

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

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

t; — вес j-й вершины моделируемого графа.

После занесения исходной информации на входе элемента ИЛИ вЂ” НЕ 5 имеется низкий потенциал, а на выходе — высокий. На

55 выходах элементов ИЛИ вЂ” НЕ 5 — 5ip присутствует низкий потенциал, поэтому после подачи пускового сигнала на вход 17 пусковой импульс разрешает прохождение счетных импульсов с генератора 16 тактовых

1383386

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

Устройство для определения максимальных путей в графах, содержащее матричную модель графа, состоящую из п)(п узлов, где п — максимальное число вершин моделируемого графа, группу п элементов ИЛИ вЂ” НЕ, группу и. элементов ИЛИ, группу и элементов И, группу и счетчиков веса вершины, 10 группу и счетчиков максимального пути, элемент И, элемент ИЛИ, генератор так- товых импульсов, причем каждый узел матричной модели графа содержит триггер и элемент И, отличающееся тем, что, с целью повышения быстродействия, в него введены первая и вторая группы триггеров, по и триггеров в каждой, группа и шифраторов, группа и регистров, причем в каждый узел матричной модели графа введен элемент задержки, информационный вход j-го регистра группы (j= 1, и) соединен с выходом j-го шифратора группы, i-й вход (i= 1, и) которого соединен с i-м входом (i= 1, и) j-го элемента ИЛИ группы и выходом элемента И

i-го узла матричной модели графа j ãî столбца, первый вход элемента И ij-ro узла (i= 1, и, j= 1, и) соединен с выходом элемента задержки этого же узла, вход которого соединен с выходом триггера этого же узла и

i-м входом (i= 1, n) j-го (j= 1, n) элемента ИЛИ вЂ” HE группы, выход которого сое3 импульсов через элемент И 15 на счетчики

13 максимального пути и счетчики 11 весов вершин, кроме того, пусковой импульс поступает на нулевой вход элемента ИЛИ 61 и через одноименный вход шифратора 71 код данного входа записывается в регистр 9ь

Импульс с выхода элемента ИЛИ 6 через элемент И 8i, поступает на вход установки в единицу триггера 10ь Высокий потенциал с выхода триггера 10 поступает на вход синхронизации счетчика l li и разрешает отсчет импульсов этим счетчиком. С приходом второго импульса, который заполняет до полной емкости счетчик l l i, на его выходе появляется импульс переполнения, который перебрасывает триггер 12 в нулевое состояние и тем самым запрещает отсчет счетных импульсов счетчиком 13 . Кроме того, импульс переполнения со счетчика 111 через эле менты И 4 узла матричной модели графа, одноименные триггеры 2 которых установлены в единицу, поступает на первые входы одноименных элементов ИЛИ 6 и шифраторов 7, устанавливая при этом все триггеры 2 первой строки матричной модели графа в нулевое состояние. Таким образом, на выходах элементов ИЛИ вЂ” НЕ 5 и 54 появляется высокий потенциал, который открывает элементы И 82 и 84 и разрешает прохождение импульсов с выхода элементов

ИЛИ 62 и 64 на триггеры 102 и 104, которые, установившись в единицу, разрешают отсчет импульсов счетчикам 11 и 11» весов вершин.

При этом в регистры 92 и 94 записывается код первой вершины графы.

Вычислительный процесс заканчивается с приходом 20-го импульса, после чего прекращается отсчет импульсов счетчиком

13,о. На выходе элемента ИЛИ 14-появляется низкий потенциал, который запрещает прохождение счетных импульсов с генератора 16 тактовых импульсов через элемент

И 15 на счетчики весов вершин 11 и максимального пути 13.

Показания счетчиков 13 соответствуют максимальным величинам путей в графе от первой вершины до данной. В регистрах 9 содержится код номера предыдущей вершины на максимальном пути. При этом каждому номеру вершины сопоставлен свой счетчик и регистр. В данном случае показания счетчиков следующие (начиная с первого): 2, 3, 9, 6, 5, 14, 8, 18, 10, 20, а показания регистров: О, 1, 2, 1, 2, 3, 4, 6, 7, 8.

В данном примере критический максимальный путь составляет 1, 2, 3, 6, 8, 10 вер30

50 динен с первым входом j-го элемента И группы, второй вход которого соединен с выходом j-го элемента ИЛИ группы, выход

)-го элемента И группы соединен с входом установки в «1» j-ro триггера первой группы, выход которого соединен с входом синхронизации j-го счетчика веса вершины, выход которого соединен с вторыми входами элементов И и входами установки в «О» триггеров узлов j-й строки матричной модели графа и входом установки в «О» j-го триггера второй группы, выход которого соединен с входом синхронизации j ãî счетчика максимального пути группы и с j-м входом (j= 1, и) элемента ИЛИ, выход которого соединен с первым входом элемента U, второй вход которого соединен с выходом генератора тактовых импульсов, третий вход элемента И является входом пуска устройства и соединен с и+ 1-м входом первого (j=1) элемента ИЛИ группы, выход элемента И соединен со счетными входами всех счетчиков максимального пути группы и со счетными входами счетчиков веса вершины группы.

Составитель С. Кошелев

Редактор Н. Лазаренко Техред И. Верес Корректор И. Муска

Заказ 915/49 Тираж 704 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4