Exercises

Java graphics ltr.gif 21.1 Label the following points in the plane 0 through 5, respectively: Java graphics 284equ01.gif


Taking edge lengths to be weights, consider the network defined by the edges Java graphics 284equ02.gif


Draw the network and give the adjacency-lists structure that is built by Program 20.5.

Show, in the style of Screenshot, all shortest paths in the network defined in Exercise 21.1.

Screenshot 21.3 Develop a network class implementation that represents the reverse of the weighted digraph defined by the edges inserted. Include a "reverse copy" constructor that takes a graph as parameter and inserts all that graph's edges to build its reverse.

Screenshot 21.4 Show that shortest-paths computations in networks with nonnegative weights on both vertices and edges (where the weight of a path is defined to be the sum of the weights of the vertices and the edges on the path) can be handled by building a network ADT that has weights on only the edges.

Find a large network online—perhaps a geographic database with entries for roads that connect cities or an airline or railroad schedule that contains distances or costs.

Write a random-network generator for sparse networks based on Program 17.12. To assign edge weights, define a random-edge–weight ADT and write two implementations: one that generates uniformly distributed weights, another that generates weights according to a Gaussian distribution. Write client programs to generate sparse random networks for both weight distributions with a well-chosen set of values of V and E so that you can use them to run empirical tests on graphs drawn from various distributions of edge weights.

Screenshot 21.7 Write a random-network generator for dense networks based on Program 17.13 and edge-weight generators as described in Exercise 21.6. Write client programs to generate random networks for both weight distributions with a well-chosen set of values of V and E so that you can use them to run empirical tests on graphs drawn from these models.

Implement a representation-independent network client that builds a network by taking edges with weights (pairs of integers between 0 and V – 1 with weights between 0 and 1) from standard input.

• 21.9 Write a program that generates V random points in the plane, then builds a network with edges (in both directions) connecting all pairs of points within a given distance d of one another (see Exercise 17.74), setting each edge's weight to the distance between the two points that that edge connects. Determine how to set d so that the expected number of edges is E.

Screenshot 21.10 Write a base class and derived classes that implement ADTs for graphs that may be undirected or directed graphs, weighted or unweighted, and dense or sparse.

Java graphics ltr.gif 21.11 The following table from a published road map purports to give the length of the shortest routes connecting the cities. It contains an error. Correct the table. Also, add a table that shows how to execute the shortest routes, in the style of Screenshot.

 

Providence

Westerly

New London

Norwich

Providence

53

54

48

Westerly

53

18

101

New London

54

18

12

Norwich

48

101

12

Screenshot


   
Comments