Point Cloud

struct Edge{T <: Real}
    verts    :: Tuple{Int, Int}
    distance :: T
end

Connects two neighboring verts by an edge of length distance.

struct Graph{T <: Real}
    verts :: Array{Vertex{T},1}
    edges :: Array{Edge{T},1}
end

A generic graph data structure containing vertices (points in space) stored within verts connected by edges.

struct Vertex{T <: Real}
    position :: Array{T}
end

Represents a single cell within a larger point cloud. The embedding space is normalized gene expression.

adjacency_list(G :: Graph)

Return the flattened adjacency list for graph G.

dijkstra!(dist, adj, src)

Compute the shortest path from src to all other points given adjacency list adj and distances dist using Dijkstra's algorithm.

floyd_warshall(G :: Graph)

Compute the shortest path from all vertices to all other vertices within graph G.

geodesics(x, k; D=missing, accept=(d)->true, sparse=true)

Compute the matrix of pairwise distances, given a pointcloud x and neighborhood cutoff k, from the resultant neighborhood graph. If sparse is true, it will utilize Dijkstra's algorithm, individually for each point. If sparse is false, it will utilize the Floyd Warshall algorithm.

geodesics(G :: Graph; sparse=true)

Compute the matrix of pairwise distances, given a neighborhood graph G, weighted by local Euclidean distance. If sparse is true, it will utilize Dijkstra's algorithm, individually for each point. If sparse is false, it will utilize the Floyd Warshall algorithm.

isomap(x, dₒ; k=12, sparse=true)

Compute the isometric embedding of point cloud x into dₒ dimensions. Geodesic distances between all points are estimated by utilizing the shortest path defined by the neighborhood graph. The embedding is computed from a multidimensional scaling analysis on the resultant geodesics.

mds(D², dₒ)

Computes the lowest dₒ components from a Multidimensional Scaling analysis given pairwise squared distances D².

neighborhood(x, k :: T; D=missing, accept=(d)->true) where T <: AbstractFloat

Constructs a neighborhood graph of all neighbors within euclidean distance k for each point of cloud x. If D is given, it is assumed to be a dense matrix of pairwise distances.

neighborhood(x, k :: T; D=missing, accept=(d)->true) where T <: Integer

Constructs a neighborhood graph of the k nearest neighbor for each point of cloud x. If D is given, it is assumed to be a dense matrix of pairwise distances.

scaling(D, N)

Estimate the Hausdorff dimension by computing how the number of points contained within balls scales with varying radius.

upper_tri(x)

Returns the upper triangular portion of matrix x.