rcyclechord

Number of chordless cycles of length four in a graph in R

I am trying to count the number of chordless cycles of length four in an undirected graph using R (igraph package).
This is my adyacency matrix (with '0' and integer numbers > 1, since it represents the number of shared objects between nodes):

0   8   4   10  7   11  1   
3   1   0   0   0   0   0   
0   0   0   0   0   0   0   
0   0   0   0   0   0   0   
0   0   0   0   0   0   0   
0   0   5   0   2   0   1   
9   0   1   1   0   0   1

This is the piece of code I have: 

library(igraph)
A <- matrix(c(0L, 3L, 0L, 0L, 0L, 0L, 9L, 
              8L, 1L, 0L, 0L, 0L, 0L, 0L, 
              4L, 0L, 0L, 0L, 0L, 5L, 1L, 
              10L, 0L, 0L, 0L, 0L, 0L, 1L, 
              7L, 0L, 0L, 0L, 0L, 2L, 0L, 
              11L, 0L, 0L, 0L, 0L, 0L, 0L, 
              1L, 0L, 0L, 0L, 0L, 1L, 1L), 
            7, 7) 
g <- graph.adjacency(A, mode = "undirected", diag=FALSE, weighted=TRUE)

Any help with this would be much appreciated!

Solution

  • TL;DR: the answer is 0, because the graph is cordal.

    The graph itself looks like this:

    Graph

    From the look of this graph, I'm not very optimistic we will find a chordless cycle of length four. And this can be quickly confirmed by this command:

    is.chordal(g)

    It returns TRUE, which means that this graph is chordal. In other words, "each of its cycles of four or more nodes has a chord".

    I attempted anyway to enumerate all the chordless cycles of lenght 4. Since I don't know any smart way of doing it, I will do it with a few simpler steps:

    1. Find all the simple paths from one node of the graph to any other;
    2. Keep only the paths of length 4;
    3. Check if the last node of this path is connected to the starting node, if it is, then keep this path;
    4. Extract all the subgraphs corresponding to the paths I kept;
    5. Check if they are chordal.

    Each of these steps can be performed with a function from the igraphpackage.

    res <- NULL
for (vi in V(g)) {
  pi <- all_simple_paths(g, from=vi, to = V(g))
  pi_4 <- pi[sapply(pi, length)==4]
  last_v <- sapply(pi_4, "[", 4)
  pi_4_c <- pi_4[sapply(last_v, function(v) are.connected(g, 1, v))]
  subgi <- lapply(pi_4_c, function(v) induced.subgraph(g, v))
  ci <- sapply(subgi, function(g) is_chordal(g)$chordal)
  res[[vi]] <- subgi[!ci]
}
res_with_dupl <- data.frame(t(sapply(res, V)))
unique(res_with_dupl)

    Again, the result is that there is no chordless cycle of length 4 in this graph (res is empty).

    I really look forward to reading the other answers!