mcximing / hungarian-algorithm-cpp Goto Github PK
View Code? Open in Web Editor NEWA C++ wrapper for a hungarian algorithm implementation
License: BSD 2-Clause "Simplified" License
hungarian-algorithm-cpp's People
Contributors
Stargazers
Watchers
Forkers
caomw reunanen zhongshijun amirhomayoun josercadena guangshengshi abuchegger conanhung pikamonvvs biswajitghosh98 mzahana 0gwang lorenzorossi1998 platon3344 lishuaiyin02 hongchow dendisuhubdy lhc610github jjwilke deepdriving janucaria hengzhangmiivii ks3rr mrxuehb gaussian37 aszuhri87 xiaoliangabc zhangpiu luthfikaindra19 micricket jixingwu siyeopyoon 5l1v3r1 tom13133 jovialio ankilp worksquad sddongxh lufffffeng cadcorp mloskot dashark cram3r95 yanhongzhou1994 emrahgultekin deeptoby zildj1an mithundiddi hehewang625327 tt22ty mbsm lethep khle08 xnc jingw2021 lyf7115 mogowlj pandinosaurus heedon-yoon mriechmann1 qianqian121 ismailsunni xuelianjie catsana1231 strattist ccicconetti glc12125 zoeveryday badal244 liuzhenboo yvhaoliu weilaweila navidnasyry josiah0191 pangchao-git wangruizhong shinetzh mkrupczak3 itberrios haydenai qian5683 fsc1023 marsbzp haoli-tukl ella-maisanchez liufqing littlesquirrel2017 bobblehead49 kwanghoon-kim wang-nb windwing2016 imcjhungarian-algorithm-cpp's Issues
DistMatrix Zero Check
The program will crash if a DistMatrix with size zero is passed to HungarianAlgorithm::Solve.
Fix for line 28:
if ((int) nRows .size() == 0) { return -1; }
Assigned value is garbage or undefined
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 <stdlib.h></span></td></tr>
<tr><td class="num" id="LN13">13</td><td class="line"><span class='directive'>#include <cfloat> // for DBL_MAX</span></td></tr>
<tr><td class="num" id="LN14">14</td><td class="line"><span class='directive'>#include <cmath> // 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 <vector<<span class='keyword'>double</span>> >& DistMatrix, vector<<span class='keyword'>int</span>>& 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 < 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 < 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, &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 < 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<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 >= 'nOfRows'</td><td><div class="PathNav"><a href="#Path2" title="Next event (2)">→</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)">←</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)">→</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<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)">←</a></div></td></td><td>Assuming 'row' is >= 'nOfElements'</td><td><div class="PathNav"><a href="#Path4" title="Next event (4)">→</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)">←</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)">→</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 < 0)</td></tr>
<tr><td class="num" id="LN79">79</td><td class="line"> cerr << <span class='string_literal'>"All matrix elements have to be non-negative."</span> << 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 <= 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)">←</a></div></td></td><td>Taking false branch</td><td><div class="PathNav"><a href="#Path6" title="Next event (6)">→</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<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 < 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 < 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 < 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<nOfRows; row++)</td></tr>
<tr><td class="num" id="LN121">121</td><td class="line"> <span class='keyword'>for</span> (col = 0; col<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]) < <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 > 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<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)">←</a></div></td></td><td>Assuming 'col' is < 'nOfColumns'</td><td><div class="PathNav"><a href="#Path7" title="Next event (7)">→</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)">←</a></div></td></td><td>Loop condition is true. Entering loop body</td><td><div class="PathNav"><a href="#EndPath" title="Next event (8)">→</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)">←</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 < 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 < 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 < 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<nOfColumns; col++)</td></tr>
<tr><td class="num" id="LN156">156</td><td class="line"> <span class='keyword'>for</span> (row = 0; row<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]) < <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<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<nOfRows; row++)</td></tr>
<tr><td class="num" id="LN193">193</td><td class="line"> <span class='keyword'>for</span> (col = 0; col<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<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 >= 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<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 < 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<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<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<nOfRows; row++)</td></tr>
<tr><td class="num" id="LN279">279</td><td class="line"> <span class='keyword'>if</span> ((!coveredRows[row]) && (fabs(distMatrix[row + nOfRows*col]) < <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<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<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<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<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<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<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<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<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<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<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 < 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<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<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<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<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>
No exception Handler when all Infinity row exist in DistMatrix
When all Infinity row exists in DistMatrix, program gives error while running, no exception handler for that case.
It should do no assignment when all the distances are Infinity for that job/task .
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.