并行化传递性约简

本文关键字：传递性 并行化 | 更新日期: 2023-09-27 18:24:55

我有一个Dictionary<int, List<int>>，其中Key表示集合的一个元素（或有向图中的一个顶点），List是与Key相关的其他元素的集合（因此从Key到Values之间存在有向边）。字典是为创建Hasse图而优化的，因此Values总是小于Key。

我还有一个简单的序列算法，它去除了所有的传递边（例如，我有关系式1->2、2->3和1->3。我可以删除边1->3，因为我有一条通过2）在1和3之间的路径。

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));
    }
}

有可能将算法并行化吗？我可以做平行。对于内循环。但是，不建议这样做(https://msdn.microsoft.com/en-us/library/dd997392（v=vs.110）.aspx#Anchor_2），并且由此产生的速度不会显著提高（+锁定可能存在问题）。我可以并行化外循环吗？

并行化传递性约简

有一种简单的方法可以解决并行化问题，即分离数据。从原始数据结构读取并写入新数据。这样你就可以并行运行它，甚至不需要锁定。

但可能并行化甚至没有必要，数据结构也不高效。在数组足够的地方使用dictionary（正如我所理解的代码You have verticals 0..result.Count-1）。以及用于查找的List<int>。CCD_ 4是非常低效的。CCD_ 5会更好。或者，对于更稠密的图，BitArray。所以你可以用BitArray[]来代替Dictionary<int, List<int>>。

我重写了算法并进行了一些优化。它不制作图形的普通副本并删除边，它只是从右边构建新图形。它使用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

结果是正确的。我为这个错误道歉。

相关文章：