COMP 410 Fall 2015

Part 1: Build a Graph Data Structure


Summary

In this first part you will design and implement in Java a basic graph data structure.


The Test Driver

As you did in other assignments this semester, you will create an intereactive test driver that your main method will execute. The driver will allow you to construct and manipulate interactively a graph structure, as well as to examine its structure and contents.

The driver should first present the user with a simple one-line prompt and accept a one/two character command as input:

  command (q,an,ae,dn,de,s,pn,pg)?

Here are specifics for each command:

Considerations for Edges

We are using directed edges. We have also made the assumption that from any one node N to any node M there can be no edge, or 1 edge, but not more. This means that it is possible to have an edge (N,M) going from N to M, and also an edge (M,N) going from M to N.

Remember also that it is allowed to have an edge explicitly go from a node to itself. So here is a special case that we might have to worry about when adding and removing edges (depending on how you represent things). Make sure that your representation and handling does not allow you to create two edges from N to N (from N to N in one direction, and then N to N in the other direction). For many representations, this may naturally be not allowed; just be aware of the special case and make sure you handle it properly.

Considerations for Print Format

Include the node names and numbers, the edge numbers (and labels if they are there), and a visual indication of what the source and destination of each edge is. Something like this is fine:

  (0)NewYork 
    (0)---> Chicago
    (1)(prop)---> Washington

  (1)Washington
    (3)---> NewYork
    (2)---> Denver

  (2)Chicago
    (4)---> Denver
    (5)(prop)---> Washington

  (3)Denver
    (6)(meal)---> Washington

Here the node number and edge number are in parentheses, the names/labels after. The arrow is from the node it is under to the node at the end of the "--->". For example, the first three lines tell us that :
  node 0 is named NewYork, 
  and edge 0 (with no label) goes from node NewYork to node Chicago,
  and edge 1 (with label "prop") goes from node NewYork to node Washington

Implementation Notes

Note that we have asked to have each node/edge serial numbered, but have string labels/names as well. We said a node must have a string name, and an edge MAY have a string label. Node names are unique; edge labels do not have to be. This will require you to think about how nodes and edges will be designated and retrieved as you use the graph data structure.

Consider storing the vertex-names in a sorted array, or hashmap, or something similar; that way, translating from these names to the internal representation is more efficient. This hashmap would supplement the adjacency list structure that represents the basic nodes and arcs of the graph (nodes in a list, each node with a list of edges attached to it). If you need to get a single node, you can hash it in constant time rather than search a list of all nodes in linear time.

However, we do still have need to systematically access every node in (such as doing a print). So you will need some way to efficiently get all nodes one at a time in sequence. With a hashmap you can get an iterator over all the keys (node names), but the order will be arbitrary. So in designing consider if there might be reason to keep a node list of your own, where you could control the order if needed.