Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,749

PARALLEL ALGORITHM OF SEARCH ACCESSIBILITY IN THE GRAPH

Knyazkova A.V. 1 Volchenskaya T.V. 1 Knyazkov V.S. 1
1 Vyatka State University
There are problems in the field of graph and network tasks in which the concept of reachability is used. The operation of reachability matrix construction is the key point in the problem of graph splitting up into maximal coherent subgraphs in a shortest construction problem and in a number of other problems. Many ways of performance graph models for computer processing are considered. The concept of reachability and its performance through multiple-valued displays and transitive short circuits is presented. The parallel algorithm is used to create the reachability matrix to be considered. The main characteristic is that construction of a reachability matrix operation can be executed in parallel for all graph nodes. The quantity of iterations depends on its structure, not the graph dimensions. It depends on simple circuits and paths. In real network models where the degree of connectivity in the graph is large, the speed of the construction of a matrix will increase.
graph
graph model
accessibility in the graph
a matrix of the accessibility
parallel algorithm
1. Volchenskaya T.V. Tezisy dokladov II Mezhdunarodnoinauchno-teshnicheskoikonferencii «Novyeinformacionnieteshnologiisistemy» (Theses of reports of II international scientifically – technical conference «New information technologies and systems»), October 1996, Penza, pp. 95–96.
2. Volchenskaya T.V., Knyazkov V.S. The device for definition of number of tops of subgraphs the graph. The copyright certificate no. 1341649 G06F15/20, the bulletin of inventions no. 36, 1987.
3. Volchenskaya T.V., Knyazkov V.S. The device for research of subsets the graph. The copyright certificate no. 1410051, G06F15/31, the bulletin of inventions no. 26, 1988.
4. Volchenskaya T.V., Knyazkov V.S. The device for research the graph. The copyright certificate no. 1363237, G06F15/20, the bulletin of inventions no. 48, 1987.
5. Volchenskaya T.V., Knyazkov V.S. Multipurpose cell of homogeneous structure. The patent no. 1663609 , G06F7/00, 1993.
6. Volchenskaya T.V., Knyazkov V.S. The specialized processors for the decision of problems on graphs. Journal of Advanced science no. 3, 2013, pp. 73–82.
7. Kristofides N. Graph theory. The analytical approach. Moscow, 1978.
8. Knyaz’kov V.S., Volchenskaya T.V. Maximally Parallel Algorithms for Raster Image Processing by Cellular VLSI Processors // Pattern Recognition and Image Analysis, Vol.6, no. 2, 1996, pp. 403–404.
9. Knyaz’kov V.S. An Assotiative Cellular VLSI Processor for Paralled Processing by Raster Image: the concept and Applied Computations // Pattern Recognition and Image Analysis, Vol. 6, no. 2, 1996, pp. 401–402.

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

Задач, в которых используется понятие достижимости, довольно много. Вот одна из них. Граф может быть моделью какой-то организации или социальной сети, в которой люди представлены вершинами, а дуги интерпретируют каналы связи. При рассмотрении такой модели можно поставить вопрос, может ли информация от одного лица хi быть передана другому лицу хj, т.е. существует ли путь, идущий от вершины хi к вершине хj. Если такой путь существует, то говорят, что вершина хj достижима из вершины хi. Можно интересоваться достижимостью вершины хj из вершины хi только на таких путях, длины которых не превосходят заданной величины или длина которых меньше наибольшего числа вершин в графе и т.п. задачи.

Характерной особенностью таких задач является большая размерность, что обусловливает необходимость конструирования более скоростных алгоритмов. Плодотворной основой для построения таких алгоритмов могут служить их сетевые и графовые формализации [1, 7].

Программные реализации указанных задач весьма универсальны и просто программируемы при небольших размерностях графа. Однако при значительном увеличении количества узлов или дуг графа время программного решения при последовательном исполнении инструкций становится практически неприемлемым. Аппаратные реализации хотя и обеспечивают необходимую скорость за счет параллельной обработки информации, но не обладают достаточной алгоритмической гибкостью, в силу этого – их адаптация к изменениям логики вычислений не всегда возможна [2, 3, 4, 5]. Решением данной проблемы является использование таких вычислительных алгоритмов, которые бы совмещали скорость аппаратных вычислений с легкостью программной модификации в параллельных алгоритмах [6, 8, 9].

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

Допустим, что мы имеем граф, структура которого описана матрицей смежности (рис. 1) размерностью n×n, (где n – число вершин графа), однозначно представляющая его структуру:

pic_17.wmf

а б

Рис. 1. Пример 1: а ‒ граф; б ‒ матрица смежности графа

A = {aij}, i, j = 1, 2, ..., n, а каждый элемент матрицы определяется следующим образом:

aij = 1, если существует дуга из вершины xi в вершину xj,

aij = 0, если нет дуги из вершины xi в вершину xj.

Достижимость в графе описывается матрицей достижимости

R = [rij], i, j = 1, 2, ... n, где n – число вершин графа, а каждый элемент определяется следующим образом:

rij = 1, если вершина хj достижима из хi,

rij = 0, в противном случае.

Множество вершин R(xi) графа G, достижимых из заданной вершины xi, состоит из таких элементов xj, для которых (i, j)-й элемент в матрице достижимостей равен 1. Очевидно, что все диагональные элементы в матрице R равны 1, поскольку каждая вершина достижима из себя самой путeм длины 0. Поскольку прямое отображение 1-го порядка Г+1 (xi) является множеством таких вершин xj, которые достижимы из xi с использованием путей длины 1, то множество Г+(Г+1(xi)) = Г+2 (xi) состоит из вершин, достижимых из xi с использованием путей длины 2. Аналогично Г+p(xi) является множеством вершин, которые достижимы из xi с помощью путей длины p.

Так как любая вершина графа, которая достижима из xi, должна быть достижима с использованием пути (или путей) длины 0 или 1, или 2, ..., или p, то множество вершин, достижимых для вершины xi, можно представить в виде

R(xi) = {xi } ∪ Г+1 (xi) ∪ Г+2(xi) ∪ ... ∪ Г+p(xi).

Как видим, множество достижимых вершин R(xi) представляет собой прямое транзитивное замыкание вершины xi, т.е. R(xi) = T+(xi). Следовательно, для построения матрицы достижимости находим достижимые множества R(xi) для всех вершин xi ∈ X. Полагая rij = 1, если xj ∈ R(xi) и rij = 0 в противном случае.

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

1. Так как каждая вершина достижима сама для себя, то в матрице достижимости R1 на главной диагонали должны стоять 1. Единицы можно предварительно занести на главную диагональ матрицы смежности, для того чтобы в п. 2 алгоритма использовать общую формулу преобразования.

Матрица R1

Матрица R2

x1

x 2

x 3

x 4

x 5

x 6

x 7

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 1

1

1

0

1

1

0

0

x 1

1

1

0

1

1

0

0

x 2

0

1

0

1

1

0

0

x 2

0

1

0

1

1

0

0

x 3

0

0

1

1

1

0

0

x 3

0

0

1

1

1

0

0

x 4

0

0

0

1

1

0

0

x 4

0

0

0

1

1

0

0

x 5

0

0

0

0

1

0

0

x 5

0

0

0

0

1

0

0

x 6

0

0

1

1

1

1

1

x 6

0

0

1

1

1

1

1

x 7

0

0

1

1

1

1

1

x 7

0

0

1

1

1

1

1

2. По матрице смежности для каждой вершины графа xi находим строку в матрице R1 как результат логического сложения тех (j-х) строк матрицы смежности, для которых xij = 1

knayz01.wmf

Например, для вершины x1 в матрице смежности элементы a11, a12 и a15 равны 1, следовательно, строка в матрице R1 для вершины x1 будет получена как результат логического сложения элементов соответствующих позиций первой, второй и пятой строк матрицы смежности.

Операция построения матрицы достижимостей R1 может быть выполнена параллельно для всех вершин графа.

3. По матрице R1 для каждой вершины графа находим матрицу следующего уровня R2 по аналогичным формулам:

knayz02.wmf

4. Далее процедура построения матрицы достижимости Rk по матрице достижимости предыдущего уровня Rk–1 повторяется до тех пор, пока Rk не будет равной Rk–1.

В нашем примере на рис. 1 построение матрицы достижимости произошло за одну итерацию, так как R2 = R1.

Количество итераций зависит от структуры графа, а именно от длины простых цепей и контуров. Рассмотрим второй пример, показанный на рис. 2. Как видим из примера, матрица достижимости строится за три итерации, то есть только R4 = R3. Таким образом, количество итераций равно длине самой длинной простой цепи и не зависит от количества вершин графа. В реальных сетевых моделях, где велика степень связности графа, скорость построения матрицы еще более возрастет.

pic_18.wmf

а б

Рис. 2. Пример 2: а ‒ граф; б ‒ матрица смежности графа

Матрица R1

Матрица R2

x1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 1

1

1

1

1

1

0

0

0

x 1

1

1

1

1

1

1

0

1

x 2

0

1

1

1

0

0

0

0

x 2

0

1

1

1

1

1

0

0

x 3

0

0

1

1

1

0

0

0

x 3

0

0

1

1

1

1

0

1

x 4

0

0

0

1

1

1

0

0

x 4

0

0

0

1

1

1

0

1

x 5

0

0

0

0

1

1

0

1

x 5

0

0

0

0

1

1

0

1

x 6

0

0

0

0

0

1

0

1

x 6

0

0

0

0

0

1

0

1

x 7

0

0

0

0

0

1

1

1

x 7

0

0

0

0

0

1

1

1

x 8

0

0

0

1

1

1

0

1

x 8

0

0

0

1

1

1

0

1

Матрица R3

Матрица R4

x1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 1

1

1

1

1

1

1

0

1

x 1

1

1

1

1

1

1

0

1

x 2

0

1

1

1

1

1

0

1

x 2

0

1

1

1

1

1

0

1

x 3

0

0

1

1

1

1

0

1

x 3

0

0

1

1

1

1

0

1

x 4

0

0

0

1

1

1

0

1

x 4

0

0

0

1

1

1

0

1

x 5

0

0

0

0

1

1

0

1

x 5

0

0

0

0

1

1

0

1

x 6

0

0

0

0

0

1

0

1

x 6

0

0

0

0

0

1

0

1

x 7

0

0

0

0

0

1

1

1

x 7

0

0

0

0

0

1

1

1

x 8

0

0

0

1

1

1

0

1

x 8

0

0

0

1

1

1

0

1

По сравнению с последовательным алгоритмом, в котором время выполнения зависит от размерности графа, предлагаемое решение позволяет значительно увеличить быстродействие.

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

Рецензенты:

Шатров А.В., д.ф.-м.н., профессор, зав. кафедрой «Математическое моделирование в экономике» Вятского государственного университета, г. Киров;

Бутаев М.М., д.т.н., профессор, ученый секретарь ОАО «НПП Рубин», г. Пенза.

Работа поступила в редакцию 26.02.2014.