Графическое построение графика без смежности или матрицы смежности

Question

Есть ли способ создать структуру графа без использования списка смежности или матрицы смежности в C++ boost? (структура вершин с помощью указателей, указывающих на ее соседние вершины)

Answer 1

Возможно, конечно, если ваши данные имеют «черты» теоретического графика, что означает, что вы в основном имеете дело с «вершинами» и «ребрами», даже если в вашем коде они вызываются, скажем, «узлы» и «ссылки».

Эта конструкция называется «BGL-адаптером графа». Однако это может быть немного сложным упражнением на C++. Общая идея заключается в том, чтобы научить BGL много подробностей о ваших данных:

1. , что C++ типы данных означает в вашем воображаемом графике и
2. как перебираются ваших вершин и ребер.

Итак, вы определяете класс, скажем, MyGraph, который, как правило, очень легкий и просто содержит несколько указателей на ваши данные. Затем вы определяете свои черты, предоставляя специализации шаблона из BGL graph_traits:

#include <boost/graph/graph_traits.hpp> 
namespace boost { 
    template <> 
    struct graph_traits<MyGraph> 
{ 
    typedef ... vertex_descriptor; //what plays a role of vertex in your data 
    typedef ... edge_descriptor; //what plays a role of edge in your data 

    //other typedefs from graph_traits like edge_iterator, out_edge_iterator, etc. 

    //plus, you specify "categories" of your graph explaining what types of traversal are 
    //available (more the better) 
    struct traversal_category 
     : public virtual boost::vertex_list_graph_tag 
     , public virtual boost::adjacency_graph_tag 
     , public virtual boost::bidirectional_graph_tag //means we provide access to in_edges 
                 //and to out_edges of a given vertex 
    { 
    };  
}; 
} 

После этого вы реализуете глобальные функции, которые обеспечивают доступ и итератор над структурой графа, например:

MyGraph::vertex_descriptor 
source(MyGraph::edge_descriptor e, const MyGraph & g); 

и

std::pair<MyGraph::out_edge_iterator, 
      MyGraph::out_edge_iterator> 
out_edges(MyGraph::::vertex_descriptor vd, const MyGraph & g) 

Существует около десятков таких функций перемещения, предопределенных в BGL graph concepts. Вы должны предоставить, по крайней мере, те, которые относятся к вашему объявлению traversal_category.

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

Хорошее объяснение по этому вопросу приведено в главе BGL How to Convert Existing Graphs to BGL