-----Original Message----- From: Boost-users [mailto:boost-users-bounces@lists.boost.org] On Behalf Of Matthew Markland Sent: 04 November 2015 15:43 To: boost-users@lists.boost.org Subject: [Boost-users] [BGL] Correct idiom for working with vertices.

All:

I'm building a graph on which I will be running betweenness centrality. This graph consists of a number of edges represented as pairs. For example

1 20 15 10

would represent an edge from 1<->20 and one from 15<->10. These are bidirectional.

My initial code created a property_map for the centrality results and then walked through that map using num_vertices(g) as the limit for the for-loop. What I've realized now, though, is that when BGL generates the values for num_vertices (and the iterators for vertices also), it "fills in" the gaps. So, in the graph above there would be 20 vertices that would be interated through even though most of those have no relation to edges in the graph.

So, I'm wondering what the usual idiom is in this situation. Should I instead iterator over edges and pull information from the source and target vertices of the edges?

I am not sure this is the usual idiom, but what I ended up doing is creating a map from my own numbering system to the graph's vertex descriptors (and also make a vertex property map for the reverse lookup). using vertex_descriptor = boost::graph_traits::vertex_descriptor; using edge_descriptor = boost::graph_traits::edge_descriptor; using lookup_type = std::map; using lookup_iter = lookup_type::iterator; my_graph_type m_graph; lookup_type m_lookup; vertex_descriptor find_or_add_vertex(my_index_type index) { lookup_iter i = m_lookup.find(index); if(i != m_lookup.end()) { return i->second; } else { vertex_descriptor v= add_vertex(m_graph); m_lookup.insert(std::make_pair(index, v)); return v; } } std::pair add_edge(my_index_type from, my_index_type to) { return boost::add_edge(find_or_add_vertex(from), find_or_add_vertex(to), m_graph); }