mooigraph
/
regraphlet


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212
							<!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: bfs.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>bfs.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">//   bfs.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: bfs.h,v 1.14 2003/03/24 15:58:54 raitner Exp $</span>
<a name="l00007"></a>00007 
<a name="l00008"></a>00008 <span class="preprocessor">#ifndef GTL_BFS_H</span>
<a name="l00009"></a>00009 <span class="preprocessor"></span><span class="preprocessor">#define GTL_BFS_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 <span class="preprocessor">#include &lt;GTL/node_map.h&gt;</span>
<a name="l00014"></a>00014 
<a name="l00015"></a>00015 <span class="preprocessor">#include &lt;deque&gt;</span>
<a name="l00016"></a>00016 
<a name="l00017"></a>00017 __GTL_BEGIN_NAMESPACE
<a name="l00018"></a>00018 
<a name="l00086"></a><a class="code" href="a00003.html">00086</a> <span class="keyword">class </span>GTL_EXTERN <a class="code" href="a00003.html" title="Breadth-First-Search (BFS) algorithm.">bfs</a> : <span class="keyword">public</span> <a class="code" href="a00001.html" title="Abstract baseclass for all algoritm-classes.">algorithm</a>
<a name="l00087"></a>00087 {
<a name="l00088"></a>00088 <span class="keyword">public</span>:
<a name="l00089"></a>00089     
<a name="l00093"></a>00093     <a class="code" href="a00003.html" title="Breadth-First-Search (BFS) algorithm.">bfs</a> ();
<a name="l00094"></a>00094 
<a name="l00098"></a>00098     <span class="keyword">virtual</span> ~<a class="code" href="a00003.html" title="Breadth-First-Search (BFS) algorithm.">bfs</a> ();
<a name="l00099"></a>00099 
<a name="l00100"></a>00100     <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="l00101"></a>00101 
<a name="l00111"></a><a class="code" href="a00003.html#6dd7e852f7768814aafba8962befca56">00111</a>     <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) { <span class="keywordflow">return</span> GTL_OK; }
<a name="l00112"></a>00112 
<a name="l00113"></a>00113     <span class="keyword">virtual</span> <span class="keywordtype">void</span> <a class="code" href="a00001.html#21aba63d066ae7897de6ca7d8425c408" title="Resets algorithm.">reset</a> ();
<a name="l00114"></a>00114     
<a name="l00115"></a>00115     <span class="comment">//-----------------------------------------------------------------------</span>
<a name="l00116"></a>00116     <span class="comment">//  Parameters</span>
<a name="l00117"></a>00117     <span class="comment">//-----------------------------------------------------------------------</span>
<a name="l00118"></a>00118 
<a name="l00128"></a><a class="code" href="a00003.html#23e2981c2ee617a6e12a8833d2db6210">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) {start = n;}
<a name="l00129"></a>00129 
<a name="l00135"></a><a class="code" href="a00003.html#c5cf27683ad751cd6e4129141fc9b495">00135</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="l00136"></a>00136 
<a name="l00154"></a><a class="code" href="a00003.html#25fc51b1bfbbdd3afefe0a84c1bd2f6b">00154</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="l00155"></a>00155     
<a name="l00162"></a><a class="code" href="a00003.html#d698825ec64edfa808210de913a922d3">00162</a>     <span class="keywordtype">bool</span> scan_whole_graph ()<span class="keyword"> const </span>{<span class="keywordflow">return</span> whole_graph;}
<a name="l00163"></a>00163 
<a name="l00174"></a>00174     <span class="keywordtype">void</span> calc_level (<span class="keywordtype">bool</span> <span class="keyword">set</span>);
<a name="l00175"></a>00175     
<a name="l00182"></a><a class="code" href="a00003.html#8a67bff3ab12226cf8f4bea4a14bd183">00182</a>     <span class="keywordtype">bool</span> calc_level ()<span class="keyword"> const </span>{<span class="keywordflow">return</span> level_number != 0;}
<a name="l00183"></a>00183 
<a name="l00193"></a>00193     <span class="keywordtype">void</span> store_non_tree_edges (<span class="keywordtype">bool</span> <span class="keyword">set</span>);
<a name="l00194"></a>00194 
<a name="l00202"></a><a class="code" href="a00003.html#9e16858479ee2b4980b4dbe73202a9d6">00202</a>     <span class="keywordtype">bool</span> store_non_tree_edges ()<span class="keyword"> const </span>{<span class="keywordflow">return</span> non_tree != 0;}
<a name="l00203"></a>00203 
<a name="l00204"></a>00204 
<a name="l00214"></a>00214     <span class="keywordtype">void</span> store_preds (<span class="keywordtype">bool</span> <span class="keyword">set</span>);
<a name="l00215"></a>00215 
<a name="l00222"></a><a class="code" href="a00003.html#1b73eb7f1fb984331781da890bd45029">00222</a>     <span class="keywordtype">bool</span> store_preds ()<span class="keyword"> const </span>{<span class="keywordflow">return</span> preds != 0;}
<a name="l00223"></a>00223 
<a name="l00230"></a><a class="code" href="a00003.html#a91531970fa0eb1c7e18d5455f54fe9f">00230</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="l00231"></a>00231 <span class="keyword">        </span>{<span class="keywordflow">return</span> bfs_number[n] != 0;}
<a name="l00232"></a>00232 
<a name="l00242"></a><a class="code" href="a00003.html#ad3b67493e3d936f8ca3d1fe38d72842">00242</a>     <span class="keywordtype">int</span> bfs_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="l00243"></a>00243 <span class="keyword">        </span>{<span class="keywordflow">return</span> bfs_number[n];}
<a name="l00244"></a>00244 
<a name="l00254"></a><a class="code" href="a00003.html#01e0e18c3478faf9ea6b9140c1cc4102">00254</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="l00255"></a>00255 <span class="keyword">        </span>{<span class="keywordflow">return</span> bfs_number[n];}
<a name="l00256"></a>00256 
<a name="l00267"></a><a class="code" href="a00003.html#db141187b9b6c9fc78089eb87ba19ad4">00267</a>     <span class="keywordtype">int</span> level (<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="l00268"></a>00268 <span class="keyword">        </span>{assert (level_number); <span class="keywordflow">return</span> (*level_number)[n];}
<a name="l00269"></a>00269 
<a name="l00283"></a><a class="code" href="a00003.html#eff99e4f0142cbb9977503844c0d45c9">00283</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="l00284"></a>00284 <span class="keyword">        </span>{assert (preds); <span class="keywordflow">return</span> (*preds)[n];}
<a name="l00285"></a>00285 
<a name="l00289"></a><a class="code" href="a00003.html#a0b58a03ca2fc32117948ab27a806bd1">00289</a>     <span class="keyword">typedef</span> list&lt;edge&gt;::const_iterator tree_edges_iterator;
<a name="l00290"></a>00290 
<a name="l00300"></a><a class="code" href="a00003.html#50fbe73f807b39845bb2334548c9b8cb">00300</a>     tree_edges_iterator tree_edges_begin ()<span class="keyword"> const </span>
<a name="l00301"></a>00301 <span class="keyword">        </span>{<span class="keywordflow">return</span> tree.begin();}
<a name="l00302"></a>00302 
<a name="l00309"></a><a class="code" href="a00003.html#609773f0e8e94dbdd330d5363c6d610c">00309</a>     tree_edges_iterator tree_edges_end ()<span class="keyword"> const</span>
<a name="l00310"></a>00310 <span class="keyword">        </span>{<span class="keywordflow">return</span> tree.end();}
<a name="l00311"></a>00311    
<a name="l00315"></a><a class="code" href="a00003.html#cafce54954100cc7bc9f80eb318a7bee">00315</a>     <span class="keyword">typedef</span> list&lt;node&gt;::const_iterator bfs_iterator; 
<a name="l00316"></a>00316 
<a name="l00322"></a><a class="code" href="a00003.html#7b83a88f71f210946be3ef212f4c2c37">00322</a>     bfs_iterator begin ()<span class="keyword"> const </span>
<a name="l00323"></a>00323 <span class="keyword">        </span>{<span class="keywordflow">return</span> bfs_order.begin();}
<a name="l00324"></a>00324 
<a name="l00331"></a><a class="code" href="a00003.html#b1a9a095e1e757e8f71ba752bf0e898d">00331</a>     bfs_iterator end ()<span class="keyword"> const </span>
<a name="l00332"></a>00332 <span class="keyword">        </span>{<span class="keywordflow">return</span> bfs_order.end();}
<a name="l00333"></a>00333 
<a name="l00337"></a><a class="code" href="a00003.html#ecd86c7c1f1086d4b6b11c2a0eb12afe">00337</a>     <span class="keyword">typedef</span> list&lt;edge&gt;::const_iterator non_tree_edges_iterator;
<a name="l00338"></a>00338 
<a name="l00345"></a><a class="code" href="a00003.html#0c7c3cb97a538907ddd0dc39bd884ffc">00345</a>     non_tree_edges_iterator non_tree_edges_begin ()<span class="keyword"> const </span>
<a name="l00346"></a>00346 <span class="keyword">        </span>{assert (non_tree);  <span class="keywordflow">return</span> non_tree-&gt;begin(); }
<a name="l00347"></a>00347 
<a name="l00355"></a><a class="code" href="a00003.html#37645ce2ffc6fb95afb56477025a64a8">00355</a>     non_tree_edges_iterator non_tree_edges_end ()<span class="keyword"> const </span>
<a name="l00356"></a>00356 <span class="keyword">        </span>{assert (non_tree); <span class="keywordflow">return</span> non_tree-&gt;end(); }
<a name="l00357"></a>00357     
<a name="l00361"></a><a class="code" href="a00003.html#386ac6f3c63e38c3f5263e15c3ab9d01">00361</a>     <span class="keyword">typedef</span> list&lt;bfs_iterator&gt;::const_iterator roots_iterator;
<a name="l00362"></a>00362 
<a name="l00392"></a><a class="code" href="a00003.html#ae9df31655e7ef516426dfb99c2de888">00392</a>     roots_iterator roots_begin ()<span class="keyword"> const </span>
<a name="l00393"></a>00393 <span class="keyword">        </span>{<span class="keywordflow">return</span> roots.begin();}
<a name="l00394"></a>00394 
<a name="l00401"></a><a class="code" href="a00003.html#31e77fd48aed1902d488a54f2f0ef6f8">00401</a>     roots_iterator roots_end ()<span class="keyword"> const </span>
<a name="l00402"></a>00402 <span class="keyword">        </span>{<span class="keywordflow">return</span> roots.end();}
<a name="l00403"></a>00403 
<a name="l00410"></a><a class="code" href="a00003.html#50ca0ee41753b59ed7adfe9f60adf1e4">00410</a>     <span class="keywordtype">int</span> number_of_reached_nodes ()<span class="keyword"> const</span>
<a name="l00411"></a>00411 <span class="keyword">        </span>{<span class="keywordflow">return</span> reached_nodes;}
<a name="l00412"></a>00412 
<a name="l00413"></a>00413     <span class="comment">//-----------------------------------------------------------------------</span>
<a name="l00414"></a>00414     <span class="comment">//   Handler</span>
<a name="l00415"></a>00415     <span class="comment">//-----------------------------------------------------------------------</span>
<a name="l00416"></a>00416 
<a name="l00422"></a><a class="code" href="a00003.html#b9af608a9b2d570a8688498bc3c53d7f">00422</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="l00423"></a>00423 
<a name="l00429"></a><a class="code" href="a00003.html#d99b9aeb177a8a2e0ce1c3673082cddf">00429</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="l00430"></a>00430 
<a name="l00437"></a><a class="code" href="a00003.html#3f161fe9f45e0a69892f355a889c3516">00437</a>     <span class="keyword">virtual</span> <span class="keywordtype">void</span> popped_node_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="l00438"></a>00438 
<a name="l00448"></a><a class="code" href="a00003.html#db6604080f3376e9713e35cd9d7d8943">00448</a>     <span class="keyword">virtual</span> <span class="keywordtype">void</span> finished_node_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="l00449"></a>00449 
<a name="l00460"></a><a class="code" href="a00003.html#0e45c8fe90e54bffe18b308868ccc111">00460</a>     <span class="keyword">virtual</span> <span class="keywordtype">void</span> unused_node_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="l00461"></a>00461 
<a name="l00472"></a><a class="code" href="a00003.html#d2cbb1e9c36f561da0c91fd142296f2a">00472</a>     <span class="keyword">virtual</span> <span class="keywordtype">void</span> used_node_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="l00473"></a>00473 
<a name="l00485"></a><a class="code" href="a00003.html#4f33f10121240390a5a50b5efc16c1f5">00485</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="l00486"></a>00486 
<a name="l00487"></a>00487 <span class="keyword">private</span>:
<a name="l00488"></a>00488 
<a name="l00489"></a>00489     <span class="keywordtype">void</span> bfs_sub (<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp;, <span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp;, <a class="code" href="a00011.html" title="A specialized map with edges as keys.">edge_map&lt;int&gt;</a>*);
<a name="l00490"></a>00490 
<a name="l00491"></a>00491 <span class="keyword">protected</span>:
<a name="l00492"></a>00492 
<a name="l00493"></a>00493     <span class="comment">//-----------------------------------------------------------------------</span>
<a name="l00494"></a>00494     <span class="comment">//   Data</span>
<a name="l00495"></a>00495     <span class="comment">//-----------------------------------------------------------------------</span>
<a name="l00496"></a>00496     
<a name="l00500"></a><a class="code" href="a00003.html#5a4adad9562896536b8b58ab237e8478">00500</a>     <span class="keywordtype">int</span> act_bfs_num;
<a name="l00501"></a>00501 
<a name="l00505"></a><a class="code" href="a00003.html#ff965242124a7e3a6308de0c0ebfa741">00505</a>     deque&lt;node&gt; qu;
<a name="l00506"></a>00506 
<a name="l00512"></a><a class="code" href="a00003.html#35b0acd44887615142fd5f2fc6197452">00512</a>     list&lt;node&gt; bfs_order;
<a name="l00513"></a>00513 
<a name="l00519"></a><a class="code" href="a00003.html#a259f09ada9928cda41bcb540f685e80">00519</a>     list&lt;edge&gt; tree;
<a name="l00520"></a>00520 
<a name="l00524"></a><a class="code" href="a00003.html#59d0c5c5ad2715776b20b1aec03dbc3a">00524</a>     <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;int&gt;</a> bfs_number;
<a name="l00525"></a>00525 
<a name="l00529"></a><a class="code" href="a00003.html#c3db80b59d5db049199936445a6c2da8">00529</a>     <span class="keywordtype">int</span> reached_nodes;
<a name="l00530"></a>00530     
<a name="l00536"></a><a class="code" href="a00003.html#79d19028002766f7992fe94689217f99">00536</a>     list&lt;bfs_iterator&gt; roots;
<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="l00547"></a><a class="code" href="a00003.html#6c08fbcc90d71f1cbdd03a1cdaa9dc99">00547</a>     <span class="keywordtype">bool</span> whole_graph;
<a name="l00548"></a>00548 
<a name="l00554"></a><a class="code" href="a00003.html#f2ab561d9e60a9fc2e25b02d1f807f96">00554</a>     <a class="code" href="a00020.html" title="A node in a graph.">node</a> start;
<a name="l00555"></a>00555 
<a name="l00561"></a><a class="code" href="a00003.html#ab92e9d128612c28324aafe4750dbc84">00561</a>     <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;int&gt;</a>* level_number;
<a name="l00562"></a>00562 
<a name="l00568"></a><a class="code" href="a00003.html#a6783e3e2ac4235403b37df3ee3ee968">00568</a>     list&lt;edge&gt;* non_tree;
<a name="l00569"></a>00569 
<a name="l00575"></a><a class="code" href="a00003.html#3bac5ed333bb78a30a67099c3b94aa0c">00575</a>     <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;node&gt;</a>* preds;
<a name="l00576"></a>00576 };
<a name="l00577"></a>00577 
<a name="l00578"></a>00578 __GTL_END_NAMESPACE
<a name="l00579"></a>00579 
<a name="l00580"></a>00580 <span class="preprocessor">#endif // GTL_BFS_H</span>
<a name="l00581"></a>00581 <span class="preprocessor"></span>
<a name="l00582"></a>00582 <span class="comment">//--------------------------------------------------------------------------</span>
<a name="l00583"></a>00583 <span class="comment">//   end of file</span>
<a name="l00584"></a>00584 <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>