动态有向图上的跟踪可重构性

Question

我有一个任务，需要构建一个动态有向图并跟踪所有对的可达性（即在每个顶点中维护来自该顶点的可到达顶点列表），在每个边或顶点添加/删除后更新它。

这对于 DAG 来说是可行的：我可以找到每个节点的所有路径，并从下到上构建可达性列表。删除边后，我可以从删除的边找到并更新反向图中的所有路径（即受边删除影响的所有节点）。

但是当图表中有循环时我遇到了麻烦。例如，在下图中，对于顶点 6，有一条通往 3、5、4 个顶点的路径。如果我以不同的方式删除 3-5-6 循环中每个顶点的边（5,6）可达性更改（顶点 5 将失去 3,4,6、顶点 3 的可达性，将失去到 6 的路径，并且顶点6可达性将保持不变）

所以我想我可以制作一个凝聚图并对其应用上面的算法。但这看起来是一项艰巨的任务，所以我一直在寻找一个可以维护动态凝结图的图库。

所以我有两个问题：

1. 是否有更简单的方法来完成我可能错过的任务？
2. 有没有一个库（最好是c++）可以维护动态底层图的压缩图？

Answer 1

查找图形的组成部分：

声明

    /// @brief find components
    /// @param g the graph
    /// @return vector of vectors of vertex indices in each component
    ///
    /// the vertices in a component are all reachable from each other

    std::vector<path_t> components(
        const cGraph &g );

定义：

std::vector<std::vector<int>> components(
        const cGraph &g)
    {
        // working copy on input graph
        auto work = g;

        // store for maximal component collection
        std::vector<std::vector<int>> vcomponent;

        // true when all vertices have been moved into a clique
        bool finished = false;

        while (!finished)
        {
            std::vector<int> component;

            while (!finished)
            {
                if (!component.size())
                {
                    // start by moving an arbitrary node to the clique from the work graph
                    for (int vi = 0; vi < work.vertexCount(); vi++)
                    {
                        if (work.rVertexAttr(vi, 0) == "deleted")
                            continue;
                        component.push_back(vi);
                        work.wVertexAttr(vi, {"deleted"});
                        break;
                    }
                    continue;
                }
                bool found = false;

                // loop over nodes remaining in work graph
                finished = true;
                for (int u = 0; u < work.vertexCount(); u++)
                {
                    if (work.rVertexAttr(u, 0) == "deleted")
                        continue;
                    finished = false;

                        // loop over nodes in component
                        for (int v : component)
                        {
                            if (work.find(u, v) >= 0 ||
                                work.find(v, u) >= 0)
                            {
                                // found node in work that is connected to clique nodes.
                                // move it to component
                                component.push_back(u);
                                work.wVertexAttr(u, {"deleted"});
                                found = true;
                                break;
                            }
                        }
                    
                    if (found)
                        break; // found a node to add to component
                }
                if (!found)
                    break; // no more nodes can be added, the component is maximal
            }

            if (!component.size())
                break; // did not find a clique

            // add to collection of maximal cliques
            vcomponent.push_back(component);
        }

        return vcomponent;
    }
     

这使用 Pathfinder 图论库（https://github.com/JamesBremner/PathFinder）。您可以在任何像样的图论库中找到类似的方法。

如果您想为此目的使用 Pathfinder 应用程序，组件查找器的用户文档位于此处 https://github.com/JamesBremner/PathFinder/wiki/Components-or-Cliques

对于您的应用程序，您需要在每次更改后运行此方法以查看组件是否已更改。