source: project/wiki/eggref/4/digraph @ 20024

Last change on this file since 20024 was 20024, checked in by Ivan Raikov, 11 years ago

digraph doc updated for release 1.12

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