Boost图设计没有邻接表或邻接矩阵 [英] Boost graph designing without adjacency list or adjacency matrix
问题描述
有没有什么方法来创建图形结构,而不使用邻接列表或邻接矩阵在C ++ boost? (使用指向其邻居顶点的指针的顶点结构)
Is there any way to create a graph structure without using adjacency list or adjacency matrix in C++ boost? (a vertex structure using pointers which points to its neighbour vertices)
推荐答案
当然, traits,这意味着你基本上处理顶点和边缘,即使在你的代码中,他们被称为节点和链接。
It is possible, of course, provided your data has "traits" of a theoretical graph, meaning you essentially deal with "vertices" and "edges", even if in your code they are called, say, "nodes" and "links".
此结构称为BGL图适配器。这可能是一个有点具有挑战性的C ++运动,但。一般的想法是教BGL有关你的数据的很多细节:
This construct is called "BGL graph adapter". It can be a little challenging C++ exercise, though. The general idea is to teach BGL a lot of details about your data:
- 你的数据的C ++类型在你的想象图中意味着什么, / li>
- 如何迭代顶点和边。
所以你定义一个类,比如MyGraph,它通常是一个很轻的重量,然后通过提供BGL的模板专用化来定义其特征 graph_traits
:
So you define a class, say MyGraph, which is typically a very light-weight and just keeps few pointers to your data. Then you define its traits by providing template specialization of 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
{
};
};
}
之后,您实现了在图结构上提供访问和迭代器的全局函数,例如:
After that you implement global functions which provide access and iterator over your graph structure, for example:
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图概念中预定义的几十个这样的遍历函数。您必须至少提供与上面声明的 traversal_category
相关的那些。
There is about dozens of such traverse functions predefined in BGL graph concepts. You have to provide at least those which relevant for your traversal_category
declared above.
如果一切顺利,可以使用BGL算法直接使用您的数据,而不使用预定义的BGL图。
If everything is done right, you can use your data directly with BGL algorithms, without using one of predefined BGL graphs.
在BGL章节如何将现有图表转换为BGL
这篇关于Boost图设计没有邻接表或邻接矩阵的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!