ceph/src/boost/libs/graph/doc/bc_clustering.html

   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 &mdash; 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>&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
  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&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
  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 &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="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>