获取有向图的所有组合组合

Question

我正在从邻接矩阵中寻找有向图的所有可能组合

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)

这是创建的图表：

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

所有的组合都是可行解吗？不行，作为有向图，所有的前辈都必须在解中。

    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

所以从 16 组合我保持 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

Answer 1

我无法复制您的示例，因此让我们假设所提供的第二个矩阵称为解决方案。那么也许这可行。

它很慢，所以如果它适合你，你绝对可以让它更快。

## 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

获取有向图的所有组合组合

Get all combination of combinations of a directed graph

r

directed-acyclic-graphs

adjacency-matrix