查找 DAG 中所有不可比较的节点

Question

我有兴趣在有向无环图中找到无序的顶点集（在拓扑顺序的意义上）。

即，例如：非连通子图中的两个顶点，或在以下情况下的对 (B,C), (B,D) :

我想到的天真的可能性是枚举所有拓扑排序（在这种情况下 [ A, B, C, D ] 和 [ A, C, D, B ] 并找到所有顺序最终在至少两种排序中不同的对，但是这在计算上会非常昂贵。

对于我想要实现的目标，还有其他更快的可能性吗？我正在使用 boost.graph.

Answer 1

基本上你想要的是一对节点 (u,v) 使得没有从 u 到 v 的路径，也没有从 v 到 u 的路径。您可以为每个节点找到使用 DFS 从该节点可访问的所有节点。总复杂度 O(n(n+m)).

现在您所要做的就是为每一对检查两个节点中的任何一个是否都无法被另一个访问。

Answer 2

你可以从简单的拓扑排序开始。 Boost 的实现很方便 returns 一个反向排序的顶点列表。

您可以迭代该列表，用新的分支 ID 标记每个初始叶节点，直到遇到共享节点。

演示时间

让我们从最简单的图形模型开始：

#include <boost/graph/adjacency_list.hpp>

using Graph = boost::adjacency_list<>;

我们希望映射分支：

using BranchID = int;
using BranchMap = std::vector<BranchID>; // maps vertex id -> branch id

我们想要构建、映射和可视化映射：

Graph     build();
BranchMap map_branches(Graph const&);
void      visualize(Graph const&, BranchMap const& branch_map);

int main() {
    // sample data
    Graph g = build();

    // do the topo sort and distinguish branches
    BranchMap mappings = map_branches(g);

    // output
    visualize(g, mappings);
}

构建图表

只是问题的示例数据：

Graph build() {
    Graph g(4);

    enum {A,B,C,D};
    add_edge(A, B, g);
    add_edge(A, C, g);
    add_edge(C, D, g);

    return g;
}

映射分支

如介绍中所述：

#include <boost/graph/topological_sort.hpp>

std::vector<BranchID> map_branches(Graph const& g) {
    std::vector<Vertex> reverse_topo;
    boost::topological_sort(g, back_inserter(reverse_topo));

    // traverse the output to map to unique branch ids
    std::vector<BranchID> branch_map(num_vertices(g));

    BranchID branch_id = 0;

    for (auto v : reverse_topo) {
        auto degree = out_degree(v, g);
        if (0 == degree) // is leaf?
            ++branch_id;

        if (degree < 2) // "unique" path
            branch_map[v] = branch_id;
    }

    return branch_map;
}

可视化

让我们写一个图形可视化表示，每个分支都有颜色：

#include <boost/graph/graphviz.hpp>
#include <iostream>

void visualize(Graph const& g, BranchMap const& branch_map) {
    // display helpers
    std::vector<std::string> const colors { "gray", "red", "green", "blue" };

    auto name = [](Vertex v) -> char { return 'A'+v; };
    auto color = [&](Vertex v) -> std::string { return colors[branch_map.at(v) % colors.size()]; };

    // write graphviz:
    boost::dynamic_properties dp;
    dp.property("node_id", transform(name));
    dp.property("color", transform(color));

    write_graphviz_dp(std::cout, g, dp);
}

这使用一个微小的 shorthand 助手来创建转换属性贴图：

// convenience short-hand to write transformed property maps
template <typename F>
static auto transform(F f) { return boost::make_transform_value_property_map(f, boost::identity_property_map{}); };

To compile this on a non-c++14 compiler you can replace the call to transform with the expanded body

完整列表

Live On Coliru

#include <boost/graph/adjacency_list.hpp>

using Graph = boost::adjacency_list<>;

using BranchID = int;
using BranchMap = std::vector<BranchID>; // maps vertex id -> branch id

Graph     build();
BranchMap map_branches(Graph const&);
void      visualize(Graph const&, BranchMap const& branch_map);

int main() {
    // sample data
    Graph g = build();

    // do the topo sort and distinguish branches
    BranchMap mappings = map_branches(g);

    // output
    visualize(g, mappings);
}

using Vertex = Graph::vertex_descriptor;

Graph build() {
    Graph g(4);

    enum {A,B,C,D};
    add_edge(A, B, g);
    add_edge(A, C, g);
    add_edge(C, D, g);

    return g;
}

#include <boost/graph/topological_sort.hpp>

std::vector<BranchID> map_branches(Graph const& g) {
    std::vector<Vertex> reverse_topo;
    boost::topological_sort(g, back_inserter(reverse_topo));

    // traverse the output to map to unique branch ids
    std::vector<BranchID> branch_map(num_vertices(g));

    BranchID branch_id = 0;

    for (auto v : reverse_topo) {
        auto degree = out_degree(v, g);
        if (0 == degree) // is leaf?
            ++branch_id;

        if (degree < 2) // "unique" path
            branch_map[v] = branch_id;
    }

    return branch_map;
}

#include <boost/property_map/transform_value_property_map.hpp>

// convenience short-hand to write transformed property maps
template <typename F>
static auto transform(F f) { return boost::make_transform_value_property_map(f, boost::identity_property_map{}); };

#include <boost/graph/graphviz.hpp>
#include <iostream>

void visualize(Graph const& g, BranchMap const& branch_map) {
    // display helpers
    std::vector<std::string> const colors { "gray", "red", "green", "blue" };

    auto name = [](Vertex v) -> char { return 'A'+v; };
    auto color = [&](Vertex v) -> std::string { return colors[branch_map.at(v) % colors.size()]; };

    // write graphviz:
    boost::dynamic_properties dp;
    dp.property("node_id", transform(name));
    dp.property("color", transform(color));

    write_graphviz_dp(std::cout, g, dp);
}

打印

digraph G {
A [color=gray];
B [color=red];
C [color=green];
D [color=green];
A->B ;
A->C ;
C->D ;
}

以及渲染图：

总结

分支中不同颜色的节点无法比较。

查找 DAG 中所有不可比较的节点

Finding all non-comparable nodes in DAG

boost

graph

directed-graph

directed-acyclic-graphs

演示时间

构建图表

映射分支

可视化

完整列表

总结