Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

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 gif 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 gif 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 gif 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 gif). Write a test program and test your implementation.
  6. Repeat Project gif 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 gif.


next up previous contents index

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