Get all combination of combinations of a directed graph

I have this code:

library(igraph)

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

# Create a directed graph
network <- graph_from_adjacency_matrix(as.matrix(adjacency_matrix),mode = "directed")

It's there a way to get all combinations that meet all the conditions of the parents? For example, in my case there are 2^5 = 32 possible combination but all don't meet the conditions of a directed graph.

Welcome @jsl907!

Can you say more about what mean by "meet all the conditions of the parents"? What would the expected output be for the example you provided?

Is either of these the type of output you are trying to achieve?

library(tidyverse)

adjacency_matrix %>% 
  rownames_to_column(var="row") %>% 
  gather(col, value, -row) %>% 
  filter(value==1)
  row col value
1   A   C     1
2   A   D     1
3   B   D     1
4   C   E     1
which(adjacency_matrix==1, arr.ind=TRUE)
  row col
A   1   3
A   1   4
B   2   4
C   3   5

Sorry for not explaining it well, it can be a bit confusing.

Being a directed graph, all combinations may not be possible, for example:

# Only have D 
A B C D E
0 0 0 1 0

This is not a feasible solution since D has as father A and B. A feasible solutions will be:

A B C D E
1 1 0 1 0
1 1 0 0 0
1 0 1 0 1

And this for all posible combinations.

1 Like

So you want to identify all possible directed graphs that can be constructed from n nodes, where n=5 in this case?

Yes, always keeping in mind all adjacencies.

1 Like

I guess I'm still not understanding the problem statement. Are we starting with the specific adjacency matrix you provided and then enumerating all valid directed graphs that can be generated from it? Or are we enumerating all possible directed graphs that can be generated from five distinguishable vertices?

It would be helpful if you could provide the expected output for your example. Or, if it would be easier, create a smaller example (one that has fewer possible combinations) and show us the starting adjacency matrix and the expected output (all of the expected combinations).

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

Untitled%20Diagram

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
1 Like

This topic was automatically closed 21 days after the last reply. New replies are no longer allowed.