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

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

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

Цель изобретения - повышение быстродействия устройства.

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

Устройство содержит матричную п X п модель 1 графа, триггеры 7. по числу строк и столбцов матричной модели графа, первый и второй элементы И 3 и 4, по -числу п столбцов матричной модели графа, группу элементов ИЛИ-НЕ 5, группу из п элементов ИЛИ 6, первую группу из п элементов И 7, группу из п счетчиков Я весов вершины, вторую группу из п элементов И 9, группу из п регистрирующих счетчиков 10, третью, группу из п элементов И 11, группу из- п регистрирующих триггеров 12 (D-триг- геров с синхронизацией приема информации от генератора тактовых импульсов) , четвертую группу из п элямен- тов И 13, блок 14 выбора максимального кода числа, первый элемент ИЛИ 15, первый элемент И 16, гене ратор ,17 тактовых импульсов, первый эле- {чент НЕ 18, второй элемент И 19, Vpynny из (п - 1) элементов НЕ 20, второй элемент ИЛИ 21, второй элемент НЕ ., третий и четвертый элементы И 23 и 24, третий элемент НЕ 25, триггер 26, пятый элемент И 27, выход 28, вход 29.

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

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

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

5

0

5

0

5

0

5

0

5

i-й вершины в j-ю вершину. Соответствующий триггер 2 ;; определяется пересечением i-й строки и j-ro столбца. Другие триггеры 2 : , а также счетчики 10 находятся в нулевом состоянии. Причем нумерация вершин графа начинается с Начальной вершины.

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

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

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

Отсчитав число импульсов, пропорциональное весу моделируемой вершины, счетчик 8 переполняется, и низкий потенциал с триггера перепол- нения (не показан) счетчика В подается на вторые входы элементов И 4 одноименного столбца матричной модели 1 и одноименный вход элемента ИЛИ 15. Появление низкого потенциала на входе соответствующего элемента И 9 обеспечивает прекращение подачи

счетных импульсов через элемент И 9 на вход регистрирующего счетчика 10, на котором фиксируются код максимального пути из данной вершины до-конечной вершины графа сети.Вычислительный процесс продолжается до тех пор, пока на выходах всех счетчиков 8 не будут присутствовать низкие потенциалы. На выходе элемента ИЛИ 15 .имеется низкий потенциал, в результате чего прекращается подача счетных импульсов с выхода генератора 17 через элемент И 16 на информационные входы элементов И 7 и 9. На этом первый этап работы устройства заканчивается.

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

Высокий потенциал появляется на выходе элемента И 13; в случае, если

триггер 12 , находится в единичном состоянии и его порядковый номер i наибольший из группы триггеров 12 , находящихся в единичном состоянии, так как высокий потенциал с выхода триггера 12j поступает на вход элемента НЕ 2П. В результате с выхода . элемента НЕ 20 низкий потенциал поступает на соответствующие входы элементов И 13 j (J i - 1, i - 2,-...,1 запрещая тем самым появление высоких потенциалов на выходах элементов И 13 .

Высокий потенциал с выхода элемен та И 13 поступает на информационные входы элементов И 3;: (i j 1, 2,.,,n) одноименной строки матричной модели 1 сети и поступает далее через элементы ИЖ 6 только на те,управляемые входы элементов И 11, которым в данной строке матрич- 1НОЙ модели сети соответствует дуга графа, т.е. единичное состояние триггера 2. Наличие высоких потенциалов ha управляемых выходах элементов ИЛИ 6 обеспечив ает поступление кодов с выходов счетчиков 10 на входы блока 14, который в свою очередь обеспечивает выбор максимального из поступивших кодов,-при этом соответствующие триггеры 12 перебрасываются в единичное состояние.

W

15

30

R54874

Одновременно высокие потенциалы с выходов элементов ИЛИ 6 поступают через элементы И 11 на соответствующие входы элемента ИЛИ 21. В результате на выходе элемента ИЛИ 21 появляется высокий потенциал, который поступает на первый вход элемента И 24, на второй вход которого поступает тактовый импульс с генератора 17 через элемент И 19. Следователь- . но, на выходе элемента И 24 появляется высокий потенциал, который по- стулает на второй (S) вход КЗ-триггера 26 и устанавливает его в единичное состояние.

С окончанием действия тактового импульса с генератора 17 низкий потенциал поступает на вход элемента НЕ 25. В результате на выходе элемента НЕ 25 устанавливается высокий потенциал, который поступает на второй вход элемента И 27, на первый вход которого поступает низкий потенциал с инверсного выхода триггера 26. В результате с выхода 28 устройства снимается низкий потенциал - сигнал продолжения идентификации вершин, образующих критический путь в графе. Йроцесс идентификации вершин графа продолжается аналогичным образом до конечной вершины графа, лежащей на критическом пути.

С поступлением очередного тактового импульса с генератора 17 через элемент И 19 на входы элементов И

20

25

35

40

45

50

55

13 на выходе элемента И 13|5 (К - порядковый номер конечной вершины графа, находящейся на критическом пути) появляется высокий потенциал, так как триггер 12 находится в единичном состоянии, идентифицирующий К-ю вершину, лежащую на критическом пути.

В результате высокий потенциал с выхода элемента И 13 поступает на информационные входы элементов KJ ( J 1 2, ..., п) одноименной строки матричной модели 1 сети. Конечная вершина графа не ийеет выходящих дуг. Следовательно, триггеры 2 KJ (J 1, 2, ..., п) находятся в нулевом состоянии. В результате н-а элементы ИЛИ 6 с элементов- И 3,; поступают низкие потенциалы. На управляемых выходах элементов ИЛИ 6 устанавливаются низкие потенциалы которые поступают на соответствующие входы элемента ИЛИ 21. Следовательно, на выходе элемента ИЛИ 21 устечнавливается низкий потенциал, который поступает на вход элемента НЕ 22. С выхода элемента НЕ 22 высокий потенциал поступает на второй вход элемента И 23, на первый вход которого поступает тактовый HN;- пульс с генератора 17 через элемент И 19.

В результате с выхода элемента И 23 появляется высокий потенциал, который поступает на первый (R) вход RS-триггера 26 и устанавливает его в нулевое состояние. С окончанием действия тактового импульса с генератора 17 низкий потенциал через элемент И 19 поступает на вход элемента НЕ 25. В-результате на выходе элемента НЕ 25 устанавливается высокий потенциал, который поступает на второй вход элемента И 27, на первый вход которого поступает высокий потенциал с инверсного выхода триггера 26. В результате на выходе элемента И 27 появляется высокий потенциал - сигнал окончания работы убтройства.

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

Пусть задан граф, описываемый матрицей смежности А и вектором И ве3- 5- U i- 3- - , -5 -5 t ,

енты

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

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

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

После занесения исходной информации -на входах элемента ИЛИ-НЕ 5

имеется низкий потенциал, а на выходе - высокий. На выходах элементов ИЛИ-НЕ 5v - 5 присутствует низкий потенциал, поэтому после подачи пускового сигнала на вход 29 устройства счетчика импульсы с выхода ге- lepaTopa 17 через элемент И 16 поступают через элементы И 9« - 9,о на входы регистрирующих счетчиков ( а также через элементы И на вход счетчика 8 .Через ,c приходом второго импульса, который заполняет

до полной емкости счетчик 8

10

пе

ребрасывается в единичное состояние/ триггер разряда переполнения счетчика 8

10

что вызывает прекращение

0

5

0

5

0

5 I

0

5

подачи счетных импульсов на регистрирующий счетчик .

Таким образом, на выходах элементов ИЛИ-НЕ 5д, 5,. и 5,j, и после прихода второго импульса с выхода генератора 17 через элементы И 7 и 9 появляются высокие потенциалы, после чего счетные импульсы поступают также на входы счетчиков 8g и 8, и т.д.

Вычислительный процесс первого этапа заканчивается с приходом четырнадцатого импульса, после чего прекращается подача счетных импульсов на вход счетчика 1П, (на все другие счетчики 10 подача импульсов прекращается ранее); на выходе элемента ИЛИ 15 имеется низкий потенциал, вследствие чего прекращается подача счетных импульсов на входь счетчиков 8 и 10. Показания счетчиков 10 соответствуют максимальным величинам в графе для каждой верщины, при этом каждому номеру верщины сопоставлен счетчик. В данном случае эти показания (начиная с первого) следующие: 14; 12; 11; 13; 9; 8; 8; 5; 4; 2.

На втором этапе работы устройства после появления высокого потенциала на входе элемента НЕ 18 начинается подача тактовых импульсов с генератора 17 через элемент И 19 на вход элементов И 13. Появление первого тактового импульса с генератора 17 через элемент И 19 на входы элементов И 13 приводит к появлению высокого потенциала на выходе элемента И 13,, который поступает на управляемые входы вторых элементов И 3 первой строки матричной модели графа, поэтому на входы блока 14 поступают коды со счетчиков 10,,, Ю, и 10 через элементы И 1 1, , 11 и 11ц соответственно. Максимальный из этих кодов - код со счетчика 10 (13), поэтому в единичное состояние перебрасывается триггер l. С выхода триггера 12 высокий потенциал поступает на вход элемента НЕ 20, В результате с выхода элемента НЕ 2( низкий потенциал поступает на соответствующие входы элементов И 13, 13 и 1. Следовательно, на выходе элемента И 13, устанавливается низкий потенциал.

Одновременно высокие потенциалы с выходов элементов ИЛИ 6j , 6 и 64 через элементы И 11 поступают на входы элемента ИЛИ 21. В результате на выходе последнего появляется высокий потенциал, который поступает на первый вход элемента И 24, на второй вход которого поступает тактовый импульс с генератора 17 через элемент И 19. Следовательно, на выходе элемента И 24 появляется высокий потенциал, который поступает на второй (S) вход RS-триггера 26 и устанавливает его в единичное состояние. С окончанием действия тактового импульса с генератора 17 низкий потенциал через .элемент И 19 поступает на вход элемента НЕ 2. В результате на выходе элемента НЕ 25 устанавливается высокий потенциал, который поступает на второй вход элeмёнta И 27, на первый вход которого поступает низкий потенциал с инверсного выхода триггера 26.

В результате с выхода 28 устройства снимается низкий потенциал - сигнал продолжения работы устройства.

С поступлением второго тактового импульса с генератора 17 через элемент И 19 на входы элементов И 13, на выходе элемента И 134 устанавливается высокий потендиал. Далее процесс продолжается до тех пор, пока все вершины графа, расположенные на критическом пути,будут идентифицированы. В данном примере критический максимальный путь составляет 1, 4, 7, 9 и 10 вершины, о чем свидетельствует .единичное состояние триггеров 12,, 12-4, 12т, 12д и 12,0. Поступление пятого тактового импульса с генератора 17 через элемент И 19 на входы элементов И 13 вызывает появление высокого потенциала на выходе

элемента И 1 3, , который поступает на информационные входы элементов -iqi J 2,..,, 10) одноименной строки матричной модели 1 сети. Так 5 как данная строка триггера 2 установлена в нулевое состояние, то на входы элементов ИЛИ 6 через элементы И 3 поступают низкие потенциалы. В {результате на выходе элемента

О ИЛИ 21 устанавливается низкий потенциал, который поступает на вход элемента НЕ 22. Следовательно, на выходе элемента НЕ 22 появляется высокий потенциал, который поступа5 ет на второй вход элемента И 23,на первый вход которого поступает тактовый импульс с генератора 17 через элемент И 19. В результате высокий потенциал с выхода элемента И 23 по0 ступает на R-вход триггера 26 и устанавливает его в нулевое состояние. С окончанием действия тактового ии- пульса с генератора 17 низкий потенциал через элемент И 19 поступает

5 на вход элемента НЕ 25. В результате на выходе элемента НЕ 25 устанавливается высокий потенциал, котсрый поступает на второй вход элемента И 27, на первый вход которого посту0 пает высокий потенциал с инверсного выхода триггера 26. В результате на выходе элемента И 27 появляется высокий потенциал - счгн.ал окончания работы устройства.

5

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

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

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

5 первого и второго элементов И, группу из п элементов ИЛИ-НЕ, первую,вторую, третью и четвертую группы из п элементов И, группу из п счетчиков веса вершин, группу из п регистри0 рующих сче-тчиков, блок выбора кода максимального числа, группу из п регистрирующих триггеров, группу из

п элементов ИЛИ, первый элемент ИЛИ, первый элемент НЕ, первый и второй

5 элементы И и генератор тактовых импульсов, выход которого соединен с первыми входами первого и второго элементов И, выход первого элеме11та И подключен-к первым входам элёмен-

тов и первой и второй групп, выход j-ro элемента ИПИ-НЕ (i 1, 2,... п, п - размерность матричной модели графа) соединен с вторым входом i- го элемента И первой группы, выход которого подключен к счетному входу i-ro счетчика веса вершины, выход переполнения которого соединен с вторым, входом i-ro элемента И второй группы, выход которого подключен к счетному входу i-ro регистрирующего счетчика, выход переполнения которого подключен к первому входу элемента И третьей группы, выход которого соединен с i-M входом блока выбора кода максимального числа, i-й выход которого подключен к входу i-ro ре- гистрирутащего триггера, выход которого соединен с первым входом i-ro элевый элемент НЕ подключен к втором входу второго элемента И, выход п вого элемента ИЛИ соединей с втор входом первого элемента И устройс 5 ва, отличающееся тем, что, с целью повьппения быстродействия устройства, в него введены группа из (п - 1) элементов НЕ,в рой и третий элементы НЕ, второй элемент ИЛИ, третий, четвертый и тый элементы И и триггер, выход i го регистрирующего триггера групп соединен с входом К-го элемента Н группы (К 2,3, ... п), выхад ко торого соединен с входами j-x эле ментов И четвертой группы (j 1, 2,.,., i - 1), выход i-ro элемент И третьей группы соединен с i-м в дом второго элемента ИЛИ, выход к

W

15

мента И четвертой группы, выход кото- 0 торого соединен с входом второго

рого подключен к вторым входам пер- вых элементов И узлов i-й строки .матричной модели графа, выход первого элемента И i-ro узла матричной модели графа соединен с i-м входом i- элемента ИЛИ группы, выход которо- о подключен к второму входу i-ro элемента И третьей группы, выход второго элемента И узла i-й строки матричной модели графа подключен к i-му входу i-ro элемента ИЛИ-НЕ группы, выход переполнения i-ro счетчика веса вершин группы соединен с вторыми входами вторых элементов И узлов i-ro столбца матричной модели графа и с i-M входом первого элемента ИЛИ, выход которого через первый элемент НЕ подключен к второму входу второго элемента И, выход первого элемента ИЛИ соединей с вторым входом первого элемента И устройст- ва, отличающееся тем, что, с целью повьппения быстродействия устройства, в него введены группа из (п - 1) элементов НЕ,второй и третий элементы НЕ, второй элемент ИЛИ, третий, четвертый и пятый элементы И и триггер, выход i- го регистрирующего триггера группы соединен с входом К-го элемента НЕ группы (К 2,3, ... п), выхад которого соединен с входами j-x элементов И четвертой группы (j 1, 2,.,., i - 1), выход i-ro элемента И третьей группы соединен с i-м входом второго элемента ИЛИ, выход ко

торого соединен с входом второго

элемента НЕ, выход которого подключен к первому входу третьего элемента И, выход которого соединен с пер- вьгм входом триггера, инверсный выход которого подключен к первому входу пятого элемента И, выход второго элемента ИЛИ .соединен с первым входом- четвертого элемента И, выход которого подключен к второму входу триггера, выход второго элемента И соединен с вторым входом i-ro элемента И четвертой группы, с вторыми входами третьего и четвертого элемен- тов И и с входом третьего элемента НЕ, выход которого соединен-с вторым входом пятого элемента И, выход которого является выходом устройства.

7LJ

T - 200 L

sL-usL-u (тЫ

Составитель И.Дубинина Редактор Е.Папп Техред А.Кравчук Корректор И.Муска

Заказ 7526/51 Тираж 670Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д.4/5

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

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