Directed Graph Library Design Notes



package structure:



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_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)

 (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:
 "="
 To_Graph
 To_Cursor

 Assign
 Copy
 Move

 Is_Empty
 Clear
 Clear_Labels

 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 nodes or edges 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)
 Contains_In_Subgraph
 Contains_Label_In_Subgraph

 Iterate
 Iterate_Subgraph
 First
 Last
 Next
 Previous