# Adjacency Maps and Efficient Graph Algorithms
## 1 Introduction
The incoming list corresponding to vertex \(v\) contains all edges \((u,v)\in E\) coming into vertex \(v\), for all vertices \(v\in V\). The outgoing list corresponding to vertex \(v\) contains all edges \((v,w)\in E\) going out of vertex \(v\), for all vertices \(v\in V\). The source vertex \(v\) and the target vertex \(w\) are associated with each edge \((v,w)\in E\). The adjacency list representation of a directed graph is illustrated in Figure 1. The small collection of 11 abstract operations can be implemented using the adjacency list representation to take \(O(1)\) time, with the exception of \(G\_adjacent(v,w)\), which takes \(O(\min(\text{outdeg}(v),\text{indeg}(w)))\) time, and \(G\_del\_node(v)\), which takes \(O(\text{deg}(v))\) time, as follows:  
* \(G\_vertices()\) and \(G\_edges()\) are respectively the list of vertices and the list of edges of graph \(G\). * \(G\_incoming(v)\) and \(G\_outgoing(v)\) are respectively the list of edges coming into vertex \(v\) and the list of edges going out of vertex \(v\). * \(G\_adjacent(v,w)\) is implemented by scanning the list of edges going out of vertex \(v\), or the list of edges coming into vertex \(w\). * \(G\_source(e)\) and \(G\_target(e)\) are respectively the source and the target vertex associated with edge \(e\). * \(G\_new\_vertex()\) is implemented by appending a new vertex \(v\) to the list of vertices of graph \(G\), and returning vertex \(v\). * \(G\_new\_edge(v,w)\) is implemented by appending a new edge \(e\) to the list of edges of graph \(G\), setting to \(v\) the source vertex associated with edge \(e\), setting to \(w\) the target vertex associated with edge \(e\), appending \(e\) to the list of edges going out of vertex \(v\) and to the list of edges coming into vertex \(w\), and returning edge \(e\). * \(G\_del\_vertex(v)\) is implemented by performing \(G\_del\_edge(e)\) for each edge \(e\) in the list of edges coming into vertex \(v\) and for each edge \(e\) in the list of edges going out of vertex \(v\), and then deleting vertex \(v\) from the list of vertices of graph \(G\). * \(G.del\_edge(e)\) is implemented by deleting edge \(e\) from the list of edges of graph \(G\), from the list of edges coming into vertex \(G.target(e)\), and from the list of edges going out of vertex \(G.source(e)\). The adjacency list representation of a graph \(G=(V,E)\) with \(n\) vertices and \(m\) edges takes \(O(n+m)\) space, and it allows for implementing graph algorithms such as depth-first search, biconnectivity, acyclicity, planarity testing, topological sorting, and many others to take \(O(n+m)\) time [6; 7]. In the adjacency list representation of a graph, edges can also be made explicit by replacing the lists of incoming and outgoing edges with dictionaries of source vertices to incoming edges and target vertices to outgoing edges. This allows for a more efficient adjacency test, although adding a logarithmic factor to the cost to all of the operations (when dictionaries are implemented using balanced trees) or turning the worst-case cost for all of the operations into expected cost (when dictionaries are implemented using hashing). Such a representation was advocated in [5; 8], and adopted as the default graph representation in the NetworkX package for network analysis in Python [9]. Essentially, the adjacency map representation of a graph consists of a dictionary \(D\) of vertices to a pair of dictionaries of vertices to edges: a first dictionary \(I\) of source vertices to incoming edges, and a second dictionary \(O\) of target vertices to outgoing edges. Definition 2: Let \(G=(V,E)\) be a graph with \(n\) vertices and \(m\) edges. The adjacency map representation of \(G\) consists of a dictionary of \(n\) elements (the vertices of the graph) to a pair of dictionaries of \(m\) elements (the source and target vertices for the edges of the graph, respectively). The incoming dictionary corresponding to vertex \(v\) contains the mappings \((u,(u,v))\) for all edges \((u,v)\in E\) coming into vertex \(v\), for all vertices \(v\in V\).