INRIA & friends

fr.inrialpes.exmo.align.impl
Class HungarianAlgorithm

java.lang.Object
  extended byfr.inrialpes.exmo.align.impl.HungarianAlgorithm

public class HungarianAlgorithm
extends java.lang.Object


Constructor Summary
HungarianAlgorithm()
           
 
Method Summary
static void clearCovers(int[] rowCover, int[] colCover)
           
static void convertPath(int[][] mask, int[][] path, int count)
           
static double[][] copyOf(double[][] original)
           
static void erasePrimes(int[][] mask)
           
static double findLargest(double[][] array)
           
static int findPrimeInRow(int[][] mask, int row)
           
static double findSmallest(double[][] cost, int[] rowCover, int[] colCover, double maxCost)
           
static int findStarInCol(int[][] mask, int col)
           
static int[] findUncoveredZero(int[] row_col, double[][] cost, int[] rowCover, int[] colCover)
           
static int hg_step1(int step, double[][] cost)
           
static int hg_step2(int step, double[][] cost, int[][] mask, int[] rowCover, int[] colCover)
          What STEP 2 does: Marks uncovered zeros as starred and covers their row and column.
static int hg_step3(int step, int[][] mask, int[] colCover)
          What STEP 3 does: Cover columns of starred zeros.
static int hg_step4(int step, double[][] cost, int[][] mask, int[] rowCover, int[] colCover, int[] zero_RC)
          What STEP 4 does: Find an uncovered zero in cost and prime it (if none go to step 6).
static int hg_step5(int step, int[][] mask, int[] rowCover, int[] colCover, int[] zero_RC)
           
static int hg_step6(int step, double[][] cost, int[] rowCover, int[] colCover, double maxCost)
           
static int[][] hgAlgorithm(double[][] costPrm, java.lang.String sumType)
           
static void main(java.lang.String[] args)
           
static double[][] transpose(double[][] array)
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

HungarianAlgorithm

public HungarianAlgorithm()
Method Detail

findLargest

public static double findLargest(double[][] array)

transpose

public static double[][] transpose(double[][] array)

copyOf

public static double[][] copyOf(double[][] original)

hgAlgorithm

public static int[][] hgAlgorithm(double[][] costPrm,
                                  java.lang.String sumType)

hg_step1

public static int hg_step1(int step,
                           double[][] cost)

hg_step2

public static int hg_step2(int step,
                           double[][] cost,
                           int[][] mask,
                           int[] rowCover,
                           int[] colCover)
What STEP 2 does: Marks uncovered zeros as starred and covers their row and column.


hg_step3

public static int hg_step3(int step,
                           int[][] mask,
                           int[] colCover)
What STEP 3 does: Cover columns of starred zeros. Check if all columns are covered.


hg_step4

public static int hg_step4(int step,
                           double[][] cost,
                           int[][] mask,
                           int[] rowCover,
                           int[] colCover,
                           int[] zero_RC)
What STEP 4 does: Find an uncovered zero in cost and prime it (if none go to step 6). Check for star in same row: if yes, cover the row and uncover the star's column. Repeat until no uncovered zeros are left and go to step 6. If not, save location of primed zero and go to step 5.


findUncoveredZero

public static int[] findUncoveredZero(int[] row_col,
                                      double[][] cost,
                                      int[] rowCover,
                                      int[] colCover)

hg_step5

public static int hg_step5(int step,
                           int[][] mask,
                           int[] rowCover,
                           int[] colCover,
                           int[] zero_RC)

findStarInCol

public static int findStarInCol(int[][] mask,
                                int col)

findPrimeInRow

public static int findPrimeInRow(int[][] mask,
                                 int row)

convertPath

public static void convertPath(int[][] mask,
                               int[][] path,
                               int count)

erasePrimes

public static void erasePrimes(int[][] mask)

clearCovers

public static void clearCovers(int[] rowCover,
                               int[] colCover)

hg_step6

public static int hg_step6(int step,
                           double[][] cost,
                           int[] rowCover,
                           int[] colCover,
                           double maxCost)

findSmallest

public static double findSmallest(double[][] cost,
                                  int[] rowCover,
                                  int[] colCover,
                                  double maxCost)

main

public static void main(java.lang.String[] args)

INRIA & friends

..no bottom yet...