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

Contents of /src/graph.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 32 - (show annotations)
Sat Aug 18 15:25:03 2012 UTC (7 years, 1 month ago) by ben
File MIME type: text/plain
File size: 5022 byte(s)
have fun with a longer single route
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 void edge_randomize(struct edge* e)
54 {
55 e->distance = rand();
56 }
57
58 int node_is_linked(struct node* a, struct node* b)
59 {
60 int i;
61 for (i = 0; i < a->count; i++) {
62 if (a->neighbours[i].to == b)
63 return 1;
64 }
65 return 0;
66 }
67
68 int node_link(struct node* a, struct node* b, int distance)
69 {
70 struct edge *nba, *nbb;
71
72 assert (a != b);
73
74 a->count++;
75 nba = realloc(a->neighbours, a->count * sizeof(struct edge));
76 if (!nba) {
77 a->count--;
78 return -1;
79 }
80 nba[a->count - 1].distance = distance;
81 nba[a->count - 1].to = b;
82
83 b->count++;
84 nbb = realloc(b->neighbours, b->count * sizeof(struct edge));
85 if (!nbb) {
86 a->count--;
87 b->count--;
88 free(nba);
89 return -1;
90 }
91 nbb[b->count - 1].distance = distance;
92 nbb[b->count - 1].to = a;
93
94 a->neighbours = nba;
95 b->neighbours = nbb;
96 return 0;
97 }
98
99 int node_unlink(struct node* a, struct node* b)
100 {
101 struct edge *nba, *nbb;
102 int i, j;
103 a->count--;
104 nba = malloc(a->count * sizeof(struct edge));
105 if (!nba) {
106 a->count++;
107 return -1;
108 }
109 for (i = 0, j = 0; i < a->count; i++, j++) {
110 if (a->neighbours[i].to != b) {
111 nba[j].to = a->neighbours[i].to;
112 nba[j].distance = a->neighbours[i].distance;
113 } else {
114 j--;
115 }
116 }
117
118 nbb = malloc(b->count * sizeof(struct edge));
119 if (!nbb) {
120 a->count++;
121 b->count++;
122 free(nba);
123 return - 1;
124 }
125 for (i = 0, j = 0; i < b->count; i++, j++) {
126 if (b->neighbours[i].to != a) {
127 nbb[j].to = b->neighbours[i].to;
128 nbb[j].distance = b->neighbours[i].distance;
129 } else {
130 j--;
131 }
132 }
133 free(a->neighbours);
134 free(b->neighbours);
135 a->neighbours = nba;
136 b->neighbours = nbb;
137 return 0;
138 }
139
140 struct graph* graph_new(int n)
141 {
142 struct graph* g;
143
144 srand(time(NULL));
145
146 g = malloc(sizeof(struct graph));
147 if (!g) {
148 return NULL;
149 }
150
151 g->nodes = malloc(n * sizeof(struct node));
152 if (!(g->nodes)) {
153 free(g);
154 return NULL;
155 }
156
157 memset(g->nodes, 0, n * sizeof(struct node));
158 g->count = n;
159 return g;
160 }
161
162 int graph_randomize1(struct graph* g, int l)
163 {
164 int m, n, i, j;
165
166 for (i = 0; i < g->count; i++) {
167 node_randomize(&(g->nodes[i]));
168 }
169
170 for (j = 0; j < l; j++) {
171 m = rand() % g->count;
172 n = rand() % g->count;
173 if ((m == n) || node_is_linked(&(g->nodes[m]), &(g->nodes[n]))) {
174 continue;
175 }
176 if (node_link(&(g->nodes[m]), &(g->nodes[n]), rand())) {
177 goto revert;
178 }
179 }
180
181 return 0;
182 revert:
183 for (i = 0; i < g->count; i++) {
184 node_destroy(&(g->nodes[i]));
185 }
186 memset(g->nodes, 0, g->count * sizeof(struct node));
187 return -1;
188 }
189
190 int graph_randomize2(struct graph* g, int l)
191 {
192 int i, j, n;
193 for (i = 0; i < g->count; i++) {
194 node_randomize(&(g->nodes[i]));
195
196 for (j = 0; j < l; j++) {
197 n = rand() % g->count;
198 if ((i == n) || node_is_linked(&(g->nodes[i]), &(g->nodes[n]))) {
199 continue;
200 }
201 if (node_link(&(g->nodes[i]), &(g->nodes[n]), rand())) {
202 goto revert;
203 }
204 }
205 }
206
207 return 0;
208 revert:
209 for (i = 0; i < g->count; i++) {
210 node_destroy(&(g->nodes[i]));
211 }
212 memset(g->nodes, 0, g->count * sizeof(struct node));
213 return -1;
214 }
215
216 void graph_destroy(struct graph* g)
217 {
218 int i;
219
220 for (i = 0; i < g->count; i++) {
221 free(g->nodes[i].neighbours);
222 }
223 free(g->nodes);
224 free(g);
225 return;
226 }

  ViewVC Help
Powered by ViewVC 1.1.26