Opened 9 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: |
Description (last modified by )
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)
Change History (22)
comment:1 Changed 8 years ago by
- Status changed from new to needs_review
comment:2 Changed 8 years ago by
- Cc ncohen added
comment:3 Changed 8 years ago by
- 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
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
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
- 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
- Keywords tree plot added
comment:8 Changed 8 years ago by
(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
one moment please, I have to correct a typo in the doc
Changed 8 years ago by
comment:10 Changed 8 years ago by
typo corrected, done
comment:11 Changed 8 years ago by
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])
notmax(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
- 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
comment:13 Changed 8 years ago by
- 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
- Status changed from needs_review to positive_review
ok, looks good to me. Positive review.
comment:15 Changed 8 years ago by
- 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?
sage: T = graphs.RandomTree(1000) sage: T.plot(layout='tree',save_pos=True) sage: T.is_drawn_free_of_edge_crossings() True
Changed 8 years ago by
comment:16 Changed 8 years ago by
- 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
This is exactly the thing asked for, so I think you are safe in setting it to positive review as long as patchbot agrees...
comment:18 Changed 8 years ago by
- Status changed from needs_review to positive_review
Green light !
Nathann
comment:19 Changed 8 years ago by
- Merged in set to sage-5.10.beta3
- Resolution set to fixed
- Status changed from positive_review to closed
hello there, here is a patch, needs review !