Parallelize transitive reduction

Question

У меня есть Dictionary<int, List<int>>, где Ключ представляет элемент множества (или вершину в ориентированном графе), а List - это набор других элементов, которые связаны с ключом (поэтому существуют ориентированные края от ключа до значений). Словарь оптимизирован для создания диаграммы Хассе, поэтому значения всегда меньше ключа.

У меня также есть простой последовательный алгоритм, который удаляет все транзитивные ребра (например, у меня есть отношения 1-> 2, 2-> 3 и 1-> 3. Я могу удалить край 1-> 3, потому что у меня есть путь между 1 и 3 через 2).

for(int i = 1; i < dictionary.Count; i++) 
{ 
    for(int j = 0; j < i; j++) 
    { 
     if(dictionary[i].Contains(j)) 
       dictionary[i].RemoveAll(r => dictionary[j].Contains(r)); 
    } 
} 

Можно ли распараллелить алгоритм? Я мог бы сделать Parallel.For для внутреннего цикла. Однако это не рекомендуется (https://msdn.microsoft.com/en-us/library/dd997392(v=vs.110).aspx#Anchor_2), и полученная скорость не будет значительно увеличиваться (+ могут возникнуть проблемы с блокировкой). Могу ли я распараллелить внешний цикл?

Answer 1

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

Но, вероятно, распараллеливание даже не требуется, структуры данных неэффективны. Вы используете словарь, где будет достаточно массива (поскольку я понимаю код У вас есть вершины 0..result.Count-1). И List<int> для поиска. List.Contains очень неэффективен. HashSet было бы лучше. Или, для более плотных графов, BitArray. Итак, вместо Dictionary<int, List<int>> Вы можете использовать BitArray[].

Я переписал алгоритм и сделал некоторые оптимизации. Он не делает простой копии графа и удаляет ребра, он просто конструирует новый граф только из правых краев. Он использует BitArray[] для входного графика и List<int>[] для окончательного графика, так как последний гораздо более разреженный.

int sizeOfGraph = 1000; 

//create vertices of a graph 
BitArray[] inputGraph = new BitArray[sizeOfGraph]; 
for (int i = 0; i < inputGraph.Length; ++i) 
{ 
    inputGraph[i] = new BitArray(i); 
} 

//fill random edges 
Random rand = new Random(10); 
for (int i = 1; i < inputGraph.Length; ++i) 
{ 
    BitArray vertex_i = inputGraph[i]; 
    for(int j = 0; j < vertex_i.Count; ++j) 
    { 
     if(rand.Next(0, 100) < 50) //50% fill ratio 
     { 
      vertex_i[j] = true; 
     } 
    } 
} 

//create transitive closure 
for (int i = 0; i < sizeOfGraph; ++i) 
{ 
    BitArray vertex_i = inputGraph[i]; 
    for (int j = 0; j < i; ++j) 
    { 
     if (vertex_i[j]) { continue; } 
     for (int r = j + 1; r < i; ++r) 
     { 
      if (vertex_i[r] && inputGraph[r][j]) 
      { 
       vertex_i[j] = true; 
       break; 
      } 
     } 
    } 
} 

//create transitive reduction 
List<int>[] reducedGraph = new List<int>[sizeOfGraph]; 
Parallel.ForEach(inputGraph, (vertex_i, state, ii) => 
{ 
    { 
     int i = (int)ii; 
     List<int> reducedVertex = reducedGraph[i] = new List<int>(); 

     for (int j = i - 1; j >= 0; --j) 
     { 
      if (vertex_i[j]) 
      { 
       bool ok = true; 
       for (int x = 0; x < reducedVertex.Count; ++x) 
       { 
        if (inputGraph[reducedVertex[x]][j]) 
        { 
         ok = false; 
         break; 
        } 
       } 
       if (ok) 
       { 
        reducedVertex.Add(j); 
       } 
      } 
     } 
    } 
}); 

MessageBox.Show("Finished, reduced graph has " 
    + reducedGraph.Sum(s => s.Count()) + " edges."); 

EDIT

я написал: код имеет некоторые проблемы. С направлением i теперь можно удалить края, которые вам нужны, и результат будет неправильным. Это оказалось ошибкой. Я думал, таким образом, позволяет иметь график

1->0 
2->1, 2->0 
3->2, 3->1, 3->0 

Vertex 2 получает уменьшенный на вершины 1, так что мы имеем

1->0 
2->1 
3->2, 3->1, 3->0 

Теперь вершиной 3 получает уменьшается на вершине 2

1->0 
2->1 
3->2, 3->0 

И у нас есть проблема, так как мы не можем уменьшить 3->0, который остался здесь из-за уменьшения 2->0. Но это моя ошибка, этого никогда не произойдет.Внутренний цикл проходит строго от низшего к высшему, так что вместо

Vertex 3 получает уменьшается на вершине 1

1->0 
2->1 
3->2, 3->1 

и теперь от вершины 2

1->0 
2->1 
3->2 

И результат является правильным. Прошу прощения за ошибку.