You can edit this page using wiki syntax for markup.

Article contents:== Outdated egg! This is an egg for CHICKEN 4, the unsupported old release. You're almost certainly looking for [[/eggref/5/digraph|the CHICKEN 5 version of this egg]], if it exists. If it does not exist, there may be equivalent functionality provided by another egg; have a look at the [[https://wiki.call-cc.org/chicken-projects/egg-index-5.html|egg index]]. Otherwise, please consider porting this egg to the current version of CHICKEN. [[tags:egg]] == digraph Directed graph in adjacency list format. [[toc:]] == 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</procedure> 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 [[/users/ivan-raikov|Ivan Raikov]] === 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-2016 Ivan Raikov. 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/>. Description of your changes:

I would like to authenticate

Spam control

What do you get when you subtract 7 from 15?