type Vertex_Access is access all Vertex'Class;
type Vertices_Array is array (Natural range <>) of Vertex_Access;
type Edges_Array is array (Natural range <>) of Edge_Access;
type Breadth_Record is record Vertex : Vertex_Access; Distance : Natural; Predecessor : Vertex_Access; end record;
type Breadth_Vertices_Array is array (Natural range <>) of Breadth_Record;
type Depth_Record is record Vertex : Vertex_Access; First_Discovered, End_Search : Natural; Predecessor : Vertex_Access; end record;
type Depth_Vertices_Array is array (Natural range <>) of Depth_Record;
type Reverse_Edge_Callback is access procedure (G : Graph; Edge : Edge_Access);
type Connected_Component_List is access Connected_Component;
Null_Vertex_Iterator : constant Vertex_Iterator;
Null_Edge_Iterator : constant Edge_Iterator;
procedure Set_Directed
( | G | : in out Graph; |
Directed | : Boolean); |
procedure Destroy
( | E | : in out Edge) is abstract; |
procedure Destroy
( | V | : in out Vertex) is abstract; |
procedure Destroy
( | G | : in out Graph); |
function Is_Acyclic
( | G | : Graph) return Boolean; |
function Get_Src
( | E | : access Edge) return Vertex_Access; |
function Get_Dest
( | E | : access Edge) return Vertex_Access; |
function Get_Index
( | V | : access Vertex) return Natural; |
function Max_Index
( | G | : Graph) return Natural; |
function Breadth_First_Search
( | G | : Graph; |
Root | : access Vertex'Class) return Breadth_Vertices_Array; |
procedure Revert_Edge
( | G | : Graph; |
E | : Edge_Access); |
function Depth_First_Search
( | G | : Graph) return Depth_Vertices_Array; |
function Depth_First_Search
( | G | : Graph; |
Acyclic | : access Boolean; | |
Reverse_Edge_Cb | : Reverse_Edge_Callback := null) return Depth_Vertices_Array; |
procedure Free
( | List | : in out Connected_Component_List); |
function Strongly_Connected_Components
( | G | : Graph) return Connected_Component_List; |
function Strongly_Connected_Components
( | G | : Graph; |
DFS | : Depth_Vertices_Array) return Connected_Component_List; |
function Kruskal
( | G | : Graph) return Edges_Array; |
function At_End
( | V | : Vertex_Iterator) return Boolean; |
function First
( | G | : Graph; |
Src, Dest | : Vertex_Access := null; | |
Directed | : Boolean := True) return Edge_Iterator; |
function At_End
( | E | : Edge_Iterator) return Boolean; |
function Repeat_Count
( | E | : Edge_Iterator) return Positive; |
General implementation for a graph.
This provides a representation for a graph structure, with nodes (vertices) connected by links (edges).
It is not intended for huges, highly-connected graphs, since there are several lists provided for efficient access to ancestor and children nodes.