Racket Generic Graph Library
1 Generic Graph Interface
gen:  graph
graph?
has-vertex?
has-edge?
vertex=?
add-vertex!
remove-vertex!
rename-vertex!
add-edge!
add-directed-edge!
remove-edge!
remove-directed-edge!
get-vertices
in-vertices
get-neighbors
in-neighbors
get-edges
in-edges
edge-weight
transpose
graph-copy
graph-union!
2 Graph Constructors
2.1 Unweighted Graphs
unweighted-graph?
unweighted-graph/  undirected
unweighted-graph/  directed
unweighted-graph/  adj
2.2 Weighted Graphs
weighted-graph?
weighted-graph/  undirected
weighted-graph/  directed
undirected-graph
directed-graph
2.3 Matrix Graphs
matrix-graph?
matrix-graph
3 Graph properties
define-vertex-property
define-edge-property
4 Basic Graph Functions
4.1 Breadth-first Search
bfs
bfs/  generalized
do-bfs
fewest-vertices-path
4.2 Depth-first Search
dfs
dfs/  generalized
do-dfs
dag?
tsort
cc
cc/  bfs
scc
5 Minimum Spanning Tree
mst-kruskal
mst-prim
6 Single-source Shortest Paths
bellman-ford
dijkstra
dag-shortest-paths
7 All-pairs Shortest Paths
floyd-warshall
transitive-closure
johnson
8 Graph Coloring
coloring
coloring/  greedy
coloring/  brelaz
order-smallest-last
valid-coloring?
9 Maximum Flow
maxflow
bipartite?
maximum-bipartite-matching
10 Graphviz
graphviz
11 Other
$v
$from
$to
$discovered?
$seen?
$visited?
$broke?
$acc
Bibliography
7.1

Racket Generic Graph Library

Stephen Chang <[email protected]>

 (require graph) package: graph

Generic graph library for Racket.

Requires Racket 5.3.2 or later (due to define-generics and enqueue-front! in data/queue).

1 Generic Graph Interface

value

gen:graph : any/c

A generic interface (see Generic Interfaces) that defines a graph. To supply method implementations, a struct should use the #:methods form.

procedure

(graph? g)  boolean?

  g : any/c
Returns #t if g implements gen:graph (ie, is a graph) and #f otherwise.

A graph has the following methods:

2 Graph Constructors

2.1 Unweighted Graphs

See also the directed-graph and undirected-graph constructors, which create either a weighted or unweighted graph.

procedure

(unweighted-graph? g)  boolean?

  g : any/c
Indicates whether a graph is an unweighted graph.

procedure

(unweighted-graph/undirected edges)

  (and/c graph? unweighted-graph?)
  edges : (listof (list/c any/c any/c))
Creates an unweighted graph that implements gen:graph from a list of undirected edges. Each edge is represented by a list of two vertices. Vertices can be any Racket values comparable with equal?.

Examples:
> (define g (unweighted-graph/undirected '((a b) (c d))))
> (graph? g)

#t

> (unweighted-graph? g)

#t

> (has-edge? g 'a 'b)

#t

> (has-edge? g 'b 'a)

#t

procedure

(unweighted-graph/directed edges)

  (and/c graph? unweighted-graph?)
  edges : (listof (list/c any/c any/c))
Creates an unweighted graph that implements gen:graph from a list of directed edges. Each edge is represented by a list of two vertices, where the first vertex in the list is the source and the second is the destination. Vertices can be any Racket values comparable with equal?.

Examples:
> (define g (unweighted-graph/directed '((a b) (c d))))
> (graph? g)

#t

> (unweighted-graph? g)

#t

> (has-edge? g 'a 'b)

#t

> (has-edge? g 'b 'a)

#f

procedure

(unweighted-graph/adj edges)  (and/c graph? unweighted-graph?)

  edges : (listof list?)
Creates an unweighted graph that implements gen:graph from an adjacency list. Each element of the list is a list of vertices where the first vertex is the source and the rest are destinations. Vertices can be any Racket values comparable with equal?.

Examples:
> (define g (unweighted-graph/adj '((a b c) (b c d))))
> (graph? g)

#t

> (unweighted-graph? g)

#t

> (has-edge? g 'a 'b)

#t

> (has-edge? g 'b 'a)

#f

2.2 Weighted Graphs

See also the directed-graph and undirected-graph constructors, which create either a weighted or unweighted graph.

procedure

(weighted-graph? g)  boolean?

  g : any/c
Indicates whether a graph is a weighted graph.

procedure

(weighted-graph/undirected edges)

  (and/c graph? weighted-graph?)
  edges : (listof (list/c number? any/c any/c))
Creates a weighted graph that implements gen:graph from a list of weighted, undirected edges. Each edge is represented by a list of one number and two vertices, where the number is the weight. Vertices can be any Racket values comparable with equal?.

Examples:
> (define g (weighted-graph/undirected '((10 a b) (20 b c))))
> (graph? g)

#t

> (weighted-graph? g)

#t

> (has-edge? g 'a 'b)

#t

> (has-edge? g 'b 'a)

#t

> (edge-weight g 'a 'b)

10

> (edge-weight g 'b 'a)

10

procedure

(weighted-graph/directed edges)

  (and/c graph? weighted-graph?)
  edges : (listof (list/c number? any/c any/c))
Creates a weighted graph that implements gen:graph from a list of weighted, directed edges. Each edge is represented by a list of one number and two vertices, where the number is the weight, and the first vertex in the list is the source and the second vertex is the destination. Vertices can be any Racket values comparable with equal?. Non-existent edges return an infinite weight, even for non-existent vertices.

Examples:
> (define g (weighted-graph/directed '((10 a b) (20 b c))))
> (graph? g)

#t

> (weighted-graph? g)

#t

> (has-edge? g 'a 'b)

#t

> (has-edge? g 'b 'a)

#f

> (edge-weight g 'a 'b)

10

> (edge-weight g 'b 'a)

+inf.0

> (edge-weight g 'b 'd)

+inf.0

procedure

(undirected-graph edges [wgts])

  (and/c graph? (or/c unweighted-graph? weighted-graph?))
  edges : (listof (list/c number? any/c any/c))
  wgts : (listof number?) = #f
Creates either a weighted or unweighted graph that implements gen:graph from a list of undirected edges and possibly a list of weights. Each edge is represented by a list of two vertices. Vertices can be any Racket values comparable with equal?. If a list of weights is provided, then the result is a weighted graph. Otherwise, the result is an unweighted graph. The number of weights must equal the number of edges.

Examples:
> (define g (undirected-graph '((a b) (b c)) '(10 20)))
> (graph? g)

#t

> (weighted-graph? g)

#t

> (has-edge? g 'a 'b)

#t

> (has-edge? g 'b 'a)

#t

> (edge-weight g 'a 'b)

10

> (edge-weight g 'b 'a)

10

> (define g2 (undirected-graph '((a b) (b c))))
> (weighted-graph? g2)

#f

> (unweighted-graph? g2)

#t

procedure

(directed-graph edges [wgts])

  (and/c graph? (or/c unweighted-graph? weighted-graph?))
  edges : (listof (list/c number? any/c any/c))
  wgts : (listof number?) = #f
Creates either a weighted or unweighted graph that implements gen:graph from a list of directed edges and possibly a list of weights. Each edge is represented by a list of two vertices where the first vertex in the list is the source and the second vertex is the destination. Vertices can be any Racket values comparable with equal?. If a list of weights is provided, then the result is a weighted graph. Otherwise, the result is an unweighted graph. The number of weights must equal the number of edges. Non-existent edges return an infinite weight, even for non-existent vertices.

Examples:
> (define g (directed-graph '((a b) (b c)) '(10 20)))
> (graph? g)

#t

> (weighted-graph? g)

#t

> (has-edge? g 'a 'b)

#t

> (has-edge? g 'b 'a)

#f

> (edge-weight g 'a 'b)

10

> (edge-weight g 'b 'a)

+inf.0

> (edge-weight g 'b 'd)

+inf.0

> (define g2 (directed-graph '((a b) (b c))))
> (weighted-graph? g2)

#f

> (unweighted-graph? g2)

#t

2.3 Matrix Graphs

procedure

(matrix-graph? g)  boolean?

  g : any/c
Indicates whether a graph is a matrix graph.

syntax

(matrix-graph [[expr ...+] ...+])

Creates a matrix graph that implements gen:graph from nested rows of expressions, exactly like matrix form. Vertices are the (0-based) row/column numbers and the weights are the number at each row-column. Use #f to indicate no edge.

NOTE: matrix-graph is implemented with matrix, so the same typed-untyped performance caveats probably apply.

Examples:
> (define g (matrix-graph [[0 3 8 #f -4]
                           [#f 0 #f 1 7]
                           [#f 4 0 #f #f]
                           [2 #f -5 0 #f]
                           [#f #f #f 6 0]]))
> (graph? g)

#t

> (matrix-graph? g)

#t

> (has-edge? g 0 1)

#t

> (has-edge? g 1 0)

#f

> (edge-weight g 0 1)

3

> (edge-weight g 1 0)

+inf.0

> (floyd-warshall g)

'#hash(((1 3) . 1.0)

       ((2 1) . 4.0)

       ((0 2) . -3.0)

       ((3 3) . 0.0)

       ((1 1) . 0.0)

       ((0 4) . -4.0)

       ((1 0) . 3.0)

       ((1 4) . -1.0)

       ((0 1) . 1.0)

       ((3 2) . -5.0)

       ((4 1) . 5.0)

       ((4 4) . 0)

       ((4 3) . 6.0)

       ((2 3) . 5.0)

       ((0 0) . 0.0)

       ((4 2) . 1.0)

       ((3 1) . -1.0)

       ((4 0) . 8.0)

       ((2 4) . 3.0)

       ((2 0) . 7.0)

       ((3 0) . 2.0)

       ((2 2) . 0.0)

       ((0 3) . 2.0)

       ((1 2) . -4.0)

       ((3 4) . -2.0))

3 Graph properties

The following forms associate properties with a graph. The graph itself is unchanged. These are inspired by and resemble the Boost Graph Library’s externally-stored properties

syntax

(define-vertex-property graph prop-name maybe-init maybe-vs)

 
graph = graph?
     
prop-name = identifier?
     
maybe-init = 
  | #:init init-expr
     
init-expr = expr
     
maybe-vs = 
  | #:vs vs
     
vs = list?
Creates a vertex property for vertices of the graph where each vertex maps to a value. This is a loose association, as keys of the mapping don’t necessarily have to be vertices in the graph.

Essentially, a vertex property is just a hash table with vertex keys that has some convenient accessors. The accessors do not enforce that vertices must be in the graph to support algorithms that make use of imaginary vertices.

Defines the following names:

If an #:init argument is supplied, each vertex in the graph is associated with the result of computing init-expr. In the init-expr, the identifier $v may be used to refer to the vertex whose value is being set. The init-expr is evaluated only once. If vertices are added to the graph after the mapping is created, those vertices will not have a value in the mapping until the setter is called.

A #:vs argument maybe supplied to specify the order in which the vertices are initialized. The vs list is only used if there is also an #:init expression.

Examples:
> (define g (unweighted-graph/directed '((a b) (b c) (c d))))
> (define-vertex-property g dist #:init 0)
> (dist 'a)

0

> (dist 'non-exist)

dist: no dist value for non-exist

> (dist 'non-exist #:default #f)

#f

> (dist-set! 'a 100)
> (dist 'a)

100

> (dist->hash)

'#hash((a . 100) (b . 0) (c . 0) (d . 0))

> (define-vertex-property g itself #:init $v)
> (itself 'a)

'a

syntax

(define-edge-property graph prop-name maybe-init maybe-for-each)

 
graph = graph?
     
prop-name = identifier?
     
maybe-init = 
  | #:init init-expr
     
init-expr = expr
     
maybe-vs = 
  | #:for-each for-each-e ...
     
for-each-e = expr
Creates an edge property for all possible edges in the graph (ie, every pair of vertices) where each edge maps to a value.

Essentially, an edge property is just a hash table with edges as keys that has some convenient accessors. The accessors do not enforce that edges must be in the graph to support algorithms that make use of imaginary edges.

Defines the following names:

If an #:init argument is supplied, each pair of vertices in the graph is associated with the result of computing init-expr. In the init-expr, the identifiers $from and $to may be used to refer to the vertices whose value is being set.

The #:for-each keyword may be used instead of #:init when more control of the initialization is required. The for-each-e expressions are evaluated once per pair of vertices. The $from and $to identifiers are again available to refer to the vertices in the "current" edge.

Examples:
> (define g (unweighted-graph/directed '((a b) (b c) (c d) (d a))))
> (define-edge-property g A #:init 0)
> (A 'a 'b)

0

Non-edges also get a value.

Examples:
> (get-edges g)

'((d a) (c d) (b c) (a b))

> (A 'a 'd)

0

But non-existent vertices still fails.

Examples:
> (A 'a 'e)

A: no A value for edge a-e

> (A 'a 'e #:default #f)

#f

Examples:
> (A-set! 'a 'b 100)
> (A 'a 'b)

100

> (define-edge-property g C #:init 100)
> (C->hash)

'#hash(((d d) . 100)

       ((d c) . 100)

       ((a b) . 100)

       ((c b) . 100)

       ((a d) . 100)

       ((a a) . 100)

       ((d b) . 100)

       ((d a) . 100)

       ((b b) . 100)

       ((a c) . 100)

       ((c d) . 100)

       ((c a) . 100)

       ((c c) . 100)

       ((b a) . 100)

       ((b c) . 100)

       ((b d) . 100))

> (define-edge-property g B #:for-each (B-set! $from $to (format "~a-~a" $from $to)))
> (B 'c 'd)

"c-d"

> (B->hash)

'#hash(((d d) . "d-d")

       ((d c) . "d-c")

       ((a b) . "a-b")

       ((c b) . "c-b")

       ((a d) . "a-d")

       ((a a) . "a-a")

       ((d b) . "d-b")

       ((d a) . "d-a")

       ((b b) . "b-b")

       ((a c) . "a-c")

       ((c d) . "c-d")

       ((c a) . "c-a")

       ((c c) . "c-c")

       ((b a) . "b-a")

       ((b c) . "b-c")

       ((b d) . "b-d"))

4 Basic Graph Functions

4.1 Breadth-first Search

procedure

(bfs g source)  
(hash/c any/c number? #:immutable #f)
(hash/c any/c any/c #:immutable #f)
  g : graph?
  source : any/c
Standard textbook breadth-first search, ie as [CLRS]. Takes two arguments, a graph and a source vertex. Returns two values, a hash table mapping a vertex to the distance (in terms of number of vertices) from the source, and a hash table mapping a vertex to its predecessor in the search.

procedure

(bfs/generalized g    
  source    
  [#:init-queue Q    
  #:break break?    
  #:init init    
  #:visit? custom-visit?-fn    
  #:discover discover    
  #:visit visit    
  #:return finish])  any
  g : graph?
  source : any/c
  Q : queue? = (mk-empty-fifo)
  break? : (-> graph? [source any/c] [from any/c] [to any/c] boolean?)
   = (λ _ #f)
  init : (-> graph? [source any/c] void?) = void
  custom-visit?-fn : (-> graph? [source any/c] [from any/c] [to any/c] boolean?)
   = #f
  discover : (-> graph? [source any/c] [from any/c] [to any/c] [acc any/c] any/c)
   = (λ (G s u v acc) acc)
  visit : (-> graph? [source any/c] [v any/c] [acc any/c] any/c)
   = (λ (G s v acc) acc)
  finish : (-> graph? [source any/c] [acc any/c] any)
   = (λ (G s acc) acc)
Generalized breadth-first search. Partially inspired by the C++ Boost Graph Library. See Lee et al. OOPSLA 1999 [GGCL]. Here is the rough implementation:
(enqueue! Q s)
(mark-discovered! s)
(define new-acc
  (for/fold ([acc (init G s)]) ([u (in-queue Q)])
    (for ([inner-acc (visit G s u acc)])
      ([v (in-neighbors G u)] #:when (visit? G s u v) #:break (break? G s u v))
      (mark-discovered! v)
      (begin0 (discover G s u v inner-acc)
              (enqueue! Q v)))))
(finish G s new-acc)
Utilizes a queue that implements gen:queue. A vertex is discovered when it gets added to the queue. If no custom-visit?-fn is provided, then the default behavior is to not enqueue/visit vertices that have already been discovered (ie seen). The function checks the #:break condition when a vertex is discovered (ie being considered for enqueueing). When a vertex is dequeued, then visit is called. The result of bfs/generalized is the result of finish.

An accumulator is threaded through all the functions and returned at the end. The initial accumulator value is the result of applying init. By default the accumulator is threaded through discover, visit, and is returned via finish.

Accumulator history:

Added in version 0.2 of package graph.

syntax

(do-bfs graph source maybe-init-queue maybe-break
        maybe-init maybe-visit? maybe-discover maybe-visit maybe-return)
 
graph = graph?
     
maybe-init-queue = 
  | #:init-queue queue
  | #:init-queue: queue
     
queue = queue?
     
maybe-break = 
  | #:break (from to) break-exp ...
  | #:break: break-exp ...
     
break-exp = expr
     
maybe-init = 
  | #:init init-exp ...
  | #:init: init-exp ...
     
init-exp = expr
     
maybe-visit? = 
  | #:visit? (from to) visit?-exp ...
  | #:visit?: visit?-exp ...
  | #:enqueue? (from to) enq?-exp ...
  | #:enqueue?: enq?-exp ...
     
visit?-exp = expr
     
enq?-exp = expr
     
maybe-discover = 
  | #:discover (from to) discover-exp ...
  | #:discover (from to acc) discover-exp ...
  | #:discover: discover-exp ...
  | #:on-enqueue (from to) enq-exp ...
  | #:on-enqueue (from to acc) enq-exp ...
  | #:on-enqueue: enq-exp ...
     
discover-exp = expr
     
enq-exp = expr
     
maybe-visit = 
  | #:visit (v) visit-exp ...
  | #:visit (v acc) visit-exp ...
  | #:visit: visit-exp ...
  | #:on-dequeue (v) deq-exp ...
  | #:on-dequeue (v acc) deq-exp ...
  | #:on-dequeue: deq-exp ...
     
visit-exp = expr
     
deq-exp = expr
     
maybe-return = 
  | #:return (acc) return-exp ...
  | #:return: return-exp ...
     
return-exp = expr
     
from = identifier?
     
to = identifier?
     
v = identifier?
     
acc = identifier?
Cleaner syntax for bfs/generalized. Essentially, this form eliminates the need to define separate functions and then pass them as bfs/generalized’s keyword arguments. Instead, the bodies of those functions are inserted right after the corresponding keywords.

Each possible keyword has a colon-suffixed and non-colon-suffixed version. The non-colon-suffixed versions bind user-supplied identifiers. For example, the keywords #:break, #:visit?, #:discover, and #:visit bind identifiers that represent the vertices under consideration. For some keywords, the accumulator may also be named. If the accumulator is unnamed, then it is implicitly passed through unchanged. If the accumulator is named, then the result of evaluating the body becomes the new accumulator value.

In the body of colon-suffixed keywords, implicit special identifiers refer to the vertices under consideration. Specifically, $v is bound to the current vertex and $from is its parent (when appropriate). A $to identifier has the same value as $v, in case that name makes more sense in the context of the program. The special $acc identifier represents the accumulator value.

Colon-suffixed keyword history:

Added in version 0.3 of package graph.

The keywords that don’t bind any names (#:init-queue and #:init) have both colon and non-colon versions, to have a consistent naming scheme.

The keywords #:visit?, #:discover, and #:visit also have alternate names, #:enqueue?, #:on-enqueue, and #:on-dequeue, respectively, which can be used when these names are more appropriate, for program readability.

In any of the keyword arguments, the special identifiers $discovered?, $seen?, and $visited? are also available, where ($seen? v) indicates whether the vertex has been seen, ie whether the vertex has ever been added to the queue (($discovered? v) is the same as $seen?), and ($visited? v) indicates whether the vertex has been visited, ie pulled off the queue.

In the #:return expressions, the $broke? special identifier indicates whether the search was terminated early according to the #:break condition.

For example, below is Dijkstra’s algorithm, implemented with do-bfs. The code defines two vertex propertys: d maps a vertex to the currently known shortest distance from the source and π maps a vertex to its predecessor in the shortest path from the source. The algorithm utilizes a priority queue (ie, heap) that is sorted according to intermediate shortest paths. A node is added to the heap when it improves one of the paths. The algorithm makes use of the special identifiers $v and $from.

(define (dijkstra G src)
  (define-vertex-property G d #:init +inf.0) ; length of currently known shortest path
  (define-vertex-property G π #:init #f) ; (π v) is predecessor of v on shortest path
  (define (wgt u v) (edge-weight G u v))
 
  (do-bfs G src #:init-queue (mk-empty-priority (λ (u v) (< (d u) (d v))))
    #:init (d-set! src 0)
    #:enqueue?: (> (d $v) (+ (d $from) (wgt $from $v)))
    #:on-enqueue:
      (d-set! $v (+ (d $from) (wgt $from $v)))
      (π-set! $v $from)
    #:return: (values (d->hash) (π->hash))))

bfs, fewest-vertices-path, cc/bfs, mst-prim, and dijkstra all use the do-bfs form.}

procedure

(fewest-vertices-path G source target)  (or/c list? #f)

  G : graph?
  source : any/c
  target : any/c
Consumes a graph and two vertices, and returns the shortest path (in terms of number of vertices) between the two vertices. The result is a list of vertices, or #f if there is no path.

4.2 Depth-first Search

procedure

(dfs g)  
(hash/c any/c number? #:immutable #f)
(hash/c any/c any/c #:immutable #f)
(hash/c any/c number? #:immutable #f)
  g : graph?
Standard textbook depth-first search algorith, ie like in [CLRS]. Consumes a graph and returns three hashes: one that maps a vertex to its "discovery time", another that maps a vertex to its predecessor in the search, and a third that maps a vertex to its "finishing time".

procedure

(dfs/generalized g    
  [#:order order    
  #:break break?    
  #:init init    
  #:inner-init inner-init    
  #:visit? custom-visit?-fn    
  #:prologue prologue    
  #:epilogue epilogue    
  #:process-unvisited? process-unvisited?    
  #:process-unvisited process-unvisited    
  #:combine combine    
  #:return finish])  any
  g : graph?
  order : (-> list? list?) = (λ (x) x)
  break? : (-> graph? [from any/c] [to any/c] boolean?)
   = (λ _ #f)
  init : (-> graph? void?) = void
  inner-init : (-> any/c any/c) = (λ (acc) acc)
  custom-visit?-fn : (-> graph? [from any/c] [to any/c] boolean?)
   = #f
  prologue : (-> graph? [from any/c] [v any/c] [acc any/c] any/c)
   = (λ (G u v acc) acc)
  epilogue : (-> graph? [from any/c] [v any/c] [acc any/c] any/c)
   = (λ (G u v acc) acc)
  process-unvisited? : (-> graph? [from any/c] [to any/c] boolean?)
   = (λ _ #f)
  process-unvisited : (-> graph? [from any/c] [to any/c] [acc any/c] any/c)
   = (λ (G u v acc) acc)
  combine : (-> [x any/c] [acc any/c] any/c) = (λ (x acc) x)
  finish : (-> graph? [acc any/c] any/c) = (λ (G acc) acc)
Note: You probably want to use the nicer do-dfs form instead of this function.

Generalized depth-first search. Partially inspired by the C++ Boost Graph Library. See Lee et al. OOPSLA 1999 [GGCL]. Here is the rough implementation:

; inner loop: keep following (unvisited) links
(define (do-visit parent u acc)
  (mark-visited! u)
  (define new-acc
    (for/fold ([acc (prologue G parent u acc)])
              ([v (in-neighbors G u)] #:break (break? G u v))
      (cond [(visit? G u v) (do-visit u v acc)]
            [(process-unvisited? G u v) (process-unvisited G u v acc)]
            [else acc])))
  (epilogue G parent u new-acc))
 
; outer loop: picks a new vertex to continue with when search reaches dead end
(define new-acc
  (for/fold ([acc (init G)])
            ([u (order (get-vertices G))] #:break (break? G #f u))
    (cond [(visit? G #f u) (combine (do-visit #f u (inner-init acc)) acc)]
          [(process-unvisited? G #f u) (process-unvisited G #f u acc)]
          [else acc])))
 
(finish G new-acc)

The do-visit function is the inner loop that keeps following edges, depth-first, until the search gets stuck. The "visit" part of the code is separated into two functions, the prologue, which represents the descending part of the visit, and epilogue, which gets called on the way back up. The outer for/fold loop picks a new vertex to restart the search when it gets stuck. Vertices that are already visited are marked and are not visited again by default, but the custom-visit?-fn can override this. The algorithm terminates when all vertices are visited, or the #:break condition is triggered. The result of dfs/generalized is the result of finish.

An accumulator is threaded through all the functions and returned at the end. The initial accumulator value is the result of applying init. There is another inner-init value that starts a new sub-accumulator each time the outer for/fold loop iterates. The optional combine function combines the result of each outer loop iteration with the overall accumulator. See the implementation of cc for an example of where this is useful. If a different inner-init is unneeded, it defaults to the same value as the overall accumulator.

Accumulator history:

Added in version 0.2 of package graph.

If an order function is supplied, the outer loop uses it to sort the vertices before determining which vertex to visit next. The break? predicate aborts the search and returns when it is true. process-unvisited? and process-unvisited specify code to run when a vertex is not visited.

The functions that require both a "from" and a "to" vertex argument are given #f for the "from" (ie the parent) when there is none.

syntax

(do-dfs graph maybe-order maybe-break maybe-init maybe-inner-init
        maybe-visit? maybe-prologue maybe-epilogue
        maybe-process-unvisited? maybe-process-unvisited maybe-combine maybe-return)
 
graph = graph?
     
maybe-order = 
  | #:order order
  | #:order: order
     
order = (-> list? list?)
     
maybe-break = 
  | #:break (from to) break-exp ...
  | #:break (from to acc) break-exp ...
  | #:break: break-exp ...
     
break-exp = expr
     
maybe-init = 
  | #:init init-exp ...
  | #:init: init-exp ...
     
init-exp = expr
     
maybe-inner-init = 
  | #:inner-init iinit-exp ...
  | #:inner-init: iinit-exp ...
     
iinit-exp = expr
     
maybe-visit? = 
  | #:visit? (from to) visit?-exp ...
  | #:visit?: visit?-exp ...
     
visit?-exp = expr
     
maybe-prologue = 
  | #:prologue (from to) prologue-exp ...
  | #:prologue (from to acc) prologue-exp ...
  | #:prologue: prologue-exp ...
     
prologue-exp = expr
     
maybe-epilogue = 
  | #:epilogue (from to) epilogue-exp ...
  | #:epilogue (from to acc) epilogue-exp ...
  | #:epilogue: epilogue-exp ...
     
epilogue-exp = expr
     
maybe-process-unvisited? = 
  | #:process-unvisited? (from to) process-unvisited?-exp ...
  | #:process-unvisited?: process-unvisited?-exp ...
     
process-unvisited?-exp = expr
     
maybe-process-unvisited = 
  | #:process-unvisited (from to) process-unvisited-exp ...
  | #:process-unvisited (from to acc) process-unvisited-exp ...
  | #:process-unvisited: process-unvisited-exp ...
     
process-unvisited-exp = expr
     
maybe-combine = 
  | #:combine combine-fn
  | #:combine: combine-fn
     
maybe-return = 
  | #:return () return-exp ...
  | #:return (acc) return-exp ...
  | #:return: return-exp ...
     
return-exp = expr
     
from = identifier?
     
to = identifier?
     
v = identifier?
     
acc = identifier?
Analogous to do-bfs. Nicer syntax for dfs/generalized. Essentially, this form eliminates the need to define separate functions and then pass them as dfs/generalized’s keyword arguments. Instead, the bodies of those functions are inserted right after the corresponding keywords.

Each possible keyword has a colon-suffixed and non-colon-suffixed version. The non-colon-suffixed versions bind user-supplied identifiers. For example, the keywords #:break, #:visit?, #:prologue, #:epilogue, #:process-unvisited?, and #:process-unvisited bind identifiers that represent the vertices under consideration. For some keywords, the accumulator may also be named. If the accumulator is unnamed, then it is implicitly passed through unchanged. If the accumulator is named, then the result of evaluating the body becomes the new accumulator value.

In the body of colon-suffixed keywords, implicit special identifiers refer to the vertices under consideration. Specifically, $v is bound to the current vertex and $from is its parent (when appropriate). A $to identifier has the same value as $v, in case that name makes more sense in the context of the program. The special $acc identifier represents the accumulator value.

Colon-suffixed keyword history:

Added in version 0.3 of package graph.

The keywords that don’t bind any names (#:order, #:init, #:iinit, and #:combine) have both colon and non-colon versions, to have a consistent naming scheme.

In the #:return expressions, the $broke? special identifier indicates whether the search was terminated early according to the #:break condition.

As an example, here is a possible definition for dag?, a predicate that indicates whether a graph is directed and acyclic. The function uses the classic three vertex coloring, where white indicates unseen, gray indicates discovered, and black indicates done. Encountering a gray node while searching indicates a cycle so this is checked as the #:break condition. The implementation of dag? uses the special $v and $broke? identifiers.

(define (dag? G)
  (define-vertex-property G color #:init WHITE)
  (do-dfs G
   #:break: (gray? (color $v)) ; seeing a gray vertex means a loop
   #:visit?: (white? (color $v))
   #:prologue: (color-set! $v GRAY)
   #:epilogue: (color-set! $v BLACK)
   #:return: (not $broke?))) ; didnt break means no loop = acyclic

Here is a possible implementation of tsort, ie topological sort. It maintains the sorted vertices as an accmulator and ads vertices to the result on the way back up the depth-first search.

(define (tsort G)
  (do-dfs G #:init null
            #:epilogue: (cons $v $acc)))

dfs, tsort, dag?, cc, and scc all use the do-dfs form.}

procedure

(dag? g)  boolean?

  g : graph?
Indicates whether a graph is directed and acyclic.

procedure

(tsort g)  list?

  g : graph?
Returns the vertices in the given graph, topologically sorted. Note that the returned order may not be the only valid ordering.

procedure

(cc g)  (listof list?)

  g : graph?
Calculates the connected components of graph g. g should be an undirected graph. Returns a list of lists of vertices, where each sublist is a connected component.

Added in version 0.2 of package graph.

procedure

(cc/bfs g)  (listof list?)

  g : graph?
Calculates the connected components of graph g using do-bfs. g should be an undirected graph. Returns a list of lists of vertices, where each sublist is a connected component.

Added in version 0.2 of package graph.

procedure

(scc g)  (listof list?)

  g : graph?
Calculates the strongly connected components of a graph using Tarjan’s algorithm [tarjan-scc]. g should be a directed graph. Returns a list of lists of vertices, where each sublist is a strongly connected subgraph.

5 Minimum Spanning Tree

procedure

(mst-kruskal g)  (listof (list/c any/c any/c))

  g : graph?
Computes the minimum spanning tree using Kruskal’s algorithm and the data/union-find data structure. Returns a list of edges.

procedure

(mst-prim g source)  (listof (list/c any/c any/c))

  g : graph?
  source : any/c
Computes the minimum spanning tree of a graph using Prim’s algorithm, which is based on breadth-first search. Returns a list of edges.

6 Single-source Shortest Paths

procedure

(bellman-ford g source)  
(hash/c any/c number? #:immutable #f)
(hash/c any/c any/c #:immutable #f)
  g : graph?
  source : any/c
Computes the shortest paths from the given source to every other vertex using the Bellman-Ford algorithm. The function errors when the graph has a negative weight cycle, but otherwise, negative weights are allowed.

Returns two hashes, one that maps a vertex to its distance (in total edge weights) from the source and one that maps a vertex to its predecessor in the shortest path from the source.

procedure

(dijkstra g source)  
(hash/c any/c number? #:immutable #f)
(hash/c any/c any/c #:immutable #f)
  g : graph?
  source : any/c
Similarly computes shortest paths from the source to every other vertex. Faster than Bellman-Ford but no negative weight edges are allowed. Based on breadth-first search.

procedure

(dag-shortest-paths g source)

  
(hash/c any/c number? #:immutable #f)
(hash/c any/c any/c #:immutable #f)
  g : graph?
  source : any/c
The fastest shortest paths algorithm but only works on dags.

7 All-pairs Shortest Paths

procedure

(floyd-warshall g)

  (hash/c (list/c any/c any/c) number? #:immutable #f)
  g : graph?
Computes the length of the shortest path for all pairs of vertices using the Floyd-Warshall algorithm. Returns a hash mapping a pair of vertices to the length of the shortest path between them.

procedure

(transitive-closure g)

  (hash/c (list/c any/c any/c) boolean? #:immutable #f)
  g : graph?
Returns a hash mapping a pair of vertices to a boolean. If true, then there exists a path from the first vertex to the second.

procedure

(johnson g)

  (hash/c (list/c any/c any/c) number? #:immutable #f)
  g : graph?
Computes all-pairs shortest paths using Johnson’s algorithm. Should be faster than Floyd Warshall for sparse graphs. Theoretical running time is O(VElogV).

Handles negative weights by first running bellman-ford. The uses dijkstra for each vertex in the graph.

Note, the running time could be theoretically faster with a version of Dijkstra that uses a Fibonacci heap instead of a standard heap.

Graph coloring functions are only valid for undirected graphs.

8 Graph Coloring

procedure

(coloring g num-colors [#:order order])

  (or/c (hash/c any/c number? #:immutable #f) #f)
  g : graph?
  num-colors : natural-number/c
  order : (-> list? list?) = (λ (x) x)
Returns a coloring for the given graph using at most the specified number of colors, or #f if no coloring is possible. Uses backtracking algorithm so takes exponential time. Optional #:order parameter determines the order in which verticies are colored.

The returned "colors" are integers in [0,num-colors).

procedure

(coloring/greedy g [#:order order])

  
number?
(hash/c any/c number? #:immutable #f)
  g : graph?
  order : (or/c 'smallest-last (-> list? list?))
   = 'smallest-last
Returns a "greedy" coloring of the given graph, where the color for a vertex is the "smallest" color not used by one of its neighbors (or the number of colors is increased).

The function always returns a valid coloring but the optimality (ie number of colors used) depends on the ordering in which the vertices are considered. The default is to use "smallest-last" ordering (see order-smallest-last) but if #:order is a procedure, then it is applied to sort the list of vertices before the coloring begins.

Only works on undirected graphs.

The returned "colors" are non-negative integers starting from 0. The function also returns the total number of colors used.

procedure

(coloring/brelaz g)  (hash/c any/c number? #:immutable #f)

  g : graph?
Returns a "greedy" coloring of the given graph, using the Brelaz vertex ordering heuristic. Note that this function is separate from coloring/greedy because the ordering is determined in an online manner.

procedure

(order-smallest-last g)  list?

  g : graph?
Consumes a graph and returns the vertices of the graph in "smallest-last" order. The ordering proceeds as follows. The vertex with the smallest degree is last. Then that vertex is removed and the degrees of the remaining vertices are updated. Then the second to last vertex has the lowest remaining degree and so on.

Only works for undirected graphs.

procedure

(valid-coloring? g coloring)  boolean?

  g : graph?
  coloring : (hash/c any/c number?)
Indicates whether the given coloring (a hash that maps a vertex to a color) is valid, meaning that no edge has two vertices of the same color.

This function assumes that a "color" is a number and uses = to compare colors.

9 Maximum Flow

procedure

(maxflow g source sink)  (hash/c (list/c any/c any/c) number?)

  g : graph?
  source : any/c
  sink : any/c
Computes the maximum flow in graph g from source to sink using the Edmonds-Karp algorithm, which runs in time O(VE^2). Edmonds-Karp is an improvement on the Ford-Fulkerson algorithm in that it uses fewest-vertices-path to find an augmenting path in each iteration.

The function returns a hash mapping an edge to a non-negative number representing the flow along that edge. The returned returned flow is maximal and obeys a few properties:
  • The flow out of the source equals the source into the sink.

  • The flow out of each non-source/sink vertex equals the flow into that vertex.

  • The flow along each edge is <= the edge’s capacity (ie, weight).

This function should only be used on directed graphs, otherwise things get double counted.

procedure

(bipartite? g)  (or/c #f (list/c list? list?))

  g : graph?
Determines whether a graph is bipartite using a dfs-based 2-coloring, thus runs in linear time. Returns #f if the graph is not bipartite (ie, not 2-colorable), and other wise returns a list of two lists, where each sublist is the "left" and "right" sets of vertices, respectively, in the bipartite graph.

procedure

(maximum-bipartite-matching g)  (listof (list/c any/c any/c))

  g : graph?
Returns a list of edges representing the maximum matching of the given bipartite graph. An error is raised if the given graph is not bipartite. Uses maxflow to compute the maximum matching.

Note: this is not the Hopcroft-Karp (ie fastest) bipartite matching algorithm.

10 Graphviz

procedure

(graphviz g [#:output output #:colors colors])  string?

  g : graph?
  output : (or/c output-port? #f) = #f
  colors : (or/c (hash/c any/c natural-number/c) #f) = #f
Returns the dotfile representation of the given graph (as a string).

The optional color argument maps vertices to colors, where the color corresponds to the "H" component of an HSV color representation. The given colors are normalized to be between 0 and 1.0 before generating the graphviz output, with the maximum specified color value corresponding to 1.0 (the S and V components are currently unspecifiable and are always 1.0).

Typically, the color argument is the output of a function from Graph Coloring, e.g., (graphviz g #:colors (coloring/brelaz g)).

The optional output argument redirects the output from a string to the given output port. A string is returned when the argument is #f.

11 Other

value

$v : identifier?

An identifier that’s bound to the "current" vertex in certain contexts.

See define-vertex-property, do-bfs, and do-dfs.

An identifier that’s bound to the "from" vertex in certain contexts.

value

$to : identifier?

An identifier that’s bound to the "to" vertex certain contexts.

A function that queries the "seen" vertices in certain contexts.

See do-bfs.
A function that queries the "seen" vertices in certain contexts. Same as $discovered?.

See do-bfs.
A function that queries the "visited" vertices in certain contexts.

See do-bfs.
Indicates whether the #:break condition was triggered in some contexts.

See do-bfs and do-dfs.

value

$acc : identifier?

Represents an accumulator value in some contexts.

See do-dfs.

Added in version 0.2 of package graph.

Bibliography

[GGCL] Lie-Quan Lee, Jeremy G. Siek, and Andrew Lumsdaine, “The Generic Graph Component Library,” OOPSLA, 1999.
[tarjan-scc] Robert E. Tarjan, “Depth first search and linear graph algorithms.,” SIAM Journal on Computing, 1(2):146-160, 1972.
[CLRS] Charles E. Leiserson, Clifford Stein, Thomas H. Cormen, and Ronald Rivest, Introduction to Algorithms, 2nd ed.. 2001.