Package elki.math.geometry
Class PrimsMinimumSpanningTree
- java.lang.Object
-
- 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 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 Description static PrimsMinimumSpanningTree.Array2DAdapter
ARRAY2D_ADAPTER
Adapter class for double[][] matrixes.
-
Constructor Summary
Constructors Constructor Description PrimsMinimumSpanningTree()
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method 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 belowminDegree
.
-
-
-
Field Detail
-
ARRAY2D_ADAPTER
public static final PrimsMinimumSpanningTree.Array2DAdapter ARRAY2D_ADAPTER
Adapter class for double[][] matrixes.
-
-
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 setadapter
- 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 setadapter
- Adapter instancecollector
- 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 belowminDegree
.- Parameters:
numnodes
- Number of nodes (MUST use numbers 0 tonumnodes-1
)tree
- Original spanning treeminDegree
- Minimum node degree- Returns:
- Pruned spanning tree
-
-