diff options
Diffstat (limited to 'dis/Transitive/transitive.c')
| -rw-r--r-- | dis/Transitive/transitive.c | 57 |
1 files changed, 29 insertions, 28 deletions
diff --git a/dis/Transitive/transitive.c b/dis/Transitive/transitive.c index 51805a6..9337aad 100644 --- a/dis/Transitive/transitive.c +++ b/dis/Transitive/transitive.c | |||
| @@ -61,42 +61,43 @@ int main(int argc, char **argv) { | |||
| 61 | if ((dout = (unsigned int *)malloc(n * n * sizeof(unsigned int))) == NULL) | 61 | if ((dout = (unsigned int *)malloc(n * n * sizeof(unsigned int))) == NULL) |
| 62 | return (-1); | 62 | return (-1); |
| 63 | 63 | ||
| 64 | for (i = 0; i < n * n; i++) { | 64 | SET_UP |
| 65 | *(din + i) = NO_PATH; | ||
| 66 | *(dout + i) = NO_PATH; | ||
| 67 | } | ||
| 68 | |||
| 69 | randInit(seed); | 65 | randInit(seed); |
| 70 | for (k = 0; k < m; k++) { | ||
| 71 | i = randInt(0, n - 1); | ||
| 72 | j = randInt(0, n - 1); | ||
| 73 | *(din + j * n + i) = randInt(MIN_EDGES, MAX_EDGES); | ||
| 74 | } | ||
| 75 | 66 | ||
| 76 | SET_UP | 67 | for_each_job { |
| 77 | startTime = time(NULL); | 68 | for (i = 0; i < n * n; i++) { |
| 69 | *(din + i) = NO_PATH; | ||
| 70 | *(dout + i) = NO_PATH; | ||
| 71 | } | ||
| 78 | 72 | ||
| 79 | START_LOOP | 73 | for (k = 0; k < m; k++) { |
| 80 | for (k = 0; k < n; k++) { | 74 | i = randInt(0, n - 1); |
| 81 | unsigned int old; | 75 | j = randInt(0, n - 1); |
| 82 | unsigned int new1; | 76 | *(din + j * n + i) = randInt(MIN_EDGES, MAX_EDGES); |
| 83 | unsigned int *dtemp; | 77 | } |
| 84 | 78 | ||
| 85 | for (i = 0; i < n; i++) { | 79 | startTime = time(NULL); |
| 86 | for (j = 0; j < n; j++) { | 80 | |
| 87 | old = *(din + j * n + i); | 81 | for (k = 0; k < n; k++) { |
| 88 | new1 = *(din + j * n + k) + *(din + k * n + i); | 82 | unsigned int old; |
| 89 | *(dout + j * n + i) = (new1 < old ? new1 : old); | 83 | unsigned int new1; |
| 90 | assert(*(dout + j * n + i) <= NO_PATH); | 84 | unsigned int *dtemp; |
| 91 | assert(*(dout + j * n + i) <= *(din + j * n + i)); | 85 | |
| 86 | for (i = 0; i < n; i++) { | ||
| 87 | for (j = 0; j < n; j++) { | ||
| 88 | old = *(din + j * n + i); | ||
| 89 | new1 = *(din + j * n + k) + *(din + k * n + i); | ||
| 90 | *(dout + j * n + i) = (new1 < old ? new1 : old); | ||
| 91 | assert(*(dout + j * n + i) <= NO_PATH); | ||
| 92 | assert(*(dout + j * n + i) <= *(din + j * n + i)); | ||
| 93 | } | ||
| 92 | } | 94 | } |
| 95 | dtemp = dout; | ||
| 96 | dout = din; | ||
| 97 | din = dtemp; | ||
| 93 | } | 98 | } |
| 94 | dtemp = dout; | ||
| 95 | dout = din; | ||
| 96 | din = dtemp; | ||
| 97 | } | 99 | } |
| 98 | 100 | ||
| 99 | STOP_LOOP | ||
| 100 | stopTime = time(NULL); | 101 | stopTime = time(NULL); |
| 101 | 102 | ||
| 102 | for (j = 0; j < n; j++) { | 103 | for (j = 0; j < n; j++) { |
