通过vertex_index属性访问顶点？

Question

在BGL中是否存在通过其vertex_index属性访问顶点的内置方式？

using VertexProperties = boost::property<boost::vertex_index_t, int>;
using DirectedGraph = boost::adjacency_list<
   boost::listS, 
   boost::vecS, 
   boost::directedS, 
   VertexProperties,
   boost::no_property>;
using VertexDescriptor = boost::graph_traits<DirectedGraph>::vertex_descriptor;
using EdgeDescriptor = boost::graph_traits<DirectedGraph>::edge_descriptor;

int main()
{
    DirectedGraph g;
    auto indices = boost::get(boost::vertex_index, g);

    boost::add_vertex(DirectedGraph::vertex_property_type{123123}, g); // unique index
    boost::add_vertex(DirectedGraph::vertex_property_type{451345}, g); // unique index

    // how do I access the vertex with my unique index?

    // I only see the way from vertex->vertex_index via the property map
    indices[x];

}

Answer 1

到目前为止，这个领域中最友好的解决方案是使用内部名称属性。这是boost::adjacency_list的一个混合特性(在maybe_named_graph中实现)。

此外，为此您的方法“重新定位”vertex_index_t可能是错误的:顶点索引是一个库“契约”，它假定它将所有顶点vertices(g)映射到一个连续的积分域[0, num_vertices(g))。您的ID不满足这些属性，因此当您在图形上调用BGL算法时，它将导致未指定的，而且很可能是未定义行为。

总之，我会将属性重新定义为您自己的包：

struct VertexProps {
    int my_id;
    VertexProps(int id) : my_id(std::move(id)) {}
};

using Graph = boost::adjacency_list<boost::listS, boost::listS, boost::directedS, VertexProps,
                                    boost::no_property>;
using V     = Graph::vertex_descriptor;
using E     = Graph::edge_descriptor;

现在您需要专门化一些特性来告诉maybe_named_graph，VertexProps的某些部分是您的顶点名称：

template <> struct boost::graph::internal_vertex_name<VertexProps> {
    struct type {
        using result_type = int;
        int const& operator()(VertexProps const& vp) const { return vp.my_id; }
    };
};

template <> struct boost::graph::internal_vertex_constructor<VertexProps> {
    struct type {
        auto operator()(int const& value) const { return VertexProps{value}; }
    };
};

现在您可以按名称添加顶点：

V a = add_vertex(123123, g); // unique index
V b = add_vertex(451345, g); // unique index

但是，与其使用a或b，您还可以继续在后续操作中使用名称：

add_edge(123123, 451345, g);

可以显式地从属性中获取顶点描述符：

V va = *g.vertex_by_property(123123);
V vb = *g.vertex_by_property(451345);

作为一个用户友好的惊喜，您甚至不需要提前创建顶点：

add_edge(234234, 562456, g);

会神奇地添加两个新的，命名的顶点。

现场演示

住在Coliru

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

struct VertexProps {
    int my_id;
    VertexProps(int id) : my_id(std::move(id)) {}
};

template <> struct boost::graph::internal_vertex_name<VertexProps> {
    struct type {
        using result_type = int;
        int const& operator()(VertexProps const& vp) const { return vp.my_id; }
    };
};

template <> struct boost::graph::internal_vertex_constructor<VertexProps> {
    struct type {
        auto operator()(int const& value) const { return VertexProps{value}; }
    };
};

using Graph = boost::adjacency_list<boost::listS, boost::listS, boost::directedS, VertexProps,
                                    boost::no_property>;
using V     = Graph::vertex_descriptor;
using E     = Graph::edge_descriptor;

int main() {
    Graph g;
    print_graph(g, get(&VertexProps::my_id, g), std::cout << "\n --- Empty:\n");
    auto my_id = get(&VertexProps::my_id, g);

    V a = add_vertex(123123, g); // unique index
    V b = add_vertex(451345, g); // unique index
    print_graph(g, my_id, std::cout << "\n --- Vertices:\n");

    std::cout << g[a].my_id << std::endl;
    std::cout << g[b].my_id << std::endl;

    add_edge(123123, 451345, g);
    print_graph(g, my_id, std::cout << "\n --- Edge:\n");

    V va = *g.vertex_by_property(123123);
    V vb = *g.vertex_by_property(451345);
    add_edge(vb, va, g);
    print_graph(g, my_id, std::cout << "\n --- Edges:\n");

    add_edge(234234, 562456, g);
    print_graph(g, my_id, std::cout << "\n --- Magically added:\n");
}

打印

 --- Empty:

 --- Vertices:
123123 --> 
451345 --> 
123123
451345

 --- Edge:
123123 --> 451345 
451345 --> 

 --- Edges:
123123 --> 451345 
451345 --> 123123 

 --- Magically added:
123123 --> 451345 
451345 --> 123123 
562456 --> 
234234 --> 562456 

更多和警告

围绕这一点有许多有趣的边缘案例。你可以在这里读到更多关于他们的信息：

如何在命名图上使用boost图算法？