diff options
author | Hugo Hörnquist <hugo@lysator.liu.se> | 2023-09-13 00:01:28 +0200 |
---|---|---|
committer | Hugo Hörnquist <hugo@lysator.liu.se> | 2023-09-13 00:01:28 +0200 |
commit | a82b6c772089aa46e30c6c89ef48f514294df3cb (patch) | |
tree | e25d9b6fd1fefe8b6ac293a5c0b53293872a8f54 /doc/ref/general/graph.texi | |
parent | Add basic documentation for lens. (diff) | |
parent | Even more documentation. (diff) | |
download | calp-a82b6c772089aa46e30c6c89ef48f514294df3cb.tar.gz calp-a82b6c772089aa46e30c6c89ef48f514294df3cb.tar.xz |
Merge branch 'next' into datarewrite-structures
Diffstat (limited to 'doc/ref/general/graph.texi')
-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 |