Strategy to build test graphs for Dijkstra's algorithm?

Question

I recently implemented Dijkstra's algorithm to practice Java. I'm now considering how to build random test graphs (with unidirectional edges).

Currently, I use a naive method. Nodes are created at random locations in 2d space (where x and y are unsigned integers between 0 and some MAX_SPACE constant). Edges are randomly created to connect the nodes, so that each node has an outdegree of at least 1 (and at most MAX_DEGREE). Indegree is not enforced. Then I search for a path between the first and last Nodes in the set, which may or may not be connected.

In a more realistic situation, nodes would have a probability of being connected proportional to their proximity in 2d space. What is a good strategy to build random test graphs with that property?

NOTES

I will primarily use this to build graphs that can be drawn and verified by hand, but scaling to larger graphs is a consideration.

The strategy should be easily modified to support the following constants (and maybe others -- let me know if you think of any interesting ones):

• MIN_NODES, MAX_NODES: a range of sizes for the graph
• CONNECTEDNESS: average out-degree
• PROXIMITY: weight given to preferring to connect proximal nodes

Answer 1

You could start by looking at the different random graph generators available in JUNG (Java library):

• Barabasi Albert Generator - Simple evolving scale-free random graph generator. At each time step, a new vertex is created and is connected to existing vertices according to the principle of "preferential attachment", whereby vertices with higher degree have a higher probability of being selected for attachment.

• Eppstein Power Law Generator - Graph generator that generates undirected graphs with power-law degree distributions.

There are various other generators available to - See Listing Here

For python there is the NetworkX library that also provides many graph generators - Listed Here

With many of these generators you can specify the size, so you can start small and go from there.