# (lispkit graph)

Last updated

Last updated

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

This is the graph that is implemented by this code:

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

:

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

Constructors

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

Returns a new empty graph object using `eq-hash`

as the hash function and `eq?`

as the equivalence function for nodes.

Returns a new empty graph object using `eqv-hash`

as the hash function and `eqv?`

as the equivalence function for nodes.

Returns a new empty graph object using `equal-hash`

as the hash function and `equal?`

as the equivalence function for nodes.

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.

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.

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.

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.

Symbol representing the `graph`

type. The `type-for`

procedure of library `(lispkit type)`

returns this symbol for all graph objects.

Predicates

Returns `#t`

if *obj* is a graph.

Returns `#t`

if *obj* is a graph using `eq-hash`

as hash function and `eq?`

as equivalence function for nodes.

Returns `#t`

if *obj* is a graph using `eqv-hash`

as hash function and `eqv?`

as equivalence function for nodes.

Returns `#t`

if *obj* is a graph using `eq-hash`

as hash function and `eq?`

as equivalence function for nodes.

Returns `#t`

if *graph* is an empty graph, i.e. a graph without nodes and edges.

Returns `#t`

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

Introspection

Returns the node equivalence function used by *graph*.

Returns the node hash function used by *graph*.

Returns `#t`

if *graph* contains *node*; otherwise `#f`

is returned.

Returns a list of all nodes of *graph*.

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

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.

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.

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

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

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

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

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

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

Mutation

Adds *node* to *graph*. It is an error if the comparison and hash functions associated with *graph* are incompatible with *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*.

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.

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

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.

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

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

Processing graphs

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')`

.

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')`

.

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.

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.

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.

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.

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.

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.

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.

**(make-graph ****hash equiv****)**

**(make-eq-graph)**

**(make-eqv-graph)**

**(make-equal-graph)**

**(graph ****hash equiv nodes edges****)**

**(eq-graph ****nodes edges****)**

**(eqv-graph ****nodes edges****)**

**(equal-graph ****nodes edges****)**

**graph-type-tag**

**(graph? ****obj****)**

**(eq-graph? ****obj****)**

**(eqv-graph? ****obj****)**

**(equal-graph? ****obj****)**

**(graph-empty? ****graph****)**

**(graph-cyclic? ****graph****)**

**(node-equivalence-function ****graph****)**

**(node-hash-function ****graph****)**

**(graph-has-node? ****graph node****)**

**(graph-nodes ****graph****)**

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

**(graph-edges ****graph****)**

**(graph-edge-label ****graph from to****)**

**(graph-in-degree ****graph node****)**

**(graph-in-degree ****graph node****)**

**(graph-out-degree ****graph node****)**

**(graph-neighbors ****graph from****)**

**(graph-neighbors ****graph from****)**

**(graph-neighbors+labels ****graph from****)**

**(graph-add-node! ****graph node****)**

**(graph-remove-node! ****graph node****)**

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

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

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

**(graph-transpose ****graph****)**

**(graph-complement ****graph****)**

**(graph-fold-nodes ****f z graph****)**

**(graph-fold-edges ****f z graph****)**

**(graph-reachable? ****graph from to****)**

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

**(graph-topological-sort ****graph****)**

**(graph-weakly-connected-components ****graph****)**

**(graph-strongly-connected-components ****graph****)**

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

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