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

вИЗОБРЕТЕНИЯ Союз Советскик Социалистическик Республик(61) Дополнительное к авт, свид-ву(22) Заявлено 13. 09. 78 (21)2665194/18-24с присоединением заявки Ио(51)М. Кл. С 06 С 7/122 Государственный комитет СССР по делам изобретений и открытий(54 ) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ГРАФОВ Изобретение относится к вычислительной технике и может быть использовано при исследовании систем, блоки которых или системы в целом могут быть представлены в виде сетевых моделей или ярусных графов.Известно устройство для определения кратчайшего пути через сеть 1 Ц, содержащее программный задатчик параметров узлов, программный задатчик параметров дуг, блок элементов времени узлов.Недостатком этого устройства является то, что число дуг и узлов исследуемой сети или исследуемого графа не может превышать числа соответственно моделей узлов и дуг. Наиболее близким по технической сущности к предложенному является устройство, содержащее блок моделей вершин, блок формирования топологии и блок управления, генератор импульсов, элементы И, ИЛИ, триггеры 2 . 25 В этом устройстве число ветвей исследуемого сетевого графика не может превышать количество моделей ветви в устройстве. Цель изобретения - расширение класса решаемых задач за счет разбиения графа на подграфы. Поставленная цель достигается за счет того, что в устройство для моделирования графов, содержащее блок моделей вершин, состоящий из и моделей вершин, выходы каждой из которых соединены .с группой входов блока формирования топологии и со входами элемента. И, блок управления, вход которого подключен к выходу элемента И, генератор импульсов, введены счетчиК, блок памяти, статистический анализатор, причем выход генератора импульсов подключен к счетному входу счетчика, выход которого соединен с первым информационным входом блока управления и с информационным входом блока памяти, выход которого подключен ко входу статистического анализатора, выход которого соединен со вторым информационным входом блока управления, установочный выход которого подключен к установочным входам блока моделей вершин, счетчика и генератора импульсов, первая группа выходов настройки блока управления соединена со входами настройки блокамоделей вершин, вторая группа выходов настройки блока управления подключена ко входам настройки блока формирования топологии, группа управляющих выходов блока управления соединена с управляющими входами блока формирования топологии, выходы блока моделей вершин подключены к управляющим входам блока памяти.Кроме того, блок формирования тополонии содержит и моделей связнос- О ти, каждая из которых включает в себя элемент И, элементы ИЛИ и регистр, установочный нход которого соединен с соответствующим входом настройки блока формирования топологии, выходы регистра подключены к первым входам элементов ИЛИ, вторые входы которых соединены с соответствующими входами блока формирования топологии, выходы элементов ИЛИ соединены с инФормационными входами элемента И, управляющий вход которого подключен к соответстнующему управляющему входу блока формирования топологии, выход элемента И соединен с соотнетстнующим выходом блока Формирования . 25 топологии.На фиг.1 представлена структурная схема устройства;на фиг.2 - модель связности.Устройство для моделирования графов содержит: блок 1 моделей вершин, блок 2 формирования топологии, блок 3 управления, генератор импульсов 4, счетчик (импульсон) 5, блок памяти 6, статистический анализатор 7, элемент И 8.Блок 1 моделей вершин содержит управляемые генераторы 9 случайных временных интервалов, каждый из которых вырабатывает на выходе разрешающий сигнал через случайный интервал времени после поступления сигнала на его вход запускачто позволяет моделировать случайные веса вершин графа.Модель 10 связности содержит: регистр 11, элементы ИЛИ 12, элемент 45 И 13.Устройство рабОтает следующим образом.Блок 3 управления вырабатывает на выходе сигнал, по которому устанав О ливается в нуль счетчик 5, приводятся в исходное состояние генераторы 9,. Блок 1 моделей вершин и блок 2 Формирования топологии настраиваются блоком 3 на заданные вероятностные харак теристики весов вершин и на требуемую топологию граФа.Для этого на выходах блока 3 вырабатываются сигналы, настраивающие генераторы 9 на воспроизведение случайных временных интервалов с задан-ными нероятщэстными характеристиками и вырабатынаются сигналы, по которым в регистрах 11 моделей 10 связности устанавливаются коды, которые разрешают появление сигнала на выходе эле ментов И 13 лишь при определеннойкомбинации сигналов на входах элементов ИЛИ 12. Так, например, еслинеобходимо появление сигнала .на выходе модели 10 связности с номеромпри появлении сигналов на выходахгенераторов 9 с номерами 1,1,е(311 Ф 1 е), то в регистр 11 будет записан двоичный код с единицами вовсех разрядах, кроме к-го 1-го и а-го,значение которых равно нулю. Тем самым задается требуемая топология графа. Моделирование одной реализацииначинается по сигналам с блока 3,которые поступают одновременно навсе модели 10 связности и тем саьымразрешают их срабатывание. Одновременно запускается генератор 4 импульсов, сигналы с выхода которого поступают на вход счетчика 5, являющегося таймером модели.В моделях 10 первого яруса графасрабатывают элементы И 13, выходныесигналы которых запускают соответствующие генераторы 9, При возникновении в случайный момент времени сиг"нала на выходе какого-либо генератора 9 выполняется следующее.Во-первых, изменяются входные сигналы моделей 10 связности и тем самым н зависимости от связности вершин графа запускаются дополнительныегенераторы 9, чем моделируется начало выполнения очередных вершин графа.Во-вторых, сигнал с выхода генератора 9 поступает на соответстнукщийадресный вход блока б памяти. По адресу, соответствующему возбужденномуадресному входу, в блок 6 записывается состояние счетчика 5, в результате чего фиксируется момент окончаниявыполнения определенной вершины графа.В-третьих, сигнал с выхода генератора 9 поступает на элемент И 8,где контролируется момент окончаниявыполнения всех вершин графа,Таким образом устройство работаетдо тех пор, пока на всех входах элемента И 8 не появятся разрешающиесигналы, что свидетельствует об окончании моделирования одной реализации.Блок 3 по сигналу с выхода элементаИ 8 останавливает работу моделей 10и устанавливает н исходное состояние таймер и генераторы 9. Анализатор 7 обрабатывает в соответствии стребуемой программой исследованиясодержимое блока 6 памяти.Таким образом, устройство работает в случае, когда число вершин графа меньше или равно числу генераторов 9В противном случае ярусный граф разбивается на несколько графов, для каждого из которых выполнено предыдущее условие. Моделирование одной реализации полного графа разбивается на последовательное моделирование полученных графов.Сначало, аналогично предыдущему,моделируется первый граф, затем блок3 производит перенастройку генераторов 9 и моделей 10 в соответствии схарактеристиками второго графа. Дляучета связности первого и второгограФов блок 3 считывает из анализатора 7 коды времен окончания выполнения всех вершин первого графа, связанных согласно топологии с вершинами второго графа. Блок 3 для каждой-й вершины второго графа отыскивает.из множества кодов времени окончаниявершин первого графа, связанных сэтой -й вершиной, максимальный код,который, таким образом, является кодом начала выполнения )-й вершиныв полном графе,Блок 3 вырабатывает сигнал, покоторому устанавливаются в исходноесостояние таймер и генераторы 9. Запускается генератор 4 и начинаетсяработа таймера.В процессе счета таймера блок 3сравнивает код в счетчике 5 с полученными кодами начала работ вершин.второго графа. При равенстве кодовдля некоторой 1-й вершины второгографа блок 3 вырабатывает сигнал,по которому разрешается срабатывание )-й модели 10 связности и т.д.Описываемое устройство благодаряналичию новых элементов и связеймежду ними позволяет проводить анализ графов, у которых число вершинпревышает число генераторов блокамоделей вершин.Формула изобретения1.устройство для моделирования гра- . фов, содержащее блок моделей вершин, состоящий из и моделей вершин, выходы каждой из которых соединены с группой входов блока Формирования .топологии и со входами элемента И, блок управления, вход которого подключен к выходу элемента И, генератор импульсов, о т л и ч а ю щ е ес я тем, что, с целью расширения класса решаемых задач за счет воэможности разбиения графа на подграфы,в устройство введены счетчик, блокпамяти, статистический анализатор,причем выход генератора импульсовподлкючен к счетному входу счетчика,выход которого соединен с первыминФормационным входом блока управления и с информационным входом блокапамяти, выход которого подключен ковходу статистического анализатора,выход которого соединен со вторыминформационным входом блока управления, установочный выход которого подключен к установочным входам блокамоделей вершин, счетчика и генератора импульсов, первая группа выходовнастройки блока управления соединена15 со входами настройки блока моделейвершин, вторая группа выходов настройки блока управления подключенако входам настройки блока формирования топологии, группа управляющих20 выходов блока управления соединенас управляющими входами блока формирования топологии, выходы блока моделейвершин подключены к управляющим входам блока памяти.25 2.устройство по п.1, о т л ич а ю щ е е с я тем, что блок Формирования топологии состоит из п моделей связности, каждая из которых содержит элемент .И, элементы ИЛИ и регистр, установочный вход которогосоединен с соответствующим входомнастройки блока формирования топологии, выходы регистра подключены кпервым входам элементов ИЛИ, вторые35входы которых соединены с соответствующими входами блока формированиятопологии, выходы элементов ИЛИсоединены с информационными входамиэлемента И, управляющий вход которого подключен к соответствующему40 управляющему входу блока Формирования топологии, выход элемента И соединен с соответствующим выходом блока формирования топологии.Источники информации,принятые во внимание при экспертизе1.Авторское свидетельство СССР9 407345, кл. С 06 С 7/48, 1971.2.Авторское свидетельство СССРМ 422002, кл. С 06 С 7/48, 197250 (прототип).763911 Подписвоего комитета СССРи и открытийРаушская наб., д.4/5ППП Патент , г.ужгород,ул.Проектная,ил Составитель А.Ко актор Т.Орловская Техред Т,Иаточкаказ б 2 а 5/43 Тираж 751 ВНИИПИ Государственно по делам иэобретени 113035, Иосква, Ж