University of Virginia, Department of Computer Science
CS201J: Engineering Software, Fall 2002

Notes: Thursday 12 September 2002
Assignments Due

Notes and Questions

What are the advantages and disadvantages of each approach to array bounds errors:

Graph Data Abstraction

In class Tuesday, we will work on implementing a Graph data abstraction that satisfies this specification:

public class Graph {
   // OVERVIEW: 
   //      A Graph is a mutable type that represents an undirected
   //      graph.  It consists of nodes that are named by Strings,
   //      and edges that connect a pair of nodes.
   //      A typical Graph is: < Nodes, Edges >
   //       where
   //         Nodes = { n1, n2, , nm }
   //       and 
   //         Edges = { {from_1, to_1}, , {from_n, to_n} }

   // Creator
   public Graph () 
      // EFFECTS: Initializes this to a graph
      //      with no nodes or edges: < {}, {} >.

   // Mutators
   public void addNode (String name)
      // REQUIRES: name is not the name of a node in this
      //  MODIFIES: this
      // EFFECTS: adds a node named name to this:
      //     this_post = < this_pre.nodes U { name }, this_pre.edges >

   public void addEdge (String fnode, String tnode)
      // REQUIRES: fnode and tnode are names of nodes in this.
      // MODIFIES: this
      // EFFECTS: Adds an edge from fnode to tnode to this:
      //       this_post = < this_pre.nodes, this_pre.edges U { {fnode, tnode} } >

   // Observers
   public boolean hasNode (String node)
      // EFFECTS: Returns true iff node is a node in this.

   public StringIterator nodes ()
      // EFFECTS: Returns the StringIterator that
      //      yields all nodes in this in arbitrary order.

   StringSet getNeighbors (String node)
      // REQUIRES: node is a node in this
      // EFFECTS: Returns the StringSet consisting of all nodes in this
      //      that are directly connected to node:
      //         \result =  { n | {node, n} is in this.edges }

CS201J University of Virginia
Department of Computer Science
CS 201J: Engineering Software
Sponsored by the
National Science Foundation