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

 

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

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

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

РЕСПУБЛИК..(5.1)4 6 F 15 20

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

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

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

IlO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3848761/24-24 (22) 23.01.85 (46) 23.01.87. Бюл. № 3 (72) A.А.Есетов (53) 681.3(088.8) (56) Авторское свидетельство СССР

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

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

¹ 995094, кл. C 06 F 15/20, 1981, „„SU„„12 54 7 А1 (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНЫХ ПУТЕЙ В ГРАФАХ (5?) Изобретение относится к области вычислительной техники. Itåëü.èçîáðåтения — повышение быстродействия устройства, Изобретение обеспечивает более высокое быстродействие при идентификации вершин графа, образующих критический путь, за счет выбора иэ rpaAa вершин, расположенных на критическом пути, исключая длительную процедуру перебора всех вершин

rpaAa. Это достигается введением в устройство группы элементов НЕ, элементов И, ИЛИ, НЕ и триггера. 1 ил.

1285487

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

Задача. определения максимального критического пути в графе заключается

B определении Hpëè÷èíû и индентификации вершин, образующих этот путь.

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

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

Устройство содержит матричную и х и модель t графа, триггеры 2 по числу строк и столбцов матричной модели графа, первый и второй элементы И 3 и 4, по числу п столбцов матричной модели графа, группу элементов ИЛИ-НЕ 5, группу из и элементов

ИЛИ 6, первую группу из и элементов

И 7, группу из и счетчиков 8 "весов вершины, вторую группу из и элементов И 9 группу из п регист1

25 рирующих счетчиков 10, третью. группу из и элементов И 11, группу из.п регистрирующих триггеров 12 (n-триггеров с синхронизацией приема информаций от генератора тактовых импульсов), четвертую группу из и элементов И 13, блок 14 выбора максимального кода числа, первый элемент ИЛИ

15, первый элемент И 16, генератор ,17 тактовых импульсов, первый элеC

1чент HE 18, второй элемент И 19, 35 группу из (и — 1) элементов НЕ 20, второй элемент ИЛИ 21, второй эле мент НЕ 23 третий и четвертый элементы И 23 и 24, третий элемент НЕ

25, триггер 26, пятый элемент И 27, 40 выход 38, вход 29.

Матричная модель 1 rpaAa представляет собой матрицу однородных узлов, каждый из которых представляет собой триггер 2 и подсоединенные

45 к его выходу элементы И 3 и 4. Раз— мер матричной модели пхп, где n— максимальное число вершин моделируемого графа.

Устройство работает следующим образом, Первоначально в модель 1 заносит— ся информация о топологии моделируемого графа (сети) ° При этом триггеры 2 1 (i, 1 = 1, 2,...,n), которые

55 являются формирователями дуг, устанавливаются в единичное состояние, если есть информационная связь из

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

В единичное состояние устанавливается также триггер 12, соответствующий начально вершине моделирующего графа. В счетчики 8 соответствующих

6 вершин,. rpaAa заносятся числа импуль 1

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

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

И 7 и 9. При этом импульсы проходят на все счетчики 1О, так как в исходном состоянии вторые входы элементов

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

Отсчитав число импульсов, пропорпиональное "весу моделируемой вершины, счетчик 8 переполняется, и низкий потенциал с триггера переполнения (He показан) счетчика 8 подается на вторые входы элементов И 4 одноименного столбца матричной модели 1 и одноименный вход элемента

ИЛИ 15. Появление низкого потенциала на входе соответствующего элемента

И 9 обеспечивает прекращение подачи! 285487 счетных импульсов через элемент И

9 на вход регистрирующего счетчика

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

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

Второй этап работы устройства начинается после появления высокого потенциала на выходе элемента НЕ

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

И 19 поступают на входы элементов

И 13.

Высокий потенциал появляется на выходе элемента И 13; в случае, если триггер 12; находится в единичном состоянии и его порядковый номер i наибольший из группы триггеров 12„ находящихся в единичном состоянии, так как высокий потенциал с выхода триггера 12; поступает на вход элемента НЕ 20. В результате с выхода элемента НЕ ?О низкий потенциал поступает на соответствующие входы элементов И 13> (j = i — 1, i — 2;...,f) 35 запрещая тем самым появление высоких потенциалов на выходах элементов И 13> .

Высокий потенциал с выхода элемен «40 та И 13, поступает на информационные входы элементов И 3 (i

1, 2...,n) одноименной строки матричной модели 1 сети и поступает далее через элементы ИЛИ 6 только

45 на те управляемые входы элементов

И 11, которым в данной строке матричной модели сети соответствует дуга графа, т.е. единичное состояние триггера 2. Наличие высоких потенциалов

Ма управляемых выходах элементов

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

Одновременно высокие потенциалы с выходов элементов ИЛИ 6 поступают через элементы И 11 на соответствующие входы элемента ИЛИ ?1. В результате на выходе элемента ИЛИ ?1 появляется высокий потенциал, который поступает на первый вход элемента

И 24, на второй вход которого поступает тактовый импульс с генератора

17 через элемент И 19. Следовательно, на выходе элемента И 24 появляется высокий потенциал, который поступает на второй (S) вход RS-триггера 26 и устанавливает его в единичное состояние.

С окончанием действия тактового импульса с генератора 17 низкий потенциал поступает на вход элемента

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

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

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

К-ю вершину, лежащую на критическом пути.

В результате высокий потенциал с выхода элемента И 13 z поступает на информационные входы элементов

И 3„(j = 1, 2, ..., п) одноименной строки матричной модели 1 сети.

Конечная вершина графа не имеет выходящих дуг. Следовательно, триггеры 2 (j = 1, 2, ..., n) находятся в нулевом состоянии. В результате на элементы ИЛИ 6 с элементов. И 3 поступают низкие потенциалы. На управляемых выходах элементов ИЛИ 6 устанавливаются низкие потенциалы, которые поступают на соответствующие входы элемента ИЛИ 21, Следо1285487

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

О 1 1 1 О О О О О О

О О 0 О 1 О 1 О О О

О 0 0

О О О

О О О

О 0 0

О 0 0

О О О

О, 0 О

О О О

0 1 1 1 О 1 О

О О О 1 О О 0

О О 0 О 1 1 О

О О О О 1 О О

0 О О О О 1 О

О 0 О О О О 1

0 О О О О О 1

О О 0 0 О О О (>; 3; 2 ; 5; 4; 3; 4; 3; 2 23 элементы

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

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

F емого графа.

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

21 устанавливается низкий потенциas>, который поступает на вход элемента НЕ 22. С выхода элемента HF, 22 высокий потенциал поступает на второй вход элемента И 23, на первый вход которого поступает тактовый им; пульс с генератора 17 через элемент И 19.

В результате с выхода элемента И

23 появляется высокий потенциал, который поступает на первый (R) вход

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

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

ИЛИ-HF, 5, — 5> присутствует низкий потенциал, поэтому после подачи пу5 скового сигнала на вход 29 устройства счетчика импульсы с выхода ге,нератора 17 через элемент И 16 поступают через элементы И 9, — о, на входы регистрирующих счетчиков 10, — 10,, а также через элементы И 7ш на вход счетчика 8 .Через t = 2,ñ приходом второго импульса, который заполняет до полной емкости счетчик 816, перебрасывается в единичное состояние/ триггер разряда переполнения счетчика 8„, что вызывает прекращение подачи счетных импульсов на регистрирующий счетчик 10, Таким образом, на выходах элементов ИЛИ-НЕ 5, 5,и 5, и после прихода второго импульса с выхода генератора 17 через элементы И 7 и 9 появляются высокие потенциалы, по25 сле чего счетные импульсы поступают также на входы счетчиков 8< и

8ч и т д

Вычислительный процесс первого этапа заканчивается с приходом четырнадцатого импульса, после чего прекрашается подача счетных импульсов на вход счетчика 10, (на все другие счетчики 10 подача импульсов прекращается ранее); на выходе элемента

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

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

4; 2.

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

55 высокого потенциала на выходе элемента И 13 который поступает на управляемые входы вторых элементов

И 3 первой строки матричной модели графа, поэтому на входы блока 14 по7 12 ступают коды со счетчиков 10, 10> и 1П4 через элементы И 11, 11 и

11 соответственно. Максимальный из этих кодов — код со счетчика 10 : (13), поэтому н единичное состояние перебрасывается триггер 1? . С выхода триггера 1? высокий потенциал поступает на вход элемента НЕ ?,.

В результате с выхода элемента НЕ

204 низкий потенциал поступает на соответствующие входы элементов И

13, 13 и 13 . Следовательно, на выходе элемента И 13, устанавливается низкий потенциал.

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

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

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

1? 1, 12;, 12, 1?, и 12, . Поступление пятого тактового импульса с генератора 17 через элемент И 19 на входы элементов И 13 вызывает появВ ление высокого потенциала на выходе

85487 8

5

30 элемента И 13,, который поступает на информационные входы элементов

И 3,О (j = 1, 2,...,10) одноименной юJ строки матричной модели 1 сети, Так как данная строка триггера 2 установлена в нулевое состояние, то на входы элементов ИЛИ 6 через элементы

И 3 поступают низкие потенциалы.

В результате на выходе элемента

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

С окончанием действия тактового импульса с генератора 17 низкий потенциал через элемент И !9 поступает на вход элемента НЕ 25. В результате на выходе элемента НЕ 25 устанавливается высокий потенциал, котсрый поступает на второй вход элемента

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

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

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

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

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

И подключен к первым входам элемен—

1285487 тов И первой и второй групп, выход

j-го элемента ИЛИ-НЕ (i = 1, 2..., п, п — размерность матричной модели графа) соединен с вторым входом го элемента И первой группы, выход 5 которого подключен к счетному входу

i-го счетчика "веса вершины, выход переполнения которого соединен с вторым. входом i-ro элемента И второй группы, выход которого подключен к счетному входу i-го регистрирующего счетчика, выход переполнения которого подключен к первому входу элемента И третьей группы, выход которого соединен с i-м входом блока выбора кода максимального числа, i-й выход которого подключен к вхолу i-ro регистрирующего триггера, выход которого соединен с первым входом i-ro элемента И четвертой группы, выход кото- 20

Э рого подключен к вторым входам пер вых элементов И узлов i-й строки .матричной модели графа, выход первого элемента И i-го узла матричной модели rpaAa соединен с i-м входом i° .25 го элемента ИЛИ группы, выход котороо подключен к второму входу i-го элемента И третьей группы, выход второго элемента И узла i-й строки матричной модели графа подключен к i-му входу i-го элемента ИЛИ-НЕ группы выход переполнения >-ro счетчика . "веса" вершин группы соединен с вторыми входами вторых элементов И узлов i-го столбца матричной модели 35 графа и с i-м входом первого элемента ИЛИ, выход которого через первый элемент HE подключен к второму входу второго элемента И, выход первого элемента ИЛИ соединен с вторым входом первого элемента И устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства, в него введены группа из (и — 1) элементов НЕ,второй и третий элементы НЕ, второй элемент ИЛИ, третий, четвертый и пятый элементы И и триггер, выход iro регистрирующего триггера группы соединен с входом К-го элемента НЕ группы (К = 2,3, ... и), выход которого соединен с входами j-x элементов И четвертой группы (j 1, 2...,, i — 1), выход i-го элемента

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

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

НЕ, выход которого соединен с вторым входом пятого элемента И, выход которого является выходом устройства.

1385487

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

Редактор Е.Папп Техред А.Кравчук Корректор H.1 уска

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

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

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

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