Opened 6 years ago

Last modified 6 years ago

#17309 closed enhancement

SubHypergraphSearch — at Initial Version

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.4
Component: combinatorial designs Keywords:
Cc: jmantysalo, dimpase, vdelecroix, Stefan Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges


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 into a way to deal with another definition of "substructure" and compute things like the VC-dimension, in case somebody cares.

Change History (0)

Note: See TracTickets for help on using tickets.