Алгоритм Пурдома: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 25: Строка 25:
  
 
=== Описание схемы реализации последовательного алгоритма ===
 
=== Описание схемы реализации последовательного алгоритма ===
 +
 +
'''1 этап''' (''вычисление компонент сильной связности'') может быть реализован [[Алгоритм Тарьяна поиска компонент сильной связности|алгоритмом Тарьяна]]<ref name=DFS>Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.</ref>, находящим компоненты сильной связности в ходе [[Поиск в глубину (DFS)|поиска в глубину]].
 +
 +
'''2 этап''' (''топологическая сортировка'') может быть реализован алгоритмом Кана<ref>Kahn, A B. “Topological Sorting of Large Networks.” Communications of the ACM 5, no. 11 (November 1962): 558–62. doi:10.1145/368996.369025.</ref> либо последовательным применением [[Поиск в глубину (DFS)|поиска в глубину]]<ref>Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.</ref> для нумерации вершин в предпорядке.
 +
 +
'''3 этап''' (''транзитивное замыкание'' <math>\tilde G</math>) выполняется следующим алгоритмом:
 +
 +
'''Входные данные''':
 +
    ациклический граф 'G'' с вершинами 'V'', пронумерованными в топологическом порядке, и рёбрами ''E''.
 +
'''Выходные данные''':
 +
    для каждой вершины ''v'' ∈ ''V'' – набор вершин ''T''(''v''),
 +
        так что транзитивное замыкание ''G'' состоит из рёбер (''v'', ''w''), ''v'' ∈ ''V'', ''w'' ∈ ''T''(''v'').
 +
   
 +
'''for each''' ''v'' ∈ ''V'' '''do''' ''T''(''v'') := { ''v'' }
 +
'''for''' ''v'' ∈ ''V'' '''in reverse order''':
 +
    '''for each''' (''v'', ''w'') ∈ ''E'' '''do''' ''T''(''v'') := ''T''(''v'') ∪ ''T''(''w'')
 +
 +
'''4 этап''' (''транзитивное замыкание'' <math>G</math>) либо выполняется следующим алгоритмом:
 +
 +
'''Входные данные'''
 +
    граф ''G'' с вершинами ''V'';
 +
    компоненты сильной связности ''SCC''(''v'') графа ''G'';
 +
    граф <math>\tilde G</math> с вершинами <math>\tilde V</math>;
 +
    транзитивное замыкание <math>\tilde T</math> графа <math>\tilde G</math>.
 +
'''Выходные данные''':
 +
    для каждой вершины ''v'' ∈ ''V'' – набор вершин ''T''(''v''),
 +
        так что транзитивное замыкание ''G'' состоит из рёбер (''v'', ''w''), ''v'' ∈ ''V'', ''w'' ∈ ''T''(''v'').
 +
       
 +
'''for each''' ''v'' ∈ ''V'' '''do''' ''T''(''v'') := { ''v'' }
 +
'''for each''' ''v'' ∈ <math>\tilde V</math>:
 +
    '''for each''' ''w'' ∈ <math>\tilde T(v)</math>:
 +
        ''T''(''v'') := ''T''(''v'') ∪ ''SCC''(''w'')
 +
    '''for each''' ''x'' ∈ ''SCC''(''v''):
 +
        ''T''(''x'') := ''T''(''v'')    ''/* присваивание по ссылке */''
 +
 +
либо транзитивное замыкание может строиться по упакованным данным <math>\tilde T(v)</math> одной из следующих функций:
 +
 +
'''Входные данные'''
 +
    граф ''G'' с вершинами ''V'';
 +
    компоненты сильной связности ''SCC''(''v'') графа ''G'';
 +
    отображение ''R''(''v'') вершин графа ''G'' на вершины графа <math>\tilde G</math>;
 +
    граф <math>\tilde G</math> с вершинами <math>\tilde V</math>;
 +
    транзитивное замыкание <math>\tilde T</math> графа <math>\tilde G</math>.
 +
   
 +
'''function''' transitive_closure(''v''):
 +
    ''T'' := { ''v'' }
 +
    '''for each''' ''w'' ∈ <math>\tilde T(R(v))</math>:
 +
        ''T'' := ''T'' ∪ ''SCC''(''w'')
 +
    '''return''' ''T''
 +
   
 +
'''function''' is_in_transitive_closure(''v'', ''w''):
 +
    '''return''' ''R''(''w'') ∈ <math>\tilde T(R(v))</math>
 +
 
=== Последовательная сложность алгоритма ===
 
=== Последовательная сложность алгоритма ===
 
=== Информационный граф ===
 
=== Информационный граф ===

Версия 12:31, 14 июня 2015

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма

Алгоритм Пурдома[1] находит транзитивное замыкание ориентированного графа за время [math]O(\mu n)[/math], где [math]\mu \le m[/math] – число рёбер, соединяющих компоненты сильной связности этого графа.

1.2 Математическое описание

Алгоритм основан на следующих свойствах:

  1. Если вершины [math]v[/math] и [math]w[/math] принадлежат одной компоненте сильной связности графа [math]G[/math], то его транзитивное замыкание [math]G^+[/math] содержит рёбра [math](v, w)[/math] и [math](w, v)[/math].
  2. Если вершины [math]x[/math] и [math]y[/math] принадлежат одной компоненте сильной связности графа [math]G[/math], а вершины [math]z[/math] и [math]t[/math] – другой, то рёбра [math](x, z)[/math], [math](x, t)[/math], [math](y, z)[/math], [math](y, t)[/math] принадлежат или не принадлежат транзитивному замыканию [math]G^+[/math] одновременно.

Таким образом, поиск транзитивного замыкания графа [math]G[/math] сводится к поиску транзитивного замыкания ациклического графа [math]\tilde G[/math], полученного из [math]G[/math] схлопыванием каждой компоненты сильной связности в одну вершину. Транзитивное замыкание ациклического графа вычисляется с использованием топологической сортировки вершин графа.

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

Вычисления производятся в четыре этапа:

  1. Найти компоненты сильной связности исходного графа, заменить каждую компоненту на одну вершину и удалить образовавшиеся рёбра-петли.
  2. Выполнить топологическую сортировку полученного ациклического графа [math]\tilde G[/math].
  3. Вычислить транзитивное замыкание графа [math]\tilde G[/math], двигаясь от вершин с бо́льшими номерами к меньшим.
  4. По найденному транзитивному замыканию [math]\tilde G[/math] восстановить транзитивное замыкание исходного графа.

Последний этап не является обязательным, если рассматривать транзитивное замыкание [math]\tilde G[/math] как «упакованное» транзитивное замыкание [math]G[/math].

1.5 Описание схемы реализации последовательного алгоритма

1 этап (вычисление компонент сильной связности) может быть реализован алгоритмом Тарьяна[2], находящим компоненты сильной связности в ходе поиска в глубину.

2 этап (топологическая сортировка) может быть реализован алгоритмом Кана[3] либо последовательным применением поиска в глубину[4] для нумерации вершин в предпорядке.

3 этап (транзитивное замыкание [math]\tilde G[/math]) выполняется следующим алгоритмом:

Входные данные:
    ациклический граф 'G с вершинами 'V, пронумерованными в топологическом порядке, и рёбрами E.
Выходные данные:
    для каждой вершины vV – набор вершин T(v),
        так что транзитивное замыкание G состоит из рёбер (v, w), vV, wT(v).
    
for each vV do T(v) := { v }
for vV in reverse order:
    for each (v, w) ∈ E do T(v) := T(v) ∪ T(w)

4 этап (транзитивное замыкание [math]G[/math]) либо выполняется следующим алгоритмом:

Входные данные
    граф G с вершинами V;
    компоненты сильной связности SCC(v) графа G;
    граф [math]\tilde G[/math] с вершинами [math]\tilde V[/math];
    транзитивное замыкание [math]\tilde T[/math] графа [math]\tilde G[/math].
Выходные данные:
    для каждой вершины vV – набор вершин T(v),
        так что транзитивное замыкание G состоит из рёбер (v, w), vV, wT(v).
        
for each vV do T(v) := { v }
for each v[math]\tilde V[/math]:
    for each w[math]\tilde T(v)[/math]:
        T(v) := T(v) ∪ SCC(w)
    for each xSCC(v):
        T(x) := T(v)    /* присваивание по ссылке */

либо транзитивное замыкание может строиться по упакованным данным [math]\tilde T(v)[/math] одной из следующих функций:

Входные данные
    граф G с вершинами V;
    компоненты сильной связности SCC(v) графа G;
    отображение R(v) вершин графа G на вершины графа [math]\tilde G[/math];
    граф [math]\tilde G[/math] с вершинами [math]\tilde V[/math];
    транзитивное замыкание [math]\tilde T[/math] графа [math]\tilde G[/math].
    
function transitive_closure(v):
    T := { v }
    for each w[math]\tilde T(R(v))[/math]:
        T := TSCC(w)
    return T
    
function is_in_transitive_closure(v, w):
    return R(w) ∈ [math]\tilde T(R(v))[/math]

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Описание ресурса параллелизма алгоритма

1.9 Описание входных и выходных данных

1.10 Свойства алгоритма

2 Программная реализация алгоритмов

2.1 Особенности реализации последовательного алгоритма

2.2 Описание локальности данных и вычислений

2.3 Возможные способы и особенности реализации параллельного алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

  1. Purdom, Paul, Jr. “A Transitive Closure Algorithm.” Bit 10, no. 1 (March 1970): 76–94. doi:10.1007/BF01940892.
  2. Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.
  3. Kahn, A B. “Topological Sorting of Large Networks.” Communications of the ACM 5, no. 11 (November 1962): 558–62. doi:10.1145/368996.369025.
  4. Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.