# Adjacency Maps and Efficient Graph Algorithms
## 1 Introduction  
Adjacency lists have been the preferred graph representation for over five decades now because a large number of graph algorithms can be implemented to run in linear time in the number of vertices and edges in the graph using an adjacency-list representation, while no graph algorithm can be implemented to run in linear time using an adjacency-matrix representation. The only exception to the latter is the sparse representation of static directed graphs of [1], which uses (allocated, but uninitialized) quadratic space in the number of vertices in the graph and allows for implementing graph algorithms that test edge existence, such as finding a universal sink (a vertex of in-degree equal to the number of vertices minus one and out-degree zero) in a directed graph ([2] [Ex. 22.1-6]), to run in linear time in the number of vertices and edges in the graph. Graph algorithms can be described using a small collection of abstract operations on graphs, which can be implemented using appropriate data structures such as adjacency matrices, adjacency lists, and adjacency maps. For example, the representation of graphs in the LEDA library of efficient data structures and algorithms [3] supports about 120 abstract operations, and the representation of graphs in the BGL library of graph algorithms [4] supports about 50 abstract operations. A smaller collection of 32 abstract operations is described in [5], which allows for describing most graph algorithms. Actually, the following collection of only 11 abstract operations suffices for describing most of the fundamental graph algorithms, where lists of vertices and edges are arranged in the order fixed by the representation of the graph. Much of the following is adapted from ([5] [Section 1.3]). * \(G.\mathit{vertices}()\) gives a list of the vertices of graph \(G\). * \(G.\mathit{edges}()\) gives a list of the edges of graph \(G\). * \(G.\mathit{incoming}(p)\) gives a list of the edges of graph \(G\) coming into vertex \(v\). * \(G.\mathit{outgoing}(v)\) gives a list of the edges of graph \(G\) going out of vertex \(v\). * \(G.\mathit{adjacent}(v,w)\) is true if there is an edge in graph \(G\) going out of vertex \(v\) and coming into vertex \(w\), and false otherwise. * \(G.\mathit{source}(e)\) gives the source vertex of edge \(e\) in graph \(G\). * \(G.\mathit{target}(e)\) gives the target vertex of edge \(e\) in graph \(G\). * \(G.\mathit{new\_vertex}()\) inserts a new vertex in graph \(G\). * \(G\_new\_edge(v,w)\) inserts a new edge in graph \(G\) going out of vertex \(v\) and coming into vertex \(w\). * \(G\_del\_vertex(v)\) deletes vertex \(v\) from graph \(G\), together with all those edges going out of or coming into vertex \(v\). * \(G\_del\_edge(e)\) deletes edge \(e\) from graph \(G\). These abstract operations apply to both undirected and directed graphs. An undirected graph is the particular case of a directed graph in which for every edge \((v,w)\) of the graph, the reversed edge \((w,v)\) also belongs to the graph. For example, a simple traversal of an undirected graph \(G\), in which vertices and edges are visited in the order fixed by the representation of the graph, can be described using these abstract operations as shown in Algorithm 1. ```
for all\(v\in G\_vertices()\)do for all\(e\in G\_outgoing(v)\)do \(w=G\_target(e)\)...
```  
**Algorithm 1** Simple traversal of an undirected graph \(G\). Essentially, the adjacency list representation of a graph is an array of lists, one for each vertex in the graph, where the list corresponding to a given vertex contains the target vertices of the edges coming out of the given vertex. However, this is often extended by making edges explicit, as follows:  
Definition 1: Let \(G=(V,E)\) be a graph with \(n\) vertices and \(m\) edges. The adjacency list representation of \(G\) consists of a list of \(n\) elements (the vertices of the graph), a list of \(m\) elements (the edges of the graph), and two lists of \(n\) lists of a total of \(m\) elements (the edges of the graph).