I have a matrix and graph (same structure):
library(igraph)
m = structure(c(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 2, 2, 1, 1, 1, 2, 2, 3, 3, 3, 2, 2, 2, 2, 3, 3), dim = c(6L,
6L))
g = structure(list(36, FALSE, c(1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13,
14, 15, 16, 17, 19, 20, 21, 22, 23, 25, 26, 27, 28, 29, 31, 32,
33, 34, 35, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35
), c(0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 18, 19,
20, 21, 22, 24, 25, 26, 27, 28, 30, 31, 32, 33, 34, 0, 1, 2,
3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 21, 22, 23, 24, 25, 26, 27, 28, 29), NULL, NULL, NULL, NULL,
list(c(1, 0, 1), structure(list(), names = character(0)),
list(name = c("1", "2", "3", "4", "5", "6", "7", "8",
"9", "10", "11", "12", "13", "14", "15", "16", "17",
"18", "19", "20", "21", "22", "23", "24", "25", "26",
"27", "28", "29", "30", "31", "32", "33", "34", "35",
"36"), value = c(1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2,
1, 1, 1, 2, 2, 2, 1, 1, 1, 2, 3, 2, 1, 1, 1, 1, 3, 3,
1, 1, 1, 1, 3, 3), color = structure(c(1L, 1L, 1L, 1L,
1L, 2L, 1L, 1L, 1L, 1L, 2L, 2L, 1L, 1L, 1L, 2L, 2L, 2L,
1L, 1L, 1L, 2L, 3L, 2L, 1L, 1L, 1L, 1L, 3L, 3L, 1L, 1L,
1L, 1L, 3L, 3L), levels = c("1", "2", "3"), class = "factor"),
label = c(1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1,
1, 1, 2, 2, 2, 1, 1, 1, 2, 3, 2, 1, 1, 1, 1, 3, 3,
1, 1, 1, 1, 3, 3)), structure(list(), names = character(0)))), class = "igraph")
g = upgrade_graph(g)
plot(g)
edgelist = dput(as_edgelist(g))
adj_matrix = get.adjacency(g)
For this matrix m :
[,1] [,2] [,3] [,4] [,5] [,6]
[1,] 1 1 1 1 1 2
[2,] 1 1 1 1 2 2
[3,] 1 1 1 2 2 2
[4,] 1 1 1 2 3 2
[5,] 1 1 1 1 3 3
[6,] 1 1 1 1 3 3
I think I know how to do this for the graph g using igraph - I select all nodes that have a value 1 and make a subgraph, then check if this subgraph is fully connected AND contains nodes with values 2 or 3. I do this for values 2,3:
library(igraph)
check_connectivity_igraph <- function(g, value) {
value_vertices <- which(V(g)$value == value)
if (length(value_vertices) < 2) {
return(TRUE)
}
subgraph <- induced_subgraph(g, value_vertices)
is_connected <- components(subgraph)$no == 1
return(is_connected)
}
result_1 <- check_connectivity_igraph(g, 1)
result_2 <- check_connectivity_igraph(g, 2)
result_3 <- check_connectivity_igraph(g, 3)
How can I do the same for the matrix m?
Updated Igraph approach
check_all_connectivity <- function(g) {
values_to_check <- c(1, 2, 3)
results <- list()
for (value in values_to_check) {
same_value_vertices <- which(V(g)$value == value)
result_for_value <- list()
if (length(same_value_vertices) < 2) {
result_for_value$connected <- TRUE
result_for_value$violation_count <- 0
result_for_value$violating_nodes <- integer(0)
results[[paste0("value_", value)]] <- result_for_value
next
}
other_value_vertices <- which(V(g)$value != value)
if (length(other_value_vertices) > 0) {
subgraph <- delete_vertices(g, other_value_vertices)
} else {
subgraph <- g
}
comp <- components(subgraph)
is_connected <- comp$no == 1
result_for_value$connected <- is_connected
if (!is_connected) {
component_sizes <- table(comp$membership)
largest_component <- as.numeric(names(component_sizes)[which.max(component_sizes)])
isolated_nodes <- which(comp$membership != largest_component)
violating_nodes <- same_value_vertices[isolated_nodes]
result_for_value$violation_count <- length(violating_nodes)
result_for_value$violating_nodes <- violating_nodes
} else {
result_for_value$violation_count <- 0
result_for_value$violating_nodes <- integer(0)
}
results[[paste0("value_", value)]] <- result_for_value
}
return(results)
}
check_all_connectivity(upgrade_graph(g))
Matrix Result
check_connectivity_matrix <- function(m, value) {
mask <- m == value
if (sum(mask) < 2) {
return(0)
}
visited <- matrix(FALSE, nrow = nrow(m), ncol = ncol(m))
coords <- which(mask, arr.ind = TRUE)
start_cell <- coords[1, ]
flood_fill <- function(i, j) {
if (i < 1 || i > nrow(m) || j < 1 || j > ncol(m) ||
visited[i, j] || m[i, j] != value) {
return()
}
visited[i, j] <<- TRUE
flood_fill(i-1, j)
flood_fill(i, j+1)
flood_fill(i+1, j)
flood_fill(i, j-1)
}
flood_fill(start_cell[1], start_cell[2])
violations <- sum(mask & !visited)
return(violations)
}
count_total_violations <- function(m) {
unique_values <- unique(as.vector(m))
total_violations <- 0
for (val in unique_values) {
violations <- check_connectivity_matrix(m, val)
total_violations <- total_violations + violations
}
return(total_violations)
}
total_violations <- count_total_violations(m)
print(total_violations)
It is not a directed graph. So any numbers which are once connected with the pool of "1"s or "2"s etc. are always connected with all the others in the pool. This makes the checking very easy.
m <- matrix(c(
1, 1, 1, 1, 1, 2,
1, 1, 1, 1, 2, 2,
1, 1, 1, 2, 2, 2,
1, 1, 1, 2, 3, 2,
1, 1, 1, 1, 3, 3,
1, 1, 1, 1, 3, 3
), nrow = 6, byrow = TRUE)
# the column and row names are the names or the nodes
# in this case, index and names are the same
colnames(m) <- 1:ncol(m)
rownames(m) <- 1:nrow(m)
We can check whether any in the column have the allowed_values (e.g. c(1) or c(2), ... - it could be also c(1, 2) or c(2, 3), etc. - which would stand for 1 or 2 in the first case, 2 or 3 in the second case etc.
is_connected <- function(mat, allowed_values=c(1)) {
df <- as.data.frame(mat)
matches <- lapply(allowed_values, function(val) df == val)
if (length(matches) > 1) {
any_matches <- Reduce(`|`, matches)
} else {
any_matches <- matches[[1]]
}
sort(union(colnames(df)[sapply(as.data.frame(any_matches), any)],
rownames(df)[sapply(as.data.frame(t(any_matches)), any)]))
}
So all values which are connected by edges with the value 1 or 2 or 3 or a combination of those are:
> is_connected(m, allowed_values=1)
[1] "1" "2" "3" "4" "5" "6"
> is_connected(m, 2)
[1] "1" "2" "3" "4" "5" "6"
> is_connected(m, 3)
[1] "4" "5" "6"
> is_connected(m, c(2,3))
[1] "1" "2" "3" "4" "5" "6"
> is_connected(m, c(1,2))
[1] "1" "2" "3" "4" "5" "6"
> is_connected(m, c(1,2,3))
[1] "1" "2" "3" "4" "5" "6"
So you can see all 6 nodes are connected via "1" or "2". But "3" connects only the nodes 4, 5, 6.