У меня есть пользовательские структуры данных, подобные этому:
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.
Потрясающая информация, которую клеи объединяет воедино, и заставила меня наверстать упущенное в некоторых основных моментах, таких как концепции графиков. Я пришел спросить, как использовать список смежности с пользовательскими структурами данных, а вы пошли объяснять, как определить полностью собственный граф.
Я собираюсь изучить компромиссы между подходами :
Это использует связанные свойства, это работает, но я вынужден копировать вершины и ребра по одному, когда структуры данных уже готовы к работе framabin.org/p/?38454294b9eecc09#fONu/B/xaGhaXk6Dlf/3/ehs/…. Это пытается использовать пользовательские контейнеры, и я очень далек от правильного понимания: framabin.org/p/…. Принятый ответ выдает файл leda как RTFM и убегает к «обходному решению пакета».
Хорошая развязка с ответами. 1. Стоимость временной сложности может быть не так уж велика. Это зависит от масштаба и распределения (логарифм (N) довольно быстр, ЕСЛИ ваши ребра действительно упорядочены. Было бы несложно добавить небольшой кэш поиска в конструктор оболочки Glue (MyGraph
).
Я согласен, что 2., вероятно, оптимален и концептуально чист (он требует специального кода BGL, но это было бы ненавязчиво, поэтому можно избежать тесной связи).
3. [объявление 1-й маркер] упрощение, если вам не нужно часто изменять график и сохранять сопоставления, кажется наименьшим кодом/обслуживанием магии BGL. Вы сможете наиболее эффективно использовать, например. существующий объем работ по StackOverflow
3. [объявление 2-й пункт] Я согласен, что он не будет достаточно гибким. Я думаю, независимо от того, как вы его вращаете, adjacency_list будет предполагать, что он может создать контейнер out-edge-list (поэтому ссылки отсутствуют), и даже если вы заставите его использовать «фальшивую контейнерную оболочку», чтобы на самом деле ссылаться на ваш список вершин, который вероятно, нарушил бы некоторые предположения в библиотеке. Я думаю, что графические модели по определению имеют семантику значений в BGL). Не стоит?
Документация по концепциям 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()
, andout_edges()
functions must all be constant time. Theout_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
Все, что требуется дополнительно, это аргументы алгоритма. Вам понадобится как карта цветов, так и карта индекса вершин. Это совершенно нормально и также потребуется, если у вас есть, например. adjacency_list<vecS, listS, directedS>
.
Я скрою индексную карту внутри оболочки MyGraph
и открою цветовую карту, чтобы вы могли выбрать свои предпочтения:
#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{}));
Извините, в грязной истории правок этого поста я добавил контекст внизу и немного опоздал. Спасибо за подробный ответ, берусь за чтение.
Поскольку stackoverflow теперь действительно не поощряет темы в стиле форума ... Я добавил к своему первоначальному вопросу свою реакцию на ваш отличный ответ.
Да. Я думаю, что на самом деле это не решило проблему. Тем не менее, я согласился и прокомментировал пулю за пулей. В будущем и в интересах будущих посетителей, ищущих ответы, вы можете опубликовать новый вопрос. Это /больше работы/ и сложнее поставить вопрос с пользой, но, по крайней мере, это заставляет нас думать о более широкой картине и ценности вопросов для широкой публики :) Приветствия
Спасибо за этот подробный ответ, это было очень полезно для моего понимания. Я все еще пытаюсь понять, почему этот пример не работает с такими функциями, как boost::out_edges
? Кажется, это должно работать, поскольку Glue::MyGraph
моделирует концепцию IncidenceGraph, но я получаю ошибки вывода типа на boost::out_edges(start_vertex, g);
— может быть, я упускаю что-то очевидное?
@bosmacs Вам нужно использовать АДЛ: Жить на Колируboost::edges
на самом деле не реализован для нашего типа графика. Требования концепции сказать, что out_edges(v, g)
должен компилироваться, а не boost::out_edges(v, g)
.
Спасибо, что указали на это; это не первый раз, когда меня сбивает с толку ADL. Другой вопрос: depth_first_search
работает с вашим примером, но topological_sort
, который в основном является вызовом dfs, но с посетителем bgl_named_params
, не работает. Знаете ли вы, что потребовалось бы для адаптации этого примера в данном случае? Я еще совсем не знаком с именованными параметрами, так что тем временем мне нужно кое-что почитать.
@bosmacs Вы назвали все аргументы? Так. BGL требует очень пристального внимания к деталям. Лично мне не нравятся именованные аргументы (но я думаю, что это как-то связано с интерфейсом python-bgl)
Я пропустил вопрос о топологической сортировке. Думаю, это заслуживает отдельного вопроса на основном сайте. Я думаю, что для топологической сортировки требуется индекс вершины (сопоставление вершин с [0..num_vertices(g))), а этого сейчас нет в коде.
Хотите сузить это до определенного минимальный воспроизводимый пример, используя #include <boost/graph/????_graph.hpp>? Я могу нанести удар по нему. Я знаю общие принципы. Подождите ... по той ссылке, по которой, как вы сказали, никогда не отвечали, есть принятый ответ с положительными голосами.