Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 12
Текст из файла (страница 12)
УЗЛЫ! ДЛЯ КОТОРЫХ МАЕК(1) а 0 4 ИГНОРИРУЮТСЯ ВХОДНЫЕ ПАРАМЕТРЫЯООТ вЂ” УЗЕЛ4 ОПРЕДЕЛЯЮЩИЙ КОМПОНЕНТУ. (ХА01, АОТМСТ) - МАССИВЫ ДЛЯ СТРУКТУРЫ СМЕЖНОСТИ МА5К вЂ” ЗАДАЕТ ПОДГРАФ, ВЫХОДНЫЕ ПАРАМЕТРЫ— оео - массив содейжащий степени узлов В КОМПОНЕНТЕ. СС512Е- ЧИСЛО УЗЛОВ КОМПОНЕНТЫ! ЭАДАИНОЙ МАБК И йООТ . РАБОЧИИ ПАРАМЕТРЬБ - ВЕКТОР ДЛЯ ХРАНЕНИЯ УЗЛОВ КОМПОНЕНТЫ, УРОВЕНЬ ЗА УРОВНЕМ ° 1МТЕСЕЯ АОТМСТ(1), ОЕО(1), ЬБ(!), МАБК(1) 1МТЕОЕЯ ХАО1(1), СС512Е, 1, 10ЕО, 1, 15ТОР, 25ТЯТ, 1 ЬВЕ01М, ЕЧСЕМО, 1Ю512Е, МВЯ, МООЕ, АООТ ПРИСВОЕНИЕ НАЧАЛЬНЫХ ЗНАЧЕНИЙ ... МАССИВ ХАО2 ИСПОЛЬЗУЕТСЯ ДЛЯ УКАЗАНИЯ КАКИЕ УЗЛЫ ОБРАБОТАНЫ НА ДАННЫЙ МОМЕНТ. (2)Е61М - УКАЗАТЕЛЬ НАЧАЛА ТЕКУЩЕГО УРОВНЯ .
ЕУ)ДМО УКАЗЫВАЕТ ЮНЕЦ ЭТОГО УРОВНЯ . НАЙТИ СТЕПЕНИ УЗЛОВ ТЕ)(У(ЦЕГО УРОВНЯ И ПОСТРОИТЬ СЛЕДУЮЩИЙ УРОВЕНЬ. ОО 400 1 !.ВЕ61М, ЬЧ(.ЕМО МООЕ ЬБ(1) 15ТЯТ -ХА01(МООЕ) 25ТОР 1АВБ(ХАО1(МОРЕ 4 !)) - ! 1ОЕО 0 1Р ( 15ТОР .ЬТ 1БТЯТ ) 00 ТО 300 00 200 1 ЗБТЯТ, 15ТОР МВЯ АОЗМСТ(1) 1Р ( МА5К(нйй) 50 О ) 60 ТО 200 1))ЕС 10ЕО + 1 1Р ( ХАО.)(МВй) .ЬТ 0 ) 60 ТО 200 еа !"л. 4. Ленточные и профильные методы хлп>(мвя> - -капе(мвя) ССБ1ХЕ ССБ1йй ч ! !.Б(ССБ12Е) ° Л!ВЯ СОМТ1МОЕ ОЕС(МОЬЕ) 10ЕС СОМТ1МПЕ 800 В>)0 400 О С 3- числить ширину такущеГО уРОВня если ОнА йнулевля, постоонть следующий уровень.
Ч812Е ССБ>2Е - ЬЧЬХЧО Ь ( !.ЧБ12Е .ОТ. 0 ) Ой ТО >00 ВООСТАНОВИТЬ ПРАВИЛЬНЫЕ ЭНАКИ В ХА01 ° ВОЭВРАТ. 00 500 1 1, С0812Е мбое - ЬБ(!> ХЛО1(МООЕ> = -ХЛО>(МООЕ) ОРМТ1МСЕ ЯЕТПЯМ ВМО 800 е м,,- и 'ь.-ее .~ г. (ТСМ (Вече!Бе Сп()(111 — МСКее) Эта подпрограмма применяет описанный в разделе 4.3.1 алгоритм цСМ к связной компоненте подграфа. Она оперирует с той связной компонентой, которая задана входными параметрами БООТ, МАЭК, ХАРЯ и АРЯЬ)С'!'.
Начальным узлом является значение переменной КОРТ. Так как алгоритму необходимы степени узлов данной компоненты, то первым шагом будет вычисление этих степеней посредством обращения к подпрограмме РЕО>БЕЕ. Узлы определяются и упорядочиваются уровень за уровнем; каждый новый уровень нумеруется в результате очередного выполнения цикла РО 600 1 =.... Цикл РО 200 1 =... находит ненумерованных соседей данного узла; в остальной части цикла РО 600 пРоизводится сортировка методом пузырька для упоря- вень.
Когда узел заносится в 1,$, изменяется знак у соответствую>него значвния в массиве ХАМ, чтобы этот узел не запоминался в 18 вторично. (Аналогичную функцию в подпрограмме КООТ).3 выполнял массив МАЯК; здесь, однако, МАЕК должен сохранять свое входное содержимое, чтобы правильно были определены степени узлов.) Переменная ССЗ)ЕЕ имеет смысл числа узлов, находяшихся в 1.8 в данный момент. После того как найдены все узлы и вычислены их степени, узлы, записанные в 1.6, используются для восстановления первоначальных знаков элементов ХАРЯ (цикл РО 500 1 = ...).
ПСН НУМЕРУЕТ СВЯЗНУЮ КОМПОНЕНТУ ! ЗАДАННУЮ НАЗК Н ВОСТ» ИСПОЛЬЗУЯ АЛГОРИТМ ЯСН . ПРОЦЕСС НУМЕРАЦИИ ДОЛЖЕЙ ИАЧИИАТЬСЯ С УЗЛА ЯООТ ° (ХАЬХ, АОЛЧСТ) - МАССИВЫ ДЛЯ СТРУКТУРЫ СМЕЖНОСТИ ГРАФА, Выхпйные пАРАнетяы- РЕЕМ - СОДЕРЖИТ ЙСМ УПОРЯ))ОЧЕНИЕ . СС$12Е ЧИСЛО УЗЛОВ „СВЯЗНСИ КОМПОНЕНТЫ а ПРОНУМЕРОВАННОЙ ПОДПЙОГРАННОЯ ЙСН $ РАБОЧИЙ ПАРАМЕТР Оео - няссив для хРАнения степеней Узлов подГРНРА, ЗАДАННОГО ПОСРЕДСТВОМ НАЗК И ЙООТ, ЗОВЙООТ1НЕ ВСН ( ВООТ, ХАОХ, АОХНСТ, МАЗИ» 1 РЕЯМ, СС$12Е, ВЕО ) С Са ° ° ° ° ее ° а ° е ° е ° а ° ° ° а ° а»а ° ° ° ° ° ° е ° ° ° ° ° $$$$ ° е ° е ° е ° е ° ° ° ° ° ° ° ° ° ° ее С С 1НТЕОЕВ АОЛЧСТ(1), ЭЕО()), МАЕК()), РЕВИ(1) )ИТЕОЕВ ХАЛХ(!), СС$12$, РНВВ, 1.
Х, ХЗТОР, ) ХБТВТ, К, Ь, ЬВЕО1Н, ЬНВВ, 1.РЕЙН, 1 ЬУЬЕНО, НВВ, Ж)ВЕ, ВООЧ' Се ° а»ее»а ° ° ° ° е ° е ° ° ° е ° ° ° ° ° е ° аее ° ° ее» ° ° ° а ° а ° ° ааааа ° ° ° аеаеее С С с няйти стзпенн узлов в конпоненте „ С ЗАДАННОИ МАЗИ И ЙООТ * С сАьь оеояее ( Воот, ХАВх, Аохнст, НАБЕ. Оео, СС$12Е, РЕЕМ ) МАЗЕ(ВОСТ) О 1Р ( СС$12Е .ЬЕ.
1 ) ЙЕТОВН ЬУЬЕНО О 1)ЧВВ 1 С С С С 100 ЬВЕО)М И ЬУЬЕИО УКАЗЫВАЮГ НАЧАЛО И КЧ)НЕЦ ТЕЙТ)ЦЕГО уРовня . ЬВЕО)Н - ЬУЬЕНО + ) ЬУЬЕНО ЬНВВ ВО БОО 1 ЬВЕ01Н, ЬУЬЕ)Ю $ ° а ° ° а ° аааа$ ° $ ° ° ее ° ° ° ° ° ° ° ° ° ° а ° ° ° ° ° ° ° $ ° ° ° ° ° ° ° ° ° ° ° ° ° а»а ° а ° ° ° ° ° ° ° ° $$$$$ ° ° ° ° $$$$$$$$ ° ° ° ° ° ° ° $ ° $ ° $ ° ° $ ° ° ° ° ° ° $ ° $$ ° ° Ч ° ° $ ° $ ° а ° ° ° ° $$$ Се»ее»а ° ° ВСМ ... ОБРАТНОЕ УЛОРЯДОЧЕНИЕ КАТХИЛЯА МАККИ ее ° Се» ° а*а» ° ° ° а ° а ° ° еаааеаеаа ° $$$$$$$$$$ ° ° ° $$$$$$$$$$ ° ° ° $$$$$$$ ° $$ Се.ее»»ее ° ° е ° а»а ° е ° ° ° ее» ° ° ° ° ° $$ ° ° $$ ° ° е ° ° $$$$$$$ ° ° ° ° ° $$$$$$$$$ ° С С С С С С ВХОДНЫЕ ПАРАМЕТРЫ С ВОСТ УЗЕЛ» ОПРЕДЕЛЯЮЖий СВЯЗНУЮ КОНПОНЕНТУ ' С НАчАЛьНЫЯ для Йсн - уПОРЙЛОЧЕНИЯ ° С С С С С ИЗНЕНЯЕИЬ)й ПАРАМЕТРС ИАЗЕ -'РАССИАТРИВАются лишь узлы котояын С СООТВЕТСТВУЮТ НЕНУЛЕВЫЕ ВХОДНЫЕ ЗНАЧЕНИЯ С В НАЗК .
ДЛЯ УЗЛОВ а ПРОНУНЕРЧШАННЫХ ЙСН з С В НАЗК ЗАДАЕТУЯ О С С С С С С С С С С С С ИСПОЛЬЗУЕМЫЕ ПОДПРОГРАННЫ С ПЕОВЕЕ. С Се»ее ° а ° а ° ° ° е ° а ° а ° а ° ° ее ° ° ° ° а ° аееее ° а ° ° ° ° ° ° ° ° ееае ° ае ° ° ° ° ее»ее Йб >'л 4 Ленточнме и нРофальнне методы ДПЙ КАЖДОГО УЗЛА В ТЕКУЩЕМ УРОВНЕ йООЕ РЕМЕ ( 1 ) ЗЗТЙТ ХАОЗ(НООЕ) ззтоР КА01(нове+) > С С С С НАЙТИ НЕНУМЕРОВАННЫХ СОСЕДЕЙ, РНВЙ Н ЬНВЙ УКАЗЫВАЮТ ПЕРВОГО И ПОСЛЕДНЕГО НЗ НЕНУМЕРОВАННЫХ СОСЕДЕЙ ТЕКУЩЕГО УЗЛА ИЗ РЕЕМ ° РНВЙ ЬНВЙ + > 00 200 1 ззтвт, >ВТОР НВЙ АОЛЧСТ(1) 1Р ( МАЗЕ(НВЙ) ЕО.
0 ) 60 ТО 200 ЬНВЙ >2ЧВЙ + 1 МАЗЕ(НЕЙ) 0 РЕЙН(ЬНВЙ) НВЙ СОНТ1>Е)Е 1Р ( Ртчвв .Ое. Енвв > со то воо 200 С С С С упопядочнть соседей данного узлА по ВозРАстанню СТЕПЕНЕЙ, СОРТИРОВКА МЕТОДОМ ПУЗЫРЬКА . К РНВЙ ь к к ° к + НВЙ РЕЙН(К) 1Р ( Ь .ЬК РНВЙ ) 60 ТО ЗОО ЬРЕЙМ РЕЙН(( ) 1Р ( ОЕС().РЕВМ) .ЕЕ. ОЕС(НВЙ) ) РЕЙН(1+1> ЬРЕЙМ 1 Ь 1 со то чоо РЕЙН(1+1) НВЙ ТР ( к ьт. ЬНВЙ > со то зоо СОНТ1НОЕ 1Р (ЬНВЙ .СТ. ЬИ.Е(ЧО) СО ТО 100 60 ТО ЗОО С С С С ПОЛУЧЕНО УПОРЯДОЧЕНИЕ КАТХИЛЛА -НАККИ НИЖЕ ОНО БУДЕТ ОБРАЩЕНО ° К ССЗ12Е/2 1. ССЗ12Е ПО ТОО 1 1, К ЬРЕЙМ н РЕЙН(Ь) РЕЕМ(Ь> ° РЕЙН(1) РЕЕМ(1) ЬРЕЙМ ).Ь-1 СОНТТНОЕ Йет((вн Ено 700 дочения этих соседей по возрастанию степеней.
Новое упорядочение записывается в массив РЕЧ(М, как объяснено в $3.3. Финальный цикл (РО 700 1=...) обрашает упорядочение; в результате будет получено не стандартное, а обратное упорядочение Катхнлла †Мак, й 4.Д Профильные улорлоочения В! Отметим, что, так же как и в подпрограмме ГРООТ).В, переменной МАЕК(!) прн записи узла ! присваивается нулевое значение. Однако в отличие от йООТ!.8 подпрограмма КСМ не восстанавливает исходное состояние массива МАЯК. Элементы МАЯК, соответствующие узлам пронумерованной связной компоненты, остаются равными нулю на выходе из подпрограммы.
ОЕХКСМ(ОЕ)ч)ега! (ХСМ) Эта подпрограмма находит МСМ вЂ упорядочен произвольного несвязного графа. Она просматривает граф н обращается к подпрограмме )ХСМ, чтобы пронумеровать каждую связную компоненту. Входными данными подпрограммы являются число узлов (или уравнений) ХЕЯ(()В н граф, заданный парой массивов (ХАШ, АИ!ЧС1). ОЕ)ч(КСМ обращается к подпрограммам с* ° оеиасм ... Сеоатное упорядочение катхилла — макки ° ° ° ° ° С* ° ° ° ~ ° *~ ПРОИЗВОЛЬНОГО ГРАФА *ь"' ~''''~'~''"'~*'"'''* с ~ ° **~ * ИСПОЛЬЗУЕМЫЕ ПОДПРОГРАММЫ РМЛООТ ЯСМ с ЗСВКОСТ1МЕ СЕМЕСМ ( МЕ!)МЗ, ХАОЗ, АОЗМСУ, РЕЕМ, МАКК, Х!.3 ] с ° ° ° ° с 1МТЕСЕК АОЗМСУ(!), МАЕК(!), РЕКМ(1), Х1.З(1) 1МТЕСЕК ХАОЗ(!), ССЗ1ХЕ, 1, МЕ!)МЗ.
МЕЧЕ, мсм. аоот с с с с с с с с с с с с с с с с с с оенесм находит оыатное упорядочение катхилла-макки ПРОИЗВОЛЬНОГО ГРАФА, ДЛЯ КАЖДОЙ СВЯЗНОЙ КОМПОНЕНТЫ ГРАФА УПОРЯДОЧЕНИЕ ДОСТИГАЕТСЯ ВЫЗОВОМ ЯСМ . ВХОДНЫЕ ЛАРАМЕТРЫМЕЧМБ - ЧИСЛО УРАВНЕНИЙ. (ХАОЗ, АОЗМСУ) - МАССИВЫ ДЛЯ СТРУКТУРЫ СМЕЖНОСТИ ГРАФА МАТРИЦЫ ВЫХОДНОЙ ПАРАМЕТРРекм - Вектор, содеежаи(нй асм-упорядочение. РАВОчие ЛАРАметры мАяк " ВектОР дпя маркиРСВки переменных ПРОНУМЕРОВАННЫХ В ПРОЦЕССЕ УПОРЯЗ(ОЧЕННЯ ° начальные значения компонент Равны 1; онн заменяются на о ПРН нунеоацнн Узлов. „ хьз - индексный некто~ для стРуктуоы уеовйей, храня(кайся в неиспользуемых на данный момент позициях вектооа перестановки Рккм . 62 Гл.
4. Ленточные о Профильные метооы С ° Э ° ° Ф Э ° ° ЭЭ ° ° ° ° ° Ф ° ФФФ ° Ф ° ° ФФ ° 00 100 1 1, МЕ()МБ МАЕК(1) 1 СОЧТ1МОГ МОМ 1 00 200 1 1, МЕОНБ 100 для к~ждой иййкнеовлнной связной коипонейтй. 1Р (МАБК(1) .ЕО. О) 00 ТО 200 ЯООТ 1 Внйчйле нАЙти псеВДОпеРнеэеРлйный узел йоот. СТРУКТУРА УРОВНЕЙФ НАЙДЕИНАЯ РййООТФ хРАнится нйчинАВ 0 Реям(ном)* зйтей плоисходйт ОБРАщение к йсм . Поот - нечАльныЙ УЗЕЛ ПРИ УПОРЯДОЧЕНИИ КОМПОНЕНТ.
САП. РМЯООТ ( ВООТ, ХАМ!, АОЗМСТ. МАЯК, 1 МЬУЬ, ХЬБ, РЕЯМ(МОМ) ) САЬЬ ЯСМ ( ЯООТ. ХАП), Ав)МСТ, МАЕК, ! РЕЯМ(!ЧОЛ), ССБ1ХЕ, ХЬБ ) МОМ МОЧ э ССБ!2Е 1Р (МОЛ .ОТ. НЕОНЕ) ЯЕТОВМ 200 СОМТ1МОЕ ВЕТОЯМ ЕМО С С С С С С Р)()БООТ и (хСМ, которые используют массивы МАЯК и Х(.Я как рабочие.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
