Boost Graph Library中是否存在通过vertex_index属性访问顶点的内置方法？

Unfortunately, the Boost Graph Library (BGL) doesn’t provide a built-in method to directly look up a vertex by its vertex_index property value out of the box. The vertex_index property is primarily designed to map vertex descriptors to unique integer indices (like how you use indices[x]), not the reverse.

To solve this, you’ll need to maintain your own reverse mapping that links your custom vertex_index values to their corresponding VertexDescriptor objects. Here’s how to implement this with your existing code:

Step-by-Step Solution #

1. Add a reverse lookup map to store the association between your unique index values and vertex descriptors.
2. Update the map whenever you add a vertex to ensure it stays in sync with your graph.
3. Use the map to look up vertices by index whenever you need to access them.

Modified Code Example #

#include <boost/graph/adjacency_list.hpp>
#include <unordered_map>
#include <iostream>

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);
    
    // Create a reverse lookup map: index -> vertex descriptor
    std::unordered_map<int, VertexDescriptor> index_to_vertex;

    // Add vertices and populate the reverse map
    auto v1 = boost::add_vertex(DirectedGraph::vertex_property_type{123123}, g);
    index_to_vertex[123123] = v1;

    auto v2 = boost::add_vertex(DirectedGraph::vertex_property_type{451345}, g);
    index_to_vertex[451345] = v2;

    // Now you can access vertices by their custom index
    int target_index = 123123;
    if (index_to_vertex.contains(target_index)) {
        VertexDescriptor v = index_to_vertex[target_index];
        // Verify the index matches
        std::cout << "Vertex descriptor for index " << target_index << " has value: " << indices[v] << std::endl;
    } else {
        std::cout << "No vertex found with index " << target_index << std::endl;
    }

    return 0;
}

Key Notes #

• Syncing with graph changes: If you ever remove vertices from your graph, make sure to erase the corresponding entries from index_to_vertex to avoid invalid descriptors.
• Performance: Using an unordered_map gives you average O(1) lookup time, which is efficient for most use cases. If you need ordered lookups, you can use a std::map instead (with O(log n) time).
• Why no built-in support?: BGL avoids adding this by default because reverse lookup isn’t a universal requirement. Letting users maintain their own maps keeps the library lightweight and flexible, avoiding unnecessary overhead for those who don’t need this functionality.

内容的提问来源于stack exchange，提问作者Yamahari