ITCS-6114\/8114: Algorithms and Data Structures
\nProject 1 \u2014 Shortest Paths in a Network
\nDue Date
\nThe due date is Tuesday, November 23, 2021 by 11:59:59 pm. See the syllabus for late policies. See below for submission guidelines.
\nIntroduction
\nConsider a data communication network that must route data packets (email, MP3 files, or video files, for example). Such a network consists of routers connected by physical cables or links. A router can act as a source, a destination, or a forwarder of data packets. We can model a network as a graph with each router corresponding to a vertex and the link or physical connection between two routers corresponding to a pair of directed edges between the vertices.
\nA network that follows the OSPF (Open Shortest Path First) protocol routes packets using Dijkstra\u2019s shortest path algorithm. The criteria used to compute the weight corresponding to a link can include the time taken for data transmission, reliability of the link, transmission cost, and available bandwidth. Typically each router has a complete representation of the network graph and associated information available to it.
\nFor the purposes of this project ( help with nursing paper writing from experts with MSN & DNP degrees), each link has associated with it the transmission time taken for data to get from the vertex at one end to the vertex at the other end. You will compute the best path using the criterion of minimizing the total time taken for data to reach the destination. The shortest time path minimizes the sum of the transmission times of the links along the path.
\nThe network topology can change dynamically based on the state of the links and the routers. For example, a link may go down when the corresponding cable is cut, and a vertex may go down when the corresponding router crashes. In addition to these transient changes, changes to a network occur when a link is added or removed.
\nExample
\nConsider a very simplified example of a network at UNCC, with vertices at Belk Gym, Woodward Hall, College of Education, Duke Hall, Grigg Hall, and College of Health and Human Services. See Figure 1 for an illustration. For this example, the shortest time (or fastest) path from Belk (Gym) to (College of) Education is: Belk\u2013Duke\u2013Education with a total transmission time of 0.9 milliseconds.<\/p>\n
Figure 1: An example network graph. Each link shown represents two directed edges. Shown next to each link are the associated transmission times of its two edges in milliseconds.
\nYour Job
\nYou have five tasks in this project ( help with nursing paper writing from experts with MSN & DNP degrees): building the initial graph, updating the graph to reflect changes, finding the shortest path between any two vertices in the graph based on its current state, printing the graph, and finding reachable sets of vertices. These are described in turn.
\nBuilding the Graph
\nYour program should run from the command-line:
\ngraph network.txt
\nwhere network.txt is a file that contains the initial state of the graph. (Other names besides network.txt may be used, so you cannot hard-code this.) The format of the file is quite simple. Each link representing two directed edges is listed on a line, and is specified by the names of its two vertices followed by the transmission time. Vertices are simply strings (vertex names with no spaces) and the transmission times are floating point numbers. For the above example, the file will look like:
\nBelk Grigg 1.2
\nBelk Health 0.5
\nDuke Belk 0.6
\nBelk Woodward 0.25
\nWoodward Grigg 1.1
\nGrigg Duke 1.6
\nHealth Woodward 0.7
\nHealth Education 0.45
\nWoodward Education 1.3
\nDuke Education 0.3
\nWoodward Duke 0.67
\nFor each input link, add two directed edges, one in each direction.
\nChanges to the Graph
\nInput about changes to the graph, requests for shortest paths, and requests to print the graph will come as input queries to be read from the standard input. Here are queries indicating changes to the graph.
\naddedge tailvertex headvertex transmit time \u2014 Add a single directed edge from tailvertex to headvertex. Here headvertex and tailvertex are the names of the vertices and transmit time is a float specifying the transmission time of the edge. If a vertex does not exist in the graph already, add it to the graph. If the edge is already in the graph, change its transmission time. Important note: This can enable two vertices to be connected by a directed edge in one direction and not the other, or enable the transmission times in the two directions to be different.
\ndeleteedge tailvertex headvertex \u2014 Delete the specified directed edge from the graph. Do not remove the vertices. If the edge does not exist, do nothing. Note: This may cause two vertices to be connected by a directed edge in one direction, but not the other.
\nedgedown tailvertex headvertex \u2014 Mark the directed edge as \u201cdown\u201d and therefore unavailable for use. The response to an edgedown (or edgeup) Question Assignment should mark only the specified directed edge as \u201cdown\u201d (or \u201cup\u201d). So its companion directed edge (the edge going in the other direction) should not be affected.
\nedgeup tailvertex headvertex \u2014 Mark the directed edge as \u201cup\u201d, and available for use. Its previous transmission time should be used.
\nvertexdown vertex \u2014 Mark the vertex as \u201cdown\u201d. None of its edges can be used. Marking a vertex as \u201cdown\u201d should not cause any of its incoming or outgoing edges to be marked as \u201cdown\u201d. So the graph can have \u201cup\u201d edges going to and leaving from a \u201cdown\u201d vertex. However a path through such a \u201cdown\u201d vertex cannot be used as a valid path.
\nvertexup vertex \u2014 Mark the vertex as \u201cup\u201d again.
\nFinding the Shortest Path
\nThe Question Assignment for finding the shortest path will look like path from_vertex to_vertex
\nwhere from_vertex and to_vertex are names of vertices. This should compute the shortest time path from from_vertex to to_vertex using Dijkstra\u2019s algorithm and based on the current state of the graph.
\nThe most difficult task is the implementation of Dijkstra\u2019s algorithm, and especially the priority queue (as a min binary heap).
\nThe output must be the vertices along the shortest path, followed by the total transmission time. For example, with our example graph and no changes to the state of the graph, the Question Assignment path Belk Education should yield as output
\nBelk Duke Education 0.9
\nPrint Graph
\nThe simple Question Assignment print
\nmust print the contents of the graph. Vertices must be printed in alphabetical order and the outward edge for each vertex must be printed in alphabetical order. For the example graph, the output should be
\nBelk
\nDuke 0.6
\nGrigg 1.2
\nHealth 0.5
\nWoodward 0.25
\nDuke
\nBelk 0.6
\nEducation 0.3
\nGrigg 1.6
\nWoodward 0.67
\nEducation
\nDuke 0.3
\nHealth 0.45
\nWoodward 1.3
\nGrigg
\nBelk 1.2
\nDuke 1.6
\nWoodward 1.1
\nHealth …
\nWoodward …
\nWhen a vertex is down, append the word DOWN after the vertex. When an edge is down, append the word DOWN after the edge.
\nReachable Vertices
\nSince the states of the vertices and edges may change with time, it is useful to know the set of vertices reachable from each vertex by valid paths. You must develop and implement an algorithm that identifies for each vertex, the set of all its reachable vertices. You should not use the shortest distance algorithm implemented above to obtain the set of reachable vertices. Important: Additionally, you must describe your algorithm and justify its running time, using \u201cO\u201d notation, in the comments for this algorithm in your submitted code.
\nThe Question Assignment reachable
\nmust print for each \u201cup\u201d vertex, all vertices that are reachable from it. So vertices that are \u201cdown\u201d or not reachable by \u201cup\u201d edges will not be printed. Vertices must be printed in alphabetical order, and the set of vertices reachable from each vertex must be printed in alphabetical order. For example, if only vertices Health and Grigg are reachable from vertex Belk, the output will look
\nlike
\nBelk
\nGrigg
\nHealth
\nDuke …
\nQuit
\nThe input Question Assignment quit should simply cause the program to exit without printing anything.
\nProject Hints
\nYou should create a Graph class, a Vertex class and an Edge class to hold the relevant vertex and weighted edge information. Use an adjacency list of edges in the vertex class.
\nThe implementation of Dijkstra\u2019s algorithm is perhaps the hardest part of the project ( help with nursing paper writing from experts with MSN & DNP degrees). You may like to first implement Dijkstra\u2019s algorithm using an array as the priority queue to maintain the vertex distances, and then implement the min binary heap to achieve the more efficient priority queue implementation.
\nRemember that the initial information about the network graph will come from a file specified as a command-line argument. The graph you create will be a directed graph with two edges, one in each direction, for each input link. The queries will come from the standard input and the output from your program should go to the standard output. Example input and output files will be posted.
\nGrading Criteria
\nThe total of 100 points for this project ( help with nursing paper writing from experts with MSN & DNP degrees) is broken up into:
\n20 points for proper construction of the graph and outputting a correct description.
\n35 points for efficiently finding shortest paths using Dijkstra\u2019s algorithm. You will lose 15 points if you do not use a binary heap to implement the priority queue.
\n15 points for updating the graph based on network changes.
\n15 points for printing all reachable vertex sets and analyzing the complexity of your algorithm.
\n15 points for compilation, structure, and documentation.
\nWithin these criteria, your grade will depend on program structure, efficiency, and correct execution.
\nThe structure of your code will be judged for quality of the comments, quality of the data structure design, and especially the logic of the implementation. The comments need not be extremely long: just explain clearly the purpose of each class and each function within each class.
\nSubmission Guidelines
\nYour submission must include all your source code and a brief report as a README file. Your submission should NOT include any IDE-specific project ( help with nursing paper writing from experts with MSN & DNP degrees) files, any compiled files, or any executables. Every file should have your name in a comment line at the top. Your README file should have a brief description of your program design, the breakdown of the files, which compiler you used, a summary of what you think works and fails in your program, and a short description of your data structure design.
\nYou will submit your project ( help with nursing paper writing from experts with MSN & DNP degrees) on Canvas. You should submit a single zip or tar file containing your source code files and README file. You can submit your project ( help with nursing paper writing from experts with MSN & DNP degrees) multiple times; only the most recent project ( help with nursing paper writing from experts with MSN & DNP degrees) submission will be graded. The most recent project ( help with nursing paper writing from experts with MSN & DNP degrees) submission will also be used to compute late days, if any.
\nFinal Warning
\nA project ( help with nursing paper writing from experts with MSN & DNP degrees) that does not follow the submission guidelines will receive a 10 point deduction. Proper submission is entirely your responsibility. Contact the TA if you have any doubts whatsoever about your submission. Do NOT submit your project ( help with nursing paper writing from experts with MSN & DNP degrees) via email. Be sure to keep copies of your files and do not change them after submitting. After grades are posted, you have exactly one week to resolve all problems. After that week is up, all grades are final.
\nPlease observe the academic integrity guidelines in the syllabus, and submit your own work.<\/p>\n
—<\/p>\n
Algorithms and Data Structures (ITCS-6114\/8114)
\nProject 1 \u2014 Shortest Paths in a Network
\nDue Date<\/p>\n
The due date is Tuesday, November 23, 2021 by 11:59:59 pm. See the syllabus for late policies. See below for submission guidelines.<\/p>\n
Introduction<\/p>\n
Consider a data communication network that must route data packets (email, MP3 files, or video files, for example). Such a network consists of routers connected by physical cables or links. A router can act as a source, a destination, or a forwarder of data packets. We can model a network as a graph with each router corresponding to a vertex and the link or physical connection between two routers corresponding to a pair of directed edges between the vertices.<\/p>\n
A network that follows the OSPF (Open Shortest Path<\/p>\n","protected":false},"excerpt":{"rendered":"
ITCS-6114\/8114: Algorithms and Data Structures Project 1 \u2014 Shortest Paths in a Network Due Date The due date is Tuesday, November 23, 2021 by 11:59:59\u2026<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8773,8771,8772,8770,8775,8776,7685,8774,8769],"tags":[1400,613,142,7594,1394,7598,7595,7593,7597,7599,7601,7590,7596,133,7655,7656,7591,7592],"class_list":["post-92006","post","type-post","status-publish","format-standard","hentry","category-all-assignment-help","category-assessment-help-online","category-assessment-help-online-in-australia","category-assessments-help","category-australia-assignment-help","category-instant-assignment-help","category-my-assignment-help","category-sample-assignment-help","category-thesis-help","tag-best-custom-essay-writing-services","tag-best-dissertation-writing-services-uk","tag-best-online-essay-writing-services","tag-cheap-custom-essay-writing-services","tag-custom-research-paper-writers","tag-custom-research-papers-writing-service","tag-essay-writer-websites","tag-essay-writing-service-quality-cheap","tag-free-research-paper-writing-service","tag-help-me-write-a-research-paper","tag-i-need-help-with-my-dissertation","tag-professional-dissertation-writing-service","tag-quick-essay-writing-service","tag-research-paper-writing-service-cheap","tag-service-writing-my-essay-write-custom","tag-someone-to-write-my-paper","tag-top-rated-dissertation-writing-services","tag-top-uk-dissertation-writing-services"],"_links":{"self":[{"href":"https:\/\/www.studyproessays.com\/help\/wp-json\/wp\/v2\/posts\/92006","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.studyproessays.com\/help\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.studyproessays.com\/help\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.studyproessays.com\/help\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.studyproessays.com\/help\/wp-json\/wp\/v2\/comments?post=92006"}],"version-history":[{"count":0,"href":"https:\/\/www.studyproessays.com\/help\/wp-json\/wp\/v2\/posts\/92006\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.studyproessays.com\/help\/wp-json\/wp\/v2\/media?parent=92006"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.studyproessays.com\/help\/wp-json\/wp\/v2\/categories?post=92006"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.studyproessays.com\/help\/wp-json\/wp\/v2\/tags?post=92006"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}