无需邻接列表或邻接矩阵的Boost图设计[关闭]

有没有办法在 C++ boost 中不使用邻接列表或邻接矩阵来创建图结构？ （使用指向其邻居顶点的指针的顶点结构）

当然，只要您的数据具有理论图的“特征”，这意味着您本质上处理“顶点”和“边”，即使在您的代码中它们被称为“节点”和“链接” 。

该构造称为“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 图概念 http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/graph_concepts.html。您必须至少提供与您相关的内容traversal_category上面声明的。

如果一切正确，您可以直接通过 BGL 算法使用数据，而无需使用预定义的 BGL 图表之一。

BGL 章节对此主题给出了很好的解释如何将现有图形转换为 BGL http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/leda_conversion.html