Rooster Graph

Rooster Graph is a graph library for Scheme. Patterned after the popular Boost Graph Library for C++, it allows for a very clean separation between the graph container and graph algorithms. It does not have the complete functionality of the Boost Graph Library, but it does go a bit further by having both strict- and lazy-evaluated methods; the user of the graph has pause/continue/stop control and is not constrained by memory.

Rooster Graph uses Scheme macros to get the benefit of speed while having generic operations. It has only been implemented on CHICKEN Scheme, although porting it to other Scheme implementations would be quite easy.

Another Boost Graph Library implementation for a functional language is the Ruby Graph Library.

Rooster Graph is released under the modified BSD license, and no dependencies exist that make it incompatible with GPL software.

Latest version: 0.4.0

• Rooster Graph Documentation
• SAVANNAH Development Site
• License and Copyrights
• Distribution Archive
• CHICKEN Egg
• Development Archive

Future Directions

1. Graph containers backed by databases. The reference database will be Berkeley DB.
2. Export to the GXL format. This is one of the two standard graph formats (the other is GraphML, which has not been widely adopted).
   
3. More graph algorithms!

Sample

;; Adapted from
;; http://www.boost.org/libs/graph/doc/file_dependency_example.html

;; rgraph needs hygienic macro support.  Use "csi -hygienic" when
;; running the code.

(require-extension srfi-40 rgraph)

(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-adjacency-list myg1
  (fill-graph! 
   depth-first-search
   topological-sort 
   partition-fidmat)
  (vl-vector) (vertex-name vertex-color)
  (el-hash) (edge-weight)
  #t #t)

(define g1 (make-myg1))
(myg1-fill-graph! g1 used-by set-myg1-vertex-name!)

(print "Vertex order [list]:")
(for-each
 (lambda (v) (print (myg1-vertex-name g1 v)))
 (myg1-vertices g1))

(print "Topological sort [stream]:")
(stream-for-each
 (lambda (v) 
   (print (myg1-vertex-name g1 v)))
  (myg1-topological-sort* g1))

(print "add-vertex! add-edge! ...")
(define v1 (myg1-add-vertex! g1))
(define v2 (myg1-add-vertex! g1))
(define v3 (myg1-add-vertex! g1))
(define e1 (myg1-add-edge! g1 v1 v2))
(define e2 (myg1-add-edge! g1 v1 v3))
(define e3 (myg1-add-edge! g1 v2 v3))

(print "internal properties ...")
(set-myg1-vertex-name! g1 v1 "first vertex name")
(print (myg1-vertex-name g1 v1))
(print (myg1-vertex-name g1 v2))
(set-myg1-edge-weight! g1 e1 "first edge weight")
(print (myg1-edge-weight g1 e1))
(print (myg1-edge-weight g1 e2))

(print "out-edges ...")
(print (myg1-out-edges g1 v2))
(stream-for-each print (myg1-out-edges* g1 v1))

(print "in-edges ...")
(print (myg1-in-edges g1 v2))
(stream-for-each print (myg1-in-edges* g1 v3))

    

Tests

(require-extension srfi-40)
(require-extension rgraph-test1)
(require-extension rgraph-test2)
(require-extension rgraph-test3)