smerc (version 1.0.1)

csg: Construct connected subgraphs


csg, lcsg, and scsg construct connected subgraphs. set contains a vector of vertices of the pattern 1, 2, 3, ..., N. idx is a vector of possible vertices being considered as a subgraph. w is a connectivity matrix relating the N vertices. w[i,j] = 1 if vertices i and j are connected, i.e., if they share an edge. The dimensions of w are \(N times k\), where k = length(idx). While the rows of w contain adjacency information for all N vertices, only the idx columns of the complete adjacency matrix are used in w. See Details for discussion of scsg.


csg(set, idx, w)

lcsg(lset, idx, w)

scsg(idx, w, verbose = FALSE)



A vector of (presumably connected) vertices.


A vector of vertices considered for inclusion in the subgraph, e.g., based on nearest neighbors.


The adjacency matrix for all vertices by row, but with only the idx columns


A list of sets.


A logical value indicating whether very descriptive messages should be provided. Default is FALSE. If TRUE, this can be useful for diagnosing where the sequences of connected subgraphs is slowing down/having problems.


A list of with all possible combinations of set and each possible connected vertex in idx, or NULL if none are possible.


scsg performs a sequence of lcsg calls. Starting with lset == list(idx[1]), scsg keeps iteratively building more connected subsgraphs by perfoming something like: set1 = list(idx[1]). set2 = lcsg(set1, idx, w). set3 = lcsg(set2, idx, w). This is done until there are no more connected subgraphs among the elements of idx.


# determine 50 nn of region 1 for NY data
coords = as.matrix(nydf[,c("longitude", "latitude")])
d = sp::spDists(coords, longlat = TRUE)
nn50 = order(d[1,])[1:50]
w = nyw[,nn50]
set = 1
# first set of connected neighbors
nb1 = csg(set, idx = nn50, w = w)
# extend set of connected neighbors
# for first element of nb1
set2 = nb1[[1]]
nb2 = csg(set2, idx = nn50, w = w)
# do the same thing for all sets in nb1
nb2e = lcsg(nb1, idx = nn50, w = w)
# the sets in nb2 should be present in the
# first 9 positions of nb2e
all.equal(nb2, nb2e[seq_along(nb2)])

# apply scsg to first 10 nn of vertex 1
nn10 = order(d[1,])[1:10]
w = nyw[, nn10]
nb3 = scsg(nn10, w, verbose = TRUE)
# }