Commit | Line | Data |
---|---|---|
70407e86 | 1 | /* This file is part of the Linux Trace Toolkit viewer |
277e5b53 | 2 | * Copyright (C) 2009, 2010 Benjamin Poirier <benjamin.poirier@polymtl.ca> |
70407e86 | 3 | * |
277e5b53 BP |
4 | * This program is free software: you can redistribute it and/or modify it |
5 | * under the terms of the GNU Lesser General Public License as published by | |
6 | * the Free Software Foundation, either version 2.1 of the License, or (at | |
7 | * your option) any later version. | |
70407e86 | 8 | * |
277e5b53 BP |
9 | * This program is distributed in the hope that it will be useful, but WITHOUT |
10 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
11 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public | |
12 | * License for more details. | |
70407e86 | 13 | * |
277e5b53 BP |
14 | * You should have received a copy of the GNU Lesser General Public License |
15 | * along with this program. If not, see <http://www.gnu.org/licenses/>. | |
70407e86 BP |
16 | */ |
17 | ||
18 | // for INFINITY in math.h | |
19 | #define _ISOC99_SOURCE | |
20 | ||
21 | #ifdef HAVE_CONFIG_H | |
22 | #include <config.h> | |
23 | #endif | |
24 | ||
25 | #include <math.h> | |
26 | #include <stdio.h> | |
27 | #include <stdlib.h> | |
28 | ||
2bd4b3e4 | 29 | #include "sync_chain.h" |
70407e86 BP |
30 | |
31 | #include "event_analysis_linreg.h" | |
32 | ||
33 | ||
70407e86 BP |
34 | // Functions common to all analysis modules |
35 | static void initAnalysisLinReg(SyncState* const syncState); | |
36 | static void destroyAnalysisLinReg(SyncState* const syncState); | |
37 | ||
10341d26 | 38 | static void analyzeExchangeLinReg(SyncState* const syncState, Exchange* const exchange); |
70407e86 BP |
39 | static GArray* finalizeAnalysisLinReg(SyncState* const syncState); |
40 | static void printAnalysisStatsLinReg(SyncState* const syncState); | |
8d7d16dd BP |
41 | static void writeAnalysisGraphsPlotsLinReg(SyncState* const syncState, const |
42 | unsigned int i, const unsigned int j); | |
70407e86 BP |
43 | |
44 | // Functions specific to this module | |
70407e86 BP |
45 | static void finalizeLSA(SyncState* const syncState); |
46 | static void doGraphProcessing(SyncState* const syncState); | |
47 | static GArray* calculateFactors(SyncState* const syncState); | |
48 | static void shortestPath(Fit* const* const fitArray, const unsigned int | |
49 | traceNum, const unsigned int traceNb, double* const distances, | |
50 | unsigned int* const previousVertex); | |
51 | static double sumDistances(const double* const distances, const unsigned int | |
52 | traceNb); | |
53 | static void reduceFactors(Fit* const* const fitArray, const unsigned int* const | |
54 | previousVertex, const unsigned int traceNum, double* const drift, | |
55 | double* const offset, double* const stDev); | |
56 | ||
57 | // Graph-related Glib functions | |
58 | static void gfGraphDestroy(gpointer data, gpointer user_data); | |
59 | static gint gcfGraphTraceCompare(gconstpointer a, gconstpointer b); | |
60 | ||
61 | ||
62 | static AnalysisModule analysisModuleLinReg= { | |
63 | .name= "linreg", | |
64 | .initAnalysis= &initAnalysisLinReg, | |
65 | .destroyAnalysis= &destroyAnalysisLinReg, | |
70407e86 BP |
66 | .analyzeExchange= &analyzeExchangeLinReg, |
67 | .finalizeAnalysis= &finalizeAnalysisLinReg, | |
68 | .printAnalysisStats= &printAnalysisStatsLinReg, | |
467066ee | 69 | .graphFunctions= { |
c6356aa7 | 70 | .writeTraceTraceForePlots= &writeAnalysisGraphsPlotsLinReg, |
467066ee | 71 | } |
70407e86 BP |
72 | }; |
73 | ||
74 | ||
75 | /* | |
76 | * Analysis module registering function | |
77 | */ | |
2f961b65 | 78 | void registerAnalysisLinReg() |
70407e86 BP |
79 | { |
80 | g_queue_push_tail(&analysisModules, &analysisModuleLinReg); | |
81 | } | |
82 | ||
83 | ||
84 | /* | |
85 | * Analysis init function | |
86 | * | |
87 | * This function is called at the beginning of a synchronization run for a set | |
88 | * of traces. | |
89 | * | |
90 | * Allocate some of the analysis specific data structures | |
91 | * | |
92 | * Args: | |
93 | * syncState container for synchronization data. | |
94 | * This function allocates these analysisData members: | |
95 | * fitArray | |
96 | * stDev | |
97 | */ | |
98 | static void initAnalysisLinReg(SyncState* const syncState) | |
99 | { | |
100 | unsigned int i; | |
101 | AnalysisDataLinReg* analysisData; | |
102 | ||
103 | analysisData= malloc(sizeof(AnalysisDataLinReg)); | |
104 | syncState->analysisData= analysisData; | |
105 | ||
106 | analysisData->fitArray= malloc(syncState->traceNb * sizeof(Fit*)); | |
107 | for (i= 0; i < syncState->traceNb; i++) | |
108 | { | |
109 | analysisData->fitArray[i]= calloc(syncState->traceNb, sizeof(Fit)); | |
110 | } | |
111 | ||
112 | if (syncState->stats) | |
113 | { | |
114 | analysisData->stDev= malloc(sizeof(double) * syncState->traceNb); | |
115 | } | |
116 | } | |
117 | ||
118 | ||
119 | /* | |
120 | * Analysis destroy function | |
121 | * | |
122 | * Free the analysis specific data structures | |
123 | * | |
124 | * Args: | |
125 | * syncState container for synchronization data. | |
126 | * This function deallocates these analysisData members: | |
127 | * fitArray | |
128 | * graphList | |
129 | * stDev | |
130 | */ | |
131 | static void destroyAnalysisLinReg(SyncState* const syncState) | |
132 | { | |
133 | unsigned int i; | |
134 | AnalysisDataLinReg* analysisData; | |
135 | ||
136 | analysisData= (AnalysisDataLinReg*) syncState->analysisData; | |
137 | ||
138 | if (analysisData == NULL) | |
139 | { | |
140 | return; | |
141 | } | |
142 | ||
143 | for (i= 0; i < syncState->traceNb; i++) | |
144 | { | |
145 | free(analysisData->fitArray[i]); | |
146 | } | |
147 | free(analysisData->fitArray); | |
148 | ||
149 | g_queue_foreach(analysisData->graphList, &gfGraphDestroy, NULL); | |
150 | g_queue_free(analysisData->graphList); | |
151 | ||
152 | if (syncState->stats) | |
153 | { | |
154 | free(analysisData->stDev); | |
155 | } | |
156 | ||
157 | free(syncState->analysisData); | |
158 | syncState->analysisData= NULL; | |
159 | } | |
160 | ||
161 | ||
162 | /* | |
163 | * Perform analysis on a series of event pairs. | |
164 | * | |
70407e86 BP |
165 | * Args: |
166 | * syncState container for synchronization data | |
10341d26 | 167 | * exchange structure containing the many events |
70407e86 | 168 | */ |
10341d26 | 169 | static void analyzeExchangeLinReg(SyncState* const syncState, Exchange* const exchange) |
70407e86 BP |
170 | { |
171 | unsigned int ni, nj; | |
172 | double dji, eji; | |
173 | double timoy; | |
174 | Fit* fit; | |
10341d26 | 175 | Message* ackedMessage; |
70407e86 BP |
176 | AnalysisDataLinReg* analysisData; |
177 | ||
d5b038ec BP |
178 | g_debug("Synchronization calculation, " |
179 | "%d acked packets - using last one,", | |
10341d26 | 180 | g_queue_get_length(exchange->acks)); |
70407e86 BP |
181 | |
182 | analysisData= (AnalysisDataLinReg*) syncState->analysisData; | |
10341d26 | 183 | ackedMessage= g_queue_peek_tail(exchange->acks); |
70407e86 BP |
184 | |
185 | // Calculate the intermediate values for the | |
186 | // least-squares analysis | |
76be6fc2 BP |
187 | dji= ((double) ackedMessage->inE->cpuTime - (double) ackedMessage->outE->cpuTime |
188 | + (double) exchange->message->outE->cpuTime - (double) | |
189 | exchange->message->inE->cpuTime) / 2; | |
190 | eji= fabs((double) ackedMessage->inE->cpuTime - (double) | |
191 | ackedMessage->outE->cpuTime - (double) exchange->message->outE->cpuTime + | |
192 | (double) exchange->message->inE->cpuTime) / 2; | |
193 | timoy= ((double) ackedMessage->outE->cpuTime + (double) | |
194 | exchange->message->inE->cpuTime) / 2; | |
10341d26 BP |
195 | ni= ackedMessage->outE->traceNum; |
196 | nj= ackedMessage->inE->traceNum; | |
70407e86 BP |
197 | fit= &analysisData->fitArray[nj][ni]; |
198 | ||
199 | fit->n++; | |
200 | fit->st+= timoy; | |
201 | fit->st2+= pow(timoy, 2); | |
202 | fit->sd+= dji; | |
203 | fit->sd2+= pow(dji, 2); | |
204 | fit->std+= timoy * dji; | |
205 | ||
206 | g_debug("intermediate values: dji= %f ti moy= %f " | |
207 | "ni= %u nj= %u fit: n= %u st= %f st2= %f sd= %f " | |
208 | "sd2= %f std= %f, ", dji, timoy, ni, nj, fit->n, | |
209 | fit->st, fit->st2, fit->sd, fit->sd2, fit->std); | |
210 | } | |
211 | ||
212 | ||
213 | /* | |
214 | * Finalize the factor calculations | |
215 | * | |
216 | * The least squares analysis is finalized and finds the factors directly | |
217 | * between each pair of traces that had events together. The traces are | |
218 | * aranged in a graph, a reference trace is chosen and the factors between | |
219 | * this reference and every other trace is calculated. Sometimes it is | |
220 | * necessary to use many graphs when there are "islands" of independent | |
221 | * traces. | |
222 | * | |
223 | * Args: | |
224 | * syncState container for synchronization data. | |
225 | * | |
226 | * Returns: | |
227 | * Factors[traceNb] synchronization factors for each trace | |
228 | */ | |
229 | static GArray* finalizeAnalysisLinReg(SyncState* const syncState) | |
230 | { | |
231 | GArray* factors; | |
232 | ||
233 | // Finalize the processing | |
234 | finalizeLSA(syncState); | |
235 | ||
236 | // Find a reference node and structure nodes in a graph | |
237 | doGraphProcessing(syncState); | |
238 | ||
239 | /* Calculate the resulting offset and drift between each trace and its | |
240 | * reference | |
241 | */ | |
242 | factors= calculateFactors(syncState); | |
243 | ||
244 | return factors; | |
245 | } | |
246 | ||
247 | ||
248 | /* | |
249 | * Print statistics related to analysis. Must be called after | |
250 | * finalizeAnalysis. | |
251 | * | |
252 | * Args: | |
253 | * syncState container for synchronization data. | |
254 | */ | |
255 | static void printAnalysisStatsLinReg(SyncState* const syncState) | |
256 | { | |
257 | unsigned int i, j; | |
258 | AnalysisDataLinReg* analysisData; | |
259 | ||
260 | if (!syncState->stats) | |
261 | { | |
262 | return; | |
263 | } | |
264 | ||
265 | analysisData= (AnalysisDataLinReg*) syncState->analysisData; | |
266 | ||
267 | printf("Linear regression analysis stats:\n"); | |
268 | ||
269 | printf("\tIndividual synchronization factors:\n"); | |
270 | ||
271 | for (j= 0; j < syncState->traceNb; j++) | |
272 | { | |
273 | for (i= 0; i < j; i++) | |
274 | { | |
275 | Fit* fit; | |
276 | ||
277 | fit= &analysisData->fitArray[j][i]; | |
278 | printf("\t\t%3d - %-3d: ", i, j); | |
279 | printf("a0= % 7g a1= 1 %c %7g accuracy %7g\n", fit->d0, fit->x < | |
280 | 0. ? '-' : '+', fabs(fit->x), fit->e); | |
281 | ||
282 | fit= &analysisData->fitArray[i][j]; | |
283 | printf("\t\t%3d - %-3d: ", j, i); | |
284 | printf("a0= % 7g a1= 1 %c %7g accuracy %7g\n", fit->d0, fit->x < | |
285 | 0. ? '-' : '+', fabs(fit->x), fit->e); | |
286 | } | |
287 | } | |
288 | ||
289 | printf("\tTree:\n"); | |
290 | for (i= 0; i < syncState->traceNb; i++) | |
291 | { | |
292 | GList* result; | |
293 | ||
294 | result= g_queue_find_custom(analysisData->graphList, &i, | |
295 | &gcfGraphTraceCompare); | |
296 | if (result != NULL) | |
297 | { | |
298 | Graph* graph; | |
299 | ||
300 | graph= (Graph*) result->data; | |
301 | ||
302 | printf("\t\ttrace %u reference %u previous vertex ", i, | |
303 | graph->reference); | |
304 | ||
305 | if (i == graph->reference) | |
306 | { | |
307 | printf("- "); | |
308 | } | |
309 | else | |
310 | { | |
311 | printf("%u ", graph->previousVertex[i]); | |
312 | } | |
313 | ||
314 | printf("stdev= %g\n", analysisData->stDev[i]); | |
315 | } | |
316 | else | |
317 | { | |
318 | g_error("Trace %d not part of a graph\n", i); | |
319 | } | |
320 | } | |
321 | } | |
322 | ||
323 | ||
324 | /* | |
325 | * Finalize the least-squares analysis. The intermediate values in the fit | |
326 | * array are used to calculate the drift and the offset between each pair of | |
327 | * nodes based on their exchanges. | |
328 | * | |
329 | * Args: | |
330 | * syncState: container for synchronization data. | |
331 | */ | |
332 | static void finalizeLSA(SyncState* const syncState) | |
333 | { | |
334 | unsigned int i, j; | |
335 | AnalysisDataLinReg* analysisData; | |
336 | ||
337 | analysisData= (AnalysisDataLinReg*) syncState->analysisData; | |
338 | ||
339 | for (i= 0; i < syncState->traceNb; i++) | |
340 | { | |
341 | for (j= 0; j < syncState->traceNb; j++) | |
342 | { | |
343 | if (i != j) | |
344 | { | |
345 | Fit* fit; | |
346 | double delta; | |
347 | ||
348 | fit= &analysisData->fitArray[i][j]; | |
349 | ||
350 | delta= fit->n * fit->st2 - pow(fit->st, 2); | |
351 | fit->x= (fit->n * fit->std - fit->st * fit->sd) / delta; | |
352 | fit->d0= (fit->st2 * fit->sd - fit->st * fit->std) / delta; | |
353 | fit->e= sqrt((fit->sd2 - (fit->n * pow(fit->std, 2) + | |
354 | pow(fit->sd, 2) * fit->st2 - 2 * fit->st * fit->sd | |
355 | * fit->std) / delta) / (fit->n - 2)); | |
356 | ||
d5b038ec BP |
357 | g_debug("[i= %u j= %u]", i, j); |
358 | g_debug("n= %d st= %g st2= %g sd= %g sd2= %g std= %g", | |
70407e86 | 359 | fit->n, fit->st, fit->st2, fit->sd, fit->sd2, fit->std); |
d5b038ec BP |
360 | g_debug("xij= %g d0ij= %g e= %g", fit->x, fit->d0, fit->e); |
361 | g_debug("(xji= %g d0ji= %g)", -fit->x / (1 + fit->x), | |
70407e86 BP |
362 | -fit->d0 / (1 + fit->x)); |
363 | } | |
364 | } | |
365 | } | |
366 | } | |
367 | ||
368 | ||
369 | /* | |
370 | * Structure nodes in graphs of nodes that had exchanges. Each graph has a | |
371 | * reference node, the one that can reach the others with the smallest | |
372 | * cummulative error. | |
373 | * | |
374 | * Args: | |
375 | * syncState: container for synchronization data. | |
376 | * This function allocates these analysisData members: | |
377 | * graphList | |
378 | */ | |
379 | static void doGraphProcessing(SyncState* const syncState) | |
380 | { | |
381 | unsigned int i, j; | |
382 | double* distances; | |
383 | unsigned int* previousVertex; | |
384 | AnalysisDataLinReg* analysisData; | |
385 | ||
386 | analysisData= (AnalysisDataLinReg*) syncState->analysisData; | |
387 | ||
388 | distances= malloc(syncState->traceNb * sizeof(double)); | |
389 | previousVertex= malloc(syncState->traceNb * sizeof(unsigned int)); | |
390 | analysisData->graphList= g_queue_new(); | |
391 | ||
392 | for (i= 0; i < syncState->traceNb; i++) | |
393 | { | |
394 | double errorSum; | |
395 | GList* result; | |
396 | ||
397 | // Perform shortest path search | |
d5b038ec | 398 | g_debug("shortest path trace %d, distances: ", i); |
70407e86 BP |
399 | shortestPath(analysisData->fitArray, i, syncState->traceNb, distances, |
400 | previousVertex); | |
401 | ||
402 | for (j= 0; j < syncState->traceNb; j++) | |
403 | { | |
404 | g_debug("%g, ", distances[j]); | |
405 | } | |
d5b038ec | 406 | g_debug("previousVertex: "); |
70407e86 BP |
407 | for (j= 0; j < syncState->traceNb; j++) |
408 | { | |
409 | g_debug("%u, ", previousVertex[j]); | |
410 | } | |
70407e86 BP |
411 | |
412 | // Group in graphs nodes that have exchanges | |
413 | errorSum= sumDistances(distances, syncState->traceNb); | |
414 | result= g_queue_find_custom(analysisData->graphList, &i, | |
415 | &gcfGraphTraceCompare); | |
416 | if (result != NULL) | |
417 | { | |
418 | Graph* graph; | |
419 | ||
d5b038ec | 420 | g_debug("found graph"); |
70407e86 BP |
421 | graph= (Graph*) result->data; |
422 | if (errorSum < graph->errorSum) | |
423 | { | |
d5b038ec | 424 | g_debug("adding to graph"); |
70407e86 BP |
425 | graph->errorSum= errorSum; |
426 | free(graph->previousVertex); | |
427 | graph->previousVertex= previousVertex; | |
428 | graph->reference= i; | |
429 | previousVertex= malloc(syncState->traceNb * sizeof(unsigned | |
430 | int)); | |
431 | } | |
432 | } | |
433 | else | |
434 | { | |
435 | Graph* newGraph; | |
436 | ||
d5b038ec | 437 | g_debug("creating new graph"); |
70407e86 BP |
438 | newGraph= malloc(sizeof(Graph)); |
439 | newGraph->errorSum= errorSum; | |
440 | newGraph->previousVertex= previousVertex; | |
441 | newGraph->reference= i; | |
442 | previousVertex= malloc(syncState->traceNb * sizeof(unsigned int)); | |
443 | ||
444 | g_queue_push_tail(analysisData->graphList, newGraph); | |
445 | } | |
446 | } | |
447 | ||
448 | free(previousVertex); | |
449 | free(distances); | |
450 | } | |
451 | ||
452 | ||
453 | /* | |
454 | * Calculate the resulting offset and drift between each trace and its | |
455 | * reference. | |
456 | * | |
457 | * Args: | |
458 | * syncState: container for synchronization data. | |
459 | * | |
460 | * Returns: | |
461 | * Factors[traceNb] synchronization factors for each trace | |
462 | */ | |
463 | static GArray* calculateFactors(SyncState* const syncState) | |
464 | { | |
465 | unsigned int i; | |
466 | AnalysisDataLinReg* analysisData; | |
467 | GArray* factors; | |
468 | ||
469 | analysisData= (AnalysisDataLinReg*) syncState->analysisData; | |
470 | factors= g_array_sized_new(FALSE, FALSE, sizeof(Factors), | |
471 | syncState->traceNb); | |
08365995 | 472 | g_array_set_size(factors, syncState->traceNb); |
70407e86 BP |
473 | |
474 | // Calculate the resulting offset and drift between each trace and its | |
475 | // reference | |
476 | for (i= 0; i < syncState->traceNb; i++) | |
477 | { | |
478 | GList* result; | |
479 | ||
480 | result= g_queue_find_custom(analysisData->graphList, &i, | |
481 | &gcfGraphTraceCompare); | |
482 | if (result != NULL) | |
483 | { | |
484 | Graph* graph; | |
485 | double stDev; | |
486 | Factors* traceFactors; | |
487 | ||
488 | graph= (Graph*) result->data; | |
489 | traceFactors= &g_array_index(factors, Factors, i); | |
490 | ||
491 | reduceFactors(analysisData->fitArray, graph->previousVertex, i, | |
492 | &traceFactors->drift, &traceFactors->offset, &stDev); | |
493 | ||
494 | if (syncState->stats) | |
495 | { | |
496 | analysisData->stDev[i]= stDev; | |
497 | } | |
498 | } | |
499 | else | |
500 | { | |
501 | g_error("Trace %d not part of a graph\n", i); | |
502 | } | |
503 | } | |
504 | ||
505 | return factors; | |
506 | } | |
507 | ||
508 | ||
509 | /* | |
510 | * Single-source shortest path search to find the path with the lowest error to | |
511 | * convert one node's time to another. | |
512 | * Uses Dijkstra's algorithm | |
513 | * | |
514 | * Args: | |
515 | * fitArray: array with the regression parameters | |
516 | * traceNum: reference node | |
517 | * traceNb: number of traces = number of nodes | |
518 | * distances: array of computed distance from source node to node i, | |
519 | * INFINITY if i is unreachable, preallocated to the number of | |
520 | * nodes | |
521 | * previousVertex: previous vertex from a node i on the way to the source, | |
522 | * UINT_MAX if i is not on the way or is the source, | |
523 | * preallocated to the number of nodes | |
524 | */ | |
525 | static void shortestPath(Fit* const* const fitArray, const unsigned int | |
526 | traceNum, const unsigned int traceNb, double* const distances, unsigned | |
527 | int* const previousVertex) | |
528 | { | |
529 | bool* visited; | |
530 | unsigned int i, j; | |
531 | ||
532 | visited= malloc(traceNb * sizeof(bool)); | |
533 | ||
534 | for (i= 0; i < traceNb; i++) | |
535 | { | |
536 | const Fit* fit; | |
537 | ||
538 | visited[i]= false; | |
539 | ||
540 | fit= &fitArray[traceNum][i]; | |
d5b038ec | 541 | g_debug("fitArray[traceNum= %u][i= %u]->n = %u", traceNum, i, fit->n); |
70407e86 BP |
542 | if (fit->n > 0) |
543 | { | |
544 | distances[i]= fit->e; | |
545 | previousVertex[i]= traceNum; | |
546 | } | |
547 | else | |
548 | { | |
549 | distances[i]= INFINITY; | |
550 | previousVertex[i]= UINT_MAX; | |
551 | } | |
552 | } | |
553 | visited[traceNum]= true; | |
554 | ||
555 | for (j= 0; j < traceNb; j++) | |
556 | { | |
557 | g_debug("(%d, %u, %g), ", visited[j], previousVertex[j], distances[j]); | |
558 | } | |
70407e86 BP |
559 | |
560 | for (i= 0; i < traceNb - 2; i++) | |
561 | { | |
562 | unsigned int v; | |
563 | double dvMin; | |
564 | ||
565 | dvMin= INFINITY; | |
566 | for (j= 0; j < traceNb; j++) | |
567 | { | |
568 | if (visited[j] == false && distances[j] < dvMin) | |
569 | { | |
570 | v= j; | |
571 | dvMin= distances[j]; | |
572 | } | |
573 | } | |
574 | ||
d5b038ec | 575 | g_debug("v= %u dvMin= %g", v, dvMin); |
70407e86 BP |
576 | |
577 | if (dvMin != INFINITY) | |
578 | { | |
579 | visited[v]= true; | |
580 | ||
581 | for (j= 0; j < traceNb; j++) | |
582 | { | |
583 | const Fit* fit; | |
584 | ||
585 | fit= &fitArray[v][j]; | |
586 | if (visited[j] == false && fit->n > 0 && distances[v] + fit->e | |
587 | < distances[j]) | |
588 | { | |
589 | distances[j]= distances[v] + fit->e; | |
590 | previousVertex[j]= v; | |
591 | } | |
592 | } | |
593 | } | |
594 | else | |
595 | { | |
596 | break; | |
597 | } | |
598 | ||
599 | for (j= 0; j < traceNb; j++) | |
600 | { | |
601 | g_debug("(%d, %u, %g), ", visited[j], previousVertex[j], distances[j]); | |
602 | } | |
70407e86 BP |
603 | } |
604 | ||
605 | free(visited); | |
606 | } | |
607 | ||
608 | ||
609 | /* | |
610 | * Cummulate the distances between a reference node and the other nodes | |
611 | * reachable from it in a graph. | |
612 | * | |
613 | * Args: | |
614 | * distances: array of shortest path distances, with UINT_MAX for | |
615 | * unreachable nodes | |
616 | * traceNb: number of nodes = number of traces | |
617 | */ | |
618 | static double sumDistances(const double* const distances, const unsigned int traceNb) | |
619 | { | |
620 | unsigned int i; | |
621 | double result; | |
622 | ||
623 | result= 0; | |
624 | for (i= 0; i < traceNb; i++) | |
625 | { | |
626 | if (distances[i] != INFINITY) | |
627 | { | |
628 | result+= distances[i]; | |
629 | } | |
630 | } | |
631 | ||
632 | return result; | |
633 | } | |
634 | ||
635 | ||
636 | /* | |
637 | * Cummulate the time correction factors between two nodes accross a graph | |
638 | * | |
639 | * With traceNum i, reference node r: | |
640 | * tr= (1 + Xri) * ti + D0ri | |
641 | * = drift * ti + offset | |
642 | * | |
643 | * Args: | |
644 | * fitArray: array with the regression parameters | |
645 | * previousVertex: previous vertex from a node i on the way to the source, | |
646 | * UINT_MAX if i is not on the way or is the source, | |
647 | * preallocated to the number of nodes | |
648 | * traceNum: end node, the reference depends on previousVertex | |
649 | * drift: drift factor | |
650 | * offset: offset factor | |
651 | */ | |
652 | static void reduceFactors(Fit* const* const fitArray, const unsigned int* const | |
653 | previousVertex, const unsigned int traceNum, double* const drift, double* | |
654 | const offset, double* const stDev) | |
655 | { | |
656 | if (previousVertex[traceNum] == UINT_MAX) | |
657 | { | |
658 | *drift= 1.; | |
659 | *offset= 0.; | |
660 | *stDev= 0.; | |
661 | } | |
662 | else | |
663 | { | |
664 | const Fit* fit; | |
665 | double cummDrift, cummOffset, cummStDev; | |
666 | unsigned int pv; | |
667 | ||
668 | pv= previousVertex[traceNum]; | |
669 | ||
670 | fit= &fitArray[pv][traceNum]; | |
671 | reduceFactors(fitArray, previousVertex, pv, &cummDrift, &cummOffset, | |
672 | &cummStDev); | |
673 | ||
674 | *drift= cummDrift * (1 + fit->x); | |
675 | *offset= cummDrift * fit->d0 + cummOffset; | |
676 | *stDev= fit->x * cummStDev + fit->e; | |
677 | } | |
678 | } | |
679 | ||
680 | ||
681 | /* | |
682 | * A GFunc for g_queue_foreach() | |
683 | * | |
684 | * Args: | |
685 | * data Graph*, graph to destroy | |
686 | * user_data NULL | |
687 | */ | |
688 | static void gfGraphDestroy(gpointer data, gpointer user_data) | |
689 | { | |
690 | Graph* graph; | |
691 | ||
692 | graph= (Graph*) data; | |
693 | ||
694 | free(graph->previousVertex); | |
695 | free(graph); | |
696 | } | |
697 | ||
698 | ||
699 | /* | |
700 | * A GCompareFunc for g_queue_find_custom() | |
701 | * | |
702 | * Args: | |
703 | * a: Graph* graph | |
704 | * b: unsigned int* traceNum | |
705 | * | |
706 | * Returns: | |
707 | * 0 if graph contains traceNum | |
708 | */ | |
709 | static gint gcfGraphTraceCompare(gconstpointer a, gconstpointer b) | |
710 | { | |
711 | Graph* graph; | |
712 | unsigned int traceNum; | |
713 | ||
714 | graph= (Graph*) a; | |
715 | traceNum= *(unsigned int *) b; | |
716 | ||
717 | if (graph->previousVertex[traceNum] != UINT_MAX) | |
718 | { | |
719 | return 0; | |
720 | } | |
721 | else if (graph->reference == traceNum) | |
722 | { | |
723 | return 0; | |
724 | } | |
725 | else | |
726 | { | |
727 | return 1; | |
728 | } | |
729 | } | |
730 | ||
08365995 BP |
731 | |
732 | /* | |
733 | * Write the analysis-specific graph lines in the gnuplot script. | |
734 | * | |
735 | * Args: | |
08365995 BP |
736 | * syncState: container for synchronization data |
737 | * i: first trace number, on the x axis | |
738 | * j: second trace number, garanteed to be larger than i | |
739 | */ | |
8d7d16dd BP |
740 | void writeAnalysisGraphsPlotsLinReg(SyncState* const syncState, const unsigned |
741 | int i, const unsigned int j) | |
08365995 BP |
742 | { |
743 | AnalysisDataLinReg* analysisData; | |
744 | Fit* fit; | |
745 | ||
746 | analysisData= (AnalysisDataLinReg*) syncState->analysisData; | |
747 | fit= &analysisData->fitArray[j][i]; | |
748 | ||
8d7d16dd | 749 | fprintf(syncState->graphsStream, |
08365995 BP |
750 | "\t%7g + %7g * x " |
751 | "title \"Linreg conversion\" with lines " | |
752 | "linecolor rgb \"gray60\" linetype 1, \\\n", | |
753 | fit->d0, 1. + fit->x); | |
754 | } |