mooigraph
/
regraphlet


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210
							<!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: dfs.h Source File</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><a href="classes.html"><span>Classes</span></a></li>
    <li class="current"><a href="files.html"><span>Files</span></a></li>
    <li><a href="pages.html"><span>Related&nbsp;Pages</span></a></li>
  </ul>
</div>
<h1>dfs.h</h1><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">//==========================================================================</span>
<a name="l00002"></a>00002 <span class="comment">//</span>
<a name="l00003"></a>00003 <span class="comment">//   dfs.h</span>
<a name="l00004"></a>00004 <span class="comment">//</span>
<a name="l00005"></a>00005 <span class="comment">//==========================================================================</span>
<a name="l00006"></a>00006 <span class="comment">// $Id: dfs.h,v 1.25 2003/03/24 15:58:54 raitner Exp $</span>
<a name="l00007"></a>00007 
<a name="l00008"></a>00008 <span class="preprocessor">#ifndef GTL_DFS_H</span>
<a name="l00009"></a>00009 <span class="preprocessor"></span><span class="preprocessor">#define GTL_DFS_H</span>
<a name="l00010"></a>00010 <span class="preprocessor"></span>
<a name="l00011"></a>00011 <span class="preprocessor">#include &lt;GTL/GTL.h&gt;</span>
<a name="l00012"></a>00012 <span class="preprocessor">#include &lt;GTL/algorithm.h&gt;</span>
<a name="l00013"></a>00013 
<a name="l00014"></a>00014 __GTL_BEGIN_NAMESPACE
<a name="l00015"></a>00015 
<a name="l00087"></a><a class="code" href="a00008.html">00087</a> <span class="keyword">class </span>GTL_EXTERN <a class="code" href="a00008.html" title="Depth-First-Search (DFS) algorithm.">dfs</a> : <span class="keyword">public</span> <a class="code" href="a00001.html" title="Abstract baseclass for all algoritm-classes.">algorithm</a> 
<a name="l00088"></a>00088 {
<a name="l00089"></a>00089 <span class="keyword">public</span>:
<a name="l00093"></a>00093     <a class="code" href="a00008.html" title="Depth-First-Search (DFS) algorithm.">dfs</a> ();
<a name="l00094"></a>00094 
<a name="l00095"></a>00095 
<a name="l00099"></a>00099     <span class="keyword">virtual</span> ~<a class="code" href="a00008.html" title="Depth-First-Search (DFS) algorithm.">dfs</a> ();
<a name="l00100"></a>00100     
<a name="l00101"></a>00101     <span class="keywordtype">int</span> <a class="code" href="a00001.html#734b189509a8d6b56b65f8ff772d43ca" title="Applies algorithm to graph g.">run</a> (<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G);
<a name="l00102"></a>00102 
<a name="l00114"></a>00114     <span class="keyword">virtual</span> <span class="keywordtype">int</span> <a class="code" href="a00001.html#76361fb03ad1cf643affc51821e43bed" title="Checks whether all preconditions are satisfied.">check</a> (<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G);
<a name="l00115"></a>00115 
<a name="l00116"></a>00116     <span class="keyword">virtual</span> <span class="keywordtype">void</span> <a class="code" href="a00001.html#21aba63d066ae7897de6ca7d8425c408" title="Resets algorithm.">reset</a> ();
<a name="l00117"></a>00117 
<a name="l00118"></a>00118 
<a name="l00119"></a>00119     <span class="comment">//---------------------------------------------------------------------</span>
<a name="l00120"></a>00120     <span class="comment">//   Parameters</span>
<a name="l00121"></a>00121     <span class="comment">//---------------------------------------------------------------------</span>
<a name="l00122"></a>00122     
<a name="l00128"></a><a class="code" href="a00008.html#ad21fd0d3036350fd341f877d5747852">00128</a>     <span class="keywordtype">void</span> start_node (<span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp; n) 
<a name="l00129"></a>00129         { start = n; }
<a name="l00130"></a>00130 
<a name="l00136"></a><a class="code" href="a00008.html#0282acea81eb9c0d02ceea109fc25f10">00136</a>     <a class="code" href="a00020.html" title="A node in a graph.">node</a> start_node ()<span class="keyword"> const </span>{<span class="keywordflow">return</span> start;}
<a name="l00137"></a>00137     
<a name="l00156"></a><a class="code" href="a00008.html#a7c864a6f3a120720138b187b3ed95b5">00156</a>     <span class="keywordtype">void</span> scan_whole_graph (<span class="keywordtype">bool</span> <span class="keyword">set</span>) {whole_graph = <span class="keyword">set</span>;}
<a name="l00157"></a>00157     
<a name="l00165"></a><a class="code" href="a00008.html#121e68fa166dc109b9f59f5bad3b0a8f">00165</a>     <span class="keywordtype">bool</span> scan_whole_graph ()<span class="keyword"> const </span>{<span class="keywordflow">return</span> whole_graph;}
<a name="l00166"></a>00166 
<a name="l00173"></a>00173     <span class="keywordtype">void</span> calc_comp_num (<span class="keywordtype">bool</span> <span class="keyword">set</span>);
<a name="l00174"></a>00174 
<a name="l00181"></a><a class="code" href="a00008.html#ba070824c0cd45651083a9c62ac34c1a">00181</a>     <span class="keywordtype">bool</span> calc_comp_num ()<span class="keyword"> const </span>{<span class="keywordflow">return</span> comp_number != 0;}
<a name="l00182"></a>00182 
<a name="l00183"></a>00183 
<a name="l00193"></a>00193     <span class="keywordtype">void</span> store_preds (<span class="keywordtype">bool</span> <span class="keyword">set</span>);
<a name="l00194"></a>00194 
<a name="l00201"></a><a class="code" href="a00008.html#5fdfdf59dbd7616167b47013df79364b">00201</a>     <span class="keywordtype">bool</span> store_preds ()<span class="keyword"> const </span>{<span class="keywordflow">return</span> preds != 0;}
<a name="l00202"></a>00202     
<a name="l00213"></a>00213     <span class="keywordtype">void</span> store_non_tree_edges (<span class="keywordtype">bool</span> <span class="keyword">set</span>);
<a name="l00214"></a>00214 
<a name="l00222"></a><a class="code" href="a00008.html#c81e86d2e2b8f4ef5e34470486717dcf">00222</a>     <span class="keywordtype">bool</span> store_non_tree_edges ()<span class="keyword"> const </span>{<span class="keywordflow">return</span> back_edges != 0;}
<a name="l00223"></a>00223 
<a name="l00224"></a>00224     <span class="comment">//---------------------------------------------------------------------</span>
<a name="l00225"></a>00225     <span class="comment">//   Access </span>
<a name="l00226"></a>00226     <span class="comment">//----------------------------------------------------------------------</span>
<a name="l00227"></a>00227 
<a name="l00234"></a><a class="code" href="a00008.html#174338f8e57a5ba93c08469c2a531a8b">00234</a>     <span class="keywordtype">bool</span> reached (<span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp; n)<span class="keyword"> const</span>
<a name="l00235"></a>00235 <span class="keyword">        </span>{<span class="keywordflow">return</span> dfs_number[n] != 0;}
<a name="l00236"></a>00236 
<a name="l00246"></a><a class="code" href="a00008.html#9309a0573f52643196bef32251cf96df">00246</a>     <span class="keywordtype">int</span> dfs_num (<span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp; n)<span class="keyword"> const </span>
<a name="l00247"></a>00247 <span class="keyword">        </span>{<span class="keywordflow">return</span> dfs_number[n];}
<a name="l00248"></a>00248 
<a name="l00258"></a><a class="code" href="a00008.html#5aa6d81775ad13d92c6e5a7661041866">00258</a>     <span class="keywordtype">int</span> operator[] (<span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp; n)<span class="keyword"> const </span>
<a name="l00259"></a>00259 <span class="keyword">        </span>{<span class="keywordflow">return</span> dfs_number[n];}
<a name="l00260"></a>00260 
<a name="l00269"></a><a class="code" href="a00008.html#1b1c940ed5df7e7b8f825ede1d37f364">00269</a>     <span class="keywordtype">int</span> comp_num (<span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp; n)<span class="keyword"> const</span>
<a name="l00270"></a>00270 <span class="keyword">        </span>{assert (comp_number); <span class="keywordflow">return</span> (*comp_number)[n];}
<a name="l00271"></a>00271 
<a name="l00282"></a><a class="code" href="a00008.html#7c4dc665c18e987c1eb61b69cb582d4f">00282</a>     <a class="code" href="a00020.html" title="A node in a graph.">node</a> father (<span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp; n)<span class="keyword"> const</span>
<a name="l00283"></a>00283 <span class="keyword">        </span>{assert (preds); <span class="keywordflow">return</span> (*preds)[n];}
<a name="l00284"></a>00284 
<a name="l00288"></a><a class="code" href="a00008.html#0eee0ddec5343c05f617d6d7aabb6d19">00288</a>     <span class="keyword">typedef</span> list&lt;edge&gt;::const_iterator tree_edges_iterator;
<a name="l00289"></a>00289 
<a name="l00299"></a><a class="code" href="a00008.html#7c13e57ce4138032322bc2230a260b9a">00299</a>     tree_edges_iterator tree_edges_begin ()<span class="keyword"> const </span>
<a name="l00300"></a>00300 <span class="keyword">        </span>{<span class="keywordflow">return</span> tree.begin();}
<a name="l00301"></a>00301 
<a name="l00307"></a><a class="code" href="a00008.html#3b2de20ab3cff57507f2db17982a6725">00307</a>     tree_edges_iterator tree_edges_end ()<span class="keyword"> const</span>
<a name="l00308"></a>00308 <span class="keyword">        </span>{<span class="keywordflow">return</span> tree.end();}
<a name="l00309"></a>00309 
<a name="l00313"></a><a class="code" href="a00008.html#d040ddae37492e18c8e029406d667bd9">00313</a>     <span class="keyword">typedef</span> list&lt;node&gt;::const_iterator dfs_iterator; 
<a name="l00314"></a>00314 
<a name="l00320"></a><a class="code" href="a00008.html#d77350c772b18d305e92d44afe784282">00320</a>     dfs_iterator begin ()<span class="keyword"> const </span>
<a name="l00321"></a>00321 <span class="keyword">        </span>{<span class="keywordflow">return</span> dfs_order.begin();}
<a name="l00322"></a>00322 
<a name="l00329"></a><a class="code" href="a00008.html#08e6a3b0c1f7c9f7d725b586d5c00857">00329</a>     dfs_iterator end ()<span class="keyword"> const </span>
<a name="l00330"></a>00330 <span class="keyword">        </span>{<span class="keywordflow">return</span> dfs_order.end();}
<a name="l00331"></a>00331 
<a name="l00335"></a><a class="code" href="a00008.html#e7301f3d4417e60fb3a499180375194e">00335</a>     <span class="keyword">typedef</span> list&lt;edge&gt;::const_iterator non_tree_edges_iterator;
<a name="l00336"></a>00336 
<a name="l00343"></a><a class="code" href="a00008.html#1f92658af729dff37e76ad3025b98a79">00343</a>     non_tree_edges_iterator non_tree_edges_begin ()<span class="keyword"> const </span>
<a name="l00344"></a>00344 <span class="keyword">        </span>{assert (back_edges);  <span class="keywordflow">return</span> back_edges-&gt;begin(); }
<a name="l00345"></a>00345 
<a name="l00353"></a><a class="code" href="a00008.html#f6c9d194226a73515cab7805d1d2a9cf">00353</a>     non_tree_edges_iterator non_tree_edges_end ()<span class="keyword"> const </span>
<a name="l00354"></a>00354 <span class="keyword">        </span>{assert (back_edges); <span class="keywordflow">return</span> back_edges-&gt;end(); }
<a name="l00355"></a>00355 
<a name="l00359"></a><a class="code" href="a00008.html#17cb59c8a1fead11fa6b0c85cf5a478e">00359</a>     <span class="keyword">typedef</span> list&lt;dfs_iterator&gt;::const_iterator roots_iterator;
<a name="l00360"></a>00360 
<a name="l00388"></a><a class="code" href="a00008.html#a084e2afe7b58c7bd94e4a8cf8c630af">00388</a>     roots_iterator roots_begin ()<span class="keyword"> const </span>
<a name="l00389"></a>00389 <span class="keyword">        </span>{<span class="keywordflow">return</span> roots.begin();}
<a name="l00390"></a>00390 
<a name="l00397"></a><a class="code" href="a00008.html#c074438451c387aaf0cf6aaac79bcd16">00397</a>     roots_iterator roots_end ()<span class="keyword"> const </span>
<a name="l00398"></a>00398 <span class="keyword">        </span>{<span class="keywordflow">return</span> roots.end();}
<a name="l00399"></a>00399 
<a name="l00406"></a><a class="code" href="a00008.html#5bffe465fdd599a63a2c3d4593f21187">00406</a>     <span class="keywordtype">int</span> number_of_reached_nodes ()<span class="keyword"> const</span>
<a name="l00407"></a>00407 <span class="keyword">        </span>{<span class="keywordflow">return</span> reached_nodes;}
<a name="l00408"></a>00408 
<a name="l00409"></a>00409 
<a name="l00410"></a>00410     <span class="comment">//-----------------------------------------------------------------------</span>
<a name="l00411"></a>00411     <span class="comment">//   Handler - for customization purposes</span>
<a name="l00412"></a>00412     <span class="comment">//-----------------------------------------------------------------------</span>
<a name="l00413"></a>00413 
<a name="l00419"></a><a class="code" href="a00008.html#cc82574cd42ab8256e685374bee5fabb">00419</a>     <span class="keyword">virtual</span> <span class="keywordtype">void</span> init_handler (<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G) {}
<a name="l00420"></a>00420     
<a name="l00426"></a><a class="code" href="a00008.html#b96c7c6183856dd9e356fdcf50835b32">00426</a>     <span class="keyword">virtual</span> <span class="keywordtype">void</span> end_handler (<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G) {}
<a name="l00427"></a>00427 
<a name="l00435"></a><a class="code" href="a00008.html#73dabe5882226b53494a487b7c34f1d1">00435</a>     <span class="keyword">virtual</span> <span class="keywordtype">void</span> entry_handler (<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G, <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp; n, <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp; f) {}
<a name="l00436"></a>00436 
<a name="l00445"></a><a class="code" href="a00008.html#8071fc4e82deff7ceb2790cd4eb42280">00445</a>     <span class="keyword">virtual</span> <span class="keywordtype">void</span> leave_handler (<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G, <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp; n, <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp; f) {}
<a name="l00446"></a>00446 
<a name="l00455"></a><a class="code" href="a00008.html#e3f095c9fe6106e82c24543da4844ea3">00455</a>     <span class="keyword">virtual</span> <span class="keywordtype">void</span> before_recursive_call_handler (<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G, <a class="code" href="a00010.html" title="An edge in a graph.">edge</a>&amp; e, <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp; n) {}
<a name="l00456"></a>00456     
<a name="l00466"></a><a class="code" href="a00008.html#25ae75fe08f1d8c0fedcf9dcae09d092">00466</a>     <span class="keyword">virtual</span> <span class="keywordtype">void</span> after_recursive_call_handler (<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G, <a class="code" href="a00010.html" title="An edge in a graph.">edge</a>&amp; e, <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp; n) {}
<a name="l00467"></a>00467     
<a name="l00477"></a><a class="code" href="a00008.html#df1c667188e632761c63f529537c544c">00477</a>     <span class="keyword">virtual</span> <span class="keywordtype">void</span> old_adj_node_handler (<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G, <a class="code" href="a00010.html" title="An edge in a graph.">edge</a>&amp; e, <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp; n) {}
<a name="l00478"></a>00478 
<a name="l00489"></a><a class="code" href="a00008.html#3b5fbea7a7baed9946cfb4444a7f20ea">00489</a>     <span class="keyword">virtual</span> <span class="keywordtype">void</span> new_start_handler (<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G, <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp; n) { };
<a name="l00490"></a>00490 
<a name="l00491"></a>00491 <span class="keyword">private</span>:
<a name="l00492"></a>00492 
<a name="l00496"></a>00496     <span class="keywordtype">void</span> dfs_sub (<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp;, <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp;, <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp;);
<a name="l00497"></a>00497 
<a name="l00498"></a>00498 <span class="keyword">protected</span>:    
<a name="l00499"></a>00499 
<a name="l00500"></a>00500     <span class="comment">//----------------------------------------------------------------------</span>
<a name="l00501"></a>00501     <span class="comment">//   Data</span>
<a name="l00502"></a>00502     <span class="comment">//----------------------------------------------------------------------</span>
<a name="l00503"></a>00503 
<a name="l00507"></a>00507     <span class="keywordtype">int</span> act_dfs_num;
<a name="l00511"></a>00511     <span class="keywordtype">int</span> act_comp_num;
<a name="l00515"></a>00515     list&lt;edge&gt; tree;
<a name="l00519"></a>00519     list&lt;node&gt; dfs_order;
<a name="l00523"></a>00523     <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;int&gt;</a> dfs_number;
<a name="l00527"></a>00527     <span class="keywordtype">int</span> reached_nodes;
<a name="l00531"></a>00531     <a class="code" href="a00011.html" title="A specialized map with edges as keys.">edge_map&lt;int&gt;</a>* used;
<a name="l00535"></a>00535     list&lt;dfs_iterator&gt; roots;
<a name="l00536"></a>00536     
<a name="l00537"></a>00537 
<a name="l00538"></a>00538     <span class="comment">//-----------------------------------------------------------------------</span>
<a name="l00539"></a>00539     <span class="comment">// Optional </span>
<a name="l00540"></a>00540     <span class="comment">//-----------------------------------------------------------------------</span>
<a name="l00541"></a>00541     
<a name="l00545"></a>00545     <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;int&gt;</a>* comp_number;
<a name="l00549"></a>00549     <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;node&gt;</a>* preds;
<a name="l00553"></a>00553     list&lt;edge&gt;* back_edges;
<a name="l00557"></a>00557     <a class="code" href="a00020.html" title="A node in a graph.">node</a> start;
<a name="l00561"></a>00561     <span class="keywordtype">bool</span> whole_graph;
<a name="l00562"></a>00562 };
<a name="l00563"></a>00563 
<a name="l00564"></a>00564 __GTL_END_NAMESPACE
<a name="l00565"></a>00565 
<a name="l00566"></a>00566 <span class="preprocessor">#endif // GTL_DFS_H</span>
<a name="l00567"></a>00567 <span class="preprocessor"></span>
<a name="l00568"></a>00568 <span class="comment">//--------------------------------------------------------------------------</span>
<a name="l00569"></a>00569 <span class="comment">//   end of file</span>
<a name="l00570"></a>00570 <span class="comment">//--------------------------------------------------------------------------</span>
</pre></div>    <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>