3.1 Adjacency List
An adjacency list, , is a data type for representing adjacency relationships of the sparse graph . Adjacency lists are described in more detail in Section 2.3 of this document.
An adjacency list is typically stored in a dynamic data structure that identifies the edge from vertex to vertex as an ordered pair of vertex labels . Descriptive information is usually associated with each edge.
More specifically, the following operations are supported on an adjacency list :
Insert adds an arbitrary edge to . If edge is not already in the list, insert signals a successful insertion.
Get retrieves an arbitrary edge from . When edge is in , get signals a successful lookup.
Scan permits sequential access to all edges incident upon vertex . Vertex scans are bounded. More specifically, a vertex scan finds all edges such that . When scan finds edge , it returns . When a vertex scan has exhausted all entries in its range, a finished signal is emitted.
A scan has two support operations: push and pop. A push suspends the scan at its current position. A pop resumes a suspended scan. The push and pop operations permit scans to be nested.
Put updates the information associated with an arbitrary edge in .
The algorithms assume that read operations (get and scan) make edge information available in a buffer (this buffer is usually denoted by the symbol ). Update operations (insert and put) modify the description of an edge based on the current contents of the communication buffer.
Algorithms for creating adjacency lists are examined in Section 4.