From 0fac96af120a47ed686c26745af50288086e22d3 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Hugo=20H=C3=B6rnquist?= <hugo@lysator.liu.se>
Date: Tue, 12 Sep 2023 23:51:26 +0200
Subject: Even more documentation.

---
 doc/ref/general/graph.texi | 65 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 65 insertions(+)
 create mode 100644 doc/ref/general/graph.texi

(limited to 'doc/ref/general/graph.texi')

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
-- 
cgit v1.2.3