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)",
           url="https://doi.org/10.1002/j.1538-7305.1957.tb01515.x",
           bibkey="doi:10.1002/j.1538-7305.1957.tb01515.x")
public class PrimsMinimumSpanningTree
extends java.lang.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
Bell System Technical Journal 36

Since:

0.5.5

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

Modifier and Type	Method and Description
static int[]	processDense(double[][] 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 <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