I wrote a simple/naive graph traversal in breadth-first, and then was playing with it to apply a simple tree, instead of a structured graph that easily bends itself to this function. I'm afraid I'm having difficulty coming up with a get-children lambda that'll yield the result I want, and it seems to be a nice brain-teaser to have a go at. Here it is:
The breadth-first function is:
(defun run-breadth-first (node fn get-children)
"Run fn breadth-first starting from node, traversing the whole tree."
(let ((queue (list node)))
(loop for i = (first queue)
for inners = (if i (funcall get-children i) nil)
until (null i)
when inners do (setf queue (append queue inners))
do
(funcall fn i)
(pop queue))))
Btw, if anyone is wondering why I'm doing this, because I found it a nice abstraction to apply, and have a find call of one line to do a search as such:
(run-breadth-first sg-node #'find-sg-at-aux #'inner-nodes)
Now the difficulty I'm having is, I'd like to see this run with a regular list, instead of a custom graph structure with get-children functions returning a list of children. Here is an attempt with a simple 5-am test syntax:
(test run-breadth-first.test.list
(let (output)
(run-breadth-first '(1 2 (3 (4.1 4.2)) 5 (6 (6.1)) 7)
(lambda (node) (push (first node) output))
(lambda (node) (if (atom (first node))
(list (rest node))
(list (append (rest node) (first node)))))))
(is (equal output (reverse '(1 2 5 7 3 6 4.1 4.2 6.1)))))
But when you run the statement inside, which is here for easy copying and separation:
(let (output)
(run-breadth-first '(1 2 (3 (4.1 4.2)) 5 (6 (6.1)) 7)
(lambda (node) (push (first node) output))
(lambda (node) (if (atom (first node))
(list (rest node))
(list (append (rest node) (first node))))))
output)
it returns:
(6.1 4.2 4.1 #1=(6.1) 6 #2=(4.1 4.2) 3 7 (6 #1#) 5 (3 #2#) 2 1)
The order of elements are correct, except the inner-lists. I'm yet to find a way to give me the result:
(6.1 4.2 4.1 6 3 7 5 2 1)
Could anyone see a solution?
Apparently, using just lambda functions was taking the valuable tool 'trace' away, and writing the function explicitly helped me shape it further.
Here is one function that'll give the correct result:
(defun get-list-children (node)
(if (atom (first node))
(if (atom (second node))
(list (rest node))
(list (append (rest (rest node)) (second node))))
(list (append (rest node) (first node)))))
then call it:
(let (output)
(run-breadth-first '(1 2 (3 (4.1 4.2)) 5 (6 (6.1)) 7)
(lambda (node) (push (first node) output))
#'get-list-children)
output)