jody@computer.org

Computer Science 3

Graph Traversal – Travel Route Assignment

Problem: Given a graph representing locations and travel among those locations, determine routes according to specified criteria. The nodes of a graph are considered locations. Each location has a cost associated with visitng that location. The edges of a graph are considered direct travel connections between two locations. Each edge has a cost and a time associated with traversing that edge. Edges are non-directional. The product must address finding the following routes:

• Cheapest route(s) from a source location to a destination location (cheapest)
• Shortest-time route(s) from a source location to a destination location (shortest-time)
• Fewest-connection route(s) from a source location to a destination location (least-legs)
• Cheapest route(s) from a source location to a destination location via an intermediate location (layover)
• Route that starts and ends at a given location and visits all locations (tour)
• Cheapest route that starts and ends at a given location and visit all locations (cheapest-tour)
• Route that starts at any location and visits each location exactly once (h-tour)
• Route that starts and ends at a given location and visits each location exactly once (ts-tour)
• Tourist route that starts at any location and traverses every connection exactly once (e-tour)

Sample Graph
Sample Graph Input Format
Location: Connection:	(name cost) (locationName1 locationName2 cost minutes)
Graph:	(Loc/Con1 Loc/Con2 ... Loc/ConN)
Sample Graph:	(define G '((C 10)             (C B  45 25)             (C D  45 30)             (B  9)             (D 12)             (A 10)             (C A  90 45)             (D E  10 10)             (E  8)             (A B  40 30)             (A E 180 60))
Route:	((loc1 loc2 ... locN) cost time)
Function Invocation Syntax
Functions:	(cheapest Graph SourceLoc DestLoc) (shortest-time Graph SourceLoc DestLoc) (least-legs Graph SourceLoc DestLoc) (layover Graph SourceLoc IntLoc DestLoc) (tour Graph Loc) (cheapest-tour Graph Loc) (h-tour Graph) (ts-tour Graph Loc) (e-tour Graph)
Sample Function Invocations and Return Values
	(cheapest G 'A 'D)   ((A C D) 167 75) (shortest-time G 'A 'D)   ((A E D) 220 70)

[More complex sample graph diagram]

Assessment Rubric:

[PDF version]