(use eggdoc)

(define doc
  `((eggdoc:begin
     (name "graph-bfs")
     (description "Breadth-first search in a graph.")
     (author (url "http://chicken.wiki.br/users/ivan-raikov" "Ivan Raikov"))

     (history 
      (version "1.11" "Added digraph and test as test-dependencies")
      (version "1.9" "Ported to Chicken 4")
      (version "1.8" "Now using matchable extension")
      (version "1.7" "Unit tests updated to use testbase")
      (version "1.6" "Build script updated for better cross-platform compatibility")
      (version "1.5" "eggdoc documentation fix")
      (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")
	       (url "matchable.html" "matchable"))

     (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 #<<EOF
;; example adapted from graph example in the Boost library documentation
(require-extension srfi-1)
(require-extension digraph)
(require-extension 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))
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
<http://www.gnu.org/licenses/>.")))))

(if (eggdoc->html doc) (void))