Re: [Boost-users] [BGL] Correct idiom for working with vertices.

Subject: Re: [Boost-users] [BGL] Correct idiom for working with vertices.
From: alex (alexhighviz_at_[hidden])
Date: 2015-11-04 12:45:01

>-----Original Message-----
>From: Boost-users [mailto:boost-users-bounces_at_[hidden]] On Behalf Of
>Matthew Markland
>Sent: 04 November 2015 15:43
>To: boost-users_at_[hidden]
>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<my_graph_type>::vertex_descriptor;
using edge_descriptor = boost::graph_traits<my_graph_type>::edge_descriptor;
using lookup_type = std::map<my_index_type, vertex_descriptor>;
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<edge_descriptor, bool> 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);
}