How to calculate edge betweenness with BGL

Question

Based off of this post, I was able to compile this code.

Graph_type newGraph(edge_arrayNoDuplicates, edge_arrayNoDuplicates + numEdges, transmission_delay, numVertices);

boost::shared_array_property_map<double, boost::property_map<Graph_type, vertex_index_t>::const_type>
            edge_centrality_map(num_vertices(newGraph), get(boost::vertex_index, newGraph));
    brandes_betweenness_centrality(newGraph, edge_centrality_map);

I'm wanting to get the edge centrality map rather than the centrality map, and I think I implemented that correctly but I'm not sure. What I am hoping to get from this is to be able to use the returned value from calling brandes_betweenness_centrality(newGraph, edge_centrality_map) and find the edge with the highest edge betweenness, and then delete that edge. I can't figure out how to access the values returned from calling the brandes algorithm. Does it even return values? If not, how do I access the edge betweenness?

Answer 1

Okay, I just posted the simplified graph reading code.

In your current question I see the new edge_arrayNoDuplicates variable name, which suggests that you went to some extents to remove duplicate edges.

As a pro-tip let me suggest that you can have the same effect without any manual work by choosing setS instead of vecS for the edge container selector:

using Graph_type =
    boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS,
                          boost::no_property,
                          boost::property<boost::edge_weight_t, float>>;

That's two letters changed, and done. Actually, for performance you may still want to keep vecS, but you should probably see what your profiler tells you. If it's fast enough, I wouldn't bother.

---

Then the code for the betweenness algorithm had some problems.

boost::shared_array_property_map<
    double,
    boost::property_map<Graph_type, boost::vertex_index_t>::const_type>
    edge_centrality_map(num_vertices(g), get(boost::vertex_index, g));

First, let's be modern, avoiding duplication of the type information:

auto edge_centrality_map = boost::make_shared_array_property_map(
    num_vertices(g), 1., get(boost::vertex_index, g));

Next, this has the problem that it uses the vertex index, where you need an edge index, at best. But let's look further first:

brandes_betweenness_centrality(g, edge_centrality_map);

You pass edge_centrality_map as the single map argument. Checking the docs tells me that the only 2-argument overload is

template<typename Graph, typename CentralityMap>
void
brandes_betweenness_centrality(const Graph& g, CentralityMap centrality_map);

So, no matter how you name the variable, it will not be the EdgeCentralityMap, but still the (Vertex)CentralityMap. Oops. That's probably why you had the vertex_index there, to make it compile at all.

I'd suggest using a regular map rather than the shared array property map:

std::map<Graph_type::edge_descriptor, double> edge_centralities;

This way you don't have to use indirection using an edge_index (which you also don't have yet). You can directly adapt this as a property-map:

auto ecm = boost::make_assoc_property_map(edge_centralities);

Which you can then use in the algorithm. To avoid having to supply some kind of centrality map, we can use the named-parameters overload:

brandes_betweenness_centrality(g, boost::edge_centrality_map(ecm));

To dump out the result:

for (auto edge : boost::make_iterator_range(edges(g))) {
    auto s = invmap.at(source(edge, g));
    auto t = invmap.at(target(edge, g));
    std::cout << "Betweenness for " << s << "-" << t << " "
              << edge_centralities.at(edge) << "\n";
}

Live Demo

Live On Coliru (data source: put_data_here.txt)

The sample uses a larger graph and displays the top-10 edges with highest centrality:

int main() {
    Mappings mappings;
    Graph_type g = readInGraph("put_data_here.txt", mappings);

    using ECMap = std::map<Graph_type::edge_descriptor, double>;
    using ECEntry = ECMap::value_type;
    ECMap ecm;
    brandes_betweenness_centrality(
        g, boost::edge_centrality_map(boost::make_assoc_property_map(ecm)));

    std::vector<std::reference_wrapper<ECEntry>> ranking(ecm.begin(), ecm.end());

    {
        // top-n
        auto n = std::min(10ul, ranking.size());
        auto first = ranking.begin(), middle = first + n, last = ranking.end();
        std::partial_sort(
                first, middle, last,
                [](ECEntry const& a, ECEntry const& b) { return a.second > b.second; });

        ranking.erase(middle, last);
    }

    auto& edgenames = mappings.right;

    for (ECEntry const& entry : ranking) {
        auto [edge, centrality] = entry;
        auto s = edgenames.at(source(edge, g));
        auto t = edgenames.at(target(edge, g));
        std::cout << s << "-" << t << " centrality " << centrality << "\n";
    }
}

Prints

J-Q centrality 35.1
J-H centrality 20.5905
N-H centrality 18.0905
C-P centrality 16.1
H-B centrality 14.5571
P-S centrality 13.6024
J-C centrality 13.3833
H-E centrality 12.8905
Q-R centrality 12.6
L-G centrality 12.5333