cccd (version 1.5)

rng: Relative Neighborhood Graph.

Description

the relative neighborhood graph defined by a set of points.

Usage

rng(x=NULL, dx=NULL, r = 1, method = NULL, usedeldir = TRUE, open = TRUE, k = NA, algorithm = 'cover_tree')

Arguments

x

a data matrix. Either x or dx must be provided.

dx

an interpoint distance matrix.

r

a multiplier to grow the balls.

method

the method used for the distance. See dist

usedeldir

a logical. If true and the data are two dimensional and the deldir package is installed, the Delaunay triangularization is first computed, and this is used to compute the relative neighborhood graph.

open

logical. If TRUE, open balls are used in the definition.

k

If given, get.knn is used from FNN to approximate the relative neighborhood graph. Only the k nearest neighbors to the points are used to determine whether an edge should be made or not. This will be much faster and use less memory for large data sets, but is an approximation unless k is sufficiently large.

algorithm

See get.knn.

Value

an object of class igraph, with the additional attributes

layout

the x matrix.

r,p

arguments given to rng.

Details

the relative neighborhood graph is defined in terms of balls centered at observations. For two observations, the balls are set to have radius equal to the distance between the observations (or r times this distance if r is not 1). There is an edge between the vertices associated with the observations if and only if there are no vertices in the lune defined by the intersection of the balls.

The flag open should make no difference for most applications, but there are very specific cases (see the example section below) where setting it to be TRUE will give the wrong answer (thanks to Luke Mathieson for pointing this out to me).

References

J.W. Jaromczyk and G.T. Toussaint, "Relative neighborhood graphs and their relatives", Proceedings of the IEEE, 80, 1502-1517, 1992.

G.T. Toussaint, "A Graph-Theoretic Primal Sketch", Computational Morphology, 229-260, 1988.

D.J. Marchette, Random Graphs for Statistical Pattern Recognition, John Wiley & Sons, 2004.

See Also

gg,cccd,ccd, dist get.knn

Examples

x <- matrix(runif(100),ncol=2)

g <- rng(x)
## Not run: 
# plot(g)
# ## End(Not run)

## Example using 'open':
g <- graph.full(5,directed=FALSE)

g1 <- rng(x=get.adjacency(g,sparse=FALSE),open=TRUE)
ecount(g1)
g2 <- rng(x=get.adjacency(g,sparse=FALSE),open=FALSE)
graph.isomorphic(g2,g)