Что необходимо для использования алгоритмов BGL в существующих структурах данных (ребра и вершины как вектор<Объект *>)?

У меня есть пользовательские структуры данных, подобные этому:

vector<myVertex *> my_vertices;
vector<myEdge *> my_edges;

В моем классе myEdge есть методы source() и target(), возвращающие myVertex*, поэтому он должен быть готов как есть, верно?

Какой внешняя адаптация мне нужно сделать, чтобы использовать граф BGL с моими контейнерами? Я знаю о примеры адаптеров в документе, но буду очень признателен за помощь!

Меня интересует простой тип базового графа adjacency_list, но я пока не уверен в концепциях обхода графа, которые мне нужны.

Что я понял о параметрах adjacency_list:

adjacency_list<OutEdgeListS, VertexListS, DirectedS,
             VertexProperty, EdgeProperty, GraphProperty, EdgeListS>
  • OutEdgeListS и VertexListS — это селекторы для контейнеров, используемых для представления (1) списка ребер для каждой из вершин и (2) списка вершин. Эти контейнеры содержат элементы vertex_descriptor и edge_descriptor соответственно. Мой тип контейнера — простой std::vector, поэтому я думаю, что мне не нужно создавать новый тип контейнера, как в примере/container_gen.cpp. я нужно просто уточнить, возможно, с помощью graph_traits, что тип моих элементов контейнера является указателем на объект.
  • VertexProperty и EdgeProperty предназначены для использования в качестве внутреннего хранилища дополнительной информации, например, цветовых меток, весов кромок... и уже несколько лет предлагают функцию пакетного свойства.

Я хотел бы, чтобы дескрипторы вершин и ребер не были целыми числами по умолчанию, а были указателями на мои объекты. В документации BGL прямо указано, что это возможно в версии книги 2002 г., 12.1.2:

An object-oriented graph implementation might use pointers to heap allocated vertex objects. With the graph traits class, these differences are hidden by the vertex descriptor associated type.

Хотя, похоже, он исчез из текущего онлайн-документа 1.70.

В идеале я хотел бы инициализировать так:

MyGraph g(const& my_edges,const& my_vertices,
  undirected_tag, some_color, someweights, allow_parallel_edges_tag);

P.S. Меня не интересует размещение указателей объектов в файле property_map. Я не хочу использовать «vecS по умолчанию», std::vector, где дескриптор является целым числом. Я готов использовать «пользовательский vecS» в качестве std::vector указателей на объекты; как для OutEdgeList, так и для VertexList.

Обновлено: это тот же самый вопрос, что и «1». из Вот этот. За исключением того, что на него так и не ответили... и предложенное решение было для "2.", с property_map и дорогим двойным сопоставлением :). Похоже, что после нескольких часов изучения сотен тем SO большинство людей рекомендуют использовать property_maps, а не работать с пользовательскими контейнерами. Люди склонны использовать карты свойств для хранения фактических узлов и ребер — их указателей на объекты, и позволяют дескрипторам вершин и краев содержать чистые целочисленные индексы по умолчанию. Тем не менее, из того, что я здесь прочитал, «ниже» vertex_descriptor находится внутренний слой реального индекса для повышения.

В качестве контекста: я планирую использовать dijkstra/johnson_all_pairs_shortest_paths (с картой предшественника и посетителем?), а в дальнейшем оптимальный-dreyfus-wagner для деревьев штейнера с http://paal.mimuw.edu.pl/, библиотекой поверх bgl. Чтобы создать решатель соединения sql для инструмента dbms-erd pgmodeler https://github.com/pgmodeler/pgmodeler/pull/1232.

20.05.19 : Отвечаю на ответ Sehe.

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

Я собираюсь изучить компромиссы между подходами :

  1. оставьте мои структуры данных как есть, а ваше решение пользовательского графика. я будет тратить совсем немного времени на инициализацию, но, вероятно, много больше времени на поиск преимуществ. Низкая пространственная сложность, но высокое время сложность.
  2. Тот же подход, но рефакторинг моей библиотеки, добавление выделенного хранилища с вектор инцидентных ребер на вершину (как атрибут класса моя вершина?). Поиск по краю с постоянным временем, а не O (log (n)) с (1) std::equal_range ? Наверное лучший вариант.
  3. Используйте adjacency_list, но с временной сложностью bgl гарантии.
    • Создайте список смежности по умолчанию, настройте двустороннее сопоставление с моим библиотечные контейнеры/использовать связанные/внутренние свойства. Высокое пространство сложность ; низкая временная сложность, но только для алгоритмов bgl, инициализация будет долгой.
    • Не хотите ли вы также уточнить, имеете ли вы правильный OutEdgeList и VertexList позволяет использовать класс списка смежности с пользовательскими контейнеры вариант ? Сохраняете ссылки на эти колодки ? Я подозреваю на данный момент реализация adjacency_list не может быть что гибкий.

Хотите сузить это до определенного минимальный воспроизводимый пример, используя #include <boost/graph/????_graph.hpp>? Я могу нанести удар по нему. Я знаю общие принципы. Подождите ... по той ссылке, по которой, как вы сказали, никогда не отвечали, есть принятый ответ с положительными голосами.

Kenny Ostrom 18.05.2019 23:34

Это использует связанные свойства, это работает, но я вынужден копировать вершины и ребра по одному, когда структуры данных уже готовы к работе framabin.org/p/?38454294b9eecc09#fONu/B/xaGhaXk6Dlf/3/ehs/…. Это пытается использовать пользовательские контейнеры, и я очень далек от правильного понимания: framabin.org/p/…. Принятый ответ выдает файл leda как RTFM и убегает к «обходному решению пакета».

AIDoubt 19.05.2019 00:11

Хорошая развязка с ответами. 1. Стоимость временной сложности может быть не так уж велика. Это зависит от масштаба и распределения (логарифм (N) довольно быстр, ЕСЛИ ваши ребра действительно упорядочены. Было бы несложно добавить небольшой кэш поиска в конструктор оболочки Glue (MyGraph).

sehe 20.05.2019 16:53

Я согласен, что 2., вероятно, оптимален и концептуально чист (он требует специального кода BGL, но это было бы ненавязчиво, поэтому можно избежать тесной связи).

sehe 20.05.2019 16:53

3. [объявление 1-й маркер] упрощение, если вам не нужно часто изменять график и сохранять сопоставления, кажется наименьшим кодом/обслуживанием магии BGL. Вы сможете наиболее эффективно использовать, например. существующий объем работ по StackOverflow

sehe 20.05.2019 16:57

3. [объявление 2-й пункт] Я согласен, что он не будет достаточно гибким. Я думаю, независимо от того, как вы его вращаете, adjacency_list будет предполагать, что он может создать контейнер out-edge-list (поэтому ссылки отсутствуют), и даже если вы заставите его использовать «фальшивую контейнерную оболочку», чтобы на самом деле ссылаться на ваш список вершин, который вероятно, нарушил бы некоторые предположения в библиотеке. Я думаю, что графические модели по определению имеют семантику значений в BGL). Не стоит?

sehe 20.05.2019 16:57
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
4
6
372
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Документация по концепциям Graph находится здесь: https://www.boost.org/doc/libs/1_70_0/libs/graph/doc/graph_concepts.html

Итак, вы так и не сказали нам, какие алгоритмы собираетесь использовать.

Итак, позвольте мне выбрать примеры: BFS. документы говорит, что для этого требуется:

A directed or undirected graph. The graph type must be a model of Vertex List Graph and Incidence Graph.

Глядя на ваши уже существующие структуры данных, кажется, что вы легко охватываете только вариант использования Vertex List.

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

In reality, it's pretty likely that you omitted parts of your pre-existing data-structures that are relevant to the problem, as most algorithms will be highly sub-optimal on just Vertex+Edge lists.

In practice I suppose you Edge list might be organized like a classical adjacency list (e.g. ordering by source vertex, so you CAN have a O(log(n)) lookup by source vertex).

For the example below I'm assuming this is the case. Keep in mind we're only approaching the complexity guarantees from Incidence Graph Concept:

Complexity guarantees

The source(), target(), and out_edges() functions must all be constant time. The out_degree() function must be linear in the number of out-edges.

To actually meet these requirements, you will need to have dedicated storage of out-edges per vertex

Итак, приступим:

Издевательство над вашей библиотекой

namespace YourLibrary {
    struct myVertex {
    };

    struct myEdge {
        myVertex* _s = nullptr;
        myVertex* _t = nullptr;

        myVertex* source() const { return _s; }
        myVertex* target() const { return _t; }
    };

    using Vertices = std::vector<myVertex *>;
    using Edges = std::vector<myEdge *>;
}

Реализация концепций графа

Вы хотели сохранить ссылки на уже существующие структуры данных:

namespace Glue {

    struct MyGraph {
        struct EdgeOrder {
            template <typename A, typename B>
                bool operator()(A const* a, B const* b) const { return source(a) < source(b); }
            private:
            static auto source(YourLibrary::myVertex const* v) { return v; }
            static auto source(YourLibrary::myEdge const* e) { return e->source(); }
        };

        using Vertices = YourLibrary::Vertices;
        using Edges = YourLibrary::Edges;

        Vertices& _vertices;
        Edges& _edges;

        MyGraph(Vertices& vv, Edges& ee) : _vertices(vv), _edges(ee)  { }
    };
}

Теперь я просто пробежусь по списку требуемых типов признаков для каждой концепции:

namespace boost {

    template <> struct graph_traits<Glue::MyGraph> {
        // Due to Graph concept
        using vertex_descriptor      = YourLibrary::myVertex*;
        using edge_descriptor        = YourLibrary::myEdge*;
        using directed_category      = directed_tag;
        using edge_parallel_category = allow_parallel_edge_tag;
        static vertex_descriptor null_vertex() { return nullptr; }

        // Due to Vertex List concept
        struct traversal_category : vertex_list_graph_tag, incidence_graph_tag { };
        using vertex_iterator        = Glue::MyGraph::Vertices::const_iterator;
        using vertices_size_type     = std::size_t;

        // Due to Incidence Graph concept
        using out_edge_iterator = Glue::MyGraph::Edges::const_iterator;
        using degree_size_type = std::size_t;
    };

}

И, наконец, повторно откройте пространство имен, чтобы ADL мог найти эти функции, необходимые для удовлетворения критерия «допустимых выражений»:

namespace Glue {
    // Due to Vertex List concept
    auto vertices(MyGraph const& g) {
        return std::make_pair(g._vertices.begin(), g._vertices.end());
    }

    std::size_t num_vertices(MyGraph const& g) {
        return g._vertices.size();
    }

    // Due to Incidence Graph concept
    auto source(YourLibrary::myEdge const* e, MyGraph const& g) {
        return e->source();
    }
    auto target(YourLibrary::myEdge const* e, MyGraph const& g) {
        return e->target();
    }

    auto out_edges(YourLibrary::myVertex const* v, MyGraph const& g) {
        return std::equal_range(g._edges.begin(), g._edges.end(), v, MyGraph::EdgeOrder{});;
    }
    std::size_t out_degree(YourLibrary::myVertex const* v, MyGraph const& g) {
        auto oee = std::equal_range(g._edges.begin(), g._edges.end(), v, MyGraph::EdgeOrder{});
        return std::distance(oee.first, oee.second);
    }
}

Это будет примерно эквивалентно функционально adjacency_list с setS для контейнера вершин.

Посмотреть Live On Coliru

Запуск BFS

Все, что требуется дополнительно, это аргументы алгоритма. Вам понадобится как карта цветов, так и карта индекса вершин. Это совершенно нормально и также потребуется, если у вас есть, например. adjacency_list<vecS, listS, directedS>.

Я скрою индексную карту внутри оболочки MyGraph и открою цветовую карту, чтобы вы могли выбрать свои предпочтения:

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/container/flat_map.hpp>
#include <algorithm>

namespace YourLibrary {
    struct myVertex {
    };

    struct myEdge {
        myVertex* _s = nullptr;
        myVertex* _t = nullptr;

        myVertex* source() const { return _s; }
        myVertex* target() const { return _t; }
    };

    using Vertices = std::vector<myVertex *>;
    using Edges = std::vector<myEdge *>;
}

namespace Glue {

    struct MyGraph {
        struct EdgeOrder {
            template <typename A, typename B>
                bool operator()(A const* a, B const* b) const { return source(a) < source(b); }
            private:
            static auto source(YourLibrary::myVertex const* v) { return v; }
            static auto source(YourLibrary::myEdge const* e) { return e->source(); }
        };

        using Vertices = YourLibrary::Vertices;
        using Edges = YourLibrary::Edges;

        using Index = boost::container::flat_map<Vertices::value_type, std::size_t>;

        Vertices& _vertices;
        Edges& _edges;
        Index _index;

        MyGraph(Vertices& vv, Edges& ee) : _vertices(vv), _edges(ee)  {
            _index.reserve(vv.size());
            std::size_t i = 0;
            for(auto v : vv) { _index[v] = i++; }
        }
    };
}

namespace boost {

    template <> struct graph_traits<Glue::MyGraph> {
        // Due to Graph concept
        using vertex_descriptor      = YourLibrary::myVertex*;
        using edge_descriptor        = YourLibrary::myEdge*;
        using directed_category      = directed_tag;
        using edge_parallel_category = allow_parallel_edge_tag;
        static vertex_descriptor null_vertex() { return nullptr; }

        // Due to Vertex List concept
        struct traversal_category : vertex_list_graph_tag, incidence_graph_tag { };
        using vertex_iterator        = Glue::MyGraph::Vertices::const_iterator;
        using vertices_size_type     = std::size_t;

        // Due to Incidence Graph concept
        using out_edge_iterator = Glue::MyGraph::Edges::const_iterator;
        using degree_size_type = std::size_t;
    };

}

namespace Glue {
    // Due to Vertex List concept
    auto vertices(MyGraph const& g) {
        return std::make_pair(g._vertices.begin(), g._vertices.end());
    }

    std::size_t num_vertices(MyGraph const& g) {
        return g._vertices.size();
    }

    // Due to Incidence Graph concept
    auto source(YourLibrary::myEdge const* e, MyGraph const& g) {
        return e->source();
    }
    auto target(YourLibrary::myEdge const* e, MyGraph const& g) {
        return e->target();
    }

    auto out_edges(YourLibrary::myVertex const* v, MyGraph const& g) {
        return std::equal_range(g._edges.begin(), g._edges.end(), v, MyGraph::EdgeOrder{});;
    }
    std::size_t out_degree(YourLibrary::myVertex const* v, MyGraph const& g) {
        auto oee = std::equal_range(g._edges.begin(), g._edges.end(), v, MyGraph::EdgeOrder{});
        return std::distance(oee.first, oee.second);
    }

    // Due to BFD requiring the index_map
    auto get(boost::vertex_index_t, MyGraph const& g) {
        return boost::make_assoc_property_map(g._index);
    }
}

int main() {
    // I hate manual memory management, so let's own some objects
    auto a = std::make_unique<YourLibrary::myVertex>();
    auto b = std::make_unique<YourLibrary::myVertex>();
    auto c = std::make_unique<YourLibrary::myVertex>();
    auto ab = std::make_unique<YourLibrary::myEdge>(YourLibrary::myEdge{a.get(), b.get()});
    auto bc = std::make_unique<YourLibrary::myEdge>(YourLibrary::myEdge{b.get(), c.get()});

    // These were given in your question:
    YourLibrary::Vertices vv { a.get(), b.get(), c.get() };
    YourLibrary::Edges ee { ab.get(), bc.get() };

    // this is the glue required to fulfill the BGL concepts:
    Glue::MyGraph g(vv, ee);

    // this is showing that you can now BFS on it
    using V = boost::graph_traits<Glue::MyGraph>::vertex_descriptor;
    V start_vertex = a.get();
    std::map<V, boost::default_color_type> color_data;

    boost::breadth_first_search(g, start_vertex,
            boost::visitor(boost::default_bfs_visitor{})
            .color_map(boost::make_assoc_property_map(color_data)));
}

Заключение

У алгоритмов есть требования, и пока вы их удовлетворяете, вы можете использовать любую структуру данных, которую захотите.

В этом случае вы МОЖЕТЕ захотеть быть действительно уверенными в сделанных предположениях и добавить это в конструктор MyGraph:

assert(std::is_sorted(_edges.begin(), _edges.end(), EdgeOrder{}));

Извините, в грязной истории правок этого поста я добавил контекст внизу и немного опоздал. Спасибо за подробный ответ, берусь за чтение.

AIDoubt 19.05.2019 02:11

Поскольку stackoverflow теперь действительно не поощряет темы в стиле форума ... Я добавил к своему первоначальному вопросу свою реакцию на ваш отличный ответ.

AIDoubt 20.05.2019 01:42

Да. Я думаю, что на самом деле это не решило проблему. Тем не менее, я согласился и прокомментировал пулю за пулей. В будущем и в интересах будущих посетителей, ищущих ответы, вы можете опубликовать новый вопрос. Это /больше работы/ и сложнее поставить вопрос с пользой, но, по крайней мере, это заставляет нас думать о более широкой картине и ценности вопросов для широкой публики :) Приветствия

sehe 20.05.2019 16:59

Спасибо за этот подробный ответ, это было очень полезно для моего понимания. Я все еще пытаюсь понять, почему этот пример не работает с такими функциями, как boost::out_edges? Кажется, это должно работать, поскольку Glue::MyGraph моделирует концепцию IncidenceGraph, но я получаю ошибки вывода типа на boost::out_edges(start_vertex, g); — может быть, я упускаю что-то очевидное?

bosmacs 23.02.2021 21:14

@bosmacs Вам нужно использовать АДЛ: Жить на Колируboost::edges на самом деле не реализован для нашего типа графика. Требования концепции сказать, что out_edges(v, g) должен компилироваться, а не boost::out_edges(v, g).

sehe 23.02.2021 21:50

Спасибо, что указали на это; это не первый раз, когда меня сбивает с толку ADL. Другой вопрос: depth_first_search работает с вашим примером, но topological_sort, который в основном является вызовом dfs, но с посетителем bgl_named_params, не работает. Знаете ли вы, что потребовалось бы для адаптации этого примера в данном случае? Я еще совсем не знаком с именованными параметрами, так что тем временем мне нужно кое-что почитать.

bosmacs 23.02.2021 23:36

@bosmacs Вы назвали все аргументы? Так. BGL требует очень пристального внимания к деталям. Лично мне не нравятся именованные аргументы (но я думаю, что это как-то связано с интерфейсом python-bgl)

sehe 24.02.2021 00:04

Я пропустил вопрос о топологической сортировке. Думаю, это заслуживает отдельного вопроса на основном сайте. Я думаю, что для топологической сортировки требуется индекс вершины (сопоставление вершин с [0..num_vertices(g))), а этого сейчас нет в коде.

sehe 24.02.2021 00:05
спросил.
bosmacs 24.02.2021 14:38

Другие вопросы по теме