In this assignment, you will solve several real world network planning problems by mapping them to well-known graph algorithms. These graph algorithms are
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.
Checkpoint Submission: Tuesday May 5 @ 10:00 PM
Final Submission: Thursday May 14 @ 10:00 PM
For both the checkpoint and final submissions, 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 can develop your code anywhere but you must test it on the ieng6 servers. If you plan to develop your code on ieng6 DO NOT log into ieng6.ucsd.edu instead log into one of ieng6's dedicated servers. 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 to setup your ssh key and
cloning your git repo over SSH.
Also, make sure your repository is created in the cse100-sp15 namespace. If not, our grading scripts will not be able to access your code and you will receive a zero on the assignment.
After having followed the instructions for cloning the Git repositoryover SSH, you will see the following files:
| Vertex.hpp Vertex.cpp |
Defines a single vertex in the graph. |
| Edge.hpp Edge.cpp |
Defines a single weighted edge in the graph in terms of cost and speed. |
| 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. Use formatted read from file because there maybe whitespaces before the first column as well. 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.
Requirement for final submission
For the final submission, 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.
Requirement for the checkpoint submission
For the checkpoint submission, you should complete the part of the assignment that builds the graph representation from the input file and outputs the first line of analysis—the cost of building all possible links. Submit your files before the deadline with the commit message "CHECKPOINT SUBMISSION". We will grade these submissions for correctness.
Note that this submmission represents the BARE MINIMUM you should have completed by the checkpoint deadline. You should strive to be well beyond this point before the checkpoint deadline (i.e., try to submit your checkpoint code early). If you're done early with the part that you need to submit before the checkpoint deadline, you should move on and try to complete the rest of the project as soon as possible.
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.
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:
cse100-sp15 If you do not create your repository in the right namespace you will lose your checkpoint grade
git status to see what files have been changed.git add [files] to stage certain files for a commit
git commit -m "CHECKPOINT SUBMISSION" to indicate that this is your checkpoint submission.
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 both for the checkpoint and sinal submissions! 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. Your program should also be able to handle (not crash)for graphs with 1000 vertices and 100000 edges, although there are no run time requirements that you need to meet for these larger graphs. To get full credit, style and comments count.
Point Distribution: