c++ - 可以在 Boost Graph Library 中即时计算边吗？

Question

在我的应用程序中，我有某种图形，其中每个节点/顶点可以相互连接，但实际连接是确定的在运行时。

当然，通过迭代实现这很简单在所有现有顶点上并将它们连接到最后一个我已经添加到图中并在运行时使用过滤图决定连接是否仍然存在。

目的是使用BFS或DFS或BGL提供的其他算法。

是否有任何其他方法可以更有效地完成该任务？通过示例:在初始化时添加所有(!)顶点并具有一些一种在运行时检查边缘的回调？

这就是我试图解决它的方法，但那个不起作用:

#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/graph_utility.hpp>
struct VD { };
struct ED { };

struct Graph : boost::adjacency_matrix<boost::directedS, VD, ED>
{
    Graph() : boost::adjacency_matrix<boost::directedS, VD, ED>(4) { }
    //=================================================================
    // Functions required by the AdjacencyMatrix concept
    template <typename D, typename VP, typename EP, typename GP, typename A>
    std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, bool>
    edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
        typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
        const adjacency_matrix<D,VP,EP,GP,A>& g)
    {
        // Connect vertex 1 and 2
        bool exists = (u == 1 && v == 2);

        typename boost::adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor
            e(exists, u, v, boost::detail::get_edge_property(g.get_edge(u,v)));

        return std::make_pair(e, exists);
    }
};

int main() {
    Graph g;
    print_graph(g);

    std::vector<int> component(num_vertices(g));
    int num = boost::connected_components(g, &component[0]);
}

如有任何指点，我们将不胜感激!

Answer 1

来自 BGL concepts :

The heart of the Boost Graph Library (BGL) is the interface, or concepts (in the parlance of generic programming), that define how a graph can be examined and manipulated in a data-structure neutral fashion. In fact, the BGL interface need not even be implemented using a data-structure, as for some problems it is easier or more efficient to define a graph implicitly based on some functions.

没有标准模型实现，但文档在 Chapter 19: Graph Adaptors 中包含一个示例

它显示了 grid_graph 适配器，它可能与您的用例非常匹配。如果没有，它应该会给你关于如何根据概念要求创建隐式图模型的好主意。

[2]: