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

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

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

Цель достигается за счет того, что исследование графа производится по гибкому циклу работы (длительность гибкого цикла работы определяется соотношением Т 2тТц, где m - количество максимальных сильно связ- пых подграфов в графе, ).

На фиг.1 представлена структурная схема устройства; на фиг.2 - структурная схема блока записи; на фиг.З - структурная схема блока управления.

Устройство содержит матрицу 1 п хп (п - количество вершип графа) моделей дуг, каждая из которых состоит из элемента ИЛИ 2, триггера 3, первого 4 и второго 5 элементов И, п.ервую 6 и вторую 7 группы элементо WlHj группы триггеров прямого 8 и обратпого 9 отображения, элемент 10 задержки, группу элементов, И 11, блок 12 записи, -блок 13 управления.

генератор 1А тактовых импульсов. Блек 12 записи содержит дешифратор 15, п групп элементов И 16, группу регистров 17. Блок 13 управления содержит первьй 18, второй 19 и третий 20 элементы И, первую группу эле- ментов И 21, .Т-триггер 22, триггер 23 работы вторую группу элементов И 24, счетчик 25,, регистр 26 состояния.

На чертежах также обозначены вход 27 блока записи, группа 28 адресных входов блока записи, группа 29 информационных входов блока записи, пер- вьш 30 вход блока управления, группа 31 входов блока управления, второй 32 вход блока управления, первый 33 выход блока управления, первая 34 и оторая 35 группы выходов блока управления, второй 36 выход блока управления.

Устройство для моделирования графов работает следующим образом.

Первоначально в матрицу 1 заносится информация о топологии графа путем установки соответствую1Ц их триггеров 3 в единичное состояние. Триггер 3,-у (i,,n) определяется пересечением строки с номером i, равным номеру

12788802

начальной вершины модел1 руемой дуги и столбца с номером j, равным номеру ее конечной вершины. Триггеры В и 9 находятся в нулевом состоянии. ; с подачей пускового игатульса на второй вход 32 блока управления (БУ), являющегося входом запуска устройст

5

0

5

0

5

0

ва, осуществляется сброс регистров 17 блока 12 записи, счетчика 25 блока I3 управления и установка в единичное состояние всех разрядов регистра 26 состояния. Высокие потенциалы с единичных выходов всех разрядов регистра 26 состояния через элемент И 19 устанавливают в единич- . вое состояние триггер 23 работы, единичное состояние которого определяет период работы всего устройства, .

Высокий потенциал с прямого выхода триггера 23 работы разрешает прохождение через элемент И 20 тактовых импульсов, поступающих с генератора 14 на вход 30 блока 13. Сигналы с выхода элемента И 20 поступают на счетный вход триггера 22. При наличии высокого потенциала на его прямом выходе выполняется цикл выделения очередного макс1-1мального сильно связанного подграфа из моделируемого графа, а при наличии высокого потенциала на его инверсном выходе выполняется цикл записи номе- . ров вершин выделенного подграфа в блок 12 записи.

ЦIiкл выделения максимального си-пь- но связного подграфа, содержащего i-ю вершину .х;, выполняется путем пересечения прямого и обрат- Г fx; транзитивных замыканий.

„

иого

Выбор i-й вершины осуществляется элементами И 2 .блока 13. Ес,пи i-й элемент И 21 (в начале работы первый элемент И 21) имеет на обоих входах высокий потенциал, то сигнал с его 5 выхода через i-й выход 34 блока 13 , подается на входы i-x элементов lUlU 6 и 7 и далее на единичные входы . триггеров 8; и.9;, единичное состояние i-x триггеров 8 и 9 означает вы,- бор i-й верЕшны графа, для которой будет осуществляться выделение максимального сильно связного подграфа,

0

Построение множества Г осуществляется подачей высокого потенциала с единичного выхода триггера 8j на вторые вхоДы элементов И 4 одноименной строки матрицы 1,

за счет чего при шличии дуги из i-й вершины графа в j-ra (i, j 1 , n), что соответствует единичному состоянию триггера , высокий потенциал с выхода элемента И 4 через элемент ИЛИ 6 перебрасывает в единичное состояние триггер 8;, с выхода которого высокий потенциал поступает на вторые входы элементов И строки матрицы 1, и так до-тех пор, пока существует путь из j-й вершины в очередную и т.д. Вершинам, об- paзyющи прямое транзитивное замыкание для i-й вершины графа, соответствуют единичные состояния тригге- ров 8..

Л р -л

Построение множества Г x;j производится одновременно подачей высокого потенциала с выхода триггера 9 на вторые входы элементов И 5 одноименного столбца матрицы 1, за счет чего при наличии дуги в i-ю вершину из k-й (i, , n) высокий потенциал с выхода элемента 7 перебрасывает в единичное состояние триггер , с выхода которого высокий потенциал поступает на вторые входы элементов И 5 k-ro столбца матрицы 1, и так до тех пор, пока имеются дуги из предшествующих вершин в данную. Вершинам, образующим обратное транзитивное замыкание для i-й вершины графа, соответствуют единичные состояния триггеров 9

22 входе счетчика подключен элемент задержки, обеспечивающий задержку сигнал на время цикла записной увеличивает значение счетчика на единицу, новый адрес записи с второй группы выходов 35 блока 13 через группу адресных входов 28 блока 12 поступает на дешифратор 15. Сигнал с выхода дешифратора 15 подается на входы тех элементов И 16, номер строки

40

Далее выполняется цикл записи. По приходу следующего тактового импульса на элемент И 20 блока 13 триггер 22 перебрасывается в противоположное состояние. Сигнал записи с инверсного выхода триггера 22 через выход 33 блока 13 подается на вход элемента 10 задержки и на третьи входы элементов И 11. Пересечение прямого и обратного транзитивных за- 5 которых совпадает с адресом записи, мыканий осуществляется совладением На этом цикл записи кончается, высоких потенциалов на входах со- По следующему тактовому импульсу ответствующих элементов И 11. Верши- триггер 22 блока 13 устанавливается

в единичное состояние н выполняется 50 следующий цикл выделения максимального ошьно связного подграфа. Прн этом,так как высокий потенциал появляется на выходе только того i-ro элемента И 21, для которого соответ- 55

ны, входяише в выделен}1ыи максимальный сильно связный подграф, определяются высокими потенциалами.на выходах oднoимe п ыx элементов И 11. Эти сигналы поступают на группу информационных входов 29 блока 12, которая соединена с первыми входами соответствующих элементов И группы 16. Запись информации осуп;ествляет- ся в тот регистр 17 (, т, где т- количество максимальных сильно связствующий элемент И 24 1шеет на выходе также высокий потеициаЛ у очередной мак симальньш сильно связный подграф будет выделяться для вершины Х; , не вошедшей в ранее выделенные подграных подг рафов в графе), входные элементы И 16 которого открыты сигналом с выхода дешифратора 15 (в начале работы в первый регистр 17). Еди- ничное значение j -го разряда регистра 7g показьгоает, что j-я вериина графа входит в выделенньп максимальный сильно связный подграф с номером Е.

Высокий потенциал с выхода i-ro элемента И 11 через элементы ИЛИ 2. осуществляет сброс триггеров 3 i-й строки и i-ro столбца матрицы 1, исключая тем самым i-ю вершину графа из дальнейшего рассмотрения. Высокие потенциалы, появляюпцшся на выходах тех элементов И 11, номера кото- рых соответствуют вершинам исходного графа, выделенным в максимальный

сильно связный подграф, через группу входов 3 блока 13 поступают на входы установки в пуль соответствующих разрядов регистра 26. Установленньш в нулевое состояние i-й разряд регистра 26 указывает, что i-я вершина исходного графа входит в один из выделенных подграфов. Задержанный элементом 10 задержки сигнал записи поступает на нулевые входы всех триггеров 8 и 9, осуществляя тем самым подготовку для последующей работы устройства. Един1этный сигнал с инверсного выхода триггера 22 поступает также на вход счетчика 25 (причем на

входе счетчика подключен элемент задержки, обеспечивающий задержку сиг нал на время цикла записной увеличивает значение счетчика на единицу, новый адрес записи с второй группы выходов 35 блока 13 через группу адресных входов 28 блока 12 поступает на дешифратор 15. Сигнал с выхода дешифратора 15 подается на входы тех элементов И 16, номер строки

которых совпадает с адресом записи, На этом цикл записи кончается, По следующему тактовому импульсу триггер 22 блока 13 устанавливается

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

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

1 ;

Процесс продол;кается до тех пор, пока все разряды регистра 26 блока 3 -не будут установлены в нулевое состояние. При нг(личии высоких потенциалов на инверсных выходах всех разрядов регистра 26 на выходе элемента И 18 блока 13 формируется сиг- пап, который поступает на вход установки в пуль триггера 23 и сбрасывает его, устройство прекращает работу.

Формула ц. 3 о б р е т е н и я

Устройство для моделирования графов, содержащее матрицу пхп (п - количество верши графа) моделей дуг. калодая из которЕ 1Х состоит из триггера, первого и второго элементов И, элемента 1ШИ, первую и вторую группы элементов ИЛИ, группу триггеров прямого и группу триггеров обратного отобралшний, группу элементов И, элемент задержки, генератор тактовых импульсов, блок записи состоящий из п групп элементов И, группы регистров, и дешифратора, блок .управления, состоящий из регистра состояния, первого, второго и третьего элементов И, первой группы элементов И, Т-триггера,триггера работы и счетчика, причем в каждой модели дуги выход элемента ИЛИ подключен к входу установки в I триггера, прямой выход которого соедипен с первыми входами первого и второго элементов И, выход первого элемента И Кс1йодой 1-й модели дуги j-ro столбца (i, ,n) мaтpиlI lI моделей дуг соединен с i-м входом j-ro элемента ИЛИ первой группы, выход которого подключен к входу установки в 1 j-ro триггера прямого отображения группы, выход которого соединен е BTOpbWi-s входами первых элементов И i-й строки матрицы моделей дуг () и первым входом j-ro элем ён- та И группы, выход второго элемента Н каждой j-й модели дуги i-й строки матрицы моделей дуг соединен с J-M входом i-ro элемента 1-ШИ второй группы, выход которого подключен к входу устаноБки в 1 i-ro триггера обра ;ного отображения группы, выход которого соединен с вторыми входами вторых элементов И j-ro столбц матр.ицы моделей дуг (j i) и вторым

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

входами второго элемента И блока управления, выход которого подключен к входу установки в 1 триггера работы, разрядные выходы второй группы выходов регистра состояния со- единены с одноименными входами первого элемента И блока управления, выход которого подключен к входу установки в О триггера работы, выход которого соединен с первым входом

третьего элемента И блока управле- пия, выход которого подключен к счетному входу Т-триггера, прямой выход которого соединен с первыми входами элементов И первой группы блока управления, инверсн1 1Й выход Т-триггера соединен со счетным входом счетчика, с входом элемента задержки и с третьими входами элементов И группы, вгэ1ход каладого i-ro элемента И группы подключен к i-му входу первой группы информационных входов регистра состояний, второй вход третьего элемента И блока управления подключен к выходу генератора тактовых импульсов, установочный вход счетчика, входы второй группы информационных входов p erijCTpa состояний и первые группы информационных входов всех регистров группы блока записи объединены и являются входом запуска устройства, выход каждого i-ro элемента И первой группы блока управления подключен к (п+1)-м входам i-x элементов ИЛИ первой и второй групп,

выход элемента задержки подключен к входам установки в О триггеров

обратного отображения группы и триггеров прямого отобр.эжения группы, выход i-ro элемента И группы подключен

45 к первым входам элементов ИЛИ моделей дуг i-й строки матрицы моделей дуг и к вторьм входам элементов ИЛИ моделей дуг i-ro столбца матрицы моделей дуг, выход i-ro элемента И

50 группы подключен к первому .входу

i-ro элемента И каждой из групп блока записи, вторые входы элементов И i-й группы блока записи объединены и подключены к i-му вы55 ходу .дешифратора, группа входов которого подключена к группе выходов счетчика, выход каждого j-ro элемента И i-й группы блока записи подключен к j-му входу второй группы

. 71

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

788808 .

второму входу (i+l)-ro элемента И первой группы блока управления, первый разрядньй выход первой группы выходов регистра состояния соединен 5 с вторым входом первого элемента И первой группы блока управления,-рач- рядпые выходы второй группы выходов регистра состояния, кроме последнего, подключены к соответствующим вхо О дам элементов И второй группы блока управления.

n.jl T

-.l-JL-. -J--I-I

.

O ixZlS n

L OE-Ci

J 772 Sir,- Sffi Фиг.Л

Редактор В.Иванова

Составитель Т.Сапунова

Техред Л.Кравчук Корректор О.Луговая

Заказ 6841/49 Тираж 671Подписное

БШМТИ Государственного комитета СССР

по делам изобретеннй к открытий 113035, Москва, м-35, Раушская наб., д. 4/5

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

22

Изобретение относится к облас-- ти вычислительной техники и может быть использовано для решения задач выделения максимальных сильно связ- ных подграфов. Целью изобретения является повышение быстродействия устройства. Это достигается введением в блок управления второй группы элементов И вйесто сдвигающего регистра. Устройство для моделирования графов содержит матрицу п хп моделей дуг, две группы элементов ГШИ, группу элементов И, группу триггеров прямого отображения, группу триггеров обратного отображения, элемент задержки, блок записи, блок управления и генератор тактовых импульсов. 3 ил. о р (О с