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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеспублик р 11995094,(61) Дополнительное к авт. свид-ву -(22) Заявлено 04. 08. 81 (21)3331336/18-24 1 М Кп 3 С 06 Р 15/20 с присоединением заявки Нов Государственный комитет СССР по делам изобретений и открытийДата опубликования описания 07.02.83(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЮКСИИАЛЬНЫХПУТЕЙ В ГРАФАХ Изобретение относится к вычислительной технике и может быть использовано при исследовании параметров сетевых графов.Задача определения максимального критического пути в графе заключается в определении величины и индентиФикации вершин, образующих этот путь.Известно устройство для определения максимального критического пути в графе, содержащее генератор тактовых импульсов, выход которого подключен к входу первого элемента И, управляемый вход которого подключен к выходу элемента НЕ, вход которо-,. го подключен к выходу второго элемента И по числу строк и столбцов матричной модели графа цепочки из последовательно соединенных счетчика и ,триггера, по числу столбцовматрич ной модели графа группы элементов И, дополнительные элементы НЕ, первые и вторые группы элементов И, дополнительные счетчики, выходы каждого из которых подключены к выходу элемента И второй группы, управляемый вход которого подключен к выходу дополнительного элемента НЕ, выходы триггеров одноименного столбца матричной модели графа подключены к соответствующим входам группы элементов И, выход которого подключен к входу дополнительного элемента НЕ и управляемомувходу элемента И первой группы, выход которого подключен к соответствующему входу второго элемента И ивходам счетчиков одноименной строкиматричной модели графа, информационные входы первьи и вторых элементовИ группы подключены к выходу первогоэлемента И Г 13. Недостатками известного устройстваявляются необходимость перехода отграфа с нагруженными вершинами кграфу с нагруженными дугами, низкоебыстродейстие, так как определениемаксимального критического пути визвестном устройстве осуществляется последовательно в три этапа, первые д ва 20 иэ которы связаны с занесение исходной информации о топологии ифвесахфф дуг моделируемого граФаи подсчета импульсов в счетчиках1 весовф дуг, а третий этап - со 25 сравнением результатов двух подсчетов в схемах сравнения.Наиболее близким по техническойсущности к предлагаемому являетсяустройство для определения максималь ных путей в графах, в состав которо 995094го входят цепочки из последовательносоединенных первого триггера и первого элемента И по числу и строк и истолбцов матричной модели графа, иэлементов ИЛИ-НЕ, и элементов ИЛИ,и вторых элементов И, счетчиковвесов вершин, и третьих элементов И, регистрирующих счетчиков, ичетвертых элементов И, вторых триггеров, и пятых элементов И, блок выбора максимального кода, дешифратоР,дополнительный счетчик, первый эле"Мент И, второй элемент И, элемент,входу шестого элемента И и первомувходу седьмого элемента И, выходкоторого подсоединен к первым входам вторых элементов И и первым входам третьих элементов И, выходы первых элементов И одноименной 1-й(1 = 1, и ) строки матричной модели 2 Ографа подсоединены к входам 1-гоэлемента ИЛИ-НЕ, выход которого подсоединен к второму входу 1-го второ"го элемента И, выход которого подсоединен .к входу 1-го счетчика веса вершины, выход которого подсоединен к вторым входам первых элементов И одноименного столбца матричноймодели графа, к первому входу 1-готретьего элемента И и к 1-му входу ЗОэлемента ИЛИ, выход которого подсоединен к второму входу второго элемента И, второй вход 1-го третьегоэлемента И подсоединен к выходу 1-гоэлемента ИЛИ, а выход подсоединенчерез регистрирующий счетчик к первому входу группы 1-х четвертых элементов И, выход которой подсоединенк 1-му входу блока выбора максимального кода,-й выход которого подсоединен к входу -го второго триггера, выход которого подсоединен кпервому входу 1-го пятого элементаИ, второй вход которого подсоединенк -му выходу дешифратора, вход которого подсоединен к выходу дополнительного счетчика, вход которого,подсоединен к выходу первого элементаИ Г 21.Цель изобретения - повышение быстродействия устройства.56Поставленная цель достигаетсятем, что в устройство для определения максимальных путей в графах, содержащее матричную модель графа размерностью и х и, каждый узел которойсодержит триггео и первый элементИ, причем выход триггера соединен спервым входом первого элемента И, атакже группу из и элементов ИЛИ-ЙЕ,первую, вторую, третью и четвертую Щ.и счетчиков фвеса 1 вершин, группуиз и регистрирующих счетчиков блоквыбора кода максимального числа,группу из 11 регистрирующих триггеров,Я группу из и элементов ИЛИ, элементИЛИ, дешифратор, первый и второй элементы И, счетчик и генератор тактовых импульсов, выход которого соединен с первыми входами первого и второго элементов И, выход первого элемента И подключен к первым входамэлементов И первой и второй групп,вйход 1 -го элемента ИЛИ-НЕ ( 1= 1,и,и - размерность матричной моделиграфа) соединен с вторым входом 1 -гоэлемента И первой группы,.выход которого подключен к входу 1-го счетчика веса вершины, выход которого соединен с вторым входом 1 -гоэлемента И второй групПы, выод последнего через-й регистрирующийсчетчик подключен к первому входуэлемента И третьей группы, выход которого соединен с 1-м входом блокавыбора кода максимального числа,1-й выход которого подключен к входу1-го регистрирующего триггера, выходкоторого соединен с первым входом1-го элемента И четвертой группы,выход которого подключен к вторымвходам первых элементов И узлов 1-йстроки матричной модели графа, выходпервого элемента И 1-го узла матричной модели графа соединен с 1-м вхо-дом 1 -го элемента ИЛИ группы, выходкоторого подключен к второму входу1-го элемента И третьей группы, выходэлемента ИЛИ соединен с вторым входомпервого элемента И, выход второгоэлемента И чеоез счетчик подключен квходу дешифратора, 1-й выход которого соединен с вторым входом 1-гоэлемента И четвертой группы, введеныэлемент НЕ, а в каждый узел матричной модели графа - второй элемент Ивыход второго элемента И узла 1-йстроки подключен к 1-му входу 1-гоэлемента ИЛИ-НЕ группы, выход -госчетчика весами вершин группы соединен с первыми входами вторых элементов И узлов 1-го столбца матричной модели графа и с 1-м входом элемента ИЛИ,выход которого через элементНЕ подключен к втброму входу второгоэлемента И, выход триггера 1 -го узламатричной модели графа соединен свторым входом второго элемента И узла матричной модели графа.На чертеже представлена структурная схема устройства для определения максимальных путей в графах.Устройство содержит матричную модель 1 графа, триггеры 2 по числу строк и столбцов матричной моДели графа ( и х и ), первый и второй элементы И 3 и 4, по числу и столбцов матричной модели графа группу элементов ИЛИ-НЕ 5, группу из и элементов ИЛИ 6, первую группу из и элементов И 7, группу из. и счетчиков 8 фвесовф 1 вершины, вторую группу из и элементов И 9, группу из и ре истриОпределение вершин графа, обраэу-.ющих максимальный критический путь,осуществляется в два этапа,На первом этапе с появлением пускового сигнала на входе 22 элементаИ 16 импульсы с выхода генератора 17поступают на входы элементов И 7 .и 9.При этом импульсы проходят на всесчетчики 10, так как в исходном состоянии вторые входи элементов И 9подключены к выходам одноименныхсчетчиков 8, на которых появляетсясигнал переполнения. Кроме того,счетные импульсы поступают через элементы И 7 на входы тех счетчиков 8,для которых триггеры 2 одноименнойстроки матрицы находятся в нулевом : рующих счетчиков 10, третью группу . из и элементов И 11, группу из и ре". гистрирующих триггеров 12, четвертую группу из и элементов И 13, блок 14 выбора максимального кода числа, элемент ИЛИ 15, первый элемент Й 16, генератор 17 тактовых импульсов, элемент НЕ 18, второй элемент И 19; счетчик 20, дешифратор 21, вход 22, выход 23Матричная модель 1 графа представляет собой матрицу однородных узлов, каждый из которых представляет собой триггер 2 и подсоединенные к его выходу элементы И 3 и 4 Размер мат-, ричной модели - пм и , где и - мак:симальное число вершин моделируемого графа.Устройство работает следующимобразом.Первоначально в ь 4 одель 1 заносится информация о топологии модулируемого графа (сети)При этом триггеры 2 ц ,= 1, и ), которые являются формирователями дуг, устанавливаются в единичное состояние, если есть информационная связь из-й вершины в ) -ю вершину. Соответствующий триг- гер 2; определяется пересечением -й строки и-го столбца Другие триггеры 2( , а также счетчики 10 и 20 находятся в нулевом состоянии. В единичное состояние устанавливается также триггер 12, соответствующий начальной вершине модулируемого графа. В счетчики 8 Соответствующих вершин графа заносятся числа. импульсов, дополняющие фвесафф вершин до полной емкости счетчиков. После занесения исходной информации на выходах элементов 5 ИЛИ-НЕ, объединяющих выходы триггеров 2,в строках, соответствующих конечный вершинам моделируемого графа, будут высокие потенциалы. Это объясняется тем, что в однонап-, равленном графе без циклов и петель конечные вершины не содержат выходящих ветвей, а следовательно, все триггеры 2 в этой строке будут в нулевом состоянии. со-"тонниив Это происходит благодарятому, что на выходе соответствующихэлементов ИЛИ-НЕ 5 и на Управляемомвходе одноименного элемента И 7 будут высокие потенциалы,Отсчитав число импульсов, пропорциональное фвесу моделируемойвершины, счетчик 8 переполняется, инизкий потенциал с триггера переполнения (не показан) счетчика 8 подает.10 ся на вторые входы элементов И 4 одноименного столбца матричной модели1 н одноименный вход элемента ИЛИ 15.Появление низкого потенциала на входе соответствующего элемента И 915 обеспечивает прекращение подачи счетных импульсов через элемент И 9 навход регистрирующего счетчика 10,на котором Фиксируется код максиМального пути из данной вершины до ко"20 нечной вершины графа сети, Вычисли,тельный процесс прбдолжается .до техпор, пока на выходах всех счетчиков8 не будут присутствовать низкие по"тенциалы. На выходе элемента ИЛИ 1525 имеется низкий потенциал, в результате чего прекращается подача счетныхимпульсов с выхода генератора 17 через элемент И 1 б на информационныевходы Ълементов И 7 и 9. На этомпервый этап работы устройства заканчивается. Второй этап работы устройства начинается после появления высокогопотенциала на выходе элемента НЕ 18, 35 после чего счетные импульсы с выходагенератора 17 через элемент И 19 пос-тупают на вход счетчика 20, с первоговыхода которого код поступает.на входы дешифратора 21. На выходе дешифра О тора 21 возбуждаются поочередно выходные шины, которые подсоединенык первым входам соответствующих элементов И 13. Если при этом триггер12( 1= 1,п) находится в единичномсостоянии, то высокий потенциал поступает на второй, вход элемента И 13;,а с его выхода высокий потенциал поступает на информационные входы элементов И 3(,= 1,о) одноименной строки матричной модели сети 1и поступает далее через элементыИЛИ б только на те управляемые входыэлементов И 11, которым в даннойстроке матричной модели сети соответствует дуга графа, т.е. единичное состояние триггера 2. Наличие высоких потенциалов на управляемых выходах элементов ИЛИ б обеспечиваетпоступление кодов с выходов счетчиков 10 на входы блока 14, который, 6 ф в свою очередь, обеспечивает выбормаксимального из.поступивших кодов,при этом соответствующие триггеры12 перебрасываются в единичное состояние и т.д. Процесс поиска макси мального критического пути заканчи 995094вается при появлении единичного сигнала на выходе 23 (сигнал переполнения счетчика 20).Работа устройства при определении максимальных путей для всех вершин в графе поясняется следующим примером,Пусть задан граф, описываемый матрицей смежности А и вектором Т весов вершин. 10 0111000000 000.0101000 0000111010 0000001000 0000000110 0000000010 0000000001 20 0000000001 0000000000 Т=1 р Зу 2 у 5 р 4 у Зр 4 у 3) 2 у 2),где элементыО, если нет дуги из-й С г вершины в 1 -ю 1, если есть дуга из -ой вершины в-ю; Ф; -вес-й вершины моделиру.емого графа, 35После занесения исходной информации на входах элемента ИЛИ-НЕ 5 имеется низкий потенциал, а на выходе - высокий, На выходах элементов ИЛИ-НЕ 51 - 5 9 присутствует низкий 40 потенциал, поэтому после подачи пускового сигнала на вход 22 устройства счетчика импульсы с выхода генератора 17 через элемент И 16 поступают через элементы Ц 91 - 91 р на входы регистрирующих счетчиков 10 1 - 10 1 о, а также через элементы И 71 о на вход .счетчика 8 р. Через Ф 1 О: 2, с приходом второго импульса, которых заполняет до полной емкости счетчик 81 О, перебрасывается н единичное состояние триггер разряда переполнения счетчика 81 О, что вызывает прекращение подачи счетных импульсов на ре гистрирующий счетчик 10 О . 55Таким образом, на выходах элементов ИЛИ-НЕ 5 вр 59 и 10 и после при хода второго импульса с выхода генератора 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.Таким образом, устройство за счет введения дополнительных элементов с новыми связями обеспечивает получение нового положительного эффекта, который заключается в повышении быстродействия устРойства путем исключения длительной процедуры повторного ввода матрицы смежности моделируемого графа.Формула изобретенияУстройство для определения максимальных путей в графах, содержащее матричную модель графа размерностью и х ь , каждый узел которой содержит триггер и первый элемент И, причем выход триггера соединен с первым входом первого элемента И, а также группу из и элементов ИЛИ"ЙЕпервую, вторую, третью и четвертую группы изи элементов И, группу из и счетчиков ффвесаф вершин, группу из и регистрирующих счетчиков, блок выбора кода максимального числа, группу из и ре-.гистрирующих триггеров, группу из я элементов ИЛИ, элемент ИЛИ, дешифратор, первый и второй элементы И, счетчик к генератор тактовых нмйульсов, выход которого соединен с первыми входами первого и второго элементов И, выход первого элемента И подключен к первым входам элементов И первой и второй групп, выход -го элемента ИЛИ-НЕ (= р, и - раэмерность матричной модели графа) соединен с вторым входом-го элемента И первой группы, выход которого под.ключен к входу -го счетчика ффвеса .вершины, выход которого соединен с вторым входом 1 -го элемента И второй группы, выход последнего через-й регистрирующий счегчик подключен к первому входу элемента И третьей группы, выход которого соединен с 1 -м входом блока выбора кода максимального числа, -й выход которого подключен к входу -го регистрирующего триггера, выход которого соединен с первым входом -го элемента И четвертой.группы выход которого подключен к вторым входам первЫх элементов И узлов "й строки матричной моделй графа, выход первого элемента И г-го узла матричной модели графа соединен с -м входом т -го элемента ИЛИ груПпы, выходкоторого подключен к второму входу-гоэлемента И третьей группы, выходэлемента ИЛИ соединен с вторым вхо"дом первого элемента И, выход второго элемента И через счетчик подключен к выходу дешифратора,-й выходкоторого соединен со вторым входом-го элемента И четвертой группы,о т л и ч а ю щ е е с я тем, что,с целью повышения быстродействияустройства, в него введены элементНЕ, а в каядый узел матричной модели.графа - второй. элемент И выход второго элемента И узла .-й строки подключен к-му входу-го элементаИЛИ-НЕ группы, выход -го счетчикавеса вершин группы соединен спервымивходами вторых элементов Иузлов-го столбца матричной модели20 графа и с -м входом элемента ИЛИ,выход которого через элемент НЕ подключен к второму входу второго элемента И, выход. триггера 1-го узламатричной модели графа соединен с25 вторым входом второго элемента И узла матричной модели графа.Источники информации,принятые во внимание при экспертизе1, Авторское свидетельство СССР30 9 798854, кл. 6 06 Р 15/20, 1978.2. Авторское свидетельство СССРпо заявке 9 3007322/28-24,кл. 6 Об Г 15/20, 1980 (прототип).995094 Составитель И.Дубининарович Техред Ж,Кастелевич КорректорА.Дэят акт ак илиал ППП Патент, г.ужгород, ул.,Проектная 646/34 Тираж ВНИИПИ Государс по делам изобр 113035, Москва, Ж704веннотений35, Ра оми ткр кая Подписноеета СССРтийнаб., д,4/5