Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 11
Текст из файла (страница 11)
Шаг 1 (инициализация). Выбрать в Х произвольный узел г. Шаг 2 (настроение структуры уровней). Построкть структуру уровней с корнем в г: ,2'(г) (г(,р(г), 1.|(г)...,, 1.цо(г)», тз Га 4, Ленте«ние и орофильние метода Шаг д (стягивание последнего уровня). Выбрать в 2'нн(г)' узел х с минимальной степенью. Шаг 4 (яостроение структуры уровней).
а) Построить структуру уровней с корнем в х: 2'(х)= (Е о(х), Т.1(х), ..., 1.и„>(х)). б) Если 1(х))1(г), положить г«-х и перейти к шагу 3. Шаг 5 (финиш). Узел х является псевдопериферийным. В следующем разделе описаны и обсуждаются подпрограммы РИКООТ и КООТ(.Я, реализующие этот алгоритм. На рис. 4.3.9 приведен пример, демонстрирующий работу алгоритма Узлы уровня 1 всех структур уровней помечены числом ~'. 4.8.8. Подпрограммы поиска начального узла В этом разделе описаны и обсуждаются две подпрограммы, реализующие алгоритм предыдущего раздела.
В этих подпрограммах и подпрограммах разделов 4.3.4 и 4.4.2 имеется несколько общих входных параметров, которые были описаны в 5 3.3. Прежде чем продолжить чтение, читателю, возможно, будет полезно вспомнить содержание этого параграфа. КООТЬЯ (КООТео (,ече! Я(гпс(пге) Назначение этой подпрограммы — генерировать структуру уровней связной компоненты, задаваемой входными параметрами ГРООТ, МАЯК, ХАШ и А1)оИС'г', как описано в 5 3.3 На выходе из подпрограммы будет получена структура уровней с корнем в узле КООТ; она задается парой массивов (Х(.Я, ЕЯ), причем узлы уровня Й суть значения переменных ).Я(1), где Х(.Я(й)(1( Х(Я(я+1).
Число уровней указывает переменная Я.Ч1. Отметим, что, так как в Фортране не допускаются нулевые индексы, у нас не может быть «нулевого уровня»; поэтому здесь й соответствует С»-~ в структуре уровней раздела 4.3.2. По той же причине И1Ч(. на единицу больше, чем эксцентриситет узла 11ООТ. Подпрограмма определяет уровень за уровнем; новый уровень получается в результате каждого выполнения цикла 1)О 400 .... После определения каждого очередного узла (в результате выполнения цикла 110 300 ...) его номер помещается в массив ).Я, а соответствуюшее ему значение в массиве МАЯК заменяется на нуль, чтобы этот узел не попал в 1,Я вторично. После того как структура уровней построена, значения массива МАЯК, соответствующие узлам структуры, переопределяются на 1 (что выполняется циклом 110 500 ...).
РН)1ООТ (Р)Нд КООТ) Эта подпрограмма определяет псевдопериферийный узел связной компоненты данного графа при помоши алгоритма, 74 Гю. б. Ленточные и лрофнеьные методы СА!.1. ОЕОВА!(5) 1Р (1ЕВЕ.Е!).О) 60 ТО 100 САСЬ 5АЧЕ(З, 5) 5ТОР !00 СОМТ1М()Е СОМТ1МОЕ ЕОО С С С С ЬЧ512Е СС512Е - ЬЧЬЕ!ЧО 1Р (ьчзгге ,Ст. о ) оо то гоо 500 «) Ев. уэюы, лов!вимм воомбюмоебулмо ивиуивбив вивчвиив бмюовибю ЫАВК. В вриеииююв - Мойен. - прим. оврвб.
описанного в разделе 4.3.2. Подпрограмма оперирует со связ- ной компонентой, задаваемой входными параметрами ((ООТ, МАЯК, ХАРЯ и АРЛ! (С'1', как описано в З З.З. с ° ° ° " ° * ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° Се ° ° ° ° ° ° ° ° е е ° ° ° ° е ° ° ° ее ° ° ° е е ° ° ° Сееее е ° Се С ° е ° ° е ° ° ее ° ° е ° е ° ° ° ° е ° ° ° е ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° е С С С С С С С С С С С С 00 300 3 15ТХТ, !5ТОР МВН " АО)МСЪ(1) 1Р (ЫА5К(МВЕ) ЕО О) СО ТО ЗОО СС512Е СС512Е + ! !.5(СС512Е) МВЕ ЧАЗК(МВХ) 0 СОНТ1МОЕ ВЫЧИСЛИТЬ ШИРИНУ ТЕКУЩЕГО УРОВНЯ.
ЕСЛИ ОНА НЕ РАВНА НУЛЮь ПОСТРОИТЬ СЛЕДУЮЩИЙ УРОВЕЙЬ. В МАЕК ВОССТАНОВИТЬ 1 ДЛЯ УЗЛОВ СТРУКТУРЫ УРОВНЕЙ Хсз(МЕЧ! е!) ЬЧЬЕ(ЧО + 1 00 500 1 1, СС512Е МООЕ !.5(1) ИА5К(МООЕ) 1 СОМТ1МПЕ ввтохМ ЕМО РМЕООТ ПОИСК ПСЕВДОПЕРИФЕРИйНОГО УЗЛА ° ° ° ° ° ° ° Рмпоот Резлизует модифицировннный ВАРиннт схемы гиввсА, ПУЛА И СТСКЬ(ЕВЕРА ОТЫСКАНИЯ ПСЕВДСПЕРИФЕРИЙНЫХ УЗЛОВ ОНА ОПРЕДЕЛЯЕТ ТАКОЙ УЗЕЛ ДЛЯ ПОДГРАФА е ЗАДАВАЕМОГО МАВК И ПОСТ.
ВХОДНЫЕ ПАРАМЕТРЫ(ХАОЗ, АО)МСТ) МАССИВЫ ДПЯ СТРУКТУРЫ СМЕЖНОСТИ ГРАРА МАКК - ЗАДАЕТ ПОДГРАФ* УЗЛЫ ь ДЛЯ КОТОРЫХ ЫАЗК(1) = О ь ИГНОРИРУЮТСЯ. ИЗМЕНЯЕМЫЙ ПАРАМЕТР- еоот - нА Входе ( Вместе 0 МАЕК) ОПРЕДЕЛяят ИСПОЛЬЗУЕМЫЕ ПОДПРОГРАММЫ ЕООТ).$ . Се ° ° ° ее« ° ° еее ° ° ° ееее ° еее ° ° ° еее ° ° ее«е ° ее«в ° ° ° еее ° ееее ° ° е ° ° ° е ° ° э С С Сэ ° ° ° ° ° ° ° е ° е ° е е 1 1 С Севе ° ° С С С С С С С 100 200 300 С С С 400 С С С С С С С С С С д 4.8.
Профильные уоорядочения 7$ конпоненту, для которой ииьетсн ПСЕВДОПЕРИФЕРИЙНЫЙ УЗЕЛ НА ВЫХОДŠ— ЗТО НАЙДЕННЫЙ УЗЕЛ ° ВЫХОДНЫЕ ПАРАЫЕТРЫМ.УЬ ЧИСЛО УРОВНЕЙ В СТРУКТУРЕ УРОВНЕЙ С КОРНЕН В УЗЛЕ йООТ. (ХЕЗ,ЕЗ) - ПАРА МАССИВОВ ДЛЯ ХРАНЕНИЯ НАЙДЕННОЙ СТРУКТУРЫ УРОВНЕЙ БПВЕООТ1НЕ «Т(ЕООТ ( ВСОТ, ХАВ), АВ)НЕТ, МАЕК. Н(АП., ХЬБ, 1.$ ) 1НТЕСЕЕ АВ)НОТ(1). ЕЗ(1), МАЕК(1), Х1.$(1) 1НТЕСЕЕ ХАО)(1), СС$12Е, 1, )БТЛТ, К, КБТОР, КБТЕТ, М1НОЕС. НАВОЗ, НОЕС, ФПЛ6., НОВЕ, М)НЬИ., « ° ° ° ° ° ° ° ееее\ее ° ° ее« ° ° ° ° ° ° ° э ° ее« ° ° ° ее ° ° ° ° ° ° ° ° ° * ° ° ° «ее««4« ОПРЕДЕЛИТЬ СТРУКТУРУ УРОВНЕЙ С КОРНЕМ В йООТ САЫ.
ЕООТЬБ ( ПООТ, ХАО), АВ)ЫСТ, МАЕК, М.УЬ, ХЬЗ, ЕБ ) СС$12Е ХЗ.Б(НЬй.+1) - 1 1Р ( НЬЖ..Е9. 1 .ОВ. ВНЕ..ЕО. СС$12Е ) ВЕТСЕН ВЫБРАТЬ П ПОСЛЕДНЕМ УРОВНЕ УЗЕЛ 0 НИИИМ СТЕПЕНЬЮ е )ЗТЕТ ХЬБ(йИЧ.) МТНОЕС СС$12Е ЕООТ ЕЗ()БТЕТ) 1Р ( СС$12Е .Е(). )БТЕТ ) 60 ТО 400 ВО 200 1 1$ТПТ, СС$12Е НОВЕ ЕБ(1 > МЬЕС 0 КБТЕТ - ХАО)(МЮЕ> КБТОР ХАО)(НОВЕ+1) - ! ОО 200 К КБТЕТ. КБТОР КАПОВ АВ)НОТ(К) 1Р ( МАЕК(НАВОЗ) .СТ. 0 ) НОЕС )ВЕС + 1 СОНТ1НСЕ 1Р ( НВЕС .СЕ. М1НОЕС ) СО ТО 300 ВОЮТ НОВЕ М1НОЕС НОЕС СОНТ1 ПСЕ Н ПОСТРОИТЬ СТРУКТУРУ УРОВНЕН С КОРНЕМ В ЭТО(4 УЗЛЕ САЕ(.
ЛООП,Б ( ЕООТ, ХАВ), АО)НСТ, МАЕК, М)Н$ЛЧ,. )П.Б, 3.$) 1Р (НСМ.И..З.Е. М.УЬ) ВЕТСЕН МИ М)НЬИ 1Р ( %ЛЯ. ЕТ СС$12Е ) СО тО :00 ВГП>ЕН 78 Гл. 4. Ленточнае и нрарильнае метооа Первое обращение к подпрограмме КООТ(.Я соответствует шагу 2 алгоритма. Если компонента состоит из единственного узла или является цепью, для которой ЕООТ вЂ” одна из концевых точек, то КООТ вЂ” периферийный узел, а ЕЯ содержит соответствующую корневую структуру уровней; поэтому работа программы прекращается.
В противном случае в последнем уровне разыскивается узел с минимальной степенью (шаг 3 алгоритма; в подпрограмме этому соответствует цикл ОО 300...). Строится новая структура уровней с корнем в этом узле (обращение с меткой 400 к подпрограмме ЯООТ).Я), после чего выполняется тест на окончание работы (шаг 46) алгоритма. Если тест не проходит, управление передается оператору с меткой 100, и процедура повторяется.
На выходе КООТ хранит номер псевдопериферийного узла, а пара массивов (Х1Я, ЕЯ)— соответствующую корневую структуру уровней. 4.3,4. Подпрограммы обратного алгоритма Катхилла — Макки Здесь будут описаны три подпрограммы — ОЕОйЕЕ, ЕСМ и ОЕНРСМ, составляющие вместе с подпрограммами предыдущего раздела полную реализацию описанного в равд. 4.3.1 алгоритма КСМ. Роль входных параметров ЕООТ, МАЯК, ХАОС, А03НСУ и РЕКМ та же, что и в $3.3.
Отношения управления между подпрограммами указаны на рисунке. Т)ЕО)сЕЕ Эта подпрограмма вычисляет степени узлов связной,компоненты графа. Подпрограмма оперирует с той связной компонентой, которая задана посредством входных параметров 11ООТ, МАЯК, ХА0е и АОЗИСУ, Начиная с первого уровня (состоящего из единственного узла цООТ), вычисляются степени узлов; для каждого уровня определение степеней осуществляет цикл ОО 400 1 = .... При обследовании соседей для узлов данного уровня (цикл РО 200 3 = ..) те из них, которые еще не были записаны в массив 1.Я, теперь помещаются туда, тем самым генерируется новый уро- с ° С~ ° ° ° ° ° ° СЕОЕЕЕ ...
СТЕПЕНИ В МАРКИРОВАННОЙ !) КОМПОНЕНТЕ ° ~ С ~ 1 ° 1 ° ° ° 4 С БОВ)ВСТ1МЕ ОЕОйЕЕ ( ЯООТ, ХАО3, А01МСТ, МАЯК, 1 ОЕО, СС5125, 1.5 ) С ° * ° ° ° ° ° ° ° ° ~ ~ ° ° ° ° ° ~ ~ ° ° ~4 ° ~ ° ° ° ~ ° ° ° ° ° ° ° ° ° ° ° 4 С С С С С 1.5(1) ЯООТ ХАШ(йООТ) -ХАО1(АООТ) ЬЧЬЕМО 0 СС512Е 1 С С С С ЕВЕ61М ЕЧЬЕМО + ЕЧЗ.Е(40 СС512Е 100 С С С С С С С С С С С С С С С С С С С С С ,С С ПОДПРОГРАМНА ВЫЧИСЛЯЕТ СТЕПЕНИ УЗЛОВ В СВЯЗНОЙ КОМПОНЕНТЕ ЗАДАВАЕМОЙ МАЕК Н ЯООТ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
