An Hypergraph class for visualization (pretty basic one !)

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Helloooooooooooo !!

This patch implements a veeeeeeeery basic Hypergraphs class whose only purpose is to draw them. It's very hard to get something meaningful, and I implemented it as I needed to draw many many many hypergraphs with less than 5 or 6 sets.

And it takes time to manually go through all the sets, and wonder how it should be drawn on a sheet of paper. I have heaps of them. This code made my life easier, and that's why I submit it as a patch even though it is pretty basic. If somebody thinks that it can prove useful to somebody else ...

In particular, even though I have been thinking hard about this for a long time, this patch does not contain any data structure for hypergraphs, nor the most basic hypergraphs functions. I haven't had the need to write one until now, and I don't want to write code that I do not need, for I don't believe that you can write good code that you don't use yourself ^^;

.... though I will probably work on that in not so long.

Have fuuuuuuuuuuuuuuuuun !

P.S. : Oh, and this patch also fixes an awkwardness with TikZ and LaTeX : if you need to add a package to LaTeX in a ._latex_ method, you can now add the package to the preamble in the ._latex_ method itself and everything will run smoothly.

Nathann

CC: @sagetrac-azi @sagetrac-Stefan @dimpase @nthiery @hivert @zabrocki

Component: graph theory

Author: Nathann Cohen

Reviewer: Travis Scrimshaw

Merged: sage-5.11.beta2

Issue created by migration from https://trac.sagemath.org/ticket/14712

[nthiery]

Hi Nathann!

Replying to @nathanncohen:

P.S. : Oh, and this patch also fixes an awkwardness with TikZ and LaTeX : if you need to add a package to LaTeX in a ._latex_ method, you can now add the package to the preamble in the ._latex_ method itself and everything will run smoothly.

Excellent! That's been annoying for a while, and this seems the way to do! I'd make it a separate ticket though since it's a pretty different feature and could get a positive review almost instantly by itself (though I would want to have the point of view of John or ...).

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:3

Well, I don't mind much having to wait a bit more. If you like the feature you can review this patch though, it's not very long and does not do anything smart :-P

Nathann

[73a39ce3-a287-437f-a1fe-8fc39b3a280a]

comment:4

The patch doesn't apply for me on OS X 10.8.3 with sage version 5.9. I get the following:

sage: hg_sage.apply("/Applications/sage/patches/trac_14712.patch")
cd "/Applications/sage/devel/sage" && sage --hg import   "/Applications/sage/patches/trac_14712.patch"
applying /Applications/sage/patches/trac_14712.patch
patching file doc/en/reference/graphs/index.rst
Hunk #2 FAILED at 23
1 out of 3 hunks FAILED -- saving rejects to file doc/en/reference/graphs/index.rst.rej
unable to find 'sage/graphs/hypergraph_generators.py' for patching
1 out of 1 hunks FAILED -- saving rejects to file sage/graphs/hypergraph_generators.py.rej
abort: patch failed to apply

I'm not sure what is causing this (it's my first time really trying to apply someone else's patch).

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:5

You apparently did it well, but Sage's current version for developpers is 5.10.rc1 :-)

Nathann

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:6

Hey Nathann,

Here's a review patch which removed the info from the latex output, does a basic explanation of a hypergraph, and makes some docstring tweaks.

The reason why I moved the info into the class definition is that the first thing I tried was view(H, tightpage=True) and I got a latex error. Also if you want to create a list of hypergraphs, there's no point in outputting the description everytime. Furthermore, putting it at the class level means it's easily available in the interactive documentation (where you are creating the pdfs).

If you're happy with my changes, go ahead and set this to positive review.

Best,

Travis

PS - I also would've preferred the latex part to be in a separate patch.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:9

Helloooooooooooo !!

The reason why I moved the info into the class definition is that the first thing I tried was view(H, tightpage=True) and I got a latex error. Also if you want to create a list of hypergraphs, there's no point in outputting the description everytime. Furthermore, putting it at the class level means it's easily available in the interactive documentation (where you are creating the pdfs).

Hmmm... Honestly, I would feel safer if the warning was always included in the document. It is very unlikely that anyone would read the documentation of Hypergraph before trying to view one, and as everybody since the early days of maths has been assuming that an hyperedge is the set of all vertices it CONTAINS, I am totally sure that everybody would misunderstand the drawings unless he/she is forced to read the warning.

What do you think ?

Nathann

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:10

Hmmmmmmm... Do you think that we could make this a warning, printed when ".latex" is called ? And it would stay in Hypergraph?, obviously.

Nathann

[tscrim]

comment:11

I think a warning is a better approach to this than explicitly putting text in the pdf output because that broke my (basic) test. However there are many things in sage which have conventions that user may not necessarily see immediately (or wonder about particular outputs), but as long as it is clearly documented what our convention choices are, it's okay. Anyways, what I'm trying to say is I'm okay with doing a warning, but I'm not 100% convinced that it is necessary.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:12

Hello !!

I think a warning is a better approach to this than explicitly putting text in the pdf output because that broke my (basic) test.

Methinks that it is a problem with tightpage more than a problem with my _latex_ output.

However there are many things in sage which have conventions that user may not necessarily see immediately (or wonder about particular outputs), but as long as it is clearly documented what our convention choices are, it's okay.

It depends. Sometimes it is sufficient, when you believe that the user may not understand what the output means, and will then look for the documentation. But in this case I am 100% sure that the users will believe that they understand the output, and that it would be the same as returning a wrong result. The users definitely HAVE to read this thing once.

I will make it a warning in a split second.

Nathann

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:13

What do you think ?

There a new warning in that patch, and I am used to hypergraphs whose edges can be equal to the empty set from time to time :-)

If you like it, you can set the ticket to positive_review.

Nathann

[tscrim]

comment:14

The warning looks okay, but look at this hypergraph:

sage: H = Hypergraph([{1,2,3},{2,3,4},{3,4,5},{6,8},{7}])
sage: view(H)

I don't see an edge between 6 and 8. Also I get the following:

sage: H = Hypergraph([{1,2}])                    
sage: view(H)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-13-b92aa03e5aba> in <module>()
----> 1 view(H)
...
/home/travis/sage-5.10.rc1/local/lib/python2.7/site-packages/sage/graphs/hypergraph.pyc in _latex_(self)
    232             # "center", i.e. the vertex representing the set s
    233             cx,cy = pos[s]
--> 234             s = map(lambda x:pos[x],s)
    235             s = sorted(s, key = lambda (x,y) : arctan2(x-cx,y-cy))
    236 

TypeError: argument 2 to map() must support iteration

so something isn't quite working (similarly for any one set of vertices).

Edit/PS - For the next version of the patch which fixes the above, could you fold all of the patches into one?

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:15

Patch updated ! It now plots the pairs, and the bug is fixed... But I really don't know what to do with sets of size 1. Do you think that it is ok to ignore them ? I don't know how to draw them either :-/

Nathann

[tscrim]

comment:16

We're getting there. Sets of size 1 are are drawn as isolated vertices. From the current construction which does not allow vertices not part of some (hyper)edge, there is no ambiguity with vertices not in some edge (and is not also rendered). Although you could draw them as a loop.

However now I'm not getting any colors. Also, why are the tests in edge_coloring() and _spring_layout() not test? Is it because their outputs are random? If so, I'd rather have them marked as # random. Thanks.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:17

Hellooooooooo !

We're getting there. Sets of size 1 are are drawn as isolated vertices. From the current construction which does not allow vertices not part of some (hyper)edge, there is no ambiguity with vertices not in some edge (and is not also rendered).

Wow cool. This code was much smarter than I thought :-P

Although you could draw them as a loop.

Hmmm... I have a personal problem with loops.

However now I'm not getting any colors. Also, why are the tests in edge_coloring() and _spring_layout() not test?

Well, they are tested. One of the tests is disabled in each case because it may depend on the architecture indeed.

Is it because their outputs are random? If so, I'd rather have them marked as # random. Thanks.

Done done ! :-)

Nathann

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Attachment: trac_14712.patch.gz

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:18

Oh, I forgot your "no color" problem though... I just tried the examples from the docstrings and there's no problem on my side O_o

Nathann

[tscrim]

comment:19

So Nathann, you're getting the graph with colors? Is there something (non-standard) I need to have installed to use the MILP coloring algorithm? Previously you just had the default value for g.coloring().

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:20

Hellooooooooo !!

So Nathann, you're getting the graph with colors? Is there something (non-standard) I need to have installed to use the MILP coloring algorithm? Previously you just had the default value for g.coloring().

Arg... Yes, I do get the colors, and you do not need anything to run coloring with algorithm=MILP as you have GLPK installed as a part of Sage. I changed this argument as I noticed algorithm=MILP was apparently faster than the default one for those instances.

It should not make any difference for the colors, though :-/

Nathann

[tscrim]

comment:21

Now colors work for me...strange...well, positive review then.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:22

Wow. Thanks :-)

Nathann

[jdemeyer]

Merged: sage-5.11.beta2