Opened 6 years ago

Last modified 6 years ago

#17309 closed enhancement

SubHypergraphSearch — at Version 4

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.4
Component: combinatorial designs Keywords:
Cc: jmantysalo, dimpase, vdelecroix, Stefan Merged in:
Authors: Nathann Cohen Reviewers:
Report Upstream: N/A Work issues:
Branch: u/ncohen/17309 (Commits, GitHub, GitLab) Commit: 9d3d155b6481ce8d76683b192d1bee6d7ee223a2
Dependencies: Stopgaps:

Status badges

Description (last modified by 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.

Change History (4)

comment:1 Changed 6 years ago by ncohen

  • Authors set to Nathann Cohen
  • Branch set to u/ncohen/17309
  • Cc jmantysalo dimpase vdelecroix Stefan added
  • Status changed from new to needs_review

comment:2 Changed 6 years ago by git

  • Commit set to 4c163fcba5cf78e2582408bcdb33d0f5dd3b6158

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

4c163fctrac #17309: SubHypergraphSearch

comment:3 Changed 6 years ago by git

  • Commit changed from 4c163fcba5cf78e2582408bcdb33d0f5dd3b6158 to 9d3d155b6481ce8d76683b192d1bee6d7ee223a2

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

9d3d155trac #17309: SubHypergraphSearch

comment:4 Changed 6 years ago by ncohen

  • Description modified (diff)
Note: See TracTickets for help on using tickets.