文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > FUNCT I ONAL PEARLS Drawing Trees
侵权投诉

FUNCT I ONAL PEARLS Drawing Trees

This article describes the application of functional programming techniques to a problem previously studied by imperative programmers, that of drawing general trees automatically. We first consider the nature of the problem and the ideas behind its solutio

J. Functional Programming 6 (3): 527{534, May 1996 c 1996 Cambridge University Press 527

FUNCTIONAL PEARLS

Drawing Trees

University of Cambridge Computer Laboratory New Museums Site, Pembroke Street Cambridge CB2 3QG, United Kingdom

ANDREW J. KENNEDY

Abstract This article describes the application of functional programming techniques to a problem previously studied by imperative programmers, that of drawing general trees automatically. We rst consider the nature of the problem and the ideas behind its solution (due to Radack), independent of programming language implementation. We then describe a Standard ML program which re ects the structure of the abstract solution much better than an imperative language implementation. We conclude with an informal discussion on the correctness of the implementation and some changes which improve the algorithm's worst-case time complexity.

1 The problem and its solution The problem is this: given a labelled tree, assign to each node a position on the page to give an aesthetically pleasing rendering of the tree. We assume that nodes at the same depth are positioned on the same horizontal line on the page, so the problem reduces to nding a position horizontally for each node. But what do we mean by\aesthetically pleasing"? The various papers on the subject (Radack, 1988; Wetherell and Shannon, 1979; Vaucher, 1980; Reingold and Tilford, 1981; Walker, 1990) list aesthetic rules which constrain the positions in a number of ways. We adopt the same rules as Radack and Walker: 1. Two nodes at the same level should be placed at least a given distance apart. 2. A parent should be centred over its o spring. 3. Tree drawings should be symmetrical with respect to re ection|a tree and its mirror image should produce drawings that are re ections of each other. In particular, this means that symmetric trees will be rendered symmetrically. So, for example, Figure 1 shows two renderings, the rst bad, the second good. 4. Identical subtrees should be rendered identically|their position in the larger tree should not a ect their appearance. In Figure 2 the tree on the left fails the test, and the one on the right passes. Finally, trees should be as narrow as possible without violating these rules.

第1页

你可能喜欢

热门文档

相关文档

  • FUNCT I ONAL PEARLS Diets for Fat Sets

    FUNCT I ONAL PEARLS Draw... 暂无评价 8页 免费 FUNCT I ONAL PEARLS ...Testing for set membership in a diet is similar to binary search trees: ...

  • FUNCT I ONAL PEARLS Combinators for Breadth-First S...

    FUNCT I ONAL PEARLS Combinators for Breadth-First Search_专业资料。Every functional programmer knows the technique of \replacing failure by a list of ...

  • ...Functional Programming 1 FUNCT I ONAL PEARLS Inv...

    Functional Programming 1 FUNCT I ONAL PEARLS Inve Our aim in this pearl is to exploit simple equational reasoning to derive the inverse of the Burrows-...

  • ...Functional Programming 1 FUNCT I ONAL PEARLS Max...

    Under consideration for publi...

  • I_1_Sets

    FUNCT I ONAL PEARLS Diet... 暂无评价 6页 免费 I. PRACTICAL NEED FOR FU... 暂无评价 6页 免费 2.1 Sets 暂无评价 20页 1财富值 Ergodic Theory ...

  • I-Search First Draft

    FUNCT I ONAL PEARLS Comb... 暂无评价 11页 免费 first draft 2页 5财富值 First Draft 17页 免费 First draft 1页 免费 Lecture 17 Shortest Path... ...

  • lecture 34,Binomial Heaps

    FUNCT I ONAL PEARLS Expl... 暂无评价 12页 免费 Min-max heaps – ... Binomial Heaps Leftist trees Binomial heaps Actual Amortized O(log n) O(...

  • A Poor Man

    免费 FUNCT I ONAL PEARLS... 暂无评价 11页 免费 leanEA A Poor Man's Ev... 暂无评价 34页 免费 Abstract A Poor Man's ... 暂无评价 10页 免费...

  • Poor Man's 3D - Hack Canada

    暂无评价 7页 免费 FUNCT I ONAL PEARLS A Po... 暂无评价 11页 免费喜欢此文档的还喜欢 小学英语阅读100篇WORD文本... 48页 2财富值 办公文具2 36页 ...

  • Profiling Lazy Functional Programs

    FUNCT I ONAL PEARLS A Po... 暂无评价 11页 免费 Parser Combinators for E... 6页 免费 Abstract Visual Haskell ... 12页 免费 Programming Language ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email