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

дючтиоф .ц с библиотъи ,)БА ОПИСАНИЕ ИЗОЬЕЕт ЕНИЯ р) 16460 Союз Советских Социалистических Республик(22) Заявлено 30,01.76 (21) 2318861/24 51) М. Кл,е б 066 7/486 066 7/122 аявкиприсоединением осударственный комите Совета Министров ССС па делам изобретенийи открытий 3) Гриоритет 681.333 (088,8(5 ата опубликования описания 31.05.7 Авторыизобрете, В. Васильев, О, Н. Голованова и Е. А. РалдугинИнститут электродинамики АН Украинской ССР Заявите 4) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ ГРАФИКОВ у критичетакже вели на взвешенопределять длиндом заданных за 2 ширение функциоИзобретение относится к области вычислительной техники.Известное по основному авт. св.422002 устройство для моделирования сетевых графиков содержит блок моделей ветвей, число которых равно числу работ сетевого графика, блок формирования топологии, блок управления и генератор импульсов.Каждая модель ветви содержит задатчики адресов начального и конечного узлов, формирователь временных интервалов, триггеры, элементы И, инвертор, элемент ИЛИ, Блок формирования топологии содержит элементы И, инвертор и элементы ИЛ 1 Л. Все модели ветвей соединены с блоком формирования топологии и с генератором импульсов, который выдает импульсы двух серий (А и Б). Устройство определяет величинского пути сетевого графика, ачину длиннейшего пути на сети (ном графе).Однако оно не позволяетнейший путь на сети с обхопрещенных узлов.Цель изобретения - раснальных возможностей устройства, а именно обеспечение возможности отыскания на сети длиннейшего пути, не проходящего через заданные узлы. Это достигается тем, что в предлагаемое устройство для моделирования сетевых графиков в каждую модель ветви введен дополнительный элемент И, в блок формирования топологии введены триггер, сдвиговый регистр и счетчик, вход которого соединен с входом сдвигового регистра и с выходом первого элемента ИЛИ блока формирования топологии, а выход счетчика соединен с единичным входом триггера блока формирования топологии, единичный выход которого подключен к одному из входов третьего элемента И блока формирования топологии, а нулевой выход триггера соединен с одним из входов второго элемента ИЛИ блока формирования топологии, а выход сдвигового регистра подключен к первому входу дополнительного элемента И каждой модели ветви, второй вход которого соединен с выходом задатчика адреса начального узла, а выход подключен к единичному входу второго триггера модели ветви.Запрещение узлов осуществляется посредством исключения ветвей, исходящих из запрещенных узлов. Это исключение ветвей производится установкой вторых триггеров соответствующих моделей ветвей в единичное состояние и выполняется в течение подготовительного периода, измеряемого У импульсами серии Б, где У - емкость задатчиков адресов и счетчика блока формирования то5 10 15 20 25 Зо 35 40 45 50 55 пологии, Поэтому в процессе моделирования длиннейших путей, который следует за подготовительным периодом, формирователи временных интервалов моделей ветвей, исходящих из запрещенных узлов, не включаются, и отсчет соответствующих временных интервалов не производится.На чертеже показана функциональная схема предлагаемого устройства.Схема содержит блок 1 моделей ветвей, блок 2 формирования топологии, блок 3 управления, генератор импульсов 4.Каждая модель ветви включает задатчики адресов 5, 6 начального и конечного узлов соответственно, формирователь 7 временных интервалов, триггеры 8, 9, элементы И 10, 11, 12, инвертор 13, элемент ИЛИ 14. Блок 2 формирования топологии содержит элементы И 15, 16, 17, элементы ИЛИ 18, 19, 20, инвертор 21, сдвиговый регистр 22, триггер 23 и счетчик 24.Пусть устройство работает в режиме многократного отыскания длиннейших путей, т. е, последовательно отыскиваются длиннейшие пути между начальным узлом сети и некоторым подмножеством остальных узлов сети. К моменту окончания определения одного из искомых длиннейших путей в регистр 22 уже занесена информация о запрещенных узлах для следующего длиннейшего пути. По сигналу пуска блок управления устанавливает все триггеры моделей ветвей и триггер блока формирования топологии в нуль. Нулевой выходной сигнал элемента И 15 совместно с нулевым сигналом из блока управления через элемент ИЛИ 20 и первые элементы И всех моделей ветвей запрещает включение формирователей временных интервалов. Запреты снимаются с моделей ветвей, не исходящих из запрещенных узлов, после просчета М импульсов серии Б, где У - емкость счетчика блока формирования топологии. (Считаем, что отсчет импульсов в каждом периоде работы начинается с нуля).Пусть после К импульсов серии Б сигнал перевыполнения появился на выходе задатчика адреса начального узла -й модели ветви, изображенной на чертеже, Если К-й узел не отмечен в регистре 22 блока формирования топологии единицей, то на выходе третьего элемента И с-й модели ветви не появляется единичного сигнала, и триггер 9 этой модели ветви остается в нулевом состоянии, Если же К-й узел является запрещенным, т. е, отмечен в регистре единицей, то на выходе элемента И 12 -й модели ветви (и остальных моделей ветвей, исходящих из К-го узла), единичный сигнал появляется и соответствующий триггер 9 устанавливается в единичное состояние, Формирователь временных интервалов упомянутой ветви не включается, а с единичного выхода триггера 9 подается разрешающий сигнал на элемент И 11.После и импульсов серии Б все п узлов моделируемой сети просматриваются аналогично, а в регистре 22 блока формирования топологии записываются нули. Импульсы серии Б продолжают поступать на задатчики адресов начальных и конечных узлов, так как триггер блока формирования топологии по-прежнему остается в нулевом состоянии. Единичный выходной сигнал элемента ИЛИ 18 блока формирования топологии через инвертор 21 запрещает подачу импульсов серии А на формирователи временных интервалов.После просчета М импульсов серии Б на выходе счетчика блока формирования топологии появляется единичный сигнал, по которому триггер 23 блока формирования топологии переключается в единичное состояние. После просчета У импульсов серии Б восстанавливается содержимое задатчиков адресов начальных и конечных узлов. Далее работа устройства протекает аналогично работе устройства по основному авт. св.422022.Таким образом, устройство благодаря введению новых элементов и связей обеспечивает расширение функциональных возможностей и позволяет решать задачи связи и теории графов. Формчла изобретения Устройство для моделирования сетевых графиков по авт. св.422002, о т л и ч а ющ е е с я тем, что, с целью расширения функциональных возможностей, в каждую модель ветви введен дополнительный элемент И, в блок формирования топологии введены триггер, сдвиговый регистр и счетчик, вход которого соединен с входом сдвигового регистра и с выходом первого элемента ИЛИ блока формирования топологии, а выход счетчика соединен с единичным входом триггера блока формирования топологии, единичный выход которого подключен к одному из входов третьего элемента И блока формирования топологии, а нулевой выход триггера соединен с одним из входов второго элемента ИЛИ блока формирования топологии, а выход сдвигового регистра подключен к первому входу дополнительного элемента И каждой модели ветви, второй вход которого соединен с выходом задатчика адреса начального узла, а выход подключен к единичному входу второго триггера модели ветви.За Типография, пр, Сапунов 118/17 Изд. Мц 414ЦНИИПИ Государственного комитетапо делам изобретений113035, Москва, Ж.35, Рауш Тираж 815 Совета Мшшс и открытий ская паб., д. 4