/[paths]/src/graph.c
ViewVC logotype

Contents of /src/graph.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 76 - (show annotations)
Fri Aug 31 03:14:09 2012 UTC (6 years, 10 months ago) by ben
File MIME type: text/plain
File size: 6377 byte(s)
make chromatic distance model displayable
1 /* Copyright (c) 2012, Benoit Rouits <brouits@free.fr>
2 * Some rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * ALTHOUGH THIS SOFTWARE IS MADE OF WIN AND SCIENCE, IT IS PROVIDED BY THE
14 * AUTHOR AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
15 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
16 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
17 * THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
18 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
19 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
20 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
22 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
23 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 *
25 */
26
27 #include <string.h>
28 #include <stdlib.h>
29 #include <time.h>
30 #include <assert.h>
31 #include "graph.h"
32
33 void node_destroy(struct node* n)
34 {
35 int i;
36 for(i = 0; i < n->count; i++) {
37 node_unlink(n, n->neighbours[i].to);
38 }
39 free(n->neighbours);
40 n->neighbours = NULL;
41 return;
42 }
43
44 void node_randomize(struct node* n)
45 {
46 n->event.pitch = rand() % 128;
47 n->event.duration = rand() % 3000000; /* keep randomness < 3sec */
48 n->event.bend = rand();
49 n->event.velocity = rand() % 128;
50 n->event.volume = rand() % 128;
51 }
52
53 int distance_randomize(struct node* a, struct node* b)
54 {
55 return rand();
56 }
57
58 int distance_chromatic(struct node* a, struct node* b)
59 {
60 if (a->event.pitch > b->event.pitch)
61 return a->event.pitch - b->event.pitch;
62 else
63 return b->event.pitch - a->event.pitch;
64 }
65
66 int node_is_linked(struct node* a, struct node* b)
67 {
68 int i;
69 for (i = 0; i < a->count; i++) {
70 if (a->neighbours[i].to == b)
71 return 1;
72 }
73 return 0;
74 }
75
76 int node_link(struct node* a, struct node* b, distance_fun fun)
77 {
78 struct edge *nba, *nbb;
79 int distance = (*fun)(a, b);
80
81 assert (a != b);
82
83 a->count++;
84 nba = realloc(a->neighbours, a->count * sizeof(struct edge));
85 if (!nba) {
86 a->count--;
87 return -1;
88 }
89 nba[a->count - 1].to = b;
90 nba[a->count - 1].from = a;
91 nba[a->count - 1].distance = distance;
92
93 b->count++;
94 nbb = realloc(b->neighbours, b->count * sizeof(struct edge));
95 if (!nbb) {
96 a->count--;
97 b->count--;
98 free(nba);
99 return -1;
100 }
101 nbb[b->count - 1].to = a;
102 nbb[b->count - 1].from = b;
103 nbb[b->count - 1].distance = distance;
104
105 a->neighbours = nba;
106 b->neighbours = nbb;
107 return distance;
108 }
109
110 int node_unlink(struct node* a, struct node* b)
111 {
112 struct edge *nba, *nbb;
113 int i, j;
114 a->count--;
115 nba = malloc(a->count * sizeof(struct edge));
116 if (!nba) {
117 a->count++;
118 return -1;
119 }
120 for (i = 0, j = 0; i < a->count; i++, j++) {
121 if (a->neighbours[i].to != b) {
122 nba[j].to = a->neighbours[i].to;
123 nba[j].distance = a->neighbours[i].distance;
124 } else {
125 j--;
126 }
127 }
128
129 nbb = malloc(b->count * sizeof(struct edge));
130 if (!nbb) {
131 a->count++;
132 b->count++;
133 free(nba);
134 return - 1;
135 }
136 for (i = 0, j = 0; i < b->count; i++, j++) {
137 if (b->neighbours[i].to != a) {
138 nbb[j].to = b->neighbours[i].to;
139 nbb[j].distance = b->neighbours[i].distance;
140 } else {
141 j--;
142 }
143 }
144 free(a->neighbours);
145 free(b->neighbours);
146 a->neighbours = nba;
147 b->neighbours = nbb;
148 return 0;
149 }
150
151 struct graph* graph_new(int n)
152 {
153 struct graph* g;
154
155 srand(time(NULL));
156
157 g = malloc(sizeof(struct graph));
158 if (!g) {
159 return NULL;
160 }
161
162 g->nodes = malloc(n * sizeof(struct node));
163 if (!(g->nodes)) {
164 free(g);
165 return NULL;
166 }
167
168 memset(g->nodes, 0, n * sizeof(struct node));
169 g->count = n;
170 g->edges = NULL;
171 g->egg = NULL;
172 return g;
173 }
174
175 static struct edge* graph_edges_grow(struct edge* edges, int lcount, struct node* u, struct node* v, int distance)
176 {
177 struct edge* e;
178
179 e = realloc(edges, (lcount + 1) * sizeof(*edges));
180 if (!e)
181 return NULL;
182 edges = e;
183 edges[lcount].from = u;
184 edges[lcount].to = v;
185 edges[lcount].distance = distance;
186
187 return edges;
188 }
189
190 int graph_randomize1(struct graph* g, int l)
191 {
192 int m, n, i, j;
193 int distance;
194
195 /* randomize node's values for each node */
196 for (i = 0; i < g->count; i++) {
197 node_randomize(&(g->nodes[i]));
198 }
199
200 /* create l links */
201 for (j = 0; j < l; j++) {
202 struct edge *e;
203 m = rand() % g->count;
204 n = rand() % g->count;
205 if ((m == n) || node_is_linked(&(g->nodes[m]), &(g->nodes[n]))) {
206 continue;
207 }
208 if ((distance = node_link(&(g->nodes[m]), &(g->nodes[n]), distance_chromatic)) < 0) {
209 goto revert;
210 }
211 /* keep memory of links */
212 e = graph_edges_grow(g->edges, j, &(g->nodes[m]), &(g->nodes[n]), distance);
213 if (!e)
214 goto revert;
215 g->edges = e;
216 }
217
218 g->lcount = l;
219 return 0;
220 revert:
221 for (i = 0; i < g->count; i++) {
222 node_destroy(&(g->nodes[i]));
223 }
224 free(g->edges);
225 g->edges = NULL;
226 g->lcount = 0;
227 memset(g->nodes, 0, g->count * sizeof(struct node));
228 return -1;
229 }
230
231 int graph_randomize2(struct graph* g, int l)
232 {
233 int i, j, n;
234 int lcount = 0;
235 int distance;
236
237 for (i = 0; i < g->count; i++) {
238 node_randomize(&(g->nodes[i]));
239
240 for (j = 0; j < l; j++) {
241 struct edge *e;
242 n = rand() % g->count;
243 if ((i == n) || node_is_linked(&(g->nodes[i]), &(g->nodes[n]))) {
244 continue;
245 }
246 if ((distance = node_link(&(g->nodes[i]), &(g->nodes[n]), distance_chromatic)) < 0)
247 goto revert;
248 /* else */
249 /* keep memory of links */
250 e = graph_edges_grow(g->edges, lcount, &(g->nodes[i]), &(g->nodes[n]), distance);
251 if (!e)
252 goto revert;
253 g->edges = e;
254 lcount++;
255 }
256 }
257
258 g->lcount = lcount;
259 return 0;
260 revert:
261 for (i = 0; i < g->count; i++) {
262 node_destroy(&(g->nodes[i]));
263 }
264 free(g->edges);
265 g->edges = NULL;
266 g->lcount = 0;
267 memset(g->nodes, 0, g->count * sizeof(struct node));
268 return -1;
269 }
270
271 void graph_destroy(struct graph* g)
272 {
273 int i;
274
275 for (i = 0; i < g->count; i++) {
276 free(g->nodes[i].neighbours);
277 }
278 free(g->nodes);
279 free(g->edges);
280 free(g);
281 return;
282 }

  ViewVC Help
Powered by ViewVC 1.1.26