Main routine for topological sort. Calls itself recursively on all adjacent * vertices which were not yet visited. After that, 'current_vertex' is added to * '*result_ptr'. */
| 48 | * '*result_ptr'. |
| 49 | */ |
| 50 | void do_ts( int * * graph, int current_vertex, int * colors, int * * result_ptr |
| 51 | ) |
| 52 | { |
| 53 | int i; |
| 54 | |
| 55 | colors[ current_vertex ] = gray; |
| 56 | for ( i = 0; graph[ current_vertex ][ i ] != -1; ++i ) |
| 57 | { |
| 58 | int adjacent_vertex = graph[ current_vertex ][ i ]; |
| 59 | if ( colors[ adjacent_vertex ] == white ) |
| 60 | do_ts( graph, adjacent_vertex, colors, result_ptr ); |
| 61 | /* The vertex is either black, in which case we do not have to do |
| 62 | * anything, or gray, in which case we have a loop. If we have a loop, |
| 63 | * it is not clear what useful diagnostic we can emit, so we emit |
| 64 | * nothing. |
| 65 | */ |
| 66 | } |
| 67 | colors[ current_vertex ] = black; |
| 68 | **result_ptr = current_vertex; |
| 69 | ( *result_ptr )++; |
| 70 | } |
| 71 | |
| 72 | |
| 73 | void topological_sort( int * * graph, int num_vertices, int * result ) |