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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИН 386 4 б 06 Р 15 2 ОПИСАНИЕ ИЗОБРЕТЕНИЯК А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ Г. исследовании па Целью изобрет быстродействия ления величины рирующих счетч шин критическог этап. Устройстводель графа 1, гру группу элементо ров 7, группу р тов 8 И первую геров, группу сч группу счетчико элемент 14 ИЛ тор 16 тактовых М. Злоб льство СССР 15/20, 1982. ство СССР 15/20, 1983. ДЛЯ ОПРЕДЕЛЕ Х ПУТЕЙ В ГРА ится к вычислительть использовано при ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(57) Изобретение относной технике и может бь ра метров сетевых графов. ения является повышение устройства за счет опредекритического пути в регистиках и идентификации веро пути в регистрах в одинсодержит матричную моппу элементов 5 ИЛИ - НЕ, в 6 ИЛИ, группу шифратоегистров 9, группу элемен и вторую 12 группы тригетчиков веса вершины 11, в максимального пути 13, И, элемент 15 И, генераимпульсов, вход 17. 1 ил.1383386 0111001001 0010110000 0000010010 0000001000 0000011001 0000000101 0000000111 0000000001 0000000001 0000000000 40 45 1Изобретение относится к вычислительной технике и может быть использовано для исследования параметров сетевых графов.Задача определения максимального критического пути в графе заключается в определении значения величины и идентификации вершин, образующих этот путь.Целью изобретения является повышение быстродействия за счет определения величины критического пути в регистрирующих счетчиках и идентификации вершин критического пути в регистрах в один этап,На чертеже представлена структурная схема устройства для определения максимальных путей в графах.Устройство содержит матричную модель 1 графа, каждый узел которой содержит триггер 2, соединенный через элемент 3 задержки с элементом И 4, группы элементов ИЛИ - НЕ 5 и ИЛИ 6 и группу шифраторов 7, соответствующим образом соединенных с матричной моделью графа, группу элементов И 8, группу регистров 9, первую группу триггеров 10, соединенных с группой счетчиков 11 веса вершины, которые через вторую группу триггеров 12 соединены с группой счетчиков 13 максимального пути, элементы ИЛИ 14 и И 15, генератор 16 тактовых импульсов, вход 17.Устройство работает следующим образом.Первоначально в модель 1 заносится информация о топологии моделируемого графа. При этом триггеры 2 (1, 1= 1;и), которые являются формирователями дуг, устанавливаются в единичное состояние, если есть информационная связь на 1-й вершины в 1-ю вершину. Соответствующий триггер 2 определяется пересечением 1-й строки и 1-го столбца. Другие триггеры 2,. а также триггеры 1 О и счетчики 13 устанавливаются в нулевое состояние. Триггеры 12 устанавливаются в единичное состояние. В счетчики 11, которые соответствуют вершинам графа, заносятся числа импульсов, дополняющие веса вершин до полной емкости счетчиков.После занесения исходной информации на выходах элементов ИЛИ - НЕ 5,объединяющих выходы триггеров 2 в столбцах, соответствующих начальным вершинам моделируемого графа, присутствуют высокие потенциалы. Это объясняется тем, что в однонаправленном графе без циклов и петель начальные вершины не содержат входящих ветвей, а, следовательно, все триггеры 2 в этом столбце находятся в нулевом состоянии.Определение вершин графа, образующих максимальный критический путь и величины этого пути, осуществляется следующим образом. С появлением пускового сигнала на входе 17 счетные импульсы начинают поступать на счетчики 13 (так как триггеры 12 находятся в единичном состоянии и на синхронизирующие входы счетчиков 13 подаются высокие потенциалы) и на счетчик 11 веса начальной вершины (так как пусковой сигнал через элемент ИЛИ 6 и элемент И 8 2устанавливает управляющий триггер 10 в единичное состояние) . Отсчитав число импульсов, пропорциональное весу моделируемой вершины, счетчик 11 переполняется и импульсом переполнения устанавливает триг гер 12 и все триггеры 2 одноименной строки в нулевое состояние, Низкий потенциал с выхода триггера 12 останавливает отсчет импульсов счетчиком 13, на котором фиксируется код максимального пути от началь ной вершины до данной вершины. Импульс переполнения со счетчика веса моделируемой вершины через элементы И одноименной строки матричной модели графа, триггеры 2 которой установлены в единичное состояние, поступает на одноименные входы элемента ИЛИ 6 и шифратора 7, переводя при этом триггеры 2 соответствующей строки в нулевое состояние. В регистр 9 записывается код предыдущей вершины, из которой имеется информационная связь в 20 данную вершину. При этом отсчет импульсовпроисходит в тех счетчиках 11 веса вершин, вершины которых не имеют входящих ветвей (т.е, все триггеры одноименного столбца матричной модели графа находятся в нулевом состоянии) . Вычислительный процесс заканчивается после того, как все триггеры 12 перебросятся в нулевое состояние.После этого на выходе элемента ИЛИ 14 появлятся низкий потенциал, который запрещает прохождение счетных импульсов с генеЗ 0 ратора тактовых импульсов.Устройство при определении величиныкритического пути и идентификации вершин работает следующим образом.Пусть задан граф, описываемый матрицей смежности А и вектором Т весов вершин. Т =/2, 1,6,4,2, 5, 2,4, 1,21, где элементы О, если нет дуги из 1-й вершины в 1-ю;а =501, если есть дуга из 1-й вершины в 1-ю;1; - вес 1-й вершины моделируемого графа,После занесения исходной информации навходе элемента ИЛИ - НЕ 5, имеется низхий потенциал, а на выходе - высокий. На 55 выходах элементов ИЛИ - НЕ 5 - 5 о присутствует низкий потенциал, поэтому после подачи пускового сигнала на вход 17 пусковой импульс разрешает прохождение счетных импульсов с генератора 16 тактовых1383386 4шины, о чем свидетельствуют показания регистров 9 - 9 з, 96, 9 в и 9 шформцла изобретенияУстройство для определения максимальных путей в графах, содержащее матричную модель графа, состоящую из пХп узлов, где п - максимальное число вершин моделируемого графа, группу п элементов ИЛИ - НЕ, группу и, элементов ИЛИ, группу п элементов И, группу и счетчиков веса вершины, 10 группу и счетчиков максимального пути,элемент И, элемент ИЛИ, генератор тактовых импульсов, причем каждый узел матричной модели графа содержит триггер и элемент И, отличающееся тем, что, с целью повышения быстродействия, в него введены первая и вторая группы триггеров, по и триггеров в каждой, группа и шифраторов, группа и регистров, причем в каждый узел матричной модели графа введен элемент задержки, информационный вход 1-го регистра группы (1= 1, и) соединен с выходом 1-го шифратора группы, 1-й вход (1= 1, и) которого соединен с 1-м входом (1= 1, и) 1-го элемента ИЛИ группы и выходом элемента И 1-го узла матричной модели графа 1-го столбца, первый вход элемента И 11-го узла (1= 1, и, 1= 1, и) соединен с выходом элемента задержки этого же узла, вход которого соединен с выходом триггера этого же узла и 1-м входом (1= 1, и) 1-го (1= 1, и) элемента ИЛИ - НЕ группы, выход которого сое 3импульсов через элемент И 15 на счетчики 13 максимального пути и счетчики 11 весов вершин, кроме того, пусковой импульс поступает на нулевой вход элемента ИЛИ 61 и через одноименный вход шифратора 71 код данного входа записывается в регистр 9 ь Импульс с выхода элемента ИЛИ 6 через элемент И 8, поступает на вход установки в единицу триггера 10 ь Высокий потенциал с выхода триггера 101 поступает на вход синхронизации счетчика 111 и разрешает отсчет импульсов этим счетчиком. С приходом второго импульса, который заполняет до полной емкости счетчик 11 ь на его выходе появляется импульс переполнения, который перебрасывает триггер 121 в нулевое состояние и тем самым запрещает отсчет счетных импульсов счетчиком 13. Кроме того, импульс переполнения со счетчика 111 через эле менты И 4 узла матричной модели графа, одноименные триггеры 2 которых установлены в единицу, поступает на первые входы одноименных элементов ИЛИ 6 и шифраторов 7, устанавливая при этом все триггеры 2 первой строки матричной модели графа в нулевое состояние. Таким образом, на выходах элементов ИЛИ - НЕ 5 и 54 появляется высокий потенциал, который открывает элементы И 82 и 84 и разрешает прохождение импульсов с выхода элементов ИЛИ 62 и 64 на триггеры 102 и 104, которые, установившись в единицу, разрешают отсчет импульсов счетчикам 11 и 11 весов вершин. При этом в регистры 92 и 94 записывается код первой вершины графы.Вычислительный процесс заканчивается с приходом 20-го импульса, после чего прекращается отсчет импульсов счетчиком 13. На выходе элемента ИЛИ 14 появляется низкий потенциал, который запрещает прохождение счетных импульсов с генератора 16 тактовых импульсов через элемент И 15 на счетчики весов вершин 11 и максимального пути 13. Показания счетчиков 13 соответствуют максимальным величинам путей в графе от первой вершины до данной. В регистрах 9 содержится код номера предыдущей вершины на максимальном пути. При этом каждому номеру вершины сопоставлен свой счетчик и регистр. В данном случае показания счетчиков следующие (начиная с первого): 2, 3, 9, 6, 5, 14, 8, 18, 10, 20, а показания регистров: О, 1, 2, 1, 2, 3, 4, 6, 7, 8.В данном примере критический максимальный путь составляет 1, 2, 3, 6, 8, 10 вер 30 35 40 45 50 динен с первым входом 1-го элемента И группы, второй вход которого соединен с выходом 1-го элемента ИЛИ группы, выход 1-го элемента И группы соединен с входом установки в 1 1-го триггера первой группы, выход которого соединен с входом синхронизации 1-го счетчика веса вершины, выход которого соединен с вторыми входами элементов И и входами установки в О триггеров узлов 1-й строки матричной модели графа и входом установки в О 1-го триггера второй группы, выход которого соединен с входом синхронизации 1-го счетчика максимального пути группы и с 1-м входом (1= 1, и) элемента ИЛИ, выход которого соединен с первым входом элемента И, второй вход которого соединен с выходом генератора тактовых импульсов, третий вход элемента И является входом пуска устройства и соединен с и+ 1-м входом первого =1) элемента ИЛИ группы, выход элемента И соединен со счетными входами всех счетчиков максимального пути группы и со счетными входами счетчиков веса вершины группы.Составитель С. Кошелев Редактор Н. Лазаренко Техред И. Верес Корректор И. Муска Заказ 915/49 Тираж 704 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж - 35, Раушская наб., д. 4/5 Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4