Graph Representation Using an Adjacency List

Summary

The graph abstract data type is very useful for identifying relationships between entities. Graphs can be used to represent navigation on a map, with the entities being the way-points and the connections between the way-points being the named routes, with additional attributes of distance and travel time. Graphs can also be used to represent states and state transitions for finite state diagrams.

Both maps and finite state diagrams benefit from a directed graph, where relationships are directional. There are also undirected graphs, which can be used to model such things as molecular structures, where the atoms are the entities and the connections between them are the chemical bonds.

The following example shows an implementation of an undirected graph with a fixed number of entities. A fixed length graph is an efficient representation when the number of entities you are modeling will not grow, such as when you are modeling the structure of a protein. This example defines a generic data type for a graph. The generic data type allows the programmer to specialize the graph upon instantiation by specifying the type of the entity and the number of entities in the graph.

As is my custom, I am using the Ada programming language for my example. The generic abstract data type is defined in an Ada package, and a simple procedure is written to illustrate how the package is used.

Ada Package Specification

The Ada package specification defines the public interfaces to the abstract data type and the private internal data representations used in the abstract data type.

------------------------------------------------------------------
-- Generic Undirected Graph Package --
------------------------------------------------------------------
generic
   type Element is private;
   Max_Elements : Positive;
package Fixed_Length_Graph is
   subtype Element_Id is Positive range 1..Max_Elements;
   type Adjacency_List is array(Element_Id) of Boolean;
   type Undirected_Graph is tagged private;
   Procedure Add_Element(to : in out Undirected_Graph;
                              Item : in Element;
                              Id   : in Element_Id);
   Procedure Add_Adjacencies(to : in out Undirected_Graph;
                                   Item : in Element_Id;
                                   List : in Adjacency_List);
   function Get_Element(From : in Undirected_Graph;
                               Id   : in Element_Id) return Element;
   function List_Adjacencies(From : in Undirected_Graph;
                             Id   : in Element_Id) return Adjacency_List;
   No_Element_Error : Exception;
private
   type Adjacency_Matrix is array(Element_Id) of Adjacency_List;
   type Element_Record is record
      Filled : Boolean := False;
      The_Element : Element;
   end record;
   type Element_List is array(Element_Id) of Element_Record;
   type Undirected_Graph is tagged record
      Adjacencies : Adjacency_Matrix := (Others => (Others => False));
      Elements    : Element_List;
   end record;
end Fixed_Length_Graph;

This package provides two public data types: Adjacency_List, which is fully exposed to the public, and Undirected_Graph, which is declared to be private and is therefore an opaque type. The completion of the type Undirected_Graph is seen in the private section of the package specification, along with the private types Adjacency_Matrix, Element_Record, and Element_List, which are completely private, having no exposure to the public.
You may notice that Adjacency_List is an array of boolean values and Adjacency_Matrix is an array of Adjacency_List elements.

Ada Package Body

The Ada package body contains the implementation of all the functions and procedures declared in the Ada package specification. The contents of the Ada package body are completely hidden from any the calling subprograms. One consequence of this is that the calling subprogram never needs to be recompiled if only the package body is modified. The calling subprogram depends upon the interface specified in the package specification, not upon the implementation of that interface.
package body Fixed_Length_Graph is



-----------------
-- Add_Element --
-----------------



procedure Add_Element(to : in out Undirected_Graph;
                    Item : in Element;
                      Id : in Element_Id)is
begin
   To.Elements(Id).The_Element := Item;
   To.Elements(Id).Filled := True;
end Add_Element;



---------------------
-- Add_Adjacencies --
---------------------



procedure Add_Adjacencies(to : in out Undirected_Graph;
                        Item : in Element_Id;
                        List : in Adjacency_List) is
begin
   for I in List'Range loop
      To.Adjacencies(Item)(I) := List(I);
      To.Adjacencies(I)(Item) := List(I);
   end loop;
end Add_Adjacencies;



-----------------
-- Get_Element --
-----------------



function Get_Element(From : in Undirected_Graph;
                       Id : in Element_Id) return Element is
begin
   if From.Elements(Id).Filled then
      return From.Elements(ID).The_Element;
   else
      raise No_Element_Error;
   end if;
end Get_Element;



----------------------
-- List_Adjacencies --
----------------------



function List_Adjacencies(From : in Undirected_Graph;
                            Id : in Element_Id) return Adjacency_List is
begin
   return From.Adjacencies(Id);
end List_Adjacencies;



end Fixed_Length_Graph;
Remember that the Adjacency_Matrix is defined as an array of arrays, not as a two-dimensional array. This was done to simplify the ability to return the adjacencies associated with a specific entity or node.

Testing the Undirected Graph Package

In this test I have decided to create a graph of bounded string values. The graph I am representing is shown in the diagram below.

Test Source Code

------------------------------------------------------------------
-- Second test of Fixed_Length_Graph package --
------------------------------------------------------------------
with Ada.Text_Io; use Ada.Text_IO;
with Ada.Strings.Bounded;
with Fixed_Length_Graph;

procedure Graph_Test_02 is
   package B_Strings is new Ada.Strings.Bounded.Generic_Bounded_Length(25);
   use B_Strings;
   package Str_Graph is new Fixed_Length_Graph(B_Strings.Bounded_String, 7);
   use Str_Graph;
   The_Graph: Undirected_Graph;
   Adj_List : Adjacency_List;

   Subtype Index is Positive range 1..7;
   type Str_Array is array(Index) of B_Strings.Bounded_String;
   Names : Str_Array;


   Adj_Array : Array(Index) of Adjacency_List;

begin
   Names(1) := To_Bounded_String("One");
   Names(2) := To_Bounded_String("Two");
   Names(3) := To_bounded_String("Three");
   Names(4) := To_Bounded_String("Four");
   Names(5) := To_Bounded_String("Five");
   Names(6) := To_Bounded_String("Six");
   Names(7) := To_Bounded_String("Seven");
   for I in Names'Range loop
      The_Graph.Add_Element(Names(I), I);
   end loop;
   Adj_Array(1) := (2 => True, 3 => True, Others => False);
   Adj_Array(2) := (1 => True, 3 => True, 4 => True, Others => False);
   Adj_Array(3) := (1 => True, 2 => True, Others => False);
   Adj_Array(4) := (2 => True, 5 => True, 6 => True, Others => False);
   Adj_Array(5) := (4 => True, 7 => True, Others => False);
   Adj_Array(6) := (4 => True, 7 => True, Others => False);
   Adj_Array(7) := (5 => True, 6 => True, Others => False);

   for I in Adj_Array'Range loop
      The_Graph.Add_Adjacencies(I, Adj_Array(I));
   end loop;

   for I in Element_Id'Range loop
      Put(To_String(The_Graph.Get_Element(I)) & "-> ");
      Adj_List := The_Graph.List_Adjacencies(I);
      for J in Adj_List'Range loop
         if Adj_List(J) = True then
            Put(To_String(The_Graph.Get_Element(J)) & " ");
         end if;
      end loop;
      New_Line;
   end loop;

end Graph_Test_02;

The output of this program is:



One-> Two Three
Two-> One Three Four
Three-> One Two
Four-> Two Five Six
Five-> Four Seven
Six-> Four Seven

Seven-> Five Six