3 Copyright (c) Fernando Vilas 2013
6 Some content from the Stoer-Wagner Min Cut documentation,
7 Copyright (c) Daniel Trebbien 2010
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)
14 <title>Boost Graph Library: Maximum Adjacency Search
</Title>
16 <img src=
"../../../boost.png" alt=
"C++ Boost" width=
"277" height=
"86">
18 <h1><a name=
"sec:maximum-adjacency-search"></a>
19 <tt>maximum_adjacency_search
</tt>
24 <em>// named parameter versions
</em>
25 template
<class Graph, class class P, class T, class R
>
27 maximum_adjacency_search(const Graph
& g,
28 const bgl_named_params
<P, T, R
>& params);
30 <i>// non-named parameter versions
</i>
31 template
<class Graph, class WeightMap, class MASVisitor
>
33 maximum_adjacency_search(const Graph
& g, WeightMap weights, MASVisitor vis,
34 const typename graph_traits
<Graph
>::vertex_descriptor start);
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
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.
64 <b>for
</b> each vertex
<i>u in V
</i>
65 <i>reach_count[u] :=
0</i>
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>
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
85 initialize vertex
<i>u
</i>
90 examine vertex
<i>u
</i>
92 examine edge
<i>(u,t)
</i>
97 finish vertex
<i>u
</i>
104 <h3>Where Defined
</h3>
107 <a href=
"../../../boost/graph/maximum_adjacency_search.hpp"><tt>boost/graph/maximum_adjacency_search.hpp
</tt></a></p>
111 IN:
<tt>const UndirectedGraph
& g
</tt></p>
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>
118 <h3>Named Parameters
</h3>
120 <p>IN:
<tt>WeightMap weights
</tt></p>
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>
132 IN:
<tt>visitor(MASVisitor vis)
</tt></p>
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>
140 IN:
<tt>root_vertex(typename
141 graph_traits
<VertexListGraph
>::vertex_descriptor start)
</tt></p>
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
146 <b>Default:
</b> <tt>*vertices(g).first
</tt><br>
149 <h4>Expert Parameters
</h4>
151 <p>IN:
<tt>vertex_index_map(VertexIndexMap vertexIndices)
</tt> </p>
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.
167 <p>UTIL:
<tt>vertex_assignment_map(AssignmentMap assignments)
</tt></p>
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
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.
178 <p>UTIL:
<tt>max_priority_queue(MaxPriorityQueue
& pq)
</tt></p>
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.
189 <p>UTIL:
<tt>index_in_heap_map(IndexInHeapMap indicesInHeap)
</tt></p>
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.
202 <p>UTIL:
<tt>distance_map(DistanceMap wAs)
</tt></p>
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>).
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.
221 <p><tt>bad_graph
</tt>
223 If
<tt>num_vertices(g)
</tt> is less than
2
226 <p><tt>std::invalid_argument
</tt>
228 If a max-priority queue is given as an argument and it is not empty
231 <h3><a name=
"SECTION001340300000000000000">
236 The time complexity is
<i>O(E + V)
</i>.
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>
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>
250 <h3>Visitor Event Points
</h3>
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>
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>
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>
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>
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>
279 <td nowrap
>Copyright
© 2012</td><td>