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

 

УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ ГРАФОВ, содержащее генератор импульсов, блок определения рангов вершин графа, состоящий из матрицы формирователей дуг,каждый формирователь дуг которой содержит триггер, п элементов ИЛИ, п элементов и, п счетчиков , п схем сравнения по числу столбцов матрицы (-« - число вершин графа), блок управления , включающий реверсивный счетчик , выходы триггеров j-x столбцов (, п) формирователя дуг соединены с входами j-x элементов ИЛИ, выходы которых соединены с информационными входами соответствующих элементов И, выходы элементов И подключены к информационным входам соответствующих счетчиков, выходы которых соединены с первыми входами схем сравнения, вторые входы которых объединены и соединены с выходом реверсивного счетчика блока управления, выход каждой j-й ( схемы сравнения подключен к входам триггеров j-й строки (,n) матрицы формирователей дуг, выход генератора импульсов соединен с управляющим входом блока управления , управляклций выход которого соединен с управляющими входами h элементов И блока определения рангов вершин графа, отличающее с.я тем, что, с целью расширения функциональных возможностей устройства путем определения длительности -поярусного выполнения сетевого графа, в него введены блок регистрации, содержащий реверсивный счетчик, группу элементов И и сумматор, блок счетчиков длительности , содержащий три группы из п элементов И, п счетчиков и элемент ИЛИ, а блок управления дополнительно содержит.пять элементов и, три элемента ИЛИ, два триггера,два элемента НЕ и формирователь импульсов , причем первый управляющий вход блока управления соединен с первыми входами первого, второго третьего и четвертого элементов И блока управления и первыми входами i элементов И первой группы блока счетчиков длительности, вторые вхо (Л ды первого и второго элементов И блока управления объединены и подключены к единичному выходу первого триггера блока управления и вторым входам элементов И первой группы блока счетчиков длительности,третий вход первого элемента И блока , управления соединен с единичным выходом второго триггера блока управления , а выход - с вычитакицим входом реверсивного счетчика блока, регистрации , третий вход второго элеСП мента И и первый вход пятого элеменО ) та И блока управления объединены и подключены к нулевому выходу второго триггера блока управления и к управляющим входам элементов И группь блока регистрации, выход второго элемента И блока управления соединен с первыми входами первого и второго элементов ИЛИ блока управления, вторые входы третьего и четвертого элементов И блока управления объединены и подключены к нулевому выходу первого триггера блока управления, выход третьего элемента И блока управления соединен с суммирующим входом реверсивного счетчика блока управления , выход четвертого элемента И

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

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

РЕСПУБЛИК

З(59 G 06 F 15 20

ОПИСАНИЕ ИЭОБРЕТЕНИ

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3513865/18-24 (22) 23.11.82 (46) 30.01.84. Бюл. Р 4 (72) В.Н. Кустов, M ° Г. Мальцев и A.H. Ярмош (53) 681.333(088.8) (56) 1. Авторское свидетельство СССР

9 525954, кл. G 06 F 15/20, 1974.

2. Авторское свидетельство СССР

Р 716043, кл. G 06 F 15/20, 1977 (прототип). (54)(57) УСТРОИСТВО ДЛЯ МОДЕЛИРОВАИИЯ СЕТЕВЫХ ГРАФОВ, содержащее генератор импульсов, блок определения рангов вершин графа, состоящий из матрицы формирователей дуг,каждый формирователь дуг которой содержит триггер, и элементов ИЛИ, и элементов И, и счетчиков, . п схем сравнения по числу столбцов матрицы (-и — число вершин графа), блок управления, включающий реверсивный счетчик выходы триггеров J-x столбцов ()=1, и) формирователя дуг соединены с входами g-х элементов ИЛИ, выходы которых соединены с информационными входами соответствующих элементов И, выходы элементов И подключены к информационным входам соответствующих счетчиков, выходы которых соединены с первыми входами схем сравнения, вторые входы которых объединены и соединены с выходом реверсивного счетчика блока управления, выход каждой j-й ()=1, n) схемы сравнения подключен к входам триггеров J-й строки ()=1,n) матрицы формирователей дуг, выход генератора импульсов соединен с управляющим входом блока управления, управляющий выход которого соединен с управляющими входами и элементов И блока определения рангов вершин графа, о т л и ч а ю щ е» е с.я тем, что, с целью расширения функциональных возможностей устройства путем определения дли„„80„„1070560 A тельности .поярусного выполнения сетевого графа, в него введены блок регистрации, содержащий реверсивный счетчик, группу элементов И и сумматор, блок счетчиков длительности, содержащий три группы из и элементов И, и счетчиков и зле мент ИЛИ, а блок управления дополнительно содержит. пять элементов И, три элемента ИЛИ, два триггера,два элемента НЕ и формирователь импульсов, причем первый управляющий вход блока управления соединен с первыми входами первого, второго третьего и четвертого элементов И блока управления и первыми входами элементов И первой группы блока

Ф счетчиков длительности, вторые вхоВ ды первого и второго элементов И блока управления объединены и подключены к единичному выходу первого триггера блока управления и вторым входам элементов И первой группы блока счетчиков длительности, третий вход первого элемента И блока, управления соединен с единичным выходом второго .триггера блока управления, а выход — с.вычитающим входом реверсивного счетчика блока. регистрации, третий вход второго элемента И и первый вход пятого элемен та И блока управления объединены и подключены к нулевому выходу втррого триггера блока управления и к .управляющим входам элементов И груп блока регистрации, выход второго зл мента И блока управления соединен с первыми входами первого и второго элементов ИЛИ блока управления, вто рые входы третьего и четвертого элементов И блока управления объединены и подключвны,к нулевому выходу первого триггера блока управления, выход третьего элемента И блока управ-. ления соединен с суммирующим входом реверсивного счетчика блока управления, выход четвертого элемента И

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

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

Известно устройство для опреде- 5 ления кратчайшего пути в графе, содержащее генератор импульсов, выход которого подключен к входу блока управления, и матрицу формирователей дуг, причем выходы формировате- ð лей дуг каждого столбца соединены с входами соответствующего элемента

ИЛИ (17.

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

НЕ блока управления, выходы реверсивного счетчика блока регистрации соединены с информационными входами элементов И группы блока регистрации, выходы которых подключены к информационным входам сумматора, третьи входы элементов И первой группы блока счетчиков длительности соединены с выходами соответствующих схем срав1 нения блока определения рангов вер шин графа, первые входы элементов И второй группы блока счетчиков длитель. ности являются инфррмационными входами устройства, вторые входы объединены и являются управляющим входом,устройства, а выходы объединены

:с выходами соответствующих элементов И первой группы блока счетчиков длительности и подключены к суммирующим входам счетчиков блока счетчиков длительности, выходы которых соединены через соответствующие элементы И третьей группы с входами элемен- та ИЛИ блока счетчиков длительности, вы ход которого соединен с нулевым входом, второго триггера блока управления.

2 выход счетчика числа импульсов соеди. нен с первыми входами блоков сравнения, выход каждого элемента ИЛИ подключен к второму входу соответствующего элемента И, выход которого соединен с входом соответствующего регистрирующего счетчика, выход кото-— рого подключен к второму входу соот. ветствующего блока сравнения, выход которого соединен с входами формирователей дуг соответствующей строки Г21.

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

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

Поставленная цель достигается тем, что в устройство, содержащее генератор импульсов, блок определения рангов вераин графа, состоящий из матрицы формирователей дуг, каждый формирователь дуг которой содержит. триггер, и элементов ИЛИ,.

1070560

30

50

65 и элементов И, и счетчиков, и схем сравнения по числу столбцов матрицы (.n — - число вершин графа), блок управления, включающий реверсивный счетчик, выходы триггеров j-x стобцов (j=1,n) формирователя дуг соединены с входами j-х элементов

ИЛИ, выходы которых соединены с информационными входами соответствующих элементов И, выходы элементов

И подключены к информационным вхо- 10 дам соответствующих счетчиков,выходы которых соединены с первыми входами схем сравнения, вторые входы которых объединены и соединены с выходом реверсивного счетчика бло- 5 ка управления, выход каждой )-й ()=1,n) схемы сравнения подключен к входам триггеров j-й строки (j=1,п) матрицы формирователей дуг, выход генератора импульсов соединен с управляющим входом блока управления, управляющий выход которого соединен с управляющими входами и элементов И блока определения рангов вершин графа, дополнительно введены блок регистрации, содержащий реверсивный счетчик, группу элементов

И и сумматор, блок счетчиков длительности, содержащий три группы из и элементов И, и счетчиков и элемент

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

ВхОДам элементОВ И перВОЙ Группы 45 блока счетчиков длительности, третий вход первого элемента И блока управления соединен с единичным выходом второго триггера блока управления, а выход — с вычитающим входом реверсивного счетчика блока регистрации, третий вход второго элемента И и первый вход пятого элемента И блока управления объединены и подключены к нулевому выходу второго триггера блока управления и к управляющим входам элементов И группы блока регистрации, выход второго элемента И блока управления соединен с первыми входами первого и второго элементов ИЛИ блока управления, вторые входы третьего и четВертого элементов И схемы управления объединены и подключены к нулевому выходу первого триггера блока управления, выход третьего элемента

И блока управления соединен с суммирующим входом реверсивного счетчика блока управления, выход четвертого элемента И блока управления является управляющим выходом блока управления, второй вход пятого элемента И блока управления через первый элемент HE блока управления соединен с выходом реверсивного счетчика блока управления, а выход — с первым входом генератора импульсов, второй вход которого является пусковым входом устройства, второй вход первого элемента ИЛИ блока управления является входом установки исходного состояния устройства, и соединен с нулевым входом первого триггера блока управления, управляющими входами реверсивного счетчика блока .управления, сумматора блока регистрации, счетчиков блока счетчиков длительности и счетчиков блока определения рангов вершин графа, выход первого элемента ИЛИ блока управления подключен к единичному входу второго триггера блока управления и суммирующему входу реверсивного счетчика блока регистрации, второй вход второго элемента ИЛИ блока управления соединен через формирователь импульсов с Выходом второго элемента НЕ .и единичным входом первого триггера блока управления, а выход - с вычитающим входом реверсивного счетчика блока управления, входы третьего элемента ИЛИ блока управления соединены с выходами элементов ИЛИ блока определения рангов Вершин графа, а выход — с входом второго элемента НЕ блока управления, выходы реверсивного счетчика .блока регистрации соединены с информационными входами элементов И группы блока регистрации, выходы которых подключены. к информационным входам сумматора, третьи входы элементов И первой группы блока счетчиков длительности соединены с выходами соответствующих схем сравнения блока определения рангов вершин графа, первые входы элементов И второй группы блока счетчиков длительности являются информационными Входами устройства, вторые входы объединены и являются управляющим входом устройства, а выходы объединены с выходами соответствующих элементов И первой группы блока счетчиков длительности и подключены к суммирующим входам счетчиков блока счетчиков длительности, выходы которых соединены через соответствующие элементы И третьей группы с входами элемента ИЛИ блока счетчиков длительности, выход которого соединен с нулевым входом второго триггера блока управления.

1070560

На чертеже приведена структурная схема устройства.

Устройство содержит блок 1 регистрации, блок 2 управления, блок

3 счетчиков длительности, блок 4 определения рангов вершин графа, re- 5 нератор 5 импульсов, вход 6 установки исходного состояния устройства,.пусковой вход 7 устройства, информационные входы 8 и 9 устройства и управляющий вход 10 устройства. 10

Блок 1 регистрации включает реверсивный счетчик 11, группу элементов И 12 и сумматор 13.

Блок 2 управления содержит эле- 15 мент И 14, элемент ИЛИ 15, триггер

16, реверсивный счетчик 17, элемент

И 18, элемент ИЛИ 19, элемент И 20, формирователь 21 импульсов, элемент

И 22, триггер 23, элемент НЕ 24, элемент ИЛИ 25, а также элементы НЕ

36 и И 37. Блок 3 счетчиков длительности состоит нз элемента ИЛИ 26, группы элементов И 27, группы счетчиков 28, группы элементов И 29 и группы элементов И 30.

Блок 4 определения рангов вершин графа содержит группу схем 31 сравнения, группу счетчиков 32, группу элементов И 33, групйу элементов

ИЛИ 34 и матрицу из триггеров 35 формирователей дуг.

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

Первоначально в блок 4 заносится информация о топологии моделируемого З5 графа сети ° При этом сигналы, поступающие на входы триггеров 35 формирователей дуг, моделирующих ветви графа, устанавливают их в единичное состояние. Соответствующий триггер 40 формирователей дуг определяется пересечением строки с номером, равным номеру начального узла моделируемой ветви, и столбца с номером, равным номеру ее конечного узла. После 45 занесения исходной информации на выходах элементов 34, объединяющих выходы триггеров 35 формирователей дуг в столбцах, соответствующих начальным узлам моделируемого графа, 50 имеются низкие потенциалы, так как в однонаправленном графе без циклов и петель начальные узлы не содержат входящих ветвей и триггеры формирователей дуг, находящиеся в этом столбце, будут в нулевом состоянии.

СигНал начальной установки, поступающий на вход 6 устройства, подается далее на управляющие входы сумматора 13, счетчиков 17, 28 и 32, нулевой вход триггера 23 и обнуляет их.60

Этот же сигнал поступает иа первый вход элемента ИЛИ 15, а с его выхода - на единичный вход триггера 16 и на суммирующий вход счетчика 11. при этом на соответствующих выходах 65 триггеров 23 и 16 появляется единичный потенциал, а на счетчике 11 устанавливается единичный код во всех разрядах.

Сигнал на входе 10 разрешает прием на счетчик 28 прямого кода длительностей соответствующих узлов графа, поступающих на входы 9 устройства. Сигнал на входе 10, поступая на управляющие входы элементов И 29, разрешает прохождение через них сигналов с входов 9 прямого кода длительности счета соответствующего узла графа, который поступает на вторые входы элементов И 29. С выходов элементов И 29 код коступает на информационные входы счетчиков 28, где и запоминается.

С поступлением пускового сигнала с входа 7 на первый вход генератора

5 импульсов на его выходе появляются сигналы, синхронизирующие работу устройства. Единичный потенциал с первого выхода триггера 23 подается на вторые входы элементов И 22 и 20 и разрешает прохождение поступающих на первые .их входы сигналов с выхода генератора импульсов. Сигнал с выхода элемента И 20,поступающий на суммирующий вход счетчика 17, прибавляет к его содержимому "1". Одновременно сигнал с выхода элемента

И 22 поступает на управляющие входы элементов И 33, при этом сигналы не проходят через элементы И 33 на входы счетчиков 32 тех столбцов, все триггеры 35 которых находятся в нулевом состоянии. Далее содержимое счетчиков 32 поступает на первые входы схем 31 сравнения соответствующего столбца, на вторые входы которых подается информация со счетчика 17. При несовпадении показаний счетчиков 17 и 32 схема 31 сравнения. вырабатывает импульс, который сбрасывает в нулевое состояние триггеры 35 формирователей дуг строки с номером, равным .номеру столбца, в схеме сравнения которого не произошло сравнения. С появлением очередного сигнала на выходе генератора импульсов процесс повторяется.

Вичислительный процесс продолжается до тех пор, пока все триггеры

35 не будут обнулены. Как только последний из них обнулится, нулевые сигналы с выхсдов элементов ИЛИ 34 поступят на входы элемента ИЛИ 25, а с еМ выхода — на вход элемента

HE 24. Появившийся на его выходе единичный сигнал поступит на единичный вход триггера 23 и переведет его в единичное состояние . Сигнал с выхода элемента НЕ 24 поступит также на вход формирователя 21 импульсоа„ c его выхода — на вход элемента ИЛИ 19, с выхода которого—

1070560. на вычитающий вход счетчика 17. Это необходимо для получения на счетчике 17 кода, равного номеру максимального ранга. При появлении данного кода на счетчике 17 на вы.ходах схем 31 сравнения, соответствующих узлам графа максимального г ранга, появится единичный сигнал. который поступит на входы выбранных элементов И 30 на вторые входы которых поступит единичный потенциал. с единичного выхода триггера 23, поэтому поступающие на первые входы этих элементов сигналы с выхода генератора импульсов будут проходить через них на суммирующий вход счетчиков 28, увеличивая их содержимое на единицу. Этот же импульс с генератора импульсов, поступая на вычитающий вход счетчика

11 через элемент И 14, вычтет из его содержимого единицу. Импульс с генератора импульсов, поступив на первый вход элемента И 14,,про„ ходит через него, так как на два других входа поданы разрешающие по генциалы: на второй вход — с выхода триггера 23, а на третий — с выхода триггера 16.

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

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

13. В этом случае на сумматоре оказывается код, равный максимальной длительности из длительностей узлов наивысшего ранга.

Кроме того, единичный потенциал с выхода триггера 16 подается на третий вход элемента И 18 и вместе с единичным потенциалом с выхода триггера 23, который подается на второй вход, разрешает прохождение через элемент H 18 поступившего на его первый вход импульса с генератора 5 импусов. Сигнал с выхода элемента И 18 поступает на второй вход элемента ИЛИ 15 и с его выхода на суммирующий вход счетчика

11, устанавливая на нем вновь единичный код во всех разрядах, и на единичный вход триггера 16. Сигнал

15 с выхода элемента И 18 подается также на первый вход элемента ИЛИ 19 и с его выхода на вычитающий вход счетчика 17. Вычитание единицы из содержимого счетчика 17 (счетчика

7п номера ранга) и перевод в единичное состояние триггера 16 позволяют с приходом очередного импульса с генератора импульсов начать процесс выявления узла графа с максимальной

25 длительностью в следующем ранге и подсуммирование соответствующего кода к содержимому сумматора.

По окончании этого процесса при обнулении счетчика 17 в сумматоре

13 оказывается код, равный времени счета по графу, узлы которого предварительно распределены по рангам. Этот .процесс оканчивается тогда, когда к содержимому сумматора

13 и дсу иру я длительность симального узла нулевого ранга и код в нем становится равным времени счета по графу, узлы которого предварительно распределены по рангам.При

-этом генератора 5 импульсов будет

40 остановлен сигналом с выхода элемента И 37, на первый вход которого подается единичный сигнал с нулевого выхода триггера 16, а .на второй вход — сигнал с выхода второго эле45 мента HE 36, который инвертирует сигнал с выхода счетчика 17.

Таким образом, устройство предварительно распределяет граф по рангам а затем для всех рангов выявляет

Ф

5О узлы с максимальной длительностью выполнения и суммирует коды длительностей, им соответствующие, что расширяет функциональные возможности устройства путем определения длительности поярусного выполнения сетевого граФа.

Составитель С. Назаров

Редактор T. Мермелштейн Техред В.Далекорей Корр«тор В. Бутяга

Заказ 11683/46 Тираж 699 Подписное

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

113035, Москве, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4