无需邻接表或邻接矩阵的Boost图设计

Question

在C++ Boost中，是否有不使用邻接表或邻接矩阵创建图结构的方法？（例如使用指向其相邻顶点的指针的顶点结构）

- Lahiru

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); 

and

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

在BGL图形概念中，预定义了大约数十个这样的遍历函数。您必须至少提供那些与上面声明的traversal_category相关的函数。

如果一切都做得正确，您可以直接使用BGL算法处理数据，而不使用预定义的BGL图形之一。

BGL章节如何将现有图形转换为BGL对此进行了很好的解释。

- Michael Simbirsky