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;

要找到那个root，你会写：

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

    return order.back();
}

要从给定的根获取所有最短路径，您只需要一个BFS（如果您的边权重等于Dijkstra，则相当于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;
}

Demo Graph

我们来开始演示

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

该图如下所示：

请注意，此特定图表具有多个根。 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);
    }

哪个打印

Live On Coliru

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

完整清单

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