Modifying a graph
-
procedure Set_Directed (G : in out Graph; Directed : Boolean);
-
function Is_Directed (G : Graph) return Boolean;
-
procedure Add_Vertex (G : in out Graph; V : access Vertex'Class);
-
procedure Add_Edge
(G : in out Graph;
E : access Edge'Class;
Source, Dest : access Vertex'Class);
-
procedure Destroy (E : in out Edge) is abstract;
-
procedure Destroy (V : in out Vertex) is abstract;
-
procedure Destroy (G : in out Graph);
-
procedure Clear (G : in out Graph);
-
procedure Remove (G : in out Graph; E : access Edge'Class);
-
procedure Remove (G : in out Graph; V : access Vertex'Class);
-
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 In_Degree (G : Graph; V : access Vertex'Class) return Natural;
function Out_Degree (G : Graph; V : access Vertex'Class) return Natural;
-
procedure Move_To_Front (G : in out Graph; V : access Vertex'Class);
-
procedure Move_To_Back (G : in out Graph; V : access Vertex'Class);
-
function Get_Index (V : access Vertex) return Natural;
-
function Max_Index (G : Graph) return Natural;
Breadth First Search
This search algorithm traverse the tree layer after layer (first the
nodes closer to the specified root, then the grand-children of this
root, and so on).
-
function Breadth_First_Search (G : Graph; Root : access Vertex'Class)
return Breadth_Vertices_Array;
Depth First Search
This algorithm traverse the tree in depth, ie all the descendents of the
first child are found before the second child.
This algorithm has several properties: it can indicate whether the graph
is cyclic. Moreover, the subgraph formed by all the nodes and the edges
between a vertex and its predecessor (see the structure
Depth_Record) is
a tree.
If the graph is acyclic, then the resulting array is sorted
topologically: if G contains an edge (u, v), then u appears before v.
-
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;
Strongly connected components
Strongly connected components in a directed graph are the maximal set of
vertices such that for every pair {u, v} of vertices in the set, there
exist a path from u to v and a path from v to u.
Two vertices are in different strongly connected components if there
exist at most one of these paths.
-
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;
Minimum spanning trees
A minimum spanning tree is a subset of the edges of G that forms a
tree (acyclic) and connects all the vertices of G.
Note that the number of edges in the resulting tree is always
(number of vertices of G) - 1
-
function Kruskal (G : Graph) return Edges_Array;
Vertex iterator
-
function First (G : Graph) return Vertex_Iterator;
-
procedure Next (V : in out Vertex_Iterator);
-
function At_End (V : Vertex_Iterator) return Boolean;
-
function Get (V : Vertex_Iterator) return Vertex_Access;
Edge iterator
-
function First
(G : Graph;
Src, Dest : Vertex_Access := null;
Directed : Boolean := True)
return Edge_Iterator;
-
procedure Next (E : in out Edge_Iterator);
-
function At_End (E : Edge_Iterator) return Boolean;
-
function Get (E : Edge_Iterator) return Edge_Access;
-
function Repeat_Count (E : Edge_Iterator) return Positive;