Algorithms in Java, Part 5: Graph Algorithms (3rd Edition) (Pt.5)
Taking edge lengths to be weights, consider the network defined by the edges
Draw the network and give the adjacency -lists structure that is built by Program 20.5. 21.2 Show, in the style of Figure 21.3, all shortest paths in the network defined in Exercise 21.1. 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. 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. 21.5 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. 21.6 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. 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. 21.8 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 . 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.
|