Index

Package: Graphs

Description

package Glib.Graphs is

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.

Classes

Vertex (abstract)

type Vertex is abstract tagged private;

Immediate Children:

Primitive operations:

Edge (abstract)

type Edge   is abstract tagged private;

Immediate Children:

Primitive operations:

Types

Vertex_Access

type Vertex_Access is access all Vertex'Class;

Edge_Access

type Edge_Access   is access all Edge'Class;
General access types to vertices and edges

Vertex_Iterator

type Vertex_Iterator is private;

Edge_Iterator

type Edge_Iterator   is private;
Iterators other the vertices and edges of the graph

Vertices_Array

type Vertices_Array is array (Natural range <>) of Vertex_Access;

Edges_Array

type Edges_Array    is array (Natural range <>) of Edge_Access;

Breadth_Record

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.

Breadth_Vertices_Array

type Breadth_Vertices_Array is array (Natural range <>) of Breadth_Record;

Depth_Record

type Depth_Record is record
      Vertex : Vertex_Access;
      First_Discovered, End_Search : Natural;
      Predecessor : Vertex_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.

Depth_Vertices_Array

type Depth_Vertices_Array is array (Natural range <>) of Depth_Record;

Reverse_Edge_Callback

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

Connected_Component

type Connected_Component;

Connected_Component_List

type Connected_Component_List is access Connected_Component;

Constants & Global variables

Null_Vertex_Iterator (Vertex_Iterator)

Null_Vertex_Iterator : constant Vertex_Iterator;

Null_Edge_Iterator (Edge_Iterator)

Null_Edge_Iterator : constant Edge_Iterator;

Subprograms & Entries

Set_Directed

procedure Set_Directed 
(G: in out Graph;
Directed: Boolean);
Indicate whether the graph is oriented.

Is_Directed

function Is_Directed 
(G: Graph) return Boolean;
Return True if the graph is oriented

Add_Vertex

procedure Add_Vertex 
(G: in out Graph;
V: access Vertex'Class);
Add a new vertex to the graph.

Add_Edge

procedure Add_Edge 
(G: in out Graph;
E: access Edge'Class;
Source, Dest: access Vertex'Class);
Add a new edge to the graph.

Destroy (abstract)

procedure Destroy 
(E: in out Edge) is abstract;
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.

Destroy (abstract)

procedure Destroy 
(V: in out Vertex) is abstract;
Destroy the memory occupied by the vertex. This doesn't remove the vertex from the graph. This subprogram must be overriden. This subprogram shouldn't (and in fact can't) free V itself.

Destroy

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

Clear

procedure Clear 
(G: in out Graph);
Remove all the nodes and edges of the graph.

Remove

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

Remove

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

Is_Acyclic

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

Get_Src

function Get_Src  
(E: access Edge) return Vertex_Access;

Get_Dest

function Get_Dest 
(E: access Edge) return Vertex_Access;
Return the source and destination for a given edge

In_Degree

function In_Degree  
(G: Graph;
V: access Vertex'Class) return Natural;

Out_Degree

function Out_Degree 
(G: Graph;
V: access Vertex'Class) return Natural;
Return the number of edges ending on V, or starting from V.

Move_To_Front

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.

Move_To_Back

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.

Get_Index

function Get_Index 
(V: access Vertex) return Natural;
Return the uniq index associated with the vertex. Each vertex has a different index from 0 to Max_Index (Graph)

Max_Index

function Max_Index 
(G: Graph) return Natural;
Return the maximum index used for vertices in the graph.

Breadth_First_Search

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

Revert_Edge

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.

Depth_First_Search

function Depth_First_Search 
(G: Graph) return Depth_Vertices_Array;
Traverse the tree Depth_First.

Depth_First_Search

function Depth_First_Search 
(G: Graph;
Acyclic: access Boolean;
Reverse_Edge_Cb: Reverse_Edge_Callback := null) 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.

Free

procedure Free 
(List: in out Connected_Component_List);
Free the list of strongly connected components

Strongly_Connected_Components

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

Strongly_Connected_Components

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.

Kruskal

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.

First

function First 
(G: Graph) return Vertex_Iterator;
Return a pointer to the first vertex.

Next

procedure Next 
(V: in out Vertex_Iterator);
Moves V to the next vertex in the graph.

At_End

function At_End 
(V: Vertex_Iterator) return Boolean;
Return True if V points after the last vertex

Get

function Get 
(V: Vertex_Iterator) return Vertex_Access;
Get the vertex pointed to by V

First

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.

Next

procedure Next 
(E: in out Edge_Iterator);
Moves V to the next edge in the graph.

At_End

function At_End 
(E: Edge_Iterator) return Boolean;
Return True if V points after the last edge

Get

function Get 
(E: Edge_Iterator) return Edge_Access;
Get the edge pointed to by E.

Repeat_Count

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.