c++ - Boost::graph 获取到根的路径

Question

我有下图

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

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

Answer 1

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

If you only know it to be a DAG, you should probably find roots by finding leaf nodes in the reverse graph - that's a bit more expensive. But maybe you just know the roots before-hand, so I'll consider this problem solved for this demo.

我将从您的图表开始:

struct GraphItem { std::string name; };

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

名称便于演示。您可以在该 bundle 中拥有任何您需要的东西。让我们添加一些可读的类型定义:

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);

这是使用属性映射从顶点获取名称的一个很好的演示。让我们定义一些助手，这样你就可以找到例如节点 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);
    }

图表看起来像这样:

Note that this particular graph has multiple roots. The one returned by find_root happens to be the furthest one because it's found last.

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

    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);
    }

哪个打印

Live On Coliru

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

完整 list

Live On 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;
}