SubHypergraphSearch #17309

nathanncohen · 2014-11-08T16:45:39Z

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

The text was updated successfully, but these errors were encountered:

nathanncohen · 2014-11-08T16:46:39Z

Branch: u/ncohen/17309

nathanncohen · 2014-11-08T16:46:39Z

Author: Nathann Cohen

sagetrac-git · 2014-11-08T16:54:49Z

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

`4c163fc`	`trac #17309: SubHypergraphSearch`

sagetrac-git · 2014-11-08T16:54:49Z

Commit: 4c163fc

sagetrac-git · 2014-11-08T17:02:47Z

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

`9d3d155`	`trac #17309: SubHypergraphSearch`

sagetrac-git · 2014-11-08T17:02:47Z

Changed commit from 4c163fc to 9d3d155

sagetrac-git · 2014-11-16T10:02:17Z

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`

sagetrac-git · 2014-11-16T10:02:17Z

Changed commit from 9d3d155 to 6b4eceb

sagetrac-git · 2014-11-26T15:23:07Z

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`

sagetrac-git · 2014-11-26T15:23:07Z

Changed commit from 6b4eceb to 6f2f204

sagetrac-git · 2014-12-25T15:45:20Z

Changed commit from 6f2f204 to 82b928a

sagetrac-git · 2014-12-25T15:45:20Z

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

`82b928a`	`trac #17309: SubHypergraphSearch`

nathanncohen · 2014-12-25T15:45:38Z

comment:9

(it was conflicting with the latest beta)

nathanncohen · 2015-02-24T14:43:50Z

comment:10

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

dimpase · 2015-02-25T09:36:23Z

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) ?)

nathanncohen · 2015-02-25T09:38:07Z

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 · 2015-02-25T10:05:58Z

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 · 2015-02-25T10:41:32Z

comment:14

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

nathanncohen · 2015-02-25T10:43:34Z

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 · 2015-02-25T10:45:14Z

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

sagetrac-git · 2015-02-25T10:51:31Z

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`

sagetrac-git · 2015-02-25T10:51:31Z

Changed commit from 82b928a to c0d1d1f

nathanncohen · 2015-02-25T10:53:05Z

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 · 2015-02-25T10:53:38Z

comment:19

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

it should say unlabelled

sagetrac-git · 2015-02-25T10:54:30Z

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

`d83413a`	`trac #17309: Broken doc and typo`

sagetrac-git · 2015-02-25T10:54:30Z

Changed commit from c0d1d1f to d83413a

dimpase · 2015-02-25T11:53:23Z

Reviewer: Dima Pasechnik

dimpase · 2015-02-25T11:53:23Z

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.

nathanncohen · 2015-02-25T12:05:57Z

comment:22

Wow ! Thank you very much.

Nathann

vbraun · 2015-02-25T23:31:26Z

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.

nathanncohen · 2015-02-26T07:40:06Z

comment:25

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

Nathann

dimpase · 2015-02-26T09:22:14Z

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

nathanncohen · 2015-02-26T09:59:19Z

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 · 2015-02-26T18:18:09Z

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 · 2015-02-26T18:21:19Z

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.

nathanncohen · 2015-02-26T20:53:02Z

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 · 2015-02-26T21:09:44Z

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 · 2015-02-26T21:27:16Z

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!

sagetrac-git · 2015-02-27T07:48:31Z

Changed commit from d83413a to 5d7a241

sagetrac-git · 2015-02-27T07:48:31Z

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

`5d7a241`	`trac #17309: Mac OS X ...`

nathanncohen · 2015-02-27T07:49:41Z

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 · 2015-02-28T21:24:16Z

Changed branch from u/ncohen/17309 to 5d7a241

nathanncohen mannequin added this to the sage-6.4 milestone Nov 8, 2014

nathanncohen mannequin added p: major / 3 labels Nov 8, 2014

nathanncohen mannequin added the s: needs review label Nov 8, 2014

This comment has been minimized.

Sign in to view

nathanncohen mannequin added the c: combinatorial designs label Nov 10, 2014

dimpase added s: positive review and removed s: needs review labels Feb 25, 2015

vbraun added s: needs work and removed s: positive review labels Feb 26, 2015

nathanncohen mannequin added s: positive review and removed s: needs work labels Feb 27, 2015

vbraun removed the s: positive review label Feb 28, 2015

vbraun closed this as completed in 7a971ad Feb 28, 2015

nathanncohen mannequin mentioned this issue Nov 24, 2014

Cleanup subgraphsearch to avoid crashes #17376

Closed

SubHypergraphSearch #17309

SubHypergraphSearch #17309

Comments

nathanncohen mannequin commented Nov 8, 2014

nathanncohen mannequin commented Nov 8, 2014

nathanncohen mannequin commented Nov 8, 2014

sagetrac-git mannequin commented Nov 8, 2014

sagetrac-git mannequin commented Nov 8, 2014

sagetrac-git mannequin commented Nov 8, 2014

sagetrac-git mannequin commented Nov 8, 2014

This comment has been minimized.

sagetrac-git mannequin commented Nov 16, 2014

sagetrac-git mannequin commented Nov 16, 2014

sagetrac-git mannequin commented Nov 26, 2014

sagetrac-git mannequin commented Nov 26, 2014

sagetrac-git mannequin commented Dec 25, 2014

sagetrac-git mannequin commented Dec 25, 2014

nathanncohen mannequin commented Dec 25, 2014

nathanncohen mannequin commented Feb 24, 2015

dimpase commented Feb 25, 2015

nathanncohen mannequin commented Feb 25, 2015

dimpase commented Feb 25, 2015

dimpase commented Feb 25, 2015

nathanncohen mannequin commented Feb 25, 2015

dimpase commented Feb 25, 2015

sagetrac-git mannequin commented Feb 25, 2015

sagetrac-git mannequin commented Feb 25, 2015

nathanncohen mannequin commented Feb 25, 2015

dimpase commented Feb 25, 2015

sagetrac-git mannequin commented Feb 25, 2015

sagetrac-git mannequin commented Feb 25, 2015

dimpase commented Feb 25, 2015

dimpase commented Feb 25, 2015

nathanncohen mannequin commented Feb 25, 2015

vbraun commented Feb 25, 2015

nathanncohen mannequin commented Feb 26, 2015

dimpase commented Feb 26, 2015

nathanncohen mannequin commented Feb 26, 2015

vbraun commented Feb 26, 2015

dimpase commented Feb 26, 2015

nathanncohen mannequin commented Feb 26, 2015

vbraun commented Feb 26, 2015

dimpase commented Feb 26, 2015

sagetrac-git mannequin commented Feb 27, 2015

sagetrac-git mannequin commented Feb 27, 2015

nathanncohen mannequin commented Feb 27, 2015

vbraun commented Feb 28, 2015