mooigraph
/
regraphlet


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214
							<!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: algorithm 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>algorithm Class Reference</h1><!-- doxytag: class="algorithm" -->Abstract baseclass for all algoritm-classes.  
<a href="#_details">More...</a>
<p>
<div class="dynheader">
Inheritance diagram for algorithm:</div>
<div class="dynsection">
<p><center><img src="a00102.gif" border="0" usemap="#a00103" alt="Inheritance graph"></center>
<map name="a00103">
<area shape="rect" href="a00002.html" title="Bellman Ford algorithm." alt="" coords="147,5,245,29"><area shape="rect" href="a00003.html" title="Breadth&#45;First&#45;Search (BFS) algorithm." alt="" coords="176,53,216,77"><area shape="rect" href="a00005.html" title="Dijkstra&#39;s Algorithm for computing a shortest path from a single source to a..." alt="" coords="151,101,241,125"><area shape="rect" href="a00008.html" title="Depth&#45;First&#45;Search (DFS) algorithm." alt="" coords="176,149,216,173"><area shape="rect" href="a00009.html" title="Dijkstra&#39;s Algorithm for computing single source shortest path." alt="" coords="164,197,228,221"><area shape="rect" href="a00012.html" title="Heuristic graph bi&#45;partitioning algorithm (Fiduccia&#45;Mattheyses)." alt="" coords="149,245,243,269"><area shape="rect" href="a00015.html" title="Maximum flow algorithm (Edmonds&#45;Karp)." alt="" coords="152,293,240,317"><area shape="rect" href="a00016.html" title="Maximum flow algorithm (Malhotra, Kumar, Maheshwari)." alt="" coords="149,341,243,365"><area shape="rect" href="a00017.html" title="Maximum flow algorithm with shortest augmenting paths." alt="" coords="147,389,245,413"><area shape="rect" href="a00018.html" title="Kruskal&#39;s algorithm for finding minimal spanning tree of a graph." alt="" coords="159,437,233,461"><area shape="rect" href="a00023.html" title="Tests if a graph can be drawn on a plane without any edge crossings." alt="" coords="160,485,232,509"><area shape="rect" href="a00025.html" title="Heuristic graph bi&#45;partitioning algorithm (Wei&#45;Cheng)." alt="" coords="132,533,260,557"><area shape="rect" href="a00026.html" title="ST&#45;number algorithm." alt="" coords="153,581,239,605"><area shape="rect" href="a00004.html" title="Biconnectivity&#45;test and low&#45;numbers." alt="" coords="309,101,413,125"><area shape="rect" href="a00007.html" title="Connected components algorithm." alt="" coords="315,149,408,173"><area shape="rect" href="a00028.html" title="Topological sorting." alt="" coords="329,197,393,221"></map>
<center><font size="2">[<a href="graph_legend.html">legend</a>]</font></center></div>

<p>
<a href="a00104.html">List of all members.</a><table border="0" cellpadding="0" cellspacing="0">
<tr><td></td></tr>
<tr><td colspan="2"><br><h2>Public Types</h2></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">enum &nbsp;</td><td class="memItemRight" valign="bottom">{ <a class="el" href="a00001.html#f1a0078e153aa99c24f9bdf0d97f67105114c20e4a96a76b5de9f28bf15e282b">GTL_OK</a> =  1, 
<a class="el" href="a00001.html#f1a0078e153aa99c24f9bdf0d97f67106fcf574690bbd6cf710837a169510dd7">GTL_ERROR</a> =  0
 }</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Return values for <a class="el" href="a00001.html#76361fb03ad1cf643affc51821e43bed" title="Checks whether all preconditions are satisfied.">algorithm::check</a> and <a class="el" href="a00001.html#734b189509a8d6b56b65f8ff772d43ca" title="Applies algorithm to graph g.">algorithm::run</a>.  <a href="a00001.html#f1a0078e153aa99c24f9bdf0d97f6710">More...</a><br></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="b79e1ddec2f2afdf4b36b10724db8b15"></a><!-- doxytag: member="algorithm::algorithm" ref="b79e1ddec2f2afdf4b36b10724db8b15" args="()" -->
&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#b79e1ddec2f2afdf4b36b10724db8b15">algorithm</a> ()</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Creates an <a class="el" href="a00001.html" title="Abstract baseclass for all algoritm-classes.">algorithm</a> object. <br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="dca9b1e7fa3afd914519a9dbb44e9fd5"></a><!-- doxytag: member="algorithm::~algorithm" ref="dca9b1e7fa3afd914519a9dbb44e9fd5" args="()" -->
virtual&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#dca9b1e7fa3afd914519a9dbb44e9fd5">~algorithm</a> ()</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Destroys the <a class="el" href="a00001.html" title="Abstract baseclass for all algoritm-classes.">algorithm</a> object. <br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">virtual int&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#734b189509a8d6b56b65f8ff772d43ca">run</a> (<a class="el" href="a00014.html">graph</a> &amp;g)=0</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Applies algorithm to graph g.  <a href="#734b189509a8d6b56b65f8ff772d43ca"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">virtual int&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00001.html#76361fb03ad1cf643affc51821e43bed">check</a> (<a class="el" href="a00014.html">graph</a> &amp;g)=0</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Checks whether all preconditions are satisfied.  <a href="#76361fb03ad1cf643affc51821e43bed"></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="a00001.html#21aba63d066ae7897de6ca7d8425c408">reset</a> ()=0</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Resets algorithm.  <a href="#21aba63d066ae7897de6ca7d8425c408"></a><br></td></tr>
</table>
<hr><a name="_details"></a><h2>Detailed Description</h2>
Abstract baseclass for all algoritm-classes. 
<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>Member Enumeration Documentation</h2>
<a class="anchor" name="f1a0078e153aa99c24f9bdf0d97f6710"></a><!-- doxytag: member="algorithm::@0" ref="f1a0078e153aa99c24f9bdf0d97f6710" args="" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">anonymous enum          </td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Return values for <a class="el" href="a00001.html#76361fb03ad1cf643affc51821e43bed" title="Checks whether all preconditions are satisfied.">algorithm::check</a> and <a class="el" href="a00001.html#734b189509a8d6b56b65f8ff772d43ca" title="Applies algorithm to graph g.">algorithm::run</a>. 
<p>
<dl compact><dt><b>Enumerator: </b></dt><dd>
<table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"><em><a class="anchor" name="f1a0078e153aa99c24f9bdf0d97f67105114c20e4a96a76b5de9f28bf15e282b"></a><!-- doxytag: member="GTL_OK" ref="f1a0078e153aa99c24f9bdf0d97f67105114c20e4a96a76b5de9f28bf15e282b" args="" -->GTL_OK</em>&nbsp;</td><td>
Used as (positive) return value of <a class="el" href="a00001.html#76361fb03ad1cf643affc51821e43bed" title="Checks whether all preconditions are satisfied.">algorithm::check</a> and <a class="el" href="a00001.html#734b189509a8d6b56b65f8ff772d43ca" title="Applies algorithm to graph g.">algorithm::run</a>. </td></tr>
<tr><td valign="top"><em><a class="anchor" name="f1a0078e153aa99c24f9bdf0d97f67106fcf574690bbd6cf710837a169510dd7"></a><!-- doxytag: member="GTL_ERROR" ref="f1a0078e153aa99c24f9bdf0d97f67106fcf574690bbd6cf710837a169510dd7" args="" -->GTL_ERROR</em>&nbsp;</td><td>
Used as (negative) return value of <a class="el" href="a00001.html#76361fb03ad1cf643affc51821e43bed" title="Checks whether all preconditions are satisfied.">algorithm::check</a> and <a class="el" href="a00001.html#734b189509a8d6b56b65f8ff772d43ca" title="Applies algorithm to graph g.">algorithm::run</a>. </td></tr>
</table>
</dl>

</div>
</div><p>
<hr><h2>Member Function Documentation</h2>
<a class="anchor" name="734b189509a8d6b56b65f8ff772d43ca"></a><!-- doxytag: member="algorithm::run" ref="734b189509a8d6b56b65f8ff772d43ca" args="(graph &amp;g)=0" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">virtual int algorithm::run           </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> [pure virtual]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Applies algorithm to graph g. 
<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 </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><a class="el" href="a00001.html#f1a0078e153aa99c24f9bdf0d97f67105114c20e4a96a76b5de9f28bf15e282b">algorithm::GTL_OK</a></em>&nbsp;</td><td>on success </td></tr>
    <tr><td valign="top"></td><td valign="top"><em><a class="el" href="a00001.html#f1a0078e153aa99c24f9bdf0d97f67106fcf574690bbd6cf710837a169510dd7">algorithm::GTL_ERROR</a></em>&nbsp;</td><td>otherwise </td></tr>
  </table>
</dl>

<p>Implemented in <a class="el" href="a00002.html#226308389f3c36dfc02768c09f777a3b">bellman_ford</a>, <a class="el" href="a00003.html#06ae16bd0f3bb2f8eb6b3e36659ba82e">bfs</a>, <a class="el" href="a00005.html#1d2f36d3977ef90285442a269a03b919">bid_dijkstra</a>, <a class="el" href="a00008.html#f0863b8974d5fd58cd0375c78ed8163b">dfs</a>, <a class="el" href="a00009.html#7b30f3d8ad42baae27989bc14befe0d0">dijkstra</a>, <a class="el" href="a00012.html#015b171fcaa01973ebe6c6a46a727097">fm_partition</a>, <a class="el" href="a00015.html#0a4391b9093d6966b47c023a555099e2">maxflow_ff</a>, <a class="el" href="a00016.html#07c7cb1ae5db23d87cf49ce7769b2814">maxflow_pp</a>, <a class="el" href="a00017.html#b4305a2bb370ad9c43cc68d339b2dda0">maxflow_sap</a>, <a class="el" href="a00018.html#c025e8dad0db7a6a1e0e7b476b547802">min_tree</a>, <a class="el" href="a00023.html#93232e765c08dd2a4c00d192bb48b5fc">planarity</a>, <a class="el" href="a00025.html#4ab180ca4cf57c811e3478c3de4c4dc3">ratio_cut_partition</a>, and <a class="el" href="a00026.html#f902a0c05d07d47b587e8f7a6b7beaa1">st_number</a>.</p>

</div>
</div><p>
<a class="anchor" name="76361fb03ad1cf643affc51821e43bed"></a><!-- doxytag: member="algorithm::check" ref="76361fb03ad1cf643affc51821e43bed" args="(graph &amp;g)=0" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">virtual int algorithm::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> [pure virtual]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Checks whether all preconditions are satisfied. 
<p>
<em>Please</em> <em>note:</em> It is definitly required (and <a class="el" href="a00001.html#734b189509a8d6b56b65f8ff772d43ca" title="Applies algorithm to graph g.">run</a> relies on it), that this method was called in advance.<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 </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><a class="el" href="a00001.html#f1a0078e153aa99c24f9bdf0d97f67105114c20e4a96a76b5de9f28bf15e282b">algorithm::GTL_OK</a></em>&nbsp;</td><td>if algorithm can be applied </td></tr>
    <tr><td valign="top"></td><td valign="top"><em><a class="el" href="a00001.html#f1a0078e153aa99c24f9bdf0d97f67106fcf574690bbd6cf710837a169510dd7">algorithm::GTL_ERROR</a></em>&nbsp;</td><td>otherwise. </td></tr>
  </table>
</dl>

<p>Implemented in <a class="el" href="a00002.html#9da2fb7d20ef1f726ee935474302d80b">bellman_ford</a>, <a class="el" href="a00003.html#6dd7e852f7768814aafba8962befca56">bfs</a>, <a class="el" href="a00004.html#5db0b38d8d01af52720d6941103de4f2">biconnectivity</a>, <a class="el" href="a00005.html#92c6790f5ea4a7417b593342c58a953b">bid_dijkstra</a>, <a class="el" href="a00007.html#060c996e815c56cbab61f36d57fc3545">components</a>, <a class="el" href="a00008.html#908f4ea617ed59767ed334b39a2771d0">dfs</a>, <a class="el" href="a00009.html#fb4aff7134caa15dcce88668c54899aa">dijkstra</a>, <a class="el" href="a00012.html#21f4498904415ef1d88354517e7be95e">fm_partition</a>, <a class="el" href="a00015.html#b79864f21b29192bc9a81ebfa00cd262">maxflow_ff</a>, <a class="el" href="a00016.html#05bb51b4f7ab213b6624188a0e64a025">maxflow_pp</a>, <a class="el" href="a00017.html#f94644633a5cfb386de082cc02febef3">maxflow_sap</a>, <a class="el" href="a00018.html#d87b1bfbc687ad943c07538fa0c3d270">min_tree</a>, <a class="el" href="a00023.html#e06c471d957a116aad14e338c341f8b1">planarity</a>, <a class="el" href="a00025.html#c4bdc17520a51ffda1a51294ed8e83ef">ratio_cut_partition</a>, <a class="el" href="a00026.html#2aad4550b821c52d6998bff35fd8648f">st_number</a>, and <a class="el" href="a00028.html#d83c28909478d35c737a2c70506407dd">topsort</a>.</p>

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

<p>
Resets algorithm. 
<p>
Prepares the algorithm to be applied to another graph. <em>Please</em> <em>note:</em> The options an algorithm may support do <em>not</em> get reset by this. It is just to reset internally used datastructures. 
<p>Implemented in <a class="el" href="a00002.html#7d28afa62ce8068c4d0f2d1f96136fd6">bellman_ford</a>, <a class="el" href="a00003.html#355b797efe46ab262e71c05ba75de940">bfs</a>, <a class="el" href="a00004.html#a1a4b091fd8b2bbea2b36b91bab713af">biconnectivity</a>, <a class="el" href="a00005.html#6ed0e7e34862ca44ae4f83eb3081ae3a">bid_dijkstra</a>, <a class="el" href="a00007.html#1c1fb446e7a6bb18fbc8d2cbc82d90be">components</a>, <a class="el" href="a00008.html#1c893f699517cc72624cf171b7bc4da4">dfs</a>, <a class="el" href="a00009.html#16f9249e8cce25cbd0a3297fc8fa9a44">dijkstra</a>, <a class="el" href="a00012.html#61c77e15f54e288a192d3710ed9a2fc4">fm_partition</a>, <a class="el" href="a00015.html#8c87fccfda3fa1a320c4a280b2752ae9">maxflow_ff</a>, <a class="el" href="a00016.html#039b1c893b2197a1f3fe0586c2d3e802">maxflow_pp</a>, <a class="el" href="a00017.html#6c35136743e38cee6c31e18cf8ca20be">maxflow_sap</a>, <a class="el" href="a00018.html#3c4b17c455dd77b4120ec5564a4ac428">min_tree</a>, <a class="el" href="a00023.html#ca500e3d46a99c6231aff86afa2a71b1">planarity</a>, <a class="el" href="a00025.html#941fa7af07b89ba98454bbf31140061b">ratio_cut_partition</a>, <a class="el" href="a00026.html#e6f86706b8ae3495d3794b8c684fff0f">st_number</a>, and <a class="el" href="a00028.html#403076f952ef640cb3f52c9b1a495a1f">topsort</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>