/*									tab:8
 *
 * make_graph.sc - generate a graph for connected component code
 *
 * "Copyright (c) 1993 by Steve Lumetta and The Regents of the University 
 * of California.  All rights reserved."
 *
 * Permission to use, copy, modify, and distribute this software and its
 * documentation for any purpose, without fee, and without written agreement is
 * hereby granted, provided that the above copyright notice and the following
 * two paragraphs appear in all copies of this software.
 * 
 * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
 * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
 * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 * 
 * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
 * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
 *
 * Author:	    Steve Lumetta
 * Version:	    118
 * Creation Date:   Wed May 11 16:42:21 1994
 * Filename:	    make_graph.sc
 * History:
 */

#include <stdio.h>
#include <split-c/split-c.h>
#include "connect.h"

void *malloc();

int random_seed;
node_t *spread node_list;
int n_ptr_doubles;
int edge_num;
edge_t *f_edges;
FILE *fp;

static void increment (node_t *node)
{
    node->value++;
}

static int e_used = 0;
static void create_edge (node_t *node, node_t *global other)
{
    edge_t *edge = &f_edges[e_used++];
    edge->node = other;
    edge->next = (edge_t *global)node;
}

/*
   all_make_graph -- creates a graph of type <gtype> with <n_vertices>
   vertices, using <percent> to determine the presence of edges.  Returns
   the number of edges in the graph.

   GRAPH_2D: creates a 2 dimensional toroidal graph with an <n_vertices> x
   <n_vertices> block of vertices on each processor.  Edges are present with
   probability <percent>.

   GRAPH_3D: creates a 3 dimensional toroidal graph with an <n_vertices> x
   <n_vertices> x <n_vertices> block of vertices on each processor.  Edges are
   present with probability <percent>.

   GRAPH_DEG_3: creates graph with an <n_vertices>, each of which picks three
   neighbors at random (uniformly).
*/

/* We use node value to maintain some information about remote edges. */
#define HAS_RIGHT 1
#define HAS_DOWN  2
#define HAS_BACK  4

int x_dim, y_dim;

int all_make_graph (graph_t gtype, int n_vertices, int percent)
{
    node_t *node, *global target;
    int n_total, /* x_dim, y_dim, */ z_dim, dims, i, j, k, n_edges, edge_num;
    edge_t *global free_edges, *global new_edge, *global edge;

    srandom ((MYPROC * 7 + 211) * 65539 * random_seed);
    n_edges = 0;
    
    switch (gtype) {
        case GRAPH_2D:
	    n_total = n_vertices * n_vertices;
	    node_list = (node_t *spread)
		all_spread_malloc (n_total * PROCS, sizeof (node_t));
	    for (i = 0, node = tolocal (node_list); i < n_total; i++, node++) {
		node->value = 0;
		node->edges = NULL;
	    }
	    edge_num = (2 * n_total * percent) / 100 + 1;
	    free_edges = (edge_t *global)malloc (edge_num * sizeof (edge_t));
	    for (dims = PROCS, x_dim = 1; dims >= 4; dims /= 4, x_dim *= 2);
	    y_dim = x_dim;
	    x_dim *= dims;
	    for (i = 0, node = tolocal (node_list); i < n_vertices; i++) {
		for (j = 0; j < n_vertices; j++, node++) {
		    if ((random () % 100) < percent) {
			n_edges++;
			if (--edge_num < 0) {
			    edge_num = (n_total * percent) / 800 + 1;
			    free_edges = (edge_t *global)
				malloc (edge_num * sizeof (edge_t));
			    edge_num--;
			}
			new_edge = &free_edges[edge_num];
			new_edge->next = node->edges;
			node->edges = new_edge;
			if (j < n_vertices - 1) {
			    new_edge->node = (node_t *global)(node + 1);
			    if (--edge_num < 0) {
				edge_num = (n_total * percent) / 800 + 1;
				free_edges = (edge_t *global)
				    malloc (edge_num * sizeof (edge_t));
				edge_num--;
			    }
			    new_edge = &free_edges[edge_num];
			    new_edge->next = (node + 1)->edges;
			    (node + 1)->edges = new_edge;
			    new_edge->node = (node_t *global)node;
			} else {
			    new_edge->node =
				toglobal (((MYPROC + 1) % x_dim) +
					  (MYPROC / x_dim) * x_dim,
					  node - n_vertices + 1);
			    node->value |= HAS_RIGHT;
			}
		    }
		    if ((random () % 100) < percent) {
			n_edges++;
			if (--edge_num < 0) {
			    edge_num = (n_total * percent) / 800 + 1;
			    free_edges = (edge_t *global)
				malloc (edge_num * sizeof (edge_t));
			    edge_num--;
			}
			new_edge = &free_edges[edge_num];
			new_edge->next = node->edges;
			node->edges = new_edge;
			if (i < n_vertices - 1) {
			    new_edge->node = (node_t *global)
				(node + n_vertices);
			    if (--edge_num < 0) {
				edge_num = (n_total * percent) / 800 + 1;
				free_edges = (edge_t *global)
				    malloc (edge_num * sizeof (edge_t));
				edge_num--;
			    }
			    new_edge = &free_edges[edge_num];
			    new_edge->next = (node + n_vertices)->edges;
			    (node + n_vertices)->edges = new_edge;
			    new_edge->node = (node_t *global)node;
			} else {
			    new_edge->node =
				toglobal ((((MYPROC / x_dim + 1) * x_dim) %
					   PROCS) + (MYPROC % x_dim), node -
					  n_vertices * (n_vertices - 1));
			    node->value |= HAS_DOWN;
			}
		    }
		}
	    }
	    barrier();
	    /* Check remote nodes to left for edge presence. */
	    for (i = 0, node = tolocal (node_list);
		 i < n_vertices; i++, node += n_vertices) {
		target = toglobal (((MYPROC + x_dim - 1) % x_dim) +
				   (MYPROC / x_dim) * x_dim,
				   node + n_vertices - 1);
		if (target->value & HAS_RIGHT) {
		    if (--edge_num < 0) {
			edge_num = (n_total * percent) / 800 + 1;
			free_edges = (edge_t *global)
			    malloc (edge_num * sizeof (edge_t));
			edge_num--;
		    }
		    new_edge = &free_edges[edge_num];
		    new_edge->next = node->edges;
		    node->edges = new_edge;
		    new_edge->node = target;
		}
	    }
	    barrier();
	    /* Check remote nodes above for edge presence. */
	    for (i = 0, node = tolocal (node_list);
		 i < n_vertices; i++, node++) {
		target = toglobal ((((MYPROC / x_dim + y_dim - 1) * x_dim) %
				    PROCS) + (MYPROC % x_dim), node +
				   n_vertices * (n_vertices - 1));
		if (target->value & HAS_DOWN) {
		    if (--edge_num < 0) {
			edge_num = (n_total * percent) / 800 + 1;
			free_edges = (edge_t *global)
			    malloc (edge_num * sizeof (edge_t));
			edge_num--;
		    }
		    new_edge = &free_edges[edge_num];
		    new_edge->next = node->edges;
		    node->edges = new_edge;
		    new_edge->node = target;
		}
	    }
	    break;
        case GRAPH_3D:
	    n_total = n_vertices * n_vertices * n_vertices;
	    node_list = (node_t *spread)
		all_spread_malloc (n_total * PROCS, sizeof (node_t));
	    for (i = 0, node = tolocal (node_list);
		 i < n_vertices * n_vertices * n_vertices; i++, node++) {
		node->value = 0;
		node->edges = NULL;
	    }
	    edge_num = (3 * n_total * percent) / 100 + 1;
	    free_edges = (edge_t *global)malloc (edge_num * sizeof (edge_t));
	    for (dims = PROCS, x_dim = 1; dims >= 8; dims /= 8, x_dim *= 2);
	    z_dim = y_dim = x_dim;
	    if (dims > 1) {
		x_dim *= 2;
		if (dims > 2)
		    y_dim *= 2;
	    }
	    for (k = 0, node = tolocal (node_list); k < n_vertices; k++) {
		for (i = 0; i < n_vertices; i++) {
		    for (j = 0; j < n_vertices; j++, node++) {
			if ((random () % 100) < percent) {
			    n_edges++;
			    if (--edge_num < 0) {
				edge_num = (n_total * percent) / 800 + 1;
				free_edges = (edge_t *global)
				    malloc (edge_num * sizeof (edge_t));
				edge_num--;
			    }
			    new_edge = &free_edges[edge_num];
			    new_edge->next = node->edges;
			    node->edges = new_edge;
			    if (j < n_vertices - 1) {
				new_edge->node = (node_t *global)(node + 1);
				if (--edge_num < 0) {
				    edge_num = (n_total * percent) / 800 + 1;
				    free_edges = (edge_t *global)
					malloc (edge_num * sizeof (edge_t));
				    edge_num--;
				}
				new_edge = &free_edges[edge_num];
				new_edge->next = (node + 1)->edges;
				(node + 1)->edges = new_edge;
				new_edge->node = (node_t *global)node;
			    } else {
				new_edge->node =
				    toglobal (((MYPROC + 1) % x_dim) +
					      (MYPROC / x_dim) * x_dim,
					      node - n_vertices + 1);
				node->value |= HAS_RIGHT;
			    }
			}
			if ((random () % 100) < percent) {
			    n_edges++;
			    if (--edge_num < 0) {
				edge_num = (n_total * percent) / 800 + 1;
				free_edges = (edge_t *global)
				    malloc (edge_num * sizeof (edge_t));
				edge_num--;
			    }
			    new_edge = &free_edges[edge_num];
			    new_edge->next = node->edges;
			    node->edges = new_edge;
			    if (i < n_vertices - 1) {
				new_edge->node = (node_t *global)
				    (node + n_vertices);
				if (--edge_num < 0) {
				    edge_num = (n_total * percent) / 800 + 1;
				    free_edges = (edge_t *global)
					malloc (edge_num * sizeof (edge_t));
				    edge_num--;
				}
				new_edge = &free_edges[edge_num];
				new_edge->next = (node + n_vertices)->edges;
				(node + n_vertices)->edges = new_edge;
				new_edge->node = (node_t *global)node;
			    } else {
				new_edge->node =
				    toglobal (((MYPROC / x_dim + 1 ) %
					       y_dim) * x_dim +
					      (MYPROC / (x_dim * y_dim)) *
					      (x_dim * y_dim) +
					      (MYPROC % x_dim),
					      node -
					      n_vertices * (n_vertices - 1));
				node->value |= HAS_DOWN;
			    }
			}
			if ((random () % 100) < percent) {
			    n_edges++;
			    if (--edge_num < 0) {
				edge_num = (n_total * percent) / 800 + 1;
				free_edges = (edge_t *global)
				    malloc (edge_num * sizeof (edge_t));
				edge_num--;
			    }
			    new_edge = &free_edges[edge_num];
			    new_edge->next = node->edges;
			    node->edges = new_edge;
			    if (k < n_vertices - 1) {
				new_edge->node = (node_t *global)
				    (node + n_vertices * n_vertices);
				if (--edge_num < 0) {
				    edge_num = (n_total * percent) / 800 + 1;
				    free_edges = (edge_t *global)
					malloc (edge_num * sizeof (edge_t));
				    edge_num--;
				}
				new_edge = &free_edges[edge_num];
				new_edge->next =
				    (node + n_vertices * n_vertices)->edges;
				(node + n_vertices * n_vertices)->edges =
				    new_edge;
				new_edge->node = (node_t *global)node;
			    } else {
				new_edge->node =
				    toglobal ((((MYPROC / (x_dim * y_dim) +
						 1) * x_dim * y_dim) % PROCS) +
					      (MYPROC % (x_dim * y_dim)),
					      node - n_vertices * 
					      n_vertices * (n_vertices - 1));
				node->value |= HAS_BACK;
			    }
			}
		    }
		}
	    }
	    barrier();
	    /* Check remote nodes to left for edge presence. */
	    for (i = 0, node = tolocal (node_list);
		 i < n_vertices * n_vertices; i++, node += n_vertices) {
		target = toglobal (((MYPROC + x_dim - 1) % x_dim) +
				   (MYPROC / x_dim) * x_dim,
				   node + n_vertices - 1);
		if (target->value & HAS_RIGHT) {
		    if (--edge_num < 0) {
			edge_num = (n_total * percent) / 800 + 1;
			free_edges = (edge_t *global)
			    malloc (edge_num * sizeof (edge_t));
			edge_num--;
		    }
		    new_edge = &free_edges[edge_num];
		    new_edge->next = node->edges;
		    node->edges = new_edge;
		    new_edge->node = target;
		}
	    }
	    barrier();
	    /* Check remote nodes above for edge presence. */
	    for (i = 0, node = tolocal (node_list);
		 i < n_vertices; i++, node += n_vertices * (n_vertices - 1)) {
		for (j = 0; j < n_vertices; j++, node++) {
		    target = toglobal (((MYPROC / x_dim + y_dim - 1 ) %
					y_dim) * x_dim +
				       (MYPROC / (x_dim * y_dim)) *
				       (x_dim * y_dim) + (MYPROC % x_dim),
				       node + n_vertices * (n_vertices - 1));
		    if (target->value & HAS_DOWN) {
			if (--edge_num < 0) {
			    edge_num = (n_total * percent) / 800 + 1;
			    free_edges = (edge_t *global)
				malloc (edge_num * sizeof (edge_t));
			    edge_num--;
			}
			new_edge = &free_edges[edge_num];
			new_edge->next = node->edges;
			node->edges = new_edge;
			new_edge->node = target;
		    }
		}
	    }
	    barrier();
	    /* Check remote nodes above for edge presence. */
	    for (i = 0, node = tolocal (node_list);
		 i < n_vertices * n_vertices; i++, node++) {
		target = toglobal ((((MYPROC / (x_dim * y_dim) + z_dim - 1) *
				     x_dim * y_dim) % PROCS) +
				   (MYPROC % (x_dim * y_dim)),
				   node + n_vertices * n_vertices *
				   (n_vertices - 1));
		if (target->value & HAS_BACK) {
		    if (--edge_num < 0) {
			edge_num = (n_total * percent) / 800 + 1;
			free_edges = (edge_t *global)
			    malloc (edge_num * sizeof (edge_t));
			edge_num--;
		    }
		    new_edge = &free_edges[edge_num];
		    new_edge->next = node->edges;
		    node->edges = new_edge;
		    new_edge->node = target;
		}
	    }
	    break;
	case GRAPH_DEG_3:
	    n_total = n_vertices;
	    node_list = (node_t *spread)
		all_spread_malloc (n_total * PROCS, sizeof (node_t));
	    for (i = 0, node = tolocal (node_list); i < n_total; i++, node++) {
		node->value = 0;
		node->edges = NULL;
	    }
	    barrier ();
	    edge_num = 3 * n_total;
	    free_edges = (edge_t *global)malloc (edge_num * sizeof (edge_t));
	    for (i = 0, node = tolocal (node_list); i < n_total; i++, node++) {
#if 0
		for (j = 0; j < 3; j++) {
#endif
		for (j = (random () & 3); j > 0; j--) {
		    n_edges++;
		    new_edge = &free_edges[--edge_num];
		    new_edge->next = node->edges;
		    node->edges = new_edge;
		    new_edge->node = &node_list[random () % (n_total * PROCS)];
		    atomic (increment, &new_edge->node->value);
		}
	    }
	    all_atomic_sync ();
	    for (i = 0, edge_num = 0, node = tolocal (node_list); i < n_total;
		 i++, node++)
		edge_num += node->value;
	    f_edges = (edge_t *)malloc (edge_num * sizeof (edge_t));
	    barrier ();
	    for (i = 0, node = tolocal (node_list); i < n_total; i++, node++)
		for (edge = node->edges; edge != NULL; edge = edge->next)
		    atomic (create_edge, edge->node, (node_t *global)node);
	    all_atomic_sync ();
		for (i = 0, edge = (edge_t *global)f_edges; i < edge_num;
		     i++, edge++) {
		node = (node_t *)(edge->next);
		edge->next = node->edges;
		node->edges = edge;
	    }
	    break;
	default:
	    on_one fprintf (fp, "Can't generate that type of graph yet.");
	    barrier ();
	    exit (0);
    }

    n_edges = all_reduce_to_all_add (n_edges);

#ifndef FAST
    on_one fprintf (fp, "Total number of edges: %d\n", n_edges);
#endif
	    
    return n_total;
}

static void usage (char *name)
{
    on_one {
	fprintf (stderr, "Syntax: %s options\n", name);
	fprintf (stderr, "    -double n        Number of pointer doublings per iteration\n");
	fprintf (stderr, "    -number n        Number of vertices (per side of subblock\n");
	fprintf (stderr, "                     for 2D and 3D, total for others)\n");
	fprintf (stderr, "    -output          Use stdout for output\n");
	fprintf (stderr, "    -procs n         Number of processors (power of 2)\n");
	fprintf (stderr, "    -type  2/3/t/r   Graph type (2D, 3D, Degree 3, Random)\n");
	fprintf (stderr, "    -seed  n         Random number seed\n");
	fprintf (stderr, "    -%% n             Probability of edge presence\n");
	fflush (stderr);
    }
    barrier ();
    exit (1);
}

int num_procs, g_type, n_side, percent, use_stdout;

static void process_args (int argc, char **argv) {
    int i, len;

    /* Initialize variables, then change them according to options. */
    num_procs = PROCS;
    random_seed = 123123;
    g_type = GRAPH_2D;
    n_side = 200;
    percent = 40;
    n_ptr_doubles = 3;
    use_stdout = 0;
    
    for (i = 1; i < argc; i++) {
	len = strlen (argv[i]);
	if (argv[i][0] != '-' || len < 2) usage (argv[0]);
	switch (argv[i][1]) {
	    case 'd':
	        if (!strncmp (argv[i], "-double", len)) {
		    if (++i == argc) usage (argv[0]);
		    sscanf (argv[i], "%d", &n_ptr_doubles);
		    break;
		}
		usage (argv[0]);
	    case 'n':
	        if (!strncmp (argv[i], "-number", len)) {
		    if (++i == argc) usage (argv[0]);
		    sscanf (argv[i], "%d", &n_side);
		    break;
		}
		usage (argv[0]);
	    case 'o':
	        if (!strncmp (argv[i], "-output", len)) {
		    use_stdout = 1;
		    break;
		}
		usage (argv[0]);
	    case 'p':
	        if (!strncmp (argv[i], "-procs", len)) {
		    if (++i == argc) usage (argv[0]);
		    sscanf (argv[i], "%d", &num_procs);
		    break;
		}
		usage (argv[0]);
	    case 's':
	        if (!strncmp (argv[i], "-seed", len)) {
		    if (++i == argc) usage (argv[0]);
		    sscanf (argv[i], "%d", &random_seed);
		    break;
		}
		usage (argv[0]);
	    case 't':
	        if (!strncmp (argv[i], "-type", len)) {
		    if (++i == argc) usage (argv[0]);
		    switch (argv[i][0]) {
		        case '2':
			    g_type = GRAPH_2D;
			    break;
			case '3':
			    g_type = GRAPH_3D;
			    break;
			case 't':
			    g_type = GRAPH_DEG_3;
			    break;
			case 'r':
			    g_type = GRAPH_RANDOM;
			    break;
			default:
			    usage (argv[0]);
		    }
		    break;
		}
		usage (argv[0]);
	    case '%':
	        if (!strncmp (argv[i], "-%", len)) {
		    if (++i == argc) usage (argv[0]);
		    sscanf (argv[i], "%d", &percent);
		    break;
		}
		usage (argv[0]);
	}
    }
}

splitc_main (int argc, char **argv)
{
    int n_vertices, i;
    node_t *node, *comp_list;
    edge_t *global edge;

    process_args (argc, argv);
/*    all_set_PROCS (num_procs); */
    on_one {
	if (use_stdout)
	    fp = stdout;
	else
	    fp = fopen("results", "a");
#ifndef FAST
	fprintf(fp, "connect -t %c -n %d -%% %d -p %d -d %d -s %d\n\n",
		"23tr"[g_type], n_side, percent, num_procs, n_ptr_doubles,
		random_seed);
#endif
    }
    n_vertices = all_make_graph (g_type, n_side, percent);

    comp_list = all_local_traversal (n_vertices);
    comp_list = all_find_components (n_vertices, comp_list);
    
    on_one {
#ifndef FAST
	fprintf(fp, "\n\n");
#endif
	fclose(fp);
    }
}