diff options
Diffstat (limited to '')
-rw-r--r-- | doc/ref/general/graph.texi | 65 |
1 files changed, 65 insertions, 0 deletions
diff --git a/doc/ref/general/graph.texi b/doc/ref/general/graph.texi new file mode 100644 index 00000000..1677b635 --- /dev/null +++ b/doc/ref/general/graph.texi @@ -0,0 +1,65 @@ +@node A Graph data structure +@section A Graph data structure + +This is a simple immutable directed graph. + +Most operations are O(n), since Scheme lacks a total order betwen +arbitrary objects. + +@defun make-graph [node-key-proc=identity] [node-equal?=eq?] +Constructs a new graph. + +@var{node-key-proc} should be a procedure mapping the actual nodes to +a value which can be compared. These values are sometimes called +``node keys''. +@cindex node keys + +@var{node-equal?} should return if two nodes are equal or not. +@end defun + +@defun rebuild-graph [old-graph] [nodes='()] [edges='()] +@c TODO document me +@end defun + +@defun graph-empty? graph +Does the graph contaitn +@end defun + +@defun add-node graph node edge-neighbors +Adds the value @var{node} to @var{graph}. @var{edge-neighbors} should +be a list of node keys. +@end defun + +@defun get-node graph key +Retrieve a node from the graph, given its node key. + +Returns @code{#f} if no such node exists. +@end defun + +@defun remove-node graph node +Remvoe @var{node} from @var{graph}, if it exists. +@end defun + +@defun find-dangling-node graph +Find a node in the graph which no other node ``depends'' on (has an +edge pointing at it). + +NOTE this is O(n^2) (maybe, sort of?) +Getting it faster would require building an index, which +is hard since there isn't a total order on symbols. +@end defun + + +@defun pop-dandling-node graph +Find a node as per @code{find-dangling-node}, and return two values: +the node, and a new graph without that node. +@end defun + +@defun resolve-dependency-graph graph +If each edge is assumed to indicate a nodes dependencies, then this +procedure will find return a flat list where each dependency is before +its dependants. + +If any link is missing, or a cycle exists, then the result is +undefined. +@end defun |