CODEWITHSUNDEEP
rcyclechord
Tomas Marina
Tomas Marina

Reputation: 73

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!

Upvotes: 2

Views: 495

Answers (2)

Vincent Guillemot
Vincent Guillemot

Reputation: 3429

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!

Upvotes: 2

gfgm
gfgm

Reputation: 3647

Here is another approach. Although probably not a very efficient way to do it algorithmically, it has the merit of drawing on fast native igraph routines. The basic strategy is:

  1. Find all cycles of length 4

  2. Find all triangles

  3. If a length-4 cycle shares 3 nodes with a triangle its not chordless so we get rid of it and return what's left.

Below is a function, then we can test it on a easy to interpret artificial graph, and a random graph:

library(igraph)

getChordless4s <- function(g) {
  # Add names to save on annoyance later
  if (is.null(names(V(g)))) {V(g)$name <- V(g)}
  # We get all the triangles
  tr <- triangles(g)
  tr <- matrix(names(tr), nrow=length(tr)/3, byrow = T)
  # Now we get all the cycles of length-4
  g2 <- make_ring(4)
  res <- subgraph_isomorphisms(pattern = g2, target = g)
  # strip these to the node names and drop reduncancies
  res <- unique(lapply(res, function(cyc){sort(names(cyc))}))
  # If one of our triangles appears in a length-4 cycle than 
  # that cycle is not chordless. 
  # Test for this by checking if the length of the intersection of the vertex
  # names of the 4-cycle and any triangle is 3.
  res <- res[!unlist(lapply(res, function(cyc){any(apply(tr, 1, function(row){length(intersect(cyc, row))==3}))}))]
  # Print anything we have if we have it
  if (length(res)==0) {cat("No chordless cycles of length-4 found")} else {
    res
  }
}

Now lets generate a toy graph where we should be clear what the expected result should be:

g <- graph_from_data_frame(data.frame(from = c("A", "B", "C", "D", "A", "E", "E", "F"), 
                                      to = c("B", "C", "D", "A", "E", "D", "F", "D")),
                           directed = F)
plot(g)

We clearly want the function to return A-B-C-D and not A-D-E-F:

getChordless4s(g)
#> [[1]]
#> [1] "A" "B" "C" "D"

Now let's try a random graph:

set.seed(42)
g <- random.graph.game(10, .2)
plot(g)


# Check that there are chordless graphs to find
is.chordal(g)$chordal
#> [1] FALSE

getChordless4s(g)
#> [[1]]
#> [1] "2" "3" "7" "8"
#> 
#> [[2]]
#> [1] "2" "3" "6" "7"
#> 
#> [[3]]
#> [1] "2" "3" "5" "7"
#> 
#> [[4]]
#> [1] "3" "5" "7" "8"
#> 
#> [[5]]
#> [1] "3" "5" "6" "7"

There's probably some published algorithm on efficient ways of finding chordless cycles, and now I'd be curious to know what it is. Fun problem.

Created on 2018-05-09 by the reprex package (v0.2.0).

Upvotes: 2

Related Questions