Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 29
Текст из файла (страница 29)
ОО 200 1 1, МЕОМБ 1Р (МО1Я.ЧЕ(1) ЕЕ 0) ОО ТО 200 КООТ 1 САЕ1. РМЕЧЕБ ( КООТ. ХАОЗ, АОЛЧСУ, МООЕЧЕ. М1М.. Х1.5, ЕБ ) 1ХЕ5 ХЕБ(МЕЧЕ) ЕЕАР ЕБ(1ХЕБ) СА(.1. К()ТЯЕЕ ( (.ЕАР, ХАО), АО)МСУ, РЕКИ, МВ1.КБ, ХВЕХ, МООЕЧЕ. ХЕБ. 1.5 ) 200 1 СОМТ1МОЕ КЕТОКМ ЕМО структуру уровней с корнем в псевдопериферийном узле, а вектор )ч)ОР1'(ГЕ хранит для каждого узла соответствующий ему номер уровня в структуре уровней. Работа подпрограммы начинается с присвоения начальных значений вектору )ч)ОР1Л"1, и переменной )ч)В1КЬ. Затем она исследует граф, пока не найдет еще не пронумерованный узел. Отметим, что для нумерованных узлов в векторе )ч)ОР1((1 устанавливаются нулевые значения.
Найденный узел 1 вместе с массивом )ч)ОР11(1. определяет связный подграф исходного графа, Далее происходит обращение к подпрограммам Р)ч)1Ч1Ь й ЩТКЕЕ, которые упорядочивают узлы этого подграфа. Подпрограмма заканчивает работу, когда все компо. ненты графа обработаны. Р)ч)еч(ЕЬ 1Р11)() 1е)теЕ Ягпс1пге) Подпрограмма Р)ч)ЕЪ).Ь строит корневую структуру уровней для компоненты, заданной посредством )ч)ОР).'1(1; в качестве корня берется псевдопериферийный узел, Кроме того, запоминаются номера уровней, соответствующие узлам в структуре уровней. Связная компонента задается входными параметрами КООТ, ХАР), АР))ч)СУ и )ч)ОР1ЛЧ.. Ртч!.'Л.Ь прежде всего обращается к подпрограмме РЫКООТ, которая вычисляет требуемую кор.
невую структуру уровнеи, помещая ее в 1Ы1Л(е, ХЕЗ, 18). Затем циклом по структуре уровней (РО 200 ЕЪ'Е = .. ) определяются номера уровней, соответствующие узлам; они записываются в )ч)ОР1'ч'1.. 9 б 8. Алгоритм вм !негения древовидного разбиения 191 ! Нечез .. построение структуры уровней * СТРОИТ КОРНЕВУЮ СТРУКТУРУ УРОВНЕЙ ДЛЯ МАРКИРОВАННОГО СВЯЗНОГО ПОДГРАФА) КОРЕНЬ СТРУКТУРЫ БЕРЕТСЯ В ПСЕВДОПЕРИФЕРИЯНОМ УЗЛЕ. ЗАПОМИНАЮТСЯ НОМЕРА УРОВНЕЙ .
ВХОДНЫЕ ПАРАМЕТРЫ " (хлпз, Аозмст) - структуРА сМежНОСти ° ВЫХОДНЫЕ ПАРАМЕТРЫ МЕЧЕ - ЧИСЛО УРОВНЕЙ В ПОСТРОЕННОЙ СТРУКТУРЕ. (Х!.5, !5) - ПОСТРОЕННАЯ СТРУКТУРА УРОВНЕЙ. ИЗМЕНЯЕМЫЕ ПАРАМЕТРЫКООТ - НА„ВХОДЕ ВМЕСТЕ С НООЕЧЕ ЗАДАЕТ КОМПОНЕНТУ ЧЕЙ ПСЕВДОПЕРИФЕРИЙНЫй УЗЕЛ НУЖНО НАЙТИ нА Выходе - это НАйденн(ый узел. МООЕЧ!. - НА ВХОДЕ ЗАДАЕТ ПОДГРА'Р.
НА ВЫХОДЕ СОДЕРЖИТ НОМЕРА УРОВНЕит СООТВЕТСТВУЮЩИЕ УЗЛАМ . ИСПОЛЬЗУЕМЫЕ ПОДПРОГРАММЫРМЯООТ . С ° ° ° С ЗОВКООТ1МЕ 1 С Се ° ° е в ° С 1НТЕСЕК 1МТЕОЕК 1 С Сне * С в ° е е ° ° е ° $$ ее е ° евве ° ° вв САЕ1. РМКООТ ( КООТ, ХАОЗ, АОЗМСУ, МООЕЧЕ, 1 МЕЧЕ, ХЕЗ, Еа ) ОО 200 ЕЧ!. 1, МЕЧЕ ЕВЕСТМ ХЕЗ(ЕЧЕ) ЕЧЕЕМО ХЕ5(ЕЧЕ + 1) - 1 ОО 100 3 ЕВЕ01М, ЕЧЕЕМО МООЕ Ез(З) МООЕЧЕ(МОСЕ) ЕЧЕ сомт1)х)е СОМТЗМОЕ КЕТОКМ ЕМО 100 200 ЩТКЕЕ (Ке(!Пе() (;)по(!еп1 Т)1ЕЕ) Это та самая подпрограмма, которая реализует описанный в разделе б.3.1 алгоритм вычисления фактор-дерева. Для хранения подмножеств узлов используется стек; его организацию с с с с С с с с с с С с с с с с с с с с с с РМЕЧЕ5 ( КООТ, ХАОЗ, АОЗМСУ, МОО!.ЧЕ, МЕЧЕ, ХЕ5, Ез ) АОЗМСУ(1), Ез(1), МООЕЧЕ(!), Х!.5(1) ХАОЗ(1), 3, !.ВЕ61М, ЕЧЕ, ЕЧ!.ЕМО, МЕЧЕ, МОВЕ, КООТ 192 Гв В Методы фактор-деревьев мы и рас мотрим прежде, чем входить в детали подпрограммы.
Для каждого подмножества, помещенного в стек, нужно запомнить число узлов в нем н соответствующий ему номер уровня, В массиве под названием 5ТАСК мы храним в последовательных позициях узлы подмножества; в двух следующих позициях хранятся число узлов и номер уровня. Используется еще переменная ТОРЗТК, указывающая число занятых на данный ггонсльное состояние Юеяеторо зтАск еяоЮ еетсео умоЮ отАСК Ряс. 6.ЗЛ. Организация стека я подпрогРамме НЯТИЕЕ. момент позиций стека. Рис.
6.3.7 иллюстрирует организацию вектора БТАСК. Чтобы поместить подмножество 5 уровня е в стен, мы просто переписываем узлы 5 в вектор ЯТАСК, начиная с позиции ТОРБТК+!. Затем мы записываем число ~5( и номер уровня е' и, наконец, изменяем значение переменной ТОРБТК. С другой стороны, чтобы вытолкнуть подмножество узлов нз магазина, мы вначале определяем по значению переменной БТАСК (ТОРБТК вЂ” !) число узлов этого подмножествз, после чего можно выбрать из ЬТАСК само подмножество, начиная с позиции ТОРБТК вЂ” )Б~ — Е Наконец, снова изменяется значение ТОРБТК, чтобы отразить новый статус стека. Теперь мы рассмотрим детали подпрограммы РОТОЗЕЕ. Она оперирует со связным подграфом, заданным посредством (.ЕАР, ХАШ, АР)Р)СУ и ЫОО(Аг(.. Неявно предполагается, что для этого подграфа сформирована структура уровней, причем массив Р)00(Аг( содержит номера уровней его узлов, а переменная ЕЕАР задает листовой узел структуры уровней.
Говорят, что узел х является листом структуры уровней Ы' = (Еа, У-ь ° Ь), если х ~ (.~ и АсЦ (х) П 1.,+1 = ке, б блз Алгоритм вычисления древовидного разбиения !9$ с* ° СОРТ51 КОПИЯ ЦЕЛОГО ВЕКТОРА ° ч чч С ° ° ° ° * ° ° ° ° С С С С С С С С С С С С С ПЕРЕПИСЫВАЕТ М ЦЕЛЫХ ЧИСЕЛ ИЗ ВЕКТОРА А В ВЕКТОР В ( т(Ассивы коротких целых чисел ) . Входнь(е ЛАРАт)етРЫ- М - ДЛИНА ВЕКТОРА .
А - ЦЕЛЫЙ ВЕКТОР. ВмходнОЙ ЛАРАт(етР. В - ВЫХОДНОЙ ЦЕЛЫЙ ВЕКТОР ° ° ° ° ° С зовкопт1ме соРт51 ( м, А, В ) С С' 1МТЕОЕК А(1), В(1) 1МТЕОЕК 1, М 1Р ( м ье. о ) кетикм ОО 1ОО 1 1, М В(1) А(1) 100 СОМТ1МПЕ кетокм ЕМО Помимо ЬТАСК подпрограмма использует еще один рабочий вектор АШЬ. В нем хранится пересечение смежного множества текущего блока с нижним уровнем, которое является потенциальным подмножеством следуюшего блока. Работа подпрограммы начинается с присвоения начальных значений вектору ЬТАСК, указателю ТОРЬТК и переменной ТОР(.Н(..
Локальная переменная ТОР(.Н(. хранит номер уровня верхнего подмножества магазина. Затем определяется листовой блок: это делается посредством вызова подпрограммы г(ЧАРА)х(, которой передается узел (.ЕАР. (Листовой блок— это подмножество У такое, что Ус: с„и Аб) (У)П (,,1 = 8 ) Найденный блок нумеруется как следующий блок фактор-дерева (оператор с меткой 300). Мы спускаемся теперь на следующий уровень (1ЕНЕЕ= = ЕЕНЕ(. — 1 и последуюшие операторы). Построение очередного потенциального блока начинается с пересечения нового уровня и смежного множества предыдушего блока.
Если подмножество узлов, находящееся на вершине стека, принадлежит тому же уровню, оно выталкивается из магазина и включается в потенциальный блок. Затем происходит обрашение к подпро- Г96 Гв д Методы 4~автор-деревьев грамме Г)ч)ЗРАМ (оператор с меткой 400), которая находит оболочку ') этого объединения. Если оболочка не имеет ненумерованных соседей на верхнем уровне, то она становится очередным нумерованным блоком. В противном случае она кладется иа стек и определяется листовой блок, который и будет следующим нумерованным блоком.
Подпрограмма проходит все уровни, пока не дойдет до первого. К этому времени должны быть пронумерованы все узлы компоненты, и работа подпрограммы заканчивается. РМЗРАИ (Р(Мб 5РАМ) Эта подпрограмма используется подпрограммой РОТОЗЕЕ н имеет несколько функций, одна из которых состоит в вычислении оболочки множества. Пусть Ы' = ()е, У.ь ..., У.Д вЂ” заданная структура уровней, а 5 — подмножество уровня ю'.
Подпрограмма определяет оболочку '5 в подграфе 6(1.,) и находит пересечение смежного множества для 5 с уровнем 1., ь Если же оболочка 5 имеет ненумерованных соседей в уровне 1.,+ь то программа находит ненумерованный листовой узел; в этом случае оболочка 5 может остаться лишь частично сформированной. Входной информацией для подпрограммы являются: структура графа, хранимая парой массивов (ХЛШ, ЛР,)(ч)СУ), структура уровней, неявно хранимая вектором МОР(.Ч(., и подмножество ((ч)ЗРАЫ, ЬЕТ) уровня (.ЕЧЕ1 в структуре уровней. На выходе содержимое вектора ЗЕТ расширится, включив в себя оболочку заданного множества.
Значение переменной МЬРА(ч) будет увеличено до числа элементов оболочки, После присвоения начальных значений подпрограмма проходит циклом по узлам частичной оболочки. Переменная ВЕТРТК указывает текущий узел рассматриваемой оболочки. Затем выполняется цикл РО 500 .) = ..., в котором инспектируются номера уровней соседей. В зависимости от номера уровня сосед либо игнорируется„ либо включается в оболочку, либо включается в смежное множество. Наконец, есть еще одна возт можностгп сосед принадлежит более высокому уровню. В этом случае прослеживается путь по ненумерованным узлам вверх по структуре уровней, пока не будет найден листовой узел.
После восстановления первоначальных значений в массиве МОР(.Ч1 для узлов частично сформированного смежного множества (цикл РО 900 1 = ...) происходит выход из подпрограммы. При нормальном же выходе из ГМЗРАЫ полностью сформированные оболочка и смежное множество будут находиться соответственно в ()ч)ВРАТ, БЕТ) и (ДАШЬ, АШЗ). Переменная ЕЕАГ при этом имеет нулевое значение, ') То есть множество У = ЯРАМ(3), а точнее у 01е ь — Лрим.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
