Package gov.nih.mipav.model.algorithms

Class Dijkstra

java.lang.Object

java.lang.Thread

gov.nih.mipav.model.algorithms.AlgorithmBase

gov.nih.mipav.model.algorithms.Dijkstra

All Implemented Interfaces:

java.awt.event.ActionListener, java.awt.event.WindowListener, java.lang.Runnable, java.util.EventListener

public class Dijkstra
extends AlgorithmBase

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
(package private) class	Dijkstra.csr_matrix
(package private) class	Dijkstra.Pair<T extends java.lang.Comparable<T>,U extends java.lang.Comparable<U>>

Nested classes/interfaces inherited from class java.lang.Thread

java.lang.Thread.State, java.lang.Thread.UncaughtExceptionHandler

Field Summary

Fields

Modifier and Type	Field	Description
(package private) Dijkstra.csr_matrix	csgraph
(package private) boolean	directed
(package private) Dijkstra.csr_matrix	directed_G_csr
(package private) double[][]	directed_pred
(package private) double[][]	directed_SP
(package private) Dijkstra.csr_matrix	directed_sparse_zero_G
(package private) double[][]	directed_sparse_zero_SP
(package private) double[][]	dist_matrix
(package private) double[]	dist_matrix_1D
(package private) double	DTYPE_EPS
(package private) int[]	indices
(package private) double	limit
(package private) boolean	min_only
(package private) int	NULL_IDX
(package private) int[][]	predecessor_matrix
(package private) int[]	predecessor_matrix_1D
(package private) boolean	return_predecessors
(package private) int[][]	source_matrix
(package private) int[]	source_matrix_1D
(package private) Dijkstra.csr_matrix	undirected_G_csr
(package private) double[][]	undirected_pred
(package private) double[][]	undirected_SP
(package private) double[][]	undirected_SP_limit_0
(package private) double[][]	undirected_SP_limit_2
(package private) Dijkstra.csr_matrix	undirected_sparse_zero_G
(package private) double[][]	undirected_sparse_zero_SP
(package private) boolean	unweighted
(package private) Dijkstra.csr_matrix	unweighted_G_csr

Fields inherited from class gov.nih.mipav.model.algorithms.AlgorithmBase

destFlag, destImage, image25D, mask, maxProgressValue, minProgressValue, multiThreadingEnabled, nthreads, progress, progressModulus, progressStep, runningInSeparateThread, separable, srcImage, threadStopped

Fields inherited from class java.lang.Thread

MAX_PRIORITY, MIN_PRIORITY, NORM_PRIORITY

Constructor Summary

Constructors

Constructor	Description
Dijkstra()
Dijkstra(Dijkstra.csr_matrix csgraph, boolean directed, int[] indices, boolean return_predecessors, boolean unweighted, double limit, boolean min_only)

Method Summary

Modifier and Type	Method	Description
(package private) void	_construct_dist_matrix(double[][] graph, int[][] pred, double[][] dist, boolean directed, double null_value)
(package private) int	_dijkstra(int[] source_indices, double[] csr_weights, int[] csr_indices, int[] csr_indptr, double[] csrT_weights, int[] csrT_indices, int[] csrT_indptr, double[][] dist_matrix, int[][] pred, int[][] sources, double limit)
(package private) int	_dijkstra(int[] source_indices, double[] csr_weights, int[] csr_indices, int[] csr_indptr, double[] csrT_weights, int[] csrT_indices, int[] csrT_indptr, double[] dist_matrix, int[] pred, int[] sources, double limit)
(package private) int	_dijkstra_multi_separate(int[] source_indices, double[] csr_weights, int[] csr_indices, int[] csr_indptr, double[] csrT_weights, int[] csrT_indices, int[] csrT_indptr, double[][] dist_matrix, int[][] pred, int[][] sources, double limit)
(package private) void	_dijkstra_scan_heap(java.util.PriorityQueue<Dijkstra.Pair<java.lang.Double,java.lang.Integer>> heap, Dijkstra.Pair<java.lang.Double,java.lang.Integer> v, double[] csr_weights, int[] csr_indices, int[] csr_indptr, double[][] dist_matrix, int[][] pred, boolean return_pred, int[][] sources, boolean return_source, double limit)
(package private) void	_dijkstra_scan_heap(java.util.PriorityQueue<Dijkstra.Pair<java.lang.Double,java.lang.Integer>> heap, Dijkstra.Pair<java.lang.Double,java.lang.Integer> v, double[] csr_weights, int[] csr_indices, int[] csr_indptr, double[] dist_matrix, int[] pred, boolean return_pred, int[] sources, boolean return_source, double limit)
void	_populate_graph(double[] data, int[] indices, int[] indptr, double[][] graph, double null_value)
double[][]	construct_dist_matrix(Dijkstra.csr_matrix graph, int[][] predecessors, boolean directed, double null_value)
void	create_test_arrays()
double[][]	csgraph_to_dense(Dijkstra.csr_matrix csgraph, double null_value)
(package private) double[]	getDist_matrix_1D()
(package private) double[][]	getDistMatrix()
(package private) int[]	getPredecessor_matrix_1D()
(package private) int[][]	getPredecessorMatrix()
(package private) int[]	getSource_matrix_1D()
void	runAlgorithm()	Actually runs the algorithm.
void	test_dijkstra_construct_shortest_path()
void	test_dijkstra_indices_min_only()
void	test_dijkstra_limit()
void	test_directed_dijkstra()
void	test_directed_sparse_zero_dijkstra()
void	test_predecessors_dijkstra()
void	test_undirected_dijkstra()
void	test_undirected_sparse_zero_dijkstra()
void	test_unweighted_path_dijkstra()

Methods inherited from class gov.nih.mipav.model.algorithms.AlgorithmBase

actionPerformed, addListener, addProgressChangeListener, calculateImageSize, calculatePrincipleAxis, computeElapsedTime, computeElapsedTime, convertIntoFloat, delinkProgressToAlgorithm, delinkProgressToAlgorithmMulti, displayError, errorCleanUp, finalize, fireProgressStateChanged, fireProgressStateChanged, fireProgressStateChanged, fireProgressStateChanged, fireProgressStateChanged, generateProgressValues, getDestImage, getElapsedTime, getMask, getMaxProgressValue, getMinProgressValue, getNumberOfThreads, getProgress, getProgressChangeListener, getProgressChangeListeners, getProgressModulus, getProgressStep, getProgressValues, getSrcImage, isCompleted, isImage25D, isMultiThreadingEnabled, isRunningInSeparateThread, isThreadStopped, linkProgressToAlgorithm, linkProgressToAlgorithm, makeProgress, notifyListeners, removeListener, removeProgressChangeListener, run, setCompleted, setImage25D, setMask, setMaxProgressValue, setMinProgressValue, setMultiThreadingEnabled, setNumberOfThreads, setProgress, setProgressModulus, setProgressStep, setProgressValues, setProgressValues, setRunningInSeparateThread, setSrcImage, setStartTime, setThreadStopped, startMethod, windowActivated, windowClosed, windowClosing, windowDeactivated, windowDeiconified, windowIconified, windowOpened

Methods inherited from class java.lang.Thread

activeCount, checkAccess, clone, countStackFrames, currentThread, dumpStack, enumerate, getAllStackTraces, getContextClassLoader, getDefaultUncaughtExceptionHandler, getId, getName, getPriority, getStackTrace, getState, getThreadGroup, getUncaughtExceptionHandler, holdsLock, interrupt, interrupted, isAlive, isDaemon, isInterrupted, join, join, join, onSpinWait, resume, setContextClassLoader, setDaemon, setDefaultUncaughtExceptionHandler, setName, setPriority, setUncaughtExceptionHandler, sleep, sleep, start, stop, suspend, toString, yield

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

DTYPE_EPS

final double DTYPE_EPS

See Also:

Constant Field Values

NULL_IDX

final int NULL_IDX

See Also:

Constant Field Values

csgraph

Dijkstra.csr_matrix csgraph

directed

boolean directed

indices

int[] indices

return_predecessors

boolean return_predecessors

unweighted

boolean unweighted

limit

double limit

min_only

boolean min_only

dist_matrix

double[][] dist_matrix

predecessor_matrix

int[][] predecessor_matrix

source_matrix

int[][] source_matrix

dist_matrix_1D

double[] dist_matrix_1D

predecessor_matrix_1D

int[] predecessor_matrix_1D

source_matrix_1D

int[] source_matrix_1D

undirected_SP_limit_0

double[][] undirected_SP_limit_0

undirected_SP_limit_2

double[][] undirected_SP_limit_2

undirected_SP

double[][] undirected_SP

undirected_G_csr

Dijkstra.csr_matrix undirected_G_csr

directed_SP

double[][] directed_SP

directed_G_csr

Dijkstra.csr_matrix directed_G_csr

unweighted_G_csr

Dijkstra.csr_matrix unweighted_G_csr

directed_sparse_zero_G

Dijkstra.csr_matrix directed_sparse_zero_G

directed_sparse_zero_SP

double[][] directed_sparse_zero_SP

undirected_sparse_zero_G

Dijkstra.csr_matrix undirected_sparse_zero_G

undirected_sparse_zero_SP

double[][] undirected_sparse_zero_SP

directed_pred

double[][] directed_pred

undirected_pred

double[][] undirected_pred

Constructor Detail

Dijkstra

public Dijkstra()

Dijkstra

public Dijkstra(Dijkstra.csr_matrix csgraph,
                boolean directed,
                int[] indices,
                boolean return_predecessors,
                boolean unweighted,
                double limit,
                boolean min_only)

Method Detail

runAlgorithm

public void runAlgorithm()

Description copied from class: AlgorithmBase

Actually runs the algorithm. Implemented by inheriting algorithms.

Specified by:

runAlgorithm in class AlgorithmBase

_dijkstra

int _dijkstra(int[] source_indices,
              double[] csr_weights,
              int[] csr_indices,
              int[] csr_indptr,
              double[] csrT_weights,
              int[] csrT_indices,
              int[] csrT_indptr,
              double[][] dist_matrix,
              int[][] pred,
              int[][] sources,
              double limit)

_dijkstra_scan_heap

void _dijkstra_scan_heap(java.util.PriorityQueue<Dijkstra.Pair<java.lang.Double,java.lang.Integer>> heap,
                         Dijkstra.Pair<java.lang.Double,java.lang.Integer> v,
                         double[] csr_weights,
                         int[] csr_indices,
                         int[] csr_indptr,
                         double[][] dist_matrix,
                         int[][] pred,
                         boolean return_pred,
                         int[][] sources,
                         boolean return_source,
                         double limit)

_dijkstra_multi_separate

int _dijkstra_multi_separate(int[] source_indices,
                             double[] csr_weights,
                             int[] csr_indices,
                             int[] csr_indptr,
                             double[] csrT_weights,
                             int[] csrT_indices,
                             int[] csrT_indptr,
                             double[][] dist_matrix,
                             int[][] pred,
                             int[][] sources,
                             double limit)

_dijkstra

int _dijkstra(int[] source_indices,
              double[] csr_weights,
              int[] csr_indices,
              int[] csr_indptr,
              double[] csrT_weights,
              int[] csrT_indices,
              int[] csrT_indptr,
              double[] dist_matrix,
              int[] pred,
              int[] sources,
              double limit)

_dijkstra_scan_heap

void _dijkstra_scan_heap(java.util.PriorityQueue<Dijkstra.Pair<java.lang.Double,java.lang.Integer>> heap,
                         Dijkstra.Pair<java.lang.Double,java.lang.Integer> v,
                         double[] csr_weights,
                         int[] csr_indices,
                         int[] csr_indptr,
                         double[] dist_matrix,
                         int[] pred,
                         boolean return_pred,
                         int[] sources,
                         boolean return_source,
                         double limit)

getDist_matrix_1D

double[] getDist_matrix_1D()

getPredecessor_matrix_1D

int[] getPredecessor_matrix_1D()

getSource_matrix_1D

int[] getSource_matrix_1D()

getDistMatrix

double[][] getDistMatrix()

getPredecessorMatrix

int[][] getPredecessorMatrix()

csgraph_to_dense

public double[][] csgraph_to_dense(Dijkstra.csr_matrix csgraph,
                                   double null_value)

_populate_graph

public void _populate_graph(double[] data,
                            int[] indices,
                            int[] indptr,
                            double[][] graph,
                            double null_value)

construct_dist_matrix

public double[][] construct_dist_matrix(Dijkstra.csr_matrix graph,
                                        int[][] predecessors,
                                        boolean directed,
                                        double null_value)

_construct_dist_matrix

void _construct_dist_matrix(double[][] graph,
                            int[][] pred,
                            double[][] dist,
                            boolean directed,
                            double null_value)

create_test_arrays

public void create_test_arrays()

test_dijkstra_limit

public void test_dijkstra_limit()

test_directed_dijkstra

public void test_directed_dijkstra()

test_undirected_dijkstra

public void test_undirected_dijkstra()

test_directed_sparse_zero_dijkstra

public void test_directed_sparse_zero_dijkstra()

test_undirected_sparse_zero_dijkstra

public void test_undirected_sparse_zero_dijkstra()

test_dijkstra_indices_min_only

public void test_dijkstra_indices_min_only()

test_predecessors_dijkstra

public void test_predecessors_dijkstra()

test_unweighted_path_dijkstra

public void test_unweighted_path_dijkstra()

test_dijkstra_construct_shortest_path

public void test_dijkstra_construct_shortest_path()