NAME
Test program for Graph.
SYNOPSIS
perl test_graph.pl [size (default 3 works well)]DESCRIPTION
This program constructs size x size "square" directed and undirected graphs, then tests various path-finding related methods: TransitiveClosure_Floyd_Warshall, APSP_Floyd_Warshall, and SSSP (all flavors).
You can think of each node as a cell in a matrix. In the directed case, each node is has edges from its neighbors down and right (the coordinates growing to down and right), eg, node 1,1 is has edges to nodes 1,2, node 2,1, and node 2,2. In the undirected case, the down left diagonal is present as well, eg, from node 1,1 to node 0,2. All edges have unit weight.
This structure makes it easy to calculate the correct answers. For example, the all-pairs-shortest-path in the directed case should have an edge from every node to every other node that is further down or to the right, and the weight should be equal to the maximun difference in the coordinates of the nodes. Eg, the weight from node 1,1 to node 3,3 is 2 along the path 1,1 to 2,2 to 3,3.
AUTHOR
Nathan Goodman