Boost::graph 获取到根的路径

Question

我有以下图表

boost::adjacency_list<boost::setS, boost::vecS, boost::directedS, GraphItem>;

我需要一直到父节点的路径到根节点。我无法更改图形的类型，是否有任何算法以及它有什么复杂性？

Answer 1

假设你知道你的图实际上是一棵树，你可以使用拓扑排序来找到根。

如果你只知道它是一个 DAG，你可能应该通过在反向图中找到叶节点来找到根——这有点贵。但也许你只是事先知道根源，所以我会认为这个问题已经在这个演示中解决了。

我将从你的图表开始：

struct GraphItem { std::string name; };

using Graph  = boost::adjacency_list<boost::setS, boost::vecS, boost::directedS, GraphItem>;

该名称便于演示目的。您可以在该捆绑包中拥有您需要的任何东西。让我们添加一些可读的 typedef：

using Vertex = Graph::vertex_descriptor;
using Order  = std::vector<Vertex>;
using Path   = std::deque<Vertex>;
static constexpr Vertex NIL = -1;

要找到那个根，你会写：

Vertex find_root(Graph const& g) { // assuming there's only 1
    Order order;
    topological_sort(g, back_inserter(order));

    return order.back();
}

要从给定的根获取所有最短路径，您只需要一个 BFS（如果您的边权重都相等，则相当于 Dijkstra 的）：

Order shortest_paths(Vertex root, Graph const& g) {
    // find shortest paths from the root
    Order predecessors(num_vertices(g), NIL);
    auto recorder = boost::record_predecessors(predecessors.data(), boost::on_examine_edge());

    boost::breadth_first_search(g, root, boost::visitor(boost::make_bfs_visitor(recorder)));

    // assert(boost::count(predecessors, NIL) == 1); // if only one root allowed
    assert(predecessors[root] == NIL);

    return predecessors;
}

根据 BFS 返回的顺序，您可以找到您要查找的路径：

Path path(Vertex target, Order const& predecessors) {
    Path path { target };

    for (auto pred = predecessors[target]; pred != NIL; pred = predecessors[pred]) {
        path.push_back(pred);
    }

    return path;
}

您可以打印给定合适的属性映射以获取显示名称的那些：

template <typename Name> void print(Path path, Name name_map) {
    while (!path.empty()) {
        std::cout << name_map[path.front()];
        path.pop_front();
        if (!path.empty()) std::cout << " <- ";
    }
    std::cout << std::endl;
}

演示图

让我们开始演示

int main() {
    Graph g;
    // name helpers
    auto names   = get(&GraphItem::name, g);

这是使用属性映射从顶点获取名称的一个很好的演示。让我们定义一些助手，这样你就可以找到例如 node by_name("E")：

    auto named   = [=]   (std::string target) { return [=](Vertex vd) { return names[vd] == target; }; };
    auto by_name = [=,&g](std::string target) { return *boost::find_if(vertices(g), named(target)); };

让我们g用示例数据填充图形：

    // read sample graph
    {
        boost::dynamic_properties dp;
        dp.property("node_id", names);
        read_graphviz(R"( digraph {
                A -> H;
                B -> D; B -> F; C -> D; C -> G;
                E -> F; E -> G; G -> H;
                root -> A; root -> B
            })", g, dp);
    }

该图如下所示：

请注意，此特定图形具有多个根。返回的那个find_root恰好是最远的一个，因为它是最后找到的。

现在从给定的根中找到一些节点：

    for (auto root : { find_root(g), by_name("E") }) {
        auto const order = shortest_paths(root, g);
        std::cout << " -- From " << names[root] << "\n";

        for (auto target : { "G", "D", "H" })
            print(path(by_name(target), order), names);
    }

哪个打印

住在 Coliru

 -- From root
G
D <- B <- root
H <- A <- root
 -- From E
G <- E
D
H <- G <- E

完整列表

住在 Coliru

#include <boost/graph/adjacency_list.hpp>       // adjacency_list
#include <boost/graph/topological_sort.hpp>     // find_if
#include <boost/graph/breadth_first_search.hpp> // shortest paths
#include <boost/range/algorithm.hpp> // range find_if
#include <boost/graph/graphviz.hpp>  // read_graphviz
#include <iostream>

struct GraphItem { std::string name; };

using Graph  = boost::adjacency_list<boost::setS, boost::vecS, boost::directedS, GraphItem>;
using Vertex = Graph::vertex_descriptor;
using Order  = std::vector<Vertex>;
using Path   = std::deque<Vertex>;
static constexpr Vertex NIL = -1;

Vertex find_root(Graph const& g);
Order  shortest_paths(Vertex root, Graph const& g);
Path   path(Vertex target, Order const& predecessors);
template <typename Name> void print(Path path, Name name_map);

int main() {
    Graph g;
    // name helpers
    auto names   = get(&GraphItem::name, g);
    auto named   = [=]   (std::string target) { return [=](Vertex vd) { return names[vd] == target; }; };
    auto by_name = [=,&g](std::string target) { return *boost::find_if(vertices(g), named(target)); };

    // read sample graph
    {
        boost::dynamic_properties dp;
        dp.property("node_id", names);
        read_graphviz(R"( digraph {
                A -> H;
                B -> D; B -> F; C -> D; C -> G;
                E -> F; E -> G; G -> H;
                root -> A; root -> B
            })", g, dp);
    }

    // 3 paths from 2 different roots
    for (auto root : { find_root(g), by_name("E") }) {
        auto const order = shortest_paths(root, g);
        std::cout << " -- From " << names[root] << "\n";

        for (auto target : { "G", "D", "H" })
            print(path(by_name(target), order), names);
    }
}

Vertex find_root(Graph const& g) { // assuming there's only 1
    Order order;
    topological_sort(g, back_inserter(order));

    return order.back();
}

Order shortest_paths(Vertex root, Graph const& g) {
    // find shortest paths from the root
    Order predecessors(num_vertices(g), NIL);
    auto recorder = boost::record_predecessors(predecessors.data(), boost::on_examine_edge());

    boost::breadth_first_search(g, root, boost::visitor(boost::make_bfs_visitor(recorder)));

    // assert(boost::count(predecessors, NIL) == 1); // if only one root allowed
    assert(predecessors[root] == NIL);

    return predecessors;
}

Path path(Vertex target, Order const& predecessors) {
    Path path { target };

    for (auto pred = predecessors[target]; pred != NIL; pred = predecessors[pred]) {
        path.push_back(pred);
    }

    return path;
}

template <typename Name>
void print(Path path, Name name_map) {
    while (!path.empty()) {
        std::cout << name_map[path.front()];
        path.pop_front();
        if (!path.empty()) std::cout << " <- ";
    }
    std::cout << std::endl;
}