# Adjacency Maps and Efficient Graph Algorithms
## 3 Results  
We have implemented the simple graph construction algorithm and the universal sink algorithm in Python, taken the Python implementation of the breadth-first graph traversal algorithm from ([5] [Appendix A]), and run the algorithms for graph construction, breadth-first traversal, and universal sink on the 86,856 random directed graphs in the benchmark dataset. Table 1 shows the average running time of each of the three algorithms with the adjacency-list and the adjacency-map representation, over \(n(n-1)=56\), 240, 992, 4032, 16,256, 65,280 random directed graphs with \(n=8,16,32,64,128,256\) vertices, respectively, on a computer with a 12-core Intel Xeon processor and 64 GB of memory.  
The ratio of these average running times (adjacency maps over adjacency lists) for the three graph algorithms are plotted in Figure 3. Graph construction is about 4 times slower with adjacency maps for graphs with at most 16 vertices, but only about 2 times slower for graphs with at least 128 vertices. On the other hand, breadth-first graph traversal and the universal sink algorithm run faster with adjacency maps for all graph sizes in the case of graph traversal and for graphs with at least 64 vertices in the case of universal sink on the average.  
\begin{table}
\begin{tabular}{c c c c c c c} \hline  & \multicolumn{2}{c}{**Construct**} & \multicolumn{2}{c}{**Traversal**} & \multicolumn{2}{c}{**Sink**} \\ \cline{2-7} \(n\) & **List** & **Map** & **List** & **Map** & **List** & **Map** \\ \hline
8 & 0.000098 & 0.000411 & 0.000049 & 0.000038 & 0.000014 & 0.000027 \\
16 & 0.000282 & 0.001071 & 0.000114 & 0.000086 & 0.000020 & 0.000031 \\
32 & 0.000822 & 0.002202 & 0.000321 & 0.000239 & 0.000052 & 0.0 These running times are shown in more detail in Figure 4, where instead of average running times, individual running times are plotted for each of the random directed graphs in the benchmark dataset. Graph construction is almost always slower with adjacency maps for graphs with 8, 16, or 32 vertices, but it is faster with adjacency maps for 170 of the 4032 graphs with 64 vertices, 2870 of the 16,256 graphs with 128 vertices, and 3599 of the 65,280 graphs with 256 vertices in the benchmark dataset.  
Breadth-first graph traversal is almost always faster with adjacency maps: for all the 56 graphs with 8 vertices, 239 of the 240 graphs with 16 vertices, 989 of the 992 graphs with 32 vertices, 4022 of the 4032 graphs with 64 vertices, 16,247 of the 16,256 graphs with 128 vertices, and 65,266 of the 65,280 graphs with 256 vertices in the benchmark dataset. The universal sink algorithm is always slower with adjacency maps for graphs with 8 or 16 vertices, but it is faster with adjacency maps for 394 of the 992 graphs with 32 vertices, 2828 of the 4032 graphs with 64 vertices, 13,839 of the 16,256 graphs with 128 vertices, and 60,582 of the 65,280 of the graphs with 256 vertices in the benchmark dataset.  
Figure 3: Ratio of the average running time with the adjacency-map over the adjacency-list representation, for the graph construction (violet), breadth-first traversal (green), and universal sink (cyan) algorithms, on random directed graphs with \(n=8,16,32,64,128,256\) vertices and \(1,\ldots,n(n-1)\) directed edges.  
Figure 4: Running time (seconds) for the graph construction (**left**), breadth-first traversal (**center**), and universal sink (**right**) algorithms on the benchmark dataset, for the adjacency-list (violet) and adjacency-map (green) representation, on random directed graphs with (**top** to **bottom**) \(n=8,16,32,64,128,256\) vertices and \(1,\ldots,n(n-1)\) directed edges.