并行化传递闭包缩减

Question

我有一个 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));
    }
}

这个算法能否并行化？我可以在内部循环中使用Parallel.For，但是这不被推荐（https://msdn.microsoft.com/zh-cn/library/dd997392(v=vs.110).aspx#Anchor_2），而且速度提升也不会很明显（加上可能存在锁定问题）。我能并行化外部循环吗？

- Storm

---

在Stackoverflow上搜索“线程安全字典”。 - jdweng

这个图是传递闭包吗？否则这将无法工作（考虑1->2，2->3，3->4，1->4）。 - Antonín Lejsek

是的，没错。如果不是这样，就无法形成哈斯图。 - Storm

Answer 1

解决并行化问题的简单方法是分离数据。从原始数据结构中读取并写入新的数据结构。这样，您可以在并行运行时甚至不需要锁定。

但可能并行化甚至不是必要的，因为数据结构不够高效。您使用字典，而数组就足够了（根据我理解的代码，您有顶点0..result.Count-1）。对于查找，您使用List<int>。 List.Contains非常低效。更好的选择是HashSet。或者对于更密集的图形，使用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

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

- Antonín Lejsek

---

谢谢，我会尝试您的算法。请问，为什么i的增量存在问题，您能详细说明一下吗？我确定没有关系是j>=i的，所以关系的二进制矩阵只在i-j对角线（下三角）下方有真值。 - Storm