Program 3: Dynamic Minimum Spanning Trees
Due Date: Part 2 November 23, 2014 at noon
One of the challenges of real data structure design is that data structures do not operate
in isolation, but rather many data structures interact with each other to produce a combined
objective. This project will explore this by having you to implement a number of different data
structures (graphs, multiway trees, and heaps) to achieve the objective of maintaining a minimum spanning tree (MST).
The goal of this project is to input an undirected graph with weighted edges, compute an initial
MST for the graph. Then as changes occur in the graph structure, the MST is to be updated.
These changes include the insertion and deletion of vertices, insertion and deletion of edges, and changing the weights of edges.
All input will occur from the standard input and output to the standard output – both file and keyboard. The input begins with a description of the graph. This description starts with the number of vertices, followed by a list of the vertices, one per line. Each vertex has an associated string identifier. You may assume that each string identifier consists of at most 20 characters.
For example, here is the input file layout for three vertices.
3 (number of vertices)
V126.96.36.199 (vertex identifier)
To specify the edges, the number of edges is given followed by a list of edges, each consisting of the identifiers of the endpoints and the edge weight (float). You may assume that all weights are positive.
For example, here is the input file layout for two edges.
2 (number of edges)
V188.8.131.52 V184.108.40.2068 43.56 (endpoints and edge weight)
V220.127.116.118 V18.104.22.1683 170.36
You may assume that the first part of the input follows these specifications (that is, you do not
have to check for input format errors), but you should verify that the vertex identifiers are unique
(a duplicate vertex should be ignored), and that the edges are distinct (no multiple edges) and the endpoints are valid vertices. If input line has invalid data display the invalid input line and the appropriate error message.
MST by Prim's Algorithm:
The initial graph has edges connecting all nodes. After inputting the graph, compute its MST using Prim's algorithm.
For consistency, you should use the first vertex input (V22.214.171.124 in this case) as the starting vertex for the algorithm. Output the sequence of edges that have been added to the tree and their associated weights.
The rest of the input consists of a sequence of directives, each indicating an operation to be
performed on the graph. For those directives that alter the graph, you should incrementally update your MST after each operation. Note that in the course of performing these operations, the graph may become disconnected. In this case you will need to maintain a separate MST for each connected portion of the graph.
Print the graph: Print the entire graph.
Print the MST: Print the contents of the current MST(s). Print the MST according to a preorder traversal of the graph given the current root(s).
Path: Given two vertex identifiers, compute and print the weight and path between them in the MST using Dijkstra’s algorithm. If the vertices are not in the same tree, then print a message indicating this.
Insert vertex: Insert a vertex (with no edges) in the graph given its identifier.
Insert edge: Insert an edge between two existing vertices into the graph
Decrease weight: Decrease the weight on an existing edge in the graph by the given amount.
Delete vertex: Delete the given vertex from the graph and all its incident edges.
Delete edge: Delete the given edge from the graph.
Increase weight: Increase the weight on an existing edge by the given amount.
Here is a summary of the update directives:
Print-graph Print the graph
print-mst Print the MST(s)
path u v Print the weight and path from u to v in the MST
insert-vertex u Insert vertex u in the graph
insert-edge u v w Insert edge (u,v) with weight w in the graph
decrease-weight u v w Decrease the weight of edge (u,v) by w units
delete-vertex u Delete vertex u from the graph
delete-edge u v Delete edge (u,v) from the graph
increase-weight u v w Increase the weight of edge (u,v) by w units
quit This is the last directive
You may assume that the input will adhere to these conventions. However if any operation is illegal (attempting to insert a vertex that already exists or deleting an edge that does not exist), the operation should be ignored and an error message should be printed.
After each update operation, print a message indicating what operation was performed, and which vertex or edges were added to or deleted from the MST.
You are required to implement at least three separate data structures for the assignment: (1) an undirected weighted graph, (2) a multiway tree, and (3) a binary heap. The undirected graph must be implemented using an adjacency matrix or adjacency list, and edges must have cross links between. The MST is to be stored in the multiway tree, using the firstChild and nextSibling representation. It will also be necessary to have a parent pointer for each node for path finding operations. The binary heap is used in Prim's algorithm.
The update operations must be performed incrementally, by completely rebuilding the MST from scratch after each operation using Prim's algorithm.
I would suggest that you begin by implementing just build graph, print graph, Prim's algorithm and printing the MST. Then go about adding the other operations. This way you can get partial credit if the other operations are not working. Implement the update operations one by one, so that if you run out of time, at least you will have a partial subset that is supported.
You are allowed to use simple, linear data structures from the Java or C++ libraries (e.g. strings, linked-lists, vectors, stacks, queues). You are not allowed to use anything more sophisticated though (no trees, dictionaries, priority queues, etc.). The only exception is you may use any data structure you like for mapping vertex identifiers to actual vertex objects, as mentioned in the previous paragraph.
This project involves the integration of a number of different data structures. The easy but ugly way to do this would be to make one huge class in which you store all the information for each vertex (adjacency matrix or adjacency list, multiway tree, information for Prim's algorithm, etc). However, this is not at all modular. In C++ this could be handled cleanly by multiple inheritance, but Java does not support multiple inheritance. For full credit, you should modularize the major project components.
The graph can be represented by a straightforward implementation of the adjacency matrix or adjacency list along with cross links between the edges. There is a maximum of 100 vertices. Your data structure should be capable of handling any number of vertices in that range in an efficient manner.
The graph/MST will change to merge trees (when edges are added), split trees (when edges are deleted), determine whether two vertices are in the same tree, compute the path and weight between two vertices in the tree, determine whether a given graph edge is in the tree, etc. The MST may need to be cross referenced with the graph, so that given an edge of the graph the corresponding edge in the tree can be found (if it is in the tree) and given an edge in the tree the corresponding edge in the graph can be found.
Whenever the graph is updated the MST is rebuilt.
Major Data Structures:
The main data structures consist of the graph, which is represented using an adjacency matrix or adjacency list representation and a multiway tree representation of the MST. The graph data structure will likely consist of at least two types of nodes: vertices and edges. Each vertex node contains information such as the vertex identifier and a pointer to the adjacency matrix or adjacency list. Each edge node contains information about each edge, including the neighboring vertex, the edge weight, and the cross link to the twin edge.
Each MST is a multiway tree. Each node of this data structure contains a reference to the associated vertex in the graph. In addition the node might contain pointers to the first child, next sibling, previous sibling, and parent in the multiway tree. Note that there may be many MST's, one for each connected component, and the associated data structure should allow for this possibility.
For each directive output the directive, for the path and print-mst directives print the associated output, and print any error message, if needed.
Each MST should be printed in preorder.
Start each line with a string “. . . " to indicate depth. For consistency of output, the children of each node should be listed in increasing order by the string identifier.
For example, for a tree the operation “print-mst" could produce the output shown below by applying a preorder traversal of the tree.
. . a
. . . b
. . . . e
. . . . f
. . . c
. . . . g
. . . . . j
. . . . . k
. . . . . l
. . h
You are to ask the user if the directives will be entered from the keyboard or from a file.
1) Check for duplicate vertices and edges. Display a message if any. Use the the first one that was given and ignore the duplicate.
2) Check whether the number of edges and vertices equals the number indicated in the first line.
3)Check if the weight of an edge is greater than zero. If zero or less. Display a message that the edge doesn't exist