Parallel Transitional Reduction

Question

I have Dictionary<int, List<int>>where Key represents a set element (or vertex in an oriented graph), and List is a set of other elements related to the key (therefore there are oriented edges from key to value). The dictionary is optimized to create a Hasse diagram, so the values ​​are always less than the key.

I also have a simple sequential algorithm that removes all transitive edges (for example, I have the relationships 1-> 2, 2-> 3 and 1-> 3. I can remove the edge 1-> 3 because I have a path between 1 and 3 through 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));
    }
}

Is it possible to parallelize the algorithm? I could do Parallel.For for the inner loop. However, this is not recommended ( https://msdn.microsoft.com/en-us/library/dd997392(v=vs.110).aspx#Anchor_2 ), and the resulting speed will not increase significantly (+ there may be problems with blocking) . Is it possible to parallelize the outer loop?

Answer 1

There is an easy way to solve the parallelization problem, separate data. Read the original data structure and write to a new one. This way you can run it in parallel without even blocking it.

, , , . , ( 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.");

: . , i , , , . . ,

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

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. , . ,

3 1

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

2

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

. .