Quelle  chap5_mj.html   Sprache: HTML

<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
         "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<script type="text/javascript"
  src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>GAP (datastructures) - Chapter 5: Union-Find</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap5"  onload="jscontent()">


<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a>  <a href="chap1_mj.html">1</a>  <a href="chap2_mj.html">2</a>  <a href="chap3_mj.html">3</a>  <a href="chap4_mj.html">4</a>  <a href="chap5_mj.html">5</a>  <a href="chap6_mj.html">6</a>  <a href="chap7_mj.html">7</a>  <a href="chap8_mj.html">8</a>  <a href="chap9_mj.html">9</a>  <a href="chap10_mj.html">10</a>  <a href="chap11_mj.html">11</a>  <a href="chap12_mj.html">12</a>  <a href="chapBib_mj.html">Bib</a>  <a href="chapInd_mj.html">Ind</a>  </div>

<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap4_mj.html">[Previous Chapter]</a>    <a href="chap6_mj.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap5.html">[MathJax off]</a></p>
<p><a id="X7C0CE80081C1D1A2" name="X7C0CE80081C1D1A2"></a></p>
<div class="ChapSects"><a href="chap5_mj.html#X7C0CE80081C1D1A2">5 <span class="Heading">Union-Find</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5_mj.html#X7DFB63A97E67C0A1">5.1 <span class="Heading">Introduction</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5_mj.html#X7C5F33687C53BEF0">5.2 <span class="Heading">API</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X804726FA84A7EA0F">5.2-1 IsPartitionDS</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X794FFC5983C63468">5.2-2 PartitionDSCons</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7EAC43E97BE451C0">5.2-3 PartitionDSCons</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X85E4403778DC83A0">5.2-4 PartitionDS</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X876385547BD14FDD">5.2-5 PartitionDS</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7B0B222583188A6B">5.2-6 PartitionDS</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X8796F318875443C4">5.2-7 PartitionDS</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X8344F7007AD2C44B">5.2-8 Representative</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7FABCE367DC2F82B">5.2-9 Unite</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7A41C16979664337">5.2-10 RootsIteratorOfPartitionDS</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7EA363F57FC53B4E">5.2-11 RootsOfPartitionDS</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X83E6F1DE84ABFB69">5.2-12 NumberParts</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X8635245A83D7DC1B">5.2-13 SizeUnderlyingSetDS</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X8716AC8F79820C86">5.2-14 PartsOfPartitionDS</a></span>
</div></div>
</div>

<h3>5 <span class="Heading">Union-Find</span></h3>

<p><a id="X7DFB63A97E67C0A1" name="X7DFB63A97E67C0A1"></a></p>

<h4>5.1 <span class="Heading">Introduction</span></h4>

<p><strong class="pkg">datastructures</strong> defines the interface for mutable data structures representing partitions of <code class="code">[1..n]</code>, commonly known as union-find data structures. Key operations are <code class="func">Unite</code> (<a href="chap5_mj.html#X7FABCE367DC2F82B"><span class="RefLink">5.2-9</span></a>) which fuses two parts of a partition and <code class="func">Representative</code> (<a href="chap5_mj.html#X8344F7007AD2C44B"><span class="RefLink">5.2-8</span></a>) which returns a canonical representative of the part containing a given point.</p>

<p><a id="X7C5F33687C53BEF0" name="X7C5F33687C53BEF0"></a></p>

<h4>5.2 <span class="Heading">API</span></h4>

<p><a id="X804726FA84A7EA0F" name="X804726FA84A7EA0F"></a></p>

<h5>5.2-1 IsPartitionDS</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsPartitionDS</code>( <var class="Arg">arg</var> )</td><td class="tdright">( filter )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code></p>

<p>Category of datastructures representing partitions. Equality is identity and family is ignored.</p>

<p><a id="X794FFC5983C63468" name="X794FFC5983C63468"></a></p>

<h5>5.2-2 PartitionDSCons</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; PartitionDSCons</code>( <var class="Arg">filter</var>, <var class="Arg">n</var> )</td><td class="tdright">( constructor )</td></tr></table></div>
<p>Family containing all partition data structures Returns the trivial partition of the set <code class="code">[1..n]</code>.</p>

<p><a id="X7EAC43E97BE451C0" name="X7EAC43E97BE451C0"></a></p>

<h5>5.2-3 PartitionDSCons</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; PartitionDSCons</code>( <var class="Arg">filter</var>, <var class="Arg">partition</var> )</td><td class="tdright">( constructor )</td></tr></table></div>
<p>Returns the union find structure of <var class="Arg">partition</var>.</p>

<p><a id="X85E4403778DC83A0" name="X85E4403778DC83A0"></a></p>

<h5>5.2-4 PartitionDS</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; PartitionDS</code>( <var class="Arg">filter</var>, <var class="Arg">n</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns the trivial partition of the set <code class="code">[1..n]</code>.</p>

<p><a id="X876385547BD14FDD" name="X876385547BD14FDD"></a></p>

<h5>5.2-5 PartitionDS</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; PartitionDS</code>( <var class="Arg">n</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns the trivial partition of the set <code class="code">[1..n]</code>.</p>

<p><a id="X7B0B222583188A6B" name="X7B0B222583188A6B"></a></p>

<h5>5.2-6 PartitionDS</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; PartitionDS</code>( <var class="Arg">filter</var>, <var class="Arg">partition</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns the union find structure of <var class="Arg">partition</var>.</p>

<p><a id="X8796F318875443C4" name="X8796F318875443C4"></a></p>

<h5>5.2-7 PartitionDS</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; PartitionDS</code>( <var class="Arg">partition</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns the union find structure of <var class="Arg">partition</var>.</p>

<p><a id="X8344F7007AD2C44B" name="X8344F7007AD2C44B"></a></p>

<h5>5.2-8 Representative</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; Representative</code>( <var class="Arg">unionfind</var>, <var class="Arg">k</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: a positive integer</p>

<p>Returns a canonical representative of the part of the partition that <var class="Arg">k</var> is contained in.</p>

<p><a id="X7FABCE367DC2F82B" name="X7FABCE367DC2F82B"></a></p>

<h5>5.2-9 Unite</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; Unite</code>( <var class="Arg">unionfind</var>, <var class="Arg">k1</var>, <var class="Arg">k2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Fuses the parts of the partition <var class="Arg">unionfind</var> containing <var class="Arg">k1</var> and <var class="Arg">k2</var>.</p>

<p><a id="X7A41C16979664337" name="X7A41C16979664337"></a></p>

<h5>5.2-10 RootsIteratorOfPartitionDS</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; RootsIteratorOfPartitionDS</code>( <var class="Arg">unionfind</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: an iterator</p>

<p>Returns an iterator that runs through canonical representatives of parts of the partition <var class="Arg">unionfind</var>.</p>

<p><a id="X7EA363F57FC53B4E" name="X7EA363F57FC53B4E"></a></p>

<h5>5.2-11 RootsOfPartitionDS</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; RootsOfPartitionDS</code>( <var class="Arg">unionfind</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A list.</p>

<p>Returns a list of the canonical representatives of the parts of the partition <var class="Arg">unionfind</var>.</p>

<p><a id="X83E6F1DE84ABFB69" name="X83E6F1DE84ABFB69"></a></p>

<h5>5.2-12 NumberParts</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; NumberParts</code>( <var class="Arg">unionfind</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: a positive integer</p>

<p>Returns the number of parts of the partition <var class="Arg">unionfind</var>.</p>

<p><a id="X8635245A83D7DC1B" name="X8635245A83D7DC1B"></a></p>

<h5>5.2-13 SizeUnderlyingSetDS</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; SizeUnderlyingSetDS</code>( <var class="Arg">unionfind</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: a positive integer</p>

<p>Returns the size of the underlying set of the partition <var class="Arg">unionfind</var>.</p>

<p><a id="X8716AC8F79820C86" name="X8716AC8F79820C86"></a></p>

<h5>5.2-14 PartsOfPartitionDS</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; PartsOfPartitionDS</code>( <var class="Arg">unionfind</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: a list of lists</p>

<p>Returns the partition <var class="Arg">unionfind</var> as a list of lists.</p>


<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap4_mj.html">[Previous Chapter]</a>    <a href="chap6_mj.html">[Next Chapter]</a>   </div>


<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a>  <a href="chap1_mj.html">1</a>  <a href="chap2_mj.html">2</a>  <a href="chap3_mj.html">3</a>  <a href="chap4_mj.html">4</a>  <a href="chap5_mj.html">5</a>  <a href="chap6_mj.html">6</a>  <a href="chap7_mj.html">7</a>  <a href="chap8_mj.html">8</a>  <a href="chap9_mj.html">9</a>  <a href="chap10_mj.html">10</a>  <a href="chap11_mj.html">11</a>  <a href="chap12_mj.html">12</a>  <a href="chapBib_mj.html">Bib</a>  <a href="chapInd_mj.html">Ind</a>  </div>

<hr />
<p class="foot">generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>