(use eggdoc)
(define doc
`((eggdoc:begin
(name "graph-bfs")
(description "Breadth-first search in a graph.")
(author (url "mailto:iraikov@ece.gatech.edu" "Ivan Raikov"))
(history
(version "1.4" "License upgrade to GPL v3")
(version "1.3" "Minor updates to the setup script")
(version "1.2" "Added support for chicken-setup -test")
(version "1.1" "Clarification in the section on graph-bfs-dist")
(version "1.0" "Initial release"))
(requires (url "iset.html" "iset"))
(usage "(require-extension graph-bfs)")
(download "graph-bfs.egg")
(documentation
(p "The graph-bfs library is an implementation of breadth-first search "
"on a graph object that follows the API of e.g. the " (url "digraph.html" "digraph egg")
".")
(subsection "Breadth-first-search procedures"
(procedure "graph-bfs-foreach:: G FNODE FEDGE ROOTS -> UNDEFINED"
(p "breadth-first search iterator; given a list of initial nodes, " (tt "ROOTS") ", "
"the successors of each initial node are visited in breadth-first search order, "
"and procedures " (tt "FNODE") " and " (tt "FEDGE") " are applied to "
"each node or edge, respectively, as the graph is traversed. "
(tt "FNODE") " is of the form " (tt "LAMBDA N -> _") " where " (tt "N")
" is node number; and " (tt "FEDGE") " is of the form "
(tt "LAMBDA EDGE") " where " (tt "EDGE") " is a list of the form "
(tt "(I J INFO)") "; " (tt "I") " and " (tt "J") " are the nodes defining "
"the edge, and " (tt "INFO") " is edge metadata."))
(procedure "graph-bfs-fold:: G FNODE FEDGE ROOTS NODE-INIT EDGE-INIT -> NODE-STATE EDGE-STATE"
(p "breadth-first search iterator with state; given a list of initial nodes, "
(tt "ROOTS") ", and initial node state and edge state, " (tt "NODE-INIT") " and "
(tt "EDGE-INIT") " the successors of each initial node are visited in "
"breadth-first search order, and procedures " (tt "FNODE") " and " (tt "FEDGE")
" are applied to each node and the node state, or edge and the edge state, "
"respectively, as the graph is traversed. "
(tt "FNODE") " is of the form " (tt "LAMBDA N NODE-STATE -> NODE-STATE")
" where " (tt "N") " is node number, and NODE-STATE can be of arbitrary type and "
"must of the same type as " (tt "NODE-INIT") ". "
(tt "FEDGE") " is of the form " (tt "LAMBDA EDGE EDGE-STATE") " where "
(tt "EDGE") " is a list of the form " (tt "(I J INFO)") "; "
(tt "I") " and " (tt "J") " are the nodes defining the edge, and "
(tt "INFO") " is edge metadata; " (tt "EDGE-STATE") " must be of the same type "
"as " (tt "EDGE-INIT")))
(procedure "graph-bfs-dist:: G ROOTS -> S32VECTOR * MAX-DIST"
(p "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 " (tt "S32VECTOR") " and "
(tt "MAX-DIST") " is the maximum distance computed."))))
(examples (pre #<~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))
EOF
)
(license
"Copyright 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
."))))
(if (eggdoc->html doc) (void))