source: project/graph-bfs/tags/1.4/graph-bfs-eggdoc.scm @ 7359

Last change on this file since 7359 was 4885, checked in by Ivan Raikov, 13 years ago

Created release 1.4

File size: 5.3 KB
Line 
1
2(use eggdoc)
3
4(define doc
5  `((eggdoc:begin
6     (name "graph-bfs")
7     (description "Breadth-first search in a graph.")
8     (author (url "mailto:iraikov@ece.gatech.edu" "Ivan Raikov"))
9
10     (history 
11      (version "1.4" "License upgrade to GPL v3")
12      (version "1.3" "Minor updates to the setup script")
13      (version "1.2" "Added support for chicken-setup -test")
14      (version "1.1" "Clarification in the section on graph-bfs-dist")
15      (version "1.0" "Initial release"))
16
17     (requires (url "iset.html" "iset"))
18
19     (usage "(require-extension graph-bfs)")
20
21     (download "graph-bfs.egg")
22
23     (documentation
24     
25      (p "The graph-bfs library is an implementation of breadth-first search "
26         "on a graph object that follows the API of e.g. the " (url "digraph.html" "digraph egg")
27         ".")
28
29      (subsection "Breadth-first-search procedures"
30
31          (procedure "graph-bfs-foreach:: G FNODE FEDGE ROOTS -> UNDEFINED"
32                     (p "breadth-first search iterator; given a list of initial nodes, " (tt "ROOTS") ", "
33                        "the successors of each initial node are visited in breadth-first search order, "
34                        "and procedures " (tt "FNODE") " and " (tt "FEDGE") " are applied to "
35                        "each node or edge, respectively, as the graph is traversed. "
36                        (tt "FNODE") " is of the form " (tt "LAMBDA N -> _") " where " (tt "N") 
37                        " is node number; and " (tt "FEDGE") " is of the form " 
38                        (tt "LAMBDA EDGE") " where " (tt "EDGE") " is a list of the form "
39                        (tt "(I J INFO)") "; " (tt "I") " and " (tt "J") " are the nodes defining "
40                        "the edge, and " (tt "INFO") " is edge metadata."))
41
42          (procedure "graph-bfs-fold:: G FNODE FEDGE ROOTS NODE-INIT EDGE-INIT -> NODE-STATE EDGE-STATE"
43                     (p "breadth-first search iterator with state; given a list of initial nodes, " 
44                        (tt "ROOTS") ", and initial node state and edge state, " (tt "NODE-INIT") " and "
45                        (tt "EDGE-INIT") " the successors of each initial node are visited in "
46                        "breadth-first search order, and procedures " (tt "FNODE") " and " (tt "FEDGE") 
47                        " are applied to each node and the node state, or edge and the edge state, "
48                        "respectively, as the graph is traversed. "
49                        (tt "FNODE") " is of the form " (tt "LAMBDA N NODE-STATE -> NODE-STATE") 
50                        " where " (tt "N")  " is node number, and NODE-STATE can be of arbitrary type and "
51                        "must of the same type as " (tt "NODE-INIT") ". " 
52                        (tt "FEDGE") " is of the form " (tt "LAMBDA EDGE EDGE-STATE") " where " 
53                        (tt "EDGE") " is a list of the form " (tt "(I J INFO)") "; " 
54                        (tt "I") " and " (tt "J") " are the nodes defining the edge, and " 
55                        (tt "INFO") " is edge metadata; " (tt "EDGE-STATE") " must be of the same type "
56                        "as " (tt "EDGE-INIT")))
57
58          (procedure "graph-bfs-dist:: G ROOTS -> S32VECTOR * MAX-DIST"
59                     (p "breadth-first search distance; this procedure computes BFS "
60                        "maximum distance from a root node for all successors "
61                        "of the given initial nodes, and the maximum distance from root "
62                        "across all nodes traversed. The node distances are returned in "
63                        " an SRFI-4 vector of type " (tt "S32VECTOR") " and "
64                        (tt "MAX-DIST") " is the maximum distance computed."))))
65
66     (examples (pre #<<EOF
67;; example adapted from graph example in the Boost library documentation
68(require-extension srfi-1)
69(require-extension digraph)
70(require-extension graph-bfs)
71
72(define g (make-digraph 'depgraph "dependency graph"))
73
74(define used-by
75   (list
76     (cons 'dax_h 'foo_cpp) (cons 'dax_h 'bar_cpp) (cons 'dax_h 'yow_h)
77     (cons 'yow_h 'bar_cpp) (cons 'yow_h 'zag_cpp) (cons 'boz_h 'bar_cpp)
78     (cons 'boz_h 'zig_cpp) (cons 'boz_h 'zag_cpp) (cons 'zow_h 'foo_cpp)
79     (cons 'foo_cpp 'foo_o) (cons 'foo_o 'libfoobar_a) 
80     (cons 'bar_cpp 'bar_o) (cons 'bar_o 'libfoobar_a) 
81     (cons 'libfoobar_a 'libzigzag_a) (cons 'zig_cpp 'zig_o) 
82     (cons 'zig_o 'libzigzag_a) (cons 'zag_cpp 'zag_o) 
83     (cons 'zag_o 'libzigzag_a) (cons 'libzigzag_a 'killerapp)))
84
85
86(define node-list (delete-duplicates 
87                   (concatenate (list (map car used-by) (map cdr used-by)))))
88
89(define node-ids (list-tabulate (length node-list) values))
90 
91(for-each (lambda (i n) ((g 'add-node!) i n)) node-ids node-list)
92(define node-map (zip node-list node-ids))
93
94(for-each (lambda (e) 
95            (match e ((ni . nj) (let ((i (car (alist-ref ni node-map)))
96                                      (j (car (alist-ref nj node-map))))
97                                  ((g 'add-edge!) (list i j (format "~A->~A" ni nj)))))
98                   (else (error "invalid edge " e))))
99          used-by)
100
101(define roots (map car ((g 'roots))))
102
103(graph-bfs-foreach g 
104           (lambda (n) (print (format "node ~A; " n)))
105           (lambda (e) (print (format "edge ~A; " e)))
106           roots)
107
108(graph-bfs-fold g 
109               (lambda (n ax) (cons (list 'node n) ax)) 
110               (lambda (e ax) (cons (list 'edge e) ax)) 
111               roots (list) (list))
112EOF
113)
114     (license
115      "Copyright Ivan Raikov and the Okinawa Institute of Science and Technology
116
117This program is free software: you can redistribute it and/or modify
118it under the terms of the GNU General Public License as published by
119the Free Software Foundation, either version 3 of the License, or (at
120your option) any later version.
121
122This program is distributed in the hope that it will be useful, but
123WITHOUT ANY WARRANTY; without even the implied warranty of
124MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
125General Public License for more details.
126
127A full copy of the GPL license can be found at
128<http://www.gnu.org/licenses/>."))))
129
130(if (eggdoc->html doc) (void))
Note: See TracBrowser for help on using the repository browser.