Projects

1.   Devise a graph description language. Implement a routine that reads the description of a graph and constructs a graph object instance. Your routine should be completely generic--it should not depend on the graph implementation used.
2.   Extend Project  by writing a routine that prints the description of a given graph object instance.
3.   Complete the implementation of the GraphAsMatrix class declared in Program  by providing suitable definitions for the following member functions: GraphAsMatrix (constructor), GraphAsMatrix (destructor), Purge, AddVertex, SelectVertex, AddEdge, SelectEdge, IsEdge, Vertices, Edges, IncidentEdges and EmanatingEdges. Write a test program and test your implementation.
4.   Repeat Project  for the GraphAsLists class.
5.   The DigraphAsMatrix class can be implemented using multiple inheritance:

   class DigraphAsMatrix : public Digraph, public GraphAsMatrix
   {
       ...
   };

   Implement the DigraphAsMatrix class by providing suitable definitions for the following member functions: DigraphAsMatrix (constructor), DigraphAsMatrix (destructor), Purge, AddEdge, SelectEdge, IsEdge 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 member function to the Digraph class abstract interface that creates an instance of and returns a reference to an undirected graph which underlies the given digraph.
8. Devise an approach using an iterator 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 routine that solves the single-source shortest path problem on a DAG.
10.   Devise and implement an routine that transforms a vertex-weighted activity-node graph into an edge-weighted event-node graph.
11. Complete the implementation of the critical path analysis routines. In particular, you must implement the LatestTimeVisitor along the lines of the EarliestTimeVisitor defined in Program .

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