130 lines
3.3 KiB
C
130 lines
3.3 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <pthread.h>
|
|
|
|
#include "routing4SITA.h"
|
|
|
|
pthread_mutex_t mutex;
|
|
|
|
void *Search(void* arguments);
|
|
|
|
int main() {
|
|
printf("hello world!\n");
|
|
|
|
pthread_mutex_init (&mutex, NULL);
|
|
|
|
pthread_t startThread;
|
|
THREAD_DATA_t* data;
|
|
data = (THREAD_DATA_t*) malloc(sizeof(THREAD_DATA_t));
|
|
data->node = getStartNode();
|
|
data->cost = 0;
|
|
data->depth = 0;
|
|
data->predecessors[0] = data->node->id;
|
|
data->bestpath = (BESTPATH_t*) malloc(sizeof(BESTPATH_t));
|
|
data->bestpath->lowestCost = -1;
|
|
data->bestpath->depth = 0;
|
|
|
|
pthread_create(&startThread, NULL, Search, data);
|
|
pthread_join(startThread, NULL);
|
|
|
|
printf("\nBest Path: %i", data->bestpath->predecessorsBestPath[0]);
|
|
for(int i = 1; i <= data->bestpath->depth; i++) {
|
|
printf(" --> %i", data->bestpath->predecessorsBestPath[i]);
|
|
}
|
|
printf("\nWith cost of: %i\n", data->bestpath->lowestCost);
|
|
|
|
for(;;) {
|
|
|
|
}
|
|
|
|
return 0;
|
|
}
|
|
|
|
|
|
void *Search(void* arguments) {
|
|
|
|
THREAD_DATA_t *data = (THREAD_DATA_t*) arguments;
|
|
|
|
//printf("Number: %i\n", data->node->id);
|
|
//printf("Cost to this node: %i\n", data->cost);
|
|
|
|
if(data->node->id == 8) {
|
|
//printf("!!!End found! Cost: %i\n", data->cost);
|
|
|
|
//critical section start
|
|
pthread_mutex_lock (&mutex);
|
|
|
|
if(data->bestpath->lowestCost == -1) {
|
|
//first solution found
|
|
// printf("first solution found! %i\n", data->depth);
|
|
data->bestpath->lowestCost = data->cost;
|
|
data->bestpath->depth = data->depth;
|
|
for(int j = 0; j < data->depth; j++) {
|
|
data->bestpath->predecessorsBestPath[j] = data->predecessors[j];
|
|
}
|
|
data->bestpath->predecessorsBestPath[(data->bestpath->depth)] = data->node->id;
|
|
} else {
|
|
|
|
if(data->bestpath->lowestCost > data->cost) {
|
|
//new best solution found
|
|
//printf("new best solution found! %i\n", data->depth);
|
|
data->bestpath->lowestCost = data->cost;
|
|
data->bestpath->depth = data->depth;
|
|
for(int j = 0; j < data->depth; j++) {
|
|
data->bestpath->predecessorsBestPath[j] = data->predecessors[j];
|
|
}
|
|
data->bestpath->predecessorsBestPath[(data->bestpath->depth)] = data->node->id;
|
|
}
|
|
}
|
|
|
|
//critical section end
|
|
pthread_mutex_unlock (&mutex);
|
|
return NULL;
|
|
}
|
|
|
|
if(data->node->nodescount == 0) {
|
|
// printf("No next nodes\n");
|
|
return NULL;
|
|
}
|
|
|
|
pthread_t threads[data->node->nodescount];
|
|
|
|
for(int i = 0; i < data->node->nodescount; i++) {
|
|
THREAD_DATA_t* nextdata;
|
|
nextdata = (THREAD_DATA_t*) malloc(sizeof(THREAD_DATA_t));
|
|
nextdata->node = (data->node->nodesnext[i]);
|
|
nextdata->bestpath = data->bestpath;
|
|
nextdata->cost = data->node->nodescost[i] + data->cost;
|
|
nextdata->depth = data->depth + 1;
|
|
|
|
for(int j = 0; j < data->depth; j++) {
|
|
nextdata->predecessors[j] = data->predecessors[j];
|
|
}
|
|
nextdata->predecessors[((nextdata->depth) - 1)] = data->node->id;
|
|
pthread_create(&threads[i], NULL, Search, nextdata);
|
|
}
|
|
|
|
for(int i = 0; i < data->node->nodescount; i++) {
|
|
pthread_join(threads[i],NULL);
|
|
}
|
|
|
|
return NULL;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|