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.
<group>Glib, the general-purpose library</group>
procedure Add_Edge
(G : in out Graph;
E : access Edge'Class;
Source, Dest : access Vertex'Class)
Add a new edge to the graph. The edge is allocated automatically if needed
procedure Add_Edge
(G : in out Graph;
Source, Dest : access Vertex'Class)
Add a new edge to the graph. The edge is allocated automatically if needed
procedure Add_Vertex (G : in out Graph; V : access Vertex'Class)
Add a new vertex to the graph
function At_End (E : Edge_Iterator) return Boolean
Return True if V points after the last edge
function At_End (V : Vertex_Iterator) return Boolean
Return True if V points after the last vertex
function Breadth_First_Search (G : Graph; Root : access Vertex'Class)
return Breadth_Vertices_Array
Traverse the tree Breadth_First, and sort the nodes accordingly. The returned list is sorted so that all nodes at a distance k from Root are found before the nodes at a distance (k+1). The running time is O(vertices + edges).
type Breadth_Record is record
Vertex : Vertex_Access;
Distance : Natural;
Predecessor : Vertex_Access;
end record;
Distance is the shortest distance from the root of the breadth-first search to Vertex. The graph is considered as unweighted. Thus, Distance is 1 for direct children of Root, 2 for grand-children,... Predecessor is the parent of Vertex used when computing the distance.
type Breadth_Vertices_Array is array (Natural range <>) of Breadth_Record;
procedure Clear (G : in out Graph)
Remove all the nodes and edges of the graph.
type Connected_Component (Num_Vertices : Natural) is record
Vertices : Vertices_Array (1 .. Num_Vertices);
Next : Connected_Component_List;
end record;
type Connected_Component_List is access Connected_Component;
function Depth_First_Search (G : Graph) return Depth_Vertices_Array
Traverse the tree Depth_First.
function Depth_First_Search
(G : Graph;
Acyclic : access Boolean;
Reverse_Edge_Cb : Reverse_Edge_Callback := null;
Force_Undirected : Boolean := False)
return Depth_Vertices_Array
Same as above, but Acyclic is also modified to indicate whether G is acyclic. If Reverse_Edge_Cb is not null, then it is called to reverse the ends of selected edges, so that the final graph is acyclic. Note that you must revert the ends, or there will be an infinite loop. You might also want to mark the edge as reverted somehow, so as to draw the arrows on the correct side, if your application is graphical.
If Reverse_Edge_Cb is null, no edge is reverted, and the graph is unmodified.
If Force_Undirected is True, then a directed graph is temporarily considered as undirected, and reverse edges will be returned. In this case, Reverse_Edge_Cb will never be called (and the graph never considered as acyclic).
type Depth_Record is record
Vertex : Vertex_Access;
First_Discovered, End_Search : Natural;
Predecessor : Vertex_Access;
Edge : Edge_Access;
end record;
First_Discovered and End_Search are the two timestamps computed during the search. The former is the time Vertex was first discovered. The latter is the time when all the children of vertex were fully processed. Predecessor is the parent of Vertex.
type Depth_Vertices_Array is array (Natural range <>) of Depth_Record;
procedure Destroy (E : in out Edge)
Destroy the memory occupied by the edge. This doesn't remove the edge from the graph. You should override this subprogram for the specific edge type you are using. This subprogram shouldn't (and in fact can't) free E itself.
procedure Destroy (G : in out Graph)
Destroy all the nodes and edges of the graph, and then free the memory occupied by the graph itself
procedure Destroy (V : in out Vertex)
Destroy the memory occupied by the vertex. This doesn't remove the vertex from the graph. This subprogram must be overridden. This subprogram shouldn't (and in fact can't) free V itself.
type Edge is tagged private;
type Edge_Access is access all Edge'Class;
General access types to vertices and edges
type Edge_Iterator is private;
Iterators other the vertices and edges of the graph
type Edges_Array is array (Natural range <>) of Edge_Access;
function First (G : Graph) return Vertex_Iterator
Return a pointer to the first vertex.
function First
(G : Graph;
Src, Dest : Vertex_Access := null;
Directed : Boolean := True)
return Edge_Iterator
Return a pointer to the first edge from Src to Dest. If either Src or Dest is null, then any vertex matches. Thus, if both parameters are nulll, this iterator will traverse the whole graph. Note: there might be duplicates returned by this iterator, especially when the graph is not oriented. Directed can be used to temporarily overrides the setting in the graph: If Directed is True, the setting of G is taken into account. If Directed is False, the setting of G is ignored, and the graph is considered as not directed.
procedure Free (List : in out Connected_Component_List)
Free the list of strongly connected components
function Get (E : Edge_Iterator) return Edge_Access
Get the edge pointed to by E.
function Get (V : Vertex_Iterator) return Vertex_Access
Get the vertex pointed to by V
function Get_Dest (E : access Edge) return Vertex_Access
Return the source and destination for a given edge
function Get_Index (V : access Vertex) return Natural
Return the uniq index associated with the vertex. Each vertex has a different index from Min_Vertex_Index to Max_Index (Graph)
function Get_Src (E : access Edge) return Vertex_Access
Return the source and destination for a given edge
type Graph is private;
function In_Degree (G : Graph; V : access Vertex'Class) return Natural
Return the number of edges ending on V, or starting from V.
function Is_Acyclic (G : Graph) return Boolean
Return True if G contains no cycle. Note that this requires a depth-first search, the running time is thus O (edges + vertices). G must be oriented
function Is_Directed (G : Graph) return Boolean
Return True if the graph is oriented
function Kruskal (G : Graph) return Edges_Array
Return a minimum spanning tree of G using Kruskal's algorithm. This algorithm runs in O(E * log E), with E = number of edges.
function Max_Index (G : Graph) return Integer
Return the maximum index used for vertices in the graph. Return -1 if the graph is empty.
Min_Vertex_Index : constant := 0;
indexes for vertices go from Min_Vertex_Index .. Max_Index (Graph)
procedure Move_To_Back (G : in out Graph; V : access Vertex'Class)
Move V to the back of the list of vertices in the graph, so that the iterators will return this item last. All iterators become obsolete.
procedure Move_To_Front (G : in out Graph; V : access Vertex'Class)
Move V to the front of the list of vertices in the graph, so that the iterators will return this item first. All iterators become obsolete.
procedure Next (E : in out Edge_Iterator)
Moves V to the next edge in the graph.
procedure Next (V : in out Vertex_Iterator)
Moves V to the next vertex in the graph.
Null_Edge_Iterator : constant Edge_Iterator;
Null_Vertex_Iterator : constant Vertex_Iterator;
function Out_Degree (G : Graph; V : access Vertex'Class) return Natural
Return the number of edges ending on V, or starting from V.
procedure Remove (G : in out Graph; E : access Edge'Class)
Remove the edge from the graph. The primitive subprogram Destroy is called for the edge. Any iterator currently pointing to E becomes invalid
procedure Remove (G : in out Graph; V : access Vertex'Class)
Remove the vertex from the graph. Destroy is called for the vertex. Note that all the edges to or from the vertex are destroyed (see Remove above). Any iterator currently pointing to V becomes invalid
function Repeat_Count (E : Edge_Iterator) return Positive
Return the number of similar edges (same ends) that were found before, and including this one). For instance, if there two edges from A to B, then the first one will have a Repeat_Count of 1, and the second 2.
type Reverse_Edge_Callback is access
procedure (G : Graph; Edge : Edge_Access);
Callback called when the two ends of the edge should be reverted, so as to make the graph acyclick
procedure Revert_Edge (G : Graph; E : Edge_Access)
Revert the two ends of Edge. This is meant to be used as a callback for Depth_First_Search so as to make the graph acyclic.
procedure Set_Directed (G : in out Graph; Directed : Boolean)
Indicate whether the graph is oriented.
function Strongly_Connected_Components (G : Graph)
return Connected_Component_List
Return the list of strongly connected components. This is a linear time algorithm O(vertices + edges).
function Strongly_Connected_Components
(G : Graph; DFS : Depth_Vertices_Array)
return Connected_Component_List
Same as above, but a depth-first search has already been run on G, and we reuse the result. This is of course more efficient than the previous function.
type Vertex is tagged private;
type Vertex_Access is access all Vertex'Class;
General access types to vertices and edges
type Vertex_Iterator is private;
Iterators other the vertices and edges of the graph
type Vertices_Array is array (Natural range <>) of Vertex_Access;