Objectives

• Get familiar with ADT graph and its concrete implementation
• Select various graph algorithms to solve problems

This assignment is worth 5% of your final grade. Your assignment will be marked based on the correctness, efficiency (data structures, algorithms and memory usage), readability (including documentation) and maintainability (modular design) of your program.

Problem Description

An organization built and maintains a network of communication infrastructure. The infrastructure consists a set of communication servers, distributed in various locations around the world, and a set of bi-directional links directly connecting two servers.

Each server is assigned a unique name and is located in a particular location. Because the location information of the servers is irrelevant to the problems we need to solve, we'll ignore the location information and other features of the servers for this assignment's purposes.

Each direct link connecting two servers together is bidirectional, has a unit cost for a standard communication volume, and a capacity of how much communication volume it can handle in a unit time.

Then the organization conducted a business analysis to identify a list of communication demands. Each demand identifies the communication volume needed between two servers.

Here is a sample file that shows an example of the aforementioned infrastructure data and business analysis result data.

Your Tasks:

You are asked to develop a C++ program that takes the name of a file containing the infrastructure data and the communication demands identified by the business analysis as its command line argument, then conducts a technology analysis based on the information provided in the file.

More specifically, your technology analysis program should conduct the following two tasks based on the provided infrastructure data and business analysis result:

1. Identify any of the communication demands that can't be met by the current infrastructure due to lack of connected routes between the two servers listed in the demand.
2. Excluding all the unrealizable demands identified in the previous task, if all the rest communication demands must be met with the lowest cost possible, can the current infrastructure handle them? If not, identify any direct link whose volume capacity must be expanded and calculate how much its volume capacity must be expanded, with the assumption that the unit cost of the link would remain the same after its capacity expansion.

Write your analysis result to a text file named techAnalysisResult.txt. Here is a sample tech analysis result file.

The input file must follow the format of the sample input file. However, your output file doesn't necessarily need to follow the format of the sample output file, as long as your report is easy to read and interprets without any ambiguity.

Design and Documentation

With your solution, include a readme file (similar to the one required in programming assignment 1) that clearly explains your main design decisions, such as why you chose your concrete data structure to implement the graph, and which algorithm(s) you chose to use in your program and why.

Modularize your code properly. Your source code file(s) should have the usual proper header documentation/comments and necessary in-line comments.

Create a Makefile to automate the building of your program. Upon typing make, an executable file named pex3 should be generated.

Submission

To submit your solution, change working directory to where your solution is located and run the following command:

~liuh/bin/submit 260 Pex3 .

The submit script currently accept Makefile, README, typescript, *.md, *.cpp, *.h, src/*.cpp and include/*.h files.

If this command is successfully executed, it should show you a list of the files just got submitted to the instructor's directory. If you submit your assignment more than once, all but the last one will be discarded. Take advantage of this feature, submit early and submit often. Your assignment must be submitted before the due date and time.

You can check what you have submitted for this assignment by running the following command:

~liuh/bin/checksubmit 260 Pex3