mooigraph
/
regraphlet


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392
							<!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: topsort 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>topsort Class Reference</h1><!-- doxytag: class="topsort" --><!-- doxytag: inherits="dfs" -->Topological sorting.  
<a href="#_details">More...</a>
<p>
<div class="dynheader">
Inheritance diagram for topsort:</div>
<div class="dynsection">
<p><center><img src="a00205.gif" border="0" usemap="#a00206" alt="Inheritance graph"></center>
<map name="a00206">
<area shape="rect" href="a00008.html" title="Depth&#45;First&#45;Search (DFS) algorithm." alt="" coords="24,81,64,105"><area shape="rect" href="a00001.html" title="Abstract baseclass for all algoritm&#45;classes." alt="" coords="5,7,83,31"></map>
<center><font size="2">[<a href="graph_legend.html">legend</a>]</font></center></div>
<div class="dynheader">
Collaboration diagram for topsort:</div>
<div class="dynsection">
<p><center><img src="a00207.gif" border="0" usemap="#a00208" alt="Collaboration graph"></center>
<map name="a00208">
<area shape="rect" href="a00008.html" title="Depth&#45;First&#45;Search (DFS) algorithm." alt="" coords="665,119,705,143"><area shape="rect" href="a00001.html" title="Abstract baseclass for all algoritm&#45;classes." alt="" coords="401,101,479,125"><area shape="rect" href="a00020.html" title="A node in a graph." alt="" coords="415,188,465,212"><area shape="rect" title="start" alt="" coords="463,188,471,196"><area shape="rect" title="start" alt="" coords="661,132,669,140"><area shape="rect" title="int_node" alt="" coords="411,185,419,193"><area shape="rect" title="int_node" alt="" coords="463,185,471,193"><area shape="rect" href="a00021.html" title="node_map\&lt; int \&gt;" alt="" coords="379,237,501,261"><area shape="rect" title="top_numbers" alt="" coords="497,240,505,248"><area shape="rect" title="top_numbers" alt="" coords="772,213,780,221"><area shape="rect" title="comp_number\ndfs_number" alt="" coords="497,235,505,243"><area shape="rect" title="comp_number\ndfs_number" alt="" coords="673,140,681,148"><area shape="rect" href="a00019.html" title="ne_map\&lt; node, int, graph, allocator\&lt; int \&gt; \&gt;" alt="" coords="21,237,304,261"><area shape="rect" href="a00011.html" title="edge_map\&lt; int \&gt;" alt="" coords="379,5,501,29"><area shape="rect" title="used" alt="" coords="497,20,505,28"><area shape="rect" title="used" alt="" coords="673,115,681,123"><area shape="rect" href="a00019.html" title="ne_map\&lt; edge, int, graph, allocator\&lt; int \&gt; \&gt;" alt="" coords="21,5,304,29"><area shape="rect" href="a00021.html" title="node_map\&lt; node \&gt;" alt="" coords="371,53,509,77"><area shape="rect" title="preds" alt="" coords="505,72,513,80"><area shape="rect" title="preds" alt="" coords="661,116,669,124"><area shape="rect" href="a00019.html" title="ne_map\&lt; node, node, graph, allocator\&lt; node \&gt; \&gt;" alt="" coords="5,53,320,77"></map>
<center><font size="2">[<a href="graph_legend.html">legend</a>]</font></center></div>

<p>
<a href="a00209.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">&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00028.html#76a9055969b9dbf006320040be9fd5e6">topsort</a> ()</td></tr>

<tr><td class="memItemLeft" nowrap align="right" valign="top">int&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00028.html#71069dab2159b75a324f3b8a44a88ced">top_num</a> (const <a class="el" href="a00020.html">node</a> &amp;n) const </td></tr>

<tr><td class="memItemLeft" nowrap align="right" valign="top">bool&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00028.html#6df72e7e38299c30695e9391c3b04383">is_acyclic</a> () const </td></tr>

<tr><td class="memItemLeft" nowrap align="right" valign="top">topsort_iterator&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00028.html#f2b446d051fceb0df31df7057e03025b">top_order_begin</a> () const </td></tr>

<tr><td class="memItemLeft" nowrap align="right" valign="top">topsort_iterator&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00028.html#b4d0debf92c9e5eeceec48856af4b329">top_order_end</a> () const </td></tr>

<tr><td class="memItemLeft" nowrap align="right" valign="top">virtual int&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00028.html#d83c28909478d35c737a2c70506407dd">check</a> (<a class="el" href="a00014.html">graph</a> &amp;G)</td></tr>

<tr><td class="memItemLeft" nowrap align="right" valign="top">virtual void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00028.html#403076f952ef640cb3f52c9b1a495a1f">reset</a> ()</td></tr>

<tr><td class="memItemLeft" nowrap align="right" valign="top">virtual void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00028.html#1cd92994d564acf79c37e40bdb292827">init_handler</a> (<a class="el" href="a00014.html">graph</a> &amp;G)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Handler called before the start of DFS.  <a href="#1cd92994d564acf79c37e40bdb292827"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">virtual void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00028.html#4401a056e4310ca7eca47587f7da5daf">leave_handler</a> (<a class="el" href="a00014.html">graph</a> &amp;, <a class="el" href="a00020.html">node</a> &amp;, <a class="el" href="a00020.html">node</a> &amp;)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Handler called after all the adjacent edges of <em>n</em> have been examined.  <a href="#4401a056e4310ca7eca47587f7da5daf"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">virtual void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00028.html#97074494bbdb878a1e3b6da232e965dd">old_adj_node_handler</a> (<a class="el" href="a00014.html">graph</a> &amp;, <a class="el" href="a00010.html">edge</a> &amp;, <a class="el" href="a00020.html">node</a> &amp;)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Handler called when a already marked node <em>n</em> connected to the actual node by <em>e</em> is found during the search of all adjacent edges of the actual node.  <a href="#97074494bbdb878a1e3b6da232e965dd"></a><br></td></tr>
</table>
<hr><a name="_details"></a><h2>Detailed Description</h2>
Topological sorting. 
<p>
Assigns to each <a class="el" href="a00020.html" title="A node in a graph.">node</a> <code>n</code> a number <code>top_num</code> such that for every <a class="el" href="a00010.html" title="An edge in a graph.">edge</a> <code>(u,v)</code> <code>top_num[u]</code> &lt; <code>top_num[v]</code>, if possible, i.e. iff the directed <a class="el" href="a00014.html" title="A directed or undirected graph.">graph</a> is acyclic.<p>
Similar to the testing of <a class="el" href="a00004.html" title="Biconnectivity-test and low-numbers.">biconnectivity</a>, which extends DFS to calculate low-numbers, the topsort-algorithm extends DFS to calculate the new numbering (and thus to test whether such a numbering is possible).<p>
In order to traverse all the nodes in the order of its top-numbers, a new iterator, <code>topsort_iterator</code> is provided. <hr><h2>Constructor &amp; Destructor Documentation</h2>
<a class="anchor" name="76a9055969b9dbf006320040be9fd5e6"></a><!-- doxytag: member="topsort::topsort" ref="76a9055969b9dbf006320040be9fd5e6" args="()" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">topsort::topsort           </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>
default constructor; enables scanning of the whole_graph.<p>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00008.html#2399808134dbabf6aa5e1b2e35a73954" title="Constructor.">dfs::dfs</a> </dd></dl>

</div>
</div><p>
<hr><h2>Member Function Documentation</h2>
<a class="anchor" name="71069dab2159b75a324f3b8a44a88ced"></a><!-- doxytag: member="topsort::top_num" ref="71069dab2159b75a324f3b8a44a88ced" args="(const node &amp;n) const " -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">int topsort::top_num           </td>
          <td>(</td>
          <td class="paramtype">const <a class="el" href="a00020.html">node</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>n</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const<code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Number in topological order.<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>&lt;code&gt;n&lt;/code&gt;</em>&nbsp;</td><td><a class="el" href="a00020.html" title="A node in a graph.">node</a>. </td></tr>
  </table>
</dl>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>number in topological order. </dd></dl>

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

<p>
Tests if <a class="el" href="a00014.html" title="A directed or undirected graph.">graph</a> was acyclic.<p>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>true iff <a class="el" href="a00014.html" title="A directed or undirected graph.">graph</a> was acyclic. </dd></dl>

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

<p>
Iterate through nodes in topsort-order.<p>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>start-iterator. </dd></dl>

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

<p>
Iterate through nodes in topsort-order.<p>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>end-iterator. </dd></dl>

</div>
</div><p>
<a class="anchor" name="d83c28909478d35c737a2c70506407dd"></a><!-- doxytag: member="topsort::check" ref="d83c28909478d35c737a2c70506407dd" args="(graph &amp;G)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">virtual int topsort::check           </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="a00014.html">graph</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>G</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [virtual]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Preconditions: <ul>
<li>
<code>G</code> is directed. </li>
<li>
DFS may be applied </li>
</ul>
<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>&lt;code&gt;G&lt;/code&gt;</em>&nbsp;</td><td><a class="el" href="a00014.html" title="A directed or undirected graph.">graph</a>. </td></tr>
  </table>
</dl>
<dl class="return" compact><dt><b>Returns:</b></dt><dd><code><a class="el" href="a00001.html#f1a0078e153aa99c24f9bdf0d97f67105114c20e4a96a76b5de9f28bf15e282b">algorithm::GTL_OK</a></code> if <a class="el" href="a00028.html" title="Topological sorting.">topsort</a> may be applied to <code>G</code>. </dd></dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00008.html#908f4ea617ed59767ed334b39a2771d0" title="Checks whether the preconditions for DFS are satisfied.">dfs::check</a> </dd></dl>

<p>Reimplemented from <a class="el" href="a00008.html#908f4ea617ed59767ed334b39a2771d0">dfs</a>.</p>

</div>
</div><p>
<a class="anchor" name="403076f952ef640cb3f52c9b1a495a1f"></a><!-- doxytag: member="topsort::reset" ref="403076f952ef640cb3f52c9b1a495a1f" args="()" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">virtual void topsort::reset           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [virtual]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Reset <dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00008.html#1c893f699517cc72624cf171b7bc4da4" title="Resets algorithm.">dfs::reset</a> </dd></dl>

<p>Reimplemented from <a class="el" href="a00008.html#1c893f699517cc72624cf171b7bc4da4">dfs</a>.</p>

</div>
</div><p>
<a class="anchor" name="1cd92994d564acf79c37e40bdb292827"></a><!-- doxytag: member="topsort::init_handler" ref="1cd92994d564acf79c37e40bdb292827" args="(graph &amp;G)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">virtual void topsort::init_handler           </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="a00014.html">graph</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>G</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [virtual]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Handler called before the start of DFS. 
<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>G</em>&nbsp;</td><td>graph for which DFS was invoked. </td></tr>
  </table>
</dl>

<p>Reimplemented from <a class="el" href="a00008.html#cc82574cd42ab8256e685374bee5fabb">dfs</a>.</p>

</div>
</div><p>
<a class="anchor" name="4401a056e4310ca7eca47587f7da5daf"></a><!-- doxytag: member="topsort::leave_handler" ref="4401a056e4310ca7eca47587f7da5daf" args="(graph &amp;, node &amp;, node &amp;)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">virtual void topsort::leave_handler           </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="a00014.html">graph</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>G</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="a00020.html">node</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>n</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="a00020.html">node</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>f</em></td><td>&nbsp;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td><td width="100%"><code> [virtual]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Handler called after all the adjacent edges of <em>n</em> have been examined. 
<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>G</em>&nbsp;</td><td>graph for which DFS was invoked. </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>n</em>&nbsp;</td><td>actual node. </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>f</em>&nbsp;</td><td>predecessor. </td></tr>
  </table>
</dl>

<p>Reimplemented from <a class="el" href="a00008.html#8071fc4e82deff7ceb2790cd4eb42280">dfs</a>.</p>

</div>
</div><p>
<a class="anchor" name="97074494bbdb878a1e3b6da232e965dd"></a><!-- doxytag: member="topsort::old_adj_node_handler" ref="97074494bbdb878a1e3b6da232e965dd" args="(graph &amp;, edge &amp;, node &amp;)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">virtual void topsort::old_adj_node_handler           </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="a00014.html">graph</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>G</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="a00010.html">edge</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>e</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="a00020.html">node</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>n</em></td><td>&nbsp;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td><td width="100%"><code> [virtual]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Handler called when a already marked node <em>n</em> connected to the actual node by <em>e</em> is found during the search of all adjacent edges of the actual node. 
<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>G</em>&nbsp;</td><td>graph for which DFS was invoked. </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>e</em>&nbsp;</td><td>edge connecting the actual node to the old one. </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>n</em>&nbsp;</td><td>used node. </td></tr>
  </table>
</dl>

<p>Reimplemented from <a class="el" href="a00008.html#df1c667188e632761c63f529537c544c">dfs</a>.</p>

</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>