Programming Assignment 1 - Tidy Tree Drawings

Advanced Programming II, Spring 2003

Due Date

This assignment is due by 2:00 p.m. on Tuesday, 4 February.

See the assignment turn-in page (last modified on 21 January 2003) for instructions on turning in your assignment.

Some free-hand sketching programs have the ability to tidy drawings. For example, if a user of such a program produced the drawing on the left, the program might actually output the tidy drawing on the right:

The Problem

Write a program that accepts from std-in a free-hand sketch of a tree and writes to std-out a tidy version of the input tree.

Assuming a coordinate system in which x increases to the right and y increases going down, a tree is tidy if all the following properties hold:

All nodes are circles of the same diameter.
All nodes the same distance away from the root have collinear centers; the line through the centers is called the level line.
All level lines are parallel to the x axis.
The distance between an adjacent pair of level lines is the same as the distance between any adjacent pair of level lines.
A parent is centered horizontally over its children, if any.
Subtrees should be placed so that some small amount of space (say half of the node radius) appears between adjacent.

Input

Input consists of a sequence of zero or more strokes. Each stroke represents a node or an edge between nodes.

A stroke is a sequence of four or more integers interpreted as a sequence of (two or more) (x, y) point coordinates. Each integer is separated from adjacent integers by at least one non-newline space character. Every integer on the same line is part of the stroke defined by the line.

Any number of space characters may appear between adjacent strokes.

The node with the smallest y coordinate should be considered the root node; if more than one node has the same y coordinate, your program may choose any of the nodes with the same y coordinate to be the root.

A stroke that doesn't appear to be a node or an edge should be flagged as illegal input.

Output

If the input describes a valid tree, the output should describe a tidy version of the tree using the following format:

The word nodes followed by a sequence of integers interpreted as a sequence of (x, y) points describing the node centers. Node centers may be listed in any order.
The word edges followed by a sequence of integers interpreted as a sequence of a sequence of (x, y) points describing edge endpoints. The first four integers describe the endpoints of the first edge, the second four integers describe the endpoints of the next edge, and so on. Edges may be listed in any order.

Adjacent elements of output must be separated by at least one space character. Nodes may appear before edges or vice versa.

If the input is invalid, your program should output to std-err a single error message describing the problem; only the first problem discovered need be reported.

Testing

There are two programs available to test your code. tsketch produces input in the format required by your program; tshow accepts output in the format produced by your program and displays it. Both of these programs can be found in the assignment directory /export/home/class/cs-509/pa1 from any cslab machine or rockhopper.

Both tsketch and tshow use the X Window System. You must be sitting in front of a system that's running the X window system to to use either program; if you are sitting in front of a system that's not running the X window system, you can't use either program.

If you are sitting in front of a cs lab machine, a pc running linux, or an sgi and you're running a window manager, then you're sitting in front of a system running the X window system and you can use either program.

If you're sitting in front of a pc running ms software, then you are sitting in front of a system that is not running the X window system and you can't use either program.

However, you may still have problems if you're sitting in from of a system running the X window system. If you have remotely logged into another system (using telnet, rlogin, or rsh) and you're trying to run either program on the remote system, you have to also do the following:

Find the name of your local system using the hostname command:
```
loc: hostname
clayton

loc: 
```
Set and export the DISPLAY environment variable on the remote system to
```
localsystemname:0.0
```
where localsystemname is the name of your local system. For example, type
```
rem: export DISPLAY=clayton:0.0

rem: 
```
if you're using ksh.
On the local host, type
```
xhost + 
```
you should get an message like "access control disabled, clients can connect from any host":
```
loc: xhost +
access control disabled, clients can connect from any host

loc: 
```
If you're paranoid about giving every host access to your screen, you can type instead (on the local host)
```
xhost remotesystemname
```
where remotesystemname is the name of the remote system:
```
loc: xhost cslab18
cslab18 being added to access control list

loc: 
```
You should now be able to run either program on the remote system and have the windows pop up on the local system's screen.

This page last modified on 22 January 2003.