You can edit this page using wiki syntax for markup.

Article contents:[[tags:egg]] == graph-bfs Breadth-first search in a graph. [[toc:]] == Documentation The graph-bfs library is an implementation of breadth-first search on a directed graph object that follows the API of the [[digraph|digraph egg]]. === Breadth-first-search procedures <procedure>foreach:: G FNODE FEDGE ROOTS -> UNDEFINED</procedure> Breadth-first search iterator; given a list of initial nodes, {{ROOTS}}, the successors of each initial node are visited in breadth-first search order, and procedures {{FNODE}} and {{FEDGE}} are applied to each node or edge, respectively, as the graph is traversed. {{FNODE}} is of the form {{LAMBDA N -> _}} where {{N}} is node number; and {{FEDGE}} is of the form {{LAMBDA EDGE}} where {{EDGE}} is a list of the form {{(I J INFO)}}; {{I}} and {{J}} are the nodes defining the edge, and {{INFO}} is edge metadata. <procedure>fold:: G FNODE FEDGE ROOTS NODE-INIT EDGE-INIT -> NODE-STATE EDGE-STATE</procedure> Breadth-first search iterator with state; given a list of initial nodes, {{ROOTS}}, and initial node state and edge state, {{NODE-INIT}} and {{EDGE-INIT}} the successors of each initial node are visited in breadth-first search order, and procedures {{FNODE}} and {{FEDGE}} are applied to each node and the node state, or edge and the edge state, respectively, as the graph is traversed. {{FNODE}} is of the form {{LAMBDA N NODE-STATE -> NODE-STATE}} where {{N}} is node number, and NODE-STATE can be of arbitrary type and must of the same type as {{NODE-INIT}}. {{FEDGE}} is of the form {{LAMBDA EDGE EDGE-STATE}} where {{EDGE}} is a list of the form {{(I J INFO)}}; {{I}} and {{J}} are the nodes defining the edge, and {{INFO}} is edge metadata; {{EDGE-STATE}} must be of the same type as {{EDGE-INIT}} <procedure>dist:: G ROOTS -> S32VECTOR * MAX-DIST</procedure> Breadth-first search distance; this procedure computes BFS maximum distance from a root node for all successors of the given initial nodes, and the maximum distance from root across all nodes traversed. The node distances are returned in an SRFI-4 vector of type {{S32VECTOR}} and {{MAX-DIST}} is the maximum distance computed. == Examples ;; example adapted from graph example in the Boost library documentation (import scheme (chicken base) (chicken format) srfi-1 digraph graph-bfs) (define g (make-digraph 'depgraph "dependency graph")) (define used-by (list (cons 'dax_h 'foo_cpp) (cons 'dax_h 'bar_cpp) (cons 'dax_h 'yow_h) (cons 'yow_h 'bar_cpp) (cons 'yow_h 'zag_cpp) (cons 'boz_h 'bar_cpp) (cons 'boz_h 'zig_cpp) (cons 'boz_h 'zag_cpp) (cons 'zow_h 'foo_cpp) (cons 'foo_cpp 'foo_o) (cons 'foo_o 'libfoobar_a) (cons 'bar_cpp 'bar_o) (cons 'bar_o 'libfoobar_a) (cons 'libfoobar_a 'libzigzag_a) (cons 'zig_cpp 'zig_o) (cons 'zig_o 'libzigzag_a) (cons 'zag_cpp 'zag_o) (cons 'zag_o 'libzigzag_a) (cons 'libzigzag_a 'killerapp))) (define node-list (delete-duplicates (concatenate (list (map car used-by) (map cdr used-by))))) (define node-ids (list-tabulate (length node-list) values)) (for-each (lambda (i n) (add-node! g i n)) node-ids node-list) (define node-map (zip node-list node-ids)) (for-each (lambda (e) (match e ((ni . nj) (let ((i (car (alist-ref ni node-map))) (j (car (alist-ref nj node-map)))) (add-edge! g (list i j (format "~A->~A" ni nj))))) (else (error "invalid edge " e)))) used-by) (define roots (map car (roots g))) (foreach g (lambda (n) (print (format "node ~A; " n))) (lambda (e) (print (format "edge ~A; " e))) roots) (fold g (lambda (n ax) (cons (list 'node n) ax)) (lambda (e ax) (cons (list 'edge e) ax)) roots (list) (list)) == About this egg === Author [[/users/ivan-raikov|Ivan Raikov]] === Repository [[https://github.com/iraikov/chicken-graph-bfs|https://github.com/iraikov/chicken-graph-bfs]] === Version history ; 2.1 : Removed srfi-13 as a test dependency ; 2.0 : Ported to CHICKEN 5 and yasos-based interface ; 1.13 : Ensure that test script returns proper exit code ; 1.12 : Documentation converted to wiki format ; 1.11 : Added digraph and test as test-dependencies ; 1.9 : Ported to Chicken 4 ; 1.8 : Now using matchable extension ; 1.7 : Unit tests updated to use testbase ; 1.6 : Build script updated for better cross-platform compatibility ; 1.5 : eggdoc documentation fix ; 1.4 : License upgrade to GPL v3 ; 1.3 : Minor updates to the setup script ; 1.2 : Added support for chicken-setup -test ; 1.1 : Clarification in the section on graph-bfs-dist ; 1.0 : Initial release === License Copyright 2007-2018 Ivan Raikov This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. A full copy of the GPL license can be found at <http://www.gnu.org/licenses/>. Description of your changes:

I would like to authenticate

Spam control

What do you get when you multiply 9 by 9?