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 <v1,v2> [w] has a direction, from v1 to v2, 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).
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 solution will also be needed for prac' 6.
L.Allison, Comp. Sci. and S.W.E., Monash University, Australia.