# (rapid graph)

Graph algorithms.

## Directed graphs

A directed graph or digraph consists of a set of nodes and a set of edges. Each node is distinguished by its label. Each edge has a source node and a target node. There is at most one edge between two nodes. The nodes that are targets of edges whose source is a given node are the successors of the given node. The predecessors of a given node are those nodes for which the given node is a successor.

## Procedures

### `(digraph comparator)`

Returns a digraph without any node whose labels are compared using `comparator`.

### `(digraph? obj)`

Returns `#t` if `obj` is a digraph and `#f` otherwise.

### `(digraph-label-comparator digraph)`

Returns the label comparator of the `digraph`.

### `(digraph-label-set digraph)`

Returns the set of all labels of the nodes of the `digraph`.

### `(digraph-successor-set digraph label)`

Returns the set of labels of all successors of the node labeled `label` in the `digraph`.

### `(digraph-predecessor-set digraph label)`

Returns the set of labels of all predecessors of the node labeled `label` in the `digraph`.

### `(digraph-adjoin-edge digraph source target)`

Returns a digraph that results from adjoining an edge between the nodes labeled `source` and `target` to the `digraph`. If there is already an edge between the `source` and `target`, no edge is added. If there is no node labeled `source` or `target`, a node with that label is adjoined as well.

### `(digraph-adjoin-node digraph label . targets)`

Returns a digraph that results from adjoining a node labeled `label` and edges from that node to the nodes labeled `targets` to the `digraph`. If there is already a node `label`, no node is added. If there is already an edge between the `label` and one of the `targets`, that edge is not added. If there is no node labeled by one of `targets`, a node with that label is adjoined as well.

### `(digraph-node-count digraph)`

Returns the number of nodes of the digraph.

### `(digraph-find predicate digraph failure)`

Returns the label of an arbitrarily chosen node of the `digraph` such that `predicate` returns a true value when invoked with the label and the nodes successor and predecessor sets as arguments, or the result of tail-calling `failure` with no arguments when there is none.

### `(digraph-fold proc nil digraph)`

Invokes `proc` for each node of the `digraph` with three arguments: the label of the node, its successor set, its predecessor set, and an accumulated result of the previous invokation. For the first invokation, `nil` is used as the last argument. Returns the result of the last invokation or `nil` if there was no invokation.

### `(digraph->alist digraph)`

Returns a newly allocated association list with one association for each node of `digraph`. Each association is a pair whose car is the label and whose cdr is a newly allocated list of the successors' labels of the node.

### `(alist->digraph comparator alist)`

procedure({alist->digraph comparator alist}) Returns a newly allocated digraph, created as if by `digraph` using the comparator `comparator`, that has one node per association in `alist`. Each association is a pair whose car is the label and whose cdr is a list of the successors' labels of the node.

### `(digraph-sccs digraph)`

Returns a topologically sorted list of the strongly-connected components of the `digraph`. Each strongly-connected component is a newly allocated list of the labels of the nodes belonging to that strongly-connected component.