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

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

**(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"))

**(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.**(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))

**(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.Last modified 7mo ago