## Documentation

Table of Contents
Class Inheritance Tree
Widget Screenshots
Package groups

## Index

Package: Graphs

- Goto spec source

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

- Goto declaration in source
- Goto full declaration in source

    type Vertex is abstract tagged private;

#### Immediate Children:

Gtkada.Canvas.Canvas_Item_Record

#### Primitive operations:

Destroy

- To API doc
- To spec

Get_Index

- To API doc
- To spec

### Edge (abstract)

- Goto declaration in source
- Goto full declaration in source

    type Edge   is abstract tagged private;

#### Immediate Children:

Gtkada.Canvas.Canvas_Link_Record

#### Primitive operations:

Destroy

- To API doc
- To spec

Get_Dest

- To API doc
- To spec

Get_Src

- To API doc
- To spec

# Types

### Graph

- Goto declaration in source
- Goto full declaration in source

    type Graph  is private;

### Vertex_Access

- Goto declaration in source

    type Vertex_Access is access all Vertex'Class;

### Edge_Access

- Goto declaration in source

    type Edge_Access   is access all Edge'Class;

General access types to vertices and edges

### Vertex_Iterator

- Goto declaration in source

    type Vertex_Iterator is private;

### Edge_Iterator

- Goto declaration in source
- Goto full declaration in source

    type Edge_Iterator   is private;

Iterators other the vertices and edges of the graph

### Vertices_Array

- Goto declaration in source

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

### Edges_Array

- Goto declaration in source

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

### Breadth_Record

- Goto declaration in source

    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

- Goto declaration in source

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

### Depth_Record

- Goto declaration in source

    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

- Goto declaration in source

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

### Reverse_Edge_Callback

- Goto declaration in source

    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

- Goto declaration in source
- Goto full declaration in source

    type Connected_Component;

### Connected_Component_List

- Goto declaration in source

    type Connected_Component_List is access Connected_Component;

# Constants & Global variables

### Null_Vertex_Iterator

- Goto declaration in source

(Vertex_Iterator)

    Null_Vertex_Iterator : constant Vertex_Iterator;

### Null_Edge_Iterator

- Goto declaration in source
- Goto full declaration in source

(Edge_Iterator)

    Null_Edge_Iterator : constant Edge_Iterator;

# Subprograms & Entries

### Set_Directed

- Goto spec in source

    procedure Set_Directed (G: in out Graph;Directed: Boolean);

Indicate whether the graph is oriented.

### Is_Directed

- Goto spec in source

    function Is_Directed (G: Graph) return Boolean;

Return True if the graph is oriented

### Add_Vertex

- Goto spec in source

    procedure Add_Vertex (G: in out Graph;V: access Vertex'Class);

Add a new vertex to the graph.

### Add_Edge

- Goto spec in source

    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)

- Goto spec in source

    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)

- Goto spec in source

    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

- Goto spec in source

    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

- Goto spec in source

    procedure Clear (G: in out Graph);

Remove all the nodes and edges of the graph.

### Remove

- Goto spec in source

    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

- Goto spec in source

    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

- Goto spec in source

    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

- Goto spec in source

    function Get_Src  (E: access Edge) return Vertex_Access;

### Get_Dest

- Goto spec in source

    function Get_Dest (E: access Edge) return Vertex_Access;

Return the source and destination for a given edge

### In_Degree

- Goto spec in source

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

### Out_Degree

- Goto spec in source

    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

- Goto spec in source

    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

- Goto spec in source

    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

- Goto spec in source

    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

- Goto spec in source

    function Max_Index (G: Graph) return Natural;

Return the maximum index used for vertices in the graph.

### Breadth_First_Search

- Goto spec in source

    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

- Goto spec in source

    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

- Goto spec in source

    function Depth_First_Search (G: Graph) return Depth_Vertices_Array;

Traverse the tree Depth_First.

### Depth_First_Search

- Goto spec in source

    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

- Goto spec in source

    procedure Free (List: in out Connected_Component_List);

Free the list of strongly connected components

### Strongly_Connected_Components

- Goto spec in source

    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

- Goto spec in source

    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

- Goto spec in source

    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

- Goto spec in source

    function First (G: Graph) return Vertex_Iterator;

Return a pointer to the first vertex.

### Next

- Goto spec in source

    procedure Next (V: in out Vertex_Iterator);

Moves V to the next vertex in the graph.

### At_End

- Goto spec in source

    function At_End (V: Vertex_Iterator) return Boolean;

Return True if V points after the last vertex

### Get

- Goto spec in source

    function Get (V: Vertex_Iterator) return Vertex_Access;

Get the vertex pointed to by V

### First

- Goto spec in source

    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

- Goto spec in source

    procedure Next (E: in out Edge_Iterator);

Moves V to the next edge in the graph.

### At_End

- Goto spec in source

    function At_End (E: Edge_Iterator) return Boolean;

Return True if V points after the last edge

### Get

- Goto spec in source

    function Get (E: Edge_Iterator) return Edge_Access;

Get the edge pointed to by E.

### Repeat_Count

- Goto spec in source

    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.