Hypergraph isomorphic copy search¶
This module implements a code for the following problem:
INPUT: two hypergraphs
OUTPUT: a copy of
in
It is also possible to enumerate all such copies, and to require that such copies be induced copies. More formally:
A copy of
in
is an injection
such that for any set
we have
.
It is an induced copy if no other set of
is contained in
, i.e.
.
The functions implemented here lists all such injections. In particular, the
number of copies of in itself is equal to
.
The feature is available through
IncidenceStructure.isomorphic_substructures_iterator()
.
Implementation¶
A hypergraph is stored as a list of edges, each of which is a “dense” bitset
over points. In particular, two sets of distinct cardinalities
require the same memory space. A hypergraph is a C struct with the following
fields:
n,m
(int
) – number of points and edges.limbs
(int
) – number of 64-bits blocks per set.set_space
(uint64_t *
) – address of the memory used to store the sets.sets
(uint64_t **
) –sets[i]
points toward thelimbs
blocks encoding set. Note also that
sets[i][limbs]
is equal to the cardinality ofset[i]
, so thatsets
has lenthm*(limbs+1)*sizeof(uint64_t)
.names
(int *
) – associates an integer ‘name’ to each of then
points.
The operations used on this data structure are:
void permute(hypergraph * h, int n1, int n2)
– exchanges pointsand
in the data structure. Note that their names are also exchanged so that we still know which is which.
int induced_hypergraph(hypergraph * h1, int n, hypergraph * tmp1)
– stores intmp1
the hypergraph induced by the firstpoints, i.e. all sets
such that
. The function returns the number of such sets.
void trace_hypergraph64(hypergraph * h, int n, hypergraph * tmp)
– stores intmp1
the trace ofon the first
points, i.e. all sets of the form
.
Algorithm¶
We try all possible assignments of a representant for every
. When we have picked a representant for the first
points
, we check that:
- The hypergraph induced by the (ordered) list
in
is equal to the one induced by
in
.
- If
is contained in
sets of size
in
, then
is contained in
sets of size
in
. This is done by comparing the trace of the hypergraphs while remembering the original size of each set.
As we very often need to build the hypergraph obtained by the trace of the first
points (for all possible
), those hypergraphs are cached. The hypergraphs
induced by the same points are handled similarly.
Limitations¶
Number of points For efficiency reason the implementation assumes that
has
points. Making this work for larger values means that calls to
qsort
have to be replaced by calls to qsort_r
(i.e. to sort the edges
you need to know the number of limbs per edge) and that induces a big slowdown
for small cases (~50% when this code was implemented). Also, 64 points for
is already very very big considering the problem at hand. Even
seems too much.
Vertex ordering The order of vertices in has a huge influence on the
performance of the algorithm. If no set of
contains more that one of the
first
points, then almost all partial assignments of representants are
possible for the first
points (though the degree of the vertices is taken
into account). For this reason it is best to pick an ordering such that the
first vertices are contained in as many sets as possible together. A heuristic
is implemented at
relabel_heuristic()
.
AUTHORS:
- Nathann Cohen (November 2014, written in various airports between Nice and Chennai).
Methods¶
-
class
sage.combinat.designs.subhypergraph_search.
SubHypergraphSearch
¶ Bases:
object
-
relabel_heuristic
()¶ Relabels
in order to make the algorithm faster.
Objective: we try to pick an ordering
of the points of
that maximizes the number of sets involving the first points in the ordering. One way to formalize the problems indicates that it may be NP-Hard (generalizes the max clique problem for graphs) so we do not try to solve it exactly: we just need a sufficiently good heuristic.
Assuming that the first points are
, we determine
as the point
such that the number of sets
with
and
is maximal. In case of ties, we take a point with maximum degree.
This function is called when an instance of
SubHypergraphSearch
is created.EXAMPLE:
sage: d = designs.projective_plane(3) sage: d.isomorphic_substructures_iterator(d).relabel_heuristic()
-