Data Structures and Algorithms with Object-Oriented Design Patterns in Python

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  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  by providing suitable definitions for the following operations: __init__, purge, addVertex, getVertex, addEdge, getEdge, isEdge, vertices, edges, getIncidentEdges, and getEmanatingEdges. Write a test program and test your implementation.
4.   Repeat Project  for the GraphAsLists class.
5.   The DigraphAsMatrix class can be implemented by extending the GraphAsMatrix class introduced in Program  and the abstract Digraph class introduced in Program :

   class DigraphAsMatrix(GraphAsMatrix, Digraph):
       # ...

   Implement the DigraphAsMatrix class by providing suitable definitions for the following methods: __init__, purge, addEdge, getEdge, isEdge, vertices and edges. You must also have a complete implementation of the base class GraphAsMatrix (see Project ). Write a test program and test your implementation.
6. Repeat Project  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 abstract Graph class introduced in Program .
8. Devise an approach using an enumerator 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 .

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