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