Project Option: Network Algorithms

Overview

The City of Seattle has finally gotten fed up with Sound Transit. You, our hero(ine), have been summoned from the dappled forests of that mystical kingdom known as Sieg, shrouded in mystery (even the UWites don't know what happens in there for no one ever goes in...and no one ever comes out).

You are presented with the problem of providing efficient transit to major points of interest within the city. To keep costs down, it is suggested that you build your structure on top of or underneath existing roadways and thouroughfares. Your training in the Dark Arts of CSE allow you to immediately realize that this is a graph problem and that the all-pairs shortest path algorithm would give a good first apprximation to this (also, you heard that this technique was being considered for use in planning new freeways...).

So, while you still haven't decided whether or not you want to put busses, trains, monorails, subways, or rope tows with skateboards on your new routes, at least you have a good starting point for determining the ideal routes.

Assignment

For this assignment, you will write a program that takes as input a file containing a description of your graph. Your program will then find the shortest paths between every pair of nodes in the network and find the cut points (for potential bottleneck analysis. Also known as cut vertices.) in the network. An more detailed explanation of how DFS can be applied to find cut points is given can be found here.

You will have to design and implement a generic digraph representation and implement the "all-pairs shortest path" algorithm (as described in Weiss), as well as a non-brute force algorithm for finding cut points.

File Format:

Because we will use graphs of the below format in our tests, it is VITALLY IMPORTANT that the input to your program be able to read the format described below. You are responsible for ensuring that your program behaves properly on legal input. Everything between (but not including) BEGIN and END is a description of the file format. Brackets ('<' and '>') are used to designate descriptions of the file text, rather than the text itself. Anything after a # is a comment; you do not have to implement comments in your programs parser! Columns of vertical periods are used to show that a list of the preceeding pattern is to be included.

BEGIN cse326Graph-v1.0 # This is the version number for this file format. <number of nodes> <number of edges> <node identifier> <node label> # The identifier must be a unique integral id. . # The label must be a string with no spaces. . # The label is meta data and doesn't affect the graph. . # Each identifier/label pair goes on its own line. . (<source node id>, <dest node id>) <cost> # The source node id and the dest . # node id correspond to the nodes from which this edge . # sources and to which it goes. The cost is a floating-point . # (double) value representing the distance between # these nodes. . # Put each edge on its own line. . $ # Put a dollar sign at the end to signify end of file. END The version number is meant to allow for you to extend the file format without breaking compatability with our test code. If you wish to extend the file format to accomodate other data for your graph, change the version number and make your parser behave differently if it sees your version number at the top of the file. However, if you decide to extend your parser, you still must be able to parse the version 1 file format given here, so you can run our test cases.

If you need further clarification on the maze file format, please read this email.

Extensions:

For extensions, you pretty much have a carte blache. Here are a few ideas. They are by no means the only things you can do as extensions.

Distance is not the only factor when it comes to traffic congestion! Simulate real traffic conditions by modifying the file format so that your program will accept the average duration of a trip along an edge, and allow the user to calculate the shortest path between two nodes based on distance, duration of trip, or some mixture of the two.
Simulate traffic conditions at different times of day by modifying your program so that the user may interactively change the duration of a trip along an arbitrary edge (see the above extension). You will need dynamically update your shortest path calculations and inform the user of any changed routes. Note that it may not be very efficient to run the all-pairs shortest path algorithm every time an edge is modifed in the graph.
Oftentimes, large-scale events such as a sports game or a fair may draw large numbers of vehicles into a relatively small area. Modify your file format so that your program will accept a description of an edge's capacity (ie, the maximum number of cars which can pass through this edge in one minute). Use the MaxFlow/MinCut algorithm (as specified in Weiss) to determine the maximum number of cars which may be routed towards a single destination. You may need to add a fictional "source" node (and edges) to your graph in order to simulate traffic using this algorithm.