mooigraph
/
regraphlet


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161
							<!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: biconnectivity.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>biconnectivity.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">//   biconnectivity.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: biconnectivity.h,v 1.18 2003/03/26 13:37:14 raitner Exp $</span>
<a name="l00007"></a>00007 
<a name="l00008"></a>00008 <span class="preprocessor">#ifndef GTL_BICONNECTIVITY_H</span>
<a name="l00009"></a>00009 <span class="preprocessor"></span><span class="preprocessor">#define GTL_BICONNECTIVITY_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/dfs.h&gt;</span>
<a name="l00013"></a>00013 
<a name="l00014"></a>00014 <span class="preprocessor">#include &lt;list&gt;</span>
<a name="l00015"></a>00015 <span class="preprocessor">#include &lt;stack&gt;</span>
<a name="l00016"></a>00016 
<a name="l00017"></a>00017 __GTL_BEGIN_NAMESPACE
<a name="l00018"></a>00018 
<a name="l00035"></a><a class="code" href="a00004.html">00035</a> <span class="keyword">class </span>GTL_EXTERN <a class="code" href="a00004.html" title="Biconnectivity-test and low-numbers.">biconnectivity</a> : <span class="keyword">public</span> <a class="code" href="a00008.html" title="Depth-First-Search (DFS) algorithm.">dfs</a> 
<a name="l00036"></a>00036 {
<a name="l00037"></a>00037 <span class="keyword">public</span>:
<a name="l00043"></a>00043     <a class="code" href="a00004.html" title="Biconnectivity-test and low-numbers.">biconnectivity</a> ();
<a name="l00044"></a>00044 
<a name="l00050"></a><a class="code" href="a00004.html#f8e2bb061de4a08f95a2a3a94fdbd797">00050</a>     <span class="keyword">virtual</span> ~<a class="code" href="a00004.html" title="Biconnectivity-test and low-numbers.">biconnectivity</a> () {}
<a name="l00051"></a>00051 
<a name="l00065"></a>00065     <span class="keyword">virtual</span> <span class="keywordtype">int</span> <a class="code" href="a00008.html#908f4ea617ed59767ed334b39a2771d0" title="Checks whether the preconditions for DFS are satisfied.">check</a> (<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G);
<a name="l00066"></a>00066 
<a name="l00067"></a>00067     <span class="keyword">virtual</span> <span class="keywordtype">void</span> <a class="code" href="a00008.html#1c893f699517cc72624cf171b7bc4da4" title="Resets algorithm.">reset</a> ();
<a name="l00068"></a>00068 
<a name="l00075"></a><a class="code" href="a00004.html#e0d0b47a16da24c0f124cb989ccf5846">00075</a>     <span class="keywordtype">int</span> low_number (<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="l00076"></a>00076 <span class="keyword">        </span>{<span class="keywordflow">return</span> low_num[n];}
<a name="l00077"></a>00077 
<a name="l00083"></a><a class="code" href="a00004.html#2db9457fbbfb6a832234d8455e807198">00083</a>     <span class="keywordtype">bool</span> is_biconnected ()<span class="keyword"> const </span>
<a name="l00084"></a>00084 <span class="keyword">        </span>{<span class="keywordflow">return</span> num_of_components == 1;}
<a name="l00085"></a>00085 
<a name="l00092"></a><a class="code" href="a00004.html#f6fe3286b7cb24e0da460cfdbf733d79">00092</a>     <span class="keywordtype">bool</span> store_components ()<span class="keyword"> const</span>
<a name="l00093"></a>00093 <span class="keyword">        </span>{ <span class="keywordflow">return</span> store_comp; }
<a name="l00094"></a>00094 
<a name="l00105"></a><a class="code" href="a00004.html#b7c9e256a4d7a4ffea33b20f014e1f69">00105</a>     <span class="keywordtype">void</span> store_components (<span class="keywordtype">bool</span> <span class="keyword">set</span>) 
<a name="l00106"></a>00106         { store_comp  = <span class="keyword">set</span>; <span class="keywordflow">if</span> (<span class="keyword">set</span>) <a class="code" href="a00008.html#121e68fa166dc109b9f59f5bad3b0a8f" title="Returns true iff the whole graph will be scanned.">scan_whole_graph</a> (<span class="keyword">set</span>); }
<a name="l00107"></a>00107     
<a name="l00119"></a><a class="code" href="a00004.html#774fd08203a6d164605afc4cdc8b9201">00119</a>     <span class="keywordtype">void</span> make_biconnected (<span class="keywordtype">bool</span> <span class="keyword">set</span>) 
<a name="l00120"></a>00120         { add_edges = <span class="keyword">set</span>; <span class="keywordflow">if</span> (<span class="keyword">set</span>) <a class="code" href="a00008.html#121e68fa166dc109b9f59f5bad3b0a8f" title="Returns true iff the whole graph will be scanned.">scan_whole_graph</a> (<span class="keyword">set</span>); }
<a name="l00121"></a>00121     
<a name="l00129"></a><a class="code" href="a00004.html#2db912e8bc1a89e431116824434e836d">00129</a>     <span class="keywordtype">bool</span> make_biconnected ()<span class="keyword"> const </span>
<a name="l00130"></a>00130 <span class="keyword">        </span>{ <span class="keywordflow">return</span> add_edges; }
<a name="l00131"></a>00131     
<a name="l00138"></a><a class="code" href="a00004.html#c5295da180114bffbbfd621d644d4c58">00138</a>     list&lt;edge&gt;::iterator additional_begin ()
<a name="l00139"></a>00139         { <span class="keywordflow">return</span> additional.begin (); }
<a name="l00140"></a>00140 
<a name="l00147"></a><a class="code" href="a00004.html#447a86f387efd181b25b8bacf3365e75">00147</a>     list&lt;edge&gt;::iterator additional_end ()
<a name="l00148"></a>00148         { <span class="keywordflow">return</span> additional.end (); }
<a name="l00149"></a>00149     
<a name="l00153"></a>00153     <span class="keyword">typedef</span> list&lt;node&gt;::iterator cutpoint_iterator;
<a name="l00154"></a>00154 
<a name="l00164"></a><a class="code" href="a00004.html#473197552874aaf148e847838144eed7">00164</a>     cutpoint_iterator cut_points_begin () 
<a name="l00165"></a>00165         { <span class="keywordflow">return</span> cut_points.begin(); }
<a name="l00166"></a>00166 
<a name="l00173"></a><a class="code" href="a00004.html#78cb06c1d056b9519622a67a92e85b6e">00173</a>     cutpoint_iterator cut_points_end () 
<a name="l00174"></a>00174         { <span class="keywordflow">return</span> cut_points.end(); }
<a name="l00175"></a>00175 
<a name="l00176"></a>00176 
<a name="l00180"></a>00180     <span class="keyword">typedef</span> list&lt;pair&lt;list&lt;node&gt;, list&lt;edge&gt; &gt; &gt;::iterator component_iterator;
<a name="l00181"></a>00181 
<a name="l00195"></a><a class="code" href="a00004.html#c0b7253533edc3f1412f771cb35bf04a">00195</a>     component_iterator components_begin ()
<a name="l00196"></a>00196         { <span class="keywordflow">return</span> <a class="code" href="a00007.html" title="Connected components algorithm.">components</a>.begin(); }
<a name="l00197"></a>00197 
<a name="l00198"></a>00198 
<a name="l00205"></a><a class="code" href="a00004.html#0bd1c70975e664174e591efd64f8dc71">00205</a>     component_iterator components_end ()
<a name="l00206"></a>00206         { <span class="keywordflow">return</span> <a class="code" href="a00007.html" title="Connected components algorithm.">components</a>.end(); }
<a name="l00207"></a>00207 
<a name="l00213"></a><a class="code" href="a00004.html#c984168e3c2b1b92fc20def2b38fb07f">00213</a>     <span class="keywordtype">int</span> number_of_components ()<span class="keyword"> const</span>
<a name="l00214"></a>00214 <span class="keyword">        </span>{<span class="keywordflow">return</span> num_of_components; }
<a name="l00215"></a>00215 
<a name="l00216"></a>00216     <span class="comment">//-----------------------------------------------------------------------</span>
<a name="l00217"></a>00217     <span class="comment">//   Handler used to extend dfs to biconnectivity</span>
<a name="l00218"></a>00218     <span class="comment">//-----------------------------------------------------------------------</span>
<a name="l00222"></a>00222 <span class="comment"></span>    <span class="keyword">virtual</span> <span class="keywordtype">void</span> <a class="code" href="a00008.html#cc82574cd42ab8256e685374bee5fabb" title="Handler called before the start of DFS.">init_handler</a> (<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp;);
<a name="l00223"></a>00223 
<a name="l00227"></a>00227     <span class="keyword">virtual</span> <span class="keywordtype">void</span> <a class="code" href="a00008.html#73dabe5882226b53494a487b7c34f1d1" title="Handler called when touching node n.">entry_handler</a> (<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="l00228"></a>00228 
<a name="l00232"></a>00232     <span class="keyword">virtual</span> <span class="keywordtype">void</span> <a class="code" href="a00008.html#e3f095c9fe6106e82c24543da4844ea3" title="Handler called when a unused node n connected to the actual node by e is found.">before_recursive_call_handler</a> (<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp;, <a class="code" href="a00010.html" title="An edge in a graph.">edge</a>&amp;, <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp;);
<a name="l00233"></a>00233 
<a name="l00237"></a>00237     <span class="keyword">virtual</span> <span class="keywordtype">void</span> <a class="code" href="a00008.html#25ae75fe08f1d8c0fedcf9dcae09d092" title="Handler called after the algorithm returns from the subtree starting at n connected...">after_recursive_call_handler</a> (<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp;, <a class="code" href="a00010.html" title="An edge in a graph.">edge</a>&amp;, <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp;);
<a name="l00238"></a>00238 
<a name="l00242"></a>00242     <span class="keyword">virtual</span> <span class="keywordtype">void</span> <a class="code" href="a00008.html#df1c667188e632761c63f529537c544c" title="Handler called when a already marked node n connected to the actual node by e is...">old_adj_node_handler</a> (<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp;, <a class="code" href="a00010.html" title="An edge in a graph.">edge</a>&amp;, <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp;);
<a name="l00243"></a>00243 
<a name="l00247"></a>00247     <span class="keyword">virtual</span> <span class="keywordtype">void</span> <a class="code" href="a00008.html#3b5fbea7a7baed9946cfb4444a7f20ea" title="Called when DFS is started with start-node n.">new_start_handler</a> (<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 name="l00248"></a>00248 
<a name="l00252"></a>00252     <span class="keyword">virtual</span> <span class="keywordtype">void</span> <a class="code" href="a00008.html#8071fc4e82deff7ceb2790cd4eb42280" title="Handler called after all the adjacent edges of n have been examined.">leave_handler</a> (<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="l00253"></a>00253 
<a name="l00257"></a>00257     <span class="keyword">virtual</span> <span class="keywordtype">void</span> <a class="code" href="a00008.html#b96c7c6183856dd9e356fdcf50835b32" title="Handler called at the end of DFS.">end_handler</a> (<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp;);    
<a name="l00258"></a>00258 
<a name="l00259"></a>00259 
<a name="l00260"></a>00260 <span class="keyword">protected</span>:
<a name="l00264"></a>00264     list&lt;edge&gt; self_loops;
<a name="l00265"></a>00265 
<a name="l00269"></a>00269     <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;component_iterator&gt;</a> in_component;
<a name="l00270"></a>00270 
<a name="l00274"></a>00274     <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;int&gt;</a> low_num;
<a name="l00278"></a>00278     <span class="keywordtype">int</span> num_of_components;
<a name="l00282"></a>00282     <span class="keywordtype">bool</span> store_comp;
<a name="l00286"></a>00286     <span class="keywordtype">bool</span> add_edges;
<a name="l00290"></a>00290     <a class="code" href="a00020.html" title="A node in a graph.">node</a> last;
<a name="l00294"></a>00294     stack&lt;node&gt; node_stack;
<a name="l00298"></a>00298     stack&lt;edge&gt; edge_stack;
<a name="l00302"></a>00302     list&lt;pair&lt;list&lt;node&gt;, list&lt;edge&gt; &gt; &gt; <a class="code" href="a00007.html" title="Connected components algorithm.">components</a>;
<a name="l00306"></a>00306     list&lt;node&gt; cut_points;
<a name="l00310"></a>00310     <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;int&gt;</a> cut_count;
<a name="l00314"></a>00314     list&lt;edge&gt; additional;
<a name="l00318"></a>00318     <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;node&gt;</a> first_child;
<a name="l00319"></a>00319 };
<a name="l00320"></a>00320 
<a name="l00321"></a>00321 __GTL_END_NAMESPACE
<a name="l00322"></a>00322 
<a name="l00323"></a>00323 <span class="preprocessor">#endif // GTL_BICONNECTIVITY_H</span>
<a name="l00324"></a>00324 <span class="preprocessor"></span>
<a name="l00325"></a>00325 <span class="comment">//--------------------------------------------------------------------------</span>
<a name="l00326"></a>00326 <span class="comment">//   end of file</span>
<a name="l00327"></a>00327 <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>