# How to perform a breadth-first traversal of an expression?

Mathematica provides functions that perform a depth-first traversal, or which use such a traversal, including: Scan, Count, Cases, Replace, and Position. It is also the standard evaluation order therefore functions Mapped (Map, MapAll) will evaluate in a depth-first order.

It is quite direct to do this:

expr = {{1, {2, 3}}, {4, 5}};

Scan[Print, expr, {0, -1}]


1

2

3

{2,3}

{1,{2,3}}

4

5

{4,5}

{{1,{2,3}},{4,5}}

How can one do a Scan-type operation breadth-first? (Simply storing then reordering the output is not adequate as it doesn't change the order in which expressions are visited.)

Scan has the property that it does not build an output expression the way that e.g. Map does, which is quite appropriate for breadth-first scans, and conserves memory.

-
What do you mean that Map and MapAll perform a df traversal? – Rojo Aug 8 '12 at 11:05
Convert expression to Graph, then do BreadthFirstScan. – Sjoerd C. de Vries Aug 8 '12 at 11:08
@Rojo A little late but I rewrote the question to hopefully rectify the inaccurate statements. – Mr.Wizard Jul 28 '14 at 11:09

Here is an expressly iterative solution:

bf[f_, x_] := ((f~Scan~#; #~Level~{2})& ~FixedPoint~ {x};)

(*
In[2]:= bf[Print, {{1, {2, 3}}, {4, 5}}]

{{1,{2,3}},{4,5}}
{1,{2,3}}
{4,5}
1
{2,3}
4
5
2
3
*)


Incorporating Rojo's advice to Hold expressions gathered by Level:

bf[f_, x_] := ( Level[f~Scan~#; #, {2}, Hold] & ~FixedPoint~ {x} ;)

-
As they always say, Know Your Audience ;) – WReach Aug 8 '12 at 19:34
I may have to Accept this. :-) – Mr.Wizard Aug 8 '12 at 20:32
hmm... you start out with a sad face, but end with a winkey – R. M. Aug 8 '12 at 21:42
+1, you forgot to put the ;) in the next line. Wink not intended but appropriate – Rojo Aug 8 '12 at 22:42
bf[Hold, Hold[Print@2]] leaks. It could be fixed by letting down the audience and changing infix Level to Level[#, {2}, Hold] – Rojo Aug 9 '12 at 0:44

Here is a simple implementation of a breadth first traversal. It simply maps the function onto each element on the current level and then collects all non-atomic entries into the next level, rinse and repeat.

breadthFirstApply[{}, call_] := Null


      breadthFirstApply[{{1, {2, 3}}, {4, 5}}, Print]

{1,{2,3}}(*level 1*)
{4,5} (*level 1*)
1 (*level 2*)
{2,3} (*level 2*)
4 (*level 2*)
5 (*level 2*)
2 (*level 3*)
3 (*level 3*)


Edit: Updated code based on feedback from Rojo

-
+1. 2 small comments/questions. 1) Any reason to use call[#]& instead of plain call? 2) Any difference between Join@@Select... and Level[list, {2}] apart from Join@@... requiring all the sublists to have the same head? – Rojo Aug 8 '12 at 13:29
@Rojo I can't say there was any particular reason for the call[#]& just did it in a hurry, as for Level, I'm just in a mindeset where I didn't consider Level. Thanks for the great feedback, I added the changes to the code. – jVincent Aug 9 '12 at 0:11
:). Now with level I think you don't even need the inner Select, because the atoms simply won't be extracted by Level since they belong to level 1 – Rojo Aug 9 '12 at 0:16
@Rojo I'm rapidly running out of code for you to hack away at. :) – jVincent Aug 9 '12 at 0:30
breadthFirst[expr_] := Flatten[Table[Level[expr, {j}], {j, 0, Depth[expr]}], 1]


Running example:

expr = {{1, {2, 3}}, {4, 5}};

(* Out[14]= {{{1, {2, 3}}, {4, 5}}, {1, {2, 3}}, {4, 5}, 1, {2,
3}, 4, 5, 2, 3} *)

-
expr = {{1, {2, 3}}, {4, 5}};

Do[Scan[Print, expr, {i}], {i, 0, Depth@expr}]


{{1,{2,3}},{4,5}}
{1,{2,3}}
{4,5}
1
{2,3}
4
5
2
3

-
If I'm not mistaken ReplaceAll doesn't do breadth first, but depth first pre-order. And apart from it (and maybe Pick which I would have to think if it offers something new to the issue) I also don't know how to do . – Rojo Aug 8 '12 at 10:07
@Rojo Would you explain what you wrote about ReplaceAll? – Mr.Wizard Aug 8 '12 at 10:26
I meant that ReplaceAll does a recursive "first the expression and then the arguments traversal (depth first, pre-order), while most of the other functions do a depth first post-order (first the arguments, then the whole expression). But breath-first I think is different, it would mean traverse one level at a time, upload.wikimedia.org/wikipedia/commons/4/46/Animated_BFS.gif – Rojo Aug 8 '12 at 10:37
@Rojo just for reference, this would be a BF traversal, correct?: Table[Scan[Print, expr, {i}], {i, 0, Depth@expr}]; – Mr.Wizard Aug 8 '12 at 10:49
@Mr.Wizard Yes, that is a breadth-first traversal. – Zach Langley Aug 8 '12 at 14:38

I meant my comment above as a joke, but here's the implementation anyway.

Some ugly recursive code to convert the expression to a Graph:

ClearAll[treeBuild]
treeBuild[expr_[ops___]] := treeBuild[expr, #] & /@ {ops}
treeBuild[name_, expr_[ops___]] :=
Module[{node = Unique[expr]}, {name \[DirectedEdge] node,treeBuild[node, #] & /@ {ops}}]
treeBuild[node_, a_] := node \[DirectedEdge] Unique["L" <> ToString[a] <> "\$"]


Build the Graph

g = treeBuild[expr] // Flatten;

Graph[g, VertexLabels -> "Name", PlotRangePadding -> 0.25,
VertexSize -> Large, VertexStyle -> {List -> Green}]


And now the breadth first scan:

HighlightGraph[
Graph[g, VertexSize -> Large, VertexStyle -> {List -> Green}], {#}] & /@
Reap[
][[2, 1]]//ListAnimate


-

A package-ready breadth-first position search, returning positions of a pattern in an expression. It allows top-down and bottom-up breadth-first traversals by setting level specification. It is not exactly the one Mr.Wizard was looking for, as it checks absolute levels rigorously (i.e. all level 4 subparts are checked before any level 3 subpart is visited). Deals with the usual level specifications and can return a limited number of cases if asked for.

Options[bfPosition] = {Heads -> True};
bfPosition[expr_, patt_, opts : OptionsPattern[]] :=
bfPosition[expr, patt, {0, \[Infinity]}, \[Infinity], opts];
bfPosition[expr_, patt_, level_, opts : OptionsPattern[]] :=
bfPosition[expr, patt, level, \[Infinity], opts];
bfPosition[expr_, patt_, level_, 0 | 0., opts : OptionsPattern[]] = {};
bfPosition[expr_, patt_, level_, n_, opts : OptionsPattern[]] /;
If[MatchQ[level, {_Integer | Infinity, _Integer | Infinity} |
{_Integer | Infinity} | _Integer | Infinity], True,
Message[bfPosition::level, level]; False] := Module[
{lev, max = Depth@expr, range, c = 0, found, reap},

(* Normalize level specification *)
lev = Switch[level /. Infinity -> max,
{_Integer, _Integer}, level,
{_Integer}, {First@level, First@level},
_Integer, {1, level}];
lev = (Min[#, max] & /@ (lev /. x_?Negative :> Max[(max + 1 + x), 0]));
range = Range[First@lev, Last@lev, If[Greater @@ lev, -1, 1]];

(* Check each level until the required amount of matches are found *)
reap = Last@Reap@Do[
found = Position[expr, patt, {i, i}, n - c, Heads -> OptionValue@Heads];
c = c + Length@found;
Sow@found;
If[c >= n, Return[]];,
{i, range}];

If[reap === {}, {}, Join @@ (First@reap)]
];


bfPosition[expr, pattern] gives a list of the positions at which objects matching pattern appear in expr by performing a breadth-first search of subparts. Position[expr, pattern, levelspec] finds only objects that appear on levels specified by levelspec. Position[expr, pattern, levelspec, n] gives the positions of the first n objects found. bfPosition effectively accepts reverse-ordered level specifications that define the order of search in expr: for example bfPosition[expr, pattern, {\[Infinity], 0}] performs a bottom-up while bfPosition[expr, pattern, {0, \[Infinity]}] performs a top-down breadth-first search.

Test it:

 expr = {{1, {2, 3}}, {4, 5}};
pos = bfPosition[expr, _, {\[Infinity], 0}, Heads -> False];
If[# === {}, expr, Extract[expr, #]] & /@ pos

{2, 3, 1, {2, 3}, 4, 5, {1, {2, 3}}, {4, 5}, {{1, {2, 3}}, {4, 5}}}


Note that all level-3 objects (2, 3) are visited before encountering a level-2 leaf (1).

bfPosition is not like Position (Position does a depth-first postorder search):

bfPosition[expr, _, Heads -> False]

{{}, {1}, {2}, {1, 1}, {1, 2}, {2, 1}, {2, 2}, {1, 2, 1}, {1, 2, 2}}

{{1, 1}, {1, 2, 1}, {1, 2, 2}, {1, 2}, {1}, {2, 1}, {2, 2}, {2}, {}}


Find positions using bottom-up or top-down search:

bfPosition[expr, _, {\[Infinity], 0}, Heads -> False]
bfPosition[expr, _, {0, \[Infinity]}, Heads -> False]

{{1, 2, 1}, {1, 2, 2}, {1, 1}, {1, 2}, {2, 1}, {2, 2}, {1}, {2}, {}}

{{}, {1}, {2}, {1, 1}, {1, 2}, {2, 1}, {2, 2}, {1, 2, 1}, {1, 2, 2}}


Find a limited number of occurrences only:

bfPosition[expr, _, {\[Infinity], 0}, 4, Heads -> False]
bfPosition[expr, _, {0, \[Infinity]}, 4, Heads -> False]

{{1, 2, 1}, {1, 2, 2}, {1, 1}, {1, 2}}

{{}, {1}, {2}, {1, 1}}
`
-