diff options
Diffstat (limited to 'src/boost/libs/disjoint_sets')
| -rw-r--r-- | src/boost/libs/disjoint_sets/Jamfile.v2 | 3 | ||||
| -rw-r--r-- | src/boost/libs/disjoint_sets/bibliography.html | 59 | ||||
| -rw-r--r-- | src/boost/libs/disjoint_sets/disjoint_sets.html | 309 | ||||
| -rw-r--r-- | src/boost/libs/disjoint_sets/index.html | 14 | ||||
| -rw-r--r-- | src/boost/libs/disjoint_sets/test/Jamfile | 8 | ||||
| -rw-r--r-- | src/boost/libs/disjoint_sets/test/disjoint_set_test.cpp | 76 |
6 files changed, 469 insertions, 0 deletions
diff --git a/src/boost/libs/disjoint_sets/Jamfile.v2 b/src/boost/libs/disjoint_sets/Jamfile.v2 new file mode 100644 index 00000000..cf5eb618 --- /dev/null +++ b/src/boost/libs/disjoint_sets/Jamfile.v2 @@ -0,0 +1,3 @@ +# Empty Jamfile because the super project still expects one to appear here. +# Can be deleted once 'status/Jamfile.v2' has been updated in the super +# project. diff --git a/src/boost/libs/disjoint_sets/bibliography.html b/src/boost/libs/disjoint_sets/bibliography.html new file mode 100644 index 00000000..54fc44a0 --- /dev/null +++ b/src/boost/libs/disjoint_sets/bibliography.html @@ -0,0 +1,59 @@ +<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> + +<html> +<head> + <meta http-equiv="Content-Language" content="en-us"> + <meta http-equiv="Content-Type" content="text/html; charset=us-ascii"> + + <title>Boost Utility Library: Bibliography</title> +</head> + +<body bgcolor="#FFFFFF" link="#0000EE" text="#000000" vlink="#551A8B" alink= +"#FF0000"> + <img src="../../boost.png" alt="C++ Boost" width="277" height= + "86"><br clear="none"> + + <h2>Bibliography</h2> + + <dl compact> + <dt><a name="tarjan83:_data_struct_network_algo" id= + "tarjan83:_data_struct_network_algo">1</a></dt> + + <dd>R. E. Tarjan.<br> + <em>Data Structures and Network Algorithms</em>.<br> + Society for Industrial and Applied Mathematics, 1983.</dd> + + <dt> </dt> + + <dt><a name="clr90" id="clr90">2</a></dt> + + <dd>T. Cormen, C. Leiserson, and R. Rivest.<br> + <em>Introduction to Algorithms</em>.<br> + McGraw-Hill, 1990.</dd> + </dl><br> + <hr> + + <p><a href="http://validator.w3.org/check?uri=referer"><img border="0" src= + "../../doc/images/valid-html401.png" alt="Valid HTML 4.01 Transitional" + height="31" width="88"></a></p> + + <p>Revised + <!--webbot bot="Timestamp" s-type="EDITED" s-format="%d %B, %Y" startspan -->01 + December, 2006<!--webbot bot="Timestamp" endspan i-checksum="38508" --></p> + + <table summary=""> + <tr valign="top"> + <td nowrap><i>Copyright © 2000</i></td> + + <td><i><a href="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</a>, Univ.of + Notre Dame (<a href= + "mailto:jsiek@lsc.nd.edu">jsiek@lsc.nd.edu</a>)</i></td> + </tr> + </table> + + <p><i>Distributed under the Boost Software License, Version 1.0. (See + accompanying file <a href="../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or + copy at <a href= + "http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>)</i></p> +</body> +</html> diff --git a/src/boost/libs/disjoint_sets/disjoint_sets.html b/src/boost/libs/disjoint_sets/disjoint_sets.html new file mode 100644 index 00000000..ef1632d2 --- /dev/null +++ b/src/boost/libs/disjoint_sets/disjoint_sets.html @@ -0,0 +1,309 @@ +<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> + +<html> +<head> + <meta http-equiv="Content-Language" content="en-us"> + <meta http-equiv="Content-Type" content="text/html; charset=us-ascii"> + + <title>Boost Disjoint Sets</title> +</head> + +<body bgcolor="#FFFFFF" link="#0000EE" text="#000000" vlink="#551A8B" alink= +"#FF0000"> + <img src="../../boost.png" alt="C++ Boost" width="277" height= + "86"><br clear="none"> + + <h1><a name="sec:disjoint-sets" id="sec:disjoint-sets"></a> Disjoint + Sets</h1> + <pre> +disjoint_sets<Rank, Parent, FindCompress> +</pre> + + <p>This is class that provides disjoint sets operations with <i>union by + rank</i> and <i>path compression</i>. A disjoint-sets data structure + maintains a collection <i>S = {S<sub>1</sub>, S<sub>2</sub>, ..., + S<sub>k</sub>}</i> of disjoint sets. Each set is identified by a + <i>representative</i> which is some member of of the set. Sets are + represented by rooted trees which are encoded in the <tt>Parent</tt> + property map. Two heuristics: "union by rank" and "path compression" are + used to speed up the operations [<a href= + "./bibliography.html#tarjan83:_data_struct_network_algo">1</a>, <a href= + "./bibliography.html#clr90">2</a>].</p> + + <h3>Where Defined</h3><a href= + "../../boost/pending/disjoint_sets.hpp"><tt>boost/pending/disjoint_sets.hpp</tt></a> + + <h3>Template Parameters</h3> + + <table border summary=""> + <tr> + <td><tt>Rank</tt></td> + + <td>must be a model of <a href= + "../property_map/doc/ReadWritePropertyMap.html">ReadWritePropertyMap</a> + with an integer value type and a key type equal to the set's element + type.</td> + </tr> + + <tr> + <td><tt>Parent</tt></td> + + <td>must be a model of <a href= + "../property_map/doc/ReadWritePropertyMap.html">ReadWritePropertyMap</a> + and the key and value type the same as the set's element type.</td> + </tr> + + <tr> + <td><tt>FindCompress</tt></td> + + <td>should be one of the find representative and path compress function + objects.</td> + </tr> + </table> + + <h3>Example</h3> + + <p>A typical usage pattern for <tt>disjoint_sets</tt> can be seen in the + <a href= + "../graph/doc/kruskal_min_spanning_tree.html"><tt>kruskal_minimum_spanning_tree()</tt></a> + algorithm. In this example, we call <tt>link()</tt> instead of + <tt>union_set()</tt> because <tt>u</tt> and <tt>v</tt> were obtained from + <tt>find_set()</tt> and therefore are already the representatives for their + sets.</p> + <pre> + ... + disjoint_sets<Rank, Parent, FindCompress> dsets(rank, p); + + for (ui = vertices(G).first; ui != vertices(G).second; ++ui) + dsets.make_set(*ui); + ... + while ( !Q.empty() ) { + e = Q.front(); + Q.pop(); + u = dsets.find_set(source(e)); + v = dsets.find_set(target(e)); + if ( u != v ) { + *out++ = e; + dsets.link(u, v); + } + } +</pre> + + <h3>Members</h3> + + <table border summary=""> + <tr> + <th>Member</th> + + <th>Description</th> + </tr> + + <tr> + <td><tt>disjoint_sets(Rank r, Parent p)</tt></td> + + <td>Constructor.</td> + </tr> + + <tr> + <td><tt>disjoint_sets(const disjoint_sets& x)</tt></td> + + <td>Copy constructor.</td> + </tr> + + <tr> + <td><tt>template <class Element><br> + void make_set(Element x)</tt></td> + + <td>Creates a singleton set containing Element <tt>x</tt>.</td> + </tr> + + <tr> + <td><tt>template <class Element><br> + void link(Element x, Element y)</tt></td> + + <td>Union the two sets <i>represented</i> by element <tt>x</tt> and + <tt>y</tt>.</td> + </tr> + + <tr> + <td><tt>template <class Element><br> + void union_set(Element x, Element y)</tt></td> + + <td>Union the two sets that <i>contain</i> elements <tt>x</tt> and + <tt>y</tt>. This is equivalent to + <tt>link(find_set(x),find_set(y))</tt>.</td> + </tr> + + <tr> + <td><tt>template <class Element><br> + Element find_set(Element x)</tt></td> + + <td>Return the representative for the set containing element + <tt>x</tt>.</td> + </tr> + + <tr> + <td><tt>template <class ElementIterator><br> + std::size_t count_sets(ElementIterator first, ElementIterator + last)</tt></td> + + <td>Returns the number of disjoint sets.</td> + </tr> + + <tr> + <td><tt>template <class ElementIterator><br> + void compress_sets(ElementIterator first, ElementIterator + last)</tt></td> + + <td>Flatten the parents tree so that the parent of every element is its + representative.</td> + </tr> + </table> + + <h3>Complexity</h3> + + <p>The time complexity is <i>O(m alpha(m,n))</i>, where <i>alpha</i> is the + inverse Ackermann's function, <i>m</i> is the number of disjoint-set + operations (<tt>make_set()</tt>, <tt>find_set()</tt>, and <tt>link()</tt> + and <i>n</i> is the number of elements. The <i>alpha</i> function grows + very slowly, much more slowly than the <i>log</i> function.</p> + + <h3>See Also</h3><a href= + "../graph/doc/incremental_components.html"><tt>incremental_connected_components()</tt></a> + <hr> + <pre> +disjoint_sets_with_storage<ID,InverseID,FindCompress> +</pre> + + <p>This class manages the storage for the rank and parent properties + internally. The storage is in arrays, which are indexed by element ID, + hence the requirement for the <tt>ID</tt> and <tt>InverseID</tt> functors. + The rank and parent properties are initialized during construction so the + each element is in a set by itself (so it is not necessary to initialize + objects of this class with the <a href= + "../graph/doc/incremental_components.html#sec:initialize-incremental-components"> + <tt>initialize_incremental_components()</tt></a> function). This class is + especially useful when computing the (dynamic) connected components of an + <tt>edge_list</tt> graph which does not provide a place to store vertex + properties.</p> + + <h3>Template Parameters</h3> + + <table border summary=""> + <tr> + <th>Parameter</th> + + <th>Description</th> + + <th>Default</th> + </tr> + + <tr> + <td><tt>ID</tt></td> + + <td>must be a model of <a href= + "../property_map/doc/ReadablePropertyMap.html">ReadablePropertyMap</a> that + maps elements to integers between zero 0 and N, the total number of + elements in the sets.</td> + + <td><tt>boost::identity_property_map</tt></td> + </tr> + + <tr> + <td><tt>InverseID</tt></td> + + <td>must be a model of <a href= + "../property_map/doc/ReadablePropertyMap.html">ReadablePropertyMap</a> that + maps integers to elements.</td> + + <td><tt>boost::identity_property_map</tt></td> + </tr> + + <tr> + <td><tt>FindCompress</tt></td> + + <td>should be one of the find representative and path compress function + objects.</td> + + <td><tt>representative_with_full_path_compression</tt></td> + </tr> + </table> + + <h3>Members</h3> + + <p>This class has all of the members in <tt>disjoint_sets</tt> as well as + the following members.</p> + <pre> +disjoint_sets_with_storage(size_type n = 0, + ID id = ID(), + InverseID inv = InverseID()) +</pre>Constructor. + <pre> +template <class ElementIterator> +void disjoint_sets_with_storage:: + normalize_sets(ElementIterator first, ElementIterator last) +</pre>This rearranges the representatives such that the representative of +each set is the element with the smallest ID.<br> + Postcondition: <tt>v >= parent[v]</tt><br> + Precondition: the disjoint sets structure must be compressed.<br> + <hr> + + <h2><a name="sec:representative-with-path-halving" id= + "sec:representative-with-path-halving"></a></h2> + <pre> +representative_with_path_halving<Parent> +</pre> + + <p>This is a functor which finds the representative vertex for the same + component as the element <tt>x</tt>. While traversing up the representative + tree, the functor also applies the path halving technique to shorten the + height of the tree.</p> + <pre> +Element operator()(Parent p, Element x) +</pre> + <hr> + + <h2><a name="sec:representative-with-full-path-compression" id= + "sec:representative-with-full-path-compression"></a><br></h2> + <pre> +representative_with_full_path_compression<Parent> +</pre> + + <p>This is a functor which finds the representative element for the set + that element <tt>x</tt> belongs to.</p> + <pre> +Element operator()(Parent p, Element x) +</pre> + + <p><br></p> + <hr> + + <p><a href="http://validator.w3.org/check?uri=referer"><img border="0" src= + "../../doc/images/valid-html401.png" alt="Valid HTML 4.01 Transitional" + height="31" width="88"></a></p> + + <p>Revised + <!--webbot bot="Timestamp" s-type="EDITED" s-format="%d %B, %Y" startspan -->01 + December, 2006<!--webbot bot="Timestamp" endspan i-checksum="38508" --></p> + + <table summary=""> + <tr valign="top"> + <td nowrap><i>Copyright © 2000</i></td> + + <td><i><a href="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</a>, Univ.of + Notre Dame (<a href="mailto:jsiek@lsc.nd.edu">jsiek@lsc.nd.edu</a>)<br> + <a href="http://www.boost.org/people/liequan_lee.htm">Lie-Quan Lee</a>, + Univ.of Notre Dame (<a href= + "mailto:llee1@lsc.nd.edu">llee1@lsc.nd.edu</a>)<br> + <a href="http://www.lsc.nd.edu/~lums">Andrew Lumsdaine</a>, Univ.of + Notre Dame (<a href= + "mailto:lums@lsc.nd.edu">lums@lsc.nd.edu</a>)</i></td> + </tr> + </table> + + <p><i>Distributed under the Boost Software License, Version 1.0. (See + accompanying file <a href="../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or + copy at <a href= + "http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>)</i></p> +</body> +</html> diff --git a/src/boost/libs/disjoint_sets/index.html b/src/boost/libs/disjoint_sets/index.html new file mode 100644 index 00000000..91d5a97f --- /dev/null +++ b/src/boost/libs/disjoint_sets/index.html @@ -0,0 +1,14 @@ +<html> +<head> +<meta http-equiv="refresh" content="0; URL=disjoint_sets.html"> +</head> +<body> +Automatic redirection failed, please go to +<a href="disjoint_sets.html">disjoint_sets.html</a>. <hr> +<p>© Copyright Beman Dawes, 2001</p> +<p>Distributed under the Boost Software License, Version 1.0. (See accompanying +file <a href="../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or copy +at <a href="http://www.boost.org/LICENSE_1_0.txt">www.boost.org/LICENSE_1_0.txt</a>) +</p> +</body> +</html>
\ No newline at end of file diff --git a/src/boost/libs/disjoint_sets/test/Jamfile b/src/boost/libs/disjoint_sets/test/Jamfile new file mode 100644 index 00000000..823cd976 --- /dev/null +++ b/src/boost/libs/disjoint_sets/test/Jamfile @@ -0,0 +1,8 @@ +# Copyright Jeremy Siek 2002 +# Use, modification and distribution are subject to 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) + +test-suite disjoint_sets : + [ run disjoint_set_test.cpp ] + ;
\ No newline at end of file diff --git a/src/boost/libs/disjoint_sets/test/disjoint_set_test.cpp b/src/boost/libs/disjoint_sets/test/disjoint_set_test.cpp new file mode 100644 index 00000000..cd588396 --- /dev/null +++ b/src/boost/libs/disjoint_sets/test/disjoint_set_test.cpp @@ -0,0 +1,76 @@ +// (C) Copyright Jeremy Siek 2002. +// 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) + +#include <boost/pending/disjoint_sets.hpp> +#include <boost/test/minimal.hpp> +#include <boost/cstdlib.hpp> + +template <typename DisjointSet> +struct test_disjoint_set { + static void do_test() + { + // The following tests are pretty lame, just a basic sanity check. + // Industrial strength tests still need to be written. + +#if !defined(__MWERKS__) || __MWERKS__ > 0x3003 + std::size_t elts[] +#else + std::size_t elts[4] +#endif + = { 0, 1, 2, 3 }; + + const int N = sizeof(elts)/sizeof(*elts); + + DisjointSet ds(N); + + ds.make_set(elts[0]); + ds.make_set(elts[1]); + ds.make_set(elts[2]); + ds.make_set(elts[3]); + + BOOST_CHECK(ds.find_set(0) != ds.find_set(1)); + BOOST_CHECK(ds.find_set(0) != ds.find_set(2)); + BOOST_CHECK(ds.find_set(0) != ds.find_set(3)); + BOOST_CHECK(ds.find_set(1) != ds.find_set(2)); + BOOST_CHECK(ds.find_set(1) != ds.find_set(3)); + BOOST_CHECK(ds.find_set(2) != ds.find_set(3)); + + + ds.union_set(0, 1); + ds.union_set(2, 3); + BOOST_CHECK(ds.find_set(0) != ds.find_set(3)); + int a = ds.find_set(0); + BOOST_CHECK(a == ds.find_set(1)); + int b = ds.find_set(2); + BOOST_CHECK(b == ds.find_set(3)); + + ds.link(a, b); + BOOST_CHECK(ds.find_set(a) == ds.find_set(b)); + BOOST_CHECK(1 == ds.count_sets(elts, elts + N)); + + ds.normalize_sets(elts, elts + N); + ds.compress_sets(elts, elts + N); + BOOST_CHECK(1 == ds.count_sets(elts, elts + N)); + } +}; + +int +test_main(int, char*[]) +{ + using namespace boost; + { + typedef + disjoint_sets_with_storage<identity_property_map, identity_property_map, + find_with_path_halving> ds_type; + test_disjoint_set<ds_type>::do_test(); + } + { + typedef + disjoint_sets_with_storage<identity_property_map, identity_property_map, + find_with_full_path_compression> ds_type; + test_disjoint_set<ds_type>::do_test(); + } + return boost::exit_success; +} |