Документация для концепций Graph удобно здесь: https://www.boost.org/doc/libs/1_70_0/libs/graph/doc/graph_concepts.html
Итак, вы никогда не говорили нам, какие алгоритмы вы намереваетесь использовать.
Итак, позвольте мне выбрать примеры: BFS. Документы говорят, что для этого требуется:
Ориентированный или неориентированный граф.Тип графика должен быть моделью График списка вершин и График инцидентов .
Глядя на ваши уже существующие структуры данных, выглядит только вылегко охватить случай использования списка вершин.
Края реализованы больше как список краев.Невозможно эмулировать граф инцидентности из пограничного списка без времени выполнения или затрат на хранение (это математика, не имеет ничего общего с библиотекой или качеством кода).
В действительности, вполне вероятно, что вы пропустили части вашегоуже существующие структуры данных, которые имеют отношение к проблеме, так как большинство алгоритмов будут весьма неоптимальными только для списков Vertex + Edge.
На практике я предполагаю, что ваш список Edge может быть организован как классический список смежности.(например, упорядочение по исходной вершине, поэтому вы МОЖЕТЕ выполнить поиск O (log (n)) по исходной вершине).
Для примера ниже Я предполагаю, что это случай .Имейте в виду, что мы только приближаемся к гарантиям сложности из концепции графов инцидентов:
Гарантии сложности
source(), target() и out_edges() Функции должны быть все время.Функция out_degree() должна быть линейной по количеству выходных ребер.
Чтобы фактически выполнить эти требования, вам потребуется специальное хранилище выходных ребер для каждой вершины
Итак, давайте попробуем:
Mocking YourLibrary
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{}));