提升图形设计不邻接表或者邻接矩阵 [英] Boost graph designing without adjacency list or adjacency matrix

问题描述

有什么方法来创建，而不需要使用C相邻列表或邻接矩阵++提高图形结构？ （使用指向它的邻居顶点指向顶点结构）

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)

推荐答案

这是可能的，当然前提是你的数据有一个理论图的特质，这意味着你基本上是应对顶点和边，连如果在你的code，他们被称为，说，节点和链接。

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:

1. 在假想图什么C ++数据类型的平均值和


2. 如何在你的顶点和边迭代。

所以你定义一个类，说为MyGraph，这通常是一个非常重量轻，只是不断几个指针您的数据。

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 )

有大约几十个这样的横向职能$ P $中的 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算法使用您的数据，而无需使用$ P $之一pdefined BGL图。

If everything is done right, you can use your data directly with BGL algorithms, without using one of predefined BGL graphs.

关于这个问题的一个很好的解释在BGL章的如何将现有的图表来BGL

A good explanation on the subject is given in BGL chapter How to Convert Existing Graphs to BGL

这篇关于提升图形设计不邻接表或者邻接矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！