Graph theory - Objective C Breadth-first search example
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
WordFinder.xcodeproj
WordFinder
README.md

README.md

WordFinder

Graph theory - Objective C Breadth-first search example

I’ve made an example where graph theory and Breadth-first search comes in hand using a simple game. “Wordz” was very popular for a while, if you don’t know the game itself you are probably familiar with the game concept where you have to connect given letters which would then form a word. The more letters in the word, the more points you get. The game in this example has 4×4 letter matrix and the words may be assembled from letters in all directions (not just vertically and horizontally). For 16 given letters that form the 4×4 matrix, all possible words are listed (with matrix coordinates for connecting each letter in the word) using the Breadth-first search algorithm.

There are three main objects: graph node, directional graph and the search controller.

Every node has a list of other nodes it’s adjacent to. Graph adds the nodes via the addAdjacentNode: method:

@interface GraphNode : NSObject
{
    NSMutableArray *_adjacent;
    NSString *_nodeName;
	NSString *_nodeValue;
}

- (void)addAdjacentNode:(GraphNode *)node;
- (NSArray *)adjacentNodes;

Using the DirectionalGraph object the nodes are connected forming the Graph.

@interface DirectionalGraph : NSObject

- (void)addEdgeFromNode:(GraphNode *)node1 toNode:(GraphNode *)node2;
- (void)addBidirectionalEdgeFromNode:(GraphNode *)node1 toNode:(GraphNode *)node2;

@end

Search controller is used for performing the Breadth-first search on the DirectionalGraph object.

@interface GraphSearchController : NSObject
{
	NSMutableArray *_nodes;
    NSMutableArray *_visited;
	NSMutableArray *_dataSource;
    NSMutableArray *_allPaths;
    NSMutableArray *_allWords;
	NSMutableDictionary *_wordPathDict;

    GraphNode *_startNode;
	GraphNode *_endNode;

    DirectionalGraph *_graph;
}

- (void)startSearch;

@end

_nodes array contains all 16 node object representing each letter

_visited is used for the BFS algorithm to track the nodes that have already been visited

_dataSource is the array of words to match BFS results

_allPaths, _allWords and _wordPathDict are used to store BFS results

_startNode and _endNode are the two nodes the BFS is trying to find the path between; the BFS algorithm is executed for each two nodes in the graph

Input

In GraphSearchController.m:

4x4 matrix like the one below is used for graph search example

A B C D
E F G H
I J K L
M N O P

e.g. for a matrix in the image above:

e e y o
d i t j
o u r v
b w u a

inline presentation of the above 4x4 matrix

static NSString *valueString = @"eeyoditjourvbwua";

Output

All found words and letter locations are logged in the console, e.g.:

'variety'
(
	"v - (3,4)",
	"a - (4,4)",
	"r - (3,3)",
	"i - (2,2)",
	"e - (1,2)",
	"t - (2,3)",
	"y - (1,3)"
)