Graph search algorithm implementation of searching for words on a boggle board in objective-c

gistfile1.m

#import <Foundation/Foundation.h>

@interface Node : NSObject
@property (nonatomic, strong) NSString * letter;
@property (nonatomic, strong) NSMutableSet * adjacentNodes;
@end

@implementation Node
-(NSMutableSet *)adjacentNodes{
    if(_adjacentNodes){
        return _adjacentNodes;
    }
    _adjacentNodes = [[NSMutableSet alloc] init];
    return _adjacentNodes;
}
@end


@interface Graph : NSObject
@property (nonatomic, strong) NSSet * nodes;
@property (nonatomic, strong) NSDictionary * lookupDictionary;

+(instancetype)graphForBoggleBoard:(NSArray *)board;

-(BOOL)searchForWord:(NSString *)word;
@end

@implementation Graph

+(instancetype)graphForBoggleBoard:(NSArray *)board{
    NSMutableSet * nodes = [[NSMutableSet alloc] init];
    NSMutableDictionary * dictionary = [NSMutableDictionary dictionary];

    NSMutableArray * nodeBoard = [[NSMutableArray alloc] initWithCapacity:board.count];
    for (NSArray * row in board){
        NSMutableArray * nodeRow = [[NSMutableArray alloc] initWithCapacity:row.count];
        for (NSString * letter in row){
            Node * node = [[Node alloc] init];
            node.letter = letter;
            
            [nodeRow addObject:node];
            [nodes addObject:node];
            if (dictionary[node.letter]){
                [dictionary[node.letter] addObject:node];
            }else{
                dictionary[node.letter] = @[node].mutableCopy;
            }
        }
        [nodeBoard addObject:nodeRow];
    }


    NSArray * previousRow = nil;
    for (NSInteger row = 0; row < nodeBoard.count; row++){
        NSArray * nodeRow = nodeBoard[row];
        for (NSInteger col = 0; col < nodeRow.count; col ++){
            Node * currentNode = nodeBoard[row][col];
            for (int i = col - 1; i <= col + 1; i++){
                if (i < 0 || i >= nodeRow.count)
                    continue;
                Node * node = previousRow[i];
                if (node){
                    [currentNode.adjacentNodes addObject:node];
                    [node.adjacentNodes addObject:currentNode];   
                }
            }
            if (col > 0){
                Node * node = nodeBoard[row][col - 1];
                [currentNode.adjacentNodes addObject:node];
                [node.adjacentNodes addObject:currentNode];
            }
        }
        previousRow = nodeRow;
    }


    Graph * graph = [[Graph alloc] init];
    graph.lookupDictionary = dictionary;
    graph.nodes = nodes;
    return graph;
}

BOOL depthFirstSearch(Node * node, NSString * word, NSInteger depth, NSMutableSet * visitedNodes){

    unichar nodeLetter = [node.letter characterAtIndex:0];
    unichar wordLetter = [word characterAtIndex:depth];

    [visitedNodes addObject:node];

    if (nodeLetter == wordLetter){
        if (depth < word.length - 1) {
            for (Node * adjacentNode in node.adjacentNodes){
                if ([visitedNodes containsObject:adjacentNode]) continue;
                BOOL found = depthFirstSearch(adjacentNode, word, depth + 1, visitedNodes);
                if (found) return found;
            }
        }
        else return YES;
    }

    [visitedNodes removeObject:node];
    return NO;
}

-(BOOL)searchForWord:(NSString *)word{
    NSString * firstLetter = [NSString stringWithFormat:@"%c",[word characterAtIndex:0]];
    NSSet * firstNodes = self.lookupDictionary[firstLetter];
    for (Node * node in firstNodes){
        NSMutableSet * visitedNodes = [[NSMutableSet alloc] initWithCapacity:word.length];
        BOOL found = depthFirstSearch(node, word, 0, visitedNodes);
        if (found) return found;
    }

    return NO;
}
@end


int main(int argc, char *argv[]) {
    @autoreleasepool {
        NSArray * boggleBoard = @[
                                  @[@"a", @"b", @"c"],
                                  @[@"d", @"d", @"h"],
                                  @[@"e", @"i", @"u"]
                                  ];

        Graph * graph = [Graph graphForBoggleBoard:boggleBoard];
        NSLog (@"Word %@", [graph searchForWord:@"chuddd"] ? @"exists" : @"doesnt exist");
    }
    return 0;
}