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

 

О rI И С А Н И Е ?32898

ИЗОБРЕТЕН ИЯ

Союз Советски к

Социалистическик

Республик

Н АВТОРСНОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) Заявлено09.11.77 (21) 2541796/18»24 (5) ) Щ Кл

G06 G 7/122 с присоединением заявки .%

Государственный комитет

СССР (23) Приоритет ао делам изобретений н открытий (53) УДК681,3. .001.57 (088.8) ОпУбликовано 05.05.80. Бюллетень № 17

Дата опубликования описания 08 05 80 (72) Авторы изобретения

А. Г. Додонов, О. Н. Голованова, Я, Я. Фенюк и В. В. Хаджинов

Институт электродинамики АН Украинской CCP (7! ) Заявитель (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

ГРАФОВ

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

Известно устройство для моделирования графов (Ц, содержащее модели ветвей графа, соединенные согласно топологии графа, Каждая модель ветви содержит счетчик временного интервала, два триггера, элементы И и элементы ИЛИ. Уст ройство позволяет решать ряд задач на направленных графах.

Недостатком устройства является малое быстродействие за счет ручной ком- . мутации графа.

Наиболее близким по технической сущ15 ности к изобретению является устройство для моделированйя сетевого графа (2), содержащее блок управления, генератор, два выхода которого подключены соотнес ственно к первому и второму входам блока ормирования топологии, первый и вто рой выходы которого соединены соотве вственно с первыми и вторыми Bxog&MH блоков моделей ветвей, каждый из кото

2 рых содержит два счетчика адреса, входы которых подключены к первому входу блока модели ветви, счетчик временного интервала, выход которого соединен с единичными входами первого и второго триггеров, элементы ИЛИ и элемент И. Первый вход первого элемента И подключен ко второму входу блока модели ветви,второй вход — к нулевому входу первого триг гера и к первому входу второго элемента И, выход которого подключен к первому выходу блока модели ветви. Единичный выход первого триггера соединен со вторым выходом блока модели ветви, единичный выход второго триггера каждого блока модели ветви - с соответствующим входом из первой группы входов блока формирования топологии, Зто устройство позволяет автоматически формировать топологию и предназначено для нахождения критических путей в ориентированном графе. Однако имеются задачи, математической моделью в которых является неориентированные графы, 3 7328 например задачи об оптимальном дереве. связи, оптимальной связывающей сети.

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

I задач.

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

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

Ф

И каждого блока модели ветви. Выход третьего элемента И соединен с нулевым входом первого триггера, второй axonсо вторым входом второго элемента И и единичным выходом второго триггера, счет- 25 ный ахоп которого соединен с выходом первого элемента И, третий вход которо

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

Выходы счетчиков адреса подключены ко 40 входам соответствующих элементов ИЛИ.

Первый и второй выходы блока формирования топологии jсоединены соответственно с третьим и четвертым входами блока управления, второй выход которого под- 45 ключен к нулевым входам вторых триггеPoB„

Блок управления содержит два счетчика, элемент задержки, инвертор и два элемента И, первые и вторые входы которых 50 соединены с первым входом блока. и вьтходом первого счетчика соответственно.

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

98 4 со вторым выходом блока, Третий и четвертый входы блока подключены к счетным входам первого и второго счетчиков соответственно.

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

Устройство содержит блок 1 моделей ветвей, блок 2 формирования топологии, блок 3 .управления, генератор 4, элемент, 5 .ИЛИ-HE и формирователь 6 импульсов.

Блок 1 модели ветви состоит иэ счет ! чика 7 временного интервала счетчиков 8, 9 адреса, первого и второго триггеров

10, 11, элемента 12 ИЛИ, элементов И

13-16, входных и выходных полюсов

° 17-24 (полюса 17 и 18 являются первым и вторым входом, а полюса 19 и 20— первым и вторым выходами блока соотвеч ственно) .

Блок 2 имеет первый 26, второй 27 и третий 28 выходы, первую 29 и вторую

30 группы входов.

Блок 3 управления имеет два выхода

31 и 32 и четыре входа 33-36, и состоит из элемента задержки 37, двух элементов И 38 и 39, инвертора 40 и двух счетчиков 41 и 42.

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

В исходном состоянии триггеры 10, 11 находятся в нулевом состоянии. В счетчике 7 записано количество импульсов, пропорциональное длительностям соответствующих им ветвей исследуемого графа, В счетчиках 8 и 9 заданы в обратном коде адреса вершин графа, инцидентных, согласно топологии исследуемого графа, данной ветви.

В блоках 1, не принимающих участие в моделировании графа, счетчики 8 и 9 находятся в нулевом состоянии.

Фаза 1 - поиск очередной сформированной модели ветви, которая может входить в решение задачи. После подачи сигналов пуска, формирователь 6 импульсов подает импульсы на входы счетчиков 7 временного интервала, Первым появляется сигнал переключения в том счетчике 7, в который была записана самая большая дли» тельность. По этому сигналу в этом блоке 1 устанавливаются в единичное состояние триггеры 10 и 11, и сигнал с единичного выхода триггера 11 поступает на один из входов первой группы в блоке 2. По этому сигналу блок 2 выдает на управляющий вход формирователя 6 сигнал, запрещающий подачу импульсов на

Работа устройства в режиме по фазе 2 описана выше.

В режиме по фазе 2 подсчитываются сигналы свяэаности, поступившие на входы 30 блока 2. Сигналы свяэаности, собираюшиеся по схеме ИЛИ в блоке 2 с выхода 27 поступают на вход 36 блока 3 управления, который подсчитывает их. Конец определения связности оставшегося подграфа определяется элементом 5

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

Как только окончится процесс определения связности оставшегося подграфа в режиме по фазе 2, триггеры 12 всех моделей ветвей находятся в нулевом состоянии, и на всех входах элемента 5 присутствуют нулевые сигналы. При этом с выхода элемента 5 выдается на вход 33 блока 3 разрешаюший единичный сигнал.

5 (328 счетчики 7. Признаком удаления ветви иэ графа служит единичное состояние выхода

20 в соответствующем блоке модели ве ви, Фаза 2 - определение связанности всех вершин графа. Если оставшиеся вершины графа связаны между собой, то данная ветвь окончательно удаляется иэ графа, в противном случае она возвращается в граф. о

Одновременно с прекрашением формирования длительностей ветвей блок 2 формирования топологии с выхода 26 начинает выдачу импульсов на входы 17 всех блоков. Эти сигналы поступают на входьE 15 счетчиков 8 и 9 адреса для автоматического формирования топологии. Первым по является сигнал на выходе эадатчиков 8 или 9 адресов, в которых записан перв начальный адрес Bl, потом на выходах 20 задатчиков адресов, в которых записан следующий 1 адрес В2, и т.д. Для провер« ки связности ветвей, оставшихся в графе, т.е. в тех моделях 1 ветви, в которых триггер 10 находится в нулевом состоянии, по первоначальному адресу Bl блок

2 формирования топологии выдает единичный логический уровень на входы 18 блоков 1. Втех блоках 1,,в которых запи- . сан адрес Bl и триггер 10 находится в нулевом состоянии единичный логический уровень с выхода элемента 13 И устанавливает в единичное состояние триггер 11, Теперь на входах элемента 14 И имеются сигналы логической единицы, и единичный сигнал с выхода этого элемента подается на второй вход элемента 16 И. При поступлении сигнала второго адреса с выходов счетчиков адреса 8 и 9 через элемент 12 ИЛИ на первый вход элемента

16 И единица с его выхода поступает на один из входов второй группы блока 2, Число входов в первой и второй группах входов соответствует числу блоков 1.

При наличии хотя бы одного единичного сигнала на входах 30 блок 2 формирования топологии выдает на выход 27 си нал, который поступает на входы 18 блоков 1. В моделях ветвей, присутствующих в графе, и в которых есть сигналы второ- го адреса, присутствуют единичные логические уровни на всех входах элемента

13 И. Сигналы единицы q выходов элементов 13 И поступают на счетные входы триггеров 11, Те триггеры 11, которые в этот мэмент времени нахолиллсь в единичном состоянии, перебрасываются в нулевое состо98 6 янке, а триггеры 11, находившиеся в нулевом состоянии, переходят в единичное состояние, и таким образом сигналы связности передаются следующим моделям ветвей по следуюшим адресам вершин графа.

Чередуя режимы работы данного уст ройства по фазам 1 и 2 находят, HaIIpEE

Мер, минимальное связываюшее дерево следующим образом. В режиме по фазе l импульсы с выхода формирователя поступают одновременно на входы счетчиков 7 всех блоков 1. Модели ветвей формируют свои длительности по порядку уменьшения их величин, начиная с самой большей.Как только какой-нибудь блок 1 сформировал свою длительность, два триггера 10 и 11 устанавливаются в единичное состояние.

Единица с единичного выхода триггера

11 сформированной модели ветви поступает на один из входов 29 блока 2. При наличии хотя бы одной единицы на входах

29 блок 2 с выхода 28 выдает запрет формирователю 6 на выдачу импульсов формирования временных интервалов, и опновременно начинает выдавать импульсы с выхода 26 на выходы счетчиков 8 и 9 адресов всех моделей ветвей, т.е. производится переключение работы устройства в режиме по фазе 2 для определения связности графа без сформированной и отключенной по фазе 1 ветви, 98 8 навливается в нулевое состояние. Счет чик 42 предназначен для подсчета количества связных вершин в графе. Перед началом работы устройства для моделирс вания графов в режиме по фазе 2 счет чик 42 сбрасывается по входу 34 в исходное состояние N - (где N — емкость, счетчика, V - число вершин в графе решаемой задачи). Через Ч импульсов, поступающих.на вход 36 блока 3, на выходе счетчика .42 появляется импульс переполнения, а на выходе инвертора 40 - нулег вой сигнал. Сигнал сброса триггеров 10 с выхода 31 блока 3 вырабатывается при одновременном присутствии единиц на всех входах элемента И 39, т,е. после

Ькончания определения связности оставшегося подграфа, регенерации информации о топологии в блоках 1 и признака, что не все вершины исходного графа связаны, Если все вершины исходного графа связаны, на выходе инвертора 40 имеется ну» левой сигнал, который запрещает срабатывание элемента 39 И. После конца определения связности. оставшегося подграфа импульс переполнения с выхода счетчика

41 поступает на элемент 38 И. Сигнал выхода :влемента 38 И через элемент 37 задержки поступает на выход 32 блока 3 каксигналсброса триггеров 11 в блоках 1.

Введение новых элементов и связей позволило расширить класс решаемых задач и дало возможность параллельной обработки информации одновременно во всех моделях ветвей, т.е. увеличило быстродействие устройства.

7 7328

По этому сигналу, определяющему конец определении связности вершин оставшего подграфа, если не будут достигнуты все вершины исходногографа,блок 3 с выхода 31 выдаетсигнал единицы на входы 21 всех блоков 1. В блоке 1 модели ветви, исключенной иэ графа в предыдущем режиме по фа зе 1, триггер 11 дает разрешающий потенциал на вход элемента 15 И, и триггер 10 устанавливается в нулевое состоя-1.0 ние, так как эта ветвь входит в решение задачи. Если исключение ветви в предыдущем режиме по фазе 1 не влияет на связанность вершин исходного графа, блок 3 не выдает сигнала на входы 21 блоков 1 ,и исключенная ветвь не возвращается в граф. В любом случае после прихода сигнала единицы с выхода элемента 5 на вход 33 блока 3 через некоторое время задержки, необходимое для анализа связ- >О ности вершин, блок 3 с выхода 32 выдает сигнал на входы 24 всех блоков 1, по которому производится сброс триггеров

11 и убираются все сигналы единицы на входах 29 блока 2, т.е. устройство для. моделирования графов снова переключается в режим по фазе 1 и т.д, Устройство останавливается после того, как произойдет формирование временных интервалов и пробное исключение всех® ветвей графа. Зто происходит автоматически за один просчет регенерационного счетчика вформирователе,,работающем параллельно со всеми счетчиками 7. На этом решение задачи заканчивается.Три З5, геры 10.в блоках моделей ветвей принадлежащих минимальному связывающему дереву, находятся в единичном состоянии.

Единичные сигналы с выходов 20 моде40 лей 1 ветвей могут подаваться на устройство или табло индикации. При этом исходная информация о длительностях веъ. вей, записанная в счетчиках 7, восстанавливается. Величина связывакицего дерева может быть определена поочередным суммированием длительностей ветвей ему принадлежащих.

Максимальное связывающее дерево на.ходят аналогично, с той лишь разницей, Ю 50 что исходная информация в длительности ветвей графа записывается в обратном коде.

Рассмотрим блок 3 управления. Счеч чик 41 предназначен для регенерации ин55 формации об адресах в моделях ветвей, Емкость счетчика 41 равна емкости счет чиков 8 и 9 адреса в блоках 1. Перед началом решения задачи счетчик 41 устаФормула изобретения

1, Устройство для моделирования графов, содержащее блок управлении генератора, два выхода которого подключены соответственно к первому и второму входам блока формирования топологии, первый и второй выходы которого соединены соответственно с первыми и вторыми входами блоков моделей ветвей, каждый из которых содержит два счетчика адреса, входы которых подключены к первому входу блока модели ветви, счетчик временного интервала, выход которого соединен с единичными входами первого и второго триггеров, элемент ИЛИ и элементы И, первый вход первого элемента И подключен ко второму входу блока модели ветви, второй вход первого элемента И соединен с нулевым выходом первого триггера и с

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

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

898 10 чен ко второму входу блока управления и

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

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

Источники информации, принятые во внимание при экспертизе

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

% 305484, кл. 606 С 7/48 1970

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

% 422002, кл. С 06 5 7/48, 1972 {прототип).

732898 зг и

З6

91/2 Я

Составитель А. Яицков

Техред O. Андрейко Корректор И. Муска

Редактор Л, Утехина

1 филиал ППП Патент, г.Ужгород, ул.Проектная, 4

Заказ 1739/39 Тираж 751 Подписное

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

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