mooigraph
/
regraphlet


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393
							<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
      <title>GTL - Graph Template Library: pq_tree Class Reference</title>
      <link href="doxygen.css" rel="stylesheet" type="text/css">
  </head>
  <body>
    <p class="links">  
      <a href="../index.html">Home</a> |
      Documentation |
      <a href="../register.html">Download</a> |
      <a href="../platforms.html">Platforms</a> |
      <a href="../refer.html">Projects</a> |      
      <a href="../lists.html">Mailing Lists</a> |
      <a href="../history.html">Version History</a>
    </p>

<!-- Generated by Doxygen 1.5.3 -->
<div class="tabs">
  <ul>
    <li><a href="index.html"><span>Main&nbsp;Page</span></a></li>
    <li class="current"><a href="classes.html"><span>Classes</span></a></li>
    <li><a href="files.html"><span>Files</span></a></li>
    <li><a href="pages.html"><span>Related&nbsp;Pages</span></a></li>
  </ul>
</div>
<div class="tabs">
  <ul>
    <li><a href="classes.html"><span>Alphabetical&nbsp;List</span></a></li>
    <li><a href="annotated.html"><span>Class&nbsp;List</span></a></li>
    <li><a href="hierarchy.html"><span>Class&nbsp;Hierarchy</span></a></li>
    <li><a href="functions.html"><span>Class&nbsp;Members</span></a></li>
  </ul>
</div>
<h1>pq_tree Class Reference</h1><!-- doxytag: class="pq_tree" -->PQ-Trees.  
<a href="#_details">More...</a>
<p>

<p>
<a href="a00193.html">List of all members.</a><table border="0" cellpadding="0" cellspacing="0">
<tr><td></td></tr>
<tr><td colspan="2"><br><h2>Public Member Functions</h2></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="fea06921780eb07ddb36294b109964d0"></a><!-- doxytag: member="pq_tree::pq_tree" ref="fea06921780eb07ddb36294b109964d0" args="()" -->
&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00024.html#fea06921780eb07ddb36294b109964d0">pq_tree</a> ()</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Creates empty <a class="el" href="a00024.html" title="PQ-Trees.">pq_tree</a>. <br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00024.html#083c13459458a97d675f505f3fa03f20">pq_tree</a> (int id, <a class="el" href="a00020.html">node</a> n, const list&lt; pq_leaf * &gt; &amp;le)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Creates a PQ-tree consisting of a single P-node whose whose children are the leaves given in list <code>le</code>.  <a href="#083c13459458a97d675f505f3fa03f20"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="e6b44b3a6db8914beb368aee2bf7cc92"></a><!-- doxytag: member="pq_tree::~pq_tree" ref="e6b44b3a6db8914beb368aee2bf7cc92" args="()" -->
&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00024.html#e6b44b3a6db8914beb368aee2bf7cc92">~pq_tree</a> ()</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Deletes PQ-tree. <br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">bool&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00024.html#0fed41c20f026574fd1106c3e4ee7da6">reduce</a> (list&lt; pq_leaf * &gt; &amp;leaves)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Applies so called template matchings to the tree until either all leaves labeled with <code>id</code> are consecutive in all equivalent trees or until it is recognized that this can't be achieved.  <a href="#0fed41c20f026574fd1106c3e4ee7da6"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00024.html#04f82d883059692ae11bba21f774fe36">replace_pert</a> (int id, <a class="el" href="a00020.html">node</a> n, const list&lt; pq_leaf * &gt; &amp;le, <a class="el" href="a00022.html">planar_embedding</a> *em=0, list&lt; direction_indicator &gt; *dirs=0)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Replaces all the pertinent parts of the PQ-tree after a (successful) reduction by a new P-node, whose children are given in <code>le</code>.  <a href="#04f82d883059692ae11bba21f774fe36"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00024.html#37f329b20436db734e9a73e3840d7521">get_frontier</a> (<a class="el" href="a00022.html">planar_embedding</a> &amp;em, list&lt; direction_indicator &gt; &amp;dirs)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Scans whole tree from left to right and stores edges (in the graph) represented by the leaves in <code>em</code>.  <a href="#37f329b20436db734e9a73e3840d7521"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="1e2bdfb9af85972e9254260d74c63651"></a><!-- doxytag: member="pq_tree::reset" ref="1e2bdfb9af85972e9254260d74c63651" args="()" -->
void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00024.html#1e2bdfb9af85972e9254260d74c63651">reset</a> ()</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">After a (successful) reduction <code>reset</code> has to be called in order to prepare the tree for the next reduction. <br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">pq_node *&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00024.html#d5788903c1411626e69e49aaa1b6541b">get_fail</a> ()</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Returns the (PQ-) <a class="el" href="a00020.html" title="A node in a graph.">node</a> to which none of the template matchings were applicable.  <a href="#d5788903c1411626e69e49aaa1b6541b"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">bool&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00024.html#b320f9d84cba3198a95cc5f33fde0813">is_fail_root</a> ()</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Returns true iff fail is the root of the pertinent subtree.  <a href="#b320f9d84cba3198a95cc5f33fde0813"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">sons_iterator&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00024.html#5e0d37425b4bc803217f6ad387b0bb09">remove_dir_ind</a> (q_node *q_fail, sons_iterator s_it)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Remove a direction indicator among sons of a Q-node. Needed for computation of the obstruction set.  <a href="#5e0d37425b4bc803217f6ad387b0bb09"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">bool&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00024.html#6d6f83ee5dc56b3c49ae9c0ab447fec1">integrity_check</a> () const </td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Checks the structure of the tree.  <a href="#6d6f83ee5dc56b3c49ae9c0ab447fec1"></a><br></td></tr>
</table>
<hr><a name="_details"></a><h2>Detailed Description</h2>
PQ-Trees. 
<p>
<dl class="rcs" compact><dt><b>Date</b></dt><dd></dd></dl>
<dl class="rcs" compact><dt><b>Revision</b></dt><dd></dd></dl>
<hr><h2>Constructor &amp; Destructor Documentation</h2>
<a class="anchor" name="083c13459458a97d675f505f3fa03f20"></a><!-- doxytag: member="pq_tree::pq_tree" ref="083c13459458a97d675f505f3fa03f20" args="(int id, node n, const list&lt; pq_leaf * &gt; &amp;le)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">pq_tree::pq_tree           </td>
          <td>(</td>
          <td class="paramtype">int&nbsp;</td>
          <td class="paramname"> <em>id</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="a00020.html">node</a>&nbsp;</td>
          <td class="paramname"> <em>n</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const list&lt; pq_leaf * &gt; &amp;&nbsp;</td>
          <td class="paramname"> <em>le</em></td><td>&nbsp;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td><td width="100%"></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Creates a PQ-tree consisting of a single P-node whose whose children are the leaves given in list <code>le</code>. 
<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>id</em>&nbsp;</td><td>st-number of <code>n</code> </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>n</em>&nbsp;</td><td><a class="el" href="a00020.html" title="A node in a graph.">node</a> in the graph to which the P-node refers </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>le</em>&nbsp;</td><td>list of children </td></tr>
  </table>
</dl>

</div>
</div><p>
<hr><h2>Member Function Documentation</h2>
<a class="anchor" name="0fed41c20f026574fd1106c3e4ee7da6"></a><!-- doxytag: member="pq_tree::reduce" ref="0fed41c20f026574fd1106c3e4ee7da6" args="(list&lt; pq_leaf * &gt; &amp;leaves)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">bool pq_tree::reduce           </td>
          <td>(</td>
          <td class="paramtype">list&lt; pq_leaf * &gt; &amp;&nbsp;</td>
          <td class="paramname"> <em>leaves</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Applies so called template matchings to the tree until either all leaves labeled with <code>id</code> are consecutive in all equivalent trees or until it is recognized that this can't be achieved. 
<p>
This operation is guaranteed to perform in O(PPT), where PPT is the size of the so called <em>pruned</em> <em>pertinent</em> <em>subtree</em>, which can be constructed, by cutting away all the parts of the PQ-tree, that do not contain a leaf labeled with <code>id</code>.<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>leaves</em>&nbsp;</td><td>list of full leaves</td></tr>
  </table>
</dl>
<dl compact><dt><b>Return values:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>true</em>&nbsp;</td><td>if tree was successfully reduced </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>false</em>&nbsp;</td><td>if reduction failed </td></tr>
  </table>
</dl>

</div>
</div><p>
<a class="anchor" name="04f82d883059692ae11bba21f774fe36"></a><!-- doxytag: member="pq_tree::replace_pert" ref="04f82d883059692ae11bba21f774fe36" args="(int id, node n, const list&lt; pq_leaf * &gt; &amp;le, planar_embedding *em=0, list&lt; direction_indicator &gt; *dirs=0)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">void pq_tree::replace_pert           </td>
          <td>(</td>
          <td class="paramtype">int&nbsp;</td>
          <td class="paramname"> <em>id</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="a00020.html">node</a>&nbsp;</td>
          <td class="paramname"> <em>n</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const list&lt; pq_leaf * &gt; &amp;&nbsp;</td>
          <td class="paramname"> <em>le</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="a00022.html">planar_embedding</a> *&nbsp;</td>
          <td class="paramname"> <em>em</em> = <code>0</code>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">list&lt; direction_indicator &gt; *&nbsp;</td>
          <td class="paramname"> <em>dirs</em> = <code>0</code></td><td>&nbsp;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td><td width="100%"></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Replaces all the pertinent parts of the PQ-tree after a (successful) reduction by a new P-node, whose children are given in <code>le</code>. 
<p>
The edges (in the graph), represented by the leaves are stored in left to right order in <code>em</code>[n] They form (up to reversion) the so called upward-embedding. A direction indicator representing the direction in which the leaves were scanned is added to the sons of the root of the pertinent subtree (if neccessary). All direction indicators in the pertinent subtree are stored in <code>dirs</code>.<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>id</em>&nbsp;</td><td>st-number of <code>n</code> </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>n</em>&nbsp;</td><td><a class="el" href="a00020.html" title="A node in a graph.">node</a> in the graph to which the new P-node refers </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>le</em>&nbsp;</td><td>list of children </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>em</em>&nbsp;</td><td>planar embedding </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>dirs</em>&nbsp;</td><td>direction indicators in pertinent subtree </td></tr>
  </table>
</dl>

</div>
</div><p>
<a class="anchor" name="37f329b20436db734e9a73e3840d7521"></a><!-- doxytag: member="pq_tree::get_frontier" ref="37f329b20436db734e9a73e3840d7521" args="(planar_embedding &amp;em, list&lt; direction_indicator &gt; &amp;dirs)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">void pq_tree::get_frontier           </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="a00022.html">planar_embedding</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>em</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">list&lt; direction_indicator &gt; &amp;&nbsp;</td>
          <td class="paramname"> <em>dirs</em></td><td>&nbsp;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td><td width="100%"></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Scans whole tree from left to right and stores edges (in the graph) represented by the leaves in <code>em</code>. 
<p>
All direction indicators in the tree are stored in <code>dirs</code>. This is used in planarity test to get the upward embedding of the last <a class="el" href="a00020.html" title="A node in a graph.">node</a>, because no reduction is needed in this case since all leaves are labeled with the same number.<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>em</em>&nbsp;</td><td>planar embedding </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>dirs</em>&nbsp;</td><td>direction indicators in tree </td></tr>
  </table>
</dl>

</div>
</div><p>
<a class="anchor" name="d5788903c1411626e69e49aaa1b6541b"></a><!-- doxytag: member="pq_tree::get_fail" ref="d5788903c1411626e69e49aaa1b6541b" args="()" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">pq_node* pq_tree::get_fail           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Returns the (PQ-) <a class="el" href="a00020.html" title="A node in a graph.">node</a> to which none of the template matchings were applicable. 
<p>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>PQ-node at which the reduction failed </dd></dl>

</div>
</div><p>
<a class="anchor" name="b320f9d84cba3198a95cc5f33fde0813"></a><!-- doxytag: member="pq_tree::is_fail_root" ref="b320f9d84cba3198a95cc5f33fde0813" args="()" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">bool pq_tree::is_fail_root           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Returns true iff fail is the root of the pertinent subtree. 
<p>
<dl compact><dt><b>Return values:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>true</em>&nbsp;</td><td>iff reduction failed at the root of the pertinent subtree. </td></tr>
  </table>
</dl>

</div>
</div><p>
<a class="anchor" name="5e0d37425b4bc803217f6ad387b0bb09"></a><!-- doxytag: member="pq_tree::remove_dir_ind" ref="5e0d37425b4bc803217f6ad387b0bb09" args="(q_node *q_fail, sons_iterator s_it)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">sons_iterator pq_tree::remove_dir_ind           </td>
          <td>(</td>
          <td class="paramtype">q_node *&nbsp;</td>
          <td class="paramname"> <em>q_fail</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">sons_iterator&nbsp;</td>
          <td class="paramname"> <em>s_it</em></td><td>&nbsp;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td><td width="100%"></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Remove a direction indicator among sons of a Q-node. Needed for computation of the obstruction set. 
<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>q_fail</em>&nbsp;</td><td>the Q-node on which the reduction failed </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>the</em>&nbsp;</td><td>position of the direction indicator among the sons</td></tr>
  </table>
</dl>
<dl compact><dt><b>Return values:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>next</em>&nbsp;</td><td>valid sons iterator </td></tr>
  </table>
</dl>

</div>
</div><p>
<a class="anchor" name="6d6f83ee5dc56b3c49ae9c0ab447fec1"></a><!-- doxytag: member="pq_tree::integrity_check" ref="6d6f83ee5dc56b3c49ae9c0ab447fec1" args="() const " -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">bool pq_tree::integrity_check           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const</td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Checks the structure of the tree. 
<p>
<dl class="note" compact><dt><b>Note:</b></dt><dd>Use this only for debugging since it scans the whole tree, which isn't acceptable in terms of performance in most cases.</dd></dl>
<dl compact><dt><b>Return values:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>true</em>&nbsp;</td><td>iff tree passes checks </td></tr>
  </table>
</dl>

</div>
</div><p>
    <p class="links">
      <a href="http://www.uni-passau.de/">University of Passau</a>
      &nbsp;-&nbsp;
      <a href="http://www.fmi.uni-passau.de/">FMI</a>
      &nbsp;-&nbsp;
      <a href="http://www.fmi.uni-passau.de/fmi/lehrstuehle/brandenburg/">Theoretical
	Computer Science</a>
    </p>
  <div class="copyright">
      Design &copy; 2002, 2003 <a href="mailto:raitner@fmi.uni-passau.de">Marcus Raitner</a>,  University of Passau 
  </div>
</body>
</html>