123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284 |
- <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 <class Graph, class class P, class T, class R>
- void
- maximum_adjacency_search(const Graph& g,
- const bgl_named_params<P, T, R>& params);
- <i>// non-named parameter versions</i>
- template <class Graph, class WeightMap, class MASVisitor>
- void
- maximum_adjacency_search(const Graph& g, WeightMap weights, MASVisitor vis,
- const typename graph_traits<Graph>::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& 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.boost.org/sgi/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<null_visitor></tt><br>
- </blockquote>
- IN: <tt>root_vertex(typename
- graph_traits<VertexListGraph>::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& 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 std::vector<vertex_descriptor>::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 boost::property_traits<WeightMap>::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 © 2012</td><td>
- Fernando Vilas
- </td></tr></table>
- </body>
- </html>
|