Dijkstra helpers

RandGraph is a program to help with generating, converting and manipulating graphs.

Installing

See INSTALL.

Using RandGraph

Run the program without args to get a list of available commands. A summary of what the various commands do:

• Generate (in native Haskell format) random graphs with:
  • Specified number of vertices,
  • Normally distributed out-degree per vertex, but within a specified maximum. Thus, the out-degree distribution is a "truncated normal".
  • Uniformly random edge destinations (unique for a given source vertex),
  • Uniform edge weights, within a given range.
• Compute shortest paths on the graphs.
• Convert graphs to:
  • C-Json as needed by the SFDL program,
  • Stream of numbers in the format expected by the C implementation of Dijsktra (in dijkstra/c/) intended for the MIPS emulator.
  • A gviz file, which can be processed using dot to produce visualizations of the graph.
  • A file for the uDrawGraph visualization program. This is currently incomplete - the produced uDrawGraph image does not show vertex numbers or edge weights.
• Convert graphs from:
  • C-Json format.
  • A "manual" format consisting of Haskell lists of edges, as specified by the input to the processing function:

    manual2gr :: [(Int,             -- ! vertex number
                   [(Int,           -- ! edge destination vertex number
                     Int)           -- ! edge weight
                   ])
                 ] -> ...