287: Graphs

by Duncan Guthrie

Status

This SRFI is currently in draft status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi-287@nospamsrfi.schemers.org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

• Received: 2026-10-12
• 60-day deadline: 2026-12-14

Abstract

This SRFI proposes a programming interface for working with graphs, based on Martin Erwig’s functional graph library design. The FGL design takes a rather different view of graphs from most graph presentations, in that the data structures are persistent, which is a good fit for Scheme. The interface is generic to any node and edge label data-type, as long as a SRFI 128 comparator can be specified.

Issues

none so far

Table of contents

• Rationale
• Graph presentation
• Node context
• R6RS conditions
• Argument restrictions and convention
• Notation and convention
• Index of exported procedures and variables
• Specification
  • Predicates
  • Constructors
  • Operations
  • Composition
  • Decomposition
  • Inspection
  • Traversal
  • Node context
• Implementation
• References
• Acknowledgements
• Copyright

Rationale

Graphs are ubiquitous in programming, but are difficult to implement efficiently. Martin Erwig’s functional graph libary design [1], dating from around 2000, has found currency in the Haskell community [2]. Persistent graphs are also included with ocamlgraph [4], the original FGL also targets Standard ML, and there is a recent port of FGL to Gleam [5]. Current implementations are mature, are distinguished by a rich set of graph operations, and are supported by availability of appropriate data structures in recent years such as integer mappings. However, there has been no graph proposal so far for Scheme, despite widespread applicability in modern compiler techniques, and for productivity in working with Scheme day-to-day. Graphs are frequently an elegant solution.

Graph presentation

The graphs described here are directed multigraphs. Nodes are indexed by non-negative integers, as in the original FGL/ML design [3], and in FGL/Haskell which gives an efficient implementation based on big-endian Patricia trees (precisely the integer mappings in SRFI 224 [7]). Representing undirected graphs is possible by adding two edges in opposite directions for every undirected edge.

In the design presented here, there may be more than one edge from a given source node to a given target node, providing that they are distinguished by label, but there cannot be more than one edge between the same incident nodes with the same label.

Apart from indexing nodes by non-negative integers, there is no restriction on the datatypes for node and edge labels, and it is possible for these to be disjoint. When constructing a graph, SRFI 128 [6] comparators for the node and edge labels respectively are required.

The order of the graph is the count of nodes, whereas the size of the graph is the count of edges. The graph-order and graph-size procedures are named so that they reflect this graph-theoretical terminology, as well as other graph libraries. Nonetheless, keep in mind that this is somewhat inconsistent with other data structure libraries for Scheme, such as SRFI 224 integer mappings, where size is the count of elements.

Node context

A node context, for some node, is an object which describes incoming edges (to which the node is target), node index, node label, and outgoing edges (from which the node is the source). This is used during graph construction, for extracting the node and any incident edges from a graph, and for mapping and folding over a graph. In the programming interface, incoming edges are represented as pairs of source nodes and edge labels, and outgoing edges are similarly represented as pairs of target nodes and edge labels.

R⁶RS conditions

In this SRFI, “an error is raised” means that an error is signalled, and that the condition has type &error (if R⁶RS conditions are available). Similarly, “an assertion violation is raised” means that an error is signalled and that the condition has type &assertion (if R⁶RS conditions are available). Furthermore, this should be a compound condition as follows:

• Raise a &who condition with the procedure name defined in this document
• Raise an &irritants condition with the irritants in the order described

R⁶RS conditions may not be available, in which implementations may simply signal an error (in the sense of the R⁷RS) with the described irritants.

Argument restrictions and convention

This specification follows the R⁶RS procedure entries convention. In addition to the naming conventions specifying type restriction for arguments where they are used, we add the following:

Notation and convention

Graph objects are printed in examples as #<graph>. Node contexts are printed in examples as #<node-context predecessors index label successors>. The order of arguments reflects the convention in FGL/ML and FGL/Haskell and makes it easier to distinguish a list of incoming pairs from a list of outgoing pairs than locating predecessors and successors last.

The name of the library is simply graph. A single library is exported: (srfi :287 graph) and the alias (srfi :287), which exports the same procedures.

Index of exported procedures and variables

Constructors

empty-graph build-graph list->graph

Predicates

graph? graph-empty? graph-contains? graph-contains-edge?

Operations

graph-order graph-size

graph-node-label-comparator graph-edge-label-comparator

graph=?

Composition

graph-embed graph-insert graph-insert-edges

Decomposition

graph-match graph-match-any

graph-delete graph-delete-edges graph-delete-all-edges

Inspection

graph-context graph-adjacencies

graph-nodes graph-predecessors graph-successors

graph-nodes+labels graph-predecessors+labels graph-successors+labels

graph-indegree graph-outdegree graph-degree

Traversal

graph-fold

Node context

node-context node-context?

node-context-incoming node-context-index node-context-label node-context-outgoing

Specification

Constructors

Construct the empty graph using comparators for the node and edge labels respectively. An assertion violation is raised with nlab-comp or elab-comp respectively as irritant if it is not a SRFI 128 comparator. Examples:

(define default-label-comparator
  (make-comparator string? string=? string<? string-hash))

(empty-graph default-label-comparator
             default-label-comparator) → <graph>
(empty-graph) → ERROR

Construct a graph using comparators for the node and edge labels respectively, followed by any number of node contexts. An assertion violation is raised in the following circumstances:

1. With nlab-comp or elab-comp respectively if they are not a SRFI 128 comparator.
2. With context’s node index as irritant if it is not a non-negative integer.
3. With context’s node label and node label comparator nlab-comp as irritants if it is not a valid label with respect to nlab-comp.
4. With the incoming and outgoing edges if they are not a proper list.
5. Next, for the incoming and outgoing edges:
   1. With a given element as irritant if it is a non-pair.
   2. Assuming that it is a pair, then:
      1. Its car (source or target node index) if it is not a non-negative integer.
      2. Its cdr (edge label) and the variadic argument list of contexts (context …) if it not contained as index of any node context. This would imply a directed edge from or to to an invalid node index.
      3. With the pair’s cdr (edge label) and elab-comp as irritants if the edge label is not a valid label with respect to elab-comp.

Notably, unlike graph-embed, the order of the contexts does not matter, in that incoming and outgoing edge pairs can refer to source or target nodes regardless of the associated context's position within the list of contexts. The other major difference from graph-embed is that in the case of duplicate node contexts (same index), the first context is preferred, and subsequent contexts are ignored.

In the following example, the same graph is built twice. This graph has nodes indexed at 0, 1 and 2, those nodes labelled “zero”, “one”, and “two”, and then an edge from node 0 to node 1, an edge from node 1 to node 2, and two edges from node 2 back to node 0. In the first case, this is built only by specifying outgoing edges. In the second example, the edge from node 0 to node 1 is added as an incoming edge to node 1, and so too the edge from node 1 to node 2 is added as an incoming edge to node 2.

(define example1
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '((1 . "edge0.1")))
    (node-context '() 1 "one"  '((2 . "edge1.2")))
    (node-context '() 2 "two"  '((0 . "edge2.0") (0 . "edge2.0'"))))

(define example2
  (build-graph default-label-comparator default-label-comparator
    (node-context '()                0 "zero" '())
    (node-context '((0 . "edge0.1")) 1 "one" '())
    (node-context '((1 . "edge1.2")) 2 "two" '((0 . "edge2.0") (0 . "edge2.0'")))))

(graph=? example1 example2) → #t

Construct a graph using comparators for the node and edge labels respectively, followed by a list of node contexts. Error-raising behaviour is consistent with build-graph, as if it was applied to pair. An assertion violation is raised with pair as irritant is not a proper list. Example:

(list->graph default-label-comparator default-label-comparator
  (list (node-context '() 0 "zero" '((1 . "edge0.1")))
        (node-context '() 1 "one"  '((2 . "edge1.2")))
        (node-context '() 2 "two"  '((0 . "edge2.0") (0 . "edge2.0'")))))
→ #<graph>

Predicates

Returns #t if obj is a graph object. Returns #f otherwise.

Returns #t if graph is empty (no nodes or edges). Returns #f otherwise. Examples:

(empty-graph?
  (empty-graph default-label-comparator default-label-comparator)) → #t
(empty-graph?
  (build-graph default-label-comparator default-label-comparator) → #t
(empty-graph?
  (build-graph default-label-comparator default-label-comparator
               (node-context '() 0 "zero" '()))) → #f
(empty-graph? "abacus") → ERROR

Procedure which tests whether graph contains a node inexed at k. The first case returns #t if there is any node at k. The second case returns #t if and only if there is a node at k and that it has label label. Returns #f otherwise. An assertion violation is raised with irritants label and graph if label is not valid with respect to graph’s node label comparator. Returns #f otherwise. Examples:

(define example1
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '((1 . "edge0.1")))
    (node-context '() 1 "one"  '((2 . "edge1.2")))
    (node-context '() 2 "two"  '((0 . "edge2.0") (0 . "edge2.0'")))))

(graph-contains? example1 0)          → #t
(graph-contains? example1 0 "zero")   → #t
(graph-contains? example1 2 "two")    → #t
(graph-contains? example1 2 "mynode") → #f

(graph-contains? example1 0 'zero) → ERROR ;; wrong label datatype!

Procedure which tests whether graph contains an edge incident originating at src and terminating at tgt. The first case returns #t if there is any edge incident. The second case returns #t if and only if there is any edge incident and that it has label label. Returns #f otherwise. An assertion violation is raised with irritants label and graph if label is not valid with respect to graph’s edge label comparator. An assertion violation is raised with src or tgt respectively and graph if they are not non-negative integers. Returns #f otherwise. Examples:

(define example1
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '((1 . "edge0.1")))
    (node-context '() 1 "one"  '((2 . "edge1.2")))
    (node-context '() 2 "two"  '((0 . "edge2.0") (0 . "edge2.0'")))))

(graph-contains-edge? example1 2 0)             → #t
(graph-contains-edge? example1 2 0 "edge2.0")   → #t
(graph-contains-edge? example1 2 0 "edge2.0'")  → #t
(graph-contains-edge? example1 2 0 "edge2.0''") → #f

(graph-contains-edge? example1 2 19)             → #f
(graph-contains-edge? example1 2 19 "elsewhere") → #f


(graph-contains-edge? example1 1 2 'edge1.2) → ERROR

Operations

Get the respective count of nodes and edges contained in graph. Examples:

(define example1
  (empty-graph default-label-comparator default-label-comparator))

(define example2
  (build-graph default-label-comparator default-label-comparator
               (node-context '() 0 "zero" '())))

(define example3
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '((1 . "edge0.1")))
    (node-context '() 1 "one"  '((2 . "edge1.2")))
    (node-context '() 2 "two"  '((0 . "edge2.0") (0 . "edge2.0'")))))

(graph-order example1) → 0
(graph-size example1)  → 0

(graph-order example2) → 1
(graph-size example2)  → 0

(graph-order example3) → 2
(graph-size example3)  → 4

Retrieve the respective node and edge label comparators for graph as SRFI 128 comparator objects.

Returns #t providing that every graph has the same nodes and edges, and that they are indexed and labelled the same. Further, the node label comparators must be the same, and also the edge label comparators. Returns #f otherwise.

(define example1
  (empty-graph default-label-comparator default-label-comparator))

(define example2
  (build-graph default-label-comparator default-label-comparator
               (node-context '() 0 "zero" '())))

(define example3
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '((1 . "edge0.1")))
    (node-context '() 1 "one"  '((2 . "edge1.2")))
    (node-context '() 2 "two"  '((0 . "edge2.0") (0 . "edge2.0'")))))

(define example4
  (build-graph default-label-comparator default-label-comparator
    (node-context '()                0 "zero" '())
    (node-context '((0 . "edge0.1")) 1 "one" '())
    (node-context '((1 . "edge1.2")) 2 "two" '((0 . "edge2.0") (0 . "edge2.0'")))))

(graph=? example1 example1) → #t
(graph=? example1 example2) → #f
(graph=? example3 example4) → #t
(graph=? example1 example2 example3 example4) #f

(define ci-label-comparator
  (make-comparator string? string-ci=? string-ci<? string-ci-hash))

(define example5
  (build-graph ci-label-comparator ci-label-comparator
    (node-context '()                0 "zero" '())
    (node-context '((0 . "edge0.1")) 1 "one" '())
    (node-context '((1 . "edge1.2")) 2 "two" '((0 . "edge2.0") (0 . "edge2.0'")))))

(graph=? example5 example3 example4) → #t
(graph=? example3 example4 example5) → #t

Composition

Embed node contexts context1, context2 and so on into graph. The error-raising behaviour is almost identical to that of build-graph on the level of each context, except in two cases. First, when an invalid source/target node is declared, an assertion violation is raised with irritants the invalid source/target node and graph with all of the work done embedding previous contexts prior to processing the current, invalid context. Similarly, the check that a node or edge label is valid is with respect to graph’s node or edge label comparators, and an assertion violation is raised with the label and graph with all of the work done embedding previous contexts.

That is, graph-embed’s behaviour as a variadic procedure can be considered equvialent to repeatedly calling graph-embed with a single argument, rather than how build-graph creates a single graph from a list of contexts. This means that edges declared earlier cannot refer to nodes which have yet to be inserted. However, it can be declared as an incoming edge, providing the source node has already been declared.

It is not an error to embed a node context corresponding to an existing node, which will be replaced by the new context. Notably, this includes elimination of any incoming or outgoing edges declared previously.

Basic examples:

(define c0 (node-context '() 0 "zero" '()))
(define c1 (node-context '((0 . "edge0.1")) 1 "one" '()))
(define c2 (node-context '((1 . "edge1.2")) 2 "two" '((0 . "edge2.0") (0 . "edge2.0'"))))

(define ge (empty-graph default-label-comparator default-label-comparator))
(define g0 (graph-embed ge c0))
(define g1 (graph-embed g0 c1))
(define g2a (graph-embed g1 c2))

(define g2b (graph-embed ge c0 c1 c2))

(define g3 (graph-embed g2a (node-context '() 3 "three" '())))

(graph=? g2a g2b) → #t
(graph=? g2b g3)  → #f

In the following example, an edge from node 0 to node 2 has not been declared yet, but it is feasible to add it as an incoming edge to node 2, since node 0 has already been declared:

(graph-embed ge
  (node-context '() 0 "zero" '((0 . "identity") (2 . "zero->two")))
  (node-context '() 0 "two"  '()))
→ ERROR

(graph-adjacencies
  (graph-embed ge
    (node-context '()                  0 "zero" '((0 . "identity")))
    (node-context '((0 . "zero->two")) 2 "two"  '())))

→ (#<node-context () 0 "zero" ((0 . "identity") (2 . "zero->two"))>
   #<node-context () 2 "two"  ()>)

Finally, replacing existing node 1:

(graph-adjacencies
  (graph-embed
    ge
    (node-context '() 0 "zero"   '())
    (node-context '() 1 "one"    '((0 . "one->zero")))
    (node-context '() 2 "two"    '())
    (node-context '() 1 "oneone" '((2 . "one->two")))))
→ (#<node-context () 0 "zero"   ()>
   #<node-context () 1 "oneone" ((2 . "one->two"))>
   #<node-context () 2 "two"    ()>)

Insert nodes with index k1 and label label1, and so on into graph. An assertion violation is raised with label1 and graph if it is not a valid label with respect to graph’s node label comparator, and so on. Examples:

(define ge
  (empty-graph default-label-comparator default-label-comparator))

(graph-nodes (graph-insert ge 0"zero" 1"one" 2"two" 3"three"))
→ (0 1 2 3)

(graph-nodes+labels (graph-insert ge 0"zero" 1"one" 2"two" 3"three"))
→ ((0 . "zero") (1 . "one") (2 . "two") (3 . "three"))

Insert edges from src1 to tgt1 with label label1 and so on into graph. An assertion violation is raised with src1, tgt1 and so on respectively as irritant if they are not a non-negative integer. An assertion violation is raised with src1 and graph as irritants if src1 is not already contained within graph or is not a valid index for a graph, and similarly with tgt1 and graph as irritants if tgt1 is not already contained within graph or is not a valid index for a graph. An assertion violation is raised with label1 and graph as irritants if label1 is invalid given graph’s edge label comparator.

Examples

(define example1
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '((1 . "edge0.1")))
    (node-context '() 1 "one"  '((2 . "edge1.2")))
    (node-context '() 2 "two"  '((0 . "edge2.0") (0 . "edge2.0'")))))

(define template
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '())
    (node-context '() 1 "one"  '())
    (node-context '() 2 "two"  '())))

(define example2
  (graph-insert-edges template
     0 1 "edge0.1"
     1 2 "edge1.2"
     2 0 "edge2.0"
     2 0 "edge2.0'"))

(graph=? example1 example2) → #t

Decomposition

Decompose a graph into two values: a node context (containing the incoming edges, index, label and outgoing edges for node k) and a graph without node k and any edges incident to k. If k is not contained within graph, then an assertion violation is raised with k and graph as irritants. Examples:

(define example1
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '((1 . "edge0.1")))
    (node-context '() 1 "one"  '())))

(define example2
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '((1 . "edge0.1")))
    (node-context '() 1 "one"  '((2 . "edge1.2")))
    (node-context '() 2 "two"  '((0 . "edge2.0") (0 . "edge2.0'")))))


(define-values (context example3) (graph-match example2 2))

context
→ #<node-context '((2 . "edge1.2")) 2 "two" '((0 . "edge2.0") (0 . "edge2.0'"))>

(graph=? example3 example1) → #t

Like graph-match, except that an arbitrary node is selected, providing that graph is non-empty. If graph is empty, then an assertion violation is raised with graph as irritant, because there exists no node to be removed.

In the following example, it is assumed that the first node to be matched will be 2, but this is not guaranteed:

(define example1
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '((1 . "edge0.1")))
    (node-context '() 1 "one"  '((2 . "edge1.2")))
    (node-context '() 2 "two"  '((0 . "edge2.0") (0 . "edge2.0'")))))

(define-values (context example2) (graph-match-any example2))
context
→ #<node-context '((2 . "edge1.2")) 2 "two" '((0 . "edge2.0") (0 . "edge2.0'"))>

(graph=? example2 example1) → #t

Remove the nodes indexed at k1, k2 and so on from graph. Similarly to the decompositions above, all edges incident with k1, k2 and so on are removed. No error is raised if k1 or k2 are not contained within graph.

(define example1
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '())))

(define example2
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '((1 . "edge0.1")))
    (node-context '() 1 "one"  '((2 . "edge1.2")))
    (node-context '() 2 "two"  '((0 . "edge2.0") (0 . "edge2.0'")))))

(graph=? example1 (graph-delete example2 1 2)) → #t

Remove the edges from src1 to tgt1 with label label1, and so on. An assertion violation is raised with src1 or tgt1 respectively as irritant if they are not a non-negative integer. An assertion violation is raised with label1 and graph as irritants if label1 is invalid given graph’s edge label comparator. No error is raised if src1 or tgt1 and so on are not contained within graph.

Examples:

(define example1
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '((1 . "edge0.1")))
    (node-context '() 1 "one"  '())
    (node-context '() 2 "two"  '((0 . "edge2.0")))))

(define example2
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '((1 . "edge0.1")))
    (node-context '() 1 "one"  '((2 . "edge1.2")))
    (node-context '() 2 "two"  '((0 . "edge2.0") (0 . "edge2.0'")))))

(define example3
  (graph-delete-edges example2
                      1 2 "edge1.2"
                      2 0 "edge2.0'"))

(graph=? example1 example3) → #t

Remove all of the edges from src1 to tgt1, and so on. This removes all edges regardless of label. An assertion violation is raised with src1 or tgt1 respectively as irritant if they are not a non-negative integer. No error is raised if src1 or tgt1 and so on are not contained within graph. Examples

(define example1
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '((1 . "edge0.1")))
    (node-context '() 1 "one"  '())
    (node-context '() 2 "two"  '())))

(define example2
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '((1 . "edge0.1")))
    (node-context '() 1 "one"  '((2 . "edge1.2")))
    (node-context '() 2 "two"  '((0 . "edge2.0") (0 . "edge2.0'")))))

(define example3
  (graph-delete-all-edges example2
                          1 2
                          2 0))

(graph=? example1 example3) → #t

Inspection

Like graph-match, except that only a node context is retrieved, which is faster as there is no need to decompose the graph into one in which k and any edges are not present. Error behaviour is identical to graph-match. Examples:

(define example1
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '((1 . "edge0.1")))
    (node-context '() 1 "one"  '((2 . "edge1.2")))
    (node-context '() 2 "two"  '((0 . "edge2.0") (0 . "edge2.0'")))))

(graph-context example1 0)
→ #<node-context ((2 . "edge2.0'") (2 . "edge2.0")) 0 "zero" ((1 . "edge0.1"))>
(graph-context example1 2)
→ #<node-context  ((1 . "edge1.2")) 2 "two" ((0 . "edge2.0'") (0 . "edge2.0"))>

Get a list of adjacencies, which is a list of node contexts consisting only of index, label and outgoing edges (incoming edges are empty). These node contexts can in turn be used to build the same graph. Examples:

(define example1
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '((1 . "edge0.1")))
    (node-context '() 1 "one"  '((2 . "edge1.2")))
    (node-context '() 2 "two"  '((0 . "edge2.0") (0 . "edge2.0'")))))

(graph-adjacencies example1)
→ (#<node-context () 0 "zero" ((1 . "edge0.1"))>
   #<node-context () 1 "one" ((2 . "edge1.2"))>
   #<node-context () 2 "two" ((0 . "edge2.0'") (0 . "edge2.0"))>)

(graph=? example1
         (list->graph default-label-comparator default-label-comparator
                      (graph-adjacencies example1)))
→ #t

Get a list of node indices contained within graph. Examples:

(define example1
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '((1 . "edge0.1")))
    (node-context '() 1 "one"  '((20 . "edge1.20")))
    (node-context '() 20 "twenty"  '((0 . "edge2.0") (0 . "edge2.0'")))))

(graph-nodes example1) → (0 1 20)

Get the predecessors of node k, as a list of source node indices. If k is not contained within graph, then an assertion violation is raised with k and graph as irritants. Examples:

(define example1
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '((1 . "edge0.1") (2 . "edge0.2")))
    (node-context '() 1 "one"  '((2 . "edge1.2")))
    (node-context '() 2 "two"  '((0 . "edge2.0") (0 . "edge2.0'") (2 . "identity")))))

(graph-predecessors 0) → (2)
(graph-predecessors 2) → (0 1 2)

Get the successors of node k as a list of target node indices. If k is not contained within graph, then an assertion violation is raised with k and graph as irritants. Examples:

(define example1
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '((1 . "edge0.1") (2 . "edge0.2")))
    (node-context '() 1 "one"  '((2 . "edge1.2")))
    (node-context '() 2 "two"  '((0 . "edge2.0") (0 . "edge2.0'") (2 . "identity")))))

(graph-successors 0) → (1 2)
(graph-successors 2) → (0 2)

Retrieve the nodes and labels contained within graph as an association list. Examples:

(define example1
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '((1 . "edge0.1")))
    (node-context '() 1 "one"  '((20 . "edge1.20")))
    (node-context '() 20 "twenty"  '((0 . "edge2.0") (0 . "edge2.0'")))))

(graph-nodes+labels example1) → ((0 . "zero") (1 . "one") (20 . "twenty"))

Get the predecessors of node k as a list of pairs of source node and edge labels. If k is not contained within graph, then an assertion violation is raised with k and graph as irritants. Examples:

(define example1
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '((1 . "edge0.1") (2 . "edge0.2")))
    (node-context '() 1 "one"  '((2 . "edge1.2")))
    (node-context '() 2 "two"  '((0 . "edge2.0") (0 . "edge2.0'") (2 . "identity")))))

(graph-predecessors+labels 0) → ((2 . "edge2.0'") (2 . "edge2.0"))
(graph-predecessors+labels 2) → ((0 . "edge0.2") (1 . "edge1.2") (2 . "identity"))

Get the successors of node k as a list of pairs of target node and edge labels. If k is not contained within graph, then an assertion violation is raised with k and graph as irritants. Examples:

(define example1
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '((1 . "edge0.1") (2 . "edge0.2")))
    (node-context '() 1 "one"  '((2 . "edge1.2")))
    (node-context '() 2 "two"  '((0 . "edge2.0") (0 . "edge2.0'") (2 . "identity")))))

(graph-successors+labels 0) → ((1 . "edge0.1") (2 . "edge0.2"))
(graph-successors+labels 2) → ((0 . "edge2.0'") (0 . "edge2.0") (2 . "identity"))

Get the indegree of node k, which is a numeric count of the incoming edges. If k is not contained within graph, then an assertion violation is raised with k and graph as irritants. Examples:

(define example1
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '((2 . "edge0.2")))
    (node-context '() 1 "one"  '((2 . "edge1.2")))
    (node-context '() 2 "two"  '((0 . "edge2.0") (0 . "edge2.0'") (2 . "identity")))))

(graph-indegree example1 0) → 2  ; two edges from node 2
(graph-indegree example1 1) → 0
(graph-indegree example1 2) → 3  ; also a loop labelled "identity"

Get the outdegree of node k, which is a numeric count of the outgoing edges. If k is not contained within graph, then an assertion violation is raised with k and graph as irritants. Examples:

(define example1
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '((2 . "edge0.2")))
    (node-context '() 1 "one"  '((2 . "edge1.2")))
    (node-context '() 2 "two"  '((0 . "edge2.0") (0 . "edge2.0'") (2 . "identity")))))

(graph-outdegree example1 0) → 1
(graph-outdegree example2 0) → 1
(graph-outdegree example3 0) → 3

Get the degree of node k, which is a numeric count of both incoming and outgoing edges. If k is not contained within graph, then an assertion violation is raised with k and graph as irritants. Examples:

(define example1
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '((2 . "edge0.2")))
    (node-context '() 1 "one"  '((2 . "edge1.2")))
    (node-context '() 2 "two"  '((0 . "edge2.0") (0 . "edge2.0'") (2 . "identity")))))

(graph-degree example1 0) → 3
(graph-degree example2 0) → 1
(graph-degree example3 0) → 6

Traversal

Fold over graph, in an unspecified order. procedure? is applied to two arguments: the current node context, and the accumulator, which begins as obj. In the following example, graph-adjacencies can be defined as follows:

(define (graph-adjacencies g)
  (list-sort
    (lambda (c1 c2)
      (< (node-context-index c1) (node-context-index c2)))
    (graph-fold
     (lambda (ctxt prev)
       (cons (node-context '()
                           (node-context-index ctxt)
                           (node-context-label ctxt)
                           (node-context-outgoing ctxt))
             prev))
     '()
     g)))

(define example1
  (build-graph default-label-comparator default-label-comparator
    (node-context '() 0 "zero" '((2 . "edge0.2")))
    (node-context '() 1 "one"  '((2 . "edge1.2")))
    (node-context '() 2 "two"  '((0 . "edge2.0") (0 . "edge2.0'") (2 . "identity")))))

(graph-adjacencies example1)
→ (#<node-context () 0 "zero" ((2 . "edge0.2"))>
   #<node-context () 1 "one" ((2 . "edge1.2"))>
   #<node-context () 2 "two" ((0 . "edge2.0'") (0 . "edge2.0") (2 . "identity"))>)

Node context

Returns #t if obj is a node context. Returns #f otherwise.

Construct a node context from incoming edges incoming, index k, label label and outgoing edges outgoing. No validation in this low-level constructor is made as there is no way to check that the node or edge labels are invalid in isolation. Instead, the graph constructors and procedures make these checks with respect to their comparators.

Implementation

The sample implementation targets Chez Scheme and is written in (mostly) portable R⁶RS. It imports various SRFIs from the Chez-SRFI grab-bag. At the time of writing, the only external dependency is the sample implementation of the draft SRFI 262 pattern matcher [8].

A full property test suite is supported. This means that SRFI 158, SRFI 194 and SRFI 252 are a dependency, which may not be widespread in many Scheme implementations.

References

• [1] Martin Erwig, 2001.
      ‘Inductive graphs and functional graph algorithms’
      Journal of Functional Programming, Vol. 11, Issue 5
• [2] Martin Erwig, Ivan Lazar Miljenovic, 2001.
      fgl: Martin Erwig’s Functional Graph Library
• [3] Martin Erwig, October 31, 1997.
      FGL/ML - A Functional Graph Library for ML
• [4] Sylvain Conchon, Jean-Christophe Filliâtre, Julien Signoles, n/d.
      A generic graph library for OCaml
• [5]  Giacomo Cavalieri, n/d.
      A package for working with graphs in Gleam
• [6] John Cowan, 2016.
      SRFI 128: Comparators (reduced)
• [7] Wolfgang Corcoran-Mathe, 2021.
      SRFI 224: Integer Mappings
• [8] Daphne Preston-Kendal, 2025 (draft).
      SRFI 262: Extensible pattern-matcher
• [9] Michael Sperber, R. Kent Dybvig, Matthew Flatt, Anton van Straaten, 2009.
      Revised [6] Report on the Algorithmic Language Scheme (online)
      Cambridge University Press, ISBN: 978-0-521-19399-3

Acknowledgements

Copyright

© 2026 Duncan Guthrie.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice (including the next paragraph) shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.