#16622 closed defect (fixed)
Deprecate Hypergraph in favor of IncidenceStructure
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.3 
Component:  combinatorial designs  Keywords:  
Cc:  Stefan, dimpase, nthiery, brett, vdelecroix  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  20b3b4a (Commits)  Commit:  
Dependencies:  #16553  Stopgaps: 
Description
a "Hypergraph" class was introduced in #14712, but there also exists IncidenceStructure
in sage/combinat/designs
as well as set_system
in sage/matroids
.
We should really start to all work together on the same class, so for now let's deprecate Hypergraph in favor of IncidenceStructure
.
1) The only interesting thing that Hypergraph
can do is plot a hypergraph, and IncidenceStructure
has no such feature.
2) Right now set_system
claims to be only for internal use, so we cannot use it right now as a replacement right now.
Nathann
Change History (45)
comment:1 followup: ↓ 2 Changed 6 years ago by
comment:2 in reply to: ↑ 1 ; followup: ↓ 3 Changed 6 years ago by
Yo !
I'm not sure one should
deprecate
one in favour of the other. They are different names of the same object, as far as I am concerned. (IMHO "hypergraph" is a more common name, and there has been a lot of work done in this terminology, especially in TCS people prefer this terminology).
Hmmm... I prefer Hypergraph too, but the most interesting code is in IncidenceStructure
. What I am implementing right now does the following :
1) move the features of Hypergraph
that are not available in IncidenceStructure
into IncidenceStructure
2) add a deprecation warning saying that in the future Hypergraph will be an alias for IncidenceStructure
but that the input/output are different so that people should use IncidenceStructure
directly in the meantime
I made a mistake with git commands, and as a result all files were "touched" and I recompile Sage right now... In the meantime I will make sure that all doctests that used to work on Hypergraph
still work, and I will update the doc/doctests of their new IncidenceStructure
counterparts.
I have nothing against changing the name of IncidenceStructure
by the way. Vincent wrote a patch recently (#16553) which showed that it had been written with "Block Design" in mind, which is not what "incidence structure" means. What do you think ? Anyway, if we eventually merge the two we will have to change the input of one for the inputs of the other, so this way is as good as any.
Besides, I suspect that nobody besides me knows that Sage has a Hypergraph class. I began this patch because of some emails with Stefan, which made us notice that we are already doing the same work twice in matroids and designs when it comes to hypergraphs.
Nathann
comment:3 in reply to: ↑ 2 ; followup: ↓ 4 Changed 6 years ago by
Replying to ncohen:
Yo !
I'm not sure one should
deprecate
one in favour of the other. They are different names of the same object, as far as I am concerned. (IMHO "hypergraph" is a more common name, and there has been a lot of work done in this terminology, especially in TCS people prefer this terminology).Hmmm... I prefer Hypergraph too, but the most interesting code is in
IncidenceStructure
.
I'd rather rename IncidenceStructure
. There is more Sagedependent hypergraph code around, some of it quite deep,
cf. http://flagmatic.org/
It's not using Sage's own hypergraph code as it wasn't around at the time this was written, but still...
comment:4 in reply to: ↑ 3 Changed 6 years ago by
I'd rather rename
IncidenceStructure
. There is more Sagedependent hypergraph code around, some of it quite deep, cf. http://flagmatic.org/ It's not using Sage's own hypergraph code as it wasn't around at the time this was written, but still...
Well if they don't use it, what exactly is the problem ? In the end Hypergraph
and IncidenceStructure
will be the same object anyway.
Nathann
comment:5 followup: ↓ 6 Changed 6 years ago by
By the way according to Sage's rules you cannot just rename IncidenceStructure
(tell me that we don't care about this rule and I will do it in a second), for we already have an Hypergraph
object around. Only one can be named Hypergraph
, and if we change it to IncidenceStructure
the input changes, i.e. no backward compatibility.
I personally do not care about backward compatibility, but I know the workflow :
1) I don't care
2) Somebody writes to Sagedevel
3) Everybody throws me stones
4) Deprecation warning
Nathann
comment:6 in reply to: ↑ 5 ; followup: ↓ 7 Changed 6 years ago by
Replying to ncohen:
By the way according to Sage's rules you cannot just rename
IncidenceStructure
(tell me that we don't care about this rule and I will do it in a second), for we already have anHypergraph
object around. Only one can be namedHypergraph
, and if we change it toIncidenceStructure
the input changes, i.e. no backward compatibility.
What I meant to say is that you can rename things, change the underlying implementations, etc, as long as you do not remove functions and classes. No need to deprecate anything at all. IMHO...
comment:7 in reply to: ↑ 6 ; followup: ↓ 11 Changed 6 years ago by
Dima :
What I meant to say is that you can rename things, change the underlying implementations, etc, as long as you do not remove functions and classes. No need to deprecate anything at all. IMHO...
Right now we have a Hypergraph class and an IncidenceStructure? class. In the future it would be good to have only one, i.e. Hypergraph
and IncidenceStructure
should be the same class. I am trying to do this by telling users to stop using Hypergraph
for a while and use IncidenceStructure
instead, and after one year of deprecation Hypergraph
will be an alias for IncidenceStructure
.
How could we do that without deprecation ?
Nathann
comment:8 Changed 6 years ago by
 Branch set to u/ncohen/16622
 Status changed from new to needs_review
comment:9 Changed 6 years ago by
 Commit set to b3b34e871ef20af303be1cf527fa421dd46cbaeb
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
11994ef  trac #16553: Review

e7a97ea  trac #16553: doc fix + deprecation is_block_design

3c0dd71  trac #16553v3: change .points() > .ground_set()

52b7177  trac #16553: merge sage 6.3.beta5

0698433  trac #16553: deprecated alias .points() + fix

d14ae50  trac #16622: Move 3 methods of Hypergraph (no other modification)

9be97a3  trac #16622: Unindent the same 3 functions (no other modification)

95a3a91  trac #16622: Return its methods to Hypergraph

2b06098  trac #16622: Give them to IncidenceStructure too

b3b34e8  trac #16622: Deprecate Hypergraph

comment:10 Changed 6 years ago by
 Dependencies set to #16553
comment:11 in reply to: ↑ 7 ; followup: ↓ 12 Changed 6 years ago by
Replying to ncohen:
Dima :
What I meant to say is that you can rename things, change the underlying implementations, etc, as long as you do not remove functions and classes. No need to deprecate anything at all. IMHO...
Right now we have a Hypergraph class and an
IncidenceStructure
class. In the future it would be good to have only one, i.e.Hypergraph
andIncidenceStructure
should be the same class. I am trying to do this by telling users to stop usingHypergraph
for a while and useIncidenceStructure
instead, and after one year of deprecationHypergraph
will be an alias forIncidenceStructure
.How could we do that without deprecation ?
if you just put everything that we have in Hypergraph
into IncidenceStructure
, and then do
Hypergraph = IncidenceStructure
you only add more methods to Hypergraph
and to IncidenceStructure
. Nothing is removed. How can it break users' code? Why would one need to deprecate?
comment:12 in reply to: ↑ 11 ; followup: ↓ 13 Changed 6 years ago by
if you just put everything that we have in
Hypergraph
intoIncidenceStructure
, and then doHypergraph = IncidenceStructure
The input of Hypergraph
is not the same as IncidenceStructure
. In IncidenceStructure
you need to provide the sets of points, which you do not need to do in Hypergraph
.
Honestly, I am pretty sure that nobody uses this Hypergraph
class. But I am tired of fighting with everybody for this kind of stuff.
Nathann
comment:13 in reply to: ↑ 12 ; followup: ↓ 14 Changed 6 years ago by
Replying to ncohen:
if you just put everything that we have in
Hypergraph
intoIncidenceStructure
, and then doHypergraph = IncidenceStructureThe input of
Hypergraph
is not the same asIncidenceStructure
. InIncidenceStructure
you need to provide the sets of points, which you do not need to do inHypergraph
.
You can, and should, make that set of points in IncidenceStructure
's constructor optional. (Using *args syntax).
comment:14 in reply to: ↑ 13 ; followup: ↓ 15 Changed 6 years ago by
You can, and should, make that set of points in
IncidenceStructure
's constructor optional. (Using *args syntax).
If I do that in IncidenceStructure
and make an alias Hypergraph=IncidenceStructure
will you review it ?
Nathann
comment:15 in reply to: ↑ 14 ; followups: ↓ 16 ↓ 28 Changed 6 years ago by
Replying to ncohen:
You can, and should, make that set of points in
IncidenceStructure
's constructor optional. (Using *args syntax).If I do that in
IncidenceStructure
and make an aliasHypergraph=IncidenceStructure
will you review it ?
yes!
comment:16 in reply to: ↑ 15 Changed 6 years ago by
yes!
Excellent. I'm on it then.
Nathann
comment:17 Changed 6 years ago by
 Commit changed from b3b34e871ef20af303be1cf527fa421dd46cbaeb to fb636aa9c5019845211ddc90e1166f23a53c684f
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
fb636aa  trac #16622: Hypergraph is now an incidence structure

comment:18 followup: ↓ 19 Changed 6 years ago by
Your turn !
Nathann
comment:19 in reply to: ↑ 18 ; followup: ↓ 21 Changed 6 years ago by
Replying to ncohen: Could you make docstrings talking about vertices and edges a bit more clear, by mentioning that here we follow hypergraph terminology at these points (and adding an incidence structure equivalent if known...)? Otherwise it looks too confusing.
comment:20 Changed 6 years ago by
 Commit changed from fb636aa9c5019845211ddc90e1166f23a53c684f to 9f7045952f7dd14cbcb4dfa25e1d6549353f15d1
Branch pushed to git repo; I updated commit sha1. New commits:
9f70459  trac #16622: Changing the terminology

comment:21 in reply to: ↑ 19 Changed 6 years ago by
Could you make docstrings talking about vertices and edges a bit more clear, by mentioning that here we follow hypergraph terminology at these points (and adding an incidence structure equivalent if known...)? Otherwise it looks too confusing.
I just updated a commit. Tell me if you found other occurrences of words that should be changed.
Remember that two of the new functions are private ones, though, so it is not thaaaaaaat bad either.
Nathann
comment:22 Changed 6 years ago by
I am getting "No module named hypergraph" while building docs. Is it just me?
OSError: [graphs ] /home/scratch/dimpase/sage/sage6.3.beta2/src/doc/en/reference/graphs/sage/graphs/hypergraph.rst:11: WARNING: autodoc can't import/find module 'sage.graphs.hypergraph', it reported error: "No module named hypergraph", please check your spelling and sys.path make: *** [dochtml] Error 1
comment:23 Changed 6 years ago by
No it is not you, I forgot to remove it from the doc.
Nathann
comment:24 Changed 6 years ago by
 Commit changed from 9f7045952f7dd14cbcb4dfa25e1d6549353f15d1 to cb60470c5e8885ef031ed8bb4a84a38f3e8987f5
Branch pushed to git repo; I updated commit sha1. New commits:
cb60470  trac #16622: Broken doc

comment:25 Changed 6 years ago by
Does it work better for you ? With this cursed doc system I had to do a "make docclean" and I have to rebuild everything _
Nathann
comment:26 followup: ↓ 29 Changed 6 years ago by
For the record, I do know that Hypergraph
exists and used it in my code  thanks for the meaningful titles, Nathann ;) So I definitely care about that code not breaking right away, but rather telling me what has to be adjusted, if anything. I would also not think about IncidenceStructure
as an interesting class to look at, so please keep Hypergraph name at least as an alias.
comment:27 Changed 6 years ago by
currently Hypergraph?
and IncidenceSystem?
say:
A base class for incidence structure (or block design) with explicit ground set and blocks. INPUT: * "points"  the underlying set. If "points" is an integer v, then the set is considered to be {0, ..., v1}. * "blocks"  the blocks (might be any iterable)
It should say more: (my comments are in  )
A base class for incidence structure (or block design, or hypergraphs, or set systems) with explicit (or implicit DOCUMENTING LATEST CHANGE) ground set and blocks. INPUT: * "points"  the underlying set. In hypergraph terminology: "vertices". If "points" is an integer v, then the set is considered to be {0, ..., v1}. If omitted, it is the union of blocks. * "blocks"  the blocks (might be any iterable). In hypergraph terminology: "edges"; in set systems terminology: "sets of the system".
comment:28 in reply to: ↑ 15 Changed 6 years ago by
You can, and should, make that set of points in
IncidenceStructure
's constructor optional. (Using *args syntax).If I do that in
IncidenceStructure
and make an aliasHypergraph=IncidenceStructure
will you review it ?yes!
Harmony! :)
comment:29 in reply to: ↑ 26 ; followup: ↓ 33 Changed 6 years ago by
Yo !
For the record, I do know that
Hypergraph
exists and used it in my code
What for, if I may ask ? To draw them ? If so, would yo have any idea of how to make it work for more complicated hypergraphs ? It works well for small ones, but very quickly all the drawings are impossible to read :/
Nathann
comment:30 Changed 6 years ago by
 Commit changed from cb60470c5e8885ef031ed8bb4a84a38f3e8987f5 to cd7ba1a82334e5777ef61acae66dd20f5b19066e
Branch pushed to git repo; I updated commit sha1. New commits:
cd7ba1a  trac #16622: More doc fixes

comment:31 Changed 6 years ago by
Here it is Dima ! I added "i.e. sets, i.e. blocks" a bit everywhere. This way it is clear to everybody and it keeps the sentences short.
And the doc builds.
Nathann
comment:32 followup: ↓ 34 Changed 6 years ago by
Hmm, but how about HyperGraphGenerators
?
The file src/sage/graphs/hypergraph_generators.py
is still there.
Another issue is that there is no Hypergraph
in the index of the reference manual. (That's how I actually found HyperGraphGenerators
in the 1st place.)
comment:33 in reply to: ↑ 29 Changed 6 years ago by
Replying to ncohen:
What for, if I may ask ? To draw them ? If so, would yo have any idea of how to make it work for more complicated hypergraphs ? It works well for small ones, but very quickly all the drawings are impossible to read
:/
Yes, to draw them  I had to construct a bunch of hypergraphs based on pictures and it was a nice check to see that everything was done correctly. They were quite small and simple, so your code worked OK for me.
Given that even for regular graphs it is hard to automatically produce "the best" or even just "an OK" picture, I doubt that this can be easily done for hypergraphs ;) Perhaps 3D plots would work better, if we had a nice renderer.
comment:34 in reply to: ↑ 32 ; followup: ↓ 35 Changed 6 years ago by
Yo !
Hmm, but how about
HyperGraphGenerators
? The filesrc/sage/graphs/hypergraph_generators.py
is still there.
It is true. It can be used to lists all hypergraphs through hypergraphs.nauty
. I do not think that it is a problem.
Another issue is that there is no
Hypergraph
in the index of the reference manual. (That's how I actually foundHyperGraphGenerators
in the 1st place.)
There is a "hypergraph" entry in the "Graph theory" section. We cannot really afford to add a "Hypergraph" entry just near the "graph theory" section given the very small amount of code that we ship O_o
Nathann
comment:35 in reply to: ↑ 34 ; followup: ↓ 36 Changed 6 years ago by
Replying to ncohen:
Yo !
Hmm, but how about
HyperGraphGenerators
? The filesrc/sage/graphs/hypergraph_generators.py
is still there.It is true. It can be used to lists all hypergraphs through
hypergraphs.nauty
. I do not think that it is a problem.Another issue is that there is no
Hypergraph
in the index of the reference manual. (That's how I actually foundHyperGraphGenerators
in the 1st place.)There is a "hypergraph" entry in the "Graph theory" section. We cannot really afford to add a "Hypergraph" entry just near the "graph theory" section given the very small amount of code that we ship
O_o
I think Incidence structures (i.e. hypergraphs, i.e. set systems)
should be in the toplevel list, next to graph theory and matroids. (and no Hypergraphs in Graphs).
And HyperGraphGenerators
should become HypergraphGenerators
and go to this section (of the manual, as well as of the code).
comment:36 in reply to: ↑ 35 Changed 6 years ago by
I think
Incidence structures (i.e. hypergraphs, i.e. set systems)
should be in the toplevel list, next to graph theory and matroids. (and no Hypergraphs in Graphs).And
HyperGraphGenerators
should becomeHypergraphGenerators
and go to this section (of the manual, as well as of the code).
Well, we disagree there. To me this hypergraph stuff is nothing more than a gadget for the moment, Vincent just fixed a lot of things there in his last patch and many methods will just raise deprecation warnings for a year. Plus there is so little code that putting it on the same level as graphs... O_o
I mean, even LP is buried in "numerical" and it is ten times more used and more useful, and combinatorial designs contain a thousand objects that only Sage can build, and it is buried too...
Plus it would mean that the code exists in sage/combinat/designs and the doc actually hints that it should be sage/hypergraphs ?
Sorry Dima but I think that it is too early for that.
Nathann
comment:37 Changed 6 years ago by
 Status changed from needs_review to positive_review
OK. I hope one can at least open a ticket to rename HyperGraphGenerators
to HypergraphGenerators
. I'll review it!
comment:38 Changed 6 years ago by
Just a pointer, after seeing a talk by David Auger a couple weeks ago:
Fully Automatic Visualisation of Overlapping Sets, http://hal.archivesouvertes.fr/docs/00/40/72/69/PDF/EuroVis09.pdf
I invited David to come talk at our Sage user group in Paris next fall, to discuss Tulip and potential collaborations with Sage.
comment:40 Changed 6 years ago by
 Status changed from needs_work to needs_review
HMmm.. Well, given that it was in needs_work
I may as well add the commit you wanted :P
Nathann
comment:41 Changed 6 years ago by
 Commit changed from cd7ba1a82334e5777ef61acae66dd20f5b19066e to 20b3b4ae81823ebb6ba6a365c54358143838ec78
Branch pushed to git repo; I updated commit sha1. New commits:
20b3b4a  trac #16622: HyperGraphGenerators > HypergraphGenerators

comment:42 Changed 6 years ago by
 Reviewers set to Dima Pasechnik
 Status changed from needs_review to positive_review
comment:43 Changed 6 years ago by
THanks for the review by the way :)
Nathann
comment:44 Changed 6 years ago by
 Branch changed from u/ncohen/16622 to 20b3b4ae81823ebb6ba6a365c54358143838ec78
 Resolution set to fixed
 Status changed from positive_review to closed
comment:45 Changed 6 years ago by
 Commit 20b3b4ae81823ebb6ba6a365c54358143838ec78 deleted
Possible followup: #17391.
I'm not sure one should
deprecate
one in favour of the other. They are different names of the same object, as far as I am concerned. (IMHO "hypergraph" is a more common name, and there has been a lot of work done in this terminology, especially in TCS people prefer this terminology).