如何使用 BGL 计算边缘介数

Question

基于 this post，我能够编译这段代码。

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);

我想要获取边缘中心图而不是中心图，我认为我正确地实现了它，但我不确定。我希望从中得到的是能够使用调用 brandes_betweenness_centrality(newGraph, edge_centrality_map) 的 returned 值并找到具有最高边缘介数的边缘，然后删除该边缘。我不知道如何通过调用 brandes 算法访问值 returned。它甚至 return 值吗？如果没有，我如何访问边介数？

Answer 1

好吧，我只是。

在您当前的问题中，我看到了新的 edge_arrayNoDuplicates 变量名称，这表明您在一定程度上删除了重复的边。

作为专业提示，我建议您在没有任何手动工作的情况下通过选择 setS 而不是 vecS 来获得相同的效果边缘容器选择器：

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

两个字母改完了。实际上，为了性能，您可能仍想保留 vecS，但您可能应该看看分析器告诉您的内容。够快的话，我就不介意了。

然后介数算法的代码有一些问题。

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));

首先，让我们保持现代，避免重复类型信息：

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

接下来，这有一个问题，它使用顶点索引，而你最多需要一个边缘索引。但让我们先看得更远：

brandes_betweenness_centrality(g, edge_centrality_map);

您将 edge_centrality_map 作为单个地图参数传递。检查 the docs 告诉我唯一的 2 参数重载是

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

因此，无论您如何命名变量，它都不会是EdgeCentralityMap，而是(Vertex)CentralityMap。哎呀。这可能就是为什么你有 vertex_index 在那里，让它编译。

我建议使用常规映射而不是共享数组属性映射：

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

这样您就不必使用 edge_index（您还没有）来使用间接寻址。您可以直接将其调整为属性-map:

auto ecm = boost::make_assoc_property_map(edge_centralities);

然后您可以在算法中使用它。为了避免必须提供某种中心图，我们可以使用命名参数重载：

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

转出结果：

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 On Coliru (data source: put_data_here.txt)

示例使用更大的图并显示中心性最高的前 10 条边：

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";
    }
}

版画

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

如何使用 BGL 计算边缘介数

How to calculate edge betweenness with BGL

c++

boost

boost-graph

现场演示