CSC212 Lab 10 2014

--D. Thiebaut (talk) 22:52, 28 October 2014 (EDT)

---

Generating Graphic Representations of Trees

Graphviz is a simple engine for generating very polished images of trees or graphs. Graphviz takes the definition of a tree, or of a graph, written in a specific language called DOT and produces images of the tree or graph structure. Graphviz is sometimes installed on Linux systems, and can be installed as well on Windows and Mac computers. See the see Graphviz's Download page for more details.
Let's generate a simple Tree.

• Open this page in your browser: http://graphviz-dev.appspot.com/ (if the site is down, try this one instead: http://sandbox.kidstrythisathome.com/erdos/
• Make sure DOT is selected as the language
• Enter the following graph definition in the Edit window.

digraph "Lab10" {
   8 -> 3;
   3 -> 4;
   3 -> 10;
   3 -> 7;
   8 -> 12;
}

• As you type, you should see a graph appearing in the right window.

Challenge 1: Create A Binary-Search Tree

• Use the same utility to create the tree used in the lecture slides, and shown below:

• You will notice that the tree doesn't display well when a node only has 1 child. To get a more accurate left-right balance of the nodes, we simply need to create "fake" nodes for the null pointers.

Adding "Fake" Null Nodes

The two nodes that do not display well are 10 and 14 because they have only 1 child each. To prevent the vertical alignment, we can declare them as follows, in the DOT language:

digraph "Lab10" {
   8 -> 3;
   8 -> 10;
   3 -> 1;
   3 -> 6;
   6-> 4;
   6 -> 7;
   null10left  [shape=point];
   10 -> null10left;
   10 -> 14;
   14 -> 13;
   null14right [shape=point];
   14 -> null14right;
}

• Go ahead and enter the new definition for the tree. Observe that it is now correctly oriented.

The Dot Language

• You have just learned a new language! DOT.
• It is quite rich, and will allow you to generate more sophisticated trees (or graphs) than we have done in this lab, and you can see some examples of graphs here: http://www.graphviz.org/Gallery.php.
• If you are interested in learning more about the Dot language for generating trees or graphs with graphviz, you may want to read this Wikipedia page on the Dot Language.