3.1 Adjacency List

An adjacency list, $A$, is a data type for representing adjacency relationships of the sparse graph $G=(V,E)$. 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 $i$ to vertex $j$ as an ordered pair of vertex labels $(i,j)$. Descriptive information is usually associated with each edge.

More specifically, the following operations are supported on an adjacency list $A$:

• Insert adds an arbitrary edge $(i,j)$ to $A$. If edge $(i,j)$ is not already in the list, insert signals a successful insertion.

• Get retrieves an arbitrary edge $(i,j)$ from $A$. When edge $(i,j)$ is in $A$, get signals a successful lookup.

• Scan permits sequential access to all edges incident upon vertex $i$. Vertex scans are bounded. More specifically, a vertex scan finds all edges $(i,j)$ such that $j_{{min}}\leq j\leq j_{{max}}$. When scan finds edge $(i,j)$, it returns $j$. 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 $(i,j)$ in $A$.

The algorithms assume that read operations (get and scan) make edge information available in a buffer (this buffer is usually denoted by the symbol $e$). 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.