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

 

Изобретение относится к вычислительной технике, может быть использовано для анализа результатов объединения нескольких фрагментов сетевого графика в единый сетевой график и позволяет обнаруживать ошибки типа контуров и ложных (тупиковых и хвостовых вер1нин). Устройство содержит матрицу 1 моделей дуг, выполненных в виде триггеров 2, две группы элементов ИЛИ-НЕ 3 и 4, две группы элементов 5 и 6 индикации, элемент И- -НЕ 7, элемент ИЛИ 8, элемент И 9, в.чод 10 иуска устройства, генератор 1 1 импульсов, триггер 12, группу элементов И 13, груииу счетчиков 14, элемент 15 индикации, счетчик 16. В исходном состоянии в счетчики 14 и 16 заносят код, равный количеству вершин графа , в матрицу 1 заносят информацию о топологии сетевого графика и нодачей сигнала на вход 10 занускают генератор П. Через соответствующие элементы И 13 импульсы с выхода генератора поступают на входы установки в нуль триггеров соответствующих строк матрицы 1. Если в тоиологии сетевого графа контуры отсутствуют, то не позднее чем на момент нро.чождения К-го импульса генератора 1 1 все триггеры должны быть обнулены, о чем свидетельствует выключенное состояние элемента 15. Если контуры есть (элемент 15 включен), выключенные элементы 6 указьшают верншны, которые могут его образовывать. 2 ил. «о (Л со оо 05 о to Oi

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (5!) 4 G 06 Е 15 20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АBTOPCHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4060108/24-24 (22) 25.04.86 (46) 07.09.87. Бюл. № 33 (72) Г. С. Колесник (53) 681.333 (088.8) (56) Авторское свидетельство СССР

¹ 716043, кл. G 06 F 15/20, 1977.

Авторское свидетельство СССР № 1070560, кл. G 06 F 15/20, 1984. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ СЕТЕВЫХ ГРАФИКОВ (57) Изобретение относится к вычислительной технике, может быть использовано для анализа результатов объединения нескольких фрагментов сетевого графика в единый сетевой график и позволяет обнаруживать ошибки типа контуров и ложных (тупиковых и хвостовых вершин). Устройство содержит матрицу 1 моделей дуг, выполненных в виде триггеров 2, две группы элементов ИЛИ вЂ” HE 3 и 4, две группы эле„„SU„„1336026 А 1 ментов 5 и 6 индикации, элемент И- -HE 7, элемент ИЛИ 8, элемент И 9, вход 10 пуска устройства, генератор 11 импульсов, триггер !

2, группу элементов И 13, группу счетчиков 14, элемент 15 индикации, счетчик 16.

В исходном состоянии в счетчики !4 и 16 заносят код, равный количеству вершин графа, в матрицу 1 заносят информацию о топологии сетевого графика и подачей сигнала

«а вход 10 запускают генератор 11. Через соответствуюгцие элементы И 13 импульсы с выхода генератора поступак>т на входы установки в нуль триггеров соответствующих строк матрицы 1. Если в топологии сетевого графа контуры отсутствуют, то нс позднее чем на момент прохождения К-го импульса генератора 11 все триггеры должны быть обнулены, о чсм свидетельствует выключсHное состояние элемента 15. Если контуры есть (элемент 15 включен), выключенные элементы 6 указывают вершины, которые могут его образовывать. 2 ил.

1336026

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

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

На фиг. 1 представлена функциональная схема примера исполнения устройства; на фиг. 2 — фрагмент сетевого графика с ошибками в топологии (а), с устранением тупиковых и хвостовых вершин (б), с устранением контура (в).

Устройство содержит матрицу 1 моделей дуг, выполненных в виде триггеров 2, две группы элементов ИЛИ вЂ” НЕ 3 и 4, две группы элементов 5 и 6 индикации, элемент И вЂ” НЕ 7, элемент ИЛИ 8, элемент И 9, вход 10 пуска устройства, генератор 11 импульсов, триггер 12, группу элементов И 13, группу счетчиков 14, элемент 15 индикации, счетчик 16.

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

В исходном состоянии в счетчики 14 и

l6 заносят код, равный количеству К вершин графа, триггер 12 обнуляют, а те триггеры 2, которые соответствуют дугам графа, устанавливают в единичное состояние. Единичные потенциалы присутствуют на выходах тех элементов ИЛИ вЂ” НЕ 3 и 4, которые соответствуют хвостовым и тупиковым вершинам, и, если включены элементы 5 и 6, не соответствующие начальным и конечным вершинам, то устраняют ошибки в схеме графа и в матрице 1.

Подачей сигнала на вход 10 осуществляют запуск генератора 11, импульсы которого проходит на выход элемента И 9 благодаря наличию разрешающего потенциала на выходе элемента И вЂ” НЕ 7, на ряде входов которого имеется нулевой потенциал.

Состояние элемента 15 до окончания работы устройства значения не имеет.

Первый же импульс генератора 11 устанавливает в единичное состояние триггер 12 так, что до конца работы устройства единичный потенциал с выхода триггера 12 через элемент ИЛИ 8 подается на первый вход элемента И 9. Импульсы с выхода элемента И 9 поступают также на вычитающий вход счетчика 16 и на входы элементов И 13, однако первый импульс проходит на выходы лишь тех элементов И

13, на вторые входы которых подается единичный потенциал с выходов соответствующих элементов ИЛИ вЂ” НЕ 3, на всех вхоaах которых присутствует нулевой потенциал с выхода триггеров 2 тех столбцов матрицы 1, которые относятся к начальным вершинам. С выходов элементов И 13 импульс поступает, во-первых, на вычитающие входы одноименных счетчиков 14 и уменьшает их содержимое на 1. И далее каждый импульс

55 стоянии. После устранения этих ошибок по мнемосхеме графа в нем останется контур (фиг. 2б) с участием вершин 2, 3, 6. Тогда в исходном состянии обнуляются триггеры 2 первого столбца матрицы 1 и седьмой ее строки, единичный потенциал появляется на выходе элементов ИЛИ вЂ” НЕ 3i и 4 включаются элементы 5 и 6, При подаче сигнала на вход 10 генератор 11начинает выдачу импульсов, первый генератора 11 проходит на входы этих счетчиков, так как по прохождении К импульсов содержимое счетчиков, соответствующих начальным вершинам, станет равным О, т.е. начальные вершины имеют нулевой ранг. Вовторых, импульс с выхода элементов И 13 поступает на входы установки в ноль триггеров 2 одноименных строк матрицы 1 моделей дуг и обнуляет их.

Если в графике нет контуров, то после

10 каждого обнуления триггеров 2 одной или нескольких строк матрица 1 моделей дуг увеличивает число элементов ИЛИ вЂ” НЕ 3, на всех входах которых присутствует нулевой, а на выходе — единичный потенциал, 1 соответственно увеличивается число счетчиков 14, на входы которых проходят импульсы генератора 11. Тогда не позднее, чем на момент прохождения К-го импульса, все строки матрицы 1 обнуляются, и при выдаче счетчиком 16 сигнала переполнения

20 после отсчета им К импульсов генератор

11 прекращает работу. На всех входах элемента И вЂ” НЕ 7 должен присутствовать единичный потенциал, а на его выходе — нулевой потенциал, и выключенное состояние элемента 15 свидетельствует об отсутствии контуров в графике. Содержимое счетчиков

14 указывает ранг вершин графа.

При наличии в сетевом графике контура на некотором импульсе генератора 11 после вычеркивания очередной строки матЗ0 рицы 1 моделей дуг число элементов ИЛИ—

НЕ 3 и 4, на всех входах которых присутствуют нули, а на выходе — единичный потенциал, возрастать не будет. Поэтому при останове генератора 11 на некоторых входах элемента И вЂ” НЕ 7 присутствуют нуЗ левые потенциалы, на его выходе — единичный потенциал, и включенное состояние элемента 15 является свидетельством наличия контура в графике. Тогда по выключенным блокам 6 находят вершины, которые могут входить в контур, и по схеме

40 графика находят его и устраняют. Далее снова запускают устройство до тех пор, пока при очередном останове генератора

11 блок 15 не будет выключен.

На фиг. 2а показан пример сетевого

4 графика с наличием ложного тупика (вершина 4) и хвоста (вершина 6), которые будут указаны включенными элементами

64 и 5 соответственно, так как все триггеры четвертой строки и шестого столбца матрицы 1 моделей дуг будут в нулевом со1336026

Составитель А. Мишин

Редактор С. Патрушева Техред И. Верее Корректор В. В,тяга

Заказ 3804j45 Тираж 672 Подписное

ВНИИПИ Государственного комитета СССР Во делам изобретений и открытий

1! 3035, Москва, УК вЂ” 35, Раушская наб., д. 4 5

Производственно-полиграфицеское предприятие, г. Ужгород, i.л. Проектная. 4 из которых проходит на выход элемента

И 13! и обнуляет триггеры 2 первой строки матрицы l. Вследствие этого и на выходе элемента ИЛИ вЂ” НЕ 3; появляется единичный потенциал, так что второй импульс генератора 11 проходит уже и через элемент И 135 и обнуляет триггеры 2 пятой строки матрицы 1, вследствие чего единичный потенциал появляется и на выходе элемента ИЛИ вЂ” HE 34. Поэтому третий импульс генератора 11 проходит и через элемент И 134 и обнуляет триггеры 2 четвертой строки матрицы 1. Однако это не увеличивает число элементоа ИЛИ вЂ” НЕ 3, на выходах которых присутствуют единичные потенциалы, поэтому по окончании работы устройства по сигналу переполнения счетчика 16 на ряде входов элементов И вЂ” НЕ 7 (на втором, третьим и шестом) присутствует нулевой потенциал и элемент

15 включен, что свидетельствует о наличии контура. Включенные элементы 6, 6з, бг, укажут. вершины, которые могут образовывать контур. После нахождения и устранения контура пользователем с помощью схемы графика (фиг. 2в) в результате работы устройства в счетчик 14 будут зафиксированы ранги вершин, на выходе элемента И вЂ” НЕ

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

Формула изобретения

Устройство для исследования сетевых графиков, содержащее матрицу моделей дуг, группу элементов И, генератор импульсов, элемент И, элемент ИЛИ и триггер, причем каждый узел матрицы моделей дуг содержит триггер, вход запуска генератора импульсов является входом пуска устройства, отличающееся тем, что, с целью расширения функциональных возможностей устройства за счет обеспечения возможности обнаружения ошибок в топологии сетевого графика, Rнего введены,дBE группы элементов ИЛИ вЂ” НЕ, элемент И вЂ” НЕ. счетчик и группа счетчиков, причем выход триггера Р, К-го узла матрицы моделей дуг Р=1,...,M;

10 К= 1,...,М, где М вЂ” количество вершин в сетевом графике) подключен к Р-му входу

К-го элемента ИЛИ вЂ” HE первой группы н

К-му входу P-го элемента ИЛИ вЂ” НЕ второй группы, выход которого подключен к Р-му

15 входу элемента И вЂ” НЕ и является P-ым выходом признака принадлежности Р-й вершины контуру сетевого графика устройства, выход элемента И вЂ” HE подключен к первому входу элемента ИЛИ и является выходом признака наличия контуров в сетевом

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

И, выход которого подключен к вычитающему входу счетчика, к первым входам всех элементов И группы и входу установки в «1» триггера, выход которого подключен к второму входу элемента ИЛИ, выход которого подключен к второму входу элемента И, выход К-го элемента ИЛИ—

НЕ первой группы подключен к второму входу К-го элемента И группы, выход кото3Q рого подключен к входам установки в «О» триггеров всех узлов К-й строки матрицы моделей дуг и вычитаю!цему входу К-го счетчика группы, выход признака переполнения счетчика подключен к входу останова генератора импульсов.