chickadee » digraph

digraph

Directed graph in adjacency list format.

Documentation

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

The present version implements a yasos object that provides a number of methods for graph operations.

Directed graph procedures

The digraph object is created by procedure make-digraph:

make-digraph: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 yasos object supports the following operations:

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!
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!
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!
procedure LAMBDA N which removes node N and all its edges from the graph
nodes
returns a list with the nodes of the graph and their metadata
edges
returns a list with the edges of the graph and their metadata
roots
returns a list with all nodes in the graph that do not have an predecessor
terminals
which returns a list with all nodes in the graph that do not have a successor
order
returns the number of nodes in the graph
size
returns the number of edges in the graph
capacity
returns the size of the underlying dynamic vector
succ
procedure LAMBDA N which returns a list with the successor nodes of node N
pred
procedure LAMBDA N which returns a list with the predecessor nodes of node N
succ-list
returns a list containing the successor nodes for each node.
pred-list
returns a list containing the predecessor nodes for each node.
out-edges
procedure LAMBDA N which returns a list with the outgoing edges of node N
in-edges
procedure LAMBDA N which returns a list with the incoming edges of node N
has-edge
procedure LAMBDA I J which returns true if edge I -> J exists in the graph and false otherwise
has-node
procedure LAMBDA N which returns true if node N exists in the graph and false otherwise
node-info
procedure LAMBDA N which returns the metadata for node N
node-info-set!
procedure LAMBDA N V which sets the metadata for node N
foreach-node
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
procedure LAMBDA F which iterates over the edges in the graph by invoking function F on each edge

Examples

;; example adapted from graph example in the Boost library documentation
(import 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) (add-node! g 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))))
				  (add-edge! g (list i j (format "~A->~A" ni nj)))))
		   (else (error "invalid edge " e))))
	  used-by)
(print (nodes g))
(print (edges g))

(remove-node! g 0)
(print (nodes g))
(print (edges g))

About this egg

Author

Ivan Raikov

Repository

https://github.com/iraikov/chicken-digraph

Version history

2.0
Ported to CHICKEN 5 and yasos
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-2018 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/>.

Contents »