7.9 Find a route

7.9 Find a route

This program will use scanf (fscanf) to input data and a number of arrays to process the data.

The program will first input a data set that the first part is composed of records that have four data elements. The first two are zip codes, the third is the distance, in miles, between the two zip codes. The last field is a comment. These records represent a rode between two cities. A route, in this case can be traveled either direction. All three values will be integers.

This section of the data is terminated by a record with all three values set to zero.

The next section in the data file is a set of records that have two zip codes. For each pair of zip codes find a route between the zip codes. There is a third field that has a comment.

Be able to get your data both from the standard input or a specified file name.

The data set is "guaranteed" to have less than 500 roads and less than 250 zip codes. But, use #define pre-processor statements to define these limits (if you need limits).

For extra credit, find multiple routes and select the shortest (and longest?) route.

At the start of your program print out:

• Your name
• CIS265 Louis Taber
• Lab: 7.9: Find a route
• A blank line
• The number of roads read in
• A second blank line

Then for each route requested print out:

• The route number and the source and destination zip codes.
• Each of the roads taken and there length
• A summary of the route with the total miles and the number of roads
• Print a descriptive error message if no route can be found. Indicate why with as much detail as possible.

At the end of your program print the following summary:

• The number of routes found, total miles and total roads.
• The number of routes not found.

Given the following example input.

85716 95949  820 Tucson-GrassValley
99801 95949 1400 GrassValley-Alaska
00000 00000   00
85716 99801      Tucson-Alaska
85716 34562      Tucson-?
00000 00000

This output should be in (about) the following format:

Your name
CIS265  Louis Taber
Lab: 7.7: Find a route

3 roads read in.

1. Route from 85716 to 99801
   85716 to 95949   820 miles
   95949 to 99801   400 miles
** 85716 to 99801  1240 miles

2. Route from 85716 to 34562
** No route available: zip 34562 not found.

Summary:
   1 route(s) found.  Total 1240 miles.  Total 2 roads.
   1 route not found 

Test your program with the following sample data set. It is available by anonymous FTP at
ftp://lt.tucson.az.us/pub/c/route.dat.

Study areas:

• File processing. Hanly & Koffman Chapter 12, Page 595. Kernighan Chapter 8 p151, & p241-249. Harbison Chapter 11.
• scanf(). Hanly & Koffman pages 35, 51-53, 88, and 461. Kernighan p157. Harbison p357-364.
• Arrays. Hanly & Koffman Chapter 8, page 363. Kernighan Chapter 5 page 93. Harbison p123-126.
• Pointers. Hanly & Koffman p280, p283, p678. Kernighan Chapter 5 page 93. Harbison p119-123.
• rand() & srand(). Hanly & Koffman page AP9. Kernighan p252. (Perhaps p46 too.) Harbison p393.

Hints:

• Keep track when a road has been used.
• Keep track of when a zip code has been "visited".
• Keep track of roads and zips that don't work.
• Clear the above indicators before working on a new route.
• Remember roads can be used both ways.
• Be able to "back-track" roads/routes that didn't work.
• For the extra credit portion, choose random directions leaving a given zip code. Look at the function rand(). Keep track of the best current route while looking for a shorter path.
• Look at the "read roads" program in section: 6.21.4.

Turn in a copy of your program and its output when used with the above test data marked with:

• Your name
• TABER CIS265
• Lab 7.9: Find a route
• The compiler and OS that you used.

Please turn your lab in to me, Louis Taber, during class, or slide it under the door of Santa Rita Building room A-115 (my office).

7.9 Find a route