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> 25template <class Graph, class class P, class T, class R> 26void 27maximum_adjacency_search(const Graph& g, 28 const bgl_named_params<P, T, R>& params); 29 30<i>// non-named parameter versions</i> 31template <class Graph, class WeightMap, class MASVisitor> 32void 33maximum_adjacency_search(const Graph& g, WeightMap weights, MASVisitor vis, 34 const typename graph_traits<Graph>::vertex_descriptor start); 35 36</pre> 37 38<p> 39The <tt>maximum_adjacency_search()</tt> function performs a traversal 40of the vertices in an undirected graph. The next vertex visited is the 41vertex that has the most visited neighbors at any time. In the case of 42an unweighted, undirected graph, the number of visited neighbors of the 43very last vertex visited in the graph is also the number of edge-disjoint 44paths between that vertex and the next-to-last vertex visited. These can be 45retrieved from a visitor, an example of which is in the test harness 46mas_test.cpp. 47</p> 48 49<p> 50The <tt>maximum_adjacency_search()</tt> function invokes user-defined 51actions at certain event-points within the algorithm. This provides a 52mechanism for adapting the generic MAS algorithm to the many situations 53in which it can be used. In the pseudo-code below, the event points 54for MAS are the labels on the right. The user-defined actions must be 55provided in the form of a visitor object, that is, an object whose type 56meets the requirements for a MAS Visitor. 57</p> 58 59<table> 60<tr> 61<td valign="top"> 62<pre> 63MAS(<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- 85initialize vertex <i>u</i> 86- 87- 88- 89- 90examine vertex <i>u</i> 91- 92examine edge <i>(u,t)</i> 93- 94- 95- 96- 97finish 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 111IN: <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.boost.org/sgi/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 132IN: <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 140IN: <tt>root_vertex(typename 141graph_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"> 232Complexity</a> 233</h3> 234 235<p> 236The 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. 244Partitioning by maximum adjacency search of graphs. 245Partitioning Data Sets: Dimacs Workshop, April 19-21, 1993. 246Vol 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> 280Fernando Vilas 281</td></tr></table> 282 283</body> 284</html> 285
