Generate non-redundant graph patterns

60 Views Asked by At

I'm trying to generate all possible non-redundant patterns of a complete graph with 4 nodes, using different combinations of nodes. I want to get the linear form of the graph patterns, eg: A-B-C-D.

Kn complete graph

complete graph pattern of 4 nodes

The nodes can be repeated objects, for example, E-E-E-E. For now, I want to test with E and R.

I tried generating patterns using itertools.combinations_with_replacement and I get 5 patterns:

patterns_comb = [''.join(i) for i in itertools.combinations_with_replacement(["E","R"],4)] 

The output is

['EEEE', 'EEER', 'EERR', 'ERRR', 'RRRR']

Then I use itertools.product and I get 16 patterns:

patterns_product = [''.join(i) for i in itertools.product(["E","R"],repeat=4)]

The output is:

['EEEE', 'EEER', 'EERE', 'EERR', 'EREE', 'ERER', 'ERRE', 'ERRR', 'REEE', 'REER', 'RERE', 'RERR', 'RREE', 'RRER', 'RRRE', 'RRRR']

I run a downstream analysis using these patterns. Using itertools.combinations_with_replacement lead to missing patterns that could be important. But when using itertools.product, there would be redundant patterns, i.e patterns that are producing similar results, so it would take a long time to complete the downstream analysis.

For example: ERRE gives the same output as REER (so both are actually the same pattern), and RERE gives the same output as ERER, EERR, RREE.

Is there any solution to get non-redundant patterns or to compare these patterns to see whether they are similar or not?

I tried using Networkx package to compare the edges but it is quite hard to compare because of repeated nodes.

0

There are 0 best solutions below