CS 5510 Homework 1

Due: Monday, January 25th, 2010 9:40am

Implement homework assignments in whatever functional language you like. If you don't know what to use, then use PLT Scheme. If you use PLT Scheme and need to learn the language, see the getting-started page in the documentation, which is also included in the distribution.

Part 1 – Reading a Graph

A directed graph is supplied on standard input as a sequences of lines, where each line is a sequence of distinct positive integers followed by a color and two positive real numbers. The numbers and colon are separated by one or more spaces, and extra spaces can appear at the beginning or end of the line. The first number in a line represents a node that is connected to the node represented by each of the other numbers in the same line. The final two numbers represent the dimensions of a graphical representation of the node, width followed by height. The first number in each line is distinct from the first number in all other lines (i.e., each node's outgoing edges are specified once), and every number that appears in the input is the first number of some line (i.e, each node is specified).

For example, the input

  1 2 3 : 2.0 10.0
  2     : 2.0 5.0 
  3     : 2.0 5.0

describes a tree of three nodes, where node 1 is the root and nodes 2 and 3 are its children. The graphical representation of each node is 2.0 units wide; the root is 10.0 units tall, while the other nodes are 5.0 units tall.

As another example,

  10 5 7 : 1.0 1.0
  5 7 10 : 1.0 1.0
  7 10 5 : 1.0 1.0

describes a graph containing three nodes that are linked in all possible ways.

When your program reads a graph, it should check that the input obeys the contract specified above (each node is defined once, etc.).

Part 2 – Detecting Trees

Having read a graph, detect whether it represents a forest of trees.

Part 3 – Detecting DAGs

Detect whether a graph represents a directed acyclic graph.

Part 4 – Drawing Graphics Nicely

Generate a layout for an input graph, and report it as a sequence of lines, one for each input node, with the node number followed by two real numbers representing a position left and down from some origin.

Generating a “nice” layout can be arbitrarily difficult, but for the special cases of forests and DAGs, your program should produce “obviously nice” output. For example, a good output for the first example above might be

  1 0.5 0.0
  2 0.0 3.0
  3 6.0 3.0

which centers the root above its two children.

Part 5 – Really Drawing

Make your program draw the graph and produce a picture. By producing a picture, you get more control over the ways that edges are drawn to connect nodes.