7.9

## Racket Generic Graph Library

 (require graph) package: graph-lib

Generic graph library for Racket.

Requires Racket 6.0 or later.

### 1Generic Graph Interface

 value
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:

•  procedure(has-vertex? g v) → boolean? g : graph? v : any/c
Indicates whether a vertex is in the given graph.

•  procedure(has-edge? g u v) → boolean? g : graph? u : any/c v : any/c
Indicates whether an edge is in the given graph.

•  procedure(vertex=? g u v) → boolean? g : graph? u : any/c v : any/c
Indicates whether vertices u and v are the same vertex, according to graph g.

•  procedure(add-vertex! g v) → void? g : graph? v : any/c
Imperatively adds a vertex to a graph.

•  procedure(remove-vertex! g v) → void? g : graph? v : any/c
Imperatively removes a vertex from a graph. Any edges containing the vertex are also removed.

•  procedure(rename-vertex! g old new) → void? g : graph? old : any/c new : any/c
Imperatively renames vertex old to new in a graph. An exception is thrown if new already exists in the graph.

•  procedure(add-edge! g u v [weight]) → void? g : graph? u : any/c v : any/c weight : any/c = 'default-value
Imperatively adds an undirected edge and optional weight to a graph. Each graph that implements the interface determines its own default weight value.

•  procedure(add-directed-edge! g u v [weight]) → void? g : graph? u : any/c v : any/c weight : any/c = 'default-value
Imperatively adds a directed, optionally weighted edge to a graph. Each graph that implements the interface determines its own default weight value.

•  procedure(remove-edge! g u v) → void? g : graph? u : any/c v : any/c
Imperatively removes the undirected edge.

•  procedure g : graph? u : any/c v : any/c
Imperatively removes the directed edge.

•  procedure g : graph?
Returns a list of vertices in the graph.

•  procedure g : graph?
Returns a sequence of vertices in the graph.

•  procedure(get-neighbors g v) → list? g : graph? v : any/c
Returns a list of vertex v’s neighbors in the graph.

•  procedure g : graph? v : any/c
Returns a sequence of vertex v’s neighbors in the graph.

•  procedure(get-edges g) → list? g : graph?
Returns a list of edges in the graph.

•  procedure g : graph?
Returns a sequence of edges in the graph.

•  procedure(edge-weight g u v [#:default default]) → any/c? g : graph? u : any/c v : any/c default : any/c = +inf.0
Returns the weight of the edge in the graph, if it has one. For non-existent edges, returns the specified default.

Changed in version 0.5.1 of package graph-lib: added default argument

•  procedure(transpose g) → graph? g : graph?
Returns a new graph where the edges of the original graph are reversed.

•  procedure(graph-copy g) → graph? g : graph?
Returns a copy of the given graph.

•  procedure(graph-union! g other) → void? g : graph? other : graph?
Copies the data from other into g.

### 2Graph Constructors

#### 2.1Unweighted Graphs

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

 procedure 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 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.2Weighted Graphs

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

 procedure 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 any/c 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 weight (label) and two vertices. Vertices can be any Racket values comparable with equal?. Weights can be any Racket values comparable with equal?. Note that some algorithms will fail on non-numerical egde weights.

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 any/c 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 weight (label) and two vertices, 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. In general, weights can be any Racket values comparable with equal?. Note that some algorithms will fail on non-numerical egde weights.

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 any/c any/c)) wgts : (listof any/c) = #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. Weights can be any Racket values comparable with equal?. Note that some algorithms will fail on non-numerical egde weights.

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 any/c any/c)) wgts : (listof any/c) = #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. Weights can be any Racket values comparable with equal?. Note that some algorithms will fail on non-numerical egde weights.

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.3Matrix Graphs

 procedure 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(((3 4) . -2.0) ((4 4) . 0) ((2 0) . 7.0) ((3 3) . 0.0) ((1 1) . 0.0) ((0 1) . 1.0) ((4 3) . 6.0) ((0 4) . -4.0) ((3 0) . 2.0) ((0 0) . 0.0) ((2 2) . 0.0) ((1 0) . 3.0) ((1 4) . -1.0) ((0 3) . 2.0) ((2 3) . 5.0) ((3 1) . -1.0) ((1 3) . 1.0) ((2 1) . 4.0) ((4 1) . 5.0) ((0 2) . -3.0) ((4 2) . 1.0) ((2 4) . 3.0) ((3 2) . -5.0) ((1 2) . -4.0) ((4 0) . 8.0))

### 3Graph 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:

• prop-name: A procedure that returns the value associated with the given vertices.
• (prop-name v): Returns the value associated with the vertex v.

• (prop-name v #:default val): Returns the value associated with the given vertex. Returns val if v has no value associated with it.

• prop-name->hash: A no-argument function that returns a hash table representation of the vertex-value mappings.

• prop-name-set!: When given a vertex and a value, associates the value with the given vertex.

• prop-name-defined?: Indicates whether the given vertex has an associated value.

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:

• prop-name: A procedure that returns the value associated with the given vertices.
• (prop-name u v): Returns the value associated with the pair of vertices.

• (prop-name u v #:default val): Returns the value associated with the given pair of vertices. Returns val if edge u-v has no value associated with it.

• prop-name->hash: A no-argument function that returns a hash table representation of the edge-value mappings.

• prop-name-set!: When given an edge (ie two vertices) and a value, associates the value with the given edge.

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) '((c d) (b c) (a b) (d a)) > (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(((a d) . 100) ((d a) . 100) ((b d) . 100) ((b a) . 100) ((a a) . 100) ((a c) . 100) ((c d) . 100) ((a b) . 100) ((c c) . 100) ((b c) . 100) ((b b) . 100) ((d c) . 100) ((c a) . 100) ((c b) . 100) ((d b) . 100) ((d 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(((a d) . "a-d") ((d a) . "d-a") ((b d) . "b-d") ((b a) . "b-a") ((a a) . "a-a") ((a c) . "a-c") ((c d) . "c-d") ((a b) . "a-b") ((c c) . "c-c") ((b c) . "b-c") ((b b) . "b-b") ((d c) . "d-c") ((c a) . "c-a") ((c b) . "c-b") ((d b) . "d-b") ((d d) . "d-d"))

### 4Basic Graph Functions

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-lib.

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-lib.

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, min-st-prim, max-st-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.2Depth-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 algorithm, 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-lib.

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-lib.

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-lib.

 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-lib.

 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.

### 5Spanning Trees

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

Added in version 0.5.2 of package graph-lib.

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

Added in version 0.5.2 of package graph-lib.

 procedure(min-st-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.

Added in version 0.5.2 of package graph-lib.

 procedure(max-st-prim g source) → (listof (list/c any/c any/c)) g : graph? source : any/c
Computes the maximum spanning tree of a graph using Prim’s algorithm, which is based on breadth-first search. Returns a list of edges.

Added in version 0.5.2 of package graph-lib.

 procedure(mst-kruskal g) → (listof (list/c any/c any/c)) g : graph?
Deprecated. Alias for min-st-kruskal.

 procedure(mst-prim g source) → (listof (list/c any/c any/c)) g : graph? source : any/c
Deprecated. Alias for min-st-prim.

### 6Single-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.

### 7All-pairs Shortest Paths

 procedure → (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 → (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.

### 8Graph 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 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.

### 9Maximum 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 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.

### 10Graphviz

 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.

### 11Other

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

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

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

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

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

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

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

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

See do-bfs and do-dfs.
 value
Represents an accumulator value in some contexts.

See do-dfs.

Added in version 0.2 of package graph-lib.

### 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.