A Mathematica Tutorial for Combinatorica Users

The function below takes a graph g and a vertex start and performs a breadth first search of g starting
at start. The function returns three lists (i) bfi, which contains breadth first search numbers, (ii) parent, which contains parent pointers representing the breadth first search tree, and (iii) lvl, which contains the distances of vertices from start.

BFS[g_Graph, 
        start_Integer] :=                 
Module[{e  =  ToAdjacencyLists[g], 
            bfi = Table[0, {V[g]}], cnt = 1,  
            queue = {start}, 
parent = 
              Table[i, {i, V[g]}],  
            lvl = Table[
                Infinity, {V[
                    g]}]}, 
bfi[[start]] = cnt++;  
lvl[[start]] = 0; 
While[
            queue ≠ {}, 
{v, 
                queue} = {First[queue], 
                Rest[queue]}; 
Scan[(If[
                    bfi[[#]] == 0, 
                    bfi[[#]] = cnt++; 
parent[[#]] = v; 
lvl[[#]] = 
                      lvl[[v]] + 1; 
AppendTo[
                      queue, #]]) &, 
              e[[v]]
]
]; 
{bfi, parent, 
            lvl}] /; (1 ≤ start) && (start ≤ 
              V[g])

To show how the BFS function works,we define g as a wheel with 7 vertices and run BFS on it.

g  =  Wheel[7]

ShowGraph[g,  VertexNumber -> On]

BFS[g,  1]

Function Definition

A function definition that defines a function F has the syntax

                                  F[sequence of arguments] := body of function

Each argument in the sequence of arguments is a pattern that is matched when the function is called.  For example, the first input below defines a single argument function F and the second input calls it with argument 10. The argument 10 in the function call matches x_ in the function definition with the result that x acquires the value 10 and this is used when the right handside x^2 is evaluated.

F[x_]  :=  x^2

F[10]

Restrictions can be placed on what matches a pattern, thereby forcing arguments of only certain types (or forms) in the call to match arguments in the definition. For example,

G[y_Integer]  :=  y^2

G[10]

G[10.1]

F[10.1]

In this example, only an integer argument in the function call to G can match y_Integer. This is the kind of pattern matching used in the definition of BFS. Only a graph object can match the first argument and only an integer can match the second argument. Here are examples in which the matching fails amd the function call fails to evaluate BFS.

BFS[10,  10]

BFS[g,  10.1]

Pattern matching is an extremely important topic inMathematicaand one can say a lot more about it than what has been said here.But,we'll now move on to the next item in the code that is worth discussing.

Defining Local Variables

As the help string below tells us, a Module is a way to define local variables. The first argument of Module is a list of variables (some of which may be accompanied by initializations) and the second argument is the code to which these definitions apply.

I use Module in BFS to define the variables  e, bfi, cnt,  queue,  parent,  lvl.  I initialize all of these variables as I define them.

An alternative to Module is Block. We will not discuss the distinction between these two constructs here.

?Module

As the following example shows, the variables i and j have no existence outside Module.

Module[{i,  j},  i  =  10;  j  =  20]

i

j

List Manipulation

In BFS the variable bfi is initialized as bfi=Table[0,{V[g]}]. Here I use one of the most common Mathematica constructs, Table.

?Table

As the above help strings tells us, Table can be used to generate single dimensional or multiple dimensional table (lists). For example,

Table[1,  {10}]

Table[1,  {i,  10}]

Table[i,  {i,  10}]

Table[i,  {i,  3,  10}]

Table[i*j,  {i,  10},  {j,  10}]

t = Table[i*j,  {i,  10},  {j,  1,  i}]

t // ColumnForm

Though there are many other Mathematica constructs that can be used as alternatives to Table, they will probably be slower and not as elegant.

In BFS the variable e is initialized to the adjacency list representation of the graph g. Converting the graph into its adjacency list representation before doing anything else is common feature in many Combinatorica functions that work with graphs. Below, I show what is assigned to e when g is a 7-vertex Wheel .

e  =  ToAdjacencyLists[g]

The body of BFS starts after the variables are defined and the first statement in the body is 
			bfi[[ start ]] = cnt++;
When bfi is defined, it is initialized to a list of 0's via the Table function. In the above statement the slot in bfi indexed by start is assigned the value of cnt. So [[..]] plays the same role of as [..] does in languages such as C or C++. The second statement in BFS is a very similar initialization
			lvl[[ start ]] = 0;
An arbitrary subset of the slots in a list can be assigned values using one statement, as the following example shows. After the variable l is assigned to {1, 2, ..., 10}, l[[ 2 ]], l[[5]], and l[[6]] are assigned 3 new values in one statement.

l  =  Range[10]

l[[{2,  5,  6}]]  =  {-1,  -2,  -3}

l

In Mathematica the List object is amazingly versatile.For example,elements from a List can be extracted using any of the following operations:Part,First,Last,Head,Extract,Take,Drop,Rest,Select,and Cases. Under the heading "List Operations"  Mathematica aprovides: Append, Prepend, Insert, Delete, DeleteCases, ReplacePart, Join, Union, Intersection, Complement, Sort, Reverse, RotateLeft, RotateRight, PadLeft, PadRight. There are many other operations related to Lists under the heading of "List Construction," "List Testing," and "Structure Manipulation." Most objects in Combinatorica are represented as lists and therefore the amazing array of list manipulation functions thatMathematicaprovides leads to compact and elegant programs.

Loops

The next construct used in BFS is the While construct. As the help string below tells us, the While construct takes in two arguments and the semantics are similar to those associated with while-loops in C or C++.

?While

The example below shows that unlike a function like Table, While does not produce any output and therefore its importance is in the side effects it causes.

sum  =  0

i  =  0

While[i  <  10,  sum  =  sum +  10;  i++]

sum

Other iteration constructs in Mathematica are provided by the Do-construct and the For-construct.

?Do

?For

The first statement in the body of the while-loop in BFS is 
		 { v,  queue }  =  {  First[queue],   Rest[queue]  };
and this is yet another evidence of the versatility of the List data structure in Mathematica. First[queue] evaluates to the first (top) element in the queue. Rest[queue] evaluates to a list obtained by dropping the first element from queue. These two quantities are simultaneously assigned to v and queue respectively, having the effect of dequeuing an element from queue and assigning it to v.

l  =  {1,  3,  8,  -1,  11,  12}

{v,  l}  =  {First[l],  Rest[l]}

{v,  l}

Functional Operations

The rest of the while-loop in BFS is taken up by a call to the Scan function. Scan, along with relatives such as Map and Apply and extremely important functions in Mathematica. These are called functional operations because they work by applying functions to elements of lists.

?Scan

Scan, like the While-function produces no output. It is useful only for the side-effects it produces. In BFS,  Scan produces side-effects on bvi, parent, and lvl.  

In the following example, I define a single argument function Acc that increases a quantity m by the given argument. Scan[Acc, l] evaluates Acc by providing it with each element of l in turn. This results in each element in l being added to m. If m is initialized to 0 and then Scan[Acc, l] is called then m ends up being the sum of the values in l.  Note that Scan[Acc, l] produces no output and the this function call is useful only in the effect it has on m.

Acc[x_]  :=  m = m  +  x

l

m  =  0

Scan[Acc,  l]

m

In the above example, Acc was explicitly named. Mathematica provides a way of specifying functions without explicitly naming them. This mechanism, demonstrated below is called a "pure function."  In the example below, we do not use Acc; instead, within the call to Scan, we specify an equivalent pure function
				Function[x,   m  = m + x]
that takes a single formal argument x and adds it to the quantity m.

m  =  0

Scan[Function[x,  m  =  m  +  x],  l]

m

?Function

The help string for Function above tells us that there is a shortform we can use for pure functions in which the formal arguments are also not explicitly named. The example below shows this. In this example,
				(m = m + #)&
is used to specify a pure function with a single argument, specified by #.

m  =  0

Scan[(m  =  m  +  #)  &,  l]

m

Below is yet another example of Scan and pure functions.The pure function
				If [  PrimeQ[#],   s++ ]&
increments s if  the argument provided to the function is a prime. Using this,  the following example discovers that the number of primes no greater than 1000 is 168.

l  =  Range[1000];

?PrimeQ

s  =  0

Scan[If[PrimeQ[#],  s++] &,  l]

s

As a final example of Scan, consider the function call to Scan in BFS. The appropriate code fragment is reproduced below. The second argument to this function call is e[[ v ]], which is the list of all neighbors of v. So Scan processes each neighbor, say u, of v in turn, checking to see the bfi-value of u is 0. If bfi[[ u ]]  is then it means that u has not yet been visited and the values of bfi[[u]], parent[[ u ]], and lvl[[ u ]] are all appropriately updated.
    
   				 Scan[(If[bfi[[#]]==0,bfi[[#]]=cnt++;
            				parent[[#]]=v;
           					 lvl[[#]]=lvl[[v]]+1;
            				AppendTo[queue,#]])&,    e[[v]]
      				]

Map is a Mathematica function that is closely related to Scan and is probably more useful than Scan. The big difference between Scan and Map is that Map returns output and therefore can be used as an argument to other functions. Anything Scan can do, Map can also do. But calling Map when Scan suffices, as in the BFS example leads to inefficient code.

?Map

l  =  {1,  2,  10,  4}

Map[#^2 &,  l]

Map[f,  {1,  3,  4}]

Map is important enough that Mathematica contains several variants: MapAll, MapAt, MapIndexed, and MapThread.

Final Words

After the end of the definition of BFS, the reader will notice
			 /;   (1 ≤ start)  &&  (start  ≤  V[g])
As the following help string tells us, this is a boolean condition that has to evaluate to True for the function
definition to help. So this condition ensures that unless start is a valid vertex (an integer in the range 1 through the number of vertices) BFS will not be defined.

?/;