de.lmu.ifi.dbs.elki.visualization.parallel3d.layout

Class AbstractLayout3DPC<N extends Layout.Node>

java.lang.Object

de.lmu.ifi.dbs.elki.visualization.parallel3d.layout.AbstractLayout3DPC<N>

All Implemented Interfaces:

Layouter3DPC<NumberVector>, SimilarityBasedLayouter3DPC

Direct Known Subclasses:

CompactCircularMSTLayout3DPC, MultidimensionalScalingMSTLayout3DPC, SimpleCircularMSTLayout3DPC

public abstract class AbstractLayout3DPC<N extends Layout.Node>
extends java.lang.Object
implements SimilarityBasedLayouter3DPC

Abstract class for dimension similarity based layouters.

Since:

0.6.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	AbstractLayout3DPC.AbstractNode<N extends AbstractLayout3DPC.AbstractNode<N>> Abstract node implementation.
private static class	AbstractLayout3DPC.LowerTriangularAdapter Class to use a lower-triangular similarity matrix for distance-based Prim's spanning tree.
static class	AbstractLayout3DPC.Parameterizer Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
(package private) DependenceMeasure	sim Similarity measure

Fields inherited from interface de.lmu.ifi.dbs.elki.visualization.parallel3d.layout.SimilarityBasedLayouter3DPC

SIM_ID

Constructor Summary

Constructors

Constructor and Description
AbstractLayout3DPC(DependenceMeasure sim) Constructor.

Method Summary

Modifier and Type	Method and Description
protected N	buildSpanningTree(int dim, double[] mat, Layout layout) Build the minimum spanning tree.
protected N	buildTree(int[] msg, int cur, int parent, java.util.ArrayList<N> nodes) Recursive tree build method.
static double[]	computeSimilarityMatrix(DependenceMeasure sim, Relation<? extends NumberVector> rel) Compute a column-wise dependency matrix for the given relation.
static int	findOptimalRoot(int[] msg) Find the "optimal" root of a spanning tree.
DependenceMeasure	getSimilarity() Get the similarity measure to use.
abstract Layout	layout(int dim, double[] mat) Main analysis method.
Layout	layout(Relation<? extends NumberVector> rel) Run the layouting algorithm.
(package private) abstract N	makeNode(int dim, java.util.List<N> children)
protected int	maxDepth(Layout.Node node) Compute the depth of the graph.

Methods inherited from class java.lang.Object

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

Field Detail

sim

DependenceMeasure sim

Similarity measure

Constructor Detail

AbstractLayout3DPC

public AbstractLayout3DPC(DependenceMeasure sim)

Constructor.

Parameters:

sim - Similarity measure

Method Detail

getSimilarity

public DependenceMeasure getSimilarity()

Description copied from interface: SimilarityBasedLayouter3DPC

Get the similarity measure to use.

Specified by:

getSimilarity in interface SimilarityBasedLayouter3DPC

Returns:

Similarity measure.

layout

public Layout layout(Relation<? extends NumberVector> rel)

Description copied from interface: Layouter3DPC

Run the layouting algorithm.

Specified by:

layout in interface Layouter3DPC<NumberVector>

Parameters:

rel - Relation to use

Returns:

Layout, nodes indexed by dimension.

computeSimilarityMatrix

public static double[] computeSimilarityMatrix(DependenceMeasure sim,
                                               Relation<? extends NumberVector> rel)

Compute a column-wise dependency matrix for the given relation.

Parameters:

sim - Dependence measure

rel - Vector relation

Returns:

Similarity matrix (lower triangular form)

layout

public abstract Layout layout(int dim,
                              double[] mat)

Description copied from interface: SimilarityBasedLayouter3DPC

Main analysis method.

Specified by:

layout in interface SimilarityBasedLayouter3DPC

Parameters:

dim - Dimensionality

mat - Similarity matrix

Returns:

Layout

buildSpanningTree

protected N buildSpanningTree(int dim,
                              double[] mat,
                              Layout layout)

Build the minimum spanning tree.

Parameters:

mat - Similarity matrix

layout - Layout to write to

Returns:

Root node id

makeNode

abstract N makeNode(int dim,
                    java.util.List<N> children)

buildTree

protected N buildTree(int[] msg,
                      int cur,
                      int parent,
                      java.util.ArrayList<N> nodes)

Recursive tree build method.

Parameters:

msg - Minimum spanning graph

cur - Current node

parent - Parent node

nodes - Nodes array to fill - must be preinitialized with nulls!

Returns:

Tree of nodes

maxDepth

protected int maxDepth(Layout.Node node)

Compute the depth of the graph.

Parameters:

node - Current node

Returns:

Depth

findOptimalRoot

public static int findOptimalRoot(int[] msg)

Find the "optimal" root of a spanning tree. Optimal in the sense of: one of the most central nodes.

This uses a simple message passing approach. Every node that has only one unset neighbor will emit a message to this neighbor. The node last to emit wins.

Parameters:

msg - Minimum spanning graph.

Returns:

optimal root node.