Возможно ли вычисление ребер в библиотеке графов ускорения? - PullRequest
Новая
       37

Возможно ли вычисление ребер в библиотеке графов ускорения?

1 голос
/ 10 июля 2019

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

Конечно, это тривиально реализовать путем итерации по всем существующим вершинами соединяя их с последним, который я добавил к графу, и используя отфильтрованный граф во время выполнения, чтобы решить, что соединение все еще сохраняется.

Цель состоит в том, чтобы использовать BFS или DFS или другие алгоритмы, предоставляемые BGL.

Есть ли другой подход для более эффективного выполнения этой задачи?Например: добавление всех (!) Вершин при инициализации и наличие какого-то обратного вызова, который проверяет ребро во время выполнения?

Вот как я пытался это решить, но этот не работает: 

#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/graph_utility.hpp>
struct VD { };
struct ED { };

struct Graph : boost::adjacency_matrix<boost::directedS, VD, ED>
{
    Graph() : boost::adjacency_matrix<boost::directedS, VD, ED>(4) { }
    //=================================================================
    // Functions required by the AdjacencyMatrix concept
    template <typename D, typename VP, typename EP, typename GP, typename A>
    std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, bool>
    edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
        typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
        const adjacency_matrix<D,VP,EP,GP,A>& g)
    {
        // Connect vertex 1 and 2
        bool exists = (u == 1 && v == 2);

        typename boost::adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor
            e(exists, u, v, boost::detail::get_edge_property(g.get_edge(u,v)));

        return std::make_pair(e, exists);
    }
};

int main() {
    Graph g;
    print_graph(g);

    std::vector<int> component(num_vertices(g));
    int num = boost::connected_components(g, &component[0]);
}

Буду признателен за любые указатели!

1 Ответ

0 голосов
/ 10 июля 2019

Из концепций BGL :

Сердцем библиотеки графов ускорения (BGL) является интерфейс или концепции (на языке универсального программирования), которые определяют, какграф можно исследовать и манипулировать нейтральным способом структуры данных.Фактически, интерфейс BGL даже не нужно реализовывать с использованием структуры данных, поскольку для некоторых задач проще или эффективнее определить граф, неявно основанный на некоторых функциях.

Стандартной модели реализации нет, но документы содержат пример в Глава 19: Адаптеры графиков

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

[2]:

...