Google Git
Sign in
apache / hbase-site / 2c46013158a253c8fb93c7b7bef94eb5bfdc9a3f / . / devapidocs / org / apache / hadoop / hbase / util / MunkresAssignment.html
blob: dd0da197ceef68be265de8763b04eff4873f96e7 [file] [log] [blame]
<!DOCTYPE HTML>
<html lang="en">
<head>
<!-- Generated by javadoc (17) -->
<title>MunkresAssignment (Apache HBase 4.0.0-alpha-1-SNAPSHOT API)</title>
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="description" content="declaration: package: org.apache.hadoop.hbase.util, class: MunkresAssignment">
<meta name="generator" content="javadoc/ClassWriterImpl">
<link rel="stylesheet" type="text/css" href="../../../../../stylesheet.css" title="Style">
<link rel="stylesheet" type="text/css" href="../../../../../script-dir/jquery-ui.min.css" title="Style">
<link rel="stylesheet" type="text/css" href="../../../../../jquery-ui.overrides.css" title="Style">
<script type="text/javascript" src="../../../../../script.js"></script>
<script type="text/javascript" src="../../../../../script-dir/jquery-3.6.1.min.js"></script>
<script type="text/javascript" src="../../../../../script-dir/jquery-ui.min.js"></script>
</head>
<body class="class-declaration-page">
<script type="text/javascript">var evenRowColor = "even-row-color";
var oddRowColor = "odd-row-color";
var tableTab = "table-tab";
var activeTableTab = "active-table-tab";
var pathtoroot = "../../../../../";
loadScripts(document, 'script');</script>
<noscript>
<div>JavaScript is disabled on your browser.</div>
</noscript>
<div class="flex-box">
<header role="banner" class="flex-header">
<nav role="navigation">
<!-- ========= START OF TOP NAVBAR ======= -->
<div class="top-nav" id="navbar-top">
<div class="skip-nav"><a href="#skip-navbar-top" title="Skip navigation links">Skip navigation links</a></div>
<ul id="navbar-top-firstrow" class="nav-list" title="Navigation">
<li><a href="../../../../../index.html">Overview</a></li>
<li><a href="package-summary.html">Package</a></li>
<li class="nav-bar-cell1-rev">Class</li>
<li><a href="class-use/MunkresAssignment.html">Use</a></li>
<li><a href="package-tree.html">Tree</a></li>
<li><a href="../../../../../deprecated-list.html">Deprecated</a></li>
<li><a href="../../../../../index-all.html">Index</a></li>
<li><a href="../../../../../help-doc.html#class">Help</a></li>
</ul>
</div>
<div class="sub-nav">
<div>
<ul class="sub-nav-list">
<li>Summary:&nbsp;</li>
<li>Nested&nbsp;|&nbsp;</li>
<li><a href="#field-summary">Field</a>&nbsp;|&nbsp;</li>
<li><a href="#constructor-summary">Constr</a>&nbsp;|&nbsp;</li>
<li><a href="#method-summary">Method</a></li>
</ul>
<ul class="sub-nav-list">
<li>Detail:&nbsp;</li>
<li><a href="#field-detail">Field</a>&nbsp;|&nbsp;</li>
<li><a href="#constructor-detail">Constr</a>&nbsp;|&nbsp;</li>
<li><a href="#method-detail">Method</a></li>
</ul>
</div>
<div class="nav-list-search"><label for="search-input">SEARCH:</label>
<input type="text" id="search-input" value="search" disabled="disabled">
<input type="reset" id="reset-button" value="reset" disabled="disabled">
</div>
</div>
<!-- ========= END OF TOP NAVBAR ========= -->
<span class="skip-nav" id="skip-navbar-top"></span></nav>
</header>
<div class="flex-content">
<main role="main">
<!-- ======== START OF CLASS DATA ======== -->
<div class="header">
<div class="sub-title"><span class="package-label-in-type">Package</span>&nbsp;<a href="package-summary.html">org.apache.hadoop.hbase.util</a></div>
<h1 title="Class MunkresAssignment" class="title">Class MunkresAssignment</h1>
</div>
<div class="inheritance" title="Inheritance Tree"><a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Object.html" title="class or interface in java.lang" class="external-link">java.lang.Object</a>
<div class="inheritance">org.apache.hadoop.hbase.util.MunkresAssignment</div>
</div>
<section class="class-description" id="class-description">
<hr>
<div class="type-signature"><span class="annotations">@Private
</span><span class="modifiers">public class </span><span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-33">MunkresAssignment</a></span>
<span class="extends-implements">extends <a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Object.html" title="class or interface in java.lang" class="external-link">Object</a></span></div>
<div class="block">Computes the optimal (minimal cost) assignment of jobs to workers (or other analogous) concepts
given a cost matrix of each pair of job and worker, using the algorithm by James Munkres in
"Algorithms for the Assignment and Transportation Problems", with additional optimizations as
described by Jin Kue Wong in "A New Implementation of an Algorithm for the Optimal Assignment
Problem: An Improved Version of Munkres' Algorithm". The algorithm runs in O(n^3) time and need
O(n^2) auxiliary space where n is the number of jobs or workers, whichever is greater.</div>
</section>
<section class="summary">
<ul class="summary-list">
<!-- =========== FIELD SUMMARY =========== -->
<li>
<section class="field-summary" id="field-summary">
<h2>Field Summary</h2>
<div class="caption"><span>Fields</span></div>
<div class="summary-table three-column-summary">
<div class="table-header col-first">Modifier and Type</div>
<div class="table-header col-second">Field</div>
<div class="table-header col-last">Description</div>
<div class="col-first even-row-color"><code>private int[]</code></div>
<div class="col-second even-row-color"><code><a href="#assignments" class="member-name-link">assignments</a></code></div>
<div class="col-last even-row-color">&nbsp;</div>
<div class="col-first odd-row-color"><code>private float[]</code></div>
<div class="col-second odd-row-color"><code><a href="#colAdjust" class="member-name-link">colAdjust</a></code></div>
<div class="col-last odd-row-color">&nbsp;</div>
<div class="col-first even-row-color"><code>private final int</code></div>
<div class="col-second even-row-color"><code><a href="#cols" class="member-name-link">cols</a></code></div>
<div class="col-last even-row-color">&nbsp;</div>
<div class="col-first odd-row-color"><code>private boolean[]</code></div>
<div class="col-second odd-row-color"><code><a href="#colsCovered" class="member-name-link">colsCovered</a></code></div>
<div class="col-last odd-row-color">&nbsp;</div>
<div class="col-first even-row-color"><code>private float[][]</code></div>
<div class="col-second even-row-color"><code><a href="#cost" class="member-name-link">cost</a></code></div>
<div class="col-last even-row-color">&nbsp;</div>
<div class="col-first odd-row-color"><code>private float[]</code></div>
<div class="col-second odd-row-color"><code><a href="#leastInRow" class="member-name-link">leastInRow</a></code></div>
<div class="col-last odd-row-color">&nbsp;</div>
<div class="col-first even-row-color"><code>private int[]</code></div>
<div class="col-second even-row-color"><code><a href="#leastInRowIndex" class="member-name-link">leastInRowIndex</a></code></div>
<div class="col-last even-row-color">&nbsp;</div>
<div class="col-first odd-row-color"><code>private byte[][]</code></div>
<div class="col-second odd-row-color"><code><a href="#mask" class="member-name-link">mask</a></code></div>
<div class="col-last odd-row-color">&nbsp;</div>
<div class="col-first even-row-color"><code>private static final byte</code></div>
<div class="col-second even-row-color"><code><a href="#NONE" class="member-name-link">NONE</a></code></div>
<div class="col-last even-row-color">&nbsp;</div>
<div class="col-first odd-row-color"><code>private <a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Deque.html" title="class or interface in java.util" class="external-link">Deque</a>&lt;<a href="Pair.html" title="class in org.apache.hadoop.hbase.util">Pair</a>&lt;<a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Integer.html" title="class or interface in java.lang" class="external-link">Integer</a>,<wbr><a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Integer.html" title="class or interface in java.lang" class="external-link">Integer</a>&gt;&gt;</code></div>
<div class="col-second odd-row-color"><code><a href="#path" class="member-name-link">path</a></code></div>
<div class="col-last odd-row-color">&nbsp;</div>
<div class="col-first even-row-color"><code>private static final byte</code></div>
<div class="col-second even-row-color"><code><a href="#PRIME" class="member-name-link">PRIME</a></code></div>
<div class="col-last even-row-color">&nbsp;</div>
<div class="col-first odd-row-color"><code>private float[]</code></div>
<div class="col-second odd-row-color"><code><a href="#rowAdjust" class="member-name-link">rowAdjust</a></code></div>
<div class="col-last odd-row-color">&nbsp;</div>
<div class="col-first even-row-color"><code>private final int</code></div>
<div class="col-second even-row-color"><code><a href="#rows" class="member-name-link">rows</a></code></div>
<div class="col-last even-row-color">&nbsp;</div>
<div class="col-first odd-row-color"><code>private boolean[]</code></div>
<div class="col-second odd-row-color"><code><a href="#rowsCovered" class="member-name-link">rowsCovered</a></code></div>
<div class="col-last odd-row-color">&nbsp;</div>
<div class="col-first even-row-color"><code>private static final byte</code></div>
<div class="col-second even-row-color"><code><a href="#STAR" class="member-name-link">STAR</a></code></div>
<div class="col-last even-row-color">&nbsp;</div>
<div class="col-first odd-row-color"><code>private final boolean</code></div>
<div class="col-second odd-row-color"><code><a href="#transposed" class="member-name-link">transposed</a></code></div>
<div class="col-last odd-row-color">&nbsp;</div>
</div>
</section>
</li>
<!-- ======== CONSTRUCTOR SUMMARY ======== -->
<li>
<section class="constructor-summary" id="constructor-summary">
<h2>Constructor Summary</h2>
<div class="caption"><span>Constructors</span></div>
<div class="summary-table two-column-summary">
<div class="table-header col-first">Constructor</div>
<div class="table-header col-last">Description</div>
<div class="col-constructor-name even-row-color"><code><a href="#%3Cinit%3E(float%5B%5D%5B%5D)" class="member-name-link">MunkresAssignment</a><wbr>(float[][]&nbsp;costMatrix)</code></div>
<div class="col-last even-row-color">
<div class="block">Construct a new problem instance with the specified cost matrix.</div>
</div>
</div>
</section>
</li>
<!-- ========== METHOD SUMMARY =========== -->
<li>
<section class="method-summary" id="method-summary">
<h2>Method Summary</h2>
<div id="method-summary-table">
<div class="table-tabs" role="tablist" aria-orientation="horizontal"><button id="method-summary-table-tab0" role="tab" aria-selected="true" aria-controls="method-summary-table.tabpanel" tabindex="0" onkeydown="switchTab(event)" onclick="show('method-summary-table', 'method-summary-table', 3)" class="active-table-tab">All Methods</button><button id="method-summary-table-tab2" role="tab" aria-selected="false" aria-controls="method-summary-table.tabpanel" tabindex="-1" onkeydown="switchTab(event)" onclick="show('method-summary-table', 'method-summary-table-tab2', 3)" class="table-tab">Instance Methods</button><button id="method-summary-table-tab4" role="tab" aria-selected="false" aria-controls="method-summary-table.tabpanel" tabindex="-1" onkeydown="switchTab(event)" onclick="show('method-summary-table', 'method-summary-table-tab4', 3)" class="table-tab">Concrete Methods</button></div>
<div id="method-summary-table.tabpanel" role="tabpanel">
<div class="summary-table three-column-summary" aria-labelledby="method-summary-table-tab0">
<div class="table-header col-first">Modifier and Type</div>
<div class="table-header col-second">Method</div>
<div class="table-header col-last">Description</div>
<div class="col-first even-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4"><code>private <a href="Pair.html" title="class in org.apache.hadoop.hbase.util">Pair</a>&lt;<a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Integer.html" title="class or interface in java.lang" class="external-link">Integer</a>,<wbr><a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Integer.html" title="class or interface in java.lang" class="external-link">Integer</a>&gt;</code></div>
<div class="col-second even-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4"><code><a href="#findUncoveredZero()" class="member-name-link">findUncoveredZero</a>()</code></div>
<div class="col-last even-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4">
<div class="block">Find a zero cost assignment which is not covered.</div>
</div>
<div class="col-first odd-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4"><code>private void</code></div>
<div class="col-second odd-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4"><code><a href="#preliminaries()" class="member-name-link">preliminaries</a>()</code></div>
<div class="col-last odd-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4">
<div class="block">Corresponds to the "preliminaries" step of the original algorithm.</div>
</div>
<div class="col-first even-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4"><code>private <a href="Pair.html" title="class in org.apache.hadoop.hbase.util">Pair</a>&lt;<a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Integer.html" title="class or interface in java.lang" class="external-link">Integer</a>,<wbr><a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Integer.html" title="class or interface in java.lang" class="external-link">Integer</a>&gt;</code></div>
<div class="col-second even-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4"><code><a href="#primeInRow(int)" class="member-name-link">primeInRow</a><wbr>(int&nbsp;r)</code></div>
<div class="col-last even-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4">
<div class="block">Find a primed zero in the specified row.</div>
</div>
<div class="col-first odd-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4"><code>int[]</code></div>
<div class="col-second odd-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4"><code><a href="#solve()" class="member-name-link">solve</a>()</code></div>
<div class="col-last odd-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4">
<div class="block">Get the optimal assignments.</div>
</div>
<div class="col-first even-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4"><code>private <a href="Pair.html" title="class in org.apache.hadoop.hbase.util">Pair</a>&lt;<a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Integer.html" title="class or interface in java.lang" class="external-link">Integer</a>,<wbr><a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Integer.html" title="class or interface in java.lang" class="external-link">Integer</a>&gt;</code></div>
<div class="col-second even-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4"><code><a href="#starInCol(int)" class="member-name-link">starInCol</a><wbr>(int&nbsp;c)</code></div>
<div class="col-last even-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4">
<div class="block">Find a starred zero in the specified column.</div>
</div>
<div class="col-first odd-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4"><code>private <a href="Pair.html" title="class in org.apache.hadoop.hbase.util">Pair</a>&lt;<a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Integer.html" title="class or interface in java.lang" class="external-link">Integer</a>,<wbr><a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Integer.html" title="class or interface in java.lang" class="external-link">Integer</a>&gt;</code></div>
<div class="col-second odd-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4"><code><a href="#starInRow(int)" class="member-name-link">starInRow</a><wbr>(int&nbsp;r)</code></div>
<div class="col-last odd-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4">
<div class="block">Find a starred zero in a specified row.</div>
</div>
<div class="col-first even-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4"><code>private boolean</code></div>
<div class="col-second even-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4"><code><a href="#stepOne()" class="member-name-link">stepOne</a>()</code></div>
<div class="col-last even-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4">
<div class="block">Corresponds to step 1 of the original algorithm.</div>
</div>
<div class="col-first odd-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4"><code>private void</code></div>
<div class="col-second odd-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4"><code><a href="#stepThree()" class="member-name-link">stepThree</a>()</code></div>
<div class="col-last odd-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4">
<div class="block">Corresponds to step 3 of the original algorithm.</div>
</div>
<div class="col-first even-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4"><code>private void</code></div>
<div class="col-second even-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4"><code><a href="#stepTwo()" class="member-name-link">stepTwo</a>()</code></div>
<div class="col-last even-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4">
<div class="block">Corresponds to step 2 of the original algorithm.</div>
</div>
<div class="col-first odd-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4"><code>private boolean</code></div>
<div class="col-second odd-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4"><code><a href="#testIsDone()" class="member-name-link">testIsDone</a>()</code></div>
<div class="col-last odd-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4">
<div class="block">Test whether the algorithm is done, i.e.</div>
</div>
<div class="col-first even-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4"><code>private void</code></div>
<div class="col-second even-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4"><code><a href="#updateMin(int,int)" class="member-name-link">updateMin</a><wbr>(int&nbsp;row,
int&nbsp;col)</code></div>
<div class="col-last even-row-color method-summary-table method-summary-table-tab2 method-summary-table-tab4">
<div class="block">A specified row has become covered, and a specified column has become uncovered.</div>
</div>
</div>
</div>
</div>
<div class="inherited-list">
<h3 id="methods-inherited-from-class-java.lang.Object">Methods inherited from class&nbsp;java.lang.<a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Object.html" title="class or interface in java.lang" class="external-link">Object</a></h3>
<code><a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Object.html#clone()" title="class or interface in java.lang" class="external-link">clone</a>, <a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Object.html#equals(java.lang.Object)" title="class or interface in java.lang" class="external-link">equals</a>, <a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Object.html#finalize()" title="class or interface in java.lang" class="external-link">finalize</a>, <a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Object.html#getClass()" title="class or interface in java.lang" class="external-link">getClass</a>, <a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Object.html#hashCode()" title="class or interface in java.lang" class="external-link">hashCode</a>, <a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Object.html#notify()" title="class or interface in java.lang" class="external-link">notify</a>, <a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Object.html#notifyAll()" title="class or interface in java.lang" class="external-link">notifyAll</a>, <a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Object.html#toString()" title="class or interface in java.lang" class="external-link">toString</a>, <a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Object.html#wait()" title="class or interface in java.lang" class="external-link">wait</a>, <a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Object.html#wait(long)" title="class or interface in java.lang" class="external-link">wait</a>, <a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Object.html#wait(long,int)" title="class or interface in java.lang" class="external-link">wait</a></code></div>
</section>
</li>
</ul>
</section>
<section class="details">
<ul class="details-list">
<!-- ============ FIELD DETAIL =========== -->
<li>
<section class="field-details" id="field-detail">
<h2>Field Details</h2>
<ul class="member-list">
<li>
<section class="detail" id="NONE">
<h3>NONE</h3>
<div class="member-signature"><span class="modifiers">private static final</span>&nbsp;<span class="return-type">byte</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-40">NONE</a></span></div>
<dl class="notes">
<dt>See Also:</dt>
<dd>
<ul class="see-list">
<li><a href="../../../../../constant-values.html#org.apache.hadoop.hbase.util.MunkresAssignment.NONE">Constant Field Values</a></li>
</ul>
</dd>
</dl>
</section>
</li>
<li>
<section class="detail" id="STAR">
<h3>STAR</h3>
<div class="member-signature"><span class="modifiers">private static final</span>&nbsp;<span class="return-type">byte</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-41">STAR</a></span></div>
<dl class="notes">
<dt>See Also:</dt>
<dd>
<ul class="see-list">
<li><a href="../../../../../constant-values.html#org.apache.hadoop.hbase.util.MunkresAssignment.STAR">Constant Field Values</a></li>
</ul>
</dd>
</dl>
</section>
</li>
<li>
<section class="detail" id="PRIME">
<h3>PRIME</h3>
<div class="member-signature"><span class="modifiers">private static final</span>&nbsp;<span class="return-type">byte</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-42">PRIME</a></span></div>
<dl class="notes">
<dt>See Also:</dt>
<dd>
<ul class="see-list">
<li><a href="../../../../../constant-values.html#org.apache.hadoop.hbase.util.MunkresAssignment.PRIME">Constant Field Values</a></li>
</ul>
</dd>
</dl>
</section>
</li>
<li>
<section class="detail" id="transposed">
<h3>transposed</h3>
<div class="member-signature"><span class="modifiers">private final</span>&nbsp;<span class="return-type">boolean</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-48">transposed</a></span></div>
</section>
</li>
<li>
<section class="detail" id="rows">
<h3>rows</h3>
<div class="member-signature"><span class="modifiers">private final</span>&nbsp;<span class="return-type">int</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-51">rows</a></span></div>
</section>
</li>
<li>
<section class="detail" id="cols">
<h3>cols</h3>
<div class="member-signature"><span class="modifiers">private final</span>&nbsp;<span class="return-type">int</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-54">cols</a></span></div>
</section>
</li>
<li>
<section class="detail" id="cost">
<h3>cost</h3>
<div class="member-signature"><span class="modifiers">private</span>&nbsp;<span class="return-type">float[][]</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-57">cost</a></span></div>
</section>
</li>
<li>
<section class="detail" id="mask">
<h3>mask</h3>
<div class="member-signature"><span class="modifiers">private</span>&nbsp;<span class="return-type">byte[][]</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-60">mask</a></span></div>
</section>
</li>
<li>
<section class="detail" id="rowsCovered">
<h3>rowsCovered</h3>
<div class="member-signature"><span class="modifiers">private</span>&nbsp;<span class="return-type">boolean[]</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-63">rowsCovered</a></span></div>
</section>
</li>
<li>
<section class="detail" id="colsCovered">
<h3>colsCovered</h3>
<div class="member-signature"><span class="modifiers">private</span>&nbsp;<span class="return-type">boolean[]</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-66">colsCovered</a></span></div>
</section>
</li>
<li>
<section class="detail" id="path">
<h3>path</h3>
<div class="member-signature"><span class="modifiers">private</span>&nbsp;<span class="return-type"><a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Deque.html" title="class or interface in java.util" class="external-link">Deque</a>&lt;<a href="Pair.html" title="class in org.apache.hadoop.hbase.util">Pair</a>&lt;<a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Integer.html" title="class or interface in java.lang" class="external-link">Integer</a>,<wbr><a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Integer.html" title="class or interface in java.lang" class="external-link">Integer</a>&gt;&gt;</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-69">path</a></span></div>
</section>
</li>
<li>
<section class="detail" id="assignments">
<h3>assignments</h3>
<div class="member-signature"><span class="modifiers">private</span>&nbsp;<span class="return-type">int[]</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-76">assignments</a></span></div>
</section>
</li>
<li>
<section class="detail" id="leastInRow">
<h3>leastInRow</h3>
<div class="member-signature"><span class="modifiers">private</span>&nbsp;<span class="return-type">float[]</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-81">leastInRow</a></span></div>
</section>
</li>
<li>
<section class="detail" id="leastInRowIndex">
<h3>leastInRowIndex</h3>
<div class="member-signature"><span class="modifiers">private</span>&nbsp;<span class="return-type">int[]</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-82">leastInRowIndex</a></span></div>
</section>
</li>
<li>
<section class="detail" id="rowAdjust">
<h3>rowAdjust</h3>
<div class="member-signature"><span class="modifiers">private</span>&nbsp;<span class="return-type">float[]</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-83">rowAdjust</a></span></div>
</section>
</li>
<li>
<section class="detail" id="colAdjust">
<h3>colAdjust</h3>
<div class="member-signature"><span class="modifiers">private</span>&nbsp;<span class="return-type">float[]</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-84">colAdjust</a></span></div>
</section>
</li>
</ul>
</section>
</li>
<!-- ========= CONSTRUCTOR DETAIL ======== -->
<li>
<section class="constructor-details" id="constructor-detail">
<h2>Constructor Details</h2>
<ul class="member-list">
<li>
<section class="detail" id="&lt;init&gt;(float[][])">
<h3>MunkresAssignment</h3>
<div class="member-signature"><span class="modifiers">public</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-92">MunkresAssignment</a></span><wbr><span class="parameters">(float[][]&nbsp;costMatrix)</span></div>
<div class="block">Construct a new problem instance with the specified cost matrix. The cost matrix must be
rectangular, though not necessarily square. If one dimension is greater than the other, some
elements in the greater dimension will not be assigned. The input cost matrix will not be
modified.</div>
</section>
</li>
</ul>
</section>
</li>
<!-- ============ METHOD DETAIL ========== -->
<li>
<section class="method-details" id="method-detail">
<h2>Method Details</h2>
<ul class="member-list">
<li>
<section class="detail" id="solve()">
<h3>solve</h3>
<div class="member-signature"><span class="modifiers">public</span>&nbsp;<span class="return-type">int[]</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-151">solve</a></span>()</div>
<div class="block">Get the optimal assignments. The returned array will have the same number of elements as the
number of elements as the number of rows in the input cost matrix. Each element will indicate
which column should be assigned to that row or -1 if no column should be assigned, i.e. if
result[i] = j then row i should be assigned to column j. Subsequent invocations of this method
will simply return the same object without additional computation.</div>
<dl class="notes">
<dt>Returns:</dt>
<dd>an array with the optimal assignments</dd>
</dl>
</section>
</li>
<li>
<section class="detail" id="preliminaries()">
<h3>preliminaries</h3>
<div class="member-signature"><span class="modifiers">private</span>&nbsp;<span class="return-type">void</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-213">preliminaries</a></span>()</div>
<div class="block">Corresponds to the "preliminaries" step of the original algorithm. Guarantees that the matrix
is an equivalent non-negative matrix with at least one zero in each row.</div>
</section>
</li>
<li>
<section class="detail" id="testIsDone()">
<h3>testIsDone</h3>
<div class="member-signature"><span class="modifiers">private</span>&nbsp;<span class="return-type">boolean</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-248">testIsDone</a></span>()</div>
<div class="block">Test whether the algorithm is done, i.e. we have the optimal assignment. This occurs when there
is exactly one starred zero in each row.</div>
<dl class="notes">
<dt>Returns:</dt>
<dd>true if the algorithm is done</dd>
</dl>
</section>
</li>
<li>
<section class="detail" id="stepOne()">
<h3>stepOne</h3>
<div class="member-signature"><span class="modifiers">private</span>&nbsp;<span class="return-type">boolean</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-300">stepOne</a></span>()</div>
<div class="block">Corresponds to step 1 of the original algorithm.</div>
<dl class="notes">
<dt>Returns:</dt>
<dd>false if all zeroes are covered</dd>
</dl>
</section>
</li>
<li>
<section class="detail" id="stepTwo()">
<h3>stepTwo</h3>
<div class="member-signature"><span class="modifiers">private</span>&nbsp;<span class="return-type">void</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-334">stepTwo</a></span>()</div>
<div class="block">Corresponds to step 2 of the original algorithm.</div>
</section>
</li>
<li>
<section class="detail" id="stepThree()">
<h3>stepThree</h3>
<div class="member-signature"><span class="modifiers">private</span>&nbsp;<span class="return-type">void</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-378">stepThree</a></span>()</div>
<div class="block">Corresponds to step 3 of the original algorithm.</div>
</section>
</li>
<li>
<section class="detail" id="findUncoveredZero()">
<h3>findUncoveredZero</h3>
<div class="member-signature"><span class="modifiers">private</span>&nbsp;<span class="return-type"><a href="Pair.html" title="class in org.apache.hadoop.hbase.util">Pair</a>&lt;<a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Integer.html" title="class or interface in java.lang" class="external-link">Integer</a>,<wbr><a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Integer.html" title="class or interface in java.lang" class="external-link">Integer</a>&gt;</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-429">findUncoveredZero</a></span>()</div>
<div class="block">Find a zero cost assignment which is not covered. If there are no zero cost assignments which
are uncovered, then null will be returned.</div>
<dl class="notes">
<dt>Returns:</dt>
<dd>pair of row and column indices of an uncovered zero or null</dd>
</dl>
</section>
</li>
<li>
<section class="detail" id="updateMin(int,int)">
<h3>updateMin</h3>
<div class="member-signature"><span class="modifiers">private</span>&nbsp;<span class="return-type">void</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-444">updateMin</a></span><wbr><span class="parameters">(int&nbsp;row,
int&nbsp;col)</span></div>
<div class="block">A specified row has become covered, and a specified column has become uncovered. The least
value per row may need to be updated.</div>
<dl class="notes">
<dt>Parameters:</dt>
<dd><code>row</code> - the index of the row which was just covered</dd>
<dd><code>col</code> - the index of the column which was just uncovered</dd>
</dl>
</section>
</li>
<li>
<section class="detail" id="starInRow(int)">
<h3>starInRow</h3>
<div class="member-signature"><span class="modifiers">private</span>&nbsp;<span class="return-type"><a href="Pair.html" title="class in org.apache.hadoop.hbase.util">Pair</a>&lt;<a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Integer.html" title="class or interface in java.lang" class="external-link">Integer</a>,<wbr><a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Integer.html" title="class or interface in java.lang" class="external-link">Integer</a>&gt;</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-466">starInRow</a></span><wbr><span class="parameters">(int&nbsp;r)</span></div>
<div class="block">Find a starred zero in a specified row. If there are no starred zeroes in the specified row,
then null will be returned.</div>
<dl class="notes">
<dt>Parameters:</dt>
<dd><code>r</code> - the index of the row to be searched</dd>
<dt>Returns:</dt>
<dd>pair of row and column indices of starred zero or null</dd>
</dl>
</section>
</li>
<li>
<section class="detail" id="starInCol(int)">
<h3>starInCol</h3>
<div class="member-signature"><span class="modifiers">private</span>&nbsp;<span class="return-type"><a href="Pair.html" title="class in org.apache.hadoop.hbase.util">Pair</a>&lt;<a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Integer.html" title="class or interface in java.lang" class="external-link">Integer</a>,<wbr><a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Integer.html" title="class or interface in java.lang" class="external-link">Integer</a>&gt;</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-481">starInCol</a></span><wbr><span class="parameters">(int&nbsp;c)</span></div>
<div class="block">Find a starred zero in the specified column. If there are no starred zeroes in the specified
row, then null will be returned.</div>
<dl class="notes">
<dt>Parameters:</dt>
<dd><code>c</code> - the index of the column to be searched</dd>
<dt>Returns:</dt>
<dd>pair of row and column indices of starred zero or null</dd>
</dl>
</section>
</li>
<li>
<section class="detail" id="primeInRow(int)">
<h3>primeInRow</h3>
<div class="member-signature"><span class="modifiers">private</span>&nbsp;<span class="return-type"><a href="Pair.html" title="class in org.apache.hadoop.hbase.util">Pair</a>&lt;<a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Integer.html" title="class or interface in java.lang" class="external-link">Integer</a>,<wbr><a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Integer.html" title="class or interface in java.lang" class="external-link">Integer</a>&gt;</span>&nbsp;<span class="element-name"><a href="../../../../../src-html/org/apache/hadoop/hbase/util/MunkresAssignment.html#line-496">primeInRow</a></span><wbr><span class="parameters">(int&nbsp;r)</span></div>
<div class="block">Find a primed zero in the specified row. If there are no primed zeroes in the specified row,
then null will be returned.</div>
<dl class="notes">
<dt>Parameters:</dt>
<dd><code>r</code> - the index of the row to be searched</dd>
<dt>Returns:</dt>
<dd>pair of row and column indices of primed zero or null</dd>
</dl>
</section>
</li>
</ul>
</section>
</li>
</ul>
</section>
<!-- ========= END OF CLASS DATA ========= -->
</main>
<footer role="contentinfo">
<hr>
<p class="legal-copy"><small>Copyright &#169; 2007&#x2013;2020 <a href="https://www.apache.org/">The Apache Software Foundation</a>. All rights reserved.</small></p>
</footer>
</div>
</div>
</body>
</html>