Programming the Cell Processor
by Daniele Paolo Scarpazza, Oreste Villa, and Fabrizio Petrini


Listing One

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

/* ... */

/* the graph */
vertex_t * G;

/* number of vertices in the graph */
unsigned card_V;

/* root vertex (where the visit starts) */
unsigned root;

void parse_input( int argc, char** argv );
int main(int argc, char ** argv)
{
  unsigned *Q, *Q_next, *marked;
  unsigned  Q_size=0, Q_next_size=0;
  unsigned  level = 0;

  parse_input(argc, argv);
  graph_load();

  Q      = (unsigned *) calloc(card_V, sizeof(unsigned));
  Q_next = (unsigned *) calloc(card_V, sizeof(unsigned));
  marked = (unsigned *) calloc(card_V, sizeof(unsigned));

  Q[0] = root;
  Q_size  = 1;
  while (Q_size != 0)
    {
      /* scanning all vertices in queue Q */
      unsigned Q_index;
      for ( Q_index=0; Q_index<Q_size; Q_index++ )
	{
	  const unsigned vertex = Q[Q_index];
	  const unsigned length = G[vertex].length;
	  /* scanning each neighbor of each vertex */
	  unsigned i;
	  for ( i=0; i<length; i++)
	    {
	      const unsigned neighbor = G[vertex].neighbors[i];
	      if( !marked[neighbor] ) {
		/* mark the neighbor */
		marked[neighbor]      = TRUE;
		/* enqueue it to Q_next */
		Q_next[Q_next_size++] = neighbor;
	      }
	    }
	}
      level++;
      unsigned * swap_tmp;
      swap_tmp    = Q;
      Q           = Q_next;
      Q_next      = swap_tmp;
      Q_size      = Q_next_size;
      Q_next_size = 0;
    }
  return 0;
}





