--- /dev/null
+/*
+
+ Test for the MPI Graph routines :
+
+ MPI_Graphdims_get
+ MPI_Graph_create
+ MPI_Graph_get
+ MPI_Graph_map
+ MPI_Graph_neighbors
+ MPI_Graph_neighbors_count
+*/
+
+
+#include "mpi.h"
+#include <stdio.h>
+/* stdlib.h Needed for malloc declaration */
+#include <stdlib.h>
+#include "test.h"
+
+void NumberEdges ( int **, int **, int, int, int );
+void PrintGraph ( int, int *, int * );
+
+int main( int argc, char **argv )
+{
+ MPI_Comm comm, new_comm;
+ int reorder;
+ int nbrarray[3], baseindex;
+ int size, i, j, nnodes, nedges, q_nnodes, q_nedges, q_nnbrs, newrank;
+ int *index, *edges, *q_index, *q_edges, *rankbuf;
+ int worldrank, err = 0, toterr;
+
+ MPI_Init( &argc, &argv );
+
+ MPI_Comm_rank( MPI_COMM_WORLD, &worldrank );
+
+/* Generate the graph for a binary tree.
+
+ Note that EVERY process must have the SAME data
+ */
+ comm = MPI_COMM_WORLD;
+ MPI_Comm_size( comm, &size );
+
+ index = (int *)malloc( (size + 1) * sizeof(int) );
+ edges = (int *)malloc( (size + 1) * 3 * sizeof(int) );
+ reorder = 0;
+ for (i=0; i < size; i++) {
+ index[i] = 0;
+ }
+ NumberEdges( &index, &edges, -1, 0, size - 1 );
+ nedges= index[0];
+ for (i=1; i<size; i++) {
+ nedges += index[i];
+ index[i] = index[i] + index[i-1];
+ }
+ nnodes = size;
+#ifdef DEBUG
+ PrintGraph( nnodes, index, edges );
+#endif
+ MPI_Graph_create( comm, nnodes, index, edges, reorder, &new_comm );
+
+/* Now, try to get the information about this graph */
+ MPI_Graphdims_get( new_comm, &q_nnodes, &q_nedges );
+ if (q_nnodes != nnodes) {
+ printf( "Wrong number of nodes, expected %d got %d\n", nnodes, q_nnodes );
+ err++;
+ }
+ if (q_nedges != nedges) {
+ printf( "Wrong number of edges; expected %d got %d\n", nedges, q_nedges );
+ err++;
+ }
+ q_index = (int *)malloc( q_nnodes * sizeof(int) );
+ q_edges = (int *)malloc( q_nedges * sizeof(int) );
+
+ MPI_Graph_get( new_comm, q_nnodes, q_nedges, q_index, q_edges );
+
+/* Check with original */
+ if (worldrank == 0) {
+ printf( "Checking graph_get\n" );
+ }
+/* Because reorder was set to zero, we should have the same data */
+ for (i=0; i<size; i++) {
+ if (index[i] != q_index[i]) {
+ err++;
+ printf( "index[%d] is %d, should be %d\n", i, q_index[i], index[i] );
+ }
+ }
+ for (i=0; i<nedges; i++) {
+ if (edges[i] != q_edges[i]) {
+ err++;
+ printf( "edges[%d] is %d, should be %d\n", i, q_edges[i], edges[i] );
+ }
+ }
+
+/* Now, get each neighbor set individually */
+ for (i=0; i<size; i++) {
+ MPI_Graph_neighbors_count( new_comm, i, &q_nnbrs );
+ MPI_Graph_neighbors( new_comm, i, 3, nbrarray );
+
+ /* Need to test */
+ baseindex = (i > 0) ? index[i-1] : 0;
+ for (j=0; j<q_nnbrs; j++) {
+ if (nbrarray[j] != edges[baseindex+j]) {
+ err++;
+ printf( "nbrarray[%d] for rank %d should be %d, is %d\n",
+ j, i, edges[baseindex+j], nbrarray[j] );
+ }
+ }
+ }
+
+/* Test MPI_Graph_map by seeing what ranks are generated for this graph */
+ MPI_Graph_map( comm, nnodes, index, edges, &newrank );
+
+ if (worldrank == 0) {
+ printf( "Checking graph_map\n" );
+ }
+/* Check that the ranks are at least disjoint among all processors. */
+ rankbuf = (int *)malloc( size * sizeof(int) );
+ MPI_Allgather( &newrank, 1, MPI_INT, rankbuf, 1, MPI_INT, comm );
+ for (i=0; i<size; i++) {
+ for (j=0; j<size; j++) {
+ if (rankbuf[j] == i) break;
+ }
+ if (j >= size) {
+ err++;
+ printf( "Rank %d missing in graph_map\n", i );
+ }
+ }
+
+ MPI_Allreduce( &err, &toterr, 1, MPI_INT, MPI_SUM, MPI_COMM_WORLD );
+ if (worldrank == 0) {
+ if (toterr == 0)
+ printf( "No errors in MPI Graph routines\n" );
+ else
+ printf( "Found %d errors in MPI Graph routines\n", toterr );
+ }
+
+ MPI_Comm_free( &new_comm );
+ free( index );
+ free( edges );
+ free( q_index );
+ free( q_edges );
+ free( rankbuf );
+ MPI_Finalize( );
+ return 0;
+}
+
+/*
+ * Routine to print out a graph for debugging
+ */
+void PrintGraph( nnodes, index, edges )
+int nnodes, *index, *edges;
+{
+ int i, lastidx, j;
+ lastidx=0;
+ printf( "rank\tindex\tedges\n" );
+ for (i=0; i<nnodes; i++) {
+ printf( "%d\t%d\t", i, index[i] );
+ for (j=0; j<index[i] - lastidx; j++) {
+ printf( "%d ", *edges++ );
+ }
+ printf( "\n" );
+ lastidx = index[i];
+ }
+}
+
+/*
+ Number index[0] as first, add its children, and then number them.
+ Note that because of the way the index/edge list is defined, we
+ need to do a depth-first evaluation
+
+ Each process is connected to the processes rank+1
+ and rank + 1 + floor((size)/2), where size is the size of the subtree
+
+ Make index[i] the DEGREE of node i. We'll make the relative to 0
+ at the end.
+ */
+void NumberEdges( Index, Edges, parent, first, last )
+int **Index, **Edges, parent, first, last;
+{
+ int *index = *Index;
+ int *edges = *Edges;
+ int right;
+
+ index[0] = 0;
+ if (parent >= 0) {
+#ifdef DEBUG
+ printf( "Adding parent %d to %d\n", parent, first );
+#endif
+ *index = *index + 1;
+ *edges++ = parent;
+ }
+ if (first >= last) {
+ /* leaf */
+ index++;
+ if (parent >= 0) {
+ *Index = index;
+ *Edges = edges;
+ }
+ return;
+ }
+
+/* Internal node. Always at least a left child */
+#ifdef DEBUG
+ printf( "Adding left child %d to %d\n", first + 1, first );
+#endif
+ *index = *index + 1;
+ *edges++ = first + 1;
+
+/* Try to add a right child */
+ right = (last - first)/2;
+ right = first + right + 1;
+ if (right == first + 1)
+ right++;
+ if (right <= last) {
+ /* right child */
+#ifdef DEBUG
+ printf( "Adding rightchild %d to %d\n", right, first );
+#endif
+ *index = *index + 1;
+ *edges++ = right;
+ }
+ index++;
+ if (first + 1 <= last && right - 1 > first) {
+ NumberEdges( &index, &edges, first, first + 1,
+ (right <= last) ? right - 1: last );
+ }
+ if (right <= last) {
+ NumberEdges( &index, &edges, first, right, last );
+ }
+ if (parent >= 0) {
+ *Index = index;
+ *Edges = edges;
+ }
+}
