SubHypergraphSearch

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

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.

CC: @jm58660 @dimpase @videlec @sagetrac-Stefan

Component: combinatorial designs

Author: Nathann Cohen

Branch/Commit: 5d7a241

Reviewer: Dima Pasechnik

Issue created by migration from https://trac.sagemath.org/ticket/17309

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Branch: u/ncohen/17309

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Author: Nathann Cohen

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

4c163fc

trac #17309: SubHypergraphSearch

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Commit: 4c163fc

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

9d3d155

trac #17309: SubHypergraphSearch

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 4c163fc to 9d3d155

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Description changed:

--- 
+++ 
@@ -8,4 +8,4 @@

 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.
+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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

3688bdb	trac #17309: SubHypergraphSearch
6b4eceb	trac #17309: Caching the traces and induced subgraphs of h2

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 9d3d155 to 6b4eceb

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

ae1f014	trac #17309: SubHypergraphSearch
8e8bde1	trac #17309: Caching the traces and induced subgraphs of h2
6f2f204	trac #17309: Bugfix

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 6b4eceb to 6f2f204

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 6f2f204 to 82b928a

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

82b928a

trac #17309: SubHypergraphSearch

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:9

(it was conflicting with the latest beta)

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:10

Guys ?... This feature is really cool, I swear. Plus you probably will not find it anywhere else..

[dimpase]

comment:11

Do you iterate over embeddings of H in G, factoring out the automorphisms of H? (i.e. if f is an automorphism of H, and g an embedding of H, do distinguish g(H) and g(H^f) ?)

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:12

No, this code does not. It enumerates all labelled copies, and the number of copies of H that you will find in H is |aut(H)|.

[dimpase]

comment:13

Replying to @nathanncohen:

No, this code does not. It enumerates all labelled copies, and the number of copies of H that you will find in H is |aut(H)|.

it should say distinct copies, or even distinct (unlabelled) copies.

[dimpase]

comment:14

The stuff should be tested on a 32-bit system, just to make sure there is no arch-specific bugs...

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:15

The stuff should be tested on a 32-bit system, just to make sure there is no arch-specific bugs...

Well, you can if you have one but I tried to be careful with respect to that and explicitly wrote uint64_t when I needed a 64-bits integer. Usually the 'int' variables that I use represent the vertex of a hypergraph, so I do not think that it will overflow anytime soon :-P

[dimpase]

comment:16

Trying out the patch, I get

Error building the documentation.
Traceback (most recent call last):
  File "/home/dima/software/sage/src/doc/common/builder.py", line 1623, in <module>
    getattr(get_builder(name), type)()
  File "/home/dima/software/sage/src/doc/common/builder.py", line 296, in _wrapper
    getattr(get_builder(document), name)(*args, **kwds)
  File "/home/dima/software/sage/src/doc/common/builder.py", line 503, in _wrapper
    x.get(99999)
  File "/home/dima/software/sage/local/lib/python/multiprocessing/pool.py", line 558, in get
    raise self._value
OSError: [combinat ] /home/dima/software/sage/local/lib/python2.7/site-packages/sage/combinat/designs/__init__.py:docstring of sage.combinat.designs.__init__:32: WARNING: undefined label: sage.combinat.designs.subhypergraph_search (if the link has no caption the label must precede a section header)

make: *** [doc-html] Error 1

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

dad6191	trac #17309: SubHypergraphSearch
c0d1d1f	trac #17309: Broken doc and typo

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 82b928a to c0d1d1f

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:18

That's because the documentation of the combinat/ folder now work in a different way from the rest of Sage's doc. It is meant to be distributed with no central index of files, and I had forgotten to add my new file to the new index of files it creates.

I also changed 'disjoint' into 'distinct unlabelled', and rebased everything on the latest beta.

Nathann

[dimpase]

comment:19

+ As the automorphism group of `C_5` has size 10, the number of distinct
+ labelled copies is 12. 

it should say unlabelled

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

d83413a

trac #17309: Broken doc and typo

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c0d1d1f to d83413a

[dimpase]

Reviewer: Dima Pasechnik

[dimpase]

comment:21

Replying to @nathanncohen:

The stuff should be tested on a 32-bit system, just to make sure there is no arch-specific bugs...

Well, you can if you have one but I tried to be careful with respect to that and explicitly wrote uint64_t when I needed a 64-bits integer. Usually the 'int' variables that I use represent the vertex of a hypergraph, so I do not think that it will overflow anytime soon :-P

OK, it works both on 64 and 32 bit (arando is still alive). LGTM.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:22

Wow ! Thank you very much.

Nathann

[vbraun]

comment:23

I got this on OSX:

sage -t --long src/sage/combinat/designs/incidence_structures.py
**********************************************************************
File "src/sage/combinat/designs/incidence_structures.py", line 586, in sage.combinat.designs.incidence_structures.IncidenceStructure.isomorphic_substructures_iterator
Failed example:
    sum(1 for _ in IP.isomorphic_substructures_iterator(IC))
Expected:
    120
Got:
    0
**********************************************************************
File "src/sage/combinat/designs/incidence_structures.py", line 598, in sage.combinat.designs.incidence_structures.IncidenceStructure.isomorphic_substructures_iterator
Failed example:
    sum(1 for _ in IP.isomorphic_substructures_iterator(IC,induced=True))
Expected:
    120
Got:
    0
**********************************************************************
File "src/sage/combinat/designs/incidence_structures.py", line 606, in sage.combinat.designs.incidence_structures.IncidenceStructure.isomorphic_substructures_iterator
Failed example:
    sum(1 for _ in IP.isomorphic_substructures_iterator(IC))
Expected:
    420
Got:
    0
**********************************************************************
File "src/sage/combinat/designs/incidence_structures.py", line 608, in sage.combinat.designs.incidence_structures.IncidenceStructure.isomorphic_substructures_iterator
Failed example:
    sum(1 for _ in IP.isomorphic_substructures_iterator(IC,induced=True))
Expected:
    60
Got:
    0
**********************************************************************
File "src/sage/combinat/designs/incidence_structures.py", line 615, in sage.combinat.designs.incidence_structures.IncidenceStructure.isomorphic_substructures_iterator
Failed example:
    sum(1 for _ in H.isomorphic_substructures_iterator(H))
Expected:
    5616
Got:
    1
**********************************************************************
1 item had failures:
   5 of  16 in sage.combinat.designs.incidence_structures.IncidenceStructure.isomorphic_substructures_iterator
    [287 tests, 5 failures, 2.07 s]

Just as a stab in the dark, this is often a sign of comparisons by memory location somewhere. Somehow many Python objects end in different orders in ram on OSX.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:25

Can you give me access to an OSX machine ? I can't debug in the dark.

Nathann

[dimpase]

comment:26

Replying to @nathanncohen:

Can you give me access to an OSX machine ? I can't debug in the dark.

If you can't find an OSX machine around, I can hook up a spare laptop running OSX so that you can ssh into it.Hopefully this will be fast enough. Do you still have access to arando box? Anyhow, you will need to ssh into arando, and from it to the laptop. I'll have to figure out how to make ssh from laptop persistent.

Dima

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:27

Hello,

If you can't find an OSX machine around, I can hook up a spare laptop running OSX so that you can ssh into it.Hopefully this will be fast enough. Do you still have access to arando box? Anyhow, you will need to ssh into arando, and from it to the laptop.

I just tried again the instructions you gave me on the 13/06/13 to connect to arando, but I got the following (on boxen):

ncohen@boxen:~$ ssh -p21925 localhost
ssh: connect to host localhost port 21925: Connection refused

A colleague of mine who has a Mac laptop "may" come in the afternoon. And if she is willing I "could" take it from her for a while, and compile Sage from its sources and stuff.

But really it would be cool if the same machine that Volker uses for his tests could be used for debugging, because really it is very very troublesome to get some code to work on an architecture that I do not have access to.

Nathann

[vbraun]

comment:28

I can give you access, just email me your ssh key. The box is not always on, so let me know when you need it.

[dimpase]

comment:29

Replying to @vbraun:

I can give you access, just email me your ssh key. The box is not always on, so let me know when you need it.

I think we're all set, Nathann uses an OSX laptop I hooked up via arando. At least it's not under any other load.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:30

I have spent severa hours on this bug, and all I can say right now is that after a call to qsort, what is sorted on my machine is not sorted on the OSX machine.

[vbraun]

comment:31

Sounds like your comparison function is not a total order. This is illegal, and qsort behavior will be undefined (and different depending on the algorithm used by qsort, its often not quick sort but depends on the size of the input etc.).

[dimpase]

comment:32

  The comparison function must return an integer less than, equal to, or greater than zero if the first
     argument is considered to be respectively less than, equal to, or greater than the second.

and you return True/False!

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from d83413a to 5d7a241

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

5d7a241

trac #17309: Mac OS X ...

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:34

and you return True/False!

That was it. The function returned 1 or 0, and Linux seemed to do the job alright with that. Mac OS X did not.

Nathann

[vbraun]

Changed branch from u/ncohen/17309 to 5d7a241