Учебник по DFS: от последовательного к параллельному

Question

Итак, я реализовал наложение пути на графе с помощью специального A*, используя boost::graphНо все разработано с нуля.

То, что пути перекрываются, просто. Дан график букв ('A'-> 'C',...) и словом ПРИВЕТ, мне нужно найти лучшее перекрытие, начиная с 'H' на графике, оканчивающемся на 'O' (если он существует или заканчивается при достижении длины пути). "Лучший" относится к способу выбора узлов-кандидатов, просто исследуя букву, которая ближе к текущей в слове. Таким образом, веса графика являются динамическими, они зависят от входного слова. Смотрите следующий пример:

/*
 *    B          H
 *   / \        /
 *  A---D---F---G---I
 *   \ /\
 *    C  E
 *
 *  input:  A E I O U
 *  result: A D F G I
 */

То, что я сделал, очень просто: использовать DFS, которая отслеживает узлы и вставляет их в очередь с приоритетами. Очевидно, это не совсем оптимально: я бы очень хотел использовать boost::depth_first_search,

Моя проблема проста: во всех примерах используется обход графа без начального узла. График очень большой, как минимум 8M узлов, в надежде получить до 100M узлов в кластере. Поэтому я стремлюсь распределить граф по кластеру с помощью Parallel BGL.

Что вам предложить?

Возможно, мой подход с нуля на самом деле не самый лучший, было бы проще использовать BGL, но хотя мне удалось попробовать очень простой astar_searchЯ не могу попробовать простой depth_first_search, Я не могу понять цветовые карты и то, как я могу установить узел назначения, поэтому я опубликую свой код, надеясь, что кто-то укажет мне правильное направление.

Отметьте еще раз, мне нужно переместить код, когда он будет работать, в Parallel BGL.

Спасибо!

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
#include <utility>
#include <list>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/astar_search.hpp>

// Funky
std::unordered_map<char, int> letters;
auto getletter = [](std::size_t i) -> char { return 'A' + i; };


typedef boost::adjacency_list<boost::vecS, // V
                              boost::vecS, // E
                              boost::bidirectionalS,
                              boost::no_property,
                              int // Ignore weights for now
                              > graph;

typedef boost::graph_traits<graph>::edge_iterator edge_iterator;

// Used to end the A*-like search algorithm
struct end_astar { };

// Custom A* visitor
template <class Vertex>
class bestmatch_visitor : public boost::default_dfs_visitor //public boost::default_astar_visitor
{
public:

    // Constructor
    bestmatch_visitor(Vertex goal) : destination_(goal) { };

    // ==============
    // == VERTICES ==
    // ==============

    template<class Graph>
    void initialize_vertex(Vertex u, const Graph &g)
    {
        std::cout << "init " << u << " " << getletter(u) << std::endl;
    }

    // Push a new vertex in the stack
    template<class Graph>
    void discover_vertex(Vertex u, const Graph &g)
    {
        std::cout << "discover " << u << " " << getletter(u) << std::endl;
    }

    // Pop a vertex and examine it
    template <class Graph>
    void examine_vertex(Vertex u, const Graph& g)
    {
        std::cout << ">>>>> examine " << u << " " << getletter(u) << std::endl;

        if (u == destination_) throw end_astar();
    }

    // Vertex examined, moving to the blacklist
    template <class Graph>
    void finish_vertex(Vertex u, const Graph& g)
    {
        std::cout << "vertex examined, closing " << u << " " << getletter(u) << std::endl;
    }

    // ===========
    // == EDGES ==
    // ===========

    // Examine out edges
    template <class Edge, class Graph>
    void examine_edge(Edge e, const Graph& g)
    {
        std::cout << "--> edge examine " << e << std::endl;
    }

    // Relax edge if distance from goal reduces
    template <class Edge, class Graph>
    void edge_relaxed(Edge e, const Graph& g)
    {
        std::cout << "--> edge relax " << e << std::endl;
    }

    // Distance from goal does not decrease: don't relax
    template <class Edge, class Graph>
    void edge_not_relaxed(Edge e, const Graph& g)
    {
        std::cout << "--> edge NOT relaxed " << e << std::endl;
    }

    // Ooops! Already checked this one
    template <class Edge, class Graph>
    void black_target(Edge e, const Graph& g)
    {
        std::cout << "--> BLACKLISTED " << e << std::endl;
    }


private:
    Vertex destination_;
};


int main()
{
    /*
     *    B          H
     *   / \        /
     *  A---D---F---G---I
     *   \ /\
     *    C  E
     *
     *  input:  A Z I M U T
     *  result: A C D F G I
     *
     *  nodes:  ABCDEFGHI
     *  codes:  012345678
     */

    for (int i = 'A'; i <= 'I'; i++) letters[i] = i - 'A';

    graph g;

    boost::add_edge(letters['A'], letters['B'], g);
    boost::add_edge(letters['A'], letters['C'], g);
    boost::add_edge(letters['A'], letters['D'], g);

    boost::add_edge(letters['B'], letters['D'], g);

    boost::add_edge(letters['C'], letters['D'], g);

    boost::add_edge(letters['D'], letters['E'], g);
    boost::add_edge(letters['D'], letters['F'], g);

    boost::add_edge(letters['F'], letters['G'], g);

    boost::add_edge(letters['G'], letters['H'], g);
    boost::add_edge(letters['G'], letters['I'], g);

    edge_iterator ei, ee;

    for (boost::tie(ei, ee) = boost::edges(g); ei != ee; ei++)
    {
        graph::edge_descriptor d = *ei;

        std::cout << getletter(boost::source(*ei, g)) << " -> " <<
        getletter(boost::target(*ei, g)) << "    " << std::endl; //<< g[d] << std::endl;
    }

    // Predecessors
    std::vector<graph::vertex_descriptor> p(boost::num_vertices(g));

    // Distances
    std::vector<graph::vertex_descriptor> d(boost::num_vertices(g));

    // Color: HOW?
    //typename boost::property_map<graph, boost::vertex_color_t>::type c;

    // Start and finish
    int start = letters['A'];
    int goal  = letters['I'];

    bestmatch_visitor<int> v(letters['A']);

    // Useless:
    boost::depth_first_search(g, boost::visitor(v));

    // HOW?
    //boost::depth_first_visit(g, letters['A'], boost::visitor(v), c);

}

Answer 1

1. Похоже, у вас определен посетитель Bellman-Ford, а не посетитель DFS. Обратите внимание, что нет никакой параллелиbellman_ford_shortest_paths, но есть несколько других доступных алгоритмов поиска кратчайших путей. https://www.boost.org/doc/libs/1_71_0/libs/graph_parallel/doc/html/index.html

2. boost::depth_first_search можно задать начальную вершину с root_vertex.

3. Вам не нужно вводить цветовую карту; если вы используетеboost::vecSтип хранилища для ваших вершин, один будет предоставлен вам. В противном случае вы можете создать такую ​​цветовую карту:

using Vert = boost::graph_traits<MyGraph>::vertex_descriptor
using Map = std::unordered_map<Vert, boost::default_color_type, boost::hash<Vert>>;

Map stlColors;
auto boostColors = boost::make_assoc_property_map(stlColors);

5. API для инструментов параллельного графа был изменен, но документация не была обновлена, чтобы отразить это. В параллельной версии алгоритмов также наблюдается неожиданное поведение, которое не соответствует последовательному поведению.

   а. Параллельно хочешьdepth_first_visit или tsin_depth_first_visitне depth_first_search, который будет запускаться с разных узлов в каждом процессе.

   б. Вы должны быть очень осторожны с распределеннымиproperty_mapс. Простое чтение с карты может вызвать срабатывание операций MPI, что может вызватьdepth_first_visitварианты заблокировать. Что еще хуже, блокировки недетерминированы из-за асинхронной моделиmpi_process_group. breadth_first_searchпо моему опыту был намного более надежным. Я не тестировал алгоритмы кратчайших путей, но поскольку проблемы возникают из-за распределенногоproperty_maps, не думайте, что только потому, что он работает с 8 процессами, он не зависнет на 16... или зависнет в четвертый раз, когда вы запустите его на 8 процессах.

   c. Ошибка вmpi_process_groupбиблиотека параллельного графа ускорения, связанная с нулевыми узлами в некоторых процессах. Здесь есть исправление: https://github.com/boostorg/graph_parallel/issues/18