graph-scc

Computes strongly-connected components (SCC) of a graph.

  1. graph-scc
  2. Documentation
    1. SCC procedures
  3. Examples
  4. About this egg
    1. Author
    2. Repository
    3. Version history
    4. License

Documentation

The graph-scc library computes the strongly connected components (SCC) of a graph, using Tarjan's algorithm, and a graph object that follows the API of e.g. the digraph egg.

SCC procedures

[procedure] fold:: G F INITIAL -> STATE

SCC graph iterator; every SCC is represented as a list of nodes. the nodes in each SCC are folded together using the user-supplied function F, which is of the form LAMBDA SCC STATE

Examples

 
;; example adapted from graph example in the Boost library documentation
(import srfi-1 digraph graph-scc)

(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 'libfoobar_a 'dax_h) (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)

(define roots (map car (roots g)))

;; accumulate all SCC in a list 
(fold g (lambda (scc ax) (cons scc ax)) (list))

About this egg

Author

Ivan Raikov

Repository

https://github.com/iraikov/chicken-graph-scc

Version history
2.0
Ported to CHICKEN 5 and yasos-based graph interface
1.9
Documentation converted to wiki format
1.8
Ported to Chicken 4
1.7
Now using matchable extension
1.6
Updated meta file for testbase
1.5
Updated units tests to use testbase
1.4
Build script updated for better cross-platform compatibility
1.3
eggdoc documentation fix
1.2
License upgrade to GPL v3.
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/>.