STL extension - directed graph [40C]

Contributed by David Fisher

Create an STL style "digraph" template class (with template parameters LabelType and ValueType) with the following member functions: constructor, destructor, copy constructor, copy assignment, addNode(label, value), removeNode(label), addEdge(label1, label2), removeEdge(label1, label2), isEdge(label1, label2), setNodeLabel(oldLabel, newLabel), getNodeValue(label), setNodeValue(label).

Also define the following kinds of iterators:

• - NodeIterator - all nodes in the digraph
• - EdgeIterator - all edges in the digraph
• - BFS/DFSIterator - "depth first" and "breadth first" traversal iterators, starting from a particular node
• - In/OutEdgeIterator - iterate over all "in" or "out" edges for a node

Program elements

Reinforces: understanding of STL containers and iterators; graph algorithms

Extension [60D]

create a "subgraph" class which shares data with its parent graph/subgraph. Add a function findComponents() to the digraph class which returns a list of subgraphs (weakly connected components). The subgraph should continue to exist if the parent graph is deleted. This can reinforce reference counting.