SubHypergraphSearch

[ncohen]

At long long long long last.

I have been wanting to write this for ages but never really needed it. And one should never implement something unless one needs it.

Here it is. It does what SubgraphSearch already does for graphs, but it does it for hypergraphs. The code is just a simple eunmeration of all possibilities, with a couple of cuts. The implementation tries to make this as cheap as possible.

We now have a IncidenceStructure.isomorphic_substructures_iterator whose name is similar to the new Poset.has_isomorphic_subposet.

Oh, and it does not work if the pattern you try to find had >64 points. It is already very large considering how hard it is to run this code anyway, plus making it work for >64 implied a +50% cost even for small instances on my use case. So I thought it was not worth it.

Right now it handles induced and non-induced hypergraph. Later, in another patch, it can be improved to deal with another definition of "substructure" and compute things like the VC-dimension, in case somebody cares.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​4c163fc

trac #17309: SubHypergraphSearch

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​9d3d155

trac #17309: SubHypergraphSearch