Discrete Mathematics and Its Applications

Programming Assignment #4: Graphs and Trees

• Graphviz is a popular and widely used graph drawing tool kit. And it's helpful to use it extensively in our future programming assignments. In this problem, we'd like to play with the Graphviz software.
  • Installation. Download and install the Graphviz software. (Or, you may want to download and install this local copy.)
  • The input to Graphviz is called "dot" files. Try to draw figures (graphs) from these three dot files: dot source1, dot source2 and dot source3.
  (Note: the facilities we've seen in these three dot files are enough for the current programming assignment. However, the Graphviz tool kit is more powerful than these above demos have demonstrated. For its detailed information, refer to the Graphviz website.)
• (Optional, extra credit.) In this problem, our task is to design and implement a module called "dot". The dot module could turn user input into a "dot" representation (just as we've seen in the problem 1), and then into a "jpg" file. The interface for the dot module looks like:

  signature dot =
    type dot
    
    dot newDot ();
    void dotInsert (string from, string to, string info, dot d);
    void dotToJpg (dot d, string fileName);
  end
  

  In which, the type dot is an ADT decribing the structrue of a dot (not a dot file). Function dotInsert inserts a new edge (staring from node from to node to, with extra information info on this edge) into the dot d. Finally, the function dotToJpg draw the dot d into a jpg file named fileName.

  As an example, consider the dot source3 in problem 1, the client code to generate this dot looks roughly like (in C):

  // file main.c
  #include "dot.h"
  
  int main ()
  {
    // create an empty dot
    dot d = newDot ();
    // inserting edges
    dotInsert ("1", "2", "2.4km", d);
    dotInsert ("2", "3", "1.5km", d);
    dotInsert ("3", "4", "4.3km", d);
    dotInsert ("4", "1", "20.9km", d);
    
    // draw this dot "d" in a jpg file named "demo3.jpg"
    dotToJpg (d, "demo3");
  
    return 0;
  }
  

• In this and the next problem, we'll make use of the "dot" module from problem 2. And if you don't finish that problem, you may use our implementation (the files "dot.h" and "dot.c" in the "lib" subdirectory).

  In this problem, our task is to design and implement an extensible "tree" ADT. The interface for the extensible tree ADT looks like the following one. Note that you're required only to implement either the adjacency matrix or the adjacency list representation.

  signature tree =
    type tree
    typedef void (*visitTy)(poly); // in C's syntax
  
    // create an empty tree
    tree newTree ();
    // insert a new vertex "v" into a tree "t"
    void treeInsertVertex (tree t, poly v);
    // insert an edge starting from vertex "from" to vertex "to"
    void treeInsertEdge (tree t, poly from, poly to);
    // insert an edge starting from vertex "from" to vertex "to", with the edge information "info"
    void treeInsertEdgeInfo (tree t, poly from, poly to, poly info);
    // draw the tree "t" in a jpg file named "fileName.jpg"
    void treeToJpg (tree t, char *fileName);
    // visit the tree "t" in preorder, using the function "visit"
    void treePreOrder (tree t, poly root, visitTy visit);
    // visit the tree "t" in inorder, using the function "visit"
    void treeInOrder (tree t, poly root, visitTy visit);
    // visit the tree "t" in postorder, using the function "visit"
    void treePostOrder (tree t, poly root, visitTy visit);
    // visit the tree "t" in level-order, using the function "visit"
    void treeLevelOrder (tree t, poly root, visitTy visit);
  end
  

• In this problem, our task is to design and implement a "graph" ADT. The interface for the graph ADT looks like the following one:

  signature graph =
    type graph
    typedef void (*visitTy)(poly);
  
    // create an empty graph
    graph newGraph ();
    // insert a new vertex "v" into a graph "g"
    void graphInsertVertex (graph g, poly v);
    // insert an edge starting from vertex "from" to vertex "to"
    void graphInsertEdge (graph g, poly from, poly to);
    // insert an edge starting from vertex "from" to vertex "to", with the edge information "info"
    void graphInsertEdgeInfo (graph g, poly from, poly to, poly info);
    // walk the graph "g" in dfs order starting from vertex "start", visit every vertex using function "visit"
    void graphDfs (graph g, poly start, visitTy visit);
    // dfs the graph "g" starting from vertex "start", calculate and return the dfs-tree
    tree graphDfsTree (graph g, poly start);
    // walk the graph "g" in bfs order starting from vertex "start", visit every vertex using function "visit"
    void graphBfs (graph g, poly start, visitTy visit);
    // bfs the graph "g" starting from vertex "start", calculate and return the bfs-tree
    tree graphBfsTree (graph g, poly start);
    /////////////////////////////////////////////////////
    // Note: the following functions are ALL optional  //
    /////////////////////////////////////////////////////
    // Dijkstra algorithm
    tree graphDijkstra (graph g, poly start);
    // topological sorting
    void graphTopoSort (graph g);
    // Kruskal algorithm
    tree graphKruskal (graph g);
    // Prim algorithm
    tree graphPrim (graph g);
  end