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

10

15

20

11325500

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

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

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

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

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

В матрицу 1 заносят информацию о опологии графа, загружая в соответ- ствз ющие регистры 3 веса дуг . Обнулят распределитель 6, счетчики 19 и 20 и регистры 11 и 12.

После подачи сигнала пуска импульсы с выходагенератора 5 поступают на вход распределителя 6, который поочередно выдает импульсы на свои выходы. мпульс с первого выхода распределителя 6 открьгоает блок 4 элементов И одели 2 (М-1,М)-го узла матрицы 1 между (М-1)-й и М-й вершинами графа, через соответствующий блок 7 элементов IfflH поступает на соответствующий вход блока 9, который выдает его на выход в инверсном коде, а блок 10 - в прямом коде. Через переключатель 22 подвес дуги поступает на информационные входы регистров 11. Задним фронтом импульса с первого выхода распределителя 6 вес этой дуги, равный величине максимального пути из (М-1)-й в М-ю вершину графа, записывается в соответствующий регистр 11,

При постзшлении импульса с второго выхода распределителя 6 открьшают- ся блоки 4 моделей 2 (М-2)-й строки матрицы 1 и вес дуги (М-2,М) с выхода соответствующего регистра 3 через соотбл от ги бл го вт ве вую ду да туп ра код ном пер вхо (Мпризап рог

гич

25 пос ре вел шин Имп

3Q ля сод ным мла ет

35

съ зап наю вую ни

40 фа лич чи ра по

ij5 с 11 то пр ос ра пр ко сп аг об

им на

50

55

00

2

ответствующий блор; 4 элементов И и блок 7 элементов ИЛИ поступает на соответствующий вход блока 9, а вес дуги (М-2; М-1) через соответствующий блок 7 элементов ИЛИ - на вход первого слагаемого сумматора 13, на вход второго слаг 1емого которого поступает вес дуги (М-1,М) с выхода соответствующего регистра 11. Суммарный вес дуги (М-2,М-1) и дуги (М-1,И) с выхода соответствующего сумматора 13 поступает на вход блока 9, который выбирает наибольший из двух поступивших кодов и выдает его на выход в инверсном, а блок 10 - в прямом коде через переключатель 22 на информационные входы регистров 11, из которых лишь (М2)-и регистр 11 записывает его, при поступлении на его вход признака записи заднего фронта импульса с второго выхода распределителя 6.

Далее устройство работает аналогично, и после прохождения импульса С

последнего выхода распределителя 6 в регистрах 11 оказываются записанными величины 1 максимальных путей из вершин графа в его конечную М-ю вершину, Импульс (М-1)-го выхода распределителя б поступает на вход счетчика 20, содержимое которого становится равным 1. Единичньй сигнал с выхода младшего разряда счетчика 20 поступает на выход устройства как сигнал на

35

съем величин Т и на входы признака записи регистров 12, которые запоминают поступающие с выходов соответствующих вычитателей 16 наиболее поздние времена вьтолнения вершин гра40 фа, получаемые путем вычитания из величины If, поступающей на входы вычитателей I6 с выхода первого регистра 11, величин максимальных путей, поступающих на входы вычитателей 16

ij5 с выходов соответствуюшрих регистров 11, начиная с второго, задним фронтом импульса с (М-1)-го выхода распределителя 6, поступающим на вход останова генератора 5. Завершается работа устройства на первом этапе. Перед вторым этапом устройство приводят в исходное состояние, однако в матрицу 1 весов дуг графа транспонируют относительно неглавной диагонали. Счетчик 20 и регистры 12 не обнуляют.

После подачи пускового сигнала импульсы генератора 5 вновь поступают на вход распределителя 6, и далее уст50

55

ройство работает так же, как на первом этапе. В регистрах 11 оказьшают- ся записанными величины максимальных путей инвертированного графа, которые в прямом графе соответствуют наиболее ранним временам Тр выполнения вершин. При этом номера регистров 11 также должны инвертироваться, т.е. в первом регистре 11 записывается наиболее раннее время выполнения М-й вершины, а в (М-1)-м регистре 11 - наиболее раннее время выполнения первой вер- пшны.

При поступлении импульса с последнего выхода распределителя 6 содержимое счетчика 20 становится равным 2. Единичный сигнал с выхода его второго разряда поступает на выход устройства как сигнал на съем с выходов регистров 11 величин Тр наиболее ранних времен вьшолнения вершин и на входы опроса схем 21 сравнения. Схемы 21 сравнения сравнивают поступающие на их входы величины Тр (с выходов регистров П) и Tf, (с выходов регистров 12) и выдают на выходы устройства единичные сигналы только при равенстве Тр и Т , что имеет место лишь для вершин, лежащих на критическом пути. Таким образом, единичные сигналы на выходах тех или иных схем 21 сравнения указывают вершины, через которые проходит максимальньш критический путь графа между его начальной матрицы 1, обусловливает поступление

и конечной вершинами. На случай нали- чия в исследуемом графе двух или более таких одинаковых по величине путей по схеме графа уточняют, одному или нескольким таким путям принадлежат найденные вершины.

На третьем этапе для каждой дуги графа определяется свободный резерв времени -(Т„+Т), где Т - вес данной дуги. Дпя этого устройство вновь приводят в исходное состояние , не обнуляя, счетчик 20, регистры 11 и 12 и сохраняя записанную в матрице 1 информацию о топологии инвертированного графа. Переключатель 22 переводят в другое положение, подключая счетчик 18, в который заносят 1.

Затем вновь подают сигнал пуска и импульсы генератора 5 вновь поступают на вход распределителя 6, импульс с первого выхода которого открывает (Н-1,М)-й блок 4 элементов И, .и вес дуги (1,2) между первой и второй вершинами графа через соответствующий

40

45

50

55

веса дуги, записанного в (М-2,М-1)-м регистре 3, через блок 7 элементов ИЛИ на вход второго сумматора 14, на другой вход которого поступает значе ние Т,, (2) с выхода второго регистра 12 так, что на вход второго вычитателя 15 поступает величина Т„ (2)+Т(2,3

В результате с выходов соответствующих вычитателей 1Ь в темпе работы распределителя 6 снимаются величины свободных резервов времени дуг графа причем выдаваемые счетчиком 19 коды указьгоают номера конечных вершин дуг Причем, величина Р тогда указывает свободный резерв времени, когда она больше 0. Импульс с (M-l)-ro выхода распределителя 6, поступая на вход останова генератора 5, прекращает работу устройства.

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

Устройство для исследования путей в графе, с.одержащее две группы реблок 7 поступает на вход соответствующего сумматора 15, на другой вход которого через (М-2,М)-й блок 18, открытый импульсом с первого выхода распределителя 6, и соответствующий блок 8 элементов ИЛИ поступает значение Тр (2) времени вьшолнения второй вершины. На выход устройства с выхода вычитателя 15 вьщается величина Pj.(l,2) свободного резерва времени дуги (1,2) между первой и второй вершинами графа, при этом номер вычитателя 15 (в данном случае этот номер 1)

указывает номер начальной вершины дуги, а код на выходе счетчика 19 (в данном случае после поступления одного импульса с первого выхода распределителя 6, это код 2) - номер конечной вершины дуги.

Импульсы с второго, третьего и т.д. выходов распределителя 6 открывают блоки 18 элементов И соответствующих: строк матриць 17 для прохождения на входы соответствующих вычита

0

телей Тр с выходов соответствующих регистров 11, на другие входы вычита- телей 15 с выходов соответствующих сумматоров 14 (для первого вычитателя 1 5 с выхода М-го блока 7 элементов ИЛИ) - суммы значений Т и весов дуг Т. Например, импульс с второго выхода распределителя 6, открыв блоки 4 элементов И моделей 2 (М-2)-и строки

0

5

0

5

веса дуги, записанного в (М-2,М-1)-м регистре 3, через блок 7 элементов ИЛИ на вход второго сумматора 14, на другой вход которого поступает значение Т,, (2) с выхода второго регистра 12 так, что на вход второго вычитателя 15 поступает величина Т„ (2)+Т(2,3),

В результате с выходов соответствующих вычитателей 1Ь в темпе работы распределителя 6 снимаются величины свободных резервов времени дуг графа, причем выдаваемые счетчиком 19 коды указьгоают номера конечных вершин дуг. Причем, величина Р тогда указывает свободный резерв времени, когда она больше 0. Импульс с (M-l)-ro выхода распределителя 6, поступая на вход останова генератора 5, прекращает работу устройства.

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

Устройство для исследования путей в графе, с.одержащее две группы реw

гистров, блок выбора максимального кода и наддиагональн: то матрицу моделей дуг из (М-) строк и (м-) столбцов, где М - число вершин в графе, каждый узел которой содержит блок элементов И и регистр, выход которого подключен к первому входу блока элементов И, отличающееся тем, что, с целью расширения функциональных возможностей устройства за счет определения минимального и максимального веса ребер, соединенных с вершинами графа, в него введен распределитель импульсов, переключатель, блок элементов НЕ, две группы блоков элементов ИЛИ, две группы сзлмматоров. Группа схем сравнения, два счетчика, две группы вьгчитателей, генератор тактовых импульсов и надциагональная матрица опроса из (M-I) строк и (М-1) 20 столбцов, каждый узел которой содержит блок элементов И, причем вход пуска генератора тактовых импульсов является входом пуска устройства, выход генератора тактовых импульсов подключен к первому информационному входу переключателя и входу распределителя импульсов, (М-К)-й выход которого (К-1,...М-1) подключен к вторым вхогруппы, выход К-го сумматора первой группы (K;tM-l) подключен к К-му ин- форма1щонному входу блока выбора максимального кода, выход (M-l)-ro блока элементов ИЛИ первой группы подключен к (М-)-му информационному входу блока выбора максимального кода, выход которого подключен к входу блока элементов НЕ, выход которого подключен к второму информационному входу переключателя, второй выход которого подключен к информационным входам всех регистров первой группы, выход К-го регистра первой группы (Кт) подключен к вторьм входам всех блоков элементов И К-й строки наддиагональной матрицы опроса, к входам вычитаемого (K-I)-ro вычитателя первой группы, к входу второго слагаемого К-го суммато ра первой группы,..первому информацион ному входу (М-К)-й схемы сравнения группы и является К-м информационньм выходом первой группы устройства, выход первого регистра первой группы подключен к вторым входам всех блоков элементов И первой строки наддиагональной матрицы опроса, к входам уменьшаемого всех вычитателей первой гр уппы и является первым информацион15

25

дам всех блоков элементов и К-й стро- 30 ньм выходом первой группы устройства, ки наддиагональной матрицы моделей выход К-го вычитателя первой группы к

дуг, к входу признака записи К-го регистра первой группы и к первым входам всех блоков элементов И К-й строки наддиагональной матрицы опроса, (М-I)-и выход распределителя импульсов подключен к входу останова генератора тактовых импульсов и к счетному входу первого счетчика, выход младшего разряда которого подключен к входам признаков записи всех регистров второй группы и является выходом признака окончания первого этапа работы устройства, вькоды всех

() подключен к информационному входу К-го регистра второй группы, вы ход которого подключен к входу второ35 го слагаемого (М-К)-го сумматора второй группы и к второму информационному входу К-й схемы сравнения группы выход признак равенства которой является К-м информационным выходом вто 0 рой группы, выходы блоков элементов И К-го столбца (Ki l) наддиагональной ма трицы опроса подключены к соответствующим входам К-го блока элементов ИЛИ второй группы, выход которого под

рой группы, выходы блоков элементов И К-го столбца (Ki l) наддиагональной матрицы опроса подключены к соответствующим входам К-го блока элементов ИЛИ второй группы, выход которого подблоков элементов И К-го столбца (Kfl) 45 к.шочен к входу уменьшаемого (М-К)-го наддиагональной матрицы моделей дуг вычитателя второй группы, выход блока

подключены к соответствующим входам К-го блока (К/1) элементов ИЛИ первой группы, выход К-го блока элементов ИЛИ первой группы (К-г, М-1) подюгао- чен к входу первого слагаемого К-го сумматора первой группы и к входу первого слагаемого (М-К)-го сумматора второй группы, выход блока элементов И первого столбца наддиагональной матРИДЫ моделей дуг подключен к входу первого слагаемого первого сумматора первой группы и к входу первого слагаемого (М-1)го сумматора второй

w

20255006

группы, выход К-го сумматора первой группы (K;tM-l) подключен к К-му ин- форма1щонному входу блока выбора максимального кода, выход (M-l)-ro блока элементов ИЛИ первой группы подключен к (М-)-му информационному входу блока выбора максимального кода, выход которого подключен к входу блока элементов НЕ, выход которого подключен к второму информационному входу переключателя, второй выход которого подключен к информационным входам всех регистров первой группы, выход К-го регистра первой группы (Кт) подключен к вторьм входам всех блоков элементов И К-й строки наддиагональной матрицы опроса, к входам вычитаемого (K-I)-ro вычитателя первой группы, к входу второго слагаемого К-го сумматора первой группы,..первому информационному входу (М-К)-й схемы сравнения группы и является К-м информационньм выходом первой группы устройства, выход первого регистра первой группы подключен к вторым входам всех блоков элементов И первой строки наддиагональной матрицы опроса, к входам уменьшаемого всех вычитателей первой гр уппы и является первым информацион15

25

30 ньм выходом первой группы устройства, выход К-го вычитателя первой группы

() подключен к информационному входу К-го регистра второй группы, выход которого подключен к входу второ35 го слагаемого (М-К)-го сумматора второй группы и к второму информационному входу К-й схемы сравнения группы, выход признак равенства которой является К-м информационным выходом вто 0 рой группы, выходы блоков элементов И К-го столбца (Ki l) наддиагональной матрицы опроса подключены к соответствующим входам К-го блока элементов ИЛИ второй группы, выход которого под45 к.шочен к входу уменьшаемого (М-К)-го вычитателя второй группы, выход блока

элементов И первого столбца подключен к входу уменьшаемого (М-1)-го вычитателя второй группы, выход К-го сзгмма- тора второй группы () подключен к входу вычитаемого К-го вычитателя второй группы, выход которого является К-м информационным выходом третьей группы устройства, выход (M-l)-ro блока элементов ИЛИ первой группы

подключен к входу вычитаемого первого вычитателя второй группы, информационный выход которого является пер713255008

вым информационным выходом третьейройства, первый выход переключателя группы устройства, выход второго раз-подключен к счетному входу второго ряда первого счетчика подключен ксчетчика, информационный выход кото- входам опроса всех схем сравнениярого является информационным выходом группы и является выходом признака устрой ства. окончания второго этапа работы устСоставитель А.Мишин Редактор В.Петраш Техред И.Попович КорректорН.Король

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

БНИИПИ Государственного комитета СССР

по делам изобретений и открытий П3035, Москва, Ж-35, Раушская наб., д.4/5

Производственно-полиграфическое предприятие,г.Ужгород,ул.Проектная,4

Изобретение относится к вычислительной технике, может быть использовано для исследования сетевых графов без контуров и петель и позволяет находить IИнимaльнyro и максимальную массу дуг, соединенньвс с вершинами графа, определять критические пути в .графе и свободные резервы времени исполнения вершин графа, что расширяет; функциональные возможности устройства. С этой целью устройство для исследования путей в графе содержит над- диагональную матрицу моделей дуг, содержащую в своих узлах регистры, на которых записана масса дуг графа, и блоки элементов И. Критический путь определяется путем анализа на схемах сравнения группы экстремальных кодов массы дуг. Результаты анализа запоминаются на регистрах одной.из двух групп, входящих в состав устройства. Затем при помощи двух групп сумматоров и двух групп вычитателей определяются максимальные и минимальные массы дуг всех вершин графа, а также резерв свободного времени исполнения вершин графа. 1 ил. С/) С