Устройство для исследования сетевых графиков Советский патент 1987 года по МПК G06F15/173 

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

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

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

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

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

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

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

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

генератора 11 проходит на входы этих счетчиков, так как по прохождении К импульсов содержимое счетчиков, соответствующих начальным вершин.ам, станет равным О, т.е.

начальные вершины имеют нулевой ранг. Во- вторых, импульс с выхода элементов И 13 поступает на входы установки в ноль триггеров 2 одноименных строк матрицы 1 моделей дуг и обнуляет их.

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

каждого обнуления триггеров 2 одной или нескольких строк матрица 1 моделей дуг увеличивает число элементов ИЛИ-НЕ 3, на всех входах которых присутствует нулевой, а на выходе - единичный потенциал,

5 соответственно увеличивается число счетчиков 14, на входы которых проходят импульсы генератора 11. Тогда не позднее, чем на момент прохождения К-го импульса, все строки матрицы 1 обнуляются, и при выдаче счетчиком 16 сигнала переполнения

0 после отсчета им К импульсов генератор 11 прекращает работу. На всех входах элемента И-НЕ 7 должен присутствовать единичный потенциал, а на его выходе - нулевой потенциал, и выключенное состояние

, элемента 15 свидетельствует об отсутствии контуров в графике. Содержимое счетчиков 14 указывает ранг вершин графа.

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

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

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

с графика с наличием ложного тупика (вершина 4) и хвоста (вершина 6), которые будут указаны включенными элементами 64 и 5б соответственно, так как все триггеры четвертой строки и шестого столбца матрицы 1 моделей дуг будут в нулевом со0 стоянии. После устранения этих ошибок по мнемосхеме графа в нем останется контур (фиг. 26) с участием вершин 2, 3, 6. Тогда в исходном состянии обнуляются триггеры 2 первого столбца матрицы 1 и седьмой ее строки, единичный потенциал появляется на

5 выходе элементов ИЛИ-НЕ 3| и 4, включаются элементы 5i и бу.

При подаче сигнала на вход 10 генератор Пначинает выдачу импульсов, первый

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

держит триггер, вход запуска генератора импульсов является входом пуска устройства, отличающееся тем, что, с целью расширения функциональных возможностей уст5 ройства за счет обеспечения возможности обнаружения ошибок в топологии сетевого графика, в него введены две группы элементов ИЛИ-НЕ, элемент И-НЕ, счетчик и группа счетчиков, причем выход триггера Р, К-го узла матрицы моделей дуг ,...,М:

0 к. 1,...,М, где М - количество вершин в сетевом графике) подключен к Р-му входу К-го элемента ИЛИ-НЕ первой группы и К-му входу Р-го элемента ИЛИ - НЕ второй группы, выход которого подключен к Р-му

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

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

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

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

к. 1,...,М, где М - количество вершин в сетевом графике) подключен к Р-му входу К-го элемента ИЛИ-НЕ первой группы и К-му входу Р-го элемента ИЛИ - НЕ второй группы, выход которого подключен к Р-му

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

5

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

Изобретение относится к вычислительной технике, может быть использовано для анализа результатов объединения нескольких фрагментов сетевого графика в единый сетевой график и позволяет обнаруживать ошибки типа контуров и ложных (тупиковых и хвостовых вер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

Редактор С. Патрушева Заказ 3804/45

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

Техред И. ВересКорректор В. Бутяга

Тираж 672По.чпмсное

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

1 13035, Москва, Ж-35, Раушская наб., д. 4.5 Производствеино-полиграфическое предприятие, г. Ужгород, ул. Проектная. 4