OKAMutableDirectedGraph is an implementation of a directed graph in Objective-C.
OKAMutableDirectedGraph was developed originally for managing dependencies - but it can be used for path finding, sorting, garbage collection and much more.
NSString *a = @"a";
NSString *b = @"b";
NSString *c = @"c";
OKAMutableDirectedGraph *graph = [[OKAMutableDirectedGraph alloc] init];
for (NSString *job in @[ a, b, c ]) {
[graph addNode:job];
}
[graph addEdgeFrom:c to:b];
[graph addEdgeFrom:b to:a];
NSMutableArray *sorted = [NSMutableArray array];
do {
NSArray *heads = graph.heads;
for (NSString *job in heads) {
[graph removeNode:job];
[sorted addObject:job];
}
} while (graph.heads.count != 0);
(lldb) sorted => @[ c, b, a ]Princeton University - Directed Graphs
Oliver Atkinson
OKAMutableDirectedGraph is available under the MIT license. See the LICENSE file for more info.