Opened 5 years ago

Closed 5 years ago

Last modified 5 years ago

#16622 closed defect (fixed)

Deprecate Hypergraph in favor of IncidenceStructure

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.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 follow-up: Changed 5 years ago by dimpase

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

comment:2 in reply to: ↑ 1 ; follow-up: Changed 5 years ago by 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. 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

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

comment:3 in reply to: ↑ 2 ; follow-up: Changed 5 years ago by dimpase

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 Sage-dependent 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 5 years ago by ncohen

I'd rather rename IncidenceStructure. There is more Sage-dependent 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

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

comment:5 follow-up: Changed 5 years ago by 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 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 Sage-devel

3) Everybody throws me stones

4) Deprecation warning

Nathann

comment:6 in reply to: ↑ 5 ; follow-up: Changed 5 years ago by dimpase

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

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 ; follow-up: Changed 5 years ago by 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 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 5 years ago by ncohen

  • Authors set to Nathann Cohen
  • Branch set to u/ncohen/16622
  • Status changed from new to needs_review

comment:9 Changed 5 years ago by git

  • Commit set to b3b34e871ef20af303be1cf527fa421dd46cbaeb

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

11994eftrac #16553: Review
e7a97eatrac #16553: doc fix + deprecation is_block_design
3c0dd71trac #16553v3: change .points() -> .ground_set()
52b7177trac #16553: merge sage 6.3.beta5
0698433trac #16553: deprecated alias .points() + fix
d14ae50trac #16622: Move 3 methods of Hypergraph (no other modification)
9be97a3trac #16622: Unindent the same 3 functions (no other modification)
95a3a91trac #16622: Return its methods to Hypergraph
2b06098trac #16622: Give them to IncidenceStructure too
b3b34e8trac #16622: Deprecate Hypergraph

comment:10 Changed 5 years ago by ncohen

  • Dependencies set to #16553

comment:11 in reply to: ↑ 7 ; follow-up: Changed 5 years ago by dimpase

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

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?

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

comment:12 in reply to: ↑ 11 ; follow-up: Changed 5 years ago by ncohen

if you just put everything that we have in Hypergraph into IncidenceStructure, and then do

   Hypergraph = 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 ; follow-up: Changed 5 years ago by dimpase

Replying to ncohen:

if you just put everything that we have in Hypergraph into IncidenceStructure, and then do

   Hypergraph = 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.

You can, and should, make that set of points in IncidenceStructure's constructor optional. (Using *args syntax).

comment:14 in reply to: ↑ 13 ; follow-up: Changed 5 years ago by 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 alias Hypergraph=IncidenceStructure will you review it ?

Nathann

comment:15 in reply to: ↑ 14 ; follow-ups: Changed 5 years ago by dimpase

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 alias Hypergraph=IncidenceStructure will you review it ?

yes!

comment:16 in reply to: ↑ 15 Changed 5 years ago by ncohen

yes!

Excellent. I'm on it then.

Nathann

comment:17 Changed 5 years ago by git

  • Commit changed from b3b34e871ef20af303be1cf527fa421dd46cbaeb to fb636aa9c5019845211ddc90e1166f23a53c684f

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

fb636aatrac #16622: Hypergraph is now an incidence structure

comment:18 follow-up: Changed 5 years ago by ncohen

Your turn !

Nathann

comment:19 in reply to: ↑ 18 ; follow-up: Changed 5 years ago by dimpase

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 5 years ago by git

  • Commit changed from fb636aa9c5019845211ddc90e1166f23a53c684f to 9f7045952f7dd14cbcb4dfa25e1d6549353f15d1

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

9f70459trac #16622: Changing the terminology

comment:21 in reply to: ↑ 19 Changed 5 years ago by 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.

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 5 years ago by dimpase

I am getting "No module named hypergraph" while building docs. Is it just me?

OSError: [graphs   ] /home/scratch/dimpase/sage/sage-6.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: *** [doc-html] Error 1

comment:23 Changed 5 years ago by ncohen

No it is not you, I forgot to remove it from the doc.

Nathann

comment:24 Changed 5 years ago by git

  • Commit changed from 9f7045952f7dd14cbcb4dfa25e1d6549353f15d1 to cb60470c5e8885ef031ed8bb4a84a38f3e8987f5

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

cb60470trac #16622: Broken doc

comment:25 Changed 5 years ago by ncohen

Does it work better for you ? With this cursed doc system I had to do a "make doc-clean" and I have to rebuild everything -_-

Nathann

comment:26 follow-up: Changed 5 years ago by novoselt

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 5 years ago by dimpase

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, ..., v-1}.

   * "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, ..., v-1}. 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 5 years ago by kcrisman

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 ?

yes!

Harmony! :)

comment:29 in reply to: ↑ 26 ; follow-up: Changed 5 years ago by ncohen

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 5 years ago by git

  • Commit changed from cb60470c5e8885ef031ed8bb4a84a38f3e8987f5 to cd7ba1a82334e5777ef61acae66dd20f5b19066e

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

cd7ba1atrac #16622: More doc fixes

comment:31 Changed 5 years ago by ncohen

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 follow-up: Changed 5 years ago by dimpase

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 5 years ago by novoselt

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 ; follow-up: Changed 5 years ago by ncohen

Yo !

Hmm, but how about HyperGraphGenerators? The file src/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 found HyperGraphGenerators 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 ; follow-up: Changed 5 years ago by dimpase

Replying to ncohen:

Yo !

Hmm, but how about HyperGraphGenerators? The file src/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 found HyperGraphGenerators 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 top-level 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 5 years ago by ncohen

I think Incidence structures (i.e. hypergraphs, i.e. set systems) should be in the top-level 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).

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

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

comment:37 Changed 5 years ago by dimpase

  • 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 5 years ago by nthiery

Just a pointer, after seeing a talk by David Auger a couple weeks ago:

Fully Automatic Visualisation of Overlapping Sets, http://hal.archives-ouvertes.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:39 Changed 5 years ago by vbraun

  • Status changed from positive_review to needs_work

Reviewer name

comment:40 Changed 5 years ago by ncohen

  • 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

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

comment:41 Changed 5 years ago by git

  • Commit changed from cd7ba1a82334e5777ef61acae66dd20f5b19066e to 20b3b4ae81823ebb6ba6a365c54358143838ec78

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

20b3b4atrac #16622: HyperGraphGenerators --> HypergraphGenerators

comment:42 Changed 5 years ago by dimpase

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

comment:43 Changed 5 years ago by ncohen

THanks for the review by the way :-)

Nathann

comment:44 Changed 5 years ago by vbraun

  • Branch changed from u/ncohen/16622 to 20b3b4ae81823ebb6ba6a365c54358143838ec78
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:45 Changed 5 years ago by kcrisman

  • Commit 20b3b4ae81823ebb6ba6a365c54358143838ec78 deleted

Possible followup: #17391.

Note: See TracTickets for help on using tickets.