hemlock/alga.sls at a · jitwit/hemlock · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
;; (eval-when (compile) (optimize-level 3))

(library (alga)
  (export dfs
          bfs
          topological-sort
          acyclic?
          dag?
          scc
          scc-count

          ;; construction
          empty-graph
          vertex
          edge
          overlay
          connect
          connects
          connects*
          overlays
          overlays*

          ;; common graphs
          vertices
          vertices*
          edges
          path
          circuit
          bi-clique
          clique
          star
          stars

          ;; manipulation
          insert-vertex
          insert-edge
          transpose
          remove-self-loops
          induce

          ;; queries
          empty?
          vertex-list
          vertex-list-descending
          edge-list
          adjacent
          adjacent-descending
          incoming-edges
          incoming-edges-descending
          has-vertex?
          has-edge?
          vertex-count
          edge-count

          )
  (import (chezscheme)
          (prefix (batched-queue) q:)
          (prefix (patricia) t:)
          (prefix (patricia-set) s:))

  (define-syntax inc!
    (syntax-rules ()
      ((_ x)
       (set! x (fx1+ x)))))

  (define-syntax push!
    (syntax-rules ()
      ((_ x X)
       (set! X (cons x X)))))

  (define-syntax pop!
    (syntax-rules ()
      ((_ X)
       (let ((x (car X)))
         (set! X (cdr X))
         x))))

  (include "code/alga.scm")
  (include "code/graph-algorithms.scm")
  )