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

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

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

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

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

Устройство для моделирования графов содержит: блок 1 моделей вершин, блок 2 формирования топологии, блок 3 управления, генератор импульсов 4, счетчик (импульсов) 5, блок памяти 6, статистический анализатор 7, элемент И 8.

Блок 1 моделей вершин содержит управляемое генераторы 9 случайных временных интервалов, каждый из которых вырабатывает на выходе разрешающий сигнал через случайный интервал времени после поступления сигнала на его вход запуска/что позволяет моделировать случайные веса вершин графа. Модель 10 связности содержит: регистр 11, элементы ИЛИ 12, элемент И 13.

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

Блок 3 управления вырабатывает на выходе сигнал, по которому устанавливается в нуль счетчик 5, приводятся в исходное состояние генераторы 9.. Блок 1 моделей вершин и блок 2 формирования топологии настраиваются блоком 3 на заданные вероятностные характеристики весов вершин и на требуемую топологию графа.

Для этого на выходгис блока 3 вырабатываются сигналы, настраивающие генераторы 9 на воспроизведение случайных временных интервалов с заданными вероятчрстными характеристиками и 1вырабатываются сигналы, по которым в регистрах 11 моделей 10 связности устанавливаются коды, которые разрешают появление сигнала на выходе элементов И 13 лишь при определенной комбинации сигналов на входах элементов ИЛИ 12. Так, например, если необходимо появление сигнала .на выходе модели 10 связности с номером j при появлении сигналов на выходах генераторов 9 с номерами k.l.nn (), то в регистр 11 будет записан двоичный код с единицами во всех разрядах, кроме k-ro 1-го и тзначение которых равно нулю. Тем самьпл задается требуемая топология графа. Моделирование одной реализации начинается по сигналам с блока 3, которые поступают одновременно на все модели 10 связности и тем caNttJM разрешают их срабатывание. Одновременно запускается генератор 4 импульсов , сигналы с выхода которого поступают на вход счетчика 5, являющего ся таймером модели.

В моделях 10 первого яруса графа срабатывают элементы И 13, выходные сигнсшы KOTOpfcix запускают соответствующие генераторы 9. При врзникновении в случайный момент времени сигнала на выходе какого-либо генератора 9 выполняется следующее.

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

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

В-третьих, сигнал с выхода генератора 9 поступает на элемент И 8, где контролируется момент окончания выполнения всех вершин графа.

Таким образом устройство работает до тех пор, пока на всех входах элемента И 8 не появятся разрешающие сигналы, что свидетельствует об окончании моделирования одной реализации Блок 3 по сигналу с выхода элемента И 8 останавливает работу моделей 10 и устанавливает в исходное состояние таймер и генераторы 9. Анализатор 7 обрабатывает в соответствии с требуемой программой исследования содержимое блока 6 памяти.

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

Сначало, аналогично предьадущему, моделируется первый граф, затем блок 3 производит перенастройку генераторов 9 и моделей 10 в соответствии с характеристиками второго графа. Для учета связности первого и второго графов блок 3 считывает из анализатора 7 коды времен окончания выполнения всех вершин первого графа, связанных согласно топологии с веЕянинами второго графа. Блок 3 для каждой j-й вершины второго графа отыскивает из множества кодов времени окончания вершин первого графа, связанных с этой J-й вершиной, максимальный код, который, таким образом, является кодом начсша выполнения j-й веряиины в полном графе.

Блок 3 вырабатывает сигнал, по которому устанавливаются в исходное состояние таймер и генераторы 9. Запускается генератор 4 и начинается работа таймера.

В процессе счета таймера блок 3 сравнивает код в счетчике 5 с полученными кодами начала работ вершин второго графа. При равенстве кодов для некоторой j-и вершины второго графа блок 3 вырабатывает сигнал, по которому разрешается срабатьгаание j-й модели 10 связности и т.д.

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

изобретения

Формула

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

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

Источники информации, 5 принятые во внимание при экспертизе

1.Авторское свидетельство СССР 407345, кл. G Об G 7/48, 1971.

2.Авторское свидетельство СССР № 422002, кл. G Об G 7/48, 1972 0 (прототип).