Opened 6 years ago

Closed 6 years ago

#14712 closed enhancement (fixed)

An Hypergraph class for visualization (pretty basic one !)

Reported by: ncohen Owned by: tbd
Priority: major Milestone: sage-5.11
Component: graph theory Keywords:
Cc: azi, Stefan, dimpase, nthiery, hivert, zabrocki Merged in: sage-5.11.beta2
Authors: Nathann Cohen Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

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

Attachments (1)

trac_14712.patch (13.8 KB) - added by ncohen 6 years ago.

Download all attachments as: .zip

Change History (24)

comment:1 Changed 6 years ago by ncohen

  • Status changed from new to needs_review

comment:2 in reply to: ↑ description Changed 6 years ago by nthiery

Hi Nathann!

Replying to ncohen:

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

comment:3 Changed 6 years ago by ncohen

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

comment:4 Changed 6 years ago by scmancuso

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

comment:5 Changed 6 years ago by ncohen

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

Nathann

comment:6 follow-up: Changed 6 years ago by tscrim

  • Reviewers set to Travis Scrimshaw

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.

Last edited 6 years ago by tscrim (previous) (diff)

comment:7 Changed 6 years ago by tscrim

  • Component changed from PLEASE CHANGE to graph theory

comment:8 Changed 6 years ago by zabrocki

  • Cc zabrocki added

comment:9 in reply to: ↑ 6 Changed 6 years ago by ncohen

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

comment:10 Changed 6 years ago by ncohen

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

Nathann

comment:11 follow-up: Changed 6 years ago by tscrim

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.

comment:12 in reply to: ↑ 11 Changed 6 years ago by ncohen

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

comment:13 Changed 6 years ago by ncohen

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

comment:14 Changed 6 years ago by tscrim

  • Status changed from needs_review to needs_work

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?

Last edited 6 years ago by tscrim (previous) (diff)

comment:15 Changed 6 years ago by ncohen

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

comment:16 follow-up: Changed 6 years ago by tscrim

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.

comment:17 in reply to: ↑ 16 Changed 6 years ago by ncohen

  • Status changed from needs_work to needs_review

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

Changed 6 years ago by ncohen

comment:18 Changed 6 years ago by ncohen

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

comment:19 follow-up: Changed 6 years ago by tscrim

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

comment:20 in reply to: ↑ 19 Changed 6 years ago by ncohen

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

comment:21 Changed 6 years ago by tscrim

  • Status changed from needs_review to positive_review

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

comment:22 Changed 6 years ago by ncohen

Wow. Thanks :-)

Nathann

comment:23 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.11.beta2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.