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

СЛ

оо

00 00

со 00

О5

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

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

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

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

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

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

Первоначально в модель 1 заносится информация о топологии моделируемого графа. При этом триггеры 2,; (i, j ), которые являются формирователями дуг, устанавливаются в единичное состояние, если есть информационная связь на i-й верщииы-в, j-ю вершину. Соответствующий триггер 2,,- определяется пересечением i-й строки и j-ro столбца. Другие триггеры 2,-;,.а также триггеры 10 и счетчики 13 устанавливаются в нулевое состояние. Триггеры 12 устанавливаются в единичное состояние. В счетчики 11, которые соответствуют вершинам графа, заносятся числа импульсов, дополняющие веса вершин до полной емкости счетчиков. После занесения исходной информации на выходах элементов ИЛИ-НЕ 5 объединяющих выходы триггеров 2 в столбцах, соответ- стЕ1ующих начальным вершинам моделируемого графа, присутствуют высокие потенциалы. Это объясняется тем, что в однонаправленном графе без циклов и петель начальные вершины не содержат входящих ветвей, а, следовательно, все триггеры 2 в этом столбце находятся в нулевом состоянии.

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

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

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

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

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

5

5

0

А

0111001001 00101 10000 0000010010

000000 000001

1000

1

о о о

1

0000000 1 00000001 000000000 000000000

0000000000

0

т /2, 1, 6, 4, 2, 5, 2, 4, 1, 2J, где элементы

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

a.v 1

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

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

После занесения исходной информации на входе элемента ИЛИ-НЕ 5i имеется низкий потенциал, а на выходе - высокий. На 5 выходах элементов ИЛИ-НЕ 62-5io присутствует низкий потенциал, поэтому после подачи пускового сигнала на вход 17 пусковой импульс разрешает прохождение счетных импульсов с генератора 16 тактовых

импульсов через элемент И 15 на счетчики 13 максимального пути и счетчики 11 весов вершин, кроме того, пусковой импульс поступает на нулевой вход элемента ИЛИ 6i и через одноименный вход шифратора 1 код данного входа записывается в регистр 9i. Импульс с выхода элемента ИЛИ 6i. через элемент И 8i, поступает на вход установки в единицу триггера 10i. Высокий потенциал с выхода триггера lOi поступает на вход

шины, о чем свидетельствуют показания регистров 9-9з, 9б, 98 и 9|о.

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

синхронизации счетчика Ih и разрешает от- 10 группу п счетчиков максимального пути, счет импульсов этим счетчиком. С приходомэлемент И, элемент ИЛИ, генератор таквторого импульса, который заполняет до полной емкости счетчик lli, на его выходе

появляется импульс переполнения, который

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

перебрасывает триггер 12 в нулевое состоя-повышения быстродействия, в него введены

ние и тем самым запрещает отсчет счетныхпервая и вторая группы триггеров, по п тригимпульсов счетчиком 13|. Кроме того, им-герое в каждой, группа п шифраторов, группульс переполнения со счетчика 111 через элементы И 4 узла матричной модели графа, одноименные триггеры 2 которых установлены в единицу, поступает на первые входы 20 пь1 (j: iT n) соединен с выходом j-ro шиф- одноименных элементов ИЛИ 6 и шифрато-ратора группы, i-й вход (i ) которого

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

задержки этого же узла, вход которого соединен с выходом триггера этого же узла и i-M входом (i 1, п) j-ro (j 1, п) элемента ИЛИ-НЕ группы, выход которого соеров 7, устанавливая при этом все триггеры 2 первой строки матричной модели графа в нулевое состояние. Таким образом, на выходах элементов ИЛИ-НЕ 52 и 54 появляется высокий потенциал, который открывает элементы И 82 и 84 и разрешает прохождение импульсов с выхода элементов ИЛИ 62 и 64 на триггеры 102 и 104, которые, установившись в единицу, разрешают отсчет

25 С j

импульсов счетчикам 1 Ь и 1 Ц весов вершин, о Динен с первым входом j-ro элемента И групПри этом в регистры 92 и 94 записывается код первой вершины графы.

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

пы, второй вход которого соединен с выходом j-ro элемента ИЛИ группы, выход j-ro элемента И группы соединен с входом установки в «1 j-ro триггера первой группы, выход которого соединен с входом синхро13,0 . На выходе элемента ИЛИ 14 появля- 35 зации j-ro счетчика веса вершины, вы- ется низкий потенциал, который запрещает которого соединен с вторыми входами

прохождение счетных импульсов с генерато-элементов И и входами установки в «О тригра 16 тактовых импульсов через элемент Р° узлов j-й строки матричной модели

графа и входом установки в «О j-ro триггера второй группы, выход которого соеди- 40 нен с входом синхронизации j-ro счетчика

Показания счетчиков 13 соответствуютмаксил1ального пути группы и с j-м входом

максимальным величинам путей в графе от(j 1, п) элемента ИЛИ, выход которого

соединен с первым входом элемента И, второй вход которого соединен с выходом генератора тактовых импульсов, третий вход элемента И является входом пуска устройИ 15 на счетчики весов вершин 11 и максимального пути 13.

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

ства и соединен с п + 1-м входом первого () элемента ИЛИ группы, выход элемента И соединен со счетными входами всех счетчиков максимального пути группы и со счетными входами счетчиков веса вершины группы.

шины, о чем свидетельствуют показания регистров 9-9з, 9б, 98 и 9|о.

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

па п регистров, причем в каждый узел матричной модели графа введен элемент задержки, инфор мационный вход j-ro регистра группь1 (j: iT n) соединен с выходом j-ro шиф- ратора группы, i-й вход (i ) которого

соеди та И i-ro у ца, п

25 С j

50

ства и соединен с п + 1-м входом первого () элемента ИЛИ группы, выход элемента И соединен со счетными входами всех счетчиков максимального пути группы и со счетными входами счетчиков веса вершины группы.

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