Computer Science 431

Algorithms

Spring 2015, The College of Saint Rose

We are back to the graph highway data for the programming portion of this problem set.

You may work alone or in groups of size 2 or 3 on this assignment. Only one submission per group is needed.

Programming Tasks

You previously developed a program to construct a
graph data structure based on the contents of a data file that
describes the highway segments in a road system (a "`.gra`
file").

Mapping Traversals

Your first task is to add commands and code to implement those
commands to your `Mapping` program to create output files that can
be used to view your graph traversal results.

My executable on `mogul.strose.edu` implements these as the
`MapDepthFirst` (`mdft`) and `MapBreadthFirst` (`mbft`)
commands.

You will perform the same breadth-first and depth-first traversals,
but instead of printing to the screen, you will write a file in
"`.pth`" format. This file format consists of a label (used in
some cases for a route name, but here will represent a traversal
order), a waypoint name, and the waypoint's coordinates.

For example, the file contents when my program computes a
breadth-first traversal on the `dc-all.gra` graph, using
`I-395@2`

as a starting point:

BFT0 I-395@2 38.879107 -77.033601 BFT1 I-395@1&US1@I-395 38.879249 -77.036197 BFT2 I-395@3 38.882314 -77.027882 BFT3 I-395/US1@VA/DC 38.873929 -77.043343 BFT4 US1@MaiAve 38.88365 -77.032099 BFT5 I-395@4 38.882402 -77.024009 BFT6 US1_S/US50_W 38.891968 -77.031627 BFT7 I-395@5 38.882515 -77.019176 BFT8 I-66/US50 38.893471 -77.053385 BFT9 US1/US50@ConAve 38.891968 -77.021542 BFT10 I-395@7 38.882815 -77.01254 BFT11 I-66/US50@VA/DC 38.891834 -77.06479 BFT12 I-66@EStExpy 38.895909 -77.053256 BFT13 US1@US50_E&US50@US1_N&US1AltWas@US1_S 38.903458 -77.019525 BFT14 I-395@8 38.885496 -77.01269 BFT15 I-66@US29 38.902489 -77.055831 BFT16 US1@RhoIslAve_W 38.913142 -77.019997 BFT17 US50/US1AltWas@I-395 38.90486 -77.015705 BFT18 I-395@9 38.894757 -77.014182 BFT19 US1@CapSt 38.916882 -77.009182 BFT20 US50/US1AltWas@BreRd 38.913008 -76.992016 BFT21 I-395@10 38.897813 -77.014187 BFT22 US1@MonAve 38.924661 -76.985664 BFT23 US50@US1Alt_N&US1AltWas@US50_E 38.917249 -76.972146 BFT24 I-395@US50 38.90491 -77.016081 BFT25 US1@DC/MD 38.935078 -76.963005 BFT26 US50@SouDakAve 38.918184 -76.954594 BFT27 US1AltWas@DC/MD 38.930637 -76.957253 BFT28 US50@DC/MD 38.917917 -76.941805

These files should be given a `.pth` extension. Once such a file
is created, it can be visualized by directing a browser at the Highway
Data Explorer (HX) at
`/chm/viewer/`
and uploading the `.pth` file in the file selection box at the top
of the page.

These two new commands are worth 10 points total.

Finding The "Best Of"

For this task, you are to add a capability to your program to be able
to find and report the *n* longest or shortest edges in the graph.

For example, with the `canyt.gra` graph, the 10 shortest edges:

YT6@MacBoatLau to YT6@+X646670 via YT6 length 0.0000 YT1@MorLakeRS to YT1@BC/YT via YT1 length 0.0936 YT1@BeaCrkAir to YT1@CanCus via YT1 length 0.1077 YT2@DukeSt to YT2@GeoBlaFry via YT2 length 0.1979 YT4_S/YT6_S to YT4@OldCanRd&YT6@OldCanRd_S via YT4,YT6 length 0.2299 YT6@+x822 to YT6@+x116 via YT6 length 0.2522 YT6@+X297007 to YT6@+X720169 via YT6 length 0.2704 YT4@+x88 to YT4@+x87 via YT4 length 0.2739 YT2@+X456835 to YT2@CliAgaRd via YT2 length 0.3073 YT6@+X401385 to YT6@+x771 via YT6 length 0.3446

and the 10 longest edges:

YT1@+X372730 to YT1@+X931620 via YT1 length 10.3368 YT1@+X687758 to YT1@+X612218 via YT1 length 9.8789 YT3@+X260467 to YT3@+x898989 via YT3 length 9.0087 YT2@+X558217 to YT2@GraRd via YT2 length 8.2056 YT1@+X336247 to YT1@+X858279 via YT1 length 7.4635 YT4@+x48 to YT4@+X800213 via YT4 length 7.1541 YT5@+X717826 to YT5@+X920982 via YT5 length 7.0805 YT1@CanCus to YT1@+X680719 via YT1 length 6.9887 YT2@HunCrkRd to YT2@BonCrkRd via YT2 length 6.9588 YT6@+X620794 to YT6@LapCanTr via YT6 length 6.8125

A format similar to the above would be appropriate for text output.
You will earn 15 points for producing correct output similar to the
above. The reference solution does this with the
`PrintShortestEdges` (`pse`) and `PrintLongestEdges`
(`ple`) commands. Each should take a parameter, which is how many
of the shorest/longest edges should be displayed.

One way to accomplish this is to create a list of all edges and sort
them by edge length. But we can do this more efficiently. For
5 points, compute the set of longest/shortest edges in
*Theta(n|E|)* time, where *n* is the number of longest/shortest edges
you are looking for and *|E|* is total the number of edges in the
graph. See the idea of a "BestOf" structure as described in the lab
exercise at the end of Chapter 11 (p. 275) of Bailey.

For 5 points, you are to implement two additional commands, where the
lists of longest or shortest edges are written to a file in a
particular format. Here, each edge in the set of results should be
specified by placing the vertex information for each of its endpoints
on consecutive lines of a file. For example, the 3 shortest edges
from `canyt.gra` would be specified as:

YT6@MacBoatLau 62.86788 -130.82806 YT6@+X646670 62.868138 -130.827901 YT1@MorLakeRS 59.998729 -132.116818 YT1@BC/YT 60.000075 -132.117087 YT1@BeaCrkAir 62.407424 -140.860358 YT1@CanCus 62.40891 -140.85935

The reference solution does this with the `MapShortestEdges`
(`mse`) and `MapLongestEdges` (`mle`) commands. Each should
take two parameters, the first being how many of the shorest/longest
edges should be displayed, and the second the name of the file to use.

These files should be given a `.nmp` extension. These files can
also be visualized by HDX at
`/chm/viewer/`.

Written Problem

Just one written problem this time:

- Levitin Exercise 7.1.8, p. 258. (5 points)

Submitting

Before 11:59 PM, Tuesday, April 7, 2015, submit your problem set for
grading. To complete the
submission, upload an archive (a `.7z` or
`.zip`) file containing all required files using
Submission
Box under assignment "PS7".

Grading

This assignment is worth 35 points, which are distributed as follows:

> Feature | Value | Score |

Mappable graph traversals | 10 | |

Shortest/longest set of edge lengths correctness | 10 | |

Shortest/longest efficiently | 5 | |

Shortest/longest mappable | 5 | |

Exercise 7.1.8 | 5 | |

Total | 35 | |