Opened 12 years ago
Closed 11 years ago
#6747 closed defect (fixed)
Improve plotting of trees
Reported by: | boothby | Owned by: | boothby |
---|---|---|---|
Priority: | minor | Milestone: | sage-4.2.1 |
Component: | graph theory | Keywords: | |
Cc: | sage-combinat, jason, myurko | Merged in: | sage-4.2.1.alpha0 |
Authors: | Tom Boothby | Reviewers: | Nathann Cohen, Michael Yurko |
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
When one plots a tree with G.plot(layout='tree')
, the result is ugly. For one thing, a tree plot should never have crossing lines. I have code that makes a nice tree plot in nearly-linear time, which should be included in Sage.
Attachments (4)
Change History (17)
Changed 12 years ago by
comment:1 Changed 12 years ago by
You code looks like it first chooses the center vertex in the graph, then converts is as a Poset by picking this special vertex as a root, and plotting this Poset... But you did not post the patch :-)
Changed 12 years ago by
comment:2 Changed 12 years ago by
- Summary changed from Improve plotting of trees to [with patch, needs review] Improve plotting of trees
Uhm... my code does nothing like what you said. And I didn't post the patch because I hadn't cleaned it up / incorporated it into the GraphPlot? class / documented it. But now I have!
comment:3 Changed 12 years ago by
- Cc sage-combinat added
- Milestone set to sage-4.1.2
comment:4 Changed 12 years ago by
- Summary changed from [with patch, needs review] Improve plotting of trees to [with patch, needs work] Improve plotting of trees
I just tried your patch, and as I never plotted any tree in Sage, I tried to generate some for a start.... I tried your algorithm on graphs.BalancedTree?(3,4) and graphs.BalancedTree?(3,5). They are displayed on my machine in a very odd shape ( the picture had a large width and a very small height ). I admit these graphs contain a lot of vertices and may not be good examples, but what do you think of this result ? Do you think there would be a way to slightly change you code so that in such cases the plot could have a look closer from what one gets with the current layout=tree parameter ?
I know it is very easy to criticize in such cases, and much harder to come up with a good algorithm.. Thinking about it, I thought that maybe the best way to draw a tree properly would be to begin with a cross-free embedding of the tree in the plane ( as you mentionned ), then to use the usual trick of repulsion between vertices to obtain a balanced shape ? I know it is not a good solution because of its complexity. I'll continue thinking about it, though O_o
comment:5 Changed 12 years ago by
These are extreme examples, and I'm not sure that a top-down layout will ever look good. I believe that the solution for this particular problem would be to implement a circular tree layout algorithm. However, if you play with the parameters, you can get a fairly nice plot.
T = graphs.BalancedTree(3,5) P = T.plot(layout='tree',tree_root=0) P.show(aspect_ratio=.1,figsize=(15,15))
comment:6 Changed 12 years ago by
- Cc jason added
comment:7 follow-up: ↓ 12 Changed 12 years ago by
Applies fines, and I could not find any bug in it. Clearly improves the plotting for "human" trees. This new patch includes the previous one, plus :
- A INPUT section
- A new semicolumn after EXAMPLES ::
If you agree with these changes, you can set this ticket to positive review !
Nathann
Changed 12 years ago by
comment:8 Changed 12 years ago by
comment:9 Changed 12 years ago by
- Status changed from needs_work to needs_review
- Summary changed from [with patch, needs work] Improve plotting of trees to [with patch, needs review] Improve plotting of trees
comment:10 Changed 12 years ago by
- Summary changed from [with patch, needs review] Improve plotting of trees to Improve plotting of trees
comment:11 Changed 11 years ago by
- Cc myurko added
comment:12 in reply to: ↑ 7 Changed 11 years ago by
- Status changed from needs_review to positive_review
Replying to ncohen:
Applies fines, and I could not find any bug in it. Clearly improves the plotting for "human" trees. This new patch includes the previous one, plus :
- A INPUT section
- A new semicolumn after EXAMPLES ::
If you agree with these changes, you can set this ticket to positive review !
Nathann
The change look fine.
comment:13 Changed 11 years ago by
- Merged in set to sage-4.2.1.alpha0
- Resolution set to fixed
- Reviewers set to Nathann Cohen, Michael Yurko
- Status changed from positive_review to closed
old plot