Найти пути длины = 4, начиная с матрицы смежности ориентированного графа, учитывая только различные ребра?

Question

Учитывая модель EREW-PRAM, которая позволяет мне использовать произвольное число параллельно работающих процессоров, не конфликтуя ни с ними, ни в режиме чтения, ни в режиме записи, мне нужно найти число путей длины 4, учитывая, что у меня естьматрица A смежности входных узлов-узлов, представляющая ориентированный граф, и мне нужно исключить пути, которые не используют четкие ребра (например: (a, b), (b, a), (a, b), (b,а) не является допустимым путем).

У меня есть функция, которая использует n ^ 3 процессоров и вычисляет умножение матриц двух заданных матриц за время O (logn):

mult-matrix(A, A, n) => B-> дает мне пути длины 2.

mult-matrix(B, B, n) => C -> дает мне пути длины 4, но я думаю, что он рассматривает пути, которые пересекают одни и те же ребра.

Я попытался вычесть 1 из элементов C, у которых узел u связывается с узлом v в обоих направлениях, но я не уверен, что это работает.

Как я мог решить проблему, учитываячто мне просто нужно исключить некоторые пути из результирующей матрицы C?

Любое рабочее решение приветствуется, учитывая, что число процессоров ограничено до n ^ 3, а время должно быть O (logn) в худшем случае,Упражнения должны решаться с использованием псевдо-паскальского языка, но при наличии рабочего решения я смогу написать псевдокод самостоятельно.

Answer 1

Я думаю, что нашел решение в https://www.perlmonks.org/?node_id=522270

Учитывая входную матрицу A, я могу вычислить матрицу смежности для путей длиной 2, 3 и 4 с помощью предоставленной функции.

• A2 - матрица смежности, полученная умножением A * A и содержащая пути длиной 2
• A3, полученная умножением A2 * A и содержащая пути длины 3
• A4.получается умножением A3 * A и содержит пути длиной 4

. Чтобы исключить повторяющиеся ребра, я должен вычислить матрицу C, полученную путем поэлементного вычитания среди вычисленных матриц.

C[i,j] = A4[i,j] - A3[i,j] - A2[i,j] - A[i,j]

C содержит конечный результат.

Следующий псевдокод решает проблему с EREW-PRAM с использованием O (n ^3) процессоры и во времени O (logn).

procedure paths_length_4(A, n) // Work = O(n^3 logn)
begin
    A2 := mult_matrix(A, A, n) // T=O(logn), P=O(n^3)
    A3 := mult_matrix(A2, A, n) // T=O(logn), P=O(n^3)
    A4 := mult_matrix(A3, A, n) // T=O(logn), P=O(n^3)
    for all i,j where 1 ≤ i ≤ n, 1 ≤ j ≤ n pardo // P=O(n^2)
        C[i,j] := A4[i,j] - A3[i,j] - A2[i,j] - A[i,j]
end