Homework

Homework Questions? Ask a Tutor for Answers ASAP

Connect one-on-one with {0} who will answer your question

Customer Question

**Program 3: Dynamic Minimum Spanning Trees**

Due Date: Part 2 November 23, 2014 at noon

**Overview:**

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.

** **

**Graph Input:**

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)

V128.8.10.14 (vertex identifier)

V128.8.128.423

V128.8.10.268

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)

V128.8.10.14 V128.8.10.268 43.56 (endpoints and edge weight)

V128.8.10.268 V128.8.128.423 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 (V128.8.10.14 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.

** **

**Update Directives:**

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.

** **

**Implementation Requirements:**

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.

** **

**Implementation Suggestions:**

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.

** **

**MST Updates:**

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.

** **

**Output Format: **

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.

Directive-----------------> print-mst

i

. d

. . a

. . . b

. . . . e

. . . . f

. . . c

. . . . g

. . . . . j

. . . . . k

. . . . . l

. . h

. m

** **

** **

**Input:**

You are to ask the user if the directives will be entered from the keyboard or from a file.

**Test Cases:**

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

Show More

Show Less

Was this answer helpful?

Describe your issueThe assistant will guide you

Chat 1:1 with a tutorLicensed Experts are available 24/7

100% satisfaction guaranteeGet all the answers you need

Related Homework Questions

Answer the following questions about the graph given below:

Answer the following questions about the graph given below:Algorithms Forum: Algorithms | Graph and its representations1.How many vertices exist in this graph? 2.How many edges exist in this graph? 3.… read more

ICS 340 Programming Project, Deliverable A Specification:

ICS 340 Programming Project, Deliverable A Specification: Start with the given Java program “prog340”, which lets you select a file to read from your computer, reads the file, and interprets that file… read more

I need help with my data structures assignment. Java. I need

Second opinion] I need help with my data structures assignment… read more

Longest common subsequence algorithm The longest common

Longest common subsequence algorithm The longest common subsequence (LCS) is often used in the fields of DNA sequence comparison or version control. Please make the LCS algorithm according to the slid… read more

Using JavaScript: Ford-Fulkerson - Augmenting Paths: When we

Using JavaScript:Ford-Fulkerson - Augmenting Paths: When we generally talk about the Ford-Fulkerson algorithm to find the maximum flow through a graph, It would be interesting to "find an augmenting p… read more

● Graph.java that implements a directed graph using an

● Graph.java that implements a directed graph using an adjacency matrix. ● GraphApplicaiton.java with a main method that (i) creates a graph, (ii) displays its details, and, (iii) for every vertex, pr… read more

I'm having some trouble understanding pseudocode for my

I'm having some trouble understanding pseudocode for my assignment … read more

I have a huge project for C++ Data Structures & the last

I have a huge project for C++ Data Structures & the last thing I need to do is create a simple graph. Can you help me program this functionality? … read more

I have a GUI and an algorithm that finds all possible paths

I have a GUI and an algorithm that finds all possible paths from source to destination in an unweighted directed graph. I'm having trouble combining both. This is a JAVA assignment … read more

New concepts tested by this program Implement Graph Interface Use

New concepts tested by this program Implement Graph Interface Use Graph to maintain a network of Actors Shortest Path Algorithm implementation A Graph is a set of Vertices and a Set of Edges. You will… read more

TO RAJ:1. A deque (pronounced deck) is an ordered set of

TO RAJ: 1. A deque (pronounced deck) is an ordered set of items from which items may be deleted at either end and into which items may be inserted at either end. Call the two ends left and right. This… read more

Objective Breadth First Search C++ Due: April 17 before

Objective Breadth First Search C++ Due: April 17 before 11:55pm on myCourses (this due date is a change from the initial class schedule) The objective of this programming assignment is use breadth fir… read more

Task Background: Graphs and Trees are useful in visualizing

Task Background: Graphs and Trees are useful in visualizing data and the relations within and between data sets. Conversely, it is also important to be able to represent graphs as databases or arrays,… read more

Directed Graph with String Vertices and Edges Perform DFSBFS

The directed and labelled graph above, which is also known as a Semantic Network, provides an insight into the world of some species (vertices) and their properties (labelled edges). This structure sh… read more

Task Background: Graphs and Trees are useful in visualizing

Task Background: Graphs and Trees are useful in visualizing data and the relations within and between data sets. Conversely, it is also important to be able to represent graphs as databases or arrays,… read more

Discrete math Part I: Adjacency Matrix and Shortest Path Construct

Discrete math Part I: Adjacency Matrix and Shortest Path Construct a graph based on the adjacency matrix that appears below. Label all nodes with indices consistent with the placement of numbers withi… read more

5. Find all minimum spanning trees (MST) in the following

5. Find all minimum spanning trees (MST) in the following network. Clearly indicate your staring node, chosen spanning link at each step, the resulting trees and the value of the objective function. N… read more

Disclaimer: Information in questions, answers, and other posts on this site ("Posts") comes from individual users, not JustAnswer; JustAnswer is not responsible for Posts. Posts are for general information, are not intended to substitute for informed professional advice (medical, legal, veterinary, financial, etc.), or to establish a professional-client relationship. The site and services are provided "as is" with no warranty or representations by JustAnswer regarding the qualifications of Experts. To see what credentials have been verified by a third-party service, please click on the "Verified" symbol in some Experts' profiles. JustAnswer is not intended or designed for EMERGENCY questions which should be directed immediately by telephone or in-person to qualified professionals.

Ask-a-doc Web sites: If you've got a quick question, you can try to get an answer from sites that say they have various specialists on hand to give quick answers... Justanswer.com.

JustAnswer.com...has seen a spike since October in legal questions from readers about layoffs, unemployment and severance.

Web sites like justanswer.com/legal

...leave nothing to chance.

...leave nothing to chance.

Traffic on JustAnswer rose 14 percent...and had nearly 400,000 page views in 30 days...inquiries related to stress, high blood pressure, drinking and heart pain jumped 33 percent.

Tory Johnson, GMA Workplace Contributor, discusses work-from-home jobs, such as JustAnswer in which verified Experts answer people’s questions.

I will tell you that...the things you have to go through to be an Expert are quite rigorous.

Wonderful service, prompt, efficient, and accurate. Couldn't have asked for more. I cannot thank you enough for your help.

Freshfield, Liverpool, UK

This expert is wonderful. They truly know what they are talking about, and they actually care about you. They really helped put my nerves at ease. Thank you so much!!!!

Los Angeles, CA

Thank you for all your help. It is nice to know that this service is here for people like myself, who need answers fast and are not sure who to consult.

Hesperia, CA

I couldn't be more satisfied! This is the site I will always come to when I need a second opinion.

Kernersville, NC

Just let me say that this encounter has been entirely professional and most helpful. I liked that I could ask additional questions and get answered in a very short turn around.

Woodstock, NY

Thank you so much for taking your time and knowledge to support my concerns. Not only did you answer my questions, you even took it a step further with replying with more pertinent information I needed to know.

Elkton, Maryland

He answered my question promptly and gave me accurate, detailed information. If all of your experts are half as good, you have a great thing going here.

Dallas, TX

< Previous | Next >

Scott

MIT Graduate

5,811 satisfied customers

MIT Graduate (Math, Programming, Science, and Music)

LogicPro

Engineer

23,494 satisfied customers

Expert in Python,Java C++ C C# VB Javascript Design SQL HTML

Manal Elkhoshkhany

Tutor

4,941 satisfied customers

More than 5000 online tutoring sessions.

Linda_us

Finance, Accounts & Homework Tutor

3,138 satisfied customers

Post Graduate Diploma in Management (MBA)

Chris M.

M.S.W. Social Work

2,852 satisfied customers

Master's Degree, strong math and writing skills, experience in one-on-one tutoring (college English)

F. Naz

Chartered Accountant

2,280 satisfied customers

Experience with chartered accountancy

Jaun

Teacher

2,100 satisfied customers

Masters in Business Administration.

< Previous | Next >

Disclaimer: Information in questions, answers, and other posts on this site ("Posts") comes from individual users, not JustAnswer; JustAnswer is not responsible for Posts. Posts are for general information, are not intended to substitute for informed professional advice (medical, legal, veterinary, financial, etc.), or to establish a professional-client relationship. The site and services are provided "as is" with no warranty or representations by JustAnswer regarding the qualifications of Experts. To see what credentials have been verified by a third-party service, please click on the "Verified" symbol in some Experts' profiles. JustAnswer is not intended or designed for EMERGENCY questions which should be directed immediately by telephone or in-person to qualified professionals.