The George Washington University
School of Engineering and Applied Science
Department of Electrical Engineering and Computer Science

CSci 131 - Data Structures - Fall 1997
Programming Project #5

Due Date: Section 10: Dec. 2, 1997, Section 11: Dec. 1, 1997

The final project involves writing a program which accepts information regarding the calling relationships between the subprograms of an Ada program and produces a tree diagram illustrating the program structure. This is a miniature of the sort of calling relationships that must be computed by compilers and other program analysis tools.

These calling relationships can best be represented using a directed graph. You will use a modified version of the package Digraphs_Generic. Modify the representation of the graph, so that it uses the adjacency list representation shown in figure 10.8 of the textbook. The new package specification should look as follows:

  GENERIC

  TYPE Vertices IS (<>);

PACKAGE Digraphs_Generic_ADO IS
------------------------------------------------------------------------
--| Specification for unweighted digraphs with discrete vertex sets
--| This is an Abstract Data Object (ADO) version.
--| Each instantiation produces a single graph object.
--| Author: Michael B. Feldman, The George Washington University 
--| Last Modified: November 1997.                                   
------------------------------------------------------------------------

  -- constructors

  PROCEDURE InitializeGraph;
  -- Pre:  none
  -- Post: the graph has no edges

  PROCEDURE AddEdge (Source, Destination: IN Vertices);
  PROCEDURE DeleteEdge (Source, Destination: IN Vertices);
  -- Pre:  Source, and Destination are defined
  -- Post: adds or deletes the edge <Source, Destination>
  --       AddEdge has no effect if the edge is 
  --       already in the graph; DeleteEdge has no effect if 
  --       the edge is not in the graph

  FUNCTION IsEmpty RETURN Boolean;
  -- Pre:  None
  -- Post: returns True if and only if the graph is empty

  FUNCTION NumberOfEdges RETURN Natural;
  -- Pre:  None
  -- Post: returns the number of edges in the graph

  FUNCTION IsAdjacent (Source, Destination: Vertices) 
    RETURN Boolean;
  -- Pre:  Source, and Destination are defined
  -- Post: returns True if and only if the graph has an 
  --       edge <Source, Destination>

  PROCEDURE DisplayGraph;
  -- Pre:  None
  -- Post: displays the graph in matrix form using T or F 
  --       for presence or absence of edge

  FUNCTION GetDepth RETURN Natural;
  -- Pre:  None
  -- Post: returns the current length of a traversal path

  GENERIC
    WITH PROCEDURE Visit(V: Vertices);
  PROCEDURE Traverse_BFS (Start: IN Vertices);
  -- Pre:  V is defined
  -- Post: performs breadth-first traversal starting at vertex V

  GENERIC
    WITH PROCEDURE Visit(V: Vertices);
  PROCEDURE Traverse_DFS (Start: IN Vertices);
  -- Pre:  V is defined
  -- Post: performs depth-first traversal starting at vertex V

PRIVATE

  TYPE Node;
  TYPE List IS ACCESS Node;
  TYPE Node IS
    RECORD
      Adjacent_Vertex: Vertices;
      Next_Vertex: List;
    END RECORD;
  TYPE AdjacencyList IS ARRAY(Vertices) OF List;
  TYPE Digraph IS RECORD
    Store: AdjacencyList;
    Depth: Natural := 0;
  END RECORD;
  OneGraph: DiGraph;
END Digraphs_Generic_ADO

This package differs in two ways: first, it is an ADO, not an ADT, package. Second, there is an additional operation GetDepth (see below).

You must modify the subprograms in the package body to reflect this change. Traverse_DFS and Traverse_BFS are implementation-independent, but you'll need to modify Traverse_DFS as given below.

For simplicity, let us assume that the subprogram names are the names Main, Procedure1, Procedure2, Procedure 3, Procedure4 and Procedure5. Define an enumeration type in your main procedure to define these choices. Instantiate the graph package with this enumeration type as the vertices.

The input to this program will be a file containing pairs of subprogram names defining the calling relationship of some Ada program. An example of an input file is the following:

  Main Procedure1
  Main Procedure2
  Main Procedure5
  Procedure1 Procedure3
  Procedure1 Procedure4

The first line of the above input file indicates that Main calls Procedure1. Your program should add an edge to the directed graph from Main to Procedure1. Once all calling relationships have been input, your program should output a tree using indentation to indicate the calling relationships. The output for the previous input should look as follows:

  Main
    Procedure1
      Procedure3
      Procedure4
    Procedure2
    Procedure5

You may assume that the calling relationships in the program contain no subprograms that are called by more than one other subprogram and contain no recursive calls, either direct or indirect.

To produce the above output you will need to make a modification to the DepthFirst procedure within Traverse_DFS. The component Depth should be incremented prior to the loop in the DepthFirst procedure and decremented after the loop. It should be initialized inside Traverse_DFS prior to the call to DepthFirst.

The function GetDepth retrieves this value. To produce the above structure diagram (which is actually called a spanning tree), call the Traverse_DFS procedure instantiated with a Visit procedure that displays the vertex name, but prior to the name it displays an appropriate number of spaces based on the value retrieved from GetDepth.