mooigraph
/
regraphlet


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101
							<!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: min_tree.h Source File</title>
      <link href="doxygen.css" rel="stylesheet" type="text/css">
  </head>
  <body>
    <p class="links">  
      <a href="../index.html">Home</a> |
      Documentation |
      <a href="../register.html">Download</a> |
      <a href="../platforms.html">Platforms</a> |
      <a href="../refer.html">Projects</a> |      
      <a href="../lists.html">Mailing Lists</a> |
      <a href="../history.html">Version History</a>
    </p>

<!-- Generated by Doxygen 1.5.3 -->
<div class="tabs">
  <ul>
    <li><a href="index.html"><span>Main&nbsp;Page</span></a></li>
    <li><a href="classes.html"><span>Classes</span></a></li>
    <li class="current"><a href="files.html"><span>Files</span></a></li>
    <li><a href="pages.html"><span>Related&nbsp;Pages</span></a></li>
  </ul>
</div>
<h1>min_tree.h</h1><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">//==========================================================================</span>
<a name="l00002"></a>00002 <span class="comment">//</span>
<a name="l00003"></a>00003 <span class="comment">//   min_tree.cpp</span>
<a name="l00004"></a>00004 <span class="comment">//</span>
<a name="l00005"></a>00005 <span class="comment">//==========================================================================</span>
<a name="l00006"></a>00006 <span class="comment">// $Id: min_tree.h,v 1.3 2001/06/21 10:55:08 chris Exp $</span>
<a name="l00007"></a>00007 
<a name="l00008"></a>00008 <span class="preprocessor">#ifndef GTL_MIN_TREE_H</span>
<a name="l00009"></a>00009 <span class="preprocessor"></span><span class="preprocessor">#define GTL_MIN_TREE_H</span>
<a name="l00010"></a>00010 <span class="preprocessor"></span>
<a name="l00011"></a>00011 <span class="preprocessor">#include &lt;GTL/GTL.h&gt;</span>
<a name="l00012"></a>00012 <span class="preprocessor">#include &lt;GTL/algorithm.h&gt;</span>
<a name="l00013"></a>00013 <span class="preprocessor">#include &lt;GTL/edge_map.h&gt;</span>
<a name="l00014"></a>00014 <span class="preprocessor">#include &lt;set&gt;</span>
<a name="l00015"></a>00015 
<a name="l00016"></a>00016 __GTL_BEGIN_NAMESPACE
<a name="l00017"></a>00017 
<a name="l00024"></a><a class="code" href="a00018.html">00024</a> <span class="keyword">class </span><a class="code" href="a00018.html" title="Kruskal&amp;#39;s algorithm for finding minimal spanning tree of a graph.">min_tree</a>: <span class="keyword">public</span> <a class="code" href="a00001.html" title="Abstract baseclass for all algoritm-classes.">algorithm</a> { 
<a name="l00025"></a>00025 
<a name="l00026"></a>00026 <span class="keyword">public</span>:
<a name="l00027"></a>00027 
<a name="l00031"></a>00031     <a class="code" href="a00018.html#d5c01151dac766b65b485b73da5f1543" title="Constructor.">min_tree</a> ();
<a name="l00032"></a>00032 
<a name="l00036"></a><a class="code" href="a00018.html#0df992f77a8656121777aa2c0380a67a">00036</a>     <span class="keyword">virtual</span> <a class="code" href="a00018.html#0df992f77a8656121777aa2c0380a67a" title="Destructor.">~min_tree</a> () {};
<a name="l00037"></a>00037 
<a name="l00053"></a>00053     <span class="keywordtype">int</span> <a class="code" href="a00018.html#d87b1bfbc687ad943c07538fa0c3d270" title="Checks whether algorithm can be applied.">check</a> (<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; g);
<a name="l00054"></a>00054 
<a name="l00055"></a>00055     <span class="keywordtype">int</span> <a class="code" href="a00018.html#c025e8dad0db7a6a1e0e7b476b547802" title="Applies algorithm to graph g.">run</a> (<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; g);
<a name="l00056"></a>00056     
<a name="l00057"></a>00057     <span class="keyword">virtual</span> <span class="keywordtype">void</span> <a class="code" href="a00018.html#3c4b17c455dd77b4120ec5564a4ac428" title="Resets algorithm.">reset</a> ();
<a name="l00058"></a>00058 
<a name="l00067"></a>00067     <span class="keywordtype">void</span> <a class="code" href="a00018.html#0f3eb1714b7859576037cf4b991b16cb" title="Sets edge weights.">set_distances</a> (<span class="keyword">const</span> <a class="code" href="a00011.html" title="A specialized map with edges as keys.">edge_map&lt;int&gt;</a>&amp; dist);
<a name="l00068"></a>00068 
<a name="l00076"></a>00076     set&lt;edge&gt; <a class="code" href="a00018.html#59de5032f3ff973f97f29d43f70ea360" title="Edges of minimal spanning tree calculated in the last call of min_tree::run.">get_min_tree</a>();
<a name="l00077"></a>00077     
<a name="l00083"></a>00083     <span class="keywordtype">int</span> <a class="code" href="a00018.html#8ca03d32ba55a9eb20b52fcb0e6fa6a5" title="Weight of minimal spanning tree.">get_min_tree_length</a>();
<a name="l00084"></a>00084     
<a name="l00085"></a>00085 <span class="keyword">private</span>:
<a name="l00086"></a>00086     <span class="keyword">typedef</span> pair&lt;int, node::adj_edges_iterator&gt; TSP_A_VALUE;
<a name="l00087"></a>00087 
<a name="l00088"></a>00088     <span class="keyword">class </span>input_comp {
<a name="l00089"></a>00089     <span class="keyword">public</span>:
<a name="l00090"></a>00090         <span class="keywordtype">bool</span> operator()(TSP_A_VALUE x, TSP_A_VALUE y)
<a name="l00091"></a>00091             { <span class="keywordflow">return</span> x.first &gt; y.first;}
<a name="l00092"></a>00092     };
<a name="l00093"></a>00093 
<a name="l00094"></a>00094     <a class="code" href="a00011.html" title="A specialized map with edges as keys.">edge_map&lt;int&gt;</a> dist;
<a name="l00095"></a>00095     <span class="keywordtype">int</span> weight;
<a name="l00096"></a>00096     set&lt;edge&gt; tree;
<a name="l00097"></a>00097     <span class="keywordtype">bool</span> is_set_distances;
<a name="l00098"></a>00098 };
<a name="l00099"></a>00099 
<a name="l00100"></a>00100 __GTL_END_NAMESPACE
<a name="l00101"></a>00101 
<a name="l00102"></a>00102 <span class="preprocessor">#endif // GTL_MIN_TREE_H</span>
<a name="l00103"></a>00103 <span class="preprocessor"></span>
<a name="l00104"></a>00104 
<a name="l00105"></a>00105 
<a name="l00106"></a>00106 
<a name="l00107"></a>00107 
</pre></div>    <p class="links">
      <a href="http://www.uni-passau.de/">University of Passau</a>
      &nbsp;-&nbsp;
      <a href="http://www.fmi.uni-passau.de/">FMI</a>
      &nbsp;-&nbsp;
      <a href="http://www.fmi.uni-passau.de/fmi/lehrstuehle/brandenburg/">Theoretical
	Computer Science</a>
    </p>
  <div class="copyright">
      Design &copy; 2002, 2003 <a href="mailto:raitner@fmi.uni-passau.de">Marcus Raitner</a>,  University of Passau 
  </div>
</body>
</html>