c++ - 没有邻接表或邻接矩阵的Boost图形设计

Closed. This question does not meet Stack Overflow guidelines。它当前不接受答案。












想改善这个问题吗？更新问题，以便将其作为on-topic用于堆栈溢出。

6年前关闭。



Improve this question




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

最佳答案

当然，只要您的数据具有理论图的“特征”，就意味着您实际上可以处理“顶点”和“边缘”，即使在您的代码中称它们为“节点”和“链接”也是可能的。

该构造称为“BGL图形适配器”。但是，这可能是一个具有挑战性的C++练习。总体思路是教BGL有关您数据的许多详细信息:

虚构图和

中数据的C++类型意味着什么

如何遍历顶点和边缘。

因此，您定义了一个类，例如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中对此主题做了很好的解释

关于c++ - 没有邻接表或邻接矩阵的Boost图形设计，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20418753/