Home Esplora Aiuto
Accedi
mooigraph
/
regraphlet
Segui 1
Vota 0
Forka 0
File Problemi 0 Pull Requests 0 Wiki
Albero (Tree): 8a3496fffe
Rami (Branch) Tag
regraphlet
/
orig
/
GTL-1.2.4
/
doc
/
manual
/
a00100.html

a00100.html 8.0 KB
Cronologia Originale

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899 
  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: topsort.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>topsort.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">//   topsort.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: topsort.h,v 1.8 2000/09/11 07:36:43 raitner Exp $</span>
    34. 

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

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

  36. <a name="l00009"></a>00009 <span class="preprocessor"></span><span class="preprocessor">#define GTL_TOPSORT</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/dfs.h&gt;</span>
    40. 

  40. <a name="l00013"></a>00013 
    41. 

  41. <a name="l00014"></a>00014 __GTL_BEGIN_NAMESPACE
    42. 

  42. <a name="l00015"></a>00015 
    43. 

  43. <a name="l00034"></a><a class="code" href="a00028.html">00034</a> <span class="keyword">class </span>GTL_EXTERN <a class="code" href="a00028.html" title="Topological sorting.">topsort</a> : <span class="keyword">public</span> <a class="code" href="a00008.html" title="Depth-First-Search (DFS) algorithm.">dfs</a> 
    44. 

  44. <a name="l00035"></a>00035 {
    45. 

  45. <a name="l00036"></a>00036 <span class="keyword">public</span>:
    46. 

  46. <a name="l00042"></a><a class="code" href="a00028.html#76a9055969b9dbf006320040be9fd5e6">00042</a>     <a class="code" href="a00028.html" title="Topological sorting.">topsort</a> () : <a class="code" href="a00008.html" title="Depth-First-Search (DFS) algorithm.">dfs</a> () {whole_graph = <span class="keyword">true</span>; acyclic = <span class="keyword">true</span>;}
    47. 

  47. <a name="l00043"></a>00043 
    48. 

  48. <a name="l00050"></a><a class="code" href="a00028.html#71069dab2159b75a324f3b8a44a88ced">00050</a>     <span class="keywordtype">int</span> top_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>
    49. 

  49. <a name="l00051"></a>00051 <span class="keyword">        </span>{ <span class="keywordflow">return</span> top_numbers[n]; }
    50. 

  50. <a name="l00052"></a>00052 
    51. 

  51. <a name="l00058"></a><a class="code" href="a00028.html#6df72e7e38299c30695e9391c3b04383">00058</a>     <span class="keywordtype">bool</span> is_acyclic ()<span class="keyword"> const</span>
    52. 

  52. <a name="l00059"></a>00059 <span class="keyword">        </span>{ <span class="keywordflow">return</span> acyclic; }
    53. 

  53. <a name="l00060"></a>00060 
    54. 

  54. <a name="l00064"></a>00064     <span class="keyword">typedef</span> list&lt;node&gt;::const_iterator topsort_iterator;
    55. 

  55. <a name="l00065"></a>00065 
    56. 

  56. <a name="l00071"></a><a class="code" href="a00028.html#f2b446d051fceb0df31df7057e03025b">00071</a>     topsort_iterator top_order_begin()<span class="keyword"> const</span>
    57. 

  57. <a name="l00072"></a>00072 <span class="keyword">        </span>{ <span class="keywordflow">return</span> top_order.begin(); }
    58. 

  58. <a name="l00073"></a>00073 
    59. 

  59. <a name="l00079"></a><a class="code" href="a00028.html#b4d0debf92c9e5eeceec48856af4b329">00079</a>     topsort_iterator top_order_end()<span class="keyword"> const</span>
    60. 

  60. <a name="l00080"></a>00080 <span class="keyword">        </span>{ <span class="keywordflow">return</span> top_order.end(); }
    61. 

  61. <a name="l00081"></a>00081 
    62. 

  62. <a name="l00094"></a>00094     <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);
    63. 

  63. <a name="l00095"></a>00095 
    64. 

  64. <a name="l00100"></a>00100     <span class="keyword">virtual</span> <span class="keywordtype">void</span> <a class="code" href="a00008.html#1c893f699517cc72624cf171b7bc4da4" title="Resets algorithm.">reset</a> ();
    65. 

  65. <a name="l00101"></a>00101 
    66. 

  66. <a name="l00105"></a>00105     <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; G);
    67. 

  67. <a name="l00106"></a>00106 
    68. 

  68. <a name="l00110"></a>00110     <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;);
    69. 

  69. <a name="l00111"></a>00111 
    70. 

  70. <a name="l00115"></a>00115     <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;);
    71. 

  71. <a name="l00116"></a>00116 
    72. 

  72. <a name="l00117"></a>00117 <span class="keyword">protected</span>:
    73. 

  73. <a name="l00121"></a>00121     <span class="keywordtype">int</span> act_top_num;
    74. 

  74. <a name="l00125"></a>00125     <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;int&gt;</a> top_numbers;
    75. 

  75. <a name="l00129"></a>00129     list&lt;node&gt; top_order;
    76. 

  76. <a name="l00133"></a>00133     <span class="keywordtype">bool</span> acyclic;
    77. 

  77. <a name="l00134"></a>00134 };
    78. 

  78. <a name="l00135"></a>00135 
    79. 

  79. <a name="l00136"></a>00136 __GTL_END_NAMESPACE
    80. 

  80. <a name="l00137"></a>00137 
    81. 

  81. <a name="l00138"></a>00138 <span class="preprocessor">#endif // GTL_TOPSORT</span>
    82. 

  82. <a name="l00139"></a>00139 <span class="preprocessor"></span>
    83. 

  83. <a name="l00140"></a>00140 <span class="comment">//--------------------------------------------------------------------------</span>
    84. 

  84. <a name="l00141"></a>00141 <span class="comment">//   end of file</span>
    85. 

  85. <a name="l00142"></a>00142 <span class="comment">//--------------------------------------------------------------------------</span>
    86. 

  86. </pre></div>    <p class="links">
    87. 

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

  88.       &nbsp;-&nbsp;
    89. 

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

  90.       &nbsp;-&nbsp;
    91. 

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

  92. 	Computer Science</a>
    93. 

  93.     </p>
    94. 

  94.   <div class="copyright">
    95. 

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

  96.   </div>
    97. 

  97. </body>
    98. 

  98. </html>
    99. 

  99.