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

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

1

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

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

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

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

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

Перед пуском устройства в матрицу 1 заносят информацию о топологии графа, при этом триггеры 5 устанавливаются в О, а в счетчики 3 заносят коды, дополняющие веса дуг до полной емкости счетчиков 3. Обнуляют регистры 10 и счетчики 8, 9 и 14.

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

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

в прямом графе соответствуют величинам максимальных путей в конечную вершину графа. Далее величины времен выполнения вершин прямого и инвертированного графов сравнивают на схемах

11сравнения, при этом номер схемы

11 сравнения, которая выдала единичный сигнал на свой выход признака равенства , соответствует номеру вершины, через которую проходит максимальный путь в графе. 1 ил.

ваются счетчиками 3 моделей 2 первой строки матри1№1 1 и всеми счетчиками 8. Отсчитав число импульсов, равное весу дуги, счетчик 3 переполняется и устанавливает в единичное состояние триггер 5. Когда все триггеры 5 моделей 2 дуг всего столбца матрицы 1 перебрасываются в единичное состояние, на выходе соответствующего элемента И 6 появляется единичный потенциал, поступающий на управляющие входы счетчиков 3 моделей 2 одноименной строки матрицы 1, и те начинают счет импульсов. Кроме того, на выходе .соответствующего элемента НЕ 12 появляется нулевой потенциал, и соответствующий счетчик 8 прекращает счет импульсов. Вычислительный процесс продолжается до те пор, пока на всех

входах элемента И 13 не установятся единичные потенциалы. В этот момент единичный потенциал с выхода элемента И 13 поступает на вход останова генератора 15 и прекращает работу устройства. Число импульсов, зафиксированное в счетчиках 8, соответствует, наиболее ранним временам выполнения вершин.

Кроме того, импульс с выхода элемента И 13 поступает на вход счетчика 14, KoTopbiii увеличивает свое соV.

держимое на единицу и выдает единичный потенциад на первый разряд информационного выхода. Появдение сигнала на импудьсных входах признаков записи регистров 10 обусдовливает запись на ней содержимого счетчиков 8, Кроме того, единичный потенциал с первого разряда информационного выхода счетчика 14 открывает элементы И 7.

При наличии в графе дуги с нулевым весом в соответствующий счетчик 3 заносят число импульсов, равное его емкости, но триггер 5 устанавливается в состояние О. Тогда первый же импульс сбрасывает счетчик 3 в О, что обусловливает появление единичного сигнала на выходе элемента НЕ А и переход триггера 5 в состояние 1.

На втором этапе вновь приводят устройство в исходное Состояние, но регистры 10 не обнуляются, а в матрицу 1 заносят информацию о топологии инвертированного графа, т.е. данные

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

10

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

20

Устройство для исследования путей в графе, содержащее наддиагональную матрицу из (Р-1) X (Р-1) моделей дуг, где Р - количество вершин в графе, матрицы исходного графа, но транспор- -jb группы элементов И, группу эле- тированные относительно неглавной ментов НЕ, две группы счетчиков,

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

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

30

ход признака переполнения которого подключен к первому входу установки в 1 триггера той же модели дуги наддиагональной матрицы, выход триг.записывается, так как единичный по- гера М-й Модели дуги К-й строки над- тенциал с первого разряда информаци- диагональной матрицы (М 2, ..., онного счетчика 14 через импульсные Р-1; К 1, ...,Р-1) подключен к входы признаков записи регистров 10 К-му входу (М-1)-го элемента И первой не проходит. Другая особенность работы устройства на втором этапе состоит в том, что при появлении на выходе элемента И 6 единичного потенциа40

группы, выход которого подключен к

ла, обусловливающего запрещение счета импульсов соответствующим счетчивыходу М-го элемента НЕ группы и первому входу (М-1)-го элемента И второй группы, информационный выход К-го счетчика первой группы ( Р-1) подключен к первому информационному вхо- ком 8, на выходе одноименного элемен- ду К-й схемы сравнения группы, о т - та И 7 появляется единичный потенци- личающееся тем, что, с це- ал, разрешающий счет импульсов соот- лью расширения функциональной возмож- ветствующим счетчиком 9 до останова ности устройства за счет определения генератора 15 после того, как на вы- вершин максимального пути в графе, ходе элемента И 13 появится единичный 50 него введены группа регистров, элепотенциал. В результате по окончании второго этапа работы устройства в счетчиках 9 будут зафиксированы наиболее поздние времена выполнения вершин прямого (исследуемого) графа.

Появление единичного потенциала на выходе элемента И 13 приводит к увеличению содержимое счетчика 14,

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

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

20

-jb

30

ход признака переполнения которого подключен к первому входу установки в 1 триггера той же модели дуги наддиагональной матрицы, выход триггера М-й Модели дуги К-й строки над- диагональной матрицы (М 2, ..., Р-1; К 1, ...,Р-1) подключен к К-му входу (М-1)-го элемента И первой

гера М-й Модели дуги К-й строки на диагональной матрицы (М 2, ..., Р-1; К 1, ...,Р-1) подключен к К-му входу (М-1)-го элемента И перв

40

группы, выход которого подключен к

выходу М-го элемента НЕ группы и пе вому входу (М-1)-го элемента И втор группы, информационный выход К-го счетчика первой группы ( Р-1) под ключен к первому информационному вх ду К-й схемы сравнения группы, о т личающееся тем, что, с це лью расширения функциональной возмо ности устройства за счет определен вершин максимального пути в графе, 50 него введены группа регистров, эл

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

матрицы, вход разрешения пуска устройства подключен к входу разрешения счета счетчиков всех моделей дуг первой строки наддиагональной матрицы, выход триггера первой модели дуги первой строки наддиагональной матрицы подключен к входу первого элемента НЕ группы, первому входу элемента И и к входам разрешения счета всех счетчиков моделей дуг второй строки наддиагональной матрицы, выход К-го элемента И первой группы (К/Р-2, Р-1) подключен к входам разрешения счета всех счетчиков моделей дуг (К+2)-й строки наддиагональной матрицы и к (К+1)-му входу элемента И, выход (Р-2)-го элемента И подключен к (Р-1) му входу элемента И, выход которого подключен к счетному входу счетчика и к входу останова генератора импульсов, выход которого подключен к счетным входам счетчиков всех моделей дуг наддиагональной матрицы и к счет

5

0

ным входам всех счетчиков первой и второй групп, выход К-го элемента НЕ группы подключен к входу блокировки счета К-го счетчика второй группы, информационный выход которого подключен к информационному входу К-го регистра группы, первый разряд информационного выхода счетчика подключен к вторым входам всех элементов И второй группы и к входам признака записи всех регистров группы, выход К-го регистра группы подключен к второму информационному входу К-й схемы сравнения группы, выход признака равенства которой является выходом признака принадлежности (К+О-й вершины максимальному пути в графе устройства, второй разряд информационного выхода счетчика подключен к входам всех схем сравнения группы, выход К-го элемента И второй группы (К4Р-1) подключен к входу разрешения счета К-го счетчика первой группы.

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