You are looking at historical revision 20087 of this page. It may differ significantly from its current revision.

## graph-bfs

Breadth-first search in a graph.

## Usage

(require-extension graph-bfs)

## Documentation

The graph-bfs library is an implementation of breadth-first search on a graph object that follows the API of e.g. the digraph egg.

### Breadth-first-search procedures

*[procedure]*

`graph-bfs-foreach:: G FNODE FEDGE ROOTS -> UNDEFINED`

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]*

`graph-bfs-fold:: G FNODE FEDGE ROOTS NODE-INIT EDGE-INIT -> NODE-STATE EDGE-STATE`

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]*

`graph-bfs-dist:: G ROOTS -> S32VECTOR * MAX-DIST`

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 (use 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) ((g 'add-node!) 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)))) ((g 'add-edge!) (list i j (format "~A->~A" ni nj))))) (else (error "invalid edge " e)))) used-by) (define roots (map car ((g 'roots)))) (graph-bfs-foreach g (lambda (n) (print (format "node ~A; " n))) (lambda (e) (print (format "edge ~A; " e))) roots) (graph-bfs-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

### Version history

- 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-2010 Ivan Raikov and the Okinawa Institute of Science and Technology 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/>.