]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | |
25 | betweenness_centrality_clustering</span></h1> | |
26 | <p>boost::betweenness_centrality_clustering — Graph | |
27 | clustering 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 | |
63 | betweenness centrality. It is an iterative algorithm, where in each | |
64 | step it computes the edge betweenness centrality (via <a href= | |
65 | "betweenness_centrality.html">brandes_betweenness_centrality</a>) and | |
66 | removes the edge with the maximum betweenness centrality. The | |
67 | <tt class="computeroutput">done</tt> function object determines | |
68 | when the algorithm terminates (the edge found when the algorithm | |
69 | terminates will not be removed).</p> | |
70 | ||
71 | <h2>Parameters</h2> | |
72 | IN: <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 | ||
85 | IN: <tt>Done done</tt> | |
86 | <blockquote> | |
87 | The function object that indicates termination of the algorithm. | |
88 | It must be a ternary function object thats accepts the maximum | |
89 | centrality, the descriptor of the edge that will be removed, and | |
90 | the graph <tt class="computeroutput">g</tt>.<br> | |
91 | <b>Python</b>: Any callable Python object will suffice. | |
92 | </blockquote> | |
93 | ||
94 | OUT/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 | ||
111 | IN: <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>, | |
144 | Indiana University (dgregor@cs.indiana.edu)<br> | |
145 | <a href="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</a>, Indiana | |
146 | University (<a href= | |
147 | "mailto:lums@osl.iu.edu">lums@osl.iu.edu</a>)</td> | |
148 | </tr> | |
149 | </table> | |
150 | </body> | |
151 | </html> |