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

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

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

Устройство для определения сзяз- ности графа содержит дешифратор 1, первый 2 и второй 3 элементы И,, группу элементов И 4, первую группу элементов ИЛИ 5, группу элементов И 6, группу триггеров 7, группу элементов И 8,. группу регистров 9, группу триггеров 10, группу блоков 11 сравнения первый 12 и второй 13 регистры, третий 14 и четвертьй 15 элементы И, первую группу схем 16 сравнения, вто рую группу схем 17 сравнения, группы элементов И 18, 19, вторую группу элементов ИЛИ 20, блок 21 управления первый 22, второй 23, третий 24 и четвертый 25 выходы блока управления вход 26 разрешения опроса устройства вход 27 номера начальной вершины отказавшей ветви графи устройства, вход 28 номера конечной вершины отказавшей ветви графа устройства, вхо ды 29 задания топологии исследуемого графа устройства, выход 30 сигнала несвязности графа устройства, выход 31 сигнала связности графа устройства.

Блок 21 управления (фиг.2) содер- жит одновибратор 32, генератор 33 тактовых импульсов, кольцевой сдвиговый регистр 34, элемент И 35, элемент И,ПИ 36, элементы НЕ 37 и 38.

Блок 11 сравнения (фиг.З) содер- жит группу элементов И 39, группу схем 40 сравнения и элемент ИЛИ 41.

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

По входу 29 в регистг1Ы 9 и триггеры 10 записывается описание графа, .которое составляется на основании графического изображен ш сети связи ЭВМ следующим- образом.

А. На графе сети связи ЭКМ выделяют знаком D все те в-ершииы, у которых число выходных ветвей 3 (связность больше 3).

Б. Если не имеется ни одной выдеенной вершины, то выполняется операция В, иначе - операция Г.

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

В противном случае берут любую вершину, у которой число выходных ветвей 1, и.выписывают, начиная с данной вершины, по порядку все вершины на пути к другой вершине, у которой число выходных ветвей 1. Номера вершин соединяют знаком 8 . Заканчивают описание номером вершины конца пути.

Описание графа составлено.

Г. Берут любую вьщеленную вершину.

Д. По каж,цому выходному направлению (линии связи) описывают путь (путем перечисления вершин и соединения их знаком и) до первой встречной выделенной вершины (включительно) ибо до концевой вершины, если такая имеется. Помечают вьщеленный путь.

Е. Для всех остальных выд.еленных вершин описывают путь согласно операции Д по всем выходным ветвям, не входящим в помеченные (описанные) пути.

Ж. Полученные отдельные описания путей соединяют знаком В в единое выражение - описание графа.

В регистры 9 заносятся номера вершин, а значения триггеров 10 устанавливаются следующим образом: О, если описание графа Ш 1, если описание графа S .

Если в сети связи ЭВМ вышла из строя линия связи между вершинами X и Y, то их 1омера подают соответственно на входы 27 и 28 устройства. Эти номера записываются в регистры 12 и. 13. На вход 26 подают импульс опроса на проверку связности графа, который поступает на одновибратор 32 (фиг.2). Сигнал с выхода одновибра- тора. 32 через элемент ИЛИ 36 открывает элемент И 35, и генератор 33 тактовых импульсов начинает производить циклический сдвиг кода 0...01, записанного в сдвиговом регистре 34.

Сигналом О с выхода 22 блок 21 управления через элементы И 6 устанавливает триггеры 7 в нуль, Сигна

лом с выхода 25 блок 21 управления производит корректировку описания графа путем замены операции ® на ffl между номерами соседних вершин X и Сравнение номеров вершин, описываю- щих отказавшую ветвь (линию связи) с номерами вершин в описании графа производится схемами сравнения 16 и 17. Если соседние номера вершин в описании графа X и Y, то элемент

ИЛИ 20 вырабатывает сигнал 1 и устанавливает триггер 10 в состояние О. Следующим сигналом (сигналом с выхода 23) блок 21 управления через элемент ИЛИ 5 и открытый элемен И 6 устанавливает первый триггер 7 в состояние 1. Если триггер 10 находится в состоянии 1, операция 8 то через открытий элемент И 8 сле- дуюш;ий триггер 7 устанавливается в состояние 1 и т.д. Этот лавинообразный процесс заканчивается на первом же закрытом элементе И 8, т.е. на коде операцииШ. Одновременно с этим работают блоки 11 сравнения. Если количество вершин в описании графа равно N, то число блоков 11 сравнения равно N-1. На вход элементов И 39 подается номер вершины (из регистра 9) и соответствующее данному номеру состояние триггера 27 связности (если триггер 7 находится в состоянии 1, то данная вершина доступна, если триггер 7 находится в состоянии О то - недоступна). На вход блока 11 сравнения i-ro узл (начиная с второго) подаются следующие сигналы (см.фиг.3): номер i-й вершины из регистра 9 подается на все схемы 40 сравнения (вход i) и- не подается на входы элементов И 39 на вторые входы элементов И 39 подается сигнал с соответствующего триггера 7 связности.

Блок 11 сравнения определяет, доступен ли 1-й узел хотя бы из одного уже доступного узла (узла, у которого триггер 7 связности находится в состоянии 1). Сигналом с выхода блок 11 сравнения устанавливает соответствующий ему триггер связности в состояние 1.

Элементы И 8 предназначены для встречной установки триггеров 7 в состояние 1, в выражении между двумя знаками операций.

Если все триггеры 7 связности установлеры в состояние 1, то дешифратор 1 вырабатывает сигнал 1

.

Ш

15

20

25

30

35

40

5

0

5

304

о связности графа. Блок 21 управления сигналом с выхода 24 формирует импульс на одном из выходов устройства (на выходе 30 или 31). Появление 1 на выходе 30 свидетельствует о несвязности графа, а на выходе 31 - о связности.

На этом работа устройства заканчивается, и устройство переходит в режим ожидания.

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

1. Устройство для определения связности графа, содержащее первую, вторую, третью, четвертую и пятую группы элементов И, первую группу элементов ИЛИ, первую и вторую группы триггеров, выход каждого i-ro триггера (где ,2,...п) первой группы подключен к первым входам i-x элементов И первой и второй групп, отличающее ся тем, что, с целью увеличения быстродействия устройства, в него введены группа регистров, первая и вторая группы схем сравнения, группа блоков сравнения, вторая группа элементов ИЛИ, два регистра, четыре элемента И, дешифратор и блок управления, причем первый выход блока управления подключен к первым входам элементов И третьей группы, второй вход каждого j-ro элемента И третьей группы (где ,2,...,(п+1)) подключен к выходу j-ro элемента ИЛИ второй группы, выход каждого j-ro элемента И третьей группы подключен к входу j-ro триггера второй группы, выход каждого j-ro триггера второй группы, кроме (п+1)-го, подключен к второму входу i-ro элемента И первой группы (), выход каждого j-ro триггера второй группы, кроме первого, подключен к второму входу i-ro элемента И второй группы (), выход каждого i-ro элемента И первой группы подключен к первому входу j-ro элемента И.ПИ

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

блока сравнения группы подключен к выходу соответствующего регистра группы, входы установки в единицу TpiHrrepoB первой группы и установочные входы регистров группы; являются входами задап-ия топологии исследуемого графа устройства, вход установки в нуль каждого триггера первой группы подключен к выходу одноимен1277130 6

(i-1)-ro элемента И пятой группы, выход каждой i-й схемь: сравнения (,3,...,(п-1)) второй группы подключен к первому входу i-го элемента 5 И пятой группы и к второму входу (1-1)-го элемента И четвертой группы, вьгход п-й схемы сравненрш первой группы подключен к второму входу (п-1)-го элемента И пятой группы,

ного элемента ШШ первой группы, тре-JQ выход п-й схемы сравнения второй

тий выход блока управления подключен к первым входам первого и второго элементов Й, вторые входы которых . объединены и подключены к выходу дешифратора, выход первого элемента И является выходом сигнала несвязности графа устройства, выход второго элемента И- является выходом сигнала . связности графа устройства, четверты выход блока управления подключен к первым входам третьего и четвертого элементов И, второй вход третьего элемента И подключен к выходу первог регистра, второй вход четвер чзго элемента И подключен к выходу второго регистра, вход первого регистра является входом номера начальной,вершины отказавшей ветви графа устройства вход второго регистра является входом номера конечной вершины отказав- ш;ей ветви графа устройства, выход третьего элемента И подключен к первым входам схем сравнения первой Группы, выход четвертого элемента И подключен к первым входам схем сравнения второй группы, вторые входы одноименных схем сравнения первой и второй групп объединены и подключены к выходу одноименного регистра группы, вьтход первой схемы сравнения первой группы подключен.к первому входу первого элемента И четвертой группы, вь1ход первой схемы сравнения второй группы подключен, к первому входу первого элемента И пятой rpyrt- лы, выход каждой i-й схемы сравнения (,3,..,,(п-1)) первой группы под- :ключен к первому входу i-ro элемента И четвертой группы и к второму входу

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

2. Устройство по П.1, отличающее с я тем, что блок управления содержит генератор тактовых импульсов, элемент И, элемент ИЛИ, два элемента НЕ, одновибратор и кольцевой сдвиговый регистр, выход генератора тактовых импульсов подключен к первому входу элемента И, выход которого подключен к входу кольдево- го сдвигового регистра, выход первого разряда кольцевого сдвигового регистра подключен к входу первого элемента НЕ, выход которого является соответственно первь 1м выходом блока управления, выходы второго, третьего и четвертого разрядов кольцевого сдвигового регистра являются соответственно вторым, тpeтьи и четверть1м выходами, блока управтЕения, выход последнего разряда кольцевого сдвигового регистра подклюг ен к входу второго элемента НЕ, выг.оц которого подключен к первому входу элемента Г-ШИ, выход элемента ИЛИ подключен к второму входу элемента И, второй вход элемента ШЩ подключен к выходу од- новибратора, вход которого является входом блока управления.

26

Фиг.1

Изобретение относится к области вычислительной техники для определения связности графов и может быть использовано в сетях связи ЭВЬ1 в качестве одного из модулей системы се- теметрии узла коммутации. Целью изобретения является увеличение быстродействия. Поставленная цель достигается тем, что в ус тройство для определения связности графов, содержащее пять групп элементов И, группу элементов ИЛИ, две группы триггеров, введены группа регистров, две группы схем сравнения, группа блоков сравнения, группа элементов ИЛИ, два регистра, четьфе элемента И, дешифратор и блок управления. 1 з.п. ф-лы, 3 ил. i (Л N5 sj

22 25 2 3

t/e.3

Редактор И.Рыбченко

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

Техред М.Ходанич Корректор Г.Решетник

Зйказ 6669/44 Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

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

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