Opened 10 years ago

Closed 8 years ago

#11908 closed defect (fixed)

Fix tree plotting again

Reported by: boothby Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.10
Component: graph theory Keywords: tree, plot
Cc: nthiery, vdelecroix, ncohen Merged in: sage-5.10.beta3
Authors: Frédéric Chapoton Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by ncohen)

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:

Attachments (3)

trac_11908-fc.patch (17.3 KB) - added by chapoton 8 years ago.
trac_11908-rev.patch (3.3 KB) - added by ncohen 8 years ago.
trac_11908-more_test.patch (775 bytes) - added by chapoton 8 years ago.

Download all attachments as: .zip

Change History (22)

comment:1 Changed 8 years ago by chapoton

  • Authors set to Frédéric Chapoton
  • Status changed from new to needs_review

hello there, here is a patch, needs review !

comment:2 Changed 8 years ago by chapoton

  • Cc ncohen added

comment:3 Changed 8 years ago by ncohen

  • Status changed from needs_review to needs_work

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

comment:4 Changed 8 years ago by ncohen

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

Nathann

comment:5 Changed 8 years ago by 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.

comment:6 Changed 8 years ago by chapoton

  • Status changed from needs_work to needs_review

here is a rebased patch on 5.10.beta1

I have used the idea of the center as default root

comment:7 Changed 8 years ago by chapoton

  • Keywords tree plot added

comment:8 Changed 8 years ago by ncohen

(while testing the patch)

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

Nathann

comment:9 Changed 8 years ago by chapoton

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

Changed 8 years ago by chapoton

comment:10 Changed 8 years ago by chapoton

typo corrected, done

comment:11 Changed 8 years ago by 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

comment:12 Changed 8 years ago by 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.

Changed 8 years ago by ncohen

comment:13 Changed 8 years ago by ncohen

  • Description modified (diff)
  • Reviewers set to Nathann Cohen

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

comment:14 Changed 8 years ago by chapoton

  • Status changed from needs_review to positive_review

ok, looks good to me. Positive review.

comment:15 Changed 8 years ago by boothby

  • Status changed from positive_review to needs_work

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

    T = graphs.RandomTree(1000)
    T.plot(layout='tree',save_pos=True)
    T.is_drawn_free_of_edge_crossings()
Version 0, edited 8 years ago by boothby (next)

Changed 8 years ago by chapoton

comment:16 Changed 8 years ago by chapoton

  • Status changed from needs_work to needs_review

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

comment:17 Changed 8 years ago by 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...

Last edited 8 years ago by kcrisman (previous) (diff)

comment:18 Changed 8 years ago by ncohen

  • Status changed from needs_review to positive_review

Green light !

Nathann

comment:19 Changed 8 years ago by jdemeyer

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