PyBoolNet.PrimeImplicants._percolation

[jgtz]

I noticed that when propagating fixed nodes, the resulting rules are not necessarily in the "sum of all possible prime implicants" form (Blake canonical form). So after

primes = PyBoolNet.FileExchange.bnet2primes(rules)

the rule is in the Blake canonical form, but after

PyBoolNet.PrimeImplicants._percolation(primes,True)

it might not. I don't expect that to necessarily be a problem, but it could be if the expanded network (and stable motifs) don't recalculate the functions to be in the Blake canonical form. Just wanted to check on this since I noticed it.

[jcrozum]

Can you give an example? Maybe we can make our own percolator function that avoids the issue. Recalculating the implicants is very slow.

And do we really need the Blake form? I think it's okay if we have extra terms, so long as we have all minterms in there somewhere, right?

[jgtz]

Example:

N=1000
K=3
p=sm.RandomBooleanNetworks.get_criticality_p_Kauffman(K)[0] 
N_ensemble=5
seed=1000
rbn_ensemble=sm.RandomBooleanNetworks.Random_Boolean_Network_Ensemble_Kauffman(N,K,p,N_ensemble,seed=seed,write_Boolean_network=True)
rules=rbn_ensemble[4]
rules = sm.Format.booleannet2bnet(rules)
primes = PyBoolNet.FileExchange.bnet2primes(rules)
print("Prime implicants before reduction for n87: "+str(primes['n87'][0]))
PyBoolNet.PrimeImplicants._percolation(primes,True)
print("Prime implicants after reduction for n87: "+str(primes['n87'][0]))
print("The prime implicant should only be [{'n907': 0}] if the latter was simplified")

Output

Prime implicants before reduction for n87: [{'n774': 1, 'n907': 0}, {'n324': 0, 'n907': 0}]
Prime implicants after reduction for n87: [{'n907': 0}, {'n324': 0, 'n907': 0}]
The prime implicant should only be [{'n907': 0}] if the latter was simplified

[jcrozum]

Ok, thanks for the example. I am 99% sure that this will not cause any issues with the stable motif identification, at least not in examples like this one. We should keep thinking about this though. If you ever find a case where this leads to the wrong stable motif result, please post it.

[jgtz]

Will keep in mind if I see something. I do know it can sometimes be expensive to calculate it.

Not sure what you mean with "have all minterms"? The Blake canonical form includes only the non-reducible prime implicants, so each implicant can't be reduced. Or do you mean, the minimal number of prime implicants that fully define the same function?

I know the Blake canonical form is needed for stable motifs, or we can find some non-minimal stable motifs and miss the actual "minimal" stable motifs. I do think PyBoolNet calculates it using the correct prime implicant Boolean function, so I am not worried about that (I think I remember from their paper and/or discussions I had with them that they use the blake canonical form).

I am more more wondering if we might be missing some node/edges simplifications, like in the example above. Also, for the LDOI to work the way it should (hypergraph paths), we need to work on the expanded network with the blake canonical form or we can miss some paths.

[jcrozum]

Sorry, I meant that I think the rule will l always look like like the BCF terms + some extra stuff, and if that's the case, I don't think we'll have any problems.

[jgtz]

I tried to build some counter-examples, but I think you're right. It would seem that, given a BCF, fixing any subset of the variables results in the BCF of the reduced function + some extra terms. I had never realized this was the case.

[jgtz]

Given that the above is the case, I will close this.