dirk@kulcs.uucp (Dirk Craeynest) (12/20/89)
Some time ago, I asked the net for information on the graphical representation of trees and graphs. This was my message: > From: dirk@kulcs.uucp (Dirk Craeynest) > Newsgroups: comp.lang.ada,comp.graphics,comp.sources.wanted > Subject: Graphical representation of trees and graphs > Date: 6 Nov 89 10:12:35 GMT > Organization: Katholieke Universiteit Leuven, Dept. Computer Science > > We are looking for pointers to software packages to display abstract > syntax trees (or more generally -graphs) graphically, and to allow for > interactive manipulation and modification of these representations. > The software should preferably be public domain, in Ada and based on > X11, although all information is appreciated. > > We are building an environment for the semantics directed construction > of compilers, interpreters, etc. based on a newly designed > metalanguage. This metalanguage allows the user to describe these > tools in a very modular and secure way as a number of successive > transformations of an internal abstract representation of the source > program. The environment includes a symbolic debugger, and we would > like to provide a graphical interface to the abstract syntax graphs > representing program fragments. > > Please reply by e-mail. I will summarize if interest warrants. > Thanks. > > Dirk Craeynest As promised, here is an overview of the replies. As most messages have been passed on to several people, I have included a From and Date line per person. Thanks to everyone who responded. ------------------------------------------------------------------------ >From bryan%sierra.STANFORD.EDU Wed Nov 8 07:44:15 1989 Date: Tue, 7 Nov 89 12:07:19 PST From: Daniel Winkowski <dgw@mimsy.umd.edu> Date: Tue, 27 Sep 88 11:49:21 EDT From: magerman@linc.cis.upenn.edu (David Magerman) Date: Tue, 20 Sep 88 16:06:04 EDT If you haven't received any responses yet, I may have something for you. I'm a student at the University of Pennsylvania. I was working on an NL animation project, and I needed to represent the arcs of the parsing process in the form of an arc chart, where nodes represented the position either before or after a word and arcs connected a the nodes according to an array, with those arcs labeled with mouse-sensitive objects, depending upon a labelling function provided at run-time. The point is, if you don't mind lining up the nodes in the network horizontally, then what I have might be what you need. It is well tested and, to the best of my knowledge, produces a minimum-sized, non-overlapping (the labels, that is) chart of a directed, cyclic graph. As an added feature, it works with all of the 7.2 hardcopy stuff, so you can hardcopy any chart. If you're interested in taking a look at what I have, send me mail at magerman@linc.cis.upenn.edu. -- David Magerman University of Pennsylvania, LINC Lab ------------------------------------------------------------------------ >From bryan%sierra.STANFORD.EDU Wed Nov 8 07:44:15 1989 Date: Tue, 7 Nov 89 12:07:19 PST From: Daniel Winkowski <dgw@mimsy.umd.edu> Date: Tue, 27 Sep 88 11:49:21 EDT From: Eric A. Raymond <RAYMOND@PLUTO.ARC.NASA.GOV> Date: Tue 20 Sep 88 16:27:19-PDT In addition to the format-graph-from-root stuff in Genera, you may also be interested in the ISI Grapher (contact Gabriel Robins: gabriel@vaxa.isi.edu). Although a bit large, it is faster than format-graph-from-root for large graphs. It provides a zoomed out picture of the entire graph which may be used to scroll a zoomed in window. ------------------------------------------------------------------------ >From bryan%sierra.STANFORD.EDU Wed Nov 8 07:44:15 1989 Date: Tue, 7 Nov 89 12:07:19 PST From: Daniel Winkowski <dgw@mimsy.umd.edu> Date: Tue, 27 Sep 88 11:49:21 EDT From: Bruce Israel <israel@brillig.umd.edu> Date: Tue, 20 Sep 88 17:38:17 EDT I just started installing ISI-Grapher at work, which is a package to do that sort of thing, available from USC-ISI. I don't know how much it costs or anything like that. I can look up more exact contact information if you are interested. Bruce ------------------------------------------------------------------------ >From bryan%sierra.STANFORD.EDU Wed Nov 8 07:44:15 1989 Date: Tue, 7 Nov 89 12:07:19 PST From: Daniel Winkowski <dgw@mimsy.umd.edu> Date: Tue, 27 Sep 88 11:49:21 EDT From: George McKee <mckee@corwin.ccs.northeastern.edu> Date: Wed, 21 Sep 88 11:46:59 EDT I have a vague memory of Ken Forbus at Illinois mentioning some such thing in a response to a similar inquiry a few months ago. I sent him email asking about it but never got a reply (we've been having internal network trouble, so his answer may not have gotten through). The system Forbus mentioned was hacked together by a grad student and may have worked under "Genera" 6.1 only. There's the ISI Grapher, but that's free only to Government sites. I've also got networks I'd like to draw on the screen; if you hear about reasonably generic code to do such things, I'd appreciate knowing what you find out... - George McKee College of Computer Science Northeastern University, Boston 02115 CSnet: mckee@Corwin.CCS.Northeastern.EDU Phone: (617) 437-5204 uucp: ...iuvax!corwin!mckee (don't ask why) ------------------------------------------------------------------------ >From bryan%sierra.STANFORD.EDU Wed Nov 8 07:44:15 1989 Date: Tue, 7 Nov 89 12:07:19 PST From: Daniel Winkowski <dgw@mimsy.umd.edu> Date: Tue, 27 Sep 88 11:49:21 EDT From: denny%dione.CRAY.COM@uc.msc.umn.edu (Denny Olson) Date: Tue, 20 Sep 88 14:15:31 CDT Daniel; > Is there any public software available for drawing directed cyclic or > graphs? Check with Dr. Ken Forbus of the University of Illinois. [forbus@p.cs.uiuc.edu] He posted something about this type of tool his group has produced at Illinois some time ago. Denny Olson Cray Research, Inc. ------------------------------------------------------------------------ >From bryan%sierra.STANFORD.EDU Wed Nov 8 07:44:15 1989 Date: Tue, 7 Nov 89 12:07:19 PST From: Daniel Winkowski <dgw@mimsy.umd.edu> Date: Tue, 27 Sep 88 11:49:21 EDT From: csw@Sun.COM (Christopher Warth) Date: Mon, 26 Sep 88 12:04:02 PDT Steve North at Bell Labs has a program called DAG to do exactly what you want. It is probably not public domain but you might want to talk to the author anyway. He can certainly supply copious references. Send mail to north@ulysses.att.com He'll probably contact you directly if he sees your posting. -csw ------------------------------------------------------------------------ >From bryan%sierra.STANFORD.EDU Wed Nov 8 07:44:15 1989 Date: Tue, 7 Nov 89 12:07:19 PST From: Stephen C. North <north%hector@att.arpa> Date: Tue, 22 Nov 88 15:43:21 Phong Vo, Emden Gansner, and I wrote DAG. It is based on the Sugiyama heuristics. Our contributions are: optimal node ranking improved mincross heuristics (often 50% less) final node placement using an L1 program an algorithm that gives good approximate solutions to the L1 program and is much faster. We have a paper that is about to appear in SPE that more or less describes this in the usual SPE style. You could get something working from this or even from reading the Sugiyama paper. We are working on a more detailed and formal presentation of the algorithms. We are trying to get binary release to certain universities and I put Stanford on the list. I hate to promise anything but it looks like the forces of good may win at least this much. If you send me your postal mailing address, I'll send you a preprint of the paper. Stephen North ------------------------------------------------------------------------ >From bryan%sierra.STANFORD.EDU Wed Nov 8 07:44:15 1989 Date: Tue, 7 Nov 89 12:07:19 PST From: Daniel Winkowski <dgw@mimsy.umd.edu> Date: Tue, 27 Sep 88 11:49:21 EDT From: rutgers!parns.NSC.COM!barnes The Sungrab Graph Layout Package is a set of C routines which accepts a specification for a directed graph. It attempts to find a two-dimensional layout of the graph which minimizes the number of edge-crossings. It's documented in Software Practice and Experience, Jan 1987. The paper is by L. Rowe et al. I have seen results from this package and it looks good, but I haven't seen or used the code. I should be grateful if you would mail me any information you find about graph packages, too. I'm more interested in packages running on X Windows, but anything can probably be re-targeted, as the real work is in the layout algorithm. tim barnes barnes@parns.nsc.com (408) 721 6169 ...!sun!nsc!parns!barnes ------------------------------------------------------------------------ >From bryan%sierra.STANFORD.EDU Wed Nov 8 07:44:15 1989 Date: Tue, 7 Nov 89 12:07:19 PST sungrab - sun graph browser SYNOPSIS sungrab [ -a aspect ratio ] [ -E ] [ -P ] [ -S ] [ name ] DESCRIPTION Sungrab is an editor for directed graphs. The graph is specified in the file named name. If no input file is specified, the file ``default.graph'' is assumed. Sungrab reads the input file and automatically lays out and displays the graph. The user can then edit the graph interactively (i.e., add, delete, and move nodes and edges), print a hard copy of the graph on a Varian plotter, or save the graph in a file for future edit- ing. The graph can be saved in sungrab format for sub- sequent browsing, or it can be saved in gremlin format for inclusion in a troff document or for further edit- ing with gremlin. The options are as follows: -a Allows the user to specify the aspect ratio of a subsequently saved gremlin image. That is, the number specified after the -a flag controls the ratio of the x-axis width to the y-axis width. For example, invoking sungrab with the option -a2 will produce gremlin files whose images are twice as wide as they are tall; -a0.33 will produce gremlin files whose images are three times as tall as they are wide. The default aspect ratio is 1. -E Nodes and edges "explode" when they are deleted. For the easily amused. -P Sends sungrab into pbrowse mode. See the pbrowse manual page. -S Turns on the remote procedure call interface of sungrab. The protocol is described in the client manual page. Before running sungrab, it is necessary to start up suntools and to open up a window. The format of the input file is as follows. The first field on a line begins at the left margin. Fields on a line are separated by tab characters (indicated here as ``<tab>''). All lines before the line beginning with ``*NAME*'' are ignored. After the keyword ``*NODES*'' all the nodes are listed by name, one per line. After the keyword ``*EDGES*'' the edges are listed, one per line, by specifying a source node and a destination node, separated by a <tab>. *NAME* title of graph *NODES* node node : *EDGES* from_node <tab> to_node from_node <tab> to_node : SEE ALSO pbrowse(local), client(local), gremlin(local), suntools(sun) Sungrab -- A Browser for Directed Graphs Sungrab: A Tutorial AUTHOR The GRAB Group BUGS + If do a zoom, then a screen stretch, then a zoom, then do a size to fit, we will get back to the screen of the zoom before the screen stretch, instead of the original screen. + Left mouse button in browse mode acts funny some- times (though not lately). This is a pre-release version of sungrab. Please send bugs and comments to grab@ingres.Berkeley.EDU. sources on postgres.berkeley.edu ------------------------------------------------------------------------ >From bryan%sierra.STANFORD.EDU Wed Nov 8 07:44:15 1989 Date: Tue, 7 Nov 89 12:07:19 PST From: lim@iris.ucdavis.edu (Lloyd Lim) Date: 6 Jul 89 20:07:31 GMT Subject: graph layout summary Here is the summary of references for graph layout that I promised. I thought I had a longer list but when I finally checked through all of my responses, most of them turned out to be requests for summaries. Some references were to vague for me to locate. At the least, three good surveys are listed here and some newer articles I found myself are listed. This should give anyone a good start. Note that graph drawing, layout, and embedding are all terms for the same thing. The following three papers provide good surveys and/or bibliographies of graph layout problem. P. Eades and R. Tamassia, "Algorithms for Drawing Graphs: An Annotated Bibliography", Technical Report #82, Department of Computer Science, University of Queensland, Australia, 1987 R. Tamassia, G. Battista, and C. Batini, "Automatic Graph Drawing and Readability of Diagrams", IEEE Trans. Syst., Man, Cybern., SMC-18 (1988), pp. 61-79 E.B. Messinger, "Automatic Layout of Large Directed Graphs", TR 88-07-88, Department of Computer Science, University of Washington The address to write to for obtaining this one is: Dept. of Computer Science, FR-35 University of Washington Seattle, WA 98195 This is here for the hell of it. I think it's one of the first papers on graph drawing. W.T. Tutte, "How to Draw a Graph", Proc. London Math Soc., v. 3 (1963), pp 743-768 I received a copy in the mail of the following paper. I don't know if it is published or being considered for publishing at the moment. It gives O(e) algorithms for planarity testing, planar embedding, and computing the total number of different planar embeddings and an O(e log v) algorithm for finding the maximal planar subgraph of the input graph. I'm not sure if these algorithms are of practical use but they are theoretically important. The planarity algorithm is simplified while the maximal planar subgraph algorithm is a new result. J. Cai, X. Han, and R.E. Tarjan, "New Solutions to Four Planar Graph Problems" Rectilinear graph layout algorithms have been studied a lot since they are used for VLSI layout problems. The following article describes a divide and conquer framework using bifurcators. Layout area, crossing number, and minimax edge length are discussed. A good reference list for VLSI papers is included. I would say this paper is more theoretical. S.N. Bhatt and F.T. Leighton, "A Framework for Solving VLSI Graph Layout Problems", Journal of Computer and System Sciences, v. 28 (1984), pp. 300-343 The following paper describes a linear time alogrithm for recognizing and embedding planar rectilinear graphs. Psuedocode is provided. F. Hoffmann and K. Kriegel, "Embedding Rectilinear Graphs in Linear Time", Information Processing Letters, v. 29 (1988), pp.75-79 I am most interested in drawing straight line undirected graphs. This paper is the general algorithm I was looking for. The algorithm is very simple. Psuedocode is provided. I'm not sure how the speed is for large graphs since I haven't implemented it yet and the algorithm is dynamic. If anyone happens to know the email addresses of either Tomihisa Kamada or Satoru Kawai at the University of Tokyo, I would love to have them. I kind of like this approach. T. Kamada and S. Kawai, "An Algorithm for Drawing General Undirected Graphs", Information Processing Letters, v. 31 (1989), pp. 7-15 The algorithm in the following article was reported to have disappointing performance - 13 minutes for 280 nodes on a Sun 2. I think the above algorithm is slower since it takes 7.6 seconds for a regular dodecahedron (20 nodes) on a VAX 8600. Using an optimistic extrapolation based on O(v**2), it comes out to almost 25 minutes for 280 nodes on a VAX 8600. L.A. Rowe, M. Davis, E. Messinger, C. Meyer, C. Spirakis, and A. Tuan, "A Browser for Directed Graphs", Software Pract. Exper., v. 17 (1987), pp. 61-76 Thanks to all who responded. +++ Lloyd Lim Internet: lim@iris.ucdavis.edu Compuserve: 72647,660 US Mail: 146 Lysle Leach Hall, U.C. Davis, Davis, CA 95616 ------------------------------------------------------------------------ >From mcnabb%uxe.cso.uiuc.edu Wed Nov 8 07:42:40 1989 From: Dave McNabb <mcnabb@uxe.cso.uiuc.edu> Date: Tue, 7 Nov 89 10:21:03 -0600 Subject: display and manipulation of trees [...] The only thing I have to offer at this point is a reference to a paper by Reingold and Tilford which presents an optimal algorithm for "tidier" display of trees. Though the output device was not graphical (lp or dumb terminal) the algorithm can easily be generalized to better representation of the nodes and links; it is primarily concerned with placement of the centers of nodes. This article marked the end of a long battle over how to display trees in the most pleasing or tidy form. I can send you the exact reference if you are interested, and may even be able to locate a copy of the original code (Pascal I believe). Tilford left uiuc for Rational and has become an Ada guru; he might have redone some of this work in Ada... David McNabb RIVERS Project National Center for Supercomputing Applications University of Illinois at Urbana-Champaign INTERNET: mcnabb@ncsa.uiuc.edu USENET: ...!{cmcl2,seismo,uunet}!uiucdcs!zaphod!mcnabb ------------------------------------------------------------------------ >From mcnabb%iroquois@ux1.cso.uiuc.edu Wed Nov 8 23:47:40 1989 From: mcnabb%iroquois@ux1.cso.uiuc.edu (David McNabb) Date: Wed, 8 Nov 89 14:22:34 CST Subject: Re: display and manipulation of trees The "Tidier Drawings of Trees" paper appeared in IEEE something, probably Computer. Sorry but I cannot seem to find that reference. I did find the tech report: Tilford, John S. "Tree Drawing Algorithms", Department of Computer Science Technical Report #1055, University of Illinois at Urbana-Champaign, Urbana, Illinois, 1981, p. 65. You might be able to get this by contacting Erna Amerman, Dept of Computer Science, Univ of Ill. at Urbana-Champaign. (email: erna@a.cs.uiuc.edu) If she is out she can surely point you at the UI source for tech reports (which will charge you something minimal... []). Let me know what you think. If you are still interested I'll see if I can get you an email address for Tilford, and/or source code. -DM ------------------------------------------------------------------------ >From bryan%sierra.STANFORD.EDU Wed Nov 8 07:44:15 1989 From: bryan@sierra.STANFORD.EDU (Doug L. Bryan) Date: Tue, 7 Nov 89 12:07:19 PST Subject: graph layout and display > mcsun!prlb2!prlbcom!kulcs!dirk@uunet.uu.net (Dirk Craeynest) > Graphical representation of trees and graphs Dirk, I've built a quick-and-dirty 300 line Ada program which browses our version of DIANA. Other, more respectable, layout software is listed below. [see other messages -dc] doug ------------------------------------------------------------------------ >From 4237_5606@uwovax.uwo.ca Thu Nov 9 00:16:08 1989 From: Eric Ho <4237_5606@uwovax.uwo.ca> Date: Wed, 8 Nov 89 17:00:55 est Subject: Graphical representation of trees and graphs I know that there is a package (PD) doing the above mentioned things, however, this is written in modula-2 by a guy in Cali. Tech. I think you should try ftp to simtel20.arpa, there is a ADA directory containing various PD ada sources, hope this helps! best wishes, eric ----- e.ho@uwovax.uwo.ca Rare as is true love, ture friendship is still rarer. - La Rochefoucauld ------------------------------------------------------------------------ Dirk Craeynest | bitnet: dirk@blekul60.bitnet Katholieke Universiteit Leuven | domain: dirk@cs.kuleuven.ac.be Department of Computer Science | uucp: dirk@kulcs.uucp Celestijnenlaan 200 A | {uunet,mcsun}!prlbcom!kulcs!dirk B-3030 Leuven (Heverlee), Belgium | phone: +(32) 16-200656 x3555 telex: 23674 kuleuv b | fax: +(32) 16-205308