Boost图形库：获取特定顶点的顺序号？

Question

Boost 图形库有一个函数vertex_descriptor vertex(vertices_size_type n, const adjacency_list& g)，第n 个returnsvertex_descriptor。这个函数的反函数是什么？即获取给定的订单号vertex_descriptor?

Answer 1

一般来说，没有有效的方法，因为它取决于顶点的存储方式。

如果您不关心性能，您可以创建这样的函数：

template <typename Graph>
size_t index_of(Graph const& g, typename Graph::vertex_descriptor const& vd)
{
    auto vs = vertices(g);
    auto lookup = std::find(vs.first, vs.second, vd);
    assert(lookup != vs.second);

    return std::distance(vs.first, lookup);
}

在下面的 "comprehensive" 测试中，它被证明适用于 adjacency_list<> 图表类型的大量不同配置。

上述性能在 vecS 存储下应该是合理的，但否则可能会很糟糕。在这种情况下，最好提供您自己的 vertex_index 映射，因为许多其他算法确实需要（例如 write_graphviz）：

how provide a vertex_index property for my graph

测试程序

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/random.hpp>
#include <boost/random.hpp>

using namespace boost;

template <typename Graph>
size_t index_of(Graph const& g, typename Graph::vertex_descriptor const& vd)
{
    auto vs = vertices(g);
    auto lookup = std::find(vs.first, vs.second, vd);
    assert(lookup != vs.second);

    return std::distance(vs.first, lookup);
}

static mt19937 rnd(time(0));

template <typename Graph, size_t num_vertices = 200, size_t num_edges = 300>
void test_index_of()
{
    Graph g;
    generate_random_graph(g, 100, 300, rnd);

    for(auto const& v : make_iterator_range(vertices(g))) {
        assert(v == boost::vertex(index_of(g, v), g));
    }
}

int main()
{
    test_index_of<adjacency_list<vecS,  vecS,  undirectedS> >();
    test_index_of<adjacency_list<vecS,  setS,  undirectedS> >();
    test_index_of<adjacency_list<vecS,  listS, undirectedS> >();
    test_index_of<adjacency_list<setS,  vecS,  undirectedS> >();
    test_index_of<adjacency_list<setS,  setS,  undirectedS> >();
    test_index_of<adjacency_list<setS,  listS, undirectedS> >();
    test_index_of<adjacency_list<listS, vecS,  undirectedS> >();
    test_index_of<adjacency_list<listS, setS,  undirectedS> >();
    test_index_of<adjacency_list<listS, listS, undirectedS> >();
    test_index_of<adjacency_list<vecS,  vecS,  directedS>   >();
    test_index_of<adjacency_list<vecS,  setS,  directedS>   >();
    test_index_of<adjacency_list<vecS,  listS, directedS>   >();
    test_index_of<adjacency_list<setS,  vecS,  directedS>   >();
    test_index_of<adjacency_list<setS,  setS,  directedS>   >();
    test_index_of<adjacency_list<setS,  listS, directedS>   >();
    test_index_of<adjacency_list<listS, vecS,  directedS>   >();
    test_index_of<adjacency_list<listS, setS,  directedS>   >();
    test_index_of<adjacency_list<listS, listS, directedS>   >();
}

Boost图形库：获取特定顶点的顺序号？

Boost graph library: Get the order number of a specific vertex?

boost

测试程序