Racket Generic Graph Library

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.

• 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 (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.

• procedure (get-edges g) → list?

  g : graph?

  Returns a list of edges in the graph.

• procedure (in-edges g) → sequence?

  g : 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.

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

2 Graph Constructors

2.1 Unweighted Graphs

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

2.2 Weighted Graphs

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

2.3 Matrix Graphs

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

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

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.

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.

4 Basic Graph Functions

4.1 Breadth-first Search

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.

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.

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

4.2 Depth-first Search