Устройство для исследования графов

(57) Иэобрет вычислительн использовано в частности, ности графа чия циклов в е относится к областитехники и может быть 2Трудовогорственныйнаипницкий,ля исследования графов,ля определения доступя любой вершины, налирафе и максимального ен Фиков,чинский олни ригг ей и имеет твие льство ССС 5/20, 1975 ство СССР 5/20, 1971 СЛЕДОВАНИЯ ност опре и на ГОСУДАРСТ 8 ЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ АВТОРСКОМУ СВИДЕТЕЛЬСТВ(46) 15.11.86. Бюл. В (71) Белорусский орден Красного Знамени госуд университет им.В.И.Лен (72) С.Ю.Головин, А.С. Г.Я.Лопатов, А.М.Никон В.Ф.Ранчинский, Г.Н.Че Г.И.Епаковский и С.С.З (53) 681.333(088.8) (56) Авторское свидете У 643880, кл. С 06 Р 1Авторское свидетель У 408312, кл, О 06 Р 1 (54) УСТРОЙСТВО ДЛЯ ИС ГРАФОВ,801270763 графе. Цель изобретения - псе быстродействия. Для достиуказанной цели устройство доельно содержит элементы ИЛИ, И, ры состояния, блоки записи свяблок связи. Данное устройство в 2,5 раза большее быстродейи, кроме определения доступ- любой вершины графа, позволяетс лять максимальный путь в графе щ чие циклов в нем, 6 ил.1270763 1Изобретение относится к вычислительной технике и может быть иснользовано для исследования графов, в частности для определения доступности графа для любой вершины наличия циклов в графе и максимального пути в графе.Цель изобретения - повьппение быстродействия.На фиг, 1 приведена функциональ- О ная схема предлагаемого устройства для исследования графов; на фиг, 2 - структура блока связи; на фиг. 3 - структура узла связи; на фиг. 4 - структура блока записи связей; на 15 фиг. 5 - элемент связи; на фиг. 6 - временные диаграммы. 4 ункциональная схема устройства для исследования графов включает 20 счетчик 1, линию 2 задержки, управляемые ключевые элементы 3, триггеры 4, тактовый вход 5 устройства, вход 6 начальной установки устройства, вы" ход 7 конца испытания устроиства,и 25 элементы ИЛИ 8, первый многовходовой элемент ИЛИ 9, второй многовходовой элемент ИЛИ 10, третий многовходовой элемент ИЛИ 11, элемент НЕ 12, триггеры 13 состояния, элемент И 14, 30 входы 15 состояния (вторые информационные входы) устройства, блоки 16 записи связей, блок 17 связи, входы 18 изменения адреса (вход задания логической единицы) устройства, входы З 5 19 задания режима, первые информационные входы 20 (ответа), входы 21 разрешения записи, информационные выходы 22 блоков записи связей и адресные входы блока связи, выходы ответа блока связи,и входы ответа блока записи связей 23, выходы запроса блока записи связей и входы запроса бло". ка связи 24, входы 25 ответа блока связи, выходы 26 запроса блока связи, 45 модели вершин 27.1-27.2 И, вход, 28 сброса блока связи. Блок 17 связи включает регистры29 образующие пары регистров 30.1 Ф50ЗО.Я, блок 31 синхронизации, узлысвязи 32,1, 1-32, ЫМ, образующиематрицу ЯхМ, входы 33 ответа узласвязи, выходы 34 ответа узла связи,выходы 35 запроса узла связи, входы36 запроса узла связи, адресные вы 55ходы 37 узла связи, адресные входы 38узла связи, входы,39 синхронизацииузла связи,3Схема узла 32 связи включает элементы И 40, образующие группы элементов И 41.1-41.2, элементы связи 42,1"42,2, второй вход ответа узла 43 связи, второй выход 44 ответа узла связи, первый адресный вход 45 элементасвязи, второй адресный вход 46 элемента связи, первый вход 47, второйвход 48.Функциональная схема блока 15записи связей включает узел 49памяти, элемент ИЛИ 50, счетчик 51адреса, элемент 52 сравнения, регистр53, вход 54 сброса тактовый вход 55,функциональная схема элемента 42связи включает первый элементИЛИ 56, элемент 57 запрета, первыеэлементы И 58, второй триггер 59,мультиплексор 60, второй элементИЛИ 61, первый триггер 62, вторыеэлементы И 63,Рассмотрим функционирование устройства при определении максимального пути в графе по фиг, 1, Исходное состояние блоков устройства .следующее. В счетчике 1 находится О, который заносится сигналом с шины 6, одновременно приводящем в состояние готовности блок 17 связи через элемент ИЛИ 11. В блоки 16 записи связей занесены исходящие связи соответствующих вершин в виде двоичных номе" ров вершин, связанных с данной. Функционированйе блока 16 записи связей при записи рассмотрим по фиг. 4.Исходящие связи заносятся через вход 20. Адрес записи очередной исходящей связи определяется содержанием счетчика 51, которое наращивается при помощи подачи единиц на вход 18, После записи последней ис- ходящей связи в счетчик 51 добавляется еще одна 1 и в регистр 53 заносится новое содержимое счетчика 51 при помощи подачи разрешающего сигнала на вход 21. Режим записи в узле 49 памяти определяется состоянием шины 19. В исходном состоянии содержимое счетчика 51 равно О, те. он указывает на адрес хранения первой исходящей связи, Если некоторая вершина не имеет исходящих связей, то содержимое счетчика 51 будет равно содержимому регистра 53 и тогда схема 52 сравнения вырабатывает О на инверсном выходе. Если у данной вершины имеется хотя бы одна исходящая связь, то содержИ- мое счетчика 51 в исходном состояниии регистра 53 не совпадают и на инверсном выходе схемы 52 сравнениябудет 1, Таким образом, если даннаявершина не имеет исходящих связей,то на выходе 24 будет О, в противном случае - 1. Если на выходе 24некоторого блока 16 имеется О, тосоответствующий управляемый ключевойэлемент 3 будет закрыт, В противномслучае, соответствующий элемент 3будет открыт, так как триггеры 13состояния в исходном состоянии находятся в единичном состоянии, а триггеры 4 - в нулевом. Если хотя бы водном из блоков 16 записана исходящая связь, то на выходе элементаИЛИ 10 будет 1, а на первом входесчетчика 1 появится О, На выходеокончания испытания 7 также будет О.Единичное состояние триггеров 13 20устанавливается в исходный моментпутем установки триггеров 4 в единичное состояние через шины (входы) 15и последующей переписи их состоянияв триггеры 13 после окончания записив блоки 16 сигналом с выхода элемента НЕ 12. Сигнал с выхода блока 10,пройдя через линию 2 задержки, сбросит триггеры 4 в 0 и приведет в исходное состояние счетчик 51. 30Устройство работает следующимобразом,При подаче тактовых импульсов навход 6 импульсы проходят через открытые управляемые ключевые элементы 3на тактовые входы блоков 49 (линия 1на фиг. 6). Рассмотрим ситуацию, когда в двух соседних вершинах с номерами 2 к+ 1 40 и 2 к + 2 имеются исходящие связи и первые разряды обоих адресов равны 1, а следующие разряды - соответственно 0 и 1. Из узлов 49 памяти производится на выходы 22 чтение исходящей 45 связи по адресу, определяемому содержимым счетчика 51. По сигналу на входе 28 производится сброс всех узлов 32 связи в исходное состояние и запись содержимого шин (входов) 22 в 50 регистры 29. При поступлении на тактовый выход 35 импульсов производится выдвижение очередного разряда исходящей связи на выход (линии 2 и 3), При появлении на выходе первого разряда исходящей связи на первом выходе 31.1 блока 31 синхронизации появляется тактовый импульс, который является разрешающим для узлов 32 связипервого столбца (линия 4, фиг, 6),Единицы с входов запроса 24 обоихмоделей вершин поступают на входы 36запроса ( К + 1)-го узла 32 связипервого столбца (линии 5 и 6 нафиг. 6), Если запрос отсутствует, тона выходах обоих пар элементов И 40будет О. При наличии запроса, еслиразряд адреса равен О, то единицапоявится на выходе левого элемента И,в противном случае - на выходе правого элемента И (линии 7 и 8 нафиг, 6)На входы 45 и 46 могут бытьподаны следующие сочетания сигналов:либо две единицы, либо два нуля, либоноль и единица (общим случаем являются две единицы). При подаче на входы45 и 46 двух единиц на выходе элемента ИЛИ 61 появится единица (линия9, фиг. 6). Элемент 57 запрета выдает на выходе нуль (линия 10,фиг. 6). Таким образом, на установочном входе триггера 62 будет 1, а наустановочном входе триггера 59 - О,При приходе разрешаемого сигналапо шине 39 триггеры установятся всоответствующее состояние (линии11 и 12), Выход триггера 62 формирует разрешающий сигнал для мультиплексора 60, который подключает одиниз входов на выход в соответствии ссостоянием адресного входа которыйопределяется выходом триггера 59.При наличии 0 на выходе триггера 59на выход мультиплексора 60 подключается первый вход 47, в противномслучае - второй вход 48, При подачеследующего сигнала на вход 5 разрешающий сигнал из блока 31 синхронизации подается только на узлы связи второго столбца, а на выходахсдвиговых регистров 29 появляетсяследующий разряд исходящей связи(линии 2 и 3 на фиг, 6). Он проходитпо каналу связи. подключенному первым разрядом адреса в узлах 32 связипервого столбца на входы 38 соответствующего узла связи второго столбца (линия 13, фиг, 6), Описанныйпроцесс повторяется до тех пор, покана соответствующих выходах 35 запроса узлов связи 32 М -го столбца не.появится единица. Пусть на первомвыходе 35-го узла связи И-гостолбца появилась 1, причем этот выход соответствует адресу первой исходящей связи вершины с номером 21 +1(линия 14, фиг. 6), Адресные выходы32 узлов связи последнего столбца неиспользуются. При появлении на выходах 26 запроса единицы триггер 4через элемент ИЛИ 8 перейдет в единичное состояние - линия 15. На первый вход 33 (3, М )-го,.узла связипоступит 1, В зависимости от состояния триггера 59 единица с входа 33появится на выходе либо первого 58, 1 Олибо второго элемента И 63. Если навходе 33 будет О, то в формированиисостояния выхода 34 принимает участиевход 43 через элемент ИЛИ 56, Рассмотрим описанный процесс для (6 +1)- 15го узла связи 1-го столбца. В этомслучае на первом входе 33 будет 1,а на втором - 0 (линии 16 и 17).Тогда на выходе с номером (2 М +1)появится 1, а на выходе 23 с номером 20(З( +2) - 0 (линии 18 и 19) . В случае1 через элемент ИЛИ 50 в счетчик 51добавляется 1 и производится чтениеследующей исходящей связи из запоминающего устройства 49 на выходы 22, 25В то же время через элемент ИЛИ 11на вход 28 подается 1, которая сбросит в О триггеры 59 и 62 (линии 20, 11и 12) и разрешит запись информациив 29. Описанный процесс будет понто- з 0ряться до тех пор, пока из всех бло"ков 16 записи связей, в которых былизаписаны адреса исходящих связей,не будут отправлены все связи и получены отнеты. Если из некоторого блока 16 записи связей был отправлензапрос, но ответ не пришел то нследующем цикле передачи запрос отправляется по старому адресу во второй раз, так как содержимое счетчика51 не изменилось. Если из данногоблока 16 записи связей прочитанывсе исходящие связи и получены ответы, то содержимое счетчика 51,равно содержимому регистра 53 и инверсный выход элемента 52 сравненияустанавливается н О. Когда на всехвыходах 24 окажутся О (линии 4 и 5),то иа выходе элемента ИЛИ 10 появитсяО, после чего на первом входе блока14 появится единица (линии 21 и 22),В это время состояние выхода 7 равно единице, что позволяет добавить нсчетчик 1 единицу. Одновременно посигналу с выхода 12 содержимое триггерон 4 перепишется в триггеры 13.Если имеется хотя бы одна вершинас исходящими снязями, у которой со 63Ьдержимое триггера 13 равно единице,то описанный процесс повторяется снова, но предварительно через линию 2задержки сигналом с выхода элеменгаИЛИ 10 будут сброшены в 0 триггеры 4(линия 15) и счетчики 51 в блоках 16записи связей. Когда после очередного цикла ни один из триггеров 4 небудет находится в единичном состоянии, на выходе 7 будет также 0 и нсчетчик 1 не будет добавляться единицы. Это говорит об успешном окончаниииспытания, а содержимое счетчика равно максимальному пути в графе.Для определения доступности некоторой вершины необходимо в исходномсостоянии установить триггер 13состояния вершины нужной вершины вединичное состояние., а все остальноев 0Дальнейшее аналогично описан"ному,Для определения наличия циклов .н графе исходное состояние устанавливается как для случая определениямаксимального пути в графе. Если впроцессе функцнонирования н счетчике2 окажется число, большее числа вершин н графе, то это говорит о наличиициклов в исследуемом графе. Время решения задачи равно суммедвух времен: времени настройки устройства на структуру исследуемого .графа и времени определения требуемых характеристик. За счет использования введенных блоков появляетсявозможность быстро изменять структуру исследуемого графа и производитьперенастройку на новую структуру,вследствие чего достигается сокращение времени решения задачи в 2,5 раза по сравнению с известным устройством,Формула изобретения Устройство для исследонания графов, содержащее счетчик, линию задержки, 2 И моделей вершин (где И = = 2"), каждая из которых включает управляемый ключевой элемент, элемент ИЛИ и триггер, причем тактовый вход устройства соединен с первыми управляющими входами всех управляемых ключевых элементов 2 И моделей вершин, вход начальной установки устройства подключен к входу сброса счетчика, но всех моделях вершин выход элемента ИЛИ соединен с единичным входом триггера, о т л ич а ю щ е е с я тем, что, с цельюповышения быстродействия, введенытри многовходовых элемента ИЛИ,элемент НЕ, элемент И, блок связи,включающий И пар регистров, узелсинхронизации и матрицу из И х Музлов связи (где М = 1 оя 2 И), каж 2дый из которых включает две группыиз двух элементов И и два элементасвязй, каждый из которых состоит иэдвух элементов ИЛИ, первого и второго элементов И, двух триггеров,элемента запрета и мультиплексора, вкаждую модель вершины введен триггер 15состояния и блок записи связей,включающий узел памяти, элемент ИЛИ,,счетчик, элемент сравнения и регистр,причем в каждом блоке записи связей первый вход элементов ИЛИ соединен с входом 20задания логической единицы устройства,а выход элемента ИЛИ подключен к1счетному входу счетчика, выход которогосоединен с адресным входом узла памяти, первым входом элемента сравнения 25и входом регистра, вход разрешениязаписи которого подключен к входуразрешения записи устройства, авыход - соединен с вторым входомэлемента сравнения, первый информа- ЗОционный вход устройства соединен синформационным входом узла памяти,вход записи считывания которого соединен с входом задания режима устройства, в каждой модели вершины тактовый вход узла памяти соединен с выходом управляемого ключевого элемента, информационный вход которогоподключен к выходу элемента сравнения блока задания записи связей, 40второй управляемый вход управляемогоключевого элемента каждой моделивершины соединен с выходом триггерасостояния, вход которого подключенк выходу триггера модели вершины, . 45первый вход элемента ИЛИ моделивершины соединен с вторым информационным входом устройства, выходывсех триггеров всех моделей вершинсоединены с соответствующими входами 5 Опервого многовходового элемента ИЛИ,выход которого подключен к выходуокончания испытания устройства ипервому входу элемента И устройства,второй вход которого соединен с разрешающими входами всех триггеровсостояния моделей вершин, выход элемента И устройства соединен со счетю входом счетчика, выход второгоноговходового элемента ИЛИ соединенвходом элемента НЕ и входом линииадержки, входы второго многовходовоголемента ИЛИ подключены к выходам соответствующих элементов сравнения блоков записи связей соответствующих моделей вершин, выход линии задержки соединен с нулевыми входами триггеров и входами сброса счетчиков блоков записи связей всех моделей вершин, вторые входы элементов ИЛИ блоков записи связей моделей вершин соединены с соответствующими входами группы третьего многовходового элемента ИЛИ, вход которого соединен с входом начальной установки устройства, информационные выходы узла памяти блока записи связей (2 к+ 1) и (2 К+2)-й моделей вершин соединены соответственно с входами первого и; второго регистров (К +1)-й пары блока связи (где К =1, И), выходы первых элементов ИЛИ первого и второго элементов связи (К +1)-го узла связи первого столбца матрицы блока связи соединены соответственно с вторыми входами элементов ИЛИ блоков записи связей (2 К+ 1) и (2 К+2)-й моделей вершин, выходы элементов сравнения которых подключены соответственно к прямому входу первого и первому входу второго элементов И первой и второй групп (К+1)-го узла связи первого столб ца матрицы блока связи, выходы триггеров (2 К+1) и (2 К+2)-й модели вершин соединены соответственно спервыми входами элементов И первого и второго элементов связи (К+1)-го узла связи М-го столбца матрицы блока связи, выходы первых триггеров которых подключены соответственно к вторым входам элементов ИЛИ (2 К+1) и (2 К+2)-й моделей вершин, выход третьего многовходового элемента ИЛИ соединен с входами сброса первого и второго триггеров связи и разрешающими входами регистров блока связи, сдвиговые входы которых подключены к тактовому входу устройства и входу узла синхронизации, 1 -й выход которого соединен с разрешающими входами триггеров элементов связи-го столбца матрицы из БхМ узлов связи, первые входы элементов И и первой и второй групп (К, 1 )-го столбца блока связи соединены с выходом первого элемента ИЛИ соответствующего элемента связи соот 1 ветствующего узла связи ( +1)-го столбца матрицы блока связи, прямой вход первого и первый вход второго элементов И соответствующей группы которого подключены к выходу первого триггера, разрешающему входу мультиплексора и вторым входам элементов И элемента связи (Ф, )-го узла связи, выход мультиплексора которого соединен с инверсным входом первого элемента И и вторым входом второго элемента И соответствующей группы соответствующего узла связи (+1)-го столбца матрицы, причем в каждом узле связи второй вход второго элемента И первой группыподключен к первому входу мультиплексора второго элемента связи и второму входу с мультиплексора первого элемента связи, выход первого элемента И первой группы подключен к первым входам второго элемента ИЛИ и элемента запрета первого элемента связи, выход второго элемента И первой группы соединен с вторыми входами второго элемента ИЛИ и элемента э апре та в то рого элеме нта свя э и выход второго элемента И которого подключен 27076310к первому входу первого элементаИЛИ первого элемента связи, выходвторого элемента И которого соединенс вторым входом первого элеМента ИЛИ5второго элемента связи, выход первогоэлемента И второй группы подключен квторым входам второго элемента ИЛИ иэлемента запрета первого элементасвязи, выход второго элемента И вто 1 О рой группы соединен с первыми входа"ми второго элемента ИЛИ и элементазапрета второго элемента связи, второй вход второго элемента И второйгруппы соединен с первым входом15 мультиплексора первого элемента связи и вторым входом мультиплексоравторого элемента связи, причем вкаждом элементе связи выход первогоэлемента И соединен с вторым входом20 первого элемента ИЛИ, выход второгоэлемента ИЛИ подключен к установочному входу первого триггера, выход,элемента запрета соединен с установочным входом первого триггера,25 .выход которого соединен с адреснымвходом мультиплексора, инверснымвходом первого элемента И и третьимвходом второго элемента И,1270763 авитель В, Верховскийед Л.Сердюкова 1(оррек В. Синицк ж 671 Подписи Заказ 6244/5 ВНИИПИ Государств по делам изобре 035, Москва, Жоектная ул. ическо едактор Ю. Середа Производственно-поли 1 У Ю 17 1 г И ного комитета СССРний и открытийРаушская наб д. 4/5 предприятие, г. Ужгоро