Устройство для определения максимальных путей в графах
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
Союз Советских
Социалистических
Республик
{ii>995094, (61}Дополнительное к авт. свид-ву— (22) Заявлено 04. 08. 81 (21)3331336/18 24
f$g)+ g 3
G 06 F 15/20 с присоединением заявки ¹â€”
Государственный комитет
СССР по делам изобретений и открытий (?3) Приоритет—
Опубликовано 0702.83. Бюллетень ¹5
153) УДК 681 333 (088. 8) Дата опубликования описания.07.02.83 (72) Автор изобретения
В.A.Òèòîâ (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНЫХ
ПУТЕЙ В ГРАФАХ
Изобретение относится к вычислительной технике и может быть использовано при исследовании параметров сетевых графов.
Задача определения максимального критического пути в графе заключает» ся в определении величины и индентификации вершин, образующих этот путь.
Известно устройство для определения максимального критического пути в графе, содержащее генератор тактовых импульсов, выход которого подключен к входу первого элемента И, управляемый вход которого подключен к выходу элемента НЕ, вход которо-,. го подключен к выходу второго элемента И по числу строк и столбцов матричной модели графа цепочки из последовательно соединенных счетчика и .триггера, по числу столбцов матрич ной модели графа группы элементов И, дополнительные элементы НЕ, первые и вторые группы элементов И, дополнительные счетчики, выходы каждого из которых подключены к выходу элемента
И второй группы, управляемый вход которого подключен к выходу дополнительного элемента НЕ, выходы триггеров одноименного столбца матричной модели графа подключены к соответствующим входам группы элементов И, выход ко.торого подключен к .входу дополнительного элемента HE и управляемому входу элемента И первой группы, выход которого подключен к соответствующему входу второго элемента И и входам счетчиков одноименной строки матричной модели графа, информационные входы первьи и вторых элементов
И группы подключены к выходу первого элемента И C1 j. . Недостатками известного устройства являются необходимость перехода от графа с нагруженными вершинами к графу с нагруженными дугами, низкое быстродейстие, так как определение максимального критического пути в известном устройстве осуществляется последовательно в три этапа, первые д ва
20 иэ которых связаны с занесени исходной информации о топологии и весах дуг моделируемого граФа и подсчета импульсов в счетчиках весов дуг, а третий этап — со
25 сравнением результатов двух подсчетов в схемах сравнения.
Наиболее близким по технической сущности к предлагаемому является устройство для определения максимальЗО йых путей в графах, в состав которо995094 го входят цепочки из последовательно соединенных первого триггера и первого элемента И по числу и строк и и столбцов матричной модели графа, и элементов ИЛИ-HE n элементов ИЛИ, и вторых элементов И, счетчиков весов вершин, п третьих элементов И, регистрирующих счетчиков, четвертых элементов И, вторых триггеров, и пятых элементов И, блок выбора максимального кода, дешифратор, дополнительный счетчик, первый элемент И, второй элемент И, элемент ,ИЛИ, генератор тактовых импульсов, выход которого подсоединен к первому .входу шестого элемента И и первому входу седьмого элемента И, выход которого подсоединен к первым входам вторых элементов И и первым входам третьих элементов И, выходы первых элементов И одноименной 1-й (1 = Z и ) строки матричной модели N графа подсоединены к входам i --го элемента ИЛИ-HE выход которого подсоединен к второму входу i-го второ"
ro элемента И, выход которого подсоединен к входу1-ro счетчика ве- Я са вершины, выход которого подсоединен к вторым входам первых элементов И одноименного столбца матричной модели графа, к первому входу i-го третьего элемента И и к 1-му входу у) элемента ИЛИ, выход которого подсоединен к второму входу второго элемента И, второй вход i-ro третьего элемента И подсоединен к выходу i-го элемента ИЛИ, а выход подсоединен через регистрирующий счетчик к первому входу группы i-x четвертых элементов И, выход которой подсоединен к 1-му входу блока выбора максимального кода, -й выход которого подсоединен к входу -ro второго триггера, выход которого подсоединен к первому. входу i-ão пятого элемента
И, второй вход которого подсоединен к -му выходу дешифратора, вход которого подсоединен к выходу дополни- 45 тельного счетчика, вход которого . подсоединен к выходу первого элемента
И Г21, Цель изобретения — повышение быстродействия устройства.
59
Поставленная цель достигается тем, что в устройство для определения максимальных путей в графах, содержащее матричную модель графа размерностью и х и, каждый узел которой содержит триггер и первый элемент
И, причем выход триггера соединен с первым входом первого элемента И, а также группу из и элементов ИЛИ-HE первую, вторую, третью и четвертую Щ ,группы,из и элементов И, группу из .п счетчиков веса вершин, группу из и регистрирующих счетчиков„ блок выбора кода максимального числа, группу из 11 регистрирующих триггеров, ИЛИ, дешифратор, первый и второй элементы И, счетчик и генератор тактовых импульсов, выход которого соединен с первыми входами первого и второго элементов И, выход первого элемента И подключен к первым входам элементов И первой и второй групп, вйход i --ro элемента ИЛИ-НЕ (i= I,ï, n — размерность матричной модели графа) соединен с вторым входом i -го элемента И первой группы,.выход которого подключен к входу 1 -ro счетчика веса вершины, выход которого соединен с вторым входом i -ro элемента И второй групПы, вы<од последнего через -й регистрирующий счетчик подключен к первому входу элемента И третьей группы, выход которого соединен с 1-м входом блока выбора кода максимального числа, 1-й выход которого подключен к входу .1-го регистрирующего триггера, выход которого соединен с первым входом i-го элемента И четвертой группы, выход которого подключен к вторым входам первых элементов И узлов 1-й строки матричной модели графа, выход первого элемента И i-го узла матричной модели графа соединен с i-м вхо- дом 1 -ro элемента ИЛИ группы, выход которого подключен к второму входу i-го элемента И третьей группы, выход элемента ИЛИ соединен с вторым входом первого элемента И, выход второго элемента И через счетчик подключен к входу дешифратора, 1-й выход которого соединен с вторым входом i --ro элемента И четвертой группы, введены элемент НЕ, а в каждый узел матричной модели графа — второй элемент И выход второго элемента И узла i-u строки подключен к i-му входу i--го элемента ИЛИ-HE группы, выход i-ro счетчика веса вершин группы соединен с первыми входами вторых элементов И узлов 1-го столбца матричной модели графа и с 1-м входом элемента ИЛИ,выход которого через элемент HE подключен к втброму входу второго элемента И, выход триггера i --ro узла матричной модели графа соединен с вторым входом второго элемента И узла матричной модели графа. На чертеже представлена структурная схема устройства для определения максимальных путей в графах. Устройство содержит матричную модель 1 графа, триггеры 2 по числу строк и столбцов матричной модели графа (n x и ), первый и второй элементы И 3 и 4, по числу и столбцов матричной модели графа группу элементов ИЛИ-НЕ 5, группу из и элементов ИЛИ 6, первую группу из и элементов И 7, группу из. и счетчиков 8 весов вершины, вторую группу из и элементов И 9, группу из и ре истри. 995094 Определение вершин графа, обраэу-. ющих максимальный критический путь, .осуществляется в два этапа. На первом этапе с появлением пускового сигнала на входе 22 элемента И 16 импульсы с выхода генератора 17 поступают на входы элементов И 7 и 9. При этом импульсы проходят на все счетчики 10, так как в исходном состоянии вторые входи элементов И 9 подключены к выходам одноименных счетчиков 8, на которых появляетсясигнал переполнения. Кроме того, счетные импульсы поступают через элементы И 7 на входы тех счетчиков S, для которых триггеры 2 одноименной строки матрицы находятся s нулевом : - рующих счетчиков 10, третью группу . из и элементов И 11, группу из и ре гистрирующих триггеров 12 четвертую группу из и элементов И 13, блок 14 выбора -максимального кода числа, элемент ИЛИ 15, первый элемент Й 16, генератор 17 тактовых импульсов, элемент НЕ 18, второй элемент И 19; счетчик 20, дешифратор 21, вход 22, выход 23 ° Матричная модель 1 графа представляет собой матрицу однородных узлов, каждый из которых представляет собой триггер 2 и подсоединенные к его выходу элементы И 3 и 4.- Размер мат-, ричной модели — n и, где и — мак:симальное число вершин моделируемого графа. Устройство работает следующим образом. Первоначально в модель 1 заносится информация о топологии модулируемого графа (сети) ° При этом триггеры 2; (), = 1, и ), которые являются формирователями дуг, устанавливаются в единичное состояние, если есть информационная связь из r --й вершины в j --ю вершину. Соответствующий триг- гер 2;. определяется пересечением -й строки и 1 -го столбца.. Другие триггеры. 2(, а также счетчики 10 и 20 находятся в нулевом состоянии. В единичное состояние устанавливается также триггер 12, соответствующий начальной вершине модулируемого графа. В счетчики 8 Соответствующих вершин графа заносятся числа. импульсов, дополняющие веса вершин до полной емкости счетчиков. После занесения исходной информации на выходах элементов 5 ИЛИ-НЕ, объединяющих выходы триггеров 2,в строках, соответствующих конечный вершинам моделируемого графа, будут высокие потенциалы. Это объясняется тем, что в однонап- . равленном графе без циклов и петель конечные вершины не содержат выходящих ветвей, а следовательно, все триггеры 2 в этой строке будут в нулевом состоянии. со -"тоники Это происходит благодаря тому, что на выходе соответствующих элементов ИЛИ-НЕ 5 и на УпРавляемом входе одноименного элемента И 7 бу-дут высокие потенциалы. Отсчитав число импульсов, пропорциональное весу моделируемой вершины, счетчик 8 переполняется, и низкий потенциал с триггера переполнения (не показан) счетчика 8-подает 10 ся на вторые входы элементов И 4 одноименного столбца матричной модели 1 н одноименный вход элемента ИЛИ 15. Появление низкого потенциала на вхо» де соответствующего элемента И 9 (5 обеспечивает прекращение подачи счетных импульсов через элемент И 9 на вход регистрирующего счетчика 10, на котором фиксируется код максиМального пути из цанной вершины до ко70 нечной вершины графа сети. Вычисли,тельный процесс прбдолжается .до тех пор, пока на выходах всех счетчиков 8 не будут присутствовать низкие потенциалы. На выходе элемента ИЛИ 15 25 имеется низкий потенциал, в результате чего прекращается подача счетных импульсов с выхода генератора 17 через элемент И 16 на информационные входы Ълементов И 7 и 9. На этом первый этап работы устройства заканчивается. Второй этап работы УстРойства начинается после появления высокого потенциала на выходе элемента НЕ 18, 35 после чего счетные импульсы с выхода генератора 17 через элемент И 19 пос- тупают на вход счетчика 20, с первого выхода которого код поступает.на входы дешифратора 21. На выходе дешифра4р тора 21 возбуждаются поочередно выходные шины, которые подсоединены к первым входам соответствующих элементов И 13. Если при этом триггер 12 „. (i= 1,п) находится в единичном 45 состоянии, то высокий потенциал поступает на второй.,вход элемента И 13;. а с его выхода высокий потенциал поступает на информационные входы элементов И 3(((,j= l,n) одноименной строки матричной модели сети 1 и поступает далее через элементы ИЛИ 6 только на те управляемые входы элементов И 11, которьм в данной строке матричной модели сети соответствует дуга графа, т.е. единичное состояние триггера 2. Наличие высоких потенциалов на управляемых выходах элементов KJIH 6 обеспечивает поступление кодов с выходов счетчиков 10 на входы блока 14, который, 6@ в свою очередь, обеспечивает выбор максимального из.поступивших кодов, при этом соответствующие триггеры 12 перебрасываются в единичное состояние и т.д. Процесс поиска макси65 мального критического пути заканчи995094 вается при появлении единичного сигнала на выходе 23 (сигнал переполнения счетчика 20). Работа устройства при определении максимальных путей для всех вершин в графе поясняется следующим примером. Пусть задан граф, описываемый матрицей смежности А и вектором Т весов вершин. О 1 1 1 О О О О О О О О О. О 1 О 1 О О О О О О 0 1 1 1 0 1 О О О 0 О О О 1 О 0 0 О О О О О О 0 1 1 О О О О 0 О О О О 1 О О О 0 О О О 0 0 О 1 О О О 0 О О О О О 1 О О 0 О О О О 0 О 0 Т=(1; 3; 2; 5; 4; 3; 4; 3, 2; 2) где элементы О, если нет дуги из -й С z вершины в -ю! 1, если есть дуга из i-ой вершины в j --ю; 11 - У вес В 1 -A вершины моделиру.емого графа. 35 После занесения исходной информации на входах элемента ИЛИ-НЕ 5 имеется низкий потенциал, а на выходе — высокий. На выходах элементов ИЛИ-HE 51 — 5 9 присутствует низкий 40 потенциал, поэтому после подачи пускового сигнала на вход 22 устройства счетчика импульсы с выхода генератора 17 через элемент И 16 поступают через элементы Ц 91 — 91р на входы регистрирующих счетчиков 10 1 — 101, а также через элементы И 71в на вход .счетчика 8 „р. Через +1 - 2, с приходом второго импульса, которых заполняет до полной емкости счетчик 81О, перебрасывается н единичное состояние триггер разряда переполнения счетчика 81О, что вызывает прекращение подачи счетных импульсов на ре гистрирующий счетчик 10„О . Таким образом, на выходах элементов ИЛИ НЕ 561 59 и 510 и после при хода второго импульса с выхода генератора 17 через элементы И 7 и . 9 появляются высокие потенциалы, после чего счетные импульсы поступают также на входы счетчиков 88 и 89 и т.д. Вычислительный процесс перного этапа заканчивается с приходом четырнадцатого импульса, после чего прекращается подача счетных импульсон на вход счетчика 10 (на все другие счетчики 10 подача импульсов прекращается ранее); на выходе элемента ИЛИ 15 имеется низкий потенциал, вследствие чего прекращается подача счетных импульсов на входы счетчиков 8 и 10. Показания счетчиков 10 соответствуют максимальным величинам в графе для каждой вершины, при этом каждому номеру вершины сопоставлен счетчик. В данном случае эти показания (начиная с первого) следующие : 14; 12; 11; 13; 9; 8; 8; 5; 4; 2. На втором этапе работы устройства после появления высокого потенциала на входе элемента НЕ 18 начинается подача счетных импульсов на вход счетчика 20. Поянление первого импульса с генератора 17 через элемент на входе дешифратора 21 вызывает возбуждение первой его выходной шины, в результате чего с выхода элемента И 13 высокий потенциал поступает на управляемые входы вторых элементов И 3 первой строки матричной модели графа, поэтому на входы блока 14 поступают коды со счетчиков 10,, 103 и 10, через элементы И 11, 113 и 111 соответственно. Максимальный из ) этих кодов — код со счетчика 104 (13), поэтому в единичное состояние перебрасывается триггер 12 4 . Далее к содержимому счетчика 20 прибавляется единица и процесс продолжается до тех пор, пока не переполнится счетчик 20, после чего на выходе 23 устройства будет выдан единичный сигнал (сигнал переполнения счетчика 20). В данном примере критический максимальный путь составляет 1, 4, 7, 9 и 10 вершины, о чем свидетельствуют единичные состояния триггеров 121, 12,, 12>, 129 и 1216. Таким образом, устройство за счет введения дополнительных элементов с новыми связями обеспечивает получение нового положительного эффекта, который заключается в повышении быстродействия устройства путем исключения длительной процедуры повторного ввода матрицы смежности моделируемого графа. Формула изобретения Устройство для определения максимальных путей в графах, содержащее матричную модель графа размерностью и х n, каждый узел которой содержит триггер и первый элемент И, причем выход триггера соединен с первым входом первого элемента И, а также группу из и элементов ИЛИ-ЙЕ>первую, вторую, третью и четвертую группы из 995094 и элементов И, группу из и счетчиков веса вершин, группу из и регистрирующих счетчиков, блок выбора кода максимального числа, группу из и регистрирующих триггеров, группу из элементов ИЛИ, элемент ИЛИ, дешифратор, первый и второй элементы И, счетчик к генератор тактовых нмйульсов, выход которого соединен с первыми входами первого и второго элементов И, выход первого элемента И подключен к первым входам элементов И первой и второй групп, выход -ro элемента ИЛИ-НЕ (= J,и, n — раэмерность матричной модели графа) соединен с вторым входом i --го элемента И первой группы, выход которого под.ключен к входу i-ro счетчика веса .вершины, выход которого соединен с вторым входом i -го элемента И второй группы, выход последнего через q --й регистрирующий счегчик подключен к первому входу элемента И третьей группы, выход которого соединен с 1 -м входом блока выбора кода максимального числа, i-й выход которого подключен к входу i.-ro регистрирующего триггера, выход которого соединен с первым входом l-ro элемента И четвертой--группы выход которого подключен к вторым входам первЫх элементов И узлов -й строки матричной моделй графа, выход первого элемента И i-ro узла матричной модели графа соединен с -м входом т -го элемента ИЛИ груПпы, выход которого подключен к второму входу i -ro элемента И третьей группы, выход элемента ИЛИ соединен с вторым входом первого элемента И, выход второго элемента И через счетчик подключен к выходу дешифратора, > --й выход которого соединен со вторым входом i-го элемента И четвертой группы, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства, в него введены элемент НЕ, а в карый узел матричной модели. графа — второй элемент И выход второго элемента И узла i.-й строки подключен к -му входу i --го элемента ИЛИ-НЕ группы, выход -го счетчика веса вершин группы соединен с первыми входами вторых элементов И узлов -го столбца матричной модели 20 графа и с -м входом элемента ИЛИ, выход которого через элемент НЕ подключен к второму входу второго элемента И, выход. триггера 3-ro узла матричной модели графа соединен с 25 вторым входом второго элемента И уз ла матричной модели графа. Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР 30 9 798854, кл. G 06 F 15/20, 1978. 2. Авторское свидетельство СССР по заявке Р 3007322/28-24, кл. 6 06 F 15/20, 1980 (прототип). 995094 Составитель И.Дубинина Редактор A.Âîðîâè÷ Техред Ж.Кастелевич, Корректора.Дэнтко Заказ 646/34 Тираж 704 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж-35, раущскан наб., д.4/5 Филиал ППП Патент, r.Óæãîðîä, ул..Проектная,4
