diff options
Diffstat (limited to 'test/ccured_olden/em3d/make_graph.c')
| -rw-r--r-- | test/ccured_olden/em3d/make_graph.c | 173 |
1 files changed, 173 insertions, 0 deletions
diff --git a/test/ccured_olden/em3d/make_graph.c b/test/ccured_olden/em3d/make_graph.c new file mode 100644 index 00000000..6bec340d --- /dev/null +++ b/test/ccured_olden/em3d/make_graph.c @@ -0,0 +1,173 @@ +/* make_graph.c - Create a graph to be solved for the electromagnetic + * problem in 3 dimensions. + * + * By: Martin C. Carlisle + * Date: Feb 23, 1994 + * + */ + +#include <stdio.h> +#include <stdlib.h> +#include "em3d.h" +#include "util.h" + +#define NUM_H_NODES n_nodes +#define H_NODE_DEGREE d_nodes + +#define NUM_E_NODES n_nodes +#define E_NODE_DEGREE d_nodes + +int n_nodes; +int d_nodes; + +node_t **make_table(int size) +{ + node_t **retval; + + retval = (node_t **) ALLOC(size*sizeof(node_t *)); + assert(retval); + return retval; +} + +// post: +// all 'next' fields valid or null +// to_nodes, from_nodes, coefs are dead +void fill_table(node_t **table, int size) +{ + int i; + + /* Now we fill the table with allocated nodes */ + for (i=0; i<size; i++) + { + table[i] = (node_t *) ALLOC(sizeof(node_t)); + table[i]->value = gen_uniform_double(); + table[i]->from_count = 0; + + if (i > 0) + table[i-1]->next = table[i]; + } + table[size-1]->next = NULL; +} + +// post: +// nodes in 'nodelist' have their 'to_nodes' array created, of +// size 'degree'; then this array is filled with pointers to +// randomly-chosen nodes (no duplicates); 'from_count' in the +// pointed-to node keeps track of its in-degree +void make_neighbors(node_t *nodelist, node_t **table, int tablesz, + int degree) +{ + node_t *cur_node; + + for(cur_node = nodelist; cur_node; cur_node=cur_node->next) + { + node_t *other_node; + int j,k; + + cur_node->to_nodes = (node_t **) ALLOC(degree*(sizeof(node_t *))); + for (j=0; j<degree; j++) + { + /* Make sure no duplicates are generated */ + do + { + other_node = table[gen_number(tablesz)]; + for (k=0; k<j; k++) + if (other_node == cur_node->to_nodes[k]) break; + } + while (k<j); + cur_node->to_nodes[j]=other_node; + other_node->from_count++; /* bad load: 50% */ + } + } +} + +// post: +// from_nodes and coeffs get allocated, size specified by 'from_count', +// which is the 'degree' from above; coeff's entries are set randomly, +// from_nodes' entries left dead; from_count then set to 0 +void update_from_coeffs(node_t *nodelist) +{ + node_t *cur_node; + + /* Setup coefficient and from_nodes vectors for h nodes */ + for (cur_node = nodelist; cur_node; cur_node=cur_node->next) + { + int from_count = cur_node->from_count; + int k; + + cur_node->from_nodes = (node_t **) ALLOC(from_count * sizeof(node_t *)); + cur_node->coeffs = (double *) ALLOC(from_count * sizeof(double)); + for (k=0; k<from_count; k++) + cur_node->coeffs[k] = gen_uniform_double(); + + cur_node->from_count = 0; + } +} + +// post: +// nodes pointed-to by those on 'nodelist' have their from_nodes' +// entries filled with back-edges; from_count is used to add +// information contiguously; global algorithm structure keeps the +// array access in bounds (we counted in-degree before, and that +// count was used to allocate, and now we one again enumerate the +// pointers to a node); perhaps a runtime check is in order here +void fill_from_fields(node_t *nodelist, int degree) +{ + node_t *cur_node; + for(cur_node = nodelist; cur_node; cur_node = cur_node->next) + { + int j; + + for (j=0; j<degree; j++) + { + node_t *other_node = cur_node->to_nodes[j]; + other_node->from_nodes[other_node->from_count] = cur_node; + other_node->from_count++; + } + } +} + +// post: +// two arrays of nodes are created; all 'h' nodes are then pointed to +// H_NODE_DEGREE 'e' nodes, and vice-versa for 'e' nodes; backedge +// information is also computed; pointers to the first nodes of each +// set are stashed in a graph_t and returned (sets are linked together +// as a linked list) +graph_t initialize_graph() +{ + node_t **h_table; + node_t **e_table; + graph_t retval; + + /* We start by creating a table of pointers to the h nodes */ + h_table = make_table(NUM_H_NODES); + fill_table(h_table,NUM_H_NODES); + + /* We repeat the same for the e nodes */ + e_table = make_table(NUM_E_NODES); + fill_table(e_table,NUM_E_NODES); + + /* At this point, for each h node, we give it the appropriate number + of neighbors as defined by the degree */ + make_neighbors(h_table[0],e_table,NUM_E_NODES,H_NODE_DEGREE); + make_neighbors(e_table[0],h_table,NUM_H_NODES,E_NODE_DEGREE); + + /* We now create from count and initialize coefficients */ + update_from_coeffs(h_table[0]); + update_from_coeffs(e_table[0]); + + /* Fill the from fields in the nodes */ + fill_from_fields(h_table[0],H_NODE_DEGREE); + fill_from_fields(e_table[0],E_NODE_DEGREE); + + retval.e_nodes=e_table[0]; + retval.h_nodes=h_table[0]; + + free(h_table); + free(e_table); + + return retval; +} + + + |