NYCJUG/2009-11-10/BreadthFirstGraphTraversal

Introduction

The following question was posed on a programming questions site called "stackoverflow.com":

Breadth first search, and A* search in a graph?

I understand how to use a breadth first search and A* in a tree structure, but given the following graph, how would it be implemented? In other words, how would the search traverse the graph? "S" is the start state.

There were a number of helpful suggestions but it occurred to me how simple and quick it would be to write J code to illustrate a solution, so, in about fifteen minutes, I did so. The following is the reply I posted. The intention here is to show how simple a solution can be when much of the structure of the code is built into the data structure.

A J Solution

I don't know how helpful you will find this, but here's a complete solution coded in the functional language J (available for free from jsoftware.com).

First, it's probably simplest to work directly from a representation of the graph you show in your picture. I represent this as a (# nodes) x (# nodes) table with a number at (i,j) for the value of the link between node-i and node-j. Also, along the diagonal I've put the number associated with each node itself.

So, I enter this as follows - don't worry too much about the unfamiliar notation, you'll soon see what the result looks like:

     grph=: <;.1&>TAB,&.><;._2 ] 0 : 0
    A   B   C   D   E   G1  G2  S
A    2   1           8           2
B        1   1   1       4       2
C        3   1               5  
D                1       5   2  
E                    6   9   7  
G1                        0      
G2                            0  
S    2       3                   5
)

So, I've assigned the variable "grph" as a 9x9 table where the first row and first column are the labels "A"-"E", "G1", "G2", and "S"; I've used tabs to delimit items so this could be cut-and-pasted to or from a spreadsheet as needed.

Now, I'll check the size of my table and display it:

   $grph
9 9
   grph
+---+--+--+--+--+--+---+---+--+
|   | A| B| C| D| E| G1| G2| S|
+---+--+--+--+--+--+---+---+--+
| A | 2| 1|  |  | 8|   |   | 2|
+---+--+--+--+--+--+---+---+--+
| B |  | 1| 1| 1|  | 4 |   | 2|
+---+--+--+--+--+--+---+---+--+
| C |  | 3| 1|  |  |   | 5 |  |
+---+--+--+--+--+--+---+---+--+
| D |  |  |  | 1|  | 5 | 2 |  |
+---+--+--+--+--+--+---+---+--+
| E |  |  |  |  | 6| 9 | 7 |  |
+---+--+--+--+--+--+---+---+--+
| G1|  |  |  |  |  | 0 |   |  |
+---+--+--+--+--+--+---+---+--+
| G2|  |  |  |  |  |   | 0 |  |
+---+--+--+--+--+--+---+---+--+
| S | 2|  | 3|  |  |   |   | 5|
+---+--+--+--+--+--+---+---+--+

It looks OK and it's easy to compare this to the picture of the graph to check it. Now I'll drop the first row and column so we're left only with numbers (as boxed literals), and remove any extraneous tab characters.

   grn=. TAB-.~&.>}.}."1 grph

You can see I assign this result to the variable "grn".

Next, I'll replace any empty cells with "_" - which represents infinity - then convert the literals to numeric representation (re-assigning the result to the same name "grn"):

   grn=. ".&>(0=#&>grn)}grn,:<'_'

Finally, I'll move the last column and row to the beginning since this is the one for "S" and it's supposed to be first. I'll also display the result to confirm that it looks correct.

   ]grn=. _1|."1]_1|.grn   NB. "S" goes first.
5 2 _ 3 _ _ _ _
2 2 1 _ _ 8 _ _
2 _ 1 1 1 _ 4 _
_ _ 3 1 _ _ _ 5
_ _ _ _ 1 _ 5 2
_ _ _ _ _ 6 9 7
_ _ _ _ _ _ 0 _
_ _ _ _ _ _ _ 0

So, now that I have a simple 8x8 table of numbers representing the graph, it's a simple matter to traverse it.

Here's a simple J function, called "traverseGraph", to read this table, traverse the graph it represents, and return two results: the indexes (0-based origin) of the nodes visited, and the values of the points and edges in the order visited.

traverseGraph=: 3 : 0
   pts=. ,_-.~,ix{y [ nxt=. ix=. ,0
   while. 0~:#nxt=. ~.ix-.~;([:I._~:])&.><"1 nxt{y do.
        ix=. ix,nxt [ pts=. pts,_-.~,nxt{y
   end.
   ix;pts
)

We start by initializing three variables: the list of indexes "ix" (to zero, since we want to begin in the zeroth row of the table), a variable "nxt" to point to the next group of nodes (initially the same as the starting node), and the list of point values "pts" (starting as the 0th row of our input table, known internally as "y", with all the infinite values removed.)

In the "while." loop, we continue as long as there's more than zero "nxt" values resulting from pulling the current row out of the table and removing any nodes (in "ix") we've already visited. Inside the loop, we accumulate the next set of indexes onto the end of "nxt" and the point values onto "pts". At the end, we return the indexes and point values as our (two-element) result.

We run it like this - it displays the result by default:

   traverseGraph grn
+---------------+---------------------------------------------+
|0 1 3 2 5 7 4 6|5 2 3 2 2 1 8 3 1 5 2 1 1 1 4 6 9 7 0 1 5 2 0|
+---------------+---------------------------------------------+

So, the first box contains the indexes starting with "0" and ending with "6". The second boxed item is the vector of point values in the order we accumulated them. I don't know what you do with these, so I just show them.

We can use the indexes to display the node names like this:

   0 1 3 2 5 7 4 6{(<"0'SABCDE'),'G1';'G2'
+-+-+-+-+-+--+-+--+
|S|A|C|B|E|G2|D|G1|
+-+-+-+-+-+--+-+--+

I don't know how useful you'll find this but it does outline a simple solution to your problem.