Параллельное программирование: Учебное пособие, страница 29

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


Рисунок 2.10.

Таблица 1.  Список вершин с множествами дуг (выходных/входных).

Индекс

имени i

Имя

вершины

Ярус

j

Новый

индекс k

T(1)

T(2)

T(3)

T(4)

T(5)

T(6)

1

a

{b, e, c} = {2, 3, 5}

{Æ}

1

1

2

b

{f, s} = {6, 8}

{a} = {1}

2

3

3

c

{f} = {6}

{a} = {1}

2

4

4

d

{e, g} = {5, 7}

{Æ}

1

2

5

e

{h} = {9}

{a, d} = {1, 4}

2

5

6

f

{v} = {11}

{b, c} = {2, 3}

3

6

7

g

{v} = {11}

{d, h} = {4, 9}

5

9

8

s

{h, v} = {9, 11}

{b} = {2}

3

7

9

h

{g, w} = {7, 10}

{e, s} = {5,8}

4

8

10

w

{v} = {11}

{h} = {9}

5

10

11

v

{Æ}

{f, g, s, w} = {6, 7, 8, 10}

6

11

Для лексикографического упорядочения орграфа удобно использовать колонку  таблицы 1. В таблицу введены два дополнительных столбца: один предназначен для закрепления за вершиной  порядкового номера яруса j , а второй – для записи нового упорядочивающего индекса .

Алгоритм, показанный на рисунке 2.11, размещает вершины по ярусам и присваивает им новые индексы. В результате множество вершин будет упорядочено так, что между его элементами будет иметь место отношение порядка: , если , где . В операторах схемы рис. 2.11 использованы такие выражения и обозначения:                                                      Рисунок 2.11.

*число вершин орграфа;

исходный индекс, ярус и новый индекс вершины орграфа;

множество вершин от которых входят дуги;

*рабочее множество вершин, исключаемых из .

Матрица смежности для графа, представленного рисунком 2.10, до и после лексикографического упорядочения приведена на рисунке 2.12.


Рисунок 2.12.

Смысл лексикографического упорядочения удобно описать, используя визуальное или табличное представление орграфа следующим образом:

По именам {a, b, c,...} или по их первоначальным индексам {1, 2, 3,...} в списке (колонки Т(2), Т(1) в таблице 1) последовательно просматриваются отрицательные полустепени вершин  (колонка Т(4)). Вершины, удовлетворяющие условиям  (новый индекс имени еще не присвоен) и Æ  (нет входящих дуг), помещаются в рабочее множество М с присвоением им одного и того же номера яруса ( ) и очередного индекса вершины () . В конце очередного цикла индексная переменная  принимает значение , которое запускает процесс исключения из всех множеств  тех вершин, которые были занесены в рабочее множество (М) . При этом исключении появятся новые вершины, у которых отсутствуют входящие дуги. Вершины, которым ранее уже был присвоен новый индекс и для них  , в очередном цикле пропускаются, а вершины с отрицательной полустепенью равной нулю, помещаются в рабочее множество вершин нового яруса. Циклы просмотра продолжают до тех пор, пока всем вершинам не присвоят новые индексы.

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