summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--design_notes.txt102
1 files changed, 102 insertions, 0 deletions
diff --git a/design_notes.txt b/design_notes.txt
new file mode 100644
index 0000000..1da9414
--- /dev/null
+++ b/design_notes.txt
@@ -0,0 +1,102 @@
+
+
+
+Directed Graph Library Design Notes
+
+
+
+package structure:
+
+
+
+Ada.Containers.Directed_Graphs
+ - generic over discrete node type, array of node type, node label type, edge label type
+ - implemented using the adjacancy list method
+ - allows both nodes and edges to be labeled, one arbitrary type for each
+ - nodes and edges don't *have* to be labeled
+ - API in the style of the Ada Containers library
+ - inspiration also taken from Haskell Data.Graph.Inductive.Graph
+
+List of types:
+ Extended_Node_Type
+ Edge_Type
+ Edge_Type_Array
+ Path (derived from the node array type)
+ Graph
+ Cursor
+ Node_Label_Reference
+ Constant_Node_Label_Reference
+ Edge_Label_Reference
+ Constant_Edge_Label_Reference
+
+Constants:
+ No_Node (of Extended_Node_Type)
+ No_Element (of Cursor)
+ Empty_Graph (of Graph)
+
+List of Cursor funcs:
+ Has_Element
+ Element (cursor -> node)
+
+ Equal_Subgraph
+ Subgraph_Node_Count
+
+ (generally for most non-mutable Graph functions that operate on an input of a single node, a cursor is also fine)
+
+List of Graph funcs:
+ "="
+
+ Assign
+ Copy
+ Move
+
+ Is_Empty
+ Clear
+ Clear_Labels
+ To_Cursor (node -> cursor)
+
+ Node_Count (a measure of number of nodes in the graph)
+ Edge_Count (a measure of number of edges in the graph)
+
+ Nodes (array of all nodes in the graph)
+ Edges (array of all edges in the graph)
+ Node_Range (returns minimum and maximum of nodes in the graph)
+ Unused_Nodes (returns an array of a specified number of nodes not used in the graph)
+
+ Insert (add a node at a given position (with label), add an edge (with label), add multiple nodes, multiple edges)
+ Append (add a node at the next available position (with label), return the node added)
+ Delete (remove a node, an edge, multiple nodes, multiple edges, from the graph)
+ Append_Label (give a node or an edge a label)
+ Replace_Label
+ Delete_Label (remove a label from a node or an edge)
+ Delete_Subgraph
+ Swap (switches two nodes in the graph)
+
+ Context (returns all parents of a node, all children of the node)
+ Labeled_Context (returns all parents of a node, the label of the node, and all the children of the node)
+ Has_Label (predicates for testing if a node or edge has a label in the graph)
+ Label (returns the label of a node or an edge if it has one)
+ Label_Reference (accessor to a label)
+ Constant_Label_Reference (constant accessor)
+ Neighbors (two nodes are neighbors if they have edges in both directions)
+ Parents (nodes with edges going into a node)
+ Children (nodes with edges coming from a node)
+ Outbound (edges going out of a node)
+ Inbound (edges coming into a node)
+ Outdegree (outbound degree of a node)
+ Indegree (inbound degree of a node)
+ Degree (degree of a node; how many other nodes are connected)
+ Has_Edge (check whether two nodes are connected)
+ Has_Labeled_Edge (check whether two nodes are connected with a labeled edge)
+ Has_Neighbor (check whether two nodes are neighbors)
+
+ Find (find a node or edge with a particular label)
+ Find_In_Subgraph
+ Contains (check whether a node or an edge is in the graph)
+ Contains_Label (check if graph contains a particular node/edge label)
+
+ Iterate
+ Iterate_Subgraph
+
+
+