1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
|
#include <stdlib.h>
#include <stdio.h>
#include "sysfatal.h"
#include "balls.h"
/*
* A graph on the set of balls. Nodes are ball indices and edges are potential
* collisions between two balls.
*/
typedef struct {
size_t (*edges)[2]; /* Array of edges. Each edge endpoint is a ball index. */
size_t nEdges; /* Length of edge array. */
} Graph;
static Partition newPartition(void);
static Graph completeGraph(size_t nBalls);
static Graph matching(Graph g);
static Graph addEdge(Graph g, size_t edge[2]);
static Graph removeEdges(Graph g, Graph edges);
static Graph removeEdge(Graph g, size_t edge[2]);
static Partition addCell(Partition part, Graph cell);
static Graph newGraph(void);
static void freeGraph(Graph g);
/*
* Partition the set of all possible collisions between pairs of balls into
* chunks that can be computed concurrently. Collisions within a cell of the
* partition can run concurrently. Cells must run sequentially.
*/
Partition
partitionCollisions(size_t nBalls) {
Partition part;
Graph graph, cell;
part = newPartition();
graph = completeGraph(nBalls);
while (graph.nEdges > 0) {
cell = matching(graph);
graph = removeEdges(graph, cell);
part = addCell(part, cell);
}
freeGraph(graph);
return part;
}
void
freePartition(Partition part) {
while (part.size-- > 0)
free(part.cells[part.size].ballIndices);
free(part.cells);
}
void
printPartition(Partition part) {
size_t i, j;
for (i = 0; i < part.size; i++) {
printf("{");
for (j = 0; j < part.cells[i].size; j++)
printf("(%lu, %lu), ", part.cells[i].ballIndices[j][0],
part.cells[i].ballIndices[j][1]);
printf("}\n");
}
}
/* Allocate an empty partition. Partition should be freed by the caller after use. */
static Partition
newPartition(void) {
Partition part;
if ((part.cells = malloc(0)) == NULL)
sysfatal("Failed to allocate partition.\n");
part.size = 0;
return part;
}
/* Create a complete graph on the set of balls. */
Graph
completeGraph(size_t nBalls) {
Graph g;
size_t e, i, j;
g.nEdges = nBalls*(nBalls-1)/2;
if ((g.edges = malloc(g.nEdges * 2*sizeof(size_t))) == NULL)
sysfatal("Failed to allocate graph.\n");
e = 0;
for (i = 0; i < nBalls; i++) {
for (j = i+1; j < nBalls; j++) {
g.edges[e][0] = i;
g.edges[e++][1] = j;
}
}
return g;
}
/*
* Find and return an independent edge set in g. Two edges are independent if
* they don't share any vertices.
*/
Graph
matching(Graph g) {
Graph match;
size_t e, m;
match = newGraph();
for (e = 0; e < g.nEdges; e++) {
for (m = 0; m < match.nEdges; m++)
if (g.edges[e][0] == match.edges[m][0]
|| g.edges[e][0] == match.edges[m][1]
|| g.edges[e][1] == match.edges[m][0]
|| g.edges[e][1] == match.edges[m][1]
)
break;
if (m == match.nEdges) /* No shared vertices. */
match = addEdge(match, g.edges[e]);
}
return match;
}
Graph
addEdge(Graph g, size_t edge[2]) {
if ((g.edges = realloc(g.edges, (g.nEdges+1)*2*sizeof(size_t))) == NULL)
sysfatal("Failed to add edge to graph.\n");
g.edges[g.nEdges][0] = edge[0];
g.edges[g.nEdges][1] = edge[1];
g.nEdges++;
return g;
}
static Graph
removeEdges(Graph g, Graph edges) {
size_t i;
for (i = 0; i < edges.nEdges; i++)
g = removeEdge(g, edges.edges[i]);
return g;
}
Graph
removeEdge(Graph g, size_t edge[2]) {
size_t i, j;
for (i = 0; i < g.nEdges; i++) {
if (g.edges[i][0] == edge[0] && g.edges[i][1] == edge[1]) {
/* Shift left. */
for (j = i+1; j < g.nEdges; j++) {
g.edges[j-1][0] = g.edges[j][0];
g.edges[j-1][1] = g.edges[j][1];
}
g.nEdges--;
break;
}
}
return g;
}
Partition
addCell(Partition part, Graph cell) {
if ((part.cells = realloc(part.cells, (part.size+1)*2*sizeof(size_t))) == NULL)
sysfatal("Failed to grow partition array.\n");
part.cells[part.size].ballIndices = cell.edges;
part.cells[part.size].size = cell.nEdges;
part.size++;
return part;
}
static Graph
newGraph(void) {
Graph g;
if ((g.edges = malloc(0)) == NULL)
sysfatal("Failed to allocate graph.\n");
g.nEdges = 0;
return g;
}
static void
freeGraph(Graph g) {
free(g.edges);
}
|