CODEWITHSUNDEEP
c++boostboost-graph
ArKan
ArKan

Reputation: 485

How to calculate the betweenness centrality with weights

I'm trying to calculate the betweenness centrality of a city street network, using the Edge length property as weight, but it doesn't seem to work.

When I run without weights it gives the following results:

min: 0
mean: -nan(ind)
max: inf
stddev: -nan(ind)

and with weights:

min: 0
mean: 0
max: 0
stddev: 0

Any help would be gratelly apreciated

My implementation (in a smaller graph has worked):

struct TravelEdge {
    float length = 0.0f;
};

struct TravelNode {
    float xcoord = 0.0f;
    float ycoord = 0.0f;
    std::string osmid;
};

typedef boost::adjacency_list<
    boost::vecS, boost::vecS, boost::directedS,
    TravelNode, TravelEdge
> GraphMap;
typedef boost::property_map<GraphMap, boost::vertex_index_t>::type VertexIndexMap;

int main(){
  GraphMap graph;

  // ... loads from graphml file

  std::vector<double> centrality_vector(boost::num_vertices(graph), 0.0);
  VertexIndexMap v_index = get(boost::vertex_index, graph);
  boost::iterator_property_map<std::vector<double>::iterator, VertexIndexMap>
      vertex_property_map = make_iterator_property_map(centrality_vector.begin(), v_index);

  auto weight_map = make_transform_value_property_map([](TravelEdge& e) { return e.length; }, get(boost::edge_bundle, graph));

  // without weights
  //boost::brandes_betweenness_centrality(graph, vertex_property_map);
  // with weights
  boost::brandes_betweenness_centrality(graph, boost::predecessor_map(vertex_property_map).weight_map(weight_map));

  boost::accumulators::accumulator_set<
      double,
      boost::accumulators::features<
      boost::accumulators::tag::min,
      boost::accumulators::tag::max,
      boost::accumulators::tag::mean,
      boost::accumulators::tag::variance
      >
  > acc;

  std::for_each(centrality_vector.begin(), centrality_vector.end(), std::ref(acc));

  return 0;
}

Upvotes: 1

Views: 334

Answers (1)

ArKan
ArKan

Reputation: 485

Well, that's awkward, turns out the code is right, my graph was somehow wrong, I regenerated it and it has worked.

Edit 1

After seeing the time and amount of memory it takes to load the graph, I was able to find the problem, after I made some operations on the nodes, I was inserting them in the same graph, instead of a new one.

Edit 2

The way the betweenness with weights function is invoked is wrong, the right way would be:

boost::brandes_betweenness_centrality(
    graph,
    centrality_map(vertex_property_map)
    .vertex_index_map(v_index)
    .weight_map(get(&TravelEdge::travel_time, graph))
);

I hope someone finds this useful 😊

Upvotes: 1

Related Questions