CSE2304, Prac' 5, week 10 and 11, 10 - 21 May 1999

This prac' is about directed, edge-weighted [graphs]. A graph G=<V,E>, where V is a set of vertices and E is a set of edges. Each vertex has a name (a string) which is given in the input. Each edge <v₁,v₂> [w] has a direction, from v₁ to v₂, and a weight, w. Here is a (small) example data-set:

main-entrance                        -- a vertex or location
se-roundabout                        -- another
ne-roundabout                        -- etc.
nw-roundabout
sports-and-rec
tennis-court
FIT
law
hospital-park
                                     -- blank line ends vertex list
main-entrance  se-roundabout  2.5    -- bi-directional road, i.e. 2 edges
se-roundabout  sports-and-rec 7.5
sports-and-rec tennis-court   2.5
sports-and-rec FIT            5.5 *  -- a one-way road, i.e. one edge
FIT            tennis-court   6 *
tennis-court   ne-roundabout  6
nw-roundabout  ne-roundabout  11
se-roundabout  law            6
law            hospital-park  4 *
hospital-park  nw-roundabout  13 *
nw-roundabout  law            15 *

It represents a part of the road network around the Clayton campus. The vertices/locations are given first, one per line. A blank line indicates the end of the vertices. The edges/roads are given next, one per line. Each (section of) road is specified by two vertex names, separated by at least one space. The length of the road follows, after at least one space. If the road is one-way, an asterisk follows after at least one space, otherwise the road is bi-directional. Note that there is no direct way to drive from nw-roundabout to hospital-park, the car-park in the s.w. corner of campus. (The comments are not part of real data.)

The length of each edge was measured in cm from a printed map (it doesn't give a scale but the units don't really matter). See online [map]. Most roads are bi-directional, but some of them are one-way, e.g. sports-and-rec to FIT, and these are marked with an asterisk `*' above. A bi-directional road between v₁ and v₂ should be represented by two edges in the graph: <v₁,v₂> [w] and <v₂,v₁> [w]. A one-way road should be represented by one edge.

This data set is just an example and your program must run on other, possibly much bigger, graphs, e.g. with tens of thousands of vertices and edges.

Your program must:

1. Read in the graph from a named file specified by a command-line parameter.

2. Assume that the graph is sparse, i.e. |E|<<|V|², and implement it efficiently, e.g. by adjacency lists, in O(|E|)-space.

3. Read pairs of vertices from standard-input (stdin) and say if they are adjacent (in the graph sense) or not and, if they are adjacent, state the distance between them.

Your solution will also be needed for prac' 6.

L.Allison, Comp. Sci. and S.W.E., Monash University, Australia.