1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> 2<!-- 3 Copyright (c) 2004 Trustees of Indiana University 4 5 Distributed under the Boost Software License, Version 1.0. 6 (See accompanying file LICENSE_1_0.txt or copy at 7 http://www.boost.org/LICENSE_1_0.txt) 8 --> 9<html> 10<head> 11<meta name="generator" content= 12"HTML Tidy for Mac OS X (vers 12 April 2005), see www.w3.org"> 13<meta http-equiv="Content-Type" content= 14"text/html; charset=us-ascii"> 15<title>Function betweenness_centrality_clustering</title> 16</head> 17<body> 18<div class="titlepage"></div> 19<div class="refnamediv"> 20 21<IMG SRC="../../../boost.png" 22 ALT="C++ Boost" width="277" height="86"> 23 24<h1><img src="figs/python.gif" alt="(Python)"/><span class="refentrytitle">Function 25betweenness_centrality_clustering</span></h1> 26<p>boost::betweenness_centrality_clustering — Graph 27clustering based on edge betweenness centrality.</p> 28</div> 29<h2 xmlns:rev= 30"http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" class= 31"refsynopsisdiv-title">Synopsis</h2> 32<div xmlns:rev= 33"http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" class= 34"refsynopsisdiv"> 35<pre class="synopsis"> 36<span class="bold"><b>template</b></span><<span class= 37"bold"><b>typename</b></span> MutableGraph, <span class= 38"bold"><b>typename</b></span> Done, <span class= 39"bold"><b>typename</b></span> EdgeCentralityMap, 40 <span class= 41"bold"><b>typename</b></span> VertexIndexMap> 42 <span class="type"><span class= 43"bold"><b>void</b></span></span> betweenness_centrality_clustering(MutableGraph & g, Done done, 44 EdgeCentralityMap edge_centrality, 45 VertexIndexMap vertex_index); 46<span class="bold"><b>template</b></span><<span class= 47"bold"><b>typename</b></span> MutableGraph, <span class= 48"bold"><b>typename</b></span> Done, <span class= 49"bold"><b>typename</b></span> EdgeCentralityMap> 50 <span class="type"><span class= 51"bold"><b>void</b></span></span> betweenness_centrality_clustering(MutableGraph & g, Done done, 52 EdgeCentralityMap edge_centrality); 53<span class="bold"><b>template</b></span><<span class= 54"bold"><b>typename</b></span> MutableGraph, <span class= 55"bold"><b>typename</b></span> Done> 56 <span class="type"><span class= 57"bold"><b>void</b></span></span> betweenness_centrality_clustering(MutableGraph & g, Done done); 58</pre></div> 59<div class="refsect1" lang="en"><a name="id822306" id= 60"id822306"></a> 61<h2>Description</h2> 62<p>This algorithm implements graph clustering based on edge 63betweenness centrality. It is an iterative algorithm, where in each 64step it computes the edge betweenness centrality (via <a href= 65"betweenness_centrality.html">brandes_betweenness_centrality</a>) and 66removes the edge with the maximum betweenness centrality. The 67<tt class="computeroutput">done</tt> function object determines 68when the algorithm terminates (the edge found when the algorithm 69terminates will not be removed).</p> 70 71<h2>Parameters</h2> 72IN: <tt>const Graph& g</tt> 73<blockquote> 74 The graph object on which the algorithm will be applied. The type 75 <tt>Graph</tt> must be a model of <a 76 href="VertexListGraph.html">Vertex List Graph</a> and <a 77 href="IncidenceGraph.html">Incidence Graph</a>. When an edge 78 centrality map is supplied, it must also model <a 79 href="EdgeListGraph.html">Edge List Graph</a> and <a 80 href="MutableGraph.html">MutableGraph</a>.<br> 81 82<b>Python</b>: The parameter is named <tt>graph</tt>. 83</blockquote> 84 85IN: <tt>Done done</tt> 86<blockquote> 87The function object that indicates termination of the algorithm. 88It must be a ternary function object thats accepts the maximum 89centrality, the descriptor of the edge that will be removed, and 90the graph <tt class="computeroutput">g</tt>.<br> 91<b>Python</b>: Any callable Python object will suffice. 92</blockquote> 93 94OUT/UTIL: <tt>EdgeCentralityMap edge_centrality_map</tt> 95<blockquote> 96 This property map is used to accumulate the betweenness centrality 97 of each edge, and is a secondary form of output for the 98 algorithm. The type <tt>EdgeCentralityMap</tt> must be a model of <a 99 href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write 100 Property Map</a>, with the graph's edge descriptor type as its key 101 type. The value type of this property map should be the same as the 102 value type of the <tt>CentralityMap</tt> property map.<br> 103 104 <b>Default:</b> a <tt>dummy_property_map</tt>, which requires no 105 work to compute and returns no answer.<br> 106 <b>Python</b>: The color map must be a <tt>edge_double_map</tt> for 107 the graph.<br> 108 <b>Python default</b>: <tt>graph.get_edge_double_map("centrality")</tt> 109</blockquote> 110 111IN: <tt>VertexIndexMap vertex_index</tt> 112<blockquote> 113 This maps each vertex to an integer in the range <tt>[0, 114 num_vertices(g))</tt>. This is necessary for efficient updates of the 115 heap data structure when an edge is relaxed. The type 116 <tt>VertexIndexMap</tt> must be a model of 117 <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. The value type of the map must be an 118 integer type. The vertex descriptor type of the graph needs to be 119 usable as the key type of the map.<br> 120 <b>Default:</b> <tt>get(vertex_index, g)</tt>. 121 Note: if you use this default, make sure your graph has 122 an internal <tt>vertex_index</tt> property. For example, 123 <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does 124 not have an internal <tt>vertex_index</tt> property.<br> 125 <b>Python</b>: Unsupported parameter. 126</blockquote> 127 128<table xmlns:rev= 129"http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width= 130"100%"> 131<tr> 132<td align="left"></td> 133<td align="right"></td> 134</tr> 135</table> 136<h3>Where Defined</h3> 137<<a href= 138"../../../boost/graph/bc_clustering.hpp">boost/graph/bc_clustering.hpp</a>> 139<hr> 140<table> 141<tr valign="top"> 142<td nowrap>Copyright © 2004</td> 143<td><a href="http://www.boost.org/people/doug_gregor.html">Douglas Gregor</a>, 144Indiana University (dgregor@cs.indiana.edu)<br> 145<a href="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</a>, Indiana 146University (<a href= 147"mailto:lums@osl.iu.edu">lums@osl.iu.edu</a>)</td> 148</tr> 149</table> 150</body> 151</html> 152
