source: project/digraph/tags/1.7a/digraph-eggdoc.scm @ 7359

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

Created releases with new author URL.

File size: 8.0 KB
Line 
1
2(use eggdoc)
3
4(define doc
5  `((eggdoc:begin
6     (name "digraph")
7     (description "Directed graph in adjacency list format.")
8     (author (url "http://chicken.wiki.br/ivan raikov" "Ivan Raikov"))
9
10     (history 
11      (version "1.7" "Build script updated for better cross-platform compatibility")
12      (version "1.6" "Test infrastructure changed to use testbase")
13      (version "1.5" "Bug fixes in set-out-edges! and set-in-edges! [thanks to Andreas Scholta]")
14      (version "1.4" "License upgrade to GPL v3")
15      (version "1.3" "Updated the roots procedure to match the documentation")
16      (version "1.2" "Minor changes to the setup script")
17      (version "1.1" "Added support for chicken-setup -test")
18      (version "1.0" "Initial release"))
19
20     (requires (url "dyn-vector.html" "dyn-vector"))
21
22     (usage "(require-extension digraph)")
23
24     (download "digraph.egg")
25
26     (documentation
27     
28      (p "The digraph library is an implementation of a directed "
29         "graph, where the edges are stored as adjacency lists "
30         "indexed by node number.")
31
32      (p "The library defines a digraph \"object\" -- a procedure that "
33         "takes a method name as a symbol, and returns the procedure that "
34         "implements the respective operation.")
35
36      (subsection "Directed graph procedures"
37
38          (p "The digraph object is created by procedure " (tt "make-digraph")
39             ", which is the only user-visible procedure defined in this egg: ")
40
41          (procedure "make-digraph:: NAME INFO [NODE-LIST [SUCC-LIST [PRED-LIST]]] -> SELECTOR"
42                     (p "where " (tt "NAME") " is the graph name (string or symbol), "
43                        (tt "INFO") " is an optional metadata object of an arbitrary type "
44                        "or " (tt "#f") "; " (tt ("NODE-LIST")) 
45                        " is an optional list of nodes to be inserted in the graph; "
46                        "each element of the list must be of the form " (tt "(N INFO)") 
47                        " where " (tt "N") " is a unique node number (integer), and " (tt "INFO")
48                        " is an optional metadata object describing the node. "
49                        "Similarly, " (tt "SUCC-LIST") " and " (tt "PRED-LIST") " can be used "
50                        " to define the graph edges upon graph creation. If supplied, these arguments "
51                        "must be lists in which every element is of the form "
52                        (tt "(I J INFO)") ", where " (tt "I") " and " (tt "J") " are node numbers, "
53                        "and " (tt "INFO") " is an optional metadata object."))
54                       
55          (p "The returned selector procedure can take one of the following arguments: "
56             (symbol-table 
57              (describe "'name"       "returns the graph name (string or symbol)")
58              (describe "'info"       "returns the graph metadata (arbitrary type)")
59              (describe "'new-id!"    ("returns a procedure with no arguments, "
60                                       "which returns the lowest available node number"))
61              (describe "'add-node!"  ("returns a procedure " (tt "LAMBDA N INFO") 
62                                       " which inserts in the graph node with number " (tt "N")
63                                       " and metadata " (tt "INFO") "; if the node already "
64                                       "exists in the graph, it will be overwritten with the "
65                                       "new metadata"))
66              (describe "'add-edge!" ("returns a procedure " (tt "LAMBDA EDGE") 
67                                       " which inserts in the graph the specifed edge; "
68                                       "the edge is given by a list of the form "
69                                       (tt "(I J INFO)") ", where " (tt "I") " and " (tt "J")
70                                       " are source and destination nodes, respectively, and "
71                                       (tt "INFO") " is edge metadata of arbitrary type"))
72              (describe "'remove-node!" ("returns a procedure " (tt "LAMBDA N") 
73                                         " which removes node " (tt "N") 
74                                         " and all its edges from the graph"))
75              (describe "'nodes"       ("returns a procedure with no arguments, "
76                                        "which returns a list with the nodes of the graph "
77                                        "and their metadata"))
78              (describe "'edges"       ("returns a procedure with no arguments, "
79                                        "which returns a list with the edges of the graph "
80                                        "and their metadata"))
81              (describe "'roots"       ("returns a procedure with no arguments, "
82                                        "which returns a list with all nodes in the graph "
83                                        "that do not have an predecessor"))
84              (describe "'order"       ("returns a procedure with no arguments, "
85                                        "which returns the number of nodes in the graph"))
86              (describe "'size"        ("returns a procedure with no arguments, "
87                                        "which returns the number of edges in the graph"))
88              (describe "'capacity"    ("returns a procedure with no arguments, "
89                                        "which returns the size of the underlying dynamic vector"))
90              (describe "'succ"        ("returns a procedure " (tt "LAMBDA N")
91                                        " which returns a list with the successor nodes of node " (tt "N")))
92              (describe "'pred"        ("returns a procedure " (tt "LAMBDA N")
93                                        " which returns a list with the predecessor nodes of node " (tt "N")))
94              (describe "'out-edges"   ("returns a procedure " (tt "LAMBDA N")
95                                        " which returns a list with the outgoing edges of node " (tt "N")))
96              (describe "'in-edges"    ("returns a procedure " (tt "LAMBDA N")
97                                        " which returns a list with the incoming edges of node " (tt "N")))
98              (describe "'has-edge"    ("returns a procedure " (tt "LAMBDA I J")
99                                        " which returns true if edge " (tt "I -> J") " exists in the graph "
100                                        "and false otherwise"))
101              (describe "'has-node"    ("returns a procedure " (tt "LAMBDA N")
102                                        " which returns true if node " (tt "N") " exists in the graph "
103                                        "and false otherwise"))
104              (describe "'node-info"   ("returns a procedure " (tt "LAMBDA N")
105                                        " which returns the metadata for node " (tt "N")))
106              (describe "'foreach-node"  ("returns an iterator procedure " (tt "LAMBDA F")
107                                          " which iterates over the nodes in the graph "
108                                          "by invoking function " (tt "F") " on the node number and metadata "
109                                          "of each node"))
110              (describe "'foreach-edge" ("returns an iterator procedure " (tt "LAMBDA F")
111                                          " which iterates over the edges in the graph "
112                                          "by invoking function " (tt "F") " on each edge"))
113              (describe "'debug"        ("returns a list with the internal representation of the graph"))))))
114
115     (examples (pre #<<EOF
116;; example adapted from graph example in the Boost library documentation
117(require-extension srfi-1)
118(require-extension digraph)
119(define g (make-digraph 'depgraph "dependency graph"))
120
121(define used-by
122   (list
123     (cons 'dax_h 'foo_cpp) (cons 'dax_h 'bar_cpp) (cons 'dax_h 'yow_h)
124     (cons 'yow_h 'bar_cpp) (cons 'yow_h 'zag_cpp) (cons 'boz_h 'bar_cpp)
125     (cons 'boz_h 'zig_cpp) (cons 'boz_h 'zag_cpp) (cons 'zow_h 'foo_cpp)
126     (cons 'foo_cpp 'foo_o) (cons 'foo_o 'libfoobar_a) 
127     (cons 'bar_cpp 'bar_o) (cons 'bar_o 'libfoobar_a) 
128     (cons 'libfoobar_a 'libzigzag_a) (cons 'zig_cpp 'zig_o) 
129     (cons 'zig_o 'libzigzag_a) (cons 'zag_cpp 'zag_o) 
130     (cons 'zag_o 'libzigzag_a) (cons 'libzigzag_a 'killerapp)))
131
132
133(define node-list (delete-duplicates 
134                   (concatenate (list (map car used-by) (map cdr used-by)))))
135
136(define node-ids (list-tabulate (length node-list) values))
137 
138(for-each (lambda (i n) ((g 'add-node!) i n)) node-ids node-list)
139(define node-map (zip node-list node-ids))
140
141(for-each (lambda (e) 
142            (match e ((ni . nj) (let ((i (car (alist-ref ni node-map)))
143                                      (j (car (alist-ref nj node-map))))
144                                  ((g 'add-edge!) (list i j (format "~A->~A" ni nj)))))
145                   (else (error "invalid edge " e))))
146          used-by)
147(print ((g 'nodes)))
148(print ((g 'edges)))
149
150((g 'remove-node!) 0)
151(print ((g 'nodes)))
152(print ((g 'edges)))
153EOF
154)
155     (license
156      "Copyright Ivan Raikov and the Okinawa Institute of Science and Technology
157
158This program is free software: you can redistribute it and/or modify
159it under the terms of the GNU General Public License as published by
160the Free Software Foundation, either version 3 of the License, or (at
161your option) any later version.
162
163This program is distributed in the hope that it will be useful, but
164WITHOUT ANY WARRANTY; without even the implied warranty of
165MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
166General Public License for more details.
167
168A full copy of the GPL license can be found at
169<http://www.gnu.org/licenses/>.")))))
170
171(if (eggdoc->html doc) (void))
Note: See TracBrowser for help on using the repository browser.