diff options
| -rw-r--r-- | design_notes.txt | 102 |
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 + + + |