Fix tree plotting again

[boothby]

I wrote some code that produces fairly nice-looking tree plots in #6747, and, I might point out, worked great. For some reason, this was obliterated in #7004 with code that almost does the right thing, but fails to draw the tree crossing-free with high probability.

The easy thing is to add a parameter shuffle to GenericGraph.layout_ranked, so GenericGraph.layout_tree could just call return self.layout_ranked(heights_dict,shuffle=False) to avoid the (somewhat baffling) behavior of shuffling the vertices along the heights. IMHO, the default should be to not shuffle... but the primary focus of this ticket is to fix the damned tree plots. Again.

My preference is to bring back my code from #6747, since the results are pretty, and I find the "shrink-wrapped" look of layout_ranked to be incomprehensible for large-ish trees. A good compromise is to add options: layout = "tree", "tree:hang", "tree:shrinkwrap", "tree:circle", etc.

Note to reviewers: look at the plots produced in the doctests before giving a positive review.

Apply:

• trac_11908-fc.patch
• trac_11908-rev.patch

[chapoton]

hello there, here is a patch, needs review !

[ncohen]

Hellooooooo Frederic !

Looks like your patch does not apply cleanly on 5.10.beta1. This being said, what do you want to achieve with this patch ? What are the bad properties of the current implementation that you want to fix (I really have no idea, I never used that code) ? Do you want the drawing to be planar, for instance (no edge crossings) ?

Nathann

[ncohen]

Oh, and what about using "g.center()" as the root when none is provided ? It should minimize the tree's height.

Nathann

[chapoton]

Yes, the main aim is to have a drawing of a tree without crossings. With the current algorithm, this is not the case

g = graphs.RandomTree(80)
g.plot(layout='tree')

gives a very messy picture, which does not look like a tree at all.

Thanks for the idea of using the center, I will take care of that as soon as I can do the rebase.

[chapoton]

here is a rebased patch on 5.10.beta1

I have used the idea of the center as default root

[ncohen]

(while testing the patch)

Ahahahah. Yeah, it is indeed considerably better than what we currently have :-D

Nathann

[chapoton]

one moment please, I have to correct a typo in the doc

[chapoton]

typo corrected, done

[ncohen]

Two questions while I read and try too understand the algorithm.

• Why don't you treat the orientation up/down as you do right/left, i.e. at the end of the algorithm ?

• Why is obstruction[y] = max(x+1, obstruction[y]) not max(x+dx, obstruction[y]) ? You probably have a nice reason for that, as the plot are very pretty :-)

Nathann

[chapoton]

• Well, this is not my algorithm, it comes directly from Tom Boothby's code in #6747. I have not tried to understand how it works.

• I have introduced right and left orientations, in a simple-minded way. Maybe one can refactor the code.

[ncohen]

Hellooooooooooooo !

It took me some time to understand it, but it's done. I added comments, to help the next one who will have to read that.

If you agree with those changes, you can set the ticket to positive_review ! Nice layout :-)

Nathann

[chapoton]

ok, looks good to me. Positive review.

[boothby]

Sorry to pipe up now... but can one of you add in the following test, or something similar?

    sage: T = graphs.RandomTree(1000)
    sage: T.plot(layout='tree',save_pos=True)
    sage: T.is_drawn_free_of_edge_crossings()
    True

[chapoton]

ok, done. If you are satisfied, please consider putting back the positive review.

[kcrisman]

This is exactly the thing asked for, so I think you are safe in setting it to positive review as long as patchbot agrees...

[ncohen]

Green light !

Nathann