TopologicalSort.m

/*
A topological sort of a dag G = (V, E) is a linear ordering of all its vertices such that if G contains an edge (u, v), 
then u appears before v in the ordering. (If the graph is not acyclic, then no linear ordering is possible.) 
A topological sort of a graph can be viewed as an ordering of its vertices along a horizontal line so 
that all directed edges go from left to right.
*/
@implementation TopologicalSort
  
+ (void)topologicalSortWithAdjacencyMatrix:(NSArray<NSArray<NSNumber *> *> *)mat {
    
    NSMutableArray<CCMutableNumber *> *discoveryTime = @[].mutableCopy;
    NSMutableArray<CCMutableNumber *> *finishTime = @[].mutableCopy;
    NSMutableArray<NSNumber *> *visited = @[].mutableCopy;
    Stack<NSNumber *> *st = [[Stack alloc] init];
    
    for(NSUInteger i = 0; i < mat.count; ++i) {
        visited[i] = @(NO);
        discoveryTime[i] = [[CCMutableNumber alloc] initWithNumber:@(NSNotFound)];
        finishTime[i] = [[CCMutableNumber alloc] initWithNumber:@(NSNotFound)];
    }
    
    [[self class] DFSWithAdjacencyMatrix:mat root:0 discoveryTime:discoveryTime finishTime:finishTime visited: visited time:[[CCMutableNumber alloc] initWithNumber:@(0)] stack:st];
    
    [st print];
}

+ (void)DFSWithAdjacencyMatrix:(NSArray<NSArray<NSNumber *> *> *)mat root:(NSUInteger)idx discoveryTime:(NSMutableArray<CCMutableNumber *> *)discoveryTime finishTime:(NSMutableArray<CCMutableNumber *> *)finishTime visited: (NSMutableArray<NSNumber *> *)visited time:(CCMutableNumber *)time stack:(Stack<NSNumber *> * _Nonnull)st {
    
    visited[idx] = @(YES);
    time.num = @(time.num.integerValue + 1);
    discoveryTime[idx] = time.copy;
    
    for(NSUInteger i = 0; i < mat[idx].count; ++i) {
        if([mat[idx][i] isEqualToNumber:@(YES)] && !visited[i].boolValue) {
            [[self class] DFSWithAdjacencyMatrix:mat root:i discoveryTime:discoveryTime finishTime:finishTime visited:visited time:time stack:st];
        }
    }
    time.num = @(time.num.integerValue + 1);
    finishTime[idx] = time.copy;
    [st push:@(idx)];
}


@end