Opened 11 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)

tree2.png (32.9 KB) - added by boothby 11 years ago.
old plot
tree.png (12.8 KB) - added by boothby 11 years ago.
desired output
6747_tree_layout.patch (5.2 KB) - added by boothby 11 years ago.
trac_6747-reviewer.patch (5.7 KB) - added by ncohen 11 years ago.

Download all attachments as: .zip

Change History (17)

Changed 11 years ago by boothby

old plot

Changed 11 years ago by boothby

desired output

comment:1 Changed 11 years ago by ncohen

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 11 years ago by boothby

comment:2 Changed 11 years ago by boothby

  • 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 11 years ago by AlexGhitza

  • Cc sage-combinat added
  • Milestone set to sage-4.1.2

comment:4 Changed 11 years ago by ncohen

  • 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 11 years ago by boothby

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 11 years ago by jason

  • Cc jason added

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

Changed 11 years ago by ncohen

comment:8 Changed 11 years ago by nthiery

Thanks much for improving the layout of trees!

Please have a look at #7004, which also started splitting the layout algorithms in different methods. So we need to decide on a naming convention.

Then I guess this patch can get in, and #7400 be rebased on it.

comment:9 Changed 11 years ago by ncohen

  • 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 11 years ago by ncohen

  • Summary changed from [with patch, needs review] Improve plotting of trees to Improve plotting of trees

comment:11 Changed 11 years ago by myurko

  • Cc myurko added

comment:12 in reply to: ↑ 7 Changed 11 years ago by myurko

  • 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 mhansen

  • Authors set to Tom Boothby
  • 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
Note: See TracTickets for help on using tickets.