<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=UTF-8">
<title>steghide: WKSConstructionHeuristic Class Reference</title>
<link href="tabs.css" rel="stylesheet" type="text/css">
<link href="doxygen.css" rel="stylesheet" type="text/css">
</head><body>
<!-- Generated by Doxygen 1.5.9 -->
<div class="navigation" id="top">
<div class="tabs">
<ul>
<li><a href="index.html"><span>Main Page</span></a></li>
<li class="current"><a href="annotated.html"><span>Classes</span></a></li>
<li><a href="files.html"><span>Files</span></a></li>
</ul>
</div>
<div class="tabs">
<ul>
<li><a href="annotated.html"><span>Class List</span></a></li>
<li><a href="hierarchy.html"><span>Class Hierarchy</span></a></li>
<li><a href="functions.html"><span>Class Members</span></a></li>
</ul>
</div>
</div>
<div class="contents">
<h1>WKSConstructionHeuristic Class Reference</h1><!-- doxytag: class="WKSConstructionHeuristic" --><!-- doxytag: inherits="MatchingAlgorithm" -->a heuristic algorithm for constructing a matching
<a href="#_details">More...</a>
<p>
<code>#include <<a class="el" href="WKSConstructionHeuristic_8h_source.html">WKSConstructionHeuristic.h</a>></code>
<p>
<div class="dynheader">
Inheritance diagram for WKSConstructionHeuristic:</div>
<div class="dynsection">
<p><center><img src="classWKSConstructionHeuristic.png" usemap="#WKSConstructionHeuristic_map" border="0" alt=""></center>
<map name="WKSConstructionHeuristic_map">
<area href="classMatchingAlgorithm.html" alt="MatchingAlgorithm" shape="rect" coords="0,0,160,24">
</map>
</div>
<p>
<a href="classWKSConstructionHeuristic-members.html">List of all members.</a><table border="0" cellpadding="0" cellspacing="0">
<tr><td></td></tr>
<tr><td colspan="2"><br><h2>Classes</h2></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">class </td><td class="memItemRight" valign="bottom"><a class="el" href="classWKSConstructionHeuristic_1_1LongerShortestEdge.html">LongerShortestEdge</a></td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">a comparison operator <a href="classWKSConstructionHeuristic_1_1LongerShortestEdge.html#_details">More...</a><br></td></tr>
<tr><td colspan="2"><br><h2>Public Member Functions</h2></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"> </td><td class="memItemRight" valign="bottom"><a class="el" href="classWKSConstructionHeuristic.html#fd24063c7439518b3d1381d11a8a760f">WKSConstructionHeuristic</a> (<a class="el" href="classGraph.html">Graph</a> *g, <a class="el" href="classMatching.html">Matching</a> *m, float goal=100.0)</td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">virtual </td><td class="memItemRight" valign="bottom"><a class="el" href="classWKSConstructionHeuristic.html#da1e6ce80969aa9c0be22d62e60f5909">~WKSConstructionHeuristic</a> (void)</td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">const char * </td><td class="memItemRight" valign="bottom"><a class="el" href="classWKSConstructionHeuristic.html#16ff5405de18effbf58bba0b89670a52">getName</a> (void) const </td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="classWKSConstructionHeuristic.html#04c931636b6e457493b6bc25697f98fb">run</a> (void)</td></tr>
<tr><td colspan="2"><br><h2>Private Member Functions</h2></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="classVertex.html">Vertex</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="classWKSConstructionHeuristic.html#b466858ce4ff82430552c7ef6db8a2eb">findVertexDeg1</a> (void)</td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="classVertex.html">Vertex</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="classWKSConstructionHeuristic.html#1c2233d1625f773b3fa32cb7278e9396">findVertexDegG</a> (void)</td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="classWKSConstructionHeuristic.html#87e4ebbe9b5c5622d4ba2d9eb740e184">checkNeighboursDeg1</a> (<a class="el" href="classVertex.html">Vertex</a> *v)</td></tr>
<tr><td colspan="2"><br><h2>Private Attributes</h2></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">std::priority_queue< <a class="el" href="classVertex.html">Vertex</a> <br class="typebreak">
*, std::vector< <a class="el" href="classVertex.html">Vertex</a> * ><br class="typebreak">
, <a class="el" href="classWKSConstructionHeuristic_1_1LongerShortestEdge.html">LongerShortestEdge</a> > </td><td class="memItemRight" valign="bottom"><a class="el" href="classWKSConstructionHeuristic.html#a10ccd5f02c16ed9207f10101dd50c43">VerticesDeg1</a></td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">contains all vertices of degree 1 - every vertex in this queue has a correct shortest edge if it still has degree 1 <a href="#a10ccd5f02c16ed9207f10101dd50c43"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">std::priority_queue< <a class="el" href="classVertex.html">Vertex</a> <br class="typebreak">
*, std::vector< <a class="el" href="classVertex.html">Vertex</a> * ><br class="typebreak">
, <a class="el" href="classWKSConstructionHeuristic_1_1LongerShortestEdge.html">LongerShortestEdge</a> > </td><td class="memItemRight" valign="bottom"><a class="el" href="classWKSConstructionHeuristic.html#cb53370d5b437466e6eaed1507dcf2f9">VerticesDegG</a></td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">contains all vertices with degree greater than 1 <a href="#cb53370d5b437466e6eaed1507dcf2f9"></a><br></td></tr>
</table>
<hr><a name="_details"></a><h2>Detailed Description</h2>
This class implements a construction heuristic for the maximum matching problem. The idea for the algorithm is taken from Michael Sipser, Richard M. Karp: "Maximum matchings in sparse random graphs", in 22nd Annual Symposium on Foundations of Computer Science. The modification consists of the priority queues, resp. of the fact that the vertices in the priority queues are ordered by the length of their shortest edge, thus creating a weighted version of this heuristic by biasing the algorithm to choose shorter edges on average. <hr><h2>Constructor & Destructor Documentation</h2>
<a class="anchor" name="fd24063c7439518b3d1381d11a8a760f"></a><!-- doxytag: member="WKSConstructionHeuristic::WKSConstructionHeuristic" ref="fd24063c7439518b3d1381d11a8a760f" args="(Graph *g, Matching *m, float goal=100.0)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">WKSConstructionHeuristic::WKSConstructionHeuristic </td>
<td>(</td>
<td class="paramtype"><a class="el" href="classGraph.html">Graph</a> * </td>
<td class="paramname"> <em>g</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="classMatching.html">Matching</a> * </td>
<td class="paramname"> <em>m</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">float </td>
<td class="paramname"> <em>goal</em> = <code>100.0</code></td><td> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td><td></td>
</tr>
</table>
</div>
<div class="memdoc">
<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> </td><td>the underlying graph </td></tr>
<tr><td valign="top"></td><td valign="top"><em>m</em> </td><td>the inital matching (should be empty) </td></tr>
</table>
</dl>
</div>
</div><p>
<a class="anchor" name="da1e6ce80969aa9c0be22d62e60f5909"></a><!-- doxytag: member="WKSConstructionHeuristic::~WKSConstructionHeuristic" ref="da1e6ce80969aa9c0be22d62e60f5909" args="(void)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">virtual WKSConstructionHeuristic::~WKSConstructionHeuristic </td>
<td>(</td>
<td class="paramtype">void </td>
<td class="paramname"> </td>
<td> ) </td>
<td><code> [inline, virtual]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
</div>
</div><p>
<hr><h2>Member Function Documentation</h2>
<a class="anchor" name="87e4ebbe9b5c5622d4ba2d9eb740e184"></a><!-- doxytag: member="WKSConstructionHeuristic::checkNeighboursDeg1" ref="87e4ebbe9b5c5622d4ba2d9eb740e184" args="(Vertex *v)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">void WKSConstructionHeuristic::checkNeighboursDeg1 </td>
<td>(</td>
<td class="paramtype"><a class="el" href="classVertex.html">Vertex</a> * </td>
<td class="paramname"> <em>v</em> </td>
<td> ) </td>
<td><code> [private]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
copy all Neighbours of v that have degree 1 to VerticesDeg1
</div>
</div><p>
<a class="anchor" name="b466858ce4ff82430552c7ef6db8a2eb"></a><!-- doxytag: member="WKSConstructionHeuristic::findVertexDeg1" ref="b466858ce4ff82430552c7ef6db8a2eb" args="(void)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="classVertex.html">Vertex</a> * WKSConstructionHeuristic::findVertexDeg1 </td>
<td>(</td>
<td class="paramtype">void </td>
<td class="paramname"> </td>
<td> ) </td>
<td><code> [private]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
get the <a class="el" href="classVertex.html" title="a vertex in a graph">Vertex</a> from VerticesDeg1 that is nearest to top (with updated degrees and shortest edges)
</div>
</div><p>
<a class="anchor" name="1c2233d1625f773b3fa32cb7278e9396"></a><!-- doxytag: member="WKSConstructionHeuristic::findVertexDegG" ref="1c2233d1625f773b3fa32cb7278e9396" args="(void)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="classVertex.html">Vertex</a> * WKSConstructionHeuristic::findVertexDegG </td>
<td>(</td>
<td class="paramtype">void </td>
<td class="paramname"> </td>
<td> ) </td>
<td><code> [private]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
get the <a class="el" href="classVertex.html" title="a vertex in a graph">Vertex</a> from VerticesDegG that is nearest to top (with updated degrees and shortest edges)
</div>
</div><p>
<a class="anchor" name="16ff5405de18effbf58bba0b89670a52"></a><!-- doxytag: member="WKSConstructionHeuristic::getName" ref="16ff5405de18effbf58bba0b89670a52" args="(void) const " -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">const char* WKSConstructionHeuristic::getName </td>
<td>(</td>
<td class="paramtype">void </td>
<td class="paramname"> </td>
<td> ) </td>
<td> const<code> [inline, virtual]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
<p>Implements <a class="el" href="classMatchingAlgorithm.html#7305edae5d74e91987bcf983b2a1171a">MatchingAlgorithm</a>.</p>
</div>
</div><p>
<a class="anchor" name="04c931636b6e457493b6bc25697f98fb"></a><!-- doxytag: member="WKSConstructionHeuristic::run" ref="04c931636b6e457493b6bc25697f98fb" args="(void)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">void WKSConstructionHeuristic::run </td>
<td>(</td>
<td class="paramtype">void </td>
<td class="paramname"> </td>
<td> ) </td>
<td><code> [virtual]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
<p>Implements <a class="el" href="classMatchingAlgorithm.html#eea6c808daf03fd788c9a9feea885c41">MatchingAlgorithm</a>.</p>
</div>
</div><p>
<hr><h2>Member Data Documentation</h2>
<a class="anchor" name="a10ccd5f02c16ed9207f10101dd50c43"></a><!-- doxytag: member="WKSConstructionHeuristic::VerticesDeg1" ref="a10ccd5f02c16ed9207f10101dd50c43" args="" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">std::priority_queue<<a class="el" href="classVertex.html">Vertex</a>*, std::vector<<a class="el" href="classVertex.html">Vertex</a>*>, <a class="el" href="classWKSConstructionHeuristic_1_1LongerShortestEdge.html">LongerShortestEdge</a>> <a class="el" href="classWKSConstructionHeuristic.html#a10ccd5f02c16ed9207f10101dd50c43">WKSConstructionHeuristic::VerticesDeg1</a><code> [private]</code> </td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
</div>
</div><p>
<a class="anchor" name="cb53370d5b437466e6eaed1507dcf2f9"></a><!-- doxytag: member="WKSConstructionHeuristic::VerticesDegG" ref="cb53370d5b437466e6eaed1507dcf2f9" args="" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">std::priority_queue<<a class="el" href="classVertex.html">Vertex</a>*, std::vector<<a class="el" href="classVertex.html">Vertex</a>*>, <a class="el" href="classWKSConstructionHeuristic_1_1LongerShortestEdge.html">LongerShortestEdge</a>> <a class="el" href="classWKSConstructionHeuristic.html#cb53370d5b437466e6eaed1507dcf2f9">WKSConstructionHeuristic::VerticesDegG</a><code> [private]</code> </td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
</div>
</div><p>
<hr>The documentation for this class was generated from the following files:<ul>
<li><a class="el" href="WKSConstructionHeuristic_8h_source.html">WKSConstructionHeuristic.h</a><li><a class="el" href="WKSConstructionHeuristic_8cc.html">WKSConstructionHeuristic.cc</a></ul>
</div>
<hr size="1"><address style="text-align: right;"><small>Generated on Mon Aug 17 10:58:33 2009 for steghide by
<a href="http://www.doxygen.org/index.html">
<img src="doxygen.png" alt="doxygen" align="middle" border="0"></a> 1.5.9 </small></address>
</body>
</html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
7392c77c84ff25edfeb07995a77d5148
>
files
>
526
