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

 

Изобретение относится к области вычислительной техники и может быть использовано для исследования графов, в частности, для определения доступности графа для любой вершины, наличия циклов в графе и максимального пути в графе. Цель изобретения - повышение быстродействия. Для достижения указанной цели устройство дополнительно содержит элементы ИЛИ, И, триггеры состояния, блоки записи связей и блок связи. Данное устройство имеет в 2,5 раза большее быстродействие и, кроме определения доступности любой вершины графа, позволяет а определять максимальный путь в графе и наличие циклов в нем, 6 ил. (Л

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (59 4 G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3692890/24-24 (22) 17.01.84 (46) 15.11.86. Бюл. Ф 42 (71) Белорусский ордена Трудового

Красного Знамени государственный университет им.В.И.Ленина (72) С.Ю.Головин, А.С.Липницкий, Г.Я.Лопатов, А.М.Никонов, В.Ф.Ранчинский, Г.Н.Черников, Г.И.Епаковский и С.С.Змачинский (53) 681.333(088.8) (56) Авторское свидетельство СССР

У 643880, кл. С 06 F 15/20, 1975.

Авторское свидетельство СССР

У 408312, кл. G 06 F 15/20, 1971. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ГРАФОВ

„„SU„„1270763 А 1 (57) Изобретение относится к области вычислительной техники и может быть использовано для исследования графов, в частности, для определения доступности графа для любой вершины, наличия циклов в графе и максимального пути в графе. Цель изобретения — повышение быстродействия. Для достижения указанной цели устройство дополнительно содержит элементы ИЛИ, И, триггеры состояния, блоки записи связей и блок связи. Данное устройство имеет в 2,5 раза большее быстродействие и, кроме определения доступности любой вершины графа, позволяет определять максимальный путь в графе и наличие циклов в нем. 6 ил.

1270763

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

Цель изобретения — повьппение быстродействия.

На фиг. 1 приведена функциональ- 1О ная схема предлагаемого устройства для исследования графов; на фиг. 2— структура блока связи; на фиг. 3— структура узла связи; на фиг. 4— структура блока записи связей; на 15 фиг. 5 — элемент связи; на фиг. 6— временные диаграммы. функциональная схема устройства для исследования графов включает 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,2N, вход. 28 сброса блока связи.

Блок 17 связи включает регистры

29 образующие пары регистров 30,1Ф

ЗО.N блок 31 синхронизации, узлы связи 32.1, 1-32, NM, образующие матрицу NxM, входы 33 ответа узла связи, выходы 34 ответа узла связи, выходы 35 запроса узла связи, входы

36 запроса узла связи, адресные вы55 ходы 37 узла связи, адресные входы 38 узла связи, входы,39 синхронизации узла связи.

Схема узла 32 связи включает элементы И 40, образующие группы элементов И 41.1-41.2, элементы связи 42.142.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 добавляется еще одна I и в регистр 53 заносится новое содержимое счетчика 51 при помощи подачи разрешающего сигнала на вход 21. Режим записи в узле 49 памяти определяется состоянием шины 19.

В исходном состоянии содержимое счетчика 51 равно О, т„е. он указывает на адрес хранения первой исходящей связи. Если некоторая вершина не имеет исходящих связей, то содержимое счетчика 51 будет равно содержимому регистра 53 и тогда схема 52 сравнения вырабатывает О на инверсном выходе.

Если у данной вершины имеется хотя бы одна исходящая связь, то содержИмое счетчика 51 в исходном состоянии з 1270763 4 и регистра 53 не совпадают и на инверсном выходе схемы 52 сравнения будет 1. Таким образом, если данная вершина не имеет исходящих связей, то на выходе 24 будет О, в против- 5 ном случае — 1. Если на выходе 24 некоторого блока 16 имеется О, то соответствующий управляемый ключевой элемент 3 будет закрыт. В противном случае, соответствующий элемент 3 будет открыт, так как триггеры .13 состояния в исходном состоянии находятся в единичном состоянии, а триггеры 4 - в нулевом. Если хотя бы в одном из блоков 16 записана исходящая связь, то на выходе элемента

ИЛИ 10 будет 1, а на первом входе счетчика 1 появится О. На выходе окончания испытания 7 также будет О, Единичное состояние триггеров 13 устанавливается в исходный момент путем установки триггеров 4 в единичное состояние через шины (входы) 15 и последующей переписи их состояния в триггеры 13 после окончания записи в блоки 16 сигналом с выхода элемента НЕ 12. Сигнал с выхода блока 10, пройдя через линию 2 задержки, сбросит триггеры 4 в О и приведет в исходное состояние счетчик 51. 30

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

При подаче тактовых импульсов на вход 6 импульсы проходят через открытые управляемые ключевые элементы 3 на тактовые входы блоков 49 (линия 1 на фиг. 6).

Рассмотрим ситуацию, когда в двух соседних вершинах с номерами 2 к + 1 40

4 и 2к + 2 имеются исходящие связи и первые разряды обоих адресов равны 1, а следующие разряды — соответственно

О и 1. Из узлов 49 памяти производится на выходы 22 чтение исходящей 45 связи по адресу, определяемому содержимым счетчика 51. По сигналу на входе 28 производится сброс всех узлов

32 связи в исходное состояние и запись содержимого шин (входов) 22 в S0 регистры 29. При поступлении на тактовый выход 35 импульсов производится выдвижение очередного разряда исходящей связи на выход (линии 2 и 3).

При появлении на выходе первого раз-55 ряда исходящей связи на первом выходе

31.1 блока 31 синхронизации появляется тактовый импульс, который является разрешающим для узлов 32 связи первого столбца (линия 4, фиг. 6).

Единицы с входов запроса 24 обоих моделей вершин поступают на входы 36 запроса (К + 1)-ro узла 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.

При наличии О на выходе триггера 59 на выход мультиплексора 60 подключается первый вход 47 в противном случае — второй вход 48. При подаче следующего сигнала на вход 5 разрешающий сигнал из блока 31 синхронизации подается только на узлы связи второго столбца, а на выходах сдвиговых регистров 29 появляется следующий разряд, исходящей связи (линии 2 и 3 на фиг. 6). Он проходит по каналу связи. подключенному первым разрядом адреса в узлах 32 связи первого столбца на входы 38 соответствующего узла связи второго столбца (линия 13, фиг. 6). Описанный процесс повторяется до тех пор, пока на соответствующих выходах 35 запроса узлов связи 32 М -го столбца не. появится единица. Пусть на первом выходе 35 3 -го узла связи И-ro столбца появилась 1, причем этот выход соответствует адресу первой исходящей связи вершины с номером 2К. +1

3 12707 (линия 14, фиг. 6), Адресные выходы

32 узлов связи последнего столбца не используются. При появлении на выходах 26 запроса единицы триггер 4 через элемент ИЛИ 8 перейдет в единичное состояние — линия 15. На первый вход 33 (3, М )-го .узла связи поступит 1. В зависимости от состояния триггера 59 единица с входа 33 появится на выходе либо первого 58, 10 либо второго элемента И 63. Если на входе 33 будет О, то в формировании состояния выхода 34 принимает участие вход 43 через элемент ИЛИ 56. Рассмотрим описанный процесс для (Ф +1)- ts

ro узла связи 1-ro столбца. В этом случае на первом входе 33 будет 1, а на втором — О (линии 16 и 17).

Тогда на выходе с номером (2К +1) появится 1, а на выходе 23 с номером zg (? +2) — 0 (линии 18 и 19) . В случае

1 через элемент ИЛИ 50 в счетчик 51 добавляется 1 и производится чтение следующей исходящей связи из запоминающего устройства 49 на выходы 22, 25

В то же время через элемент ИЛИ 11 на вход 28 подается 1, которая сбросит в 0 триггеры 59 и 67.(линии 20, 11 и 12) и разрешит запись информации в 29. Описанный процесс будет понто- зб ряться до тех пор, пока из всех блоков 16 записи связей, в которых были записаны адреса исходящих связей, не будут отправлены все связи и получены отнеты. Если из некоторого блока 16 записи связей был отправлен запрос. но ответ не пришел, то н следующем цикле передачи запрос отправляется по старому адресу во второй раз, так как содержимое счетчика

51 не изменилось. Если из данного блока 16 записи связей прочитаны все исходящие связи и получены ответы, то содержимое счетчика 51, равно содержимому регистра 53 и ин- 45 версный выход элемента 52 сравнения устанавливается н О. Когда на всех выходах 24 окажутся О (линии 4 и 5), то иа выходе элемента ИЛИ 10 появится

О, после чего на первом входе блока

)4 появится единица (линии 21 и 22).

В это время состояние выхода 7 равно единице, что позволяет добавить н счетчик 1 единицу. Одновременно по сигналу с выхода 12 содержимое триг- 55 герон 4 перепишется в триггеры 13.

Если имеется хотя бы одна вершина с исходящими связями, у которой со63

d держимое триггера 13 равно единице, то описанный процесс повторяется снова, но предварительно через линию 2 задержки сигналом с выхода элеменга

ИЛИ 10 будут сброшены в О триггеры 4 (линия 15) и счетчики 51 в блоках 16 записи связей. Когда после очередного цикла ни один из триггеров 4 не будет находится в единичном состоянии, на выходе 7 будет также 0 и н счетчик 1 не будет добавляться единицы. Это говорит об успешном окончании испытания, а содержимое счетчика равно максимальному пути в графе.

Для определения доступности некоторой вершины необходимо в исходном состоянии установить триггер 13 состояния вершины нужной вершины в единичное состояние., а все остальное в 0 ° Дальнейшее аналогично описанному.

Для определения наличия циклов . н графе исходное состояние устанавлинается как для случая определения максимального пути в графе. Если в процессе функцнонирования н счетчике

2 окажется число, большее числа вершин н графе, то это говорит о наличии циклов в исследуемом графе.

Время решения задачи равно сумме двух времен. времени настройки устройства на структуру исследуемого . графа и времени определения требуемых характеристик. За счет использования введенных блоков появляется возможность быстро изменять структуру исследуемого графа и производить перенастройку на новую структуру, вследствие чего достигается сокраще" ние времени решения задачи в 2,5 раза по сравнению с известным устройством.

Формула изобретения

Устройство для исследонания графов, содержащее счетчик, линию задержки, 2N моделей вершин (где И =

= 2"), каждая из которых включает управляемый ключевой элемент, элемент ИЛИ и триггер, причем тактовый вход устройства соединен с первыми управляющими входами всех управляемых ключевых элементов 2N моделей вершин, вход начальной установки устройства подключен к входу сброса счетчика, но всех моделях вершин выход элемента ИЛИ соединен с еди1270763 нь м с з

5 э ничным входом триггера, о т л ич а ю щ е е с я тем, что, с целью повышения быстродействия, введены три многовходовых элемента ИЛИ, элемент НЕ, элемент И, блок связи, включающий И пар регистров, узел синхронизации и матрицу из N x M узлов связи (где M = 1оя 2N), каж2 дый из которых включает две группы из двух элементов И и два элемента связй, каждый из которых состоит иэ двух элементов ИЛИ, первого и вто рого элементов И, двух триггеров, элемента запрета и мультиплексора, в каждую модель вершины введен триггер 15 состояния и блок записи связей, включающий узел памяти, элемент ИЛИ,,счетчик, элемент сравнения и регистр, причем в каждом блоке записи связей первый вход элементов ИЛИ соединен с входом 20 задания логической единицы устройства, а выход элемента ИЛИ подключен к

1 счетному входу счетчика, выход которого соединен с адресным входом узла памяти, первым входом элемента сравнения 25 и входом регистра, вход разрешения записи которого подключен к входу разрешения записи устройства, а выход — соединен с вторым входом элемента сравнения, первый информа- З0 ционный вход устройства соединен с информационным входом узла памяти, вход записи считывания которого соединен с входом задания режима устройства, в каждой модели вершины тактовый вход узла памяти соединен с выходом управляемого ключевого элемента, информационный вход которого подключен к выходу элемента сравнения блока задания записи связей, 40 второй управляемый вход управляемого ключевого элемента каждой модели вершины соединен с выходом триггера состояния, вход которого подключен к выходу триггера модели вершины, 45 первый вход элемента ИЛИ модели вершины соединен с вторым информационным входом устройства, выходы всех триггеров всех моделей вершин соединены с соответствующими входами 50 первого многовходового элемента ИЛИ, выход которого подключен к выходу окончания испытания устройства и первому входу элемента И устройства, второй вход которого соединен с раз- 55 решающими входами всех триггеров состояния моделей вершин, выход элемента И устройства соединен со счетпч входом счетчика, выход второ-с ноговходового элемента ИЛИ соединен входом элемента НЕ и входом линии адержки, входы второго многовходового лемента ИЛИ подключены к выходам соответствующих элементов сравнения блоков записи связей соответствующих моделей вершин, выход линии задержки соединен с нулевыми входами триггеров и входами сброса счетчиков блоков записи связей всех моделей вершин, вторые входы элементов ИЛИ блоков записи связей моделей вершин соединены с соответствующими входами группы третьего многовходового элемента ИЛИ, вход которого соединен с входом начальной установки устройства, информационные выходы узла памяти блока записи связей (2к+ 1) и (2К+2)-й моделей вершин соединены соответственно с входами первого и; второго регистров (К +1)-й пары блока связи (где К =1, N), выходы первых элементов ИЛИ первого и второго элементов связи (K +1)-го узла связи первого столбца матрицы блока связи соединены соответственно с вторыми входами элементов ИЛИ блоков записи связей (?K+1) и (?K+2)-й моделей вершин, выходы элементов сравнения которых подключены соответственно к прямому входу первого и первому входу второго элементов И первой и второй групп (К+1) -го узла связи первого столб. ца матрицы блока связи, выходы триггеров (2К+1) и (2K+2) — и модели вершин соединены соответственно с первыми входами элементов И первого и второго элементов связи (К+1)-го узла связи М-го столбца матрицы блока связи, выходы первых триггеров которых подключены соответственно к вторым входам элементов ИЛИ (2К+1) и (?K+2) -й моделей вершин, выход третьего многовходового элемента ИЛИ соединен с входами сброса первого и второго триггеров связи и разрешающими входами регистров блока связи, сдвиговые входы которых подключены к тактовому входу устройства и входу узла синхронизации, 1 -й выход которого соединен с разрешающими входами триггеров элементов связи ) -го столбца матрицы из NxM узлов связи, первые входы элементов И и первой и второй групп (К, 1 )-го столбца блока связи соединены с выходом первого элемента ИЛИ соответствующего элемента связи соот270763

LJ ветствующего узла связи /+1)-ro столбца матрицы блока связи, прямой вход первого и первый вход второго элементов И соответствующей группы которого подключены к выходу первого триггера, разрешающему входу мультиплексора и вторым входам элементов И элемента связи (_#_,j )-го узла связи, выход мультиплексора которого соединен с инверсным входом первого элемента И и вторым входом второго элемента И соответствующей группы соответствующего узла связи ()+1)-го столбца матрицы, причем в каждом узле связи второй вход второго элемента И первой группы подключен к первому. входу мультиплексора второго элемента связи и второму входу с мультиплексора первого элемента связи, выход первого элемента И первой группы подключен к первым входам второго элемента ИЛИ и элемента запрета первого элемента связи, выход второго элемента И первой группы соединен с вторыми входами второго элемента ИЛИ и элемента запрета в TopoI элемента связи„выход второго элемента И которого подключен

10 к первому входу первого элемента

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

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

15 мультиплексора первого элемента связи и вторым входом мультиплексора

Второго элемента связи, причем В каждом элементе связи выход первого элемента И соединен с вторым входом

20 первого элемента ИЛИ, выход второго элемента ИЛИ подключен к установочному входу первого триггера, выход, элемента запрета соединен с установочным входом первого триггера, 7g -выход которого соединен с адресным входом мультиплексора, инверсным входом первого элемента И и третьим входом второго элемента И.

1270763

Фиг. 2

1270763

2t

gf

f9

18

17

18

f4 -1„, 12 4 >

У вЂ” Ч Ь вЂ” — Ф вЂ” -ч

Г Г- -, — / —à l >1 — — ч > — -г>-1 ф —.Г 1Г 1-у . Г 1. Г 1

à — à 1-1 1- —

à —— .1 — Г о

r — Г 1-Г"1-ь-Г 1ч Г 1, Фие.b

Составитель В. Верховский

Редактор Ю. Середа Техред Л.Сердюкова КорректорВ. Синицкая

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

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб,, д, 4/5

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