#17309: SubHypergraphSearch
-------------------------+-------------------------------------------------
Reporter: | Owner:
ncohen | Status: needs_review
Type: | Milestone: sage-6.4
enhancement | Resolution:
Priority: major | Merged in:
Component: | Reviewers:
PLEASE CHANGE | Work issues:
Keywords: | Commit:
Authors: | 9d3d155b6481ce8d76683b192d1bee6d7ee223a2
Nathann Cohen | Stopgaps:
Report Upstream: N/A |
Branch: |
u/ncohen/17309 |
Dependencies: |
-------------------------+-------------------------------------------------
Description changed by ncohen:
Old description:
> 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.
New description:
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.
--
--
Ticket URL: <http://trac.sagemath.org/ticket/17309#comment:4>
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.
