Boost :: graph, получающий путь до корня - PullRequest
Новая
       34

Boost :: graph, получающий путь до корня

0 голосов
/ 18 октября 2018

У меня есть следующий график 

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

, и мне нужно получить путь до родителя вплоть до корневого узла.Я не могу изменить тип графика, есть ли алгоритм для этого и какая у него сложность?

1 Ответ

0 голосов
/ 19 октября 2018

Предполагая, что вы знаете, что ваш граф действительно является деревом, вы можете использовать топологическую сортировку для поиска корня.

Если вы знаете, что это DAG, вам, вероятно, следуетнайти корни, найдя листовые узлы в обратном графе - это немного дороже.Но, может быть, вы просто знаете корни заранее, поэтому я буду считать эту проблему решенной для этой демонстрации.

Я начну с вашего графика: 

struct GraphItem { std::string name; };

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

Название удобно для демонстрационных целей.Вы можете иметь все, что вам нужно в этом комплекте.Давайте добавим некоторые читаемые typedefs: 

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's, если все веса ребер эквивалентны): 

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

Youможно распечатать те, которые имеют подходящую карту свойств, чтобы получить отображаемое имя: 

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

График выглядит следующим образом:

enter image description here

Обратите внимание, что этот конкретный граф имеет несколько корней.Тот, который возвращается 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;
}
...