-/*
- * Structure nodes in graphs of nodes that had exchanges. Each graph has a
- * reference node, the one that can reach the others with the smallest
- * cummulative error.
- *
- * Args:
- * syncState: container for synchronization data.
- * This function allocates these analysisData members:
- * graphList
- */
-static void doGraphProcessing(SyncState* const syncState)
-{
- unsigned int i, j;
- double* distances;
- unsigned int* previousVertex;
- AnalysisDataLinReg* analysisData;
-
- analysisData= (AnalysisDataLinReg*) syncState->analysisData;
-
- distances= malloc(syncState->traceNb * sizeof(double));
- previousVertex= malloc(syncState->traceNb * sizeof(unsigned int));
- analysisData->graphList= g_queue_new();
-
- for (i= 0; i < syncState->traceNb; i++)
- {
- double errorSum;
- GList* result;
-
- // Perform shortest path search
- g_debug("shortest path trace %d, distances: ", i);
- shortestPath(analysisData->fitArray, i, syncState->traceNb, distances,
- previousVertex);
-
- for (j= 0; j < syncState->traceNb; j++)
- {
- g_debug("%g, ", distances[j]);
- }
- g_debug("previousVertex: ");
- for (j= 0; j < syncState->traceNb; j++)
- {
- g_debug("%u, ", previousVertex[j]);
- }
-
- // Group in graphs nodes that have exchanges
- errorSum= sumDistances(distances, syncState->traceNb);
- result= g_queue_find_custom(analysisData->graphList, &i,
- &gcfGraphTraceCompare);
- if (result != NULL)
- {
- Graph* graph;
-
- g_debug("found graph");
- graph= (Graph*) result->data;
- if (errorSum < graph->errorSum)
- {
- g_debug("new reference");
- graph->errorSum= errorSum;
- free(graph->previousVertex);
- graph->previousVertex= previousVertex;
- graph->reference= i;
- previousVertex= malloc(syncState->traceNb * sizeof(unsigned
- int));
- }
- }
- else
- {
- Graph* newGraph;
-
- g_debug("creating new graph");
- newGraph= malloc(sizeof(Graph));
- newGraph->errorSum= errorSum;
- newGraph->previousVertex= previousVertex;
- newGraph->reference= i;
- previousVertex= malloc(syncState->traceNb * sizeof(unsigned int));
-
- g_queue_push_tail(analysisData->graphList, newGraph);
- }
- }
-
- free(previousVertex);
- free(distances);
-}
-
-
-/*
- * Calculate the resulting offset and drift between each trace and its
- * reference.
- *
- * Args:
- * syncState: container for synchronization data.
- *
- * Returns:
- * Factors[traceNb] synchronization factors for each trace
- */
-static GArray* calculateFactors(SyncState* const syncState)
-{
- unsigned int i;
- AnalysisDataLinReg* analysisData;
- GArray* factors;
-
- analysisData= (AnalysisDataLinReg*) syncState->analysisData;
- factors= g_array_sized_new(FALSE, FALSE, sizeof(Factors),
- syncState->traceNb);
- g_array_set_size(factors, syncState->traceNb);
-
- // Calculate the resulting offset and drift between each trace and its
- // reference
- for (i= 0; i < syncState->traceNb; i++)
- {
- GList* result;
-
- result= g_queue_find_custom(analysisData->graphList, &i,
- &gcfGraphTraceCompare);
- if (result != NULL)
- {
- Graph* graph;
- double stDev;
- Factors* traceFactors;
-
- graph= (Graph*) result->data;
- traceFactors= &g_array_index(factors, Factors, i);
-
- reduceFactors(analysisData->fitArray, graph->previousVertex, i,
- &traceFactors->drift, &traceFactors->offset, &stDev);
-
- if (syncState->stats)
- {
- analysisData->stDev[i]= stDev;
- }
- }
- else
- {
- g_error("Trace %d not part of a graph\n", i);
- }
- }
-
- return factors;
-}
-
-
-/*
- * Single-source shortest path search to find the path with the lowest error to
- * convert one node's time to another.
- * Uses Dijkstra's algorithm
- *
- * Args:
- * fitArray: array with the regression parameters
- * traceNum: reference node
- * traceNb: number of traces = number of nodes
- * distances: array of computed distance from source node to node i,
- * INFINITY if i is unreachable, preallocated to the number of
- * nodes
- * previousVertex: previous vertex from a node i on the way to the source,
- * UINT_MAX if i is not on the way or is the source,
- * preallocated to the number of nodes
- */
-static void shortestPath(Fit* const* const fitArray, const unsigned int
- traceNum, const unsigned int traceNb, double* const distances, unsigned
- int* const previousVertex)
-{
- bool* visited;
- unsigned int i, j;
-
- visited= malloc(traceNb * sizeof(bool));
-
- for (i= 0; i < traceNb; i++)
- {
- const Fit* fit;
-
- visited[i]= false;
-
- fit= &fitArray[traceNum][i];
- g_debug("fitArray[traceNum= %u][i= %u]->n = %u", traceNum, i, fit->n);
- if (fit->n > 0)
- {
- distances[i]= fit->e;
- previousVertex[i]= traceNum;
- }
- else
- {
- distances[i]= INFINITY;
- previousVertex[i]= UINT_MAX;
- }
- }
- visited[traceNum]= true;
-
- for (j= 0; j < traceNb; j++)
- {
- g_debug("(%d, %u, %g), ", visited[j], previousVertex[j], distances[j]);
- }
-
- for (i= 0; i < traceNb - 2; i++)
- {
- unsigned int v;
- double dvMin;
-
- dvMin= INFINITY;
- for (j= 0; j < traceNb; j++)
- {
- if (visited[j] == false && distances[j] < dvMin)
- {
- v= j;
- dvMin= distances[j];
- }
- }
-
- g_debug("v= %u dvMin= %g", v, dvMin);
-
- if (dvMin != INFINITY)
- {
- visited[v]= true;
-
- for (j= 0; j < traceNb; j++)
- {
- const Fit* fit;
-
- fit= &fitArray[v][j];
- if (visited[j] == false && fit->n > 0 && distances[v] + fit->e
- < distances[j])
- {
- distances[j]= distances[v] + fit->e;
- previousVertex[j]= v;
- }
- }
- }
- else
- {
- break;
- }
-
- for (j= 0; j < traceNb; j++)
- {
- g_debug("(%d, %u, %g), ", visited[j], previousVertex[j], distances[j]);
- }
- }
-
- free(visited);
-}
-
-
-/*
- * Cummulate the distances between a reference node and the other nodes
- * reachable from it in a graph.
- *
- * Args:
- * distances: array of shortest path distances, with UINT_MAX for
- * unreachable nodes
- * traceNb: number of nodes = number of traces
- */
-static double sumDistances(const double* const distances, const unsigned int traceNb)
-{
- unsigned int i;
- double result;
-
- result= 0;
- for (i= 0; i < traceNb; i++)
- {
- if (distances[i] != INFINITY)
- {
- result+= distances[i];
- }
- }
-
- return result;
-}
-
-
-/*
- * Cummulate the time correction factors between two nodes accross a graph
- *
- * With traceNum i, reference node r:
- * tr= (1 + Xri) * ti + D0ri
- * = drift * ti + offset
- *
- * Args:
- * fitArray: array with the regression parameters
- * previousVertex: previous vertex from a node i on the way to the source,
- * UINT_MAX if i is not on the way or is the source,
- * preallocated to the number of nodes
- * traceNum: end node, the reference depends on previousVertex
- * drift: drift factor
- * offset: offset factor
- */
-static void reduceFactors(Fit* const* const fitArray, const unsigned int* const
- previousVertex, const unsigned int traceNum, double* const drift, double*
- const offset, double* const stDev)
-{
- if (previousVertex[traceNum] == UINT_MAX)
- {
- *drift= 1.;
- *offset= 0.;
- *stDev= 0.;
- }
- else
- {
- const Fit* fit;
- double cummDrift, cummOffset, cummStDev;
- unsigned int pv;
-
- pv= previousVertex[traceNum];
-
- fit= &fitArray[pv][traceNum];
- reduceFactors(fitArray, previousVertex, pv, &cummDrift, &cummOffset,
- &cummStDev);
-
- *drift= cummDrift * (1 + fit->x);
- *offset= cummDrift * fit->d0 + cummOffset;
- *stDev= fit->x * cummStDev + fit->e;
- }
-}
-
-
-/*
- * A GFunc for g_queue_foreach()
- *
- * Args:
- * data Graph*, graph to destroy
- * user_data NULL
- */
-static void gfGraphDestroy(gpointer data, gpointer user_data)
-{
- Graph* graph;
-
- graph= (Graph*) data;
-
- free(graph->previousVertex);
- free(graph);
-}
-
-
-/*
- * A GCompareFunc for g_queue_find_custom()
- *
- * Args:
- * a: Graph* graph
- * b: unsigned int* traceNum
- *
- * Returns:
- * 0 if graph contains traceNum
- */
-static gint gcfGraphTraceCompare(gconstpointer a, gconstpointer b)
-{
- Graph* graph;
- unsigned int traceNum;
-
- graph= (Graph*) a;
- traceNum= *(unsigned int *) b;
-
- if (graph->previousVertex[traceNum] != UINT_MAX)
- {
- return 0;
- }
- else if (graph->reference == traceNum)
- {
- return 0;
- }
- else
- {
- return 1;
- }
-}
-
-