152 lines
6.1 KiB
HTML
152 lines
6.1 KiB
HTML
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
|
|
<!--
|
|
Copyright (c) 2004 Trustees of Indiana University
|
|
|
|
Distributed under the Boost Software License, Version 1.0.
|
|
(See accompanying file LICENSE_1_0.txt or copy at
|
|
http://www.boost.org/LICENSE_1_0.txt)
|
|
-->
|
|
<html>
|
|
<head>
|
|
<meta name="generator" content=
|
|
"HTML Tidy for Mac OS X (vers 12 April 2005), see www.w3.org">
|
|
<meta http-equiv="Content-Type" content=
|
|
"text/html; charset=us-ascii">
|
|
<title>Function betweenness_centrality_clustering</title>
|
|
</head>
|
|
<body>
|
|
<div class="titlepage"></div>
|
|
<div class="refnamediv">
|
|
|
|
<IMG SRC="../../../boost.png"
|
|
ALT="C++ Boost" width="277" height="86">
|
|
|
|
<h1><img src="figs/python.gif" alt="(Python)"/><span class="refentrytitle">Function
|
|
betweenness_centrality_clustering</span></h1>
|
|
<p>boost::betweenness_centrality_clustering — Graph
|
|
clustering based on edge betweenness centrality.</p>
|
|
</div>
|
|
<h2 xmlns:rev=
|
|
"http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" class=
|
|
"refsynopsisdiv-title">Synopsis</h2>
|
|
<div xmlns:rev=
|
|
"http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" class=
|
|
"refsynopsisdiv">
|
|
<pre class="synopsis">
|
|
<span class="bold"><b>template</b></span><<span class=
|
|
"bold"><b>typename</b></span> MutableGraph, <span class=
|
|
"bold"><b>typename</b></span> Done, <span class=
|
|
"bold"><b>typename</b></span> EdgeCentralityMap,
|
|
<span class=
|
|
"bold"><b>typename</b></span> VertexIndexMap>
|
|
<span class="type"><span class=
|
|
"bold"><b>void</b></span></span> betweenness_centrality_clustering(MutableGraph & g, Done done,
|
|
EdgeCentralityMap edge_centrality,
|
|
VertexIndexMap vertex_index);
|
|
<span class="bold"><b>template</b></span><<span class=
|
|
"bold"><b>typename</b></span> MutableGraph, <span class=
|
|
"bold"><b>typename</b></span> Done, <span class=
|
|
"bold"><b>typename</b></span> EdgeCentralityMap>
|
|
<span class="type"><span class=
|
|
"bold"><b>void</b></span></span> betweenness_centrality_clustering(MutableGraph & g, Done done,
|
|
EdgeCentralityMap edge_centrality);
|
|
<span class="bold"><b>template</b></span><<span class=
|
|
"bold"><b>typename</b></span> MutableGraph, <span class=
|
|
"bold"><b>typename</b></span> Done>
|
|
<span class="type"><span class=
|
|
"bold"><b>void</b></span></span> betweenness_centrality_clustering(MutableGraph & g, Done done);
|
|
</pre></div>
|
|
<div class="refsect1" lang="en"><a name="id822306" id=
|
|
"id822306"></a>
|
|
<h2>Description</h2>
|
|
<p>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 <a href=
|
|
"betweenness_centrality.html">brandes_betweenness_centrality</a>) and
|
|
removes the edge with the maximum betweenness centrality. The
|
|
<tt class="computeroutput">done</tt> function object determines
|
|
when the algorithm terminates (the edge found when the algorithm
|
|
terminates will not be removed).</p>
|
|
|
|
<h2>Parameters</h2>
|
|
IN: <tt>const Graph& g</tt>
|
|
<blockquote>
|
|
The graph object on which the algorithm will be applied. The type
|
|
<tt>Graph</tt> must be a model of <a
|
|
href="VertexListGraph.html">Vertex List Graph</a> and <a
|
|
href="IncidenceGraph.html">Incidence Graph</a>. When an edge
|
|
centrality map is supplied, it must also model <a
|
|
href="EdgeListGraph.html">Edge List Graph</a> and <a
|
|
href="MutableGraph.html">MutableGraph</a>.<br>
|
|
|
|
<b>Python</b>: The parameter is named <tt>graph</tt>.
|
|
</blockquote>
|
|
|
|
IN: <tt>Done done</tt>
|
|
<blockquote>
|
|
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 graph <tt class="computeroutput">g</tt>.<br>
|
|
<b>Python</b>: Any callable Python object will suffice.
|
|
</blockquote>
|
|
|
|
OUT/UTIL: <tt>EdgeCentralityMap edge_centrality_map</tt>
|
|
<blockquote>
|
|
This property map is used to accumulate the betweenness centrality
|
|
of each edge, and is a secondary form of output for the
|
|
algorithm. The type <tt>EdgeCentralityMap</tt> must be a model of <a
|
|
href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
|
|
Property Map</a>, 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 the <tt>CentralityMap</tt> property map.<br>
|
|
|
|
<b>Default:</b> a <tt>dummy_property_map</tt>, which requires no
|
|
work to compute and returns no answer.<br>
|
|
<b>Python</b>: The color map must be a <tt>edge_double_map</tt> for
|
|
the graph.<br>
|
|
<b>Python default</b>: <tt>graph.get_edge_double_map("centrality")</tt>
|
|
</blockquote>
|
|
|
|
IN: <tt>VertexIndexMap vertex_index</tt>
|
|
<blockquote>
|
|
This maps each vertex to an integer in the range <tt>[0,
|
|
num_vertices(g))</tt>. This is necessary for efficient updates of the
|
|
heap data structure when an edge is relaxed. The type
|
|
<tt>VertexIndexMap</tt> must be a model of
|
|
<a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. 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.<br>
|
|
<b>Default:</b> <tt>get(vertex_index, g)</tt>.
|
|
Note: if you use this default, make sure your graph has
|
|
an internal <tt>vertex_index</tt> property. For example,
|
|
<tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does
|
|
not have an internal <tt>vertex_index</tt> property.<br>
|
|
<b>Python</b>: Unsupported parameter.
|
|
</blockquote>
|
|
|
|
<table xmlns:rev=
|
|
"http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width=
|
|
"100%">
|
|
<tr>
|
|
<td align="left"></td>
|
|
<td align="right"></td>
|
|
</tr>
|
|
</table>
|
|
<h3>Where Defined</h3>
|
|
<<a href=
|
|
"../../../boost/graph/bc_clustering.hpp">boost/graph/bc_clustering.hpp</a>>
|
|
<hr>
|
|
<table>
|
|
<tr valign="top">
|
|
<td nowrap>Copyright © 2004</td>
|
|
<td><a href="http://www.boost.org/people/doug_gregor.html">Douglas Gregor</a>,
|
|
Indiana University (dgregor@cs.indiana.edu)<br>
|
|
<a href="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</a>, Indiana
|
|
University (<a href=
|
|
"mailto:lums@osl.iu.edu">lums@osl.iu.edu</a>)</td>
|
|
</tr>
|
|
</table>
|
|
</body>
|
|
</html>
|