CODEWITHSUNDEEP
rdirected-acyclic-graphsadjacency-matrix
Dragg
Dragg

Reputation: 83

Get all combination of combinations of a directed graph

I'm looking for all possible combinations of a directed graph from a adjacency matrix

adjacency_matrix <- read.table(text = "A B C D
A   0   0   1   0
B   0   0   1   0
C   0   0   0   1
D   0   0   0   0", header = TRUE)

This is the created graph:

Graph

How many combination can be do with n=4? 2^4=16

    A    B    C    D
1   1    1    1    1
2   0    1    1    1
3   1    0    1    1
4   0    0    1    1
5   1    1    0    1
6   0    1    0    1
7   1    0    0    1
8   0    0    0    1
9   1    1    1    0
10  0    1    1    0
11  1    0    1    0
12  0    0    1    0
13  1    1    0    0
14  0    1    0    0
15  1    0    0    0
16  0    0    0    0

All combinations are a feasible solution? No, being a directed graph, all the predecessors must be in the solution.

    A    B    C    D
1   1    1    1    1 #GOOD
2   0    1    1    1 #BAD, for choose C, all of his predecessors must be in the solution: A and B
3   1    0    1    1 #BAD, for choose C , must be A and B
4   0    0    1    1 #BAD, for choose C, must be A and B, for choose D must be in the solution: A,B and C
5   1    1    0    1 #BAD, for choose D, must be C and all his predecessors 
6   0    1    0    1 #BAD, for choose D, must be C and all his predecessors 
7   1    0    0    1 #BAD, for choose D, must be C and all his predecessors 
8   0    0    0    1 #BAD, for choose D, must be all his predecessors 
9   1    1    1    0 #GOOD
10  0    1    1    0 #BAD, for choose C, must be all his predecessors 
11  1    0    1    0 #BAD, for choose C, must be all his predecessors 
12  0    0    1    0 #BAD, for choose C, must be all his predecessors 
13  1    1    0    0 #GOOD
14  0    1    0    0 #GOOD
15  1    0    0    0 #GOOD
16  0    0    0    0 #GOOD

So from 16 combination I keep with 6:

    A    B    C    D
1   1    1    1    1 #GOOD
9   1    1    1    0 #GOOD
13  1    1    0    0 #GOOD
14  0    1    0    0 #GOOD
15  1    0    0    0 #GOOD
16  0    0    0    0 #GOOD

Upvotes: 1

Views: 477

Answers (1)

JacobJacox
JacobJacox

Reputation: 947

I cannot replicate your example so lets assume that the second matrix presented is called solution. Then maybe this could work.

It is slow, so if it works for you, you can definitely make it faster.

## create your solution
nodes_rank <- c(1,1,2,3)
## nodes rank is same order as your position matrix so A,B,C,D

solution <- matrix(
  c(rep(c(1,0),8),rep(c(1,1,0,0),4), rep(c(rep(1,4),rep(0,4)),2), rep(1,8),rep(0,8) ),
  ,nrow = 16,ncol=4,byrow = F)

check <- function(x){
  for(i in 1:length(x)){
    if(x[i]==1){ ## we want to have certain node
      if(nodes_rank[i]==1){
        #pass -- no worries about node rank 1
      }else{
        # all of previous must be also in
        current_node_rank <- nodes_rank[i]
        ## check if you got all the previous
        have_to_be_in <- which(nodes_rank < current_node_rank)
        are_in <- which(x[1:i]==1) ## we take i so we avoid looping errors
        if(!all(have_to_be_in %in% are_in)){
          return(F) ## if we catch something that we shouldnt break
        }
      }
    }
  }
  return(T) ## all works out its ok
}

index <- apply(solution,1,check)

solution[index,]
     [,1] [,2] [,3] [,4]
[1,]    1    1    1    1
[2,]    1    1    1    0
[3,]    1    1    0    0
[4,]    0    1    0    0
[5,]    1    0    0    0
[6,]    0    0    0    0

Upvotes: 1

Related Questions