
Boost Users : 
Subject: Re: [Boostusers] [BGL] Correct idiom for working with vertices.
From: alex (alexhighviz_at_[hidden])
Date: 20151104 12:45:01
>Original Message
>From: Boostusers [mailto:boostusersbounces_at_[hidden]] On Behalf Of
>Matthew Markland
>Sent: 04 November 2015 15:43
>To: boostusers_at_[hidden]
>Subject: [Boostusers] [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
forloop.
>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);
}
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net