3.1 Adjacency List

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

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

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

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

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

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