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

/20, 1984. СЛЕДОВА вычислипользовацо инения цеграфика в вол яет обров и ложшин). Устделей дуг, две группы группы элеГОСУДАРСТВЕННЫИ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ВТОРСКОМЪ( СВИДЕТЕПЬСТ(54) УСТРОЙСТВО ДЛЯ ИС НИЯ СЕТЕВЫХ ГРАФИКОВ (57) Изобретение относится к тельной технике, может быть ис для анализа результатов объед скольких фрагментов сетевого единый сетевой график и поз наруживать ошибки типа конту ных (тупиковых и хвостовых вер ройство содержит матрицу 1 мо выполненных в виде триггеров 2, элементов ИЛИ - НЕ 3 и 4, две ментов 5 и 6 индикации, элемент И- -НЕ 7, элемент ИЛИ 8, элемент И 9, вход 1 О пуска устройства, генератор 11 импульсов, трипер 2, группу элементов И 13, групп счетчиков 14, элемент 15 индикации, счетчик 16.В исходном состоянии в счетчики 4 и 16 заносят код, равцый количеству вершин графа, в матрицу 1 заносят информацию о топологии сетевого графика ц подачей сигнала ца вход 10 запускают генератор 1. Через соответствующие элементы И 13 импульсы с выхода генератора поступак)т на входы установки в нуль триггеров соответствующих строк матрицы 1. Если в топологии сетевого графа контуры отсутствуют, то цс поздцес чем ца момент прохождения К-го импульса генератора 11 все триггеры должны быть обнулецы, о чсм свидетельствует выключен- Я цое состояние элемента 15. Если контуры есть (элеенс 15 внэюнен), вынллюненню (/) элементы 6 указывают вершины, которые могут его образовывать. 2 ил.5055 Изобретение относится к вычислительной технике и может быть использовано для анализа результатов объединения нескольких фрагментов сетевого графика в единый сетевой график.Цель изобретения - расширение функциональных возможностей устройства за счет обеспечения возможности обнаружения ошибок в топологии сетевого гафика.На фиг. 1 представлена функциональная схема примера исполнения устройства; на фиг. 2 - фрагмент сетевого графика с ошибками в топологии (а), с устранением тупиковых и хвостовых вершин (б), с устранением контура (в).Устройство содержит матрицу 1 моделей дуг, выполненных в виде триггеров 2, две группы элементов ИЛИ - НЕ 3 и 4, две группы элементов 5 и 6 индикации, элемент И - НЕ 7, элемент ИЛИ 8, элемент И 9, вход 10 пуска устройства, генератор 11 импульсов, триггер 2, группу элементов И 13, группу счетчиков 14, элемент 15 индикации, счетчик 16,Устройство работает следующим образом.В исходном состоянии в счетчики 14 и 16 заносят код, равный количеству К вершин графа, триггер 12 обнуляют, а те триггеры 2, которые соответствуют дугам графа, устанавливают в единичное состояние. Единичные потенциалы присутствуют на выходах тех элементов ИЛИ - НЕ 3 и 4, которые соответствуют хвостовым и тупиковым вершинам, и, если включены элементы 5 и 6, не соответствующие начальным и конечным вершинам, то устраняют ошибки в схеме графа и в матрице 1.Подачей сигнала на вход 10 осуществляют запуск генератора 11, импульсы которого проходит на выход элемента И 9 благодаря наличию разрешающего потенциала на выходе элемента И - НЕ 7, на ряде входов которого имеется нулевой потенциал. Состояние элемента 15 до окончания работы устройства значения не имеет.Первый же импульс генератора 11 устанавливает в единичное состояние триггер 12 так, что до конца работы устройства единичный потенциал с выхода триггера 2 через элемент ИЛИ 8 подается на первый вход элемента И 9. Импульсы с выхода элемента И 9 поступают также на вычитающий вход счетчика 16 и на входы элементов И 13, однако первый импульс проходит на выходы лишь тех элементов И 13, на вторые входы которых подается единичный потенциал с выходов соответствующих элементов ИЛИ - НЕ 3, на всех входах которых присутствует нулевой потенциал с выхода триггеров 2 тех столбцов матрицы 1, которые относятся к начальным вершинам, С выходов элементов И 13 импульс поступает, во-первых, на вычитающие входы одноименных счетчиков 14 и уменьшает их содержимое на 1. И далее каждый импульс генератора 11 проходит на входы этих счетчиков, так как по прохождении К импульсов содержимое счетчиков, соответствующих начальным вершинам, станет равным О, т.е.начальные вершины имеют нулевой ранг. Вовторых, импульс с выхода элементов И 13 поступает на входы установки в ноль триггеров 2 одноименных строк матрицы 1 моделей дуг и обнуляет их.Если в графике нет контуров, то после 1 О каждого обнуления триггеров 2 одной илинескольких строк матрица 1 моделей дуг увеличивает число элементов ИЛИ - НЕ 3, на всех входах которых присутствует нулевой, а на выходе - единичный потенциал, 1 соответственно увеличивается число счетчиков 14, на входы которых проходят импульсы генератора 11. Тогда не позднее, чем на момент прохождения К-го импульса, все строки матрицы 1 обнуляются, и при выдаче счетчиком 16 сигнала переполнения 20 после отсчета им К импульсов генератор11 прекращает работу. На всех входах элемента И - НЕ 7 должен присутствовать единичный потенциал, а на его выходе - нулевой потенциал, и выключенное состояние элемента 15 свидетельствует об отсутствии контуров в графике. Содержимое счетчиков 14 указывает ранг вершин графа.При наличии в сетевом графике контура на некотором импульсе генератора 11 после вычеркивания очередной строки мат- ЗО рицы 1 моделей дуг число элементов ИЛИ -НЕ 3 и 4, на всех входах которых присутствуют нули, а на выходе - единичный потенциал, возрастать не будет. Поэтому при останове генератора 11 на некоторых входах элемента И - НЕ 7 присутствуют нуЗ левые потенциалы, на его выходе - единичный потенциал, и включенное состояние элемента 15 является свидетельством наличия контура в графике. Тогда по выключенным блокам 6 находят вершины, которые могут входить в контур, и по схеме 40 графика находят его и устраняют, Далееснова запускают устройство до тех пор, пока при очередном останове генератора 11 блок 15 не будет выключен.На фиг, 2 а показан пример сетевого 4 графика с наличием ложного тупика (вершина 4) и хвоста (вершина 6), которые будут указаны включенными элементами 64 и 5 в соответственно, так как все триггеры четвертой строки и шестого столбца матрицы 1 моделей дуг будут в нулевом состоянии. После устранения этих ошибок по мнемосхеме графа в нем останется контур (фиг. 2 б) с участием вершин 2, 3, 6. Тогда в исходном состянии обнуляются триггеры 2 первого столбца матрицы 1 и седьмой ее строки, единичный потенциал появляется на выходе элементов ИЛИ - НЕ 3 и 4 включаются элементы 5 и 6 у.При подаче сигнала на вход 10 генератор 11 начинает выдачу импульсов, первый1336026 г.г Составитель ва Техред И. Вере Тираж 672 венного комитета СССР иеда кто р С. Патр у шаказ 380445НИИПИ Государс1303Производственно-п из которых проходит на выход элемента И 3 и обнуляет триггеры 2 первой строки матрицы 1. Вследствие этого и на выходе элемента ИЛИ - НЕ 3; появляется единичный потенциал, так что второй импульс генератора 11 проходит уже и через элемент И 13 з и обнуляет триггеры 2 пятой строки матрицы 1, вследствие чего единичный потенциал появляется и на выходе элемента ИЛИ - НЕ 34. Поэтому третий импульс генератора 11 проходит и через элемент И 134 и обнуляет триггеры 2 четвертой строки матрицы 1. Однако это не увеличивает число элементоа ИЛИ в3, на выходах которых присутствуют единичные потенциалы, поэтому по окончании работы устройства по сигналу переполнения сцетчика 16 на ряде входов элементов И - НЕ 7 (на втором, третьим и шестом) присутствует нулевой потенциал и элемент 15 включен, что свидетельствует о наличии контура. Включенные элементы бз, 6 з, бг, укажут. вершины, которые могут образовывать контур. После нахождения и устранения контура пользователем с помощью схемы графика (фиг. 2 в) в результате работы устройства в счетчик 14 будут зафиксированы ранги вершин, на выходе элемента И - НЕ 7 появится нулевой потенциал, и включенный элемент 15 будет свидетельствовать об отсутствии контуров в сетевом графике. формула изобретенияУстройство для исследования сетевых графиков, содержащее матрицу моделей дуг, группу элементов И, генератор импульсов, элемент И, элемент ИЛИ и триггер, причем каждый узел матрицы моделей дуг содержит триггер, вход запуска генератора импульсов является входом пуска устройства, отличающееся тем, цто, с целью расширения функциональных возможностей устройства за счет обеспечения возможности обнаружения ошибок в топологии сетевого графика, в него ввелены лве группы элементов ИЛИ - НЕ, элемент И - НЕ, счетцик и группа сцетчиков, причем выход триггера Р, К-го узла матрицы моделей дуг Р=1М;10 К=1М, гле М - количество вершин в сетевом графике) подключен к Р-му входу К-го элемента ИЛИ - НЕ первой группы н К-му входу Р-го элемента ИЛИ - НЕ второй группы, выход которого подключен к Р-му 15 входу элемента И - НЕ и является Р-ымвыходом признака принадлежности Р-й вершины контуру сетевого графика устройства, выход элемента И - НЕ подключен к первому входу элемента ИЛИ и является выходом признака наличия контуров в сетевом 20 графике устройства, выхол генератора импульсов подключен к первому входу элемента И, выход которого полключен к вычитающему входу сцетцика, к первым входам всех элементов И грх ппы и вхо; х становки в 1 триггера, выход которого подключен к второму входу элемента ИЛИ, выход которого подключен к второму входу элемента И, выход К-го элемента ИЛИ - НЕ первой группы подключен к второму входу К-го элемента И группы, выход котоЗ 0 рого подключен к входам установки в 0триггеров всех узлов К-й строки матрицы моделей луг и вычитаюгцему входу К-го счетчика группы, выход признака переполнения счетчика подключен к входу останова генератора импульсов. А. Мишинс Корректор В. Б,тягаПодписноео делам изобретений и открытийская наб., д. 4 51 е, г. Ужгород, ул. Проектная. 4