# (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}. ```scheme (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:

The following lines illustrate some of the features of library `(lispkit graph)`: ```scheme (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: ```scheme (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. ```scheme (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. ```scheme (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. ```scheme (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. ```scheme (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. ```scheme (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*****)**

\ \&#xNAN;**(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. ```scheme (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 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*. ```scheme (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*****)**

\ \&#xNAN;**(graph-add-edge! *****graph edge*****)**\ \&#xNAN;**(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*****)**

\ \&#xNAN;**(graph-remove-edge! *****graph from to*****)**\ \&#xNAN;**(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*****)**

\ \&#xNAN;**(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. ```scheme (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. ```scheme (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*****)**

\ \&#xNAN;**(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*****)**

\ \&#xNAN;**(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*****)**

\ \&#xNAN;**(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. --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://www.lisppad.app/libraries/lispkit/lispkit-graph.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.