First commit
[nngd.git] / R / ectd.R
... / ...
CommitLineData
1#' Compute the Euclidian Commute-Time Distances (ECTD) in an undirected graph.
2#'
3#' Assuming similarity function doesn't depend on x, and undirected graph.
4#'
5#' @param o Output of \code{nng}.
6#' @param similarity function distance --> similarity.
7#' @param inf.replace Replace Inf values by large finite number ?
8#'
9#' @return A distances matrix (n x n)
10#'
11#' @export
12ectd <- function(o, similarity=function(x) 1, inf.replace=TRUE)
13{
14 if (!igraph::is_directed(o$graph))
15 stop("Directed graph case unimplemented yet")
16 n <- igraph::vcount(o$graph)
17 E <- igraph::as_edgelist(o$graph, names=FALSE)
18 W <- matrix(0, nrow=n, ncol=n)
19 for (i in seq_len(nrow(E))) {
20 edge <- c(E[i,1], E[i,2])
21 W[edge[1], edge[2]] <- similarity(o$distances[i])
22 W[edge[2], edge[1]] <- W[edge[1], edge[2]]
23 }
24 L <- diag(rowSums(W)) - W
25 cc <- igraph::components(o$graph)
26 distances <- matrix(Inf, nrow=n, ncol=n)
27 for (i in seq_len(cc$no)) {
28 indices <- which(cc$membership == i)
29 L_loc <- L[indices, indices]
30 n_loc <- cc$csize[i]
31 if (n_loc >= 2) L_inv = pracma::pinv(L_loc)
32 else L_inv = matrix(ifelse(L_loc != 0, 1/L_loc[1], 0))
33 Lii = matrix(rep(diag(L_inv), each=n_loc), nrow=n_loc, byrow=TRUE)
34 Ljj = matrix(rep(diag(L_inv), each=n_loc), nrow=n_loc)
35 # https://math.stackexchange.com/questions/1321305/commute-time-distance-in-a-graph
36 distances[indices, indices] <- Lii + Ljj - 2 * L_inv
37 }
38 if (inf.replace) {
39 finiteMax <- max(distances[is.finite(distances)])
40 distances[is.infinite(distances)] <- finiteMax + 1
41 }
42 distances
43}