DFS: Depth-first search

In gRapHD: Efficient Selection of Undirected Graphical Models for High-Dimensional Datasets

Description

Returns all vertices reachable from one specific vertex (assuming that there are no cycles).

Usage

DFS(model=NULL,edges=NULL, v, p=NULL)

Arguments

model	gRapHD object.
edges	matrix with 2 columns, each row representing one edge, and each column one of the vertices in the edge.
v	initial vertex (0<v<=p).
p	number of vertices.

Details

Given a list of edges, and a specific vertex v, returns a vector with all vertices in the connected component containing v. The function assumes that the graph is acyclic.

Value

Vector with all vertices reachable from v, or 0 if v is an isolated vertex.

Author(s)

Gabriel Coelho Goncalves de Abreu ([e-mail])

References

Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C. Introduction to Algorithms, 2nd Edition. MIT Press and McGraw-Hill, 2001, pp.540:9.

Examples

set.seed(7,kind="Mersenne-Twister")
dataset <- matrix(rnorm(1000),nrow=100,ncol=10)
m <- minForest(dataset,stat="BIC")

DFS(edges=m@edges,v=1,p=10)
# [1] 5 2 9 8
#######################################################################
data(dsDiscr)
m1 <- minForest(dsDiscr,homog=TRUE,forbEdges=NULL,stat="BIC")
vertices <- DFS(edges=m1@edges, v=1, p=m1@p)

# result
vertices
# numeric(0)
# meaning that 1 is an isolated vertex

# OR
m1 <- minForest(dsDiscr,homog=TRUE,forbEdges=NULL,stat="LR")
vertices <- DFS(edges=m1@edges, v=1, p=m1@p)

# result
vertices
# [1]  4  8 12 19 18 14  7 17  5  3 10 13 15  9  6 20 16 11  2
# meaning that 1 reachs all vertices (a tree)

gRapHD documentation built on Feb. 9, 2018, 6:05 a.m.