c# – 并行化传递减少

但可能并行化并不是必需的,数据结构效率不高.你使用字典,其中数组就足够了(因为我理解代码你有顶点0..result.Count-1).并列出< 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.");

编辑

我写了这个：
代码有一些问题.随着我现在的方向,您可以删除您需要的边缘,结果将是不正确的.结果证明这是一个错误.我这样想,让我们有一个图表

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

顶点2被顶点1缩小,所以我们有

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

现在顶点3被顶点2缩小

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

并且我们有一个问题,因为我们不能减少因为2-> 0减少而留在这里的3> 0.但这是我的错,这绝不会发生.内循环严格地从低到高,所以相反

顶点3被顶点1缩小

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

现在由顶点2

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

结果是正确的.我为错误道歉.