I'm trying to detect some minimal patterns with properties in random digraphs. Namely, I have a list called patterns of adjacency matrix of various size. For instance, I have [0] (a sink), but also a [0100 0001 1000 0010] (cycle of size 4), [0100, 0010, 0001, 0000] a path of length 3, etc.
When I generate a digraph, I compute all sets that may be new patterns. However, in most of the case it is something that I don't care about: for instance, if the potential new pattern is a cycle of size 5, it does not teach me anything because it has a cycle of length 3 as an induced subgraph.
I suppose one way to do it would look like this:
#D is the adjacency matrix of a possible new pattern
new_pattern = True
for pi in patterns:
k = len(pi)
induced_subgraphs = all_induced_subgraphs(D, k)
for s in induced_subgraphs:
if isomorphic(s, pi):
new_pattern = False
break
where all_induced_subgraphs(D,k) gives all possible induced subgraphs of D of size k, and isomorphic(s,pi) determines if s and pi are isomorphic digraphs.
However, checking all induced subgraphs of a digraph seems absolutely horrible to do. Is there a clever thing to do there?
Thanks to @Stef I learned that this problem has a name and can be solved using on netwokx with a function described on this page.
Personally I use igraph on my project so I will use this.