Ok, I will show you with a directed graph with 4 nodes.
library(igraph)
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
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