Graph g
Graph g
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 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.