(lispkit graph)

Library (lispkit graph) provides a simple API for representing, manipulating, and reasoning about directed graphs.

Graphs are mutable objects encapsulating nodes and edges. Since graphs organize nodes internally in a hashtable, each graph requires an equivalence and hash function upon creation.

Here is an example for creating and initializing a directed graph with library (lispkit graph). Graph g consists of the nodes {1, 2, 3, 4, 5, 6, 7, 8} and the edges {1 → 2, 2 → 1, 2 → 4, 3 → 4, 4 → 5, 5 → 2, 5 → 8, 6 → 7, 7 → 6, 7 → 8, 2 → 8}.

(define g (graph
            identity           ; node hash function
            =                  ; node equality function
            '(1 2 3 4 5 6 7 8) ; the nodes
            '((1 2)(2 1)(2 4)  ; the edges
              (3 4)(4 5)(5 2)
              (5 8)(6 7)(7 6)
              (7 8)(2 8))))

This is the graph that is implemented by this code:

Graph g

The following lines illustrate some of the features of library (lispkit graph):

(graph-out-degree g 2)      ⇒ 3
(graph-has-edge? g 3 1)     ⇒ #f
(graph-neighbors g 2)       ⇒ (8 4 1)
(graph-reachable? g 3 1)    ⇒ #t
(graph-reachable-nodes g 3) ⇒ (1 2 8 5 4 3)

There are also a few advanced algorithms for directed graphs implemented by the library:

(graph-weakly-connected-components g)
⇒ ((1 2 6 8 7 5 4 3))  
(graph-strongly-connected-components g)
⇒ ((3) (5 2 4 1) (7 6) (8))
(graph-shortest-path g 3 8)
⇒ (3 4 5 8)
  3.0

Constructors

(make-graph hash equiv)

Creates and returns a new empty graph object using hash as the hash function and equiv as the equivalence function for nodes.

(make-eq-graph)

Returns a new empty graph object using eq-hash as the hash function and eq? as the equivalence function for nodes.

(make-eqv-graph)

Returns a new empty graph object using eqv-hash as the hash function and eqv? as the equivalence function for nodes.

(make-equal-graph)

Returns a new empty graph object using equal-hash as the hash function and equal? as the equivalence function for nodes.

(graph hash equiv nodes edges)

Creates and returns a new graph object using hash as the hash function and equiv as the equivalence function for nodes. nodes is a list of all the graph's initial nodes, and edges is a list of all the initial edges of the graph. Each edge is represented as a list of the form (from to) or (from to . label) where from and to are nodes, and label is an arbitrary Lisp object used as a label annotation.

(define g0
  (graph identity =
         '(1 2 3)
         '((1 2 . "one") (1 3 . "two"))))
(graph-neighbors+labels g0 1)
⇒ ((3 . "two") (2 . "one"))

(eq-graph nodes edges)

Creates and returns a new graph object using eq-hash as the hash function and eq? as the equivalence function for nodes. nodes is a list of all the graph's initial nodes, and edges is a list of all the initial edges of the graph. Each edge is represented as a list of the form (from to) or (from to . label) where from and to are nodes, and label is an arbitrary Lisp object used as a label annotation.

(define g (eq-graph '(1 2 3) '((1 2) (1 3))))
(graph-neighbors g 1)
⇒ (3 2)

(eqv-graph nodes edges)

Creates and returns a new graph object using eqv-hash as the hash function and eqv? as the equivalence function for nodes. nodes is a list of all the graph's initial nodes, and edges is a list of all the initial edges of the graph. Each edge is represented as a list of the form (from to) or (from to . label) where from and to are nodes, and label is an arbitrary Lisp object used as a label annotation.

(define g (eqv-graph '(1 2 3) '((1 2) (2 3) (1 3))))
(graph-edges g)
⇒ ((1 2) (1 3) (2 3))

(equal-graph nodes edges)

Creates and returns a new graph object using equal-hash as the hash function and equal? as the equivalence function for nodes. nodes is a list of all the graph's initial nodes, and edges is a list of all the initial edges of the graph. Each edge is represented as a list of the form (from to) or (from to . label) where from and to are nodes, and label is an arbitrary Lisp object used as a label annotation.

(define g (equal-graph '(1 2 3) '((1 2) (1 3 . 9.8))))
(graph-neighbors+labels g 1)
⇒ ((3 . 9.8) (2 . #f))

graph-type-tag

Symbol representing the graph type. The type-for procedure of library (lispkit type) returns this symbol for all graph objects.

Predicates

(graph? obj)

Returns #t if obj is a graph.

(eq-graph? obj)

Returns #t if obj is a graph using eq-hash as hash function and eq? as equivalence function for nodes.

(eqv-graph? obj)

Returns #t if obj is a graph using eqv-hash as hash function and eqv? as equivalence function for nodes.

(equal-graph? obj)

Returns #t if obj is a graph using eq-hash as hash function and eq? as equivalence function for nodes.

(graph-empty? graph)

Returns #t if graph is an empty graph, i.e. a graph without nodes and edges.

(graph-cyclic? graph)

Returns #t if graph is a cyclic graph, i.e. a graph which has at least one node with a path to itself.

(define g
  (eq-graph '(1 2 3 4) '((1 2)(2 3)(3 4))))
(graph-cyclic? g)       ⇒ #f
(graph-add-edge! g 4 2)
(graph-cyclic? g)       ⇒ #t

Introspection

(node-equivalence-function graph)

Returns the node equivalence function used by graph.

(node-hash-function graph)

Returns the node hash function used by graph.

(graph-has-node? graph node)

Returns #t if graph contains node; otherwise #f is returned.

(graph-nodes graph)

Returns a list of all nodes of graph.

(graph-has-edge? graph edge) (graph-has-edge? graph from to)

Returns #t if edge is contained in graph, #f otherwise. edge is a list with at least two elements: the first element is the starting node, the second element is the end node. Alternatively, it is possible to provide the start and end node explicitly as parameters from and to.

(graph-edges graph)

Returns a list of all edges of graph. Each edge is represented as a list of the form (from to) or (from to . label) where from and to are nodes, and label is an arbitrary Lisp object representing the edge label.

(define g
  (eq-graph '(1 2 3) '((1 2 . "a") (1 3))))
(graph-edges g)
⇒  ((1 2 . "a") (1 3))

(graph-edge-label graph from to)

Returns the label for the edge from node from to node to. If there is no label associated with the edge, #f is returned. It is an error when graph-edge-label gets invoked for an edge that does not exist.

(graph-in-degree graph node)

Returns the number of edges that lead into node in graph. It is an error if node is not contained in graph.

(graph-in-degree graph node)

Returns the number of edges that lead into node in graph. It is an error if node is not contained in graph.

(graph-out-degree graph node)

Returns the number of edges that originate in node within graph. It is an error if node is not contained in graph.

(graph-neighbors graph from)

Returns the number of edges that originate in node within graph. It is an error if node is not contained in graph.

(graph-neighbors graph from)

Returns a list of neighbors of node from in graph. A neighbor n is a node for which there is an edge originating in from and leading to n. graph-neighbors returns #f if from is not a node of graph.

(graph-neighbors+labels graph from)

Returns a list of pairs, consisting of neighbors with associated labels of node from in graph. A neighbor n is a node for which there is an edge originating in from and leading to n. The associated label is the label of this edge of #f if it does not exist. graph-neighbors+labels returns #f if from is not a node of graph.

(define g
  (eq-graph '(1 2 3) '((1 2 . "a") (1 3))))
(graph-neighbors+labels g 1)
⇒  ((3 . #f) (2 . "a"))

Mutation

(graph-add-node! graph node)

Adds node to graph. It is an error if the comparison and hash functions associated with graph are incompatible with node.

(graph-remove-node! graph node)

Removes node from graph if it contains node, and does nothing otherwise. It is an error if the comparison and hash functions associated with graph are incompatible with node.

(graph-add-edge! graph edge) (graph-add-edge! graph edge) (graph-add-edge! graph from to label)

Adds edge to graph. edge is represented as a list of the form (from to) or (from to . label) where from and to are nodes, and label is an arbitrary Lisp object used as a label annotation.

(graph-remove-edge! graph edge) (graph-remove-edge! graph from to) (graph-remove-edge! graph from to label)

Removes edge from graph. edge is represented as a list of the form (from to) or (from to . label) where from and to are nodes, and label is an arbitrary Lisp object used as a label annotation. The label given in edge does not need to match the label of that edge in graph for the edge to be removed.

Transformation

(graph-copy graph) (graph-copy graph rnodes)

Returns a copy of graph that only includes nodes from list rnodes; i.e. rnodes acts as a node filter. Edges that either originate or lead into nodes that are not contained in rnodes will not be copied over.

(graph-transpose graph)

Returns a copy of graph with all edges reversed, i.e. start and end nodes swapped.

(define g
  (eq-graph '(1 2 3 4) '((1 2 . "a") (1 3) (4 1))))
(graph-edges (graph-transpose g))
⇒  ((3 1) (1 4) (2 1 . "a"))

(graph-complement graph)

Returns a new graph containing all possible edges that have not been contained in graph. The new graph does not have any edge labels.

(define g
  (eq-graph '(1 2 3) '((1 2 . "a") (1 3))))
(graph-edges (graph-complement g))
⇒  ((3 2) (3 1) (3 3) (1 1) (2 2) (2 1) (2 3))

Processing graphs

(graph-fold-nodes f z graph)

This is the fundamental iterator for graph nodes. Applies the procedure f across all nodes of graph using initial state value z. That is, if graph is empty, the procedure returns z. Otherwise, some node n of graph is chosen; let g' be the remaining graph without node n. graph-fold-nodes returns (graph-fold-nodes f (f n z) g').

(graph-fold-edges f z graph)

This is the fundamental iterator for graph edges. Applies the procedure f across all edges of graph using initial state value z. That is, if graph is empty, the procedure returns z. Otherwise, some edge of graph is chosen with start node s, end node e and label l; let g' be the remaining graph without this edge. graph-fold-edges returns (graph-fold-edges f (f s e l z) g').

(graph-reachable? graph from to)

Returns #t if node to is reachable from node from, i.e. there is a path/sequence of edges for getting from node from to node to. Otherwise, #f is returned.

(graph-reachable-nodes graph from) (graph-reachable-nodes graph from limit)

Returns a list of all nodes that are reachable from node from within graph. These are nodes for which there is a path/sequence of edges starting from node from. limit specifies the maximum number of edges in the paths to explore.

(graph-topological-sort graph)

Returns a list of nodes of graph that are topologically sorted. A topological sort of a directed graph is a linear ordering of its nodes such that for every directed edge from node u to node v, u comes before v in the ordering. graph-topological-sort returns #f if graph is cyclic. In this case, it is not possible to sort all nodes topologically.

(graph-weakly-connected-components graph)

Returns a list of all weakly connected components of graph. Each component is represented as a list of nodes. A weakly connected component is a subgraph of graph where all nodes are connected to each other by some path, ignoring the direction of edges.

(graph-strongly-connected-components graph)

Returns a list of all strongly connected components of graph. Each component is represented as a list of nodes. A strongly connected component is a subgraph of graph where all nodes are connected to each other by some path.

(graph-shortest-path graph from to) (graph-shortest-path graph from to distance)

Returns a shortest path from node from to node to in graph. distance is a distance function taking a starting and ending node as arguments. By default distance returns 1.0 for all edges. A path is represented as a list of nodes.

(graph-shortest-paths graph from) (graph-shortest-paths graph from distance)

Returns all the shortest paths from node from to node to in graph. distance is a distance function taking a starting and ending node as arguments. By default distance returns 1.0 for all edges. Paths are represented as lists of nodes.