In this assignment, you will solve several real world network planning problems by mapping them to well-known graph algorithms. These graph algorithms are 1) finding the shortest path and 2) constructing a minimum spanning tree. Dijkstra's shortest path algorithm in one of many algorithms and is the recommended one to use. Prim's or Kruskal's minimum spanning tree algorithms are the suggested MST solutions to use. If you prefer a different algorithm, however, you are welcome to use it -- so long as it solves the same problem.
Using the network planning problem gives you the opportunity to implement new data structures, such as union-find, and apply previously used data structures, such as heaps/priority queues, on real-world problems. Additionally, this assignment comes with more freedom than previous ones, meaning you can choose whichever data-structures you feel appropriate for solving the problem presented.
Additional links to supplement the textbook.
November 24November 26 @ 11:00 PM
This assignment will not have a checkpoint turn-in unlike previous assignments.
All your files must be submitted with a working Makefile that generates a binary executable from your source called netplan
by typing make at the command-line.
You must follow these steps to acquire the starter code and prepare for the assignment. Do not directly copy files from any directory that you find on ieng6, as may have been the procedure in previous offerings of this course!
Instead, see Using Gitlab for the proper steps.
After having followed the instructions for cloning the Git repository, you will see the following files:
| Vertex.hpp Vertex.cpp |
Defines a single vertex in the graph. |
| Edge.hpp Edge.cpp |
Defines a single edge in the graph including the cost and speed weights. |
| UndirectedGraph.hpp UndirectedGraph.cpp |
Defines an undirected graph made up of a set of vertices and edges. |
| netplan.cpp | Handle parsing the input, and solving the set of problems. |
| Makefile | GNU Make input file for automating compilation. |
| refnetplan | Reference binary for verifying your program's correctness. |
| generator.py | Python program for generating random graphs to assist with unit testing. |
You will write a program netplan that will be invoked from the command-line as follows:
./netplan infile
where infile will contain a set of line-delimited data about a network connection.
Each line will contain four columns: two strings followed by two integers, all separated by whitespace. The strings represent a company or organization; the first integer is the cost (in millions of dollars) of laying a fiber link between the two companies, thereby connecting them; the second integer is the time (in milliseconds) needed to send a packet between the two companies over the fiber link.
Here is a sample input file:
Network Point A |
Network Point B |
Cost |
Latency |
|---|---|---|---|
ibm.com |
yahoo.com |
20 |
33 |
yahoo.com |
ucsd.edu |
19 |
40 |
ucsd.edu |
ibm.com |
10 |
17 |
yahoo.com |
fsf.org |
5 |
10 |
NOTE: The header row will not be present in the input file, it is displayed here to assist with the explanation.
Your program will read the input file, creating a graph of the data, and use the various algorithms discussed to calculate six pieces of information, which will then be output (to stdout), one answer per line, in the form of an integer.
The information to be output is the following:
For example, with the above input file, a correct program will output:
54 |
34 |
20 |
386 |
482 |
96 |
This indicates that cost of the all links network is $54 million; the cost of the cheapest network is $34 million; the cheapest network saves $20 million ($54 - $34); the total transit time if all network links were used would be the sum of sending a packet from one location to every other location, totaling 386 milliseconds; the total transit time for the cheapest network would be 482 milliseconds; and that the cheaper network would be 96 milliseconds slower than the all-links network.
Your output will be tested automatically by a script, so make sure you do not output anything but those numbers, each on its own line.
NOTE: The input files used when testing/grading your project will contain only valid input. You can safely assume each network connection will be a single line; that all lines will contain all four pieces of information; and that all company names will not contain whitespace.
Note: For this assignment, you do not need to use the starter files. You are free to create your own classes and come up with your own design. Whichever decision you make, you should not skip over this section. If you plan to use the starter code, do not implement any of the methods unless you have a good understanding of how they fit into your overall design.
Decompose the problem! An object-oriented design suggests that you should define the classes UndirectedGraph, Vertex, and Edge. Think about what attributes (member variables) and behavior (member methods) the class should support. Once this step is complete, proceed to write the .hpp header file defining the interface of the class. Then implement the definitions for all methods inside a separate .cpp file. Remember to wrap your .hpp files with header guards. Simple one-line getter/setter type methods can be defined inside the .hpp file if you prefer.
Your executable program will then use an instance of your Graph class to do its work. A procedural decomposition of the program might have these parts:
You are strongly encouraged to test your data structures BEFORE proceeding to solve the final part of the assignment. Individual test cases should be written to ensure each public class method works as intended. Be especially mindful of edge/corner cases.
If you are working with a partner, one suggestion is for one person to work on the tests and the other to implement the data structure.
A strategy for this is to first define the class, stubbing out all the methods. Stubbing the methods means do
not implement them yet. If a method returns void, then create the method with an empty body. If a
method needs to return an int, pointer, or something else, place only the appropriate
return statement in the method body. For example, return -1, return nullptr, or
whatever is appropriate. This allows your code to be compiled.
Having done this, the person working on tests can at least call your methods and compile the tests against them. At this point, all tests should fail since nothing is implemented yet. As you complete various methods in the class, the tester can then test these modules one at at time. As more functionality is introduced, test everything again.
This should also help you understand how each method needs to work.
For generating sample input to help with testing, a python program has been provided as part of the starter code, generator.py. This program generates random networks with a given number of vertices and edges. However, you will still need to construct some careful graphs to test edge cases. For example, an empty graph, a complete graph, graph with all edge weights equal, etc.
When you have completed the assignment, you must submit it. Accomplishing this requires pushing your changes to GitLab by following these steps:
git status to see what files have been changed.git add [files] to stage certain files for a commit, use
git add . to add all files in the working directory to the
commit (hopefully you will not be doing this at this late stage—all files should already be in your
repository!)
git commit -m "FINAL
SUBMISSION" to commit the changes to your repository and indicate that you are done and
this is your final submission.
git push origin
master Don't forget this push! You must do this to get credit.
Some points to keep in mind:
There are 25 possible points on the assignment. If your solution files do not compile and link error-free, you
will receive 0 points for this assignment. We will compile the files you turn in with the command make netplan.
To get credit for your program, it should compile, and it should spend less than 10 seconds (on ieng6) on any 1000-edge graph (meaning up to 1001 vertices) with a unique minimum-cost spanning tree. Recall that a graph has a unique minimum-cost spanning tree if each edge has a different weight. To get full credit, style and comments count.
Point Distribution: