有向图最著名的传递闭包算法是什么？

Question

就运行时间而言，最著名的有向图传递闭包算法是什么？

我目前正在使用 Warshall 算法，但它的时间复杂度为 O(n^3)。尽管如此，由于图形表示，我的实现效果稍好一些（不是检查所有边，而是只检查所有外出边）。有没有比这更好的传递闭包算法？特别是，有没有专门针对共享内存多线程架构的东西？

Answer 1

本文讨论了各种传递闭包算法的性能：

http://www.vldb.org/ conf/1988/P382.PDF

论文中一个有趣的想法是避免在图形变化时重新计算整个闭包。

还有 Esko Nuutila 的这个页面，其中列出了一些最新的算法：

http: //www.cs.hut.fi/~enu/tc.html

该页面上列出的他的博士论文可能是最好的起点：

http://www.cs.hut.fi/~enu/thesis.html

从该页面：

实验还表明，使用区间表示
和新算法，可以计算传递闭包
通常在时间上与输入图的大小成线性关系。

Answer 2

算法设计手册有一些有用的信息。要点：

• 传递闭包和矩阵乘法一样困难；因此，最著名的边界是在 O 中运行的 Coppersmith–Winograd 算法 (n^2.376)，但实际上可能不值得使用矩阵乘法算法。
• 为了实现启发式加速，首先计算强连通分量。

Answer 3

令人惊讶的是，我无法找到 STACK_TC 算法的任何实现 由 Esko Nuutila 描述（由 AmigoNico 在另一个答案中链接）。

所以我用 C++ 编写了自己的简单实现。它与原始算法略有不同，请参阅代码中的注释以获取解释。

它成功地通过了我尝试过的一些测试，但鼓励读者进行更多测试，并根据原始论文进行验证。该代码可能未优化。

struct TransitiveClosure
{
    // The nodes of the graph are grouped into 'components'.
    // In a component, each node is reachable (possibly indirectly) from every other node.
    // If the number of components is same as the number of nodes, your graph has no cycles.
    // Otherwise there will be less components.
    // The components form a graph called 'condensation graph', which is always acyclic.
    // The components are numbered in a way that 'B is reachable from A' implies `B <= A`.

    struct Node
    {
        // An arbitrarily selected node in the same component. Same for all nodes in this component.
        std::size_t root = -1;
        // Index if the component this node belongs to.
        std::size_t comp = -1;
    };
    std::vector<Node> nodes; // Size is the number of nodes, which was passed in the argument.

    struct Component
    {
        // Nodes that are a part of this component.
        std::vector<std::size_t> nodes;
        // Which components are reachable (possibly indirectly) from this one.
        // Unordered, but has no duplicates. May or may not contain itself.
        std::vector<std::size_t> next;
        // A convenicene array.
        // `next_contains[i]` is 1 if and only if `next` contains `i`.
        // Some trailing zeroes might be missing, check the size before accessing it.
        std::vector<unsigned char/*boolean*/> next_contains;
    };
    std::vector<Component> components; // Size is the number of components.
};

[[nodiscard]] TransitiveClosure ComputeTransitiveClosure(std::size_t n, std::function<bool(std::size_t a, std::size_t b)> have_edge_from_to)
{
    // Implementation of the 'STACK_TC' algorithm, described by Esko Nuutila (1995), in
    // 'Efficient Transitive Closure Computation in Large Digraphs'.

    constexpr std::size_t nil = -1;

    TransitiveClosure ret;
    ret.nodes.resize(n);
    std::vector<std::size_t> vstack, cstack; // Vertex and component stacks.
    vstack.reserve(n);
    cstack.reserve(n);

    auto StackTc = [&](auto &StackTc, std::size_t v)
    {
        if (ret.nodes[v].root != nil)
            return; // We already visited `v`.
        ret.nodes[v].root = v;
        ret.nodes[v].comp = nil;
        vstack.push_back(v);
        std::size_t saved_height = cstack.size();
        bool self_loop = false;
        for (std::size_t w = 0; w < n; w++)
        {
            if (!have_edge_from_to(v, w))
                continue;
            if (v == w)
            {
                self_loop = true;
            }
            else
            {
                StackTc(StackTc, w);
                if (ret.nodes[w].comp == nil)
                    ret.nodes[v].root = std::min(ret.nodes[v].root, ret.nodes[w].root);
                else
                    cstack.push_back(ret.nodes[w].comp);

                // The paper that this is based on had an extra condition on this last `else` branch,
                // which I wasn't able to understand: `if (v,w) is not a forward edge`.
                // However! Ivo Gabe de Wolff (2019) in "Higher ranked region inference for compile-time garbage collection"
                // says that it doesn't affect correctness:
                // > In the loop over the successors, the original algorithm Stack_TC checks whether
                // > an edge is a so called forward edge. We do not perform this check, which may cause
                // > that a component is pushed multiple times to cstack. As duplicates are removed in the
                // > topological sort, these will be removed later on and not cause problems with correctness.
            }
        }
        if (ret.nodes[v].root == v)
        {
            std::size_t c = ret.components.size();
            ret.components.emplace_back();
            TransitiveClosure::Component &this_comp = ret.components.back();

            this_comp.next_contains.assign(ret.components.size(), false); // Sic.

            if (vstack.back() != v || self_loop)
            {
                this_comp.next.push_back(c);
                this_comp.next_contains[c] = true;
            }

            // Topologically sort a part of the component stack.
            std::sort(cstack.begin() + saved_height, cstack.end(), [&comp = ret.components](std::size_t a, std::size_t b) -> bool
            {
                if (b >= comp[a].next_contains.size())
                    return false;
                return comp[a].next_contains[b];
            });
            // Remove duplicates.
            cstack.erase(std::unique(cstack.begin() + saved_height, cstack.end()), cstack.end());

            while (cstack.size() != saved_height)
            {
                std::size_t x = cstack.back();
                cstack.pop_back();
                if (!this_comp.next_contains[x])
                {
                    if (!this_comp.next_contains[x])
                    {
                        this_comp.next.push_back(x);
                        this_comp.next_contains[x] = true;
                    }

                    this_comp.next.reserve(this_comp.next.size() + ret.components[x].next.size());
                    for (std::size_t c : ret.components[x].next)
                    {
                        if (!this_comp.next_contains[c])
                        {
                            this_comp.next.push_back(c);
                            this_comp.next_contains[c] = true;
                        }
                    }
                }
            }

            std::size_t w;
            do
            {
                w = vstack.back();
                vstack.pop_back();
                ret.nodes[w].comp = c;
                this_comp.nodes.push_back(w);
            }
            while (w != v);
        }
    };

    for (std::size_t v = 0; v < n; v++)
        StackTc(StackTc, v);

    return ret;
}

我的测试用例（来自同一篇论文）：

• 输入：（邻接矩阵，Y是边源，X是边目的地）

  {0,1,0,0,0,0,0,0},
  {0,0,1,1,0,0,0,0},
  {1,0,0,1,0,0,0,0},
  {0,0,0,0,1,1,0,0},
  {0,0,0,0,0,0,1,0},
  {0,0,0,0,1,0,0,1},
  {0,0,0,0,1,0,0,0},
  {0,0,0,0,0,1,0,0},
  

  输出：

  {nodes=[(0,3),(0,3),(0,3),(3,2),(4,0), (5,1),(4,0),(5,1)],组件=[{节点=[6,4],next=[0],next_contains=[1]},{节点=[7, 5],next=[1,0],next_contains=[1,1]},{节点=[3],next=[0,1],next_contains=[1,1,0]},{节点=[ 2,1,0],下一个=[3,2,0,1],next_contains=[1,1,1,1]}]}
  

• 输入：

  // abcdefghij
  /* 一个 */{0,1,0,0,0,1,0,1,0,0},
  /* b */{1,0,1,0,0,0,0,0,0,0},
  /* c */{0,1,0,1,0,0,0,0,0,0},
  /* d */{0,0,0,0,1,0,0,0,0,0},
  /* e */{0,0,0,1,0,0,0,0,0,0},
  /* f */{0,0,0,0,0,0,1,0,0,0},
  /*克*/{0,0,0,1,0,1,0,0,0,0},
  /* h */{0,0,0,0,0,0,0,0,1,0},
  /* 我 */{0,0,1,0,1,0,0,1,0,1},
  /* j */{0,0,0,0,0,0,0,0,0,0},
  

  输出：

  {nodes=[(0,3),(0,3),(0,3),(3,0),(3,0), (5,1),(5,1),(0,3),(0,3),(9,2)],组件=[{节点=[4,3],next=[0],next_contains =[1]},{节点=[6,5],next=[1,0],next_contains=[1,1]},{节点=[9],next=[],next_contains=[0,0 ,0]},{节点=[8,7,2,1,0],next=[3,2,0,1],next_contains=[1,1,1,1]}]}