Computer Science 431
Algorithms

Spring 2015, The College of Saint Rose

Home     Syllabus     Schedule

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: