#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. |
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.
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.
int maxWeight |
Computed maximum weight to use.
Algorithm Development Kit 1.0