search

mcximing / hungarian-algorithm-cpp

A C++ wrapper for a hungarian algorithm implementation
BSD 2-Clause "Simplified" License
291 stars 91 forks source link

Assigned value is garbage or undefined #2

Open colmartofus opened 7 years ago

colmartofus commented 7 years ago

By running clang static analysis, I found a bug. I've attached the output. You'll have to grab the following HTML and save it to a .html file to view it. It shows exactly the conditions in which the bug occurs:

<!doctype html>
<html>
<head>
<title>../hungarian.cpp</title>
<style type="text/css">
 body { color:#000000; background-color:#ffffff }
 body { font-family:Helvetica, sans-serif; font-size:10pt }
 h1 { font-size:14pt }
 .code { border-collapse:collapse; width:100%; }
 .code { font-family: "Monospace", monospace; font-size:10pt }
 .code { line-height: 1.2em }
 .comment { color: green; font-style: oblique }
 .keyword { color: blue }
 .string_literal { color: red }
 .directive { color: darkmagenta }
 .expansion { display: none; }
 .macro:hover .expansion { display: block; border: 2px solid #FF0000; padding: 2px; background-color:#FFF0F0; font-weight: normal;   -webkit-border-radius:5px;  -webkit-box-shadow:1px 1px 7px #000; position: absolute; top: -1em; left:10em; z-index: 1 } 
 .macro { color: darkmagenta; background-color:LemonChiffon; position: relative }
 .num { width:2.5em; padding-right:2ex; background-color:#eeeeee }
 .num { text-align:right; font-size:8pt }
 .num { color:#444444 }
 .line { padding-left: 1ex; border-left: 3px solid #ccc }
 .line { white-space: pre }
 .msg { -webkit-box-shadow:1px 1px 7px #000 }
 .msg { -webkit-border-radius:5px }
 .msg { font-family:Helvetica, sans-serif; font-size:8pt }
 .msg { float:left }
 .msg { padding:0.25em 1ex 0.25em 1ex }
 .msg { margin-top:10px; margin-bottom:10px }
 .msg { font-weight:bold }
 .msg { max-width:60em; word-wrap: break-word; white-space: pre-wrap }
 .msgT { padding:0x; spacing:0x }
 .msgEvent { background-color:#fff8b4; color:#000000 }
 .msgControl { background-color:#bbbbbb; color:#000000 }
 .mrange { background-color:#dfddf3 }
 .mrange { border-bottom:1px solid #6F9DBE }
 .PathIndex { font-weight: bold; padding:0px 5px; margin-right:5px; }
 .PathIndex { -webkit-border-radius:8px }
 .PathIndexEvent { background-color:#bfba87 }
 .PathIndexControl { background-color:#8c8c8c }
 .PathNav a { text-decoration:none; font-size: larger }
 .CodeInsertionHint { font-weight: bold; background-color: #10dd10 }
 .CodeRemovalHint { background-color:#de1010 }
 .CodeRemovalHint { border-bottom:1px solid #6F9DBE }
 table.simpletable {
   padding: 5px;
   font-size:12pt;
   margin:20px;
   border-collapse: collapse; border-spacing: 0px;
 }
 td.rowname {
   text-align:right; font-weight:bold; color:#444444;
   padding-right:2ex; }
</style>
</head>
<body>
<!-- BUGDESC Assigned value is garbage or undefined -->

<!-- BUGTYPE Assigned value is garbage or undefined -->

<!-- BUGCATEGORY Logic error -->

<!-- BUGFILE /home/colm/code/camera-event-detector/http/../hungarian.cpp -->

<!-- FILENAME hungarian.cpp -->

<!-- FUNCTIONNAME assignmentoptimal -->

<!-- ISSUEHASHCONTENTOFLINEINCONTEXT d531914caf766c732c24f1702c43386d -->

<!-- BUGLINE 140 -->

<!-- BUGCOLUMN 13 -->

<!-- BUGPATHLENGTH 8 -->

<!-- BUGMETAEND -->
<h3><a href="/">Summary</a> > Report 4691f7</h3>
<h3>Bug Summary</h3>
<table class="simpletable">
<tr><td class="rowname">File:</td><td>http/../hungarian.cpp</td></tr>
<tr><td class="rowname">Location:</td><td><a href="#EndPath">line 140, column 13</a></td></tr>
<tr><td class="rowname">Description:</td><td>Assigned value is garbage or undefined</td></tr>
</table>
<td class="Button"><a href="report/4691f7">Report Bug</a></td>
<h3>Annotated Source Code</h3>
<table class="code">
<tr><td class="num" id="LN1">1</td><td class="line"><span class='comment'>///////////////////////////////////////////////////////////////////////////////</span></td></tr>
<tr><td class="num" id="LN2">2</td><td class="line"><span class='comment'>// Hungarian.cpp: Implementation file for Class HungarianAlgorithm.</span></td></tr>
<tr><td class="num" id="LN3">3</td><td class="line"><span class='comment'>// </span></td></tr>
<tr><td class="num" id="LN4">4</td><td class="line"><span class='comment'>// This is a C++ wrapper with slight modification of a hungarian algorithm implementation by Markus Buehren.</span></td></tr>
<tr><td class="num" id="LN5">5</td><td class="line"><span class='comment'>// The original implementation is a few mex-functions for use in MATLAB, found here:</span></td></tr>
<tr><td class="num" id="LN6">6</td><td class="line"><span class='comment'>// http://www.mathworks.com/matlabcentral/fileexchange/6543-functions-for-the-rectangular-assignment-problem</span></td></tr>
<tr><td class="num" id="LN7">7</td><td class="line"><span class='comment'>// </span></td></tr>
<tr><td class="num" id="LN8">8</td><td class="line"><span class='comment'>// Both this code and the orignal code are published under the BSD license.</span></td></tr>
<tr><td class="num" id="LN9">9</td><td class="line"><span class='comment'>// by Cong Ma, 2016</span></td></tr>
<tr><td class="num" id="LN10">10</td><td class="line"><span class='comment'>// </span></td></tr>
<tr><td class="num" id="LN11">11</td><td class="line"> </td></tr>
<tr><td class="num" id="LN12">12</td><td class="line"><span class='directive'>#include &lt;stdlib.h&gt;</span></td></tr>
<tr><td class="num" id="LN13">13</td><td class="line"><span class='directive'>#include &lt;cfloat&gt; // for DBL_MAX</span></td></tr>
<tr><td class="num" id="LN14">14</td><td class="line"><span class='directive'>#include &lt;cmath&gt;  // for fabs()</span></td></tr>
<tr><td class="num" id="LN15">15</td><td class="line"><span class='directive'>#include "hungarian.hpp"</span></td></tr>
<tr><td class="num" id="LN16">16</td><td class="line"> </td></tr>
<tr><td class="num" id="LN17">17</td><td class="line"> </td></tr>
<tr><td class="num" id="LN18">18</td><td class="line">HungarianAlgorithm::HungarianAlgorithm(){}</td></tr>
<tr><td class="num" id="LN19">19</td><td class="line">HungarianAlgorithm::~HungarianAlgorithm(){}</td></tr>
<tr><td class="num" id="LN20">20</td><td class="line"> </td></tr>
<tr><td class="num" id="LN21">21</td><td class="line"> </td></tr>
<tr><td class="num" id="LN22">22</td><td class="line"><span class='comment'>//********************************************************//</span></td></tr>
<tr><td class="num" id="LN23">23</td><td class="line"><span class='comment'>// A single function wrapper for solving assignment problem.</span></td></tr>
<tr><td class="num" id="LN24">24</td><td class="line"><span class='comment'>//********************************************************//</span></td></tr>
<tr><td class="num" id="LN25">25</td><td class="line"><span class='keyword'>double</span> HungarianAlgorithm::Solve(vector &lt;vector&lt;<span class='keyword'>double</span>&gt; &gt;&amp; DistMatrix, vector&lt;<span class='keyword'>int</span>&gt;&amp; Assignment)</td></tr>
<tr><td class="num" id="LN26">26</td><td class="line">{</td></tr>
<tr><td class="num" id="LN27">27</td><td class="line">  <span class='keyword'>unsigned</span> <span class='keyword'>int</span> nRows = DistMatrix.size();</td></tr>
<tr><td class="num" id="LN28">28</td><td class="line">  <span class='keyword'>unsigned</span> <span class='keyword'>int</span> nCols = DistMatrix[0].size();</td></tr>
<tr><td class="num" id="LN29">29</td><td class="line"> </td></tr>
<tr><td class="num" id="LN30">30</td><td class="line">  <span class='keyword'>double</span> *distMatrixIn = <span class='keyword'>new</span> <span class='keyword'>double</span>[nRows * nCols];</td></tr>
<tr><td class="num" id="LN31">31</td><td class="line">  <span class='keyword'>int</span> *assignment = <span class='keyword'>new</span> <span class='keyword'>int</span>[nRows];</td></tr>
<tr><td class="num" id="LN32">32</td><td class="line">  <span class='keyword'>double</span> cost = 0.0;</td></tr>
<tr><td class="num" id="LN33">33</td><td class="line"> </td></tr>
<tr><td class="num" id="LN34">34</td><td class="line">  <span class='comment'>// Fill in the distMatrixIn. Mind the index is "i + nRows * j".</span></td></tr>
<tr><td class="num" id="LN35">35</td><td class="line">  <span class='comment'>// Here the cost matrix of size MxN is defined as a double precision array of N*M elements. </span></td></tr>
<tr><td class="num" id="LN36">36</td><td class="line">  <span class='comment'>// In the solving functions matrices are seen to be saved MATLAB-internally in row-order.</span></td></tr>
<tr><td class="num" id="LN37">37</td><td class="line">  <span class='comment'>// (i.e. the matrix [1 2; 3 4] will be stored as a vector [1 3 2 4], NOT [1 2 3 4]).</span></td></tr>
<tr><td class="num" id="LN38">38</td><td class="line">  <span class='keyword'>for</span> (<span class='keyword'>unsigned</span> <span class='keyword'>int</span> i = 0; i &lt; nRows; i++)</td></tr>
<tr><td class="num" id="LN39">39</td><td class="line">      <span class='keyword'>for</span> (<span class='keyword'>unsigned</span> <span class='keyword'>int</span> j = 0; j &lt; nCols; j++)</td></tr>
<tr><td class="num" id="LN40">40</td><td class="line">          distMatrixIn[i + nRows * j] = DistMatrix[i][j];</td></tr>
<tr><td class="num" id="LN41">41</td><td class="line">  </td></tr>
<tr><td class="num" id="LN42">42</td><td class="line">  <span class='comment'>// call solving function</span></td></tr>
<tr><td class="num" id="LN43">43</td><td class="line">  assignmentoptimal(assignment, &amp;cost, distMatrixIn, nRows, nCols);</td></tr>
<tr><td class="num" id="LN44">44</td><td class="line"> </td></tr>
<tr><td class="num" id="LN45">45</td><td class="line">  Assignment.clear();</td></tr>
<tr><td class="num" id="LN46">46</td><td class="line">  <span class='keyword'>for</span> (<span class='keyword'>unsigned</span> <span class='keyword'>int</span> r = 0; r &lt; nRows; r++)</td></tr>
<tr><td class="num" id="LN47">47</td><td class="line">      Assignment.push_back(assignment[r]);</td></tr>
<tr><td class="num" id="LN48">48</td><td class="line"> </td></tr>
<tr><td class="num" id="LN49">49</td><td class="line">  <span class='keyword'>delete</span>[] distMatrixIn;</td></tr>
<tr><td class="num" id="LN50">50</td><td class="line">  <span class='keyword'>delete</span>[] assignment;</td></tr>
<tr><td class="num" id="LN51">51</td><td class="line">  <span class='keyword'>return</span> cost;</td></tr>
<tr><td class="num" id="LN52">52</td><td class="line">}</td></tr>
<tr><td class="num" id="LN53">53</td><td class="line"> </td></tr>
<tr><td class="num" id="LN54">54</td><td class="line"> </td></tr>
<tr><td class="num" id="LN55">55</td><td class="line"><span class='comment'>//********************************************************//</span></td></tr>
<tr><td class="num" id="LN56">56</td><td class="line"><span class='comment'>// Solve optimal solution for assignment problem using Munkres algorithm, also known as Hungarian Algorithm.</span></td></tr>
<tr><td class="num" id="LN57">57</td><td class="line"><span class='comment'>//********************************************************//</span></td></tr>
<tr><td class="num" id="LN58">58</td><td class="line"><span class='keyword'>void</span> HungarianAlgorithm::assignmentoptimal(<span class='keyword'>int</span> *assignment, <span class='keyword'>double</span> *cost, <span class='keyword'>double</span> *distMatrixIn, <span class='keyword'>int</span> nOfRows, <span class='keyword'>int</span> nOfColumns)</td></tr>
<tr><td class="num" id="LN59">59</td><td class="line">{</td></tr>
<tr><td class="num" id="LN60">60</td><td class="line">  <span class='keyword'>double</span> *distMatrix, *distMatrixTemp, *distMatrixEnd, *columnEnd, value, minValue;</td></tr>
<tr><td class="num" id="LN61">61</td><td class="line">  <span class='keyword'>bool</span> *coveredColumns, *coveredRows, *starMatrix, *newStarMatrix, *primeMatrix;</td></tr>
<tr><td class="num" id="LN62">62</td><td class="line">  <span class='keyword'>int</span> nOfElements, minDim, row, col;</td></tr>
<tr><td class="num" id="LN63">63</td><td class="line"> </td></tr>
<tr><td class="num" id="LN64">64</td><td class="line">  <span class='comment'>/* initialization */</span></td></tr>
<tr><td class="num" id="LN65">65</td><td class="line">  *cost = 0;</td></tr>
<tr><td class="num" id="LN66">66</td><td class="line">  <span class='keyword'>for</span> (row = 0; <span class="mrange">row&lt;nOfRows</span>; row++)</td></tr>
<tr><td class="num"></td><td class="line"><div id="Path1" class="msg msgEvent" style="margin-left:23ex"><table class="msgT"><tr><td valign="top"><div class="PathIndex PathIndexEvent">1</div></td><td>Assuming 'row' is &gt;= 'nOfRows'</td><td><div class="PathNav"><a href="#Path2" title="Next event (2)">&#x2192;</a></div></td></tr></table></div></td></tr>
<tr><td class="num"></td><td class="line"><div id="Path2" class="msg msgControl" style="margin-left:9ex"><table class="msgT"><tr><td valign="top"><div class="PathIndex PathIndexControl">2</div></td><td><div class="PathNav"><a href="#Path1" title="Previous event (1)">&#x2190;</a></div></td></td><td>Loop condition is false. Execution continues on line 71</td><td><div class="PathNav"><a href="#Path3" title="Next event (3)">&#x2192;</a></div></td></tr></table></div></td></tr>
<tr><td class="num" id="LN67">67</td><td class="line">      assignment[row] = -1;</td></tr>
<tr><td class="num" id="LN68">68</td><td class="line"> </td></tr>
<tr><td class="num" id="LN69">69</td><td class="line">  <span class='comment'>/* generate working copy of distance Matrix */</span></td></tr>
<tr><td class="num" id="LN70">70</td><td class="line">  <span class='comment'>/* check if all matrix elements are positive */</span></td></tr>
<tr><td class="num" id="LN71">71</td><td class="line">  nOfElements = nOfRows * nOfColumns;</td></tr>
<tr><td class="num" id="LN72">72</td><td class="line">  distMatrix = (<span class='keyword'>double</span> *)malloc(nOfElements * <span class='keyword'>sizeof</span>(<span class='keyword'>double</span>));</td></tr>
<tr><td class="num" id="LN73">73</td><td class="line">  distMatrixEnd = distMatrix + nOfElements;</td></tr>
<tr><td class="num" id="LN74">74</td><td class="line"> </td></tr>
<tr><td class="num" id="LN75">75</td><td class="line">  <span class='keyword'>for</span> (row = 0; <span class="mrange">row&lt;nOfElements</span>; row++)</td></tr>
<tr><td class="num"></td><td class="line"><div id="Path3" class="msg msgEvent" style="margin-left:23ex"><table class="msgT"><tr><td valign="top"><div class="PathIndex PathIndexEvent">3</div></td><td><div class="PathNav"><a href="#Path2" title="Previous event (2)">&#x2190;</a></div></td></td><td>Assuming 'row' is &gt;= 'nOfElements'</td><td><div class="PathNav"><a href="#Path4" title="Next event (4)">&#x2192;</a></div></td></tr></table></div></td></tr>
<tr><td class="num"></td><td class="line"><div id="Path4" class="msg msgControl" style="margin-left:9ex"><table class="msgT"><tr><td valign="top"><div class="PathIndex PathIndexControl">4</div></td><td><div class="PathNav"><a href="#Path3" title="Previous event (3)">&#x2190;</a></div></td></td><td>Loop condition is false. Execution continues on line 85</td><td><div class="PathNav"><a href="#Path5" title="Next event (5)">&#x2192;</a></div></td></tr></table></div></td></tr>
<tr><td class="num" id="LN76">76</td><td class="line">  {</td></tr>
<tr><td class="num" id="LN77">77</td><td class="line">      value = distMatrixIn[row];</td></tr>
<tr><td class="num" id="LN78">78</td><td class="line">      <span class='keyword'>if</span> (value &lt; 0)</td></tr>
<tr><td class="num" id="LN79">79</td><td class="line">          cerr &lt;&lt; <span class='string_literal'>"All matrix elements have to be non-negative."</span> &lt;&lt; endl;</td></tr>
<tr><td class="num" id="LN80">80</td><td class="line">      distMatrix[row] = value;</td></tr>
<tr><td class="num" id="LN81">81</td><td class="line">  }</td></tr>
<tr><td class="num" id="LN82">82</td><td class="line"> </td></tr>
<tr><td class="num" id="LN83">83</td><td class="line"> </td></tr>
<tr><td class="num" id="LN84">84</td><td class="line">  <span class='comment'>/* memory allocation */</span></td></tr>
<tr><td class="num" id="LN85">85</td><td class="line">  coveredColumns = (<span class='keyword'>bool</span> *)calloc(nOfColumns, <span class='keyword'>sizeof</span>(<span class='keyword'>bool</span>));</td></tr>
<tr><td class="num" id="LN86">86</td><td class="line">  coveredRows = (<span class='keyword'>bool</span> *)calloc(nOfRows, <span class='keyword'>sizeof</span>(<span class='keyword'>bool</span>));</td></tr>
<tr><td class="num" id="LN87">87</td><td class="line">  starMatrix = (<span class='keyword'>bool</span> *)calloc(nOfElements, <span class='keyword'>sizeof</span>(<span class='keyword'>bool</span>));</td></tr>
<tr><td class="num" id="LN88">88</td><td class="line">  primeMatrix = (<span class='keyword'>bool</span> *)calloc(nOfElements, <span class='keyword'>sizeof</span>(<span class='keyword'>bool</span>));</td></tr>
<tr><td class="num" id="LN89">89</td><td class="line">  newStarMatrix = (<span class='keyword'>bool</span> *)calloc(nOfElements, <span class='keyword'>sizeof</span>(<span class='keyword'>bool</span>)); <span class='comment'>/* used in step4 */</span></td></tr>
<tr><td class="num" id="LN90">90</td><td class="line"> </td></tr>
<tr><td class="num" id="LN91">91</td><td class="line">  <span class='comment'>/* preliminary steps */</span></td></tr>
<tr><td class="num" id="LN92">92</td><td class="line">  <span class='keyword'>if</span> (nOfRows &lt;= nOfColumns)</td></tr>
<tr><td class="num"></td><td class="line"><div id="Path5" class="msg msgControl" style="margin-left:9ex"><table class="msgT"><tr><td valign="top"><div class="PathIndex PathIndexControl">5</div></td><td><div class="PathNav"><a href="#Path4" title="Previous event (4)">&#x2190;</a></div></td></td><td>Taking false branch</td><td><div class="PathNav"><a href="#Path6" title="Next event (6)">&#x2192;</a></div></td></tr></table></div></td></tr>
<tr><td class="num" id="LN93">93</td><td class="line">  {</td></tr>
<tr><td class="num" id="LN94">94</td><td class="line">      minDim = nOfRows;</td></tr>
<tr><td class="num" id="LN95">95</td><td class="line"> </td></tr>
<tr><td class="num" id="LN96">96</td><td class="line">      <span class='keyword'>for</span> (row = 0; row&lt;nOfRows; row++)</td></tr>
<tr><td class="num" id="LN97">97</td><td class="line">      {</td></tr>
<tr><td class="num" id="LN98">98</td><td class="line">          <span class='comment'>/* find the smallest element in the row */</span></td></tr>
<tr><td class="num" id="LN99">99</td><td class="line">          distMatrixTemp = distMatrix + row;</td></tr>
<tr><td class="num" id="LN100">100</td><td class="line">            minValue = *distMatrixTemp;</td></tr>
<tr><td class="num" id="LN101">101</td><td class="line">            distMatrixTemp += nOfRows;</td></tr>
<tr><td class="num" id="LN102">102</td><td class="line">            <span class='keyword'>while</span> (distMatrixTemp &lt; distMatrixEnd)</td></tr>
<tr><td class="num" id="LN103">103</td><td class="line">            {</td></tr>
<tr><td class="num" id="LN104">104</td><td class="line">                value = *distMatrixTemp;</td></tr>
<tr><td class="num" id="LN105">105</td><td class="line">                <span class='keyword'>if</span> (value &lt; minValue)</td></tr>
<tr><td class="num" id="LN106">106</td><td class="line">                    minValue = value;</td></tr>
<tr><td class="num" id="LN107">107</td><td class="line">                distMatrixTemp += nOfRows;</td></tr>
<tr><td class="num" id="LN108">108</td><td class="line">            }</td></tr>
<tr><td class="num" id="LN109">109</td><td class="line"> </td></tr>
<tr><td class="num" id="LN110">110</td><td class="line">            <span class='comment'>/* subtract the smallest element from each element of the row */</span></td></tr>
<tr><td class="num" id="LN111">111</td><td class="line">            distMatrixTemp = distMatrix + row;</td></tr>
<tr><td class="num" id="LN112">112</td><td class="line">            <span class='keyword'>while</span> (distMatrixTemp &lt; distMatrixEnd)</td></tr>
<tr><td class="num" id="LN113">113</td><td class="line">            {</td></tr>
<tr><td class="num" id="LN114">114</td><td class="line">                *distMatrixTemp -= minValue;</td></tr>
<tr><td class="num" id="LN115">115</td><td class="line">                distMatrixTemp += nOfRows;</td></tr>
<tr><td class="num" id="LN116">116</td><td class="line">            }</td></tr>
<tr><td class="num" id="LN117">117</td><td class="line">        }</td></tr>
<tr><td class="num" id="LN118">118</td><td class="line"> </td></tr>
<tr><td class="num" id="LN119">119</td><td class="line">        <span class='comment'>/* Steps 1 and 2a */</span></td></tr>
<tr><td class="num" id="LN120">120</td><td class="line">        <span class='keyword'>for</span> (row = 0; row&lt;nOfRows; row++)</td></tr>
<tr><td class="num" id="LN121">121</td><td class="line">            <span class='keyword'>for</span> (col = 0; col&lt;nOfColumns; col++)</td></tr>
<tr><td class="num" id="LN122">122</td><td class="line">                <span class='keyword'>if</span> (fabs(distMatrix[row + nOfRows*col]) &lt; <span class='macro'>DBL_EPSILON<span class='expansion'>2.2204460492503131e-16</span></span>)</td></tr>
<tr><td class="num" id="LN123">123</td><td class="line">                    <span class='keyword'>if</span> (!coveredColumns[col])</td></tr>
<tr><td class="num" id="LN124">124</td><td class="line">                    {</td></tr>
<tr><td class="num" id="LN125">125</td><td class="line">                        starMatrix[row + nOfRows*col] = <span class='keyword'>true</span>;</td></tr>
<tr><td class="num" id="LN126">126</td><td class="line">                        coveredColumns[col] = <span class='keyword'>true</span>;</td></tr>
<tr><td class="num" id="LN127">127</td><td class="line">                        <span class='keyword'>break</span>;</td></tr>
<tr><td class="num" id="LN128">128</td><td class="line">                    }</td></tr>
<tr><td class="num" id="LN129">129</td><td class="line">    }</td></tr>
<tr><td class="num" id="LN130">130</td><td class="line">    <span class='keyword'>else</span> <span class='comment'>/* if(nOfRows &gt; nOfColumns) */</span></td></tr>
<tr><td class="num" id="LN131">131</td><td class="line">    {</td></tr>
<tr><td class="num" id="LN132">132</td><td class="line">        minDim = nOfColumns;</td></tr>
<tr><td class="num" id="LN133">133</td><td class="line"> </td></tr>
<tr><td class="num" id="LN134">134</td><td class="line">        <span class='keyword'>for</span> (col = 0; <span class="mrange">col&lt;nOfColumns</span>; col++)</td></tr>
<tr><td class="num"></td><td class="line"><div id="Path6" class="msg msgEvent" style="margin-left:31ex"><table class="msgT"><tr><td valign="top"><div class="PathIndex PathIndexEvent">6</div></td><td><div class="PathNav"><a href="#Path5" title="Previous event (5)">&#x2190;</a></div></td></td><td>Assuming 'col' is &lt; 'nOfColumns'</td><td><div class="PathNav"><a href="#Path7" title="Next event (7)">&#x2192;</a></div></td></tr></table></div></td></tr>
<tr><td class="num"></td><td class="line"><div id="Path7" class="msg msgControl" style="margin-left:17ex"><table class="msgT"><tr><td valign="top"><div class="PathIndex PathIndexControl">7</div></td><td><div class="PathNav"><a href="#Path6" title="Previous event (6)">&#x2190;</a></div></td></td><td>Loop condition is true.  Entering loop body</td><td><div class="PathNav"><a href="#EndPath" title="Next event (8)">&#x2192;</a></div></td></tr></table></div></td></tr>
<tr><td class="num" id="LN135">135</td><td class="line">        {</td></tr>
<tr><td class="num" id="LN136">136</td><td class="line">            <span class='comment'>/* find the smallest element in the column */</span></td></tr>
<tr><td class="num" id="LN137">137</td><td class="line">            distMatrixTemp = distMatrix + nOfRows*col;</td></tr>
<tr><td class="num" id="LN138">138</td><td class="line">            columnEnd = distMatrixTemp + nOfRows;</td></tr>
<tr><td class="num" id="LN139">139</td><td class="line"> </td></tr>
<tr><td class="num" id="LN140">140</td><td class="line">            minValue = <span class="mrange">*distMatrixTemp++</span>;</td></tr>
<tr><td class="num"></td><td class="line"><div id="EndPath" class="msg msgEvent" style="margin-left:34ex"><table class="msgT"><tr><td valign="top"><div class="PathIndex PathIndexEvent">8</div></td><td><div class="PathNav"><a href="#Path7" title="Previous event (7)">&#x2190;</a></div></td></td><td>Assigned value is garbage or undefined</td></tr></table></div></td></tr>
<tr><td class="num" id="LN141">141</td><td class="line">            <span class='keyword'>while</span> (distMatrixTemp &lt; columnEnd)</td></tr>
<tr><td class="num" id="LN142">142</td><td class="line">            {</td></tr>
<tr><td class="num" id="LN143">143</td><td class="line">                value = *distMatrixTemp++;</td></tr>
<tr><td class="num" id="LN144">144</td><td class="line">                <span class='keyword'>if</span> (value &lt; minValue)</td></tr>
<tr><td class="num" id="LN145">145</td><td class="line">                    minValue = value;</td></tr>
<tr><td class="num" id="LN146">146</td><td class="line">            }</td></tr>
<tr><td class="num" id="LN147">147</td><td class="line"> </td></tr>
<tr><td class="num" id="LN148">148</td><td class="line">            <span class='comment'>/* subtract the smallest element from each element of the column */</span></td></tr>
<tr><td class="num" id="LN149">149</td><td class="line">            distMatrixTemp = distMatrix + nOfRows*col;</td></tr>
<tr><td class="num" id="LN150">150</td><td class="line">            <span class='keyword'>while</span> (distMatrixTemp &lt; columnEnd)</td></tr>
<tr><td class="num" id="LN151">151</td><td class="line">                *distMatrixTemp++ -= minValue;</td></tr>
<tr><td class="num" id="LN152">152</td><td class="line">        }</td></tr>
<tr><td class="num" id="LN153">153</td><td class="line"> </td></tr>
<tr><td class="num" id="LN154">154</td><td class="line">        <span class='comment'>/* Steps 1 and 2a */</span></td></tr>
<tr><td class="num" id="LN155">155</td><td class="line">        <span class='keyword'>for</span> (col = 0; col&lt;nOfColumns; col++)</td></tr>
<tr><td class="num" id="LN156">156</td><td class="line">            <span class='keyword'>for</span> (row = 0; row&lt;nOfRows; row++)</td></tr>
<tr><td class="num" id="LN157">157</td><td class="line">                <span class='keyword'>if</span> (fabs(distMatrix[row + nOfRows*col]) &lt; <span class='macro'>DBL_EPSILON<span class='expansion'>2.2204460492503131e-16</span></span>)</td></tr>
<tr><td class="num" id="LN158">158</td><td class="line">                    <span class='keyword'>if</span> (!coveredRows[row])</td></tr>
<tr><td class="num" id="LN159">159</td><td class="line">                    {</td></tr>
<tr><td class="num" id="LN160">160</td><td class="line">                        starMatrix[row + nOfRows*col] = <span class='keyword'>true</span>;</td></tr>
<tr><td class="num" id="LN161">161</td><td class="line">                        coveredColumns[col] = <span class='keyword'>true</span>;</td></tr>
<tr><td class="num" id="LN162">162</td><td class="line">                        coveredRows[row] = <span class='keyword'>true</span>;</td></tr>
<tr><td class="num" id="LN163">163</td><td class="line">                        <span class='keyword'>break</span>;</td></tr>
<tr><td class="num" id="LN164">164</td><td class="line">                    }</td></tr>
<tr><td class="num" id="LN165">165</td><td class="line">        <span class='keyword'>for</span> (row = 0; row&lt;nOfRows; row++)</td></tr>
<tr><td class="num" id="LN166">166</td><td class="line">            coveredRows[row] = <span class='keyword'>false</span>;</td></tr>
<tr><td class="num" id="LN167">167</td><td class="line"> </td></tr>
<tr><td class="num" id="LN168">168</td><td class="line">    }</td></tr>
<tr><td class="num" id="LN169">169</td><td class="line"> </td></tr>
<tr><td class="num" id="LN170">170</td><td class="line">    <span class='comment'>/* move to step 2b */</span></td></tr>
<tr><td class="num" id="LN171">171</td><td class="line">    step2b(assignment, distMatrix, starMatrix, newStarMatrix, primeMatrix, coveredColumns, coveredRows, nOfRows, nOfColumns, minDim);</td></tr>
<tr><td class="num" id="LN172">172</td><td class="line"> </td></tr>
<tr><td class="num" id="LN173">173</td><td class="line">    <span class='comment'>/* compute cost and remove invalid assignments */</span></td></tr>
<tr><td class="num" id="LN174">174</td><td class="line">    computeassignmentcost(assignment, cost, distMatrixIn, nOfRows);</td></tr>
<tr><td class="num" id="LN175">175</td><td class="line"> </td></tr>
<tr><td class="num" id="LN176">176</td><td class="line">    <span class='comment'>/* free allocated memory */</span></td></tr>
<tr><td class="num" id="LN177">177</td><td class="line">    free(distMatrix);</td></tr>
<tr><td class="num" id="LN178">178</td><td class="line">    free(coveredColumns);</td></tr>
<tr><td class="num" id="LN179">179</td><td class="line">    free(coveredRows);</td></tr>
<tr><td class="num" id="LN180">180</td><td class="line">    free(starMatrix);</td></tr>
<tr><td class="num" id="LN181">181</td><td class="line">    free(primeMatrix);</td></tr>
<tr><td class="num" id="LN182">182</td><td class="line">    free(newStarMatrix);</td></tr>
<tr><td class="num" id="LN183">183</td><td class="line"> </td></tr>
<tr><td class="num" id="LN184">184</td><td class="line">    <span class='keyword'>return</span>;</td></tr>
<tr><td class="num" id="LN185">185</td><td class="line">}</td></tr>
<tr><td class="num" id="LN186">186</td><td class="line"> </td></tr>
<tr><td class="num" id="LN187">187</td><td class="line"><span class='comment'>/********************************************************/</span></td></tr>
<tr><td class="num" id="LN188">188</td><td class="line"><span class='keyword'>void</span> HungarianAlgorithm::buildassignmentvector(<span class='keyword'>int</span> *assignment, <span class='keyword'>bool</span> *starMatrix, <span class='keyword'>int</span> nOfRows, <span class='keyword'>int</span> nOfColumns)</td></tr>
<tr><td class="num" id="LN189">189</td><td class="line">{</td></tr>
<tr><td class="num" id="LN190">190</td><td class="line">    <span class='keyword'>int</span> row, col;</td></tr>
<tr><td class="num" id="LN191">191</td><td class="line"> </td></tr>
<tr><td class="num" id="LN192">192</td><td class="line">    <span class='keyword'>for</span> (row = 0; row&lt;nOfRows; row++)</td></tr>
<tr><td class="num" id="LN193">193</td><td class="line">        <span class='keyword'>for</span> (col = 0; col&lt;nOfColumns; col++)</td></tr>
<tr><td class="num" id="LN194">194</td><td class="line">            <span class='keyword'>if</span> (starMatrix[row + nOfRows*col])</td></tr>
<tr><td class="num" id="LN195">195</td><td class="line">            {</td></tr>
<tr><td class="num" id="LN196">196</td><td class="line"><span class='directive'>#ifdef ONE_INDEXING</span></td></tr>
<tr><td class="num" id="LN197">197</td><td class="line">                assignment[row] = col + 1; <span class='comment'>/* MATLAB-Indexing */</span></td></tr>
<tr><td class="num" id="LN198">198</td><td class="line"><span class='directive'>#else</span></td></tr>
<tr><td class="num" id="LN199">199</td><td class="line">                assignment[row] = col;</td></tr>
<tr><td class="num" id="LN200">200</td><td class="line"><span class='directive'>#endif</span></td></tr>
<tr><td class="num" id="LN201">201</td><td class="line">                <span class='keyword'>break</span>;</td></tr>
<tr><td class="num" id="LN202">202</td><td class="line">            }</td></tr>
<tr><td class="num" id="LN203">203</td><td class="line">}</td></tr>
<tr><td class="num" id="LN204">204</td><td class="line"> </td></tr>
<tr><td class="num" id="LN205">205</td><td class="line"><span class='comment'>/********************************************************/</span></td></tr>
<tr><td class="num" id="LN206">206</td><td class="line"><span class='keyword'>void</span> HungarianAlgorithm::computeassignmentcost(<span class='keyword'>int</span> *assignment, <span class='keyword'>double</span> *cost, <span class='keyword'>double</span> *distMatrix, <span class='keyword'>int</span> nOfRows)</td></tr>
<tr><td class="num" id="LN207">207</td><td class="line">{</td></tr>
<tr><td class="num" id="LN208">208</td><td class="line">    <span class='keyword'>int</span> row, col;</td></tr>
<tr><td class="num" id="LN209">209</td><td class="line"> </td></tr>
<tr><td class="num" id="LN210">210</td><td class="line">    <span class='keyword'>for</span> (row = 0; row&lt;nOfRows; row++)</td></tr>
<tr><td class="num" id="LN211">211</td><td class="line">    {</td></tr>
<tr><td class="num" id="LN212">212</td><td class="line">        col = assignment[row];</td></tr>
<tr><td class="num" id="LN213">213</td><td class="line">        <span class='keyword'>if</span> (col &gt;= 0)</td></tr>
<tr><td class="num" id="LN214">214</td><td class="line">            *cost += distMatrix[row + nOfRows*col];</td></tr>
<tr><td class="num" id="LN215">215</td><td class="line">    }</td></tr>
<tr><td class="num" id="LN216">216</td><td class="line">}</td></tr>
<tr><td class="num" id="LN217">217</td><td class="line"> </td></tr>
<tr><td class="num" id="LN218">218</td><td class="line"><span class='comment'>/********************************************************/</span></td></tr>
<tr><td class="num" id="LN219">219</td><td class="line"><span class='keyword'>void</span> HungarianAlgorithm::step2a(<span class='keyword'>int</span> *assignment, <span class='keyword'>double</span> *distMatrix, <span class='keyword'>bool</span> *starMatrix, <span class='keyword'>bool</span> *newStarMatrix, <span class='keyword'>bool</span> *primeMatrix, <span class='keyword'>bool</span> *coveredColumns, <span class='keyword'>bool</span> *coveredRows, <span class='keyword'>int</span> nOfRows, <span class='keyword'>int</span> nOfColumns, <span class='keyword'>int</span> minDim)</td></tr>
<tr><td class="num" id="LN220">220</td><td class="line">{</td></tr>
<tr><td class="num" id="LN221">221</td><td class="line">    <span class='keyword'>bool</span> *starMatrixTemp, *columnEnd;</td></tr>
<tr><td class="num" id="LN222">222</td><td class="line">    <span class='keyword'>int</span> col;</td></tr>
<tr><td class="num" id="LN223">223</td><td class="line"> </td></tr>
<tr><td class="num" id="LN224">224</td><td class="line">    <span class='comment'>/* cover every column containing a starred zero */</span></td></tr>
<tr><td class="num" id="LN225">225</td><td class="line">    <span class='keyword'>for</span> (col = 0; col&lt;nOfColumns; col++)</td></tr>
<tr><td class="num" id="LN226">226</td><td class="line">    {</td></tr>
<tr><td class="num" id="LN227">227</td><td class="line">        starMatrixTemp = starMatrix + nOfRows*col;</td></tr>
<tr><td class="num" id="LN228">228</td><td class="line">        columnEnd = starMatrixTemp + nOfRows;</td></tr>
<tr><td class="num" id="LN229">229</td><td class="line">        <span class='keyword'>while</span> (starMatrixTemp &lt; columnEnd){</td></tr>
<tr><td class="num" id="LN230">230</td><td class="line">            <span class='keyword'>if</span> (*starMatrixTemp++)</td></tr>
<tr><td class="num" id="LN231">231</td><td class="line">            {</td></tr>
<tr><td class="num" id="LN232">232</td><td class="line">                coveredColumns[col] = <span class='keyword'>true</span>;</td></tr>
<tr><td class="num" id="LN233">233</td><td class="line">                <span class='keyword'>break</span>;</td></tr>
<tr><td class="num" id="LN234">234</td><td class="line">            }</td></tr>
<tr><td class="num" id="LN235">235</td><td class="line">        }</td></tr>
<tr><td class="num" id="LN236">236</td><td class="line">    }</td></tr>
<tr><td class="num" id="LN237">237</td><td class="line"> </td></tr>
<tr><td class="num" id="LN238">238</td><td class="line">    <span class='comment'>/* move to step 3 */</span></td></tr>
<tr><td class="num" id="LN239">239</td><td class="line">    step2b(assignment, distMatrix, starMatrix, newStarMatrix, primeMatrix, coveredColumns, coveredRows, nOfRows, nOfColumns, minDim);</td></tr>
<tr><td class="num" id="LN240">240</td><td class="line">}</td></tr>
<tr><td class="num" id="LN241">241</td><td class="line"> </td></tr>
<tr><td class="num" id="LN242">242</td><td class="line"><span class='comment'>/********************************************************/</span></td></tr>
<tr><td class="num" id="LN243">243</td><td class="line"><span class='keyword'>void</span> HungarianAlgorithm::step2b(<span class='keyword'>int</span> *assignment, <span class='keyword'>double</span> *distMatrix, <span class='keyword'>bool</span> *starMatrix, <span class='keyword'>bool</span> *newStarMatrix, <span class='keyword'>bool</span> *primeMatrix, <span class='keyword'>bool</span> *coveredColumns, <span class='keyword'>bool</span> *coveredRows, <span class='keyword'>int</span> nOfRows, <span class='keyword'>int</span> nOfColumns, <span class='keyword'>int</span> minDim)</td></tr>
<tr><td class="num" id="LN244">244</td><td class="line">{</td></tr>
<tr><td class="num" id="LN245">245</td><td class="line">    <span class='keyword'>int</span> col, nOfCoveredColumns;</td></tr>
<tr><td class="num" id="LN246">246</td><td class="line"> </td></tr>
<tr><td class="num" id="LN247">247</td><td class="line">    <span class='comment'>/* count covered columns */</span></td></tr>
<tr><td class="num" id="LN248">248</td><td class="line">    nOfCoveredColumns = 0;</td></tr>
<tr><td class="num" id="LN249">249</td><td class="line">    <span class='keyword'>for</span> (col = 0; col&lt;nOfColumns; col++)</td></tr>
<tr><td class="num" id="LN250">250</td><td class="line">        <span class='keyword'>if</span> (coveredColumns[col])</td></tr>
<tr><td class="num" id="LN251">251</td><td class="line">            nOfCoveredColumns++;</td></tr>
<tr><td class="num" id="LN252">252</td><td class="line"> </td></tr>
<tr><td class="num" id="LN253">253</td><td class="line">    <span class='keyword'>if</span> (nOfCoveredColumns == minDim)</td></tr>
<tr><td class="num" id="LN254">254</td><td class="line">    {</td></tr>
<tr><td class="num" id="LN255">255</td><td class="line">        <span class='comment'>/* algorithm finished */</span></td></tr>
<tr><td class="num" id="LN256">256</td><td class="line">        buildassignmentvector(assignment, starMatrix, nOfRows, nOfColumns);</td></tr>
<tr><td class="num" id="LN257">257</td><td class="line">    }</td></tr>
<tr><td class="num" id="LN258">258</td><td class="line">    <span class='keyword'>else</span></td></tr>
<tr><td class="num" id="LN259">259</td><td class="line">    {</td></tr>
<tr><td class="num" id="LN260">260</td><td class="line">        <span class='comment'>/* move to step 3 */</span></td></tr>
<tr><td class="num" id="LN261">261</td><td class="line">        step3(assignment, distMatrix, starMatrix, newStarMatrix, primeMatrix, coveredColumns, coveredRows, nOfRows, nOfColumns, minDim);</td></tr>
<tr><td class="num" id="LN262">262</td><td class="line">    }</td></tr>
<tr><td class="num" id="LN263">263</td><td class="line"> </td></tr>
<tr><td class="num" id="LN264">264</td><td class="line">}</td></tr>
<tr><td class="num" id="LN265">265</td><td class="line"> </td></tr>
<tr><td class="num" id="LN266">266</td><td class="line"><span class='comment'>/********************************************************/</span></td></tr>
<tr><td class="num" id="LN267">267</td><td class="line"><span class='keyword'>void</span> HungarianAlgorithm::step3(<span class='keyword'>int</span> *assignment, <span class='keyword'>double</span> *distMatrix, <span class='keyword'>bool</span> *starMatrix, <span class='keyword'>bool</span> *newStarMatrix, <span class='keyword'>bool</span> *primeMatrix, <span class='keyword'>bool</span> *coveredColumns, <span class='keyword'>bool</span> *coveredRows, <span class='keyword'>int</span> nOfRows, <span class='keyword'>int</span> nOfColumns, <span class='keyword'>int</span> minDim)</td></tr>
<tr><td class="num" id="LN268">268</td><td class="line">{</td></tr>
<tr><td class="num" id="LN269">269</td><td class="line">    <span class='keyword'>bool</span> zerosFound;</td></tr>
<tr><td class="num" id="LN270">270</td><td class="line">    <span class='keyword'>int</span> row, col, starCol;</td></tr>
<tr><td class="num" id="LN271">271</td><td class="line"> </td></tr>
<tr><td class="num" id="LN272">272</td><td class="line">    zerosFound = <span class='keyword'>true</span>;</td></tr>
<tr><td class="num" id="LN273">273</td><td class="line">    <span class='keyword'>while</span> (zerosFound)</td></tr>
<tr><td class="num" id="LN274">274</td><td class="line">    {</td></tr>
<tr><td class="num" id="LN275">275</td><td class="line">        zerosFound = <span class='keyword'>false</span>;</td></tr>
<tr><td class="num" id="LN276">276</td><td class="line">        <span class='keyword'>for</span> (col = 0; col&lt;nOfColumns; col++)</td></tr>
<tr><td class="num" id="LN277">277</td><td class="line">            <span class='keyword'>if</span> (!coveredColumns[col])</td></tr>
<tr><td class="num" id="LN278">278</td><td class="line">                <span class='keyword'>for</span> (row = 0; row&lt;nOfRows; row++)</td></tr>
<tr><td class="num" id="LN279">279</td><td class="line">                    <span class='keyword'>if</span> ((!coveredRows[row]) &amp;&amp; (fabs(distMatrix[row + nOfRows*col]) &lt; <span class='macro'>DBL_EPSILON<span class='expansion'>2.2204460492503131e-16</span></span>))</td></tr>
<tr><td class="num" id="LN280">280</td><td class="line">                    {</td></tr>
<tr><td class="num" id="LN281">281</td><td class="line">                        <span class='comment'>/* prime zero */</span></td></tr>
<tr><td class="num" id="LN282">282</td><td class="line">                        primeMatrix[row + nOfRows*col] = <span class='keyword'>true</span>;</td></tr>
<tr><td class="num" id="LN283">283</td><td class="line"> </td></tr>
<tr><td class="num" id="LN284">284</td><td class="line">                        <span class='comment'>/* find starred zero in current row */</span></td></tr>
<tr><td class="num" id="LN285">285</td><td class="line">                        <span class='keyword'>for</span> (starCol = 0; starCol&lt;nOfColumns; starCol++)</td></tr>
<tr><td class="num" id="LN286">286</td><td class="line">                            <span class='keyword'>if</span> (starMatrix[row + nOfRows*starCol])</td></tr>
<tr><td class="num" id="LN287">287</td><td class="line">                                <span class='keyword'>break</span>;</td></tr>
<tr><td class="num" id="LN288">288</td><td class="line"> </td></tr>
<tr><td class="num" id="LN289">289</td><td class="line">                        <span class='keyword'>if</span> (starCol == nOfColumns) <span class='comment'>/* no starred zero found */</span></td></tr>
<tr><td class="num" id="LN290">290</td><td class="line">                        {</td></tr>
<tr><td class="num" id="LN291">291</td><td class="line">                            <span class='comment'>/* move to step 4 */</span></td></tr>
<tr><td class="num" id="LN292">292</td><td class="line">                            step4(assignment, distMatrix, starMatrix, newStarMatrix, primeMatrix, coveredColumns, coveredRows, nOfRows, nOfColumns, minDim, row, col);</td></tr>
<tr><td class="num" id="LN293">293</td><td class="line">                            <span class='keyword'>return</span>;</td></tr>
<tr><td class="num" id="LN294">294</td><td class="line">                        }</td></tr>
<tr><td class="num" id="LN295">295</td><td class="line">                        <span class='keyword'>else</span></td></tr>
<tr><td class="num" id="LN296">296</td><td class="line">                        {</td></tr>
<tr><td class="num" id="LN297">297</td><td class="line">                            coveredRows[row] = <span class='keyword'>true</span>;</td></tr>
<tr><td class="num" id="LN298">298</td><td class="line">                            coveredColumns[starCol] = <span class='keyword'>false</span>;</td></tr>
<tr><td class="num" id="LN299">299</td><td class="line">                            zerosFound = <span class='keyword'>true</span>;</td></tr>
<tr><td class="num" id="LN300">300</td><td class="line">                            <span class='keyword'>break</span>;</td></tr>
<tr><td class="num" id="LN301">301</td><td class="line">                        }</td></tr>
<tr><td class="num" id="LN302">302</td><td class="line">                    }</td></tr>
<tr><td class="num" id="LN303">303</td><td class="line">    }</td></tr>
<tr><td class="num" id="LN304">304</td><td class="line"> </td></tr>
<tr><td class="num" id="LN305">305</td><td class="line">    <span class='comment'>/* move to step 5 */</span></td></tr>
<tr><td class="num" id="LN306">306</td><td class="line">    step5(assignment, distMatrix, starMatrix, newStarMatrix, primeMatrix, coveredColumns, coveredRows, nOfRows, nOfColumns, minDim);</td></tr>
<tr><td class="num" id="LN307">307</td><td class="line">}</td></tr>
<tr><td class="num" id="LN308">308</td><td class="line"> </td></tr>
<tr><td class="num" id="LN309">309</td><td class="line"><span class='comment'>/********************************************************/</span></td></tr>
<tr><td class="num" id="LN310">310</td><td class="line"><span class='keyword'>void</span> HungarianAlgorithm::step4(<span class='keyword'>int</span> *assignment, <span class='keyword'>double</span> *distMatrix, <span class='keyword'>bool</span> *starMatrix, <span class='keyword'>bool</span> *newStarMatrix, <span class='keyword'>bool</span> *primeMatrix, <span class='keyword'>bool</span> *coveredColumns, <span class='keyword'>bool</span> *coveredRows, <span class='keyword'>int</span> nOfRows, <span class='keyword'>int</span> nOfColumns, <span class='keyword'>int</span> minDim, <span class='keyword'>int</span> row, <span class='keyword'>int</span> col)</td></tr>
<tr><td class="num" id="LN311">311</td><td class="line">{</td></tr>
<tr><td class="num" id="LN312">312</td><td class="line">    <span class='keyword'>int</span> n, starRow, starCol, primeRow, primeCol;</td></tr>
<tr><td class="num" id="LN313">313</td><td class="line">    <span class='keyword'>int</span> nOfElements = nOfRows*nOfColumns;</td></tr>
<tr><td class="num" id="LN314">314</td><td class="line"> </td></tr>
<tr><td class="num" id="LN315">315</td><td class="line">    <span class='comment'>/* generate temporary copy of starMatrix */</span></td></tr>
<tr><td class="num" id="LN316">316</td><td class="line">    <span class='keyword'>for</span> (n = 0; n&lt;nOfElements; n++)</td></tr>
<tr><td class="num" id="LN317">317</td><td class="line">        newStarMatrix[n] = starMatrix[n];</td></tr>
<tr><td class="num" id="LN318">318</td><td class="line"> </td></tr>
<tr><td class="num" id="LN319">319</td><td class="line">    <span class='comment'>/* star current zero */</span></td></tr>
<tr><td class="num" id="LN320">320</td><td class="line">    newStarMatrix[row + nOfRows*col] = <span class='keyword'>true</span>;</td></tr>
<tr><td class="num" id="LN321">321</td><td class="line"> </td></tr>
<tr><td class="num" id="LN322">322</td><td class="line">    <span class='comment'>/* find starred zero in current column */</span></td></tr>
<tr><td class="num" id="LN323">323</td><td class="line">    starCol = col;</td></tr>
<tr><td class="num" id="LN324">324</td><td class="line">    <span class='keyword'>for</span> (starRow = 0; starRow&lt;nOfRows; starRow++)</td></tr>
<tr><td class="num" id="LN325">325</td><td class="line">        <span class='keyword'>if</span> (starMatrix[starRow + nOfRows*starCol])</td></tr>
<tr><td class="num" id="LN326">326</td><td class="line">            <span class='keyword'>break</span>;</td></tr>
<tr><td class="num" id="LN327">327</td><td class="line"> </td></tr>
<tr><td class="num" id="LN328">328</td><td class="line">    <span class='keyword'>while</span> (starRow&lt;nOfRows)</td></tr>
<tr><td class="num" id="LN329">329</td><td class="line">    {</td></tr>
<tr><td class="num" id="LN330">330</td><td class="line">        <span class='comment'>/* unstar the starred zero */</span></td></tr>
<tr><td class="num" id="LN331">331</td><td class="line">        newStarMatrix[starRow + nOfRows*starCol] = <span class='keyword'>false</span>;</td></tr>
<tr><td class="num" id="LN332">332</td><td class="line"> </td></tr>
<tr><td class="num" id="LN333">333</td><td class="line">        <span class='comment'>/* find primed zero in current row */</span></td></tr>
<tr><td class="num" id="LN334">334</td><td class="line">        primeRow = starRow;</td></tr>
<tr><td class="num" id="LN335">335</td><td class="line">        <span class='keyword'>for</span> (primeCol = 0; primeCol&lt;nOfColumns; primeCol++)</td></tr>
<tr><td class="num" id="LN336">336</td><td class="line">            <span class='keyword'>if</span> (primeMatrix[primeRow + nOfRows*primeCol])</td></tr>
<tr><td class="num" id="LN337">337</td><td class="line">                <span class='keyword'>break</span>;</td></tr>
<tr><td class="num" id="LN338">338</td><td class="line"> </td></tr>
<tr><td class="num" id="LN339">339</td><td class="line">        <span class='comment'>/* star the primed zero */</span></td></tr>
<tr><td class="num" id="LN340">340</td><td class="line">        newStarMatrix[primeRow + nOfRows*primeCol] = <span class='keyword'>true</span>;</td></tr>
<tr><td class="num" id="LN341">341</td><td class="line"> </td></tr>
<tr><td class="num" id="LN342">342</td><td class="line">        <span class='comment'>/* find starred zero in current column */</span></td></tr>
<tr><td class="num" id="LN343">343</td><td class="line">        starCol = primeCol;</td></tr>
<tr><td class="num" id="LN344">344</td><td class="line">        <span class='keyword'>for</span> (starRow = 0; starRow&lt;nOfRows; starRow++)</td></tr>
<tr><td class="num" id="LN345">345</td><td class="line">            <span class='keyword'>if</span> (starMatrix[starRow + nOfRows*starCol])</td></tr>
<tr><td class="num" id="LN346">346</td><td class="line">                <span class='keyword'>break</span>;</td></tr>
<tr><td class="num" id="LN347">347</td><td class="line">    }</td></tr>
<tr><td class="num" id="LN348">348</td><td class="line"> </td></tr>
<tr><td class="num" id="LN349">349</td><td class="line">    <span class='comment'>/* use temporary copy as new starMatrix */</span></td></tr>
<tr><td class="num" id="LN350">350</td><td class="line">    <span class='comment'>/* delete all primes, uncover all rows */</span></td></tr>
<tr><td class="num" id="LN351">351</td><td class="line">    <span class='keyword'>for</span> (n = 0; n&lt;nOfElements; n++)</td></tr>
<tr><td class="num" id="LN352">352</td><td class="line">    {</td></tr>
<tr><td class="num" id="LN353">353</td><td class="line">        primeMatrix[n] = <span class='keyword'>false</span>;</td></tr>
<tr><td class="num" id="LN354">354</td><td class="line">        starMatrix[n] = newStarMatrix[n];</td></tr>
<tr><td class="num" id="LN355">355</td><td class="line">    }</td></tr>
<tr><td class="num" id="LN356">356</td><td class="line">    <span class='keyword'>for</span> (n = 0; n&lt;nOfRows; n++)</td></tr>
<tr><td class="num" id="LN357">357</td><td class="line">        coveredRows[n] = <span class='keyword'>false</span>;</td></tr>
<tr><td class="num" id="LN358">358</td><td class="line"> </td></tr>
<tr><td class="num" id="LN359">359</td><td class="line">    <span class='comment'>/* move to step 2a */</span></td></tr>
<tr><td class="num" id="LN360">360</td><td class="line">    step2a(assignment, distMatrix, starMatrix, newStarMatrix, primeMatrix, coveredColumns, coveredRows, nOfRows, nOfColumns, minDim);</td></tr>
<tr><td class="num" id="LN361">361</td><td class="line">}</td></tr>
<tr><td class="num" id="LN362">362</td><td class="line"> </td></tr>
<tr><td class="num" id="LN363">363</td><td class="line"><span class='comment'>/********************************************************/</span></td></tr>
<tr><td class="num" id="LN364">364</td><td class="line"><span class='keyword'>void</span> HungarianAlgorithm::step5(<span class='keyword'>int</span> *assignment, <span class='keyword'>double</span> *distMatrix, <span class='keyword'>bool</span> *starMatrix, <span class='keyword'>bool</span> *newStarMatrix, <span class='keyword'>bool</span> *primeMatrix, <span class='keyword'>bool</span> *coveredColumns, <span class='keyword'>bool</span> *coveredRows, <span class='keyword'>int</span> nOfRows, <span class='keyword'>int</span> nOfColumns, <span class='keyword'>int</span> minDim)</td></tr>
<tr><td class="num" id="LN365">365</td><td class="line">{</td></tr>
<tr><td class="num" id="LN366">366</td><td class="line">    <span class='keyword'>double</span> h, value;</td></tr>
<tr><td class="num" id="LN367">367</td><td class="line">    <span class='keyword'>int</span> row, col;</td></tr>
<tr><td class="num" id="LN368">368</td><td class="line"> </td></tr>
<tr><td class="num" id="LN369">369</td><td class="line">    <span class='comment'>/* find smallest uncovered element h */</span></td></tr>
<tr><td class="num" id="LN370">370</td><td class="line">    h = <span class='macro'>DBL_MAX<span class='expansion'>1.7976931348623157e+308</span></span>;</td></tr>
<tr><td class="num" id="LN371">371</td><td class="line">    <span class='keyword'>for</span> (row = 0; row&lt;nOfRows; row++)</td></tr>
<tr><td class="num" id="LN372">372</td><td class="line">        <span class='keyword'>if</span> (!coveredRows[row])</td></tr>
<tr><td class="num" id="LN373">373</td><td class="line">            <span class='keyword'>for</span> (col = 0; col&lt;nOfColumns; col++)</td></tr>
<tr><td class="num" id="LN374">374</td><td class="line">                <span class='keyword'>if</span> (!coveredColumns[col])</td></tr>
<tr><td class="num" id="LN375">375</td><td class="line">                {</td></tr>
<tr><td class="num" id="LN376">376</td><td class="line">                    value = distMatrix[row + nOfRows*col];</td></tr>
<tr><td class="num" id="LN377">377</td><td class="line">                    <span class='keyword'>if</span> (value &lt; h)</td></tr>
<tr><td class="num" id="LN378">378</td><td class="line">                        h = value;</td></tr>
<tr><td class="num" id="LN379">379</td><td class="line">                }</td></tr>
<tr><td class="num" id="LN380">380</td><td class="line"> </td></tr>
<tr><td class="num" id="LN381">381</td><td class="line">    <span class='comment'>/* add h to each covered row */</span></td></tr>
<tr><td class="num" id="LN382">382</td><td class="line">    <span class='keyword'>for</span> (row = 0; row&lt;nOfRows; row++)</td></tr>
<tr><td class="num" id="LN383">383</td><td class="line">        <span class='keyword'>if</span> (coveredRows[row])</td></tr>
<tr><td class="num" id="LN384">384</td><td class="line">            <span class='keyword'>for</span> (col = 0; col&lt;nOfColumns; col++)</td></tr>
<tr><td class="num" id="LN385">385</td><td class="line">                distMatrix[row + nOfRows*col] += h;</td></tr>
<tr><td class="num" id="LN386">386</td><td class="line"> </td></tr>
<tr><td class="num" id="LN387">387</td><td class="line">    <span class='comment'>/* subtract h from each uncovered column */</span></td></tr>
<tr><td class="num" id="LN388">388</td><td class="line">    <span class='keyword'>for</span> (col = 0; col&lt;nOfColumns; col++)</td></tr>
<tr><td class="num" id="LN389">389</td><td class="line">        <span class='keyword'>if</span> (!coveredColumns[col])</td></tr>
<tr><td class="num" id="LN390">390</td><td class="line">            <span class='keyword'>for</span> (row = 0; row&lt;nOfRows; row++)</td></tr>
<tr><td class="num" id="LN391">391</td><td class="line">                distMatrix[row + nOfRows*col] -= h;</td></tr>
<tr><td class="num" id="LN392">392</td><td class="line"> </td></tr>
<tr><td class="num" id="LN393">393</td><td class="line">    <span class='comment'>/* move to step 3 */</span></td></tr>
<tr><td class="num" id="LN394">394</td><td class="line">    step3(assignment, distMatrix, starMatrix, newStarMatrix, primeMatrix, coveredColumns, coveredRows, nOfRows, nOfColumns, minDim);</td></tr>
<tr><td class="num" id="LN395">395</td><td class="line">}</td></tr></table></body></html>
ganleiboy commented 2 years ago

It shows exactly the conditions in which the bug occurs:

So how to solve the bug?