#17309: SubHypergraphSearch
-----------------------------+----------------------------
Reporter: ncohen | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.4
Component: PLEASE CHANGE | Keywords:
Merged in: | Authors:
Reviewers: | Report Upstream: N/A
Work issues: | Branch:
Commit: | Dependencies:
Stopgaps: |
-----------------------------+----------------------------
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.
--
Ticket URL: <http://trac.sagemath.org/ticket/17309>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
