Graph algorithms.
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. Returns a digraph without any node whose labels are compared usingcomparator
.
Returns #t
if obj
is a digraph and #f
otherwise.
Returns the label comparator of the digraph
.
Returns the set of all labels of the nodes of the digraph
.
Returns the set of labels of all successors of the node labeled
label
in the digraph
.
Returns the set of labels of all predecessors of the node labeled
label
in the digraph
.
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.
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.
Returns the number of nodes of the digraph.
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.
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.
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.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.
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.