# Adjacency Maps and Efficient Graph Algorithms
## 2 Materials and Methods  
We have implemented 9 of the 11 abstract operations on graphs in Python, namely  
* \(G\)_vertices\(()\)_
* \(G\)_edges\(()\)_
* \(G\)_incoming\((v)\)_
* \(G\)_outgoing\((v)\)_
* \(G\)_adjacent\((v,w)\)_
* \(G\)_source\((e)\)_
* \(G\)_target\((e)\)_
* \(G\)_new_vertex\(()\)_
* \(G\)_new_edge\((v,w)\)_  
for both the adjacency list and the adjacency map representation, and for labeled vertices and edges. Figure 2 shows the corresponding classes in detail.  
For the benchmark dataset, we have used random directed graphs with \(n=8,16,32,64\), \(128,256\) vertices and \(m=1,\ldots,n(n-1)\) directed edges. These 86,856 directed graphs were generated using the Erdos-Renyi model, by which all (directed) graphs with \(n\) vertices and \(m\) (directed) edges have the same probability [10; 11], as implemented in the NetworkX package for network analysis in Python [9].  
```
classGraph: classVertex: def__init_(self,x=None): self_1b1=x self_1=list() self_O=list() classEdge: def__init_(self,v,w,x=None): self_src=v self_tgt=w self_1b1=x def__init_(self): self_V=list() self_E=list() defvertices(self): returnself_V defedges(self): returnself_E returnself_V defness(self): returnself_V defness(self): returnself_V defness(self): returnself_V defness(self): returnself_E defness(self_D[v]_O[w] forwinself_D[v]_O] defincoming(self,v): returniter(v_I) defoutgoing(self,v): returniter(v_O) defadjacent(self,v,w): iflen(v_O)<len(w_I): returnwin
[e_tgtforeinv_O] else: returnv inself_D[w]_I defsource(self,e): returne_src deftarget(self,e): returne_tgt defnew_vertex(self,x=None): v=self_Vertex(x) self_V_Vappend(v) returnv defnew_edge(self,v,w,x=None): e=self_Edge(v,w,x) self_E.append(e) v_O.append(e) w_I.append(e) returne
```  
Listing 2: Python implementation of the adjacency list (**left**) and adjacency map (**right**) representation of a directed graph.  
In order to compare the performance of the adjacency-list and the adjacency-map representation, we have chosen three graph algorithms:  
* A simple algorithm for constructing a graph from a list of edges, thereby testing the performance of the abstract operations for adding new vertices and edges to a graph.
* An iterative algorithm for the breadth-first traversal of a graph ([5] [Section 5.2]), thereby testing the performance of the abstract operations for iterating over the vertices and edges of the graph.
* An algorithm for finding a universal sink of a directed graph ([2] [Ex. 22.1-6]), thereby testing the performance of the adjacency-test abstract operation.  
Figure 2: Python implementation of the adjacency list (**left**) and adjacency map (**right**) representation of a directed graph.  
The universal sink algorithm, adapted from [1], is shown in Algorithm 2. The first loop, which breaks at the first iteration, is used to set an initial candidate for the universal sink to the first vertex in the order fixed by the representation of the graph (actually, any vertex of the graph would suffice). The second loop is used to discard all but one of the vertices in the graph as candidates for universal sink. The third loop is used to check if the remaining candidate vertex indeed has in-degree equal to the number of vertices of the graph minus one and out-degree zero.  
```
functionuniversal_sink(\(G\)) for all\(v\in\textit{vertices}(G)\)do break for all\(w\in\textit{vertices}(G)\)do if\(v\
eq w\)and\(G.\textit{adjacent}(v,w)\)then \(v=w\) for all\(w\in\textit{vertices}(G)\)do if\(G.\textit{adjacent}(v,w)\)or(\(v\
eq w\)and not\(G.\textit{adjacent}(w,v)\))then return false return true
```  
**Algorithm 2** Finding a universal sink in a directed graph \(G=(V,E)\) with \(|V|\geqslant 2\).  
Assuming the adjacency test takes \(O(1)\) time, the graph construction algorithm, the breadth-first graph traversal algorithm, and the universal sink algorithm all take \(O(n+m)\) time, on a graph with \(n\) vertices and \(m\) directed edges.