Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Projects

  1.   Devise a graph description language. Implement a method that reads the description of a graph and constructs a graph object instance. Your method should be completely generic--it should not depend on the graph implementation used.
  2.   Extend Project gif by writing a method that prints the description of a given graph object instance.
  3.   Complete the implementation of the GraphAsMatrix class introduced in Program gif by providing suitable definitions for the following methods: GraphAsMatrix (constructor), purge, addVertex, getVertex, addEdge, getEdge, isEdge, getVertices, getEdges, getIncidentEdges, and getEmanatingEdges. Write a test program and test your implementation.
  4.   Repeat Project gif for the GraphAsLists class.
  5.   The DigraphAsMatrix class can be implemented by extending the GraphAsMatrix class introduced in Program gif to implement the Digraph interface defined in Program gif:
    public class DigraphAsMatrix
        extends GraphAsMatrix
        implements Digraph
    {
        // ...
    }
    Implement the DigraphAsMatrix class by providing suitable definitions for the following methods: DigraphAsMatrix (constructor), purge, addEdge, getEdge, isEdge, and getEdges. You must also have a complete implementation of the base class GraphAsMatrix (see Project gif). Write a test program and test your implementation.
  6. Repeat Project gif for the DigraphAsLists class.
  7. Add a method to the Digraph interface that returns the undirected graph which underlies the given digraph. Write an implementation of this method for the AbstractGraph class introduced in Program gif.
  8. Devise an approach using an enumeration and a stack to perform a topological-order traversal by doing a postorder depth-first traversal in reverse.
  9. The single-source shortest path problem on a DAG can be solved by visiting the vertices in topological order. Write an visitor for use with the topologicalOrderTraversal method that solves the single-source shortest path problem on a DAG.
  10.   Devise and implement an method that transforms a vertex-weighted activity-node graph into an edge-weighted event-node graph.
  11. Complete the implementation of the critical path analysis methods. In particular, you must implement the LatestTimeVisitor along the lines of the EarliestTimeVisitor defined in Program gif.


next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.