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

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

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

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

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

10 И группы подключены к выходу первого элемента И С 1 .

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

15 графу с нагруженными дугами, низкое быстродейстие, так. как определение максимального 1 ритическогр пути в известном устройстве осуществляется по-, следовательно в три этапа, первые д ва

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

25 сравнением результатов двух подсчетов в схемах сравнения.

Наиболее близким по технической сущности к предлагаемому является устройство для определения максималь30ных путей в графах, в состав которого входят цепочки из последовательн соединенных первого триггера и перв го элемента И по числу п строк и п столбцов матричной модели графа, п элементов ИЛИ-НЕ, п элементов ИЛИ, п вторых элементов и, счетчиков весов вершин, п третьих элементов И, регистрирующих счетчиков, п четвертых элементов И, вторых триггеров, п пятых элементов И, блок в бора максимального кода, дешифратор дополнительный счетчик, первый элемент И, второй элемент И, элемент .ИЛИ, генератор тактовых импульсов, выход которого подсоединен к первом чвходу шестого элемента И и первому входу седьмого элемента И, выход .которого подсоединен к первым входам вторых элементов И и первым входам третьих элементов И, выходы первых элементов И одноименной i-и (г 1,л ) строки матричной модели графа подсоединены к входам i-го элемента ИЛИ-НЕ, выход которого подсоединен к второму входу i-ro второго элемента И, выход которого подсоединен .к входу-i-го счетчика веса вершины, выход которого подсоединен к вторым входам первых элемен тов И одноименного столбца матричной модели графа, к первому входу i-го третьего элемента И и к i-му входу элемента ИЛИ, выход которого подсоединен к второму входу второго элемзнта И, второй вход i-ro третьего элемента К подсоединен к выходу i-го элемента ИЛИ, а выход подсоединен через регистрирующий счетчик к перво му входу группы i-x четвертых элементов И, выход которой подсоединён к i-му входу блока выбора максималь кого кода, i-и выход которого подсоединен к входу i-ro второго триг гера, выход которого подсоединен к первому входу i-ro пятого элемента И, второй вход которого подсоединен к -му выходу дешифратора, вход которого подсоединен к выходу дополни тельного счетчика, вход которого . подсоединен к выходу первого элемент И 1:2. Цель изобретения - повышение быс родействия устройства. Поставленная цель достигается тем, что в устройство для определения максимальных путей в графах, со держащее матричную модель графа раз мерностью л X п , каждый узел которо содержит триггер и первый элемент И, причем выход триггера соединен с первым входом первого элемента И, а также группу из п элементов ИЛИ-НЕ, первую,вторую, третью и четвертую .группы,иэ п элементов И, группу из .п счетчиков веса вершин, группу из п регистрирующих счетчиков, блок выбора кода максимального числа, группу из п регистрирующих триггеро группу изп элементов ИЛИ, элемент ИЛИ, дешифратор, первый и второй элементы И, счетчик и генератор тактовых импульсов, выход которого соединен с первыми входами первого и второго элементов И, выход первого элемента И подключен к первым входам элементов И первой и второй групп, выход элемента ИЛИ-НЕ (i I,n, Ti - размерность матричной модели графа) соединен с вторым входом i-го элемента И первой группы,.выход которого подключен к входу i-го счетчика веса вершины, выход которого соединен с вторым входом -i -го элемента И второй группы, выход последнего через 1 -и регистрирующий счетчик подключен к первому входу элемента И третьей группы, выход которого соединен с i-м входом блока выбора кода максимального числа, 1-й выход которого подключен к входу i-го регистрирующего триггера,выход которого соединен с первым входом i-ro элемента И четвертой группы, выход которого подключен к вторым входам первых элементов И узлов i-и строки матричной модели графа, выход первого элемента И i-го узла матричной модели графа соединен с i-м входом i-ro элемента ИЛИ группы, выход которого подключен к второму входу i-ro элемента И третьей группы, выход элемента ИЛИ соединен с вторым входом первого элемента И, выход второго элемента И через счетчик подключен к входу дешифратора, т-й выход которо-.го соединен с вторым входом i-го элемента И четвертой группы, введены элемент НЕ, а в каждый узел матричной модели графа - второй. элемент И-, выход второго элемента И узла i-и строки подключен к i-му входу i-го элемента ИЛИ-НЁ группы, выход i-ro счетчика веса вершин группы соединен с первыми входами вторых элементов И узлов i-ro столбца матричной модели графа и с i-м входом элемента ИЛИ,выход которого через элемент НЕ подключен к втЬрому входу второго элемента И, выход триггера i-ro узла матричной модели графа соединен с вторым входом второго элемента И узла матричной модели графа. На чертеже представлена структурная схема устройства для определения максимальных путей в графах. Устройство содержит матричную модель 1 графа, триггеры 2 по числу строк и столбцов матричной модели графа (п X п ), первый и второй элементы И 3 и 4, по числуп столбцов матричной модели графа группу элементов ИЛИ-НБ 5, группу из п элементов ИЛИ б, первую группу из п элементов И 7, группу nt3 п счетчиков 8 весов вершины, вторую группу из п элементов и 9, группу из г рет истрирующих счетчиков 10, третью группу из п элементов И 11, группу из п гистрирующих триггеров 12, четвертую группу из п элементов И 13, блок 14 выбора максимального кода числа, элемент ИЛИ 15, первый элемент И 16, генератор 17 тактовых импульсов, элемент НЕ 18, второй элемент И 19, счетчик 20, дешифратор 21, вход 22, выход 23. Матричная модель 1 графа представ ляет собой матрицу однородных узлов, каждый из которых представляет собой триггер 2 и подсоединенные к его выходу элементы И 3 и 4,- Размер мат-. ричной модели - пхп , где п - максимальное числовершин моделируемого графа. Устройство работает следующим образом. Первоначально в модель 1 заносится информация о топологии модулируемого графа (сети). При этом триггеры 2j (.i,,n ), которые являются формирователями дуг, устанавливаются в единичное состояние, если есть информационная связь из т-и вершины в j-ю вершину. Соответствующий триггер 2|j определяется пересечением -й строки и j-ro столбца. Другие триггеры , а также счетчики 10 и 20 находятся в нулевом состоянии. В единичное состояние устанавливается также триггер 12, соответствуниций начальной вершине модулируемого графа. В счетчики 8 соответствующих вер шин графа заносятся числа импу льсов дополняющие веса вершин до полной емкости счетчиков; После занесения исходной информации на выходах элементов 5 ИЛИ-НЕ, объединяющих выходы триггеров 2,в строках, соответствующих конечным вершинам моделируе мого графа(будут высокие потенциалы. Это объясняется тем, что в однонаправленном графе без циклод и петель конечные вершины не содержат выходящих ветвей, а следовательно, все триггеры 2 в этой строке будут в нулевом состоянии. Определение вершин графа, образующих максимальный критический путь, осуществляется в два этапа. На первом этапе с появлением пускового сигнала на входе 22элемента И 16 импульсы с выхода генератора 1 поступают на входы элементов И 7 .и При этом импульсы проходят на всё счетчики 10, так как в исходном сос тоянии вторые входы элементов И 9 подключены к выходам одноименных . счетчиков 8, на которьЬс появляется сигнал переполнения. Кроме того, счетные импульсы поступают через эл менты и 7 на входа тех счетчиков 8 для которых триггеры 2 одноименной строки матрицы находятся в нулевс состоянии. Это происходит благодаря тому, что на выходе соответствующих элементов ИЛИ-НЕ 5 и на управляемом входе одноименного элемента И 7 будут высокие потенциалы. Отсчитав число импульсов, пропорциональное весу моделируемой вершины, счетчик 8 переполняется и низкий потенциал с триггера, переполнения (не показан) счетчика 8 подает ся на вторые входы элементов И 4 одноименного столбца матричной модели 1 и одноименный вход элемента ИЛИ 15, Появление низкого потенциала на вхо- де соответствукндего элемента И Э обеспечивает прекращение подачи счетных импульсов через элемент И 9 на вход регистрирующего счетчика 10, на котором фиксируется код максиМального пути из Данной вершины до конечной вершины графа сети. Вычислительный процесс-продолжается до тех пор, пока на выходах всех счетчиков 8 не будут присутствовать, низкие потенциалы. На выходе элемента ИЛИ 15 имеется низкий потенциал, в результате чего прекращается подача счетных импульсов с выхода генератора 17 через элемент И 16 на информациЬнные входы -блементов И 7 и 9. На этом первый этап работы устройства заканчивается. Второй этап работы устройства начинается после появления высокого потенциала на выходе элемента НЕ 18, после чего счетные импульсы с } ыхода генератора 17 через элемент И 19 поступают на вход счетчика 20, с первого выхода которого код поступает.на входы дешифратора 21. На выходе дешифратора 21 возбуждаются поочередно выходные шины, которые подсоединены к первым входам соответствующих элементов и 13. Если при этом триггер , 12; ( 1-1, п) находится в единичном состоянии, то высокий потенциал поступает на второйJвход элемента И 13j а с его выхода высокий потенциал поступает на информационные входы элементов И 3|j (i,,i) одноименной строки матричной модели сети 1 и поступает далее через элементы ИЛИ 6 только на те управляемые входы элементов И 11, которьм в данной строке матричной модели сети соответствует дуга графа, т.е. единичное состояние триггера 2. Наличие высоких потенциалов на управляемых выходах элементов ИЛИ 6 обеспечивает поступление кодов с выходов счетчиков 10 на входа блока 14, который, в свою очередь, обеспечивает выбор максимального из поступивших кодов при этом соответствующие триггеры 12 перебрасывгиотся в единичное сос тояние и т.д. Процесс поиска максимального критического пути эаканчивается при появлении единичного си нала на выходе 23 (сигнал переполн ния счетчика 20) . Работа устройства при определении максимальных путей для всех ве шин в графе поясняется следующим п мером. Пусть задан граф, описываемый м рицей смежности А и вектором Т в сов вершин. 0111000000 0000101000 0000111010 0000001000 А 0000000110 0000000010 0000000001 ООООООООО 0000000000 Т 1; 3; 2; 5; 4; 3; 4; 3, 2; где элементы О, если нет дуги из i-и вершины в ); 1, если есть дуга из вершины в j-ю; i-и вершины моделир .емого графа. После занесения исходной информа ции на входах элемента ИЛИ-НЕ 5 имеется низкий потенциал, а на выхо де - высокий. На выходах элементов ИЛИ-НЕ 5, - 5 9 присутствует низкий потенциал, поэтому после подачи пуско го сигнала на вход 22 устройства сч чика импульсы с выхода генератора 17 через элемент И 16 поступают через элементы Ц 9-, - 9-,о на входы ре гистрирующих счетчиков 10-| - 10-ю, также через элементы И на вхоц.счетчика 8 . Через 2, с приходом второго импульса, которых заполняет до полной емкости счетчик ,.перебрасывается в единичное со тояние триггер разряда переполнения счетчика , что вызывает прекраще ние подачи счетных импульсов на ре гистрирующий счетчик . Таким образом, на выходах элемен тов ИЛИ-НЕ Ssf Sg и и после при хода второго импульса с выхода гене ратора 17 через элементы И 7 и .9 появляются высокие потенциалы, после чего счетные импульсы поступают также на входы счетчиков 8д и 8д и т.д. Вычислительный процесс первого этапа заканчивается с приходом четырнадцатого импульса, после чего прекращается подача счетных импуль- сов на вход счетчика 10 . (на все другие счетчики 10 подача импульсов прекращается ранее); на выходе элемента ИЛИ 15 имеется низкий потенциал, вследствие чего прекращается подача счетных импульсов на входы счетчиков 8 и 10. Показания счетчиков 10 соответствуют максимальным величинам в графе для каждой вершины, при этом каждому номеру вершины сопоставлен счетчик. В данном случае эти показания (начиная с первого) следующие : 14 12; 11; 13; 9; 8; 8; 5; 4; 2. На втором этапе работы устройства после появления высокого потенциала на входе элемента НЕ 18 начинается подача счетных импульсов на вход счетчика 20. Появление первого импульса с генератора 17 через элемент на входе дешифратора 21 вызывает возбуждение первой его выходной шины, в результате чего с выхода элемента И 13 высокий потенциал поступает на управляемые входы вторых элементов И 3 первой строки матричной модели графа, поэтому на входы блока 14 поступают коды со счетчиков lOg . lOj и 104 через элементы И llg, 11 и 11 соответственно. Максимальный из этих кодов - код со счетчика 104 (13), поэтому в единичное состояние Перебрасывается триггер 12 4 Далее к содержимому счетчика 20 прибавляется единица и процесс продолжается до тех пор, пока не пере.полнится счетчик 20, после чего на выходе 23 устройства будет выдан единичный сигнал (сигнал переполнения счетчика 20). В данном примере критический максимальный путь составляет 1, 4, 7, 9и10 вершины, о чем свидетельствуют единичные состояния триггеров 12, 124, 12-7, 12ди . Таким образом, устройство за счет введения дополнительных элементов с новыми связями обеспечивает получение нового положительного эффекта, который заключается в повышений быстродействия устройства путем исключения длительной процедуры повторного ввода матрицы смежности моделируемого графа. Формула изобретения Устройство для определения максимальных путей в графа х, содержащее матричную модел графа размерностью п ж п , каждый узел которой, соДержит триггер и первый элемент И, причем ВЕ1ХОД триггера соединен с первым входом первого элемента И, а также группу из п элементов ИЛИ-НЕ,первую, вторую/ третью и четвертую группы из n элементрв И, группу из п счетчиков веса вершин, группу из п регистрирующих счетчиков, блок выбора кода максимального числа, группу из п. регистрирующих триггеров, группу из п элементов ИЛИ, элемент ИЛИ, дешифратор, первый и второй элементы И, счетчик к генератор тактовых импульсов, выход которого соединен с первыми входами первого и второго элементов И, выход первого элемента И подкачен к первым вхо,ам элементов И первой и второй групп, выход 4-го элемента ИЛИ-НЕ (i 1,п, п - раЭмерность матричной модели графа) соединен с вторым входом i-го элемента И первой группы, выход которого подключен к входу i-ro счетчика веса вершины, выход которого соединен с вторым входом i -ГО элемента И второй группы, выход последнего через i-и регистрирующий счетчик подключен к первому входу элемента И третьей группы, выход которого соединен с -{-м входом блока выбора кода максимального числа, i-й выход которого подключен к входу i-го регистрирующего триггера, выход которого соединен с первым вхо дом i-ro элемента И четвертой группы выход которого подключён к вторым входам первых элементов И уэлов i-й строки матричной модели графа, выход первого элемента И i-ro узла матричной модели графа соединен с i-M входом t-го элемента ИЛИ группы,выхОд которого подключен к второму входу i-ro элемента И третьей группы, выход элемента ИЛИ соединен с вторым входом первого элемента И/ выход второгсз элемента И через счетчик подключён к выходу дешифратора, i-и выход которого соединен со вторым входом i-ro элемента И четвертЬй группы, отличающее с я тем, что, с целью повышения быстродействия устройства, в него введены элемент НЕ, а в каждый узел матричной модели графа - второй, элемент И, выход вто- . рого элемента И узла i.-й строки подключен к i-му входу i-го элемента |ИЛИ-НЕ группы, выход i-ro счетчика веса вершин группы соединен с первыми входс1ми вторых элементов И узлов i-го столбца матричной модели графа и с f-M входом элемента ИЛИ, выход которого через элемент НЕ подключен к второму входу второго элемента И, выход триггера 1-го узла матричной модели графа соединен с вторым входом второго элемента И уз- ла матричной модели графа. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР 798854, кл. G 06 F 15/20, 1978. 2.Авторское свидетельство СССР по заявке 3007322/28-24, кл. G 06 F 15/20, 1980 (прототип).