trac 7004: Refactor the graph layout code, and add interface with graphviz
Nicolas M. Thiery
Due to urgent needs for Sage days 20, I just rebased and worked
further on my patch for #7004:
Refactor the graph layout code, and add interface with graphviz
It is now up on trac for review. See the ticket description for what
was changed. The main improvement from the user point of view is that
it is more modular, allowing for using any layout algorithm
(circular/spring/planar/...) with any plot function (graph_editor,
plot, save, plot3d), when meaningful. There are a couple design
questions and TODO's left in the ticket description which I reproduce
here for discussions.
So here is what remains to do, now in this ticket, or later:
* Double check all the logic to make sure it is backward compatible
There are not that many tests for the graph layout code (because it
is non trivial to test). So please recreate all your favorite graph
plots and see if there is anything broken.
* graph_editor was using iterations=1000 as default. Was there a
reason? If yes, do we want to set this up as default value for all
layouts?
* What should be the default layout algorithm?
* Planar layout when the graph is planar
* acyclic if acyclic
* spring otherwise
* The spring option for graded layouts does not work: the plot get
completely squished horizontally. Could someone please help me
debug this?
sage: G = posets.[wiki:IntegerPartitions](3).hasse_diagram()
sage: G.plot(layout="acyclic_dummy", spring = True)
To be compared with:
sage: G.plot(layout="acyclic_dummy")
* Find a better name for acyclic_dummy. Once the spring option will
be functional, this could be set to the default value, and the
layout renamed to acyclic_spring.
* Choose a good option name for the direction of growth of acyclic
layout, and a good default value. Merge this with the option for
tree layout (tree_orientation).
orientation = "up" (as for tree) ?
rankdir = "BT" (as in graphviz)?
* A lot of code is doing things very similar to dot2tex. Maybe things could be merged.
* Implement the various options for both latex constructions (tikz or dot2tex)
* Implement the default layout of standard graphs using a
default_layout method rather than at construction time.
Notes:
- Up to fixing a couple things after this discussion, the patch
should be essentially ready. As much as possible, I'd rather have
it not rot away again. Quick comments and reviews would be most
welcome!
- I am a bit worried about conflicts with #7608. Indeed, besides its
main changes which are well localized and far from what #7004
touches, the patch up on #7608 does trivial edits almost everywhere
in the graph code (apparently fixing spurious end of line spaces).
I would suggest to either remove those trivial edits from #7608, or
to rebase it on #7004 (which will be much easier than the
converse).
Thanks in advance!
Nicolas
--
Nicolas M. Thi�ry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/
Robert Miller
<Nicolas...@u-psud.fr> wrote:
> Due to urgent needs for Sage days 20, I just rebased and worked
> further on my patch for #7004:
> * What should be the default layout algorithm?
> * Planar layout when the graph is planar
I wonder if this is a good idea. The Schnyder algorithm tends to make
the graph, while technically embedded in a planar way, very hard to
look at. I would think twice about using it by default (although
everything is linear in the number of vertices, so it's not
computationally a bad idea). I've often wondered about an adapted
spring algorithm which preserved faces, to apply after Schnyder...
> * Implement the default layout of standard graphs using a
> default_layout method rather than at construction time.
That's a great idea!
> I would suggest to ... rebase [#7608] on #7004.
+1
--
Robert L. Miller
http://www.rlmiller.org/
Rado
> reason? If yes, do we want to set this up as default value for all
> layouts?
I think Mitesh added that part, so he should answer if there are any
deep reasons for it. But most likely any value would work. As long as
the user gets something other than a giant cluster.
Or maybe we should use circle layout and every call on graph_editor
would be a fast game of http://www.planarity.net/ :)
Nicolas M. Thiery
> I started the lecture and the review. I need your tools to draw huge
> Rauzy diagrams (more than 1000 vertices) and graphs of graphs. Hence,
> I will see if your patch is "adaptable".
Excellent, thanks! That will be a good stress on graphviz and the
interface; I am not sure if they can handle properly huge graphs
(especially the later).
> If anybody else is on that, tell me I will concentrate my efforts on
> Rauzy diagrams.
I haven't heard of anyone else yet. So please go ahead!
I'll probably post an updated patch later tonight fixing a couple
trivial doctest failures. And there are two issues left (ranked+spring
layout, and doctesting failures when using graphviz; see the ticket
description) I am not sure how dependent we are on the Sage graph
experts on those.
Cheers,
Nicolas M. Thiery
Thanks for your quick feedback!
Anyone else comments? Vincent is about to review the code.
On Tue, Feb 09, 2010 at 04:15:59PM -0800, Robert Miller wrote:
> On Tue, Feb 9, 2010 at 3:53 PM, Nicolas M. Thiery
> <Nicolas...@u-psud.fr> wrote:
> > Due to urgent needs for Sage days 20, I just rebased and worked
> > further on my patch for #7004:
> ...
> > �* What should be the default layout algorithm?
> > � * Planar layout when the graph is planar
>
> I wonder if this is a good idea. The Schnyder algorithm tends to
> make the graph, while technically embedded in a planar way, very
> hard to look at. I would think twice about using it by default
> (although everything is linear in the number of vertices, so it's
> not computationally a bad idea). I've often wondered about an
> adapted spring algorithm which preserved faces, to apply after
> Schnyder...
Ok, I'll just leave spring layout as default, until a fancy
planar/spring will get implemented.
Do you think you could have a couple spare minutes to spend on the
issue I am having with the ranked+spring layout? I must be misusing
spring_layout_fast, with its height = True argument, but am having a
hard time finding why. A working ranked+spring layout would be really
a great feature for all our posets and such.
Thanks in advance!
Cheers,
Rob Beezer
wrote:
> * Implement the various options for both latex constructions (tikz or dot2tex)
I looked through the changes to latex (tikzpicture) code for graphs,
to allow consistent handling of the dot2tex/graphviz output. It all
looks fine and the tikzpicture environments seem to be unchanged, so I
think backward compatibility is preserved here. And the changes, in
addition to the bounding box code, will be useful when I come back to
this.
My only comment regards line 313 of graph_latex.py, where the
docstring suggests adding the tkz-graph package by joining a string to
sage.misc.latex.LATEX_HEADER. This would be better accomplished by
using the latex.add_to_preamble() call, which in particular won't add
a string that is already there.
Thanks for your improvements and work on this!
Rob
Pat LeSmithe
> * graph_editor was using iterations=1000 as default. Was there a
> reason? If yes, do we want to set this up as default value for all
> layouts?
Feel free to change this --- there's definitely no deep reason.
It was an attempt to avoid giving the user "a giant cluster."
Nicolas M. Thiery
Thanks for your feedback!
I posted your two comments on trac for the reviewer.
On Wed, Feb 10, 2010 at 10:01:39PM -0800, Rob Beezer wrote:
> On Feb 9, 3:53�pm, "Nicolas M. Thiery" <Nicolas.Thi...@u-psud.fr>
> wrote:
> > �* Implement the various options for both latex constructions (tikz or dot2tex)
>
> I looked through the changes to latex (tikzpicture) code for graphs,
> to allow consistent handling of the dot2tex/graphviz output. It all
> looks fine and the tikzpicture environments seem to be unchanged, so I
> think backward compatibility is preserved here. And the changes, in
> addition to the bounding box code, will be useful when I come back to
> this.
Cool.
> My only comment regards line 313 of graph_latex.py, where the
> docstring suggests adding the tkz-graph package by joining a string to
> sage.misc.latex.LATEX_HEADER. This would be better accomplished by
> using the latex.add_to_preamble() call, which in particular won't add
> a string that is already there.
Thanks for the suggestion. Done.
> Thanks for your improvements and work on this!
Just scratching hard a big itch of mine :-)
Cheers,
Nicolas M. Thiery
I just put on http://wiki.sagemath.org/combinat/CoolPictures a few
pictures produced using this patch. Here is Tom Denton's reaction when
he looked at the n=5 one:
"First they tell us we will never need more than 640k of RAM, then
they tell us our documents should always be less than the length of a
limousine..."
(I had to fight with TeX's limit on dimensions to get it to compile)
By the way: this is a call for adding more pictures on this page!
Cheers,
Alex Ghitza
> I just put on http://wiki.sagemath.org/combinat/CoolPictures a few
> pictures produced using this patch.
Hi Nicolas,
Cool pictures indeed. Can you also post the Sage code for generating
them?
Best,
Alex
--
Alex Ghitza -- Lecturer in Mathematics -- The University of Melbourne
-- Australia -- http://www.ms.unimelb.edu.au/~aghitza/
Nicolas M. Thiery
> Cool pictures indeed. Can you also post the Sage code for generating
> them?
I definitely will, when that won't require anymore a collection of,
hmm, non production grade code, in particular to define and work with
those monoids. Oh, and for the last picture, I had to edit manually
the latex file to scale down the TeX dimensions; something probably
not often enough needed to deserve automatizing and integration into
Sage.
Let me use the occasion for a feature request: immutable graphs. I
had to hack around this to make a graph with graphs as nodes.