mooigraph
/
regraphlet


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275
							<!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: dfs Class Reference</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 class="current"><a href="classes.html"><span>Classes</span></a></li>
    <li><a href="files.html"><span>Files</span></a></li>
    <li><a href="pages.html"><span>Related&nbsp;Pages</span></a></li>
  </ul>
</div>
<div class="tabs">
  <ul>
    <li><a href="classes.html"><span>Alphabetical&nbsp;List</span></a></li>
    <li><a href="annotated.html"><span>Class&nbsp;List</span></a></li>
    <li><a href="hierarchy.html"><span>Class&nbsp;Hierarchy</span></a></li>
    <li><a href="functions.html"><span>Class&nbsp;Members</span></a></li>
  </ul>
</div>
<h1>dfs Class Reference</h1><!-- doxytag: class="dfs" --><!-- doxytag: inherits="algorithm" -->Depth-First-Search (DFS) algorithm.  
<a href="#_details">More...</a>
<p>
<div class="dynheader">
Inheritance diagram for dfs:</div>
<div class="dynsection">
<p><center><img src="a00131.gif" border="0" usemap="#a00132" alt="Inheritance graph"></center>
<map name="a00132">
<area shape="rect" href="a00004.html" title="Biconnectivity&#45;test and low&#45;numbers." alt="" coords="5,156,109,180"><area shape="rect" href="a00007.html" title="Connected components algorithm." alt="" coords="133,156,227,180"><area shape="rect" href="a00028.html" title="Topological sorting." alt="" coords="251,156,315,180"><area shape="rect" href="a00001.html" title="Abstract baseclass for all algoritm&#45;classes." alt="" coords="141,7,219,31"></map>
<center><font size="2">[<a href="graph_legend.html">legend</a>]</font></center></div>
<div class="dynheader">
Collaboration diagram for dfs:</div>
<div class="dynsection">
<p><center><img src="a00133.gif" border="0" usemap="#a00134" alt="Collaboration graph"></center>
<map name="a00134">
<area shape="rect" href="a00001.html" title="Abstract baseclass for all algoritm&#45;classes." alt="" coords="401,5,479,29"><area shape="rect" href="a00020.html" title="A node in a graph." alt="" coords="415,92,465,116"><area shape="rect" title="start" alt="" coords="463,100,471,108"><area shape="rect" title="start" alt="" coords="648,143,656,151"><area shape="rect" title="int_node" alt="" coords="411,89,419,97"><area shape="rect" title="int_node" alt="" coords="463,89,471,97"><area shape="rect" href="a00021.html" title="node_map\&lt; int \&gt;" alt="" coords="379,144,501,168"><area shape="rect" title="comp_number\ndfs_number" alt="" coords="497,153,505,161"><area shape="rect" title="comp_number\ndfs_number" alt="" coords="641,155,649,163"><area shape="rect" href="a00019.html" title="ne_map\&lt; node, int, graph, allocator\&lt; int \&gt; \&gt;" alt="" coords="21,144,304,168"><area shape="rect" href="a00011.html" title="edge_map\&lt; int \&gt;" alt="" coords="379,192,501,216"><area shape="rect" title="used" alt="" coords="497,196,505,204"><area shape="rect" title="used" alt="" coords="641,165,649,173"><area shape="rect" href="a00019.html" title="ne_map\&lt; edge, int, graph, allocator\&lt; int \&gt; \&gt;" alt="" coords="21,192,304,216"><area shape="rect" href="a00021.html" title="node_map\&lt; node \&gt;" alt="" coords="371,240,509,264"><area shape="rect" title="preds" alt="" coords="505,247,513,255"><area shape="rect" title="preds" alt="" coords="656,168,664,176"><area shape="rect" href="a00019.html" title="ne_map\&lt; node, node, graph, allocator\&lt; node \&gt; \&gt;" alt="" coords="5,240,320,264"></map>
<center><font size="2">[<a href="graph_legend.html">legend</a>]</font></center></div>

<p>
<a href="a00135.html">List of all members.</a><table border="0" cellpadding="0" cellspacing="0">
<tr><td></td></tr>
<tr><td colspan="2"><br><h2>Public Types</h2></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="0eee0ddec5343c05f617d6d7aabb6d19"></a><!-- doxytag: member="dfs::tree_edges_iterator" ref="0eee0ddec5343c05f617d6d7aabb6d19" args="" -->
typedef list&lt; <a class="el" href="a00010.html">edge</a> &gt;<br>
::const_iterator&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#0eee0ddec5343c05f617d6d7aabb6d19">tree_edges_iterator</a></td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Iterator for the tree edges of the DFS-tree. <br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="d040ddae37492e18c8e029406d667bd9"></a><!-- doxytag: member="dfs::dfs_iterator" ref="d040ddae37492e18c8e029406d667bd9" args="" -->
typedef list&lt; <a class="el" href="a00020.html">node</a> &gt;<br>
::const_iterator&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#d040ddae37492e18c8e029406d667bd9">dfs_iterator</a></td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Iterator for the (reached) nodes in DFS-order. <br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="e7301f3d4417e60fb3a499180375194e"></a><!-- doxytag: member="dfs::non_tree_edges_iterator" ref="e7301f3d4417e60fb3a499180375194e" args="" -->
typedef list&lt; <a class="el" href="a00010.html">edge</a> &gt;<br>
::const_iterator&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#e7301f3d4417e60fb3a499180375194e">non_tree_edges_iterator</a></td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Iterator for the non-tree-edges. <br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="17cb59c8a1fead11fa6b0c85cf5a478e"></a><!-- doxytag: member="dfs::roots_iterator" ref="17cb59c8a1fead11fa6b0c85cf5a478e" args="" -->
typedef list<br>
&lt; <a class="el" href="a00008.html#d040ddae37492e18c8e029406d667bd9">dfs_iterator</a> &gt;<br>
::const_iterator&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#17cb59c8a1fead11fa6b0c85cf5a478e">roots_iterator</a></td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Iterator for the roots of the DFS-forest. <br></td></tr>
<tr><td colspan="2"><br><h2>Public Member Functions</h2></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="2399808134dbabf6aa5e1b2e35a73954"></a><!-- doxytag: member="dfs::dfs" ref="2399808134dbabf6aa5e1b2e35a73954" args="()" -->
&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#2399808134dbabf6aa5e1b2e35a73954">dfs</a> ()</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Constructor. <br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="998e0c28d20bbbbb5a0d705371e4ed00"></a><!-- doxytag: member="dfs::~dfs" ref="998e0c28d20bbbbb5a0d705371e4ed00" args="()" -->
virtual&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#998e0c28d20bbbbb5a0d705371e4ed00">~dfs</a> ()</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Destructor. <br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">int&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#f0863b8974d5fd58cd0375c78ed8163b">run</a> (<a class="el" href="a00014.html">graph</a> &amp;G)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Applies algorithm to graph g.  <a href="#f0863b8974d5fd58cd0375c78ed8163b"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">virtual int&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#908f4ea617ed59767ed334b39a2771d0">check</a> (<a class="el" href="a00014.html">graph</a> &amp;G)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Checks whether the preconditions for DFS are satisfied.  <a href="#908f4ea617ed59767ed334b39a2771d0"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">virtual void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#1c893f699517cc72624cf171b7bc4da4">reset</a> ()</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Resets algorithm.  <a href="#1c893f699517cc72624cf171b7bc4da4"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#ad21fd0d3036350fd341f877d5747852">start_node</a> (const <a class="el" href="a00020.html">node</a> &amp;n)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Sets start-node for DFS.  <a href="#ad21fd0d3036350fd341f877d5747852"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="a00020.html">node</a>&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#0282acea81eb9c0d02ceea109fc25f10">start_node</a> () const </td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Returns start-node for DFS.  <a href="#0282acea81eb9c0d02ceea109fc25f10"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#a7c864a6f3a120720138b187b3ed95b5">scan_whole_graph</a> (bool set)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Enables or disables scanning of the whole graph.  <a href="#a7c864a6f3a120720138b187b3ed95b5"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">bool&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#121e68fa166dc109b9f59f5bad3b0a8f">scan_whole_graph</a> () const </td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Returns true iff the whole <a class="el" href="a00014.html" title="A directed or undirected graph.">graph</a> will be scanned.  <a href="#121e68fa166dc109b9f59f5bad3b0a8f"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#70862ea715c52eb95fb704afd3a6e676">calc_comp_num</a> (bool set)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Enables or Disables the calculation of the completion number.  <a href="#70862ea715c52eb95fb704afd3a6e676"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">bool&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#ba070824c0cd45651083a9c62ac34c1a">calc_comp_num</a> () const </td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Returns true iff completion-numbers will be calculated.  <a href="#ba070824c0cd45651083a9c62ac34c1a"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#7043f46eb3887cbcbb1391fc783407a4">store_preds</a> (bool set)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Enables or disables the storing of predecessors.  <a href="#7043f46eb3887cbcbb1391fc783407a4"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">bool&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#5fdfdf59dbd7616167b47013df79364b">store_preds</a> () const </td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Returns true iff the storing of predecessors is enabled.  <a href="#5fdfdf59dbd7616167b47013df79364b"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#6f54f1c4339eacc8961e795439d4593d">store_non_tree_edges</a> (bool set)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Enables the storing of back-edges.  <a href="#6f54f1c4339eacc8961e795439d4593d"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">bool&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#c81e86d2e2b8f4ef5e34470486717dcf">store_non_tree_edges</a> () const </td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Returns true iff the storing of non-tree-edges is enabled.  <a href="#c81e86d2e2b8f4ef5e34470486717dcf"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">bool&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#174338f8e57a5ba93c08469c2a531a8b">reached</a> (const <a class="el" href="a00020.html">node</a> &amp;n) const </td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Checks whether node <em>n</em> was reached in last DFS.  <a href="#174338f8e57a5ba93c08469c2a531a8b"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">int&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#9309a0573f52643196bef32251cf96df">dfs_num</a> (const <a class="el" href="a00020.html">node</a> &amp;n) const </td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">DFS-Number of <em>n</em>.  <a href="#9309a0573f52643196bef32251cf96df"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">int&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#5aa6d81775ad13d92c6e5a7661041866">operator[]</a> (const <a class="el" href="a00020.html">node</a> &amp;n) const </td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">DFS-Number of <em>n</em>.  <a href="#5aa6d81775ad13d92c6e5a7661041866"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">int&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#1b1c940ed5df7e7b8f825ede1d37f364">comp_num</a> (const <a class="el" href="a00020.html">node</a> &amp;n) const </td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Completion-number of node <em>n</em>, if enabled in last run.  <a href="#1b1c940ed5df7e7b8f825ede1d37f364"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="a00020.html">node</a>&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#7c4dc665c18e987c1eb61b69cb582d4f">father</a> (const <a class="el" href="a00020.html">node</a> &amp;n) const </td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Returns father of <a class="el" href="a00020.html" title="A node in a graph.">node</a> <em>n</em> in DFS-forest.  <a href="#7c4dc665c18e987c1eb61b69cb582d4f"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="a00008.html#0eee0ddec5343c05f617d6d7aabb6d19">tree_edges_iterator</a>&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#7c13e57ce4138032322bc2230a260b9a">tree_edges_begin</a> () const </td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Iterate through all edges picked in last DFS.  <a href="#7c13e57ce4138032322bc2230a260b9a"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="a00008.html#0eee0ddec5343c05f617d6d7aabb6d19">tree_edges_iterator</a>&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#3b2de20ab3cff57507f2db17982a6725">tree_edges_end</a> () const </td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">End-iterator for iteration through all edges picked in last DFS.  <a href="#3b2de20ab3cff57507f2db17982a6725"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="a00008.html#d040ddae37492e18c8e029406d667bd9">dfs_iterator</a>&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#d77350c772b18d305e92d44afe784282">begin</a> () const </td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Iterate through all (reached) nodes in DFS-order.  <a href="#d77350c772b18d305e92d44afe784282"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="a00008.html#d040ddae37492e18c8e029406d667bd9">dfs_iterator</a>&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#08e6a3b0c1f7c9f7d725b586d5c00857">end</a> () const </td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">End-Iterator for iteration through all (reached) nodes in DFS-order.  <a href="#08e6a3b0c1f7c9f7d725b586d5c00857"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="a00008.html#e7301f3d4417e60fb3a499180375194e">non_tree_edges_iterator</a>&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#1f92658af729dff37e76ad3025b98a79">non_tree_edges_begin</a> () const </td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Iterate through all non-tree-edges (if enabled).  <a href="#1f92658af729dff37e76ad3025b98a79"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="a00008.html#e7301f3d4417e60fb3a499180375194e">non_tree_edges_iterator</a>&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#f6c9d194226a73515cab7805d1d2a9cf">non_tree_edges_end</a> () const </td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">End-iterator for iteration through all non-tree-edges (if enabled).  <a href="#f6c9d194226a73515cab7805d1d2a9cf"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="a00008.html#17cb59c8a1fead11fa6b0c85cf5a478e">roots_iterator</a>&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#a084e2afe7b58c7bd94e4a8cf8c630af">roots_begin</a> () const </td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Iterator pointing towards the first root in the DFS-forest.  <a href="#a084e2afe7b58c7bd94e4a8cf8c630af"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="a00008.html#17cb59c8a1fead11fa6b0c85cf5a478e">roots_iterator</a>&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#c074438451c387aaf0cf6aaac79bcd16">roots_end</a> () const </td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Iterator pointing to the end of all roots.  <a href="#c074438451c387aaf0cf6aaac79bcd16"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">int&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#5bffe465fdd599a63a2c3d4593f21187">number_of_reached_nodes</a> () const </td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Number of nodes reached in last DFS.  <a href="#5bffe465fdd599a63a2c3d4593f21187"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">virtual void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#cc82574cd42ab8256e685374bee5fabb">init_handler</a> (<a class="el" href="a00014.html">graph</a> &amp;G)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Handler called before the start of DFS.  <a href="#cc82574cd42ab8256e685374bee5fabb"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">virtual void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#b96c7c6183856dd9e356fdcf50835b32">end_handler</a> (<a class="el" href="a00014.html">graph</a> &amp;G)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Handler called at the end of DFS.  <a href="#b96c7c6183856dd9e356fdcf50835b32"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">virtual void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#73dabe5882226b53494a487b7c34f1d1">entry_handler</a> (<a class="el" href="a00014.html">graph</a> &amp;G, <a class="el" href="a00020.html">node</a> &amp;n, <a class="el" href="a00020.html">node</a> &amp;f)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Handler called when touching node <em>n</em>.  <a href="#73dabe5882226b53494a487b7c34f1d1"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">virtual void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#8071fc4e82deff7ceb2790cd4eb42280">leave_handler</a> (<a class="el" href="a00014.html">graph</a> &amp;G, <a class="el" href="a00020.html">node</a> &amp;n, <a class="el" href="a00020.html">node</a> &amp;f)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Handler called after all the adjacent edges of <em>n</em> have been examined.  <a href="#8071fc4e82deff7ceb2790cd4eb42280"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">virtual void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#e3f095c9fe6106e82c24543da4844ea3">before_recursive_call_handler</a> (<a class="el" href="a00014.html">graph</a> &amp;G, <a class="el" href="a00010.html">edge</a> &amp;e, <a class="el" href="a00020.html">node</a> &amp;n)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Handler called when a unused node <em>n</em> connected to the actual node by <em>e</em> is found.  <a href="#e3f095c9fe6106e82c24543da4844ea3"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">virtual void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#25ae75fe08f1d8c0fedcf9dcae09d092">after_recursive_call_handler</a> (<a class="el" href="a00014.html">graph</a> &amp;G, <a class="el" href="a00010.html">edge</a> &amp;e, <a class="el" href="a00020.html">node</a> &amp;n)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Handler called after the algorithm returns from the subtree starting at <em>n</em> connected to the actual node by <em>e</em>.  <a href="#25ae75fe08f1d8c0fedcf9dcae09d092"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">virtual void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#df1c667188e632761c63f529537c544c">old_adj_node_handler</a> (<a class="el" href="a00014.html">graph</a> &amp;G, <a class="el" href="a00010.html">edge</a> &amp;e, <a class="el" href="a00020.html">node</a> &amp;n)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Handler called when a already marked node <em>n</em> connected to the actual node by <em>e</em> is found during the search of all adjacent edges of the actual node.  <a href="#df1c667188e632761c63f529537c544c"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">virtual void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00008.html#3b5fbea7a7baed9946cfb4444a7f20ea">new_start_handler</a> (<a class="el" href="a00014.html">graph</a> &amp;G, <a class="el" href="a00020.html">node</a> &amp;n)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Called when DFS is started with start-node <em>n</em>.  <a href="#3b5fbea7a7baed9946cfb4444a7f20ea"></a><br></td></tr>
</table>
<hr><a name="_details"></a><h2>Detailed Description</h2>
Depth-First-Search (DFS) algorithm. 
<p>
<dl class="rcs" compact><dt><b>Date</b></dt><dd></dd></dl>
<dl class="rcs" compact><dt><b>Revision</b></dt><dd></dd></dl>
<p>
Encapsulates the DFS algoritm together with all the data produced by a run of DFS. Since there exits so much different things which one might want to calculate during a DFS this class provides basically two different customization features. First it is possible to take influence on the behaviour of this algortihm by changing some of the following options:<ul>
<li><a class="el" href="a00008.html#ad21fd0d3036350fd341f877d5747852" title="Sets start-node for DFS.">dfs::start_node</a> (default: an arbitrary node will be chosen)</li><li><a class="el" href="a00008.html#a7c864a6f3a120720138b187b3ed95b5" title="Enables or disables scanning of the whole graph.">dfs::scan_whole_graph</a> states whether BFS will be continued in the unused part of the graph, if not all nodes were touched at the end of DFS started at the start-node. (default: disabled)</li><li><a class="el" href="a00008.html#70862ea715c52eb95fb704afd3a6e676" title="Enables or Disables the calculation of the completion number.">dfs::calc_comp_num</a> toggle storing of completion-numbers for each node, i.e. a numbering which reflects the order in which nodes were <em>finished</em>. (default: disabled)</li><li><a class="el" href="a00008.html#7043f46eb3887cbcbb1391fc783407a4" title="Enables or disables the storing of predecessors.">dfs::store_preds</a> toggle storing the predecessor of each node, i.e. the father in DFS-tree. (default: disabled)</li><li><a class="el" href="a00008.html#6f54f1c4339eacc8961e795439d4593d" title="Enables the storing of back-edges.">dfs::store_non_tree_edges</a> toggle storing of all non-tree-edges (tree-edges are always stored) in a list and thus enable or disable iteration through all non-tree-edges. (default: disabled)</li></ul>
<p>
But the trouble with most DFS-algorithm is that one always wants to add a little bit of code somewhere in the algorithm. And then there are only two ways to get this done. The more efficient one (in terms of runtime) is to implement the DFS anew and add the new code where necessary. The other way (which is more efficient in terms of code-writing) is to take the algorithm as provided and run through the list of nodes it returns (resulting in an extra factor of 2).<p>
Our DFS-algoritm class provides a new method to add small pieces of code to the algorithm: Handler. These are virtual functions called at well-defined, important states of the algorithm (e.g. before a new recursive call). So the only thing to do is to derive your extended DFS from this class and to override the handlers where needed. In detail there are the following handler supported (have a look at the source code for details):<ul>
<li><a class="el" href="a00008.html#cc82574cd42ab8256e685374bee5fabb" title="Handler called before the start of DFS.">dfs::init_handler</a></li><li><a class="el" href="a00008.html#b96c7c6183856dd9e356fdcf50835b32" title="Handler called at the end of DFS.">dfs::end_handler</a></li><li><a class="el" href="a00008.html#73dabe5882226b53494a487b7c34f1d1" title="Handler called when touching node n.">dfs::entry_handler</a></li><li><a class="el" href="a00008.html#8071fc4e82deff7ceb2790cd4eb42280" title="Handler called after all the adjacent edges of n have been examined.">dfs::leave_handler</a></li><li><a class="el" href="a00008.html#e3f095c9fe6106e82c24543da4844ea3" title="Handler called when a unused node n connected to the actual node by e is found.">dfs::before_recursive_call_handler</a></li><li><a class="el" href="a00008.html#25ae75fe08f1d8c0fedcf9dcae09d092" title="Handler called after the algorithm returns from the subtree starting at n connected...">dfs::after_recursive_call_handler</a></li><li><a class="el" href="a00008.html#df1c667188e632761c63f529537c544c" title="Handler called when a already marked node n connected to the actual node by e is...">dfs::old_adj_node_handler</a></li><li><a class="el" href="a00008.html#3b5fbea7a7baed9946cfb4444a7f20ea" title="Called when DFS is started with start-node n.">dfs::new_start_handler</a></li></ul>
<p>
<em>Please</em> <em>note:</em> We do <em>not</em> claim that this set of handlers is sufficient in any way. So if you believe that some new handler is needed urgently please let us know.<p>
There is a lot of information stored during DFS (e.g. nodes in dfs-order, list of non-tree-edges). Some of it can be obtained directly by using the corresponding member-function (e.g. <a class="el" href="a00008.html#9309a0573f52643196bef32251cf96df" title="DFS-Number of n.">dfs::dfs_num</a>), but all information that can be thought of as a list (e.g. nodes in dfs-order) can be accessed through iterators. In detail these are (of course depending on what options are chosen!):<ul>
<li><a class="el" href="a00008.html#d040ddae37492e18c8e029406d667bd9" title="Iterator for the (reached) nodes in DFS-order.">dfs::dfs_iterator</a></li><li><a class="el" href="a00008.html#0eee0ddec5343c05f617d6d7aabb6d19" title="Iterator for the tree edges of the DFS-tree.">dfs::tree_edges_iterator</a></li><li><a class="el" href="a00008.html#e7301f3d4417e60fb3a499180375194e" title="Iterator for the non-tree-edges.">dfs::non_tree_edges_iterator</a></li><li><a class="el" href="a00008.html#17cb59c8a1fead11fa6b0c85cf5a478e" title="Iterator for the roots of the DFS-forest.">dfs::roots_iterator</a> </li></ul>
<hr><h2>Member Function Documentation</h2>
<a class="anchor" name="f0863b8974d5fd58cd0375c78ed8163b"></a><!-- doxytag: member="dfs::run" ref="f0863b8974d5fd58cd0375c78ed8163b" args="(graph &amp;G)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">int dfs::run           </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="a00014.html">graph</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>g</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [virtual]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Applies algorithm to graph g. 
<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>g</em>&nbsp;</td><td>graph </td></tr>
  </table>
</dl>
<dl compact><dt><b>Return values:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em><a class="el" href="a00001.html#f1a0078e153aa99c24f9bdf0d97f67105114c20e4a96a76b5de9f28bf15e282b">algorithm::GTL_OK</a></em>&nbsp;</td><td>on success </td></tr>
    <tr><td valign="top"></td><td valign="top"><em><a class="el" href="a00001.html#f1a0078e153aa99c24f9bdf0d97f67106fcf574690bbd6cf710837a169510dd7">algorithm::GTL_ERROR</a></em>&nbsp;</td><td>otherwise </td></tr>
  </table>
</dl>

<p>Implements <a class="el" href="a00001.html#734b189509a8d6b56b65f8ff772d43ca">algorithm</a>.</p>

</div>
</div><p>
<a class="anchor" name="908f4ea617ed59767ed334b39a2771d0"></a><!-- doxytag: member="dfs::check" ref="908f4ea617ed59767ed334b39a2771d0" args="(graph &amp;G)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">virtual int dfs::check           </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="a00014.html">graph</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>G</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [virtual]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Checks whether the preconditions for DFS are satisfied. 
<p>
Currently there aren't any restricitions for the DFS algorithm.<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>G</em>&nbsp;</td><td><a class="el" href="a00014.html" title="A directed or undirected graph.">graph</a>. </td></tr>
  </table>
</dl>
<dl compact><dt><b>Return values:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em><a class="el" href="a00001.html#f1a0078e153aa99c24f9bdf0d97f67105114c20e4a96a76b5de9f28bf15e282b">algorithm::GTL_OK</a></em>&nbsp;</td><td>if algorithm can be applied </td></tr>
    <tr><td valign="top"></td><td valign="top"><em><a class="el" href="a00001.html#f1a0078e153aa99c24f9bdf0d97f67106fcf574690bbd6cf710837a169510dd7">algorithm::GTL_ERROR</a></em>&nbsp;</td><td>otherwise. </td></tr>
  </table>
</dl>

<p>Implements <a class="el" href="a00001.html#76361fb03ad1cf643affc51821e43bed">algorithm</a>.</p>

<p>Reimplemented in <a class="el" href="a00004.html#5db0b38d8d01af52720d6941103de4f2">biconnectivity</a>, <a class="el" href="a00007.html#060c996e815c56cbab61f36d57fc3545">components</a>, and <a class="el" href="a00028.html#d83c28909478d35c737a2c70506407dd">topsort</a>.</p>

</div>
</div><p>
<a class="anchor" name="1c893f699517cc72624cf171b7bc4da4"></a><!-- doxytag: member="dfs::reset" ref="1c893f699517cc72624cf171b7bc4da4" args="()" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">virtual void dfs::reset           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [virtual]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Resets algorithm. 
<p>
Prepares the algorithm to be applied to another graph. <em>Please</em> <em>note:</em> The options an algorithm may support do <em>not</em> get reset by this. It is just to reset internally used datastructures. 
<p>Implements <a class="el" href="a00001.html#21aba63d066ae7897de6ca7d8425c408">algorithm</a>.</p>

<p>Reimplemented in <a class="el" href="a00004.html#a1a4b091fd8b2bbea2b36b91bab713af">biconnectivity</a>, <a class="el" href="a00007.html#1c1fb446e7a6bb18fbc8d2cbc82d90be">components</a>, and <a class="el" href="a00028.html#403076f952ef640cb3f52c9b1a495a1f">topsort</a>.</p>

</div>
</div><p>
<a class="anchor" name="ad21fd0d3036350fd341f877d5747852"></a><!-- doxytag: member="dfs::start_node" ref="ad21fd0d3036350fd341f877d5747852" args="(const node &amp;n)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">void dfs::start_node           </td>
          <td>(</td>
          <td class="paramtype">const <a class="el" href="a00020.html">node</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>n</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Sets start-node for DFS. 
<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>n</em>&nbsp;</td><td>start-node. </td></tr>
  </table>
</dl>

</div>
</div><p>
<a class="anchor" name="0282acea81eb9c0d02ceea109fc25f10"></a><!-- doxytag: member="dfs::start_node" ref="0282acea81eb9c0d02ceea109fc25f10" args="() const " -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="a00020.html">node</a> dfs::start_node           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const<code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Returns start-node for DFS. 
<p>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>start-node. </dd></dl>

</div>
</div><p>
<a class="anchor" name="a7c864a6f3a120720138b187b3ed95b5"></a><!-- doxytag: member="dfs::scan_whole_graph" ref="a7c864a6f3a120720138b187b3ed95b5" args="(bool set)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">void dfs::scan_whole_graph           </td>
          <td>(</td>
          <td class="paramtype">bool&nbsp;</td>
          <td class="paramname"> <em>set</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Enables or disables scanning of the whole graph. 
<p>
If enabled and the DFS started at the given start-node stops without having touched all nodes, it will be continued with the next unused node, and so on until all nodes were used. This makes sure that for every node dfs_number is defined.<p>
On the other hand, if this feature is disabled, one will be able to check what nodes can be reached, when starting a DFS at the start-node, because for those not reached dfs_number will be 0.<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>set</em>&nbsp;</td><td>if true enable scanning the whole <a class="el" href="a00014.html" title="A directed or undirected graph.">graph</a>. </td></tr>
  </table>
</dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00008.html#a084e2afe7b58c7bd94e4a8cf8c630af" title="Iterator pointing towards the first root in the DFS-forest.">dfs::roots_begin</a> <p>
<a class="el" href="a00008.html#c074438451c387aaf0cf6aaac79bcd16" title="Iterator pointing to the end of all roots.">dfs::roots_end</a> </dd></dl>

</div>
</div><p>
<a class="anchor" name="121e68fa166dc109b9f59f5bad3b0a8f"></a><!-- doxytag: member="dfs::scan_whole_graph" ref="121e68fa166dc109b9f59f5bad3b0a8f" args="() const " -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">bool dfs::scan_whole_graph           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const<code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Returns true iff the whole <a class="el" href="a00014.html" title="A directed or undirected graph.">graph</a> will be scanned. 
<p>
<dl compact><dt><b>Return values:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>true</em>&nbsp;</td><td>iff the whole <a class="el" href="a00014.html" title="A directed or undirected graph.">graph</a> will be scanned. </td></tr>
  </table>
</dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00008.html#a084e2afe7b58c7bd94e4a8cf8c630af" title="Iterator pointing towards the first root in the DFS-forest.">dfs::roots_begin</a> <p>
<a class="el" href="a00008.html#c074438451c387aaf0cf6aaac79bcd16" title="Iterator pointing to the end of all roots.">dfs::roots_end</a> </dd></dl>

</div>
</div><p>
<a class="anchor" name="70862ea715c52eb95fb704afd3a6e676"></a><!-- doxytag: member="dfs::calc_comp_num" ref="70862ea715c52eb95fb704afd3a6e676" args="(bool set)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">void dfs::calc_comp_num           </td>
          <td>(</td>
          <td class="paramtype">bool&nbsp;</td>
          <td class="paramname"> <em>set</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Enables or Disables the calculation of the completion number. 
<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>set</em>&nbsp;</td><td>if true completion-numbers will be calculated. </td></tr>
  </table>
</dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00008.html#1b1c940ed5df7e7b8f825ede1d37f364" title="Completion-number of node n, if enabled in last run.">dfs::comp_num</a> </dd></dl>

</div>
</div><p>
<a class="anchor" name="ba070824c0cd45651083a9c62ac34c1a"></a><!-- doxytag: member="dfs::calc_comp_num" ref="ba070824c0cd45651083a9c62ac34c1a" args="() const " -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">bool dfs::calc_comp_num           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const<code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Returns true iff completion-numbers will be calculated. 
<p>
<dl compact><dt><b>Return values:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>true</em>&nbsp;</td><td>iff completion-numbers will be calculated. </td></tr>
  </table>
</dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00008.html#1b1c940ed5df7e7b8f825ede1d37f364" title="Completion-number of node n, if enabled in last run.">dfs::comp_num</a> </dd></dl>

</div>
</div><p>
<a class="anchor" name="7043f46eb3887cbcbb1391fc783407a4"></a><!-- doxytag: member="dfs::store_preds" ref="7043f46eb3887cbcbb1391fc783407a4" args="(bool set)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">void dfs::store_preds           </td>
          <td>(</td>
          <td class="paramtype">bool&nbsp;</td>
          <td class="paramname"> <em>set</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Enables or disables the storing of predecessors. 
<p>
If enabled for every node the predecessor in DFS will be stored.<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>set</em>&nbsp;</td><td>if true predecessors will be stored. </td></tr>
  </table>
</dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00008.html#7c4dc665c18e987c1eb61b69cb582d4f" title="Returns father of node n in DFS-forest.">dfs::father</a> </dd></dl>

</div>
</div><p>
<a class="anchor" name="5fdfdf59dbd7616167b47013df79364b"></a><!-- doxytag: member="dfs::store_preds" ref="5fdfdf59dbd7616167b47013df79364b" args="() const " -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">bool dfs::store_preds           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const<code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Returns true iff the storing of predecessors is enabled. 
<p>
<dl compact><dt><b>Return values:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>true</em>&nbsp;</td><td>iff the storing of predecessors is enabled. </td></tr>
  </table>
</dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00008.html#7c4dc665c18e987c1eb61b69cb582d4f" title="Returns father of node n in DFS-forest.">dfs::father</a> </dd></dl>

</div>
</div><p>
<a class="anchor" name="6f54f1c4339eacc8961e795439d4593d"></a><!-- doxytag: member="dfs::store_non_tree_edges" ref="6f54f1c4339eacc8961e795439d4593d" args="(bool set)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">void dfs::store_non_tree_edges           </td>
          <td>(</td>
          <td class="paramtype">bool&nbsp;</td>
          <td class="paramname"> <em>set</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Enables the storing of back-edges. 
<p>
If enabled the list of non-tree-edges can be traversed in the order they occured using <a class="el" href="a00008.html#e7301f3d4417e60fb3a499180375194e" title="Iterator for the non-tree-edges.">non_tree_edges_iterator</a>.<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>set</em>&nbsp;</td><td>if true non_tree_edges will be stored. </td></tr>
  </table>
</dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00008.html#1f92658af729dff37e76ad3025b98a79" title="Iterate through all non-tree-edges (if enabled).">dfs::non_tree_edges_begin</a> <p>
<a class="el" href="a00008.html#f6c9d194226a73515cab7805d1d2a9cf" title="End-iterator for iteration through all non-tree-edges (if enabled).">dfs::non_tree_edges_end</a> </dd></dl>

</div>
</div><p>
<a class="anchor" name="c81e86d2e2b8f4ef5e34470486717dcf"></a><!-- doxytag: member="dfs::store_non_tree_edges" ref="c81e86d2e2b8f4ef5e34470486717dcf" args="() const " -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">bool dfs::store_non_tree_edges           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const<code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Returns true iff the storing of non-tree-edges is enabled. 
<p>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>true iff the storing of non-tree-edges is enabled. </dd></dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00008.html#1f92658af729dff37e76ad3025b98a79" title="Iterate through all non-tree-edges (if enabled).">dfs::non_tree_edges_begin</a> <p>
<a class="el" href="a00008.html#f6c9d194226a73515cab7805d1d2a9cf" title="End-iterator for iteration through all non-tree-edges (if enabled).">dfs::non_tree_edges_end</a> </dd></dl>

</div>
</div><p>
<a class="anchor" name="174338f8e57a5ba93c08469c2a531a8b"></a><!-- doxytag: member="dfs::reached" ref="174338f8e57a5ba93c08469c2a531a8b" args="(const node &amp;n) const " -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">bool dfs::reached           </td>
          <td>(</td>
          <td class="paramtype">const <a class="el" href="a00020.html">node</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>n</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const<code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Checks whether node <em>n</em> was reached in last DFS. 
<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>n</em>&nbsp;</td><td>node to be checked. </td></tr>
  </table>
</dl>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>true iff <em>n</em> was reached. </dd></dl>

</div>
</div><p>
<a class="anchor" name="9309a0573f52643196bef32251cf96df"></a><!-- doxytag: member="dfs::dfs_num" ref="9309a0573f52643196bef32251cf96df" args="(const node &amp;n) const " -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">int dfs::dfs_num           </td>
          <td>(</td>
          <td class="paramtype">const <a class="el" href="a00020.html">node</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>n</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const<code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
DFS-Number of <em>n</em>. 
<p>
Please note that DFS-Number 0 means that this node wasn't reached.<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>n</em>&nbsp;</td><td>node. </td></tr>
  </table>
</dl>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>DFS-Number of <em>n</em>. </dd></dl>

</div>
</div><p>
<a class="anchor" name="5aa6d81775ad13d92c6e5a7661041866"></a><!-- doxytag: member="dfs::operator[]" ref="5aa6d81775ad13d92c6e5a7661041866" args="(const node &amp;n) const " -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">int dfs::operator[]           </td>
          <td>(</td>
          <td class="paramtype">const <a class="el" href="a00020.html">node</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>n</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const<code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
DFS-Number of <em>n</em>. 
<p>
Please note that DFS-Number 0 means that this node wasn't reached.<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>n</em>&nbsp;</td><td>node. </td></tr>
  </table>
</dl>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>DFS-Number of <em>n</em>. </dd></dl>

</div>
</div><p>
<a class="anchor" name="1b1c940ed5df7e7b8f825ede1d37f364"></a><!-- doxytag: member="dfs::comp_num" ref="1b1c940ed5df7e7b8f825ede1d37f364" args="(const node &amp;n) const " -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">int dfs::comp_num           </td>
          <td>(</td>
          <td class="paramtype">const <a class="el" href="a00020.html">node</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>n</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const<code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Completion-number of node <em>n</em>, if enabled in last run. 
<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>n</em>&nbsp;</td><td>node. </td></tr>
  </table>
</dl>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>Completion-number of <em>n</em>. </dd></dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00008.html#70862ea715c52eb95fb704afd3a6e676" title="Enables or Disables the calculation of the completion number.">dfs::calc_comp_num</a> </dd></dl>

</div>
</div><p>
<a class="anchor" name="7c4dc665c18e987c1eb61b69cb582d4f"></a><!-- doxytag: member="dfs::father" ref="7c4dc665c18e987c1eb61b69cb582d4f" args="(const node &amp;n) const " -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="a00020.html">node</a> dfs::father           </td>
          <td>(</td>
          <td class="paramtype">const <a class="el" href="a00020.html">node</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>n</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const<code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Returns father of <a class="el" href="a00020.html" title="A node in a graph.">node</a> <em>n</em> in DFS-forest. 
<p>
If <em>n</em> is a root in the forest or wasn't reached the return value is <code>node()</code>.<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>n</em>&nbsp;</td><td>node. </td></tr>
  </table>
</dl>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>Father of <em>n</em>. </dd></dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00008.html#7043f46eb3887cbcbb1391fc783407a4" title="Enables or disables the storing of predecessors.">dfs::store_preds</a> </dd></dl>

</div>
</div><p>
<a class="anchor" name="7c13e57ce4138032322bc2230a260b9a"></a><!-- doxytag: member="dfs::tree_edges_begin" ref="7c13e57ce4138032322bc2230a260b9a" args="() const " -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="a00008.html#0eee0ddec5343c05f617d6d7aabb6d19">tree_edges_iterator</a> dfs::tree_edges_begin           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const<code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Iterate through all edges picked in last DFS. 
<p>
Please note that this edges not always form a tree. In case the graph is not (strongly) connected they form a forest.<p>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>start for iteration through all edges followed in DFS. </dd></dl>

</div>
</div><p>
<a class="anchor" name="3b2de20ab3cff57507f2db17982a6725"></a><!-- doxytag: member="dfs::tree_edges_end" ref="3b2de20ab3cff57507f2db17982a6725" args="() const " -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="a00008.html#0eee0ddec5343c05f617d6d7aabb6d19">tree_edges_iterator</a> dfs::tree_edges_end           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const<code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
End-iterator for iteration through all edges picked in last DFS. 
<p>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>end for iteration through all edges followed in DFS. </dd></dl>

</div>
</div><p>
<a class="anchor" name="d77350c772b18d305e92d44afe784282"></a><!-- doxytag: member="dfs::begin" ref="d77350c772b18d305e92d44afe784282" args="() const " -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="a00008.html#d040ddae37492e18c8e029406d667bd9">dfs_iterator</a> dfs::begin           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const<code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Iterate through all (reached) nodes in DFS-order. 
<p>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>start for iteration through all nodes in DFS-order. </dd></dl>

</div>
</div><p>
<a class="anchor" name="08e6a3b0c1f7c9f7d725b586d5c00857"></a><!-- doxytag: member="dfs::end" ref="08e6a3b0c1f7c9f7d725b586d5c00857" args="() const " -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="a00008.html#d040ddae37492e18c8e029406d667bd9">dfs_iterator</a> dfs::end           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const<code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
End-Iterator for iteration through all (reached) nodes in DFS-order. 
<p>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>end for iteration through all (reached) nodes </dd></dl>

</div>
</div><p>
<a class="anchor" name="1f92658af729dff37e76ad3025b98a79"></a><!-- doxytag: member="dfs::non_tree_edges_begin" ref="1f92658af729dff37e76ad3025b98a79" args="() const " -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="a00008.html#e7301f3d4417e60fb3a499180375194e">non_tree_edges_iterator</a> dfs::non_tree_edges_begin           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const<code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Iterate through all non-tree-edges (if enabled). 
<p>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>start for iteration through all non-tree-edges. </dd></dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00008.html#6f54f1c4339eacc8961e795439d4593d" title="Enables the storing of back-edges.">dfs::store_non_tree_edges</a> </dd></dl>

</div>
</div><p>
<a class="anchor" name="f6c9d194226a73515cab7805d1d2a9cf"></a><!-- doxytag: member="dfs::non_tree_edges_end" ref="f6c9d194226a73515cab7805d1d2a9cf" args="() const " -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="a00008.html#e7301f3d4417e60fb3a499180375194e">non_tree_edges_iterator</a> dfs::non_tree_edges_end           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const<code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
End-iterator for iteration through all non-tree-edges (if enabled). 
<p>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>end for iteration through all non-tree-edges. </dd></dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00008.html#6f54f1c4339eacc8961e795439d4593d" title="Enables the storing of back-edges.">dfs::store_non_tree_edges</a> </dd></dl>

</div>
</div><p>
<a class="anchor" name="a084e2afe7b58c7bd94e4a8cf8c630af"></a><!-- doxytag: member="dfs::roots_begin" ref="a084e2afe7b58c7bd94e4a8cf8c630af" args="() const " -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="a00008.html#17cb59c8a1fead11fa6b0c85cf5a478e">roots_iterator</a> dfs::roots_begin           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const<code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Iterator pointing towards the first root in the DFS-forest. 
<p>
<em>Please note</em> that intstead of pointing directly towards the <a class="el" href="a00020.html" title="A node in a graph.">node</a> (i.e. <code>*it</code> is of type <a class="el" href="a00020.html" title="A node in a graph.">node</a>) the iterator points towards a <a class="el" href="a00008.html#d040ddae37492e18c8e029406d667bd9" title="Iterator for the (reached) nodes in DFS-order.">dfs_iterator</a>, which represents the root (i.e. <code>*it</code> is of type <a class="el" href="a00008.html#d040ddae37492e18c8e029406d667bd9" title="Iterator for the (reached) nodes in DFS-order.">dfs_iterator</a>).<p>
Using this technique makes it possible not only to obtain all the roots in the forest, but also the whole trees associated with each one. This can be achieved because a root_iterator specifies the exact position of the root in the DFS-ordering and by definition of DFS all the descendents of the root, i.e. the whole tree, will come later in DFS, such that by incrementing the <a class="el" href="a00008.html#d040ddae37492e18c8e029406d667bd9" title="Iterator for the (reached) nodes in DFS-order.">dfs_iterator</a>, a <a class="el" href="a00008.html#17cb59c8a1fead11fa6b0c85cf5a478e" title="Iterator for the roots of the DFS-forest.">roots_iterator</a> points at, one can traverse the whole tree with this given root.<p>
Of course if the root isn't the last <a class="el" href="a00020.html" title="A node in a graph.">node</a> in the DFS-forest on will also traverse all following trees, but since the first <a class="el" href="a00020.html" title="A node in a graph.">node</a> of such a tree one will discover is its root, the successor of the <a class="el" href="a00008.html#17cb59c8a1fead11fa6b0c85cf5a478e" title="Iterator for the roots of the DFS-forest.">roots_iterator</a> can be used as end-iterator.<p>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>start for iteration through all roots in DFS-forest. </dd></dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00008.html#a7c864a6f3a120720138b187b3ed95b5" title="Enables or disables scanning of the whole graph.">dfs::scan_whole_graph</a> </dd></dl>

</div>
</div><p>
<a class="anchor" name="c074438451c387aaf0cf6aaac79bcd16"></a><!-- doxytag: member="dfs::roots_end" ref="c074438451c387aaf0cf6aaac79bcd16" args="() const " -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="a00008.html#17cb59c8a1fead11fa6b0c85cf5a478e">roots_iterator</a> dfs::roots_end           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const<code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Iterator pointing to the end of all roots. 
<p>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>end for iteration through all roots in DFS-forest. </dd></dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00008.html#a7c864a6f3a120720138b187b3ed95b5" title="Enables or disables scanning of the whole graph.">dfs::scan_whole_graph</a> </dd></dl>

</div>
</div><p>
<a class="anchor" name="5bffe465fdd599a63a2c3d4593f21187"></a><!-- doxytag: member="dfs::number_of_reached_nodes" ref="5bffe465fdd599a63a2c3d4593f21187" args="() const " -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">int dfs::number_of_reached_nodes           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const<code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Number of nodes reached in last DFS. 
<p>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>number of reached nodes. </dd></dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00008.html#a7c864a6f3a120720138b187b3ed95b5" title="Enables or disables scanning of the whole graph.">dfs::scan_whole_graph</a> </dd></dl>

</div>
</div><p>
<a class="anchor" name="cc82574cd42ab8256e685374bee5fabb"></a><!-- doxytag: member="dfs::init_handler" ref="cc82574cd42ab8256e685374bee5fabb" args="(graph &amp;G)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">virtual void dfs::init_handler           </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="a00014.html">graph</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>G</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [inline, virtual]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Handler called before the start of DFS. 
<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>G</em>&nbsp;</td><td>graph for which DFS was invoked. </td></tr>
  </table>
</dl>

<p>Reimplemented in <a class="el" href="a00004.html#c13bfac43192225a9161b0bf0827f600">biconnectivity</a>, and <a class="el" href="a00028.html#1cd92994d564acf79c37e40bdb292827">topsort</a>.</p>

</div>
</div><p>
<a class="anchor" name="b96c7c6183856dd9e356fdcf50835b32"></a><!-- doxytag: member="dfs::end_handler" ref="b96c7c6183856dd9e356fdcf50835b32" args="(graph &amp;G)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">virtual void dfs::end_handler           </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="a00014.html">graph</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>G</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [inline, virtual]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Handler called at the end of DFS. 
<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>G</em>&nbsp;</td><td>graph for which DFS was invoked. </td></tr>
  </table>
</dl>

<p>Reimplemented in <a class="el" href="a00004.html#eade3bbc61d1046ba80ec88988f72c44">biconnectivity</a>.</p>

</div>
</div><p>
<a class="anchor" name="73dabe5882226b53494a487b7c34f1d1"></a><!-- doxytag: member="dfs::entry_handler" ref="73dabe5882226b53494a487b7c34f1d1" args="(graph &amp;G, node &amp;n, node &amp;f)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">virtual void dfs::entry_handler           </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="a00014.html">graph</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>G</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="a00020.html">node</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>n</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="a00020.html">node</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>f</em></td><td>&nbsp;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td><td width="100%"><code> [inline, virtual]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Handler called when touching node <em>n</em>. 
<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>G</em>&nbsp;</td><td>graph for which DFS was invoked. </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>n</em>&nbsp;</td><td>actual node. </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>f</em>&nbsp;</td><td>predecessor. </td></tr>
  </table>
</dl>

<p>Reimplemented in <a class="el" href="a00004.html#caf5548cba90ee5b6ae3a542ac13e767">biconnectivity</a>.</p>

</div>
</div><p>
<a class="anchor" name="8071fc4e82deff7ceb2790cd4eb42280"></a><!-- doxytag: member="dfs::leave_handler" ref="8071fc4e82deff7ceb2790cd4eb42280" args="(graph &amp;G, node &amp;n, node &amp;f)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">virtual void dfs::leave_handler           </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="a00014.html">graph</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>G</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="a00020.html">node</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>n</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="a00020.html">node</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>f</em></td><td>&nbsp;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td><td width="100%"><code> [inline, virtual]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Handler called after all the adjacent edges of <em>n</em> have been examined. 
<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>G</em>&nbsp;</td><td>graph for which DFS was invoked. </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>n</em>&nbsp;</td><td>actual node. </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>f</em>&nbsp;</td><td>predecessor. </td></tr>
  </table>
</dl>

<p>Reimplemented in <a class="el" href="a00004.html#cbb12e89c368f4346f36d09888d8bfb0">biconnectivity</a>, and <a class="el" href="a00028.html#4401a056e4310ca7eca47587f7da5daf">topsort</a>.</p>

</div>
</div><p>
<a class="anchor" name="e3f095c9fe6106e82c24543da4844ea3"></a><!-- doxytag: member="dfs::before_recursive_call_handler" ref="e3f095c9fe6106e82c24543da4844ea3" args="(graph &amp;G, edge &amp;e, node &amp;n)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">virtual void dfs::before_recursive_call_handler           </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="a00014.html">graph</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>G</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="a00010.html">edge</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>e</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="a00020.html">node</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>n</em></td><td>&nbsp;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td><td width="100%"><code> [inline, virtual]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Handler called when a unused node <em>n</em> connected to the actual node by <em>e</em> is found. 
<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>G</em>&nbsp;</td><td>graph for which DFS was invoked. </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>e</em>&nbsp;</td><td>edge connecting the actual node to the unused one. </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>n</em>&nbsp;</td><td>unused node. </td></tr>
  </table>
</dl>

<p>Reimplemented in <a class="el" href="a00004.html#cf4ca6d67f23498c43cfc3669c80417c">biconnectivity</a>, and <a class="el" href="a00007.html#a443188e949f25a82ad0c15ff5a5378e">components</a>.</p>

</div>
</div><p>
<a class="anchor" name="25ae75fe08f1d8c0fedcf9dcae09d092"></a><!-- doxytag: member="dfs::after_recursive_call_handler" ref="25ae75fe08f1d8c0fedcf9dcae09d092" args="(graph &amp;G, edge &amp;e, node &amp;n)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">virtual void dfs::after_recursive_call_handler           </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="a00014.html">graph</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>G</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="a00010.html">edge</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>e</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="a00020.html">node</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>n</em></td><td>&nbsp;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td><td width="100%"><code> [inline, virtual]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Handler called after the algorithm returns from the subtree starting at <em>n</em> connected to the actual node by <em>e</em>. 
<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>G</em>&nbsp;</td><td>graph for which DFS was invoked. </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>e</em>&nbsp;</td><td>edge connecting the actual node to the unused one. </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>n</em>&nbsp;</td><td>unused node. </td></tr>
  </table>
</dl>

<p>Reimplemented in <a class="el" href="a00004.html#9a2e5d5f934d5ff1d93c545414a7dab5">biconnectivity</a>.</p>

</div>
</div><p>
<a class="anchor" name="df1c667188e632761c63f529537c544c"></a><!-- doxytag: member="dfs::old_adj_node_handler" ref="df1c667188e632761c63f529537c544c" args="(graph &amp;G, edge &amp;e, node &amp;n)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">virtual void dfs::old_adj_node_handler           </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="a00014.html">graph</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>G</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="a00010.html">edge</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>e</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="a00020.html">node</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>n</em></td><td>&nbsp;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td><td width="100%"><code> [inline, virtual]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Handler called when a already marked node <em>n</em> connected to the actual node by <em>e</em> is found during the search of all adjacent edges of the actual node. 
<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>G</em>&nbsp;</td><td>graph for which DFS was invoked. </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>e</em>&nbsp;</td><td>edge connecting the actual node to the old one. </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>n</em>&nbsp;</td><td>used node. </td></tr>
  </table>
</dl>

<p>Reimplemented in <a class="el" href="a00004.html#54c5d1deed1c326f5934f4181770612b">biconnectivity</a>, <a class="el" href="a00007.html#4894a383b2c86bcdff340c6c3474ec2e">components</a>, and <a class="el" href="a00028.html#97074494bbdb878a1e3b6da232e965dd">topsort</a>.</p>

</div>
</div><p>
<a class="anchor" name="3b5fbea7a7baed9946cfb4444a7f20ea"></a><!-- doxytag: member="dfs::new_start_handler" ref="3b5fbea7a7baed9946cfb4444a7f20ea" args="(graph &amp;G, node &amp;n)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">virtual void dfs::new_start_handler           </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="a00014.html">graph</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>G</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="a00020.html">node</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>n</em></td><td>&nbsp;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td><td width="100%"><code> [inline, virtual]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Called when DFS is started with start-node <em>n</em>. 
<p>
This is particularly useful when DFS was invoked with the <a class="el" href="a00008.html#a7c864a6f3a120720138b187b3ed95b5" title="Enables or disables scanning of the whole graph.">scan_whole_graph</a> option.<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>G</em>&nbsp;</td><td>graph for which DFS was invoked. </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>n</em>&nbsp;</td><td>start-node. </td></tr>
  </table>
</dl>

<p>Reimplemented in <a class="el" href="a00004.html#e67b0c7d2677f0f60d46995ff244a6d0">biconnectivity</a>, and <a class="el" href="a00007.html#8c455b66ec09be3fb7b04045a8f999cf">components</a>.</p>

</div>
</div><p>
    <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>