CODEWITHSUNDEEP
ralgorithmgraphigraph
experimenter
experimenter

Reputation: 63

Bron-Kerbosch algorithm in R

I want to implement Bron-Kerbosch algorithm in igraph manually. I want to replicate the example with the graph from Wikipedia page. This is the solution I came up with so far.

library(igraph)
g <- graph.formula(1-2,1-5,5-2,2-3,3-4,4-5,4-6)
P <- as.vector(V(g))
bron_kerbosch <- function(R,P,X) {

    if (length(P) == 0 && length(X) == 0) {
        print (R)
    } else {
        for (v in P) {
            neis <- as.vector(neighbors(g,v))
            bron_kerbosch(union(R,v),intersect(P,neis),intersect(X,neis))
            P <- c(P[-which(P==v)])
            X <- c(X,v)
        }
    }
}
> bron_kerbosch(c(),P,c())
[1] 1 2 3
[1] 2 4
[1] 3 5
[1] 4 5
[1] 5 6

And the answer should be: [[1, 2, 5], [2, 3], [3, 4], [4, 5], [4, 6]] I am indexing from 1, not from 0. Any idea what I'm doing wrong?

Upvotes: 1

Views: 421

Answers (1)

experimenter
experimenter

Reputation: 63

And I've just found the solution. I used the indices of g graph, instead of names :/. So I changed two lines:

 P <- V(g)$name
 neis <- neighbors(g,v)$name

This will work now with characters instead of numbers. And the result:

 [1] "1" "2" "5"
 [1] "2" "3"
 [1] "5" "4"
 [1] "3" "4"
 [1] "4" "6"

So the vertices are not ordered (5,4) should be (4,5) but I think it doesn't matter much. However it should be good to write this to integer numbers, instead of chars.

Upvotes: 2

Related Questions