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