Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/bc_clustering.html @ 29

Last change on this file since 29 was 29, checked in by landauf, 17 years ago

updated boost from 1_33_1 to 1_34_1
File size: 6.1 KB
Line 
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 &mdash; 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>&lt;<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&gt; 
42  <span class="type"><span class=
43"bold"><b>void</b></span></span> betweenness_centrality_clustering(MutableGraph &amp; g, Done done,
44                                         EdgeCentralityMap edge_centrality,
45                                         VertexIndexMap vertex_index);
46<span class="bold"><b>template</b></span>&lt;<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&gt; 
50  <span class="type"><span class=
51"bold"><b>void</b></span></span> betweenness_centrality_clustering(MutableGraph &amp; g, Done done,
52                                         EdgeCentralityMap edge_centrality);
53<span class="bold"><b>template</b></span>&lt;<span class=
54"bold"><b>typename</b></span> MutableGraph, <span class=
55"bold"><b>typename</b></span> Done&gt; 
56  <span class="type"><span class=
57"bold"><b>void</b></span></span> betweenness_centrality_clustering(MutableGraph &amp; 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 compute 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&amp; 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/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/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>adjacenty_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&lt;<a href=
138"../../../boost/graph/bc_clustering.hpp">boost/graph/bc_clustering.hpp</a>&gt;
139<hr>
140<table>
141<tr valign="top">
142<td nowrap>Copyright &copy; 2004</td>
143<td><a href="../../../people/doug_gregor.html">Douglas Gregor</a>,
144Indiana University (dgregor@cs.indiana.edu)<br>
145<a href="http://www.osl.iu.edu/~lums">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>
Note: See TracBrowser for help on using the repository browser.