...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

boost::betweenness_centrality_clustering — Graph clustering based on edge betweenness centrality.

template<typenameMutableGraph,typenameDone,typenameEdgeCentralityMap,typenameVertexIndexMap>voidbetweenness_centrality_clustering(MutableGraph & g, Done done, EdgeCentralityMap edge_centrality, VertexIndexMap vertex_index);template<typenameMutableGraph,typenameDone,typenameEdgeCentralityMap>voidbetweenness_centrality_clustering(MutableGraph & g, Done done, EdgeCentralityMap edge_centrality);template<typenameMutableGraph,typenameDone>voidbetweenness_centrality_clustering(MutableGraph & g, Done done);

This algorithm implements graph clustering based on edge
betweenness centrality. It is an iterative algorithm, where in each
step it computes the edge betweenness centrality (via brandes_betweenness_centrality) and
removes the edge with the maximum betweenness centrality. The
`done` function object determines
when the algorithm terminates (the edge found when the algorithm
terminates will not be removed).

The graph object on which the algorithm will be applied. The typeIN:Graphmust be a model of Vertex List Graph and Incidence Graph. When an edge centrality map is supplied, it must also model Edge List Graph and MutableGraph.

Python: The parameter is namedgraph.

The function object that indicates termination of the algorithm. It must be a ternary function object thats accepts the maximum centrality, the descriptor of the edge that will be removed, and the graphOUT/UTIL:g.

Python: Any callable Python object will suffice.

This property map is used to accumulate the betweenness centrality of each edge, and is a secondary form of output for the algorithm. The typeIN:EdgeCentralityMapmust be a model of Read/Write Property Map, with the graph's edge descriptor type as its key type. The value type of this property map should be the same as the value type of theCentralityMapproperty map.

Default:adummy_property_map, which requires no work to compute and returns no answer.

Python: The color map must be aedge_double_mapfor the graph.

Python default:graph.get_edge_double_map("centrality")

This maps each vertex to an integer in the range[0, num_vertices(g)). This is necessary for efficient updates of the heap data structure when an edge is relaxed. The typeVertexIndexMapmust be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.

Default:get(vertex_index, g). Note: if you use this default, make sure your graph has an internalvertex_indexproperty. For example,adjacenty_listwithVertexList=listSdoes not have an internalvertex_indexproperty.

Python: Unsupported parameter.

Copyright © 2004 | Douglas Gregor,
Indiana University (dgregor@cs.indiana.edu) Andrew Lumsdaine, Indiana University (lums@osl.iu.edu) |