de.lmu.ifi.dbs.elki.math.geometry

Class PrimsMinimumSpanningTree

java.lang.Object

de.lmu.ifi.dbs.elki.math.geometry.PrimsMinimumSpanningTree

@Reference(authors="R. C. Prim",
           title="Shortest connection networks and some generalizations",
           booktitle="Bell System Technical Journal, 36 (1957)")
public class PrimsMinimumSpanningTree
extends Object

Prim's algorithm for finding the minimum spanning tree. Implementation for dense graphs, represented as distance matrix. Reference:

R. C. Prim
Shortest connection networks and some generalizations
In: Bell System Technical Journal, 36 (1957), pp. 1389–140

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	PrimsMinimumSpanningTree.Adapter<T> Adapter interface to allow use with different data representations.
static class	PrimsMinimumSpanningTree.Array2DAdapter Adapter for a simple 2d double matrix.

Field Summary

Fields

Modifier and Type	Field and Description
static PrimsMinimumSpanningTree.Array2DAdapter	ARRAY2D_ADAPTER Adapter class for double[][] matrixes.

Constructor Summary

Constructors

Constructor and Description
PrimsMinimumSpanningTree()

Method Summary

Methods

Modifier and Type	Method and Description
static int[]	processDense(double[][] mat) Process a k x k distance matrix.
static int[]	processDense(Matrix mat) Process a k x k distance matrix.
static <T> int[]	processDense(T data, PrimsMinimumSpanningTree.Adapter<T> adapter) Run Prim's algorithm on a dense graph.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

ARRAY2D_ADAPTER

public static final PrimsMinimumSpanningTree.Array2DAdapter ARRAY2D_ADAPTER

Adapter class for double[][] matrixes.

Constructor Detail

PrimsMinimumSpanningTree

public PrimsMinimumSpanningTree()

Method Detail

processDense

public static int[] processDense(double[][] mat)

Process a k x k distance matrix.

Parameters:

mat - Distance matrix

Returns:

list of node number pairs representing the edges

processDense

public static int[] processDense(Matrix mat)

Process a k x k distance matrix.

Parameters:

mat - Distance matrix

Returns:

list of node number pairs representing the edges

processDense

public static <T> int[] processDense(T data,
                     PrimsMinimumSpanningTree.Adapter<T> adapter)

Run Prim's algorithm on a dense graph.

Parameters:

data - Data set

adapter - Adapter instance

Returns:

list of node number pairs representing the edges