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

<html>
<!--
    Copyright (c) Fernando Vilas 2013


    Some content from the Stoer-Wagner Min Cut documentation,
    Copyright (c) Daniel Trebbien 2010

     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: Maximum Adjacency Search</Title>
<body>
<img src="../../../boost.png" alt="C++ Boost" width="277" height="86">

<h1><a name="sec:maximum-adjacency-search"></a>
<tt>maximum_adjacency_search</tt>
</h1>

<p>
<pre>
<em>// named parameter versions</em>
template &lt;class Graph, class class P, class T, class R&gt;
void
maximum_adjacency_search(const Graph&amp; g,
       const bgl_named_params&lt;P, T, R&gt;&amp; params);

<i>// non-named parameter versions</i>
template &lt;class Graph, class WeightMap, class MASVisitor&gt;
void
maximum_adjacency_search(const Graph&amp; g, WeightMap weights, MASVisitor vis,
       const typename graph_traits&lt;Graph&gt;::vertex_descriptor start);

</pre>

<p>
The <tt>maximum_adjacency_search()</tt> function performs a traversal
of the vertices in an undirected graph. The next vertex visited is the
vertex that has the most visited neighbors at any time. In the case of
an unweighted, undirected graph, the number of visited neighbors of the
very last vertex visited in the graph is also the number of edge-disjoint
paths between that vertex and the next-to-last vertex visited. These can be
retrieved from a visitor, an example of which is in the test harness
mas_test.cpp.
</p>

<p>
The <tt>maximum_adjacency_search()</tt> function invokes user-defined
actions at certain event-points within the algorithm. This provides a
mechanism for adapting the generic MAS algorithm to the many situations
in which it can be used. In the pseudo-code below, the event points
for MAS are the labels on the right. The user-defined actions must be
provided in the form of a visitor object, that is, an object whose type
meets the requirements for a MAS Visitor.
</p>

<table>
<tr>
<td valign="top">
<pre>
MAS(<i>G</i>)
  <b>for</b> each vertex <i>u in V</i> 
    <i>reach_count[u] := 0</i>
  <b>end for</b>
  // for the starting vertex s
  <i>reach_count[s] := 1</i>
  <b>for</b> each unvisited vertex <i>u in V</i>
    <b>call</b> MAS-VISIT(<i>G</i>, <i>u</i>)
    remove u from the list on unvisited vertices
    <b>for</b> each out edge from <i>u</i> to <i>t</i>
       <b>if</b> <i>t</i> has not yet been visited
         increment <i>reach_count[t]</i>
       <b>end if</b>
    <b>end for</b> each out edge
    <b>call</b> MAS-VISIT(<i>G</i>, <i>u</i>)
  <b>end for</b> each unvisited vertex
<pre>
</td>
<td valign="top">
<pre>
-
-
initialize vertex <i>u</i>
-
-
-
-
examine vertex <i>u</i>
-
examine edge <i>(u,t)</i>
-
-
-
-
finish vertex <i>u</i>
-
</pre>
</td>
</tr>
</table>

<h3>Where Defined</h3>

<p>
<a href="../../../boost/graph/maximum_adjacency_search.hpp"><tt>boost/graph/maximum_adjacency_search.hpp</tt></a></p>

<h3>Parameters</h3>

IN: <tt>const UndirectedGraph&amp; g</tt></p>
<blockquote>
  A connected, directed graph. The graph type must
  be a model of <a href="./IncidenceGraph.html">Incidence Graph</a>
  and <a href="./VertexListGraph.html">Vertex List Graph</a>.<br>
</blockquote>

<h3>Named Parameters</h3>

<p>IN: <tt>WeightMap weights</tt></p>
<blockquote>
  The weight or length of each edge in the graph. The
  <tt>WeightMap</tt> type must be a model of
  <a href="../../property_map/doc/ReadablePropertyMap.html">Readable
  Property Map</a> and its value type must be <a class="external"
  href="http://www.sgi.com/tech/stl/LessThanComparable.html">
  Less Than Comparable</a> and summable. The key type of this map
  needs to be the graph's edge descriptor type.
  <b>Default:</b> <tt>get(edge_weight, g)</tt><br>
</blockquote>

IN: <tt>visitor(MASVisitor vis)</tt></p>
<blockquote>
  A visitor object that is invoked inside the algorithm at the
  event-points specified by the MAS Visitor concept. The visitor
  object is passed by value <a href="#1">[1]</a>. <br>
  <b>Default:</b> <tt>mas_visitor&lt;null_visitor&gt;</tt><br>
</blockquote>

IN: <tt>root_vertex(typename
graph_traits&lt;VertexListGraph&gt;::vertex_descriptor start)</tt></p>
<blockquote>
  This specifies the vertex that the depth-first search should
  originate from. The type is the type of a vertex descriptor for the
  given graph.<br>
  <b>Default:</b> <tt>*vertices(g).first</tt><br>
</blockquote>

<h4>Expert Parameters</h4>

<p>IN: <tt>vertex_index_map(VertexIndexMap vertexIndices)</tt> </p>
<blockquote>
  This maps each vertex to an integer in the range
  [0, <tt>num_vertices(g)</tt>). This is only necessary if the default is
  used for the assignment, index-in-heap, or distance maps.
  <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
  key type must be the graph's vertex descriptor type.<br>
  <b>Default:</b> <tt>get(boost::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.
</blockquote>

<p>UTIL: <tt>vertex_assignment_map(AssignmentMap assignments)</tt></p>
<blockquote>
  <tt>AssignmentMap</tt> must be a model of <a
  href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write Property
  Map</a>. The key and value types must be the graph's vertex descriptor
  type.<br>
  <b>Default:</b> A <tt>boost::iterator_property_map</tt> using a
  <tt>std::vector</tt> of <tt>num_vertices(g)</tt> vertex descriptors and
  <tt>vertexIndices</tt> for the index map.
</blockquote>

<p>UTIL: <tt>max_priority_queue(MaxPriorityQueue&amp; pq)</tt></p>
<blockquote>
  <tt>MaxPriorityQueue</tt> must be a model of <a
  href="./KeyedUpdatableQueue.html">Keyed Updatable Queue</a> and a
  max-<a href="./UpdatableQueue.html#concept%3AUpdatablePriorityQueue">
  Updatable Priority Queue</a>. The value type must be the graph's vertex
  descriptor and the key type must be the weight type.
  <b>Default:</b> A <tt>boost::d_ary_heap_indirect</tt> using a default
  index-in-heap and distance map.
</blockquote>

<p>UTIL: <tt>index_in_heap_map(IndexInHeapMap indicesInHeap)</tt></p>
<blockquote>
  This parameter only has an effect when the default max-priority queue is used.<br>
  <tt>IndexInHeapMap</tt> must be a model of <a
  href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write Property
  Map</a>. The key type must be the graph's vertex descriptor type. The
  value type must be a size type
  (<tt>typename&nbsp;std::vector&lt;vertex_descriptor&gt;::size_type</tt>).<br>
  <b>Default:</b> A <tt>boost::iterator_property_map</tt> using a
  <tt>std::vector</tt> of <tt>num_vertices(g)</tt> size type objects and
  <tt>vertexIndices</tt> for the index map.
</blockquote>

<p>UTIL: <tt>distance_map(DistanceMap wAs)</tt></p>
<blockquote>
  This parameter only has an effect when the default max-priority queue is used.<br>
  <tt>DistanceMap</tt> must be a model of <a
  href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write Property
  Map</a>. The key type must be the graph's vertex descriptor type. The
  value type must be the weight type
  (<tt>typename&nbsp;boost::property_traits&lt;WeightMap&gt;::value_type</tt>).
  <br>
  <b>Default:</b> A <tt>boost::iterator_property_map</tt> using a
  <tt>std::vector</tt> of <tt>num_vertices(g)</tt> weight type objects
  and <tt>vertexIndices</tt> for the index map.
</blockquote>

<h3>Returns</h3>
<p>void</p>

<h3>Throws</h3>

<p><tt>bad_graph</tt>
<blockquote>
  If <tt>num_vertices(g)</tt> is less than 2
</blockquote></p>

<p><tt>std::invalid_argument</tt>
<blockquote>
  If a max-priority queue is given as an argument and it is not empty
</blockquote>.

<h3><a name="SECTION001340300000000000000">
Complexity</a>
</h3>

<p>
The time complexity is <i>O(E + V)</i>.
</p>

<h3>References</h3>
<ul>
<li>David Matula (1993). <q><a href="http://dl.acm.org/citation.cfm?id=313872&dl=ACM&coll=DL&CFID=85991501&CFTOKEN=44461131">A linear time 2 + epsilon approximation algorightm for edge connectivity</a></q>
</li>
<li>Cai, Weiqing and Matula, David W. 
Partitioning by maximum adjacency search of graphs. 
Partitioning Data Sets: Dimacs Workshop, April 19-21, 1993. 
Vol 19. Page 55. 1995. Amer Mathematical Society</li>
}
</ul>

<h3>Visitor Event Points</h3>

<ul>
<li><b><tt>vis.initialize_vertex(s, g)</tt></b> is invoked on every
  vertex of the graph before the start of the graph search.</li>

<li><b><tt>vis.start_vertex(s, g)</tt></b> is invoked on the source
  vertex once before processing its out edges.</li>

<li><b><tt>vis.examine_edge(e, g)</tt></b> is invoked on every out-edge
  of each vertex after it is started.</li>

<li><b><tt>vis.finish_vertex(u, g)</tt></b> is invoked on a vertex after
  all of its out edges have been examined and the reach counts of the
  unvisited targets have been updated.</li>
</ul>

<h3>Notes</h3>

<p><a name="1">[1]</a> 
  Since the visitor parameter is passed by value, if your visitor
  contains state then any changes to the state during the algorithm
  will be made to a copy of the visitor object, not the visitor object
  passed in. Therefore you may want the visitor to hold this state by
  pointer or reference.</p>

<hr>
<table>
<tr valign=top>
<td nowrap>Copyright &copy; 2012</td><td>
Fernando Vilas
</td></tr></table>

</body>
</html>
Commit	Line	Data
7c673cae FG	1	<html>
	2	<!--
	3	Copyright (c) Fernando Vilas 2013
	4
	5
	6	Some content from the Stoer-Wagner Min Cut documentation,
	7	Copyright (c) Daniel Trebbien 2010
	8
	9	Distributed under the Boost Software License, Version 1.0.
	10	(See accompanying file LICENSE_1_0.txt or copy at
	11	http://www.boost.org/LICENSE_1_0.txt)
	12	-->
	13	<head>
	14	<title>Boost Graph Library: Maximum Adjacency Search</Title>
	15	<body>
	16	<img src="../../../boost.png" alt="C++ Boost" width="277" height="86">
	17
	18	<h1><a name="sec:maximum-adjacency-search"></a>
	19	<tt>maximum_adjacency_search</tt>
	20	</h1>
	21
	22	<p>
	23	<pre>
	24	<em>// named parameter versions</em>
	25	template <class Graph, class class P, class T, class R>
	26	void
	27	maximum_adjacency_search(const Graph& g,
	28	const bgl_named_params<P, T, R>& params);
	29
	30	<i>// non-named parameter versions</i>
	31	template <class Graph, class WeightMap, class MASVisitor>
	32	void
	33	maximum_adjacency_search(const Graph& g, WeightMap weights, MASVisitor vis,
	34	const typename graph_traits<Graph>::vertex_descriptor start);
	35
	36	</pre>
	37
	38	<p>
	39	The <tt>maximum_adjacency_search()</tt> function performs a traversal
	40	of the vertices in an undirected graph. The next vertex visited is the
	41	vertex that has the most visited neighbors at any time. In the case of
	42	an unweighted, undirected graph, the number of visited neighbors of the
	43	very last vertex visited in the graph is also the number of edge-disjoint
	44	paths between that vertex and the next-to-last vertex visited. These can be
	45	retrieved from a visitor, an example of which is in the test harness
	46	mas_test.cpp.
	47	</p>
	48
	49	<p>
	50	The <tt>maximum_adjacency_search()</tt> function invokes user-defined
	51	actions at certain event-points within the algorithm. This provides a
	52	mechanism for adapting the generic MAS algorithm to the many situations
	53	in which it can be used. In the pseudo-code below, the event points
	54	for MAS are the labels on the right. The user-defined actions must be
	55	provided in the form of a visitor object, that is, an object whose type
	56	meets the requirements for a MAS Visitor.
	57	</p>
	58
	59	<table>
	60	<tr>
	61	<td valign="top">
	62	<pre>
	63	MAS(<i>G</i>)
	64	<b>for</b> each vertex <i>u in V</i>
65	<i>reach_count[u] := 0</i>
66	<b>end for</b>
67	// for the starting vertex s
68	<i>reach_count[s] := 1</i>
69	<b>for</b> each unvisited vertex <i>u in V</i>
70	<b>call</b> MAS-VISIT(<i>G</i>, <i>u</i>)
71	remove u from the list on unvisited vertices
72	<b>for</b> each out edge from <i>u</i> to <i>t</i>
73	<b>if</b> <i>t</i> has not yet been visited
74	increment <i>reach_count[t]</i>
75	<b>end if</b>
76	<b>end for</b> each out edge
77	<b>call</b> MAS-VISIT(<i>G</i>, <i>u</i>)
78	<b>end for</b> each unvisited vertex
79	<pre>
80	</td>
81	<td valign="top">
82	<pre>
83	-
84	-
85	initialize vertex <i>u</i>
86	-
87	-
88	-
89	-
90	examine vertex <i>u</i>
91	-
92	examine edge <i>(u,t)</i>
93	-
94	-
95	-
96	-
97	finish vertex <i>u</i>
98	-
99	</pre>
100	</td>
101	</tr>
102	</table>
103
104	<h3>Where Defined</h3>
105
106	<p>
107	<a href="../../../boost/graph/maximum_adjacency_search.hpp"><tt>boost/graph/maximum_adjacency_search.hpp</tt></a></p>
108
109	<h3>Parameters</h3>
110
111	IN: <tt>const UndirectedGraph& g</tt></p>
112	<blockquote>
113	A connected, directed graph. The graph type must
114	be a model of <a href="./IncidenceGraph.html">Incidence Graph</a>
115	and <a href="./VertexListGraph.html">Vertex List Graph</a>.<br>
116	</blockquote>
117
118	<h3>Named Parameters</h3>
119
120	<p>IN: <tt>WeightMap weights</tt></p>
121	<blockquote>
122	The weight or length of each edge in the graph. The
123	<tt>WeightMap</tt> type must be a model of
124	<a href="../../property_map/doc/ReadablePropertyMap.html">Readable
125	Property Map</a> and its value type must be <a class="external"
126	href="http://www.sgi.com/tech/stl/LessThanComparable.html">
127	Less Than Comparable</a> and summable. The key type of this map
128	needs to be the graph's edge descriptor type.
129	<b>Default:</b> <tt>get(edge_weight, g)</tt><br>
130	</blockquote>
131
132	IN: <tt>visitor(MASVisitor vis)</tt></p>
133	<blockquote>
134	A visitor object that is invoked inside the algorithm at the
135	event-points specified by the MAS Visitor concept. The visitor
136	object is passed by value <a href="#1">[1]</a>. <br>
137	<b>Default:</b> <tt>mas_visitor<null_visitor></tt><br>
138	</blockquote>
139
140	IN: <tt>root_vertex(typename
141	graph_traits<VertexListGraph>::vertex_descriptor start)</tt></p>
142	<blockquote>
143	This specifies the vertex that the depth-first search should
144	originate from. The type is the type of a vertex descriptor for the
145	given graph.<br>
146	<b>Default:</b> <tt>*vertices(g).first</tt><br>
147	</blockquote>
148
149	<h4>Expert Parameters</h4>
150
151	<p>IN: <tt>vertex_index_map(VertexIndexMap vertexIndices)</tt> </p>
152	<blockquote>
153	This maps each vertex to an integer in the range
154	[0, <tt>num_vertices(g)</tt>). This is only necessary if the default is
155	used for the assignment, index-in-heap, or distance maps.
156	<tt>VertexIndexMap</tt> must be a model of <a
157	href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
158	Map</a>. The value type of the map must be an integer type. The
159	key type must be the graph's vertex descriptor type.<br>
160	<b>Default:</b> <tt>get(boost::vertex_index, g)</tt>
161	Note: if you use this default, make sure your graph has
162	an internal <tt>vertex_index</tt> property. For example,
163	<tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does
164	not have an internal <tt>vertex_index</tt> property.
165	</blockquote>
166
167	<p>UTIL: <tt>vertex_assignment_map(AssignmentMap assignments)</tt></p>
168	<blockquote>
169	<tt>AssignmentMap</tt> must be a model of <a
170	href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write Property
171	Map</a>. The key and value types must be the graph's vertex descriptor
172	type.<br>
173	<b>Default:</b> A <tt>boost::iterator_property_map</tt> using a
174	<tt>std::vector</tt> of <tt>num_vertices(g)</tt> vertex descriptors and
175	<tt>vertexIndices</tt> for the index map.
176	</blockquote>
177
178	<p>UTIL: <tt>max_priority_queue(MaxPriorityQueue& pq)</tt></p>
179	<blockquote>
180	<tt>MaxPriorityQueue</tt> must be a model of <a
181	href="./KeyedUpdatableQueue.html">Keyed Updatable Queue</a> and a
182	max-<a href="./UpdatableQueue.html#concept%3AUpdatablePriorityQueue">
183	Updatable Priority Queue</a>. The value type must be the graph's vertex
184	descriptor and the key type must be the weight type.
185	<b>Default:</b> A <tt>boost::d_ary_heap_indirect</tt> using a default
186	index-in-heap and distance map.
187	</blockquote>
188
189	<p>UTIL: <tt>index_in_heap_map(IndexInHeapMap indicesInHeap)</tt></p>
190	<blockquote>
191	This parameter only has an effect when the default max-priority queue is used.<br>
192	<tt>IndexInHeapMap</tt> must be a model of <a
193	href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write Property
194	Map</a>. The key type must be the graph's vertex descriptor type. The
195	value type must be a size type
196	(<tt>typename std::vector<vertex_descriptor>::size_type</tt>).<br>
197	<b>Default:</b> A <tt>boost::iterator_property_map</tt> using a
198	<tt>std::vector</tt> of <tt>num_vertices(g)</tt> size type objects and
199	<tt>vertexIndices</tt> for the index map.
200	</blockquote>
201
202	<p>UTIL: <tt>distance_map(DistanceMap wAs)</tt></p>
203	<blockquote>
204	This parameter only has an effect when the default max-priority queue is used.<br>
205	<tt>DistanceMap</tt> must be a model of <a
206	href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write Property
207	Map</a>. The key type must be the graph's vertex descriptor type. The
208	value type must be the weight type
209	(<tt>typename boost::property_traits<WeightMap>::value_type</tt>).
210	<br>
211	<b>Default:</b> A <tt>boost::iterator_property_map</tt> using a
212	<tt>std::vector</tt> of <tt>num_vertices(g)</tt> weight type objects
213	and <tt>vertexIndices</tt> for the index map.
214	</blockquote>
215
216	<h3>Returns</h3>
217	<p>void</p>
218
219	<h3>Throws</h3>
220
221	<p><tt>bad_graph</tt>
222	<blockquote>
223	If <tt>num_vertices(g)</tt> is less than 2
224	</blockquote></p>
225
226	<p><tt>std::invalid_argument</tt>
227	<blockquote>
228	If a max-priority queue is given as an argument and it is not empty
229	</blockquote>.
230
231	<h3><a name="SECTION001340300000000000000">
232	Complexity</a>
233	</h3>
234
235	<p>
236	The time complexity is <i>O(E + V)</i>.
237	</p>
238
239	<h3>References</h3>
240	<ul>
241	<li>David Matula (1993). <q><a href="http://dl.acm.org/citation.cfm?id=313872&dl=ACM&coll=DL&CFID=85991501&CFTOKEN=44461131">A linear time 2 + epsilon approximation algorightm for edge connectivity</a></q>
242	</li>
243	<li>Cai, Weiqing and Matula, David W.
244	Partitioning by maximum adjacency search of graphs.
245	Partitioning Data Sets: Dimacs Workshop, April 19-21, 1993.
246	Vol 19. Page 55. 1995. Amer Mathematical Society</li>
247	}
248	</ul>
249
250	<h3>Visitor Event Points</h3>
251
252	<ul>
253	<li><b><tt>vis.initialize_vertex(s, g)</tt></b> is invoked on every
254	vertex of the graph before the start of the graph search.</li>
255
256	<li><b><tt>vis.start_vertex(s, g)</tt></b> is invoked on the source
257	vertex once before processing its out edges.</li>
258
259	<li><b><tt>vis.examine_edge(e, g)</tt></b> is invoked on every out-edge
260	of each vertex after it is started.</li>
261
262	<li><b><tt>vis.finish_vertex(u, g)</tt></b> is invoked on a vertex after
263	all of its out edges have been examined and the reach counts of the
264	unvisited targets have been updated.</li>
265	</ul>
266
267	<h3>Notes</h3>
268
269	<p><a name="1">[1]</a>
270	Since the visitor parameter is passed by value, if your visitor
271	contains state then any changes to the state during the algorithm
272	will be made to a copy of the visitor object, not the visitor object
273	passed in. Therefore you may want the visitor to hold this state by
274	pointer or reference.</p>
275
276	<hr>
277	<table>
278	<tr valign=top>
279	<td nowrap>Copyright © 2012</td><td>
280	Fernando Vilas
281	</td></tr></table>
282
283	</body>
284	</html>