1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
<!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 compute 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/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/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>adjacenty_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="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</a>, Indiana
University (<a href=
"mailto:lums@osl.iu.edu">lums@osl.iu.edu</a>)</td>
</tr>
</table>
</body>
</html>
|
