Racket Generic Graph Library
| (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
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.- Indicates whether an edge is in the given graph.
- 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.- 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
(remove-directed-edge! g u v) → void?
g : graph? u : any/c v : any/c Imperatively removes the directed edge.procedure
(get-vertices g) → list?
g : graph? Returns a list of vertices in the graph.procedure
(in-vertices g) → sequence?
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
(in-neighbors g v) → sequence?
g : graph? v : any/c Returns a sequence of vertex v’s neighbors in the graph.- Returns a list of edges in the graph.
- Returns a sequence of edges in the graph.
procedure
(edge-weight g u v) → number?
g : graph? u : any/c v : any/c Returns the weight of the edge in the graph (if it has one). Returns +inf.0 for non-existent edges.- 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.
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
procedure
(unweighted-graph/undirected edges)
→ (and/c graph? unweighted-graph?) edges : (listof (list/c any/c any/c))
> (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))
> (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?)
> (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
procedure
(weighted-graph/undirected edges)
→ (and/c graph? weighted-graph?) edges : (listof (list/c number? any/c any/c))
> (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))
> (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
> (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
> (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
syntax
(matrix-graph [[expr ...+] ...+])
NOTE: matrix-graph is implemented with matrix, so the same typed-untyped performance caveats probably apply.
> (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)
((4 4) . 0)
((3 1) . -1.0)
((0 2) . -3.0)
((2 3) . 5.0)
((4 3) . 6.0)
((0 4) . -4.0)
((1 2) . -4.0)
((3 0) . 2.0)
((3 2) . -5.0)
((2 2) . 0.0)
((2 0) . 7.0)
((0 3) . 2.0)
((2 4) . 3.0)
((4 2) . 1.0)
((1 1) . 0.0)
((3 3) . 0.0)
((0 0) . 0.0)
((2 1) . 4.0)
((4 0) . 8.0)
((4 1) . 5.0)
((1 4) . -1.0)
((1 0) . 3.0)
((3 4) . -2.0)
((0 1) . 1.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?
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.
> (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((b . 0) (a . 100) (d . 0) (c . 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
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.
> (define g (unweighted-graph/directed '((a b) (b c) (c d) (d a))))
> (define-edge-property g A #:init 0)
> (A 'a 'b) 0
> (get-edges g) '((d a) (c d) (a b) (b c))
> (A 'a 'd) 0
> (A 'a 'e) A: no A value for edge a-e
> (A 'a 'e #:default #f) #f
> (A-set! 'a 'b 100)
> (A 'a 'b) 100
> (define-edge-property g C #:init 100)
> (C->hash)
'#hash(((c a) . 100)
((d d) . 100)
((a c) . 100)
((b c) . 100)
((a b) . 100)
((b b) . 100)
((d c) . 100)
((d b) . 100)
((b d) . 100)
((c c) . 100)
((c b) . 100)
((a a) . 100)
((a d) . 100)
((b a) . 100)
((c d) . 100)
((d a) . 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(((c a) . "c-a")
((d d) . "d-d")
((a c) . "a-c")
((b c) . "b-c")
((a b) . "a-b")
((b b) . "b-b")
((d c) . "d-c")
((d b) . "d-b")
((b d) . "b-d")
((c c) . "c-c")
((c b) . "c-b")
((a a) . "a-a")
((a d) . "a-d")
((b a) . "b-a")
((c d) . "c-d")
((d a) . "d-a"))
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
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)
(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)
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.
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?
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.
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
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?
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)
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.
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?
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.
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.}
Added in version 0.2 of package graph.
Added in version 0.2 of package graph.
5 Minimum Spanning Tree
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
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
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
7 All-pairs Shortest Paths
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)
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
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 numbers 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?
procedure
(order-smallest-last g) → list?
g : graph?
Only works for undirected graphs.
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
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.
Note: this is not the Hopcroft-Karp (ie fastest) bipartite matching algorithm.
10 Graphviz
11 Other
value
See define-vertex-property, do-bfs, and do-dfs.
value
value
value
value
value
value
value
Added in version 0.2 of package graph.