"I've seen this element before..." Often we are faced with the problem of building up sets incrementally, by removing pieces one at a time from a larger whole. The bottlenecks in this case are usually: 1) adding a small set X to a large set S (copies S and X, making this ~O(|S|+|X|)) 2) removing elements of the large set S from the small set X (binary search: |X|*log(|S|)) A classic example of this is a breadth-first-search. We start at one vertex of a graph and in each iteration we add the set of new neighbors X to the set of vertices S that have already been found. We can make this more useful by making the program return the sets of new neighbors found in each iteration, that is, the sets of vertices that are distance 1, 2, 3, etc. from the initial vertex.

Here is a simple example of a graph:

1--2--3
|     |   
4--5--6
   |  |
7--8--9

which I will store as a table mapping vertices (e.g.: 1) to a set of neighbors (e.g.: {2,4}).

G := table([1={2,4}, 2={1,3}, 3={2,6}, 4={1,5}, 5={4,6,8}, 6={3,5,9}, 7={8}, 8={5,7,9}, 9={6,8}]);

Starting from vertex 1, the BFS should return [{1}, {2,4}, {3,5}, {6,8}, {7,9}], corresponding to vertices that are distance [0,1,2,3,4] away. How would you program this in Maple ? I like to use the following trick:

zap := proc(v) procname(v) := NULL; v end proc:
forget(zap):

This procedure returns any object that it has not seen before, but assigns object=NULL to its own remember table so that if the object is encountered again nothing is returned. If S is a set, the result of map(zap, S) is the set of objects in S that are new. If you use this in your code, you should always take care to include the second line, forget(zap). Otherwise you will find yourself tracking down mysterious bugs, the cause of which are a topic in itself. As an aside, what useful operation will the following do ?

zap := proc(v) procname(v) := NULL; v end proc:
forget(zap):
L := [1,2,1,1,3,2,4,3,1,2];
map(zap, L);

And for the experts in the house, how might you use the following variant ?

zap := proc(v) procname(v) := false; true end proc:
forget(zap);

Returning to breadth-first-search, here is some simple yet efficient code that takes a graph G as encoded above and a vertex v to start from. We store the current new neighbors in a set X and write them to a table S.

BFS := proc(G, v)
  local S, X, i, zap, d;
   zap := proc(v) procname(v) := NULL; v end proc;
   forget(zap);
   S := table();
   X := map(zap, {v});
   for i from 0 while nops(X) > 0 do
     S[i] := X;
     X := {seq(op(map(zap, G[i])), i=X)};
   end do;
   d := i-1;
   [seq(S[i], i=0..d)];
end proc:

You can play with this code to make it more efficient. For example, you can use another seq in place of op(map(zap, G[i])) and use lists everywhere instead of sets to completely avoid sorting (all elements are unique). These types of optimizations are important for large problems. Assuming you know, you should always ask yourself "what will the kernel do ?" That's the surest way to fast code.