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 want to check if its possible for all 1's to reach all other 1's without stepping on a 2 or 3
• I want to check if its possible for all 2's to reach all other 2's without stepping on a 1,3
• I want to check if its possible for all 3's to reach all other 3's without stepping on a 1,2

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)

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 want to check if its possible for all 1's to reach all other 1's without stepping on a 2 or 3
• I want to check if its possible for all 2's to reach all other 2's without stepping on a 1,3
• I want to check if its possible for all 3's to reach all other 3's without stepping on a 1,2

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)

• r
• igraph

• 1 Regarding your included example, dput(g) does not really generate reproducible graph object. If it's relevant, please consider including code to generate it from your input data. – margusl Commented Mar 16 at 8:23
• Is this about implementing your own breadth-first search on a matrix? Or, guessing from igraph tag, building graph from a matrix so you could use your current solution? Or something else? – margusl Commented Mar 16 at 12:14
• I traide on my M3 mac. Your structure seems to be created with an old version of igraph. I had to run g <- upgrade_graph(g) on that before plot(g). So which igraph version do you have? run sessionInfo(). I have igraph_2.1.4 – Gwang-Jin Kim Commented Mar 16 at 14:25
• 1 @TimG, while I think many data handling/analysis could benefit from terra processes, assuming a 2D upon a graph which lacks support above 1D wouldn't directly answer the 'is connected' question beyond should/could/appears to be. Like your work. – Chris Commented Mar 16 at 15:21
• 2 I am not very motivated to look at this, as you don't seem to have the habit of marking answers as accepted. – trincot Commented Mar 16 at 15:30

1 Answer 1

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.