From 5db1a71fb365cf12e4e41e334e22a2e5a1205371 Mon Sep 17 00:00:00 2001
From: Jed Barber <jjbarber@y7mail.com>
Date: Thu, 23 Apr 2020 16:33:35 +1000
Subject: API more or less complete
---
design_notes.txt | 18 +-
src/ada-containers-directed_graphs.ads | 508 +++++++++++++++++++++++++++++++--
2 files changed, 500 insertions(+), 26 deletions(-)
diff --git a/design_notes.txt b/design_notes.txt
index 08993b8..700ed9d 100644
--- a/design_notes.txt
+++ b/design_notes.txt
@@ -20,14 +20,14 @@ Ada.Containers.Directed_Graphs
List of types:
Extended_Node_Type
Edge_Type
- Edge_Array_Type
+ Edge_Array
Path (derived from the node array type)
Graph
Cursor
- Node_Label_Reference_Type
- Constant_Node_Label_Reference_Type
- Edge_Label_Reference_Type
- Constant_Edge_Label_Reference_Type
+ Node_Label_Reference
+ Constant_Node_Label_Reference
+ Edge_Label_Reference
+ Constant_Edge_Label_Reference
Constants:
No_Node (of Extended_Node_Type)
@@ -45,6 +45,8 @@ List of Cursor funcs:
List of Graph funcs:
"="
+ To_Graph
+ To_Cursor
Assign
Copy
@@ -53,11 +55,9 @@ List of Graph funcs:
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)
@@ -90,10 +90,12 @@ List of Graph funcs:
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 (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
diff --git a/src/ada-containers-directed_graphs.ads b/src/ada-containers-directed_graphs.ads
index 6d0a2b0..e383c0c 100644
--- a/src/ada-containers-directed_graphs.ads
+++ b/src/ada-containers-directed_graphs.ads
@@ -13,52 +13,524 @@ private with
generic
- with Node_Type is (<>);
- with Node_Array_Type is array (Positive) of Node_Type;
- with Node_Label_Type is private;
- with Edge_Label_Type is private;
+ type Node_Type is (<>);
+ type Node_Array is array (Positive) of Node_Type;
+
+ type Node_Label_Type is private;
+ type Edge_Label_Type is private;
package Ada.Containers.Directed_Graphs is
+ subtype Path is Node_Array;
+
subtype Extended_Node_Type is Node_Type'Base
range Node_Type'First - 1 ..
Node_Type'Min (Node_Type'Base'Last - 1, Node_Type'Last) + 1;
- subtype Path is Node_Array_Type;
+ No_Node : constant Extended_Node_Type := Extended_Node_Type'First;
+
+
+
type Edge_Type is record
From : Node_Type;
To : Node_Type;
end record;
- type Edge_Array_Type is array (Positive) of Edge_Type;
+ type Edge_Array is array (Positive) of Edge_Type;
+
+
+
type Graph is tagged private;
type Cursor is private;
+ No_Element : constant Cursor;
+
+ function Has_Element
+ (Position : in Cursor)
+ return Boolean;
+
+ package Graph_Iterator_Interfaces is new
+ Ada.Iterator_Interfaces (Cursor, Has_Element);
+
+ Empty_Graph : constant Graph;
+
+ overriding function "="
+ (Left, Right : in Graph)
+ return Boolean;
+
+ function To_Graph
+ (Nodes : in Node_Array;
+ Edges : in Edge_Array)
+ return Graph;
+
+ function To_Cursor
+ (Container : in Graph;
+ Node : in Node_Type)
+ return Cursor;
+
+
+
+
+ procedure Assign
+ (Target : in out Graph;
+ Source : in Graph);
+
+ function Copy
+ (Source : in Graph)
+ return Graph;
+
+ procedure Move
+ (Target, Source : in out Graph);
+
+
+
+
+ function Is_Empty
+ (Container : in Graph)
+ return Boolean;
+
+ procedure Clear
+ (Container : in out Graph);
+
+ procedure Clear_Labels
+ (Container : in out Graph);
+
+
+
+
+ function Node_Count
+ (Container : in Graph)
+ return Count_Type;
+
+ function Edge_Count
+ (Container : in Graph)
+ return Count_Type;
+
+ function Nodes
+ (Container : in Graph)
+ return Node_Array;
+
+ function Edges
+ (Container : in Graph)
+ return Edge_Array;
+
+ procedure Node_Range
+ (Container : in Graph;
+ Minimum : out Node;
+ Maximum : out Node);
+
+ function Unused_Nodes
+ (Container : in Graph;
+ Count : in Positive := 1)
+ return Node_Array;
+
+
+
+
+ procedure Insert
+ (Container : in out Graph;
+ Node : in Node_Type);
+
+ procedure Insert
+ (Container : in out Graph;
+ Node : in Node_Type;
+ Label : in Node_Label_Type);
+
+ procedure Insert
+ (Container : in out Graph;
+ Nodes : in Node_Array);
+
+ procedure Insert
+ (Container : in out Graph;
+ Edge : in Edge_Type);
+
+ procedure Insert
+ (Container : in out Graph;
+ Edge : in Edge_Type;
+ Label : in Edge_Label_Type);
+
+ procedure Insert
+ (Container : in out Graph;
+ Edges : in Edge_Array);
+
+ procedure Append
+ (Container : in out Graph;
+ Position : out Cursor);
+
+ procedure Append
+ (Container : in out Graph;
+ Label : in Node_Label_Type;
+ Position : out Cursor);
+
+ procedure Delete
+ (Container : in out Graph;
+ Node : in Node_Type);
+
+ procedure Delete
+ (Position : in out Cursor);
+
+ procedure Delete
+ (Container : in out Graph;
+ Nodes : in Node_Array);
+
+ procedure Delete
+ (Container : in out Graph;
+ Edge : in Edge_Type);
+
+ procedure Delete
+ (Container : in out Graph;
+ Edges : in Edge_Array);
+
+ procedure Append_Label
+ (Container : in out Graph;
+ Node : in Node_Type;
+ Label : in Node_Label_Type);
+
+ procedure Append_Label
+ (Position : in out Cursor;
+ Label : in Node_Label_Type);
+
+ procedure Append_Label
+ (Container : in out Graph;
+ Edge : in Edge_Type;
+ Label : in Edge_Label_Type);
+
+ procedure Replace_Label
+ (Container : in out Graph;
+ Node : in Node_Type;
+ Label : in Node_Label_Type);
+
+ procedure Replace_Label
+ (Position : in out Cursor;
+ Label : in Node_Label_Type);
+
+ procedure Replace_Label
+ (Container : in out Graph;
+ Edge : in Edge_Type;
+ Label : in Edge_Label_Type);
+
+ procedure Delete_Label
+ (Container : in out Graph;
+ Node : in Node_Type);
+
+ procedure Delete_Label
+ (Position : in out Cursor);
+
+ procedure Delete_Label
+ (Container : in out Graph;
+ Edge : in Edge_Type);
+
+ procedure Delete_Subgraph
+ (Position : in out Cursor);
+
+ procedure Swap
+ (Container : in out Graph;
+ Left, Right : in Node_Type);
+
+ procedure Swap
+ (Left, Right : in out Cursor);
- type Node_Label_Constant_Reference_Type
+
+ procedure Context
+ (Container : in Graph;
+ Node : in Node_Type;
+ Parents : out Node_Array;
+ Children : out Node_Array);
+
+ procedure Context
+ (Position : in Cursor;
+ Parents : out Node_Array;
+ Children : out Node_Array);
+
+ procedure Labeled_Context
+ (Container : in Graph;
+ Node : in Node_Type;
+ Parents : out Node_Array;
+ Children : out Node_Array;
+ Label : out Node_Label_Type);
+
+ procedure Labeled_Context
+ (Position : in Cursor;
+ Parents : out Node_Array;
+ Children : out Node_Array;
+ Label : out Node_Label_Type);
+
+ function Has_Label
+ (Container : in Graph;
+ Node : in Node_Type)
+ return Boolean;
+
+ function Has_Label
+ (Position : in Cursor)
+ return Boolean;
+
+ function Has_Label
+ (Container : in Graph;
+ Edge : in Edge_Type)
+ return Boolean;
+
+ function Label
+ (Container : in Graph;
+ Node : in Node_Type)
+ return Node_Label_Type;
+
+ function Label
+ (Position : in Cursor)
+ return Node_Label_Type;
+
+ function Label
+ (Container : in Graph;
+ Edge : in Edge_Type)
+ return Edge_Label_Type;
+
+ type Node_Label_Constant_Reference
(Element : not null access constant Node_Label_Type) is private
- with
- Implicit_Dereference => Element;
+ with Implicit_Dereference => Element;
+
+ function Constant_Label_Reference
+ (Container : in Graph;
+ Node : in Node_Type)
+ return Node_Label_Constant_Reference;
- type Node_Label_Reference_Type (Element : not null access Node_Label_Type) is private
- with
- Implicit_Dereference => Element;
+ function Constant_Label_Reference
+ (Position : in Cursor)
+ return Node_Label_Constant_Reference;
- type Edge_Label_Constant_Reference_Type
+ type Node_Label_Reference
+ (Element : not null access Node_Label_Type) is private
+ with Implicit_Dereference => Element;
+
+ function Label_Reference
+ (Container : in Graph;
+ Node : in Node_Type)
+ return Node_Label_Reference;
+
+ function Label_Reference
+ (Position : in Cursor)
+ return Node_Label_Reference;
+
+ type Edge_Label_Constant_Reference
(Element : not null access constant Edge_Label_Type) is private
- with
- Implicit_Dereference => Element;
+ with Implicit_Dereference => Element;
+
+ function Constant_Label_Reference
+ (Container : in Graph;
+ Edge : in Edge_Type)
+ return Edge_Label_Constant_Reference;
+
+ type Edge_Label_Reference
+ (Element : not null access Edge_Label_Type) is private
+ with Implicit_Dereference => Element;
+
+ function Label_Reference
+ (Container : in Graph;
+ Edge : in Edge_Type)
+ return Edge_Label_Reference;
+
+ function Neighbors
+ (Container : in Graph;
+ Node : in Node_Type)
+ return Node_Array;
+
+ function Neighbors
+ (Position : in Cursor)
+ return Node_Array;
+
+ function Parents
+ (Container : in Graph;
+ Node : in Node_Type)
+ return Node_Array;
+
+ function Parents
+ (Position : in Cursor)
+ return Node_Array;
+
+ function Children
+ (Container : in Graph;
+ Node : in Node_Type)
+ return Node_Array;
+
+ function Children
+ (Position : in Cursor)
+ return Node_Array;
+
+ function Outbound
+ (Container : in Graph;
+ Node : in Node_Type)
+ return Edge_Array;
+
+ function Outbound
+ (Position : in Cursor)
+ return Edge_Array;
+
+ function Inbound
+ (Container : in Graph;
+ Node : in Node_Type)
+ return Edge_Array;
+
+ function Inbound
+ (Position : in Cursor)
+ return Edge_Array;
+
+ function Outdegree
+ (Container : in Graph;
+ Node : in Node_Type)
+ return Count_Type;
+
+ function Outdegree
+ (Position : in Cursor)
+ return Count_Type;
+
+ function Indegree
+ (Container : in Graph;
+ Node : in Node_Type)
+ return Count_Type;
+
+ function Indegree
+ (Position : in Cursor)
+ return Count_Type;
+
+ function Degree
+ (Container : in Graph;
+ Node : in Node_Type)
+ return Count_Type;
+
+ function Degree
+ (Position : in Cursor)
+ return Count_Type;
+
+ function Has_Edge
+ (Container : in Graph;
+ Parent, Child : in Node_Type)
+ return Boolean;
+
+ function Has_Edge
+ (Parent, Child : in Cursor)
+ return Boolean;
+
+ function Has_Labeled_Edge
+ (Container : in Graph;
+ Parent, Child : Node_Type)
+ return Boolean;
+
+ function Has_Labeled_Edge
+ (Parent, Child : in Cursor)
+ return Boolean;
+
+ function Has_Neighbor
+ (Container : in Graph;
+ Left, Right : in Node_Type)
+ return Boolean;
+
+ function Has_Neighbor
+ (Left, Right : in Cursor)
+ return Boolean;
+
+
+
+
+ function Find
+ (Container : in Graph;
+ Label : in Node_Label_Type)
+ return Node_Array;
+
+ function Find
+ (Container : in Graph;
+ Label : in Edge_Label_Type)
+ return Edge_Array;
+
+ function Find_In_Subgraph
+ (Position : in Cursor;
+ Label : in Node_Label_Type)
+ return Node_Array;
+
+ function Find_In_Subgraph
+ (Position : in Cursor;
+ Label : in Edge_Label_Type)
+ return Edge_Array;
+
+ function Contains
+ (Container : in Graph;
+ Node : in Node_Type)
+ return Boolean;
+
+ function Contains
+ (Container : in Graph;
+ Node : in Node_Type;
+ Label : in Node_Label_Type)
+ return Boolean;
+
+ function Contains
+ (Container : in Graph;
+ Edge : in Edge_Type)
+ return Boolean;
+
+ function Contains
+ (Container : in Graph;
+ Edge : in Edge_Type;
+ Label : in Edge_Label_Type)
+ return Boolean;
+
+ function Contains_Label
+ (Container : in Graph;
+ Label : in Node_Label_Type)
+ return Boolean;
+
+ function Contains_Label
+ (Container : in Graph;
+ Label : in Edge_Label_Type)
+ return Boolean;
+
+ function Contains_In_Subgraph
+ (Position : in Cursor;
+ Node : in Node_Type)
+ return Boolean;
+
+ function Contains_In_Subgraph
+ (Position : in Cursor;
+ Node : in Node_Type;
+ Label : in Node_Label_Type)
+ return Boolean;
+
+ function Contains_In_Subgraph
+ (Position : in Cursor;
+ Edge : in Edge_Type)
+ return Boolean;
+
+ function Contains_In_Subgraph
+ (Position : in Cursor;
+ Edge : in Edge_Type;
+ Label : in Edge_Label_Type)
+ return Boolean;
+
+ function Contains_Label_In_Subgraph
+ (Position : in Cursor;
+ Label : in Node_Label_Type)
+ return Boolean;
+
+ function Contains_Label_In_Subgraph
+ (Position : in Cursor;
+ Label : in Edge_Label_Type)
+ return Boolean;
+
+
+
+
+ function Iterate
+ (Container : in Graph)
+ return Graph_Iterator_Interfaces.Reversible_Iterator'Class;
- type Edge_Label_Reference_Type (Element : not null access Edge_Label_Type) is private
- with
- Implicit_Dereference => Element;
+ function Iterate_Subgraph
+ (Container : in Graph;
+ Position : in Cursor)
+ return Graph_Iterator_Interfaces.Forward_Iterator'Class;
private
--
cgit