source: buchla-68k/orig/GP/TOPO.C@ 28c0933

Last change on this file since 28c0933 was 3ae31e9, checked in by Thomas Lopatic <thomas@…>, 7 years ago

Imported original source code.

  • Property mode set to 100755
File size: 2.1 KB
Line 
1/*
2 =============================================================================
3 topo.c -- Topological Sort Algorithm
4 Version 2 -- 1989-02-07 -- D.N. Lynx Crowe
5 =============================================================================
6*/
7
8#include "stddefs.h"
9
10/*
11 =============================================================================
12
13 Topological Sort Algorithm
14 --------------------------
15
16 Initialize an array T[i][j] such that
17 if i is a predecessor of j, T[i][j] = 1,
18 otherwise, T[i][j] = 0.
19
20 Set the count of completed tasks to 0.
21
22 Set the order[] array to zeros.
23
24 Repeat:
25
26 Search T for an unconstrained task k,
27 such that T[i][k] = 0 for all i,
28 and for that task:
29
30 Set order[count] = k, { log task }
31
32 Set T[k][j] = 0 for all j, { enable successors }
33
34 Set T[k][k] = 1, and { mark task complete }
35
36 Add 1 to the count of completed tasks.
37
38 until no unconstrained tasks exist.
39
40 If the number of completed tasks = the number of tasks, the job is done.
41 =============================================================================
42*/
43
44/*
45
46*/
47
48/*
49 =============================================================================
50 topo() -- Topological Sort Algorithm
51 =============================================================================
52*/
53
54short
55topo(n, T, order)
56register short n; /* input: number of tasks */
57register char *T; /* input: precedence array, char T[n][n] */
58register short order[]; /* output: task order array*/
59{
60 register short count, j, k;
61
62 count = 0; /* initialize count of number of tasks done */
63
64look:
65 k = 0;
66
67 do {
68
69 /* look for an unconstrained task */
70
71 for (j = 0; j < n; j++)
72 if (T[(j * n) + k]) /* if any bit is set */
73 goto haspred; /* ... it's constrained */
74
75 order[count++] = k; /* log the task */
76 T[(k * n) + k] = 1; /* mark the task complete */
77
78 for (j = 0; j < n; j++) /* trigger its successors */
79 T[(k * n) + j] = 0;
80
81 goto look; /* look for another task */
82
83haspred:
84 } while (++k LE n);
85
86 if (count EQ n) /* see if all are done */
87 return(SUCCESS);
88 else
89 return(FAILURE);
90}
Note: See TracBrowser for help on using the repository browser.