Opened 4 years ago

Closed 4 years ago

#17309 closed enhancement (fixed)

SubHypergraphSearch

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.4
Component: combinatorial designs Keywords:
Cc: jmantysalo, dimpase, vdelecroix, Stefan Merged in:
Authors: Nathann Cohen Reviewers: Dima Pasechnik
Report Upstream: N/A Work issues:
Branch: 5d7a241 (Commits) Commit: 5d7a2415b3dd7c6329acdbe858ba454969b94c15
Dependencies: Stopgaps:

Description (last modified by ncohen)

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.

Change History (36)

comment:1 Changed 4 years ago by ncohen

  • Authors set to Nathann Cohen
  • Branch set to u/ncohen/17309
  • Cc jmantysalo dimpase vdelecroix Stefan added
  • Status changed from new to needs_review

comment:2 Changed 4 years ago by git

  • Commit set to 4c163fcba5cf78e2582408bcdb33d0f5dd3b6158

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

4c163fctrac #17309: SubHypergraphSearch

comment:3 Changed 4 years ago by git

  • Commit changed from 4c163fcba5cf78e2582408bcdb33d0f5dd3b6158 to 9d3d155b6481ce8d76683b192d1bee6d7ee223a2

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

9d3d155trac #17309: SubHypergraphSearch

comment:4 Changed 4 years ago by ncohen

  • Description modified (diff)

comment:5 Changed 4 years ago by ncohen

  • Component changed from PLEASE CHANGE to combinatorial designs

comment:6 Changed 4 years ago by git

  • Commit changed from 9d3d155b6481ce8d76683b192d1bee6d7ee223a2 to 6b4eceb60b3b1b9d403f80bdcff935e0419d68ed

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

3688bdbtrac #17309: SubHypergraphSearch
6b4ecebtrac #17309: Caching the traces and induced subgraphs of h2

comment:7 Changed 4 years ago by git

  • Commit changed from 6b4eceb60b3b1b9d403f80bdcff935e0419d68ed to 6f2f2042daf39a1e3de977c649bb6ee79216654b

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

ae1f014trac #17309: SubHypergraphSearch
8e8bde1trac #17309: Caching the traces and induced subgraphs of h2
6f2f204trac #17309: Bugfix

comment:8 Changed 4 years ago by git

  • Commit changed from 6f2f2042daf39a1e3de977c649bb6ee79216654b to 82b928ac9c0b6dd1744b1d7b370e552d6f898ed0

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

82b928atrac #17309: SubHypergraphSearch

comment:9 Changed 4 years ago by ncohen

(it was conflicting with the latest beta)

comment:10 Changed 4 years ago by ncohen

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

Last edited 4 years ago by ncohen (previous) (diff)

comment:11 Changed 4 years ago by dimpase

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

comment:12 follow-up: Changed 4 years ago by ncohen

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

comment:13 in reply to: ↑ 12 Changed 4 years ago by dimpase

Replying to ncohen:

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.

Last edited 4 years ago by dimpase (previous) (diff)

comment:14 follow-up: Changed 4 years ago by dimpase

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

comment:15 in reply to: ↑ 14 ; follow-up: Changed 4 years ago by ncohen

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

comment:16 Changed 4 years ago by dimpase

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

comment:17 follow-up: Changed 4 years ago by git

  • Commit changed from 82b928ac9c0b6dd1744b1d7b370e552d6f898ed0 to c0d1d1f3bc69fe771249c9dca8aef77ecdf1a087

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

dad6191trac #17309: SubHypergraphSearch
c0d1d1ftrac #17309: Broken doc and typo

comment:18 in reply to: ↑ 17 Changed 4 years ago by ncohen

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

comment:19 Changed 4 years ago by dimpase

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

it should say unlabelled

comment:20 Changed 4 years ago by git

  • Commit changed from c0d1d1f3bc69fe771249c9dca8aef77ecdf1a087 to d83413ad45c40ed1b474f521a2bd0164f6c99bbf

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

d83413atrac #17309: Broken doc and typo

comment:21 in reply to: ↑ 15 Changed 4 years ago by dimpase

  • Reviewers set to Dima Pasechnik
  • Status changed from needs_review to positive_review

Replying to ncohen:

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.

comment:22 Changed 4 years ago by ncohen

Wow ! Thank you very much.

Nathann

comment:23 Changed 4 years ago by vbraun

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.

comment:24 Changed 4 years ago by vbraun

  • Status changed from positive_review to needs_work

comment:25 follow-up: Changed 4 years ago by ncohen

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

Nathann

comment:26 in reply to: ↑ 25 ; follow-up: Changed 4 years ago by dimpase

Replying to ncohen:

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

comment:27 in reply to: ↑ 26 Changed 4 years ago by ncohen

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

comment:28 follow-up: Changed 4 years ago by 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.

comment:29 in reply to: ↑ 28 Changed 4 years ago by dimpase

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.

comment:30 Changed 4 years ago by ncohen

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.

comment:31 Changed 4 years ago by vbraun

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

comment:32 follow-up: Changed 4 years ago by dimpase

  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!

Last edited 4 years ago by dimpase (previous) (diff)

comment:33 Changed 4 years ago by git

  • Commit changed from d83413ad45c40ed1b474f521a2bd0164f6c99bbf to 5d7a2415b3dd7c6329acdbe858ba454969b94c15

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

5d7a241trac #17309: Mac OS X ...

comment:34 in reply to: ↑ 32 Changed 4 years ago by ncohen

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

comment:35 Changed 4 years ago by ncohen

  • Status changed from needs_work to positive_review

comment:36 Changed 4 years ago by vbraun

  • Branch changed from u/ncohen/17309 to 5d7a2415b3dd7c6329acdbe858ba454969b94c15
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.