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

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

Известно устройство для анализа параметров графа, содержащее элементы задержки, триггеры, элементы И, ИЛИ, НЕ и наборные поля. Это устройство используется для определения внешнего радиуса любой вершины в графе.

Недостатком этого устройства является ручная коммутация, в соответствии с топологией анализируемого графа.

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

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

00

ел о о о

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

Недостаток этого устройства - невозможность решения широко распространенной задачи пометки вершин графа методом поиска в глубину и ручная коммутация связей в графе.

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

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

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

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

5 подключен ко второму входу элемента ИЛИ

и является входом задания начальной вер шины модели, а вход управления записью

подключен к выходу четвертого элемента И,

второй вход которого подключен к выходу

0 третьего элемента И, выход элемента ИЛИ подключен к установочному входу триггера, выход которого подключен ко второму входу первого элемента И, выход которого подключен к входам соответственно первого и

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

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

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

установочному входу триггера, второй вход

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

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

Устройство содержит блок 1 управления, перебором вершин, модель 2 вершины, повторенную В раз (В - число вершин в графе). Здесь и далее цифрами в скобках, стоящим после номеров позиций на чертеже, обозначены порядковые номера совершенно одинаковых по своему функциональному назначению и техническому исполнению блоков, узлов и элементов, а просто цифрами в скобках возле контуров блоков и узлов - порядковые номера входов и выходов данного блока или узла. В каждую модель 2 вершины входит триггер 3, регистры 4, 5 сдвига, элементы 6, 7, 8, 9, И, элементы 10 ИЛИ, элементы 11, 12 НЕ, блок элементов 13 И из М элементов (М log2B). Блок 1 управления перебором вершин включает генератор 14 импульсов, блок формирования сигналов управления 15, счетчики 16,17 импульсов, триггер 18, элементы 19, 20 И, элемент 21 ИЛИ.

Кроме этого, на фиг. 1 цифровые обозначения имеют вход 22 управления пуском, осведомительный вход 23 блока 1 управления, перебором вершин, выход 24 реверса блока 1, первый выход 25 сдвига блока 1, информационный выход 26 устройства, В входов 27 задания начальной вершины графа, второй выход 28 сдвига блока 1 управления, выход 29 опроса модели 2 вершин, вход

30 опроса модели 2 вершины, В групп входов 31 задания кода номера вершины.

Множество моделей 2 вершин, связанных с блоком 1 управления образуют пзрал- 5 лельную моделирующую структуру, в которой все В одноименных полюсов 23, 24, 25, 26, 28 электрически соединены вместе. Выходной полюс 29 К-ой модели 2 вершины соединен с входным полюсом 30 К - 1-й 10 модели 2 вершины.

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

Пусть необходимо сформировать список вершин графа, начиная с заданной, в

5 порядке, определяемом процедурой поиска в глубину на графе, структура которого представлена на фиг. 2. Зададим в качестве начальной вершину с номером К

Перед началом работы в регистры 4

0 сдвига первой группы заносится информация о структуре связей в графе. Триггеры 3 устанавливаются в исходное единичное состояние. Регистры 5 сдвига второй группы в исходном состоянии настроены на сдвиг в

5 сторону старших разрядов (прямой ход) и содержат нули во всех разрядах. Блок 15 формирования сигналов управления в исходном состоянии не вырабатывает никаких сигналов на своих выходах (1) - (5).

0 Сигналом пуска на полюсе 22, прошедшим через элемент 21 ИЛИ блока t управления перебором вершин, устанавливается в единицу триггер 18 блока 1 и запускается генератор 14 импульсов, импульсы которого

5 через элемент 19 И блока 1 поступают на вход (2) блока формирования сигналов управления. Под действием этих импульсов блок 15 начинает формировать сигналы управления. Одновременно с этим сигнал пу0 ска поступает на К-й полюс 27 задания начальной вершины. По сигналу на последнем полюсе устанавливается в нулевое состояние К-й триггер 3 и записывается единица в младший (первый) разряд К-го

5 регистра 5 сдвига. На К-ой группе входов 31 задания кода вершины присутствует код, соответствующий номеру К-ой вершины, который передается на информационные выходы 26 устройства через блок 13 элементов

0 И. На выходе (4) вырабатывается импульс стробирования счетчика 16 импульсов. По этому сигналу код номера вершины (1) заносится в счетчик 16 импульсов. Затем вырабатывается сигнал на выходе (5), который

5 переводит в нулевое состояние триггер 18 блока 1 : элемент 19 И блока 1 закрывается, а элемент 20 И того же блока открывается, и тактовые импульсы начинают поступать на входы счетчиков 16, 17 импульсов и на полюс 28. Т.к. в счетчик 16 импульсов записан

код 1 ион работает на вычитание, то, приняв один импульс, он сформирует сигнал обнуления, который через элемент 21 ИЛИ блока 1 переведет триггер 18 в единицу. Подача тактовых импульсов на полюс 28 прекратится. Таким образом, на выход 28 сигнала сдвига блока 1 управления поступит один импульс, который одновременно сдвинет все регистры 4 на один разряд. В регистрах 4 моделей (2) и (3) вершин на выходе сформируется сигнал единицы. Переключение триггера 18 в единицу продолжит работу блока формирования сигналов управления 15 под действием тактовых импульсов на его входе (2): опрашивается состояние осведомительного сигнала на полюсе 23. На выходах элементов 12 НЕ в моделях (2) и (3) вершин к этому моменту сформируются нулевые сигналы, поэтому и на полюсе 23 будет такой же сигнал. При нулевом сигнале на полюсе 23 формируется импульс сдвига, поступающий с выхода (3) на полюс 25. Сдвиг регистров 5 второй группы на один разряд приводит к тому, что на информаци- оннных выходах 26 пропадает код номера вершин (1). Затем сигнал с полюса 30 проходит через первый элемент 7 И, появляется на полюсе 29 узла 2 (1) вершины, поступает на полюс 30 модели 2 (2) вершины, на выход 29 которой уже не проходит, т.к. на выходе элемента 11 НЕ в этом узле в данный момент присутствует нулевой сигнал. В этой модели 2(2) вершины сигнала опроса с полюса 30 пройдет через элементы б, 7 И и запишет единицу в младший разряд регистра 5 сдвига, выходной сигнал которого через элементы И блока 13 установит на информационных выходах 26 устройства код еерши- ны (2). Блоки 13 элементов И в остальных моделях вершин в этот момент закрыты нулевым сигналом с выходов регистров 5 сдвига. Заметим, что всякий раз на соответствующем такте единица записывается только в один регистр 5 сдвига. После этого триггер 18 блока 1 переводится в нулевое состояние, и тактовые сигналы с выхода элемента 20 И продолжают заполнение счетчиков 16, 17 импульсов блока 1 управления и сдвиг регистров 4. Импульс переполнения счетчика 17 импульсов вернет триггер 18 в единичное состояние. К этому моменту информация в кольцевых регистрах 4 восстановит исходное состояние. На информационных выходах 26 устройства установлен код вершины1 (2), регистр 4 находится в исходном состоянии и можно продолжить процедуру поиска в глубину и формирование списка номеров вершин.

Блок 15 формирования сигналов управления формирует импульс стробирования

для счетчика 16 блока 1 управления, в который теперь занесется код вершины (2), и описанный выше процесс повторится. В ходе поиска в глубину триггеры 3 в моделях 2

вершин переводятся в нулевое состояние, а коды номеров вершин выдаются на информационные выходы 26 устройства.

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

0 вершины (5). К этому моменту все триггеры 3 уже переведены в нулевое состояние, поэтому на полюсе 23 сформируется сигнал единичного уровня, после опроса которого блок 15 перейдет к ёыполнению обратного

5 хода: установит признак обратного хода на полюсе 24 и затем сдвинет регистры 5 на один разряд назад. В результате возврата на полюсах 26 установится код вершины (4). Далее идут описанные уже действия по пе0 редаче кода вершины в счетчик 16 импульсов, отсчет импульсов счетчиками 16, 17 и одновременный сдвиг регистроа 4. Опрос осведомительного сигнала на полюсе 23 снова покажет наличие единицы, т.е. из вер5 шины (4) при заданной в примере структуре графа тоже нельзя продолжить движение в глубину (прямой ход), т.к. триггеры 3 переведены в нулевое состояние. Сравнив после этого код на полюсах 26 с кодом, в котором

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

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

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

0 Начало - инициализация устройства и формирование сигнала пуска.

Блок 32 - запись, кода номера еершины в счетчик 16 импульсов блока управления, перебором вершин.

5 Блок 33 - формирование импульсов сдвига регистров 4 с участием счетчиков 16, 17.

Блок 34 - анализ состояния осведомительного сигнала на полюсе 23. Если О - перейти на блок 35, иначе - на блок 37.

Блок 35 - подача одиночного импульса сдвига на полюс 25 для сдвига регистров 5.

Блок 36 - подача одиночного импульса на полюс 30, связанный с выходом (1) блока 15 формирования сигналов управления.

Блок 37-установка признака обратного хода на полюсе 2А.

Блок 38 - подача одиночного импульса на полюс 25 для сдвига назад регистров 5.

Блок 39 - передача кода номера вершины в счетчик (6) (аналогично блоку 32).

Блок 40 - сдвиг регистров 4 (аналогично блоку 33).

Блок 41 - то же, что и в блоке 34. Если О - перейти на блок 42, иначе - на блок 43.

Блок 42 - установить признак прямого хода на полюсе 24 и перейти на блок 35.

Блок 43 - сравнить код на полюсах 26 с кодом, содержащим единицы во всех разрядах. Если О - то перейти на блок 38, иначе - конец.

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

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

0 сдвига моделей вершин группы, группы входов задания начальной вершины и задания кода номера вершины которой являются соответственно первой и второй группами входов задания устройства, а выход сигнала

5 опроса последней модели вершины группы является выходом устройства, причем в каждую модель вершины введены первый и второй элементы НЕ, блок элементов И, выход которого является информационным выхо0 дом модели, первый вход - входом задания кода номера вершины, а второй вход подключен к выходу младшего разряда второго регистра сдвига, вход записи которого подключен к второму вхрду элемента ИЛИ и

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

0 подключен к установочному входу триггера, выход которого подключен к второму входу первого элемента И, выход которого подключен к входам соответственно первого и второго элементов НЕ, выход первого из

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

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

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

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

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

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

-фО(В)

г (4

&

Фиг./

23 24

% Щ8)

г&

s 4 з г /

Матрица с/ъе #0слгг/ &

H

«J

Pff3P( ufiutmff0Ј4 S 6

гг/

Фиг. Z

faf J0a/JltHltЈJU Јf{Јct

V