Startseite Erkunden Hilfe
Anmelden
mooigraph
/
regraphlet
Beobachten 1
Favorit hinzufügen 0
Fork 0
Dateien Issues 0 Pull-Requests 0 Wiki
Struktur: 8a3496fffe
Branches Tags
regraphlet
/
orig
/
GTL-1.2.4
/
doc
/
manual
/
a00098.html

a00098.html 17 KB
Verlauf Originalformat

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247 
  1. <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
    2. 

  2. <html>
    3. 

  3.   <head>
    4. 

  4.     <meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
    5. 

  5.       <title>GTL - Graph Template Library: st_number.h Source File</title>
    6. 

  6.       <link href="doxygen.css" rel="stylesheet" type="text/css">
    7. 

  7.   </head>
    8. 

  8.   <body>
    9. 

  9.     <p class="links">  
    10. 

  10.       <a href="../index.html">Home</a> |
    11. 

  11.       Documentation |
    12. 

  12.       <a href="../register.html">Download</a> |
    13. 

  13.       <a href="../platforms.html">Platforms</a> |
    14. 

  14.       <a href="../refer.html">Projects</a> |      
    15. 

  15.       <a href="../lists.html">Mailing Lists</a> |
    16. 

  16.       <a href="../history.html">Version History</a>
    17. 

  17.     </p>
    18. 

  18. 

  19. <!-- Generated by Doxygen 1.5.3 -->
    20. 

  20. <div class="tabs">
    21. 

  21.   <ul>
    22. 

  22.     <li><a href="index.html"><span>Main&nbsp;Page</span></a></li>
    23. 

  23.     <li><a href="classes.html"><span>Classes</span></a></li>
    24. 

  24.     <li class="current"><a href="files.html"><span>Files</span></a></li>
    25. 

  25.     <li><a href="pages.html"><span>Related&nbsp;Pages</span></a></li>
    26. 

  26.   </ul>
    27. 

  27. </div>
    28. 

  28. <h1>st_number.h</h1><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">//==========================================================================</span>
    29. 

  29. <a name="l00002"></a>00002 <span class="comment">//</span>
    30. 

  30. <a name="l00003"></a>00003 <span class="comment">//   st_number.h</span>
    31. 

  31. <a name="l00004"></a>00004 <span class="comment">//</span>
    32. 

  32. <a name="l00005"></a>00005 <span class="comment">//==========================================================================</span>
    33. 

  33. <a name="l00006"></a>00006 <span class="comment">// $Id: st_number.h,v 1.17 2002/12/20 08:26:08 chris Exp $</span>
    34. 

  34. <a name="l00007"></a>00007 
    35. 

  35. <a name="l00008"></a>00008 <span class="preprocessor">#ifndef GTL_ST_NUMBER_H</span>
    36. 

  36. <a name="l00009"></a>00009 <span class="preprocessor"></span><span class="preprocessor">#define GTL_ST_NUMBER_H</span>
    37. 

  37. <a name="l00010"></a>00010 <span class="preprocessor"></span>
    38. 

  38. <a name="l00011"></a>00011 <span class="preprocessor">#include &lt;GTL/GTL.h&gt;</span>
    39. 

  39. <a name="l00012"></a>00012 <span class="preprocessor">#include &lt;GTL/graph.h&gt;</span>
    40. 

  40. <a name="l00013"></a>00013 <span class="preprocessor">#include &lt;GTL/node_map.h&gt;</span>
    41. 

  41. <a name="l00014"></a>00014 <span class="preprocessor">#include &lt;GTL/edge_map.h&gt;</span>
    42. 

  42. <a name="l00015"></a>00015 <span class="preprocessor">#include &lt;GTL/algorithm.h&gt;</span>
    43. 

  43. <a name="l00016"></a>00016 
    44. 

  44. <a name="l00017"></a>00017 <span class="preprocessor">#include &lt;list&gt;</span>
    45. 

  45. <a name="l00018"></a>00018 <span class="preprocessor">#include &lt;utility&gt;</span>
    46. 

  46. <a name="l00019"></a>00019 
    47. 

  47. <a name="l00020"></a>00020 __GTL_BEGIN_NAMESPACE
    48. 

  48. <a name="l00021"></a>00021 
    49. 

  49. <a name="l00025"></a>00025 <span class="keyword">class </span>GTL_EXTERN pathfinder 
    50. 

  50. <a name="l00026"></a>00026 {
    51. 

  51. <a name="l00027"></a>00027 <span class="keyword">public</span>:
    52. 

  52. <a name="l00028"></a>00028     <span class="comment">//---------------------------------------------------------- CONSTRUCTOR</span>
    53. 

  53. <a name="l00029"></a>00029         
    54. 

  54. <a name="l00033"></a>00033     pathfinder(<span class="keyword">const</span> <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> st, <a class="code" href="a00020.html" title="A node in a graph.">node</a> s);    
    55. 

  55. <a name="l00034"></a>00034         
    56. 

  56. <a name="l00038"></a>00038     <span class="keywordtype">bool</span> is_valid()
    57. 

  57. <a name="l00039"></a>00039     {
    58. 

  58. <a name="l00040"></a>00040         <span class="keywordflow">return</span> is_biconn;
    59. 

  59. <a name="l00041"></a>00041     }
    60. 

  60. <a name="l00042"></a>00042         
    61. 

  61. <a name="l00043"></a>00043     <span class="comment">//------------------------------------------------------------- ITERATOR</span>
    62. 

  62. <a name="l00044"></a>00044         
    63. 

  63. <a name="l00048"></a>00048     <span class="keyword">class </span>const_iterator 
    64. 

  64. <a name="l00049"></a>00049     {
    65. 

  65. <a name="l00050"></a>00050     <span class="keyword">public</span>:
    66. 

  66. <a name="l00054"></a>00054         const_iterator(pathfinder&amp; _pf) : pf (_pf)
    67. 

  67. <a name="l00055"></a>00055         {
    68. 

  68. <a name="l00056"></a>00056         }
    69. 

  69. <a name="l00057"></a>00057 
    70. 

  70. <a name="l00061"></a>00061         const_iterator(pathfinder&amp; _pf, <a class="code" href="a00020.html" title="A node in a graph.">node</a> n);        
    71. 

  71. <a name="l00062"></a>00062                 
    72. 

  72. <a name="l00066"></a>00066         const_iterator&amp; operator++();
    73. 

  73. <a name="l00070"></a>00070         const_iterator operator++(<span class="keywordtype">int</span>);
    74. 

  74. <a name="l00074"></a>00074         <span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp; operator*()<span class="keyword"> const </span>
    75. 

  75. <a name="l00075"></a>00075 <span class="keyword">        </span>{
    76. 

  76. <a name="l00076"></a>00076             <span class="keywordflow">return</span> curr;
    77. 

  77. <a name="l00077"></a>00077         }
    78. 

  78. <a name="l00078"></a>00078                 
    79. 

  79. <a name="l00082"></a>00082         <span class="keywordtype">bool</span> operator==(<span class="keyword">const</span> const_iterator&amp; it) 
    80. 

  80. <a name="l00083"></a>00083         {
    81. 

  81. <a name="l00084"></a>00084             <span class="keywordflow">return</span> curr == it.curr;
    82. 

  82. <a name="l00085"></a>00085         }
    83. 

  83. <a name="l00086"></a>00086 
    84. 

  84. <a name="l00090"></a>00090         <span class="keywordtype">bool</span> operator!=(<span class="keyword">const</span> const_iterator&amp; it)
    85. 

  85. <a name="l00091"></a>00091         {
    86. 

  86. <a name="l00092"></a>00092             <span class="keywordflow">return</span> curr != it.curr;
    87. 

  87. <a name="l00093"></a>00093         }
    88. 

  88. <a name="l00094"></a>00094     <span class="keyword">private</span>:
    89. 

  89. <a name="l00098"></a>00098         <span class="keyword">enum</span> iteration_state {END, UP, DOWN};
    90. 

  90. <a name="l00099"></a>00099 
    91. 

  91. <a name="l00103"></a>00103         iteration_state state;
    92. 

  92. <a name="l00104"></a>00104 
    93. 

  93. <a name="l00108"></a>00108         <a class="code" href="a00020.html" title="A node in a graph.">node</a> curr;
    94. 

  94. <a name="l00109"></a>00109 
    95. 

  95. <a name="l00113"></a>00113         pathfinder&amp; pf;
    96. 

  96. <a name="l00114"></a>00114     };
    97. 

  97. <a name="l00115"></a>00115         
    98. 

  98. <a name="l00119"></a>00119     const_iterator path(<a class="code" href="a00020.html" title="A node in a graph.">node</a> n)
    99. 

  99. <a name="l00120"></a>00120     {
    100. 

  100. <a name="l00121"></a>00121         <span class="keywordflow">return</span> const_iterator(*<span class="keyword">this</span>, n);
    101. 

  101. <a name="l00122"></a>00122     }
    102. 

  102. <a name="l00123"></a>00123         
    103. 

  103. <a name="l00127"></a>00127     const_iterator end()
    104. 

  104. <a name="l00128"></a>00128     {
    105. 

  105. <a name="l00129"></a>00129         <span class="keywordflow">return</span> const_iterator (*<span class="keyword">this</span>);
    106. 

  106. <a name="l00130"></a>00130     }
    107. 

  107. <a name="l00131"></a>00131         
    108. 

  108. <a name="l00132"></a>00132 <span class="keyword">private</span>:
    109. 

  109. <a name="l00133"></a>00133     <span class="comment">//------------------------------------------------------------ FUNCTIONS</span>
    110. 

  110. <a name="l00134"></a>00134                 
    111. 

  111. <a name="l00138"></a>00138     <span class="keywordtype">void</span> dfs_sub (<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;);
    112. 

  112. <a name="l00139"></a>00139                 
    113. 

  113. <a name="l00140"></a>00140     <span class="comment">//-------------------------------------------------------------- MEMBERS </span>
    114. 

  114. <a name="l00141"></a>00141                 
    115. 

  115. <a name="l00145"></a>00145     <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;int&gt;</a> dfs_num;
    116. 

  116. <a name="l00146"></a>00146 
    117. 

  117. <a name="l00150"></a>00150     <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;int&gt;</a> low_num;
    118. 

  118. <a name="l00151"></a>00151 
    119. 

  119. <a name="l00155"></a>00155     <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;list&lt;edge&gt;</a> &gt; tree;
    120. 

  120. <a name="l00156"></a>00156 
    121. 

  121. <a name="l00160"></a>00160     <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;list&lt;edge&gt;</a> &gt; back;
    122. 

  122. <a name="l00161"></a>00161 
    123. 

  123. <a name="l00165"></a>00165     <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;list&lt;edge&gt;</a> &gt; forward;
    124. 

  124. <a name="l00166"></a>00166 
    125. 

  125. <a name="l00170"></a>00170     <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;list&lt;edge&gt;::iterator</a>&gt; to_low;
    126. 

  126. <a name="l00171"></a>00171 
    127. 

  127. <a name="l00175"></a>00175     <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;list&lt;edge&gt;::iterator</a>&gt; to_father;
    128. 

  128. <a name="l00176"></a>00176                 
    129. 

  129. <a name="l00180"></a>00180     <span class="keyword">typedef</span> pair&lt;list&lt;edge&gt;::iterator, list&lt;edge&gt;::iterator&gt; pos_pair;
    130. 

  130. <a name="l00181"></a>00181 
    131. 

  131. <a name="l00185"></a>00185     <a class="code" href="a00011.html" title="A specialized map with edges as keys.">edge_map&lt;pos_pair &gt;</a> pos;
    132. 

  132. <a name="l00186"></a>00186 
    133. 

  133. <a name="l00190"></a>00190     <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;int&gt;</a> used;
    134. 

  134. <a name="l00191"></a>00191                 
    135. 

  135. <a name="l00195"></a>00195     <span class="keywordtype">int</span> act_dfs_num;
    136. 

  136. <a name="l00196"></a>00196 
    137. 

  137. <a name="l00200"></a>00200     <span class="keywordtype">int</span> new_nodes;
    138. 

  138. <a name="l00201"></a>00201 
    139. 

  139. <a name="l00205"></a>00205     <span class="keywordtype">bool</span> is_biconn;
    140. 

  140. <a name="l00206"></a>00206                 
    141. 

  141. <a name="l00211"></a>00211     <span class="keyword">friend</span> <span class="keyword">class </span>const_iterator;
    142. 

  142. <a name="l00212"></a>00212 };
    143. 

  143. <a name="l00213"></a>00213 
    144. 

  144. <a name="l00232"></a><a class="code" href="a00026.html">00232</a> <span class="keyword">class </span>GTL_EXTERN <a class="code" href="a00026.html" title="ST-number algorithm.">st_number</a> : <span class="keyword">public</span> <a class="code" href="a00001.html" title="Abstract baseclass for all algoritm-classes.">algorithm</a> 
    145. 

  145. <a name="l00233"></a>00233 {
    146. 

  146. <a name="l00234"></a>00234 <span class="keyword">public</span>:
    147. 

  147. <a name="l00242"></a><a class="code" href="a00026.html#07532323fbcc643dfc419809385b64a7">00242</a>     <a class="code" href="a00026.html" title="ST-number algorithm.">st_number</a>() : <a class="code" href="a00001.html" title="Abstract baseclass for all algoritm-classes.">algorithm</a>()
    148. 

  148. <a name="l00243"></a>00243     {
    149. 

  149. <a name="l00244"></a>00244     }
    150. 

  150. <a name="l00245"></a>00245 
    151. 

  151. <a name="l00249"></a><a class="code" href="a00026.html#4f3a2a6ceab39d106c920ee3546c259d">00249</a>     <span class="keyword">virtual</span> ~<a class="code" href="a00026.html" title="ST-number algorithm.">st_number</a>()
    152. 

  152. <a name="l00250"></a>00250     {
    153. 

  153. <a name="l00251"></a>00251     }
    154. 

  154. <a name="l00252"></a>00252         
    155. 

  155. <a name="l00258"></a><a class="code" href="a00026.html#1564af6f603160105643f22bf2f6955b">00258</a>     <span class="keywordtype">void</span> st_edge(<a class="code" href="a00010.html" title="An edge in a graph.">edge</a> e)
    156. 

  156. <a name="l00259"></a>00259     {
    157. 

  157. <a name="l00260"></a>00260         st = e;
    158. 

  158. <a name="l00261"></a>00261     }
    159. 

  159. <a name="l00262"></a>00262 
    160. 

  160. <a name="l00268"></a><a class="code" href="a00026.html#58fc3b24be01d7b06fd4b6f94340e1c3">00268</a>     <a class="code" href="a00010.html" title="An edge in a graph.">edge</a> st_edge()<span class="keyword"> const</span>
    161. 

  161. <a name="l00269"></a>00269 <span class="keyword">    </span>{
    162. 

  162. <a name="l00270"></a>00270         <span class="keywordflow">return</span> st;
    163. 

  163. <a name="l00271"></a>00271     }
    164. 

  164. <a name="l00272"></a>00272 
    165. 

  165. <a name="l00282"></a><a class="code" href="a00026.html#a607c9aaa5a4d9c45e5854ce672f0fda">00282</a>     <span class="keywordtype">void</span> s_node(<a class="code" href="a00020.html" title="A node in a graph.">node</a> n) 
    166. 

  166. <a name="l00283"></a>00283     {
    167. 

  167. <a name="l00284"></a>00284         s = n;
    168. 

  168. <a name="l00285"></a>00285     }
    169. 

  169. <a name="l00286"></a>00286 
    170. 

  170. <a name="l00292"></a><a class="code" href="a00026.html#48e4837ebed88445c1f594024d8753dc">00292</a>     <a class="code" href="a00020.html" title="A node in a graph.">node</a> s_node()<span class="keyword"> const</span>
    171. 

  171. <a name="l00293"></a>00293 <span class="keyword">    </span>{
    172. 

  172. <a name="l00294"></a>00294         <span class="keywordflow">return</span> s;
    173. 

  173. <a name="l00295"></a>00295     }
    174. 

  174. <a name="l00296"></a>00296 
    175. 

  175. <a name="l00304"></a><a class="code" href="a00026.html#969162a10da5daba4219419d45c4be51">00304</a>     <span class="keywordtype">int</span>&amp; operator[](<span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp; n)
    176. 

  176. <a name="l00305"></a>00305     {
    177. 

  177. <a name="l00306"></a>00306         <span class="keywordflow">return</span> st_num[n];
    178. 

  178. <a name="l00307"></a>00307     }
    179. 

  179. <a name="l00308"></a>00308     
    180. 

  180. <a name="l00312"></a>00312     <span class="keyword">typedef</span> list&lt;node&gt;::iterator iterator;
    181. 

  181. <a name="l00313"></a>00313 
    182. 

  182. <a name="l00317"></a>00317     <span class="keyword">typedef</span> list&lt;node&gt;::reverse_iterator reverse_iterator;
    183. 

  183. <a name="l00318"></a>00318         
    184. 

  184. <a name="l00325"></a><a class="code" href="a00026.html#1eddb2577b16109d22cde98a8ffde057">00325</a>     iterator begin()
    185. 

  185. <a name="l00326"></a>00326     {
    186. 

  186. <a name="l00327"></a>00327         <span class="keywordflow">return</span> st_ord.begin();
    187. 

  187. <a name="l00328"></a>00328     }   
    188. 

  188. <a name="l00329"></a>00329 
    189. 

  189. <a name="l00335"></a><a class="code" href="a00026.html#3912b83a8cbddcb1fc804d20be528d52">00335</a>     iterator end()
    190. 

  190. <a name="l00336"></a>00336     {
    191. 

  191. <a name="l00337"></a>00337         <span class="keywordflow">return</span> st_ord.end();
    192. 

  192. <a name="l00338"></a>00338     }
    193. 

  193. <a name="l00339"></a>00339         
    194. 

  194. <a name="l00347"></a><a class="code" href="a00026.html#56f2c67e9b49362947fe0c99278f6d31">00347</a>     reverse_iterator rbegin()
    195. 

  195. <a name="l00348"></a>00348     {
    196. 

  196. <a name="l00349"></a>00349         <span class="keywordflow">return</span> st_ord.rbegin();
    197. 

  197. <a name="l00350"></a>00350     }
    198. 

  198. <a name="l00351"></a>00351         
    199. 

  199. <a name="l00358"></a><a class="code" href="a00026.html#4c5fdce6ab2be7ee9ddbb09e8d5c8560">00358</a>     reverse_iterator rend()
    200. 

  200. <a name="l00359"></a>00359     {
    201. 

  201. <a name="l00360"></a>00360         <span class="keywordflow">return</span> st_ord.rend();
    202. 

  202. <a name="l00361"></a>00361     }
    203. 

  203. <a name="l00362"></a>00362         
    204. 

  204. <a name="l00363"></a>00363 
    205. 

  205. <a name="l00379"></a>00379     <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);
    206. 

  206. <a name="l00380"></a>00380 
    207. 

  207. <a name="l00381"></a>00381 
    208. 

  208. <a name="l00394"></a>00394     <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);
    209. 

  209. <a name="l00395"></a>00395 
    210. 

  210. <a name="l00396"></a>00396 
    211. 

  211. <a name="l00404"></a><a class="code" href="a00026.html#e6f86706b8ae3495d3794b8c684fff0f">00404</a>     <span class="keywordtype">void</span> <a class="code" href="a00001.html#21aba63d066ae7897de6ca7d8425c408" title="Resets algorithm.">reset</a>()
    212. 

  212. <a name="l00405"></a>00405     {
    213. 

  213. <a name="l00406"></a>00406         st_ord.erase (st_ord.begin(), st_ord.end());
    214. 

  214. <a name="l00407"></a>00407     }
    215. 

  215. <a name="l00408"></a>00408 <span class="keyword">protected</span>:
    216. 

  216. <a name="l00412"></a>00412     <a class="code" href="a00010.html" title="An edge in a graph.">edge</a> st;
    217. 

  217. <a name="l00413"></a>00413 
    218. 

  218. <a name="l00417"></a>00417     <a class="code" href="a00020.html" title="A node in a graph.">node</a> s;
    219. 

  219. <a name="l00418"></a>00418 
    220. 

  220. <a name="l00422"></a>00422     pathfinder* pf;
    221. 

  221. <a name="l00423"></a>00423 
    222. 

  222. <a name="l00427"></a>00427     list&lt;node&gt; st_ord;
    223. 

  223. <a name="l00428"></a>00428 
    224. 

  224. <a name="l00432"></a>00432     <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;int&gt;</a> st_num;
    225. 

  225. <a name="l00433"></a>00433 };
    226. 

  226. <a name="l00434"></a>00434 
    227. 

  227. <a name="l00435"></a>00435 __GTL_END_NAMESPACE
    228. 

  228. <a name="l00436"></a>00436 
    229. 

  229. <a name="l00437"></a>00437 <span class="preprocessor">#endif // GTL_ST_NUMBER_H</span>
    230. 

  230. <a name="l00438"></a>00438 <span class="preprocessor"></span>
    231. 

  231. <a name="l00439"></a>00439 <span class="comment">//--------------------------------------------------------------------------</span>
    232. 

  232. <a name="l00440"></a>00440 <span class="comment">//   end of file</span>
    233. 

  233. <a name="l00441"></a>00441 <span class="comment">//--------------------------------------------------------------------------</span>
    234. 

  234. </pre></div>    <p class="links">
    235. 

  235.       <a href="http://www.uni-passau.de/">University of Passau</a>
    236. 

  236.       &nbsp;-&nbsp;
    237. 

  237.       <a href="http://www.fmi.uni-passau.de/">FMI</a>
    238. 

  238.       &nbsp;-&nbsp;
    239. 

  239.       <a href="http://www.fmi.uni-passau.de/fmi/lehrstuehle/brandenburg/">Theoretical
    240. 

  240. 	Computer Science</a>
    241. 

  241.     </p>
    242. 

  242.   <div class="copyright">
    243. 

  243.       Design &copy; 2002, 2003 <a href="mailto:raitner@fmi.uni-passau.de">Marcus Raitner</a>,  University of Passau 
    244. 

  244.   </div>
    245. 

  245. </body>
    246. 

  246. </html>
    247. 

  247.