mooigraph
/
regraphlet


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241
							<!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: planarity.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>planarity.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">//   planarity.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: planarity.h,v 1.22 2008/02/03 18:17:08 chris Exp $</span>
<a name="l00007"></a>00007 
<a name="l00008"></a>00008 <span class="preprocessor">#ifndef PLANARITY_H</span>
<a name="l00009"></a>00009 <span class="preprocessor"></span><span class="preprocessor">#define PLANARITY_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/graph.h&gt;</span>
<a name="l00013"></a>00013 <span class="preprocessor">#include &lt;GTL/algorithm.h&gt;</span>
<a name="l00014"></a>00014 <span class="preprocessor">#include &lt;GTL/st_number.h&gt;</span>
<a name="l00015"></a>00015 <span class="preprocessor">#include &lt;GTL/embedding.h&gt;</span>
<a name="l00016"></a>00016 <span class="preprocessor">#include &lt;GTL/biconnectivity.h&gt;</span>
<a name="l00017"></a>00017 <span class="preprocessor">#include &lt;GTL/pq_node.h&gt;</span>
<a name="l00018"></a>00018 
<a name="l00019"></a>00019 __GTL_BEGIN_NAMESPACE
<a name="l00020"></a>00020 
<a name="l00046"></a><a class="code" href="a00023.html">00046</a> <span class="keyword">class </span>GTL_EXTERN <a class="code" href="a00023.html" title="Tests if a graph can be drawn on a plane without any edge crossings.">planarity</a> : <span class="keyword">public</span> <a class="code" href="a00001.html" title="Abstract baseclass for all algoritm-classes.">algorithm</a> 
<a name="l00047"></a>00047 {
<a name="l00048"></a>00048 <span class="keyword">public</span>:
<a name="l00054"></a>00054     <a class="code" href="a00023.html" title="Tests if a graph can be drawn on a plane without any edge crossings.">planarity</a>();
<a name="l00055"></a>00055     
<a name="l00059"></a>00059     ~<a class="code" href="a00023.html" title="Tests if a graph can be drawn on a plane without any edge crossings.">planarity</a>();
<a name="l00060"></a>00060 
<a name="l00080"></a>00080     <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="l00081"></a>00081     
<a name="l00098"></a>00098     <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="l00099"></a>00099     
<a name="l00106"></a>00106     <span class="keywordtype">void</span> <a class="code" href="a00001.html#21aba63d066ae7897de6ca7d8425c408" title="Resets algorithm.">reset</a>();
<a name="l00107"></a>00107     
<a name="l00117"></a><a class="code" href="a00023.html#1679e285a7135b48b572764f5e8e773d">00117</a>     <span class="keywordtype">void</span> calc_embedding(<span class="keywordtype">bool</span> p)
<a name="l00118"></a>00118     {
<a name="l00119"></a>00119         emp = p;
<a name="l00120"></a>00120         <span class="keywordflow">if</span> (!emp) kup = <span class="keyword">false</span>;
<a name="l00121"></a>00121     }
<a name="l00122"></a>00122 
<a name="l00132"></a><a class="code" href="a00023.html#7806f9040f6ba20befb15ea3a25ba76a">00132</a>     <span class="keywordtype">bool</span> calc_embedding ()<span class="keyword"> const</span>
<a name="l00133"></a>00133 <span class="keyword">        </span>{ <span class="keywordflow">return</span> emp; }
<a name="l00134"></a>00134 
<a name="l00146"></a><a class="code" href="a00023.html#7b8e8e5414a4eedb0f99253d3b62ffa3">00146</a>     <span class="keywordtype">void</span> calc_obstruction(<span class="keywordtype">bool</span> p)
<a name="l00147"></a>00147     {
<a name="l00148"></a>00148         kup = p;
<a name="l00149"></a>00149         <span class="keywordflow">if</span> (kup) emp = <span class="keyword">true</span>;
<a name="l00150"></a>00150     }
<a name="l00151"></a>00151 
<a name="l00161"></a><a class="code" href="a00023.html#16713450b2930008709b87fc4f32fc6f">00161</a>     <span class="keywordtype">bool</span> calc_obstruction()<span class="keyword"> const</span>
<a name="l00162"></a>00162 <span class="keyword">    </span>{
<a name="l00163"></a>00163         <span class="keywordflow">return</span> kup;
<a name="l00164"></a>00164     }
<a name="l00165"></a>00165 
<a name="l00183"></a><a class="code" href="a00023.html#f67236533dce559d2670eae581750f54">00183</a>     <span class="keywordtype">void</span> make_biconnected(<span class="keywordtype">bool</span> p) 
<a name="l00184"></a>00184     {
<a name="l00185"></a>00185         bip = p;
<a name="l00186"></a>00186     }
<a name="l00187"></a>00187     
<a name="l00196"></a><a class="code" href="a00023.html#ab1a8ac05bacd090cb347340e0f9d119">00196</a>     <span class="keywordtype">bool</span> make_biconnected()<span class="keyword"> const </span>
<a name="l00197"></a>00197 <span class="keyword">    </span>{
<a name="l00198"></a>00198         <span class="keywordflow">return</span> bip;
<a name="l00199"></a>00199     }
<a name="l00200"></a>00200 
<a name="l00206"></a><a class="code" href="a00023.html#7a623f4c0e5c753a01dab6c0a79c3b50">00206</a>     <span class="keywordtype">bool</span> is_planar()<span class="keyword"> const</span>
<a name="l00207"></a>00207 <span class="keyword">    </span>{
<a name="l00208"></a>00208         <span class="keywordflow">return</span> planar;
<a name="l00209"></a>00209     }
<a name="l00210"></a>00210     
<a name="l00219"></a><a class="code" href="a00023.html#9ab79a340e361c3300cc08e82edd4e12">00219</a>     <a class="code" href="a00022.html" title="Ordered adjacency lists as a result of planarity testing.">planar_embedding</a>&amp; get_embedding()
<a name="l00220"></a>00220     {
<a name="l00221"></a>00221         <span class="keywordflow">return</span> embedding;
<a name="l00222"></a>00222     }
<a name="l00223"></a>00223 
<a name="l00233"></a><a class="code" href="a00023.html#c9021696934cc24afbc36aa307b2919b">00233</a>     list&lt;edge&gt;&amp; get_obstruction_edges()
<a name="l00234"></a>00234     {
<a name="l00235"></a>00235         <span class="keywordflow">return</span> ob_edges;
<a name="l00236"></a>00236     }
<a name="l00237"></a>00237 
<a name="l00247"></a><a class="code" href="a00023.html#c1bee50e38d398f3868a3308164caa31">00247</a>     list&lt;node&gt;&amp; get_obstruction_nodes()
<a name="l00248"></a>00248     {
<a name="l00249"></a>00249         <span class="keywordflow">return</span> ob_nodes;
<a name="l00250"></a>00250     }
<a name="l00251"></a>00251 <span class="keyword">private</span>:
<a name="l00263"></a>00263     <span class="keywordtype">bool</span> run_on_biconnected(<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G, <a class="code" href="a00022.html" title="Ordered adjacency lists as a result of planarity testing.">planar_embedding</a>&amp; em);
<a name="l00264"></a>00264 
<a name="l00273"></a>00273     <span class="keywordtype">void</span> add_to_embedding(<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G, <a class="code" href="a00022.html" title="Ordered adjacency lists as a result of planarity testing.">planar_embedding</a>&amp; em);
<a name="l00274"></a>00274 
<a name="l00287"></a>00287     <span class="keywordtype">void</span> correct_embedding(<a class="code" href="a00022.html" title="Ordered adjacency lists as a result of planarity testing.">planar_embedding</a>&amp; em,
<a name="l00288"></a>00288                            <a class="code" href="a00026.html" title="ST-number algorithm.">st_number</a>&amp; st,
<a name="l00289"></a>00289                            <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map</a>&lt;list&lt;direction_indicator&gt; &gt;&amp; dirs);
<a name="l00290"></a>00290 
<a name="l00305"></a>00305     <span class="keywordtype">void</span> extend_embedding(
<a name="l00306"></a>00306         <a class="code" href="a00020.html" title="A node in a graph.">node</a> n,
<a name="l00307"></a>00307         <a class="code" href="a00022.html" title="Ordered adjacency lists as a result of planarity testing.">planar_embedding</a>&amp; em,
<a name="l00308"></a>00308         <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;int&gt;</a>&amp; mark,
<a name="l00309"></a>00309         <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map</a>&lt;<a class="code" href="a00027.html" title="List which can be reversed in .">symlist&lt;edge&gt;::iterator</a> &gt;&amp; upward_begin);
<a name="l00310"></a>00310         
<a name="l00323"></a>00323     <span class="keywordtype">void</span> switch_to_component(<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G,
<a name="l00324"></a>00324                              biconnectivity::component_iterator it);
<a name="l00325"></a>00325  
<a name="l00343"></a>00343     <span class="keywordtype">void</span> examine_obstruction(<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G,
<a name="l00344"></a>00344                              <a class="code" href="a00026.html" title="ST-number algorithm.">st_number</a>&amp; st,
<a name="l00345"></a>00345                              <a class="code" href="a00020.html" title="A node in a graph.">node</a> act,
<a name="l00346"></a>00346                              pq_node* fail,
<a name="l00347"></a>00347                              <span class="keywordtype">bool</span> failed_at_root,
<a name="l00348"></a>00348                              <a class="code" href="a00022.html" title="Ordered adjacency lists as a result of planarity testing.">planar_embedding</a>&amp; em,
<a name="l00349"></a>00349                              <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map</a>&lt;list&lt;direction_indicator&gt; &gt;&amp; dirs,
<a name="l00350"></a>00350                              <a class="code" href="a00024.html" title="PQ-Trees.">pq_tree</a>* PQ); 
<a name="l00351"></a>00351 
<a name="l00366"></a>00366     <span class="keywordtype">void</span> dfs_bushform(<a class="code" href="a00020.html" title="A node in a graph.">node</a> act,
<a name="l00367"></a>00367                       <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;int&gt;</a>&amp; mark,
<a name="l00368"></a>00368                       <a class="code" href="a00026.html" title="ST-number algorithm.">st_number</a>&amp; st,
<a name="l00369"></a>00369                       <span class="keywordtype">int</span> stop,
<a name="l00370"></a>00370                       <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;edge&gt;</a>&amp; to_father);
<a name="l00371"></a>00371 
<a name="l00372"></a>00372     
<a name="l00385"></a>00385     <span class="keywordtype">void</span> attachment_cycle (<a class="code" href="a00020.html" title="A node in a graph.">node</a> n, <a class="code" href="a00022.html" title="Ordered adjacency lists as a result of planarity testing.">planar_embedding</a>&amp; em);
<a name="l00386"></a>00386 
<a name="l00398"></a>00398     <span class="keywordtype">void</span> mark_all_neighbors_of_leaves (pq_node* act, <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;int&gt;</a>&amp; mark);
<a name="l00399"></a>00399     
<a name="l00413"></a>00413     pq_leaf* run_through_partial(q_node* partial,
<a name="l00414"></a>00414                                  <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;int&gt;</a>&amp; mark,
<a name="l00415"></a>00415                                  <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;edge&gt;</a>&amp; to_father,
<a name="l00416"></a>00416                                  <a class="code" href="a00020.html" title="A node in a graph.">node</a> v);
<a name="l00417"></a>00417 
<a name="l00428"></a>00428     <a class="code" href="a00020.html" title="A node in a graph.">node</a> up_until_marked(<a class="code" href="a00020.html" title="A node in a graph.">node</a> act,
<a name="l00429"></a>00429                          <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;int&gt;</a>&amp; mark,
<a name="l00430"></a>00430                          <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;edge&gt;</a>&amp; to_father);
<a name="l00431"></a>00431 
<a name="l00443"></a>00443     <a class="code" href="a00020.html" title="A node in a graph.">node</a> up_until_marked(<a class="code" href="a00020.html" title="A node in a graph.">node</a> act,
<a name="l00444"></a>00444                          <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;int&gt;</a>&amp; mark,
<a name="l00445"></a>00445                          <a class="code" href="a00026.html" title="ST-number algorithm.">st_number</a>&amp; st);
<a name="l00446"></a>00446 
<a name="l00455"></a>00455     pq_leaf* search_full_leaf (pq_node* n);
<a name="l00456"></a>00456         
<a name="l00465"></a>00465     pq_leaf* search_empty_leaf(pq_node* n);
<a name="l00466"></a>00466 
<a name="l00478"></a>00478     <span class="keywordtype">void</span> case_A(p_node* p_fail,
<a name="l00479"></a>00479                 <a class="code" href="a00020.html" title="A node in a graph.">node</a> act,
<a name="l00480"></a>00480                 <a class="code" href="a00026.html" title="ST-number algorithm.">st_number</a>&amp; _st,
<a name="l00481"></a>00481                 <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;edge&gt;</a> to_father,
<a name="l00482"></a>00482                 <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G);
<a name="l00483"></a>00483 
<a name="l00495"></a>00495     <span class="keywordtype">void</span> case_B(p_node* p_fail,
<a name="l00496"></a>00496                 <a class="code" href="a00020.html" title="A node in a graph.">node</a> act,
<a name="l00497"></a>00497                 <a class="code" href="a00026.html" title="ST-number algorithm.">st_number</a>&amp; _st,
<a name="l00498"></a>00498                 <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;edge&gt;</a> to_father,
<a name="l00499"></a>00499                 <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G);
<a name="l00500"></a>00500 
<a name="l00515"></a>00515     <span class="keywordtype">void</span> case_C(<a class="code" href="a00020.html" title="A node in a graph.">node</a>* nodes,
<a name="l00516"></a>00516                 pq_leaf** leaves,
<a name="l00517"></a>00517                 <a class="code" href="a00026.html" title="ST-number algorithm.">st_number</a>&amp; _st,
<a name="l00518"></a>00518                 <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;edge&gt;</a> to_father,
<a name="l00519"></a>00519                 <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G,
<a name="l00520"></a>00520                 q_node* q_fail);
<a name="l00521"></a>00521 
<a name="l00536"></a>00536     <span class="keywordtype">void</span> case_D(<a class="code" href="a00020.html" title="A node in a graph.">node</a>* nodes,
<a name="l00537"></a>00537                 pq_leaf** leaves,
<a name="l00538"></a>00538                 <a class="code" href="a00026.html" title="ST-number algorithm.">st_number</a>&amp; _st,
<a name="l00539"></a>00539                 <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;edge&gt;</a> to_father,
<a name="l00540"></a>00540                 <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G,
<a name="l00541"></a>00541                 q_node* q_fail);
<a name="l00542"></a>00542 
<a name="l00557"></a>00557     <span class="keywordtype">void</span> case_E(<a class="code" href="a00020.html" title="A node in a graph.">node</a>* nodes,
<a name="l00558"></a>00558                 pq_leaf** leaves,
<a name="l00559"></a>00559                 <a class="code" href="a00026.html" title="ST-number algorithm.">st_number</a>&amp; _st,
<a name="l00560"></a>00560                 <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;edge&gt;</a> to_father,
<a name="l00561"></a>00561                 <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G,
<a name="l00562"></a>00562                 q_node* q_fail);
<a name="l00563"></a>00563 
<a name="l00564"></a>00564 <span class="preprocessor">#ifdef _DEBUG</span>
<a name="l00565"></a>00565 <span class="preprocessor"></span>
<a name="l00568"></a>00568     <span class="keywordtype">void</span> write_bushform(<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G, <a class="code" href="a00026.html" title="ST-number algorithm.">st_number</a>&amp; _st, <span class="keywordtype">int</span> k, <span class="keyword">const</span> <span class="keywordtype">char</span>* name,
<a name="l00569"></a>00569                         <span class="keyword">const</span> <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;int&gt;</a>&amp; mark, <span class="keyword">const</span> <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;edge&gt;</a>&amp; to_father);
<a name="l00570"></a>00570 
<a name="l00574"></a>00574     <span class="keywordtype">void</span> write_node(ostream&amp; os, <span class="keywordtype">int</span> <span class="keywordtype">id</span>, <span class="keywordtype">int</span> label, <span class="keywordtype">int</span> mark);
<a name="l00575"></a>00575 <span class="preprocessor">#endif</span>
<a name="l00576"></a>00576 <span class="preprocessor"></span>    
<a name="l00580"></a>00580     list&lt;edge&gt; ob_edges;
<a name="l00581"></a>00581     
<a name="l00585"></a>00585     list&lt;node&gt; ob_nodes;
<a name="l00586"></a>00586     
<a name="l00590"></a>00590     <a class="code" href="a00022.html" title="Ordered adjacency lists as a result of planarity testing.">planar_embedding</a> embedding;
<a name="l00591"></a>00591     
<a name="l00595"></a>00595     <span class="keywordtype">bool</span> planar;
<a name="l00596"></a>00596     
<a name="l00600"></a>00600     <span class="keywordtype">bool</span> emp;
<a name="l00601"></a>00601     
<a name="l00605"></a>00605     <span class="keywordtype">bool</span> kup;
<a name="l00606"></a>00606     
<a name="l00610"></a>00610     <span class="keywordtype">bool</span> bip;
<a name="l00611"></a>00611 };
<a name="l00612"></a>00612 
<a name="l00613"></a>00613 __GTL_END_NAMESPACE
<a name="l00614"></a>00614 
<a name="l00615"></a>00615 <span class="preprocessor">#endif // PLANARITY_H</span>
<a name="l00616"></a>00616 <span class="preprocessor"></span>
<a name="l00617"></a>00617 <span class="comment">//--------------------------------------------------------------------------</span>
<a name="l00618"></a>00618 <span class="comment">//   end of file</span>
<a name="l00619"></a>00619 <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>