1 /* This software was developed by Bruce Hendrickson and Robert Leland *
2 * at Sandia National Laboratories under US Department of Energy *
3 * contract DE-AC04-76DP00789 and is copyrighted by Sandia Corporation. */
4
5 #include <stdio.h>
6 #include "defs.h"
7 #include "structs.h"
8
9
10 /* Find vertices on boundary of partition, and change their assignments. */
11
find_bndy(graph,nvtxs,assignment,new_val,pbndy_list)12 int find_bndy(graph, nvtxs, assignment, new_val, pbndy_list)
13 struct vtx_data **graph; /* array of vtx data for graph */
14 int nvtxs; /* number of vertices in graph */
15 short *assignment; /* processor each vertex gets assigned to */
16 int new_val; /* assignment value for boundary vtxs */
17 int **pbndy_list; /* returned list, end with zero */
18 {
19 int *bndy_list; /* returned list, end with zero */
20 int *edges; /* loops through edge list */
21 int list_length; /* returned number of vtxs on boundary */
22 int set, set2; /* set a vertex is in */
23 int i, j; /* loop counters */
24 double *smalloc(), *srealloc();
25
26 bndy_list = (int *) smalloc((unsigned) (nvtxs + 1) * sizeof(int));
27
28 list_length = 0;
29 for (i = 1; i <= nvtxs; i++) {
30 set = assignment[i];
31 edges = graph[i]->edges;
32 for (j = graph[i]->nedges - 1; j; j--) {
33 set2 = assignment[*(++edges)];
34 if (set2 != set) {
35 bndy_list[list_length++] = i;
36 break;
37 }
38 }
39 }
40 bndy_list[list_length] = 0;
41
42 for (i = 0; i < list_length; i++) {
43 assignment[bndy_list[i]] = (short) new_val;
44 }
45
46 /* Shrink out unnecessary space */
47 *pbndy_list = (int *) srealloc((char *) bndy_list,
48 (unsigned) (list_length + 1) * sizeof(int));
49
50 return (list_length);
51 }
52
53
54 /* Find a vertex separator on one side of an edge separator. */
55
find_side_bndy(graph,nvtxs,assignment,side,new_val,pbndy_list)56 int find_side_bndy(graph, nvtxs, assignment, side, new_val, pbndy_list)
57 struct vtx_data **graph; /* array of vtx data for graph */
58 int nvtxs; /* number of vertices in graph */
59 short *assignment; /* processor each vertex gets assigned to */
60 int side; /* side to take vertices from */
61 int new_val; /* assignment value for boundary vtxs */
62 int **pbndy_list; /* returned list, end with zero */
63
64 {
65 int *edges; /* loops through edge list */
66 int *bndy_list; /* returned list, end with zero */
67 int list_length; /* returned number of vtxs on boundary */
68 int set, set2; /* set a vertex is in */
69 int i, j; /* loop counters */
70 double *smalloc(), *srealloc();
71
72 if (*pbndy_list != NULL) {
73 /* Contains list of all vertices on boundary. */
74 bndy_list = *pbndy_list;
75 i = list_length = 0;
76 while (bndy_list[i] != 0) {
77 if (assignment[bndy_list[i]] == side) {
78 bndy_list[list_length++] = bndy_list[i];
79 }
80 ++i;
81 }
82 }
83
84 else {
85 bndy_list = (int *) smalloc((unsigned) (nvtxs + 1) * sizeof(int));
86
87 list_length = 0;
88 for (i = 1; i <= nvtxs; i++) {
89 set = assignment[i];
90 if (set == side) {
91 edges = graph[i]->edges;
92 for (j = graph[i]->nedges - 1; j; j--) {
93 set2 = assignment[*(++edges)];
94 if (set2 != set) {
95 bndy_list[list_length++] = i;
96 break;
97 }
98 }
99 }
100 }
101 }
102
103 bndy_list[list_length] = 0;
104
105 for (i = 0; i < list_length; i++) {
106 assignment[bndy_list[i]] = (short) new_val;
107 }
108
109 /* Shrink out unnecessary space */
110 *pbndy_list = (int *) srealloc((char *) bndy_list,
111 (unsigned) (list_length + 1) * sizeof(int));
112
113 return (list_length);
114 }
115