In this first part you will design and implement in Java a basic graph data structure.
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:
q | Quit command. End execution. |
an | Add node command. Serial number the node so that it has a unique id. Prompt the user for other information needed for a node (name, etc.). Let's require the name to be unique as well (so we can hash the string and get one node back). Return true if it was added successfully; return false if it is already in the graph. |
ae | Add edge command. Serial number the edge so that it has a unique id. Prompt the user for other information about a edge (weight, label, etc.). A user should not be required to label an edge but should be given that option (meaning when asked for a label, giving a null response is allowed). We will not require edges to have unique labels, but we do need to check that an edge from the indicated source node to the destination node is not already in the graph. Return true if the edge is added; return false if it is not added (for whatever reasons... see below). |
dn | Delete node command. Prompt the user for the node name and remove it from the structure(s) of the graph. Removing a node will require also removing the edges into and out of that node. Return true if the node was found and successfully removed; return false if the node was not in the graph. |
de | Delete edge command. Prompt the user for the edge id and remove it from the structure(s) of the graph. Since we are assuming there is only one edge from ni to nj, we can simply ask for the names of the two nodes (remember direction matters) to identify the edge uniquely. Removing an edge will not require removing any nodes (remember that a set of nodes with no edges is a valid graph... not connected, but a graph nonetheless). Return true is the edge is found and removed; return false otherwise. |
s | Size command. Print how many nodes and how many edges are in the graph (separate information, not a sum of the two). You will want the graph to provide each of these two values separately; your driver will request both and format the output appropriately. |
pg | Print graph command. Produce a readable form of the graph structure and contents. See notes on print format below. |
pn | Print node command. Just like the print graph command except it is done for a single node. You will prompt the user for a node name. See notes on print format below. |
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.
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)---> WashingtonHere 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
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.