Directed Graph implementation in Objective-C

Question

Before diving in and rolling my own implementation in Objective-C, I'm looking around to try and find an iPhone SDK-compatible directed graph ("digraph") implementation. For the sake of this question, I'll lean on Wikipedia to define the term:

Because ensuring the graph is acyclic or otherwise preventing infinite recursion is non-trivial with digraphs, I'm hoping that there's an existing implementation I can reference.

Can anyone point me to an existing directed graph class in Objective-C? I checked out CHDataStructures, but nothing jumped out at me as being equivalent.

Answer 1

I've never heard of any Cocoa directed graph implementation like what you appear to be describing, but it really shouldn't be too difficult to implement. Basically you'd just need a Node object with an id ivar to hold the value and an NSMutableSet to point to its children. Ensuring acyclicality would be about a O(n log n) operation (where n is the # of nodes in the graph). When you go to add a child to a Node, you'd just need to traverse the children links and make sure that none are ever repeated. It'd be something like this:

BOOL isNodeAcyclic(Node * n, NSMutableSet * visitedNodes) {
  if ([visitedNodes intersectsSet:[n children]]) { return NO; }
  for (Node * child in [n children]) {
    [visitedNodes addObject:child];
    BOOL isChildAcyclic = isNodeAcyclic(child, newSet);
    [visitedNodes removeObject:child];
    if (isChildAcyclic == NO) { return NO; }
  }
  return YES;
}

Then to determine if a node you're adding to a graph would make it be cyclical, you'd just need to do something like this in your Node class:

- (BOOL) addChild:(Node *)newChild {
  [[self children] addObject:newChild];
  BOOL isAcyclic = isNodeAcyclic(newChild, [NSMutableSet set]);
  if (isAcyclic == NO) {
    //adding this child has caused a cycle
    [[self children] removeObject:newChild];
  }
  return isAcyclic;
}

(I just wrote this off the top of my head and haven't tested it. However, it should work.)

If you come up with an implementation that's appropriate, be sure to talk to Quinn Taylor (the author of CHDataStructures). This seems like the sort of thing that would be really neat to have in that framework. OTOH, he might be willing to write it for you and include it in the framework himself.