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

Author:

Erich Schubert

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.
static interface	PrimsMinimumSpanningTree.Collector Interface for collecting edges.

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.
static <T> void	processDense(T data, PrimsMinimumSpanningTree.Adapter<T> adapter, PrimsMinimumSpanningTree.Collector collector) Run Prim's algorithm on a dense graph.
static int[]	pruneTree(int numnodes, int[] tree, int minDegree) Prune the minimum spanning tree, removing all edges to nodes that have a degree below minDegree.

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

processDense

public static <T> void processDense(T data,
                    PrimsMinimumSpanningTree.Adapter<T> adapter,
                    PrimsMinimumSpanningTree.Collector collector)

Run Prim's algorithm on a dense graph.

Parameters:

data - Data set

adapter - Adapter instance

collector - Edge collector

pruneTree

public static int[] pruneTree(int numnodes,
              int[] tree,
              int minDegree)

Prune the minimum spanning tree, removing all edges to nodes that have a degree below minDegree.

Parameters:

numnodes - Number of nodes (MUST use numbers 0 to numnodes-1)

tree - Original spanning tree

minDegree - Minimum node degree

Returns:

Pruned spanning tree