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

我有下图

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

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

最佳答案

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



我将从您的图表开始:

struct GraphItem { std::string name; };

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

该名称便于演示。在该 bundle 包中，您可以拥有所需的任何东西。让我们添加一些可读的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);

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

该图如下所示:





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

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

关于c++ - Boost::graph获取到达根目录的路径，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/52878925/