Graph/SingleSourceShortestPath/generateBench.c File Reference

Program to generate a bunch of large (sparse) sample graphs. More...

#include <stdio.h>
#include <stdlib.h>

Functions

int randomWeight ()
 Generate random weight over the graph.
int main (int argc, char **argv)
 Generate benchmark graph 1.

Variables

int maxWeight
 Computed maximum weight to use.


Detailed Description

Program to generate a bunch of large (sparse) sample graphs.

Computes a stylized sparse graph given parameter n. Final graph will have n^2+2 vertices and n^3 - n^2 + 2n edges. Each edge will have a random weight greater than zero and less than n*n.

Author:
George Heineman
Date:
6/15/08

Function Documentation

int main ( int  argc,
char **  argv 
)

Generate benchmark graph 1.

Given argument n, generate graph with n^2+2 vertices.

Imagine a square nxn of vertices viewed as a set of n columns. All vertices in column i are connected to all vertices i column i+1, for 0 <= i < n. Then vertex s are connected to all vertices in column 0 while all vertices in column n-1 are connected to target vertex t.

All edges are given a random weight in the range 1..n^2

Total edges = n + n^2(n-1) + n = n^3-n^2+2n

int randomWeight (  ) 

Generate random weight over the graph.


Variable Documentation

int maxWeight

Computed maximum weight to use.

Algorithm Development Kit 1.0