[ceph.git] / ceph / src / boost / libs / graph / doc / betweenness_centrality.html

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<!--
     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)
  -->
  <head>
    <title>Boost Graph Library: Brandes' Betweenness Centrality</title>
  </head>

  <body>
    <IMG SRC="../../../boost.png" 
     ALT="C++ Boost" width="277" height="86"> 
<h1><img src="figs/python.gif" alt="(Python)"/><tt>brandes_betweenness_centrality</tt></h1>

    <p>
    <pre>
<em>// named parameter versions</em>
template&lt;typename Graph, typename Param, typename Tag, typename Rest&gt;
void 
brandes_betweenness_centrality(const Graph&amp; g,
                               const bgl_named_params&lt;Param,Tag,Rest&gt;&amp; params);

template&lt;typename Graph, typename CentralityMap&gt;
void 
brandes_betweenness_centrality(const Graph&amp; g, CentralityMap centrality_map);

template&lt;typename Graph, typename CentralityMap, typename EdgeCentralityMap&gt;
void 
brandes_betweenness_centrality(const Graph&amp; g, CentralityMap centrality_map,
                               EdgeCentralityMap edge_centrality);

<em>// non-named parameter versions</em>
template&lt;typename Graph, typename CentralityMap, typename EdgeCentralityMap,
         typename IncomingMap, typename DistanceMap, typename DependencyMap, 
         typename PathCountMap, typename VertexIndexMap&gt;
void 
brandes_betweenness_centrality(const Graph&amp; g, CentralityMap centrality_map,
                               EdgeCentralityMap edge_centrality,
                               IncomingMap incoming,
                               DistanceMap distance, DependencyMap dependency,
                               PathCountMap path_count, 
                               VertexIndexMap vertex_index);

template&lt;typename Graph, typename CentralityMap, typename EdgeCentralityMap,
         typename IncomingMap, typename DistanceMap, typename DependencyMap, 
         typename PathCountMap, typename VertexIndexMap, typename WeightMap&gt;    
void 
brandes_betweenness_centrality(const Graph&amp; g, CentralityMap centrality_map,
                               EdgeCentralityMap edge_centrality,
                               IncomingMap incoming, 
                               DistanceMap distance,  DependencyMap dependency,
                               PathCountMap path_count,      
                               VertexIndexMap vertex_index,
                               WeightMap weight_map);

<em>// helper functions</em>
template&lt;typename Graph, typename CentralityMap&gt;
void 
relative_betweenness_centrality(const Graph&amp; g, CentralityMap centrality_map);

template&lt;typename Graph, typename CentralityMap&gt;
typename property_traits&lt;CentralityMap&gt;::value_type
central_point_dominance(const Graph&amp; g, CentralityMap centrality_map);
    </pre>

<p>This algorithm&nbsp;[<a href="bibliography.html#brandes01">54</a>]
computes the <em>betweenness centrality</em>&nbsp;[<a
href="bibliography.html#freeman77">55</a>,<a
href="bibliography.html#anthonisse71">56</a>] of each vertex or each
edge in the graph. The betweenness centrality of a vertex <em>v</em>
is defined by

<p><img src="figs/betweenness_centrality.gif">,

<p>where <img src="figs/sigma_st.gif"> is the number of shortest paths from
vertex <em>s</em> to vertex <em>t</em> and <img src="figs/sigma_stv.gif">
is the number of shortest paths from vertex <em>s</em> to vertex
<em>t</em> that pass through vertex <em>v</em>.

<!-- \sum_{s \neq v \neq t}\frac{\sigma_{st}(v)}{\sigma_{st}} -->

<p>The edge betweenness centrality indicates for each edge the
betweenness centrality that was contributed to the target(s) of the
edge (plural for undirected graphs). Similar to (vertex) betweenness
centrality, edge betweenness centrality can be used to determine the
edges through which most shortest paths must pass. A single invocation
of this algorithm can compute either the vertex or edge centrality (or
both).</p>

<p>This algorithm can operate either on weighted graphs (if a suitable
edge weight map is supplied) or unweighted graphs (if no edge weight
map is supplied). The result is the absolute betweenness centrality;
to convert to the relative betweenness centrality, which scales each
absolute centrality by <img src="figs/rel_betweenness_centrality.gif">
(where <em>n</em> is the number of vertices in the graph), use
<tt>relative_betweenness_centrality</tt>. Given the relative
betweenness centrality, one can compute the <em>central point
dominance</em>&nbsp;[<a href="bibliography.html#freeman77">55</a>], which is a measure of the maximum "betweenness" of any
point in the graph: it will be 0 for complete graphs and
1 for "wheel" graphs (in which there is a central vertex that all
paths include; see <a href="#Fig1">Fig. 1</a>). Let <img src="figs/v_star.gif"> be the vertex with the largest relative betweenness centrality; then, the central point dominance is defined as:

<p><img src="figs/central_point_dominance.gif">

<!-- C_B' = \frac{\sum_{v \in V} C_B(v^*) - C_B'(v)}{n-1} -->

<p><a name="Fig1">
    <table border="1">
      <thead>
        <tr>
          <th>Fig. 1: A wheel graph, where every path travels through the central node. <br>The central point dominance of this graph is 1.</td>
        </tr>
      </thead>
      <tbody>
        <tr>
          <td align="center"><img src="figs/wheel_graph.gif"></td>
        </tr>
      </tbody>
    </table>

<h3>Where Defined</h3>
<a href="../../../boost/graph/betweenness_centrality.hpp"><tt>boost/graph/betweenness_centrality.hpp</tt></a>

<h3>Parameters</h3>
IN: <tt>const Graph&amp; 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>.<br>

<b>Python</b>: The parameter is named <tt>graph</tt>.
</blockquote>
    
UTIL: <tt>IncomingMap incoming</tt> 
<blockquote>
  This property map records the set of edges incoming to each vertex that comprise a shortest path from a particular source vertex through this vertex, and is used internally by the algorithm.The <tt>IncomingMap</tt> type must be a <a
  href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property
  Map</a> whose key type is the same as the vertex descriptor type of
  the graph and whose value type is a Sequence (e.g., an
  <tt>std::vector</tt>) containing edge descriptors.<br>

  <b>Default:</b> <a
  href="../../property_map/doc/iterator_property_map.html">
  <tt>iterator_property_map</tt></a> created from a
  <tt>std::vector</tt> of <tt>std::vector&lt;Edge&gt;</tt>, where
  <tt>Edge</tt> is the edge descriptor type of the graph.<br>

  <b>Python</b>: Unsupported parameter.
</blockquote>

UTIL: <tt>DistanceMap distance_map</tt> 
<blockquote>
  The shortest path weight from each source vertex <tt>s</tt> to each
  vertex in the graph <tt>g</tt> is recorded in this property map, but
  the result is only used internally. The type <tt>DistanceMap</tt>
  must be a model of <a
  href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
  Property Map</a>. The vertex descriptor type of the graph needs to
  be usable as the key type of the distance map. The value type of the
  distance map is the element type of a <a
  href="./Monoid.html">Monoid</a>.<br>

  <b>Default:</b> <a
  href="../../property_map/doc/iterator_property_map.html">
  <tt>iterator_property_map</tt></a> created from a
  <tt>std::vector</tt> of the <tt>WeightMap</tt>'s value type (or the
  <tt>vertices_size_type</tt> of the graph when no weight map exists)
  of size <tt>num_vertices(g)</tt> and using the <tt>vertex_index</tt> for
  the index map.<br>

  <b>Python</b>: Unsupported parameter.
</blockquote>

UTIL: <tt>DependencyMap dependency</tt> 
<blockquote>
  Property map used internally to accumulate partial betweenness
  centrality results. The type <tt>DependencyMap</tt> must be a model
  of <a href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
  Property Map</a>. The vertex descriptor type of the graph needs to
  be usable as the key type of the dependency map. The value type of
  the dependency map must be compatible with the value type of the
  centrality map.<br>

  <b>Default:</b> <a
  href="../../property_map/doc/iterator_property_map.html">
  <tt>iterator_property_map</tt></a> created from a
  <tt>std::vector</tt> of the <tt>CentralityMap</tt>'s value type of
  size <tt>num_vertices(g)</tt> and using the <tt>vertex_index</tt>
  for the index map.<br>

  <b>Python</b>: Unsupported parameter.
</blockquote>

UTIL: <tt>PathCountMap path_count</tt> 
<blockquote>
  Property map used internally to accumulate the number of paths that
  pass through each particular vertex. The type <tt>PathCountMap</tt>
  must be a model of <a
  href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
  Property Map</a>. The vertex descriptor type of the graph needs to
  be usable as the key type of the dependency map. The value type of
  the dependency map must be an integral type large enough to store
  the number of paths in the graph.<br>

  <b>Default:</b> <a
  href="../../property_map/doc/iterator_property_map.html">
  <tt>iterator_property_map</tt></a> created from a
  <tt>std::vector</tt> of the <tt>degree_size_type</tt> of the graph of
  size <tt>num_vertices(g)</tt> and using the <tt>vertex_index</tt>
  for the index map.<br>

  <b>Python</b>: Unsupported parameter.
</blockquote>

<h3>Named parameters</h3>
OUT/UTIL: <tt>CentralityMap centrality_map</tt>
<blockquote>
  This property map is used to accumulate the betweenness centrality
  of each vertex, and is the primary output of the algorithm. The type
  <tt>CentralityMap</tt> must be a model of <a
  href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
  Property Map</a>, with the graph's vertex descriptor type as its key
  type. The value type of this property map should be a floating-point
  or rational type.<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>vertex_double_map</tt> for
  the graph.<br>
  <b>Python default</b>: <tt>graph.get_vertex_double_map("centrality")</tt>
</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>vertex_index_map(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>

IN: <tt>weight_map(WeightMap w_map)</tt>   
<blockquote>
  The weight or ``length'' of each edge in the graph. The weights
  must all be non-negative, and the algorithm will throw a
  <a href="./exception.html#negative_edge"><tt>negative_edge</tt></a> 
  exception is one of the edges is negative.
  The type <tt>WeightMap</tt> must be a model of
  <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. The edge descriptor type of
  the graph needs to be usable as the key type for the weight
  map. The value type for this map must be
  the same as the value type of the distance map.<br>
  <b>Default:</b> All edge weights are assumed to be equivalent.
  <b>Python</b>: If supplied, must be an <tt>edge_double_map</tt> for the graph.
</blockquote>

<h3>Complexity</h3> 
The time complexity is <em>O(VE)</em> for unweighted graphs and
<em>O(VE + V(V+E) log V)</em> for weighted graphs. The space complexity
is <em>O(VE)</em>.

    <hr>

<TABLE>
<TR valign=top>
<TD nowrap>Copyright &copy; 2004</TD><TD>
<A HREF="http://www.boost.org/people/doug_gregor.html">Douglas Gregor</A>, Indiana University (dgregor@cs.indiana.edu</A>)<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>
<!-- Created: Fri Jun  4 16:42:50 EST 2004 -->
<!-- hhmts start -->Last modified: Tue Mar  1 14:14:51 EST 2005 <!-- hhmts end -->
  </body>
</html>
Commit	Line	Data
7c673cae FG	1	<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
	2	<html>
	3	<!--
	4	Copyright (c) 2004 Trustees of Indiana University
	5
	6	Distributed under the Boost Software License, Version 1.0.
	7	(See accompanying file LICENSE_1_0.txt or copy at
	8	http://www.boost.org/LICENSE_1_0.txt)
	9	-->
	10	<head>
	11	<title>Boost Graph Library: Brandes' Betweenness Centrality</title>
	12	</head>
	13
	14	<body>
	15	<IMG SRC="../../../boost.png"
	16	ALT="C++ Boost" width="277" height="86">
	17	<h1><img src="figs/python.gif" alt="(Python)"/><tt>brandes_betweenness_centrality</tt></h1>
	18
	19	<p>
	20	<pre>
	21	<em>// named parameter versions</em>
	22	template<typename Graph, typename Param, typename Tag, typename Rest>
	23	void
	24	brandes_betweenness_centrality(const Graph& g,
	25	const bgl_named_params<Param,Tag,Rest>& params);
	26
	27	template<typename Graph, typename CentralityMap>
	28	void
	29	brandes_betweenness_centrality(const Graph& g, CentralityMap centrality_map);
	30
	31	template<typename Graph, typename CentralityMap, typename EdgeCentralityMap>
	32	void
	33	brandes_betweenness_centrality(const Graph& g, CentralityMap centrality_map,
	34	EdgeCentralityMap edge_centrality);
	35
	36	<em>// non-named parameter versions</em>
	37	template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
	38	typename IncomingMap, typename DistanceMap, typename DependencyMap,
	39	typename PathCountMap, typename VertexIndexMap>
	40	void
	41	brandes_betweenness_centrality(const Graph& g, CentralityMap centrality_map,
	42	EdgeCentralityMap edge_centrality,
	43	IncomingMap incoming,
	44	DistanceMap distance, DependencyMap dependency,
	45	PathCountMap path_count,
	46	VertexIndexMap vertex_index);
	47
	48	template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
	49	typename IncomingMap, typename DistanceMap, typename DependencyMap,
	50	typename PathCountMap, typename VertexIndexMap, typename WeightMap>
	51	void
	52	brandes_betweenness_centrality(const Graph& g, CentralityMap centrality_map,
	53	EdgeCentralityMap edge_centrality,
	54	IncomingMap incoming,
	55	DistanceMap distance, DependencyMap dependency,
	56	PathCountMap path_count,
	57	VertexIndexMap vertex_index,
	58	WeightMap weight_map);
	59
	60	<em>// helper functions</em>
	61	template<typename Graph, typename CentralityMap>
	62	void
	63	relative_betweenness_centrality(const Graph& g, CentralityMap centrality_map);
	64
65	template<typename Graph, typename CentralityMap>
66	typename property_traits<CentralityMap>::value_type
67	central_point_dominance(const Graph& g, CentralityMap centrality_map);
68	</pre>
69
70	<p>This algorithm [<a href="bibliography.html#brandes01">54</a>]
71	computes the <em>betweenness centrality</em> [<a
72	href="bibliography.html#freeman77">55</a>,<a
73	href="bibliography.html#anthonisse71">56</a>] of each vertex or each
74	edge in the graph. The betweenness centrality of a vertex <em>v</em>
75	is defined by
76
77	<p><img src="figs/betweenness_centrality.gif">,
78
79	<p>where <img src="figs/sigma_st.gif"> is the number of shortest paths from
80	vertex <em>s</em> to vertex <em>t</em> and <img src="figs/sigma_stv.gif">
81	is the number of shortest paths from vertex <em>s</em> to vertex
82	<em>t</em> that pass through vertex <em>v</em>.
83
84	<!-- \sum_{s \neq v \neq t}\frac{\sigma_{st}(v)}{\sigma_{st}} -->
85
86	<p>The edge betweenness centrality indicates for each edge the
87	betweenness centrality that was contributed to the target(s) of the
88	edge (plural for undirected graphs). Similar to (vertex) betweenness
89	centrality, edge betweenness centrality can be used to determine the
90	edges through which most shortest paths must pass. A single invocation
91	of this algorithm can compute either the vertex or edge centrality (or
92	both).</p>
93
94	<p>This algorithm can operate either on weighted graphs (if a suitable
95	edge weight map is supplied) or unweighted graphs (if no edge weight
96	map is supplied). The result is the absolute betweenness centrality;
97	to convert to the relative betweenness centrality, which scales each
98	absolute centrality by <img src="figs/rel_betweenness_centrality.gif">
99	(where <em>n</em> is the number of vertices in the graph), use
100	<tt>relative_betweenness_centrality</tt>. Given the relative
101	betweenness centrality, one can compute the <em>central point
102	dominance</em> [<a href="bibliography.html#freeman77">55</a>], which is a measure of the maximum "betweenness" of any
103	point in the graph: it will be 0 for complete graphs and
104	1 for "wheel" graphs (in which there is a central vertex that all
105	paths include; see <a href="#Fig1">Fig. 1</a>). Let <img src="figs/v_star.gif"> be the vertex with the largest relative betweenness centrality; then, the central point dominance is defined as:
106
107	<p><img src="figs/central_point_dominance.gif">
108
109	<!-- C_B' = \frac{\sum_{v \in V} C_B(v^*) - C_B'(v)}{n-1} -->
110
111	<p><a name="Fig1">
112	<table border="1">
113	<thead>
114	<tr>
115	<th>Fig. 1: A wheel graph, where every path travels through the central node. <br>The central point dominance of this graph is 1.</td>
116	</tr>
117	</thead>
118	<tbody>
119	<tr>
120	<td align="center"><img src="figs/wheel_graph.gif"></td>
121	</tr>
122	</tbody>
123	</table>
124
125	<h3>Where Defined</h3>
126	<a href="../../../boost/graph/betweenness_centrality.hpp"><tt>boost/graph/betweenness_centrality.hpp</tt></a>
127
128	<h3>Parameters</h3>
129	IN: <tt>const Graph& g</tt>
130	<blockquote>
131	The graph object on which the algorithm will be applied. The type
132	<tt>Graph</tt> must be a model of <a
133	href="VertexListGraph.html">Vertex List Graph</a> and <a
134	href="IncidenceGraph.html">Incidence Graph</a>. When an edge
135	centrality map is supplied, it must also model <a
136	href="EdgeListGraph.html">Edge List Graph</a>.<br>
137
138	<b>Python</b>: The parameter is named <tt>graph</tt>.
139	</blockquote>
140
141	UTIL: <tt>IncomingMap incoming</tt>
142	<blockquote>
143	This property map records the set of edges incoming to each vertex that comprise a shortest path from a particular source vertex through this vertex, and is used internally by the algorithm.The <tt>IncomingMap</tt> type must be a <a
144	href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property
145	Map</a> whose key type is the same as the vertex descriptor type of
146	the graph and whose value type is a Sequence (e.g., an
147	<tt>std::vector</tt>) containing edge descriptors.<br>
148
149	<b>Default:</b> <a
150	href="../../property_map/doc/iterator_property_map.html">
151	<tt>iterator_property_map</tt></a> created from a
152	<tt>std::vector</tt> of <tt>std::vector<Edge></tt>, where
153	<tt>Edge</tt> is the edge descriptor type of the graph.<br>
154
155	<b>Python</b>: Unsupported parameter.
156	</blockquote>
157
158	UTIL: <tt>DistanceMap distance_map</tt>
159	<blockquote>
160	The shortest path weight from each source vertex <tt>s</tt> to each
161	vertex in the graph <tt>g</tt> is recorded in this property map, but
162	the result is only used internally. The type <tt>DistanceMap</tt>
163	must be a model of <a
164	href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
165	Property Map</a>. The vertex descriptor type of the graph needs to
166	be usable as the key type of the distance map. The value type of the
167	distance map is the element type of a <a
168	href="./Monoid.html">Monoid</a>.<br>
169
170	<b>Default:</b> <a
171	href="../../property_map/doc/iterator_property_map.html">
172	<tt>iterator_property_map</tt></a> created from a
173	<tt>std::vector</tt> of the <tt>WeightMap</tt>'s value type (or the
174	<tt>vertices_size_type</tt> of the graph when no weight map exists)
175	of size <tt>num_vertices(g)</tt> and using the <tt>vertex_index</tt> for
176	the index map.<br>
177
178	<b>Python</b>: Unsupported parameter.
179	</blockquote>
180
181	UTIL: <tt>DependencyMap dependency</tt>
182	<blockquote>
183	Property map used internally to accumulate partial betweenness
184	centrality results. The type <tt>DependencyMap</tt> must be a model
185	of <a href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
186	Property Map</a>. The vertex descriptor type of the graph needs to
187	be usable as the key type of the dependency map. The value type of
188	the dependency map must be compatible with the value type of the
189	centrality map.<br>
190
191	<b>Default:</b> <a
192	href="../../property_map/doc/iterator_property_map.html">
193	<tt>iterator_property_map</tt></a> created from a
194	<tt>std::vector</tt> of the <tt>CentralityMap</tt>'s value type of
195	size <tt>num_vertices(g)</tt> and using the <tt>vertex_index</tt>
196	for the index map.<br>
197
198	<b>Python</b>: Unsupported parameter.
199	</blockquote>
200
201	UTIL: <tt>PathCountMap path_count</tt>
202	<blockquote>
203	Property map used internally to accumulate the number of paths that
204	pass through each particular vertex. The type <tt>PathCountMap</tt>
205	must be a model of <a
206	href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
207	Property Map</a>. The vertex descriptor type of the graph needs to
208	be usable as the key type of the dependency map. The value type of
209	the dependency map must be an integral type large enough to store
210	the number of paths in the graph.<br>
211
212	<b>Default:</b> <a
213	href="../../property_map/doc/iterator_property_map.html">
214	<tt>iterator_property_map</tt></a> created from a
215	<tt>std::vector</tt> of the <tt>degree_size_type</tt> of the graph of
216	size <tt>num_vertices(g)</tt> and using the <tt>vertex_index</tt>
217	for the index map.<br>
218
219	<b>Python</b>: Unsupported parameter.
220	</blockquote>
221
222	<h3>Named parameters</h3>
223	OUT/UTIL: <tt>CentralityMap centrality_map</tt>
224	<blockquote>
225	This property map is used to accumulate the betweenness centrality
226	of each vertex, and is the primary output of the algorithm. The type
227	<tt>CentralityMap</tt> must be a model of <a
228	href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
229	Property Map</a>, with the graph's vertex descriptor type as its key
230	type. The value type of this property map should be a floating-point
231	or rational type.<br>
232
233	<b>Default:</b> a <tt>dummy_property_map</tt>, which requires no
234	work to compute and returns no answer.<br>
235	<b>Python</b>: The color map must be a <tt>vertex_double_map</tt> for
236	the graph.<br>
237	<b>Python default</b>: <tt>graph.get_vertex_double_map("centrality")</tt>
238	</blockquote>
239
240	OUT/UTIL: <tt>EdgeCentralityMap edge_centrality_map</tt>
241	<blockquote>
242	This property map is used to accumulate the betweenness centrality
243	of each edge, and is a secondary form of output for the
244	algorithm. The type <tt>EdgeCentralityMap</tt> must be a model of <a
245	href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
246	Property Map</a>, with the graph's edge descriptor type as its key
247	type. The value type of this property map should be the same as the
248	value type of the <tt>CentralityMap</tt> property map.<br>
249
250	<b>Default:</b> a <tt>dummy_property_map</tt>, which requires no
251	work to compute and returns no answer.<br>
252	<b>Python</b>: The color map must be a <tt>edge_double_map</tt> for
253	the graph.<br>
254	<b>Python default</b>: <tt>graph.get_edge_double_map("centrality")</tt>
255	</blockquote>
256
257	IN: <tt>vertex_index_map(VertexIndexMap vertex_index)</tt>
258	<blockquote>
259	This maps each vertex to an integer in the range <tt>[0,
260	num_vertices(g))</tt>. This is necessary for efficient updates of the
261	heap data structure when an edge is relaxed. The type
262	<tt>VertexIndexMap</tt> must be a model of
263	<a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. The value type of the map must be an
264	integer type. The vertex descriptor type of the graph needs to be
265	usable as the key type of the map.<br>
266	<b>Default:</b> <tt>get(vertex_index, g)</tt>.
267	Note: if you use this default, make sure your graph has
268	an internal <tt>vertex_index</tt> property. For example,
269	<tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does
270	not have an internal <tt>vertex_index</tt> property.<br>
271	<b>Python</b>: Unsupported parameter.
272	</blockquote>
273
274	IN: <tt>weight_map(WeightMap w_map)</tt>
275	<blockquote>
276	The weight or ``length'' of each edge in the graph. The weights
277	must all be non-negative, and the algorithm will throw a
278	<a href="./exception.html#negative_edge"><tt>negative_edge</tt></a>
279	exception is one of the edges is negative.
280	The type <tt>WeightMap</tt> must be a model of
281	<a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. The edge descriptor type of
282	the graph needs to be usable as the key type for the weight
283	map. The value type for this map must be
284	the same as the value type of the distance map.<br>
285	<b>Default:</b> All edge weights are assumed to be equivalent.
286	<b>Python</b>: If supplied, must be an <tt>edge_double_map</tt> for the graph.
287	</blockquote>
288
289	<h3>Complexity</h3>
290	The time complexity is <em>O(VE)</em> for unweighted graphs and
291	<em>O(VE + V(V+E) log V)</em> for weighted graphs. The space complexity
292	is <em>O(VE)</em>.
293
294	<hr>
295
296	<TABLE>
297	<TR valign=top>
298	<TD nowrap>Copyright © 2004</TD><TD>
299	<A HREF="http://www.boost.org/people/doug_gregor.html">Douglas Gregor</A>, Indiana University (dgregor@cs.indiana.edu</A>)<br>
300	<A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
301	Indiana University (<A
302	HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
303	</TD></TR></TABLE>
304	<!-- Created: Fri Jun 4 16:42:50 EST 2004 -->
305	<!-- hhmts start -->Last modified: Tue Mar 1 14:14:51 EST 2005 <!-- hhmts end -->
306	</body>
307	</html>