Lab #5: Graph & Tree

Introduction

In this lab, we'll study the techniques for handling graphs and trees.

This lab is divided into three parts. The first part discusses a graph visualization tool---graphviz. And the second part delves into the problem of automatic graph visulization. Finally, the third problem studies graph data structures and related algorithms.

1. Graphviz

Graphs are easier to implement and graph algorithms are easier to debug, if the graph internel structures are visualized in some friendly form. Fortunately, there are some powfer tools to help doing such kind of job. In this course, the graph visualization tool we'll be using is Graphviz. Graphviz is a popular and widely used graph drawing tool kit. In this problem, we'd like to play with the Graphviz software.

First, you'd want to download and install the Graphviz software to your machine.

After intalling it, let's see how Graphviz works. (Here we only cover its basic usage, for complete reference, you'd like to read the online documentation.) Basically, Graphviz reads as input some text file and outputs an image file. The input text file contains a program written in a programming language called "DOT". And this program decribes all information to draw a graph: say, the vertices, the edges, the colors, etc.. After reading the text file, graphviz automatically draws a figure according to the DOT program in it.

To better understanding this process, let's study some simple examples. Now download this DOT source file: demo1.dot to your computer. Skim its code, you can see these:

digraph g
{
  "1"->"2";
  "2"->"3";
  "3"->"4";
  "4"->"1";
}

As we can see, the structure of a DOT program is very much like that of a C program. We'd like to present some explainations. The digraph is a key word, which tells that we want to draw a directed graph called "g". And between the two braces { and } are a list of statements, each of which takes this form:

i -> j;

where both i and j are vertices. This statement i -> j specifies that we want an edge from vertex i to vertex j. So as a whole, we have four edges in this DOT file:

"1"->"2";
  "2"->"3";

etc..

Then how can we draw this graph? It's relatively easy. On Windows or Linux, open a command line prompt, go to the directory where your file demo1.dot resides. And type this command in:

dot -Tjpg domo1.dot >demo1.jpg

Press enter, if no accident, a pretty JPG file demo1.jpg should have been generated. But what does the above command mean? It's may be clear after you try this:

dot -Tpdf domo1.dot >demo1.pdf

Cool? Hur? :-) But the real power of Graphviz comes from the fact that it's fully configurable. To see this, leave as an exercise to you to study two more examples: demo2.dot and demo3.dot.

This finishes our study of the Graphviz tool kit. And to know more, you should read the documentation, and try to figure out what kind of other cool things you can do with it.

2. Graph Visulization

Having known how Graphviz works, our goal is to write a software module which automatically finishes the task of graph drawing. Download this software template to start with. You don't need to write any code, just make sure you understand the code we offered you.

Browse the code, you should first run the executable "tcc.exe":

tcc

and check the output. Then read the file main.c, and explain to yourself how this output is generated.

To get help and hint, you should run with:

tcc --help

3. Graph

In this problem set, your job is to write the graph data structures and operations. Download this code template to start with.

There is an executable called graph.exe, you may want to run it to get some ideas.