The Internet backbone consists of trunk lines between major cities. Use of each link incurs a cost per gigabit (Gb) that depends on a variety of factors that we needn't get into here. The cost to send a message from one point to another is the sum of the link costs on the path.
We can represent the network as a directed graph (since network costs could be asymmetric) with edges weighted by the link cost.
The cost table is a text file containing one entry per line. Each
entry consists of 3 fields separated by tab characters ('\t').
The first two fields are 3-letter codes identifying the
from
and
to
cities (which just happen to be FAA codes for the nearby
airports), and the third field is non-negative numeric cost
(int).
Write a program called
network_cost
that will read a cost table from
cin
and take two command-line arguments for the start and end cities.
Compute the minimum-cost path and print it to
cout in proper order in the same format as the input
file (remember, your output will be
diffed
with a reference file).
You may use the standard libary templates
list and
vector.
You may use
map
only
while building the graph.
Additionally, take an optional pair of arguments
"-o"
and
filename. If the flag is provided,
as you search the graph, dump the graph frame-by-frame to
.dot
files named
filename-nnnn.dot
where
nnnn
is the nth frame. The final frame should mark the shortest path
in red.
Use the graph dump routines in
graph-draw.h
and
graph-draw.cc.
Do not modify these files
(except for any needed bug fixes). Write your own code for the
graph search algorithm. Yes, your program will have two different
internal representations of the graph. Deal with it.
The .dot files are to be processed by the dot program which is
part of the
Graphviz
package. You can download Graphviz from
here.
Write or borrow a shell script, named
Run
to compile and run the program and to generate .gif files from the
.dot files.
This file is a required part of your submission, but need not be
your own work. Your instructor's script will be posted shortly.
For example, the following input:
Given start and end cities bli and sea should produce output:
bli bfi 6
bli sea 16
bli pdx 4
bli geg 16
bfi pdx 6
bfi geg 8
sea pdx 6
sea geg 4
sea ykm 8
pdx geg 2
geg ykm 4
ykm bli 8
ykm bfi 10
ykm sea 4
bli pdx 4
pdx geg 2
geg ykm 4
ykm sea 4
Finally, write a program called
total_message_cost
that will take the output file as input
and compute the net cost. For example, the previous output should
produce the final output:
This program
(
bli sea 14
total_message_cost)
may be written in C++ or a scripting language (Bash,
Perl, Python). No Java, please.
Submit a zip file containing all source code,
Run
script and test cases to
the usual place
so your marker can run the program in a stand-alone environment
(you may assume your marker has Graphviz installed).