Opened 6 years ago
Closed 6 years ago
#17309 closed enhancement (fixed)
SubHypergraphSearch
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.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 )
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 noninduced hypergraph. Later, in another patch, it can be improved to deal with another definition of "substructure" and compute things like the VCdimension, in case somebody cares.
Change History (36)
comment:1 Changed 6 years ago by
 Branch set to u/ncohen/17309
 Cc jmantysalo dimpase vdelecroix Stefan added
 Status changed from new to needs_review
comment:2 Changed 6 years ago by
 Commit set to 4c163fcba5cf78e2582408bcdb33d0f5dd3b6158
comment:3 Changed 6 years ago by
 Commit changed from 4c163fcba5cf78e2582408bcdb33d0f5dd3b6158 to 9d3d155b6481ce8d76683b192d1bee6d7ee223a2
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
9d3d155  trac #17309: SubHypergraphSearch

comment:4 Changed 6 years ago by
 Description modified (diff)
comment:5 Changed 6 years ago by
 Component changed from PLEASE CHANGE to combinatorial designs
comment:6 Changed 6 years ago by
 Commit changed from 9d3d155b6481ce8d76683b192d1bee6d7ee223a2 to 6b4eceb60b3b1b9d403f80bdcff935e0419d68ed
comment:7 Changed 6 years ago by
 Commit changed from 6b4eceb60b3b1b9d403f80bdcff935e0419d68ed to 6f2f2042daf39a1e3de977c649bb6ee79216654b
comment:8 Changed 6 years ago by
 Commit changed from 6f2f2042daf39a1e3de977c649bb6ee79216654b to 82b928ac9c0b6dd1744b1d7b370e552d6f898ed0
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
82b928a  trac #17309: SubHypergraphSearch

comment:9 Changed 6 years ago by
(it was conflicting with the latest beta)
comment:10 Changed 6 years ago by
Guys ?... This feature is really cool, I swear. Plus you probably will not find it anywhere else..
comment:11 Changed 6 years ago by
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) ?) }
comment:12 followup: ↓ 13 Changed 6 years ago by
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 6 years ago by
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.
comment:14 followup: ↓ 15 Changed 6 years ago by
The stuff should be tested on a 32bit system, just to make sure there is no archspecific bugs...
comment:15 in reply to: ↑ 14 ; followup: ↓ 21 Changed 6 years ago by
The stuff should be tested on a 32bit system, just to make sure there is no archspecific 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 64bits 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 6 years ago by
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/sitepackages/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: *** [dochtml] Error 1
comment:17 followup: ↓ 18 Changed 6 years ago by
 Commit changed from 82b928ac9c0b6dd1744b1d7b370e552d6f898ed0 to c0d1d1f3bc69fe771249c9dca8aef77ecdf1a087
comment:18 in reply to: ↑ 17 Changed 6 years ago by
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 6 years ago by
+ 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 6 years ago by
 Commit changed from c0d1d1f3bc69fe771249c9dca8aef77ecdf1a087 to d83413ad45c40ed1b474f521a2bd0164f6c99bbf
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
d83413a  trac #17309: Broken doc and typo

comment:21 in reply to: ↑ 15 Changed 6 years ago by
 Reviewers set to Dima Pasechnik
 Status changed from needs_review to positive_review
Replying to ncohen:
The stuff should be tested on a 32bit system, just to make sure there is no archspecific 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 64bits 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 6 years ago by
Wow ! Thank you very much.
Nathann
comment:23 Changed 6 years ago by
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 6 years ago by
 Status changed from positive_review to needs_work
comment:25 followup: ↓ 26 Changed 6 years ago by
Can you give me access to an OSX machine ? I can't debug in the dark.
Nathann
comment:26 in reply to: ↑ 25 ; followup: ↓ 27 Changed 6 years ago by
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 6 years ago by
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 followup: ↓ 29 Changed 6 years ago by
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 6 years ago by
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 6 years ago by
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 6 years ago by
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 followup: ↓ 34 Changed 6 years ago by
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
!
comment:33 Changed 6 years ago by
 Commit changed from d83413ad45c40ed1b474f521a2bd0164f6c99bbf to 5d7a2415b3dd7c6329acdbe858ba454969b94c15
Branch pushed to git repo; I updated commit sha1. New commits:
5d7a241  trac #17309: Mac OS X ...

comment:34 in reply to: ↑ 32 Changed 6 years ago by
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 6 years ago by
 Status changed from needs_work to positive_review
comment:36 Changed 6 years ago by
 Branch changed from u/ncohen/17309 to 5d7a2415b3dd7c6329acdbe858ba454969b94c15
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
trac #17309: SubHypergraphSearch