You are looking at historical revision 29768 of this page. It may differ significantly from its current revision.

## digraph

Directed graph in adjacency list format.

## Usage

(require-extension digraph)

## Documentation

The `digraph` library is an implementation of a directed graph, where the edges are stored as adjacency lists indexed by node number.

The library defines a digraph "object" -- a procedure that takes a method name as a symbol, and returns the procedure that implements the respective operation.

### Directed graph procedures

The digraph object is created by procedure `make-digraph`, which is the only user-visible procedure defined in this egg:

*[procedure]*

`make-digraph:: NAME INFO [NODE-LIST [SUCC-LIST [PRED-LIST]]] -> SELECTOR`

where:

`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.`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.

The returned selector procedure can take one of the following arguments:

`'name`- returns the graph name (string or symbol)
`'info`- returns the graph metadata (arbitrary type)
`'new-id!`- returns a procedure with no arguments, which returns the lowest available node number
`'add-node!`- 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 `'add-edge!`- 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 `'remove-node!`- returns a procedure
`LAMBDA N`which removes node`N`and all its edges from the graph `'nodes`- returns a procedure with no arguments, which returns a list with the nodes of the graph and their metadata
`'edges`- returns a procedure with no arguments, which returns a list with the edges of the graph and their metadata
`'roots`- returns a procedure with no arguments, which returns a list with all nodes in the graph that do not have an predecessor
`'terminals`- returns a procedure with no arguments, which returns a list with all nodes in the graph that do not have a successor
`'order`- returns a procedure with no arguments, which returns the number of nodes in the graph
`'size`- returns a procedure with no arguments, which returns the number of edges in the graph
`'capacity`- returns a procedure with no arguments, which returns the size of the underlying dynamic vector
`'succ`- returns a procedure
`LAMBDA N`which returns a list with the successor nodes of node`N` `'pred`- returns a procedure
`LAMBDA N`which returns a list with the predecessor nodes of node`N` `'succ-list`- returns a procedure with no arguments which returns a list containing the successor nodes for each node.
`'pred-list`- returns a procedure with no arguments which returns a list containing the predecessor nodes for each node.
`'out-edges`- returns a procedure
`LAMBDA N`which returns a list with the outgoing edges of node`N` `'in-edges`- returns a procedure
`LAMBDA N`which returns a list with the incoming edges of node`N` `'has-edge`- returns a procedure
`LAMBDA I J`which returns true if edge`I -> J`exists in the graph and false otherwise `'has-node`- returns a procedure
`LAMBDA N`which returns true if node`N`exists in the graph and false otherwise `'node-info`- returns a procedure
`LAMBDA N`which returns the metadata for node`N` `'node-info-set!`- returns a procedure
`LAMBDA N V`which sets the metadata for node`N` `'foreach-node`- 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 `'foreach-edge`- returns an iterator procedure
`LAMBDA F`which iterates over the edges in the graph by invoking function`F`on each edge `'debug`- returns a list with the internal representation of the graph

## Examples

;; example adapted from graph example in the Boost library documentation (require-extension srfi-1 digraph matchable) (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) (print ((g 'nodes))) (print ((g 'edges))) ((g 'remove-node!) 0) (print ((g 'nodes))) (print ((g 'edges)))

## About this egg

### Author

### Version history

- 1.16
- Added terminals message to digraph object
- 1.15
- Ensure unit test script return proper exit code
- 1.13
- Added test as a test dependency
- 1.12
- Converted documentation to wiki format
- 1.11
- Ported to Chicken 4
- 1.10
- Now using matchable extension
- 1.9
- Added procedures pred-list and succ-list
- 1.8
- Added procedure node-info-set!
- 1.7
- Build script updated for better cross-platform compatibility
- 1.6
- Test infrastructure changed to use testbase
- 1.5
- Bug fixes in set-out-edges! and set-in-edges! [thanks to Andreas Scholta]
- 1.4
- License upgrade to GPL v3
- 1.3
- Updated the roots procedure to match the documentation
- 1.2
- Minor changes to the setup script
- 1.1
- Added support for chicken-setup -test
- 1.0
- Initial release

### License

Copyright 2007-2012 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/>.